Annotation of sys/net/bsd-comp.c, Revision 1.1.1.1
1.1 nbrk 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
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 */
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
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
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 *
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
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 *
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 *
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
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
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
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 */
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
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
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 */
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to bsd-comp.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / net