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