FR2951038A1 - Efficient extensible markup language interchange bit stream processing method, involves re-aligning coding values to predicted binary size, validating prediction of part of binary size, and processing events corresponding to binary size - Google Patents

Abstract

The method involves collecting consecutive events coding values of bit stream by a collecting unit, and predicting binary size of collected coding values by a prediction unit. The coding values of the collected coding values are re-aligned to the predicted binary size by a re-aligning unit. Prediction of part of the binary size is validated by a validating unit. Events corresponding to the binary size are processed by a processing unit. Independent claims are also included for the following : (1) a device for processing bit stream, comprising a collecting unit (2) an information storing medium comprising a set of instructions to execute a method for processing bit stream (3) a computer readable program product comprising coding portions to execute a method for processing bit stream.

Description

The present invention relates to a method and a corresponding device for processing, generally decoding, a bit stream comprising coded events and corresponding in particular to an encoded structured document. It applies in particular to structured documents of the XML type (acronym for "eXtensible Markup Language" for extensible markup language) encoded in the form of an EXI (Efficient XML Interchange) or Fast Infoset type bitstream. An XML document is composed of elements, each element starting with an opening tag with the name of the element (for example: <tag>) and ending with a closing tag that also contains the name of the element ( for example: </ tag>). Each element can contain other elements or textual data. On the other hand, an element can be specified by attributes, each attribute being defined by a name and having a value. The attributes are placed in the opening tag of the element they specify (for example: <attribute tag = "value">). In a manner known per se, the XML syntax also makes it possible to define comments, processing instructions and escape sections.

We consider in the following that XML data are described in terms of Items "or" events ", each item or event can be an element start (for example <tag>), an end of element (for example < / tag>), an attribute (eg attribute = "value"), textual content, comment, processing instruction or escape section.

XML has many advantages and has become a reference language for storing data in a file or exchanging data. The XML language allows in particular to have many tools to process the generated files. In particular, an XML document can be edited manually with a simple text editor. In addition, as an XML document contains its built-in data structure, this document is very readable even without knowing the specification.

The main disadvantage of the XML syntax is to be very verbose. Thus the size of an XML document can be several times larger than the intrinsic size of the data. This large size of XML documents also induces a significant processing time during the generation and reading of XML documents. It also induces a significant transmission time.

To overcome these drawbacks, methods of compression and encoding of an XML document have been sought. The purpose of these methods is to encode the content of the XML document in a more efficient form, while allowing easy rebuilding of the XML document. This is particularly the case for binary formats such as EXI (format used as a basis for the standardization of a binary XML format by the W3C EXI Working Group - "World Wide Web Consortium", an organization producing standards for the Web) or Fast Infoset specified by ITU-T Rec. X.891 1 ISO / IEC 24824-1. These formats have the characteristic of taking into account a large number of structural information of the document in order to further compress the data. For example, the EXI recommendation, available through the document "Efficient XML Interchange (EXI) Format 1.0 - W3C Working Draft 28 July 2008", takes into account the order of appearance of the different events within a structured document for build one or more grammars that can encode the most frequent events on a small number of bits. A grammar is composed of a set of productions, each production comprising an XML event description, an associated coding value, and the indication of the next grammar to use. To code an XML event using a grammar, the output containing the most accurate description of the XML event is used. The encoding value contained in this output is used to represent the event in the encoded bitstream, and the information contained in the event and not described in the output is encoded in sequence. A grammar according to Efficient XML is scalable. In a certain number of cases, after the occurrence of an XML event already described by a grammar production (if it is not described by a production, it can not be encoded by the grammar), the grammar is modified to include a new and more efficient production corresponding to this XML event. This output can either contain a more accurate description of the event, decreasing the amount of information to be encoded to represent the event, or have a more compact encoding value. The coding values, or "codes", are expressed in the form of "priorities" having, generally, between 1 and 3 levels. Coding an encoding value amounts to coding the values of its priority. These values are usually expressed in one byte (8 bits) and thus manipulated by the encoder. However, each level can be coded on the minimum number of bits to be able to encode the highest value of this level associated with a grammar production. Also, for a level taking values from 0 to 6, three coding bits are used. To encode an XML document, a set of grammars is used. Some grammars are used to code the structure of the XML document. In addition, for each type of XML event present in the document (an XML element type being a set of events with the same name), a set of grammars is used to encode XML events of that type. Indication of the following grammar at the level of productions allows you to navigate within these grammars. A set of string or value dictionaries is also used to encode the event or attribute names, and other contents of the XML document. These dictionaries also evolve by incorporating new strings / values encountered in the document and coded. The grammar rules used can either be generic rules, common to all XML documents and built from the XML syntax, or be document type-specific rules, constructed from an XML Schema describing the structure of the document. this type of document. During decoding, the inverse process is used: the encoding value corresponding to an EXI event is extracted from the EXI bit stream, and makes it possible to identify the coded XML event as well as the additional information to be decoded. In addition, during decoding, the same rules for the evolution of grammars and string dictionaries are used, making it possible to have at any time a set of rules for grammars and dictionaries identical to the one used during coding. As an example, the following XML fragment is used to describe the encoding of an XML document using the EXI specification: <personname> <firstname> John </ firstname> <lastname> Smith </ lastname> < / person> At the beginning of the encoding of this fragment, since the encoder has not yet encountered a "person" event, here a <person> element start, a default grammar is created for this event. It is a grammar containing only generic productions. During the encoding of the "person" element, new productions will be created and inserted to make the grammar linked to the "person" element more efficient. The default grammar used to encode the content of the "person" element is as follows (simplified with respect to the Efficient XML specification, including using a single grammar to code the "person" element): EE events , SE, CH shown here (further events are provided in the EXI recommendation) used to describe ElementContent events: EE 0 SE (*) ElementContent 1.0 CH ElementContent 1.1 XML are called EXI events and are directly associated with the encoding values ( or "priorities") of the binary EXI flow. In particular, "EE" corresponds to the event of end of element, "SE (*)" corresponds an event of beginning of any element (generic, the name is not specified), and "CH" corresponds to a textual content event. During encoding, after receiving the event corresponding to the beginning of "person" element (SE (person)), and having it coded for example literally (or with the help of an appropriate grammar of higher level), the encoder selects the encoding grammar of the content of the "person" element, described above. Then, the encoder receives the element start event "firstname" (<firstname> corresponding to an EXI event SE (firstname)). The most accurate output that corresponds to this event in the above grammar is the second: SE (*) ElementContent 1.0 The encoder therefore encodes this event by inserting the "1.0" priority into the binary EXI stream. Since the first level of priority includes two distinct values ("0" and "1") among the productions of the grammar, this level can be coded on a bit, with the value "1". Similarly, the second priority level includes two distinct values and can be bit-coded with the value "0". The priority "1.0" is thus encoded here with the two bits "10". This coded data is thus initially generated on one or more bytes. According to various coding options available in the EXI recommendation, this coding value is then inserted, such that, in the EXI flow, it is in the form of one or more whole bytes (so-called "byte-aligned" option where each new coded value begins again on a new byte), or in a compacted form with only two bits (so-called "bit-packed" option where the coded values are concatenated to each other on a minimum number of bits to represent all the possible priorities) . As can be easily understood, the latter option produces a more compact version of the coded bitstream, but requires, in return, a slightly longer processing time to proceed with compaction (concatenation) during encoding, or realignment over time. bytes during decoding. Then, since the production does not specify the name of the element, "firstname" is encoded, for example literally using a specific format to the Efficient XML specification (similar to the UTF8 format). We then continue encoding the content of "firstname". In this design, we look for the production associated with this element. As no "firstname" element has yet been met, we create a "firstname" grammar from the default grammar mentioned above. The "firstname" element contains a text node for a single child. We encode this text node, for example literally. Once this encoded text node, we update the grammar of "firstname" by inserting a text production CH. Grammar "firstname" ElementContent: CH 0 EE 1 SE (*) ElementContent 2.0 CH ElementContent 2.1 Once the content of "firstname" is coded, the encoder modifies the grammar associated with the "person" element to adapt the grammar to the XML data encountered. For this, a new production is added to the grammar, this production corresponding to the beginning of element "firstname". This production is associated with the priority "0", and the other priorities are shifted to preserve the uniqueness of the priorities. It will be recalled here that the decoder acting symmetrically will be able to achieve similar priority (or index) offsets as the received data is decoded. Thus the grammar "person" becomes: Grammar "person" ElementContent: SE (firstname) ElementContent 0 7 SE (*) ElementContent 2.0 CH ElementContent 2.1 The following event of the XML fragment to be encoded is the beginning of the element "lastname". As for "firstname", this element is coded using the production: SE (*) ElementContent 2.0 since no production corresponding to the element "lastname" is found. Since the first priority level now has three possible values, it is coded on two bits, with the value "2". The second priority level is always coded on a single bit. The priority "2.0" is thus encoded here with the three bits "100". Depending on the option "byte-aligned" or "bit-packed" chosen, these priorities are either inserted on whole bytes, or compacted and concatenated.

The name of the element, "lastname", is then encoded, for example literally. Then the content of "lastname" is coded using the grammar associated with the element "lastname", to create if necessary during the first iteration, similar to what is described above for the grammar " firstname ".

