annotate zlib/inffast.c @ 15:d28f3d01043c

Add code to make nebulous terrain increase penetration of sheilds.
author darius
date Sat, 06 Dec 1997 15:21:57 +0000
parents 1040ca591f2e
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
10
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
1 /* inffast.c -- process literals and length/distance pairs fast
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
2 * Copyright (C) 1995 Mark Adler
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
3 * For conditions of distribution and use, see copyright notice in zlib.h
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
4 */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
5
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
6 #include "zutil.h"
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
7 #include "inftrees.h"
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
8 #include "infblock.h"
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
9 #include "infcodes.h"
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
10 #include "infutil.h"
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
11 #include "inffast.h"
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
12
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
13 struct inflate_codes_state {int dummy;}; /* for buggy compilers */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
14
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
15 /* simplify the use of the inflate_huft type with some defines */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
16 #define base more.Base
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
17 #define next more.Next
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
18 #define exop word.what.Exop
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
19 #define bits word.what.Bits
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
20
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
21 /* macros for bit input with no checking and for returning unused bytes */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
22 #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
23 #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
24
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
25 /* Called with number of bytes left to write in window at least 258
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
26 (the maximum string length) and number of input bytes available
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
27 at least ten. The ten bytes are six bytes for the longest length/
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
28 distance pair plus four bytes for overloading the bit buffer. */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
29
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
30 int inflate_fast(bl, bd, tl, td, s, z)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
31 uInt bl, bd;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
32 inflate_huft *tl, *td;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
33 inflate_blocks_statef *s;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
34 z_stream *z;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
35 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
36 inflate_huft *t; /* temporary pointer */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
37 uInt e; /* extra bits or operation */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
38 uLong b; /* bit buffer */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
39 uInt k; /* bits in bit buffer */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
40 Bytef *p; /* input data pointer */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
41 uInt n; /* bytes available there */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
42 Bytef *q; /* output window write pointer */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
43 uInt m; /* bytes to end of window or read pointer */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
44 uInt ml; /* mask for literal/length tree */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
45 uInt md; /* mask for distance tree */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
46 uInt c; /* bytes to copy */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
47 uInt d; /* distance back to copy from */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
48 Bytef *r; /* copy source pointer */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
49
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
50 /* load input, output, bit values */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
51 LOAD
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
52
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
53 /* initialize masks */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
54 ml = inflate_mask[bl];
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
55 md = inflate_mask[bd];
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
56
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
57 /* do until not enough input or output space for fast loop */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
58 do { /* assume called with m >= 258 && n >= 10 */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
59 /* get literal/length code */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
60 GRABBITS(20) /* max bits for literal/length code */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
61 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
62 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
63 DUMPBITS(t->bits)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
64 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
65 "inflate: * literal '%c'\n" :
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
66 "inflate: * literal 0x%02x\n", t->base));
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
67 *q++ = (Byte)t->base;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
68 m--;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
69 continue;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
70 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
71 do {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
72 DUMPBITS(t->bits)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
73 if (e & 16)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
74 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
75 /* get extra bits for length */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
76 e &= 15;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
77 c = t->base + ((uInt)b & inflate_mask[e]);
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
78 DUMPBITS(e)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
79 Tracevv((stderr, "inflate: * length %u\n", c));
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
80
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
81 /* decode distance base of block to copy */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
82 GRABBITS(15); /* max bits for distance code */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
83 e = (t = td + ((uInt)b & md))->exop;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
84 do {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
85 DUMPBITS(t->bits)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
86 if (e & 16)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
87 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
88 /* get extra bits to add to distance base */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
89 e &= 15;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
90 GRABBITS(e) /* get extra bits (up to 13) */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
91 d = t->base + ((uInt)b & inflate_mask[e]);
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
92 DUMPBITS(e)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
93 Tracevv((stderr, "inflate: * distance %u\n", d));
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
94
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
95 /* do the copy */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
96 m -= c;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
97 if ((uInt)(q - s->window) >= d) /* offset before dest */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
98 { /* just copy */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
99 r = q - d;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
100 *q++ = *r++; c--; /* minimum count is three, */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
101 *q++ = *r++; c--; /* so unroll loop a little */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
102 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
103 else /* else offset after destination */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
104 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
105 e = d - (q - s->window); /* bytes from offset to end */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
106 r = s->end - e; /* pointer to offset */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
107 if (c > e) /* if source crosses, */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
108 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
109 c -= e; /* copy to end of window */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
110 do {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
111 *q++ = *r++;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
112 } while (--e);
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
113 r = s->window; /* copy rest from start of window */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
114 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
115 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
116 do { /* copy all or what's left */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
117 *q++ = *r++;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
118 } while (--c);
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
119 break;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
120 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
121 else if ((e & 64) == 0)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
122 e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
123 else
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
124 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
125 z->msg = "invalid distance code";
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
126 UNGRAB
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
127 UPDATE
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
128 return Z_DATA_ERROR;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
129 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
130 } while (1);
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
131 break;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
132 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
133 if ((e & 64) == 0)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
134 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
135 if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
136 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
137 DUMPBITS(t->bits)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
138 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
139 "inflate: * literal '%c'\n" :
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
140 "inflate: * literal 0x%02x\n", t->base));
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
141 *q++ = (Byte)t->base;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
142 m--;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
143 break;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
144 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
145 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
146 else if (e & 32)
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
147 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
148 Tracevv((stderr, "inflate: * end of block\n"));
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
149 UNGRAB
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
150 UPDATE
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
151 return Z_STREAM_END;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
152 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
153 else
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
154 {
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
155 z->msg = "invalid literal/length code";
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
156 UNGRAB
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
157 UPDATE
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
158 return Z_DATA_ERROR;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
159 }
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
160 } while (1);
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
161 } while (m >= 258 && n >= 10);
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
162
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
163 /* not enough input or output--restore pointers and return */
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
164 UNGRAB
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
165 UPDATE
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
166 return Z_OK;
1040ca591f2e First entry of Paradise Server 2.9 patch 10 Beta
darius
parents:
diff changeset
167 }