Repository files navigation

fhpack is a compression tool with a singular purpose: to compressApple II hi-res graphics images. It uses a modified version ofthe LZ4 compression format, called LZ4FH ("fadden's hi-res").

I've had an idea for a project involving hi-res graphics compressionfor several years, but didn't do much about it. After learningaboutLZ4, and seeing uncompressors writtenfor the6502 and65816,I decided to see if I could apply LZ4 to hi-res images.

A few hi-res compressors were written back in The Day, usually employingrun-length encoding, which is easy to write and fast to encode and decode.In the spirit of LZ4, I decided to put together an asymmetric codec,meaning compression is very very slow, but uncompression is very very fast.

The result is a modified form of LZ4 that consistently beats LZ4-HC,and generally comes close to (and occasionally beats) ShrinkIt's LZW/II.The decoder is tiny and extremely fast, especially on the 65816 wherethe bulk data copy instructions can be used.

The compressor has two modes, similar to LZ4's "fast" and "high". Thefast mode uses greedy parsing and is not particularly fast, while thehigh-compression mode uses optimal parsing and takes 12 times as long.Both employ simple brute-force algorithms, which we can get away withbecause we're only compressing 8KB of data. The high-compression modedoes about 4% better on average -- not huge, but not negligible.

Other compression programs, such as gzip, produce significantly smalleroutput, but uncompression is much slower and requires more memory.

The comments infhpack.cpp describe the data format. It'sessentially LZ4 modified to work better on a system with 8-bit registers.

There is no implementation of the compression side for the 6502.An implementation that uses greedy parsing is feasible, as the bulk of thetime is spent comparing 8-bit strings that are less than 256 bytes long,and the 6502 series is pretty good at that. The optimal parser couldtheoretically be done on a machine with 128KB of RAM, but would take avery long time to run.

The hi-res screen has a curious interleaved structure that leaves "holes"in memory -- parts of the frame buffer that don't affect what appearson screen. The screen layout is divided into 128-byte sections, with120 bytes of visible data followed by an eight byte "hole". The holestend to be filled with zeroes, though sometimes they may containgarbage or program state.

fhpack can do one of three things with the screen holes:

1. Preserve them. This mode is enabled with the "-h" flag. If youwant the uncompressed data to exactly match the original, youmust specify this flag.
2. Fill them with zeroes.
3. Fill them with a pattern that matches the data immediately beforeor after the hole.

In some cases #2 provides the best results, in others #3 wins.The difference is usual minimal, with outliers in the 70-90 byte range.On modern hardware fhpack runs very quickly, so when not in hole-preservemode the tool compresses everything twice, and keeps whichever approachyielded the smallest output.

The 6502/65816 versions of the uncompressor (source and binaries), aswell as two slideshow applications written in Applesoft and a numberof sample files, are provided on theattached disk images(click "view raw" to download them from github).

There are six disk images. The first three hold the slide show demo:

• LZ4FHDemo.do (/LZ4FH, 140KB) - Source and object code for theuncompression routines, plus a few test images and the Applesoft"SLIDESHOW" program.
• UncompressedSlides.do (/SLIDESHOW, 140KB) - A set of 16 uncompressedhi-res images.
• CompressedSlides.do (/SLIDESHOW, 140KB) - A set of 42 compressedhi-res images.

Toview the demo,put the LZ4FHDemo image in slot 6 drive 1, and oneof the "slide" disks in slot 6 drive 2. Boot the disk and "-SLIDESHOW".Just hit return at the prompt to accept the default prefix.

The slideshow program will scan the specified directory and identify filesthat appear to be compressed or uncompressed hi-res images. It willthen start a slide show, moving through them as quickly as possible.By swapping the compressed and uncompressed disks and restarting theprogram, you can compare the performance with and without compression.(For a 5.25" disk, it's generally faster to load a compressed image anduncompress it than it is to load an uncompressed image.)

There is a second demo, called "HYPERSLIDE", which shows off the rawperformance by eliminating the disk accesses. A set of 15 images is loadedinto just 24KB of memory -- overwriting BASIC.System -- and presented as aslide show as quickly as possible. The demo and selected images are onthis disk:

• HyperSlide.po (/HYPERSLIDE, 140KB)

Torun the demo, putthe disk image in slot 6 drive 1, boot the disk,and "-HYPERSLIDE". If you are running on a IIgs, you may want to try itwith the 65816 uncompressor, which is much faster than the 6502 version.If you want to compute frame timings, you can set an iteration count,and the slide show will beep at the start and end.

A larger set of images is available on a pair of 800KB disks. One diskhas the compressed form, the other the uncompressed form:

• UncompressedImages.po (/IMAGES, 800KB)
• CompressedImages.po (/IMAGES.LZ4H, 800KB)

It's worth noting that the images onCompressedSlides.do take up about135KB of disk space, but are about 104KB combined. The rest of the spaceis used up by filesystem overhead. Storing them in a ShrinkIt archivewould be more efficient, but would also make them far more difficultto unpack.

Running under AppleWin with "authentic" disk access speed enabled,a slide show of uncompressed images runs at about 1.7 seconds perimage (about 0.6fps). With compressed images the time varies, becausethe size of the compressed image affects the amount of disk activity,but it averages about 1.4 seconds per image (about 0.7 fps).

Removing disk activity from the equation, HyperSlide improves that toabout 4.3 fps, with very little variation between files. The decodetime is dominated by byte copies, and we're always copying 8KB, so theconsistency is expected.

HyperSlide incurs a fair bit of overhead from Applesoft BASIC. The"blitz test", included on the LZ4FH demo disk, generates machine languagecalls that uncompress the same image 100x, eliminating all overhead(and simulating what HyperSlide could do if it weren't written inBASIC). The speed improves to 5.6 fps. To put that into perspective,you could unpack a green image twice in the time it takes "CALL 62454"to clear the screen to green.

The most significant boost in speed comes from using the 65816 datamove instructions. With a 65816 implementation, still running at 1MHz,HyperSlide hits 7.7 fps, and BLITZTEST tops 12 fps.

The uncompressor takes as arguments the addresses of the compressed dataand the buffer to uncompress to. These are poked into memory locations$02FC and $02FE. In the current implementation, the output buffer mustbe $2000 or $4000 (the two hi-res pages).

Packed images use the FOT ($08) file type, with an auxtype of $8066(0x66 is ASCII 'f'). These files can be viewed withCiderPress v4.0.1 and later.

I grabbed a set of about 70 images, most from games, a few from early"contributed program" disks. The latter include what look like digitizedscans that don't compress especially well.

All images were compressed with LZ4 r131 in high-compression mode (lz4 -9), NuLib2 with LZW/II, and LZ4FH (fhpack -9). fhpack output has aone-byte magic number, while LZ4-HC has 15 bytes of headers and footers,so for a fair "raw data" comparison the numbers should be adjustedappropriately.

Most source images are 8192 bytes long, some are a few bytes shorter.

Note: test/nomatch is not compressible by LZ4 encoding. fhpack was ableto compress it because it zeroed out the "screen holes". When processedin hole-preservation mode, test/nomatch expands to 8292 bytes.

LZSS, which was used by HardPressed to get reasonable compression withfast decode speeds, reduces the corpus to 243991 bytes (36.7%), making ita viable alternative. It's generally inferior to LZ4 as the maximummatch length and offset are much shorter, but that's not too significantfor hi-res images. Literals are identified with individual flag bits,rather than as runs of bytes, which reduces performance for long stringsof literals.