ModdingWiki - User contributions [en-gb]

User talk:Levellass

2022-06-20T10:40:42Z

Levellass: /* Odd sprite files in Executioners */

Hi Levellass - not sure if you've seen the question on [[Talk:Softdisk Library Format]] but since you wrote it you're probably best placed to answer! -- [[User:Malvineous|Malvineous]] 02:26, 6 January 2012 (GMT)

Hi Levellass - I reverted your change to [[IMF Format]] (removing [[:Category:File Formats]]) because I am trying to remove all the pages from that category, instead putting them into more specific ones. So in this case [[IMF Format]] will appear in [[:Category:All file formats]] as well as [[:Category:All music formats]]. And these categories should apply automatically when an infobox is added to the article page, so hopefully there will be no need to add categories manually! So if you spot any pages missing categories, please add infoboxes to them instead of just the bare categories. Thanks! -- [[User:Malvineous|Malvineous]] 09:03, 8 March 2013 (GMT)
: Nifty, that should certainly simplify things. -[[User:Levellass|Endian? What are you on about?]]

Hey, LL! Your new example/explanation of Huffman helped a lot in writing a decompressor, but I'm having an issue using it on EGAGRAPH. I verified that it is identical to the EGADICT created by KG and that I am reading it correctly. I get a tree full of reversed bit sequences, just like you said. However, the EGAGRAPH does not appear to use reversed bit sequences; it is completely uncompressed. (It does still have the UInt32LE at the front of the appropriate chunks specifying decompressed length.) Keen can read it and KeenGraph can read it, but using the provided dictionary, I can't. Can you help me? [[User:Fleexy|Fleexy]] ([[User talk:Fleexy|talk]]) 17:32, 3 January 2014 (GMT)

== Titlebuild: black stripe ==

Hey! I used your Keen Dreams title builder, but when I used it in my mod, black stripe appeared at the right corner of the title screen that doesn't and never wanna disappear at all. Fix it please! [[User:Szemigi|Szemigi]] ([[User talk:Szemigi|talk]]) 00:57, 8 September 2021 (GMT)

== Odd sprite files in Executioners ==

I've been digging into the [[Executioners]] stuff you added, and while most sprites decode perfectly fine, I found a few really peculiar entries I can't figure out. The problem are the two files called <tt>GWORDS.VOL</tt> and <tt>RWORDS.VOL</tt>, from inside the <tt>INTRO.VOL</tt> archive.

They seem to be just more RLE-masked sprite files, but when decoding, things start looking... weird. According to their headers, the dimensions of the two files are respectively 218×72 and 162×82 but this gives weird corrupted output. instead, the RLE data, which specifically can't cross line width boundaries, seem to act as if their widths are, respectively, 55 and 41, as can be seen by full-line skip commands that are chopped off at these as maximum length. But when forcing the files to decode with those widths, the output barely looks any less distorted. In fact, the second halves of both files seem to align to widths that are one pixel less than the top halves, without any visible separation between the two blocks.

Do you have any idea what those files are, and how to decode them? -[[User:Nyerguds|Nyerguds]] ([[User talk:Nyerguds|talk]]) 21:39, 29 April 2022 (GMT)
: Hey there. Yeah, some images in the archive have an odd format. They are composed of several smaller images arranged in a grid, but the game samples pixels from each image in sequence to build up the final picture. A good example of this is REAPBIO.VOL, consisting of a 4x4 grid of images with the complete image coming out like 0123456789aABCDEF0123...
: As another note, I have written a utility in BASIC that can extract most of the game's files, including levels. I'm only having trouble with the cinematics since my Dosbox setup cannot display them so I can't test by altering their data. I've been meaning to add more to the executioner's page but if you want my notes on stuff I can put them somewhere. -[[User:Levellass|Endian? What are you on about?]] ([[User talk:Levellass|talk]]) 08:34, 19 June 2022 (GMT)
:: Ah, don't worry too much about the article's formatting; a lot of articles started as pretty bare bones infodumps and only got refined later. That's what the todo tag is for. I've often taken incomplete articles in the wiki, researched the formats, added code for them in [[Engie File Converter|my conversion tool]], and in the process, reformatted and rewritten the articles. Any specific info on how exactly these grid-images work would be welcome.
:: The cinematics seem to play fine for be, btw, but I haven't dug into what files they use. The first cinematic (the bloody TV room) seems to use these odd grid images, though.
:: File extraction is no issue for me; I already implemented that in [[Librarian|my own archive handling tool]]. I haven't encountered anything I can't extract with that. But since I hit that roadblock, I kind of stopped working on it, and haven't gotten around to releasing a new version with that update. -[[User:Nyerguds|Nyerguds]] ([[User talk:Nyerguds|talk]]) 09:45, 19 June 2022 (GMT)
:::Nifty. Well I'll try and get the other file formats up here, some are quite curious. There's a difference between animating images and movies proper, which seem to be able to place sounds, sprites and images onscreen. If you've looked through the level format you'll know how convoluted this game's files can get. I'll try and look into whether the game has any sort of hard coding for those odd images. It's nice to know I won't need to code up an import tool. -[[User:Levellass|Endian? What are you on about?]] ([[User talk:Levellass|talk]]) 10:40, 20 June 2022 (GMT)

User talk:Levellass

2022-06-19T08:34:41Z

Levellass: Wow, should've replied to this message. Executioner's stuff.

Executioners

2022-03-25T23:48:41Z

Levellass: Add sprites

{{NeedMoreInfo}}
{{Game Infobox
| Levels = No
| Tiles = No
| Sprites = No
| Fullscreen = No
| Sound = No
| Music = No
| Text = No
| Story = No
| Interface = No
}}
'''Executioners''' is a DOS game made by Ethan Petty and Icer Addis of Bloodlust Software in 1992. It was their first game, and it sold relatively well at the time. It is notable for its violent content, moderated only by the constraints of the hardware of the time.

{{BeginGameFileList}}
{{GameFile
| Name = BACK*.VOL E.VOL FUCKED.VOL FUCKED2.VOL GUILLBIO.VOL PROD*.VOL REAPBOI.VOL SKETCH.VOL SKETCH2.VOL SKULL.VOL TITLE.VOL
| Format = [[Raw VGA Image]]
| KnownFormat = Yes
| Desc = 320x200 VGA images, no palette data
}}
{{GameFile
| Name = BACKPAL.VOL BIOPAL.VOL DARKPAL.VOL LIGHTPAL.VOL PRODPAL.VOL RUNPAL.VOL SDPAL.VOL SLPAL.VOL TPAL.VOL TVPAL.VOL
| Format = [[VGA Palette]]
| KnownFormat = Yes
| Desc = Game palettes, 'Classic' VGA format
}}
{{GameFile
| Name = BLOOD.VOL BOOM.VOL END*.VOL EXECUTE.VOL FIRE.VOL GR.VOL GUILL*.VOL NEWS*.VOL PLAYERS.VOL RATATATA.VOL REAP*.VOL
| Format = [[Creative Voice File]]
| KnownFormat = Yes
| Desc = Game sounds, old VOC format
}}
{{GameFile
| Name = EXEC.VOL RUN.VOL SOUND.VOL
| Format = [[CMF Format]]
| KnownFormat = Yes
| Desc = Background music
}}
{{GameFile
| Name = FONT.VOL
| Format = [[Executioners Font Format]]
| KnownFormat = Yes
| Desc = Game font
}}
{{GameFile
| Name = EDLAUGH.VOL FLOOR.VOL GF*.VOL GR*.VOL GS*.VOL GSHOCK.VOL GTALK.VOL GWORDS.VOL HBLOOD*.VOL HMOUTH*.VOL JAW.VOL P*.VOL PBALL.VOL PTR.VOL PWORD.VOL RBLINK*.VOL RF*.VOL RR*.VOL RS*.VOL RTALK.VOL RSHOCK.VOL RWORDS.VOL TVD*.VOL TVN*.VOL TVS*.VOL
| Format = [[Executioners RLE Compression]]
| KnownFormat = Yes
| Desc = Individual RLE-compressed images
}}
{{GameFile
| Name = *CHAR.VOL BOSS*.VOL MISC.VOL OBJECT.VOL
| Format = [[Executioners Sprite Format]]
| KnownFormat = Yes
| Desc = Game sprites
}}
{{GameFile
| Name = INTRO.VOL
| Format = [[Executioners Archive Format]]
| KnownFormat = Yes
| Desc = Most, but not all, game files in a simple archive
}}
{{EndGameFileList}}

== Related Links ==

* [https://dosgames.com/game/executioners/] Executioners on DOSGames.com

[[Category:Bloodlust Software]]
[[Category:Sidescroller]]

Executioners Sprite Format

2022-03-25T23:43:24Z

Levellass: Sprite format isn't TOO tricky, the others though. whooo...

{{stub}}
{{Tileset Infobox
| Hardware1 = VGA
| Palette = External
| Names = N
| TileMinSize = 0×0
| TileMaxSize = 255×255
| NumPlanes = 1
| PlaneArrangement = Linear
| HasTransparency = Y
| Metadata = None
| Subtilesets = N
| Compressed = Y
| Hidden = Y
| Games =
{{Game|Executioners}}
}}

Sprites for [[Executioners]] are stored in various files, notable in that they are not kept in the [[Executioners Archive Format|game's main archive.]] Chiefly these are <tt>*CHAR.VOL</tt> Each file contains a single character in the game.

== Signature ==

Sprite files lack a specific signature. However the sprite files start with a <tt>word</tt> that gives the size of the sprite header block. This is equivalent to the number of sprite entries multiplied by 13. The first byte after this will be 0x10 and the fourth 0xFF. (This is the header of an [[Executioners RLE Compression|RLE block.]]) This can be used to identify the file with high accuracy.

== Header ==

Each sprite entry has a nul-terminated 13 byte entry in the file header as follows:

{|class="wikitable"
!Data type!!Description!!Notes
|-
|[[UINT16LE]]||iSize||Size of compressed data block
|-
|[[UINT16LE]]||Frame||Sprite frame image belongs to
|-
|[[UINT16LE]]||L-H-Position||Position of image horizontally, relative to left facing sprite
|-
|[[UINT16LE]]||L-V-Position||Position of image vertically, relative to left facing sprite
|-
|[[UINT16LE]]||R-H-Position||Position of image horizontally, relative to right facing sprite
|-
|[[UINT16LE]]||R-V-Position||Position of image vertically, relative to right facing sprite
|-
|[[char]][1]||END||0x00, terminates entry
|}

Character sprites are divided into independently animating sections such as an upper and lower half, allowing for the full sprite image to have more states. Each 'part' of a sprite occupies its own 'frame' in the level and sprite files cannot share any frames of bugs will occur. What each image 'is' is also hard-coded into the game based on its frame number, limiting how they may be used.

Images also have a horizontal\vertical offset that positions them relative to the sprite 'core' which varies depending on whether the sprite is facing right or left.

== Sprite data ==

Each image is a single [[Executioners RLE Compression|Executioners RLE]] compressed block. The game reads each block sequentially, using the sum of the block sizes given in the header entries to tell where a new block begins.

Executioners

2022-03-25T22:33:35Z

Levellass: Add masked image 'format'

{{NeedMoreInfo}}
{{Game Infobox
| Levels = No
| Tiles = No
| Sprites = No
| Fullscreen = No
| Sound = No
| Music = No
| Text = No
| Story = No
| Interface = No
}}
'''Executioners''' is a DOS game made by Ethan Petty and Icer Addis of Bloodlust Software in 1992. It was their first game, and it sold relatively well at the time. It is notable for its violent content, moderated only by the constraints of the hardware of the time.

{{BeginGameFileList}}
{{GameFile
| Name = BACK*.VOL E.VOL FUCKED.VOL FUCKED2.VOL GUILLBIO.VOL PROD*.VOL REAPBOI.VOL SKETCH.VOL SKETCH2.VOL SKULL.VOL TITLE.VOL
| Format = [[Raw VGA Image]]
| KnownFormat = Yes
| Desc = 320x200 VGA images, no palette data
}}
{{GameFile
| Name = BACKPAL.VOL BIOPAL.VOL DARKPAL.VOL LIGHTPAL.VOL PRODPAL.VOL RUNPAL.VOL SDPAL.VOL SLPAL.VOL TPAL.VOL TVPAL.VOL
| Format = [[VGA Palette]]
| KnownFormat = Yes
| Desc = Game palettes, 'Classic' VGA format
}}
{{GameFile
| Name = BLOOD.VOL BOOM.VOL END*.VOL EXECUTE.VOL FIRE.VOL GR.VOL GUILL*.VOL NEWS*.VOL PLAYERS.VOL RATATATA.VOL REAP*.VOL
| Format = [[Creative Voice File]]
| KnownFormat = Yes
| Desc = Game sounds, old VOC format
}}
{{GameFile
| Name = EXEC.VOL RUN.VOL SOUND.VOL
| Format = [[CMF Format]]
| KnownFormat = Yes
| Desc = Background music
}}
{{GameFile
| Name = FONT.VOL
| Format = [[Executioners Font Format]]
| KnownFormat = Yes
| Desc = Game font
}}
{{GameFile
| Name = EDLAUGH.VOL FLOOR.VOL GF*.VOL GR*.VOL GS*.VOL GSHOCK.VOL GTALK.VOL GWORDS.VOL HBLOOD*.VOL HMOUTH*.VOL JAW.VOL P*.VOL PBALL.VOL PTR.VOL PWORD.VOL RBLINK*.VOL RF*.VOL RR*.VOL RS*.VOL RTALK.VOL RSHOCK.VOL RWORDS.VOL TVD*.VOL TVN*.VOL TVS*.VOL
| Format = [[Executioners RLE Compression]]
| KnownFormat = Yes
| Desc = Individual RLE-compressed images
}}
{{GameFile
| Name = INTRO.VOL
| Format = [[Executioners Archive Format]]
| KnownFormat = Yes
| Desc = Most, but not all, game files in a simple archive
}}
{{EndGameFileList}}

== Related Links ==

* [https://dosgames.com/game/executioners/] Executioners on DOSGames.com

[[Category:Bloodlust Software]]
[[Category:Sidescroller]]

Executioners Archive Format

2022-03-25T22:33:22Z

Levellass: Add note on repeated files

{{Archive Infobox
| MaxFiles = 4095
| FAT = Beginning
| Names = Yes, 8.3
| Metadata = None
| Subdirectories = N
| Compressed = N
| Encrypted = N
| Hidden = Y
| Games =
{{Game|Executioners}}
}}
The '''Executioners Archive Format''' is how most, but not all, files in the game [[Executioners]] is stored. The game will check the archive file first and fall back to the game directory if the desired file could not be found in the archives. This means you can simply rename or remove the archive files to force the game to use external files from the game directory. The default volume file also contains duplicates of some files, (such as <tt>GF1.VOL</tt>) intended to be used at different points in the game. However, since the game scans the file header sequentially, it always stops at the first matching entry, never reading the repeats.

== File format ==

=== Signature ===

There is no known signature for this format. One method to identify files is to check the first <tt>word</tt> of the file and compare it to the <tt>word</tt> at 0x0A. The first value will be a multiple of 16 (the file entries) and the second will be two larger (FAT plus the FAT size <tt>word</tt>). This should give a minimal chance of incorrectly identifing a file.

=== File entry ===

The first section of the file consists of file entries, with the remainder containing the data. Each file entry consists of the filename, its offset and its size. This slightly unusual configuration (storing both the offset and the size) means it is possible (in theory) for two different files to share the same data, and to insert "hidden" data between files.

A file entry is laid out as follows:

{|class="wikitable"
!Data type!!Description
|-
|[[char]] cFilename[8]||Filename (8.3 style, but lacking extension), only NULL-terminated if there is enough room
|-
|[[UINT32LE]] iOffset||File offset from start of group file
|-
|[[UINT32LE]] iSize||File size
|}

File entries in the archive do not store the file extension, which is <tt>.VOL</tt> by default, for all contained files.

=== Implementation Restrictions & Bugs ===

* All file names in the archive must be in upper case

* When searching for a file name, the first match in the FAT is used.

Executioners Font Format

2022-03-25T22:15:04Z

Levellass: Simplify format since some stuff belongs on the RLE page.

Executioners RLE Format

2022-03-25T22:11:39Z

Levellass: Tweak page now I know a bit more

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte
| Games =
{{Game|Executioners}}
}}
[[Executioners]] occasionally uses [[RLE Compression]], or Run Length Encoding, which is explained here. The scheme is used by and large to handle the masking of certain images in-game, rather than to compress the image pixels themselves.

Each 'block' of RLE data begins with a 4-byte header that gives the height and width of the uncompressed image (and thus the block's decompressed size) as well as having two flags identifying it as a block of the right format.

{|class="wikitable"
!Data type!!Description!!Notes
|-
|[[char]][1]||ID||0x10, indicates a valid block
|-
|[[UINT8]]||iwidth||Image width
|-
|[[UINT8]]||iheight||Image height
|-
|[[char]][1]||END||0xFF, ends header
|}

The RLE scheme itself is relatively simple and relies on the data being composed of two kinds of pixels; image pixels which are always read as literals, and unmasked 'empty' pixels which are rows of the same type of pixel. This does, however, mean that no compression can be performed on any non-empty pixels. The scheme can be considered as follows:

1.) While the output data is less than heightXwidth:
2.) Get a byte
3.) Is the value of this byte larger than 127?
-> If no then:
-> Get the next [Value] bytes
-> Move forward [Value] bytes and go to 1
-> If yes, then:
-> Use value 0xFF and copy it [Value - 128] times
-> Move forward a byte and go to 1

Note that it is possible to have zero length runs of both literals and empty pixels, allowing compressed data to be arbitrarily larger than uncompressed data. Image data also tends to be compressed line-by-line; that is, each row of pixels is considered separately and concatenated. This further reduces compression efficiency.

The exact value of the byte used for 'empty pixels' is uncertain, images can contain pixels with value 0xFF and display that color in the palette correctly.

Executioners RLE Format

2022-03-25T14:36:18Z

Levellass: Create page! Good thing Executioners doesn't have much complex coding.

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte
| Games =
{{Game|Executioners}}
}}
[[Executioners]] occasionally uses [[RLE Compression]], or Run Length Encoding, which is explained here.

The RLE routine works from a given location to output a given length of data. However these are not part of the encoding itself and are hard-coded into the game. For example, game font characters get their starting position from the font file header, whereas scrolling images merely start at the fifth byte of the file.

The RLE scheme is relatively simple and relies on the data being composed of two kinds of pixels; image pixels which are always read as literals, and unmasked 'empty' pixels which are rows of the same type of pixel. This does, however, mean that no compression can be performed on any non-empty pixels. The scheme can be considered as follows:

1.) Get a byte
2.) Is the value of this byte larger than 127?
-> If no then:
-> Get the next [Value] bytes
-> Move forward [Value] bytes and go to 1
-> If yes, then:
-> Use value 0xFF and copy it [Value - 128] times
-> Move forward a byte and go to 1

Note that it is possible to have zero length runs of both literals and empty pixels, allowing compressed data to be arbitrarily larger than uncompressed data. A compressed block can also have arbitrary data appended to it that will be loaded into memory as the game gets the size of the compressed block from elsewhere and there is no hard coded end to each block of data.

The exact value of the byte used for 'empty pixels' is uncertain, images can contain pixels with value 0xFF and display that color in the palette correctly.

Executioners Font Format

2022-03-25T14:15:43Z

Levellass: Link

{{Font Infobox
| MaxGlyphs = 256
| GlyphMinSize = 0×0
| GlyphMaxSize = 255×255
| Metadata = None
| Bitmap = Y
| Vector = N
| Compressed = Y
| Hidden = Y
| Games =
{{Game|Executioners}}
}}
[[Executioners]] uses a simple, [[RLE Compression|RLE-compressed]] format t store its game font and also, in a slightly simpler form, scrolling images. An animating image is stored as a single font character, in its own file, without the header found in the game font.

== Header ==

The header of the font file consists of 256 <tt>words</tt> giving the address of each character of the font in the file. Blank characters have an address of 0, while all 'valid' characters should have an address of at least 0x200. This allows the game to display text strings consisting of all 256 ASCII values.

== Character entries ==

Each character address in the header points to a character entry whose format is as follows:

{|class="wikitable"
!Data type!!Description!!Notes
|-
|[[char]][1]||ID||0x10, indicates a valid character
|-
|[[UINT8]]||iwidth||Image width
|-
|[[UINT8]]||iheight||Image height
|-
|[[char]][1]||END||0xFF, ends header
|}

Image data is compressed using the [[Executioners RLE Compression]] format. Because of this, arbitrary data can be stored at the end of each character's compressed data.

== Scrolling images ==

As noted above, scrolling images are formatted as a single character, given its own file. (As such the first character of the file will be 0x10 and the fourth 0xFF). Scrolling images are images that move around the screen in some fashion.

Executioners

2022-03-25T14:13:44Z

Levellass: Add the game font format

{{NeedMoreInfo}}
{{Game Infobox
| Levels = No
| Tiles = No
| Sprites = No
| Fullscreen = No
| Sound = No
| Music = No
| Text = No
| Story = No
| Interface = No
}}
'''Executioners''' is a DOS game made by Ethan Petty and Icer Addis of Bloodlust Software in 1992. It was their first game, and it sold relatively well at the time. It is notable for its violent content, moderated only by the constraints of the hardware of the time.

{{BeginGameFileList}}
{{GameFile
| Name = BACK*.VOL E.VOL FUCKED.VOL FUCKED2.VOL GUILLBIO.VOL PROD*.VOL REAPBOI.VOL SKETCH.VOL SKETCH2.VOL SKULL.VOL TITLE.VOL
| Format = [[Raw VGA Image]]
| KnownFormat = Yes
| Desc = 320x200 VGA images, no palette data
}}
{{GameFile
| Name = BACKPAL.VOL BIOPAL.VOL DARKPAL.VOL LIGHTPAL.VOL PRODPAL.VOL RUNPAL.VOL SDPAL.VOL SLPAL.VOL TPAL.VOL TVPAL.VOL
| Format = [[VGA Palette]]
| KnownFormat = Yes
| Desc = Game palettes, 'Classic' VGA format
}}
{{GameFile
| Name = BLOOD.VOL BOOM.VOL END*.VOL EXECUTE.VOL FIRE.VOL GR.VOL GUILL*.VOL NEWS*.VOL PLAYERS.VOL RATATATA.VOL REAP*.VOL
| Format = [[Creative Voice File]]
| KnownFormat = Yes
| Desc = Game sounds, old VOC format
}}
{{GameFile
| Name = EXEC.VOL RUN.VOL SOUND.VOL
| Format = [[CMF Format]]
| KnownFormat = Yes
| Desc = Background music
}}
{{GameFile
| Name = FONT.VOL
| Format = [[Executioners Font Format]]
| KnownFormat = Yes
| Desc = Game font
}}
{{GameFile
| Name = INTRO.VOL
| Format = [[Executioners Archive Format]]
| KnownFormat = Yes
| Desc = Most, but not all, game files in a simple archive
}}
{{EndGameFileList}}

== Related Links ==

* [https://dosgames.com/game/executioners/] Executioners on DOSGames.com

[[Category:Bloodlust Software]]
[[Category:Sidescroller]]

Executioners Font Format

2022-03-25T14:13:17Z

Levellass: Create page, I should not be staying up so late

{{Font Infobox
| MaxGlyphs = 256
| GlyphMinSize = 0×0
| GlyphMaxSize = 255×255
| Metadata = None
| Bitmap = Y
| Vector = N
| Compressed = Y
| Hidden = Y
| Games =
{{Game|Executioners}}
}}
[[Executioners]] uses a simple, RLE-compressed format t store its game font and also, in a slightly simpler form, scrolling images. An animating image is stored as a single font character, in its own file, without the header found in the game font.

== Header ==

The header of the font file consists of 256 <tt>words</tt> giving the address of each character of the font in the file. Blank characters have an address of 0, while all 'valid' characters should have an address of at least 0x200. This allows the game to display text strings consisting of all 256 ASCII values.

== Character entries ==

Each character address in the header points to a character entry whose format is as follows:

{|class="wikitable"
!Data type!!Description!!Notes
|-
|[[char]][1]||ID||0x10, indicates a valid character
|-
|[[UINT8]]||iwidth||Image width
|-
|[[UINT8]]||iheight||Image height
|-
|[[char]][1]||END||0xFF, ends header
|}

Image data is compressed using the [[Executioners RLE Compression]] format. Because of this, arbitrary data can be stored at the end of each character's compressed data.

== Scrolling images ==

As noted above, scrolling images are formatted as a single character, given its own file. (As such the first character of the file will be 0x10 and the fourth 0xFF). Scrolling images are images that move around the screen in some fashion.

Jazz Jackrabbit Font Format

2022-03-25T13:52:49Z

Levellass: Clarification

{{Font Infobox
| MaxGlyphs = 65,535
| GlyphMinSize = 0×0
| GlyphMaxSize = 16,383×65,535
| Metadata = None
| Bitmap = Y
| Vector = N
| Compressed = N
| Hidden = N
| Games =
{{Game|Jazz Jackrabbit}}
}}
The font files in Jazz Jackrabbit are stored in two slightly different ways; most fonts are 'normal fonts' with one exception, <tt>FONTS.000</tt>. Some font characters are stored in non-font files. (For example the bonus font is stored in <tt>BONUS.000</tt> with the bonus sprites.)

== Normal fonts ==

The standard .0FN files (Fontbig, fontiny, fontmn1, fontmn2 and font2) consist of a 23 byte header ('Digital Dimensions + $1A followed by the h and v spacing between font characters when displayed and two blank bytes.) followed by font characters. Font characters can either contain data, or be placeholders. Placeholders are simply a blank word, and tend to end up in blocks in the font file.

Font characters consist of a character size word (Uncompressed character size + 4) followed by a [[Jazz Jackrabbit RLE compression]] compressed block. (RLE block size word followed by compressed data.)

Uncompressed character data consists of two words, the character width and height, followed by the character pixel data stored in the 'normal' way. Fonts contain no palette, so the color of the font will depend on the level it is in.

== FONTS.000 ==

This font file is similar to the others, but with some slight differences. Its header contains only a word dictating how many font characters are in the file (Default 37), directly followed by the character data. There is no h or v spacing for this font.

Characters are uncompressed and consist of a header of 8 bytes. (Four words; width of character \ 4; height of character; height * width / 4; and a blank word.) followed by the character pixel data.

Character data is stored as four interlaced images. Each image is one quarter of the columns of pixels making up the character. Image 1 is columns 1,5,9... image 2 is 2,6,10... and so on.

== Bonus.000 ==

This contains the bonus level font and sprites. It is not a font file per se but a graphics file.

File:Jazz Jackrabbit Font Format.png

2022-03-25T13:32:21Z

Levellass: Gotta remember how to add categories.

== Summary ==
The extracted FONTBIG.0FN file, via JJ1MOD.

[[Category:Jazz Jackrabbit]]

File:Jazz Jackrabbit Font Format.png

2022-03-25T13:30:54Z

Levellass: The extracted FONTBIG.0FN file, via JJ1MOD. Category:Jazz Jackrabbit

== Summary ==
The extracted FONTBIG.0FN file, via JJ1MOD.

Category:Jazz Jackrabbit

Executioners

2022-03-25T13:14:42Z

Levellass: Add first novel format, the archive!

Executioners Archive Format

2022-03-25T13:13:30Z

Levellass: Create page! First in a while, many more to come

{{Archive Infobox
| MaxFiles = 4095
| FAT = Beginning
| Names = Yes, 8.3
| Metadata = None
| Subdirectories = N
| Compressed = N
| Encrypted = N
| Hidden = Y
| Games =
{{Game|Executioners}}
}}
The '''Executioners Archive Format''' is how most, but not all, files in the game [[Executioners]] is stored. The game will check the archive file first and fall back to the game directory if the desired file could not be found in the archives. This means you can simply rename or remove the archive files to force the game to use external files from the game directory.

== File format ==

=== Signature ===

There is no known signature for this format. One method to identify files is to check the first <tt>word</tt> of the file and compare it to the <tt>word</tt> at 0x0A. The first value will be a multiple of 16 (the file entries) and the second will be two larger (FAT plus the FAT size <tt>word</tt>). This should give a minimal chance of incorrectly identifing a file.

=== File entry ===

The first section of the file consists of file entries, with the remainder containing the data. Each file entry consists of the filename, its offset and its size. This slightly unusual configuration (storing both the offset and the size) means it is possible (in theory) for two different files to share the same data, and to insert "hidden" data between files.

A file entry is laid out as follows:

{|class="wikitable"
!Data type!!Description
|-
|[[char]] cFilename[8]||Filename (8.3 style, but lacking extension), only NULL-terminated if there is enough room
|-
|[[UINT32LE]] iOffset||File offset from start of group file
|-
|[[UINT32LE]] iSize||File size
|}

File entries in the archive do not store the file extension, which is <tt>.VOL</tt> by default, for all contained files.

=== Implementation Restrictions & Bugs ===

* All file names in the archive must be in upper case

* When searching for a file name, the first match in the FAT is used.

Executioners

2022-03-25T12:50:08Z

Levellass: Ooop, should've noted the classic VGA format, adding the game sound format too since it's here

Executioners

2022-03-25T12:36:12Z

Levellass: I'm not dead! Adding familiar file formats in preparation for writing up UNfamiliar ones and coding an editor.

Jazz Jackrabbit

2022-03-25T12:27:00Z

Levellass: Can confirm Fonts.000 is a 0FN type file with minor modifications. I wrote the tool that can edit fonts, it notes this on the format's page.

{{Stub}}
{{Game Infobox
| Levels = Edit
| Tiles = Edit
| Sprites = Edit
| Fullscreen = Edit
| Sound = Edit
| Music = Edit
| Text = No
| Story = No
| Interface = No
}}

== Tools ==

{{BeginFileFormatTools|Type=game}}
{{FileFormatTool
| Name = [http://www.jazz2online.com/downloads/6143/j1e-jazz-jackrabbit1-level-editor-version-12/ J1E]
| Platform = Windows
| grp = N/A
| map = Edit
| gfx = ?
| mus = ?
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [http://www.jazz2online.com/downloads/6040/jj1mod/ JJ1MOD]
| Platform = DOS
| grp = N/A
| map = No
| gfx = Edit
| mus = No
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [http://www.jazz2online.com/jcs94/ JCS'94]
| Platform = Windows
| grp = N/A
| map = Edit
| gfx = ?
| mus = ?
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{EndFileFormatTools}}

{{BeginGameFileList}}
{{GameFile
| Name = bonusmap.*
| Format = [[Jazz Jackrabbit Bonusmap Format]]
| KnownFormat = Yes
| Desc = Bonus levels
}}
{{GameFile
| Name = bonus[xy].000
| Format = [[Jazz Jackrabbit Bonus Format]]
| KnownFormat = Yes
| Desc = Bonus fonts and sprites
}}
{{GameFile
| Name = *.0sc
| Format = [[Jazz Jackrabbit Cutscene Format]]
| KnownFormat = Yes
| Desc = Cutscenes
}}
{{GameFile
| Name = macro.*
| Format = [[Jazz Jackrabbit Demo Format]]
| KnownFormat = Yes
| Desc = Demo macros
}}
{{GameFile
| Name = font*.0fn fonts.000
| Format = [[Jazz Jackrabbit Font Format]]
| KnownFormat = Yes
| Desc = Fonts
}}
{{GameFile
| Name = level?.*
| Format = [[Jazz Jackrabbit Map Format]]
| KnownFormat = Yes
| Desc = Normal levels
}}
{{GameFile
| Name = menu.000
| Format = [[Jazz Jackrabbit Menu Format]]
| KnownFormat = Yes
| Desc = Menu graphics
}}
{{GameFile
| Name = panel.000
| Format = [[Jazz Jackrabbit Panel Format]]
| KnownFormat = Yes
| Desc = In-level game panel
}}
{{GameFile
| Name = planet.*
| Format = [[Jazz Jackrabbit Planet Format]]
| KnownFormat = Yes
| Desc = Planet images
}}
{{GameFile
| Name = save.*
| Format = [[Jazz Jackrabbit Saved Game Format]]
| KnownFormat = Yes
| Desc = Saved games
}}
{{GameFile
| Name = hiscore
| Format = [[Jazz Jackrabbit Score Format]]
| KnownFormat = Yes
| Desc = High scores
}}
{{GameFile
| Name = sounds.*
| Format = [[Jazz Jackrabbit Sound Format]]
| KnownFormat = Yes
| Desc = Sound effects
}}
{{GameFile
| Name = sprites.* mainchar.000
| Format = [[Jazz Jackrabbit Sprite Format]]
| KnownFormat = Yes
| Desc = Sprites
}}
{{GameFile
| Name = blockx.* bonus?.000
| Format = [[Jazz Jackrabbit Tile Format]]
| KnownFormat = Yes
| Desc = Level tiles and bonus tiles, respectively
}}
{{GameFile
| Name = *.psm
| Format = [[ProTracker Studio Module]]
| KnownFormat = Yes
| Desc = Background music
}}
{{EndGameFileList}}

Most files are compressed with [[Jazz Jackrabbit RLE compression]].

==External links==
* [http://www.alister.eu/jazz/oj/ OpenJazz] might provide insight in the various file formats though it is working with flawed information

[[Category:Epic Megagames]]
[[Category:Renaissance]]
[[Category:Sidescroller]]

Executioners

2021-04-24T04:30:13Z

Levellass: Create page, should add more data and formats as I figure them out

CMF Format

2021-04-24T04:19:27Z

Levellass: Add Executioners, which uses this format in music. (Hopefully more will be added on that game soon.)

{{Music Infobox
| Type = MIDI
| Instruments = OPL
| NumChannels = 16
| NumTracks = 1
| NumPatterns = 1
| NumOrders = 0
| Tags = Title, Artist, Remarks
| Games =
{{Game|Jill of the Jungle}}
{{Game|Kiloblaster}}
{{Game|Scud Atak}}
{{Game|Solar Winds}}
{{Game|Traffic Department 2192}}
{{Game|Math Rescue}}
{{Game|Word Rescue}}
{{Game|Xargon}}
{{Game|King Arthur's K.O.R.T.}}
{{Game|Executioners}}
}}
The Creative Music Format (CMF) was created by Creative Labs for use with their SoundBlaster series of sound cards. It is a cut-down version of the [[MID Format|MIDI format]] (only one track) but unlike MIDI it allows custom instruments to be stored in the file itself (and unlike the Module formats that preceded it, the instruments were not sampled but were synthesised using the Adlib/SoundBlaster OPL chips.)

== File format ==

The file begins with a header:

{|class="wikitable"
!Data type!!Name!!Description
|-
|BYTE[4]||cSignature||"CTMF" (not NULL-terminated)
|-
|UINT8||iVersionMinor||Minor version number (normally 0x01)
|-
|UINT8||iVersionMajor||Major version number (normally 0x01)
|-
|UINT16LE||iOffsetInstruments||Offset of the instrument block, from the start of the file
|-
|UINT16LE||iOffsetMusic||Offset of the music block, from the start of the file
|-
|UINT16LE||iTicksPerQuarter||Clock ticks per quarter note (one beat)
|-
|UINT16LE||iTicksPerSecond||Clock ticks per second
|-
|UINT16LE||iOffsetTitle||Offset of the song title string, zero if no title
|-
|UINT16LE||iOffsetComposer||Offset of the composer's name, zero if not listed
|-
|UINT16LE||iOffsetRemarks||Offset of the "remarks" string, zero if no remarks
|-
|UINT8[16]||iChannelInUse||Channel in use table (0x00 == channel not used, 0x01 == channel used in song)
|}

The rest of the header depends on the version:

==== Version 1.0 ====
{|class="wikitable"
!Data type!!Name!!Description
|-
|UINT8||iInstrumentCount||Number of instruments used
|}

==== Version 1.1 ====
{|class="wikitable"
!Data type!!Name!!Description
|-
|UINT16LE||iInstrumentCount||Number of instruments used
|-
|UINT16LE||iTempo||Basic tempo (BPM?)
|}

The song title, composer and remarks (if present) should follow this header and the instrument block should follow that (although there is no requirement for them to be located here, as long as the offsets in the header point to the correct location.) These three strings are NULL-terminated ASCII.

It is worth noting that the header stores both a tempo value and a "ticks per quarter note" value, however the only field that seems to be used for timing during playback is the "ticks per second" field. The tempo field doesn't even exist in version 1.0 files. It is assumed "basic tempo" means BPM (beats per minute) as this is the meaning of the "basic tempo" field in the earlier [[AdLib MIDI Format]].

It is also worth noting that between v1.0 and v1.1, the number of possible instruments expanded from a maximum of 256 (UINT8) to 65536 (UINT16.) However the MIDI data itself is only capable of addressing up to 128 instruments, so any extras cannot be used. Perhaps there was originally an intention to make these available through instrument banks like MIDI does.

Be aware that the title/composer/remarks fields are supposed to be zero if there is no metadata, but [[Highway Hunter]] sets them to invalid values (past EOF), so you may wish to check that these fields are within range and ignore them otherwise.

=== Instrument block ===

The instrument block contains all the instruments used in the song. The first instrument is referred to in the song data as instrument zero (MIDI patch #0.) The following table lists the fields used to define one instrument - it is repeated ''iInstrumentCount'' times.

{|class="wikitable"
!Data type!!Name!!OPL base register!!Description
|-
|UINT8||iModChar||0x20||Modulator characteristic (Mult, KSR, EG, VIB and AM flags)
|-
|UINT8||iCarChar||0x23||Carrier characteristic (Mult, KSR, EG, VIB and AM flags)
|-
|UINT8||iModScale||0x40||Modulator key scaling/output level
|-
|UINT8||iCarScale||0x43||Carrier key scaling/output level
|-
|UINT8||iModAttack||0x60||Modulator attack/decay level
|-
|UINT8||iCarAttack||0x63||Carrier attack/decay level
|-
|UINT8||iModSustain||0x80||Modulator sustain/release level
|-
|UINT8||iCarSustain||0x83||Carrier sustain/release level
|-
|UINT8||iModWaveSel||0xE0||Modulator wave select
|-
|UINT8||iCarWaveSel||0xE3||Carrier wave select
|-
|UINT8||iFeedback||0xC0||Feedback/connection
|-
|BYTE[5]
|colspan=3|Padding to bring instrument definition up to 16 bytes
|}

There are 16 default instruments, repeated into the 128 available MIDI instruments (so instrument 0, 16, 32, etc. all refer to this first default instrument. See [[#Default instruments]] below) The instrument block then overrides these defaults. [[Word Rescue]] is notable for having CMFs that rely on these default instruments being present and correct.

==== Percussive instruments ====
Since each CMF instrument contains both OPL modulator and OPL carrier settings, when an instrument is selected in a CMF file, both the modulator and carrier settings are loaded into the OPL chip for that channel.

When the CMF is in percussive mode however (see [[#Controller 0x67: Rhythm mode]] below), most of the percussive instruments only occupy either a modulator or a carrier (i.e. half an instrument.) This means that loading these instruments must be treated slightly differently, as a whole instrument is supplied but only half of it will be loaded into the OPL chip, and not necessarily the expected half.

When percussive mode is active and an instrument change event (MIDI event 0xC0) is received on a percussive channel (12-16 inclusive), the instruments should be loaded as follows:

{|class="wikitable"
!CMF channel!!Instrument!!Instrument source!!OPL cell
|-
|<center>12</center>||Bass drum||Modulator Carrier||13 - Channel 7 Modulator 16 - Channel 7 Carrier
|-
|<center>13</center>||Snare drum||Modulator||17 - Channel 8 Carrier
|-
|<center>14</center>||Tom tom||Modulator||15 - Channel 9 Modulator
|-
|<center>15</center>||Top cymbal||Modulator||18 - Channel 9 Carrier
|-
|<center>16</center>||Hi-hat||Modulator||14 - Channel 8 Modulator
|}

Despite some documentation suggesting that certain instruments cannot have their pitch set, the Creative Labs SBFMDRV will play all percussive instruments at the requested pitch. Note however that as only one pitch can be set per channel, playing both a snare and hi-hat, or both a tom tom and top cymbal, at the same time, will cause a conflict, potentially changing the pitch of an already-playing note. The Creative Labs SBFMDRV simply writes the pitch as each note is played, changing the pitch of any currently playing note on the shared channel.

Be aware that some songs (e.g. [[Kiloblaster]]'s <tt>song_2</tt>) play two different percussive instruments simultaneously, when those two instruments share the same OPL channel (e.g. hi-hat and snare drum.) The notes are actually played at different pitches, which introduces a conflict, as only one note frequency is available for the channel and it must be shared by both instruments. In this case the order of events is important, as the pitch of the last event at that instant is the one that gets set for the channel. Normally with MIDI, if notes are played at the same instant in time it does not matter which order they are issued in, however in this case the song is quite different if the order is not maintained.

Essentially SBFMDRV writes the pitch to the OPL channel as the events are encountered, so whichever note is played last is the frequency the channel will be set to.

=== Song data ===

The song data itself is in standard MIDI format - identical to the ''data'' stored in a MIDI MTrk block (but without the "MTrk" header of course.) For details on this, see the [[MID Format#MIDI data|MIDI data description]].

One difference worth noting is that the official Creative Labs CMF player does not support pitch bends (code 0xE0) and those events are simply ignored. Simple sysex data appears to be ignored also, however its use in a CMF file can cause problems with other players.

==== MIDI controllers ====

In addition to the standard MIDI controllers (which are actually rarely used in CMF files), the following controllers have special meaning in a CMF file. Each controller has one data byte (the "controller value", 0-127), and the meaning of this byte will of course depend on which controller was selected.

{|class="wikitable"
!Controller!!Purpose
|-
|0x63||Non-standard extension: AM+VIB depth control (see below)
|-
|0x66||Set marker byte (used as a status flag readable by a music player)
|-
|0x67||Switch OPL between melody and rhythm mode (see below)
|-
|0x68||Transpose up by given number of 1/128 semitones
|-
|0x69||Transpose down by given number of 1/128 semitones
|}

===== Controller 0x63: Depth control =====
MIDI controller 0x63 is a nonstandard extension to allow the OPL's AM+VIB depth control to be adjusted (normal CMF playback has both the AM and VIB depth control fixed in the on state.) When this controller is set to zero, the depth control is switched off (i.e. amplitude depth is 1 dB, vibrato depth is 7 cents.) Setting the controller to a value of one increases the vibrato to a depth of 14 cents (OPL port 0xBD has bit 6 set), and setting the control to a value of two increases the amplitude depth to 4.8 dB (OPL port 0xBD has bit 7 set). Setting the control to a value of three increases both depth controllers, which is the CMF default setting (OPL port 0xBD has bits 6 and 7 set.)

Since this setting is global and affects the entire OPL chip, it does not matter which channel the controller change is issued on.

===== Controller 0x66: Song markers =====
Controller 0x66 is used to set a marker byte in the song. This can be used to notify the music player that a certain point in a song has been reached, or to trigger some kind of action in time with the music.

===== Controller 0x67: Rhythm mode =====
MIDI controller 0x67 is used to switch between "melody mode" and OPL "rhythm mode." In melody mode, nine-channel FM music is possible. In rhythm-mode, six-channel FM music is possible, with an additional five channels used for percussion (allowing 11 sounds to be played simultaneously.) In this mode, the last five MIDI channels are reserved for the percussive instruments as shown below.

Since this setting is global and affects the entire OPL chip, it does not matter which channel the controller change is issued on.

{|class="wikitable"
!Hex channel!!MIDI channel!!Use in melody mode!!Use in rhythm mode
|-
|0x00||1||Normal instrument||Normal instrument
|-
|0x01||2||Normal instrument||Normal instrument
|-
|0x02||3||Normal instrument||Normal instrument
|-
|0x03||4||Normal instrument||Normal instrument
|-
|0x04||5||Normal instrument||Normal instrument
|-
|0x05||6||Normal instrument||Normal instrument
|-
|0x06||7||Normal instrument||Normal instrument
|-
|0x07||8||Normal instrument||Normal instrument
|-
|0x08||9||Normal instrument||Normal instrument
|-
|0x09||10||Normal instrument||Normal instrument
|-
|0x0A||11||Normal instrument||Normal instrument
|-
|0x0B||12||Normal instrument||Bass drum
|-
|0x0C||13||Normal instrument||Snare drum
|-
|0x0D||14||Normal instrument||Tom-tom
|-
|0x0E||15||Normal instrument||Top cymbal
|-
|0x0F||16||Normal instrument||Hi-hat cymbal
|}

See [[#CMF/MIDI vs Adlib channels]] below for more details.

===== Controller 0x68: Transpose up =====
This controller transposes all following notes on the channel up by the given number of 1/128 semitones. Since the controller value must be between 0 and 127, it will allow a song to be transposed up anywhere between zero and almost a full semitone. The value is absolute, so a controller requesting a transpose up by 127 followed by a transpose up by 64, will initially be transposed up by almost a full semitone (127) but will then be transposed back by a half semitone (to 64).

A value of zero resets back to "not transposed."

===== Controller 0x69: Transpose down =====
Identical to controller 0x68 (Transpose up) only of course in the opposite direction, and again only affecting the channel the controller is issued on.

=== Notes ===

==== Keyon/off handling ====
Some songs don't always send keyoffs after a keyon, or they send them out of order (e.g. note 1 on, delay, note 2 on, note 1 off, delay, note 2 off.) If you don't check this you'll end up switching a note off too early (in the above example the "note 1 off" should *not* switch off "note 2" that was switched on just before it.) <tt>song_9.xr1</tt> from the first episode of Xargon is an excellent example of this, right at the start of the song.

The best way of handling this when playing through an OPL chip seems to be to remember the last note played on a channel, and upon receiving a keyoff, only process it if the keyoff is for the note currently playing on the channel (otherwise it can be discarded.) If a keyon is received and a note is already being played on a channel, the old note should be switched off just before playing the new note.

==== Keyon/off timing ====
Some songs play a note-on, then immediately (with no delay) have a corresponding note-off. If this is played faithfully, then the note will not be heard, however the Creative Labs player still plays these notes. The correct solution is {{TODO|currently unknown - wait for one tick or use the emulator callback between events?}}. A good example of this is the first few notes in <tt>song_32.xr1</tt>. ([https://github.com/adplug/adplug/issues/41 Discussion])

==== Default instruments ====
Although no documentation exists about this, it seems that the Creative Labs player sets the 128 available instruments based on 16 defaults looped/repeated to fill the 128 slots. They do not appear to be based on any MIDI instrument specification. Any instruments included in the CMF file then override these defaults. Some songs (e.g. the [[Word Rescue]] background music) rely on these default instruments and don't play properly if only their custom instruments are set.

There appear to be a different set of default instruments used for the percussion channels when rhythm mode is active. More investigation needs to be done to determine what these are and if they are related to the 16 default melody instruments.

{{TODO|Post a set of OPL settings here (perhaps in [[IBK Format]]) that provides these default parameters.}}

{{TODO|Confirm whether it's possible to set more than 16 custom instruments, without them looping and overwriting the earlier ones.}}

==== CMF/MIDI vs Adlib channels ====
MIDI (and consequently CMF) supports up to 16 channels. The OPL2 synth on the Adlib only supports a maximum of nine channels in normal mode, or six channels plus five percussion instruments in rhythm mode.

This means that any CMF player must correctly map up to 16 MIDI channels to only nine OPL channels. Many songs from games work correctly with a 1:1 mapping (i.e. the game music doesn't go beyond MIDI channel 9), however there are some songs that use channels beyond this (e.g. [[Word Rescue]] again, which, given the Voyetra credit, has probably been minimally converted from MIDI.)

At the time of writing, there are no known songs that use more than nine MIDI channels simultaneously, however [[Word Rescue]]'s E1L1 song appears to sound more than nine notes simultaneously across a smaller number of channels, so if all these notes should be heard, the extended OPL3 channels probably need to be used. [[Xargon]] <tt>song9</tt> also sounds multiple notes simultaneously in a single channel. Either of these will result in lost notes unless the available channels are cleverly managed.

As an aside, it would be interesting to test this with Creative's driver to see how it behaves.

==== Note velocity ====
The velocity values are loaded more or less directly into the OPL chip. This means unlike MIDI, the velocity is not a linear scale from 0 to 127, but logarithmic. A value of 1 is almost silent, and rapidly increase in volume so that values 2 and 3 are much louder. At the other end of the scale, 127 is full volume, but 126 and 125 are barely any quieter.

==== Format violations ====

These format violations may require special consideration in order for a player to correctly handle these files.

* <tt>dan.cmf</tt> from [[Jill of the Jungle]] should end with bytes <tt>FF 2F 00</tt> (the <tt>00</tt> indicating no data bytes for the <tt>2F</tt> 'end of song' event) but it instead ends with <tt>FF 2F FE</tt>, with <tt>FE</tt> being an invalid (truncated) MIDI number.

* [[Highway Hunter]] CMF files contain invalid offsets for the metadata fields, as they point past the end of the file.

== Tools ==
{{BeginFileFormatTools|Type=audio}}
{{FileFormatTool
| Name = [http://www.hitsquad.com/smm/programs/cmf2mid/ CMF2MID]
| Platform = DOS
| canPlay = No
| canCreate = No
| canModify = No
| canExport = Yes; .mid
| canImport = Yes; [[CMF Format|.cmf]]
| editHidden = No
| editMetadata = No
| notes = Convert CMF files into MIDI
}}
{{FileFormatTool
| Name = [http://adplug.sourceforge.net AdPlug/AdPlay]
| Platform = DOS, Linux, Windows
| canPlay = Yes
| canCreate = No
| canModify = No
| canExport = No
| canImport = No
| editHidden = No
| editMetadata = No
| notes = Plugins for various audio players (plus a command line player) that mostly supports CMF files
}}
{{FileFormatTool
| Name = [http://www.shikadi.net/utils/xmms.html Malvineous' Adlib plugin]
| Platform = Linux
| canPlay = Yes
| canCreate = No
| canModify = No
| canExport = No
| canImport = No
| editHidden = No
| editMetadata = No
| notes = Plugin for XMMS and Audacious that plays most CMF files more accurately than AdPlug
}}
{{FileFormatTool
| Name = [[OPL3 Bank Editor]]
| Platform = Linux, Windows, macOS
| canPlay = No
| canCreate = No
| canModify = No
| canExport = Yes; many
| canImport = No
| editHidden = No
| editMetadata = No
| notes = Import instruments from CMF files to use them in banks
}}
{{EndFileFormatTools}}

== Similar formats ==
* The CMF song data is stored in the same format as used by [[MID Format|MIDI files]]
* The [[SBI Format]] (SoundBlaster Instrument) is the same as used in the CMF instrument block, with a header on the front.
* The [[IBK Format]] (Instrument Bank) is a group of SBI instruments, similar to the whole CMF instrument block.

All Dogs Archive Format

2020-06-12T13:40:30Z

Levellass: Create this apge, I think that's all the formats in this game!

{{Tileset Infobox
| Hardware1 = CGA
| Hardware2 = EGA
| Hardware3 = TGA
| Palette = External
| Names = N
| TileMinSize = 0×0
| TileMaxSize = 8,191×65,535
| NumPlanes = 1
| HasTransparency = N
| Metadata = Yes
| Subtilesets = N
| Compressed = N
| Hidden = N
| Games =
{{Game|All Dogs Go To Heaven}}
}}

The Polarware game [[All Dogs Go To Heaven]] stores its graphics in two sets of seven archive files with the names <tt>MRH_DOG?.DB?</tt>. There are two sets of graphics, one for the [[Raw CGA data|CGA]] version of the game and the other for the [[Raw EGA data|EGA]] and TGA versions. Both sets of archive use the same format to store the graphics (and text) chunks used by the game.

Each file is divided into two sections, a header giving the location, size and decompressed size of graphics chunks, and the chunks themselves. Chunks may or may not be compressed; the game decides this by checking to see if the decompressed data size is the same as that of the actual chunk size. All text chunks are uncompressed but only a few graphics chunks are as well. The chunks that are compressed are done so using [[All Dogs RLE compression]] which is very inefficient.

The graphics data is either CGA or EGA (With the TGA graphics being based on the EGA data) in linear (rather than planar) format. As such the raw data can simply be given a bitmap header to convert it into a 2bpp or 4bpp image.

== Format ==

Number of images:
0 2 NumImages The total number of images in the file. The header's total size will be this
multiplied by 8 plus 2 bytes long.
List:
0 2 DeCmpSize Size of the chunk when decompressed, in bytes.
2 2 CmpSize Size of the chunk in the file.
12 4 DataStart Where in the file the chunk starts

== Notes ==

Each graphic chunk contains six bytes giving the graphic width (in data bytes, not pixels), height and total size when decompressed (again in bytes).

Some chunks have a corresponding 'mask' chunk used by the game to give the graphic some transparency. This is a black and white image. Other chunks simply set black as the transparent color.

Some (but far from all) of the game's text is stored as 32-byte chunks. Specifically the strings used in the 'hangman' type minigame. These chunks are always uncompressed and nul-padded. They also lack the size size bytes at the start.

The first four bytes of a chunk are not compressed but the next two are, despite bytes 5&6 being metadata (The image size) rather than graphics data.

File:Raw CGA Data.png

2020-06-12T13:17:42Z

Levellass: The CGA titlescreen of All Dogs Go To Heaven showing the four color palette.

The CGA titlescreen of [[All Dogs Go To Heaven]] showing the four color palette.

File:All Dogs Go To Heaven.png

2020-06-12T13:15:37Z

Levellass: Box cover for the Amiga version of All Dogs Go To Heaven.

Box cover for the Amiga version of [[All Dogs Go To Heaven]].

Category:All Dogs Go To Heaven

2020-06-12T13:12:49Z

Levellass: Well this needs blueshifting.

LPCM format

2020-06-12T13:10:21Z

Levellass: Create page, it's a basic format but a surprisingly commonly used one, even way back when.

{{Sound Infobox
| Type = PCM
| NumChannels = 1
| BitsPerSample = 8
| Compressed = N
| Tags = Name
| Games =
{{Game|All Dogs Go To Heaven}}
{{Game|Jazz Jackrabbit}}
}}

Linear pulse-code modulation (LPCM) is a specific type of PCM (pulse-code modulation) where the quantization levels are linearly uniform. This is in contrast to PCM encodings where quantization levels vary as a function of amplitude. Though PCM is a more general term, it is often used to describe data encoded as LPCM. It is the standard form of digital audio in computers, compact discs, digital telephony and other digital audio applications. In a PCM stream, the amplitude of the analog signal is sampled regularly at uniform intervals, and each sample is quantized to the nearest value within a range of digital steps.

A PCM stream has two basic properties that determine the stream's fidelity to the original analog signal: the sampling rate, which is the number of times per second that samples are taken; and the bit depth, which determines the number of possible digital values that can be used to represent each sample.

In short such data consists of an uncompressed steam of data where a certain number of bytes represents a piece of a soundwave. Playing a specific amplitude for each 'tick' of time will reproduce the sound to varying levels of fidelity depending on how often the sound was sampled. It is a highly inefficient way to store audio data as even very poor quality audio must be sampled several thousand times per second.

In most early games using this format the sampling rate is either very low, around a tenth of a standard wave file, ([[All Dogs Go To Heaven]]) or the game 'smoothed' or altered the data to improve quality ([[Jazz Jackrabbit]]). The stream is read as mono (rather than stereo) with 16 bits per sample. This makes the format exceedingly simple, lacking any organization or compression of any kind aside from the raw sound data.

All Dogs RLE Compression

2020-06-12T13:09:20Z

Levellass: Fix that template!

{{Compression Infobox
| Type = Stream
| UnitSize = 1-bit
| Games =
{{Game|All Dogs Go To Heaven}}
}}

[[All Dogs Go To Heaven]] uses [[RLE Compression]] to compress graphics chunks in its [[All Dogs Archive format|graphics archives.]] This is one of many possible ways to create a functional RLE system.

The compressed file consists of an UINT32LE giving the number of bytes (not pixels) in each row of the graphics chunk, an UINT32LE giving the number of rows in the graphic, and the compressed data. The first UINT32LE of the compressed data, which is almost always uncompressed, gives the size of the uncompressed data. As a check the decompressed size value should be equal to the width and height values multiplied.

The data can be either [[Raw CGA Data|CGA]] or [[Raw EGA data|EGA]] data which are four or two pixels of data per byte respectively.

The compressed data is processed in a loop. After each byte is read, its value is used to select an action. If the byte has a value of 27 (val & 0x1B) then the next word gives the number of identical bytes to output and the byte after that is the byte to repeat. All other bytes are passed through unchanged. The next byte is then read and the same procedure followed until there is no more data or the decompressed size has been reached. (This will be obtained elsewhere in the graphics archive even though it is also part of the graphics chunk.)

It should be noted that the repeat length words are big-endian, unlike all others in the game.

As a result of this inefficient scheme it is possible to 'compress' data in this format by simply replacing and 0x1B bytes with the sequence 1B 00 01 1B.

An illustration:

12 34 1B 00 03 56 78 90

This data is interpreted as follows:

12 34 # Copy 12 and 34 through unchanged
1B 00 03 56 # Repeat 56 three times
81 78 90 # Copy 78 and 90 through unchanged

Or as pseudocode:

* If [Decompressed data length] < [Final length] then:
*# Read a byte [Value]
*# If the byte value = 27, then:
*#* Move forward a byte
*#* Read the next two bytes
*#* Store this big-endian value as [length]
*#* Move forward two bytes
*#* Read the next byte
*#* Repeat the byte [length] thimes
*#* Move forward a byte and return to step 1.
*# Else:
*#* Read the next byte and output it unchanged
*#* Move forward a byte and return to step 1.

It can be seen that this system is very far from optimal since two, three and even four repeating bytes must be treated as non-repeating.

All Dogs Go To Heaven

2020-06-12T12:54:57Z

Levellass: Change format link

{{Stub}}
{{Game Infobox
| Title = All_Dogs_Title.png
| Levels = None
| Tiles = None
| Sprites = Not editable
| Fullscreen = Not editable
| Sound = None
| Music = Not editable
| Text = Not editable
| Story = Not editable
| Interface = Not editable
}}

'''All Dogs Go To Heaven''' is a 1989 video game for DOS and Amiga. It is based on the 1989 film of the same name and features ten minigames loosely tied together to form a story mode. The MS-DOS version is known for having surprisingly loud 'music' that plays at unexpected time.

The MS-DOS version also contains three executables and two sets of graphics files, for CGA, EGA,and TGA display respectively, with the TGA graphics being sourced from the EGA files.

== Tools ==

{{BeginGameFileList}}
{{GameFile
| Name = MRH_DOGC.DB?
| Format = [[All Dogs Archive format]]
| KnownFormat = Yes
| Desc = CGA graphics files
}}
{{GameFile
| Name = MRH_DOGC.DB?
| Format = [[All Dogs Archive format]]
| KnownFormat = Yes
| Desc = EGA\TGA graphics files
}}
{{GameFile
| Name = *.MUS
| Format = [[LPCM format]]
| KnownFormat = Yes
| Desc = Low quality audio clips used for short bits of music and sound
}}
{{GameFile
| Name = ?
| Format = [[All Dogs RLE compression]]
| KnownFormat = Yes
| Desc = This is a modified form of RLE used to compress some graphics data in the game archives
}}
{{EndGameFileList}}

* Some game text is contained in the executable, the executable is uncompressed. But some text is also stored, uncompressed, in the graphics archives.

[[Category:Polarware]]

All Dogs RLE Compression

2020-06-12T12:49:51Z

Levellass: Create page for the format, it was surprisingly annoying to figure out

{{Compression Infobox
| Type = Stream
| UnitSize = 1-bit
| Games =
{{All Dogs Go To Heaven}}
}}

[[All Dogs Go To Heaven]] uses [[RLE Compression]] to compress graphics chunks in its [[All Dogs Archive format|graphics archives.]] This is one of many possible ways to create a functional RLE system.

The compressed file consists of an UINT32LE giving the number of bytes (not pixels) in each row of the graphics chunk, an UINT32LE giving the number of rows in the graphic, and the compressed data. The first UINT32LE of the compressed data, which is almost always uncompressed, gives the size of the uncompressed data. As a check the decompressed size value should be equal to the width and height values multiplied.

The data can be either [[Raw CGA Data|CGA]] or [[Raw EGA data|EGA]] data which are four or two pixels of data per byte respectively.

The compressed data is processed in a loop. After each byte is read, its value is used to select an action. If the byte has a value of 27 (val & 0x1B) then the next word gives the number of identical bytes to output and the byte after that is the byte to repeat. All other bytes are passed through unchanged. The next byte is then read and the same procedure followed until there is no more data or the decompressed size has been reached. (This will be obtained elsewhere in the graphics archive even though it is also part of the graphics chunk.)

It should be noted that the repeat length words are big-endian, unlike all others in the game.

As a result of this inefficient scheme it is possible to 'compress' data in this format by simply replacing and 0x1B bytes with the sequence 1B 00 01 1B.

An illustration:

12 34 1B 00 03 56 78 90

This data is interpreted as follows:

12 34 # Copy 12 and 34 through unchanged
1B 00 03 56 # Repeat 56 three times
81 78 90 # Copy 78 and 90 through unchanged

Or as pseudocode:

* If [Decompressed data length] < [Final length] then:
*# Read a byte [Value]
*# If the byte value = 27, then:
*#* Move forward a byte
*#* Read the next two bytes
*#* Store this big-endian value as [length]
*#* Move forward two bytes
*#* Read the next byte
*#* Repeat the byte [length] thimes
*#* Move forward a byte and return to step 1.
*# Else:
*#* Read the next byte and output it unchanged
*#* Move forward a byte and return to step 1.

It can be seen that this system is very far from optimal since two, three and even four repeating bytes must be treated as non-repeating.

File:All Dogs Title.png

2020-06-12T12:25:03Z

Levellass: Titlescreen for All Dogs Go To Heaven.

Titlescreen for [[All Dogs Go To Heaven]].

All Dogs Go To Heaven

2020-06-12T12:23:00Z

Levellass: Create page. Not much to say here.

{{Stub}}
{{Game Infobox
| Title = All_Dogs_Title.png
| Levels = None
| Tiles = None
| Sprites = Not editable
| Fullscreen = Not editable
| Sound = None
| Music = Not editable
| Text = Not editable
| Story = Not editable
| Interface = Not editable
}}

'''All Dogs Go To Heaven''' is a 1989 video game for DOS and Amiga. It is based on the 1989 film of the same name and features ten minigames loosely tied together to form a story mode. The MS-DOS version is known for having surprisingly loud 'music' that plays at unexpected time.

The MS-DOS version also contains three executables and two sets of graphics files, for CGA, EGA,and TGA display respectively, with the TGA graphics being sourced from the EGA files.

== Tools ==

{{BeginGameFileList}}
{{GameFile
| Name = MRH_DOGC.DB?
| Format = [[All Dogs Archive format]]
| KnownFormat = Yes
| Desc = CGA graphics files
}}
{{GameFile
| Name = MRH_DOGC.DB?
| Format = [[All Dogs Archive format]]
| KnownFormat = Yes
| Desc = EGA\TGA graphics files
}}
{{GameFile
| Name = *.MUS
| Format = [[Wave file format|LPCM format]]
| KnownFormat = Yes
| Desc = Low quality audio clips used for short bits of music and sound
}}
{{GameFile
| Name = ?
| Format = [[All Dogs RLE compression]]
| KnownFormat = Yes
| Desc = This is a modified form of RLE used to compress some graphics data in the game archives
}}
{{EndGameFileList}}

* Some game text is contained in the executable, the executable is uncompressed. But some text is also stored, uncompressed, in the graphics archives.

[[Category:Polarware]]

Talk:Jill of the Jungle

2019-08-20T04:25:06Z

Levellass: JMod reply

In my version of Jill of the Jungle, the palettes were found at these locations:

Jill:

VGA to EGA conversion table @ 0x24964.

VGA palette @ 0x24A64.

Jill2:

VGA to EGA conversion table @ 0x1F5B4.

VGA palette @ 0x1F6B4.

Jill3:

VGA to EGA conversion table @ 0x1F704.

VGA palette @ 0x1F804.

Some of them differ from the posted. Does anyone else have a different version? --[[User:SaxxonPike|SaxxonPike]] 16:10, 12 July 2010 (GMT)
:Not sure - is there an easy way to tell which version a given .exe is? If so we should add a column to the table for the version number, so we can list the offsets for all known versions. Maybe also a signature code so it's easy for a program to identify which version a given file is. -- [[User:Malvineous|Malvineous]] 22:49, 12 July 2010 (GMT)

::I've seen different versions of a couple of Epic games, like Jill of the Jungle, Jazz Jackrabbit, Epic Pinball, Silverball and Extreme Pinball, and I couldn't find a version number inside the .exe files or see a version number when running the game. The only way to see which version number a game has, is to read what the included Helpme.doc file says. And even that is not foolproof as I've seen different .exe files with the same Helpme.doc file. Apogee surely did the version numbering a lot better than Epic :). [[User:Calvero|Calvero]] 11:17, 13 July 2010 (GMT)

:::The HELPME.DOC files can be quite misleading, actually. I've found a bunch of copies of the shareware episodes where the HELPME.DOC claims the game is version 2.0 when the game itself identifies itself by another version number (e.g. Solar Winds, version 2.0 in the .DOC and 1.1 in-game). Regarding Jill of the Jungle, there are "officially" (by officially I mean what they identify themselves as in the documents) only two recognized versions, 1.0 and 1.2. But there are also a number of revisions I've found to version 1.2 which I personally call 1.2, 1.2a, 1.2b and 1.2c. I know for a fact all of these revisions except 1.2c also have matching registered versions (I'm not too convinced that 1.2c actually had anything else than a shareware release). I have made a document some time ago to make it easier to identify these versions and it can be found from [http://aoebeta.110mb.com/Private/jill_versions.txt here] (the data is that of the main game EXE). --[[User:Litude|Litude]] 11:24, 15 July 2010 (GMT)

::::Wow, would you mind including that info on the main Jill page? I'm happy to do it but might be better if you do the first edit so it goes against your name in the edit history. Add an extra column for those palette offsets so we can add them in when we find them out for a particular version. My Jill versions match up well with your list, except my Jill 1 v1.0 (216804) is dated 1992-06-01, one day earlier than in your list. Also not sure if you're recording dates/versions of jjfile0.exe (the episode loader) because I'm not sure where that came from as I didn't find it until relatively recently. -- [[User:Malvineous|Malvineous]] 11:38, 15 July 2010 (GMT)

:::::Alright, I'll try adding the info though I don't really mind having someone else adding them (I don't really care that much about getting credited for stuff). Regarding the modify date of version 1.0, you're absolutely right. It seems my finger slipped when putting together that document. JJFILE0.EXE first appeared in version 1.2a and was also present in version 1.2b, but it was removed in 1.2c (which is why I think its shareware only, can't see any other reason for its removal). I don't record the dates of that file as as far as I know there are only two versions of the file, one of which is present in version 1.2a and the other one which is present in 1.2b.--[[User:Litude|Litude]] 12:43, 15 July 2010 (GMT)

::::::The version that is called version 1.1 of Jill 1 on [http://www.classicdosgames.com/game/Jill_of_the_Jungle.html RGB Classic Games] is called version 1.2a here, but when you run the game it says it's the United kingdom version. It gets this version information from the file INTRO.JN1. So at least one version of the game has in-game version information :). Through my own research I found out that only version 1.0 has the references to Commander Keen, Mario, Duke Nukem and Pac-Man in the map level. Can someone confirm this? It's possible to copy MAP.JN1 of version 1.0 to later versions to restore these references. [[User:Calvero|Calvero]] 15:42, 15 July 2010 (GMT)

:::::::That installer is mislabeled, check the documents and it's listed as being version 1.2 (there was no version 1.1 of the game as far as I know). I did check that version but didn't look through it thoroughly enough to notice that it has a modified INTRO.JN1, just concluded it was 1.2a. But that doesn't mean 1.2a was exclusively made for the United Kingdom, as you can find version 1.2a without this United Kingdom mention from [http://cd.textfiles.com/swheaven1/GAMES/JILL.ZIP here]. Regarding actual changes between the versions, I haven't really been looking into this but seeing as MAP.JN1 is identical in 1.2, 1.2a, 1.2b and 1.2c it seems likely. --[[User:Litude|Litude]] 16:01, 15 July 2010 (GMT)

:::::::While I can't confirm it, it has been discussed on the PCKF that the Commander Keen reference only appeared in early versions of Jill and for some reason it was later removed. Which, being a Commander Keen forum, was then immediately followed by many "where I can get the original version" requests. -- [[User:Malvineous|Malvineous]] 14:07, 16 July 2010 (GMT)

== Ordering Info same format as ZZT graphics? ==

It looks like the Ordering Info format described under the Episode Selection Screen might match the graphics format used for Super ZZT:

[[Super_ZZT_Graphics_Format]]

Thoughts?
--[[User:SaxxonPike|SaxxonPike]] ([[User talk:SaxxonPike|talk]]) 05:10, 5 March 2019 (UTC)
:Yes, that's exactly the format it uses, I was actually in the middle of trying to pick this apart.Maybe I should resurrect that half-done graphics editor. -[[User:Levellass|Endian? What are you on about?]] ([[User talk:Levellass|talk]]) 13:02, 10 March 2019 (UTC)

== New Level Editor ==

A new level editor, jMod, has recently been released for this game (http://k1n9duk3.shikadi.net/jmod.html), should it be added to this page?

::I'd vote yes, as a section or link. This is the MODDING wiki after all and should include all the tools that can be used in some form or other.-[[User:Levellass|Endian? What are you on about?]] ([[User talk:Levellass|talk]]) 04:25, 20 August 2019 (UTC)

Talk:Jill of the Jungle

2019-03-10T13:02:55Z

Levellass: Confirm Super ZZT format for order info

Softdisk Library Format

2018-11-02T23:31:55Z

Levellass: Reword and fix problems

{{Archive Infobox
| MaxFiles = 65,535
| FAT = Beginning
| Names = Yes, 8.3
| Metadata = None
| Subdirectories = N
| Compressed = Y
| Encrypted = N
| Hidden = Y
| Games =
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 3}}
{{Game|Dangerous Dave 4}}
}}
SLIB, or Softdisk LIBrary, compression is a container file format used by [[Softdisk]] software to compress various files used by their games, most notably the Commander Keen Dreams series of games, (Including Dangerous Dave 3 and Dangerous Dave 4)to store title images used at the beginning of each game. It was created in 1992 by Jim Row.

The data held in the file can be compressed in any one of three ways, uncompressed, LZW and LZH. The compression used is primitive and rather different from later or traditional versions of LZW\LZH. SLIB files were created by the program <tt>SOFTLIB.EXE</tt> and as such any game that uses this format contains various segments of code in common with <tt>SOFTLIB</tt> for the decompression of data.

There is a closely related format, the SHL or Softdisk Help Library format. SHL files contain only a single file. Their header is slightly different, it's file signature is 'CMP1' (CoMPression of 1 file) while that of SLIB files is SLIB. The veracity of both files can be confirmed by checking for a word of value 2 at offset 4 in the file. The actual files have been given a number of extensions; <tt>.CMP</tt> (CoMPressed), <tt>.SHL</tt> (Softdisk Help Library) or the game extension.

The SLIB file can roughly be broken into a number of parts; the header, which contains data about the various data chunks, and the data chunks themselves, each containing a single file. Each chunk also has a short header.

== Header ==

The file header is found only in SLIB files and is absent in SHL files, which are loaded into memory in their enitrety. The SLIB header allows individual data chunks to be loaded inhto memory seperately.

The SLIB header is a variable length header that contains information about how many chunks there are in a file as well as their location in the file and size. It is used by the game to load chunks into memory and by <tt>SOFLIB</tt> to extract compressed files.

The first part of the header is a fixed length of 8 bytes and allows the game to identify the file as SLIB and also the total length of the header (Which will be 30 * the value at offset 6 plus 8.) The second part is a series of chunk headers that hold information about what file is held in each chunk. (The last six bytes are repeated at the start of the data chunk.)

FILE HEADER:
0 CHAR[4] fID Signature, 'SLIB' (Softdisk LIBrary)
4 UINT16LE Version Version number, always $0002
6 UINT16LE Chunks Number of data chunks in file
8 CHAR[30x] Chunk headers Chunk headers

IMAGE HEADERS:
? CHAR[16] Name Name of compressed image (Max len 12 chars) padded with nuls
+16 UINT32LE Dat st Start of image data in file (From start of first image chunk)
+20 UINT32LE Dat end End of image data in file (From start of first image chunk)
+24 UINT32LE iOriginalSize Decompressed data size
+28 UINT16LE iCompression Compression used, 0 = none, 1 = LZW, 2 = LZH

== Data Chunks ==

The data chunk has a short header followed by the actual data itself. The format differs slightly between SLIB chunkks and SHL files. Both format must identify themselves to the game, and they do so in different ways.

Notice that in the case of SLIB chunks bytes 4-10 are identical to bytes 24-30 of that chunk's header.

SLIB CHUNK FORMAT
? CHAR[4] cID Signature'CUNK' (Chunk UNKompressed size)
+4 UINT32LE iOriginalSize Decompressed data size
+8 UINT16LE iCompression Compression method
+10 CHAR[?] Data Image data

SHL files are slightly more tricky; an uncompressed SHL file is simply raw data, compressed data must identify itself as such and so the header is slightly longer. It can be considered a combination of the chunk header and the SLIB header in the section above.

SHL FILE FORMAT
0 CHAR[4] cID Signature'CMP1' (CoMPressed s1ingle file)
4 UINT16LE iCompression Compression method (as above)
6 UINT32LE iOriginalSize Decompressed data size
10 UINT32LE iCompressedSize Compressed data size
14 CHAR[?] Data Image data

== Compression ==

As noted above there are three forms of compression. The first is simple enough, no compression at all, the data is simply stored in the file. (Actually increasing the size!) The other two are called 'LZW' and 'LZH' by the programmers but both differ from what are now standard implmentations of those formats.

=== LZW ===

A compression value of 1 means the chunk is [[LZW compression|LZW compressed]]. The format of the compression used is different from the more 'usual' implementation of LZW. Most LZW works by building a 'dictionary', but LZW is in essence just referring back to data that has already been read.

The core of the implementation is that if a sequence is encountered that has already been read then it is replaced with a pointer to it. There are three types of data, flag bytes, pointers and literals.

Flag bytes divide the datastream into segments of eight 'values' which can be either literals or pointers. Pointers are 2 bytes long, literals 1 byte. (Therefore there will be a flag byte every 8 to 16 bytes of data.) The value of each bit (In little endian) indicates whether a value will be a literal (1) or codeword (0) Thus a value of 199 (11000111 in binary) indicates three pointers, three literals and two pointers in that order. (Total of 13 bytes.)

Literals are sequences that have never been seen in the datastream before, they cannot be compressed and are thus the same in the compressed and decompressed datastreams. (If the data is text they become quite obvious.) Any string less than 3 bytes long that has not been read before or cannot be pointed to (See below) will be stored as literals.

Pointers are reference to data that has already been read. They are two bytes long, with the first 12 bits giving the location to read data from and the last 4 bits giving the length of data to read.

The lower nybble (4 bits) of the second pointer byte holds the length of repeat data to read minus three. (This makes sense, the shortest sequence it makes sense to code is three bytes which can be given the value 0.) It will be immediately apparent that the maximum length of repeated data that can be stored as a pointer is 18 bytes.

The high nybble of the second byte is multiplied by 256 then added to the first byte to give the location of the data to read in the 'sliding window' minus 18. In hexadecimal this is as simple as appending the nybble to the first byte. For example flag bytes of <tt>$EA $F6</tt> point to location <tt>$FEA</tt> with '6' relating to the data length to read.

The 'sliding window' in this case is the region of decompressed data that the compressed data can point to. It will be immediately obvious that the pointers can encode values between +-2048, or about 2KB. If the decompressed data is less than 2KB in size then zero is the start of the data, if it is larger than it is 2048 bytes from the end of the data. (This is the origin of the term 'sliding window'; it is a window of data that can be slid along the datastream as it gets bigger.)

It will be noted that it is probable that the compressed datastream will not be perfectly divisible by flag bytes. In this case the unused bits are set to 0. The decompressor stops when the decompressed data size is equal to the value given in the chunk header.

The last thing to keep in mind is that the flagged location obtained requires 18 to be added to it. This is due to how the decompressor is set up in memory; it needs a buffer of 18 bytes (the maximum length of compressed data that can be decompressed) between where it is working and the start of the datastream proper. These bytes are initially filled with blank spaces (<tt>$20</tt> not <tt>$00</tt>.) and considered part of the datastream but not part that is output to the final file. (Their locations are negative.)

This has an odd result; it's entirely possible for a flag byte to point to a negative value and output one or more characters that were never part of the uncompressed data. To illustrate this we will look at the text string 'I am Sam. Sam I am!' as compressed by <tt>softlib.exe</tt>. Note that on line 6 it requests 5 bytes from address -1. This is the string ' I am'. The last four bytes are from the start of the sentence but the first, a blank space, comes from the buffer.

FF Flag byte, 8 literals follow
49 20 61 6D 20 53 61 6D 'I am Sam' as literals
09 Flag byte, 1L, 2P, 1L,4Blanks ($09 = 00001001)
2E '.' as literal
F2 F1 Pointer, read 1 + 3 = 4 bytes from $FF2, or -14 + 18 = 4 in the data. This is ' Sam'
ED F2 Pointer, read 2 + 3 = 5 bytes from $FED or -19 + 18 = -1 in the data. This is ' I am'
21 '!' as literal

=== LZH ===

LZH is a combination of LZW and [[Huffman Compression]]. In its simplest implementation it is two levels of compression, first the data is LZW compressed, then it is Huffman compressed. This is used for example in <tt>GAMEMAPS</tt> However, the compression used in this case seems to be similar to that used in Keen 1, pure LZW using a dictionary.

The format is far from elucidated, but a table in the executables involved can be used to convert data into the 8 and 9 bit codes used for perfectly incompressible data. (Once compression starts being used this changes, indicative that this table is used to build the initial LZW dictionary.)

It is also notable that it seems to use both 8 and 9 bit codes, which is very difficult to do without some table to indicate the length of the codes. This varaible codeword length may be why the compression is said to be 'huffman'

The [http://www.apogeesoftware.com/uncategorized/apogee-releases-blake-stone-source-code Planet Strike source code release] contains C code that handles LZH compression and decompression in <tt>JM_LZH.C</tt>. The code was written by Jim T. Row, who apparently also wrote the Softlib utility, so chances are it is the same implementation of LZH.

== Softlib ==

Soflib (Softdisk Library Creator) is a DOS program that can be used to create or extract files from SLIB files. It can work with both forms of compression used in SLIB files. It is notable that for some reason files shorter than 24 bytes often fail to be compressed correctly. (Soflib outputs a library with an empty chunk in it.) Soflib can be downloaded from the tools section of this page.

== Data contained in libraries ==

Keen Dreams uses SLIB to compress its title screen and also comes with a number of LZH compressed .SHL files containing text. The title screen is in [[LBM Format]] It is notable that the game does not read most of the LBM chunks, focusing instead on the FORM, BMHD and BODY chunks. This is because while the compressed files were designed to be viewed and edited in a standalone program, the game did not need things such as the LBM palette.

Dangerous Dave 3 and 4 use an additional SLIB file to store their digital sound effects, which are seperate from their [[AudioT Format|PC\adlib sounds]]

== Tools ==

* [http://www.shikadi.net/files/games/softdisk/softlib.exe SOFTLIB.EXE] - original DOS program that can create and modify Softdisk Libraries
* [http://dl.dropbox.com/u/3940020/Titlebuild.zip TITLEBUILD] - Windows program to turn a 320x200 bitmap into <tt>KDREAMS.CMP</tt> for Keen Dreams

== Credits ==

This format partially reverse engineered by [[User:Lemm]] and [[User:Levellass]].

Duke 1 Level Format

2018-07-30T15:41:02Z

Levellass: Fix two errors in object table

{{Map Infobox
| Type = 2D tile-based
| Layers = 1
| Tile size = 16×16
| Viewport = 208×160
| Games =
{{Game|Duke Nukem}}
}}

The levels in [[Duke Nukem]] 1 are stored in the files <tt>WORLDALx.DNy</tt>, where y is the episode number, and x is the level number, going from 1-9 then A-C. Oddly, level 2 is the intermediate level and level C is the demo level.

Level structure is very simple, each level is 128x90 tiles in size and consists of 11520 UINT16LE words (23040 bytes) of data. Each word controls what appears on one tile in the level. (The level has only one plane, containing background, foreground and enemies. Thus each word is sometimes called a ShapeThing. Because of this limit, the game has some interesting shortcuts to allow things to appear more naturally, such as an enemy tile using the tile before it as its background.) The following values control what appears:

{|class="wikitable"
! Range (hex) !! Class !! Description
|-
| 0000-05FF || Flashers || Animated backgrounds or stationary backdrops, Duke can pass through these.
|-
| 0600-17FF || Backgrounds || Static background objects that Duke can pass through.
|-
| 1800-2FFF || Solids || Static foreground objects that Duke cannot pass through.
|-
| 3000-3059 || Active || This is the fun stuff, all the things that move, such as techbots, bonuses, items, Duke's starting location, hazards (spikes, force fields), doors, keyholes/access slots, conveyor belts and some special effect items (such as mirror floor and transparent windows).
|-
| 306A-FFFF || (Hacks) || Static foreground objects that Duke cannot pass through. The first tiles use tile images from BORDER.DN? and most of the later tiles are displayed as random junk. All of these tiles are clingable.
|}

== Tile mapping ==

The Level's tiles use tile graphics from 8 files: <tt>BACK0.DN?</tt> through <tt>BACK3.DN?</tt> and <tt>SOLID0.DN?</tt> through <tt>SOLID3.DN?</tt>. Tiles from <tt>BORDER.DN?</tt> can also be used, though they are not "officially" supported.

Each file contains 48 tiles (at least the game loads 48 tiles from each file), so there are 384 "actual" tiles. Due to the way the tile graphics are stored in memory, you need to divide the tile value by 32 (EGA plane size of a 16x16 pixel tile) to get a tile index from the data stored in the level file.

{|class="wikitable"
! Range (hex) !! File
|-
| 0000-05FF || BACK0.DN?
|-
| 0600-0BFF || BACK1.DN?
|-
| 0C00-11FF || BACK2.DN?
|-
| 1200-17FF || BACK3.DN?
|-
| 1800-1DFF || SOLID0.DN?
|-
| 1E00-23FF || SOLID1.DN?
|-
| 2400-29FF || SOLID2.DN?
|-
| 2A00-2FFF || SOLID3.DN?
|-
| 3000-367F || Varies, see below
|-
| 4000-? || current backdrop 1 (hack)
|-
| 8100-? || current backdrop 2 (hack)
|}

=== Active ===

The follow tiles appear to be manually mapped. These tile codes from the map do not need to be divided by 32, unlike the other tilecodes.

{|class="wikitable"
! Tile code (hex) !! File !! Tile index !! Type !! Description
|-
| 3000 || OBJECT0.DN1 || 0 || Bonus || Grey box, empty
|-
| 3001 || OBJECT0.DN1 || 5 || Interactive || Elevator
|-
| 3002 || {{TODO|?}} || ? || Interactive || Left-moving conveyor belt start, must be left of end tile
|-
| 3003 || {{TODO|?}} || ? || Interactive || Left-moving conveyor belt end, must be on right of start tile
|-
| 3004 || {{TODO|?}} || ? || Interactive || Right-moving conveyor belt start, must be left of end tile
|-
| 3005 || {{TODO|?}} || ? || Interactive || Right-moving conveyor belt end, must be on right of start tile
|-
| 3006 || OBJECT0.DN1 || 10 || Bonus || Grey box (0 @ OBJECT0.DN1), contains shoes
|-
| 3007 || OBJECT0.DN1 || 11-17 || Interactive || Rocket, tile below is replaced with default tile after rocket takeoff
|-
| 3008 || OBJECT0.DN1 || 24-28 || Hazard || Flamethrower, firing to the right (three tiles wide including placement tile)
|-
| 3009 || OBJECT0.DN1 || 18 || Bonus || Grey box (0 @ OBJECT0.DN1), contains celing-clinger
|-
| 300A || OBJECT0.DN1 || 29-33 || Hazard || Flamethrower, firing to the left (three tiles wide including placement tile)
|-
| 300B || ANIM0.DN1 || 0-5 || Enemy || Floating 1x1 robot with purple antenna
|-
| 300C || ANIM0.DN1 || 10-33 || Enemy || Jumping 2x2 robot
|-
| 300D || ANIM0.DN1 || 34-41 || Enemy || Wheeled 2x1 robot with blue wheels
|-
| 300E || ANIM1.DN1 || 0-31 || Enemy || 2x2 rotating wheel with flames
|-
| 300F || OBJECT0.DN1 || 43 || Bonus || Grey box (0 @ OBJECT0.DN1), contains raygun (ammo)
|-
| 3010 || ANIM1.DN1 || 32 || Enemy || 1x1 robot
|-
| 3011 || - || - || - || Exit door (only 1 instance allowed!)
|-
| 3012 || ANIM2.DN1 || 17 || Bonus || Grey box (0 @ OBJECT0.DN1), contains dynamite
|-
| 3013 || ANIM2.DN1 || 24-31 || Enemy || Flying orb monster, each shot removes one orb
|-
| 3014 || - || - || Decorative || Shimmering water effect, also affects tile below this one
|-
| 3015 || ANIM2.DN1 || 32-35 || Bonus || Red box (1 @ OBJECT2.DN1), contains soda can
|-
| 3016 || ANIM2.DN1 || 40-43 || Enemy || Green bitey creature walking up and down walls, facing right
|-
| 3017 || ANIM2.DN1 || 44-47 || Enemy || Green bitey creature walking up and down walls, facing left
|-
| 3018 || OBJECT0.DN1 || 44 || Bonus || Red box (1 @ OBJECT2.DN1), contains turkey drumstick
|-
| 3019 || ANIM3.DN1 || 0 || - || Bridge that explodes when stepped on twice (only 1 instance allowed!)
|-
| 301A || OBJECT1.DN1 || 0-3 || Hazard || Blue force field, horizontal
|-
| 301B || ANIM3.DN1 || 12-19 || Hazard || Rotating fan blades, can't stand on when shot
|-
| 301C || ANIM3.DN1 || 12-19 || Hazard || Rotating fan blades, can stand on when shot
|-
| 301D || OBJECT1.DN1 || 8 || Bonus || Blue box (0 @ OBJECT2.DN1), contains football
|-
| 301E || OBJECT1.DN1 || 9 || Bonus || Blue box (0 @ OBJECT2.DN1), contains joystick
|-
| 301F || OBJECT1.DN1 || 10 || Bonus || Blue box (0 @ OBJECT2.DN1), contains "DN" floppy
|-
| 3020 || OBJECT1.DN1 || 13 || Bonus || Grey box (0 @ OBJECT2.DN1), contains robohand
|-
| 3021 || OBJECT1.DN1 || 15-18 || Hazard || White/blue force field, vertical
|-
| 3022 || ANIM3.DN1 || 20-47 || Enemy || Helicopter
|-
| 3023 || OBJECT1.DN1 || 19-23 || Bonus || Blue box (0 @ OBJECT2.DN1), contains balloon
|-
| 3024 || ANIM4.DN1 || 8-10 || Bonus || Security camera
|-
| 3025 || ANIM4.DN1 || 11 || Decorative || Brown spikes
|-
| 3026 || ANIM4.DN1 || 12 || Decorative || Rock, left half
|-
| 3027 || ANIM4.DN1 || 13 || Decorative || Rock, right half
|-
| 3028 || ANIM4.DN1 || 14 || Decorative || Grey rounded window
|-
| 3029 || OBJECT1.DN1 || 24 || Bonus || Grey box (0 @ OBJECT0.DN1), contains nuclear molecule
|-
| 302A || OBJECT1.DN1 || 33 || Hazard || Loose/falling ACME sign
|-
| 302B || OBJECT1.DN1 || 34 || Hazard || Blue reactor
|-
| 302C || OBJECT1.DN1 || 45-46 || Hazard || Spike, pokes up when walking over
|-
| 302D || OBJECT1.DN1 || 47-49 || Bonus || Blue box (0 @ OBJECT2.DN1), contains magenta flag
|-
| 302E || OBJECT2.DN1 || 2-4 || Bonus || Blue box (0 @ OBJECT2.DN1), contains radio
|-
| 302F || ANIM4.DN1 || 20-28 || Interactive || Teleporter, transports to tilecode 3030
|-
| 3030 || ANIM4.DN1 || 20-28 || Interactive || Teleporter, transports to tilecode 302F
|-
| 3031 || ANIM4.DN1 || 31 || Hazard || Spiky round red bomb, bouncing
|-
| 3032 || - || - || Interactive || Player start point
|-
| 3033 || OBJECT1.DN1 || 14 || Bonus || Grey box (0 @ OBJECT0.DN1), contains access card
|-
| 3034 || OBJECT2.DN1 || 5-12 || Interactive || Access card activation point
|-
| 3035 || OBJECT2.DN1 || 14-15 || Interactive || Robohand activation point
|-
| 3036 || {{TODO|?}} || ? || ? || Red girder, creates a bridge when Robohand activation point is used
|-
| 3037 || OBJECT2.DN1 || 21 || Bonus || Grey box (0 @ OBJECT0.DN1), contains "D"
|-
| 3038 || OBJECT2.DN1 || 21 || Bonus || Grey box (0 @ OBJECT0.DN1), contains "U"
|-
| 3039 || OBJECT2.DN1 || 21 || Bonus || Grey box (0 @ OBJECT0.DN1), contains "K"
|-
| 303A || OBJECT2.DN1 || 21 || Bonus || Grey box (0 @ OBJECT0.DN1), contains "E"
|-
| 303B || ANIM2.DN1 || 18-23 || Bonus || Purple rabbit thing, 5000 bonus points
|-
| 303C || ANIM5.DN1 || 1 || Enemy || Fire monster
|-
| 303D || ANIM5.DN1 || 12 || Decorative || Diamond-shaped wire mesh
|-
| 303E || ANIM5.DN1 || 13 || Decorative || Window showing through to backdrop, left half
|-
| 303F || ANIM5.DN1 || 14 || Decorative || Window showing through to backdrop, right half
|-
| 3040 || OBJECT2.DN1 || 23 || Interactive || Message, press up to read (blank message for most levels?)
|-
| 3041 || - || - || - || Screen display with Dr. Proton
|-
| 3042 || ANIM5.DN1 || 30-42 || Enemy || Dr Proton, E3 boss, killable ("I won it all!", game ends)
|-
| 3043 || ANIM5.DN1 || 30-42 || Enemy || Dr Proton, E1 boss, not killable (escapes to moon, game ends)
|-
| 3044 || OBJECT2.DN1 || 24 || Interactive || Door key, red
|-
| 3045 || OBJECT2.DN1 || 25 || Interactive || Door key, green
|-
| 3046 || OBJECT2.DN1 || 26 || Interactive || Door key, blue
|-
| 3047 || OBJECT2.DN1 || 27 || Interactive || Door key, magenta
|-
| 3048 || OBJECT2.DN1 || 37 || Interactive || Door lock, operated by red key
|-
| 3049 || OBJECT2.DN1 || 38 || Interactive || Door lock, operated by green key
|-
| 304A || OBJECT2.DN1 || 39 || Interactive || Door lock, operated by blue key
|-
| 304B || OBJECT2.DN1 || 40 || Interactive || Door lock, operated by magenta key
|-
| 304C || OBJECT2.DN1 || 28 || Interactive || Door, opened by red lock
|-
| 304D || OBJECT2.DN1 || 28 || Interactive || Door, opened by green lock
|-
| 304E || OBJECT2.DN1 || 28 || Interactive || Door, opened by blue lock
|-
| 304F || OBJECT2.DN1 || 28 || Interactive || Door, opened by magenta lock
|-
| 3050 || OBJECT1.DN1 || 8 || Bonus || Football
|-
| 3051 || OBJECT0.DN1 || 44 || Bonus || Turkey drumstick
|-
| 3052 || ANIM2.DN1 || 32-35 || Bonus || Soda can
|-
| 3053 || OBJECT1.DN1 || 10 || Bonus || "DN" floppy disk
|-
| 3054 || OBJECT1.DN1 || 9 || Bonus || Joystick
|-
| 3055 || OBJECT1.DN1 || 47-49 || Bonus || Purple flag
|-
| 3056 || OBJECT2.DN1 || 2-4 || Bonus || Radio
|-
| 3057 || ANIM4.DN1 || 31 || Hazard || Spiky round red bomb, stationary, explodes on touch
|-
| 3058 || OBJECT2.DN1 || 48 || Hazard || Spikes, poking up
|-
| 3059 || OBJECT2.DN1 || 49 || Hazard || Spikes, poking down
|}

== Links ==

There are numerous level editors available, from the basic original ASCII one, to rather advanced ones capable of rendering animations.

* Maps can be found at [http://vgmaps.com/Atlas/PC/index.htm#DukeNukem vgmaps.com]
* The original level editor is at [http://archive.shikadi.net/sites/www.geocities.com/dooknookimklassik/ Dook Nookim Klassik]
* A reasonable level editor can be found at [http://crystalshard.net/?p=8&s=51 crystalshard.net]
* Possibly the best editor is DN1MOD, which renders levels as the game does, by loading the game's graphics files [http://archive.shikadi.net/sites/members.iinet.net.au/~markim/admiral_bob/files/]

File:Duke 1 Level Format.png

2018-07-30T15:38:18Z

Levellass: Custom level in the Duke 1 Level Format

Custom level in the [[Duke 1 Level Format]]

Jill of the Jungle

2018-07-09T07:44:48Z

Levellass: Add selection executables data formats

{{Game Infobox
| Levels = Edit
| Tiles = No
| Sprites = No
| Fullscreen = None
| Sound = No
| Music = Edit
| Text = No
| Story = Edit
| Interface = No
}}

[[Jill of the Jungle]] is the first version of the engine which would go on to power [[Xargon]]. It supports CGA, EGA and VGA graphics by way of "colour maps", which dictate the CGA and EGA colours to be used to display each of the possible 256-colours of a given image. This way only a single 256-colour image is supplied, rather than a different image for each display.

Jill is also unique in that it is one of a very small number of games that include a level editor, albeit an undocumented one. See the [[Using the official Jill of the Jungle level editor|tutorial]] for more details.

== Tools ==

{{BeginFileFormatTools|Type=game}}
{{FileFormatTool
| Name = [[Using the official Jill of the Jungle level editor|Built-in editor]]
| Platform = DOS
| grp = N/A
| map = Edit
| gfx = No
| mus = No
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [[Camoto]]
| Platform = Linux/Windows
| grp = N/A
| map = Edit
| gfx = Read
| mus = Edit
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [http://ftp.funet.fi/pub/msdos/games/editors/jilledit.zip JillEdit] [http://www.stuntsillusion.com/download/jilledit.zip (mirror)]
| Platform = DOS
| grp = N/A
| map = Edit
| gfx = No
| mus = No
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{EndFileFormatTools}}

{{BeginGameFileList}}
{{GameFile
| Name = *.cfg
| Format = [[CFG Format (Jill of the Jungle)]]
| KnownFormat = Yes
| Desc = Game configuration
}}
{{GameFile
| Name = *.ddt
| Format = [[CMF Format]]
| KnownFormat = Yes
| Desc = Background music
}}
{{GameFile
| Name = jill,dma
| Format = [[DMA Format]]
| KnownFormat = Yes
| Desc = Tile information
}}
{{GameFile
| Name = *.jn[123]
| Format = [[Jill of the Jungle Map Format]]
| KnownFormat = Yes
| Desc = Game levels
}}
{{GameFile
| Name = *.mac
| Format = [[MAC Format (Jill of the Jungle)]]
| KnownFormat = Yes
| Desc = Demo macros
}}
{{GameFile
| Name = *.sha
| Format = [[SHA Format]]
| KnownFormat = Yes
| Desc = Shapes (images/tiles)
}}
{{GameFile
| Name = *.vcl
| Format = [[VCL Format]]
| KnownFormat = Yes
| Desc = Sound and text assets
}}
{{GameFile
| Name = jn[123]save.[0-9]
| Format = [[Jill of the Jungle Map Format]]
| KnownFormat = Yes
| Desc = Saved games - just dumps of the entire level in its current state
}}
{{EndGameFileList}}

== Palette ==
[[Image:Jill of the Jungle palette.png|thumb|right|128px|Jill of the Jungle palette]]
The VGA palette can be found inside the .EXE file. The palette is the same in all episodes and versions.

==== Episode 1: Jill of the Jungle ====
{|class="wikitable"
!Version!!CRC32!!Date!!Size!!Palette Offset
|-
|1.0||7899CC28||1992-06-01||216 804 bytes||0x1ED84
|-
|1.2||9540714E||1992-07-12||204 784 bytes||0x1F884
|-
|1.2(a)||51ADAE83||1992-07-30||206 963 bytes||0x1FD54
|-
|1.2(b)||171E9EC0||1992-08-21||206 712 bytes||0x1FC34
|-
|1.2(c)||C52CA6D9||1993-02-17||206 636 bytes||0x1FC04
|-
|1.2(d)||0E7C596F||1993-12-27||219 216 bytes||0x24A64
|}

==== Episode 2: Jill Goes Underground ====
{|class="wikitable"
!Version!!CRC32!!Date!!Size!!Palette Offset
|-
|1.0||6064EA0A||1992-06-17||65 166* bytes||0x1F0B4†
|-
|1.2(a)||?||1992-07-30||?||?
|-
|1.2(b)||17477A49||1992-08-21||204 158 bytes||0x1F6E4
|-
|1.2(c)||75176ED7||1993-02-17||204 096 bytes||0x1F6B4
|-
|1.2(d)||0FDB489E||1993-12-27||218 338 bytes||0x26A64
|}

==== Episode 3: Jill Saves the Prince ====
{|class="wikitable"
!Version!!CRC32!!Date!!Size!!Palette Offset
|-
|1.0||3B4D8C3B||1992-07-07||201 616 bytes||0x1F1F4
|-
|1.2(a)||B4EA288C||1992-07-30||204 425 bytes||0x1F804
|-
|1.2(b)||D5345AFB||1992-08-21||204 174 bytes||0x1F6E4
|-
|1.2(c)||3FFF0F6C||1993-02-17||204 112 bytes||0x1F6B4
|-
|1.2(d)||E27D4300||1993-12-27||218 370 bytes||0x26A64
|}

*This version has been packed using [[LZEXE|LZEXE91]]. 
†Data taken from version after uncompressing using [[UNLZEXE]].

The palette is in [[VGA Palette|classic VGA format]] (6-bit RGB.) Note that the [[SHA Format]] can override this palette.

== Episode selection screen ==

Some versions of Jill come bundled with an episode loader executable which displays an interactive screen that allows the player to select from three episodes (if present) and ordering info. The executable contains large amounts (About 90%) of raw data used to display the screen itself and the ordering info if selected. The selection screen uses a single image but various areas of it are faded in in sequence when the executable runs.

The ordering info data seems to be slightly compressed using some form of RLE where certain characters act as flags. Values of 0-16 for example set colors, 24 moves down a line and 25 sets a run of spaces indicated by the next byte.

{|class="wikitable"
!Data!!Location!!Size
|-
|Screen||04E7||64'000 bytes
|-
|Screen palette||FEE7||768 bytes
|-
|Order info||12AF2||23'630 bytes
|}

== Notes ==
* Since the level files are used for a lot of different things, you can e.g. swap <tt>INTRO.JN1</tt> and <tt>1.JN1</tt> and then when you load the first level you'll be playing the intro screen. The demo and help screens can be accessed in the same way.
* You can also press Ctrl+P on the main menu to play the intro level, and Ctrl+E to enter the [[Using the official Jill of the Jungle level editor|level editor]].

== External links ==
* [http://jillofthejungle.110mb.com/home.html Unofficial Jill of the Jungle page] ([http://members.tripod.com/classic_roach/id14.html Older version], and [http://jill-of-the-jungle.tripod.com/jillsite/index.html alternate version])
* [http://ftp.funet.fi/pub/msdos/games/editors/jilledit.zip JillEdit] [http://www.stuntsillusion.com/download/jilledit.zip (mirror)] - a level editor for Jill of the Jungle created by Rory L. Fisher.
* [http://www.vgmaps.com/Atlas/PC/index.htm#JillOfTheJungle vgmaps.com] - all Jill maps as image files
* [http://www.youtube.com/watch?v=_88gJZoLpyc "Funky" remix] by Nick Stubblefield

[[Category:Epic Megagames]]
[[Category:Sidescroller]]

EGAGraph Format

2017-06-17T06:48:35Z

Levellass: REmove stub status (Seriously?) Continue demo format

{{Tileset Infobox
| Hardware1 = VGA
| Palette = External
| Names = N
| HasTransparency = Y
| Metadata = None
| Subtilesets = N
| Compressed = Y
| Hidden = N
| Games =
{{Game|Catacomb 3-D}}
{{Game|Catacomb Abyss}}
{{Game|Commander Keen 4-6}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 3}}
}}

'''EGAGraph''', short for 'EGA graphics library' is the format used to store graphics, demos, fonts, game texts and more in many early [[:Category:Id Software|id Software]] games.

The basic format is that of a number of [[Huffman Compression]] compressed sub-files (Chunks) stored in a similar manner to the [[AudioT Format]]. Like this format it has three main files, <tt>EGAGRAPH</tt>, <tt>EGAHEAD</tt>and <tt>EGADICT</tt>.

It is notable that while the <tt>EGAHEAD</tt> and <tt>EGADICT</tt> are stored in the game executable, they need to be extracted for [[TED5]] to edit levels.

This article may contain errors as some formats have not been worked out completely.

== EGA Head (EGAHEAD.xxx) ==

There are two versions of this format. The first version, used in [[Commander Keen Dreams]], [[Dangerous Dave 3]] and [[Dangerous Dave 4]], is an array of 4-byte little-endian values. The second version, used in all later EGA games, is an array of 3-byte unsigned little-endian values.

This header file may be present as an external file (eg. [[Bio Menace]]), or it may be included in the EXE file (eg. [[Catacomb 3-D]]). The last entry in the header is always the size of the EGAGRAPH.xxx file, and the first entry in the header is always 00 00 00. To find the end, you can search for filesize(EGAGRAPH.xxx) as a 3-byte (little-endian) value in the EXE. Then to find the start, go back 3 bytes at a time until you get to 00 000 00. Or use the fact that entries always get smaller as you go back, unless the entry is $FFFFFF.

In [[Catacomb 3-D]] v1.00 <tt>EGAHEAD.C3D</tt> is at $1BFD0 from the start of the decompressed ([[unlzexe]]) EXE file, and is 1437 bytes long, or 479 3-byte entries (for 478 chunks). It is then followed by 3 zero bytes (padding to multiple of 16?) 00 00 00, then the <tt>MAPHEAD.C3D</tt>.

In [[Catacomb Abyss]] v1.13 <tt>EGAHEAD.ABS</tt> is at $1BDB0 from the start of the decompressed ([[unlzexe]]) EXE file, and 1881 bytes long and has 626 chunks.

In [[Catacomb Apocalypse]] v1.00b <tt>EGAHEAD.APC</tt> is at $1E270 from the start of the decompressed ([[unlzexe]]) EXE file, and 2049 bytes long and has 682 chunks.

This header file stores the offsets (relative to the start of the <tt>EGAGRAPH</tt> file) for each sub file. The format is trivial, in that the header file is simply an array of 3 or 4 byte variables. (Each variable is a "slot", as the game refers to files by index.) Most games use the more compact 3-byte variables, since the <tt>EGAGRAPH</tt> file is never larger than $FFFFFF. However games based on older engines, notably [[Commander Keen Dreams]], [[Dangerous Dave 3]] and [[Dangerous Dave 4]], use 4-byte vales as these are easier to deal with.

It is important to note that not every 'slot' will be in use. Tiles especially if blank (All black) will be considered 'empty' and not worth adding to the file. (A blank 16x16 tile takes up 12 bytes of space if compressed, and there can be hundreds.) There are two ways of dealing with this; by default the games set all empty slot headers to -1, but many programs compress the graphics anyway and use a normal header value for them.

The last offset in the file will be an offset to the end of the main <tt>EGAGRAPH</tt> file. (So this should be ignored when reading the file to prevent a zero-byte file appearing last.) The total size of the <tt>EGAHEAD</tt> divided by 3 (Or 4) will also give the number of 'slots' the game uses. This varies, but is usually about 10,000.

Unlike [[AudioT Format]] files, <tt>EGAGRAPH</tt> is always compressed. However the header and dictionary may be external (E.g [[Bio Menace]])

== Dictionary (EGADICT.xxx) ==

The same [[Huffman Compression]] scheme used elsewhere in the [[Commander Keen]] series is used. When reading compressed chunks out of the <tt>EGAGRAPH</tt> file, the first four bytes located at the <tt>EGAHEAD</tt> offset are a UINT32LE specifying the file's decompressed size (which is required for the decompression algorithm.) The compressed data then follows, EXCEPT for 16x16 masked and unmasked tiles. Since these all have a similar decompressed size (128 bytes for unmasked, 256 bytes for masked) it is a waste of space to include these (Since tiles make up the bulk of graphics slots.) The decompressed size is hard coded, as are the start and finish of the unmasked and masked tile slots.

Note that the <tt>EGADICT</tt> file is not often obvious, usually being embedded in the main exe file. It is possible to locate it by looking for the string <tt>$FD $01 $00 $00 $00 $00</tt>, which appears at the end of nearly all Huffman dictionaries. They are the last 6 bytes out of 1024 (256*2*2), so add 6 and subtract 1024 to get the start (pointer to the head node).

Executables usually contain two or more dictionaries, but the <tt>EGADICT</tt> is usually '''the second one''', except in the case of early games like Keen Dreams, where it is the first of THREE. (A simple check of whether it decompresses the data sensibly works.)

In [[Catacomb 3-D]] <tt>EGADICT.C3D</tt> is at offset $24464 from the start of the decompressed CAT3D.EXE, which is the second Huffman dictionary and comes immediately after the first Huffman Dictionary.

In [[Catacomb Abyss]] v1.13 <tt>EGADICT.ABS</tt> is at offset $2734C from the start of the decompressed CATABYSS.EXE, which is the second Huffman dictionary.

In [[Catacomb Apocalypse]] v1.00b <tt>EGADICT.APC</tt> is at offset $26B24 from the start of the decompressed CATAPOC.EXE, which is the second Huffman dictionary.

== Main file (EGAGRAPH.xxx) ==

This file is simply an array of data files. Each file starts at the offset specified in the <tt>EGAHEAD</tt> file, and as there are no filenames each file is referred to by its index/slot number. Slots containing dummy values in the header are treated as if they don't exist in the <tt>EGAGRAPH</tt> file. Each file within the <tt>EGAGRAPH</tt> file is individually compressed. A file can be read by opening the <tt>EGAGRAPH</tt> file, seeking to the offset specified in the <tt>EGAHEAD</tt> file, reading a UINT32LE for the decompressed file size, and then decompressing the data from that point onwards using standard Huffman decompression techniques.

Note that in early games such as Keen Dreams, the <tt>EGAGRAPH</tt> file may have another name. (Such as <tt>KDREAM.EGA</tt> in that case.) in which case it is always the largest non-executable file.

=== Chunks ===

Each sub file or chunk is a separate graphic, ordered in the <tt>EGAGRAPH</tt> file in a specific way, much again like the [[AudioT Format]]. Chunks are labeled starting at 0. The game executable is hard coded for the start and finish of various chunk types. For example, Keen 4 has chunks 124-520 as sprites and will treat any chunk between these two numbers as a sprite. (Note that the game refers to chunk number, not sprite number.) The usual order of chunks is:

Picture table
Masked picture table
Sprite table
Fonts
Pictures (Unmasked bitmaps)
Masked pictures
8x8 unmasked tiles (Single chunk)
8x8 masked tiles (Single chunk)
16x16 unmasked tiles
16x16 masked tiles
32x32 unmasked tiles (Optional)
32x32 masked tiles (Optional)
Misc graphics (Optional)
Game texts
Demo files (Optional)
Misc data (Optional)

== Chunk formats ==

When compressed each chunk consists of a dword giving the decompressed size followed by the compressed data.

=== Picture table ===

Always present and always the first chunk, the picture table is 4 * numpics bytes long, consisting of two words for each picture (Width\8, Height) used when displaying picture chunks.

Divide the decompressed size by 4 to get numpics.

=== Masked picture table ===

Always present and always the second chunk, the picture table is 4 * numpics bytes long, consisting of two words for each picture (Width\8, Height) used when displaying masked picture chunks. This table is often quite small.

=== Sprite table ===

Always present and always the third chunk, the picture table is 16 * numspr bytes long, consisting of eight words for each sprite image (Width\8, Height, x offset, y offset and clipping rectangle left, top, right and bottom; all in that order.) used when displaying sprite chunks. This is what Modkeen exports as its notoriously hard to use xSPRITES.txt file.

=== Fonts ===

Always present and always starting at the fourth chunk. (Chunk 3!) Each chunk is a single monochrome font, containing all the entries from 0-255 for that font. Each 'letter' is stored separately and consecutively. A game will have at least one, and usually 3 fonts. The format is version two of [[EGA Font format]]

Fonts are used in the game for game texts. They can be stretched or colored and are always transparent, meaning they look strange when not over a single-color background.

=== Pictures (Bitmaps) ===

These follow game fonts. You need to know how many fonts there are before it to know how what chunk number the first picture is (3+NumFonts). In [[Catacomb 3-D]] there are 2 fonts.

Bitmaps are stored as standard [[Raw EGA data]], the size of each plane being the decompressed chunk size \ 4. In order to be displayed properly these need information from chunk 0, the picture table. Note that unlike fonts, data does not wrap, so a 4x4 sprite will consist of four planes of four bytes in size, the same as an 8x4 sprite.

Pictures are used for things such as title screens or pictures in game texts. Most of the main menu will consist of pictures. They are also used for the wall textures in EGA FPS games like [[Catacomb 3-D]], in which case the wall textures come near the end of the picture list (starting from chunk 137 in [[Catacomb 3-D]]).

The number of picture chunks is given in chunk 0, the picture table.

=== Masked pictures (Masked bitmaps) ===

These follow Pictures. You need to know how many fonts there are, to know how what chunk number the first Masked picture is (3+NumFonts+numpics).

These are identical to the picture chunks in every respect, except being masked, they consist of five EGA planes, not four. Some games (E.g [[Catacomb 3-D]] make great use of masked pictures, but most games have only one or two. They need information from chunk 1, the masked picture table, to be displayed correctly.

The number of Masked pictures is given in Chunk 1.

=== Sprites ===

The first Sprite chunk is at 3+numfonts+numpics+numMaskedPics.

Sprites are exactly identical to masked pictures in format except the game cannot stretch or warp them. Most games use these for enemy, player or item graphics during gameplay. They need information from chunk 2, the sprite table both to display correctly and to interact correctly, something more complex than masked pictures.

There are usually several hundred sprite chunks, but [[Catacomb 3-D]] only has 3 sprite chunks and they are used for the PaddleWar game (Skulls and Bones). The number of sprite chunks is given in chunk 2.

=== 8x8 tiles ===

8x8 tiles are used by most games in status windows or foe the borders of message windows in-game. (And occasionally by TED5 to display levels.) There are thus not many of them. ALL the masked or unmasked tiles are one single chunk stored as four and five plane [[Raw EGA data]] respectively. The number of 8x8 unmasked and masked tiles is hard-coded into the executable, but can be worked out by dividing the decompressed chunk size by 32 and 40 (The size of one tile's data) respectively.

=== 16x16 and 32x32 tiles ===

32x32 tiles are optional and rarely used. 16x16 tiles are only occasionally absent and for most games make up the bulk of graphics. There are usually several thousand entries. Both come in masked and unmasked kinds, just like 8x8 tiles.

These chunks have notable differences. Each tile is an individual chunk and stored as four or five plane [[Raw EGA data]] with a plane size of 128 (16x16) or 512 (32x32). These chunks do NOT have a dword specifying their decompressed size as this is hard-coded into the executable as a space saving measure. (As is the start and finish of unmasked and masked tile chunks.) This can cause problems for editing programs.

Tiles make up the bulk of 2D game levels but are seldom seen elsewhere.

=== Misc graphics ===

Sometimes following tile graphics are miscellaneous graphics, that cannot be handled by the other chunk types. For example, Keen 4-6 has two misc graphics files used for the 'COMMANDER KEEN terminator text' intro. These graphics usually have unique formats that fit their function and few have been investigated.

==== Keen 4-6 Intro Bitmaps ====

This is the text that displays after the 'Ready, press any key' screen at Keen startup. It is composed of a monochrome bitmap that is scrolled across the screen and distorted for special effects. When displayed it is transparent, with a special palette so it is not black-and-white. It consists of a header followed by RLE compressed monochrome data.

HEADER:
0 2 Img height Height of the image in pixels
2 2 Img width Width of the image in pixels
4 2x Line point Pointers to line 1,2,3..etc of data. There will be [Img height] of
these, each 2 bytes long. The first pointer will have the value
(2 * [Img height] + 4)
+2 ? RLE data RLE-WM compressed data

DATA:
0 2 Black run Number of black pixels to write
2 2 Not-blk run Number of not-black pixels to write
4 2 Black run....
...
..
.
? 2 End $FFFF; end of row.

=== Game texts ===

Also known as ANSII chunks, these are used by the game for things like help screens, and have their own format. In the main they are simply text documents, interspersed with various commands to make things happen. Each file is divided up into a number of 'pages' which are moved between by pressing the up/down arrows. Pages can also have action sequences (Repeated each time the page is moved to, you cannot leave a page until the sequence finishes.)

^P First command in every file. Defines a page start
^E Ends the file
^Cx Change font color to $x until next page or ^C command
^Gx,y,z Display (unmasked) picture chunk z at location x,y (In pixels)
^Tx,y,z,t Display picture chunk z at x,y for z clicks of time
^Bx,y,z,t,b ?
^Lx,y ?

=== Demo files ===

These files, which can be recorded in several games using the 'demo cheat' consist of a series of commands that are played back when a demo is run ingame. (The game is also 'derandomized' during recording so all demo playbacks will be predictable.)

The format is quite simple; consisting of two words and a number of byte pairs. The first two bytes store the number of the level to load for the demo, the next two store the length of data to load\play (After this limit is reached the demo will end, whether or not there is any more data to read.) The remaining byte pairs each encode a time and a keypress. The following values are known:

01 Left
04 Up
05 Nothing
06 Down
09 Right
15 Ctrl
25 Alt

=== Misc files ===

The last few chunks are demo files and occasionally miscellaneous data. Demo file formats are currently unknown but can be recorded using the demo cheat. They contain the level number and difficulty followed by a series of key commands.

== Utilities ==

* [[KeenWiki:ModKeen|ModKeen]] (DOS) and [[KeenWiki:LModKeen|LModKeen]] (Linux/Windows) can be used to modify graphics and text stored in EGAGRAPH.CKx for the Commander Keen [[KeenWiki:Goodbye Galaxy|Goodbye Galaxy]] trilogy.
* WDC (Windows) can be used to view or modify the graphics and text stored in EGAGRAPH for [[Catacomb 3-D]] and [[Catacomb Abyss]].

File:EGAGraph Format.png

2017-06-17T06:35:07Z

Levellass: Commander Keen 5 masked tileset in EGAGraph format.

[[Commander Keen]] 5 masked tileset in EGAGraph format.

EGAGraph Format

2017-06-17T06:12:11Z

Levellass: Start demo format edit

{{Stub}}
{{Tileset Infobox
| Hardware1 = VGA
| Palette = External
| Names = N
| HasTransparency = Y
| Metadata = None
| Subtilesets = N
| Compressed = Y
| Hidden = N
| Games =
{{Game|Catacomb 3-D}}
{{Game|Catacomb Abyss}}
{{Game|Commander Keen 4-6}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 3}}
}}

'''EGAGraph''', short for 'EGA graphics library' is the format used to store graphics, demos, fonts, game texts and more in many early [[:Category:Id Software|id Software]] games.

The basic format is that of a number of [[Huffman Compression]] compressed sub-files (Chunks) stored in a similar manner to the [[AudioT Format]]. Like this format it has three main files, <tt>EGAGRAPH</tt>, <tt>EGAHEAD</tt>and <tt>EGADICT</tt>.

It is notable that while the <tt>EGAHEAD</tt> and <tt>EGADICT</tt> are stored in the game executable, they need to be extracted for [[TED5]] to edit levels.

This article may contain errors as some formats have not been worked out completely.

== EGA Head (EGAHEAD.xxx) ==

There are two versions of this format. The first version, used in [[Commander Keen Dreams]], [[Dangerous Dave 3]] and [[Dangerous Dave 4]], is an array of 4-byte little-endian values. The second version, used in all later EGA games, is an array of 3-byte unsigned little-endian values.

This header file may be present as an external file (eg. [[Bio Menace]]), or it may be included in the EXE file (eg. [[Catacomb 3-D]]). The last entry in the header is always the size of the EGAGRAPH.xxx file, and the first entry in the header is always 00 00 00. To find the end, you can search for filesize(EGAGRAPH.xxx) as a 3-byte (little-endian) value in the EXE. Then to find the start, go back 3 bytes at a time until you get to 00 000 00. Or use the fact that entries always get smaller as you go back, unless the entry is $FFFFFF.

In [[Catacomb 3-D]] v1.00 <tt>EGAHEAD.C3D</tt> is at $1BFD0 from the start of the decompressed ([[unlzexe]]) EXE file, and is 1437 bytes long, or 479 3-byte entries (for 478 chunks). It is then followed by 3 zero bytes (padding to multiple of 16?) 00 00 00, then the <tt>MAPHEAD.C3D</tt>.

In [[Catacomb Abyss]] v1.13 <tt>EGAHEAD.ABS</tt> is at $1BDB0 from the start of the decompressed ([[unlzexe]]) EXE file, and 1881 bytes long and has 626 chunks.

In [[Catacomb Apocalypse]] v1.00b <tt>EGAHEAD.APC</tt> is at $1E270 from the start of the decompressed ([[unlzexe]]) EXE file, and 2049 bytes long and has 682 chunks.

This header file stores the offsets (relative to the start of the <tt>EGAGRAPH</tt> file) for each sub file. The format is trivial, in that the header file is simply an array of 3 or 4 byte variables. (Each variable is a "slot", as the game refers to files by index.) Most games use the more compact 3-byte variables, since the <tt>EGAGRAPH</tt> file is never larger than $FFFFFF. However games based on older engines, notably [[Commander Keen Dreams]], [[Dangerous Dave 3]] and [[Dangerous Dave 4]], use 4-byte vales as these are easier to deal with.

It is important to note that not every 'slot' will be in use. Tiles especially if blank (All black) will be considered 'empty' and not worth adding to the file. (A blank 16x16 tile takes up 12 bytes of space if compressed, and there can be hundreds.) There are two ways of dealing with this; by default the games set all empty slot headers to -1, but many programs compress the graphics anyway and use a normal header value for them.

The last offset in the file will be an offset to the end of the main <tt>EGAGRAPH</tt> file. (So this should be ignored when reading the file to prevent a zero-byte file appearing last.) The total size of the <tt>EGAHEAD</tt> divided by 3 (Or 4) will also give the number of 'slots' the game uses. This varies, but is usually about 10,000.

Unlike [[AudioT Format]] files, <tt>EGAGRAPH</tt> is always compressed. However the header and dictionary may be external (E.g [[Bio Menace]])

== Dictionary (EGADICT.xxx) ==

The same [[Huffman Compression]] scheme used elsewhere in the [[Commander Keen]] series is used. When reading compressed chunks out of the <tt>EGAGRAPH</tt> file, the first four bytes located at the <tt>EGAHEAD</tt> offset are a UINT32LE specifying the file's decompressed size (which is required for the decompression algorithm.) The compressed data then follows, EXCEPT for 16x16 masked and unmasked tiles. Since these all have a similar decompressed size (128 bytes for unmasked, 256 bytes for masked) it is a waste of space to include these (Since tiles make up the bulk of graphics slots.) The decompressed size is hard coded, as are the start and finish of the unmasked and masked tile slots.

Note that the <tt>EGADICT</tt> file is not often obvious, usually being embedded in the main exe file. It is possible to locate it by looking for the string <tt>$FD $01 $00 $00 $00 $00</tt>, which appears at the end of nearly all Huffman dictionaries. They are the last 6 bytes out of 1024 (256*2*2), so add 6 and subtract 1024 to get the start (pointer to the head node).

Executables usually contain two or more dictionaries, but the <tt>EGADICT</tt> is usually '''the second one''', except in the case of early games like Keen Dreams, where it is the first of THREE. (A simple check of whether it decompresses the data sensibly works.)

In [[Catacomb 3-D]] <tt>EGADICT.C3D</tt> is at offset $24464 from the start of the decompressed CAT3D.EXE, which is the second Huffman dictionary and comes immediately after the first Huffman Dictionary.

In [[Catacomb Abyss]] v1.13 <tt>EGADICT.ABS</tt> is at offset $2734C from the start of the decompressed CATABYSS.EXE, which is the second Huffman dictionary.

In [[Catacomb Apocalypse]] v1.00b <tt>EGADICT.APC</tt> is at offset $26B24 from the start of the decompressed CATAPOC.EXE, which is the second Huffman dictionary.

== Main file (EGAGRAPH.xxx) ==

This file is simply an array of data files. Each file starts at the offset specified in the <tt>EGAHEAD</tt> file, and as there are no filenames each file is referred to by its index/slot number. Slots containing dummy values in the header are treated as if they don't exist in the <tt>EGAGRAPH</tt> file. Each file within the <tt>EGAGRAPH</tt> file is individually compressed. A file can be read by opening the <tt>EGAGRAPH</tt> file, seeking to the offset specified in the <tt>EGAHEAD</tt> file, reading a UINT32LE for the decompressed file size, and then decompressing the data from that point onwards using standard Huffman decompression techniques.

Note that in early games such as Keen Dreams, the <tt>EGAGRAPH</tt> file may have another name. (Such as <tt>KDREAM.EGA</tt> in that case.) in which case it is always the largest non-executable file.

=== Chunks ===

Each sub file or chunk is a separate graphic, ordered in the <tt>EGAGRAPH</tt> file in a specific way, much again like the [[AudioT Format]]. Chunks are labeled starting at 0. The game executable is hard coded for the start and finish of various chunk types. For example, Keen 4 has chunks 124-520 as sprites and will treat any chunk between these two numbers as a sprite. (Note that the game refers to chunk number, not sprite number.) The usual order of chunks is:

Picture table
Masked picture table
Sprite table
Fonts
Pictures (Unmasked bitmaps)
Masked pictures
8x8 unmasked tiles (Single chunk)
8x8 masked tiles (Single chunk)
16x16 unmasked tiles
16x16 masked tiles
32x32 unmasked tiles (Optional)
32x32 masked tiles (Optional)
Misc graphics (Optional)
Game texts
Demo files (Optional)
Misc data (Optional)

== Chunk formats ==

When compressed each chunk consists of a dword giving the decompressed size followed by the compressed data.

=== Picture table ===

Always present and always the first chunk, the picture table is 4 * numpics bytes long, consisting of two words for each picture (Width\8, Height) used when displaying picture chunks.

Divide the decompressed size by 4 to get numpics.

=== Masked picture table ===

Always present and always the second chunk, the picture table is 4 * numpics bytes long, consisting of two words for each picture (Width\8, Height) used when displaying masked picture chunks. This table is often quite small.

=== Sprite table ===

Always present and always the third chunk, the picture table is 16 * numspr bytes long, consisting of eight words for each sprite image (Width\8, Height, x offset, y offset and clipping rectangle left, top, right and bottom; all in that order.) used when displaying sprite chunks. This is what Modkeen exports as its notoriously hard to use xSPRITES.txt file.

=== Fonts ===

Always present and always starting at the fourth chunk. (Chunk 3!) Each chunk is a single monochrome font, containing all the entries from 0-255 for that font. Each 'letter' is stored separately and consecutively. A game will have at least one, and usually 3 fonts. The format is version two of [[EGA Font format]]

Fonts are used in the game for game texts. They can be stretched or colored and are always transparent, meaning they look strange when not over a single-color background.

=== Pictures (Bitmaps) ===

These follow game fonts. You need to know how many fonts there are before it to know how what chunk number the first picture is (3+NumFonts). In [[Catacomb 3-D]] there are 2 fonts.

Bitmaps are stored as standard [[Raw EGA data]], the size of each plane being the decompressed chunk size \ 4. In order to be displayed properly these need information from chunk 0, the picture table. Note that unlike fonts, data does not wrap, so a 4x4 sprite will consist of four planes of four bytes in size, the same as an 8x4 sprite.

Pictures are used for things such as title screens or pictures in game texts. Most of the main menu will consist of pictures. They are also used for the wall textures in EGA FPS games like [[Catacomb 3-D]], in which case the wall textures come near the end of the picture list (starting from chunk 137 in [[Catacomb 3-D]]).

The number of picture chunks is given in chunk 0, the picture table.

=== Masked pictures (Masked bitmaps) ===

These follow Pictures. You need to know how many fonts there are, to know how what chunk number the first Masked picture is (3+NumFonts+numpics).

These are identical to the picture chunks in every respect, except being masked, they consist of five EGA planes, not four. Some games (E.g [[Catacomb 3-D]] make great use of masked pictures, but most games have only one or two. They need information from chunk 1, the masked picture table, to be displayed correctly.

The number of Masked pictures is given in Chunk 1.

=== Sprites ===

The first Sprite chunk is at 3+numfonts+numpics+numMaskedPics.

Sprites are exactly identical to masked pictures in format except the game cannot stretch or warp them. Most games use these for enemy, player or item graphics during gameplay. They need information from chunk 2, the sprite table both to display correctly and to interact correctly, something more complex than masked pictures.

There are usually several hundred sprite chunks, but [[Catacomb 3-D]] only has 3 sprite chunks and they are used for the PaddleWar game (Skulls and Bones). The number of sprite chunks is given in chunk 2.

=== 8x8 tiles ===

8x8 tiles are used by most games in status windows or foe the borders of message windows in-game. (And occasionally by TED5 to display levels.) There are thus not many of them. ALL the masked or unmasked tiles are one single chunk stored as four and five plane [[Raw EGA data]] respectively. The number of 8x8 unmasked and masked tiles is hard-coded into the executable, but can be worked out by dividing the decompressed chunk size by 32 and 40 (The size of one tile's data) respectively.

=== 16x16 and 32x32 tiles ===

32x32 tiles are optional and rarely used. 16x16 tiles are only occasionally absent and for most games make up the bulk of graphics. There are usually several thousand entries. Both come in masked and unmasked kinds, just like 8x8 tiles.

These chunks have notable differences. Each tile is an individual chunk and stored as four or five plane [[Raw EGA data]] with a plane size of 128 (16x16) or 512 (32x32). These chunks do NOT have a dword specifying their decompressed size as this is hard-coded into the executable as a space saving measure. (As is the start and finish of unmasked and masked tile chunks.) This can cause problems for editing programs.

Tiles make up the bulk of 2D game levels but are seldom seen elsewhere.

=== Misc graphics ===

Sometimes following tile graphics are miscellaneous graphics, that cannot be handled by the other chunk types. For example, Keen 4-6 has two misc graphics files used for the 'COMMANDER KEEN terminator text' intro. These graphics usually have unique formats that fit their function and few have been investigated.

==== Keen 4-6 Intro Bitmaps ====

This is the text that displays after the 'Ready, press any key' screen at Keen startup. It is composed of a monochrome bitmap that is scrolled across the screen and distorted for special effects. When displayed it is transparent, with a special palette so it is not black-and-white. It consists of a header followed by RLE compressed monochrome data.

HEADER:
0 2 Img height Height of the image in pixels
2 2 Img width Width of the image in pixels
4 2x Line point Pointers to line 1,2,3..etc of data. There will be [Img height] of
these, each 2 bytes long. The first pointer will have the value
(2 * [Img height] + 4)
+2 ? RLE data RLE-WM compressed data

DATA:
0 2 Black run Number of black pixels to write
2 2 Not-blk run Number of not-black pixels to write
4 2 Black run....
...
..
.
? 2 End $FFFF; end of row.

=== Game texts ===

Also known as ANSII chunks, these are used by the game for things like help screens, and have their own format. In the main they are simply text documents, interspersed with various commands to make things happen. Each file is divided up into a number of 'pages' which are moved between by pressing the up/down arrows. Pages can also have action sequences (Repeated each time the page is moved to, you cannot leave a page until the sequence finishes.)

^P First command in every file. Defines a page start
^E Ends the file
^Cx Change font color to $x until next page or ^C command
^Gx,y,z Display (unmasked) picture chunk z at location x,y (In pixels)
^Tx,y,z,t Display picture chunk z at x,y for z clicks of time
^Bx,y,z,t,b ?
^Lx,y ?

=== Demo files ===

These files, which can be recorded in several games using the 'demo cheat' consist of a series of commands that are played back when a demo is run ingame. (The game is also 'derandomized' during recording so all demo playbacks will be predictable.)

The format is quite simple; consisting of two words and a number of byte pairs. The first two bytes store the number of the level to load for the demo, the next two store the length of data to load\play (After this limit is reached the demo will end, whether or not there is any more data to read.) The remaining byte pairs each encode a time and a keypress. The following values are known:

01 Left
04 Up
05 Nothing
06 Down
09 Right
15 Ctrl

=== Misc files ===

The last few chunks are demo files and occasionally miscellaneous data. Demo file formats are currently unknown but can be recorded using the demo cheat. They contain the level number and difficulty followed by a series of key commands.

== Utilities ==

* [[KeenWiki:ModKeen|ModKeen]] (DOS) and [[KeenWiki:LModKeen|LModKeen]] (Linux/Windows) can be used to modify graphics and text stored in EGAGRAPH.CKx for the Commander Keen [[KeenWiki:Goodbye Galaxy|Goodbye Galaxy]] trilogy.
* WDC (Windows) can be used to view or modify the graphics and text stored in EGAGRAPH for [[Catacomb 3-D]] and [[Catacomb Abyss]].

File:GameMaps Format.png

2017-03-11T07:59:34Z

Levellass: A [[Commander Keen] 4 level built using the GAMEMAPS format.

A [[Commander Keen] 4 level built using the GAMEMAPS format.

Huffman Compression

2016-05-24T10:09:22Z

Levellass: Rewrite complete

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte in, 1-bit out
| Games =
{{Game|The Blues Brothers}}
{{Game|Catacomb 3-D}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 2}}
}}

[[Huffman Compression]] is a compression algorithm used in many classic games. It is about as efficient as LZW or RLE compression, with many games using the three formats simultaneously.

Huffman compression involves changing how various characters are stored. Normally all characters in a given segment of data are equal and take an equal amount of space to store. However by making more common characters take up less space while allowing less commonly used characters to take up more the overall size of a segment of data can be reduced. Any Huffman compressed data will thus be associated with a dictionary file (internal or external) used to decompress it. This page will go through each aspect of Huffman compression in a stepwise manner before presenting some examples of usage and source code.

==Frequency tables==

To illustrate the various aspects of Huffman compression the example text "She sells seashells by the sea shore." will be Huffman compressed and the processes and outputs shown in various sections on this page.

In order to compress data using Huffman compression the compressor must first build a 'frequency table' of all the elements it wishes to compress. In most cases this will be the 256 values a single byte can take, though it need not be limited to this. (Due to the binary nature of the compression method, sets of elements that match powers of 2 are both easiest and most efficient to compress.) The data is scanned and each occurrence of a given value. Taking the letters in our example sentence we can construct the following frequency table:

<pre>
Char Freq
's' 7
'e' 7
' ' 6
'h' 4
'l' 4
'a' 2
'S' 1
'b' 1
'o' 1
'r' 1
't' 1
'y' 1
'.' 1
</pre>

==The Binary Tree==

The binary tree is core to how Huffman compression compresses data. This is done by constructing a 'binary tree', so named because of its branching structure. Each branching point or 'node' has two options, 'left' and 'right' which lead either to another node or a character. The tree is constructed so that every character can be placed upon it and every path ends in a character.

This is done by first building a point of origin, 'root node' and the adding further nodes from there. Using our example we can build the following binary tree simply by listing the nodes alphabetically (and using '_' to stand in for the space for clarity):

<pre>
[Root]
____|_______
/ \
__|__ |
/ \ / \
| | | .
/ \ / \ / \
| | | | | |
/ \ / \ / \ / \ / \ / \
_ S a b e h l o r s t y
</pre>

On this tree we can use 'L' to specify a left path and 'R' to specify a right. As such the letter 'a' is represented by 'LLRL' and 'y' by 'RLRR'. Note that since the number of different characters is not a power of two (E.g. 16) not all paths from the root to a character are the same length, one is considerably shorter. The '.' character is represented by simply 'RR'

Assuming that 'R' and 'L' are '0' and '1' each 8-bit character in the original text can be represented by just 4 bits on average, halving the message length. This is far from optimal however and there is a specific procedure used to construct an optimal tree for the shortest message length. To do this advantage is taken of the fact that paths can be different lengths. If one set of paths is made a bit shorter at the expense of making a smaller set of paths a bit longer then the overall message will be made shorter.

===Constructing an optimal tree===

The first step in creating an optimal tree again is to create a 'root node'. To populate its two options the compressor repeatedly divides the frequency table. This is done by starting with the most common character and seeing if it contains more occurrences than the rest of the table combined. If not then the second most common character is added and so on.

In our example there are a total of 37 characters. Three characters make up more than half of this, 's', 'e' and ' '. Because of the binary structure of the tree however ''four'' options are needed here so 'h' is also included. All of these characters are placed on the left option of the root node while the remaining characters are placed on the right.

The next step creates a new node with left and right options and repeats the process. The two most common characters of the four, 's' and 'e' go to the left branch of this new node. A third node is created and, now that there are only two options, each is given a branch. The tree now looks like this:

<pre>
[Root]
/ \
| l, a, etc
/ \
| _, h
/ \
s e
</pre>

Now the character 's' can be represented as LLL and 'e' as LLR.

The compressor now moves 'up' to the previous node which still has a branch with more than one option in it. Another node is created and, since there are only two options, one is assigned to each branch. Te compressor then returns to the root node to deal with the right half of the tree. When it has assigned very character to a node the following optimal tree is produced:

<pre>
___[Root]____
/ \
_|_ ___|_______
/ \ / \
| | | |
/ \ / \ / \ / \
s e _ h l | | |
/ \ / \ / \
a | o r t |
/ \ / \
S b y .
</pre>

Notice that 4 characters now have paths that are just 3 choices long while 4 have paths 4 choices long and 4 have paths 5 choices long. Overall the average path length is the same as our previous tree. However 24 occurrences are one choice shorter, 5 are identical, 3 are one choice longer and '.' is three choices longer. This gives us a compressed message that is a total of 18 choices (or bits) shorter.

===Labeling the tree===

Now that a tree has been constructed it needs to be labelled in some form so that it can be stored as data either in the decompressor or to be sent with the compressed code. There are two major issues, what system to use when assigning numbers to the various nodes, and what bit value, 0 or 1, to assign to left or right options.

The most common (but far from unique) system is to label nodes from the 'bottom' of the tree to the top, going left-to-right across each 'layer' of the tree. (In our example the node that leads to 'S' and 'b' would thus be the first numbered node.) Nodes are usually numbered starting with 0 and ending with the root node having the highest number. Our tree would be numbered as follows using this system:

<pre>
____[11]_____
/ \
[9] __[10]_____
/ \ / \
[5] [6] [7] [8]
/ \ / \ / \ / \
s e _ h l [2] [3] [4]
/ \ / \ / \
a [0] o r t[1]
/ \ / \
S b y .
</pre>

Usually the left branch is given a bit value of 0 and the right branch a bit value of 1. Using this scheme 's' in our example resides on node 1 and is represented by the bit string '000' The complete compressed message in bit form is now <tt>10110 011 001 010 000 001 100 100 000 010 000 001 1010 000 011 001 100 100 000 010 10111 11110 010 1110 011 001 010 000 001 1010 010 000 011 1100 1101 001 11111</tt> or in bytes <tt>$B3 $28 $19 $02 $06 $83 $32 $05 $7F $2E $65 $03 $48 $3C $D3 $F0</tt> (The final byte is padded with nul bits.) This is a total of 16 bytes used for a 37 byte message.

===Standard tree size===

The most common implementation of Huffman compression is '1 byte in, 1 bit out'. This involves compressing one byte of data at a time and converting it into a bitstream. In this case the compressor expects to find 256 different possible values of data. This requires a tree with 255 nodes, including the root, and an average path length of 8 choices.

This is not the only possibility however and Huffman can compress data in words or dwords or in more exotic manners. {{Game|Commander Keen Dreams}} for example combines Huffman with LZW compression, building a binary tree of a fixed size and filling it with the most recently encountered strings of bits.

==The dictionary==

Often the binary tree must be stored in some form, usually called a ''dictionary''. This will either be fixed and known by both the compressor and decompressor. (Which minimizes individual message sizes but can limit compression efficiency overall.) or tailored for each message and sent with said message.

Dictionary format is quite standard. It is merely a numerical list of nodes (however they have been labelled.) starting with node 0 and ending with the root. Each node usually taking up four bytes, two bytes per branch. Each branch will have one byte dedicated to identifying if it leads to another node or a character and the other byte identifying the node or character. Usually '0' identifies the option asleading to a character and '1' to another node, but again this can be reversed.

Using this system, our example tree could be stored as either of the two following:

0S0b 0y0. 0a10 0o0r 0t11 0s0e 0_0h 0l12 1314 1516 1718 19110

$00 $53 $00 $62 $00 $79 $00 $2E $00 $6F $00 $72 $00 $74 $01 $01 $00 $73 $00 $65 $00 $20 $00 $68...
- S - b - y - . - o - r - t | n1 - s - e - _ - h ...
(node 0) (node 1) (node 3) (node 4) (node 5) (node 6) ...

The dictionary is thus usually 1020 bytes long, containing 255 nodes of 4 bytes each, though again this can vary depending on how readable the dictionary is to humans and whether or not the dictionary itself is compressed.

==Huffman implementation in ID Software games==

Games created by Id Software have a shared but distinct implementation of Huffman compression.

In older games such as {{Game|Dangerous Dave 2}} the dictionary and data are included together in one file. First is a four-byte header,, 'HUFF' followed by four bytes that give the decompressed size of the data (for memory purposes.). Following that is the dictionary, 1020 bytes in length then the compressed data.

In newer games (such as [[Commander Keen 4-6]] or [[Wolfenstein 3-D]]) the data is stored in an external file which consists of a number of concatenated 'chunks', each chunk beginning with a dword giving its decompressed size (again for memory purposes.). These chunks are addressed by an internal or external 'header' file consisting of a series of three (or sometimes four) byte offsets to the start of various chunks in the data file. (The end of the header is easily found as the last entry is the length of the data file.) The dictionary is 1024 bytes long and stored in the executable.

The dictionary consists of 255 nodes (in newr games plus four null bytes of padding) and there are two or three dictionaries stored in the executable depending on the game. The end of these dictionaries can be found by looking for node 255 (number 254!) which universally consists of the string <tt>$00 $00 $FD $01</tt> due to the fact that the byte <tt>$00</tt> is the single most common character in game data and thus always occupies the left branch of the root node while the other branch must go to the next lowest node, number 253.

An important but subtle difference is how data is read. While bytes are read sequentially (1, 2, 3...) bits within each byte are read in reverse order (8, 7, 6...). (Technically each byte is little endian.)

===Trivial ID dictionary===

The following is a complete 'trivial' dictionary. This dictionary is constructed such that data compressed with it is not altered in any way, the output and input are the same. When used to construct a binary tree all paths are of equal length, 8 choices or bits. And the nodes are arranged in a logical order with an easily seen pattern; the first half of the tree consists of terminal nodes, the second half of branch nodes. (Of the second half the first half of ''that'' consists of branch nodes that lead to terminal nodes while the second half consists of branch nodes to two branch nodes and so on.)

$00 $00 $80 $00 $40 $00 $C0 $00 $20 $00 $A0 $00 $60 $00 $E0 $00
$10 $00 $90 $00 $50 $00 $D0 $00 $30 $00 $B0 $00 $70 $00 $F0 $00
$08 $00 $88 $00 $48 $00 $C8 $00 $28 $00 $A8 $00 $68 $00 $E8 $00
$18 $00 $98 $00 $58 $00 $D8 $00 $38 $00 $B8 $00 $78 $00 $F8 $00
$04 $00 $84 $00 $44 $00 $C4 $00 $24 $00 $A4 $00 $64 $00 $E4 $00
$14 $00 $94 $00 $54 $00 $D4 $00 $34 $00 $B4 $00 $74 $00 $F4 $00
$0C $00 $8C $00 $4C $00 $CC $00 $2C $00 $AC $00 $6C $00 $EC $00
$1C $00 $9C $00 $5C $00 $DC $00 $3C $00 $BC $00 $7C $00 $FC $00
$02 $00 $82 $00 $42 $00 $C2 $00 $22 $00 $A2 $00 $62 $00 $E2 $00
$12 $00 $92 $00 $52 $00 $D2 $00 $32 $00 $B2 $00 $72 $00 $F2 $00
$0A $00 $8A $00 $4A $00 $CA $00 $2A $00 $AA $00 $6A $00 $EA $00
$1A $00 $9A $00 $5A $00 $DA $00 $3A $00 $BA $00 $7A $00 $FA $00
$06 $00 $86 $00 $46 $00 $C6 $00 $26 $00 $A6 $00 $66 $00 $E6 $00
$16 $00 $96 $00 $56 $00 $D6 $00 $36 $00 $B6 $00 $76 $00 $F6 $00
$0E $00 $8E $00 $4E $00 $CE $00 $2E $00 $AE $00 $6E $00 $EE $00
$1E $00 $9E $00 $5E $00 $DE $00 $3E $00 $BE $00 $7E $00 $FE $00
$01 $00 $81 $00 $41 $00 $C1 $00 $21 $00 $A1 $00 $61 $00 $E1 $00
$11 $00 $91 $00 $51 $00 $D1 $00 $31 $00 $B1 $00 $71 $00 $F1 $00
$09 $00 $89 $00 $49 $00 $C9 $00 $29 $00 $A9 $00 $69 $00 $E9 $00
$19 $00 $99 $00 $59 $00 $D9 $00 $39 $00 $B9 $00 $79 $00 $F9 $00
$05 $00 $85 $00 $45 $00 $C5 $00 $25 $00 $A5 $00 $65 $00 $E5 $00
$15 $00 $95 $00 $55 $00 $D5 $00 $35 $00 $B5 $00 $75 $00 $F5 $00
$0D $00 $8D $00 $4D $00 $CD $00 $2D $00 $AD $00 $6D $00 $ED $00
$1D $00 $9D $00 $5D $00 $DD $00 $3D $00 $BD $00 $7D $00 $FD $00
$03 $00 $83 $00 $43 $00 $C3 $00 $23 $00 $A3 $00 $63 $00 $E3 $00
$13 $00 $93 $00 $53 $00 $D3 $00 $33 $00 $B3 $00 $73 $00 $F3 $00
$0B $00 $8B $00 $4B $00 $CB $00 $2B $00 $AB $00 $6B $00 $EB $00
$1B $00 $9B $00 $5B $00 $DB $00 $3B $00 $BB $00 $7B $00 $FB $00
$07 $00 $87 $00 $47 $00 $C7 $00 $27 $00 $A7 $00 $67 $00 $E7 $00
$17 $00 $97 $00 $57 $00 $D7 $00 $37 $00 $B7 $00 $77 $00 $F7 $00
$0F $00 $8F $00 $4F $00 $CF $00 $2F $00 $AF $00 $6F $00 $EF $00
$1F $00 $9F $00 $5F $00 $DF $00 $3F $00 $BF $00 $7F $00 $FF $00
$00 $01 $01 $01 $02 $01 $03 $01 $04 $01 $05 $01 $06 $01 $07 $01
$08 $01 $09 $01 $0A $01 $0B $01 $0C $01 $0D $01 $0E $01 $0F $01
$10 $01 $11 $01 $12 $01 $13 $01 $14 $01 $15 $01 $16 $01 $17 $01
$18 $01 $19 $01 $1A $01 $1B $01 $1C $01 $1D $01 $1E $01 $1F $01
$20 $01 $21 $01 $22 $01 $23 $01 $24 $01 $25 $01 $26 $01 $27 $01
$28 $01 $29 $01 $2A $01 $2B $01 $2C $01 $2D $01 $2E $01 $2F $01
$30 $01 $31 $01 $32 $01 $33 $01 $34 $01 $35 $01 $36 $01 $37 $01
$38 $01 $39 $01 $3A $01 $3B $01 $3C $01 $3D $01 $3E $01 $3F $01
$40 $01 $41 $01 $42 $01 $43 $01 $44 $01 $45 $01 $46 $01 $47 $01
$48 $01 $49 $01 $4A $01 $4B $01 $4C $01 $4D $01 $4E $01 $4F $01
$50 $01 $51 $01 $52 $01 $53 $01 $54 $01 $55 $01 $56 $01 $57 $01
$58 $01 $59 $01 $5A $01 $5B $01 $5C $01 $5D $01 $5E $01 $5F $01
$60 $01 $61 $01 $62 $01 $63 $01 $64 $01 $65 $01 $66 $01 $67 $01
$68 $01 $69 $01 $6A $01 $6B $01 $6C $01 $6D $01 $6E $01 $6F $01
$70 $01 $71 $01 $72 $01 $73 $01 $74 $01 $75 $01 $76 $01 $77 $01
$78 $01 $79 $01 $7A $01 $7B $01 $7C $01 $7D $01 $7E $01 $7F $01
$80 $01 $81 $01 $82 $01 $83 $01 $84 $01 $85 $01 $86 $01 $87 $01
$88 $01 $89 $01 $8A $01 $8B $01 $8C $01 $8D $01 $8E $01 $8F $01
$90 $01 $91 $01 $92 $01 $93 $01 $94 $01 $95 $01 $96 $01 $97 $01
$98 $01 $99 $01 $9A $01 $9B $01 $9C $01 $9D $01 $9E $01 $9F $01
$A0 $01 $A1 $01 $A2 $01 $A3 $01 $A4 $01 $A5 $01 $A6 $01 $A7 $01
$A8 $01 $A9 $01 $AA $01 $AB $01 $AC $01 $AD $01 $AE $01 $AF $01
$B0 $01 $B1 $01 $B2 $01 $B3 $01 $B4 $01 $B5 $01 $B6 $01 $B7 $01
$B8 $01 $B9 $01 $BA $01 $BB $01 $BC $01 $BD $01 $BE $01 $BF $01
$C0 $01 $C1 $01 $C2 $01 $C3 $01 $C4 $01 $C5 $01 $C6 $01 $C7 $01
$C8 $01 $C9 $01 $CA $01 $CB $01 $CC $01 $CD $01 $CE $01 $CF $01
$D0 $01 $D1 $01 $D2 $01 $D3 $01 $D4 $01 $D5 $01 $D6 $01 $D7 $01
$D8 $01 $D9 $01 $DA $01 $DB $01 $DC $01 $DD $01 $DE $01 $DF $01
$E0 $01 $E1 $01 $E2 $01 $E3 $01 $E4 $01 $E5 $01 $E6 $01 $E7 $01
$E8 $01 $E9 $01 $EA $01 $EB $01 $EC $01 $ED $01 $EE $01 $EF $01
$F0 $01 $F1 $01 $F2 $01 $F3 $01 $F4 $01 $F5 $01 $F6 $01 $F7 $01
$F8 $01 $F9 $01 $FA $01 $FB $01 $FC $01 $FD $01

Using this example we can see the unusual manner in which ID games read bits within bytes. As an example consider the character $80; in binary this is '10000000' However, following this path using the dictionary given above will output the character $01 (00000001). Instead the bits must be read in reverse order. Doing so will lead to the following nodes starting at the root node: 254(root) -> 252 -> 248 -> 240 -> 224 -> 192 -> 128 -> 0(terminal node for characters $00 and $80)

== Source code ==

Some example code is available in various languages showing how to decompress (and in some cases compress) files using the Huffman algorithm.

=== QuickBasic ===

<source lang="qbasic">
'
' 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

' Input filename, output filename
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
</source>

----

<source lang="qbasic">
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
</source>

=== Visual Basic .NET ===

==== Huffman tree representation ====

This class, BinaryTreeNode, represents a binary tree whose branch nodes carry no value, like a Huffman dictionary tree.
<source lang="vbnet">Public Class BinaryTreeNode(Of T)
' By Fleexy, public domain, credit where credit is due
Private Branch As Boolean
Private Children As BinaryTreeNode(Of T)()
Private HoldValue As T
Public Sub New(LeafValue As T)
Branch = False
HoldValue = LeafValue
End Sub
Public Sub New(LeftChild As BinaryTreeNode(Of T), RightChild As BinaryTreeNode(Of T))
Branch = True
Children = {LeftChild, RightChild}
End Sub
Public ReadOnly Property HasValue As Boolean
Get
Return Not Branch
End Get
End Property
Public Property Value As T
Get
If Branch Then Throw New InvalidOperationException
Return HoldValue
End Get
Set(value As T)
If Branch Then Throw New InvalidOperationException
HoldValue = value
End Set
End Property
Public Property Child(Side As ChildSide) As BinaryTreeNode(Of T)
Get
If Not Branch Then Throw New InvalidOperationException
Return Children(Side)
End Get
Set(value As BinaryTreeNode(Of T))
If Not Branch Then Throw New InvalidOperationException
Children(Side) = value
End Set
End Property
Public Enum ChildSide As Byte
Left = 0
Right = 1
End Enum
Public ReadOnly Property Count As Integer
Get
If Not Branch Then Return 1
Return Children(0).Count + Children(1).Count
End Get
End Property
Public ReadOnly Property Depth As Integer
Get
If Not Branch Then Return 1
Return Math.Max(Children(0).Depth, Children(1).Depth) + 1
End Get
End Property
Public Overrides Function ToString() As String
Return "{Count = " & Count & ", Depth = " & Depth & "}"
End Function
End Class</source>

==== Huffman tree reading ====

This piece of code will read in a stored Huffman dictionary in the format described at the top of this article and store it in a BinaryTreeNode(Of Byte) as shown above.
<source lang="vbnet"> ' By Fleexy, public domain, credit where credit is due
Dim fDict As New IO.FileStream(DictionaryFile, IO.FileMode.Open)
Dim raw(254) As Tuple(Of UShort, UShort)
For x = 0 To 254
raw(x) = Tuple.Create(ReadUShort(fDict), ReadUShort(fDict))
Next
fDict.Close()
Dim GenerateTree As Func(Of UShort, BinaryTreeNode(Of Byte))
GenerateTree = Function(NextNode As UShort) As BinaryTreeNode(Of Byte)
Dim n As Tuple(Of UShort, UShort) = raw(NextNode)
Dim a, b As BinaryTreeNode(Of Byte)
If n.Item1 < 256 Then
a = New BinaryTreeNode(Of Byte)(n.Item1)
Else
a = GenerateTree(n.Item1 - 256)
End If
If n.Item2 < 256 Then
b = New BinaryTreeNode(Of Byte)(n.Item2)
Else
b = GenerateTree(n.Item2 - 256)
End If
Return New BinaryTreeNode(Of Byte)(a, b)
End Function
Dim dict As BinaryTreeNode(Of Byte) = GenerateTree(254)
fDict.Close()</source>

[[Category:Code examples]]

Huffman Compression

2016-05-24T09:32:37Z

Levellass: More rewrite

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte in, 1-bit out
| Games =
{{Game|The Blues Brothers}}
{{Game|Catacomb 3-D}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 2}}
}}

[[Huffman Compression]] is a compression algorithm used in many classic games. It is about as efficient as LZW or RLE compression, with many games using the three formats simultaneously.

Huffman compression involves making/reading a ''dictionary'' of 256 entries, one for each possible 1-byte character. This is organised in the form of a ''binary tree'' which is basically formed by taking the two lowest frequency characters and combining them into a new entry with their added frequencies and repeating until all entries are reduced to one ''root node''. After the dictionary is created, every character of data is replaced with the corresponding bit representation from the tree.

Any Huffman compressed data will thus be associated with a dictionary file (internal or external) used to decompress it. This page will explain the various aspects of Huffman compression using the example text "She sells seashells by the sea shore."

==Frequency tables==

In order to compress data using Huffman compression the compressor must build a 'frequency table' of all the elements it wishes to compress. In most cases this will be the 256 values a single byte can take, though it need not be limited to this. (Due to the binary nature of the compression method, sets of elements that match powers of 2 are both easiest and most efficient to compress.) The data is scanned and each occurrence of a given value. Taking the letters in our example sentence we can construct the following frequency table:

<pre>
Char Freq
's' 7
'e' 7
' ' 6
'h' 4
'l' 4
'a' 2
'S' 1
'b' 1
'o' 1
'r' 1
't' 1
'y' 1
'.' 1
</pre>

==The Binary Tree==

The binary tree is core to how Huffman compression compresses data. This is done by constructing a 'binary tree', so named because of its branching structure. Each branching point or 'node' has two options, 'left' and 'right' which lead either to another node or a character. The tree is constructed so that every character can be placed upon it and every path ends in a character.

This is done by first building a point of origin, 'root node' and the adding further nodes from there. Using our example we can build the following binary tree simply by listing the nodes alphabetically (and using '_' to stand in for the space for clarity):

<pre>
[Root]
____|_______
/ \
__|__ |
/ \ / \
| | | .
/ \ / \ / \
| | | | | |
/ \ / \ / \ / \ / \ / \
_ S a b e h l o r s t y
</pre>

On this tree we can use 'L' to specify a left path and 'R' to specify a right. As such the letter 'a' is represented by 'LLRL' and 'y' by 'RLRR'. Note that since the number of different characters is not a power of two (E.g. 16) not all paths from the root to a character are the same length, one is considerably shorter. The '.' character is represented by simply 'RR'

Assuming that 'R' and 'L' are '0' and '1' each 8-bit character in the original text can be represented by just 4 bits on average, halving the message length. This is far from optimal however and there is a specific procedure used to construct an optimal tree for the shortest message length. To do this advantage is taken of the fact that paths can be different lengths. If one set of paths is made a bit shorter at the expense of making a smaller set of paths a bit longer then the overall message will be made shorter.

===Constructing an optimal tree===

The first step in creating an optimal tree again is to create a 'root node'. To populate its two options the compressor repeatedly divides the frequency table. This is done by starting with the most common character and seeing if it contains more occurrences than the rest of the table combined. If not then the second most common character is added and so on.

In our example there are a total of 37 characters. Three characters make up more than half of this, 's', 'e' and ' '. Because of the binary structure of the tree however ''four'' options are needed here so 'h' is also included. All of these characters are placed on the left option of the root node while the remaining characters are placed on the right.

The next step creates a new node with left and right options and repeats the process. The two most common characters of the four, 's' and 'e' go to the left branch of this new node. A third node is created and, now that there are only two options, each is given a branch. The tree now looks like this:

<pre>
[Root]
/ \
| l, a, etc
/ \
| _, h
/ \
s e
</pre>

Now the character 's' can be represented as LLL and 'e' as LLR.

The compressor now moves 'up' to the previous node which still has a branch with more than one option in it. Another node is created and, since there are only two options, one is assigned to each branch. Te compressor then returns to the root node to deal with the right half of the tree. When it has assigned very character to a node the following optimal tree is produced:

<pre>
___[Root]____
/ \
_|_ ___|_______
/ \ / \
| | | |
/ \ / \ / \ / \
s e _ h l | | |
/ \ / \ / \
a | o r t |
/ \ / \
S b y .
</pre>

Notice that 4 characters now have paths that are just 3 choices long while 4 have paths 4 choices long and 4 have paths 5 choices long. Overall the average path length is the same as our previous tree. However 24 occurrences are one choice shorter, 5 are identical, 3 are one choice longer and '.' is three choices longer. This gives us a compressed message that is a total of 18 choices (or bits) shorter.

===Labeling the tree===

Now that a tree has been constructed it needs to be labelled in some form so that it can be stored as data either in the decompressor or to be sent with the compressed code. There are two major issues, what system to use when assigning numbers to the various nodes, and what bit value, 0 or 1, to assign to left or right options.

The most common (but far from unique) system is to label nodes from the 'bottom' of the tree to the top, going left-to-right across each 'layer' of the tree. (In our example the node that leads to 'S' and 'b' would thus be the first numbered node.) Nodes are usually numbered starting with 0 and ending with the root node having the highest number. Our tree would be numbered as follows using this system:

<pre>
____[11]_____
/ \
[9] __[10]_____
/ \ / \
[5] [6] [7] [8]
/ \ / \ / \ / \
s e _ h l [2] [3] [4]
/ \ / \ / \
a [0] o r t[1]
/ \ / \
S b y .
</pre>

Usually the left branch is given a bit value of 0 and the right branch a bit value of 1. Using this scheme 's' in our example resides on node 1 and is represented by the bit string '000' The complete compressed message in bit form is now <tt>10110 011 001 010 000 001 100 100 000 010 000 001 1010 000 011 001 100 100 000 010 10111 11110 010 1110 011 001 010 000 001 1010 010 000 011 1100 1101 001 11111</tt> or in bytes <tt>$B3 $28 $19 $02 $06 $83 $32 $05 $7F $2E $65 $03 $48 $3C $D3 $F0</tt> (The final byte is padded with nul bits.) This is a total of 16 bytes used for a 37 byte message.

===Standard tree size===

The most common implementation of Huffman compression is '1 byte in, 1 bit out'. This involves compressing one byte of data at a time and converting it into a bitstream. In this case the compressor expects to find 256 different possible values of data. This requires a tree with 255 nodes, including the root, and an average path length of 8 choices.

This is not the only possibility however and Huffman can compress data in words or dwords or in more exotic manners. {{Game|Commander Keen Dreams}} for example combines Huffman with LZW compression, building a binary tree of a fixed size and filling it with the most recently encountered strings of bits.

==The dictionary==

Often the binary tree must be stored in some form, usually called a ''dictionary''. This will either be fixed and known by both the compressor and decompressor. (Which minimizes individual message sizes but can limit compression efficiency overall.) or tailored for each message and sent with said message.

Dictionary format is quite standard. It is merely a numerical list of nodes (however they have been labelled.) starting with node 0 and ending with the root. Each node usually taking up four bytes, two bytes per branch. Each branch will have one byte dedicated to identifying if it leads to another node or a character and the other byte identifying the node or character. Usually '0' identifies the option asleading to a character and '1' to another node, but again this can be reversed.

Using this system, our example tree could be stored as either of the two following:

0S0b 0y0. 0a10 0o0r 0t11 0s0e 0_0h 0l12 1314 1516 1718 19110

$00 $53 $00 $62 $00 $79 $00 $2E $00 $6F $00 $72 $00 $74 $01 $01 $00 $73 $00 $65 $00 $20 $00 $68...
- S - b - y - . - o - r - t | n1 - s - e - _ - h ...
(node 0) (node 1) (node 3) (node 4) (node 5) (node 6) ...

The dictionary is thus usually 1020 bytes long, containing 255 nodes of 4 bytes each, though again this can vary depending on how readable the dictionary is to humans and whether or not the dictionary itself is compressed.

==Huffman implementation in ID Software games==

Games created by Id Software have a shared but distinct implementation of Huffman compression.

In older games such as {{Game|Dangerous Dave 2}} the dictionary and data are included together in one file. First is a four-byte header,, 'HUFF' followed by four bytes that give the decompressed size of the data (for memory purposes.). Following that is the dictionary, 1020 bytes in length then the compressed data.

In newer games (such as [[Commander Keen 4-6]] or [[Wolfenstein 3-D]]) the data is stored in an external file which consists of a number of concatenated 'chunks', each chunk beginning with a dword giving its decompressed size (again for memory purposes.). These chunks are addressed by an internal or external 'header' file consisting of a series of three (or sometimes four) byte offsets to the start of various chunks in the data file. (The end of the header is easily found as the last entry is the length of the data file.) The dictionary is 1024 bytes long and stored in the executable.

The dictionary consists of 254 nodes (in newr games plus four null bytes of padding) and there are two or three dictionaries stored in the executable depending on the game. The end of these dictionaries can be found by looking for node 254 which universally consists of the string <tt>$00 $00 $FD $01</tt> due to the fact that the byte <tt>$00</tt> is the single most common character in game data and thus always occupies the left branch of the root node.

The data itself is read byte-by-byte in the normal fashion ''but with the order of bits in every byte being reversed''. The following 1020 bytes constitute the complete 'trivial' Huffman dictionary for this implementation, that is, one that does not compress the data at all:

$00 $00 $80 $00 $40 $00 $C0 $00 $20 $00 $A0 $00 $60 $00 $E0 $00
$10 $00 $90 $00 $50 $00 $D0 $00 $30 $00 $B0 $00 $70 $00 $F0 $00
$08 $00 $88 $00 $48 $00 $C8 $00 $28 $00 $A8 $00 $68 $00 $E8 $00
$18 $00 $98 $00 $58 $00 $D8 $00 $38 $00 $B8 $00 $78 $00 $F8 $00
$04 $00 $84 $00 $44 $00 $C4 $00 $24 $00 $A4 $00 $64 $00 $E4 $00
$14 $00 $94 $00 $54 $00 $D4 $00 $34 $00 $B4 $00 $74 $00 $F4 $00
$0C $00 $8C $00 $4C $00 $CC $00 $2C $00 $AC $00 $6C $00 $EC $00
$1C $00 $9C $00 $5C $00 $DC $00 $3C $00 $BC $00 $7C $00 $FC $00
$02 $00 $82 $00 $42 $00 $C2 $00 $22 $00 $A2 $00 $62 $00 $E2 $00
$12 $00 $92 $00 $52 $00 $D2 $00 $32 $00 $B2 $00 $72 $00 $F2 $00
$0A $00 $8A $00 $4A $00 $CA $00 $2A $00 $AA $00 $6A $00 $EA $00
$1A $00 $9A $00 $5A $00 $DA $00 $3A $00 $BA $00 $7A $00 $FA $00
$06 $00 $86 $00 $46 $00 $C6 $00 $26 $00 $A6 $00 $66 $00 $E6 $00
$16 $00 $96 $00 $56 $00 $D6 $00 $36 $00 $B6 $00 $76 $00 $F6 $00
$0E $00 $8E $00 $4E $00 $CE $00 $2E $00 $AE $00 $6E $00 $EE $00
$1E $00 $9E $00 $5E $00 $DE $00 $3E $00 $BE $00 $7E $00 $FE $00
$01 $00 $81 $00 $41 $00 $C1 $00 $21 $00 $A1 $00 $61 $00 $E1 $00
$11 $00 $91 $00 $51 $00 $D1 $00 $31 $00 $B1 $00 $71 $00 $F1 $00
$09 $00 $89 $00 $49 $00 $C9 $00 $29 $00 $A9 $00 $69 $00 $E9 $00
$19 $00 $99 $00 $59 $00 $D9 $00 $39 $00 $B9 $00 $79 $00 $F9 $00
$05 $00 $85 $00 $45 $00 $C5 $00 $25 $00 $A5 $00 $65 $00 $E5 $00
$15 $00 $95 $00 $55 $00 $D5 $00 $35 $00 $B5 $00 $75 $00 $F5 $00
$0D $00 $8D $00 $4D $00 $CD $00 $2D $00 $AD $00 $6D $00 $ED $00
$1D $00 $9D $00 $5D $00 $DD $00 $3D $00 $BD $00 $7D $00 $FD $00
$03 $00 $83 $00 $43 $00 $C3 $00 $23 $00 $A3 $00 $63 $00 $E3 $00
$13 $00 $93 $00 $53 $00 $D3 $00 $33 $00 $B3 $00 $73 $00 $F3 $00
$0B $00 $8B $00 $4B $00 $CB $00 $2B $00 $AB $00 $6B $00 $EB $00
$1B $00 $9B $00 $5B $00 $DB $00 $3B $00 $BB $00 $7B $00 $FB $00
$07 $00 $87 $00 $47 $00 $C7 $00 $27 $00 $A7 $00 $67 $00 $E7 $00
$17 $00 $97 $00 $57 $00 $D7 $00 $37 $00 $B7 $00 $77 $00 $F7 $00
$0F $00 $8F $00 $4F $00 $CF $00 $2F $00 $AF $00 $6F $00 $EF $00
$1F $00 $9F $00 $5F $00 $DF $00 $3F $00 $BF $00 $7F $00 $FF $00
$00 $01 $01 $01 $02 $01 $03 $01 $04 $01 $05 $01 $06 $01 $07 $01
$08 $01 $09 $01 $0A $01 $0B $01 $0C $01 $0D $01 $0E $01 $0F $01
$10 $01 $11 $01 $12 $01 $13 $01 $14 $01 $15 $01 $16 $01 $17 $01
$18 $01 $19 $01 $1A $01 $1B $01 $1C $01 $1D $01 $1E $01 $1F $01
$20 $01 $21 $01 $22 $01 $23 $01 $24 $01 $25 $01 $26 $01 $27 $01
$28 $01 $29 $01 $2A $01 $2B $01 $2C $01 $2D $01 $2E $01 $2F $01
$30 $01 $31 $01 $32 $01 $33 $01 $34 $01 $35 $01 $36 $01 $37 $01
$38 $01 $39 $01 $3A $01 $3B $01 $3C $01 $3D $01 $3E $01 $3F $01
$40 $01 $41 $01 $42 $01 $43 $01 $44 $01 $45 $01 $46 $01 $47 $01
$48 $01 $49 $01 $4A $01 $4B $01 $4C $01 $4D $01 $4E $01 $4F $01
$50 $01 $51 $01 $52 $01 $53 $01 $54 $01 $55 $01 $56 $01 $57 $01
$58 $01 $59 $01 $5A $01 $5B $01 $5C $01 $5D $01 $5E $01 $5F $01
$60 $01 $61 $01 $62 $01 $63 $01 $64 $01 $65 $01 $66 $01 $67 $01
$68 $01 $69 $01 $6A $01 $6B $01 $6C $01 $6D $01 $6E $01 $6F $01
$70 $01 $71 $01 $72 $01 $73 $01 $74 $01 $75 $01 $76 $01 $77 $01
$78 $01 $79 $01 $7A $01 $7B $01 $7C $01 $7D $01 $7E $01 $7F $01
$80 $01 $81 $01 $82 $01 $83 $01 $84 $01 $85 $01 $86 $01 $87 $01
$88 $01 $89 $01 $8A $01 $8B $01 $8C $01 $8D $01 $8E $01 $8F $01
$90 $01 $91 $01 $92 $01 $93 $01 $94 $01 $95 $01 $96 $01 $97 $01
$98 $01 $99 $01 $9A $01 $9B $01 $9C $01 $9D $01 $9E $01 $9F $01
$A0 $01 $A1 $01 $A2 $01 $A3 $01 $A4 $01 $A5 $01 $A6 $01 $A7 $01
$A8 $01 $A9 $01 $AA $01 $AB $01 $AC $01 $AD $01 $AE $01 $AF $01
$B0 $01 $B1 $01 $B2 $01 $B3 $01 $B4 $01 $B5 $01 $B6 $01 $B7 $01
$B8 $01 $B9 $01 $BA $01 $BB $01 $BC $01 $BD $01 $BE $01 $BF $01
$C0 $01 $C1 $01 $C2 $01 $C3 $01 $C4 $01 $C5 $01 $C6 $01 $C7 $01
$C8 $01 $C9 $01 $CA $01 $CB $01 $CC $01 $CD $01 $CE $01 $CF $01
$D0 $01 $D1 $01 $D2 $01 $D3 $01 $D4 $01 $D5 $01 $D6 $01 $D7 $01
$D8 $01 $D9 $01 $DA $01 $DB $01 $DC $01 $DD $01 $DE $01 $DF $01
$E0 $01 $E1 $01 $E2 $01 $E3 $01 $E4 $01 $E5 $01 $E6 $01 $E7 $01
$E8 $01 $E9 $01 $EA $01 $EB $01 $EC $01 $ED $01 $EE $01 $EF $01
$F0 $01 $F1 $01 $F2 $01 $F3 $01 $F4 $01 $F5 $01 $F6 $01 $F7 $01
$F8 $01 $F9 $01 $FA $01 $FB $01 $FC $01 $FD $01

This is a useful example to use since it has a number of unique features. Firstly the paths to any given terminal node are all the same length, 8 bits. Secondly the 'byte reversal' can easily be seen in that the path to each terminal node is the ''reverse'' of the character it represents. And finally the nodes are arranged in a logical order with an easily seen pattern; the first half of the tree consists of terminal nodes, the second half of branch nodes. (Of the second half the first half of ''that'' consists of branch nodes that lead to terminal nodes while the second half consists of branch nodes to two branch nodes and so on.)

As an example the character $80 (128 or 10000000) can be expected to be represented by the path '00000001' and as such be the second node in the tree. Starting at the root node and following the leftmost path until the last step takes us to the following nodes: 254(root) -> 252 -> 248 -> 240 -> 224 -> 192 -> 128 -> 0(terminal node for characters $00 and $80)

== Source code ==

Some example code is available in various languages showing how to decompress (and in some cases compress) files using the Huffman algorithm.

=== QuickBasic ===

<source lang="qbasic">
'
' 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
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
</source>

----

<source lang="qbasic">
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
</source>

=== Visual Basic .NET ===

==== Huffman tree representation ====

This class, BinaryTreeNode, represents a binary tree whose branch nodes carry no value, like a Huffman dictionary tree.
<source lang="vbnet">Public Class BinaryTreeNode(Of T)
' By Fleexy, public domain, credit where credit is due
Private Branch As Boolean
Private Children As BinaryTreeNode(Of T)()
Private HoldValue As T
Public Sub New(LeafValue As T)
Branch = False
HoldValue = LeafValue
End Sub
Public Sub New(LeftChild As BinaryTreeNode(Of T), RightChild As BinaryTreeNode(Of T))
Branch = True
Children = {LeftChild, RightChild}
End Sub
Public ReadOnly Property HasValue As Boolean
Get
Return Not Branch
End Get
End Property
Public Property Value As T
Get
If Branch Then Throw New InvalidOperationException
Return HoldValue
End Get
Set(value As T)
If Branch Then Throw New InvalidOperationException
HoldValue = value
End Set
End Property
Public Property Child(Side As ChildSide) As BinaryTreeNode(Of T)
Get
If Not Branch Then Throw New InvalidOperationException
Return Children(Side)
End Get
Set(value As BinaryTreeNode(Of T))
If Not Branch Then Throw New InvalidOperationException
Children(Side) = value
End Set
End Property
Public Enum ChildSide As Byte
Left = 0
Right = 1
End Enum
Public ReadOnly Property Count As Integer
Get
If Not Branch Then Return 1
Return Children(0).Count + Children(1).Count
End Get
End Property
Public ReadOnly Property Depth As Integer
Get
If Not Branch Then Return 1
Return Math.Max(Children(0).Depth, Children(1).Depth) + 1
End Get
End Property
Public Overrides Function ToString() As String
Return "{Count = " & Count & ", Depth = " & Depth & "}"
End Function
End Class</source>

==== Huffman tree reading ====

This piece of code will read in a stored Huffman dictionary in the format described at the top of this article and store it in a BinaryTreeNode(Of Byte) as shown above.
<source lang="vbnet"> ' By Fleexy, public domain, credit where credit is due
Dim fDict As New IO.FileStream(DictionaryFile, IO.FileMode.Open)
Dim raw(254) As Tuple(Of UShort, UShort)
For x = 0 To 254
raw(x) = Tuple.Create(ReadUShort(fDict), ReadUShort(fDict))
Next
fDict.Close()
Dim GenerateTree As Func(Of UShort, BinaryTreeNode(Of Byte))
GenerateTree = Function(NextNode As UShort) As BinaryTreeNode(Of Byte)
Dim n As Tuple(Of UShort, UShort) = raw(NextNode)
Dim a, b As BinaryTreeNode(Of Byte)
If n.Item1 < 256 Then
a = New BinaryTreeNode(Of Byte)(n.Item1)
Else
a = GenerateTree(n.Item1 - 256)
End If
If n.Item2 < 256 Then
b = New BinaryTreeNode(Of Byte)(n.Item2)
Else
b = GenerateTree(n.Item2 - 256)
End If
Return New BinaryTreeNode(Of Byte)(a, b)
End Function
Dim dict As BinaryTreeNode(Of Byte) = GenerateTree(254)
fDict.Close()</source>

[[Category:Code examples]]

Huffman Compression

2016-05-24T08:42:37Z

Levellass: First part or rewrite

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte in, 1-bit out
| Games =
{{Game|The Blues Brothers}}
{{Game|Catacomb 3-D}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 2}}
}}

[[Huffman Compression]] is a compression algorithm used in many classic games. It is about as efficient as LZW or RLE compression, with many games using the three formats simultaneously.

Huffman compression involves making/reading a ''dictionary'' of 256 entries, one for each possible 1-byte character. This is organised in the form of a ''binary tree'' which is basically formed by taking the two lowest frequency characters and combining them into a new entry with their added frequencies and repeating until all entries are reduced to one ''root node''. After the dictionary is created, every character of data is replaced with the corresponding bit representation from the tree.

Any Huffman compressed data will thus be associated with a dictionary file (internal or external) used to decompress it. This page will explain the various aspects of Huffman compression using the example text "She sells seashells by the sea shore."

==Frequency tables==

In order to compress data using Huffman compression the compressor must build a 'frequency table' of all the elements it wishes to compress. In most cases this will be the 256 values a single byte can take, though it need not be limited to this. (Due to the binary nature of the compression method, sets of elements that match powers of 2 are both easiest and most efficient to compress.) The data is scanned and each occurrence of a given value. Taking the letters in our example sentence we can construct the following frequency table:

<pre>
Char Freq
's' 7
'e' 7
' ' 6
'h' 4
'l' 4
'a' 2
'S' 1
'b' 1
'o' 1
'r' 1
't' 1
'y' 1
'.' 1
</pre>

==The Binary Tree==

The binary tree is core to how Huffman compression compresses data. This is done by constructing a 'binary tree', so named because of its branching structure. Each branching point or 'node' has two options, 'left' and 'right' which lead either to another node or a character. The tree is constructed so that every character can be placed upon it and every path ends in a character.

This is done by first building a point of origin, 'root node' and the adding further nodes from there. Using our example we can build the following binary tree simply by listing the nodes alphabetically (and using '_' to stand in for the space for clarity):

<pre>
[Root]
____|_______
/ \
__|__ |
/ \ / \
| | | .
/ \ / \ / \
| | | | | |
/ \ / \ / \ / \ / \ / \
_ S a b e h l o r s t y
</pre>

On this tree we can use 'L' to specify a left path and 'R' to specify a right. As such the letter 'a' is represented by 'LLRL' and 'y' by 'RLRR'. Note that since the number of different characters is not a power of two (E.g. 16) not all paths from the root to a character are the same length, one is considerably shorter. The '.' character is represented by simply 'RR'

Assuming that 'R' and 'L' are '0' and '1' each 8-bit character in the original text can be represented by just 4 bits on average, halving the message length. This is far from optimal however and there is a specific procedure used to construct an optimal tree for the shortest message length. To do this advantage is taken of the fact that paths can be different lengths. If one set of paths is made a bit shorter at the expense of making a smaller set of paths a bit longer then the overall message will be made shorter.

===Constructing an optimal tree===

The first step in creating an optimal tree again is to create a 'root node'. To populate its two options the compressor repeatedly divides the frequency table. This is done by starting with the most common character and seeing if it contains more occurrences than the rest of the table combined. If not then the second most common character is added and so on.

In our example there are a total of 37 characters. Three characters make up more than half of this, 's', 'e' and ' '. Because of the binary structure of the tree however ''four'' options are needed here so 'h' is also included. All of these characters are placed on the left option of the root node while the remaining characters are placed on the right.

The next step creates a new node with left and right options and repeats the process. The two most common characters of the four, 's' and 'e' go to the left branch of this new node. A third node is created and, now that there are only two options, each is given a branch. The tree now looks like this:

<pre>
[Root]
/ \
| l, a, etc
/ \
| _, h
/ \
s e
</pre>

Now the character 's' can be represented as LLL and 'e' as LLR.

The compressor now moves 'up' to the previous node which still has a branch with more than one option in it. Another node is created and, since there are only two options, one is assigned to each branch. Te compressor then returns to the root node to deal with the right half of the tree. When it has assigned very character to a node the following optimal tree is produced:

<pre>
___[Root]____
/ \
_|_ ___|_______
/ \ / \
| | | |
/ \ / \ / \ / \
s e _ h l | | |
/ \ / \ / \
a | o r t |
/ \ / \
S b y .
</pre>

Notice that 4 characters now have paths that are just 3 choices long while 4 have paths 4 choices long and 4 have paths 5 choices long. Overall the average path length is the same as our previous tree. However 24 occurrences are one choice shorter, 5 are identical, 3 are one choice longer and '.' is three choices longer. This gives us a compressed message that is a total of 18 choices (or bits) shorter.

===Labeling the tree===

Now that a tree has been constructed it needs to be labelled in some form so that it can be stored as data either in the decompressor or to be sent with the compressed code. There are two major issues, what system to use when assigning numbers to the various nodes, and what bit value, 0 or 1, to assign to left or right options.

The most common (but far from unique) system is to label nodes from the 'bottom' of the tree to the top, going left-to-right across each 'layer' of the tree. (In our example the node that leads to 'y' and '.' would thus be the first numbered node.) Nodes are usually numbered starting with 0 and ending with the root node having the highest number.

Usually the left branch is given a bit value of 0 and the right branch a bit value of 1. Using this scheme 's' in our example resides on node 1 and is represented by the bit string '000' The complete compressed message is now '10110-011-001-010-000-001-100-100-000-010-000-001-1010-000-011-001-100-100-000-010-10111-11110-010-1110-011-001-010-000-001-1010-010-000-011-1100-1101-001-11111' or in bytes <tt>$B3 $28 $19 $02 $06 $83 $32 $05 $7F $2E $65 $03 $48 $3C $D3 $F0</tt> (The final byte is padded with nul bits.) This is a total of 16 bytes used for a 37 byte message.

==Nodes==

The binary tree must be stored in some form, usually called a ''dictionary''. The format varies from game to game, but is usually broadly along these lines. The tree will have 254 nodes (for all the one byte characters in game data) stored as two 'branches' of that node, usually taking up 4 bytes each, but sometimes 3. The second part is either 0 or 1, and says whether that branch goes to a character (0) or another node (1). The first part is the value of either that character or that node. (For the usual 4-byte implementation each part is a byte.)

In the Huffman table then we can expect to see each possible character TWICE, once as a character, once as a node reference. Note that the nodes are numbered from 0-253, NOT 1-254. The order of the nodes doesn't matter, only how they are connected.

The root node is ALWAYS node 254 (number 253!) and should always be something like $xx $yy $00 $00 (Since 0 is the most common character it is closest to the root.) It will also tend to be at the end of the dictionary, since most programs find it easier to write their dictionaries from bottom to top. This can often be used to find Huffman dictionaries in files, if you know what you are looking for.

==Example==

Compress the word "HUFFMAN". For simplicity, we will not use the usual 256 character tree, but rather something a bit smaller. (Huffman trees can be any size, the concept is the same.)

<ol>
<li>Frequencies are: 1: H,U,M,A,N 2: F</li>
<li>Make a binary tree: (here left = 0 and right = 1)
<pre>
[Root node]
/ \
[0] [1]
/ \ / \
F N [2] [3]
/ \ / \
M A H U
</pre>
</li>
<li>The first letter is 'H'; this on the tree is <tt>110</tt> The next letter is 'U' which is <tt>111</tt>. The third letter is 'F' which is <tt>00</tt> and so on (notice common letters have shorter strings?) The final output in bits is <tt>110111000010010101</tt>.</li>
</ol>

This is not of course the optimum Huffman tree, but that doesn't matter in this case, ANY tree will do. As bytes the output is thus: <tt>11011100 00100101 01000000</tt> (the end bit is padded with nulls) or <tt>$DC $25 $40</tt>. We have a reduction in size from 7 bytes to 3, over 50%! Sadly, we then need to include the Huffman table (the ''dictionary'') in some form.

In general a dictionary is built up by listing each node sequentially starting at 0 and ending with the root.

A possibility for storing the dictionary might be:

$00 $46 $00 $4E $01 $02 $01 $03 $00 $4D $00 $41 $00 $48 $00 $55 $01 $01 $01 $00
- F - N - - - - - M - A - H - U - - - -
(node 0) (node 1) (node 2) (node 3) (Root node)

In

Here we have numbered the nodes starting at the root as 254 and labelled every other node from 0-3 going left to right and top to bottom. This dictionary is stored ''bottom to top'' left to right. The first four bytes belong to node 0, the next four to node 2, the next to node 3, the next to node 1 and the final four bytes belonging to the root node. This somewhat 'reversed' method of storage as opposed to labeling is used in the Keen executables and is a result of how trees were built in one direction then read and stored in the other.

To decompress the data we use the tree again starting at the root node and reading the data bit by bit. So the first three bits are <tt>100</tt> which leads us down the tree to character 'H', then <tt>000</tt> which leads us to 'U' and so on.

==Huffman implementation in ID Software games==

Games created by Id Software (such as [[Commander Keen 4-6]] or [[Wolfenstein 3-D]]) have a shared but distinct implementation of Huffman compression. The dictionary consists of 1020 bytes (254 nodes plus for null bytes of padding) and there are two or three dictionaries stored in the executable depending on game. (The end of these can be found by looking for node 254 which usually consists of the string $00 $00 $FD $01)

The data itself is stored in an external file which consists of a number of concatenated 'chunks', each chunk beginning with a dword giving its decompressed size. There is also an internal 'header' file consisting of a series of three (or sometimes four) byte offsets to the start of various chunks in the data file. (The end of this can be found as the last entry is the length of the data file.)

The data itself is read byte-by-byte in the normal fashion ''but with the order of bits in every byte being reversed''. The following 1020 bytes constitute the complete 'trivial' Huffman dictionary for this implementation, that is, one that does not compress the data at all:

$00 $00 $80 $00 $40 $00 $C0 $00 $20 $00 $A0 $00 $60 $00 $E0 $00
$10 $00 $90 $00 $50 $00 $D0 $00 $30 $00 $B0 $00 $70 $00 $F0 $00
$08 $00 $88 $00 $48 $00 $C8 $00 $28 $00 $A8 $00 $68 $00 $E8 $00
$18 $00 $98 $00 $58 $00 $D8 $00 $38 $00 $B8 $00 $78 $00 $F8 $00
$04 $00 $84 $00 $44 $00 $C4 $00 $24 $00 $A4 $00 $64 $00 $E4 $00
$14 $00 $94 $00 $54 $00 $D4 $00 $34 $00 $B4 $00 $74 $00 $F4 $00
$0C $00 $8C $00 $4C $00 $CC $00 $2C $00 $AC $00 $6C $00 $EC $00
$1C $00 $9C $00 $5C $00 $DC $00 $3C $00 $BC $00 $7C $00 $FC $00
$02 $00 $82 $00 $42 $00 $C2 $00 $22 $00 $A2 $00 $62 $00 $E2 $00
$12 $00 $92 $00 $52 $00 $D2 $00 $32 $00 $B2 $00 $72 $00 $F2 $00
$0A $00 $8A $00 $4A $00 $CA $00 $2A $00 $AA $00 $6A $00 $EA $00
$1A $00 $9A $00 $5A $00 $DA $00 $3A $00 $BA $00 $7A $00 $FA $00
$06 $00 $86 $00 $46 $00 $C6 $00 $26 $00 $A6 $00 $66 $00 $E6 $00
$16 $00 $96 $00 $56 $00 $D6 $00 $36 $00 $B6 $00 $76 $00 $F6 $00
$0E $00 $8E $00 $4E $00 $CE $00 $2E $00 $AE $00 $6E $00 $EE $00
$1E $00 $9E $00 $5E $00 $DE $00 $3E $00 $BE $00 $7E $00 $FE $00
$01 $00 $81 $00 $41 $00 $C1 $00 $21 $00 $A1 $00 $61 $00 $E1 $00
$11 $00 $91 $00 $51 $00 $D1 $00 $31 $00 $B1 $00 $71 $00 $F1 $00
$09 $00 $89 $00 $49 $00 $C9 $00 $29 $00 $A9 $00 $69 $00 $E9 $00
$19 $00 $99 $00 $59 $00 $D9 $00 $39 $00 $B9 $00 $79 $00 $F9 $00
$05 $00 $85 $00 $45 $00 $C5 $00 $25 $00 $A5 $00 $65 $00 $E5 $00
$15 $00 $95 $00 $55 $00 $D5 $00 $35 $00 $B5 $00 $75 $00 $F5 $00
$0D $00 $8D $00 $4D $00 $CD $00 $2D $00 $AD $00 $6D $00 $ED $00
$1D $00 $9D $00 $5D $00 $DD $00 $3D $00 $BD $00 $7D $00 $FD $00
$03 $00 $83 $00 $43 $00 $C3 $00 $23 $00 $A3 $00 $63 $00 $E3 $00
$13 $00 $93 $00 $53 $00 $D3 $00 $33 $00 $B3 $00 $73 $00 $F3 $00
$0B $00 $8B $00 $4B $00 $CB $00 $2B $00 $AB $00 $6B $00 $EB $00
$1B $00 $9B $00 $5B $00 $DB $00 $3B $00 $BB $00 $7B $00 $FB $00
$07 $00 $87 $00 $47 $00 $C7 $00 $27 $00 $A7 $00 $67 $00 $E7 $00
$17 $00 $97 $00 $57 $00 $D7 $00 $37 $00 $B7 $00 $77 $00 $F7 $00
$0F $00 $8F $00 $4F $00 $CF $00 $2F $00 $AF $00 $6F $00 $EF $00
$1F $00 $9F $00 $5F $00 $DF $00 $3F $00 $BF $00 $7F $00 $FF $00
$00 $01 $01 $01 $02 $01 $03 $01 $04 $01 $05 $01 $06 $01 $07 $01
$08 $01 $09 $01 $0A $01 $0B $01 $0C $01 $0D $01 $0E $01 $0F $01
$10 $01 $11 $01 $12 $01 $13 $01 $14 $01 $15 $01 $16 $01 $17 $01
$18 $01 $19 $01 $1A $01 $1B $01 $1C $01 $1D $01 $1E $01 $1F $01
$20 $01 $21 $01 $22 $01 $23 $01 $24 $01 $25 $01 $26 $01 $27 $01
$28 $01 $29 $01 $2A $01 $2B $01 $2C $01 $2D $01 $2E $01 $2F $01
$30 $01 $31 $01 $32 $01 $33 $01 $34 $01 $35 $01 $36 $01 $37 $01
$38 $01 $39 $01 $3A $01 $3B $01 $3C $01 $3D $01 $3E $01 $3F $01
$40 $01 $41 $01 $42 $01 $43 $01 $44 $01 $45 $01 $46 $01 $47 $01
$48 $01 $49 $01 $4A $01 $4B $01 $4C $01 $4D $01 $4E $01 $4F $01
$50 $01 $51 $01 $52 $01 $53 $01 $54 $01 $55 $01 $56 $01 $57 $01
$58 $01 $59 $01 $5A $01 $5B $01 $5C $01 $5D $01 $5E $01 $5F $01
$60 $01 $61 $01 $62 $01 $63 $01 $64 $01 $65 $01 $66 $01 $67 $01
$68 $01 $69 $01 $6A $01 $6B $01 $6C $01 $6D $01 $6E $01 $6F $01
$70 $01 $71 $01 $72 $01 $73 $01 $74 $01 $75 $01 $76 $01 $77 $01
$78 $01 $79 $01 $7A $01 $7B $01 $7C $01 $7D $01 $7E $01 $7F $01
$80 $01 $81 $01 $82 $01 $83 $01 $84 $01 $85 $01 $86 $01 $87 $01
$88 $01 $89 $01 $8A $01 $8B $01 $8C $01 $8D $01 $8E $01 $8F $01
$90 $01 $91 $01 $92 $01 $93 $01 $94 $01 $95 $01 $96 $01 $97 $01
$98 $01 $99 $01 $9A $01 $9B $01 $9C $01 $9D $01 $9E $01 $9F $01
$A0 $01 $A1 $01 $A2 $01 $A3 $01 $A4 $01 $A5 $01 $A6 $01 $A7 $01
$A8 $01 $A9 $01 $AA $01 $AB $01 $AC $01 $AD $01 $AE $01 $AF $01
$B0 $01 $B1 $01 $B2 $01 $B3 $01 $B4 $01 $B5 $01 $B6 $01 $B7 $01
$B8 $01 $B9 $01 $BA $01 $BB $01 $BC $01 $BD $01 $BE $01 $BF $01
$C0 $01 $C1 $01 $C2 $01 $C3 $01 $C4 $01 $C5 $01 $C6 $01 $C7 $01
$C8 $01 $C9 $01 $CA $01 $CB $01 $CC $01 $CD $01 $CE $01 $CF $01
$D0 $01 $D1 $01 $D2 $01 $D3 $01 $D4 $01 $D5 $01 $D6 $01 $D7 $01
$D8 $01 $D9 $01 $DA $01 $DB $01 $DC $01 $DD $01 $DE $01 $DF $01
$E0 $01 $E1 $01 $E2 $01 $E3 $01 $E4 $01 $E5 $01 $E6 $01 $E7 $01
$E8 $01 $E9 $01 $EA $01 $EB $01 $EC $01 $ED $01 $EE $01 $EF $01
$F0 $01 $F1 $01 $F2 $01 $F3 $01 $F4 $01 $F5 $01 $F6 $01 $F7 $01
$F8 $01 $F9 $01 $FA $01 $FB $01 $FC $01 $FD $01

This is a useful example to use since it has a number of unique features. Firstly the paths to any given terminal node are all the same length, 8 bits. Secondly the 'byte reversal' can easily be seen in that the path to each terminal node is the ''reverse'' of the character it represents. And finally the nodes are arranged in a logical order with an easily seen pattern; the first half of the tree consists of terminal nodes, the second half of branch nodes. (Of the second half the first half of ''that'' consists of branch nodes that lead to terminal nodes while the second half consists of branch nodes to two branch nodes and so on.)

As an example the character $80 (128 or 10000000) can be expected to be represented by the path '00000001' and as such be the second node in the tree. Starting at the root node and following the leftmost path until the last step takes us to the following nodes: 254(root) -> 252 -> 248 -> 240 -> 224 -> 192 -> 128 -> 0(terminal node for characters $00 and $80)

== Source code ==

Some example code is available in various languages showing how to decompress (and in some cases compress) files using the Huffman algorithm.

=== QuickBasic ===

<source lang="qbasic">
'
' 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
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
</source>

----

<source lang="qbasic">
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
</source>

=== Visual Basic .NET ===

==== Huffman tree representation ====

This class, BinaryTreeNode, represents a binary tree whose branch nodes carry no value, like a Huffman dictionary tree.
<source lang="vbnet">Public Class BinaryTreeNode(Of T)
' By Fleexy, public domain, credit where credit is due
Private Branch As Boolean
Private Children As BinaryTreeNode(Of T)()
Private HoldValue As T
Public Sub New(LeafValue As T)
Branch = False
HoldValue = LeafValue
End Sub
Public Sub New(LeftChild As BinaryTreeNode(Of T), RightChild As BinaryTreeNode(Of T))
Branch = True
Children = {LeftChild, RightChild}
End Sub
Public ReadOnly Property HasValue As Boolean
Get
Return Not Branch
End Get
End Property
Public Property Value As T
Get
If Branch Then Throw New InvalidOperationException
Return HoldValue
End Get
Set(value As T)
If Branch Then Throw New InvalidOperationException
HoldValue = value
End Set
End Property
Public Property Child(Side As ChildSide) As BinaryTreeNode(Of T)
Get
If Not Branch Then Throw New InvalidOperationException
Return Children(Side)
End Get
Set(value As BinaryTreeNode(Of T))
If Not Branch Then Throw New InvalidOperationException
Children(Side) = value
End Set
End Property
Public Enum ChildSide As Byte
Left = 0
Right = 1
End Enum
Public ReadOnly Property Count As Integer
Get
If Not Branch Then Return 1
Return Children(0).Count + Children(1).Count
End Get
End Property
Public ReadOnly Property Depth As Integer
Get
If Not Branch Then Return 1
Return Math.Max(Children(0).Depth, Children(1).Depth) + 1
End Get
End Property
Public Overrides Function ToString() As String
Return "{Count = " & Count & ", Depth = " & Depth & "}"
End Function
End Class</source>

==== Huffman tree reading ====

This piece of code will read in a stored Huffman dictionary in the format described at the top of this article and store it in a BinaryTreeNode(Of Byte) as shown above.
<source lang="vbnet"> ' By Fleexy, public domain, credit where credit is due
Dim fDict As New IO.FileStream(DictionaryFile, IO.FileMode.Open)
Dim raw(254) As Tuple(Of UShort, UShort)
For x = 0 To 254
raw(x) = Tuple.Create(ReadUShort(fDict), ReadUShort(fDict))
Next
fDict.Close()
Dim GenerateTree As Func(Of UShort, BinaryTreeNode(Of Byte))
GenerateTree = Function(NextNode As UShort) As BinaryTreeNode(Of Byte)
Dim n As Tuple(Of UShort, UShort) = raw(NextNode)
Dim a, b As BinaryTreeNode(Of Byte)
If n.Item1 < 256 Then
a = New BinaryTreeNode(Of Byte)(n.Item1)
Else
a = GenerateTree(n.Item1 - 256)
End If
If n.Item2 < 256 Then
b = New BinaryTreeNode(Of Byte)(n.Item2)
Else
b = GenerateTree(n.Item2 - 256)
End If
Return New BinaryTreeNode(Of Byte)(a, b)
End Function
Dim dict As BinaryTreeNode(Of Byte) = GenerateTree(254)
fDict.Close()</source>

[[Category:Code examples]]

Huffman Compression

2016-05-24T06:47:43Z

Levellass: Partial rewrite save

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte in, 1-bit out
| Games =
{{Game|The Blues Brothers}}
{{Game|Catacomb 3-D}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 2}}
}}

[[Huffman Compression]] is a compression algorithm used in many classic games. It is about as efficient as LZW or RLE compression, with many games using the three formats simultaneously.

Huffman compression involves making/reading a ''dictionary'' of 256 entries, one for each possible 1-byte character. This is organised in the form of a ''binary tree'' which is basically formed by taking the two lowest frequency characters and combining them into a new entry with their added frequencies and repeating until all entries are reduced to one ''root node''. After the dictionary is created, every character of data is replaced with the corresponding bit representation from the tree.

Any Huffman compressed data will thus be associated with a dictionary file (internal or external) used to decompress it. This page will explain the various aspects of Huffman compression using the example text "She sells seashells by the sea shore."

==Frequency tables==

In order to compress data using Huffman compression the compressor must build a 'frequency table' of all the elements it wishes to compress. In most cases this will be the 256 values a single byte can take, though it need not be limited to this. (Due to the binary nature of the compression method, sets of elements that match powers of 2 are both easiest and most efficient to compress.) The data is scanned and each occurrence of a given value. Taking the letters in our example sentence we can construct the following frequency table:

<pre>
Char Freq
's' 7
'e' 7
' ' 6
'l' 4
'a' 2
'h' 2
'S' 1
'b' 1
'o' 1
'r' 1
't' 1
'y' 1
'.' 1
</pre>

==The Binary Tree==

The binary tree is core to how Huffman compression compresses data. It relies on the fact that in random data only a few characters will be common while most will not. Representing more common characters in a shorter form will thus save space even if it comes at the cost of representing rarer characters in a longer form. Specifically if the total number of occurrences of a character to be shortened outnumber all the characters that will have to be lengthened then shortening that character's representation will save space.

This is done by constructing a 'binary tree', so named because of its branching structure. The first step in doing this is to create a 'root'. This root will have two possible options, left and right which will lead to further branching points. To build an optimum tree the compressor looks at the most frequent character and sees if it is more common than all the other characters combined. (For long chunks of text this is usually the space character.)

In our example this is 's', occurring 7 times. It is not however more common than all the remaining letters. In this case the compressor gives the root two options, "left" and "right", both leading to other options. (Otherwise it would give the root an option that led to the most common character.)

Next the compressor works on the newly created options, leftmost first. Now it splits the frequency table in half. The most common characters will be considered for the left node, the least common for the right. In our example the table is split into 2 sets of 7 options. (With only 13 entries a 'dummy option' with frequency 0 is created to allow the division.) Again 's' in not common enough so the splitting repeats. (This requires the creation of ''another'' dummy option, but ''again'' in the lowest frequency half of the table which must 'donate' its most frequent member to the higher frequency half of the table.)

's' 7
'e' 7
' ' 6
'l' 4
'a' 2
'h' 2
'S' 1

==Nodes==

The binary tree must be stored in some form, usually called a ''dictionary''. The format varies from game to game, but is usually broadly along these lines. The tree will have 254 nodes (for all the one byte characters in game data) stored as two 'branches' of that node, usually taking up 4 bytes each, but sometimes 3. The second part is either 0 or 1, and says whether that branch goes to a character (0) or another node (1). The first part is the value of either that character or that node. (For the usual 4-byte implementation each part is a byte.)

In the Huffman table then we can expect to see each possible character TWICE, once as a character, once as a node reference. Note that the nodes are numbered from 0-253, NOT 1-254. The order of the nodes doesn't matter, only how they are connected.

The root node is ALWAYS node 254 (number 253!) and should always be something like $xx $yy $00 $00 (Since 0 is the most common character it is closest to the root.) It will also tend to be at the end of the dictionary, since most programs find it easier to write their dictionaries from bottom to top. This can often be used to find Huffman dictionaries in files, if you know what you are looking for.

==Example==

Compress the word "HUFFMAN". For simplicity, we will not use the usual 256 character tree, but rather something a bit smaller. (Huffman trees can be any size, the concept is the same.)

<ol>
<li>Frequencies are: 1: H,U,M,A,N 2: F</li>
<li>Make a binary tree: (here left = 0 and right = 1)
<pre>
[Root node]
/ \
[0] [1]
/ \ / \
F N [2] [3]
/ \ / \
M A H U
</pre>
</li>
<li>The first letter is 'H'; this on the tree is <tt>110</tt> The next letter is 'U' which is <tt>111</tt>. The third letter is 'F' which is <tt>00</tt> and so on (notice common letters have shorter strings?) The final output in bits is <tt>110111000010010101</tt>.</li>
</ol>

This is not of course the optimum Huffman tree, but that doesn't matter in this case, ANY tree will do. As bytes the output is thus: <tt>11011100 00100101 01000000</tt> (the end bit is padded with nulls) or <tt>$DC $25 $40</tt>. We have a reduction in size from 7 bytes to 3, over 50%! Sadly, we then need to include the Huffman table (the ''dictionary'') in some form.

In general a dictionary is built up by listing each node sequentially starting at 0 and ending with the root.

A possibility for storing the dictionary might be:

$00 $46 $00 $4E $01 $02 $01 $03 $00 $4D $00 $41 $00 $48 $00 $55 $01 $01 $01 $00
- F - N - - - - - M - A - H - U - - - -
(node 0) (node 1) (node 2) (node 3) (Root node)

In

Here we have numbered the nodes starting at the root as 254 and labelled every other node from 0-3 going left to right and top to bottom. This dictionary is stored ''bottom to top'' left to right. The first four bytes belong to node 0, the next four to node 2, the next to node 3, the next to node 1 and the final four bytes belonging to the root node. This somewhat 'reversed' method of storage as opposed to labeling is used in the Keen executables and is a result of how trees were built in one direction then read and stored in the other.

To decompress the data we use the tree again starting at the root node and reading the data bit by bit. So the first three bits are <tt>100</tt> which leads us down the tree to character 'H', then <tt>000</tt> which leads us to 'U' and so on.

==Huffman implementation in ID Software games==

Games created by Id Software (such as [[Commander Keen 4-6]] or [[Wolfenstein 3-D]]) have a shared but distinct implementation of Huffman compression. The dictionary consists of 1020 bytes (254 nodes plus for null bytes of padding) and there are two or three dictionaries stored in the executable depending on game. (The end of these can be found by looking for node 254 which usually consists of the string $00 $00 $FD $01)

The data itself is stored in an external file which consists of a number of concatenated 'chunks', each chunk beginning with a dword giving its decompressed size. There is also an internal 'header' file consisting of a series of three (or sometimes four) byte offsets to the start of various chunks in the data file. (The end of this can be found as the last entry is the length of the data file.)

The data itself is read byte-by-byte in the normal fashion ''but with the order of bits in every byte being reversed''. The following 1020 bytes constitute the complete 'trivial' Huffman dictionary for this implementation, that is, one that does not compress the data at all:

$00 $00 $80 $00 $40 $00 $C0 $00 $20 $00 $A0 $00 $60 $00 $E0 $00
$10 $00 $90 $00 $50 $00 $D0 $00 $30 $00 $B0 $00 $70 $00 $F0 $00
$08 $00 $88 $00 $48 $00 $C8 $00 $28 $00 $A8 $00 $68 $00 $E8 $00
$18 $00 $98 $00 $58 $00 $D8 $00 $38 $00 $B8 $00 $78 $00 $F8 $00
$04 $00 $84 $00 $44 $00 $C4 $00 $24 $00 $A4 $00 $64 $00 $E4 $00
$14 $00 $94 $00 $54 $00 $D4 $00 $34 $00 $B4 $00 $74 $00 $F4 $00
$0C $00 $8C $00 $4C $00 $CC $00 $2C $00 $AC $00 $6C $00 $EC $00
$1C $00 $9C $00 $5C $00 $DC $00 $3C $00 $BC $00 $7C $00 $FC $00
$02 $00 $82 $00 $42 $00 $C2 $00 $22 $00 $A2 $00 $62 $00 $E2 $00
$12 $00 $92 $00 $52 $00 $D2 $00 $32 $00 $B2 $00 $72 $00 $F2 $00
$0A $00 $8A $00 $4A $00 $CA $00 $2A $00 $AA $00 $6A $00 $EA $00
$1A $00 $9A $00 $5A $00 $DA $00 $3A $00 $BA $00 $7A $00 $FA $00
$06 $00 $86 $00 $46 $00 $C6 $00 $26 $00 $A6 $00 $66 $00 $E6 $00
$16 $00 $96 $00 $56 $00 $D6 $00 $36 $00 $B6 $00 $76 $00 $F6 $00
$0E $00 $8E $00 $4E $00 $CE $00 $2E $00 $AE $00 $6E $00 $EE $00
$1E $00 $9E $00 $5E $00 $DE $00 $3E $00 $BE $00 $7E $00 $FE $00
$01 $00 $81 $00 $41 $00 $C1 $00 $21 $00 $A1 $00 $61 $00 $E1 $00
$11 $00 $91 $00 $51 $00 $D1 $00 $31 $00 $B1 $00 $71 $00 $F1 $00
$09 $00 $89 $00 $49 $00 $C9 $00 $29 $00 $A9 $00 $69 $00 $E9 $00
$19 $00 $99 $00 $59 $00 $D9 $00 $39 $00 $B9 $00 $79 $00 $F9 $00
$05 $00 $85 $00 $45 $00 $C5 $00 $25 $00 $A5 $00 $65 $00 $E5 $00
$15 $00 $95 $00 $55 $00 $D5 $00 $35 $00 $B5 $00 $75 $00 $F5 $00
$0D $00 $8D $00 $4D $00 $CD $00 $2D $00 $AD $00 $6D $00 $ED $00
$1D $00 $9D $00 $5D $00 $DD $00 $3D $00 $BD $00 $7D $00 $FD $00
$03 $00 $83 $00 $43 $00 $C3 $00 $23 $00 $A3 $00 $63 $00 $E3 $00
$13 $00 $93 $00 $53 $00 $D3 $00 $33 $00 $B3 $00 $73 $00 $F3 $00
$0B $00 $8B $00 $4B $00 $CB $00 $2B $00 $AB $00 $6B $00 $EB $00
$1B $00 $9B $00 $5B $00 $DB $00 $3B $00 $BB $00 $7B $00 $FB $00
$07 $00 $87 $00 $47 $00 $C7 $00 $27 $00 $A7 $00 $67 $00 $E7 $00
$17 $00 $97 $00 $57 $00 $D7 $00 $37 $00 $B7 $00 $77 $00 $F7 $00
$0F $00 $8F $00 $4F $00 $CF $00 $2F $00 $AF $00 $6F $00 $EF $00
$1F $00 $9F $00 $5F $00 $DF $00 $3F $00 $BF $00 $7F $00 $FF $00
$00 $01 $01 $01 $02 $01 $03 $01 $04 $01 $05 $01 $06 $01 $07 $01
$08 $01 $09 $01 $0A $01 $0B $01 $0C $01 $0D $01 $0E $01 $0F $01
$10 $01 $11 $01 $12 $01 $13 $01 $14 $01 $15 $01 $16 $01 $17 $01
$18 $01 $19 $01 $1A $01 $1B $01 $1C $01 $1D $01 $1E $01 $1F $01
$20 $01 $21 $01 $22 $01 $23 $01 $24 $01 $25 $01 $26 $01 $27 $01
$28 $01 $29 $01 $2A $01 $2B $01 $2C $01 $2D $01 $2E $01 $2F $01
$30 $01 $31 $01 $32 $01 $33 $01 $34 $01 $35 $01 $36 $01 $37 $01
$38 $01 $39 $01 $3A $01 $3B $01 $3C $01 $3D $01 $3E $01 $3F $01
$40 $01 $41 $01 $42 $01 $43 $01 $44 $01 $45 $01 $46 $01 $47 $01
$48 $01 $49 $01 $4A $01 $4B $01 $4C $01 $4D $01 $4E $01 $4F $01
$50 $01 $51 $01 $52 $01 $53 $01 $54 $01 $55 $01 $56 $01 $57 $01
$58 $01 $59 $01 $5A $01 $5B $01 $5C $01 $5D $01 $5E $01 $5F $01
$60 $01 $61 $01 $62 $01 $63 $01 $64 $01 $65 $01 $66 $01 $67 $01
$68 $01 $69 $01 $6A $01 $6B $01 $6C $01 $6D $01 $6E $01 $6F $01
$70 $01 $71 $01 $72 $01 $73 $01 $74 $01 $75 $01 $76 $01 $77 $01
$78 $01 $79 $01 $7A $01 $7B $01 $7C $01 $7D $01 $7E $01 $7F $01
$80 $01 $81 $01 $82 $01 $83 $01 $84 $01 $85 $01 $86 $01 $87 $01
$88 $01 $89 $01 $8A $01 $8B $01 $8C $01 $8D $01 $8E $01 $8F $01
$90 $01 $91 $01 $92 $01 $93 $01 $94 $01 $95 $01 $96 $01 $97 $01
$98 $01 $99 $01 $9A $01 $9B $01 $9C $01 $9D $01 $9E $01 $9F $01
$A0 $01 $A1 $01 $A2 $01 $A3 $01 $A4 $01 $A5 $01 $A6 $01 $A7 $01
$A8 $01 $A9 $01 $AA $01 $AB $01 $AC $01 $AD $01 $AE $01 $AF $01
$B0 $01 $B1 $01 $B2 $01 $B3 $01 $B4 $01 $B5 $01 $B6 $01 $B7 $01
$B8 $01 $B9 $01 $BA $01 $BB $01 $BC $01 $BD $01 $BE $01 $BF $01
$C0 $01 $C1 $01 $C2 $01 $C3 $01 $C4 $01 $C5 $01 $C6 $01 $C7 $01
$C8 $01 $C9 $01 $CA $01 $CB $01 $CC $01 $CD $01 $CE $01 $CF $01
$D0 $01 $D1 $01 $D2 $01 $D3 $01 $D4 $01 $D5 $01 $D6 $01 $D7 $01
$D8 $01 $D9 $01 $DA $01 $DB $01 $DC $01 $DD $01 $DE $01 $DF $01
$E0 $01 $E1 $01 $E2 $01 $E3 $01 $E4 $01 $E5 $01 $E6 $01 $E7 $01
$E8 $01 $E9 $01 $EA $01 $EB $01 $EC $01 $ED $01 $EE $01 $EF $01
$F0 $01 $F1 $01 $F2 $01 $F3 $01 $F4 $01 $F5 $01 $F6 $01 $F7 $01
$F8 $01 $F9 $01 $FA $01 $FB $01 $FC $01 $FD $01

This is a useful example to use since it has a number of unique features. Firstly the paths to any given terminal node are all the same length, 8 bits. Secondly the 'byte reversal' can easily be seen in that the path to each terminal node is the ''reverse'' of the character it represents. And finally the nodes are arranged in a logical order with an easily seen pattern; the first half of the tree consists of terminal nodes, the second half of branch nodes. (Of the second half the first half of ''that'' consists of branch nodes that lead to terminal nodes while the second half consists of branch nodes to two branch nodes and so on.)

As an example the character $80 (128 or 10000000) can be expected to be represented by the path '00000001' and as such be the second node in the tree. Starting at the root node and following the leftmost path until the last step takes us to the following nodes: 254(root) -> 252 -> 248 -> 240 -> 224 -> 192 -> 128 -> 0(terminal node for characters $00 and $80)

== Source code ==

Some example code is available in various languages showing how to decompress (and in some cases compress) files using the Huffman algorithm.

=== QuickBasic ===

<source lang="qbasic">
'
' 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
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
</source>

----

<source lang="qbasic">
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
</source>

=== Visual Basic .NET ===

==== Huffman tree representation ====

This class, BinaryTreeNode, represents a binary tree whose branch nodes carry no value, like a Huffman dictionary tree.
<source lang="vbnet">Public Class BinaryTreeNode(Of T)
' By Fleexy, public domain, credit where credit is due
Private Branch As Boolean
Private Children As BinaryTreeNode(Of T)()
Private HoldValue As T
Public Sub New(LeafValue As T)
Branch = False
HoldValue = LeafValue
End Sub
Public Sub New(LeftChild As BinaryTreeNode(Of T), RightChild As BinaryTreeNode(Of T))
Branch = True
Children = {LeftChild, RightChild}
End Sub
Public ReadOnly Property HasValue As Boolean
Get
Return Not Branch
End Get
End Property
Public Property Value As T
Get
If Branch Then Throw New InvalidOperationException
Return HoldValue
End Get
Set(value As T)
If Branch Then Throw New InvalidOperationException
HoldValue = value
End Set
End Property
Public Property Child(Side As ChildSide) As BinaryTreeNode(Of T)
Get
If Not Branch Then Throw New InvalidOperationException
Return Children(Side)
End Get
Set(value As BinaryTreeNode(Of T))
If Not Branch Then Throw New InvalidOperationException
Children(Side) = value
End Set
End Property
Public Enum ChildSide As Byte
Left = 0
Right = 1
End Enum
Public ReadOnly Property Count As Integer
Get
If Not Branch Then Return 1
Return Children(0).Count + Children(1).Count
End Get
End Property
Public ReadOnly Property Depth As Integer
Get
If Not Branch Then Return 1
Return Math.Max(Children(0).Depth, Children(1).Depth) + 1
End Get
End Property
Public Overrides Function ToString() As String
Return "{Count = " & Count & ", Depth = " & Depth & "}"
End Function
End Class</source>

==== Huffman tree reading ====

This piece of code will read in a stored Huffman dictionary in the format described at the top of this article and store it in a BinaryTreeNode(Of Byte) as shown above.
<source lang="vbnet"> ' By Fleexy, public domain, credit where credit is due
Dim fDict As New IO.FileStream(DictionaryFile, IO.FileMode.Open)
Dim raw(254) As Tuple(Of UShort, UShort)
For x = 0 To 254
raw(x) = Tuple.Create(ReadUShort(fDict), ReadUShort(fDict))
Next
fDict.Close()
Dim GenerateTree As Func(Of UShort, BinaryTreeNode(Of Byte))
GenerateTree = Function(NextNode As UShort) As BinaryTreeNode(Of Byte)
Dim n As Tuple(Of UShort, UShort) = raw(NextNode)
Dim a, b As BinaryTreeNode(Of Byte)
If n.Item1 < 256 Then
a = New BinaryTreeNode(Of Byte)(n.Item1)
Else
a = GenerateTree(n.Item1 - 256)
End If
If n.Item2 < 256 Then
b = New BinaryTreeNode(Of Byte)(n.Item2)
Else
b = GenerateTree(n.Item2 - 256)
End If
Return New BinaryTreeNode(Of Byte)(a, b)
End Function
Dim dict As BinaryTreeNode(Of Byte) = GenerateTree(254)
fDict.Close()</source>

[[Category:Code examples]]

Huffman Compression

2016-05-23T09:23:07Z

Levellass: Reword example and more clearly label nodes

{{Compression Infobox
| Type = Stream
| UnitSize = 1-byte in, 1-bit out
| Games =
{{Game|The Blues Brothers}}
{{Game|Catacomb 3-D}}
{{Game|Commander Keen Dreams}}
{{Game|Dangerous Dave 2}}
}}

[[Huffman Compression]] is a compression algorithm used in many classic games. It is about as efficient as LZW or RLE compression, with many games using the three formats simultaneously.

Huffman compression involves making/reading a ''dictionary'' of 256 entries, one for each possible 1-byte character. This is organised in the form of a ''binary tree'' which is basically formed by taking the two lowest frequency characters and combining them into a new entry with their added frequencies and repeating until all entries are reduced to one ''root node''. After the dictionary is created, every character of data is replaced with the corresponding bit representation from the tree.

Any Huffman compressed data will thus be associated with a dictionary file (internal or external) used to decompress it.

==Nodes==

The binary tree must be stored in some form, usually called a ''dictionary''. The format varies from game to game, but is usually broadly along these lines. The tree will have 254 nodes (for all the one byte characters in game data) stored as two 'branches' of that node, usually taking up 4 bytes each, but sometimes 3. The second part is either 0 or 1, and says whether that branch goes to a character (0) or another node (1). The first part is the value of either that character or that node. (For the usual 4-byte implementation each part is a byte.)

In the Huffman table then we can expect to see each possible character TWICE, once as a character, once as a node reference. Note that the nodes are numbered from 0-253, NOT 1-254. The order of the nodes doesn't matter, only how they are connected.

The root node is ALWAYS node 254 (number 253!) and should always be something like $xx $yy $00 $00 (Since 0 is the most common character it is closest to the root.) It will also tend to be at the end of the dictionary, since most programs find it easier to write their dictionaries from bottom to top. This can often be used to find Huffman dictionaries in files, if you know what you are looking for.

==Example==

Compress the word "HUFFMAN". For simplicity, we will not use the usual 256 character tree, but rather something a bit smaller. (Huffman trees can be any size, the concept is the same.)

<ol>
<li>Frequencies are: 1: H,U,M,A,N 2: F</li>
<li>Make a binary tree: (here left = 0 and right = 1)
<pre>
'Root node'
[254]
/ \
/ [1]
/ / \
[0] [2] [3]
/ \ / \ / \
F N M A H U
</pre>
</li>
<li>The first letter is 'H'; this on the tree is <tt>110</tt> The next letter is 'U' which is <tt>111</tt>. The third letter is 'F' which is <tt>00</tt> and so on (notice common letters have shorter strings?) The final output in bits is <tt>110111000010010101</tt>.</li>
</ol>

This is not of course the optimum Huffman tree, but that doesn't matter, ANY tree will do. As bytes the output is thus: <tt>11011100 00100101 01000000</tt> (the end bit is padded with nulls) or <tt>$DC $25 $40</tt>. We have a reduction in size from 7 bytes to 3, over 50%! Sadly, we then need to include the Huffman table (the ''dictionary'') in some form.

A possibility for storing the dictionary might be: <tt>$00 $46 $00 $4E $00 $4D $00 $41 $00 $48 $00 $55 $01 $02 $01 $03 $01 $01 $01 $00</tt>. Here we have numbered the nodes starting at the root as 254 and labelled every other node from 0-3 going left to right and top to bottom. (Notice node 0 is shown in the example on the same level as nodes 2 and 3, it is actually a level higher, with node 1.) This dictionary is stored ''bottom to top'' left to right. The first four bytes belong to node 0, the next four to node 2, the next to node 3, the next to node 1 and the final four bytes belonging to the root node. This somewhat 'reversed' method of storage as opposed to labeling is used in the Keen executables and is a result of how trees were built in one direction then read and stored in the other.

To decompress the data we use the tree again starting at the root node and reading the data bit by bit. So the first three bits are <tt>100</tt> which leads us down the tree to character 'H', then <tt>000</tt> which leads us to 'U' and so on.

==Huffman implementation in ID Software games==

Games created by Id Software (such as [[Commander Keen 4-6]] or [[Wolfenstein 3-D]]) have a shared but distinct implementation of Huffman compression. The dictionary consists of 1020 bytes (254 nodes plus for null bytes of padding) and there are two or three dictionaries stored in the executable depending on game. (The end of these can be found by looking for node 254 which usually consists of the string $00 $00 $FD $01)

The data itself is stored in an external file which consists of a number of concatenated 'chunks', each chunk beginning with a dword giving its decompressed size. There is also an internal 'header' file consisting of a series of three (or sometimes four) byte offsets to the start of various chunks in the data file. (The end of this can be found as the last entry is the length of the data file.)

The data itself is read byte-by-byte in the normal fashion ''but with the order of bits in every byte being reversed''. The following 1020 bytes constitute the complete 'trivial' Huffman dictionary for this implementation, that is, one that does not compress the data at all:

$00 $00 $80 $00 $40 $00 $C0 $00 $20 $00 $A0 $00 $60 $00 $E0 $00
$10 $00 $90 $00 $50 $00 $D0 $00 $30 $00 $B0 $00 $70 $00 $F0 $00
$08 $00 $88 $00 $48 $00 $C8 $00 $28 $00 $A8 $00 $68 $00 $E8 $00
$18 $00 $98 $00 $58 $00 $D8 $00 $38 $00 $B8 $00 $78 $00 $F8 $00
$04 $00 $84 $00 $44 $00 $C4 $00 $24 $00 $A4 $00 $64 $00 $E4 $00
$14 $00 $94 $00 $54 $00 $D4 $00 $34 $00 $B4 $00 $74 $00 $F4 $00
$0C $00 $8C $00 $4C $00 $CC $00 $2C $00 $AC $00 $6C $00 $EC $00
$1C $00 $9C $00 $5C $00 $DC $00 $3C $00 $BC $00 $7C $00 $FC $00
$02 $00 $82 $00 $42 $00 $C2 $00 $22 $00 $A2 $00 $62 $00 $E2 $00
$12 $00 $92 $00 $52 $00 $D2 $00 $32 $00 $B2 $00 $72 $00 $F2 $00
$0A $00 $8A $00 $4A $00 $CA $00 $2A $00 $AA $00 $6A $00 $EA $00
$1A $00 $9A $00 $5A $00 $DA $00 $3A $00 $BA $00 $7A $00 $FA $00
$06 $00 $86 $00 $46 $00 $C6 $00 $26 $00 $A6 $00 $66 $00 $E6 $00
$16 $00 $96 $00 $56 $00 $D6 $00 $36 $00 $B6 $00 $76 $00 $F6 $00
$0E $00 $8E $00 $4E $00 $CE $00 $2E $00 $AE $00 $6E $00 $EE $00
$1E $00 $9E $00 $5E $00 $DE $00 $3E $00 $BE $00 $7E $00 $FE $00
$01 $00 $81 $00 $41 $00 $C1 $00 $21 $00 $A1 $00 $61 $00 $E1 $00
$11 $00 $91 $00 $51 $00 $D1 $00 $31 $00 $B1 $00 $71 $00 $F1 $00
$09 $00 $89 $00 $49 $00 $C9 $00 $29 $00 $A9 $00 $69 $00 $E9 $00
$19 $00 $99 $00 $59 $00 $D9 $00 $39 $00 $B9 $00 $79 $00 $F9 $00
$05 $00 $85 $00 $45 $00 $C5 $00 $25 $00 $A5 $00 $65 $00 $E5 $00
$15 $00 $95 $00 $55 $00 $D5 $00 $35 $00 $B5 $00 $75 $00 $F5 $00
$0D $00 $8D $00 $4D $00 $CD $00 $2D $00 $AD $00 $6D $00 $ED $00
$1D $00 $9D $00 $5D $00 $DD $00 $3D $00 $BD $00 $7D $00 $FD $00
$03 $00 $83 $00 $43 $00 $C3 $00 $23 $00 $A3 $00 $63 $00 $E3 $00
$13 $00 $93 $00 $53 $00 $D3 $00 $33 $00 $B3 $00 $73 $00 $F3 $00
$0B $00 $8B $00 $4B $00 $CB $00 $2B $00 $AB $00 $6B $00 $EB $00
$1B $00 $9B $00 $5B $00 $DB $00 $3B $00 $BB $00 $7B $00 $FB $00
$07 $00 $87 $00 $47 $00 $C7 $00 $27 $00 $A7 $00 $67 $00 $E7 $00
$17 $00 $97 $00 $57 $00 $D7 $00 $37 $00 $B7 $00 $77 $00 $F7 $00
$0F $00 $8F $00 $4F $00 $CF $00 $2F $00 $AF $00 $6F $00 $EF $00
$1F $00 $9F $00 $5F $00 $DF $00 $3F $00 $BF $00 $7F $00 $FF $00
$00 $01 $01 $01 $02 $01 $03 $01 $04 $01 $05 $01 $06 $01 $07 $01
$08 $01 $09 $01 $0A $01 $0B $01 $0C $01 $0D $01 $0E $01 $0F $01
$10 $01 $11 $01 $12 $01 $13 $01 $14 $01 $15 $01 $16 $01 $17 $01
$18 $01 $19 $01 $1A $01 $1B $01 $1C $01 $1D $01 $1E $01 $1F $01
$20 $01 $21 $01 $22 $01 $23 $01 $24 $01 $25 $01 $26 $01 $27 $01
$28 $01 $29 $01 $2A $01 $2B $01 $2C $01 $2D $01 $2E $01 $2F $01
$30 $01 $31 $01 $32 $01 $33 $01 $34 $01 $35 $01 $36 $01 $37 $01
$38 $01 $39 $01 $3A $01 $3B $01 $3C $01 $3D $01 $3E $01 $3F $01
$40 $01 $41 $01 $42 $01 $43 $01 $44 $01 $45 $01 $46 $01 $47 $01
$48 $01 $49 $01 $4A $01 $4B $01 $4C $01 $4D $01 $4E $01 $4F $01
$50 $01 $51 $01 $52 $01 $53 $01 $54 $01 $55 $01 $56 $01 $57 $01
$58 $01 $59 $01 $5A $01 $5B $01 $5C $01 $5D $01 $5E $01 $5F $01
$60 $01 $61 $01 $62 $01 $63 $01 $64 $01 $65 $01 $66 $01 $67 $01
$68 $01 $69 $01 $6A $01 $6B $01 $6C $01 $6D $01 $6E $01 $6F $01
$70 $01 $71 $01 $72 $01 $73 $01 $74 $01 $75 $01 $76 $01 $77 $01
$78 $01 $79 $01 $7A $01 $7B $01 $7C $01 $7D $01 $7E $01 $7F $01
$80 $01 $81 $01 $82 $01 $83 $01 $84 $01 $85 $01 $86 $01 $87 $01
$88 $01 $89 $01 $8A $01 $8B $01 $8C $01 $8D $01 $8E $01 $8F $01
$90 $01 $91 $01 $92 $01 $93 $01 $94 $01 $95 $01 $96 $01 $97 $01
$98 $01 $99 $01 $9A $01 $9B $01 $9C $01 $9D $01 $9E $01 $9F $01
$A0 $01 $A1 $01 $A2 $01 $A3 $01 $A4 $01 $A5 $01 $A6 $01 $A7 $01
$A8 $01 $A9 $01 $AA $01 $AB $01 $AC $01 $AD $01 $AE $01 $AF $01
$B0 $01 $B1 $01 $B2 $01 $B3 $01 $B4 $01 $B5 $01 $B6 $01 $B7 $01
$B8 $01 $B9 $01 $BA $01 $BB $01 $BC $01 $BD $01 $BE $01 $BF $01
$C0 $01 $C1 $01 $C2 $01 $C3 $01 $C4 $01 $C5 $01 $C6 $01 $C7 $01
$C8 $01 $C9 $01 $CA $01 $CB $01 $CC $01 $CD $01 $CE $01 $CF $01
$D0 $01 $D1 $01 $D2 $01 $D3 $01 $D4 $01 $D5 $01 $D6 $01 $D7 $01
$D8 $01 $D9 $01 $DA $01 $DB $01 $DC $01 $DD $01 $DE $01 $DF $01
$E0 $01 $E1 $01 $E2 $01 $E3 $01 $E4 $01 $E5 $01 $E6 $01 $E7 $01
$E8 $01 $E9 $01 $EA $01 $EB $01 $EC $01 $ED $01 $EE $01 $EF $01
$F0 $01 $F1 $01 $F2 $01 $F3 $01 $F4 $01 $F5 $01 $F6 $01 $F7 $01
$F8 $01 $F9 $01 $FA $01 $FB $01 $FC $01 $FD $01

This is a useful example to use since it has a number of unique features. Firstly the paths to any given terminal node are all the same length, 8 bits. Secondly the 'byte reversal' can easily be seen in that the path to each terminal node is the ''reverse'' of the character it represents. And finally the nodes are arranged in a logical order with an easily seen pattern; the first half of the tree consists of terminal nodes, the second half of branch nodes. (Of the second half the first half of ''that'' consists of branch nodes that lead to terminal nodes while the second half consists of branch nodes to two branch nodes and so on.)

As an example the character $80 (128 or 10000000) can be expected to be represented by the path '00000001' and as such be the second node in the tree. Starting at the root node and following the leftmost path until the last step takes us to the following nodes: 254(root) -> 252 -> 248 -> 240 -> 224 -> 192 -> 128 -> 0(terminal node for characters $00 and $80)

== Source code ==

Some example code is available in various languages showing how to decompress (and in some cases compress) files using the Huffman algorithm.

=== QuickBasic ===

<source lang="qbasic">
'
' 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
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
</source>

----

<source lang="qbasic">
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
</source>

=== Visual Basic .NET ===

==== Huffman tree representation ====

This class, BinaryTreeNode, represents a binary tree whose branch nodes carry no value, like a Huffman dictionary tree.
<source lang="vbnet">Public Class BinaryTreeNode(Of T)
' By Fleexy, public domain, credit where credit is due
Private Branch As Boolean
Private Children As BinaryTreeNode(Of T)()
Private HoldValue As T
Public Sub New(LeafValue As T)
Branch = False
HoldValue = LeafValue
End Sub
Public Sub New(LeftChild As BinaryTreeNode(Of T), RightChild As BinaryTreeNode(Of T))
Branch = True
Children = {LeftChild, RightChild}
End Sub
Public ReadOnly Property HasValue As Boolean
Get
Return Not Branch
End Get
End Property
Public Property Value As T
Get
If Branch Then Throw New InvalidOperationException
Return HoldValue
End Get
Set(value As T)
If Branch Then Throw New InvalidOperationException
HoldValue = value
End Set
End Property
Public Property Child(Side As ChildSide) As BinaryTreeNode(Of T)
Get
If Not Branch Then Throw New InvalidOperationException
Return Children(Side)
End Get
Set(value As BinaryTreeNode(Of T))
If Not Branch Then Throw New InvalidOperationException
Children(Side) = value
End Set
End Property
Public Enum ChildSide As Byte
Left = 0
Right = 1
End Enum
Public ReadOnly Property Count As Integer
Get
If Not Branch Then Return 1
Return Children(0).Count + Children(1).Count
End Get
End Property
Public ReadOnly Property Depth As Integer
Get
If Not Branch Then Return 1
Return Math.Max(Children(0).Depth, Children(1).Depth) + 1
End Get
End Property
Public Overrides Function ToString() As String
Return "{Count = " & Count & ", Depth = " & Depth & "}"
End Function
End Class</source>

==== Huffman tree reading ====

This piece of code will read in a stored Huffman dictionary in the format described at the top of this article and store it in a BinaryTreeNode(Of Byte) as shown above.
<source lang="vbnet"> ' By Fleexy, public domain, credit where credit is due
Dim fDict As New IO.FileStream(DictionaryFile, IO.FileMode.Open)
Dim raw(254) As Tuple(Of UShort, UShort)
For x = 0 To 254
raw(x) = Tuple.Create(ReadUShort(fDict), ReadUShort(fDict))
Next
fDict.Close()
Dim GenerateTree As Func(Of UShort, BinaryTreeNode(Of Byte))
GenerateTree = Function(NextNode As UShort) As BinaryTreeNode(Of Byte)
Dim n As Tuple(Of UShort, UShort) = raw(NextNode)
Dim a, b As BinaryTreeNode(Of Byte)
If n.Item1 < 256 Then
a = New BinaryTreeNode(Of Byte)(n.Item1)
Else
a = GenerateTree(n.Item1 - 256)
End If
If n.Item2 < 256 Then
b = New BinaryTreeNode(Of Byte)(n.Item2)
Else
b = GenerateTree(n.Item2 - 256)
End If
Return New BinaryTreeNode(Of Byte)(a, b)
End Function
Dim dict As BinaryTreeNode(Of Byte) = GenerateTree(254)
fDict.Close()</source>

[[Category:Code examples]]

Huffman Compression

2014-01-06T00:34:05Z

Levellass: Add more data on the Keen implementation

[[Huffman Compression]] is a compression algorithm used in many classic games. It is about as efficient as LZW or RLE compression, with many games using the three formats simultaneously.

Huffman compression involves making/reading a ''dictionary'' of 256 entries, one for each possible 1-byte character. This is organised in the form of a ''binary tree'' which is basically formed by taking the two lowest frequency characters and combining them into a new entry with their added frequencies and repeating until all entries are reduced to one ''root node''. After the dictionary is created, every character of data is replaced with the corresponding bit representation from the tree.

Any Huffman compressed data will thus be associated with a dictionary file (internal or external) used to decompress it.

==Nodes==

The binary tree must be stored in some form, usually called a ''dictionary''. The format varies from game to game, but is usually broadly along these lines. The tree will have 254 nodes (for all the one byte characters in game data) stored as two 'branches' of that node, usually taking up 4 bytes each, but sometimes 3. The second part is either 0 or 1, and says whether that branch goes to a character (0) or another node (1). The first part is the value of either that character or that node. (For the usual 4-byte implementation each part is a byte.)

In the Huffman table then we can expect to see each possible character TWICE, once as a character, once as a node reference. Note that the nodes are numbered from 0-253, NOT 1-254. The order of the nodes doesn't matter, only how they are connected.

The root node is ALWAYS node 254 (number 253!) and should always be something like $xx $yy $00 $00 (Since 0 is the most common character it is closest to the root.) It will also tend to be at the end of the dictionary, since most programs find it easier to write their dictionaries from bottom to top. This can often be used to find Huffman dictionaries in files, if you know what you are looking for.

==Example==

Compress the word "HUFFMAN". For simplicity, we will not use the usual 256 character tree, but rather something a bit smaller. (Huffman trees can be any size, the concept is the same.)

<ol>
<li>Frequencies are: 1: H,U,M,A,N 2: F</li>
<li>Make a binary tree: (here left = 0 and right = 1)
<pre>
'Root node'
*
/ \
/ *
/ / \
* * *
/ \ / \ / \
F N M A H U
</pre>
</li>
<li>The first letter is 'H'; this on the tree is <tt>110</tt> The next letter is 'U' which is <tt>111</tt>. The third letter is 'F' which is <tt>00</tt> and so on (notice common letters have shorter strings?) The final output in bits is <tt>110111000010010101</tt>.</li>
</ol>

This is not of course the optimum Huffman tree, but that doesn't matter, ANY tree will do. As bytes the output is thus: <tt>11011100 00100101 01000000</tt> (the end bit is padded with nulls) or <tt>$DC $25 $40</tt>. We have a reduction in size from 7 bytes to 3, over 50%! Sadly, we then need to include the Huffman table (the ''dictionary'') in some form.

A possibility for storing the dictionary might be: <tt>$00 $46 $00 $4E $00 $4D $00 $41 $00 $48 $00 $55 $01 $02 $01 $03 $01 $01 $01 $00</tt>. Here we have numbered the nodes starting at the root as 254 and labelled every other node from 0-4 going left to right and top to bottom. (If this is hard to see, try drawing things out on a piece of paper, the first 12 bytes are the bottom 3 nodes, all pointing to characters, and the last 8 bytes are the top two nodes, all pointing to other nodes.) This is the format used in Keen 4-6 executables.

To decompress the data we use the tree again starting at the root node and reading the data bit by bit. So the first three bits are <tt>100</tt> which leads us down the tree to character 'H', then <tt>000</tt> which leads us to 'U' and so on.

==Huffman implementation in ID Software games==

Games created by Id Software (such as [[Commander Keen 4-6]] or [[Wolfenstein 3-D]]) have a shared but distinct implementation of Huffman compression. The dictionary consists of 1020 bytes (254 nodes plus for null bytes of padding) and there are two or three dictionaries stored in the executable depending on game. (The end of these can be found by looking for node 254 which usually consists of the string $00 $00 $FD $01)

The data itself is stored in an external file which consists of a number of concatenated 'chunks', each chunk beginning with a dword giving its decompressed size. There is also an internal 'header' file consisting of a series of three (or sometimes four) byte offsets to the start of various chunks in the data file. (The end of this can be found as the last entry is the length of the data file.)

The data itself is read byte-by-byte in the normal fashion ''but with the order of bits in every byte being reversed''. The following 1020 bytes constitute the complete 'trivial' Huffman dictionary for this implementation, that is, one that does not compress the data at all:

$00 $00 $80 $00 $40 $00 $C0 $00 $20 $00 $A0 $00 $60 $00 $E0 $00
$10 $00 $90 $00 $50 $00 $D0 $00 $30 $00 $B0 $00 $70 $00 $F0 $00
$08 $00 $88 $00 $48 $00 $C8 $00 $28 $00 $A8 $00 $68 $00 $E8 $00
$18 $00 $98 $00 $58 $00 $D8 $00 $38 $00 $B8 $00 $78 $00 $F8 $00
$04 $00 $84 $00 $44 $00 $C4 $00 $24 $00 $A4 $00 $64 $00 $E4 $00
$14 $00 $94 $00 $54 $00 $D4 $00 $34 $00 $B4 $00 $74 $00 $F4 $00
$0C $00 $8C $00 $4C $00 $CC $00 $2C $00 $AC $00 $6C $00 $EC $00
$1C $00 $9C $00 $5C $00 $DC $00 $3C $00 $BC $00 $7C $00 $FC $00
$02 $00 $82 $00 $42 $00 $C2 $00 $22 $00 $A2 $00 $62 $00 $E2 $00
$12 $00 $92 $00 $52 $00 $D2 $00 $32 $00 $B2 $00 $72 $00 $F2 $00
$0A $00 $8A $00 $4A $00 $CA $00 $2A $00 $AA $00 $6A $00 $EA $00
$1A $00 $9A $00 $5A $00 $DA $00 $3A $00 $BA $00 $7A $00 $FA $00
$06 $00 $86 $00 $46 $00 $C6 $00 $26 $00 $A6 $00 $66 $00 $E6 $00
$16 $00 $96 $00 $56 $00 $D6 $00 $36 $00 $B6 $00 $76 $00 $F6 $00
$0E $00 $8E $00 $4E $00 $CE $00 $2E $00 $AE $00 $6E $00 $EE $00
$1E $00 $9E $00 $5E $00 $DE $00 $3E $00 $BE $00 $7E $00 $FE $00
$01 $00 $81 $00 $41 $00 $C1 $00 $21 $00 $A1 $00 $61 $00 $E1 $00
$11 $00 $91 $00 $51 $00 $D1 $00 $31 $00 $B1 $00 $71 $00 $F1 $00
$09 $00 $89 $00 $49 $00 $C9 $00 $29 $00 $A9 $00 $69 $00 $E9 $00
$19 $00 $99 $00 $59 $00 $D9 $00 $39 $00 $B9 $00 $79 $00 $F9 $00
$05 $00 $85 $00 $45 $00 $C5 $00 $25 $00 $A5 $00 $65 $00 $E5 $00
$15 $00 $95 $00 $55 $00 $D5 $00 $35 $00 $B5 $00 $75 $00 $F5 $00
$0D $00 $8D $00 $4D $00 $CD $00 $2D $00 $AD $00 $6D $00 $ED $00
$1D $00 $9D $00 $5D $00 $DD $00 $3D $00 $BD $00 $7D $00 $FD $00
$03 $00 $83 $00 $43 $00 $C3 $00 $23 $00 $A3 $00 $63 $00 $E3 $00
$13 $00 $93 $00 $53 $00 $D3 $00 $33 $00 $B3 $00 $73 $00 $F3 $00
$0B $00 $8B $00 $4B $00 $CB $00 $2B $00 $AB $00 $6B $00 $EB $00
$1B $00 $9B $00 $5B $00 $DB $00 $3B $00 $BB $00 $7B $00 $FB $00
$07 $00 $87 $00 $47 $00 $C7 $00 $27 $00 $A7 $00 $67 $00 $E7 $00
$17 $00 $97 $00 $57 $00 $D7 $00 $37 $00 $B7 $00 $77 $00 $F7 $00
$0F $00 $8F $00 $4F $00 $CF $00 $2F $00 $AF $00 $6F $00 $EF $00
$1F $00 $9F $00 $5F $00 $DF $00 $3F $00 $BF $00 $7F $00 $FF $00
$00 $01 $01 $01 $02 $01 $03 $01 $04 $01 $05 $01 $06 $01 $07 $01
$08 $01 $09 $01 $0A $01 $0B $01 $0C $01 $0D $01 $0E $01 $0F $01
$10 $01 $11 $01 $12 $01 $13 $01 $14 $01 $15 $01 $16 $01 $17 $01
$18 $01 $19 $01 $1A $01 $1B $01 $1C $01 $1D $01 $1E $01 $1F $01
$20 $01 $21 $01 $22 $01 $23 $01 $24 $01 $25 $01 $26 $01 $27 $01
$28 $01 $29 $01 $2A $01 $2B $01 $2C $01 $2D $01 $2E $01 $2F $01
$30 $01 $31 $01 $32 $01 $33 $01 $34 $01 $35 $01 $36 $01 $37 $01
$38 $01 $39 $01 $3A $01 $3B $01 $3C $01 $3D $01 $3E $01 $3F $01
$40 $01 $41 $01 $42 $01 $43 $01 $44 $01 $45 $01 $46 $01 $47 $01
$48 $01 $49 $01 $4A $01 $4B $01 $4C $01 $4D $01 $4E $01 $4F $01
$50 $01 $51 $01 $52 $01 $53 $01 $54 $01 $55 $01 $56 $01 $57 $01
$58 $01 $59 $01 $5A $01 $5B $01 $5C $01 $5D $01 $5E $01 $5F $01
$60 $01 $61 $01 $62 $01 $63 $01 $64 $01 $65 $01 $66 $01 $67 $01
$68 $01 $69 $01 $6A $01 $6B $01 $6C $01 $6D $01 $6E $01 $6F $01
$70 $01 $71 $01 $72 $01 $73 $01 $74 $01 $75 $01 $76 $01 $77 $01
$78 $01 $79 $01 $7A $01 $7B $01 $7C $01 $7D $01 $7E $01 $7F $01
$80 $01 $81 $01 $82 $01 $83 $01 $84 $01 $85 $01 $86 $01 $87 $01
$88 $01 $89 $01 $8A $01 $8B $01 $8C $01 $8D $01 $8E $01 $8F $01
$90 $01 $91 $01 $92 $01 $93 $01 $94 $01 $95 $01 $96 $01 $97 $01
$98 $01 $99 $01 $9A $01 $9B $01 $9C $01 $9D $01 $9E $01 $9F $01
$A0 $01 $A1 $01 $A2 $01 $A3 $01 $A4 $01 $A5 $01 $A6 $01 $A7 $01
$A8 $01 $A9 $01 $AA $01 $AB $01 $AC $01 $AD $01 $AE $01 $AF $01
$B0 $01 $B1 $01 $B2 $01 $B3 $01 $B4 $01 $B5 $01 $B6 $01 $B7 $01
$B8 $01 $B9 $01 $BA $01 $BB $01 $BC $01 $BD $01 $BE $01 $BF $01
$C0 $01 $C1 $01 $C2 $01 $C3 $01 $C4 $01 $C5 $01 $C6 $01 $C7 $01
$C8 $01 $C9 $01 $CA $01 $CB $01 $CC $01 $CD $01 $CE $01 $CF $01
$D0 $01 $D1 $01 $D2 $01 $D3 $01 $D4 $01 $D5 $01 $D6 $01 $D7 $01
$D8 $01 $D9 $01 $DA $01 $DB $01 $DC $01 $DD $01 $DE $01 $DF $01
$E0 $01 $E1 $01 $E2 $01 $E3 $01 $E4 $01 $E5 $01 $E6 $01 $E7 $01
$E8 $01 $E9 $01 $EA $01 $EB $01 $EC $01 $ED $01 $EE $01 $EF $01
$F0 $01 $F1 $01 $F2 $01 $F3 $01 $F4 $01 $F5 $01 $F6 $01 $F7 $01
$F8 $01 $F9 $01 $FA $01 $FB $01 $FC $01 $FD $01

This is a useful example to use since it has a number of unique features. Firstly the paths to any given terminal node are all the same length, 8 bits. Secondly the 'byte reversal' can easily be seen in that the path to each terminal node is the ''reverse'' of the character it represents. And finally the nodes are arranged in a logical order with an easily seen pattern; the first half of the tree consists of terminal nodes, the second half of branch nodes. (Of the second half the first half of ''that'' consists of branch nodes that lead to terminal nodes while the second half consists of branch nodes to two branch nodes and so on.)

As an example the character $80 (128 or 10000000) can be expected to be represented by the path '00000001' and as such be the second node in the tree. Starting at the root node and following the leftmost path until the last step takes us to the following nodes: 254(root) -> 252 -> 248 -> 240 -> 224 -> 192 -> 128 -> 0(terminal node for characters $00 and $80)

== Source code ==

Some example code is available in various languages showing how to decompress (and in some cases compress) files using the Huffman algorithm.

=== QuickBasic ===

<source lang="qbasic">
'
' 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
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
</source>

----

<source lang="qbasic">
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
</source>

=== Visual Basic .NET ===

==== Huffman tree representation ====

This class, BinaryTreeNode, represents a binary tree whose branch nodes carry no value, like a Huffman dictionary tree.
<source lang="vbnet">Public Class BinaryTreeNode(Of T)
' By Fleexy, public domain, credit where credit is due
Private Branch As Boolean
Private Children As BinaryTreeNode(Of T)()
Private HoldValue As T
Public Sub New(LeafValue As T)
Branch = False
HoldValue = LeafValue
End Sub
Public Sub New(LeftChild As BinaryTreeNode(Of T), RightChild As BinaryTreeNode(Of T))
Branch = True
Children = {LeftChild, RightChild}
End Sub
Public ReadOnly Property HasValue As Boolean
Get
Return Not Branch
End Get
End Property
Public Property Value As T
Get
If Branch Then Throw New InvalidOperationException
Return HoldValue
End Get
Set(value As T)
If Branch Then Throw New InvalidOperationException
HoldValue = value
End Set
End Property
Public Property Child(Side As ChildSide) As BinaryTreeNode(Of T)
Get
If Not Branch Then Throw New InvalidOperationException
Return Children(Side)
End Get
Set(value As BinaryTreeNode(Of T))
If Not Branch Then Throw New InvalidOperationException
Children(Side) = value
End Set
End Property
Public Enum ChildSide As Byte
Left = 0
Right = 1
End Enum
Public ReadOnly Property Count As Integer
Get
If Not Branch Then Return 1
Return Children(0).Count + Children(1).Count
End Get
End Property
Public ReadOnly Property Depth As Integer
Get
If Not Branch Then Return 1
Return Math.Max(Children(0).Depth, Children(1).Depth) + 1
End Get
End Property
Public Overrides Function ToString() As String
Return "{Count = " & Count & ", Depth = " & Depth & "}"
End Function
End Class</source>

==== Huffman tree reading ====

This piece of code will read in a stored Huffman dictionary in the format described at the top of this article and store it in a BinaryTreeNode(Of Byte) as shown above.
<source lang="vbnet"> ' By Fleexy, public domain, credit where credit is due
Dim fDict As New IO.FileStream(DictionaryFile, IO.FileMode.Open)
Dim raw(254) As Tuple(Of UShort, UShort)
For x = 0 To 254
raw(x) = Tuple.Create(ReadUShort(fDict), ReadUShort(fDict))
Next
fDict.Close()
Dim GenerateTree As Func(Of UShort, BinaryTreeNode(Of Byte))
GenerateTree = Function(NextNode As UShort) As BinaryTreeNode(Of Byte)
Dim n As Tuple(Of UShort, UShort) = raw(NextNode)
Dim a, b As BinaryTreeNode(Of Byte)
If n.Item1 < 256 Then
a = New BinaryTreeNode(Of Byte)(n.Item1)
Else
a = GenerateTree(n.Item1 - 256)
End If
If n.Item2 < 256 Then
b = New BinaryTreeNode(Of Byte)(n.Item2)
Else
b = GenerateTree(n.Item2 - 256)
End If
Return New BinaryTreeNode(Of Byte)(a, b)
End Function
Dim dict As BinaryTreeNode(Of Byte) = GenerateTree(254)
fDict.Close()</source>

[[Category:File Formats]]
[[Category:Compressed Files]]
[[Category:Huffman Compression]]
[[Category:Compression Algorithms]]
[[Category:Code examples]]
[[Category:Dangerous Dave 2]]

Huffman Compression

2014-01-02T03:38:42Z

Levellass: Add second example

[[Huffman Compression]] is a compression algorithm used in many classic games. It is about as efficient as LZW or RLE compression, with many games using the three formats simultaneously.

Huffman compression involves making/reading a ''dictionary'' of 256 entries, one for each possible 1-byte character. This is organised in the form of a ''binary tree'' which is basically formed by taking the two lowest frequency characters and combining them into a new entry with their added frequencies and repeating until all entries are reduced to one ''root node''. After the dictionary is created, every character of data is replaced with the corresponding bit representation from the tree.

Any Huffman compressed data will thus be associated with a dictionary file (internal or external) used to decompress it.

==Nodes==

The binary tree must be stored in some form, usually called a ''dictionary''. The format varies from game to game, but is usually broadly along these lines. The tree will have 254 nodes (for all the one byte characters in game data) stored as two 'branches' of that node, usually taking up 4 bytes each, but sometimes 3. The second part is either 0 or 1, and says whether that branch goes to a character (0) or another node (1). The first part is the value of either that character or that node. (For the usual 4-byte implementation each part is a byte.)

In the Huffman table then we can expect to see each possible character TWICE, once as a character, once as a node reference. Note that the nodes are numbered from 0-253, NOT 1-254. The order of the nodes doesn't matter, only how they are connected.

The root node is ALWAYS node 254 (number 253!) and should always be something like $xx $yy $00 $00 (Since 0 is the most common character it is closest to the root.) It will also tend to be at the end of the dictionary, since most programs find it easier to write their dictionaries from bottom to top. This can often be used to find Huffman dictionaries in files, if you know what you are looking for.

==Example 1==

Compress the word "HUFFMAN". For simplicity, we will not use the usual 256 character tree, but rather something a bit smaller. (Huffman trees can be any size, the concept is the same.)

<ol>
<li>Frequencies are: 1: H,U,M,A,N 2: F</li>
<li>Make a binary tree: (here left = 0 and right = 1)
<pre>
'Root node'
*
/ \
/ *
/ / \
* * *
/ \ / \ / \
F N M A H U
</pre>
</li>
<li>The first letter is 'H'; this on the tree is <tt>110</tt> The next letter is 'U' which is <tt>111</tt>. The third letter is 'F' which is <tt>00</tt> and so on (notice common letters have shorter strings?) The final output in bits is <tt>110111000010010101</tt>.</li>
</ol>

This is not of course the optimum Huffman tree, but that doesn't matter, ANY tree will do. As bytes the output is thus: <tt>11011100 00100101 01000000</tt> (the end bit is padded with nulls) or <tt>$DC $25 $40</tt>. We have a reduction in size from 7 bytes to 3, over 50%! Sadly, we then need to include the Huffman table (the ''dictionary'') in some form.

A possibility for storing the dictionary might be: <tt>$00 $46 $00 $4E $00 $4D $00 $41 $00 $48 $00 $55 $01 $02 $01 $03 $01 $01 $01 $00</tt>. Here we have numbered the nodes starting at the root as 254 and labelled every other node from 0-4 going left to right and top to bottom. (If this is hard to see, try drawing things out on a piece of paper, the first 12 bytes are the bottom 3 nodes, all pointing to characters, and the last 8 bytes are the top two nodes, all pointing to other nodes.) This is the format used in Keen 4-6 executables.

To decompress the data we use the tree again starting at the root node and reading the data bit by bit. So the first three bits are <tt>100</tt> which leads us down the tree to character 'H', then <tt>000</tt> which leads us to 'U' and so on.

==Example 2==

The following 1020 bytes constitute the complete 'trivial' Huffman dictionary, that is, one that does not compress the data at all:

$00 $00 $80 $00 $40 $00 $C0 $00 $20 $00 $A0 $00 $60 $00 $E0 $00
$10 $00 $90 $00 $50 $00 $D0 $00 $30 $00 $B0 $00 $70 $00 $F0 $00
$08 $00 $88 $00 $48 $00 $C8 $00 $28 $00 $A8 $00 $68 $00 $E8 $00
$18 $00 $98 $00 $58 $00 $D8 $00 $38 $00 $B8 $00 $78 $00 $F8 $00
$04 $00 $84 $00 $44 $00 $C4 $00 $24 $00 $A4 $00 $64 $00 $E4 $00
$14 $00 $94 $00 $54 $00 $D4 $00 $34 $00 $B4 $00 $74 $00 $F4 $00
$0C $00 $8C $00 $4C $00 $CC $00 $2C $00 $AC $00 $6C $00 $EC $00
$1C $00 $9C $00 $5C $00 $DC $00 $3C $00 $BC $00 $7C $00 $FC $00
$02 $00 $82 $00 $42 $00 $C2 $00 $22 $00 $A2 $00 $62 $00 $E2 $00
$12 $00 $92 $00 $52 $00 $D2 $00 $32 $00 $B2 $00 $72 $00 $F2 $00
$0A $00 $8A $00 $4A $00 $CA $00 $2A $00 $AA $00 $6A $00 $EA $00
$1A $00 $9A $00 $5A $00 $DA $00 $3A $00 $BA $00 $7A $00 $FA $00
$06 $00 $86 $00 $46 $00 $C6 $00 $26 $00 $A6 $00 $66 $00 $E6 $00
$16 $00 $96 $00 $56 $00 $D6 $00 $36 $00 $B6 $00 $76 $00 $F6 $00
$0E $00 $8E $00 $4E $00 $CE $00 $2E $00 $AE $00 $6E $00 $EE $00
$1E $00 $9E $00 $5E $00 $DE $00 $3E $00 $BE $00 $7E $00 $FE $00
$01 $00 $81 $00 $41 $00 $C1 $00 $21 $00 $A1 $00 $61 $00 $E1 $00
$11 $00 $91 $00 $51 $00 $D1 $00 $31 $00 $B1 $00 $71 $00 $F1 $00
$09 $00 $89 $00 $49 $00 $C9 $00 $29 $00 $A9 $00 $69 $00 $E9 $00
$19 $00 $99 $00 $59 $00 $D9 $00 $39 $00 $B9 $00 $79 $00 $F9 $00
$05 $00 $85 $00 $45 $00 $C5 $00 $25 $00 $A5 $00 $65 $00 $E5 $00
$15 $00 $95 $00 $55 $00 $D5 $00 $35 $00 $B5 $00 $75 $00 $F5 $00
$0D $00 $8D $00 $4D $00 $CD $00 $2D $00 $AD $00 $6D $00 $ED $00
$1D $00 $9D $00 $5D $00 $DD $00 $3D $00 $BD $00 $7D $00 $FD $00
$03 $00 $83 $00 $43 $00 $C3 $00 $23 $00 $A3 $00 $63 $00 $E3 $00
$13 $00 $93 $00 $53 $00 $D3 $00 $33 $00 $B3 $00 $73 $00 $F3 $00
$0B $00 $8B $00 $4B $00 $CB $00 $2B $00 $AB $00 $6B $00 $EB $00
$1B $00 $9B $00 $5B $00 $DB $00 $3B $00 $BB $00 $7B $00 $FB $00
$07 $00 $87 $00 $47 $00 $C7 $00 $27 $00 $A7 $00 $67 $00 $E7 $00
$17 $00 $97 $00 $57 $00 $D7 $00 $37 $00 $B7 $00 $77 $00 $F7 $00
$0F $00 $8F $00 $4F $00 $CF $00 $2F $00 $AF $00 $6F $00 $EF $00
$1F $00 $9F $00 $5F $00 $DF $00 $3F $00 $BF $00 $7F $00 $FF $00
$00 $01 $01 $01 $02 $01 $03 $01 $04 $01 $05 $01 $06 $01 $07 $01
$08 $01 $09 $01 $0A $01 $0B $01 $0C $01 $0D $01 $0E $01 $0F $01
$10 $01 $11 $01 $12 $01 $13 $01 $14 $01 $15 $01 $16 $01 $17 $01
$18 $01 $19 $01 $1A $01 $1B $01 $1C $01 $1D $01 $1E $01 $1F $01
$20 $01 $21 $01 $22 $01 $23 $01 $24 $01 $25 $01 $26 $01 $27 $01
$28 $01 $29 $01 $2A $01 $2B $01 $2C $01 $2D $01 $2E $01 $2F $01
$30 $01 $31 $01 $32 $01 $33 $01 $34 $01 $35 $01 $36 $01 $37 $01
$38 $01 $39 $01 $3A $01 $3B $01 $3C $01 $3D $01 $3E $01 $3F $01
$40 $01 $41 $01 $42 $01 $43 $01 $44 $01 $45 $01 $46 $01 $47 $01
$48 $01 $49 $01 $4A $01 $4B $01 $4C $01 $4D $01 $4E $01 $4F $01
$50 $01 $51 $01 $52 $01 $53 $01 $54 $01 $55 $01 $56 $01 $57 $01
$58 $01 $59 $01 $5A $01 $5B $01 $5C $01 $5D $01 $5E $01 $5F $01
$60 $01 $61 $01 $62 $01 $63 $01 $64 $01 $65 $01 $66 $01 $67 $01
$68 $01 $69 $01 $6A $01 $6B $01 $6C $01 $6D $01 $6E $01 $6F $01
$70 $01 $71 $01 $72 $01 $73 $01 $74 $01 $75 $01 $76 $01 $77 $01
$78 $01 $79 $01 $7A $01 $7B $01 $7C $01 $7D $01 $7E $01 $7F $01
$80 $01 $81 $01 $82 $01 $83 $01 $84 $01 $85 $01 $86 $01 $87 $01
$88 $01 $89 $01 $8A $01 $8B $01 $8C $01 $8D $01 $8E $01 $8F $01
$90 $01 $91 $01 $92 $01 $93 $01 $94 $01 $95 $01 $96 $01 $97 $01
$98 $01 $99 $01 $9A $01 $9B $01 $9C $01 $9D $01 $9E $01 $9F $01
$A0 $01 $A1 $01 $A2 $01 $A3 $01 $A4 $01 $A5 $01 $A6 $01 $A7 $01
$A8 $01 $A9 $01 $AA $01 $AB $01 $AC $01 $AD $01 $AE $01 $AF $01
$B0 $01 $B1 $01 $B2 $01 $B3 $01 $B4 $01 $B5 $01 $B6 $01 $B7 $01
$B8 $01 $B9 $01 $BA $01 $BB $01 $BC $01 $BD $01 $BE $01 $BF $01
$C0 $01 $C1 $01 $C2 $01 $C3 $01 $C4 $01 $C5 $01 $C6 $01 $C7 $01
$C8 $01 $C9 $01 $CA $01 $CB $01 $CC $01 $CD $01 $CE $01 $CF $01
$D0 $01 $D1 $01 $D2 $01 $D3 $01 $D4 $01 $D5 $01 $D6 $01 $D7 $01
$D8 $01 $D9 $01 $DA $01 $DB $01 $DC $01 $DD $01 $DE $01 $DF $01
$E0 $01 $E1 $01 $E2 $01 $E3 $01 $E4 $01 $E5 $01 $E6 $01 $E7 $01
$E8 $01 $E9 $01 $EA $01 $EB $01 $EC $01 $ED $01 $EE $01 $EF $01
$F0 $01 $F1 $01 $F2 $01 $F3 $01 $F4 $01 $F5 $01 $F6 $01 $F7 $01
$F8 $01 $F9 $01 $FA $01 $FB $01 $FC $01 $FD $01

This is a useful example to use since it has a number of unique features. Firstly the paths to any given terminal node are all the same length, 8 bits. Secondly the path to each terminal node is the ''reverse'' of the character it represents. And finally the nodes are arranged in a logical order with an easily seen pattern; the first half of the tree consists of terminal nodes, the second half of branch nodes. (Of the second half the first half of ''that'' consists of branch nodes that lead to terminal nodes while the second half consists of branch nodes to two branch nodes and so on.)

As an example the character $80 (128 or 10000000) can be expected to be represented by the path '00000001' and as such be the second node in the tree. Starting at the root node and following the leftmost path until the last step takes us to the following nodes: 254(root) -> 252 -> 248 -> 240 -> 224 -> 192 -> 128 -> 0(terminal node for characters $00 and $80)

== Source code ==

Some example code is available in various languages showing how to decompress (and in some cases compress) files using the Huffman algorithm.

=== QuickBasic ===

<source lang="qbasic">
'
' 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
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
</source>

----

<source lang="qbasic">
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
</source>

=== Visual Basic .NET ===

==== Huffman tree representation ====

This class, BinaryTreeNode, represents a binary tree whose branch nodes carry no value, like a Huffman dictionary tree.
<source lang="vbnet">Public Class BinaryTreeNode(Of T)
' By Fleexy, public domain, credit where credit is due
Private Branch As Boolean
Private Children As BinaryTreeNode(Of T)()
Private HoldValue As T
Public Sub New(LeafValue As T)
Branch = False
HoldValue = LeafValue
End Sub
Public Sub New(LeftChild As BinaryTreeNode(Of T), RightChild As BinaryTreeNode(Of T))
Branch = True
Children = {LeftChild, RightChild}
End Sub
Public Property Value As T
Get
If Branch Then Throw New InvalidOperationException
Return HoldValue
End Get
Set(value As T)
If Branch Then Throw New InvalidOperationException
HoldValue = value
End Set
End Property
Public Property Child(Side As ChildSide) As BinaryTreeNode(Of T)
Get
If Not Branch Then Throw New InvalidOperationException
Return Children(Side)
End Get
Set(value As BinaryTreeNode(Of T))
If Not Branch Then Throw New InvalidOperationException
Children(Side) = value
End Set
End Property
Public Enum ChildSide As Byte
Left = 0
Right = 0
End Enum
Public ReadOnly Property Count As Integer
Get
If Not Branch Then Return 1
Return Children(0).Count + Children(1).Count
End Get
End Property
Public ReadOnly Property Depth As Integer
Get
If Not Branch Then Return 1
Return Math.Max(Children(0).Depth, Children(1).Depth) + 1
End Get
End Property
Public Overrides Function ToString() As String
Return "{Count = " & Count & ", Depth = " & Depth & "}"
End Function
End Class</source>

==== Huffman tree reading ====

This piece of code will read in a stored Huffman dictionary in the format described at the top of this article and store it in a BinaryTreeNode(Of Byte) as shown above.
<source lang="vbnet"> ' By Fleexy, public domain, credit where credit is due
Dim fDict As New IO.FileStream(DictionaryFile, IO.FileMode.Open)
Dim raw(254) As Tuple(Of UShort, UShort)
For x = 0 To 254
raw(x) = Tuple.Create(ReadUShort(fDict), ReadUShort(fDict))
Next
fDict.Close()
Dim GenerateTree As Func(Of UShort, BinaryTreeNode(Of Byte))
GenerateTree = Function(NextNode As UShort) As BinaryTreeNode(Of Byte)
Dim n As Tuple(Of UShort, UShort) = raw(NextNode)
Dim a, b As BinaryTreeNode(Of Byte)
If n.Item1 < 256 Then
a = New BinaryTreeNode(Of Byte)(n.Item1)
Else
a = GenerateTree(n.Item1 - 256)
End If
If n.Item2 < 256 Then
b = New BinaryTreeNode(Of Byte)(n.Item2)
Else
b = GenerateTree(n.Item2 - 256)
End If
Return New BinaryTreeNode(Of Byte)(a, b)
End Function
Dim dict As BinaryTreeNode(Of Byte) = GenerateTree(254)
fDict.Close()</source>

[[Category:File Formats]]
[[Category:Compressed Files]]
[[Category:Huffman Compression]]
[[Category:Compression Algorithms]]
[[Category:Code examples]]
[[Category:Dangerous Dave 2]]

Cosmo's Cosmic Adventure

2013-04-06T09:34:59Z

Levellass: Add Cosgraph link, change some game stuff that is now editable.

{{Game Infobox
| Levels = Edit
| Tiles = Edit
| Sprites = Edit
| Fullscreen = Edit
| Sound = Edit
| Music = Edit
| Text = No
| Story = No
| Interface = No
}}
'''Cosmo's Cosmic Adventure''', also known simply as Cosmo, is a three part series chronicling the adventures of Cosmo, a small, green sucker-handed alien boy who is seeking his parents after a meteor collision forces them to land their ship on a dangerous and uncharted planet.

The Cosmo engine was later updated and used for [[Duke Nukem II]], so the two games share a number of file formats.

== Tools ==

{{BeginFileFormatTools|Type=game}}
{{FileFormatTool
| Name = [[Camoto]]
| Platform = Linux console/GUI
| grp = Edit
| map = Edit
| gfx = Edit
| mus = Edit
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [http://www.shikadi.net/wiki/files/moddingwiki/tools/cosmo/cosedit.zip CosEdit]
| Platform = DOS GUI
| grp = No
| map = Edit
| gfx = No
| mus = No
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [http://www.shikadi.net/wiki/files/moddingwiki/tools/cosmo/cosmedit10.zip Cosmo Edit]
| Platform = DOS console
| grp = No
| map = Edit
| gfx = No
| mus = No
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [http://www.shikadi.net/wiki/files/moddingwiki/tools/cosmo/textract.zip TExtract]
| Platform = DOS console
| grp = Read
| map = No
| gfx = No
| mus = No
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = Wombat
| Platform = Windows GUI
| grp = Read
| map = Read
| gfx = Read
| mus = Read
| sfx = No
| txt = No
| sav = No
| exe = No
}}
{{FileFormatTool
| Name = [https://dl.dropbox.com/u/3940020/COSGRAPH-working.zip Cosgraph]
| Platform = Windows GUI
| grp = Read
| map = No
| gfx = Edit
| mus = Edit
| sfx = Edit
| txt = No
| sav = No
| exe = No
}}
{{EndFileFormatTools}}

 

== File formats ==

This section lists the major file formats used in the game.

{|class="wikitable"
!Use!!Format!!Details
|-
| Backgrounds || [[Raw EGA data#Planar|Full-screen planar EGA]] || 32,000 byte <tt>*.MNI</tt> files are 320x200 full-screen images (in four planes: blue, green, red, intensity). <tt>TITLE1.MNI</tt> is the image on the right, which is in this format.
|-
| Exit screen || [[B800 Text]] || 4000-byte <tt>*.MNI</tt> files are text screens shown at exit (e.g. <tt>NOMEMORY.MNI</tt>)
|-
| Graphics || [[Cosmo Tileset Format]] || <tt>ACTORS.MNI</tt>, <tt>BD*.MNI</tt>, <tt>CARTOON.MNI</tt>, <tt>MASKTILE.MNI</tt>, <tt>PLAYER.MNI</tt> and <tt>TILES.MNI</tt> are all tilesets
|-
| Tile attributes || [[Cosmo Tile Attributes]] || Format of the <tt>TILEATTR.MNI</tt> file
|-
| Group || [[VOL Format]] || group file storing the game data (both the <tt>*.VOL</tt> and <tt>*.STN</tt> files are in this format.)
|-
| Levels || [[Cosmo Level Format]] || <tt>A*.MNI</tt> are game levels.
|-
| Messages || - || Text is contained in the executable in all episodes, but in Cosmo 1 & 2, the executable is compressed by [[LZEXE]], and can be uncompressed with [[UNLZEXE]].
|-
| Music || [[IMF Format]] || Most of the <tt>M*.MNI</tt> files are music files, e.g. <tt>MHAPPY.MNI</tt>) - see [[#Notes]] below
|-
| Sounds || [[Inverse Frequency Sound format]] || <tt>SOUNDSx.MNI</tt> files are in this format, there are three per episode
|-
| Saves || [[Cosmo Savegame Format]] || <tt>COSMOx.SVx</tt> are saved games. <tt>COSMOx.SVT</tt> is a temporary save written at the start of each level
|-
| Tile info || [[Cosmo Tileinfo Format]] || How to lay out the actor tiles. <tt>ACTRINFO.MNI</tt>, <tt>PLYRINFO.MNI</tt> and <tt>CARTINFO.MNI</tt> are in this format
|}

== Notes ==

* In the original Cosmo Engine, the graphics memory is allocated after the memory used for storing the IMF file loaded for the current level. This has the unfortunate side effect of corrupting the entire tileset graphics table in memory, turning the graphics into random colours when a complex IMF file is loaded. This is because the data from the IMF file overflows its allocated memory and overwrites the start of the tileset data. Of course this only happens in memory, so the corruption is not permanent upon exiting. The corruption will occur whenever that particular over-sized IMF file is loaded, but the corruption will completely disappear if the IMF file is removed from the [[:Category:Group Files|group file]] or replaced with a less-complex version (i.e. by reducing the number of notes.) This does not appear to affect how the program runs, only affecting the tileset graphics. The overflow limit appears to be around 40K, which is above the size of nearly all Apogee IMF files, but not at the limit of IMF file size (64K for type-1, or effectively unlimited for type-0 as used in Cosmo.)

* The game reads from the VOL and STN files in preference to the current directory. Any game files in the current directory will not be read while the VOL/STN is present. To modify a file, it will either need to be imported back into the VOL/STN, or the VOL/STN should have its entire contents extracted into the game folder and then be removed or renamed.

* A directory path (relative to the current directory) can be given on the command line. Any files that the game writes (saved games, high scores, etc.) will be written to this folder instead. This is probably to allow running the game directly from read-only media like a CD.

[[Category:Apogee]]
[[Category:Sidescroller]]