RLE.h File Reference

Run Length Encoding interface file. More...

Functions
unsigned int	RLE_encode (unsigned int *buf, unsigned int pos, unsigned int w, int nbits)
	Uses a run length encoding method to encode the bits in the specified word.
int	RLE_compare (unsigned int w, int nbits, int max)
	Compares the size of the max with run length method and returns (almost) rle_size - max.
unsigned int	RLE_size (unsigned int w, int nbits)
	Returns the size of the run length encoding method.

---

Detailed Description

Run Length Encoding interface file.

Author:

JJRussell - russell@slac.stanford.edu

   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.

---

Function Documentation

int RLE_compare	(	unsigned int	word,
		int	cnt,
		int	max
	)

Compares the size of the max with run length method and returns (almost) rle_size - max.

Return values:

	>0	Indicates RLE encoding is larger than max. How much larger is not encoded, only that it is larger.
	=0	The number of bits needed by the RLE_encode is the same as max
	<0	The number of bits needed by the RLE_compare is less than max. In this case, max + return value = size of RLE encoding.

Parameters:

	word	The word to encode
	cnt	The maximum bit number + 1 (LSB = 0) that can be set. For example, if all 32 bits can be set, then this is 32, if only 16 bits (right-jusified) then 16. This must be a value between 1 and 32.
	max	The maximum number of bits.

This routine can be used to judge whether some other encoding method is better than the run length method.

Example

If one wishes to use an asis encoding on a 16-bit value if the run length encoding method exceeds 16 bits

      / * Check if the run length encoding size is greater than or equal 16 * /
      if (RLE_compare (word, 16, 16) >= 0)
      {
          / * Yes, RLE method is greater than or equal to 16 bits 
              use asis encoding                                    * /
          pos = BFP_wordB (buf, pos, 1);
          pos = BFP_wordR (buf, pos, word, 16);
      }
      else
     {
          / * No, RLE_method is less than 16 bits * /
          pos = BFP_wordB  (buf, pos, 0);
          pos = RLE_encode (buf, pos, word, 16);
      }

unsigned int RLE_encode	(	unsigned int *	buf,
		unsigned int	pos,
		unsigned int	word,
		int	cnt
	)

Uses a run length encoding method to encode the bits in the specified word.

Returns:

The updated bit position

Parameters:

	buf	The output buffer
	pos	The current bit position
	word	The word to encode
	cnt	The maximum bit number + 1 (LSB = 0) that can be set. For example, if all 32 bits can be set, then this is 32, if only 16 bits (right-jusified) then 16. This must be a value between 1 and 32.

unsigned int RLE_size	(	unsigned int	word,
		int	cnt
	)

Returns the size of the run length encoding method.

Returns:

The number of bits needed by the RLE_encode

Parameters:

	word	The word to encode
	cnt	The maximum bit number + 1 (LSB = 0) that can be set. For example, if all 32 bits can be set, then this is 32, if only 16 bits (right-jusified) then 16. This must be a value between 1 and 32.