[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: (draft-ietf-rohc-epic-lite) 00 01 02 03 04 05 06 07 08 09 10 11 12 13 RFC 4997

Network Working Group                  Richard Price, Siemens/Roke Manor
INTERNET-DRAFT                        Robert Finking, Siemens/Roke Manor
Expires: April 2004

                                                        October 27, 2003

          Formal Notation for Robust Header Compression (ROHC-FN)
                 <draft-ietf-rohc-formal-notation-02.txt>

Status of this memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or cite them other than as "work in progress".

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

   This document is a submission of the IETF ROHC WG.  Comments should
   be directed to its mailing list, rohc@ietf.org.


Abstract

   This document defines ROHC-FN: a formal notation for specifying how
   to compress and decompress fields from an arbitrary protocol stack.
   ROHC-FN is intended to simplify the creation of new compression
   profiles to fit within the ROHC [RFC-3095] framework.













Price et al.                                                    [Page 1]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003






Table of contents


   1. Introduction ....................................................4


   2. Terminology .....................................................4


   3. Overview of ROHC-FN .............................................5

      3.1. Scope of ROHC-FN ...........................................5
      3.2. Example using IPv4 .........................................6
      3.3. Adding robustness ..........................................8

   4. Normative definition of ROHC-FN .................................9

      4.1. ROHC-FN syntax .............................................9
      4.2. Comments ..................................................10
      4.2.1. End Of Line Comments ....................................10
      4.2.2. Block Comments ..........................................11
      4.3. Implementation structures .................................11
      4.3.1. The uncomp attribute ....................................12
      4.3.2. The uncomp_start attribute ..............................12
      4.3.3. The uncomp_length attribute .............................12
      4.3.4. The comp attribute ......................................12
      4.3.5. The comp_start attribute ................................12
      4.3.6. The comp_length attribute ...............................12
      4.3.7. The context attribute ...................................12
      4.3.8. The updated_context attribute ...........................13

   5. Encoding methods ...............................................13

      5.1. Basic encoding methods ....................................13
      5.1.1. Value ...................................................14
      5.1.2. Irregular ...............................................14
      5.1.3. Static ..................................................14
      5.1.4. LSB .....................................................15
      5.1.5. Index ...................................................15
      5.2. Relative Field Encoding Methods ...........................15
      5.2.1. Same As .................................................15
      5.2.2. Group ...................................................16
      5.2.3. Expression ..............................................16
      5.2.4. Constant ................................................18
      5.2.5. Derived value ...........................................18
      5.2.6. Inferred_size ...........................................19
      5.2.7. Inferred_offset .........................................19



Price et al.                                                    [Page 2]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


      5.2.8. Inferred_ip_checksum ....................................19
      5.3. Control field encoding methods ............................20
      5.3.1. Discriminator ...........................................20
      5.3.2. Control field ...........................................21
      5.3.3. From list ...............................................22
      5.3.4. CRC .....................................................22
      5.4. Packet format encoding methods ............................22
      5.4.1. Single packet format ....................................22
      5.4.2. Multiple packet formats .................................23
      5.4.3. List of known length ....................................25
      5.5. Miscellaneous encoding methods ............................28
      5.5.1. Uncompressible ..........................................28

   6. Bit level worked example .......................................29

      6.1. Example Packet Format .....................................29
      6.2. Initial Encoding ..........................................29
      6.3. Basic Compression .........................................31
      6.4. Inter-packet compression ..................................31
      6.5. Variable Length Discriminators ............................33
      6.6. Default encoding ..........................................35

   7. Security considerations ........................................36


   8. Acknowledgements ...............................................36


   9. Authors' addresses .............................................36


   10. References ....................................................36


   Appendix A. Supporting Prolog Code ................................38



















Price et al.                                                    [Page 3]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003




1. Introduction

   ROHC FN is a simple notation designed to help with the creation of
   new ROHC [RFC-3095] header compression profiles.  ROHC-FN offers a
   library of "encoding methods" that are often used in ROHC profiles,
   so new profiles can be defined without needing to redefine this
   library from scratch.

   Informally, an encoding method is just a function that converts
   uncompressed data into compressed data.  The simplest encoding
   methods only have one input and output: the input is an uncompressed
   field and the output is the compressed version of the field.  More
   complex encoding methods can compress multiple fields at the same
   time, e.g. "list" encoding from [RFC-3095], which is designed to
   compress an ordered list of fields.

   The features required for defining ROHC-FN are offered by the
   programming language Prolog.  As such ROHC-FN is defined both in
   English and also in Prolog.  The English definition is more
   digestible but less formal.  The Prolog definition is less digestible
   but totally precise in that it allows any profile defined using ROHC-
   FN to be compiled and executed, allowing  the profile's behaviour to
   be observed on real data.  Hence where any ambiguity appears in the
   English definition, the Prolog definition will clarify the issue.
   There should however, be no conflicts between the English and Prolog
   definitions.  Any such conflicts should be reported to the authors.

   Note that this draft contains a standalone definition of ROHC-FN
   (i.e. there is no need to understand Prolog in order to understand
   ROHC-FN).


2. Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC-2119 [RFC-2119].

   Control field

     Control fields are transmitted from a ROHC compressor to a ROHC
     decompressor, but are not part of the uncompressed protocol header
     itself.  An example is a checksum field over the header to ensure
     robustness against bit errors and dropped packets.

   Encoding method

     Encoding methods are functions that can be applied to compress
     fields in a protocol header.



Price et al.                                                    [Page 4]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



   Field

     ROHC-FN divides the protocol to be compressed into a set of
     contiguous bit patterns known as fields.

   Library of encoding methods

     The library of encoding methods contains a number of commonly used
     encoding methods for compressing header fields.

   Profile

     A ROHC [RFC-3095] profile is a description of how to compress a
     certain protocol stack over a certain type of link.  Each profile
     includes packet formats to compress the headers and a state machine
     to control the actions of each endpoint.

3. Overview of ROHC-FN

   This section gives an overview of ROHC-FN and explains how it can be
   used to compress header fields as part of a ROHC profile.

3.1. Scope of ROHC-FN

   The following section describes the scope of ROHC-FN, and explains
   how it relates to the overall ROHC framework and also how it relates
   to specific ROHC profiles.

   The ROHC framework is common to all profiles: it defines the general
   principles for doing ROHC compression.  It defines the profile
   concept, which makes ROHC a general platform for compression schemes.
   It sets link layer requirements, and in particular negotiation
   requirements for all ROHC profiles.  It defines a set of common
   functions such as Context Identifiers (CIDs) and padding and
   segmentation (useful if the link layer can only handle a limited
   range of packet sizes).  It also defines common packet formats (IR,
   IR-DYN, Feedback, Short-CID expander, etc.), and it defines a
   generic, profile independent, handling of feedback.

   A ROHC profile is a description of how to compress a certain protocol
   stack over a certain type of link.  For example, ROHC profiles are
   available for RTP/UDP/IP and many other protocol stacks.

   Each ROHC profile can be further subdivided into the following two
   components:

   a)  Packet formats for compressing and decompressing headers
   b)  State machine





Price et al.                                                    [Page 5]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   The job of the packet formats is to define how to compress and
   decompress headers.  The packet formats must define the compressed
   version of each uncompressed header (and vice versa).

   The packet formats will typically compress headers relative to a
   "context" of field values from previous headers in a flow.  This
   improves the overall compression ratio, due to taking into account
   redundancies between successive headers.

   The job of the state machine is to ensure that the profile is robust
   against bit errors and dropped packets.  The state machine manages
   the context, providing feedback and other mechanisms to ensure that
   the compressor and decompressor contexts are kept in sync.

   ROHC-FN is designed to help provide the packet formats for use in new
   ROHC profiles.  It offers a library of encoding methods for
   compressing fields, and a mechanism for combining these encoding
   methods to create new packet formats tailored to a specific protocol
   stack.  Note however that the state machine for the new profiles is
   beyond the scope of ROHC-FN, and must be provided separately.

3.2. Example using IPv4

   Rather than immediately diving in with a formal definition of ROHC-
   FN, the following section will give an overview of how the notation
   is used by means of an example.  The example will develop the formal
   notation for an encoding method capable of compressing a single,
   well-known header: the IPv4 header.

   The first step is to specify the overall encoding method for the IPv4
   header.  In this case we will use the single_packet_format encoding
   method.  This encoding method compresses a header by dividing it into
   fields, compressing each field in turn, and then sending a single
   packet containing the compressed version of each field.  We define
   this by writing the following in ROHC-FN:

   ipv4_header           ::=   single_packet_format,

   {

   The symbol "::=" means "is encoded as", so the above expression
   defines that the IPv4 header is encoded by sending a single packet
   format (containing the compressed version of each field in the IPv4
   header).

   Note the opening curly brace, which indicates that subsequent
   definitions are local to the ipv4_header.  This scoping mechanism
   helps to clarify which fields belong to which headers: it becomes
   especially useful when compressing complex protocol stacks with
   several headers and fields, often sharing the same names.




Price et al.                                                    [Page 6]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   The next step is to specify the fields contained in the uncompressed
   IPv4 header, which is accomplished in ROHC-FN as follows:

     uncompressed_data   ::=   version,        %  4 bits
                               header_length,  %  4 bits
                               tos,            %  6 bits
                               ecn,            %  2 bits
                               length,         % 16 bits
                               id,             % 16 bits
                               reserved,       %  1 bits
                               dont_frag,      %  1 bits
                               more_fragments, %  1 bits
                               offset,         % 13 bits
                               ttl,            %  8 bits
                               protocol,       %  8 bits
                               checksum,       % 16 bits
                               src_addr,       % 32 bits
                               dest_addr,      % 32 bits

   After this, we specify the fields contained in the compressed header.
   Exactly what appears in this list of fields depends on the encoding
   methods used to encode the uncompressed fields - we may be able to
   compress certain fields down to 0 bits, in which case they do not
   need to be sent in the compressed header at all as explained below.
   Note that the order of the fields in the compressed header is
   independent of the order of the fields in the uncompressed header.

     compressed_data     ::=   src_addr,       % 32 bits
                               dest_addr,      % 32 bits
                               length,         % 16 bits
                               id,             % 16 bits
                               ttl,            %  8 bits
                               protocol,       %  8 bits
                               tos,            %  6 bits
                               ecn,            %  2 bits
                               dont_frag,      %  1 bits

   The next step is to specify the encoding methods for each field in
   the IPv4 header.  These will be taken from well-known encoding
   methods in the ROHC-FN library.  Note that the intention here is to
   illustrate the use of the notation, rather than to describe the
   optimum method of compressing IPv4 headers, therefore for the purpose
   of the example we will use just three encoding methods from the ROHC-
   FN library.

   The "value" encoding method can compress any field whose length and
   value is fixed.  No compressed bits need to be sent because the field
   can be reconstructed using its known size and value.  The "value"
   encoding method is used to compress five fields in the IPv4 header as
   described below:




Price et al.                                                    [Page 7]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     version             ::=   value(4, 4),
     header_length       ::=   value(4, 5),
     reserved            ::=   value(1, 0),
     more_fragments      ::=   value(1, 0),
     offset              ::=   value(13, 0),

   Note that the first parameter indicates the length of the
   uncompressed field in bits, and the second parameter gives its
   integer value.

   The "irregular" encoding method can be used to encode any field whose
   length is fixed.  It is a very general encoding method that can be
   used for fields to which no other encoding method applies.  All of
   the bits in the uncompressed field need to be sent; hence this
   encoding does not give any compression.

     tos                 ::=   irregular(6),
     ecn                 ::=   irregular(2),
     length              ::=   irregular(16),
     id                  ::=   irregular(16),
     dont_frag           ::=   irregular(1),
     ttl                 ::=   irregular(8),
     protocol            ::=   irregular(8),
     src_addr            ::=   irregular(32),
     dest_addr           ::=   irregular(32),

   The final encoding method is at the opposite extreme of generality:
   "inferred_ip_checksum" is a specific encoding method for calculating
   the IP checksum from the rest of the header values.  Like the "value"
   encoding method, no compressed bits need to be sent, since the field
   value can be entirely reconstructed using the values in the other
   fields of the IP header.

     checksum            ::=   inferred_ip_checksum
   }

   We have now defined the format of the compressed IPv4 header, and
   provided enough information to allow an implementation to construct
   the compressed header from an uncompressed header and vice versa.
   This completes the example.

3.3. Adding robustness

   ROHC profiles are designed to be "robust" against packet loss and
   residual bit errors on the link over which header compression takes
   place.  A well-designed profile can cope with these errors without
   losing additional packets or introducing additional bit errors in the
   decompressed headers.

   ROHC-FN offers two techniques to help ensure that a ROHC profile is
   robust.  Firstly, the encoding methods in the ROHC-FN library are



Price et al.                                                    [Page 8]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   designed to tolerate a certain number of dropped or misordered
   packets between the compressor and decompressor.  For example, Least-
   Significant Bit (LSB) encoding can robustly compress fields that
   change by a small value between successive headers.

   Secondly, the "CRC" encoding method can be used to provide a CRC over
   the original uncompressed header, to detect faulty decompressed
   headers and prevent them from mistakenly being used to update the
   context.  This situation is illustrated in Figure 1:

                                        CRC failure
    +--------------+ +--------------+ ================ +--------------+
   -| Valid header |-| Valid header |-|Invalid header|-| Valid header |-
    +--------------+ +--------------+ ================ +--------------+
          |  |             |  |                              |  |
   >------+  +------>------+  +--------------->--------------+  +------>
                 context                   context

         Figure 1: Preventing accidental corruption of the context

4. Normative definition of ROHC-FN

   This section gives the normative definition of ROHC-FN, including its
   syntax and any data structures that it requires.

4.1. ROHC-FN syntax

   Defining how to compress a field or header using ROHC-FN is extremely
   simple.  All that needs to be provided is the following:

   a)  A name for the field or header to be compressed.
   b)  An encoding method, together with any parameters it needs,
   including subfield parameters.

   For example:

     field_name ::= encoding_method(param1, param2, ...),
     {
        sub_field_1  ::= foo1,
        sub_field_2  ::= foo2(foo2_param),
        etc.
     }

   This describes how to map the field "field_name" from an uncompressed
   value, to a compressed value, by encoding it using "encoding_method",
   with the specified parameters and subfields.

   Note that the use of { and } provide a scoping mechanism, in that
   "sub_field_1" and "sub_field_2" are actually contained within
   "field_name". It is also legal syntax to qualify the names of the




Price et al.                                                    [Page 9]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   fields explicitly, using a dot. Thus, without using the {, } scoping
   mechanism, the previous example would look like this:

     field_name              ::= encoding_method(param1, param2, ...),
     field_name.sub_field_1  ::= foo1,
     field_name.sub_field_2  ::= foo2(foo2_param),
     etc.




   All formal notation is represented using this simple syntax.  Because
   the construct can be nested, complex relationships can be notated.

4.2. Comments

   Comments do not affect the formal meaning of what is notated, but can
   be used to improve readability.  The use of them is entirely
   optional.

   It should be noted that profiles will be read, by many readers, in
   terms of their intuitive English meaning.  Such readers will not
   necessarily differentiate between the formal and commentary parts of
   a profile.  It is essential therefore that any comments written are
   correct.  They should not be considered of lesser importance than the
   rest of the notation in a profile, and should be strictly consistent
   with it.

   If the profile author does wish to insert free English text into the
   profile, in order to explain why something has been done a particular
   way, to clarify the intended meaning of the notation, or to elaborate
   on some point, they can do so by use of one of the two commenting
   styles described below.

4.2.1. End Of Line Comments


   The end of line comment style makes use of the % comment character.
   Any text between the % character and the end of the line has no
   formal meaning.  For example:

     %-----------------------------------------------------------------
     %    IR-REPLICATE packet formats
     %-----------------------------------------------------------------

     % The following fields are included in all of the IR-REPLICATE
     % packet formats:
     %

     replicate_common    ::=   discriminator,    %    8 bits
                               tcp.seq_number,   %   32 bits



Price et al.                                                   [Page 10]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


                               tcp.flags.ecn,    %    2 bits

4.2.2. Block Comments

   The block comment style makes use of the /* and */ delimiters.  Any
   text between the /* and the */ has no formal meaning.  For example:

     /******************************************************************
      *   IR-REPLICATE packet formats
      *****************************************************************/

     /* The following fields are included in all of the IR-REPLICATE
      * packet formats:
      */

                                                                                           replicate_common    ::=   discriminator,    /*   8 bits */
                               tcp.seq_number,   /*  32 bits */
                               tcp.flags.ecn,    /*   2 bits */

   The block comment style allows comments to be nested (i.e. comments
   inside comments are allowed).  For example:

     /* Old version temporarily kept as a comment; delete when finalised
      *
      *replicate_common    ::=   discriminator,           /*   8 bits */
      *                          tcp.scaled_seq_number,   /*  22 bits */
      *                          tcp.seq_number_residue,  /*  10 bits */
      *                          tcp.flags.ecn,           /*   2 bits */
      */


   Readers familiar with the C, C++ or Java programming languages,
   should take careful note of this fact!

4.3. Implementation structures

   The following section gives some information about the data that must
   be stored by an implementation of a ROHC profile.  ROHC-FN assumes
   that the data is available as a single structure, indexed by the name
   of the relevant field.  Note, however, that provided the relevant
   data is available, the exact way in which the data structure is
   stored is up to the implementation itself.

   ROHC-FN assumes that for each field to be compressed, the following
   eight attributes are available:

     uncomp, uncomp_start, uncomp_length, comp, comp_start, comp_length,
     context, updated_context






Price et al.                                                   [Page 11]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   The notation to access any of the attributes for a particular field,
   is the name of the attribute, followed by the field name in brackets.
   For example;

     uncomp(tcp_ip.options.list_length)

   Gives the uncompressed value of the tcp_ip.options.list_length field.
   Each of the attributes is explained in more detail below.

4.3.1. The uncomp attribute

   The uncomp attribute contains the uncompressed value of the field.
   This can either be the value of a field from the uncompressed header,
   or the uncompressed value of a control field, but all fields have an
   uncomp value attribute.

4.3.2. The uncomp_start attribute

   The uncomp_start attribute contains the position in the header that
   the uncompressed field starts at, specified in bits.  Control fields
   do not make use of this attribute.

4.3.3. The uncomp_length attribute

   The uncomp_length attribute contains the length of the uncompressed
   field, specified in bits.  All fields have an uncomp_length
   attribute.

4.3.4. The comp attribute

   The comp attribute contains the compressed value of the field, i.e.
   the value of the field as it appears in the compressed header.  Note
   that this will not be used for fields which are not encoded; some
   don't appear in the compressed header at all.

4.3.5. The comp_start attribute

   The comp_start attribute contains the position in the compressed
   header that the field starts at, specified in bits.  All attributes
   which appear in the compressed header make use of this attribute.

4.3.6. The comp_length attribute

   The comp_length attribute contains the length of the compressed
   field, specified in bits.  All attributes which appear in the
   compressed header make use of this attribute.

4.3.7. The context attribute

   The purpose of the context attribute is to allow inter-packet
   compression.  An analogy can be found in MPEG video compression.



Price et al.                                                   [Page 12]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   Reasonable video compression can be achieved simply by treating each
   frame as a still image and compressing it e.g. using JPEG.  However
   MPEG compression takes advantage of the fact that successive frames
   of video can be compressed more efficiently by taking into account
   the similarities between them.  Similarly, the context attribute
   contains information about the previous value of the field.  Note
   that there will be no context for the first packet in a stream.

   The context attribute is actually key to efficient compression, since
   the behavior of one header is very often related to the behavior of
   previous headers in a flow.  For example, the RTP Sequence Number
   field increases by 1 for each consecutive header in an RTP stream.

   ROHC profiles take into account the dependency between successive
   headers by storing and referencing the context attribute.  However,
   whilst it is possible to do this explicitly, most of the time the
   context is referenced implicitly by the encoding methods.

   An implementation of ROHC-FN should allow encoding methods to read
   values from the context, and should be able to update the context
   with the new field values from the current header (or some other
   value if that is appropriate).

   All fields make use of the context attribute.

4.3.8. The updated_context attribute

   The updated_context attribute contains the value that the context
   attribute will take for the next header.  The state machine for a
   ROHC profile defines a specific point at which the context is
   updated: at this point the updated_context attribute should be copied
   into the context attribute.

   All fields make use of the updated_context attribute.

5. Encoding methods

   The ROHC [RFC-3095] standard contains a number of different
   techniques for compressing header fields (LSB encoding, value
   encoding, list-based compression etc.).  Each of these techniques can
   be added to the ROHC-FN library so that they can be reused when
   creating new ROHC profiles.

   The following encoding methods are all defined in English; a formal
   Prolog definition for each is given in the next section.  The sub-
   section numbers are the same as those in the next section to make it
   straightforward to refer from English to Prolog and vice versa,
   without cluttering up the English definitions with Prolog.

5.1. Basic encoding methods




Price et al.                                                   [Page 13]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   This section defines the simplest set of encoding methods.  All these
   encoding methods are self-contained in that they do not need to refer
   to other fields.

5.1.1. Value

   The value encoding method is used to encode header fields which
   always have a fixed size and value.  E.g. the IPv6 header version
   number is a four bit field that always has the value 6:

     version             ::=   value(4, 6)

   Since the value is fixed, it is omitted from the compressed header.
   As with all omitted fields the author of a profile has the option of
   notating a value encoded field as a zero bit field in the compressed
   header field order list, if they so wish.

5.1.2. Irregular

   The "irregular" encoding method leaves the field untouched.  The
   field in the compressed packet will have an identical bit pattern to
   the original field in the uncompressed packet.  E.g.

     age_in_years        ::=   irregular(16)

   Note that since the field divisions specified in the profile are
   completely arbitrary, there is no reason not to take what is
   specified as a single field in a header specification and break it
   down into smaller fields.

   Using this technique, fields which are only irregular in part can be
   better compressed.  E.g. if the above field was the age in years of
   the human who originated the packet, and if we knew from the protocol
   definition that the field would never have a value greater than 123,
   we would know that the most significant bits would always be zero, so
   we might encode it as follows:

     age_in_years_part_1 ::=   value(9,0),
     age_in_years_part_2 ::=   irregular(7)

5.1.3. Static

   The "static" encoding method compresses a field whose length and
   value is the same as for the previous header in the flow.  E.g.

     src_port            ::=   static

   Since the field value is the same as the previous field value, the
   entire field can be reconstructed from the context, so it is
   compressed to zero bits and does not appear in the compressed header.




Price et al.                                                   [Page 14]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


5.1.4. LSB

   The "lsb" encoding method compresses a field whose value differs by a
   small amount from the value stored in the context.  E.g.

       msn               ::=   lsb(2,0),

   The "lsb(k, p)" encoding method can compress a field f whose value
   lies between (context(f) - p) and (context(f) - p + 2^k - 1)
   inclusive.  In particular, if p = 0 then the field value can only
   stay the same or increase relative to the previous header in the
   flow.  If p = -1 then it can only increase, whereas if p = 2^k then
   it can only decrease.

   The compressed field takes up the specified number of bits in the
   compressed header.  See the ROHC [RFC-3095] standard for a full
   definition of LSB encoding.

5.1.5. Index

   The "index" encoding method compresses a field whose value is one of
   a list of possible values.  It takes two parameters.  The first is
   the length of the uncompressed field, in bits.  The second is the
   list of possible values that the field can take.  E.g.

     id_flags            ::=   index(8, [3, 5, 22])

   The compressed packet contains the index of the value to be
   compressed.  The leftmost item in the list has an index of 0, the
   next item an index of 1 and so on.

   The compressed field has a length of log2 of the length of the list,
   rounded up to the nearest integer. So the above example would have a
   compressed length of 2 bits.


5.2. Relative Field Encoding Methods

   The encoding methods in this section are all able to encode a field
   whose value can be inferred from the value of another field or
   fields.

   Fields can be referred to outside of the scope they are defined in,
   by using the '.' scoping notation.  So for example, to refer to
   field_1 from outside the scope of the test_single_format header
   (where it is defined), use 'test_single_format.field_1'.  The same
   scoping mechanism can be used for subfields within fields.


5.2.1. Same As




Price et al.                                                   [Page 15]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   The "same_as" encoding method is used for fields that are always
   identical to another field.  Whilst having two identical fields in a
   header is not normal, "same_as" is also useful for encoding fields
   that are needed by encoding techniques that need to refer to other
   fields.  For example:

     count               ::=   inferred_offset(4),
     {
       base_field        ::=   same_as(test_offset.id),
       offset            ::=   value(4,3)
     }

   Since the same_as encoding method gets the entire value of the field
   from another field, it takes up zero bits in the compressed header.

5.2.2. Group

   The "group" encoding method is used to group two or more non-
   contiguous uncompressed fields together, so that they can be treated
   as a single field for compression.  This encoding method takes a
   single argument, which is the list of fields to be joined together.
   This argument is specified as a subfield, field_list. For example:

     tcp.ecn_and_reserved     ::=   group,
     {
       field_list             ::=   ip.ecn,
                                    tcp.flags.ecn,
                                    tcp.reserved
     }

   The group encoding method does not define any bits in the compressed
   header directly, but, like same_as (above), is intended to be used in
   conjunction with the control_field encoding method (below). For
   example:

     tcp.ecn_and_reserved         ::= control_field,
     {
       base_field                 ::= group,
       {
         field_list               ::= ip.ecn,
                                      tcp.flags.ecn,
                                      tcp.reserved
       },

       compressed_method          ::= value(8, 0)
     }

5.2.3. Expression






Price et al.                                                   [Page 16]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   This encoding method is used to when the uncompressed value of the
   field is defined by a mathematical expression.  The expression can be
   made up of any of the following components:

   Integers              Integers can be expressed as decimal values,
                         binary values (prefixed  by 0b), or  hex                                                                  values
                         (prefixed  by  0x).    Negative  integers   are
                         prefixed by a "-" sign.

   Operators             The operators +, -, *, / and ^ are available,
                         along with ( and ) for grouping.  Note that
                         k / v is undefined if k is not an integer
                         multiple of v (i.e. if it does not evaluate to
                         an integer).
                         The precedence for each of the operators, along
                         with parentheses is given below (higher
                         precedence first):
                         (, )
                         ^
                         *, /
                         +, -

   floor (k, v)          Returns k / v rounded down to the nearest
                         integer (undefined for v == 0).

   mod (k, v)            Returns k - v * floor(k, v).

   log2 (v)              Returns the smallest integer k where v <= 2^k,
                         i.e. it returns the smallest number of bits in
                         which value v can be stored.


   The expression may refer to any of the attributes in the data
   structure stored for each field (see above), but the following
   attributes are most likely to be useful:

   uncomp        - the uncompressed value of the field,
   uncomp_length - the length of the uncompressed field in bits,
   comp          - the compressed value of the field,
   comp_length   - the length of the compressed field in bits,

   To access any of the attributes for a particular field, write the
   name of the attribute, followed by the field name in brackets.  E.g.

     uncomp(tcp_ip.options.list_length)

   This will get the uncompressed value of the list length of the tcp
   options list.  Note that if any of the attributes used in the
   expression are undefined, the value of the expression is undefined.
   Here is a complete example of expression encoding, which employs the
   above attribute:



Price et al.                                                   [Page 17]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



     data_offset     ::= expression((uncomp(tcp_ip.options.list_length)
                                     + 160) / 32)

   Since the value of an expression encoded field is constructed
   entirely from the expression, it takes up zero bits in the compressed
   header.

       Constant

   "Constant" encoding works in the same manner as expression, but the
   expression must yield a value that is constant for all headers.


5.2.5. Derived value

   The "derived_value" encoding method is similar to the value encoding
   method, except that the length and value do not have to be constant,
   since they are specified as subfields, rather than as in line
   parameters.  For example:

     tcp.seq_number  ::=  derived_value,
     {5.2.4.
       field_length  ::=  constant(8),
       field_value   ::=  expression(uncomp(tcp.seq_number.residue) +
                                     (uncomp(tcp.seq_number.scaled) *
                                      uncomp(tcp.payload_size)))
     }

   If constant encoding is used for both fields, the encoding method is
   identical to value encoding. For example,

     field_1         ::= value(4, 11)

   has identical meaning to:


     field_1         ::=  derived_value,
     {
       field_length  ::=  constant(4),
       field_value   ::=  constant(11)
     }


   The number of bits that derived_value encoding takes up in the
   compressed header depends on the encoding methods used for the length
   and value. The above examples would both take up zero bits in the
   header since the constant and expression encoding methods both take
   up zero bits in the compressed header. If both length and value
   encoding methods take up bits in the compressed header, the length
   encoding is done first, followed by the value encoding.



Price et al.                                                   [Page 18]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



5.2.6. Inferred_size

   The "inferred_size" encoding method infers the value of a field from
   the total amount of remaining data in the header.

   The first parameter specifies the length of the uncompressed field in
   bits, and the second parameter specifies an offset that will be
   subtracted from the total data length when deriving the value of the
   field.  E.g.

     size_field          ::=   inferred_size(4, -8)

   Since the value of the field is only dependent on the size of the
   data, which is known, the encoded field is zero bits long.

