symbian-qemu-0.9.1-12/zlib-1.2.3/examples/zran.c
changeset 1 2fb8b9db1c86
equal deleted inserted replaced
0:ffa851df0825 1:2fb8b9db1c86
       
     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() */
       
    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 }