rfc1977.txt

改文件中包含了三个协议

      of using a Configure-Nak to ask the peer to specify a larger
      dictionary.

A.  BSD Compress Algorithm

   This code is the core of a commercial workstation implementation.  It
   was derived by transliterating the 4.*BSD compress command.  It is
   unlikely to be of direct use in any system that does not have the
   same mixture of mbufs and STREAMS buffers.  It may need to be retuned
   for CPU's other than RISC's with many registers and certain
   addressing modes.  However, the code is the most accurate and
   unambiguous way of defining the changes to the BSD compress source
   required to apply it to a stream instead of a file.

   Note that it assumes a "short" contains 16 bits and an "int" contains
   at least 32 bits.  Where it would matter if more than 32 bits were in
   an "int" or "long," __uint32_t is used instead.

/* Because this code is derived from the 4.3BSD compress source:
 *
 *
 * Copyright (c) 1985, 1986 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * James A. Woods, derived from original work by Spencer Thomas
 * and Joseph Orost.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 * 3. All advertising materials mentioning features or use of this
 *    software must display the following acknowledgement:



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


 *      This product includes software developed by the University of
 *      California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


/* ***************** */

struct bsd_db {
    int     totlen;                     /* length of this structure */
    u_int   hsize;                      /* size of the hash table */
    u_char  hshift;                     /* used in hash function */
    u_char  n_bits;                     /* current bits/code */
    u_char  debug;
    u_char  unit;
    u_short mru;
    u_short seqno;                      /* # of last byte of packet */
    u_int   maxmaxcode;                 /* largest valid code */
    u_int   max_ent;                    /* largest code in use */
    u_int   in_count;                   /* uncompressed bytes */
    u_int   bytes_out;                  /* compressed bytes */
    u_int   ratio;                      /* recent compression ratio */
    u_int   checkpoint;                 /* when to next check ratio */
    int     clear_count;                /* times dictionary cleared */
    int     incomp_count;               /* incompressible packets */
    int     decomp_count;               /* packets decompressed */
    int     overshoot;                  /* excess decompression buf */
    int     undershoot;                 /* insufficient decomp. buf */
    u_short *lens;                      /* array of lengths of codes */
    struct bsd_dict {
        union {                         /* hash value */
            __uint32_t  fcode;
            struct {
#ifdef BSD_LITTLE_ENDIAN



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


                u_short prefix;         /* preceding code */
                u_char  suffix;         /* last character of new code */
                u_char  pad;
#else
                u_char  pad;
                u_char  suffix;         /* last character of new code */
                u_short prefix;         /* preceding code */
#endif
            } hs;
        } f;
        u_short codem1;                 /* output of hash table -1 */
        u_short cptr;                   /* map code to hash table */
    } dict[1];
};
#define BSD_OVHD (2+2)                  /* overhead/packet */
#define MIN_BSD_BITS    9
#define MAX_BSD_BITS    15              /* implementation limit */
#define BSD_VERS        1               /* when shifted */
#ifdef _KERNEL
extern struct bsd_db *pf_bsd_init(struct bsd_db*, int, int, int);
extern int pf_bsd_comp(struct bsd_db*,u_char*,int,struct mbuf*,int);
extern mblk_t* pf_bsd_decomp(struct bsd_db*, mblk_t*);
extern void pf_bsd_incomp(struct bsd_db*, mblk_t*, u_int);
#endif


/* ***************** */
/* PPP "BSD compress" compression
 *  The differences between this compression and the classic BSD LZW
 *  source are obvious from the requirement that the classic code worked
 *  with files while this handles arbitrarily long streams that
 *  are broken into packets.  They are:
 *
 *      When the code size expands, a block of junk is not emitted by
 *          the compressor and not expected by the decompressor.
 *
 *      New codes are not necessarily assigned every time an old
 *          code is output by the compressor.  This is because a packet
 *          end forces a code to be emitted, but does not imply that a
 *          new sequence has been seen.
 *
 *      The compression ratio is checked at the first end of a packet
 *          after the appropriate gap.  Besides simplifying and speeding
 *          things up, this makes it more likely that the transmitter
 *          and receiver will agree when the dictionary is cleared when
 *          compression is not going well.
 */




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


/*
 * the next two codes should not be changed lightly, as they must not
 * lie within the contiguous general code space.
 */
#define CLEAR   256                     /* table clear output code */
#define FIRST   257                     /* first free entry */
#define LAST    255

#define BSD_INIT_BITS   MIN_BSD_BITS

#define MAXCODE(b) ((1 << (b)) - 1)
#define BADCODEM1 MAXCODE(MAX_BSD_BITS);

