Jr Cartridge blank for eprom

[Trixter]

You're at a disadvantage using LZW anyway, since it was determined many moons ago that LZ77 beats it in most general cases if you run the codes it produces through an order-0 entropy reduction scheme (like huffman, range coding, or arithmetic coding).

Recent developments in Jarek Duda's ANS theory has created an entropy coder that matches the efficiency of arithmetic coding but with very simple decoding. I haven't put any effort into trying to make an 808x version, but it should be possible for the enterprising hobbyist with time on their hands.

[Brutman]

That's kind of an apples to oranges comparison, isn't it? If I interpreted that correctly, you are comparing LZ77 with something like Huffman encoding compared to straight LZW. It would be more fair to compare it to LZW with Huffman encoding.

[Shaos]

I'm not going to win this competition anytime soon ... my general LZW algorithm took 147456 bytes of input and produced 132797 bytes of output. Which is reasonable considering the binaries look like random data, but not great when simple heuristics that take advantage of the structure of binaries can beat it.

My output codes are fixed at 12 bits long, so I have to overcome a 50% penalty right from the start. If I had the variable bit rate part done I would expect most of the output codes to be 9 bits for this file size, thus taking another 25% off of my output size.

Yes, 132K is not good - because by simply replacing sequences of zeros by 00-00-00-XX-YY as I did before I got 130K
Do you have a limit for length of the word for your dictionary?
May be you should add RLE of some sort into your algorithm, because LZ77 covers RLE naturally and LZ78/LZW do not, if I understand things correctly...

[Trixter]

That's kind of an apples to oranges comparison, isn't it? If I interpreted that correctly, you are comparing LZ77 with something like Huffman encoding compared to straight LZW. It would be more fair to compare it to LZW with Huffman encoding.

My bad -- I jumped the gun a little, because I was thinking of something I didn't write down (sorry!) Storer and Szymanski showed in 1984 that an LZ77 scheme using optimal parsing, plus an efficient encoding of the length-offset pairs, can beat LZW. So a good LZ77 implementation (like LZ4 with optimal parsing) will beat LZ78 (like LZW) every time. What I THEN tried to write down in my reply was "oh, and even a bad LZ77 implementation will beat LZW if you run the codes it produces through an entropy encoder". Sorry for the confusion.

I blame sickness (I have a bad ear infection and body aches ATM).

[Brutman]

It's pure LZW and with the fixed 12 bit output codes it's at a terrible disadvantage. I really need to get the variable bit coding done/working.

The maximum string length is 48 bytes. So for text logs like what my HTTP server generates, it works great ... but for small files that look relatively random it is going to be terrible.

RLE would certainly improve it, but then there would be an analysis pass required to figure out if the next section of bytes should be LZW or RLE encoded. An RLE encoding pass up front might be a nice optimization, especially for executables.

[Brutman]

... I blame sickness (I have a bad ear infection and body aches ATM).

No problem at all. I'm am actually kind of delighted that we have three people talking about compression algorithms for a hobby project on a Saturday morning. ;-0

My intent with LZW was to stretch the brain a little bit and create a library that I can use to compress my text logs on the fly with. So far I've basically re-implemented Unix compress without the variable bit rate. Implementing LZW using the Wikipedia description was a bit of a brain stretcher; I'm getting out of practice.

[Trixter]

I'm always down for talking compression, although all of my experience coding actual implementations have been extremely asymmetric (decompression speed is king, compression ratio is secondary, compression speed is not a concern). Your needs are the complete opposite from mine as you're performing compression live on the hardware. For that, I think LZW is a better choice than LZ77 (which makes sense, since IIRC LZW was created primarily for streaming to tape).

You mentioned the maximum string length is 48 bytes -- Does that mean you are resetting the dictionary on every new string? That is going to destroy your compression ratio, since (in web logs) there is very high commonality from one line to the next...

[Shaos]

LENGTH is 1 or 2 bytes:
1xxxxxxx - for 4...131
01xxxxxx - for 132..195
00xxxxxx xxxxxxxx - for up to 16383

If you care about decomp speed, you might want to put codes at the end instead of the beginning. For example, 1xxxxxxx means this is necessary:

Code: Select all

