rfc1977.txt

改文件中包含了三个协议

                i = hsize;
                while (i != 0) {
                        db->dict[--i].codem1 = BADCODEM1;
                        db->dict[i].cptr = 0;
                }
        }

        bzero(db,sizeof(*db)-sizeof(db->dict));
        db->lens = lens;
        db->unit = unit;
        db->mru = mru;
        db->hsize = hsize;
        db->hshift = hshift;
        db->maxmaxcode = maxmaxcode;
        db->clear_count = -1;

        pf_bsd_clear(db);

        return db;
}


/* compress a packet
 *      Assume the protocol is known to be >= 0x21 and < 0xff.



Schryver                     Informational                     [Page 13]

RFC 1977                    PPP BSD Compress                 August 1996


 *      One change from the BSD compress command is that when the
 *      code size expands, we do not output a bunch of padding.
 */
int                                     /* new slen */
pf_bsd_comp(struct bsd_db *db,
            u_char *cp_buf,             /* compress into here */
            int proto,                  /* this original PPP protocol */
            struct mbuf *m,             /* from here */
            int slen)
{
        register int hshift = db->hshift;
        register u_int max_ent = db->max_ent;
        register u_int n_bits = db->n_bits;
        register u_int bitno = 32;
        register __uint32_t accum = 0;
        register struct bsd_dict *dictp;
        register __uint32_t fcode;
        register u_char c;
        register int hval, disp, ent;
        register u_char *rptr, *wptr;
        struct mbuf *n;

#define OUTPUT(ent) {                   \
        bitno -= n_bits;                \
        accum |= ((ent) << bitno);      \
        do {                            \
                *wptr++ = accum>>24;    \
                accum <<= 8;            \
                bitno += 8;             \
        } while (bitno <= 24);          \
        }


        /* start with the protocol byte */
        ent = proto;
        db->in_count++;

        /* install sequence number */
        cp_buf[0] = db->seqno>>8;
        cp_buf[1] = db->seqno;
        db->seqno++;

        wptr = &cp_buf[2];
        slen = m->m_len;
        db->in_count += slen;
        rptr = mtod(m, u_char*);
        n = m->m_next;
        for (;;) {



Schryver                     Informational                     [Page 14]

RFC 1977                    PPP BSD Compress                 August 1996


                if (slen == 0) {
                        if (!n)
                                break;
                        slen = n->m_len;
                        rptr = mtod(n, u_char*);
                        n = n->m_next;
                        if (!slen)
                                continue;   /* handle 0-length buffers*/
                        db->in_count += slen;
                }

                slen--;
                c = *rptr++;
                fcode = BSD_KEY(ent,c);
                hval = BSD_HASH(ent,c,hshift);
                dictp = &db->dict[hval];

                /* Validate and then check the entry. */
                if (dictp->codem1 >= max_ent)
                        goto nomatch;
                if (dictp->f.fcode == fcode) {
                        ent = dictp->codem1+1;
                        continue;       /* found (prefix,suffix) */
                }

                /* continue probing until a match or invalid entry */
                disp = (hval == 0) ? 1 : hval;
                do {
                        hval += disp;
                        if (hval >= db->hsize)
                                hval -= db->hsize;
                        dictp = &db->dict[hval];
                        if (dictp->codem1 >= max_ent)
                                goto nomatch;
                } while (dictp->f.fcode != fcode);
                ent = dictp->codem1+1;  /* found (prefix,suffix) */
                continue;

nomatch:
                OUTPUT(ent);            /* output the prefix */

                /* code -> hashtable */
                if (max_ent < db->maxmaxcode) {
                        struct bsd_dict *dictp2;
                        /* expand code size if needed */
                        if (max_ent >= MAXCODE(n_bits))
                                db->n_bits = ++n_bits;




Schryver                     Informational                     [Page 15]

RFC 1977                    PPP BSD Compress                 August 1996


                        /* Invalidate old hash table entry using
                         * this code, and then take it over.
                         */
                        dictp2 = &db->dict[max_ent+1];
                        if (db->dict[dictp2->cptr].codem1 == max_ent)
                                db->dict[dictp2->cptr].codem1=BADCODEM1;
                        dictp2->cptr = hval;
                        dictp->codem1 = max_ent;
                        dictp->f.fcode = fcode;

                        db->max_ent = ++max_ent;
                }
                ent = c;
        }

        OUTPUT(ent);                    /* output the last code */
        db->bytes_out += (wptr-&cp_buf[2]   /* count complete bytes */
                          + (32-bitno+7)/8);

        if (pf_bsd_check(db))
                OUTPUT(CLEAR);          /* do not count the CLEAR */

        /* Pad dribble bits of last code with ones.
         * Do not emit a completely useless byte of ones.
         */
        if (bitno != 32)
                *wptr++ = (accum | (0xff << (bitno-8))) >> 24;

        /* Increase code size if we would have without the packet
         * boundary and as the decompressor will.
         */
        if (max_ent >= MAXCODE(n_bits)
            && max_ent < db->maxmaxcode)
                db->n_bits++;

        return (wptr - cp_buf);
#undef OUTPUT
}


