source: proto/JSON/json_prototype.py @ 675

Last change on this file since 675 was 675, checked in by ksherdy, 9 years ago

Implement escape and parallel_prefix_parity defs and demos.

File size: 10.5 KB
Line 
1# -*- coding: utf-8 -*-
2#
3# json_prototype.py
4#
5# Ken Herdy
6# Oct. 13, 2010
7#
8#----------------------------------------------------------------------------
9#
10# We use python's unlimited precision integers for unbounded bit streams.
11# This permits simple logical operations on the entire stream.
12# Assumption: bitstreams are little-endian (e.g., as on x86).
13#
14#----------------------------------------------------------------------------
15#
16
17import bitutil
18import byteclass
19import math
20import sys
21
22debug = False
23filename = "json_prototype.py"
24
25# Globals
26# Bitstream function defs input/output *only* bitstream type variables.
27# Global declarations allow debug blocks in bitstream defs. Do not shadow variables.
28u8data = ""
29lgth = 0
30
31def validate_number(lex, EOF_mask):
32        Errors = 0     
33        M0 = 0                                                  # Assume the cursor is at the first Minus, Zero, or Digit_1_9 character
34        M0 = bitutil.Advance(lex.Comma)                         # WARNING - A hack to set initial cursor postions and ease testing. The 'lexical' FIRST SET for the JSON number production is {-,0,1,..,9} .     
35
36        M1 = bitutil.ScanThru(M0, lex.Minus & M0)               # ? Optional character class [-]
37        E1 = M1 &~(lex.Zero|lex.Digit1_9)
38
39        M1a = M1 & lex.Zero                                     # Split
40        M1b = M1 & lex.Digit0_9                         
41        M2a = bitutil.Advance(M1a)
42        M2b = bitutil.Advance(M1b)
43        M3b = bitutil.ScanThru(M2b,lex.Digit0_9)
44        M4 = M2a | M3b                                          # Join
45       
46        M4a = M4 &~(lex.DecimalPoint)                           # Split
47        M4b = M4 & (lex.DecimalPoint)
48        M5b = bitutil.Advance(M4b)
49        E5b = M5b &~(lex.Digit0_9)                              # + [0-9]+
50        M6 = bitutil.ScanThru(M5b,lex.Digit0_9)
51        M7 = M4a | M6                                           # Join
52       
53        M7a = M7 &~(lex.Ee)                                     # Split
54        E7a = M7a &~(lex.NumberFollowSet)
55        M7b = M7 &(lex.Ee)
56        M8b = bitutil.Advance(M7b)
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)
61        M11 = M7a | M10b                                        # Join
62       
63        Errors = E1 | E5b | E7a | E10b
64       
65        if debug:
66                bitutil.print_aligned_streams([('Input Data', u8data), 
67                              ('M0', bitutil.bitstream2string(M0, lgth)),
68                              ('M1', bitutil.bitstream2string(M1, lgth)),
69                              ('E1', bitutil.bitstream2string(E1, lgth)),
70                              ('M1a', bitutil.bitstream2string(M1a, lgth)),
71                              ('M2a', bitutil.bitstream2string(M2a, lgth)),
72                              ('M2b', bitutil.bitstream2string(M2b, lgth)),
73                              ('M3b', bitutil.bitstream2string(M3b, lgth)),
74                              ('M4', bitutil.bitstream2string(M4, lgth)),
75                              ('M4a', bitutil.bitstream2string(M4a, lgth)),
76                              ('M4b', bitutil.bitstream2string(M4b, lgth)),
77                              ('M5b', bitutil.bitstream2string(M5b, lgth)),
78                              ('E5b', bitutil.bitstream2string(E5b, lgth)),           
79                              ('M6', bitutil.bitstream2string(M6, lgth)),
80                              ('M7', bitutil.bitstream2string(M7, lgth)),
81                              ('M7a', bitutil.bitstream2string(M7a, lgth)),
82                              ('E7a', bitutil.bitstream2string(E7a, lgth)),                                                   
83                              ('M7b', bitutil.bitstream2string(M7b, lgth)),
84                              ('M8b', bitutil.bitstream2string(M8b, lgth)),
85                              ('M9b', bitutil.bitstream2string(M9b, lgth)),           
86                              ('E9b', bitutil.bitstream2string(E9b, lgth)),           
87                              ('M10b', bitutil.bitstream2string(M10b, lgth)),                         
88                              ('M11', bitutil.bitstream2string(M11, lgth)),                                                   
89                              ('Errors', bitutil.bitstream2string(Errors, lgth))])             
90        return Errors
91
92
93def demo_validate_number(u8data):
94        r"""   
95        For example, 00 is not reported as an error case, but -- is reported as an error case.
96
97        RFC 4627 - JavaScript Object Notation (JSON) 
98        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
99
100        number = [ minus ] int [ frac ] [ exp ]
101        decimal-point = %x2E       ; .
102        digit1-9 = %x31-39         ; 1-9
103        e = %x65 / %x45            ; e E
104        exp = e [ minus / plus ] 1*DIGIT
105        frac = decimal-point 1*DIGIT
106        int = zero / ( digit1-9 *DIGIT )
107        minus = %x2D               ; -
108        plus = %x2B                ; +
109        zero = %x30                ; 0 
110        """
111        r"""
112        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
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        """
125        r"""
126        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
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        """
139        r"""
140        >>> demo_validate_number(',012345,12345,0,00,-0,-00')
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
151        <BLANKLINE>
152        """ 
153        global lgth
154        lgth = len(u8data)
155
156        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
157        (lex) = byteclass.classify_bytes(bit)
158        Errors = validate_number(lex,EOF_mask)
159
160        bitutil.print_aligned_streams([('Input Data', u8data), 
161                              ('Minus', bitutil.bitstream2string(lex.Minus, lgth)),
162                              ('Zero', bitutil.bitstream2string(lex.Zero, 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)),
168                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
169                              ('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
264if __name__ == "__main__":
265        import doctest
266        doctest.testmod()
267
268        if len(sys.argv) < 1:
269                sys.stderr.write("Usage: " + filename + "\n")
270                sys.exit(2)
271
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 TracBrowser for help on using the repository browser.