1 | /* $NetBSD: bsd-comp.c,v 1.22 2016/08/06 22:38:18 pgoyette Exp $ */ |
2 | /* Id: bsd-comp.c,v 1.6 1996/08/28 06:31:58 paulus Exp */ |
3 | |
4 | /* Because this code is derived from the 4.3BSD compress source: |
5 | * |
6 | * |
7 | * Copyright (c) 1985, 1986 The Regents of the University of California. |
8 | * All rights reserved. |
9 | * |
10 | * This code is derived from software contributed to Berkeley by |
11 | * James A. Woods, derived from original work by Spencer Thomas |
12 | * and Joseph Orost. |
13 | * |
14 | * Redistribution and use in source and binary forms, with or without |
15 | * modification, are permitted provided that the following conditions |
16 | * are met: |
17 | * 1. Redistributions of source code must retain the above copyright |
18 | * notice, this list of conditions and the following disclaimer. |
19 | * 2. Redistributions in binary form must reproduce the above copyright |
20 | * notice, this list of conditions and the following disclaimer in the |
21 | * documentation and/or other materials provided with the distribution. |
22 | * 3. Neither the name of the University nor the names of its contributors |
23 | * may be used to endorse or promote products derived from this software |
24 | * without specific prior written permission. |
25 | * |
26 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
27 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
28 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
29 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
30 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
31 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
32 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
33 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
34 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
35 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
36 | * SUCH DAMAGE. |
37 | */ |
38 | |
39 | /* |
40 | * This version is for use with mbufs on BSD-derived systems. |
41 | */ |
42 | |
43 | #include <sys/cdefs.h> |
44 | __KERNEL_RCSID(0, "$NetBSD: bsd-comp.c,v 1.22 2016/08/06 22:38:18 pgoyette Exp $" ); |
45 | |
46 | #include <sys/param.h> |
47 | #include <sys/systm.h> |
48 | #include <sys/mbuf.h> |
49 | #include <sys/socket.h> |
50 | #include <sys/module.h> |
51 | #include <net/if.h> |
52 | #include <net/if_types.h> |
53 | #include <net/ppp_defs.h> |
54 | #include <net/if_ppp.h> |
55 | |
56 | #define PACKETPTR struct mbuf * |
57 | #include <net/ppp-comp.h> |
58 | |
59 | #if DO_BSD_COMPRESS |
60 | /* |
61 | * PPP "BSD compress" compression |
62 | * The differences between this compression and the classic BSD LZW |
63 | * source are obvious from the requirement that the classic code worked |
64 | * with files while this handles arbitrarily long streams that |
65 | * are broken into packets. They are: |
66 | * |
67 | * When the code size expands, a block of junk is not emitted by |
68 | * the compressor and not expected by the decompressor. |
69 | * |
70 | * New codes are not necessarily assigned every time an old |
71 | * code is output by the compressor. This is because a packet |
72 | * end forces a code to be emitted, but does not imply that a |
73 | * new sequence has been seen. |
74 | * |
75 | * The compression ratio is checked at the first end of a packet |
76 | * after the appropriate gap. Besides simplifying and speeding |
77 | * things up, this makes it more likely that the transmitter |
78 | * and receiver will agree when the dictionary is cleared when |
79 | * compression is not going well. |
80 | */ |
81 | |
82 | /* |
83 | * A dictionary for doing BSD compress. |
84 | */ |
85 | struct bsd_db { |
86 | int totlen; /* length of this structure */ |
87 | u_int hsize; /* size of the hash table */ |
88 | u_char hshift; /* used in hash function */ |
89 | u_char n_bits; /* current bits/code */ |
90 | u_char maxbits; |
91 | u_char debug; |
92 | u_char unit; |
93 | uint16_t seqno; /* sequence # of next packet */ |
94 | u_int hdrlen; /* header length to preallocate */ |
95 | u_int mru; |
96 | u_int maxmaxcode; /* largest valid code */ |
97 | u_int max_ent; /* largest code in use */ |
98 | u_int in_count; /* uncompressed bytes, aged */ |
99 | u_int bytes_out; /* compressed bytes, aged */ |
100 | u_int ratio; /* recent compression ratio */ |
101 | u_int checkpoint; /* when to next check the ratio */ |
102 | u_int clear_count; /* times dictionary cleared */ |
103 | u_int incomp_count; /* incompressible packets */ |
104 | u_int incomp_bytes; /* incompressible bytes */ |
105 | u_int uncomp_count; /* uncompressed packets */ |
106 | u_int uncomp_bytes; /* uncompressed bytes */ |
107 | u_int comp_count; /* compressed packets */ |
108 | u_int comp_bytes; /* compressed bytes */ |
109 | uint16_t *lens; /* array of lengths of codes */ |
110 | struct bsd_dict { |
111 | union { /* hash value */ |
112 | uint32_t fcode; |
113 | struct { |
114 | #if BYTE_ORDER == LITTLE_ENDIAN |
115 | uint16_t prefix; /* preceding code */ |
116 | u_char suffix; /* last character of new code */ |
117 | u_char pad; |
118 | #else |
119 | u_char pad; |
120 | u_char suffix; /* last character of new code */ |
121 | uint16_t prefix; /* preceding code */ |
122 | #endif |
123 | } hs; |
124 | } f; |
125 | uint16_t codem1; /* output of hash table -1 */ |
126 | uint16_t cptr; /* map code to hash table entry */ |
127 | } dict[1]; |
128 | }; |
129 | |
130 | #define BSD_OVHD 2 /* BSD compress overhead/packet */ |
131 | #define BSD_INIT_BITS BSD_MIN_BITS |
132 | |
133 | static void *bsd_comp_alloc(u_char *options, int opt_len); |
134 | static void *bsd_decomp_alloc(u_char *options, int opt_len); |
135 | static void bsd_free(void *state); |
136 | static int bsd_comp_init(void *state, u_char *options, int opt_len, |
137 | int unit, int hdrlen, int debug); |
138 | static int bsd_decomp_init(void *state, u_char *options, int opt_len, |
139 | int unit, int hdrlen, int mru, int debug); |
140 | static int bsd_compress(void *state, struct mbuf **mret, |
141 | struct mbuf *mp, int slen, int maxolen); |
142 | static void bsd_incomp(void *state, struct mbuf *dmsg); |
143 | static int bsd_decompress(void *state, struct mbuf *cmp, |
144 | struct mbuf **dmpp); |
145 | static void bsd_reset(void *state); |
146 | static void bsd_comp_stats(void *state, struct compstat *stats); |
147 | |
148 | /* |
149 | * Procedures exported to if_ppp.c. |
150 | */ |
151 | static struct compressor ppp_bsd_compress = { |
152 | .compress_proto = CI_BSD_COMPRESS, |
153 | .comp_alloc = bsd_comp_alloc, |
154 | .comp_free = bsd_free, |
155 | .comp_init = bsd_comp_init, |
156 | .comp_reset = bsd_reset, |
157 | .compress = bsd_compress, |
158 | .comp_stat = bsd_comp_stats, |
159 | .decomp_alloc = bsd_decomp_alloc, |
160 | .decomp_free = bsd_free, |
161 | .decomp_init = bsd_decomp_init, |
162 | .decomp_reset = bsd_reset, |
163 | .decompress = bsd_decompress, |
164 | .incomp = bsd_incomp, |
165 | .decomp_stat = bsd_comp_stats, |
166 | }; |
167 | |
168 | /* |
169 | * the next two codes should not be changed lightly, as they must not |
170 | * lie within the contiguous general code space. |
171 | */ |
172 | #define CLEAR 256 /* table clear output code */ |
173 | #define FIRST 257 /* first free entry */ |
174 | #define LAST 255 |
175 | |
176 | #define MAXCODE(b) ((1 << (b)) - 1) |
177 | #define BADCODEM1 MAXCODE(BSD_MAX_BITS) |
178 | |
179 | #define BSD_HASH(prefix,suffix,hshift) ((((uint32_t)(suffix)) << (hshift)) \ |
180 | ^ (uint32_t)(prefix)) |
181 | #define BSD_KEY(prefix,suffix) ((((uint32_t)(suffix)) << 16) \ |
182 | + (uint32_t)(prefix)) |
183 | |
184 | #define CHECK_GAP 10000 /* Ratio check interval */ |
185 | |
186 | #define RATIO_SCALE_LOG 8 |
187 | #define RATIO_SCALE (1<<RATIO_SCALE_LOG) |
188 | #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG) |
189 | |
190 | static void bsd_clear(struct bsd_db *); |
191 | static int bsd_check(struct bsd_db *); |
192 | static void *bsd_alloc(u_char *, int, int); |
193 | static int bsd_init(struct bsd_db *, u_char *, int, int, int, int, |
194 | int, int); |
195 | |
196 | /* |
197 | * clear the dictionary |
198 | */ |
199 | static void |
200 | bsd_clear(struct bsd_db *db) |
201 | { |
202 | db->clear_count++; |
203 | db->max_ent = FIRST-1; |
204 | db->n_bits = BSD_INIT_BITS; |
205 | db->ratio = 0; |
206 | db->bytes_out = 0; |
207 | db->in_count = 0; |
208 | db->checkpoint = CHECK_GAP; |
209 | } |
210 | |
211 | /* |
212 | * If the dictionary is full, then see if it is time to reset it. |
213 | * |
214 | * Compute the compression ratio using fixed-point arithmetic |
215 | * with 8 fractional bits. |
216 | * |
217 | * Since we have an infinite stream instead of a single file, |
218 | * watch only the local compression ratio. |
219 | * |
220 | * Since both peers must reset the dictionary at the same time even in |
221 | * the absence of CLEAR codes (while packets are incompressible), they |
222 | * must compute the same ratio. |
223 | */ |
224 | static int /* 1=output CLEAR */ |
225 | bsd_check(struct bsd_db *db) |
226 | { |
227 | u_int new_ratio; |
228 | |
229 | if (db->in_count >= db->checkpoint) { |
230 | /* age the ratio by limiting the size of the counts */ |
231 | if (db->in_count >= RATIO_MAX |
232 | || db->bytes_out >= RATIO_MAX) { |
233 | db->in_count -= db->in_count/4; |
234 | db->bytes_out -= db->bytes_out/4; |
235 | } |
236 | |
237 | db->checkpoint = db->in_count + CHECK_GAP; |
238 | |
239 | if (db->max_ent >= db->maxmaxcode) { |
240 | /* Reset the dictionary only if the ratio is worse, |
241 | * or if it looks as if it has been poisoned |
242 | * by incompressible data. |
243 | * |
244 | * This does not overflow, because |
245 | * db->in_count <= RATIO_MAX. |
246 | */ |
247 | new_ratio = db->in_count << RATIO_SCALE_LOG; |
248 | if (db->bytes_out != 0) |
249 | new_ratio /= db->bytes_out; |
250 | |
251 | if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE) { |
252 | bsd_clear(db); |
253 | return 1; |
254 | } |
255 | db->ratio = new_ratio; |
256 | } |
257 | } |
258 | return 0; |
259 | } |
260 | |
261 | /* |
262 | * Return statistics. |
263 | */ |
264 | static void |
265 | bsd_comp_stats(void *state, struct compstat *stats) |
266 | { |
267 | struct bsd_db *db = (struct bsd_db *) state; |
268 | u_int out; |
269 | |
270 | stats->unc_bytes = db->uncomp_bytes; |
271 | stats->unc_packets = db->uncomp_count; |
272 | stats->comp_bytes = db->comp_bytes; |
273 | stats->comp_packets = db->comp_count; |
274 | stats->inc_bytes = db->incomp_bytes; |
275 | stats->inc_packets = db->incomp_count; |
276 | stats->ratio = db->in_count; |
277 | out = db->bytes_out; |
278 | if (stats->ratio <= 0x7fffff) |
279 | stats->ratio <<= 8; |
280 | else |
281 | out >>= 8; |
282 | if (out != 0) |
283 | stats->ratio /= out; |
284 | } |
285 | |
286 | /* |
287 | * Reset state, as on a CCP ResetReq. |
288 | */ |
289 | static void |
290 | bsd_reset(void *state) |
291 | { |
292 | struct bsd_db *db = (struct bsd_db *) state; |
293 | |
294 | db->seqno = 0; |
295 | bsd_clear(db); |
296 | db->clear_count = 0; |
297 | } |
298 | |
299 | /* |
300 | * Allocate space for a (de) compressor. |
301 | */ |
302 | static void * |
303 | bsd_alloc(u_char *options, int opt_len, int decomp) |
304 | { |
305 | int bits; |
306 | u_int newlen, hsize, hshift, maxmaxcode; |
307 | struct bsd_db *db; |
308 | |
309 | if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS |
310 | || options[1] != CILEN_BSD_COMPRESS |
311 | || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION) |
312 | return NULL; |
313 | bits = BSD_NBITS(options[2]); |
314 | switch (bits) { |
315 | case 9: /* needs 82152 for both directions */ |
316 | case 10: /* needs 84144 */ |
317 | case 11: /* needs 88240 */ |
318 | case 12: /* needs 96432 */ |
319 | hsize = 5003; |
320 | hshift = 4; |
321 | break; |
322 | case 13: /* needs 176784 */ |
323 | hsize = 9001; |
324 | hshift = 5; |
325 | break; |
326 | case 14: /* needs 353744 */ |
327 | hsize = 18013; |
328 | hshift = 6; |
329 | break; |
330 | case 15: /* needs 691440 */ |
331 | hsize = 35023; |
332 | hshift = 7; |
333 | break; |
334 | case 16: /* needs 1366160--far too much, */ |
335 | /* hsize = 69001; */ /* and 69001 is too big for cptr */ |
336 | /* hshift = 8; */ /* in struct bsd_db */ |
337 | /* break; */ |
338 | default: |
339 | return NULL; |
340 | } |
341 | |
342 | maxmaxcode = MAXCODE(bits); |
343 | newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0])); |
344 | db = malloc(newlen, M_DEVBUF, M_NOWAIT|M_ZERO); |
345 | if (!db) |
346 | return NULL; |
347 | |
348 | if (!decomp) { |
349 | db->lens = NULL; |
350 | } else { |
351 | db->lens = malloc((maxmaxcode+1) * sizeof(db->lens[0]), |
352 | M_DEVBUF, M_NOWAIT); |
353 | if (!db->lens) { |
354 | free(db, M_DEVBUF); |
355 | return NULL; |
356 | } |
357 | } |
358 | |
359 | db->totlen = newlen; |
360 | db->hsize = hsize; |
361 | db->hshift = hshift; |
362 | db->maxmaxcode = maxmaxcode; |
363 | db->maxbits = bits; |
364 | |
365 | return (void *) db; |
366 | } |
367 | |
368 | static void |
369 | bsd_free(void *state) |
370 | { |
371 | struct bsd_db *db = (struct bsd_db *) state; |
372 | |
373 | if (db->lens) |
374 | free(db->lens, M_DEVBUF); |
375 | free(db, M_DEVBUF); |
376 | } |
377 | |
378 | static void * |
379 | bsd_comp_alloc(u_char *options, int opt_len) |
380 | { |
381 | return bsd_alloc(options, opt_len, 0); |
382 | } |
383 | |
384 | static void * |
385 | bsd_decomp_alloc(u_char *options, int opt_len) |
386 | { |
387 | return bsd_alloc(options, opt_len, 1); |
388 | } |
389 | |
390 | /* |
391 | * Initialize the database. |
392 | */ |
393 | static int |
394 | bsd_init(struct bsd_db *db, u_char *options, int opt_len, int unit, int hdrlen, |
395 | int mru, int debug, int decomp) |
396 | { |
397 | int i; |
398 | |
399 | if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS |
400 | || options[1] != CILEN_BSD_COMPRESS |
401 | || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION |
402 | || BSD_NBITS(options[2]) != db->maxbits |
403 | || (decomp && db->lens == NULL)) |
404 | return 0; |
405 | |
406 | if (decomp) { |
407 | i = LAST+1; |
408 | while (i != 0) |
409 | db->lens[--i] = 1; |
410 | } |
411 | i = db->hsize; |
412 | while (i != 0) { |
413 | db->dict[--i].codem1 = BADCODEM1; |
414 | db->dict[i].cptr = 0; |
415 | } |
416 | |
417 | db->unit = unit; |
418 | db->hdrlen = hdrlen; |
419 | db->mru = mru; |
420 | #ifndef DEBUG |
421 | if (debug) |
422 | #endif |
423 | db->debug = 1; |
424 | |
425 | bsd_reset(db); |
426 | |
427 | return 1; |
428 | } |
429 | |
430 | static int |
431 | bsd_comp_init(void *state, u_char *options, int opt_len, int unit, int hdrlen, |
432 | int debug) |
433 | { |
434 | return bsd_init((struct bsd_db *) state, options, opt_len, |
435 | unit, hdrlen, 0, debug, 0); |
436 | } |
437 | |
438 | static int |
439 | bsd_decomp_init(void *state, u_char *options, int opt_len, int unit, int hdrlen, |
440 | int mru, int debug) |
441 | { |
442 | return bsd_init((struct bsd_db *) state, options, opt_len, |
443 | unit, hdrlen, mru, debug, 1); |
444 | } |
445 | |
446 | |
447 | /* |
448 | * compress a packet |
449 | * One change from the BSD compress command is that when the |
450 | * code size expands, we do not output a bunch of padding. |
451 | */ |
452 | int /* new slen */ |
453 | bsd_compress(void *state, |
454 | struct mbuf **mret /* return compressed mbuf chain here */, |
455 | struct mbuf *mp /* from here */, |
456 | int slen, int maxolen) |
457 | { |
458 | struct bsd_db *db = (struct bsd_db *) state; |
459 | int hshift = db->hshift; |
460 | u_int max_ent = db->max_ent; |
461 | u_int n_bits = db->n_bits; |
462 | u_int bitno = 32; |
463 | uint32_t accm = 0, fcode; |
464 | struct bsd_dict *dictp; |
465 | u_char c; |
466 | int hval, disp, ent, ilen; |
467 | u_char *rptr, *wptr; |
468 | u_char *cp_end; |
469 | int olen; |
470 | struct mbuf *m; |
471 | |
472 | #define PUTBYTE(v) { \ |
473 | ++olen; \ |
474 | if (wptr) { \ |
475 | *wptr++ = (v); \ |
476 | if (wptr >= cp_end) { \ |
477 | m->m_len = wptr - mtod(m, u_char *); \ |
478 | MGET(m->m_next, M_DONTWAIT, MT_DATA); \ |
479 | m = m->m_next; \ |
480 | if (m) { \ |
481 | m->m_len = 0; \ |
482 | if (maxolen - olen > MLEN) \ |
483 | MCLGET(m, M_DONTWAIT); \ |
484 | wptr = mtod(m, u_char *); \ |
485 | cp_end = wptr + M_TRAILINGSPACE(m); \ |
486 | } else \ |
487 | wptr = NULL; \ |
488 | } \ |
489 | } \ |
490 | } |
491 | |
492 | #define OUTPUT(ent) { \ |
493 | bitno -= n_bits; \ |
494 | accm |= ((ent) << bitno); \ |
495 | do { \ |
496 | PUTBYTE(accm >> 24); \ |
497 | accm <<= 8; \ |
498 | bitno += 8; \ |
499 | } while (bitno <= 24); \ |
500 | } |
501 | |
502 | /* |
503 | * If the protocol is not in the range we're interested in, |
504 | * just return without compressing the packet. If it is, |
505 | * the protocol becomes the first byte to compress. |
506 | */ |
507 | rptr = mtod(mp, u_char *); |
508 | ent = PPP_PROTOCOL(rptr); |
509 | if (ent < 0x21 || ent > 0xf9) { |
510 | *mret = NULL; |
511 | return slen; |
512 | } |
513 | |
514 | /* Don't generate compressed packets which are larger than |
515 | the uncompressed packet. */ |
516 | if (maxolen > slen) |
517 | maxolen = slen; |
518 | |
519 | /* Allocate one mbuf to start with. */ |
520 | MGET(m, M_DONTWAIT, MT_DATA); |
521 | *mret = m; |
522 | if (m != NULL) { |
523 | m->m_len = 0; |
524 | if (maxolen + db->hdrlen > MLEN) |
525 | MCLGET(m, M_DONTWAIT); |
526 | m->m_data += db->hdrlen; |
527 | wptr = mtod(m, u_char *); |
528 | cp_end = wptr + M_TRAILINGSPACE(m); |
529 | } else |
530 | wptr = cp_end = NULL; |
531 | |
532 | /* |
533 | * Copy the PPP header over, changing the protocol, |
534 | * and install the 2-byte packet sequence number. |
535 | */ |
536 | if (wptr) { |
537 | *wptr++ = PPP_ADDRESS(rptr); /* assumes the ppp header is */ |
538 | *wptr++ = PPP_CONTROL(rptr); /* all in one mbuf */ |
539 | *wptr++ = 0; /* change the protocol */ |
540 | *wptr++ = PPP_COMP; |
541 | *wptr++ = db->seqno >> 8; |
542 | *wptr++ = db->seqno; |
543 | } |
544 | ++db->seqno; |
545 | |
546 | olen = 0; |
547 | rptr += PPP_HDRLEN; |
548 | slen = mp->m_len - PPP_HDRLEN; |
549 | ilen = slen + 1; |
550 | for (;;) { |
551 | if (slen <= 0) { |
552 | mp = mp->m_next; |
553 | if (!mp) |
554 | break; |
555 | rptr = mtod(mp, u_char *); |
556 | slen = mp->m_len; |
557 | if (!slen) |
558 | continue; /* handle 0-length buffers */ |
559 | ilen += slen; |
560 | } |
561 | |
562 | slen--; |
563 | c = *rptr++; |
564 | fcode = BSD_KEY(ent, c); |
565 | hval = BSD_HASH(ent, c, hshift); |
566 | dictp = &db->dict[hval]; |
567 | |
568 | /* Validate and then check the entry. */ |
569 | if (dictp->codem1 >= max_ent) |
570 | goto nomatch; |
571 | if (dictp->f.fcode == fcode) { |
572 | ent = dictp->codem1+1; |
573 | continue; /* found (prefix,suffix) */ |
574 | } |
575 | |
576 | /* continue probing until a match or invalid entry */ |
577 | disp = (hval == 0) ? 1 : hval; |
578 | do { |
579 | hval += disp; |
580 | if (hval >= db->hsize) |
581 | hval -= db->hsize; |
582 | dictp = &db->dict[hval]; |
583 | if (dictp->codem1 >= max_ent) |
584 | goto nomatch; |
585 | } while (dictp->f.fcode != fcode); |
586 | ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */ |
587 | continue; |
588 | |
589 | nomatch: |
590 | OUTPUT(ent); /* output the prefix */ |
591 | |
592 | /* code -> hashtable */ |
593 | if (max_ent < db->maxmaxcode) { |
594 | struct bsd_dict *dictp2; |
595 | /* expand code size if needed */ |
596 | if (max_ent >= MAXCODE(n_bits)) |
597 | db->n_bits = ++n_bits; |
598 | |
599 | /* Invalidate old hash table entry using |
600 | * this code, and then take it over. |
601 | */ |
602 | dictp2 = &db->dict[max_ent+1]; |
603 | if (db->dict[dictp2->cptr].codem1 == max_ent) |
604 | db->dict[dictp2->cptr].codem1 = BADCODEM1; |
605 | dictp2->cptr = hval; |
606 | dictp->codem1 = max_ent; |
607 | dictp->f.fcode = fcode; |
608 | |
609 | db->max_ent = ++max_ent; |
610 | } |
611 | ent = c; |
612 | } |
613 | |
614 | OUTPUT(ent); /* output the last code */ |
615 | db->bytes_out += olen; |
616 | db->in_count += ilen; |
617 | if (bitno < 32) |
618 | ++db->bytes_out; /* count complete bytes */ |
619 | |
620 | if (bsd_check(db)) |
621 | OUTPUT(CLEAR); /* do not count the CLEAR */ |
622 | |
623 | /* |
624 | * Pad dribble bits of last code with ones. |
625 | * Do not emit a completely useless byte of ones. |
626 | */ |
627 | if (bitno != 32) |
628 | PUTBYTE((accm | (0xff << (bitno-8))) >> 24); |
629 | |
630 | if (m != NULL) { |
631 | m->m_len = wptr - mtod(m, u_char *); |
632 | m->m_next = NULL; |
633 | } |
634 | |
635 | /* |
636 | * Increase code size if we would have without the packet |
637 | * boundary and as the decompressor will. |
638 | */ |
639 | if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) |
640 | db->n_bits++; |
641 | |
642 | db->uncomp_bytes += ilen; |
643 | ++db->uncomp_count; |
644 | if (olen + PPP_HDRLEN + BSD_OVHD > maxolen) { |
645 | /* throw away the compressed stuff if it is longer than uncompressed */ |
646 | if (*mret != NULL) { |
647 | m_freem(*mret); |
648 | *mret = NULL; |
649 | } |
650 | ++db->incomp_count; |
651 | db->incomp_bytes += ilen; |
652 | } else { |
653 | ++db->comp_count; |
654 | db->comp_bytes += olen + BSD_OVHD; |
655 | } |
656 | |
657 | return olen + PPP_HDRLEN + BSD_OVHD; |
658 | #undef OUTPUT |
659 | #undef PUTBYTE |
660 | } |
661 | |
662 | |
663 | /* |
664 | * Update the "BSD Compress" dictionary on the receiver for |
665 | * incompressible data by pretending to compress the incoming data. |
666 | */ |
667 | static void |
668 | bsd_incomp(void *state, struct mbuf *dmsg) |
669 | { |
670 | struct bsd_db *db = (struct bsd_db *) state; |
671 | u_int hshift = db->hshift; |
672 | u_int max_ent = db->max_ent; |
673 | u_int n_bits = db->n_bits; |
674 | struct bsd_dict *dictp; |
675 | uint32_t fcode; |
676 | u_char c; |
677 | uint32_t hval, disp; |
678 | int slen, ilen; |
679 | u_int bitno = 7; |
680 | u_char *rptr; |
681 | u_int ent; |
682 | |
683 | /* |
684 | * If the protocol is not in the range we're interested in, |
685 | * just return without looking at the packet. If it is, |
686 | * the protocol becomes the first byte to "compress". |
687 | */ |
688 | rptr = mtod(dmsg, u_char *); |
689 | ent = PPP_PROTOCOL(rptr); |
690 | if (ent < 0x21 || ent > 0xf9) |
691 | return; |
692 | |
693 | db->seqno++; |
694 | ilen = 1; /* count the protocol as 1 byte */ |
695 | rptr += PPP_HDRLEN; |
696 | slen = dmsg->m_len - PPP_HDRLEN; |
697 | for (;;) { |
698 | if (slen <= 0) { |
699 | dmsg = dmsg->m_next; |
700 | if (!dmsg) |
701 | break; |
702 | rptr = mtod(dmsg, u_char *); |
703 | slen = dmsg->m_len; |
704 | continue; |
705 | } |
706 | ilen += slen; |
707 | |
708 | do { |
709 | c = *rptr++; |
710 | fcode = BSD_KEY(ent, c); |
711 | hval = BSD_HASH(ent, c, hshift); |
712 | dictp = &db->dict[hval]; |
713 | |
714 | /* validate and then check the entry */ |
715 | if (dictp->codem1 >= max_ent) |
716 | goto nomatch; |
717 | if (dictp->f.fcode == fcode) { |
718 | ent = dictp->codem1+1; |
719 | continue; /* found (prefix,suffix) */ |
720 | } |
721 | |
722 | /* continue probing until a match or invalid entry */ |
723 | disp = (hval == 0) ? 1 : hval; |
724 | do { |
725 | hval += disp; |
726 | if (hval >= db->hsize) |
727 | hval -= db->hsize; |
728 | dictp = &db->dict[hval]; |
729 | if (dictp->codem1 >= max_ent) |
730 | goto nomatch; |
731 | } while (dictp->f.fcode != fcode); |
732 | ent = dictp->codem1+1; |
733 | continue; /* finally found (prefix,suffix) */ |
734 | |
735 | nomatch: /* output (count) the prefix */ |
736 | bitno += n_bits; |
737 | |
738 | /* code -> hashtable */ |
739 | if (max_ent < db->maxmaxcode) { |
740 | struct bsd_dict *dictp2; |
741 | /* expand code size if needed */ |
742 | if (max_ent >= MAXCODE(n_bits)) |
743 | db->n_bits = ++n_bits; |
744 | |
745 | /* Invalidate previous hash table entry |
746 | * assigned this code, and then take it over. |
747 | */ |
748 | dictp2 = &db->dict[max_ent+1]; |
749 | if (db->dict[dictp2->cptr].codem1 == max_ent) |
750 | db->dict[dictp2->cptr].codem1 = BADCODEM1; |
751 | dictp2->cptr = hval; |
752 | dictp->codem1 = max_ent; |
753 | dictp->f.fcode = fcode; |
754 | |
755 | db->max_ent = ++max_ent; |
756 | db->lens[max_ent] = db->lens[ent]+1; |
757 | } |
758 | ent = c; |
759 | } while (--slen != 0); |
760 | } |
761 | bitno += n_bits; /* output (count) the last code */ |
762 | db->bytes_out += bitno/8; |
763 | db->in_count += ilen; |
764 | (void)bsd_check(db); |
765 | |
766 | ++db->incomp_count; |
767 | db->incomp_bytes += ilen; |
768 | ++db->uncomp_count; |
769 | db->uncomp_bytes += ilen; |
770 | |
771 | /* Increase code size if we would have without the packet |
772 | * boundary and as the decompressor will. |
773 | */ |
774 | if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) |
775 | db->n_bits++; |
776 | } |
777 | |
778 | |
779 | /* |
780 | * Decompress "BSD Compress". |
781 | * |
782 | * Because of patent problems, we return DECOMP_ERROR for errors |
783 | * found by inspecting the input data and for system problems, but |
784 | * DECOMP_FATALERROR for any errors which could possibly be said to |
785 | * be being detected "after" decompression. For DECOMP_ERROR, |
786 | * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be |
787 | * infringing a patent of Motorola's if we do, so we take CCP down |
788 | * instead. |
789 | * |
790 | * Given that the frame has the correct sequence number and a good FCS, |
791 | * errors such as invalid codes in the input most likely indicate a |
792 | * bug, so we return DECOMP_FATALERROR for them in order to turn off |
793 | * compression, even though they are detected by inspecting the input. |
794 | */ |
795 | int |
796 | bsd_decompress(void *state, struct mbuf *cmp, struct mbuf **dmpp) |
797 | { |
798 | struct bsd_db *db = (struct bsd_db *) state; |
799 | u_int max_ent = db->max_ent; |
800 | uint32_t accm = 0; |
801 | u_int bitno = 32; /* 1st valid bit in accm */ |
802 | u_int n_bits = db->n_bits; |
803 | u_int tgtbitno = 32-n_bits; /* bitno when we have a code */ |
804 | struct bsd_dict *dictp; |
805 | int explen, i, seq, len; |
806 | u_int incode, oldcode, finchar; |
807 | u_char *p, *rptr, *wptr; |
808 | struct mbuf *m, *dmp, *mret; |
809 | int adrs, ctrl, ilen; |
810 | int space, codelen, ; |
811 | |
812 | /* |
813 | * Save the address/control from the PPP header |
814 | * and then get the sequence number. |
815 | */ |
816 | *dmpp = NULL; |
817 | rptr = mtod(cmp, u_char *); |
818 | adrs = PPP_ADDRESS(rptr); |
819 | ctrl = PPP_CONTROL(rptr); |
820 | rptr += PPP_HDRLEN; |
821 | len = cmp->m_len - PPP_HDRLEN; |
822 | seq = 0; |
823 | for (i = 0; i < 2; ++i) { |
824 | while (len <= 0) { |
825 | cmp = cmp->m_next; |
826 | if (cmp == NULL) |
827 | return DECOMP_ERROR; |
828 | rptr = mtod(cmp, u_char *); |
829 | len = cmp->m_len; |
830 | } |
831 | seq = (seq << 8) + *rptr++; |
832 | --len; |
833 | } |
834 | |
835 | /* |
836 | * Check the sequence number and give up if it differs from |
837 | * the value we're expecting. |
838 | */ |
839 | if (seq != db->seqno) { |
840 | if (db->debug) |
841 | printf("bsd_decomp%d: bad sequence # %d, expected %d\n" , |
842 | db->unit, seq, db->seqno - 1); |
843 | return DECOMP_ERROR; |
844 | } |
845 | ++db->seqno; |
846 | |
847 | /* |
848 | * Allocate one mbuf to start with. |
849 | */ |
850 | MGETHDR(dmp, M_DONTWAIT, MT_DATA); |
851 | if (dmp == NULL) |
852 | return DECOMP_ERROR; |
853 | mret = dmp; |
854 | dmp->m_len = 0; |
855 | dmp->m_next = NULL; |
856 | MCLGET(dmp, M_DONTWAIT); |
857 | dmp->m_data += db->hdrlen; |
858 | wptr = mtod(dmp, u_char *); |
859 | space = M_TRAILINGSPACE(dmp) - PPP_HDRLEN + 1; |
860 | |
861 | /* |
862 | * Fill in the ppp header, but not the last byte of the protocol |
863 | * (that comes from the decompressed data). |
864 | */ |
865 | wptr[0] = adrs; |
866 | wptr[1] = ctrl; |
867 | wptr[2] = 0; |
868 | wptr += PPP_HDRLEN - 1; |
869 | |
870 | ilen = len; |
871 | oldcode = CLEAR; |
872 | explen = 0; |
873 | for (;;) { |
874 | if (len == 0) { |
875 | cmp = cmp->m_next; |
876 | if (!cmp) /* quit at end of message */ |
877 | break; |
878 | rptr = mtod(cmp, u_char *); |
879 | len = cmp->m_len; |
880 | ilen += len; |
881 | continue; /* handle 0-length buffers */ |
882 | } |
883 | |
884 | /* |
885 | * Accumulate bytes until we have a complete code. |
886 | * Then get the next code, relying on the 32-bit, |
887 | * unsigned accm to mask the result. |
888 | */ |
889 | bitno -= 8; |
890 | accm |= *rptr++ << bitno; |
891 | --len; |
892 | if (tgtbitno < bitno) |
893 | continue; |
894 | incode = accm >> tgtbitno; |
895 | accm <<= n_bits; |
896 | bitno += n_bits; |
897 | |
898 | if (incode == CLEAR) { |
899 | /* |
900 | * The dictionary must only be cleared at |
901 | * the end of a packet. But there could be an |
902 | * empty mbuf at the end. |
903 | */ |
904 | if (len > 0 || cmp->m_next != NULL) { |
905 | while ((cmp = cmp->m_next) != NULL) |
906 | len += cmp->m_len; |
907 | if (len > 0) { |
908 | m_freem(mret); |
909 | if (db->debug) |
910 | printf("bsd_decomp%d: bad CLEAR\n" , db->unit); |
911 | return DECOMP_FATALERROR; /* probably a bug */ |
912 | } |
913 | } |
914 | bsd_clear(db); |
915 | explen = ilen = 0; |
916 | break; |
917 | } |
918 | |
919 | if (incode > max_ent + 2 || incode > db->maxmaxcode |
920 | || (incode > max_ent && oldcode == CLEAR)) { |
921 | m_freem(mret); |
922 | if (db->debug) { |
923 | printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x " , |
924 | db->unit, incode, oldcode); |
925 | printf("max_ent=0x%x explen=%d seqno=%d\n" , |
926 | max_ent, explen, db->seqno); |
927 | } |
928 | return DECOMP_FATALERROR; /* probably a bug */ |
929 | } |
930 | |
931 | /* Special case for KwKwK string. */ |
932 | if (incode > max_ent) { |
933 | finchar = oldcode; |
934 | extra = 1; |
935 | } else { |
936 | finchar = incode; |
937 | extra = 0; |
938 | } |
939 | |
940 | codelen = db->lens[finchar]; |
941 | explen += codelen + extra; |
942 | if (explen > db->mru + 1) { |
943 | m_freem(mret); |
944 | if (db->debug) { |
945 | printf("bsd_decomp%d: ran out of mru\n" , db->unit); |
946 | #ifdef DEBUG |
947 | while ((cmp = cmp->m_next) != NULL) |
948 | len += cmp->m_len; |
949 | printf(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n" , |
950 | len, finchar, codelen, explen); |
951 | #endif |
952 | } |
953 | return DECOMP_FATALERROR; |
954 | } |
955 | |
956 | /* |
957 | * For simplicity, the decoded characters go in a single mbuf, |
958 | * so we allocate a single extra cluster mbuf if necessary. |
959 | */ |
960 | if ((space -= codelen + extra) < 0) { |
961 | dmp->m_len = wptr - mtod(dmp, u_char *); |
962 | MGET(m, M_DONTWAIT, MT_DATA); |
963 | if (m == NULL) { |
964 | m_freem(mret); |
965 | return DECOMP_ERROR; |
966 | } |
967 | m->m_len = 0; |
968 | m->m_next = NULL; |
969 | dmp->m_next = m; |
970 | MCLGET(m, M_DONTWAIT); |
971 | space = M_TRAILINGSPACE(m) - (codelen + extra); |
972 | if (space < 0) { |
973 | /* now that's what I call *compression*. */ |
974 | m_freem(mret); |
975 | return DECOMP_ERROR; |
976 | } |
977 | dmp = m; |
978 | wptr = mtod(dmp, u_char *); |
979 | } |
980 | |
981 | /* |
982 | * Decode this code and install it in the decompressed buffer. |
983 | */ |
984 | p = (wptr += codelen); |
985 | while (finchar > LAST) { |
986 | dictp = &db->dict[db->dict[finchar].cptr]; |
987 | #ifdef DEBUG |
988 | if (--codelen <= 0 || dictp->codem1 != finchar-1) |
989 | goto bad; |
990 | #endif |
991 | *--p = dictp->f.hs.suffix; |
992 | finchar = dictp->f.hs.prefix; |
993 | } |
994 | *--p = finchar; |
995 | |
996 | #ifdef DEBUG |
997 | if (--codelen != 0) |
998 | printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n" , |
999 | db->unit, codelen, incode, max_ent); |
1000 | #endif |
1001 | |
1002 | if (extra) /* the KwKwK case again */ |
1003 | *wptr++ = finchar; |
1004 | |
1005 | /* |
1006 | * If not first code in a packet, and |
1007 | * if not out of code space, then allocate a new code. |
1008 | * |
1009 | * Keep the hash table correct so it can be used |
1010 | * with uncompressed packets. |
1011 | */ |
1012 | if (oldcode != CLEAR && max_ent < db->maxmaxcode) { |
1013 | struct bsd_dict *dictp2; |
1014 | uint32_t fcode; |
1015 | uint32_t hval, disp; |
1016 | |
1017 | fcode = BSD_KEY(oldcode,finchar); |
1018 | hval = BSD_HASH(oldcode,finchar,db->hshift); |
1019 | dictp = &db->dict[hval]; |
1020 | |
1021 | /* look for a free hash table entry */ |
1022 | if (dictp->codem1 < max_ent) { |
1023 | disp = (hval == 0) ? 1 : hval; |
1024 | do { |
1025 | hval += disp; |
1026 | if (hval >= db->hsize) |
1027 | hval -= db->hsize; |
1028 | dictp = &db->dict[hval]; |
1029 | } while (dictp->codem1 < max_ent); |
1030 | } |
1031 | |
1032 | /* |
1033 | * Invalidate previous hash table entry |
1034 | * assigned this code, and then take it over |
1035 | */ |
1036 | dictp2 = &db->dict[max_ent+1]; |
1037 | if (db->dict[dictp2->cptr].codem1 == max_ent) { |
1038 | db->dict[dictp2->cptr].codem1 = BADCODEM1; |
1039 | } |
1040 | dictp2->cptr = hval; |
1041 | dictp->codem1 = max_ent; |
1042 | dictp->f.fcode = fcode; |
1043 | |
1044 | db->max_ent = ++max_ent; |
1045 | db->lens[max_ent] = db->lens[oldcode]+1; |
1046 | |
1047 | /* Expand code size if needed. */ |
1048 | if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) { |
1049 | db->n_bits = ++n_bits; |
1050 | tgtbitno = 32-n_bits; |
1051 | } |
1052 | } |
1053 | oldcode = incode; |
1054 | } |
1055 | dmp->m_len = wptr - mtod(dmp, u_char *); |
1056 | |
1057 | /* |
1058 | * Keep the checkpoint right so that incompressible packets |
1059 | * clear the dictionary at the right times. |
1060 | */ |
1061 | db->bytes_out += ilen; |
1062 | db->in_count += explen; |
1063 | if (bsd_check(db) && db->debug) { |
1064 | printf("bsd_decomp%d: peer should have cleared dictionary\n" , |
1065 | db->unit); |
1066 | } |
1067 | |
1068 | ++db->comp_count; |
1069 | db->comp_bytes += ilen + BSD_OVHD; |
1070 | ++db->uncomp_count; |
1071 | db->uncomp_bytes += explen; |
1072 | |
1073 | *dmpp = mret; |
1074 | return DECOMP_OK; |
1075 | |
1076 | #ifdef DEBUG |
1077 | bad: |
1078 | if (codelen <= 0) { |
1079 | printf("bsd_decomp%d: fell off end of chain " , db->unit); |
1080 | printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n" , |
1081 | incode, finchar, db->dict[finchar].cptr, max_ent); |
1082 | } else if (dictp->codem1 != finchar-1) { |
1083 | printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x " , |
1084 | db->unit, incode, finchar); |
1085 | printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n" , oldcode, |
1086 | db->dict[finchar].cptr, dictp->codem1); |
1087 | } |
1088 | m_freem(mret); |
1089 | return DECOMP_FATALERROR; |
1090 | #endif /* DEBUG */ |
1091 | } |
1092 | |
1093 | MODULE(MODULE_CLASS_MISC, ppp_bsdcomp, "if_ppp" ); |
1094 | |
1095 | static int |
1096 | ppp_bsdcomp_modcmd(modcmd_t cmd, void *arg) |
1097 | { |
1098 | |
1099 | switch (cmd) { |
1100 | case MODULE_CMD_INIT: |
1101 | return ppp_register_compressor(&ppp_bsd_compress, 1); |
1102 | case MODULE_CMD_FINI: |
1103 | return ppp_unregister_compressor(&ppp_bsd_compress, 1); |
1104 | case MODULE_CMD_STAT: |
1105 | return 0; |
1106 | default: |
1107 | return ENOTTY; |
1108 | } |
1109 | |
1110 | return ENOTTY; |
1111 | } |
1112 | #endif /* DO_BSD_COMPRESS */ |
1113 | |