It is currently Fri Aug 18, 2017 5:01 pm

All times are UTC - 7 hours





Post new topic Reply to topic  [ 24 posts ]  Go to page Previous  1, 2
Author Message
PostPosted: Sat Jan 02, 2016 10:51 am 
Offline

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 18798
Location: NE Indiana, USA (NTSC)
Sik wrote:
tepples wrote:
I like to use a unary code, in which each bit of a control word can be 0 for a single literal symbol or 1 for part of previous run, to be fairly efficient on real data and easy to decode to a multiple of 8 bytes. LZSS in the Allegro 4 library and Game Boy Advance and Nintendo DS BIOS uses a variant of this unary code, where each bit of the control word is one way for a literal and the other way for a reference to previous data.

I don't think that qualifies under the definition of unary code you linked, though... (the tokens are always 0 or 1, not a string of bits)

That's because unary coding and run-length encoding are inverses of each other. From an RLE point of view, PB8's repeat coding is a unary code.

0: Run of 1 byte, then change byte
10: Run of 2 bytes, then change byte
110: Run of 3 bytes, then change byte
1110: Run of 4 bytes, then change byte
etc.

Quote:
Also what you've described applies to pretty much nearly every LZ77-based scheme out there

It models the probability of a back-reference as 50%, with the other 50% for a single literal byte, with no dependence on the previous runs. This is equivalent to runs of back-references and runs of literals each having a geometric distribution to their lengths. Unary codes and other Golomb codes are ideal for geometric distributions, with the Golomb code's M parameter depending on the distribution's p parameter. Optimally, M should be close to -log(2)/log(1 - p), with the unary code corresponding to M = 1 or p = .5. Most schemes branded as "RLE", on the other hand, treat all run lengths up to 32 or 128 or whatever as equally likely.

Another option for coding run lengths is the exp-Golomb code. It replaces the unary code for the quotient with the Elias gamma code, resulting in longer codes for values 1 and 3 (runs of length 2 or 4) for shorter codes for longer runs. Exp-Golomb is ideal for power law (Zipf) distributions.

Quote:
(LZSS's particularity is the use of a ring buffer instead of the already decoded data, allowing for more room to reuse strings as repeated strings don't go into the buffer).

Repeated strings do go into the ring buffer, at least in Allegro 4 LZSS (which is equivalent to GBA LZSS with different bit ordering). The use of a ring buffer is to allow encoding or decoding without keeping the entire uncompressed stream in RAM at once. The difference between LZSS and the format described in Ziv and Lempel's 1977 paper is that original LZ77 assumed that all back references would be followed by exactly one literal and potentially have zero length, while LZSS allows back-references to follow one another directly.


Top
 Profile  
 
PostPosted: Sun Jan 03, 2016 3:17 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 492
Guys, please keep compression theory in a separate topic. This topic's intention was to have data on existing open-source compression algorithms' performance on the NES, not to argue what is the theoretical best.


Top
 Profile  
 
PostPosted: Sun Jan 03, 2016 9:25 am 
Offline

Joined: Mon Mar 30, 2015 10:14 am
Posts: 172
if you are interested by LZ4 decompressor, you can find the 6502 implementation here :
http://pferrie.host22.com/misc/appleii.htm


Top
 Profile  
 
PostPosted: Thu Jan 21, 2016 5:18 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 492
Added lz5hc results. It's a new variant, performs worse than LZO in both metrics, but it's liberally licensed.


Top
 Profile  
 
PostPosted: Tue Jun 06, 2017 11:41 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 492
I've made an asm version of lz4 that will probably soon be a part of cc65. Its speed has been posted on the first page, ~7x faster than the C version.

I also made a version that unpacks to VRAM. Rough speeds for a full 1024 nametable:
- rle takes 0.5 frames
- uncompressed takes 1.3 frames
- lz4 takes 2.8 frames

It's slower, but far from being an issue, as unpacking a nametable happens during a black screen anyway. The compression tends to be better than the Shiru version of RLE.


Top
 Profile  
 
PostPosted: Tue Jun 06, 2017 10:53 pm 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 213
Can you post your "samples" the things you compress to make the tests I have some other methods I would like to compare.


Top
 Profile  
 
PostPosted: Wed Jun 07, 2017 1:36 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 492
As mentioned, the base tests were done with the first 768 bytes of the GPL (https://github.com/clbr/nes/blob/master ... /srcdata.h). I can't post the nametable I tested, as it's a part of an upcoming MegaCat game.


Top
 Profile  
 
PostPosted: Wed Jun 07, 2017 3:57 am 
Offline

Joined: Tue Feb 07, 2017 2:03 am
Posts: 213
Code:
Algo         | Ratio  | Speed | License, comments
------------------------------------------------
exomizer mem | 0.5807 | 9.4   | Free to use/modify; needs about 162 bytes of temp RAM, 4 of which need to be ZP

Speed is based upon 143492 cycles for 768 bytes extrapolated to estimated NES speeds. Assumes Not ZP based selfmodifying Next Byte routine, with all variables stored in ZP. Using indirect vector would save RAM but cost cycles, ZP based get next byte would get more speed. Data was packed in reverse with literals.
exomizer 'mem' mode is 446 bytes, the 'sfx' Self extracting program is 696, the RAW decoder used for mem is 189 bytes, with literal support.


Top
 Profile  
 
PostPosted: Wed Jun 07, 2017 10:10 am 
Offline

Joined: Tue Oct 06, 2015 10:16 am
Posts: 492
Added, thanks.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 24 posts ]  Go to page Previous  1, 2

All times are UTC - 7 hours


Who is online

Users browsing this forum: lazigamer and 8 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group