CODEWITHSUNDEEP
network-programmingcompression
Vish_Master
Vish_Master

Reputation: 9

what is the simplest compression techniques for a single network packet?

Need a simple compression method for a single network packet. simple in the sense a technique which uses least computation.

Thanks!

Upvotes: 0

Views: 2179

Answers (3)

David Cary
David Cary

Reputation: 5490

The "PPP Predictor Compression Protocol" is one of the lowest-computation algorithms available for single-packet compression. Source code is available in RFC1978.

The decompressor guesses what the next byte is in the current context. If it guesses correctly, the next bit from the compressed text is "1"; If it guesses incorrectly, the next bit from the compressed text is "0" and the next byte from the compressed text is passed through literally (and the guess table for this context is updated so next time it guesses this literal byte).

The compressor attempts to compress the data field of the packet. Even if half of the guesses are wrong, the compressed data field will end up smaller than the plaintext data, and the compressed flag for that packet is set to 1, and the compressed data is sent in the packet. If too many more guesses are wrong, however, the "compressed" data ends up the same or even longer than the plaintext -- so the compressor instead sets the compressed flag for that packet to 0, and simply sends the raw plaintext in the packet.

Upvotes: 2

Mark Adler
Mark Adler

Reputation: 112374

lz4 compresses and decompresses very fast. zlib can compress better, but not quite as fast. The "least computation" would be to not compress at all.

Upvotes: 1

James Card
James Card

Reputation: 130

There are two basic types of compression: loss-less and lossy. Loss-less means that if you have two algorithms c(msg) which is the compression algorithm and d(msg) which is the decompression algorithm then

msg == d(c(msg))

Of course then, this implies that a lossy compression would be:

msg != d(c(msg))

With some information, lossy is ok. This is typically how sound is handled. You can lose some bits without any noticeable loss. MP3 compression works this way, for example. Lossy algorithms are usually specific to the type of information that you are compressing.

So, it really depends upon the data that you are transmitting. I assume that you are speaking strictly about the payload and not any of the addressing fields and that you are interested in loss-less compression. The simplest would be run length encoding (RLE). In RLE, you basically find duplicate successive values and you replace the values with a flag followed by a count followed by the value to repeat. You should only do this if the length of the run is greater (or equal) to the length of the tuple

(sizeof(flag)+sizeof(count)+sizeof(value).

This can work really well if the data is less than 8 bits in which case you can use the 8th bit as the flag. So for instance if you had three 'A's "AAA" then in hex that would be 414141. You can encode that to C103. In this case, the max run would be 255 (FF) before you would have to start the compression sequence again if there were more than 255 characters of the same value. So in this case 3 bytes becomes 2 bytes. In a best case, 255 7-bit values of the same value would then be 2 characters instead of 255.

A simple state machine could be used to handle the RLE.

See http://en.wikipedia.org/wiki/Run-length_encoding

Upvotes: 0

Related Questions