Huffman Coding

Quite some time ago I did a short post about a compression technique called run-length encoding (or RLE), that was a commonly used compression method for graphic and level data. At the time I wrote and implemented it for the graphics and level data for my home-brew game Bobs Fury with quite the success, significantly reducing the disk space required for the base game.

I do however have some files left, which are largely just ASCII text, that don’t compress well or at all using that technique. I’d like to make them smaller, and of course harder to read as they contain story text, not that my game has a brilliant story, but you get the idea. Step in an encoding technique called Huffman coding.

Essentially the encoding algorithm encodes symbols as a variable length stream of bits. The most frequently used symbols are represented by shorter bit streams, whilst the least used have longer ones. Normally in a computer each symbol would be encoded as a fixed number of bits, such as say 8-bit or 16, so this results (hopefully) in shorter encodings for most symbols, and longer ones only for the rarely used ones.

The tricky part is creating the Huffman tree, which is basically a code-book representing how each symbol is encoded or decoded. Here is a quick tutorial on how they are created, which will also give you a feel for how the encoding works. It’s also commonly known as a dictionary, or code book.

A fixed tree can be used for everything, but would not do the best job for every set of data being compressed. So typically a tree is created and stored along with the encoded data to achieve the best compression possible. This of course does add some overhead, which could be a problem if the resulting encoding isn’t much shorter than the original.

Huffman coding typically works poorly when the symbols all appear in the text at roughly the same frequency. The worst case being everything with exactly the same frequency. Notably it won’t produce an encoding that is longer than the original data, although with the overhead of storing the tree, you could end up with a larger data file. In practise this rarely happens.

Other data such as English text stored in ASCII actually compresses quite well. As usually not all the 255 characters are used, most encodings will be shorter than 8 bits per symbol. Also because natural language uses some letters more than others the average encoding length for all the symbols will be shorter.

Huffman coding was actually invented quite some time ago (1951) by David Huffman, well before it came into common use. Check out the Wikipedia page for more information. It’s a part of many commonly used compression programs and formats such a Zip and Bzip. Older 8-bit machines typically weren’t powerful enough, so it wasn’t commonly used until more powerful machines with more memory became available.

It took me much longer than usual to write this post primarily because I began the process of writing an encoder and decoder, but because of the complexity, it’s taken up much more time than I expected. Currently I have just finished the encoder, but have yet to test it. I had hoped to get the code running first, but that will have to wait.

Snarf for DOS

Today’s game is another one made by Everett Kaser, a shareware author who happens to still be making new games. I wrote about another of his games a short while ago, Hero’s heart. This one named Snarf was made in 1988 originally, released in 1990 and with updated versions of the game coming out up until 1993. It’s an arcade style game in which you need to collect treasure and keys, and avoid enemies known as snarfs.

Like Hero’s Heart, this has high resolution EGA graphics (640x350x16) that allows for larger levels without having to implement scrolling, which wasn’t easy on old PC hardware. The sprites are drawn nicely although there isn’t really much in the way of animation, but what’s there works. The sound is again from the PC speaker and consists of a few bleeps and bloops, it’s ok and you can turn it off if you don’t like the audio.

Game-play wise it’s very much a score attack arcade style game. The main way you get points is of course collecting treasure, which is multiplied by the numbers of ‘tags’ you have left at the end of a level. The main hazard is of course the snarfs who spawn from nests located around the map. if you happen to run into the snarfs they take your tags which is essentially your health. There are usually a fair few running around, and they spawn endlessly so it’s best to avoid them if you can.

The controls seem to be inspired by games like Robotron which allow you to fire your weapon in a different direction to that you are moving. This proves to be a very handy feature, although I’m yet to get good at it. You can only have one or two shots in the air depending on what you set, so it’s best to only fire when you know the shot will hit something in a short time. Otherwise you could be waiting before you can shoot again. Again it is generally better to avoid the snarfs rather than shoot them if you can.

The snarfs themselves seem to be reasonably intelligent, being able to avoid shots, find a path to you and generally trap you. I’ve found myself getting trapped by the blighters and having to try and shoot as many as I can, or simply try to out smart them.

I found Snarf to be quite fun, but didn’t get too far into the levels because I didn’t have enough time to really practice and work at being better. It is mostly the controls that I need to work on learning as I hadn’t played a game with a scheme like that before. There are 50 levels and a level editor included, so there is no shortage of content level wise. There are some downsides, such as not getting any more than a single life, but you can select the level you start on, so you don’t have to play the same ones repeatedly.

Gemini of Ancient DOS Games also did a video about Snarf quite some time ago, you can find it here. The game is available as freeware from the RGB classic DOS games website here.

Motherboard: EPoX EP-MVP4A

Just when you thought I had run out of Socket 7 boards here’s another one! Today’s mother board was made by the Taiwanese company EPoX who made value boards that were targeted towards the over-clocker and enthusiast market. Here’s an overview of the board.

This board was made mid 1999, late in the life of the socket 7 standard. It would have probably carried an AMD, Cyrix or IBM chip, as Intel had already moved onto the Slot 1 standard at this time. Lets take a quick look at what features make this board different to the other socket 7 boards I’ve looked at so far.

Thermistor

One of the most obvious things is seen in the middle of the CPU socket. It’s a thermistor for measuring the CPU temperature. CPUs of the time didn’t have this feature built-in, so without this sensor an over-clocker would have to guess how hot their machine was running by touch or other means. This also proved useful for technicians to help determine if there was something wrong with the setup or thermal compound on the CPU. Unfortunately these sensors weren’t really all that accurate, but they were better than nothing.

Chassis Fan

Next I noticed that this board has connectors for a chassis fan. Of course these extra fans had been around for quite a while at this stage, and the connector for a year or so. This is a reflection of the significant increase in power consumption and heat generation in machines of the late 90’s. Although it wouldn’t get out of hand until much later (with P4 chips)

Jumpers

When you look at the configuration jumpers, you can tell it was designed with over-clockers in mind. Unlike other boards there is a simple and clear way to set the multiplier and bus speed. There is a single jumper which you use to select the speed option desired. Most other boards required you to decode a table and apply a number of jumpers correctly. Unfortunately this photo didn’t come out as clear as I would have liked.

VIA made the chipset for this board, they typically had fairly well performing chips, that had better, but not perfect software support. The south bridge chip has integrated sound and other basic peripherals, with a trident video chip integrated into the north bridge. On board video is connected internally via an AGP bus, but there is no standard AGP slot for an external card. This would have been limiting, as the PCI graphics cards that were still available would have been slower than the AGP counterparts.

From the perspective of a technician this board would have been quite easy to handle. The manual would have been unnecessary even the first time you set it up. The power connector is nice and close to a mounting hole, so you wouldn’t flex the board too much when connecting a stiff power connector.

For the end-user that really depends on what you wanted out of it. For most users it would have been as good as any other board, as long as the on-board graphics was good enough. the ease of CPU configuration would have suited over-clockers the most, but many of them would have preferred having an AGP slot in addition to the on-board graphics. Luckily PCI graphics cards were widely available at the time.