Following the encoding of the "lastname" element, the "person" grammar is modified to add a production corresponding to the beginning of the "lastname" element (with shift of priorities), and it becomes: Grammar "person" "ElementContent: 30 Next, the end element event, corresponding to the end of the" person "element is encoded, using the output: SE (lastname) ElementContent 0 SE (firstname) ElementContent 1 EE 2 SE ( *) ElementContent 3.0 CH ElementContent 3.1 If, subsequently, in the XML document, the encoder encounters another similar "person" element, this element will be encoded from this grammar. Thus the first event corresponding to the content of the "person" element is the start event of the "firstname" element. This element is coded with the production: SE (firstname) ElementContent 1 Note that the production 3.0 SE (*) ElementContent also corresponds to this event, but is less precise (it does not specify the name "firstname" of the element ). This is the first production that is used for increased coding efficiency. The encoder therefore encodes the priority of this production, namely the value "1", which is coded on two bits (because taking values from 0 to 3), or "01". There is no need to encode the name of the element, since this is specified by the output and comes out of the initial literal encoding when the "firstname" element was encountered for the first time. The encoder then encodes the contents of the "firstname" element. Since a production specific to the start event of the "firstname" element already exists in the grammar, it is not necessary to add a new production to the grammar. The encoder then similarly encodes the start event of the "lastname" element, encoding only the "0" priority with the two bits "00". Thus, for the coding of the second "person" element similar to the first, the generated code is more compact, since it is no longer necessary to code the names of the elements contained in "person", nor literally (by coding the entire string), or even using an index. Thus, throughout the coding of an XML document, one navigates from one grammar to another to find the productions adapted to the coding of the XML events. This navigation is based on the XML event that has just been coded, and whose associated output indicates the next grammar to use.

The EXI recommendation also provides mechanisms to prepare, before coding or decoding, the grammars in whole or in part, from a file of structural description of documents, called XML Schema ("XML Schema").

If such an XML schema is available to describe the content of the "person" element, namely a "firstname" element and a "lastname" element, it is possible to build from the start the generated grammar after the end of the coding. first "person" element. However, if the schema further specifies that the elements "firstname" and "lastname" must be ordered inside the "person" element ("firstname" preceding "lastname"), it is possible to generate the following grammars to describe the content of the "person" element (always in a simplified way compared to the Efficient XML specification). ElementContentl: SE (firstname) ElementContent2 0 EE 1.0 SE (*) ElementContentl 1.1 ElementContent2 1.2 ElementContent2: SE (lastname) ElementContent3 0 EE 1.0 SE (*) ElementContent2 1.1 ElementContent2 1.2 ElementContent3: EE 0 SE (*) ElementContent2 1.0 ElementContent2 1.1 These grammars use the known order of appearance of the elements "firstname" and "lastname" to separate the productions in several grammars and to reduce the number of productions per grammar, and consequently the number of bits necessary to code a priority . These grammars can even be reduced if deviations from the schema are not accepted. A deviation is the presence of an XML event not described by the schema. It may be the presence of an XML element other than those described by the schema, or the presence of an XML element described by the schema, but in a place not provided for by the schema. When using a schema to construct the EXI grammars, a first mode, the deviation mode, makes it possible to take these deviations into account and to code them. Another mode, the strict mode, does not allow these deviations and does not allow to encode a document containing such a deviation. In this last mode, it is thus possible to get rid of so-called "generic" productions (such as SE (*)) useful for dealing with unexpected events) and those that will not be realized.

Also, in strict mode, the grammars become: ElementContentl: SE (firstname) ElementContent2 0

ElementContent2: SE (lastname) ElementContent3 0

ElementContent3: EE 0 In this case, since each grammar contains only one priority, this priority does not need to be coded. Thus, the set of events describing the content of the "person" element as described above is encoded in zero bit (all events can be predicted safely) and can be decoded quickly by prediction.

The decoding of a bit stream resulting from such encodings or access to a part of the encoded document is generally achieved by successively accessing the events, for example EXI, composing the bitstream and then decoding them one after the other. In the case of activating the "bit-packed" coded data compaction option, a realignment of the coded data on the byte boundaries is then carried out in order to be manipulated by the decoder and compared with other data. manipulated, in the same form, by this decoder. The programming interfaces SAX ("Simple API for XML" in English, or "Simple programming interface for XML" in French) and StAX ("Streaming API for XML" in English, or "Programming interface as you go XML "in French) allow this EXI event access by EXI event. This sequential decoding introduces long processing times, mainly because a new EXI event will only start to be decoded when the previous EXI event has been fully decoded. To improve the efficiency of the decoding, it has been possible to use current processors having several processing units that can operate in parallel (for example multi-core processors). Such processors are expensive and sometimes not integrable in small equipment. Recently, the introduction of single, multiple data instructions, otherwise known by the acronym SIMD for "Single Instruction Multiple Data", has opened new perspectives for parallel processing. The SIMD instructions, implemented in particular in the AltiVec instructions of the PowerPC processors or the MMX or SSE instructions of the Pentium processors, make it possible to perform, in a single instruction cycle, operations on several different operands. Note that such instructions can be implemented on each core of a core processor to improve computational performance. These SIMD instructions could thus be used, as described by the publication US 2008/033974, to accelerate the decoding of XML documents using a parallel bit stream technique, also known as Parabix ("Parallel bit streams for XML ").

This technique performs the decoding of an octet-aligned bitstream (that is, substantially according to the "byte-aligned" option, because the data is encoded in UTF-8 mode) and implements the steps following: - transformation of the coded stream of octets into eight bit streams. Thus, from a stream of 128 bytes, eight 128-bit streams are obtained, each bit stream containing the bit placed at a given position for each of the 128 bytes. This transformation can be performed according to the "inductive doubling" principle of recursively dividing the stream by two: each byte is split into two half-bytes, the half-bytes being grouped together to obtain two streams of 128 half-bytes; then the operation is repeated, but with twice the size, to obtain four streams of 128 quarter bytes; finally, a new repetition makes it possible to obtain the eight streams of 128 eighths of bytes, that is to say 128 bits; - generation of lexical flows describing the content of the XML stream.

Thus, there is a lexical flow which corresponds to the character "<", used in XML to note the beginnings of elements. These lexical flows are calculated from the eight bit streams; decoding the XML stream from the eight bit streams and lexical streams. Lexical flows are used to determine the limits of XML events. From these limits and the eight bit streams, events representing the XML content are generated. The acceleration of decoding in this method lies mainly in the operations of determining XML lexical markers that can be performed on 128 bytes in parallel, using few operations for each lexical marker. In addition, these determinations share steps that can be factored, which further reduces the computations. These same single multiple-data instructions can also be used during encoding to parallelize certain operations on multiple operands.

The SIMD instructions are therefore an effective means of accelerating processing such as structured document coding or decoding. However, these instructions are not suitable for encoding formats in which the encoded data is compacted (for example the "bit-packed" option) and are therefore not aligned with the byte boundaries. This misfit is evident during decoding since the decoder does not know the number of bits used for each coded data until it has decoded the previous data. Indeed, as explained above, the number of bits used depends on the number of productions in the current grammar, the latter being a function of the production used during the coding of the previous data. The decoder is thus unable to simultaneously process two or more successive coded data.

The aim of the invention is to overcome these disadvantages of the prior art in order to make it possible, in a grouped manner, to compact or realign a plurality of coded data, in particular using instructions of the SIMD type. This results in accelerated processing (decoding, access to part of the encoded document).

For the purpose of this invention, a method for processing a bit stream corresponding in particular to a coded structured document, the bit stream comprising event coding values, the method comprising the steps of: - recovering a plurality consecutive event coding values of said bit stream; predicting the binary size of said recovered coding values; realigning, with the aid of said predicted bit sizes, the encoding values of said recovered plurality to correspond to a given bit alignment; 30 - validating the prediction of at least a portion of the bit sizes; - handle the events corresponding to the binary sizes whose prediction is validated.

According to the invention, one seeks to know the encoding values which have been correctly decompacted, that is to say the realignment with the format used by the decoder. In fact, this decompacting then allows the decoder to find, in the grammars or decoding dictionaries, the corresponding EXI and XML events without difficulty. To know these values, one makes assumptions about their compacted size (prediction of the sizes) which one validates generally using the values of coding themselves. Indeed, the compacted size of a value depends on the type of value to be encoded. In particular, in the case of a priority value, the compacted size depends on the grammar containing the production corresponding to this priority. But the grammar used depends on the previous event, so the value of the previous priority. Thus, to verify the size prediction of a value, it may be sufficient (in the case of a priority) to check the prediction of the previous value.

Thanks in particular to the SIMD instructions, the operations aimed at the realignment of the values can be carried out simultaneously on several values, without being limited by the sequential browsing of the grammars and decoding tables normally necessary to know the compacted size of the following value. The decoding of the EXI flows is thus accelerated.

Furthermore, the processing of the values thus delimited in the EXI flow can be carried out in a conventional manner, by directly recovering the realigned values, for example to decode them or to directly access a desired part of the encoded document. In a main embodiment of the invention, the method further comprises the steps of: - predicting retrieved encoding values so as to form a predicted plurality of encoding values, said encoding values of the predicted plurality being according to said given bit alignment; and - checking the prediction of the encoding values by comparing the predicted and realigned pluralities so as to validate the prediction of at least a portion of the bit sizes.

