Wrapping every expression with % 2 ** 32 to get a C-like behavior

Question

I'm trying to port the following C loop to Python:

for (int32_t i = 32; --i >= 0;) {
    v0 += ((v1 << 4 ^ v1 >> 5) + v1) ^ (sum + k[sum & 3]);
    sum -= delta;
    v1 += ((v0 << 4 ^ v0 >> 5) + v0) ^ (sum + k[sum >> 11 & 3]);
}

The problem is that the these integers are 32-bit unsigned and the code above relies on integer wrapping. My first attempt was to introduce the U32 class (see here), but after porting this code to Python 3, the solution got so ugly (see here) that I started to looking for other ones. My best idea at the moment is to wrap every expression with % 2 ** 32, so that it wraps around. Here's how this looks:

for _ in range(32):
    v0 = (
        v0
        +
        (
            (
                (v1 << 4) % 2**32 ^ (v1 >> 5) % 2**32
            ) % 2**32
            +
            v1 ^ (sum_ + k[sum_ & 3]) % 2**32
        ) % 2**32
    ) % 2**32

    sum_ = (sum_ - delta) % 2 ** 32

    v1 = (
        v1
        +
        (
            (
                (
                    (v0 << 4) % 2**32 ^ (v0 >> 5) % 2**32
                ) % 2**32 + v0
            ) % 2**32
            ^
            (sum_ + k[(sum_ >> 11) % 2**32 & 3]) % 2**32
        ) % 2**32
    ) % 2**32

It looks strange and I'm not sure it's the best idea. What do you think of it? Is it something that needs improving? If so, how?

Answer 1

The C code you quoted is part of an implementation of the XTEA block cipher. So the obvious thing to do is to search for existing Python implementations, and sure enough, ActiveState has this one by Paul Chakravarti, in which the loop you quoted is translated as follows:

sum,delta,mask = 0L,0x9e3779b9L,0xffffffffL
for round in range(n):
    v0 = (v0 + (((v1<<4 ^ v1>>5) + v1) ^ (sum + k[sum & 3]))) & mask
    sum = (sum + delta) & mask
    v1 = (v1 + (((v0<<4 ^ v0>>5) + v0) ^ (sum + k[sum>>11 & 3]))) & mask

You can see that only three truncations to 32 bits are needed, one at the end of each line. That's because:

1. A right shift can't overflow, so the expressions v1>>5, v0>>5 and sum>>11 don't need to be truncated.

2. (a & mask) ^ (b & mask) is equal to (a ^ b) & mask, so the truncation can be postponed until after the bitwise-exclusive-or operation.

3. ((a & mask) + (b & mask)) & mask is equal to (a + b) & mask, so the truncation can be postponed until after the addition operation.

A final point worth noting is that it makes very little difference (for this application) whether you implement truncation using the & (bitwise-and) or % (integer remainder) operations:

>>> from timeit import timeit
>>> timeit('0x1234567890ABCDEF & 0xffffffff')
0.026652097702026367
>>> timeit('0x1234567890ABCDEF % 0x100000000')
0.025462865829467773

(That's because the numbers in XTEA never get very big, no more than 2³⁷ or so. For large numbers, the bitwise-and operator is much faster than the remainder operator.)

Answer 2

Firstly, the expensive modulo operation % 2**32 can be replaced by a cheap bitwise and: & 2**32-1. Make sure to familiarize yourself with operator precedence, because it's not intuitive when it comes to bitwise operators (if you haven't done that yet).

As a next step, you could use the following properties to optimize the equations:

• (a % m + b % m) % m = (a + b) % m
• (a & n ^ b & n) & n = (a ^ b) & n

That allows you get rid of many of the & 2**32-1 operations at the cost of bigger intermediate results. If you want to make sure to get the highest speed, do some perfs. In any case, it will make the code much more readable.