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
unthwackinit(Unthwack * ut)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
unthwackstate(Unthwack * ut,uchar * mask)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
unthwackinsert(Unthwack * ut,int len,ulong seq)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
unthwack(Unthwack * ut,uchar * dst,int ndst,uchar * src,int nsrc,ulong seq)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("unthwack: blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n",
175 seq, cseq, src[0], cmask, src[1]);
176 return -2;
177 }
178
179 smax = src + nsrc;
180 src += 2;
181 utnbits = 0;
182 utbits = 0;
183 overbits = 0;
184 lithist = ~0;
185 while(src < smax || utnbits - overbits >= MinDecode){
186 while(utnbits <= 24){
187 utbits <<= 8;
188 if(src < smax)
189 utbits |= *src++;
190 else
191 overbits += 8;
192 utnbits += 8;
193 }
194
195 /*
196 * literal
197 */
198 len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
199 if(len == 0){
200 if(lithist & 0xf){
201 utnbits -= 9;
202 lit = (utbits >> utnbits) & 0xff;
203 lit &= 255;
204 }else{
205 utnbits -= 8;
206 lit = (utbits >> utnbits) & 0x7f;
207 if(lit < 32){
208 if(lit < 24){
209 utnbits -= 2;
210 lit = (lit << 2) | ((utbits >> utnbits) & 3);
211 }else{
212 utnbits -= 3;
213 lit = (lit << 3) | ((utbits >> utnbits) & 7);
214 }
215 lit = (lit - 64) & 0xff;
216 }
217 }
218 if(d >= dmax)
219 return -1;
220 *d++ = lit;
221 lithist = (lithist << 1) | (lit < 32) | (lit > 127);
222 blocks->maxoff++;
223 continue;
224 }
225
226 /*
227 * length
228 */
229 if(len < 255)
230 utnbits -= lenbits[len];
231 else{
232 utnbits -= DBigLenBits;
233 code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
234 len = DMaxFastLen;
235 use = DBigLenBase;
236 bits = (DBigLenBits & 1) ^ 1;
237 while(code >= use){
238 len += use;
239 code -= use;
240 code <<= 1;
241 utnbits--;
242 if(utnbits < 0)
243 return -1;
244 code |= (utbits >> utnbits) & 1;
245 use <<= bits;
246 bits ^= 1;
247 }
248 len += code;
249
250 while(utnbits <= 24){
251 utbits <<= 8;
252 if(src < smax)
253 utbits |= *src++;
254 else
255 overbits += 8;
256 utnbits += 8;
257 }
258 }
259
260 /*
261 * offset
262 */
263 utnbits -= 4;
264 bits = (utbits >> utnbits) & 0xf;
265 off = offbase[bits];
266 bits = offbits[bits];
267
268 utnbits -= bits;
269 off |= (utbits >> utnbits) & ((1 << bits) - 1);
270 off++;
271
272 b = blocks;
273 while(off > b->maxoff){
274 off -= b->maxoff;
275 b++;
276 if(b >= eblocks)
277 return -1;
278 }
279 if(d + len > dmax
280 || b != blocks && len > off)
281 return -1;
282 s = b->data + b->maxoff - off;
283 blocks->maxoff += len;
284
285 for(i = 0; i < len; i++)
286 d[i] = s[i];
287 d += len;
288 }
289 if(utnbits < overbits)
290 return -1;
291
292 len = d - blocks->data;
293 memmove(dst, blocks->data, len);
294
295 unthwackinsert(ut, len, seq);
296
297 return len;
298 }
299