1 #ifndef LINT
2 static char sccsid[]="@(#) lzc.c 2.6 88/01/30 18:39:15";
3 #endif /* LINT */
4
5 /*
6 Lempel-Ziv compression. Mostly based on Tom Pfau's assembly language
7 code.
8
9 The contents of this file are hereby released to the public domain.
10
11 -- Rahul Dhesi 1986/12/31
12 */
13
14 #include "options.h"
15 #include "zoo.h"
16 #include "zooio.h"
17 #include "various.h"
18 #include "zoofns.h" /* function definitions */
19 /* zoomem.h defines IN_BUF_SIZE & OUT_BUF_SIZE */
20 #include "zoomem.h"
21 #include "debug.h"
22 #include "assert.h"
23 /* lzconst.h contains constants for lzd() and lzc() */
24 #include "lzconst.h"
25
26 void init_ctab PARMS((void));
27 void wr_ccode PARMS((int));
28 int rd_cch PARMS((void));
29 int lukup_ccode PARMS((int, int, int *));
30 void ad_ccode PARMS((int, int, int));
31 void check_ratio PARMS((void));
32 void flush_c PARMS((int));
33
34 /* interval at which to check ratio */
35 #define CHECKGAP 4000
36 #define NEXT_USE 1
37 #define FIRST_USE 2
38 #define FOUND 0
39
40 struct tabentry {
41 int first;
42 int next;
43 char z_ch;
44 };
45
46 extern char *out_buf_adr;
47 extern char *in_buf_adr;
48 extern char memflag; /* memory allocated? */
49 struct tabentry *table; /* this table also used by lzd.c */
50 static unsigned int free_code;
51 static int nbits;
52 static unsigned int max_code;
53 static unsigned int bitsout;
54 static int bit_interval;
55 static unsigned int bytesin, ratio, ratflag;
56 static unsigned int in_offset, in_size;
57 static unsigned int bit_offset;
58
59 #ifdef UNBUF_IO
60 #define BLOCKFILE int
61 #define BLOCKREAD read
62 #define BLOCKWRITE write
63 int read PARMS ((int, VOIDPTR, unsigned));
64 int write PARMS ((int, VOIDPTR, unsigned));
65 #else
66 #define BLOCKFILE ZOOFILE
67 #define BLOCKREAD zooread
68 #define BLOCKWRITE zoowrite
69 #endif /* UNBUF_IO */
70
71 static BLOCKFILE in_f, out_f;
72
lzc(input_f,output_f)73 int lzc (input_f, output_f)
74 BLOCKFILE input_f, output_f;
75 {
76 int nextch, prefix_code, k;
77 int status;
78 int where;
79
80 in_f = input_f;
81 out_f = output_f;
82
83 bit_offset = in_offset = in_size = 0;
84
85 if (memflag == 0) {
86 table = (struct tabentry *) ealloc((MAXMAX+10) * sizeof(struct tabentry));
87 memflag++;
88 }
89
90 init_ctab();
91 wr_ccode(CLEAR);
92 nextch = rd_cch();
93 if (nextch == EOF) { /* note real EOF, not Z_EOF */
94 wr_ccode (Z_EOF);
95 flush_c ((int) ((bit_offset + 7) / 8));
96 return (0); /* normal return from compress */
97 }
98
99 /* compression loop begins here with nextch holding the next input char */
100 loop1:
101 if (ratflag != 0)
102 check_ratio();
103 nextch &= 0xff; /* turn character to code */
104 assert(nextch < 256);
105 loop2:
106 prefix_code = nextch;
107 nextch = rd_cch();
108 if (nextch == EOF) { /* note real EOF, not Z_EOF */
109 wr_ccode (prefix_code);
110 wr_ccode (Z_EOF);
111 flush_c ((int) ((bit_offset + 7) / 8));
112 return (0); /* normal return from compress */
113 }
114 nextch &= 0xff; /* force to 8 bits */
115 assert(nextch < 256);
116
117 k = nextch;
118 status = lukup_ccode (prefix_code, nextch, &where);
119 if (status == FOUND) {
120 nextch = where; /* where found */
121 goto loop2;
122 }
123 assert(status == FIRST_USE || status == NEXT_USE);
124
125 /* reach here with status = FIRST_USE or NEXT_USE */
126 ad_ccode (status, nextch, where);
127
128 wr_ccode (prefix_code);
129 nextch = k;
130
131 if (free_code <= max_code)
132 goto loop1;
133 assert(nbits >= 9 && nbits <= MAXBITS);
134 if (nbits >= MAXBITS) {
135 /* To continue using table after it is full, remove next two lines */
136 wr_ccode (CLEAR);
137 init_ctab();
138
139 goto loop1;
140 }
141
142 nbits++;
143 assert(nbits >= 9 && nbits <= MAXBITS);
144 max_code = max_code << 1;
145 goto loop1;
146 } /* end lzc() */
147
wr_ccode(code)148 void wr_ccode (code)
149 int code;
150 {
151 unsigned int ofs_inbyte, hibits;
152 int byte_offset;
153
154 #ifdef DEBUG
155 if (code == CLEAR)
156 printf(" CLEAR\n");
157 #endif
158
159 assert(nbits >= 9 && nbits <= MAXBITS);
160 bitsout += nbits; /* total number of bits written */
161 bit_interval -= nbits;
162 if (bit_interval < 0)
163 ratflag = 1; /* time to check ratio */
164
165 byte_offset = bit_offset / 8;
166 ofs_inbyte = bit_offset % 8; /* offset within byte */
167 bit_offset += nbits; /* allowing for new code */
168
169 if (byte_offset >= OUTBUFSIZ - 4) {
170 flush_c (byte_offset);
171 bit_offset = ofs_inbyte + nbits;
172 out_buf_adr[0] = out_buf_adr [byte_offset];
173 byte_offset = 0;
174 }
175
176 code = code & 0xffff; /* force to 16 bits */
177
178 if (ofs_inbyte == 0)
179 out_buf_adr[byte_offset] = code & 0xff;
180 else
181 out_buf_adr[byte_offset] |= (code << ofs_inbyte) & 0xff;
182
183 hibits = ((unsigned int) code) >> (8 - ofs_inbyte);
184 out_buf_adr[byte_offset+1] = hibits & 0xff;
185 out_buf_adr[byte_offset+2] = (((unsigned int) hibits) >> 8) & 0xff;
186
187 assert(nbits >= 9 && nbits <= MAXBITS);
188 } /* end wr_ccode() */
189
init_ctab()190 void init_ctab()
191 {
192 int i;
193 bytesin = bitsout = ratio = ratflag = 0;
194 bit_interval = CHECKGAP;
195 nbits = 9;
196 max_code = 512;
197 #ifdef COMMENT
198 for (i = 0; i < 256; i++) {
199 #endif
200 for (i = 0; i < MAXMAX+1; i++) {
201 table[i].z_ch = table[i].first = table[i].next = -1;
202 }
203 #ifdef COMMENT
204 /*DEBUG*/ table[MAXMAX].first = table[MAXMAX].next = -1;
205 /*DEBUG*/ table[MAXMAX-1].first = table[MAXMAX-1].next = -1;
206 #endif
207 free_code = FIRST_FREE;
208 } /* end init_ctab() */
209
210 int rd_cch()
211 {
212 int count;
213 bytesin++;
214 if (in_offset == in_size) {
215 count = BLOCKREAD (in_f, in_buf_adr, INBUFSIZ);
216 if (count == -1)
217 prterror ('f', "Error reading input file during compression.\n");
218 addbfcrc (in_buf_adr, count);
219 if (count == 0) {
220 debug((printf("\nEOF on input\n")))
221 return (EOF); /* real EOF, not Z_EOF */
222 }
223 in_size = count;
224 debug((printf("\ninput %d chars\n", count)))
225 in_offset = 0;
226 }
227 in_offset++;
228 return (in_buf_adr[in_offset-1] & 0xff);
229 } /* end rd_cch () */
230
231 void check_ratio()
232 {
233 #ifdef COMMENT
234 int rat;
235 if (bitsout > 16383) { /* avoid overflow */
236 bitsout /= 4;
237 bytesin /= 4;
238 }
239 rat = (2 * bitsout) / bytesin;
240 if (1.1 * rat < ratio) {
241 printf("#");
242 wr_ccode (CLEAR);
243 init_ctab();
244 bit_interval = CHECKGAP;
245 bitsout = 0;
246 bytesin = 0;
247 ratio = 0;
248 } else
249 ratio = ((ratio << 2) + ((2 * bitsout) / bytesin)) / 5;
250 #else
251 bit_interval = CHECKGAP;
252 bitsout = 0;
253 bytesin = 0;
254 #endif
255 } /* end check_ratio() */
256
257 void ad_ccode (status, ch, index)
258 int status, index, ch;
259 {
260 assert(status == FIRST_USE || status == NEXT_USE);
261 #ifdef COMMENT
262 if (free_code >= MAXMAX) /* to fix apparent bug in original */
263 return;
264 #endif
265 #ifdef COMMENT
266 if (status == NEXT_USE)
267 table[index].next = free_code;
268 else /* else must be FIRST_USE */
269 table[index].first = free_code;
270 #endif
271 if (status == NEXT_USE)
272 table[index].next = (free_code >= MAXMAX ? -1 : free_code);
273 else /* else must be FIRST_USE */
274 table[index].first = (free_code >= MAXMAX ? -1 : free_code);
275
276 #ifdef COMMENT
277 if (free_code < MAXMAX) {
278 #endif
279 if (free_code <= MAXMAX) {
280 table[free_code].first = table[free_code].next = -1;
281 table[free_code].z_ch = ch & 0xff;
282 free_code++;
283 }
284 } /* end ad_ccode() */
285
286 int lukup_ccode (index, ch, where)
287 int index; /* where to start looking */
288 int ch; /* char to look for */
289 int *where; /* last entry looked at */
290 {
291 *where = index;
292 index = table[index].first;
293 if (index == -1) {
294 return (FIRST_USE); /* not found, first use */
295 } else {
296 while (1) {
297 if ((table[index].z_ch & 0xff) == (ch & 0xff)) {
298 *where = index;
299 return (FOUND);
300 }
301 *where = index;
302 index = table[index].next;
303 if (index == -1) {
304 return (NEXT_USE);
305 }
306 } /* end while */
307 } /* end else */
308 } /* end lukup_ccode() */
309
310 void flush_c (count)
311 int count;
312 {
313 int status;
314 #ifdef DEBUG
315 printf(" <flushed %d bytes> ", count);
316 #endif
317
318 #ifdef CHECK_BREAK
319 check_break();
320 #endif
321
322 if (count != 0) {
323 status = BLOCKWRITE (out_f, out_buf_adr, count);
324 if (status == -1)
325 prterror ('f', "Error writing during compression.\n");
326 }
327 }
328