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