5.2.7. Inferred_offset

   The "inferred_offset" encoding method compresses a field that takes a
   known offset relative to a certain base value.  In typical usage the
   base value will be specified as the value of another field, although
   any value can be specified.

   The method has three parameters.  The first parameter, length,
   defines the length of the uncompressed field in bits.  The length
   parameter is specified in parentheses in the normal way. The second
   parameter specifies the base value, along with how to encode that
   value in the compressed header.  The third parameter specifies the
   offset from the base value, along with the encoding method for that.
   Because these two parameters allow for the specification of encoding
   methods, they are specified using subfields, rather than as regular
   parameters.  E.g.

     id              ::=   inferred_offset(16),
     {
       base_field    ::=   same_as(msn),
       offset        ::=   static
     }

   This says that the id field is 16 bits long in the uncompressed
   header, and has a static offset from the value of the MSN.

   The exact number of bits it takes to encode an inferred offset field
   depends on the encoding methods used for the base_field and offset.
   The above example takes up zero bits in the compressed header, since
   both the same_as and static encoding methods compress down to zero
   bits.

5.2.8. Inferred_ip_checksum





Price et al.                                                   [Page 19]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   The "inferred_ip_checksum" encoding method is a very specific
   encoding method used to compress the IP checksum field.  It should
   only be used for that purpose:

     checksum        ::=   inferred_ip_checksum

   Since the checksum can be constructed solely from the other fields in
   the header, zero bytes are sent for this encoding.

5.3. Control field encoding methods

   This section provides a selection of encoding method for handling
   control fields, i.e. fields which appear in the compressed header to
   control the compression in some way and do not appear in the
   uncompressed header at all.

5.3.1. Discriminator

   The discriminator encoding method writes a literal bit string into
   the compressed header.  It is intended to be used in conjunction with
   the multiple_packet_formats encoding method, which allows for more
   than one method of compression for a given header.  The discriminator
   encoding method allows a unique bit pattern to be specified, in
   binary, which identifies the particular compression format
   ("co_format") that has been used.  The syntax for the
   literal_discriminator encoding method is unusual - for readability,
   the discriminator is simply specified in between two single quote
   marks. For example

     discriminator     ::=   '011'

   The discriminator encoding method has an optional subfield, format,
   which provides extra discriminator bits, which are not given in
   literal form, but have an encoding method specified in the usual way.
   It is possible to describe the entire discriminator in this way, in
   which case the literal part of the discriminator can be empty. For
   example:

     discriminator        ::= '',
     {
       format ::= same_as(ip_id_zero)
     }

   The format field is designed to be used to segregate the different
   packet formats (co_formats) into broad categories, for example, those
   which have a permanently zero IP ID and those which don't. The
   compressor uses the same set of packet formats for a particular flow,
   so the choice of formats must be stored in the context at the
   compressor and decompressor. The compressor will only use packet
   formats which belong to the set of formats it has chosen for the
   flow, as specified by the format field of the discriminator. Note



Price et al.                                                   [Page 20]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   that this is what this field was designed to cope with, but its use
   in not restricted to this.

   When the compressor sends the very first packet in the flow, it needs
   to tell the decompressor which set of packet formats it wants to use
   to compress all of the subsequent packets in the flow. If the
   optional format field is not being used then there is only one set of
   packet formats, so this is not an issue. If the optional format field
   is being used then the first packet in the flow needs to indicate the
   number of bits that the format field will take up. This is done using
   the num_formats field.

   A packet which has a "num_formats" field allows the compressor to
   choose a new set of packet formats, and then to send its choice
   explicitly to the decompressor. The "num_formats" parameter specifies
   how many distinct sets of packet formats are available. The
   compressor can work out from this how many bits it needs to send
   (log2 of the number formats, rounded up). For example:

     discriminator                ::=    '1001',
     {
       num_formats                ::=    constant(2)
     }

   In this case there are just two sets of formats available, so the
   compressor sends 1 bit to the decompressor to indicate which of the
   two sets it wants to use.

   The literal part of the discriminator is added into the compressed
   header as is, so it takes up however many bits are in the given
   literal bit pattern. The optional format field follows it and takes
   up however many bits the specified encoding method takes up,
   similarly with the num_formats field.

5.3.2. Control field

   This encoding method is used for fields that need to be sent in the
   compressed header, but which don't appear in the uncompressed header
   at all.  It takes two parameters, the base field, which is the field
   it is based on and the compressed_method, which specifies the method
   to use to encode the given field.  E.g.

     order_data           ::=   control_field,

     { base_field         ::=   same_as(test_list.list_of_fields.order),

       compressed_method  ::=   irregular(1)}.

   The exact encoding of a control field, and the number of bits it
   takes up are determined by the encoding method used by
   compressed_method.



Price et al.                                                   [Page 21]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



5.3.3. From list

   The "from_list" encoding method is used to extract the presence and
   order flags from a list of items encoded with the
   list_of_known_length encoding method (see below). For example:

       order_flag           ::=   from_list(test_list.order_flag),
       presence_flag        ::=   from_list(test_list.presence_flag)

   For full details on the meaning of each of these flags, see list
   encoding below.

5.3.4. CRC

   The "crc" encoding method provides a CRC calculated across the
   original uncompressed header.  The size of the CRC can be altered
   depending on the importance of the data in a given compressed packet,
   and also on the characteristics of the link over which the protocol
   is to be transmitted.  A sufficiently long CRC should be provided to
   ensure the probability that an unexpected error will be missed is
   negligible.  For example:

     crc_field   ::=   crc(3)   %   3 bits

   The currently valid CRC polynomials are those defined in [RFC-3095],
   Section 5.9.1 and 5.9.2.

   Editors Note: Need to describe CRC algorithm here, or reference it's
   definition.

5.4. Packet format encoding methods

   This section details encoding methods used to encode whole headers.
   All the encoding methods described above are designed to encode
   single fields within headers; the packet format encoding methods
   allow the individual fields to be built up into packets.  The
   encoding methods described in this section are intended for that
   purpose, to contain a list of fields and corresponding encoding
   methods, by which the whole packet can be encoded.


5.4.1. Single packet format

   The "single_packet_format" encoding method specifies a single fixed
   encoding for a given kind of protocol header.  This is the simplest
   packet encoding method.  For example:







Price et al.                                                   [Page 22]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     test_single_format    ::=   single_packet_format,
     {
       uncompressed_data   ::=   field_1,   %   4 bits
                                 field 2,   %   4 bits

       compressed_data     ::=   field_2,   %   0 bits
                                 field 1,   %   4 bits

       field_1             ::=   irregular(4),
       field 2             ::=   value(4, 9)
     }

   This specifies the order of the fields in the uncompressed header,
   followed by the order of the fields in the compressed header,
   followed by a list of encoding techniques for each field.

   The compressed data will appear in the order specified by the field
   order list "compressed_data", with each individual field being
   encoded in the manner given for that field.  Consequently the length
   of the compressed data will be the total of the lengths of all the
   individual fields.  The above example would encode field_2 first
   (zero bits long), followed by field_1 (four bits long), giving a
   total length of four bits.

   Note that the order of the fields specified in compressed_data does
   not have to match the order they appear in the uncompressed_data.
   Fields of zero bits length may be omitted from the field order list,
   since their position in the list is not significant.  So, without
   changing the meaning, we could have written the above as:

     test_single_format    ::=   single_packet_format,
     {
       uncompressed_data   ::=   field_1,   %   4 bits
                                 field 2,   %   4 bits

       compressed_data     ::=   field 1,   %   4 bits

       field_1             ::=   irregular(4),
       field 2             ::=   value(4, 9)
     }


5.4.2. Multiple packet formats

   This encoding method allows multiple encodings for a given header.
   This allows different compression techniques to be used at different
   times, depending on what is the most efficient way of compressing a
   particular header.

   For example a field may have a fixed value most of the time, but very
   occasionally the fixed value may change.  Using single_packet_format,



Price et al.                                                   [Page 23]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   this field would have to be encoded as irregular, even though the
   value only changes rarely.  Using multiple_packet_formats however we
   can provide two alternative encodings, one for when the value remains
   fixed and another for when the value changes.

   This encoding method is notated in a similar way to the
   single_packet_format encoding method; there are however a number of
   differences.  Firstly, it is necessary to specify the number of
   alternative packet formats that are defined, which is done via the
   co_format_count field.  This is a control field in that it doesn't
   appear in the uncompressed header.  Typically it will be encoded as a
   constant and so won't take up any bits in the compressed header
   either, for example:

     co_format_count     ::=   constant(2),

   Secondly the field names are different.  "uncompressed_data", becomes
   "uncompressed_format", and "compressed_data" is split into several
   fields, since whilst there is still only a single definition of the
   uncompressed packet format, there are obviously several alternative
   compressed packet formats.  These are defined via fields named
   co_format_0, co_format_1, co_format_2 etc., each of which has a
   separate set of field encodings associated with it.  In particular
   each co_format must include a discriminator which uniquely identifies
   that particular co_format. (See discriminator encoding above).

   The third difference is that the field encodings appear as subfields
   of each compressed packet format.  This is necessary to make it
   explicit which encoding methods are to be used for which compressed
   packet format, for example:

     co_format_0         ::=   discriminator,   %   1 bits
                               field_1,         %   0 bits
     {
       discriminator     ::=   '0',
       field_1           ::=   static
     }

   Note that the discriminator must always appear first in the field
   order list, since the decompressor needs to know what packet format
   it is dealing with before it can do anything else with the rest of
   the packet.

   Finally, default encoding methods can be specified for each field.
   The default encoding methods specify the encoding method to use for a
   field if a given co_format does not give an encoding method for that
   field.  This prevents the same encoding method from having to be
   spelt out for every co_format.  There is no need to specify a field
   order list for the default encoding methods, since the field order is
   specified individually for each co_format, so "..." can be given
   instead.  For example:



Price et al.                                                   [Page 24]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



     default_methods     ::=   ... ,
     {
       field_1           ::=   value(4,1),
       field_2           ::=   value(4,2)
     }

   Note that the normal case will be for all default encodings to be
   compressed to zero bits, in which case they are irrelevant to
   compressed field order.  However if any default encodings are used
   which compress to greater than zero bits, their position in the field
   order list must be specified explicitly for each co_format.

   Putting this altogether, here is a complete example of multiple
   packet formats:

     test_packet_formats   ::=   multiple_packet_formats,
     {
       co_format_count     ::=   constant(2),

       co_format_0         ::=   discriminator,
                                 field_1,
       {
         discriminator     ::=   '0',
         field_1           ::=   static
       },

       co_format_1         ::=   discriminator,
                                 field_1,
       {
         discriminator     ::=   '11',
         field_1           ::=   irregular(4)
       },

       uncompressed_format ::=   field_1,
                                 field_2,

       default_methods     ::=   ... ,
       {
         field_2           ::=   value(4,2)
       }
     }

5.4.3. List of known length

   The "list_of_known_length" encoding method compresses a list of items
   in the uncompressed header that are a known number of bits in length.
   Example applications for "list" encoding include TCP SACK blocks and
   TCP options.





Price et al.                                                   [Page 25]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   The set of list items that are present, and the order in which they
   occur can change between successive headers.  When they change this
   information must be sent to the decompressor, so that it knows which
   fields to reconstruct and in what order.  The list_of_known_length
   encoding method sends the order and presence information to the
   decompressor by creating two new control fields, "order" and
   "presence", along with two new flags, order_flag and presence_flag,
   which indicate whether order and/or presence data has changed.


   The encoding method requires two subfields to be supplied: the
   overall length of the list in bits (list_length), and the items that
   can occur in the list (list_items).  For example:

     list_length       ::=   constant(8),

     list_items        ::=   field_1,
                             field_2,
                             field_3,

   Each list item is a single field, which itself must be notated in the
   normal way, by supplying a suitable encoding method for it. For
   example:

       field_1           ::=   irregular(4),
       field_2           ::=   value(4, 2),
       field_3           ::=   inferred_size(4, 0)

   The list_of_known_length encoding method is unusual in that it also
   creates two fields: order_flag and presence_flag. These two fields
   are one bit long each and are used to indicate whether the order or
   presence of the fields in the list has changed. If set to one, then
   the order/presence has changed, if set to zero it has not changed.
   Note that order_flag and presence_flag are control fields; they do
   not appear in the uncompressed header directly. Their value is
   accessed by using the from_list encoding method (see above).

   If the order flag is set then order information is transmitted in the
   compressed packet, since it has changed. The order information starts
   with an 8 bit long length field, which specifies how many entries
   there are in the order list. This gives a maximum effective list
   length of 255 list items.

   The order list itself is a string of n entries, indicating the order
   of possible list items, where n is specified by the 8 bit length
   field at the start of the order information.  For a list which can
   contain N different types of list item, the length of each entry in
   the list will be the minimum number of bits required to represent the
   N different types of entry, i.e. log2 N, rounded up. For example if
   there were between 5 and 8 different types of entry inclusive, then
   each entry would take up 3 bits. The order list contains an entry for



Price et al.                                                   [Page 26]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   each of the list items in the order in which they will occur, if
   present. The order list is padded to a whole number of bytes, if it
   is not already a whole number of bytes in length.

   Note that if there is only one type of list item (e.g. as is the case
   with SACK blocks), then there is no need to represent the items in
   the order list, since they can be represented by zero bits; all that
   is needed is the 8 bit length field. In this case the length is fixed
   at one byte, so no padding is ever needed for lists with only one
   type of list item.

   If the presence_flag is set, then presence information is transmitted
   in the compressed packet, since it has changed. The presence
   information, is a list of bit flags, one per entry in the order list,
   which are set to "1" to indicate that the list item is present or "0"
   if not.  These flags occur in the order in which the entries appear
   in the order information, and are padded to a whole number of bytes.

   Note that if there is only one type of list item, as is the case with
   SACK blocks, then there is never a need to send the presence
   information, since the 8 bit length field at the start of the order
   information.

   The example below shows how to use list_of_known_length to encode a
   list of fields.  In this case, the list in the uncompressed header is
   always 8 bits long, so its length is "constant(8)".  The list
   contains three fields, which are encoded as shown below:


     list_of_fields      ::=   list_of_known_length,
     {
       list_length       ::=   constant(8),
       order_flag        ::=   from_list(list_eg.order_flag),
       presence_flag     ::=   from_list(list_eg.presence_flag),

       list_items        ::=   field_1,
                               field_2,
                               field_3,

       field_1           ::=   irregular(4),
       field_2           ::=   value(4, 2),
       field_3           ::=   inferred_size(4, 0)
     }


   A complete example of the use of the list_of_known_length encoding
   method in situ is given below. This example shows how the above list
   might be notated as being part of a bigger packet "list_eg":






