sl@0: /* Portions Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies). sl@0: * All rights reserved. sl@0: */ sl@0: sl@0: /* zran.c -- example of zlib/gzip stream indexing and random access sl@0: * Copyright (C) 2005 Mark Adler sl@0: * For conditions of distribution and use, see copyright notice in zlib.h sl@0: Version 1.0 29 May 2005 Mark Adler */ sl@0: sl@0: /* Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary() sl@0: for random access of a compressed file. A file containing a zlib or gzip sl@0: stream is provided on the command line. The compressed stream is decoded in sl@0: its entirety, and an index built with access points about every SPAN bytes sl@0: in the uncompressed output. The compressed file is left open, and can then sl@0: be read randomly, having to decompress on the average SPAN/2 uncompressed sl@0: bytes before getting to the desired block of data. sl@0: sl@0: An access point can be created at the start of any deflate block, by saving sl@0: the starting file offset and bit of that block, and the 32K bytes of sl@0: uncompressed data that precede that block. Also the uncompressed offset of sl@0: that block is saved to provide a referece for locating a desired starting sl@0: point in the uncompressed stream. build_index() works by decompressing the sl@0: input zlib or gzip stream a block at a time, and at the end of each block sl@0: deciding if enough uncompressed data has gone by to justify the creation of sl@0: a new access point. If so, that point is saved in a data structure that sl@0: grows as needed to accommodate the points. sl@0: sl@0: To use the index, an offset in the uncompressed data is provided, for which sl@0: the latest access point at or preceding that offset is located in the index. sl@0: The input file is positioned to the specified location in the index, and if sl@0: necessary the first few bits of the compressed data is read from the file. sl@0: inflate is initialized with those bits and the 32K of uncompressed data, and sl@0: the decompression then proceeds until the desired offset in the file is sl@0: reached. Then the decompression continues to read the desired uncompressed sl@0: data from the file. sl@0: sl@0: Another approach would be to generate the index on demand. In that case, sl@0: requests for random access reads from the compressed data would try to use sl@0: the index, but if a read far enough past the end of the index is required, sl@0: then further index entries would be generated and added. sl@0: sl@0: There is some fair bit of overhead to starting inflation for the random sl@0: access, mainly copying the 32K byte dictionary. So if small pieces of the sl@0: file are being accessed, it would make sense to implement a cache to hold sl@0: some lookahead and avoid many calls to extract() for small lengths. sl@0: sl@0: Another way to build an index would be to use inflateCopy(). That would sl@0: not be constrained to have access points at block boundaries, but requires sl@0: more memory per access point, and also cannot be saved to file due to the sl@0: use of pointers in the state. The approach here allows for storage of the sl@0: index in a file. sl@0: */ sl@0: sl@0: #include sl@0: #include sl@0: #include sl@0: #include sl@0: #include sl@0: #include sl@0: sl@0: _LIT(KTestTitle, "inflatePrime() Test."); sl@0: sl@0: RTest test(_L("inflateprimetest.exe")); sl@0: const int numTestFiles = 2; sl@0: const char *filePath = "z:\\test\\inflateprimetest\\\0"; sl@0: const char *testFile[numTestFiles] = {"gzipped.gz\0", "zipped.zip\0"}; sl@0: sl@0: /* Test macro and function */ sl@0: void Check(TInt aValue, TInt aExpected, TInt aLine) sl@0: { sl@0: if (aValue != aExpected) sl@0: { sl@0: test.Printf(_L("*** Expected error: %d, got: %d\r\n"), aExpected, aValue); sl@0: test.operator()(EFalse, aLine); sl@0: } sl@0: } sl@0: #define test2(a, b) Check(a, b, __LINE__) sl@0: sl@0: #define SPAN 1048576L /* desired distance between access points */ sl@0: #define WINSIZE 32768U /* sliding window size */ sl@0: #define CHUNK 128 /* file input buffer size */ sl@0: sl@0: /* access point entry */ sl@0: struct point { sl@0: off_t out; /* corresponding offset in uncompressed data */ sl@0: off_t in; /* offset in input file of first full byte */ sl@0: int bits; /* number of bits (1-7) from byte at in - 1, or 0 */ sl@0: unsigned char window[WINSIZE]; /* preceding 32K of uncompressed data */ sl@0: }; sl@0: sl@0: /* access point list */ sl@0: struct access { sl@0: int have; /* number of list entries filled in */ sl@0: int size; /* number of list entries allocated */ sl@0: struct point *list; /* allocated list */ sl@0: }; sl@0: sl@0: /* Deallocate an index built by build_index() */ sl@0: void free_index(struct access *index) sl@0: { sl@0: if (index != NULL) { sl@0: free(index->list); sl@0: free(index); sl@0: } sl@0: } sl@0: sl@0: /* Add an entry to the access point list. If out of memory, deallocate the sl@0: existing list and return NULL. */ sl@0: struct access *addpoint(struct access *index, int bits, sl@0: off_t in, off_t out, unsigned left, unsigned char *window) sl@0: { sl@0: struct point *next; sl@0: sl@0: // if list is empty, create it (start with eight points) sl@0: if (index == NULL) { sl@0: index = (struct access *)malloc(sizeof(struct access)); sl@0: if (index == NULL) return NULL; sl@0: index->list = (struct point *)malloc(sizeof(struct point) << 3); sl@0: if (index->list == NULL) { sl@0: free(index); sl@0: return NULL; sl@0: } sl@0: index->size = 8; sl@0: index->have = 0; sl@0: } sl@0: sl@0: // if list is full, make it bigger sl@0: else if (index->have == index->size) { sl@0: index->size <<= 1; sl@0: next = (struct point *)realloc(index->list, sizeof(struct point) * index->size); sl@0: if (next == NULL) { sl@0: free_index(index); sl@0: return NULL; sl@0: } sl@0: index->list = next; sl@0: } sl@0: sl@0: // fill in entry and increment how many we have sl@0: next = index->list + index->have; sl@0: next->bits = bits; sl@0: next->in = in; sl@0: next->out = out; sl@0: if (left) sl@0: memcpy(next->window, window + WINSIZE - left, left); sl@0: if (left < WINSIZE) sl@0: memcpy(next->window + left, window, WINSIZE - left); sl@0: index->have++; sl@0: sl@0: /* return list, possibly reallocated */ sl@0: return index; sl@0: } sl@0: sl@0: /* Make one entire pass through the compressed stream and build an index, with sl@0: access points about every span bytes of uncompressed output -- span is sl@0: chosen to balance the speed of random access against the memory requirements sl@0: of the list, about 32K bytes per access point. Note that data after the end sl@0: of the first zlib or gzip stream in the file is ignored. build_index() sl@0: returns the number of access points on success (>= 1), Z_MEM_ERROR for out sl@0: of memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a sl@0: file read error. On success, *built points to the resulting index. */ sl@0: int build_index(FILE *in, off_t span, struct access **built) sl@0: { sl@0: int ret; sl@0: off_t totin, totout; /* our own total counters to avoid 4GB limit */ sl@0: off_t last; /* totout value of last access point */ sl@0: struct access *index; /* access points being generated */ sl@0: z_stream strm; sl@0: unsigned char input[CHUNK]; sl@0: unsigned char window[WINSIZE]; sl@0: struct point *next = NULL; sl@0: sl@0: /* initialize inflate */ sl@0: strm.zalloc = Z_NULL; sl@0: strm.zfree = Z_NULL; sl@0: strm.opaque = Z_NULL; sl@0: strm.avail_in = 0; sl@0: strm.next_in = Z_NULL; sl@0: ret = inflateInit2(&strm, 47); /* automatic zlib or gzip decoding */ sl@0: if (ret != Z_OK) sl@0: return ret; sl@0: sl@0: /* inflate the input, maintain a sliding window, and build an index -- this sl@0: also validates the integrity of the compressed data using the check sl@0: information at the end of the gzip or zlib stream */ sl@0: totin = totout = last = 0; sl@0: index = NULL; /* will be allocated by first addpoint() */ sl@0: strm.avail_out = 0; sl@0: do { sl@0: /* get some compressed data from input file */ sl@0: strm.avail_in = fread(input, 1, CHUNK, in); sl@0: if (ferror(in)) { sl@0: ret = Z_ERRNO; sl@0: goto build_index_error; sl@0: } sl@0: if (strm.avail_in == 0) { sl@0: ret = Z_DATA_ERROR; sl@0: goto build_index_error; sl@0: } sl@0: strm.next_in = input; sl@0: sl@0: /* process all of that, or until end of stream */ sl@0: do { sl@0: /* reset sliding window if necessary */ sl@0: if (strm.avail_out == 0) { sl@0: strm.avail_out = WINSIZE; sl@0: strm.next_out = window; sl@0: } sl@0: sl@0: /* inflate until out of input, output, or at end of block -- sl@0: update the total input and output counters */ sl@0: totin += strm.avail_in; sl@0: totout += strm.avail_out; sl@0: ret = inflate(&strm, Z_BLOCK); /* return at end of block */ sl@0: totin -= strm.avail_in; sl@0: totout -= strm.avail_out; sl@0: if (ret == Z_NEED_DICT) sl@0: ret = Z_DATA_ERROR; sl@0: if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) sl@0: goto build_index_error; sl@0: if (ret == Z_STREAM_END) sl@0: break; sl@0: sl@0: /* if at end of block, consider adding an index entry (note that if sl@0: data_type indicates an end-of-block, then all of the sl@0: uncompressed data from that block has been delivered, and none sl@0: of the compressed data after that block has been consumed, sl@0: except for up to seven bits) -- the totout == 0 provides an sl@0: entry point after the zlib or gzip header, and assures that the sl@0: index always has at least one access point; we avoid creating an sl@0: access point after the last block by checking bit 6 of data_type sl@0: */ sl@0: if ((strm.data_type & 128) && !(strm.data_type & 64) && sl@0: (totout == 0 || totout - last > span)) { sl@0: index = addpoint(index, strm.data_type & 7, totin, sl@0: totout, strm.avail_out, window); sl@0: if (index == NULL) { sl@0: ret = Z_MEM_ERROR; sl@0: goto build_index_error; sl@0: } sl@0: last = totout; sl@0: } sl@0: } while (strm.avail_in != 0); sl@0: } while (ret != Z_STREAM_END); sl@0: sl@0: /* clean up and return index (release unused entries in list) */ sl@0: (void)inflateEnd(&strm); sl@0: sl@0: next = (struct point *)realloc(index->list, sizeof(struct point) * index->have); sl@0: if (next == NULL) { sl@0: free_index(index); sl@0: return Z_MEM_ERROR; sl@0: } sl@0: index->list = next; sl@0: index->size = index->have; sl@0: *built = index; sl@0: return index->size; sl@0: sl@0: /* return error */ sl@0: build_index_error: sl@0: (void)inflateEnd(&strm); sl@0: if (index != NULL) sl@0: free_index(index); sl@0: return ret; sl@0: } sl@0: sl@0: /* Use the index to read len bytes from offset into buf, return bytes read or sl@0: negative for error (Z_DATA_ERROR or Z_MEM_ERROR). If data is requested past sl@0: the end of the uncompressed data, then extract() will return a value less sl@0: than len, indicating how much as actually read into buf. This function sl@0: should not return a data error unless the file was modified since the index sl@0: was generated. extract() may also return Z_ERRNO if there is an error on sl@0: reading or seeking the input file. */ sl@0: int extract(FILE *in, struct access *index, off_t offset, sl@0: unsigned char *buf, int len) sl@0: { sl@0: int ret, skip, value; sl@0: z_stream strm; sl@0: struct point *here; sl@0: unsigned char input[CHUNK]; sl@0: //unsigned char discard[WINSIZE]; /* No longer required. See comments below. */ sl@0: sl@0: /* proceed only if something reasonable to do */ sl@0: if (len < 0) sl@0: return 0; sl@0: sl@0: /* find where in stream to start */ sl@0: here = index->list; sl@0: ret = index->have; sl@0: while (--ret && here[1].out <= offset) sl@0: here++; sl@0: sl@0: /* initialize file and inflate state to start there */ sl@0: strm.zalloc = Z_NULL; sl@0: strm.zfree = Z_NULL; sl@0: strm.opaque = Z_NULL; sl@0: strm.avail_in = 0; sl@0: strm.next_in = Z_NULL; sl@0: ret = inflateInit2(&strm, -15); /* raw inflate */ sl@0: if (ret != Z_OK) sl@0: return ret; sl@0: ret = fseek(in, here->in - (here->bits ? 1 : 0), SEEK_SET); sl@0: if (ret == -1) sl@0: goto extract_ret; sl@0: sl@0: ret = getc(in); sl@0: if (ret == -1) { sl@0: ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR; sl@0: goto extract_ret; sl@0: } sl@0: sl@0: // If bits is > 0 set the value as done in the original zran.c sl@0: // else set the value to the next byte to prove that inflatePrime sl@0: // is not adding anything to the start of the stream when bits is sl@0: // set to 0. It is then necessary to unget the byte. sl@0: if(here->bits) { sl@0: value = ret >> (8 - here->bits); sl@0: } sl@0: else { sl@0: value = ret; sl@0: ungetc(ret, in); sl@0: } sl@0: sl@0: ret = inflatePrime(&strm, here->bits, value); sl@0: if(ret != Z_OK) { sl@0: goto extract_ret; sl@0: } sl@0: test.Printf(_L("zran: bits = %d\n"), here->bits); sl@0: test.Printf(_L("zran: value = %d\n"), value); sl@0: sl@0: (void)inflateSetDictionary(&strm, here->window, WINSIZE); sl@0: sl@0: /* No longer required. See comment below. sl@0: * sl@0: * skip uncompressed bytes until offset reached, then satisfy request sl@0: offset -= here->out; sl@0: */ sl@0: strm.avail_in = 0; sl@0: skip = 1; /* while skipping to offset */ sl@0: do { sl@0: /* define where to put uncompressed data, and how much */ sl@0: if (skip) { /* at offset now */ sl@0: strm.avail_out = len; sl@0: strm.next_out = buf; sl@0: skip = 0; /* only do this once */ sl@0: } sl@0: sl@0: /* This code is not required in this test as it is used sl@0: * to discard decompressed data between the current sl@0: * access point and the offset(place in the file from sl@0: * which we wish to decompress data). sl@0: * sl@0: if (offset > WINSIZE) { // skip WINSIZE bytes sl@0: strm.avail_out = WINSIZE; sl@0: strm.next_out = discard; sl@0: offset -= WINSIZE; sl@0: } sl@0: else if (offset != 0) { // last skip sl@0: strm.avail_out = (unsigned)offset; sl@0: strm.next_out = discard; sl@0: offset = 0; sl@0: } sl@0: */ sl@0: sl@0: /* uncompress until avail_out filled, or end of stream */ sl@0: do { sl@0: if (strm.avail_in == 0) { sl@0: strm.avail_in = fread(input, 1, CHUNK, in); sl@0: if (ferror(in)) { sl@0: ret = Z_ERRNO; sl@0: goto extract_ret; sl@0: } sl@0: if (strm.avail_in == 0) { sl@0: ret = Z_DATA_ERROR; sl@0: goto extract_ret; sl@0: } sl@0: strm.next_in = input; sl@0: } sl@0: ret = inflate(&strm, Z_NO_FLUSH); /* normal inflate */ sl@0: if (ret == Z_NEED_DICT) sl@0: ret = Z_DATA_ERROR; sl@0: if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR) sl@0: goto extract_ret; sl@0: if (ret == Z_STREAM_END) sl@0: break; sl@0: } while (strm.avail_out != 0); sl@0: sl@0: /* if reach end of stream, then don't keep trying to get more */ sl@0: if (ret == Z_STREAM_END) sl@0: break; sl@0: sl@0: /* do until offset reached and requested data read, or stream ends */ sl@0: } while (skip); sl@0: sl@0: /* compute number of uncompressed bytes read after offset */ sl@0: ret = skip ? 0 : len - strm.avail_out; sl@0: sl@0: /* clean up and return bytes read or error */ sl@0: extract_ret: sl@0: (void)inflateEnd(&strm); sl@0: return ret; sl@0: } sl@0: sl@0: /* Demonstrate the use of build_index() and extract() by processing the file sl@0: provided and then extracting CHUNK bytes at each access point. */ sl@0: int TestInflatePrime(char *file) sl@0: { sl@0: int len; sl@0: FILE *in; sl@0: struct access *index; sl@0: unsigned char buf[CHUNK]; sl@0: sl@0: in = fopen(file, "rb"); sl@0: if (in == NULL) sl@0: { sl@0: return KErrPathNotFound; sl@0: } sl@0: sl@0: // build index sl@0: len = build_index(in, SPAN, &index); sl@0: if (len < 0) sl@0: { sl@0: fclose(in); sl@0: test.Printf(_L("error: %d\n"), len); sl@0: return KErrGeneral; sl@0: } sl@0: test.Printf(_L("zran: built index with %d access points\n"), len); sl@0: sl@0: // Extract some data at the start of each access point. This is done sl@0: // so that we can try extracting some data that does not necessarily sl@0: // start at a byte boundary ie it might start mid byte. sl@0: for(int i = 0; i < index->have; i++) sl@0: { sl@0: len = extract(in, index, index->list[i].out, buf, CHUNK); sl@0: if (len < 0) sl@0: { sl@0: test.Printf(_L("zran: extraction failed: ")); sl@0: sl@0: if(len == Z_MEM_ERROR) sl@0: { sl@0: test.Printf(_L("out of memory error\n")); sl@0: } sl@0: else sl@0: { sl@0: test.Printf(_L("input corrupted error\n")); sl@0: } sl@0: } sl@0: else sl@0: { sl@0: test.Printf(_L("zran: extracted %d bytes at %Lu\n"), len, index->list[i].out); sl@0: } sl@0: } sl@0: sl@0: // clean up and exit sl@0: free_index(index); sl@0: fclose(in); sl@0: sl@0: return KErrNone; sl@0: } sl@0: sl@0: /** sl@0: @SYMTestCaseID SYSLIB-EZLIB2-UT-4273 sl@0: @SYMTestCaseDesc To check that data can be decompressed at various points in a sl@0: compressed file (i.e. decompression may start part of the way sl@0: through a byte) via the use of inflatePrime(). sl@0: @SYMTestPriority Low sl@0: @SYMTestActions 1. Open a compressed file for reading. sl@0: 2. Create an inflate stream and initialise it using inflateInit2(), sl@0: setting windowBits to 47 (automatic gzip/zip header detection). sl@0: 3. Inflate the data in the file using inflate(). During inflation sl@0: create access points using structure Point which maps points sl@0: in the uncompressed data with points in the compressed data. sl@0: The first access point should be at the start of the data sl@0: i.e. after the header. sl@0: sl@0: Structure Point consist of : sl@0: • UPoint(in bytes) – this is the point in the uncompressed data sl@0: • CPoint(in bytes) – this is the point in the compressed data sl@0: • bits(in bits) – this is the point in the compressed data sl@0: 4. Cleanup the inflate stream using inflateEnd(). sl@0: 5. For each access point do the following: sl@0: a. Initialise the inflate stream using inflateInit2(), sl@0: setting windowBits to -15. sl@0: b. Move the file pointer to CPoint - 1 in the input file. sl@0: c. Calculate the value which will be passed to inflatePrime(). sl@0: The algorithm used to calculate value can be seen in the sl@0: attached diagram (in the test spec). sl@0: d. Call inflatePrime() with the bits and value. sl@0: e. Inflate a small section of in the input file using inflate(). sl@0: f. Cleanup the inflate stream using inflateEnd(). sl@0: 6. Close the compressed file and cleanup any allocated memory. sl@0: sl@0: Note: This test should be completed using a zlib file and a gzip sl@0: file. These files should be 500 – 1000KB in size. sl@0: @SYMTestExpectedResults inflatePrime() should return Z_OK and the data should be sl@0: decompressed with no errors. sl@0: @SYMDEF REQ7362 sl@0: */ sl@0: void RunTestL() sl@0: { sl@0: test.Next(_L(" @SYMTestCaseID:SYSLIB-EZLIB2-UT-4273 ")); sl@0: int err; sl@0: char file[KMaxFileName]; sl@0: sl@0: for(int i = 0; i < numTestFiles; i++) sl@0: { sl@0: TBuf<40> testName(_L("inflatePrime test using file ")); sl@0: testName.AppendNum(i); sl@0: test.Next(testName); sl@0: sl@0: strcpy(file, filePath); sl@0: strcat(file, testFile[i]); sl@0: sl@0: err = TestInflatePrime(file); sl@0: sl@0: if(err == KErrPathNotFound) sl@0: { sl@0: test.Printf(_L("zran: could not open file number %d for reading\n"), i); sl@0: User::Leave(err); sl@0: } sl@0: else if(err != KErrNone) sl@0: { sl@0: User::Leave(err); sl@0: } sl@0: sl@0: test.Printf(_L("\n")); sl@0: } sl@0: } sl@0: sl@0: TInt E32Main() sl@0: { sl@0: __UHEAP_MARK; sl@0: sl@0: test.Printf(_L("\n")); sl@0: test.Title(); sl@0: test.Start(KTestTitle); sl@0: sl@0: CTrapCleanup* cleanup = CTrapCleanup::New(); sl@0: sl@0: TRAPD(err, RunTestL()); sl@0: test2(err, KErrNone); sl@0: sl@0: test.End(); sl@0: test.Close(); sl@0: delete cleanup; sl@0: sl@0: __UHEAP_MARKEND; sl@0: return KErrNone; sl@0: }