The goal of this contest is to write a compression routine using the RLE (Run-Length Encoding) algorithm. RLE, a very simple compression technique, saves bytes when 4 or more bytes are identical in a row (known as a "run"). These 4 or more bytes are then replaced by just three bytes:
Byte 1 = $91 (flag that indicates a run)
Byte 2 = Value of the byte that keeps repeating itself.
Byte 3 = Number of bytes that repeat.
Bytes that do not repeat are merely copied. This data:
.db 0,1,2,3,4,4,4,4,4,5,6
Would be replaced by:
.db 0,1,2,3,$91,4,5,5,6
In this case, two bytes would be saved.
There are some special cases that you should be aware of:
1.)"$91" might be present in the data. Because "$91" serves as the run flag, if this byte appears in the data, it must always be treated as a run. ".db $15,$91,$55" would compressed as ".db $15,$91,$91,$01,$55". In this case, $91 serves as both the flag and the byte that "runs" even though the "run" is only one byte long.
2.)A "run" might be larger than 255 bytes. In that case, you have to divide the run into a series of runs (a max run length of 256). For example, ".db $01,$01,$01...(300 times)" would be compressed to ".db $91,1,0,$91,1,44". As you can see, a "run" of 256 bytes is compressed as having a size of "0".
3.)Two-byte runs must not be compressed. If they were to be, the data would actually gain bytes by compression. Three-byte runs represent no change, and therefore whether or not they are to be treated as runs is left up to you.
This decompression routine might be helpful to you. It was originally written by David Phillips (and later optimized with with the help of Clem V. and Aaron Curtis):
;Input:
;HL = Compress From
;DE = Compress To
;BC = Bytes to Decompress
Decompress:
ld a, (hl)
cp $91
jr z, DispRLERun
ldi
DispRLEC:
ret po
jr Decompress
DispRLERun:
inc hl
inc hl
ld a, (hl)
DispRLERunL:
dec hl
dec a
ldi
jr nz, DispRLERunL
inc hl
jr DispRLEC
The INPUT of your compresion routine is 3 16-bit registers. The choice of registers is up to you. One must contain the address of the data. Another must contain the address of the place to store the compressed data. The last 16-bit register must contain the number of bytes to compress are the inputs. The output (other than compressed data) can also be stored in any 16-bit register. The output 16-bit register contains the number of bytes of compressed data. Also note: This contest is fairly open and will accept the use of shadow registers (this includes the inputs/outputs).
Send your entries to Sam by February 24th. Good luck!
|