1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
38 /*-
39  * fcompress.c - File compression ala IEEE Computer, June 1984.
42  *		Spencer W. Thomas	(decvax!utah-cs!thomas)
75 /* A code_int must be able to hold 2**BITS values of type int, and also -1. */
92 #define	MAXCODE(n_bits)	((1 << (n_bits)) - 1)
109 	 * Block compression parameters -- after all codes are used up,
139 #define	fp		zs->zs_fp
140 #define	zmode		zs->zs_mode
141 #define	state		zs->zs_state
142 #define	n_bits		zs->zs_n_bits
143 #define	maxbits		zs->zs_maxbits
144 #define	maxcode		zs->zs_maxcode
145 #define	maxmaxcode	zs->zs_maxmaxcode
146 #define	htab		zs->zs_htab
147 #define	codetab		zs->zs_codetab
148 #define	hsize		zs->zs_hsize
149 #define	free_ent	zs->zs_free_ent
150 #define	block_compress	zs->zs_block_compress
151 #define	clear_flg	zs->zs_clear_flg
152 #define	ratio		zs->zs_ratio
153 #define	checkpoint	zs->zs_checkpoint
154 #define	offset		zs->zs_offset
155 #define	in_count	zs->zs_in_count
156 #define	bytes_out	zs->zs_bytes_out
157 #define	out_count	zs->zs_out_count
158 #define	buf		zs->zs_buf
159 #define	fcode		zs->u.w.zs_fcode
160 #define	hsize_reg	zs->u.w.zs_hsize_reg
161 #define	ent		zs->u.w.zs_ent
162 #define	hshift		zs->u.w.zs_hshift
163 #define	stackp		zs->u.r.zs_stackp
164 #define	finchar		zs->u.r.zs_finchar
165 #define	code		zs->u.r.zs_code
166 #define	oldcode		zs->u.r.zs_oldcode
167 #define	incode		zs->u.r.zs_incode
168 #define	roffset		zs->u.r.zs_roffset
169 #define	size		zs->u.r.zs_size
170 #define	gbuf		zs->u.r.zs_gbuf
205 /*-
207  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
210  * 	Modified Lempel-Ziv method (LZW).  Basically finds common
216 /*-
219  * Algorithm:  use open addressing double hashing (no chaining) on the
221  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
223  * to a faster exclusive-or manipulation.  Also do block compression with
225  * ratio decreases, but after the table fills.  The variable-length output
226  * codes are re-sized at this point, and a special CLEAR code is generated
254 		return (-1);  in zwrite()
257 		return (-1);  in zwrite()
260 	bytes_out = 3;		/* Includes 3-byte header mojo. */  in zwrite()
270 	--count;  in zwrite()
275 	hshift = 8 - hshift;	/* Set hash code range bound. */  in zwrite()
280 middle:	for (i = 0; count--;) {  in zwrite()
291 		disp = hsize_reg - i;	/* Secondary hash (after G. Knott). */  in zwrite()
294 probe:		if ((i -= disp) < 0)  in zwrite()
303 nomatch:	if (output(zs, (code_int) ent) == -1)  in zwrite()
304 			return (-1);  in zwrite()
308 			codetabof(i) = free_ent++;	/* code -> hashtable */  in zwrite()
312 			if (cl_block(zs) == -1)  in zwrite()
313 				return (-1);  in zwrite()
327 		if (output(zs, (code_int) ent) == -1) {  in zclose()
330 			return (-1);  in zclose()
333 		if (output(zs, (code_int) - 1) == -1) {  in zclose()
336 			return (-1);  in zclose()
339 	rval = fclose(fp) == EOF ? -1 : 0;  in zclose()
344 /*-
347  * 	code:	A n_bits-bit integer.  If == -1, then EOF.  This assumes
348  *		that n_bits =< (long)wordsize - 1.
384 		bits -= (8 - r_off);  in output()
385 		ocode >>= 8 - r_off;  in output()
390 			bits -= 8;  in output()
401 				return (-1);  in output()
417 					return (-1);  in output()
438 				return (-1);  in output()
448  * the "string" table on-the-fly; requiring no table to be stored in the
480 		return (-1);  in zread()
482 	maxbits = header[2];	/* Set -b from file. */  in zread()
488 		return (-1);  in zread()
492 	for (code = 255; code >= 0; code--) {  in zread()
499 	if (oldcode == -1)	/* EOF already? */  in zread()
504 	count--;  in zread()
507 	while ((code = getcode(zs)) > -1) {  in zread()
510 			for (code = 255; code >= 0; code--)  in zread()
514 			oldcode = -1;  in zread()
521 			if (code > free_ent || oldcode == -1) {  in zread()
524 				return (-1);  in zread()
533 		 * bound by 1 << BITS - 256.  in zread()
545 			if (count-- == 0)  in zread()
547 			*bp++ = *--stackp;  in zread()
551 		if ((code = free_ent) < maxmaxcode && oldcode != -1) {  in zread()
561 eof:	return (num - count);  in zread()
564 /*-
565  * Read one code from the standard input.  If EOF, return -1.
569  * 	code or -1 is returned.
598 			return (-1);  in getcode()
601 		size = (size << 3) - (n_bits - 1);  in getcode()
612 	bits -= (8 - r_off);  in getcode()
613 	r_off = 8 - r_off;	/* Now, roffset into gcode word. */  in getcode()
619 		bits -= 8;  in getcode()
652 		if (output(zs, (code_int) CLEAR) == -1)  in cl_block()
653 			return (-1);  in cl_block()
664 	m1 = -1;  in cl_hash()
666 	i = cl_hsize - 16;  in cl_hash()
668 		*(htab_p - 16) = m1;  in cl_hash()
669 		*(htab_p - 15) = m1;  in cl_hash()
670 		*(htab_p - 14) = m1;  in cl_hash()
671 		*(htab_p - 13) = m1;  in cl_hash()
672 		*(htab_p - 12) = m1;  in cl_hash()
673 		*(htab_p - 11) = m1;  in cl_hash()
674 		*(htab_p - 10) = m1;  in cl_hash()
675 		*(htab_p - 9) = m1;  in cl_hash()
676 		*(htab_p - 8) = m1;  in cl_hash()
677 		*(htab_p - 7) = m1;  in cl_hash()
678 		*(htab_p - 6) = m1;  in cl_hash()
679 		*(htab_p - 5) = m1;  in cl_hash()
680 		*(htab_p - 4) = m1;  in cl_hash()
681 		*(htab_p - 3) = m1;  in cl_hash()
682 		*(htab_p - 2) = m1;  in cl_hash()
683 		*(htab_p - 1) = m1;  in cl_hash()
684 		htab_p -= 16;  in cl_hash()
685 	} while ((i -= 16) >= 0);  in cl_hash()
686 	for (i += 16; i > 0; i--)  in cl_hash()
687 		*--htab_p = m1;  in cl_hash()
719 	 * Layering compress on top of stdio in order to provide buffering,  in zopen()