File formats

Tools, assembly, and file formats.
levellass
Posts: 3001
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

File formats

Post by levellass »

I am adding a small subsection to the patch index that has Commander Keen (And related game's) file formats in it, as a minor resource to other Keeners (And because I am fiercely competitive with CK Guy.) I only have a few up currently, but I hope to have all the file formats up sometime.

The index can be found at: http://levellord.toxicsheep.com/File%20Formats/
User avatar
ckguy
Posts: 465
Joined: Tue Oct 14, 2003 11:20 am
Location: Wakefield, RI, US
Contact:

Post by ckguy »

Kind of beat me to it. :-)

Thanks for these, sorry about the email issues, they were 100% my fault.

I love your angry explanation of the LZW compression. Over the course of my life I've tried several times to implement it in various programming languages, but working at the bit level has always made me angry, too. :D
User avatar
Napalm
Posts: 19
Joined: Sat Oct 27, 2007 6:49 am
Location: UK

Post by Napalm »

Hey levellass,
Nice work. I've noticed a mistake. In the DD2 doc you mentioned this a couple of times.
8 1024 Egadict [Huffman dictionary for decompression, 256x4 byte entries]
This is the Huffman Binary Tree and not a EGA Dictionary. How about a mention? You should also put your name/handle to the files so that if people use them they know who worked on them. I will write up a document on the sound file format for episodes 4-6 of Keen.


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

Post by levellass »

Aaah yes; there are small things I have forgotten (I had to add the image offset for Dave for example.) that i didn't get around to fixing. (It's been a hectic week.)

I shall fix that as soon as I am able, and must chat to you sometime about implementing huffman compression in BASIC, my repeated attempts have not turned out well. ;p
User avatar
Malvineous
Posts: 113
Joined: Sat Mar 13, 2004 12:54 am
Location: Brisbane, Australia
Contact:

Post by Malvineous »

You know, this sort of info would go great on the ModdingWiki ;-)

EDIT: And how come you want Huffman in BASIC anyway? One part of me says you'd be better off putting that time in learning C (which is really quite nice once you get the hang of it) and the other part of me says you could always compile the C code into a library and call it from within your BASIC code - it'd certainly run a lot faster that way.
levellass
Posts: 3001
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Post by levellass »

1.) Anyone who's not willing to sacrifice 1 second for one-time decompression can only complain to me if they don't run windows.

2.)Too late, I figured it out myself.

3.) I now refuse to learn C on principle.
User avatar
Malvineous
Posts: 113
Joined: Sat Mar 13, 2004 12:54 am
Location: Brisbane, Australia
Contact:

Post by Malvineous »

Well if it's only one-time decompression then I guess it's not too bad, but still, I've seen many programs where "only a second" here and there quickly add up to a really sluggish program.

Also don't get me wrong, converting the code to BASIC is a great exercise to learn even more about both languages as well as the Huffman algorithm, as long as you don't mind "reinventing the wheel" to a certain extent ;-)

Oh, and if you don't want to learn C because of the Huffman code, well, it's a great example of how not to write C code. You can write BASIC code that's just as horrible, believe me. There's a reason why C and C++ are the most widely used languages, don't let yourself miss out on that because of a few dodgy coders :-)

Will you be posting your BASIC version of the Huffman algorithm? Can we include it with an example program on the ModdingWiki?
levellass
Posts: 3001
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Post by levellass »

Well I don't see why not. What it does it make a huffman tree that doesn't compress, thus any data relating to it doesn't need to be compressed either. Of course, to decompress the data I need Napalm's subroutine, which is what takes all the time, afterwards of course it's a simple and quick matter of changing the raw data only.

Code: Select all

'___________________________________________________
SUB MAKHUF 'Mak a degenerate huffman tree, store as string huffq
'___________________________________________________
OPEN "HUFF.DD2" FOR BINARY AS #8
aq = "HUFF"
PUT #8, 1, aq
x = 9
FOR t = 0 TO 255
b = t
va = 0
vb = 0
vc = 0
vd = 0
ve = 0
vf = 0
vg = 0
vh = 0
IF b > 127 THEN LET va = va + 1
b = b MOD 128
IF b > 63 THEN LET vb = vb + 1
b = b MOD 64
IF b > 31 THEN LET vc = vc + 1
b = b MOD 32
IF b > 15 THEN LET vd = vd + 1
b = b MOD 16
IF b > 7 THEN LET ve = ve + 1
b = b MOD 8
IF b > 3 THEN LET vf = vf + 1
b = b MOD 4
IF b > 1 THEN LET vg = vg + 1
b = b MOD 2
IF b = 1 THEN LET vh = vh + 1
b = (vh * 128) + (vg * 64) + (vf * 32) + (16 * ve) + (8 * vd) + (4 * vc) + (2 * vb) + va
aq = MKI$(b)
PUT #8, x, aq
x = x + 2
NEXT t
FOR t = 0 TO 253
aq = MKI$(t + 256)
PUT #8, x, aq
x = x + 2
NEXT t
GET #8, 1, huffq
CLOSE #8
KILL "HUFF.DD2"
END SUB

Code: Select all

'
' DANGEROUS DAVE 2 - IN THE HAUNTED MANSION - Huffman Decompressor
'  - by Napalm with thanks to Adurdin's work on ModKeen
'
' This source is Public Domain, please credit me if you use it.
'
'
DECLARE SUB HUFFDECOMPRESS (INNAME AS STRING, OUTNAME AS STRING)
TYPE NODE
        BIT0 AS INTEGER
        BIT1 AS INTEGER
END TYPE

' Test Function
CLS
HUFFDECOMPRESS "TITLE1.DD2", "TITLE1.PIC"

