Skeleton code for zlib inflate routine

inflate.c

#include "inflate.h"

int inflate(char *output, int *output_length, const char *input, int input_length) {

	final_block = 0;
	do {
		get_block_type();

		switch(block_type) {

		case 0: /* uncompressed */
			discard_partial_byte();
			get_block_length();

			copy_bytes(output, input, length);

			input += length; output += length;
			break;

		case 1: /* static Huffman */
			do {
				static_get_literal_or_length();
				if (length > 0)
				{
					static_get_distance();
					copy_buffer_bytes(output, distance, length);
				}
				else if (literal != 256)
				{
					copy_byte(output, literal);
				}
			} while (literal != 256);
			break;

		case 2: /* dynamic Huffman */

			/* get sizes of litlen/distance code tables, and of the mini code table used to construct them */
			request_bits(14);
			num_litlen_codes = 257 + get_bits(5); /* 257..286 */
			num_dist_codes = 1 + get_bits(5);     /* 1..32 */
			num_clen_codes = 4 + get_bits(4);     /* 4..19 */

			/* get mini clen table */
			request_bits(num_clen_codes * 3); /* (needs space for up to (7 + 3*19) which is exactly 64 bits!) */
			make_clen_codes();

			/* codelengths stream */
			while (codepos < num_litlen_codes + num_dist_codes) {
				get_clen_or_runlength();
				if (clen_code < 16) {
					codelengths[codepos++] = clen_code;
				} else {
					/* run length encoding: either previous code or 0 */
					/* note: watch out for codepos-1 < 0 and codepos >= num_litlen_codes + num_dist_codes! */
					repeat_code = (clen_code == 16)? codelengths[codepos-1] : 0;
					for (; runlength > 0; runlength--) { codelength[codepos++] = repeat_code; }
				}
			}
			make_litlen_and_dist_codes();

			/* main stream, as with static codes above */
			do {
				get_literal_or_length();
				if (length > 0)
				{
					get_distance();
					copy_buffer_bytes(output, distance, length);
				}
				else if (literal != 256)
				{
					copy_byte(output, literal);
				}
			} while (literal != 256);

			default: /* invalid block type */
				return ERROR;
		}

	} while (!final_block);

}

inflate.h

static inline void get_block_type() {
	require_bits(3);
	final_block = get_bits(1);
	block_type = get_bits(2);
}

static inline void discard_partial_byte() {
	discard_bits(bits_length & 7);
}

static inline unsigned int read_bits(int n) {
	return bits & ((1 << n) - 1);
}

static inline void discard_bits(int n) {
	bits >>= (n);
	bits_length -= (n);
}

static inline unsigned int read_bits(int n) {
	unsigned int ret = read_bits(n);
	discard_bits(n);
	return ret;
}

static inline int get_block_length() {
	block_length = get_bits(16);
	int block_length_check = get_bits(16);
	if ((block_length_check ^ 0xFFFF) != block_length) {
		return -1;
	}
	return block_length;
}

static inline int require_bits(int n) {

	while (bits_length < n) {
		add_byte();
	}
}

static inline int get_byte() {
	/* potential end-of-input error */
	int ret = *input;
	input++;
	input_length--;
	return ret;
}

static inline int add_byte() {
	/* potential end-of-input error in get_byte() */
	/* note: bits assumed to be empty */
	unsigned long long next_byte = get_byte();
	bits |= (next_byte << bits_length);
	bits_length += 8;
}

static void copy_byte(int literal) {
	/* potential end-of-output error */
	*(output++) = literal;
	bytes_out++;
}

static inline int copy_bytes(int length) {
	/* potential end-of-input error in read_byte() */
	/* potential end-of-output error in copy_byte() */
	for (int i = 0; i < length; i++) {
		copy_byte(*read_byte());
		input_length--;
	}
}

static unsigned long long bits;
static int bits_length;
static int block_type, final_block;
static int literal, length;

static enum {
	ERR_NONE = 0; OK = ERR_NONE;
	ERR_END_OF_INPUT;
	ERR_END_OF_OUTPUT;
} error;