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