Compression

ModKeen mods Tiles and Sprites in all episodes of Commander Keen.
Post Reply
levellass
Posts: 2883
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Compression

Post by levellass » Thu Sep 25, 2008 10:20 am

Modkeen can decompress the Keen graphics, but will not compress them again on import.

I am exceedingly curious as to how these files are compressed; from what I've been able to tinker with, I can affect the sprites file by modifying the latch file, and that can't be right.

It seems to be a form of RLE compression involving copying data that has already been decompressed. (Such as 'copy the byte seven bytes back from here nine times' ) but I can't figure out much more than that.

I am utterly defeated, does anyone know where I may get something about the format (And no, I don't mean the uncompressed graphics format, that was a breeze.)

If you can help, please don't use programming terms, that never works. Levellord was blabbing o about planes and RGB values when I wanted information from her, and it did me no good until I figured it out myself. I am not a smart girl, I need things spelled out as basic as possible.

It's driving me mad.

User avatar
Napalm
Posts: 19
Joined: Sat Oct 27, 2007 6:49 am
Location: UK

Post by Napalm » Sat Sep 27, 2008 2:18 am

If you are talking about the EGAGRAPH/EGAHEAD data then thats compressed using Huffman.
I have code for all of this. What language are you working in?

Napalm

levellass
Posts: 2883
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Post by levellass » Sat Sep 27, 2008 6:19 am

BASIC.

I am talking of course about EGALATCH and c used in Commander Keen 1, Shadow Knights and Dangerous Dave II I guess I should have made that clear at the start.

However, I am still interested in understanding the huffman coding, so if you do have some information on this, I would be interested in receiving it.

User avatar
Napalm
Posts: 19
Joined: Sat Oct 27, 2007 6:49 am
Location: UK

Post by Napalm » Mon Sep 29, 2008 11:50 pm

I spoke to Adurdin and he's uploaded a new version of the UNLZEXE program (which comes with source) to the file dump. So you all might want to get this if you are modding other DOS based games. It can be found here: http://files.keenmodding.org/unlzexe5.zip

Either way, I believe this is what you wanted levellass. Special thanks goes to Adurdin for his work on ModKeen.

Update: Levellass found a problem with regards to calling the LZWDECOMPRESS function multiple times. I've fixed the problem. The source below is now corrected.

QBASIC SOURCE: LZWDECOM.BAS

Code: Select all

DECLARE FUNCTION READBITS% (FILE AS INTEGER, NUMBITS AS INTEGER, BITCLEAR AS INTEGER)
DECLARE SUB LZWDECOMPRESS (INNAME AS STRING, OUTNAME AS STRING)
DECLARE SUB LZWOUTPUT (FILE AS INTEGER, DIC AS INTEGER, CHAR AS INTEGER)
'
' KEEN1 Compatible LZW Decompressor (Lempel-Ziv-Welch)
' - by Napalm with thanks to Adurdin's work on ModKeen
'
' This source is Public Domain
'
'

' Allocate dictionary
DIM LZDIC(0 TO 4095) AS INTEGER
DIM LZCHR(0 TO 4095) AS INTEGER

' Test Function
LZWDECOMPRESS "EGALATCH.CK1", "EGALATCH.DAT"
LZWDECOMPRESS "EGASPRIT.CK1", "EGASPRIT.DAT"



SUB LZWDECOMPRESS (INNAME AS STRING, OUTNAME AS STRING)
        SHARED LZDIC() AS INTEGER, LZCHR() AS INTEGER
        DIM INFILE AS INTEGER, OUTFILE AS INTEGER, I AS INTEGER
        DIM BITLEN AS INTEGER, CURPOS AS INTEGER
        DIM CW AS INTEGER, PW AS INTEGER, C AS INTEGER, P AS INTEGER
        DIM CHECK AS INTEGER

        ' Open files for input and output
        INFILE = FREEFILE
        OPEN INNAME FOR BINARY ACCESS READ AS INFILE
        OUTFILE = FREEFILE
        OPEN OUTNAME FOR BINARY ACCESS WRITE AS OUTFILE
        SEEK INFILE, 7

       
        ' Fill dictionary with starting values
        FOR I = 0 TO 4095
                LZDIC(I) = -1
                IF I < 256 THEN
                        LZCHR(I) = I
                ELSE
                        LZCHR(I) = -1
                END IF
        NEXT I

        ' Decompress input stream to output stream
        BITLEN = 9
        CURPOS = 258
        CW = READBITS(INFILE, BITLEN, 1)
        LZWOUTPUT OUTFILE, LZDIC(CW), LZCHR(CW)
       
        WHILE CW <> &H100 AND CW <> &H101
                PW = CW
                CW = READBITS(INFILE, BITLEN, 0)
                IF CW <> &H100 AND CW <> &H101 THEN
                        P = PW
                        CHECK = (LZCHR(CW) <> -1)
                       
                        IF CHECK THEN
                                TMP = CW
                        ELSE
                                TMP = PW
                        END IF
                        WHILE LZDIC(TMP) <> -1
                                TMP = LZDIC(TMP)
                        WEND
                        C = LZCHR(TMP)
                       
                        IF CHECK THEN
                                LZWOUTPUT OUTFILE, LZDIC(CW), LZCHR(CW)
                        ELSE
                                LZWOUTPUT OUTFILE, P, C
                        END IF
                       
                        IF CURPOS < 4096 THEN
                                LZDIC(CURPOS) = P
                                LZCHR(CURPOS) = C
                                CURPOS = CURPOS + 1
                                IF CURPOS = (2 ^ BITLEN - 1) AND BITLEN < 12 THEN
                                        BITLEN = BITLEN + 1
                                END IF
                        END IF

                END IF
        WEND
       
        ' Close files
        CLOSE OUTFILE
        CLOSE INFILE
END SUB

SUB LZWOUTPUT (FILE AS INTEGER, DIC AS INTEGER, CHAR AS INTEGER)
        SHARED LZDIC() AS INTEGER, LZCHR() AS INTEGER
        DIM LZSTK(0 TO 127) AS STRING * 1
        DIM X AS INTEGER, SP AS INTEGER
        DIM LDIC AS INTEGER, LCHAR AS INTEGER

        LCHAR = CHAR
        LDIC = DIC
        SP = 0
        X = 1

        DO
                IF SP >= 128 THEN
                        PRINT "LZW: Stack Overflow!"
                        END
                END IF
                LZSTK(SP) = CHR$(LCHAR)
                SP = SP + 1
                IF LDIC <> -1 THEN
                        LCHAR = LZCHR(LDIC)
                        LDIC = LZDIC(LDIC)
                ELSE
                        X = 0
                END IF
        LOOP WHILE X
       
        WHILE SP <> 0
                SP = SP - 1
                PUT FILE, , LZSTK(SP)
        WEND
END SUB

FUNCTION READBITS% (FILE AS INTEGER, NUMBITS AS INTEGER, BITCLEAR AS INTEGER)
        STATIC BITDAT AS STRING * 1, BITPOS AS INTEGER
        DIM BITVAL AS INTEGER, BIT AS INTEGER

        IF BITCLEAR THEN
                BITPOS = 0
        END IF

        BITVAL = 0
        FOR BIT = (NUMBITS - 1) TO 0 STEP -1
                IF BITPOS = 0 THEN
                        GET FILE, , BITDAT
                        BITPOS = 7
                ELSE
                        BITPOS = BITPOS - 1
                END IF
                IF ASC(BITDAT) AND 2 ^ BITPOS THEN
                        BITVAL = BITVAL OR 2 ^ BIT
                END IF
        NEXT BIT

        READBITS% = BITVAL
END FUNCTION
Napalm

levellass
Posts: 2883
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Post by levellass » Tue Sep 30, 2008 11:37 am

Wonderful; this works perfectly on Keen code and I shall be seeing what else I can do with it presently.

gerstrong
Posts: 63
Joined: Sun Jan 25, 2009 3:21 pm

Post by gerstrong » Thu Feb 19, 2009 5:33 pm

Does anyone has knowledge about the decompress algorithm of UNP? I would like to integrate it into CKP, so version 1.34 of Keen1 can be launched with it...

Post Reply