simple-lz77.c

simple-lz77压缩算法

/* simple-lz77.c -- Simple LZ77 (Ziv-Lempel) encoding [compression] with
** fixed offset/legth sizes [fixed size window of 4096 {2**12} bytes,
** match lengths of 15 {2**4-1} bytes] and alternating pointers into the
** window dictionary and new symbols [characters].
** The implementation is not optimized for speed [but for simplicity of
** code and data structures].
**
** Copyright (C) 1992,2004 Eric Laroche.  All rights reserved.
**
** @author Eric Laroche <[e-mail]>, www.lrdev.com
** @version @(#)$Id: simple-lz77.c,v 1.1 2004/05/06 13:27:28 laroche Exp $
**
** Patents may apply to algorithms implemented by this code;
** you need to ensure that your use of such algorithms is legal.
**
** This program is free software;
** you can redistribute it and/or modify it.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
**
*/


/* [implemented interface] */
#include "simple-lz77.h"


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <assert.h>


/** OFFSETBITS+LENGTHBITS.
* POINTERBITS%8 must be 0 to have the encoding output byte-aligned.
*/
#define POINTERBITS 16

/** Number of bits used in encoding offsets into the dictionary window.
* The window size will be 1<<OFFSETBITS.
* Since OFFSETBITS+LENGTHBITS==POINTERBITS [to have byte-aligned bits] and
* LENGTHBITS<=OFFSETBITS [larger strings than window size can't be found
* {if lookahead-self-referencing matches are not considered}] and
* LENGTHBITS>=2 [very short matches don't compress], OFFSETBITS ranges
* from 8 to 14.
*/
#define OFFSETBITS 12

/** Number of bits used to encode lengths of string matches.
* OFFSETBITS+LENGTHBITS are a multiple of 8 to have byte-aligned bits.
*/
#define LENGTHBITS (POINTERBITS - OFFSETBITS)  /* 4 */

#define WINDOWSIZE (1 << OFFSETBITS)  /* 4096 */
#define LOOKAHEADSIZE ((1 << LENGTHBITS) - 1)  /* 15 */
#define POINTERBYTES (POINTERBITS / 8)  /* 2 */


/* typedef struct lz77_st lz77; */

/** A simple Ziv-Lempel 77 dictionary.
*/
struct lz77_st
{
	/** Dictionary window.
	*/
	char window[WINDOWSIZE];
};


/* [local functions] */
static void decodeByDictionary(lz77*, char const*, int, int*, char*, int, int*);
static void encodeByDictionary(lz77*, char const*, int, int*, char*, int, int*);
static int fillBuffer(char*, int, FILE*);
static void findLargest(char const*, int, char const*, int, int*, int*);
static int gcd(int, int);
static int matchLength(char const*, int, char const*, int);
static int maxDictionaryDecodingIn(void);
static int maxDictionaryDecodingOut(void);
static int maxDictionaryEncodingIn(void);
static int maxDictionaryEncodingOut(void);
static void* memrot(void*, int, int);
static int putN(char const*, int, FILE*);
static void updateDictionary(lz77*, char const*, int);


/** Get a lz77 encoder.
* Initiates encoder's state (its dictionary).
* Returns NULL if memory allocation failed.
*/
lz77* lz77_new(void)
{
	lz77* p;

	p = (lz77*)malloc(sizeof(*p));
	if (p == NULL) {
		return NULL;
	}

	assert(WINDOWSIZE > 0);

	/* initialize {en/de}coder/dictionary state */
	memset(p->window, 0, WINDOWSIZE);  /* zeroed dictionary */

	return p;
}


/** Dispose a lz77 encoder.
*/
void lz77_delete(lz77* p)
{
	if (p == NULL) {  /* NULL is ok as argument */
		return;
	}

	free(p);
}


