1 /* $NetBSD: bsd-comp.c,v 1.2 2005/02/20 10:47:17 cube Exp $ */
3 /* Because this code is derived from the 4.3BSD compress source:
6 * Copyright (c) 1985, 1986 The Regents of the University of California.
9 * This code is derived from software contributed to Berkeley by
10 * James A. Woods, derived from original work by Spencer Thomas
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. All advertising materials mentioning features or use of this software
22 * must display the following acknowledgement:
23 * This product includes software developed by the University of
24 * California, Berkeley and its contributors.
25 * 4. Neither the name of the University nor the names of its contributors
26 * may be used to endorse or promote products derived from this software
27 * without specific prior written permission.
29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
43 * Id: bsd-comp.c,v 1.4 2004/01/17 05:47:55 carlsonj Exp
46 #include <sys/types.h>
52 #include <net/ppp_defs.h>
53 #include <net/ppp-comp.h>
58 * PPP "BSD compress" compression
59 * The differences between this compression and the classic BSD LZW
60 * source are obvious from the requirement that the classic code worked
61 * with files while this handles arbitrarily long streams that
62 * are broken into packets. They are:
64 * When the code size expands, a block of junk is not emitted by
65 * the compressor and not expected by the decompressor.
67 * New codes are not necessarily assigned every time an old
68 * code is output by the compressor. This is because a packet
69 * end forces a code to be emitted, but does not imply that a
70 * new sequence has been seen.
72 * The compression ratio is checked at the first end of a packet
73 * after the appropriate gap. Besides simplifying and speeding
74 * things up, this makes it more likely that the transmitter
75 * and receiver will agree when the dictionary is cleared when
76 * compression is not going well.
80 * A dictionary for doing BSD compress.
83 int totlen
; /* length of this structure */
84 u_int hsize
; /* size of the hash table */
85 u_char hshift
; /* used in hash function */
86 u_char n_bits
; /* current bits/code */
90 u_short seqno
; /* sequence number of next packet */
91 u_int hdrlen
; /* header length to preallocate */
93 u_int maxmaxcode
; /* largest valid code */
94 u_int max_ent
; /* largest code in use */
95 u_int in_count
; /* uncompressed bytes, aged */
96 u_int bytes_out
; /* compressed bytes, aged */
97 u_int ratio
; /* recent compression ratio */
98 u_int checkpoint
; /* when to next check the ratio */
99 u_int clear_count
; /* times dictionary cleared */
100 u_int incomp_count
; /* incompressible packets */
101 u_int incomp_bytes
; /* incompressible bytes */
102 u_int uncomp_count
; /* uncompressed packets */
103 u_int uncomp_bytes
; /* uncompressed bytes */
104 u_int comp_count
; /* compressed packets */
105 u_int comp_bytes
; /* compressed bytes */
106 u_short
*lens
; /* array of lengths of codes */
108 union { /* hash value */
111 #ifdef BSD_LITTLE_ENDIAN
112 u_short prefix
; /* preceding code */
113 u_char suffix
; /* last character of new code */
117 u_char suffix
; /* last character of new code */
118 u_short prefix
; /* preceding code */
122 u_short codem1
; /* output of hash table -1 */
123 u_short cptr
; /* map code to hash table entry */
127 #define BSD_OVHD 2 /* BSD compress overhead/packet */
128 #define BSD_INIT_BITS BSD_MIN_BITS
130 static void *bsd_decomp_alloc
__P((u_char
*options
, int opt_len
));
131 static void bsd_free
__P((void *state
));
132 static int bsd_decomp_init
__P((void *state
, u_char
*options
, int opt_len
,
133 int unit
, int hdrlen
, int mru
, int debug
));
134 static void bsd_incomp
__P((void *state
, PACKETPTR in
));
135 static int bsd_decompress
__P((void *state
, PACKETPTR in
, PACKETPTR
*out
));
136 static void bsd_reset
__P((void *state
));
137 static void bsd_comp_stats
__P((void *state
, struct compstat
*stats
));
140 * Exported procedures.
142 struct compressor ppp_bsd_compress
= {
143 CI_BSD_COMPRESS
, /* compress_proto */
144 NULL
, /* comp_alloc */
145 NULL
, /* comp_free */
146 NULL
, /* comp_init */
147 NULL
, /* comp_reset */
148 NULL
, /* comp_compress */
149 NULL
, /* comp_stat */
150 bsd_decomp_alloc
, /* decomp_alloc */
151 bsd_free
, /* decomp_free */
152 bsd_decomp_init
, /* decomp_init */
153 bsd_reset
, /* decomp_reset */
154 bsd_decompress
, /* decompress */
155 bsd_incomp
, /* incomp */
156 bsd_comp_stats
, /* decomp_stat */
160 * the next two codes should not be changed lightly, as they must not
161 * lie within the contiguous general code space.
163 #define CLEAR 256 /* table clear output code */
164 #define FIRST 257 /* first free entry */
167 #define MAXCODE(b) ((1 << (b)) - 1)
168 #define BADCODEM1 MAXCODE(BSD_MAX_BITS)
170 #define BSD_HASH(prefix,suffix,hshift) ((((u_int32_t)(suffix)) << (hshift)) \
171 ^ (u_int32_t)(prefix))
172 #define BSD_KEY(prefix,suffix) ((((u_int32_t)(suffix)) << 16) \
173 + (u_int32_t)(prefix))
175 #define CHECK_GAP 10000 /* Ratio check interval */
177 #define RATIO_SCALE_LOG 8
178 #define RATIO_SCALE (1<<RATIO_SCALE_LOG)
179 #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)
181 static void bsd_clear
__P((struct bsd_db
*));
182 static int bsd_check
__P((struct bsd_db
*));
183 static void *bsd_alloc
__P((u_char
*, int, int));
184 static int bsd_init
__P((struct bsd_db
*, u_char
*, int, int, int, int,
188 * clear the dictionary
195 db
->max_ent
= FIRST
-1;
196 db
->n_bits
= BSD_INIT_BITS
;
200 db
->checkpoint
= CHECK_GAP
;
204 * If the dictionary is full, then see if it is time to reset it.
206 * Compute the compression ratio using fixed-point arithmetic
207 * with 8 fractional bits.
209 * Since we have an infinite stream instead of a single file,
210 * watch only the local compression ratio.
212 * Since both peers must reset the dictionary at the same time even in
213 * the absence of CLEAR codes (while packets are incompressible), they
214 * must compute the same ratio.
216 static int /* 1=output CLEAR */
222 if (db
->in_count
>= db
->checkpoint
) {
223 /* age the ratio by limiting the size of the counts */
224 if (db
->in_count
>= RATIO_MAX
225 || db
->bytes_out
>= RATIO_MAX
) {
226 db
->in_count
-= db
->in_count
/4;
227 db
->bytes_out
-= db
->bytes_out
/4;
230 db
->checkpoint
= db
->in_count
+ CHECK_GAP
;
232 if (db
->max_ent
>= db
->maxmaxcode
) {
233 /* Reset the dictionary only if the ratio is worse,
234 * or if it looks as if it has been poisoned
235 * by incompressible data.
237 * This does not overflow, because
238 * db->in_count <= RATIO_MAX.
240 new_ratio
= db
->in_count
<< RATIO_SCALE_LOG
;
241 if (db
->bytes_out
!= 0)
242 new_ratio
/= db
->bytes_out
;
244 if (new_ratio
< db
->ratio
|| new_ratio
< 1 * RATIO_SCALE
) {
248 db
->ratio
= new_ratio
;
258 bsd_comp_stats(state
, stats
)
260 struct compstat
*stats
;
262 struct bsd_db
*db
= (struct bsd_db
*) state
;
265 stats
->unc_bytes
= db
->uncomp_bytes
;
266 stats
->unc_packets
= db
->uncomp_count
;
267 stats
->comp_bytes
= db
->comp_bytes
;
268 stats
->comp_packets
= db
->comp_count
;
269 stats
->inc_bytes
= db
->incomp_bytes
;
270 stats
->inc_packets
= db
->incomp_count
;
271 stats
->ratio
= db
->in_count
;
273 if (stats
->ratio
<= 0x7fffff)
282 * Reset state, as on a CCP ResetReq.
288 struct bsd_db
*db
= (struct bsd_db
*) state
;
296 * Allocate space for a (de) compressor.
299 bsd_alloc(options
, opt_len
, decomp
)
304 u_int newlen
, hsize
, hshift
, maxmaxcode
;
307 if (opt_len
!= 3 || options
[0] != CI_BSD_COMPRESS
|| options
[1] != 3
308 || BSD_VERSION(options
[2]) != BSD_CURRENT_VERSION
)
311 bits
= BSD_NBITS(options
[2]);
313 case 9: /* needs 82152 for both directions */
314 case 10: /* needs 84144 */
315 case 11: /* needs 88240 */
316 case 12: /* needs 96432 */
320 case 13: /* needs 176784 */
324 case 14: /* needs 353744 */
328 case 15: /* needs 691440 */
332 case 16: /* needs 1366160--far too much, */
333 /* hsize = 69001; */ /* and 69001 is too big for cptr */
334 /* hshift = 8; */ /* in struct bsd_db */
340 maxmaxcode
= MAXCODE(bits
);
341 newlen
= sizeof(*db
) + (hsize
-1) * (sizeof(db
->dict
[0]));
342 db
= (struct bsd_db
*) malloc(newlen
);
345 memset(db
, 0, sizeof(*db
) - sizeof(db
->dict
));
350 db
->lens
= (u_short
*) malloc((maxmaxcode
+1) * sizeof(db
->lens
[0]));
360 db
->maxmaxcode
= maxmaxcode
;
370 struct bsd_db
*db
= (struct bsd_db
*) state
;
378 bsd_decomp_alloc(options
, opt_len
)
382 return bsd_alloc(options
, opt_len
, 1);
386 * Initialize the database.
389 bsd_init(db
, options
, opt_len
, unit
, hdrlen
, mru
, debug
, decomp
)
392 int opt_len
, unit
, hdrlen
, mru
, debug
, decomp
;
396 if (opt_len
< CILEN_BSD_COMPRESS
397 || options
[0] != CI_BSD_COMPRESS
|| options
[1] != CILEN_BSD_COMPRESS
398 || BSD_VERSION(options
[2]) != BSD_CURRENT_VERSION
399 || BSD_NBITS(options
[2]) != db
->maxbits
400 || (decomp
&& db
->lens
== NULL
))
410 db
->dict
[--i
].codem1
= BADCODEM1
;
411 db
->dict
[i
].cptr
= 0;
426 bsd_decomp_init(state
, options
, opt_len
, unit
, hdrlen
, mru
, debug
)
429 int opt_len
, unit
, hdrlen
, mru
, debug
;
431 return bsd_init((struct bsd_db
*) state
, options
, opt_len
,
432 unit
, hdrlen
, mru
, debug
, 1);
437 * Update the "BSD Compress" dictionary on the receiver for
438 * incompressible data by pretending to compress the incoming data.
441 bsd_incomp(state
, in
)
445 struct bsd_db
*db
= (struct bsd_db
*) state
;
446 u_int hshift
= db
->hshift
;
447 u_int max_ent
= db
->max_ent
;
448 u_int n_bits
= db
->n_bits
;
449 struct bsd_dict
*dictp
;
459 ent
= rptr
[0]; /* get the protocol */
465 if ((ent
& 1) == 0 || ent
< 0x21 || ent
> 0xf9)
469 ilen
= 1; /* count the protocol as 1 byte */
471 slen
= in
->buf
+ in
->len
- rptr
;
473 for (; slen
> 0; --slen
) {
475 fcode
= BSD_KEY(ent
, c
);
476 hval
= BSD_HASH(ent
, c
, hshift
);
477 dictp
= &db
->dict
[hval
];
479 /* validate and then check the entry */
480 if (dictp
->codem1
>= max_ent
)
482 if (dictp
->f
.fcode
== fcode
) {
483 ent
= dictp
->codem1
+1;
484 continue; /* found (prefix,suffix) */
487 /* continue probing until a match or invalid entry */
488 disp
= (hval
== 0) ? 1 : hval
;
491 if (hval
>= db
->hsize
)
493 dictp
= &db
->dict
[hval
];
494 if (dictp
->codem1
>= max_ent
)
496 } while (dictp
->f
.fcode
!= fcode
);
497 ent
= dictp
->codem1
+1;
498 continue; /* finally found (prefix,suffix) */
500 nomatch
: /* output (count) the prefix */
503 /* code -> hashtable */
504 if (max_ent
< db
->maxmaxcode
) {
505 struct bsd_dict
*dictp2
;
506 /* expand code size if needed */
507 if (max_ent
>= MAXCODE(n_bits
))
508 db
->n_bits
= ++n_bits
;
510 /* Invalidate previous hash table entry
511 * assigned this code, and then take it over.
513 dictp2
= &db
->dict
[max_ent
+1];
514 if (db
->dict
[dictp2
->cptr
].codem1
== max_ent
)
515 db
->dict
[dictp2
->cptr
].codem1
= BADCODEM1
;
517 dictp
->codem1
= max_ent
;
518 dictp
->f
.fcode
= fcode
;
520 db
->max_ent
= ++max_ent
;
521 db
->lens
[max_ent
] = db
->lens
[ent
]+1;
525 bitno
+= n_bits
; /* output (count) the last code */
526 db
->bytes_out
+= bitno
/8;
527 db
->in_count
+= ilen
;
531 db
->incomp_bytes
+= ilen
;
533 db
->uncomp_bytes
+= ilen
;
535 /* Increase code size if we would have without the packet
536 * boundary and as the decompressor will.
538 if (max_ent
>= MAXCODE(n_bits
) && max_ent
< db
->maxmaxcode
)
544 * Decompress "BSD Compress"
546 * Because of patent problems, we return DECOMP_ERROR for errors
547 * found by inspecting the input data and for system problems, but
548 * DECOMP_FATALERROR for any errors which could possibly be said to
549 * be being detected "after" decompression. For DECOMP_ERROR,
550 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
551 * infringing a patent of Motorola's if we do, so we take CCP down
554 * Given that the frame has the correct sequence number and a good FCS,
555 * errors such as invalid codes in the input most likely indicate a
556 * bug, so we return DECOMP_FATALERROR for them in order to turn off
557 * compression, even though they are detected by inspecting the input.
560 bsd_decompress(state
, in
, out
)
565 struct bsd_db
*db
= (struct bsd_db
*) state
;
566 u_int max_ent
= db
->max_ent
;
568 u_int bitno
= 32; /* 1st valid bit in accm */
569 u_int n_bits
= db
->n_bits
;
570 u_int tgtbitno
= 32-n_bits
; /* bitno when we have a code */
571 struct bsd_dict
*dictp
;
572 int explen
, seq
, len
;
573 u_int incode
, oldcode
, finchar
;
574 u_char
*p
, *rptr
, *wptr
;
581 ++rptr
; /* skip protocol (assumed 0xfd) */
582 seq
= (rptr
[0] << 8) + rptr
[1];
584 ilen
= len
= in
->buf
+ in
->len
- rptr
;
587 * Check the sequence number and give up if it is not what we expect.
589 if (seq
!= db
->seqno
++) {
591 printf("bsd_decomp%d: bad sequence # %d, expected %d\n",
592 db
->unit
, seq
, db
->seqno
- 1);
596 wptr
= (*out
)->buf
+ db
->hdrlen
;
602 * Accumulate bytes until we have a complete code.
603 * Then get the next code, relying on the 32-bit,
604 * unsigned accm to mask the result.
607 accm
|= *rptr
++ << bitno
;
609 if (tgtbitno
< bitno
)
611 incode
= accm
>> tgtbitno
;
615 if (incode
== CLEAR
) {
617 * The dictionary must only be cleared at
618 * the end of a packet. But there could be an
619 * empty message block at the end.
623 printf("bsd_decomp%d: bad CLEAR\n", db
->unit
);
624 return DECOMP_FATALERROR
;
631 if (incode
> max_ent
+ 2 || incode
> db
->maxmaxcode
632 || (incode
> max_ent
&& oldcode
== CLEAR
)) {
634 printf("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
635 db
->unit
, incode
, oldcode
);
636 printf("max_ent=0x%x seqno=%d\n",
639 return DECOMP_FATALERROR
; /* probably a bug */
642 /* Special case for KwKwK string. */
643 if (incode
> max_ent
) {
651 codelen
= db
->lens
[finchar
];
652 explen
+= codelen
+ extra
;
653 if (explen
> db
->mru
+ 1) {
655 printf("bsd_decomp%d: ran out of mru\n", db
->unit
);
656 return DECOMP_FATALERROR
;
660 * Decode this code and install it in the decompressed buffer.
662 p
= (wptr
+= codelen
);
663 while (finchar
> LAST
) {
664 dictp
= &db
->dict
[db
->dict
[finchar
].cptr
];
668 printf("bsd_decomp%d: fell off end of chain ", db
->unit
);
669 printf("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
670 incode
, finchar
, db
->dict
[finchar
].cptr
, max_ent
);
671 return DECOMP_FATALERROR
;
673 if (dictp
->codem1
!= finchar
-1) {
674 printf("bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",
675 db
->unit
, incode
, finchar
);
676 printf("oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode
,
677 db
->dict
[finchar
].cptr
, dictp
->codem1
);
678 return DECOMP_FATALERROR
;
681 *--p
= dictp
->f
.hs
.suffix
;
682 finchar
= dictp
->f
.hs
.prefix
;
688 printf("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
689 db
->unit
, codelen
, incode
, max_ent
);
692 if (extra
) /* the KwKwK case again */
696 * If not first code in a packet, and
697 * if not out of code space, then allocate a new code.
699 * Keep the hash table correct so it can be used
700 * with uncompressed packets.
702 if (oldcode
!= CLEAR
&& max_ent
< db
->maxmaxcode
) {
703 struct bsd_dict
*dictp2
;
707 fcode
= BSD_KEY(oldcode
,finchar
);
708 hval
= BSD_HASH(oldcode
,finchar
,db
->hshift
);
709 dictp
= &db
->dict
[hval
];
711 /* look for a free hash table entry */
712 if (dictp
->codem1
< max_ent
) {
713 disp
= (hval
== 0) ? 1 : hval
;
716 if (hval
>= db
->hsize
)
718 dictp
= &db
->dict
[hval
];
719 } while (dictp
->codem1
< max_ent
);
723 * Invalidate previous hash table entry
724 * assigned this code, and then take it over
726 dictp2
= &db
->dict
[max_ent
+1];
727 if (db
->dict
[dictp2
->cptr
].codem1
== max_ent
) {
728 db
->dict
[dictp2
->cptr
].codem1
= BADCODEM1
;
731 dictp
->codem1
= max_ent
;
732 dictp
->f
.fcode
= fcode
;
734 db
->max_ent
= ++max_ent
;
735 db
->lens
[max_ent
] = db
->lens
[oldcode
]+1;
737 /* Expand code size if needed. */
738 if (max_ent
>= MAXCODE(n_bits
) && max_ent
< db
->maxmaxcode
) {
739 db
->n_bits
= ++n_bits
;
740 tgtbitno
= 32-n_bits
;
745 (*out
)->len
= wptr
- ((*out
)->buf
+ db
->hdrlen
);
748 * Keep the checkpoint right so that incompressible packets
749 * clear the dictionary at the right times.
751 db
->bytes_out
+= ilen
;
752 db
->in_count
+= explen
;
753 if (bsd_check(db
) && db
->debug
) {
754 printf("bsd_decomp%d: peer should have cleared dictionary\n",
759 db
->comp_bytes
+= ilen
+ BSD_OVHD
;
761 db
->uncomp_bytes
+= explen
;
765 #endif /* DO_BSD_COMPRESS */