📄 rfc1977.txt
字号:
#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.
*
* 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.
*/
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;
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;
}
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.
* 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 (;;) {
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;
/* 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 */
{
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;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -