basic RLE coder stuck in loop??

Go To Last Post
26 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


Hi freaks.  I have a basic Run Length Encoder but it is getting caught in a loop and freezing the system.  

/**
 * inRaw, pointer to raw pixel data, r,g,b - 24bit
 * inSize size in bytes of the raw image
 */
void encode_rle(char * inRaw, unsigned int inSize){


    struct size24 * outBuffer = safe_malloc(1850000);

    struct size24 * inBuffer = (struct size24 *)inRaw;
    struct size24 * inStart = (struct size24 *)inRaw;


    unsigned int outStart = (unsigned int)outBuffer;

    struct size24 * pixel1 = NULL,
                  * pixel2 = NULL,
                  * pixel3 = NULL,
                  * pixel  = NULL,

                  marker;

    // arbitrary value -
    set_value(&marker, 0x101010);

    unsigned int count = 0;


    // kick off the comparison algorithm
    memcpy(pixel1, inBuffer++, 3);
    memcpy(pixel2, inBuffer++, 3);
    memcpy(pixel3, inBuffer++, 3);

    int p = 0;

    while(((char *)inBuffer - (char *)inStart) - inSize != 0){


        // detected a string of three matching pixels, begin to traverse the pixels if they match
        if(memcmp(pixel1, pixel2, 3) == 0){
             if(memcmp(pixel2, pixel3, 3) == 0){


                // set the MARKER pixel
                set_value(outBuffer++, 0x101010);

                 // three bytes match thus far
                 count = 3;

                 // next pixel to compare
                 memcpy(pixel, inBuffer++, 3);


                 // while string of likewise pixels begin counting
                 while(memcmp(pixel3, pixel, 3) == 0){
                     count++; memcpy(pixel, inBuffer++, 3); printf("\n\rloop %i", count);
                 }

                 // set the repetition count
                 set_value(outBuffer++, count);

                 // set the repetition pixel color
                 memcpy(outBuffer++, pixel3, 3);


                 // load next palette to compare
                memcpy(pixel, pixel, 3);
                memcpy(pixel2, inBuffer++, 3);
                memcpy(pixel3, inBuffer++, 3);
            }
             else{

                 if(memcmp(pixel1, &marker, 3) == 0)
                         memcpy(outBuffer++, pixel1, 3);

                memcpy(outBuffer++, pixel1, 3);

                memcpy(pixel1, pixel2, 3);
                memcpy(pixel2, pixel3, 3);
                memcpy(pixel3, inBuffer++, 3);
             }
        }
        else{
            if(memcmp(pixel1, &marker, 3) == 0)
                    memcpy(outBuffer++, pixel1, 3);

            memcpy(outBuffer++, pixel1, 3);


            memcpy(pixel1, pixel2, 3);
            memcpy(pixel2, pixel3, 3);
            memcpy(pixel3, inBuffer++, 3);
        }
    }
    printf("\n\rFile Size before compression %i", (unsigned int)inSize);
    printf("\n\rFile Size after compression %i\n\r\n\r", (unsigned int)outBuffer - outStart);
}

 

 it freezes here after say 650 loops:

 

// while string of likewise pixels begin counting
while(memcmp(pixel3, pixel, 3) == 0){
	count++; memcpy(pixel, inBuffer++, 3); printf("\n\rloop %i", count);
}

out of interest, the printf statement displays the following...

 

Now, I'm merely counting the number of consecutive pixels and am not writing to any memory location which leads me to believe the problem is somewhere else. Also, it is failing when doing the printf..  yes, without the printf it still fails.

 

What are your views?

This topic has a solution.
Last Edited: Tue. Nov 19, 2019 - 11:19 PM
This reply has been marked as the solution. 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Fianawarrior wrote:

    struct size24 * pixel1 = NULL,
                  * pixel2 = NULL,
                  * pixel3 = NULL,
                  * pixel  = NULL,

                  marker;

    // arbitrary value -
    set_value(&marker, 0x101010);

    unsigned int count = 0;

    // kick off the comparison algorithm
    memcpy(pixel1, inBuffer++, 3);
    memcpy(pixel2, inBuffer++, 3);
    memcpy(pixel3, inBuffer++, 3);