#define BSD_HASH(prefix,suffix,hshift) ((((__uint32_t)(suffix)) \
                                         << (hshift)) \
                                        ^ (__uint32_t)(prefix))
#define BSD_KEY(prefix,suffix) ((((__uint32_t)(suffix)) << 16)  \
                                + (__uint32_t)(prefix))

#define CHECK_GAP       10000           /* Ratio check interval */

#define RATIO_SCALE_LOG 8
#define RATIO_SCALE     (1<<RATIO_SCALE_LOG)
#define RATIO_MAX       (0x7fffffff>>RATIO_SCALE_LOG)

/* clear the dictionary
 */
static void
pf_bsd_clear(struct bsd_db *db)
{
        db->clear_count++;
        db->max_ent = FIRST-1;
        db->n_bits = BSD_INIT_BITS;
        db->ratio = 0;
        db->bytes_out = 0;
        db->in_count = 0;
        db->incomp_count = 0;
        db->decomp_count = 0;
        db->overshoot = 0;
        db->undershoot = 0;
        db->checkpoint = CHECK_GAP;
}


/* If the dictionary is full, then see if it is time to reset it.
 *
 * Compute the compression ratio using fixed-point arithmetic
 * with 8 fractional bits.



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


 *
 * Since we have an infinite stream instead of a single file,
 * watch only the local compression ratio.
 *
 * Since both peers must reset the dictionary at the same time even in
 * the absence of CLEAR codes (while packets are incompressible), they
 * must compute the same ratio.
 */
static int                              /* 1=output CLEAR */
pf_bsd_check(struct bsd_db *db)
{
        register u_int new_ratio;

        if (db->in_count >= db->checkpoint) {
                /* age the ratio by limiting the size of the counts */
                if (db->in_count >= RATIO_MAX
                    || db->bytes_out >= RATIO_MAX) {
                        db->in_count -= db->in_count/4;
                        db->bytes_out -= db->bytes_out/4;
                }

                db->checkpoint = db->in_count + CHECK_GAP;

                if (db->max_ent >= db->maxmaxcode) {
                        /* Reset the dictionary only if the ratio is
                         * worse, or if it looks as if it has been
                         * poisoned by incompressible data.
                         *
                         * This does not overflow, because
                         *      db->in_count <= RATIO_MAX.
                         */
                        new_ratio = db->in_count<<RATIO_SCALE_LOG;
                        if (db->bytes_out != 0)
                                new_ratio /= db->bytes_out;

                        if (new_ratio < db->ratio
                            || new_ratio < 1*RATIO_SCALE) {
                                pf_bsd_clear(db);
                                return 1;
                        }
                        db->ratio = new_ratio;
                }
        }
        return 0;
}


/* Initialize the database.



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


 */
struct bsd_db *
pf_bsd_init(struct bsd_db *db,          /* initialize this database */
            int unit,                   /* for debugging */
            int bits,                   /* size of LZW code word */
            int mru)                    /* MRU for input, 0 for output*/
{
        register int i;
        register u_short *lens;
        register u_int newlen, hsize, hshift, maxmaxcode;

        switch (bits) {
        case 9:                         /* needs 82152 for both comp &*/
        case 10:                        /* needs 84144          decomp*/
        case 11:                        /* needs 88240 */
        case 12:                        /* needs 96432 */
                hsize = 5003;
                hshift = 4;
                break;
        case 13:                        /* needs 176784 */
                hsize = 9001;
                hshift = 5;
                break;
        case 14:                        /* needs 353744 */
                hsize = 18013;
                hshift = 6;
                break;
        case 15:                        /* needs 691440 */
                hsize = 35023;
                hshift = 7;
                break;
        case 16:                        /* needs 1366160--far too much*/
                /* hsize = 69001; */    /* and 69001 is too big for */
                /* hshift = 8; */       /* cptr in struct bsd_db */
                /* break; */
        default:
                if (db) {
                        if (db->lens)
                                kern_free(db->lens);
                        kern_free(db);
                }
                return 0;
        }
        maxmaxcode = MAXCODE(bits);
        newlen = sizeof(*db) + (hsize-1)*(sizeof(db->dict[0]));

        if (db) {
                lens = db->lens;



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


                if (db->totlen != newlen) {
                        if (lens)
                                kern_free(lens);
                        kern_free(db);
                        db = 0;
                }
        }
        if (!db) {
                db = (struct bsd_db*)kern_malloc(newlen);
                if (!db)
                        return 0;
                if (mru == 0) {
                        lens = 0;
                } else {
                        lens = (u_short*)kern_malloc((maxmaxcode+1)
                                                     * sizeof(*lens));
                        if (!lens) {
                                kern_free(db);
                                return 0;
                        }
                        i = LAST+1;
                        while (i != 0)
                                lens[--i] = 1;
                }