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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [rtos/] [ecos-3.0/] [packages/] [services/] [compress/] [zlib/] [current/] [src/] [inffast.c] - Blame information for rev 786

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 786 skrzyp
/* inffast.c -- fast decoding
2
 * Copyright (C) 1995-2004 Mark Adler
3
 * For conditions of distribution and use, see copyright notice in zlib.h
4
 */
5
 
6
#include "zutil.h"
7
#include "inftrees.h"
8
#include "inflate.h"
9
#include "inffast.h"
10
 
11
#ifndef ASMINF
12
 
13
/* Allow machine dependent optimization for post-increment or pre-increment.
14
   Based on testing to date,
15
   Pre-increment preferred for:
16
   - PowerPC G3 (Adler)
17
   - MIPS R5000 (Randers-Pehrson)
18
   Post-increment preferred for:
19
   - none
20
   No measurable difference:
21
   - Pentium III (Anderson)
22
   - M68060 (Nikl)
23
 */
24
#ifdef POSTINC
25
#  define OFF 0
26
#  define PUP(a) *(a)++
27
#else
28
#  define OFF 1
29
#  define PUP(a) *++(a)
30
#endif
31
 
32
/*
33
   Decode literal, length, and distance codes and write out the resulting
34
   literal and match bytes until either not enough input or output is
35
   available, an end-of-block is encountered, or a data error is encountered.
36
   When large enough input and output buffers are supplied to inflate(), for
37
   example, a 16K input buffer and a 64K output buffer, more than 95% of the
38
   inflate execution time is spent in this routine.
39
 
40
   Entry assumptions:
41
 
42
        state->mode == LEN
43
        strm->avail_in >= 6
44
        strm->avail_out >= 258
45
        start >= strm->avail_out
46
        state->bits < 8
47
 
48
   On return, state->mode is one of:
49
 
50
        LEN -- ran out of enough output space or enough available input
51
        TYPE -- reached end of block code, inflate() to interpret next block
52
        BAD -- error in block data
53
 
54
   Notes:
55
 
56
    - The maximum input bits used by a length/distance pair is 15 bits for the
57
      length code, 5 bits for the length extra, 15 bits for the distance code,
58
      and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
59
      Therefore if strm->avail_in >= 6, then there is enough input to avoid
60
      checking for available input while decoding.
61
 
62
    - The maximum bytes that a single length/distance pair can output is 258
63
      bytes, which is the maximum length that can be coded.  inflate_fast()
64
      requires strm->avail_out >= 258 for each loop to avoid checking for
65
      output space.
66
 */
