ยปCore Development>Code coverage>Modules/zlib/inffast.c

Python code coverage for Modules/zlib/inffast.c

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