linux-old/drivers/isdn/isdn_bsdcomp.c
<<
>>
Prefs
   1/*
   2 * BSD compression module
   3 *
   4 * Patched version for ISDN syncPPP written 1997/1998 by Michael Hipp
   5 * The whole module is now SKB based.
   6 *
   7 * Compile with:
   8 *  gcc -O2 -I/usr/src/linux/include -D__KERNEL__ -DMODULE -c isdn_bsdcomp.c
   9 */
  10
  11/*
  12 * Original copyright notice:
  13 *
  14 * Copyright (c) 1985, 1986 The Regents of the University of California.
  15 * All rights reserved.
  16 *
  17 * This code is derived from software contributed to Berkeley by
  18 * James A. Woods, derived from original work by Spencer Thomas
  19 * and Joseph Orost.
  20 *
  21 * Redistribution and use in source and binary forms, with or without
  22 * modification, are permitted provided that the following conditions
  23 * are met:
  24 * 1. Redistributions of source code must retain the above copyright
  25 *    notice, this list of conditions and the following disclaimer.
  26 * 2. Redistributions in binary form must reproduce the above copyright
  27 *    notice, this list of conditions and the following disclaimer in the
  28 *    documentation and/or other materials provided with the distribution.
  29 * 3. All advertising materials mentioning features or use of this software
  30 *    must display the following acknowledgement:
  31 *      This product includes software developed by the University of
  32 *      California, Berkeley and its contributors.
  33 * 4. Neither the name of the University nor the names of its contributors
  34 *    may be used to endorse or promote products derived from this software
  35 *    without specific prior written permission.
  36 *
  37 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  38 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  39 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  40 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  41 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  42 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  43 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  45 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  46 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  47 * SUCH DAMAGE.
  48 */
  49
  50#ifndef MODULE
  51#error This file must be compiled as a module.
  52#endif
  53
  54#include <linux/module.h>
  55
  56#include <linux/kernel.h>
  57#include <linux/sched.h>
  58#include <linux/types.h>
  59#include <linux/fcntl.h>
  60#include <linux/interrupt.h>
  61#include <linux/ptrace.h>
  62#include <linux/ioport.h>
  63#include <linux/in.h>
  64#include <linux/malloc.h>
  65#include <linux/tty.h>
  66#include <linux/errno.h>
  67#include <linux/string.h>       /* used in new tty drivers */
  68#include <linux/signal.h>       /* used in new tty drivers */
  69
  70#include <asm/system.h>
  71#include <asm/bitops.h>
  72#include <asm/segment.h>
  73#include <asm/byteorder.h>
  74#include <asm/types.h>
  75
  76#include <linux/if.h>
  77
  78#include <linux/if_ether.h>
  79#include <linux/netdevice.h>
  80#include <linux/skbuff.h>
  81#include <linux/inet.h>
  82#include <linux/ioctl.h>
  83
  84#include <linux/ppp_defs.h>
  85
  86#include <linux/isdn.h>
  87#include <linux/isdn_ppp.h>
  88/* #include <linux/netprotocol.h> */
  89#include <linux/ip.h>
  90#include <linux/tcp.h>
  91#include <linux/if_arp.h>
  92#include <linux/ppp-comp.h>
  93
  94#include "isdn_ppp.h"
  95
  96#define BSD_VERSION(x)  ((x) >> 5)
  97#define BSD_NBITS(x)    ((x) & 0x1F)
  98
  99#define BSD_CURRENT_VERSION     1
 100
 101#define DEBUG 1
 102
 103/*
 104 * A dictionary for doing BSD compress.
 105 */
 106
 107struct bsd_dict {
 108        u32 fcode;
 109        u16 codem1;             /* output of hash table -1 */
 110        u16 cptr;               /* map code to hash table entry */
 111};
 112
 113struct bsd_db {
 114        int            totlen;          /* length of this structure */
 115        unsigned int   hsize;           /* size of the hash table */
 116        unsigned char  hshift;          /* used in hash function */
 117        unsigned char  n_bits;          /* current bits/code */
 118        unsigned char  maxbits;         /* maximum bits/code */
 119        unsigned char  debug;           /* non-zero if debug desired */
 120        unsigned char  unit;            /* ppp unit number */
 121        u16 seqno;                      /* sequence # of next packet */
 122        unsigned int   mru;             /* size of receive (decompress) bufr */
 123        unsigned int   maxmaxcode;      /* largest valid code */
 124        unsigned int   max_ent;         /* largest code in use */
 125        unsigned int   in_count;        /* uncompressed bytes, aged */
 126        unsigned int   bytes_out;       /* compressed bytes, aged */
 127        unsigned int   ratio;           /* recent compression ratio */
 128        unsigned int   checkpoint;      /* when to next check the ratio */
 129        unsigned int   clear_count;     /* times dictionary cleared */
 130        unsigned int   incomp_count;    /* incompressible packets */
 131        unsigned int   incomp_bytes;    /* incompressible bytes */
 132        unsigned int   uncomp_count;    /* uncompressed packets */
 133        unsigned int   uncomp_bytes;    /* uncompressed bytes */
 134        unsigned int   comp_count;      /* compressed packets */
 135        unsigned int   comp_bytes;      /* compressed bytes */
 136        unsigned short  *lens;          /* array of lengths of codes */
 137        struct bsd_dict *dict;          /* dictionary */
 138        int xmit;
 139};
 140
 141#define BSD_OVHD        2               /* BSD compress overhead/packet */
 142#define MIN_BSD_BITS    9
 143#define BSD_INIT_BITS   MIN_BSD_BITS
 144#define MAX_BSD_BITS    15
 145
 146/*
 147 * the next two codes should not be changed lightly, as they must not
 148 * lie within the contiguous general code space.
 149 */
 150#define CLEAR   256                     /* table clear output code */
 151#define FIRST   257                     /* first free entry */
 152#define LAST    255
 153
 154#define MAXCODE(b)      ((1 << (b)) - 1)
 155#define BADCODEM1       MAXCODE(MAX_BSD_BITS);
 156
 157#define BSD_HASH(prefix,suffix,hshift) ((((unsigned long)(suffix))<<(hshift)) \
 158                                         ^ (unsigned long)(prefix))
 159#define BSD_KEY(prefix,suffix)          ((((unsigned long)(suffix)) << 16) \
 160                                         + (unsigned long)(prefix))
 161
 162#define CHECK_GAP       10000           /* Ratio check interval */
 163
 164#define RATIO_SCALE_LOG 8
 165#define RATIO_SCALE     (1<<RATIO_SCALE_LOG)
 166#define RATIO_MAX       (0x7fffffff>>RATIO_SCALE_LOG)
 167
 168/*
 169 * clear the dictionary
 170 */
 171
 172static void bsd_clear(struct bsd_db *db)
 173{
 174        db->clear_count++;
 175        db->max_ent      = FIRST-1;
 176        db->n_bits       = BSD_INIT_BITS;
 177        db->bytes_out    = 0;
 178        db->in_count     = 0;
 179        db->incomp_count = 0;
 180        db->ratio            = 0;
 181        db->checkpoint   = CHECK_GAP;
 182}
 183
 184/*
 185 * If the dictionary is full, then see if it is time to reset it.
 186 *
 187 * Compute the compression ratio using fixed-point arithmetic
 188 * with 8 fractional bits.
 189 *
 190 * Since we have an infinite stream instead of a single file,
 191 * watch only the local compression ratio.
 192 *
 193 * Since both peers must reset the dictionary at the same time even in
 194 * the absence of CLEAR codes (while packets are incompressible), they
 195 * must compute the same ratio.
 196 */
 197static int bsd_check (struct bsd_db *db)        /* 1=output CLEAR */
 198{
 199    unsigned int new_ratio;
 200
 201    if (db->in_count >= db->checkpoint)
 202      {
 203        /* age the ratio by limiting the size of the counts */
 204        if (db->in_count >= RATIO_MAX || db->bytes_out >= RATIO_MAX)
 205          {
 206            db->in_count  -= (db->in_count  >> 2);
 207            db->bytes_out -= (db->bytes_out >> 2);
 208          }
 209        
 210        db->checkpoint = db->in_count + CHECK_GAP;
 211        
 212        if (db->max_ent >= db->maxmaxcode)
 213          {
 214            /* Reset the dictionary only if the ratio is worse,
 215             * or if it looks as if it has been poisoned
 216             * by incompressible data.
 217             *
 218             * This does not overflow, because
 219             *  db->in_count <= RATIO_MAX.
 220             */
 221
 222            new_ratio = db->in_count << RATIO_SCALE_LOG;
 223            if (db->bytes_out != 0)
 224              {
 225                new_ratio /= db->bytes_out;
 226              }
 227            
 228            if (new_ratio < db->ratio || new_ratio < 1 * RATIO_SCALE)
 229              {
 230                bsd_clear (db);
 231                return 1;
 232              }
 233            db->ratio = new_ratio;
 234          }
 235      }
 236    return 0;
 237}
 238
 239/*
 240 * Return statistics.
 241 */
 242
 243static void bsd_stats (void *state, struct compstat *stats)
 244{
 245        struct bsd_db *db = (struct bsd_db *) state;
 246    
 247        stats->unc_bytes    = db->uncomp_bytes;
 248        stats->unc_packets  = db->uncomp_count;
 249        stats->comp_bytes   = db->comp_bytes;
 250        stats->comp_packets = db->comp_count;
 251        stats->inc_bytes    = db->incomp_bytes;
 252        stats->inc_packets  = db->incomp_count;
 253        stats->in_count     = db->in_count;
 254        stats->bytes_out    = db->bytes_out;
 255}
 256
 257/*
 258 * Reset state, as on a CCP ResetReq.
 259 */
 260static void bsd_reset (void *state,unsigned char code, unsigned char id,
 261                        unsigned char *data, unsigned len,
 262                        struct isdn_ppp_resetparams *rsparm)
 263{
 264        struct bsd_db *db = (struct bsd_db *) state;
 265
 266        bsd_clear(db);
 267        db->seqno       = 0;
 268        db->clear_count = 0;
 269}
 270
 271/*
 272 * Release the compression structure
 273 */
 274static void bsd_free (void *state)
 275{
 276        struct bsd_db *db = (struct bsd_db *) state;
 277
 278        if (db) {
 279                /*
 280                 * Release the dictionary
 281                 */
 282                if (db->dict) {
 283                        vfree (db->dict);
 284                        db->dict = NULL;
 285                }
 286
 287                /*
 288                 * Release the string buffer
 289                 */
 290                if (db->lens) {
 291                        vfree (db->lens);
 292                        db->lens = NULL;
 293                }
 294
 295                /*
 296                 * Finally release the structure itself.
 297                 */
 298                kfree (db);
 299                MOD_DEC_USE_COUNT;
 300        }
 301}
 302
 303
 304/*
 305 * Allocate space for a (de) compressor.
 306 */
 307static void *bsd_alloc (struct isdn_ppp_comp_data *data)
 308{
 309        int bits;
 310        unsigned int hsize, hshift, maxmaxcode;
 311        struct bsd_db *db;
 312        int decomp;
 313
 314        static unsigned int htab[][2] = {
 315                { 5003 , 4 } , { 5003 , 4 } , { 5003 , 4 } , { 5003 , 4 } , 
 316                { 9001 , 5 } , { 18013 , 6 } , { 35023 , 7 } , { 69001 , 8 } 
 317        };
 318                
 319        if (data->optlen != 1 || data->num != CI_BSD_COMPRESS
 320                || BSD_VERSION(data->options[0]) != BSD_CURRENT_VERSION)
 321                return NULL;
 322
 323        bits = BSD_NBITS(data->options[0]);
 324
 325        if(bits < 9 || bits > 15)
 326                return NULL;
 327
 328        hsize = htab[bits-9][0];
 329        hshift = htab[bits-9][1];
 330        
 331        /*
 332         * Allocate the main control structure for this instance.
 333         */
 334        maxmaxcode = MAXCODE(bits);
 335        db = (struct bsd_db *) kmalloc (sizeof (struct bsd_db),GFP_KERNEL);
 336        if (!db)
 337                return NULL;
 338
 339        memset (db, 0, sizeof(struct bsd_db));
 340
 341        db->xmit = data->flags & IPPP_COMP_FLAG_XMIT;
 342        decomp = db->xmit ? 0 : 1;
 343
 344        /*
 345         * Allocate space for the dictionary. This may be more than one page in
 346         * length.
 347         */
 348        db->dict = (struct bsd_dict *) vmalloc (hsize * sizeof (struct bsd_dict));
 349        if (!db->dict) {
 350                bsd_free (db);
 351                return NULL;
 352        }
 353
 354        MOD_INC_USE_COUNT;
 355
 356        /*
 357         * If this is the compression buffer then there is no length data.
 358         * For decompression, the length information is needed as well.
 359         */
 360        if (!decomp)
 361                db->lens = NULL;
 362        else {
 363                db->lens = (unsigned short *) vmalloc ((maxmaxcode + 1) *
 364                        sizeof (db->lens[0]));
 365                if (!db->lens) {
 366                        bsd_free (db); /* calls MOD_DEC_USE_COUNT; */
 367                        return (NULL);
 368                }
 369        }
 370
 371        /*
 372         * Initialize the data information for the compression code
 373         */
 374        db->totlen     = sizeof (struct bsd_db) + (sizeof (struct bsd_dict) * hsize);
 375        db->hsize      = hsize;
 376        db->hshift     = hshift;
 377        db->maxmaxcode = maxmaxcode;
 378        db->maxbits    = bits;
 379
 380        return (void *) db;
 381}
 382
 383/*
 384 * Initialize the database.
 385 */
 386static int bsd_init (void *state, struct isdn_ppp_comp_data *data, int unit, int debug)
 387{
 388        struct bsd_db *db = state;
 389        int indx;
 390        int decomp;
 391
 392        if(!state || !data) {
 393                printk(KERN_ERR "isdn_bsd_init: [%d] ERR, state %lx data %lx\n",unit,(long)state,(long)data);
 394                return 0;
 395        }
 396
 397        decomp = db->xmit ? 0 : 1;
 398    
 399        if (data->optlen != 1 || data->num != CI_BSD_COMPRESS
 400                || (BSD_VERSION(data->options[0]) != BSD_CURRENT_VERSION)
 401                || (BSD_NBITS(data->options[0]) != db->maxbits)
 402                || (decomp && db->lens == NULL)) {
 403                printk(KERN_ERR "isdn_bsd: %d %d %d %d %lx\n",data->optlen,data->num,data->options[0],decomp,(unsigned long)db->lens);
 404                return 0;
 405        }
 406
 407        if (decomp)
 408                for(indx=LAST;indx>=0;indx--)
 409                        db->lens[indx] = 1;
 410
 411        indx = db->hsize;
 412        while (indx-- != 0) {
 413                db->dict[indx].codem1 = BADCODEM1;
 414                db->dict[indx].cptr   = 0;
 415        }
 416
 417        db->unit = unit;
 418        db->mru  = 0;
 419
 420        db->debug = 1;
 421    
 422        bsd_reset(db,0,0,NULL,0,NULL);
 423    
 424        return 1;
 425}
 426
 427/*
 428 * Obtain pointers to the various structures in the compression tables
 429 */
 430
 431#define dict_ptrx(p,idx) &(p->dict[idx])
 432#define lens_ptrx(p,idx) &(p->lens[idx])
 433
 434#ifdef DEBUG
 435static unsigned short *lens_ptr(struct bsd_db *db, int idx)
 436{
 437        if ((unsigned int) idx > (unsigned int) db->maxmaxcode) {
 438                printk (KERN_DEBUG "<9>ppp: lens_ptr(%d) > max\n", idx);
 439                idx = 0;
 440        }
 441        return lens_ptrx (db, idx);
 442}
 443
 444static struct bsd_dict *dict_ptr(struct bsd_db *db, int idx)
 445{
 446        if ((unsigned int) idx >= (unsigned int) db->hsize) {
 447                printk (KERN_DEBUG "<9>ppp: dict_ptr(%d) > max\n", idx);
 448                idx = 0;
 449        }
 450        return dict_ptrx (db, idx);
 451}
 452
 453#else
 454#define lens_ptr(db,idx) lens_ptrx(db,idx)
 455#define dict_ptr(db,idx) dict_ptrx(db,idx)
 456#endif
 457
 458/*
 459 * compress a packet
 460 */
 461static int bsd_compress (void *state, struct sk_buff *skb_in, struct sk_buff *skb_out,int proto)
 462{
 463        struct bsd_db *db;
 464        int hshift;
 465        unsigned int max_ent;
 466        unsigned int n_bits;
 467        unsigned int bitno;
 468        unsigned long accm;
 469        int ent;
 470        unsigned long fcode;
 471        struct bsd_dict *dictp;
 472        unsigned char c;
 473        int hval,disp,ilen,mxcode;
 474        unsigned char *rptr = skb_in->data;
 475        int isize = skb_in->len;
 476
 477#define OUTPUT(ent)                     \
 478  {                                     \
 479    bitno -= n_bits;                    \
 480    accm |= ((ent) << bitno);           \
 481    do  {                               \
 482        if(skb_out && skb_tailroom(skb_out) > 0)        \
 483                *(skb_put(skb_out,1)) = (unsigned char) (accm>>24); \
 484        accm <<= 8;                     \
 485        bitno += 8;                     \
 486    } while (bitno <= 24);              \
 487  }
 488
 489        /*
 490         * If the protocol is not in the range we're interested in,
 491         * just return without compressing the packet.  If it is,
 492         * the protocol becomes the first byte to compress.
 493         */
 494        printk(KERN_DEBUG "bsd_compress called with %x\n",proto);
 495        
 496        ent = proto;
 497        if (proto < 0x21 || proto > 0xf9 || !(proto & 0x1) )
 498                return 0;
 499
 500        db      = (struct bsd_db *) state;
 501        hshift  = db->hshift;
 502        max_ent = db->max_ent;
 503        n_bits  = db->n_bits;
 504        bitno   = 32;
 505        accm    = 0;
 506        mxcode  = MAXCODE (n_bits);
 507        
 508        /* This is the PPP header information */
 509        if(skb_out && skb_tailroom(skb_out) >= 2) {
 510                char *v = skb_put(skb_out,2);
 511                /* we only push our own data on the header,
 512                  AC,PC and protos is pushed by caller  */
 513                v[0] = db->seqno >> 8;
 514                v[1] = db->seqno;
 515        }
 516
 517        ilen   = ++isize; /* This is off by one, but that is what is in draft! */
 518
 519        while (--ilen > 0) {
 520                c     = *rptr++;
 521                fcode = BSD_KEY  (ent, c);
 522                hval  = BSD_HASH (ent, c, hshift);
 523                dictp = dict_ptr (db, hval);
 524        
 525                /* Validate and then check the entry. */
 526                if (dictp->codem1 >= max_ent)
 527                        goto nomatch;
 528
 529                if (dictp->fcode == fcode) {
 530                        ent = dictp->codem1 + 1;
 531                        continue;       /* found (prefix,suffix) */
 532                }
 533        
 534                /* continue probing until a match or invalid entry */
 535                disp = (hval == 0) ? 1 : hval;
 536
 537                do {
 538                        hval += disp;
 539                        if (hval >= db->hsize)
 540                                hval -= db->hsize;
 541                        dictp = dict_ptr (db, hval);
 542                        if (dictp->codem1 >= max_ent)
 543                                goto nomatch;
 544                } while (dictp->fcode != fcode);
 545
 546                ent = dictp->codem1 + 1;        /* finally found (prefix,suffix) */
 547                continue;
 548        
 549nomatch:
 550                OUTPUT(ent);            /* output the prefix */
 551        
 552                /* code -> hashtable */
 553                if (max_ent < db->maxmaxcode) {
 554                        struct bsd_dict *dictp2;
 555                        struct bsd_dict *dictp3;
 556                        int indx;
 557
 558                        /* expand code size if needed */
 559                        if (max_ent >= mxcode) {
 560                                db->n_bits = ++n_bits;
 561                                mxcode = MAXCODE (n_bits);
 562                        }
 563            
 564                        /* 
 565                         * Invalidate old hash table entry using
 566                         * this code, and then take it over.
 567                         */
 568                        dictp2 = dict_ptr (db, max_ent + 1);
 569                        indx   = dictp2->cptr;
 570                        dictp3 = dict_ptr (db, indx);
 571
 572                        if (dictp3->codem1 == max_ent)
 573                                dictp3->codem1 = BADCODEM1;
 574
 575                        dictp2->cptr   = hval;
 576                        dictp->codem1  = max_ent;
 577                        dictp->fcode = fcode;
 578                        db->max_ent    = ++max_ent;
 579
 580                        if (db->lens) {
 581                                unsigned short *len1 = lens_ptr (db, max_ent);
 582                                unsigned short *len2 = lens_ptr (db, ent);
 583                                *len1 = *len2 + 1;
 584                        }
 585                }
 586                ent = c;
 587        }
 588    
 589        OUTPUT(ent);            /* output the last code */
 590
 591        if(skb_out)
 592                db->bytes_out    += skb_out->len; /* Do not count bytes from here */
 593        db->uncomp_bytes += isize;
 594        db->in_count     += isize;
 595        ++db->uncomp_count;
 596        ++db->seqno;
 597
 598        if (bitno < 32)
 599                ++db->bytes_out; /* must be set before calling bsd_check */
 600
 601        /*
 602         * Generate the clear command if needed
 603         */
 604
 605        if (bsd_check(db))
 606                OUTPUT (CLEAR);
 607
 608        /*
 609         * Pad dribble bits of last code with ones.
 610         * Do not emit a completely useless byte of ones.
 611         */
 612        if (bitno < 32 && skb_out && skb_tailroom(skb_out) > 0) 
 613                *(skb_put(skb_out,1)) = (unsigned char) ((accm | (0xff << (bitno-8))) >> 24);
 614    
 615        /*
 616         * Increase code size if we would have without the packet
 617         * boundary because the decompressor will do so.
 618         */
 619        if (max_ent >= mxcode && max_ent < db->maxmaxcode)
 620                db->n_bits++;
 621
 622        /* If output length is too large then this is an incompressible frame. */
 623        if (!skb_out || (skb_out && skb_out->len >= skb_in->len) ) {
 624                ++db->incomp_count;
 625                db->incomp_bytes += isize;
 626                return 0;
 627        }
 628
 629        /* Count the number of compressed frames */
 630        ++db->comp_count;
 631        db->comp_bytes += skb_out->len;
 632        return skb_out->len;
 633
 634#undef OUTPUT
 635}
 636
 637/*
 638 * Update the "BSD Compress" dictionary on the receiver for
 639 * incompressible data by pretending to compress the incoming data.
 640 */
 641static void bsd_incomp (void *state, struct sk_buff *skb_in,int proto)
 642{
 643        bsd_compress (state, skb_in, NULL, proto);
 644}
 645
 646/*
 647 * Decompress "BSD Compress".
 648 */
 649static int bsd_decompress (void *state, struct sk_buff *skb_in, struct sk_buff *skb_out,
 650                           struct isdn_ppp_resetparams *rsparm)
 651{
 652        struct bsd_db *db;
 653        unsigned int max_ent;
 654        unsigned long accm;
 655        unsigned int bitno;             /* 1st valid bit in accm */
 656        unsigned int n_bits;
 657        unsigned int tgtbitno;  /* bitno when we have a code */
 658        struct bsd_dict *dictp;
 659        int seq;
 660        unsigned int incode;
 661        unsigned int oldcode;
 662        unsigned int finchar;
 663        unsigned char *p,*ibuf;
 664        int ilen;
 665        int codelen;
 666        int extra;
 667
 668        db       = (struct bsd_db *) state;
 669        max_ent  = db->max_ent;
 670        accm     = 0;
 671        bitno    = 32;          /* 1st valid bit in accm */
 672        n_bits   = db->n_bits;
 673        tgtbitno = 32 - n_bits; /* bitno when we have a code */
 674
 675        printk(KERN_DEBUG "bsd_decompress called\n");
 676
 677        if(!skb_in || !skb_out) {
 678                printk(KERN_ERR "bsd_decompress called with NULL parameter\n");
 679                return DECOMP_ERROR;
 680        }
 681    
 682        /*
 683         * Get the sequence number.
 684         */
 685        if( (p = skb_pull(skb_in,2)) == NULL) {
 686                return DECOMP_ERROR;
 687        }
 688        p-=2;
 689        seq   = (p[0] << 8) + p[1];
 690        ilen  = skb_in->len;
 691        ibuf = skb_in->data;
 692
 693        /*
 694         * Check the sequence number and give up if it differs from
 695         * the value we're expecting.
 696         */
 697        if (seq != db->seqno) {
 698                if (db->debug) {
 699                        printk(KERN_DEBUG "bsd_decomp%d: bad sequence # %d, expected %d\n",
 700                                db->unit, seq, db->seqno - 1);
 701                }
 702                return DECOMP_ERROR;
 703        }
 704
 705        ++db->seqno;
 706        db->bytes_out += ilen;
 707
 708        if(skb_tailroom(skb_out) > 0)
 709                *(skb_put(skb_out,1)) = 0;
 710        else
 711                return DECOMP_ERR_NOMEM;
 712    
 713        oldcode = CLEAR;
 714
 715        /*
 716         * Keep the checkpoint correctly so that incompressible packets
 717         * clear the dictionary at the proper times.
 718         */
 719
 720        for (;;) {
 721                if (ilen-- <= 0) {
 722                        db->in_count += (skb_out->len - 1); /* don't count the header */
 723                        break;
 724                }
 725
 726                /*
 727                 * Accumulate bytes until we have a complete code.
 728                 * Then get the next code, relying on the 32-bit,
 729                 * unsigned accm to mask the result.
 730                 */
 731
 732                bitno -= 8;
 733                accm  |= *ibuf++ << bitno;
 734                if (tgtbitno < bitno)
 735                        continue;
 736
 737                incode = accm >> tgtbitno;
 738                accm <<= n_bits;
 739                bitno += n_bits;
 740
 741                /*
 742                 * The dictionary must only be cleared at the end of a packet.
 743                 */
 744        
 745                if (incode == CLEAR) {
 746                        if (ilen > 0) {
 747                                if (db->debug)
 748                                        printk(KERN_DEBUG "bsd_decomp%d: bad CLEAR\n", db->unit);
 749                                return DECOMP_FATALERROR;       /* probably a bug */
 750                        }
 751                        bsd_clear(db);
 752                        break;
 753                }
 754
 755                if ((incode > max_ent + 2) || (incode > db->maxmaxcode)
 756                        || (incode > max_ent && oldcode == CLEAR)) {
 757                        if (db->debug) {
 758                                printk(KERN_DEBUG "bsd_decomp%d: bad code 0x%x oldcode=0x%x ",
 759                                        db->unit, incode, oldcode);
 760                                printk(KERN_DEBUG "max_ent=0x%x skb->Len=%d seqno=%d\n",
 761                                        max_ent, skb_out->len, db->seqno);
 762                        }
 763                        return DECOMP_FATALERROR;       /* probably a bug */
 764                }
 765        
 766                /* Special case for KwKwK string. */
 767                if (incode > max_ent) {
 768                        finchar = oldcode;
 769                        extra   = 1;
 770                } else {
 771                        finchar = incode;
 772                        extra   = 0;
 773                }
 774
 775                codelen = *(lens_ptr (db, finchar));
 776                if( skb_tailroom(skb_out) < codelen + extra) {
 777                        if (db->debug) {
 778                                printk(KERN_DEBUG "bsd_decomp%d: ran out of mru\n", db->unit);
 779#ifdef DEBUG
 780                                printk(KERN_DEBUG "  len=%d, finchar=0x%x, codelen=%d,skblen=%d\n",
 781                                        ilen, finchar, codelen, skb_out->len);
 782#endif
 783                        }
 784                        return DECOMP_FATALERROR;
 785                }
 786
 787                /*
 788                 * Decode this code and install it in the decompressed buffer.
 789                 */
 790
 791                p     = skb_put(skb_out,codelen);
 792                p += codelen;
 793                while (finchar > LAST) {
 794                        struct bsd_dict *dictp2 = dict_ptr (db, finchar);
 795            
 796                        dictp = dict_ptr (db, dictp2->cptr);
 797
 798#ifdef DEBUG
 799                        if (--codelen <= 0 || dictp->codem1 != finchar-1) {
 800                                if (codelen <= 0) {
 801                                        printk(KERN_ERR "bsd_decomp%d: fell off end of chain ", db->unit);
 802                                        printk(KERN_ERR "0x%x at 0x%x by 0x%x, max_ent=0x%x\n", incode, finchar, dictp2->cptr, max_ent);
 803                                } else {
 804                                        if (dictp->codem1 != finchar-1) {
 805                                                printk(KERN_ERR "bsd_decomp%d: bad code chain 0x%x finchar=0x%x ",db->unit, incode, finchar);
 806                                                printk(KERN_ERR "oldcode=0x%x cptr=0x%x codem1=0x%x\n", oldcode, dictp2->cptr, dictp->codem1);
 807                                        }
 808                                }
 809                                return DECOMP_FATALERROR;
 810                        }
 811#endif
 812
 813                        {
 814                                u32 fcode = dictp->fcode;
 815                                *--p    = (fcode >> 16) & 0xff;
 816                                finchar = fcode & 0xffff;
 817                        }
 818                }
 819                *--p = finchar;
 820        
 821#ifdef DEBUG
 822                if (--codelen != 0)
 823                        printk(KERN_ERR "bsd_decomp%d: short by %d after code 0x%x, max_ent=0x%x\n", db->unit, codelen, incode, max_ent);
 824#endif
 825        
 826                if (extra)              /* the KwKwK case again */
 827                        *(skb_put(skb_out,1)) = finchar;
 828        
 829                /*
 830                 * If not first code in a packet, and
 831                 * if not out of code space, then allocate a new code.
 832                 *
 833                 * Keep the hash table correct so it can be used
 834                 * with uncompressed packets.
 835                 */
 836                if (oldcode != CLEAR && max_ent < db->maxmaxcode) {
 837                        struct bsd_dict *dictp2, *dictp3;
 838                        u16  *lens1,  *lens2;
 839                        unsigned long fcode;
 840                        int hval, disp, indx;
 841            
 842                        fcode = BSD_KEY(oldcode,finchar);
 843                        hval  = BSD_HASH(oldcode,finchar,db->hshift);
 844                        dictp = dict_ptr (db, hval);
 845            
 846                        /* look for a free hash table entry */
 847                        if (dictp->codem1 < max_ent) {
 848                                disp = (hval == 0) ? 1 : hval;
 849                                do {
 850                                        hval += disp;
 851                                        if (hval >= db->hsize)
 852                                                hval -= db->hsize;
 853                                        dictp = dict_ptr (db, hval);
 854                                } while (dictp->codem1 < max_ent);
 855                        }
 856            
 857                        /*
 858                         * Invalidate previous hash table entry
 859                         * assigned this code, and then take it over
 860                         */
 861
 862                        dictp2 = dict_ptr (db, max_ent + 1);
 863                        indx   = dictp2->cptr;
 864                        dictp3 = dict_ptr (db, indx);
 865
 866                        if (dictp3->codem1 == max_ent)
 867                                dictp3->codem1 = BADCODEM1;
 868
 869                        dictp2->cptr   = hval;
 870                        dictp->codem1  = max_ent;
 871                        dictp->fcode = fcode;
 872                        db->max_ent    = ++max_ent;
 873
 874                        /* Update the length of this string. */
 875                        lens1  = lens_ptr (db, max_ent);
 876                        lens2  = lens_ptr (db, oldcode);
 877                        *lens1 = *lens2 + 1;
 878            
 879                        /* Expand code size if needed. */
 880                        if (max_ent >= MAXCODE(n_bits) && max_ent < db->maxmaxcode) {
 881                                db->n_bits = ++n_bits;
 882                                tgtbitno   = 32-n_bits;
 883                        }
 884                }
 885                oldcode = incode;
 886        }
 887
 888        ++db->comp_count;
 889        ++db->uncomp_count;
 890        db->comp_bytes   += skb_in->len - BSD_OVHD;
 891        db->uncomp_bytes += skb_out->len;
 892
 893        if (bsd_check(db)) {
 894                if (db->debug)
 895                        printk(KERN_DEBUG "bsd_decomp%d: peer should have cleared dictionary on %d\n",
 896                                db->unit, db->seqno - 1);
 897        }
 898        return skb_out->len;
 899}
 900
 901/*************************************************************
 902 * Table of addresses for the BSD compression module
 903 *************************************************************/
 904
 905static struct isdn_ppp_compressor ippp_bsd_compress = {
 906        NULL,NULL,              /* prev,next: overwritten by isdn_ppp */
 907        CI_BSD_COMPRESS,        /* compress_proto */
 908        bsd_alloc,              /* alloc */
 909        bsd_free,               /* free */
 910        bsd_init,               /* init */
 911        bsd_reset,              /* reset */
 912        bsd_compress,           /* compress */
 913        bsd_decompress,         /* decompress */
 914        bsd_incomp,             /* incomp */
 915        bsd_stats               /* comp_stat */
 916};
 917
 918/*************************************************************
 919 * Module support routines
 920 *************************************************************/
 921
 922int init_module(void)
 923{
 924        int answer = isdn_ppp_register_compressor (&ippp_bsd_compress);
 925        if (answer == 0)
 926                printk (KERN_INFO "PPP BSD Compression module registered\n");
 927        return answer;
 928}
 929
 930void cleanup_module(void)
 931{
 932        isdn_ppp_unregister_compressor (&ippp_bsd_compress);
 933}
 934
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.