1 /* bits.c -- output variable-length bit strings
2
3 Copyright (C) 1999, 2009-2023 Free Software Foundation, Inc.
4 Copyright (C) 1992-1993 Jean-loup Gailly
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software Foundation,
18 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19
20
21 /*
22 * PURPOSE
23 *
24 * Output variable-length bit strings. Compression can be done
25 * to a file or to memory. (The latter is not supported in this version.)
26 *
27 * DISCUSSION
28 *
29 * The PKZIP "deflate" file format interprets compressed file data
30 * as a sequence of bits. Multi-bit strings in the file may cross
31 * byte boundaries without restriction.
32 *
33 * The first bit of each byte is the low-order bit.
34 *
35 * The routines in this file allow a variable-length bit value to
36 * be output right-to-left (useful for literal values). For
37 * left-to-right output (useful for code strings from the tree routines),
38 * the bits must have been reversed first with bi_reverse().
39 *
40 * For in-memory compression, the compressed bit stream goes directly
41 * into the requested output buffer. The input data is read in blocks
42 * by the mem_read() function. The buffer is limited to 64K on 16 bit
43 * machines.
44 *
45 * INTERFACE
46 *
47 * void bi_init (FILE *zipfile)
48 * Initialize the bit string routines.
49 *
50 * void send_bits (int value, int length)
51 * Write out a bit string, taking the source bits right to
52 * left.
53 *
54 * int bi_reverse (int value, int length)
55 * Reverse the bits of a bit string, taking the source bits left to
56 * right and emitting them right to left.
57 *
58 * void bi_windup ()
59 * Write out any remaining bits in an incomplete byte.
60 *
61 * void copy_block(char *buf, unsigned len, int header)
62 * Copy a stored block to the zip file, storing first the length and
63 * its one's complement if requested.
64 *
65 */
66
67 #include <config.h>
68 #include "tailor.h"
69 #include "gzip.h"
70
71 #ifdef DEBUG
72 # include <stdio.h>
73 #endif
74
75 /* ===========================================================================
76 * Local data used by the "bit string" routines.
77 */
78
79 static file_t zfile; /* output gzip file */
80
81 #ifndef IBM_Z_DFLTCC
82 static
83 #endif
84 unsigned short bi_buf;
85 /* Output buffer. bits are inserted starting at the bottom (least significant
86 * bits).
87 */
88
89 #define Buf_size (8 * 2*sizeof(char))
90 /* Number of bits used within bi_buf. (bi_buf might be implemented on
91 * more than 16 bits on some systems.)
92 */
93
94 #ifndef IBM_Z_DFLTCC
95 static
96 #endif
97 int bi_valid;
98 /* Number of valid bits in bi_buf. All bits above the last valid bit
99 * are always zero.
100 */
101
102 int (*read_buf) (char *buf, unsigned size);
103 /* Current input function. Set to mem_read for in-memory compression */
104
105 #ifdef DEBUG
106 off_t bits_sent; /* bit length of the compressed data */
107 #endif
108
109 /* ===========================================================================
110 * Initialize the bit string routines.
111 * ZIPFILE is the output zip file; it is NO_FILE for in-memory compression.
112 */
113 void
114 bi_init (file_t zipfile)
115 {
116 zfile = zipfile;
117 bi_buf = 0;
118 bi_valid = 0;
119 #ifdef DEBUG
120 bits_sent = 0L;
121 #endif
122
123 /* Set the defaults for file compression. They are set by memcompress
124 * for in-memory compression.
125 */
126 if (zfile != NO_FILE) {
127 read_buf = file_read;
128 }
129 }
130
131 /* ===========================================================================
132 * Send VALUE on LENGTH bits.
133 * IN assertion: LENGTH <= 16 and VALUE fits in LENGTH bits.
134 */
135 void
136 send_bits (int value, int length)
137 {
138 #ifdef DEBUG
139 Tracev ((stderr, " l %2d v %4x ", length, value + 0u));
140 Assert(length > 0 && length <= 15, "invalid length");
141 bits_sent += (off_t)length;
142 #endif
143 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
144 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
145 * unused bits in value.
146 */
147 if (bi_valid > (int)Buf_size - length) {
148 bi_buf |= (value << bi_valid);
149 put_short(bi_buf);
150 bi_buf = (ush)value >> (Buf_size - bi_valid);
151 bi_valid += length - Buf_size;
152 } else {
153 bi_buf |= value << bi_valid;
154 bi_valid += length;
155 }
156 }
157
158 /* ===========================================================================
159 * Reverse the first LEN bits of CODE, using straightforward code (a faster
160 * method would use a table)
161 * IN assertion: 1 <= LEN <= 15
162 */
163 unsigned
164 bi_reverse (unsigned code, int len)
165 {
166 register unsigned res = 0;
167 do {
168 res |= code & 1;
169 code >>= 1, res <<= 1;
170 } while (--len > 0);
171 return res >> 1;
172 }
173
174 /* ===========================================================================
175 * Write out any remaining bits in an incomplete byte.
176 */
177 void
178 bi_windup ()
179 {
180 if (bi_valid > 8) {
181 put_short(bi_buf);
182 } else if (bi_valid > 0) {
183 put_byte(bi_buf);
184 }
185 bi_buf = 0;
186 bi_valid = 0;
187 #ifdef DEBUG
188 bits_sent = (bits_sent+7) & ~7;
189 #endif
190 }
191
192 /* ===========================================================================
193 * Copy a stored block to the zip file, storing first the length and its
194 * one's complement if requested. BUF is the input data of length
195 * LEN; HEADER is true if block header must be written.
196 */
197 void
198 copy_block (char *buf, unsigned len, int header)
199 {
200 bi_windup(); /* align on byte boundary */
201
202 if (header) {
203 put_short((ush)len);
204 put_short((ush)~len);
205 #ifdef DEBUG
206 bits_sent += 2*16;
207 #endif
208 }
209 #ifdef DEBUG
210 bits_sent += (off_t)len<<3;
211 #endif
212 while (len--) {
213 put_byte(*buf++);
214 }
215 }