1.1 History and Design

EXI is the result of extensive work carried out by the W3C's XMLBinary Characterization (XBC) and Efficient XML Interchange (EXI)Working Groups. XBC was chartered to investigate the costs andbenefits of an alternative form of XML, and formulate a way to objectivelyevaluate the potential of a substitute format for XML. Based on XBC'srecommendations, EXI was chartered, first to measure, evaluate, andcompare the performance of various XML technologies (using metricsdeveloped by XBC[XBC Measurement Methodologies]), and then, if it appearedsuitable, to formulate a recommendation for a W3C formatspecification. The measurements results and analyses, are presentedelsewhere[EXI Measurements Note]. The format described in thisdocument is the specification so recommended.

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

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

EXI is compatible with XML at the XML Information Set[XML Information Set] level, rather than at the XML syntax level. Thispermits it to encapsulate an efficient alternative syntax and grammarfor XML, while facilitating at least the potential for minimizing theimpact 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 appearEMPHASIZED in this document, are to be interpreted as described in RFC2119[IETF RFC 2119]. Other terminology used to describe the EXIformat is defined in the body of this specification.

The termevent andstream is used throughout this document to denoteEXI event andEXI stream respectively unless the words are qualified differently to mean otherwise.

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

A set of one or more grammar productions that share the sameleft-hand side non-terminal symbol are often presented together annotatedwithevent codes that specify how events matching the terminal symbols of the associated productions are represented in the EXI stream as follows:

Section8.1 Grammar Notation introduces additional notations for describing productions andevent codes in grammars. Those additional notations facilitate concise representation of the EXI grammar system.

[Definition:]  In this document, the termqname is used to denote aQName^XS2.QName values are composed of an uri, a local-name and an optional prefix. Two qnames are considered equal if they have the same uri and local-name, regardless of their prefix values. In cases where prefixes are not relevant, such as in the grammar notation, they are not specified by this document.

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

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

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

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

When it is stated that strings are sorted in lexicographical order,it is done so character by character, and the order among characters is determined by comparing their Unicode code points.

Unless stated otherwise, when this specification indicates one type is derived from another type, it means the type is derived by extension or restriction, not by union or list. Similarly, when this specification uses the term type hierarchy, it is referring to the hierarchy of types derived from one another by extension or restriction

Note:

5.1 EXI Cookie

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

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

5.2 Distinguishing Bits

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

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

Systems that use EXI streams as well as XML documents can reliably look atthe Distinguishing Bits to determine whether to interpret a particularstream as XML or EXI.

5.3 EXI Format Version

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

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 previewversion. Final versions correspond to final, approved versions of the EXI format specification.AnEXI 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. The behavior of an EXI processor on an EXI stream with its first bit set to 0 followed by a version not corresponding to a version implemented by the processor is not constrained by this specification. For example, the EXI processor MAY reject such a stream outright or it MAY attempt to process the EXI body.Preview versions of the EXI format are useful forgaining implementation and deployment experience prior to finalizing aparticular 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 more4-bit unsigned integers representing the version number. The versionnumber is determined by summing this sequence of 4-bit unsignedvalues and adding 1 (one). The sequence is terminated by any 4-bit unsigned integer witha value in the range 0-14. As such, the first 15 version numbers arerepresented by 4 bits, the next 15 are represented by 8 bits, etc.

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

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

The following are example EXI format version numbers.

EXI processors conforming with the final version of thisspecification MUST use the 5-bit value 0 0000 as the versionnumber.

5.4 EXI Options

[Definition:]  Thefifthpart of the EXIheader is theEXI Options, which provides a way to specify theoptions used to encode the body of the EXI stream.[Definition:]  The EXI Options are represented as anEXI Options document, which is an XML document encoded using the EXI format described in this specification.This results in a very compact headerformat 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 theDistinguishing Bits.When EXI Options are present in the header, an EXI Processor MUST observe thespecified options to process the EXI stream that follows. Otherwise,an EXI Processor may obtain the EXI options using another mechanism.There are no fallback option values provided by this specification for usein the absence of the whole EXI Options part.