cmp al,10000000b
je handle_1
...
handle_1:
and al,01111111b
add al,4


But if you change your codes to be at the end, you can do this:

Code: Select all

shr al,1
jc handle_1
...
handle_1:
add al,4


This is both smaller and faster on 8086. It shifts the bits into carry and jumps based on carry bit, and when you're finished you don't need to adjust the value as it is already in the correct format.

Hm, interesting, so it will be
xxxxxxx1 - 4...131
1xxxxxx0 - 132...195
and 0xxxxxx0 xxxxxxxx - any other number up to 16383?
Actually, I think in my case masking is NOT required to get rid of highest 1 - just add 84H instead of 04H and it's gone

EDIT: I just thought of another optimization: Don't use FF for the code; instead, use the value that shows up the least. Scan the entire file before compressing to determine which value shows up the least, then use that as the code. Otherwise, data that has a lot of FFs in it (like most 8-bit programming!) won't compress very well...

I don't think I'll get a lot by switching to rarest byte - usually a lot of FFs will be successfully eaten by LZ77, but I can at least estimate using outputs from my current design to see possible impact of that...

P.S. So I took results of compression of JRCARTS7.IMG and count number of literals FF that was coded in:

Code: Select all

> grep "\[255\]" JRCARTS7.out
[255] 0xFF ? = 218
[255] 0xFF ? = 175
[255] 0xFF ? = 140
[255] 0xFF ? = 39
[255] 0xFF ? = 62
[255] 0xFF ? = 98
[255] 0xFF ? = 159
[255] 0xFF ? = 240
[255] 0xFF ? = 140
> python
Python 2.5.2 (r252:60911, Jan 24 2010, 18:51:01)
[GCC 4.3.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> 218+175+140+39+62+98+159+240+140
1271
>>> 112715-1271
111444
>>> 100.0*1271/112715   
1.127622765381715


so by switching to rarest byte I'll get extra 1.2KB (-1.13%) so 112,715 will turn into 111,444 - from one hand it's better, from other it's not too much yet to convince me to get rid of FF at the name of my compression utility (it's SHAFF because of FF : ) - it's still a little far from ZX7 and RNC method 2...

[Brutman]

Oh no, not at all. Just that I won't let a string grow past 48 bytes. If you try to add a 49th byte to a string it punts - it outputs the current code for the current 48 byte string that just got built up and then outputs one of the cardinal 0-256 codes to start a new string.

You can do the same thing if you choose not to clear the dictionary when it fills. Wiping out the dictionary when it fills can be expensive because you have to build the dictionary up again. In a highly repetitive file (like a log?) that might not make sense. General algorithms will clear the dictionary when it fills because they want to be able to adapt to different parts of a file.

The 48 byte limitation was pretty arbitrary. I just wanted to make sure that when I reserved buffer space that I had didn't cause overruns. Also, string length adds to decoding time because I did not store all of the strings in the dictionary; I used the space saving trick where a longer string holds just its new byte and points back to the previous string for the rest of string. It's very space efficient but it's a pain during decode; I have to rebuild the output string in reverse order. Based on my sample files, 48 byte strings are *very* rare .. usually the dictionary fills before you can find that kind of repetition.

[Trixter]

Code: Select all

1xxxxxxx - for 4...131
01xxxxxx - for 132..195
00xxxxxx xxxxxxxx - for up to 16383


Meaning, I'd change it to this:

Code: Select all

xxxxxxx1 - for 4...131
xxxxxx01 - for 132..195
xxxxxx00 xxxxxxxx - for up to 16383


That way you can shift-and-branch and the value is already in the correct format once you get to the code that handles it.

If you ever find yourself with many more codes (16 or more), a jump table might be better; something like this (paraphrased from the interrupt handler I wrote for 8088 MPH):

Code: Select all

        xor     bx,bx
        mov     bl,code
        and     bl,7 ;to protect against bad input
        shl     bx,1 ;to match 16-bit offset alignment
        jmp     [cs:jumptable+bx]
...
jumptable       dw offset housekeeping
                dw offset signalready
                dw offset checkexecution
                dw offset returnarea
                dw offset vintcontrol
                dw offset musiccontrol
                dw offset usertickcontrol
                dw offset installcheck