OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [zlib/] [examples/] [zran.c] - Blame information for rev 761

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 745 jeremybenn
/* zran.c -- example of zlib/gzip stream indexing and random access
2
 * Copyright (C) 2005 Mark Adler
3
 * For conditions of distribution and use, see copyright notice in zlib.h
4
   Version 1.0  29 May 2005  Mark Adler */
5
 
6
/* Illustrate the use of Z_BLOCK, inflatePrime(), and inflateSetDictionary()
7
   for random access of a compressed file.  A file containing a zlib or gzip
8
   stream is provided on the command line.  The compressed stream is decoded in
9
   its entirety, and an index built with access points about every SPAN bytes
10
   in the uncompressed output.  The compressed file is left open, and can then
11
   be read randomly, having to decompress on the average SPAN/2 uncompressed
12
   bytes before getting to the desired block of data.
13
 
14
   An access point can be created at the start of any deflate block, by saving
15
   the starting file offset and bit of that block, and the 32K bytes of
16
   uncompressed data that precede that block.  Also the uncompressed offset of
17
   that block is saved to provide a referece for locating a desired starting
18
   point in the uncompressed stream.  build_index() works by decompressing the
19
   input zlib or gzip stream a block at a time, and at the end of each block
20
   deciding if enough uncompressed data has gone by to justify the creation of
21
   a new access point.  If so, that point is saved in a data structure that
22
   grows as needed to accommodate the points.
23
 
24
   To use the index, an offset in the uncompressed data is provided, for which
25
   the latest accees point at or preceding that offset is located in the index.
26
   The input file is positioned to the specified location in the index, and if
27
   necessary the first few bits of the compressed data is read from the file.
28
   inflate is initialized with those bits and the 32K of uncompressed data, and
29
   the decompression then proceeds until the desired offset in the file is
30
   reached.  Then the decompression continues to read the desired uncompressed
31
   data from the file.
32
 
33
   Another approach would be to generate the index on demand.  In that case,
34
   requests for random access reads from the compressed data would try to use
35
   the index, but if a read far enough past the end of the index is required,
36
   then further index entries would be generated and added.
37
 
38
   There is some fair bit of overhead to starting inflation for the random
39
   access, mainly copying the 32K byte dictionary.  So if small pieces of the
40
   file are being accessed, it would make sense to implement a cache to hold
41
   some lookahead and avoid many calls to extract() for small lengths.
42
 
43
   Another way to build an index would be to use inflateCopy().  That would
44
   not be constrained to have access points at block boundaries, but requires
45
   more memory per access point, and also cannot be saved to file due to the
46
   use of pointers in the state.  The approach here allows for storage of the
47
   index in a file.
48
 */
49
 
50
#include <stdio.h>
51
#include <stdlib.h>
52
#include <string.h>
53
#include "zlib.h"
54
 
55
#define local static
56
 
57
#define SPAN 1048576L       /* desired distance between access points */
58
#define WINSIZE 32768U      /* sliding window size */
59
#define CHUNK 16384         /* file input buffer size */
60
 
61
/* access point entry */
62
struct point {
63
    off_t out;          /* corresponding offset in uncompressed data */
64
    off_t in;           /* offset in input file of first full byte */
65
    int bits;           /* number of bits (1-7) from byte at in - 1, or 0 */
66
    unsigned char window[WINSIZE];  /* preceding 32K of uncompressed data */
67
};
68
 
69
/* access point list */
70
struct access {
71
    int have;           /* number of list entries filled in */
72
    int size;           /* number of list entries allocated */
73
    struct point *list; /* allocated list */
74
};
75
 
76
/* Deallocate an index built by build_index() */
77
local void free_index(struct access *index)
78
{
79
    if (index != NULL) {
80
        free(index->list);
81
        free(index);
82
    }
83
}
84
 
85
/* Add an entry to the access point list.  If out of memory, deallocate the
86
   existing list and return NULL. */
87
local struct access *addpoint(struct access *index, int bits,
88
    off_t in, off_t out, unsigned left, unsigned char *window)
