CVS $Id: RLE.h,v 1.1 2009/04/30 00:31:28 russell Exp $
Overview
Interface specification for routines to encode bit strings using a run length encoding method. The only twist added to the straight-forward encoding, is that only the necessary number of bits needed to encode the bit address are used. For example, when encoding a 32-bit value, the straight-forward run-length encoding would use a 5-bit address (representing the bit number) and a 1 bit stop/continue bit. However, when the number of bits left to encode is less than 16, one only needs 4 bits. Similarly, when the number of bits left to encode is less tha 8, one only needs 3 bits, etc, etc.
Warning:
As is usual in these encoding routines, encoding 0 is the user's responsibility. This is because many times a value of 0 has already been encoded as a side-effect of some larger encoding scheme.
Summary
The set of run length encoding routines is
RLE_encode, encodes an n-bit number. While n can be any number from 1-32, practically speaking, only powers of 2 will affect the result (1,2,4,8,16,32)
RLE_exceeds, can be used to determine whether the size of the encoded pattern exceeds a maximum value. This can be useful when choosing between competing encoding methods, without actually encoding the data. This routine is somewhat faster than calling RLE_size, since RLE_exceeds can stop once the size exceeds the maximum value.
RLE_size, returns the size, in bits, needed to encode an n-bit number.