Price et al.                                                   [Page 27]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   list_eg               ::= single_packet_format,
   {
     uncompressed_data   ::= list_of_fields,

     compressed_data     ::= order_flag,
                             presence_flag,
                             list_of_fields,

     order_flag          ::= control_field,
     {
       base_field        ::= same_as(list_eg.list_of_fields.order_flag),
       compressed_method ::= irregular(1)
     },

     presence_flag       ::= control_field,
     {
       base_field        ::= same_as
                                 (list_eg.list_of_fields.presence_flag),
       compressed_method ::= irregular(1)
     },

     list_of_fields      ::= list_of_known_length,
     {
       list_length       ::= constant(8),
       order_flag        ::= from_list(list_eg.order_flag),
       presence_flag     ::= from_list(list_eg.presence_flag),

       list_items        ::= field_1,
                             field_2,
                             field_3,

       field_1           ::= irregular(4),
       field_2           ::= value(4, 2),
       field_3           ::= inferred_size(4, 0)
     }
   }

5.5. Miscellaneous encoding methods

   This section introduces some miscellaneous encoding methods that can
   be used to compress fields in a protocol header.

5.5.1. Uncompressible

   The "uncompressible" encoding method is a special case of "irregular"
   encoding, where the length of the field is derived from the value of
   another field instead of being fixed.

   The encoding method takes four parameters. The first parameter gives
   the base value for calculating the length of the data, whilst the
   next three parameters specify a divisor, multiplier and offset which



Price et al.                                                   [Page 28]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   scale the variable so that it specifies the size of the
   uncompressible field in bits. For example:

     data  ::=   uncompressible(test_uncompressible.length, 2, 2, 4)

   An example of how this might be used within another packet is as
   follows:

     test_uncompressible ::= single_packet_format,
     {
       uncompressed_data ::=   length,
                               data,

       compressed_data   ::=   data,

       length            ::=   value(4, 1),

       data              ::=   uncompressible
                                 (test_uncompressible.length, 2, 2, 4)
     }

   The size of the uncompressible field in the compressed and
   uncompressed packets is (uncomp(FIELD_NAME) / DIVISOR) * MULTIPLIER +
   OFFSET.

6. Bit level worked example

   This section gives a worked example at the bit level, showing how a
   simple profile describes the compression of real data from an
   imaginary packet format.  The example used has been kept fairly
   simple, whilst still aiming to illustrate some of the intricacies
   that arise in use of the notation.

   All the formal notation in this section has been tested using the
   Prolog definitions of the encoding methods given in section Error!
   Reference source not found..

6.1. Example Packet Format

   Our imaginary header contains information about a packet of
   sandwiches.  It is just 8 bits long, consisting of two four bit
   fields:

     1. number of sandwiches
     2. number of extras (including cake, fruit, etc.)

   So for example 10010010 would indicate a packet with 5 sandwiches and
   two extras.

6.2. Initial Encoding




Price et al.                                                   [Page 29]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



   An initial definition based solely on the above information is:

     sandwich_header       ::=   single_packet_format,
     {
       uncompressed_data   ::=   num_sandwiches  : 4 bits
                                 num_extras      : 4 bits

       compressed_data     ::=   num_sandwiches  : 4 bits
                                 num_extras      : 4 bits

       num_sandwiches      ::=   irregular(4),
       num_extras          ::=   irregular(4)
     }

   This defines the packet nicely, but doesn't actually offer any
   compression.  If we use it to encode the above header, we get:

     Uncompressed header: 10010010
     Compressed header:   10010010

   This is because we have stated that both fields are irregular - i.e.
   we don't know anything about their behaviour.































Price et al.                                                   [Page 30]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



6.3. Basic Compression

   If packets of sandwiches were standardized to always contain two
   extras, regardless of the number of sandwiches, then the second field
   would always be 0010.  The second field however remains in the header
   for backward compatibility reasons.  We now have:


     sandwich_header       ::=   single_packet_format,
     {
       uncompressed_data   ::=   num_sandwiches  : 4 bits
                                 num_extras      : 4 bits

       compressed_data     ::=   num_sandwiches  : 4 bits
                                 num_extras      : 0 bits

       num_sandwiches      ::=   irregular(4),
       num_extras          ::=   value(4, 2)
     }

   Using this simple scheme, we have successfully encoded the fact that
   one of the fields has a permanently fixed value of two, and therefore
   contains no useful information.  Note that we could just as well have
   omitted "num_extras  : 0 bits" from the definition of the compressed
   data if we so wished.

   Using this new encoding on the above header, we get:

     Uncompressed header: 10010010
     Compressed header:   1001

   Which halves the amount of data we need to transmit.  However, this
   encoding fails to take any advantage of a stream of identical
   packets:

     Uncompressed header: 10010010
     Compressed header:   1001

     Uncompressed header: 10010010
     Compressed header:   1001

     Uncompressed header: 10010010
     Compressed header:   1001

6.4. Inter-packet compression

   The profile we have defined so far has not compressed the
   num_sandwiches field at all.  This field can take any value, and so
   there is no better single method of encoding this field than the
   irregular encoding already used.  However using the



Price et al.                                                   [Page 31]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   multiple_packet_formats encoding we can avoid having to stick to a
   single encoding method.

   What would be ideal is to avoid encoding the field on the occasions
   when its value is the same as the same field in the preceding header.
   This is exactly what static encoding does:

   sandwich_header       ::=   multiple_packet_formats,
   {
     uncompressed_format ::=   num_sandwiches,  % 4 bits
                               num_extras,      % 4 bits

     co_format_count     ::=   constant(2),

     co_format_0         ::=   discriminator,   % 1 bits
                               num_sandwiches,  % 0 bits
                               num_extras,      % 0 bits
     {
       discriminator     ::=   '0',
       num_sandwiches    ::=   static,
       num_extras        ::=   value(4, 2)
     },

     co_format_1         ::=   discriminator,   % 1 bits
                               num_sandwiches,  % 4 bits
                               num_extras,      % 0 bits
     {
       discriminator     ::=   '1',
       num_sandwiches    ::=   irregular(4),
       num_extras        ::=   value(4, 2)
     }
   }

   Note that we have had to add a discriminator field, in order that the
   decompressor knows which packet format we have used.  The format with
   a static number of sandwiches is now just 1 bit long.  However, the
   original packet format (with an irregular number of sandwiches) has
   also grown by one bit.  An important consideration when creating
   multiple packet formats is whether the extra format occurs frequently
   enough that the average compressed header length is shorter as a
   result.  For example if no two packets of sandwiches, with the same
   number of sandwiches in, were ever transmitted consecutively, then
   the static format packet would never be used and all we have just
   achieved is to lengthen our packet by one bit.  However it turns out
   that it is quite common to send out consecutive packets of sandwiches
   which have the same number of sandwiches in, so we achieve a
   significant saving by being able to encode the headers of such
   packets in a single bit.






Price et al.                                                   [Page 32]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   Using the above header, we now get:

     Uncompressed header: 10010010
     Compressed header:   11001

     Uncompressed header: 10010010
     Compressed header:   0 ; 11001

     Uncompressed header: 10010010
     Compressed header:   0 ; 11001

   The first header in the stream is compressed the same way as before,
   except that it now has the extra 1 bit discriminator at the start.
   When a second header arrives, with the same number of sandwiches as
   the first, it can now be compressed in two possible ways, either as a
   single bit (0), or in the same way as previously.

   Prolog execution of a profile will show all possible encodings of a
   packet as defined by a given profile, separated by semi-colons.
   Either of the above encodings for the packet could be produced by a
   valid implementation, although of course a good implementation would
   always pick the encoding which led to the best compression of the
   packet stream (which is not necessarily the smallest encoding for a
   particular packet).

6.5. Variable Length Discriminators

   Suppose we do some analysis on sandwich flows and discover that
   whilst it is usual for successive packets to have the same number of
   sandwiches in them, on the occasions when they don't, the packet is
   almost always a "diet" packet.  The number of sandwiches in a diet
   packet is always one.  To encode the flow more efficiently a packet
   format needs to be written to reflect this.

   This now gives a total of three packet formats, which means we need
   three discriminators to differentiate between them.  The obvious
   solution here is to increase the number of bits in the discriminator
   from 1 to two and for example use discriminators 00, 01, and 10.
   However we can do slightly better than this.

   Any uniquely identifiable discriminator will suffice, so we can use
   0, 10 and 11.  If the discriminator starts with 0, that's the whole
   thing.  If it starts with 1 the decompressor knows it has to check
   one more bit to determine the packet kind.

   It would be erroneous to use 0, 01 and 10 as discriminators since
   after reading an initial 0, the decompressor would have no way of
   knowing if the next bit was a second bit of discriminator, or the
   first bit of the next field in the packet stream.

   This gives us the following:



Price et al.                                                   [Page 33]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     sandwich_header       ::=   multiple_packet_formats,
     {
       uncompressed_format ::=   num_sandwiches,  % 4 bits
                                 num_extras,      % 4 bits

       co_format_count     ::=   constant(3),

       co_format_0         ::=   discriminator,   % 1 bits
                                 num_sandwiches,  % 0 bits
                                 num_extras,      % 0 bits
       {
         discriminator     ::=   '0',
         num_sandwiches    ::=   static,
         num_extras        ::=   value(4, 2)
       },

       co_format_1         ::=   discriminator,   % 2 bits
                                 num_sandwiches,  % 0 bits
                                 num_extras,      % 0 bits
       {
         discriminator     ::=   '10',
         num_sandwiches    ::=   value(4, 1),
         num_extras        ::=   value(4, 2)
       },

       co_format_2         ::=   discriminator,   % 2 bits
                                 num_sandwiches,  % 4 bits
                                 num_extras,      % 0 bits
       {
         discriminator     ::=   '11',
         num_sandwiches    ::=   irregular(4),
         num_extras        ::=   value(4, 2)
       }
     }

   Here is some example output:

     Uncompressed header: 10010010
     Compressed header:   111001

     Uncompressed header: 10010010
     Compressed header:   0 ; 111001

     Uncompressed header: 10010010
     Compressed header:   0 ; 111001

     Uncompressed header: 00010010
     Compressed header:   10 ; 110001






Price et al.                                                   [Page 34]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



6.6. Default encoding

   There is some redundancy in the notation used to define the profiles
   so far.  The num_extras field is the same in every packet format, and
   is redefined each time.  If the sandwich protocol was changed at some
   time in the future (e.g. suppose the number of extras is no longer
   fixed to 2), the num_extras field would have to be changed in every
   packet.

   This problem can be avoided by specifying a default encoding for this
   field, which also leads to a more concisely notated profile:

     sandwich_header_5     ::=   multiple_packet_formats,
     {
       uncompressed_format ::=   num_sandwiches,  % 4 bits
                                 num_extras,      % 4 bits

       co_format_count     ::=   constant(3),

       co_format_0         ::=   discriminator,   % 1 bit
                                 num_sandwiches,  % 0 bits
       {
         discriminator     ::=   '0',
         num_sandwiches    ::=   static
       },

       co_format_1         ::=   discriminator,   % 2 bits
                                 num_sandwiches,  % 0 bits
       {
         discriminator     ::=   '10',
         num_sandwiches    ::=   value(4, 1)
       },

       co_format_2         ::=   discriminator,   % 2 bits
                                 num_sandwiches,  % 4 bits
       {
         discriminator     ::=   '11',
         num_sandwiches    ::=   irregular(4)
       },

       default_methods     ::=   ... ,
       {
         num_extras        ::=   value(4,2)
       }
     }

   The above profile behaves in exactly the same way as the one notated
   previously.





Price et al.                                                   [Page 35]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



7. Security considerations

   This draft describes a formal notation similar to ABNF [RFC-2234],
   and hence is not believed to raise any security issues.

8. Acknowledgements

   A number of important concepts and ideas have been borrowed from ROHC
   [RFC-3095].  Updates to the LIST encoding methods owe much to
   discussions with Qian Zhang and Hongbin Liao.

   Thanks to Rob Hancock and Stephen McCann for putting up with the
   authors' arguments and making helpful suggestions, frequently against
   the tide!

   The authors would also like to thank Carsten Bormann, Ghyslain
   Pelletier, Christian Schmidt, Max Riegel and Lars-Erik Jonsson for
   their comments and encouragement.  We haven't always agreed, but the
   arguments have been fun!

9. Authors' addresses

                                                                                                             Richard Price         Tel: +44 1794 833681
   Email:                richard.price@roke.co.uk

   Robert Finking        Tel: +44 1794 833189
   Email:                robert.finking@roke.co.uk


   Roke Manor Research Ltd
   Romsey, Hants, SO51 0ZN
   United Kingdom
   http://www.roke.co.uk

10. References

   [RFC-2026]  "The Internet Standards Process - Revision 3", Scott
               Bradner, RFC 2026, Internet Engineering Task Force,
               October 1996

   [RFC-2119]  "Key words for use in RFCs to Indicate Requirement
               Levels", Scott Bradner, RFC 2119, Internet Engineering
               Task Force, March 1997

   [RFC-2234]  "Augmented BNF for Syntax Specifications: ABNF",
               D. Crocker and P. Overell, RFC 2234, Internet Engineering
               Task Force, November 1997

   [RFC-3095]  "RObust Header Compression (ROHC)", Carsten Bormann et
               al, RFC3095, Internet Engineering Task Force, July 2001



Price et al.                                                   [Page 36]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003
























































Price et al.                                                   [Page 37]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


Appendix A.    Supporting Prolog Code

   This appendix contains the supporting Prolog code that is needed in
   order to execute a profile written in ROHC-FN. It also contains some
   test profiles that illustrate the use of the various encoding
   methods.

                                      -Prolog 5.2

