Subversion Repositories openrisc

//==========================================================================

//

//      src/bsd_comp.c

//

//==========================================================================

// ####ECOSGPLCOPYRIGHTBEGIN####                                            

// -------------------------------------------                              

// This file is part of eCos, the Embedded Configurable Operating System.   

// Copyright (C) 2003 Free Software Foundation, Inc.                        

//

// eCos is free software; you can redistribute it and/or modify it under    

// the terms of the GNU General Public License as published by the Free     

// Software Foundation; either version 2 or (at your option) any later      

// version.                                                                 

//

// eCos is distributed in the hope that it will be useful, but WITHOUT      

// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or    

// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License    

// for more details.                                                        

//

// You should have received a copy of the GNU General Public License        

// along with eCos; if not, write to the Free Software Foundation, Inc.,    

// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.            

//

// As a special exception, if other files instantiate templates or use      

// macros or inline functions from this file, or you compile this file      

// and link it with other works to produce a work based on this file,       

// this file does not by itself cause the resulting work to be covered by   

// the GNU General Public License. However the source code for this file    

// must still be made available in accordance with section (3) of the GNU   

// General Public License v2.                                               

//

// This exception does not invalidate any other reasons why a work based    

// on this file might be covered by the GNU General Public License.         

// -------------------------------------------                              

// ####ECOSGPLCOPYRIGHTEND####                                              

// ####BSDALTCOPYRIGHTBEGIN####                                             

// -------------------------------------------                              

// Portions of this software may have been derived from FreeBSD, OpenBSD,   

// or other sources, and if so are covered by the appropriate copyright     

// and license included herein.                                             

// -------------------------------------------                              

// ####BSDALTCOPYRIGHTEND####                                               

//==========================================================================

/* 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. 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.

 */

/*

 * This version is for use with mbufs on BSD-derived systems.

 *

 * $FreeBSD: src/sys/net/bsd_comp.c,v 1.11 1999/08/28 00:48:14 peter Exp $

 */

#define _KERNEL

#include <sys/param.h>

//#include <sys/systm.h>

#include <sys/malloc.h>

#include <sys/mbuf.h>

#include <cyg/ppp/net/ppp_defs.h>

#define PACKETPTR       struct mbuf *

#include <cyg/ppp/net/ppp_comp.h>

#if DO_BSD_COMPRESS

/*

 * 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.

 */

/*

 * A dictionary for doing BSD compress.

 */

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  maxbits;

    u_char  debug;

    u_char  unit;

    u_int16_t seqno;                    /* sequence # of next packet */

    u_int   hdrlen;                     /* header length to preallocate */

    u_int   mru;

    u_int   maxmaxcode;                 /* largest valid code */

    u_int   max_ent;                    /* largest code in use */

    u_int   in_count;                   /* uncompressed bytes, aged */

    u_int   bytes_out;                  /* compressed bytes, aged */

    u_int   ratio;                      /* recent compression ratio */

    u_int   checkpoint;                 /* when to next check the ratio */

    u_int   clear_count;                /* times dictionary cleared */

    u_int   incomp_count;               /* incompressible packets */

    u_int   incomp_bytes;               /* incompressible bytes */

    u_int   uncomp_count;               /* uncompressed packets */

    u_int   uncomp_bytes;               /* uncompressed bytes */

    u_int   comp_count;                 /* compressed packets */

    u_int   comp_bytes;                 /* compressed bytes */

    u_int16_t *lens;                    /* array of lengths of codes */

    struct bsd_dict {

        union {                         /* hash value */

            u_int32_t   fcode;

            struct {

#if BYTE_ORDER == LITTLE_ENDIAN

                u_int16_t 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_int16_t prefix;       /* preceding code */

#endif

            } hs;

        } f;

        u_int16_t codem1;               /* output of hash table -1 */

        u_int16_t cptr;                 /* map code to hash table entry */

    } dict[1];

};

#define BSD_OVHD        2               /* BSD compress overhead/packet */

