Mastering Algorithms With C - Kyle Loudon [157]
#include "bitree.h"
/*****************************************************************************
* *
* Define a structure for nodes of Huffman trees. *
* *
*****************************************************************************/
typedef struct HuffNode_ {
unsigned char symbol;
int freq;
} HuffNode;
/*****************************************************************************
* *
* Define a structure for entries in Huffman code tables. *
* *
*****************************************************************************/
typedef struct HuffCode_ {
unsigned char used;
unsigned short code;
unsigned char size;
} HuffCode;
/*****************************************************************************
* *
* Define the number of bits required for LZ77 token members. *
* *
*****************************************************************************/
#define LZ77_TYPE_BITS 1
#define LZ77_WINOFF_BITS 12
#define LZ77_BUFLEN_BITS 5
#define LZ77_NEXT_BITS 8
/*****************************************************************************
* *
* Define the size of the sliding window and the look-ahead buffer for *
* LZ77. Each must be less than or equal to 2 raised to LZ77_WINOFF_BITS *
* and LZ77_BUFLEN_BITS respectively. *
* *
*****************************************************************************/
#define LZ77_WINDOW_SIZE 4096
#define LZ77_BUFFER_SIZE 32
/*****************************************************************************
* *
* Define the number of bits for LZ77 phrase tokens. *
* *
*****************************************************************************/
#define LZ77_PHRASE_BITS (LZ77_TYPE_BITS+LZ77_WINOFF_BITS\
+LZ77_NEXT_BITS+LZ77_BUFLEN_BITS)
/*****************************************************************************
* *
* Define the number of bits for LZ77 symbol tokens. *
* *
*****************************************************************************/
#define LZ77_SYMBOL_BITS (LZ77_TYPE_BITS+LZ77_NEXT_BITS)
/*****************************************************************************
* *
* --------------------------- Public Interface --------------------------- *
* *
*****************************************************************************/
int huffman_compress(const unsigned char *original, unsigned char
**compressed, int size);
int huffman_uncompress(const unsigned char *compressed, unsigned char
**original);
int lz77_compress(const unsigned char *original, unsigned char **compressed,
int size);
int lz77_uncompress(const unsigned char *compressed, unsigned char
**original);
#endif
Description of Bit Operations
When compressing and uncompressing data, often we need to perform operations on less than a single byte. Therefore, before discussing various methods of data compression, it is important to become familiar with some basic operations for working with data one bit at a time. These operations are necessary because bit operators in C work only with intrinsic integral operands, which are small. The operations presented in this section work with buffers containing any number of bits. Note that the set of operations presented here is rather incomplete. Specifically, only those that are used in this chapter and in Chapter 15, are defined.
Interface for Bit Operations
Name
bit_ get
Synopsis
int bit_get(const unsigned char *bits, int pos);
Return Value
State of the desired bit: 1 or 0.
Description
Gets the state of the bit at position pos in the buffer bits. The leftmost position in the buffer is 0. The state returned is either 1 or 0.
Complexity
O (1)
Name
bit_set
Synopsis
void bit_set(unsigned char *bits, int pos, int state);
Return Value
None.
Description
Sets the state of the bit at position pos in the buffer bits to the value specified by state. The leftmost position in the buffer is 0. The state must be 1 or 0.
Complexity
O (1)
Name
bit_xor
Synopsis
void bit_xor(const unsigned char *bits1, const unsigned char *bits2,