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]
