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.
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.
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]
22 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
26 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
27 /* All Rights Reserved */
29 #pragma ident "%Z%%M% %I% %E% SMI"
32 * Huffman encoding program
33 * Usage: pack [[ -f ] [ - ] [-/] filename ... ] filename ...
34 * - option: enable/disable listing of statistics
39 #include <sys/isa_defs.h>
40 #include <sys/param.h>
44 #include <libcmdutils.h>
49 #define PACKED 017436 /* <US><RS> - Unlikely value */
53 struct stat status
, ostatus
;
54 static struct utimbuf u_times
;
56 /* union for overlaying a long int with a set of four characters */
58 struct { long int lng
; } lint
;
59 struct { char c0
, c1
, c2
, c3
; } chars
;
62 /* character counters */
71 int force
= 0; /* allow forced packing for consistency in directory */
73 static char filename
[MAXPATHLEN
];
76 int infile
; /* unpacked file */
77 int outfile
; /* packed file */
79 char outbuff
[BUFSIZ
+4];
81 /* variables associated with the tree */
87 /* variables associated with the encoding process */
92 #if defined(_LITTLE_ENDIAN)
93 char *maskshuff
[4] = {&(mask
.chars
.c3
),
97 #elif defined(_BIG_ENDIAN)
98 char *maskshuff
[4] = {&(mask
.chars
.c0
),
103 #error Unknown byte ordering!
112 #define hmove(a, b) {(b).count = (a).count; (b).node = (a).node; }
114 static void heapify(int i
);
116 /* Extended system attribute support */
118 static int saflg
= 0;
121 /* gather character frequency statistics */
122 /* return 1 if successful, 0 otherwise */
127 for (i
= 0; i
< END
; i
++)
129 while ((i
= read(infile
, inbuff
, BUFSIZ
)) > 0)
131 count
[inbuff
[--i
]&0377] += 2;
134 (void) fprintf(stderr
, gettext(
135 "pack: %s: read error - file unchanged: "), source
);
140 /* encode the current file */
141 /* return 1 if successful, 0 otherwise */
147 register char **q
, *outp
;
148 register int bitsleft
;
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);
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
++)
169 dictsize
= outp
-&outbuff
[0];
171 /* output the text */
172 (void) lseek(infile
, 0L, 0);
178 inleft
= read(infile
, inp
= &inbuff
[0], BUFSIZ
);
180 (void) fprintf(stderr
, gettext(
181 "pack: %s: read error - file unchanged: "),
187 c
= (--inleft
< 0) ? END
: (*inp
++ & 0377);
188 mask
.lint
.lng
= bits
[c
]<<bitsleft
;
194 bitsleft
-= length
[c
];
195 while (bitsleft
< 0) {
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
);
207 ((union FOUR
*)outbuff
)->lint
.lng
=
208 ((union FOUR
*)&outbuff
[BUFSIZ
])->lint
.lng
;
216 if (write(outfile
, outbuff
, c
) != c
)
222 /* makes a heap out of heap[i],...,heap[n] */
228 struct heap heapsubi
;
229 hmove(heap
[i
], heapsubi
);
231 while (i
<= lastparent
) {
233 if (heap
[k
].count
> heap
[k
+1].count
&& k
< n
)
235 if (heapsubi
.count
< heap
[k
].count
)
237 hmove(heap
[k
], heap
[i
]);
240 hmove(heapsubi
, heap
[i
]);
243 /* return 1 after successful packing, 0 otherwise */
245 packfile(char *source
)
247 register int c
, i
, p
;
250 /* gather frequency statistics */
251 if (input(source
) == 0)
254 /* put occurring chars in heap with their counts */
257 insize
.lint
.lng
= n
= 0;
258 for (i
= END
; i
>= 0; i
--) {
262 insize
.lint
.lng
+= count
[i
];
263 heap
[++n
].count
= count
[i
];
267 if (diffbytes
== 1) {
268 (void) fprintf(stderr
, gettext(
269 "pack: %s: trivial file - file unchanged\n"), source
);
272 insize
.lint
.lng
>>= 1;
273 for (i
= n
/2; i
>= 1; i
--)
276 /* build Huffman tree */
279 parent
[heap
[1].node
] = ++lastnode
;
281 hmove(heap
[n
], heap
[1]);
284 parent
[heap
[1].node
] = lastnode
;
285 heap
[1].node
= lastnode
;
286 heap
[1].count
+= inc
;
289 parent
[lastnode
] = 0;
291 /* assign lengths to encoding for each character */
292 bitsout
= maxlev
= 0;
293 for (i
= 1; i
<= 24; i
++)
295 for (i
= 0; i
<= END
; i
++) {
297 for (p
= parent
[i
]; p
!= 0; p
= parent
[p
])
303 bitsout
+= c
*(count
[i
]>>1);
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
);
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
);
322 /* compute bit patterns for each character */
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
;
332 mask
.lint
.lng
&= ~inc
;
336 return (output(source
));
340 main(int argc
, char *argv
[])
345 int k
, sep
, errflg
= 0;
348 int fcount
= 0; /* count failures */
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 */
358 (void) textdomain(TEXT_DOMAIN
);
360 if (progname
= strrchr(argv
[0], '/'))
365 while ((c
= getopt(argc
, argv
, "f-/")) != EOF
) {
374 * Check for invalid option. Also check for missing
375 * file operand, ie: "pack" or "pack -".
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"));
385 (argc
== 1 && (argv
[0][0] == '-' || argv
[0][0] == '/') &&
386 argv
[0][1] == '\0')) {
388 * return 1 for usage error when no file was specified
394 /* loop through the file names */
395 for (k
= 0; k
< argc
; k
++) {
396 if (argv
[k
][0] == '-' && argv
[k
][1] == '\0') {
400 fcount
++; /* increase failure count - expect the worst */
403 * invalid option; just count the number of files not
408 /* remove any .z suffix the user may have added */
409 for (cp
= argv
[k
]; *cp
!= '\0'; ++cp
)
411 if (cp
[-1] == SUF1
&& cp
[-2] == SUF0
) {
412 *cp
-- = '\0'; *cp
-- = '\0'; *cp
= '\0';
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
;
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
);
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
]);
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"),
441 if (status
.st_size
== 0) {
442 (void) fprintf(stderr
, gettext(
443 "pack: %s: cannot pack a zero length file\n"),
447 if (status
.st_nlink
!= 1) {
448 (void) fprintf(stderr
, gettext(
449 "pack: %s: has links\n"),
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
);
459 if ((outfile
= creat(filename
, status
.st_mode
| O_RDONLY
))
461 (void) fprintf(stderr
, gettext(
462 "pack: %s: cannot create: "), filename
);
467 error
= facl_get(infile
, ACL_NO_TRIVIAL
, &aclp
);
470 (void) fprintf(stderr
, gettext(
471 "pack: %s: cannot retrieve ACL: %s\n"), argv
[k
],
472 acl_strerror(error
));
475 if (packfile(argv
[k
])) {
476 if (pathconf(argv
[k
], _PC_XATTR_EXISTS
) == 1)
478 if (saflg
&& sysattr_support(argv
[k
],
479 _PC_SATTR_EXISTS
) == 1)
481 if (sattr_exist
|| xattr_exist
) {
482 if (mv_xattrs(progname
, argv
[k
], filename
,
483 sattr_exist
, 0) != 0) {
484 /* Move attributes back ... */
487 if (pathconf(filename
,
488 _PC_XATTR_EXISTS
) == 1)
490 if (saflg
&& sysattr_support(filename
,
491 _PC_SATTR_EXISTS
) == 1)
493 if (xattr_exist
|| sattr_exist
) {
494 (void) mv_xattrs(progname
,
497 (void) unlink(filename
);
502 if (unlink(argv
[k
]) != 0) {
503 (void) fprintf(stderr
, gettext(
504 "pack: %s :cannot unlink:"),
507 perror("No permission");
514 if (unlink(argv
[k
]) != 0) {
515 (void) fprintf(stderr
, gettext(
516 "pack: %s :cannot unlink"),
519 perror("No permission");
524 (void) printf(gettext(
525 "pack: %s: %.1f%% Compression\n"),
527 ((double)(-outsize
+(insize
.lint
.lng
))/
528 (double)insize
.lint
.lng
)*100);
529 /* output statistics */
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 "
537 (void) printf(gettext(
538 "\t%d distinct bytes in input\n"),
540 (void) printf(gettext(
541 "\tdictionary overhead = %ld bytes\n"),
543 (void) printf(gettext(
544 "\teffective entropy = %.2f bits/byte\n"),
545 ((double)outsize
/ (double)insize
.lint
.lng
)
547 (void) printf(gettext(
548 "\tasymptotic entropy = %.2f bits/byte\n"),
549 ((double)(outsize
-dictsize
) /
550 (double)insize
.lint
.lng
) * 8);
553 u_times
.actime
= status
.st_atime
;
554 u_times
.modtime
= status
.st_mtime
;
555 if (utime(filename
, &u_times
) != 0) {
557 (void) fprintf(stderr
,
559 "pack: cannot change times on %s: "),
563 if (chmod(filename
, status
.st_mode
) != 0) {
565 (void) fprintf(stderr
,
567 "pack: can't change mode to %o on %s: "),
568 status
.st_mode
, filename
);
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"),
579 fcount
--; /* success after all */
588 closein
: (void) close(outfile
);
589 (void) close(infile
);