RLE Encoding/Decoding using simple C concept..plz help

This is a discussion on RLE Encoding/Decoding using simple C concept..plz help within the C Programming forums, part of the General Programming Boards category; Your version of RLE is not what I'm used to. Older versions of RLE such as in PCX files relied ...

  1. #16
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    Your version of RLE is not what I'm used to. Older versions of RLE such as in PCX files relied on some magical value to turn encoding on and off. Newer versions simply rely on character repeat counts to turn encoding on and off.

    So:

    AAAAAAAAABCCCDDDDDEEEEEFFFFFFFFFF

    would be this logically:

    A A 7 B C C 1 D D 2 E E 2 F F 8

    And this in RLE byte form:
    65 65 07 66 67 67 01 68 68 02 69 69 02 70 70 08

    Most systems will only allow at max 255 characters to be RLE because this is the max value for a byte or unsigned char.

    Spanning RLEs
    You can do spanning RLEs but you must place some extra logic in the code. You can determine when to turn RLE decode off by simply looking at the run length. Whenever the run length is < FF you know the byte following is a literal character and not a run length. The only time a run length can continue on is if the length is FF. So this is a long RLE byte stream:

    65 65 FF FF FF FF FF FF 7F 68 68 4F

    The RLE is turned off at 7F. Then 68 is interpreted as a literal character. Then 68 is encountered again and RLE mode is turned on and 4F is then interpreted as a run length.

    Special case
    There is one special case you must handle. Look at this byte stream:

    65 65 FF FF FF FF FF FF FF 68 68 4F

    RLE is turned off at 68, however 68 is interpreted as a run length. Then the next 68 is interpreted as a literal and the 4F is interpreted as another literal. This is clearly incorrect. The fix:

    65 65 FF FF FF FF FF FF FF 00 68 68 4F

    RLE is turned off at 00, 68 is literal, next 68 turns RLE on, 4F is run length for 68...which is correct.

    If the RLE terminates and the length is exactly FF then a 00 or some magic value must follow the RLE byte. This will turn off RLE. So now if the byte following FF is 00 then you take the FF and then turn RLE off and grab the next byte. Both your encoder and decoder must understand this logic to function correctly.
    Last edited by VirtualAce; 01-10-2008 at 04:50 PM.

  2. #17
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by Bubba View Post
    Your version of RLE is not what I'm used to. Older versions of RLE such as in PCX files relied on some magical value to turn encoding on and off. Newer versions simply rely on character repeat counts to turn encoding on and off.
    Hmm, that's very different to what I've used.

    I'm used to the high bit of the length byte telling whether the next byte is to be repeated (1), or whether the next <length> bytes are to be copied verbatim(0). If the next length byte has the same high-bit as the previous one, then if it is (0) you combine the previous length byte and this one and copy up to around 2^14 - 2^7 more chars, else if it is (1) AND the following byte to repeat is the same as the last byte to repeat then you fill with up to 2^14 - 2^7 more of the same byte. Otherwise you simply write up to 2^7 of that byte.

    Maybe it's nothing like your normal RLE, but it compresses better than the method you describe, adding at most 5 bytes to a file of several gigabytes, and compressing a run of 1 billion of the same byte down to only 10 bytes. Just as fast too.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. a simple question. plz help
    By monashhros3 in forum C Programming
    Replies: 1
    Last Post: 03-28-2008, 01:40 PM
  2. plz help me with simple string comparison.
    By MegaManZZ in forum C++ Programming
    Replies: 11
    Last Post: 02-18-2008, 12:11 PM
  3. Matrix Multiplication with simple syntax! plz help.
    By codebox in forum C Programming
    Replies: 6
    Last Post: 11-05-2004, 08:03 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21