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