2

I need to rotate a 64 bit value using 2 32 bit registers. Has anyone come across an efficient way of doing this?

giroy
  • 2,203
  • 6
  • 27
  • 38

3 Answers3

4

Well, a normal rotate can be implemented like this: 

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

So, here's a guess at a 64-bit implementation with 32-bit vars:

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

Basically, I'm just taking the rotated bits from the high word and OR-ing them with the low word, and vice-versa.

Here's a quick test: 

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);
    }
}
Seth
  • 45,033
  • 10
  • 85
  • 120
  • @jsl4tv hmm, you're right. However, shifts between 32 and 63 bits could be faked by rotating twice (once with 31, and again with 32 - n). Not exactly efficient, maybe I'll figure out a better algorithm. – Seth Jul 24 '10 at 04:42
  • If `n>=32` just swap the 32-bit words to begin with then perform the `n<32` algorithm as usual. – R.. GitHub STOP HELPING ICE Jul 24 '10 at 07:34
0

Here's an alternative implementation that swaps values when n >= 32. It also handles the case when n = 0 or n = 32, which causes hi >> (32 - n) to be shifted more than the type width, resulting in undefined behavior.

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));
}
Carl Ekerot
  • 2,078
  • 1
  • 16
  • 10
0

This is how it looks like in assembly

;-------------------------------------------------------------------------------
; Rol64
; EXTERN_C UINT64 CDECL Rol64(UINT64,INT);
;-------------------------------------------------------------------------------
; In:
;   eax:edx = 64bit value to rotate
;   dl      = number of bits to rotate
; Return:
;   rotated value in eax:edx
;-------------------------------------------------------------------------------

BeginCDECL Rol64

   ;- parameters --------------------------------------------------
   in_Lo  EQU DWORD PTR [esp + 04h]
   in_Hi  EQU DWORD PTR [esp + 08h]
   in_Cnt EQU DWORD PTR [esp + 0Ch]


 ; get parameters
 mov eax, in_Lo
 mov edx, in_Hi
 mov ecx, in_Cnt

 ; count modula 64
 and cl, 03Fh

 ; zero?
 cmp cl, 0
 jz short rol64_exit

 ; shift above 32? then exchange hi/lo
 cmp cl, 020h
 jc short rol64_noxchg
   xchg eax, edx
 rol64_noxchg:

 ; save registers
 push ebx

 ; low, forward
 mov ebx, eax
 shl ebx, cl
 push ebx

 ; high, forward
 mov ebx, edx
 shl ebx, cl

 ; get reverse count
 mov ch, 32
 sub ch, cl
 mov cl, ch

 ; high, reverse
 shr eax, cl
 or ebx, eax

 ; low, reverse
 pop eax
 shr edx, cl
 or eax, edx

 ; move tmp to high
 mov edx, ebx

 ; restore registers
 pop ebx

 ; done
 rol64_exit:
 ret

EndCDECL Rol64
Arnoud Mulder
  • 139
  • 1
  • 5