Jake Evans
Jake Evans

Reputation: 1048

Bitwise Rotate Right

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!)

Upvotes: 10

Views: 35565

Answers (5)

Lars Weber
Lars Weber

Reputation: 7

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

Upvotes: 0

lonny
lonny

Reputation: 319

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)

Upvotes: 3

fuzzydrawrings
fuzzydrawrings

Reputation: 303

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))

Upvotes: 7

Serge Ballesta
Serge Ballesta

Reputation: 149075

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

Upvotes: 4

David Heffernan
David Heffernan

Reputation: 613252

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)

Upvotes: 5

Related Questions