#define BSD_INIT_BITS   BSD_MIN_BITS

static void     bsd_clear __P((struct bsd_db *db));

static int      bsd_check __P((struct bsd_db *db));

static void     *bsd_alloc __P((u_char *options, int opt_len, int decomp));

static int      bsd_init __P((struct bsd_db *db, u_char *options, int opt_len,

                              int unit, int hdrlen, int mru, int debug,

                              int decomp));

static void     *bsd_comp_alloc __P((u_char *options, int opt_len));

static void     *bsd_decomp_alloc __P((u_char *options, int opt_len));

static void     bsd_free __P((void *state));

static int      bsd_comp_init __P((void *state, u_char *options, int opt_len,

                                   int unit, int hdrlen, int debug));

static int      bsd_decomp_init __P((void *state, u_char *options, int opt_len,

                                     int unit, int hdrlen, int mru, int debug));

static int      bsd_compress __P((void *state, struct mbuf **mret,

                                  struct mbuf *mp, int slen, int maxolen));

static void     bsd_incomp __P((void *state, struct mbuf *dmsg));

static int      bsd_decompress __P((void *state, struct mbuf *cmp,

                                    struct mbuf **dmpp));

static void     bsd_reset __P((void *state));

static void     bsd_comp_stats __P((void *state, struct compstat *stats));

/*

 * Procedures exported to if_ppp.c.

 */

struct compressor ppp_bsd_compress = {

    CI_BSD_COMPRESS,            /* compress_proto */

    bsd_comp_alloc,             /* comp_alloc */

    bsd_free,                   /* comp_free */

    bsd_comp_init,              /* comp_init */

    bsd_reset,                  /* comp_reset */

    bsd_compress,               /* compress */

    bsd_comp_stats,             /* comp_stat */

    bsd_decomp_alloc,           /* decomp_alloc */

    bsd_free,                   /* decomp_free */

    bsd_decomp_init,            /* decomp_init */

    bsd_reset,                  /* decomp_reset */

    bsd_decompress,             /* decompress */

    bsd_incomp,                 /* incomp */

    bsd_comp_stats,             /* decomp_stat */

};

/*

 * 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 MAXCODE(b)      ((1 << (b)) - 1)

#define BADCODEM1       MAXCODE(BSD_MAX_BITS)

#define BSD_HASH(prefix,suffix,hshift)  ((((u_int32_t)(suffix)) << (hshift)) \

                                         ^ (u_int32_t)(prefix))

#define BSD_KEY(prefix,suffix)          ((((u_int32_t)(suffix)) << 16) \

                                         + (u_int32_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

bsd_clear(db)

    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->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.

 *

 * 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 */

bsd_check(db)

    struct bsd_db *db;

{

    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) {

                bsd_clear(db);

                return 1;

            }

            db->ratio = new_ratio;

        }

    }

    return 0;

}

/*

 * Return statistics.

 */

static void

bsd_comp_stats(state, stats)

    void *state;

    struct compstat *stats;

{

    struct bsd_db *db = (struct bsd_db *) state;

    u_int out;

    stats->unc_bytes = db->uncomp_bytes;

    stats->unc_packets = db->uncomp_count;

    stats->comp_bytes = db->comp_bytes;

    stats->comp_packets = db->comp_count;

    stats->inc_bytes = db->incomp_bytes;

    stats->inc_packets = db->incomp_count;

    stats->ratio = db->in_count;

    out = db->bytes_out;

    if (stats->ratio <= 0x7fffff)

        stats->ratio <<= 8;

    else

        out >>= 8;

    if (out != 0)

        stats->ratio /= out;

}

/*

 * Reset state, as on a CCP ResetReq.

 */

static void

bsd_reset(state)

    void *state;

{

    struct bsd_db *db = (struct bsd_db *) state;

    db->seqno = 0;

    bsd_clear(db);

    db->clear_count = 0;

}

/*

 * Allocate space for a (de) compressor.

 */

static void *

