10

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.

Improve this question
9
  • 1
    I don't know whether it filtered up from the Spectrum or down from the ST/Amiga but the most popular cruncher and decruncher for the SAM Coupé was definitely Huffman-based. Alas I don't recall whether it also had a predecessor stage in which it applied RLE, or applied a sliding window, or anything like that. But clearly somebody was reading the literature.
    – Tommy
    Jun 21, 2021 at 21:34
  • 1
    Can you point to a specific example of a game that did this? I don't remember seeing any at the time.
    – Chromatix
    Jun 21, 2021 at 21:37
  • 2
    @introspec : Random example: SEAlink, one of several XMODEM extensions with compression, using ARC in mid-80s. Howard Chu's ports (1986) were Huffman encoded LZW. Admittedly, compression in the file transport was not typical -- compress then upload and/or download then decompress were very frequent operation sequences.
    – Eric Towers
    Jun 22, 2021 at 20:03
  • 1
    @introspec : Your comment is broader than the ZX Spectrum: "... proper (lz77-style) compression only became popular in 1990s. I would be extremely surprised to find out that anything apart from RLE could be used during the commercial era of ZX Spectrum in 1980s." Restricting to the ZX Spectrum, X/Y/ZMODEM exists for ZX Spectrum now and XMODEM was available in 1988 (X-LOADER). I recall using SEAlink on the ZX around 1987/88, but I have no link for that.
    – Eric Towers
    Jun 22, 2021 at 21:55
  • 2
    @EricTowers, come on, we have "ZX Spectrum tapes" in the heading, do I really need to pre-empt my every comment with "Talking about ZX Spectrum tapes"? Anyway, talking about ZX Spectrum tapes, many thanks for the information that SEAlink existed on ZX. I did not know about it. However, anything ARC-based would require substantial memory for decompression (for tree etc). It may work in a file downloading utility, but not very likely as part of a game loader. So, I am still very sceptical about prospects of finding games packed using ARC or a similar scheme prior to ~second half of the 1990s.
    – introspec
    Jun 22, 2021 at 22:58

4 Answers 4

Reset to default
16

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.

Improve this answer
6
  • You're right. I think it was from the eastern European demoscene. Edited my question just now to be more precise.
    – forest
    Jun 21, 2021 at 22:59
  • 8
    "Implosion" is the name often given to an LZ78-based compression algorithm, usually LZW, which is not based on Huffman encoding at all. Instead it builds a dictionary of data blocks as they arise in the data, and the encoding is simply indices into that dictionary (which begins with a fixed set of literals and a "clear code"). LZW was used in GIF. It was found that combining LZ77 substring searches with Huffman compression was more effective than LZW, but a Z80 might not be able to decode it while keeping up with the tape.
    – Chromatix
    Jun 22, 2021 at 5:09
  • 2
    @introspec based on finding the "same blocks of bytes" definitely sounds like an LZ approach though.
    – hobbs
    Jun 22, 2021 at 13:39
  • 1
    @hobbs, yes, almost all of them would be derived from LZ77 or LZSS. Much more practical on 8-bit computers. LZW is derived from LZ78 - a very different algorithm that requires a lot more memory during decompression. RLE was also pretty common, but got completely wiped away by the middle of 1990s. The only reason RLE survived for a fairly long time is because many hacker releases were based on Multiface snapshots. This included the full system memory, so unusued memory tended to be filled by zeros and tended to compress well.
    – introspec
    Jun 22, 2021 at 13:45
  • 1
    I've just read the Turbo Imploder decompressor - it is a byte-aligned variation of LZ77 (LZF would be the nearest modern equivalent of it). I'll read MR Pack II as well - I'd surprised to see actual Huffman codes used, but never say never.
    – introspec
    Jun 24, 2021 at 10:22
9

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.)

Improve this answer
3
  • 1
    Many thanks for mentioning Digi Synth demo - this is probably the earliest example of Huffman coding on ZX Spectrum that I am aware of. Do you know any other examples of programs from late 1980s/early 1990s that would use anything different from RLE or LZ77/LZSS style compression?
    – introspec
    Jun 22, 2021 at 10:38
  • 2
    @introspec I have to confess: my greatest hobby was the loader routines, not the compression itself. But as far as I remember, there were no advanced methods of data compression available in the late '80s. RLE was the simplest, LZ was more efficient. There were some optimization approaches, e.g. line reorder for the screen data or RLE with pre-counted value for the best compression ratio.
    – Martin Maly
    Jun 22, 2021 at 11:49
  • @MartinMaly: Did you experiment with using more than two lengths of pulse? I don't know how much wow and flutter cheap tape drive had, but if one could classify pulses as being 1.0, 1.5, 2.0, or 2.5 times the minimum width, and had a uniform distribution of the four pulse widths, that would take an average of 1.75 times the minimum pulse length for every two bits of data stored.
    – supercat
    Oct 5, 2021 at 21:55
8

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

Improve this answer
1
  • 1
    Many thanks for your comment, it is great to see non-trivial examples of RLE being commonly used in the 1980s.
    – introspec
    Oct 4, 2021 at 10:10
2

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.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .