Main » Programming » The Oodle LZNIB Algorithm » New reply
    Alert
    You are about to bump an old thread. This is usually a very bad idea. Please think about what you are about to do before you press the Post button.
    New reply
    Post help

    Presentation

    [b]…[/b] — bold type
    [i]…[/i] — italic
    [u]…[/u] — underlined
    [s]…[/s] — strikethrough
    [code]…[/code] — code block
    [spoiler]…[/spoiler] — spoiler block
    [spoiler=…]…[/spoiler]
    [source]…[/source] — colorcoded block, assuming C#
    [source=…]…[/source] — colorcoded block, specific language[which?]
    [abbr=…]…[/abbr] — abbreviation
    [color=…]…[/color] — set text color
    [jest]…[/jest] — you're kidding
    [sarcasm]…[/sarcasm] — you're not kidding

    Links

    [img]http://…[/img] — insert image
    [url]http://…[/url]
    [url=http://…]…[/url]
    >>… — link to post by ID
    [user=##] — link to user's profile by ID

    Quotations

    [quote]…[/quote] — untitled quote
    [quote=…]…[/quote] — "Posted by …"
    [quote="…" id="…"]…[/quote] — ""Post by …" with link by post ID

    Embeds

    [youtube]…[/youtube] — video ID only please
    Thread review
    Screwtape 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.
      Main » Programming » The Oodle LZNIB Algorithm » New reply
      Kawa's Github