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