Чередование 4-х байтовых int до 8-байтовых int

Question

В настоящее время я работаю над созданием функции, которая принимает два 4-байтовых целых числа без знака и возвращает 8-байтовый код без знака. Я пытался основывать свою работу на методах, описанных этим исследованием , но все мои попытки оказались безуспешными. Конкретные входы, с которыми я работаю: 0x12345678 и 0xdeadbeef, и результат, который я ищу, равен 0x12de34ad56be78ef. Это моя работа до сих пор:

unsigned long interleave(uint32_t x, uint32_t y){
    uint64_t result = 0;
    int shift = 33;

    for(int i = 64; i > 0; i-=16){
        shift -= 8;
        //printf("%d\n", i);
        //printf("%d\n", shift);
        result |= (x & i) << shift;
        result |= (y & i) << (shift-1);
    }
}

Однако эта функция продолжает возвращать 0xfffffffe, что неверно. Я печатаю и проверяю эти значения, используя:

printf("0x%x\n", z);

и ввод инициализируется следующим образом:

uint32_t x = 0x12345678;
uint32_t y = 0xdeadbeef;

Любая помощь по этой теме будет принята с благодарностью, C был для меня очень сложным языком, а побитовые операции - тем более.

Answer 1

Это может быть сделано на основе чередования битов , но пропуская некоторые шаги, чтобы он чередовал только байты. Идея та же: сначала разбейте байты за пару шагов, затем объедините их.

Вот план, проиллюстрированный моими удивительными навыками рисования от руки:

В С (не проверено):

// step 1, moving the top two bytes
uint64_t a = (((uint64_t)x & 0xFFFF0000) << 16) | (x & 0xFFFF);
// step 2, moving bytes 2 and 6
a = ((a & 0x00FF000000FF0000) << 8) | (a & 0x000000FF000000FF);
// same thing with y
uint64_t b = (((uint64_t)y & 0xFFFF0000) << 16) | (y & 0xFFFF);
b = ((b & 0x00FF000000FF0000) << 8) | (b & 0x000000FF000000FF);
// merge them
uint64_t result = (a << 8) | b;

---

Было предложено использовать SSSE3 PSHUFB, оно будет работать, но есть инструкция, которая может выполнять побитовое чередование за один раз, punpcklbw . Таким образом, все, что нам действительно нужно сделать, это получить значения в векторных регистрах и из них, и эта единственная инструкция просто позаботится об этом.

Не тестировалось:

uint64_t interleave(uint32_t x, uint32_t y) {
  __m128i xvec = _mm_cvtsi32_si128(x);
  __m128i yvec = _mm_cvtsi32_si128(y);
  __m128i interleaved = _mm_unpacklo_epi8(yvec, xvec);
  return _mm_cvtsi128_si64(interleaved);
}

Answer 2

С бит-сдвигом и побитовыми операциями (независимо от порядкового номера):

uint64_t interleave(uint32_t x, uint32_t y){

    uint64_t result = 0;

    for(uint8_t i = 0; i < 4; i ++){
        result |= ((x & (0xFFull << (8*i))) << (8*(i+1)));
        result |= ((y & (0xFFull << (8*i))) << (8*i));
    }

    return result;
}

С указателями (зависит от порядка байтов):

uint64_t interleave(uint32_t x, uint32_t y){

    uint64_t result = 0;

    uint8_t * x_ptr = (uint8_t *)&x;
    uint8_t * y_ptr = (uint8_t *)&y;
    uint8_t * r_ptr = (uint8_t *)&result;

    for(uint8_t i = 0; i < 4; i++){
        *(r_ptr++) = y_ptr[i];
        *(r_ptr++) = x_ptr[i];
    }

    return result;

}

Примечание: это решение принимает порядок байтов с прямым порядком байтов

Answer 3

используйте профсоюзное наказание. Легко оптимизировать компилятор.

#include <stdio.h>
#include <stdint.h>
#include <string.h>

typedef union
{
        uint64_t u64;
        struct 
        {
            union
            {
                uint32_t a32;
                uint8_t a8[4]
            };
            union
            {
                uint32_t b32;
                uint8_t b8[4]
            };
        };
        uint8_t u8[8];
}data_64;

uint64_t interleave(uint32_t a, uint32_t b)
{
    data_64 in , out;

    in.a32 = a;
    in.b32 = b;



    for(size_t index = 0; index < sizeof(a); index ++)
    {

        out.u8[index * 2 + 1] = in.a8[index];
        out.u8[index * 2 ] = in.b8[index];
    }
    return out.u64;
}


int main(void)
{

    printf("%llx\n", interleave(0x12345678U, 0xdeadbeefU)) ;
}

Answer 4

Вы можете сделать это так:

uint64_t interleave(uint32_t x, uint32_t y)
{
     uint64_t z;

     unsigned char *a = (unsigned char *)&x;   // 1
     unsigned char *b = (unsigned char *)&y;   // 1
     unsigned char *c = (unsigned char *)&z;

     c[0] = a[0];
     c[1] = b[0];
     c[2] = a[1];
     c[3] = b[1];
     c[4] = a[2];
     c[5] = b[2];
     c[6] = a[3];
     c[7] = b[3];

     return z;
}

Поменяйте местами a и b на линиях, помеченных 1 в зависимости от требований заказа.

Версия со сдвигами, где младший бит y всегда является младшим битом выхода, как в вашем примере:

uint64_t interleave(uint32_t x, uint32_t y)
{
     return 
           (y & 0xFFull)
         | (x & 0xFFull)       << 8
         | (y & 0xFF00ull)     << 8
         | (x & 0xFF00ull)     << 16
         | (y & 0xFF0000ull)   << 16
         | (x & 0xFF0000ull)   << 24
         | (y & 0xFF000000ull) << 24
         | (x & 0xFF000000ull) << 32;
}

Компиляторы, которые я пробовал, похоже, не справляются с оптимизацией ни одной из версий, поэтому, если это критическая ситуация с производительностью, возможно, предложение встроенной сборки из комментариев является подходящим вариантом.