Changeset 684


Ignore:
Timestamp:
Oct 30, 2010, 4:34:25 PM (8 years ago)
Author:
ksherdy
Message:

General reorganization. Addition of JSON String processing logic.

Location:
proto/JSON
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • proto/JSON/byteclass.py

    r682 r684  
    7777
    7878def classify_bytes(bit) :
    79   u8 = u8_streams()
    80   lex = lexical_streams()
    81   ctrl = control_streams()
    82   u8.unibyte = (~bit[0]);
    83   u8.prefix = (bit[0] & bit[1]);
    84   u8.prefix2 = (u8.prefix &~ bit[2]);
    85   temp1 = (bit[2] &~ bit[3]);
    86   u8.prefix3 = (u8.prefix & temp1);
    87   temp2 = (bit[2] & bit[3]);
    88   u8.prefix4 = (u8.prefix & temp2);
    89   u8.suffix = (bit[0] &~ bit[1]);
    90   temp3 = (bit[2] | bit[3]);
    91   temp4 = (u8.prefix &~ temp3);
    92   temp5 = (bit[4] | bit[5]);
    93   temp6 = (temp5 | bit[6]);
    94   temp7 = (temp4 &~ temp6);
    95   temp8 = (bit[6] | bit[7]);
    96   temp9 = (bit[5] & temp8);
    97   temp10 = (bit[4] | temp9);
    98   temp11 = (u8.prefix4 & temp10);
    99   u8.badprefix = (temp7 | temp11);
    100   temp12 = (temp5 | temp8);
    101   u8.xE0 = (u8.prefix3 &~ temp12);
    102   temp13 = (bit[4] & bit[5]);
    103   temp14 = (bit[7] &~ bit[6]);
    104   temp15 = (temp13 & temp14);
    105   u8.xED = (u8.prefix3 & temp15);
    106   u8.xF0 = (u8.prefix4 &~ temp12);
    107   temp16 = (bit[5] &~ bit[4]);
    108   temp17 = (temp16 &~ temp8);
    109   u8.xF4 = (u8.prefix4 & temp17);
    110   u8.xA0_xBF = (u8.suffix & bit[2]);
    111   u8.x80_x9F = (u8.suffix &~ bit[2]);
    112   u8.x90_xBF = (u8.suffix & temp3);
    113   u8.x80_x8F = (u8.suffix &~ temp3);
    114   temp18 = (bit[0] | bit[1]);
    115   temp19 = (temp18 | bit[2]);
    116   ctrl.x00_x1F = (~temp19);
    117   temp20 = (temp18 | temp3);
    118   ctrl.CR = (temp15 &~ temp20);
    119   temp21 = (bit[4] &~ bit[5]);
    120   temp22 = (bit[6] &~ bit[7]);
    121   temp23 = (temp21 & temp22);
    122   ctrl.LF = (temp23 &~ temp20);
    123   temp24 = (temp21 & temp14);
    124   ctrl.HT = (temp24 &~ temp20);
    125   temp25 = (temp1 &~ temp18);
    126   ctrl.SP = (temp25 &~ temp12);
    127   temp26 = (bit[1] &~ bit[0]);
    128   temp27 = (temp26 & temp2);
    129   temp28 = (bit[6] & bit[7]);
    130   temp29 = (temp21 & temp28);
    131   lex.LCurlyBrace = (temp27 & temp29);
    132   temp30 = (temp2 &~ temp18);
    133   lex.Colon = (temp30 & temp23);
    134   temp31 = (temp13 &~ temp8);
    135   lex.Comma = (temp25 & temp31);
    136   lex.RCurlyBrace = (temp27 & temp15);
    137   temp32 = (bit[3] &~ bit[2]);
    138   temp33 = (temp26 & temp32);
    139   lex.LSquareBracket = (temp33 & temp29);
    140   lex.RSquareBracket = (temp33 & temp15);
    141   lex.Minus = (temp25 & temp15);
    142   lex.Zero = (temp30 &~ temp12);
    143   temp34 = (bit[5] | bit[6]);
    144   temp35 = (~temp34);
    145   temp36 = (bit[5] | temp8);
    146   temp37 = ((bit[4] & temp35)|(~(bit[4]) & temp36));
    147   lex.Digit1_9 = (temp30 & temp37);
    148   temp38 = (bit[4] & temp34);
    149   lex.Digit0_9 = (temp30 &~ temp38);
    150   temp39 = (temp13 & temp22);
    151   lex.DecimalPoint = (temp25 & temp39);
    152   temp40 = (temp16 & temp14);
    153   temp41 = (temp3 &~ temp1);
    154   temp42 = (temp26 &~ temp41);
    155   lex.Ee = (temp40 & temp42);
    156   temp43 = (temp29 | temp15);
    157   lex.PlusMinus = (temp25 & temp43);
    158   temp44 = (lex.Comma | lex.RCurlyBrace);
    159   lex.NumberFollowSet = (temp44 | lex.RSquareBracket);
    160   lex.DQuote = (temp33 & temp31);
    161   lex.RSolidus = (temp33 & temp31);
    162   lex.Solidus = (temp33 & temp31);
    163   lex.b = (temp33 & temp31);
    164   lex.f = (temp33 & temp31);
    165   lex.n = (temp33 & temp31);
    166   lex.t = (temp33 & temp31);
    167   lex.u = (temp33 & temp31);
    168   temp45 = (temp26 & temp1);
    169   temp46 = (temp45 &~ bit[4]);
    170   temp47 = (~temp28);
    171   temp48 = ((bit[5] & temp47)|(~(bit[5]) & temp8));
    172   temp49 = (temp46 & temp48);
    173   temp50 = (lex.Digit0_9 | temp49);
    174   temp51 = (temp26 &~ temp3);
    175   temp52 = (temp51 &~ bit[4]);
    176   temp53 = (temp52 & temp48);
    177   lex.HexDigit = (temp50 | temp53);
    178   temp54 = (temp15 | temp23);
    179   temp55 = (temp54 | temp24);
    180   temp56 = (temp55 &~ temp20);
    181   lex.WS = (temp56 | ctrl.SP); 
    182   return (u8,lex,ctrl)
     79        u8 = u8_streams()
     80        lex = lexical_streams()
     81        ctrl = control_streams()
     82        u8.unibyte = (~bit[0]);
     83        u8.prefix = (bit[0] & bit[1]);
     84        u8.prefix2 = (u8.prefix &~ bit[2]);
     85        temp1 = (bit[2] &~ bit[3]);
     86        u8.prefix3 = (u8.prefix & temp1);
     87        temp2 = (bit[2] & bit[3]);
     88        u8.prefix4 = (u8.prefix & temp2);
     89        u8.suffix = (bit[0] &~ bit[1]);
     90        temp3 = (bit[2] | bit[3]);
     91        temp4 = (u8.prefix &~ temp3);
     92        temp5 = (bit[4] | bit[5]);
     93        temp6 = (temp5 | bit[6]);
     94        temp7 = (temp4 &~ temp6);
     95        temp8 = (bit[6] | bit[7]);
     96        temp9 = (bit[5] & temp8);
     97        temp10 = (bit[4] | temp9);
     98        temp11 = (u8.prefix4 & temp10);
     99        u8.badprefix = (temp7 | temp11);
     100        temp12 = (temp5 | temp8);
     101        u8.xE0 = (u8.prefix3 &~ temp12);
     102        temp13 = (bit[4] & bit[5]);
     103        temp14 = (bit[7] &~ bit[6]);
     104        temp15 = (temp13 & temp14);
     105        u8.xED = (u8.prefix3 & temp15);
     106        u8.xF0 = (u8.prefix4 &~ temp12);
     107        temp16 = (bit[5] &~ bit[4]);
     108        temp17 = (temp16 &~ temp8);
     109        u8.xF4 = (u8.prefix4 & temp17);
     110        u8.xA0_xBF = (u8.suffix & bit[2]);
     111        u8.x80_x9F = (u8.suffix &~ bit[2]);
     112        u8.x90_xBF = (u8.suffix & temp3);
     113        u8.x80_x8F = (u8.suffix &~ temp3);
     114        temp18 = (bit[0] | bit[1]);
     115        temp19 = (temp18 | bit[2]);
     116        ctrl.x00_x1F = (~temp19);
     117        temp20 = (temp18 | temp3);
     118        ctrl.CR = (temp15 &~ temp20);
     119        temp21 = (bit[4] &~ bit[5]);
     120        temp22 = (bit[6] &~ bit[7]);
     121        temp23 = (temp21 & temp22);
     122        ctrl.LF = (temp23 &~ temp20);
     123        temp24 = (temp21 & temp14);
     124        ctrl.HT = (temp24 &~ temp20);
     125        temp25 = (temp1 &~ temp18);
     126        ctrl.SP = (temp25 &~ temp12);
     127        temp26 = (bit[1] &~ bit[0]);
     128        temp27 = (temp26 & temp2);
     129        temp28 = (bit[6] & bit[7]);
     130        temp29 = (temp21 & temp28);
     131        lex.LCurlyBrace = (temp27 & temp29);
     132        temp30 = (temp2 &~ temp18);
     133        lex.Colon = (temp30 & temp23);
     134        temp31 = (temp13 &~ temp8);
     135        lex.Comma = (temp25 & temp31);
     136        lex.RCurlyBrace = (temp27 & temp15);
     137        temp32 = (bit[3] &~ bit[2]);
     138        temp33 = (temp26 & temp32);
     139        lex.LSquareBracket = (temp33 & temp29);
     140        lex.RSquareBracket = (temp33 & temp15);
     141        lex.Minus = (temp25 & temp15);
     142        lex.Zero = (temp30 &~ temp12);
     143        temp34 = (bit[5] | bit[6]);
     144        temp35 = (~temp34);
     145        temp36 = (bit[5] | temp8);
     146        temp37 = ((bit[4] & temp35)|(~(bit[4]) & temp36));
     147        lex.Digit1_9 = (temp30 & temp37);
     148        temp38 = (bit[4] & temp34);
     149        lex.Digit0_9 = (temp30 &~ temp38);
     150        temp39 = (temp13 & temp22);
     151        lex.DecimalPoint = (temp25 & temp39);
     152        temp40 = (temp16 & temp14);
     153        temp41 = (temp3 &~ temp1);
     154        temp42 = (temp26 &~ temp41);
     155        lex.Ee = (temp40 & temp42);
     156        temp43 = (temp29 | temp15);
     157        lex.PlusMinus = (temp25 & temp43);
     158        temp44 = (lex.Comma | lex.RCurlyBrace);
     159        lex.NumberFollowSet = (temp44 | lex.RSquareBracket);
     160        temp45 = (temp22 &~ temp5);
     161        lex.DQuote = (temp25 & temp45);
     162        lex.RSolidus = (temp33 & temp31);
     163        temp46 = (temp13 & temp28);
     164        lex.Solidus = (temp25 & temp46);
     165        temp47 = (temp26 & temp1);
     166        lex.b = (temp47 & temp45);
     167        temp48 = (temp16 & temp22);
     168        lex.f = (temp47 & temp48);
     169        lex.n = (temp47 & temp39);
     170        lex.t = (temp27 & temp17);
     171        lex.u = (temp27 & temp40);
     172        temp49 = (temp47 &~ bit[4]);
     173        temp50 = (~temp28);
     174        temp51 = ((bit[5] & temp50)|(~(bit[5]) & temp8));
     175        temp52 = (temp49 & temp51);
     176        temp53 = (lex.Digit0_9 | temp52);
     177        temp54 = (temp26 &~ temp3);
     178        temp55 = (temp54 &~ bit[4]);
     179        temp56 = (temp55 & temp51);
     180        lex.HexDigit = (temp53 | temp56);
     181        temp57 = (temp15 | temp23);
     182        temp58 = (temp57 | temp24);
     183        temp59 = (temp58 &~ temp20);
     184        lex.WS = (temp59 | ctrl.SP);
     185        return (u8,lex,ctrl)
    183186
  • proto/JSON/json_prototype.py

    r682 r684  
    3030u8data = ""
    3131lgth = 0
     32
     33def simd_const_4(hexdigit,EOF_mask):
     34        r"""
     35        IDISA library function.
     36        """
     37        lgth = bitutil.count_leading_zeroes(~EOF_mask)/4
     38        return int(hexdigit*(lgth+1),16)&EOF_mask
     39       
     40def parse_escape(lex, EOF_mask):
     41        odd = simd_const_4('a',EOF_mask)
     42        even = simd_const_4('5',EOF_mask)
     43       
     44        start = lex.RSolidus &~ bitutil.Advance(lex.RSolidus)
     45       
     46        even_start = start & even
     47        even_final = (even_start + lex.RSolidus) & ~lex.RSolidus
     48        even_escape = even_final & odd
     49       
     50        odd_start = start & odd
     51        odd_final = (odd_start + lex.RSolidus) & ~lex.RSolidus
     52        odd_escape = (odd_final & even)
     53       
     54        escape = (even_escape | odd_escape)
     55       
     56        return escape
     57       
     58def demo_parse_escape(u8data):
     59        global lgth
     60        lgth = len(u8data)
     61
     62        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
     63        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
     64        (escape) = parse_escape(lex,EOF_mask)
     65
     66        bitutil.print_aligned_streams([('Input Data', u8data),
     67                              ('lex.RSolidus', bitutil.bitstream2string(lex.RSolidus, lgth)),   
     68                              ('escape', bitutil.bitstream2string(escape, lgth)),       
     69                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
     70        return
     71
     72def parallel_prefix_parity(strm,lgth):
     73        r"""
     74        Translate to library function.
     75       
     76        x y  x XOR y
     77        ------------
     78        0 0   0
     79        0 1   1
     80        1 0   1
     81        0 0   0
     82
     83        Let n = length(bitstream).
     84
     85        Define Pk,i as the parity of the bit range [k-(k+2^i),k] for bit positions n >= k >= 1.
     86       
     87        Base Case: Pk,0 = bitstream at position k, for all k, n >= k >= 0.
     88        Inductive Step: Pk,i+1 = (Pk,i << 2^i) XOR Pk,i.
     89       
     90        Pk,ceil(log(n) denotes the parity of the bit position k, n >= k >= 0.
     91       
     92        bitstream[k] = 1 --> odd parity
     93        bitstream[k] = 0 --> even parity
     94        """
     95        t1 = strm
     96        for i in range(0,int(math.ceil(math.log(lgth,2)))):
     97                t2 = t1 ^ (t1 << pow(2,i))
     98                t1 = t2
     99        return t2 
     100
     101def demo_parallel_prefix_parity(u8data):
     102        r"""
     103        >>> demo_parallel_prefix_parity('[data] [data][data] [data] [data')
     104        Input Data        : [data] [data][data] [data] [data
     105        lex.LSquareBracket: 1______1_____1______1______1____
     106        lex.RSquareBracket: _____1______1_____1______1______
     107        parity            : 11111__11111_11111__11111__11111
     108        EOF_Mask          : 11111111111111111111111111111111_
     109        <BLANKLINE>
     110        """
     111        global lgth
     112        lgth = len(u8data)
     113
     114        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
     115        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
     116        brackets = (lex.LSquareBracket | lex.RSquareBracket)
     117        (parity) = parallel_prefix_parity(brackets,lgth)
     118
     119        bitutil.print_aligned_streams([('Input Data', u8data),
     120                              ('lex.LSquareBracket', bitutil.bitstream2string(lex.LSquareBracket, lgth)),
     121                              ('lex.RSquareBracket', bitutil.bitstream2string(lex.RSquareBracket, lgth)),                             
     122                              ('parity', bitutil.bitstream2string(parity, lgth)),       
     123                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
     124        return
     125
    32126
    33127def validate_number(lex, EOF_mask):
     
    92186        return Errors
    93187
    94 
    95188def demo_validate_number(u8data):
    96189        r"""   
    97         For example, 00 is not reported as an error case, but -- is reported as an error case.
    98 
    99190        RFC 4627 - JavaScript Object Notation (JSON) 
    100191        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
     
    171262                              ('Errors', bitutil.bitstream2string(Errors, lgth))])
    172263
    173 def simd_const_4(hexdigit,EOF_mask):
    174         r"""
    175         IDISA library function.
    176         """
    177         lgth = bitutil.count_leading_zeroes(~EOF_mask)/4
    178         return int(hexdigit*(lgth+1),16)&EOF_mask
    179        
    180 def parse_escape(lex, EOF_mask):
    181         odd = simd_const_4('a',EOF_mask)
    182         even = simd_const_4('5',EOF_mask)
    183        
    184         start = lex.RSolidus &~ bitutil.Advance(lex.RSolidus)
    185        
    186         even_start = start & even
    187         even_final = (even_start + lex.RSolidus) & ~lex.RSolidus
    188         even_escape = even_final & odd
    189        
    190         odd_start = start & odd
    191         odd_final = (odd_start + lex.RSolidus) & ~lex.RSolidus
    192         odd_escape = (odd_final & even)
    193        
    194         escape = (even_escape | odd_escape)
    195        
    196         return escape
    197        
    198 def demo_parse_escape(u8data):
    199         global lgth
    200         lgth = len(u8data)
    201 
    202         (bit, EOF_mask) = bitutil.transpose_streams(u8data)
    203         (u8, lex, ctrl) = byteclass.classify_bytes(bit)
    204         (escape) = parse_escape(lex,EOF_mask)
    205 
     264def validate_string(lex,escape,lgth):
     265        r"""
     266        RFC 4627 - JavaScript Object Notation (JSON) 
     267
     268        string = quotation-mark *char quotation-mark
     269        char = unescaped /
     270              escape (
     271                  %x22 /          ; "    quotation mark  U+0022
     272                  %x5C /          ; \    reverse solidus U+005C
     273                  %x2F /          ; /    solidus         U+002F
     274                  %x62 /          ; b    backspace       U+0008
     275                  %x66 /          ; f    form feed       U+000C
     276                  %x6E /          ; n    line feed       U+000A
     277                  %x72 /          ; r    carriage return U+000D
     278                  %x74 /          ; t    tab             U+0009
     279                  %x75 4HEXDIG )  ; uXXXX                U+XXXX
     280
     281        escape = %x5C              ; \
     282
     283        quotation-mark = %x22      ; "
     284
     285        unescaped = %x20-21 / %x23-5B / %x5D-10FFFF
     286        """
     287
     288        return
     289
     290def demo_validate_string(u8data):
     291
     292        global lgth
     293        lgth = len(u8data)
     294
     295        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
     296        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
     297        escape = parse_escape(lex, EOF_mask)
     298       
     299        # Mark String starts "
     300        unescaped_quotation_marks = (lex.DQuote &~ escape)
     301       
     302        # Mask String interiors
     303        parity_mask = parallel_prefix_parity(unescaped_quotation_marks, lgth)
     304        string_mask = parity_mask & bitutil.Advance(parity_mask)
     305       
     306       
     307       
     308        errors = validate_string(lex,escape,lgth)
     309       
     310        errors = 1
     311       
    206312        bitutil.print_aligned_streams([('Input Data', u8data),
    207                               ('lex.RSolidus', bitutil.bitstream2string(lex.RSolidus, lgth)),   
    208                               ('escape', bitutil.bitstream2string(escape, lgth)),       
    209                               ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
    210         return
    211 
    212 def parallel_prefix_parity(strm,lgth):
    213         r"""
    214         Translate to library function.
    215        
    216         x y  x XOR y
    217         ------------
    218         0 0   0
    219         0 1   1
    220         1 0   1
    221         0 0   0
    222 
    223         Let n = length(bitstream).
    224 
    225         Define Pk,i as the parity of the bit range [k-(k+2^i),k] for bit positions n >= k >= 1.
    226        
    227         Base Case: Pk,0 = bitstream at position k, for all k, n >= k >= 0.
    228         Inductive Step: Pk,i+1 = (Pk,i << 2^i) XOR Pk,i.
    229        
    230         Pk,ceil(log(n) denotes the parity of the bit position k, n >= k >= 0.
    231        
    232         bitstream[k] = 1 --> odd parity
    233         bitstream[k] = 0 --> even parity
    234         """
    235         t1 = strm
    236         for i in range(0,int(math.ceil(math.log(lgth,2)))):
    237                 t2 = t1 ^ (t1 << pow(2,i))
    238                 t1 = t2
    239         return t2 
    240 
    241 def demo_parallel_prefix_parity(u8data):
    242         r"""
    243         >>> demo_parallel_prefix_parity('[data] [data][data] [data] [data')
    244         Input Data        : [data] [data][data] [data] [data
    245         lex.LSquareBracket: 1______1_____1______1______1____
    246         lex.RSquareBracket: _____1______1_____1______1______
    247         parity            : 11111__11111_11111__11111__11111
    248         EOF_Mask          : 11111111111111111111111111111111_
    249         <BLANKLINE>
    250         """
    251         global lgth
    252         lgth = len(u8data)
    253 
    254         (bit, EOF_mask) = bitutil.transpose_streams(u8data)
    255         (u8, lex, ctrl) = byteclass.classify_bytes(bit)
    256         brackets = (lex.LSquareBracket | lex.RSquareBracket)
    257         (parity) = parallel_prefix_parity(brackets,lgth)
    258 
    259         bitutil.print_aligned_streams([('Input Data', u8data),
    260                               ('lex.LSquareBracket', bitutil.bitstream2string(lex.LSquareBracket, lgth)),
    261                               ('lex.RSquareBracket', bitutil.bitstream2string(lex.RSquareBracket, lgth)),                             
    262                               ('parity', bitutil.bitstream2string(parity, lgth)),       
    263                               ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
     313                              ('escape', bitutil.bitstream2string(escape, lgth)),
     314                              ('DQuote', bitutil.bitstream2string(lex.DQuote, lgth)),
     315                              ('unescaped_quotation_marks', bitutil.bitstream2string(unescaped_quotation_marks, lgth)),
     316                              ('string_mask', bitutil.bitstream2string(string_mask, lgth)),                           
     317                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
     318                              ('errors', bitutil.bitstream2string(errors, lgth))])     
     319                             
    264320        return
    265321
     
    268324        # Transpose to parallel bit streams and prepare an EOF mask.
    269325        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
    270 
     326       
    271327        # Classify bytes for UTF-8 processing, whitespace, control and JSON lexical analysis.
    272         (u8, control, lex) = byteclass.classify_bytes(bit)
    273 
     328        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
     329       
    274330        # Validate UTF-8 multibyte sequences and determine the UTF-8 scope streams.
    275331        u8 = u8u16.validate_utf8(u8) 
    276  
     332       
     333        # Mark escape characters
     334        escape = parse_escape(lex, EOF_mask)
     335       
     336#       bitutil.print_aligned_streams([('Input Data', u8data),
     337#                             ('escape', bitutil.bitstream2string(escape, lgth)),
     338#                             ('DQuote', bitutil.bitstream2string(lex.DQuote, lgth)),
     339#                             ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])       
     340       
     341        # Mark unescaped "
     342       
     343
    277344        return
    278345 
     
    295362
    296363        u8data = bitutil.readfile(sys.argv[1])
    297 #       demo_validate_number(u8data)
    298364#       demo_parse_escape(u8data)
    299365#       demo_parallel_prefix_parity(u8data)
     366#       demo_validate_number(u8data)
     367        demo_validate_string(u8data)
    300368#       demo_parse_json(u8data)
  • proto/JSON/u8u16.py

    r682 r684  
    4545        error_mask |= u8anyscope ^ u8.suffix
    4646        u8.error = error_mask   
     47       
    4748        return u8
    4849
Note: See TracChangeset for help on using the changeset viewer.