Validation of size predictions is carried out here by means of a verification of certain coding values, generally the grammar priorities. In one embodiment, the method comprises associating, with at least one decoding table of said bit stream, a prediction sequence whose inputs comprise at least one event coding value and a binary size associated with this encoding value; and said predictions of coding values and bit sizes are retrieved from said prediction sequence associated with the current decoding table. Access to predictions is thus immediate for a set of events to be decoded. In particular, such prediction sequences make it easy to obtain these predictions independently of the size of the operands of the SIMD instructions used. In particular, said decoding tables are grammars (preferably EXI) corresponding to a type of structured element. According to a particular characteristic, the method comprises a step of constructing said sequence of predictions from at least one simple prediction associated with at least one input of the decoding tables, said simple prediction providing another decoding table entry (and therefore another coding value). By way of example, in the EXI case, such an entry may be a production. A simple prediction includes in particular the indication of an event (or a corresponding entry of the tables) likely to occur after the entry concerned, for example an EXI production which would follow a first production. These simple predictions can in particular be updated according to the result of the predictions made according to the invention. Thanks to these simple productions, the constitution, or even the updating, of the prediction sequences proves to be simple.

In particular, said construct comprises traversing a plurality of decode table entries by navigating with simple predictions associated with said traversed entries, and adding said simple predictions traversed to said prediction sequence. This realization of the prediction sequences useful for simultaneous treatments with SIMD instructions thus remains of simple complexity. In particular, said path is performed until a simple prediction of a decoding table is obtained which indicates an input of another decoding table to which a sequence of predictions is already associated. This avoids an infinite looping generating an infinite sequence. In addition, this arrangement optimizes the invention since, in the long run, the entries of the decoding tables will each be in a single prediction sequence.

According to one characteristic, the method comprises updating said sequence of predictions according to said verification. In particular, said prediction sequence is updated by splitting at a coding value for which prediction statistics information reaches a threshold value. Typically, this coding value corresponds to an event that is too often poorly predicted. This arrangement makes it possible to optimize the prediction sequences for a better decoding of EXI flows. According to another characteristic of the invention, at least one bit shift mask is calculated for the realignment of the set of coding values. In particular, a bit shift mask is stored in memory, associated with said sequence of predictions. The mask is notably stored in a register of the operand size of the SIMD instructions. Such a mask thus makes it possible, in one instruction cycle, to realign several encoding values of the flow EXI. According to another characteristic of the invention, said processing comprises the decoding of the first recovered coding value whose prediction is erroneous, using link information associated with an input of said sequence of predictions. This arrangement makes it possible to continue the decoding efficiently even though a prediction error may have occurred, since a decoding table entry is thus recovered for the incorrectly predicted value and the subsequent decoding of the EXI flow can be carried out either conventionally, either by a new implementation of the invention.

According to still another characteristic of the invention, said prediction sequence comprises a number of entries which is a multiple of the number of values contained, according to said binary alignment of the predicted plurality, in a single multiple data instruction operand ( SIMD).

Thus, decoding can be done optimally (in terms of speed) because, at all cycles of calculation, the Multiple Data Unique Instructions (SIMD) will handle a maximum number of events, as long as the predictions are validated. In one embodiment of the invention, said verification comprises the application of a prediction mask so as not to take into account at least one coding value during said comparison. In particular, said plurality of retrieved coding values is stored, in realigned form, in a second single multiple data instruction register. In particular, said verification implements at least one single multiple data instruction (SIMD) having, for first operand, said second register storing said plurality of realigned recovered coding values and, for second operand, a third register storing said plurality of values predicted coding, so as to obtain a comparison indication for each coding value.

In particular, said checking comprises the application of a prediction mask to the result of said single multiple-data instruction, so as to delete said comparison indication for at least one coding value. This arrangement allows the implementation of the invention itself for the values for which the value prediction is not used, typically content values. The mask therefore excludes such values for comparison. In one embodiment of the invention, the realignment of the encoding values implements at least one bit-shift multiple data instruction (SIMD). In particular, the method includes concatenating the predicted bit sizes in a first single data multiple instruction register (SIMD). Also, it is contemplated that the bit shift values for each retrieved code value are calculated using at least one single multiple data instruction (SIMD) applied to said first register. The use of the SIMD instructions in most calculations leading to realignment provides faster decoding since, in one instruction cycle, bit shift is determined for all events of said plurality. By way of example, current SIMD instruction registers have a size of 128 bits, allowing, for example, to realign sixteen coded events in one cycle. In another embodiment, said realignment implements a plurality of single data multiple instructions (SIMD) capable of progressively aligning the retrieved coding values, by iterative shifting of subgroups of successive coding values. The iteration is naturally stopped when the alignment obtained corresponds to that of the predicted coding values, for example when each recovered event is now represented on one byte.

In particular, the subgroups are divided in two from one SIMD iteration to the other. This arrangement provides a simple implementation of the realignment using existing SIMD instructions on current processors. In a simplified embodiment of the invention, said validation comprises comparing at least a portion of the recovered bitstream with a predefined structure, and, in the case of a positive comparison, using a prediction sequence associated with said predefined structure. to predict the bit sizes. This configuration simplifies the validation of predictions by the prior use of a predefined structure. Indeed, if the binary values recovered from the stream are similar, at least in part (where they prove to be relevant, using masks for example), to a known structure, then it is intended to directly use the sequence of predictions attached to this structure and to consider its content as now validated, especially to know concretely the sizes for unpacking / realignment. Thus, subsequent checks on predicted values are avoided.

This provides a faster and more efficient mechanism, in particular allowing faster access to specific locations of a structured coded document. Correlatively, the invention is directed to a device for processing a bit stream comprising event coding values of a structured document, the device comprising: a means capable of recovering a plurality of consecutive event coding values said bit stream; prediction means for predicting the bit size of said retrieved code values; realignment means adapted to realign, using said predicted bit sizes, the encoding values of said recovered plurality to correspond to a given bit alignment; a validation means able to validate the prediction of at least a portion of the bit sizes; a processing module for processing the events corresponding to the binary sizes whose prediction is validated. The decoding device has characteristics and advantages similar to the decoding method according to the invention. Optionally, the device may comprise means relating to the characteristics of the decoding method set forth above. In particular, the prediction means is also able to predict retrieved coding values so as to form a predicted plurality of coding values, said coding values of the predicted plurality being according to said given bit alignment; and the validation means is adapted to verify the prediction of the coding values by comparison of the predicted and realigned pluralities so as to validate the prediction of at least a portion of the bit sizes. In particular, the device may comprise single multi-data instructions and associated registers for simultaneously storing information (encoding values, predicted sizes, predicted values, bit shift masks) relating to a plurality of successive encoding values to treat. In one embodiment, the device comprises decoding tables with associated prediction sequences whose inputs comprise at least one event coding value and a bit size associated with this coding value. In particular, the device comprises simple predictions associated with inputs of the decoding tables and informing another decoding table entry, and means for constructing such a sequence of predictions from simple predictions. An information storage means, possibly totally or partially removable, readable by a computer system, comprises instructions for a computer program adapted to implement the processing method according to the invention when this program is loaded and executed by the computer system. A microprocessor readable computer program comprises portions of software code adapted to implement the processing method according to the invention, when loaded and executed by the microprocessor.

The information storage means and computer program have characteristics and advantages similar to the processes they implement. Thanks to the invention, the binary stream decoding, for example of the EXI type, is improved by decompressing, in a group of instructions, a plurality of EXI events coded in compacted form ("bit-packed"). Other features and advantages of the invention will become apparent from the following description, illustrated by the accompanying drawings, in which: FIG. 1 shows an example of EXI grammars embodying the present invention; FIGS. 2a to 2c illustrate the constitution of an exemplary bit stream to be processed by the invention, as well as such an example before and after decompacting; FIG. 3 represents, in the form of a flow chart, general decoding steps according to the invention; FIG. 4 represents, in the form of a flow chart, steps for updating a simple prediction according to the invention, implemented during the decoding of FIG. 3; FIG. 5 represents, in the form of a flow chart, steps of construction of prediction sequences according to the invention, implemented during the decoding of FIG. 3; FIG. 6 illustrates a sequence of predictions according to the invention for the example of FIG. 2; FIG. 7 represents, in the form of a flow chart, decoding steps of the invention implemented during the general decoding of FIG. 3; FIGS. 8a to 8h illustrate the decoding operations of FIG. 7 for the example of FIG. 2; FIG. 9 represents, in the form of a flow chart, steps for updating the prediction sequences according to the invention; and FIG. 10 shows a particular hardware configuration of a decoding or encoding device suitable for carrying out the method according to the invention. The present invention is in particular implemented for the decoding of a bit stream, of the EXI type in the following description, corresponding to an encoded XML structured document, the bit stream comprising event coding values, the method comprising the steps of: - recovering a plurality of consecutive event coding values from said bit stream; predicting the binary size of said retrieved encoding values, and optionally predicting retrieved encoding values to form a predicted plurality of encoding values; realigning, with the aid of said predicted bit sizes, the coding values of said recovered plurality to correspond to a given bit alignment, which may notably be that of the coding values of the predicted plurality; - Validate the prediction of at least a portion of the bit sizes, for example by checking the prediction of the coding values by comparison of the predicted and realigned pluralities; - handle the events corresponding to the binary sizes whose prediction is validated. By means of unique instructions with multiple data (SIMD) in particular, these steps leading to realignment and those possibly verification can be conducted simultaneously on a large number of coded events. As will be discussed hereinafter in detail, a key element of the efficient decoding according to the invention typically using SIMD instructions is the prior determination (by prediction) of the compacted sizes of the coding values, in order to identify each of the encoding values in the EXI flow and to decode the events corresponding to these values, at one time. The realignment of the coding values with those predicted makes it possible to verify them by comparison in order to deduce from them whether the predictions are accurate and therefore whether the predicted sizes are also accurate. Thus all the values which precede the first badly predicted value have been correctly delimited in the EXI bit stream, and this simultaneously thanks to the SIMD instructions. The decoding of the events corresponding to these delimited values can then be carried out in a conventional manner by matching these values with the priorities of the EXI grammars or the indexes of the decoding dictionaries.

