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

Run length encoding is a compression technique that takes advantage of repeated consecutive digits. Encoding involves putting a character followed by count.

Example input: 123334455555AAA

Output for above input: 1\12\13\34\25\5A\3

(1 is appearing once, 2 is appearing twice,k 3 is appearing 3 times, 4 is appearing twice, 5 is appearing 5 times, A is appearing 3 times. \ represents the ESCAPE sequence. \1 means ASCII value 1)

If a digit is repeated more than 255 times, it should be split into two parts as in following example:

Example input:1 repated 257 times
Output for above input:1\2551\2

A decoder does the reverse.

Write a C program that encodes in RLE format and also decodes RLE format to restore to the original file. (When a file is encoded and decoded, the original file should be restored)

i have already done the encoding part.i want someone to help me with the decoding part..plz use simple C..i am posting the encoding part i have done for ur reference..plz help guys.its urgent..

Code:

---


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
char a[500];
int count=0,setcount=1,temp=255;
FILE *stream;
clrscr();

printf("\nEnter the input:\n");
scanf("%s",&a);
stream=fopen("g.txt","w");
int len=strlen(a);
printf("Original input :%s\n\nLength:%d\n\nCompressed output:",a,len);

while(count<len)
{
        if(a[count]==a[count+1])
        {
        setcount++;
        count++;
        }

        else
                while(1)
                {
                if(setcount>255)
                        {
                        printf("%c\\%d",a[count],temp);
                        setcount-=temp;
                        }
                else
                        {
                        printf("%c\\%d",a[count],setcount);
                      fprintf(stream, " %c\\ %d", a[count],setcount);
                        setcount=1;
                        count++;
                        break;
                        }


                }

        }

        printf("\n");


        getch();
        return(0);




}

---

>> ...its urgent
When is it due?

gg

> Output for above input: 1\12\13\34\25\5A\3
How do you propose to tell the difference at the start between
1 repeated once, followed by 2, as in 12
1 repeated 12 times followed by a \, as in 111111111111\

The problem is, your encoding is wrong.
You should be writing out just TWO bytes per character, one byte being the character, and the other byte representing the repeat count.

Decoding is them much easier as you always read a pair, then expand a sequence.

and you should work on your indentation - it is not consistent

Agreed, the encoder is completely wrong, in so many ways!
But since it's urgent you wont have time to understand the details so I wont bother to explain them.

but the program is running perfectly..
if there are 12 1's followd by 2 it will give the output as 1\122..no problem with that..thats what they have said to do in the problem..pls neone help me with the decoding part...

input : 1\52\3 should be decoded as

11111222

can neone help me with a code..pls..its very urgent..thanxx guys..

His encoding, if really done in text, could work. (It could be decoded.) Example,

Code:

---

1/12/1

---

Read the 1. Read the /. Now read in numbers until you get to the next /. That last number/character was just read, put it back. You now have: character / number of times to repeat.

Granted, this encoding, if done in plain text, is horrid, and I wonder just how much benefit you'd get out of it. It should really be a binary file of two bytes: character, length. However, whatever requirements are being put on the OP may restrict that.

EDIT: Rereading the OP's first post, I think perhaps whatever he or she has is trying to say, put it in a binary file, with byte pairs of character,length... albeit the whole thing about escape sequences is ... off.

Quote:

---

Originally Posted by garv84

but the program is running perfectly..
if there are 12 1's followd by 2 it will give the output as 1\122..no problem with that..thats what they have said to do in the problem..pls neone help me with the decoding part...

input : 1\52\3 should be decoded as

11111222

can neone help me with a code..pls..its very urgent..thanxx guys..

---

Garv, we aren't a homework writing service, no matter how urgent it may be. You show your functions code, and tell us what the problem is, and we'll do our best to give advice.

We won't write a function, or half the program in your case, while you offer no work, at all on it.

Cactus Hugger has described the algorithm that I would use. If the program you claim is yours, is really yours, you should have very little trouble coding it up.

It's not that way however, because you didn't write the first program you posted. You got it from another source, and now you need help, of course.

Programming is a lot of work. You can't become a programmer by just cherry-picking other people's code (even if it's open source or public domain or even given to you), and trying to get by. It takes a lot of work FROM YOU.

> but the program is running perfectly..
Just because it runs without crashing and produces an output file is not a sign of perfection.

You're not addressing the issues raised in my previous post.

Given 1/122/3
You need to find a way of making sure it decodes as
1/122/3
and not as
1/122/3
This is what Cactus_Hugger was talking about.

It might be easier if you always wrote the length out as 3 digits, say
1/0122/003
If you know the length is always 3 digits, it makes it easier to deal with.

Your description clearly indicates that you are not supposed to store character followed by backslash and integer, but a character followed by another character whose integral value indicates the number of repeats.

So your output should look something like that:

Quote:

---

A0B"C^
for 48 A-s, 34 B-s, 94 C-s

---

The description uses \1 and explains how to interpret it, because characters with small ASCII values are non-printing (so you'd just see rectangles instead, for example).

plz tell me something..

say for ex : 1\125

all thses are characters.we are to print 1 125 tyms.how can we conver characters 125 into integar..??

A character is an integer, just with a small range. You don't want to print the integral value of the character at all. You want to use a char for counting, not an int.

Code:

---

char a = 's';
char b;

for (b = 0; b < a; ++b) {
}

---

Try something like that putting something inside the loop, and you might get the idea.

You might also Google for ASCII tables.

Quote:

---

Originally Posted by garv84

plz tell me something..

say for ex : 1\125

all thses are characters.we are to print 1 125 tyms.how can we conver characters 125 into integar..??

---

If you write the compressor properly then you don't have to!

Everyone always teaches RLE compression by giving examples with text, and shows the compressed version as if it were text. Such examples always contain lots of repeated bytes too.
However that's not the reality of how anybody who knows what they're doing implements it.

You are supposed to accept binary data, and write out binary data. Every byte value between 0 and 255 should be able to be compressed from the input file, and later restored after decompression of hte compressed file. This in turn basically means that your compressed file becomes a binary format as well.

Quote:

---

... and shows the compressed version as if it were text. Such examples always contain lots of repeated bytes too.

---

You could of course use RLE several times over to compress you data virtually to nothing.

Just kidding.

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.

Quote:

---

Originally Posted by Bubba

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.