public inbox for linux-kernel@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH 0/20] inflate: refactor boot-time inflate code
@ 2005-12-22 18:26 Matt Mackall
  2005-12-22 18:26 ` [PATCH 1/20] inflate: lindent and manual formatting changes Matt Mackall
  2006-01-05  3:50 ` [PATCH 0/20] inflate: refactor boot-time inflate code Andrew Morton
  0 siblings, 2 replies; 24+ messages in thread
From: Matt Mackall @ 2005-12-22 18:26 UTC (permalink / raw)
  To: Andrew Morton; +Cc: linux-kernel, linux-arch, linux-tiny

This is a refactored version of the lib/inflate.c:

- clean up some really ugly code
- clean up atrocities like '#include "../../../lib/inflate.c"'
- drop a ton of cut and paste code from the kernel boot
- move towards making the boot decompressor pluggable
- move towards unifying the multiple inflate implementations
- save space

Recent changes include:

- use proper pointer types for minimal malloc arena
- fix up static const usage to make ARM happy
- fix compile with CONFIG_MODVERSIONS

This touches 11 architectures, which makes things slightly
interesting. Rather than break the patches out by arch, I've gone the
route of making a number of small incremental changes that sweep
across the tree. Patches that touch the per-arch code are marked
"(arch)".

I've been primarily testing this on x86, but various versions of this
code have gotten testing on a variety of architectures as part of my
linux-tiny tree.

(This work was sponsored in part by the CE Linux Forum.)

