idnits 2.17.1 draft-ietf-pppext-predictor-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-03-29) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == Mismatching filename: the document gives the document name as 'draft-ieft-pppext-predictor-00', but the file name used is 'draft-ietf-pppext-predictor-00' == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 17 instances of too long lines in the document, the longest one being 13 characters in excess of 72. ** The abstract seems to contain references ([2], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 76: '...ber. This value MAY be compressed whe...' RFC 2119 keyword, line 79: '...Protocol packets MUST NOT be send with...' RFC 2119 keyword, line 316: '...on has not be negotiated, it MUST be a...' RFC 2119 keyword, line 321: '...CP Protocol field MAY be compressed as...' RFC 2119 keyword, line 363: '...on has not be negotiated, it MUST be a...' (1 more instance...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- The document date (December 1993) is 11062 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '65536' is mentioned on line 169, but not defined -- Looks like a reference, but probably isn't: 'Hash' on line 228 -- Looks like a reference, but probably isn't: 'SIZ1' on line 243 == Unused Reference: '3' is defined on line 398, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' -- Possible downref: Non-RFC (?) normative reference: ref. '3' Summary: 11 errors (**), 0 flaws (~~), 5 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group D Rand 2 Internet Draft Novell 3 Expires in six months December 1993 5 PPP Predictor Compression Protocol 6 draft-ieft-pppext-predictor-00.txt 8 Status of this Memo 10 This document is the product of the Point-to-Point Protocol Working 11 Group of the Internet Engineering Task Force (IETF). Comments should 12 be submitted to the ietf-ppp@ucdavis.edu mailing list. 14 Distribution of this memo is unlimited. 16 This document is an Internet Draft. Internet Drafts are working 17 documents of the Internet Engineering Task Force (IETF), its Areas, 18 and its Working Groups. Note that other groups may also distribute 19 working documents as Internet Drafts. 21 Internet Drafts are draft documents valid for a maximum of six 22 months. Internet Drafts may be updated, replaced, or obsoleted by 23 other documents at any time. It is not appropriate to use Internet 24 Drafts as reference material or to cite them other than as a 25 ``working draft'' or ``work in progress.'' 27 Please check the 1id-abstracts.txt listing contained in the 28 internet-drafts Shadow Directories on nic.ddn.mil, nnsc.nsf.net, 29 nic.nordu.net, ftp.nisc.sri.com, or munnari.oz.au to learn the 30 current status of any Internet Draft. 32 Abstract 34 The Point-to-Point Protocol (PPP) [1] provides a standard method of 35 encapsulating multiple protocol datagrams over point-to-point links. 37 The PPP Compression Control Protocol [2] provides a method for 38 transporting multi-protocol datagrams over PPP encapsulated links. 40 This document describes the use of the Predictor data compression 41 algorithm for compressing PPP encapsulated packets. 43 1. Introduction 45 Predictor is a high speed compression algorithm, available without 46 license fees. The compression ratio obtained using predictor is not 47 as good as other compression algorithms, but it remains one of the 48 fastest algorithms available. 50 Note that although care has been taken to ensure that the following 51 code does not infringe any patents, there is no assurance that it is 52 not covered by a patent. 54 2. Licensing 56 There are no license fees or costs associated with using the 57 Predictor algorithm. 59 Use the following code at your own risk. 61 3. Predictor Packets 63 Before any Predictor packets may be communicated, PPP must reach the 64 Network-Layer Protocol phase, and the Compression Control Protocol 65 must reach the Opened state. 67 Exactly one Predictor datagram is encapsulated in the PPP Information 68 field, where the PPP Protocol field indicates type hex 00FD 69 (compressed datagram). 71 The maximum length of the Predictor datagram transmitted over a PPP 72 link is the same as the maximum length of the Information field of a 73 PPP encapsulated packet. 75 Prior to compression, the uncompressed data begins with the PPP 76 Protocol number. This value MAY be compressed when Protocol-Field- 77 Compression is negotiated. 79 PPP Link Control Protocol packets MUST NOT be send within compressed 80 data. 82 3.1. Predictor theory 84 Predictor works by filling a guess table with values, based on the 85 hash of the previous characters seen. Since we are either emitting 86 the source data, or depending on the guess table, we add a flag bit 87 for every byte of input, telling the decompressor if it should 88 retrieve the byte from the compressed data stream, or the guess 89 table. Blocking the input into groups of 8 characters means that we 90 don't have to bit-insert the compressed output - a flag byte preceeds 91 every 8 bytes of compressed data. Each bit of the flag byte 92 corresponds to one byte of reconstructed data. 94 Take the source file: 96 000000 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA. 97 000010 4141 4141 4141 410a 4141 4141 4141 410a AAAAAAA.AAAAAAA. 98 000020 4142 4142 4142 410a 4241 4241 4241 420a ABABABA.BABABAB. 99 000030 7878 7878 7878 780a xxxxxxx. 101 Compressing the above data yields the following: 103 000000 6041 4141 4141 0a60 4141 4141 410a 6f41 `AAAAA.`AAAAA.oA 104 000010 0a6f 410a 4142 4142 4142 0a60 4241 4241 .oA.ABABAB.`BABA 105 000020 420a 6078 7878 7878 0a B.`xxxxx. 107 Reading the above data says: 109 flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. 110 Reconstructed data is: 0 1 2 3 4 5 6 7 111 File: A A A A A 112 Guess table: A A 113 flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. 114 Reconstructed data is: 0 1 2 3 4 5 6 7 115 File: A A A A A 116 Guess table: A A 117 flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6. 118 Reconstructed data is: 0 1 2 3 4 5 6 7 119 File: A 120 Guess table: A A A A A A 121 flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6. 122 Reconstructed data is: 0 1 2 3 4 5 6 7 123 File: A 124 Guess table: A A A A A A 125 flag = 0x41 - 2 bytes in this block were guessed correctly, 0 and 6. 126 Reconstructed data is: 0 1 2 3 4 5 6 7 127 File: B A B A B 128 Guess table: A A 129 flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6. 130 Reconstructed data is: 0 1 2 3 4 5 6 7 131 File: B A B A B 132 Guess table: A B 133 flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6 134 Reconstructed data is: 0 1 2 3 4 5 6 7 135 File: x x x x x 136 Guess table: x x 138 And now, on to the source - note that it has been modified to work 139 with a split block. If your data stream can't be split within a block 140 (eg, compressing packets), then the code dealing with "final", and 141 the memcpy are not required. You can detect this situation (or 142 errors, for that matter) by observing that the flag byte indicates 143 that more data is required from the compressed data stream, but you 144 are out of data (len in decompress is <= 0). It *is* ok if len == 0, 145 and flags indicate guess table usage. 147 #include 148 #ifdef __STDC__ 149 #include 150 #endif 151 #include 152 /* 153 * pred.c -- Test program for Dave Rand's rendition of the 154 * predictor algorithm 155 * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson) 156 * Updated by: Carsten Bormann 157 * Original : Dave Rand / 158 */ 160 /* The following hash code is the heart of the algorithm: 161 * It builds a sliding hash sum of the previous 3-and-a-bit characters 162 * which will be used to index the guess table. 163 * A better hash function would result in additional compression, 164 * at the expense of time. 165 */ 166 #define HASH(x) Hash = (Hash << 4) ^ (x) 168 static unsigned short int Hash; 169 static unsigned char GuessTable[65536]; 171 static int 172 compress(source, dest, len) 173 unsigned char *source, *dest; 174 int len; 175 { 176 int i, bitmask; 177 unsigned char *flagdest, flags, *orgdest; 179 orgdest = dest; 180 while (len) { 181 flagdest = dest++; flags = 0; /* All guess wrong initially */ 182 for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) { 183 if (GuessTable[Hash] == *source) { 184 flags |= bitmask; /* Guess was right - don't output */ 185 } else { 186 GuessTable[Hash] = *source; 187 *dest++ = *source; /* Guess wrong, output char */ 188 } 189 HASH(*source++);len--; 190 } 191 *flagdest = flags; 192 } 193 return(dest - orgdest); 194 } 196 static int 197 decompress(source, dest, lenp, final) 198 unsigned char *source, *dest; 199 int *lenp, final; 200 { 201 int i, bitmask; 202 unsigned char flags, *orgdest; 203 int len = *lenp; 204 orgdest = dest; 205 while (len >= 9) { 206 flags = *source++; 207 for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 208 if (flags & bitmask) { 209 *dest = GuessTable[Hash]; /* Guess correct */ 210 } else { 211 GuessTable[Hash] = *source; /* Guess wrong */ 212 *dest = *source++; /* Read from source */ 213 len--; 214 } 215 HASH(*dest++); 216 } 217 len--; 218 } 219 while (final && len) { 220 flags = *source++; 221 len--; 222 for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) { 223 if (flags & bitmask) { 224 *dest = GuessTable[Hash]; /* Guess correct */ 225 } else { 226 if (!len) 227 break; /* we seem to be really done -- cabo */ 228 GuessTable[Hash] = *source; /* Guess wrong */ 229 *dest = *source++; /* Read from source */ 230 len--; 231 } 232 HASH(*dest++); 233 } 234 } 235 *lenp = len; 236 return(dest - orgdest); 237 } 239 #define SIZ1 8192 241 static void 242 compress_file(f) FILE *f; { 243 char bufp[SIZ1]; 244 char bufc[SIZ1/8*9+9]; 245 int len1, len2; 246 while ((len1 = fread(bufp, 1, SIZ1, f)) > 0) { 247 len2 = compress((unsigned char *)bufp, (unsigned char *)bufc, len1); 248 (void) fwrite(bufc, 1, len2, stdout); 249 } 250 } 251 static void 252 decompress_file(f) FILE *f; { 253 char bufp[SIZ1+9]; 254 char bufc[SIZ1*9+9]; 255 int len1, len2, len3; 257 len1 = 0; 258 while ((len3 = fread(bufp+len1, 1, SIZ1, f)) > 0) { 259 len1 += len3; 260 len3 = len1; 261 len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 0); 262 (void) fwrite(bufc, 1, len2, stdout); 263 (void) memcpy(bufp, bufp+len3-len1, len1); 264 } 265 len2 = decompress((unsigned char *)bufp, (unsigned char *)bufc, &len1, 1); 266 (void) fwrite(bufc, 1, len2, stdout); 267 } 269 int 270 main(ac, av) 271 int ac; 272 char** av; 273 { 274 char **p = av+1; 275 int dflag = 0; 277 for (; --ac > 0; p++) { 278 if (!strcmp(*p, "-d")) 279 dflag = 1; 280 else if (!strcmp(*p, "-")) 281 (dflag?decompress_file:compress_file)(stdin); 282 else { 283 FILE *f = fopen(*p, "r"); 284 if (!f) { 285 perror(*p); 286 exit(1); 287 } 288 (dflag?decompress_file:compress_file)(f); 289 (void) fclose(f); 290 } 291 } 292 return(0); 293 } 295 3.2. Encapsulation for Predictor type 1 297 The correct encapsulation for type 1 compression is the protocol 298 type, 1 bit indicating if the data is compressed or not, 15 bits of 299 the uncompressed data length in octets, compressed data, and 300 uncompressed CRC-16 of the two octets of unsigned length in network 301 byte order, followed by the original, uncompressed data packet. 303 0 1 304 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 305 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 306 | CCP Protocol Identifier | 307 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 308 |*| Uncompressed length (octets)| * is compressed flag 309 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed 310 | Compressed data... | 0 means data is not compressed 311 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 312 | CRC - 16 | 313 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 315 The CCP Protocol Identifier that starts the packet is always 0xfd. 316 If PPP Protocol field compression has not be negotiated, it MUST be a 317 16-bit field. 319 The Compressed data is the Protocol Identifier and the Info fields of 320 the original PPP packet described in [1], but not the Address, 321 Control, FCS, or Flag. The CCP Protocol field MAY be compressed as 322 described in [1], regardless of whether the Protocol field of the CCP 323 Protocol Identifier is compressed or whether PPP Protocol field 324 compression has been negotiated. 326 It is not required that any of the fields land on an even word 327 boundary - the compressed data may be of any length. If during the 328 decode procedure, the CRC-16 does not match the decoded frame, it 329 means that the compress or decompress process has become 330 desyncronized. This will happen as a result of a frame being lost in 331 transit if LAPB is not used. In this case, a new configure-request 332 must be sent, and the CCP will drop out of the open state. Upon 333 receipt of the configure-ack, the predictor tables are cleared to 334 zero, and compression can be resumed without data loss. 336 3.3. Encapsulation for Predictor type 2 338 The correct encapsulation for type 2 compression is the protocol 339 type, followed by the data stream. Within the data stream is the 340 current frame length (uncompressed), compressed data, and 341 uncompressed CRC-16 of the two octets of unsigned length in network 342 byte order, followed by the original, uncompressed data. The data 343 stream may be broken at any convenient place for encapsulation 344 purposes. With type 2 encapsulation, LAPB is almost essential for 345 correct delivery. 347 0 1 348 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 349 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 350 | CCP Protocol Identifier | 351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 352 |*| Uncompressed length (octets)| * is compressed flag 353 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1 means data is compressed 354 | Compressed data... | 0 means data is not compressed 355 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 356 | CRC-16 | 357 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 358 |*| Uncompressed length (octets)| * is compressed flag 359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 360 ... 362 The CCP Protocol Identifier that starts the packet is always 0xfd. 363 If PPP Protocol field compression has not be negotiated, it MUST be a 364 16-bit field. 366 The Compressed data is the Protocol Identifier and the Info fields of 367 the original PPP packet described in [1], but not the Address, 368 Control, FCS, or Flag. The CCP Protocol field MAY be compressed as 369 described in [1], regardless of whether the Protocol field of the CCP 370 Protocol Identifier is compressed or whether PPP Protocol field 371 compression 373 It is not required that any field land on an even word boundary - the 374 compressed data may be of any length. If during the decode 375 procedure, the CRC-16 does not match the decoded frame, it means that 376 the compress or decompress process has become desyncronized. This 377 will happen as a result of a frame being lost in transit if LAPB is 378 not used. In this case, a new configure-request must be sent, and 379 the CCP will drop out of the open state. Upon receipt of the 380 configure-ack, the predictor tables are cleared to zero, and 381 compression can be resumed without data loss. 383 4. Configuration Option Format 385 There are no options for Predictor type one or two. 387 Security Considerations 389 Security issues are not discussed in this memo. 391 References 393 [1] Simpson, W. A., "The Point-to-Point Protocol", RFC in progress. 395 [2] Rand, D., "The PPP Compression Control Protocol (CCP)", work in 396 progress. 398 [3] Rand, D., "PPP Reliable Transmission", work in progress. 400 Acknowledgments 402 The predictor algorithm was originally implemented by Timo Raita, at 403 the ACM SIG Conference, New Orleans, 1987. 405 Bill Simpson helped with the document formatting. 407 Chair's Address 409 The working group can be contacted via the current chair: 411 Fred Baker 412 Advanced Computer Communications 413 315 Bollay Drive 414 Santa Barbara, California 93117 416 (805) 685 4455 418 EMail: fbaker@acc.com 420 Author's Address 422 Questions about this memo can also be directed to: 424 Dave Rand 425 Novell, Inc. 426 2180 Fortune Drive 427 San Jose, CA 95131 429 +1 408 321-1259 431 EMail: dave_rand@novell.com 432 Table of Contents 434 1. Introduction .......................................... 1 436 2. Licensing ............................................. 1 438 3. Predictor Packets ..................................... 2 439 3.1 Predictor theory ................................ 2 440 3.2 Encapsulation for Predictor type 1 .............. 7 441 3.3 Encapsulation for Predictor type 2 .............. 8 443 4. Configuration Option Format ........................... 9 445 SECURITY CONSIDERATIONS ...................................... 9 447 REFERENCES ................................................... 9 449 ACKNOWLEDGEMENTS ............................................. 9 451 CHAIR'S ADDRESS .............................................. 9 453 AUTHOR'S ADDRESS ............................................. 9