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

В настоящее время я работаю над созданием функции, которая принимает два 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 был для меня очень сложным языком, а побитовые операции тем более.

Источник

4 ответа

Решение

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

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;

}

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

Источник

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

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

перестановка

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

// 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);
}
Источник

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

#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)) ;
}
Источник

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

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 в зависимости от требований заказа.

Версия со сменами, где LSB y всегда LSB результата, как в вашем примере, это:

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;
}

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

Источник
Другие вопросы по тегам