Menu
▾
▴
CVS: blob/src/lib mini_inflate.c,NONE,1.1 Makefile.am,1.12,1.13
|
From: Erik M. <er...@us...> - 2002-02-17 15:41:57
|
Update of /cvsroot/blob/blob/src/lib
In directory usw-pr-cvs1:/tmp/cvs-serv889/src/lib
Modified Files:
Makefile.am
Added Files:
mini_inflate.c
Log Message:
- cleanup configure.in and Makefile.am
- make uudecode and xmodem conditionally compiled sources
- make cramfs and jffs2 really conditionally compiled
- move mini_inflate to libblob
--- NEW FILE: mini_inflate.c ---
/*-------------------------------------------------------------------------
* Filename: mini_inflate.c
* Version: $Id: mini_inflate.c,v 1.1 2002/02/17 15:41:54 erikm Exp $
* Copyright: Copyright (C) 2001, Russ Dill
* Author: Russ Dill <Rus...@as...>
* Description: Mini inflate implementation (RFC 1951)
*-----------------------------------------------------------------------*/
/*
*
* 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
* (at your option) 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#ident "$Id: mini_inflate.c,v 1.1 2002/02/17 15:41:54 erikm Exp $"
#ifdef HAVE_CONFIG_H
# include <blob/config.h>
#endif
#include <blob/mini_inflate.h>
#include <blob/util.h>
#define NO_ERROR 0
#define COMP_UNKNOWN 1 /* The specififed bytype is invalid */
#define CODE_NOT_FOUND 2 /* a huffman code in the stream could not be decoded */
#define TOO_MANY_BITS 3 /* pull_bits was passed an argument that is too
* large */
/* This struct represents an entire huffman code set. It has various lookup
* tables to speed decoding */
struct huffman_set {
int bits; /* maximum bit length */
int num_symbols; /* Number of symbols this code can represent */
int *lengths; /* The bit length of symbols */
int *symbols; /* All of the symbols, sorted by the huffman code */
int *count; /* the number of codes of this bit length */
int *first; /* the first code of this bit length */
int *pos; /* the symbol that first represents (in the symbols
* array) */
};
struct bitstream {
unsigned char *data; /* increments as we move from byte to byte */
unsigned char bit; /* 0 to 7 */
unsigned long decoded; /* The number of bytes decoded */
int error;
int distance_count[16];
int distance_first[16];
int distance_pos[16];
int distance_lengths[32];
int distance_symbols[32];
int code_count[8];
int code_first[8];
int code_pos[8];
int code_lengths[19];
int code_symbols[19];
int length_count[16];
int length_first[16];
int length_pos[16];
int length_lengths[288];
int length_symbols[288];
struct huffman_set codes;
struct huffman_set lengths;
struct huffman_set distance;
};
#define NO_COMP 0
#define FIXED_COMP 1
#define DYNAMIC_COMP 2
/* The order that the code lengths in section 3.2.7 are in */
static unsigned char huffman_order[] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
11, 4, 12, 3, 13, 2, 14, 1, 15};
/* associate a stream with a block of data and reset the stream */
static void init_stream(struct bitstream *stream, unsigned char *data)
{
stream->error = NO_ERROR;
stream->decoded = 0;
stream->data = data;
stream->bit = 0; /* The first bit of the stream is the lsb of the
* first byte */
/* really sorry about all this initialization, think of a better way,
* let me know and it will get cleaned up */
stream->codes.bits = 8;
stream->codes.num_symbols = 19;
stream->codes.lengths = stream->code_lengths;
stream->codes.symbols = stream->code_symbols;
stream->codes.count = stream->code_count;
stream->codes.first = stream->code_first;
stream->codes.pos = stream->code_pos;
stream->lengths.bits = 16;
stream->lengths.num_symbols = 288;
stream->lengths.lengths = stream->length_lengths;
stream->lengths.symbols = stream->length_symbols;
stream->lengths.count = stream->length_count;
stream->lengths.first = stream->length_first;
stream->lengths.pos = stream->length_pos;
stream->distance.bits = 16;
stream->distance.num_symbols = 32;
stream->distance.lengths = stream->distance_lengths;
stream->distance.symbols = stream->distance_symbols;
stream->distance.count = stream->distance_count;
stream->distance.first = stream->distance_first;
stream->distance.pos = stream->distance_pos;
}
/* pull 'bits' bits out of the stream. The last bit pulled it returned as the
* msb. (section 3.1.1)
*/
static unsigned long pull_bits(struct bitstream *stream,
const unsigned int bits)
{
unsigned long ret;
int i;
ret = 0;
for (i = 0; i < bits; i++) {
ret += ((*(stream->data) >> stream->bit) & 1) << i;
/* if, before incrementing, we are on bit 7,
* go to the lsb of the next byte */
if (stream->bit++ == 7) {
stream->bit = 0;
stream->data++;
}
}
return ret;
}
static int pull_bit(struct bitstream *stream)
{
int ret = ((*(stream->data) >> stream->bit) & 1);
if (stream->bit++ == 7) {
stream->bit = 0;
stream->data++;
}
return ret;
}
/* discard bits up to the next whole byte */
static void discard_bits(struct bitstream *stream)
{
if (stream->bit != 0) {
stream->bit = 0;
stream->data++;
}
}
/* No decompression, the data is all literals (section 3.2.4) */
static void decompress_none(struct bitstream *stream, unsigned char *dest)
{
unsigned int length;
discard_bits(stream);
length = *(stream->data++);
length += *(stream->data++) << 8;
pull_bits(stream, 16); /* throw away the inverse of the size */
stream->decoded += length;
memcpy(dest, stream->data, length);
stream->data += length;
}
/* Read in a symbol from the stream (section 3.2.2) */
static int read_symbol(struct bitstream *stream, struct huffman_set *set)
{
int bits = 0;
int code = 0;
while (!(set->count[bits] && code < set->first[bits] +
set->count[bits])) {
code = (code << 1) + pull_bit(stream);
if (++bits > set->bits) {
/* error decoding (corrupted data?) */
stream->error = CODE_NOT_FOUND;
return -1;
}
}
return set->symbols[set->pos[bits] + code - set->first[bits]];
}
/* decompress a stream of data encoded with the passed length and distance
* huffman codes */
static void decompress_huffman(struct bitstream *stream, unsigned char *dest)
{
struct huffman_set *lengths = &(stream->lengths);
struct huffman_set *distance = &(stream->distance);
int symbol, length, dist, i;
do {
if ((symbol = read_symbol(stream, lengths)) < 0) return;
if (symbol < 256) {
*(dest++) = symbol; /* symbol is a literal */
stream->decoded++;
} else if (symbol > 256) {
/* Determine the length of the repitition
* (section 3.2.5) */
if (symbol < 265) length = symbol - 254;
else if (symbol == 285) length = 258;
else {
length = pull_bits(stream, (symbol - 261) >> 2);
length += (4 << ((symbol - 261) >> 2)) + 3;
length += ((symbol - 1) % 4) <<
((symbol - 261) >> 2);
}
/* Determine how far back to go */
if ((symbol = read_symbol(stream, distance)) < 0)
return;
if (symbol < 4) dist = symbol + 1;
else {
dist = pull_bits(stream, (symbol - 2) >> 1);
dist += (2 << ((symbol - 2) >> 1)) + 1;
dist += (symbol % 2) << ((symbol - 2) >> 1);
}
stream->decoded += length;
for (i = 0; i < length; i++) *(dest++) = dest[-dist];
}
} while (symbol != 256); /* 256 is the end of the data block */
}
/* Fill the lookup tables (section 3.2.2) */
static void fill_code_tables(struct huffman_set *set)
{
int code = 0, i, length;
/* fill in the first code of each bit length, and the pos pointer */
set->pos[0] = 0;
for (i = 1; i < set->bits; i++) {
code = (code + set->count[i - 1]) << 1;
set->first[i] = code;
set->pos[i] = set->pos[i - 1] + set->count[i - 1];
}
/* Fill in the table of symbols in order of their huffman code */
for (i = 0; i < set->num_symbols; i++) {
if ((length = set->lengths[i]))
set->symbols[set->pos[length]++] = i;
}
/* reset the pos pointer */
for (i = 1; i < set->bits; i++) set->pos[i] -= set->count[i];
}
static void init_code_tables(struct huffman_set *set)
{
memset(set->lengths, 0, set->num_symbols);
memset(set->count, 0, set->bits);
memset(set->first, 0, set->bits);
}
/* read in the huffman codes for dynamic decoding (section 3.2.7) */
static void decompress_dynamic(struct bitstream *stream, unsigned char *dest)
{
/* I tried my best to minimize the memory footprint here, while still
* keeping up performance. I really dislike the _lengths[] tables, but
* I see no way of eliminating them without a sizable performance
* impact. The first struct table keeps track of stats on each bit
* length. The _length table keeps a record of the bit length of each
* symbol. The _symbols table is for looking up symbols by the huffman
* code (the pos element points to the first place in the symbol table
* where that bit length occurs). I also hate the initization of these
* structs, if someone knows how to compact these, lemme know. */
struct huffman_set *codes = &(stream->codes);
struct huffman_set *lengths = &(stream->lengths);
struct huffman_set *distance = &(stream->distance);
int hlit = pull_bits(stream, 5) + 257;
int hdist = pull_bits(stream, 5) + 1;
int hclen = pull_bits(stream, 4) + 4;
int length, curr_code, symbol, i, last_code;
last_code = 0;
init_code_tables(codes);
init_code_tables(lengths);
init_code_tables(distance);
/* fill in the count of each bit length' as well as the lengths
* table */
for (i = 0; i < hclen; i++) {
length = pull_bits(stream, 3);
codes->lengths[huffman_order[i]] = length;
if (length) codes->count[length]++;
}
fill_code_tables(codes);
/* Do the same for the length codes, being carefull of wrap through
* to the distance table */
curr_code = 0;
while (curr_code < hlit) {
if ((symbol = read_symbol(stream, codes)) < 0) return;
if (symbol == 0) {
curr_code++;
last_code = 0;
} else if (symbol < 16) { /* Literal length */
lengths->lengths[curr_code] = last_code = symbol;
lengths->count[symbol]++;
curr_code++;
} else if (symbol == 16) { /* repeat the last symbol 3 - 6
* times */
length = 3 + pull_bits(stream, 2);
for (;length; length--, curr_code++)
if (curr_code < hlit) {
lengths->lengths[curr_code] =
last_code;
lengths->count[last_code]++;
} else { /* wrap to the distance table */
distance->lengths[curr_code - hlit] =
last_code;
distance->count[last_code]++;
}
} else if (symbol == 17) { /* repeat a bit length 0 */
curr_code += 3 + pull_bits(stream, 3);
last_code = 0;
} else { /* same, but more times */
curr_code += 11 + pull_bits(stream, 7);
last_code = 0;
}
}
fill_code_tables(lengths);
/* Fill the distance table, don't need to worry about wrapthrough
* here */
curr_code -= hlit;
while (curr_code < hdist) {
if ((symbol = read_symbol(stream, codes)) < 0) return;
if (symbol == 0) {
curr_code++;
last_code = 0;
} else if (symbol < 16) {
distance->lengths[curr_code] = last_code = symbol;
distance->count[symbol]++;
curr_code++;
} else if (symbol == 16) {
length = 3 + pull_bits(stream, 2);
for (;length; length--, curr_code++) {
distance->lengths[curr_code] =
last_code;
distance->count[last_code]++;
}
} else if (symbol == 17) {
curr_code += 3 + pull_bits(stream, 3);
last_code = 0;
} else {
curr_code += 11 + pull_bits(stream, 7);
last_code = 0;
}
}
fill_code_tables(distance);
decompress_huffman(stream, dest);
}
/* fill in the length and distance huffman codes for fixed encoding
* (section 3.2.6) */
static void decompress_fixed(struct bitstream *stream, unsigned char *dest)
{
/* let gcc fill in the initial values */
struct huffman_set *lengths = &(stream->lengths);
struct huffman_set *distance = &(stream->distance);
memset(lengths->count, 0, 16);
memset(lengths->first, 0, 16);
memset(lengths->lengths, 8, 144);
memset(lengths->lengths + 144, 9, 112);
memset(lengths->lengths + 256, 7, 24);
memset(lengths->lengths + 280, 8, 8);
lengths->count[7] = 24;
lengths->count[8] = 152;
lengths->count[9] = 112;
memset(distance->count, 0, 16);
memset(distance->first, 0, 16);
memset(distance->lengths, 5, 32);
distance->count[5] = 32;
fill_code_tables(lengths);
fill_code_tables(distance);
decompress_huffman(stream, dest);
}
/* returns the number of bytes decoded, < 0 if there was an error. Note that
* this function assumes that the block starts on a byte boundry
* (non-compliant, but I don't see where this would happen). section 3.2.3 */
long decompress_block(unsigned char *dest, unsigned char *source)
{
int bfinal, btype;
struct bitstream stream;
init_stream(&stream, source);
do {
bfinal = pull_bit(&stream);
btype = pull_bits(&stream, 2);
if (btype == NO_COMP) decompress_none(&stream, dest + stream.decoded);
else if (btype == DYNAMIC_COMP)
decompress_dynamic(&stream, dest + stream.decoded);
else if (btype == FIXED_COMP) decompress_fixed(&stream, dest + stream.decoded);
else stream.error = COMP_UNKNOWN;
} while (!bfinal && !stream.error);
return stream.error ? -stream.error : stream.decoded;
}
Index: Makefile.am
===================================================================
RCS file: /cvsroot/blob/blob/src/lib/Makefile.am,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -d -r1.12 -r1.13
--- Makefile.am 15 Feb 2002 23:08:20 -0000 1.12
+++ Makefile.am 17 Feb 2002 15:41:54 -0000 1.13
@@ -36,6 +36,7 @@
md5support.c \
memcpy.c \
memset.c \
+ mini_inflate.c \
printf.c \
reboot.c \
serial.c \
|
