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