[PATCH] Add unpack support for gzip(1)

[Xin LI <delphij@xxxxxxxxxxx>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi,

Here is the patch I have written for FreeBSD and ported to DragonFly,
tested on leaf.

Cheers,
- --
Xin LI <delphij@delphij.net>	http://www.delphij.net/
FreeBSD - The Power to Serve!
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.12 (FreeBSD)

iEYEARECAAYFAkpsDioACgkQi+vbBBjt66BBnACeKl7L281xOCbI/qhitCGrRVeG
cWsAn0ASbu0dAq4H+47muE3BMVrVZbTL
=jA3L
-----END PGP SIGNATURE-----

diff --git a/usr.bin/gzip/unpack.c b/usr.bin/gzip/unpack.c
new file mode 100644
index 0000000..aa14800
--- /dev/null
+++ b/usr.bin/gzip/unpack.c
@@ -0,0 +1,322 @@
+/*-
+ * Copyright (c) 2009 Xin LI <delphij@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+/* This file is #included by gzip.c */
+
+/*
+ * pack(1) file format:
+ *
+ * The first 7 bytes is the header:
+ *	00, 01 - Signature (US, RS), we already validated it earlier.
+ *	02..05 - Uncompressed size
+ *	    06 - Level for the huffman tree (<=24)
+ *
+ * pack(1) will then store symbols (leaf) nodes count in each huffman
+ * tree levels, each level would consume 1 byte (See [1]).
+ *
+ * After the symbol count table, there is the symbol table, storing
+ * symbols represented by coresponding leaf node.  EOB is not being
+ * explicitly transmitted (not necessary anyway) in the symbol table.
+ *
+ * Compressed data goes after the symbol table.
+ *
+ * NOTES
+ *
+ * [1] If we count EOB into the symbols, that would mean that we will
+ * have at most 256 symbols in the huffman tree.  pack(1) rejects empty
+ * file and files that just repeats one character, which means that we
+ * will have at least 2 symbols.  Therefore, pack(1) would reduce the
+ * last level symbol count by 2 which makes it a number in
+ * range [0..254], so all levels' symbol count would fit into 1 byte.
+ */
+
+#define	PACK_HEADER_LENGTH	7
+#define	HTREE_MAXLEVEL		24
+
+/*
+ * unpack descriptor
+ *
+ * Represent the huffman tree in a similiar way that pack(1) would
+ * store in a packed file.  We store all symbols in a linear table,
+ * and store pointers to each level's first symbol.  In addition to
+ * that, maintain two counts for each level: inner nodes count and
+ * leaf nodes count.
+ */
+typedef struct {
+	int		symbol_size;	/* Size of the symbol table */
+	int		treelevels;	/* Levels for the huffman tree */
+
+	int		*symbolsin;	/* Table of leaf symbols count in
+					   each level */
+	int		*inodesin;	/* Table of internal nodes count in
+					   each level */
+
+	char		*symbol;	/* The symbol table */
+	char		*symbol_eob;	/* Pointer to the EOB symbol */
+	char		**tree;		/* Decoding huffman tree (pointers to
+					   first symbol of each tree level */
+
+	off_t		uncompressed_size; /* Uncompressed size */
+	FILE		*fpIn;		/* Input stream */
+	FILE		*fpOut;		/* Output stream */
+} unpack_descriptor_t;
+
+/*
+ * Release resource allocated to an unpack descriptor.
+ *
+ * Caller is responsible to make sure that all of these pointers are
+ * initialized (in our case, they all point to valid memory block).
+ * We don't zero out pointers here because nobody else would ever
+ * reference the memory block without scrubing them.
+ */
+static void
+unpack_descriptor_fini(unpack_descriptor_t *unpackd)
+{
+
+	free(unpackd->symbolsin);
+	free(unpackd->inodesin);
+	free(unpackd->symbol);
+	free(unpackd->tree);
+
+	fclose(unpackd->fpIn);
+	fclose(unpackd->fpOut);
+}
+
+/*
+ * Recursively fill the internal node count table
+ */
+static void
+unpackd_fill_inodesin(const unpack_descriptor_t *unpackd, int level)
+{
+
+	/*
+	 * The internal nodes would be 1/2 of total internal nodes and
+	 * leaf nodes in the next level.  For the last level there
+	 * would be no internal node by defination.
+	 */
+	if (level < unpackd->treelevels) {
+		unpackd_fill_inodesin(unpackd, level + 1);
+		unpackd->inodesin[level] = (unpackd->inodesin[level + 1] +
+					  unpackd->symbolsin[level + 1]) / 2;
+	} else
+		unpackd->inodesin[level] = 0;
+}
+
+/*
+ * Update counter for accepted bytes
+ */
+static void
+accepted_bytes(off_t *bytes_in, off_t newbytes)
+{
+
+	if (bytes_in != NULL)
+		(*bytes_in) += newbytes;
+}
+
+/*
+ * Read file header and construct the tree.  Also, prepare the buffered I/O
+ * for decode rountine.
+ *
+ * Return value is uncompressed size.
+ */
+static void
+unpack_parse_header(int in, int out, char *pre, size_t prelen, off_t *bytes_in,
+    unpack_descriptor_t *unpackd)
+{
+	unsigned char hdr[PACK_HEADER_LENGTH];	/* buffer for header */
+	ssize_t bytesread;		/* Bytes read from the file */
+	int i, j, thisbyte;
+
+	/* Prepend the header buffer if we already read some data */
+	if (prelen != 0)
+		memcpy(hdr, pre, prelen);
+
+	/* Read in and fill the rest bytes of header */
+	bytesread = read(in, hdr + prelen, PACK_HEADER_LENGTH - prelen);
+	if (bytesread < 0)
+		maybe_err("Error reading pack header");
+
+	accepted_bytes(bytes_in, PACK_HEADER_LENGTH);
+
+	/* Obtain uncompressed length (bytes 2,3,4,5)*/
+	unpackd->uncompressed_size = 0;
+	for (i = 2; i <= 5; i++) {
+		unpackd->uncompressed_size <<= 8;
+		unpackd->uncompressed_size |= hdr[i];
+	}
+
+	/* Get the levels of the tree */
+	unpackd->treelevels = hdr[6];
+	if (unpackd->treelevels > HTREE_MAXLEVEL || unpackd->treelevels < 1)
+		maybe_errx("Huffman tree has insane levels");
+
+	/* Let libc take care for buffering from now on */
+	if ((unpackd->fpIn = fdopen(in, "r")) == NULL)
+		maybe_err("Can not fdopen() input stream");
+	if ((unpackd->fpOut = fdopen(out, "w")) == NULL)
+		maybe_err("Can not fdopen() output stream");
+
+	/* Allocate for the tables of bounds and the tree itself */
+	unpackd->inodesin =
+	    calloc(unpackd->treelevels, sizeof(*(unpackd->inodesin)));
+	unpackd->symbolsin =
+	    calloc(unpackd->treelevels, sizeof(*(unpackd->symbolsin)));
+	unpackd->tree =
+	    calloc(unpackd->treelevels, (sizeof (*(unpackd->tree))));
+	if (unpackd->inodesin == NULL || unpackd->symbolsin == NULL ||
+	    unpackd->tree == NULL)
+		maybe_err("calloc");
+
+	/* We count from 0 so adjust to match array upper bound */
+	unpackd->treelevels--;
+
+	/* Read the levels symbol count table and caculate total */
+	unpackd->symbol_size = 1;		/* EOB */
+	for (i = 0; i <= unpackd->treelevels; i++) {
+		if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
+			maybe_err("File appears to be truncated");
+		unpackd->symbolsin[i] = (unsigned char)thisbyte;
+		unpackd->symbol_size += unpackd->symbolsin[i];
+	}
+	accepted_bytes(bytes_in, unpackd->treelevels);
+	if (unpackd->symbol_size > 256)
+		maybe_errx("Bad symbol table");
+
+	/* Allocate for the symbol table, point symbol_eob at the beginning */
+	unpackd->symbol_eob = unpackd->symbol = calloc(1, unpackd->symbol_size);
+	if (unpackd->symbol == NULL)
+		maybe_err("calloc");
+
+	/*
+	 * Read in the symbol table, which contain [2, 256] symbols.
+	 * In order to fit the count in one byte, pack(1) would offset
+	 * it by reducing 2 from the actual number from the last level.
+	 *
+	 * We adjust the last level's symbol count by 1 here, because
+	 * the EOB symbol is not being transmitted explicitly.  Another
+	 * adjustment would be done later afterward.
+	 */
+	unpackd->symbolsin[unpackd->treelevels]++;
+	for (i = 0; i <= unpackd->treelevels; i++) {
+		unpackd->tree[i] = unpackd->symbol_eob;
+		for (j = 0; j < unpackd->symbolsin[i]; j++) {
+			if ((thisbyte = fgetc(unpackd->fpIn)) == EOF)
+				maybe_errx("Symbol table truncated");
+			*unpackd->symbol_eob++ = (char)thisbyte;
+		}
+		accepted_bytes(bytes_in, unpackd->symbolsin[i]);
+	}
+
+	/* Now, take account for the EOB symbol as well */
+	unpackd->symbolsin[unpackd->treelevels]++;
+
+	/*
+	 * The symbolsin table has been constructed now.
+	 * Caculate the internal nodes count table based on it.
+	 */
+	unpackd_fill_inodesin(unpackd, 0);
+}
+
+/*
+ * Decode huffman stream, based on the huffman tree.
+ */
+static void
+unpack_decode(const unpack_descriptor_t *unpackd, off_t *bytes_in)
+{
+	int thislevel, thiscode, thisbyte, inlevelindex;
+	int i;
+	off_t bytes_out = 0;
+	const char *thissymbol;	/* The symbol pointer decoded from stream */
+
+	/*
+	 * Decode huffman.  Fetch every bytes from the file, get it
+	 * into 'thiscode' bit-by-bit, then output the symbol we got
+	 * when one has been found.
+	 *
+	 * Assumption: sizeof(int) > ((max tree levels + 1) / 8).
+	 * bad things could happen if not.
+	 */
+	thislevel = 0;
+	thiscode = thisbyte = 0;
+
+	while ((thisbyte = fgetc(unpackd->fpIn)) != EOF) {
+		accepted_bytes(bytes_in, 1);
+
+		/*
+		 * Split one bit from thisbyte, from highest to lowest,
+		 * feed the bit into thiscode, until we got a symbol from
+		 * the tree.
+		 */
+		for (i = 7; i >= 0; i--) {
+			thiscode = (thiscode << 1) | ((thisbyte >> i) & 1);
+
+			/* Did we got a symbol? (referencing leaf node) */
+			if (thiscode >= unpackd->inodesin[thislevel]) {
+				inlevelindex =
+				    thiscode - unpackd->inodesin[thislevel];
+				if (inlevelindex > unpackd->symbolsin[thislevel])
+					maybe_errx("File corrupt");
+
+				thissymbol =
+				    &(unpackd->tree[thislevel][inlevelindex]);
+				if ((thissymbol == unpackd->symbol_eob) &&
+				    (bytes_out == unpackd->uncompressed_size))
+					goto finished;
+
+				fputc((*thissymbol), unpackd->fpOut);
+				bytes_out++;
+
+				/* Prepare for next input */
+				thislevel = 0; thiscode = 0;
+			} else {
+				thislevel++;
+				if (thislevel > unpackd->treelevels)
+					maybe_errx("File corrupt");
+			}
+		}
+	}
+
+finished:
+	if (bytes_out != unpackd->uncompressed_size)
+		maybe_errx("Premature EOF");
+}
+
+/* Handler for pack(1)'ed file */
+static off_t
+unpack(int in, int out, char *pre, size_t prelen, off_t *bytes_in)
+{
+	unpack_descriptor_t	unpackd;
+
+	unpack_parse_header(dup(in), dup(out), pre, prelen, bytes_in, &unpackd);
+	unpack_decode(&unpackd, bytes_in);
+	unpack_descriptor_fini(&unpackd);
+
+	/* If we reached here, the unpack was successful */
+	return (unpackd.uncompressed_size);
+}
+
diff --git a/usr.bin/gzip/gzip.c b/usr.bin/gzip/gzip.c
index 90c7368..70c10b4 100644
--- a/usr.bin/gzip/gzip.c
+++ b/usr.bin/gzip/gzip.c
@@ -76,6 +76,9 @@ enum filetype {
 #ifndef NO_COMPRESS_SUPPORT
 	FT_Z,
 #endif
+#ifndef NO_PACK_SUPPORT
+	FT_PACK,
+#endif
 	FT_LAST,
 	FT_UNKNOWN
 };
@@ -92,6 +95,10 @@ enum filetype {
 #define Z_MAGIC		"\037\235"
 #endif
 
+#ifndef NO_PACK_SUPPORT
+#define PACK_MAGIC	"\037\036"
+#endif
+
 #define GZ_SUFFIX	".gz"
 
 #define BUFLEN		(64 * 1024)
@@ -165,7 +172,7 @@ static	char	*infile;		/* name of file coming in */
 
 static	void	maybe_err(const char *fmt, ...)
     __attribute__((__format__(__printf__, 1, 2)));
-#ifndef NO_BZIP2_SUPPORT
+#if !defined(NO_BZIP2_SUPPORT) || !defined(NO_PACK_SUPPORT)
 static	void	maybe_errx(const char *fmt, ...)
     __attribute__((__format__(__printf__, 1, 2)));
 #endif
@@ -213,6 +220,10 @@ static	FILE 	*zdopen(int);
 static	off_t	zuncompress(FILE *, FILE *, char *, size_t, off_t *);
 #endif
 
+#ifndef NO_PACK_SUPPORT
+static	off_t	unpack(int, int, char *, size_t, off_t *);
+#endif
+
 int main(int, char *p[]);
 
 #ifdef SMALL
@@ -411,7 +422,7 @@ maybe_err(const char *fmt, ...)
 	exit(2);
 }
 
-#ifndef NO_BZIP2_SUPPORT
+#if !defined(NO_BZIP2_SUPPORT) || !defined(NO_PACK_SUPPORT)
 /* ... without an errno. */
 void
 maybe_errx(const char *fmt, ...)
@@ -1073,6 +1084,11 @@ file_gettype(u_char *buf)
 		return FT_Z;
 	else
 #endif
+#ifndef NO_PACK_SUPPORT
+	if (memcmp(buf, PACK_MAGIC, 2) == 0)
+		return FT_PACK;
+	else
+#endif
 		return FT_UNKNOWN;
 }
 
@@ -1427,6 +1443,17 @@ file_uncompress(char *file, char *outfile, size_t outsize)
 	} else
 #endif
 
+#ifndef NO_PACK_SUPPORT
+	if (method == FT_PACK) {
+		if (lflag) {
+			maybe_warnx("no -l with packed files");
+			goto lose;
+		}
+
+		size = unpack(fd, zfd, NULL, 0, NULL);
+	} else
+#endif
+
 #ifndef SMALL
 	if (method == FT_UNKNOWN) {
 		if (lflag) {
@@ -1620,6 +1647,12 @@ handle_stdin(void)
 		fclose(in);
 		break;
 #endif
+#ifndef NO_PACK_SUPPORT
+	case FT_PACK:
+		usize = unpack(STDIN_FILENO, STDOUT_FILENO,
+			       (char *)header1, sizeof header1, &gsize);
+		break;
+#endif
 	}
 
 #ifndef SMALL
@@ -1993,6 +2026,9 @@ display_version(void)
 #ifndef NO_COMPRESS_SUPPORT
 #include "zuncompress.c"
 #endif
+#ifndef NO_PACK_SUPPORT
+#include "unpack.c"
+#endif
 
 static ssize_t
 read_retry(int fd, void *buf, size_t sz)