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 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 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 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 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 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