^ permalink raw reply	[flat|nested] 24+ messages in thread
* [PATCH 6/20] inflate: internalize CRC calculation, cleanup table calculation
@ 2005-10-31 20:54 Matt Mackall
  2005-10-31 20:54 ` [PATCH 7/20] inflate: eliminate memzero usage Matt Mackall
  0 siblings, 1 reply; 24+ messages in thread
From: Matt Mackall @ 2005-10-31 20:54 UTC (permalink / raw)
  To: Andrew Morton, linux-kernel; +Cc: linux-arch

inflate: cleanup CRC calculation

Move CRC calculation into inflate code
Cleanup table calculation code

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: 2.6.14/lib/inflate.c
===================================================================
--- 2.6.14.orig/lib/inflate.c	2005-10-28 22:01:17.000000000 -0700
+++ 2.6.14/lib/inflate.c	2005-10-28 22:01:18.000000000 -0700
@@ -109,6 +109,10 @@
 
 #include <asm/types.h>
 
+static u32 crc_32_tab[256];
+static u32 crc;		/* dummy var until users get cleaned up */
+#define CRCPOLY_LE 0xedb88320
+
 /* Huffman code lookup table entry--this entry is four bytes for machines
    that have 16-bit pointers (e.g. PC's in the small or medium model).
    Valid extra bits are 0..13.  e == 15 is EOB (end of block), e == 16
@@ -128,7 +132,7 @@ struct huft {
 struct iostate {
 	u8 *window;
 	int opos, osize, bits;
-	u32 buf;
+	u32 buf, crc;
 };
 
 /* Function prototypes */
@@ -154,6 +158,12 @@ static int INIT inflate(struct iostate *
 
 static void flush_output(struct iostate *io)
 {
+	int i;
+
+	for (i = 0; i < io->opos; i++)
+		io->crc = crc_32_tab[(io->window[i] ^ (int)io->crc) & 0xff]
+			^ (io->crc >> 8);
+
 	outcnt = io->opos;
 	flush_window();
 	io->opos = 0;
@@ -906,47 +916,16 @@ static int INIT inflate(struct iostate *
  *
  **********************************************************************/
 
-static u32 crc_32_tab[256];
-static u32 crc;		/* initialized in makecrc() so it'll reside in bss */
-#define CRC_VALUE (crc ^ 0xffffffffUL)
-
-/*
- * Code to compute the CRC-32 table. Borrowed from
- * gzip-1.0.3/makecrc.c.
- * Not copyrighted 1990 Mark Adler
- */
-
 static void INIT makecrc(void)
 {
+	unsigned i, j;
+	u32 c = 1;
 
-	unsigned long c;	/* crc shift register */
-	unsigned long e;	/* polynomial exclusive-or pattern */
-	int i;			/* counter for all possible eight bit values */
-	int k;			/* byte being shifted into crc apparatus */
-
-	/* terms of polynomial defining this crc (except x^32): */
-	static const int p[] =
-	    { 0, 1, 2, 4, 5, 7, 8, 10, 11, 12, 16, 22, 23, 26 };
-
-	/* Make exclusive-or pattern from polynomial */
-	e = 0;
-	for (i = 0; i < sizeof(p) / sizeof(int); i++)
-		e |= 1L << (31 - p[i]);
-
-	crc_32_tab[0] = 0;
-
-	for (i = 1; i < 256; i++) {
-		c = 0;
-		for (k = i | 256; k != 1; k >>= 1) {
-			c = c & 1 ? (c >> 1) ^ e : c >> 1;
-			if (k & 1)
-				c ^= e;
-		}
-		crc_32_tab[i] = c;
+	for (i = 128; i; i >>= 1) {
+		c = (c >> 1) ^ ((c & 1) ? CRCPOLY_LE : 0);
+		for (j = 0; j < 256; j += 2 * i)
+			crc_32_tab[i + j] = c ^ crc_32_tab[j];
 	}
-
-	/* this is initialized here so this code could reside in ROM */
-	crc = 0xffffffffUL;	/* shift register contents */
 }
 
 /* gzip flag byte */
@@ -966,14 +945,15 @@ static int INIT gunzip(void)
 	u8 flags;
 	unsigned char magic[2];	/* magic header */
 	char method;
-	u32 orig_crc = 0;	/* original crc */
-	u32 orig_len = 0;	/* original uncompressed length */
+	u32 orig_crc;
+	u32 orig_len;
 	int res;
 	struct iostate io;
 
 	io.window = window;
 	io.osize = WSIZE;
 	io.opos = io.bits = io.buf = 0;
+	io.crc = 0xffffffffUL;
 
 	magic[0] = get_byte();
 	magic[1] = get_byte();
@@ -1051,8 +1031,7 @@ static int INIT gunzip(void)
 		return -1;
 	}
 
-	/* Get the crc and original length */
-	/* crc32  (see algorithm.doc)
+	/* Get the crc and original length
 	 * uncompressed input size modulo 2^32
 	 */
 	orig_crc = (u32)get_byte();
@@ -1066,7 +1045,7 @@ static int INIT gunzip(void)
 	orig_len |= (u32)get_byte() << 24;
 
 	/* Validate decompression */
-	if (orig_crc != CRC_VALUE) {
+	if (orig_crc != ~io.crc) {
 		error("crc error");
 		return -1;
 	}

^ permalink raw reply	[flat|nested] 24+ messages in thread

end of thread, other threads:[~2006-01-05  5:15 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2005-12-22 18:26 [PATCH 0/20] inflate: refactor boot-time inflate code Matt Mackall
2005-12-22 18:26 ` [PATCH 1/20] inflate: lindent and manual formatting changes Matt Mackall
2005-12-22 18:26   ` [PATCH 2/20] inflate: kill legacy bits Matt Mackall
2005-12-22 18:26     ` [PATCH 3/20] inflate: clean up input logic Matt Mackall
2005-12-22 18:26       ` [PATCH 4/20] inflate: start moving globals into iostate Matt Mackall
2005-12-22 18:26         ` [PATCH 5/20] inflate: cleanup Huffman table code Matt Mackall
2005-12-22 18:26           ` [PATCH 6/20] inflate: internalize CRC calculation, cleanup table calculation Matt Mackall
2005-12-22 18:26             ` [PATCH 7/20] inflate: eliminate memzero usage Matt Mackall
2005-12-22 18:26               ` [PATCH 8/20] inflate: (arch) kill unneeded declarations Matt Mackall
2005-12-22 18:26                 ` [PATCH 9/20] inflate: (arch) refactor inflate malloc code Matt Mackall
2005-12-22 18:26                   ` [PATCH 10/20] inflate: (arch) kill external CRC calculation Matt Mackall
2005-12-22 18:26                     ` [PATCH 11/20] inflate: (arch) kill get_byte Matt Mackall
2005-12-22 18:26                       ` [PATCH 12/20] inflate: internalize (arch) most of the output window handling Matt Mackall
2005-12-22 18:26                         ` [PATCH 13/20] inflate: (arch) kill silly zlib typedefs Matt Mackall
2005-12-22 18:26                           ` [PATCH 14/20] inflate: (arch) use an error callback rather than a global Matt Mackall
2005-12-22 18:26                             ` [PATCH 15/20] inflate: (arch) tidy user declarations Matt Mackall
2005-12-22 18:26                               ` [PATCH 16/20] inflate: remove legacy DEBG macros Matt Mackall
2005-12-22 18:26                                 ` [PATCH 17/20] inflate: mark some arrays as initdata Matt Mackall
2005-12-22 18:27                                   ` [PATCH 18/20] inflate: minor const changes Matt Mackall
2005-12-22 18:27                                     ` [PATCH 19/20] inflate: (arch) use proper linking Matt Mackall
2005-12-22 18:27                                       ` [PATCH 20/20] inflate: make in-core inflate share common CRC Matt Mackall
2006-01-05  3:50 ` [PATCH 0/20] inflate: refactor boot-time inflate code Andrew Morton
2006-01-05  5:09   ` Matt Mackall
  -- strict thread matches above, loose matches on Subject: below --
2005-10-31 20:54 [PATCH 6/20] inflate: internalize CRC calculation, cleanup table calculation Matt Mackall
2005-10-31 20:54 ` [PATCH 7/20] inflate: eliminate memzero usage Matt Mackall

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox