Commit | Line | Data |
---|---|---|
3013fe88 NW |
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 | #include "crypt.h" | |
57 | ||
58 | #ifdef DEBUG | |
59 | # include <stdio.h> | |
60 | #endif | |
61 | ||
78ed81a3 | 62 | #ifdef RCSID |
63 | static char rcsid[] = "$Id: bits.c,v 0.9 1993/06/11 10:16:58 jloup Exp $"; | |
3013fe88 NW |
64 | #endif |
65 | ||
66 | /* =========================================================================== | |
67 | * Local data used by the "bit string" routines. | |
68 | */ | |
69 | ||
70 | local file_t zfile; /* output gzip file */ | |
71 | ||
72 | local unsigned short bi_buf; | |
73 | /* Output buffer. bits are inserted starting at the bottom (least significant | |
74 | * bits). | |
75 | */ | |
76 | ||
77 | #define Buf_size (8 * 2*sizeof(char)) | |
78 | /* Number of bits used within bi_buf. (bi_buf might be implemented on | |
79 | * more than 16 bits on some systems.) | |
80 | */ | |
81 | ||
82 | local int bi_valid; | |
83 | /* Number of valid bits in bi_buf. All bits above the last valid bit | |
84 | * are always zero. | |
85 | */ | |
86 | ||
78ed81a3 | 87 | int (*read_buf) OF((char *buf, unsigned size)); |
3013fe88 NW |
88 | /* Current input function. Set to mem_read for in-memory compression */ |
89 | ||
90 | #ifdef DEBUG | |
91 | ulg bits_sent; /* bit length of the compressed data */ | |
92 | #endif | |
93 | ||
94 | /* =========================================================================== | |
95 | * Initialize the bit string routines. | |
96 | */ | |
97 | void bi_init (zipfile) | |
98 | file_t zipfile; /* output zip file, NO_FILE for in-memory compression */ | |
99 | { | |
100 | zfile = zipfile; | |
101 | bi_buf = 0; | |
102 | bi_valid = 0; | |
103 | #ifdef DEBUG | |
104 | bits_sent = 0L; | |
105 | #endif | |
106 | ||
107 | /* Set the defaults for file compression. They are set by memcompress | |
108 | * for in-memory compression. | |
109 | */ | |
110 | if (zfile != NO_FILE) { | |
111 | read_buf = file_read; | |
112 | } | |
113 | } | |
114 | ||
115 | /* =========================================================================== | |
116 | * Send a value on a given number of bits. | |
117 | * IN assertion: length <= 16 and value fits in length bits. | |
118 | */ | |
119 | void send_bits(value, length) | |
120 | int value; /* value to send */ | |
121 | int length; /* number of bits */ | |
122 | { | |
123 | #ifdef DEBUG | |
124 | Tracev((stderr," l %2d v %4x ", length, value)); | |
125 | Assert(length > 0 && length <= 15, "invalid length"); | |
126 | bits_sent += (ulg)length; | |
127 | #endif | |
128 | /* If not enough room in bi_buf, use (valid) bits from bi_buf and | |
129 | * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) | |
130 | * unused bits in value. | |
131 | */ | |
132 | if (bi_valid > (int)Buf_size - length) { | |
133 | bi_buf |= (value << bi_valid); | |
134 | put_short(bi_buf); | |
135 | bi_buf = (ush)value >> (Buf_size - bi_valid); | |
136 | bi_valid += length - Buf_size; | |
137 | } else { | |
138 | bi_buf |= value << bi_valid; | |
139 | bi_valid += length; | |
140 | } | |
141 | } | |
142 | ||
143 | /* =========================================================================== | |
144 | * Reverse the first len bits of a code, using straightforward code (a faster | |
145 | * method would use a table) | |
146 | * IN assertion: 1 <= len <= 15 | |
147 | */ | |
148 | unsigned bi_reverse(code, len) | |
149 | unsigned code; /* the value to invert */ | |
150 | int len; /* its bit length */ | |
151 | { | |
152 | register unsigned res = 0; | |
153 | do { | |
154 | res |= code & 1; | |
155 | code >>= 1, res <<= 1; | |
156 | } while (--len > 0); | |
157 | return res >> 1; | |
158 | } | |
159 | ||
160 | /* =========================================================================== | |
161 | * Write out any remaining bits in an incomplete byte. | |
162 | */ | |
163 | void bi_windup() | |
164 | { | |
165 | if (bi_valid > 8) { | |
166 | put_short(bi_buf); | |
167 | } else if (bi_valid > 0) { | |
168 | put_byte(bi_buf); | |
169 | } | |
170 | bi_buf = 0; | |
171 | bi_valid = 0; | |
172 | #ifdef DEBUG | |
173 | bits_sent = (bits_sent+7) & ~7; | |
174 | #endif | |
175 | } | |
176 | ||
177 | /* =========================================================================== | |
178 | * Copy a stored block to the zip file, storing first the length and its | |
179 | * one's complement if requested. | |
180 | */ | |
181 | void copy_block(buf, len, header) | |
182 | char *buf; /* the input data */ | |
183 | unsigned len; /* its length */ | |
184 | int header; /* true if block header must be written */ | |
185 | { | |
186 | bi_windup(); /* align on byte boundary */ | |
187 | ||
188 | if (header) { | |
189 | put_short((ush)len); | |
190 | put_short((ush)~len); | |
191 | #ifdef DEBUG | |
192 | bits_sent += 2*16; | |
193 | #endif | |
194 | } | |
195 | #ifdef DEBUG | |
196 | bits_sent += (ulg)len<<3; | |
197 | #endif | |
198 | while (len--) { | |
199 | #ifdef CRYPT | |
200 | int t; | |
201 | if (key) zencode(*buf, t); | |
202 | #endif | |
203 | put_byte(*buf++); | |
204 | } | |
205 | } |