35 Comments so far

1. 
   Steve - April 28th, 2016 8:56 pm

   I collected some stats on the decompressor’s behavior with my disk image, so I could see the typical block sizes and other things. That may help inform where and how to optimize.

   Each token in the compressed data is one of three things:

   • A marker followed by a (distance,length) pair of previous data to copy. There are 4 marker subtypes.
   • An escaped marker, for when a marker byte itself should appear in the output
   • A literal byte that’s not a marker, and is just copied to the output

   In my data, they appear with these frequencies:

   marker1 "Distant copy" = 44686 
   marker2 "Medium copy" = 53308 
   marker3 "Short copy" = 35166 
   marker4 "Near copy (incl. RLE)" = 12714 
   escaped marker = 4333
   literal byte = 1056435

   There are a LOT of literal bytes, so making that case fast is important. For the 4 types of markers, each will copy a block of bytes from a previous section of the output data. Those blocks can be anywhere from 3 to 128 bytes. I recorded this distribution of block sizes:

   lengths[3] = 26476            
   lengths[4] = 26262            
   lengths[5] = 28504          
   lengths[6] = 17860          
   lengths[7] = 10462           
   lengths[8] = 7217              
   lengths[9] = 4720              
   lengths[10] = 3858             
   lengths[11] = 2872             
   lengths[12] = 2215             
   lengths[13] = 1519             
   lengths[14] = 1351             
   lengths[15] = 967              
   lengths[16] = 1026             
   lengths[17] = 712              
   lengths[18] = 706              
   lengths[19] = 575              
   lengths[20] = 490              
   lengths[21] = 372              
   lengths[22] = 376              
   lengths[23] = 349              
   lengths[24] = 333              
   lengths[25] = 247              
   lengths[26] = 253              
   lengths[27] = 205              
   lengths[28] = 231              
   lengths[29] = 995                         
   lengths[35] = 1043                    
   lengths[48] = 898                       
   lengths[72] = 752                      
   lengths[128] = 2028

   80% of blocks are 8 bytes or less! That makes me question whether unrolling the copy loop or using copy.l would help, or hurt. If those changes required more than a couple of extra instructions for checking the block size and dealing with alignment and tailing bytes, then the extra overhead would probably outweigh the savings for such short blocks.

   On the other hand, even though the number of large blocks isn’t great, there are many bytes in each one. Maybe I should be looking at the total number of bytes in all instances of a given block sizes, rather than just the number of instances of that size.

2. 
   George Phillips - April 28th, 2016 11:54 pm

   LZG’s clever scheme of picking marker bytes depending on the data to reduce expansion certainly makes it harder to have a fast case. When I’ve done custom decompression for 8 and 16 bit CPUs I like use use control bytes that look like “NNNNN FF” which the “F” bits are the function and the N bits are the parameter. I load a byte, then do a right shift and branch on carry which might go to the most common operation which leaves the remaining bits ready to use as a parameter. Or it might go to another right shift which will pick between two more possibilities.

   A 256 entry lookup table to dispatch to the M1, M2, M3, M4 and LITERAL handlers is likely the best way to go. The 68020 has scaled indexing modes so I can see having a 2 instruction decode. My 68000 is very rusty so I’ll write in C pseudo-code:

   d0 = *a0++; // get byte
   goto a1[d0 * 4]; // table lookup with indirect

   If your decompression code can live in the low 64 K of memory the table only needs 16 bit entries.

   And remember to shave off a jump by putting the dispatch at the end of each handler.

   There is the possibility of a faster dispatch, but the cost of instructions and the particular features of the 68020 (especially the small instruction cache) might not make it worthwhile. It goes something like this:

   d0 = *a0++;
   goto a1 + d0 * 16;

   The idea is that every 16 bytes starting at “a1” you have the handler for that byte. Most of them will be literals where they’ll simply copy d0 to the output and then do their own dispatch. Scaled indexing could be a help here as it will do a multiply by up to 8 for you, but 8 bytes may not be enough room to handle a literal. For the others you’d just to a jump to the routine rather than having to expand the (sparse) table of handlers even more.

   But maybe scaled indexing is the way to go. Altering d0 is a pain because the all the handlers will have to undo the shift to use the value. Even if 8 bytes is too tight to put in the dispatch code it could still be better to have a “jmp a2” to return back to the main loop.

