1 /* $NetBSD: util.c,v 1.1 2026/06/11 08:29:49 rumble Exp $ */ 2 3 /* 4 * Cribbed from 4.4BSD/Net2 and NetBSD 4.99.42 with some stuff ripped out and 5 * cleaned up. 6 */ 7 8 /*- 9 * Copyright (c) 1991, 1993 10 * The Regents of the University of California. All rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #include <sys/types.h> 38 #include <stdint.h> 39 #include <stdio.h> 40 #include <unistd.h> 41 42 #include "util.h" 43 44 /* 'thecrc' must initially be 0. */ 45 int 46 sum1(int thecrc, u_char *buf, uint32_t len) 47 { 48 /* 49 * 16-bit checksum, rotating right before each addition; 50 * overflow is discarded. 51 */ 52 for (u_char *p = buf; p < &buf[len]; ++p) { 53 if (thecrc & 1) 54 thecrc |= 0x10000; 55 thecrc = ((thecrc >> 1) + *p) & 0xffff; 56 } 57 58 return (thecrc); 59 } 60 61 /* 62 * Copyright (c) 1985, 1986 The Regents of the University of California. 63 * All rights reserved. 64 * 65 * This code is derived from software contributed to Berkeley by 66 * James A. Woods, derived from original work by Spencer Thomas 67 * and Joseph Orost. 68 * 69 * Redistribution and use in source and binary forms, with or without 70 * modification, are permitted provided that the following conditions 71 * are met: 72 * 1. Redistributions of source code must retain the above copyright 73 * notice, this list of conditions and the following disclaimer. 74 * 2. Redistributions in binary form must reproduce the above copyright 75 * notice, this list of conditions and the following disclaimer in the 76 * documentation and/or other materials provided with the distribution. 77 * 3. All advertising materials mentioning features or use of this software 78 * must display the following acknowledgement: 79 * This product includes software developed by the University of 80 * California, Berkeley and its contributors. 81 * 4. Neither the name of the University nor the names of its contributors 82 * may be used to endorse or promote products derived from this software 83 * without specific prior written permission. 84 * 85 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 86 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 87 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 88 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 89 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 90 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 91 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 92 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 93 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 94 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 95 * SUCH DAMAGE. 96 */ 97 98 /* 99 * compress.c - File compression ala IEEE Computer, June 1984. 100 * 101 * Authors: Spencer W. Thomas (decvax!utah-cs!thomas) 102 * Jim McKie (decvax!mcvax!jim) 103 * Steve Davies (decvax!vax135!petsd!peora!srd) 104 * Ken Turkowski (decvax!decwrl!turtlevax!ken) 105 * James A. Woods (decvax!ihnp4!ames!jaw) 106 * Joe Orost (decvax!vax135!petsd!joe) 107 */ 108 109 #include <sys/param.h> 110 #include <sys/stat.h> 111 #include <signal.h> 112 #include <utime.h> 113 #include <errno.h> 114 #include <unistd.h> 115 #include <stdio.h> 116 #include <ctype.h> 117 #include <stdlib.h> 118 #include <string.h> 119 120 #define BITS 16 121 #define HSIZE 69001 /* 95% occupancy */ 122 123 /* 124 * a code_int must be able to hold 2**BITS values of type int, and also -1 125 */ 126 typedef long int code_int; 127 typedef long int count_int; 128 129 static const unsigned char magic_header[] = { "\037\235" }; /* 1F 9D */ 130 131 /* Defines for third byte of header */ 132 #define BIT_MASK 0x1f 133 #define BLOCK_MASK 0x80 134 /* Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is 135 a fourth header byte (for expansion). 136 */ 137 138 #define INIT_BITS 9 /* initial number of bits/code */ 139 140 static int n_bits; /* number of bits/code */ 141 static int maxbits = BITS; /* user settable max # bits/code */ 142 static code_int maxcode; /* maximum code, given n_bits */ 143 static code_int maxmaxcode = 1 << BITS; /* should NEVER generate this code */ 144 #define MAXCODE(n_bits) ((1 << (n_bits)) - 1) 145 146 static count_int htab [HSIZE]; 147 static unsigned short codetab [HSIZE]; 148 149 #define codetabof(i) codetab[i] 150 151 /* 152 * To save much memory, we overlay the table used by compress() with those 153 * used by decompress(). The tab_prefix table is the same size and type 154 * as the codetab. The tab_suffix table needs 2**BITS characters. We 155 * get this from the beginning of htab. The output stack uses the rest 156 * of htab, and contains characters. There is plenty of room for any 157 * possible stack (stack used to be 8000 characters). 158 */ 159 160 #define tab_prefixof(i) codetabof(i) 161 #define tab_suffixof(i) ((unsigned char *)(htab))[i] 162 #define de_stack ((unsigned char *)&tab_suffixof(1<<BITS)) 163 164 static code_int free_ent = 0; /* first unused entry */ 165 166 static code_int getcode(FILE *); 167 168 /* 169 * block compression parameters -- after all codes are used up, 170 * and compression rate changes, start over. 171 */ 172 static int block_compress = BLOCK_MASK; 173 static int clear_flg = 0; 174 175 /* 176 * the next two codes should not be changed lightly, as they must not 177 * lie within the contiguous general code space. 178 */ 179 #define FIRST 257 /* first free entry */ 180 #define CLEAR 256 /* table clear output code */ 181 182 /*- 183 * Algorithm from "A Technique for High Performance Data Compression", 184 * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19. 185 * 186 * Algorithm: 187 * Modified Lempel-Ziv method (LZW). Basically finds common 188 * substrings and replaces them with a variable size code. This is 189 * deterministic, and can be done on the fly. Thus, the decompression 190 * procedure needs no input table, but tracks the way the table was built. 191 */ 192 193 static const unsigned char rmask[9] = { 194 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff 195 }; 196 197 #ifndef BUFFER_SIZE 198 #define BUFFER_SIZE 16384 199 #endif 200 201 /* maximum number of bytes to return from getcode(). if 0, no limit. */ 202 static uint32_t getcode_maxreadbytes; 203 204 /* number of bytes getcode has returned since decompress() was called */ 205 static uint32_t getcode_readbytes; 206 207 /* this shouldn't be here, but it's faster to just do it on the fly */ 208 static int output_checksum; 209 210 /* 211 * Decompress 'input' to 'output'. This routine adapts to the codes in 212 * the file building the "string" table on-the-fly; requiring no table to 213 * be stored in the compressed file. See the definitions above. 214 * 215 * Returns the number of bytes written to 'output'. 216 */ 217 static uint32_t 218 do_decompression(FILE *input, FILE *output) { 219 unsigned char *stackp; 220 int finchar; 221 code_int code, oldcode, incode; 222 int n, nwritten, offset; /* Variables for buffered write */ 223 char buff[BUFFER_SIZE]; /* Buffer for buffered write */ 224 uint32_t byteswritten; 225 226 byteswritten = 0; 227 228 /* 229 * As above, initialize the first 256 entries in the table. 230 */ 231 maxcode = MAXCODE(n_bits = INIT_BITS); 232 for ( code = 255; code >= 0; code-- ) { 233 tab_prefixof(code) = 0; 234 tab_suffixof(code) = (unsigned char)code; 235 } 236 free_ent = ((block_compress) ? FIRST : 256 ); 237 238 finchar = oldcode = getcode(input); 239 if(oldcode == -1) /* EOF already? */ 240 return (0); 241 242 /* first code must be 8 bits = char */ 243 n=0; 244 buff[n++] = (char)finchar; 245 246 stackp = de_stack; 247 248 while ( (code = getcode(input)) > -1 ) { 249 250 if ( (code == CLEAR) && block_compress ) { 251 for ( code = 255; code >= 0; code-- ) 252 tab_prefixof(code) = 0; 253 clear_flg = 1; 254 free_ent = FIRST - 1; 255 if ( (code = getcode(input)) == -1 ) /* O, untimely death! */ 256 break; 257 } 258 incode = code; 259 /* 260 * Special case for KwKwK string. 261 */ 262 if ( code >= free_ent ) { 263 *stackp++ = finchar; 264 code = oldcode; 265 } 266 267 /* 268 * Generate output characters in reverse order 269 */ 270 while ( code >= 256 ) { 271 *stackp++ = tab_suffixof(code); 272 code = tab_prefixof(code); 273 } 274 *stackp++ = finchar = tab_suffixof(code); 275 276 /* 277 * And put them out in forward order 278 */ 279 do { 280 /* 281 * About 60% of the time is spent in the putchar() call 282 * that appeared here. It was originally 283 * putchar ( *--stackp ); 284 * If we buffer the writes ourselves, we can go faster (about 285 * 30%). 286 * 287 * At this point, the next line is the next *big* time 288 * sink in the code. It takes up about 10% of the time. 289 */ 290 buff[n++] = *--stackp; 291 if (n == BUFFER_SIZE) { 292 offset = 0; 293 do { 294 output_checksum = sum1(output_checksum, 295 (u_char *)&buff[offset], n); 296 if (output == NULL) 297 nwritten = n; 298 else 299 nwritten = write(fileno(output), &buff[offset], n); 300 if (nwritten < 0) 301 return (0); 302 offset += nwritten; 303 byteswritten += nwritten; 304 } while ((n -= nwritten) > 0); 305 } 306 } while ( stackp > de_stack ); 307 308 /* 309 * Generate the new entry. 310 */ 311 if ( (code=free_ent) < maxmaxcode ) { 312 tab_prefixof(code) = (unsigned short)oldcode; 313 tab_suffixof(code) = finchar; 314 free_ent = code+1; 315 } 316 /* 317 * Remember previous code. 318 */ 319 oldcode = incode; 320 } 321 /* 322 * Flush the stuff remaining in our buffer... 323 */ 324 offset = 0; 325 while (n > 0) { 326 output_checksum = sum1(output_checksum, (u_char *)&buff[offset], n); 327 if (output == NULL) 328 nwritten = n; 329 else 330 nwritten = write(fileno(output), &buff[offset], n); 331 if (nwritten < 0) 332 return (0); 333 offset += nwritten; 334 n -= nwritten; 335 byteswritten += nwritten; 336 } 337 338 return (byteswritten); 339 } 340 341 /*- 342 * Read one code from the standard input. If EOF, return -1. 343 * Inputs: 344 * FILE stream. 345 * Outputs: 346 * code or -1 is returned. 347 */ 348 static code_int 349 getcode(FILE *input) 350 { 351 code_int code; 352 static int offset = 0, size = 0; 353 static unsigned char buf[BITS]; 354 int r_off, bits; 355 size_t readbytes; 356 unsigned char *bp = buf; 357 358 if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) { 359 /* 360 * If the next entry will be too big for the current code 361 * size, then we must increase the size. This implies reading 362 * a new buffer full, too. 363 * 364 * Bail immediately if we've read in our maximum. 365 */ 366 if (getcode_maxreadbytes != 0 && 367 getcode_readbytes == getcode_maxreadbytes) 368 return (-1); 369 370 371 if ( free_ent > maxcode ) { 372 n_bits++; 373 if ( n_bits == maxbits ) 374 maxcode = maxmaxcode; /* won't get any bigger now */ 375 else 376 maxcode = MAXCODE(n_bits); 377 } 378 if ( clear_flg > 0) { 379 maxcode = MAXCODE (n_bits = INIT_BITS); 380 clear_flg = 0; 381 } 382 383 if (getcode_maxreadbytes != 0 && 384 n_bits > (getcode_maxreadbytes - getcode_readbytes)) 385 readbytes = getcode_maxreadbytes - getcode_readbytes; 386 else 387 readbytes = n_bits; 388 389 size = fread( buf, 1, readbytes, input ); 390 if ( size <= 0 ) 391 return -1; /* end of file */ 392 getcode_readbytes += size; 393 offset = 0; 394 /* Round size down to integral number of codes */ 395 size = (size << 3) - (n_bits - 1); 396 } 397 r_off = offset; 398 bits = n_bits; 399 /* 400 * Get to the first byte. 401 */ 402 bp += (r_off >> 3); 403 r_off &= 7; 404 /* Get first part (low order bits) */ 405 code = (*bp++ >> r_off); 406 bits -= (8 - r_off); 407 r_off = 8 - r_off; /* now, offset into code word */ 408 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ 409 if ( bits >= 8 ) { 410 code |= *bp++ << r_off; 411 r_off += 8; 412 bits -= 8; 413 } 414 /* high order bits. */ 415 code |= (*bp & rmask[bits]) << r_off; 416 offset += n_bits; 417 418 return code; 419 } 420 421 /* 422 * Decompress from stream 'input' into stream 'output', reading at most 423 * 'maxinput' bytes from 'input'. 424 * 425 * The special value 0 for maxinput indicates no limit. 426 * 427 * Returns the number of bytes outputted. 428 */ 429 uint32_t 430 decompress(FILE *input, FILE *output, uint32_t maxinput, int *cksum) 431 { 432 uint32_t ret; 433 434 if (maxinput != 0 && maxinput < 4) 435 return (0); 436 437 if ((getc(input) & 0xff) != magic_header[0] || 438 (getc(input) & 0xff) != magic_header[1]) 439 return (0); 440 441 clear_flg = 0; 442 maxbits = getc(input); 443 block_compress = maxbits & BLOCK_MASK; 444 maxbits &= BIT_MASK; 445 maxmaxcode = 1 << maxbits; 446 if (maxbits > BITS) 447 return (0); 448 449 getcode_maxreadbytes = (maxinput == 0) ? 0 : maxinput - 3; 450 getcode_readbytes = 0; 451 output_checksum = 0; 452 ret = do_decompression(input, output); 453 *cksum = output_checksum; 454 455 return (ret); 456 } 457
Indexes created Mon Oct 26 00:26:21 UTC 2026