The Hidden Rationale Behind ASTC's Use of Integer Sequence Encoding

The choice of compression methods in graphics technologies often involves subtle trade-offs that aren't immediately apparent. The recent article from ryg's blog delves into a fascinating question: why does ASTC (Adaptive Scalable Texture Compression) use Integer Sequence Encoding (ISE) when almost no other compression formats employ this technique?

At first glance, ISE appears to be a suboptimal choice. The article explains that ISE in ASTC handles value ranges with prime factors of 3 or 5, not just powers of 2. For instance, encoding values in the range [0,95] involves using 5 bits for the lower portion and "high trits" (values in [0,2]) for the upper portion. When comparing this to straightforward binary encoding, ISE seems to offer only modest savings—0.4 bits per symbol in the best case.

However, when compared to more sophisticated prefix codes, the savings diminish significantly. For trits (values in [0,2]), prefix codes average approximately 1.67 bits per symbol, while ISE averages about 1.60 bits per symbol—a mere 0.07 bits per symbol difference. With ASTC's limited block size (128 bits total, with at least 17 bits dedicated to headers), the maximum theoretical savings from ISE shrink to under 5 bits, and practically to just 4 bits in the most extreme cases.

The article then reveals the crucial insight: the primary reason for using ISE isn't compression efficiency but predictability. Unlike prefix codes, which produce variable-length outputs depending on the actual data, ISE guarantees a fixed size regardless of content. This predictability is essential for ASTC's design, which infers coding parameters from the remaining bits after headers and other data have been accounted for.

In contexts where block boundaries are rigid and available bits must be precisely known, this determinism outweighs the marginal compression gains of prefix codes. The alternative—using prefix codes—would require additional header bits to handle the variability, potentially negating any savings.

This design choice highlights an important principle in compression: different applications make different trade-offs. Most other compression formats don't use ISE because they either prioritize raw compression efficiency or can afford the overhead of more complex techniques like arithmetic coding when predictability is required.

The article also briefly touches on the "quint" encoding variant for five values, which follows similar principles with comparable efficiency characteristics. This reinforces that the choice of ISE in ASTC is a deliberate decision based on the specific constraints and requirements of texture compression in graphics applications.

Ultimately, ASTC's use of ISE exemplifies how technical standards often make choices that seem counterintuitive without understanding the full context. In this case, the predictability of ISE enables the format to work effectively within its strict bit budget, demonstrating that compression is as much about meeting constraints as it is about minimizing size.