19e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* zran.c -- example of zlib/gzip stream indexing and random access 204351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes * Copyright (C) 2005, 2012 Mark Adler 39e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * For conditions of distribution and use, see copyright notice in zlib.h 404351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes Version 1.1 29 Sep 2012 Mark Adler */ 504351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes 604351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes/* Version History: 704351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes 1.0 29 May 2005 First version 804351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes 1.1 29 Sep 2012 Fix memory reallocation error 904351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes */ 109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary() 129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project for random access of a compressed file. A file containing a zlib or gzip 139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project stream is provided on the command line. The compressed stream is decoded in 149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project its entirety, and an index built with access points about every SPAN bytes 159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project in the uncompressed output. The compressed file is left open, and can then 169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project be read randomly, having to decompress on the average SPAN/2 uncompressed 179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project bytes before getting to the desired block of data. 189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project An access point can be created at the start of any deflate block, by saving 209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the starting file offset and bit of that block, and the 32K bytes of 219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uncompressed data that precede that block. Also the uncompressed offset of 229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project that block is saved to provide a referece for locating a desired starting 239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project point in the uncompressed stream. build_index() works by decompressing the 249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project input zlib or gzip stream a block at a time, and at the end of each block 259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project deciding if enough uncompressed data has gone by to justify the creation of 269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project a new access point. If so, that point is saved in a data structure that 279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project grows as needed to accommodate the points. 289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project To use the index, an offset in the uncompressed data is provided, for which 309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the latest accees point at or preceding that offset is located in the index. 319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project The input file is positioned to the specified location in the index, and if 329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project necessary the first few bits of the compressed data is read from the file. 339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project inflate is initialized with those bits and the 32K of uncompressed data, and 349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the decompression then proceeds until the desired offset in the file is 359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project reached. Then the decompression continues to read the desired uncompressed 369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project data from the file. 379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Another approach would be to generate the index on demand. In that case, 399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project requests for random access reads from the compressed data would try to use 409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the index, but if a read far enough past the end of the index is required, 419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project then further index entries would be generated and added. 429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project There is some fair bit of overhead to starting inflation for the random 449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project access, mainly copying the 32K byte dictionary. So if small pieces of the 459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project file are being accessed, it would make sense to implement a cache to hold 469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project some lookahead and avoid many calls to extract() for small lengths. 479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project Another way to build an index would be to use inflateCopy(). That would 499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project not be constrained to have access points at block boundaries, but requires 509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project more memory per access point, and also cannot be saved to file due to the 519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project use of pointers in the state. The approach here allows for storage of the 529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index in a file. 539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include <stdio.h> 569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include <stdlib.h> 579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include <string.h> 589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#include "zlib.h" 599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define local static 619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define SPAN 1048576L /* desired distance between access points */ 639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define WINSIZE 32768U /* sliding window size */ 649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define CHUNK 16384 /* file input buffer size */ 659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* access point entry */ 679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectstruct point { 689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project off_t out; /* corresponding offset in uncompressed data */ 699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project off_t in; /* offset in input file of first full byte */ 709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int bits; /* number of bits (1-7) from byte at in - 1, or 0 */ 719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char window[WINSIZE]; /* preceding 32K of uncompressed data */ 729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project}; 739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* access point list */ 759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectstruct access { 769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int have; /* number of list entries filled in */ 779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int size; /* number of list entries allocated */ 789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct point *list; /* allocated list */ 799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project}; 809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Deallocate an index built by build_index() */ 829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal void free_index(struct access *index) 839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (index != NULL) { 859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project free(index->list); 869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project free(index); 879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Add an entry to the access point list. If out of memory, deallocate the 919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project existing list and return NULL. */ 929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal struct access *addpoint(struct access *index, int bits, 939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project off_t in, off_t out, unsigned left, unsigned char *window) 949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct point *next; 969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* if list is empty, create it (start with eight points) */ 989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (index == NULL) { 999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index = malloc(sizeof(struct access)); 1009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (index == NULL) return NULL; 1019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index->list = malloc(sizeof(struct point) << 3); 1029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (index->list == NULL) { 1039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project free(index); 1049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return NULL; 1059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index->size = 8; 1079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index->have = 0; 1089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* if list is full, make it bigger */ 1119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if (index->have == index->size) { 1129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index->size <<= 1; 1139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project next = realloc(index->list, sizeof(struct point) * index->size); 1149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (next == NULL) { 1159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project free_index(index); 1169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return NULL; 1179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index->list = next; 1199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* fill in entry and increment how many we have */ 1229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project next = index->list + index->have; 1239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project next->bits = bits; 1249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project next->in = in; 1259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project next->out = out; 1269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (left) 1279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project memcpy(next->window, window + WINSIZE - left, left); 1289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (left < WINSIZE) 1299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project memcpy(next->window + left, window, WINSIZE - left); 1309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index->have++; 1319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* return list, possibly reallocated */ 1339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return index; 1349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 1359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Make one entire pass through the compressed stream and build an index, with 1379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project access points about every span bytes of uncompressed output -- span is 1389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project chosen to balance the speed of random access against the memory requirements 1399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project of the list, about 32K bytes per access point. Note that data after the end 1409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project of the first zlib or gzip stream in the file is ignored. build_index() 1419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project returns the number of access points on success (>= 1), Z_MEM_ERROR for out 1429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project of memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a 1439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project file read error. On success, *built points to the resulting index. */ 1449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int build_index(FILE *in, off_t span, struct access **built) 1459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 1469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int ret; 1479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project off_t totin, totout; /* our own total counters to avoid 4GB limit */ 1489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project off_t last; /* totout value of last access point */ 1499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct access *index; /* access points being generated */ 1509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project z_stream strm; 1519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char input[CHUNK]; 1529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char window[WINSIZE]; 1539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* initialize inflate */ 1559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.zalloc = Z_NULL; 1569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.zfree = Z_NULL; 1579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.opaque = Z_NULL; 1589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_in = 0; 1599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_in = Z_NULL; 1609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = inflateInit2(&strm, 47); /* automatic zlib or gzip decoding */ 1619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret != Z_OK) 1629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return ret; 1639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* inflate the input, maintain a sliding window, and build an index -- this 1659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project also validates the integrity of the compressed data using the check 1669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project information at the end of the gzip or zlib stream */ 1679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project totin = totout = last = 0; 1689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index = NULL; /* will be allocated by first addpoint() */ 1699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_out = 0; 1709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 1719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* get some compressed data from input file */ 1729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_in = fread(input, 1, CHUNK, in); 1739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ferror(in)) { 1749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = Z_ERRNO; 1759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto build_index_error; 1769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (strm.avail_in == 0) { 1789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = Z_DATA_ERROR; 1799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto build_index_error; 1809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_in = input; 1829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* process all of that, or until end of stream */ 1849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 1859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* reset sliding window if necessary */ 1869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (strm.avail_out == 0) { 1879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_out = WINSIZE; 1889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_out = window; 1899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 1909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* inflate until out of input, output, or at end of block -- 1929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project update the total input and output counters */ 1939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project totin += strm.avail_in; 1949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project totout += strm.avail_out; 1959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = inflate(&strm, Z_BLOCK); /* return at end of block */ 1969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project totin -= strm.avail_in; 1979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project totout -= strm.avail_out; 1989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == Z_NEED_DICT) 1999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = Z_DATA_ERROR; 2009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 2019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto build_index_error; 2029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == Z_STREAM_END) 2039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 2049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* if at end of block, consider adding an index entry (note that if 2069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project data_type indicates an end-of-block, then all of the 2079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project uncompressed data from that block has been delivered, and none 2089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project of the compressed data after that block has been consumed, 2099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project except for up to seven bits) -- the totout == 0 provides an 2109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project entry point after the zlib or gzip header, and assures that the 2119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index always has at least one access point; we avoid creating an 2129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project access point after the last block by checking bit 6 of data_type 2139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if ((strm.data_type & 128) && !(strm.data_type & 64) && 2159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (totout == 0 || totout - last > span)) { 2169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index = addpoint(index, strm.data_type & 7, totin, 2179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project totout, strm.avail_out, window); 2189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (index == NULL) { 2199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = Z_MEM_ERROR; 2209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto build_index_error; 2219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project last = totout; 2239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (strm.avail_in != 0); 2259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (ret != Z_STREAM_END); 2269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* clean up and return index (release unused entries in list) */ 2289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (void)inflateEnd(&strm); 22904351a92ecc8429c999acbfc5dfe5aa8bee1d19dElliott Hughes index->list = realloc(index->list, sizeof(struct point) * index->have); 2309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project index->size = index->have; 2319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project *built = index; 2329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return index->size; 2339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* return error */ 2359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project build_index_error: 2369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (void)inflateEnd(&strm); 2379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (index != NULL) 2389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project free_index(index); 2399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return ret; 2409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 2419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Use the index to read len bytes from offset into buf, return bytes read or 2439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project negative for error (Z_DATA_ERROR or Z_MEM_ERROR). If data is requested past 2449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the end of the uncompressed data, then extract() will return a value less 2459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project than len, indicating how much as actually read into buf. This function 2469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project should not return a data error unless the file was modified since the index 2479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project was generated. extract() may also return Z_ERRNO if there is an error on 2489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project reading or seeking the input file. */ 2499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlocal int extract(FILE *in, struct access *index, off_t offset, 2509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char *buf, int len) 2519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 2529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int ret, skip; 2539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project z_stream strm; 2549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project struct point *here; 2559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char input[CHUNK]; 2569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char discard[WINSIZE]; 2579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* proceed only if something reasonable to do */ 2599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len < 0) 2609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 0; 2619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* find where in stream to start */ 2639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project here = index->list; 2649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = index->have; 2659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project while (--ret && here[1].out <= offset) 2669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project here++; 2679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* initialize file and inflate state to start there */ 2699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.zalloc = Z_NULL; 2709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.zfree = Z_NULL; 2719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.opaque = Z_NULL; 2729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_in = 0; 2739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_in = Z_NULL; 2749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = inflateInit2(&strm, -15); /* raw inflate */ 2759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret != Z_OK) 2769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return ret; 2779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = fseeko(in, here->in - (here->bits ? 1 : 0), SEEK_SET); 2789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == -1) 2799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto extract_ret; 2809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (here->bits) { 2819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = getc(in); 2829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == -1) { 2839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR; 2849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto extract_ret; 2859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (void)inflatePrime(&strm, here->bits, ret >> (8 - here->bits)); 2879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 2889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (void)inflateSetDictionary(&strm, here->window, WINSIZE); 2899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* skip uncompressed bytes until offset reached, then satisfy request */ 2919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project offset -= here->out; 2929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_in = 0; 2939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project skip = 1; /* while skipping to offset */ 2949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 2959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* define where to put uncompressed data, and how much */ 2969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (offset == 0 && skip) { /* at offset now */ 2979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_out = len; 2989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_out = buf; 2999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project skip = 0; /* only do this once */ 3009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (offset > WINSIZE) { /* skip WINSIZE bytes */ 3029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_out = WINSIZE; 3039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_out = discard; 3049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project offset -= WINSIZE; 3059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else if (offset != 0) { /* last skip */ 3079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_out = (unsigned)offset; 3089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_out = discard; 3099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project offset = 0; 3109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* uncompress until avail_out filled, or end of stream */ 3139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project do { 3149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (strm.avail_in == 0) { 3159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.avail_in = fread(input, 1, CHUNK, in); 3169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ferror(in)) { 3179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = Z_ERRNO; 3189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto extract_ret; 3199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (strm.avail_in == 0) { 3219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = Z_DATA_ERROR; 3229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto extract_ret; 3239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project strm.next_in = input; 3259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = inflate(&strm, Z_NO_FLUSH); /* normal inflate */ 3279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == Z_NEED_DICT) 3289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = Z_DATA_ERROR; 3299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) 3309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project goto extract_ret; 3319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == Z_STREAM_END) 3329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 3339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (strm.avail_out != 0); 3349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* if reach end of stream, then don't keep trying to get more */ 3369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (ret == Z_STREAM_END) 3379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 3389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* do until offset reached and requested data read, or stream ends */ 3409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } while (skip); 3419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* compute number of uncompressed bytes read after offset */ 3439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project ret = skip ? 0 : len - strm.avail_out; 3449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* clean up and return bytes read or error */ 3469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project extract_ret: 3479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project (void)inflateEnd(&strm); 3489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return ret; 3499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 3509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Demonstrate the use of build_index() and extract() by processing the file 3529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project provided on the command line, and the extracting 16K from about 2/3rds of 3539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project the way through the uncompressed output, and writing that to stdout. */ 3549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectint main(int argc, char **argv) 3559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project{ 3569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project int len; 3579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project off_t offset; 3589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project FILE *in; 359381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes struct access *index = NULL; 3609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project unsigned char buf[CHUNK]; 3619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* open input file */ 3639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (argc != 2) { 3649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "usage: zran file.gz\n"); 3659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 1; 3669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project in = fopen(argv[1], "rb"); 3689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (in == NULL) { 3699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: could not open %s for reading\n", argv[1]); 3709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 1; 3719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* build index */ 3749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = build_index(in, SPAN, &index); 3759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len < 0) { 3769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fclose(in); 3779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project switch (len) { 3789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project case Z_MEM_ERROR: 3799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: out of memory\n"); 3809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 3819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project case Z_DATA_ERROR: 3829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: compressed data error in %s\n", argv[1]); 3839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 3849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project case Z_ERRNO: 3859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: read error on %s\n", argv[1]); 3869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project break; 3879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project default: 3889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: error %d while building index\n", len); 3899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 1; 3919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 3929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: built index with %d access points\n", len); 3939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* use index by reading some bytes from an arbitrary offset */ 3959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project offset = (index->list[index->have - 1].out << 1) / 3; 3969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len = extract(in, index, offset, buf, CHUNK); 3979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project if (len < 0) 3989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: extraction failed: %s error\n", 3999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project len == Z_MEM_ERROR ? "out of memory" : "input corrupted"); 4009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project else { 4019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fwrite(buf, 1, len, stdout); 4029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fprintf(stderr, "zran: extracted %d bytes at %llu\n", len, offset); 4039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project } 4049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 4059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* clean up and exit */ 4069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project free_index(index); 4079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project fclose(in); 4089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project return 0; 4099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project} 410