It is currently Fri Sep 21, 2018 9:53 pm

 All times are UTC - 7 hours

 Page 2 of 2 [ 24 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: Compression benchmarksPosted: Sat Jan 02, 2016 10:51 am

Joined: Sun Sep 19, 2004 11:12 pm
Posts: 20562
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

 Post subject: Re: Compression benchmarksPosted: Sun Jan 03, 2016 3:17 am

Joined: Tue Oct 06, 2015 10:16 am
Posts: 796
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

 Post subject: Re: Compression benchmarksPosted: Sun Jan 03, 2016 9:25 am

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

Top

 Post subject: Re: Compression benchmarksPosted: Thu Jan 21, 2016 5:18 am

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

Top

 Post subject: Re: Compression benchmarksPosted: Tue Jun 06, 2017 11:41 am

Joined: Tue Oct 06, 2015 10:16 am
Posts: 796
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

 Post subject: Re: Compression benchmarksPosted: Tue Jun 06, 2017 10:53 pm

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

Top

 Post subject: Re: Compression benchmarksPosted: Wed Jun 07, 2017 1:36 am

Joined: Tue Oct 06, 2015 10:16 am
Posts: 796
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

 Post subject: Re: Compression benchmarksPosted: Wed Jun 07, 2017 3:57 am

Joined: Tue Feb 07, 2017 2:03 am
Posts: 579
Code:
------------------------------------------------
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

 Post subject: Re: Compression benchmarksPosted: Wed Jun 07, 2017 10:10 am

Joined: Tue Oct 06, 2015 10:16 am
Posts: 796

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 24 posts ] Go to page Previous  1, 2

 All times are UTC - 7 hours

Who is online

Users browsing this forum: Google [Bot] and 2 guests

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

Search for:
 Jump to:  Select a forum ------------------ NES / Famicom    NESdev    NESemdev    NES Graphics    NES Music    Homebrew Projects       2018 NESdev Competition       2017 NESdev Competition       2016 NESdev Competition       2014 NESdev Competition       2011 NESdev Competition    Newbie Help Center    NES Hardware and Flash Equipment       Reproduction    NESdev International       FCdev       NESdev China       NESdev Middle East Other    General Stuff    Membler Industries    Other Retro Dev       SNESdev       GBDev    Test Forum Site Issues    phpBB Issues    Web Issues    nesdevWiki