bsd_alloc(options, opt_len, decomp)

    u_char *options;

    int opt_len, decomp;

{

    int bits;

    u_int newlen, hsize, hshift, maxmaxcode;

    struct bsd_db *db;

    if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS

        || options[1] != CILEN_BSD_COMPRESS

        || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION)

        return NULL;

    bits = BSD_NBITS(options[2]);

    switch (bits) {

    case 9:                     /* needs 82152 for both directions */

    case 10:                    /* needs 84144 */

    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 cptr */

        /* hshift = 8; */       /* in struct bsd_db */

        /* break; */

    default:

        return NULL;

    }

    maxmaxcode = MAXCODE(bits);

    newlen = sizeof(*db) + (hsize-1) * (sizeof(db->dict[0]));

    MALLOC(db, struct bsd_db *, newlen, M_DEVBUF, M_NOWAIT);

    if (!db)

        return NULL;

    bzero(db, sizeof(*db) - sizeof(db->dict));

    if (!decomp) {

        db->lens = NULL;

    } else {

        MALLOC(db->lens, u_int16_t *, (maxmaxcode+1) * sizeof(db->lens[0]),

               M_DEVBUF, M_NOWAIT);

        if (!db->lens) {

            FREE(db, M_DEVBUF);

            return NULL;

        }

    }

    db->totlen = newlen;

    db->hsize = hsize;

    db->hshift = hshift;

    db->maxmaxcode = maxmaxcode;

    db->maxbits = bits;

    return (void *) db;

}

static void

bsd_free(state)

    void *state;

{

    struct bsd_db *db = (struct bsd_db *) state;

    if (db->lens)

        FREE(db->lens, M_DEVBUF);

    FREE(db, M_DEVBUF);

}

static void *

bsd_comp_alloc(options, opt_len)

    u_char *options;

    int opt_len;

{

    return bsd_alloc(options, opt_len, 0);

}

static void *

bsd_decomp_alloc(options, opt_len)

    u_char *options;

    int opt_len;

{

    return bsd_alloc(options, opt_len, 1);

}

/*

 * Initialize the database.

 */

static int

bsd_init(db, options, opt_len, unit, hdrlen, mru, debug, decomp)

    struct bsd_db *db;

    u_char *options;

    int opt_len, unit, hdrlen, mru, debug, decomp;

{

    int i;

    if (opt_len < CILEN_BSD_COMPRESS || options[0] != CI_BSD_COMPRESS

        || options[1] != CILEN_BSD_COMPRESS

        || BSD_VERSION(options[2]) != BSD_CURRENT_VERSION

        || BSD_NBITS(options[2]) != db->maxbits

        || (decomp && db->lens == NULL))

        return 0;

    if (decomp) {

        i = LAST+1;

        while (i != 0)

            db->lens[--i] = 1;

    }

    i = db->hsize;

    while (i != 0) {

        db->dict[--i].codem1 = BADCODEM1;

        db->dict[i].cptr = 0;

    }

    db->unit = unit;

    db->hdrlen = hdrlen;

    db->mru = mru;

#ifndef DEBUG

    if (debug)

#endif

        db->debug = 1;

    bsd_reset(db);

    return 1;

}

static int

bsd_comp_init(state, options, opt_len, unit, hdrlen, debug)

    void *state;

    u_char *options;

    int opt_len, unit, hdrlen, debug;

{

    return bsd_init((struct bsd_db *) state, options, opt_len,

                    unit, hdrlen, 0, debug, 0);

}

static int

bsd_decomp_init(state, options, opt_len, unit, hdrlen, mru, debug)

    void *state;

    u_char *options;

    int opt_len, unit, hdrlen, mru, debug;

{

    return bsd_init((struct bsd_db *) state, options, opt_len,

                    unit, hdrlen, mru, debug, 1);

}

/*

 * compress a packet

 *      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 */

