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 */
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()
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.
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.
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
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.
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
64 #define WINSIZE 32768U // sliding window size
65 #define CHUNK 16384 // file input buffer size
67 // See comments in zran.h.
68 void deflate_index_free(struct deflate_index *index) {
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) {
83 // The list is empty. Create it, starting with eight access points.
84 index = malloc(sizeof(struct deflate_index));
89 index->list = malloc(sizeof(point_t) * index->mode);
90 if (index->list == NULL) {
96 else if (index->have == index->mode) {
97 // The list is full. Make it bigger.
99 point_t *next = realloc(index->list, sizeof(point_t) * index->mode);
101 deflate_index_free(index);
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);
118 memcpy(next->window, window + WINSIZE - left, left);
120 memcpy(next->window + left, window, WINSIZE - left);
122 // Return the index, which may have been newly allocated or destroyed.
126 // Decompression modes. These are the inflateInit2() windowBits parameter.
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)
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
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;
151 if (strm.avail_in < sizeof(buf) && ferror(in)) {
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 :
166 ret = inflateInit2(&strm, mode);
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);
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;
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;
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);
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);
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);
219 if (ret != Z_STREAM_END) {
220 // An error was encountered. Discard the index and return a negative
222 deflate_index_free(index);
223 return ret == Z_NEED_DICT ? Z_DATA_ERROR : ret;
226 // Shrink the index to only the occupied access points and return it.
228 index->length = totout;
229 point_t *list = realloc(index->list, sizeof(point_t) * index->have);
231 // Seems like a realloc() to make something smaller should always work,
233 deflate_index_free(index);
242 // Support zlib versions before 1.2.3 (July 2005), or incomplete zlib clones
243 // that do not have inflatePrime().
245 # define INFLATEPRIME inflatePreface
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
258 *in |= value << k; // write value above the low k bits
261 k = 8 - k; // the number of bits just appended
263 value >>= k; // drop the bits appended
265 k = 8; // now at a byte boundary
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) {
278 if (strm == Z_NULL || bits < 0 || bits > 16)
279 return Z_STREAM_ERROR;
282 value &= (2 << (bits - 1)) - 1;
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
289 const int dynlen = 95; // number of bits in the block
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];
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
299 memcpy(in, dyn, sizeof(dyn));
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);
307 // Append the bits bits from value, which takes us to a byte boundary.
308 append_bits(value, bits, in, &have);
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
318 strm->avail_in = have >> 3;
321 strm->next_out = in; // not used, but can't be NULL
322 return inflate(strm, Z_NO_FLUSH);
326 # define INFLATEPRIME inflatePrime
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;
336 // If nothing to extract, return zero bytes extracted.
337 if (len == 0 || offset < 0 || offset >= index->length)
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)
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);
357 if (point->bits && (ch = getc(in)) == EOF)
358 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR;
360 ret = inflateInit2(&strm, RAW);
364 INFLATEPRIME(&strm, point->bits, ch >> (8 - point->bits));
365 inflateSetDictionary(&strm, point->window, WINSIZE);
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
374 // Discard up to offset uncompressed bytes.
375 strm.avail_out = offset < WINSIZE ? (unsigned)offset : WINSIZE;
376 strm.next_out = discard;
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;
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)) {
392 strm.next_in = input;
394 unsigned got = strm.avail_out;
395 ret = inflate(&strm, Z_NO_FLUSH);
396 got -= strm.avail_out;
398 // Update the appropriate count.
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;
414 // Read and discard the remainder of the gzip trailer.
415 drop -= strm.avail_in;
419 // The input does not have a complete trailer.
420 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR;
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);
429 if (strm.avail_in == 0) {
430 strm.avail_in = fread(input, 1, CHUNK, in);
431 if (strm.avail_in < CHUNK && ferror(in)) {
435 strm.next_in = input;
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);
443 inflateReset2(&strm, RAW);
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);
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;
458 #define SPAN 1048576L // desired distance between access points
459 #define LEN 16384 // number of bytes to extract
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");
472 FILE *in = fopen(argv[1], "rb");
474 fprintf(stderr, "zran: could not open %s for reading\n", argv[1]);
478 // Get optional offset.
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]);
490 struct deflate_index *index = NULL;
491 int len = deflate_index_build(in, SPAN, &index);
496 fprintf(stderr, "zran: out of memory\n");
499 fprintf(stderr, "zran: %s ended prematurely\n", argv[1]);
502 fprintf(stderr, "zran: compressed data error in %s\n", argv[1]);
505 fprintf(stderr, "zran: read error on %s\n", argv[1]);
508 fprintf(stderr, "zran: error %d while building index\n", len);
512 fprintf(stderr, "zran: built index with %d access points\n", len);
514 // Use index by reading some bytes from an arbitrary offset.
515 unsigned char buf[LEN];
517 offset = ((index->length + 1) << 1) / 3;
518 ptrdiff_t got = deflate_index_extract(in, index, offset, buf, LEN);
520 fprintf(stderr, "zran: extraction failed: %s error\n",
521 got == Z_MEM_ERROR ? "out of memory" : "input corrupted");
523 fwrite(buf, 1, got, stdout);
524 fprintf(stderr, "zran: extracted %ld bytes at %lld\n", got, offset);
527 // Clean up and exit.
528 deflate_index_free(index);