It is therefore found that the exact prediction of all the coding values can be optional, the main one being to predict the size used in the EXI flow to code this value. It is interesting, to validate the prediction, to have a certain number of values from which we can obtain a certain prediction. This is the case of the priorities used for EXI productions, unlike the content associated with the events (value of an attribute for example) which are generally highly variable. In the preferred embodiment of the invention, the EXI grammars are adapted, as illustrated in FIG. 1, to allow the generation of predictions. As a reminder, the EXI grammars 10 include productions 11 which associate an event EXI 12 (corresponding to an XML event type) to a coding value 13 (or "priority"). In FIG. 1, production 11 is also associated with so-called "simple" predictions 14 which, for the majority of productions, indicate the production used after this first production to treat the event of the same depth following that treated. by this production. The "depth" here has the same meaning as the "depth" of the XML elements within the XML document 1. Each simple production prediction 14 contains statistical information (not shown) on the production (s) actually used during the occurrences of For example, the simple production prediction model 14 used is a system with two states of probability and a prediction. Both states are "unlikely" and "very likely".

The statistical data can be collected initially from the document EXI 2 to be decoded or through the coding / decoding of XML data similar to the data to be encoded / decoded. This statistical data can also be initialized from an XML schema. In the context of a preferred mode of implementation, it is limited to recover the statistical data as the decoding EXI data. The main advantage is a very low cost in terms of computational complexity and processing time while maintaining interesting predictive performance. Thus, at the beginning of the decoding, the initial state of a simple prediction 14 is "unlikely" with no associated production.

Then during the decoding, when a production is used, the update of the simple prediction is as follows: - if this production used corresponds to that of the simple prediction 14 associated with the previous production, the state of this simple prediction goes from "unlikely" to "very likely", or stays at "very likely"; - if this production used does not correspond to that of the simple prediction and the state is "unlikely", then the prediction model replaces the old production predicted by this new production, with an "unlikely" associated state . It is also the treatment that is carried out if the model did not contain production because of the initial state for example; - finally, if this production does not correspond to that of the simple prediction 14 but that the state is "very probable", the state passes to "not probable". In this model, the simple contained production 14 is the one that is returned when an algorithm looks for a simple production starting from the current production 11. In a variant, the contained production is returned only if the state is at "very probable "(no prediction then being made since this current production 11 for an" unlikely "state). This modeling of simple predictions 14 makes it possible to memorize and preserve a production frequently used in a particular circumstance. However other more complex models can be implemented, for example by keeping a list of the last productions used following the current production 11 and by returning the most used production. In this case, each simple prediction 14 contains one or more probable productions, possibly with corresponding probability ratios. Still with reference to FIG. 1, for each production 11 corresponding to an EXI or XML event having a value or a content (this is the case for attributes that take a value, textual contents, elementary beginnings, the name of which is not specified, or comments and processing instructions), a simple prediction 15 relating to this content is associated with the production 11.

In a particular embodiment of the invention, only events corresponding to a textual value or an attribute whose name is specified have associated simple content predictions. Indeed, other events are either too infrequent to be interesting to treat (especially for comments or treatment instructions), too variable to be able to make correct predictions about their content and especially about the size (This is the case of events representing an attribute whose name is not specified). For productions 11 corresponding to a textual value or attribute, the simple content predictions are composed of a state and the type of encoding for the textual value. As for simple production predictions 14, this state can for example take two values "unlikely" and "very likely". The type of encoding shown is either the local index table, the global index table, or the length of the string in the case of literal encoding.

The updating of the simple content predictions is similar to that of the simple production predictions. As will be seen later, the invention provides efficient EXI flow decoding by simultaneously delimiting several coding values in said EXI flow, since their binary size in the EXI flow can be predicted.

Simple production predictions, being more reliable, will be used to validate size predictions. As illustrated in FIG. 1, a simple prediction 16 is also associated with each grammar representing the beginning of the content of an element (that is, the grammar used after processing the element start tag opening said element. ). This prediction concerns the production used to process the first event that represents part of the content of this element. In our example, this is the AT event.

The updating of this simple prediction 16 is similar to that of the simple predictions 14 and 15 described above.

Finally, to improve the prediction performance according to the invention, a sequence of predictions 17 is associated with each of the grammars representing the beginning of the content of an element. This prediction sequence 17 lists in particular simple prediction information for several consecutive events, here AT (title), then SE (firstname), etc.

As will be described hereinafter with reference to FIG. 5, this prediction sequence 17 is constructed, for grammar 10, from simple predictions 14, 15 and 16.

According to one embodiment of the invention, the prediction of the bit sizes of the event coding values is carried out using this prediction sequence 17.

A prediction sequence 17 consists of a set of information (a more detailed example of which is provided below with reference to FIG. 6).

The first of these information is a list of bit sizes 20 of encoding values corresponding to the events predicted in the sequence, in the compacted format used in EXI binary coding

20 (providing the flow EXI 2). The binary size of an encoding value is for example the minimum number of bits needed to encode the set of encoding values. As previously explained in relation to the EXI priorities, this size can be the sum of the minimum number of bits to code

