1 /*
2
3 Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
4 Permission is granted to any individual or institution to use, copy, or
5 redistribute this software so long as all of the original files are included
6 unmodified, that it is not sold for profit, and that this copyright notice
7 is retained.
8
9 */
10
11 /*
12 * bits.c by Jean-loup Gailly.
13 *
14 * This is a new version of im_bits.c originally written by Richard B. Wales
15 *
16 * PURPOSE
17 *
18 * Output variable-length bit strings.
19 *
20 * DISCUSSION
21 *
22 * The PKZIP "deflate" file format interprets compressed file data
23 * as a sequence of bits. Multi-bit strings in the file may cross
24 * byte boundaries without restriction.
25 *
26 * The first bit of each byte is the low-order bit.
27 *
28 * The routines in this file allow a variable-length bit value to
29 * be output right-to-left (useful for literal values). For
30 * left-to-right output (useful for code strings from the tree routines),
31 * the bits must have been reversed first with bi_reverse().
32 *
33 * INTERFACE
34 *
35 * void bi_init (FILE *zipfile)
36 * Initialize the bit string routines.
37 *
38 * void send_bits (int value, int length)
39 * Write out a bit string, taking the source bits right to
40 * left.
41 *
42 * int bi_reverse (int value, int length)
43 * Reverse the bits of a bit string, taking the source bits left to
44 * right and emitting them right to left.
45 *
46 * void bi_windup (void)
47 * Write out any remaining bits in an incomplete byte.
48 *
49 * void copy_block(char far *buf, unsigned len, int header)
50 * Copy a stored block to the zip file, storing first the length and
51 * its one's complement if requested.
52 *
53 */
54
55 #include "zip.h"
56
57 /* ===========================================================================
58 * Local data used by the "bit string" routines.
59 */
60
61 local FILE *zfile; /* output zip file */
62
63 local unsigned short bi_buf;
64 /* Output buffer. bits are inserted starting at the bottom (least significant
65 * bits).
66 */
67
68 #define Buf_size (8 * 2*sizeof(char))
69 /* Number of bits used within bi_buf. (bi_buf might be implemented on
70 * more than 16 bits on some systems.)
71 */
72
73 local int bi_valid; /* number of valid bits in bi_buf */
74 /* All bits above the last valid bit are always zero.
75 */
76
77 #ifdef DEBUG
78 ulg bits_sent; /* bit length of the compressed data */
79 #endif
80
81 /* Output a 16 bit value to the bit stream, lower (oldest) byte first */
82 #define PUTSHORT(w) \
83 { (void) zputc ((char)((w) & 0xff), zfile); \
84 (void) zputc ((char)((ush)(w) >> 8), zfile); \
85 }
86
87 /* Output an 8 bit value to the bit stream, bits right to left */
88 #define PUTBYTE(w) \
89 { (void) zputc ((char)((w) & 0xff), zfile); \
90 }
91
92 /* ===========================================================================
93 * Initialize the bit string routines.
94 */
bi_init(zipfile)95 void bi_init (zipfile)
96
97 FILE *zipfile; /* output zip file */
98 {
99 zfile = zipfile;
100 bi_buf = 0;
101 bi_valid = 0;
102 #ifdef DEBUG
103 bits_sent = 0L;
104 #endif
105 }
106
107 /* ===========================================================================
108 * Send a value on a given number of bits.
109 * IN assertion: length <= 16 and value fits in length bits.
110 */
send_bits(value,length)111 void send_bits(value, length)
112 int value; /* value to send */
113 int length; /* number of bits */
114 {
115 #ifdef DEBUG
116 Tracevv((stderr," l %2d v %4x ", length, value));
117 Assert(length > 0 && length <= 15, "invalid length");
118 bits_sent += (ulg)length;
119 #endif
120 /* If not enough room in bi_buf, use (valid) bits from bi_buf and
121 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
122 * unused bits in value.
123 */
124 if (bi_valid > (int)Buf_size - length) {
125 bi_buf |= (value << bi_valid);
126 PUTSHORT(bi_buf);
127 bi_buf = (ush)value >> (Buf_size - bi_valid);
128 bi_valid += length - Buf_size;
129 } else {
130 bi_buf |= value << bi_valid;
131 bi_valid += length;
132 }
133 }
134
135 /* ===========================================================================
136 * Reverse the first len bits of a code, using straightforward code (a faster
137 * method would use a table)
138 * IN assertion: 1 <= len <= 15
139 */
bi_reverse(code,len)140 unsigned bi_reverse(code, len)
141 unsigned code; /* the value to invert */
142 int len; /* its bit length */
143 {
144 register unsigned res = 0;
145 do {
146 res |= code & 1;
147 code >>= 1, res <<= 1;
148 } while (--len > 0);
149 return res >> 1;
150 }
151
152 /* ===========================================================================
153 * Write out any remaining bits in an incomplete byte.
154 */
bi_windup()155 void bi_windup()
156 {
157 if (bi_valid > 8) {
158 PUTSHORT(bi_buf);
159 } else if (bi_valid > 0) {
160 PUTBYTE(bi_buf);
161 }
162 bi_buf = 0;
163 bi_valid = 0;
164 if (ferror (zfile)) error ("write error on zip file");
165 #ifdef DEBUG
166 bits_sent = (bits_sent+7) & ~7;
167 #endif
168 }
169
170 /* ===========================================================================
171 * Copy a stored block to the zip file, storing first the length and its
172 * one's complement if requested.
173 */
copy_block(buf,len,header)174 void copy_block(buf, len, header)
175 char far *buf; /* the input data */
176 unsigned len; /* its length */
177 int header; /* true if block header must be written */
178 {
179 bi_windup(); /* align on byte boundary */
180
181 if (header) {
182 PUTSHORT((ush)len);
183 PUTSHORT((ush)~len);
184 #ifdef DEBUG
185 bits_sent += 2*16;
186 #endif
187 }
188 zfwrite(buf, 1, len, zfile); /* ??? far */
189 #ifdef DEBUG
190 bits_sent += (ulg)len<<3;
191 #endif
192 fflush(zfile);
193 if (ferror(zfile)) error ("write error on zip file");
194 }
195