Skip to content

Book review - Hacker's Delight

When the Quake 3 source code was released a while ago, people found a curious function called InvSqrt. This function turned out to calculate the inverse square root of a floating-point number in a pretty cool way (read everything about the function here). Recently someone tried ( unsuccessfully ) to find out the origin of the function and the function was once again on Slashdot and Digg.

Personally I'm not concerned with calculating square roots or their inverses but I'm implementing a compiler for a severely limited RISC architecture right now. This architecture only knows 15 very basic operations. For example there are only logical shifts. Arithmetic shifts and rotate operations have to be compiled to a combination of logical shifts and bit-wise operations like "and" and "or". There's not even a bit-wise "not" instruction. Inversing an operand means xor-ing it with a bitmask with every bit set.

Anyway, the latest round of e-popularity of the InvSqrt function and my current work brings me to this update. Three years ago I bought the first edition of the book Hacker's Delight by Henry S. Warren, Jr (the official website of the book is http://www.hackersdelight.org/ ). On nearly 300 pages it tells the tale of some decades of assembly programming on weird platforms and what tricks people came up to overcome the limits of older computers. An Amazon reviewer describes the book in the following words: "Think of it as 'The Art of Computer Programming, Volume 0: Bit Manipulation'. Except without the annoying Knuth attitude". This describes it well, I think.

Continue reading "Book review - Hacker's Delight"