SUB HUFFDECOMPRESS (INNAME AS STRING, OUTNAME AS STRING) ' by Napalm
        DIM INFILE AS INTEGER, OUTFILE AS INTEGER, I AS INTEGER
        DIM SIG AS LONG, OUTLEN AS LONG, BITMASK AS INTEGER
        DIM CURNODE AS INTEGER, NEXTNODE AS INTEGER
        DIM CHRIN AS STRING * 1, CHROUT AS STRING * 1
        DIM NODES(0 TO 254) AS NODE

        ' Open input file
        INFILE = FREEFILE
        OPEN INNAME FOR BINARY ACCESS READ AS INFILE
       
        ' Check file signature
        GET INFILE, , SIG
        IF SIG <> &H46465548 THEN ' Hex for: HUFF in little endian
                PRINT "INVALID FILE!"
                EXIT SUB
        END IF
       
        ' Get output length
        OUTLEN = 0
        GET INFILE, , OUTLEN
       
        ' Read in the huffman binary tree
        FOR I = 0 TO 254
                GET INFILE, , NODES(I).BIT0
                GET INFILE, , NODES(I).BIT1
        NEXT I

        ' Open output file
        OUTFILE = FREEFILE
        OPEN OUTNAME FOR BINARY ACCESS WRITE AS OUTFILE

        ' Decompress input data using binary tree
        CURNODE = 254
        DO
                BITMASK = 0
                GET INFILE, , CHRIN
                DO
                        ' Decide which node to travel down depending on
                        '   input bits from CHRIN.
                        IF ASC(CHRIN) AND 2 ^ BITMASK THEN
                                NEXTNODE = NODES(CURNODE).BIT1
                        ELSE
                                NEXTNODE = NODES(CURNODE).BIT0
                        END IF
                       
                        ' Is this next node another part of the tree or
                        '   is it a end node? Less than 256 mean end node.
                        IF NEXTNODE < 256 THEN
                               
                                ' Get output char from end node and save.
                                CHROUT = CHR$(NEXTNODE AND &HFF)
                                PUT OUTFILE, , CHROUT
                               
                                ' Amend output length and start from top of
                                '   binary tree.
                                OUTLEN = OUTLEN - 1
                                CURNODE = 254

                        ELSE
                                ' Travel to next node
                                CURNODE = (NEXTNODE AND &HFF)

                        END IF

                        ' Move to next input bit
                        BITMASK = BITMASK + 1
                LOOP WHILE BITMASK < 8 AND OUTLEN > 0
                ' Loop while we still need to output data
        LOOP WHILE OUTLEN > 0

        ' Clean up
        CLOSE OUTFILE
        CLOSE INFILE

END SUB
User avatar
Malvineous
Posts: 113
Joined: Sat Mar 13, 2004 12:54 am
Location: Brisbane, Australia
Contact:

Post by Malvineous »

That's excellent, thanks Levellass! And thanks for all the Jazz Jackrabbit info you've added to the ModdingWiki, it's fantastic! (Oh, and in response to one of your summaries "does nobody check this" the answer is mostly no, because we don't know whether we're right or not! Most people - myself included - put stuff up as soon as we think we know what's going on, then correct it as we figure more stuff out. It really helps when people like you come along who actually know how the formats work...)

I have one question though - you added a new section about graphic-planar EGA data. I don't fully understand what you mean by that, as I've never encountered it before. Are you referring to a file that stores multiple planar EGA data files one after the other?

EDIT: I've created a page with your code on it, if you want to add anything to it.
levellass
Posts: 3001
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Post by levellass »

Sort of, yes.

In Dangerous Dave II for example the tile file consists of each individual tile's RGBI planes one after the other, RGBIRGBIRGBI.... this is because each individual tile is loaded separately and so, in essence IS it's own file. The same goes for Dave I, where ALL the graphics are stored in this manner (And with their RGBI order reversed.)

You can check my Keengraph source, it has code for dealing with this.

To me this is just a logical progression; either the whole file may be in planes, or the individual graphics, or the individual pixels. I assumed that Keen 4-6 files would be in a similar format, but do not know as yet.
User avatar
Malvineous
Posts: 113
Joined: Sat Mar 13, 2004 12:54 am
Location: Brisbane, Australia
Contact:

Post by Malvineous »

Ah ok, I see now - graphic-planar is just normal planar images stuck one after the other in a single file. Yes, many games use this for their tile data. If you don't mind I'd like to combine your graphic-planar description with the normal planar data one, because in essence I don't think they're different formats - just different methods of storing the same format in a file.

Thanks for the writeup on the Huffman algorithm too, by the way. Now I finally understand how it works :-)
gerstrong
Posts: 63
Joined: Sun Jan 25, 2009 3:21 pm

ICE Information

Post by gerstrong »

The Ice information in tilemaps of Keen1-3 is missing.

Top ceiling:

if 2 = semiice
if 3 = ice
levellass
Posts: 3001
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Post by levellass »

Indeed, something I noticed whilst uploading it to the modding wiki. This has been corrected, thankyou for noticing.
gerstrong
Posts: 63
Joined: Sun Jan 25, 2009 3:21 pm

Post by gerstrong »

I don't see it corrected. Which Wiki do you mean? Sorry, but I'm looking for a good one in which I find more information about tiles
levellass
Posts: 3001
Joined: Wed Oct 11, 2006 12:03 pm
Location: Ngaruawahia New Zealand

Post by levellass »

You can find all the info *I* know of here: http://www.shikadi.net/moddingwiki/Keen ... nfo_format

I'm planning to upload some more slightly Keen-related stuff too.

Mal: You think graphic planar is bad, Dangerous Dave 1 has every graphic's lines divided into planes, with the planes in reverse order!
Post Reply