EXI processors MAY provide external means for applications or users tospecify EXI Options when the EXI Options document is absent.SuchEXI processors are typically used in controlled systemswhere the knowledge about the effective EXI Options is shared prior tothe exchange of EXIstreams. The mechanisms to communicate out-of-band EXI Options and their representation are implementation dependent.

The following table describes the EXI options that may be specified in theEXI Options document.

AppendixC XML Schema for EXI Options Document provides an XML Schemadescribingthe EXI Options document.This schema is designed to produce smaller headersfor option combinations used when compactness is critical.

TheEXI Options document isrepresented as anEXI body informed by the above mentioned schema using the default optionsspecified by the following XML document.An EXI Options document consists only of an EXI body, and MUST NOTstart with an EXI header.

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

Note that this specification does not requireEXI processors to read and process the schema prescribed for EXI options document (C XML Schema for EXI Options Document), in order to process EXI options documents. EXI processors MUST use the schema-informed grammars that stem from the schema in processing EXI options documents, beyond which there is no requirement as to the use of the schema, and implementations are free to use any methods to retrieve the instructions that observe the grammars for processing EXI options documents. Section8.5 Schema-informed Grammars describes the system to derive schema-informed grammars from XML Schemas.

Below is a brief description of each EXI option.

[Definition:]  Thealignment option is used to control the alignment ofevent codes andcontent items. The value is one ofbit-packed,byte-alignment orpre-compression, of whichbit-packed is the default value assumed when the "alignment" element is absent in theEXI Options document.The option valuesbyte-alignment andpre-compression are effected when "byte" and "pre-compress" elements are present in the EXI Options document, respectively.When the value ofcompression option is set to true, alignment of the EXI Body is governed by the rules specified in9. EXI Compression instead of the alignment option value. The "alignment" element MUST NOT appear in an EXI options document when the "compression" element is present.

[Definition:]  The alignment option valuebit-packed indicates that theevent codes and associated content are packed in bits without any padding in-between.

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

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

[Definition:]  Thecompression option is a Boolean used to increase compactness using additional computational resources. The default value "false" is assumed when the "compression" element is absent in theEXI Options document whereas its presence denotes the value "true".When set to true, theevent codes and associated content are compressed according to9. EXI Compression regardless of thealignment option value. As mentioned above, the "compression" element MUST NOT appear in an EXI options document when the "alignment" element is present.

[Definition:]  Thestrict option is a Boolean used to increase compactness by using a strict interpretation of the schemas and omitting preservation of certain items, such as comments, processing instructions and namespace prefixes. The default value "false" is assumed when the "strict" element is absent in theEXI Options documentwhereas its presence denotes the value "true".When set to true,those productions that have NS, CM, PI, ER, and SC terminal symbols are omitted from theEXI grammars, and schema-informed element and type grammars are restricted to only permit items declared in the schemas.A note in section8.5.4.4.2 Adding Productions when Strict is True describes some additional restrictions consequential of the use of this option.The "strict" element MUST NOT appear in anEXI options document whenone of "dtd", "prefixes", "comments", "pis" or "selfContained"element is present in the same options document.

[Definition:]  Thefragment option is a Boolean that indicates whether theEXI body is anEXI document or anEXI fragment. When set to true, theEXI body is anEXI fragment. Otherwise, theEXI body is anEXI document. The default value "false" is assumed when the "fragment" element is absent in theEXI Options documentwhereas its presence denotes the value "true".

[Definition:]  Thepreserve option is a set of Booleans that can be set independentlyto each enable or disable a share of the format's capacity determining whether or how certain information items can be preserved in the EXI stream.Section6.3 Fidelity Options describes the set of information itemsaffected by the preserve option.The presence of "dtd", "prefixes", "lexicalValues", "comments" and "pis" in the EXI Options document each turns on fidelity options Preserve.comments, Preserve.pis, Preserve.dtd, Preserve.prefixes and Preserve.lexicalValues whereas the absence denotes turning each off.The elements "dtd", "prefixes", "comments" and "pis"MUST NOT appear in anEXI options document when the "strict" element is present in the same options document.The element "lexicalValues", on the other hand, is permitted to occur in the presence of "strict" element.

