idnits 2.17.1 draft-ietf-pppext-cobs-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-04-26) 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 -- however, there's a paragraph with a matching beginning. Boilerplate error? ** 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. == 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 a Security Considerations section. ** 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. ** The abstract seems to contain references ([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 113: '... o MUST, SHALL, or MANDATORY -- ...' RFC 2119 keyword, line 116: '... o SHOULD or RECOMMEND -- This i...' RFC 2119 keyword, line 119: '... o MAY or OPTIONAL -- This item ...' RFC 2119 keyword, line 146: '...re reserved, and MUST be set to zero o...' RFC 2119 keyword, line 174: '... transmitters SHALL be capable of ha...' (10 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == Using lowercase 'not' together with uppercase 'MUST', 'SHALL', 'SHOULD', or 'RECOMMENDED' is not an accepted usage according to RFC 2119. Please use uppercase 'NOT' together with RFC 2119 keywords (if that is what you mean). Found 'MUST not' in this paragraph: One aspect of zero-run compression is that on reception this compressed data has to be expanded back to its original size. On the very highest speed links, where the link data rate is comparable to the memory system bandwidth, this potential 15:1 expansion at the receiver may be unacceptable. For this reason, the receiver may request in its COBS Configuration Option that the sender *not* gen-erate zero-pair (hex E0-FE) or zero-run (hex D3-DF) COBS codes. If the receiver does not indicate its desire to receive zero-pair and zero-run codes in its COBS Configuration Option, the transmitter MUST not generate these codes. -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (November 1997) is 9659 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: '0' is mentioned on line 1029, but not defined -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' Summary: 11 errors (**), 0 flaws (~~), 3 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 PPP Working Group J. Carlson 2 Internet Draft IronBridge Networks 3 expires in six months S. Cheshire 4 M. Baker 5 Stanford University 6 November 1997 8 PPP Consistent Overhead Byte Stuffing (COBS) 9 11 Status of this Memo 13 This document is the product of the Point-to-Point Protocol 14 Extensions Working Group of the Internet Engineering Task Force 15 (IETF). Comments should be submitted to the ietf-ppp@merit.edu 16 mailing list. 18 Distribution of this memo is unlimited. 20 This document is an Internet-Draft. Internet-Drafts are working 21 documents of the Internet Engineering Task Force (IETF), its areas, 22 and its working groups. Note that other groups may also distribute 23 working documents as Internet-Drafts. 25 Internet-Drafts are draft documents valid for a maximum of six 26 months. Internet-Drafts may be updated, replaced, or obsoleted by 27 other documents at any time. It is not appropriate to use Internet- 28 Drafts as reference material or to cite them other than as a 29 ``working draft'' or ``work in progress.'' 31 To learn the current status of any Internet-Draft, please check the 32 1id-abstracts.txt listing contained in the Internet-Drafts Shadow 33 Directories on ds.internic.net, nic.nordu.net, ftp.nisc.sri.com, or 34 munnari.oz.au. 36 Abstract 38 The Point-to-Point Protocol (PPP) [1] provides a standard method for 39 transporting multi-protocol datagrams over point-to-point links. 41 PPP also defines an extensible Link Control Protocol, which allows 42 the negotiation of optional frame encoding methods. This document 43 defines the Consistent Overhead Byte Stuffing (COBS) negotiation and 44 encapsulation procedure. 46 Table of Contents 48 1. Introduction ........................................... 2 49 1.1. Conventions ............................................ 3 50 2. COBS Configuration Option Format ....................... 3 51 3. Encapsulation Method ................................... 5 52 3.1. Frame Transmission ..................................... 6 53 3.2. Frame Reception ........................................ 8 54 3.3. Zero-pair and zero-run encoding ........................ 9 55 3.4. Packet Preemption ...................................... 10 56 3.5. Recovery on LCP Renegotiation .......................... 12 57 3.6. Handling of Corrupted Data ............................. 12 58 4. Source Code ............................................ 13 59 4.1. Linear buffer encoding and decoding .................... 13 60 4.2. PPP/COBS Encoding with mbufs ........................... 16 61 4.2.1. PPP Context Handling ................................... 16 62 4.2.2. PPP Frame Transmission ................................. 17 63 4.2.3. Frame Reception ........................................ 23 64 5. Acknowledgments ........................................ 26 65 6. References ............................................. 26 66 7. Authors' Addresses ..................................... 26 68 1. Introduction 70 Standard PPP encapsulation on an asynchronous link uses an encapsula- 71 tion procedure called AHDLC, and on a Synchronous Optical Network 72 (SONET) or Synchronous Digital Heirarchy (SDH) link an encapsulation 73 procedure called Octet Synchronous [2]. These procedures are easy to 74 implement, require only a single character buffer and have good 75 error-recovery characteristics, but they have a worst case expansion 76 ratio of 100% where the user data consists of only hex 7D or 7E. 78 This draft describes a new encapsulation method for PPP due to origi- 79 nal work by Stuart Cheshire and Mary Baker at the Stanford University 80 Computer Science Department [3]. This new method is slightly more 81 complex than either of the two standard encodings and requires a 207 82 character buffer, but it has the same error-recovery characteristics 83 and has a worst-case expansion of less than 0.5%. 85 This low bound on worst-case expansion has a number of benefits. For 86 applications requiring Quality of Service (QoS) guarantees, it may be 87 necessary to over-provision a line using PPP by a factor of two in 88 order to deliver the requested bandwidth or to suffer possible queu- 89 ing delays when data do expand. For applications where the underly- 90 ing transport has message size limits, such as some radio protocols, 91 conventional PPP byte stuffing requires that the PPP Maximum Receive 92 Unit (MRU) and the associated network Maximum Transmission Units 93 (MTUs) be reduced to half of the underlying hardware MTU. Even where 94 these considerations are not important, COBS options can provide 95 lower overhead than standard encoding methods, resulting in better 96 performance. 98 It should be noted that this concern over pathological data patterns 99 which double in size is not entirely academic. Certain protocols, 100 such as raw Pulse-Code Modulated (PCM) voice over User Datagram Pro- 101 tocol (UDP), can be prone to sending an excessive density of 7E char- 102 acters which will cause the standard encapsulations to double the 103 amount of actual data sent. Ironically, these protocols are pre- 104 cisely the ones that are likely to want guaranteed bandwidth ser- 105 vices. COBS avoids those expansion cases entirely because its 106 worst-case expansion in encoded data is less than 0.5%. 108 1.1. Conventions 110 The following language conventions are used in the items of specifi- 111 cation in this document: 113 o MUST, SHALL, or MANDATORY -- This item is an absolute require- 114 ment of the specification. 116 o SHOULD or RECOMMEND -- This item should generally be followed 117 for all but exceptional circumstances. 119 o MAY or OPTIONAL -- This item is truly optional and may be fol- 120 lowed or ignored according to the needs of the implementor. 122 2. COBS Configuration Option Format 124 A summary of the COBS Configuration Option format for the Link Con- 125 trol Protocol (LCP) is shown below. The fields are transmitted from 126 left to right. 128 0 1 2 129 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 130 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 131 | Type | Length | Flags | 132 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 134 Type 136 To Be Determined 138 Length 140 3 142 Flags 144 The flags are a single octet representing options which are passed 145 from the receiver to the transmitter. The most significant six 146 bits of this octet are reserved, and MUST be set to zero on 147 transmit and ignored on reception. 149 0 1 2 3 4 5 6 7 150 +-----+-----+-----+-----+-----+-----+-----+-----+ 151 | Res | Res | Res | Res | Res | Res | PRE | ZXE | 152 +-----+-----+-----+-----+-----+-----+-----+-----+ 154 These flags are: 156 ZXE If set to 1, then the receiver supports both zero pair 157 elimination (ZPE) and zero run elimination (ZRE). 159 PRE If set to 1, then the receiver supports packet preemp- 160 tion, which allows the sender to interrupt a COBS packet 161 in mid-stream to send a higher priority packet, and to 162 then return to the lower priority data. 164 This option is a boolean flag appearing at most once in a single 165 Configure-Request message. If it is present in a Configure-Request 166 message, then the sender wishes to receive data encoded using COBS 167 once LCP reaches Open state. If it is absent from the request, then 168 the sender does not wish to receive COBS data. If the option is 169 included in a Configure-Reject, then the sender is unable to transmit 170 using COBS and will continue to use the standard method for this link 171 (either Octet Synchronous or AHDLC) when LCP reaches the Open state. 173 The value of the Flags field is not negotiated because all COBS 174 transmitters SHALL be capable of handling all possible flag combina- 175 tions. Just as with MRU negotiation, where a receiver indicating 176 that it is prepared to receive packets up to 2048 octets in length 177 does not obligate its peer to actually send any packet with as many 178 as 2048 octets, a receiver indicating that it is prepared to receive 179 either of the optional COBS encodings does not obligate its peer to 180 actually send any packet using those encodings. Consequently, the 181 COBS option MUST NOT be included in a Configure-Nak message in reply 182 to a Configure-Request containing this option, even if the peer does 183 not implement some or all of the options that the receiver has indi- 184 cated its willingness to receive. 186 An implementation that requires the use of COBS for normal operation 187 MAY, however, choose to send an "unsolicited" Configure-Nak with the 188 COBS option if the peer fails to include the COBS option in its 189 Configure-Request. 191 3. Encapsulation Method 193 Like the standard encapsulations, COBS uses an octet of hex 7E to 194 mark the bounds between frames. The value 7E does not appear in the 195 frame data itself. Using the value 7E helps ensure compatibility 196 with any existing software and hardware that may assume that the PPP 197 frame boundary marker is always 7E. It also aids recovery in the 198 case where errors occur and the transmitter and receiver are not in 199 agreement about whether COBS encapsulation is in effect. Because the 200 framing marker is the same regardless of whether COBS encapsulation 201 is in effect, frame boundaries are still detected correctly, and this 202 allows the error recovery described in section 3.5 to work very 203 easily. 205 COBS encapsulation is a simple reversible transformation that elim- 206 inates all instances of hex 7E from the frame to be transmitted. 207 This COBS encoding procedure is logically a two-step process, 208 although in real implementations both steps are performed in a single 209 loop for the sake of efficiency. The first step ("zero elimination") 210 eliminates all occurrences of zeroes from the data, while guarantee- 211 ing to add at most no more than 0.5% to the data size. This results 212 in a data packet containing only byte values hex 01 to hex FF, and no 213 zeroes. The second step ("7E substitution") replaces all occurrences 214 of hex 7E with hex 00, thereby producing a packet that does contain 215 zeroes but contains no instances of hex 7E. 217 The zero elimination step encodes any data packet using a series of 218 COBS code blocks. Each COBS code block begins with a single code 219 byte, followed by zero or more data bytes. The code byte determines 220 how many data bytes follow. The codes and their meanings are deter- 221 mined such that all possible data packets can be encoded as a valid 222 series of code blocks, and furthermore, even in the worst possible 223 case, there exists no valid encoding that adds more than 0.5% over- 224 head to the packet size. There is no pre-set limit to the length of 225 packet that may be encoded. The value zero is never used as a code 226 byte, nor does it ever appear as a data byte, which is why the output 227 of COBS zero elimination never contains any instances of the value 228 zero. 230 The 7E substitution step allows a linear code range to be used for 231 octet counts without concern for the potential end-of-frame marker in 232 the middle of the code space. 234 The PPP/COBS codes and their meanings are listed below: 236 Code (n) Followed by: Meaning 237 -------- ------------ ------- 238 00 Unused (framing character placeholder) 239 01-CF n-1 data bytes The data bytes, plus implicit trailing zero 240 D0 n-1 data bytes The data bytes, no implicit trailing zero 241 D1 Unused (resume preempted packet) 242 D2 Unused (reserved for future use) 243 D3-DF nothing a run of (n-D0) zeroes 244 E0-FE n-E0 data bytes The data bytes, plus two trailing zeroes 245 FF Unused (PPP error) 247 Code byte hex 00 is never used, in order to provide the required 248 "zero elimination" property. 250 Code byte hex D1 is never used (although value D1 may appear as a 251 data byte). If a COBS receiver observes that the first byte after a 252 framing marker is value D1, then it means that this new "packet" of 253 PPP data resumes transmission of a previously preempted packet (see 254 section 3.4). 256 Code byte hex D2 is never used (although value D2 may appear as a 257 data byte). Code byte hex D2 is reserved for future use. 259 Code byte hex FF is never used (although value FF may appear as a 260 data byte). If a COBS receiver observes that the first byte after a 261 framing marker is value FF, then this indicates that an error has 262 occurred (see section 3.5). 264 When negotiated, COBS goes into effect when LCP reaches the Open 265 state. When COBS is in effect, subsequent frames, including LCP mes- 266 sages such as Protocol-Reject, must be sent using COBS. If LCP 267 leaves the Open state, then COBS must be disabled. If LCP is renego- 268 tiated or if the peer is restarted, then COBS may be disabled 269 silently; this is detected by the procedure in section 3.5. 271 An implementation SHOULD disable COBS transmission before sending an 272 LCP Terminate-Request message. 274 3.1. Frame Transmission 276 As with AHDLC and Octet Synchronous encoding, a 7E is used to mark 277 the frame boundary. This value is guaranteed never to occur within 278 COBS encoded data. 280 The COBS zero elimination procedure effectively searches the packet 281 for the first occurrence of value zero. To simplify the encoding 282 procedure, all packets are treated as though they end with a trailing 283 zero at the very end, after the standard CRC. This "phantom" octet 284 of hex 00 is automatically discarded after decoding at the receiving 285 end to correctly reconstruct the original packet data. 287 The number of octets up to and including the first zero determines 288 the code to be output. If this number is 207 or fewer, then this 289 number is output as the code byte, followed by the actual non-zero 290 bytes themselves. The zero is skipped and not output; the receiver 291 will automatically add the zero back in as part of the decoding pro- 292 cess. If there are 207 or more non-zero bytes, then code hex D0 is 293 output, followed by the first 207 non-zero bytes. This process is 294 repeated until all of the bytes of the packet (including the phantom 295 trailing zero at the end) have been encoded. 297 As an optional optimization, if the receiver has indicated its desire 298 to receive zero-pair and zero-run codes in its COBS Configuration 299 Option, then the transmitter MAY elect to encode zero pairs and zero 300 runs more efficiently. If a pair of 00 octets are found in the input 301 data after 0 to 30 non-zero octets, then the count of non-zero octets 302 plus E0 is output, followed by the non-zero octets, and both 00 303 octets in the input data are skipped. If a run of three to fifteen 304 00 octets are found in the input data, then the count of these 00 305 octets plus D0 is output and the 00 octets in the input data are 306 skipped. See section 3.3 below for more details. 308 If the receiver has indicated that it supports packet preemption and 309 the sender is also configured to support it, then it is possible to 310 preempt the state of the current COBS packet within two bytes and 311 send another. If preemption is required for a high-priority packet, 312 then the output state is checked. If the output is idle (no COBS 313 output is in progress) then the packet is sent normally. If the out- 314 put is busy (at least one data octet has been output for a packet in 315 progress), then an error is forced to interrupt the current packet 316 and the current packet being transmitted is saved but the COBS encod- 317 ing state is discarded, and the high-priority packet is then sent 318 using COBS encoding. When the high-priority packet is complete and 319 the terminating 7E has been sent, the sender MAY resume the saved 320 packet by issuing a D1 code after the terminating 7E, and then res- 321 tarting COBS encoding. If a subsequent high-priority packet requires 322 transmission instead, then it MAY be sent immediately. See section 323 3.4 below for more details. 325 Note that both of these options are proper supersets of the basic 326 encoding, so a transmitter that does not support an option which the 327 receiver does support will always send data that the receiver can 328 correctly decode. Likewise, if the receiver does not support a given 329 option, the transmitter MUST disable its use of this encoding. This 330 arrangement allows the LCP negotiation for COBS to be quite simple. 332 The COBS count code FF is never used. Since a COBS count always fol- 333 lows a 7E, this means that a COBS encoder will never generate 7E FF. 334 This sequence is instead used to disable COBS in the event that LCP 335 is renegotiated; see section 3.5. 337 3.2. Frame Reception 339 The frame boundaries are located by a 7E as with AHDLC and Octet Syn- 340 chronous encodings. A frame boundary in the input stream terminates 341 the decoding process. If the boundary occurs at the end of a COBS 342 code block then the packet is deemed complete and the final trailing 343 ("phantom") zero is removed before the packet is passed to the higher 344 layer for processing. If the boundary occurs within a COBS code 345 block then this is an error or, if the receiver supports it, a poten- 346 tial packet preemption. See section 3.4 below for more details on 347 packet preemption. 349 If the first octet of the frame is hex FF, then recovery is attempted 350 as in section 3.5. Otherwise, the stream of octets within a within a 351 frame is transformed by converting all instances of 00 to 7E. If the 352 first octet of the frame is hex D1, then this "packet" resumes 353 transmission of a previously preempted packet. See section 3.4 below 354 for more details on packet preemption. Otherwise, the COBS decoder 355 decodes the encoded byte stream as described below: 357 The COBS decoder reads the first byte (the code byte). 359 If the octet is D0, then 207 octets of data are copied from the input 360 stream to the frame, and no 00 octets are appended. 362 Otherwise, if the most significant four bits are 1101, and ZPE/ZRE is 363 implemented in the receiver, then the least significant four bits are 364 used as a count of 00 octets to append to the frame data. If ZPE/ZRE 365 is not implemented in the receiver, then this is an error. 367 Otherwise, if the most significant three bits are 111, and ZPE/ZRE is 368 implemented in the receiver, then this encodes a run followed by a 369 pair of zeroes. The least significant five bits are used as a count 370 of octets to read from the input data stream. These octets are 371 copied to the frame being decoded, and then two 00 octets are 372 appended to the frame data. If ZPE/ZRE is not implemented in the 373 receiver, then this is an error. 375 Otherwise, the value of the octet is a counter. Count-1 octets of 376 the input stream are copied to the frame and a single 00 octet is 377 appended. 379 The decoding process then continues by reading the next code byte 380 from the input and repeating the decoding process described above 381 until all bytes of the input have been consumed. 383 3.3. Zero-pair and zero-run encoding 385 The goal of COBS encoding is to provide a standard that is suitable 386 for use on both the highest speed links and the lowest speed links. 388 One dilemma that faces designers of higher level protocols today is 389 that for efficiency at very high speeds it is beneficial to align 390 fields to 64-bit or even 128-bit boundaries. The IPv6 header format 391 is an example of this trend. Unfortunately this can often mean 392 inserting padding zeroes between fields to ensure proper alignment, 393 thereby wasting precious bandwidth when these packets are sent over 394 low speed links. Another common practice is for protocol designers 395 to define fields that are reserved for future expansion, accompanied 396 by the familiar phrase "MUST be set to zero on transmission and 397 ignored on reception." These extra unnecessary zeroes in packets also 398 waste bandwidth. 400 The purpose of COBS's zero-pair and zero-run encoding is to remove 401 this protocol designers' dilemma. COBS's zero-pair and zero-run 402 encoding can "compress out" block of zeroes from packet data, thereby 403 making the cost of these extra zeroes negligible. This allows proto- 404 col designers to design one single format for their protocol, without 405 being forced to choose between either favoring high speed or favoring 406 low speed links. 408 Particularly for string fields, it can be convenient to have a fixed 409 size field that is considerably longer than the typical string length 410 it holds, in order to keep a simple fixed-format packet structure 411 while at the same time not unduly limiting the length of string that 412 may be used in that field. As long as the unused bytes are zero- 413 filled, zero-pair and zero-run encoding will "compress out" those 414 unused bytes, making their cost negligible. 416 Zero-pair and zero-run encoding are not intended to compete with more 417 sophisticated (and more computationally costly) compression algo- 418 rithms such as Lempel-Ziv [4] or Huffman [5] encoding. On the very 419 slowest links, these compression algorithms may still be appropriate. 420 The highest compression ratios are achieved by algorithms such as Van 421 Jacobson's TCP header compression which take advantage of interdepen- 422 dencies between packets. However, this means that a single packet 423 loss on the link can cause multiple packets to be unrecoverable, 424 which may not be appropriate for technologies such as wireless links 425 where packet loss rates are already relatively high. 427 One aspect of zero-run compression is that on reception this 428 compressed data has to be expanded back to its original size. On the 429 very highest speed links, where the link data rate is comparable to 430 the memory system bandwidth, this potential 15:1 expansion at the 431 receiver may be unacceptable. For this reason, the receiver may 432 request in its COBS Configuration Option that the sender *not* gen- 433 erate zero-pair (hex E0-FE) or zero-run (hex D3-DF) COBS codes. If 434 the receiver does not indicate its desire to receive zero-pair and 435 zero-run codes in its COBS Configuration Option, the transmitter MUST 436 not generate these codes. 438 The reverse situation -- of a COBS transmitter that does not imple- 439 ment zero-pair and zero-run encoding -- needs no negotiation. Even 440 if the receiver indicates its willingness to receive zero-pair and 441 zero-run codes of a transmitter that does not implement them, the 442 transmitter's output, while not containing those codes, will still be 443 a perfectly legal encoding of the packets. It may be a sub-optimal 444 encoding, but it is still a legal encoding that the receiver will 445 decode correctly. 447 3.4. Packet Preemption 449 On low speed links there can be conflicting goals. To provide effi- 450 ciency, it is desirable to allow packets to be as large as possible. 451 However, if a small high-priority packet arrives just as a large 452 low-priority packet begins transmission, the high-priority packet is 453 delayed until transmission of the large low-priority packet is com- 454 plete, which favors making the maximum packet size relatively small. 455 Packet preemption solves this dilemma by allowing the link to suspend 456 transmission of a low-priority packet immediately whenever a high- 457 priority packet needs to be sent, and then resume transmission of the 458 low-priority packet afterwards. 460 COBS packet preemption allows us to do this with at most two bytes of 461 additional overhead compared to sending the packets in the normal 462 sequential manner. 464 If the receiver has indicated in its COBS Configuration Option that 465 it supports packet preemption, then the transmitter can preempt a 466 low-priority packet at any time simply by forcing an error and then 467 beginning transmission of the high-priority packet. After the high- 468 priority packet(s) has (have) been sent, the sender resumes transmis- 469 sion of the preempted packet by transmitting a code hex D1 (resume 470 preempted packet) and then resuming COBS encoded transmission from 471 the first untransmitted byte of the preempted packet. 473 During packet transmission, the transmitter is either in a state in 474 which it is transmitting data within a COBS block or it has just sent 475 the last octet of a COBS block and is preparing to send the code byte 476 to start a new COBS block. To force an error for packet preemption, 477 a 7E code must be sent within the data portion of a COBS block. 478 Therefore, if the transmitter is preparing to send a new counter when 479 preemption is necessary, it should either calculate and send that 480 counter first, or it should send a dummy counter of 02. In any case, 481 the 7E that follows will signal the preemption. The receiver will 482 detect an incomplete COBS code block as an error. 484 A receiver that supports packet preemption must maintain two packet 485 receive buffers. The two buffers are equal in status, but at any 486 point in time one buffer is the "active buffer" and the other is the 487 "inactive buffer". If an error occurs in the course of COBS decod- 488 ing, then the receiver treats it as a possible indication of packet 489 preemption. The receiver remembers the number of decoded bytes that 490 have been written into the active buffer, and the other buffer now 491 becomes the active buffer. The receiver then proceeds to receive 492 packets as normal into this buffer. When the receiver observes a 493 packet that begins with the byte value hex D1, it recognizes this as 494 an indication to resume a previously preempted packet. The active 495 and inactive buffers are again swapped, but now instead of beginning 496 writing to the start of the buffer, the receiver proceeds to append 497 bytes after any data that is already there. In the unlikely event 498 that the inactive buffer contains no bytes of data, this is not con- 499 sidered an error. A previous packet may have been preempted before 500 even a single byte of data was decoded, in which case having zero 501 bytes of data already in the buffer when the packet resumes is in 502 fact correct. 504 The following example shows a large packet preempted by two small 505 ones. The large packet contains the hex values "01 02 03 04 05 06 506 07" and the two small packets contain the values "11 12 13" and "21 507 22 23" respectively. If the large packet is preempted after three 508 bytes, the correct encoding of this data is: 510 7E 08 01 02 03 7E 04 11 12 13 7E 04 21 22 23 7E D1 05 04 05 06 07 7E 512 The byte-stream begins with the framing marker 7E. The encoder then 513 indicates that it plans to send seven non-zero bytes (COBS code hex 514 08). It then sends the first three of those non-zero bytes (01 02 515 03) before a pair of high-priority packets arrive. The sender then 516 interrupts the transmission of the low-priority packet with another 517 framing marker 7E, and sends the two high-priority packets. The 518 receiver holds the three bytes of the partially received packet in 519 the inactive buffer while it is receiving the high-priority packets. 520 When the high-priority packets are complete, the sender sends a code 521 hex D1 to indicate that it is resuming transmission of the preempted 522 packet. The encoder indicates that it plans to send four non-zero 523 bytes (COBS code hex 05) and sends the remaining four bytes of the 524 low-priority packet. 526 Since packet preemption is most useful on low-speed links, high-speed 527 COBS implementations may elect not to implement packet preemption. 528 If the receiver does not indicate that is supports packet preemption 529 in its COBS Configuration Option, the transmitter MUST NOT preempt 530 packets. 532 The reverse situation -- of a COBS transmitter that does not imple- 533 ment packet preemption -- needs no negotiation. Even if the receiver 534 indicates its willingness to allow packet preemption, the 535 transmitter's output, while not containing any packet preemption, 536 will still be a perfectly legal steam of encoded packets. 538 3.5. Recovery on LCP Renegotiation 540 Since all implementations are required to send LCP frames with the 541 standard address and control fields, regardless of prior negotiation, 542 all LCP frames must begin with the hex sequence FF 03 C0 21 before 543 any byte-stuffing occurs. 545 The first octet of COBS data is always a counter value. Because of 546 the encoding methods chosen, this counter is never sent as FF. This 547 is to allow for recovery in case LCP is renegotiated or synchroniza- 548 tion is lost with the peer. Since LCP frames must begin with FF, any 549 frame seen when COBS is in use which begins with hex FF must 550 represent the start of an LCP frame without COBS enabled. The 551 receiver should disable COBS and revert back to Octet Synchronous or 552 AHDLC decoding as appropriate. 554 COBS speaking implementations using AHDLC MUST NOT default to escap- 555 ing FF when sending LCP frames unless COBS is explicitly disabled 556 since that would compromise this recovery mechanism. 558 3.6. Handling of Corrupted Data 560 If data are lost or corrupted during transmission, it is desirable 561 that the errors affect a minimum number of packets. For COBS, the 562 error characteristics are similar to AHDLC and Octet Synchronous 563 encodings. 565 If one of the code byte octets is lost or corrupted, then the block 566 will be miscounted. This is likely to ultimately result in the 567 inclusion of the trailing 7E within the data portion of an erroneous 568 COBS block. The receiver will detect this as either an error (if it 569 does not support preemption) or as a preempted message. In the 570 latter case, the falsely preempted message will be discarded when the 571 next true preemption occurs. If the 7E still falls on a natural 572 boundary between COBS blocks, then COBS will not detect the error, 573 but the standard Frame Check Sequence (FCS) will be used to detect 574 the corruption. 576 If one of the data octets is corrupted, then the FCS will be used to 577 detect the corruption. As above, lost data octets will result in a 578 trailing 7E being included within the data portion of a message and 579 result in the loss of that one packet. 581 If the preemption-resume signal (D1) is lost, then the resumed data 582 stream will be treated as an independent frame and will be discarded 583 with an FCS error. 585 If data are corrupted such as to deliver 7E FF to a COBS receiver, 586 that receiver should restart LCP renegotiation due to the apparent 587 loss of state and should then restart COBS. For COBS encoding to be 588 viable on a given link, the probability of this type of corruption 589 must be acceptably low. 591 As with AHDLC and Octet-Synchronous, the loss of a 7E marker between 592 frames will result in the loss of those two frames. 594 4. Source Code 596 Two implementations are given for reference. The first implementa- 597 tion is a basic version which encodes and decodes linear blocks and 598 includes ZPE/ZRE. It is able to handle multiple blocks within one 599 coding unit by use of multiple sequential invocations. 601 The second is designed for a system using BSD-like mbufs for the PPP 602 stack and using a very simple FIFO buffer interface for data transmit 603 and receive. It includes standard 16-bit FCS generation and checking 604 and implements both the ZPE/ZRE option and the packet preemption 605 option. 607 4.1. Linear buffer encoding and decoding 609 typedef unsigned char u_char; /* 8 bit quantity */ 610 typedef enum 611 { 612 Unused = 0x00, /* Unused (framing character placeholder) */ 613 DiffZero = 0x01, /* Range 0x01 - 0xCE: */ 614 DiffZeroMax = 0xCF, /* n-1 explicit characters plus a zero */ 615 Diff = 0xD0, /* 207 explicit characters, no added zero */ 616 Resume = 0xD1, /* Unused (resume preempted packet) */ 617 Reserved = 0xD2, /* Unused (reserved for future use) */ 618 RunZero = 0xD3, /* Range 0xD3 - 0xDF: */ 619 RunZeroMax = 0xDF, /* 3-15 zeroes */ 620 Diff2Zero = 0xE0, /* Range 0xE0 - 0xFE: */ 621 Diff2ZeroMax = 0xFE, /* 0-30 explicit characters plus 2 zeroes */ 622 Error = 0xFF /* Unused (PPP LCP renegotiation) */ 623 } StuffingCode; 625 /* These macros examine just the top 3/4 bits of the code byte */ 626 #define isDiff2Zero(X) (((X) & 0xE0) == (Diff2Zero & 0xE0)) 627 #define isRunZero(X) (((X) & 0xF0) == (RunZero & 0xF0)) 629 /* Convert from single-zero code to corresponding double-zero code */ 630 #define ConvertZP (Diff2Zero - DiffZero) 632 /* Allow generation of zero pair and zero run code blocks? */ 633 int ZPZR = 1; 635 /* Highest single-zero code with a corresponding double-zero code */ 636 #define MaxConvertible (ZPZR ? Diff2ZeroMax - ConvertZP : 0) 638 /* Convert to/from 0x7E-free data for sending over PPP link */ 639 static u_char Tx(u_char x) { return(x == 0x7E ? 0 : x); } 640 static u_char Rx(u_char x) { return(x == 0 ? 0x7E : x); } 642 /* 643 * StuffData stuffs "length" bytes of data from the buffer "ptr", 644 * writing the output to "dst", and returning as the result the 645 * address of the next free byte in the output buffer. 646 * The size of the output buffer must be large enough to accommodate 647 * the encoded data, which in the worst case may expand by almost 648 * 0.5%. The exact amount of safety margin required can be 649 * calculated using (length+1)/206, rounded *up* to the next whole 650 * number of bytes. E.g. for a 1K packet, the output buffer needs to 651 * be 1K + 5 bytes to be certain of accommodating worst-case packets. 652 */ 654 #define FinishBlock(X) \ 655 (*code_ptr = Tx(X), code_ptr = dst++, code = DiffZero) 657 static u_char *StuffData(const u_char *ptr, unsigned int length, 658 u_char *dst, u_char **code_ptr_ptr) 659 { 660 const u_char *end = ptr + length; 661 u_char *code_ptr = *code_ptr_ptr; 662 u_char code = DiffZero; 664 /* Recover state from last call, if applicable */ 665 if (code_ptr) code = Rx(*code_ptr); 666 else code_ptr = dst++; 668 while (ptr < end) 669 { 670 u_char c = *ptr++; /* Read the next character */ 671 if (c == 0) /* If it's a zero, do one of these operations */ 672 { 673 if (isRunZero(code) && code < RunZeroMax) code++; 674 else if (code == Diff2Zero) code = RunZero; 675 else if (code <= MaxConvertible) code += ConvertZP; 676 else FinishBlock(code); 677 } 678 else /* else, non-zero; do one of these operations */ 679 { 680 if (isDiff2Zero(code)) FinishBlock(code - ConvertZP); 681 else if (code == RunZero) FinishBlock(Diff2Zero); 682 else if (isRunZero(code)) FinishBlock(code-1); 683 *dst++ = Tx(c); 684 if (++code == Diff) FinishBlock(code); 685 } 686 } 687 *code_ptr_ptr = code_ptr; 688 FinishBlock(code); 689 return(dst-1); 690 } 692 /* 693 * UnStuffData decodes "srclength" bytes of data from the buffer 694 * "ptr", writing the output to "dst". If the decoded data does not 695 * fit within "dstlength" bytes or any other error occurs, then 696 * UnStuffData returns NULL. 697 */ 698 static u_char *UnStuffData(const u_char *ptr, unsigned int srclength, 699 u_char *dst, unsigned int dstlength) 700 { 701 const u_char *end = ptr + srclength; 702 const u_char *limit = dst + dstlength; 703 while (ptr < end) 704 { 705 int z, c = Rx(*ptr++); 706 if (c == Error || c == Resume || c == Reserved) return(NULL); 707 else if (c == Diff) { z = 0; c--; } 708 else if (isRunZero(c)) { z = c & 0xF; c = 0; } 709 else if (isDiff2Zero(c)) { z = 2; c &= 0x1F; } 710 else { z = 1; c--; } 712 while (--c >= 0 && dst < limit) *dst++ = Rx(*ptr++); 713 while (--z >= 0 && dst < limit) *dst++ = 0; 714 } 715 if (dst < limit) return(dst-1); 716 else return(NULL); 717 } 719 /* Example showing use of chained StuffData calls */ 720 unsigned int StuffExample(const u_char *head, unsigned int hlength, 721 const u_char *data, unsigned int dlength, 722 u_char *dst) 723 { 724 u_char *ptr = dst; 725 u_char *stuffstate = NULL; 727 /* First stuff the packet header into the buffer */ 728 ptr = StuffData(head, hlength, ptr, &stuffstate); 730 /* Then append the packet body to the stuffed header */ 731 ptr = StuffData(data, dlength, ptr, &stuffstate); 733 /* Then return the total length of data generated */ 734 return(ptr-dst); 735 } 737 4.2. PPP/COBS Encoding with mbufs 739 4.2.1. PPP Context Handling 741 struct cobs_context { 742 /* Transmit encoding state */ 743 struct txcontext { 744 struct mbuf *bufs,*nextp; 745 short count,zskip,lcount; 746 } tx[2]; 747 int txpri,txendofframe,txintr; 748 int txallowpri,txallowzxe; 750 /* Receive decoding state */ 751 struct mbuf *mhead,*mtail; 752 struct mbuf *savedpkt; 753 int rxcount,rxlcount,zadd; 754 u_short rxfcs; 755 u_short savedfcs; 756 u_char rxlchar; 757 }; 759 /* 760 * Simple context initialization. User is responsible for setting 761 * cb.txallowpri and cb.txallowzxe based on the outcome of PPP 762 * negotiation. 763 */ 764 void 765 init_cobs_context(struct cobs_context *cb) 766 { 767 bzero(cb,sizeof(*cb)); 768 cb->rxfcs = 0xFFFF; 769 } 771 4.2.2. PPP Frame Transmission 773 /* 774 * This is called once for each transmit-FIFO-empty interrupt. It 775 * takes a pointer to the transmit FIFO buffer and the available 776 * room in that buffer, and returns the number of bytes inserted. 777 * Priority is supported even if the peer doesn't support COBS 778 * priority interruption. If txallowpri is cleared, then priority 779 * packets are sent out on packet boundaries rather than as 780 * interrupts. 781 */ 782 int 783 ppp_cobs_xmit(struct cobs_context *cb, u_char *buffer, int buflen) 784 { 785 u_char *dp,chr,*obuf; 786 int len,count; 787 struct mbuf *mb,*mb2; 788 struct txcontext *tx; 790 if (buflen <= 0 || buffer == NULL || cb == NULL) 791 return 0; 793 /* 794 * If there's a high priority packet waiting and we're in the 795 * middle of sending a low priority one, then send the escape 796 * flag and switch. 797 */ 798 obuf = buffer; 799 if (!cb->txendofframe && cb->tx[1].nextp != NULL && 800 cb->txpri == 0) { 801 if (cb->tx[0].bufs == NULL) 802 cb->txpri = 1; 803 else if (buflen >= 2 && cb->txallowpri) { 804 cb->txpri = 1; 805 if (cb->tx[0].count == 0) { 806 *buffer++ = 0x02; 807 buflen--; 808 } 809 *buffer++ = 0x7E; 810 buflen--; 811 cb->tx[0].count = cb->tx[0].zskip = cb->tx[0].lcount = 0; 812 cb->txintr = 1; 813 cb->tx[1].lcount = -1; 814 } 815 } 817 tx = cb->tx + cb->txpri; 818 if ((mb = tx->bufs) == NULL) { 819 if ((mb = tx->nextp) != NULL) { 820 tx->nextp = mb->m_act; 821 mb->m_act = NULL; 822 } 823 } 824 count = tx->count; 825 while (buflen > 0) { 826 if (cb->txendofframe) { 827 switch (cb->txendofframe) { 828 case 1: 829 /* 830 * If the zero removal falls right on the end of 831 * the packet, then we need to add a dummy code to 832 * insert a 00 byte which will be deleted by the 833 * receiver. 834 */ 835 *buffer++ = 0x01; 836 buflen--; 837 cb->txendofframe = 2; 838 break; 839 case 2: 840 /* Packet done; send frame mark */ 841 *buffer++ = 0x7E; 842 count = 0; 843 buflen--; 844 cb->txendofframe = 0; 845 tx->lcount = -1; 846 break; 848 } 849 continue; 850 } 851 if (count == 0) { 852 if (mb == NULL) { 853 tx->bufs = mb; 854 tx->count = count; 855 if (cb->txpri == 1 && cb->tx[0].bufs != NULL) { 856 cb->txpri = 0; 857 tx = cb->tx; 858 mb = tx->bufs; 859 } else { 860 if (cb->tx[0].nextp == NULL && 861 cb->tx[1].nextp == NULL) 862 break; 863 cb->txpri = (cb->tx[1].nextp != NULL); 864 tx = cb->tx + cb->txpri; 865 tx->bufs = mb = tx->nextp; 866 tx->nextp = mb->m_act; 867 mb->m_act = NULL; 868 } 869 count = tx->count; 870 if (cb->txpri == 0 && cb->txintr) { 871 cb->txintr = 0; 872 *buffer++ = 0xD1; /* Resume packet */ 873 buflen--; 874 } 875 continue; 876 } 878 /* Do look-ahead for encoding modes */ 879 dp = mtod(mb,u_char *); 880 if (*dp == 0 && cb->txallowzxe) { 881 mb2 = mb; 882 len = mb->m_len; 883 while (mb2 != NULL && count < 15) 884 if (*dp++ == 0) { 885 count++; 886 if (--len <= 0) { 887 do { 888 mb2 = mb2->m_next; 889 if (mb2 == NULL) 890 break; 891 dp = mtod(mb2,u_char *); 892 len = mb2->m_len; 893 } while (len <= 0); 894 } 895 } else 896 break; 897 if (mb2 == NULL) 898 count++; /* Include phantom zero byte here */ 899 } 900 if (count >= 3) { 901 tx->zskip = count; 902 chr = 0xD0 + count; 903 count = 0; 904 } else { 905 dp = mtod(mb,u_char *); 906 len = mb->m_len; 907 mb2 = mb; 908 count = 0; 909 while (mb2 != NULL && count < 207) 910 if (*dp++ != 0) { 911 count++; 912 if (--len <= 0) { 913 do { 914 mb2 = mb2->m_next; 915 if (mb2 == NULL) 916 break; 917 dp = mtod(mb2,u_char *); 918 len = mb2->m_len; 919 } while (len <= 0); 920 } 921 } else 922 break; 923 if (count == 207) 924 chr = 0xD0; 925 else { 926 chr = count+1; 927 tx->zskip = 1; 928 if (count <= 30 && cb->txallowzxe && 929 mb2 != NULL) { 930 if (len <= 1) 931 do { 932 mb2 = mb2->m_next; 933 if (mb2 == NULL) 934 break; 935 dp = mtod(mb2,u_char *); 936 len = mb2->m_len; 937 } while (len <= 0); 938 if (mb2 == NULL || *dp == 0) { 939 chr = count + 0xE0; 940 tx->zskip = 2; 941 } 942 } 943 } 945 } 946 tx->lcount = chr; 947 } else { 948 if (mb->m_len == 0) { 949 mb = m_free(mb); 950 continue; 951 } 952 chr = *mtod(mb,u_char *); 953 mb->m_len--; 954 mb->m_off++; 955 count--; 956 } 957 if (chr == 0x7E) 958 chr = 0; 959 *buffer++ = chr; 960 buflen--; 961 if (count == 0) { 962 count = tx->zskip; 963 while (mb != NULL && count > 0) { 964 len = mb->m_len; 965 if (len > count) { 966 mb->m_len -= count; 967 mb->m_off += count; 968 count = 0; 969 break; 970 } 971 count -= len; 972 mb = m_free(mb); 973 } 974 tx->zskip = 0; 975 while (mb != NULL && mb->m_len == 0) 976 mb = m_free(mb); 977 if (mb == NULL) 978 if (count == 0 && tx->lcount != 0xD0) 979 cb->txendofframe = 1; 980 else 981 cb->txendofframe = 2; 982 count = 0; 983 } 984 } 985 tx->bufs = mb; 986 tx->count = count; 987 return buffer-obuf; 988 } 990 /* 991 * This is called once for each out-bound packet. The arguments are 992 * the COBS state structure, the pointer to the out-bound mbuf chain, 993 * and the priority level of the packet (0 or 1 for low or high). 994 */ 995 void 996 ppp_cobs_enqueue(struct cobs_context *cb, struct mbuf *mb, int pri) 997 { 998 u_short fcs; 999 u_char *dp; 1000 int len; 1001 struct mbuf *mb2; 1002 struct txcontext *tx; 1004 /* 1005 * It turns out to be horribly complicated to support both the 1006 * scan-ahead functions and the CRC calculation at the same time 1007 * since the last byte of the CRC (or even both bytes) may be 00. 1008 * Thus, it is necessary in this implementation to do the CRC 1009 * first and the COBS encoding second in two separate steps. If 1010 * the COBS output were fed into a simple linear output buffer 1011 * big enough to hold the largest packet, then this could be 1012 * greatly simplified. 1013 */ 1014 if (cb == NULL || mb == NULL) 1015 return; 1016 fcs = 0xFFFF; 1017 for (mb2 = mb; mb2 != NULL; mb2 = mb2->m_next) { 1018 dp = mtod(mb2,u_char *); 1019 for (len = mb2->m_len; len > 0; len--) 1020 fcs = (fcs >> 8) ^ fcstab[(fcs ^ *dp++) & 0xff]; 1021 } 1022 mb2 = dtom(dp); 1023 if (mb2->m_len+mb2->m_off > MMAXOFF-2) { 1024 mb2->m_next = m_get(M_DONTWAIT,MT_PPPTX); 1025 mb2 = mb2->m_next; 1026 dp = mtod(mb2,u_char *); 1027 } 1028 fcs = ~fcs; 1029 dp[0] = fcs&0xFF; 1030 dp[1] = fcs>>8; 1031 mb2->m_len += 2; 1033 tx = cb->tx + pri; 1034 if (tx->nextp == NULL) 1035 tx->nextp = mb; 1036 else { 1037 for (mb2 = tx->nextp; mb2->m_act != NULL; mb2 = mb2->m_act) 1038 ; 1039 mb2->m_act = mb; 1040 } 1042 } 1044 4.2.3. Frame Reception 1046 /* 1047 * This is called once for each FIFO-full-or-stale interrupt. It 1048 * takes a pointer to the COBS state structure, the FIFO buffer 1049 * pointer, and the length of the data in the FIFO. It in turn 1050 * calls send_up_packet(struct mbuf *) if a packet has been received, 1051 * or ppp_recv_error(void) if an error occurs, or disable_cobs(void) 1052 * if the peer is apparently restarting LCP negotiation. 1053 */ 1054 void 1055 ppp_cobs_rcv(struct cobs_context *cb, u_char *buffer, int len) 1056 { 1057 u_char *dp = NULL,chr,rxlchar; 1058 struct mbuf *mb,*mb2; 1059 int mlen = 0,count; 1060 u_short fcs; 1062 if ((mb = cb->mtail) != NULL) { 1063 mlen = mb->m_len; 1064 dp = mtod(mb,u_char *) + mlen; 1065 } 1066 fcs = cb->rxfcs; 1067 count = cb->rxcount; 1068 rxlchar = chr = cb->rxlchar; 1069 while (len > 0) { 1070 len--; 1071 chr = *buffer++; 1072 if (chr == 0x7E) { 1073 rxlchar = chr; 1074 if (count > 0) { 1075 if (mb != NULL) 1076 mb->m_len = mlen; 1077 m_freem(cb->savedpkt); 1078 cb->savedfcs = fcs; 1079 cb->savedpkt = cb->mhead; 1080 cb->zadd = 0; 1081 mb = cb->mhead = NULL; 1082 } 1083 while (cb->zadd > 1) { 1084 if (mb == NULL || mlen >= MLEN) { 1085 mb2 = m_get(M_DONTWAIT,MT_PPPRX); 1086 if (mb2 == NULL) 1087 goto ppp_input_error; 1088 if (mb != NULL) { 1089 mb->m_len = mlen; 1090 mb->m_next = mb2; 1091 } else 1092 cb->mhead = mb2; 1093 mb = mb2; 1094 cb->mtail = mb; 1095 dp = mtod(mb,u_char *); 1096 mlen = 0; 1097 } 1098 *dp++ = 0; 1099 fcs = (fcs >> 8) ^ fcstab[fcs & 0xff]; 1100 mlen++; 1101 cb->zadd--; 1102 } 1103 if (mb == NULL) 1104 m_freem(cb->mhead); 1105 else if (count > 0 || fcs != 0xF0B8) { 1106 ppp_input_error: 1107 if (cb->mhead->m_next != NULL || mlen > 4) 1108 ppp_recv_error(); 1109 m_freem(cb->mhead); 1110 } else { 1111 mb->m_len = mlen; 1112 m_adj(cb->mhead,-2); /* Strip the CRC */ 1113 send_up_packet(cb->mhead); 1114 } 1115 cb->mtail = cb->mhead = mb = NULL; 1116 count = cb->rxcount = cb->rxlcount = cb->zadd = 0; 1117 fcs = cb->rxfcs = 0xFFFF; 1118 continue; 1119 } 1120 if (chr == 0xD1 && rxlchar == 0x7E) { /* Resume code */ 1121 m_freem(cb->mhead); 1122 mb = cb->mhead = cb->savedpkt; 1123 if (mb != NULL) { 1124 while (mb->m_next != NULL) 1125 mb = mb->m_next; 1126 cb->mtail = mb; 1127 mlen = mb->m_len; 1128 dp = mtod(mb,u_char *) + mlen; 1129 } else { 1130 dp = NULL; 1131 mlen = 0; 1132 } 1133 fcs = cb->savedfcs; 1134 cb->savedpkt = NULL; 1135 rxlchar = chr; 1136 continue; 1138 } 1139 rxlchar = chr; 1140 if (chr == 0) 1141 chr = 0x7E; 1142 for (;;) { 1143 if (mb == NULL || mlen >= MLEN) { 1144 mb2 = m_get(M_DONTWAIT,MT_PPPRX); 1145 if (mb2 == NULL) 1146 goto ppp_input_error; 1147 if (mb != NULL) { 1148 mb->m_len = mlen; 1149 mb->m_next = mb2; 1150 } else 1151 cb->mhead = mb2; 1152 mb = mb2; 1153 cb->mtail = mb; 1154 dp = mtod(mb,u_char *); 1155 mlen = 0; 1156 } 1157 if (count > 0) { 1158 *dp++ = chr; 1159 fcs = (fcs >> 8) ^ fcstab[(fcs ^ chr) & 0xff]; 1160 mlen++; 1161 count--; 1162 break; 1163 } 1164 if (cb->zadd == 0) { 1165 /* This can happen only if the peer starts renegotiating LCP */ 1166 if (chr == 0xFF) { 1167 disable_cobs(); 1168 m_freem(cb->mhead); 1169 m_freem(cb->savedpkt); 1170 cb->mhead = cb->mtail = cb->savedpkt = NULL; 1171 return; 1172 } 1173 switch (chr & 0xF0) { 1174 case 0xD0: 1175 cb->zadd = chr - 0xD0; 1176 count = 0; 1177 break; 1178 case 0xE0: 1179 case 0xF0: 1180 count = chr - 0xE0; 1181 cb->zadd = 2; 1182 break; 1183 default: 1184 cb->zadd = (chr == 0xD0) ? 0 : 1; 1185 count = chr-1; 1187 } 1188 cb->rxlcount = count; 1189 break; 1190 } 1191 cb->zadd--; 1192 *dp++ = 0; 1193 fcs = (fcs >> 8) ^ fcstab[fcs & 0xff]; 1194 mlen++; 1195 } 1196 } 1197 if (mb != NULL) 1198 mb->m_len = mlen; 1199 cb->rxfcs = fcs; 1200 cb->mtail = mb; 1201 cb->rxcount = count; 1202 cb->rxlchar = rxlchar; 1203 } 1205 5. Acknowledgments 1207 This encapsulation method was first described in Stuart Cheshire's 1208 Ph.D. Thesis at Stanford University. 1210 6. References 1212 [1] W. Simpson, "The Point-to-Point Protocol (PPP)", RFC 1661, 1213 07/21/1994 1215 [2] W. Simpson, "PPP in HDLC-like Framing", RFC 1662, 07/1994 1217 [3] S. Cheshire and M. Baker, "Consistent Overhead Byte Stuffing," 1218 ACM SIGCOMM - Cannes, France, September 1997. 1220 [4] J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data 1221 Compression," IEEE Transactions on Information Theory, May 1977. 1223 [5] D. A. Huffman, "A Method for the Construction of Minimum- 1224 Redundancy Codes," Proceedings of the IRE, Vol.40, No.9, September 1225 1952, pp.1098-1101. 1227 7. Authors' Addresses 1229 James Carlson 1230 IronBridge Networks 1231 5 Corporate Drive 1232 Andover MA 01810-2448 1234 Phone: +1 978 691 4644 1235 Fax: +1 978 691 6300 1236 Email: carlson@wing.net 1238 Stuart Cheshire 1239 Stanford University 1240 Stanford CA 94305 1242 Phone: +1 650 723 9427 1243 Email: cheshire@cs.stanford.edu 1245 Mary Baker 1246 Stanford University 1247 Stanford CA 94305 1249 Phone: +1 650 725 3711 1250 Email: mgbaker@cs.stanford.edu