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