File: /usr/src/linux/drivers/net/bsd_comp.c
1 /*
2 * Update: The Berkeley copyright was changed, and the change
3 * is retroactive to all "true" BSD software (ie everything
4 * from UCB as opposed to other peoples code that just carried
5 * the same license). The new copyright doesn't clash with the
6 * GPL, so the module-only restriction has been removed..
7 */
8
9 /* Because this code is derived from the 4.3BSD compress source:
10 *
11 * Copyright (c) 1985, 1986 The Regents of the University of California.
12 * All rights reserved.
13 *
14 * This code is derived from software contributed to Berkeley by
15 * James A. Woods, derived from original work by Spencer Thomas
16 * and Joseph Orost.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
20 * are met:
21 * 1. Redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer.
23 * 2. Redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution.
26 * 3. All advertising materials mentioning features or use of this software
27 * must display the following acknowledgement:
28 * This product includes software developed by the University of
29 * California, Berkeley and its contributors.
30 * 4. Neither the name of the University nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
33 *
34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44 * SUCH DAMAGE.
45 */
46
47 /*
48 * This version is for use with contiguous buffers on Linux-derived systems.
49 *
50 * ==FILEVERSION 20000226==
51 *
52 * NOTE TO MAINTAINERS:
53 * If you modify this file at all, please set the number above to the
54 * date of the modification as YYMMDD (year month day).
55 * bsd_comp.c is shipped with a PPP distribution as well as with
56 * the kernel; if everyone increases the FILEVERSION number above,
57 * then scripts can do the right thing when deciding whether to
58 * install a new bsd_comp.c file. Don't change the format of that
59 * line otherwise, so the installation script can recognize it.
60 *
61 * From: bsd_comp.c,v 1.3 1994/12/08 01:59:58 paulus Exp
62 */
63
64 #include <linux/module.h>
65 #include <linux/init.h>
66 #include <linux/slab.h>
67 #include <linux/vmalloc.h>
68
69 #include <linux/ppp_defs.h>
70
71 #undef PACKETPTR
72 #define PACKETPTR 1
73 #include <linux/ppp-comp.h>
74 #undef PACKETPTR
75
76 /*
77 * PPP "BSD compress" compression
78 * The differences between this compression and the classic BSD LZW
79 * source are obvious from the requirement that the classic code worked
80 * with files while this handles arbitrarily long streams that
81 * are broken into packets. They are:
82 *
83 * When the code size expands, a block of junk is not emitted by
84 * the compressor and not expected by the decompressor.
85 *
86 * New codes are not necessarily assigned every time an old
87 * code is output by the compressor. This is because a packet
88 * end forces a code to be emitted, but does not imply that a
89 * new sequence has been seen.
90 *
91 * The compression ratio is checked at the first end of a packet
92 * after the appropriate gap. Besides simplifying and speeding
93 * things up, this makes it more likely that the transmitter
94 * and receiver will agree when the dictionary is cleared when
95 * compression is not going well.
96 */
97
98 /*
99 * Macros to extract protocol version and number of bits
100 * from the third byte of the BSD Compress CCP configuration option.
101 */
102
103 #define BSD_VERSION(x) ((x) >> 5)
104 #define BSD_NBITS(x) ((x) & 0x1F)
105
106 #define BSD_CURRENT_VERSION 1
107
108 /*
109 * A dictionary for doing BSD compress.
110 */
111
112 struct bsd_dict {
113 union { /* hash value */
114 unsigned long fcode;
115 struct {
116 #if defined(__LITTLE_ENDIAN) /* Little endian order */
117 unsigned short prefix; /* preceding code */
118 unsigned char suffix; /* last character of new code */
119 unsigned char pad;
120 #elif defined(__BIG_ENDIAN) /* Big endian order */
121 unsigned char pad;
122 unsigned char suffix; /* last character of new code */
123 unsigned short prefix; /* preceding code */
124 #else
125 #error Endianness not defined...
126 #endif
127 } hs;
128 } f;
129 unsigned short codem1; /* output of hash table -1 */
130 unsigned short cptr; /* map code to hash table entry */
131 };
132
133 struct bsd_db {
134 int totlen; /* length of this structure */
135 unsigned int hsize; /* size of the hash table */
136 unsigned char hshift; /* used in hash function */
137 unsigned char n_bits; /* current bits/code */
138 unsigned char maxbits; /* maximum bits/code */
139 unsigned char debug; /* non-zero if debug desired */
140 unsigned char unit; /* ppp unit number */
141 unsigned short seqno; /* sequence # of next packet */
142 unsigned int mru; /* size of receive (decompress) bufr */
143 unsigned int maxmaxcode; /* largest valid code */
144 unsigned int max_ent; /* largest code in use */
145 unsigned int in_count; /* uncompressed bytes, aged */
146 unsigned int bytes_out; /* compressed bytes, aged */
147 unsigned int ratio; /* recent compression ratio */
148 unsigned int checkpoint; /* when to next check the ratio */
149 unsigned int clear_count; /* times dictionary cleared */
150 unsigned int incomp_count; /* incompressible packets */
151 unsigned int incomp_bytes; /* incompressible bytes */
152 unsigned int uncomp_count; /* uncompressed packets */
153 unsigned int uncomp_bytes; /* uncompressed bytes */
154 unsigned int comp_count; /* compressed packets */
155 unsigned int comp_bytes; /* compressed bytes */
156 unsigned short *lens; /* array of lengths of codes */
157 struct bsd_dict *dict; /* dictionary */
158 };
159
160 #define BSD_OVHD 2 /* BSD compress overhead/packet */
161 #define MIN_BSD_BITS 9
162 #define BSD_INIT_BITS MIN_BSD_BITS
163 #define MAX_BSD_BITS 15
164
165 static void bsd_free (void *state);
166 static void *bsd_alloc(unsigned char *options, int opt_len, int decomp);
167 static void *bsd_comp_alloc (unsigned char *options, int opt_len);
168 static void *bsd_decomp_alloc (unsigned char *options, int opt_len);
169
170 static int bsd_init (void *db, unsigned char *options,
171 int opt_len, int unit, int debug, int decomp);
172 static int bsd_comp_init (void *state, unsigned char *options,
173 int opt_len, int unit, int opthdr, int debug);
174 static int bsd_decomp_init (void *state, unsigned char *options,
175 int opt_len, int unit, int opthdr, int mru,
176 int debug);
177
178 static void bsd_reset (void *state);
179 static void bsd_comp_stats (void *state, struct compstat *stats);
180
181 static int bsd_compress (void *state, unsigned char *rptr,
182 unsigned char *obuf, int isize, int osize);
183 static void bsd_incomp (void *state, unsigned char *ibuf, int icnt);
184
185 static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
186 unsigned char *obuf, int osize);
187
188 /* These are in ppp_generic.c */
189 extern int ppp_register_compressor (struct compressor *cp);
190 extern void ppp_unregister_compressor (struct compressor *cp);
191
192 /*
193 * the next two codes should not be changed lightly, as they must not
194 * lie within the contiguous general code space.
195 */
196 #define CLEAR 256 /* table clear output code */
197 #define FIRST 257 /* first free entry */
198 #define LAST 255
199
200 #define MAXCODE(b) ((1 << (b)) - 1)
201 #define BADCODEM1 MAXCODE(MAX_BSD_BITS);
202
203 #define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) \
204 ^ (unsigned long)(prefix))
205 #define BSD_KEY(prefix,suffix) ((((unsigned long)(suffix)) << 16) \
206 + (unsigned long)(prefix))
207
208 #define CHECK_GAP 10000 /* Ratio check interval */
209
210 #define RATIO_SCALE_LOG 8
211 #define RATIO_SCALE (1<<RATIO_SCALE_LOG)
212 #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)
213
214 /*
215 * clear the dictionary
216 */
217
218 static void
219 bsd_clear(struct bsd_db *db)
220 {
221 db->clear_count++;
222 db->max_ent = FIRST-1;
223 db->n_bits = BSD_INIT_BITS;
224 db->bytes_out = 0;
225 db->in_count = 0;
226 db->ratio = 0;
227 db->checkpoint = CHECK_GAP;
228 }
229
230 /*
231 * If the dictionary is full, then see if it is time to reset it.
232 *
233 * Compute the compression ratio using fixed-point arithmetic
234 * with 8 fractional bits.
235 *
236 * Since we have an infinite stream instead of a single file,
237 * watch only the local compression ratio.
238 *
239 * Since both peers must reset the dictionary at the same time even in
240 * the absence of CLEAR codes (while packets are incompressible), they
241 * must compute the same ratio.
242 */
243
244 static int bsd_check (struct bsd_db *db) /* 1=output CLEAR */
245 {
246 unsigned int new_ratio;
247
248 if (db->in_count >= db->checkpoint)
249 {
250 /* age the ratio by limiting the size of the counts */
251 if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)
252 {
253 db->in_count -= (db->in_count >> 2);
254 db->bytes_out -= (db->bytes_out >> 2);
255 }
256
257 db->checkpoint = db->in_count + CHECK_GAP;
258
259 if (db->max_ent >= db->maxmaxcode)
260 {
261 /* Reset the dictionary only if the ratio is worse,
262 * or if it looks as if it has been poisoned
263 * by incompressible data.
264 *
265 * This does not overflow, because
266 * db->in_count <= RATIO_MAX.
267 */
268
269 new_ratio = db->in_count << RATIO_SCALE_LOG;
270 if (db->bytes_out != 0)
271 {
272 new_ratio /= db->bytes_out;
273 }
274
275 if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
276 {
277 bsd_clear (db);
278 return 1;
279 }
280 db->ratio = new_ratio;
281 }
282 }
283 return 0;
284 }
285
286 /*
287 * Return statistics.
288 */
289
290 static void bsd_comp_stats (void *state, struct compstat *stats)
291 {
292 struct bsd_db *db = (struct bsd_db *) state;
293
294 stats->unc_bytes = db->uncomp_bytes;
295 stats->unc_packets = db->uncomp_count;
296 stats->comp_bytes = db->comp_bytes;
297 stats->comp_packets = db->comp_count;
298 stats->inc_bytes = db->incomp_bytes;
299 stats->inc_packets = db->incomp_count;
300 stats->in_count = db->in_count;
301 stats->bytes_out = db->bytes_out;
302 }
303
304 /*
305 * Reset state, as on a CCP ResetReq.
306 */
307
308 static void bsd_reset (void *state)
309 {
310 struct bsd_db *db = (struct bsd_db *) state;
311
312 bsd_clear(db);
313
314 db->seqno = 0;
315 db->clear_count = 0;
316 }
317
318 /*
319 * Release the compression structure
320 */
321
322 static void bsd_free (void *state)
323 {
324 struct bsd_db *db = (struct bsd_db *) state;
325
326 if (db)
327 {
328 /*
329 * Release the dictionary
330 */
331 if (db->dict)
332 {
333 vfree (db->dict);
334 db->dict = NULL;
335 }
336 /*
337 * Release the string buffer
338 */
339 if (db->lens)
340 {
341 vfree (db->lens);
342 db->lens = NULL;
343 }
344 /*
345 * Finally release the structure itself.
346 */
347 kfree (db);
348 MOD_DEC_USE_COUNT;
349 }
350 }
351
352 /*
353 * Allocate space for a (de) compressor.
354 */
355
356 static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)
357 {
358 int bits;
359 unsigned int hsize, hshift, maxmaxcode;
360 struct bsd_db *db;
361
362 if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3
363 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
364 {
365 return NULL;
366 }
367
368 bits = BSD_NBITS(options[2]);
369
370 switch (bits)
371 {
372 case 9: /* needs 82152 for both directions */
373 case 10: /* needs 84144 */
374 case 11: /* needs 88240 */
375 case 12: /* needs 96432 */
376 hsize = 5003;
377 hshift = 4;
378 break;
379 case 13: /* needs 176784 */
380 hsize = 9001;
381 hshift = 5;
382 break;
383 case 14: /* needs 353744 */
384 hsize = 18013;
385 hshift = 6;
386 break;
387 case 15: /* needs 691440 */
388 hsize = 35023;
389 hshift = 7;
390 break;
391 case 16: /* needs 1366160--far too much, */
392 /* hsize = 69001; */ /* and 69001 is too big for cptr */
393 /* hshift = 8; */ /* in struct bsd_db */
394 /* break; */
395 default:
396 return NULL;
397 }
398 /*
399 * Allocate the main control structure for this instance.
400 */
401 maxmaxcode = MAXCODE(bits);
402 db = (struct bsd_db *) kmalloc (sizeof (struct bsd_db),
403 GFP_KERNEL);
404 if (!db)
405 {
406 return NULL;
407 }
408
409 memset (db, 0, sizeof(struct bsd_db));
410 /*
411 * Allocate space for the dictionary. This may be more than one page in
412 * length.
413 */
414 db->dict = (struct bsd_dict *) vmalloc (hsize *
415 sizeof (struct bsd_dict));
416 if (!db->dict)
417 {
418 bsd_free (db);
419 return NULL;
420 }
421
422 MOD_INC_USE_COUNT;
423 /*
424 * If this is the compression buffer then there is no length data.
425 */
426 if (!decomp)
427 {
428 db->lens = NULL;
429 }
430 /*
431 * For decompression, the length information is needed as well.
432 */
433 else
434 {
435 db->lens = (unsigned short *) vmalloc ((maxmaxcode + 1) *
436 sizeof (db->lens[0]));
437 if (!db->lens)
438 {
439 bsd_free (db);
440 return (NULL);
441 }
442 }
443 /*
444 * Initialize the data information for the compression code
445 */
446 db->totlen = sizeof (struct bsd_db) +
447 (sizeof (struct bsd_dict) * hsize);
448
449 db->hsize = hsize;
450 db->hshift = hshift;
451 db->maxmaxcode = maxmaxcode;
452 db->maxbits = bits;
453
454 return (void *) db;
455 }
456
457 static void *bsd_comp_alloc (unsigned char *options, int opt_len)
458 {
459 return bsd_alloc (options, opt_len, 0);
460 }
461
462 static void *bsd_decomp_alloc (unsigned char *options, int opt_len)
463 {
464 return bsd_alloc (options, opt_len, 1);
465 }
466
467 /*
468 * Initialize the database.
469 */
470
471 static int bsd_init (void *state, unsigned char *options,
472 int opt_len, int unit, int debug, int decomp)
473 {
474 struct bsd_db *db = state;
475 int indx;
476
477 if ((opt_len != 3) || (options[0] != CI_BSD_COMPRESS) || (options[1] != 3)
478 || (BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
479 || (BSD_NBITS(options[2]) != db->maxbits)
480 || (decomp && db->lens == NULL))
481 {
482 return 0;
483 }
484
485 if (decomp)
486 {
487 indx = LAST;
488 do
489 {
490 db->lens[indx] = 1;
491 }
492 while (indx-- > 0);
493 }
494
495 indx = db->hsize;
496 while (indx-- != 0)
497 {
498 db->dict[indx].codem1 = BADCODEM1;
499 db->dict[indx].cptr = 0;
500 }
501
502 db->unit = unit;
503 db->mru = 0;
504 #ifndef DEBUG
505 if (debug)
506 #endif
507 db->debug = 1;
508
509 bsd_reset(db);
510
511 return 1;
512 }
513
514 static int bsd_comp_init (void *state, unsigned char *options,
515 int opt_len, int unit, int opthdr, int debug)
516 {
517 return bsd_init (state, options, opt_len, unit, debug, 0);
518 }
519
520 static int bsd_decomp_init (void *state, unsigned char *options,
521 int opt_len, int unit, int opthdr, int mru,
522 int debug)
523 {
524 return bsd_init (state, options, opt_len, unit, debug, 1);
525 }
526
527 /*
528 * Obtain pointers to the various structures in the compression tables
529 */
530
531 #define dict_ptrx(p,idx) &(p->dict[idx])
532 #define lens_ptrx(p,idx) &(p->lens[idx])
533
534 #ifdef DEBUG
535 static unsigned short *lens_ptr(struct bsd_db *db, int idx)
536 {
537 if ((unsigned int) idx > (unsigned int) db->maxmaxcode)
538 {
539 printk ("<9>ppp: lens_ptr(%d) > max\n", idx);
540 idx = 0;
541 }
542 return lens_ptrx (db, idx);
543 }
544
545 static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
546 {
547 if ((unsigned int) idx >= (unsigned int) db->hsize)
548 {
549 printk ("<9>ppp: dict_ptr(%d) > max\n", idx);
550 idx = 0;
551 }
552 return dict_ptrx (db, idx);
553 }
554
555 #else
556 #define lens_ptr(db,idx) lens_ptrx(db,idx)
557 #define dict_ptr(db,idx) dict_ptrx(db,idx)
558 #endif
559
560 /*
561 * compress a packet
562 *
563 * The result of this function is the size of the compressed
564 * packet. A zero is returned if the packet was not compressed
565 * for some reason, such as the size being larger than uncompressed.
566 *
567 * One change from the BSD compress command is that when the
568 * code size expands, we do not output a bunch of padding.
569 */
570
571 static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,
572 int isize, int osize)
573 {
574 struct bsd_db *db;
575 int hshift;
576 unsigned int max_ent;
577 unsigned int n_bits;
578 unsigned int bitno;
579 unsigned long accm;
580 int ent;
581 unsigned long fcode;
582 struct bsd_dict *dictp;
583 unsigned char c;
584 int hval;
585 int disp;
586 int ilen;
587 int mxcode;
588 unsigned char *wptr;
589 int olen;
590
591 #define PUTBYTE(v) \
592 { \
593 ++olen; \
594 if (wptr) \
595 { \
596 *wptr++ = (unsigned char) (v); \
597 if (olen >= osize) \
598 { \
599 wptr = NULL; \
600 } \
601 } \
602 }
603
604 #define OUTPUT(ent) \
605 { \
606 bitno -= n_bits; \
607 accm |= ((ent) << bitno); \
608 do \
609 { \
610 PUTBYTE(accm >> 24); \
611 accm <<= 8; \
612 bitno += 8; \
613 } \
614 while (bitno <= 24); \
615 }
616
617 /*
618 * If the protocol is not in the range we're interested in,
619 * just return without compressing the packet. If it is,
620 * the protocol becomes the first byte to compress.
621 */
622
623 ent = PPP_PROTOCOL(rptr);
624 if (ent < 0x21 || ent > 0xf9)
625 {
626 return 0;
627 }
628
629 db = (struct bsd_db *) state;
630 hshift = db->hshift;
631 max_ent = db->max_ent;
632 n_bits = db->n_bits;
633 bitno = 32;
634 accm = 0;
635 mxcode = MAXCODE (n_bits);
636
637 /* Initialize the output pointers */
638 wptr = obuf;
639 olen = PPP_HDRLEN + BSD_OVHD;
640
641 if (osize > isize)
642 {
643 osize = isize;
644 }
645
646 /* This is the PPP header information */
647 if (wptr)
648 {
649 *wptr++ = PPP_ADDRESS(rptr);
650 *wptr++ = PPP_CONTROL(rptr);
651 *wptr++ = 0;
652 *wptr++ = PPP_COMP;
653 *wptr++ = db->seqno >> 8;
654 *wptr++ = db->seqno;
655 }
656
657 /* Skip the input header */
658 rptr += PPP_HDRLEN;
659 isize -= PPP_HDRLEN;
660 ilen = ++isize; /* Low byte of protocol is counted as input */
661
662 while (--ilen > 0)
663 {
664 c = *rptr++;
665 fcode = BSD_KEY (ent, c);
666 hval = BSD_HASH (ent, c, hshift);
667 dictp = dict_ptr (db, hval);
668
669 /* Validate and then check the entry. */
670 if (dictp->codem1 >= max_ent)
671 {
672 goto nomatch;
673 }
674
675 if (dictp->f.fcode == fcode)
676 {
677 ent = dictp->codem1 + 1;
678 continue; /* found (prefix,suffix) */
679 }
680
681 /* continue probing until a match or invalid entry */
682 disp = (hval == 0) ? 1 : hval;
683
684 do
685 {
686 hval += disp;
687 if (hval >= db->hsize)
688 {
689 hval -= db->hsize;
690 }
691 dictp = dict_ptr (db, hval);
692 if (dictp->codem1 >= max_ent)
693 {
694 goto nomatch;
695 }
696 }
697 while (dictp->f.fcode != fcode);
698
699 ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */
700 continue;
701
702 nomatch:
703 OUTPUT(ent); /* output the prefix */
704
705 /* code -> hashtable */
706 if (max_ent < db->maxmaxcode)
707 {
708 struct bsd_dict *dictp2;
709 struct bsd_dict *dictp3;
710 int indx;
711
712 /* expand code size if needed */
713 if (max_ent >= mxcode)
714 {
715 db->n_bits = ++n_bits;
716 mxcode = MAXCODE (n_bits);
717 }
718
719 /* Invalidate old hash table entry using
720 * this code, and then take it over.
721 */
722
723 dictp2 = dict_ptr (db, max_ent + 1);
724 indx = dictp2->cptr;
725 dictp3 = dict_ptr (db, indx);
726
727 if (dictp3->codem1 == max_ent)
728 {
729 dictp3->codem1 = BADCODEM1;
730 }
731
732 dictp2->cptr = hval;
733 dictp->codem1 = max_ent;
734 dictp->f.fcode = fcode;
735 db->max_ent = ++max_ent;
736
737 if (db->lens)
738 {
739 unsigned short *len1 = lens_ptr (db, max_ent);
740 unsigned short *len2 = lens_ptr (db, ent);
741 *len1 = *len2 + 1;
742 }
743 }
744 ent = c;
745 }
746
747 OUTPUT(ent); /* output the last code */
748
749 db->bytes_out += olen - PPP_HDRLEN - BSD_OVHD;
750 db->uncomp_bytes += isize;
751 db->in_count += isize;
752 ++db->uncomp_count;
753 ++db->seqno;
754
755 if (bitno < 32)
756 {
757 ++db->bytes_out; /* must be set before calling bsd_check */
758 }
759
760 /*
761 * Generate the clear command if needed
762 */
763
764 if (bsd_check(db))
765 {
766 OUTPUT (CLEAR);
767 }
768
769 /*
770 * Pad dribble bits of last code with ones.
771 * Do not emit a completely useless byte of ones.
772 */
773
774 if (bitno != 32)
775 {
776 PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
777 }
778
779 /*
780 * Increase code size if we would have without the packet
781 * boundary because the decompressor will do so.
782 */
783
784 if (max_ent >= mxcode && max_ent < db->maxmaxcode)
785 {
786 db->n_bits++;
787 }
788
789 /* If output length is too large then this is an incomplete frame. */
790 if (wptr == NULL)
791 {
792 ++db->incomp_count;
793 db->incomp_bytes += isize;
794 olen = 0;
795 }
796 else /* Count the number of compressed frames */
797 {
798 ++db->comp_count;
799 db->comp_bytes += olen;
800 }
801
802 /* Return the resulting output length */
803 return olen;
804 #undef OUTPUT
805 #undef PUTBYTE
806 }
807
808 /*
809 * Update the "BSD Compress" dictionary on the receiver for
810 * incompressible data by pretending to compress the incoming data.
811 */
812
813 static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)
814 {
815 (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);
816 }
817
818 /*
819 * Decompress "BSD Compress".
820 *
821 * Because of patent problems, we return DECOMP_ERROR for errors
822 * found by inspecting the input data and for system problems, but
823 * DECOMP_FATALERROR for any errors which could possibly be said to
824 * be being detected "after" decompression. For DECOMP_ERROR,
825 * we can issue a CCP reset-request; for DECOMP_FATALERROR, we may be
826 * infringing a patent of Motorola's if we do, so we take CCP down
827 * instead.
828 *
829 * Given that the frame has the correct sequence number and a good FCS,
830 * errors such as invalid codes in the input most likely indicate a
831 * bug, so we return DECOMP_FATALERROR for them in order to turn off
832 * compression, even though they are detected by inspecting the input.
833 */
834
835 static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
836 unsigned char *obuf, int osize)
837 {
838 struct bsd_db *db;
839 unsigned int max_ent;
840 unsigned long accm;
841 unsigned int bitno; /* 1st valid bit in accm */
842 unsigned int n_bits;
843 unsigned int tgtbitno; /* bitno when we have a code */
844 struct bsd_dict *dictp;
845 int explen;
846 int seq;
847 unsigned int incode;
848 unsigned int oldcode;
849 unsigned int finchar;
850 unsigned char *p;
851 unsigned char *wptr;
852 int adrs;
853 int ctrl;
854 int ilen;
855 int codelen;
856 int extra;
857
858 db = (struct bsd_db *) state;
859 max_ent = db->max_ent;
860 accm = 0;
861 bitno = 32; /* 1st valid bit in accm */
862 n_bits = db->n_bits;
863 tgtbitno = 32 - n_bits; /* bitno when we have a code */
864
865 /*
866 * Save the address/control from the PPP header
867 * and then get the sequence number.
868 */
869
870 adrs = PPP_ADDRESS (ibuf);
871 ctrl = PPP_CONTROL (ibuf);
872
873 seq = (ibuf[4] << 8) + ibuf[5];
874
875 ibuf += (PPP_HDRLEN + 2);
876 ilen = isize - (PPP_HDRLEN + 2);
877
878 /*
879 * Check the sequence number and give up if it differs from
880 * the value we're expecting.
881 */
882
883 if (seq != db->seqno)
884 {
885 if (db->debug)
886 {
887 printk("bsd_decomp%d: bad sequence # %d, expected %d\n",
888 db->unit, seq, db->seqno - 1);
889 }
890 return DECOMP_ERROR;
891 }
892
893 ++db->seqno;
894 db->bytes_out += ilen;
895
896 /*
897 * Fill in the ppp header, but not the last byte of the protocol
898 * (that comes from the decompressed data).
899 */
900
901 wptr = obuf;
902 *wptr++ = adrs;
903 *wptr++ = ctrl;
904 *wptr++ = 0;
905
906 oldcode = CLEAR;
907 explen = 3;
908
909 /*
910 * Keep the checkpoint correctly so that incompressible packets
911 * clear the dictionary at the proper times.
912 */
913
914 for (;;)
915 {
916 if (ilen-- <= 0)
917 {
918 db->in_count += (explen - 3); /* don't count the header */
919 break;
920 }
921
922 /*
923 * Accumulate bytes until we have a complete code.
924 * Then get the next code, relying on the 32-bit,
925 * unsigned accm to mask the result.
926 */
927
928 bitno -= 8;
929 accm |= *ibuf++ << bitno;
930 if (tgtbitno < bitno)
931 {
932 continue;
933 }
934
935 incode = accm >> tgtbitno;
936 accm <<= n_bits;
937 bitno += n_bits;
938
939 /*
940 * The dictionary must only be cleared at the end of a packet.
941 */
942
943 if (incode == CLEAR)
944 {
945 if (ilen > 0)
946 {
947 if (db->debug)
948 {
949 printk("bsd_decomp%d: bad CLEAR\n", db->unit);
950 }
951 return DECOMP_FATALERROR; /* probably a bug */
952 }
953
954 bsd_clear(db);
955 break;
956 }
957
958 if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
959 || (incode > max_ent && oldcode == CLEAR))
960 {
961 if (db->debug)
962 {
963 printk("bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
964 db->unit, incode, oldcode);
965 printk("max_ent=0x%x explen=%d seqno=%d\n",
966 max_ent, explen, db->seqno);
967 }
968 return DECOMP_FATALERROR; /* probably a bug */
969 }
970
971 /* Special case for KwKwK string. */
972 if (incode > max_ent)
973 {
974 finchar = oldcode;
975 extra = 1;
976 }
977 else
978 {
979 finchar = incode;
980 extra = 0;
981 }
982
983 codelen = *(lens_ptr (db, finchar));
984 explen += codelen + extra;
985 if (explen > osize)
986 {
987 if (db->debug)
988 {
989 printk("bsd_decomp%d: ran out of mru\n", db->unit);
990 #ifdef DEBUG
991 printk(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
992 ilen, finchar, codelen, explen);
993 #endif
994 }
995 return DECOMP_FATALERROR;
996 }
997
998 /*
999 * Decode this code and install it in the decompressed buffer.
1000 */
1001
1002 wptr += codelen;
1003 p = wptr;
1004 while (finchar > LAST)
1005 {
1006 struct bsd_dict *dictp2 = dict_ptr (db, finchar);
1007
1008 dictp = dict_ptr (db, dictp2->cptr);
1009 #ifdef DEBUG
1010 if (--codelen <= 0 || dictp->codem1 != finchar-1)
1011 {
1012 if (codelen <= 0)
1013 {
1014 printk("bsd_decomp%d: fell off end of chain ", db->unit);
1015 printk("0x%x at 0x%x by 0x%x, max_ent=0x%x\n",
1016 incode, finchar, dictp2->cptr, max_ent);
1017 }
1018 else
1019 {
1020 if (dictp->codem1 != finchar-1)
1021 {
1022 printk("bsd_decomp%d: bad code chain 0x%x "
1023 "finchar=0x%x ",
1024 db->unit, incode, finchar);
1025
1026 printk("oldcode=0x%x cptr=0x%x codem1=0x%x\n",
1027 oldcode, dictp2->cptr, dictp->codem1);
1028 }
1029 }
1030 return DECOMP_FATALERROR;
1031 }
1032 #endif
1033 *--p = dictp->f.hs.suffix;
1034 finchar = dictp->f.hs.prefix;
1035 }
1036 *--p = finchar;
1037
1038 #ifdef DEBUG
1039 if (--codelen != 0)
1040 {
1041 printk("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
1042 db->unit, codelen, incode, max_ent);
1043 }
1044 #endif
1045
1046 if (extra) /* the KwKwK case again */
1047 {
1048 *wptr++ = finchar;
1049 }
1050
1051 /*
1052 * If not first code in a packet, and
1053 * if not out of code space, then allocate a new code.
1054 *
1055 * Keep the hash table correct so it can be used
1056 * with uncompressed packets.
1057 */
1058
1059 if (oldcode != CLEAR && max_ent < db->maxmaxcode)
1060 {
1061 struct bsd_dict *dictp2, *dictp3;
1062 unsigned short *lens1, *lens2;
1063 unsigned long fcode;
1064 int hval, disp, indx;
1065
1066 fcode = BSD_KEY(oldcode,finchar);
1067 hval = BSD_HASH(oldcode,finchar,db->hshift);
1068 dictp = dict_ptr (db, hval);
1069
1070 /* look for a free hash table entry */
1071 if (dictp->codem1 < max_ent)
1072 {
1073 disp = (hval == 0) ? 1 : hval;
1074 do
1075 {
1076 hval += disp;
1077 if (hval >= db->hsize)
1078 {
1079 hval -= db->hsize;
1080 }
1081 dictp = dict_ptr (db, hval);
1082 }
1083 while (dictp->codem1 < max_ent);
1084 }
1085
1086 /*
1087 * Invalidate previous hash table entry
1088 * assigned this code, and then take it over
1089 */
1090
1091 dictp2 = dict_ptr (db, max_ent + 1);
1092 indx = dictp2->cptr;
1093 dictp3 = dict_ptr (db, indx);
1094
1095 if (dictp3->codem1 == max_ent)
1096 {
1097 dictp3->codem1 = BADCODEM1;
1098 }
1099
1100 dictp2->cptr = hval;
1101 dictp->codem1 = max_ent;
1102 dictp->f.fcode = fcode;
1103 db->max_ent = ++max_ent;
1104
1105 /* Update the length of this string. */
1106 lens1 = lens_ptr (db, max_ent);
1107 lens2 = lens_ptr (db, oldcode);
1108 *lens1 = *lens2 + 1;
1109
1110 /* Expand code size if needed. */
1111 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
1112 {
1113 db->n_bits = ++n_bits;
1114 tgtbitno = 32-n_bits;
1115 }
1116 }
1117 oldcode = incode;
1118 }
1119
1120 ++db->comp_count;
1121 ++db->uncomp_count;
1122 db->comp_bytes += isize - BSD_OVHD - PPP_HDRLEN;
1123 db->uncomp_bytes += explen;
1124
1125 if (bsd_check(db))
1126 {
1127 if (db->debug)
1128 {
1129 printk("bsd_decomp%d: peer should have cleared dictionary on %d\n",
1130 db->unit, db->seqno - 1);
1131 }
1132 }
1133 return explen;
1134 }
1135
1136 /*************************************************************
1137 * Table of addresses for the BSD compression module
1138 *************************************************************/
1139
1140 static struct compressor ppp_bsd_compress = {
1141 CI_BSD_COMPRESS, /* compress_proto */
1142 bsd_comp_alloc, /* comp_alloc */
1143 bsd_free, /* comp_free */
1144 bsd_comp_init, /* comp_init */
1145 bsd_reset, /* comp_reset */
1146 bsd_compress, /* compress */
1147 bsd_comp_stats, /* comp_stat */
1148 bsd_decomp_alloc, /* decomp_alloc */
1149 bsd_free, /* decomp_free */
1150 bsd_decomp_init, /* decomp_init */
1151 bsd_reset, /* decomp_reset */
1152 bsd_decompress, /* decompress */
1153 bsd_incomp, /* incomp */
1154 bsd_comp_stats /* decomp_stat */
1155 };
1156
1157 /*************************************************************
1158 * Module support routines
1159 *************************************************************/
1160
1161 int __init bsdcomp_init(void)
1162 {
1163 int answer = ppp_register_compressor(&ppp_bsd_compress);
1164 if (answer == 0)
1165 printk(KERN_INFO "PPP BSD Compression module registered\n");
1166 return answer;
1167 }
1168
1169 void __exit bsdcomp_cleanup(void)
1170 {
1171 ppp_unregister_compressor(&ppp_bsd_compress);
1172 }
1173
1174 module_init(bsdcomp_init);
1175 module_exit(bsdcomp_cleanup);
1176