zran.c
1 /* zran.c -- example of zlib/gzip stream indexing and random access 2 * Copyright (C) 2005, 2012 Mark Adler 3 * For conditions of distribution and use, see copyright notice in zlib.h 4 Version 1.1 29 Sep 2012 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 */ 10 11 /* Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary() 12 for random access of a compressed file. A file containing a zlib or gzip 13 stream is provided on the command line. The compressed stream is decoded in 14 its entirety, and an index built with access points about every SPAN bytes 15 in the uncompressed output. The compressed file is left open, and can then 16 be read randomly, having to decompress on the average SPAN/2 uncompressed 17 bytes before getting to the desired block of data. 18 19 An access point can be created at the start of any deflate block, by saving 20 the starting file offset and bit of that block, and the 32K bytes of 21 uncompressed data that precede that block. Also the uncompressed offset of 22 that block is saved to provide a referece for locating a desired starting 23 point in the uncompressed stream. build_index() works by decompressing the 24 input zlib or gzip stream a block at a time, and at the end of each block 25 deciding if enough uncompressed data has gone by to justify the creation of 26 a new access point. If so, that point is saved in a data structure that 27 grows as needed to accommodate the points. 28 29 To use the index, an offset in the uncompressed data is provided, for which 30 the latest access point at or preceding that offset is located in the index. 31 The input file is positioned to the specified location in the index, and if 32 necessary the first few bits of the compressed data is read from the file. 33 inflate is initialized with those bits and the 32K of uncompressed data, and 34 the decompression then proceeds until the desired offset in the file is 35 reached. Then the decompression continues to read the desired uncompressed 36 data from the file. 37 38 Another approach would be to generate the index on demand. In that case, 39 requests for random access reads from the compressed data would try to use 40 the index, but if a read far enough past the end of the index is required, 41 then further index entries would be generated and added. 42 43 There is some fair bit of overhead to starting inflation for the random 44 access, mainly copying the 32K byte dictionary. So if small pieces of the 45 file are being accessed, it would make sense to implement a cache to hold 46 some lookahead and avoid many calls to extract() for small lengths. 47 48 Another way to build an index would be to use inflateCopy(). That would 49 not be constrained to have access points at block boundaries, but requires 50 more memory per access point, and also cannot be saved to file due to the 51 use of pointers in the state. The approach here allows for storage of the 52 index in a file. 53 */ 54 55 #include <stdio.h> 56 #include <stdlib.h> 57 #include <string.h> 58 #include "zlib.h" 59 60 #define local static 61 62 #define SPAN 1048576L /* desired distance between access points */ 63 #define WINSIZE 32768U /* sliding window size */ 64 #define CHUNK 16384 /* file input buffer size */ 65 66 /* access point entry */ 67 struct point { 68 off_t out; /* corresponding offset in uncompressed data */ 69 off_t in; /* offset in input file of first full byte */ 70 int bits; /* number of bits (1-7) from byte at in - 1, or 0 */ 71 unsigned char window[WINSIZE]; /* preceding 32K of uncompressed data */ 72 }; 73 74 /* access point list */ 75 struct access { 76 int have; /* number of list entries filled in */ 77 int size; /* number of list entries allocated */ 78 struct point *list; /* allocated list */ 79 }; 80 81 /* Deallocate an index built by build_index() */ 82 local void free_index(struct access *index) 83 { 84 if (index != NULL) { 85 free(index->list); 86 free(index); 87 } 88 } 89 90 /* Add an entry to the access point list. If out of memory, deallocate the 91 existing list and return NULL. */ 92 local struct access *addpoint(struct access *index, int bits, 93 off_t in, off_t out, unsigned left, unsigned char *window) 94 { 95 struct point *next; 96 97 /* if list is empty, create it (start with eight points) */ 98 if (index == NULL) { 99 index = malloc(sizeof(struct access)); 100 if (index == NULL) return NULL; 101 index->list = malloc(sizeof(struct point) << 3); 102 if (index->list == NULL) { 103 free(index); 104 return NULL; 105 } 106 index->size = 8; 107 index->have = 0; 108 } 109 110 /* if list is full, make it bigger */ 111 else if (index->have == index->size) { 112 index->size <<= 1; 113 next = realloc(index->list, sizeof(struct point) * index->size); 114 if (next == NULL) { 115 free_index(index); 116 return NULL; 117 } 118 index->list = next; 119 } 120 121 /* fill in entry and increment how many we have */ 122 next = index->list + index->have; 123 next->bits = bits; 124 next->in = in; 125 next->out = out; 126 if (left) 127 memcpy(next->window, window + WINSIZE - left, left); 128 if (left < WINSIZE) 129 memcpy(next->window + left, window, WINSIZE - left); 130 index->have++; 131 132 /* return list, possibly reallocated */ 133 return index; 134 } 135 136 /* Make one entire pass through the compressed stream and build an index, with 137 access points about every span bytes of uncompressed output -- span is 138 chosen to balance the speed of random access against the memory requirements 139 of the list, about 32K bytes per access point. Note that data after the end 140 of the first zlib or gzip stream in the file is ignored. build_index() 141 returns the number of access points on success (>= 1), Z_MEM_ERROR for out 142 of memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a 143 file read error. On success, *built points to the resulting index. */ 144 local int build_index(FILE *in, off_t span, struct access **built) 145 { 146 int ret; 147 off_t totin, totout; /* our own total counters to avoid 4GB limit */ 148 off_t last; /* totout value of last access point */ 149 struct access *index; /* access points being generated */ 150 z_stream strm; 151 unsigned char input[CHUNK]; 152 unsigned char window[WINSIZE]; 153 154 /* initialize inflate */ 155 strm.zalloc = Z_NULL; 156 strm.zfree = Z_NULL; 157 strm.opaque = Z_NULL; 158 strm.avail_in = 0; 159 strm.next_in = Z_NULL; 160 ret = inflateInit2(&strm, 47); /* automatic zlib or gzip decoding */ 161 if (ret != Z_OK) 162 return ret; 163 164 /* inflate the input, maintain a sliding window, and build an index -- this 165 also validates the integrity of the compressed data using the check 166 information at the end of the gzip or zlib stream */ 167 totin = totout = last = 0; 168 index = NULL; /* will be allocated by first addpoint() */ 169 strm.avail_out = 0; 170 do { 171 /* get some compressed data from input file */ 172 strm.avail_in = fread(input, 1, CHUNK, in); 173 if (ferror(in)) { 174 ret = Z_ERRNO; 175 goto build_index_error; 176 } 177 if (strm.avail_in == 0) { 178 ret = Z_DATA_ERROR; 179 goto build_index_error; 180 } 181 strm.next_in = input; 182 183 /* process all of that, or until end of stream */ 184 do { 185 /* reset sliding window if necessary */ 186 if (strm.avail_out == 0) { 187 strm.avail_out = WINSIZE; 188 strm.next_out = window; 189 } 190 191 /* inflate until out of input, output, or at end of block -- 192 update the total input and output counters */ 193 totin += strm.avail_in; 194 totout += strm.avail_out; 195 ret = inflate(&strm, Z_BLOCK); /* return at end of block */ 196 totin -= strm.avail_in; 197 totout -= strm.avail_out; 198 if (ret == Z_NEED_DICT) 199 ret = Z_DATA_ERROR; 200 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 201 goto build_index_error; 202 if (ret == Z_STREAM_END) 203 break; 204 205 /* if at end of block, consider adding an index entry (note that if 206 data_type indicates an end-of-block, then all of the 207 uncompressed data from that block has been delivered, and none 208 of the compressed data after that block has been consumed, 209 except for up to seven bits) -- the totout == 0 provides an 210 entry point after the zlib or gzip header, and assures that the 211 index always has at least one access point; we avoid creating an 212 access point after the last block by checking bit 6 of data_type 213 */ 214 if ((strm.data_type & 128) && !(strm.data_type & 64) && 215 (totout == 0 || totout - last > span)) { 216 index = addpoint(index, strm.data_type & 7, totin, 217 totout, strm.avail_out, window); 218 if (index == NULL) { 219 ret = Z_MEM_ERROR; 220 goto build_index_error; 221 } 222 last = totout; 223 } 224 } while (strm.avail_in != 0); 225 } while (ret != Z_STREAM_END); 226 227 /* clean up and return index (release unused entries in list) */ 228 (void)inflateEnd(&strm); 229 index->list = realloc(index->list, sizeof(struct point) * index->have); 230 index->size = index->have; 231 *built = index; 232 return index->size; 233 234 /* return error */ 235 build_index_error: 236 (void)inflateEnd(&strm); 237 if (index != NULL) 238 free_index(index); 239 return ret; 240 } 241 242 /* Use the index to read len bytes from offset into buf, return bytes read or 243 negative for error (Z_DATA_ERROR or Z_MEM_ERROR). If data is requested past 244 the end of the uncompressed data, then extract() will return a value less 245 than len, indicating how much as actually read into buf. This function 246 should not return a data error unless the file was modified since the index 247 was generated. extract() may also return Z_ERRNO if there is an error on 248 reading or seeking the input file. */ 249 local int extract(FILE *in, struct access *index, off_t offset, 250 unsigned char *buf, int len) 251 { 252 int ret, skip; 253 z_stream strm; 254 struct point *here; 255 unsigned char input[CHUNK]; 256 unsigned char discard[WINSIZE]; 257 258 /* proceed only if something reasonable to do */ 259 if (len < 0) 260 return 0; 261 262 /* find where in stream to start */ 263 here = index->list; 264 ret = index->have; 265 while (--ret && here[1].out <= offset) 266 here++; 267 268 /* initialize file and inflate state to start there */ 269 strm.zalloc = Z_NULL; 270 strm.zfree = Z_NULL; 271 strm.opaque = Z_NULL; 272 strm.avail_in = 0; 273 strm.next_in = Z_NULL; 274 ret = inflateInit2(&strm, -15); /* raw inflate */ 275 if (ret != Z_OK) 276 return ret; 277 ret = fseeko(in, here->in - (here->bits ? 1 : 0), SEEK_SET); 278 if (ret == -1) 279 goto extract_ret; 280 if (here->bits) { 281 ret = getc(in); 282 if (ret == -1) { 283 ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR; 284 goto extract_ret; 285 } 286 (void)inflatePrime(&strm, here->bits, ret >> (8 - here->bits)); 287 } 288 (void)inflateSetDictionary(&strm, here->window, WINSIZE); 289 290 /* skip uncompressed bytes until offset reached, then satisfy request */ 291 offset -= here->out; 292 strm.avail_in = 0; 293 skip = 1; /* while skipping to offset */ 294 do { 295 /* define where to put uncompressed data, and how much */ 296 if (offset == 0 && skip) { /* at offset now */ 297 strm.avail_out = len; 298 strm.next_out = buf; 299 skip = 0; /* only do this once */ 300 } 301 if (offset > WINSIZE) { /* skip WINSIZE bytes */ 302 strm.avail_out = WINSIZE; 303 strm.next_out = discard; 304 offset -= WINSIZE; 305 } 306 else if (offset != 0) { /* last skip */ 307 strm.avail_out = (unsigned)offset; 308 strm.next_out = discard; 309 offset = 0; 310 } 311 312 /* uncompress until avail_out filled, or end of stream */ 313 do { 314 if (strm.avail_in == 0) { 315 strm.avail_in = fread(input, 1, CHUNK, in); 316 if (ferror(in)) { 317 ret = Z_ERRNO; 318 goto extract_ret; 319 } 320 if (strm.avail_in == 0) { 321 ret = Z_DATA_ERROR; 322 goto extract_ret; 323 } 324 strm.next_in = input; 325 } 326 ret = inflate(&strm, Z_NO_FLUSH); /* normal inflate */ 327 if (ret == Z_NEED_DICT) 328 ret = Z_DATA_ERROR; 329 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 330 goto extract_ret; 331 if (ret == Z_STREAM_END) 332 break; 333 } while (strm.avail_out != 0); 334 335 /* if reach end of stream, then don't keep trying to get more */ 336 if (ret == Z_STREAM_END) 337 break; 338 339 /* do until offset reached and requested data read, or stream ends */ 340 } while (skip); 341 342 /* compute number of uncompressed bytes read after offset */ 343 ret = skip ? 0 : len - strm.avail_out; 344 345 /* clean up and return bytes read or error */ 346 extract_ret: 347 (void)inflateEnd(&strm); 348 return ret; 349 } 350 351 /* Demonstrate the use of build_index() and extract() by processing the file 352 provided on the command line, and the extracting 16K from about 2/3rds of 353 the way through the uncompressed output, and writing that to stdout. */ 354 int main(int argc, char **argv) 355 { 356 int len; 357 off_t offset; 358 FILE *in; 359 struct access *index = NULL; 360 unsigned char buf[CHUNK]; 361 362 /* open input file */ 363 if (argc != 2) { 364 fprintf(stderr, "usage: zran file.gz\n"); 365 return 1; 366 } 367 in = fopen(argv[1], "rb"); 368 if (in == NULL) { 369 fprintf(stderr, "zran: could not open %s for reading\n", argv[1]); 370 return 1; 371 } 372 373 /* build index */ 374 len = build_index(in, SPAN, &index); 375 if (len < 0) { 376 fclose(in); 377 switch (len) { 378 case Z_MEM_ERROR: 379 fprintf(stderr, "zran: out of memory\n"); 380 break; 381 case Z_DATA_ERROR: 382 fprintf(stderr, "zran: compressed data error in %s\n", argv[1]); 383 break; 384 case Z_ERRNO: 385 fprintf(stderr, "zran: read error on %s\n", argv[1]); 386 break; 387 default: 388 fprintf(stderr, "zran: error %d while building index\n", len); 389 } 390 return 1; 391 } 392 fprintf(stderr, "zran: built index with %d access points\n", len); 393 394 /* use index by reading some bytes from an arbitrary offset */ 395 offset = (index->list[index->have - 1].out << 1) / 3; 396 len = extract(in, index, offset, buf, CHUNK); 397 if (len < 0) 398 fprintf(stderr, "zran: extraction failed: %s error\n", 399 len == Z_MEM_ERROR ? "out of memory" : "input corrupted"); 400 else { 401 fwrite(buf, 1, len, stdout); 402 fprintf(stderr, "zran: extracted %d bytes at %llu\n", len, offset); 403 } 404 405 /* clean up and exit */ 406 free_index(index); 407 fclose(in); 408 return 0; 409 }