67
void inflate_fast(strm, start)
68
z_streamp strm;
69
unsigned start;         /* inflate()'s starting value for strm->avail_out */
70
{
71
    struct inflate_state FAR *state;
72
    unsigned char FAR *in;      /* local strm->next_in */
73
    unsigned char FAR *last;    /* while in < last, enough input available */
74
    unsigned char FAR *out;     /* local strm->next_out */
75
    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
76
    unsigned char FAR *end;     /* while out < end, enough space available */
77
#ifdef INFLATE_STRICT
78
    unsigned dmax;              /* maximum distance from zlib header */
79
#endif
80
    unsigned wsize;             /* window size or zero if not using window */
81
    unsigned whave;             /* valid bytes in the window */
82
    unsigned write;             /* window write index */
83
    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
84
    unsigned long hold;         /* local strm->hold */
85
    unsigned bits;              /* local strm->bits */
86
    code const FAR *lcode;      /* local strm->lencode */
87
    code const FAR *dcode;      /* local strm->distcode */
88
    unsigned lmask;             /* mask for first level of length codes */
89
    unsigned dmask;             /* mask for first level of distance codes */
90
    code this;                  /* retrieved table entry */
91
    unsigned op;                /* code bits, operation, extra bits, or */
92
                                /*  window position, window bytes to copy */
93
    unsigned len;               /* match length, unused bytes */
94
    unsigned dist;              /* match distance */
95
    unsigned char FAR *from;    /* where to copy match from */
96
 
97
    /* copy state to local variables */
98
    state = (struct inflate_state FAR *)strm->state;
99
    in = strm->next_in - OFF;
100
    last = in + (strm->avail_in - 5);
101
    out = strm->next_out - OFF;
102
    beg = out - (start - strm->avail_out);
103
    end = out + (strm->avail_out - 257);
104
#ifdef INFLATE_STRICT
105
    dmax = state->dmax;
106
#endif
107
    wsize = state->wsize;
108
    whave = state->whave;
109
    write = state->write;
110
    window = state->window;
111
    hold = state->hold;
112
    bits = state->bits;
113
    lcode = state->lencode;
114
    dcode = state->distcode;
115
    lmask = (1U << state->lenbits) - 1;
116
    dmask = (1U << state->distbits) - 1;
117
 
118
    /* decode literals and length/distances until end-of-block or not enough
119
       input data or output space */
120
    do {
121
        if (bits < 15) {
122
            hold += (unsigned long)(PUP(in)) << bits;
123
            bits += 8;
124
            hold += (unsigned long)(PUP(in)) << bits;
125
            bits += 8;
126
        }
127
        this = lcode[hold & lmask];
128
      dolen:
129
        op = (unsigned)(this.bits);
130
        hold >>= op;
131
        bits -= op;
132
        op = (unsigned)(this.op);
133
        if (op == 0) {                          /* literal */
134
            Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
135
                    "inflate:         literal '%c'\n" :
136
                    "inflate:         literal 0x%02x\n", this.val));
137
            PUP(out) = (unsigned char)(this.val);
138
        }
139
        else if (op & 16) {                     /* length base */
140
            len = (unsigned)(this.val);
141
            op &= 15;                           /* number of extra bits */
142
            if (op) {
143
                if (bits < op) {
144
                    hold += (unsigned long)(PUP(in)) << bits;
145
                    bits += 8;
146
                }
147
                len += (unsigned)hold & ((1U << op) - 1);
148
                hold >>= op;
149
                bits -= op;
150
            }
151
            Tracevv((stderr, "inflate:         length %u\n", len));
152
            if (bits < 15) {
153
                hold += (unsigned long)(PUP(in)) << bits;
154
                bits += 8;
155
                hold += (unsigned long)(PUP(in)) << bits;
156
                bits += 8;
157
            }
158
            this = dcode[hold & dmask];
159
          dodist:
160
            op = (unsigned)(this.bits);
161
            hold >>= op;
162
            bits -= op;
163
            op = (unsigned)(this.op);
164
            if (op & 16) {                      /* distance base */
165
                dist = (unsigned)(this.val);
166
                op &= 15;                       /* number of extra bits */
167
                if (bits < op) {
168
                    hold += (unsigned long)(PUP(in)) << bits;
169
                    bits += 8;
170
                    if (bits < op) {
171
                        hold += (unsigned long)(PUP(in)) << bits;
172
                        bits += 8;
173
                    }
174
                }
175
                dist += (unsigned)hold & ((1U << op) - 1);
176
#ifdef INFLATE_STRICT
177
                if (dist > dmax) {
178
                    strm->msg = (char *)"invalid distance too far back";
179
                    state->mode = BAD;
180
                    break;
181
                }
182
#endif
183
                hold >>= op;
184
                bits -= op;
185
                Tracevv((stderr, "inflate:         distance %u\n", dist));
186
                op = (unsigned)(out - beg);     /* max distance in output */
187
                if (dist > op) {                /* see if copy from window */
188
                    op = dist - op;             /* distance back in window */
189
                    if (op > whave) {
190
                        strm->msg = (char *)"invalid distance too far back";
191
                        state->mode = BAD;
192
                        break;
193
                    }
194
                    from = window - OFF;
195
                    if (write == 0) {           /* very common case */
196
                        from += wsize - op;
197
                        if (op < len) {         /* some from window */
198
                            len -= op;
199
                            do {
200
                                PUP(out) = PUP(from);
201
                            } while (--op);
202
                            from = out - dist;  /* rest from output */
203
                        }
204
                    }
205
                    else if (write < op) {      /* wrap around window */
206
                        from += wsize + write - op;
207
                        op -= write;
208
                        if (op < len) {         /* some from end of window */
209
                            len -= op;
210
                            do {
211
                                PUP(out) = PUP(from);
212
                            } while (--op);
213
                            from = window - OFF;
214
                            if (write < len) {  /* some from start of window */
215
                                op = write;
216
                                len -= op;
217
                                do {
218
                                    PUP(out) = PUP(from);
219
                                } while (--op);
220
                                from = out - dist;      /* rest from output */
221
                            }
222
                        }
223
                    }
224
                    else {                      /* contiguous in window */
225
                        from += write - op;
226
                        if (op < len) {         /* some from window */
227
                            len -= op;
228
                            do {
229
                                PUP(out) = PUP(from);
230
                            } while (--op);
231
                            from = out - dist;  /* rest from output */
232
                        }
233
                    }
234
                    while (len > 2) {
235
                        PUP(out) = PUP(from);
236
                        PUP(out) = PUP(from);
237
                        PUP(out) = PUP(from);
238
                        len -= 3;
239
                    }
240
                    if (len) {
241
                        PUP(out) = PUP(from);
242
                        if (len > 1)
243
                            PUP(out) = PUP(from);
244
                    }
245
                }
246
                else {
247
                    from = out - dist;          /* copy direct from output */
248
                    do {                        /* minimum length is three */
249
                        PUP(out) = PUP(from);
250
                        PUP(out) = PUP(from);
251
                        PUP(out) = PUP(from);
252
                        len -= 3;
253
                    } while (len > 2);
254
                    if (len) {
255
                        PUP(out) = PUP(from);
256
                        if (len > 1)
257
                            PUP(out) = PUP(from);
258
                    }
259
                }
260
            }
261
            else if ((op & 64) == 0) {          /* 2nd level distance code */
262
                this = dcode[this.val + (hold & ((1U << op) - 1))];
263
                goto dodist;
264
            }
265
            else {
266
                strm->msg = (char *)"invalid distance code";
267
                state->mode = BAD;
268
                break;
269
            }
270
        }
