Opportunity for speedup

Mitch Bradley wmb at laptop.org
Thu Feb 19 14:16:11 EST 2009

Bobby Powers wrote:
> On Thu, Feb 19, 2009 at 1:56 PM, Wade Brainerd <wadetb at gmail.com> wrote:
>> RLE (run length encoding) compresses sequences of identical pixels ("runs")
>> as value/count pairs.
>> So abbbbbbbbbbccc would be stored as 1a 10b 3c.
>> The decompressor looks like:
>> while (cur < end)
>> {
>>    unsigned short count = *cur++;
>>    unsigned short value = *cur++;
>>    while (count--)
>>       *dest++ = value;
>> }
>> This can be faster than memcpy because you are reading significantly less
>> memory than you would with memcpy, thus fewer cache misses are incurred.
>> Because the startup images are mostly spans solid colors, this kind of
>> compression works very well.  If that were not the case, say if there were a
>> left-to-right gradient in the background, RLE would probably make things
>> worse, thus you have to be careful when choosing it.
>> But the smaller size on disk and in memory would probably improve
>> performance in other ways as well.
>> Best,
>> Wade
> thanks, that makes sense
We are already getting some portion of the possible compression by doing 
the "iframe style" delta encoding of the second and subsequent frames, 
but the rle is still of some use.  It does a good job of shrinking the 
first frame, and it halves the size of the delta wad.

The first-frame-shrink could also be accomplished by the trick of 
assuming an initial solid background and representing the first frame as 
a delta from that.

In either case, it looks like rle decoding might be a nice addition, as 
it reduces the size of the frames on disk from 1.2 MB to about 140 KB.

More information about the Devel mailing list