Changeset 287 for docs


Ignore:
Timestamp:
Aug 31, 2009, 3:02:29 PM (10 years ago)
Author:
ksherdy
Message:

Updated section "A Catalog of ..."

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Balisage09/Bal2009came0601.xml

    r283 r287  
    221221               <tbody>
    222222                  <tr valign="top">
    223                      <td>XML</td>
     223                     <td>Input Data</td>
    224224                     <td>
    225225                        <code>&lt;</code>
     
    455455      <section>
    456456         <title>General Streams</title>
    457          <para>This section describes the bit streams which support operations that are common to
    458             many XML processing tasks.</para>
     457         <para>This section describes bit streams which support basic processing operations.</para>
    459458
    460459         <section>
    461460            <title>Deletion Mask Streams</title>
    462             <para>The DelMask (deletion mask) streams marks character code unit positions for
    463                deletion. Since the deletion operation arises in many stages of XML processing,
    464                positions are initially marked for deletion, and then subsequently deleted in
    465                parallel, using a bitwise ORing of a number of deletion masks. A single invocation of
    466                a SIMD based parallel deletion algorithm may perform deletions accumulated across a
    467                number of XML processing stages. Several algorithms to delete bits at positions
    468                marked by DelMask are possible [<xref linkend="u8u16"/>]. </para>
    469             <para> As an example, deletion arises in the replacement of predefined entities, such as
    470                in the replacement of the &amp;amp; entity, with the &amp; character. Further
    471                deletion masks, such as masks resulting from UTF-8 to UTF-16 transcoding, XML
    472                end-of-line handling, and CDATA section delimeter processing may then be ORd for
    473                accumulation with the predefined entity deletion mask.</para>
     461            <para>DelMask (deletion mask) streams marks character code unit positions for deletion.
     462               Since the deletion operation is dependency free across many stages of XML processing,
     463               it is possible to simply mark and record deletion positions as deletion mask streams for future processing. A single
     464               invocation of a SIMD based parallel deletion algorithm can then perform the deletion of
     465               positions accumulated across a number of stages through a bitwise ORing of deletion
     466               masks. For example, deletion arises in the replacement of predefined entities with a
     467               single character, such as in the replacement of the &amp;amp; entity, with the
     468               &amp; character. Deletion also arises in XML
     469               end-of-line handling, and CDATA section delimeter processing. Several algorithms to
     470               delete bits at positions marked by DelMask are possible [<xref linkend="u8u16"/>]. </para>
    474471            <para>The following table provides an example of generating a DelMask in the context of
    475472               bit stream based parsing of well-formed character references and predefined entities.
    476                Character reference and predefined entity bit stream definitions are provided below.<!-- PARABIX2_1  -->
    477                <!--
    478             <table>
    479                <caption>
    480                   <para>DelMask Stream Generation</para>
    481                </caption>
    482             </table>
    483             -->
     473               The result is the generation of a DelMask stream. <table>
     474                  <caption>
     475                     <para>DelMask Stream Generation</para>
     476                  </caption>
     477                  <colgroup>
     478                     <col align="left" valign="top"/>
     479                     <col align="left" valign="top"/>
     480                  </colgroup>
     481                  <tbody>
     482                     <tr valign="top">
     483                        <td>Input Data</td>
     484                        <td>
     485                           <code>&amp;gt; &amp;#13; &amp;#x0a;</code>
     486                        </td>
     487                     </tr>
     488                     <tr valign="top">
     489                        <td>GenRefs</td>
     490                        <td>
     491                           <code>_11______________</code>
     492                        </td>
     493                     </tr>
     494
     495                     <tr valign="top">
     496                        <td>DecRefs</td>
     497                        <td>
     498                           <code>_______11________</code>
     499                        </td>
     500                     </tr>
     501                     <tr valign="top">
     502                        <td>HexRefs</td>
     503                        <td>
     504                           <code>______________11_</code>
     505                        </td>
     506                     </tr>
     507                     <tr valign="top">
     508                        <td>DelMask</td>
     509                        <td>
     510                           <code>111__1111__11111_</code>
     511                        </td>
     512                     </tr>
     513                     <tr valign="top">
     514                        <td>ErrorFlag</td>
     515                        <td>
     516                           <code>__________________</code>
     517                        </td>
     518                     </tr>
     519                  </tbody>
     520               </table>
    484521            </para>
    485522         </section>
     
    488525            <title>Error Flag Streams </title>
    489526            <para>Error flag streams indicates the character code unit positions of syntactical
    490                errors. XML processing examples which benefit from the marking error positions
     527               errors. XML processing examples which benefit from the marking of error positions
    491528               include UTF-8 character sequence validation and XML parsing [<xref linkend="u8u16"
    492529               />].</para>
    493530            <para>The following table provides an example of using bit streams to parse character
    494531               references and predefined entities which fail to meet the XML 1.0 well-formedness
    495                constraints. This results in the generation of a error flag stream.<!-- PARABIX2_2  -->
    496                <!-- REPLACE
    497                <table>
    498                <caption>
    499                   <para>Error Flag Stream Generation</para>
     532               constraints. The result is the generation of an error flag stream that marks the
     533               positions of mal-formed decimal and hexical character references respectively. <table>
     534                  <caption>
     535                     <para>Error Flag Stream Generation</para>
    500536                  </caption>
    501537                  <colgroup>
    502538                     <col align="left" valign="top"/>
     539                     <col align="left" valign="top"/>
    503540                  </colgroup>
    504541                  <tbody>
    505542                     <tr valign="top">
    506                         <td>XML</td>
    507                         <td>
    508                            <code>Well Formed &amp;lt; Erroneous &amp;gt!</code>
    509                         </td>
    510                      </tr>
    511                      <tr valign="top">
    512                         <td>RefStart</td>
    513                         <td>
    514                            <code></code>
    515                         </td>
    516                      </tr>
    517                      <tr valign="top">
    518                         <td>RefEnd</td>
    519                         <td>
    520                            <code></code>
    521                         </td>
    522                      </tr>
    523                      <tr valign="top">
    524                         <td>RefError</td>
    525                         <td>
    526                            <code></code>
     543                        <td>Input Data</td>
     544                        <td>
     545                           <code>&amp;gt; &amp;#, &amp;#x; </code>
     546                        </td>
     547                     </tr>
     548                     <tr valign="top">
     549                        <td>GenRefs</td>
     550                        <td>
     551                           <code>_11___________</code>
     552                        </td>
     553                     </tr>
     554                     <tr valign="top">
     555                        <td>DecRefs</td>
     556                        <td>
     557                           <code>______________</code>
     558                        </td>
     559                     </tr>
     560                     <tr valign="top">
     561                        <td>HexRefs</td>
     562                        <td>
     563                           <code>______________</code>
     564                        </td>
     565                     </tr>
     566                     <tr valign="top">
     567                        <td>DelMask</td>
     568                        <td>
     569                           <code>111__11__111__</code>
     570                        </td>
     571                     </tr>
     572                     <tr valign="top">
     573                        <td>ErrorFlag</td>
     574                        <td>
     575                           <code>_______1____1__</code>
    527576                        </td>
    528577                     </tr>
    529578                  </tbody>
    530579               </table>
    531                -->
    532580            </para>
    533 
    534581         </section>
    535582
     
    546593            bytestream representation [<xref linkend="CASCON08"/>].</para>
    547594         <para>A key role of lexical item streams in XML parsing is to facilitate fast scanning
    548             operations. For example, a LeftAngle lexical item stream may be formed to identify those
    549             character code unit positions at which a “&lt;” character occurs. Hardware register
    550             bit scan operations may then be used by the XML parser on the LeftAngle stream to
    551             efficiently identify the position of the next “&lt;”. Based on the capabilities of
    552             current commodity processors, a single register bit scan operation may effectively scan
    553             up to 64 byte positions with a single instruction.</para>
     595            operations. For example, a left angle bracket lexical item stream may be formed to
     596            identify those character code unit positions at which a “&lt;” character occurs.
     597            Hardware register bit scan operations may then be used by the XML parser on the left
     598            angle bracket stream to efficiently identify the position of the next “&lt;”. Based
     599            on the capabilities of current commodity processors, a single register bit scan
     600            operation may effectively scan up to 64 byte positions with a single instruction.</para>
    554601         <para>Overall, the construction of the full set of lexical item stream computations
    555602            requires approximately 1.0 CPU cycles per byte when implemented for 128 positions at a
    556603            time using 128-bit SSE registers on Intel Core2 processors [<xref linkend="CASCON08"/>].
    557             The following table describes the core lexical item streams defined by the Parabix XML
     604            The following table defines the core lexical item streams defined by the Parabix XML
    558605            parser.</para>
    559606         <para>
     
    659706                  <tr>
    660707                     <td align="left"> Digit </td>
    661                      <td align="left"> Marks the position of any digit character.</td>
     708                     <td align="left"> Marks the position of any digit.</td>
    662709                  </tr>
    663710                  <tr>
     
    672719            </table>
    673720         </para>
    674          <para>The following table illustrates a number of the lexical item streams.
    675             <!--
     721         <para> The following illustrates a number of the lexical item streams. </para>
     722         <para>
    676723            <table>
    677724               <caption>
    678725                  <para>Lexical Item Streams</para>
    679726               </caption>
    680            
    681                
    682727               <colgroup>
    683728                  <col align="left" valign="top"/>
     729                  <col align="left" valign="top"/>
    684730               </colgroup>
    685 
     731               <tbody>
     732                  <tr valign="top">
     733                     <td>Input Data</td>
     734                     <td>
     735                        <code>&lt;tag&gt;&lt;tag&gt; text &amp;lt;
     736                           &amp;#x3e; &lt;/tag&gt;&lt;/tag&gt;</code>
     737                     </td>
     738                  </tr>
     739
     740                  <tr valign="top">
     741                     <td>LAngle</td>
     742                     <td>
     743                        <code>1____1______________________1_____1_____</code>
     744                     </td>
     745                  </tr>
     746                  <tr valign="top">
     747                     <td>RAngle</td>
     748                     <td>
     749                        <code>____1____1_______________________1_____1</code>
     750                     </td>
     751                  </tr>
     752                  <tr valign="top">
     753                     <td>WS</td>
     754                     <td>
     755                        <code>__________1____1____1______1____________</code>
     756                     </td>
     757                  </tr>
     758                  <tr valign="top">
     759                     <td>RefStart</td>
     760                     <td>
     761                        <code>________________1____1__________________</code>
     762                     </td>
     763                  </tr>
     764                  <tr valign="top">
     765                     <td>Hex</td>
     766                     <td>
     767                        <code>__1____1____1___________11_____1_____1__</code>
     768                     </td>
     769                  </tr>
     770
     771                  <tr valign="top">
     772                     <td>Semicolon</td>
     773                     <td>
     774                        <code>___________________1______1_____________</code>
     775                     </td>
     776                  </tr>
     777                  <tr valign="top">
     778                     <td>Slash</td>
     779                     <td>
     780                        <code>_____________________________1_____1____</code>
     781                     </td>
     782                  </tr>
    686783               </tbody>
    687784            </table>
    688                -->
    689785         </para>
     786
    690787      </section>
    691788
     
    694791         <para> An XML parser must accept the UTF-8 encoding of Unicode [<xref linkend="XML10"/>].
    695792            It is a fatal error if an XML document determined to be in UTF-8 contains byte sequences
    696             that are not legal in that encoding. UTF-8 byte classification, scope and error flag bit
    697             streams are defined to validate UTF-8 byte sequences and support transcoding to UTF-16
    698             if desired.</para>
     793            that are not legal in that encoding. UTF-8 byte classification, scope, XML character
     794            validation and error flag bit streams are defined to validate UTF-8 byte sequences and
     795            support transcoding to UTF-16.</para>
    699796
    700797         <section>
     
    703800               forming single and multibyte sequences. The u8Prefix and u8Suffix bit streams
    704801               identify bytes that represent, respectively, prefix or suffix bytes of multibyte
    705                sequences. The u8UniByte bit stream identifies those bytes that may be considered
    706                single-byte sequences. The u8Prefix2, u8Prefix3, and u8Prefix4 refine the u8Prefix
    707                respectively indicating prefixes of two, three or four byte sequences.</para>
     802               UTF-8 sequences. The u8UniByte bit stream identifies those bytes that may be
     803               considered single-byte sequences. The u8Prefix2, u8Prefix3, and u8Prefix4 refine the
     804               u8Prefix respectively indicating prefixes of two, three or four byte
     805            sequences respectively.</para>
    708806         </section>
    709807
    710808         <section>
    711809            <title>UTF-8 Scope Streams</title>
    712             <para> Scope streams represent expectations established by prefix bytes. For example,
    713                bit stream u8Scope22 represents the positions at which a second byte of a two-byte
    714                sequence is expected based on the occurrence of a two-byte prefix in the immediately
    715                preceding positions. The u8scope32, u8Scope33, u8Scope42, u8scope43, and u8Scope44
    716                complete the set of UTF-8 scope streams.</para>
    717             <para> The following examples demonstrate the UTF-8 character encoding validation
     810            <para> Scope streams represent expectations established by UTF-8 prefix bytes. For
     811               example, the u8Scope22 bit stream represents the positions at which the second byte of a
     812               two-byte sequence is expected based on the occurrence of a two-byte prefix in the
     813               immediately preceding position. The u8scope32, u8Scope33, u8Scope42, u8scope43, and
     814               u8Scope44 complete the set of UTF-8 scope streams.</para>
     815            <para> The following example demonstrates the UTF-8 character encoding validation
    718816               process using parallel bit stream techniques. The result of this validation process
    719                is an error flag stream identifying those positions at which errors are identified.</para>
     817               is an error flag stream identifying the positions at which errors occur.</para>
    720818            <para>
    721819               <table>
     
    726824                     <col align="left" valign="top"/>
    727825                     <col align="left" valign="top"/>
    728                      <col align="left" valign="top"/>
    729                      <col align="left" valign="top"/>
    730                      <col align="left" valign="top"/>
    731                      <col align="left" valign="top"/>
    732                      <col align="left" valign="top"/>
    733                      <col align="left" valign="top"/>
    734                      <col align="left" valign="top"/>
    735                      <col align="left" valign="top"/>
    736                      <col align="left" valign="top"/>
    737                      <col align="left" valign="top"/>
    738                      <col align="left" valign="top"/>
    739                      <col align="left" valign="top"/>
    740                      <col align="left" valign="top"/>
    741                      <col align="left" valign="top"/>
    742                      <col align="left" valign="top"/>
    743                      <col align="left" valign="top"/>
    744                      <col align="left" valign="top"/>
    745                      <col align="left" valign="top"/>
    746                      <col align="left" valign="top"/>
    747                      <col align="left" valign="top"/>
    748                      <col align="left" valign="top"/>
    749                      <col align="left" valign="top"/>
    750                      <col align="left" valign="top"/>
    751                      <col align="left" valign="top"/>
    752                      <col align="left" valign="top"/>
    753                      <col align="left" valign="top"/>
    754826                  </colgroup>
    755827                  <tbody>
    756828                     <tr valign="top">
    757829                        <td>Input Data</td>
    758                         <td colspan="1">
    759                            <code>A</code>
    760                         </td>
    761                         <td colspan="1">
    762                            <code> </code>
    763                         </td>
    764                         <td colspan="1">
    765                            <code>T</code>
    766                         </td>
    767                         <td colspan="1">
    768                            <code>e</code>
    769                         </td>
    770                         <td colspan="1">
    771                            <code>x</code>
    772                         </td>
    773                         <td colspan="1">
    774                            <code>t</code>
    775                         </td>
    776                         <td colspan="1">
    777                            <code> </code>
    778                         </td>
    779                         <td colspan="1">
    780                            <code>i</code>
    781                         </td>
    782                         <td colspan="1">
    783                            <code>n</code>
    784                         </td>
    785                         <td colspan="1">
    786                            <code> </code>
    787                         </td>
    788                         <td colspan="1">
    789                            <code>F</code>
    790                         </td>
    791                         <td colspan="1">
    792                            <code>a</code>
    793                         </td>
    794                         <td colspan="1">
    795                            <code>r</code>
    796                         </td>
    797                         <td colspan="1">
    798                            <code>s</code>
    799                         </td>
    800                         <td colspan="1">
    801                            <code>i</code>
    802                         </td>
    803                         <td colspan="1">
    804                            <code>:</code>
    805                         </td>
    806                         <td colspan="2">
    807                            <code>ى</code>
    808                         </td>
    809                         <td colspan="2">
    810                            <code>س</code>
    811                         </td>
    812                         <td colspan="2">
    813                            <code>ر</code>
    814                         </td>
    815                         <td colspan="2">
    816                            <code>ا</code>
    817                         </td>
    818                         <td colspan="2">
    819                            <code>ف</code>
    820                         </td>
    821                         <td colspan="1">
    822                            <code> </code>
    823                         </td>
    824                         <td colspan="2">
    825                            <code>ن</code>
    826                         </td>
    827                         <td colspan="2">
    828                            <code>ت</code>
    829                         </td>
    830                         <td colspan="2">
    831                            <code>Ù
    832 </code>
    833                         </td>
    834                         <td colspan="1">
    835                            <code> </code>
    836                         </td>
    837                         <td colspan="2">
    838                            <code>ك</code>
    839                         </td>
    840                         <td colspan="2">
    841                            <code>ى</code>
    842                         </td>
    843                      </tr>
    844                      <tr valign="top">
    845                         <td>UTF-8</td>
    846                         <td>
    847                            <code>41</code>
    848                         </td>
    849                         <td>
    850                            <code>20</code>
    851                         </td>
    852                         <td>
    853                            <code>54</code>
    854                         </td>
    855                         <td>
    856                            <code>65</code>
    857                         </td>
    858                         <td>
    859                            <code>78</code>
    860                         </td>
    861                         <td>
    862                            <code>74</code>
    863                         </td>
    864                         <td>
    865                            <code>20</code>
    866                         </td>
    867                         <td>
    868                            <code>69</code>
    869                         </td>
    870                         <td>
    871                            <code>6E</code>
    872                         </td>
    873                         <td>
    874                            <code>20</code>
    875                         </td>
    876                         <td>
    877                            <code>46</code>
    878                         </td>
    879                         <td>
    880                            <code>61</code>
    881                         </td>
    882                         <td>
    883                            <code>72</code>
    884                         </td>
    885                         <td>
    886                            <code>73</code>
    887                         </td>
    888                         <td>
    889                            <code>69</code>
    890                         </td>
    891                         <td>
    892                            <code>3A</code>
    893                         </td>
    894                         <td>
    895                            <code>D9</code>
    896                         </td>
    897                         <td>
    898                            <code>89</code>
    899                         </td>
    900                         <td>
    901                            <code>D8</code>
    902                         </td>
    903                         <td>
    904                            <code>B3</code>
    905                         </td>
    906                         <td>
    907                            <code>D8</code>
    908                         </td>
    909                         <td>
    910                            <code>B1</code>
    911                         </td>
    912                         <td>
    913                            <code>D8</code>
    914                         </td>
    915                         <td>
    916                            <code>A7</code>
    917                         </td>
    918                         <td>
    919                            <code>D9</code>
    920                         </td>
    921                         <td>
    922                            <code>81</code>
    923                         </td>
    924                         <td>
    925                            <code>20</code>
    926                         </td>
    927                         <td>
    928                            <code>D9</code>
    929                         </td>
    930                         <td>
    931                            <code>86</code>
    932                         </td>
    933                         <td>
    934                            <code>D8</code>
    935                         </td>
    936                         <td>
    937                            <code>AA</code>
    938                         </td>
    939                         <td>
    940                            <code>D9</code>
    941                         </td>
    942                         <td>
    943                            <code>85</code>
    944                         </td>
    945                         <td>
    946                            <code>20</code>
    947                         </td>
    948                         <td>
    949                            <code>D9</code>
    950                         </td>
    951                         <td>
    952                            <code>83</code>
    953                         </td>
    954                         <td>
    955                            <code>D9</code>
    956                         </td>
    957                         <td>
    958                            <code>89</code>
    959                         </td>
    960                      </tr>
    961                      <tr valign="top">
    962                         <td>u8UniByte</td>
    963                         <td>
    964                            <code>1</code>
    965                         </td>
    966                         <td>
    967                            <code>1</code>
    968                         </td>
    969                         <td>
    970                            <code>1</code>
    971                         </td>
    972                         <td>
    973                            <code>1</code>
    974                         </td>
    975                         <td>
    976                            <code>1</code>
    977                         </td>
    978                         <td>
    979                            <code>1</code>
    980                         </td>
    981                         <td>
    982                            <code>1</code>
    983                         </td>
    984                         <td>
    985                            <code>1</code>
    986                         </td>
    987                         <td>
    988                            <code>1</code>
    989                         </td>
    990                         <td>
    991                            <code>1</code>
    992                         </td>
    993                         <td>
    994                            <code>1</code>
    995                         </td>
    996                         <td>
    997                            <code>1</code>
    998                         </td>
    999                         <td>
    1000                            <code>1</code>
    1001                         </td>
    1002                         <td>
    1003                            <code>1</code>
    1004                         </td>
    1005                         <td>
    1006                            <code>1</code>
    1007                         </td>
    1008                         <td>
    1009                            <code>1</code>
    1010                         </td>
    1011                         <td>
    1012                            <code>0</code>
    1013                         </td>
    1014                         <td>
    1015                            <code>0</code>
    1016                         </td>
    1017                         <td>
    1018                            <code>0</code>
    1019                         </td>
    1020                         <td>
    1021                            <code>0</code>
    1022                         </td>
    1023                         <td>
    1024                            <code>0</code>
    1025                         </td>
    1026                         <td>
    1027                            <code>0</code>
    1028                         </td>
    1029                         <td>
    1030                            <code>0</code>
    1031                         </td>
    1032                         <td>
    1033                            <code>0</code>
    1034                         </td>
    1035                         <td>
    1036                            <code>0</code>
    1037                         </td>
    1038                         <td>
    1039                            <code>0</code>
    1040                         </td>
    1041                         <td>
    1042                            <code>1</code>
    1043                         </td>
    1044                         <td>
    1045                            <code>0</code>
    1046                         </td>
    1047                         <td>
    1048                            <code>0</code>
    1049                         </td>
    1050                         <td>
    1051                            <code>0</code>
    1052                         </td>
    1053                         <td>
    1054                            <code>0</code>
    1055                         </td>
    1056                         <td>
    1057                            <code>0</code>
    1058                         </td>
    1059                         <td>
    1060                            <code>0</code>
    1061                         </td>
    1062                         <td>
    1063                            <code>1</code>
    1064                         </td>
    1065                         <td>
    1066                            <code>0</code>
    1067                         </td>
    1068                         <td>
    1069                            <code>0</code>
    1070                         </td>
    1071                         <td>
    1072                            <code>0</code>
    1073                         </td>
    1074                         <td>
    1075                            <code>0</code>
     830                        <td>
     831                           <code>A Text in Farsi: ى س ر ا ف ن ت Ù
     832 Ùƒ ى </code>
     833                        </td>
     834                     </tr>
     835                     <tr valign="top">
     836                        <td>High Nybbles</td>
     837                        <td>
     838                           <code>42567726624677632D8DBDBDAD82D8DAD82D8D8</code>
     839                        </td>
     840                     </tr>
     841                     <tr valign="top">
     842                        <td>Low Nybbles</td>
     843                        <td>
     844                           <code>10458409E061239A099838187910968A9509399</code>
     845                        </td>
     846                     </tr>
     847                     <tr valign="top">
     848                        <td>u8Unibyte</td>
     849                        <td>
     850                           <code>11111111111111111__________1______1____</code>
    1076851                        </td>
    1077852                     </tr>
     
    1079854                        <td>u8Prefix</td>
    1080855                        <td>
    1081                            <code>0</code>
    1082                         </td>
    1083                         <td>
    1084                            <code>0</code>
    1085                         </td>
    1086                         <td>
    1087                            <code>0</code>
    1088                         </td>
    1089                         <td>
    1090                            <code>0</code>
    1091                         </td>
    1092                         <td>
    1093                            <code>0</code>
    1094                         </td>
    1095                         <td>
    1096                            <code>0</code>
    1097                         </td>
    1098                         <td>
    1099                            <code>0</code>
    1100                         </td>
    1101                         <td>
    1102                            <code>0</code>
    1103                         </td>
    1104                         <td>
    1105                            <code>0</code>
    1106                         </td>
    1107                         <td>
    1108                            <code>0</code>
    1109                         </td>
    1110                         <td>
    1111                            <code>0</code>
    1112                         </td>
    1113                         <td>
    1114                            <code>0</code>
    1115                         </td>
    1116                         <td>
    1117                            <code>0</code>
    1118                         </td>
    1119                         <td>
    1120                            <code>0</code>
    1121                         </td>
    1122                         <td>
    1123                            <code>0</code>
    1124                         </td>
    1125                         <td>
    1126                            <code>0</code>
    1127                         </td>
    1128                         <td>
    1129                            <code>1</code>
    1130                         </td>
    1131                         <td>
    1132                            <code>0</code>
    1133                         </td>
    1134                         <td>
    1135                            <code>1</code>
    1136                         </td>
    1137                         <td>
    1138                            <code>0</code>
    1139                         </td>
    1140                         <td>
    1141                            <code>1</code>
    1142                         </td>
    1143                         <td>
    1144                            <code>0</code>
    1145                         </td>
    1146                         <td>
    1147                            <code>1</code>
    1148                         </td>
    1149                         <td>
    1150                            <code>0</code>
    1151                         </td>
    1152                         <td>
    1153                            <code>1</code>
    1154                         </td>
    1155                         <td>
    1156                            <code>0</code>
    1157                         </td>
    1158                         <td>
    1159                            <code>0</code>
    1160                         </td>
    1161                         <td>
    1162                            <code>1</code>
    1163                         </td>
    1164                         <td>
    1165                            <code>0</code>
    1166                         </td>
    1167                         <td>
    1168                            <code>1</code>
    1169                         </td>
    1170                         <td>
    1171                            <code>0</code>
    1172                         </td>
    1173                         <td>
    1174                            <code>1</code>
    1175                         </td>
    1176                         <td>
    1177                            <code>0</code>
    1178                         </td>
    1179                         <td>
    1180                            <code>0</code>
    1181                         </td>
    1182                         <td>
    1183                            <code>1</code>
    1184                         </td>
    1185                         <td>
    1186                            <code>0</code>
    1187                         </td>
    1188                         <td>
    1189                            <code>1</code>
    1190                         </td>
    1191                         <td>
    1192                            <code>0</code>
     856                           <code>_________________1_1_1_1_1__1_1_1__1_1_</code>
    1193857                        </td>
    1194858                     </tr>
     
    1196860                        <td>u8Suffix</td>
    1197861                        <td>
    1198                            <code>0</code>
    1199                         </td>
    1200                         <td>
    1201                            <code>0</code>
    1202                         </td>
    1203                         <td>
    1204                            <code>0</code>
    1205                         </td>
    1206                         <td>
    1207                            <code>0</code>
    1208                         </td>
    1209                         <td>
    1210                            <code>0</code>
    1211                         </td>
    1212                         <td>
    1213                            <code>0</code>
    1214                         </td>
    1215                         <td>
    1216                            <code>0</code>
    1217                         </td>
    1218                         <td>
    1219                            <code>0</code>
    1220                         </td>
    1221                         <td>
    1222                            <code>0</code>
    1223                         </td>
    1224                         <td>
    1225                            <code>0</code>
    1226                         </td>
    1227                         <td>
    1228                            <code>0</code>
    1229                         </td>
    1230                         <td>
    1231                            <code>0</code>
    1232                         </td>
    1233                         <td>
    1234                            <code>0</code>
    1235                         </td>
    1236                         <td>
    1237                            <code>0</code>
    1238                         </td>
    1239                         <td>
    1240                            <code>0</code>
    1241                         </td>
    1242                         <td>
    1243                            <code>0</code>
    1244                         </td>
    1245                         <td>
    1246                            <code>0</code>
    1247                         </td>
    1248                         <td>
    1249                            <code>1</code>
    1250                         </td>
    1251                         <td>
    1252                            <code>0</code>
    1253                         </td>
    1254                         <td>
    1255                            <code>1</code>
    1256                         </td>
    1257                         <td>
    1258                            <code>0</code>
    1259                         </td>
    1260                         <td>
    1261                            <code>1</code>
    1262                         </td>
    1263                         <td>
    1264                            <code>0</code>
    1265                         </td>
    1266                         <td>
    1267                            <code>1</code>
    1268                         </td>
    1269                         <td>
    1270                            <code>0</code>
    1271                         </td>
    1272                         <td>
    1273                            <code>1</code>
    1274                         </td>
    1275                         <td>
    1276                            <code>0</code>
    1277                         </td>
    1278                         <td>
    1279                            <code>0</code>
    1280                         </td>
    1281                         <td>
    1282                            <code>1</code>
    1283                         </td>
    1284                         <td>
    1285                            <code>0</code>
    1286                         </td>
    1287                         <td>
    1288                            <code>1</code>
    1289                         </td>
    1290                         <td>
    1291                            <code>0</code>
    1292                         </td>
    1293                         <td>
    1294                            <code>1</code>
    1295                         </td>
    1296                         <td>
    1297                            <code>0</code>
    1298                         </td>
    1299                         <td>
    1300                            <code>0</code>
    1301                         </td>
    1302                         <td>
    1303                            <code>1</code>
    1304                         </td>
    1305                         <td>
    1306                            <code>0</code>
    1307                         </td>
    1308                         <td>
    1309                            <code>1</code>
     862                           <code>__________________1_1_1_1_1__1_1_1__1_1</code>
    1310863                        </td>
    1311864                     </tr>
     
    1313866                        <td>u8Prefix2</td>
    1314867                        <td>
    1315                            <code>0</code>
    1316                         </td>
    1317                         <td>
    1318                            <code>0</code>
    1319                         </td>
    1320                         <td>
    1321                            <code>0</code>
    1322                         </td>
    1323                         <td>
    1324                            <code>0</code>
    1325                         </td>
    1326                         <td>
    1327                            <code>0</code>
    1328                         </td>
    1329                         <td>
    1330                            <code>0</code>
    1331                         </td>
    1332                         <td>
    1333                            <code>0</code>
    1334                         </td>
    1335                         <td>
    1336                            <code>0</code>
    1337                         </td>
    1338                         <td>
    1339                            <code>0</code>
    1340                         </td>
    1341                         <td>
    1342                            <code>0</code>
    1343                         </td>
    1344                         <td>
    1345                            <code>0</code>
    1346                         </td>
    1347                         <td>
    1348                            <code>0</code>
    1349                         </td>
    1350                         <td>
    1351                            <code>0</code>
    1352                         </td>
    1353                         <td>
    1354                            <code>0</code>
    1355                         </td>
    1356                         <td>
    1357                            <code>0</code>
    1358                         </td>
    1359                         <td>
    1360                            <code>0</code>
    1361                         </td>
    1362                         <td>
    1363                            <code>1</code>
    1364                         </td>
    1365                         <td>
    1366                            <code>0</code>
    1367                         </td>
    1368                         <td>
    1369                            <code>1</code>
    1370                         </td>
    1371                         <td>
    1372                            <code>0</code>
    1373                         </td>
    1374                         <td>
    1375                            <code>1</code>
    1376                         </td>
    1377                         <td>
    1378                            <code>0</code>
    1379                         </td>
    1380                         <td>
    1381                            <code>1</code>
    1382                         </td>
    1383                         <td>
    1384                            <code>0</code>
    1385                         </td>
    1386                         <td>
    1387                            <code>1</code>
    1388                         </td>
    1389                         <td>
    1390                            <code>0</code>
    1391                         </td>
    1392                         <td>
    1393                            <code>0</code>
    1394                         </td>
    1395                         <td>
    1396                            <code>1</code>
    1397                         </td>
    1398                         <td>
    1399                            <code>0</code>
    1400                         </td>
    1401                         <td>
    1402                            <code>1</code>
    1403                         </td>
    1404                         <td>
    1405                            <code>0</code>
    1406                         </td>
    1407                         <td>
    1408                            <code>1</code>
    1409                         </td>
    1410                         <td>
    1411                            <code>0</code>
    1412                         </td>
    1413                         <td>
    1414                            <code>0</code>
    1415                         </td>
    1416                         <td>
    1417                            <code>1</code>
    1418                         </td>
    1419                         <td>
    1420                            <code>0</code>
    1421                         </td>
    1422                         <td>
    1423                            <code>1</code>
    1424                         </td>
    1425                         <td>
    1426                            <code>0</code>
     868                           <code>_________________1_1_1_1_1__1_1_1__1_1_</code>
    1427869                        </td>
    1428870                     </tr>
     
    1430872                        <td>u8Scope22</td>
    1431873                        <td>
    1432                            <code>0</code>
    1433                         </td>
    1434                         <td>
    1435                            <code>0</code>
    1436                         </td>
    1437                         <td>
    1438                            <code>0</code>
    1439                         </td>
    1440                         <td>
    1441                            <code>0</code>
    1442                         </td>
    1443                         <td>
    1444                            <code>0</code>
    1445                         </td>
    1446                         <td>
    1447                            <code>0</code>
    1448                         </td>
    1449                         <td>
    1450                            <code>0</code>
    1451                         </td>
    1452                         <td>
    1453                            <code>0</code>
    1454                         </td>
    1455                         <td>
    1456                            <code>0</code>
    1457                         </td>
    1458                         <td>
    1459                            <code>0</code>
    1460                         </td>
    1461                         <td>
    1462                            <code>0</code>
    1463                         </td>
    1464                         <td>
    1465                            <code>0</code>
    1466                         </td>
    1467                         <td>
    1468                            <code>0</code>
    1469                         </td>
    1470                         <td>
    1471                            <code>0</code>
    1472                         </td>
    1473                         <td>
    1474                            <code>0</code>
    1475                         </td>
    1476                         <td>
    1477                            <code>0</code>
    1478                         </td>
    1479                         <td>
    1480                            <code>0</code>
    1481                         </td>
    1482                         <td>
    1483                            <code>1</code>
    1484                         </td>
    1485                         <td>
    1486                            <code>0</code>
    1487                         </td>
    1488                         <td>
    1489                            <code>1</code>
    1490                         </td>
    1491                         <td>
    1492                            <code>0</code>
    1493                         </td>
    1494                         <td>
    1495                            <code>1</code>
    1496                         </td>
    1497                         <td>
    1498                            <code>0</code>
    1499                         </td>
    1500                         <td>
    1501                            <code>1</code>
    1502                         </td>
    1503                         <td>
    1504                            <code>0</code>
    1505                         </td>
    1506                         <td>
    1507                            <code>1</code>
    1508                         </td>
    1509                         <td>
    1510                            <code>0</code>
    1511                         </td>
    1512                         <td>
    1513                            <code>0</code>
    1514                         </td>
    1515                         <td>
    1516                            <code>1</code>
    1517                         </td>
    1518                         <td>
    1519                            <code>0</code>
    1520                         </td>
    1521                         <td>
    1522                            <code>1</code>
    1523                         </td>
    1524                         <td>
    1525                            <code>0</code>
    1526                         </td>
    1527                         <td>
    1528                            <code>1</code>
    1529                         </td>
    1530                         <td>
    1531                            <code>0</code>
    1532                         </td>
    1533                         <td>
    1534                            <code>0</code>
    1535                         </td>
    1536                         <td>
    1537                            <code>1</code>
    1538                         </td>
    1539                         <td>
    1540                            <code>0</code>
    1541                         </td>
    1542                         <td>
    1543                            <code>1</code>
    1544                         </td>
    1545                      </tr>
    1546                      <tr valign="top">
    1547                         <td>u8Error</td>
    1548                         <td>
    1549                            <code>0</code>
    1550                         </td>
    1551                         <td>
    1552                            <code>0</code>
    1553                         </td>
    1554                         <td>
    1555                            <code>0</code>
    1556                         </td>
    1557                         <td>
    1558                            <code>0</code>
    1559                         </td>
    1560                         <td>
    1561                            <code>0</code>
    1562                         </td>
    1563                         <td>
    1564                            <code>0</code>
    1565                         </td>
    1566                         <td>
    1567                            <code>0</code>
    1568                         </td>
    1569                         <td>
    1570                            <code>0</code>
    1571                         </td>
    1572                         <td>
    1573                            <code>0</code>
    1574                         </td>
    1575                         <td>
    1576                            <code>0</code>
    1577                         </td>
    1578                         <td>
    1579                            <code>0</code>
    1580                         </td>
    1581                         <td>
    1582                            <code>0</code>
    1583                         </td>
    1584                         <td>
    1585                            <code>0</code>
    1586                         </td>
    1587                         <td>
    1588                            <code>0</code>
    1589                         </td>
    1590                         <td>
    1591                            <code>0</code>
    1592                         </td>
    1593                         <td>
    1594                            <code>0</code>
    1595                         </td>
    1596                         <td>
    1597                            <code>0</code>
    1598                         </td>
    1599                         <td>
    1600                            <code>0</code>
    1601                         </td>
    1602                         <td>
    1603                            <code>0</code>
    1604                         </td>
    1605                         <td>
    1606                            <code>0</code>
    1607                         </td>
    1608                         <td>
    1609                            <code>0</code>
    1610                         </td>
    1611                         <td>
    1612                            <code>0</code>
    1613                         </td>
    1614                         <td>
    1615                            <code>0</code>
    1616                         </td>
    1617                         <td>
    1618                            <code>0</code>
    1619                         </td>
    1620                         <td>
    1621                            <code>0</code>
    1622                         </td>
    1623                         <td>
    1624                            <code>0</code>
    1625                         </td>
    1626                         <td>
    1627                            <code>0</code>
    1628                         </td>
    1629                         <td>
    1630                            <code>0</code>
    1631                         </td>
    1632                         <td>
    1633                            <code>0</code>
    1634                         </td>
    1635                         <td>
    1636                            <code>0</code>
    1637                         </td>
    1638                         <td>
    1639                            <code>0</code>
    1640                         </td>
    1641                         <td>
    1642                            <code>0</code>
    1643                         </td>
    1644                         <td>
    1645                            <code>0</code>
    1646                         </td>
    1647                         <td>
    1648                            <code>0</code>
    1649                         </td>
    1650                         <td>
    1651                            <code>0</code>
    1652                         </td>
    1653                         <td>
    1654                            <code>0</code>
    1655                         </td>
    1656                         <td>
    1657                            <code>0</code>
    1658                         </td>
    1659                         <td>
    1660                            <code>0</code>
     874                           <code>__________________1_1_1_1_1__1_1_1__1_1</code>
     875                        </td>
     876                     </tr>
     877                     <tr valign="top">
     878                        <td>Errors</td>
     879                        <td>
     880                           <code>_______________________________________</code>
    1661881                        </td>
    1662882                     </tr>
     
    1664884               </table>
    1665885
     886
    1666887            </para>
    1667 
    1668             <section>
    1669                <title>UTF-8 Validation Streams</title>
    1670                <para> Proper formation of UTF-8 byte sequences requires that the correct number of
    1671                   suffix bytes always follow a UTF-8 prefix byte and that certain illegal
    1672                   combinations are ruled out. For example, sequences beginning with the prefix bytes
    1673                   0xF5 through 0xFF are illegal as they would represent code point values above
    1674                   10FFFF. In addition, there are constraints on the first suffix byte following
    1675                   certain special prefixes, namely that a suffix following the prefix 0xE0 must fall
    1676                   in the range 0xA0 –0xBF, a suffix following the prefix 0xED must fall in the range
    1677                   0x80 –0x9F, a suffix following the prefix 0xF0 must fall in the range 0x90 –0xBF
    1678                   and a suffix following the prefix 0xF4 must fall in the range 0x80 –0x8F. The task
    1679                   of ensuring that each of these constraints hold is known as UTF-8 validation. The
    1680                   following bit streams xE0, xED, xF0, xF4, xA0_xBF, x80_x9F, x90_xBF, and x80_x8F
    1681                   are constructed to flag UTF-8 validation errors. The result of UTF-8 validation is
    1682                   an UTF-8 error flag bit stream contructed as an ORing of a series of UTF-8
    1683                   validation tests. </para>
    1684             </section>
    1685888         </section>
    1686889
    1687890         <section>
    1688             <title>UTF-8 Surrogate Character Streams</title>
    1689             <para> The Unicode surrogate characters OxFFFF and OxFFFE correspond to the UTF-8
    1690                encodings of 0xEF 0xBF 0xBF and 0xEF 0xBF 0xBE respectively. As such, bit streams
    1691                xEF, xBF, and xBE are constructed to flag illegal surrogate characters in XML as part
    1692                of the XML character validation process. </para>
     891            <title>UTF-8 Validation Streams</title>
     892            <para> Proper formation of UTF-8 byte sequences requires that the correct number of
     893               suffix bytes always follow a UTF-8 prefix byte, and that certain illegal byte
     894               combinations are ruled out. For example, sequences beginning with the prefix bytes
     895               0xF5 through 0xFF are illegal as they would represent code point values above 10FFFF.
     896               In addition, there are constraints on the first suffix byte following certain special
     897               prefixes, namely that a suffix following the prefix 0xE0 must fall in the range
     898               0xA0–0xBF, a suffix following the prefix 0xED must fall in the range 0x80–0x9F, a
     899               suffix following the prefix 0xF0 must fall in the range 0x90–0xBF and a suffix
     900               following the prefix 0xF4 must fall in the range 0x80–0x8F. The task of ensuring that
     901               each of these constraints hold is known as UTF-8 validation. The bit streams xE0,
     902               xED, xF0, xF4, xA0_xBF, x80_x9F, x90_xBF, and x80_x8F are constructed to flag the
     903               aforementioned UTF-8 validation errors. The result of UTF-8 validation is a UTF-8
     904               error flag bit stream contructed as the ORing of a series of UTF-8 validation tests.
     905            </para>
     906         </section>
     907
     908         <section>
     909            <title>XML Character Validation Streams</title>
     910            <para>The UTF-8 character sequences <emphasis>0xEF 0xBF 0xBF</emphasis> and
     911                  <emphasis>0xEF 0xBF 0xBE</emphasis> correspond to the Unicode code points 0xFFFE
     912               and 0xFFFF respectively. In XML 1.0, 0xFFFE and 0xFFFF represent characters outside
     913               the legal XML character ranges. As such, bit streams which mark 0xEF, 0xBF, and 0xBE
     914               character are constructed to flag illegal UTF-8 character sequences. </para>
    1693915         </section>
    1694916
     
    1721943               u8LastByte (u8UniByte , u8Scope22 , u8Scope33 , and u8Scope44 ) and u8Scope42 streams
    1722944               mark the positions at which the correct UTF-16 bits are computed. The bit sets at
    1723                other positions must be deleted to compress the streams to UTF-16 indexed form.
     945               other positions must be deleted to compress the streams to the UTF-16 indexed form.
    1724946            </para>
    1725947         </section>
     
    1729951         <title>Control Character Streams</title>
    1730952         <para>The control character bit streams marks ASCII control characters in the range
    1731             x00-x1F. Additional control character bit streams mark the tab, carriage return, line
    1732             feed, and space characters. An additional bit stream to mark carriage return line
    1733             combinations is also constructed. Control character bit streams support the operations
    1734             of XML character validation and XML end-of-line handling.</para>
     953            0x00-0x1F. Additional control character bit streams mark the tab, carriage return, line
     954            feed, and space character. In addition, a bit stream to mark carriage return line
     955            combinations is also constructed. Presently, control character bit streams support the
     956            operations of XML 1.0 character validation and XML end-of-line handling.</para>
    1735957
    1736958         <section>
    1737959            <title>XML Character Validation</title>
    1738             <para>Legal characters in XML are the tab, carriage return, and line feed characters
    1739                together with all Unicode characters and excluding the surrogate blocks, OxFFFE and
     960            <para>Legal characters in XML are the tab, carriage return, and line feed characters,
     961               together with all Unicode characters and excluding the surrogate blocks, as well as hexadecimal OxFFFE and
    1740962               OxFFFF [<xref linkend="XML10"/>]. The x00_x1F bit stream is constructed and used in
    1741                combination with additional control character bit streams to flags illegal control
    1742                characters in XML. Bit stream XML character validation results in the production of a
    1743                bit stream error mask. </para>
     963               combination with the additional control character bit streams to flags the positions
     964               of illegal control characters.</para>
    1744965         </section>
    1745966
    1746967         <section>
    1747968            <title>XML 1.0 End-of-line Handling</title>
    1748             <para>In XML 1.0 the two-character sequence CR LF (carriage return, line feed) together
    1749                with any CR character not followed by a LF character must be converted to a single LF
     969            <para>In XML 1.0 the two-character sequence CR LF (carriage return, line feed) as well as
     970               any CR character not followed by a LF character must be converted to a single LF
    1750971               character [<xref linkend="XML10"/>].</para>
    1751972            <para>By defining carriage return, line feed, and carriage return line feed bit streams,
    1752973               dentoted CR, LF and CRLF respectively, end-of-line normalization processing can be
    1753                performed in parallel, using only a small number of logical and shift operations.</para>
     974               performed in parallel using only a small number of logical and shift operations.</para>
    1754975            <para/>
    1755976            <para>The following example demonstrates the generation of the CRLF deletion mask. In
    1756977               this example, the position of all CR characters followed by LF characters are marked
    1757978               for deletion. Isolated carriage returns are then replaced with LF characters.
    1758                Completion of this process satisfies the XML 1.0 end-of-line handling requirements.</para>
     979               Completion of this process satisfies the XML 1.0 end-of-line handling requirements.
     980               For clarity, this example encodes input data carriage returns as
     981               <emphasis>C</emphasis> characters, whereas line feed characters are shown as
     982                  <emphasis>L</emphasis> characters.</para>
    1759983            <para>
    1760984               <table>
     
    17861010                     </tr>
    17871011                     <tr valign="top">
    1788                         <td>Delmask</td>
    1789                         <td>
    1790                            <code>-------------------------1--------------------------------------</code>
     1012                        <td>DelMask</td>
     1013                        <td>
     1014                           <code>--------------------------1-------------------------------------</code>
    17911015                        </td>
    17921016                     </tr>
     
    17991023      </section>
    18001024
    1801       <!-- Comment Processing Instruction and CDATA Section Streams ??? -->
    1802 
    18031025      <section>
    1804          <title>Comment, Processing Instruction, CDATA Section Streams</title>
    1805          <para>Comments, processing instructions and CDATA sections represent sections of an XML
    1806             document which may contain markup that is not interpreted by the XML processor. As such,
    1807             the union of comment, processing Instruction and CDATA section extents define regions of
    1808             non-interpreteable markup in an XML document. The stream formed by this union is termed
    1809             the ignorable markup stream. The purpose of the the ignorable markup stream is to mark
    1810             the positions of all non-interpreted XML markup for deletion.</para>
    1811          <para>The following tables provides an example of marking comment extents. <table>
     1026         <title>Call Out Streams</title>
     1027         <para> Call out bit streams mark the extents of XML markup structures such as comments,
     1028            processing instruction and CDATA sections as well as physical structures such as character and
     1029            entity references and general references.  Call out streams are also formed for logical markup structures such
     1030            start tags, end tags and empty element tags. </para>
     1031         <section>
     1032            <title>Comment, Processing Instruction and CDATA Section Call Out Streams</title>
     1033            <para>Comments, processing instructions and CDATA sections call out streams, Ct_Span,
     1034               PI_Span and CD_Span respectively, define sections of an XML document which
     1035               contain markup that is not interpreted by an XML processor. As such, the union of
     1036               Ct_Span, PI_Span and CD_Span streams defines the regions of non-interpreteable markup.
     1037               The stream formed by this union is termed the CtCDPI_Mask.</para>
     1038            <para>The following tables provides an example of constructing the CtCDPI_Mask. </para>
     1039            <table>
     1040
    18121041               <caption>
    1813                   <para>Comment, Processing Instuction and CDATA Streams</para>
     1042                  <para>CtCDPI Mask Generation</para>
    18141043               </caption>
    18151044               <colgroup>
    18161045                  <col align="left" valign="top"/>
     1046                  <col align="left" valign="top"/>
    18171047               </colgroup>
    18181048               <tbody>
    18191049                  <tr valign="top">
    1820                      <td>Input Data</td>
    1821                      <td>
    1822                         <code>&lt;!-- do a&amp;b --&gt; &lt;?php f(a&amp;b)
    1823                            ?&gt; &lt;!-- show x&lt;&lt;1
    1824                            --&gt;&lt;![CDATA[abcdedf x&lt;&lt;1 ]]&gt;</code>
    1825                      </td>
    1826                   </tr>
    1827                   <tr valign="top">
    1828                      <td>Comment</td>
    1829                      <td>
    1830                         <code>111111111111111-----------------111111111111111111-------------------------</code>
    1831                      </td>
    1832                   </tr>
    1833                   <tr valign="top">
    1834                      <td>CDATA</td>
    1835                      <td>
    1836                         <code>--------------------------------------------------1111111111111111111111111</code>
    1837                      </td>
    1838                   </tr>
    1839                   <tr valign="top">
    1840                      <td>PI</td>
    1841                      <td>
    1842                         <code>----------------111111111111111--------------------------------------------</code>
    1843                      </td>
    1844                   </tr>
     1050                     <td>input data</td>
     1051                     <td>
     1052                        <code> &lt;?php?&gt; &lt;!-- example --&gt; &lt;![CDATA[
     1053                           shift: a&lt;&lt;1 ]]&gt; </code>
     1054                     </td>
     1055                  </tr>
     1056
     1057                  <tr valign="top">
     1058                     <td>CD_Span</td>
     1059                     <td>
     1060                        <code>______________________________11111111111111111111111__</code>
     1061                     </td>
     1062                  </tr>
     1063                  <tr valign="top">
     1064                     <td>Ct_Span</td>
     1065                     <td>
     1066                        <code>_____________111111111111______________________________</code>
     1067                     </td>
     1068                  </tr>
     1069                  <tr valign="top">
     1070                     <td>PI_Span</td>
     1071                     <td>
     1072                        <code>__11111________________________________________________</code>
     1073                     </td>
     1074                  </tr>
     1075                  <tr valign="top">
     1076                     <td>CtCDPI_Mask</td>
     1077                     <td>
     1078                        <code>__111111___111111111111111___1111111111111111111111111_</code>
     1079                     </td>
     1080                  </tr>
     1081                  <tr valign="top">
     1082                     <td>Error</td>
     1083                     <td>
     1084                        <code>________________________________________________________</code>
     1085                     </td>
     1086                  </tr>
     1087
    18451088               </tbody>
    18461089            </table>
    1847          </para>
    1848          <para> With the removal of all non-interpreteable markup, several phases of parallel bit
    1849             stream based SIMD operations may follow, operating on up to 128 byte positions on
    1850             current commondity processors, assured of XML markup relevancy, and in parallel. For
    1851             example, with the removal of comments, processing instructions and CDATA secions, XML
    1852             names may be identified and length sorted for efficient symbol table construction. </para>
    1853          <para> As an aside, comments and CDATA sections must be first be validated to ensure that
    1854             comments do not contain "--" sequences and that CDATA sections do not contain
    1855             "]]&gt;" sequences prior to ignorable markup stream generation.</para>
    1856       </section>
    1857 
    1858 
    1859       <section>
    1860          <title>Predefined Entity Deletion Streams</title>
    1861          <para>Predefined character (<![CDATA[&lt;,&gt;,&amp;,&apos;,&quot;]]>)
    1862             and numeric character references (&amp;#nnnn;, &amp;#xhhhh;) must be replaced by
    1863             a single character [<xref linkend="XML10"/>]. Using a strategy analogous as that used
    1864             for comment, processing instruction and CDATA sections, the marking of the union of all
    1865             references byte position extents in bit space, with the exception of the final bit
    1866             position of each reference, defines the deletion mask stream for predefined
    1867          entities.</para>
    1868       </section>
    1869 
    1870       <section>
    1871          <title>Parallel Parsing with Bit Stream Addition Streams</title>
    1872          <para>Whereas sequential bit scans over lexical item streams form the basis of XML parsing
    1873             in the current Parabix parser, a new method of parallel parsing has been developed and
    1874             prototyped using the concept of bitstream addition. Fundamental to this method is the
    1875             concept of a <emphasis>cursor</emphasis> stream, a bit stream marking the positions of
    1876             multiple parallel parses currently in process. </para>
    1877          <para>The results of parsing using the bit stream addition technique are producing using a
    1878             series of <emphasis>call-out</emphasis> bit streams. These streams mark the beginning
    1879             and end of each start tag, end tag and empty tag. Within tags, additional streams exist
    1880             to mark start and end positions for tag names, attribute names and attribute valus. An
    1881             error flag stream marks the positions of any syntactic errors encountered during
    1882             parsing.</para>
    1883          <para>
     1090            <para> With the removal of all non-interpreteable markup, several phases of parallel bit
     1091               stream based SIMD operations may follow operating on up to 128 byte positions on
     1092               current commondity processors and assured of XML markup relevancy. For
     1093               example, with the extents identification of comments, processing instructions and
     1094               CDATA secions, XML names may be identified and length sorted for efficient symbol
     1095               table construction. </para>
     1096            <para> As an aside, comments and CDATA sections must first be validated to ensure
     1097               that comments do not contain "--" sequences and that CDATA sections do not contain illegal
     1098               "]]&gt;" sequences prior to ignorable markup stream generation.</para>
     1099         </section>
     1100
     1101         <section>
     1102            <title>Reference Call Out Streams</title>
     1103            <para>The reference call out streams are the GenRefs, DecRefs, and HexRefs streams. This
     1104               subset of the call out streams marks the extents of all but the closing semicolon of
     1105               general and character references.</para>
     1106            <para>Predefined character
     1107               (<![CDATA[&lt;,&gt;,&amp;,&apos;,&quot;]]>) and numeric character
     1108               references (&amp;#nnnn;, &amp;#xhhhh;) must be replaced by a single character
     1109                  [<xref linkend="XML10"/>]. As previously shown, this subset of call out streams enables the construction of a DelMask for
     1110               references.</para>
     1111         </section>
     1112
     1113         <section>
     1114            <title>Tag Call Out Streams</title>
     1115            <para>Whereas sequential bit scans over lexical item streams form the basis of XML
     1116               parsing, in the current Parabix parser a new method of parallel parsing has been
     1117               developed and prototyped using the concept of bitstream addition. Fundamental to this
     1118               method is the concept of a <emphasis>cursor</emphasis> stream, a bit stream marking
     1119               the positions of multiple parallel parses currently in process. </para>
     1120            <para>The results of parallel parsing using the bit stream addition technique produces a
     1121               set of tag call out bit streams. These streams mark the extents of each start tag,
     1122               end tag and empty element tag. Within tags, additional streams mark start
     1123               and end positions for tag names, as well as attribute names and values. An error flag
     1124               stream marks the positions of any syntactic errors encountered during parsing.</para>
     1125            <para> The set of tag call out streams consists of the ElemNames, AttNames, AttVals, Tags,
     1126               EmptyTagEnds and EndTags bit streams. The following example demonstrates the bit
     1127               stream output produced which from parallel parsing using bit stream addition. </para>
    18841128            <table>
    18851129               <caption>
    1886                   <para>Parallel Parsing Call Out Streams</para>
     1130                  <para>Tag Call Out Streams</para>
    18871131               </caption>
    18881132               <colgroup>
    18891133                  <col align="left" valign="top"/>
     1134                  <col align="left" valign="top"/>
    18901135               </colgroup>
    18911136               <tbody>
     
    18931138                     <td>Input Data</td>
    18941139                     <td>
    1895                         <code>&lt;first
    1896                            att1=&quot;val1&quot;&gt;&lt;second/&gt;&lt;third
    1897                            wrong=value&gt;some
    1898                         text&lt;/third&gt;&lt;/first/&gt;</code>
    1899                      </td>
    1900                   </tr>
    1901                   <tr valign="top">
    1902                      <td>ElemNamePositions</td>
    1903                      <td>
    1904                         <code>-1------------------1--------1-------------------------------------------</code>
    1905                      </td>
    1906                   </tr>
    1907                   <tr valign="top">
    1908                      <td>ElemNameFollows</td>
    1909                      <td>
    1910                         <code>------1-------------------1-------1--------------------------------------</code>
    1911                      </td>
    1912                   </tr>
    1913                   <tr valign="top">
    1914                      <td>STagEnds</td>
    1915                      <td>
    1916                         <code>------------------1------------------------------------------------------</code>
     1140                        <code>&lt;root&gt;&lt;t1&gt;text&lt;/t1&gt;&lt;t2
     1141                           a1=&apos;foo&apos; a2 =
     1142                           &apos;fie&apos;&gt;more&lt;/t2&gt;&lt;tag3
     1143                           att3=&apos;b&apos;/&gt;&lt;/root&gt;</code>
     1144                     </td>
     1145                  </tr>
     1146
     1147                  <tr valign="top">
     1148                     <td>ElemNames</td>
     1149                     <td>
     1150                        <code>_1111__11___________11_______________________________1111__________________</code>
     1151                     </td>
     1152                  </tr>
     1153                  <tr valign="top">
     1154                     <td>AttNames</td>
     1155                     <td>
     1156                        <code>_______________________11_______11________________________1111_____________</code>
     1157                     </td>
     1158                  </tr>
     1159                  <tr valign="top">
     1160                     <td>AttrVals</td>
     1161                     <td>
     1162                        <code>__________________________11111______11111_____________________111_________</code>
    19171163                     </td>
    19181164                  </tr>
     
    19201166                     <td>EmptyTagEnds</td>
    19211167                     <td>
    1922                         <code>---------------------------1---------------------------------------------</code>
    1923                      </td>
    1924                   </tr>
    1925                   <tr valign="top">
    1926                      <td>ParseError</td>
    1927                      <td>
    1928                         <code>-----------------------------------------1-----------------------------1-</code>
    1929                      </td>
    1930                   </tr>
    1931                   <tr valign="top">
    1932                      <td>AttNameStarts</td>
    1933                      <td>
    1934                         <code>-------1---------------------------1-------------------------------------</code>
    1935                      </td>
    1936                   </tr>
    1937                   <tr valign="top">
    1938                      <td>AttNameFollows</td>
    1939                      <td>
    1940                         <code>-----------1----------------------------1--------------------------------</code>
    1941                      </td>
    1942                   </tr>
    1943                   <tr valign="top">
    1944                      <td>AttValStarts</td>
    1945                      <td>
    1946                         <code>------------1----------------------------1-------------------------------</code>
    1947                      </td>
    1948                   </tr>
    1949                   <tr valign="top">
    1950                      <td>AttValEnds</td>
    1951                      <td>
    1952                         <code>-----------------1-------------------------------------------------------</code>
    1953                      </td>
    1954                   </tr>
    1955                   <tr valign="top">
    1956                      <td>EndTagSeconds</td>
    1957                      <td>
    1958                         <code>---------------------------------------------------------1-------1-------</code>
    1959                      </td>
    1960                   </tr>
    1961                   <tr valign="top">
    1962                      <td>EndTagEnds</td>
    1963                      <td>
    1964                         <code>---------------------------------------------------------------1-------1-</code>
     1168                        <code>___________________________________________________________________1_______</code>
     1169                     </td>
     1170                  </tr>
     1171                  <tr valign="top">
     1172                     <td>EndTags</td>
     1173                     <td>
     1174                        <code>_______________111______________________________111__________________11111_</code>
     1175                     </td>
     1176                  </tr>
     1177
     1178                  <tr valign="top">
     1179                     <td>Start/EmptyTags</td>
     1180                     <td>
     1181                        <code>_1111__11___________1111111111111111111111___________11111111111111________</code>
     1182                     </td>
     1183                  </tr>
     1184                  <tr valign="top">
     1185                     <td>Error</td>
     1186                     <td>
     1187                        <code>____________________________________________________________________________</code>
    19651188                     </td>
    19661189                  </tr>
    19671190               </tbody>
    19681191            </table>
    1969          </para>
    1970 
     1192
     1193         </section>
    19711194      </section>
    1972 
    19731195   </section>
    19741196   <section>
Note: See TracChangeset for help on using the changeset viewer.