Bitwise Rotate Right

Question

I am trying to convert this C function into Python;

typedef unsigned long var;
    /* Bit rotate rightwards */
    var ror(var v,unsigned int bits) {
        return (v>>bits)|(v<<(8*sizeof(var)-bits));
    }

I have tried Googling for some solutions, but I can't seem to get any of them to give the same results as the one here.

This is one solution I have found from another program;

def mask1(n):
   """Return a bitmask of length n (suitable for masking against an
      int to coerce the size to a given length)
   """
   if n >= 0:
       return 2**n - 1
   else:
       return 0

def ror(n, rotations=1, width=8):
    """Return a given number of bitwise right rotations of an integer n,
       for a given bit field width.
    """
    rotations %= width
    if rotations < 1:
        return n
    n &= mask1(width)
    return (n >> rotations) | ((n << (8 * width - rotations)))

I am trying to btishift key = 0xf0f0f0f0f123456. The C code gives 000000000f0f0f12 when it is called with; ror(key, 8 << 1) and Python gives; 0x0f0f0f0f0f123456 (the original input!)

Why are you passing in `8 << 1`for the rotations then? That's larger than `width`, so you end up with 0 rotations (`16 % 8` is 0). — Martijn Pieters, Nov 27 '14 at 17:40
It's in a loop up to 3. So it will rotations will be `8 << 0`, `8<<1`, `8<<2`. — Jake Evans, Nov 27 '14 at 17:44
All those are larger than `width` *and* multiples of `width`, so `rotations %= width` will always be `0`. — Martijn Pieters, Nov 27 '14 at 17:46
I understand that. If I change `width` I get results that are still not comparable to that of the C output. — Jake Evans, Nov 27 '14 at 17:49
The C output looks like a rotation by 16 bits, with a mask of 32 bits. I have no idea why you are using `rotations %= width` at all here. — Martijn Pieters, Nov 27 '14 at 17:54
Martijn Peters already explained why Python gives the original input (the rotation is a multiple of the width). So why place the bounty? If there is another example which gives the wrong answer (where the rotation is not a multiple of the width), edit the question to show it. — interjay, Dec 01 '14 at 13:05
For the record: best-practices rotates in C: http://stackoverflow.com/questions/776508/circular-shift-rotate-operations-in-c — Peter Cordes, Aug 17 '15 at 17:23

score 5 · Answer 1 · answered Dec 01 '14 at 13:11

Your C output doesn't match the function that you provided. That is presumably because you are not printing it correctly. This program:

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

uint64_t ror(uint64_t v, unsigned int bits) 
{
    return (v>>bits) | (v<<(8*sizeof(uint64_t)-bits));
}

int main(void)
{
    printf("%llx\n", ror(0x0123456789abcdef, 4));
    printf("%llx\n", ror(0x0123456789abcdef, 8));
    printf("%llx\n", ror(0x0123456789abcdef, 12));
    printf("%llx\n", ror(0x0123456789abcdef, 16));
    return 0;
}

produces the following output:

f0123456789abcde
ef0123456789abcd
def0123456789abc
cdef0123456789ab

To produce an ror function in Python I refer you to this excellent article: http://www.falatic.com/index.php/108/python-and-bitwise-rotation

This Python 2 code produces the same output as the C program above:

ror = lambda val, r_bits, max_bits: \
    ((val & (2**max_bits-1)) >> r_bits%max_bits) | \
    (val << (max_bits-(r_bits%max_bits)) & (2**max_bits-1))

print "%x" % ror(0x0123456789abcdef, 4, 64)
print "%x" % ror(0x0123456789abcdef, 8, 64)
print "%x" % ror(0x0123456789abcdef, 12, 64)
print "%x" % ror(0x0123456789abcdef, 16, 64)

fuzzydrawrings · Answer 2 · 2020-05-03T20:54:22.953

5

The shortest way I've found in Python: (note this works only with integers as inputs)

def ror(n,rotations,width):
    return (2**width-1)&(n>>rotations|n<<(width-rotations))

edited May 03 '20 at 20:54

answered May 03 '20 at 20:41

fuzzydrawrings

283
2
6

score 3 · Answer 3 · edited Jun 20 '20 at 09:12

There are different problems in your question.

C part :

You use a value of key that is a 64 bits value (0x0f0f0f0f0f123456), but the output shows that for you compiler unsigned long is only 32 bits wide. So what C code does is rotating the 32 bits value 0x0f123456 16 times giving 0x34560f12

If you had used unsigned long long (assuming it is 64 bits on your architecture as it is on mine), you would have got 0x34560f0f0f0f0f12 (rotation 16 times of a 64 bits)

Python part :

The definition of width between mask1 and ror is not consistent. mask1 takes a width in bits, where ror takes a width in bytes and one byte = 8 bits.

The ror function should be :

def ror(n, rotations=1, width=8):
    """Return a given number of bitwise right rotations of an integer n,
       for a given bit field width.
    """
    rotations %= width * 8  #  width bytes give 8*bytes bits
    if rotations < 1:
        return n
    mask = mask1(8 * width)  # store the mask
    n &= mask
    return (n >> rotations) | ((n << (8 * width - rotations)) & mask)  # apply the mask to result

That way with key = 0x0f0f0f0f0f123456, you get :

>>> hex(ror(key, 16))
'0x34560f0f0f0f0f12L'
>>> hex(ror(key, 16, 4))
'0x34560f12L'

exactly the same as C output

score 2 · Answer 4 · answered Jul 30 '20 at 14:08

i know its nearly 6 years old

I always find it easier to use string slices than bitwise operations.

def rotate_left(x, n):
    return int(f"{x:032b}"[n:] + f"{x:032b}"[:n], 2)

def rotate_right(x, n):
    return int(f"{x:032b}"[-n:] + f"{x:032b}"[:-n], 2)

score 1 · Answer 5 · answered Nov 23 '19 at 07:52

def rotation_value(value, rotations, widht=32):
    """ Return a given number of bitwise left or right rotations of an interger 
    value,
    for a given bit field widht.
    if rotations == -rotations:
        left
    else:
        right
    """
    if int(rotations) != abs(int(rotations)):
        rotations = widht + int(rotations)
    return (int(value)<<(widht-(rotations%widht)) | (int(value)>>(rotations%widht))) & ((1<<widht)-1)

Bitwise Rotate Right

5 Answers5

C part :

Python part :

Linked

Related