aboutsummaryrefslogtreecommitdiff
path: root/examples
diff options
context:
space:
mode:
Diffstat (limited to 'examples')
-rw-r--r--examples/zran.c651
-rw-r--r--examples/zran.h69
2 files changed, 348 insertions, 372 deletions
diff --git a/examples/zran.c b/examples/zran.c
index 879c47c..1ffba7f 100644
--- a/examples/zran.c
+++ b/examples/zran.c
@@ -1,114 +1,101 @@
1/* zran.c -- example of zlib/gzip stream indexing and random access 1/* zran.c -- example of deflate stream indexing and random access
2 * Copyright (C) 2005, 2012, 2018 Mark Adler 2 * Copyright (C) 2005, 2012, 2018, 2023 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 * Version 1.2 14 Oct 2018 Mark Adler */ 4 * Version 1.3 18 Feb 2023 Mark Adler */
5 5
6/* Version History: 6/* Version History:
7 1.0 29 May 2005 First version 7 1.0 29 May 2005 First version
8 1.1 29 Sep 2012 Fix memory reallocation error 8 1.1 29 Sep 2012 Fix memory reallocation error
9 1.2 14 Oct 2018 Handle gzip streams with multiple members 9 1.2 14 Oct 2018 Handle gzip streams with multiple members
10 Add a header file to facilitate usage in applications 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
11 */ 16 */
12 17
13/* Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary() 18// Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary()
14 for random access of a compressed file. A file containing a zlib or gzip 19// for random access of a compressed file. A file containing a raw deflate
15 stream is provided on the command line. The compressed stream is decoded in 20// stream is provided on the command line. The compressed stream is decoded in
16 its entirety, and an index built with access points about every SPAN bytes 21// its entirety, and an index built with access points about every SPAN bytes
17 in the uncompressed output. The compressed file is left open, and can then 22// in the uncompressed output. The compressed file is left open, and can then
18 be read randomly, having to decompress on the average SPAN/2 uncompressed 23// be read randomly, having to decompress on the average SPAN/2 uncompressed
19 bytes before getting to the desired block of data. 24// bytes before getting to the desired block of data.
20 25//
21 An access point can be created at the start of any deflate block, by saving 26// An access point can be created at the start of any deflate block, by saving
22 the starting file offset and bit of that block, and the 32K bytes of 27// the starting file offset and bit of that block, and the 32K bytes of
23 uncompressed data that precede that block. Also the uncompressed offset of 28// uncompressed data that precede that block. Also the uncompressed offset of
24 that block is saved to provide a reference for locating a desired starting 29// that block is saved to provide a reference for locating a desired starting
25 point in the uncompressed stream. deflate_index_build() works by 30// point in the uncompressed stream. deflate_index_build() decompresses the
26 decompressing the input zlib or gzip stream a block at a time, and at the 31// input raw deflate stream a block at a time, and at the end of each block
27 end of each block deciding if enough uncompressed data has gone by to 32// decides if enough uncompressed data has gone by to justify the creation of a
28 justify the creation of a new access point. If so, that point is saved in a 33// new access point. If so, that point is saved in a data structure that grows
29 data structure that grows as needed to accommodate the points. 34// as needed to accommodate the points.
30 35//
31 To use the index, an offset in the uncompressed data is provided, for which 36// To use the index, an offset in the uncompressed data is provided, for which
32 the latest access point at or preceding that offset is located in the index. 37// the latest access point at or preceding that offset is located in the index.
33 The input file is positioned to the specified location in the index, and if 38// The input file is positioned to the specified location in the index, and if
34 necessary the first few bits of the compressed data is read from the file. 39// necessary the first few bits of the compressed data is read from the file.
35 inflate is initialized with those bits and the 32K of uncompressed data, and 40// inflate is initialized with those bits and the 32K of uncompressed data, and
36 the decompression then proceeds until the desired offset in the file is 41// decompression then proceeds until the desired offset in the file is reached.
37 reached. Then the decompression continues to read the desired uncompressed 42// Then decompression continues to read the requested uncompressed data from
38 data from the file. 43// the file.
39 44//
40 Another approach would be to generate the index on demand. In that case, 45// There is some fair bit of overhead to starting inflation for the random
41 requests for random access reads from the compressed data would try to use 46// access, mainly copying the 32K byte dictionary. If small pieces of the file
42 the index, but if a read far enough past the end of the index is required, 47// are being accessed, it would make sense to implement a cache to hold some
43 then further index entries would be generated and added. 48// lookahead to avoid many calls to deflate_index_extract() for small lengths.
44 49//
45 There is some fair bit of overhead to starting inflation for the random 50// Another way to build an index would be to use inflateCopy(). That would not
46 access, mainly copying the 32K byte dictionary. So if small pieces of the 51// be constrained to have access points at block boundaries, but would require
47 file are being accessed, it would make sense to implement a cache to hold 52// more memory per access point, and could not be saved to a file due to the
48 some lookahead and avoid many calls to deflate_index_extract() for small 53// use of pointers in the state. The approach here allows for storage of the
49 lengths. 54// index in a file.
50
51 Another way to build an index would be to use inflateCopy(). That would
52 not be constrained to have access points at block boundaries, but requires
53 more memory per access point, and also cannot be saved to file due to the
54 use of pointers in the state. The approach here allows for storage of the
55 index in a file.
56 */
57 55
58#include <stdio.h> 56#include <stdio.h>
59#include <stdlib.h> 57#include <stdlib.h>
60#include <string.h> 58#include <string.h>
59#include <limits.h>
61#include "zlib.h" 60#include "zlib.h"
62#include "zran.h" 61#include "zran.h"
63 62
64#define WINSIZE 32768U /* sliding window size */ 63#define WINSIZE 32768U // sliding window size
65#define CHUNK 16384 /* file input buffer size */ 64#define CHUNK 16384 // file input buffer size
66
67/* Access point entry. */
68struct point {
69 off_t out; /* corresponding offset in uncompressed data */
70 off_t in; /* offset in input file of first full byte */
71 int bits; /* number of bits (1-7) from byte at in-1, or 0 */
72 unsigned char window[WINSIZE]; /* preceding 32K of uncompressed data */
73};
74 65
75/* See comments in zran.h. */ 66// See comments in zran.h.
76void deflate_index_free(struct deflate_index *index) 67void deflate_index_free(struct deflate_index *index) {
77{
78 if (index != NULL) { 68 if (index != NULL) {
79 free(index->list); 69 free(index->list);
80 free(index); 70 free(index);
81 } 71 }
82} 72}
83 73
84/* Add an entry to the access point list. If out of memory, deallocate the 74// Add an access point to the list. If out of memory, deallocate the existing
85 existing list and return NULL. index->gzip is the allocated size of the 75// list and return NULL. index->mode is temporarily the allocated number of
86 index in point entries, until it is time for deflate_index_build() to 76// access points, until it is time for deflate_index_build() to return. Then
87 return, at which point gzip is set to indicate a gzip file or not. 77// index->mode is set to the mode of inflation.
88 */ 78static struct deflate_index *add_point(struct deflate_index *index, int bits,
89static struct deflate_index *addpoint(struct deflate_index *index, int bits, 79 off_t in, off_t out, unsigned left,
90 off_t in, off_t out, unsigned left, 80 unsigned char *window) {
91 unsigned char *window)
92{
93 struct point *next;
94
95 /* if list is empty, create it (start with eight points) */
96 if (index == NULL) { 81 if (index == NULL) {
82 // The list is empty. Create it, starting with eight access points.
97 index = malloc(sizeof(struct deflate_index)); 83 index = malloc(sizeof(struct deflate_index));
98 if (index == NULL) return NULL; 84 if (index == NULL)
99 index->list = malloc(sizeof(struct point) << 3); 85 return NULL;
86 index->have = 0;
87 index->mode = 8;
88 index->list = malloc(sizeof(point_t) * index->mode);
100 if (index->list == NULL) { 89 if (index->list == NULL) {
101 free(index); 90 free(index);
102 return NULL; 91 return NULL;
103 } 92 }
104 index->gzip = 8;
105 index->have = 0;
106 } 93 }
107 94
108 /* if list is full, make it bigger */ 95 else if (index->have == index->mode) {
109 else if (index->have == index->gzip) { 96 // The list is full. Make it bigger.
110 index->gzip <<= 1; 97 index->mode <<= 1;
111 next = realloc(index->list, sizeof(struct point) * index->gzip); 98 point_t *next = realloc(index->list, sizeof(point_t) * index->mode);
112 if (next == NULL) { 99 if (next == NULL) {
113 deflate_index_free(index); 100 deflate_index_free(index);
114 return NULL; 101 return NULL;
@@ -116,318 +103,291 @@ static struct deflate_index *addpoint(struct deflate_index *index, int bits,
116 index->list = next; 103 index->list = next;
117 } 104 }
118 105
119 /* fill in entry and increment how many we have */ 106 // Fill in the access point and increment how many we have.
120 next = (struct point *)(index->list) + index->have; 107 point_t *next = (point_t *)(index->list) + index->have++;
121 next->bits = bits; 108 if (index->have < 0) {
122 next->in = in; 109 // Overflowed the int!
110 deflate_index_free(index);
111 return NULL;
112 }
123 next->out = out; 113 next->out = out;
114 next->in = in;
115 next->bits = bits;
124 if (left) 116 if (left)
125 memcpy(next->window, window + WINSIZE - left, left); 117 memcpy(next->window, window + WINSIZE - left, left);
126 if (left < WINSIZE) 118 if (left < WINSIZE)
127 memcpy(next->window + left, window, WINSIZE - left); 119 memcpy(next->window + left, window, WINSIZE - left);
128 index->have++;
129 120
130 /* return list, possibly reallocated */ 121 // Return the index, which may have been newly allocated or destroyed.
131 return index; 122 return index;
132} 123}
133 124
134/* See comments in zran.h. */ 125// Decompression modes. These are the inflateInit2() windowBits parameter.
135int deflate_index_build(FILE *in, off_t span, struct deflate_index **built) 126#define RAW -15
136{ 127#define ZLIB 15
137 int ret; 128#define GZIP 31
138 int gzip = 0; /* true if reading a gzip file */ 129
139 off_t totin, totout; /* our own total counters to avoid 4GB limit */ 130// See comments in zran.h.
140 off_t last; /* totout value of last access point */ 131int deflate_index_build(FILE *in, off_t span, struct deflate_index **built) {
141 struct deflate_index *index; /* access points being generated */ 132 // Set up inflation state.
142 z_stream strm; 133 z_stream strm = {0}; // inflate engine (gets fired up later)
143 unsigned char input[CHUNK]; 134 unsigned char buf[CHUNK]; // input buffer
144 unsigned char window[WINSIZE]; 135 unsigned char win[WINSIZE] = {0}; // output sliding window
145 136 off_t totin = 0; // total bytes read from input
146 /* initialize inflate */ 137 off_t totout = 0; // total bytes uncompressed
147 strm.zalloc = Z_NULL; 138 int mode = 0; // mode: RAW, ZLIB, or GZIP (0 => not set yet)
148 strm.zfree = Z_NULL; 139
149 strm.opaque = Z_NULL; 140 // Decompress from in, generating access points along the way.
150 strm.avail_in = 0; 141 int ret; // the return value from zlib, or Z_ERRNO
151 strm.next_in = Z_NULL; 142 off_t last; // last access point uncompressed offset
152 ret = inflateInit2(&strm, 47); /* automatic zlib or gzip decoding */ 143 struct deflate_index *index = NULL; // list of access points
153 if (ret != Z_OK)
154 return ret;
155
156 /* inflate the input, maintain a sliding window, and build an index -- this
157 also validates the integrity of the compressed data using the check
158 information in the gzip or zlib stream */
159 totin = totout = last = 0;
160 index = NULL; /* will be allocated by first addpoint() */
161 strm.avail_out = 0;
162 do { 144 do {
163 /* get some compressed data from input file */ 145 // Assure available input, at least until reaching EOF.
164 strm.avail_in = fread(input, 1, CHUNK, in);
165 if (ferror(in)) {
166 ret = Z_ERRNO;
167 goto deflate_index_build_error;
168 }
169 if (strm.avail_in == 0) { 146 if (strm.avail_in == 0) {
170 ret = Z_DATA_ERROR; 147 strm.avail_in = fread(buf, 1, sizeof(buf), in);
171 goto deflate_index_build_error;
172 }
173 strm.next_in = input;
174
175 /* check for a gzip stream */
176 if (totin == 0 && strm.avail_in >= 3 &&
177 input[0] == 31 && input[1] == 139 && input[2] == 8)
178 gzip = 1;
179
180 /* process all of that, or until end of stream */
181 do {
182 /* reset sliding window if necessary */
183 if (strm.avail_out == 0) {
184 strm.avail_out = WINSIZE;
185 strm.next_out = window;
186 }
187
188 /* inflate until out of input, output, or at end of block --
189 update the total input and output counters */
190 totin += strm.avail_in; 148 totin += strm.avail_in;
191 totout += strm.avail_out; 149 strm.next_in = buf;
192 ret = inflate(&strm, Z_BLOCK); /* return at end of block */ 150 if (strm.avail_in < sizeof(buf) && ferror(in)) {
193 totin -= strm.avail_in; 151 ret = Z_ERRNO;
194 totout -= strm.avail_out;
195 if (ret == Z_NEED_DICT)
196 ret = Z_DATA_ERROR;
197 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR)
198 goto deflate_index_build_error;
199 if (ret == Z_STREAM_END) {
200 if (gzip &&
201 (strm.avail_in || ungetc(getc(in), in) != EOF)) {
202 ret = inflateReset(&strm);
203 if (ret != Z_OK)
204 goto deflate_index_build_error;
205 continue;
206 }
207 break; 152 break;
208 } 153 }
209 154
210 /* if at end of block, consider adding an index entry (note that if 155 if (mode == 0) {
211 data_type indicates an end-of-block, then all of the 156 // At the start of the input -- determine the type. Assume raw
212 uncompressed data from that block has been delivered, and none 157 // if it is neither zlib nor gzip. This could in theory result
213 of the compressed data after that block has been consumed, 158 // in a false positive for zlib, but in practice the fill bits
214 except for up to seven bits) -- the totout == 0 provides an 159 // after a stored block are always zeros, so a raw stream won't
215 entry point after the zlib or gzip header, and assures that the 160 // start with an 8 in the low nybble.
216 index always has at least one access point; we avoid creating an 161 mode = strm.avail_in == 0 ? RAW : // empty -- will fail
217 access point after the last block by checking bit 6 of data_type 162 (strm.next_in[0] & 0xf) == 8 ? ZLIB :
218 */ 163 strm.next_in[0] == 0x1f ? GZIP :
219 if ((strm.data_type & 128) && !(strm.data_type & 64) && 164 /* else */ RAW;
220 (totout == 0 || totout - last > span)) { 165 ret = inflateInit2(&strm, mode);
221 index = addpoint(index, strm.data_type & 7, totin, 166 if (ret != Z_OK)
222 totout, strm.avail_out, window); 167 break;
223 if (index == NULL) { 168 }
224 ret = Z_MEM_ERROR; 169 }
225 goto deflate_index_build_error; 170
226 } 171 // Assure available output. This rotates the output through, for use as
227 last = totout; 172 // a sliding window on the uncompressed data.
173 if (strm.avail_out == 0) {
174 strm.avail_out = sizeof(win);
175 strm.next_out = win;
176 }
177
178 if (mode == RAW && index == NULL)
179 // We skip the inflate() call at the start of raw deflate data in
180 // order generate an access point there. Set data_type to imitate
181 // the end of a header.
182 strm.data_type = 0x80;
183 else {
184 // Inflate and update the number of uncompressed bytes.
185 unsigned before = strm.avail_out;
186 ret = inflate(&strm, Z_BLOCK);
187 totout += before - strm.avail_out;
188 }
189
190 if ((strm.data_type & 0xc0) == 0x80 &&
191 (index == NULL || totout - last >= span)) {
192 // We are at the end of a header or a non-last deflate block, so we
193 // can add an access point here. Furthermore, we are either at the
194 // very start for the first access point, or there has been span or
195 // more uncompressed bytes since the last access point, so we want
196 // to add an access point here.
197 index = add_point(index, strm.data_type & 7, totin - strm.avail_in,
198 totout, strm.avail_out, win);
199 if (index == NULL) {
200 ret = Z_MEM_ERROR;
201 break;
228 } 202 }
229 } while (strm.avail_in != 0); 203 last = totout;
230 } while (ret != Z_STREAM_END); 204 }
231 205
232 /* clean up and return index (release unused entries in list) */ 206 if (ret == Z_STREAM_END && mode == GZIP &&
233 (void)inflateEnd(&strm); 207 (strm.avail_in || ungetc(getc(in), in) != EOF))
234 index->list = realloc(index->list, sizeof(struct point) * index->have); 208 // There is more input after the end of a gzip member. Reset the
235 index->gzip = gzip; 209 // inflate state to read another gzip member. On success, this will
210 // set ret to Z_OK to continue decompressing.
211 ret = inflateReset2(&strm, GZIP);
212
213 // Keep going until Z_STREAM_END or error. If the compressed data ends
214 // prematurely without a file read error, Z_BUF_ERROR is returned.
215 } while (ret == Z_OK);
216 inflateEnd(&strm);
217
218 if (ret != Z_STREAM_END) {
219 // An error was encountered. Discard the index and return a negative
220 // error code.
221 deflate_index_free(index);
222 return ret == Z_NEED_DICT ? Z_DATA_ERROR : ret;
223 }
224
225 // Shrink the index to only the occupied access points and return it.
226 index->mode = mode;
236 index->length = totout; 227 index->length = totout;
228 point_t *list = realloc(index->list, sizeof(point_t) * index->have);
229 if (list == NULL) {
230 // Seems like a realloc() to make something smaller should always work,
231 // but just in case.
232 deflate_index_free(index);
233 return Z_MEM_ERROR;
234 }
235 index->list = list;
237 *built = index; 236 *built = index;
238 return index->have; 237 return index->have;
239
240 /* return error */
241 deflate_index_build_error:
242 (void)inflateEnd(&strm);
243 deflate_index_free(index);
244 return ret;
245} 238}
246 239
247/* See comments in zran.h. */ 240// See comments in zran.h.
248int deflate_index_extract(FILE *in, struct deflate_index *index, off_t offset, 241ptrdiff_t deflate_index_extract(FILE *in, struct deflate_index *index,
249 unsigned char *buf, int len) 242 off_t offset, unsigned char *buf, size_t len) {
250{ 243 // Do a quick sanity check on the index.
251 int ret, skip; 244 if (index == NULL || index->have < 1 || index->list[0].out != 0)
252 z_stream strm; 245 return Z_STREAM_ERROR;
253 struct point *here;
254 unsigned char input[CHUNK];
255 unsigned char discard[WINSIZE];
256 246
257 /* proceed only if something reasonable to do */ 247 // If nothing to extract, return zero bytes extracted.
258 if (len < 0) 248 if (len == 0 || offset < 0 || offset >= index->length)
259 return 0; 249 return 0;
260 250
261 /* find where in stream to start */ 251 // Find the access point closest to but not after offset.
262 here = index->list; 252 int lo = -1, hi = index->have;
263 ret = index->have; 253 point_t *point = index->list;
264 while (--ret && here[1].out <= offset) 254 while (hi - lo > 1) {
265 here++; 255 int mid = (lo + hi) >> 1;
266 256 if (offset < point[mid].out)
267 /* initialize file and inflate state to start there */ 257 hi = mid;
268 strm.zalloc = Z_NULL; 258 else
269 strm.zfree = Z_NULL; 259 lo = mid;
270 strm.opaque = Z_NULL; 260 }
271 strm.avail_in = 0; 261 point += lo;
272 strm.next_in = Z_NULL; 262
273 ret = inflateInit2(&strm, -15); /* raw inflate */ 263 // Initialize the input file and prime the inflate engine to start there.
264 int ret = fseeko(in, point->in - (point->bits ? 1 : 0), SEEK_SET);
265 if (ret == -1)
266 return Z_ERRNO;
267 int ch = 0;
268 if (point->bits && (ch = getc(in)) == EOF)
269 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR;
270 z_stream strm = {0};
271 ret = inflateInit2(&strm, RAW);
274 if (ret != Z_OK) 272 if (ret != Z_OK)
275 return ret; 273 return ret;
276 ret = fseeko(in, here->in - (here->bits ? 1 : 0), SEEK_SET); 274 if (point->bits)
277 if (ret == -1) 275 inflatePrime(&strm, point->bits, ch >> (8 - point->bits));
278 goto deflate_index_extract_ret; 276 inflateSetDictionary(&strm, point->window, WINSIZE);
279 if (here->bits) {
280 ret = getc(in);
281 if (ret == -1) {
282 ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR;
283 goto deflate_index_extract_ret;
284 }
285 (void)inflatePrime(&strm, here->bits, ret >> (8 - here->bits));
286 }
287 (void)inflateSetDictionary(&strm, here->window, WINSIZE);
288 277
289 /* skip uncompressed bytes until offset reached, then satisfy request */ 278 // Skip uncompressed bytes until offset reached, then satisfy request.
290 offset -= here->out; 279 unsigned char input[CHUNK];
291 strm.avail_in = 0; 280 unsigned char discard[WINSIZE];
292 skip = 1; /* while skipping to offset */ 281 offset -= point->out; // number of bytes to skip to get to offset
282 size_t left = len; // number of bytes left to read after offset
293 do { 283 do {
294 /* define where to put uncompressed data, and how much */ 284 if (offset) {
295 if (offset > WINSIZE) { /* skip WINSIZE bytes */ 285 // Discard up to offset uncompressed bytes.
296 strm.avail_out = WINSIZE; 286 strm.avail_out = offset < WINSIZE ? (unsigned)offset : WINSIZE;
297 strm.next_out = discard;
298 offset -= WINSIZE;
299 }
300 else if (offset > 0) { /* last skip */
301 strm.avail_out = (unsigned)offset;
302 strm.next_out = discard; 287 strm.next_out = discard;
303 offset = 0;
304 } 288 }
305 else if (skip) { /* at offset now */ 289 else {
306 strm.avail_out = len; 290 // Uncompress up to left bytes into buf.
307 strm.next_out = buf; 291 strm.avail_out = left < UINT_MAX ? (unsigned)left : UINT_MAX;
308 skip = 0; /* only do this once */ 292 strm.next_out = buf + len - left;
309 } 293 }
310 294
311 /* uncompress until avail_out filled, or end of stream */ 295 // Uncompress, setting got to the number of bytes uncompressed.
312 do { 296 if (strm.avail_in == 0) {
313 if (strm.avail_in == 0) { 297 // Assure available input.
314 strm.avail_in = fread(input, 1, CHUNK, in); 298 strm.avail_in = fread(input, 1, CHUNK, in);
315 if (ferror(in)) { 299 if (strm.avail_in < CHUNK && ferror(in)) {
316 ret = Z_ERRNO; 300 ret = Z_ERRNO;
317 goto deflate_index_extract_ret; 301 break;
318 } 302 }
319 if (strm.avail_in == 0) { 303 strm.next_in = input;
320 ret = Z_DATA_ERROR; 304 }
321 goto deflate_index_extract_ret; 305 unsigned got = strm.avail_out;
322 } 306 ret = inflate(&strm, Z_NO_FLUSH);
323 strm.next_in = input; 307 got -= strm.avail_out;
308
309 // Update the appropriate count.
310 if (offset)
311 offset -= got;
312 else
313 left -= got;
314
315 // If we're at the end of a gzip member and there's more to read,
316 // continue to the next gzip member.
317 if (ret == Z_STREAM_END && index->mode == GZIP) {
318 // Discard the gzip trailer.
319 unsigned drop = 8; // length of gzip trailer
320 if (strm.avail_in >= drop) {
321 strm.avail_in -= drop;
322 strm.next_in += drop;
323 }
324 else {
325 // Read and discard the remainder of the gzip trailer.
326 drop -= strm.avail_in;
327 strm.avail_in = 0;
328 do {
329 if (getc(in) == EOF)
330 // The input does not have a complete trailer.
331 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR;
332 } while (--drop);
324 } 333 }
325 ret = inflate(&strm, Z_NO_FLUSH); /* normal inflate */
326 if (ret == Z_NEED_DICT)
327 ret = Z_DATA_ERROR;
328 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR)
329 goto deflate_index_extract_ret;
330 if (ret == Z_STREAM_END) {
331 /* the raw deflate stream has ended */
332 if (index->gzip == 0)
333 /* this is a zlib stream that has ended -- done */
334 break;
335
336 /* near the end of a gzip member, which might be followed by
337 another gzip member -- skip the gzip trailer and see if
338 there is more input after it */
339 if (strm.avail_in < 8) {
340 fseeko(in, 8 - strm.avail_in, SEEK_CUR);
341 strm.avail_in = 0;
342 }
343 else {
344 strm.avail_in -= 8;
345 strm.next_in += 8;
346 }
347 if (strm.avail_in == 0 && ungetc(getc(in), in) == EOF)
348 /* the input ended after the gzip trailer -- done */
349 break;
350 334
351 /* there is more input, so another gzip member should follow -- 335 if (strm.avail_in || ungetc(getc(in), in) != EOF) {
352 validate and skip the gzip header */ 336 // There's more after the gzip trailer. Use inflate to skip the
353 ret = inflateReset2(&strm, 31); 337 // gzip header and resume the raw inflate there.
354 if (ret != Z_OK) 338 inflateReset2(&strm, GZIP);
355 goto deflate_index_extract_ret;
356 do { 339 do {
357 if (strm.avail_in == 0) { 340 if (strm.avail_in == 0) {
358 strm.avail_in = fread(input, 1, CHUNK, in); 341 strm.avail_in = fread(input, 1, CHUNK, in);
359 if (ferror(in)) { 342 if (strm.avail_in < CHUNK && ferror(in)) {
360 ret = Z_ERRNO; 343 ret = Z_ERRNO;
361 goto deflate_index_extract_ret; 344 break;
362 }
363 if (strm.avail_in == 0) {
364 ret = Z_DATA_ERROR;
365 goto deflate_index_extract_ret;
366 } 345 }
367 strm.next_in = input; 346 strm.next_in = input;
368 } 347 }
369 ret = inflate(&strm, Z_BLOCK); 348 strm.avail_out = WINSIZE;
370 if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 349 strm.next_out = discard;
371 goto deflate_index_extract_ret; 350 ret = inflate(&strm, Z_BLOCK); // stop at end of header
372 } while ((strm.data_type & 128) == 0); 351 } while (ret == Z_OK && (strm.data_type & 0x80) == 0);
373
374 /* set up to continue decompression of the raw deflate stream
375 that follows the gzip header */
376 ret = inflateReset2(&strm, -15);
377 if (ret != Z_OK) 352 if (ret != Z_OK)
378 goto deflate_index_extract_ret; 353 break;
354 inflateReset2(&strm, RAW);
379 } 355 }
356 }
380 357
381 /* continue to process the available input before reading more */ 358 // Continue until we have the requested data, the deflate data has
382 } while (strm.avail_out != 0); 359 // ended, or an error is encountered.
383 360 } while (ret == Z_OK && left);
384 if (ret == Z_STREAM_END) 361 inflateEnd(&strm);
385 /* reached the end of the compressed data -- return the data that
386 was available, possibly less than requested */
387 break;
388
389 /* do until offset reached and requested data read */
390 } while (skip);
391
392 /* compute the number of uncompressed bytes read after the offset */
393 ret = skip ? 0 : len - strm.avail_out;
394 362
395 /* clean up and return the bytes read, or the negative error */ 363 // Return the number of uncompressed bytes read into buf, or the error.
396 deflate_index_extract_ret: 364 return ret == Z_OK || ret == Z_STREAM_END ? len - left : ret;
397 (void)inflateEnd(&strm);
398 return ret;
399} 365}
400 366
401#ifdef TEST 367#ifdef TEST
402 368
403#define SPAN 1048576L /* desired distance between access points */ 369#define SPAN 1048576L // desired distance between access points
404#define LEN 16384 /* number of bytes to extract */ 370#define LEN 16384 // number of bytes to extract
405
406/* Demonstrate the use of deflate_index_build() and deflate_index_extract() by
407 processing the file provided on the command line, and extracting LEN bytes
408 from 2/3rds of the way through the uncompressed output, writing that to
409 stdout. An offset can be provided as the second argument, in which case the
410 data is extracted from there instead. */
411int main(int argc, char **argv)
412{
413 int len;
414 off_t offset = -1;
415 FILE *in;
416 struct deflate_index *index = NULL;
417 unsigned char buf[LEN];
418 371
419 /* open input file */ 372// Demonstrate the use of deflate_index_build() and deflate_index_extract() by
373// processing the file provided on the command line, and extracting LEN bytes
374// from 2/3rds of the way through the uncompressed output, writing that to
375// stdout. An offset can be provided as the second argument, in which case the
376// data is extracted from there instead.
377int main(int argc, char **argv) {
378 // Open the input file.
420 if (argc < 2 || argc > 3) { 379 if (argc < 2 || argc > 3) {
421 fprintf(stderr, "usage: zran file.gz [offset]\n"); 380 fprintf(stderr, "usage: zran file.raw [offset]\n");
422 return 1; 381 return 1;
423 } 382 }
424 in = fopen(argv[1], "rb"); 383 FILE *in = fopen(argv[1], "rb");
425 if (in == NULL) { 384 if (in == NULL) {
426 fprintf(stderr, "zran: could not open %s for reading\n", argv[1]); 385 fprintf(stderr, "zran: could not open %s for reading\n", argv[1]);
427 return 1; 386 return 1;
428 } 387 }
429 388
430 /* get optional offset */ 389 // Get optional offset.
390 off_t offset = -1;
431 if (argc == 3) { 391 if (argc == 3) {
432 char *end; 392 char *end;
433 offset = strtoll(argv[2], &end, 10); 393 offset = strtoll(argv[2], &end, 10);
@@ -437,14 +397,18 @@ int main(int argc, char **argv)
437 } 397 }
438 } 398 }
439 399
440 /* build index */ 400 // Build index.
441 len = deflate_index_build(in, SPAN, &index); 401 struct deflate_index *index = NULL;
402 int len = deflate_index_build(in, SPAN, &index);
442 if (len < 0) { 403 if (len < 0) {
443 fclose(in); 404 fclose(in);
444 switch (len) { 405 switch (len) {
445 case Z_MEM_ERROR: 406 case Z_MEM_ERROR:
446 fprintf(stderr, "zran: out of memory\n"); 407 fprintf(stderr, "zran: out of memory\n");
447 break; 408 break;
409 case Z_BUF_ERROR:
410 fprintf(stderr, "zran: %s ended prematurely\n", argv[1]);
411 break;
448 case Z_DATA_ERROR: 412 case Z_DATA_ERROR:
449 fprintf(stderr, "zran: compressed data error in %s\n", argv[1]); 413 fprintf(stderr, "zran: compressed data error in %s\n", argv[1]);
450 break; 414 break;
@@ -458,19 +422,20 @@ int main(int argc, char **argv)
458 } 422 }
459 fprintf(stderr, "zran: built index with %d access points\n", len); 423 fprintf(stderr, "zran: built index with %d access points\n", len);
460 424
461 /* use index by reading some bytes from an arbitrary offset */ 425 // Use index by reading some bytes from an arbitrary offset.
426 unsigned char buf[LEN];
462 if (offset == -1) 427 if (offset == -1)
463 offset = (index->length << 1) / 3; 428 offset = ((index->length + 1) << 1) / 3;
464 len = deflate_index_extract(in, index, offset, buf, LEN); 429 ptrdiff_t got = deflate_index_extract(in, index, offset, buf, LEN);
465 if (len < 0) 430 if (got < 0)
466 fprintf(stderr, "zran: extraction failed: %s error\n", 431 fprintf(stderr, "zran: extraction failed: %s error\n",
467 len == Z_MEM_ERROR ? "out of memory" : "input corrupted"); 432 got == Z_MEM_ERROR ? "out of memory" : "input corrupted");
468 else { 433 else {
469 fwrite(buf, 1, len, stdout); 434 fwrite(buf, 1, got, stdout);
470 fprintf(stderr, "zran: extracted %d bytes at %llu\n", len, offset); 435 fprintf(stderr, "zran: extracted %ld bytes at %lld\n", got, offset);
471 } 436 }
472 437
473 /* clean up and exit */ 438 // Clean up and exit.
474 deflate_index_free(index); 439 deflate_index_free(index);
475 fclose(in); 440 fclose(in);
476 return 0; 441 return 0;
diff --git a/examples/zran.h b/examples/zran.h
index 2314125..ebf780d 100644
--- a/examples/zran.h
+++ b/examples/zran.h
@@ -1,40 +1,51 @@
1/* zran.h -- example of zlib/gzip stream indexing and random access 1/* zran.h -- example of deflated stream indexing and random access
2 * Copyright (C) 2005, 2012, 2018 Mark Adler 2 * Copyright (C) 2005, 2012, 2018, 2023 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h 3 * For conditions of distribution and use, see copyright notice in zlib.h
4 * Version 1.2 14 Oct 2018 Mark Adler */ 4 * Version 1.3 18 Feb 2023 Mark Adler */
5 5
6#include <stdio.h> 6#include <stdio.h>
7#include "zlib.h" 7#include "zlib.h"
8 8
9/* Access point list. */ 9// Access point.
10typedef struct point {
11 off_t out; // offset in uncompressed data
12 off_t in; // offset in compressed file of first full byte
13 int bits; // 0, or number of bits (1-7) from byte at in-1
14 unsigned char window[32768]; // preceding 32K of uncompressed data
15} point_t;
16
17// Access point list.
10struct deflate_index { 18struct deflate_index {
11 int have; /* number of list entries */ 19 int have; // number of access points in list
12 int gzip; /* 1 if the index is of a gzip file, 0 if it is of a 20 int mode; // -15 for raw, 15 for zlib, or 31 for gzip
13 zlib stream */ 21 off_t length; // total length of uncompressed data
14 off_t length; /* total length of uncompressed data */ 22 point_t *list; // allocated list of access points
15 void *list; /* allocated list of entries */
16}; 23};
17 24
18/* Make one entire pass through a zlib or gzip compressed stream and build an 25// Make one pass through a zlib, gzip, or raw deflate compressed stream and
19 index, with access points about every span bytes of uncompressed output. 26// build an index, with access points about every span bytes of uncompressed
20 gzip files with multiple members are indexed in their entirety. span should 27// output. gzip files with multiple members are fully indexed. span should be
21 be chosen to balance the speed of random access against the memory 28// chosen to balance the speed of random access against the memory requirements
22 requirements of the list, about 32K bytes per access point. The return value 29// of the list, which is about 32K bytes per access point. The return value is
23 is the number of access points on success (>= 1), Z_MEM_ERROR for out of 30// the number of access points on success (>= 1), Z_MEM_ERROR for out of
24 memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a file 31// memory, Z_BUF_ERROR for a premature end of input, Z_DATA_ERROR for a format
25 read error. On success, *built points to the resulting index. */ 32// or verification error in the input file, or Z_ERRNO for a file read error.
33// On success, *built points to the resulting index.
26int deflate_index_build(FILE *in, off_t span, struct deflate_index **built); 34int deflate_index_build(FILE *in, off_t span, struct deflate_index **built);
27 35
28/* Deallocate an index built by deflate_index_build() */ 36// Use the index to read len bytes from offset into buf. Return the number of
29void deflate_index_free(struct deflate_index *index); 37// bytes read or a negative error code. If data is requested past the end of
38// the uncompressed data, then deflate_index_extract() will return a value less
39// than len, indicating how much was actually read into buf. If given a valid
40// index, this function should not return an error unless the file was modified
41// somehow since the index was generated, given that deflate_index_build() had
42// validated all of the input. If nevertheless there is a failure, Z_BUF_ERROR
43// is returned if the compressed data ends prematurely, Z_DATA_ERROR if the
44// deflate compressed data is not valid, Z_MEM_ERROR if out of memory,
45// Z_STREAM_ERROR if the index is not valid, or Z_ERRNO if there is an error
46// reading or seeking on the input file.
47ptrdiff_t deflate_index_extract(FILE *in, struct deflate_index *index,
48 off_t offset, unsigned char *buf, size_t len);
30 49
31/* Use the index to read len bytes from offset into buf. Return bytes read or 50// Deallocate an index built by deflate_index_build().
32 negative for error (Z_DATA_ERROR or Z_MEM_ERROR). If data is requested past 51void deflate_index_free(struct deflate_index *index);
33 the end of the uncompressed data, then deflate_index_extract() will return a
34 value less than len, indicating how much was actually read into buf. This
35 function should not return a data error unless the file was modified since
36 the index was generated, since deflate_index_build() validated all of the
37 input. deflate_index_extract() will return Z_ERRNO if there is an error on
38 reading or seeking the input file. */
39int deflate_index_extract(FILE *in, struct deflate_index *index, off_t offset,
40 unsigned char *buf, int len);
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-15 22:37:46 +0000