1 #ifndef lint
2 static char sccsid[] = "@(#)compact.c 4.8 (Berkeley) 02/28/91";
3 #endif
4
5 /*
6 * Adaptive Huffman code input to output
7 *
8 * On - line algorithm
9 *
10 * Does not prepend decoding tree
11 *
12 * Written by Colin L. Mc Master (UCB) February 28, 1979
13 */
14 #include <strings.h>
15 #include "compact.h"
16
17 union cio d;
18 union cio c;
19 int bits;
20 char *infname; /* input file's name */
21 char fname[MAXPATHLEN+1]; /* output file's name */
22 struct stat ucfstatus; /* uncompacted file status */
23
24 int verbose = 0;
25
main(argc,argv)26 main(argc, argv)
27 int argc;
28 char *argv[];
29 {
30 register short j;
31
32 argc--, argv++;
33 if (argc > 0 && strcmp(*argv, "-v") == 0) {
34 verbose++;
35 argc--, argv++;
36 }
37 dir[513].next = NULL;
38 for (head = dir + (j = 513); j--; ) {
39 dirp = head--;
40 head->next = dirp;
41 }
42 bottom = dirp->pt = dict;
43 dict[0].sons[LEFT].top = dict[0].sons[RIGHT].top = dirp;
44 dirq = dirp->next;
45 in[EF].flags = FBIT | SEEN;
46 if (argc == 0)
47 exit(compact("-"));
48 for (j = 0; j < argc; j++) {
49 if (verbose && argc > 0)
50 printf("%s: ", argv[j]);
51 if (compact(argv[j]))
52 exit(1);
53 }
54 exit(0);
55 }
56
57 /*
58 * Compact a single file ("-" implies stdin).
59 */
compact(file)60 compact(file)
61 char *file;
62 {
63 int j, ignore;
64 FILE *setup();
65
66 for (j = 256; j--; )
67 in[j].flags = 0;
68 bottom->sons[RIGHT].top->next = flist;
69 bottom->sons[RIGHT].top = dirp;
70 flist = dirq;
71 cfp = uncfp = NULL;
72 if (strcmp(file, "-") != 0) {
73 char *cp, *tp;
74
75 /* verify .C suffix fits */
76 cp = rindex(file, '/');
77 if (cp == 0)
78 cp = file;
79 else
80 cp++;
81 tp = index(cp, '\0');
82 if (tp - cp > MAXNAMLEN || strlen(file) + 2 >= MAXPATHLEN) {
83 fprintf(stderr, "%s: File name too long\n", file);
84 goto bad;
85 }
86 uncfp = fopen(file, "r");
87 if (uncfp == NULL) {
88 fprintf(stderr, "compact: "), perror(file);
89 goto bad;
90 }
91 fstat(fileno(uncfp), &ucfstatus);
92 if ((ucfstatus.st_mode & S_IFMT) != S_IFREG) {
93 fprintf(stderr, "%s: Not a regular file.\n", file);
94 goto bad;
95 }
96 } else
97 uncfp = stdin;
98 infname = file;
99
100 cfp = setup(uncfp, &ignore);
101 if (cfp == NULL) {
102 if (ignore)
103 goto done;
104 goto bad;
105 }
106 if (compress(uncfp, cfp)) {
107 if (cfp != stdout)
108 (void) unlink(fname);
109 goto bad2;
110 }
111 encode(EF);
112 if (bits) {
113 d.integ <<= 16 - bits;
114 putc(d.chars.hib, cfp);
115 if (bits > 8)
116 putc(d.chars.lob, cfp);
117 bits = 0;
118 }
119 fflush(cfp);
120 if (ferror(uncfp) || ferror(cfp)) {
121 if (cfp != stdout) {
122 fprintf(stderr, "compact: ");
123 if (ferror(cfp))
124 perror(fname);
125 else
126 perror(infname);
127 (void) unlink(fname);
128 }
129 goto bad;
130 }
131 if (cfp != stdout) {
132 struct stat cfstatus;
133 longint csize, ucsize;
134
135 (void) fstat(fileno(cfp), &cfstatus);
136 csize = cfstatus.st_size;
137 ucsize = ucfstatus.st_size;
138 if (csize >= ucsize) {
139 printf("%s: ", infname);
140 (void) unlink(fname);
141 printf("Not compacted, does not save bytes.\n");
142 goto done;
143 }
144 if (verbose) {
145 FILE *fd;
146 longint n, m;
147
148 while (ucsize - csize > 21474) {
149 ucsize /= 10;
150 csize /= 10;
151 }
152 n = 100000 * (ucsize - csize) / ucsize + 5;
153 m = (n % 1000) / 10;
154 bits = m % 10 + '0';
155 c.integ = m / 10 + '0';
156 printf("%ld.%c%c%% compression\n",
157 n / 1000, c.chars.lob, bits);
158 }
159 if (unlink(infname) < 0)
160 fprintf(stderr, "compact: "), perror(infname);
161 }
162 done:
163 if (cfp != NULL && cfp != stdout)
164 fclose(cfp);
165 if (uncfp != NULL)
166 fclose(uncfp);
167 return (0);
168 bad2:
169 fprintf(stderr, "compact: ");
170 if (cfp != stdout)
171 perror(infname);
172 else
173 fprintf(stderr,
174 "Unsuccessful compact of standard input to standard output.\n");
175 bad:
176 if (cfp != NULL && cfp != stdout)
177 fclose(cfp);
178 if (uncfp != NULL)
179 fclose(uncfp);
180 return (1);
181 }
182
encode(ch)183 encode(ch)
184 int ch;
185 {
186 register struct node *pp;
187 int stack[17];
188 register int stbits = 1, *sp = &stack[0], rbits = bits;
189 register union cio *dp = &d;
190 union cio c;
191
192 c.integ = ch;
193 *sp = in[ch].flags & FBIT;
194 pp = in[ch].fp;
195
196 while (pp->fath.fp) {
197 *sp <<= 1;
198 if (pp->fath.flags & FBIT)
199 (*sp)++;
200 stbits++;
201 if ((stbits &= 017) == 0)
202 sp++;
203 pp = pp->fath.fp;
204 }
205
206 /* pop the output stack */
207 do {
208 while (stbits-- > 0) {
209 dp->integ <<= 1;
210 if (*sp & 01)
211 dp->integ++;
212 ++rbits;
213 if ((rbits &= 017) == 0) {
214 putc(dp->chars.hib, cfp);
215 putc(dp->chars.lob, cfp);
216 if (ferror(cfp))
217 goto done;
218 }
219 *sp >>= 1;
220 }
221 stbits = 16;
222 } while (--sp >= &stack[0]);
223 done:
224 bits = rbits;
225 }
226
compress(uncfp,cfp)227 compress(uncfp, cfp)
228 register FILE *uncfp, *cfp;
229 {
230 register union cio *dp = &d;
231 register union cio *cp = &c;
232
233 cp->integ = (dp->integ >> 8) & 0377;
234 for (; cp->integ != EOF; cp->integ = getc(uncfp)) {
235 if ((in[cp->integ].flags & SEEN) == 0) {
236 register short j, m;
237
238 encode(NC);
239 uptree(NC);
240 insert(cp->integ);
241
242 m = 0200;
243 for (j = 8; j--; m >>= 1) {
244 dp->integ <<= 1;
245 if (m & cp->integ)
246 dp->integ++;
247 ++bits;
248 if ((bits &= 017) == 0) {
249 putc(dp->chars.hib, cfp);
250 putc(dp->chars.lob, cfp);
251 }
252 }
253 } else
254 encode(cp->integ);
255 if (ferror(cfp)) {
256 perror(fname);
257 return (1);
258 }
259 uptree(cp->integ);
260 }
261 if (ferror(uncfp)) {
262 perror(infname);
263 return (1);
264 }
265 return (0);
266 }
267
268 FILE *
setup(uncfp,ignore)269 setup(uncfp, ignore)
270 FILE *uncfp;
271 int *ignore;
272 {
273 FILE *cfp = NULL;
274 register union cio *dp = &d;
275 register union cio *cp = &c;
276
277 dp->integ = getc(uncfp);
278 if (*ignore = (dp->integ == EOF))
279 goto bad;
280 cp->integ = getc(uncfp);
281 if (*ignore = (cp->integ == EOF))
282 goto bad;
283 dp->chars.hib = cp->integ & 0377;
284 if ((dp->integ &= 0177777) == COMPACTED) {
285 fprintf(stderr, "%s: Already compacted.\n", infname);
286 *ignore = 1;
287 goto bad;
288 }
289 if (dp->integ == PACKED) {
290 fprintf(stderr,
291 "%s: Already packed using pack program, use unpack.\n",
292 infname);
293 *ignore = 1;
294 goto bad;
295 }
296 if (strcmp(infname, "-") != 0) {
297 sprintf(fname, "%s.C", infname);
298 cfp = fopen(fname, "w");
299 if (cfp == NULL)
300 goto bad2;
301 (void) fchmod(fileno(cfp), ucfstatus.st_mode);
302 } else
303 cfp = stdout;
304 cp->integ = COMPACTED;
305 putc(cp->chars.lob, cfp);
306 putc(cp->chars.hib, cfp);
307 if (ferror(cfp))
308 goto bad2;
309 bits = 8;
310 cp->integ = dp->integ & 0377;
311
312 in[NC].fp = in[EF].fp = dict[0].sons[LEFT].sp.p = bottom = dict + 1;
313 bottom->sons[LEFT].count = bottom->sons[RIGHT].count =
314 dict[0].sons[RIGHT].count = 1;
315 dirp->next = dict[0].sons[RIGHT].top = bottom->sons[LEFT].top =
316 bottom->sons[RIGHT].top = dirq = NEW;
317 dirq->next = NULL;
318 dict[0].fath.fp = NULL;
319 dirq->pt = bottom->fath.fp = in[cp->integ].fp = dict;
320 in[cp->integ].flags = (FBIT | SEEN);
321 in[NC].flags = SEEN;
322 dict[0].fath.flags = RLEAF;
323 bottom->fath.flags = (LLEAF | RLEAF);
324 dict[0].sons[LEFT].count = 2;
325
326 dict[0].sons[RIGHT].sp.ch = cp->integ;
327 bottom->sons[LEFT].sp.ch = NC;
328 bottom->sons[RIGHT].sp.ch = EF;
329 return (cfp);
330 bad2:
331 if (cfp && cfp != stdout) {
332 fprintf(stderr, "compact: "), perror(fname);
333 (void) unlink(fname);
334 }
335 bad:
336 if (cfp && cfp != stdout)
337 fclose(cfp);
338 return (NULL);
339 }
340