Encoding Methods - rohc_fn.pl

   :- ensure_loaded(debug).
   :- ensure_loaded(basic_predicates).


   %--------------------------------------------------------------------
   %   Standard library of encoding methods
   %--------------------------------------------------------------------

   % The standard library of encoding methods forms the basis of the
   notation.   All Prolog run and tested using SWI
   % A ROHC-FN description essentially just applies one or more encoding
   methods
   % to each field in the uncompressed header. ROHC-FN descriptions can
   only use
   % encoding methods (no raw Prolog!).
   %
   % The encoding methods are built on top of the basic predicates,
   which are
   % defined separately.
   %

   discriminator(DISCRIMINATOR) :-
     get_current_field(NAME),
     uncomp(NAME, ''),
     qualify_name('format', NAME, FORMAT_NAME),
     qualify_name('num_formats', NAME, NUM_FORMATS_NAME),
     atom_length(DISCRIMINATOR, NUM_BITS),
     (
       current_predicate(FORMAT_NAME/0) ->
         context(NAME, CURRENT_FORMAT),
         precision(CHECK),
         make_size(CHECK, CURRENT_FORMAT, FORMAT),
         FORMAT_NAME,
         uncomp(FORMAT_NAME, PROPOSED_FORMAT),
         PROPOSED_FORMAT = FORMAT,
         updated_context(NAME, CURRENT_FORMAT)
       ;
       true
     ),
     (



Price et al.                                                   [Page 38]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


       doing(compression) ->
         (
           current_predicate(NUM_FORMATS_NAME/0) ->
             NUM_FORMATS_NAME,
             uncomp(NUM_FORMATS_NAME, NUM_FORMATS),
             (
               updated_context(NAME, CHECK_FORMAT),
               CHECK_FORMAT = 0 ->
                 (
                   format_name(NUM_FORMATS, CURRENT_FORMAT),
                   updated_context(NAME, CURRENT_FORMAT)
                   ;
                   updated_context(NAME, 0),
                   fail
                 )
               ;
               updated_context(NAME, CURRENT_FORMAT)
             ),
             precision(CHECK),
             make_bin(CHECK, INT_NUM_FORMATS, NUM_FORMATS),
             INDEX_SIZE is ceiling(log(INT_NUM_FORMATS) / log(2)),
             make_size(INDEX_SIZE, CURRENT_FORMAT, ATOM_FORMAT),
             atom_concat(DISCRIMINATOR, ATOM_FORMAT,
   DISCRIMINATOR_AND_FORMAT)
           ;
           DISCRIMINATOR_AND_FORMAT = DISCRIMINATOR
         ),
         comp(NAME, DISCRIMINATOR_AND_FORMAT)
       ;
       doing(decompression) ->
         (
           current_predicate(NUM_FORMATS_NAME/0) ->
             NUM_FORMATS_NAME,
             uncomp(NUM_FORMATS_NAME, NUM_FORMATS),
             precision(CHECK),
             make_bin(CHECK, INT_NUM_FORMATS, NUM_FORMATS),
             INDEX_SIZE is ceiling(log(INT_NUM_FORMATS) / log(2)),
             TOTAL_BITS is NUM_BITS + INDEX_SIZE,
             extract_bits(NAME, TOTAL_BITS, 1),
             comp(NAME, D1),
             sub_atom(D1, 0, NUM_BITS, INDEX_SIZE, DISCRIMINATOR),
             sub_atom(D1, NUM_BITS, INDEX_SIZE, 0, CURRENT_FORMAT),
             updated_context(NAME, CURRENT_FORMAT)
           ;
           extract_bits(NAME, NUM_BITS, 1),
           comp(NAME, D1), DISCRIMINATOR = D1
         )
     ).


   crc(N) :-



Price et al.                                                   [Page 39]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     evaluate(N, 0, V),
     discriminator(V).


   aux_static(NAME, VALUE) :-
     get_current_field(NAME),
     context(NAME, VALUE),
     defined(VALUE),
     atom_length(VALUE, N),
     (
       doing(compression) ->
         extract_bits(NAME, N, 0),
         uncomp(NAME, V), VALUE = V,
         comp(NAME, '')
       ;
       doing(decompression) ->
         comp(NAME, ''),
         uncomp(NAME, VALUE)
     ).

   ncu_static :-
     aux_static(_, _).

   static :-
     aux_static(NAME, VALUE),
     updated_context(NAME, VALUE).


   aux_lsb(K, P, NAME, U_VALUE) :-
     get_current_field(NAME),
     context(NAME, CONTEXT_VALUE),
     defined(CONTEXT_VALUE),
     atom_length(CONTEXT_VALUE, N),
     evaluate(N, P - CONTEXT_VALUE, BASE),
     (
       doing(compression) ->
         extract_bits(NAME, N, 0),
         uncomp(NAME, U_VALUE),
         evaluate(N, (U_VALUE + BASE) mod 2^K, X),
         evaluate(N, U_VALUE + BASE, Y),
         X = Y,
         evaluate(K, U_VALUE, C_VALUE),
         comp(NAME, C_VALUE)
       ;
       doing(decompression) ->
         extract_bits(NAME, K, 1),
         comp(NAME, C_VALUE),
         evaluate(N, (C_VALUE + BASE) mod 2^K, X),
         evaluate(N, X - BASE, U_VALUE),
         uncomp(NAME, U_VALUE)
     ).



Price et al.                                                   [Page 40]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



   ncu_lsb(K, P) :-
     aux_lsb(K, P, _, _).

   lsb(K, P) :-
     aux_lsb(K, P, NAME, VALUE),
     updated_context(NAME, VALUE).


   aux_counter(LENGTH, NAME, COUNTER) :-
     get_current_field(NAME),
     context(NAME, VALUE),
     (
       defined(VALUE) ->
         evaluate(LENGTH, VALUE + 1, COUNTER)
       ;
       evaluate(LENGTH, 0, COUNTER)
     ),
     uncomp(NAME, COUNTER).

   ncu_counter(LENGTH) :-
     aux_counter(LENGTH, _, _).

   counter(LENGTH) :-
     aux_counter(LENGTH, NAME, COUNTER),
     updated_context(NAME, COUNTER).


   aux_irregular(NUM_BITS, NAME, VALUE) :-
     get_current_field(NAME),
     (
       doing(compression) ->
         extract_bits(NAME, NUM_BITS, 0),
         uncomp(NAME, VALUE),
         comp(NAME, VALUE)
       ;
       doing(decompression) ->
         extract_bits(NAME, NUM_BITS, 1),
         comp(NAME, VALUE),
         uncomp(NAME, VALUE)
     ).

   ncu_irregular(NUM_BITS) :-
     aux_irregular(NUM_BITS, _, _).

   irregular(NUM_BITS) :-
     aux_irregular(NUM_BITS, NAME, VALUE),
     updated_context(NAME, VALUE).


   uncompressible(BASE_FIELD, DIVISOR, MULTIPLIER, OFFSET) :-



