From 9c3a5830218c4e7fff23b8fc4386269db77a03a9 Mon Sep 17 00:00:00 2001 From: Mark Adler Date: Fri, 9 Sep 2011 23:24:52 -0700 Subject: zlib 1.2.2.4 --- examples/README.examples | 5 + examples/fitblk.c | 14 +- examples/gun.c | 23 +-- examples/gzjoin.c | 5 +- examples/zran.c | 404 +++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 430 insertions(+), 21 deletions(-) create mode 100644 examples/zran.c (limited to 'examples') diff --git a/examples/README.examples b/examples/README.examples index 75e9970..5632d7a 100644 --- a/examples/README.examples +++ b/examples/README.examples @@ -35,3 +35,8 @@ zpipe.c reads and writes zlib streams from stdin to stdout - illustrates the proper use of deflate() and inflate() - deeply commented in zlib_how.html (see above) + +zran.c + index a zlib or gzip stream and randomly access it + - illustrates the use of Z_BLOCK, inflatePrime(), and + inflateSetDictionary() to provide random access diff --git a/examples/fitblk.c b/examples/fitblk.c index 5f83114..c61de5c 100644 --- a/examples/fitblk.c +++ b/examples/fitblk.c @@ -73,7 +73,7 @@ local void quit(char *why) local int partcompress(FILE *in, z_streamp def) { int ret, flush; - char raw[RAWLEN]; + unsigned char raw[RAWLEN]; flush = Z_NO_FLUSH; do { @@ -96,7 +96,7 @@ local int partcompress(FILE *in, z_streamp def) local int recompress(z_streamp inf, z_streamp def) { int ret, flush; - char raw[RAWLEN]; + unsigned char raw[RAWLEN]; flush = Z_NO_FLUSH; do { @@ -129,8 +129,8 @@ int main(int argc, char **argv) int ret; /* return code */ unsigned size; /* requested fixed output block size */ unsigned have; /* bytes written by deflate() call */ - char *blk; /* intermediate and final stream */ - char *tmp; /* close to desired size stream */ + unsigned char *blk; /* intermediate and final stream */ + unsigned char *tmp; /* close to desired size stream */ z_stream def, inf; /* zlib deflate and inflate states */ /* get requested output size */ @@ -163,8 +163,7 @@ int main(int argc, char **argv) if (ret == Z_STREAM_END && def.avail_out >= EXCESS) { /* write block to stdout */ have = size + EXCESS - def.avail_out; - ret = fwrite(blk, 1, have, stdout); - if (ret != have || ferror(stdout)) + if (fwrite(blk, 1, have, stdout) != have || ferror(stdout)) quit("error writing output"); /* clean up and print results to stderr */ @@ -217,8 +216,7 @@ int main(int argc, char **argv) /* done -- write block to stdout */ have = size - def.avail_out; - ret = fwrite(blk, 1, have, stdout); - if (ret != have || ferror(stdout)) + if (fwrite(blk, 1, have, stdout) != have || ferror(stdout)) quit("error writing output"); /* clean up and print results to stderr */ diff --git a/examples/gun.c b/examples/gun.c index 1c0d8e5..bfec590 100644 --- a/examples/gun.c +++ b/examples/gun.c @@ -1,7 +1,7 @@ /* gun.c -- simple gunzip to give an example of the use of inflateBack() * Copyright (C) 2003, 2005 Mark Adler * For conditions of distribution and use, see copyright notice in zlib.h - Version 1.2 20 March 2005 Mark Adler */ + Version 1.3 12 June 2005 Mark Adler */ /* Version history: 1.0 16 Feb 2003 First version for testing of inflateBack() @@ -14,6 +14,7 @@ Add a bunch of comments 1.2 20 Mar 2005 Add Unix compress (LZW) decompression Copy file attributes from input file to output file + 1.3 12 Jun 2005 Add casts for error messages [Oberhumer] */ /* @@ -221,12 +222,12 @@ local int lunpipe(unsigned have, unsigned char *next, struct ind *indp, if (last == -1) return Z_BUF_ERROR; if (flags & 0x60) { - strm->msg = "unknown lzw flags set"; + strm->msg = (char *)"unknown lzw flags set"; return Z_DATA_ERROR; } max = flags & 0x1f; if (max < 9 || max > 16) { - strm->msg = "lzw bits out of range"; + strm->msg = (char *)"lzw bits out of range"; return Z_DATA_ERROR; } if (max == 9) /* 9 doesn't really mean 9 */ @@ -246,7 +247,7 @@ local int lunpipe(unsigned have, unsigned char *next, struct ind *indp, if (NEXT() == -1) /* missing a bit */ return Z_BUF_ERROR; if (last & 1) { /* code must be < 256 */ - strm->msg = "invalid lzw code"; + strm->msg = (char *)"invalid lzw code"; return Z_DATA_ERROR; } rem = (unsigned)last >> 1; /* remaining 7 bits */ @@ -313,7 +314,7 @@ local int lunpipe(unsigned have, unsigned char *next, struct ind *indp, to detect random or corrupted input after a compress header. In any case, the prev > end check must be retained. */ if (code != end + 1 || prev > end) { - strm->msg = "invalid lzw code"; + strm->msg = (char *)"invalid lzw code"; return Z_DATA_ERROR; } match[stack++] = (unsigned char)final; @@ -394,7 +395,7 @@ local int gunpipe(z_stream *strm, int infile, int outfile) break; /* empty gzip stream is ok */ } if (last != 31 || (NEXT() != 139 && last != 157)) { - strm->msg = "incorrect header check"; + strm->msg = (char *)"incorrect header check"; ret = first ? Z_DATA_ERROR : Z_ERRNO; break; /* not a gzip or compress header */ } @@ -410,7 +411,7 @@ local int gunpipe(z_stream *strm, int infile, int outfile) ret = Z_BUF_ERROR; if (NEXT() != 8) { /* only deflate method allowed */ if (last == -1) break; - strm->msg = "unknown compression method"; + strm->msg = (char *)"unknown compression method"; ret = Z_DATA_ERROR; break; } @@ -423,7 +424,7 @@ local int gunpipe(z_stream *strm, int infile, int outfile) NEXT(); if (last == -1) break; if (flags & 0xe0) { - strm->msg = "unknown header flags set"; + strm->msg = (char *)"unknown header flags set"; ret = Z_DATA_ERROR; break; } @@ -476,7 +477,7 @@ local int gunpipe(z_stream *strm, int infile, int outfile) NEXT() != ((outd.crc >> 24) & 0xff)) { /* crc error */ if (last != -1) { - strm->msg = "incorrect data check"; + strm->msg = (char *)"incorrect data check"; ret = Z_DATA_ERROR; } break; @@ -487,7 +488,7 @@ local int gunpipe(z_stream *strm, int infile, int outfile) NEXT() != ((outd.total >> 24) & 0xff)) { /* length error */ if (last != -1) { - strm->msg = "incorrect length check"; + strm->msg = (char *)"incorrect length check"; ret = Z_DATA_ERROR; } break; @@ -641,7 +642,7 @@ int main(int argc, char **argv) argv++; test = 0; if (argc && strcmp(*argv, "-h") == 0) { - fprintf(stderr, "gun 1.2 (20 Mar 2005)\n"); + fprintf(stderr, "gun 1.3 (12 Jun 2005)\n"); fprintf(stderr, "Copyright (c) 2005 Mark Adler\n"); fprintf(stderr, "usage: gun [-t] [file1.gz [file2.Z ...]]\n"); return 0; diff --git a/examples/gzjoin.c b/examples/gzjoin.c index 7434c5b..129347c 100644 --- a/examples/gzjoin.c +++ b/examples/gzjoin.c @@ -26,6 +26,7 @@ * Change history: * * 1.0 11 Dec 2004 - First version + * 1.1 12 Jun 2005 - Changed ssize_t to long for portability */ /* @@ -118,7 +119,7 @@ local bin *bopen(char *name) 1 indicating that end-of-file was reached */ local int bload(bin *in) { - ssize_t len; + long len; if (in == NULL) return -1; @@ -126,7 +127,7 @@ local int bload(bin *in) return 0; in->next = in->buf; do { - len = read(in->fd, in->buf + in->left, CHUNK - in->left); + len = (long)read(in->fd, in->buf + in->left, CHUNK - in->left); if (len < 0) return -1; in->left += (unsigned)len; diff --git a/examples/zran.c b/examples/zran.c new file mode 100644 index 0000000..8c7717e --- /dev/null +++ b/examples/zran.c @@ -0,0 +1,404 @@ +/* zran.c -- example of zlib/gzip stream indexing and random access + * Copyright (C) 2005 Mark Adler + * For conditions of distribution and use, see copyright notice in zlib.h + Version 1.0 29 May 2005 Mark Adler */ + +/* Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary() + for random access of a compressed file. A file containing a zlib or gzip + stream is provided on the command line. The compressed stream is decoded in + its entirety, and an index built with access points about every SPAN bytes + in the uncompressed output. The compressed file is left open, and can then + be read randomly, having to decompress on the average SPAN/2 uncompressed + bytes before getting to the desired block of data. + + An access point can be created at the start of any deflate block, by saving + the starting file offset and bit of that block, and the 32K bytes of + uncompressed data that precede that block. Also the uncompressed offset of + that block is saved to provide a referece for locating a desired starting + point in the uncompressed stream. build_index() works by decompressing the + input zlib or gzip stream a block at a time, and at the end of each block + deciding if enough uncompressed data has gone by to justify the creation of + a new access point. If so, that point is saved in a data structure that + grows as needed to accommodate the points. + + To use the index, an offset in the uncompressed data is provided, for which + the latest accees point at or preceding that offset is located in the index. + The input file is positioned to the specified location in the index, and if + necessary the first few bits of the compressed data is read from the file. + inflate is initialized with those bits and the 32K of uncompressed data, and + the decompression then proceeds until the desired offset in the file is + reached. Then the decompression continues to read the desired uncompressed + data from the file. + + Another approach would be to generate the index on demand. In that case, + requests for random access reads from the compressed data would try to use + the index, but if a read far enough past the end of the index is required, + then further index entries would be generated and added. + + There is some fair bit of overhead to starting inflation for the random + access, mainly copying the 32K byte dictionary. So if small pieces of the + file are being accessed, it would make sense to implement a cache to hold + some lookahead and avoid many calls to extract() for small lengths. + + Another way to build an index would be to use inflateCopy(). That would + not be constrained to have access points at block boundaries, but requires + more memory per access point, and also cannot be saved to file due to the + use of pointers in the state. The approach here allows for storage of the + index in a file. + */ + +#include +#include +#include +#include "zlib.h" + +#define local static + +#define SPAN 1048576L /* desired distance between access points */ +#define WINSIZE 32768U /* sliding window size */ +#define CHUNK 16384 /* file input buffer size */ + +/* access point entry */ +struct point { + off_t out; /* corresponding offset in uncompressed data */ + off_t in; /* offset in input file of first full byte */ + int bits; /* number of bits (1-7) from byte at in - 1, or 0 */ + unsigned char window[WINSIZE]; /* preceding 32K of uncompressed data */ +}; + +/* access point list */ +struct access { + int have; /* number of list entries filled in */ + int size; /* number of list entries allocated */ + struct point *list; /* allocated list */ +}; + +/* Deallocate an index built by build_index() */ +local void free_index(struct access *index) +{ + if (index != NULL) { + free(index->list); + free(index); + } +} + +/* Add an entry to the access point list. If out of memory, deallocate the + existing list and return NULL. */ +local struct access *addpoint(struct access *index, int bits, + off_t in, off_t out, unsigned left, unsigned char *window) +{ + struct point *next; + + /* if list is empty, create it (start with eight points) */ + if (index == NULL) { + index = malloc(sizeof(struct access)); + if (index == NULL) return NULL; + index->list = malloc(sizeof(struct point) << 3); + if (index->list == NULL) { + free(index); + return NULL; + } + index->size = 8; + index->have = 0; + } + + /* if list is full, make it bigger */ + else if (index->have == index->size) { + index->size <<= 1; + next = realloc(index->list, sizeof(struct point) * index->size); + if (next == NULL) { + free_index(index); + return NULL; + } + index->list = next; + } + + /* fill in entry and increment how many we have */ + next = index->list + index->have; + next->bits = bits; + next->in = in; + next->out = out; + if (left) + memcpy(next->window, window + WINSIZE - left, left); + if (left < WINSIZE) + memcpy(next->window + left, window, WINSIZE - left); + index->have++; + + /* return list, possibly reallocated */ + return index; +} + +/* Make one entire pass through the compressed stream and build an index, with + access points about every span bytes of uncompressed output -- span is + chosen to balance the speed of random access against the memory requirements + of the list, about 32K bytes per access point. Note that data after the end + of the first zlib or gzip stream in the file is ignored. build_index() + returns the number of access points on success (>= 1), Z_MEM_ERROR for out + of memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a + file read error. On success, *built points to the resulting index. */ +local int build_index(FILE *in, off_t span, struct access **built) +{ + int ret; + off_t totin, totout; /* our own total counters to avoid 4GB limit */ + off_t last; /* totout value of last access point */ + struct access *index; /* access points being generated */ + z_stream strm; + unsigned char input[CHUNK]; + unsigned char window[WINSIZE]; + + /* initialize inflate */ + strm.zalloc = Z_NULL; + strm.zfree = Z_NULL; + strm.opaque = Z_NULL; + strm.avail_in = 0; + strm.next_in = Z_NULL; + ret = inflateInit2(&strm, 47); /* automatic zlib or gzip decoding */ + if (ret != Z_OK) + return ret; + + /* inflate the input, maintain a sliding window, and build an index -- this + also validates the integrity of the compressed data using the check + information at the end of the gzip or zlib stream */ + totin = totout = last = 0; + index = NULL; /* will be allocated by first addpoint() */ + strm.avail_out = 0; + do { + /* get some compressed data from input file */ + strm.avail_in = fread(input, 1, CHUNK, in); + if (ferror(in)) { + ret = Z_ERRNO; + goto build_index_error; + } + if (strm.avail_in == 0) { + ret = Z_DATA_ERROR; + goto build_index_error; + } + strm.next_in = input; + + /* process all of that, or until end of stream */ + do { + /* reset sliding window if necessary */ + if (strm.avail_out == 0) { + strm.avail_out = WINSIZE; + strm.next_out = window; + } + + /* inflate until out of input, output, or at end of block -- + update the total input and output counters */ + totin += strm.avail_in; + totout += strm.avail_out; + ret = inflate(&strm, Z_BLOCK); /* return at end of block */ + totin -= strm.avail_in; + totout -= strm.avail_out; + if (ret == Z_NEED_DICT) + ret = Z_DATA_ERROR; + if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) + goto build_index_error; + if (ret == Z_STREAM_END) + break; + + /* if at end of block, consider adding an index entry (note that if + data_type indicates an end-of-block, then all of the + uncompressed data from that block has been delivered, and none + of the compressed data after that block has been consumed, + except for up to seven bits) -- the totout == 0 provides an + entry point after the zlib or gzip header, and assures that the + index always has at least one access point; we avoid creating an + access point after the last block by checking bit 6 of data_type + */ + if ((strm.data_type & 128) && !(strm.data_type & 64) && + (totout == 0 || totout - last > span)) { + index = addpoint(index, strm.data_type & 7, totin, + totout, strm.avail_out, window); + if (index == NULL) { + ret = Z_MEM_ERROR; + goto build_index_error; + } + last = totout; + } + } while (strm.avail_in != 0); + } while (ret != Z_STREAM_END); + + /* clean up and return index (release unused entries in list) */ + (void)inflateEnd(&strm); + index = realloc(index, sizeof(struct point) * index->have); + index->size = index->have; + *built = index; + return index->size; + + /* return error */ + build_index_error: + (void)inflateEnd(&strm); + if (index != NULL) + free_index(index); + return ret; +} + +/* Use the index to read len bytes from offset into buf, return bytes read or + negative for error (Z_DATA_ERROR or Z_MEM_ERROR). If data is requested past + the end of the uncompressed data, then extract() will return a value less + than len, indicating how much as actually read into buf. This function + should not return a data error unless the file was modified since the index + was generated. extract() may also return Z_ERRNO if there is an error on + reading or seeking the input file. */ +local int extract(FILE *in, struct access *index, off_t offset, + unsigned char *buf, int len) +{ + int ret, skip; + z_stream strm; + struct point *here; + unsigned char input[CHUNK]; + unsigned char discard[WINSIZE]; + + /* proceed only if something reasonable to do */ + if (len < 0) + return 0; + + /* find where in stream to start */ + here = index->list; + ret = index->have; + while (--ret && here[1].out <= offset) + here++; + + /* initialize file and inflate state to start there */ + strm.zalloc = Z_NULL; + strm.zfree = Z_NULL; + strm.opaque = Z_NULL; + strm.avail_in = 0; + strm.next_in = Z_NULL; + ret = inflateInit2(&strm, -15); /* raw inflate */ + if (ret != Z_OK) + return ret; + ret = fseeko(in, here->in - (here->bits ? 1 : 0), SEEK_SET); + if (ret == -1) + goto extract_ret; + if (here->bits) { + ret = getc(in); + if (ret == -1) { + ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR; + goto extract_ret; + } + (void)inflatePrime(&strm, here->bits, ret >> (8 - here->bits)); + } + (void)inflateSetDictionary(&strm, here->window, WINSIZE); + + /* skip uncompressed bytes until offset reached, then satisfy request */ + offset -= here->out; + strm.avail_in = 0; + skip = 1; /* while skipping to offset */ + do { + /* define where to put uncompressed data, and how much */ + if (offset == 0 && skip) { /* at offset now */ + strm.avail_out = len; + strm.next_out = buf; + skip = 0; /* only do this once */ + } + if (offset > WINSIZE) { /* skip WINSIZE bytes */ + strm.avail_out = WINSIZE; + strm.next_out = discard; + offset -= WINSIZE; + } + else if (offset != 0) { /* last skip */ + strm.avail_out = (unsigned)offset; + strm.next_out = discard; + offset = 0; + } + + /* uncompress until avail_out filled, or end of stream */ + do { + if (strm.avail_in == 0) { + strm.avail_in = fread(input, 1, CHUNK, in); + if (ferror(in)) { + ret = Z_ERRNO; + goto extract_ret; + } + if (strm.avail_in == 0) { + ret = Z_DATA_ERROR; + goto extract_ret; + } + strm.next_in = input; + } + ret = inflate(&strm, Z_NO_FLUSH); /* normal inflate */ + if (ret == Z_NEED_DICT) + ret = Z_DATA_ERROR; + if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) + goto extract_ret; + if (ret == Z_STREAM_END) + break; + } while (strm.avail_out != 0); + + /* if reach end of stream, then don't keep trying to get more */ + if (ret == Z_STREAM_END) + break; + + /* do until offset reached and requested data read, or stream ends */ + } while (skip); + + /* compute number of uncompressed bytes read after offset */ + ret = skip ? 0 : len - strm.avail_out; + + /* clean up and return bytes read or error */ + extract_ret: + (void)inflateEnd(&strm); + return ret; +} + +/* Demonstrate the use of build_index() and extract() by processing the file + provided on the command line, and the extracting 16K from about 2/3rds of + the way through the uncompressed output, and writing that to stdout. */ +int main(int argc, char **argv) +{ + int len; + off_t offset; + FILE *in; + struct access *index; + unsigned char buf[CHUNK]; + + /* open input file */ + if (argc != 2) { + fprintf(stderr, "usage: zran file.gz\n"); + return 1; + } + in = fopen(argv[1], "rb"); + if (in == NULL) { + fprintf(stderr, "zran: could not open %s for reading\n", argv[1]); + return 1; + } + + /* build index */ + len = build_index(in, SPAN, &index); + if (len < 0) { + fclose(in); + switch (len) { + case Z_MEM_ERROR: + fprintf(stderr, "zran: out of memory\n"); + break; + case Z_DATA_ERROR: + fprintf(stderr, "zran: compressed data error in %s\n", argv[1]); + break; + case Z_ERRNO: + fprintf(stderr, "zran: read error on %s\n", argv[1]); + break; + default: + fprintf(stderr, "zran: error %d while building index\n", len); + } + return 1; + } + fprintf(stderr, "zran: built index with %d access points\n", len); + + /* use index by reading some bytes from an arbitrary offset */ + offset = (index->list[index->have - 1].out << 1) / 3; + len = extract(in, index, offset, buf, CHUNK); + if (len < 0) + fprintf(stderr, "zran: extraction failed: %s error\n", + len == Z_MEM_ERROR ? "out of memory" : "input corrupted"); + else { + fwrite(buf, 1, len, stdout); + fprintf(stderr, "zran: extracted %d bytes at %llu\n", len, offset); + } + + /* clean up and exit */ + free_index(index); + fclose(in); + return 0; +} -- cgit v1.2.3-55-g6feb