bsd_compress(state, mret, mp, slen, maxolen)

    void *state;

    struct mbuf **mret;         /* return compressed mbuf chain here */

    struct mbuf *mp;            /* from here */

    int slen;                   /* uncompressed length */

    int maxolen;                /* max compressed length */

{

    struct bsd_db *db = (struct bsd_db *) state;

    int hshift = db->hshift;

    u_int max_ent = db->max_ent;

    u_int n_bits = db->n_bits;

    u_int bitno = 32;

    u_int32_t accm = 0, fcode;

    struct bsd_dict *dictp;

    u_char c;

    int hval, disp, ent, ilen;

    u_char *rptr, *wptr;

    u_char *cp_end;

    int olen;

    struct mbuf *m;

#define PUTBYTE(v) {                                    \

    ++olen;                                             \

    if (wptr) {                                         \

        *wptr++ = (v);                                  \

        if (wptr >= cp_end) {                           \

            m->m_len = wptr - mtod(m, u_char *);        \

            MGET(m->m_next, M_DONTWAIT, MT_DATA);       \

            m = m->m_next;                              \

            if (m) {                                    \

                m->m_len = 0;                            \

                if (maxolen - olen > MLEN)              \

                    MCLGET(m, M_DONTWAIT);              \

                wptr = mtod(m, u_char *);               \

                cp_end = wptr + M_TRAILINGSPACE(m);     \

            } else                                      \

                wptr = NULL;                            \

        }                                               \

    }                                                   \

}

#define OUTPUT(ent) {                                   \

    bitno -= n_bits;                                    \

    accm |= ((ent) << bitno);                           \

    do {                                                \

        PUTBYTE(accm >> 24);                            \

        accm <<= 8;                                     \

        bitno += 8;                                     \

    } while (bitno <= 24);                              \

}

    /*

     * If the protocol is not in the range we're interested in,

     * just return without compressing the packet.  If it is,

     * the protocol becomes the first byte to compress.

     */

    rptr = mtod(mp, u_char *);

    ent = PPP_PROTOCOL(rptr);

    if (ent < 0x21 || ent > 0xf9) {

        *mret = NULL;

        return slen;

    }

    /* Don't generate compressed packets which are larger than

       the uncompressed packet. */

    if (maxolen > slen)

        maxolen = slen;

    /* Allocate one mbuf to start with. */

    MGET(m, M_DONTWAIT, MT_DATA);

    *mret = m;

    if (m != NULL) {

        m->m_len = 0;

        if (maxolen + db->hdrlen > MLEN)

            MCLGET(m, M_DONTWAIT);

        m->m_data += db->hdrlen;

        wptr = mtod(m, u_char *);

        cp_end = wptr + M_TRAILINGSPACE(m);

    } else

        wptr = cp_end = NULL;

    /*

     * Copy the PPP header over, changing the protocol,

     * and install the 2-byte packet sequence number.

     */

    if (wptr) {

        *wptr++ = PPP_ADDRESS(rptr);    /* assumes the ppp header is */

        *wptr++ = PPP_CONTROL(rptr);    /* all in one mbuf */

        *wptr++ = 0;                     /* change the protocol */

        *wptr++ = PPP_COMP;

        *wptr++ = db->seqno >> 8;

        *wptr++ = db->seqno;

    }

    ++db->seqno;

    olen = 0;

    rptr += PPP_HDRLEN;

    slen = mp->m_len - PPP_HDRLEN;

    ilen = slen + 1;

    for (;;) {

        if (slen <= 0) {

            mp = mp->m_next;

            if (!mp)

                break;

            rptr = mtod(mp, u_char *);

            slen = mp->m_len;

            if (!slen)

                continue;   /* handle 0-length buffers */

            ilen += 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;        /* finally 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;

            /* 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 += olen;

    db->in_count += ilen;

    if (bitno < 32)

        ++db->bytes_out;        /* count complete bytes */

    if (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)

        PUTBYTE((accm | (0xff << (bitno-8))) >> 24);

    if (m != NULL) {

        m->m_len = wptr - mtod(m, u_char *);