Efficient XML Interchange (EXI) Format 1.0

1.1 History and Design

EXI is the result of extensive work carried out by the W3C's XML Binary Characterization (XBC) and Efficient XML Interchange (EXI) Working Groups. XBC was chartered to investigate the costs and benefits of an alternative form of XML, and formulate a way to objectively evaluate the potential of a substitute format for XML. Based on XBC's recommendations, EXI was chartered, first to measure, evaluate, and compare the performance of various XML technologies (using metrics developed by XBC [XBC Measurement Methodologies]), and then, if it appeared suitable, to formulate a recommendation for a W3C format specification. The measurements results and analyses, are presented elsewhere [EXI Measurements Note]. The format described in this document is the specification so recommended.

The functional requirements of the EXI format are those that were prepared by the XBC WG in their analysis of the desirable properties of a high performance encoding for XML [XBC Properties]. Those properties were derived from a very broad set of use cases also identified by the XBC working group [XBC Use Cases].

The design of the format presented here, is largely based on the results of the measurements carried out by the group to evaluate the performance characteristics (mainly of processing efficiency and compactness) of various existing formats. The EXI format is based on Efficient XML [Efficient XML], including for example the basis heuristic grammar approach, compression algorithm, and resulting entropy encoding.

EXI is compatible with XML at the XML Information Set [XML Information Set] level, rather than at the XML syntax level. This permits it to encapsulate an efficient alternative syntax and grammar for XML, while facilitating at least the potential for minimizing the impact on XML application interoperability.

1.2 Notational Conventions and Terminology

The key words MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL, when they appear EMPHASIZED in this document, are to be interpreted as described in RFC 2119 [IETF RFC 2119]. Other terminology used to describe the EXI format is defined in the body of this specification.

The term event and stream is used throughout this document to denote EXI event and EXI stream respectively unless the words are qualified differently to mean otherwise.

This document specifies an abstract grammar for EXI. In grammar notation, all terminal symbols are represented in plain text and all non-terminal symbols are represented in italics. Grammar productions are represented as follows:

A set of one or more grammar productions that share the same left-hand-side non-terminal symbol are often presented together along with event codes that uniquely identify events among the collocated productions as follows:

Section 8.1 Grammar Notation introduces additional notations for describing productions and event codes in grammars. Those additional notations facilitates concise representation of the EXI grammar system.

[Definition:]   In this document, the term qname is used to denote a QName^XS2. When used to qualify terminal symbols in grammars (see Table 4-1 for notation), to identify built-in element grammars (see 8.4.3 Built-in Element Grammar) and global type grammars (see 8.5.4.1.3 Type Grammars), or to distinguish value channels in EXI compression (see 9.2.2 Value Channels), such uses of qname represent QName values, which are tuples of { uri, local-name }. Otherwise, a qname represents a QName value affixed with a prefix part to make a triplet of { prefix, uri, local-name }, where the absence of prefix is indicated by "" (an empty string). Two qnames are considered equal when they have the same uri and the same local-name to each other regardless of prefix values.

Terminal symbols that are qualified with a qname permit the use of a wildcard symbol (*) in place of or as part of a qname. The forms of terminal symbols involving qname wildcards used in grammars and their definitions are described in the table below.

Several prefixes are used throughout this document to designate certain namespaces. The bindings shown below are assumed, however, any prefixes can be used in practice if they are properly bound to the namespaces.

In describing the layout of an EXI format construct, a pair of square brackets [ ] are used to surround the name of a field to denote that the occurrence of the field is optional in the structure of the part or component that contains the field.

In arithmetic expressions, the notation ⌈x⌉ where x represents a real number denotes the ceiling of x, that is, the smallest integer greater than or equal to x.

5.1 EXI Cookie

[Definition:]   An EXI header MAY start with an EXI Cookie, which is a four byte field that serves to indicate that the stream of which it is a part is an EXI stream. The four byte field consists of four characters " $ " , " E ", " X " and " I " in that order, each represented as an ASCII octet, as follows.

This four byte sequence is particular to EXI and specific enough to distinguish EXI streams from a broad range of data types currently used on the Web. While the EXI cookie is optional, its use is RECOMMENDED in the EXI header when the EXI stream is exchanged in a context where longer, more solid content-based datatype identification is desired than what is provided by Distinguishing Bits whose role is rather narrowly focused on distinguishing EXI streams from XML documents.

5.2 Distinguishing Bits

[Definition:]   The second part in the EXI header is the Distinguishing Bits, which is a two bit field of which the first bit contains the value 1 and the second bit contains the value 0, as follows.

Unlike the optional EXI cookie that MAY occur to precede this field, the presence of Distinguishing Bits is REQUIRED in the EXI header. It is used to distinguish EXI streams from text XML documents in the absence of an EXI cookie. This two bit sequence is the minimum that suffices to distinguish EXI streams from XML documents since it is the minimum length bit pattern that cannot occur as the first two bits of a well-formed XML document represented in any one of the conventional character encodings, such as UTF-8, UTF-16, UCS-2, UCS-4, EBCDIC, ISO 8859, Shift-JIS and EUC, according to XML 1.0 [XML 1.0]. Therefore, XML Processors are expected to reject an EXI stream as early as they read and process the first byte from the stream.

Systems that use EXI streams as well as XML documents can reliably look at the Distinguishing Bits to determine whether to interpret a particular stream as XML or EXI.

5.3 EXI Format Version

[Definition:]   The fourth part in the EXI header is the EXI Format Version, which identifies the version of the EXI format being used. EXI format version numbers are integers. Each version of the EXI Format Specification specifies the corresponding EXI format version number to be used by conforming implementations. The EXI format version number that corresponds with this version of the EXI format specification is 0 (zero).

The first bit of the version field indicates whether the version is a preview or final version of the EXI format. A value of 0 indicates this is a final version and a value of 1 indicates this is a preview version. Final versions correspond to final, approved versions of the EXI format specification. An EXI processor that implements a final version of the EXI format specification is REQUIRED to process EXI streams that have a version field with its first bit set to 0 followed by a version number that corresponds to the version of the EXI specification the processor implements. Preview versions of the EXI format are useful for gaining implementation and deployment experience prior to finalizing a particular version of the EXI format. While preview versions may match drafts of this specification, they are not governed by this specification and the behaviour of EXI processors encountering preview versions of the EXI format is implementation dependent. Implementers are free to coordinate to achieve interoperability between different preview versions of the EXI format.

Following the first bit of the version is a sequence of one or more 4-bit unsigned integers representing the version number. The version number is determined by summing this sequence of 4-bit unsigned values. The sequence is terminated by any 4-bit unsigned integer with a value in the range 0-14. As such, the first 15 version numbers are represented by 4 bits, the next 15 are represented by 8 bits, etc.

Given an EXI stream with its stream cursor positioned just past the first bit of the EXI format version field, the EXI format version number can be computed by going through the following steps with version number initially set to 1.

1. Read next 4 bits as an unsigned integer value.
2. Add the value that was just read to the version number.
3. If the value is 15, go to step 1, otherwise (i.e. the value being in the range of 0-14), use the current value of the version number as the EXI version number.

The following are example EXI format version numbers.

EXI processors conforming with the final version of this specification MUST use the 5-bit value 0 0000 as the version number.

5.4 EXI Options

[Definition:]  The fifth part of the EXI header is the EXI Options, which provides a way to specify the options used to encode the body of the EXI stream. [Definition:]   The EXI Options are represented as an EXI Options document, which is an XML document encoded using the EXI format described in this specification. This results in a very compact header format that can be read and written with very little additional software.

The presence of EXI Options in its entirety is optional in EXI header, and it is predicated on the value of the presence bit that follows the Distinguishing Bits. When EXI Options are present in the header, an EXI Processor MUST observe the specified options to process the EXI stream that follows. Otherwise, an EXI Procesor may obtain the EXI options using another mechanism. There are no fallback option values provided by this specification for use in the absence of the whole EXI Options part.

EXI processors MAY provide external means for applications or users to specify EXI Options when the EXI header is absent. Such EXI processors are typically used in controlled systems where the knowledge about the effective EXI Options is shared prior to the exchange of EXI streams . The mechanism to communicate out-of-bound EXI Options and their representation used in such systems are implementation dependent.

The following table describes the EXI options specified in the options field.

Appendix C XML Schema for EXI Options Header provides an XML Schema describing the EXI Options document. This schema is designed to produce smaller headers for option combinations used when compactness is critical.

The EXI Options document is encoded as an EXI body informed by the above mentioned schema using the default options specified by the following XML document. An EXI Options document consists only of EXI body, and MUST NOT start with an EXI header.

  <header xmlns="http://www.w3.org/2007/07/exi">
    <strict/>
  </header>

[Definition:]  The alignment option is used to control the alignment of event codes and content items. The value is one of bit-packed, byte-alignment or pre-compression, of which bit-packed is the default value assumed when the "alignment" element is absent in the EXI Options document. When the value of compression option is set to true, the way event codes and associated contents are represented is governed by the rule specified in 9. EXI Compression instead of the alignment option value, thus the compression option value "true" effectively rescinds the effect of an alignment option value.

[Definition:]  Alignment option value bit-packed indicates that the the event codes and associated content are packed in bits without any paddings in-between.

[Definition:]  Alignment option value byte-alignment indicates that the event codes and associated content are aligned on byte boundaries. While byte-alignment generally results in EXI streams of larger sizes compared with their bit-packed equivalents, byte-alignment may provide a help in some use cases that involve frequent copying of large arrays of scalar data directly out of the stream. It can also make it possible to work with data in-place and can make it easier to debug encoded data by allowing items on aligned boundaries to be easily located in the stream.

[Definition:]  Alignment option value pre-compression alignment indicates that all steps involved in compression (see section 9. EXI Compression) are to be done with the exception of the final step of applying the DEFLATE algorithm. The primary use case of pre-compression is to avoid a duplicate compression step when compression capability is built into the transport protocol. In this case, pre-compression just prepares the stream for later compression.

[Definition:]  The compression option is a Boolean used to increase compactness using additional computational resources. The default value "false" is assumed when the "compression" element is absent in the EXI Options document. When set to true, the event codes and associated content are compressed according to 9. EXI Compression regardless of the alignment option value.

[Definition:]  The strict option is a Boolean used to increase compactness by using a strict interpretation of the schemas and omitting preservation of certain items, such as comments, processing instructions and namespace prefixes. The default value "false" is assumed when the "strict" element is absent in the EXI Options document. When set to true, NS, CM, PI, ER and SC events are pruned from EXI grammars, and schema-informed element and type grammars are restricted to only permit items declared in the schemas. The "strict" element MUST NOT appear in an EXI options document when the "preserve" element is present in the same options document.

[Definition:]  The fragment option is a Boolean that indicates whether the EXI body is an EXI document or an EXI fragment. When set to true, the EXI body is an EXI fragment. Otherwise, the EXI body is an EXI document. Unlike EXI documents, EXI fragments are capable of representing multiple elements at the root level. They are analogous in concept to external general parsed entities^XML in XML in that they consist of a sequence of elements, processing instructions and comments in containers of their own that are physically separate from the documents in which they are to be used. An EXI fragment is formally defined in terms of its grammar in Sections 8.4.2 Built-in Fragment Grammar and 8.5.2 Schema-informed Fragment Grammar. The XML Information Set an EXI stream is mapped onto contains a document information item if the stream represents an EXI document, otherwise, the XML Information Set does not have a document information item if the stream represents an EXI fragment. The order among elements, processing instructions and comments that appear at the root in an EXI fragment is deemed significant and MUST be preserved by EXI processors.

[Definition:]  The preserve option is a set of Booleans that can be set independently to control whether certain information items are preserved in the EXI stream. 6.3 Fidelity Options describes the set of information items effected by the preserve option. The "preserve" element MUST NOT appear in an EXI options document when the "strict" element is present in the same options document.

[Definition:]  The selfContained option is a Boolean used to enable the use of self contained elements in the EXI stream. Self contained elements may be read independently from the rest of the EXI body, allowing them to be indexed for random access. The "selfContained" element MUST NOT appear in an EXI options document when the "compression" or "pre-compression" elements are present in the same options document.

[Definition:]  The schemaID option may be used to identify the schema information used when encoding the EXI body. When the "schemaID" element in the EXI options document contains the xsi:nil attribute, no schema information was used when encoding the EXI body. When the value of the "schemaID" element is empty, no user defined schema information was used when encoding the EXI body; however, the built-in XML Schema types may have been used with the xsi:type attribute to specify element types. When the schemaID option is absent (i.e., undefined), no statement is made about the schema information used to encode the EXI body and this information MUST be communicated out of band. This specification does not dictate the syntax or semantics of other values specified in this field. An example schemaID scheme is the use of URI that is apt for globally identifying schema resources on the Web. The parties involved in the exchange are free to agree on the scheme of schemaID field that is appropriate for their use to uniquely identify the schema information.

[Definition:]  The datatypeRepresentationMap option, represented by a "datatypeRepresentationMap" element, identifies datatype representations used to encode values in the EXI body as described in 7.4 Datatype Representation Map .

[Definition:]  The blockSize option specifies the block size used for EXI compression. When the blockSize option is absent, the default blocksize of 1,000,000 is used. The default blockSize is intentionally large but can be reduced for processing large documents on devices with limited memory.

[Definition:]   The valueMaxLength option specifies the maximum length of string values representing value content items to be considered for addition to the string table. When the valueMaxLength option is absent, the maximum length is unbounded. String values representing value content items that have length larger than the valueMaxLength option value are excluded from further consideration on account of valuePartitionCapacity for addition to the string table.

[Definition:]   The valuePartitionCapacity option specifies the total capacity of the global and all local value partitions of a string table, where the measurement unit of the capacity is the number of unique enitiries. When the valuePartitionCapacity option is absent, an unbounded capacity is assumed. A string representing a value content item that has length smaller than or equal to the valueMaxLength option value and is not found in the value partitions at the time of the value occurrence is to be added into the string table only when doing so would not cause the number of unique values in value partitions to exceed the capacity. The use of valuePartitionCapacity option value and the way the number of unique values are counted for value partitions are described in 7.3.1 String Table Partitions.

6.1 Determining Event Codes

The structure of an EXI stream is described by the EXI grammars, which are formally specified in section 8. EXI Grammars. Each grammar defines which events are permitted to occur at any given point in the EXI stream and provides a pre-assigned event code for each event.

For example, the grammar productions below describe the events that can occur in a schema-informed EXI stream after the Start-Document (SD) event provided there are four global elements defined in the schema and provide an event code for each event:

At the point in an EXI stream where the above grammar productions are in effect, the event code of Start Element "A" (i.e. SE("A")) is 0. The event code of a DOCTYPE (DT) event at this point in the stream is 4.1, and so on.

6.2 Representing Event Codes

Each event code is represented by a sequence of 1 to 3 parts that uniquely identify an event. Event code parts are encoded in order starting with the first part followed by subsequent parts.

When the value of compression option is false, and bit-packed alignment option is used for the current processing of the stream, the ith part of an event code is encoded using the minimum number of bits required to distinguish it from the ith part of the other sibling event codes in the current grammar. Specifically, the ith part of an event code is encoded as an n-bit unsigned integer (7.1.9 n-bit Unsigned Integer), of which n is ⌈ log ₂ m ⌉ where m is the number of distinct values used as the ith part of its own and all its sibling event codes in the current grammar. Two event codes are siblings at the ith part if and only if they share the same values in all preceding parts. All event codes are siblings at the first part.

On the other hand, when the value of compression option is true, or either byte-alignment or pre-compression alignment option is used, the ith part of an event code is encoded using the minimum number of bytes instead of bits required to distinguish it from the ith part of the other sibling event codes in the current grammar. Each part is encoded as an n-bit unsigned integer (7.1.9 n-bit Unsigned Integer), of which n is ⌈ log ₂ m ⌉ where m is the number of distinct values used as the ith part of its own and all its sibling event codes in the current grammar. The number of bytes used for the n-bit unsigned integer representation in this case is equal to ⌈ n / 8 ⌉.

Regardless of the values of compression option and alignment option, if there is only one distinct value for a given part, the part is omitted (i.e., encoded in log ₂ 1 = 0 bits = 0 bytes).

For example, the nine event codes shown in the DocContent grammar above have a value ranging from 0 to 4 for their first part. There are five distinct values needed to identify the first part of these event codes. Therefore, when EXI compression and alignment are not in effect, the first part can be encoded in ⌈ log ₂ 5 ⌉ = 3 bits. In the same fashion, the number of bits used for encoding second and third part (if present) are calculated as ⌈ log ₂ 4 ⌉ = 2 bits and ⌈ log ₂ 2 ⌉ = 1 bits, respectively. On the other hand, when EXI compression or alignment is in effect, the number of bytes used for each part is ⌈ 3 / 8 ⌉ = 1 bytes for the first part, ⌈ 2 / 8 ⌉ = 1 bytes for the second part and ⌈ 1 / 8 ⌉ = 1 bytes for the third part.

The table below illustrates how the event codes of each event in the DocContent grammar above is encoded.

6.3 Fidelity Options

Some XML applications do not require the entire XML feature set and would prefer to eliminate the overhead associated with unused features. For example, the SOAP 1.2 specification [SOAP 1.2] prohibits the use of XML processing-instructions. In addition, there are many data-exchange use cases that do not require XML comments or DTDs.

Applications can use a set of fidelity options to specify the XML features they require. As specified in section 8.3 Pruning Unneeded Productions, EXI processors MUST use these fidelity options to prune the events that are not required from the grammars, improving compactness and processing efficiency.

The table below lists the fidelity options supported by this version of the EXI specification and describes the effect setting these options has on the EXI stream.

7.1 Built-in EXI Datatype Representations

The following sections describe the encoding rules of built-in EXI datatype representations for representing values in EXI streams.

7.1.10 String

Values of type String are represented as a length prefixed sequence of characters. The length indicates the number of characters in the string and is represented as an Unsigned Integer (see 7.1.6 Unsigned Integer). If a restricted character set is defined for the string (see 7.1.10.1 Restricted Character Sets), each character is represented as an n-bit Unsigned Integer (see 7.1.9 n-bit Unsigned Integer). Otherwise, each character is represented by its UCS [ISO/IEC 10646] code point encoded as an Unsigned Integer (see 7.1.6 Unsigned Integer).

EXI uses a string table to represent certain content items more efficiently. Section 7.3 String Table describes the string table and how it is applied to different content items.

7.1.10.1 Restricted Character Sets

If a string value is associated with a schema datatype and one or more of the datatypes in its datatype hierarchy has one or more pattern facets, there may be a restricted character set defined for the string value. The following steps are used to determine the restricted character set, if any, defined for a given string value associated with such a schema datatype.

First, determine the character set for each datatype in the datatype hierarchy of the string value that has one or more pattern facets according to section E Deriving Character Sets from XML Schema Regular Expressions. For each datatype with more than one pattern facet, compute the restricted character set based on the union of the regular expressions specified by its pattern facets. If the restricted character set for a datatype contains at least 255 characters or contains non-BMP characters, the character set of the datatype is not restricted and can be omitted from further consideration.

Then, compute the restricted character set for the string value as the intersection of all the character sets computed above. If the resulting character set contains less than 255 characters, the string value has a restricted character set and each character is represented using an n-bit Unsigned Integer (see 7.1.9 n-bit Unsigned Integer), where n is log₂(N + 1) and N is the number of characters in the restricted character set.

The characters in the restricted character set are sorted by UCS [ISO/IEC 10646] code point and represented by integer values in the range (0 ... N-1) according to their ordinal position in the set. Characters that are not in this set are represented by the integer N followed by the UCS code point of the character represented as an Unsigned Integer.

The figure below illustrates an overview of the process for determining and using restricted character sets described in this section.

Figure 7-1. String Processing Model

7.2 Enumerations

Values of enumerated types are encoded as n-bit Unsigned Integers (7.1.9 n-bit Unsigned Integer) where n = ⌈ log ₂ m ⌉ and m is the number of items in the enumerated type. The value assigned to each item corresponds to its ordinal position in the enumeration in schema-order starting with position zero (0).

Exceptions are for schema types derived from others by union and their subtypes, QName or Notation and types derived therefrom by restriction. The values of such types are processed by their respective built-in EXI datatype representations instead of being represented as enumerations.

7.3 String Table

EXI uses a string table to assign "compact identifiers" to some string values. Occurrences of string values found in the string table are represented using the associated compact identifier rather than encoding the entire "string literal". The string table is initially pre-populated with string values that are likely to occur in certain contexts and is dynamically expanded to include additional string values encountered in the document. The following content items are encoded using a string table:

• uris
• prefixes
• uri and local-name in qnames
• values

When a string value is found in the string table, the value is encoded using the compact identifier and no changes are made to the string table as a result. When a string value is not found in the string table, its string literal is encoded as a String without using a compact identifier, only after which the string table is augmented by including the string value with an assigned compact identifier unless the string value represents a value content item and fails to satisfy the criteria in effect by virtue of valuePartitionCapacity and valueMaxLength options .

The string table is divided into partitions and each partition is optimized for more frequent use of either compact identifiers or string literals depending on the purpose of the partition. Section 7.3.1 String Table Partitions describes how EXI string table is partitioned. Section 7.3.2 Partitions Optimized for Frequent use of Compact Identifiers describes how string values are encoded when the associated partition is optimized for more frequent use of compact identifiers. Section 7.3.3 Partitions Optimized for Frequent use of String Literals describes how string values are encoded when the associated partition is optimized for more frequent use of string literals.

The life cycle of a string table spans the processing of a single EXI stream. String tables are not represented in an EXI stream or exchanged between EXI processors. A string table cannot be reused across multiple EXI streams; therefore, EXI processors MUST use a string table that is equivalent to the one that would have been newly created and pre-populated with initial values for processing each EXI stream.