1 /*
2 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
3 * Use is subject to license terms.
4 *
5 * Because this code is derived from the 4.3BSD compress source:
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. All advertising materials mentioning features or use of this software
23 * must display the following acknowledgement:
24 * This product includes software developed by the University of
25 * California, Berkeley and its contributors.
26 * 4. Neither the name of the University nor the names of its contributors
27 * may be used to endorse or promote products derived from this software
28 * without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40 * SUCH DAMAGE.
41 */
42
43 /*
44 * This version is for use with STREAMS in Solaris 2
45 *
46 * $Id: bsd-comp.c,v 1.20 1996/08/28 06:31:57 paulus Exp $
47 */
48
49 #include <sys/param.h>
50 #include <sys/types.h>
51 #include <sys/kmem.h>
52 #include <sys/stream.h>
53 #include <sys/cmn_err.h>
54 #include <sys/ddi.h>
55 #include <sys/sunddi.h>
56 #include <sys/byteorder.h>
57 #include <net/ppp_defs.h>
58
59 /* Defined for platform-neutral include file */
60 #define PACKETPTR mblk_t *
61 #include <net/ppp-comp.h>
62
63 #ifndef _BIG_ENDIAN
64 #define BSD_LITTLE_ENDIAN
65 #endif
66
67 #if DO_BSD_COMPRESS
68
69 /*
70 * PPP "BSD compress" compression
71 *
72 * The differences between this compression and the classic BSD LZW
73 * source are obvious from the requirement that the classic code worked
74 * with files while this handles arbitrarily long streams that
75 * are broken into packets. They are:
76 *
77 * When the code size expands, a block of junk is not emitted by
78 * the compressor and not expected by the decompressor.
79 *
80 * New codes are not necessarily assigned every time an old
81 * code is output by the compressor. This is because a packet
82 * end forces a code to be emitted, but does not imply that a
83 * new sequence has been seen.
84 *
85 * The compression ratio is checked at the first end of a packet
86 * after the appropriate gap. Besides simplifying and speeding
87 * things up, this makes it more likely that the transmitter
88 * and receiver will agree when the dictionary is cleared when
89 * compression is not going well.
90 */
91
92 /*
93 * A dictionary for doing BSD compress.
94 */
95 struct bsd_db {
96 int totlen; /* length of this structure */
97 uint_t hsize; /* size of the hash table */
98 uint32_t unit;
99 uchar_t hshift; /* used in hash function */
100 uchar_t n_bits; /* current bits/code */
101 uchar_t maxbits;
102 uchar_t flags;
103 ushort_t seqno; /* sequence number of next packet */
104 ushort_t mru;
105 uint_t hdrlen; /* header length to preallocate */
106 uint_t maxmaxcode; /* largest valid code */
107 uint_t max_ent; /* largest code in use */
108 uint_t in_count; /* uncompressed bytes, aged */
109 uint_t bytes_out; /* compressed bytes, aged */
110 uint_t ratio; /* recent compression ratio */
111 uint_t checkpoint; /* when to next check the ratio */
112 uint_t clear_count; /* times dictionary cleared */
113 uint_t incomp_count; /* incompressible packets */
114 uint_t incomp_bytes; /* incompressible bytes */
115 uint_t uncomp_count; /* uncompressed packets */
116 uint_t uncomp_bytes; /* uncompressed bytes */
117 uint_t comp_count; /* compressed packets */
118 uint_t comp_bytes; /* compressed bytes */
119 ushort_t *lens; /* array of lengths of codes */
120 struct bsd_dict {
121 union { /* hash value */
122 uint32_t fcode;
123 struct {
124 #ifdef BSD_LITTLE_ENDIAN
125 ushort_t prefix; /* preceding code */
126 uchar_t suffix; /* last character of new code */
127 uchar_t pad;
128 #else
129 uchar_t pad;
130 uchar_t suffix; /* last character of new code */
131 ushort_t prefix; /* preceding code */
132 #endif
133 } hs;
134 } f;
135 ushort_t codem1; /* output of hash table -1 */
136 ushort_t cptr; /* map code to hash entry */
137 } dict[1];
138 };
139
140 #define BSD_OVHD 2 /* BSD compress overhead/packet */
141 #define BSD_INIT_BITS BSD_MIN_BITS
142
143 /* db->flags values */
144 #define DS_DEBUG 0x01
145 #define DS_TESTIN 0x02
146 #define DS_TESTOUT 0x04
147 #define DS_INITDONE 0x08
148
149 static void *bsd_comp_alloc(uchar_t *options, int opt_len);
150 static void *bsd_decomp_alloc(uchar_t *options, int opt_len);
151 static void bsd_free(void *state);
152 static int bsd_comp_init(void *state, uchar_t *options, int opt_len,
153 int unit, int hdrlen, int debug);
154 static int bsd_decomp_init(void *state, uchar_t *options, int opt_len,
155 int unit, int hdrlen, int mru, int debug);
156 static int bsd_compress(void *state, mblk_t **mret,
157 mblk_t *mp, int slen, int maxolen);
158 static int bsd_incomp(void *state, mblk_t *dmsg);
159 static int bsd_decompress(void *state, mblk_t **dmpp);
160 static void bsd_reset(void *state);
161 static void bsd_comp_stats(void *state, struct compstat *stats);
162 static int bsd_set_effort(void *xarg, void *rarg, int effortlevel);
163
164 /*
165 * Procedures exported to ppp_comp.c.
166 */
167 struct compressor ppp_bsd_compress = {
168 CI_BSD_COMPRESS, /* compress_proto */
169 bsd_comp_alloc, /* comp_alloc */
170 bsd_free, /* comp_free */
171 bsd_comp_init, /* comp_init */
172 bsd_reset, /* comp_reset */
173 bsd_compress, /* compress */
174 bsd_comp_stats, /* comp_stat */
175 bsd_decomp_alloc, /* decomp_alloc */
176 bsd_free, /* decomp_free */
177 bsd_decomp_init, /* decomp_init */
178 bsd_reset, /* decomp_reset */
179 bsd_decompress, /* decompress */
180 bsd_incomp, /* incomp */
181 bsd_comp_stats, /* decomp_stat */
182 bsd_set_effort, /* set_effort */
183 };
184
185 /*
186 * the next two codes should not be changed lightly, as they must not
187 * lie within the contiguous general code space.
188 */
189 #define CLEAR 256 /* table clear output code */
190 #define FIRST 257 /* first free entry */
191 #define LAST 255
192
193 #define MAXCODE(b) ((1 << (b)) - 1)
194 #define BADCODEM1 MAXCODE(BSD_MAX_BITS)
195
196 #define BSD_HASH(prefix, suffix, hshift) \
197 ((((uint32_t)(suffix)) << (hshift)) ^ (uint32_t)(prefix))
198
199 #define BSD_KEY(prefix, suffix) \
200 ((((uint32_t)(suffix)) << 16) + (uint32_t)(prefix))
201
202 #define CHECK_GAP 10000 /* Ratio check interval */
203
204 #define RATIO_SCALE_LOG 8
205 #define RATIO_SCALE (1 << RATIO_SCALE_LOG)
206 #define RATIO_MAX (0x7fffffff >> RATIO_SCALE_LOG)
207
208 #define DECOMP_CHUNK 256
209
210 /*
211 * bsd_clear()
212 *
213 * clear the dictionary
214 */
215 static void
bsd_clear(struct bsd_db * db)216 bsd_clear(struct bsd_db *db)
217 {
218 db->clear_count++;
219 db->max_ent = FIRST-1;
220 db->n_bits = BSD_INIT_BITS;
221 db->ratio = 0;
222 db->bytes_out = 0;
223 db->in_count = 0;
224 db->checkpoint = CHECK_GAP;
225 }
226
227 /*
228 * bsd_check()
229 *
230 * If the dictionary is full, then see if it is time to reset it.
231 *
232 * Compute the compression ratio using fixed-point arithmetic
233 * with 8 fractional bits.
234 *
235 * Since we have an infinite stream instead of a single file,
236 * watch only the local compression ratio.
237 *
238 * Since both peers must reset the dictionary at the same time even in
239 * the absence of CLEAR codes (while packets are incompressible), they
240 * must compute the same ratio.
241 */
242 static int /* 1=output CLEAR */
bsd_check(struct bsd_db * db)243 bsd_check(struct bsd_db *db)
244 {
245 uint_t new_ratio;
246
247 if (db->in_count >= db->checkpoint) {
248
249 /*
250 * age the ratio by limiting the size of the counts
251 */
252 if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX) {
253 db->in_count -= db->in_count/4;
254 db->bytes_out -= db->bytes_out/4;
255 }
256
257 db->checkpoint = db->in_count + CHECK_GAP;
258
259 if (db->max_ent >= db->maxmaxcode) {
260
261 /*
262 * Reset the dictionary only if the ratio is worse,
263 * or if it looks as if it has been poisoned
264 * by incompressible data.
265 *
266 * This does not overflow, because
267 * db->in_count <= RATIO_MAX.
268 */
269 new_ratio = db->in_count << RATIO_SCALE_LOG;
270
271 if (db->bytes_out != 0) {
272 new_ratio /= db->bytes_out;
273 }
274
275 if (new_ratio < db->ratio ||
276 new_ratio < 1 * RATIO_SCALE) {
277 bsd_clear(db);
278 return (1);
279 }
280
281 db->ratio = new_ratio;
282 }
283 }
284
285 return (0);
286 }
287
288 /*
289 * bsd_comp_stats()
290 *
291 * Return statistics.
292 */
293 static void
bsd_comp_stats(void * state,struct compstat * stats)294 bsd_comp_stats(void *state, struct compstat *stats)
295 {
296 struct bsd_db *db = (struct bsd_db *)state;
297 uint_t out;
298
299 stats->unc_bytes = db->uncomp_bytes;
300 stats->unc_packets = db->uncomp_count;
301 stats->comp_bytes = db->comp_bytes;
302 stats->comp_packets = db->comp_count;
303 stats->inc_bytes = db->incomp_bytes;
304 stats->inc_packets = db->incomp_count;
305 stats->ratio = db->in_count;
306
307 out = db->bytes_out;
308
309 if (stats->ratio <= 0x7fffff) {
310 stats->ratio <<= 8;
311 } else {
312 out >>= 8;
313 }
314
315 if (out != 0) {
316 stats->ratio /= out;
317 }
318 }
319
320 /*
321 * bsd_reset()
322 *
323 * Reset state, as on a CCP ResetReq.
324 */
325 static void
bsd_reset(void * state)326 bsd_reset(void *state)
327 {
328 struct bsd_db *db = (struct bsd_db *)state;
329
330 if (db->hsize != 0) {
331 db->seqno = 0;
332
333 bsd_clear(db);
334
335 db->clear_count = 0;
336 }
337 }
338
339 /*
340 * bsd_alloc()
341 *
342 * Allocate space for a (de) compressor.
343 */
344 static void *
bsd_alloc(uchar_t * options,int opt_len,int decomp)345 bsd_alloc(uchar_t *options, int opt_len, int decomp)
346 {
347 int bits;
348 uint_t newlen;
349 uint_t hsize;
350 uint_t hshift;
351 uint_t maxmaxcode;
352 uint_t ilen;
353 struct bsd_db *db;
354
355 if (opt_len != 3 ||
356 options[0] != CI_BSD_COMPRESS ||
357 options[1] != 3 ||
358 BSD_VERSION(options[2]) != BSD_CURRENT_VERSION) {
359
360 return (NULL);
361 }
362
363 bits = BSD_NBITS(options[2]);
364
365 switch (bits) {
366
367 case 9: /* needs 82152 for both directions */
368 case 10: /* needs 84144 */
369 case 11: /* needs 88240 */
370 case 12: /* needs 96432 */
371
372 hsize = 5003;
373 hshift = 4;
374
375 break;
376
377 case 13: /* needs 176784 */
378
379 hsize = 9001;
380 hshift = 5;
381
382 break;
383
384 case 14: /* needs 353744 */
385
386 hsize = 18013;
387 hshift = 6;
388
389 break;
390
391 case 15: /* needs 691440 */
392
393 hsize = 35023;
394 hshift = 7;
395
396 break;
397
398 /* XXX: this falls thru - it was originally commented */
399 case 16: /* needs 1366160--far too much, */
400 /* hsize = 69001; */ /* and 69001 is too big for cptr */
401 /* hshift = 8; */ /* in struct bsd_db */
402 /* break; */
403
404 default:
405
406 return (NULL);
407 }
408
409 maxmaxcode = MAXCODE(bits);
410 ilen = newlen = sizeof (*db) + (hsize-1) * sizeof (db->dict[0]);
411 if (decomp)
412 newlen += (maxmaxcode+1) * sizeof (db->lens[0]);
413 db = (struct bsd_db *)kmem_alloc(newlen, KM_NOSLEEP);
414 if (!db) {
415 return (NULL);
416 }
417
418 bzero(db, sizeof (*db) - sizeof (db->dict));
419
420 if (!decomp) {
421 db->lens = NULL;
422 } else {
423 db->lens = (ushort_t *)((caddr_t)db + ilen);
424 }
425
426 db->totlen = newlen;
427 db->hsize = hsize;
428 db->hshift = (uchar_t)hshift;
429 db->maxmaxcode = maxmaxcode;
430 db->maxbits = (uchar_t)bits;
431
432 return ((void *)db);
433 }
434
435 /*
436 * bsd_free()
437 */
438 static void
bsd_free(void * state)439 bsd_free(void *state)
440 {
441 struct bsd_db *db = (struct bsd_db *)state;
442
443 if (db->hsize != 0) {
444 /* XXX feeble attempt to catch bad references. */
445 db->hsize = 0;
446
447 kmem_free(db, db->totlen);
448 }
449 }
450
451 /*
452 * bsd_comp_alloc()
453 */
454 static void *
bsd_comp_alloc(uchar_t * options,int opt_len)455 bsd_comp_alloc(uchar_t *options, int opt_len)
456 {
457 return (bsd_alloc(options, opt_len, 0));
458 }
459
460 /*
461 * bsd_decomp_alloc()
462 */
463 static void *
bsd_decomp_alloc(uchar_t * options,int opt_len)464 bsd_decomp_alloc(uchar_t *options, int opt_len)
465 {
466 return (bsd_alloc(options, opt_len, 1));
467 }
468
469 /*
470 * bsd_init()
471 *
472 * Initialize the database.
473 */
474 static int
bsd_init(struct bsd_db * db,uchar_t * options,int opt_len,int unit,int hdrlen,int mru,int debug,int decomp)475 bsd_init(struct bsd_db *db, uchar_t *options, int opt_len, int unit,
476 int hdrlen, int mru, int debug, int decomp)
477 {
478 int i;
479
480 if (db->hsize == 0 || opt_len < CILEN_BSD_COMPRESS ||
481 options[0] != CI_BSD_COMPRESS ||
482 options[1] != CILEN_BSD_COMPRESS ||
483 BSD_VERSION(options[2]) != BSD_CURRENT_VERSION ||
484 BSD_NBITS(options[2]) != db->maxbits ||
485 decomp && db->lens == NULL) {
486
487 return (0);
488 }
489
490 if (decomp) {
491 i = LAST + 1;
492
493 while (i != 0) {
494 db->lens[--i] = 1;
495 }
496 }
497
498 i = db->hsize;
499
500 while (i != 0) {
501 db->dict[--i].codem1 = BADCODEM1;
502 db->dict[i].cptr = 0;
503 }
504
505 db->unit = unit;
506 db->hdrlen = hdrlen;
507 db->mru = (ushort_t)mru;
508
509 if (debug) {
510 db->flags |= DS_DEBUG;
511 }
512
513 bsd_reset(db);
514
515 db->flags |= DS_INITDONE;
516
517 return (1);
518 }
519
520 /*
521 * bsd_comp_init()
522 */
523 static int
bsd_comp_init(void * state,uchar_t * options,int opt_len,int unit,int hdrlen,int debug)524 bsd_comp_init(void *state, uchar_t *options, int opt_len, int unit, int hdrlen,
525 int debug)
526 {
527 return (bsd_init((struct bsd_db *)state, options, opt_len,
528 unit, hdrlen, 0, debug, 0));
529 }
530
531 /*
532 * bsd_decomp_init()
533 */
534 static int
bsd_decomp_init(void * state,uchar_t * options,int opt_len,int unit,int hdrlen,int mru,int debug)535 bsd_decomp_init(void *state, uchar_t *options, int opt_len, int unit,
536 int hdrlen, int mru, int debug)
537 {
538 return (bsd_init((struct bsd_db *)state, options, opt_len,
539 unit, hdrlen, mru, debug, 1));
540 }
541
542
543 /*
544 * bsd_compress()
545 *
546 * compress a packet
547 * One change from the BSD compress command is that when the
548 * code size expands, we do not output a bunch of padding.
549 *
550 * N.B. at present, we ignore the hdrlen specified in the comp_init call.
551 */
552 static int /* new slen */
bsd_compress(void * state,mblk_t ** mretp,mblk_t * mp,int slen,int maxolen)553 bsd_compress(void *state, mblk_t **mretp, mblk_t *mp, int slen, int maxolen)
554 {
555 struct bsd_db *db = (struct bsd_db *)state;
556 int hshift = db->hshift;
557 uint_t max_ent = db->max_ent;
558 uint_t n_bits = db->n_bits;
559 uint_t bitno = 32;
560 uint32_t accm = 0;
561 uint32_t fcode;
562 struct bsd_dict *dictp;
563 uchar_t c;
564 int hval;
565 int disp;
566 int ent;
567 int ilen = slen - (PPP_HDRLEN-1);
568 mblk_t *mret;
569 uchar_t *rptr, *rmax;
570 uchar_t *wptr;
571 uchar_t *cp_end;
572 int olen;
573 mblk_t *m;
574 mblk_t **mnp;
575 #if defined(lint) || defined(_lint)
576 uchar_t hdlcaddr, hdlcctl;
577 #else
578 int hdlcaddr, hdlcctl;
579 #endif
580
581 ASSERT(db->flags & DS_INITDONE);
582
583 #define PUTBYTE(v) { \
584 if (wptr) { \
585 *wptr++ = (v); \
586 if (wptr >= cp_end) { \
587 m->b_wptr = wptr; \
588 m = m->b_cont; \
589 if (m) { \
590 wptr = m->b_wptr; \
591 cp_end = m->b_datap->db_lim; \
592 } else { \
593 wptr = NULL; \
594 } \
595 } \
596 } \
597 ++olen; \
598 }
599
600 #define OUTPUT(ent) { \
601 bitno -= n_bits; \
602 accm |= ((ent) << bitno); \
603 do { \
604 PUTBYTE(accm >> 24); \
605 accm <<= 8; \
606 bitno += 8; \
607 } while (bitno <= 24); \
608 }
609
610 #define ADJRPTR() { \
611 if (rptr != NULL) { \
612 while (rptr >= rmax) { \
613 if ((mp = mp->b_cont) == NULL) { \
614 rptr = NULL; \
615 break; \
616 } \
617 rptr = mp->b_rptr; \
618 rmax = mp->b_wptr; \
619 } \
620 } \
621 }
622
623 #define GETBYTE(v) { \
624 if (rptr != NULL) { \
625 (v) = *rptr++; \
626 } \
627 }
628
629 if (db->hsize == 0)
630 return (-1);
631
632 /*
633 * First get the protocol and check that we're
634 * interested in this packet.
635 */
636 *mretp = NULL;
637 rptr = mp->b_rptr;
638 rmax = mp->b_wptr;
639
640 /* We CANNOT do a pullup here; it's not our buffer to toy with. */
641 ADJRPTR();
642 GETBYTE(hdlcaddr);
643 ADJRPTR();
644 GETBYTE(hdlcctl);
645 ADJRPTR();
646 GETBYTE(ent);
647 ADJRPTR();
648
649 /*
650 * Per RFC 1977, the protocol field must be compressed using a
651 * PFC-like procedure. Also, all protocols between 0000-3FFF
652 * except the two compression protocols must be LZ compressed.
653 */
654 if (ent == 0) {
655 GETBYTE(ent);
656 if (rptr == NULL || ent == PPP_COMP || ent == PPP_COMPFRAG)
657 return (0);
658 } else {
659 if (ent > 0x3F)
660 return (0);
661 ilen++;
662 }
663
664 /*
665 * Don't generate compressed packets that are larger than the
666 * source (uncompressed) packet.
667 */
668 if (maxolen > slen) {
669 maxolen = slen;
670 }
671 if (maxolen < 6)
672 maxolen = 6;
673
674 /*
675 * Allocate enough message blocks to give maxolen total space
676 */
677 mnp = &mret;
678 for (olen = maxolen; olen > 0; ) {
679
680 m = allocb((olen < 4096? olen: 4096), BPRI_MED);
681
682 *mnp = m;
683 if (m == NULL) {
684 if (mnp == &mret)
685 return (0);
686 /* We allocated some; hope for the best. */
687 break;
688 }
689
690 mnp = &m->b_cont;
691 olen -= m->b_datap->db_lim - m->b_wptr;
692 }
693
694 *mnp = NULL;
695
696 m = mret;
697 wptr = m->b_wptr;
698 cp_end = m->b_datap->db_lim;
699
700 olen = 0;
701
702 /*
703 * Copy the PPP header over, changing the protocol,
704 * and install the 2-byte sequence number
705 */
706 *wptr++ = hdlcaddr;
707 *wptr++ = hdlcctl;
708 *wptr++ = PPP_COMP>>8; /* change the protocol */
709 *wptr++ = PPP_COMP;
710 *wptr++ = db->seqno >> 8;
711 *wptr++ = db->seqno;
712
713 #ifdef DEBUG
714 /*
715 * If testing output, just garbling the sequence here does the
716 * trick.
717 */
718 if ((db->flags & DS_TESTOUT) && (db->seqno % 100) == 50)
719 wptr[-1] ^= 0xAA;
720 #endif
721
722 ++db->seqno;
723
724 for (;;) {
725 ADJRPTR();
726 if (rptr == NULL)
727 break;
728
729 GETBYTE(c);
730
731 fcode = BSD_KEY(ent, c);
732 hval = BSD_HASH(ent, c, hshift);
733
734 dictp = &db->dict[hval];
735
736 /*
737 * Validate and then check the entry
738 */
739 if (dictp->codem1 >= max_ent) {
740 goto nomatch;
741 }
742
743 if (dictp->f.fcode == fcode) {
744 ent = dictp->codem1+1;
745
746 /*
747 * found (prefix,suffix)
748 */
749 continue;
750 }
751
752 /*
753 * continue probing until a match or invalid entry
754 */
755 disp = (hval == 0) ? 1 : hval;
756
757 do {
758 hval += disp;
759 if (hval >= db->hsize) {
760 hval -= db->hsize;
761 if (hval >= db->hsize) {
762 if (db->flags & DS_DEBUG) {
763 cmn_err(CE_CONT,
764 "bsd_comp%d: internal "
765 "error\n",
766 db->unit);
767 }
768 /* Caller will free it all */
769 return (-1);
770 }
771 }
772
773 dictp = &db->dict[hval];
774
775 if (dictp->codem1 >= max_ent) {
776 goto nomatch;
777 }
778 } while (dictp->f.fcode != fcode);
779
780 /*
781 * finally found (prefix,suffix)
782 */
783 ent = dictp->codem1 + 1;
784
785 continue;
786
787 nomatch:
788 /*
789 * output the prefix
790 */
791 OUTPUT(ent);
792
793 /*
794 * code -> hashtable
795 */
796 if (max_ent < db->maxmaxcode) {
797 struct bsd_dict *dictp2;
798
799 /*
800 * expand code size if needed
801 */
802 if (max_ent >= MAXCODE(n_bits)) {
803 db->n_bits = ++n_bits;
804 }
805
806 /*
807 * Invalidate old hash table entry using
808 * this code, and then take it over.
809 */
810 dictp2 = &db->dict[max_ent+1];
811
812 if (db->dict[dictp2->cptr].codem1 == max_ent) {
813 db->dict[dictp2->cptr].codem1 = BADCODEM1;
814 }
815
816 dictp2->cptr = (ushort_t)hval;
817 dictp->codem1 = max_ent;
818 dictp->f.fcode = fcode;
819
820 db->max_ent = ++max_ent;
821 }
822
823 ent = c;
824 }
825
826 /*
827 * output the last code
828 */
829 OUTPUT(ent);
830
831 olen += (32-bitno+7)/8; /* count complete bytes */
832
833 db->bytes_out += olen;
834 db->in_count += ilen;
835
836 if (bsd_check(db)) {
837 OUTPUT(CLEAR); /* do not count the CLEAR */
838 }
839
840 /*
841 * Pad dribble bits of last code with ones.
842 * Do not emit a completely useless byte of ones.
843 */
844 if (bitno != 32) {
845 PUTBYTE((accm | (0xff << (bitno - 8))) >> 24);
846 }
847
848 /*
849 * Increase code size if we would have without the packet
850 * boundary and as the decompressor will.
851 */
852 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
853 db->n_bits++;
854 }
855
856 db->uncomp_bytes += ilen;
857 ++db->uncomp_count;
858
859 if (wptr == NULL || olen + PPP_HDRLEN + BSD_OVHD >= maxolen) {
860 /*
861 * throw away the compressed stuff if it is longer
862 * than uncompressed
863 */
864 freemsg(mret);
865
866 mret = NULL;
867
868 ++db->incomp_count;
869 db->incomp_bytes += ilen;
870
871 } else {
872
873 m->b_wptr = wptr;
874 if (m->b_cont) {
875 freemsg(m->b_cont);
876 m->b_cont = NULL;
877 }
878
879 ++db->comp_count;
880 db->comp_bytes += olen + BSD_OVHD;
881 }
882
883 *mretp = mret;
884
885 return (olen + PPP_HDRLEN + BSD_OVHD);
886 #undef OUTPUT
887 #undef PUTBYTE
888 }
889
890
891 /*
892 * bsd_incomp()
893 *
894 * Update the "BSD Compress" dictionary on the receiver for
895 * incompressible data by pretending to compress the incoming data.
896 */
897 static int
bsd_incomp(void * state,mblk_t * mp)898 bsd_incomp(void *state, mblk_t *mp)
899 {
900 struct bsd_db *db = (struct bsd_db *)state;
901 uint_t hshift = db->hshift;
902 uint_t max_ent = db->max_ent;
903 uint_t n_bits = db->n_bits;
904 struct bsd_dict *dictp;
905 uint32_t fcode;
906 uchar_t c;
907 long hval;
908 long disp;
909 int slen;
910 int ilen;
911 uint_t bitno = 7;
912 uchar_t *rptr, *rmax;
913 uint_t ent;
914
915 ASSERT(db->flags & DS_INITDONE);
916
917 if (db->hsize == 0)
918 return (-1);
919
920 rptr = mp->b_rptr;
921 rmax = mp->b_wptr;
922 ADJRPTR();
923 GETBYTE(ent); /* address */
924 ADJRPTR();
925 GETBYTE(ent); /* control */
926 ADJRPTR();
927 GETBYTE(ent); /* protocol high */
928 ADJRPTR();
929
930 /*
931 * Per RFC 1977, the protocol field must be compressed using a
932 * PFC-like procedure. Also, all protocols between 0000-3FFF
933 * except the two compression protocols must be LZ compressed.
934 */
935 ilen = 1; /* count the protocol as 1 byte */
936 if (ent == 0) {
937 GETBYTE(ent);
938 if (rptr == NULL || ent == PPP_COMP || ent == PPP_COMPFRAG)
939 return (0);
940 } else {
941 if (ent > 0x3F)
942 return (0);
943 ilen++;
944 }
945
946 db->seqno++;
947
948 for (;;) {
949
950 slen = mp->b_wptr - rptr;
951 if (slen <= 0) {
952 mp = mp->b_cont;
953 if (!mp) {
954 break;
955 }
956
957 rptr = mp->b_rptr;
958 continue; /* skip zero-length buffers */
959 }
960
961 ilen += slen;
962
963 do {
964 c = *rptr++;
965
966 fcode = BSD_KEY(ent, c);
967 hval = BSD_HASH(ent, c, hshift);
968
969 dictp = &db->dict[hval];
970
971 /*
972 * validate and then check the entry
973 */
974 if (dictp->codem1 >= max_ent) {
975 goto nomatch;
976 }
977
978 if (dictp->f.fcode == fcode) {
979 ent = dictp->codem1 + 1;
980 continue; /* found (prefix,suffix) */
981 }
982
983 /*
984 * continue probing until a match or invalid entry
985 */
986 disp = (hval == 0) ? 1 : hval;
987 do {
988 hval += disp;
989 if (hval >= db->hsize) {
990 hval -= db->hsize;
991 if (hval >= db->hsize) {
992 if (db->flags & DS_DEBUG) {
993 cmn_err(CE_CONT,
994 "bsd_incomp%d: "
995 "internal error\n",
996 db->unit);
997 }
998 return (-1);
999 }
1000 }
1001
1002 dictp = &db->dict[hval];
1003 if (dictp->codem1 >= max_ent) {
1004 goto nomatch;
1005 }
1006 } while (dictp->f.fcode != fcode);
1007
1008 ent = dictp->codem1+1;
1009 continue; /* finally found (prefix,suffix) */
1010
1011 nomatch: /* output (count) the prefix */
1012 bitno += n_bits;
1013
1014 /*
1015 * code -> hashtable
1016 */
1017 if (max_ent < db->maxmaxcode) {
1018 struct bsd_dict *dictp2;
1019
1020 /*
1021 * expand code size if needed
1022 */
1023 if (max_ent >= MAXCODE(n_bits)) {
1024 db->n_bits = ++n_bits;
1025 }
1026
1027 /*
1028 * Invalidate previous hash table entry
1029 * assigned this code, and then take it over.
1030 */
1031 dictp2 = &db->dict[max_ent+1];
1032 if (db->dict[dictp2->cptr].codem1 == max_ent) {
1033 db->dict[dictp2->cptr].codem1 =
1034 BADCODEM1;
1035 }
1036
1037 dictp2->cptr = (ushort_t)hval;
1038 dictp->codem1 = max_ent;
1039 dictp->f.fcode = fcode;
1040
1041 db->max_ent = ++max_ent;
1042 db->lens[max_ent] = db->lens[ent]+1;
1043 }
1044
1045 ent = c;
1046 } while (--slen != 0);
1047 }
1048
1049 bitno += n_bits; /* output (count) the last code */
1050
1051 db->bytes_out += bitno/8;
1052 db->in_count += ilen;
1053
1054 (void) bsd_check(db);
1055
1056 ++db->incomp_count;
1057 db->incomp_bytes += ilen;
1058 ++db->uncomp_count;
1059 db->uncomp_bytes += ilen;
1060
1061 /*
1062 * Increase code size if we would have without the packet
1063 * boundary and as the decompressor will.
1064 */
1065 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
1066 db->n_bits++;
1067 }
1068 return (0);
1069 #undef ADJRPTR
1070 }
1071
1072
1073 /*
1074 * bsd_decompress()
1075 *
1076 * Decompress "BSD Compress"
1077 *
1078 * Because of patent problems, we return DECOMP_ERROR for errors
1079 * found by inspecting the input data and for system problems, but
1080 * DECOMP_FATALERROR for any errors which could possibly be said to
1081 * be being detected "after" decompression. For DECOMP_ERROR,
1082 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
1083 * infringing a patent of Motorola's if we do, so we take CCP down
1084 * instead.
1085 *
1086 * Given that the frame has the correct sequence number and a good FCS,
1087 * errors such as invalid codes in the input most likely indicate a
1088 * bug, so we return DECOMP_FATALERROR for them in order to turn off
1089 * compression, even though they are detected by inspecting the input.
1090 */
1091 static int
bsd_decompress(void * state,mblk_t ** dmpp)1092 bsd_decompress(void *state, mblk_t **dmpp)
1093 {
1094 mblk_t *cmsg = *dmpp, *mnext;
1095 struct bsd_db *db = (struct bsd_db *)state;
1096 uint_t max_ent = db->max_ent;
1097 uint32_t accm = 0;
1098 uint_t bitno = 32; /* 1st valid bit in accm */
1099 uint_t n_bits = db->n_bits;
1100 uint_t tgtbitno = 32 - n_bits; /* bitno when we have a code */
1101 struct bsd_dict *dictp;
1102 int explen;
1103 int seq;
1104 uint_t incode;
1105 uint_t oldcode;
1106 uint_t finchar = 0, ofinchar;
1107 uchar_t *p;
1108 uchar_t *rptr, *rmax;
1109 uchar_t *wptr, *prepos;
1110 mblk_t *dmsg;
1111 mblk_t *mret;
1112 int ilen;
1113 int dlen;
1114 int codelen;
1115 int extra;
1116 int decode_proto;
1117 int blockctr;
1118 int outlen;
1119 #if defined(lint) || defined(_lint)
1120 uchar_t adrs, ctrl;
1121 #else
1122 int adrs, ctrl;
1123 #endif
1124
1125 ASSERT(db->flags & DS_INITDONE);
1126
1127 /* Note: spppcomp already did a pullup to fix the first buffer. */
1128 *dmpp = NULL;
1129 rptr = cmsg->b_rptr;
1130 rmax = cmsg->b_wptr;
1131 ilen = 0;
1132
1133 /*
1134 * Note that we free as we go. If we fail to decompress,
1135 * there's nothing good that the caller can do.
1136 */
1137 #define ADJRPTR() \
1138 while (rptr >= rmax) { \
1139 mnext = cmsg->b_cont; \
1140 freeb(cmsg); \
1141 if ((cmsg = mnext) == NULL) { \
1142 rptr = NULL; \
1143 break; \
1144 } \
1145 rptr = cmsg->b_rptr; \
1146 rmax = cmsg->b_wptr; \
1147 ilen += rmax-rptr; \
1148 }
1149
1150 /*
1151 * Save the address/control from the PPP header
1152 * and then get the sequence number.
1153 */
1154 adrs = rptr[0];
1155 ctrl = rptr[1];
1156 rptr += 4;
1157 ADJRPTR();
1158 seq = rptr == NULL ? 0 : (*rptr++ << 8);
1159 ADJRPTR();
1160 if (rptr == NULL) {
1161 if (db->flags & DS_DEBUG) {
1162 cmn_err(CE_CONT, "bsd_decomp%d: bad buffer\n",
1163 db->unit);
1164 }
1165 return (DECOMP_ERROR);
1166 }
1167 seq |= *rptr++;
1168
1169 #ifdef DEBUG
1170 /*
1171 * If testing input, just pretending the sequence is bad here
1172 * does the trick.
1173 */
1174 if ((db->flags & DS_TESTIN) && (db->seqno % 300) == 101)
1175 seq ^= 0x55;
1176 #endif
1177
1178 /*
1179 * Check the sequence number and give up if it is not what we expect.
1180 */
1181 if (db->hsize == 0 || seq != db->seqno++) {
1182 freemsg(cmsg);
1183 if (db->flags & DS_DEBUG) {
1184 cmn_err(CE_CONT, "bsd_decomp%d: bad sequence # %d, "
1185 "expected %d\n", db->unit, seq, db->seqno - 1);
1186 }
1187
1188 return (DECOMP_ERROR);
1189 }
1190
1191 /*
1192 * Allocate one message block to start with.
1193 */
1194 if ((dmsg = allocb(DECOMP_CHUNK + db->hdrlen, BPRI_MED)) == NULL) {
1195 freemsg(cmsg);
1196 if (db->flags & DS_DEBUG) {
1197 cmn_err(CE_CONT,
1198 "bsd_decomp%d: can't allocate first buffer\n",
1199 db->unit);
1200 }
1201 return (DECOMP_ERROR);
1202 }
1203
1204 /*
1205 * Avoid an error that might cause us to allocate all available memory.
1206 * Enforce a maximum number of blocks to allocate for message. We add
1207 * a fudge factor of 5 extra blocks, in order to avoid unnecessary
1208 * DECOMP_ERROR when the code size is small (9).
1209 */
1210 blockctr = ((db->mru + 32 + DECOMP_CHUNK - 1) / DECOMP_CHUNK) + 5;
1211
1212 mret = dmsg;
1213 dmsg->b_wptr += db->hdrlen;
1214 dmsg->b_rptr = wptr = dmsg->b_wptr;
1215
1216 /*
1217 * Insert PPP header. This shouldn't be needed!
1218 */
1219 *wptr++ = adrs;
1220 *wptr++ = ctrl;
1221 prepos = wptr;
1222 *wptr++ = 0;
1223 dmsg->b_wptr = wptr;
1224
1225 explen = dmsg->b_datap->db_lim - wptr;
1226 oldcode = CLEAR;
1227 ilen = rmax-rptr;
1228
1229 outlen = 0;
1230 decode_proto = 1;
1231 for (;;) {
1232 ADJRPTR();
1233 if (rptr == NULL)
1234 break;
1235
1236 /*
1237 * Accumulate bytes until we have a complete code.
1238 * Then get the next code, relying on the 32-bit,
1239 * unsigned accm to mask the result.
1240 */
1241 bitno -= 8;
1242
1243 accm |= *rptr++ << bitno;
1244
1245 if (tgtbitno < bitno) {
1246 continue;
1247 }
1248
1249 incode = accm >> tgtbitno;
1250 accm <<= n_bits;
1251 bitno += n_bits;
1252
1253 if (incode == CLEAR) {
1254
1255 /*
1256 * The dictionary must only be cleared at
1257 * the end of a packet. But there could be an
1258 * empty message block at the end.
1259 */
1260 ADJRPTR();
1261 if (rptr != NULL) {
1262 freemsg(mret);
1263 freemsg(cmsg);
1264 if (db->flags & DS_DEBUG) {
1265 cmn_err(CE_CONT,
1266 "bsd_decomp%d: bad CLEAR\n",
1267 db->unit);
1268 }
1269
1270 return (DECOMP_FATALERROR);
1271 }
1272
1273 bsd_clear(db);
1274 /* Have to keep cleared state variables! */
1275 outlen += wptr-dmsg->b_wptr;
1276 dmsg->b_wptr = wptr;
1277 db->comp_bytes += ilen;
1278 ilen = 0;
1279 break;
1280 }
1281
1282 /*
1283 * Special case for KwKwK string
1284 */
1285 ofinchar = finchar;
1286 if (incode > max_ent) {
1287 if (incode > max_ent + 2 ||
1288 incode > db->maxmaxcode ||
1289 oldcode == CLEAR) {
1290 freemsg(cmsg);
1291 freemsg(mret);
1292
1293 /* probably a bug if we get here */
1294 if (db->flags & DS_DEBUG) {
1295 cmn_err(CE_CONT,
1296 "bsd_decomp%d: bad code 0x%x "
1297 "oldcode=0x%x ", db->unit, incode,
1298 oldcode);
1299 }
1300
1301 return (DECOMP_FATALERROR);
1302 }
1303 finchar = oldcode;
1304 extra = 1;
1305 } else {
1306 finchar = incode;
1307 extra = 0;
1308 }
1309 codelen = db->lens[finchar];
1310
1311 /*
1312 * Decode this code and install it in the decompressed buffer
1313 */
1314 explen -= codelen + extra;
1315 if (explen < 0) {
1316 /*
1317 * Allocate another message block
1318 */
1319 dlen = wptr - dmsg->b_wptr;
1320 outlen += dlen;
1321 db->in_count += dlen;
1322 dmsg->b_wptr = wptr;
1323 dlen = codelen + extra;
1324
1325 if (dlen < DECOMP_CHUNK) {
1326 dlen = DECOMP_CHUNK;
1327 }
1328
1329 if ((--blockctr < 0) ||
1330 (dmsg->b_cont = allocb(dlen, BPRI_MED)) == NULL) {
1331 freemsg(cmsg);
1332 freemsg(mret);
1333 if (db->flags & DS_DEBUG) {
1334 cmn_err(CE_CONT,
1335 "bsd_decomp%d: %s output "
1336 "buffers; outlen %d+%d\n",
1337 db->unit,
1338 (blockctr < 0 ? "too many" :
1339 "can't allocate"),
1340 outlen, dlen);
1341 }
1342 return (DECOMP_ERROR);
1343 }
1344
1345 dmsg = dmsg->b_cont;
1346 wptr = dmsg->b_wptr;
1347 explen = dmsg->b_datap->db_lim - wptr - codelen -
1348 extra;
1349 }
1350
1351 p = (wptr += codelen);
1352
1353 while (finchar > LAST) {
1354 dictp = &db->dict[db->dict[finchar].cptr];
1355 *--p = dictp->f.hs.suffix;
1356 finchar = dictp->f.hs.prefix;
1357 }
1358
1359 *--p = finchar;
1360
1361 if (decode_proto) {
1362 decode_proto = 0;
1363 /* Wow, is *this* ugly! */
1364 if (!(finchar & 1)) {
1365 if (p == prepos+1) {
1366 bcopy(p, prepos, wptr-p);
1367 wptr--;
1368 explen++;
1369 db->in_count++;
1370 } else {
1371 /* This is safe, but doesn't look it */
1372 *prepos = *p++;
1373 dmsg->b_rptr = p;
1374 }
1375 }
1376 }
1377
1378 if (extra) { /* the KwKwK case again */
1379 *wptr++ = ofinchar;
1380 }
1381
1382 /*
1383 * If not first code in a packet, and
1384 * if not out of code space, then allocate a new code.
1385 *
1386 * Keep the hash table correct so it can be used
1387 * with uncompressed packets.
1388 */
1389 if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
1390 struct bsd_dict *dictp2;
1391 uint32_t fcode;
1392 int hval;
1393 int disp;
1394
1395 fcode = BSD_KEY(oldcode, finchar);
1396 hval = BSD_HASH(oldcode, finchar, db->hshift);
1397
1398 dictp = &db->dict[hval];
1399
1400 /*
1401 * look for a free hash table entry
1402 */
1403 if (dictp->codem1 < max_ent) {
1404 disp = (hval == 0) ? 1 : hval;
1405
1406 do {
1407 hval += disp;
1408
1409 if (hval >= db->hsize) {
1410 hval -= db->hsize;
1411 if (hval >= db->hsize) {
1412 freemsg(cmsg);
1413 freemsg(mret);
1414 if (db->flags &
1415 DS_DEBUG) {
1416 cmn_err(CE_CONT, "bsd_decomp%d: internal error\n",
1417 db->unit);
1418 }
1419 return
1420 (DECOMP_FATALERROR);
1421 }
1422 }
1423
1424 dictp = &db->dict[hval];
1425
1426 } while (dictp->codem1 < max_ent);
1427 }
1428
1429 /*
1430 * Invalidate previous hash table entry
1431 * assigned this code, and then take it over
1432 */
1433 dictp2 = &db->dict[max_ent+1];
1434
1435 if (db->dict[dictp2->cptr].codem1 == max_ent) {
1436 db->dict[dictp2->cptr].codem1 = BADCODEM1;
1437 }
1438
1439 dictp2->cptr = (ushort_t)hval;
1440 dictp->codem1 = max_ent;
1441 dictp->f.fcode = fcode;
1442
1443 db->max_ent = ++max_ent;
1444 db->lens[max_ent] = db->lens[oldcode]+1;
1445
1446 /*
1447 * Expand code size if needed
1448 */
1449 if (max_ent >= MAXCODE(n_bits) &&
1450 max_ent < db->maxmaxcode) {
1451
1452 db->n_bits = ++n_bits;
1453 tgtbitno = 32-n_bits;
1454 }
1455 }
1456
1457 oldcode = incode;
1458 }
1459
1460 dlen = wptr-dmsg->b_wptr;
1461 outlen += dlen;
1462 db->in_count += dlen;
1463 dmsg->b_wptr = wptr;
1464 db->bytes_out += ilen;
1465
1466 /*
1467 * Keep the checkpoint right so that incompressible packets
1468 * clear the dictionary at the right times.
1469 */
1470 if (bsd_check(db) && (db->flags & DS_DEBUG)) {
1471 cmn_err(CE_CONT,
1472 "bsd_decomp%d: peer should have cleared dictionary\n",
1473 db->unit);
1474 }
1475
1476 ++db->comp_count;
1477 db->comp_bytes += ilen + BSD_OVHD;
1478 ++db->uncomp_count;
1479 db->uncomp_bytes += outlen;
1480
1481 *dmpp = mret;
1482
1483 return (DECOMP_OK);
1484 }
1485
1486 /* ARGSUSED */
1487 static int
bsd_set_effort(void * xarg,void * rarg,int effortlevel)1488 bsd_set_effort(void *xarg, void *rarg, int effortlevel)
1489 {
1490 #ifdef DEBUG
1491 struct bsd_db *xdb = (struct bsd_db *)xarg;
1492 struct bsd_db *rdb = (struct bsd_db *)rarg;
1493
1494 if (effortlevel == 42 || effortlevel == 2112) {
1495 /* corrupt received data. */
1496 if (rdb != NULL) {
1497 rdb->flags |= DS_TESTIN;
1498 cmn_err(CE_CONT, "bsd-comp: enabled input testing.");
1499 }
1500 if (effortlevel != 2112)
1501 return (0);
1502 }
1503 if (effortlevel == 2001 || effortlevel == 2112) {
1504 /* corrupt transmitted data. */
1505 if (xdb != NULL) {
1506 xdb->flags |= DS_TESTOUT;
1507 cmn_err(CE_CONT, "bsd-comp: enabled output testing.");
1508 }
1509 return (0);
1510 }
1511 #endif
1512 return (0);
1513 }
1514 #endif /* DO_BSD_COMPRESS */
1515