Compression techniques used in old ZX Spectrum tapes

Question

Many ZX Spectrum games^* (and demos) would improve loading time and save space in the tape using rudimentary compression. During decompression, the game would display "decrunching" for several seconds. What compression algorithm was typically used? Was it simple RLE?

How did this typically compare with the technique of XORing the tape with a repeating value to reduce the number of 1 bits (which took 3420 T-states to read; 0 bits took only 1710 T-states)?

_{* I'm mostly talking about those made in the Russian hacker and demoscene, not mass-marketed commercial games.}

Answer 1

I don't recall any mass-market commercial software for the Spectrum using the term "decrunching" - I'd associate that more with the demo and cracking scenes of central and eastern Europe, and my guess is that the software you saw originated from there. Around the early 1990s there were a few compression tools in use in that community, and while there's not much detailed documentation of the algorithms they used, there are a few clues to hint at something more advanced than RLE:

• Turbo Imploder - the instructions (via Google translate) describe the "implode" mode as "extremely efficient compression based on the search method the same blocks of bytes", which sounds like Huffman encoding;
• Mr.Pack II - as per the screenshot, this offered a "huffman - yes/no" option.

In more recent times, cross-development has opened up possibilities for more advanced compression algorithms, with the host machine doing the "heavy lifting" on the compression side while the decompressor is still simple and fast enough to implement in Z80. Among the current state of the art is Shrinkler and LZSA.

Answer 2

As far as I know, there were two main approaches to compress the data. The first one, more common, was to load the whole code and "de-crunch" it. It uses RLE or simple vocabulary algorithm (LZ-like). RLE was pretty common to compress screen (there is a lot of zero sequences in many cases).

The second one, less common, performs decompression during the loading. The best example I remember (Digi Synth demo) uses the Huffman-coded data and its loader decompresses its data on the fly. But RLE is suitable for this case too.

I should mention that some tape-copy programs use on-the-fly compression and decompression to fit the most data into the limited memory of ZX Spectrum (TF-Copy, BS-Copy, etc.) The most common compression method for that was the RLE, mentioned above.

I never met a software that uses the second method you mention to reduce 1s. The typical Z80 machine code has a pretty big "entropy", so XORing cannot reduce the number of 1s in any significant way. A more efficient way was to use a custom loader routine with some kind of "turbo" approach (typically shortens the length of pulses), but it has some disadvantages too (higher sensitivity to tape errors, etc.)

Answer 3

I wrote the compression routine use by the Multiface on the Spectrum and Amstrad machines. It was a plug in unit that would save all memory to tape and allow you to continue your game where you left off. Not at all to be used for piracy of course. I asked the makers, Romantic Robot, if it did any compression or just saved masses of zeros for a 16k game. It didn't do any compression, which added a lot of loading time for 16k games. I said I had some code that could do it in about 250 bytes, they told me they had about 120 spare. That's when I discovered the LDIR and CPIR commands. Basically my code would only look for a sequence of >8 identical bytes, and replace them with a 5 byte marker, the byte being repeated and the repeat count. The marker was a series of bytes I thought highly unlikely to appear as attributes, bitmap code, text, or assembly. So a very simple technique but it still saved a lot of loading time

Answer 4

For what it's worth, "decrunching" (and the opposite, crunching) appears to be a relatively common slang term for decompression on load on from the time when these systems were popular and is even still used in the current retrocomputing scene (see, for example, this demo from 2015.

The Wikipedia page for Amiga Software mentions it as having originated on the Commodore, at least a specific algorithm that involves using video memory as temporary storage - and this seems to have started the tradition of displaying "decrunching" along with possibly an animation.

Answer 5

In the old days I looked into lots of game loders, so there was no 'decrunching' and no depacking in any original game software. Only turbo-loaders (like Speedlock, Alcatraz protections 'loading schemas') and special loading routines for 'loading screens' that didn't load all 6912 bytes directly. Just take a look at Alcatraz protected screens, which load screens nicely. But, yes, this may increase data size because it may not fill the whole screen. If this is the kind of compression you mentioned, ok, but actually it's a different screen format.

While the earliest pirate copies (e.g. from Bill Gilbert) at the end of the '80s and earliest '90s had some primitive RLE's. They also started to pack loading screens (laser compact or something like this - do not remember that old stuff). Some cool screen loaders also appeared on cracked versions of the games. Just take a look at cracked 'Foxx Fights Back' (don't remember what crack: it was in Bill Gilbert's or S.S. Captain's crack).

Since those times on, crack- and demoscene people started to pack everything, except some individual people. E.g. one Moscow guy made lots of game cracks, Softstar. Until the second half of the '90s he didn't use any packers to reduce the size of his TR-DOS versions. Just take a look at large images like Stormlord (Softstar '93) 269 TR-DOS sectors length: only cracktro, XOR-protection on loaders, but no depacking here. Not a big deal to sell fewer programs on 5.25" diskette because of their size, right? :)

The oldschool demosceners and system programmers brought lots of compressors since the '90s: KSA code cruncher (LZSS), megalz, hrust, hrum, rip... and that's not a complete list. But none of these listed packers were used originally by game developers in the '80s and early '90s. Some game developers pack their messages in text adventures using not ASCII, but 7 or 6 bit encodings. Some of these words were tokenized. Sometimes developers packed their graphic slides in adventures by programming lines and textures. In the '80s there were some examples of graphic slide programming (that you could call 'procedural output graphics'), but they were all quite primitive, although they saved memory. That's all in those days.

About packers since the '90s till nowadays, here is a visual comparison of all known compression algorithms on the ZX-Spectrum alongside 7zip on PC:

In my Speccy days there was no 7zip depacker on the ZX-Spectrum. But, yeah, depacking PKZIP and RAR is possible on the ZX-Spectrum.

You can also read some articles about packing on the ZX-Spectrum:

• Packing on the ZX-Spectrum: MegaLZ (machine translation from Russian).
• Data compression for modern Z80 encoding (machine translation from Russian).

As for me, in the old days after hrust packer I started to pack with rip: slower, but smaller size. Sometimes with handmade RLE because of unpacked block size limits, but sometimes also with handmade delta pack because of two code block with small differences. You should use some pre-processing tricks when your unpacked code block size is about #A000 bytes, or you have two equal code blocks with some differences (e.g. 48k and 128k versions of game).

Now let's move to the term 'decrunching'. If you mean self-modifying code, or prebuilt code for non-cycled outputs there were earlier examples from the '80s. I don't really know who was the first, but isometric 3d engines from Ultimate Play The Game was cool for the middle of the '80s (especially Bubbler). Some of them had non-cycle output program routines.

If you mean self-modifying code, or pre-built code for non-cycled outputs there was earlier examples from 80s. I don't really know who was the first, but isometric 3d engines from Ultimate Play The Game was cool for the middle of 80s (especially Bubbler). Some of them had non-cycle output program routines. But most of them was made without initialization, so if you wish LDI command 16 times instead of LD BC, 16: LDIR these games had 16 LDIs after the loading already. This is a quite simple example to show you why 16 LDIs is better than one LDIR:

# Copy block using one LDIR command:
LD BC,16                                          # 10 tacts
LD HL,<start address of code block to copy from>  # 10 tacts
LD DE,<start address of code block to copy>       # 10 tacts
LDIR                                              # 21 tact per one byte copy * 16 = 336

# Copy block using 16 LDI commands:
DUP 16                                            # start of duplicating command
LDI                                               # 16 tacts
EDUP                                              # 16 tacts per one byte copy * 16 = 256

So 336 vs 256 CPU tacts. That's the reason to use non-cycled output program routines.

Of course real examples of 'decrunched' (or initialized self-modifying code) routines can be more complex:

# Put 4 bytes 8 times
LD SP,<address on the screen>
LD HL,<two bytes of data 1>
LD DE,<two bytes of data 2>
DUP 8
PUSH HL
PUSH DE
EDUP

Lots of 'plasma' demo effects output data like in this example. But I find it difficult to remember at least a few games from the '80s that output graphics through the machine stack. At the same time demoscene products started to use initializing and self-modifying code from the early '90s. For example, Shock megademo from ESI (see on YouTube). But the longest decrunch in the '90s was in the 3d tunnel part of Insult megademo (you can see them on YouTube, but I'm not sure that it wasn't cut). You can also check crack intros from 'Mafia Private corporation', a demoscene team, they had long decrunches.

In the second part of the '90s and '00s demosceners got rid of long "decrunches" for the sake of action and drive. Now loading a part of data again from floppy is faster than pre-calculating everything. Although this is not the case for intros and some demos, most demos Went that way. These days some guys decided to decrunch or "unpack" some data on the go. Why not if you have a special format for it? Take a look at 'chunked' colour animation with bubble Weed demo by Triebkraft (YouTube). Each frame is divided into some chunks, which are stored in their own format. Is it a unique technique to save memory? Or "decrunching on the go"? There are other examples of how for the last 30 years the retro demoscene has only been trying to efficiently use the already small amount of RAM, doesn't matter if it's RLE, modern Exomizer and Shrinkler or animation store technique.