0 users browsing Programming. | 1 guest  
Main » Programming » The Oodle LZNIB Algorithm
Pages: 1
Posted on 19-01-23, 07:24
Full mod

Post: #88 of 409
Since: 10-30-18

Last post: 12 hours
Last view: 9 hours
The other day I came across a writeup of the Oodle LZNIB algorithm, "an LZ77-family compressor which has very good decode speed (about 5X faster than Zip/deflate, about 1/2 the speed of LZ4) while getting better compression than Zip/deflate".

The bit that particularly caught my eye was near the beginning:

LZNIB can send three actions : literal run ("lrl") , match with offset ("normal match"), match with repeat offset ("rep match").

One of the key realizations for LZNIB is that even though there are three actions, only two are possible at any time.

After Literals :

- LRL should not occur (would have just been a longer LRL)
- match & rep match are possible

After Match or Rep Match :

- rep match should not occur (would have just been a longer match)
- normal match & lrl are possible

Because there are only two actions possible at each point, we can send this using a nibble with a decision threshold value :

Threshold T

- values in [0 , T-1] are action type 1
- values in [T , 15] are action type 2

So the core decode step of LZNIB is to grab the next nibble, do one branch, and then process that action. The values within your threshold group are the first part of your LRL or match len. There are at least two different thresholds, one for {match/rep-match} in the after-literals state, and one for {match/lrl} in the after-match state. In LZNIB we hard-coded the threshold for match/rep-match to 5 as this was found to be good on most data. The optimal {match/lrl} threshold is more dependent on the data.

It immediately made me think of byuu's beat patching/compression format, which has four possible actions because three were needed and the last one was thrown in because it might be useful, and to fill out the 2n bit pattern. beat definitely allows consecutive literal runs; I wonder if it's possible to use the same trick as LZNIB to use a single bit to determine the next action instead of two bits.

The ending of the words is ALMSIVI.
Pages: 1
Main » Programming » The Oodle LZNIB Algorithm
Kawa's Github