You seem to be doing a lot of memcpy to a NULL pointer?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

Blind as a bat, in too much of a rush to kick the development of.

Thanks MrKendo.

 

Out of interest, since I'm here.  Would a new pair of eyes see why the rle function is saying that after compression that the file size is larger afterwards!!!

 

 

/**
 * inRaw, pointer to raw pixel data, r,g,b - 24bit
 * inSize size in bytes of the raw image
 */
void encode_rle(char * inRaw, unsigned int inSize){

	struct size24 * outBuffer = safe_malloc(1850000);

	struct size24 * inBuffer = (struct size24 *)inRaw;
	struct size24 * inStart = (struct size24 *)inRaw;

	unsigned int outStart = (unsigned int)outBuffer;

	struct size24 pixel1,
				  pixel2,
				  pixel3,
				  pixel,

				 pixel_marker;

	// arbitrary value -
	set_value(&pixel_marker, 0x101010);

	unsigned int count = 0;

	// kick off the comparison algorithm
	memcpy(&pixel1, inBuffer++, 3);
	memcpy(&pixel2, inBuffer++, 3);
	memcpy(&pixel3, inBuffer++, 3);

	while((inBuffer - inStart) < inSize){

		// detected a string of three matching pixels, begin to traverse the pixels if they match
		if(memcmp(&pixel1, &pixel2, 3) == 0){
			 if(memcmp(&pixel2, &pixel3, 3) == 0){

				// set the MARKER pixel
				set_value(outBuffer++, 0x101010);

			 	// three bytes match thus far
			 	count = 3;

			 	// next pixel to compare
			 	memcpy(&pixel, inBuffer++, 3);

			 	// while string of likewise pixels begin counting
			 	while(memcmp(&pixel3, &pixel, 3) == 0){
			 		count++; memcpy(&pixel, inBuffer++, 3); printf("\n\rloop %i", count);
			 	}

			 	// set the repetition count
			 	set_value(outBuffer++, count);

			 	// set the repetition pixel color
			 	memcpy(outBuffer++, &pixel3, 3);

			 	// load next palette to compare
				memcpy(&pixel1, &pixel, 3);
				memcpy(&pixel2, inBuffer++, 3);
				memcpy(&pixel3, inBuffer++, 3);
			}
			 else{

				 if(memcmp(&pixel1, &pixel_marker, 3) == 0)
				 		memcpy(outBuffer++, &pixel1, 3);

				memcpy(outBuffer++, &pixel1, 3);

				memcpy(&pixel1, &pixel2, 3);
				memcpy(&pixel2, &pixel3, 3);
				memcpy(&pixel3, inBuffer++, 3);
			 }
		}
		else{
			if(memcmp(&pixel1, &pixel_marker, 3) == 0)
					memcpy(outBuffer++, &pixel1, 3);

			memcpy(outBuffer++, &pixel1, 3);

			memcpy(&pixel1, &pixel2, 3);
			memcpy(&pixel2, &pixel3, 3);
			memcpy(&pixel3, inBuffer++, 3);
		}
	}
	printf("\n\rFile Size before compression %i", (unsigned int)inSize);
	printf("\n\rFile Size after compression  %i\n\r\n\r", (unsigned int)outBuffer - outStart);
}

 

 

Last Edited: Tue. Nov 19, 2019 - 11:23 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

RLE works best on data that has long series of same data. Hit it with random data and it does not perform well. Consider the cost of the ‘management’ overhead ie: each time there is a change, you need a fixed count and value. Say you use a 8 bit count and 8 bit value - one change becomes 16 bits. So, worst case the data size doubles. With ‘ideal’ data you might expect up to /256 size. Real data falls between these two extremes.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi kartman, the data set I'm using should show a significant improvement in file size.  The image is mostly black.  Its  a picture of a Buddabrot set.

 

