idnits 2.17.1 draft-ietf-rohc-epic-lite-01.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == There is 1 instance of lines with non-ascii characters in the document. == 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 4 instances of too long lines in the document, the longest one being 5 characters in excess of 72. ** The abstract seems to contain references ([1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year -- 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 (February 2002) is 8078 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 2961, but not defined == Unused Reference: '4' is defined on line 1497, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '2' ** Obsolete normative reference: RFC 2234 (ref. '6') (Obsoleted by RFC 4234) Summary: 6 errors (**), 0 flaws (~~), 5 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group R. Price 3 Internet-Draft R. Hancock 4 Expires: August 2, 2002 S. McCann 5 A. Surtees 6 P. Ollis 7 M. West 8 Siemens/Roke Manor 9 February 2002 11 Framework for EPIC-LITE 12 draft-ietf-rohc-epic-lite-01.txt 14 Status of this Memo 16 This document is an Internet-Draft and is in full conformance with 17 all provisions of Section 10 of RFC2026. 19 Internet-Drafts are working documents of the Internet Engineering 20 Task Force (IETF), its areas, and its working groups. Note that 21 other groups may also distribute working documents as Internet- 22 Drafts. 24 Internet-Drafts are draft documents valid for a maximum of six months 25 and may be updated, replaced, or obsoleted by other documents at any 26 time. It is inappropriate to use Internet-Drafts as reference 27 material or to cite them other than as "work in progress." 29 The list of current Internet-Drafts can be accessed at http:// 30 www.ietf.org/ietf/1id-abstracts.txt. 32 The list of Internet-Draft Shadow Directories can be accessed at 33 http://www.ietf.org/shadow.html. 35 This Internet-Draft will expire on August 2, 2002. 37 Copyright Notice 39 Copyright (C) The Internet Society (2002). All Rights Reserved. 41 Abstract 43 This draft describes the framework of the Efficient Protocol 44 Independent Compression (EPIC-LITE) scheme. 46 The RObust Header Compression ROHC [1] scheme is designed to compress 47 packet headers over error prone channels. It is built around an 48 extensible core framework that can be tailored to compress new 49 protocol stacks by adding additional ROHC profiles. 51 EPIC-LITE extends the basic ROHC framework by introducing a BNF-based 52 input language that simplifies the creation of new ROHC [1] profiles. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . 8 57 2. Terminology . . . . . . . . . . . . . . . . . . . . . . 8 58 3. The EPIC-LITE framework for generating new ROHC profiles 10 59 3.1 Structure of the EPIC-LITE compressed headers . . . . . 10 60 3.2 Compression and decompression procedures . . . . . . . . 11 61 3.3 BNF input language for creating new ROHC profiles . . . 14 62 3.4 Huffman compression . . . . . . . . . . . . . . . . . . 15 63 4. Overview of the BNF input language for EPIC-LITE . . . . 16 64 4.1 Information stored at compressor and decompressor . . . 18 65 4.2 Generated data . . . . . . . . . . . . . . . . . . . . . 19 66 5. Library of EPIC-LITE encoding methods . . . . . . . . . 20 67 5.1 STATIC . . . . . . . . . . . . . . . . . . . . . . . . . 20 68 5.2 IRREGULAR . . . . . . . . . . . . . . . . . . . . . . . 21 69 5.2.1 IRREGULAR-PADDED . . . . . . . . . . . . . . . . . . . . 21 70 5.3 VALUE . . . . . . . . . . . . . . . . . . . . . . . . . 21 71 5.4 LSB . . . . . . . . . . . . . . . . . . . . . . . . . . 22 72 5.5 UNCOMPRESSED . . . . . . . . . . . . . . . . . . . . . . 22 73 5.6 STACK encoding methods . . . . . . . . . . . . . . . . . 23 74 5.6.1 STACK-TO-CONTROL . . . . . . . . . . . . . . . . . . . . 23 75 5.6.2 STACK-FROM-CONTROL . . . . . . . . . . . . . . . . . . . 23 76 5.6.3 STACK-PUSH-MSN . . . . . . . . . . . . . . . . . . . . . 23 77 5.6.4 STACK-POP-MSN . . . . . . . . . . . . . . . . . . . . . 24 78 5.6.5 STACK-ROTATE . . . . . . . . . . . . . . . . . . . . . . 24 79 5.7 INFERRED encoding methods . . . . . . . . . . . . . . . 24 80 5.7.1 INFERRED-TRANSLATE . . . . . . . . . . . . . . . . . . . 24 81 5.7.2 INFERRED-SIZE . . . . . . . . . . . . . . . . . . . . . 25 82 5.7.3 INFERRED-OFFSET . . . . . . . . . . . . . . . . . . . . 25 83 5.7.4 INFERRED-IP-CHECKSUM . . . . . . . . . . . . . . . . . . 26 84 5.8 NBO . . . . . . . . . . . . . . . . . . . . . . . . . . 26 85 5.9 SCALE . . . . . . . . . . . . . . . . . . . . . . . . . 27 86 5.10 OPTIONAL . . . . . . . . . . . . . . . . . . . . . . . . 27 87 5.11 MANDATORY . . . . . . . . . . . . . . . . . . . . . . . 28 88 5.12 CONTEXT . . . . . . . . . . . . . . . . . . . . . . . . 28 89 5.13 LIST . . . . . . . . . . . . . . . . . . . . . . . . . . 29 90 5.13.1 LIST-NEXT . . . . . . . . . . . . . . . . . . . . . . . 30 91 5.14 FLAG encoding methods . . . . . . . . . . . . . . . . . 31 92 5.14.1 N flag . . . . . . . . . . . . . . . . . . . . . . . . . 31 93 5.14.2 U flag . . . . . . . . . . . . . . . . . . . . . . . . . 32 94 5.15 FORMAT . . . . . . . . . . . . . . . . . . . . . . . . . 32 95 5.16 CRC . . . . . . . . . . . . . . . . . . . . . . . . . . 33 96 5.17 MSN encoding methods . . . . . . . . . . . . . . . . . . 34 97 5.17.1 MSN-LSB . . . . . . . . . . . . . . . . . . . . . . . . 34 98 5.17.2 MSN-IRREGULAR . . . . . . . . . . . . . . . . . . . . . 34 99 5.17.3 SET-MSN . . . . . . . . . . . . . . . . . . . . . . . . 34 100 6. Creating a new ROHC profile . . . . . . . . . . . . . . 35 101 6.1 Profile identifier . . . . . . . . . . . . . . . . . . . 35 102 6.2 Maximum number of header formats . . . . . . . . . . . . 35 103 6.3 Control of header alignment . . . . . . . . . . . . . . 36 104 6.4 Compressed header formats . . . . . . . . . . . . . . . 36 105 7. Security considerations . . . . . . . . . . . . . . . . 37 106 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . 37 107 References . . . . . . . . . . . . . . . . . . . . . . . 37 108 Authors' Addresses . . . . . . . . . . . . . . . . . . . 38 109 A. EPIC-LITE compressor and decompressor . . . . . . . . . 39 110 A.1 Compressor . . . . . . . . . . . . . . . . . . . . . . . 49 111 A.1.1 Step 1: Packet classification . . . . . . . . . . . . . 49 112 A.1.2 Step 2: Using the state machine . . . . . . . . . . . . 50 113 A.1.3 Step 3: Compressing the header . . . . . . . . . . . . . 50 114 A.1.4 Step 4: Determining the indicator flags . . . . . . . . 53 115 A.1.5 Step 5: Encapsulating in ROHC packet . . . . . . . . . . 56 116 A.2 Decompressor . . . . . . . . . . . . . . . . . . . . . . 56 117 A.2.1 Step 1: Decapsulating from ROHC packet . . . . . . . . . 56 118 A.2.2 Step 2: Running the state machine . . . . . . . . . . . 56 119 A.2.3 Step 3: Reading the indicator flags . . . . . . . . . . 56 120 A.2.4 Step 4: Decompressing the fields . . . . . . . . . . . . 59 121 A.2.5 Step 5: Verifying correct decompression . . . . . . . . 60 122 A.3 Offline processing . . . . . . . . . . . . . . . . . . . 61 123 A.3.1 Step 1: Building the header formats . . . . . . . . . . 61 124 A.3.2 Step 2: Generating the indicator flags . . . . . . . . . 66 125 A.4 Library of methods . . . . . . . . . . . . . . . . . . . 73 126 A.4.1 STATIC . . . . . . . . . . . . . . . . . . . . . . . . . 73 127 A.4.2 IRREGULAR . . . . . . . . . . . . . . . . . . . . . . . 74 128 A.4.2.1 IRREGULAR-PADDED . . . . . . . . . . . . . . . . . . . . 75 129 A.4.3 VALUE . . . . . . . . . . . . . . . . . . . . . . . . . 76 130 A.4.4 LSB . . . . . . . . . . . . . . . . . . . . . . . . . . 77 131 A.4.5 UNCOMPRESSED . . . . . . . . . . . . . . . . . . . . . . 79 132 A.4.6 STACK encoding methods . . . . . . . . . . . . . . . . . 80 133 A.4.6.1 STACK-TO-CONTROL . . . . . . . . . . . . . . . . . . . . 80 134 A.4.6.2 STACK-FROM-CONTROL . . . . . . . . . . . . . . . . . . . 81 135 A.4.6.3 STACK-PUSH-MSN . . . . . . . . . . . . . . . . . . . . . 82 136 A.4.6.4 STACK-POP-MSN . . . . . . . . . . . . . . . . . . . . . 83 137 A.4.6.5 STACK-ROTATE . . . . . . . . . . . . . . . . . . . . . . 84 138 A.4.7 INFERRED encoding methods . . . . . . . . . . . . . . . 84 139 A.4.7.1 INFERRED-TRANSLATE . . . . . . . . . . . . . . . . . . . 84 140 A.4.7.2 INFERRED-SIZE . . . . . . . . . . . . . . . . . . . . . 86 141 A.4.7.3 INFERRED-OFFSET . . . . . . . . . . . . . . . . . . . . 86 142 A.4.7.4 INFERRED-IP-CHECKSUM . . . . . . . . . . . . . . . . . . 87 143 A.4.8 NBO . . . . . . . . . . . . . . . . . . . . . . . . . . 88 144 A.4.9 SCALE . . . . . . . . . . . . . . . . . . . . . . . . . 90 145 A.4.10 OPTIONAL . . . . . . . . . . . . . . . . . . . . . . . . 91 146 A.4.11 MANDATORY . . . . . . . . . . . . . . . . . . . . . . . 92 147 A.4.12 CONTEXT . . . . . . . . . . . . . . . . . . . . . . . . 93 148 A.4.13 LIST . . . . . . . . . . . . . . . . . . . . . . . . . . 94 149 A.4.13.1 LIST-NEXT . . . . . . . . . . . . . . . . . . . . . . . 98 150 A.4.14 FLAG encoding methods . . . . . . . . . . . . . . . . . 101 151 A.4.14.1 N . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 152 A.4.14.2 U . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 153 A.4.15 FORMAT . . . . . . . . . . . . . . . . . . . . . . . . . 103 154 A.4.16 CRC . . . . . . . . . . . . . . . . . . . . . . . . . . 106 155 A.4.16.1 MSN-LSB . . . . . . . . . . . . . . . . . . . . . . . . 106 156 A.4.16.2 MSN-IRREGULAR . . . . . . . . . . . . . . . . . . . . . 109 157 A.4.16.3 SET-MSN . . . . . . . . . . . . . . . . . . . . . . . . 110 158 A.5 ABNF description of the input language . . . . . . . . . 110 159 Full Copyright Statement . . . . . . . . . . . . . . . . 113 161 1. Introduction 163 This document describes a plug-in extension for the ROHC [1] 164 framework which simplifies the creation of new compression profiles. 166 The Efficient Protocol Independent Compression (EPIC-LITE) scheme for 167 generating new ROHC profiles takes as its input a choice of one or 168 more compression techniques for each field in the protocol stack to 169 be compressed. Using this input EPIC-LITE derives a set of 170 compressed header formats that can be used to quickly and efficiently 171 compress and decompress headers. 173 Chapter 2 explains some of the terminology used in the draft. 175 Chapter 3 gives an overview of the EPIC-LITE scheme. 177 Chapter 4 describes the language used by EPIC-LITE to create new 178 profiles. 180 Chapter 5 considers the basic techniques available in the EPIC- 181 LITE library of compression routines. 183 Chapter 6 specifies the parameters used to define a ROHC [1] 184 profile. 186 Appendix A gives a normative description of EPIC-LITE in 187 pseudocode. 189 2. Terminology 191 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 192 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 193 document are to be interpreted as described in RFC-2119 [5]. 195 Profile 197 A ROHC [1] profile is a description of how to compress a certain 198 protocol stack over a certain type of link. Each profile includes 199 one or more sets of compressed header formats and a state machine 200 to control the compressor and the decompressor. 202 Context 204 The context is memory which stores one or more previous values of 205 fields in the uncompressed header. The compressor and 206 decompressor both maintain a copy of the context, and fields can 207 be compressed relative to their stored values for better 208 compression efficiency. 210 Compressed header format 212 A compressed header format describes how to compress each field in 213 the chosen protocol stack. It consists of two parts: a bit 214 pattern to indicate to the decompressor which format is being 215 used, followed by a list of the compressed versions of each field. 217 Encoding method 219 An encoding method is a procedure for compressing fields. 220 Examples include STATIC encoding (field is the same as the 221 context), INFERRED-OFFSET encoding (field is calculated at the 222 decompressor) and IRREGULAR encoding (field must be transmitted in 223 full). 225 Indicator flags 227 Each EPIC-LITE compressed packet contains a set of indicator 228 flags. The flags are placed at the front of the packet as a 229 single bit pattern, and indicate to the decompressor exactly which 230 encoding method has been applied to which field. 232 Set of compressed header formats 234 A complete set of compressed header formats uses up all of the 235 indicator bit patterns available at the start of the compressed 236 header. A profile may have several sets of compressed header 237 formats available, but only one set can be in use at a given time. 239 Library of encoding methods 241 The library of encoding methods contains a number of commonly used 242 procedures that can be called to compress fields in the chosen 243 protocol stack. More encoding methods can be added to the library 244 if they are needed. 246 BNF (Backus Naur Form) 248 BNF is a "metasyntax" commonly used to describe the syntax of 249 protocols and languages. 251 BNF input language 253 EPIC-LITE describes a new ROHC profile using a simple BNF-based 254 input language. The BNF description of the ROHC profile assigns 255 one or more encoding methods to each field in the chosen stack. 257 Control data 259 The term 'control data' refers to any data passed between the 260 compressor and decompressor, that is not part of the uncompressed 261 header. An example of control data is the header checksum 262 calculated by EPIC-LITE over the uncompressed header to ensure 263 robustness against bit errors and dropped packets. 265 3. The EPIC-LITE framework for generating new ROHC profiles 267 This chapter outlines the EPIC-LITE framework for the creation of new 268 ROHC profiles. 270 3.1 Structure of the EPIC-LITE compressed headers 272 Each compressed header is divided into two distinct parts: the 273 indicator flags and the compressed fields as illustrated below: 275 +---+---+---+---+--------------------+--------------------+--- 276 | 0 | 1 | 1 | 0 | Compressed Field 1 | Compressed Field 2 |... 277 +---+---+---+---+--------------------+--------------------+--- 278 \ \ / / \ / 279 \ \ / / \ / 280 Indicator Flags Compressed Fields 282 Figure 1 : Structure of an EPIC-LITE compressed header 284 The indicator flags specify how every field in the uncompressed 285 header has been compressed, whilst the compressed fields contain 286 enough information to transmit each field from the compressor to the 287 decompressor. This information might be the entire uncompressed 288 field, it might be LSBs (Least Significant Bits) of the uncompressed 289 field etc. 291 Note that for simplicity EPIC-LITE always places the indicator flags 292 at the front of the compressed header followed by each complete 293 compressed field in turn. As for RFC-1144 [3] the compressed fields 294 are in reverse order compared to the uncompressed header (this is a 295 useful trick to speed up parsing at the decompressor). 297 Unlike other compression schemes, the header formats used by EPIC- 298 LITE are not designed by hand but instead are generated automatically 299 using a special algorithm. This means that EPIC-LITE can be applied 300 to any protocol stack provided that it has been correctly programmed 301 using the BNF-based input language described in Section 3.3. 303 3.2 Compression and decompression procedures 305 Figure 2 illustrates the processing which is done by EPIC-LITE for 306 each header to be compressed and decompressed. Note that references 307 are given to pseudocode in Appendix A which describes each of the 308 stages explicitly. 310 --------------------------------------------------------------------- 311 | Uncompressed packet Uncompressed packet ^ 312 v | 313 +-------------------+ +-------------------+ 314 | Selecting the | | Verifying correct | 315 | context | | decompression | 316 | (Section A.1.1) | | (Section A.2.5) | 317 +-------------------+ +-------------------+ 318 | ^ 319 | Uncompressed packet Uncompressed packet | 320 v Context | 321 +-------------------+ +-------------------+ 322 | Running the | | Decompressing | 323 | state machine | | the fields | 324 | (Section A.1.2) | | (Section A.2.4) | 325 +-------------------+ +-------------------+ 326 | Set of header formats Chosen format ^ 327 | Uncompressed packet Compressed fields | 328 v Context Context | 329 +-------------------+ +-------------------+ 330 | Compressing | | Reading the | 331 | the fields | | indicator flags | 332 | (Section A.1.3) | | (Section A.2.3) | 333 +-------------------+ +-------------------+ 334 | ^ 335 | Chosen format Compressed header | 336 v Compressed fields Context | 337 +-------------------+ +-------------------+ 338 | Determining the | | Running the | 339 | indicator flags | | state machine | 340 | (Section A.1.4) | | (Section A.2.2) | 341 +-------------------+ +-------------------+ 342 | ^ 343 | Compressed header Compressed header | 344 v Context | 345 +-------------------+ +-------------------+ 346 | Encapsulating in | |Decapsulating from | 347 | ROHC packet | ---------------> | ROHC packet | 348 | (Section A.1.5) | ROHC | (Section A.2.1) | 349 +-------------------+ packet +-------------------+ 351 Figure 2: EPIC-LITE compression/decompression 353 --------------------------------------------------------------------- 355 Each of these steps is described in more detail below. 357 At the compressor: 359 Step 1: The input to the compressor is simply an uncompressed packet 360 (with known length). In order to compress the packet it is first 361 necessary to classify it and choose the context relative to which the 362 packet will be compressed. If no suitable context is available then 363 an existing context must be overwritten. 365 Step 2: Once the context has been chosen the compressor knows which 366 ROHC [1] profile will be used to compress the packet. In particular 367 it can run the state machine that determines which set of header 368 formats will be used to compress the packet (IR, IR-DYN or CO). 370 Step 3: Given the uncompressed packet and a set of compressed header 371 formats, the compressor can choose a header format to robustly carry 372 this information to the decompressor using as few bits as possible. 373 Note that EPIC-LITE chooses the header format simultaneously with 374 compressing the header to improve the overall speed of compression. 376 Step 4: Each compressed header format has a unique set of indicator 377 flags that communicate to the decompressor which format is in use. 378 The compressor determines these indicator flags and appends them to 379 the front of the compressed fields to create a compressed header. 381 Step 5: Once the compressed header has been calculated, the 382 compressor encapsulates it within a ROHC packet by adding 0 or more 383 octets of context identifier together with any padding and 384 segmentation that is required. 386 At the decompressor: 388 Step 1: The input to the decompressor is a ROHC packet. From this 389 packet the decompressor can determine the attached context 390 identifier, which in turn specifies the context relative to which the 391 packet should be decompressed. 393 Step 2: Once the context has been identified, the decompressor can 394 run the state machine to determine if the packet may be decompressed. 396 Step 3: The decompressor then reads the indicator flags in the header 397 to determine which compressed header format has been used. This 398 allows the compressed value of each field to be extracted. 400 Step 4: Using the compressed value of each field and the context, the 401 decompressor can apply the encoding methods to reconstruct the 402 uncompressed packet. Note that fields are decompressed in reverse 403 order to compression (this ensures that fields which are inferred 404 from other field values are reconstructed correctly). 406 Step 5: Finally, the decompressor verifies that correct decompression 407 has occurred by applying the header checksum. If the packet is 408 successfully verified then it can be forwarded. 410 3.3 BNF input language for creating new ROHC profiles 412 EPIC-LITE is a protocol-independent compression scheme because it can 413 generate new compressed header formats automatically using a special 414 algorithm. In order for EPIC-LITE to compress a new protocol stack 415 however, it must be given a description of how the stack behaves. 417 EPIC-LITE uses a simple BNF-based input language for the fast 418 creation of new compression schemes. The language is designed to be 419 easy to use without detailed knowledge of the mathematics underlying 420 EPIC-LITE. The only information required to create a new ROHC [1] 421 profile using EPIC-LITE is a description of how the chosen protocol 422 stack behaves. 424 EPIC-LITE converts the input into one or more sets of compressed 425 header formats that can be used by a ROHC [1] compressor and 426 decompressor. As with all version of BNF the input language has a 427 rule-based structure, which makes it easy to build new profiles out 428 of existing ones (e.g. when adding new layers to a protocol stack). 430 Figure 3 describes the process of building a set of compressed header 431 formats from the BNF input, which is done once only and the results 432 stored at the compressor and decompressor. References are given to 433 pseudocode in Appendix A which describes the various stages 434 explicitly. 436 --------------------------------------------------------------------- 438 +-----------------------+ 439 | Input Stage 1: | 440 | Resolve input | 441 | into set of compressed| 442 | header formats | 443 | (Section A.3.1) | 444 +-----------------------+ 445 | 446 v 447 +-----------------------+ 448 | Input Stage 2: | 449 | Run Huffman algorithm | 450 | to generate flags | 451 | (Section A.3.2) | 452 +-----------------------+ 454 Figure 3: Building EPIC-LITE compressed header formats 456 --------------------------------------------------------------------- 458 Note that since the EPIC-LITE compressed header formats can be 459 generated offline, the fact that profiles are specified using an 460 input language does not affect the processing requirements of 461 compression and decompression. 463 3.4 Huffman compression 465 Huffman compression [2] is a well known technique used in many 466 popular compression schemes. EPIC-LITE uses ordinary Huffman 467 compression to generate a new set of compressed header formats. 469 The basic Huffman algorithm is designed to compress an arbitrary 470 stream of characters from a character set such as ASCII. The idea is 471 to create a new set of compressed characters, where each normal 472 character maps onto a compressed character and vice versa. Common 473 characters are given shorter compressed equivalents than rarely used 474 characters, reducing the average size of the data stream. 476 EPIC-LITE uses Huffman compression to generate the indicator flags 477 for each compressed header format. Each format is treated as one 478 character in the Huffman character set, so more common compressed 479 header formats are indicated using fewer bits than rare header 480 formats. The most commonly used header format is often indicated by 481 the presence of a single "0" flag at the front of the compressed 482 header. 484 The following chapters describe the mechanisms of EPIC-LITE in 485 greater detail. 487 4. Overview of the BNF input language for EPIC-LITE 489 This chapter describes the BNF-based input language provided by EPIC- 490 LITE for the creation of new ROHC [1] profiles. 492 The language is designed to be flexible but at the same time easy to 493 use without detailed knowledge of the mathematics underlying EPIC- 494 LITE. The only requirement for writing an efficient EPIC-LITE 495 profile is a description of how the relevant protocol stack behaves. 497 As with all versions of BNF, the description of the protocol is built 498 up using the following two constructs: 500 New BNF rule A new encoding method is created from existing 501 ones by writing a new BNF rule for the encoding 502 method 504 Set of choices One or more encoding methods can be assigned to 505 a given field by using the choice ("|") operator 507 EPIC-LITE also contains a library of fundamental encoding methods 508 (STATIC compression, LSB compression etc.) as described in Chapter 5. 509 The BNF description of how to compress a new protocol stack always 510 resolves into a selection of these fundamental encoding methods. 512 The exact syntax of the BNF-based input language can itself be 513 described using an existing version of BNF. A suitable variant is 514 "Augmented BNF" (ABNF) as described in RFC-2234 [6]. For example, in 515 ABNF the syntax for defining a new encoding method in terms of 516 existing ones is as follows: 518 = "=" 519 1*( ) 521 = 522 *( "|" ) 524 Each instance of calls an encoding method that 525 converts a certain number of uncompressed bits into a certain number 526 of compressed bits. Note also that is white space, used to 527 delimit the various encoding methods. 529 A complete description of the BNF-based input language can be found 530 in Appendix A.5. 532 An example of how to create a new encoding method is given below. An 533 encoding method known as IPv6_Header is constructed from the basic 534 encoding methods available in the library. This new method is 535 designed to compress an entire IPv6 header. 537 IPv6_Header_co = Version 538 Traffic_Class_co 539 ECT_Flag_co 540 CE_Flag 541 Flow_Label_co 542 Payload_Length 543 Next_Header 544 Hop_Limit_co 545 Source_Address_co 546 Destination_Address_co 548 Version = VALUE(4,6,100%) 550 Traffic_Class = STATIC(100%) 552 ECT_Flag = STATIC(100%) 554 CE_Flag = VALUE(1,0,99%) | VALUE(1,1,1%) 556 Flow_Label = STATIC(100%) 558 Payload_Length = INFERRED-SIZE(16,288) 560 Next_Header = STACK-TO-CONTROL(8) 562 Hop_Limit = STATIC(100%) 564 Source_Address = STATIC(100%) 566 Destination_Address = STATIC(100%) 568 Each field in the IPv6 header is given a choice of possible encoding 569 methods. If an encoding method is not implicitly used 100% of the 570 time for that field (e.g. INFERRED-SIZE) then one of the parameters 571 is the probability that it will be used to encode the field in 572 question. This is very important since EPIC-LITE ensures that common 573 encoding methods require fewer bits to carry the compressed data than 574 rarely used encoding methods. 576 For optimal compression, the probability should equal the percentage 577 of time for which the encoding method is selected to compress the 578 field. Note that there is no requirement for probabilities to add up 579 to exactly 100%, as EPIC-LITE will automatically scale the 580 probabilities by a constant factor if they do not. 582 Note also that the BNF input language is designed to be both human- 583 readable and machine-readable. If only one protocol stack needs to 584 be compressed, the input language can simply be converted by hand 585 directly to an implementation. However, since the input language 586 provides a complete description of the protocol stack to be 587 compressed, it is possible to compress headers using only the 588 information contained in the BNF description and without any 589 additional knowledge of the protocol stack. This means that it is 590 possible to implement a protocol-independent compressor that can 591 download a new ROHC [1] profile described in the BNF input language 592 and immediately use it to compress headers. 594 4.1 Information stored at compressor and decompressor 596 Any ROHC compressor maintains a number of contexts as described in 597 Section 5.1.3 of ROHC [1]. Each context at the compressor and 598 decompressor includes the following: 600 Compression profile: Compressed header formats 601 State machine 602 Field values: One or more previously processed headers 604 The compression profile describes how to compress a certain protocol 605 stack over a certain type of link. It includes the profile 606 parameters that describe the set of compressed header formats (as 607 discussed in Chapter 6) and additionally records the current state of 608 the state machine. 610 The compressor also stores one or more sets of field values from 611 previously processed headers. Each new header can be compressed 612 relative to these field values to improve the compression ratio. 614 For the profiles generated using EPIC-LITE, the compressor and 615 decompressor maintain a context value for some or all of the "field 616 encodings" specified in the BNF description (recall that a field 617 encoding is a set of one or more encoding methods that can be used to 618 compress a given field). This context value is taken from the last 619 header to be successfully compressed or decompressed. 621 Furthermore, in order to provide robustness the compressor can 622 maintain more than one context value for each field. These values 623 represent the r most likely candidates values for the context at the 624 decompressor, given that bit errors and dropped packets may prevent 625 the compressor from being 100% certain exactly which values are 626 contained in the decompressor context. 628 EPIC-LITE ensures that the compressed header contains enough 629 information so that the uncompressed header can be extracted no 630 matter which one of the compressor context values is actually stored 631 at the decompressor. The only problem arises if the decompressor has 632 a context value that does not belong to the set of values stored at 633 the compressor; this situation is detected by a checksum over the 634 uncompressed header and the packet is discarded at the decompressor. 636 If more than one value for a field is stored in the compressor 637 context, some of the library encoding methods will automatically fail 638 or only succeed under certain conditions. For example, STATIC 639 encoding will fail and LSB encoding will only succeed if sufficient 640 LSBs are sent to infer correct value of the field regardless of the 641 precise value stored in the decompressor context. 643 Note that the rules for extracting fields from the uncompressed 644 header and updating the context values are given in Appendix A. 646 The number of context values per field to be stored at the compressor 647 is implementation-specific. Storing more values reduces the chance 648 that the decompressor will have a context value different from any of 649 the values stored at the compressor (which could cause the packet to 650 be decompressed incorrectly). The trade-off is that the compressed 651 header will be larger because it must contain enough information to 652 decompress relative to any of the candidate context values. 654 As an example, an implementation may choose to store the last r 655 values of each field in the compressor context. In this case 656 robustness is guaranteed against up to r - 1 consecutive dropped 657 packets between the compressor and the decompressor. 659 4.2 Generated data 661 There is some data that is passed from the compressor to the 662 decompressor, but which is not present in the uncompressed header. 663 This data communicates additional information that might be useful to 664 the decompressor: for example a checksum over the uncompressed header 665 to ensure correct decompression has occurred. 667 This data may be generated by certain encoding methods and then added 668 either to the uncompressed header to be compressed immediately or to 669 the control data stack to be compressed later. 671 5. Library of EPIC-LITE encoding methods 673 The ROHC [1] standard contains a number of different encoding methods 674 (LSB encoding, scaled timestamp encoding, list-based compression 675 etc.) for compressing header fields. EPIC-LITE treats these encoding 676 methods as library functions to be called by the BNF input language 677 when they are needed. 679 The following library contains a wide range of basic encoding 680 methods. Moreover new encoding methods can be added to the library 681 as and when they are needed. 683 Note that this chapter contains an informative description only. The 684 normative pseudocode description of every encoding method can be 685 found in Appendix A.4. 687 The syntax of each encoding method is given using ABNF as defined in 688 RFC-2234 [6]. Note that each of the encoding methods may have one or 689 more parameters of the following type: 691 A non-negative integer (specified as decimal, 692 binary or hex). Binary values are prefixed by 0b 693 and hex values are preceded by 0x. 695 An integer (positive or negative) 697 A non-negative integer used to indicate the 698 length of the field being compressed 700 A probability expressed as a percentage with at 701 most 2 decimal places 703 The name of another encoding method including 704 all parameters 706 The ABNF description of these parameters is found in Appendix A.5. 708 5.1 STATIC 710 ABNF notation: "STATIC(" ")" 712 The STATIC encoding method can be used when the header field does not 713 change relative to the context. If a field is STATIC then no 714 information concerning the field need be transmitted in the 715 compressed header. 717 The only parameter for the STATIC encoding method is a probability 718 that indicates how often the method will be used. Encoding methods 719 with high probability values require fewer bits in the compressed 720 header than encoding methods that are allocated low probability 721 values. In general the probability should reflect as accurately as 722 possible the chance that the field will be encoded as STATIC. 724 5.2 IRREGULAR 726 ABNF notation: "IRREGULAR(" "," ")" 728 The IRREGULAR encoding method is used when the field cannot be 729 compressed relative to the context, and hence must be transmitted in 730 full in the compressed header. 732 The IRREGULAR encoding method has a length parameter to indicate the 733 length of the field in bits and a probability that indicates how 734 often it will be used. 736 A modified version of IRREGULAR encoding is given below: 738 5.2.1 IRREGULAR-PADDED 740 ABNF notation: "IRREGULAR-PADDED(" "," "," 741 ")" 743 The IRREGULAR-PADDED encoding method compresses any field that is 744 large in terms of number of bits but has a small actual value (and 745 hence the most significant bits are zero). 747 The encoding method transmits a certain number of LSBs (Least 748 Significant Bits) of the field. The first parameter gives the 749 overall length of the field, whilst the next parameter specifies the 750 number of LSBs to be transmitted in the compressed header. The bits 751 not transmitted are all taken to be 0 by the decompressor. The 752 probability gives an indication of how often IRREGULAR-PADDED will be 753 used. 755 The IRREGULAR-PADDED encoding method is useful for compressing fields 756 that take small integer values with a high probability. 758 5.3 VALUE 760 ABNF notation: "VALUE(" "," "," ")" 761 The VALUE encoding method can be used to transmit one particular 762 value for a field. It is followed by parameters to indicate the 763 length and integer value of the field as well as the probability of 764 the field taking this value. 766 5.4 LSB 768 ABNF notation: "LSB(" "," "," ")" 770 The LSB encoding method compresses the field by transmitting only its 771 LSBs (Least Significant Bits). 773 The first parameter indicates the number of LSBs to transmit in the 774 compressed header. The second parameter is the offset of the LSBs: 775 it describes whether the decompressor should interpret the LSBs as 776 increasing or decreasing the field value contained in its context. 777 Again the probability indicates how often LSB encoding will be used. 779 To illustrate how the second parameter works, suppose that k LSBs are 780 transmitted with offset p. The decompressor uses these LSBs to 781 replace the k LSBs of the value of this field stored in the context 782 (val), and then adds or subtracts multiples of 2^k so that the new 783 field value lies between (val - p) and (val - p + 2^k - 1). 785 In particular, if p = 0 then the field value can only stay the same 786 or increase. If p = -1 then it can only increase, whereas if p = 2^k 787 then it can only decrease. 789 Recall that for robustness the compressor can store r values for each 790 field in its context. If this is the case then enough LSBs are 791 transmitted so that the decompressor can reconstruct the correct 792 field value, no matter which of the r values it has stored in its 793 context. This is equivalent to Window-based LSB encoding as 794 described in ROHC [1]. 796 5.5 UNCOMPRESSED 798 ABNF notation: "UNCOMPRESSED(" "," "," "," 799 ")" 801 The UNCOMPRESSED encoding method transmits a field uncompressed 802 without alteration. All uncompressed fields are transmitted as-is at 803 the end of the compressed header. 805 The UNCOMPRESSED encoding method differs from the IRREGULAR encoding 806 method in that the size of the field is not fixed, but instead is 807 specified by a control field. The first parameter gives the length n 808 of the control field: UNCOMPRESSED encoding obtains this control 809 field simply by removing the first value (which should be n bits) 810 from the control data stack. 812 The next three parameters specify a divisor, multiplier and offset 813 for the control field. These parameters scale the value of the 814 control field so that it specifies the exact size of the UNCOMPRESSED 815 field in bits. If the parameters are d, m and p respectively then: 817 size of UNCOMPRESSED field = floor(control field value / d) * m + p 819 UNCOMPRESSED encoding is usually used in conjunction with one of the 820 STACK encoding methods, which write to the control data stack as 821 explained below: 823 5.6 STACK encoding methods 825 These methods are used to move values around for use by future 826 encoding methods. They take as a parameter the number of bits to be 827 transferred and always have 100% probability of being used. 829 5.6.1 STACK-TO-CONTROL 831 ABNF notation: "STACK-TO-CONTROL(" ")" 833 This encoding method takes the specified number of bits from the 834 uncompressed header and transfers them to the control data stack. It 835 does the reverse at the decompressor. 837 5.6.2 STACK-FROM-CONTROL 839 ABNF notation: "STACK-FROM-CONTROL(" ")" 841 This encoding method takes an item with the specified number of bits 842 from the control data stack and transfers it to the uncompressed 843 header. It does the reverse at the decompressor. 845 5.6.3 STACK-PUSH-MSN 847 ABNF notation: "STACK-PUSH-MSN(" ")" 849 The MSN (Master Sequence Number) is a width defined value that 850 increases by one for each packet received at the compressor. 852 This encoding method copies the least significant specified number of 853 bits of the MSN to the top of the control data stack. Conversely, it 854 removes these bits at the decompressor. 856 5.6.4 STACK-POP-MSN 858 ABNF notation: "STACK-POP-MSN(" ")" 860 This encoding method removes the specified number of bits of the MSN 861 from the uncompressed data or adds it at the decompressor. 863 5.6.5 STACK-ROTATE 865 ABNF notation: "STACK-ROTATE(" "," ")" 867 This encoding method rotates the top n items on the top control stack 868 m times where n is the first parameter and m the second. A rotation 869 of n items by 1 moves the nth element on the control stack to the top 870 of the stack (and the top n-1 items down one place). 872 5.7 INFERRED encoding methods 874 The following versions of INFERRED encoding are available: 876 5.7.1 INFERRED-TRANSLATE 878 ABNF notation: "INFERRED-TRANSLATE(" "," *("," 879 "," ) ")" 881 The INFERRED-TRANSLATE encoding method translates a field value under 882 a certain mapping. The first pair of parameters specifies the length 883 of the field before and after the translation. This is followed by 884 additional pairs of integers, representing the field value before and 885 after it is translated. Note that the final field value at the 886 compressor (or equivalently, the original field value at the 887 decompressor) appears first in each pair. For example: 889 INFERRED-TRANSLATE(8,16,41,0x86DD,4,0x0800) ; GRE Protocol 891 The GRE Protocol field behaves in the same manner as the Next Header 892 field in other extension headers, except that it indicates that the 893 subsequent header is IPv6 or IPv4 using the values 0x86DD and 0x0800 894 instead of 41 and 4. The INFERRED-TRANSLATE encoding method can 895 convert the standard values (as provided by LIST compression defined 896 in Section 5.11) into the values required by the GRE Protocol field. 898 At the compressor, once the translation is complete the field is 899 copied to the control data stack. At the decompressor the field is 900 removed from the control data stack, translated and then added to the 901 uncompressed data. 903 5.7.2 INFERRED-SIZE 905 ABNF notation: "INFERRED-SIZE(" "," ")" 907 The INFERRED-SIZE encoding method infers the value of a field from 908 the size of the uncompressed packet. 910 The first parameter specifies the uncompressed field length in bits, 911 and the second parameter specifies the offset of the uncompressed 912 packet size (i.e. the amount of packet which has already been 913 compressed). If the INFERRED-SIZE field value is v, the offset is p 914 and the total packet length after (but not including) the INFERRED- 915 SIZE field is L then the following equation applies (assuming 8 bits 916 in a byte): 918 L = 8 * v + p 920 5.7.3 INFERRED-OFFSET 922 ABNF notation: "INFERRED-OFFSET(" ")" 924 The INFERRED-OFFSET encoding method compresses a field that usually 925 has a constant offset relative to a certain base field. 927 The parameter describes the length of the field to be compressed. 928 The base field will already be on the control data stack - put there 929 using one of the STACK methods. 931 The encoding subtracts the base field from the field to be compressed 932 and replaces the field value by these "offset" bits in the 933 uncompressed header. The offset bits are then compressed by the next 934 encoding method in the input code. 936 For example, a typical sequence number can be compressed as follows: 938 STACK-PUSH-MSN(32) ; Put MSN on control stack 940 INFERRED-OFFSET(32) ; Sequence Number 942 STACK-POP-MSN(32) ; Remove MSN 944 STATIC(99%) | ; Sequence Number offset 945 LSB(8,-1,0.7%) | 946 LSB(16,-1,0.2%) | 947 IRREGULAR(32,0.1%) 949 In this case the offset field is expected to change rarely and only 950 by small amounts, and hence it is compressed using mainly STATIC and 951 LSB encodings. 953 5.7.4 INFERRED-IP-CHECKSUM 955 ABNF notation: "INFERRED-IP-CHECKSUM(" ")" 957 This method is used for calculating the IP checksum. At the 958 compressor it replaces the bits representing the IP checksum with "0" 959 bits (these are a known distance from the beginning of this method). 960 It then continues to compress using encoding_name. At the 961 decompressor it decompresses encoding_name as usual. A 16-bit one's 962 complement sum is then computed over the length of data which has 963 been decompressed in this method and the result copied into the 964 appropiate bits (at a fixed offset) in the header. 966 5.8 NBO 968 ABNF notation: "NBO(" ")" 970 The NBO encoding method may be used if there is a possibility that 971 the following field will be in reverse byte order from the rest of 972 the header, as is sometimes seen with the IP ID, for example. The 973 method looks at the specified number of bits (typically 16 or 32) 974 and, using a history, decides whether or not they are in network byte 975 order. If they are it removes them from the stack, puts a 1-bit flag 976 with the value "1" on the stack and replaces the original value. If 977 the value is not in NBO it removes the bits, puts a flag with the 978 value "0" on the stack and replaces the byte-swapped value. This 979 method can be used prior to other methods, for example: 981 NBO (16) ; Check for network byte order 983 STACK-PUSH-MSN(16) ; Put MSN on control stack 985 INFERRED-OFFSET(16) ; IP ID 987 STACK-POP-MSN(16) ; Remove MSN 989 STATIC(80%) | ; IP ID offset 990 LSB(5,-1,15%) | 991 IRREGULAR(16,5%) 993 STATIC(99%) | ; NBO flag 994 IRREGULAR(1,1%) 996 5.9 SCALE 998 ABNF notation: "SCALE(" ")" 1000 The SCALE encoding method is used for fields which change by a 1001 regular (usually large) amount every packet. The number of bits 1002 specified are removed and a suitable scale factor chosen. Three 1003 values each with the specified length are then replaced on the stack. 1004 If the original field has value v and the chosen scale is s then 1005 these values are: 1007 v / s = the scaled value of v when v is divided by s using integer 1008 arithmetic 1010 v mod s = the remainder when v is divided by s 1012 s = the scale value 1014 They are placed on the stack in the order above so that the next 1015 value to be compressed is the scale value. 1017 5.10 OPTIONAL 1019 ABNF notation: "OPTIONAL(" ")" 1021 The OPTIONAL encoding method is used to compress fields that are 1022 optionally present in the uncompressed header. 1024 OPTIONAL encoding requires a 1 bit indicator flag to specify whether 1025 or not the optional field is present in the uncompressed header. 1027 This flag is extracted from the control data stack. The value of the 1028 flag is added to the stack by another encoding method (such as STACK- 1029 TO-CONTROL or LIST). For example: 1031 STACK-TO-CONTROL(1) ; GRE Key flag 1033 OPTIONAL(KEY-ENCODING) ; GRE Key 1035 In this case the encoding method KEY-ENCODING is called to compress 1036 the GRE Key field, but only if the Key Flag is set to 1. If the Key 1037 Flag is set to 0 (indicating that the GRE Key is not present) then 1038 some padding bits of 0 may be added to the compressed header (the 1039 number of bits added is determined by the compressor - the compressor 1040 chooses a format for KEY-ENCODING, which though not used provides the 1041 number of bits with which to pad). If there is a U method 1042 encompassing the OPTIONAL method then the number of bits with which 1043 to pad is automatically zero. 1045 5.11 MANDATORY 1047 ABNF notation: "MANDATORY(" ")" 1049 This encoding method may be used where another encoding method has 1050 appended a flag indicating the presence of a field in the 1051 uncompressed header. If the field is optionally present then the 1052 OPTIONAL encoding (above) may be used. If the field is always 1053 present then the MANDATORY encoding can be used. This checks that 1054 the value of the flag on the stack is 1 (indicating that the field is 1055 present). If the value of the flag is 0 then the MANDATORY encoding 1056 method will fail. 1058 5.12 CONTEXT 1060 ABNF notation: "CONTEXT(" "," ")" 1062 The CONTEXT encoding method is used to store multiple copies of the 1063 same field in the context. This encoding method is useful when 1064 compressing fields that take a small number of values with high 1065 probability, but when these values are not known a-priori. 1067 CONTEXT encoding can also be applied to larger fields: even an entire 1068 TCP header. This can be very useful when multiple TCP flows are sent 1069 to the same IP address, as a single ROHC [1] context can be used to 1070 compress the packets in all of the TCP flows. 1072 The first parameter specifies the encoding method that should be used 1073 to compress the field. The second parameter specifies how many 1074 copies of the field should be stored in the context. 1076 CONTEXT encoding applies the specified encoding method to the 1077 uncompressed header, compressing relative to any of the copies of the 1078 field stored in its context. It then appends an "index" value to the 1079 uncompressed header to indicate to the decompressor which context 1080 value should be used for decompression. Consider the following 1081 example using the TCP Window field: 1083 CONTEXT(TCP-WINDOW,4) ; Window 1085 VALUE(2,0,89%) | ; Window context index 1086 VALUE(2,1,10%) | 1087 VALUE(2,2,0.5%) | 1088 VALUE(2,3,0.5%) 1090 At most 4 copies of the Window field can be stored in the context. 1091 The Window field can be compressed relative to any of these values: 1092 the value chosen by the compressor is transmitted to the decompressor 1093 using the "index". 1095 5.13 LIST 1097 ABNF notation: "LIST(" "," "," "," 1098 "," "," *("," 1099 ) *("," ) ")" 1101 The LIST encoding method compresses a list of items that do not 1102 necessarily occur in the same order for every uncompressed header. 1103 Example applications for the LIST encoding method include TCP options 1104 and TCP SACK blocks. 1106 The size of the list is determined by a control field in exactly the 1107 same manner as for UNCOMPRESSED encoding. The first four integer 1108 parameters are defined as in UNCOMPRESSED. 1110 The fifth parameter gives the number of bits which should be read 1111 from the uncompressed_data stack to decide which of the encoding 1112 methods in the list to use to compress the next list item. 1114 These parameters are followed by a set of encoding methods that can 1115 be used to compress individual items in the list and a set of 1116 integers to identify which method to use. If the integer obtained 1117 using the fifth parameter matches the nth integer then use the nth 1118 encoding method. 1120 This continues until data amounting to the size of the list has been 1121 compressed. 1123 Once the list size is reached, LIST encoding appends the order in 1124 which the encoding methods were applied to the uncompressed data and 1125 the presence of data for the methods. The profile defines whether 1126 the order and presence can change in a compressed packet or not. For 1127 example: 1129 LIST(4,1,32,0,8, 1130 OPTIONAL(TCP-SACK), 1131 OPTIONAL(TCP-TIMESTAMP), 1132 OPTIONAL(TCP-END), 1133 OPTIONAL(TCP-GENERIC), 1134 5,8,0) ; TCP Options 1136 STATIC(99.9%) | ; TCP Options order 1137 IRREGULAR(8, 0.1%) 1139 STATIC(75%) | ; TCP Options presence 1140 IRREGULAR(4,25%) 1142 The order in which the methods are applied is irrelevant in the 1143 mapping between methods chosen and the indicator flags. They are 1144 always considered to be compressed in the order in which they appear 1145 in the profile and the order and presence fields deal with the actual 1146 order in which they were processed. 1148 5.13.1 LIST-NEXT 1150 ABNF notation: "LIST-NEXT(" "," *("," 1151 ) *("," ) ")" 1153 LIST-NEXT encoding is similar to basic LIST encoding, except that the 1154 next list item to compress is known a-priori from a control field. 1155 IP extension headers can be compressed using LIST-NEXT. 1157 The first parameter specifies the number of bits to extract from the 1158 control data stack before each list item is compressed. This is 1159 followed by the set of encoding methods available to LIST-NEXT and a 1160 set of 0 or more integers. The nth encoding method can only be 1161 called when the nth integer value is obtained from the control data 1162 stack. 1164 For example: 1166 LIST-NEXT(8, OPTIONAL(AH-ENCODING), 1167 OPTIONAL(ESP-ENCODING), 1168 OPTIONAL(GRE-ENCODING), 1169 OPTIONAL(GENERIC-ENCODING), 1170 51,50,47) ; Header Chain 1172 STATIC(99.9%) | ; Header Chain order 1173 IRREGULAR(8,0.01%) 1175 STATIC(75%) | ; Header Chain presence 1176 IRREGULAR(4,25%) 1178 The IP extension header chain can have a number of specific encoding 1179 methods designed for one type of extension header (AH, ESP or GRE) as 1180 well as a "generic" encoding method that can cope with arbitrary 1181 extension headers but at reduced compression efficiency. 1183 Just as with basic LIST encoding, LIST-NEXT also adds the order in 1184 which the encoding methods are applied and their presence or absence 1185 to the uncompressed header, so that the decompressor can reconstruct 1186 the list in the correct order. 1188 5.14 FLAG encoding methods 1190 The flag encoding methods are used to modify the behavior of another 1191 encoding method. Each flag encoding has a single parameter, which is 1192 the name of another encoding method. The flag encoding method calls 1193 this encoding method, but additionally modifies the input or output 1194 in some manner. 1196 Note that flag encoding methods do not require the original encoding 1197 method to be rewritten (as they only modify its input or output). 1199 5.14.1 N flag 1201 ABNF notation: "N(" ")" 1203 The N flag runs the encoding method specified by its parameter, with 1204 the exception that it does not update the context. This is useful 1205 when a field takes an unexpected value for one header and then 1206 reverts back to its original behavior in subsequent headers. 1208 An example of the N flag in use is given below: 1210 STATIC(99%) | ; Window 1211 N(LSB(11,2048,0.9%)) | 1212 IRREGULAR(16,0.1%) 1214 In the above example the N flag is applied to the TCP Window field. 1215 The field is compressed by transmitting only the last few LSBs, which 1216 are always interpreted at the decompressor as a decrease in the field 1217 value. However, because the context is not updated the field reverts 1218 back to its original value following the decrease. 1220 5.14.2 U flag 1222 ABNF notation: "U(" ")" 1224 The U flag changes the destination of any compressed bits produced by 1225 the encoding method specified as its parameter. Instead of putting 1226 them on the compressed_data stack it puts them on the unc_fields 1227 stack. They no longer contribute to the length of the compressed 1228 header so this is taken account of in the build method. This means 1229 that if an OPTIONAL method is surrounded by a U flag and the optional 1230 part is not actually present then no padding bits are required. 1232 An example of the U flag in use is given below: 1234 U(OPTIONAL(crsc_entry)) ; CSRC-list entry 1236 where 1238 csrc_entry = IRREGULAR(32) 1240 This means that if the CSRC entry is present then it will be 1241 compressed as IRREGULAR (i.e. the full 32 bits will be sent) and 1242 these bits will be pushed on the uncompressed stack. However, if it 1243 is not present then no padding bits will need to be sent. 1245 5.15 FORMAT 1247 ABNF notation: "FORMAT(" "," *() ")" 1249 The FORMAT encoding method is used to create more than one set of 1250 compressed header formats. 1252 Recall that each set of compressed header formats uses up all of the 1253 indicator bit patterns available at the start of the compressed 1254 header. Thus a profile can have several sets of compressed header 1255 formats, but only one set can be in use at a given time. 1257 FORMAT encoding is followed by a list of k encoding methods. Each 1258 encoding method is given its own set of compressed header formats in 1259 the CO packets. Note however that all encoding methods are present 1260 in the IR(-DYN) packets, so an IR(-DYN) packet may be sent to change 1261 to a new set of compressed header formats. 1263 An index flag is appended to the uncompressed header to indicate 1264 which set of formats is currently in use, as illustrated by the 1265 following example of an IR(-DYN) format (for CO the index flag would 1266 be STATIC(100%)): 1268 FORMAT(SEQUENTIAL-IP-ID,RANDOM-IP-ID) ; IP ID 1270 IRREGULAR(1,100%) ; IP_ID Index 1272 Two sets of compressed header formats are provided: one for an IP ID 1273 that increases sequentially, and one for a randomly behaving IP ID. 1274 Note that the Index flag is only sent in the IR(-DYN) packets. 1276 5.16 CRC 1278 ABNF notation: "CRC(" "," ")" 1280 The CRC encoding method generates a CRC checksum calculated across 1281 the entire uncompressed header. At the decompressor this CRC is used 1282 to validate that correct decompression has occurred. 1284 Note that it is possible for different header formats to have 1285 different amounts of CRC protection, so extra CRC bits can be 1286 allocated to protect important context-updating information. This is 1287 illustrated in the example below: 1289 CRC(3,99%) | ; Checksum Coverage 1290 CRC(7,1%) 1292 The uncompressed header is recorded in the crc_static and crc_dynamic 1293 variables. Note that the fields that either never change or only 1294 change in the IR packet are placed in crc_static, and the remaining 1295 fields are placed in crc_dynamic. The CRC is calculated over 1296 crc_static + crc_dynamic, with the static fields placed first to 1297 speed up computation. 1299 In general an EPIC-LITE profile can use any CRC length for which a 1300 CRC polynomial has been explicitly defined. The following CRC 1301 lengths are currently supported: 1303 3-bit: C(x) = 1 + x + x^3 1304 6-bit: C(x) = 1 + x + x^3 + x^4 + x^6 1305 7-bit: C(x) = 1 + x + x^2 + x^3 + x^6 + x^7 1306 8-bit: C(x) = 1 + x + x^2 + x^8 1307 10-bit: C(x) = 1 + x + x^4 + x^5 + x^9 + x^10 1308 12-bit: C(x) = 1 + x + x^2 + x^3 + x^11 + x^12 1309 16-bit: C(x) = 1 + x^2 + x^15 + x^16 1311 5.17 MSN encoding methods 1313 These methods are used to send the MSN (Master Sequence Number) to 1314 the decompressor. Separate encoding methods are required because the 1315 MNS does not appear in the uncompressed data itself. 1317 There are two encoding methods which compress the MSN and one which 1318 can be used to assign a particular field to be the MSN (for example, 1319 RTP sequence number): 1321 5.17.1 MSN-LSB 1323 ABNF notation: "MSN-LSB(" "," "," ")" 1325 This method uses ordinary LSB encoding on the value in MSN rather 1326 than on the uncompressed_data stack. It also stores some information 1327 for use if extra bits of MSN are to be sent to pad the compressed 1328 header to a specific bit alignment. 1330 5.17.2 MSN-IRREGULAR 1332 ABNF notation: "MSN-IRREGULAR(" "," ")" 1334 As with MSN-LSB this method uses ordinary IRREGULAR encoding and 1335 stores the extra information described above. 1337 5.17.3 SET-MSN 1339 ABNF notation: "SET-MSN(" ")" 1341 The parameter of this method specifies the number of bits to assign 1342 to be MSN. The bits are taken from the uncompressed stack. This 1343 value can then be used for INFERRED-OFFSET methods and compressed 1344 using MSN-LSB or MSN-IRREGULAR when no more fields need it. 1346 6. Creating a new ROHC profile 1348 This chapter describes how to generate new ROHC [1] profiles using 1349 EPIC-LITE. It is important that the profiles are specified in an 1350 unambiguous manner so that any compressor and decompressor using the 1351 profiles will be able to interoperate. 1353 The following eight variables are required by EPIC-LITE to create a 1354 new ROHC [1] profile: 1356 profile_identifier 1357 max_formats 1358 max_sets 1359 bit_alignment 1360 npatterns 1361 CO_packet 1362 IR_DYN_packet 1363 IR_packet 1365 Once a value has been assigned to each variable the profile is well- 1366 defined. A compressor and decompressor using the same values for 1367 each variable should be able to successfully interoperate. 1369 Each of the variables is described in more detail below: 1371 6.1 Profile identifier 1373 The profile_identifier is a 16-bit integer that is used when 1374 negotiating a common set of profiles between the compressor and 1375 decompressor. Official profile identifiers are assigned by IANA to 1376 ensure that two distinct profiles do not receive the same profile 1377 identifier. Note that the 8 MSBs of the profile identifier are used 1378 to specify the version of the profile (so that old profiles can be 1379 obsoleted by new profiles). 1381 6.2 Maximum number of header formats 1383 The max_formats parameter controls the number of compressed header 1384 formats to be stored at the compressor and decompressor. 1386 If more compressed header formats are generated than can be stored 1387 then EPIC-LITE discards all but the max_formats most probable formats 1388 to be used. Note that the max_formats parameter affects the EPIC- 1389 LITE compressed header formats, and so for interoperability it MUST 1390 be specified as part of the profile. 1392 If more than max_formats header formats are generated for the IR 1393 packet then this means that there are headers which it may be 1394 impossible to compress using this profile (resulting in a switch to a 1395 different profile). Hence it is RECOMMENDED that no more than 1396 max_formats distinct header formats are generated for the IR packet 1397 of any profile. 1399 In a similar manner the max_sets parameter controls the total number 1400 of sets of compressed header formats to be stored. Recall that a 1401 profile can have several sets of compressed header formats, but only 1402 one set may be in use at a given time. It is important to note that 1403 the maximum size specified by max_formats applies to each individual 1404 set of header formats, so the total overall number of formats that 1405 need to be stored is equal to max_formats * (max_sets + 2) including 1406 the 2 sets of formats for the IR and IR-DYN packets. 1408 6.3 Control of header alignment 1410 The alignment of the compressed headers is controlled using the 1411 bit_alignment parameter. The output of the EPIC-LITE compressor is 1412 guaranteed to be an integer multiple of bit_alignment bits long. 1414 Additionally, the parameter npatterns can be used to reserve bit 1415 patterns in the compressed header. The parameter specifies the 1416 number of bit patterns in the first word (i.e. the first 1417 bit_alignment bits) of the compressed header that are available for 1418 use by EPIC-LITE. Consequently npatterns takes a value between 1 and 1419 2^bit_alignment. 1421 For compatibility with ROHC [1], it is important for EPIC-LITE not to 1422 use the bit patterns 111XXXXX in the first octet of each compressed 1423 header because they are reserved by the ROHC framework. So to 1424 produce a set of header formats compatible with ROHC [1] the 1425 bit_alignment parameter MUST be set to 8 and npatterns MUST be set to 1426 224. 1428 6.4 Compressed header formats 1430 The profile parameter CO_packet specifies an encoding method that is 1431 used to generate the EPIC-LITE CO packets. This encoding method may 1432 be described using the BNF-based input language provided in Chapter 4 1433 (or in fact can be described in any manner provided that it is 1434 unambiguous). 1436 The distinction between the eight variables required to define a new 1437 ROHC [1] profile and the input language defined in Chapter 4 is 1438 important. The only requirement for compatibility with the profile 1439 is that the correct compressed header formats are used: the fact that 1440 they are specified in the input language is not important, and they 1441 can be implemented in any manner. 1443 The profile parameters IR_packet and IR_DYN_packet specify an 1444 encoding method which is used to generate the EPIC-LITE IR and IR-DYN 1445 packets respectively. 1447 Note that the IR_DYN_packet parameter is optional. If it is not 1448 given then EPIC-LITE generates the IR-DYN packet using the same 1449 encoding method as specified by the CO_packet parameter. The 1450 IR_packet parameter is also optional. If it is not given then EPIC- 1451 LITE generates the IR packet using the same encoding method as 1452 specified by the IR_DYN_packet parameter (or CO_packet if 1453 IR_DYN_packet is also not given). 1455 7. Security considerations 1457 EPIC-LITE generates compressed header formats for direct use in ROHC 1458 profiles. Consequently the security considerations for EPIC-LITE 1459 inherit those of ROHC [1]. 1461 EPIC-LITE profiles also describe how to compress and decompress 1462 headers. As such they are interpreted or compiled by the compressor 1463 and decompressor. An error in the profile description may cause 1464 undefined behaviour. In a situation where profiles could be 1465 dynamically updated consideration MUST be given to authenticating and 1466 verifying the integrity of the profile. 1468 8. Acknowledgements 1470 Header compression schemes from ROHC [1] have been important sources 1471 of ideas and knowledge. Basic Huffman encoding [2] was enhanced for 1472 the specific tasks of robust, efficient header compression. 1474 Thanks to 1476 Carsten Bormann (cabo@tzi.org) 1477 Christian Schmidt (christian.schmidt@icn.siemens.de) 1478 Max Riegel (maximilian.riegel@icn.siemens.de) 1480 for valuable input and review. 1482 References 1484 [1] Bormann, C., Burmeister, C., Degermark, M., Fukushima, H., 1485 Hannu, H., Jonsson, L-E., Hakenberg, R., Koren, T., Le, K., Liu, 1486 Z., Martensson, A., Miyazaki, A., Svanbro, K., Wiebke, T., 1487 Yoshimura, T. and H. Zheng, "RObust Header Compression (ROHC): 1488 Framework and four profiles: RTP, UDP, ESP, and uncompressed", 1489 RFC 3095, July 2001. 1491 [2] Nelson, M. and J-L. Gailly, "The Data Compression Book", M&T 1492 Books , 1995. 1494 [3] Jacobson, V., "Compressing TCP/IP headers for low-speed serial 1495 links", RFC 1144, February 1990. 1497 [4] Bradner, S., "The Internet Standards Process -- Revision 3", BCP 1498 9, RFC 2026, October 1996. 1500 [5] Bradner, S., "Key words for use in RFCs to Indicate Requirement 1501 Levels", BCP 14, RFC 2119, March 1997. 1503 [6] Crocker, D. and P. Overell, "Augmented BNF for Syntax 1504 Specifications: ABNF", RFC 2234, November 1997. 1506 Authors' Addresses 1508 Richard Price 1509 Siemens/Roke Manor 1510 Roke Manor Research Ltd. 1511 Romsey, Hants SO51 0ZN 1512 UK 1514 Phone: +44 (0)1794 833681 1515 EMail: richard.price@roke.co.uk 1516 URI: http://www.roke.co.uk 1518 Robert Hancock 1519 Siemens/Roke Manor 1520 Roke Manor Research Ltd. 1521 Romsey, Hants SO51 0ZN 1522 UK 1524 Phone: +44 (0)1794 833601 1525 EMail: robert.hancock@roke.co.uk 1526 URI: http://www.roke.co.uk 1527 Stephen McCann 1528 Siemens/Roke Manor 1529 Roke Manor Research Ltd. 1530 Romsey, Hants SO51 0ZN 1531 UK 1533 Phone: +44 (0)1794 833341 1534 EMail: stephen.mccann@roke.co.uk 1535 URI: http://www.roke.co.uk 1537 Abigail Surtees 1538 Siemens/Roke Manor 1539 Roke Manor Research Ltd. 1540 Romsey, Hants SO51 0ZN 1541 UK 1543 Phone: +44 (0)1794 833131 1544 EMail: abigail.surtees@roke.co.uk 1545 URI: http://www.roke.co.uk 1547 Paul Ollis 1548 Siemens/Roke Manor 1549 Roke Manor Research Ltd. 1550 Romsey, Hants SO51 0ZN 1551 UK 1553 Phone: +44 (0)1794 833168 1554 EMail: paul.ollis@roke.co.uk 1555 URI: http://www.roke.co.uk 1557 Mark A. West 1558 Siemens/Roke Manor 1559 Roke Manor Research Ltd. 1560 Romsey, Hants SO51 0ZN 1561 UK 1563 Phone: +44 (0)1794 833311 1564 EMail: mark.a.west@roke.co.uk 1565 URI: http://www.roke.co.uk 1567 Appendix A. EPIC-LITE compressor and decompressor 1569 This appendix gives a complete pseudocode description of the EPIC- 1570 LITE compressor and decompressor. 1572 The appendix contains the following sections: 1574 Compressor operation (Section A.1) 1575 Decompressor operation (Section A.2) 1576 Offline processing (Section A.3) 1577 Library of methods (Section A.4) 1578 BNF description of input language (Section A.5) 1580 Recall that each EPIC-LITE profile for ROHC [1] is described by the 1581 following eight variables: 1583 profile_identifier 16-bit integer uniquely identifying the 1584 ROHC profile generated by EPIC-LITE 1586 max_formats Maximum number of header formats per set 1588 max_sets Total number of sets of header formats 1590 bit_alignment Number of bits for alignment (all 1591 compressed headers will be multiples of 1592 bit_alignment bits). (Set to 8 for 1593 compatibility with ROHC [1].) 1595 npatterns Number of bit patterns available for 1596 EPIC-LITE in the first word of the 1597 compressed header (set to 224 for 1598 compatibility with ROHC [1].) 1600 CO_packet Name of the method that generates the CO 1601 packet formats 1603 IR_DYN_packet Name of the method that generates the 1604 IR-DYN packet formats 1606 IR_packet Name of the method that generates the IR 1607 packet formats 1609 Additionally, the following general functions are used in the 1610 pseudocode description of EPIC-LITE: 1612 The functions used for list manipulation are given below: 1614 empty (list) Empties the list 1616 sort-natural (list, compare) Sorts the list as defined by the compare 1617 function (which compares 2 elements). 1618 Sort is 'natural' in that original 1619 ordering of elements is preserved in the 1620 event of 2 elements being equal 1622 append (list, item) Appends an item to a list 1624 prepend (list, item) Prepend an item to head of list 1626 concatenate (list, list) Appends all the entries from the second 1627 list to the first one 1629 copy (list, list) Replaces the first list with a copy of 1630 the second list 1632 head-of (list) Finds first item in list 1634 tail-of (list) Finds last item in list 1636 next-item (curr_item) Finds the next item in the list from 1637 curr_item 1639 previous-item (curr_item) Finds the previous item in the list 1640 from curr_item 1642 at-end (list) Checks whether at the end of the list 1644 size-of (list) Returns the number of elements in list 1646 The following functions are used to traverse the BNF input language 1647 describing the new ROHC profile. Note that the relevant information 1648 can be extracted from the input language by hand or automatically via 1649 a suitable BNF parser: 1651 first-field (method_name) 1652 finds the first instance of referenced 1653 in the encoding method (applies to a non-library 1654 encoding method only) 1656 next-field (method_name) 1657 finds the next instance of in the 1658 method (if none can be found then NULL-ENCODING is 1659 returned) 1661 prev-field (method_name) 1662 finds the previous instance of in the 1663 method 1665 last-field (method_name) 1666 finds the last instance of in the 1667 method (these functions allow iteration over the 1668 different field encodings in a method. This must be in 1669 the order defined in the profile) 1671 first-method (field_encoding) 1672 find the first encoding method listed within the field 1673 encoding 1675 next-method (field_encoding) 1676 find the next encoding method listed within the field 1677 encoding (this and the previous function allow iteration 1678 over the encoding methods for a given field. This must 1679 be in the order defined in the profile. If none can be 1680 found then NULL-METHOD is returned) 1682 extract-name (method) 1683 finds the name of the encoding method 1685 extract-probability (method) 1686 finds the probability of the method being invoked 1688 Method function handling: 1690 lookup-build-function (method) 1691 finds the 'BUILD' function that relates to the 1692 method. If this is a library method, then the 1693 function returns a reference to the 'BUILD' 1694 subfunction for that method. Otherwise it 1695 returns a reference to the main 'BUILD' function 1696 which is then called recursively 1698 lookup-compress-function (method) 1699 as above but for the 'COMPRESS' function 1701 lookup-decompress-function (method) 1702 as above but for the 'DECOMPRESS' function 1704 context-size (method) 1705 looks up the number of context entries that will be 1706 needed to compress using this method. This can be 1707 worked out off line as part of the 'BUILD' function and 1708 stored for reference during compression and 1709 decompression. 1711 count-bits (method, enc) 1712 counts the number of bits that would be present in a 1713 compressed header for data compressed with format enc 1714 for this method (This can be worked out off line as part 1715 of the 'BUILD' function and stored for use during 1716 compression and decompression). 1718 Data handling: 1720 Value based functions: 1722 length (var) Returns the length in bits of var 1724 value (var) Returns the value of var 1726 str (len, val) Returns a variable with length len and 1727 containing the value val 1729 lsb (var, k) Returns the least significant k bits of 1730 a (width defined or not) value (var) in 1731 a width defined value 1733 msb (var, k) Returns the most significant k bits of a 1734 width defined value (var) in a width 1735 defined value 1737 concat (var_1, var_2) Returns a width defined value with most 1738 significant bits being var_1 and least 1739 being var_2 - ie concatenates the two 1740 strings 1742 Addition, subtraction and multiplication can be done on width defined 1743 values as long as the two values have the same length (i.e. this 1744 translates into modular arithmetic) but must be done carefully. 1746 Stack functions: 1748 In the functions below an item has a length and value associated with 1749 it which can be found using the functions above. 1751 push (stack_name, n, var) For a bit-overlay stack, this function 1752 adds n bits with value var to the top of 1753 the stack (stack_name). For an item 1754 stack, this function pushes an item with 1755 length n and value var to the top of the 1756 stack (stack_name) 1758 push (stack_name, item) For a bit-overlay stack, this function 1759 adds n bits with value var to the top of 1760 the stack (stack_name) where n is the 1761 length of item and it has value var. 1762 For an item stack, this function pushes 1763 item on var to the top of the stack 1764 (stack_name) 1766 pop (stack_name, n, item) Pop n bits of data off a bit based stack 1767 (stack_name) and put into item 1769 pop (stack_name, item) Pop item off an item based stack 1770 (stack_name) 1772 top (stack_name, n) Returns the item made up of the top n 1773 bits on a bit based stack (stack_name) 1775 top (stack_name) Returns the top item from an item based 1776 stack (stack_name) 1778 stack-size (stack) Returns the size in bits of a bit based 1779 stack 1781 add (stack_1, stack_2) Pushes stack_1 onto stack_2 but leaves 1782 the outcome in stack_1 1784 rotate (stack_name, n, m) Rotate the top n items on an item based 1785 stack (stack_name) m times. Take the 1786 nth item from the stack and put it on 1787 the top. 1789 stack-pointer (stack_name) Returns the position of the top of a 1790 stack (stack_name) NB this is never used 1791 for accessing the stack and can be of 1792 arbitrary form 1794 Context based functions: 1796 The enc_index counter is used to access information stored in the 1797 context for each field encoding. It is initially 1 and is 1798 incremented throughout compression and decompression. Some encoding 1799 methods do not have any context associated with them, for example, 1800 INFERRED-SIZE. This incremental way of accessing context information 1801 means that if a choice of two or more encoding methods is available 1802 for a given field, each in turn should contain the same number of 1803 subfields as each other, otherwise the alignment of the context will 1804 be lost. 1805 NB leaving a value in the context empty is NOT the same as storing 1806 something which zero-bits wide. 1808 context (enc_index, i, var) 1809 Put the value stored at the ith position 1810 in the context associated with enc_index 1811 into var. If there isn't a value in the 1812 ith position then return empty 1814 save (enc_index, var, storage) 1815 Store the value in var in storage 1816 associated with enc_index (to be 1817 transferred to the context if 1818 (de)compression is successful 1820 clear (enc_index, storage) Remove the value in storage associated 1821 with enc_index and leave it empty (for 1822 use if non-context-updating method) 1824 transfer (storage, context) Transfer the information in storage into 1825 the context 1827 Miscellaneous: 1829 convert-percentage (pc) Converts the percentage (in floating 1830 point) to the fixed point representation 1831 used 1833 store (list, method, field_encoding) 1834 Add method associated with 1835 field_encoding to list 1837 get-method (list, field_encoding) 1838 Return the method associated with 1839 field_encoding from list 1841 get-method-list (main_list_elt, method_chosen) 1842 Finds method_chosen such that 1843 method_chosen <=> 1844 main_list_item.id 1846 format-get-method-list (main_list_elt, method_chosen, method) 1847 Finds method_chosen such that 1848 method_chosen <=> 1849 main_list_item.id assuming that a 1850 specific method has been chosen using 1851 the FORMAT method (this is used to 1852 ensure correct decompression of an 1853 IR(-DYN) packet) 1855 get-format (main_list_elt, method_chosen) 1856 Finds the main_list_item such that 1857 method_chosen <=> main_list_item.id 1859 get-header-length (method_chosen) 1860 Returns the length in bits of the 1861 compressed header format (excluding 1862 flags) for this list element 1863 (sum of number of bits in each 1864 compressed field) 1866 lookup-crc-function (n) Finds the function for computing an 1867 n-bit crc over a specified amount of 1868 data and putting the value into a given 1869 width defined variable 1871 byte-swap (item) Returns another item the same as item 1872 but stored in the opposite byte ordering 1874 compute-16-checksum (data, length) 1875 Compute a 16-bit one's complement sum 1876 over data of length 1878 Other constructs: 1880 foreach item in [reverse] list 1881 : 1882 end loop 1884 provides for iteration over all the elements of a list [in 1885 reverse order] 1887 call function (...) 1889 indicates a reference to a function is being invoked 1891 choose (...) 1893 the choice of whatever is specified is implementation specific 1894 - it may affect efficiency but whatever choice is made will not 1895 affect interoperability, for example, choose (j < k) - pick 1896 an arbitrary value j which is less than k. 1898 Some global variables: 1900 uncompressed_data Bit based stack 1901 Compression - initially header and payload, 1902 finally empty 1903 Decompression - initially empty, 1904 finally original header and 1905 payload 1907 compressed_data Bit based stack 1908 Compression - initially empty, 1909 finally compressed header and 1910 payload 1911 Decompression - initially compressed header, 1912 finally empty 1914 unc_fields Bit based stack 1915 Compression - initially empty, 1916 used to store fields to be sent 1917 uncompressed for transfer to 1918 compressed_data 1919 Decompression - initially data which has been 1920 sent uncompressed, 1921 finally only payload for 1922 transfer to uncompressed_data 1924 received_data Bit based stack 1925 Decompression - initially packet received, 1926 splits into compressed_data and 1927 unc_fields 1929 control_data Item based stack 1930 Compression and 1931 Decompression - initially and finally empty - 1932 storage for control fields if 1933 not used immediately after 1934 generation 1936 u_flag A flag which starts with value zero. It keeps 1937 track of which stack (compressed_data or 1938 unc_fields) has the compressed data added to/ 1939 removed from it. 1941 compression_stack Pointer to either compressed_data or 1942 unc_fields, whichever is the one that is 1943 currently having data put onto it according 1944 to the value of u_flag. 1945 Initially at both compression and decompression 1946 compression_stack = compressed_data. 1948 context Storage of data as reference for 1949 compression and decompression - 1950 referenced by 'enc_index' 1952 storage Storage of data during (de)compression 1953 to be transferred to context if 1954 successful - referenced by 'enc_index' 1956 enc_index A counter to keep track of the field encodings 1957 and context data associated with them 1959 method_chosen List of methods used to compress a given 1960 header - lists the encoding method 1961 chosen for each 'enc_index' 1963 compressor_state The current state at the compressor (can be set 1964 to "IR", "IR-DYN" or "CO") 1966 current_set The set of compressed header formats 1967 currently in use 1969 crc_static The static part of the header 1971 crc_dynamic The dynamic part of the header 1973 crc The decompressed crc for checking against one 1974 calculated over full header (a width defined 1975 value) 1977 MSN The Master Sequence Number - a width defined 1978 value (its value increases by one for each 1979 packet received at the compressor or it is set 1980 to be a specific value using the SET-MSN method 1981 if the header contains a suitable field) 1983 msn_bits The number of bits chosen to encode the MSN 1985 msn_lsbs The LSBs of MSN used for padding (a width 1986 defined value) 1988 A.1 Compressor 1990 This section describes the EPIC-LITE header compressor. 1992 A.1.1 Step 1: Packet classification 1994 The input to the EPIC-LITE compressor is simply an uncompressed 1995 packet. The compressor does not know whether the packet contains an 1996 RTP header, TCP header or other type of header, and hence the first 1997 step is to determine which (if any) ROHC context can be used to 1998 compress the packet. 2000 With any profile generated by EPIC-LITE the packet classification is 2001 performed automatically, since the profile will reject any packet 2002 that it cannot successfully compress relative to the chosen context. 2004 Note however that additional packet classification MAY be performed 2005 before the packet is passed to the EPIC-LITE compressor. For example 2006 the compressor MAY wish to check that the values that are initialised 2007 in the IR packet, or fixed for all states take the values specified 2008 in the prospective context before compression is attempted, as if 2009 they do not then compression will not succeed. 2011 A.1.2 Step 2: Using the state machine 2013 The job of the state machine is to choose whether to send IR, IR-DYN 2014 or compressed (CO) packets. Since EPIC-LITE currently operates in a 2015 unidirectional mode of compression only there is no need to 2016 synchronize the decision with the decompressor, and hence the choice 2017 can be left as an implementation decision. 2019 A.1.3 Step 3: Compressing the header 2021 The next step is to choose the compressed header format that will be 2022 used to transmit the header from the compressor to the decompressor. 2023 Given the selected profile the compressor has exactly max_sets + 2 2024 possible sets of header formats available: a total of max_sets 2025 different sets of CO packets, as well as a set of IR-DYN packets and 2026 a set of IR packets. The choice of which header formats to use 2027 depends on the current state of the state machine. 2029 The compressor calls the function COMPRESS to compress the header. 2030 The function takes one parameter - the name of the method that is 2031 currently being used. The global variable enc_index is initially 1. 2033 Note that is not necessary to provide EPIC-LITE with a description of 2034 where the fields occur in the uncompressed header, as this 2035 information is provided automatically as part of each method (written 2036 in the BNF input language). Each encoding method has a specific 2037 number of bits associated with it which is the number of bits that 2038 encoding method can compress - this splits the header into fields. 2040 The function has a single output: a Boolean value indicating whether 2041 or not compression has successfully occurred. Additionally, if 2042 compression succeeds then the stack compressed_data will contain the 2043 compressed value of every field in the uncompressed header. 2045 The function also modifies the value of the global variable, 2046 method_chosen. If compression is successful then for each field in 2047 the profile, method_chosen will contain an indicator of which 2048 encoding method has been selected for the field. This is mapped onto 2049 a set of indicator flags in Section A.1.4. 2051 The compression commences with a call to the COMPRESS function for 2052 the method specified in CO_packet (or IR_DYN_packet or IR_packet 2053 depending on the compressor state). 2055 The function may call itself recursively with a different input. 2057 For one particular aspect of profile complexity there are two 2058 distinct categories. For a profile in the first category, if a 2059 header is compressible, then compression is guaranteed to complete 2060 successfully in a single pass. The second category of profiles 2061 cannot make this guarantee. This is due either to a change of packet 2062 format (as indicated through the FORMAT encoding method) or to the 2063 failure of a non-library encoding method. A change of format 2064 requires IR-DYN packets to be sent indicating the change. Multiple 2065 formats may need to be tried in order to find one that can 2066 successfully compress the packet, and the compressor should implement 2067 such a mechanism. Where a non-library encoding method fails, 2068 alternative encoding methods may be available. However, some 2069 encoding methods may have been applied, altering the contents of the 2070 stacks used to store state information for compression. The 2071 compressor should implement a mechanism, such as rolling back the 2072 compression state information, to allow alternative encoding methods 2073 to be tried. This ensures that all possible combinations of encoding 2074 methods can be tried to find one which will successfully compress the 2075 packet. 2077 If the method is specified as part of the EPIC-LITE library, the 2078 pseudocode for the COMPRESS procedure is specified separately (in 2079 Appendix A.4.). 2081 function COMPRESS (method_name) 2083 var enc, method 2084 var compress_function 2086 enc = first-field (method_name) 2088 while (enc <> NULL_ENCODING) 2089 method = first-method (enc) 2091 do 2092 # compress_function will be for the method if it is a 2093 # library method or a recursive call to this function for 2094 # a composite method... 2096 compress_function = lookup-compress-function 2097 (extract-name (method)) 2099 can_compress = call compress_function 2100 (extract-name (method)) 2102 if can_compress = true then 2104 # store the method selected from this field_encoding in 2105 # method_chosen 2107 store (method_chosen, method, enc) 2109 else 2111 # otherwise try another method in the field_encoding 2113 method = next-method (enc) 2115 endif 2117 loop until (can_compress = true) or (method = NULL_METHOD) 2119 if can_compress = true then 2121 enc = next-field (method_name) 2123 else 2125 return false 2127 endif 2129 end while 2131 return true 2133 end COMPRESS 2134 N.B. This procedure shows the encoding methods for a field being 2135 checked in the order in which they appear in the profile. The order 2136 in which they are checked is actually implementation specific but is 2137 shown in the form above for simplicity of the pseudocode. But, for 2138 interoperability the "store" function must have a unique mapping 2139 dictated by the order of the encoding methods in the profile between 2140 the field and the encoding method. 2142 Note that once the header has been compressed, the variable "storage" 2143 should contain the uncompressed value of each field which has context 2144 associated with it. This information is then transferred to the 2145 context in the compressor (possibly overwriting one of the copies of 2146 information already stored). 2148 A.1.4 Step 4: Determining the indicator flags 2150 The next step is to determine the correct indicator flags for the 2151 chosen compressed header format. 2153 Once the indicator flags have been added the header should be padded 2154 to be a multiple of bit_alignment bits and the uncompressed fields 2155 and payload added. 2157 The compressor must run the following procedures: 2159 function get-indicator-flags (method_chosen, flags_list_elt, Mvalue) 2160 var main_list_item, old_item, ml 2161 var last_N_before_item, w, length, length_item, next_length, num 2162 var last_N_of_smaller_length 2163 var found_length, n_diff 2164 var fl 2166 # How this mapping is done is implementation dependent at the 2167 # compressor 2169 get-format (main_list_item, method_chosen) 2171 old_item = next-item (main_list_item) 2172 last_N_before_item = tail-of (old_item.cum_N_list) 2174 w = head-of (main_list_item.cum_N_list) 2175 length = head-of (main_list_item.length_list) 2176 found_length = 0 2178 # If length_list only has one item then this loop will only 2179 # be done once (as in EPIC-LITE), otherwise loop until the 2180 # cumulative_N which covers Mvalue is found. This gives the 2181 # length of the flags 2183 while (found_length = 0) 2184 n_diff = w - last_N_before_item 2185 if (n_diff < Mvalue) then 2186 w = next-item (w) 2187 length = next-item (length) 2188 else 2189 found_length = 1 2190 endif 2191 end loop 2193 # Find first flags of this length from the flag list 2195 found_length = 0 2196 fl = head-of (flag_list) 2198 while (found_length = 0) 2199 if length = fl.length then 2200 found_length = 1 2201 else 2202 fl = next-item (fl) 2203 endif 2204 end loop 2206 # Find the last cumulative N which has flags of smaller length 2207 # than fl 2209 found_length = 0 2210 ml = tail-of (main_list) 2212 while (found_length = 0) 2213 if (head-of (ml.length_list) < length) then 2214 ml = previous-item (ml) 2215 else 2216 found_length = 1 2217 ml = next-item (ml) 2218 endif 2219 end loop 2221 length_item = head-of (ml.length_list) 2222 num = head-of (cum_N_list) 2223 next_length = next-item (length_item) 2224 found_length = 0 2226 while (next_length <> NULL and found_length = 0) 2227 if next_length <> length then 2228 length_item = next-item (length_item) 2229 next_length = next-item (next_length) 2230 num = next-item (num) 2231 else 2232 found_length = 1 2233 endif 2234 end loop 2236 last_N_of_smaller_length = num 2238 # Work out what the indicator flags will be for this Mvalue 2240 flags = Mvalue + fl.flags + last_N_before_item - 2241 last_N_of_smaller_length 2243 return length 2244 end get-indicator-flags 2246 procedure INDICATOR-FLAGS 2248 var n, bit, temp, length 2249 var extra_bits 2251 # Take account of the currently selected FORMAT set 2253 choose (main_list or formats and associated flag_list according 2254 to the value of current_set) 2256 length = get-indicator-flags (method_chosen, flags, 0) 2258 push (compressed_data, length, flags) 2260 # pad the compressed header to bit_alignment with extra bits of 2261 # MSN - use zeros if more space than bits of MSN 2262 bit = bit_alignment 2264 n = (bit - (stack-size (compressed_data) mod bit)) mod bit 2266 temp = value (MSN) - value (lsb (MSN, msn_bits)) 2267 temp = temp / (2^msn_bits) 2268 extra_bits = lsb (temp, n) 2270 push (unc_fields, extra_bits) 2272 # add the uncompressed fields after the compressed header 2273 add (compressed_data, unc_fields) 2275 # add the payload after the uncompressed fields 2276 add (compressed_data, uncompressed_data) 2278 end INDICATOR-FLAGS 2280 A.1.5 Step 5: Encapsulating in ROHC packet 2282 The last step is to encapsulate the EPIC-LITE compressed packet 2283 within a ROHC packet. 2285 Note that this includes adding the CID and any other ROHC framework 2286 headers (segmentation, padding etc.) as described in ROHC [1]. The 2287 ROHC packet is then ready to be transmitted. 2289 A.2 Decompressor 2291 This section describes the EPIC-LITE header decompressor. 2293 A.2.1 Step 1: Decapsulating from ROHC packet 2295 The input to the EPIC-LITE decompressor is a compressed ROHC packet. 2296 The first step is to read the CID of the packet and to extract the 2297 EPIC-LITE packet for parsing by the appropriate profile. 2299 If the ROHC packet is identified as containing an EPIC-LITE 2300 compressed packet then the decompression process continues as 2301 indicated below. 2303 A.2.2 Step 2: Running the state machine 2305 The decompressor state machine determines whether the received packet 2306 should be decompressed or discarded (based on whether the 2307 decompressor believes its stored context to be valid or invalid). 2308 Since the compressor and decompressor state machines do not have to 2309 be synchronized, this is left as an implementation decision. 2311 A.2.3 Step 3: Reading the indicator flags 2313 The input to Step 3 is an EPIC-LITE compressed packet. Note that the 2314 overall length of the packet is known from the link layer, but the 2315 length of the compressed header itself is NOT known. 2317 The first step is to determine the compressed header format and split 2318 the packet into compressed header and uncompressed data. This is 2319 accomplished by reading the indicator flags as per the following 2320 procedure: 2322 procedure decode-indicator-flags (received_data, method_chosen, 2323 flags, bit_chunks, Mvalue) 2325 var main_list_item, ml 2326 var last_N_before_item, length, length_item, next_length, num 2327 var last_N_of_smaller_length 2328 var found_length 2329 var fl 2331 found_length = 0 2332 fl = head-of (flag_list) 2334 while (found_length = 0 and fl <> NULL) 2335 if (top (received_data, fl.length*bit_chunks) 2336 <= fl.flags) then 2337 found_length = 1 2338 else 2339 fl = next-item (fl) 2340 endif 2341 end loop 2343 if fl <> NULL then 2344 fl = previous=item (fl) 2345 else 2346 fl = tail-of (flag_list) 2347 endif 2349 length = fl.length 2350 flags = top (received_data, length*bit_chunks) 2352 # Find the last cumulative N which has flags of smaller length 2353 # than fl 2355 found_length = 0 2356 ml = tail-of (main_list) 2358 while (found_length = 0) 2359 if (head-of (ml.length_list) < length) then 2360 ml = previous-item (ml) 2361 else 2362 found_length = 1 2363 ml = next-item (ml) 2364 endif 2365 end loop 2367 length_item = head-of (ml.length_list) 2368 num = head-of (ml.cum_N_list) 2369 next_length = next-item (length_item) 2370 found_length = 0 2372 while (next_length <> NULL and found_length = 0) 2373 if next_length <> length then 2374 length_item = next-item (length_item) 2375 next_length = next-item (next_length) 2376 num = next-item (num) 2377 else 2378 found_length = 1 2379 endif 2380 end loop 2382 last_N_of_smaller_length = num 2384 Mvalue = flags - fl.flags 2386 num = tail-of (ml.cum_N_list) 2388 while ((num - last_N_of_smaller_length) < Mvalue) 2389 ml = previous-item (ml) 2390 num = tail-of (ml.cum_N_list) 2391 end loop 2393 main_list_elt = ml 2394 ml = next-item (ml) 2395 last_N_before_item = tail-of (ml.cum_N_list) 2397 Mvalue = Mvalue + last_N_of_smaller_length - last_N_before_item 2399 # How this mapping is done is decompressor specific 2400 get-method-list (main_list_item, method_chosen) 2402 end decode-indicator-flags 2404 procedure READ-FLAGS 2405 var found, n, size, bit, k, len, Mvalue 2406 var temp, flags, flags_temp 2408 # Take account of the currently selected FORMAT set 2410 choose (main_list or formats and associated flag_list according 2411 to the value of current_set) 2413 decode-indicator-flags (received_data, method_chosen, 2414 flags, 1, Mvalue) 2416 len = length (flags) 2417 pop (received_data, len, flags_temp) 2419 n = get-header-length (method_chosen) 2421 # put the compressed header on the compressed data stack 2422 pop (received_data, n, temp) 2423 push (compressed_data, temp) 2425 # store any extra lsbs of MSN sent 2426 bit = bit_alignment 2427 k = (bit - (n + len) mod bit) mod bit 2428 pop (received_data, k, msn_lsbs) 2430 # put the rest of the received packet on the unc_fields stack 2431 size = stack-size (received_data) 2432 pop (received_data, size, temp) 2433 push (unc_fields, temp) 2435 end READ-FLAGS 2437 A.2.4 Step 4: Decompressing the fields 2439 Now that the format of the compressed header has been determined, the 2440 next step is to decompress each field in turn. 2442 The decompressor calls the procedure DECOMPRESS to calculate the 2443 uncompressed value of the fields. The only input to the procedure is 2444 the name of a method. Unlike the COMPRESS function there are no 2445 outputs since decompression always succeeds (although if the packet 2446 is corrupted, the correct answer may not be obtained). 2448 Initially, the DECOMPRESS procedure is called for the method 2449 specified in CO_packet (or IR_DYN_packet or IR_packet depending on 2450 the ROHC packet type received). Note that as for COMPRESS the 2451 procedure may call itself recursively with different inputs. The 2452 global variable enc_index is initially 1. 2454 procedure DECOMPRESS (method_name) 2456 var enc, method 2457 var decompress_function 2459 enc = last-field (method_name) 2461 while (enc <> NULL_ENCODING) 2463 method = get-method (method_chosen, enc) 2465 # decompress_function will be for the method if it is a 2466 # library method or a recursive call to this function for 2467 # composite method... 2469 decompress_function = lookup-decompress-function 2470 (extract-name (method)) 2472 call decompress_function (extract-name (method)) 2474 enc = prev-field (method_name) 2476 end while 2478 end DECOMPRESS 2480 Observe that the DECOMPRESS procedure reads the input code in the 2481 opposite order to the COMPRESS procedure. This is because 2482 decompression is the exact mirror-image of compression: if fields are 2483 parsed in reverse order then it will never be the case that a field 2484 can only be decompressed relative to a field that has not yet been 2485 reached. 2487 When the entire header has been decompressed it is on the stack 2488 uncompressed data and the payload is still on the stack unc_fields. 2489 These should be combined to make the original packet. 2491 A.2.5 Step 5: Verifying correct decompression 2493 By this stage the decompressor has calculated the value 2494 uncompressed_data that contains the entire uncompressed header as 2495 well as the payload. 2497 The final step is to verify that successful decompression has 2498 occurred by applying the checksum to the uncompressed header. The 2499 CRC method makes available the variables checksum_value (containing 2500 the checksum from the compressed header) and crc_static + crc_dynamic 2501 (containing all of the fields in the uncompressed header). The CRC 2502 should be evaluated over crc_static + crc_dynamic and compared with 2503 the CRC stored in checksum_value. 2505 If the uncompressed header fails the checksum then it should be 2506 discarded. If it passes then it can be forwarded by the 2507 decompressor. 2509 Furthermore, if decompression is successful then the values contained 2510 within context can be replaced by the values contained in storage. 2512 A.3 Offline processing 2514 This section describes how the profile is converted into one or more 2515 sets of compressed header formats. Note that the following 2516 algorithms are run once offline and the results stored at the 2517 compressor and decompressor. 2519 A.3.1 Step 1: Building the header formats 2521 The first step is to build up a list of the max_formats different 2522 compressed header formats that occur with the highest probability 2523 (based on the probability values given in the input code). 2525 To generate the max_sets + 2 different sets of compressed header 2526 formats, the BUILD procedure is called max_sets times with the global 2527 variable compressor_state set to "CO" and current_set taking values 2528 from 0 to max_sets - 1 inclusive. Additionally it is called once 2529 with compressor_state = "IR" and once with compressor_state = "IR- 2530 DYN". The output in each case is a list describing the top 2531 max_formats different compressed header formats. The list has the 2532 following attributes: 2534 The output from the BUILD procedure is a list describing the top 2535 max_formats different compressed header formats in the following way. 2537 Each list_item has several parts: 2539 list_item.P Overall percentage probability that the header 2540 format identified in this list item will be used 2542 list_item.N Total size of the header format identified in 2543 this list item in bits, excluding indicator 2544 flags 2546 list_item.id A list of integers uniquely identifying the 2547 header format associated with this list item (id 2548 is itself a list on which the list functions 2549 defined earlier can be performed) 2551 Note that all percentages are stored to exactly 2 decimal places (or 2552 by scaling they can be stored as a 2-octet integer from 0 to 10000 2553 inclusive). When two percentages are multiplied, the result MUST be 2554 calculated exactly (i.e. to 4 decimal places, or equivalently a 4- 2555 octet integer) and then truncated to 2 decimal places. 2557 For example, 15.8% is represented as 1580, 89.2% is represented as 2558 8920. The result of multiplying these two values together is: 2559 1580 x 8920 = 14093600 (interim result, accurate to 4 DP) 2560 14093600 / 10000 = 1409 (any remainder is discarded) 2561 1409 = 14.09% 2563 For interoperability the top max_formats entries MUST NOT be 2564 reordered when the discarding process is carried out. In the event 2565 of a tie, the list entries with the lowest indices are kept. 2567 Note that the procedure may call itself recursively using a different 2568 input. 2570 Some functions used in the BUILD procedure are defined first: 2572 # 2573 # compare two items by probability 2574 # 2575 function COMPARE (a, b) 2576 if a.P > b.P then 2577 return 1 2578 else if a.P < b.P then 2579 return -1 2580 else 2581 return 0 2582 endif 2583 end COMPARE 2584 # 2585 # discard items from list such that: 2586 # list is sorted 2587 # if list contains less than max_formats entries then 2588 # the sorted list is returned 2590 # else if list contains more than max_formats then 2591 # keep the max_formats most probably entries 2592 # if any other entries have the same probability as 2593 # the least probable entry, keep those 2594 # discard the rest 2595 # 2596 procedure DISCARD (list, max_formats) 2598 var result_list 2599 var count 2600 var last_item 2602 empty (result_list) 2604 sort-natural (list, COMPARE) 2606 count = 0 2607 last_item = tail-of (list) 2609 foreach item in reverse list 2611 if ((count >= max_formats) and ((last_item.P <> item.P) or 2612 (item.P = 0)) then 2613 break 2614 endif 2616 prepend (result_list, item) 2618 last_item = item 2620 count = count + 1 2622 end loop 2624 copy (list, result_list) 2626 end DISCARD 2627 # 2628 # combine two lists by creating their 2629 # product. This sums the N values and 2630 # multiplies the P values 2631 # 2632 procedure COMBINE (final, temp) 2634 empty (new_list) 2636 foreach dst in temp 2638 foreach src in final 2640 item.P = dst.P * src.P 2641 item.P = dst.N + src.N 2642 copy (item.id, dst.id) 2644 concatenate (item.id, src.id) 2646 append (new_list, item) 2648 end loop 2650 DISCARD (new_list, max_formats) 2652 end loop 2654 copy (final, new_list) 2656 end COMBINE 2658 # 2659 # build the list for the method given 2660 # 2661 procedure BUILD (method_name, probability, build_list) 2663 var enc, method 2664 var item 2665 var final_list, build_output, temp_list 2666 var build_function 2668 enc = first-field (method_name) 2670 item.P = convert-percentage (100%) 2671 item.N = 0 2672 empty (item.id) 2674 empty (final_list) 2675 append (final_list, item) 2677 while (enc <> NULL_ENCODING) 2679 empty (temp_list) 2681 method = first-method (enc) 2683 do 2684 # build_function will be for the method if it is a library 2685 # method or a recursive call to this function for a composite 2686 # method... 2688 empty (build_output) 2690 build_function = lookup-build-function (method) 2692 call build_function (extract-name (method), 2693 extract-probability (method), 2694 build_output) 2696 foreach item in build_output 2698 append (item.id, method) 2699 append (temp_list, item) 2701 end loop 2703 DISCARD (temp_list) 2705 method = next-method (enc) 2707 loop until method = NULL_METHOD 2709 # combine lists - result in final_list 2711 COMBINE (final_list, temp_list) 2713 enc = next-field (method_name) 2715 end while 2717 foreach item in final_list 2719 item.P *= probability 2721 end loop 2723 copy (build_list, final_list) 2725 end BUILD 2727 procedure BUILD-TABLE (base_method, result) 2729 BUILD (base_method, convert-percentage (100%), result) 2731 end BUILD-TABLE 2733 The final output of BUILD is a list describing max_formats different 2734 compressed header formats. 2736 A.3.2 Step 2: Generating the indicator flags 2738 The final step of generating a new set of compressed header formats 2739 is to convert the list of probabilities into a set of indicator 2740 flags. Each header format begins with a unique pattern of indicator 2741 flags that serve to distinguish it from all other header formats in 2742 the set. 2744 EPIC-LITE generates the indicator flags using ordinary Huffman 2745 compression. For each of the cases in Section A.3.1 where the BUILD 2746 algorithm is run the following algorithm should be applied to the 2747 output of BUILD: 2749 # 2750 # build the flags associated with the list given, reserving the 2751 # bit pattern '111' if do_reserve is set 2752 # 2753 procedure BUILD-FLAGS (main_list, do_reserve) 2755 var work_list, reserve 2756 var u, v, w, z 2757 var i, flag, value, prev_length, num_formats 2759 sort-natural (main_list, COMPARE) 2761 DISCARD (main_list, max_formats) 2763 empty (work_list) 2764 u = head-of (main_list) 2765 v = head-of (work_list) # which will be null 2767 # the work_list starts empty, so v is 'null'. However, as soon as 2768 # the first item is added to the work list, v references this item, 2769 # which is why there is a condition & re-initialisation of v at the 2770 # bottom of the loop 2772 item.P = u.P 2773 u.parent = item 2774 num_formats = size-of (main_list) 2776 for i = 0 to (num_formats - 2) 2778 if (i = (num_formats - 4) and do_reserve) then 2779 RESERVE (u, v, reserve, flag) 2780 endif 2782 u_next = next-item (u) 2783 v_next = next-item (v) 2785 if (at-end (v) or ( 2786 not at-end (u_next) and (u_next.P <= v.P)) then 2788 item.P = u.P + u_next.P 2789 append (work_list, item) 2790 u.parent = item 2791 u_next.parent = item 2792 u = next-item (u_next) 2794 else if (at-end (u) or ( 2795 not at-end (v_next) and v_next.P <= u.P)) then 2797 item.P = v.P + v_next.P 2798 append (work_list, item) 2799 v.parent = item 2800 v_next.parent = item 2801 v = next-item (v_next) 2803 else 2805 item.P = u.P + v.P 2806 append (work_list, item) 2807 u.parent = item 2808 v.parent = item 2810 u = u_next 2811 v = next-item (v) 2813 endif 2815 if (i = 0) then 2817 v = head-of (work_list) 2819 endif 2821 end loop 2823 item.parent = NULL_ITEM 2824 cumulative_N = 0 2825 empty (flag_list) 2826 w = tail-of (main_list) 2828 for i = 0 to (num_formats - 1) 2830 z = w 2831 length = 0 2833 do 2834 if do_reserve then 2835 if (type = 0 and (z = reserve [0])) then 2836 length = length + 1 2838 else if (type = 1 and (z = reserve [0] or z = reserve [1])) then 2839 length = length + 1 2841 else if (type = 2 and z = reserve [3]) then 2842 length = length + 1 2844 else if (type = 2 and z = reserve [1]) then 2845 length = length - 1 2847 else if (type = 3 and z = reserve [2]) then 2848 length = length + 1 2849 endif 2851 endif 2853 length = length + 1 2854 z = z.parent 2856 loop until z.parent = NULL_ITEM 2858 cumulative_N = cumulative_N + 1 2859 append (w.length_list, length) 2860 append (w.cum_N_list, cumulative_N) 2862 # Add this length into the flag_list - either by adding 2863 # 1 to the element with correct length or by adding a 2864 # new element. Flag_list should be in ascending order of 2865 # lengths. 2867 found_same_length = 0 2868 fl_elt = head-of (flag_list) 2870 while (fl_elt <> NULL and found_same_length = 0) 2871 if fl_elt.length = length then 2872 found_same_length = 1 2873 endif 2874 end while 2876 if found_same_length = 0 then 2877 fl_elt.N = cumulative_N 2878 fl_elt.length = length 2879 append (flag_list, fl_elt) 2880 else 2881 fl_elt.N = fl_elt.N + 1 2882 endif 2884 w = previous-item (w) 2886 end loop 2888 # Generate the Huffman flags 2890 flag_item.N = 0 2891 flag_item.length = 0 2892 flag_item.flags = 0 2893 prepend(flag_list,flag_item) 2895 fl_3 = head-of (flag_list) 2896 fl_2 = next-item (fl_3) 2898 fl_2.flags = str(fl_2.length,0) 2899 fl_1 = next-item(fl_2) 2901 while (fl_1 <> NULL) 2903 fl_1.flags = str(fl_1.length,(fl_2.flags + (fl_2.N - fl_3.N)) 2904 * 2 ^ (fl_1.length - fl_2.length)) 2906 fl_1 = next-item (fl_1) 2907 fl_2 = next-item (fl_2) 2908 fl_3 = next-item (fl_3) 2910 end while 2912 end BUILD_FLAGS 2914 # 2915 # procedure to work out whether to use one or two list 2916 # items to reserve the bits '111' 2917 # 2918 procedure RESERVE (u, v, reserve, flag) 2920 var temp_u, temp_v 2921 var t 2922 var prob 2924 temp_u = u 2925 temp_v = v 2927 flag = 0 2929 # This section works out which order the 4 remaining nodes 2930 # will be formed into tree 2931 for t = 0 to 3 2933 if (at-end (temp_v) or ( 2934 not at-end (temp_u) and temp_u.P <= temp_v.P) then 2936 reserve [t] = temp_u 2937 prob [t] = temp_u.P 2938 temp_u = next-item (temp_u) 2940 else 2942 reserve [t] = temp_v 2943 prob [t] = temp_v.P 2944 temp_v = next-item (temp_v) 2946 endif 2948 end loop 2950 # prob[0] = A ... prob [3] = D 2951 # This function is pretending to create a node which will 2952 # have the same probability as B and will take up the bit 2953 # pattern '111'. If the new node were to be created then 2954 # check whether a + 2*B >= D to decide whether or not the 2955 # node comes before or after B. This part looks at the 2956 # probabilities to work out which nodes would have their 2957 # lengths changed by inserting this node so they can be 2958 # changed accordingly in the length counting (rather than 2959 # actually trying to add the new node) 2961 if ((prob [0] + prob [1]) >= prob [3]) then 2962 flag = 0 2963 else 2964 if ((prob [0] + prob [1]) < prob [2]) then 2965 if ((prob [0] + (2 * prob [1])) < prob [3]) then 2966 flag = 1 2967 else 2968 flag = 2 2969 endif 2970 else 2971 if ((prob [1] + prob[2] < prob [3])) then 2972 flag = 3 2973 else 2974 flag = 2 2975 endif 2976 endif 2977 endif 2979 end RESERVE 2981 The procedure RESERVE is called at most once by BUILD-FLAGS to 2982 reserve the bit pattern "111" in the first octet of each compressed 2983 header (for compatibility with the ROHC framework). 2985 The output of BUILD-FLAGS is the main_list each item of which has 2986 three key parts: 2988 list_item.length_list List of lengths of numbers of flags (for 2989 EPIC-LITE this will only have one 2990 element). The lengths should 2991 (automatically) be in ascending order. 2993 list_item.cum_N_list A list of numbers - corresponding to the 2994 number of headers with each flag length 2995 in the length_list (again for EPIC-LITE 2996 there will only be one element). The 2997 numbers should (automatically) be in 2998 ascending order. 3000 list_item.identifier Some unique identifier which can be used 3001 to perform mapping between these flags 3002 and the header format used to generate a 3003 compressed header requiring these flags. 3005 and a flag_list each item of which has the following elements: 3007 flag_list_item.length The length of the Huffman flags. 3009 flag_list_item.N The cumulative number of headers with 3010 Huffman flags up to this length. 3012 flag_list_item.flags The flags for the first header with 3013 flags of this length (the rest can be 3014 worked out from this information). 3016 Note that the compressor assigns bit patterns to the indicator flags 3017 using the following rules: 3019 1. The most probable headers have all "0" indicator flags 3021 2. The indicator flags for the next header format are calculated by 3022 adding 1 to the previous flags (treated as an integer) and 3023 padding with enough 0s to reach the correct length 3025 As an example, the indicator flags for a set of compressed header 3026 formats are given below: 3028 main_list 3029 Compressed header format No. of flags Cumulative_N 3031 1 2 1 3032 2 2 2 3033 3 3 3 3034 4 4 4 3035 5 4 5 3036 6 4 6 3037 7 5 7 3038 8 6 8 3039 9 6 9 3041 flag_list 3042 No. of flags N Bit pattern of flags 3043 2 1 00 3044 3 3 100 3045 4 4 1010 3046 5 7 11010 3047 6 8 110110 3049 Note that the most probable compressed header format will have all 3050 "0" indicator flags, whilst the least probable header format will 3051 have all "1" indicator flags (except for the bit pattern "111" if 3052 this is reserved for the ROHC [1] framework). 3054 A.4 Library of methods 3056 This section gives pseudocode for each of the methods in the library. 3057 Note that for each method three pieces of pseudocode are given: 3058 corresponding to the function COMPRESS, and procedures DECOMPRESS and 3059 BUILD described previously. 3061 Note that all of the global variables required for these procedures 3062 are defined at the beginning of Appendix A. 3064 It is assumed that as soon as the 'return' command is encountered, 3065 the procedure stops. 3067 For COMPRESS functions which check through the r values stored in the 3068 context, the value of r is implementation-specific. Note that if any 3069 of the r context values is empty, any method attempting to compress 3070 relative to the context will automatically fail. 3072 A.4.1 STATIC 3074 STATIC (P%) 3075 COMPRESS (STATIC) 3076 var context_val, item 3077 var n, i 3079 context (enc_index, 1, context_val) 3080 n = length (context_val) 3082 # check that the value to be compressed matches each of the r 3083 # values stored in context for this encoding - if not then 3084 # STATIC can't be used to compress this encoding 3086 for i = 1 to r 3087 context (enc_index, i, context_val) 3088 if (context_val <> top (uncompressed_data, n)) then 3089 return false 3090 endif 3091 end loop 3093 pop (uncompressed_data, n, item) 3094 save (enc_index, item, storage) 3095 enc_index = enc_index + 1 3096 return true 3097 end COMPRESS 3099 DECOMPRESS (STATIC) 3100 var context_val 3102 context (enc_index, 1, context_val) 3103 push (uncompressed_data, context_val) 3104 save (enc_index, context_val, storage) 3105 enc_index = enc_index + 1 3106 end DECOMPRESS 3108 BUILD (STATIC, P, format) 3109 var item 3111 item.P = P 3112 item.N = 0 3113 empty (item.id) 3114 append (format, item) 3115 end BUILD 3117 A.4.2 IRREGULAR 3118 IRREGULAR(n,P%) 3120 COMPRESS (IRREGULAR) 3121 var item 3123 pop (uncompressed_data, n, item) 3124 push (compression_stack, item) 3125 save (enc_index, item, storage) 3126 enc_index = enc_index + 1 3127 return true 3128 end COMPRESS 3130 DECOMPRESS (IRREGULAR) 3131 var item 3133 pop (compression_stack, n, item) 3134 push (uncompressed_data, item) 3135 save (enc_index, item, storage) 3136 enc_index = enc_index + 1 3137 end DECOMPRESS 3139 BUILD (IRREGULAR, P, format) 3140 var item 3142 item.P = P 3143 item.N = n 3144 empty (item.id) 3145 append (format, item) 3146 end BUILD 3148 A.4.2.1 IRREGULAR-PADDED 3150 IRREGULAR-PADDED(n,k,P%) 3152 COMPRESS (IRREGULAR-PADDED) 3153 var item, temp 3155 if (value (top (uncompressed_data, n - k)) <> 0) then 3156 return false 3157 else 3158 pop (uncompressed_data, n, item) 3159 temp = lsb (item, k) 3160 push (compression_stack, temp) 3161 save (enc_index, item, storage) 3162 enc_index = enc_index + 1 3163 return true 3164 endif 3165 end COMPRESS 3167 DECOMPRESS (IRREGULAR-PADDED) 3168 var item, temp 3169 var full 3171 full = 0 3172 pop (compression_stack, k, temp) 3173 full = full + value (temp) 3174 item = str (n, full) 3175 push (uncompressed_data, item) 3176 save (enc_index, item, storage) 3177 enc_index = enc_index + 1 3178 end DECOMPRESS 3180 BUILD (IRREGULAR-PADDED, P, format) 3181 var item 3183 item.P = P 3184 item.N = k 3185 empty (item.id) 3186 append (format, item) 3187 end BUILD 3189 A.4.3 VALUE 3190 VALUE(n,v,P%) 3192 COMPRESS (VALUE) 3193 var value 3195 if (top (uncompressed_data, n) <> v) then 3196 return false 3197 else 3198 pop (uncompressed_data, n, value) 3199 save (enc_index, value, storage) 3200 enc_index = enc_index + 1 3201 return true 3202 endif 3203 end COMPRESS 3205 DECOMPRESS (VALUE) 3206 var item 3208 item = str (n, v) 3209 push (uncompressed_data, n, v) 3210 save (enc_index, item, storage) 3211 enc_index = enc_index + 1 3212 end DECOMPRESS 3214 BUILD (VALUE, P, format) 3215 var item 3217 item.P = P 3218 item.N = 0 3219 empty (item.id) 3220 append (format, item) 3221 end BUILD 3223 A.4.4 LSB 3225 LSB(k,p,P%) 3227 COMPRESS (LSB) 3228 var context_val, item, temp, new_item, lsb_val, p_item 3229 var n, i 3231 context (enc_index, 1, context_val) 3232 n = length (context_val) 3233 p_item = str (n, p) 3234 new_item = top (uncompressed_data, n) 3235 for i = 1 to r 3236 context (enc_index, i, context_val) 3238 # check new_item in interval 3239 # [value (context_val)-p, value (context_val)-p+2^k] 3241 temp = (new_item - context_val + p_item) 3242 if (value (temp) < 0) or (value (temp) >= 2^k) then 3243 return false 3244 endif 3245 end loop 3247 pop (uncompressed_data, n, item) 3248 lsb_val = lsb (item, k) 3249 push (compression_stack, lsb_val) 3250 save (enc_index, item, storage) 3251 enc_index = enc_index + 1 3252 return true 3253 end COMPRESS 3255 DECOMPRESS (LSB) 3256 var context_val, interval_start, interval_end, recd, p_item 3257 var new_item, twok_item 3258 var n, new, start, end 3260 context (enc_index, 1, context_val) 3261 n = length (context_val) 3262 p_item = str (n, p) 3263 twok_item = str (n, 2^k) 3265 pop (compression_stack, k, recd) 3266 interval_start = context_val - p 3267 interval_end = interval_start + twok_item 3268 new_item = concat (msb (interval_start, (n-k)), recd) 3270 # check whether value (new_item) is in interval 3271 # [value (interval_start), value (interval_end)] 3272 # allowing for the interval to wrap over zero. If not then 3273 # recalculate new_item 3275 start = value (interval_start) 3276 end = value (interval_end) 3277 new = value (new_item) 3279 if (((start < end) and ((new < start) or (new > end))) or 3280 ((start > end) and ((new > start) or (new < end)))) then 3282 new_item = concat (msb (interval_end, (n-k)), recd) 3284 endif 3286 push (uncompressed_data, new_item) 3287 save (enc_index, new_item, storage) 3288 enc_index = enc_index + 1 3289 end DECOMPRESS 3291 BUILD (LSB, P, format) 3292 var item 3294 item.P = P 3295 item.N = k 3296 empty (item.id) 3297 append (format, item) 3298 end BUILD 3300 A.4.5 UNCOMPRESSED 3302 UNCOMPRESSED(n,d,m,p) 3304 COMPRESS (UNCOMPRESSED) 3305 var scale_len 3306 var unc, len_item 3308 scale_len = floor( value((top(control_data)) / d) * m + p) 3309 if (stack-size (uncompressed_data) < scale_len) then 3310 return false 3311 else 3312 pop (uncompressed_data, scale_len, unc) 3313 push (unc_fields, unc) 3314 pop (control_data, len_item) 3315 if (length (len_item) <> n) then 3316 return false 3317 endif 3318 push (uncompressed_data, len_item) 3319 return true 3320 endif 3321 end COMPRESS 3322 DECOMPRESS (UNCOMPRESSED) 3323 var scale_len 3324 var unc, len_item 3326 pop (uncompressed_data, n, len_item) 3327 scale_len = floor( (value (len_item) / d) * m + p) 3328 push (control_data, len_item) 3329 pop (unc_fields, scale_len, unc) 3330 push (uncompressed_data, unc) 3331 end DECOMPRESS 3333 BUILD 3334 end BUILD 3336 A.4.6 STACK encoding methods 3338 A.4.6.1 STACK-TO-CONTROL 3340 STACK-TO-CONTROL(n) 3342 COMPRESS (STACK-TO-CONTROL) 3343 var item 3345 pop (uncompressed_data, n, item) 3346 push (control_data, item) 3347 return true 3348 end COMPRESS 3350 DECOMPRESS (STACK-TO-CONTROL) 3351 var item 3353 pop (control_data, item) 3354 push (uncompressed_data, item) 3355 end DECOMPRESS 3357 BUILD (STACK-TO-CONTROL, 100%, format) 3358 end BUILD 3360 A.4.6.2 STACK-FROM-CONTROL 3362 STACK-FROM-CONTROL(n) 3364 COMPRESS (STACK-FROM-CONTROL) 3365 var item 3367 pop (control_data, item) 3368 if (length (item) <> n) then 3369 return false 3370 endif 3371 push (uncompressed_data, item) 3372 return true 3373 end COMPRESS 3375 DECOMPRESS (STACK-TO-CONTROL) 3376 var item 3378 pop (uncompressed_data, n, item) 3379 push (control_data, item) 3380 end DECOMPRESS 3382 BUILD (STACK-TO-CONTROL, 100%, format) 3383 end BUILD 3385 A.4.6.3 STACK-PUSH-MSN 3387 STACK-PUSH-MSN(n) 3389 COMPRESS (STACK-PUSH-MSN) 3390 var temp 3392 temp = str (n, value (MSN) mod 2^n) 3393 push (control_data, temp) 3394 return true 3395 end COMPRESS 3397 DECOMPRESS (STACK-PUSH-MSN) 3398 var item 3400 pop (control_data, item) 3401 end DECOMPRESS 3403 BUILD (STACK-PUSH-MSN, 100%, format) 3404 end BUILD 3406 A.4.6.4 STACK-POP-MSN 3408 STACK-POP-MSN(n) 3410 COMPRESS (STACK-POP-MSN) 3411 var item, temp 3413 pop (uncompressed_data, n, item) 3414 temp = str (n, value (MSN) mod 2^n) 3416 if (item <> temp) 3417 #value on stack wasn't MSN 3418 return false 3419 endif 3420 return true 3421 end COMPRESS 3423 DECOMPRESS (STACK-POP-MSN) 3424 var temp 3426 temp = str (n, value (MSN) mod 2^n) 3427 push (uncompressed_data, temp) 3428 end DECOMPRESS 3430 BUILD (STACK-POP-MSN, 100%, format) 3431 end BUILD 3433 A.4.6.5 STACK-ROTATE 3435 STACK-ROTATE(n,m) 3437 COMPRESS (STACK-ROTATE) 3438 rotate (control_data, n, m) 3439 return true 3440 end COMPRESS 3442 DECOMPRESS (STACK-ROTATE) 3443 rotate (control_data, n, (n - m)) 3444 end DECOMPRESS 3446 BUILD (STACK-ROTATE, 100%, format) 3447 end BUILD 3449 A.4.7 INFERRED encoding methods 3451 A.4.7.1 INFERRED-TRANSLATE 3453 INFERRED-TRANSLATE(n,m,a(0),b(0),a(1),b(1)...,a(k-1),b(k-1)) 3455 COMPRESS (INFERRED-TRANSLATE) 3456 var item, trans_item 3457 var found, i 3459 found = 0 3460 i = 0 3462 while ((i < k) and (found = 0)) 3463 if (value (top (uncompressed_data, m)) = b(i)) 3464 pop (uncompressed_data, m, item) 3465 trans_item = str (n, a(i)) 3466 push (control_data, trans_item) 3467 found = 1 3468 else 3469 i = i + 1 3470 endif 3471 end while 3473 return found 3474 end COMPRESS 3475 DECOMPRESS (INFERRED-TRANSLATE) 3476 var trans_item 3477 var i, found 3479 found = 0 3480 i = 0 3482 pop (control_data, trans_item) 3483 while ((i < k) and (found = 0)) 3484 if (value (trans_item) = a(i)) 3485 push (uncompressed_data, m, b(i)) 3486 found = 1 3487 else 3488 i = i + 1 3489 endif 3490 end while 3491 end DECOMPRESS 3493 BUILD (INFERRED-TRANSLATE, 100%, format) 3494 end BUILD 3496 A.4.7.2 INFERRED-SIZE 3498 INFERRED-SIZE(n,p) 3500 COMPRESS (INFERRED-SIZE) 3501 var item 3502 var bits_in_byte # usually 8! 3504 if ((bits_in_byte * value (top (uncompressed_data, n))) + p) <> 3505 stack-size (uncompressed_data) then 3506 return false 3508 else 3509 pop (uncompressed_data, n, item) 3510 return true 3511 endif 3512 end COMPRESS 3514 DECOMPRESS (INFERRED-SIZE) 3515 var size 3516 var bits_in_byte # usually 8! 3518 size = (stack-size (uncompressed_data) + n - p) / bits_in_byte) 3519 push (uncompressed_data, n, size) 3520 end DECOMPRESS 3522 BUILD (INFERRED-SIZE, 100%, format) 3523 end BUILD 3525 A.4.7.3 INFERRED-OFFSET 3526 INFERRED-OFFSET(n) 3528 COMPRESS (INFERRED-OFFSET) 3529 var item, base, offset 3531 pop (uncompressed_data, n, item) 3532 pop (control_data, base) 3533 if (length (base) <> n) then 3534 return false 3535 endif 3537 offset = item - base 3538 push (uncompressed_data, offset) 3539 push (uncompressed_data, base) 3540 return true 3541 end COMPRESS 3543 DECOMPRESS (INFERRED-OFFSET) 3544 var item, base, offset 3546 pop (uncompressed_data, n, base) 3547 push (control_data, base) 3548 pop (uncompressed_data, n, offset) 3549 item = offset + base 3550 push (uncompressed_data, item) 3551 end DECOMPRESS 3553 BUILD (INFERRED-OFFSET, 100%, format) 3554 end BUILD 3556 A.4.7.4 INFERRED-IP-CHECKSUM 3558 INFERRED-IP-CHECKSUM(new_method) 3560 COMPRESS (INFERRED-IP-CHECKSUM) 3561 var compress_function 3562 var can_compress 3563 var item, ip_sum 3565 # zero the ip checksum bits in the header 3566 pop (uncompressed_data, 80, item) 3567 pop (uncompressed_data, 16, ip_sum) 3568 push (uncompressed_data, 16, 0) 3569 push (uncompressed_data, item) 3571 compress_function = lookup-compress-function 3572 (extract-name (new_method)) 3574 can_compress = call compress_function 3575 (extract-name (new_method)) 3577 return can_compress 3578 end COMPRESS 3580 DECOMPRESS (INFERRED-IP-CHECKSUM) 3581 var decompress_function 3582 var item, temp 3583 var init_len, final_len, decomp_len, ip_sum 3585 init_len = stack-size (uncompressed_data) 3586 decompress_function = lookup-decompress-function 3587 (extract-name (new_method)) 3589 call decompress_function (extract-name (new_method)) 3590 final_len = stack-size (uncompressed_data) 3592 decomp_len = final_len - init_len 3593 ip_sum = compute-16-checksum (uncompressed_data, decomp_len) 3595 pop (uncompressed_data, 80, item) 3596 pop (uncompressed_data, 16, temp) 3597 push (uncompressed_data, 16, ip_sum) 3598 push (uncompressed_data, item) 3599 end DECOMPRESS 3601 BUILD (INFERRED-IP-CHECKSUM, 100%, format) 3602 var build_function 3604 build_function = lookup-build-function 3605 (extract-name (new_method)) 3607 call build_function (extract-name (new_method), 100%, format) 3608 end BUILD 3610 A.4.8 NBO 3611 NBO(n) 3613 COMPRESS (NBO) 3614 var original, swapped 3615 var nbo_flag 3617 pop (uncompressed_data, n, original) 3618 choose (nbo_flag of zero or one) 3619 # according to whether original is in network byte order or not 3620 # (1 implies it is, 0 implies it isn't) 3621 # this decision can be made based on the context history 3623 push (uncompressed_data, 1, nbo_flag) 3624 if (nbo_flag = 0) then 3625 swapped = byte-swap (original) 3626 push (uncompressed_data, swapped) 3627 else 3628 push (uncompressed_data, original) 3629 endif 3631 # store the original value or other implementation specific 3632 # information for making decision about flag value 3633 save (enc_index, original, storage) 3634 enc_index = enc_index + 1 3635 return true 3636 end COMPRESS 3638 DECOMPRESS (NBO) 3639 var original, decomped, nbo_flag 3641 pop (uncompressed_data, n, decomped) 3642 pop (uncompressed_data, 1, nbo_flag) 3644 if (value (nbo_flag) = 1 then 3645 original = decomped 3646 else 3647 original = byte-swap (decomped) 3648 endif 3650 push (uncompressed_data, original) 3651 enc_index = enc_index + 1 3652 end DECOMPRESS 3654 BUILD (NBO, 100%, format) 3655 end BUILD 3657 A.4.9 SCALE 3659 SCALE(n) 3661 COMPRESS (SCALE) 3662 var original 3663 var scale_f, scaled_val, remainder 3665 pop (uncompressed_data, n, original) 3666 choose (scale_f) # such that original is changing by a multile 3667 # of scale_f each header. This decision can 3668 # be based on context history 3670 scaled_val = value (original) / scale_f 3671 remainder = value (original) mod scale_f 3673 push (uncompressed_data, n, scaled_val) 3674 push (uncompressed_data, n, remainder) 3675 push (uncompressed_data, n, scale_f) 3677 # store the original value or other implementation specific 3678 # information for making decision about scale_f 3679 save (enc_index, original, storage) 3680 enc_index = enc_index + 1 3681 return true 3682 end COMPRESS 3684 DECOMPRESS (SCALE) 3685 var scaled_val, scale_f, remainder 3686 var original 3688 pop (uncompressed_data, n, scale_f) 3689 pop (uncompressed_data, n, remainder) 3690 pop (uncompressed_data, n, scaled_val) 3692 original = ((scaled_val * scale_f) + remainder) mod 2^n 3693 push (uncompressed_data, n, original) 3694 enc_index = enc_index + 1 3695 end DECOMPRESS 3697 BUILD (SCALE, 100%, format) 3698 end BUILD 3700 A.4.10 OPTIONAL 3702 OPTIONAL(new_method) 3704 COMPRESS (OPTIONAL) 3705 var flag 3706 var compress_function 3707 var can_compress, n 3708 var enc 3710 pop (control_data, flag) 3711 if (value (flag) = 1) then 3712 compress_function = lookup-compress-function 3713 (extract-name (new_method)) 3715 can_compress = call compress_function 3716 (extract-name (new_method)) 3717 else 3718 choose (format to encode new_method) 3719 # compressor choice of format for new_method, where enc is the 3720 # format chosen 3722 if u_flag = 0 then 3723 # not under U method then pad with bits of zero 3724 n = count-bits (new_method, enc) 3725 push (compression_stack, n, 0) 3726 else 3727 # don't need to pad as under U method 3728 endif 3730 store (method_chosen, OPTIONAL, enc) 3731 can_compress = 1 3732 endif 3734 push (control_data, flag) 3735 return can_compress 3736 end COMPRESS 3738 DECOMPRESS (OPTIONAL) 3739 var flag, item 3740 var decompress_function 3741 var n 3742 var enc 3744 pop (control_data, flag) 3745 if (value (flag = 1)) then 3746 decompress_function = lookup-decompress-function 3747 (extract-name (new_method)) 3749 call decompress_function (extract-name (new_method)) 3750 else 3751 # enc is the format sent for new_method (obtained from the 3752 # indicator flags) 3754 if u_flag = 0 then 3755 # not under U method so need to remove bits of padding 3756 n = count-bits (new_method, enc) 3757 pop (compression_stack, n, item) 3758 else 3759 # don't need to remove padding as under U method 3760 endif 3761 endif 3763 push (control_data, flag) 3764 end DECOMPRESS 3766 BUILD (OPTIONAL, 100%, format) 3767 var build_function 3769 build_function = lookup-build-function 3770 (extract-name (new_method)) 3772 call build_function (extract-name (new_method), P, format) 3774 end BUILD 3776 A.4.11 MANDATORY 3778 MANDATORY(new_method) 3780 COMPRESS (MANDATORY) 3781 var flag 3782 var compress_function 3783 var can_compress 3785 pop (control_data, flag) 3786 if (value (flag) <> 1) then 3787 return false 3788 else 3789 compress_function = lookup-compress-function 3790 (extract-name (new_method)) 3792 can_compress = call compress_function 3793 (extract-name (new_method)) 3794 endif 3796 push (control_data, flag) 3797 return can_compress 3798 end COMPRESS 3800 DECOMPRESS (MANDATORY) 3801 var decompress_function 3802 var flag 3804 pop (control_data, flag) 3805 decompress_function = lookup-decompress-function 3806 (extract-name (new_method)) 3808 call decompress_function (extract-name (new_method)) 3809 push (control_data, flag) 3810 end DECOMPRESS 3812 BUILD (MANDATORY, 100%, format) 3813 var build_function 3815 build_function = lookup-build-function 3816 (extract-name (new_method)) 3818 call build_function (extract-name (new_method), 100%, format) 3819 end BUILD 3821 A.4.12 CONTEXT 3823 CONTEXT(new_method,k) 3825 COMPRESS (CONTEXT) 3826 var n, j, m 3827 var compress_function 3828 var can_compress 3830 n = ceiling (log2(k-1)) 3831 choose (j < k) # compressor choice 3832 m = context-size (new_method) 3833 enc_index = enc_index + j * m 3834 compress_function = lookup-compress-function 3835 (extract-name (new_method)) 3837 can_compress = call compress_function 3838 (extract-name (new_method)) 3839 push (uncompressed_data, n, j) 3840 enc_index = enc_index + (k - j - 1) * m 3841 return can_compress 3842 end COMPRESS 3844 DECOMPRESS (CONTEXT) 3845 var n, j, m 3846 var decompress_function 3847 var index 3849 n = ceiling (log2(k-1)) 3850 pop (uncompressed_data, n, index) 3851 j = value (index) 3853 m = context-size (new_method) 3854 enc_index = enc_index + j * m 3855 decompress_function = lookup-decompress-function 3856 (extract-name (new_method)) 3858 call decompress_function (extract-name (new_method)) 3859 enc_index = enc_index + (k - j - 1) * m 3860 end DECOMPRESS 3862 BUILD (CONTEXT, 100%, format) 3863 var build_function 3865 build_function = lookup-build-function (new_method) 3867 call build_function (extract-name (new_method), 100%, format) 3868 end BUILD 3870 A.4.13 LIST 3872 LIST(n,d,m,p,z,new_method(0),new_method(1),..., 3873 new_method(k-1),v(0),v(1),...,v(j)) 3875 COMPRESS (LIST) 3876 var scale_len, i, can_compress, stack_len, bits 3877 var comp_len, order, presence 3878 var present [0..(k-1)], unc_length 3879 var compress_function 3881 top(control_data, unc_length) 3882 scale_len = floor( value(unc_length) / d) * m + p) 3884 for i = 0 to (k - 1) 3885 present [i] = str (1,0) 3886 end loop 3888 order = 0 3889 bits = ceiling (log2(k-1)) 3890 i = 0 3891 list_start_enc_index = enc_index 3893 while (scale_len > 0) 3895 # basically loop through the methods until all scale_len bits 3896 # are compressed and any of the methods which aren't used are 3897 # marked as not used. The order in which methods are checked 3898 # is implementation specific but some ways will require 3899 # changing the order more frequently (reducing efficiency) than 3900 # others. 3902 stack_len = stack-size (uncompressed_data) 3903 can_compress = false 3904 i = 0 3906 while (i < k) and (can_compress = false) 3907 if (value (present [i]) = 0) and 3908 ((i >= j) or ((i < j) and 3909 (value (top (uncompressed_data, z)) = v(i)))) then 3910 present [i] = str (1,1) 3911 order = order * 2^bits + i 3912 push (control_data, present [i]) 3913 for x = 0 to i 3914 enc_index = enc_index + context-size (new_methods(x)) 3915 compress_function = lookup-compress-function 3916 (extract-name (new_method(i))) 3918 can_compress = call compress_function 3919 (extract-name (new_method(i))) 3920 if can_compress = false then 3921 return false 3922 endif 3923 comp_len = stack_len - stack-size (uncompressed_data) 3924 scale_len = scale_len - comp_len 3925 pop (control_data, present [i]) 3926 enc_index = list_start_enc_index 3927 if (length (present[i]) <> 1) then 3928 return false 3929 endif 3931 else 3932 i = i + 1 3933 endif 3934 end while 3935 end while 3937 # process remaining LIST entries that have not been used 3938 # (i.e. are not present in the header) 3940 for i = 0 to (k - 1) 3941 if (value (present [i]) = 0) then 3942 push (control_data, present [i]) 3943 for x = 0 to i 3944 enc_index = enc_index + context-size (new_methods(x)) 3945 order = order * 2^bits + i 3946 compress_function = lookup-compress-function 3947 (extract-name (new_method(i))) 3949 can_compress = call compress_function 3950 (extract-name (new_method(i))) 3951 if can_compress = false then 3952 return false 3953 endif 3954 pop (control_data, present [i]) 3955 enc_index = list_start_enc_index 3957 if (length (present[i]) <> 1) then 3958 return false 3959 endif 3961 endif 3962 end loop 3964 presence = 0 3965 for i = 0 to (k - 1) 3966 presence = presence * 2 + value (present[i]) 3967 end loop 3969 push (uncompressed_data, k, presence) 3970 push (uncompressed_data, bits*k, order) 3971 return true 3972 end COMPRESS 3974 DECOMPRESS (LIST) 3975 var decompress_function 3976 var presence, order, i, j, bits, uncomp_len, old_len, 3977 var original_len 3978 var present [0..(k - 1)] 3979 var presence_item, order_item 3981 bits = ceiling (log2(k-1)) 3982 list_start_enc_index = enc_index 3984 pop (uncompressed_data, bits*k, order_item) 3985 pop (uncompressed_data, k, presence_item) 3986 presence = value (presence_item) 3987 order = value (order_item) 3989 for i = 0 to (k - 1) 3990 present [(k - 1) - i] = lsb (presence, 1) 3991 presence = (presence - value (present [(k - 1) - i])) / 2 3992 end loop 3994 for j = 0 to (k - 1) 3995 i = value (lsb (order, bits)) 3996 order = (order � i )/ 2^bits 3998 push (control_data, present [i]) 3999 old_len = stack-size (uncompressed_data) 4000 for x = 0 to i 4001 enc_index = enc_index + context-size (new_methods(x)) 4002 decompress_function = lookup-decompress-function 4003 (extract-name (new_method(i))) 4005 call decompress_function (extract-name (new_method(i))) 4007 enc_index = list_start_enc_index 4008 uncomp_len = uncomp_len + 4009 (stack-size (uncompressed_data) - old_len) 4010 pop (control_data, present[i]) 4012 original_len = ((uncomp_len - p) * d) / m 4013 push (control_data, n, original_len) 4014 end loop 4015 end DECOMPRESS 4016 BUILD (LIST, 100%, format) 4017 var i 4018 var build_function 4019 var temp_format 4021 item.P = convert-percentage (100%) 4022 item.N = 0 4023 empty (item.id) 4024 append (format, item) 4026 for i = 0 to (k - 1) 4027 empty (temp_format) 4028 build_function = lookup-build-function ( 4029 extract-name (new_method(i))) 4030 call build_function (extract-name (new_method(i), 4031 100%, temp_format)) 4033 DISCARD (temp_format) 4034 COMBINE (format, temp_format) 4035 end loop 4036 end BUILD 4038 A.4.13.1 LIST-NEXT 4040 LIST-NEXT (n,new_method(0),new_method(1),..., 4041 new_method(k-1),v(0),v(1),...,v(j)) 4043 # This pseudocode is very similar to LIST, the differences being 4044 # from where the information about which method to use next comes 4045 # from and how to tell when there is no more data to compress using 4046 # this method 4048 COMPRESS (LIST) 4049 var i, can_compress, bits, order, presence, p 4050 var present [0..(k-1)], v, null 4051 var compress_function 4053 for i = 0 to (k - 1) 4054 present [i] = str (1,0) 4055 end loop 4057 order = 0 4058 bits = ceiling (log2(k-1)) 4059 i = 0 4060 pop (control_data, v) 4061 if (length (v) <> n) then 4062 return false 4063 endif 4065 null = str (0, 0) 4067 while (v <> null) 4068 # basically loop through the methods until no more information 4069 # has been put on the control_data stack by the previous method 4070 # (i.e. the end of the list has been reached). The order in 4071 # which methods are checked is implementation specific but some 4072 # ways will require changing the order more frequently 4073 # (reducing efficiency) than others. 4075 can_compress = false 4076 i = 0 4078 while (i < k) and (can_compress = false) 4079 if (value (present [i]) = 0) and 4080 ((i >= j) or ((i < j) and (v = v(i)))) then 4081 present [i] = str (1,1) 4082 order = order * 2^bits + i 4083 push (control_data, present [i]) 4084 p = stack-pointer (control_data) 4085 compress_function = lookup-compress-function 4086 (extract-name (new_method(i))) 4088 can_compress = call compress_function 4089 (extract-name (new_method(i))) 4090 if can_compress = false then 4091 return false 4092 endif 4094 # find out whether there is more to compress by checking 4095 # the position of the stack pointer 4097 if (p <> stack-pointer (control_data)) then 4098 pop (control_data, v) 4099 if (length (v) <> n) then 4100 return false 4101 endif 4102 pop (control_data, present [i]) 4104 else 4105 pop (control_data, present [i]) 4106 v = null 4107 endif 4108 if (length (present[i]) <> 1) then 4109 return false 4110 endif 4112 else 4113 i = i + 1 4114 endif 4115 end while 4116 end while 4118 # process remaining LIST-NEXT entries that have not been used 4119 # (i.e. are not present in the header) 4121 for i = 0 to (k - 1) 4122 if (value (present [i]) = 0) then 4123 push (control_data, present [i]) 4124 order = order * 2^bits + i 4125 compress_function = lookup-compress-function 4126 (extract-name (new_method(i))) 4128 can_compress = call compress_function 4129 (extract-name (new_method(i))) 4130 if can_compress = false then 4132 return false 4133 endif 4134 pop (control_data, present [i]) 4135 if (length (present[i]) <> 1) then 4136 return false 4137 endif 4139 endif 4140 end loop 4142 presence = 0 4143 for i = 0 to (k - 1) 4144 presence = presence * 2 + value (present[i]) 4145 end loop 4147 push (uncompressed_data, k, presence) 4148 push (uncompressed_data, bits*k, order) 4149 return true 4150 end COMPRESS 4152 DECOMPRESS is almost the same as for LIST - the only difference being 4153 that there is no need to keep track of length and push it onto the 4154 control stack at the end as this is implicit in the choice of 4155 methods. BUILD is the same as for LIST 4157 A.4.14 FLAG encoding methods 4159 A.4.14.1 N 4161 N(new_method) 4163 COMPRESS (N) 4164 var compress_function 4165 var can_compress, temp 4167 temp = enc_index 4168 compress_function = lookup-compress-function 4169 (extract-name (new_method)) 4171 can_compress = call compress_function 4172 (extract-name (new_method)) 4174 if (enc_index <> temp) then 4175 clear (temp, storage) 4176 endif 4178 return can_compress 4179 end COMPRESS 4181 DECOMPRESS (N) 4182 var decompress_function 4183 var temp 4185 temp = enc_index 4186 decompress_function = lookup-decompress-function 4187 (extract-name (new_method)) 4189 call decompress_function (extract-name (new_method)) 4191 if (enc_index <> temp) then 4192 clear (temp, storage) 4193 endif 4194 end DECOMPRESS 4196 BUILD (N, (P = extract-probability (new_method)), format) 4197 var build_function 4198 build_function = lookup-build-function (method) 4200 call build_function (extract-name (new_method), P, format) 4201 end BUILD 4203 A.4.14.2 U 4205 U(new_method) 4207 COMPRESS (U) 4208 var compress_function 4209 var can_compress 4211 if u_flag = 0 then 4212 compression_stack = unc_fields 4213 endif 4215 u_flag = u_flag + 1 4216 compress_function = lookup-compress-function 4217 (extract-name (new_method)) 4219 can_compress = call compress_function 4220 (extract-name (new_method)) 4222 u_flag = u_flag - 1 4223 if u_flag = 0 then 4224 compression_stack = compressed_data 4225 endif 4226 return can_compress 4227 end COMPRESS 4229 DECOMPRESS (U) 4230 var decompress_function 4232 if u_flag = 0 then 4233 compression_stack = unc_fields 4234 endif 4236 u_flag = u_flag + 1 4237 decompress_function = lookup-decompress-function 4238 (extract-name (new_method)) 4240 call decompress_function (extract-name (new_method)) 4241 u_flag = u_flag - 1 4242 if u_flag = 0 then 4243 compression_stack = compressed_data 4244 endif 4245 end DECOMPRESS 4247 BUILD (U, (P = extract-probability (new_method)), format) 4248 var build_function 4250 build_function = lookup-build-function (method) 4252 call build_function (extract-name (new_method), P, format) 4254 foreach el in format 4255 el.N = 0 4256 end loop 4257 end BUILD 4259 A.4.15 FORMAT 4261 FORMAT(new_method(0), ..., new_method(k - 1)) 4263 COMPRESS (FORMAT) 4264 var n, can_compress, index_val 4265 var compress_function 4267 n = ceiling(log2(k-1)) 4269 choose (index_val < k) 4270 # The compressor needs to make a choice on which FORMAT 4271 # to use. The algorithm for making this choice is entirely 4272 # up to the compressor. It may wish to take into account 4273 # compression performance (of compressed packets) and 4274 # flexibility of compression. The selection processing 4275 # should allow a successful match to be made (if possible), 4276 # but must also terminate in the case where the packet is 4277 # incompressible. It may be that a choice is made based on 4278 # "CO" state processing, which should be carried forward 4279 # into IR(-DYN) state packet generation. 4281 compress_function = lookup-compress-function ( 4282 extract-name(new_method(index_val))) 4284 can_compress = call compress_function ( 4285 extract-name (new_method(index_val))) 4287 if (can_compress <> false) then 4288 current_set = current_set * k + index_val 4289 endif 4291 if can_compress = false then 4292 return false 4293 else 4294 push (uncompressed_data, n, index_val) 4295 endif 4296 return true 4298 end COMPRESS 4300 DECOMPRESS (FORMAT) 4301 var decompress_function 4302 var n, index 4304 n = ceiling(log2(k-1)) 4305 pop (uncompressed_data, n, index) 4307 if (compressor_state <> "CO") then 4308 # get-method-list in decode-indicator-flags has to assume 4309 # one of the methods from FORMAT to get a list of methods 4310 # used. This may not be the one actually used according to 4311 # the index so the list of methods (ie method_chosen) must 4312 # be reparsed from the original main_list_elt in light of 4313 # the updated information. 4315 format-get-method-list (main_list_elt, method_chosen, 4316 new_method (value (index))) 4317 current_set = current_set * k + value (index) 4318 endif 4320 decompress_function = lookup-decompress-function ( 4321 extract-name (new_method(value (index)))) 4323 call decompress_function ( 4324 extract-name (new_method(value (index)))) 4326 end DECOMPRESS 4328 BUILD (FORMAT, 100%, format) 4329 var j, i 4330 var build_function 4331 var temp_format 4332 if (compressor_state = "CO") then 4333 j = current_set mod k 4335 current_set = current_set / k 4336 build_function = lookup-build-function ( 4337 extract-name (new_method(j))) 4338 call build_function (extract-name (new_method(j)), 4339 100%, format) 4340 else 4341 for i = 0 to (k - 1) 4342 empty (temp_format) 4343 build_function = lookup-build-function ( 4344 extract-name (new_method(i))) 4345 call build_function (extract-name (new_method(i), 4346 100%, temp_format) 4348 foreach item in temp_format 4349 append (item.id, new_method(i)) 4350 append (format, item) 4351 end loop 4352 end loop 4354 DISCARD (format) 4356 endif 4357 end BUILD 4359 A.4.16 CRC 4361 CRC(n,P%) 4363 COMPRESS (CRC) 4364 var crc_function 4366 crc_function = lookup-crc-function (n) 4367 call crc_function (n, crc_static + crc_dynamic, crc) 4368 push (compression_stack, crc) 4369 return true 4370 end COMPRESS 4372 DECOMPRESS (CRC) 4373 pop (compression_stack, n, crc) 4374 end DECOMPRESS 4376 BUILD (CRC, P%, format) 4377 var item 4379 item.P = P 4380 item.N = n 4381 empty (item.id) 4382 append (format, item) 4383 end BUILD 4385 A.4.16.1 MSN-LSB 4387 MSN-LSB(k,p,P%) 4389 COMPRESS (MSN-LSB) 4390 var context_val, item, temp, lsb_val, p_item 4391 var n, i 4393 context (enc_index, 1, context_val) 4394 n = length (context_val) 4395 p_item = str (n, p) 4397 for i = 1 to r 4398 context (enc_index, i, context_val) 4399 # check MSN in interval 4400 # [value (context_val)-p, value (context_val)-p+2^k] 4402 temp = MSN - context_val + p_item 4403 if ((value (temp) < 0) or (value (temp) >= 2^k)) then 4404 return false 4405 endif 4406 end loop 4408 lsb_val = lsb (MSN, k) 4409 push (compression_stack, lsb_val) 4410 save (enc_index, MSN, storage) 4411 enc_index = enc_index + 1 4412 msn_bits = k 4413 return true 4414 end COMPRESS 4416 DECOMPRESS (MSN-LSB) 4417 var context_val, interval_start, interval_end, recd, p_item 4418 var new_item, twok_item, temp, lsbs, twok_extra 4419 var n, m, new, start, end 4421 context (enc_index, 1, context_val) 4422 n = length (context_val) 4423 p_item = str (n, p) 4424 twok_item = str (n, 2^k) 4425 twok_extra = str (n, 2^(k + length (msn_lsbs))) 4427 pop (compression_stack, k, temp) 4428 recd = concat (msn_lsbs, temp) 4430 interval_start = context_val - p_item 4431 interval_end = interval_start + twok_extra 4432 new_item = concat (msb (interval_start, (n-k-length (msn_lsbs))), 4433 recd) 4435 # check whether value (new_item) is in interval 4436 # [value (interval_start), value (interval_end)] 4437 # allowing for the interval to wrap over zero. If not then 4438 # recalculate new_item 4440 start = value (interval_start) 4441 end = value (interval_end) 4442 new = value (new_item) 4444 if (((start < end) and ((new < start) or (new > end))) or 4445 ((start > end) and ((new > start) or (new < end)))) then 4447 new_item = concat (msb (interval_end, (n-k-length (msn_lsbs))), 4448 recd) 4449 endif 4451 MSN = new_item 4452 save (enc_index, new_item, storage) 4453 enc_index = enc_index + 1 4454 end DECOMPRESS 4456 BUILD (MSN-LSB, P, format) 4457 var item 4459 item.P = P 4460 item.N = k 4461 empty (item.id) 4462 append (format, item) 4463 end BUILD 4465 A.4.16.2 MSN-IRREGULAR 4467 MSN-IRREGULAR(n,P%) 4469 COMPRESS (MSN-IRREGULAR) 4470 push (compression_stack, MSN) 4471 save (enc_index, MSN, storage) 4472 enc_index = enc_index + 1 4473 msn_bits = n 4474 return true 4475 end COMPRESS 4477 DECOMPRESS (MSN-IRREGULAR) 4478 pop (compression_stack, n, MSN) 4479 save (enc_index, MSN, storage) 4480 enc_index = enc_index + 1 4481 end DECOMPRESS 4483 BUILD (MSN-IRREGULAR, P, format) 4484 var item 4486 item.P = P 4487 item.N = n 4488 empty (item.id) 4489 append (format, item) 4490 end BUILD 4492 A.4.16.3 SET-MSN 4494 SET-MSN(n) 4496 COMPRESS (SET-MSN) 4497 var item 4499 pop (uncompressed_data, n, item) 4500 MSN = item 4501 return true 4502 end COMPRESS 4504 DECOMPRESS (SET-MSN) 4505 push (uncompressed_data, MSN) 4506 end DECOMPRESS 4508 BUILD (SET-MSN, 100%, format) 4509 end BUILD 4511 A.5 ABNF description of the input language 4513 The following is an ABNF description of a ROHC [1] profile generated 4514 using EPIC-LITE: 4516 = 4517 4518 4519 4520 4521 4522 [ ] 4523 [ ] 4525 = 1*(%x09 | %x0A | %x0D | %x20) 4526 ; white space used as 4527 ; delimiters 4529 = "profile_identifier" 4530 4532 = "max_formats" 4534 = "max_sets" 4536 = "bit_alignment" 4538 = "npatterns" 4540 = "CO packet" 4542 = "IR-DYN packet" 4543 4545 = "IR packet" 4547 = 1*() 4549 = "0" | "1" | "2" | "3" | "4" | 4550 "5" | "6" | "7" | "8" | "9" 4552 = "0x" *() 4554 = | "a" | "b" | "c" | "d" 4555 | "e" | "f" | "A" | "B" | "C" | 4556 "D" | "E" | "F" 4558 The following is an ABNF description of a new encoding method written 4559 using the input language (note that the previous ABNF rules still 4560 apply). Comments are contained between a ";" symbol and the end of 4561 the line, and are ignored in the input language. 4563 = "=" 4564 1*( ) 4566 = 4567 *( "|" ) 4569 = ["(" *("," 4570 ) ")"] 4572 = *( | | 4573 "_" | "-" | "/" | ".") 4575 = "A" | "B" | "C" | ... | "X" | 4576 "Y" | "Z" | "a" | ... | "z" 4578 = | | | 4579 | 4581 = [] [] 4582 ["." []] "%" 4584 = | | 4585 4587 = "0b" *() 4589 = "0" | "1" 4591 = 4593 = ["-"] 4595 Full Copyright Statement 4597 Copyright (C) The Internet Society (2002). All Rights Reserved. 4599 This document and translations of it may be copied and furnished to 4600 others, and derivative works that comment on or otherwise explain it 4601 or assist in its implementation may be prepared, copied, published 4602 and distributed, in whole or in part, without restriction of any 4603 kind, provided that the above copyright notice and this paragraph are 4604 included on all such copies and derivative works. However, this 4605 document itself may not be modified in any way, such as by removing 4606 the copyright notice or references to the Internet Society or other 4607 Internet organizations, except as needed for the purpose of 4608 developing Internet standards in which case the procedures for 4609 copyrights defined in the Internet Standards process must be 4610 followed, or as required to translate it into languages other than 4611 English. 4613 The limited permissions granted above are perpetual and will not be 4614 revoked by the Internet Society or its successors or assigns. 4616 This document and the information contained herein is provided on an 4617 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 4618 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 4619 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 4620 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 4621 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 4623 Acknowledgement 4625 Funding for the RFC Editor function is currently provided by the 4626 Internet Society.