📄 rfc1977.txt
字号:
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;
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 */
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);
if (i != db->seqno++) {
freemsg(cmsg);
if (db->debug)
printf("bsd_decomp%d: bad sequence number 0x%x"
" instead of 0x%x\n",
db->unit, i, db->seqno-1);
return 0;
}
/* Guess how much memory we will need. Assume this packet was
* compressed by at least 1.5X regardless of the recent ratio.
*/
if (db->ratio > (RATIO_SCALE*3)/2)
explen = (msgdsize(cmsg)*db->ratio)/RATIO_SCALE;
else
explen = (msgdsize(cmsg)*3)/2;
if (explen > db->mru)
explen = db->mru;
dmsg = dmsg1 = allocb(explen+PPP_BUF_HEAD_INFO, BPRI_HI);
if (!dmsg1) {
freemsg(cmsg);
return 0;
}
wptr = dmsg1->b_wptr;
((struct ppp_buf*)wptr)->type = BEEP_FRAME;
/* the protocol field must be compressed */
((struct ppp_buf*)wptr)->proto = 0;
wptr += PPP_BUF_HEAD_PROTO+1;
rptr9 = cmsg->b_wptr;
db->bytes_out += rptr9-rptr;
wptr0 = wptr;
explen = dmsg1->b_datap->db_lim - wptr;
oldcode = CLEAR;
for (;;) {
if (rptr >= rptr9) {
bp = cmsg;
cmsg = cmsg->b_cont;
freeb(bp);
if (!cmsg) /* quit at end of message */
break;
rptr = cmsg->b_rptr;
rptr9 = cmsg->b_wptr;
db->bytes_out += rptr9-rptr;
continue; /* handle 0-length buffers */
}
/* Accumulate bytes until we have a complete code.
* Then get the next code, relying on the 32-bit,
* unsigned accum to mask the result.
*/
bitno -= 8;
accum |= *rptr++ << bitno;
if (tgtbitno < bitno)
continue;
incode = accum >> tgtbitno;
accum <<= n_bits;
bitno += n_bits;
if (incode == CLEAR) {
/* The dictionary must only be cleared at
* the end of a packet. But there could be an
* empty message block at the end.
*/
if (rptr != rptr9
|| cmsg->b_cont != 0) {
cmsg->b_rptr = rptr;
i = msgdsize(cmsg);
if (i != 0) {
freemsg(dmsg);
freemsg(cmsg);
if (db->debug)
printf("bsd_decomp%d: "
"bad CLEAR\n",
db->unit);
return 0;
}
}
pf_bsd_clear(db);
freemsg(cmsg);
wptr0 = wptr;
break;
}
/* Special case for KwKwK string. */
if (incode > max_ent) {
if (incode > max_ent+2
|| incode > db->maxmaxcode
|| oldcode == CLEAR) {
freemsg(dmsg);
freemsg(cmsg);
if (db->debug)
printf("bsd_decomp%d: bad code %x\n",
db->unit, incode);
return 0;
}
i = db->lens[oldcode];
/* do not write past end of buf */
explen -= i+1;
if (explen < 0) {
db->undershoot -= explen;
db->in_count += wptr-wptr0;
dmsg1->b_wptr = wptr;
CK_WPTR(dmsg1);
explen = MAX(64,i+1);
bp = allocb(explen, BPRI_HI);
if (!bp) {
freemsg(cmsg);
freemsg(dmsg);
return 0;
}
dmsg1->b_cont = bp;
dmsg1 = bp;
wptr0 = wptr = dmsg1->b_wptr;
explen=dmsg1->b_datap->db_lim-wptr-(i+1);
}
p = (wptr += i);
*wptr++ = finchar;
finchar = oldcode;
} else {
i = db->lens[finchar = incode];
explen -= i;
if (explen < 0) {
db->undershoot -= explen;
db->in_count += wptr-wptr0;
dmsg1->b_wptr = wptr;
CK_WPTR(dmsg1);
explen = MAX(64,i);
bp = allocb(explen, BPRI_HI);
if (!bp) {
freemsg(dmsg);
freemsg(cmsg);
return 0;
}
dmsg1->b_cont = bp;
dmsg1 = bp;
wptr0 = wptr = dmsg1->b_wptr;
explen = dmsg1->b_datap->db_lim-wptr-i;
}
p = (wptr += i);
}
/* decode code and install in decompressed buffer */
while (finchar > LAST) {
dictp = &db->dict[db->dict[finchar].cptr];
*--p = dictp->f.hs.suffix;
finchar = dictp->f.hs.prefix;
}
*--p = finchar;
/* If not first code in a packet, and
* if not out of code space, then allocate a new code.
*
* Keep the hash table correct so it can be used
* with uncompressed packets.
*/
if (oldcode != CLEAR
&& max_ent < db->maxmaxcode) {
struct bsd_dict *dictp2;
__uint32_t fcode;
int hval, disp;
fcode = BSD_KEY(oldcode,finchar);
hval = BSD_HASH(oldcode,finchar,db->hshift);
dictp = &db->dict[hval];
/* look for a free hash table entry */
if (dictp->codem1 < max_ent) {
disp = (hval == 0) ? 1 : hval;
do {
hval += disp;
if (hval >= db->hsize)
hval -= db->hsize;
dictp = &db->dict[hval];
} while (dictp->codem1 < max_ent);
}
/* 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[oldcode]+1;
/* Expand code size if needed.
*/
if (max_ent >= MAXCODE(n_bits)
&& max_ent < db->maxmaxcode) {
db->n_bits = ++n_bits;
tgtbitno = 32-n_bits;
}
}
oldcode = incode;
}
db->in_count += wptr-wptr0;
dmsg1->b_wptr = wptr;
CK_WPTR(dmsg1);
db->overshoot += explen;
/* Keep the checkpoint right so that incompressible packets
* clear the dictionary at the right times.
*/
if (pf_bsd_check(db)
&& db->debug) {
printf("bsd_decomp%d: peer should have "
"cleared dictionary\n", db->unit);
}
return dmsg;
}
安全考虑
Security issues are not discussed in this memo.
参考文献
[1] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51,
RFC 1661, July 1994.
[2] Rand, D., "The PPP Compression Control Protocol (CCP)", RFC
1962, June 1996.
[3] Simpson, W., "PPP LCP Extensions", RFC 1570, January 1994.
[4] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662,
July 1994.
致谢
William Simpson provided and supported the very valuable idea of not
using any additional header bytes for incompressible packets.
主席地址
The working group can be contacted via the current chair:
Karl Fox
Ascend Communications
3518 Riverside Drive, Suite 101
Columbus, Ohio 43221
EMail: karl@ascend.com
作者地址
Questions about this memo can also be directed to:
Vernon Schryver
2482 Lee Hill Drive
Boulder, Colorado 80302
EMail: vjs@rhyolite.com
RFC1977——PPP BSD Compression Protocol PPP BSD 压缩协议
1
RFC文档中文翻译计划
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -