1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21 /*
22 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
27 /* All Rights Reserved */
28
29 /*
30 * Huffman encoding program
31 * Usage: pack [[ -f ] [ - ] [-/] filename ... ] filename ...
32 * - option: enable/disable listing of statistics
33 */
34
35 #include <locale.h>
36 #include <stdarg.h>
37 #include <sys/isa_defs.h>
38 #include <sys/param.h>
39 #include <utime.h>
40 #include <sys/acl.h>
41 #include <aclutils.h>
42 #include <libcmdutils.h>
43
44 #undef lint
45
46 #define END 256
47 #define PACKED 017436 /* <US><RS> - Unlikely value */
48 #define SUF0 '.'
49 #define SUF1 'z'
50
51 struct stat status, ostatus;
52 static struct utimbuf u_times;
53
54 /* union for overlaying a long int with a set of four characters */
55 union FOUR {
56 struct { long int lng; } lint;
57 struct { char c0, c1, c2, c3; } chars;
58 };
59
60 /* character counters */
61 long count [END+1];
62 union FOUR insize;
63 long outsize;
64 long dictsize;
65 int diffbytes;
66
67 /* i/o stuff */
68 char vflag = 0;
69 int force = 0; /* allow forced packing for consistency in directory */
70
71 static char filename [MAXPATHLEN];
72 static int max_name;
73
74 int infile; /* unpacked file */
75 int outfile; /* packed file */
76 char inbuff [BUFSIZ];
77 char outbuff [BUFSIZ+4];
78
79 /* variables associated with the tree */
80 int maxlev;
81 int levcount [25];
82 int lastnode;
83 int parent [2*END+1];
84
85 /* variables associated with the encoding process */
86 char length [END+1];
87 long bits [END+1];
88 union FOUR mask;
89 long inc;
90 #if defined(_LITTLE_ENDIAN)
91 char *maskshuff[4] = {&(mask.chars.c3),
92 &(mask.chars.c2),
93 &(mask.chars.c1),
94 &(mask.chars.c0)};
95 #elif defined(_BIG_ENDIAN)
96 char *maskshuff[4] = {&(mask.chars.c0),
97 &(mask.chars.c1),
98 &(mask.chars.c2),
99 &(mask.chars.c3)};
100 #else
101 #error Unknown byte ordering!
102 #endif
103
104 /* the heap */
105 int n;
106 struct heap {
107 long int count;
108 int node;
109 } heap [END+2];
110 #define hmove(a, b) {(b).count = (a).count; (b).node = (a).node; }
111
112 static void heapify(int i);
113
114 /* Extended system attribute support */
115
116 static int saflg = 0;
117
118
119 /* gather character frequency statistics */
120 /* return 1 if successful, 0 otherwise */
121 int
input(char * source)122 input(char *source)
123 {
124 register int i;
125 for (i = 0; i < END; i++)
126 count[i] = 0;
127 while ((i = read(infile, inbuff, BUFSIZ)) > 0)
128 while (i > 0)
129 count[inbuff[--i]&0377] += 2;
130 if (i == 0)
131 return (1);
132 (void) fprintf(stderr, gettext(
133 "pack: %s: read error - file unchanged: "), source);
134 perror("");
135 return (0);
136 }
137
138 /* encode the current file */
139 /* return 1 if successful, 0 otherwise */
140 int
output(char * source)141 output(char *source)
142 {
143 int c, i, inleft;
144 char *inp;
145 register char **q, *outp;
146 register int bitsleft;
147 long temp;
148
149 /* output ``PACKED'' header */
150 outbuff[0] = 037; /* ascii US */
151 outbuff[1] = 036; /* ascii RS */
152 /* output the length and the dictionary */
153 temp = insize.lint.lng;
154 for (i = 5; i >= 2; i--) {
155 outbuff[i] = (char)(temp & 0377);
156 temp >>= 8;
157 }
158 outp = &outbuff[6];
159 *outp++ = maxlev;
160 for (i = 1; i < maxlev; i++)
161 *outp++ = levcount[i];
162 *outp++ = levcount[maxlev]-2;
163 for (i = 1; i <= maxlev; i++)
164 for (c = 0; c < END; c++)
165 if (length[c] == i)
166 *outp++ = c;
167 dictsize = outp-&outbuff[0];
168
169 /* output the text */
170 (void) lseek(infile, 0L, 0);
171 outsize = 0;
172 bitsleft = 8;
173 inleft = 0;
174 do {
175 if (inleft <= 0) {
176 inleft = read(infile, inp = &inbuff[0], BUFSIZ);
177 if (inleft < 0) {
178 (void) fprintf(stderr, gettext(
179 "pack: %s: read error - file unchanged: "),
180 source);
181 perror("");
182 return (0);
183 }
184 }
185 c = (--inleft < 0) ? END : (*inp++ & 0377);
186 mask.lint.lng = bits[c]<<bitsleft;
187 q = &maskshuff[0];
188 if (bitsleft == 8)
189 *outp = **q++;
190 else
191 *outp |= **q++;
192 bitsleft -= length[c];
193 while (bitsleft < 0) {
194 *++outp = **q++;
195 bitsleft += 8;
196 }
197 if (outp >= &outbuff[BUFSIZ]) {
198 if (write(outfile, outbuff, BUFSIZ) != BUFSIZ) {
199 wrerr: (void) fprintf(stderr, gettext(
200 "pack: %s.z: write error - "
201 "file unchanged: "), source);
202 perror("");
203 return (0);
204 }
205 ((union FOUR *)outbuff)->lint.lng =
206 ((union FOUR *)&outbuff[BUFSIZ])->lint.lng;
207 outp -= BUFSIZ;
208 outsize += BUFSIZ;
209 }
210 } while (c != END);
211 if (bitsleft < 8)
212 outp++;
213 c = outp-outbuff;
214 if (write(outfile, outbuff, c) != c)
215 goto wrerr;
216 outsize += c;
217 return (1);
218 }
219
220 /* makes a heap out of heap[i],...,heap[n] */
221 void
heapify(int i)222 heapify(int i)
223 {
224 register int k;
225 int lastparent;
226 struct heap heapsubi;
227 hmove(heap[i], heapsubi);
228 lastparent = n/2;
229 while (i <= lastparent) {
230 k = 2*i;
231 if (heap[k].count > heap[k+1].count && k < n)
232 k++;
233 if (heapsubi.count < heap[k].count)
234 break;
235 hmove(heap[k], heap[i]);
236 i = k;
237 }
238 hmove(heapsubi, heap[i]);
239 }
240
241 /* return 1 after successful packing, 0 otherwise */
242 int
packfile(char * source)243 packfile(char *source)
244 {
245 register int c, i, p;
246 long bitsout;
247
248 /* gather frequency statistics */
249 if (input(source) == 0)
250 return (0);
251
252 /* put occurring chars in heap with their counts */
253 diffbytes = -1;
254 count[END] = 1;
255 insize.lint.lng = n = 0;
256 for (i = END; i >= 0; i--) {
257 parent[i] = 0;
258 if (count[i] > 0) {
259 diffbytes++;
260 insize.lint.lng += count[i];
261 heap[++n].count = count[i];
262 heap[n].node = i;
263 }
264 }
265 if (diffbytes == 1) {
266 (void) fprintf(stderr, gettext(
267 "pack: %s: trivial file - file unchanged\n"), source);
268 return (0);
269 }
270 insize.lint.lng >>= 1;
271 for (i = n/2; i >= 1; i--)
272 heapify(i);
273
274 /* build Huffman tree */
275 lastnode = END;
276 while (n > 1) {
277 parent[heap[1].node] = ++lastnode;
278 inc = heap[1].count;
279 hmove(heap[n], heap[1]);
280 n--;
281 heapify(1);
282 parent[heap[1].node] = lastnode;
283 heap[1].node = lastnode;
284 heap[1].count += inc;
285 heapify(1);
286 }
287 parent[lastnode] = 0;
288
289 /* assign lengths to encoding for each character */
290 bitsout = maxlev = 0;
291 for (i = 1; i <= 24; i++)
292 levcount[i] = 0;
293 for (i = 0; i <= END; i++) {
294 c = 0;
295 for (p = parent[i]; p != 0; p = parent[p])
296 c++;
297 levcount[c]++;
298 length[i] = c;
299 if (c > maxlev)
300 maxlev = c;
301 bitsout += c*(count[i]>>1);
302 }
303 if (maxlev > 24) {
304 /* can't occur unless insize.lint.lng >= 2**24 */
305 (void) fprintf(stderr, gettext(
306 "pack: %s: Huffman tree has too many levels - "
307 "file unchanged\n"), source);
308 return (0);
309 }
310
311 /* don't bother if no compression results */
312 outsize = ((bitsout+7)>>3)+6+maxlev+diffbytes;
313 if ((insize.lint.lng+BUFSIZ-1)/BUFSIZ <=
314 (outsize+BUFSIZ-1)/BUFSIZ && !force) {
315 (void) printf(gettext(
316 "pack: %s: no saving - file unchanged\n"), source);
317 return (0);
318 }
319
320 /* compute bit patterns for each character */
321 inc = 1L << 24;
322 inc >>= maxlev;
323 mask.lint.lng = 0;
324 for (i = maxlev; i > 0; i--) {
325 for (c = 0; c <= END; c++)
326 if (length[c] == i) {
327 bits[c] = mask.lint.lng;
328 mask.lint.lng += inc;
329 }
330 mask.lint.lng &= ~inc;
331 inc <<= 1;
332 }
333
334 return (output(source));
335 }
336
337 int
main(int argc,char * argv[])338 main(int argc, char *argv[])
339 {
340 extern int optind;
341 register int i;
342 register char *cp;
343 int k, sep, errflg = 0;
344 int c;
345 int error;
346 int fcount = 0; /* count failures */
347 acl_t *aclp = NULL;
348 char *progname;
349 int sattr_exist = 0;
350 int xattr_exist = 0;
351
352 (void) setlocale(LC_ALL, "");
353 #if !defined(TEXT_DOMAIN) /* Should be defined by cc -D */
354 #define TEXT_DOMAIN "SYS_TEST" /* Use this only if it weren't */
355 #endif
356 (void) textdomain(TEXT_DOMAIN);
357
358 if (progname = strrchr(argv[0], '/'))
359 ++progname;
360 else
361 progname = argv[0];
362
363 while ((c = getopt(argc, argv, "f-/")) != EOF) {
364 if (c == 'f')
365 force++;
366 else if (c == '/')
367 saflg++;
368 else
369 ++errflg;
370 }
371 /*
372 * Check for invalid option. Also check for missing
373 * file operand, ie: "pack" or "pack -".
374 */
375 argc -= optind;
376 argv = &argv[optind];
377 if (errflg || argc < 1 ||
378 (argc == 1 && (argv[0][0] == '-' || argv[0][0] == '/' &&
379 argv[0][1] == '\0'))) {
380 (void) fprintf(stderr, gettext(
381 "usage: pack [-f] [-] [-/] file...\n"));
382 if (argc < 1 ||
383 (argc == 1 && (argv[0][0] == '-' || argv[0][0] == '/') &&
384 argv[0][1] == '\0')) {
385 /*
386 * return 1 for usage error when no file was specified
387 */
388 return (1);
389 }
390 }
391
392 /* loop through the file names */
393 for (k = 0; k < argc; k++) {
394 if (argv[k][0] == '-' && argv[k][1] == '\0') {
395 vflag = 1 - vflag;
396 continue;
397 }
398 fcount++; /* increase failure count - expect the worst */
399 if (errflg) {
400 /*
401 * invalid option; just count the number of files not
402 * packed
403 */
404 continue;
405 }
406 /* remove any .z suffix the user may have added */
407 for (cp = argv[k]; *cp != '\0'; ++cp)
408 ;
409 if (cp[-1] == SUF1 && cp[-2] == SUF0) {
410 *cp-- = '\0'; *cp-- = '\0'; *cp = '\0';
411 }
412 sep = -1; cp = filename;
413 max_name = pathconf(argv[k], _PC_NAME_MAX);
414 if (max_name == -1) {
415 /* pathname invalid or no limit on length of filename */
416 max_name = _POSIX_NAME_MAX;
417 }
418 /* copy argv[k] to filename and count chars in base name */
419 for (i = 0; i < (MAXPATHLEN-3) && (*cp = argv[k][i]); i++)
420 if (*cp++ == '/') sep = i;
421 if ((infile = open(filename, 0)) < 0) {
422 (void) fprintf(stderr, gettext(
423 "pack: %s: cannot open: "), filename);
424 perror("");
425 continue;
426 }
427 if (i >= (MAXPATHLEN-3) || (i-sep) > (max_name - 1)) {
428 (void) fprintf(stderr, gettext(
429 "pack: %s: file name too long\n"), argv[k]);
430 continue;
431 }
432 (void) fstat(infile, &status);
433 if (S_ISDIR(status.st_mode)) {
434 (void) fprintf(stderr, gettext(
435 "pack: %s: cannot pack a directory\n"),
436 argv[k]);
437 goto closein;
438 }
439 if (status.st_size == 0) {
440 (void) fprintf(stderr, gettext(
441 "pack: %s: cannot pack a zero length file\n"),
442 argv[k]);
443 goto closein;
444 }
445 if (status.st_nlink != 1) {
446 (void) fprintf(stderr, gettext(
447 "pack: %s: has links\n"),
448 argv[k]);
449 goto closein;
450 }
451 *cp++ = SUF0; *cp++ = SUF1; *cp = '\0';
452 if (stat(filename, &ostatus) != -1) {
453 (void) fprintf(stderr, gettext(
454 "pack: %s: already exists\n"), filename);
455 goto closein;
456 }
457 if ((outfile = creat(filename, status.st_mode | O_RDONLY))
458 < 0) {
459 (void) fprintf(stderr, gettext(
460 "pack: %s: cannot create: "), filename);
461 perror("");
462 goto closein;
463 }
464
465 error = facl_get(infile, ACL_NO_TRIVIAL, &aclp);
466
467 if (error != 0) {
468 (void) fprintf(stderr, gettext(
469 "pack: %s: cannot retrieve ACL: %s\n"), argv[k],
470 acl_strerror(error));
471 }
472
473 if (packfile(argv[k])) {
474 if (pathconf(argv[k], _PC_XATTR_EXISTS) == 1)
475 xattr_exist = 1;
476 if (saflg && sysattr_support(argv[k],
477 _PC_SATTR_EXISTS) == 1)
478 sattr_exist = 1;
479 if (sattr_exist || xattr_exist) {
480 if (mv_xattrs(progname, argv[k], filename,
481 sattr_exist, 0) != 0) {
482 /* Move attributes back ... */
483 xattr_exist = 0;
484 sattr_exist = 0;
485 if (pathconf(filename,
486 _PC_XATTR_EXISTS) == 1)
487 xattr_exist = 1;
488 if (saflg && sysattr_support(filename,
489 _PC_SATTR_EXISTS) == 1)
490 sattr_exist = 1;
491 if (xattr_exist || sattr_exist) {
492 (void) mv_xattrs(progname,
493 filename, argv[k],
494 sattr_exist, 1);
495 (void) unlink(filename);
496 goto out;
497 }
498 } else {
499 errno = 0;
500 if (unlink(argv[k]) != 0) {
501 (void) fprintf(stderr, gettext(
502 "pack: %s :cannot unlink:"),
503 argv[k]);
504 if (errno == EPERM)
505 perror("No permission");
506 else
507 perror("");
508 }
509 }
510 } else {
511 errno = 0;
512 if (unlink(argv[k]) != 0) {
513 (void) fprintf(stderr, gettext(
514 "pack: %s :cannot unlink"),
515 argv[k]);
516 if (errno == EPERM)
517 perror("No permission");
518 else
519 perror("");
520 }
521 }
522 (void) printf(gettext(
523 "pack: %s: %.1f%% Compression\n"),
524 argv[k],
525 ((double)(-outsize+(insize.lint.lng))/
526 (double)insize.lint.lng)*100);
527 /* output statistics */
528 if (vflag) {
529 (void) printf(gettext(
530 "\tfrom %ld to %ld bytes\n"),
531 insize.lint.lng, outsize);
532 (void) printf(gettext(
533 "\tHuffman tree has %d levels below "
534 "root\n"), maxlev);
535 (void) printf(gettext(
536 "\t%d distinct bytes in input\n"),
537 diffbytes);
538 (void) printf(gettext(
539 "\tdictionary overhead = %ld bytes\n"),
540 dictsize);
541 (void) printf(gettext(
542 "\teffective entropy = %.2f bits/byte\n"),
543 ((double)outsize / (double)insize.lint.lng)
544 * 8);
545 (void) printf(gettext(
546 "\tasymptotic entropy = %.2f bits/byte\n"),
547 ((double)(outsize-dictsize) /
548 (double)insize.lint.lng) * 8);
549 }
550
551 u_times.actime = status.st_atime;
552 u_times.modtime = status.st_mtime;
553 if (utime(filename, &u_times) != 0) {
554 errflg++;
555 (void) fprintf(stderr,
556 gettext(
557 "pack: cannot change times on %s: "),
558 filename);
559 perror("");
560 }
561 if (chmod(filename, status.st_mode) != 0) {
562 errflg++;
563 (void) fprintf(stderr,
564 gettext(
565 "pack: can't change mode to %o on %s: "),
566 status.st_mode, filename);
567 perror("");
568 }
569 (void) chown(filename, status.st_uid, status.st_gid);
570 if (aclp && (facl_set(outfile, aclp) < 0)) {
571 (void) fprintf(stderr, gettext(
572 "pack: %s: failed to set acl entries\n"),
573 filename);
574 perror("");
575 }
576 if (!errflg)
577 fcount--; /* success after all */
578
579 }
580 out:
581 if (aclp) {
582 acl_free(aclp);
583 aclp = NULL;
584 }
585
586 closein: (void) close(outfile);
587 (void) close(infile);
588 }
589 return (fcount);
590 }
591