89
{
90
    struct point *next;
91
 
92
    /* if list is empty, create it (start with eight points) */
93
    if (index == NULL) {
94
        index = malloc(sizeof(struct access));
95
        if (index == NULL) return NULL;
96
        index->list = malloc(sizeof(struct point) << 3);
97
        if (index->list == NULL) {
98
            free(index);
99
            return NULL;
100
        }
101
        index->size = 8;
102
        index->have = 0;
103
    }
104
 
105
    /* if list is full, make it bigger */
106
    else if (index->have == index->size) {
107
        index->size <<= 1;
108
        next = realloc(index->list, sizeof(struct point) * index->size);
109
        if (next == NULL) {
110
            free_index(index);
111
            return NULL;
112
        }
113
        index->list = next;
114
    }
115
 
116
    /* fill in entry and increment how many we have */
117
    next = index->list + index->have;
118
    next->bits = bits;
119
    next->in = in;
120
    next->out = out;
121
    if (left)
122
        memcpy(next->window, window + WINSIZE - left, left);
123
    if (left < WINSIZE)
124
        memcpy(next->window + left, window, WINSIZE - left);
125
    index->have++;
126
 
127
    /* return list, possibly reallocated */
128
    return index;
129
}
130
 
131
/* Make one entire pass through the compressed stream and build an index, with
132
   access points about every span bytes of uncompressed output -- span is
133
   chosen to balance the speed of random access against the memory requirements
134
   of the list, about 32K bytes per access point.  Note that data after the end
135
   of the first zlib or gzip stream in the file is ignored.  build_index()
136
   returns the number of access points on success (>= 1), Z_MEM_ERROR for out
137
   of memory, Z_DATA_ERROR for an error in the input file, or Z_ERRNO for a
138
   file read error.  On success, *built points to the resulting index. */
139
local int build_index(FILE *in, off_t span, struct access **built)
140
{
141
    int ret;
142
    off_t totin, totout;        /* our own total counters to avoid 4GB limit */
143
    off_t last;                 /* totout value of last access point */
144
    struct access *index;       /* access points being generated */
145
    z_stream strm;
146
    unsigned char input[CHUNK];
147
    unsigned char window[WINSIZE];
148
 
149
    /* initialize inflate */
150
    strm.zalloc = Z_NULL;
151
    strm.zfree = Z_NULL;
152
    strm.opaque = Z_NULL;
153
    strm.avail_in = 0;
154
    strm.next_in = Z_NULL;
155
    ret = inflateInit2(&strm, 47);      /* automatic zlib or gzip decoding */
156
    if (ret != Z_OK)
157
        return ret;
158
 
159
    /* inflate the input, maintain a sliding window, and build an index -- this
160
       also validates the integrity of the compressed data using the check
161
       information at the end of the gzip or zlib stream */
162
    totin = totout = last = 0;
163
    index = NULL;               /* will be allocated by first addpoint() */
164
    strm.avail_out = 0;
165
    do {
166
        /* get some compressed data from input file */
167
        strm.avail_in = fread(input, 1, CHUNK, in);
168
        if (ferror(in)) {
169
            ret = Z_ERRNO;
170
            goto build_index_error;
171
        }
172
        if (strm.avail_in == 0) {
173
            ret = Z_DATA_ERROR;
174
            goto build_index_error;
175
        }
176
        strm.next_in = input;
177
 
178
        /* process all of that, or until end of stream */
179
        do {
180
            /* reset sliding window if necessary */
181
            if (strm.avail_out == 0) {
182
                strm.avail_out = WINSIZE;
183
                strm.next_out = window;
184
            }
185
 
186
            /* inflate until out of input, output, or at end of block --
187
               update the total input and output counters */
188
            totin += strm.avail_in;
189
            totout += strm.avail_out;
190
            ret = inflate(&strm, Z_BLOCK);      /* return at end of block */
191
            totin -= strm.avail_in;
192
            totout -= strm.avail_out;
193
            if (ret == Z_NEED_DICT)
194
                ret = Z_DATA_ERROR;
195
            if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR)
196
                goto build_index_error;
197
            if (ret == Z_STREAM_END)
198
                break;
199
 
200
            /* if at end of block, consider adding an index entry (note that if
201
               data_type indicates an end-of-block, then all of the
202
               uncompressed data from that block has been delivered, and none
203
               of the compressed data after that block has been consumed,
204
               except for up to seven bits) -- the totout == 0 provides an
205
               entry point after the zlib or gzip header, and assures that the
206
               index always has at least one access point; we avoid creating an
207
               access point after the last block by checking bit 6 of data_type
208
             */
209
            if ((strm.data_type & 128) && !(strm.data_type & 64) &&
210
                (totout == 0 || totout - last > span)) {
211
                index = addpoint(index, strm.data_type & 7, totin,
212
                                 totout, strm.avail_out, window);
213
                if (index == NULL) {
214
                    ret = Z_MEM_ERROR;
215
                    goto build_index_error;
216
                }
217
                last = totout;
218
            }
219
        } while (strm.avail_in != 0);
220
    } while (ret != Z_STREAM_END);
