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