[deflate] Add support for DEFLATE decompression

Signed-off-by: Michael Brown <mcb30@ipxe.org>

5 files changed, 1569 insertions, 0 deletions

diff --git a/src/crypto/deflate.c b/src/crypto/deflate.c
new file mode 100644
index 0000000..1854eff
--- /dev/null
+++ b/src/crypto/deflate.c
@@ -0,0 +1,1045 @@
+/*
+ * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * 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.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <string.h>
+#include <strings.h>
+#include <errno.h>
+#include <assert.h>
+#include <ctype.h>
+#include <ipxe/uaccess.h>
+#include <ipxe/deflate.h>
+
+/** @file
+ *
+ * DEFLATE decompression algorithm
+ *
+ * This file implements the decompression half of the DEFLATE
+ * algorithm specified in RFC 1951.
+ *
+ * Portions of this code are derived from wimboot's xca.c.
+ *
+ */
+
+/**
+ * Byte reversal table
+ *
+ * For some insane reason, the DEFLATE format stores some values in
+ * bit-reversed order.
+ */
+static uint8_t deflate_reverse[256];
+
+/** Literal/length base values
+ *
+ * We include entries only for literal/length codes 257-284.  Code 285
+ * does not fit the pattern (it represents a length of 258; following
+ * the pattern from the earlier codes would give a length of 259), and
+ * has no extra bits.  Codes 286-287 are invalid, but can occur.  We
+ * treat any code greater than 284 as meaning "length 285, no extra
+ * bits".
+ */
+static uint8_t deflate_litlen_base[28];
+
+/** Distance base values
+ *
+ * We include entries for all possible codes 0-31, avoiding the need
+ * to check for undefined codes 30 and 31 before performing the
+ * lookup.  Codes 30 and 31 are never initialised, and will therefore
+ * be treated as meaning "14 extra bits, base distance 0".
+ */
+static uint16_t deflate_distance_base[32];
+
+/** Code length map */
+static uint8_t deflate_codelen_map[19] = {
+	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
+};
+
+/** Static Huffman alphabet length patterns */
+static struct deflate_static_length_pattern deflate_static_length_patterns[] = {
+	/* Literal/length code lengths */
+	{ 0x88, ( ( ( 143 -   0 ) + 1 ) / 2 ) },
+	{ 0x99, ( ( ( 255 - 144 ) + 1 ) / 2 ) },
+	{ 0x77, ( ( ( 279 - 256 ) + 1 ) / 2 ) },
+	{ 0x88, ( ( ( 287 - 280 ) + 1 ) / 2 ) },
+	/* Distance code lengths */
+	{ 0x55, ( ( (  31 -   0 ) + 1 ) / 2 ) },
+	/* End marker */
+	{ 0, 0 }
+};
+
+/**
+ * Transcribe binary value (for debugging)
+ *
+ * @v value		Value
+ * @v bits		Length of value (in bits)
+ * @ret string		Transcribed value
+ */
+static const char * deflate_bin ( unsigned long value, unsigned int bits ) {
+	static char buf[ ( 8 * sizeof ( value ) ) + 1 /* NUL */ ];
+	char *out = buf;
+
+	/* Sanity check */
+	assert ( bits < sizeof ( buf ) );
+
+	/* Transcribe value */
+	while ( bits-- )
+		*(out++) = ( ( value & ( 1 << bits ) ) ? '1' : '0' );
+	*out = '\0';
+
+	return buf;
+}
+
+/**
+ * Set Huffman symbol length
+ *
+ * @v deflate		Decompressor
+ * @v index		Index within lengths
+ * @v bits		Symbol length (in bits)
+ */
+static void deflate_set_length ( struct deflate *deflate, unsigned int index,
+				 unsigned int bits ) {
+
+	deflate->lengths[ index / 2 ] |= ( bits << ( 4 * ( index % 2 ) ) );
+}
+
+/**
+ * Get Huffman symbol length
+ *
+ * @v deflate		Decompressor
+ * @v index		Index within lengths
+ * @ret bits		Symbol length (in bits)
+ */
+static unsigned int deflate_length ( struct deflate *deflate,
+				     unsigned int index ) {
+
+	return ( ( deflate->lengths[ index / 2 ] >> ( 4 * ( index % 2 ) ) )
+		 & 0x0f );
+}
+
+/**
+ * Determine Huffman alphabet name (for debugging)
+ *
+ * @v deflate		Decompressor
+ * @v alphabet		Huffman alphabet
+ * @ret name		Alphabet name
+ */
+static const char * deflate_alphabet_name ( struct deflate *deflate,
+					    struct deflate_alphabet *alphabet ){
+
+	if ( alphabet == &deflate->litlen ) {
+		return "litlen";
+	} else if ( alphabet == &deflate->distance_codelen ) {
+		return "distance/codelen";
+	} else {
+		return "<UNKNOWN>";
+	}
+}
+
+/**
+ * Dump Huffman alphabet (for debugging)
+ *
+ * @v deflate		Decompressor
+ * @v alphabet		Huffman alphabet
+ */
+static void deflate_dump_alphabet ( struct deflate *deflate,
+				    struct deflate_alphabet *alphabet ) {
+	struct deflate_huf_symbols *huf_sym;
+	unsigned int bits;
+	unsigned int huf;
+	unsigned int i;
+
+	/* Do nothing unless debugging is enabled */
+	if ( ! DBG_EXTRA )
+		return;
+
+	/* Dump symbol table for each utilised length */
+	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
+				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
+		huf_sym = &alphabet->huf[ bits - 1 ];
+		if ( huf_sym->freq == 0 )
+			continue;
+		huf = ( huf_sym->start >> huf_sym->shift );
+		DBGC2 ( alphabet, "DEFLATE %p \"%s\" length %d start \"%s\" "
+			"freq %d:", deflate,
+			deflate_alphabet_name ( deflate, alphabet ), bits,
+			deflate_bin ( huf, huf_sym->bits ), huf_sym->freq );
+		for ( i = 0 ; i < huf_sym->freq ; i++ ) {
+			DBGC2 ( alphabet, " %03x",
+				huf_sym->raw[ huf + i ] );
+		}
+		DBGC2 ( alphabet, "\n" );
+	}
+
+	/* Dump quick lookup table */
+	DBGC2 ( alphabet, "DEFLATE %p \"%s\" quick lookup:", deflate,
+		deflate_alphabet_name ( deflate, alphabet ) );
+	for ( i = 0 ; i < ( sizeof ( alphabet->lookup ) /
+			    sizeof ( alphabet->lookup[0] ) ) ; i++ ) {
+		DBGC2 ( alphabet, " %d", ( alphabet->lookup[i] + 1 ) );
+	}
+	DBGC2 ( alphabet, "\n" );
+}
+
+/**
+ * Construct Huffman alphabet
+ *
+ * @v deflate		Decompressor
+ * @v alphabet		Huffman alphabet
+ * @v count		Number of symbols
+ * @v offset		Starting offset within length table
+ * @ret rc		Return status code
+ */
+static int deflate_alphabet ( struct deflate *deflate,
+			      struct deflate_alphabet *alphabet,
+			      unsigned int count, unsigned int offset ) {
+	struct deflate_huf_symbols *huf_sym;
+	unsigned int huf;
+	unsigned int cum_freq;
+	unsigned int bits;
+	unsigned int raw;
+	unsigned int adjustment;
+	unsigned int prefix;
+	int complete;
+
+	/* Clear symbol table */
+	memset ( alphabet->huf, 0, sizeof ( alphabet->huf ) );
+
+	/* Count number of symbols with each Huffman-coded length */
+	for ( raw = 0 ; raw < count ; raw++ ) {
+		bits = deflate_length ( deflate, ( raw + offset ) );
+		if ( bits )
+			alphabet->huf[ bits - 1 ].freq++;
+	}
+
+	/* Populate Huffman-coded symbol table */
+	huf = 0;
+	cum_freq = 0;
+	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
+				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
+		huf_sym = &alphabet->huf[ bits - 1 ];
+		huf_sym->bits = bits;
+		huf_sym->shift = ( 16 - bits );
+		huf_sym->start = ( huf << huf_sym->shift );
+		huf_sym->raw = &alphabet->raw[cum_freq];
+		huf += huf_sym->freq;
+		if ( huf > ( 1U << bits ) ) {
+			DBGC ( alphabet, "DEFLATE %p \"%s\" has too many "
+			       "symbols with lengths <=%d\n", deflate,
+			       deflate_alphabet_name ( deflate, alphabet ),
+			       bits );
+			return -EINVAL;
+		}
+		huf <<= 1;
+		cum_freq += huf_sym->freq;
+	}
+	complete = ( huf == ( 1U << bits ) );
+
+	/* Populate raw symbol table */
+	for ( raw = 0 ; raw < count ; raw++ ) {
+		bits = deflate_length ( deflate, ( raw + offset ) );
+		if ( bits ) {
+			huf_sym = &alphabet->huf[ bits - 1 ];
+			*(huf_sym->raw++) = raw;
+		}
+	}
+
+	/* Adjust Huffman-coded symbol table raw pointers and populate
+	 * quick lookup table.
+	 */
+	for ( bits = 1 ; bits <= ( sizeof ( alphabet->huf ) /
+				   sizeof ( alphabet->huf[0] ) ) ; bits++ ) {
+		huf_sym = &alphabet->huf[ bits - 1 ];
+
+		/* Adjust raw pointer */
+		huf_sym->raw -= huf_sym->freq; /* Reset to first symbol */
+		adjustment = ( huf_sym->start >> huf_sym->shift );
+		huf_sym->raw -= adjustment; /* Adjust for quick indexing */
+
+		/* Populate quick lookup table */
+		for ( prefix = ( huf_sym->start >> DEFLATE_HUFFMAN_QL_SHIFT ) ;
+		      prefix < ( 1 << DEFLATE_HUFFMAN_QL_BITS ) ; prefix++ ) {
+			alphabet->lookup[prefix] = ( bits - 1 );
+		}
+	}
+
+	/* Dump alphabet (for debugging) */
+	deflate_dump_alphabet ( deflate, alphabet );
+
+	/* Check that there are no invalid codes */
+	if ( ! complete ) {
+		DBGC ( alphabet, "DEFLATE %p \"%s\" is incomplete\n", deflate,
+		       deflate_alphabet_name ( deflate, alphabet ) );
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
+/**
+ * Attempt to accumulate bits from input stream
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v target		Number of bits to accumulate
+ * @ret excess		Number of excess bits accumulated (may be negative)
+ */
+static int deflate_accumulate ( struct deflate *deflate,
+				struct deflate_chunk *in,
+				unsigned int target ) {
+	uint8_t byte;
+
+	while ( deflate->bits < target ) {
+
+		/* Check for end of input */
+		if ( in->offset >= in->len )
+			break;
+
+		/* Acquire byte from input */
+		copy_from_user ( &byte, in->data, in->offset++,
+				 sizeof ( byte ) );
+		deflate->accumulator = ( deflate->accumulator |
+					 ( byte << deflate->bits ) );
+		deflate->rotalumucca = ( deflate->rotalumucca |
+					 ( deflate_reverse[byte] <<
+					   ( 24 - deflate->bits ) ) );
+		deflate->bits += 8;
+
+		/* Sanity check */
+		assert ( deflate->bits <=
+			 ( 8 * sizeof ( deflate->accumulator ) ) );
+	}
+
+	return ( deflate->bits - target );
+}
+
+/**
+ * Consume accumulated bits from the input stream
+ *
+ * @v deflate		Decompressor
+ * @v count		Number of accumulated bits to consume
+ * @ret data		Consumed bits
+ */
+static int deflate_consume ( struct deflate *deflate, unsigned int count ) {
+	int data;
+
+	/* Sanity check */
+	assert ( count <= deflate->bits );
+
+	/* Extract data and consume bits */
+	data = ( deflate->accumulator & ( ( 1 << count ) - 1 ) );
+	deflate->accumulator >>= count;
+	deflate->rotalumucca <<= count;
+	deflate->bits -= count;
+
+	return data;
+}
+
+/**
+ * Attempt to extract a fixed number of bits from input stream
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v target		Number of bits to extract
+ * @ret data		Extracted bits (or negative if not yet accumulated)
+ */
+static int deflate_extract ( struct deflate *deflate, struct deflate_chunk *in,
+			     unsigned int target ) {
+	int excess;
+	int data;
+
+	/* Return immediately if we are attempting to extract zero bits */
+	if ( target == 0 )
+		return 0;
+
+	/* Attempt to accumulate bits */
+	excess = deflate_accumulate ( deflate, in, target );
+	if ( excess < 0 )
+		return excess;
+
+	/* Extract data and consume bits */
+	data = deflate_consume ( deflate, target );
+	DBGCP ( deflate, "DEFLATE %p extracted %s = %#x = %d\n", deflate,
+		deflate_bin ( data, target ), data, data );
+
+	return data;
+}
+
+/**
+ * Attempt to decode a Huffman-coded symbol from input stream
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v alphabet		Huffman alphabet
+ * @ret code		Raw code (or negative if not yet accumulated)
+ */
+static int deflate_decode ( struct deflate *deflate,
+			    struct deflate_chunk *in,
+			    struct deflate_alphabet *alphabet ) {
+	struct deflate_huf_symbols *huf_sym;
+	uint16_t huf;
+	unsigned int lookup_index;
+	int excess;
+	unsigned int raw;
+
+	/* Attempt to accumulate maximum required number of bits.
+	 * There may be fewer bits than this remaining in the stream,
+	 * even if the stream still contains some complete
+	 * Huffman-coded symbols.
+	 */
+	deflate_accumulate ( deflate, in, DEFLATE_HUFFMAN_BITS );
+
+	/* Normalise the bit-reversed accumulated value to 16 bits */
+	huf = ( deflate->rotalumucca >> 16 );
+
+	/* Find symbol set for this length */
+	lookup_index = ( huf >> DEFLATE_HUFFMAN_QL_SHIFT );
+	huf_sym = &alphabet->huf[ alphabet->lookup[ lookup_index ] ];
+	while ( huf < huf_sym->start )
+		huf_sym--;
+
+	/* Calculate number of excess bits, and return if not yet complete */
+	excess = ( deflate->bits - huf_sym->bits );
+	if ( excess < 0 )
+		return excess;
+
+	/* Consume bits */
+	deflate_consume ( deflate, huf_sym->bits );
+
+	/* Look up raw symbol */
+	raw = huf_sym->raw[ huf >> huf_sym->shift ];
+	DBGCP ( deflate, "DEFLATE %p decoded %s = %#x = %d\n", deflate,
+		deflate_bin ( ( huf >> huf_sym->shift ), huf_sym->bits ),
+		raw, raw );
+
+	return raw;
+}
+
+/**
+ * Discard bits up to the next byte boundary
+ *
+ * @v deflate		Decompressor
+ */
+static void deflate_discard_to_byte ( struct deflate *deflate ) {
+
+	deflate_consume ( deflate, ( deflate->bits & 7 ) );
+}
+
+/**
+ * Copy data to output buffer (if available)
+ *
+ * @v out		Output data buffer
+ * @v start		Source data
+ * @v offset		Starting offset within source data
+ * @v len		Length to copy
+ */
+static void deflate_copy ( struct deflate_chunk *out,
+			   userptr_t start, size_t offset, size_t len ) {
+	size_t out_offset = out->offset;
+	size_t copy_len;
+
+	/* Copy data one byte at a time, to allow for overlap */
+	if ( out_offset < out->len ) {
+		copy_len = ( out->len - out_offset );
+		if ( copy_len > len )
+			copy_len = len;
+		while ( copy_len-- ) {
+			memcpy_user ( out->data, out_offset++,
+				      start, offset++, 1 );
+		}
+	}
+	out->offset += len;
+}
+
+/**
+ * Inflate compressed data
+ *
+ * @v deflate		Decompressor
+ * @v in		Compressed input data
+ * @v out		Output data buffer
+ * @ret rc		Return status code
+ *
+ * The caller can use deflate_finished() to determine whether a
+ * successful return indicates that the decompressor is merely waiting
+ * for more input.
+ *
+ * Data will not be written beyond the specified end of the output
+ * data buffer, but the offset within the output data buffer will be
+ * updated to reflect the amount that should have been written.  The
+ * caller can use this to find the length of the decompressed data
+ * before allocating the output data buffer.
+ */
+int deflate_inflate ( struct deflate *deflate,
+		      struct deflate_chunk *in,
+		      struct deflate_chunk *out ) {
+
+	/* This could be implemented more neatly if gcc offered a
+	 * means for enforcing tail recursion.
+	 */
+	if ( deflate->resume ) {
+		goto *(deflate->resume);
+	} else switch ( deflate->format ) {
+		case DEFLATE_RAW:	goto block_header;
+		case DEFLATE_ZLIB:	goto zlib_header;
+		default:		assert ( 0 );
+	}
+
+ zlib_header: {
+		int header;
+		int cm;
+
+		/* Extract header */
+		header = deflate_extract ( deflate, in, ZLIB_HEADER_BITS );
+		if ( header < 0 ) {
+			deflate->resume = &&zlib_header;
+			return 0;
+		}
+
+		/* Parse header */
+		cm = ( ( header >> ZLIB_HEADER_CM_LSB ) & ZLIB_HEADER_CM_MASK );
+		if ( cm != ZLIB_HEADER_CM_DEFLATE ) {
+			DBGC ( deflate, "DEFLATE %p unsupported ZLIB "
+			       "compression method %d\n", deflate, cm );
+			return -ENOTSUP;
+		}
+		if ( header & ( 1 << ZLIB_HEADER_FDICT_BIT ) ) {
+			DBGC ( deflate, "DEFLATE %p unsupported ZLIB preset "
+			       "dictionary\n", deflate );
+			return -ENOTSUP;
+		}
+
+		/* Process first block header */
+		goto block_header;
+	}
+
+ block_header: {
+		int header;
+		int bfinal;
+		int btype;
+
+		/* Extract block header */
+		header = deflate_extract ( deflate, in, DEFLATE_HEADER_BITS );
+		if ( header < 0 ) {
+			deflate->resume = &&block_header;
+			return 0;
+		}
+
+		/* Parse header */
+		deflate->header = header;
+		bfinal = ( header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) );
+		btype = ( header >> DEFLATE_HEADER_BTYPE_LSB );
+		DBGC ( deflate, "DEFLATE %p found %sblock type %#x\n",
+		       deflate, ( bfinal ? "final " : "" ), btype );
+		switch ( btype ) {
+		case DEFLATE_HEADER_BTYPE_LITERAL:
+			goto literal_block;
+		case DEFLATE_HEADER_BTYPE_STATIC:
+			goto static_block;
+		case DEFLATE_HEADER_BTYPE_DYNAMIC:
+			goto dynamic_block;
+		default:
+			DBGC ( deflate, "DEFLATE %p unsupported block type "
+			       "%#x\n", deflate, btype );
+			return -ENOTSUP;
+		}
+	}
+
+ literal_block: {
+
+		/* Discard any bits up to the next byte boundary */
+		deflate_discard_to_byte ( deflate );
+	}
+
+ literal_len: {
+		int len;
+
+		/* Extract LEN field */
+		len = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS );
+		if ( len < 0 ) {
+			deflate->resume = &&literal_len;
+			return 0;
+		}
+
+		/* Record length of literal data */
+		deflate->remaining = len;
+		DBGC2 ( deflate, "DEFLATE %p literal block length %#04zx\n",
+			deflate, deflate->remaining );
+	}
+
+ literal_nlen: {
+		int nlen;
+
+		/* Extract NLEN field */
+		nlen = deflate_extract ( deflate, in, DEFLATE_LITERAL_LEN_BITS);
+		if ( nlen < 0 ) {
+			deflate->resume = &&literal_nlen;
+			return 0;
+		}
+
+		/* Verify NLEN */
+		if ( ( ( deflate->remaining ^ ~nlen ) &
+		       ( ( 1 << DEFLATE_LITERAL_LEN_BITS ) - 1 ) ) != 0 ) {
+			DBGC ( deflate, "DEFLATE %p invalid len/nlen "
+			       "%#04zx/%#04x\n", deflate,
+			       deflate->remaining, nlen );
+			return -EINVAL;
+		}
+	}
+
+ literal_data: {
+		size_t in_remaining;
+		size_t len;
+
+		/* Calculate available amount of literal data */
+		in_remaining = ( in->len - in->offset );
+		len = deflate->remaining;
+		if ( len < in_remaining )
+			len = in_remaining;
+
+		/* Copy data to output buffer */
+		deflate_copy ( out, in->data, in->offset, len );
+
+		/* Consume data from input buffer */
+		in->offset += len;
+		deflate->remaining -= len;
+
+		/* Finish processing if we are blocked */
+		if ( deflate->remaining ) {
+			deflate->resume = &&literal_data;
+			return 0;
+		}
+
+		/* Otherwise, finish block */
+		goto block_done;
+	}
+
+ static_block: {
+		struct deflate_static_length_pattern *pattern;
+		uint8_t *lengths = deflate->lengths;
+
+		/* Construct static Huffman lengths as per RFC 1950 */
+		for ( pattern = deflate_static_length_patterns ;
+		      pattern->count ; pattern++ ) {
+			memset ( lengths, pattern->fill, pattern->count );
+			lengths += pattern->count;
+		}
+		deflate->litlen_count = 288;
+		deflate->distance_count = 32;
+		goto construct_alphabets;
+	}
+
+ dynamic_block:
+
+ dynamic_header: {
+		int header;
+		unsigned int hlit;
+		unsigned int hdist;
+		unsigned int hclen;
+
+		/* Extract block header */
+		header = deflate_extract ( deflate, in, DEFLATE_DYNAMIC_BITS );
+		if ( header < 0 ) {
+			deflate->resume = &&dynamic_header;
+			return 0;
+		}
+
+		/* Parse header */
+		hlit = ( ( header >> DEFLATE_DYNAMIC_HLIT_LSB ) &
+			 DEFLATE_DYNAMIC_HLIT_MASK );
+		hdist = ( ( header >> DEFLATE_DYNAMIC_HDIST_LSB ) &
+			  DEFLATE_DYNAMIC_HDIST_MASK );
+		hclen = ( ( header >> DEFLATE_DYNAMIC_HCLEN_LSB ) &
+			  DEFLATE_DYNAMIC_HCLEN_MASK );
+		deflate->litlen_count = ( hlit + 257 );
+		deflate->distance_count = ( hdist + 1 );
+		deflate->length_index = 0;
+		deflate->length_target = ( hclen + 4 );
+		DBGC2 ( deflate, "DEFLATE %p dynamic block %d codelen, %d "
+			"litlen, %d distance\n", deflate,
+			deflate->length_target, deflate->litlen_count,
+			deflate->distance_count );
+
+		/* Prepare for decoding code length code lengths */
+		memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
+	}
+
+ dynamic_codelen: {
+		int len;
+		unsigned int index;
+		int rc;
+
+		/* Extract all code lengths */
+		while ( deflate->length_index < deflate->length_target ) {
+
+			/* Extract code length length */
+			len = deflate_extract ( deflate, in,
+						DEFLATE_CODELEN_BITS );
+			if ( len < 0 ) {
+				deflate->resume = &&dynamic_codelen;
+				return 0;
+			}
+
+			/* Store code length */
+			index = deflate_codelen_map[deflate->length_index++];
+			deflate_set_length ( deflate, index, len );
+			DBGCP ( deflate, "DEFLATE %p codelen for %d is %d\n",
+				deflate, index, len );
+		}
+
+		/* Generate code length alphabet */
+		if ( ( rc = deflate_alphabet ( deflate,
+					       &deflate->distance_codelen,
+					       ( DEFLATE_CODELEN_MAX_CODE + 1 ),
+					       0 ) ) != 0 )
+			return rc;
+
+		/* Prepare for decoding literal/length/distance code lengths */
+		memset ( &deflate->lengths, 0, sizeof ( deflate->lengths ) );
+		deflate->length_index = 0;
+		deflate->length_target = ( deflate->litlen_count +
+					   deflate->distance_count );
+		deflate->length = 0;
+	}
+
+ dynamic_litlen_distance: {
+		int len;
+		int index;
+
+		/* Decode literal/length/distance code length */
+		len = deflate_decode ( deflate, in, &deflate->distance_codelen);
+		if ( len < 0 ) {
+			deflate->resume = &&dynamic_litlen_distance;
+			return 0;
+		}
+
+		/* Prepare for extra bits */
+		if ( len < 16 ) {
+			deflate->length = len;
+			deflate->extra_bits = 0;
+			deflate->dup_len = 1;
+		} else {
+			static const uint8_t dup_len[3] = { 3, 3, 11 };
+			static const uint8_t extra_bits[3] = { 2, 3, 7 };
+			index = ( len - 16 );
+			deflate->dup_len = dup_len[index];
+			deflate->extra_bits = extra_bits[index];
+			if ( index )
+				deflate->length = 0;
+		}
+	}
+
+ dynamic_litlen_distance_extra: {
+		int extra;
+		unsigned int dup_len;
+
+		/* Extract extra bits */
+		extra = deflate_extract ( deflate, in, deflate->extra_bits );
+		if ( extra < 0 ) {
+			deflate->resume = &&dynamic_litlen_distance_extra;
+			return 0;
+		}
+
+		/* Store code lengths */
+		dup_len = ( deflate->dup_len + extra );
+		while ( ( deflate->length_index < deflate->length_target ) &&
+			dup_len-- ) {
+			deflate_set_length ( deflate, deflate->length_index++,
+					     deflate->length );
+		}
+
+		/* Process next literal/length or distance code
+		 * length, if more are required.
+		 */
+		if ( deflate->length_index < deflate->length_target )
+			goto dynamic_litlen_distance;
+
+		/* Construct alphabets */
+		goto construct_alphabets;
+	}
+
+ construct_alphabets: {
+		unsigned int distance_offset = deflate->litlen_count;
+		unsigned int distance_count = deflate->distance_count;
+		int rc;
+
+		/* Generate literal/length alphabet */
+		if ( ( rc = deflate_alphabet ( deflate, &deflate->litlen,
+					       deflate->litlen_count, 0 ) ) !=0)
+			return rc;
+
+		/* Handle degenerate case of a single distance code
+		 * (for which it is impossible to construct a valid,
+		 * complete Huffman alphabet).  RFC 1951 states:
+		 *
+		 *   If only one distance code is used, it is encoded
+		 *   using one bit, not zero bits; in this case there
+		 *   is a single code length of one, with one unused
+		 *   code.  One distance code of zero bits means that
+		 *   there are no distance codes used at all (the data
+		 *   is all literals).
+		 *
+		 * If we have only a single distance code, then we
+		 * instead use two distance codes both with length 1.
+		 * This results in a valid Huffman alphabet.  The code
+		 * "0" will mean distance code 0 (which is either
+		 * correct or irrelevant), and the code "1" will mean
+		 * distance code 1 (which is always irrelevant).
+		 */
+		if ( deflate->distance_count == 1 ) {
+
+			deflate->lengths[0] = 0x11;
+			distance_offset = 0;
+			distance_count = 2;
+		}
+
+		/* Generate distance alphabet */
+		if ( ( rc = deflate_alphabet ( deflate,
+					       &deflate->distance_codelen,
+					       distance_count,
+					       distance_offset ) ) != 0 )
+			return rc;
+	}
+
+ lzhuf_litlen: {
+		int code;
+		uint8_t byte;
+		unsigned int extra;
+		unsigned int bits;
+
+		/* Decode Huffman codes */
+		while ( 1 ) {
+
+			/* Decode Huffman code */
+			code = deflate_decode ( deflate, in, &deflate->litlen );
+			if ( code < 0 ) {
+				deflate->resume = &&lzhuf_litlen;
+				return 0;
+			}
+
+			/* Handle according to code type */
+			if ( code < DEFLATE_LITLEN_END ) {
+
+				/* Literal value: copy to output buffer */
+				byte = code;
+				DBGCP ( deflate, "DEFLATE %p literal %#02x "
+					"('%c')\n", deflate, byte,
+					( isprint ( byte ) ? byte : '.' ) );
+				deflate_copy ( out, virt_to_user ( &byte ), 0,
+					       sizeof ( byte ) );
+
+			} else if ( code == DEFLATE_LITLEN_END ) {
+
+				/* End of block */
+				goto block_done;
+
+			} else {
+
+				/* Length code: process extra bits */
+				extra = ( code - DEFLATE_LITLEN_END - 1 );
+				if ( extra < 28 ) {
+					bits = ( extra / 4 );
+					if ( bits )
+						bits--;
+					deflate->extra_bits = bits;
+					deflate->dup_len =
+						deflate_litlen_base[extra];
+				} else {
+					deflate->extra_bits = 0;
+					deflate->dup_len = 258;
+				}
+				goto lzhuf_litlen_extra;
+			}
+		}
+	}
+
+ lzhuf_litlen_extra: {
+		int extra;
+
+		/* Extract extra bits */
+		extra = deflate_extract ( deflate, in, deflate->extra_bits );
+		if ( extra < 0 ) {
+			deflate->resume = &&lzhuf_litlen_extra;
+			return 0;
+		}
+
+		/* Update duplicate length */
+		deflate->dup_len += extra;
+	}
+
+ lzhuf_distance: {
+		int code;
+		unsigned int extra;
+		unsigned int bits;
+
+		/* Decode Huffman code */
+		code = deflate_decode ( deflate, in,
+					&deflate->distance_codelen );
+		if ( code < 0 ) {
+			deflate->resume = &&lzhuf_distance;
+			return 0;
+		}
+
+		/* Process extra bits */
+		extra = code;
+		bits = ( extra / 2 );
+		if ( bits )
+			bits--;
+		deflate->extra_bits = bits;
+		deflate->dup_distance = deflate_distance_base[extra];
+	}
+
+ lzhuf_distance_extra: {
+		int extra;
+		size_t dup_len;
+		size_t dup_distance;
+
+		/* Extract extra bits */
+		extra = deflate_extract ( deflate, in, deflate->extra_bits );
+		if ( extra < 0 ) {
+			deflate->resume = &&lzhuf_distance_extra;
+			return 0;
+		}
+
+		/* Update duplicate distance */
+		dup_distance = ( deflate->dup_distance + extra );
+		dup_len = deflate->dup_len;
+		DBGCP ( deflate, "DEFLATE %p duplicate length %zd distance "
+			"%zd\n", deflate, dup_len, dup_distance );
+
+		/* Sanity check */
+		if ( dup_distance > out->offset ) {
+			DBGC ( deflate, "DEFLATE %p bad distance %zd (max "
+			       "%zd)\n", deflate, dup_distance, out->offset );
+			return -EINVAL;
+		}
+
+		/* Copy data, allowing for overlap */
+		deflate_copy ( out, out->data, ( out->offset - dup_distance ),
+			       dup_len );
+
+		/* Process next literal/length symbol */
+		goto lzhuf_litlen;
+	}
+
+ block_done: {
+
+		DBGCP ( deflate, "DEFLATE %p end of block\n", deflate );
+
+		/* If this was not the final block, process next block header */
+		if ( ! ( deflate->header & ( 1 << DEFLATE_HEADER_BFINAL_BIT ) ))
+			goto block_header;
+
+		/* Otherwise, process footer (if any) */
+		switch ( deflate->format ) {
+		case DEFLATE_RAW:	goto finished;
+		case DEFLATE_ZLIB:	goto zlib_footer;
+		default:		assert ( 0 );
+		}
+	}
+
+ zlib_footer: {
+
+		/* Discard any bits up to the next byte boundary */
+		deflate_discard_to_byte ( deflate );
+	}
+
+ zlib_adler32: {
+		int excess;
+
+		/* Accumulate the 32 bits of checksum.  We don't check
+		 * the value, stop processing immediately afterwards,
+		 * and so don't have to worry about the nasty corner
+		 * cases involved in calling deflate_extract() to
+		 * obtain a full 32 bits.
+		 */
+		excess = deflate_accumulate ( deflate, in, ZLIB_ADLER32_BITS );
+		if ( excess < 0 ) {
+			deflate->resume = &&zlib_adler32;
+			return 0;
+		}
+
+		/* Finish processing */
+		goto finished;
+	}
+
+ finished: {
+		/* Mark as finished and terminate */
+		DBGCP ( deflate, "DEFLATE %p finished\n", deflate );
+		deflate->resume = NULL;
+		return 0;
+	}
+}
+
+/**
+ * Initialise decompressor
+ *
+ * @v deflate		Decompressor
+ * @v format		Compression format code
+ */
+void deflate_init ( struct deflate *deflate, enum deflate_format format ) {
+	static int global_init_done;
+	uint8_t i;
+	uint8_t bit;
+	uint8_t byte;
+	unsigned int base;
+	unsigned int bits;
+
+	/* Perform global initialisation if required */
+	if ( ! global_init_done ) {
+
+		/* Initialise byte reversal table */
+		for ( i = 255 ; i ; i-- ) {
+			for ( bit = 1, byte = 0 ; bit ; bit <<= 1 ) {
+				byte <<= 1;
+				if ( i & bit )
+					byte |= 1;
+			}
+			deflate_reverse[i] = byte;
+		}
+
+		/* Initialise literal/length extra bits table */
+		base = 3;
+		for ( i = 0 ; i < 28 ; i++ ) {
+			bits = ( i / 4 );
+			if ( bits )
+				bits--;
+			deflate_litlen_base[i] = base;
+			base += ( 1 << bits );
+		}
+		assert ( base == 259 ); /* sic */
+
+		/* Initialise distance extra bits table */
+		base = 1;
+		for ( i = 0 ; i < 30 ; i++ ) {
+			bits = ( i / 2 );
+			if ( bits )
+				bits--;
+			deflate_distance_base[i] = base;
+			base += ( 1 << bits );
+		}
+		assert ( base == 32769 );
+
+		/* Record global initialisation as complete */
+		global_init_done = 1;
+	}
+
+	/* Initialise structure */
+	memset ( deflate, 0, sizeof ( *deflate ) );
+	deflate->format = format;
+}
diff --git a/src/include/ipxe/deflate.h b/src/include/ipxe/deflate.h
new file mode 100644
index 0000000..19c5125
--- /dev/null
+++ b/src/include/ipxe/deflate.h
@@ -0,0 +1,283 @@
+#ifndef _IPXE_DEFLATE_H
+#define _IPXE_DEFLATE_H
+
+/** @file
+ *
+ * DEFLATE decompression algorithm
+ *
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+#include <stdint.h>
+#include <string.h>
+#include <ipxe/uaccess.h>
+
+/** Compression formats */
+enum deflate_format {
+	/** Raw DEFLATE data (no header or footer) */
+	DEFLATE_RAW,
+	/** ZLIB header and footer */
+	DEFLATE_ZLIB,
+};
+
+/** Block header length (in bits) */
+#define DEFLATE_HEADER_BITS 3
+
+/** Block header final block flags bit */
+#define DEFLATE_HEADER_BFINAL_BIT 0
+
+/** Block header type LSB */
+#define DEFLATE_HEADER_BTYPE_LSB 1
+
+/** Block header type mask */
+#define DEFLATE_HEADER_BTYPE_MASK 0x03
+
+/** Block header type: literal data */
+#define DEFLATE_HEADER_BTYPE_LITERAL 0
+
+/** Block header type: static Huffman alphabet */
+#define DEFLATE_HEADER_BTYPE_STATIC 1
+
+/** Block header type: dynamic Huffman alphabet */
+#define DEFLATE_HEADER_BTYPE_DYNAMIC 2
+
+/** Literal header LEN/NLEN field length (in bits) */
+#define DEFLATE_LITERAL_LEN_BITS 16
+
+/** Dynamic header length (in bits) */
+#define DEFLATE_DYNAMIC_BITS 14
+
+/** Dynamic header HLIT field LSB */
+#define DEFLATE_DYNAMIC_HLIT_LSB 0
+
+/** Dynamic header HLIT field mask */
+#define DEFLATE_DYNAMIC_HLIT_MASK 0x1f
+
+/** Dynamic header HDIST field LSB */
+#define DEFLATE_DYNAMIC_HDIST_LSB 5
+
+/** Dynamic header HDIST field mask */
+#define DEFLATE_DYNAMIC_HDIST_MASK 0x1f
+
+/** Dynamic header HCLEN field LSB */
+#define DEFLATE_DYNAMIC_HCLEN_LSB 10
+
+/** Dynamic header HCLEN field mask */
+#define DEFLATE_DYNAMIC_HCLEN_MASK 0x0f
+
+/** Dynamic header code length length (in bits) */
+#define DEFLATE_CODELEN_BITS 3
+
+/** Maximum length of a Huffman symbol (in bits) */
+#define DEFLATE_HUFFMAN_BITS 15
+
+/** Quick lookup length for a Huffman symbol (in bits)
+ *
+ * This is a policy decision.
+ */
+#define DEFLATE_HUFFMAN_QL_BITS 7
+
+/** Quick lookup shift */
+#define DEFLATE_HUFFMAN_QL_SHIFT ( 16 - DEFLATE_HUFFMAN_QL_BITS )
+
+/** Literal/length end of block code */
+#define DEFLATE_LITLEN_END 256
+
+/** Maximum value of a literal/length code */
+#define DEFLATE_LITLEN_MAX_CODE 287
+
+/** Maximum value of a distance code */
+#define DEFLATE_DISTANCE_MAX_CODE 31
+
+/** Maximum value of a code length code */
+#define DEFLATE_CODELEN_MAX_CODE 18
+
+/** ZLIB header length (in bits) */
+#define ZLIB_HEADER_BITS 16
+
+/** ZLIB header compression method LSB */
+#define ZLIB_HEADER_CM_LSB 0
+
+/** ZLIB header compression method mask */
+#define ZLIB_HEADER_CM_MASK 0x0f
+
+/** ZLIB header compression method: DEFLATE */
+#define ZLIB_HEADER_CM_DEFLATE 8
+
+/** ZLIB header preset dictionary flag bit */
+#define ZLIB_HEADER_FDICT_BIT 13
+
+/** ZLIB ADLER32 length (in bits) */
+#define ZLIB_ADLER32_BITS 32
+
+/** A Huffman-coded set of symbols of a given length */
+struct deflate_huf_symbols {
+	/** Length of Huffman-coded symbols */
+	uint8_t bits;
+	/** Shift to normalise symbols of this length to 16 bits */
+	uint8_t shift;
+	/** Number of Huffman-coded symbols having this length */
+	uint16_t freq;
+	/** First symbol of this length (normalised to 16 bits)
+	 *
+	 * Stored as a 32-bit value to allow the value 0x10000 to be
+	 * used for empty sets of symbols longer than the maximum
+	 * utilised length.
+	 */
+	uint32_t start;
+	/** Raw symbols having this length */
+	uint16_t *raw;
+};
+
+/** A Huffman-coded alphabet */
+struct deflate_alphabet {
+	/** Huffman-coded symbol set for each length */
+	struct deflate_huf_symbols huf[DEFLATE_HUFFMAN_BITS];
+	/** Quick lookup table */
+	uint8_t lookup[ 1 << DEFLATE_HUFFMAN_QL_BITS ];
+	/** Raw symbols
+	 *
+	 * Ordered by Huffman-coded symbol length, then by symbol
+	 * value.  This field has a variable length.
+	 */
+	uint16_t raw[0];
+};
+
+/** A static Huffman alphabet length pattern */
+struct deflate_static_length_pattern {
+	/** Length pair */
+	uint8_t fill;
+	/** Repetition count */
+	uint8_t count;
+} __attribute__ (( packed ));
+
+/** Decompressor */
+struct deflate {
+	/** Resume point
+	 *
+	 * Used as the target of a computed goto to jump to the
+	 * appropriate point within the state machine.
+	 */
+	void *resume;
+	/** Format */
+	enum deflate_format format;
+
+	/** Accumulator */
+	uint32_t accumulator;
+	/** Bit-reversed accumulator
+	 *
+	 * Don't ask.
+	 */
+	uint32_t rotalumucca;
+	/** Number of bits within the accumulator */
+	unsigned int bits;
+
+	/** Current block header */
+	unsigned int header;
+	/** Remaining length of data (e.g. within a literal block) */
+	size_t remaining;
+	/** Current length index within a set of code lengths */
+	unsigned int length_index;
+	/** Target length index within a set of code lengths */
+	unsigned int length_target;
+	/** Current length within a set of code lengths */
+	unsigned int length;
+	/** Number of extra bits required */
+	unsigned int extra_bits;
+	/** Length of a duplicated string */
+	size_t dup_len;
+	/** Distance of a duplicated string */
+	size_t dup_distance;
+
+	/** Literal/length Huffman alphabet */
+	struct deflate_alphabet litlen;
+	/** Literal/length raw symbols
+	 *
+	 * Must immediately follow the literal/length Huffman alphabet.
+	 */
+	uint16_t litlen_raw[ DEFLATE_LITLEN_MAX_CODE + 1 ];
+	/** Number of symbols in the literal/length Huffman alphabet */
+	unsigned int litlen_count;
+
+	/** Distance and code length Huffman alphabet
+	 *
+	 * The code length Huffman alphabet has a maximum Huffman
+	 * symbol length of 7 and a maximum code value of 18, and is
+	 * thus strictly smaller than the distance Huffman alphabet.
+	 * Since we never need both alphabets simultaneously, we can
+	 * reuse the storage space for the distance alphabet to
+	 * temporarily hold the code length alphabet.
+	 */
+	struct deflate_alphabet distance_codelen;
+	/** Distance and code length raw symbols
+	 *
+	 * Must immediately follow the distance and code length
+	 * Huffman alphabet.
+	 */
+	uint16_t distance_codelen_raw[ DEFLATE_DISTANCE_MAX_CODE + 1 ];
+	/** Number of symbols in the distance Huffman alphabet */
+	unsigned int distance_count;
+
+	/** Huffman code lengths
+	 *
+	 * The literal/length and distance code lengths are
+	 * constructed as a single set of lengths.
+	 *
+	 * The code length Huffman alphabet has a maximum code value
+	 * of 18 and the set of lengths is thus strictly smaller than
+	 * the combined literal/length and distance set of lengths.
+	 * Since we never need both alphabets simultaneously, we can
+	 * reuse the storage space for the literal/length and distance
+	 * code lengths to temporarily hold the code length code
+	 * lengths.
+	 */
+	uint8_t lengths[ ( ( DEFLATE_LITLEN_MAX_CODE + 1 ) +
+			   ( DEFLATE_DISTANCE_MAX_CODE + 1 ) +
+			   1 /* round up */ ) / 2 ];
+};
+
+/** A chunk of data */
+struct deflate_chunk {
+	/** Data */
+	userptr_t data;
+	/** Current offset */
+	size_t offset;
+	/** Length of data */
+	size_t len;
+};
+
+/**
+ * Initialise chunk of data
+ *
+ * @v chunk		Chunk of data to initialise
+ * @v data		Data
+ * @v offset		Starting offset
+ * @v len		Length
+ */
+static inline __attribute__ (( always_inline )) void
+deflate_chunk_init ( struct deflate_chunk *chunk, userptr_t data,
+		     size_t offset, size_t len ) {
+
+	chunk->data = data;
+	chunk->offset = offset;
+	chunk->len = len;
+}
+
+/**
+ * Check if decompression has finished
+ *
+ * @v deflate		Decompressor
+ * @ret finished	Decompression has finished
+ */
+static inline int deflate_finished ( struct deflate *deflate ) {
+	return ( deflate->resume == NULL );
+}
+
+extern void deflate_init ( struct deflate *deflate,
+			   enum deflate_format format );
+extern int deflate_inflate ( struct deflate *deflate,
+			     struct deflate_chunk *in,
+			     struct deflate_chunk *out );
+
+#endif /* _IPXE_DEFLATE_H */
diff --git a/src/include/ipxe/errfile.h b/src/include/ipxe/errfile.h
index 32c596f..1d9397d 100644
--- a/src/include/ipxe/errfile.h
+++ b/src/include/ipxe/errfile.h
@@ -297,6 +297,7 @@ FILE_LICENCE ( GPL2_OR_LATER );
 #define ERRFILE_efi_reboot	      ( ERRFILE_OTHER | 0x003e0000 )
 #define ERRFILE_memmap_settings	      ( ERRFILE_OTHER | 0x003f0000 )
 #define ERRFILE_param_cmd	      ( ERRFILE_OTHER | 0x00400000 )
+#define ERRFILE_deflate		      ( ERRFILE_OTHER | 0x00410000 )
 
 /** @} */
 
diff --git a/src/tests/deflate_test.c b/src/tests/deflate_test.c
new file mode 100644
index 0000000..1223492
--- /dev/null
+++ b/src/tests/deflate_test.c
@@ -0,0 +1,239 @@
+/*
+ * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or any later version.
+ *
+ * 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.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ * 02110-1301, USA.
+ */
+
+FILE_LICENCE ( GPL2_OR_LATER );
+
+/** @file
+ *
+ * DEFLATE tests
+ *
+ */
+
+/* Forcibly enable assertions */
+#undef NDEBUG
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ipxe/deflate.h>
+#include <ipxe/test.h>
+
+/** A DEFLATE test */
+struct deflate_test {
+	/** Compression format */
+	enum deflate_format format;
+	/** Compressed data */
+	const void *compressed;
+	/** Length of compressed data */
+	size_t compressed_len;
+	/** Expected uncompressed data */
+	const void *expected;
+	/** Length of expected uncompressed data */
+	size_t expected_len;
+};
+
+/** A DEFLATE fragment list */
+struct deflate_test_fragments {
+	/** Fragment lengths */
+	size_t len[8];
+};
+
+/** Define inline data */
+#define DATA(...) { __VA_ARGS__ }
+
+/** Define a DEFLATE test */
+#define DEFLATE( name, FORMAT, COMPRESSED, EXPECTED )			\
+	static const uint8_t name ## _compressed[] = COMPRESSED;	\
+	static const uint8_t name ## _expected[] = EXPECTED;		\
+	static struct deflate_test name = {				\
+		.format = FORMAT,					\
+		.compressed = name ## _compressed,			\
+		.compressed_len = sizeof ( name ## _compressed ),	\
+		.expected = name ## _expected,				\
+		.expected_len = sizeof ( name ## _expected ),		\
+	};
+
+/* Empty file, no compression */
+DEFLATE ( empty_literal, DEFLATE_RAW,
+	  DATA ( 0x01, 0x00, 0x00, 0xff, 0xff ), DATA() );
+
+/* "iPXE" string, no compression */
+DEFLATE ( literal, DEFLATE_RAW,
+	  DATA ( 0x01, 0x04, 0x00, 0xfb, 0xff, 0x69, 0x50, 0x58, 0x45 ),
+	  DATA ( 0x69, 0x50, 0x58, 0x45 ) );
+
+/* Empty file */
+DEFLATE ( empty, DEFLATE_RAW, DATA ( 0x03, 0x00 ), DATA() );
+
+/* "Hello world" */
+DEFLATE ( hello_world, DEFLATE_RAW,
+	  DATA ( 0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0x28, 0xcf, 0x2f, 0xca,
+		 0x49, 0x01, 0x00 ),
+	  DATA ( 0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 0x77, 0x6f, 0x72, 0x6c,
+		 0x64 ) );
+
+/* "Hello hello world" */
+DEFLATE ( hello_hello_world, DEFLATE_RAW,
+	  DATA ( 0xf3, 0x48, 0xcd, 0xc9, 0xc9, 0x57, 0xc8, 0x00, 0x93, 0xe5,
+		 0xf9, 0x45, 0x39, 0x29, 0x00 ),
+	  DATA ( 0x48, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 0x68, 0x65, 0x6c, 0x6c,
+		 0x6f, 0x20, 0x77, 0x6f, 0x72, 0x6c, 0x64 ) );
+
+/* "This specification defines a lossless compressed data format" */
+DEFLATE ( rfc_sentence, DEFLATE_RAW,
+	  DATA ( 0x0d, 0xc6, 0xdb, 0x09, 0x00, 0x21, 0x0c, 0x04, 0xc0, 0x56,
+		 0xb6, 0x28, 0x1b, 0x08, 0x79, 0x70, 0x01, 0x35, 0xe2, 0xa6,
+		 0x7f, 0xce, 0xf9, 0x9a, 0xf1, 0x25, 0xc1, 0xe3, 0x9a, 0x91,
+		 0x2a, 0x9d, 0xb5, 0x61, 0x1e, 0xb9, 0x9d, 0x10, 0xcc, 0x22,
+		 0xa7, 0x93, 0xd0, 0x5a, 0xe7, 0xbe, 0xb8, 0xc1, 0xa4, 0x05,
+		 0x51, 0x77, 0x49, 0xff ),
+	  DATA ( 0x54, 0x68, 0x69, 0x73, 0x20, 0x73, 0x70, 0x65, 0x63, 0x69,
+		 0x66, 0x69, 0x63, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x20, 0x64,
+		 0x65, 0x66, 0x69, 0x6e, 0x65, 0x73, 0x20, 0x61, 0x20, 0x6c,
+		 0x6f, 0x73, 0x73, 0x6c, 0x65, 0x73, 0x73, 0x20, 0x63, 0x6f,
+		 0x6d, 0x70, 0x72, 0x65, 0x73, 0x73, 0x65, 0x64, 0x20, 0x64,
+		 0x61, 0x74, 0x61, 0x20, 0x66, 0x6f, 0x72, 0x6d, 0x61, 0x74 ) );
+
+/* "ZLIB Compressed Data Format Specification" */
+DEFLATE ( zlib, DEFLATE_ZLIB,
+	  DATA ( 0x78, 0x01, 0x8b, 0xf2, 0xf1, 0x74, 0x52, 0x70, 0xce, 0xcf,
+		 0x2d, 0x28, 0x4a, 0x2d, 0x2e, 0x4e, 0x4d, 0x51, 0x70, 0x49,
+		 0x2c, 0x49, 0x54, 0x70, 0xcb, 0x2f, 0xca, 0x4d, 0x2c, 0x51,
+		 0x08, 0x2e, 0x48, 0x4d, 0xce, 0x4c, 0xcb, 0x4c, 0x4e, 0x2c,
+		 0xc9, 0xcc, 0xcf, 0x03, 0x00, 0x2c, 0x0e, 0x0e, 0xeb ),
+	  DATA ( 0x5a, 0x4c, 0x49, 0x42, 0x20, 0x43, 0x6f, 0x6d, 0x70, 0x72,
+		 0x65, 0x73, 0x73, 0x65, 0x64, 0x20, 0x44, 0x61, 0x74, 0x61,
+		 0x20, 0x46, 0x6f, 0x72, 0x6d, 0x61, 0x74, 0x20, 0x53, 0x70,
+		 0x65, 0x63, 0x69, 0x66, 0x69, 0x63, 0x61, 0x74, 0x69, 0x6f,
+		 0x6e ) );
+
+/* "ZLIB Compressed Data Format Specification" fragment list */
+static struct deflate_test_fragments zlib_fragments[] = {
+	{ { -1UL, } },
+	{ { 0, 1, 5, -1UL, } },
+	{ { 0, 0, 1, 0, 0, 1, -1UL } },
+	{ { 10, 8, 4, 7, 11, -1UL } },
+	{ { 45, -1UL } },
+	{ { 48, -1UL } },
+};
+
+/**
+ * Report DEFLATE test result
+ *
+ * @v deflate		Decompressor
+ * @v test		Deflate test
+ * @v frags		Fragment list, or NULL
+ * @v file		Test code file
+ * @v line		Test code line
+ */
+static void deflate_okx ( struct deflate *deflate,
+			  struct deflate_test *test,
+			  struct deflate_test_fragments *frags,
+			  const char *file, unsigned int line ) {
+	uint8_t data[ test->expected_len ];
+	struct deflate_chunk in;
+	struct deflate_chunk out;
+	size_t frag_len = -1UL;
+	size_t offset = 0;
+	size_t remaining = test->compressed_len;
+	unsigned int i;
+
+	/* Initialise decompressor */
+	deflate_init ( deflate, test->format );
+
+	/* Initialise output chunk */
+	deflate_chunk_init ( &out, virt_to_user ( data ), 0, sizeof ( data ) );
+
+	/* Process input (in fragments, if applicable) */
+	for ( i = 0 ; i < ( sizeof ( frags->len ) /
+			    sizeof ( frags->len[0] ) ) ; i++ ) {
+
+		/* Initialise input chunk */
+		if ( frags )
+			frag_len = frags->len[i];
+		if ( frag_len > remaining )
+			frag_len = remaining;
+		deflate_chunk_init ( &in, virt_to_user ( test->compressed ),
+				     offset, ( offset + frag_len ) );
+
+		/* Decompress this fragment */
+		okx ( deflate_inflate ( deflate, &in, &out ) == 0, file, line );
+		okx ( in.len == ( offset + frag_len ), file, line );
+		okx ( in.offset == in.len, file, line );
+
+		/* Move to next fragment */
+		offset = in.offset;
+		remaining -= frag_len;
+		if ( ! remaining )
+			break;
+
+		/* Check that decompression has not terminated early */
+		okx ( ! deflate_finished ( deflate ), file, line );
+	}
+
+	/* Check decompression has terminated as expected */
+	okx ( deflate_finished ( deflate ), file, line );
+	okx ( offset == test->compressed_len, file, line );
+	okx ( out.offset == test->expected_len, file, line );
+	okx ( memcmp ( data, test->expected, test->expected_len ) == 0,
+	     file, line );
+}
+#define deflate_ok( deflate, test, frags ) \
+	deflate_okx ( deflate, test, frags, __FILE__, __LINE__ )
+
+/**
+ * Perform DEFLATE self-test
+ *
+ */
+static void deflate_test_exec ( void ) {
+	struct deflate *deflate;
+	unsigned int i;
+
+	/* Allocate shared structure */
+	deflate = malloc ( sizeof ( *deflate ) );
+	ok ( deflate != NULL );
+
+	/* Perform self-tests */
+	if ( deflate ) {
+
+		/* Test as a single pass */
+		deflate_ok ( deflate, &empty_literal, NULL );
+		deflate_ok ( deflate, &literal, NULL );
+		deflate_ok ( deflate, &empty, NULL );
+		deflate_ok ( deflate, &hello_world, NULL );
+		deflate_ok ( deflate, &hello_hello_world, NULL );
+		deflate_ok ( deflate, &rfc_sentence, NULL );
+		deflate_ok ( deflate, &zlib, NULL );
+
+		/* Test fragmentation */
+		for ( i = 0 ; i < ( sizeof ( zlib_fragments ) /
+				    sizeof ( zlib_fragments[0] ) ) ; i++ ) {
+			deflate_ok ( deflate, &zlib, &zlib_fragments[i] );
+		}
+	}
+
+	/* Free shared structure */
+	free ( deflate );
+}
+
+/** DEFLATE self-test */
+struct self_test deflate_test __self_test = {
+	.name = "deflate",
+	.exec = deflate_test_exec,
+};
diff --git a/src/tests/tests.c b/src/tests/tests.c
index 6224a3d..3169da2 100644
--- a/src/tests/tests.c
+++ b/src/tests/tests.c
@@ -50,3 +50,4 @@ REQUIRE_OBJECT ( x509_test );
 REQUIRE_OBJECT ( ocsp_test );
 REQUIRE_OBJECT ( cms_test );
 REQUIRE_OBJECT ( pnm_test );
+REQUIRE_OBJECT ( deflate_test );