3. 
   George Phillips - April 28th, 2016 11:56 pm

   [ A second comment because my first attempt was too long. ]

   Wikipedia claims the 68020 does not have data alignment constraints so you could likely take advantage of that. Unaligned access is more expensive but generally the penalty is easily worth it. However, beware the “RLE” copies where the back pointer is shorter than the length. Those are overlapping and usually must be done a byte at a time to work properly. I guess that only matters for M4 “near copy” operations.

   I also see the 68020 has a 256 byte instruction cache. That might work against schemes which unroll or otherwise use too much code.

   Concerning the inner copy loops, the scaled indexing modes with PC-relative addressing can pretty quickly go into a series of “*a3++ = *a0++;” instructions so you can unroll them without much overhead. I imagine some optimized “memcpy()” code for 68000 would be a good reference.

4. 
   MagerValp - April 29th, 2016 3:45 am

   I’m not a 68K assembly language guru, but I know where to find them: http://ada.untergrund.net/?p=boardforums&forum=4

   Forgive me for saying so, but lzg doesn’t seem to be particularly well designed. It’s using whole bytes for markers when two bits would suffice, and as you note it only has single byte literals (rather than a byte count). I’d say ditch it and design something yourself. There’s no reason a simple byte based LZ scheme shouldn’t approach memcpy in speed – I’ll second George’s suggestion to see if you can find an optimized implementation to work from. I’d also investigate keeping the compressed stream word aligned, the compression hit shouldn’t be too bad and it could help a lot with performance. I’d start playing with a stream format along the lines of:

   # 00000000’00000000 EOF
   # 00cccccc’cccccccc 14-bit literal string
   # 01cccccc’bbbbbbbb 6-bit RLE count, 8-bit byte
   # 11ccccoo’oooooooo 4-bit count, 10-bit offset
   # 11cccccc’cccccccc’oooooooo’oooooooo 14-bit count, 16-bit offset

5. 
   Steve - April 29th, 2016 6:33 am

   Yeah, maybe lzg isn’t the best choice, and really I have no experience at all with compression algorithms. I did implement a lookup table to see if a byte is a marker, and it gave a roughly 15% speedup. A jump/dispatch table that branches to the right handler for the marker or literal should be faster still. But I’m looking for a 2-4x speedup if possible, so something more drastic is probably needed. A block copy of the entire uncompressed disk image into ram is plenty fast (under a second, I haven’t timed it exactly) so I know the memory bandwidth is enough at least.

   My instinct is that having literal strings that aren’t a whole number of bytes would be problematic and too slow, though I may be wrong. In MagerValp’s suggestion above, maybe replace the second line with:

   # 00cccccc Next count bytes are a literal string

   I think that would be faster to decode, but might kill the compression ratio.

   George’s faster dispatch idea looks cool, but unless I’ve misunderstood, it would require the marker bytes to be known at compile time, or else require an additional level of indirection.

   For the inner copy loops, the source code for Apple’s 68K BlockMove is here: http://toddp.com/classic/Software%20Install/Apple%20Source%20Code/System%207.1%20Source/OS/MemoryMgr/BlockMove.a But I’m not sure if there are really enough long block copies to make something like that worthwhile.

   68020 has a 256-byte instruction cache. 68030 (most of the machines this will be used with) has a 256-byte instruction cache and 256-byte data cache.

   The problem with all my projects is that there are so many interesting sidelines and diversions, I begin to lose track of whatever I meant to accomplish in the first place!

6. 
   Steve - April 29th, 2016 6:36 am

   Also, making the compressor deal with alignment is a good idea. In general, the compressor can do a lot of hard work to optimize the decompression step, given intimate knowledge of the decompression routine’s implementation.