/* Update the "BSD Compress" dictionary on the receiver for
 * incompressible data by pretending to compress the incoming data.
 */
void
pf_bsd_incomp(struct bsd_db *db,
              mblk_t *dmsg,
              u_int ent)                /* start with protocol byte */
{



Schryver                     Informational                     [Page 16]

RFC 1977                    PPP BSD Compress                 August 1996


        register u_int hshift = db->hshift;
        register u_int max_ent = db->max_ent;
        register u_int n_bits = db->n_bits;
        register struct bsd_dict *dictp;
        register __uint32_t fcode;
        register u_char c;
        register int hval, disp;
        register int slen;
        register u_int bitno = 7;
        register u_char *rptr;

        db->incomp_count++;

        db->in_count++;                 /* count protocol as 1 byte */
        db->seqno++;
        rptr = dmsg->b_rptr+PPP_BUF_HEAD_INFO;
        for (;;) {
                slen = dmsg->b_wptr - rptr;
                if (slen == 0) {
                        dmsg = dmsg->b_cont;
                        if (!dmsg)
                                break;
                        rptr = dmsg->b_rptr;
                        continue;       /* skip zero-length buffers */
                }
                db->in_count += slen;

                do {
                        c = *rptr++;
                        fcode = BSD_KEY(ent,c);
                        hval = BSD_HASH(ent,c,hshift);
                        dictp = &db->dict[hval];

                        /* validate and then check the entry */
                        if (dictp->codem1 >= max_ent)
                                goto nomatch;
                        if (dictp->f.fcode == fcode) {
                                ent = dictp->codem1+1;
                                continue;   /* found (prefix,suffix) */
                        }

                        /* continue until match or invalid entry */
                        disp = (hval == 0) ? 1 : hval;
                        do {
                                hval += disp;
                                if (hval >= db->hsize)
                                        hval -= db->hsize;
                                dictp = &db->dict[hval];



Schryver                     Informational                     [Page 17]

RFC 1977                    PPP BSD Compress                 August 1996


                                if (dictp->codem1 >= max_ent)
                                        goto nomatch;
                        } while (dictp->f.fcode != fcode);
                        ent = dictp->codem1+1;
                        continue;       /* found (prefix,suffix) */

nomatch:                                /* output (count) the prefix */
                        bitno += n_bits;

                        /* code -> hashtable */
                        if (max_ent < db->maxmaxcode) {
                            struct bsd_dict *dictp2;
                            /* expand code size if needed */
                            if (max_ent >= MAXCODE(n_bits))
                                    db->n_bits = ++n_bits;
                            /* Invalidate previous hash table entry
                             * assigned this code, and then take it over
                             */
                            dictp2 = &db->dict[max_ent+1];
                            if (db->dict[dictp2->cptr].codem1==max_ent)
                                db->dict[dictp2->cptr].codem1=BADCODEM1;
                            dictp2->cptr = hval;
                            dictp->codem1 = max_ent;
                            dictp->f.fcode = fcode;

                            db->max_ent = ++max_ent;
                            db->lens[max_ent] = db->lens[ent]+1;
                        }
                        ent = c;
                } while (--slen != 0);
        }
        bitno += n_bits;                /* output (count) last code */
        db->bytes_out += bitno/8;

        (void)pf_bsd_check(db);

        /* Increase code size if we would have without the packet
         * boundary and as the decompressor will.
         */
        if (max_ent >= MAXCODE(n_bits)
            && max_ent < db->maxmaxcode)
                db->n_bits++;
}


/* Decompress "BSD Compress"
 */
mblk_t*                                 /* 0=failed, so zap CCP */



Schryver                     Informational                     [Page 18]

RFC 1977                    PPP BSD Compress                 August 1996


pf_bsd_decomp(struct bsd_db *db,
              mblk_t *cmsg)
{
        register u_int max_ent = db->max_ent;
        register __uint32_t accum = 0;
        register u_int bitno = 32;      /* 1st valid bit in accum */
        register u_int n_bits = db->n_bits;
        register u_int tgtbitno = 32-n_bits; /* bitno when accum full */
        register struct bsd_dict *dictp;
        register int explen, i;
        register u_int incode, oldcode, finchar;
        register u_char *p, *rptr, *rptr9, *wptr0, *wptr;
        mblk_t *dmsg, *dmsg1, *bp;

        db->decomp_count++;
        rptr = cmsg->b_rptr;
        ASSERT(cmsg->b_wptr >= rptr+PPP_BUF_MIN);
        ASSERT(PPP_BUF_ALIGN(rptr));
        rptr += PPP_BUF_MIN;

        /* get the sequence number */
        i = 0;
        explen = 2;
        do {
                while (rptr >= cmsg->b_wptr) {
                        bp = cmsg;
                        cmsg = cmsg->b_cont;
                        freeb(bp);
                        if (!cmsg) {
                                if (db->debug)
                                        printf("bsd_decomp%d: missing"
                                               " %d header bytes\n",
                                               db->unit, explen);
                                return 0;
                        }
                        rptr = cmsg->b_rptr;
                }
                i = (i << 8) + *rptr++;
        } while (--explen != 0);