221
 
222
    /* clean up and return index (release unused entries in list) */
223
    (void)inflateEnd(&strm);
224
    index = realloc(index, sizeof(struct point) * index->have);
225
    index->size = index->have;
226
    *built = index;
227
    return index->size;
228
 
229
    /* return error */
230
  build_index_error:
231
    (void)inflateEnd(&strm);
232
    if (index != NULL)
233
        free_index(index);
234
    return ret;
235
}
236
 
237
/* Use the index to read len bytes from offset into buf, return bytes read or
238
   negative for error (Z_DATA_ERROR or Z_MEM_ERROR).  If data is requested past
239
   the end of the uncompressed data, then extract() will return a value less
240
   than len, indicating how much as actually read into buf.  This function
241
   should not return a data error unless the file was modified since the index
242
   was generated.  extract() may also return Z_ERRNO if there is an error on
243
   reading or seeking the input file. */
244
local int extract(FILE *in, struct access *index, off_t offset,
245
                  unsigned char *buf, int len)
246
{
247
    int ret, skip;
248
    z_stream strm;
249
    struct point *here;
250
    unsigned char input[CHUNK];
251
    unsigned char discard[WINSIZE];
252
 
253
    /* proceed only if something reasonable to do */
254
    if (len < 0)
255
        return 0;
256
 
257
    /* find where in stream to start */
258
    here = index->list;
259
    ret = index->have;
260
    while (--ret && here[1].out <= offset)
261
        here++;
262
 
263
    /* initialize file and inflate state to start there */
264
    strm.zalloc = Z_NULL;
265
    strm.zfree = Z_NULL;
266
    strm.opaque = Z_NULL;
267
    strm.avail_in = 0;
268
    strm.next_in = Z_NULL;
269
    ret = inflateInit2(&strm, -15);         /* raw inflate */
270
    if (ret != Z_OK)
271
        return ret;
272
    ret = fseeko(in, here->in - (here->bits ? 1 : 0), SEEK_SET);
273
    if (ret == -1)
274
        goto extract_ret;
275
    if (here->bits) {
276
        ret = getc(in);
277
        if (ret == -1) {
278
            ret = ferror(in) ? Z_ERRNO : Z_DATA_ERROR;
279
            goto extract_ret;
280
        }
281
        (void)inflatePrime(&strm, here->bits, ret >> (8 - here->bits));
282
    }
283
    (void)inflateSetDictionary(&strm, here->window, WINSIZE);
284
 
285
    /* skip uncompressed bytes until offset reached, then satisfy request */
286
    offset -= here->out;
287
    strm.avail_in = 0;
288
    skip = 1;                               /* while skipping to offset */
289
    do {
290
        /* define where to put uncompressed data, and how much */
291
        if (offset == 0 && skip) {          /* at offset now */
292
            strm.avail_out = len;
293
            strm.next_out = buf;
294
            skip = 0;                       /* only do this once */
295
        }
296
        if (offset > WINSIZE) {             /* skip WINSIZE bytes */
297
            strm.avail_out = WINSIZE;
298
            strm.next_out = discard;
299
            offset -= WINSIZE;
300
        }
301
        else if (offset != 0) {             /* last skip */
302
            strm.avail_out = (unsigned)offset;
303
            strm.next_out = discard;
304
            offset = 0;
305
        }
306
 
307
        /* uncompress until avail_out filled, or end of stream */
308
        do {
309
            if (strm.avail_in == 0) {
310
                strm.avail_in = fread(input, 1, CHUNK, in);
311
                if (ferror(in)) {
312
                    ret = Z_ERRNO;
313
                    goto extract_ret;
314
                }
315
                if (strm.avail_in == 0) {
316
                    ret = Z_DATA_ERROR;
317
                    goto extract_ret;
318
                }
319
                strm.next_in = input;
320
            }
321
            ret = inflate(&strm, Z_NO_FLUSH);       /* normal inflate */
322
            if (ret == Z_NEED_DICT)
323
                ret = Z_DATA_ERROR;
324
            if (ret == Z_MEM_ERROR || ret == Z_DATA_ERROR)
325
                goto extract_ret;
326
            if (ret == Z_STREAM_END)
327
                break;
328
        } while (strm.avail_out != 0);
329
 
330
        /* if reach end of stream, then don't keep trying to get more */
331
        if (ret == Z_STREAM_END)
332
            break;
333
 
334
        /* do until offset reached and requested data read, or stream ends */
335
    } while (skip);
336
 
337
    /* compute number of uncompressed bytes read after offset */
338
    ret = skip ? 0 : len - strm.avail_out;
339
 
340
    /* clean up and return bytes read or error */
341
  extract_ret:
342
    (void)inflateEnd(&strm);
343
    return ret;
344
}
345
 
