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. Present work centers around evaluating and integrating some features from other measured format technologies into EXI (see Appendix E Format Features Under Consideration).

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 9.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.

Terminal symbols that are qualified with a qname permit the use of a wildcard symbol (*) in place of a qname. The terminal symbol SE (*) matches a start element (SE) event with any qname. Similarly, the terminal symbol AT (*) matches an attribute (AT) event with any qname.

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 Distinguishing Bits

[Definition:]   An EXI header starts with Distinguishing Bits part, which is a two bit field used to distinguish EXI documents from text XML documents. The first bit contains the value 1 and the second bit contains the value 0 as follows.

This bit sequence cannot occur as the first two bits of a well-formed XML document and represents the minimum length EXI document prefix required to distinguish EXI documents from XML documents.

XML Processors are expected to consistently reject an EXI stream as early as they read and process the first byte from the stream, since neither of the bit sequences shown above constitutes the first two bits of any well-formed XML documents 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]. Systems that use EXI documents as well as XML documents can look at the Distinguishing Bits to determine whether to interpret a particular stream as XML or EXI.

5.2 EXI Format Version

[Definition:]   The third 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 formation 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.3 EXI Options

[Definition:]  The fourth 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. They are represented as 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.

EXI processors MAY provide external means for applications or users to specify EXI Options when the EXI header is abscent. 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 documents. 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.

The compression option is a Boolean used to increase compactness using additional computational resources. When set to true, the event codes and associated content are compressed according to 8. EXI Compression. Otherwise, the event codes and associated content are represented as a sequence of bit-encoded values.

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. [Definition:]  EXI fragments are analogous in concept to external general parsed entities 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 Section 9.4.2 Built-in 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.

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 schemaID option may be used to identify the schema information used to encode the EXI body. When the schemaID is nil, no schema information was used to encode the EXI body. When the schemaID option is absent (i.e., undefined), no statement is made about the schema information used to encode the EXI body and it is assumed this information is communicated out of band.

The codecMap identifies pluggable CODECs used to encode the EXI body as described in 7.4 Pluggable CODECS.

The blockSize 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.

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

The options field is encoded as an EXI body using the default options specified by the following XML document:

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

6.1 Determining Event Codes

The structure of an EXI stream is described by the EXI grammars, which are formally specified in section 9. 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 EXI compression is not in effect 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.

When the EXI events are subsequently subject to EXI compression, ith part of an event code is encoded using 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 again 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 by n-bit unsigned integer representation in this case is equal to ⌈ n / 8 ⌉.

Regardless of the EXI compression 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 the EXI compression is 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 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 9.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.

EXI processors may report an error if the application attempts to encode events that have been pruned from the grammar or may simply ignore these events.

7.1 Built-in EXI Datatypes Representation

The following sections describe the encoding rules for representing built-in EXI datatypes.

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 datatypes 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
• local-names
• values

The uris and local-names used in qname content items are also encoded using a string table. 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.

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.

7.4 Pluggable CODECS

By default, each typed value in an EXI stream is represented by the associated built-in EXI data type (e.g., seeTable 7-1). However, [Definition:]  EXI processors MAY provide the capability to specify different built-in types or user-defined encoder/decoders (CODECS) for representing specific schema types. This capability is called Pluggable CODECS.

EXI processors that support Pluggable CODECS MAY provide external means to define and install user-defined CODECS, of which EXI processors are free to choose implementation dependent mechanisms. EXI processors MAY also provide means for applications or users to specify alternate built-in types or user-defined CODECS for representing specific schema types, the mechanisms of which are again implementation dependent.

When an EXI processor encodes an EXI stream using Pluggable CODECS, it MUST specify in the EXI header each schema type that is not represented using the default built-in type and the alternate built-in type or user-defined CODEC used for each one unless the whole EXI Options part of the header is omitted. An EXI processor that attempts to decode an EXI stream that specifies a user-defined CODEC in the EXI header that it does not recognize MAY report a warning, but this is not an error. However, when an EXI processor encounters a typed value that was encoded by a user-defined CODEC that it does not support, it MUST report an error.

The EXI options header, when it appears in an EXI stream, MUST include a codecMap element for each schema type that is not represented using the default built-in type. The codecMap element includes two child elements. The QName of the first child element identifies the schema type that is not represented using the default built-in type and the QName of the second child element identifies the alternate built-in type or user-defined CODEC used to represent that type. Built-in types are identified by the type identifiers in Table 7-1.

For example, the following codecMap element indicates all values of type xsd:decimal in the EXI stream are represented using the built-in String type, which has the type ID xsd:string:

    <codecMap xmlns:xsd="http://www.w3.org/2001/XMLSchema">
        <xsd:decimal/>
        <xsd:string/>
    </codecMap>

It is the responsibility of an EXI processor to interface with a particular implementation of built-in types or user-defined CODECs properly. In the example above, an EXI processor may need to provide a string value of the data being processed that is typed as xsd:decimal in order to interface with a built-in String type. In such a case, some EXI processors may have started with a decimal value and such processors may well translate the value into a string before passing the data to the built-in String type while other EXI processors may already have a string value of the data so that it can pass the value directly to the built-in String type without any translation.

As another example, the following codecMap element indicates all values of the used-defined type geo:geometricSurface are represented using the user-defined CODEC geo:geometricInterpolator:

    <codecMap xmlns:geo="http://www.example.com/Geometry">
        <geo:geometricSurface/>
	<geo:geometricInterpolator/>
    </codecMap>

8.1 Blocks

EXI compression partitions the sequence of EXI events into a sequence of one or more non-overlapping blocks. Each block preceding the final block contains the minimum set of consecutive events that have exactly blockSize Attribute (AT) and Character (CH) values, where blockSize is the block size of the EXI stream (see 5.3 EXI Options). The final block contains no more than blockSize Attribute (AT) and Character (CH) values.

8.2 Channels

Events inside each block are multiplexed into channels. The first channel of each block is the structure channel described in Section 8.2.1 Structure Channel. The remaining channels in each block are value channels described in Section 8.2.2 Value Channels. The diagram below presents an exemplary view of the transformation in which events within a block are multiplexed into channels in one way and channels are demultiplexed into events in the other way.

Figure 8-2. Multiplexing EXI events into channels

8.3 Compressed Streams

The channels in a block are further organized into compressed streams. Smaller channels are combined into the same compressed stream, while others are each compressed separately. Below are the rules applied within the scope of a block used to determine the channels to be combined together, the order of the compressed streams and the order amongst the channels that are combined into the same compressed stream.

If the block contains at most 100 values, the block will contain only 1 compressed stream containing the structure channel followed by all of the value channels. The order of the value channels within the compressed stream is defined by the order in which the first value in each channel occurs in the EXI event sequence.

If the block contains more than 100 values, the first compressed stream contains only the structure channel. The second compressed stream contains all value channels that contain less than 100 values. And the remaining compressed streams each contain only one channel, each having more than 100 values. The order of the value channels within the second compressed stream is defined by the order in which the first value in each channel occurs in the EXI event sequence. Similarly, the order of the compressed streams following the second compressed stream in the block is defined by the order in which the first value of the channel inside each compressed stream occurs in the EXI event sequence.

Each compressed stream in a block is stored using the standard DEFLATE Compressed Data Format defined by RFC 1951 [IETF RFC 1951].

9.1 Grammar Notation

9.2 Grammar Event Codes

Each production rule in the EXI grammar includes an event code value that approximates the likelihood the associated production rule will be matched over the other productions with the same left-hand-side non-terminal symbol. Ultimately, the event codes determine the value(s) by which each non-terminal symbol will be represented in the EXI stream.

To understand how a given event code approximates the likelihood a given production will matched, it is useful to visualize the event codes for a set of production rules that have the same non-terminal symbol on the left-hand-side as a tree. For example, the following set of productions:

represents a set of information items that might occur as element content after the start tag. Using the production event codes, we can visualize this set of productions as follows:

Figure 9-1. Event code tree for ElementContent grammar

where the non-terminal symbols are represented by the leaf nodes of the tree and the event code of each production rule that contains a non-terminal symbol defines a path from the root of the tree to the node associated with that symbol. We call this the event code tree for a given set of productions.

An event code tree is similar to a Huffman tree [Huffman Coding] in that shorter paths are generally used for symbols that are considered more likely. However, event code trees are far simpler and less costly to compute and maintain. Event code trees are shallow and contain at most three levels. In addition, the length of each event code in the event code tree is assigned statically without analyzing the data. This classification provides some of the benefits of a Huffman tree without the cost.

9.3 Pruning Unneeded Productions

As discussed in section 6.3 Fidelity Options, applications MAY provide a set of fidelity options to specify the XML features they require. EXI processors MUST use these fidelity options to prune the events that are not required from the grammars, improving compactness and processing efficiency.

For example, the following set of productions represent the set of information items that might occur as element content after the start tag.

If an application sets the fidelity options preserve.comments, preserve.pis and preserve.dtd to false, the productions matching comment (CM), processing instruction (PI) and entity reference (ER) events are pruned from the grammar, producing the following set of productions:

Removing these productions from the grammar tells EXI processors that comments and processing instructions will never occur in the EXI stream, which reduces the entropy of the stream allowing it to be encoded in fewer bits.

Each time a production is removed from a grammar, the event codes of the other productions with the same non-terminal symbol on the left-hand-side MUST be adjusted to keep them contiguous if its removal has left the remaining productions with non-contiguous event codes.

9.4 Built-in XML Grammars

This section describes the built-in XML grammar used by EXI when no additional information is available to describe the contents of the EXI stream. The built-in XML grammar is used when no schema exists, for elements with unrestricted types (e.g., xsd:anyType) and for schema extensions and deviations that are not declared by the schema.

A built-in XML grammar is self-evolving. The built-in grammar continuously reflects the knowledge being learned while processing an EXI stream onto itself in order to keep refining itself for subsequent use of the grammar within the extent of processing a single stream.