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() */
free_index(struct access * 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. */
addpoint(struct access * index,int bits,off_t in,off_t out,unsigned left,unsigned char * window)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. */
build_index(FILE * in,off_t span,struct access ** built)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. */
extract(FILE * in,struct access * index,off_t offset,unsigned char * buf,int len)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. */
main(int argc,char ** argv)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 }
410