1 /* Because this code is derived from the 4.3BSD compress source:
3 * Copyright (c) 1985, 1986 The Regents of the University of California.
6 * This code is derived from software contributed to Berkeley by
7 * James A. Woods, derived from original work by Spencer Thomas
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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
40 * This version is for use with contigious buffers on Linux-derived systems.
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.
52 * $Id: bsd_comp.c,v 1.2 1995/12/18 03:37:05 paulus Exp $
56 #error This file must be compiled as a module.
59 #include <linux/module.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>
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 */
77 #include <asm/system.h>
78 #include <asm/bitops.h>
79 #include <asm/segment.h>
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>
89 #include <linux/ppp_defs.h>
92 #include <linux/netprotocol.h>
95 #include <netinet/ip.h>
96 #include <netinet/tcp.h>
97 #include <net/if_arp.h>
101 #include <linux/ppp-comp.h>
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:
111 * When the code size expands, a block of junk is not emitted by
112 * the compressor and not expected by the decompressor.
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.
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.
127 * Macros to extract protocol version and number of bits
128 * from the third byte of the BSD Compress CCP configuration option.
131 #define BSD_VERSION(x) ((x) >> 5)
132 #define BSD_NBITS(x) ((x) & 0x1F)
134 #define BSD_CURRENT_VERSION 1
137 * A dictionary for doing BSD compress.
141 union { /* hash value */
144 #ifndef BIG_ENDIAN_BITFIELD /* Little endian order */
145 unsigned short prefix; /* preceding code */
146 unsigned char suffix; /* last character of new code */
148 #else /* Big endian order */
150 unsigned char suffix; /* last character of new code */
151 unsigned short prefix; /* preceding code */
155 unsigned short codem1; /* output of hash table -1 */
156 unsigned short cptr; /* map code to hash table entry */
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 */
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
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);
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,
204 static void bsd_reset (void *state);
205 static void bsd_comp_stats (void *state, struct compstat *stats);
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);
211 static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
212 unsigned char *obuf, int osize);
214 /* These are in ppp.c */
215 extern int ppp_register_compressor (struct compressor *cp);
216 extern void ppp_unregister_compressor (struct compressor *cp);
219 * the next two codes should not be changed lightly, as they must not
220 * lie within the contiguous general code space.
222 #define CLEAR 256 /* table clear output code */
223 #define FIRST 257 /* first free entry */
226 #define MAXCODE(b) ((1 << (b)) - 1)
227 #define BADCODEM1 MAXCODE(MAX_BSD_BITS);
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))
234 #define CHECK_GAP 10000 /* Ratio check interval */
236 #define RATIO_SCALE_LOG 8
237 #define RATIO_SCALE (1<<RATIO_SCALE_LOG)
238 #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)
241 * clear the dictionary
245 bsd_clear(struct bsd_db *db)
248 db->max_ent = FIRST-1;
249 db->n_bits = BSD_INIT_BITS;
252 db->incomp_count = 0;
254 db->checkpoint = CHECK_GAP;
258 * If the dictionary is full, then see if it is time to reset it.
260 * Compute the compression ratio using fixed-point arithmetic
261 * with 8 fractional bits.
263 * Since we have an infinite stream instead of a single file,
264 * watch only the local compression ratio.
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.
271 static int bsd_check (struct bsd_db *db) /* 1=output CLEAR */
273 unsigned int new_ratio;
275 if (db->in_count >= db->checkpoint)
277 /* age the ratio by limiting the size of the counts */
278 if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)
280 db->in_count -= (db->in_count >> 2);
281 db->bytes_out -= (db->bytes_out >> 2);
284 db->checkpoint = db->in_count + CHECK_GAP;
286 if (db->max_ent >= db->maxmaxcode)
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.
292 * This does not overflow, because
293 * db->in_count <= RATIO_MAX.
296 new_ratio = db->in_count << RATIO_SCALE_LOG;
297 if (db->bytes_out != 0)
299 new_ratio /= db->bytes_out;
302 if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
307 db->ratio = new_ratio;
317 static void bsd_comp_stats (void *state, struct compstat *stats)
319 struct bsd_db *db = (struct bsd_db *) state;
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;
332 * Reset state, as on a CCP ResetReq.
335 static void bsd_reset (void *state)
337 struct bsd_db *db = (struct bsd_db *) state;
346 * Release the compression structure
349 static void bsd_free (void *state)
351 struct bsd_db *db = (struct bsd_db *) state;
356 * Release the dictionary
364 * Release the string buffer
372 * Finally release the structure itself.
380 * Allocate space for a (de) compressor.
383 static void *bsd_alloc (unsigned char *options, int opt_len, int decomp)
386 unsigned int hsize, hshift, maxmaxcode;
389 if (opt_len != 3 || options[0] != CI_BSD_COMPRESS || options[1] != 3
390 || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)
395 bits = BSD_NBITS(options[2]);
399 case 9: /* needs 82152 for both directions */
400 case 10: /* needs 84144 */
401 case 11: /* needs 88240 */
402 case 12: /* needs 96432 */
406 case 13: /* needs 176784 */
410 case 14: /* needs 353744 */
414 case 15: /* needs 691440 */
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 */
426 * Allocate the main control structure for this instance.
428 maxmaxcode = MAXCODE(bits);
429 db = (struct bsd_db *) kmalloc (sizeof (struct bsd_db),
436 memset (db, 0, sizeof(struct bsd_db));
438 * Allocate space for the dictionary. This may be more than one page in
441 db->dict = (struct bsd_dict *) vmalloc (hsize *
442 sizeof (struct bsd_dict));
451 * If this is the compression buffer then there is no length data.
458 * For decompression, the length information is needed as well.
462 db->lens = (unsigned short *) vmalloc ((maxmaxcode + 1) *
463 sizeof (db->lens[0]));
471 * Initialize the data information for the compression code
473 db->totlen = sizeof (struct bsd_db) +
474 (sizeof (struct bsd_dict) * hsize);
478 db->maxmaxcode = maxmaxcode;
484 static void *bsd_comp_alloc (unsigned char *options, int opt_len)
486 return bsd_alloc (options, opt_len, 0);
489 static void *bsd_decomp_alloc (unsigned char *options, int opt_len)
491 return bsd_alloc (options, opt_len, 1);
495 * Initialize the database.
498 static int bsd_init (void *state, unsigned char *options,
499 int opt_len, int unit, int debug, int decomp)
501 struct bsd_db *db = state;
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))
525 db->dict[indx].codem1 = BADCODEM1;
526 db->dict[indx].cptr = 0;
541 static int bsd_comp_init (void *state, unsigned char *options,
542 int opt_len, int unit, int opthdr, int debug)
544 return bsd_init (state, options, opt_len, unit, debug, 0);
547 static int bsd_decomp_init (void *state, unsigned char *options,
548 int opt_len, int unit, int opthdr, int mru,
551 return bsd_init (state, options, opt_len, unit, debug, 1);
555 * Obtain pointers to the various structures in the compression tables
558 #define dict_ptrx(p,idx) &(p->dict[idx])
559 #define lens_ptrx(p,idx) &(p->lens[idx])
562 static unsigned short *lens_ptr(struct bsd_db *db, int idx)
564 if ((unsigned int) idx > (unsigned int) db->maxmaxcode)
566 printk ("<9>ppp: lens_ptr(%d) > max\n", idx);
569 return lens_ptrx (db, idx);
572 static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
574 if ((unsigned int) idx >= (unsigned int) db->hsize)
576 printk ("<9>ppp: dict_ptr(%d) > max\n", idx);
579 return dict_ptrx (db, idx);
583 #define lens_ptr(db,idx) lens_ptrx(db,idx)
584 #define dict_ptr(db,idx) dict_ptrx(db,idx)
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.
594 * One change from the BSD compress command is that when the
595 * code size expands, we do not output a bunch of padding.
598 static int bsd_compress (void *state, unsigned char *rptr, unsigned char *obuf,
599 int isize, int osize)
603 unsigned int max_ent;
609 struct bsd_dict *dictp;
623 *wptr++ = (unsigned char) (v); \
631 #define OUTPUT(ent) \
634 accm |= ((ent) << bitno); \
637 PUTBYTE(accm >> 24); \
641 while (bitno <= 24); \
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.
650 ent = PPP_PROTOCOL(rptr);
651 if (ent < 0x21 || ent > 0xf9)
656 db = (struct bsd_db *) state;
658 max_ent = db->max_ent;
662 mxcode = MAXCODE (n_bits);
664 /* Initialize the output pointers */
666 olen = PPP_HDRLEN + BSD_OVHD;
673 /* This is the PPP header information */
676 *wptr++ = PPP_ADDRESS(rptr);
677 *wptr++ = PPP_CONTROL(rptr);
680 *wptr++ = db->seqno >> 8;
684 /* Skip the input header */
687 ilen = ++isize; /* This is off by one, but that is what is in draft! */
692 fcode = BSD_KEY (ent, c);
693 hval = BSD_HASH (ent, c, hshift);
694 dictp = dict_ptr (db, hval);
696 /* Validate and then check the entry. */
697 if (dictp->codem1 >= max_ent)
702 if (dictp->f.fcode == fcode)
704 ent = dictp->codem1 + 1;
705 continue; /* found (prefix,suffix) */
708 /* continue probing until a match or invalid entry */
709 disp = (hval == 0) ? 1 : hval;
714 if (hval >= db->hsize)
718 dictp = dict_ptr (db, hval);
719 if (dictp->codem1 >= max_ent)
724 while (dictp->f.fcode != fcode);
726 ent = dictp->codem1 + 1; /* finally found (prefix,suffix) */
730 OUTPUT(ent); /* output the prefix */
732 /* code -> hashtable */
733 if (max_ent < db->maxmaxcode)
735 struct bsd_dict *dictp2;
736 struct bsd_dict *dictp3;
739 /* expand code size if needed */
740 if (max_ent >= mxcode)
742 db->n_bits = ++n_bits;
743 mxcode = MAXCODE (n_bits);
746 /* Invalidate old hash table entry using
747 * this code, and then take it over.
750 dictp2 = dict_ptr (db, max_ent + 1);
752 dictp3 = dict_ptr (db, indx);
754 if (dictp3->codem1 == max_ent)
756 dictp3->codem1 = BADCODEM1;
760 dictp->codem1 = max_ent;
761 dictp->f.fcode = fcode;
762 db->max_ent = ++max_ent;
766 unsigned short *len1 = lens_ptr (db, max_ent);
767 unsigned short *len2 = lens_ptr (db, ent);
774 OUTPUT(ent); /* output the last code */
776 db->bytes_out += olen; /* Do not count bytes from here */
777 db->uncomp_bytes += isize;
778 db->in_count += isize;
784 ++db->bytes_out; /* must be set before calling bsd_check */
788 * Generate the clear command if needed
797 * Pad dribble bits of last code with ones.
798 * Do not emit a completely useless byte of ones.
803 PUTBYTE((accm | (0xff << (bitno-8))) >> 24);
807 * Increase code size if we would have without the packet
808 * boundary because the decompressor will do so.
811 if (max_ent >= mxcode && max_ent < db->maxmaxcode)
816 /* If output length is too large then this is an incomplete frame. */
820 db->incomp_bytes += isize;
823 else /* Count the number of compressed frames */
826 db->comp_bytes += olen;
829 /* Return the resulting output length */
836 * Update the "BSD Compress" dictionary on the receiver for
837 * incompressible data by pretending to compress the incoming data.
840 static void bsd_incomp (void *state, unsigned char *ibuf, int icnt)
842 (void) bsd_compress (state, ibuf, (char *) 0, icnt, 0);
846 * Decompress "BSD Compress".
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
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.
862 static int bsd_decompress (void *state, unsigned char *ibuf, int isize,
863 unsigned char *obuf, int osize)
866 unsigned int max_ent;
868 unsigned int bitno; /* 1st valid bit in accm */
870 unsigned int tgtbitno; /* bitno when we have a code */
871 struct bsd_dict *dictp;
875 unsigned int oldcode;
876 unsigned int finchar;
885 db = (struct bsd_db *) state;
886 max_ent = db->max_ent;
888 bitno = 32; /* 1st valid bit in accm */
890 tgtbitno = 32 - n_bits; /* bitno when we have a code */
893 * Save the address/control from the PPP header
894 * and then get the sequence number.
897 adrs = PPP_ADDRESS (ibuf);
898 ctrl = PPP_CONTROL (ibuf);
900 seq = (ibuf[4] << 8) + ibuf[5];
902 ibuf += (PPP_HDRLEN + 2);
903 ilen = isize - (PPP_HDRLEN + 2);
906 * Check the sequence number and give up if it differs from
907 * the value we're expecting.
910 if (seq != db->seqno)
914 printk("bsd_decomp%d: bad sequence # %d, expected %d\n",
915 db->unit, seq, db->seqno - 1);
921 db->bytes_out += ilen;
924 * Fill in the ppp header, but not the last byte of the protocol
925 * (that comes from the decompressed data).
937 * Keep the checkpoint correctly so that incompressible packets
938 * clear the dictionary at the proper times.
945 db->in_count += (explen - 3); /* don't count the header */
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.
956 accm |= *ibuf++ << bitno;
957 if (tgtbitno < bitno)
962 incode = accm >> tgtbitno;
967 * The dictionary must only be cleared at the end of a packet.
976 printk("bsd_decomp%d: bad CLEAR\n", db->unit);
978 return DECOMP_FATALERROR; /* probably a bug */
985 if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
986 || (incode > max_ent && oldcode == CLEAR))
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);
995 return DECOMP_FATALERROR; /* probably a bug */
998 /* Special case for KwKwK string. */
999 if (incode > max_ent)
1010 codelen = *(lens_ptr (db, finchar));
1011 explen += codelen + extra;
1016 printk("bsd_decomp%d: ran out of mru\n", db->unit);
1018 printk(" len=%d, finchar=0x%x, codelen=%d, explen=%d\n",
1019 ilen, finchar, codelen, explen);
1022 return DECOMP_FATALERROR;
1026 * Decode this code and install it in the decompressed buffer.
1031 while (finchar > LAST)
1033 struct bsd_dict *dictp2 = dict_ptr (db, finchar);
1035 dictp = dict_ptr (db, dictp2->cptr);
1037 if (--codelen <= 0 || dictp->codem1 != finchar-1)
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);
1047 if (dictp->codem1 != finchar-1)
1049 printk("bsd_decomp%d: bad code chain 0x%x "
1051 db->unit, incode, finchar);
1053 printk("oldcode=0x%x cptr=0x%x codem1=0x%x\n",
1054 oldcode, dictp2->cptr, dictp->codem1);
1057 return DECOMP_FATALERROR;
1060 *--p = dictp->f.hs.suffix;
1061 finchar = dictp->f.hs.prefix;
1068 printk("bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n",
1069 db->unit, codelen, incode, max_ent);
1073 if (extra) /* the KwKwK case again */
1079 * If not first code in a packet, and
1080 * if not out of code space, then allocate a new code.
1082 * Keep the hash table correct so it can be used
1083 * with uncompressed packets.
1086 if (oldcode != CLEAR && max_ent < db->maxmaxcode)
1088 struct bsd_dict *dictp2, *dictp3;
1089 unsigned short *lens1, *lens2;
1090 unsigned long fcode;
1091 int hval, disp, indx;
1093 fcode = BSD_KEY(oldcode,finchar);
1094 hval = BSD_HASH(oldcode,finchar,db->hshift);
1095 dictp = dict_ptr (db, hval);
1097 /* look for a free hash table entry */
1098 if (dictp->codem1 < max_ent)
1100 disp = (hval == 0) ? 1 : hval;
1104 if (hval >= db->hsize)
1108 dictp = dict_ptr (db, hval);
1110 while (dictp->codem1 < max_ent);
1114 * Invalidate previous hash table entry
1115 * assigned this code, and then take it over
1118 dictp2 = dict_ptr (db, max_ent + 1);
1119 indx = dictp2->cptr;
1120 dictp3 = dict_ptr (db, indx);
1122 if (dictp3->codem1 == max_ent)
1124 dictp3->codem1 = BADCODEM1;
1127 dictp2->cptr = hval;
1128 dictp->codem1 = max_ent;
1129 dictp->f.fcode = fcode;
1130 db->max_ent = ++max_ent;
1132 /* Update the length of this string. */
1133 lens1 = lens_ptr (db, max_ent);
1134 lens2 = lens_ptr (db, oldcode);
1135 *lens1 = *lens2 + 1;
1137 /* Expand code size if needed. */
1138 if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode)
1140 db->n_bits = ++n_bits;
1141 tgtbitno = 32-n_bits;
1149 db->comp_bytes += isize - BSD_OVHD - PPP_HDRLEN;
1150 db->uncomp_bytes += explen;
1156 printk("bsd_decomp%d: peer should have cleared dictionary on %d\n",
1157 db->unit, db->seqno - 1);
1163 /*************************************************************
1164 * Table of addresses for the BSD compression module
1165 *************************************************************/
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 */
1184 /*************************************************************
1185 * Module support routines
1186 *************************************************************/
1191 int answer = ppp_register_compressor (&ppp_bsd_compress);
1193 printk (KERN_INFO "PPP BSD Compression module registered\n");
1198 cleanup_module(void)
1200 ppp_unregister_compressor (&ppp_bsd_compress);