W3C

Efficient XML Interchange (EXI) Format 1.0

W3C Working Draft 16 July 2007

This version:
http://www.w3.org/TR/2007/WD-exi-20070716/
Latest version:
http://www.w3.org/TR/exi/
Previous version:
None (First Public Working Draft)
Editors:
John Schneider, AgileDelta, Inc.
Takuki Kamiya, Fujitsu Laboratories of America, Inc.

This document is also available in these non-normative formats: XML.


Abstract

This document is the specification of the Efficient XML Interchange (EXI) format. EXI is a very compact representation for the eXtensible Markup Language (XML) Information Set that is intended to simultaneously optimize performance and the utilization of computational resources. The EXI format uses a hybrid approach drawn from the information and formal language theories, plus practical techniques verified by measurements, for entropy encoding XML information. Using a relatively simple algorithm, which is amenable to fast and compact implementation, and a small set of data types, it reliably produces efficient encodings of XML event streams. The event production system and format definition of EXI are presented.

Status of this Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This is the first Public Working Draft of the Efficient XML Interchange (EXI) Format 1.0 specification and is intended for review by W3C members and other interested parties. It has been developed by the Efficient XML Interchange (EXI) Working Group, which is part of the Extensible Markup Language (XML) Activity.

The features and algorithms described in the normative portion of the document are specified in enough detail to be adequate for early implementation experiments, except for Section 9.5.3 Schema-informed Element Grammar, which currently describes this feature by example. Other features the group is considering are found in the non-normative Appendix E Format Features Under Consideration, for which only brief descriptions are provided, and should probably not yet be considered for implementation.

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

Comments on this document are invited and are to be sent to the public public-exi@w3.org mailing list (public archive).

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Table of Contents

1. Introduction
    1.1 History and Design
    1.2 Notational Conventions and Terminology
2. Design Principles
3. Basic Concepts
4. EXI Streams
5. EXI Header
    5.1 Distinguishing Bits
    5.2 EXI Format Version
    5.3 EXI Options
6. Encoding EXI Streams
    6.1 Determining Event Codes
    6.2 Representing Event Codes
    6.3 Fidelity Options
7. Representing Event Content
    7.1 Built-in EXI Datatypes Representation
        7.1.1 Binary
        7.1.2 Boolean
        7.1.3 Decimal
        7.1.4 Float
        7.1.5 Integer
        7.1.6 Unsigned Integer
        7.1.7 QName
        7.1.8 Date-Time
        7.1.9 n-bit Unsigned Integer
        7.1.10 String
        7.1.11 List
    7.2 Enumerations
    7.3 String Table
        7.3.1 String Table Partitions
        7.3.2 Partitions Optimized for Frequent use of Compact Identifiers
        7.3.3 Partitions Optimized for Frequent use of String Literals
    7.4 Pluggable CODECS
8. EXI Compression
    8.1 Blocks
    8.2 Channels
        8.2.1 Structure Channel
        8.2.2 Value Channels
    8.3 Compressed Streams
9. EXI Grammars
    9.1 Grammar Notation
        9.1.1 Fixed Event Codes
        9.1.2 Variable Event Codes
    9.2 Grammar Event Codes
    9.3 Pruning Unneeded Productions
    9.4 Built-in XML Grammars
        9.4.1 Built-in Document Grammar
        9.4.2 Built-in Fragment Grammar
        9.4.3 Built-in Element Grammar
    9.5 Schema-informed Grammars
        9.5.1 Schema-informed Document Grammar
        9.5.2 Schema-informed Fragment Grammar
        9.5.3 Schema-informed Element Grammar
            9.5.3.1 Element Content Models
            9.5.3.2 Undeclared Productions
            9.5.3.3 Combined Grammar
10. Conformance

Appendices

A References
    A.1 Normative References
    A.2 Other References
B Infoset Mapping
    B.1 Document Information Item
    B.2 Element Information Items
    B.3 Attribute Information Item
    B.4 Processing Instruction Information Item
    B.5 Unexpanded Entity Reference Information item
    B.6 Character Information item
    B.7 Comment Information item
    B.8 Document Type Declaration Information item
    B.9 Unparsed Entity Information Item
    B.10 Notation Information Item
    B.11 Namespace Information Item
C XML Schema for EXI Options Header
D Initial Entries in String Table Partitions
    D.1 Initial Entries in Uri Partition
    D.2 Initial Entries in Prefix Partitions
    D.3 Initial Entries in Local-Name Partitions
E Format Features Under Consideration (Non-Normative)
    E.1 Bounded Integers
    E.2 Strict Schemas
    E.3 Restricted Character Sets
    E.4 IEEE Floats
    E.5 Bounded Tables
    E.6 Grammar Coalescence
    E.7 Byte-Aligned Mode
    E.8 Indexed Elements
F Example Encoding (Non-Normative)
G Acknowledgements (Non-Normative)


1. Introduction

The Efficient XML Interchange (EXI) format is a very compact, high performance XML representation that was designed to work well for a broad range of applications. It simultaneously improves performance and significantly reduces bandwidth requirements without compromising efficient use of other resources such as battery life, code size, processing power, and memory.

EXI uses a grammar-driven approach that achieves very efficient encodings using a straightforward encoding algorithm and a small set of data types. Consequently, EXI processors are relatively simple and can be implemented on devices with limited capacity.

EXI is schema "informed", meaning that it can utilize available schema information to improve compactness and performance, but does not depend on accurate, complete or current schemas to work. It supports arbitrary schema extensions and deviations and also works very effectively with partial schemas or in the absence of any schema. The format itself also does not depend on any particular schema language, or format, for schema information.

[Definition:]  A program module called an EXI processor, whether it is part of a software or a hardware, is used by application programs to encode their structured data into EXI streams and/or to decode EXI streams to make the structured data accessible to them. This document not only specifies the EXI format, but also defines errors that EXI processors are required to detect and behave upon.

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:

LeftHandSide :   Event  NonTerminal

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:

LeftHandSide :
Event 1  NonTerminal 1EventCode1
Event 2  NonTerminal 2EventCode2
Event 3  NonTerminal 3EventCode3
...
Event n  NonTerminal nEventCoden

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.

PrefixNamespace Name
exi           http://www.w3.org/2007/07/exi
xml           http://www.w3.org/XML/1998/namespace
xsd           http://www.w3.org/2001/XMLSchema
xsi           http://www.w3.org/2001/XMLSchema-instance

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.

2. Design Principles

The following design principles were used to guide the development of EXI and encourage consistent design decisions. They are listed here to provide insight into the EXI design rationale and to anchor discussions on desirable EXI traits.

General:

One of primary objectives of EXI is to maximize the number of systems, devices and applications that can communicate using XML data. Specialized approaches optimized for specific use cases should be avoided.

Minimal:

To reach the broadest set of small, mobile and embedded applications, simple, elegant approaches are preferred to large, analytical or complex ones.

Efficient:

EXI must be competitive with hand-optimized binary formats so it can be used by applications that require this level of efficiency.

Flexible:

EXI must deal flexibly and efficiently with documents that contain arbitrary schema extensions or deviate from their schema. Documents that contain schema deviations should not cause encoding to fail.

Interoperable:

EXI must integrate well with existing XML technologies, minimizing the changes required to those technologies. It must be compatible with the XML Information Set [XML Information Set], without significant subsetting or supersetting, in order to maintain interoperability with existing and prospective XML specifications.

3. Basic Concepts

EXI achieves broad generality, flexibility, and performance, by unifying concepts from formal language theory and information theory into a single, relatively simple algorithm. The algorithm uses a grammar to determine what is likely to occur at any given point in an XML document and encodes the most likely alternatives in fewer bits. The fully generalized algorithm works for any language that can be described by a grammar (e.g., XML, Java, HTTP, etc.); however, EXI is optimized specifically for XML languages.

The built-in EXI grammar accepts any XML document or fragment and may be augmented with productions derived from XML Schemas [XML Schema Structures][XML Schema Datatypes], RELAX NG schemas [ISO/IEC 19757-2:2003], DTDs [XML 1.0] or other sources of information about what is likely to occur in a set of XML documents. The EXI encoder uses the grammar to map a stream of XML information items onto a smaller, lower entropy, stream of events.

The encoder then represents the stream of events using a set of simple variable length codes called event codes. Event codes are similar to Huffman codes [Huffman Coding], but are much simpler to compute and maintain. They are encoded directly as a sequence of values, or if additional compression is desired, they are passed to the EXI compression algorithm, which replaces frequently occurring event patterns to further reduce size.

When schemas are used, EXI also supports a user-customizable set of typed encodings for efficiently encoding typed values.

4. EXI Streams

[Definition:]  An EXI stream is an EXI header followed by an EXI stream body. It is the EXI stream body that carries the content of the document, while the EXI header amongst its roles communicates the options that were used for encoding the EXI stream body. Section 5. EXI Header describes the EXI header. Values in an EXI stream are packed into bytes most significant bit first.

Applications that use EXI streams embedded in a container data format that discerns it is an EXI stream, dictates the EXI format version and the EXI Options used for its encoding, may with to omit the EXI header. Although an EXI Body is not a valid EXI stream, EXI processors MAY provide a capability to process an EXI stream body independent of an EXI stream.

[Definition:]  The building block of an EXI stream body is an EXI event. An EXI stream body consists of a sequence of EXI events representing an EXI document or an EXI fragment.

The EXI events permitted at any given position in an EXI stream are determined by the EXI grammar. The events occur in a well-formed manner with matching start element and end element events in the same fashion as XML. The EXI grammar incorporates knowledge of the XML grammar and may be augmented and refined using schema information and fidelity options. EXI grammar is formally specified in section 9. EXI Grammars.

The following table summarizes the EXI events and associated content that occur in an EXI stream. In addition, the table includes the grammar notation used to represent each event in this specification. Each event in an EXI stream participates in a mapping system that relates events to XML Information Items so that an EXI document as a whole serves to represent an XML Information Set. The table shows XML Information Items relevant to each EXI event type. Appendix B Infoset Mapping describes the mapping system in detail.

Table 4-1. EXI event types
EXI Event TypeContentGrammar NotationInformation Item
Start Document SDB.1 Document Information Item
End Document ED
Start Element  SE ( qname )B.2 Element Information Items
qnameSE ( * )
End Element EE
AttributevalueAT ( qname )B.3 Attribute Information Item
qname, valueAT ( * )
CharactersvalueCHB.6 Character Information item
Namespace Declaration prefix, uri NSB.11 Namespace Information Item
Comment textCMB.7 Comment Information item
Processing Instruction name, textPIB.4 Processing Instruction Information Item
DOCTYPE name, public, system, textDTB.8 Document Type Declaration Information item
Entity Reference nameERB.5 Unexpanded Entity Reference Information item

Section 6. Encoding EXI Streams describes the algorithm used to encode events in the EXI stream. As indicated in the table above, there are some event types that carry content with their event instances while other event types function as markers without content. A grammar production may match a specific Element or Attribute by qname or match any Element or Attribute using wildcard notation. When a grammar matches an Element or Attribute by qname, the qname is not part of the content. When a grammar matches an Element or Attribute using wild notation, the qname is part of the content.

Each item in the event content has a data type associated with it as shown in the following table. The content of each event, if any, is encoded as a sequence of items each of which being encoded according to its data type in order starting with the first item followed by subsequent items.

Table 4-2. Data types of event content items
Content itemUsed inType
namePI, DT, ER 7.1.10 String
prefixNS 7.1.10 String
publicDT 7.1.10 String
qnameSE, AT 7.1.7 QName
systemDT 7.1.10 String
textCM, PI 7.1.10 String
uriNS 7.1.10 String
valueCH, ATAccording to the schema type (see 7. Representing Event Content) if any is in effect and the preserve.lexicalValues option is set to false, otherwise 7.1.10 String

Content items other than value have their inherent, fixed data types independent of their uses. The data type that governs each occurrence of the value item depends on the schema type if any that is in effect for the value in question. The type xsd:anySimpleType is used for values that do not have an associated schema-type, are schema-invalid, or occur in mixed content. Section 7. Representing Event Content describes how each of the types listed above are encoded in an EXI stream.

5. EXI Header

Each EXI stream begins with an EXI header. The EXI header distinguishes EXI documents from text XML documents, identifies the version of the EXI format being used, and can specify the options used to encode the body of the EXI stream. The EXI header has the following structure:

Distinguishing Bits
Presence Bit
for EXI Options
EXI Format Version[EXI Options][Padding Bits]

EXI Options field within an EXI header is optional where its presence is indicated by the value of the presence bit that follows Distinguishing Bits. The presence and absence is indicated by the value 1 and 0, respectively.

When the compression of the EXI stream is turned on dictated by EXI options, padding bits of minumum length required to make the whole length of the header byte-aligned are added at the end of the header.

The following sections describe the remaining three parts of the header.

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.

10

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.

Editorial note 
The distinguishing bits are sufficient to distinguish EXI streams from a reasonably broad range of popular content types that occur on the web. However, the introduction of an optional, larger set of bits for distinguishing EXI streams from any content type is also under consideration.

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.

Example 5-1. EXI Format Version Examples
EXI Format Version FieldDescription
  1 0000  Preview version 1
  0 0000  Final version 1
  0 1110  Final version 15
  0 1111 0000  Final version 16
  0 1111 0001  Final version 17

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.

Table 5-1. EXI Options in Options Field
EXI OptionDescription
compressionEXI compression is used to achieve better compactness
fragmentBody is encoded as an EXI fragment instead of an EXI document
preserveSpecifies whether comments, pis, etc. are preserved
schemaIDIdentify the schema information, if any, used to encode the body
codecMapIdentify pluggable CODECs used to encode body
blockSizeSpecifies the block size used for EXI compression
[user defined]User defined headers may be added

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 options used for encoding the options field
  <header xmlns="http://www.w3.org/2007/07/exi">
  </header>

6. Encoding EXI Streams

The rules for encoding a series of events as an EXI stream are very simple and are driven by a declarative set of grammars that describes the structure of an EXI stream. Every event in the stream is encoded using the same set of encoding rules, which are summarized as follows:

  1. Get the next event to be encoded
  2. If fidelity options indicate this event type is not processed, go to step 1
  3. Use the grammars to determine the event code of the event
  4. Encode the event code followed by the event content
  5. Evaluate the grammar production matched by the event
  6. Repeat until the End Document (ED) event is encoded

Namespace (NS) and attribute (AT) events are encoded in a specific order following the associated start element (SE) event. Namespace (NS) events are encoded first followed by the AT(xsi:type) event if present, followed by the AT(xsi:nil) event if present, followed by the rest of the attribute (AT) events. When schema-informed grammars are used for processing an element, attribute events occur in lexical order in the stream sorted first by qname localName then by qname uri. Otherwise, when built-in element grammars are used, attribute events can occur in any order. Namespace (NS) events can occur in any order regardless of the grammars used for processing the associated element.

EXI uses the same simple procedure described above, to encode well-formed documents, document fragments, schema-valid information items, schema-invalid information items, information items partially described by schemas and information items with no schema at all. Only the grammars that describe these items differ. For example, an element with no schema information is encoded according to the XML grammar defined by the XML specification, while an element with schema information is encoded according to the more specific grammar defined by that schema.

[Definition:]  An event code is a sequence of 1 to 3 non-negative integers called parts. Each production in a grammar has an event code that distinguishes its event from that of other productions that share the same left-hand-side non-terminal symbol.

Section 6.1 Determining Event Codes describes in detail how the grammar is used to determine the event code of an event. Section 6.2 Representing Event Codes describes in detail how event codes are represented as bits. Section 6.3 Fidelity Options describes available fidelity options and how they effect the EXI stream. Section 7. Representing Event Content describes how the typed event contents are represented as bits.

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:

Example 6-1. Example productions with event codes
SyntaxEvent Code
DocContent
SE ("A") DocEnd0
SE ("B") DocEnd1
SE ("C") DocEnd2
SE ("D") DocEnd3
SE (*) DocEnd4.0
DT DocContent4.1
CH DocContent4.2
CM DocContent4.3.0
PI DocContent4.3.1

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 2 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 2 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 2 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 2 5 ⌉ = 3 bits. In the same fashion, the number of bits used for encoding second and third part (if present) are calculated as ⌈ log 2 4 ⌉ = 2 bits and ⌈ log 2 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.

Example 6-2. Example event code encoding

Table 6-1. Example event code encoding when EXI compression is not in effect
EventPart valuesEvent Code Encoding# bits
SE ("A")0  0003
SE ("B")1  0013
SE ("C")2  0103
SE ("D")3  0113
SE (*)40 100  005
DT41 100  015
CH42 100  105
CM430100  11  06
PI431100  11  16
# distinct values ( m)542  
# bits per part
  ⌈ log 2 m
321  

Table 6-2. Example event code encoding when EXI compression is in effect
EventPart valuesEvent Code Encoding# bytes
SE ("A")0  000000001
SE ("B")1  000000011
SE ("C")2  000000101
SE ("D")3  000000111
SE (*)40 00000100  000000002
DT41 00000100  000000012
CH42 00000100  000000102
CM43000000100  00000011  000000003
PI43100000100  00000011  000000013
# distinct values (m)542  
# bytes per part
  ⌈ (log 2 m) / 8 ⌉
111  

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.

Table 6-3. Fidelity options
Fidelity optionEffect
Preserve.commentsCM events are preserved
Preserve.pisPI events are preserved
Preserve.dtdDOCTYPE and ER events are preserved
Preserve.prefixesNS events and namespace prefixes are preserved
Preserve.lexicalValuesLexical form of element and attribute values is preserved

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. Representing Event Content

The content of each event in an EXI body is represented according to its type (see Table 4-2). In the absence of external type information or when the preserve.lexicalValues option is set to true, all attribute and character values are typed as String.

[Definition:]  EXI defines a minimal set of data types called Built-in EXI datatypes that define how values are represented in EXI streams as described in 7.1 Built-in EXI Datatypes Representation. The following table lists the built-in EXI datatypes, associated type identifiers and the XML Schema Language [XML Schema Datatypes] built-in types each is used to represent by default.

Table 7-1. Built-in EXI Datatypes
Built-in EXI DatatypeEXI Datatype IDXML Schema Types
Binaryxsd:base64Binarybase64Binary
xsd:hexBinaryhexBinary
Booleanxsd:booleanboolean
Date-Timexsd:dateTimedateTime, time, date, gYearMonth, gYear, gMonthDay, gDay, gMonth
Decimalxsd:decimaldecimal
Floatxsd:doublefloat, double
Integerxsd:integerinteger without minInclusive or minExclusive facets, or with minInclusive or minExclusive facet of negative value
Unsigned IntegernonNegativeInteger or integer with minInclusive or minExclusive facet value of 0 or above
Stringxsd:stringstring, anySimpleType, anyURI, duration, All types derived by union
List All types derived by list, including IDREFS and ENTITIES
n-bit Unsigned Integer  
QName   

By default, types derived from the XML Schema types above are also represented by the associated built-in EXI datatype. When there are more than one XML Schema types above from which a type is derived directly or indirectly, the closest ancestor is used to determine the built-in EXI datatype. For example, a value of XML Schema type xsd:int is represented by the same built-in type as for XML Schema type xsd:integer. Although xsd:int is derived indirectly from xsd:integer and also further from xsd:decimal, a value of xsd:int is processed as an instance of xsd:integer because xsd:integer is closer to xsd:int than xsd:decimal is in the datatype inheritance hierarchy.

Each EXI datatype identifier above is a QName. Datatype identifiers uniquely identify one of the built-in EXI datatypes. They are used by Pluggable CODECS to designate XML Schema types to built-in EXI datatypes different from the ones that are associated by default. Not all built-in EXI datatypes are assigned datatype identifiers. Only those that have identifiers are usable by Pluggable CODECS for designating alternative representations.

The rules used to represent values of String depend on the content items to which the values belong. There are certain content items whose value representation involve the use of string tables while other content items are represented using the encoding rule described in 7.1.10 String without involvement of string tables. The content items that use string tables and how each of such content items uses string tables to represent their values are described in 7.3 String Table.

Schemas can provide one or more enumerated values for types. EXI exploits those pre-defined values when they are available to represent values of such types in a more efficient manner than it would otherwise using built-in EXI datatypes. The encoding rule for representing a type of enumerated values is described in 7.2 Enumerations. Types that are derived from other types by union and their subtypes are always represented as String regardless of the availability of enumerated values. Representation of values of which the schema type is one of QName, Notation or a type derived therefrom by restriction are also not affected by enumerated values if any.

7.1 Built-in EXI Datatypes Representation

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

7.1.1 Binary

Values typed as Binary are represented as a length-prefixed sequence of octets representing the binary content. The length is represented as an Unsigned Integer (see 7.1.6 Unsigned Integer).

7.1.2 Boolean

When the EXI compression option is set to false, values typed as Boolean are represented using one bit, otherwise they are represented using one byte. The value zero (0) represents false and the value one (1) represents true.

7.1.3 Decimal

Values typed as Decimal are represented as a Boolean sign (see 7.1.2 Boolean) followed by two Unsigned Integers (see 7.1.6 Unsigned Integer). A sign value of zero (0) is used to represent positive Decimal values and a sign value of one (1) is used to represent negative Decimal values. The first Unsigned Integer represents the integral portion of the Decimal value. The second Unsigned Integer represents the fractional portion of the Decimal value with the digits in reverse order to preserve leading zeros.

7.1.4 Float

Values typed as Float are represented as two consecutive Integers (see 7.1.5 Integer). The first Integer represents the mantissa of the floating point number and the second Integer represents the base-10 exponent of the floating point number. The range of the mantissa is - (263) to 263-1 and the range of the exponent is - (214-1) to 214-1. Values typed as Float with a mantissa or exponent outside the accepted range are represented as schema-invalid values.

The exponent value -(214) is used to indicate one of the special values: infinity, negative infinity and not-a-number (NaN). An exponent value -(214) with mantissa values 1 and -1 represents positive infinity (INF) and negative infinity (-INF) respectively. An exponent value -(214) with any other mantissa value represents NaN.

A value represented as Float can be decoded by going through the following steps.

  1. Retrieve the mantissa value using the procedure described in 7.1.5 Integer.
  2. Retrieve the exponent value using the procedure described in 7.1.5 Integer.
  3. If the exponent value is -(214), the mantissa value 1 represents INF, the mantissa value -1 represents -INF and any other mantissa value represents NaN. If the exponent value is not -(214), the float value is m × 10e where m is the mantissa and e is the exponent obtained in the preceding steps.

Note:

Support for IEEE float representation is currently under consideration. (See E.4 IEEE Floats)

7.1.5 Integer

The Integer type supports signed integer numbers of arbitrary magnitude. Values typed as Integer are represented as a Boolean sign (see 7.1.2 Boolean) followed by an Unsigned Integer (see 7.1.6 Unsigned Integer). A sign value of zero (0) is used to represent positive integers and a sign value of one (1) is used to represent negative integers. For non-negative values, the Unsigned Integer holds the magnitude of the value. For negative values, the Unsigned Integer holds the magnitude of the value minus 1.

7.1.6 Unsigned Integer

The Unsigned Integer type supports unsigned integer numbers of arbitrary magnitude. Values typed as Unsigned Integer are represented using a sequence of octets. The sequence is terminated by an octet with its most significant bit set to 0. The value of the unsigned integer is stored in the least significant 7 bits of the octets as a sequence of 7-bit bytes, with the least significant byte first.

A value represented as Unsigned Integer can be decoded by going through the following steps with the initial value set to 0 and the initial multiplier set to 1.

  1. Read the next octet.
  2. Multiply the value of the unsigned number represented by the 7 least significant bits of the octet by the current multiplier and add the result to the current value.
  3. Multiply the multiplier by 128.
  4. If the most significant bit of the octet was 1, go back to step 1.
Editorial note 
EXI also provides a modified representation for Integers that will not fit within a 64-bit integer to facilitate processing by devices that do not support big integers. This capability has not yet been specified.

7.1.7 QName

Values of type QName are each represented by the following two Strings (see 7.1.10 String) that are encoded consecutively in the order they are numbered below.

  1. URI of the QName value as an uri content item
  2. Local-name of the QName value

If the QName is in no namespace, the uri is represented by a zero length String.

Editorial note 
When the preserve.prefixes option is set to true, EXI also preserves the prefix of the QName. This capability has not yet been specified.

7.1.8 Date-Time

Values typed as Date-Time are encoded as a sequence of values representing the individual components of the Date-Time. The following table specifies each of the possible date-time components along with how they are encoded.

Table 7-2. Date-Time components
ComponentValueType
YearOffset from 2000Integer ( 7.1.5 Integer)
MonthDayMonth * 31 + Day9-bit Unsigned Integer (7.1.9 n-bit Unsigned Integer) where day is a value in the range 0-30 and month is a value in the range 1-12.
Time((Hour * 60) + Minutes) * 60 + seconds17-bit Unsigned Integer (7.1.9 n-bit Unsigned Integer)
FractionalSecsFractional secondsUnsigned Integer ( 7.1.6 Unsigned Integer) representing the fractional part of the seconds with digits in reverse order to preserve leading zeros
TimeZoneTZHours * 60 + TZMinutes11-bit Unsigned Integer (7.1.9 n-bit Unsigned Integer) representing a signed integer offset by 840 ( = 14 * 60 )
presenceBoolean presence indicatorBoolean (7.1.2 Boolean)

The variety of components that constitute a value and their appearance order depend on the XML Schema type associated with the value. The following table shows which components are included in a value of each XML Schema type that is relevant to Date-Time datatype. Items listed in square brackets are included if and only if the value of its preceding presence indicator (specified above) is set to true.

Table 7-3. Assortment of Date-Time components
XML Schema TypeIncluded Components
gYearYear, presence, [TimeZone]
gYearMonthYear, MonthDay, presence, [TimeZone]
date
dateTimeYear, MonthDay, Time, presence, [FractionalSecs], presence, [TimeZone]
gMonthMonthDay, presence, [TimeZone]
gMonthDay
gDay
timeTime, presence, [FractionalSecs], presence, [TimeZone]

7.1.9 n-bit Unsigned Integer

When the EXI compression option is set to false, values of type n-bit Unsigned Integer are represented as an unsigned binary integer using n bits. Otherwise, they are represented as an unsigned integer using the minimum number of bytes required to store n bits. Bytes are ordered with the least significant byte first.

7.1.10 String

Values of type String are encoded as a length prefixed sequence of characters. The length represents the number of characters in the string and is encoded as an Unsigned Integer (see 7.1.6 Unsigned Integer) and each character in the string is encoded as an Unsigned Integer (see 7.1.6 Unsigned Integer) representing its UCS code point.

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.11 List

Values of type List are encoded as a length prefixed sequence of values. The length is encoded as an Unsigned Integer (see 7.1.6 Unsigned Integer) and each value is encoded according to its type (see 7. Representing Event Content).

7.2 Enumerations

Values of enumerated types are encoded as n-bit Unsigned Integers (7.1.9 n-bit Unsigned Integer) where n = ⌈ log 2 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:

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.3.1 String Table Partitions

The string table is organized into partitions so that the indices assigned to compact identifiers can stay relatively small. Smaller number of indices results in improved average compactness and the efficiency of table operations. Each partition has a separate set of compact identifiers and content items are assigned to specific partitions as described below.

Uri content items and the URI portion of qname content items are assigned to the uri partition. The uri partition is optimized for frequent use of compact identifiers and is pre-populated with initial entries as described in D.1 Initial Entries in Uri Partition. When a schema is provided, the uri partition is also pre-populated with the name of each namespace URI declared in the schema, appended in lexicographical order.

Prefix content items are assigned to partitions based on their associated namespace URI. Partitions containing prefix content items are optimized for frequent use of compact identifiers and the string table is pre-populated with entries as described in D.2 Initial Entries in Prefix Partitions.

Local-name content items and the local-name portion of qname content items are assigned to partitions based on the namespace URI of the NS event or qname content item of which the local-name is a part. Partitions containing local-name content items are optimized for frequent use of string literals and the string table is pre-populated with entries as described in D.3 Initial Entries in Local-Name Partitions. When a schema is provided, the string table is also pre-populated with the local name of each attribute, element and type declared in the schema, partitioned by namespace URI and sorted lexicographically.

Value content items are assigned simultaneously to the global value partition as well as to the "local" value partition that corresponds to the qname of the attribute or element in context at the time when the string table is looked up and the string value is not found in both global and local value partitions. Partitions containing value content items are optimized for frequent use of string literals and are initially empty.

7.3.2 Partitions Optimized for Frequent use of Compact Identifiers

String table partitions that are expected to contain a relatively small number of entries used repeatedly throughout the document are optimized for the frequent use of compact identifiers. This includes the uri partition and all partitions containing prefix content items.

When a string value is found in a partition optimized for frequent use of compact identifiers, the string value is represented as the value (i+1) encoded as an n-bit Unsigned Integer (7.1.9 n-bit Unsigned Integer), where i is the value of the compact identifier, n is ⌈ log2 (m+1) ⌉ and m is the number of entries in the string table partition at the time of the operation.

When a string value is not found in a partition optimized for frequent use of compact identifiers, the String value is represented as zero (0) encoded as an n-bit Unsigned Integer, followed by the string literal encoded as a String (7.1.10 String). After encoding the String value, it is added to the string table partition and assigned the next available compact identifier m.

7.3.3 Partitions Optimized for Frequent use of String Literals

The remaining string table partitions are optimized for the frequent use of string literals. This includes all string table partitions containing local-name content items and all string table partitions containing value content items.

When a string value is found in the partitions containing local-name content items, the string value is represented as zero (0) encoded as an Unsigned Integer (see 7.1.6 Unsigned Integer) followed by an the compact identifier of the string value. The compact identifier of the string value is encoded as an n-bit unsigned integer (7.1.9 n-bit Unsigned Integer), where n is ⌈ log2 m ⌉ and m is the number of entries in the string table partition at the time of the operation.

When a string value is not found in the partitions containing local-name content items, its string literal is encoded as a String (see 7.1.10 String) with the length of the string is incremented by one. After encoding the string value, it is added to the string table partition and assigned the next available compact identifier m.

As described above, value content items are assigned to two partitions, a "local" value partition and the global value partition. When a string value is found in the "local" value partition, the string value is represented as zero (0) encoded as an Unsigned Integer (see 7.1.6 Unsigned Integer) followed by the compact identifier of the string value in the "local" value partition. When a string value is found in the global value partition, but not in the "local" value partition, the String value is represented as one (1) encoded as an Unsigned Integer (see 7.1.6 Unsigned Integer) followed by the compact identifier of the String value in the global value partition. The compact identifier is encoded as an n-bit unsigned integer (7.1.9 n-bit Unsigned Integer), where n is ⌈ log2m ⌉ and m is the number of entries in the associated partition at the time of the operation.

When a string value is not found in the global or "local" value partition, its string literal is encoded as a String (see 7.1.10 String) with the length incremented by two. After encoding the string value, it is added to both the associated "local" value string table partition and the global value string table partition.

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:

Example 7-1. codecMap indicating all Decimal values are represented using built-in String type
    <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:

Example 7-2. codecMap illustrating a used defined typed represented by a user defined CODEC.
    <codecMap xmlns:geo="http://www.example.com/Geometry">
        <geo:geometricSurface/>
	<geo:geometricInterpolator/>
    </codecMap>

8. EXI Compression

When the value of the compression option is set to true, EXI compression is used to increase compactness utilizing additional computational resources. EXI compression combines knowledge of XML with a widely adopted, standard compression algorithm to achieve higher compression ratios than would be achievable by applying compression to the entire stream. Byte-aligned representations of event codes and content items are more amenable to compression algorithms compared to unaligned representations because most compression algorithms operate on series of bytes to identify redundancies in the octets. Therefore, when EXI compression is used, event codes and content items of EXI events are encoded as aligned bytes in accordance with 6.2 Representing Event Codes and 7. Representing Event Content.

EXI compression splits a sequence of EXI events into a number of contiguous blocks of events. Events that belong to the same block are transformed into lower entropy groups of similar values called channels, which are individually well suited for standard compression algorithms. To reduce compression overhead, smaller channels are combined before compressing them, while larger channels are compressed independently. The criteria EXI compression uses to define and combine channels is intentionally simple to facilitate implementation, reduce processing overhead, and avoid the need to encode channel ordering or grouping information in the format. The figure below presents a schematic view of the steps involved in EXI compression.


EXI Compression Overview

Figure 8-1. EXI Compression Overview


In the following sections, 8.1 Blocks defines blocks and explains how EXI events are partitioned into blocks. Section 8.2 Channels defines channels, their organization as well as how a group of channels correlate to its corresponding block of events. Section 8.3 Compressed Streams describes how some channels are combined as needed in preparation for applying compression algorithms on channels.

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.


Multiplexing EXI events into channels

Figure 8-2. Multiplexing EXI events into channels


8.2.1 Structure Channel

The structure channel of each block defines the overall order and structure of the events in that block. It contains the event codes and associated content for each event in the block, except for Attribute (AT) and Character (CH) values, which are stored in the value channels. In addition, there are two attribute events whose values are stored in the structure channel instead of in value channels, which are xsi:nil and xsi:type attributes that match a schema-informed grammar production. These attribute events are intrinsic to the grammar system thus are essential in processing the structure channel because their values affect the grammar to be used for processing the rest of the elements on which they appear. All event codes and content in the structure stream occur in the same order as they occur in the EXI event sequence.

8.2.2 Value Channels

The values of the Attribute (AT) and Character (CH) events in each block are organized into separate channels based on the qname of the associated attribute or element. Specifically, the value of each Attribute (AT) event is placed in the channel identified by the qname of the Attribute and the value of each Character (CH) event is placed in the channel identified by the qname of its parent Start Element (SE) event. Each block contains exactly one channel for each distinct element or attribute qname that occurs in the block. The values in each channel occur in the order they occur in the EXI event sequence.

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. EXI Grammars

EXI is a knowledge based encoding that uses a set of grammars to determine which events are most likely to occur at any given point in an EXI stream and encodes the most likely alternatives in fewer bits. It does this by mapping the stream of events to a lower entropy set of representative values and encoding those values using a set of simple variable length codes or an EXI compression algorithm.

The result is a very simple, small algorithm that uniformly handles schema-less encoding, schema-informed encoding, schema deviations, and any combination thereof in EXI streams. These variations do not require different algorithms or different parsers, they are simply informed by different combinations of grammars.

The following sections describe the grammars used to inform the EXI encoding.

Note:

The grammar semantics in this specification are written for clarity and generality. They do not prescribe a particular implementation approach.

9.1 Grammar Notation

9.1.1 Fixed Event Codes

Each grammar production has an event code, which is represented by a sequence of one to three parts separated by periods ("."). Each part is an unsigned integer. The following are examples of grammar productions with event codes as they appear in this specification.

Example 9-1. Example productions with fixed event codes
ProductionsEvent Codes
 
LeftHandSide 1 :
Event 1   NonTerminal 10
Event 2   NonTerminal 21
Event 3   NonTerminal 32.0
Event 4   NonTerminal 42.1
Event 5   NonTerminal 52.2.0
Event 6   NonTerminal 62.2.1
 
LeftHandSide 2 :
Event 1   NonTerminal 10
Event 2   NonTerminal 21.0
Event 3   NonTerminal 31.1

The number of parts in a given event code is called the event code's length. No two productions with the same non-terminal symbol on the left-hand-side are permitted to have the same event code.

9.1.2 Variable Event Codes

Some non-terminal symbols are used on the right-hand-side in a production without an event prefixed to them. Such non-terminal symbols are macros and they are used to capture some recurring set of productions into symbols so that a symbol can be used in the grammar representation instead of including all the productions the macro represents in place every time it is used.

Example 9-2. Example productions that use macro non-terminal symbols
ABigProduction 1 :
Event 1   NonTerminal 10
Event 2   NonTerminal 21
LEFTHANDSIDE 1 (2.0)2.0
 
ABigProduction 2 :
Event 1   NonTerminal 10
LEFTHANDSIDE 1 (1.1)1.1
Event 2   NonTerminal 21.2

Because non-terminal macros are injected into the right-hand-side of more than one production, the event codes of productions with these macro non-terminals on the left-hand-side are not fixed, but will have different event code values depending on the context in which the macro non-terminal appears. This specification calls these variable event codes and uses variables in place of individual event code parts to indicate the event code parts are determined by the context. Below are some examples of variable event codes:

Example 9-3. Example non-terminal macros and its productions with variable event codes
LEFTHANDSIDE 1 (n.m) :
EVENT 1  NONTERMINAL 1 n.0
EVENT 2  NONTERMINAL 2 n.1
EVENT 3  NONTERMINAL 3 n. m+2
EVENT 4  NONTERMINAL 4 n. m+3
EVENT 5  NONTERMINAL 5 n. m+4.0
EVENT 6  NONTERMINAL 6 n. m+4.1

Unless otherwise specified, the variable n evaluates to the event code of the production in which the macro non-terminal LEFTHANDSIDE 1 appears on the right-hand-side. Similarly, the expression n. m represents the first two parts of the event code of the production in which the macro non-terminal LEFTHANDSIDE 1 appears on the right-hand-side.

Non-terminal macros are used in this specification for notational convenience only. They are not non-terminals, even though they are used in place of non-terminals. Productions that use non-terminal macros on the right-hand-side need to be expanded by macro substitution before such productions are interpreted. Therefore, ABigProduction 1 and ABigProduction 2 shown in the preceding example are equivalent to the following set of productions derived by expanding the non-terminal macro symbol LEFTHANDSIDE 1 and evaluating the variable event codes.

Example 9-4. Expanded productions equivalent to the productions used above
ABigProduction 1 :
Event 1   NonTerminal 10
Event 2   NonTerminal 21
EVENT 1  NONTERMINAL 12.0
EVENT 2  NONTERMINAL 22.1
EVENT 3  NONTERMINAL 32.2
EVENT 4  NONTERMINAL 42.3
EVENT 5  NONTERMINAL 52.4.0
EVENT 6  NONTERMINAL 62.4.1
 
ABigProduction 2 :
Event 1   NonTerminal 10
EVENT 1  NONTERMINAL 11.0
EVENT 2  NONTERMINAL 21.1
Event 2   NonTerminal 21.2
EVENT 3  NONTERMINAL 31.3
EVENT 4  NONTERMINAL 41.4
EVENT 5  NONTERMINAL 51.5.0
EVENT 6  NONTERMINAL 61.5.1

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:

Example 9-5. Example productions with event codes
ElementContent :
EE0
SE (*) ElementContent1.0
CH ElementContent1.1
ER ElementContent1.2
CM ElementContent1.3.0
PI ElementContent1.3.1

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:


Event code tree for ElementContent grammar

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.

Example 9-6. Example productions with full fidelity
ElementContent :
EE0
SE (*) ElementContent1.0
CH ElementContent1.1
ER ElementContent1.2
CM ElementContent1.3.0
PI ElementContent1.3.1

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:

Example 9-7. Example productions after pruning
ElementContent :
EE0
SE (*) ElementContent1.0
CH ElementContent1.1

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.

9.4.1 Built-in Document Grammar

In the absence of additional information about the content of the EXI stream, the following grammar describes the events that will occur in an EXI document.

SyntaxEvent Code
 
Document :
SD DocContent0
 
DocContent :
SE (*) DocEnd0
DT DocContent1.0
CM DocContent1.1.0
PI DocContent1.1.1
 
DocEnd :
ED0
CM DocEnd1.0
PI DocEnd1.1

Semantics:

All productions in the built-in Document grammars of the form LeftHandSide : SE (*) RightHandSide are evaluated as follows:

  1. Let qname be the qualified name of the element matched by SE (*)
  2. If a grammar does not exist for element qname, create one based on the Built-in Element Grammar
  3. Evaluate the element contents using a built-in grammar for element qname
  4. Evaluate the remainder of event sequence using RightHandSide.

9.4.2 Built-in Fragment Grammar

In the absence of additional information about the contents of an EXI stream, the following grammar describes the events that will occur in an EXI fragment. The grammar shown below represents the initial set of productions that belong to a built-in fragment grammar at the start of a stream processing, which is supplemented by the semantic description that explains the rules used to evolve the built-in fragment grammar to continuously improve it and be better prepared for subsequent uses of the same grammar during the rest of the processing of the stream.

SyntaxEvent Code
 
Fragment :
SD FragmentContent0
 
FragmentContent :
SE (*) FragmentContent0
ED1
CM FragmentContent2.0
PI FragmentContent2.1

Semantics:

All productions in the built-in Fragment grammars of the form LeftHandSide : SE (*) RightHandSide are evaluated as follows:

  1. Let qname be the qualified name of the element matched by SE (*)
  2. If a grammar does not exist for element qname, create one based on the Built-in Element Grammar
  3. Evaluate the element contents using a built-in grammar for element qname
  4. Create a production of the form LeftHandSide : SE (qname) RightHandSide with an event code 0
  5. Increment the first part of the event code of each production in the current grammar with the non-terminal LeftHandSide on the left hand side.
  6. Add the production created in step 4 to the grammar
  7. Evaluate the remainder of event sequence using RightHandSide.

All productions of the form LeftHandSide : SE (qname) RightHandSide that were previously added to the grammar upon the first occurrence of the element that has the qualified name qname are evaluated as follows when they are matched:

  1. Evaluate the element contents using a built-in grammar for element qname
  2. Evaluate the remainder of event sequence using RightHandSide.

9.4.3 Built-in Element Grammar

[Definition:]  EXI defines a built-in element grammar that is used in the absence of additional information about the contents of an EXI element prior to its processing. A built-in element grammar shown below is prescibed by EXI to reflect the events that will occur in an element and the order amongst them in general without any further constraint about what is likely or not likely to occur inside elements.

A single instance of built-in element grammar is shared by those elements in a stream that have the same qualified name and do not have additional a priori constraints as to their content. A separate instance of built-in element grammar is assigned to each qualified name upon the first occurrence of the elements of the same qualified name, thereafter the grammar continuously evolves by reflecting the knowledge learned while processing the content of those elements. The grammar shown below represents the initial set of productions that belong to a built-in element grammar at the time when a new instance is created, which is supplemented by the semantic description that explains the rules that are applied by the grammar onto itself to evolve and be better prepared for subsequent uses of the same grammar instance during the rest of the processing of the stream.

SyntaxEvent Code
 
StartTagContent :
EE0.0
AT (*) StartTagContent0.1
NS StartTagContent0.2
ChildContentItems (0.3)
 
ElementContent :
EE0
ChildContentItems (1.0)
 
ChildContentItems (n.m) :
SE (*) ElementContent n. m
CH ElementContent n.(m+1)
ER ElementContent n.(m+2)
CM ElementContent n.(m+3).0
PI ElementContent n.(m+3).1

Semantics:

All productions in the built-in Element grammar of the form LeftHandSide: AT (*) RightHandSide are evaluated as follows:

  1. Let qname be the qualified name of the attribute matched by AT (*)
  2. Create a production of the form LeftHandSide : AT (qname) StartTagContent with an event code 0 and increment the first part of the event code of each production in the current grammar with the non-terminal LeftHandSide on the left hand side
  3. Add the production created in the previous step to the grammar
  4. Evaluate the remainder of event sequence using RightHandSide.

All productions in the built-in Element grammars of the form LeftHandSide : SE (*) RightHandSide are evaluated as follows:

  1. Let qname be the qualified name of the element matched by SE (*)
  2. If a grammar does not exist for element qname, create one based on the Built-in Element Grammar
  3. Evaluate the element contents using a built-in grammar for element qname
  4. Create a production of the form LeftHandSide : SE (qname) RightHandSide with an event code 0
  5. Increment the first part of the event code of each production in the current grammar with the non-terminal LeftHandSide on the left hand side.
  6. Add the production created in step 4 to the grammar
  7. Evaluate the remainder of event sequence using RightHandSide.

All productions of the form LeftHandSide : SE (qname) RightHandSide that were previously added to the grammar upon the first occurrence of the element that has the qualified name qname are evaluated as follows when they are matched:

  1. Evaluate the element contents using a built-in grammar for element qname
  2. Evaluate the remainder of event sequence using RightHandSide.

All productions in the built-in Element grammar of the form LeftHandSide : CH RightHandSide are evaluated as follows:

  1. If a production of the form, LeftHandSide : CH RightHandSide with an event code of length 1 does not exist in the current element grammar, create one with event code 0 and increment the first part of the event code of each production in the current grammar with the non-terminal LeftHandSide on the left hand side.
  2. Add the production created in step 1 to the grammar
  3. Evaluate the remainder of event sequence using RightHandSide.

9.5 Schema-informed Grammars

This section describes the schema-informed grammars used by EXI when schema information is available to describe the contents of the EXI stream. Schema-informed grammars are independent of any particular schema language and can be derived from W3C XML Schemas, RELAX NG schemas, DTDs or other regular languages for describing what is likely to occur in an EXI stream.

Schema-informed grammars accept all XML documents and fragments regardless of whether and how closely they match the schema. The encoder encodes individual events using schema-informed grammars where they are available and falls back to the built-in XML grammars where they are not. In general, events for which a schema-informed grammar exists will be encoded more efficiently.

Unlike built-in XML grammars, schema-informed grammars are static and do not evolve, which permits the reuse of schema-informed grammars across the processing of multiple EXI streams. This is a single outstanding difference between the two grammar systems.

9.5.1 Schema-informed Document Grammar

When schema information is available to describe the contents of an EXI stream, the following grammar describes the events that will occur in an EXI document.

SyntaxEvent Code
 
Document :
SD DocContent0
 
DocContent :
SE (G 0) DocEnd0
SE (G 1) DocEnd1
  ⋮
SE (G n-1) DocEndn-1
SE (*) DocEnd n.0
DT DocContent n.1
CM DocContent n.2.0
PI DocContent n.2.1
 
N.B.
  • The variable n in the grammar above is the number of global elements declared in the schema. G 0, G 1, ... G n-1 represent all the qnames of global elements sorted lexicographically, first by localName, then by uri.
  • The terminal symbol SE (*) is only matched if a more specific match does not exist among SE(G 0), SE(G 1), ... SE(G n-1).
DocEnd :
ED0
CM DocEnd1.0
PI DocEnd1.1

Semantics:

All productions in the schema-informed document grammars of the form LeftHandSide : SE (*) RightHandSide are evaluated as follows:

  1. Let qname be the qualified name of the element matched by SE (*)
  2. If a grammar does not exist for Element qname, create one based on the Built-in Element Grammar
  3. Evaluate the element contents using the SE (qname) grammar

9.5.2 Schema-informed Fragment Grammar

When schema information is available to describe the contents of an EXI stream, the following grammar describes the events that will occur in an EXI fragment.

SyntaxEvent Code
 
Fragment :
SD FragmentContent0
 
FragmentContent :
SE (F 0) FragmentContent0
SE (F 1) FragmentContent1
  ⋮
SE (F n-1) FragmentContentn-1
ED n
SE (*) FragmentContent(n+1).0
CM FragmentContent(n+1).1.0
PI FragmentContent(n+1).1.1
 
N.B.
  • The variable n in the grammar above is the number of unique element qnames declared in the schema. F 0, F 1, ... F n-1 represent all the unique qnames of elements sorted lexicographically, first by localName, then by uri. If there is more than one element with the same qname, the qname is included only once with a relaxed grammar that accepts any content.
  • The terminal symbol SE (*) is only matched if a more specific match does not exist among SE(F 0), SE(F 1), ... SE(F n-1).
Semantics:

All productions in the schema-informed fragment grammars of the form LeftHandSide : SE (*) RightHandSide are evaluated as follows:

  1. Let qname be the qualified name of the element matched by SE (*)
  2. If a grammar does not exist for Element qname, create one based on the Built-in Element Grammar
  3. Evaluate the element contents using the SE (qname) grammar

9.5.3 Schema-informed Element Grammar

Editorial note 
This section is under development. It currently explains how schema-informed element grammars are constructed by example. A complete, formal description of how schema-informed element grammars are constructed will be included in the next draft.

[Definition:]  When a schema is available to describe the contents of an EXI stream, a schema-informed element grammar is derived for each element content model described by the schema. This section describes the process for creating schema-informed element grammars and provides an illustrative example.

9.5.3.1 Element Content Models

The first step is to create a grammar that describes the element's content model according to available schema information. To simplify the set of required productions and increase efficiency, the grammar takes into account that all attributes will occur sorted lexically by qname (see 6. Encoding EXI Streams).

For example, consider the following XML Schema fragment declaring two elements, <order> and <product>:

Example 9-8. Example XML Schema fragment
<xs:element name="order"> 
  <xs:complexType> 
    <xs:sequence> 
      <xs:element ref="product" maxOccurs="unbounded" /> 
    </xs:sequence> 
  </xs:complexType> 
</xs:element> 

<xs:element name="product"> 
  <xs:complexType> 
    <xs:sequence> 
      <xs:element name="description" type="xs:string" minOccurs="0"/> 
      <xs:element name="quantity" type="xs:integer" /> 
      <xs:element name="price" type="xs:float" /> 
    </xs:sequence> 
    <xs:attribute name="sku" type="xs:string" use="required" /> 
    <xs:attribute name="color" type="xs:string" use="optional" /> 
  </xs:complexType> 
</xs:element> 

The following grammar derived from this schema describes the content model for the <order> element.

Example 9-9. Schema-informed element grammar for <order>
SyntaxEvent Code
 
StartTagContent :
SE ("product") ElementContent0
 
ElementContent :
SE ("product") ElementContent0
EE1

This simple grammar accepts the content of the <order> element described by the schema above. I.e., it accepts one or more instances of the <product> element followed by an end tag.

The following grammar derived from the schema above describes the content model for the <product> element:

Example 9-10. Schema-informed element grammar for <product>
SyntaxEvent Code
 
StartTagContent1 :
AT ("color") StartTagContent20
AT ("sku") ElementContent11
 
StartTagContent2 :
AT ("sku") ElementContent10
 
ElementContent1 :
SE ("description") ElementContent20
SE ("quantity") ElementContent31
 
ElementContent2 :
SE ("quantity") ElementContent30
 
ElementContent3 :
SE ("price") ElementContent40
 
ElementContent4 :
EE0

Note:

The names of all the non-terminal symbols in this example were selected for clarity and consistency with other examples. The left-hand-side non-terminal symbol of each set of productions that have the same left-hand-side non-terminal symbol and at least one production containing the terminal symbol AT ( qname) is given a name beginning with StartTagContent. All other left-hand-side non-terminal symbols are given names beginning with ElementContent.

For each set of productions with the same non-terminal symbol on the left-hand-side, the order of the productions is defined as follows. All productions that contain the terminal symbol AT ( qname) occur first, sorted lexically by qname. These are followed by all productions that contain the terminal symbol SE ( qname), which occur in the same order they were declared in the schema. If there is a production that contains the EE terminal symbol, it occurs last.

As illustrated in the example above, the event codes assigned to each set of productions with the same non-terminal symbol on the left-hand-side have length 1 and are numbered sequentially starting with 0.

9.5.3.2 Undeclared Productions

Each element content-model defined by a schema describes the sequences of child elements and attributes that are valid for the associated element(s) according to the schema. However, they do not explicitly accept schema extensions and deviations or other information items, such as comments and processing instructions.

This section describes a set of productions used to augment the schema-informed element content model grammars to describe sequences of events that were not explicitly declared in the schema, but are permitted to occur in well-formed XML documents.

The following productions are used by each set of content model productions that have the same non-terminal symbol on the left-hand-side and include at least one production with the terminal symbol AT (qname) on the right-hand-side:

SyntaxEvent Code
 
UndeclaredStartTagItems :
AT (xsi:type) n. m
AT (xsi:nil) n.(m+1)
AT (*) n.(m+2)
AT (D 0)n.(m+3).0
AT (D 1)n.(m+3).1
  ⋮
AT (D n-1)n.(m+3).(n-1)
AT (*) [schema-invalid]n.(m+3).(n)
NS n.(m+4)

Note:

  • The variable n above represents the number of attributes declared in the schema for this context.
  • AT (xsi:type) matches an xsi:type attribute that specifies a schema-valid type for the current element. The value of an AT (xsi:type) event is represented as a QName (see 7.1.7 QName). An xsi:type attribute that specifies a schema-invalid type for the current element is matched by the AT(*) terminal symbol. The terminal symbol AT (*) is only matched if a more specific match for the current event does not exist in the grammar.
  • AT (D i) where i is a number of the range 0 ≤ i < n matches an attribute with qname D i that was declared in the schema for this context, but has a value that is schema-invalid. The value of an attribute that matches AT (D i) is encoded as a String regardless of the schema-type associated with the qname D i.
  • AT (*) [schema-invalid] matches any attribute declared in the schema that is not permitted in this context and has a schema-invalid value.

Semantics:

When using schemas, all productions of the form LeftHandSide : AT (xsi:type) are evaluated as follows:

  1. Let qname be the value of the xsi:type attribute
  2. Evaluate the element contents using the grammar for the qname type instead of the declared type for the current element

When using schemas, the production LeftHandSide : AT (*) is evaluated as follows:

  1. Let qname be the qualified name of the the attribute matched by AT (*)
  2. If a grammar exists for attribute qname, evaluate the contents of the attribute according to the AT (qname) grammar.

The following productions are used by each set of content model productions that have the same non-terminal symbol on the left-hand side:

SyntaxEvent Code
 
UndeclaredContentItems :
SE (*) n. m
CH [schema-invalid] n.( m+1)
ER n.( m+2)
CM n.( m+3).0
PI n.( m+3).1

Note:

Productions with event code length 2 that include the terminal symbol CH represent un-typed character data. The UndeclaredContentItems : CH production above is used to represent schema-invalid character data. Schema-valid character data is represented by a separate production with event code length 1 that includes the CH terminal symbol, which is included anywhere typed character data is expected in the schema-informed grammars.

Note:

The terminal symbol SE (*) is only matched if a more specific match for the current event does not exist in the grammar.

The following production is used by each set of content model productions that have the same non-terminal symbol on the left-hand-side if that set of productions does not already include a production with the non-terminal symbol EE on the right hand side.

SyntaxEvent Code
 
UndeclaredEE :
EE n
9.5.3.3 Combined Grammar

This section describes how the undeclared productions described in section 9.5.3.2 Undeclared Productions are combined with the element content model grammars described in section 9.5.3.1 Element Content Models to produce the grammar used by the EXI processor.

The following productions are added to each set of productions that has the same non- terminal symbol on the left-hand-side and includes at least one production with the terminal symbol AT ( qname) on the right-hand-side:

SyntaxEvent Code
 
StartTagContentX :
UndeclaredEE n. m
UndeclaredStartTagItems StartTagContentX n. m+1
UndeclaredContentItems ElementContent1 n. m+6

where StartTagContentX represents the left-hand-side non-terminal to which the production is being added, ElementContent1 represents the first non-terminal in the element grammar for which there is no production that includes the non-terminal AT (*) and n. m represents the next available event code with length 2. The production UndeclaredEE is only included if the element content model grammar does not already include a production of the form StartTagContentX : EE.

The following productions are added to each set of productions that have the same non- terminal symbol on the left-hand-side, but do not include a production with the terminal symbol AT ( qname) on the right-hand-side.

SyntaxEvent Code
 
ElementContentX :
UndeclaredEE n
UndeclaredContentItems ElementContentX n. m

where ElementContentX represents the left-hand-side non-terminal to which the production is being added, n represents the next available event code with length 1 and n. m represents the next available event code with length 2. The production UndeclaredEE is only included if the element content model grammar does not already include a production of the form ElementContentX : EE.

To continue our example, adding the productions described above to the example content model grammars described in section 9.5.3.1 Element Content Models, produces the following grammar:

Example 9-11. Combined grammar for <order> element
SyntaxEvent Code
 
StartTagContent :
SE ("product") ElementContent0
UndeclaredEE1.0
UndeclaredStartTagItems StartTagContent1.1
UndeclaredContentItems ElementContent1.6
 
ElementContent :
SE ("product") ElementContent0
EE1
UndeclaredContentItems ElementContent2.0

Adding the undeclared productions to the <product> element described above, produces the following grammar:

Example 9-12. Combined grammar for <product> element
SyntaxEvent Code
 
StartTagContent 1 :
AT ("color") StartTagContent 20
AT ("sku") ElementContent 11
UndeclaredEE2.0
UndeclaredStartTagItems StartTagContent 12.1
UndeclaredContentItems ElementContent 12.6
 
StartTagContent 2 :
AT ("sku") ElementContent 10
UndeclaredEE1.0
UndeclaredStartTagItems StartTagContent 21.1
UndeclaredContentItems ElementContent 11.6
 
ElementContent 1 :
SE ("description") ElementContent 20
SE ("quantity") ElementContent 31
UndeclaredEE2
UndeclaredContentItems ElementContent 13.0
 
ElementContent 2 :
SE ("quantity") ElementContent 30
UndeclaredEE1
UndeclaredContentItems ElementContent 22.0
 
ElementContent 3 :
SE ("price") ElementContent 40
UndeclaredEE1
UndeclaredContentItems ElementContent 32.0
 
ElementContent 4 :
EE0
UndeclaredContentItems ElementContent 41.0

10. Conformance

Note:

Description of EXI processor classes will be provided in this section. There will be classes of EXI processors each of which represents either the whole or some limited capacity of the capability defined in the preceding sections. The set of capability that may drive processor classification include schema processing, pluggable codecs.

A References

A.1 Normative References

IETF RFC 1951
DEFLATE Compressed Data Format Specification version 1.3, P. Deutsch, Author. Internet Engineering Task Force, May 1996. Available at http://www.ietf.org/rfc/rfc1951.txt.
IETF RFC 2119
Key words for use in RFCs to Indicate Requirement Levels, S. Bradner, Author. Internet Engineering Task Force, June 1999. Available at http://www.ietf.org/rfc/rfc2119.txt.
XML 1.0
Extensible Markup Language (XML) 1.0 (Fourth Edition), T. Bray, J. Paoli, C. M. Sperberg-McQueen, and E. Maler, Editors. World Wide Web Consortium, 10 February 1998, revised 16 August 2006. This version is http://www.w3.org/TR/2006/REC-xml-20060816. The latest version is available at http://www.w3.org/TR/REC-xml.
XML Information Set
XML Information Set (Second Edition), J. Cowan and R. Tobin, Editors. World Wide Web Consortium, 24 October 2001, revised 4 February 2004. This version is http://www.w3.org/TR/2004/REC-xml-infoset-20040204. The latest version is available at http://www.w3.org/TR/xml-infoset.
XML Schema Structures
XML Schema Part 1: Structures Second Edition, H. Thompson, D. Beech, M. Maloney, and N. Mendelsohn, Editors. World Wide Web Consortium, 2 May 2001, revised 28 October 2004. This version is http://www.w3.org/TR/2004/REC-xmlschema-1-20041028. The latest version is available at http://www.w3.org/TR/xmlschema-1.
XML Schema Datatypes
XML Schema Part 2: Datatypes Second Edition, P. Byron and A. Malhotra, Editors. World Wide Web Consortium, 2 May 2001, revised 28 October 2004. This version is http://www.w3.org/TR/2004/REC-xmlschema-2-20041028. The latest version is available at http://www.w3.org/TR/xmlschema-2.

A.2 Other References

Efficient XML
Efficient XML, part of [EXI Measurements Note] independently referenced. The latest version at the time of this writing is http://www.w3.org/TR/2006/WD-exi-measurements-20060718/#contributions-efx
EXI Measurements Note
Efficient XML Interchange Measurements Note, Greg White, Don Brutzman, Stephen Williams and Jaakko Kangasharju, Editors. World Wide Web Consortium. The latest version at the time of this writing is http://www.w3.org/TR/2006/WD-exi-measurements-20060718/.
Huffman Coding
A Method for the Construction of Minimum-Redundancy Codes, D. A. Huffman, Author. Proceedings of the I.R.E., September 1952, pp 1098-1102.
ISO/IEC 19757-2:2003
Document Schema Definition Language (DSDL) -- Part 2: Regular-grammar-based validation -- RELAX NG
SOAP 1.2
SOAP Version 1.2 Part 1: Messaging Framework, M. Gudgin, M. Hadley, N. Mendelsohn, J-J. Moreau, H. Frystyk Nielsen, Editors. World Wide Web Consortium, 24 June 2003. This version is http://www.w3.org/TR/2003/REC-soap12-part1-20030624/. The latest version is available at http://www.w3.org/TR/soap12-part1/.
XBC Measurement Methodologies
XML Binary Characterization Measurement Methodologies, S. D. Williams and P. Haggar, Editors. World Wide Web Consortium, 31 March 2005. This version is http://www.w3.org/TR/2005/NOTE-xbc-measurement-20050331/. The latest version is available at http://www.w3.org/TR/xbc-measurement.
XBC Use Cases
XML Binary Characterization Use Cases, Mike Cokus and Santiago Pericas-Geertsen, Editors. World Wide Web Consortium, 31 March 2005. This version is http://www.w3.org/TR/2005/NOTE-xbc-use-cases-20050331/. The latest version is available at http://www.w3.org/TR/xbc-use-cases.
XBC Properties
XML Binary Characterization Properties, Mike Cokus and Santiago Pericas-Geertsen, Editors. World Wide Web Consortium, 31 March 2005. This version is http://www.w3.org/TR/2005/NOTE-xbc-properties-20050331/ The latest version is available at http://www.w3.org/TR/xbc-properties/.

B Infoset Mapping

This appendix contains the mappings between the XML Information Set [XML Information Set] model and the EXI format. Starting from the document information item, each information item definition is mapped to its respective unordered set of EXI event types. The actual order amongst information set items when it is relevant reflects the occurrence order of EXI events or their references in an EXI stream that correlate to the infoset items. As used in the XML Information Set specification, the Infoset property names are shown in square brackets, [thus].

B.1 Document Information Item

A document information item maps to a pair of SD and ED event with each of its properties subject to further mapping as shown in the following table.

Table B-1. Mapping between the document information item properties to EXI event types
PropertyEXI event types
[children]CM* PI* DT? [SE, EE]
[document element][SE, EE]
[notations]Computed based on text content item of DT to which each notation information set item maps to.
[unparsed entities]Computed based on text content item of DT to which each unparsed entity information set item maps to.
[base URI]The base URI of the EXI stream
[character encoding scheme]N/A
[standalone]Not available
[version]Not available
[all declarations processed]True if all declarations contained directly or indirectly in DT are processed, otherwise false, which is the processor quality as opposed to the information provided by the format.

B.2 Element Information Items

An element information item maps to a pair of a SE event and the corresponding EE event with each of its properties subject to further mapping as shown in the following table.

Table B-2. Mapping of the element information item properties to EXI event types
PropertyEXI event types
[namespace name]SE
[local name]SE
[prefix]SE
[children][SE, EE]* PI* CM* CH* ER*
[attributes]AT*
[namespace attributes]NS*
[in-scope namespaces] The namespace information items computed using the [namespace attributes] properties of this information item and its ancestors
[base URI]The base URI of the element information item
[parent]Computed based on the last SE event encountered that did not get a matching EE event if any, or computed based on the SD event

B.3 Attribute Information Item

An attribute information item maps to an AT event with each of its properties subject to further mapping as shown in the following table.

Table B-3. Mapping of the attribute information item properties to EXI event types
PropertyEXI event types
[namespace name]AT
[local name]AT
[prefix]AT
[normalized value]The value of AT
[specified]True if the item maps to AT, otherwise false
[attribute type] Computed based on AT and DT
[references] Computed based on [attribute type] and value of AT
[owner element]Computed based on the last SE event encountered that did not get a matching EE event

B.4 Processing Instruction Information Item

A processing instruction information maps to a PI event with each of its properties subject to further mapping as shown in the following table.

Table B-4. Mapping of the processing instruction information item properties to EXI event types
PropertyEXI event types
[target]PI
[content]PI
[base URI]The base URI of the processing information item
[notation] Computed based on the availability of the internal DTD subset
[parent]Computed based on the last SE event encountered that did not get a matching EE event type

B.5 Unexpanded Entity Reference Information item

An unexpanded entity reference information item maps to an ER with each of its properties subject to further mapping as shown in the following table.

Table B-5. Mapping of the entity reference information item properties to the EXI event types
PropertyEXI event types
[name]ER
[system identifier]Based on the availability of the internal DTD subset
[public identifier]Based on the availability of the internal DTD subset
[declaration base URI]The base URI of the unexpanded entity reference information item
[parent]Computed based on the last SE event encountered that did not get a matching EE event type

B.6 Character Information item

A character information item maps to the individual characters contained in a CH event following a SE event that did not get a matching EE event.

Table B-6. Mapping of the character information item properties and the EXI event types
PropertyEXI event types
[character code]Each character in CH
[element content whitespace]Computed based on [parent] and DT
[parent]Computed based on the last SE event encountered that did not get a matching EE event

B.7 Comment Information item

A comment information item maps to a CM event with each of its properties subject to further mapping as shown in the following table.

Table B-7. Mapping of the comment information item properties and the EXI event types
PropertyEXI event types
[content]text content item of CM
[parent]Computed based on the last SE event encountered that did not get a matching EE event, or the SD event

B.8 Document Type Declaration Information item

A document type declaration information item maps to a DT event with each of its properties subject to further mapping as shown in the following table.

Table B-8. Mapping of the document type declaration information item properties to the EXI event types
PropertyEXI event types
[system identifier]DT
[public identifier]DT
[children]Computed based on text content item of DT
[parent]Computed based on the SD event

B.9 Unparsed Entity Information Item

An unparsed entity information item maps to part of the text content item of DT event with each of its properties subject to further mapping as shown in the following table.

Table B-9. Mapping of the unparsed entity information item properties to EXI event types
PropertyEXI event types
[name]Computed based on text content item of DT
[system identifier]Computed based on text content item of DT
[public identifier]Computed based on text content item of DT
[declaration base URI]The base URI of the unparsed entity information item
[notation name]Computed based on text content item of DT
[notation]Computed based on text content item of DT

B.10 Notation Information Item

An notation information item maps to part of the text content item of DT event with each of its properties subject to further mapping as shown in the following table.

Table B-10. Mapping of the notation information item properties to EXI event types
PropertyEXI event types
[name]Computed based on text content item of DT
[system identifier]Computed based on text content item of DT
[public identifier]Computed based on text content item of DT
[declaration base URI]The base URI of the notation information item

B.11 Namespace Information Item

An namespace information item ismaps toa NS event with each of its properties subject to further mapping as shown in the following table.

Table B-11. Mapping of the namespace information item properties to EXI event types
PropertyEXI event types
[prefix]NS
[namespace name]NS

C XML Schema for EXI Options Header

The following schema describes the EXI options header. It is designed to produce smaller headers for option combinations used when compactness is critical.

<xsd:schema targetNamespace="http://www.w3.org/2007/07/exi"
            xmlns:xsd="http://www.w3.org/2001/XMLSchema"
            elementFormDefault="qualified">

  <xsd:element name="header">
    <xsd:complexType>
      <xsd:sequence>
        <xsd:element name="lesscommon" minOccurs="0">
          <xsd:complexType>
            <xsd:sequence>
              <xsd:element name="uncommon" minOccurs="0">
                <xsd:complexType>
                  <xsd:sequence>
                    <xsd:any namespace="##other" minOccurs="0" maxOccurs="unbounded" />
                    <xsd:element name="codecMap" minOccurs="0" maxOccurs="unbounded">
                      <xsd:complexType>
                        <xsd:sequence>
                          <xsd:any namespace="##other" /> <!-- schema type -->
                          <xsd:any namespace="##other" /> <!-- CODEC -->
                        </xsd:sequence>
                      </xsd:complexType>
                    </xsd:element>
                  </xsd:sequence>
                </xsd:complexType>
              </xsd:element>
              <xsd:element name="preserve" minOccurs="0">
                <xsd:complexType>
                  <xsd:sequence>
                    <xsd:element name="dtd" minOccurs="0">
                      <xsd:complexType />
                    </xsd:element>
                    <xsd:element name="prefixes" minOccurs="0">
                      <xsd:complexType />
                    </xsd:element>
                    <xsd:element name="lexicalValues" minOccurs="0">
                      <xsd:complexType />
                    </xsd:element>
                    <xsd:element name="comments" minOccurs="0">
                      <xsd:complexType />
                    </xsd:element>
                    <xsd:element name="pis" minOccurs="0">
                      <xsd:complexType />
                    </xsd:element>
                  </xsd:sequence>
                </xsd:complexType>
              </xsd:element>
              <xsd:element name="blockSize" minOccurs="0">
                <xsd:simpleType>
                  <xsd:restriction base="xsd:unsignedInt" /> 
                </xsd:simpleType>
              </xsd:element>                 
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
        <xsd:element name="common" minOccurs="0">
          <xsd:complexType>
            <xsd:sequence>
              <xsd:element name="compression" minOccurs="0">
                <xsd:complexType />
              </xsd:element>
              <xsd:element name="fragment" minOccurs="0">
                <xsd:complexType />
              </xsd:element>
              <xsd:element name="schemaId" minOccurs="0" nillable="true">
                <xsd:simpleType>
                  <xsd:restriction base="xsd:string" />
                </xsd:simpleType>
              </xsd:element>
            </xsd:sequence>
          </xsd:complexType>
        </xsd:element>
        <xsd:element name="strict" minOccurs="0">
          <xsd:complexType />
        </xsd:element>
      </xsd:sequence>
    </xsd:complexType>
  </xsd:element>

</xsd:schema>

D Initial Entries in String Table Partitions

D.1 Initial Entries in Uri Partition

The following table lists the entries that are initially populated in uri partitions, where partition name URI denotes that they are entries in the uri partition.

Table D-1. Initial values in uri partition
PartitionString IDString Value
URI0"" [empty string]
URI1"http://www.w3.org/XML/1998/namespace"
URI2"http://www.w3.org/2001/XMLSchema-instance"
URI3"http://www.w3.org/2001/XMLSchema"

D.2 Initial Entries in Prefix Partitions

The following table lists the entries that are initially populated in prefix partitions, where XML-PF represents the partition for prefixes in the "http://www.w3.org/XML/1998/namespace" namespace and XSI-PF represents the partition for prefixes in the "http://www.w3.org/2001/XMLSchema-instance" namespace.

Table D-2. Initial prefix string table entries
PartitionString IDString Value
""0"" [empty string]
XML-PF0"xml"
XSI-PF0"xsi"

D.3 Initial Entries in Local-Name Partitions

The following table lists the entries that are initially populated in local-name partitions, where XML-NS represents the partition for local-names in the "http://www.w3.org/XML/1998/namespace" namespace, XSI-NS represents the partition for local-names in the "http://www.w3.org/2001/XMLSchema-instance" namespace, and XSD-NS represents the partition for local-names in the "http://www.w3.org/2001/XMLSchema" namespace.

