Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zlib/examples/zran.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 */
5
6 /* Version History:
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()
17 */
18
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.
26 //
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.
36 //
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
44 // the file.
45 //
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.
50 //
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
55 // index in a file.
56
57 #include <stdio.h>
58 #include <stdlib.h>
59 #include <string.h>
60 #include <limits.h>
61 #include "zlib.h"
62 #include "zran.h"
63
64 #define WINSIZE 32768U // sliding window size
65 #define CHUNK 16384 // file input buffer size
66
67 // See comments in zran.h.
68 void deflate_index_free(struct deflate_index *index) {
69 if (index != NULL) {
70 free(index->list);
71 free(index);
72 }
73 }
74
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) {
82 if (index == NULL) {
83 // The list is empty. Create it, starting with eight access points.
84 index = malloc(sizeof(struct deflate_index));
85 if (index == NULL)
86 return NULL;
87 index->have = 0;
88 index->mode = 8;
89 index->list = malloc(sizeof(point_t) * index->mode);
90 if (index->list == NULL) {
91 free(index);
92 return NULL;
93 }
94 }
95
96 else if (index->have == index->mode) {
97 // The list is full. Make it bigger.
98 index->mode <<= 1;
99 point_t *next = realloc(index->list, sizeof(point_t) * index->mode);
100 if (next == NULL) {
101 deflate_index_free(index);
102 return NULL;
103 }
104 index->list = next;
105 }
106
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);
112 return NULL;
113 }
114 next->out = out;
115 next->in = in;
116 next->bits = bits;
117 if (left)
118 memcpy(next->window, window + WINSIZE - left, left);
119 if (left < WINSIZE)
120 memcpy(next->window + left, window, WINSIZE - left);
121
122 // Return the index, which may have been newly allocated or destroyed.
123 return index;
124 }
125
126 // Decompression modes. These are the inflateInit2() windowBits parameter.
127 #define RAW -15
128 #define ZLIB 15
129 #define GZIP 31
130
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)
140
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
145 do {
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;
150 strm.next_in = buf;
151 if (strm.avail_in < sizeof(buf) && ferror(in)) {
152 ret = Z_ERRNO;
153 break;
154 }
155
156 if (mode == 0) {
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 :
165 /* else */ RAW;
166 ret = inflateInit2(&strm, mode);
167 if (ret != Z_OK)
168 break;
169 }
170 }
171
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);
176 strm.next_out = win;
177 }
178
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;
184 else {
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;
189 }
190
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);
200 if (index == NULL) {
201 ret = Z_MEM_ERROR;
202 break;
203 }
204 last = totout;
205 }
206
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);
213
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);
217 inflateEnd(&strm);
218
219 if (ret != Z_STREAM_END) {
220 // An error was encountered. Discard the index and return a negative
221 // error code.
222 deflate_index_free(index);
223 return ret == Z_NEED_DICT ? Z_DATA_ERROR : ret;
224 }
225
226 // Shrink the index to only the occupied access points and return it.
227 index->mode = mode;
228 index->length = totout;
229 point_t *list = realloc(index->list, sizeof(point_t) * index->have);
230 if (list == NULL) {
231 // Seems like a realloc() to make something smaller should always work,
232 // but just in case.
233 deflate_index_free(index);
234 return Z_MEM_ERROR;
235 }
236 index->list = list;
237 *built = index;
238 return index->have;
239 }
240
241 #ifdef NOPRIME
242 // Support zlib versions before 1.2.3 (July 2005), or incomplete zlib clones
243 // that do not have inflatePrime().
244
245 # define INFLATEPRIME inflatePreface
246
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
256 *have += bits;
257 if (k)
258 *in |= value << k; // write value above the low k bits
259 else
260 *in = value;
261 k = 8 - k; // the number of bits just appended
262 while (bits > k) {
263 value >>= k; // drop the bits appended
264 bits -= k;
265 k = 8; // now at a byte boundary
266 *++in = value;
267 }
268 }
269
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) {
277 // Check input.
278 if (strm == Z_NULL || bits < 0 || bits > 16)
279 return Z_STREAM_ERROR;
280 if (bits == 0)
281 return Z_OK;
282 value &= (2 << (bits - 1)) - 1;
283
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
288 };
289 const int dynlen = 95; // number of bits in the block
290
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];
294 int have = 0;
295 if (bits & 1) {
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
298 // bits.
299 memcpy(in, dyn, sizeof(dyn));
300 have = dynlen;
301 }
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);
306
307 // Append the bits bits from value, which takes us to a byte boundary.
308 append_bits(value, bits, in, &have);
309
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
317 // occupy.
318 strm->avail_in = have >> 3;
319 strm->next_in = in;
320 strm->avail_out = 0;
321 strm->next_out = in; // not used, but can't be NULL
322 return inflate(strm, Z_NO_FLUSH);
323 }
324
325 #else
326 # define INFLATEPRIME inflatePrime
327 #endif
328
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;
335
336 // If nothing to extract, return zero bytes extracted.
337 if (len == 0 || offset < 0 || offset >= index->length)
338 return 0;
339
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)
346 hi = mid;
347 else
348 lo = mid;
349 }
350 point += lo;
351
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);
354 if (ret == -1)
355 return Z_ERRNO;
356 int ch = 0;
357 if (point->bits && (ch = getc(in)) == EOF)
358 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR;
359 z_stream strm = {0};
360 ret = inflateInit2(&strm, RAW);
361 if (ret != Z_OK)
362 return ret;
363 if (point->bits)
364 INFLATEPRIME(&strm, point->bits, ch >> (8 - point->bits));
365 inflateSetDictionary(&strm, point->window, WINSIZE);
366
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
372 do {
373 if (offset) {
374 // Discard up to offset uncompressed bytes.
375 strm.avail_out = offset < WINSIZE ? (unsigned)offset : WINSIZE;
376 strm.next_out = discard;
377 }
378 else {
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;
382 }
383
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)) {
389 ret = Z_ERRNO;
390 break;
391 }
392 strm.next_in = input;
393 }
394 unsigned got = strm.avail_out;
395 ret = inflate(&strm, Z_NO_FLUSH);
396 got -= strm.avail_out;
397
398 // Update the appropriate count.
399 if (offset)
400 offset -= got;
401 else
402 left -= got;
403
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;
412 }
413 else {
414 // Read and discard the remainder of the gzip trailer.
415 drop -= strm.avail_in;
416 strm.avail_in = 0;
417 do {
418 if (getc(in) == EOF)
419 // The input does not have a complete trailer.
420 return ferror(in) ? Z_ERRNO : Z_BUF_ERROR;
421 } while (--drop);
422 }
423
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);
428 do {
429 if (strm.avail_in == 0) {
430 strm.avail_in = fread(input, 1, CHUNK, in);
431 if (strm.avail_in < CHUNK && ferror(in)) {
432 ret = Z_ERRNO;
433 break;
434 }
435 strm.next_in = input;
436 }
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);
441 if (ret != Z_OK)
442 break;
443 inflateReset2(&strm, RAW);
444 }
445 }
446
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);
450 inflateEnd(&strm);
451
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;
454 }
455
456 #ifdef TEST
457
458 #define SPAN 1048576L // desired distance between access points
459 #define LEN 16384 // number of bytes to extract
460
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");
470 return 1;
471 }
472 FILE *in = fopen(argv[1], "rb");
473 if (in == NULL) {
474 fprintf(stderr, "zran: could not open %s for reading\n", argv[1]);
475 return 1;
476 }
477
478 // Get optional offset.
479 off_t offset = -1;
480 if (argc == 3) {
481 char *end;
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]);
485 return 1;
486 }
487 }
488
489 // Build index.
490 struct deflate_index *index = NULL;
491 int len = deflate_index_build(in, SPAN, &index);
492 if (len < 0) {
493 fclose(in);
494 switch (len) {
495 case Z_MEM_ERROR:
496 fprintf(stderr, "zran: out of memory\n");
497 break;
498 case Z_BUF_ERROR:
499 fprintf(stderr, "zran: %s ended prematurely\n", argv[1]);
500 break;
501 case Z_DATA_ERROR:
502 fprintf(stderr, "zran: compressed data error in %s\n", argv[1]);
503 break;
504 case Z_ERRNO:
505 fprintf(stderr, "zran: read error on %s\n", argv[1]);
506 break;
507 default:
508 fprintf(stderr, "zran: error %d while building index\n", len);
509 }
510 return 1;
511 }
512 fprintf(stderr, "zran: built index with %d access points\n", len);
513
514 // Use index by reading some bytes from an arbitrary offset.
515 unsigned char buf[LEN];
516 if (offset == -1)
517 offset = ((index->length + 1) << 1) / 3;
518 ptrdiff_t got = deflate_index_extract(in, index, offset, buf, LEN);
519 if (got < 0)
520 fprintf(stderr, "zran: extraction failed: %s error\n",
521 got == Z_MEM_ERROR ? "out of memory" : "input corrupted");
522 else {
523 fwrite(buf, 1, got, stdout);
524 fprintf(stderr, "zran: extracted %ld bytes at %lld\n", got, offset);
525 }
526
527 // Clean up and exit.
528 deflate_index_free(index);
529 fclose(in);
530 return 0;
531 }
532
533 #endif