Ys III: Wanderers from Ys (Genesis)/Notes

The following article is a Notes Page for Ys III: Wanderers from Ys (Genesis).

Compression

Many data are stored using a LZ-type algorithm. The decompression routine is located in ROM at 0xa7a / 0xa7c.

Specification

• long: size of compressed stream - 1 (not counting this long and the following)
• long: size of uncompressed data
• compressed stream

Description

The compression is a variant of a Lempel-Ziv encoding.

First a circular buffer of 0x1000 bytes is created, filled with:

• 13 bytes 0x00
• 13 bytes 0x01
• and so on up to 13 bytes 0xff
• 256 bytes from 0x00 to 0xff
• 256 bytes from 0xff to 0x00
• 128 bytes 0x00
• 128 bytes 0x20

That sums up to 13*256 + 2*256 + 2*128 = 4096 bytes.

The initial position in this buffer is set to 0xfee.

Then a byte is read from the compressed stream. It's a mask byte. For each bit of this mask byte, from LSB to MSB:

• if the mask bit is 1, then the next byte is read from the compressed stream and output as is ; it's also placed in the circular buffer at the current position (which is then incremented)
• if the mask bit is 0, then a word is read, of the form 0xXYZT. ZXY is a position in the circular buffer, and Z+3 is the number of bytes to copy from the circular buffer to the output. Each byte sent to the output is also copied to the circular at the current position (which is then incremented).

When all 8 bits of the mask byte are treated, another mask byte is read. As sson as the number of output bytes reaches the size of uncompressed data, the algorithm stops (even in the middle of a copy from the circular buffer).

Example of a decompressor

# Buffer is a custom class, used for both source data and decompressed data
# 2 needed methods:
#    * read_b(), read_w(), read_l(): read a byte, a word or a long from the current position in the buffer 
#      (and updates current position)
#    * write_b(): write a byte to the current position in the buffer
#      (and updates current position)
def decompress(buf):
    compressed_size = buf.read_l()
    decompressed_size = buf.read_l()
    
    out = Buffer()
    
    circular_buffer = []
    
    # build circular_buffer with default values
    for j in range(0x100):
        for i in range(13):
            circular_buffer.append(j)
    
    for j in range(0x100):
        circular_buffer.append(j)
    for j in range(0xff, -1, -1):
        circular_buffer.append(j)
    
    for j in range(128):
        circular_buffer.append(0)
    for j in range(128):
        circular_buffer.append(0x20)
    
    # position in circular_buffer
    pos = 0xfee
    
    written_bytes = 0
    
    while written_bytes < decompressed_size:
        # read mask byte
        mask = buf.read_b()

        for i in range(8):
            if bit(mask, i):
                # direct read from source
                val = buf.read_b()
                out.write_b(val)
                written_bytes += 1

                # exit if decompressed size reached
                if written_bytes >= decompressed_size:
                    return out

                # update circular_buffer
                circular_buffer[pos] = val
                pos = (pos + 1) & 0xfff
                
            else:
                # read from circular_buffer
                XYZT = buf.read_w()
                pos_ = (XYZT << 4) & 0xf00 | (XYZT >> 8)  # XYZT -> ZXY
                counter = (XYZT & 0xf) + 3 # T+3

                # copy bytes from circular_buffer
                for _ in range(counter):
                    val = circular_buffer[pos_]
                    out.write_b(val)
                    written_bytes += 1

                    # exit if decompressed_size reached
                    if written_bytes >= decompressed_size:
                        return out

                    # update circular_buffer
                    circular_buffer[pos] = val
                    pos = (pos + 1) & 0xfff

                    # increment copy cursor
                    pos_ = (pos_ + 1) & 0xfff

    return out