updates from Steve Perkins
[ppp.git] / NeXT / bsd-comp.c
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  * Rewritten for NextStep's funky kernel functions, I/O threads,
40  * and netbufs (instead of real mbufs).  Also, ifnets don't install
41  * into the kernel under NS as they do under BSD.  We have tried to
42  * make the code remain as similar to the NetBSD version without
43  * incurring too much hassle.  This code is the merge of 
44  * Philip Prindeville's <philipp@res.enst.fr>/Pete French's <pete@ohm.york.ac.uk>
45  * and Stephen Perkins'  <perkins@cps.msu.edu> independent ports.
46  *
47  */
48
49 /*
50  * This version is for use with mbufs on BSD-derived systems.
51  *
52  * $Id: bsd-comp.c,v 1.4 1997/04/30 05:39:29 paulus Exp $
53  */
54
55 #include <sys/types.h>
56 #include <sys/param.h>
57 #include <sys/types.h>
58 #include <sys/socket.h>
59
60 #define KERNEL 1
61 #include <net/netbuf.h>
62 #include <net/if.h>
63
64 #include <net/ppp_defs.h>
65 #include <net/if_ppp.h>
66
67 #include "nbq.h"
68
69 #define PACKETPTR       NETBUF_T
70 #include <net/ppp-comp.h>
71
72
73 /*
74  * We align with this number of bits zero. The code makes the somewhat
75  * suspect assumption that an address can be held in an unsigned long.
76  * Sadly this is necessary to do bit operations on it.
77  */
78
79 #define Z_ALIGN 3       /* 8 byte boudary */
80 #define Z_EXTRA ((unsigned long)((1<<Z_ALIGN)-1))
81 #define ALIGN(x) ((x+Z_EXTRA) & ~Z_EXTRA)
82
83 #if DO_BSD_COMPRESS
84
85 /*
86  * The following includes are necessary to correctly
87  * support BYTE_ORDER.  -SJP
88  */
89
90 #include <netinet/in.h>
91 #include <netinet/in_systm.h>
92 #include <netinet/in_var.h>
93 #include <netinet/ip.h>
94
95 #define mtod(m,type)    ((type)NB_MAP(m))
96 typedef unsigned short u_int16_t;
97
98 /*
99  * PPP "BSD compress" compression
100  *  The differences between this compression and the classic BSD LZW
101  *  source are obvious from the requirement that the classic code worked
102  *  with files while this handles arbitrarily long streams that
103  *  are broken into packets.  They are:
104  *
105  *      When the code size expands, a block of junk is not emitted by
106  *          the compressor and not expected by the decompressor.
107  *
108  *      New codes are not necessarily assigned every time an old
109  *          code is output by the compressor.  This is because a packet
110  *          end forces a code to be emitted, but does not imply that a
111  *          new sequence has been seen.
112  *
113  *      The compression ratio is checked at the first end of a packet
114  *          after the appropriate gap.  Besides simplifying and speeding
115  *          things up, this makes it more likely that the transmitter
116  *          and receiver will agree when the dictionary is cleared when
117  *          compression is not going well.
118  */
119
120 /*
121  * A dictionary for doing BSD compress.
122  */
123 struct bsd_db {
124     void    *kbase;                     /* actual kalloc'd address for struct */
125     void    *klens;                     /* actual kalloc'd address for lens */
126     int     totlen;                     /* length of this structure */
127     u_int   hsize;                      /* size of the hash table */
128     u_char  hshift;                     /* used in hash function */
129     u_char  n_bits;                     /* current bits/code */
130     u_char  maxbits;
131     u_char  debug;
132     u_char  unit;
133     u_int16_t seqno;                    /* sequence # of next packet */
134     u_int   hdrlen;                     /* header length to preallocate */
135     u_int   mru;
136     u_int   maxmaxcode;                 /* largest valid code */
137     u_int   max_ent;                    /* largest code in use */
138     u_int   in_count;                   /* uncompressed bytes, aged */
139     u_int   bytes_out;                  /* compressed bytes, aged */
140     u_int   ratio;                      /* recent compression ratio */
141     u_int   checkpoint;                 /* when to next check the ratio */
142     u_int   clear_count;                /* times dictionary cleared */
143     u_int   incomp_count;               /* incompressible packets */
144     u_int   incomp_bytes;               /* incompressible bytes */
145     u_int   uncomp_count;               /* uncompressed packets */
146     u_int   uncomp_bytes;               /* uncompressed bytes */
147     u_int   comp_count;                 /* compressed packets */
148     u_int   comp_bytes;                 /* compressed bytes */
149     u_int16_t *lens;                    /* array of lengths of codes */
150     struct bsd_dict {
151         union {                         /* hash value */
152             u_int32_t   fcode;
153             struct {
154 #if BYTE_ORDER == LITTLE_ENDIAN
155                 u_int16_t prefix;               /* preceding code */
156                 u_char  suffix;         /* last character of new code */
157                 u_char  pad;
158 #else
159                 u_char  pad;
160                 u_char  suffix;         /* last character of new code */
161                 u_int16_t prefix;               /* preceding code */
162 #endif
163             } hs;
164         } f;
165         u_int16_t codem1;                       /* output of hash table -1 */
166         u_int16_t cptr;                 /* map code to hash table entry */
167     } dict[1];
168 };
169
170 #define BSD_OVHD        2               /* BSD compress overhead/packet */
171 #define BSD_INIT_BITS   BSD_MIN_BITS
172
173 static void     *bsd_comp_alloc __P((u_char *options, int opt_len));
174 static void     *bsd_decomp_alloc __P((u_char *options, int opt_len));
175 static void     bsd_free __P((void *state));
176 static int      bsd_comp_init __P((void *state, u_char *options, int opt_len,
177                                    int unit, int hdrlen, int debug));
178 static int      bsd_decomp_init __P((void *state, u_char *options, int opt_len,
179                                      int unit, int hdrlen, int mru, int debug));
180 static int      bsd_compress __P((void *state, NETBUF_T *mret,
181                                   NETBUF_T mp, int slen, int maxolen));
182 static void     bsd_incomp __P((void *state, NETBUF_T dmsg));
183 static int      bsd_decompress __P((void *state, NETBUF_T cmp, NETBUF_T *dmpp));
184 static void     bsd_reset __P((void *state));
185 static void     bsd_comp_stats __P((void *state, struct compstat *stats));
186
187 /*
188  * Procedures exported to if_ppp.c.
189  */
190 struct compressor ppp_bsd_compress = {
191     CI_BSD_COMPRESS,            /* compress_proto */
192     bsd_comp_alloc,             /* comp_alloc */
193     bsd_free,                   /* comp_free */
194     bsd_comp_init,              /* comp_init */
195     bsd_reset,                  /* comp_reset */
196     bsd_compress,               /* compress */
197     bsd_comp_stats,             /* comp_stat */
198     bsd_decomp_alloc,           /* decomp_alloc */
199     bsd_free,                   /* decomp_free */
200     bsd_decomp_init,            /* decomp_init */
201     bsd_reset,                  /* decomp_reset */
202     bsd_decompress,             /* decompress */
203     bsd_incomp,                 /* incomp */
204     bsd_comp_stats,             /* decomp_stat */
205 };
206
207 /*
208  * the next two codes should not be changed lightly, as they must not
209  * lie within the contiguous general code space.
210  */
211 #define CLEAR   256                     /* table clear output code */
212 #define FIRST   257                     /* first free entry */
213 #define LAST    255
214
215 #define MAXCODE(b)      ((1 << (b)) - 1)
216 #define BADCODEM1       MAXCODE(BSD_MAX_BITS)
217
218 #define BSD_HASH(prefix,suffix,hshift)  ((((u_int32_t)(suffix)) << (hshift)) \
219                                          ^ (u_int32_t)(prefix))
220 #define BSD_KEY(prefix,suffix)          ((((u_int32_t)(suffix)) << 16) \
221                                          + (u_int32_t)(prefix))
222
223 #define CHECK_GAP       10000           /* Ratio check interval */
224
225 #define RATIO_SCALE_LOG 8
226 #define RATIO_SCALE     (1<<RATIO_SCALE_LOG)
227 #define RATIO_MAX       (0x7fffffff>>RATIO_SCALE_LOG)
228
229 /* Could include inlines.h */
230 #ifndef IOLog
231 #define IOLog printf
232 #define IOLogDbg        if (db->debug) printf
233 #else
234 #define IOLogDbg        if (db->debug) IOLog
235 #endif
236
237 /*
238  * clear the dictionary
239  */
240 static void
241 bsd_clear(db)
242     struct bsd_db *db;
243 {
244     db->clear_count++;
245     db->max_ent = FIRST-1;
246     db->n_bits = BSD_INIT_BITS;
247     db->ratio = 0;
248     db->bytes_out = 0;
249     db->in_count = 0;
250     db->incomp_count = 0;
251     db->checkpoint = CHECK_GAP;
252 }
253
254 /*
255  * If the dictionary is full, then see if it is time to reset it.
256  *
257  * Compute the compression ratio using fixed-point arithmetic
258  * with 8 fractional bits.
259  *
260  * Since we have an infinite stream instead of a single file,
261  * watch only the local compression ratio.
262  *
263  * Since both peers must reset the dictionary at the same time even in
264  * the absence of CLEAR codes (while packets are incompressible), they
265  * must compute the same ratio.
266  */
267 static int                              /* 1=output CLEAR */
268 bsd_check(db)
269     struct bsd_db *db;
270 {
271     u_int new_ratio;
272
273     if (db->in_count >= db->checkpoint)
274       {
275
276         /* age the ratio by limiting the size of the counts */
277         if (db->in_count >= RATIO_MAX
278             || db->bytes_out >= RATIO_MAX) {
279             db->in_count -= db->in_count/4;
280             db->bytes_out -= db->bytes_out/4;
281         }
282
283         db->checkpoint = db->in_count + CHECK_GAP;
284
285         if (db->max_ent >= db->maxmaxcode) {
286             /* Reset the dictionary only if the ratio is worse,
287              * or if it looks as if it has been poisoned
288              * by incompressible data.
289              *
290              * This does not overflow, because
291              *  db->in_count <= RATIO_MAX.
292              */
293             new_ratio = db->in_count << RATIO_SCALE_LOG;
294             if (db->bytes_out != 0)
295                 new_ratio /= db->bytes_out;
296
297             if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
298               {
299                 bsd_clear(db);
300                 return 1;
301               }
302             db->ratio = new_ratio;
303         }
304     }
305     return 0;
306 }
307
308 /*
309  * Return statistics.
310  */
311 static void
312 bsd_comp_stats(state, stats)
313     void *state;
314     struct compstat *stats;
315 {
316     struct bsd_db *db = (struct bsd_db *) state;
317     u_int out;
318
319     stats->unc_bytes = db->uncomp_bytes;
320     stats->unc_packets = db->uncomp_count;
321     stats->comp_bytes = db->comp_bytes;
322     stats->comp_packets = db->comp_count;
323     stats->inc_bytes = db->incomp_bytes;
324     stats->inc_packets = db->incomp_count;
325     stats->ratio = db->in_count;
326     out = db->bytes_out;
327     if (stats->ratio <= 0x7fffff)
328       stats->ratio <<= 8;
329     else
330       out >>= 8;
331     if (out != 0)
332       stats->ratio /= out;
333 }
334
335 /*
336  * Reset state, as on a CCP ResetReq.
337  */
338 static void
339 bsd_reset(state)
340     void *state;
341 {
342     struct bsd_db *db = (struct bsd_db *) state;
343
344     db->seqno = 0;
345     bsd_clear(db);
346     db->clear_count = 0;
347 }
348
349 /*
350  * Allocate space for a (de) compressor.
351  */
352 static void *
353 bsd_alloc(options, opt_len, decomp)
354     u_char *options;
355     int opt_len, decomp;
356 {
357     int bits;
358     u_int newlen, hsize, hshift, maxmaxcode;
359     struct bsd_db *db;
360
361     if (opt_len != CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
362         || options[1] != CILEN_BSD_COMPRESS
363         || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
364         return NULL;
365     bits = BSD_NBITS(options[2]);
366     switch (bits) {
367     case 9:                     /* needs 82152 for both directions */
368     case 10:                    /* needs 84144 */
369     case 11:                    /* needs 88240 */
370     case 12:                    /* needs 96432 */
371         hsize = 5003;
372         hshift = 4;
373         break;
374     case 13:                    /* needs 176784 */
375         hsize = 9001;
376         hshift = 5;
377         break;
378     case 14:                    /* needs 353744 */
379         hsize = 18013;
380         hshift = 6;
381         break;
382     case 15:                    /* needs 691440 */
383         hsize = 35023;
384         hshift = 7;
385         break;
386     case 16:                    /* needs 1366160--far too much, */
387         /* hsize = 69001; */    /* and 69001 is too big for cptr */
388         /* hshift = 8; */       /* in struct bsd_db */
389         /* break; */
390     default:
391         return NULL;
392     }
393
394     maxmaxcode = MAXCODE(bits);
395     newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0]));
396     {
397     unsigned long kret;
398     kret = (unsigned long) kalloc(Z_EXTRA + newlen);
399     if (!kret)
400         return NULL;
401     db = (struct bsd_db *) ALIGN(kret);
402     bzero(db, sizeof(*db) - sizeof(db->dict));
403     db->kbase = (void *)kret;
404     }
405
406     if (!decomp) {
407         db->lens = NULL;
408     } else {
409         unsigned long kret;
410         kret = (unsigned long) kalloc(Z_EXTRA +
411                                ((maxmaxcode+1) * sizeof(db->lens[0])));
412         if (!kret) {
413             kfree(db->kbase, newlen + Z_EXTRA);
414             return NULL;
415         }
416         db->lens = (u_int16_t *) ALIGN(kret);
417         db->klens = (void *) kret;
418     }
419
420     db->totlen = newlen;
421     db->hsize = hsize;
422     db->hshift = hshift;
423     db->maxmaxcode = maxmaxcode;
424     db->maxbits = bits;
425
426     return (void *) db;
427 }
428
429 static void
430 bsd_free(state)
431     void *state;
432 {
433     struct bsd_db *db = (struct bsd_db *) state;
434
435     if (db->lens)
436         kfree(db->klens, ((db->maxmaxcode+1) * sizeof(db->lens[0])) + Z_EXTRA);
437     kfree(db->kbase, db->totlen + Z_EXTRA);
438 }
439
440 static void *
441 bsd_comp_alloc(options, opt_len)
442     u_char *options;
443     int opt_len;
444 {
445     return bsd_alloc(options, opt_len, 0);
446 }
447
448 static void *
449 bsd_decomp_alloc(options, opt_len)
450     u_char *options;
451     int opt_len;
452 {
453     return bsd_alloc(options, opt_len, 1);
454 }
455
456 /*
457  * Initialize the database.
458  */
459 static int
460 bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp)
461     struct bsd_db *db;
462     u_char *options;
463     int opt_len, unit, hdrlen, mru, debug, decomp;
464 {
465     int i;
466
467     if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS
468         || options[1] != CILEN_BSD_COMPRESS
469         || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION
470         || BSD_NBITS(options[2]) != db->maxbits
471         || decomp && db->lens == NULL)
472         return 0;
473
474     if (decomp) {
475         i = LAST+1;
476         while (i != 0)
477             db->lens[--i] = 1;
478     }
479     i = db->hsize;
480     while (i != 0) {
481         db->dict[--i].codem1 = BADCODEM1;
482         db->dict[i].cptr = 0;
483     }
484
485     db->unit = unit;
486     db->hdrlen = hdrlen;
487     db->mru = mru;
488 #ifndef DEBUG
489     if (debug)
490 #endif
491         db->debug = 1;
492
493     bsd_reset(db);
494
495     return 1;
496 }
497
498 static int
499 bsd_comp_init(state, options, opt_len, unit, hdrlen, debug)
500     void *state;
501     u_char *options;
502     int opt_len, unit, hdrlen, debug;
503 {
504     return bsd_init((struct bsd_db *) state, options, opt_len,
505                     unit, hdrlen, 0, debug, 0);
506 }
507
508 static int
509 bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug)
510     void *state;
511     u_char *options;
512     int opt_len, unit, hdrlen, mru, debug;
513 {
514     return bsd_init((struct bsd_db *) state, options, opt_len,
515                     unit, hdrlen, mru, debug, 1);
516 }
517
518
519 /*
520  * compress a packet
521  *      One change from the BSD compress command is that when the
522  *      code size expands, we do not output a bunch of padding.
523  */
524 int                                     /* new slen */
525 bsd_compress(state, mret, mp, slen, maxolen)
526     void *state;
527     NETBUF_T *mret;             /* return compressed netbuf here */
528     NETBUF_T mp;                /* from here */
529     int slen;                   /* uncompressed length */
530     int maxolen;                /* max compressed length */
531 {
532     struct bsd_db *db = (struct bsd_db *) state;
533     int hshift = db->hshift;
534     u_int max_ent = db->max_ent;
535     u_int n_bits = db->n_bits;
536     u_int bitno = 32;
537     u_int32_t accm = 0, fcode;
538     struct bsd_dict *dictp;
539     u_char c;
540     int hval, disp, ent, ilen;
541     u_char *rptr, *wptr;
542     u_char *cp_end;
543     int olen;
544     NETBUF_T m;
545
546 #define PUTBYTE(v) {                                    \
547     ++olen;                                             \
548     if (wptr) {                                         \
549         *wptr++ = (v);                                  \
550         if (wptr >= cp_end)                             \
551             wptr = NULL;                                \
552     }                                                   \
553 }
554
555 #define OUTPUT(ent) {                                   \
556     bitno -= n_bits;                                    \
557     accm |= ((ent) << bitno);                           \
558     do {                                                \
559         PUTBYTE(accm >> 24);                            \
560         accm <<= 8;                                     \
561         bitno += 8;                                     \
562     } while (bitno <= 24);                              \
563 }
564
565     /*
566      * If the protocol is not in the range we're interested in,
567      * just return without compressing the packet.  If it is,
568      * the protocol becomes the first byte to compress.
569      */
570     rptr = mtod(mp, u_char *);
571     ent = PPP_PROTOCOL(rptr);
572     if (ent < CI_BSD_COMPRESS || ent > 0xf9) {
573         *mret = NULL;
574         return slen;
575     }
576
577     /* Don't generate compressed packets which are larger than
578        the uncompressed packet. */
579     if (maxolen > slen)
580         maxolen = slen;
581
582     /* Allocate one mbuf to start with. (don't forget space for the FCS!) */
583     m = NB_ALLOC(maxolen + db->hdrlen + PPP_FCSLEN);
584     *mret = m;
585     if (m != NULL) {
586       if (db->hdrlen > 0)
587         NB_SHRINK_TOP(m, db->hdrlen);
588       NB_SHRINK_BOT(m, PPP_FCSLEN);  /* grown by pppstart() */
589         wptr = mtod(m, u_char *);
590         cp_end = wptr + maxolen;
591     } else
592         wptr = cp_end = NULL;
593
594     /*
595      * Copy the PPP header over, changing the protocol,
596      * and install the 2-byte packet sequence number.
597      */
598     if (wptr) {
599         *wptr++ = PPP_ADDRESS(rptr);    /* assumes the ppp header is */
600         *wptr++ = PPP_CONTROL(rptr);    /* all in one mbuf */
601         *wptr++ = 0;                    /* change the protocol */
602         *wptr++ = PPP_COMP;
603         *wptr++ = db->seqno >> 8;
604         *wptr++ = db->seqno;
605     }
606     ++db->seqno;
607
608     olen = 0;
609     rptr += PPP_HDRLEN;
610     slen = NB_SIZE(mp) - PPP_HDRLEN;
611     ilen = slen + 1;
612     while (slen > 0) {
613         slen--;
614         c = *rptr++;
615         fcode = BSD_KEY(ent, c);
616         hval = BSD_HASH(ent, c, hshift);
617         dictp = &db->dict[hval];
618
619         /* Validate and then check the entry. */
620         if (dictp->codem1 >= max_ent)
621             goto nomatch;
622         if (dictp->f.fcode == fcode) {
623             ent = dictp->codem1+1;
624             continue;   /* found (prefix,suffix) */
625         }
626
627         /* continue probing until a match or invalid entry */
628         disp = (hval == 0) ? 1 : hval;
629         do {
630             hval += disp;
631             if (hval >= db->hsize)
632                 hval -= db->hsize;
633             dictp = &db->dict[hval];
634             if (dictp->codem1 >= max_ent)
635                 goto nomatch;
636         } while (dictp->f.fcode != fcode);
637         ent = dictp->codem1 + 1;        /* finally found (prefix,suffix) */
638         continue;
639
640     nomatch:
641         OUTPUT(ent);            /* output the prefix */
642
643         /* code -> hashtable */
644         if (max_ent < db->maxmaxcode) {
645             struct bsd_dict *dictp2;
646             /* expand code size if needed */
647             if (max_ent >= MAXCODE(n_bits))
648                 db->n_bits = ++n_bits;
649
650             /* Invalidate old hash table entry using
651              * this code, and then take it over.
652              */
653             dictp2 = &db->dict[max_ent+1];
654             if (db->dict[dictp2->cptr].codem1 == max_ent)
655                 db->dict[dictp2->cptr].codem1 = BADCODEM1;
656             dictp2->cptr = hval;
657             dictp->codem1 = max_ent;
658             dictp->f.fcode = fcode;
659
660             db->max_ent = ++max_ent;
661         }
662         ent = c;
663     }
664
665     OUTPUT(ent);                /* output the last code */
666     db->bytes_out += olen;
667     db->in_count += ilen;
668     if (bitno < 32)
669         ++db->bytes_out;        /* count complete bytes */
670
671     if (bsd_check(db))
672         OUTPUT(CLEAR);          /* do not count the CLEAR */
673
674     /*
675      * Pad dribble bits of last code with ones.
676      * Do not emit a completely useless byte of ones.
677      */
678     if (bitno != 32)
679         PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
680
681     /*
682      * Increase code size if we would have without the packet
683      * boundary and as the decompressor will.
684      */
685     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
686         db->n_bits++;
687
688     db->uncomp_bytes += ilen;
689     ++db->uncomp_count;
690     if (olen + PPP_HDRLEN + BSD_OVHD > maxolen || wptr == NULL) {
691         /* throw away the compressed stuff if it is longer than uncompressed */
692         if (*mret != NULL) {
693             NB_FREE(*mret);
694             *mret = NULL;
695         }
696         ++db->incomp_count;
697         db->incomp_bytes += ilen;
698     } else {
699         NB_SHRINK_BOT(m, NB_SIZE(m) - (wptr - mtod(m, u_char *)));
700         ++db->comp_count;
701         db->comp_bytes += olen + BSD_OVHD;
702     }
703
704     return olen + PPP_HDRLEN + BSD_OVHD;
705 #undef OUTPUT
706 #undef PUTBYTE
707 }
708
709
710 /*
711  * Update the "BSD Compress" dictionary on the receiver for
712  * incompressible data by pretending to compress the incoming data.
713  */
714 static void
715 bsd_incomp(state, dmsg)
716     void *state;
717     NETBUF_T dmsg;
718 {
719     struct bsd_db *db = (struct bsd_db *) state;
720     u_int hshift = db->hshift;
721     u_int max_ent = db->max_ent;
722     u_int n_bits = db->n_bits;
723     struct bsd_dict *dictp;
724     u_int32_t fcode;
725     u_char c;
726     u_int32_t hval, disp;
727     int slen, ilen;
728     u_int bitno = 7;
729     u_char *rptr;
730     u_int ent;
731
732     /*
733      * If the protocol is not in the range we're interested in,
734      * just return without looking at the packet.  If it is,
735      * the protocol becomes the first byte to "compress".
736      */
737     rptr = mtod(dmsg, u_char *);
738     ent = PPP_PROTOCOL(rptr);
739     if (ent < CI_BSD_COMPRESS || ent > 0xf9)
740         return;
741
742     db->incomp_count++;
743     db->seqno++;
744     ilen = 1;           /* count the protocol as 1 byte */
745     rptr += PPP_HDRLEN;
746     slen = NB_SIZE(dmsg) - PPP_HDRLEN;
747     ilen += slen;
748
749     do {
750         c = *rptr++;
751         fcode = BSD_KEY(ent, c);
752         hval = BSD_HASH(ent, c, hshift);
753         dictp = &db->dict[hval];
754
755         /* validate and then check the entry */
756         if (dictp->codem1 >= max_ent)
757             goto nomatch;
758         if (dictp->f.fcode == fcode) {
759             ent = dictp->codem1+1;
760             continue;   /* found (prefix,suffix) */
761         }
762
763         /* continue probing until a match or invalid entry */
764         disp = (hval == 0) ? 1 : hval;
765         do {
766             hval += disp;
767             if (hval >= db->hsize)
768                 hval -= db->hsize;
769             dictp = &db->dict[hval];
770             if (dictp->codem1 >= max_ent)
771                 goto nomatch;
772         } while (dictp->f.fcode != fcode);
773         ent = dictp->codem1+1;
774         continue;       /* finally found (prefix,suffix) */
775
776     nomatch:            /* output (count) the prefix */
777         bitno += n_bits;
778
779         /* code -> hashtable */
780         if (max_ent < db->maxmaxcode) {
781             struct bsd_dict *dictp2;
782             /* expand code size if needed */
783             if (max_ent >= MAXCODE(n_bits))
784                 db->n_bits = ++n_bits;
785
786             /* Invalidate previous hash table entry
787              * assigned this code, and then take it over.
788              */
789             dictp2 = &db->dict[max_ent+1];
790             if (db->dict[dictp2->cptr].codem1 == max_ent)
791                 db->dict[dictp2->cptr].codem1 = BADCODEM1;
792             dictp2->cptr = hval;
793             dictp->codem1 = max_ent;
794             dictp->f.fcode = fcode;
795
796             db->max_ent = ++max_ent;
797             db->lens[max_ent] = db->lens[ent]+1;
798         }
799         ent = c;
800     } while (--slen != 0);
801     bitno += n_bits;            /* output (count) the last code */
802     db->bytes_out += bitno/8;
803     db->in_count += ilen;
804     (void)bsd_check(db);
805
806     ++db->incomp_count;
807     db->incomp_bytes += ilen;
808     ++db->uncomp_count;
809     db->uncomp_bytes += ilen;
810
811     /* Increase code size if we would have without the packet
812      * boundary and as the decompressor will.
813      */
814     if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
815         db->n_bits++;
816 }
817
818
819 /*
820  * Decompress "BSD Compress".
821  *
822  * Because of patent problems, we return DECOMP_ERROR for errors
823  * found by inspecting the input data and for system problems, but
824  * DECOMP_FATALERROR for any errors which could possibly be said to
825  * be being detected "after" decompression.  For DECOMP_ERROR,
826  * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
827  * infringing a patent of Motorola's if we do, so we take CCP down
828  * instead.
829  *
830  * Given that the frame has the correct sequence number and a good FCS,
831  * errors such as invalid codes in the input most likely indicate a
832  * bug, so we return DECOMP_FATALERROR for them in order to turn off
833  * compression, even though they are detected by inspecting the input.
834  */
835 int
836 bsd_decompress(state, cmp, dmpp)
837     void *state;
838     NETBUF_T cmp, *dmpp;
839 {
840     struct bsd_db *db = (struct bsd_db *) state;
841     u_int max_ent = db->max_ent;
842     u_int32_t accm = 0;
843     u_int bitno = 32;           /* 1st valid bit in accm */
844     u_int n_bits = db->n_bits;
845     u_int tgtbitno = 32-n_bits; /* bitno when we have a code */
846     struct bsd_dict *dictp;
847     int explen, seq, len;
848     u_int incode, oldcode, finchar;
849     u_char *p, *rptr, *wptr;
850     NETBUF_T dmp, mret;
851     int adrs, ctrl, ilen;
852     int space, codelen, extra, maxilen;
853
854     /*
855      * Save the address/control from the PPP header
856      * and then get the sequence number.
857      */
858     *dmpp = NULL;
859     rptr = mtod(cmp, u_char *);
860     adrs = PPP_ADDRESS(rptr);
861     ctrl = PPP_CONTROL(rptr);
862     rptr += PPP_HDRLEN;
863     len = NB_SIZE(cmp) - PPP_HDRLEN;
864     seq = (rptr[0] << 8) + rptr[1];
865     rptr += BSD_OVHD;
866     len -= BSD_OVHD;
867
868     /*
869      * Check the sequence number and give up if it differs from
870      * the value we're expecting.
871      */
872     if (seq != db->seqno) {
873         IOLogDbg("bsd_decomp%d: bad sequence # %d, expected %d\n",
874                    db->unit, seq, db->seqno - 1);
875         return DECOMP_ERROR;
876     }
877     ++db->seqno;
878
879     /*
880      * Allocate an netbuf large enough for all the data.
881      */
882     maxilen = db->mru + db->hdrlen + PPP_HDRLEN;        /* no FCS */
883     dmp = NB_ALLOC(maxilen);                    /* XXX */
884     if (dmp == NULL)
885         return DECOMP_ERROR;
886     if (db->hdrlen > 0)
887         NB_SHRINK_TOP(dmp, db->hdrlen);
888     mret = dmp;
889     wptr = mtod(dmp, u_char *);
890     space = NB_SIZE(dmp) - PPP_HDRLEN + 1;
891
892     /*
893      * Fill in the ppp header, but not the last byte of the protocol
894      * (that comes from the decompressed data).
895      */
896     wptr[0] = adrs;
897     wptr[1] = ctrl;
898     wptr[2] = 0;
899     wptr += PPP_HDRLEN - 1;
900
901     ilen = len;
902     oldcode = CLEAR;
903     explen = 0;
904     while (len > 0) {
905         /*
906          * Accumulate bytes until we have a complete code.
907          * Then get the next code, relying on the 32-bit,
908          * unsigned accm to mask the result.
909          */
910         bitno -= 8;
911         accm |= *rptr++ << bitno;
912         --len;
913         if (tgtbitno < bitno)
914             continue;
915         incode = accm >> tgtbitno;
916         accm <<= n_bits;
917         bitno += n_bits;
918
919         if (incode == CLEAR) {
920             /*
921              * The dictionary must only be cleared at
922              * the end of a packet.  But there could be an
923              * empty mbuf at the end.
924              */
925             if (len > 0) {
926                 NB_FREE(mret);
927                 IOLogDbg("bsd_decomp%d: bad CLEAR\n", db->unit);
928                 return DECOMP_FATALERROR;       /* probably a bug */
929             }
930             bsd_clear(db);
931             explen = ilen = 0;
932             break;
933         }
934
935         if (incode > max_ent + 2 || incode > db->maxmaxcode
936             || incode > max_ent && oldcode == CLEAR) {
937             NB_FREE(mret);
938             IOLogDbg("bsd_decomp%d: bad code 0x%x oldcode=0x%x max_ent=0x%x explen=%d seqno=%d\n",
939                      db->unit, incode, oldcode, max_ent, explen, db->seqno);
940             return DECOMP_FATALERROR;   /* probably a bug */
941         }
942
943         /* Special case for KwKwK string. */
944         if (incode > max_ent) {
945             finchar = oldcode;
946             extra = 1;
947         } else {
948             finchar = incode;
949             extra = 0;
950         }
951
952         codelen = db->lens[finchar];
953         explen += codelen + extra;
954         if (explen > db->mru + 1) {
955             NB_FREE(mret);
956             IOLogDbg("bsd_decomp%d: ran out of mru\n  len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
957                        db->unit, len, finchar, codelen, explen);
958             return DECOMP_FATALERROR;
959         }
960
961         /*
962          * If we have no space left, then we've overflowed...
963          */
964         if ((space -= codelen + extra) < 0) {
965             IOLog("bsd_decompress%d: no space left in netbuf (need %d bytes)\n",
966                   db->unit, (codelen + extra) - space);
967             NB_FREE(mret);
968             return DECOMP_ERROR;
969         }
970
971         /*
972          * Decode this code and install it in the decompressed buffer.
973          */
974         p = (wptr += codelen);
975         while (finchar > LAST) {
976             dictp = &db->dict[db->dict[finchar].cptr];
977 #ifdef DEBUG
978             if (--codelen <= 0 || dictp->codem1 != finchar-1)
979                 goto bad;
980 #endif
981             *--p = dictp->f.hs.suffix;
982             finchar = dictp->f.hs.prefix;
983         }
984         *--p = finchar;
985
986 #ifdef DEBUG
987         if (--codelen != 0)
988             IOLog("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
989                    db->unit, codelen, incode, max_ent);
990 #endif
991
992         if (extra)              /* the KwKwK case again */
993             *wptr++ = finchar;
994
995         /*
996          * If not first code in a packet, and
997          * if not out of code space, then allocate a new code.
998          *
999          * Keep the hash table correct so it can be used
1000          * with uncompressed packets.
1001          */
1002         if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
1003             struct bsd_dict *dictp2;
1004             u_int32_t fcode;
1005             u_int32_t hval, disp;
1006
1007             fcode = BSD_KEY(oldcode,finchar);
1008             hval = BSD_HASH(oldcode,finchar,db->hshift);
1009             dictp = &db->dict[hval];
1010
1011             /* look for a free hash table entry */
1012             if (dictp->codem1 < max_ent) {
1013                 disp = (hval == 0) ? 1 : hval;
1014                 do {
1015                     hval += disp;
1016                     if (hval >= db->hsize)
1017                         hval -= db->hsize;
1018                     dictp = &db->dict[hval];
1019                 } while (dictp->codem1 < max_ent);
1020             }
1021
1022             /*
1023              * Invalidate previous hash table entry
1024              * assigned this code, and then take it over
1025              */
1026             dictp2 = &db->dict[max_ent+1];
1027             if (db->dict[dictp2->cptr].codem1 == max_ent) {
1028                 db->dict[dictp2->cptr].codem1 = BADCODEM1;
1029             }
1030             dictp2->cptr = hval;
1031             dictp->codem1 = max_ent;
1032             dictp->f.fcode = fcode;
1033
1034             db->max_ent = ++max_ent;
1035             db->lens[max_ent] = db->lens[oldcode]+1;
1036
1037             /* Expand code size if needed. */
1038             if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
1039                 db->n_bits = ++n_bits;
1040                 tgtbitno = 32-n_bits;
1041             }
1042         }
1043         oldcode = incode;
1044     }
1045     NB_SHRINK_BOT(dmp, NB_SIZE(dmp) - (wptr - mtod(dmp, u_char *)));
1046
1047     /*
1048      * Keep the checkpoint right so that incompressible packets
1049      * clear the dictionary at the right times.
1050      */
1051     db->bytes_out += ilen;
1052     db->in_count += explen;
1053     if (bsd_check(db)) {
1054         IOLogDbg("bsd_decomp%d: peer should have cleared dictionary\n",
1055                db->unit);
1056     }
1057
1058     ++db->comp_count;
1059     db->comp_bytes += ilen + BSD_OVHD;
1060     ++db->uncomp_count;
1061     db->uncomp_bytes += explen;
1062
1063     *dmpp = mret;
1064     return DECOMP_OK;
1065
1066 #ifdef DEBUG
1067  bad:
1068     if (codelen <= 0) {
1069         IOLog("bsd_decomp%d: fell off end of chain 0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
1070               db->unit, incode, finchar, db->dict[finchar].cptr, max_ent);
1071     } else if (dictp->codem1 != finchar-1) {
1072         IOLog("bsd_decomp%d: bad code chain 0x%x finchar=0x%x oldcode=0x%x cptr=0x%x codem1=0x%x\n",
1073               db->unit, incode, finchar, oldcode, db->dict[finchar].cptr,
1074               dictp->codem1);
1075     }
1076     NB_FREE(mret);
1077     return DECOMP_FATALERROR;
1078 #endif /* DEBUG */
1079 }
1080 #endif /* DO_BSD_COMPRESS */