Bit-Manipulation Decodable (BMD) Decoder

In QF8, values are stored as fixed-point logarithms. To accumulate products in linear domain (the Kulisch accumulation strategy), each log-code must be converted back to a linear value. A BMD decoder is a way to do this conversion using only cheap integer operations — no floating-point unit required.

Definition

A decoder D̂: {0,1}^B → ℝ is bit-manipulation decodable if it can be expressed as a fixed-length straight-line program over {+, −, ×, ≫, ≪, &, |, ⊕} on machine-word integers, with the output reinterpreted as a float via type punning.

The key insight is that IEEE 754 floating-point bit patterns are approximately linear in log₂(x) — the same observation behind the famous Quake III fast inverse square root hack. BMD decoders exploit this structure.

BMD Realizations for Log-Uniform Decoding

The log-uniform quantizer decode function D̂(n) = a · rⁿ admits three BMD implementations:

1. Lookup Table

• Cost: O(N) storage, O(1) read
• For QF8 with 4 fractional bits: 16-entry LUT (compared to 64 entries for Johnson's ELMA, which uses 6 fractional bits)
• This is the approach used in the QF8 hardware design

2. Reinterpret Cast (Quake Trick)

• Compute I = αn + β as an integer, then reinterpret the bit pattern as IEEE 754 float
• Cost: 1 multiply + 1 add + type pun = 3 ops
• Exploits the fact that the IEEE 754 bit pattern is approximately linear in log₂(x)
• Named after the Quake III fast inverse square root, which uses the same bit-reinterpretation trick

3. Quadratic Approximation

• Decompose the code into integer part e and fractional part f, then:

$$2^{e+f} = 2^e \cdot (1 + 0.6602f + 0.3398f^2)$$

• Cost: 2 multiplies + 2 adds + 1 shift = 5 ops
• Maximum relative error: 0.27% (minimax optimal for constrained quadratic)
• The coefficients 0.6602 and 0.3398 are chosen to minimize the worst-case error over f ∈ [0, 1)

BMD Decoder Characterization Conjecture

The class of monotone BMD decoders from B-bit integers to positive reals is conjectured to be exactly the class of functions expressible as D̂(n) = float_reinterpret(a·n + b) for integer constants a, b, or compositions of a bounded number of such reinterpretations with integer arithmetic. This remains unproven and is listed as an open question in the QF8 paper.