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