ANS experimentations with Z80 by Mr.Spiv

 __/\__ - ---------------------------------------------- -__/  \
\\ oO //  ANS experimentations with Z80 by Mr.Spiv       /  \__/
//_--_\  - ------------------------------------------- - \__/  \
   \/                                                       \__/

Since Jarek Duda's ANS (asymmetric numeral system) came out around 2014 I always wanted to try it, but honestly, never got around to do any experimentation until summer 2025. My procrastination abilities are amazing and maths is not really my strongest super power any more. The older I get the less gets into my head, and sticks.. And not helped by the fact that the stuff I do at work tends to reserve the last remaining brain cells I have left. Anyway, the best way to learn is by doing. My main goal was to code ANS implementations whose decoders are suitable for 8-bit systems, mainly the best ever, Z80.

I ended up implementing mock up code in Python and C++ for all three main ANS "variants":

• rANS - a generic arithmetic coding replacement
• tANS - a fully table driven ANS variant, which can be seen as a Huffman coding replacement
• rABS - a two symbol (0 and 1) rANS variant with 1 bit or 1 byte at a time inputs

Decoders in Z80 assembly are also available for tANS and rABS encoders. The entire code base is available in github:
https://github.com/jounikor/ans/

This sad writeup concentrates on tabled ANS i.e. tANS:
https://github.com/jounikor/ans/blob/main/z80_tans_decoder.asm
and the challenges and learnings I had when tinkering with the Z80 assembly versions of decoders. Again this time, I was willing to sacrifice code size and RAM usage over the speed, although the resulting codes are not size coding competition winner material. This writeup leaves the encoding part in most part for the reader as an exercise ;-) Some of the terminology used in this writeup assumes the reader is in general familiar with ANS to some extent.

Since we are targeting to Z80 and 8-bit systems there are practical limitations that will make our lives easier. I chose the maximum size of the alphabet to be 256, and individual symbols are from 0 to 255. All symbol frequencies must fit into 8 bits, which means the maximum single symbol frequency is 255 or less. 0 frequency is reserved for "no symbol" marker. The sum of all symbol frequencies must be a power of 2. Total sum of all symbol frequencies is maximum 256, but not a single symbol can have the maximum frequency (see previous bullet). This implies there should always be at least 2 symbols in the encoded data/file.

I wasted quite a bit of time thinking how to create a table of all symbol frequencies which would comply with the above design limitations but also have a single symbol frequency as a power of 2 value. This would have made encoding symbol frequencies into the compressed file extremely simple i.e. just the powers with a fixed bit length get stored. Despite of my attempts that did not work out and I ended up just ensuring the total sum of all symbols was a power of 2. The basis of my implementation follows the Integer Normalization algorithm:
https://stackoverflow.com/q/31121591

The decoder side is simpler, since all transmitted output file symbol frequencies are already normalised to a total power of 2 sum.

Let's assume the total sum (i.e. M) of symbols is 32. We need 5 bits to encode every symbol frequency in the transmitted output file. How could we encode symbols frequencies in less than 5 bits, especially symbols that do not exist (i.e. those with frequency of 0)?? This was so easy with Huffman and canonical codes... Anyway, Internet gave me a hint that one could use e.g. Rice or Rice-Golomb codes. I ended up experimenting with Rice codes with shift value K=2 bits.

So, we always encode K lowest bits of a value and unary encode the quotient after shifting the value K bits to right. Values between 0 to (1<<K)-1 take K+1 bits to encode. In the unary part 0 bit is the end marker. C example how to Rice-code 'value' with some K:

uint32_t r, q;
int total_bits, n = 1;
r = value & ((1 << K) - 1);
q = value >> K;
value = 0;
while (q > 0) {
    value = (value + 1) << 1;
    --q; ++n;
}
value = (value << K) | r;
total_bits = n + K;

Once we have all the symbol frequencies known and a total sum of a power of 2, we can generate tables to help decoding. We only need 2 tables, one table L_ for ANS statex to symbol s mapping and another table `Y` for next ANS state_x after each decoded symbol.

I found this article (https://medium.com/p/d1bebfc7e076/) to be excellent describing how the basic principle of table generation works. The visualisation in that article is just great.

Let's assume we have symbols S={a,b,c,d,e,f,g,h}, and total sum M of symbols is 32. The symbol frequencies are F={2,6,9,0,0,2,6,7}. Next we are going to generate two tables with M entries in both. Note that the alphabet size can be and should be smaller than M, and does not need to be power of 2(!)

The selection of the "spreading function" for tANS table generation seems to be of greater science, however, I picked something very simple i.e. a plain number that allows me to visit every table entry without a collision. Prime numbers work great for that purpose. Let's define our spreading function f(state_x) be (state_x+5) mod M. We also need to pick up the initial starting state i.e. INITIAL_STATE. That is an encoder problem, but a tANS decoder has to know it also when tables are built. I rolled a dice and my INITIAL_STATE became number 3.

One of the key ideas in tANS is to keep the ANS state_x value within a certain range [L..2L), where in our case L==M. If M is 32 then the state_x has to remain between [32..64). When we look up the next state_x from decoding tables, the stored value is always less than L, and we need to input k more bits until state_x is again between [L..2L). Here comes in a nice simplification: why bother with state_x range [L..2L), which it is actually the same as [0..M). It would make decoder and table handling much simpler. So, my decoder keeps the state_x between [0..M) and not [L..2L).

For any symbol s in S with frequency f>0, create n, where f<=n<2f, entries in table Y_[state_x]=n and table L_[state_x]=s.

For each step after entering values into the table update state_x=f(state_x). We do not need a table for needed k input bits for the next state, since we can figure it out runtime.

Figure below shows Y and L tables for symbols in S:

state_x (INITIAL_STATE=3)
|0| | |v| | | | | | | | | | | | |1| | | | | | | | | | | | | | |1
|0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f|0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f
table_Y:                        |
070a06020e080b07030f09090806100a0a0907110b0b0a08020c0c0b09030d0d
table_L:                        |
 h b g a c h b g a c h c g b c h|c g b c h c g b f h c g b f h c
k values for illustration purposes:
 3 2 3 4 3 2 2 3 4 3 2 2 2 3 1 2|2 2 3 1 2 2 2 2 4 2 2 2 2 4 2 2

One possible Z80 implementation to generate tables Y and L is shown below. It is not necessarily the most optimised and compact, but decent one I would say. Tables make use of IX and indexing, which limits the size of one table to 128 implying the M cannot be greater than 128. In many practical use-cases this is enough.

Tables Y and L can be laid out in few ways. When M is max 64 following memory setup is OK:

L_      EQU     M_
Y_      EQU     0
        org     (($+255) & 0xff00)
table_Y:
        ds      M_
table_L:
        ds      M_

When M is 128 following memory layout would work (disclaimer, not tested too much):

L_      EQU     0
Y_      EQU     -M_
        ; Align table_L just below 256 byte boundary
        org     (($+255) & 0xff00)-M_
table_Y:
        ds      M_
table_L:
        ds      M_

Building decoding tables:

; IX = ptr to Y_ and L_ tables, both M_ bytes,
;      so total 2M_ bytes. IX must be aligned to
;      256 bytes boundary.
; A = initial state_x i.e. INITIAL_STATE
; B = number of symbols in our alphabet.
tans_build_decoding_tables:
        ld      de,0x8000
        ; E = s(ymbol), starting from 0
        ; D is actually our bit input buffer,
        ;   but its use is hidden inside the
        ;   EXTRACT_NEXT_SYMBOL_FREQ_TO_A
        ;   macro..
_main_loop:
        push    bc
        push    af
        EXTRACT_NEXT_SYMBOL_FREQ_TO_A
        jr      z,_zero_symbol
        ld      b,a  ; B = f(requency)
        ld      c,a  ; C = f(requency)
        pop     af
_per_symbol_loop:
        push    ix
        push    af
        ; Entry position in tables corresponding
        ; to state_x
        ld      ixl,a
        ; Y_[state_x] = n
        ld      (ix+Y_),c
        inc     c
        ; L_[state_x] = s
        ld      (ix+L_),e
        ; spread step i.e. state_x = f(state_x)
        pop     af
        pop     ix
        add     a,SPREAD_STEP
        ; make sure 0 <= state_x < M
        and     M_-1
        ;
        djnz    _per_symbol_loop
        ; Trick to avoid a jump i.e. CP nn;
        ; POP AF has already been done
        db      $fe
_zero_symbol:
        pop     af
        pop     bc
        inc     e
        djnz    _main_loop
        ret

After we have generated both table Y and table L, the decoder is extremely simple. Since we have no table k for how many bits to input from the compressed data stream to update state_x, we just loop until state_x>=M. The decoder must always input at least 1 bit i.e. implicitly k>=1. One possible Z80 implementation of the tANS decoder looks like the one below. I believe more seasoned Z80 wizards can optimise it even further :)

; Inputs:
;   IX = ptr to Y_ and L_ tables, both M_ bytes,
;        so total 2M_ bytes. IX must be aligned to
;        256 bytes boundary.
;   HL = ptr to end of compressed data. As you
;        know tANS stream is decoded backwards
;   C = input bit buffer
;   A = state_x
; Returns:
;   A = new state_x
;   B = decoded symbol
; Modifies:
;   C and HL
tans_decode_symbol:
        ; Entry position in tables corresponding
        ; to state_x
        ld      ixl,a
        ; get a symbol
        ld      b,(ix+L_)  ; B = symbol
        ld      a,(ix+Y_)  ; A = next state_x
        ; k-tableless adding of bits for the next state
        ; until state_x >= M_
_do_while:
        sla     c
        jr      nz,_not_empty
        dec     hl
        ld      c,(hl)
        rl      c
_not_empty:
        adc     a,a
        cp      M_
        jr      c,_do_while
        ; Scale state between [0..M) or rather [L..2L)
        and     M_-1
        ret

That was pretty simple and compact. If the decoding step is still confusing I recommend simulating tables generation on paper with some small alphabet and M that easily fits your grid paper.