Compression.txt

Addresses are MFOMTU

the FOMT games use a "custom" decompression algorithm. It's a mix of huffman/lz/run-length/diff filtering (like the BIOS functions! except it's all at once and with variations).

HEADER:
    header is first word. Is simple:
        bit 0-7:  unread (seems to always 0x70 ('p'), I guess it's decomp magic number?)
        bit 8-31: size of (uncompressed) data

HOW DATA IS READ:
    The way the thing is read is somewhat complicated. Each word is read in order. Then the *top* part of that word is read for each "chunk" of bits.
    
    For example, let's say we have the following data:
        (hex) 10 FB 15 2D
        (bin) 0001 0000 1111 1011 0001 0101 0010 1101

    Which gets us the following word (read little endian):
        (hex) 2D15FB10
        (bin) 0010 1101 0001 0101 1111 1011 0001 0000
    
    Now let's say the decompressor reads a 4 bit chunk, then a 8 bit chunk, then a 4 bit chunk.
        The first 4 bits are taken from the top of the word:
            (hex) 2
            (bin) 0010
        
        The next 8:
            (hex) D1
            (bin) 1101 0001
        
        The final 4:
            (hex) 5
            (bin) 0101
    
    If we are reading more than we can from a word, just append the next word to it in the stream.

HOW DATA IS WRITTEN:
    I'm simplifying it in this; But it's actually not written byte-by-byte; but rather short-by-short. This is, I assume, to make the decompressor suitable for directly writing to VRAM.

COMPRESSION TYPE:
    the first 8 bit chunk after the header dictates the compression type:
        bit 0-2: pass 1 (compression) identifier
        bit 3-4: huffman tree type
        bit 5-7: pass 2 (diff filtering) identifier

HUFFMAN TREE:
    If huffman tree type identifier is 0 or 3, no huffman tree are used.
    If huffman tree type identifier is 1, then the huffman tree uses 4bit values as leaves
    If huffman tree type identifier is 2, then the huffman tree uses 8bit values as leaves
    
    When reading a huffman encoded byte in the next passes it works this way:
        if huffman tree type 0 or 3, read raw 8bit chunk (no huffman lookup)
        if huffman tree type 1, lookup value for first 4bit chunk, lshift 4, orr to value of next 4bit chunk
        if huffman tree type 2, lookup value for 8bit chunk
    
    If a huffman tree is present, it's the first thing that's read after the header and the compression type byte.
    
    The algorithm for reading the huffman tree is as follows:
        currentNodePath = 0
        for i = 0 to bits*2 do
            currentNodePath = currentNodePath << 1;
            
            repeat read_chunk(bits) times
                node = tree.root
                
                for j = i to 1 step -1 do
                    node = node.child(bit(currentNodePath, j))
                end
                
                node.child(bit(currentNodePath, 0)) = leaf(read_chunk(bits))
                currentNodePath = currentNodePath + 1
            end
        end
    
    I don't really get why they felt the need of specifying the number of nodes to generate per "column" (maybe to define the end of tree data?).
    
    I don't really get why it's bits*2 "columns" either.
    
    I guess I just don't really get huffman ¯\_(ツ)_/¯

PASS 1 - DECOMPRESSION:
    Here's some kind of lz thing happening (except for type 4). Basically, when I'll in the algorithm I say apply_lz(x, y), here's what's happening:
        view = currentOut - argument[0]
        
        repeat argument[1] times
            *currentOut++ = *view++
        end
    
    In other words, argument[0] is the distance from now of the view, and argument[1] is the size of it.
    
    LZ LOOKUP:
        At the start of a pass (except for type 4), a given number of "lz lookup def entries" (idk names) are read. Basically, for each of them is defined the number of bits (-1) that are read when reading lz distances. In addition to that, a distance "offset" is computed for each entry (it's equal to 1 + (sum for each previous entry of (1 << bits)). In other words, based on the distance "magnitude", the number of bits read for that distance differs (and the lz ref lookup defines bits and implies magnitude through the maximum distance that can be defined by that number of bits).
        Table reading algorithm:
            offset = 1
            
            for each ref in lzRef do
                bits = read_chunk(4) + 1
                
                ref.bits   = bits
                ref.offset = offset
                
                offset = offset + (1 << bits)
            end

    If pass 1 type is 0 or 5+:
        read_lz_ref(2) # reads 2 lzRefs (2*4 = 8 bits)
        
        while not at_end() do
            switch i = read_chunk(2) (
                case 0, 1: # regular lz read
                    distance = lzRef[i].distance + read_chunk(lzRef[i].bits)
                    size     = read_chunk(6) + 3
                    
                    apply_lz(distance, size)
                
                case 2: # write raw (maybe huffman-encoded) data
                    count = read_chunk(6) + 1
                    
                    for j = 1, count do
                        *currentOut++ = read_huff_byte()
                    end
                
                case 3: # repeat byte
                    size = read_chunk(6) + 1
                    *currentOut++ = read_chunk(8)
                    apply_lz(1, size)
            )
        end

    If pass 1 type is 1:
        read_lz_ref(4) # reads 4 lzRefs (4*4 = 16 bits)
        
        while not at_end() do
            switch read_chunk(1) (
            
            case 0: # read one byte
                *currentOut++ = read_huff_byte()
            
            case 1: # lz
                i = read_chunk(2)
                distance = lzRef[i].distance + read_chunk(lzRef[i].bits)
                size     = read_chunk(4) + 3
                
                apply_lz(distance, size)

            )
        end
    
    If pass 1 type is 2:
        read_lz_ref(7)
        
        while not at_end() do
            switch read_chunk(1) (
            
            case 0: # read one byte
                *currentOut++ = read_huff_byte()
            
            case 1: # other
                switch i = read_chunk(3) (
                
                case 7: # read large amount of bytes
                    count = 0
                    
                    do
                        read = read_chunk(4)
                        count = (count << 3) | (read >> 1)
                    while (read & 1)
                    
                    switch read_chunk(1) (
                    
                    case 0: # read x bytes
                        repeat count + 1 times
                            *currentOut++ = read_huff_byte()
                        end
                    
                    case 1: # lz apply x bytes
                        j = read_chunk(3)
                        
                        distance = lzRef[j].distance + read_chunk(lzRef[j].bits)
                        size     = read_chunk(4) + (count << 4) + 3
                        
                        apply_lz(distance, size)
                    
                    )
                
                default: # 0-7 # low amount of lz
                    distance = lzRef[i].distance + read_chunk(lzRef[i].bits)
                    size     = read_chunk(4) + 3
                    
                    apply_lz(distance, size)
                
                )
            
            )
        end
    
    If pass 1 type is 3: # this is pretty similar to type 2, but reads in chunks of 2 bytes instead of 1. It doesn't use standard apply_lz for this reason
        read_lr_ref(3) # read 3 refs
        
        while not at_end() do
            switch read_chunk(1) (
            
            case 0: # read short
                *currentOut++ = read_huff_byte()
                *currentOut++ = read_huff_byte()
            
            case 1:
                switch i = read_chunk(2) (
                
                case 3:
                    count = 0
                    
                    do
                        read = read_chunk(3)
                        count = (count << 2) | (read >> 1)
                    while (read & 1)
                    
                    switch read_chunk(1) (
                    
                    case 0:
                        repeat count + 1 times
                            *currentOut++ = read_huff_byte()
                            *currentOut++ = read_huff_byte()
                        end
                    
                    case 1:
                        j = read_chunk(2)
                        
                        distance = 2 * (lzRef[j].distance + read_chunk(lzRef[j].bits))
                        size     = read_chunk(3) + (count << 3) + 2
                        
                        # this is apply_lz, but 2 bytes at a time
                        
                        view = currentOut - distance
                        
                        repeat size times
                            *currentOut++ = *view++
                            *currentOut++ = *view++
                        end
                    
                    )
                
                default:
                    distance = 2 * (lzRef[j].distance + read_chunk(lzRef[j].bits))
                    size     = read_chunk(3) + 2
                    
                    # this is apply_lz, but 2 bytes at a time
                    
                    view = currentOut - distance
                    
                    repeat size times
                        *currentOut++ = *view++
                        *currentOut++ = *view++
                    end
                
                )
            
            )
        end
    
    If pass 1 type is 4: # Data is read directly byte by byte
        while not at_end() do
            *currentOut++ = read_huff_byte()
        end

PASS 2 - DIFF FILTERING:
    okay so here it does some wierd filtering where it just adds each successive values and stores the sum back in. I guess the idea is that for data that is just a series of incremented bytes (01 02 03 04) it's more efficient to compress (because it becomes 01 01 01 01).
    
    Here, both reads & writes are done on the output.
    
    If pass 2 type is 0 or 5+:
        (Nothing is done)
    
    If pass 2 type is 1:
        acc = 0
        
        while not at_end() do
            a, b = read_2_nibbles() -- a is [0-3], b is [4-7]
            
            acc = b = b + acc
            acc = a = a + acc
            
            write_2_nibbles(a, b)
        end
    
    If pass 2 type is 2:
        acc = 0
        
        while not at_end() do
            a, b = read_2_bytes() -- a is [0-7], b is [8-15]
            
            acc = a = a + acc
            acc = b = b + acc
            
            write_2_bytes(a, b)
        end
    
    If pass 2 type is 3:
        acc = 0
        
        while not at_end() do
            a = read_hword()
            acc = a = a + acc
            write_hword(a)
        end
    
    If pass 2 type is 4:
        loAcc = 0
        hiAcc = 0
        
        while not at_end() do
            a, b = read_2_bytes() -- a is [0-7], b is [8-15]
            
            loAcc = a = a + loAcc
            hiAcc = b = b + hiAcc
            
            write_2_bytes(a, b)
        end