unthwack.c - vx32 - Local 9vx git repository for patches.
(HTM) git clone git://r-36.net/vx32
(DIR) Log
(DIR) Files
(DIR) Refs
---
unthwack.c (5251B)
---
1 #include "u.h"
2 #include "lib.h"
3 #include "mem.h"
4 #include "dat.h"
5 #include "fns.h"
6
7 #include "thwack.h"
8
9 enum
10 {
11 DMaxFastLen = 7,
12 DBigLenCode = 0x3c, /* minimum code for large lenth encoding */
13 DBigLenBits = 6,
14 DBigLenBase = 1 /* starting items to encode for big lens */
15 };
16
17 static uchar lenval[1 << (DBigLenBits - 1)] =
18 {
19 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
20 3, 3, 3, 3, 3, 3, 3, 3,
21 4, 4, 4, 4,
22 5,
23 6,
24 255,
25 255
26 };
27
28 static uchar lenbits[] =
29 {
30 0, 0, 0,
31 2, 3, 5, 5,
32 };
33
34 static uchar offbits[16] =
35 {
36 5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 13
37 };
38
39 static ushort offbase[16] =
40 {
41 0, 0x20,
42 0x40, 0x60,
43 0x80, 0xc0,
44 0x100, 0x180,
45 0x200, 0x300,
46 0x400, 0x600,
47 0x800, 0xc00,
48 0x1000,
49 0x2000
50 };
51
52 void
53 unthwackinit(Unthwack *ut)
54 {
55 int i;
56
57 memset(ut, 0, sizeof *ut);
58 for(i = 0; i < DWinBlocks; i++)
59 ut->blocks[i].data = ut->data[i];
60 }
61
62 ulong
63 unthwackstate(Unthwack *ut, uchar *mask)
64 {
65 ulong bseq, seq;
66 int slot, m;
67
68 seq = ~0UL;
69 m = 0;
70 slot = ut->slot;
71 for(;;){
72 slot--;
73 if(slot < 0)
74 slot += DWinBlocks;
75 if(slot == ut->slot)
76 break;
77 if(ut->blocks[slot].maxoff == 0)
78 continue;
79 bseq = ut->blocks[slot].seq;
80 if(seq == ~0UL)
81 seq = bseq;
82 else if(seq - bseq > MaxSeqMask)
83 break;
84 else
85 m |= 1 << (seq - bseq - 1);
86 }
87 *mask = m;
88 return seq;
89 }
90
91 /*
92 * insert this block in it's correct sequence number order.
93 * replace the oldest block, which is always pointed to by ut->slot.
94 * the encoder doesn't use a history at wraparound,
95 * so don't worry about that case.
96 */
97 static int
98 unthwackinsert(Unthwack *ut, int len, ulong seq)
99 {
100 uchar *d;
101 int slot, tslot;
102
103 tslot = ut->slot;
104 for(;;){
105 slot = tslot - 1;
106 if(slot < 0)
107 slot += DWinBlocks;
108 if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0)
109 break;
110 d = ut->blocks[tslot].data;
111 ut->blocks[tslot] = ut->blocks[slot];
112 ut->blocks[slot].data = d;
113 tslot = slot;
114 }
115 ut->blocks[tslot].seq = seq;
116 ut->blocks[tslot].maxoff = len;
117
118 ut->slot++;
119 if(ut->slot >= DWinBlocks)
120 ut->slot = 0;
121
122 ut->blocks[ut->slot].seq = ~0UL;
123 ut->blocks[ut->slot].maxoff = 0;
124
125 return tslot;
126 }
127
128 int
129 unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
130 {
131 UnthwBlock blocks[CompBlocks], *b, *eblocks;
132 uchar *s, *d, *dmax, *smax, lit;
133 ulong cmask, cseq, bseq, utbits;
134 int i, off, len, bits, slot, use, code, utnbits, overbits, lithist;
135
136 if(nsrc < 4 || nsrc > ThwMaxBlock)
137 return -1;
138
139 slot = ut->slot;
140 b = blocks;
141 *b = ut->blocks[slot];
142 d = b->data;
143 dmax = d + ndst;
144
145 /*
146 * set up the history blocks
147 */
148 cseq = seq - src[0];
149 cmask = src[1];
150 b++;
151 while(cseq != seq && b < blocks + CompBlocks){
152 slot--;
153 if(slot < 0)
154 slot += DWinBlocks;
155 if(slot == ut->slot)
156 break;
157 bseq = ut->blocks[slot].seq;
158 if(bseq == cseq){
159 *b = ut->blocks[slot];
160 b++;
161 if(cmask == 0){
162 cseq = seq;
163 break;
164 }
165 do{
166 bits = cmask & 1;
167 cseq--;
168 cmask >>= 1;
169 }while(!bits);
170 }
171 }
172 eblocks = b;
173 if(cseq != seq){
174 print("blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n", seq, cseq, src[0], cmask, src[1]);
175 return -2;
176 }
177
178 smax = src + nsrc;
179 src += 2;
180 utnbits = 0;
181 utbits = 0;
182 overbits = 0;
183 lithist = ~0;
184 while(src < smax || utnbits - overbits >= MinDecode){
185 while(utnbits <= 24){
186 utbits <<= 8;
187 if(src < smax)
188 utbits |= *src++;
189 else
190 overbits += 8;
191 utnbits += 8;
192 }
193
194 /*
195 * literal
196 */
197 len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
198 if(len == 0){
199 if(lithist & 0xf){
200 utnbits -= 9;
201 lit = (utbits >> utnbits) & 0xff;
202 lit &= 255;
203 }else{
204 utnbits -= 8;
205 lit = (utbits >> utnbits) & 0x7f;
206 if(lit < 32){
207 if(lit < 24){
208 utnbits -= 2;
209 lit = (lit << 2) | ((utbits >> utnbits) & 3);
210 }else{
211 utnbits -= 3;
212 lit = (lit << 3) | ((utbits >> utnbits) & 7);
213 }
214 lit = (lit - 64) & 0xff;
215 }
216 }
217 if(d >= dmax)
218 return -1;
219 *d++ = lit;
220 lithist = (lithist << 1) | (lit < 32) | (lit > 127);
221 blocks->maxoff++;
222 continue;
223 }
224
225 /*
226 * length
227 */
228 if(len < 255)
229 utnbits -= lenbits[len];
230 else{
231 utnbits -= DBigLenBits;
232 code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
233 len = DMaxFastLen;
234 use = DBigLenBase;
235 bits = (DBigLenBits & 1) ^ 1;
236 while(code >= use){
237 len += use;
238 code -= use;
239 code <<= 1;
240 utnbits--;
241 if(utnbits < 0)
242 return -1;
243 code |= (utbits >> utnbits) & 1;
244 use <<= bits;
245 bits ^= 1;
246 }
247 len += code;
248
249 while(utnbits <= 24){
250 utbits <<= 8;
251 if(src < smax)
252 utbits |= *src++;
253 else
254 overbits += 8;
255 utnbits += 8;
256 }
257 }
258
259 /*
260 * offset
261 */
262 utnbits -= 4;
263 bits = (utbits >> utnbits) & 0xf;
264 off = offbase[bits];
265 bits = offbits[bits];
266
267 utnbits -= bits;
268 off |= (utbits >> utnbits) & ((1 << bits) - 1);
269 off++;
270
271 b = blocks;
272 while(off > b->maxoff){
273 off -= b->maxoff;
274 b++;
275 if(b >= eblocks)
276 return -1;
277 }
278 if(d + len > dmax
279 || (b != blocks && len > off))
280 return -1;
281 s = b->data + b->maxoff - off;
282 blocks->maxoff += len;
283
284 for(i = 0; i < len; i++)
285 d[i] = s[i];
286 d += len;
287 }
288 if(utnbits < overbits)
289 return -1;
290
291 len = d - blocks->data;
292 memmove(dst, blocks->data, len);
293
294 unthwackinsert(ut, len, seq);
295
296 return len;
297 }