diff -r 000000000000 -r bde4ae8d615e os/ossrv/compressionlibs/ziplib/test/rtest/inflateprimetest/zran.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/os/ossrv/compressionlibs/ziplib/test/rtest/inflateprimetest/zran.cpp Fri Jun 15 03:10:57 2012 +0200 @@ -0,0 +1,548 @@ +/* Portions Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies). + * All rights reserved. + */ + +/* 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 access 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 +#include +#include + +_LIT(KTestTitle, "inflatePrime() Test."); + +RTest test(_L("inflateprimetest.exe")); +const int numTestFiles = 2; +const char *filePath = "z:\\test\\inflateprimetest\\\0"; +const char *testFile[numTestFiles] = {"gzipped.gz\0", "zipped.zip\0"}; + +/* Test macro and function */ +void Check(TInt aValue, TInt aExpected, TInt aLine) + { + if (aValue != aExpected) + { + test.Printf(_L("*** Expected error: %d, got: %d\r\n"), aExpected, aValue); + test.operator()(EFalse, aLine); + } + } +#define test2(a, b) Check(a, b, __LINE__) + +#define SPAN 1048576L /* desired distance between access points */ +#define WINSIZE 32768U /* sliding window size */ +#define CHUNK 128 /* 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() */ +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. */ +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 = (struct access *)malloc(sizeof(struct access)); + if (index == NULL) return NULL; + index->list = (struct point *)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 = (struct point *)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. */ +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]; + struct point *next = NULL; + + /* 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); + + next = (struct point *)realloc(index->list, sizeof(struct point) * index->have); + if (next == NULL) { + free_index(index); + return Z_MEM_ERROR; + } + index->list = next; + 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. */ +int extract(FILE *in, struct access *index, off_t offset, + unsigned char *buf, int len) +{ + int ret, skip, value; + z_stream strm; + struct point *here; + unsigned char input[CHUNK]; + //unsigned char discard[WINSIZE]; /* No longer required. See comments below. */ + + /* 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 = fseek(in, here->in - (here->bits ? 1 : 0), SEEK_SET); + if (ret == -1) + goto extract_ret; + + ret = getc(in); + if (ret == -1) { + ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR; + goto extract_ret; + } + + // If bits is > 0 set the value as done in the original zran.c + // else set the value to the next byte to prove that inflatePrime + // is not adding anything to the start of the stream when bits is + // set to 0. It is then necessary to unget the byte. + if(here->bits) { + value = ret >> (8 - here->bits); + } + else { + value = ret; + ungetc(ret, in); + } + + ret = inflatePrime(&strm, here->bits, value); + if(ret != Z_OK) { + goto extract_ret; + } + test.Printf(_L("zran: bits = %d\n"), here->bits); + test.Printf(_L("zran: value = %d\n"), value); + + (void)inflateSetDictionary(&strm, here->window, WINSIZE); + + /* No longer required. See comment below. + * + * 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 (skip) { /* at offset now */ + strm.avail_out = len; + strm.next_out = buf; + skip = 0; /* only do this once */ + } + + /* This code is not required in this test as it is used + * to discard decompressed data between the current + * access point and the offset(place in the file from + * which we wish to decompress data). + * + 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 and then extracting CHUNK bytes at each access point. */ +int TestInflatePrime(char *file) + { + int len; + FILE *in; + struct access *index; + unsigned char buf[CHUNK]; + + in = fopen(file, "rb"); + if (in == NULL) + { + return KErrPathNotFound; + } + + // build index + len = build_index(in, SPAN, &index); + if (len < 0) + { + fclose(in); + test.Printf(_L("error: %d\n"), len); + return KErrGeneral; + } + test.Printf(_L("zran: built index with %d access points\n"), len); + + // Extract some data at the start of each access point. This is done + // so that we can try extracting some data that does not necessarily + // start at a byte boundary ie it might start mid byte. + for(int i = 0; i < index->have; i++) + { + len = extract(in, index, index->list[i].out, buf, CHUNK); + if (len < 0) + { + test.Printf(_L("zran: extraction failed: ")); + + if(len == Z_MEM_ERROR) + { + test.Printf(_L("out of memory error\n")); + } + else + { + test.Printf(_L("input corrupted error\n")); + } + } + else + { + test.Printf(_L("zran: extracted %d bytes at %Lu\n"), len, index->list[i].out); + } + } + + // clean up and exit + free_index(index); + fclose(in); + + return KErrNone; + } + +/** +@SYMTestCaseID SYSLIB-EZLIB2-UT-4273 +@SYMTestCaseDesc To check that data can be decompressed at various points in a + compressed file (i.e. decompression may start part of the way + through a byte) via the use of inflatePrime(). +@SYMTestPriority Low +@SYMTestActions 1. Open a compressed file for reading. + 2. Create an inflate stream and initialise it using inflateInit2(), + setting windowBits to 47 (automatic gzip/zip header detection). + 3. Inflate the data in the file using inflate(). During inflation + create access points using structure Point which maps points + in the uncompressed data with points in the compressed data. + The first access point should be at the start of the data + i.e. after the header. + + Structure Point consist of : + • UPoint(in bytes) – this is the point in the uncompressed data + • CPoint(in bytes) – this is the point in the compressed data + • bits(in bits) – this is the point in the compressed data + 4. Cleanup the inflate stream using inflateEnd(). + 5. For each access point do the following: + a. Initialise the inflate stream using inflateInit2(), + setting windowBits to -15. + b. Move the file pointer to CPoint - 1 in the input file. + c. Calculate the value which will be passed to inflatePrime(). + The algorithm used to calculate value can be seen in the + attached diagram (in the test spec). + d. Call inflatePrime() with the bits and value. + e. Inflate a small section of in the input file using inflate(). + f. Cleanup the inflate stream using inflateEnd(). + 6. Close the compressed file and cleanup any allocated memory. + + Note: This test should be completed using a zlib file and a gzip + file. These files should be 500 – 1000KB in size. +@SYMTestExpectedResults inflatePrime() should return Z_OK and the data should be + decompressed with no errors. +@SYMDEF REQ7362 +*/ +void RunTestL() + { + test.Next(_L(" @SYMTestCaseID:SYSLIB-EZLIB2-UT-4273 ")); + int err; + char file[KMaxFileName]; + + for(int i = 0; i < numTestFiles; i++) + { + TBuf<40> testName(_L("inflatePrime test using file ")); + testName.AppendNum(i); + test.Next(testName); + + strcpy(file, filePath); + strcat(file, testFile[i]); + + err = TestInflatePrime(file); + + if(err == KErrPathNotFound) + { + test.Printf(_L("zran: could not open file number %d for reading\n"), i); + User::Leave(err); + } + else if(err != KErrNone) + { + User::Leave(err); + } + + test.Printf(_L("\n")); + } + } + +TInt E32Main() + { + __UHEAP_MARK; + + test.Printf(_L("\n")); + test.Title(); + test.Start(KTestTitle); + + CTrapCleanup* cleanup = CTrapCleanup::New(); + + TRAPD(err, RunTestL()); + test2(err, KErrNone); + + test.End(); + test.Close(); + delete cleanup; + + __UHEAP_MARKEND; + return KErrNone; + }