4
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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 237 or so. For large numbers, the bitwise-and operator is much faster than the remainder operator.)

\$\endgroup\$
  • \$\begingroup\$ Generally, bitwise and has a smaller complexity than the modulo (O(n) vs O(n^2)), so that's an interesting find \$\endgroup\$ – copy Dec 8 '13 at 16:56
  • \$\begingroup\$ @copy: Big-O notation describes the asymptotic performance of algorithms (their runtime as n → ∞). Here n is small and the runtime is dominated by the Python interpreter and bignum implementation overhead. \$\endgroup\$ – Gareth Rees Dec 8 '13 at 17:37
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Isn't it enough to create an additional global constant, say, M? \$\endgroup\$ – d33tah Dec 7 '13 at 1:18
  • \$\begingroup\$ @d33tah What for? \$\endgroup\$ – copy Dec 7 '13 at 1:36
  • \$\begingroup\$ Also, you only need to mask/truncate for operations that could overflow. So right-shifts (>>) don't need to be altered. Since you're dealing with "unsigned" values, take some time to be sure you don't end up with negative numbers due to subtractions; your shifts and modulo operations won't work the way you expect with negatives. \$\endgroup\$ – bonsaiviking Dec 7 '13 at 1:55
  • \$\begingroup\$ Note you can also spell 2**32-1 as 0xFFFFFFFF and save the computation and/or lookup (at the cost of more places to update if you change things). \$\endgroup\$ – Michael Urman Dec 7 '13 at 1:57
  • \$\begingroup\$ "Firstly, the expensive modulo operation can be replaced by a cheap bitwise and" — can you justify this claim? When I try timing them, I can find no significant difference in speed between these two operations in Python. \$\endgroup\$ – Gareth Rees Dec 8 '13 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.