Jr Cartridge blank for eprom

Hardware questions and modifications

Re: Jr Cartridge blank for eprom

Postby Trixter » Sat Feb 04, 2017 3:24 pm

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.
You're all insane and trying to steal my magic bag!
Trixter
 
Posts: 573
Joined: Mon Sep 01, 2008 12:00 am
Location: Illinois, USA

Re: Jr Cartridge blank for eprom

Postby Brutman » Sat Feb 04, 2017 3:58 pm

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.
Brutman
Site Admin
 
Posts: 999
Joined: Sat Jun 21, 2008 5:03 pm

Re: Jr Cartridge blank for eprom

Postby Shaos » Sat Feb 04, 2017 3:59 pm

Brutman wrote: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...
Shaos
 
Posts: 75
Joined: Mon Dec 26, 2016 10:54 am
Location: Long Island, NY

Re: Jr Cartridge blank for eprom

Postby Trixter » Sat Feb 04, 2017 4:10 pm

Brutman wrote: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).
You're all insane and trying to steal my magic bag!
Trixter
 
Posts: 573
Joined: Mon Sep 01, 2008 12:00 am
Location: Illinois, USA

Re: Jr Cartridge blank for eprom

Postby Brutman » Sat Feb 04, 2017 4:16 pm

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
Site Admin
 
Posts: 999
Joined: Sat Jun 21, 2008 5:03 pm

Re: Jr Cartridge blank for eprom

Postby Brutman » Sat Feb 04, 2017 4:19 pm

Trixter wrote:... 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.
Brutman
Site Admin
 
Posts: 999
Joined: Sat Jun 21, 2008 5:03 pm

Re: Jr Cartridge blank for eprom

Postby Trixter » Sat Feb 04, 2017 4:27 pm

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...
You're all insane and trying to steal my magic bag!
Trixter
 
Posts: 573
Joined: Mon Sep 01, 2008 12:00 am
Location: Illinois, USA

Re: Jr Cartridge blank for eprom

Postby Shaos » Sat Feb 04, 2017 4:31 pm

Trixter wrote:
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 :)

Trixter wrote: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...
Last edited by Shaos on Sat Feb 04, 2017 5:03 pm, edited 4 times in total.
Shaos
 
Posts: 75
Joined: Mon Dec 26, 2016 10:54 am
Location: Long Island, NY

Re: Jr Cartridge blank for eprom

Postby Brutman » Sat Feb 04, 2017 4:38 pm

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.
Brutman
Site Admin
 
Posts: 999
Joined: Sat Jun 21, 2008 5:03 pm

Re: Jr Cartridge blank for eprom

Postby Trixter » Sat Feb 04, 2017 4:46 pm

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
You're all insane and trying to steal my magic bag!
Trixter
 
Posts: 573
Joined: Mon Sep 01, 2008 12:00 am
Location: Illinois, USA

PreviousNext

Return to PCjr Hardware

Who is online

Users browsing this forum: No registered users and 4 guests

cron