-----Oorspronkelijk bericht-----
Van: Gerald Stap <[EMAIL PROTECTED]>
Aan: [EMAIL PROTECTED] <[EMAIL PROTECTED]>
Datum: Wednesday, February 17, 1999 1:13 AM
Onderwerp: dd-graph/age cmp format
>Hi everybody!
>
>Does anyone know the encoding/decoding algorithm for the .cmp format
>used in age?
>I can't figure it out. Does it use run length encoding, huffman, both
>or none of the above? Does it use nybbles, bits, bytes or words?
>Going crazy here....
It uses something that amounts to a vertical run length... It XOR's the
lines onto the previous one, and then compresses the zeroes that result from
this operation iff the bytes were equal. Yes, it is byte-based. But it uses
bits for the compression coding.
The code is pretty straightforward, actually. The only weird trick is that
the code uses a "db 0FEh" as sort of a skip-code. Something like this, I
forgot which code it skipped but I'll assume that it's "push af":
push af ; A on the stack....
...compute stuff
db 0FEh ; use as a "skip code"
loop:
push af
... compute
pop af
... compute
jp loop
The "db 0FEh", followed by "push af" translates into "cp 0F5h" when executed
by the Z80 - this means that only the F register is changed, and the
decruncher uses this to skip the "push af"....
Okay. Back to the algorithm. It has two steps, compressed into a single
loop.
Step 1. Every byte which is not on the first line, is XOR'd with the byte
precisely above it. In practice this means: if a byte in the picture is the
same as the byte above it, it results in a 0 in the buffer.
"code" (picture is SX bytes by SY lines; screen 5 has 128 bytes per line)
rem move the first line
for x=0 to SX-1
buffer(x)=picture(x)
next x
rem move the rest of the picture to the buffer
for y=1 to SY
for x=0 to SX-1
buffer(x+y*SX)=picture(x+(y-1)*128) XOR picture(x+y*128)
next x
next y
Step 2. Now, the next step assumes that there are a lot of zeros in the
buffer. It then uses three streams, which are interleaved (will be cleared
later): two bit streams and a byte stream. Bit stream 1 works like this:
"0": The next 8 bytes in the picture are all zero.
"1": Look at bit stream 2 for more information...
Bit stream 2:
"0": The next byte in the picture is zero.
"1": The next byte in the picture is the next byte in the byte stream.
Take some time to think about this. The byte stream doesn't contain any zero
bytes at all. It contains precisely those picture bytes which aren't zero.
The information is grouped in batches of 64 bytes, and these end up (after
compression) as anything between a single zero byte (only stream 1, all
zeros, so 64 zero bytes in the picture) or 64+9 bytes (if there are no zero
bytes in the batch; 64 bytes of data, 1 byte (0FFh) for bit stream 1, 8
bytes (0FFh) for bit stream 2.).
"Interleaving"
This is a technique used by many compression algorithms. POPCOM uses it too.
The three streams are merged into one in such a way that the next byte in
the stream always provides the information required by the decompressor at
that point.
Darn, I find that this is actually harder to explain than I'd expected.
Maybe this compression method even has a name, but I don't know it.
Erm.. if anyone can explain it better or has some actual questions about it,
just mail me.
Cas "Parallax!" Cremers
[EMAIL PROTECTED]
****
MSX Mailinglist. To unsubscribe, send an email to [EMAIL PROTECTED] and put
in the body (not subject) "unsubscribe msx [EMAIL PROTECTED]" (without the
quotes :-) Problems? contact [EMAIL PROTECTED] (www.stack.nl/~wiebe/mailinglist/)
****
