Changeset 675


Ignore:
Timestamp:
Oct 27, 2010, 11:59:07 AM (8 years ago)
Author:
ksherdy
Message:

Implement escape and parallel_prefix_parity defs and demos.

Location:
proto/JSON
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • proto/JSON/byteclass.py

    r672 r675  
    1010        RFC 4627 - JavaScript Object Notation (JSON) 
    1111        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
    12 
     12       
    1313        number = [ minus ] int [ frac ] [ exp ]
    1414        decimal-point = %x2E       ; .
     
    2121        plus = %x2B                ; +
    2222        zero = %x30                ; 0
    23 
     23       
    2424        Any single character alternative can be combined into a single character class.
    25 
     25       
    2626        """
     27        #Object
     28        LCurlyBrace = 0
     29        Colon = 0
     30        Comma = 0
     31        RCurlyBrace = 0
     32        #Array
     33        LSquareBracket = 0
     34        RSquareBracket = 0
     35        #Number
     36        Minus = 0
     37        Zero = 0
     38        Digit1_9 = 0
     39        Digit0_9 = 0
     40        DecimalPoint = 0
     41        Ee = 0
     42        PlusMinus = 0
     43        NumberFollowSet = 0
     44        #String
     45        DQuotes = 0
     46        RSolidus = 0
     47        Solidus = 0
     48        b = 0
     49        f = 0
     50        n = 0
     51        t = 0
     52        u = 0
     53        Digit0_ = 0
    2754
    2855def classify_bytes(bit) :
     
    3461  temp5 = (bit[6] & bit[7]);
    3562  temp6 = (temp4 & temp5);
    36   lex.Left_Curly_Brace = (temp3 & temp6);
     63  lex.LCurlyBrace = (temp3 & temp6);
    3764  temp7 = (bit[0] | bit[1]);
    3865  temp8 = (temp2 &~ temp7);
     
    4875  temp16 = (bit[7] &~ bit[6]);
    4976  temp17 = (temp13 & temp16);
    50   lex.Right_Curly_Brace = (temp3 & temp17);
     77  lex.RCurlyBrace = (temp3 & temp17);
    5178  temp18 = (bit[3] &~ bit[2]);
    5279  temp19 = (temp1 & temp18);
    53   lex.Left_Square_Bracket = (temp19 & temp6);
    54   lex.Right_Square_Bracket = (temp19 & temp17);
     80  lex.LSquareBracket = (temp19 & temp6);
     81  lex.RSquareBracket = (temp19 & temp17);
    5582  lex.Minus = (temp12 & temp17);
    5683  temp20 = (bit[4] | bit[5]);
     
    6188  temp24 = (bit[5] | temp14);
    6289  temp25 = ((bit[4] & temp23)|(~(bit[4]) & temp24));
    63   lex.Digit_1_9 = (temp8 & temp25);
     90  lex.Digit1_9 = (temp8 & temp25);
    6491  temp26 = (bit[4] & temp22);
    65   lex.Digit_0_9 = (temp8 &~ temp26);
     92  lex.Digit0_9 = (temp8 &~ temp26);
    6693  temp27 = (temp13 & temp9);
    67   lex.Decimal_Point = (temp12 & temp27);
     94  lex.DecimalPoint = (temp12 & temp27);
    6895  temp28 = (bit[5] &~ bit[4]);
    6996  temp29 = (temp28 & temp16);
     
    7198  temp31 = (temp30 &~ temp11);
    7299  temp32 = (temp1 &~ temp31);
    73   lex.E_e = (temp29 & temp32);
     100  lex.Ee = (temp29 & temp32);
    74101  temp33 = (temp6 | temp17);
    75   lex.Plus_Minus = (temp12 & temp33);
    76   temp34 = (lex.Comma | lex.Right_Curly_Brace);
    77   lex.Number_Follow_Set = (temp34 | lex.Right_Square_Bracket);
     102  lex.PlusMinus = (temp12 & temp33);
     103  temp34 = (lex.Comma | lex.RCurlyBrace);
     104  lex.NumberFollowSet = (temp34 | lex.RSquareBracket);
     105  lex.DQuote = (temp19 & temp15);
     106  lex.RSolidus = (temp19 & temp15);
     107  lex.Solidus = (temp19 & temp15);
     108  lex.b = (temp19 & temp15);
     109  lex.f = (temp19 & temp15);
     110  lex.n = (temp19 & temp15);
     111  lex.t = (temp19 & temp15);
     112  lex.u = (temp19 & temp15);
     113  temp35 = (temp1 &~ temp30);
     114  temp36 = (temp35 &~ bit[4]);
     115  temp37 = (~temp5);
     116  temp38 = ((bit[5] & temp37)|(~(bit[5]) & temp14));
     117  temp39 = (temp36 & temp38);
     118  lex.Digit0_9 = (lex.Digit0_9 | temp39);
    78119  return (lex)
    79120
  • proto/JSON/json_prototype.py

    r674 r675  
    1717import bitutil
    1818import byteclass
     19import math
    1920import sys
    2021
     
    2526# Bitstream function defs input/output *only* bitstream type variables.
    2627# Global declarations allow debug blocks in bitstream defs. Do not shadow variables.
    27 data = ""
     28u8data = ""
    2829lgth = 0
    2930
     
    3435
    3536        M1 = bitutil.ScanThru(M0, lex.Minus & M0)               # ? Optional character class [-]
    36         E1 = M1 &~(lex.Zero|lex.Digit_1_9)
     37        E1 = M1 &~(lex.Zero|lex.Digit1_9)
    3738
    3839        M1a = M1 & lex.Zero                                     # Split
    39         M1b = M1 & lex.Digit_0_9                               
     40        M1b = M1 & lex.Digit0_9                         
    4041        M2a = bitutil.Advance(M1a)
    4142        M2b = bitutil.Advance(M1b)
    42         M3b = bitutil.ScanThru(M2b,lex.Digit_0_9)
     43        M3b = bitutil.ScanThru(M2b,lex.Digit0_9)
    4344        M4 = M2a | M3b                                          # Join
    4445       
    45         M4a = M4 &~(lex.Decimal_Point)                          # Split
    46         M4b = M4 & (lex.Decimal_Point)
     46        M4a = M4 &~(lex.DecimalPoint)                           # Split
     47        M4b = M4 & (lex.DecimalPoint)
    4748        M5b = bitutil.Advance(M4b)
    48         E5b = M5b &~(lex.Digit_0_9)                             # + [0-9]+
    49         M6 = bitutil.ScanThru(M5b,lex.Digit_0_9)
     49        E5b = M5b &~(lex.Digit0_9)                              # + [0-9]+
     50        M6 = bitutil.ScanThru(M5b,lex.Digit0_9)
    5051        M7 = M4a | M6                                           # Join
    5152       
    52         M7a = M7 &~(lex.E_e)                                    # Split
    53         E7a = M7a &~(lex.Number_Follow_Set)
    54         M7b = M7 &(lex.E_e)
     53        M7a = M7 &~(lex.Ee)                                     # Split
     54        E7a = M7a &~(lex.NumberFollowSet)
     55        M7b = M7 &(lex.Ee)
    5556        M8b = bitutil.Advance(M7b)
    56         M9b = bitutil.ScanThru(M8b, lex.Plus_Minus & M8b)       # ? Optional character class [+-]               
    57         E9b  = M9b &~(lex.Digit_0_9)                            # + [0-9]+
    58         M10b = bitutil.ScanThru(M9b,lex.Digit_0_9)
    59         E10b = M10b &~(lex.Number_Follow_Set)
     57        M9b = bitutil.ScanThru(M8b, lex.PlusMinus & M8b)        # ? Optional character class [+-]               
     58        E9b  = M9b &~(lex.Digit0_9)                             # + [0-9]+
     59        M10b = bitutil.ScanThru(M9b,lex.Digit0_9)
     60        E10b = M10b &~(lex.NumberFollowSet)
    6061        M11 = M7a | M10b                                        # Join
    6162       
     
    6364       
    6465        if debug:
    65                 bitutil.print_aligned_streams([('Input data', data),
     66                bitutil.print_aligned_streams([('Input Data', u8data),
    6667                              ('M0', bitutil.bitstream2string(M0, lgth)),
    6768                              ('M1', bitutil.bitstream2string(M1, lgth)),
     
    8889                              ('Errors', bitutil.bitstream2string(Errors, lgth))])             
    8990        return Errors
    90        
    91 def demo_validate_number(data):
    92         """     
     91
     92
     93def demo_validate_number(u8data):
     94        r"""   
    9395        For example, 00 is not reported as an error case, but -- is reported as an error case.
    94        
     96
    9597        RFC 4627 - JavaScript Object Notation (JSON) 
    9698        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
    97        
     99
    98100        number = [ minus ] int [ frac ] [ exp ]
    99101        decimal-point = %x2E       ; .
     
    106108        plus = %x2B                ; +
    107109        zero = %x30                ; 0 
    108         """     
     110        """
    109111        r"""
    110112        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
    111         Input data   : ,-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,
    112         Minus        : _1_11_1_____1___1___1____1_______1_______1_________________________
    113         Zero         : _________11__11__1___1____1___11___________1______1__1__1__________
    114         Digit_1_9    : __________________________________111_111____111____1____111111111_
    115         Digit_0_9    : __________________________________111_111____111____1____111111111_
    116         Decimal_Point: __________________1___1____1_________1______1______________________
    117         E_e          : _______________________1____1______________________1_______________
    118         Plus_Minus   : _1_11_1_____1___1___1____1_______1_______1______1_____1____________
    119         EOF_Mask     : 1111111111111111111111111111111111111111111111111111111111111111111_
    120         Errors       : __1_1__1__1___1____1___1____1__1_________1______1_____1__1_________
    121         <BLANKLINE>
    122         """ 
     113        Input Data  : ,-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,
     114        Minus       : _1_11_1_____1___1___1____1_______1_______1_________________________
     115        Zero        : _________11__11__1___1____1___11___________1______1__1__1__________
     116        Digit1_9    : __________________________________111_111____111____1____111111111_
     117        Digit0_9    : _________11__11__1___1____1___11__111_111__1_111__1_11__1111111111_
     118        DecimalPoint: __________________1___1____1_________1______1______________________
     119        Ee          : _______________________1____1______________________1_______________
     120        PlusMinus   : _1_11_1_____1___1___1____1_______1_______1______1_____1____________
     121        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111_
     122        Errors      : __1_1__1__1___1____1___1____1__1_________1______1_____1__1_________
     123        <BLANKLINE>
     124        """
    123125        r"""
    124126        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
    125         Input data   : ,0.5,98.6,99.44,1066,1e1,0.1e1,1e-1,1e00,2e+00,2e-00,1234567890,-9876.543210,0.123456789e-12,1.234567890E+34,23456789012E66,
    126         Minus        : _________________________________1_______________1______________1________________________1__________________________________
    127         Zero         : _1_______________1_______1____________11____11____11__________1____________1_1_________________________1_____________1______
    128         Digit_1_9    : ___1_11_1_11_11_1_11_1_1___1_1_1__1_1____1_____1_____111111111___1111_11111____111111111__11_1_11111111___11_11111111_11_11_
    129         Digit_0_9    : ___1_11_1_11_11_1_11_1_1___1_1_1__1_1____1_____1_____111111111___1111_11111____111111111__11_1_11111111___11_11111111_11_11_
    130         Decimal_Point: __1____1____1_____________1__________________________________________1________1_______________1_____________________________
    131         E_e          : ______________________1_____1___1____1____1_____1_______________________________________1_______________1_______________1___
    132         Plus_Minus   : _________________________________1_________1_____1______________1________________________1_______________1__________________
    133         EOF_Mask     : 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111_
    134         Errors       : ____________________________________________________________________________________________________________________________
    135         <BLANKLINE>
    136         """     
     127        Input Data  : ,0.5,98.6,99.44,1066,1e1,0.1e1,1e-1,1e00,2e+00,2e-00,1234567890,-9876.543210,0.123456789e-12,1.234567890E+34,23456789012E66,
     128        Minus       : _________________________________1_______________1______________1________________________1__________________________________
     129        Zero        : _1_______________1_______1____________11____11____11__________1____________1_1_________________________1_____________1______
     130        Digit1_9    : ___1_11_1_11_11_1_11_1_1___1_1_1__1_1____1_____1_____111111111___1111_11111____111111111__11_1_11111111___11_11111111_11_11_
     131        Digit0_9    : ___1_11_1_11_11_1_11_1_1___1_1_1__1_1____1_____1_____111111111___1111_11111____111111111__11_1_11111111___11_11111111_11_11_
     132        DecimalPoint: __1____1____1_____________1__________________________________________1________1_______________1_____________________________
     133        Ee          : ______________________1_____1___1____1____1_____1_______________________________________1_______________1_______________1___
     134        PlusMinus   : _________________________________1_________1_____1______________1________________________1_______________1__________________
     135        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111_
     136        Errors      : ____________________________________________________________________________________________________________________________
     137        <BLANKLINE>
     138        """
    137139        r"""
    138140        >>> demo_validate_number(',012345,12345,0,00,-0,-00')
    139         Input data   : ,012345,12345,0,00,-0,-00
    140         Minus        : ___________________1__1__
    141         Zero         : _1____________1_11__1__11
    142         Digit_1_9    : __11111_11111____________
    143         Digit_0_9    : __11111_11111____________
    144         Decimal_Point: _________________________
    145         E_e          : _________________________
    146         Plus_Minus   : ___________________1__1__
    147         EOF_Mask     : 1111111111111111111111111_
    148         Errors       : __1______________1______1
     141        Input Data  : ,012345,12345,0,00,-0,-00
     142        Minus       : ___________________1__1__
     143        Zero        : _1____________1_11__1__11
     144        Digit1_9    : __11111_11111____________
     145        Digit0_9    : __11111_11111____________
     146        DecimalPoint: _________________________
     147        Ee          : _________________________
     148        PlusMinus   : ___________________1__1__
     149        EOF_Mask    : 1111111111111111111111111_
     150        Errors      : __1______________1______1
    149151        <BLANKLINE>
    150152        """ 
    151153        global lgth
    152         lgth = len(data)
    153 
    154         (bit, EOF_mask) = bitutil.transpose_streams(data)
     154        lgth = len(u8data)
     155
     156        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
    155157        (lex) = byteclass.classify_bytes(bit)
    156158        Errors = validate_number(lex,EOF_mask)
    157159
    158         bitutil.print_aligned_streams([('Input data', data),
     160        bitutil.print_aligned_streams([('Input Data', u8data),
    159161                              ('Minus', bitutil.bitstream2string(lex.Minus, lgth)),
    160162                              ('Zero', bitutil.bitstream2string(lex.Zero, lgth)),
    161                               ('Digit_1_9', bitutil.bitstream2string(lex.Digit_1_9, lgth)),
    162                               ('Digit_0_9', bitutil.bitstream2string(lex.Digit_1_9, lgth)),
    163                               ('Decimal_Point', bitutil.bitstream2string(lex.Decimal_Point, lgth)),
    164                               ('E_e', bitutil.bitstream2string(lex.E_e, lgth)),
    165                               ('Plus_Minus', bitutil.bitstream2string(lex.Plus_Minus, lgth)),
     163                              ('Digit1_9', bitutil.bitstream2string(lex.Digit1_9, lgth)),
     164                              ('Digit0_9', bitutil.bitstream2string(lex.Digit0_9, lgth)),
     165                              ('DecimalPoint', bitutil.bitstream2string(lex.DecimalPoint, lgth)),
     166                              ('Ee', bitutil.bitstream2string(lex.Ee, lgth)),
     167                              ('PlusMinus', bitutil.bitstream2string(lex.PlusMinus, lgth)),
    166168                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
    167169                              ('Errors', bitutil.bitstream2string(Errors, lgth))])
     170
     171def simd_const_4(hexdigit,EOF_mask):
     172        r"""
     173        IDISA library function.
     174        """
     175        lgth = bitutil.count_leading_zeroes(~EOF_mask)/4
     176        return int(hexdigit*(lgth+1),16)&EOF_mask
     177       
     178def parse_escape(lex, EOF_mask):
     179        odd = simd_const_4('a',EOF_mask)
     180        even = simd_const_4('5',EOF_mask)
     181       
     182        start = lex.RSolidus &~ bitutil.Advance(lex.RSolidus)
     183       
     184        even_start = start & even
     185        even_final = (even_start + lex.RSolidus) & ~lex.RSolidus
     186        even_escape = even_final & odd
     187       
     188        odd_start = start & odd
     189        odd_final = (odd_start + lex.RSolidus) & ~lex.RSolidus
     190        odd_escape = (odd_final & even)
     191       
     192        escape = (even_escape | odd_escape)
     193       
     194        return escape
     195       
     196def demo_parse_escape(u8data):
     197        global lgth
     198        lgth = len(u8data)
     199
     200        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
     201        (lex) = byteclass.classify_bytes(bit)
     202        (escape) = parse_escape(lex,EOF_mask)
     203
     204        bitutil.print_aligned_streams([('Input Data', u8data),
     205                              ('lex.RSolidus', bitutil.bitstream2string(lex.RSolidus, lgth)),   
     206                              ('escape', bitutil.bitstream2string(escape, lgth)),       
     207                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
     208        return
     209
     210def parallel_prefix_parity(strm,lgth):
     211        r"""
     212        Translate to library function.
     213       
     214        x y  x XOR y
     215        ------------
     216        0 0   0
     217        0 1   1
     218        1 0   1
     219        0 0   0
     220
     221        Let n = length(bitstream).
     222
     223        Define Pk,i as the parity of the bit range [k-(k+2^i),k] for bit positions n >= k >= 1.
     224       
     225        Base Case: Pk,0 = bitstream at position k, for all k, n >= k >= 0.
     226        Inductive Step: Pk,i+1 = (Pk,i << 2^i) XOR Pk,i.
     227       
     228        Pk,ceil(log(n) denotes the parity of the bit position k, n >= k >= 0.
     229       
     230        bitstream[k] = 1 --> odd parity
     231        bitstream[k] = 0 --> even parity
     232        """
     233        t1 = strm
     234        for i in range(0,int(math.ceil(math.log(lgth,2)))):
     235                t2 = t1 ^ (t1 << pow(2,i))
     236                t1 = t2
     237        return t2 
     238
     239def demo_parallel_prefix_parity(u8data):
     240        r"""
     241        >>> demo_parallel_prefix_parity('[data] [data][data] [data] [data')
     242        Input Data        : [data] [data][data] [data] [data
     243        lex.LSquareBracket: 1______1_____1______1______1____
     244        lex.RSquareBracket: _____1______1_____1______1______
     245        parity            : 11111__11111_11111__11111__11111
     246        EOF_Mask          : 11111111111111111111111111111111_
     247        <BLANKLINE>
     248        """
     249        global lgth
     250        lgth = len(u8data)
     251
     252        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
     253        (lex) = byteclass.classify_bytes(bit)
     254        brackets = (lex.LSquareBracket | lex.RSquareBracket)
     255        (parity) = parallel_prefix_parity(brackets,lgth)
     256
     257        bitutil.print_aligned_streams([('Input Data', u8data),
     258                              ('lex.LSquareBracket', bitutil.bitstream2string(lex.LSquareBracket, lgth)),
     259                              ('lex.RSquareBracket', bitutil.bitstream2string(lex.RSquareBracket, lgth)),                             
     260                              ('parity', bitutil.bitstream2string(parity, lgth)),       
     261                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1))])
     262        return
     263
    168264if __name__ == "__main__":
    169265        import doctest
     
    174270                sys.exit(2)
    175271
    176         data = bitutil.readfile(sys.argv[1])
    177         demo_validate_number(data)
    178        
     272        u8data = bitutil.readfile(sys.argv[1])
     273#       demo_validate_number(u8data)
     274#       demo_parse_escape(u8data)
     275        demo_parallel_prefix_parity(u8data)
Note: See TracChangeset for help on using the changeset viewer.