I'll write the decoder to morrow and get back to it.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm unfamiliar with malloc() because I never have used it.  But I believe that:

struct size24 * outBuffer = safe_malloc(1850000);

means to allocate 1, 850, 000 units of free memory space  with each unit being the size of 3 bytes (24 bits / 8);  for a total of ~ 5, 550, 000 bytes.

 

This is way beyond the capacity of any microcontroller.   Is this running on a PC host with gigabytes of heap RAM space?

 

Perhaps loop 650 is where the microcontroller runs out of internal RAM to use.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Simonetta wrote:

I'm unfamiliar with malloc() because I never have used it.  But I believe that:

struct size24 * outBuffer = safe_malloc(1850000);

means to allocate 1, 850, 000 units of free memory space  with each unit being the size of 3 bytes (24 bits / 8);  for a total of ~ 5, 550, 000 bytes.

 

This is way beyond the capacity of any microcontroller.   Is this running on a PC host with gigabytes of heap RAM space?

 

Perhaps loop 650 is where the microcontroller runs out of internal RAM to use.

 

240KBytes is the raw image.

I'd expect the compression routine to be a lot less.

 

The code is running on a ARM Cortex-A5, 512 DDR RAM

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

just to confirm the procedural function of the RLE encoder. if three or more pixels are the same colour then the pixels are replaced with three pixels that contain a marker, number of pixels that are the same and the pixel color.

 

 

Last Edited: Wed. Nov 20, 2019 - 03:42 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


To simply build your code I dummied some things that weren't shown:

#define safe_malloc malloc

typedef struct size24 {
    uint8_t r;
    uint8_t g;
    uint8_t b;
} size24_t;

void set_value(struct size24 * buf, uint32_t val) {
    buf->r = val >> 16;
    buf->g = val >> 8;
    buf->b = val;

}

Then used some test data:

char input[] = { 1, 3, 3, 4, 3, 7, 7, 7, 2, 2, 9, 9, 9, 9, 9 };

int main()
{
    encode_rle(input, sizeof(input));
}

and get the result:

loop 67
loop 68
loop 69
loop 70
loop 71
loop 72
loop 73
loop 74
loop 75
loop 76
loop 77
loop 78
loop 79
loop 80
loop 81
loop 82
loop 83
loop 84
loop 85
loop 86
loop 87
File Size before compression 15
File Size after compression  24

So, yes, you have serious problems! I would liberally sprinkle the code with printf()s to see which code paths it is taking and how the pointers are incrementing. Having done that:

    while ((inBuffer - inStart) < inSize) {

        // detected a string of three matching pixels, begin to traverse the pixels if they match
        if (memcmp(&pixel1, &pixel2, 3) == 0) {
            if (memcmp(&pixel2, &pixel3, 3) == 0) {
                printf("pix1 == pix2 and pix2 == pix3, in=%08X, out=%08X\n", inBuffer, outBuffer);

                // set the MARKER pixel
                set_value(outBuffer++, 0x101010);

                // three bytes match thus far
                count = 3;

                // next pixel to compare
                memcpy(&pixel, inBuffer++, 3);

                // while string of likewise pixels begin counting
                while (memcmp(&pixel3, &pixel, 3) == 0) {
                    count++; memcpy(&pixel, inBuffer++, 3); printf("\n\rloop %i", count);
                }

                // set the repetition count
                set_value(outBuffer++, count);

                // set the repetition pixel color
                memcpy(outBuffer++, &pixel3, 3);

                // load next palette to compare
                memcpy(&pixel1, &pixel, 3);
                memcpy(&pixel2, inBuffer++, 3);
                memcpy(&pixel3, inBuffer++, 3);
            }
            else {
                printf("pix1 == pix2,  in=%08X, out=%08X\n", inBuffer, outBuffer);

                if (memcmp(&pixel1, &pixel_marker, 3) == 0) {
                    printf("pix1 == pix2 and pix1 == marker, in=%08X, out=%08X\n", inBuffer, outBuffer);

                    memcpy(outBuffer++, &pixel1, 3);
                }

                printf("3 bytes to output\n");
                memcpy(outBuffer++, &pixel1, 3);

                memcpy(&pixel1, &pixel2, 3);
                memcpy(&pixel2, &pixel3, 3);
                memcpy(&pixel3, inBuffer++, 3);
            }
        }
        else {
            printf("pix1 != pix2, in=%08X, out=%08X\n", inBuffer, outBuffer);
            if (memcmp(&pixel1, &pixel_marker, 3) == 0)
                memcpy(outBuffer++, &pixel1, 3);

            printf("3 bytes to output\n");
                memcpy(outBuffer++, &pixel1, 3);

            memcpy(&pixel1, &pixel2, 3);
            memcpy(&pixel2, &pixel3, 3);
            memcpy(&pixel3, inBuffer++, 3);
        }
    }

I get this output...

pix1 != pix2, in=0087A03D, out=00C22040
3 bytes to output
pix1 != pix2, in=0087A040, out=00C22043
3 bytes to output
pix1 != pix2, in=0087A043, out=00C22046
3 bytes to output
pix1 != pix2, in=0087A046, out=00C22049
3 bytes to output
pix1 != pix2, in=0087A049, out=00C2204C
3 bytes to output
pix1 == pix2 and pix2 == pix3, in=0087A04C, out=00C2204F

loop 4
loop 5
loop 6
loop 7
loop 8
loop 9
loop 10
loop 11
etc...

So what's actually going on here:

is that all the pixel1/2/3 are all {0,0,0}. In other words it has "run off the end of the input data". In effect it means your stopping condition:

    while ((inBuffer - inStart) < inSize) {

Is wrong. It went too far.

 

I'm too lazy to investigate further but I do wonder about the build warning:

d:\c\testfp\testfp\testfp.cpp(56): warning C4018: '<': signed/unsigned mismatch

which relates to that very line.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
I would liberally sprinkle the code with printf()s to see which code paths it is taking and how the pointers are incrementing.

 

And use the debugger to step through the code & watch what's happening!

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

awneil wrote:
And use the debugger to step through the code & watch what's happening!
Yeah I did that too but sometimes it's simpler just to sprinkle printf()s just to get a "broad brushstrokes" view of what the path of execution is.

Last Edited: Wed. Nov 20, 2019 - 12:02 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I'm sure you did - that was addressed to  Fianawarrior

 

That should've immediately spotted the original problem with the NULL pointers...

 

 

Top Tips:

  1. How to properly post source code - see: https://www.avrfreaks.net/comment... - also how to properly include images/pictures
  2. "Garbage" characters on a serial terminal are (almost?) invariably due to wrong baud rate - see: https://learn.sparkfun.com/tutorials/serial-communication
  3. Wrong baud rate is usually due to not running at the speed you thought; check by blinking a LED to see if you get the speed you expected
  4. Difference between a crystal, and a crystal oscillatorhttps://www.avrfreaks.net/comment...
  5. When your question is resolved, mark the solution: https://www.avrfreaks.net/comment...
  6. Beginner's "Getting Started" tips: https://www.avrfreaks.net/comment...
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Fianawarrior wrote:

while((inBuffer - inStart) < inSize)

inBuffer and inStart are pointers to struct size24, taking the difference between these pointers will give result in units of sizeof(struct size24).

I suspect you intended the result to be in terms of bytes, which it won't be unless sizeof(struct size24) is 1.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

 

That's the result after running a plain image through.  Perfect guys.

 

Just to add, this fixed it:

 

while(((char *)inBuffer - (char *)inStart) < inSize){

 

 

Last Edited: Wed. Nov 20, 2019 - 03:48 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0


After processing this image:

 

 

I get the following stats on compression:

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

What if you simply ZIPped it ?

 

(IOW why reinvent the wheel? You can add libzip to your existing code and get far better compression than anything you'll come up with in the next decade)

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:

What if you simply ZIPped it ?

 

(IOW why reinvent the wheel? You can add libzip to your existing code and get far better compression than anything you'll come up with in the next decade)

 

I want to do the code to fully understand the principles and methods of subject areas...

 

I'm also going to do Huffman and LZ77

 

Last Edited: Wed. Nov 20, 2019 - 04:21 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If I was doing this I'd be tempted to split the RGB into 3 separate planes of data then compress each separately.

 

(actually in my world we wouldn't bother with RGB at all and would likely use YUV and the chances are the planes are separate anyway - well certainly the Y is separate from the U/V colour difference - thouhg they might be interleaved).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

quick question lads, hen decompressing a file, I do not know the size of the decompressed file so how much memory do I allocate?

I'm thinking of doing run throughs.  First run to calculate the size required and the second run to build the file?

 

This is not time critical. 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Fianawarrior wrote:

quick question lads, hen decompressing a file, I do not know the size of the decompressed file so how much memory do I allocate?

I'm thinking of doing run throughs.  First run to calculate the size required and the second run to build the file?

 

This is not time critical. 

Running through twice is a decent option, particularly if not time critical. It's nice and simple.

If it is taking longer than you would like, the other standard option would be to make a reasonable guess for the size, malloc that size, and then if you run out of space during the decomprsssion you do a realloc to a larger size (typically double the size each time you run out of space).

If needs be you can realloc to the exact size when finished, if you really need to get any excess memory back.

You would have to do some tests to see which method works out fastest.

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Most image formats have some kind of header on the front typically giving width, height and bit depth so you can calculate how much data you'll end up with before you start.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

nice one clawson.  Never thought of that.  your a genius.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

You should really pursue making as much code as possible portable which would allow you to test on your development computer. This gives you the following benefits (and more):

  • Segfault and core dump when dereferencing null pointers
  • Access to dynamic analyzers (such as valgrind)
  • Access to compiler supplied sanitizers (address, memory, thread, and undefined behavior)
  • Access to easy to use automated testing frameworks
  • Easy integration of build and automated test verification into your workflow (Git hooks and/or CI/CD)

These tools can make your a whole lot easier when running into these kinds of problems. Combining them with test driven development makes things even easier.

github.com/apcountryman/build-avr-gcc: a script for building avr-gcc

github.com/apcountryman/toolchain-avr-gcc: a CMake toolchain for cross compiling for the Atmel AVR family of microcontrollers

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Guys, could I have your input.  The run length encoder I'm working on - I'm thinking of writing the function to be able to handle 8bit, 16bit, 24bit and 32bit data.

 

The reason being is that say if you try to process a 24bit colour image in 8 bits the compression ratio would likely be better running at 24 bit.

 

Whats your view?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

If you're dealing with images, it's much more likely that adjacent pixels in a single colour plane are going to match than (say) RGB or YUV pixels across a full image. The larger your bit size, the lower the chance of adjacent bits being amenable to RLE coding. There are many better ways to encode pictures, particularly photographic images.

 

RLE really doesn't work well with images once you get past four or five bits colour depth. Trying it with a 32 bit depth is a serious waste of time; odds are it'll never find two matching pixels adjacent (except maybe in black edges).

 

Neil

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

barnacle wrote:
it's much more likely that adjacent pixels in a single colour plane
William, do you remember a previous post where I said to split R, G and B first then compress each separately? This!

 

There may be consistent runs in the red (say) while the green/blue are varying but if you took RGB as full 24bit numbers then you would not see the constant red (run length) because each 24 bit value would vary a bit because of the changes in green and blue. (or whatever the fixed/changing colours happen to be).

 

PS if it is YUV then equally split the planes and compress each separately. You may have a constant colour area with varying contrast for example.

Last Edited: Fri. Nov 22, 2019 - 09:32 AM