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