Annotation of /trunk/mkinitrd-magellan/klibc/usr/gzip/bits.c
Parent Directory | Revision Log
Revision 815 -
(hide 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 | niro | 532 | /* 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 | niro | 815 | static char rcsid[] = "$Id: bits.c,v 1.1 2002/08/18 00:59:21 hpa Exp $"; |
63 | niro | 532 | #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 | } |