bsd_comp.c

来自「eCos操作系统源码」· C语言 代码 · 共 1,161 行 · 第 1/3 页

    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 *);
	m->m_next = NULL;
    }

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

    db->uncomp_bytes += ilen;
    ++db->uncomp_count;
    if (olen + PPP_HDRLEN + BSD_OVHD > maxolen) {
	/* throw away the compressed stuff if it is longer than uncompressed */
	if (*mret != NULL) {
	    m_freem(*mret);
	    *mret = NULL;
	}
	++db->incomp_count;
	db->incomp_bytes += ilen;
    } else {
	++db->comp_count;
	db->comp_bytes += olen + BSD_OVHD;
    }

    return olen + PPP_HDRLEN + BSD_OVHD;
#undef OUTPUT
#undef PUTBYTE
}


/*
 * Update the "BSD Compress" dictionary on the receiver for
 * incompressible data by pretending to compress the incoming data.
 */
static void
bsd_incomp(state, dmsg)
    void *state;
    struct mbuf *dmsg;
{
    struct bsd_db *db = (struct bsd_db *) state;
    u_int hshift = db->hshift;
    u_int max_ent = db->max_ent;
    u_int n_bits = db->n_bits;
    struct bsd_dict *dictp;
    u_int32_t fcode;
    u_char c;
    u_int32_t hval, disp;
    int slen, ilen;
    u_int bitno = 7;
    u_char *rptr;
    u_int ent;

    /*
     * If the protocol is not in the range we're interested in,
     * just return without looking at the packet.  If it is,
     * the protocol becomes the first byte to "compress".
     */
    rptr = mtod(dmsg, u_char *);
    ent = PPP_PROTOCOL(rptr);
    if (ent < 0x21 || ent > 0xf9)
	return;

    db->seqno++;
    ilen = 1;		/* count the protocol as 1 byte */
    rptr += PPP_HDRLEN;
    slen = dmsg->m_len - PPP_HDRLEN;
    for (;;) {
	if (slen <= 0) {
	    dmsg = dmsg->m_next;
	    if (!dmsg)
		break;
	    rptr = mtod(dmsg, u_char *);
	    slen = dmsg->m_len;
	    continue;
	}
	ilen += slen;

	do {