/** Encode a file stream with a lz77 encoder.
* Does not initiate encoder's state (its dictionary).
*/
void lz77_encode(lz77* p, FILE* in, FILE* out)
{
	int bufferSize, bufferLength, consumed, produced, n;
	char* lookAheadBuffer;
	char outBuffer[2];

	/* have one spare byte besides the look-ahead, for the symbol */
	bufferSize = maxDictionaryEncodingIn() + 1;  /* 15+1 */

	lookAheadBuffer = (char*)malloc(bufferSize);
	if (lookAheadBuffer == NULL) {
		return;
	}

	assert(sizeof(outBuffer) >= maxDictionaryEncodingOut());
	assert(sizeof(outBuffer) == POINTERBYTES);

	bufferLength = 0;

	/* encode */
	for (;;) {

		assert(bufferSize - bufferLength >= 0);

		/* Try to fill the look-ahead buffer.
		* Note: this will check for end-of-input-file-stream more than once.
		*/
		bufferLength += fillBuffer(
			&lookAheadBuffer[bufferLength],
			bufferSize - bufferLength,
			in);

		assert(bufferLength >= 0);
		assert(bufferLength <= bufferSize);

		/* check if all input is done */
		if (bufferLength == 0) {  /* fillBuffer above only caught EOF */
			break;
		}

		/* encode and output pointers */

		consumed = 0;
		produced = 0;
		encodeByDictionary(
			p,
			lookAheadBuffer,
			bufferLength - 1,  /* spare one for the new symbol */
			&consumed,
			outBuffer,
			sizeof(outBuffer),
			&produced);

		assert(consumed >= 0);
		assert(consumed < bufferLength);
		assert(produced == POINTERBYTES);
		assert(POINTERBYTES == 2);

		n = putN(outBuffer, 2, out);
		if (n < 2) {  /* output error */
			break;
		}

		/* update dictionary */
		updateDictionary(p, lookAheadBuffer, consumed);

		assert(bufferLength - consumed >= 0);

		memmove(lookAheadBuffer, &lookAheadBuffer[consumed], bufferLength - consumed);
		bufferLength -= consumed;

		/* output new-symbol */

		assert(bufferLength >= 1);

		n = putN(lookAheadBuffer, 1, out);
		if (n < 1) {  /* output error */
			break;
		}

		/* update dictionary */
		updateDictionary(p, lookAheadBuffer, 1);

		memmove(lookAheadBuffer, &lookAheadBuffer[1], bufferLength - 1);
		bufferLength--;
	}

	free(lookAheadBuffer);
}


/** Try to fill a buffer.
*/
static int fillBuffer(char* buffer, int size, FILE* in)
{
	int i;
	int c;

	assert(buffer != NULL);
	assert(size >= 0);
	assert(in != NULL);

	i = 0;
	while (i < size) {

		c = getc(in);
		if (c == EOF) {
			break;
		}

		buffer[i++] = (char)c;
	}

	return i;
}


/** Try to write a buffer.
*/
static int putN(char const* buffer, int size, FILE* out)
{
	int i;
	int s;

	assert(buffer != NULL);
	assert(size >= 0);
	assert(out != NULL);

	i = 0;
	while (i < size) {

		s = putc(buffer[i], out);
		if (s == EOF) {  /* output error */
			break;
		}

		i++;
	}

	return i;
}


/** Decode a file stream with a lz77 decoder.
* Does not initiate decoder's state (its dictionary).
*/
void lz77_decode(lz77* p, FILE* in, FILE* out)
{
	int bufferSize, n, consumed, produced;
	char* decodeBuffer;
	char inBuffer[2];
	char cc;

	bufferSize = maxDictionaryDecodingOut();  /* 15 */

	decodeBuffer = (char*)malloc(bufferSize);
	if (decodeBuffer == NULL) {
		return;
	}

	assert(sizeof(inBuffer) >= maxDictionaryDecodingIn());
	assert(sizeof(inBuffer) == POINTERBYTES);

	/* decode */
	for (;;) {

		/* fill in-buffer */
		n = fillBuffer(inBuffer, 2, in);
		if (n == 0) {  /* done */
			break;
		}

		if (n < 2) {  /* done at an unexpected position -- partial pointer */
			break;
		}

		/* decode and output */

		consumed = 0;
		produced = 0;
		decodeByDictionary(
			p,
			inBuffer,
			POINTERBYTES,
			&consumed,
			decodeBuffer,
			bufferSize,
			&produced);

		assert(consumed == POINTERBYTES);
		assert(POINTERBYTES == 2);
		assert(produced >= 0);
		assert(produced <= bufferSize);

		n = putN(decodeBuffer, produced, out);
		if (n < produced) {  /* output error */
			break;
		}

		/* update dictionary */
		updateDictionary(p, decodeBuffer, produced);

		/* output new-symbol */

		n = fillBuffer(&cc, 1, in);
		if (n == 0) {  /* done at an unexpected position -- missing last new symbol */
			break;
		}

		n = putN(&cc, 1, out);
		if (n == 0) {  /* output error */
			break;
		}

		/* update dictionary */
		updateDictionary(p, &cc, 1);
	}

	free(decodeBuffer);
}