Contents of /trunk/mkinitrd-magellan/klibc/usr/gzip/bits.c
Parent Directory | Revision Log
Revision 815 -
(show annotations)
(download)
Fri Apr 24 18:32:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 5791 byte(s)
Fri Apr 24 18:32:46 2009 UTC (15 years ago) by niro
File MIME type: text/plain
File size: 5791 byte(s)
-updated to klibc-1.5.15
1 | /* bits.c -- output variable-length bit strings |
2 | * Copyright (C) 1992-1993 Jean-loup Gailly |
3 | * This is free software; you can redistribute it and/or modify it under the |
4 | * terms of the GNU General Public License, see the file COPYING. |
5 | */ |
6 | |
7 | |
8 | /* |
9 | * PURPOSE |
10 | * |
11 | * Output variable-length bit strings. Compression can be done |
12 | * to a file or to memory. (The latter is not supported in this version.) |
13 | * |
14 | * DISCUSSION |
15 | * |
16 | * The PKZIP "deflate" file format interprets compressed file data |
17 | * as a sequence of bits. Multi-bit strings in the file may cross |
18 | * byte boundaries without restriction. |
19 | * |
20 | * The first bit of each byte is the low-order bit. |
21 | * |
22 | * The routines in this file allow a variable-length bit value to |
23 | * be output right-to-left (useful for literal values). For |
24 | * left-to-right output (useful for code strings from the tree routines), |
25 | * the bits must have been reversed first with bi_reverse(). |
26 | * |
27 | * For in-memory compression, the compressed bit stream goes directly |
28 | * into the requested output buffer. The input data is read in blocks |
29 | * by the mem_read() function. The buffer is limited to 64K on 16 bit |
30 | * machines. |
31 | * |
32 | * INTERFACE |
33 | * |
34 | * void bi_init (FILE *zipfile) |
35 | * Initialize the bit string routines. |
36 | * |
37 | * void send_bits (int value, int length) |
38 | * Write out a bit string, taking the source bits right to |
39 | * left. |
40 | * |
41 | * int bi_reverse (int value, int length) |
42 | * Reverse the bits of a bit string, taking the source bits left to |
43 | * right and emitting them right to left. |
44 | * |
45 | * void bi_windup (void) |
46 | * Write out any remaining bits in an incomplete byte. |
47 | * |
48 | * void copy_block(char *buf, unsigned len, int header) |
49 | * Copy a stored block to the zip file, storing first the length and |
50 | * its one's complement if requested. |
51 | * |
52 | */ |
53 | |
54 | #include "tailor.h" |
55 | #include "gzip.h" |
56 | |
57 | #ifdef DEBUG |
58 | # include <stdio.h> |
59 | #endif |
60 | |
61 | #ifdef RCSID |
62 | static char rcsid[] = "$Id: bits.c,v 1.1 2002/08/18 00:59:21 hpa Exp $"; |
63 | #endif |
64 | |
65 | /* =========================================================================== |
66 | * Local data used by the "bit string" routines. |
67 | */ |
68 | |
69 | local file_t zfile; /* output gzip file */ |
70 | |
71 | local unsigned short bi_buf; |
72 | /* Output buffer. bits are inserted starting at the bottom (least significant |
73 | * bits). |
74 | */ |
75 | |
76 | #define Buf_size (8 * 2*sizeof(char)) |
77 | /* Number of bits used within bi_buf. (bi_buf might be implemented on |
78 | * more than 16 bits on some systems.) |
79 | */ |
80 | |
81 | local int bi_valid; |
82 | /* Number of valid bits in bi_buf. All bits above the last valid bit |
83 | * are always zero. |
84 | */ |
85 | |
86 | int (*read_buf) OF((char *buf, unsigned size)); |
87 | /* Current input function. Set to mem_read for in-memory compression */ |
88 | |
89 | #ifdef DEBUG |
90 | ulg bits_sent; /* bit length of the compressed data */ |
91 | #endif |
92 | |
93 | /* =========================================================================== |
94 | * Initialize the bit string routines. |
95 | */ |
96 | void bi_init (zipfile) |
97 | file_t zipfile; /* output zip file, NO_FILE for in-memory compression */ |
98 | { |
99 | zfile = zipfile; |
100 | bi_buf = 0; |
101 | bi_valid = 0; |
102 | #ifdef DEBUG |
103 | bits_sent = 0L; |
104 | #endif |
105 | |
106 | /* Set the defaults for file compression. They are set by memcompress |
107 | * for in-memory compression. |
108 | */ |
109 | if (zfile != NO_FILE) { |
110 | read_buf = file_read; |
111 | } |
112 | } |
113 | |
114 | /* =========================================================================== |
115 | * Send a value on a given number of bits. |
116 | * IN assertion: length <= 16 and value fits in length bits. |
117 | */ |
118 | void send_bits(value, length) |
119 | int value; /* value to send */ |
120 | int length; /* number of bits */ |
121 | { |
122 | #ifdef DEBUG |
123 | Tracev((stderr," l %2d v %4x ", length, value)); |
124 | Assert(length > 0 && length <= 15, "invalid length"); |
125 | bits_sent += (ulg)length; |
126 | #endif |
127 | /* If not enough room in bi_buf, use (valid) bits from bi_buf and |
128 | * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) |
129 | * unused bits in value. |
130 | */ |
131 | if (bi_valid > (int)Buf_size - length) { |
132 | bi_buf |= (value << bi_valid); |
133 | put_short(bi_buf); |
134 | bi_buf = (ush)value >> (Buf_size - bi_valid); |
135 | bi_valid += length - Buf_size; |
136 | } else { |
137 | bi_buf |= value << bi_valid; |
138 | bi_valid += length; |
139 | } |
140 | } |
141 | |
142 | /* =========================================================================== |
143 | * Reverse the first len bits of a code, using straightforward code (a faster |
144 | * method would use a table) |
145 | * IN assertion: 1 <= len <= 15 |
146 | */ |
147 | unsigned bi_reverse(code, len) |
148 | unsigned code; /* the value to invert */ |
149 | int len; /* its bit length */ |
150 | { |
151 | register unsigned res = 0; |
152 | do { |
153 | res |= code & 1; |
154 | code >>= 1, res <<= 1; |
155 | } while (--len > 0); |
156 | return res >> 1; |
157 | } |
158 | |
159 | /* =========================================================================== |
160 | * Write out any remaining bits in an incomplete byte. |
161 | */ |
162 | void bi_windup() |
163 | { |
164 | if (bi_valid > 8) { |
165 | put_short(bi_buf); |
166 | } else if (bi_valid > 0) { |
167 | put_byte(bi_buf); |
168 | } |
169 | bi_buf = 0; |
170 | bi_valid = 0; |
171 | #ifdef DEBUG |
172 | bits_sent = (bits_sent+7) & ~7; |
173 | #endif |
174 | } |
175 | |
176 | /* =========================================================================== |
177 | * Copy a stored block to the zip file, storing first the length and its |
178 | * one's complement if requested. |
179 | */ |
180 | void copy_block(buf, len, header) |
181 | char *buf; /* the input data */ |
182 | unsigned len; /* its length */ |
183 | int header; /* true if block header must be written */ |
184 | { |
185 | bi_windup(); /* align on byte boundary */ |
186 | |
187 | if (header) { |
188 | put_short((ush)len); |
189 | put_short((ush)~len); |
190 | #ifdef DEBUG |
191 | bits_sent += 2*16; |
192 | #endif |
193 | } |
194 | #ifdef DEBUG |
195 | bits_sent += (ulg)len<<3; |
196 | #endif |
197 | while (len--) { |
198 | put_byte(*buf++); |
199 | } |
200 | } |