the set of three priorities of the same grammar: 25 L [log2 (number of priorities i) 1 where [1 is the upper integer value. i = 1,2,3 The second of this information is a list of predicted coding values 21. These encoding values are stored in the format in which the decoder manipulates them, typically each value being expressed in one byte.

These values correspond, in the case of EXI structural events, to the corresponding priorities 13. Note that for some values, there may not be a predicted value because the value does not affect the subsequent decoding, only the knowledge of the bit size of the compacted coding value is necessary. This is the case, for example, for values representing a character, or for values representing an index in a table of values.

The third of this information is a set of links 22 (for example computer pointers) to productions 11 or grammars 10 corresponding to the coding values 21. These links allow the decoding algorithm to restart when a prediction error occurs, for example, to the last correctly predicted production. In particular, it can be provided that only the coding values 21 corresponding to a priority have such associated information. Finally, for each sequence of predictions are associated statistics (not shown) indicating the relevance of this sequence. These statistics are described later with reference to FIG. 9 during the updating of the prediction sequences. In the rest of the description, we are interested in the decoding of an EXI 2 stream coded in "bit-packed" mode for which the decompacting or re-alignment of the coding values is carried out using SIMD instructions relating to operands. for example, 128 bits. This makes it possible to simultaneously decompose 16 values of 8 bits (that is to say 16 bytes in total). However, there is no difficulty for those skilled in the art to extend the invention to different operand sizes and / or decompact size formats different from 8 bits. For the sake of simplicity of explanation, the following description is based on an example of decoding of 8 values, that is to say that the number of values of this example has been halved compared to the algorithms described. . However, extending this example to an example of 16 values is immediate. FIG. 2a illustrates the example for the rest of the description, by listing eight types of values (first column) present in the EXI 2 stream (coded with the "bit-packed" option) that we wish to uncompress simultaneously before decoding. The second column informs the bit size of the corresponding coding values in the flow EXI 2. FIG. 2b shows the flow EXI with these eight values 30. For example, the first coding value is "001", the second is "001". 00 ", the third" 0100 ", etc. The indications "+" and "-" below allow to delimit each of these eight values (up to the symbols "." Which designate the continuation of the flow EXI which can initially be loaded in memory). In order to be processed for decoding, these coding values must be decompacted to obtain a flux similar to the flux illustrated in FIG. 2c. In this stream, each encoding value was realigned on one byte (8 bits). This realignment requires the introduction of alignment bits whose value is '0' (indicated in the stream realigned with "."). We will now describe, with reference to FIG. 3, a general decoding algorithm according to the invention.

In a first step E100, it is tested whether there remains data to be decoded, that is to say coding values (or coded events) in the flow EXI 2. If this is not the case, the algorithm ends in step E110. If, on the other hand, there are still events to be decoded, the algorithm continues in step E120 by testing whether a prediction sequence 17 is associated with the current grammar (that is, with the grammar to be used for decoding). the next value). If this is the case (yes output of step E120), the algorithm continues in step E130 by performing the decoding provided by the invention. This decoding uses the prediction sequence 17 to simultaneously decompose a set of encoding values 30, including the eight values of our example above. This decoding is described below with reference to FIG. 7. After this step, the algorithm returns to step El 00 to process subsequent data to be decoded.

In the case where no sequence 17 is detected (non-output of step E120), the algorithm continues in step E140 by testing whether a simple prediction 14, 15 or 16 is available.

Preferably, this test is carried out as follows. First, the algorithm checks whether the current grammar corresponds to the beginning of the content of an XML element. If this is not the case, no simple prediction 14, 15 or 16 is available. If so, the algorithm checks whether a simple prediction 16 is associated with this grammar 10. In a variant, the test also looks for simple predictions for a current grammar that does not correspond to the beginning of the content of an element. In such a case, since no simple prediction 16 is associated with such a grammar 10, the search is made from the last production used: the algorithm checks whether a simple prediction 14 or 15 is associated with the last production. used. If a simple prediction 14, 15 or 16 is available, the algorithm continues in step E150, which proceeds to the construction of a sequence 17 of predicted outputs (for the current grammar) from this simple prediction 14, 15 or 16. This step is described in more detail below, with reference to FIG. 5. After step E150, the algorithm uses the prediction sequence 17 thus constructed to perform a decoding according to the invention during the first time. step E130. If no simple prediction 14, 15 or 16 is available, the algorithm continues in step E160 in which a conventional decoding is performed. Such a conventional decoding makes it possible, of course, to update (step E170) the simple predictions 14, 15 or 16 by modifying, for example, the "very probable" or "unlikely" states mentioned above. This update makes it possible to add simple predictions for productions 11 or grammars 10 that did not have any. With reference to FIG. 4, this update E170 comprises a first step E200 consisting of obtaining the production used during the conventional decoding E160 and that corresponding to the simple prediction 14, 15 or 16 to be updated. In the next step E210, the statistics of the simple prediction 14, 15 or 16 are updated.

Then, during step E220, the list of predicted productions is updated. In the preferred embodiment of the invention, for both simple production predictions and simple content predictions, these two steps E210 and E220 are merged. Returning to FIG. 3, after the update E170 of the simple prediction associated with the previous production 11 or the current grammar 10, the decoding continues in step E100 by taking into account the following data. Referring now to FIG. 5, step E150 for constructing a new prediction sequence 17 for a grammar 10 is described. It will be recalled here that a prediction sequence 17 comprises a list of bit sizes 20 corresponding to the EXI 2 stream compact format, a list of predicted coding values 21 each stored in an uncompressed format, for example on a byte, and a set of links 22. When starting the algorithm for constructing a sequence predictions 17, a grammar 10 corresponding to the beginning of the content of an XML element is selected. This grammar 10 is the initial current object for the algorithm. However, in other embodiments of the invention, the adaptations of which are within the abilities of those skilled in the art, other types of objects (in particular other grammars or productions) can be selected at startup. of this algorithm. The first step E300 consists in obtaining the simple prediction (s) 14, 15, 16 associated with the current object. In the case of a element content start grammar, it is the simple production prediction associated with this grammar 10. In the case of a production 11 corresponding to an event without content, This is the simple prediction 14 of production associated with this production. In the case of a production 11 representing a textual content or an attribute whose name is specified, it is the simple prediction of content corresponding to the value, and the simple production prediction associated with this production. . In the next step E310, this or these predictions 14, 15, 16 are added to the prediction sequence 17, while keeping the order in which they are used for the processing of the EXI 2 flow. This addition consists in informing if possible, the bit size 20, the predicted coding value 21 and the link 22. In particular, for a simple production prediction 14 or 16, the following information is used: the bit size 20 of the value to be decoded in the format used during the coding. This "compacted" bit size is a function of the number of possible productions at the prediction level, as described in the EXI specification; the predicted coding value 21 which is the priority value corresponding to the predicted production; and - the link 22 which points to the grammar containing the predicted output (if the production has been erroneously predicted, it will be necessary to use this grammar to start again the normal decoding of the document EXI 2).

For a simple content prediction, the information depends on the encoding type of the value: indexed value or literally encoded value. In the case of an indexed value (locally or globally), two values are predicted and inserted in the sequence 17: a value corresponding to the indication of an indexed value, and an index value. For the indicative value, the following information is used: the bit size of the value to be decoded which is generally 8 bits; the predicted coding value 21 which is the one used to encode the type of index used: 0 for a local index, 1 for a global index; and - no link is associated. For the index value, the following information is used: the bit size of the value to be decoded which depends on the number of values contained in the index; the predicted value 21 which is not defined. It will therefore not be taken into account in the verification of the prediction according to the invention, as illustrated hereinafter with the notion of a mask of values; and - no link is associated. In the case of a literal value, several values are predicted: a value corresponding to the length of the string and a set of values representing each character of the string. For a length of the string, the following information is used and stored in sequence 17: the bit size of the value to be decoded which is the number of bits necessary to encode that length; the predicted value 21 is the length of the chain; 15 - no link 22 is associated. For each character, in the preferred implementation, the following information is used: the bit size of the value to be decoded which is generally 8 bits; 20 - the predicted value 21 which is partially defined: it must be less than or equal to 127. Indeed, only the characters whose value is less than or equal to 127 are encoded on 8 bits. Characters with a value greater than 127 are encoded on more than 8 bits; no link 22 is associated. In an implementation variant relating to the characters, statistics are made on the size of the characters used, either generally in the EXI document, or in a particular manner for each type of value. These statistics are then used to generate the information of the prediction sequence 17 corresponding to the characters. In addition, in such a case, it is possible to verify that the characters are well encoded on the number of predicted bytes, particularly using the predicted values as described hereinafter.

Note that in our example above, it is considered that each predicted value 21 inserted in the sequence 17 is expressed in one byte (8 bits). However, in some cases these values must be encoded in several bytes (because of the great value they take). In this case, an adaptation can be carried out according to which these values are added to the sequence 17 as sets of (partial) values each coded on one byte. The creation of the sequence 17 is continued with the step E320 which consists of obtaining the following object (grammar or production generally).

If the current object is a grammar 10 or a production 11 that does not correspond to an end of element (EE in the EXI language), then the next object is the predicted output 14/16. If this output predicted 14/16 corresponds to an element start (denoted SE in EXI), then this predicted output is stored and the next object 15 becomes the grammar 10 corresponding to this element start. If the current object is a production 11 corresponding to an end of element (EE), then the next object is the production (SE) describing the beginning of the element following the current element, if it has been memorized previously (see above). This makes it possible to use, as the next prediction, the prediction 14 related to the production 11 of the beginning of the next element, which describes what follows the current element (once the latter has been fully processed). In other words, the prediction concerns the event of the same depth in the XML document 1 according to the element start event considered. If the production has not been stored, the next object is not defined and the algorithm ends in step E340. If the next object is defined, it becomes the current object, and the algorithm checks, in step E330, that this current object has one or more simple predictions 14, 15 or 16. This step consists of checking, on the one hand, that this current object may well be associated with simple predictions (for example, the current object should not be a production representing a comment), and, on the other hand, that all simple predictions 14 , 15, 16 associated with this current object have a prediction defined. In the affirmative of step E330, the construction processing of the sequence 17 continues by returning to step E300 to integrate these new simple predictions into the sequence 17. If not, the processing ends at the step E340. It is observed that in the case where a next object is a grammar corresponding to an element start and this grammar already comprises a prediction sequence 17, the latter can be concatenated to the sequence being constructed (for a previous grammar) keeping the order of EXI events. Thus, this construction operation is accelerated without having to go through again simple predictions 14, 15, 16 which have already made it possible to create this other sequence 17. However, if it is desired to take into account the simple predictions that have been updated. this concatenation can be omitted. Note also that the first bit size 20 of a sequence 17 is always correct since it corresponds to the size of the first encoded value to describe the element start and that this size is known (function of the number of priorities used in the current grammar). On the other hand, the first predicted value is not necessarily correct. This therefore results in a possible offset in the prediction check, from which a rule is derived for an implementation of the invention: the first non-correct predicted value corresponds to a correct predicted size (generally the last correctly predicted).

Furthermore, a significant risk exists that the algorithm for constructing the prediction sequence 17 loops over itself infinitely, for example in the case of an element that is often repeated (the simple prediction 14 associated with the production 11 of beginning of this element will indicate this same element start). To avoid such looping, loop stop mechanisms are proposed here, as follows: a first method consists in limiting the length of the prediction sequences. Thus, in step E320, the length of the sequence is also verified. 17 under construction, and finish construction processing as soon as this length is greater than a predefined value. For example, as soon as this length reaches a predefined multiple of the number of values that can be stored in a SIMD instruction operand; a second method consists in detecting loops at the level of simple predictions 14, 15, 16, for example when the same simple prediction (or the same pattern of simple predictions) is recalled. When such a loop is detected, the algorithm ends after a certain number of iterations of this loop. In particular, care will be taken to choose a number of iterations limiting the total size of the sequence 17, but also making the size of the sequence as close as possible to a multiple of 16 (generally, a multiple of the number values that can be handled by a single operand of the SIMD instructions). This optimizes the use of SIMD instructions whose operand filling is maximized. For example, if the number of simple predictions 14, 15, 16 corresponding to an iteration of the loop is 8, then two iterations of this loop will be performed. If this number is 12, 4 iterations will be made, resulting in 4 * 12 = 3 * 16 = 48 predictions in the sequence.

In addition, even if the processing constructs a prediction sequence 17 having the maximum allowed size, some of the predictions may be deleted so as to stop the sequence 17 at an optimal place to begin another sequence of predictions. This optimal location can be the beginning of an XML element or the beginning of an element already associated with a sequence of predictions whose statistics show that it is used effectively. Referring again to the example of the table of FIG. 2a, this algorithm for generating a prediction sequence 17 will generate the information represented in FIG. 6.

In this example, all values are shown in binary mode.

The first column indicates the type of the predicted encoding value. This column is added for a better understanding of the table and is not present in the prediction sequence 17. The second column contains the bit size of the predicted coding value. This size is represented as a binary value ("0000 0011" corresponding for example to a size of "3" bits). The third and fourth columns contain the predicted encoding value 21 in a one-byte binary format and an associated mask 23. These values and masks are used in the verification of the binary bit prediction 21 as described below. The third column actually contains the predicted encoding value when this value is present, or the value 0 otherwise. The fourth column contains a mask for checking whether the predicted value should be equal to the decoded value or not. As explained above, in the example illustrated here, it is necessary to compare the priorities to encode productions, while some content values are not taken into account because difficult to predict (so the mask 23 is arranged not to take this into account and is worth "0"). The mask thus makes it possible to determine which values are to be verified during the verification of the prediction of the bit sizes 21. It may be noted the particular case of the value of type character (last line): a single bit of the mask is 1, the most significant bit. Indeed, when predicting a character, the value of this character does not matter. On the other hand, it is important to check that this character is well coded on the number of predicted bytes. In the case of the example, the character is predicted to be encoded on a single byte, which implies according to the EXI specification that the most significant bit of this byte is 0. The predicted value 21 and the value mask 23 associated with this predicted character thus make it possible to verify this prediction of the most significant bit.

The fifth column contains a link 22 to the grammar containing the predicted productions, in the case where the prediction relates to a production. This link is used to find the grammar to use in case of a prediction error. The sixth column contains an indication of what the predicted value 21 represents. Thus, in the case of a priority, this indication corresponds to the event represented by this priority. In the case of a textual value, this indication corresponds to the type of coding of this value and possibly includes a pointer to the dictionary used for the coding of this value. After obtaining the prediction sequences associated with all or part of the EXI grammars, the decoding step according to the invention, corresponding to the step E130 of FIG. 3, is now described with reference to FIGS. 7 and 8. This decoding, and more particularly the operations allowing the delimitation of the encoding values present in the EXI 2 flow and their decompacting to have the same format as the values manipulated in the grammars, is carried out using SIMD instructions, of which a brief presentation is given at the end of this description. In the first step E400, binary size predictions of encoding values of the flow EXI to be decoded are obtained. These predictions are obtained from the prediction sequence used. Thus, in the case of the previous example, these predictions are the sizes described in the table of FIG. 6. These predictions (each on one byte) are concatenated in a SIMD (128-bit) register, as illustrated by FIG. Figure 8a. It should be noted that for the sake of compactness of the examples, FIGS. 8a to 8h only describe data on 64 bits (corresponding to 8 values only instead of 16). The number of fill bits for each encoding value to be decoded is then calculated as follows: bit size 20, which corresponds to the following SIMD instructions. padding size = simd sub 8 (simd const 8 (8), value size); FIG. 8b illustrates the number of "padding size" padding bits thus obtained.

It should be noted that if the number of predictions in the sequence 17 is greater than 16, the set of values corresponding to these predictions can not be processed simultaneously. In this case, only the bit sizes corresponding to the first 16 predictions are loaded into the SIMD register. The second step E410 is to obtain the coding values to be decoded from the flow EXI 2. This obtaining consists of loading these values into a SIMD register. It should be noted that in most cases, the beginning of the first value to be decoded is not aligned with a byte boundary ("bit-packed" option). This is to be taken into account when loading values and can be achieved by conventional algorithms. In the previous example, the values loaded into a SIMD register are shown in Figure 8c. At this stage, not knowing the length corresponding to the 16 values, 128 consecutive bits of the stream are recovered. The third step E420 concerns the decompacting itself of the values thus recovered, on the basis of the predicted bit sizes. This operation realigns the retrieved encoding values to match the binary alignment of the values manipulated by the decoder (generally octet-aligned). This unpacking is done in three sub-steps. The first substep E422 consists of counting the number of fill bits for one, two, four and eight values (in our example). This count is performed by the following SIMD instructions: count8 = padding size countl6 simd add 161h (count8, count8); count32 simd add 321h (countl6, countl6); count64 simd add 641h (count32, count32); This count amounts to adding the number of fill bits 30 for two consecutive values, which gives the value countl6, then for four and finally eight consecutive values. Thus, taking the example, we obtain the accounts of Figure 8d.

The next substep E424 consists of calculating bit shift masks from previously calculated values. These shift masks are intended, as described below, to progressively shift the sixteen encoding values recovered to align them with the format of the values manipulated by the decoder (in our example, the values are on one byte). The calculation of these offset masks consists in applying the following SIMD instructions: mask8 = simd const 16 ((1 "8) - 1); shift8 = simd and (simd srli (count8, 8), mask8); maskl6 = simd const 32 ((1 "16) - 1); shiftl6 = simd and (simd srli (count16, 16), mask16); mask32 = simd const 64 ((1 "32) - 1); shift32 = simd and (simd srli (count32, 32), mask32); mask64 = simd const 128 ((1 "64) - 1); shift64 = simd and (simd srli (count64, 64), mask64); It should be noted that if the shift masks (the shift8, shiftl6 ... values) are specific to each sequence of predictions, the masks (the mask8, maskl6 ... values) used to calculate them are constants that do not do not need to be recalculated each time the algorithm runs. On the other hand, these shift masks are invariant for the same sequence of predictions 17 and can therefore be stored with this sequence. This speeds up the decoding by taking up more memory. Strategies for memorizing these more elaborate masks can therefore be put in place. The application of these calculations to our example is illustrated in Figure 8e. Finally, the last sub-step, denoted E426, is the decompacting itself. This unpacking is done by separating the sixteen values into two groups of eight values, each in a half SIMD register. Thus, each group of eight values is aligned on a block of 64 bits (corresponding to value64 not shown in FIG. 8f). Then the process is restarted to separate each group in two, until each value is isolated on a block of eight bits (successively value32, valuel6 and value8 in Figure 8f). A last operation then makes it possible to align each of these values (see bytes in FIG. 8f). It is observed moreover that the offset of this step inserts "0" into the binary sequence, which has the further effect of expelling, from this sequence, the bits beyond the 16 desired values (corresponding to the bits marked d Figure 8f) These operations are performed by the following SIMD instructions: shifted = simd and (simd srl 128 (value, shift64), mask64); masked = simd andc (value, mask32); value64 = simd or (shifted, masked); shifted = simd and (simd srl 64 (value64, shift32), mask32); masked = simd andc (value64, mask32); value32 = simd or (shifted, masked); shifted = simd and (simd srl 32 (value32, shiftl6), maskl6); masked = simd andc (value32, maskl6); valuel6 = simd or (shifted, masked); shifted = simd and (simd srl 16 (valuel6, shift8), mask8); masked = simd andc (valuel6, mask8); value8 = simd or (shifted, masked); bytes = simd srl 8 (value8, count8); The values obtained for our example are shown in FIG. 8f (the points "." In the end showing the bit shifts made by the insertion of "0"). Thus, from the set of initially compacted values (FIG. 8c), the list of these values each represented on 1 byte is obtained. The next step E430 is then to check the predictions. For this purpose, the predicted decoding values 21 from the prediction sequence 17 are first loaded (E432) into two SIMD registers (predicted and predictmask) (see FIG. 8g, which can be performed at n any other previous step, especially during step E400 where is already accessed to the sequence 17) and the associated masks. Then the list of uncompressed byte values is compared (step E434) to the predicted list of predicted values, taking into account the predict mark mask.

The SIMD instructions used for this comparison are as follows: error = simd and (simd xor (bytes, predicted), predict mask) Thus, the operand error contains for each decompacted value a verification of the corresponding prediction (equal to 0 if the value is correctly predicted - see figure 8h for our example). It is thus seen that, using SIMD instructions, several coding values were unpacked and realigned simultaneously in order to use them to identify, in grammars or other decoding tables, the corresponding XML values and events.

In a variant, this step of the invention can be simplified. Indeed in some cases, a set of predictions can be verified in a simpler way. For example, in the case of a well-defined structure (this structure can correspond for example to an XML element with all its attributes and sub-elements), the simplification consists in verifying that the values to be decoded correspond to this structure to be able to use the prediction sequence corresponding to this structure without needing to perform additional checks. It is thus possible to omit to check the predictions for this sequence, and to continue the processing (decoding for example) of this sequence and the treatment of the elements following this well-defined structure. In such a case, the verification can be carried out for example by testing a few bits among the values to be decoded by comparison with the well-defined structure, this verification being carried out a priori, between the steps E410 and E420. In addition, if the structure is sufficiently long, this step is performed at the beginning of the decoding of the structure. And if the algorithm performs the steps E400 to E460 several times to decode the bitstream corresponding to the structure, this verification is not repeated until the bitstream corresponding to the structure is decoded.

In the next step E440, the prediction sequence 17 is updated using this prediction check. This step is described later, in more detail with reference to FIG. 9. Next, the data stream is updated (step E450). This consists of marking the position of the next value to be decoded. This is done from the indication of the first erroneous value and the size of the correctly decompacted values. In our example (Figure 8h), the 7th value has not been correctly predicted. This means, according to the rule seen above that, despite the erroneous value, the prediction of the binary size is good, that we know that the 7th value has still been well delimited and thus unpacked. We can therefore position the marker of the next value to be decoded at the beginning of the 8th value. For that, one determines the total binary size of the correctly decoded values, here 32 bits. The marker of the next value to be decoded is therefore positioned on the next bit namely on the 33rd bit of the flow EXI 2 (FIG. 8c). Then, the next step E460 consists of actually decoding the set of decompacted values (the first seven, therefore). For all the correctly predicted values, this decoding uses the information describing the XML content represented by this value to generate the event (or the event part) corresponding to this value. This reduces the treatments to be performed. As mentioned above, for the first value incorrectly predicted, however, the size of this value has been correctly predicted and the value has been correctly decompacted. However, the information describing the XML content does not match this value. The decoding is then performed from the grammar indicated in the link information 22 for this value. If no link information 22 exists for this value, the information indicated for a previous value is used (the link information used is the last link information present for one of the correctly predicted values or for this value incorrectly predicted).

It should be noted that a particular case of prediction error is when the length of a character string is erroneous. In such a case, the character predictions can nevertheless be used as long as they correspond to characters actually present in the string to be decoded: the predictions corresponding to characters positioned before the actual end of the string of characters remain valid. This particular case of management of the prediction errors can be implemented to accelerate the decoding of the strings of characters. In addition, when an error occurs on the prediction of the length of a character string, it is possible to continue to use the predictions for values occurring after the string. This can be achieved by adapting the algorithm described here. As a variant, the character strings can be processed in a specific manner: the optimized decompacting described by this algorithm is then performed for a set of values including the length of the string of characters. But the string itself is decoded in a specific way. Then, optimized decompacting is resumed to process the values following this string of characters. It should be noted that for the decoding of a string of characters, SIMD type instructions can be used profitably. Indeed, it is interesting to use such instructions on the one hand to align the coded string on byte limits, by simple bit shift instructions. On the other hand, the decoding of the character string from the encoding used by the EXI specification to a conventional encoding such as UTF-8 or UTF-16 can be performed in an optimized manner with SIMD instructions, using algorithms similar to those described by Parabix. In an alternative embodiment of the invention, the complete decoding of the document is not carried out. Thus, in some cases, it may be interesting to quickly browse the beginning of the document to reach a particular part of the document that will be decoded completely. In the example of a person list, this allows, for example, to decode only the information about a particular person. In this variant, step E460 is not carried out as long as the portion of the document processed corresponds to a non-interesting part (for example, until a particular <particular person> tag has been reached): indeed the previous steps have performed all the necessary processing to allow the decoder to process the rest of the document. The use of the invention in such a framework makes it possible to accelerate the rapid processing of a part of a document. Still with reference to FIG. 7, in the next step E470, the algorithm checks whether other predictions are available and can be used. This verification takes into account the outcome of step E430. Indeed, if a prediction error has been detected in step E430, then other predictions can not be used. The algorithm ends in step E480. If, on the other hand, no prediction error has been detected in step E430, and if there are still unused predictions in the initial prediction sequence 17, then the algorithm continues by returning to step E400 with the following predictions of the sequence. Otherwise the algorithm ends at step E480. It should be noted that this algorithm works optimally if the number of predictions available in the sequence is a multiple of 16: at each iteration of the algorithm, sixteen values will be decompacted simultaneously. If fewer than sixteen predictions are available for an iteration of the algorithm, the missing predictions are replaced by the following values: the size of the value is 0, the predicted value is 255 (that is, 1111 1111 in binary ) and the mask of the predicted value is 255 (1111 1111 in binary). This makes it possible to use the algorithm without modification while generating an error for these missing predictions in order to stop the decoding by arriving at these dummy values. Referring now to FIG. 9, the step E440 of updating the prediction sequences 17 is described as a function of the result of the verification of the predictions E430.

The first step E500 consists in updating statistics of use of the sequence. This step uses the results of the prediction check of this sequence. In one embodiment of the invention, the statistics of use of the sequence are composed of a list which contains the positions where prediction errors have occurred for the last uses of this sequence. Sequence usage statistics are composed of a list with two entries corresponding to the positions of the last two errors. The next step E510 then consists of checking whether the prediction sequence 17 is reliable or not with respect to the EXI flow 2 being decoded. This verification is based on the statistics of use of the sequence. In the statistics example above, the algorithm uses the list of positions where a prediction error has occurred. If a position has a high frequency in this list (for example, beyond 25% of the errors), then the sequence 17 is not considered reliable. In the implementation variant, if the two positions of the statistics list are equal, then the sequence 17 is not considered reliable. In other cases, the sequence 17 is considered reliable and the processing ends in step E530. If the prediction sequence 17 is not considered reliable, the algorithm proceeds to step E520 in which the prediction sequence 17 is updated. According to a preferred embodiment of the invention, this update consists of cutting the sequence 17 at the position where a prediction error occurs frequently, especially at the location of the most frequent prediction error. Thus, associated with the corresponding grammar is only the beginning of the sequence 17, that is, the events and values that are statistically correctly predicted.

According to a second implementation, the prediction sequence 17 can be reconstructed integrally by reproducing the processing of FIG. 5 and then compared with the existing sequence 17 to check whether the frequent error position comprises a different prediction.

If so, then the new prediction sequence replaces the old one. Otherwise, the old sequence is cut at this position. In a simpler variant of this second implementation, instead of reconstructing the entire sequence 17 before verification, it is possible to directly check whether the frequently erroneous prediction has been modified at the level of the corresponding simple prediction. To do this, we first identify the output 11 (corresponding to the predicted value preceding the frequently erroneous one) or the grammar 10 (in the case where the previous event is an element start) that produced this prediction, then we check if the simple prediction 14/16 associated with this production or grammar has been modified. If this is the case, the sequence is modified starting from this prediction. Following this update, the algorithm ends in step E530. A particular case of updating a prediction sequence 17 is the size change of a dictionary of values, in particular when this size change causes a change in the size of the index coding for this dictionary. Indeed, the predictions on an index in this dictionary use this size of encoding indexes. But the verification of predictions only verifies the predicted size to know if it is correct. Therefore, when an index encoding size change occurs for a dictionary, all predictions for those indexes must be changed. This modification is carried out by associating with each dictionary the simple predictions which correspond to an index of this dictionary. Thus, when changing the encoding size of the indexes of this dictionary, these simple predictions can be modified.

Then, these modifications are reported in the prediction sequences 17 constructed from these simple predictions. This can be done for example by reconstructing the prediction sequences according to the mechanisms of FIG. 5. As a variant, it is possible to optimize this operation by directly modifying the prediction sequences 17 already constructed. Note finally that, for a small dictionary of values, the size of the index coding for this dictionary will change frequently: indeed, the coding size of an index is equal to the integer value of the logarithm in base 2 of the size. of the dictionary. Since this prediction update operation is expensive, simple content predictions are not considered valid (i.e., they can not be integrated into a prediction sequence in step E330) if these predictions match an indexed value and the index size is too small (for example, less than or equal to 4 or 8). It is clear from the foregoing that the delimitation of the encoding values in an EXI flow and their unpacking can be carried out simultaneously for a large number of EXI events, in particular by the implementation of the SIMD type instructions, in spite of the not aware of these sizes in view of their dependence on previous events not yet decompacted and decoded. This efficiency is obtained by predicting the binary sizes of these EXI values, and the validation of all or part of these predictions by comparison of the EXI values thus recovered and decompacted with values also predicted. If the values have been predicted, it is that the decompacting is correct and therefore the predicted sizes are accurate. In addition to implementing these processes for decoding a bitstream as illustrated above, they can provide access, at a low cost and in a rapid manner, to a specific part of the structured structured document. Indeed, the invention makes it possible to quickly browse the coded events until reaching the first of the part to be accessed (generally an element start with a given name, or a given position in the encoded document).

The implementation of SIMD instructions can also be carried out when encoding structured documents such as XML into an EXI flow, in particular during the operations of compacting a large number of coding values retrieved from the dictionaries and grammars. For example, the method comprises: determining the encoding values of a plurality of consecutive events of said document; determining a compaction size for each coding value (generally the minimum number of bits to encode all the priorities of the corresponding grammar); and simultaneously compacting said coding values with said compaction sizes using at least one single multiple data instruction. It is mainly to perform the reverse operations of those described above for unpacking. Referring now to FIG. 10, there is described by way of example a particular hardware configuration of a processing device of a structured document and / or a bit stream corresponding to such a coded document capable of being implemented. process of the invention. An information processing device embodying the invention is for example a microcomputer 50, a workstation, a personal assistant, or a mobile phone connected to different peripherals. According to yet another embodiment of the invention, the device is in the form of a camera equipped with a communication interface to allow a connection to a network. The peripherals connected to the device according to the invention comprise, for example a digital camera 64, or a scanner or any other means of acquiring or storing images, connected to an input / output card (not shown) and supplying the device with multimedia data, possibly in the form of XML documents or EXI / Fast Infoset. The device 50 comprises a communication bus 51 to which are connected: a central processing unit CPU 52, for example in the form of a microprocessor; a read-only memory 53 in which can be contained the programs whose execution allows the implementation of the method according to the invention. It can be a flash memory or EEPROM; a random access memory 54 which, after powering on the device 50, contains the executable code of the programs of the invention necessary for the implementation of the invention. This RAM 54 is RAM (random access), which offers fast access compared to the read only memory 53; a screen 55 making it possible to display data, in particular video, and / or to serve as a graphical interface with the user who can thus interact with the programs of the invention, using a keyboard 56 or any other means such as a pointing device, such as for example a mouse 57 or an optical pen; a hard disk 58 or a storage memory, such as a compact flash type memory, which may comprise the programs of the invention as well as data used or produced during the implementation of the invention; an optional floppy disk drive 59 or another removable data medium reader adapted to receive a floppy disk 63 and to read / write data processed or to be processed according to the invention; and a communication interface 60 connected to the telecommunications network 61, the interface 60 being able to transmit and receive data. The communication bus 51 allows communication and interoperability between the various elements included in the device 50 or connected thereto. The representation of the bus 51 is not limiting and, in particular, the central unit 52 is able to communicate instructions to any element of the device 50 directly or via another element of the device 50. be replaced by any information medium such as, for example, a rewritable compact disc (CD-ROM) or not, a ZIP disk or a memory card. In general, an information storage means, readable by a microcomputer or by a microprocessor, integrated or not integrated with the processing device, possibly removable, is adapted to store one or more programs whose execution allows the implementation of the method according to the invention. The executable code allowing the processing device, the implementation of the invention can be indifferently stored in ROM 53, on the hard disk 58 or on a removable digital medium such as for example a diskette 63 as described above. According to one variant, the executable code of the programs is received via the telecommunications network 61, via the interface 60, to be stored in one of the storage means of the device 50 (such as the hard disk 58 for example) before to be executed. The central unit 52 controls and directs the execution of the instructions or portions of software code of the program or programs of the invention, the instructions or portions of software code being stored in one of the aforementioned storage means. When the device 50 is turned on, the program or programs that are stored in a non-volatile memory, for example the hard disk 58 or the read-only memory 53, are transferred into the random access memory 54 which then contains the executable code of the or programs of the invention, as well as registers for storing the variables and parameters necessary for the implementation of the invention. Note also that the device embodying the invention or incorporating it is also feasible in the form of a programmed apparatus. For example, such a device may then contain the code of the computer program or programs in a form fixed in a specific application integrated circuit (ASIC). The device described here and, particularly, the central unit 52, are able to implement all or part of the processes described in connection with Figures 4 to 9, to implement the methods of the present invention and constitute the devices objects of the present invention.

The foregoing examples are only embodiments of the invention which is not limited thereto.

Presentation of the SIMD instructions implemented in the illustrative embodiment of the present invention. simd not (op) Operator "no" bitwise. simd and (op1, op2) Operator "and" bitwise. simd andc (op1, op2) Operator "and opposite" bit by bit. Equivalent to simd and (op1, simd not (op2)). simd or (op1, op2) Operator "or" bitwise. simd xor (op1, op2) Operator "or exclusive" bit by bit. simd const n (value) Creates a constant, using bit fields of size n, each field containing the given value. simd srli (op, value) Logical shift to the right, using the specified number of bits. simd srl n (op1, op2) Logic shift to the right, using bit fields of size n, where the fields of the first operand are shifted by the number of bits indicated in the corresponding field of the second operand. simd add n hi h2 (op1, op2) Adds both operands, using bit fields of size n and using half-size operands. hi indicates which half-part (high or low, represented by h or 1) is used for each field of the first operand. h2 plays the same role for the second operand. simd sub n (op ', ope) Subtracts the two operands, using bit fields of size n.

Claims (21)

REVENDICATIONS1. A method of processing a bit stream (2) comprising event encoding values (30) of a structured document (1), the method comprising the steps of: - recovering (E410) a plurality (value) of encoding values (30) of consecutive events of said bit stream (2); predicting (E400) the binary size (20, value size) of said recovered encoding values (30); realigning (E426), using said predicted bit sizes (20, value size), the encoding values (30) of said recovered plurality (value) to correspond to a given bit alignment; - validating (E430, E434) the prediction of at least a portion of the bit sizes (20); processing (E460) the events corresponding to the bit sizes whose prediction is validated. 2. Processing method according to the preceding claim, comprising the steps of: - predicting (E432) coding values retrieved so as to form a predicted plurality of coding values (21), said coding values (21); ) of the predicted plurality being according to said given bit alignment; and - checking (E430, E434) the prediction of the coding values by comparing predicted pluralities (21, predicted) and realigned (30, bytes) so as to validate the prediction of at least a portion of the bit sizes (20). 3. Processing method according to claim 2, comprising the association (E150), at least one decoding table (10) of said bit stream (2), a prediction sequence (17) whose inputs comprise at least an event encoding value (21) and a bit size (20) associated with this encoding value, and wherein said predictions (E400, E430) of the encoding values and bit sizes are retrieved from said prediction sequence ( 17) associated with the current decoding table (10). 4. Treatment method according to the preceding claim, comprising a step of constructing (E150) said sequence of predictions (17) from at least one simple prediction (14, 15, 16) associated with at least one input (11). ) decoding tables (10), said simple prediction providing another decoding table entry. The processing method according to the preceding claim, wherein said construct (E150) comprises the path (E320) of a plurality of decode table entries (10) while navigating using simple predictions (14, 15). , 16) associated with said traversed entries, and adding (E310) said simple predictions traversed to said prediction sequence. 6. Processing method according to one of claims 3 to 5, comprising updating (E520) said sequence of predictions (17) according to said verification (E430, E434). The processing method according to one of claims 3 to 6, wherein said processing comprises decoding (E460) the first recovered coding value whose prediction is erroneous, using link information (22). ) associated with an input of said prediction sequence (17). The processing method according to one of claims 3 to 7, wherein said prediction sequence (17) comprises a number of entries which is a multiple of the number of values contained, according to said binary alignment of the predicted plurality, in a single instruction operand with multiple data (SIMD). 9. Processing method according to one of claims 2 to 8, wherein said verification (E430, E434) comprises the application of a predict mask (predict mask) so as not to take into account at least one value during said comparison. The processing method according to one of the preceding claims, wherein the realignment (E426) of the encoding values (30) implements at least one bit-shift multiple data instruction (SIMD). 11. Processing method according to the preceding claim, comprising the concatenation of the predicted bit sizes (20) in a first single-data multiple data value (SIMD) register. 12. Processing method according to one of claims 10 and 11, wherein said realignment (E426) implements a plurality of single instructions with multiple data (SIMD) able to achieve a progressive alignment of the recovered coding values, by iterative shift of subgroups of successive encoding values. 13. Treatment method according to the preceding claim, wherein the subgroups are divided in half from one iteration to the next. The processing method according to claim 1, wherein said validation (E430) comprises the comparison of at least a portion (value) of the recovered bitstream with a predefined structure, and in the case of a positive comparison, a sequence of predictions (17) associated with said predefined structure for predicting bit sizes (20, value size). 15. A processing device (50) for a bit stream (2) comprising event coding values (30) of a structured document (1), the device comprising: - means adapted to recover (E410) a plurality (value) of encoding values (30) of consecutive events of said bit stream (2); prediction means for predicting (E400) the binary size (20, value size) of said retrieved encoding values (30); realignment means adapted to realign (E426), using said predicted bit sizes (20, value size), the encoding values (30) of said recovered plurality (value) to correspond to a given bit alignment; a validation means capable of validating (E430, E434) the prediction of at least a portion of the bit sizes (20), a processing module for processing (E460) the events corresponding to the bit sizes whose prediction is validated. 16. Processing device according to claim 15, in which: the prediction means is also able to predict (E432) coding values retrieved so as to form a predicted plurality of coding values (21), said coding values (21) of the predicted plurality being according to said given bit alignment; and the validation means is able to verify (E430, E434) the prediction of the coding values by comparison of the predicted pluralities (21, predicted) and realigned (30, bytes) so as to validate the prediction of at least a part binary sizes (20). The processing apparatus according to claim 16, comprising multiple multi-data instructions and associated registers for simultaneously storing information (20, 21, 30) relating to a plurality of successive encoding values to be processed. 18. Process device according to claim 16 or 17, comprising decoding tables (10) with associated prediction sequences (17) whose inputs comprise at least one event coding value (21) and a bit size. (20) associated with this encoding value. 19. Processing device according to the preceding claim, comprising simple predictions (14, 15, 16) associated with inputs (11) of the decoding tables (10) and informing another decoding table input, and means of construction. of such a sequence of predictions from simple predictions. 20. Information storage medium, readable by a computer system, comprising instructions for a computer program adapted to implement the method according to any one of claims 1 to 14 when the program is loaded and executed by the system. computer. A microprocessor-readable computer program product comprising portions of software code adapted to implement the method of any of claims 1 to 14 when loaded and executed by the microprocessor.