1

I was looking at the below bit reversal code and just wondering how does one come up with these kind of things. (source : http://www.cl.cam.ac.uk/~am21/hakmemc.html)

/* reverse 8 bits (Schroeppel) */
unsigned reverse_8bits(unsigned41 a) {
  return ((a * 0x000202020202)  /* 5 copies in 40 bits */
             & 0x010884422010)  /* where bits coincide with reverse repeated base 2^10 */
                                /* PDP-10: 041(6 bits):020420420020(35 bits) */
             % 1023;            /* casting out 2^10 - 1's */
}

Can someone explain what does comment "where bits coincide with reverse repeated base 2^10" mean? Also how does "%1023" pull out the relevent bits? Is there any general idea in this?

3
  • 2
    write down the binary representation of the numbers and try to track down what's happening
    – phoxis
    Commented Aug 2, 2013 at 7:05
  • 1
    @phoxis Either you are assuming that the bits that are set in the input do not interfere, and you should justify this assumption in an answer (it's fine to just give leads for a broad question such as this). Or you are not assuming that the bits set in the input do not interfere through * 0x000202020202 … and your comment, akin to “just put some inputs in and see what happens”, would apply as well to the inversion of a cryptographic hash function. Commented Aug 2, 2013 at 7:19
  • Explanation of this question is extremely broad, so better is the person gets started at some point. Representing the constants in binary will get some idea i believe therefore suggested to do so.
    – phoxis
    Commented Aug 2, 2013 at 7:40

2 Answers 2

3

It is a very broad question you are asking.

Here is an explanation of what % 1023 might be about: you know how computing n % 9 is like summing the digits of the base-10 representation of n? For instance, 52 % 9 = 7 = 5 + 2. The code in your question is doing the same thing with 1023 = 1024 - 1 instead of 9 = 10 - 1. It is using the operation % 1023 to gather multiple results that have been computed “independently” as 10-bit slices of a large number.

And this is the beginning of a clue as to how the constants 0x000202020202 and 0x010884422010 are chosen: they make wide integer operations operate as independent simpler operations on 10-bit slices of a large number.

3
  • 1
    Thanks Pascal. This makes lot of sense. I split the binary of 0x010884422010 into 10 bits set and all the 1's in the set occupy complementary positions. So, %1023 should pull all the bits. This is very cool
    – chappar
    Commented Aug 2, 2013 at 7:23
  • Here is the 10 bits split of 0x010884422010. 0000000001 0000100010 0001000100 0010001000 0000010000
    – chappar
    Commented Aug 2, 2013 at 7:25
  • @chappar Oh, so together we arrived to a complete explanation then… Well done. Commented Aug 2, 2013 at 7:25
1

Expanding on Pascal Cuoq idea, here is an explaination.

The general idea is, in any base, if any number is divided by (base-1), the remainder will be sum of all the digits in the number.

For example, 34 when divided by 9 leaves 7 as remainder. This is because 34 can be written as 3 * 10 + 4

i.e. 34 = 3 * 10 + 4 = 3 * (9 +1) + 4 = 3 * 9 + (3 +4)

Now, 9 divides 3 * 9, leaving remainder (3 + 4). This process can be extended to any base 'b', since (b^n - 1) is always divided by (b-1).

Now, coming to the problem, if a number is represented in base 1024, and if the number is divided by 1023, the remainder will be sum of its digits.

To convert a binary number to base 1024, we can group bits of 10 from the right side into single number

For example, to convert binary number 0x010884422010(0b10000100010000100010000100010000000010000) to base 1024, we can group it into 10 bits number as follows

(1) (0000100010) (0001000100) (0010001000) (0000010000) = 
(0b0000000001)*1024^4 + (0b0000100010)*1024^3 + (0b0001000100)*1024^2 + (0b0010001000)*1024^1 + (0b0000010000)*1024^0

So, when this number is divided by 1023, the remainder will sum of

  0b0000000001
+ 0b0000100010
+ 0b0001000100
+ 0b0010001000
+ 0b0000010000
--------------------
  0b0011111111

If you observe the above digits closely, the '1' bits in each above digit occupy complementay positions. So, when added together, it should pull all the 8 bits in the original number.

So, in the above code, "a * 0x000202020202", creates 5 copies of the byte "a". When the result is ANDed with 0x010884422010, we selectively choose 8 bits in the 5 copies of "a". When "% 1023" is applied, we pull all the 8 bits.

So, how does it actually reverse bits? That is bit clever. The idea is, the "1" bit in the digit 0b0000000001 is actually aligned with MSB of the original byte. So, when you "AND" and you are actually ANDing MSB of the original byte with LSB of the magic number digit. Similary the digit 0b0000100010 is aligned with second and sixth bits from MSB and so on.

So, when you add all the digits of the magic number, the resulting number will be reverse of the original byte.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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