Price et al.                                                   [Page 41]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     get_current_field(NAME),
     make_atom(BASE_FIELD, ATOMISED_FIELD),
     ATOMISED_FIELD,
     uncomp(ATOMISED_FIELD, BASE_VALUE),
     atom_length(BASE_VALUE, LENGTH),
     make_bin(LENGTH, INT_BASE_VALUE, BASE_VALUE),
     NUM_BITS is (INT_BASE_VALUE // DIVISOR) * MULTIPLIER + OFFSET,
     (
       doing(compression) ->
         extract_bits(NAME, NUM_BITS, 0),
         uncomp(NAME, VALUE),
         comp(NAME, VALUE)
       ;
       doing(decompression) ->
         extract_bits(NAME, NUM_BITS, 1),
         comp(NAME, VALUE),
         uncomp(NAME, VALUE)
     ).


   same_as(QFIELD_NAME) :-
     get_current_field(CURRENT_NAME),
     make_atom(QFIELD_NAME, ATOMISED_FIELD_NAME),
     ATOMISED_FIELD_NAME,
     uncomp(ATOMISED_FIELD_NAME, UNCOMPRESSED_FIELD_VALUE),
     uncomp(CURRENT_NAME, UNCOMPRESSED_FIELD_VALUE).


   group :-
     get_current_field(NAME),
     qualify_name('field_list', NAME, FIELD_LIST_NAME),
     FIELD_LIST_NAME.


   aux_control_field(NAME, VALUE) :-
     get_current_field(NAME),
     qualify_name(base_field, NAME, BASE_NAME),
     qualify_name(compressed_method, NAME, Q_NAME),
     qualify_name(_, QUALIFIER, NAME),
     context(NAME, CONTEXT_VALUE),
     context(BASE_NAME, CONTEXT_VALUE),
     context(Q_NAME, CONTEXT_VALUE),
     (
       doing(compression) ->
         BASE_NAME,
         uncomp(BASE_NAME, VALUE),
         uncomp(NAME, VALUE),
         uncomp_start(Q_NAME, 0),
         Q_NAME,
         uncomp(Q_NAME, UNCOMP_VALUE),
         VALUE = UNCOMP_VALUE,



Price et al.                                                   [Page 42]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


         comp(Q_NAME, COMP_VALUE),
         comp(NAME, COMP_VALUE)
       ;
       doing(decompression) ->
         comp(QUALIFIER, VALUE),
         comp(NAME, VALUE),
         comp_start(NAME, START),
         comp_start(Q_NAME, START),
         Q_NAME,
         comp(Q_NAME, COMP_VALUE),
         comp(NAME, COMP_VALUE),
         uncomp(Q_NAME, UNCOMP_VALUE),
         uncomp(NAME, UNCOMP_VALUE),
         uncomp(BASE_NAME, UNCOMP_VALUE)
         %BASE_NAME
     ),
     updated_context(Q_NAME, CONTEXT_VALUE),
     updated_context(NAME, CONTEXT_VALUE),
     updated_context(BASE_NAME, CONTEXT_VALUE).

   ncu_control_field :-
     aux_control_field(_, _).

   control_field :-
     aux_control_field(NAME, FIELD),
     updated_context(NAME, FIELD).


   aux_derived_value(NAME, VALUE) :-
     get_current_field(NAME),
     qualify_name(field_length, NAME, LENGTH_NAME),
     qualify_name(field_value, NAME, VALUE_NAME),
     LENGTH_NAME,
     uncomp(LENGTH_NAME, ATOM_LENGTH),
     precision(CHECK),
     make_bin(CHECK, LENGTH, ATOM_LENGTH),
     (
       doing(compression) ->
         extract_bits(NAME, LENGTH, 0),
         comp(NAME, '')
       ;
       doing(decompression) ->
         VALUE_NAME,
         uncomp(VALUE_NAME, VALUE),
         make_size(LENGTH, VALUE, UNCOMP_VALUE),
         uncomp(NAME, UNCOMP_VALUE),
         comp(NAME, '')
     ).

   ncu_derived_value :-
     aux_derived_value(_, _).



Price et al.                                                   [Page 43]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



   derived_value :-
     aux_derived_value(NAME, FIELD),
     updated_context(NAME, FIELD).


   aux_value(NUM_BITS, V, NAME, PROPOSED_VALUE) :-
     get_current_field(NAME),
     evaluate(NUM_BITS, V, PROPOSED_VALUE),
     (
       doing(compression) ->
         extract_bits(NAME, NUM_BITS, 0),
         uncomp(NAME, VALUE),
         PROPOSED_VALUE = VALUE,
         comp(NAME, '')
       ;
       doing(decompression) ->
         comp(NAME, ''),
         uncomp(NAME, PROPOSED_VALUE)
     ).

   ncu_value(NUM_BITS, V) :-
     aux_value(NUM_BITS, V, _, _).

   value(NUM_BITS, V) :-
     aux_value(NUM_BITS, V, NAME, PROPOSED_VALUE),
     updated_context(NAME, PROPOSED_VALUE).

   aux_index(NUM_BITS, V_LIST, NAME, PROPOSED_VALUE) :-
     get_current_field(NAME),
     length(V_LIST, LENGTH),
     INDEX_SIZE is ceiling(log(LENGTH) / log(2)),
     (
       doing(compression) ->
         extract_bits(NAME, NUM_BITS, 0),
         uncomp(NAME, VALUE),
         LENGTH1 is LENGTH - 1,
         between(0, LENGTH1, INDEX),
         nth0(INDEX, V_LIST, V),
         evaluate(NUM_BITS, V, PROPOSED_VALUE),
         PROPOSED_VALUE = VALUE,
         make_bin(INDEX_SIZE, INDEX, ATOM_INDEX),
         comp(NAME, ATOM_INDEX)
       ;
       doing(decompression) ->
         extract_bits(NAME, INDEX_SIZE, 1),
         comp(NAME, ATOM_INDEX),
         make_bin(INDEX_SIZE, INDEX, ATOM_INDEX),
         nth0(INDEX, V_LIST, V),
         evaluate(NUM_BITS, V, PROPOSED_VALUE),
         uncomp(NAME, PROPOSED_VALUE)



Price et al.                                                   [Page 44]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     ).

   ncu_index(NUM_BITS, V_LIST) :-
     aux_index(NUM_BITS, V_LIST, _, _).

   index(NUM_BITS, V_LIST) :-
     aux_index(NUM_BITS, V_LIST, NAME, PROPOSED_VALUE),
     updated_context(NAME, PROPOSED_VALUE).

   inferred_ip_checksum :-
     get_current_field(NAME),
     (
       qualify_name(_, HEADER, NAME),
       uncomp(HEADER, HDR_BITS),
       sub_atom(HDR_BITS, 0, 80, _, PRE),
       sub_atom(HDR_BITS, 96, 64, _, POST) ->
         eval16(PRE, VALUE1),
         eval16(POST, VALUE2),
         sum16(VALUE1, VALUE2, TEMP),
         evaluate(16, 65535 - TEMP, CHECKSUM),
         (
           doing(compression) ->
             sub_atom(HDR_BITS, 80, 16, _, CHECKSUM),
             uncomp(NAME, CHECKSUM),
             comp(NAME, '')
           ;
           doing(decompression) ->
             comp(NAME, ''),
             uncomp(NAME, CHECKSUM)
         )
       ;
       doing(decompression) ->
         comp(NAME, ''),
         evaluate(16, 0, CHECKSUM),
         uncomp(NAME, CHECKSUM)
     ).


   inferred_offset(LENGTH) :-
     get_current_field(NAME),
     qualify_name('base_field', NAME, BASE_FIELD),
     qualify_name('offset', NAME, OFFSET),
     BASE_FIELD,
     uncomp(BASE_FIELD, BASE_FIELD_VALUE),
     (
       doing(compression) ->
         extract_bits(NAME, LENGTH, 0),
         uncomp(NAME, FIELD_VALUE),
         evaluate(LENGTH, FIELD_VALUE - BASE_FIELD_VALUE,
   PADDED_OFFSET),
         uncomp(NAME, PADDED_OFFSET),



Price et al.                                                   [Page 45]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


         uncomp_start(OFFSET, 0),
         OFFSET,
         uncomp(NAME, FIELD_VALUE)
       ;
       doing(decompression) ->
         OFFSET,
         uncomp_start(OFFSET, 0),
         uncomp(OFFSET, OFFSET),
         evaluate(LENGTH, OFFSET + BASE_FIELD_VALUE,
   PADDED_FIELD_VALUE),
         uncomp(NAME, PADDED_FIELD_VALUE)
     ).


   inferred_size(LENGTH, OFFSET) :-
     get_current_field(NAME),
     (
       uncomp('', WHOLE_HEADER),
       atom_length(WHOLE_HEADER, HEADER_LENGTH),
       precision(P),
       evaluate(P, (HEADER_LENGTH - OFFSET) / 8, TEMP_FIELD_VALUE),
       evaluate(LENGTH, TEMP_FIELD_VALUE, PROPOSED_FIELD_VALUE),
       (
         doing(compression) ->
           extract_bits(NAME, LENGTH, 0),
           uncomp(NAME, FIELD_VALUE),
           PROPOSED_FIELD_VALUE = FIELD_VALUE,
           comp(NAME, '')
         ;
         doing(decompression) ->
           comp(NAME, ''),
           uncomp(NAME, PROPOSED_FIELD_VALUE)
       ) ->
         true
       ;
       doing(decompression) ->
         comp(NAME, ''),
         evaluate(LENGTH, 0, PROPOSED_FIELD_VALUE),
         uncomp(NAME, PROPOSED_FIELD_VALUE)
     ).


   single_packet_format :-
     get_current_field(NAME),
     qualify_name('uncompressed_data', NAME, U_NAME),
     qualify_name('compressed_data', NAME, C_NAME),
     chosen_packet_format(NAME, U_NAME, C_NAME, no_common_format).


   list_of_known_length :-
     get_current_field(NAME),



Price et al.                                                   [Page 46]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     qualify_name('list_length', NAME, LIST_LENGTH),
     qualify_name('list_items', NAME, LIST_ITEMS),
     qualify_name(_, QUALIFIER, NAME),
     (
       doing(compression) ->
         uncomp(QUALIFIER, HEADER),
         uncomp_start(NAME, START),
         sub_atom(HEADER, START, _, 0, SUB_HEADER),
         uncomp(NAME, SUB_HEADER),
         LIST_LENGTH,
         LIST_ITEMS,
         uncomp(LIST_ITEMS, UNCOMP_HEADER),
         atom_prefix(SUB_HEADER, UNCOMP_HEADER),
         uncomp(NAME, UNCOMP_HEADER),
         comp(LIST_ITEMS, COMP_HEADER),
         comp(NAME, COMP_HEADER)
       ;
       doing(decompression) ->
         comp(QUALIFIER, HEADER),
         comp_start(NAME, START),
         sub_atom(HEADER, START, _, 0, TOTAL_HEADER),
         comp(NAME, TOTAL_HEADER),
         LIST_LENGTH,
         LIST_ITEMS,
         comp(LIST_ITEMS, COMP_HEADER),
         atom_prefix(TOTAL_HEADER, COMP_HEADER),
         comp(NAME, COMP_HEADER),
         uncomp(LIST_ITEMS, UNCOMP_HEADER),
         uncomp(NAME, UNCOMP_HEADER)
     ).


   from_list(LIST_NAME) :-
     get_current_field(NAME),
     (
       doing(compression) ->
         true
       ;
       doing(decompression) ->
         make_atom(LIST_NAME, ATOMISED_LIST_NAME),
         uncomp(ATOMISED_LIST_NAME, UNCOMPRESSED_FIELD_VALUE),
         uncomp(NAME, UNCOMPRESSED_FIELD_VALUE)
     ).


   multiple_packet_formats :-
     get_current_field(NAME),
     (
       PREFIX = co ->
         true
       ;



Price et al.                                                   [Page 47]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


       PREFIX = replicate
     ),
     qualify_name('uncompressed_format', NAME, U_NAME),
     qualify_name('chosen_format', NAME, CHOSEN_FORMAT),
     qualify_name('chosen_common', NAME, CHOSEN_COMMON),
     atom_concat(PREFIX, '_num_formats', FORMATS),
     qualify_name(FORMATS, NAME, Q_FORMATS),
     Q_FORMATS,
     uncomp(Q_FORMATS, NUM_FORMATS),
     (
       comp(CHOSEN_FORMAT, CHECK_NAME), CHECK_NAME = 0 ->
       (
         format_name(NUM_FORMATS, FORMAT_NUM_ATOM)
         ;
         comp(CHOSEN_FORMAT, 0),
         fail
       ),
       concat_atom([PREFIX, '_format_', FORMAT_NUM_ATOM],
   UNQUALIFIED_C_NAME),
       atom_concat(PREFIX, '_common', UNQUALIFIED_COMMON_NAME),
       qualify_name(UNQUALIFIED_C_NAME, NAME, C_NAME),
       qualify_name(UNQUALIFIED_COMMON_NAME, NAME, COMMON_NAME)
       ;
       true
     ),
     comp(CHOSEN_FORMAT, C_NAME),
     comp(CHOSEN_COMMON, COMMON_NAME),
     chosen_packet_format(NAME, U_NAME, C_NAME, COMMON_NAME).


   sequence(LIST) :-
     get_current_field(NAME),
     qualify_name(WHICH, QUALIFIER, NAME),
     qualify_name(default_methods, QUALIFIER, BACKUP_NAME),
     (
       WHICH = uncompressed_format ->
         qualify_name('chosen_format', QUALIFIER, CHOSEN_FORMAT),
         qualify_name('chosen_common', QUALIFIER, CHOSEN_COMMON),
         comp(CHOSEN_FORMAT, FORMAT_NAME),
         comp(CHOSEN_COMMON, COMMON_NAME),
         (
           doing(compression) ->
             uncomp(QUALIFIER, HEADER),
             uncomp(FORMAT_NAME, HEADER),
             uncomp(COMMON_NAME, HEADER),
             uncomp(BACKUP_NAME, HEADER)
           ;
           true
         ),
         copy_items(FORMAT_NAME, COMMON_NAME, BACKUP_NAME, LIST, 0,
   FIXED_HEADER, 0),



Price et al.                                                   [Page 48]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


         uncomp(NAME, FIXED_HEADER)
       ;
       (
         atom_prefix(WHICH, co_format_) ->
           true
         ;
         atom_prefix(WHICH, replicate_format_) ->
           true
         ;
         WHICH = co_common ->
           true
         ;
         WHICH = replicate_common
       ) ->
         (
           doing(decompression) ->
             comp(QUALIFIER, HEADER),
             comp(NAME, HEADER),
             comp(BACKUP_NAME, HEADER)
           ;
           true
         ),
         copy_items(NAME, no_common_format, BACKUP_NAME, LIST, 0,
                    FIXED_HEADER, 1),
         comp(NAME, FIXED_HEADER)
       ;
       WHICH = uncompressed_data ->
         call_items(QUALIFIER, LIST, 0, FIXED_HEADER, 0),
         uncomp(NAME, FIXED_HEADER)
       ;
       WHICH = compressed_data ->
         call_items(QUALIFIER, LIST, 0, FIXED_HEADER, 1),
         comp(NAME, FIXED_HEADER)
       ;
       WHICH = list_items ->
         qualify_name('order', QUALIFIER, LIST_ORDER),
         qualify_name('order_flag', QUALIFIER, ORDER_FLAG),
         qualify_name('presence', QUALIFIER, LIST_PRESENCE),
         qualify_name('presence_flag', QUALIFIER, PRESENCE_FLAG),
         qualify_name('total', QUALIFIER, LIST_TOTAL),
         (
           doing(decompression) ->
             length(LIST, LENGTH),
             LENGTH > 0,
             INDEX_SIZE is ceiling(log(LENGTH) / log(2)),
             comp(QUALIFIER, TOTAL_HEADER),
             ORDER_FLAG,
             PRESENCE_FLAG,
             (
               uncomp(ORDER_FLAG, O_F), O_F = '0' ->
                 context(LIST_ORDER, ORDER),



Price et al.                                                   [Page 49]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


                 defined(ORDER),
                 uncomp(LIST_ORDER, ORDER),
                 PARTIAL_HEADER = TOTAL_HEADER,
                 atom_length(ORDER, ORDER_LENGTH),
                 TOTAL is ORDER_LENGTH // INDEX_SIZE
               ;
               sub_atom(TOTAL_HEADER, 0, 8, _, ATOM_TOTAL),
               make_bin(8, TOTAL, ATOM_TOTAL),
               ORDER_LENGTH is TOTAL * INDEX_SIZE,
               sub_atom(TOTAL_HEADER, 8, ORDER_LENGTH, REMAINDER,
   ORDER),
               sub_atom(TOTAL_HEADER, _, REMAINDER, 0, PARTIAL_HEADER),
               uncomp(LIST_ORDER, ORDER)
             ),
             (
               uncomp(PRESENCE_FLAG, P_F), P_F = '0' ->
                 context(LIST_PRESENCE, PRESENCE),
                 defined(PRESENCE),
                 uncomp(LIST_PRESENCE, PRESENCE),
                 SUB_HEADER = PARTIAL_HEADER
               ;
               sub_atom(PARTIAL_HEADER, 0, TOTAL, _, PRESENCE),
               sub_atom(PARTIAL_HEADER, TOTAL, _, 0, SUB_HEADER),
               uncomp(LIST_PRESENCE, PRESENCE)
             ),
             sub_atom(TOTAL_HEADER, COMP_START, _, 0, SUB_HEADER)
           ;
           COMP_START = 0
         ),
         call_list_items(QUALIFIER, LIST, 0, COMP_START,
                         UNCOMP_HEADER, COMP_HEADER, TOTAL),
         make_bin(8, TOTAL, ATOM_TOTAL),
         uncomp(LIST_TOTAL, ATOM_TOTAL),
         uncomp(NAME, UNCOMP_HEADER),
         (
           doing(compression) ->
             uncomp(LIST_ORDER, ORDER),
             context(LIST_ORDER, OLD_ORDER),
             (
               ORDER = OLD_ORDER ->
                 M_ORDER = '',
                 uncomp(ORDER_FLAG, '0')
               ;
               atom_concat(ATOM_TOTAL, ORDER, M_ORDER),
               uncomp(ORDER_FLAG, '1')
             ),
             uncomp(LIST_PRESENCE, PRESENCE),
             context(LIST_PRESENCE, OLD_PRESENCE),
             (
               PRESENCE = OLD_PRESENCE ->
                 M_PRESENCE = '',



Price et al.                                                   [Page 50]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


                 uncomp(PRESENCE_FLAG, '0')
               ;
               M_PRESENCE = PRESENCE,
               uncomp(PRESENCE_FLAG, '1')
             ),
             concat_atom([M_ORDER, M_PRESENCE, COMP_HEADER], NEW_TOTAL),
             comp(NAME, NEW_TOTAL)
           ;
           sub_atom(TOTAL_HEADER, 0, COMP_START, _, COMP_PREFIX),
           atom_concat(COMP_PREFIX, COMP_HEADER, NEW_TOTAL),
           comp(NAME, NEW_TOTAL)
         ),
         updated_context(LIST_ORDER, ORDER),
         updated_context(LIST_PRESENCE, PRESENCE)
       ;
       WHICH = field_list ->
         call_group_items(LIST, UNCOMP_FIELD),
         uncomp(QUALIFIER, UNCOMP_FIELD),
         comp(QUALIFIER, '')
       ;
       LIST = [ITEM] ->
         ITEM
     ).


   expression(EXPRESSION) :-
     get_current_field(NAME),
     precision(NUM_BITS),
     evaluate(NUM_BITS, EXPRESSION, VALUE),
     uncomp(NAME, VALUE).


   constant(VALUE) :-
     expression(VALUE).


   % New maths functions.

   uncomp(NAME, VALUE)          :- unify_value(NAME, 0, VALUE).
   comp(NAME, VALUE)            :- unify_value(NAME, 1, VALUE).
   context(NAME, VALUE)         :- unify_value(NAME, 2, VALUE).
   updated_context(NAME, VALUE) :- unify_value(NAME, 3, VALUE).
   uncomp_start(NAME, VALUE)    :- unify_value(NAME, 4, VALUE).
   comp_start(NAME, VALUE)      :- unify_value(NAME, 5, VALUE).


   comp_length(NAME, VALUE) :-
     comp(NAME, FIELD),
     defined(FIELD),
     atom_length(FIELD, INT_VALUE),
     precision(LENGTH),



Price et al.                                                   [Page 51]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     make_bin(LENGTH, INT_VALUE, VALUE).


   sum16(X, Y, SUM) :-
     evaluate(17, (X + Y + (X + Y) // 65536) mod 2^16, SUM).


   eval16(BITS, VALUE) :-
     BITS = '' ->
       evaluate(16, 0, VALUE)
     ;
     sub_atom(BITS, 0, 16, N, VALUE1),
     sub_atom(BITS, 16, N, 0, REST),
     eval16(REST, VALUE2),
     sum16(VALUE1, VALUE2, VALUE).


                 - basic_predicates.pl

   :-                       Basic Predicates      ensure_loaded(debug).

   %------------------------------------------------------------------
   %   Basic predicates
   %------------------------------------------------------------------

   % The following basic predicates are used when defining the library
   of
   % encoding methods.

   unify_value(NAME, TYPE, VALUE) :-
     make_atom(NAME, ATOMISED_NAME),
     functor(HDR_NAME, ATOMISED_NAME, TYPE),
     type(TYPE, TYPE_DESCRIPTION),
     (
       var(VALUE) ->
         flag(HDR_NAME, VALUE, VALUE),
         (
           debug(1) ->
             write('Verify: '), write(TYPE_DESCRIPTION),
   write(ATOMISED_NAME),
             write(' = '), write(VALUE), nl
           ;
           true
         )
       ;
       flag(HDR_NAME, _, VALUE),
       (
         debug(1) ->
           write('Set: '), write(TYPE_DESCRIPTION),
   write(ATOMISED_NAME),
           write(' = '), write(VALUE), nl



Price et al.                                                   [Page 52]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


         ;
         true
       )
     ).


   get_current_field(NAME) :-
     flag('$current_field', NAME, NAME).


   defined(VALUE) :-
     VALUE \= 0.


   name(NAME) :-
     flag('$current_field', _, NAME).


   doing(X) :-
     flag('$doing', X, X).


   qualify_name(NAME, QUALIFIER, QUALIFIED_NAME) :-
     var(QUALIFIED_NAME) ->
       concat_atom([QUALIFIER, NAME], '.', QUALIFIED_NAME)
     ;
     concat_atom(LIST, '.', QUALIFIED_NAME),
     append(LIST1, [NAME], LIST),
     concat_atom(LIST1, '.', QUALIFIER).


   extract_bits(NAME, LENGTH, TYPE) :-
     TYPE1 is TYPE + 4,
     unify_value(NAME, TYPE1, START),
     qualify_name(_, QUALIFIER, NAME),
     unify_value(QUALIFIER, TYPE, HEADER),
     sub_atom(HEADER, START, LENGTH, _, VALUE),
     unify_value(NAME, TYPE, VALUE).


   make_bin(LENGTH, INT_V, ATOM_V) :-
     integer(INT_V) ->
       TEMP_INT_V is ((INT_V mod 2^LENGTH) + 2^LENGTH) mod 2^LENGTH,
       int_to_atom(TEMP_INT_V, 2, ATOM),
       atom_length(ATOM, N), N1 is N - 2,
       sub_atom(ATOM, 2, N1, 0, TEMP_ATOM_V),
       make_size(LENGTH, TEMP_ATOM_V, ATOM_V)
     ;
     atom(ATOM_V) ->
       atom_length(ATOM_V, LENGTH),
       atom_chars(ATOM_V, TEMP),



Price et al.                                                   [Page 53]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


       number_chars(INT_V, ['0', 'b' | TEMP]).


   make_size(N, V, NEW_V) :-
     atom_length(V, N1),
     (
       N1 =< N ->
         N2 is N - N1,
         make_correct_length(N2, V, NEW_V)
       ;
       N1 > N ->
         sub_atom(V, _, N, 0, NEW_V)
     ).


   make_correct_length(N, V, NEW_V) :-
     N = 0 ->
       NEW_V = V
     ;
     N > 0 ->
       N1 is N - 1,
       make_correct_length(N1, V, V1),
       atom_concat('0', V1, NEW_V).


   call_items(NAME, LIST, START, HEADER, TYPE) :-
     LIST = [] ->
       HEADER = ''
     ;
     LIST = [ENTRY | LIST1],
     (
       ENTRY = (ITEM1 : _) ->
         true
       ;
       ITEM1 = ENTRY
     ),
     make_atom(ITEM1, ITEM),
     qualify_name(ITEM, NAME, Q_ITEM),
     TYPE1 is TYPE + 4,
     unify_value(Q_ITEM, TYPE1, START),
     Q_ITEM,
     unify_value(Q_ITEM, TYPE, FIELD_VALUE),
     atom_length(FIELD_VALUE, LENGTH),
     START1 is START + LENGTH,
     call_items(NAME, LIST1, START1, HEADER1, TYPE),
     atom_concat(FIELD_VALUE, HEADER1, HEADER).


   call_list_items(NAME, LIST, UNCOMP_START, COMP_START,
                   UNCOMP_HEADER, COMP_HEADER, TOTAL) :-
     qualify_name(order, NAME, ORDER_NAME),



Price et al.                                                   [Page 54]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     qualify_name(presence, NAME, PRESENCE_NAME),
     qualify_name(list_length, NAME, LENGTH_NAME),
     uncomp(LENGTH_NAME, LEN),
     precision(N),
     make_bin(N, INT_LEN, LEN),
     (
       UNCOMP_START = INT_LEN ->
         COMP_HEADER   = '',
         UNCOMP_HEADER = '',
         uncomp(ORDER_NAME, X),
         (
           X = 0 ->
             true
           ;
           X = '' ->
             true
         ),
         uncomp(ORDER_NAME, ''),
         uncomp(PRESENCE_NAME, ''),
         TOTAL = 0
       ;
       length(LIST, LENGTH),
       LENGTH > 0,
       INDEX_SIZE is ceiling(log(LENGTH) / log(2)),
       (
         uncomp(ORDER_NAME, X), X = 0 ->
           ATOM_OPT = '1',
           (
             member(ENTRY, LIST),
             uncomp(ORDER_NAME, 0)
             ;
             uncomp(ORDER_NAME, 0),
             fail
           ),
           nth0(INDEX, LIST, ENTRY),
           make_bin(INDEX_SIZE, INDEX, ATOM_INDEX)
         ;
         uncomp(PRESENCE_NAME, PRESENCE1),
         uncomp(ORDER_NAME, ORDER1),
         sub_atom(PRESENCE1, _, 1, 0, ATOM_OPT),
         sub_atom(ORDER1, _, INDEX_SIZE, 0, ATOM_INDEX),
         atom_concat(PRESENCE, ATOM_OPT, PRESENCE1),
         atom_concat(ORDER, ATOM_INDEX, ORDER1),
         uncomp(PRESENCE_NAME, PRESENCE),
         uncomp(ORDER_NAME, ORDER),
         make_bin(INDEX_SIZE, INDEX, ATOM_INDEX),
         nth0(INDEX, LIST, ENTRY),
         member(ENTRY, LIST)
       ),
       (
         ATOM_OPT = '1' ->



Price et al.                                                   [Page 55]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


           make_atom(ENTRY, ITEM),
           qualify_name(ITEM, NAME, Q_ITEM),
           uncomp_start(Q_ITEM, UNCOMP_START),
           comp_start(Q_ITEM, COMP_START),
           % write(Q_ITEM),nl,
           Q_ITEM,
           uncomp(Q_ITEM, UNCOMP_VALUE),
           comp(Q_ITEM, COMP_VALUE),
           atom_length(UNCOMP_VALUE, UNCOMP_LENGTH),
           atom_length(COMP_VALUE, COMP_LENGTH),
           UNCOMP_START1 is UNCOMP_START + UNCOMP_LENGTH,
           COMP_START1 is COMP_START + COMP_LENGTH
         ;
         UNCOMP_VALUE = '',
         COMP_VALUE = '',
         UNCOMP_START1 = UNCOMP_START,
         COMP_START1 = COMP_START
       ),
       call_list_items(NAME, LIST, UNCOMP_START1, COMP_START1,
                       UNCOMP_HEADER1, COMP_HEADER1, TOTAL1),
       TOTAL is TOTAL1 + 1,
       atom_concat(UNCOMP_VALUE, UNCOMP_HEADER1, UNCOMP_HEADER),
       atom_concat(COMP_VALUE, COMP_HEADER1, COMP_HEADER),
       uncomp(ORDER_NAME, ORDER),
       atom_concat(ORDER, ATOM_INDEX, ORDER1),
       uncomp(ORDER_NAME, ORDER1),
       uncomp(PRESENCE_NAME, PRESENCE),
       atom_concat(PRESENCE, ATOM_OPT, PRESENCE1),
       uncomp(PRESENCE_NAME, PRESENCE1)
     ).


   copy_items(NAME, COMMON_NAME, BACKUP_NAME, LIST, START, HEADER, TYPE)
   :-
     LIST = [] ->
       HEADER = ''
     ;
     LIST = [ENTRY | LIST1],
     (
       ENTRY = (ITEM1 : _) ->
         true
       ;
       ITEM1 = ENTRY
     ),
     make_atom(ITEM1, ITEM),
     qualify_name(_, QUALIFIER, NAME),
     qualify_name(ITEM, QUALIFIER, PARENT_ITEM),
     qualify_name(ITEM, NAME, Q_ITEM),
     qualify_name(ITEM, COMMON_NAME, COMMON_ITEM),
     qualify_name(ITEM, BACKUP_NAME, BACKUP_ITEM),
     (



Price et al.                                                   [Page 56]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


       current_predicate(Q_ITEM/0) ->
         CALLED_ITEM = Q_ITEM
       ;
       current_predicate(COMMON_ITEM/0) ->
         CALLED_ITEM = COMMON_ITEM
       ;
       CALLED_ITEM = BACKUP_ITEM
     ),
     context(PARENT_ITEM, CONTEXT_VALUE),
     context(CALLED_ITEM, CONTEXT_VALUE),
     TYPE1 is TYPE + 4,
     unify_value(CALLED_ITEM, TYPE1, START),
     CALLED_ITEM,
     unify_value(CALLED_ITEM, TYPE, FIELD_VALUE),
     atom_length(FIELD_VALUE, LENGTH),
     START1 is START + LENGTH,
     uncomp(CALLED_ITEM, HDR_VALUE),
     uncomp(PARENT_ITEM, HDR_VALUE),
     comp(CALLED_ITEM, COMP_FIELD_VALUE),
     comp(PARENT_ITEM, COMP_FIELD_VALUE),
     updated_context(CALLED_ITEM, UPDATED_CONTEXT_VALUE),
     updated_context(PARENT_ITEM, UPDATED_CONTEXT_VALUE),
     copy_items(NAME, COMMON_NAME, BACKUP_NAME, LIST1, START1, HEADER1,
   TYPE),
     atom_concat(FIELD_VALUE, HEADER1, HEADER).


   call_group_items(LIST, UNCOMP_FIELD) :-
     LIST = [] ->
       UNCOMP_FIELD = ''
     ;
     LIST = [ITEM1 | LIST1] ->
       call_group_items(LIST1, UNCOMP_REMAINDER),
       make_atom(ITEM1, ITEM),
       uncomp(ITEM, UNCOMP_VALUE),
       atom_concat(UNCOMP_VALUE, UNCOMP_REMAINDER, UNCOMP_FIELD).

   chosen_packet_format(NAME, U_NAME, C_NAME, COMMON_NAME) :-
     qualify_name(_, QUALIFIER, NAME),
     (
       doing(compression) ->
         uncomp(QUALIFIER, HEADER),
         uncomp_start(NAME, START),
         sub_atom(HEADER, START, _, 0, SUB_HEADER),
         uncomp(NAME, SUB_HEADER),
         U_NAME,
         uncomp(U_NAME, UNCOMP_HEADER),
         atom_prefix(SUB_HEADER, UNCOMP_HEADER),
         uncomp(NAME, UNCOMP_HEADER),
         (
           current_predicate(COMMON_NAME/0) ->



Price et al.                                                   [Page 57]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


             COMMON_NAME,
             comp(COMMON_NAME, COMMON_HEADER)
           ;
           COMMON_HEADER = ''
         ),
         C_NAME,
         comp(C_NAME, C_HEADER),
         atom_concat(COMMON_HEADER, C_HEADER, COMP_HEADER),
         comp(NAME, COMP_HEADER)
       ;
       doing(decompression) ->
         comp(QUALIFIER, HEADER),
         comp_start(NAME, START),
         sub_atom(HEADER, START, _, 0, SUB_HEADER),
         comp(NAME, SUB_HEADER),
         (
           current_predicate(COMMON_NAME/0) ->
             COMMON_NAME,
             comp(COMMON_NAME, COMMON_HEADER)
           ;
           COMMON_HEADER = ''
         ),
         atom_concat(COMMON_HEADER, REMAINING_HEADER, SUB_HEADER),
         comp(NAME, REMAINING_HEADER),
         C_NAME,
         comp(C_NAME, COMP_HEADER),
         atom_prefix(REMAINING_HEADER, COMP_HEADER),
         comp(NAME, COMP_HEADER),
         U_NAME,
         uncomp(U_NAME, UNCOMP_HEADER1),
         uncomp(NAME, UNCOMP_HEADER1),
         U_NAME,
         uncomp(U_NAME, UNCOMP_HEADER),
         uncomp(NAME, UNCOMP_HEADER)
     ).


   format_name(NUM_FORMATS, FORMAT_NUM_ATOM) :-
     precision(LENGTH),
     make_bin(LENGTH, INT_FORMATS, NUM_FORMATS),
     UPPER_FORMAT_NUM is INT_FORMATS - 1,
     between(0, UPPER_FORMAT_NUM, FORMAT_NUM),
     int_to_atom(FORMAT_NUM, FORMAT_NUM_ATOM).


   make_atom(NAME, ATOMISED_NAME) :-
     NAME = .(LEFT, RIGHT) ->
       make_atom(RIGHT, ATOMISED_RIGHT),
       concat_atom([LEFT, ATOMISED_RIGHT], '.', ATOMISED_NAME)
     ;
     ATOMISED_NAME = NAME.



Price et al.                                                   [Page 58]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003




   evaluate(LENGTH, EXPRESSION, VALUE) :-
     EXPRESSION =.. [FUNCTOR | ARG_LIST],
     length(ARG_LIST, ARITY),
     Z is ARITY + 1,
     (
       atom(FUNCTOR), current_predicate(FUNCTOR/Z) ->
         reverse([VALUE1 | ARG_LIST], ARGUMENTS),
         apply(FUNCTOR, ARGUMENTS),
         make_size(LENGTH, VALUE1, VALUE)
       ;
       maplist(evaluate(LENGTH), ARG_LIST, ATOM_LIST),
       maplist(make_bin(LENGTH), INT_LIST, ATOM_LIST),
       TERM =.. [FUNCTOR | INT_LIST],
       (
         atom(TERM) ->
           VALUE1 = TERM,
           make_size(LENGTH, VALUE1, VALUE)
         ;
         INT_VALUE is TERM,
         make_bin(LENGTH, INT_VALUE, VALUE)
        )
      ).

   precision(16).


Debug - debug.pl

   %--------------------------------------------------------------------
   %   Debug
   %--------------------------------------------------------------------

   debug(0).

   type(0, 'Uncompressed ').
   type(1, 'Compressed ').
   type(2, 'Context ').
   type(3, 'New context ').
   type(4, 'Start of uncompressed field ').
   type(5, 'Start of compressed field ').

   p(ITEM) :- write(ITEM), nl, nl.

   print_list(LIST) :-
     debug(2) ->
     (
       LIST = [] ->
         true
       ;



Price et al.                                                   [Page 59]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


       LIST = [ITEM | LIST1],
       portray_clause(ITEM), nl, nl,
       print_list(LIST1)
     )
     ;
     true.


Defaults - defaults.pl

   :- ensure_loaded(debug).


   %--------------------------------------------------------------------
   %   Default Values
   %--------------------------------------------------------------------

   default_direction(compression).
   default_encoding(test_list).
   default_uncompressed_header('00010010').
   default_compressed_header('').
   %default_uncompressed_header('00101111').
   %default_compressed_header('101').
   %default_uncompressed_header('010001010000000000000000001011000111000
   000101110010000000000000001111111000001100111110111110010110000010111
   0110110010010000101111000001011101101100000110110010').
   %default_compressed_header('01000101000000000000000000101100011100000
   010111001000000000000000111111100000110110000010111011011001001000010
   1111000001011101101100000110110010').
   %default_uncompressed_header('010001010000000000000000001011000111000
   000101110010000000000000001111111000001100111110111110010110000010111
   011011001001000010111100000101110110110000011011001000000000010100001
   000000001010100011011100001101011110000000010101011110000101110100000
   100010111001100000000100100010001000111000010010110000110000000000000
   0000000000010000001000000010110110100').


Preprocessor - preprocessor.pl

   :- ensure_loaded(debug).
   :- ensure_loaded(rohc_fn).


   %--------------------------------------------------------------------
   %   Preprocessor
   %--------------------------------------------------------------------

   :- op(1000,xfy,::=).
   :- op(950,xfy,:).
   :- op(850,xf,bits).
   :- op(600,xfy,.).



Price et al.                                                   [Page 60]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



   % Parses the initial ROHC-FN text and divides it into a set of rules,
   % eliminating the curly braces.

   term_expansion(TEXT, RULE_LIST) :-
     TEXT = (_ ::= _),
     parse_text(TEXT, [], RULE_LIST),
     set_defaults,
     (
       debug(2) ->
         protocol('methods.txt'), print_list(RULE_LIST), noprotocol
       ;
       true
     ).


   parse_text(TEXT, NAMES, RULE_LIST) :-
     TEXT = '' ->
       RULE_LIST = []
     ;
     TEXT = (HEAD ::= BODY) ->
       goal_list(BODY, GOALS, REMAINING_TEXT),
       make_atom(HEAD, HEAD1),
       reverse([HEAD1 | NAMES], NAMES1),
       concat_atom(NAMES1, '.', QUALIFIED_HEAD),
       GOALS1 = sequence(GOALS),
       NEW_RULE =
       (
         QUALIFIED_HEAD :-
           name(QUALIFIED_HEAD), GOALS1),
           (
             REMAINING_TEXT = ({TEXT_IN_CURLY_BRACES}, NEW_TEXT) ->
               parse_text(TEXT_IN_CURLY_BRACES, [HEAD1 | NAMES],
   RULE_LIST1)
             ;
             REMAINING_TEXT = {TEXT_IN_CURLY_BRACES} ->
               parse_text(TEXT_IN_CURLY_BRACES, [HEAD1 | NAMES],
   RULE_LIST1),
               NEW_TEXT = ''
             ;
             RULE_LIST1 = [], NEW_TEXT = REMAINING_TEXT
           ),
         parse_text(NEW_TEXT, NAMES, RULE_LIST2),
         append([NEW_RULE | RULE_LIST1], RULE_LIST2, RULE_LIST
       ).

   goal_list(BODY, GOALS, REMAINING_TEXT) :-
     BODY = (GOAL, BODY1) ->
       GOAL \= {_},
       functor(GOAL, F, _),
       (



Price et al.                                                   [Page 61]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


         atom_codes(F, [A | _]), between(48, 49, A) ->
           GOAL1 = discriminator(F)
         ;
         GOAL1 = GOAL
       ),
       (
         goal_list(BODY1, GOALS1, REMAINING_TEXT) ->
           GOALS = [GOAL1 | GOALS1]
         ;
         GOALS = [GOAL1],
         REMAINING_TEXT = BODY1
       )
     ;
     BODY \= (_ ::= _), BODY \= {_} ->
       functor(BODY, F, _),
       (
         atom_codes(F, [A | _]), between(48, 49, A) ->
           GOALS = [discriminator(F)]
         ;
         GOALS = [BODY]
       ),
       REMAINING_TEXT = ''.

   set_defaults :-
     default_direction(D),
     default_encoding(E),
     default_uncompressed_header(U),
     default_compressed_header(C),
     flag('$doing', _, D),
     flag('$encoding', _, E),
     uncomp('', U),
     comp('', C).


Test Profiles - test_profiles.pl

   %--------------------------------------------------------------------
   %   Test profiles
   %--------------------------------------------------------------------

   % context('ip.version', '0000').

   test_list                ::=   single_packet_format,

   { uncompressed_data      ::=   list_of_fields,

     compressed_data        ::=   order_flag,
                                  presence_flag,
                                  list_of_fields,

     order_flag             ::=   control_field,



Price et al.                                                   [Page 62]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003



     { base_field           ::=
   same_as(test_list.list_of_fields.order_flag),

       compressed_method    ::=   irregular(1)},

     presence_flag          ::=   control_field,

     { base_field           ::=
   same_as(test_list.list_of_fields.presence_flag),

       compressed_method    ::=   irregular(1)},

     list_of_fields         ::=   list_of_known_length,

     { list_length          ::=   constant(8),
       order_flag           ::=   from_list(test_list.order_flag),
       presence_flag        ::=   from_list(test_list.presence_flag),

       list_items           ::=   field_1,
                                  field_2,
                                  field_3,
   %
       field_1              ::=   irregular(4),

       field_2              ::=   value(4, 2),

       field_3              ::=   inferred_size(4, 0)}},

   test_replicate_formats ::=   multiple_packet_formats,

   { co_num_formats      ::=   constant(2),

     co_format_0         ::=   discriminator,
                               field_1,

     { discriminator     ::=   '00',
       field_1           ::=   static},

     co_format_1         ::=   discriminator,
                               field_1,

     { discriminator     ::=   '01',
       field_1           ::=   irregular(4)},

     replicate_num_formats ::=   constant(2),

     replicate_common    ::=   rep_discriminator,
                               field_1,

     { rep_discriminator ::=   '1',



Price et al.                                                   [Page 63]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


       field_1           ::=   lsb(3,0)},

     replicate_format_0  ::=   discriminator,

     { discriminator     ::=   '1'},

     replicate_format_1  ::=   discriminator,

     { discriminator     ::=   '0'},

     uncompressed_format ::=   field_1,
                               field_2,

     default_methods     ::=   ... ,

     { field_1           ::=   value(4,1),
       field_2           ::=   value(4,2)}},


   test_packet_formats   ::=   multiple_packet_formats,

   {
     uncompressed_format ::=   field_1,
                               field_2,

     co_num_formats      ::=   constant(3),

     co_format_0         ::=   discriminator,
                               field_1,

     { discriminator     ::=   '0',
       field_1           ::=   static
     },

     co_format_1         ::=   discriminator,

     { discriminator     ::=   '10'
     },

     co_format_2         ::=   discriminator,
                               field_1,

     { discriminator     ::=   '11',
       field_1           ::=   irregular(4)
     },

     default_methods     ::=   ... ,

     { field_1           ::=   value(4,1),
       field_2           ::=   value(4,2)
     }



Price et al.                                                   [Page 64]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   },



   sandwich_header_1     ::=   single_packet_format,
   {
     uncompressed_data   ::=   num_sandwiches  : 4 bits,
                               num_extras      : 4 bits,

     compressed_data     ::=   num_sandwiches  : 4 bits,
                               num_extras      : 4 bits,

     num_sandwiches      ::=   irregular(4),
     num_extras          ::=   irregular(4)
   },


   sandwich_header_2     ::=   single_packet_format,
   {
     uncompressed_data   ::=   num_sandwiches  : 4 bits,
                               num_extras      : 4 bits,

     compressed_data     ::=   num_sandwiches  : 4 bits,
                               num_extras      : 0 bits,

     num_sandwiches      ::=   irregular(4),
     num_extras          ::=   value(4, 2)
   },


   sandwich_header_3     ::=   multiple_packet_formats,
   {
     uncompressed_format ::=   num_sandwiches  : 4 bits,
                               num_extras      : 4 bits,

     co_num_formats      ::=   constant(2),

     co_format_0         ::=   discriminator   : 1 bits,
                               num_sandwiches  : 0 bits,
                               num_extras      : 0 bits,
     {
       discriminator     ::=   '0',
       num_sandwiches    ::=   static,
       num_extras        ::=   value(4, 2)
     },

     co_format_1         ::=   discriminator   : 1 bits,
                               num_sandwiches  : 4 bits,
                               num_extras      : 0 bits,
     {
       discriminator     ::=   '1',



Price et al.                                                   [Page 65]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


       num_sandwiches    ::=   irregular(4),
       num_extras        ::=   value(4, 2)
     }
   },


   sandwich_header_4     ::=   multiple_packet_formats,
   {
     uncompressed_format ::=   num_sandwiches  : 4 bits,
                               num_extras      : 4 bits,

     co_num_formats      ::=   constant(3),

     co_format_0         ::=   discriminator   : 1 bits,
                               num_sandwiches  : 0 bits,
                               num_extras      : 0 bits,
     {
       discriminator     ::=   '0',
       num_sandwiches    ::=   static,
       num_extras        ::=   value(4, 2)
     },

     co_format_1         ::=   discriminator   : 2 bits,
                               num_sandwiches  : 0 bits,
                               num_extras      : 0 bits,
     {
       discriminator     ::=   '10',
       num_sandwiches    ::=   value(4, 1),
       num_extras        ::=   value(4, 2)
     },

     co_format_2         ::=   discriminator   : 2 bits,
                               num_sandwiches  : 4 bits,
                               num_extras      : 0 bits,
     {
       discriminator     ::=   '11',
       num_sandwiches    ::=   irregular(4),
       num_extras        ::=   value(4, 2)
     }
   },


   sandwich_header_5     ::=   multiple_packet_formats,
   {
     uncompressed_format ::=   num_sandwiches  : 4 bits,
                               num_extras      : 4 bits,

     co_num_formats      ::=   constant(3),

     co_format_0         ::=   discriminator   : 1 bits,
                               num_sandwiches  : 0 bits,



Price et al.                                                   [Page 66]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     {
       discriminator     ::=   '0',
       num_sandwiches    ::=   static
     },

     co_format_1         ::=   discriminator   : 2 bits,
                               num_sandwiches  : 0 bits,
     {
       discriminator     ::=   '10',
       num_sandwiches    ::=   value(4, 1)
     },

     co_format_2         ::=   discriminator   : 2 bits,
                               num_sandwiches  : 4 bits,
     {
       discriminator     ::=   '11',
       num_sandwiches    ::=   irregular(4)
     },

     default_methods     ::=   ... ,
     {
       num_extras        ::=   value(4,2)
     }
   },


   sandwich_header_6     ::=   multiple_packet_formats,
   {
     uncompressed_format ::=   num_sandwiches  : 4 bits,
                               num_extras      : 4 bits,

     co_num_formats      ::=   constant(3),

     co_format_0         ::=   discriminator   : 1 bits,
                               num_sandwiches  : 0 bits,
     {
       discriminator     ::=   '0',
       num_sandwiches    ::=   static
     },

     co_format_1         ::=   discriminator   : 2 bits,
                               num_sandwiches  : 0 bits,
     {
       discriminator     ::=   '10',
       num_sandwiches    ::=   value(4, 1)
     },

     co_format_2         ::=   discriminator   : 2 bits,
                               num_sandwiches  : 4 bits,
     {
       discriminator     ::=   '11'



Price et al.                                                   [Page 67]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     },

     default_methods     ::=   num_extras      : 0 bits,
                               num_sandwiches  : 4 bits,
     {
       num_extras        ::=   value(4,2),
       num_sandwiches    ::=   irregular(4)
     }
   },


   test_single_format    ::=   single_packet_format,

   { uncompressed_data   ::=   field_1,

     compressed_data     ::=   field_1,

     field_1             ::=   irregular(4)},

   test_inferred_size    ::=   single_packet_format,

   { uncompressed_data   ::=   irregular_field,
                               size_field,

     compressed_data     ::=   irregular_field,

     irregular_field     ::=   irregular(4),

     size_field          ::=   inferred_size(4, -8)},

   test_msn              ::=   counter(16),

   test_offset           ::=   single_packet_format,

   { uncompressed_data   ::=   id      :  4 bits,
                               count   :  4 bits,

     compressed_data     ::=   id      :  4 bits,

     id                  ::=   irregular(4),

     count               ::=   inferred_offset(4),

     { base_field        ::=   expression(uncomp(test_offset.id)),
       offset            ::=   value(4,3)}},

   test_index            ::=   single_packet_format,

   { uncompressed_data   ::=   one,     %  4 bits
                               two,     %  4 bits




Price et al.                                                   [Page 68]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     compressed_data     ::=   two,     %  1 bit

     one                 ::=   value(4,1),

     two                 ::=   index(4,[1,2])},

   test_derived_value ::= single_packet_format,

   { uncompressed_data   ::=   one,

     compressed_data     ::=   two,

     one                 ::=   derived_value,
     {
       field_length      ::=   constant(8),
       field_value       ::=   constant(4)
     },

     two                 ::=   '0'
   },

   test_uncompressible ::= single_packet_format,

   { uncompressed_data   ::=   length,
                               data,

     compressed_data     ::=   data,

     length              ::=   value(4, 1),

     data                ::=
   uncompressible(test_uncompressible.length, 2, 2, 4)},

   test_group            ::=   single_packet_format,

   { uncompressed_data   ::=   one,
                               two,

     compressed_data     ::=   both,

     one                 ::=   derived_value,
     one.field_length    ::=   constant(4),
     one.field_value     ::=   expression(uncomp(test_group.both) mod
   16),

     two                 ::=   derived_value,
     two.field_length    ::=   constant(4),
     two.field_value     ::=   expression(uncomp(test_group.both) //
   16),

     both                ::=   control_field,



Price et al.                                                   [Page 69]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     {
       base_field        ::=   group,
       {
         field_list      ::=   test_group.two,
                               test_group.one
       },
       compressed_method ::=   irregular(8)
     }
   },

   test_ip_checksum      ::=   single_packet_format,

   { uncompressed_data   ::=   version        :  4 bits,
                               header_length  :  4 bits,
                               tos            :  6 bits,
                               ecn            :  2 bits,
                               length         : 16 bits,
                               id             : 16 bits,
                               reserved       :  1 bits,
                               dont_frag      :  1 bits,
                               more_fragments :  1 bits,
                               offset         : 13 bits,
                               ttl            :  8 bits,
                               protocol       :  8 bits,
                               checksum       : 16 bits,
                               src_addr       : 32 bits,
                               dest_addr      : 32 bits,

     compressed_data     ::=   tos            :  6 bits,
                               ecn            :  2 bits,
                               length         : 16 bits,
                               id             : 16 bits,
                               dont_frag      :  1 bits,
                               ttl            :  8 bits,
                               protocol       :  8 bits,
                               src_addr       : 32 bits,
                               dest_addr      : 32 bits,

     version             ::=   value(4, 4),
     header_length       ::=   value(4, 5),
     tos                 ::=   irregular(6),
     ecn                 ::=   irregular(2),
     length              ::=   irregular(16),
     id                  ::=   irregular(16),
     reserved            ::=   value(1, 0),
     dont_frag           ::=   irregular(1),
     more_fragments      ::=   value(1, 0),
     offset              ::=   value(13, 0),
     ttl                 ::=   irregular(8),
     protocol            ::=   irregular(8),
     checksum            ::=   inferred_ip_checksum,



Price et al.                                                   [Page 70]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


     src_addr            ::=   irregular(32),
     dest_addr           ::=   irregular(32)}.


Test Harness - profile_test_harness.pl

   :-
   :- ensure_loaded(defaults).
   :- ensure_loaded(preprocessor).
   % :- ensure_loaded('../profiles/simplified_tcp_example').
   :- ensure_loaded('../profiles/test_profiles').


   %--------------------------------------------------------------------
   %   Test harness
   %--------------------------------------------------------------------

                           ensure_loaded(debug).   compress(U, E) :-
     flag('$doing', _, compression),
     unify_value('$encoding', 0, E),
     uncomp('', U),
     update_context, nl,
     E,
     comp(E, C), comp('', C),
     write('Uncompressed header: '), write(U), nl,
     write('Compressed header:   '), write(C), nl.

   compress(U) :- compress(U, _).

   compress :- compress(_).

   c(_) :- compress.

   decompress(C, E) :-
     flag('$doing', _, decompression),
     unify_value('$encoding', 0, E),
     comp('', C),
     update_context, nl,
     E,
     uncomp(E, U), uncomp('', U),
     write('Uncompressed header: '), write(U), nl,
     write('Compressed header:   '), write(C), nl.

   decompress(T) :- decompress(T, _).

   decompress :- decompress(_).

   d(_) :- decompress.

   % Transfers the updated context to the current context:




Price et al.                                                   [Page 71]

INTERNET-DRAFT                   ROHC-FN                October 27, 2003


   update_context :-
     (
       current_flag(F),
       functor(F, NAME, ARGS),
       (
         ARGS = 3 ->
           ( debug(1) -> write('Updating context: '), write(NAME), nl;
   true ),
           updated_context(NAME, VALUE),
           context(NAME, VALUE),
           flag(F, _, 0)
         ;
         ARGS \= 2 ->
           atom_chars(NAME, [HEAD | _]), HEAD \= '$',
           flag(F, _, 0)
       ),
       fail
     )
     ;
     true.


































Price et al.                                                   [Page 72]


Html markup produced by rfcmarkup 1.108, available from http://tools.ietf.org/tools/rfcmarkup/