[Definition:]  TheselfContained option is a Boolean used to enable the use of self-contained elements in the EXI stream. Self-contained elements may be read independently from the rest of the EXI body, allowing them to be indexed for random access. The "selfContained" element MUST NOT appear in anEXI options document whenone of "compression", "pre-compression" or "strict" elements are presentin the same options document. The default value "false" is assumed when the "selfContained" element is absent from theEXI Options documentwhereas its presence denotes the value "true".

[Definition:]  TheschemaId option may be used to identify the schema information usedfor processingthe EXI body. When the"schemaId" element in theEXI options document contains the xsi:nil attributewith its value set to true,no schema informationis used for processingthe EXI body (i.e. aschema-less EXI stream).When the value of the "schemaId" element is empty, no user defined schema information is used for processing the EXI body;however, the built-in XML schema types are available for use in 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 this informationMUST be communicated out of band.This specification does not dictate the syntax or semantics of other values specified in this field. An example schemaId scheme is the use of URI that is apt for globally identifying schema resources on the Web.The parties involved in the exchange are free to agree on the scheme of schemaId field that is appropriate for their use to uniquely identify the schema information.

[Definition:]  ThedatatypeRepresentationMap optionspecifies an alternate set of datatype representations for typedvalues intheEXI bodyas described in7.4 Datatype Representation Map.When there are no "datatypeRepresentationMap" elements in theEXI Options document, no Datatype Representation Map is used for processing the EXI body.This option does not take effect when the value of the Preserve.lexicalValues fidelity option is true (see6.3 Fidelity Options),or when theEXI stream is aschema-less EXI stream.

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

[Definition:]  ThevalueMaxLength option specifies the maximum length ofvalue content items to be considered for addition to the string table.The default value "unbounded" is assumed when the "valueMaxLength" element is absent in theEXI Options document.

[Definition:]  ThevaluePartitionCapacity option specifies the maximum number ofvalue content items in the string table at any given time.The default value "unbounded" is assumed when the "valuePartitionCapacity" element is absent in theEXI Options document.Section7.3.3 Partitions Optimized for Frequent use of String Literals specifies the behavior of the string table when this capacity is reached.

[Definition:]  Theuser defined meta-data conveys auxiliary information that applications may use to facilitate interpretation of the EXI stream.The user defined meta-data MUST NOT be interpreted in a way that alters or extends the EXI data format defined in this specification.User defined meta-data may be added to an EXI Options document just prior to thealignment option.

Note:

6.1 Determining Event Codes

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

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 assign anevent code for each one.See8.5.1 Schema-informed Document Grammar for the process used for generating the grammar productions below from the schema.

At the point in an EXI stream where the above grammar productions are in effect, theevent 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 5.0, and so on.

6.2 Representing Event Codes

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

Thei-th part of anevent code is encoded as ann-bit unsigned integer (7.1.9 n-bit Unsigned Integer), wheren is ⌈ log ₂ m ⌉ andm is the number of distinct values used as thei-th part of its own and all its sibling event codes in the current grammar.Twoevent codes are siblings at thei-th part if and only if they share the same values in all preceding parts. Allevent codes are siblings at the first part.

If there is only one distinct value for a given part, the part is omitted (i.e., encoded in log ₂ 1 = 0 bits = 0 bytes).

For example, the eightevent codes shown in theDocContent grammar above have values ranging from 0 to 5 for the first part. Six distinct values are needed to identify the first part of theseevent codes.Therefore, the first part can be encoded as ann-bit unsigned integer wheren = ⌈ log ₂ 6 ⌉ = 3. In the same fashion, the second and third part (if present) are represented asn-bit unsigned integers wheren is ⌈ log ₂ 2 ⌉ = 1  and ⌈ log ₂ 2 ⌉ = 1  respectively.

