1 /* zran.c -- example of deflate stream indexing and random access 2 * Copyright (C) 2005, 2012, 2018, 2023 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 * Version 1.4 13 Apr 2023 Mark Adler */ 5 6 /* Version History: 7 1.0 29 May 2005 First version 8 1.1 29 Sep 2012 Fix memory reallocation error 9 1.2 14 Oct 2018 Handle gzip streams with multiple members 10 Add a header file to facilitate usage in applications 11 1.3 18 Feb 2023 Permit raw deflate streams as well as zlib and gzip 12 Permit crossing gzip member boundaries when extracting 13 Support a size_t size when extracting (was an int) 14 Do a binary search over the index for an access point 15 Expose the access point type to enable save and load 16 1.4 13 Apr 2023 Add a NOPRIME define to not use inflatePrime() 17 */ 18 19 // Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary() 20 // for random access of a compressed file. A file containing a raw deflate 21 // stream is provided on the command line. The compressed stream is decoded in 22 // its entirety, and an index built with access points about every SPAN bytes 23 // in the uncompressed output. The compressed file is left open, and can then 24 // be read randomly, having to decompress on the average SPAN/2 uncompressed 25 // bytes before getting to the desired block of data. 26 // 27 // An access point can be created at the start of any deflate block, by saving 28 // the starting file offset and bit of that block, and the 32K bytes of 29 // uncompressed data that precede that block. Also the uncompressed offset of 30 // that block is saved to provide a reference for locating a desired starting 31 // point in the uncompressed stream. deflate_index_build() decompresses the 32 // input raw deflate stream a block at a time, and at the end of each block 33 // decides if enough uncompressed data has gone by to justify the creation of a 34 // new access point. If so, that point is saved in a data structure that grows 35 // as needed to accommodate the points. 36 // 37 // To use the index, an offset in the uncompressed data is provided, for which 38 // the latest access point at or preceding that offset is located in the index. 39 // The input file is positioned to the specified location in the index, and if 40 // necessary the first few bits of the compressed data is read from the file. 41 // inflate is initialized with those bits and the 32K of uncompressed data, and 42 // decompression then proceeds until the desired offset in the file is reached. 43 // Then decompression continues to read the requested uncompressed data from 44 // the file. 45 // 46 // There is some fair bit of overhead to starting inflation for the random 47 // access, mainly copying the 32K byte dictionary. If small pieces of the file 48 // are being accessed, it would make sense to implement a cache to hold some 49 // lookahead to avoid many calls to deflate_index_extract() for small lengths. 50 // 51 // Another way to build an index would be to use inflateCopy(). That would not 52 // be constrained to have access points at block boundaries, but would require 53 // more memory per access point, and could not be saved to a file due to the 54 // use of pointers in the state. The approach here allows for storage of the 55 // index in a file. 56 57 #include <stdio.h> 58 #include <stdlib.h> 59 #include <string.h> 60 #include <limits.h> 61 #include "zlib.h" 62 #include "zran.h" 63 64 #define WINSIZE 32768U // sliding window size 65 #define CHUNK 16384 // file input buffer size 66 67 // See comments in zran.h. 68 void deflate_index_free(struct deflate_index *index) { 69 if (index != NULL) { 70 free(index->list); 71 free(index); 72 } 73 } 74 75 // Add an access point to the list. If out of memory, deallocate the existing 76 // list and return NULL. index->mode is temporarily the allocated number of 77 // access points, until it is time for deflate_index_build() to return. Then 78 // index->mode is set to the mode of inflation. 79 static struct deflate_index *add_point(struct deflate_index *index, int bits, 80 off_t in, off_t out, unsigned left, 81 unsigned char *window) { 82 if (index == NULL) { 83 // The list is empty. Create it, starting with eight access points. 84 index = malloc(sizeof(struct deflate_index)); 85 if (index == NULL) 86 return NULL; 87 index->have = 0; 88 index->mode = 8; 89 index->list = malloc(sizeof(point_t) * index->mode); 90 if (index->list == NULL) { 91 free(index); 92 return NULL; 93 } 94 } 95 96 else if (index->have == index->mode) { 97 // The list is full. Make it bigger. 98 index->mode <<= 1; 99 point_t *next = realloc(index->list, sizeof(point_t) * index->mode); 100 if (next == NULL) { 101 deflate_index_free(index); 102 return NULL; 103 } 104 index->list = next; 105 } 106 107 // Fill in the access point and increment how many we have. 108 point_t *next = (point_t *)(index->list) + index->have++; 109 if (index->have < 0) { 110 // Overflowed the int! 111 deflate_index_free(index); 112 return NULL; 113 } 114 next->out = out; 115 next->in = in; 116 next->bits = bits; 117 if (left) 118 memcpy(next->window, window + WINSIZE - left, left); 119 if (left < WINSIZE) 120 memcpy(next->window + left, window, WINSIZE - left); 121 122 // Return the index, which may have been newly allocated or destroyed. 123 return index; 124 } 125 126 // Decompression modes. These are the inflateInit2() windowBits parameter. 127 #define RAW -15 128 #define ZLIB 15 129 #define GZIP 31 130 131 // See comments in zran.h. 132 int deflate_index_build(FILE *in, off_t span, struct deflate_index **built) { 133 // Set up inflation state. 134 z_stream strm = {0}; // inflate engine (gets fired up later) 135 unsigned char buf[CHUNK]; // input buffer 136 unsigned char win[WINSIZE] = {0}; // output sliding window 137 off_t totin = 0; // total bytes read from input 138 off_t totout = 0; // total bytes uncompressed 139 int mode = 0; // mode: RAW, ZLIB, or GZIP (0 => not set yet) 140 141 // Decompress from in, generating access points along the way. 142 int ret; // the return value from zlib, or Z_ERRNO 143 off_t last; // last access point uncompressed offset 144 struct deflate_index *index = NULL; // list of access points 145 do { 146 // Assure available input, at least until reaching EOF. 147 if (strm.avail_in == 0) { 148 strm.avail_in = fread(buf, 1, sizeof(buf), in); 149 totin += strm.avail_in; 150 strm.next_in = buf; 151 if (strm.avail_in < sizeof(buf) && ferror(in)) { 152 ret = Z_ERRNO; 153 break; 154 } 155 156 if (mode == 0) { 157 // At the start of the input -- determine the type. Assume raw 158 // if it is neither zlib nor gzip. This could in theory result 159 // in a false positive for zlib, but in practice the fill bits 160 // after a stored block are always zeros, so a raw stream won't 161 // start with an 8 in the low nybble. 162 mode = strm.avail_in == 0 ? RAW : // empty -- will fail 163 (strm.next_in[0] & 0xf) == 8 ? ZLIB : 164 strm.next_in[0] == 0x1f ? GZIP : 165 /* else */ RAW; 166 ret = inflateInit2(&strm, mode); 167 if (ret != Z_OK) 168 break; 169 } 170 } 171 172 // Assure available output. This rotates the output through, for use as 173 // a sliding window on the uncompressed data. 174 if (strm.avail_out == 0) { 175 strm.avail_out = sizeof(win); 176 strm.next_out = win; 177 } 178 179 if (mode == RAW && index == NULL) 180 // We skip the inflate() call at the start of raw deflate data in 181 // order generate an access point there. Set data_type to imitate 182 // the end of a header. 183 strm.data_type = 0x80; 184 else { 185 // Inflate and update the number of uncompressed bytes. 186 unsigned before = strm.avail_out; 187 ret = inflate(&strm, Z_BLOCK); 188 totout += before - strm.avail_out; 189 } 190 191 if ((strm.data_type & 0xc0) == 0x80 && 192 (index == NULL || totout - last >= span)) { 193 // We are at the end of a header or a non-last deflate block, so we 194 // can add an access point here. Furthermore, we are either at the 195 // very start for the first access point, or there has been span or 196 // more uncompressed bytes since the last access point, so we want 197 // to add an access point here. 198 index = add_point(index, strm.data_type & 7, totin - strm.avail_in, 199 totout, strm.avail_out, win); 200 if (index == NULL) { 201 ret = Z_MEM_ERROR; 202 break; 203 } 204 last = totout; 205 } 206 207 if (ret == Z_STREAM_END && mode == GZIP && 208 (strm.avail_in || ungetc(getc(in), in) != EOF)) 209 // There is more input after the end of a gzip member. Reset the 210 // inflate state to read another gzip member. On success, this will 211 // set ret to Z_OK to continue decompressing. 212 ret = inflateReset2(&strm, GZIP); 213 214 // Keep going until Z_STREAM_END or error. If the compressed data ends 215 // prematurely without a file read error, Z_BUF_ERROR is returned. 216 } while (ret == Z_OK); 217 inflateEnd(&strm); 218 219 if (ret != Z_STREAM_END) { 220 // An error was encountered. Discard the index and return a negative 221 // error code. 222 deflate_index_free(index); 223 return ret == Z_NEED_DICT ? Z_DATA_ERROR : ret; 224 } 225 226 // Shrink the index to only the occupied access points and return it. 227 index->mode = mode; 228 index->length = totout; 229 point_t *list = realloc(index->list, sizeof(point_t) * index->have); 230 if (list == NULL) { 231 // Seems like a realloc() to make something smaller should always work, 232 // but just in case. 233 deflate_index_free(index); 234 return Z_MEM_ERROR; 235 } 236 index->list = list; 237 *built = index; 238 return index->have; 239 } 240 241 #ifdef NOPRIME 242 // Support zlib versions before 1.2.3 (July 2005), or incomplete zlib clones 243 // that do not have inflatePrime(). 244 245 # define INFLATEPRIME inflatePreface 246 247 // Append the low bits bits of value to in[] at bit position *have, updating 248 // *have. value must be zero above its low bits bits. bits must be positive. 249 // This assumes that any bits above the *have bits in the last byte are zeros. 250 // That assumption is preserved on return, as any bits above *have + bits in 251 // the last byte written will be set to zeros. 252 static inline void append_bits(unsigned value, int bits, 253 unsigned char *in, int *have) { 254 in += *have >> 3; // where the first bits from value will go 255 int k = *have & 7; // the number of bits already there 256 *have += bits; 257 if (k) 258 *in |= value << k; // write value above the low k bits 259 else 260 *in = value; 261 k = 8 - k; // the number of bits just appended 262 while (bits > k) { 263 value >>= k; // drop the bits appended 264 bits -= k; 265 k = 8; // now at a byte boundary 266 *++in = value; 267 } 268 } 269 270 // Insert enough bits in the form of empty deflate blocks in front of the 271 // low bits bits of value, in order to bring the sequence to a byte boundary. 272 // Then feed that to inflate(). This does what inflatePrime() does, except that 273 // a negative value of bits is not supported. bits must be in 0..16. If the 274 // arguments are invalid, Z_STREAM_ERROR is returned. Otherwise the return 275 // value from inflate() is returned. 276 static int inflatePreface(z_stream *strm, int bits, int value) { 277 // Check input. 278 if (strm == Z_NULL || bits < 0 || bits > 16) 279 return Z_STREAM_ERROR; 280 if (bits == 0) 281 return Z_OK; 282 value &= (2 << (bits - 1)) - 1; 283 284 // An empty dynamic block with an odd number of bits (95). The high bit of 285 // the last byte is unused. 286 static const unsigned char dyn[] = { 287 4, 0xe0, 0x81, 8, 0, 0, 0, 0, 0x20, 0xa8, 0xab, 0x1f 288 }; 289 const int dynlen = 95; // number of bits in the block 290 291 // Build an input buffer for inflate that is a multiple of eight bits in 292 // length, and that ends with the low bits bits of value. 293 unsigned char in[(dynlen + 3 * 10 + 16 + 7) / 8]; 294 int have = 0; 295 if (bits & 1) { 296 // Insert an empty dynamic block to get to an odd number of bits, so 297 // when bits bits from value are appended, we are at an even number of 298 // bits. 299 memcpy(in, dyn, sizeof(dyn)); 300 have = dynlen; 301 } 302 while ((have + bits) & 7) 303 // Insert empty fixed blocks until appending bits bits would put us on 304 // a byte boundary. This will insert at most three fixed blocks. 305 append_bits(2, 10, in, &have); 306 307 // Append the bits bits from value, which takes us to a byte boundary. 308 append_bits(value, bits, in, &have); 309 310 // Deliver the input to inflate(). There is no output space provided, but 311 // inflate() can't get stuck waiting on output not ingesting all of the 312 // provided input. The reason is that there will be at most 16 bits of 313 // input from value after the empty deflate blocks (which themselves 314 // generate no output). At least ten bits are needed to generate the first 315 // output byte from a fixed block. The last two bytes of the buffer have to 316 // be ingested in order to get ten bits, which is the most that value can 317 // occupy. 318 strm->avail_in = have >> 3; 319 strm->next_in = in; 320 strm->avail_out = 0; 321 strm->next_out = in; // not used, but can't be NULL 322 return inflate(strm, Z_NO_FLUSH); 323 } 324 325 #else 326 # define INFLATEPRIME inflatePrime 327 #endif 328 329 // See comments in zran.h. 330 ptrdiff_t deflate_index_extract(FILE *in, struct deflate_index *index, 331 off_t offset, unsigned char *buf, size_t len) { 332 // Do a quick sanity check on the index. 333 if (index == NULL || index->have < 1 || index->list[0].out != 0) 334 return Z_STREAM_ERROR; 335 336 // If nothing to extract, return zero bytes extracted. 337 if (len == 0 || offset < 0 || offset >= index->length) 338 return 0; 339 340 // Find the access point closest to but not after offset. 341 int lo = -1, hi = index->have; 342 point_t *point = index->list; 343 while (hi - lo > 1) { 344 int mid = (lo + hi) >> 1; 345 if (offset < point[mid].out) 346 hi = mid; 347 else 348 lo = mid; 349 } 350 point += lo; 351 352 // Initialize the input file and prime the inflate engine to start there. 353 int ret = fseeko(in, point->in - (point->bits ? 1 : 0), SEEK_SET); 354 if (ret == -1) 355 return Z_ERRNO; 356 int ch = 0; 357 if (point->bits && (ch = getc(in)) == EOF) 358 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR; 359 z_stream strm = {0}; 360 ret = inflateInit2(&strm, RAW); 361 if (ret != Z_OK) 362 return ret; 363 if (point->bits) 364 INFLATEPRIME(&strm, point->bits, ch >> (8 - point->bits)); 365 inflateSetDictionary(&strm, point->window, WINSIZE); 366 367 // Skip uncompressed bytes until offset reached, then satisfy request. 368 unsigned char input[CHUNK]; 369 unsigned char discard[WINSIZE]; 370 offset -= point->out; // number of bytes to skip to get to offset 371 size_t left = len; // number of bytes left to read after offset 372 do { 373 if (offset) { 374 // Discard up to offset uncompressed bytes. 375 strm.avail_out = offset < WINSIZE ? (unsigned)offset : WINSIZE; 376 strm.next_out = discard; 377 } 378 else { 379 // Uncompress up to left bytes into buf. 380 strm.avail_out = left < UINT_MAX ? (unsigned)left : UINT_MAX; 381 strm.next_out = buf + len - left; 382 } 383 384 // Uncompress, setting got to the number of bytes uncompressed. 385 if (strm.avail_in == 0) { 386 // Assure available input. 387 strm.avail_in = fread(input, 1, CHUNK, in); 388 if (strm.avail_in < CHUNK && ferror(in)) { 389 ret = Z_ERRNO; 390 break; 391 } 392 strm.next_in = input; 393 } 394 unsigned got = strm.avail_out; 395 ret = inflate(&strm, Z_NO_FLUSH); 396 got -= strm.avail_out; 397 398 // Update the appropriate count. 399 if (offset) 400 offset -= got; 401 else 402 left -= got; 403 404 // If we're at the end of a gzip member and there's more to read, 405 // continue to the next gzip member. 406 if (ret == Z_STREAM_END && index->mode == GZIP) { 407 // Discard the gzip trailer. 408 unsigned drop = 8; // length of gzip trailer 409 if (strm.avail_in >= drop) { 410 strm.avail_in -= drop; 411 strm.next_in += drop; 412 } 413 else { 414 // Read and discard the remainder of the gzip trailer. 415 drop -= strm.avail_in; 416 strm.avail_in = 0; 417 do { 418 if (getc(in) == EOF) 419 // The input does not have a complete trailer. 420 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR; 421 } while (--drop); 422 } 423 424 if (strm.avail_in || ungetc(getc(in), in) != EOF) { 425 // There's more after the gzip trailer. Use inflate to skip the 426 // gzip header and resume the raw inflate there. 427 inflateReset2(&strm, GZIP); 428 do { 429 if (strm.avail_in == 0) { 430 strm.avail_in = fread(input, 1, CHUNK, in); 431 if (strm.avail_in < CHUNK && ferror(in)) { 432 ret = Z_ERRNO; 433 break; 434 } 435 strm.next_in = input; 436 } 437 strm.avail_out = WINSIZE; 438 strm.next_out = discard; 439 ret = inflate(&strm, Z_BLOCK); // stop at end of header 440 } while (ret == Z_OK && (strm.data_type & 0x80) == 0); 441 if (ret != Z_OK) 442 break; 443 inflateReset2(&strm, RAW); 444 } 445 } 446 447 // Continue until we have the requested data, the deflate data has 448 // ended, or an error is encountered. 449 } while (ret == Z_OK && left); 450 inflateEnd(&strm); 451 452 // Return the number of uncompressed bytes read into buf, or the error. 453 return ret == Z_OK || ret == Z_STREAM_END ? len - left : ret; 454 } 455 456 #ifdef TEST 457 458 #define SPAN 1048576L // desired distance between access points 459 #define LEN 16384 // number of bytes to extract 460 461 // Demonstrate the use of deflate_index_build() and deflate_index_extract() by 462 // processing the file provided on the command line, and extracting LEN bytes 463 // from 2/3rds of the way through the uncompressed output, writing that to 464 // stdout. An offset can be provided as the second argument, in which case the 465 // data is extracted from there instead. 466 int main(int argc, char **argv) { 467 // Open the input file. 468 if (argc < 2 || argc > 3) { 469 fprintf(stderr, "usage: zran file.raw [offset]\n"); 470 return 1; 471 } 472 FILE *in = fopen(argv[1], "rb"); 473 if (in == NULL) { 474 fprintf(stderr, "zran: could not open %s for reading\n", argv[1]); 475 return 1; 476 } 477 478 // Get optional offset. 479 off_t offset = -1; 480 if (argc == 3) { 481 char *end; 482 offset = strtoll(argv[2], &end, 10); 483 if (*end || offset < 0) { 484 fprintf(stderr, "zran: %s is not a valid offset\n", argv[2]); 485 return 1; 486 } 487 } 488 489 // Build index. 490 struct deflate_index *index = NULL; 491 int len = deflate_index_build(in, SPAN, &index); 492 if (len < 0) { 493 fclose(in); 494 switch (len) { 495 case Z_MEM_ERROR: 496 fprintf(stderr, "zran: out of memory\n"); 497 break; 498 case Z_BUF_ERROR: 499 fprintf(stderr, "zran: %s ended prematurely\n", argv[1]); 500 break; 501 case Z_DATA_ERROR: 502 fprintf(stderr, "zran: compressed data error in %s\n", argv[1]); 503 break; 504 case Z_ERRNO: 505 fprintf(stderr, "zran: read error on %s\n", argv[1]); 506 break; 507 default: 508 fprintf(stderr, "zran: error %d while building index\n", len); 509 } 510 return 1; 511 } 512 fprintf(stderr, "zran: built index with %d access points\n", len); 513 514 // Use index by reading some bytes from an arbitrary offset. 515 unsigned char buf[LEN]; 516 if (offset == -1) 517 offset = ((index->length + 1) << 1) / 3; 518 ptrdiff_t got = deflate_index_extract(in, index, offset, buf, LEN); 519 if (got < 0) 520 fprintf(stderr, "zran: extraction failed: %s error\n", 521 got == Z_MEM_ERROR ? "out of memory" : "input corrupted"); 522 else { 523 fwrite(buf, 1, got, stdout); 524 fprintf(stderr, "zran: extracted %ld bytes at %lld\n", got, offset); 525 } 526 527 // Clean up and exit. 528 deflate_index_free(index); 529 fclose(in); 530 return 0; 531 } 532 533 #endif 534