271
        else if ((op & 64) == 0) {              /* 2nd level length code */
272
            this = lcode[this.val + (hold & ((1U << op) - 1))];
273
            goto dolen;
274
        }
275
        else if (op & 32) {                     /* end-of-block */
276
            Tracevv((stderr, "inflate:         end of block\n"));
277
            state->mode = TYPE;
278
            break;
279
        }
280
        else {
281
            strm->msg = (char *)"invalid literal/length code";
282
            state->mode = BAD;
283
            break;
284
        }
285
    } while (in < last && out < end);
286
 
287
    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
288
    len = bits >> 3;
289
    in -= len;
290
    bits -= len << 3;
291
    hold &= (1U << bits) - 1;
292
 
293
    /* update state and return */
294
    strm->next_in = in + OFF;
295
    strm->next_out = out + OFF;
296
    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
297
    strm->avail_out = (unsigned)(out < end ?
298
                                 257 + (end - out) : 257 - (out - end));
299
    state->hold = hold;
300
    state->bits = bits;
301
    return;
302
}
303
 
304
/*
305
   inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
306
   - Using bit fields for code structure
307
   - Different op definition to avoid & for extra bits (do & for table bits)
308
   - Three separate decoding do-loops for direct, window, and write == 0
309
   - Special case for distance > 1 copies to do overlapped load and store copy
310
   - Explicit branch predictions (based on measured branch probabilities)
311
   - Deferring match copy and interspersed it with decoding subsequent codes
312
   - Swapping literal/length else
313
   - Swapping window/direct else
314
   - Larger unrolled copy loops (three is about right)
315
   - Moving len -= 3 statement into middle of loop
316
 */
317
 
318
#endif /* !ASMINF */

powered by: WebSVN 2.1.0

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