[LinuxBIOS] r35 - in trunk/filo-0.5: . fs
svn at openbios.org
svn at openbios.org
Mon Sep 24 00:33:39 CEST 2007
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 at 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 at 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 at 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));
More information about the coreboot
mailing list