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.

The strength of the book is that the presented code is not platform specific. Rather than limiting the scope to the platforms the author is most familiar with, he first introduces a simple general purpose assembly language. All code snippets in the book are written in either this assembly language or C. This allows the reader to understand the examples quickly and easily. Of course it's possible that not all instructions of the book's assembly language are available in the assembly language of the architecture you're using. This is not much of a concern though because the author shows how to simulate more complex instructions ( like arithmetic shifts or rotate ) on architectures where these instructions are not offered by the CPU.

The 290 pages of the book are divided into 16 chapters: Introduction, Basics, Power-of-2 Boundaries, Arithmetic Boundaries, Counting Bits, Searching Words, Rearranging Bits and Bytes, Multiplication, Integer Division, Integer Division by Constants, Some Elementary Functions, Unusual Bases for Number Systems, Gray Code, Hilbert's Curve, Floating-Point, and Formulas for Primes.

The first few chapters are basically all about fiddling with bits and a combination of simple bit-wise operations to calculate surprising functions. Later chapters are about more complex calculations like division, square roots, cube roots, and exponentiation. In the end he presents algorithms for special applications like a recursive algorithm to calculate the Hilbert's curve or how to calculate prime numbers.

In my experience there are at least four different situations where the book is useful:
  1. You need to emulate complex operations on architectures with a limited instruction set.
  2. You need to make arithmetic or logical functions smaller or faster.
  3. You're in awe about the mathematical tricks people can think of when they're limited to slow computers with little RAM and you want to learn from the masters.
  4. You want to win "Who can write function X using the least number of x86 instructions" challenges somewhere on the internet.

So, if you feel like you belong into one of those four groups it might be time to give the book a try. Hacker's Delight is less then $40 on Amazon right now. That's a fair price in my opinion.

Trackbacks

No Trackbacks

Comments

Display comments as Linear | Threaded

Mike on :

Thanks for introducing me to this book. I'd like to read it if I ever get the time.

Add Comment

Enclosing asterisks marks text as bold (*word*), underscore are made via _word_.
Standard emoticons like :-) and ;-) are converted to images.
BBCode format allowed
Form options

Submitted comments will be subject to moderation before being displayed.