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