aboutsummaryrefslogtreecommitdiffstats
path: root/include/linux
diff options
context:
space:
mode:
authorRichard Purdie <rpurdie@rpsys.net>2006-06-22 17:47:34 -0400
committerLinus Torvalds <torvalds@g5.osdl.org>2006-06-22 18:05:58 -0400
commit4f3865fb57a04db7cca068fed1c15badc064a302 (patch)
tree4c923c72b6ac9b633c87cc73b55a75c7cfd0f044 /include/linux
parent4f1bcaf094ccc512c23e10104c05a6f8e5b7a9e4 (diff)
[PATCH] zlib_inflate: Upgrade library code to a recent version
Upgrade the zlib_inflate implementation in the kernel from a patched version 1.1.3/4 to a patched 1.2.3. The code in the kernel is about seven years old and I noticed that the external zlib library's inflate performance was significantly faster (~50%) than the code in the kernel on ARM (and faster again on x86_32). For comparison the newer deflate code is 20% slower on ARM and 50% slower on x86_32 but gives an approx 1% compression ratio improvement. I don't consider this to be an improvement for kernel use so have no plans to change the zlib_deflate code. Various changes have been made to the zlib code in the kernel, the most significant being the extra functions/flush option used by ppp_deflate. This update reimplements the features PPP needs to ensure it continues to work. This code has been tested on ARM under both JFFS2 (with zlib compression enabled) and ppp_deflate and on x86_32. JFFS2 sees an approx. 10% real world file read speed improvement. This patch also removes ZLIB_VERSION as it no longer has a correct value. We don't need version checks anyway as the kernel's module handling will take care of that for us. This removal is also more in keeping with the zlib author's wishes (http://www.zlib.net/zlib_faq.html#faq24) and I've added something to the zlib.h header to note its a modified version. Signed-off-by: Richard Purdie <rpurdie@rpsys.net> Acked-by: Joern Engel <joern@wh.fh-wedel.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'include/linux')
-rw-r--r--include/linux/zconf.h12
-rw-r--r--include/linux/zlib.h209
-rw-r--r--include/linux/zutil.h12
3 files changed, 141 insertions, 92 deletions
diff --git a/include/linux/zconf.h b/include/linux/zconf.h
index f1cfd66b9554..0beb75e38caa 100644
--- a/include/linux/zconf.h
+++ b/include/linux/zconf.h
@@ -35,6 +35,18 @@
35# define MAX_WBITS 15 /* 32K LZ77 window */ 35# define MAX_WBITS 15 /* 32K LZ77 window */
36#endif 36#endif
37 37
38/* default windowBits for decompression. MAX_WBITS is for compression only */
39#ifndef DEF_WBITS
40# define DEF_WBITS MAX_WBITS
41#endif
42
43/* default memLevel */
44#if MAX_MEM_LEVEL >= 8
45# define DEF_MEM_LEVEL 8
46#else
47# define DEF_MEM_LEVEL MAX_MEM_LEVEL
48#endif
49
38 /* Type declarations */ 50 /* Type declarations */
39 51
40typedef unsigned char Byte; /* 8 bits */ 52typedef unsigned char Byte; /* 8 bits */
diff --git a/include/linux/zlib.h b/include/linux/zlib.h
index 4fa32f0d4df8..9e3192a7dc6f 100644
--- a/include/linux/zlib.h
+++ b/include/linux/zlib.h
@@ -1,7 +1,6 @@
1/* zlib.h -- interface of the 'zlib' general purpose compression library 1/* zlib.h -- interface of the 'zlib' general purpose compression library
2 version 1.1.3, July 9th, 1998
3 2
4 Copyright (C) 1995-1998 Jean-loup Gailly and Mark Adler 3 Copyright (C) 1995-2005 Jean-loup Gailly and Mark Adler
5 4
6 This software is provided 'as-is', without any express or implied 5 This software is provided 'as-is', without any express or implied
7 warranty. In no event will the authors be held liable for any damages 6 warranty. In no event will the authors be held liable for any damages
@@ -24,7 +23,7 @@
24 23
25 24
26 The data format used by the zlib library is described by RFCs (Request for 25 The data format used by the zlib library is described by RFCs (Request for
27 Comments) 1950 to 1952 in the files ftp://ds.internic.net/rfc/rfc1950.txt 26 Comments) 1950 to 1952 in the files http://www.ietf.org/rfc/rfc1950.txt
28 (zlib format), rfc1951.txt (deflate format) and rfc1952.txt (gzip format). 27 (zlib format), rfc1951.txt (deflate format) and rfc1952.txt (gzip format).
29*/ 28*/
30 29
@@ -33,7 +32,22 @@
33 32
34#include <linux/zconf.h> 33#include <linux/zconf.h>
35 34
36#define ZLIB_VERSION "1.1.3" 35/* zlib deflate based on ZLIB_VERSION "1.1.3" */
36/* zlib inflate based on ZLIB_VERSION "1.2.3" */
37
38/*
39 This is a modified version of zlib for use inside the Linux kernel.
40 The main changes are to perform all memory allocation in advance.
41
42 Inflation Changes:
43 * Z_PACKET_FLUSH is added and used by ppp_deflate. Before returning
44 this checks there is no more input data available and the next data
45 is a STORED block. It also resets the mode to be read for the next
46 data, all as per PPP requirements.
47 * Addition of zlib_inflateIncomp which copies incompressible data into
48 the history window and adjusts the accoutning without calling
49 zlib_inflate itself to inflate the data.
50*/
37 51
38/* 52/*
39 The 'zlib' compression library provides in-memory compression and 53 The 'zlib' compression library provides in-memory compression and
@@ -48,9 +62,18 @@
48 application must provide more input and/or consume the output 62 application must provide more input and/or consume the output
49 (providing more output space) before each call. 63 (providing more output space) before each call.
50 64
65 The compressed data format used by default by the in-memory functions is
66 the zlib format, which is a zlib wrapper documented in RFC 1950, wrapped
67 around a deflate stream, which is itself documented in RFC 1951.
68
51 The library also supports reading and writing files in gzip (.gz) format 69 The library also supports reading and writing files in gzip (.gz) format
52 with an interface similar to that of stdio. 70 with an interface similar to that of stdio.
53 71
72 The zlib format was designed to be compact and fast for use in memory
73 and on communications channels. The gzip format was designed for single-
74 file compression on file systems, has a larger header than zlib to maintain
75 directory information, and uses a different, slower check method than zlib.
76
54 The library does not install any signal handler. The decoder checks 77 The library does not install any signal handler. The decoder checks
55 the consistency of the compressed data, so the library should never 78 the consistency of the compressed data, so the library should never
56 crash even in case of corrupted input. 79 crash even in case of corrupted input.
@@ -119,7 +142,8 @@ typedef z_stream *z_streamp;
119#define Z_SYNC_FLUSH 3 142#define Z_SYNC_FLUSH 3
120#define Z_FULL_FLUSH 4 143#define Z_FULL_FLUSH 4
121#define Z_FINISH 5 144#define Z_FINISH 5
122/* Allowed flush values; see deflate() below for details */ 145#define Z_BLOCK 6 /* Only for inflate at present */
146/* Allowed flush values; see deflate() and inflate() below for details */
123 147
124#define Z_OK 0 148#define Z_OK 0
125#define Z_STREAM_END 1 149#define Z_STREAM_END 1
@@ -155,13 +179,6 @@ typedef z_stream *z_streamp;
155 179
156 /* basic functions */ 180 /* basic functions */
157 181
158extern const char * zlib_zlibVersion (void);
159/* The application can compare zlibVersion and ZLIB_VERSION for consistency.
160 If the first character differs, the library code actually used is
161 not compatible with the zlib.h header file used by the application.
162 This check is automatically made by deflateInit and inflateInit.
163 */
164
165extern int zlib_deflate_workspacesize (void); 182extern int zlib_deflate_workspacesize (void);
166/* 183/*
167 Returns the number of bytes that needs to be allocated for a per- 184 Returns the number of bytes that needs to be allocated for a per-
@@ -315,9 +332,9 @@ extern int zlib_inflateInit (z_streamp strm);
315extern int zlib_inflate (z_streamp strm, int flush); 332extern int zlib_inflate (z_streamp strm, int flush);
316/* 333/*
317 inflate decompresses as much data as possible, and stops when the input 334 inflate decompresses as much data as possible, and stops when the input
318 buffer becomes empty or the output buffer becomes full. It may some 335 buffer becomes empty or the output buffer becomes full. It may introduce
319 introduce some output latency (reading input without producing any output) 336 some output latency (reading input without producing any output) except when
320 except when forced to flush. 337 forced to flush.
321 338
322 The detailed semantics are as follows. inflate performs one or both of the 339 The detailed semantics are as follows. inflate performs one or both of the
323 following actions: 340 following actions:
@@ -341,11 +358,26 @@ extern int zlib_inflate (z_streamp strm, int flush);
341 must be called again after making room in the output buffer because there 358 must be called again after making room in the output buffer because there
342 might be more output pending. 359 might be more output pending.
343 360
344 If the parameter flush is set to Z_SYNC_FLUSH, inflate flushes as much 361 The flush parameter of inflate() can be Z_NO_FLUSH, Z_SYNC_FLUSH,
345 output as possible to the output buffer. The flushing behavior of inflate is 362 Z_FINISH, or Z_BLOCK. Z_SYNC_FLUSH requests that inflate() flush as much
346 not specified for values of the flush parameter other than Z_SYNC_FLUSH 363 output as possible to the output buffer. Z_BLOCK requests that inflate() stop
347 and Z_FINISH, but the current implementation actually flushes as much output 364 if and when it gets to the next deflate block boundary. When decoding the
348 as possible anyway. 365 zlib or gzip format, this will cause inflate() to return immediately after
366 the header and before the first block. When doing a raw inflate, inflate()
367 will go ahead and process the first block, and will return when it gets to
368 the end of that block, or when it runs out of data.
369
370 The Z_BLOCK option assists in appending to or combining deflate streams.
371 Also to assist in this, on return inflate() will set strm->data_type to the
372 number of unused bits in the last byte taken from strm->next_in, plus 64
373 if inflate() is currently decoding the last block in the deflate stream,
374 plus 128 if inflate() returned immediately after decoding an end-of-block
375 code or decoding the complete header up to just before the first byte of the
376 deflate stream. The end-of-block will not be indicated until all of the
377 uncompressed data from that block has been written to strm->next_out. The
378 number of unused bits may in general be greater than seven, except when
379 bit 7 of data_type is set, in which case the number of unused bits will be
380 less than eight.
349 381
350 inflate() should normally be called until it returns Z_STREAM_END or an 382 inflate() should normally be called until it returns Z_STREAM_END or an
351 error. However if all decompression is to be performed in a single step 383 error. However if all decompression is to be performed in a single step
@@ -355,29 +387,44 @@ extern int zlib_inflate (z_streamp strm, int flush);
355 uncompressed data. (The size of the uncompressed data may have been saved 387 uncompressed data. (The size of the uncompressed data may have been saved
356 by the compressor for this purpose.) The next operation on this stream must 388 by the compressor for this purpose.) The next operation on this stream must
357 be inflateEnd to deallocate the decompression state. The use of Z_FINISH 389 be inflateEnd to deallocate the decompression state. The use of Z_FINISH
358 is never required, but can be used to inform inflate that a faster routine 390 is never required, but can be used to inform inflate that a faster approach
359 may be used for the single inflate() call. 391 may be used for the single inflate() call.
360 392
361 If a preset dictionary is needed at this point (see inflateSetDictionary 393 In this implementation, inflate() always flushes as much output as
362 below), inflate sets strm-adler to the adler32 checksum of the 394 possible to the output buffer, and always uses the faster approach on the
363 dictionary chosen by the compressor and returns Z_NEED_DICT; otherwise 395 first call. So the only effect of the flush parameter in this implementation
364 it sets strm->adler to the adler32 checksum of all output produced 396 is on the return value of inflate(), as noted below, or when it returns early
365 so far (that is, total_out bytes) and returns Z_OK, Z_STREAM_END or 397 because Z_BLOCK is used.
366 an error code as described below. At the end of the stream, inflate() 398
367 checks that its computed adler32 checksum is equal to that saved by the 399 If a preset dictionary is needed after this call (see inflateSetDictionary
368 compressor and returns Z_STREAM_END only if the checksum is correct. 400 below), inflate sets strm->adler to the adler32 checksum of the dictionary
401 chosen by the compressor and returns Z_NEED_DICT; otherwise it sets
402 strm->adler to the adler32 checksum of all output produced so far (that is,
403 total_out bytes) and returns Z_OK, Z_STREAM_END or an error code as described
404 below. At the end of the stream, inflate() checks that its computed adler32
405 checksum is equal to that saved by the compressor and returns Z_STREAM_END
406 only if the checksum is correct.
407
408 inflate() will decompress and check either zlib-wrapped or gzip-wrapped
409 deflate data. The header type is detected automatically. Any information
410 contained in the gzip header is not retained, so applications that need that
411 information should instead use raw inflate, see inflateInit2() below, or
412 inflateBack() and perform their own processing of the gzip header and
413 trailer.
369 414
370 inflate() returns Z_OK if some progress has been made (more input processed 415 inflate() returns Z_OK if some progress has been made (more input processed
371 or more output produced), Z_STREAM_END if the end of the compressed data has 416 or more output produced), Z_STREAM_END if the end of the compressed data has
372 been reached and all uncompressed output has been produced, Z_NEED_DICT if a 417 been reached and all uncompressed output has been produced, Z_NEED_DICT if a
373 preset dictionary is needed at this point, Z_DATA_ERROR if the input data was 418 preset dictionary is needed at this point, Z_DATA_ERROR if the input data was
374 corrupted (input stream not conforming to the zlib format or incorrect 419 corrupted (input stream not conforming to the zlib format or incorrect check
375 adler32 checksum), Z_STREAM_ERROR if the stream structure was inconsistent 420 value), Z_STREAM_ERROR if the stream structure was inconsistent (for example
376 (for example if next_in or next_out was NULL), Z_MEM_ERROR if there was not 421 if next_in or next_out was NULL), Z_MEM_ERROR if there was not enough memory,
377 enough memory, Z_BUF_ERROR if no progress is possible or if there was not 422 Z_BUF_ERROR if no progress is possible or if there was not enough room in the
378 enough room in the output buffer when Z_FINISH is used. In the Z_DATA_ERROR 423 output buffer when Z_FINISH is used. Note that Z_BUF_ERROR is not fatal, and
379 case, the application may then call inflateSync to look for a good 424 inflate() can be called again with more input and more output space to
380 compression block. 425 continue decompressing. If Z_DATA_ERROR is returned, the application may then
426 call inflateSync() to look for a good compression block if a partial recovery
427 of the data is desired.
381*/ 428*/
382 429
383 430
@@ -547,16 +594,36 @@ extern int inflateInit2 (z_streamp strm, int windowBits);
547 The windowBits parameter is the base two logarithm of the maximum window 594 The windowBits parameter is the base two logarithm of the maximum window
548 size (the size of the history buffer). It should be in the range 8..15 for 595 size (the size of the history buffer). It should be in the range 8..15 for
549 this version of the library. The default value is 15 if inflateInit is used 596 this version of the library. The default value is 15 if inflateInit is used
550 instead. If a compressed stream with a larger window size is given as 597 instead. windowBits must be greater than or equal to the windowBits value
551 input, inflate() will return with the error code Z_DATA_ERROR instead of 598 provided to deflateInit2() while compressing, or it must be equal to 15 if
552 trying to allocate a larger window. 599 deflateInit2() was not used. If a compressed stream with a larger window
553 600 size is given as input, inflate() will return with the error code
554 inflateInit2 returns Z_OK if success, Z_MEM_ERROR if there was not enough 601 Z_DATA_ERROR instead of trying to allocate a larger window.
555 memory, Z_STREAM_ERROR if a parameter is invalid (such as a negative 602
556 memLevel). msg is set to null if there is no error message. inflateInit2 603 windowBits can also be -8..-15 for raw inflate. In this case, -windowBits
557 does not perform any decompression apart from reading the zlib header if 604 determines the window size. inflate() will then process raw deflate data,
558 present: this will be done by inflate(). (So next_in and avail_in may be 605 not looking for a zlib or gzip header, not generating a check value, and not
559 modified, but next_out and avail_out are unchanged.) 606 looking for any check values for comparison at the end of the stream. This
607 is for use with other formats that use the deflate compressed data format
608 such as zip. Those formats provide their own check values. If a custom
609 format is developed using the raw deflate format for compressed data, it is
610 recommended that a check value such as an adler32 or a crc32 be applied to
611 the uncompressed data as is done in the zlib, gzip, and zip formats. For
612 most applications, the zlib format should be used as is. Note that comments
613 above on the use in deflateInit2() applies to the magnitude of windowBits.
614
615 windowBits can also be greater than 15 for optional gzip decoding. Add
616 32 to windowBits to enable zlib and gzip decoding with automatic header
617 detection, or add 16 to decode only the gzip format (the zlib format will
618 return a Z_DATA_ERROR). If a gzip stream is being decoded, strm->adler is
619 a crc32 instead of an adler32.
620
621 inflateInit2 returns Z_OK if success, Z_MEM_ERROR if there was not enough
622 memory, Z_STREAM_ERROR if a parameter is invalid (such as a null strm). msg
623 is set to null if there is no error message. inflateInit2 does not perform
624 any decompression apart from reading the zlib header if present: this will
625 be done by inflate(). (So next_in and avail_in may be modified, but next_out
626 and avail_out are unchanged.)
560*/ 627*/
561 628
562extern int zlib_inflateSetDictionary (z_streamp strm, 629extern int zlib_inflateSetDictionary (z_streamp strm,
@@ -564,16 +631,19 @@ extern int zlib_inflateSetDictionary (z_streamp strm,
564 uInt dictLength); 631 uInt dictLength);
565/* 632/*
566 Initializes the decompression dictionary from the given uncompressed byte 633 Initializes the decompression dictionary from the given uncompressed byte
567 sequence. This function must be called immediately after a call of inflate 634 sequence. This function must be called immediately after a call of inflate,
568 if this call returned Z_NEED_DICT. The dictionary chosen by the compressor 635 if that call returned Z_NEED_DICT. The dictionary chosen by the compressor
569 can be determined from the Adler32 value returned by this call of 636 can be determined from the adler32 value returned by that call of inflate.
570 inflate. The compressor and decompressor must use exactly the same 637 The compressor and decompressor must use exactly the same dictionary (see
571 dictionary (see deflateSetDictionary). 638 deflateSetDictionary). For raw inflate, this function can be called
639 immediately after inflateInit2() or inflateReset() and before any call of
640 inflate() to set the dictionary. The application must insure that the
641 dictionary that was used for compression is provided.
572 642
573 inflateSetDictionary returns Z_OK if success, Z_STREAM_ERROR if a 643 inflateSetDictionary returns Z_OK if success, Z_STREAM_ERROR if a
574 parameter is invalid (such as NULL dictionary) or the stream state is 644 parameter is invalid (such as NULL dictionary) or the stream state is
575 inconsistent, Z_DATA_ERROR if the given dictionary doesn't match the 645 inconsistent, Z_DATA_ERROR if the given dictionary doesn't match the
576 expected one (incorrect Adler32 value). inflateSetDictionary does not 646 expected one (incorrect adler32 value). inflateSetDictionary does not
577 perform any decompression: this will be done by subsequent calls of 647 perform any decompression: this will be done by subsequent calls of
578 inflate(). 648 inflate().
579*/ 649*/
@@ -614,40 +684,19 @@ extern int zlib_inflateIncomp (z_stream *strm);
614 containing the data at next_in (except that the data is not output). 684 containing the data at next_in (except that the data is not output).
615*/ 685*/
616 686
617 /* various hacks, don't look :) */
618
619/* deflateInit and inflateInit are macros to allow checking the zlib version
620 * and the compiler's view of z_stream:
621 */
622extern int zlib_deflateInit_ (z_streamp strm, int level,
623 const char *version, int stream_size);
624extern int zlib_inflateInit_ (z_streamp strm,
625 const char *version, int stream_size);
626extern int zlib_deflateInit2_ (z_streamp strm, int level, int method,
627 int windowBits, int memLevel,
628 int strategy, const char *version,
629 int stream_size);
630extern int zlib_inflateInit2_ (z_streamp strm, int windowBits,
631 const char *version, int stream_size);
632#define zlib_deflateInit(strm, level) \ 687#define zlib_deflateInit(strm, level) \
633 zlib_deflateInit_((strm), (level), ZLIB_VERSION, sizeof(z_stream)) 688 zlib_deflateInit2((strm), (level), Z_DEFLATED, MAX_WBITS, \
689 DEF_MEM_LEVEL, Z_DEFAULT_STRATEGY)
634#define zlib_inflateInit(strm) \ 690#define zlib_inflateInit(strm) \
635 zlib_inflateInit_((strm), ZLIB_VERSION, sizeof(z_stream)) 691 zlib_inflateInit2((strm), DEF_WBITS)
636#define zlib_deflateInit2(strm, level, method, windowBits, memLevel, strategy) \
637 zlib_deflateInit2_((strm),(level),(method),(windowBits),(memLevel),\
638 (strategy), ZLIB_VERSION, sizeof(z_stream))
639#define zlib_inflateInit2(strm, windowBits) \
640 zlib_inflateInit2_((strm), (windowBits), ZLIB_VERSION, sizeof(z_stream))
641 692
693extern int zlib_deflateInit2(z_streamp strm, int level, int method,
694 int windowBits, int memLevel,
695 int strategy);
696extern int zlib_inflateInit2(z_streamp strm, int windowBits);
642 697
643#if !defined(_Z_UTIL_H) && !defined(NO_DUMMY_DECL) 698#if !defined(_Z_UTIL_H) && !defined(NO_DUMMY_DECL)
644 struct internal_state {int dummy;}; /* hack for buggy compilers */ 699 struct internal_state {int dummy;}; /* hack for buggy compilers */
645#endif 700#endif
646 701
647extern const char * zlib_zError (int err);
648#if 0
649extern int zlib_inflateSyncPoint (z_streamp z);
650#endif
651extern const uLong * zlib_get_crc_table (void);
652
653#endif /* _ZLIB_H */ 702#endif /* _ZLIB_H */
diff --git a/include/linux/zutil.h b/include/linux/zutil.h
index ee0c59cf2136..6adfa9a6ffe9 100644
--- a/include/linux/zutil.h
+++ b/include/linux/zutil.h
@@ -23,18 +23,6 @@ typedef unsigned long ulg;
23 23
24 /* common constants */ 24 /* common constants */
25 25
26#ifndef DEF_WBITS
27# define DEF_WBITS MAX_WBITS
28#endif
29/* default windowBits for decompression. MAX_WBITS is for compression only */
30
31#if MAX_MEM_LEVEL >= 8
32# define DEF_MEM_LEVEL 8
33#else
34# define DEF_MEM_LEVEL MAX_MEM_LEVEL
35#endif
36/* default memLevel */
37
38#define STORED_BLOCK 0 26#define STORED_BLOCK 0
39#define STATIC_TREES 1 27#define STATIC_TREES 1
40#define DYN_TREES 2 28#define DYN_TREES 2