Table D-3. Initial local-name string table entries
PartitionString IDString Value
XML-NS0"space"
XML-NS1"lang"
XML-NS2"id"
XML-NS3"base"
XSI-NS0"type"
XSI-NS1"nil"
XSD-NS0"anyType"
XSD-NS1"anySimpleType"
XSD-NS2"string"
XSD-NS3"normalizedString"
XSD-NS4"token"
XSD-NS5"language"
XSD-NS6"Name"
XSD-NS7"NCName"
XSD-NS8"ID"
XSD-NS9"IDREF"
XSD-NS10"IDREFS"
XSD-NS11"ENTITY"
XSD-NS12"ENTITIES"
XSD-NS13"NMTOKEN"
XSD-NS14"NMTOKENS"
XSD-NS15"duration"
XSD-NS16"dateTime"
XSD-NS17"time"
XSD-NS18"date"
XSD-NS19"gYearMonth"
XSD-NS20"gYear"
XSD-NS21"gMonthDay"
XSD-NS22"gDay"
XSD-NS23"gMonth"
XSD-NS24"boolean"
XSD-NS25"base64Binary"
XSD-NS26"hexBinary"
XSD-NS27"float"
XSD-NS28"double"
XSD-NS29"anyURI"
XSD-NS30"QName"
XSD-NS31"NOTATION"
XSD-NS32"decimal"
XSD-NS33"integer"
XSD-NS34"nonPositiveInteger"
XSD-NS35"negativeInteger"
XSD-NS36"long"
XSD-NS37"int"
XSD-NS38"short"
XSD-NS39"byte"
XSD-NS40"nonNegativeInteger"
XSD-NS41"positiveInteger"
XSD-NS42"unsignedLong"
XSD-NS43"unsignedInt"
XSD-NS44"unsignedShort"
XSD-NS45"unsignedByte"

E Format Features Under Consideration (Non-Normative)

This section describes format features that, at the time of writing, are under consideration by the WG. The list of proposed features and extensions under consideration is actually longer, only those that have been discussed by the WG are included here. Most of these features are intended to address the format's compactness, but some may also improve the processing efficiency of a format's processor. The feature of E.2 Strict Schemas will be described in a normative part of the specification once the details of its definition have been settled. The others will each be tested in order to collect data to determine whether their value outweighs the additional cost and complexity they would introduce into the format.

E.1 Bounded Integers

A BoundedInteger type can be used in place of a standard Integer type when it is possible to determine the bounds of a set of integer values. This can be done implicitly based on the intrinsic datatype bounds (e.g., a byte can hold values in the -128 to 127 range) or the nature of the values (e.g., lengths are never negative), or explicitly as determined by facets or constraints defined in the schema. In the case of XML Schema, facets such as minInclusive and maxInclusive may be used to determine bounds.

A BoundedInteger is encoded as an offset (or delta) from the minimum value in the range. It is encoded in the minimum number of bits that would be necessary to hold any value within the full range. For example, if an integer is constrained to have a value between 3 and 10 (inclusively) and the value to be encoded is 7, the number encoded would be 7 - 3 = 4 and the number of bits needed would be 3.

If the range defined by the bounds is large, the average number of bits needed to encode a set of values can be larger than the number of bits needed if those values are encoded as variable-length integers (see 7.1.5 Integer). Earlier results by some WG members indicate that if the value range can be represented in 12 bits or less, the use of a BoundedInteger type has some measurable benefits.

E.2 Strict Schemas

A strict schema fidelity option can be supported whereby an encoder can be informed of the validity of the document being processed. Strict schema coding would likely improve compactness for use cases where documents are known to be valid according to a given schema, or where it is known that a non-valid part of a document is of no relevance to the decoder. This fidelity option is unlikely to impact the runtime performance since it only affects an encoder's initialization phase. However, this additional information will likely benefit compactness by reducing the number of productions in the grammar and, consequently, the number of bits needed to encode event codes.

One of the usages of strict schemas would be for processing the EXI document representing the EXI Options in an EXI header. It can be encoded using the schema in Appendix C XML Schema for EXI Options Header with the options specified by the following XML document:

Header options definition for processing header options
  <header xmlns="http://www.w3.org/2007/07/exi">
    <strict/>
  </header>

E.3 Restricted Character Sets

A restricted character set type can be used in places where a small set of likely characters can be determined for a given string. These can be either built-in sets for known limited ranges (examples are the whitespace set and date/time types), or can be user defined through schema facets. In the case of XML schema, the primary facet for defining such a range would be the pattern facet.

By lexicographically sorting the characters in a restricted set, a character value can be encoded as an index in that set. The index itself can be encoded as a bounded integer (see E.1 Bounded Integers) in the range 1 to N, where N is the size of the set. For example, if the white space set is considered to have 4 values: space(0x20), tab(0x09), CR(0x0D), and LF(0x0A), then an index in this set can be encoded using 2 bits.

Just like EXI supports schema deviations, it may be possible to support character set deviations as well. One proposal introduces the notion of an escape character to indicate that the character that follows does not belong to the restricted set and it is therefore not encoded using an index.

E.4 IEEE Floats

At least two of the use cases identified in the XML Binary Characterization Use Cases document suggested efficient support for floating point data aggregates such as arrays and matrices. The most popular representation for floating point values is that defined by the IEEE 754 standard. Native support for this standard datatype in EXI could result in significant performance improvements for those applications that manipulate large amounts of numerical data. In such XML applications, a lot of time can be spent converting to and from IEEE 754. We will determine whether such direct support for IEEE 754 and numerical aggregates is significantly greater than use of the existing mechanism for floats in EXI described above.

Even though the IEEE 754 is extremely popular, it is not supported in all platforms, for instance low and mid-end cell phones. Therefore, if support for this datatype is made mandatory in EXI, some conversion software would be needed in those platforms to fully support the format. However, having support for encoding and decoding IEEE 754 values should not be considered to be dependent on the availibility of a full IEEE 754 native library since it was estimated that a platform independent decode routine would take about 300 bytes of machine code.

E.5 Bounded Tables

When previously unseen content (such as strings, elements or attributes) is encountered during EXI encoding, it is always added to a string table or a grammar. The bounded tables feature sets an a priori bound on the sizes of the string table partitions and grammars. This feature is intended to improve the space efficiency of EXI processors. Assuming a bound on the sizes of strings in the document, this feature will allow the estimation of an absolute bound on space usage.

Fixing a processor's table sizes can negatively impact compactness in certain cases given that a string or grammar rule that would have been present under normal EXI rules may not exist. However, without this feature, it may be impossible for certain documents to be processed on devices with limited memory capabilities.

E.6 Grammar Coalescence

Schema-informed grammars are constructed primarily from structural constraints expressed in a schema (e.g., an XML Schema) by considering those events that are expected to happen at a certain state as being more likely to occur than other events. These primary events are assigned an event code of length 1 to ensure that they are represented in fewer bits. On the other hand, other events such as unexpected elements, unexpected attributes, unexpected end-of-elements, comments and processing instructions are considered less likely to occur relative to the primary events, and are thus assigned event codes of length 2 or 3 to reflect their occurrence expectancy.

A schema can be regarded as a template. It follows that a schema-informed EXI encoding defines a way of representing an instance of an XML infoset relative to a template. This aspect of schema as a template opens up a path to the proposed feature of coalesced grammars, whereby EXI events convey not only an atomic event (such as an element or an attribute) but also a sequence thereof in a single coalesced event. Based on the constraints expressed in a schema, these events are construed to occur more frequently together than not.

As an example, it may be possible to learn from a schema that the element <order> is always followed by the element <product>, which in turn is always followed by the element <description>. Based on this knowledge, it is possible to assign an event code to the sequence SE("order") SE("product") SE("description") by inserting a new, coalesced production into the grammar. This new production can be used in place of the existing productions for each event, thus using a single event code to represent them.

Note that this coalescing technique is not restricted to SE events; it applies to any sequence of events that can be shown to occur frequently, for which the use of a single event code can provide obvious benefits. For example, an SE event followed by multiple AT events can also be combined using a single event code. To improve coalescing, the lexicographical order currently defined for attributes in EXI may need to be revisited so that required attributes are placed before optional ones. This additional requirement will enable better grouping and, consequently, better compactness.

E.7 Byte-Aligned Mode

For use-cases that require very fast parsing/serialization speed, a mode to generate non-compressed, byte-aligned output is under consideration. Currently, the EXI event stream is either serialized in bit-packed mode, or in a transient byte-aligned format used for channels that gets fed into a conventional compression algorithm. It is expected that an output mode that preserves byte-aligned value representations would allow implementations to better exploit fast byte-aligned memory accesses and in particular allow high-speed serialization of value arrays.

Listed below are some of the approaches that are under consideration.

  1. Exposing the intermediate pre-compression byte-aligned format as a separate, user-visible mode
  2. The intermediate format as in approach 1, but with design changes to make it more suitable for fast parsing
  3. Modify the bit-aligned format to add padding before certain value types (such as value arrays), similar in spirit to ASN.1 PER byte-aligned mode
  4. A hybrid bit-packed/byte-aligned format, that would use the compact bit-aligned structure representation as currently specified, but with embedded, byte-aligned representations of values and value arrays. This aims to fully retain compactness of the bit-packed mode, while enabling fast(er) access to values / value arrays.

The various approaches are expected to differ in their impact on both compactness and processing efficiency.

E.8 Indexed Elements

Some use cases would benefit from the ability to jump to specific locations in an EXI stream and begin reading events at those locations without reading any data prior to that point in the stream. To address this requirement, a user or application may identify a set of elements in an EXI stream that are Indexed Elements. Indexed Elements are self contained, meaning their content has no dependencies on external events or any impact those events may have had on context sensitive structures, such as string tables and learned content models. Indexed Elements are also byte aligned to facilitate seeking to their location in an EXI stream using common stream implementations.

A variety of higher level functions can be implemented on top of Indexed Elements, including random access of EXI streams and accelerated sequential access of EXI streams using skip-pointers. As an example application, an electronic document system could choose to index all the pages in the document and store the page locations in a global index. Applications and users could then jump directly to page 500 of a large document and display it immediately without reading or storing any of the preceding pages of the document.

F Example Encoding (Non-Normative)

The WG has crafted a tutorial page EXI 1.0 Encoding Examples that explains the workings of EXI format using a simple example document. At the time of this writing, the page only shows a schema-less EXI encoding of the example. A schema-informed EXI encoding of the example is expected to be added to the page soon.

G Acknowledgements (Non-Normative)

This document is the work of the Efficient XML Interchange (EXI) WG.

Members of the Working Group are (at the time of writing, sorted alphabetically by last name):

The EXI Working Group would like to acknowledge the following former members of the group for their leadership, guidance and expertise they provided throughout their individual tenure in the WG. (sorted alphabetically by last name)