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