Author: stepan Date: 2007-09-24 00:33:38 +0200 (Mon, 24 Sep 2007) New Revision: 35
Added: trunk/filo-0.5/fs/fsys_cramfs.c trunk/filo-0.5/fs/mini_inflate.c trunk/filo-0.5/fs/mini_inflate.h Modified: trunk/filo-0.5/defconfig trunk/filo-0.5/fs/Makefile Log: Add CRAMFS support to FILO.
To enable this, replace the line #FSYS_CRAMFS = 1 with FSYS_CRAMFS = 1 in your Config file.
Modified: trunk/filo-0.5/defconfig =================================================================== --- trunk/filo-0.5/defconfig 2007-03-06 19:22:33 UTC (rev 34) +++ trunk/filo-0.5/defconfig 2007-09-23 22:33:38 UTC (rev 35) @@ -56,6 +56,7 @@ FSYS_REISERFS = 1 #FSYS_XFS = 1 FSYS_ISO9660 = 1 +#FSYS_CRAMFS = 1
# Support for boot disk image in bootable CD-ROM (El Torito) ELTORITO = 1
Modified: trunk/filo-0.5/fs/Makefile =================================================================== --- trunk/filo-0.5/fs/Makefile 2007-03-06 19:22:33 UTC (rev 34) +++ trunk/filo-0.5/fs/Makefile 2007-09-23 22:33:38 UTC (rev 35) @@ -10,5 +10,7 @@ OBJS-$(FSYS_REISERFS) += fsys_reiserfs.o OBJS-$(FSYS_XFS) += fsys_xfs.o OBJS-$(FSYS_ISO9660) += fsys_iso9660.o +OBJS-$(FSYS_CRAMFS) += fsys_cramfs.o +OBJS-$(FSYS_CRAMFS) += mini_inflate.o
include $(TOPDIR)/makerules
Added: trunk/filo-0.5/fs/fsys_cramfs.c =================================================================== --- trunk/filo-0.5/fs/fsys_cramfs.c (rev 0) +++ trunk/filo-0.5/fs/fsys_cramfs.c 2007-09-23 22:33:38 UTC (rev 35) @@ -0,0 +1,465 @@ +/* + * GRUB -- GRand Unified Bootloader + * Copyright (C) 2002 Russ Dill address@hidden + * + * 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., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +/* fsys_minix.c used as a skeleton, cramfs code in kernel used as + * documentation and some code */ + +#include "shared.h" +#include "filesys.h" +#include "mini_inflate.h" + +//#define DEBUG_CRAMFS + +#ifdef DEBUG_CRAMFS +# define debug_cramfs(str, args...) printf(str, ## args) +#else +# define debug_cramfs(str, args...) do {;} while(0) +#endif + +/* include/asm-i386/type.h */ +typedef __signed__ char s8; +typedef unsigned char u8; +typedef __signed__ short s16; +typedef unsigned short u16; +typedef __signed__ int s32; +typedef unsigned int u32; + + +#define BLOCK_SIZE SECTOR_SIZE + +#define CRAMFS_MAGIC 0x28cd3d45 /* some random number */ +#define CRAMFS_SIGNATURE "Compressed ROMFS" + +/* + * Reasonably terse representation of the inode data. + */ +struct cramfs_inode { + u32 mode:16, uid:16; + /* SIZE for device files is i_rdev */ + u32 size:24, gid:8; + /* NAMELEN is the length of the file name, divided by 4 and + rounded up. (cramfs doesn't support hard links.) */ + /* OFFSET: For symlinks and non-empty regular files, this + contains the offset (divided by 4) of the file data in + compressed form (starting with an array of block pointers; + see README). For non-empty directories it is the offset + (divided by 4) of the inode of the first file in that + directory. For anything else, offset is zero. */ + u32 namelen:6, offset:26; +}; + +/* + * Superblock information at the beginning of the FS. + */ +struct cramfs_super { + u32 magic; /* 0x28cd3d45 - random number */ + u32 size; /* Not used. mkcramfs currently + writes a constant 1<<16 here. */ + u32 flags; /* 0 */ + u32 future; /* 0 */ + u8 signature[16]; /* "Compressed ROMFS" */ + u8 fsid[16]; /* random number */ + u8 name[16]; /* user-defined name */ + struct cramfs_inode root; /* Root inode data */ +}; + +/* + * Valid values in super.flags. Currently we refuse to mount + * if (flags & ~CRAMFS_SUPPORTED_FLAGS). Maybe that should be + * changed to test super.future instead. + */ +#define CRAMFS_SUPPORTED_FLAGS (0xff) + +/* Uncompression interfaces to the underlying zlib */ +int cramfs_uncompress_block(void *dst, int dstlen, void *src, int srclen); +int cramfs_uncompress_init(void); +int cramfs_uncompress_exit(void); + +/* linux/stat.h */ +#define S_IFMT 00170000 +#define S_IFLNK 0120000 +#define S_IFREG 0100000 +#define S_IFDIR 0040000 +#define S_ISLNK(m) (((m) & S_IFMT) == S_IFLNK) +#define S_ISREG(m) (((m) & S_IFMT) == S_IFREG) +#define S_ISDIR(m) (((m) & S_IFMT) == S_IFDIR) + +#define PATH_MAX 1024 /* include/linux/limits.h */ +#define MAX_LINK_COUNT 5 /* number of symbolic links to follow */ + +#define NAMELEN_MAX (((1 << (6 + 1)) - 1) << 2) /* 252 */ + +#define CRAMFS_BLOCK (4096L) +#define CRAMFS_MAX_BLOCKS ((1 << 24) / CRAMFS_BLOCK) + +/* made up, these are pointers into FSYS_BUF */ +/* read once, always stays there: */ +struct cramfs_buf { + struct cramfs_super super; + struct cramfs_inode inode; + char name[NAMELEN_MAX + 1]; + u32 block_ptrs[CRAMFS_MAX_BLOCKS]; + char data[CRAMFS_BLOCK * 2]; + char temp[CRAMFS_BLOCK]; + /* menu.lst is read 1 byte at a time, try to aleviate * + * the performance problem */ + long cached_block; /* the uncompressed block in cramfs_buf->data */ + long decompressed_block; /* the decompressed block in cramfs_buf->temp */ + long decompressed_size; /* the size that is got decompressed to */ +}; + +static struct cramfs_buf *cramfs_buf; + +#define CRAMFS_ROOT_INO (sizeof(struct cramfs_super) - sizeof(struct cramfs_inode)) + +#ifndef STAGE1_5 +#define cramfs_memcmp grub_memcmp +#define cramfs_strlen grub_strlen +#else +int +cramfs_memcmp (const char *s1, const char *s2, int n) +{ + while (n) + { + if (*s1 < *s2) + return -1; + else if (*s1 > *s2) + return 1; + s1++; + s2++; + n--; + } + + return 0; +} + + +int +cramfs_strlen (const char *str) +{ + int len = 0; + + while (*str++) + len++; + + return len; +} + + +#endif +/* check filesystem types and read superblock into memory buffer */ +int +cramfs_mount(void) +{ + debug_cramfs("attempting to mount a cramfs\n"); + + cramfs_buf = (struct cramfs_buf *) FSYS_BUF; + if (part_length < sizeof(struct cramfs_super) / BLOCK_SIZE) { + debug_cramfs("partition too short\n"); + return 0; + } + + if (!devread(0, 0, sizeof(struct cramfs_super), (char *) &cramfs_buf->super)) { + debug_cramfs("cannot read superblock\n"); + return 0; + } + + if (cramfs_buf->super.magic != CRAMFS_MAGIC) { + debug_cramfs("magic does not match\n"); + return 0; + } + + if (cramfs_memcmp(CRAMFS_SIGNATURE, cramfs_buf->super.signature, 16)) { + debug_cramfs("signiture does not match\n"); + return 0; + } + + if (cramfs_buf->super.flags & ~CRAMFS_SUPPORTED_FLAGS) { + debug_cramfs("unsupported flags\n"); + return 0; + } + + if (!S_ISDIR(cramfs_buf->super.root.mode)) { + debug_cramfs("root is not a directory\n"); + return 0; + } + + debug_cramfs("cramfs mounted\n"); + return 1; +} + +/* read from INODE into BUF */ +int +cramfs_read (char *buf, int len) +{ + u32 start; + u32 end; + int nblocks; + int block; + int block_len; + int ret = 0; + long size = 0; + long devread_ret; + + nblocks = (cramfs_buf->inode.size - 1) / CRAMFS_BLOCK + 1; + block = filepos / CRAMFS_BLOCK; + + if (!devread(0, cramfs_buf->inode.offset << 2, nblocks << 2, (char *) &cramfs_buf->block_ptrs)) + return 0; + + if (block) + start = cramfs_buf->block_ptrs[block - 1]; + else start = (cramfs_buf->inode.offset + nblocks) << 2; + + debug_cramfs("reading a file of %d blocks starting at offset %d (block %d)\n", nblocks, start, block); + debug_cramfs("filepos is %d\n", filepos); + + while (block < nblocks && len > 0) { + end = cramfs_buf->block_ptrs[block]; + block_len = end - start; + + debug_cramfs("reading to %d bytes at block %d at offset %d, %d bytes...", + len, block, start, block_len); + if (cramfs_buf->cached_block != block) { + disk_read_func = disk_read_hook; + devread_ret = devread(0, start, block_len, cramfs_buf->data); + disk_read_func = NULL; + cramfs_buf->cached_block = block; + } else debug_cramfs("%d was cached...", block); + + if (!ret && (filepos % CRAMFS_BLOCK)) { + /* its the first read, and its not block aligned */ + debug_cramfs("doing a non-aligned decompression of block %d at offset %d\n", + block, filepos % CRAMFS_BLOCK); + if (cramfs_buf->decompressed_block != block) { + size = decompress_block(cramfs_buf->temp, 4096, cramfs_buf->data + 2); + cramfs_buf->decompressed_size = size; + cramfs_buf->decompressed_block = block; + } else size = cramfs_buf->decompressed_size; + size -= filepos % CRAMFS_BLOCK; + if (size > len) size = len; + if (size > 0) + memcpy(buf, cramfs_buf->temp + (filepos % CRAMFS_BLOCK), size); + } else { + /* just another full block read */ + size = decompress_block(buf, len, cramfs_buf->data + 2); + } + if (size < 0) { + debug_cramfs("error in decomp (error %d)\n", size); + cramfs_buf->cached_block = -1; + cramfs_buf->decompressed_block = -1; + return 0; + } + debug_cramfs("decomp`d %d bytes\n", size); + buf += size; + len -= size; + filepos += size; + ret += size; + + block++; + start = end; + } + + return ret; +} + +/* preconditions: cramfs_mount already executed, therefore supblk in buffer + known as SUPERBLOCK + returns: 0 if error, nonzero iff we were able to find the file successfully + postconditions: on a nonzero return, buffer known as INODE contains the + inode of the file we were trying to look up + side effects: none yet */ +int +cramfs_dir(char *dirname) +{ + int str_chk; /* used ot hold the results of a string + compare */ + + u32 current_ino; /* inode info for current_ino */ + u32 parent_ino; + + char linkbuf[PATH_MAX]; /* buffer for following sym-links */ + int link_count = 0; + + char *rest; + char ch; + + u32 dir_size; /* size of this directory */ + u32 off; /* offset of this directory */ + u32 loc; /* location within a directory */ + + int namelen; + + /* loop invariants: + current_ino = inode to lookup + dirname = pointer to filename component we are cur looking up within + the directory known pointed to by current_ino (if any) */ + +#ifdef DEBUG_CRAMFS + printf("\n"); +#endif + + current_ino = CRAMFS_ROOT_INO; + parent_ino = current_ino; + + for (;;) { + debug_cramfs("inode offset %d, dirname %s\n", current_ino, dirname); + + if (!devread(0, current_ino, sizeof(struct cramfs_inode), (char *) &cramfs_buf->inode)) + return 0; + + /* If we've got a symbolic link, then chase it. */ + if (S_ISLNK(cramfs_buf->inode.mode)) { + int len; + + if (++link_count > MAX_LINK_COUNT) { + errnum = ERR_SYMLINK_LOOP; + return 0; + } + debug_cramfs("S_ISLNK(%s)\n", dirname); + + /* Find out how long our remaining name is. */ + len = 0; + while (dirname[len] && !isspace(dirname[len])) + len++; + + /* Get the symlink size. */ + filemax = cramfs_buf->inode.size; + if (filemax + len > sizeof(linkbuf) - 2) { + errnum = ERR_FILELENGTH; + return 0; + } + + if (len) { + /* Copy the remaining name to the end of the symlink data. + Note that DIRNAME and LINKBUF may overlap! */ + memmove(linkbuf + filemax, dirname, len); + } + linkbuf[filemax + len] = '\0'; + + /* Read the necessary blocks, and reset the file pointer. */ + len = grub_read(linkbuf, filemax); + filepos = 0; + if (!len) + return 0; + + debug_cramfs("symlink=%s\n", linkbuf); + + dirname = linkbuf; + if (*dirname == '/') { + /* It's an absolute link, so look it up in root. */ + current_ino = CRAMFS_ROOT_INO; + parent_ino = current_ino; + } else { + /* Relative, so look it up in our parent directory. */ + current_ino = parent_ino; + } + + /* Try again using the new name. */ + continue; + } + + /* If end of filename, INODE points to the file's inode */ + if (!*dirname || isspace(*dirname)) { + if (!S_ISREG(cramfs_buf->inode.mode)) { + errnum = ERR_BAD_FILETYPE; + return 0; + } + filemax = cramfs_buf->inode.size; + debug_cramfs("file found, size %d\n", filemax); + cramfs_buf->cached_block = -1; + cramfs_buf->decompressed_block = -1; + return 1; + } + + /* else we have to traverse a directory */ + parent_ino = current_ino; + + /* skip over slashes */ + while (*dirname == '/') dirname++; + + /* if this isn't a directory of sufficient size to hold our file, + abort */ + if (!(cramfs_buf->inode.size) || !S_ISDIR(cramfs_buf->inode.mode)) { + errnum = ERR_BAD_FILETYPE; + return 0; + } + + /* skip to next slash or end of filename (space) */ + for (rest = dirname; (ch = *rest) && !isspace(ch) && ch != '/'; rest++); + + /* look through this directory and find the next filename component */ + /* invariant: rest points to slash after the next filename component */ + *rest = 0; + loc = 0; + off = cramfs_buf->inode.offset << 2; + dir_size = cramfs_buf->inode.size; + + do { + debug_cramfs("dirname=`%s', rest=`%s', loc=%d\n", dirname, rest, loc); + + /* if our location/byte offset into the directory exceeds the size, + give up */ + if (loc >= dir_size) { + if (print_possibilities < 0) { +#if 0 + putchar ('\n'); +#endif + } else { + errnum = ERR_FILE_NOT_FOUND; + *rest = ch; + } + return (print_possibilities < 0); + } + + current_ino = off + loc; + + /* read in this inode */ + if (!devread(0, current_ino, sizeof(struct cramfs_inode), (char *) &cramfs_buf->inode)) + return 0; + if (!devread(0, current_ino + sizeof(struct cramfs_inode), + cramfs_buf->inode.namelen << 2, cramfs_buf->name)) + return 0; + cramfs_buf->name[cramfs_buf->inode.namelen << 2] = '\0'; + namelen = cramfs_strlen(cramfs_buf->name); + + /* advance loc prematurely to next on-disk directory entry */ + loc += sizeof(struct cramfs_inode) + (cramfs_buf->inode.namelen << 2); + + debug_cramfs("directory entry index=%d\n", loc + off); + debug_cramfs("entry=%s\n", cramfs_buf->name); + + str_chk = substring(dirname, cramfs_buf->name); + +#ifndef STAGE1_5 + if (print_possibilities && ch != '/' + && (!*dirname || str_chk <= 0)) { + if (print_possibilities > 0) + print_possibilities = -print_possibilities; + print_a_completion(cramfs_buf->name); + } +# endif + + + } while (str_chk || (print_possibilities && ch != '/')); + + *(dirname = rest) = ch; + } + /* never get here */ +}
Added: trunk/filo-0.5/fs/mini_inflate.c =================================================================== --- trunk/filo-0.5/fs/mini_inflate.c (rev 0) +++ trunk/filo-0.5/fs/mini_inflate.c 2007-09-23 22:33:38 UTC (rev 35) @@ -0,0 +1,387 @@ +/*------------------------------------------------------------------------- + * Filename: mini_inflate.c + * Version: $Id: mini_inflate.c,v 1.2 2001/10/17 19:43:32 jamey Exp $ + * Copyright: Copyright (C) 2001, Russ Dill + * Author: Russ Dill Russ.Dill@asu.edu + * 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 + * + */ +#include "mini_inflate.h" + +/* 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}; + +inline void cramfs_memset(int *s, const int c, size n) +{ + n--; + for (;n > 0; n--) s[n] = c; + s[0] = c; +} + +/* associate a stream with a block of data and reset the stream */ +static void init_stream(struct bitstream *stream, unsigned char *data, + void *(*inflate_memcpy)(void *, void *, size)) +{ + stream->error = NO_ERROR; + stream->memcpy = inflate_memcpy; + 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) + */ +inline 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; +} + +inline 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; + stream->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) +{ + cramfs_memset(set->lengths, 0, set->num_symbols); + cramfs_memset(set->count, 0, set->bits); + cramfs_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); + + cramfs_memset(lengths->count, 0, 16); + cramfs_memset(lengths->first, 0, 16); + cramfs_memset(lengths->lengths, 8, 144); + cramfs_memset(lengths->lengths + 144, 9, 112); + cramfs_memset(lengths->lengths + 256, 7, 24); + cramfs_memset(lengths->lengths + 280, 8, 8); + lengths->count[7] = 24; + lengths->count[8] = 152; + lengths->count[9] = 112; + + cramfs_memset(distance->count, 0, 16); + cramfs_memset(distance->first, 0, 16); + cramfs_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, + void *(*inflate_memcpy)(void *, void *, size)) +{ + int bfinal, btype; + struct bitstream stream; + + init_stream(&stream, source, inflate_memcpy); + 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); + +#if 0 + putstr("decompress_block start\r\n"); + putLabeledWord("stream.error = ",stream.error); + putLabeledWord("stream.decoded = ",stream.decoded); + putLabeledWord("dest = ",dest); + putstr("decompress_block end\r\n"); +#endif + return stream.error ? -stream.error : stream.decoded; +} +
Added: trunk/filo-0.5/fs/mini_inflate.h =================================================================== --- trunk/filo-0.5/fs/mini_inflate.h (rev 0) +++ trunk/filo-0.5/fs/mini_inflate.h 2007-09-23 22:33:38 UTC (rev 35) @@ -0,0 +1,82 @@ +/*------------------------------------------------------------------------- + * Filename: mini_inflate.h + * Version: $Id: mini_inflate.h,v 1.1 2001/08/14 21:17:39 jamey Exp $ + * Copyright: Copyright (C) 2001, Russ Dill + * Author: Russ Dill Russ.Dill@asu.edu + * Description: Mini deflate implementation + *-----------------------------------------------------------------------*/ +/* + * + * 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 + * + */ + +typedef __SIZE_TYPE__ size; + +#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 */ + void *(*memcpy)(void *, void *, size); + 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 + +long decompress_block(unsigned char *dest, unsigned char *source, + void *(*inflate_memcpy)(void *dest, void *src, size n));