346
/* Demonstrate the use of build_index() and extract() by processing the file
347
   provided on the command line, and the extracting 16K from about 2/3rds of
348
   the way through the uncompressed output, and writing that to stdout. */
349
int main(int argc, char **argv)
350
{
351
    int len;
352
    off_t offset;
353
    FILE *in;
354
    struct access *index;
355
    unsigned char buf[CHUNK];
356
 
357
    /* open input file */
358
    if (argc != 2) {
359
        fprintf(stderr, "usage: zran file.gz\n");
360
        return 1;
361
    }
362
    in = fopen(argv[1], "rb");
363
    if (in == NULL) {
364
        fprintf(stderr, "zran: could not open %s for reading\n", argv[1]);
365
        return 1;
366
    }
367
 
368
    /* build index */
369
    len = build_index(in, SPAN, &index);
370
    if (len < 0) {
371
        fclose(in);
372
        switch (len) {
373
        case Z_MEM_ERROR:
374
            fprintf(stderr, "zran: out of memory\n");
375
            break;
376
        case Z_DATA_ERROR:
377
            fprintf(stderr, "zran: compressed data error in %s\n", argv[1]);
378
            break;
379
        case Z_ERRNO:
380
            fprintf(stderr, "zran: read error on %s\n", argv[1]);
381
            break;
382
        default:
383
            fprintf(stderr, "zran: error %d while building index\n", len);
384
        }
385
        return 1;
386
    }
387
    fprintf(stderr, "zran: built index with %d access points\n", len);
388
 
389
    /* use index by reading some bytes from an arbitrary offset */
390
    offset = (index->list[index->have - 1].out << 1) / 3;
391
    len = extract(in, index, offset, buf, CHUNK);
392
    if (len < 0)
393
        fprintf(stderr, "zran: extraction failed: %s error\n",
394
                len == Z_MEM_ERROR ? "out of memory" : "input corrupted");
395
    else {
396
        fwrite(buf, 1, len, stdout);
397
        fprintf(stderr, "zran: extracted %d bytes at %llu\n", len, offset);
398
    }
399
 
400
    /* clean up and exit */
401
    free_index(index);
402
    fclose(in);
403
    return 0;
404
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.