1 |
745 |
jeremybenn |
/* 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() */
|
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. */
|
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. */
|
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. */
|
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. */
|
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 |
|
|
}
|