When the value of thecompression option is false andbit-packed alignment is used,n-bit unsigned integers are represented usingn bits. The first table below illustrates how theevent codes of eachevent matched by theDocContent grammar above are represented in this case.

When the value ofcompression option is true, or eitherbyte-alignment orpre-compression alignment option is used,n-bit unsigned integers are represented using the minimum number of bytes required to storen bits. The second table below illustrates how theevent codes of eachevent matched by theDocContent grammar above are represented in this case.

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 XMLprocessing instructions.In addition, there are many data-exchange use cases that do not require XML comments or DTDs.

Thepreserve option in EXI Options comprises a set of fidelity options, each of which independentlyenables or disables the format's capacity forthe preservation (or preservation level) of a certain type of information item.Applications can use thepreserve option to specify the set of fidelity options they require.As specified in section8.3 Pruning Unneeded Productions, EXI processors MUST use these fidelity options to pruneproductions that match the associated events 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 theEXI stream.

When qualified names[Namespaces in XML 1.0]  [Namespaces in XML 1.1] are used in thevalues of AT or CH events in an EXI Stream, the Preserve.prefixes fidelity option SHOULD be turned on to enable the preservation of the NS prefix declarations used by these values.Note, in particular among other cases, that this practice applies to the use of xsi:type attributes in EXI streams when Preserve.lexicalValues fidelity option is set totrue.

See section4. EXI Streams for the definition of EXI event types and their associatedcontent items.

7.1 Built-in EXI Datatype Representations

The following sections describe thebuilt-in EXI datatype representations used for representingevent codes andcontent items in EXI streams. Unless otherwise stated, individual items in an EXI stream are packed into bytes most significant bit first.

7.1.10 String

The String datatype representation is a length prefixed sequence ofcharacters. The length indicates the number of characters in thestring and is represented as an Unsigned Integer (see7.1.6 Unsigned Integer). If a restricted character set is defined for the string (see7.1.10.1 Restricted Character Sets), each character is represented as ann-bit Unsigned Integer (see7.1.9 n-bit Unsigned Integer). Otherwise, each character is represented by its Unicode[UNICODE]code point encoded as an Unsigned Integer (see7.1.6 Unsigned Integer).

EXI uses a string table to represent certaincontent items more efficiently. Section7.3 String Tabledescribes the string table and how it is applied to different contentitems.

7.1.10.1 Restricted Character Sets

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

Given the schema datatype, let the target datatype definition be the definition of the most-derived datatype that has one or more pattern facets immediately specified in its definition in the schema among those in the datatype inheritance hierarchy that traces backwards towardprimitive datatypes^XS2 starting from the datatype.If the target datatype definition is a definition for abuilt-in datatype^XS2, there is no restricted character set for the string value. Otherwise,determine the set of characters for each immediate pattern facet of the target datatype definition according to sectionE DerivingSet of Charactersfrom XML Schema Regular Expressions.Then, compute the restricted set of characters for the string value as the union of all the sets of characters computed in the previous step. If the resulting set of characters contains less than256characters and contains only BMP characters, the string value has a restricted character set and each character is represented using ann-bit Unsigned Integer (see7.1.9 n-bit Unsigned Integer), wheren is ⌈ log₂(N + 1) ⌉ andN is the number of characters in the restricted character set.

The characters in the restricted character set are sorted by Unicode[UNICODE] code point and represented by integer values in the range (0 ...N−1) according to their ordinal position in the set. Characters that are not in this set are represented by then-bit Unsigned IntegerN followed by the Unicode code point of the character represented as an Unsigned Integer.

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

Figure 7-1.String Processing Model

7.2 Enumerations

