OpenCores
URL https://opencores.org/ocsvn/or1k/or1k/trunk

Subversion Repositories or1k

[/] [or1k/] [trunk/] [rc203soc/] [sw/] [uClinux/] [drivers/] [net/] [bsd_comp.c] - Blame information for rev 1765

Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.