Эффективный способ выполнения 64-битного поворота с использованием 32-битных значений

Question

Мне нужно повернуть 64-битное значение, используя 2 32-битных регистра.Кто-нибудь сталкивался с эффективным способом сделать это?

Answer 1

Ну, нормальное вращение может быть реализовано так:

unsigned int rotate(unsigned int bits, unsigned int n) {
    return bits << n | (bits >> (32 - n));
}

Итак, вот предположение о 64-битной реализации с 32-битными переменными:

void bit_rotate_left_64(unsigned int hi, unsigned int lo, unsigned int n,
                        unsigned int *out_hi, unsigned int *out_lo) {
    unsigned int hi_shift, hi_rotated;
    unsigned int lo_shift, lo_rotated;

    hi_shift = hi << n;
    hi_rotated = hi >> (32 - n);

    lo_shift = lo << n;
    lo_rotated = lo >> (32 - n);

    *out_hi = hi_shift | lo_rotated;
    *out_lo = lo_shift | hi_rotated;
}

По сути, я просто беру повернутые биты из старшего слова и делаю их с младшим словом, и наоборот.

Вот быстрый тест:

int main(int argc, char *argv[]) { 
    /* watch the one move left */
    hi = 0;
    lo = 1;
    for (i = 0; i < 129; i++) {
        bit_rotate_left_64(hi, lo, 1, &hi, &lo);
        printf("Result: %.8x %.8x\n", hi, lo);
    }

    /* same as above, but the 0 moves left */
    hi = -1U;
    lo = 0xFFFFFFFF ^ 1;
    for (i = 0; i < 129; i++) {
        bit_rotate_left_64(hi, lo, 1, &hi, &lo);
        printf("Result: %.8x %.8x\n", hi, lo);
    }
}

Answer 2

Вот альтернативная реализация, которая меняет значения, когда n> = 32. Она также обрабатывает случай, когда n = 0 или n = 32, что приводит к смещению hi >> (32 - n) больше ширины типа, что приводит к неопределенному поведению.

void
rot64 (uint32_t hi, uint32_t lo, uint32_t n, uint32_t *hi_out, uint32_t *lo_out)
{
    /* Rotations go modulo 64 */
    n &= 0x3f;

    /* Swap values if 32 <= n < 64 */
    if (n & 0x20) {
        lo ^= hi;
        hi ^= lo;
        lo ^= hi;
    }

    /* Shift 0-31 steps */
    uint8_t shift = n & 0x1f;

    if (!shift) {
        *hi_out = hi;
        *lo_out = lo;
        return;
    }

    *hi_out = (hi << shift) | (lo >> (32 - shift));
    *lo_out = (lo << shift) | (hi >> (32 - shift));
}