When thePreserve.lexicalValues option is false,enumerated valuesare encoded asn-bit Unsigned Integers (7.1.9 n-bit Unsigned Integer) wheren = ⌈ log₂m ⌉ andm is the number of itemsin the enumerated type. The unsigned integer value assigned to each item corresponds toits ordinal position in the enumeration in schema-order starting withposition zero (0).When there are more than one item that represent the same value in the enumeration,such value can be represented using the ordinal position of any items that represent the value.

Exceptions are for schemaunion datatypes^XS2 ,list datatypes^XS2, as well as QName or Notation and types derived therefrom by restriction. The values of such types are processed by their respective built-in EXI datatype representations instead of being represented as enumerations.

7.3 String Table

EXI uses a string table to assign "compact identifiers" to somestring values. Occurrences of string values found in the string tableare represented using the associated compact identifier rather thanencoding the entire "string literal". The string table is initially pre-populated withstring values that are likely to occur in certain contexts and isdynamically expanded to include additional string values encounteredin the document. The followingcontent items are encoded using astring table:

• uris
• prefixes
• uri andlocal-nameinqnames
• values

When a string value is found in the string table, the value is encodedusing 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 encodedas a String without using a compact identifier, only after whichthe string table is augmented by including the string value with an assignedcompact identifierunless the string value represents avalue content itemand fails to satisfy the criteria in effect by virtue ofvaluePartitionCapacity andvalueMaxLength options.

The string table is divided into partitions and each partition isoptimized for more frequent use of either compact identifiers or string literalsdepending on the purpose of the partition. Section7.3.1 String Table Partitions describes how EXI string table ispartitioned. Section7.3.2 Partitions Optimized for Frequent use of Compact Identifiersdescribes how string values are encoded when the associated partitionis optimized for more frequent use of compact identifiers. Section7.3.3 Partitions Optimized for Frequent use of String Literals describes how string values areencoded when the associated partition is optimized for more frequent useof string literals.

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

7.4 Datatype Representation Map

By default, each typed value in an EXI stream is represented using itsdefault built-in EXI datatype representation (seeTable 7-1).However,[Definition:]  EXI processors MAY provide the capability to specify alternate built-in EXI datatype representations oruser-defined datatype representations for specific schemadatatypes^XS2.This capability is called aDatatype Representation Map.

EXI processors that support Datatype Representation Maps MAY provide implementation specific means to define and install user-defined datatype representations. EXI processors MAY also provide implementation specific means for applications or users to specify alternate built-in EXI datatype representations or user-defined datatype representations for representing specific schema datatypes. As with the default EXI datatype representations, alternate datatype representations are used for the associated XML Schema types specified in the Datatype Representation Map and XML Schema datatypes derived from those datatypes. When there are built-in or user-defined datatype representations associated with more than one XML Schema datatype in the type hierarchy of a particular datatype, the closest ancestor with an associated datatype representation is used to determine the EXI datatype representation. For XML Schema datatypes with enumerated values, the encoding rule described in7.2 Enumerations is used as the representation when the closest ancestor datatype with an associated datatype representation has no enumerated values.

When an EXI processor encodes an EXI stream usinga Datatype Representation Map and theEXI Options part of the header is present, the EXI options part MUST specify all alternate datatype representations used in the EXI stream.An EXI processor that attempts to decode anEXI stream that specifies a user-defined datatype representation in the EXI header thatit does not recognize MAY report a warning, but this is not anerror. However, when an EXI processor encounters a typed value thatwas encoded by a user-defined datatype representation that it does not support, it MUSTreport an error.

The EXI options header, when it appears in an EXI stream, MUST include a"datatypeRepresentationMap" element for eachschema datatypeof which the descendant datatypes derived by restriction as well as itself arenot represented using the defaultbuilt-in EXI datatype representation.The "datatypeRepresentationMap" element includes two child elements.Theqname ofthe first child element identifies the schema datatype that is notrepresented using the defaultbuilt-in EXI datatype representationand theqname of thesecond child element identifies the alternatebuilt-in EXI datatype representation or user-defined datatype representationused to represent that type.Built-in EXI datatype representations are identified by the type identifiers inTable 7-1.

