Author
|
Topic: Run Length Encoding Question. (Read 2 times)
|
RyanfromScotland
Guest
|
 |
« on: January 12, 2008, 09:37:28 pm » |
|
Ok maybe it is because I am tired or maybe it is something else I can not think of because I am tired but for some reason I can not wrap my head round part of this simple compression technique. This is the site I got most the information from so far http://www.strategyplanet.com/rctuk/tid/RLE.htmlHere is the bit that is getting me: Take this piece of compressed data '99 EF' so 99 = 10011001 meaning the most significant bit is a 1 so according to the site "if MSB=1 then B[yte] is flag to duplicate data. Read the next byte and copy it (-B[yte]+1) times to your target data stream." So we get the two's compliment which is 01100111 so that means I would copy the data 103+1 times but what if the two's compliment was 11100111 instead. Would the result be 231+1 or do I ignore the 8th bit because it is the sign bit or what if the resultant two's compliment has a nineth bit like 100000110 then do I drop the left most 1 and just work with 110? Like I say I am really tired and it has taken me about 30 minutes just to write this question. I am pretty sure I count all the bits and drop the 9th if one appears but would like this verified by someone just incase. |
|
|
|
|
BRPXQZME
Guest
|
|
« Reply #1 on: January 12, 2008, 11:26:43 pm » |
|
The two's compliment of anything with an MSB of 1 cannot have an MSB of 1. Moreover, you cannot get a two's compliment of a byte with eight bits to give you more than eight bits.
So there are two kind of bytes in this byte RLE scheme: "control" bytes, and "data" bytes. A control byte can have an MSB of 0 or 1; there are 128 values of each. 0-127 tell you to copy 1-128 (a.k.a. values 00-7F) byte(s), respectively; -128 to -1 (a.k.a. values 80-FF) tell you to copy the very next byte (and only that one), 129 to two times (because copying something once is stupid; you don't have to do it that way... there's nothing wrong with doing it stupid, but why do it?).
There are other ways to do RLE, of course, but this is about as simple as you'll ever see it.
|
|
|
|
|
RyanfromScotland
Guest
|
|
« Reply #2 on: January 13, 2008, 11:23:59 am » |
|
The two's compliment of anything with an MSB of 1 cannot have an MSB of 1. Moreover, you cannot get a two's compliment of a byte with eight bits to give you more than eight bits. I thought not but was not sure. 129 to two times (because copying something once is stupid; you don't have to do it that way... there's nothing wrong with doing it stupid, but why do it?). Yeah in all the literature I've read about RLE it says that that is one of the main flaws of this method, it can take extra space to store constantly changing data, but I have read about lots of work-arounds. Cheers for the help I think I have got it now. |
|
|
|
|
ecst
Guest
|
|
« Reply #3 on: January 13, 2008, 11:37:23 am » |
|
In fact, since the two's complement function is bijective, the numbers of values with MSB of 0 and 1, respectively, are equal, and the two's complement of $00 is $00 which has MSB of 0, there must also be a value with MSB of 1 the two's complement of which has MSB of 1, which in the case of byte values is $80 = -128. For this value, according to the website, the following byte value shall be repeated (-(-128) + 1) = -128 + 1 = -127 times, which should probably be interpreted as 129.
Note that for control byte values of $80 and $81, the Delphi code listed on the website gives loops equivalent to "for i:=1 to -127" and "for i:=1 to -128" with i being an integer, which will either throw an exception or loop many more times than intended. But then again, the author states that 125 is the internal repeat number maximum, which excludes both of these values, and thereby eliminates the whole problem of repeat values with MSB of 1.
|
|
|
|
« Last Edit: January 13, 2008, 11:45:10 am by ecst »
|
|
|
|
KingMike
Guest
|
|
« Reply #4 on: January 13, 2008, 12:47:18 pm » |
|
(-(-128) + 1) = -128 + 1 = -127 times,
-(-128) = +128.  |
|
|
|
|
creaothceann
Guest
|
|
« Reply #5 on: January 13, 2008, 12:54:29 pm » |
|
Note that for control byte values of $80 and $81, the Delphi code listed on the website gives loops equivalent to "for i:=1 to -127" and "for i:=1 to -128" with i being an integer, which will either throw an exception or loop many more times than intended.
A FOR loop with a start value greater than the end value is skipped. (Same for FOR loops with "downto", but reversed.) [ link] |
|
|
|
|
RyanfromScotland
Guest
|
|
« Reply #6 on: January 13, 2008, 01:00:38 pm » |
|
-(-128) = +128. Was going to say that in my reply but was busy taking in the rest of the message  I do not have any software on my computer that allows me to run that code although I do have a Java version of it but I think I'm doing something wrong trying to run it. When I go back to university I am doing a course in Web Technology which may have some programming in it. When I find out what language we are using I will get the software onto my computer at home and (try to) write a programme in that which does it. Tried doing it by hand for a bit just to see if I have got the concept down and I'm pretty sure I have but I really do not fancy doing the whole file manually. |
|
|
|
|
ecst
Guest
|
|
« Reply #7 on: January 13, 2008, 01:02:35 pm » |
|
(-(-128) + 1) = -128 + 1 = -127 times,
-(-128) = +128. Actually, no, not when calculating with 8 bit signed byte values as on the above website, that's what i wanted to say. Indeed, with higher bit integers it makes more sense (and then one directly gets 129 as result). Note that for control byte values of $80 and $81, the Delphi code listed on the website gives loops equivalent to "for i:=1 to -127" and "for i:=1 to -128" with i being an integer, which will either throw an exception or loop many more times than intended.
A FOR loop with a start value greater than the end value is skipped. (Same for FOR loops with "downto", but reversed.) [ link] Thanks, another time of my antiquing Delphi knowledge fragments deceiving me, though I doubt this was the intended behaviour either. EDIT: Now that i review the line "EncodeByte : shortint; //signed 8-bit number ": shortint is a 16 bit signed integer, not 8 bit, correct? Well, this frees me from my misconception. |
|
|
|
« Last Edit: January 13, 2008, 01:11:40 pm by ecst »
|
|
|
|
creaothceann
Guest
|
|
« Reply #8 on: January 13, 2008, 04:38:08 pm » |
|
I do not have any software on my computer that allows me to run that code
Maybe FreePascal is able to compile it. EDIT: Now that i review the line "EncodeByte : shortint; //signed 8-bit number ": shortint is a 16 bit signed integer, not 8 bit, correct?
Nope, SmallInt is 16 bit.  |
|
|
|
|
Ryusui
Guest
|
|
« Reply #9 on: January 13, 2008, 04:56:50 pm » |
|
One fun thing I discovered about LZ compression is that if a compression code has a distance of 1, it functions like RLE. ^_^
|
|
|
|
|
RyanfromScotland
Guest
|
|
« Reply #10 on: January 13, 2008, 06:17:13 pm » |
|
Hey thanks, I will give that a try but I have decided instead of waiting the 2 weeks until I go back to university I am going to go back to learning Visual Basic (you may remember my Simple GUI topic I made a couple of months back when I touched on learning this language). I think it would be more beneficial to take up that project again and work on making a decompressor at the same time in the same language that way all the basic guides which I could not be bothered working through before will have a bit more relevance and hopefully help keep me committed. |
|
|
|
|
|
RHDN Forum Archive