7. 
   MagerValp - April 29th, 2016 7:10 am

   LZ is so much fun though 🙂

   If you want a simple compression scheme to start playing with, you can look at the one I did for 6502:

   https://github.com/MagerValp/u4remastered/blob/master/tools/backpack.c
   https://github.com/MagerValp/u4remastered/blob/master/src/u4loader/lzmv.s

   It uses the following markers:

   # 00000000 EOF
   # 00cccccc 6-bit literal
   # 01cccccc 6-bit RLE
   # 1cccoooo’oooooooo 3-bit count, 12-bit offset

   It should be relatively easy to extend it to work on 16-bit words.

8. 
   MagerValp - April 29th, 2016 7:13 am

   Another thought: is it necessary to decompress the entire disk image in one go, or could you decompress tracks on the fly as needed? Total decompression time might be higher, but it would eliminate the long wait.

9. 
   Steve - April 29th, 2016 8:36 am

   Thanks, I’ll definitely check that out! Decompression on the fly is definitely a possibility too, and maybe my time would be better spent there than on inventing a new compression scheme. But it would replace a single delay at bootup with overall slower disk performance, at least for the first time any disk sector is read.

   I added a proper timer instead of measuring performance with my wristwatch, and here’s where things stand after removing the safety checks and adding the isMarker lookup table:

   Mac IIci BlockMove (for 2MB block) = 6761K/sec
   Mac IIsi lzg decompress = 583K/sec
   Mac IIci lzg decompress = 898K/sec
   MESS Mac IIci emulator lzg decompress = 858K/sec

   I’d like to reach about 2000K/sec on the IIci, but not sure if that’s realistic.

10. 
    Eric - April 29th, 2016 9:53 am

    Haven’t looked too closely at it, but what about this LZ4 format? There’s a C reference version, and assembly decompressors for 6502 and 65c816

    http://cyan4973.github.io/lz4/

    More on the 65c816 version
    http://www.brutaldeluxe.fr/products/crossdevtools/lz4/index.html

11. 
    George Phillips - April 29th, 2016 11:11 am

    Steve, my faster dispatch idea was predicated around generating the handler code into RAM. Then the markers don\’t have to be known at compile time nor do you need an extra level of indirection.

    I agree with Eric that LZ4 permits a faster implementation. Seems worthwhile to try compressing the hard disk image with LZ4 just to see if the compressed size is acceptable. I\’d tweak the LZ4 compressor to store offsets in big-endian format to save time and a big of code.

    Can you reach 2000K/second on the IIci? At 25 MHz that\’s 12.2 cycles/byte on average. A straightforward implementation will need one \”move.b (a0)+,(a1)+\” instruction for each byte. Seems to be no easy way to estimate instruction timing. The 68020 manual said maybe best case 6, worse case 9 cycles, best I could tell. That leaves very little time to decode though unrolled copy loops help here as decoding overhead isn\’t per-byte but per code. You could measure an unrolled byte copy loop to see how fast that is. If it runs slower than 2000K/second then it looks dubious without resorting to more complex code using word and long moves. If significantly faster then it might well be attainable.

    A slightly more complex model of the program would give a better feel for feasibility. Say estimate the cost of dispatch, multiply by the number of commands and add in the cost per byte and see what that requires.

12. 
    Eric - April 29th, 2016 11:55 am

    And there’s some Atari ST 68k assembly for LZ4 here, and I’m sure elsewhere too.

    http://www.atari-forum.com/viewtopic.php?t=26825

13. 
    rasz_pl - April 29th, 2016 12:26 pm

    try different algorithm?
    https://github.com/Cyan4973/lz4 seems to achieve ~0.3 speed of ram when decompressing

14. 
    rasz_pl - April 29th, 2016 12:28 pm

    note to self: refresh page before commenting 🙂

15. 
    Steve - April 29th, 2016 12:52 pm

    As I look more carefully at lzg, even within the marker format it defines, I don’t think the compressor makes the best choices as to how to compress. Consider this sequence:

    AA AA AA AA AA 00 AA AA AA AA AA AA AA AA AA AA

    should compress as

    AA M4_backref(d=1,l=4) 00 AA M4_backref(d=1,l=9)

    where each M4_backref is 2 bytes. So that’s 7 bytes. But instead it does:

    AA M4_backref(d=1,l=4) 00 M4_backref(d=6,l=5) M4_backref(d=1,l=5)

    which is 8 bytes. It seems when it encounters a long string that could be RLE encoded, it prefers to encode it as multiple backrefs to shorter substrings rather than a single longer RLE. I see why that’s so, but not sure how to fix it. At the time when it’s evaluating the first AA byte in the second group of AA’s, its only choices are to emit an AA literal or a backref(d=6,l=5). The backref looks like the better choice at that point. Only by applying some look-ahead logic could it see that a better “delayed gratification” choice exists.

16. 
    Eric - April 29th, 2016 2:38 pm

    I think the fix for that is the “optimal parsing” approach to parsing. Requires more time/space in compression, right?

17. 
    Steve - April 29th, 2016 2:55 pm

    Probably, though I’m not exactly sure how that would be implemented in the general case. I tried adding some code that checks if the current position is the start of a run, and if so whether the length of that run is longer than the length of a previous match that could also be backref’d from that position. It seems to work and it fixes the simple example I gave above, but on real data it only improved compression by 0.01%. 🙁

18. 
    uridium - April 29th, 2016 4:42 pm

    Are you enabling the cache on the 020 / 030? You need to turn bit 0 on in the CACR or it’s off by default. Same goes for the 030. The 030’s burst-fill mode will probably be most useful when experimenting with memcopy() type routines on the IIsi as you can move four contigious per op.

    I’m coming from an amiga background, so please excuse the n00b’ness.

19. 
    uridium - April 29th, 2016 4:43 pm

    oh.. this is nice. Yay google.

    https://winuae-mod.googlecode.com/svn/tags/winuae_2_0_2/!docs/Cache%20programming.txt

20. 
    David Kuder - April 29th, 2016 9:01 pm

    I would investigate other compression schemes, maybe one which separates the markers and literals completely except for small blocks of less than 32 bits, and optimizes for blocks of 32bits that are aligned for optimum use of move.l?

21. 
    Steve - April 29th, 2016 10:20 pm

    Oy, this is getting too deep in the weeds. The point was never to design the perfect compression algorithm, but to load this rom disk faster, and I think I’m losing focus. I decided I didn’t want to start over again with a new algorithm, so I’ve just concentrated on making optimizations to lzg.

    I’ve made two big changes:

    1. The inner copy loop does some loop unrolling and (unaligned) long and word-sized moves as well as byte-sized moves, which gives a 10% speedup. This could probably be further improved.

    2. I prefix each string of literals with a byte for the string length, so they can be copied in a fast loop without testing each byte to see if it’s a marker. This gave a further 35% speedup, but it made the compression ratio worse. Now the compressed file is 68% of original size instead of 63% for the original lzg implementation. (For comparison zip achieves 58% on the same data.)

    Decompression speed is now 1470K/sec on the IIci.

    Instruction and data caches are already on, thanks to Mac’s init code.

    I’m still not doing anything in the compressor to try to align the input or output to word or long boundaries. And I’m still reading the input and copying literal strings one byte at a time instead in words or longs. There are probably some decent speedups still to be had there.

    I don’t know how much of the lost compression ratio can be won back. Adding an extra byte to each string of literals is expensive. Maybe I can make the markers smaller somehow – I think there’s a possibility. But I’m really tired and need to put this away for a while before my head bursts.

22. 
    Mikko Ohtamaa - April 30th, 2016 3:53 pm

    Do these CPUs allow self-modifying code like x86? This was a trick many CPU intensive loops in games used by the time. Unlike modern machines, there was little or no penalty to modify code in fly because there was no heavy RAM cache. This could replace some jump table parts in a clever design.

23. 
    Steve - April 30th, 2016 4:51 pm

    I’m not certain. I think self-modifying code is OK, but you have to explicitly flush the instruction cache.

24. 
    Paul C. Pratt - April 30th, 2016 8:07 pm

    I like MagerValp\’s idea of decompressing a sector at a time, if what you are doing is implementing your own disk driver that reads from compressed ROM. If you decompress the whole thing at once, I would assume you would need to allocate RAM for the whole uncompressed disk. Just decompressing the sectors as they are asked for would not need any extra RAM. The operating system is designed to be usable when booted off floppy, so it will still feel very fast booting from ROM, even with almost any sort of decompression code.

25. 
    Anon - April 30th, 2016 10:58 pm

    Could any of this compression be applied to ROM disk in your ROM-Inator product? It would be nice to have more than a megabyte of ROM disk space to work with!
    Decompression on the fly? That way it need not be held in The tiny amount of RAM contained in a 128k/512k?

26. 
      - May 1st, 2016 3:39 am

    You’re probably already doing that, but if you prefix each literal string by its length, don’t forget that you then don’t need to escape bytes that could be considered markers.

27. 
    Jeff - May 2nd, 2016 3:06 pm

    The Mac Classic ROM contained a bootable copy of MacOS 6.0.4 – just hold down Command-Option-X-O at startup.
    Perhaps crib some compression tips from there?

28. 
    Anon - May 3rd, 2016 9:08 pm

    There was compression in the Mac Classic ROM disk? That’s news to me!
    Is there evidence of this anywhere?

29. 
    Steve - May 3rd, 2016 9:14 pm

    I don’t believe the Mac Classic rom disk is compressed. But it is stored in a super-efficient way, with toolbox code that’s already in the main rom not duplicated in the System file of the disk image.

30. 
    Paul C. Pratt - May 3rd, 2016 10:38 pm

    I notice that there is a _UnpackBits call at offset 3E454 in the Mac Classic ROM, inside the EDisk driver. And that looking at a random location somewhere in the middle of the 256k data for the ROM disk, and the corresponding section of the 400k mounted ROM disk, it looks like it could be in PackBits format. Which is a kind of compression, a rather simple one. I don\’t remember noticing that before.

31. 
    Anon - May 4th, 2016 3:04 am

    So there may already be a compression algorithm resident in the ROM disk driver that has been reused in the ROM-inator AND in the IIsi ROM?

32. 
    Anon - May 4th, 2016 5:50 am

    If the Macintosh Classic was using PackBits on its disk image: was it decompressing on the fly? Or was it unPacking into RAM and running from there?
    If it was on-the-fly: no-one ever complained about access speed on the Mac Classic ROM disk before!

33. 
    Stephane.D - May 10th, 2016 12:42 am

    I’m doing development on a 68000 based system (Megadrive) and I recently designed a derived version of LZ4 compression to take benefit of data word alignement on 68000 CPU as i really wanted to have “live GFX data decompression”.

    I originally used the classic LZ4 implementation with the best optimized assembly code i could do for decompression and i obtained about 250-360 KB/second of decompressed data on a 7.7 Mhz 68000.
    With my new LZ4W compression scheme i was able to obtain 600 up to 950 KB/second on a simple 7.7 Mhz 68000, i think there is no faster decompression algorithm on the 68000, at least i was not able to find one.

    The compression level is almost as good then LZ4 for small packet of data but get worst for larger one.

    Still you can give a try in your are interested in. You can find here the compressor (wrote in java) and the 68000 assembly decompressor :
    https://www.dropbox.com/sh/smgwbi8g6y50n60/AAC47jpBZKxPqeY_NXo703vQa?dl=0

    To obtain that decompression speed i had to heavily rely on lookup table so the decompression code is not really small (probably ~4 KB in binary format).

34. 
    denis - February 24th, 2019 2:28 pm

    Hi

    You can change the end of marker1 to this to safe 6 cycles:

    move.b (a5,d6.w),d6
    lsl.w #3,d5
    move.b (a0)+,d5
    lsl.l #8,d5
    move.b (a0)+,d5
    add.l d0,d5

    Denis

35. 
    denis - February 26th, 2019 5:22 am

    Hi

    found another one:

    all the jumps back to _mainloop with bcs jumps then to bcc _fail. this it not necessary. simply jump to the next line after _mainloop.

    Denis

Leave a reply. For customer support issues, please use the Customer Support link instead of writing comments.