For example, the following "datatypeRepresentationMap" element indicates all values of type xsd:decimal are represented using the built-in exi:string datatype representation. In addition, all datatypes directly or indirectly derived from xsd:decimal by restriction that do not have a closer ancestor in the type hierarchy with an associated datatype representation are represented using exi:string.

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

It is the responsibility of an EXI processor to interface with a particular implementation ofbuilt-in EXI datatype representationsor user-defineddatatype representationsproperly. 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 withan implementation of built-in String datatype representation.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 tothe implementation of built-in String datatype representationwhile other EXI processors may already have a string value of the data so that it can pass the value directly tothe implementation of built-in String datatype representationwithout any translation.

As another example, the following"datatypeRepresentationMap" element indicates allvalues of the user-definedsimple typegeo:geometricSurfaceand the datatypes derived from it by restrictionare representedusing the user-defined datatype representation geo:geometricInterpolator:

    <exi:datatypeRepresentationMap xmlns:geo="http://example.com/Geometry">        <geo:geometricSurface/><geo:geometricInterpolator/>    </exi:datatypeRepresentationMap>

Note:

8.1 Grammar Notation

8.2 Grammar Event Codes

Each production rule in the EXI grammar includes anevent 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, theevent codes determine the value(s) by which each non-terminal symbol will be represented in the EXI stream.

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

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

Figure 8-1.Event code tree for ElementContent grammar

where theterminal symbolsare represented by the leaf nodes of the tree, and theevent code of each production ruledefines a path from the root of the tree to the nodethat represents the terminal symbol that is on the right-hand side of the production.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 eachevent 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.

8.3 Pruning Unneeded Productions

As discussed in section6.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 prunethe productions of which the terminal symbols represent the events that are not required from the grammars,improving compactness and processing efficiency.

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

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

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

Each time a production is removed from a grammar, theevent 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.

8.4 Built-in XML Grammars

This section describes the built-in XML grammars used by EXI when no schema information is available or when available schema information describes only portions of the EXI stream.

The built-in XML grammars are dynamic and continuously evolve to reflect knowledge learned while processing an EXI stream. Newbuilt-in element grammars are created to describe the content of newly encountered elements and new grammar productions are added to refine existing built-in grammars. Newly learned grammars and productions are used to more efficiently represent subsequent events in the EXI stream. All newly createdbuilt-in element grammars areglobal element grammars.

[Definition:]  Aglobal element grammar is a grammar describing the content of an element that has global scope (i.e. a global element). At the onset of processing an EXI stream, the set of global element grammars is the set of all schema-informed element grammars derived from element declarations that have a {scope} property ofglobal. Eachbuilt-in element grammar created while processing an EXI stream is added to the set of global element grammars. Each global elementgrammarhas a uniqueqname.

8.5 Schema-informed Grammars

This section describes the schema-informed grammars used by EXI when schema information is available to describe the contents of theEXI stream.Schema information used for processing an EXI stream is either indicated by the header optionschemaId, or communicated out-of-band in the absence ofschemaId.

Schema-informed grammars accept all XML documents and fragments regardless of whether and how closely they match the schema. TheEXI stream 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.

It is important to note that schema-informed and built-in grammars are often used together within the context of a singleEXI stream. While processing a schema-informed grammar, built-in grammars may be created to represent schema deviations or elements that match wildcards declared in the schema. Even though these built-in grammars occur in the context of a schema-informed stream, they are still dynamic and evolve to represent content learned while processing the EXI stream as is described in8.4 Built-in XML Grammars.

Figure 9-1.EXI Compression Overview

9.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 result in exactlyblockSize values in its value channels (see9.2.2 Value Channels), where blockSize is the block size of the EXI stream (see5.4 EXI Options). The final block containsless than the minimum set of consecutive events that result in blockSizevalues in its value channels.

9.2 Channels

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

Figure 9-2.Multiplexing EXI events into channels