7-Zip LZMA Floating-Point Calculations Explained

7-Zip does not use floating-point calculations during LZMA encoding; instead, it relies entirely on fixed-point arithmetic, scaled integers, and precomputed lookup tables. This architectural choice guarantees cross-platform determinism, enhances computational efficiency, and prevents precision mismatches across different processor architectures.

The Requirement for Determinism

A primary design requirement for lossless compression tools like 7-Zip is binary determinism. If an encoder utilized hardware floating-point operations (FPU or vector float extensions), variations in processor microarchitectures, compiler optimizations, and rounding modes (such as differences between IEEE 754 implementations or x87 extended precision versus SSE) could result in different output streams for the identical input. By strictly eliminating floating-point math, 7-Zip guarantees that LZMA produces bit-for-bit identical output regardless of the host CPU.

Fixed-Point Probability Modeling

The LZMA entropy coder is a variant of a range coder, which continuously updates binary state probabilities. In pure mathematics, probabilities are real numbers between 0.0 and 1.0. LZMA implements these values as fixed-point integers:

  • State Scaling: LZMA scales probabilities using an integer constant (typically kBitModelTotal = 2048, representing an 11-bit fixed-point scale). A probability of 0.5 is represented as 1024.
  • Probability Adaptation: When a bit is processed, the model adapts using an integer shift formula: Prob = Prob - (Prob >> MoveBits) + (Bit ? ((kBitModelTotal - 1) >> MoveBits) : 0) This operation relies entirely on bitwise shifts, additions, and subtractions, bypassing the need for floating-point calculations.

Logarithmic Bit-Cost Estimation

During parsing, especially in maximum compression modes, LZMA uses an optimal parser (similar to the Viterbi algorithm) to determine whether to emit a literal, a match, or a repeat match. Evaluating the most cost-effective path requires estimating the bit cost (entropy) of encoding a symbol, mathematically defined as \(-\log_2(P)\).

Computing logarithms with standard floating-point functions (such as log2() or pow()) in real-time would create severe CPU bottlenecks and precision discrepancies. 7-Zip solves this by:

  1. Precomputed Lookup Tables: Initializing an integer-based table (such as ProbPrices) during setup.
  2. Integer Indexing: Mapping the 11-bit state probability directly to an entry in the table.
  3. Fixed-Point Bit Costs: Representing bit costs as integers shifted by a scaling factor (e.g., fractional bits shifted by 6 or 8 bits).

When evaluating paths, the cost accumulator simply adds these integer prices together, executing basic integer addition rather than floating-point accumulation.

Match Finding and Memory Addressing

The match-finding stage of LZMA uses algorithms such as Hash Chains (HC) and Binary Trees (BT). These components operate directly on raw byte arrays, memory offsets, and integer distance metrics. Match lengths, match distances, and dictionary window pointers are strictly managed via integer indices, requiring zero floating-point computation.

Hardware Efficiency

By confining all mathematical operations to basic integer logic:

  • The algorithm runs efficiently on embedded hardware and low-power architectures lacking a dedicated Floating-Point Unit (FPU).
  • The CPU maintains pipeline efficiency without switching between general-purpose registers and floating-point/vector registers.
  • Compiler optimizations (such as loop unrolling and branch prediction) remain simple and consistent across various compilation targets.