| < draft-ietf-pppext-bsd-compress-04.txt | draft-ietf-pppext-bsd-compress-05.txt > | |||
|---|---|---|---|---|
| Network Working Group Schryver | Network Working Group Schryver | |||
| Internet Draft | Internet Draft | |||
| expires in six months May 1995 | expires in six months October 1995 | |||
| PPP BSD Compression Protocol | PPP BSD Compression Protocol | |||
| draft-ietf-pppext-bsd-compress-04.txt | draft-ietf-pppext-bsd-compress-05.txt | |||
| Status of this Memo | Status of this Memo | |||
| This document is the product of the Point-to-Point Protocol Working | This document is the product of the Point-to-Point Protocol Working | |||
| Group of the Internet Engineering Task Force (IETF). Comments should | Group of the Internet Engineering Task Force (IETF). Comments should | |||
| be submitted to the ietf-ppp@merit.edu mailing list. | be submitted to the ietf-ppp@merit.edu mailing list. | |||
| Distribution of this memo is unlimited. | Distribution of this memo is unlimited. | |||
| This document is an Internet Draft. Internet Drafts are working | This document is an Internet Draft. Internet Drafts are working | |||
| skipping to change at line 70 ¶ | skipping to change at line 70 ¶ | |||
| - an effective code width requires less than 64KBytes of memory | - an effective code width requires less than 64KBytes of memory | |||
| on both sender and receive. | on both sender and receive. | |||
| 1.1. Licensing | 1.1. Licensing | |||
| BSD Unix compress command source is widely and freely available, with | BSD Unix compress command source is widely and freely available, with | |||
| no additional license for many computer vendors. The included source | no additional license for many computer vendors. The included source | |||
| code is based on the BSD compress command source and carries only the | code is based on the BSD compress command source and carries only the | |||
| copyright of The Regents of the University of California. Use the | copyright of The Regents of the University of California. Use the | |||
| code entirely at your own risk. It has no warranties or | code entirely at your own risk. It has no warranties or | |||
| indemnifications of any sort. | indemnifications of any sort. Note that there are patents on LZW. | |||
| 2. BSD Compress Packets | 2. BSD Compress Packets | |||
| Before any BSD Compress packets may be communicated, PPP must reach | Before any BSD Compress packets may be communicated, PPP must reach | |||
| the Network-Layer Protocol phase, and the CCP Control Protocol must | the Network-Layer Protocol phase, and the CCP Control Protocol must | |||
| reach the Opened state. | reach the Opened state. | |||
| Exactly one BSD Compress datagram is encapsulated in the PPP | Exactly one BSD Compress datagram is encapsulated in the PPP | |||
| Information field, where the PPP Protocol field contains 0xFD or | Information field, where the PPP Protocol field contains 0xFD or | |||
| 0xFB. 0xFD is used when the PPP multilink protocol is not used or | 0xFB. 0xFD is used when the PPP multilink protocol is not used or | |||
| skipping to change at line 290 ¶ | skipping to change at line 290 ¶ | |||
| Dict | Dict | |||
| The size in bits of the largest code used. It can range from 9 to | The size in bits of the largest code used. It can range from 9 to | |||
| 16. A common choice is 12. The code included below can support | 16. A common choice is 12. The code included below can support | |||
| code sizes from 9 to 15. | code sizes from 9 to 15. | |||
| It is convenient to treat the byte containing the Vers and Dict | It is convenient to treat the byte containing the Vers and Dict | |||
| fields as a single field with legal values ranging from 0x29 to | fields as a single field with legal values ranging from 0x29 to | |||
| 0x30. | 0x30. | |||
| Note that the peer receiving compressed data must use the same | ||||
| code size as the peer sending data. It is not practical for the | ||||
| receiver to use a larger dictionary or code size, because both | ||||
| dictionaries must be cleared at the same time, even when the data | ||||
| is not compressible, so that uncompressed packets are being sent, | ||||
| and so the receiver cannot receive LZW "CLEAR" codes. | ||||
| When a received Configure-Request specifies a smaller dictionary | ||||
| than the local preference, it is often best to accept it instead | ||||
| of using a Configure-Nak to ask the peer to specify a larger | ||||
| dictionary. | ||||
| A. BSD Compress Algorithm | A. BSD Compress Algorithm | |||
| This code is the core of a commercial workstation implementation. It | This code is the core of a commercial workstation implementation. It | |||
| was derived by transliterating the 4.*BSD compress command. It is | 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 | 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 | 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 | for CPU's other than RISC's with many registers and certain | |||
| addressing modes. However, the code is the most accurate and | addressing modes. However, the code is the most accurate and | |||
| unambiguous way of defining the changes to the BSD compress source | unambiguous way of defining the changes to the BSD compress source | |||
| required to apply it to a stream instead of a file. | required to apply it to a stream instead of a file. | |||
| skipping to change at line 386 ¶ | skipping to change at line 398 ¶ | |||
| u_char pad; | u_char pad; | |||
| u_char suffix; /* last character of new code */ | u_char suffix; /* last character of new code */ | |||
| u_short prefix; /* preceding code */ | u_short prefix; /* preceding code */ | |||
| #endif | #endif | |||
| } hs; | } hs; | |||
| } f; | } f; | |||
| u_short codem1; /* output of hash table -1 */ | u_short codem1; /* output of hash table -1 */ | |||
| u_short cptr; /* map code to hash table entry */ | u_short cptr; /* map code to hash table entry */ | |||
| } dict[1]; | } dict[1]; | |||
| }; | }; | |||
| #define BSD_OVHD (3+2) /* BSD compress overhead/packet */ | #define BSD_OVHD (2+2) /* BSD compress overhead/packet */ | |||
| #define MIN_BSD_BITS 9 | #define MIN_BSD_BITS 9 | |||
| #define BSD_INIT_BITS MIN_BSD_BITS | #define MAX_BSD_BITS 15 /* implementation limit */ | |||
| #define MAX_BSD_BITS 15 | #define BSD_VERS 1 /* when shifted */ | |||
| #ifdef _KERNEL | ||||
| extern struct bsd_db *pf_bsd_init(struct bsd_db*, int, int, int); | 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 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 | /* PPP "BSD compress" compression | |||
| * The differences between this compression and the classic BSD LZW | * The differences between this compression and the classic BSD LZW | |||
| * source are obvious from the requirement that the classic code worked | * source are obvious from the requirement that the classic code worked | |||
| * with files while this handles arbitrarily long streams that | * with files while this handles arbitrarily long streams that | |||
| * are broken into packets. They are: | * are broken into packets. They are: | |||
| * | * | |||
| * When the code size expands, a block of junk is not emitted by | * When the code size expands, a block of junk is not emitted by | |||
| * the compressor and not expected by the decompressor. | * the compressor and not expected by the decompressor. | |||
| * | * | |||
| * New codes are not necessarily assigned every time an old | * New codes are not necessarily assigned every time an old | |||
| skipping to change at line 428 ¶ | skipping to change at line 443 ¶ | |||
| * lie within the contiguous general code space. | * lie within the contiguous general code space. | |||
| */ | */ | |||
| #define CLEAR 256 /* table clear output code */ | #define CLEAR 256 /* table clear output code */ | |||
| #define FIRST 257 /* first free entry */ | #define FIRST 257 /* first free entry */ | |||
| #define LAST 255 | #define LAST 255 | |||
| #define BSD_INIT_BITS MIN_BSD_BITS | #define BSD_INIT_BITS MIN_BSD_BITS | |||
| #define MAXCODE(b) ((1 << (b)) - 1) | #define MAXCODE(b) ((1 << (b)) - 1) | |||
| #define BADCODEM1 MAXCODE(MAX_BSD_BITS); | #define BADCODEM1 MAXCODE(MAX_BSD_BITS); | |||
| #define BSD_HASH(prefix,suffix,hshift) ((((__uint32_t)(suffix)) << (hshift)) \ | ||||
| #define BSD_HASH(prefix,suffix,hshift) ((((__uint32_t)(suffix)) << (hshift))\ | ||||
| ^ (__uint32_t)(prefix)) | ^ (__uint32_t)(prefix)) | |||
| #define BSD_KEY(prefix,suffix) ((((__uint32_t)(suffix)) << 16) \ | #define BSD_KEY(prefix,suffix) ((((__uint32_t)(suffix)) << 16) \ | |||
| + (__uint32_t)(prefix)) | + (__uint32_t)(prefix)) | |||
| #define CHECK_GAP 10000 /* Ratio check interval */ | #define CHECK_GAP 10000 /* Ratio check interval */ | |||
| #define RATIO_SCALE_LOG 8 | #define RATIO_SCALE_LOG 8 | |||
| #define RATIO_SCALE (1<<RATIO_SCALE_LOG) | #define RATIO_SCALE (1<<RATIO_SCALE_LOG) | |||
| #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG) | #define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG) | |||
| skipping to change at line 511 ¶ | skipping to change at line 525 ¶ | |||
| } | } | |||
| db->ratio = new_ratio; | db->ratio = new_ratio; | |||
| } | } | |||
| } | } | |||
| return 0; | return 0; | |||
| } | } | |||
| /* Initialize the database. | /* Initialize the database. | |||
| */ | */ | |||
| struct bsd_db * | struct bsd_db * | |||
| pf_bsd_init(struct bsd_db *db, int unit, int bits, int mru) | 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 int i; | |||
| register u_short *lens; | register u_short *lens; | |||
| register u_int newlen, hsize, hshift, maxmaxcode; | register u_int newlen, hsize, hshift, maxmaxcode; | |||
| switch (bits) { | switch (bits) { | |||
| case 9: /* needs 82152 for both directions */ | case 9: /* needs 82152 for both directions */ | |||
| case 10: /* needs 84144 */ | case 10: /* needs 84144 */ | |||
| case 11: /* needs 88240 */ | case 11: /* needs 88240 */ | |||
| case 12: /* needs 96432 */ | case 12: /* needs 96432 */ | |||
| skipping to change at line 711 ¶ | skipping to change at line 728 ¶ | |||
| db->dict[dictp2->cptr].codem1 = BADCODEM1; | db->dict[dictp2->cptr].codem1 = BADCODEM1; | |||
| dictp2->cptr = hval; | dictp2->cptr = hval; | |||
| dictp->codem1 = max_ent; | dictp->codem1 = max_ent; | |||
| dictp->f.fcode = fcode; | dictp->f.fcode = fcode; | |||
| db->max_ent = ++max_ent; | db->max_ent = ++max_ent; | |||
| } | } | |||
| ent = c; | ent = c; | |||
| } | } | |||
| OUTPUT(ent); /* output the last code */ | OUTPUT(ent); /* output the last code */ | |||
| db->bytes_out += (wptr-(cp_buf+3) /* count complete bytes */ | db->bytes_out += (wptr-&cp_buf[2] /* count complete bytes */ | |||
| + (32-bitno+7)/8); | + (32-bitno+7)/8); | |||
| if (pf_bsd_check(db)) | if (pf_bsd_check(db)) | |||
| OUTPUT(CLEAR); /* do not count the CLEAR */ | OUTPUT(CLEAR); /* do not count the CLEAR */ | |||
| /* Pad dribble bits of last code with ones. | /* Pad dribble bits of last code with ones. | |||
| * Do not emit a completely useless byte of ones. | * Do not emit a completely useless byte of ones. | |||
| */ | */ | |||
| if (bitno != 32) | if (bitno != 32) | |||
| *wptr++ = (accum | (0xff << (bitno-8))) >> 24; | *wptr++ = (accum | (0xff << (bitno-8))) >> 24; | |||
| /* Increase code size if we would have without the packet | /* Increase code size if we would have without the packet | |||
| * boundary and as the decompressor will. | * boundary and as the decompressor will. | |||
| */ | */ | |||
| if (max_ent >= MAXCODE(n_bits) | if (max_ent >= MAXCODE(n_bits) | |||
| && max_ent < db->maxmaxcode) | && max_ent < db->maxmaxcode) | |||
| db->n_bits++; | db->n_bits++; | |||
| return (wptr - cp_buf); | return (wptr - cp_buf); | |||
| #undef OUTPUT | #undef OUTPUT | |||
| } | } | |||
| /* Update the "BSD Compress" dictionary on the receiver for | /* Update the "BSD Compress" dictionary on the receiver for | |||
| * incompressible data by pretending to compress the incoming data. | * incompressible data by pretending to compress the incoming data. | |||
| */ | */ | |||
| static void | void | |||
| pf_bsd_incomp(struct bsd_db *db, | pf_bsd_incomp(struct bsd_db *db, | |||
| mblk_t *dmsg, | mblk_t *dmsg, | |||
| u_int ent) /* start with the protocol byte */ | u_int ent) /* start with the protocol byte */ | |||
| { | { | |||
| register u_int hshift = db->hshift; | register u_int hshift = db->hshift; | |||
| register u_int max_ent = db->max_ent; | register u_int max_ent = db->max_ent; | |||
| register u_int n_bits = db->n_bits; | register u_int n_bits = db->n_bits; | |||
| register struct bsd_dict *dictp; | register struct bsd_dict *dictp; | |||
| register __uint32_t fcode; | register __uint32_t fcode; | |||
| register u_char c; | register u_char c; | |||
| skipping to change at line 836 ¶ | skipping to change at line 853 ¶ | |||
| /* Increase code size if we would have without the packet | /* Increase code size if we would have without the packet | |||
| * boundary and as the decompressor will. | * boundary and as the decompressor will. | |||
| */ | */ | |||
| if (max_ent >= MAXCODE(n_bits) | if (max_ent >= MAXCODE(n_bits) | |||
| && max_ent < db->maxmaxcode) | && max_ent < db->maxmaxcode) | |||
| db->n_bits++; | db->n_bits++; | |||
| } | } | |||
| /* Decompress "BSD Compress" | /* Decompress "BSD Compress" | |||
| */ | */ | |||
| static mblk_t* /* 0=failed, so zap CCP */ | mblk_t* /* 0=failed, so zap CCP */ | |||
| pf_bsd_decomp(struct bsd_db *db, | pf_bsd_decomp(struct bsd_db *db, | |||
| mblk_t *cmsg) | mblk_t *cmsg) | |||
| { | { | |||
| register u_int max_ent = db->max_ent; | register u_int max_ent = db->max_ent; | |||
| register __uint32_t accum = 0; | register __uint32_t accum = 0; | |||
| register u_int bitno = 32; /* 1st valid bit in accum */ | register u_int bitno = 32; /* 1st valid bit in accum */ | |||
| register u_int n_bits = db->n_bits; | register u_int n_bits = db->n_bits; | |||
| register u_int tgtbitno = 32-n_bits; /* bitno when accum full */ | register u_int tgtbitno = 32-n_bits; /* bitno when accum full */ | |||
| register struct bsd_dict *dictp; | register struct bsd_dict *dictp; | |||
| register int explen, i; | register int explen, i; | |||
| skipping to change at line 852 ¶ | skipping to change at line 869 ¶ | |||
| register u_int bitno = 32; /* 1st valid bit in accum */ | register u_int bitno = 32; /* 1st valid bit in accum */ | |||
| register u_int n_bits = db->n_bits; | register u_int n_bits = db->n_bits; | |||
| register u_int tgtbitno = 32-n_bits; /* bitno when accum full */ | register u_int tgtbitno = 32-n_bits; /* bitno when accum full */ | |||
| register struct bsd_dict *dictp; | register struct bsd_dict *dictp; | |||
| register int explen, i; | register int explen, i; | |||
| register u_int incode, oldcode, finchar; | register u_int incode, oldcode, finchar; | |||
| register u_char *p, *rptr, *rptr9, *wptr0, *wptr; | register u_char *p, *rptr, *rptr9, *wptr0, *wptr; | |||
| mblk_t *dmsg, *dmsg1, *bp; | mblk_t *dmsg, *dmsg1, *bp; | |||
| db->decomp_count++; | db->decomp_count++; | |||
| rptr = cmsg->b_rptr; | rptr = cmsg->b_rptr; | |||
| ASSERT(cmsg->b_wptr >= rptr+PPP_BUF_MIN); | ASSERT(cmsg->b_wptr >= rptr+PPP_BUF_MIN); | |||
| ASSERT(PPP_BUF_ALIGN(rptr)); | ||||
| rptr += PPP_BUF_MIN; | rptr += PPP_BUF_MIN; | |||
| /* get the sequence number */ | /* get the sequence number */ | |||
| i = 0; | i = 0; | |||
| explen = 2; | explen = 2; | |||
| do { | do { | |||
| while (rptr >= cmsg->b_wptr) { | while (rptr >= cmsg->b_wptr) { | |||
| bp = cmsg; | bp = cmsg; | |||
| cmsg = cmsg->b_cont; | cmsg = cmsg->b_cont; | |||
| freeb(bp); | freeb(bp); | |||
| skipping to change at line 879 ¶ | skipping to change at line 896 ¶ | |||
| db->unit, explen); | db->unit, explen); | |||
| return 0; | return 0; | |||
| } | } | |||
| rptr = cmsg->b_rptr; | rptr = cmsg->b_rptr; | |||
| } | } | |||
| i = (i << 8) + *rptr++; | i = (i << 8) + *rptr++; | |||
| } while (--explen != 0); | } while (--explen != 0); | |||
| if (i != db->seqno++) { | if (i != db->seqno++) { | |||
| freemsg(cmsg); | freemsg(cmsg); | |||
| if (db->debug) | if (db->debug) | |||
| printf("bsd_decomp%d: bad sequence number %d" | printf("bsd_decomp%d: bad sequence number 0x%x" | |||
| " instead of %d\n", | " instead of 0x%x\n", | |||
| db->unit, i, db->seqno-1); | db->unit, i, db->seqno-1); | |||
| return 0; | return 0; | |||
| } | } | |||
| /* Guess how much memory we will need. Assume this packet | /* Guess how much memory we will need. Assume this packet was | |||
| * compressed by at least 1.5X regardless of the recent ratio | * compressed by at least 1.5X regardless of the recent ratio. | |||
| */ | */ | |||
| if (db->ratio > (RATIO_SCALE*3)/2) | if (db->ratio > (RATIO_SCALE*3)/2) | |||
| explen = (msgdsize(cmsg)*db->ratio)/RATIO_SCALE; | explen = (msgdsize(cmsg)*db->ratio)/RATIO_SCALE; | |||
| else | else | |||
| explen = (msgdsize(cmsg)*3)/2; | explen = (msgdsize(cmsg)*3)/2; | |||
| if (explen > db->mru) | if (explen > db->mru) | |||
| explen = db->mru; | explen = db->mru; | |||
| dmsg = dmsg1 = allocb(explen+PPP_BUF_HEAD_INFO, BPRI_HI); | dmsg = dmsg1 = allocb(explen+PPP_BUF_HEAD_INFO, BPRI_HI); | |||
| if (!dmsg1) { | if (!dmsg1) { | |||
| skipping to change at line 1147 ¶ | skipping to change at line 1164 ¶ | |||
| Table of Contents | Table of Contents | |||
| 1. Introduction .......................................... 1 | 1. Introduction .......................................... 1 | |||
| 1.1 Licensing ....................................... 1 | 1.1 Licensing ....................................... 1 | |||
| 2. BSD Compress Packets .................................. 2 | 2. BSD Compress Packets .................................. 2 | |||
| 2.1 Packet Format ................................... 4 | 2.1 Packet Format ................................... 4 | |||
| 3. Configuration Option Format ........................... 6 | 3. Configuration Option Format ........................... 6 | |||
| APPENDICES ................................................... 7 | APPENDICES ................................................... 8 | |||
| A. BSD Compress Algorithm ................................ 7 | A. BSD Compress Algorithm ................................ 8 | |||
| SECURITY CONSIDERATIONS ...................................... 24 | SECURITY CONSIDERATIONS ...................................... 26 | |||
| REFERENCES ................................................... 24 | REFERENCES ................................................... 26 | |||
| ACKNOWLEDGEMENTS ............................................. 24 | ACKNOWLEDGEMENTS ............................................. 26 | |||
| CHAIR'S ADDRESS .............................................. 25 | CHAIR'S ADDRESS .............................................. 27 | |||
| AUTHOR'S ADDRESS ............................................. 25 | AUTHOR'S ADDRESS ............................................. 27 | |||
| End of changes. 25 change blocks. | ||||
| 24 lines changed or deleted | 42 lines changed or added | |||
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/ | ||||