Results 1 to 5 of 5

Thread: Compressing small packets

  1. #1
    Member
    Join Date
    Sep 2010
    Location
    US
    Posts
    126
    Thanks
    4
    Thanked 69 Times in 29 Posts

    Compressing small packets

    Say you need to compress some small packets for sending over a network. Not actually TCP packets but app data packets, of size 1-64k, average size around 16k.

    The channel is not persistent, so you can't use any information from previous packets.

    Compressor speed is important, so any compressor that has to initialize a large model is not okay. Mem use has to be under 256k.

    How would you do it?

    The obvious answer is a small-hash-table LZ77, with or without entropy coding on the back end, but is there something better that I'm not seeing?
    Last edited by cbloom; 3rd August 2016 at 20:42.

  2. #2
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,004
    Thanks
    393
    Thanked 389 Times in 149 Posts
    It's funny, but these days I'm toying with such idea exactly. Apart from LZ77/LZRW, I'd say Predictor algorithm (RFC 1987), or sort of simplified Symbol Ranking. I have found a few ideas on how to improve Predictor compression with no speed loss. I even wrote an ASM-driven version. Will release it soon!

  3. #3
    Member
    Join Date
    Sep 2008
    Location
    France
    Posts
    870
    Thanks
    472
    Thanked 264 Times in 109 Posts
    For small packets, having a pre-set dictionary to "warm up" the LZ reference table can get you a pretty significant win.

  4. #4
    Member
    Join Date
    Sep 2010
    Location
    US
    Posts
    126
    Thanks
    4
    Thanked 69 Times in 29 Posts
    Quote Originally Posted by encode View Post
    It's funny, but these days I'm toying with such idea exactly. Apart from LZ77/LZRW, I'd say Predictor algorithm (RFC 1987), or sort of simplified Symbol Ranking. I have found a few ideas on how to improve Predictor compression with no speed loss. I even wrote an ASM-driven version. Will release it soon!
    Cool, looking forward to that.

    I've been thinking a bit along those lines. LZP1 was originally made to beat Predictor in this context. I find them hard to make faster than LZ77 these days though, because the cost of a branch is so high now. They can still be good if what you care about is MAX(encode_time,decode_time) because they're so symmetric, but not so awesome if you are measuring the sum (encode_time+decode_time).

    It seems you could store the last 4 or 8 symbols in each context packed into a U32 or U64. Then adding a symbol is just shift and or. Maybe do some kind of fast scan for a byte in a U32 or U64. Hmm I might try this.

    With SSE4 you could do a super fast symbol-ranker. The new string instructions look great for maintaining MTF lists.
    Last edited by cbloom; 3rd August 2016 at 20:42.

  5. #5
    The Founder encode's Avatar
    Join Date
    May 2006
    Location
    Moscow, Russia
    Posts
    4,004
    Thanks
    393
    Thanked 389 Times in 149 Posts
    Well, that Predictor is just LZP with MIN_MATCH=MAX_MATCH=1. Unfortunately, LZP with simplest byte-aligned coding not really strikes - i.e. it has poor compression performance, unlike LZSS/LZRW. In other words, for LZP we need sort of Huffman-like bit codes for a match length coding - since we must able to compress that 1-byte match to achieve some compression. Predictor scores here.
    Also, it should be noted that LZSS has some branches too - literal (literal run) or match, in simplest case. The thing is, LZSS' decompressor never maintain hash-tables of any kind. It performs just guided copy/paste.
    At the same time LZP/Predictor must maintain a hash table of pointers/symbols (plus, compute a hash). Memory access is a big bottleneck, and for large hash tables it's even bigger than branches.
    Anyway, my Predictor definitely is not slow and it beats my LZSS implementations in terms of Comp.Time+Decomp.Time due to its lightning fast compression (Even if we talking about pure C++ compile)

Similar Threads

  1. Compressing pi
    By Matt Mahoney in forum Data Compression
    Replies: 24
    Last Post: 26th September 2016, 19:17
  2. Compressing mp3 Files
    By zhuda in forum Data Compression
    Replies: 12
    Last Post: 7th March 2011, 18:26
  3. On compressing series of ones and zeroes.
    By Chuckie in forum Data Compression
    Replies: 4
    Last Post: 3rd March 2011, 11:33
  4. compressing a really small 1k .COM file
    By Rugxulo in forum Data Compression
    Replies: 3
    Last Post: 28th November 2009, 00:32
  5. Compressing small bits of data
    By fredrp in forum Data Compression
    Replies: 9
    Last Post: 28th April 2009, 22:27

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •