• Choose a category
• All
• Classic-Fiction

By Root 1505 0

until there are no more symbols to process. We use ipos to keep track of the current bit being processed in the compressed data, and opos to keep track of the current byte we are writing to the buffer of restored data. During each iteration of the loop, we first read one bit from the compressed data to determine the type of token we are about to decode.

At the start of interpreting a token, if the first bit read is 1, we have encountered a phrase token. Thus, we read each of its members, look up the phrase in the sliding window, and write the phrase to the buffer of restored data. As we look up each phrase, we call the network function ntohl to ensure that the byte ordering of its offset and length in the window are correct for the system. This step is required because both the offset and length are in big-endian format when read from the compressed data. The look-ahead buffer is used as a convenient place to temporarily store the data before copying it into the sliding window. Last, we write the unmatched symbol encoded by the token. If the first bit read for the token is 0, we have encountered a symbol token. In this case, we write the one unmatched symbol it encodes to the buffer of restored data.

Once we write the decoded data to the buffer of restored data, we adjust the sliding window. To move the data through the sliding window, we shift the decoded data in from the right side of the window and out the left. The number of bytes we move is equal to the number of symbols we decode from the token.

The runtime complexity of lz77_uncompress is O (n), where n is the number of symbols in the original data. This is because for each of the n/c tokens in which the data is encoded, where 1/c is a constant factor that represents how efficiently symbols are encoded in phrase tokens, we perform the constant-time operation of copying symbols from the sliding window to the buffer of restored data. Thus, the runtime complexity of lz77_uncompress is O (n). Its lack of significant constant factors explains its generally superior performance to huffman_uncompress and its vast improvement in actual running time over lz77_compress.

Example 14.5. Implementation of LZ77

/*****************************************************************************

* *

* -------------------------------- lz77.c -------------------------------- *

* *

*****************************************************************************/

#include

#include

#include

#include "bit.h"

#include "compress.h"

/*****************************************************************************

* *

* ------------------------------ compare_win ----------------------------- *

* *

*****************************************************************************/

static int compare_win(const unsigned char *window, const unsigned char

*buffer, int *offset, unsigned char *next) {

int match,

longest,

i,

j,

k;

/*****************************************************************************

* *

* Initialize the offset, although it is valid only once a match is found. *

* *

*****************************************************************************/

*offset = 0;

/*****************************************************************************

* *

* If no match is found, prepare to return 0 and the next symbol in the *

* look-ahead buffer. *

* *

*****************************************************************************/

longest = 0;

*next = buffer[0];

/*****************************************************************************

* *

* Look for the best match in the look-ahead buffer and sliding window. *

* *

*****************************************************************************/

for (k = 0; k < LZ77_WINDOW_SIZE; k++) {

i = k;

j = 0;

match = 0;

/**************************************************************************

* *

* Determine how many symbols match in the sliding window at offset k. *

* *

**************************************************************************/