Armed with a text editor

mu's views on program and recipe! design

Puzzling Answers Posted 2006.05.18 07:02 PDT (#)

So what does ''.join(chr(sum(((val >> i) & 1) << (7-i) for i in range(8))) for val in range(256)) do? If you run it on python2.4 you get an ugly string. Specifically it's a list of 256 bytes with their bits swapped in order of significance: 01 becomes 80 and so forth.

But why is this useful? Thanks to Joe's work it's now part of Mutagen, and is being used as part of a scheme to calculate the kind of CRC32 that the Ogg container (of Ogg Vorbis) requires. Why a scheme? Speed. As an interpreted language, python isn't well suited to small bit calculations on large sets of numbers. A standard reduce(lambda x, y: table[(x>>24) ^ y] ^ (x << 8), data, 0) scheme is too slow for comfort. However the table used in the existing C implementations zlib.crc32 and binascii.crc32 is from the bitwise reversed generator polynomial of the one used for Ogg.

Peter Johnson came to the rescue and figured out we could get the same effect by bitswapping each byte of the data and then bitswapping the final 32-bit result. Thanks to str.translate, we hoist most of the work into C, and the above puzzler code runs once at module import to generate the translation table.

And yes, Joe, it's good for confusing you at 1AM. :)

Categories: puzzle python