CODEWITHSUNDEEP
compression
Transagonistica
Transagonistica

Reputation: 129

RLE Encoding bit sequence, not bytes

I need to implement a compression algorithm for binary data, that need to work on embedded constrained devices (256kB ROM, 48 KB RAM).

I'm thinking to the RLE compression algorithm. Unless implementing it from scratch, I've found a lot of C implementations, (for example: http://sourceforge.net/projects/bcl/?source=typ_redirect ), but they apply the RLE algorithm over the byte sequence (the word of the dictionary are 1 to 255, that is 8-bit encoding.

I'm finding for an implementation that, starting from a sequence of bytes, applies the RLE encoding over the bit-sequence corresponding to the input (0 and 1). Note that also another algorithm can work (I need a compression ratio <0.9, so I think any algorithm can do it), but the implementation need to work on a bit-basis, not bytes.

Can anyone help me? Thank you!

Upvotes: 2

Views: 3010

Answers (1)

D.Doe
D.Doe

Reputation: 11

I think that you can encode bytes such as 0, 1, 2, 3, 255… etc. (Where lots of 0 and 1)

Let's encode this bit sequence: 000000011111110 1. Shift bits and increment the counter if bit compare to last bit 2. If NOT— shift 111 to output buffer and write control bit 1 before bit sequence 3. If bits can not be packed — write 0 bit and rest of data Output: 111101110100

To decompress simply shift first control bit: If 0 — write next bit to output buffer If 1 — read 3 bits (can be other length) and convert them to the decimal number. Shift next bit which will mean what bit to repeat and start loop to represent the original sequence

But this compression method will work only on files, which have lots of 0 and 255 bytes (00000000 and 11111111 in binary), such as BMP files with black or white background.

Hope I helped you!

Upvotes: 1

Related Questions