Visualization Library 2.0.0-b5

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
zran.c
Go to the documentation of this file.
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 accees 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() */
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. */
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. */
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. */
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. */
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 }
GLuint GLint GLboolean GLint GLenum access
#define SPAN
Definition: zran.c:62
Bytef * next_in
Definition: zlib.h:69
#define NULL
Definition: ftobjs.h:61
uInt avail_in
Definition: zlib.h:70
char * malloc()
#define Z_NO_FLUSH
Definition: zlib.h:125
GLenum GLenum GLvoid GLvoid GLvoid * span
local int extract(FILE *in, struct access *index, off_t offset, unsigned char *buf, int len)
Definition: zran.c:249
#define Z_NEED_DICT
Definition: zlib.h:134
typedef void(APIENTRY *GLDEBUGPROCARB)(GLenum source
#define bits
Definition: infblock.c:15
int main(int argc, char **argv)
Definition: zran.c:354
#define inflateInit2(strm, windowBits)
Definition: zlib.h:822
voidpf opaque
Definition: zlib.h:82
GLenum GLuint GLenum GLsizei const GLchar * buf
free_func zfree
Definition: zlib.h:81
local int build_index(FILE *in, off_t span, struct access **built)
Definition: zran.c:144
#define Z_OK
Definition: zlib.h:132
int ZEXPORT inflatePrime(z_streamp strm, int bits, int value)
Definition: inflate.c:230
GLenum GLenum GLenum input
int data_type
Definition: zlib.h:84
GLenum GLsizei len
#define Z_MEM_ERROR
Definition: zlib.h:138
GLint left
local int out(void *out_desc, unsigned char *buf, unsigned len)
Definition: gun.c:131
int ZEXPORT inflate(z_streamp strm, int flush)
Definition: dummy_inflate.c:3
#define Z_NULL
Definition: zlib.h:164
alloc_func zalloc
Definition: zlib.h:80
int free()
local void free_index(struct access *index)
Definition: zran.c:82
GLintptr offset
local void skip(file *in, unsigned n)
Definition: gzappend.c:202
int ZEXPORT inflateSetDictionary(z_streamp strm, const Bytef *dictionary, uInt dictLength)
Definition: inflate.c:1291
GLuint in
GLuint index
uInt avail_out
Definition: zlib.h:74
#define CHUNK
Definition: zran.c:64
#define local
Definition: zran.c:60
GLenum GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * bits
local struct access * addpoint(struct access *index, int bits, off_t in, off_t out, unsigned left, unsigned char *window)
Definition: zran.c:92
#define Z_DATA_ERROR
Definition: zlib.h:137
Bytef * next_out
Definition: zlib.h:73
GLsizeiptr size
#define Z_BLOCK
Definition: zlib.h:169
int ZEXPORT inflateEnd(z_streamp strm)
Definition: dummy_inflate.c:12
#define SEEK_SET
Definition: zconf.h:249
#define WINSIZE
Definition: zran.c:63
#define Z_ERRNO
Definition: zlib.h:135
#define Z_STREAM_END
Definition: zlib.h:133