source: proto/JSON/json_prototype.py @ 682

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

Add UTF8 validation. Add UTF8 character set definitions.

File size: 11.1 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 u8u16
20import math
21import sys
22
23debug = False
24filename = "json_prototype.py"
25
26# Globals
27#
28# Bitstream function defs input/output *only* bitstream type variables.
29# Global declarations allow debug blocks in bitstream defs. Do not shadow variables.
30u8data = ""
31lgth = 0
32
33def validate_number(lex, EOF_mask):
34        Errors = 0     
35        M0 = 0                                                  # Assume the cursor is at the first Minus, Zero, or Digit_1_9 character
36        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} .     
37
38        M1 = bitutil.ScanThru(M0, lex.Minus & M0)               # ? Optional character class [-]
39        E1 = M1 &~(lex.Zero|lex.Digit1_9)
40
41        M1a = M1 & lex.Zero                                     # Split
42        M1b = M1 & lex.Digit0_9                         
43        M2a = bitutil.Advance(M1a)
44        M2b = bitutil.Advance(M1b)
45        M3b = bitutil.ScanThru(M2b,lex.Digit0_9)
46        M4 = M2a | M3b                                          # Join
47       
48        M4a = M4 &~(lex.DecimalPoint)                           # Split
49        M4b = M4 & (lex.DecimalPoint)
50        M5b = bitutil.Advance(M4b)
51        E5b = M5b &~(lex.Digit0_9)                              # + [0-9]+
52        M6 = bitutil.ScanThru(M5b,lex.Digit0_9)
53        M7 = M4a | M6                                           # Join
54       
55        M7a = M7 &~(lex.Ee)                                     # Split
56        E7a = M7a &~(lex.NumberFollowSet)
57        M7b = M7 &(lex.Ee)
58        M8b = bitutil.Advance(M7b)
59        M9b = bitutil.ScanThru(M8b, lex.PlusMinus & M8b)        # ? Optional character class [+-]               
60        E9b  = M9b &~(lex.Digit0_9)                             # + [0-9]+
61        M10b = bitutil.ScanThru(M9b,lex.Digit0_9)
62        E10b = M10b &~(lex.NumberFollowSet)
63        M11 = M7a | M10b                                        # Join
64       
65        Errors = E1 | E5b | E7a | E10b
66       
67        if debug:
68                bitutil.print_aligned_streams([('Input Data', u8data), 
69                              ('M0', bitutil.bitstream2string(M0, lgth)),
70                              ('M1', bitutil.bitstream2string(M1, lgth)),
71                              ('E1', bitutil.bitstream2string(E1, lgth)),
72                              ('M1a', bitutil.bitstream2string(M1a, lgth)),
73                              ('M2a', bitutil.bitstream2string(M2a, lgth)),
74                              ('M2b', bitutil.bitstream2string(M2b, lgth)),
75                              ('M3b', bitutil.bitstream2string(M3b, lgth)),
76                              ('M4', bitutil.bitstream2string(M4, lgth)),
77                              ('M4a', bitutil.bitstream2string(M4a, lgth)),
78                              ('M4b', bitutil.bitstream2string(M4b, lgth)),
79                              ('M5b', bitutil.bitstream2string(M5b, lgth)),
80                              ('E5b', bitutil.bitstream2string(E5b, lgth)),           
81                              ('M6', bitutil.bitstream2string(M6, lgth)),
82                              ('M7', bitutil.bitstream2string(M7, lgth)),
83                              ('M7a', bitutil.bitstream2string(M7a, lgth)),
84                              ('E7a', bitutil.bitstream2string(E7a, lgth)),                                                   
85                              ('M7b', bitutil.bitstream2string(M7b, lgth)),
86                              ('M8b', bitutil.bitstream2string(M8b, lgth)),
87                              ('M9b', bitutil.bitstream2string(M9b, lgth)),           
88                              ('E9b', bitutil.bitstream2string(E9b, lgth)),           
89                              ('M10b', bitutil.bitstream2string(M10b, lgth)),                         
90                              ('M11', bitutil.bitstream2string(M11, lgth)),                                                   
91                              ('Errors', bitutil.bitstream2string(Errors, lgth))])             
92        return Errors
93
94
95def demo_validate_number(u8data):
96        r"""   
97        For example, 00 is not reported as an error case, but -- is reported as an error case.
98
99        RFC 4627 - JavaScript Object Notation (JSON) 
100        RFC 5234 - Augmented BNF for Syntax Specifications: ABNF
101
102        number = [ minus ] int [ frac ] [ exp ]
103        decimal-point = %x2E       ; .
104        digit1-9 = %x31-39         ; 1-9
105        e = %x65 / %x45            ; e E
106        exp = e [ minus / plus ] 1*DIGIT
107        frac = decimal-point 1*DIGIT
108        int = zero / ( digit1-9 *DIGIT )
109        minus = %x2D               ; -
110        plus = %x2B                ; +
111        zero = %x30                ; 0 
112        """
113        r"""
114        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
115        Input Data  : ,-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,
116        Minus       : _1_11_1_____1___1___1____1_______1_______1_________________________
117        Zero        : _________11__11__1___1____1___11___________1______1__1__1__________
118        Digit1_9    : __________________________________111_111____111____1____111111111_
119        Digit0_9    : _________11__11__1___1____1___11__111_111__1_111__1_11__1111111111_
120        DecimalPoint: __________________1___1____1_________1______1______________________
121        Ee          : _______________________1____1______________________1_______________
122        PlusMinus   : _1_11_1_____1___1___1____1_______1_______1______1_____1____________
123        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111_
124        Errors      : __1_1__1__1___1____1___1____1__1_________1______1_____1__1_________
125        <BLANKLINE>
126        """
127        r"""
128        >>> demo_validate_number(',-,--,-a,00,-00,-0.,-0.e,-0.E,00,-123.456-,0.456+,0e10+,0123456789,')
129        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,
130        Minus       : _________________________________1_______________1______________1________________________1__________________________________
131        Zero        : _1_______________1_______1____________11____11____11__________1____________1_1_________________________1_____________1______
132        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_
133        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_
134        DecimalPoint: __1____1____1_____________1__________________________________________1________1_______________1_____________________________
135        Ee          : ______________________1_____1___1____1____1_____1_______________________________________1_______________1_______________1___
136        PlusMinus   : _________________________________1_________1_____1______________1________________________1_______________1__________________
137        EOF_Mask    : 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111_
138        Errors      : ____________________________________________________________________________________________________________________________
139        <BLANKLINE>
140        """
141        r"""
142        >>> demo_validate_number(',012345,12345,0,00,-0,-00')
143        Input Data  : ,012345,12345,0,00,-0,-00
144        Minus       : ___________________1__1__
145        Zero        : _1____________1_11__1__11
146        Digit1_9    : __11111_11111____________
147        Digit0_9    : __11111_11111____________
148        DecimalPoint: _________________________
149        Ee          : _________________________
150        PlusMinus   : ___________________1__1__
151        EOF_Mask    : 1111111111111111111111111_
152        Errors      : __1______________1______1
153        <BLANKLINE>
154        """ 
155        global lgth
156        lgth = len(u8data)
157
158        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
159        (u8, lex, ctrl) = byteclass.classify_bytes(bit)
160        Errors = validate_number(lex,EOF_mask)
161
162        bitutil.print_aligned_streams([('Input Data', u8data), 
163                              ('Minus', bitutil.bitstream2string(lex.Minus, lgth)),
164                              ('Zero', bitutil.bitstream2string(lex.Zero, lgth)),
165                              ('Digit1_9', bitutil.bitstream2string(lex.Digit1_9, lgth)),
166                              ('Digit0_9', bitutil.bitstream2string(lex.Digit0_9, lgth)),
167                              ('DecimalPoint', bitutil.bitstream2string(lex.DecimalPoint, lgth)),
168                              ('Ee', bitutil.bitstream2string(lex.Ee, lgth)),
169                              ('PlusMinus', bitutil.bitstream2string(lex.PlusMinus, lgth)),
170                              ('EOF_Mask', bitutil.bitstream2string(EOF_mask, lgth+1)),
171                              ('Errors', bitutil.bitstream2string(Errors, lgth))])
172
173def 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       
180def 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       
198def 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
206        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
212def 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
241def 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))])
264        return
265
266def parse_json(u8data):
267 
268        # Transpose to parallel bit streams and prepare an EOF mask.
269        (bit, EOF_mask) = bitutil.transpose_streams(u8data)
270
271        # Classify bytes for UTF-8 processing, whitespace, control and JSON lexical analysis.
272        (u8, control, lex) = byteclass.classify_bytes(bit)
273
274        # Validate UTF-8 multibyte sequences and determine the UTF-8 scope streams.
275        u8 = u8u16.validate_utf8(u8) 
276 
277        return
278 
279def demo_parse_json(u8data):
280 
281        global lgth
282        lgth = len(u8data)
283       
284        parse_json(u8data)
285 
286        return
287
288if __name__ == "__main__":
289        import doctest
290        doctest.testmod()
291
292        if len(sys.argv) < 1:
293                sys.stderr.write("Usage: " + filename + "\n")
294                sys.exit(2)
295
296        u8data = bitutil.readfile(sys.argv[1]) 
297#       demo_validate_number(u8data)
298#       demo_parse_escape(u8data)
299#       demo_parallel_prefix_parity(u8data)
300#       demo_parse_json(u8data)
Note: See TracBrowser for help on using the repository browser.