source: proto/charsetcompiler/charset_compiler.py @ 678

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

Add JSON UTF-8 definintions.

File size: 30.8 KB
Line 
1# -*- coding: utf-8 -*-
2#
3#  Character Class Compiler
4#
5#  Version 0.7 - August 14, 2009
6#     Adding generation of Python code;  parabix 2 definitions
7#  Copyright (c) 2007, Robert D. Cameron
8#  All rights reserved.
9#
10#  TO DO Notes
11#
12#  1.  Perhaps the character set definition should be extended to
13#      allow other set operations.   For example, the 'Restricted' set
14#      of XML might be defined as ['\x00-\x1f'] - ['\x09', '\x0a', '\x0d']
15#      This would require fewer operations to compute.
16#
17#  2.  The range logic generator should be modified to group
18#      bit variables the same way as the individual character logic
19#      generator (i.e., combining bits 0 and 1, 2 and 3, 4 and 5 and
20#      6 and 7 first.
21#
22#  3.  Extend for 16-bit and full Unicode character values.
23#
24#
25#--------------------------------------------------------------------------
26#
27#  Data types
28#  1. Character Set Definitions
29#  2. Boolean Expressions
30#  3. Code Generator Objects
31#
32import re, binascii, string
33
34#
35#  Character sets are defined as lists of items that
36#  are either individual characters or ranges of contiguous
37#  characters.
38#
39class CharSetDef:
40    """Definitions of character sets.   Examples:
41    CharSetDef('alpha_', ['a-z', 'A-Z', '_'])
42    CharDef('semicolon', ';') (equiv. to CharSetDef('semicolon', [';']))
43    """
44    def __init__(self, name, items, invert = False):
45        self.name = name
46        self.items = items
47        self.complemented = invert
48    def show(self): 
49        if self.complemented:
50            return "CharSetDef(%s, %s, True)" % (self.name, self.items)
51        else: return "CharSetDef(%s, %s)" % (self.name, self.items)
52
53       
54class CharDef(CharSetDef):
55    def __init__(self, name, char, invert = False):
56        self.name = name
57        self.items = [char]
58        self.complemented = invert
59    def show(self): 
60        if self.complemented:
61            return "CharDef(%s, '\\%X', True)" % (self.name, ord(self.items[0]))
62        else: return "CharDef(%s, '\\%X')" % (self.name, ord(self.items[0]))
63
64
65#
66# UTF-8 bytes occurring in the additional XML 1.1 line break
67# characters NEL and LS.
68
69UTF8_XML11_WS_bytes = [CharDef('NEL1', chr(0xC2)),
70                        CharDef('NEL2', chr(0x85)),
71                        CharDef('LS1', chr(0xE2)),
72                        CharDef('LS2', chr(0x80)),
73                        CharDef('LS3', chr(0xA8))]
74           
75DefinitionSet = {}
76
77
78
79DefinitionSet['WS_Control_10'] = [CharSetDef('control.x00_x1F', ['\x00-\x1F']),
80                                  CharDef('control.CR', '\x0D'),
81                                  CharDef('control.LF', '\x0A'),
82                                  CharDef('control.HT', '\x09'),
83                                  CharDef('control.SP', ' '),
84                                  CharSetDef('lex.WS', ['\x0D', '\x0A', '\x09', ' '])]
85
86DefinitionSet['WS_Control_10_EBCDIC'] = [CharSetDef('Control', ['\x00-\x03', '\x37',
87                                                                '\x2d-\x2f', '\x16',
88                                                                '\x0b-\x13', '\x3c-\x3d',
89                                                                '\x32', '\x26-\x27',
90                                                                '\x18-\x19', '\x3f', 
91                                                                '\x1c-\x1f']),
92                                         CharDef('CR', '\x0D'),
93                                         CharDef('LF', '\x25'),
94                                         CharDef('HT', '\x05'),
95                                         CharDef('SP', '\x40')]
96
97DefinitionSet['WS_Control_11_EBCDIC'] = [CharSetDef('Control', ['\x00-\x3f']),
98                                         CharDef('CR', '\x0D'),
99                                         CharDef('LF', '\x25'),
100                                         CharDef('HT', '\x05'),
101                                         CharDef('SP', '\x40'),
102                                         CharDef('NEL', '\x15')]
103
104
105DefinitionSet['WS_Control_11_ISO8859'] = [CharSetDef('Control', ['\x00-\x1F', '\x7F', '\x80-\x9F']),
106                                          CharDef('CR', '\x0D'),
107                                          CharDef('LF', '\x0A'),
108                                          CharDef('HT', '\x09'),
109                                          CharDef('SP', ' '),
110                                          CharDef('NEL', '\x85')]
111
112DefinitionSet['Markup'] = [CharDef('RefStart', '&'),
113                           CharDef('Semicolon', ';'),
114                           CharDef('LAngle', '<'),
115                           CharDef('RAngle', '>'),
116                           CharDef('RBracket', ']'),
117                           CharDef('Hyphen', '-'),
118                           CharDef('QMark', '?'),
119                           CharDef('Equals', "="),
120                           CharDef('SQuote', "'"),
121                           CharDef('DQuote', '"'),
122                           CharDef('Slash', '/')
123                           ]
124
125DefinitionSet['Digit_and_Hex'] = [CharSetDef('Digit', ['0-9']),
126                                  CharSetDef('Hex', ['0-9', 'A-F', 'a-f'])]
127
128DefinitionSet['Markup2'] = DefinitionSet['Markup'] + DefinitionSet['Digit_and_Hex']
129
130DefinitionSet['LexicalItems'] = [CharSetDef('MarkupStart', ['<', '&']),
131                                 CharDef('RAngle', '>'),
132                                 CharDef('RBracket', ']'),
133                                 CharDef('Hyphen', '-'),
134                                 CharDef('QMark', '?'),
135                                 CharSetDef('Quote', ['"', "'", '<', '&']),
136                                 CharSetDef('NameFollow', [';', '=', '/', '>', '?', ')', '[', '|', '?', '*', '+', ','])
137                                 ]
138DefinitionSet['LexicalItems2'] = [CharSetDef('MarkupStart', ['<', '&']),
139                                 CharDef('RAngle', '>'),
140                                 CharDef('RBracket', ']'),
141                                 CharDef('Hyphen', '-'),
142                                 CharDef('QMark', '?'),
143                                 CharSetDef('Quote', ['"', "'", '<', '&']),
144                                 CharSetDef('NameFollow', [' -,', '/', ';-?', '[-^', '{-~'])
145                                 ]
146
147
148
149DefinitionSet['Digit_and_Hex'] = [CharSetDef('lex.Digit', ['0-9']),
150                                  CharSetDef('lex.Hex', ['0-9', 'A-F', 'a-f'])]
151                                 
152DefinitionSet['LexicalItems_with_Digit'] = DefinitionSet['LexicalItems2'] + DefinitionSet['Digit_and_Hex']
153
154DefinitionSet['LI_with_MarkupPass'] = DefinitionSet['LexicalItems_with_Digit'] + [CharSetDef('AmpHashSlash', ['&', '#', '/'])]
155
156#JSON Definitino Sets
157DefinitionSet['JSON_UTF8'] =            [
158                                CharSetDef('u8.unibyte', ['\x00-\x7F']),
159                                CharSetDef('u8.prefix', ['\xC0-\xFF']),
160                                CharSetDef('u8.prefix2', ['\xC0-\xDF']),
161                                CharSetDef('u8.prefix3', ['\xE0-\xEF']),
162                                CharSetDef('u8.prefix4', ['\xF0-\xFF']),
163                                CharSetDef('u8.suffix', ['\x80-\xBF']),
164                                CharSetDef('u8.badprefix', ['\xC0-\xC1', '\xF5-\xFF']),
165                                CharDef('u8.xE0', '\xE0'),
166                                CharDef('u8.xED', '\xED'),
167                                CharDef('u8.xF0', '\xF0'),
168                                CharDef('u8.xF4', '\xF4'),
169                                CharSetDef('u8.xA0_xBF', ['\xA0-\xBF']),
170                                CharSetDef('u8.x80_x9F', ['\x80-\x9F']),
171                                CharSetDef('u8.x90_xBF', ['\x90-\xBF']),
172                                CharSetDef('u8.x80_x8F', ['\x80-\x8F']) 
173                                ]
174
175DefinitionSet['JSON_Control'] =         [
176                                #Control characters
177                                CharSetDef('ctrl.x00_x1F', ['\x00-\x1F']),
178                                CharDef('ctrl.CR', '\x0D'),
179                                CharDef('ctrl.LF', '\x0A'),
180                                CharDef('ctrl.HT', '\x09'),
181                                CharDef('ctrl.SP', ' '),
182                                ]
183
184DefinitionSet['JSON_Lexical'] =         [
185                                #Object
186                                CharDef('lex.LCurlyBrace','{'),
187                                CharDef('lex.Colon',':'),
188                                CharDef('lex.Comma',','),
189                                CharDef('lex.RCurlyBrace','}'),
190                               
191                                #Array
192                                CharDef('lex.LSquareBracket','['),
193                                CharDef('lex.RSquareBracket',']'),
194                               
195                                #Number
196                                CharDef('lex.Minus', '-'),
197                                CharDef('lex.Zero', '0'),
198                                CharSetDef('lex.Digit1_9', ['1-9']),
199                                CharSetDef('lex.Digit0_9', ['0-9']),
200                                CharDef('lex.DecimalPoint', '.'),
201                                CharSetDef('lex.Ee', ['E','e']),
202                                CharSetDef('lex.PlusMinus', ['+','-']),
203                                CharSetDef('lex.NumberFollowSet',[',','}',']']),
204                               
205                                #String
206                                CharDef('lex.DQuote','\\'),
207                                CharDef('lex.RSolidus','\\'),
208                                CharDef('lex.Solidus','\\'),
209                                CharDef('lex.b','\\'),
210                                CharDef('lex.f','\\'),
211                                CharDef('lex.n','\\'),
212                                CharDef('lex.t','\\'),
213                                CharDef('lex.u','\\'),
214                                CharSetDef('lex.HexDigit', ['0-9','a-f','A-F']),
215                               
216                                #WS
217                                CharSetDef('lex.WS', ['\x0D', '\x0A', '\x09', ' '])
218                                ]
219       
220DefinitionSet['JSON'] = DefinitionSet['JSON_UTF8'] + DefinitionSet['JSON_Control'] + DefinitionSet['JSON_Lexical'] 
221
222#
223# Following definitions for the parabix2 unbounded bitstream prototype
224#
225# First all the special characters in the XML delimiters.
226
227xml_marks =    [CharDef('lex.RefStart', '&'),
228                CharDef('lex.Semicolon', ';'),
229                CharDef('lex.LAngle', '<'),
230                CharDef('lex.RAngle', '>'),
231                CharDef('lex.LBracket', '['),
232                CharDef('lex.RBracket', ']'),
233                CharDef('lex.Exclam', '!'),
234                CharDef('lex.QMark', '?'),
235                CharDef('lex.Hyphen', '-'),
236                CharDef('lex.Equals', "="),
237                CharDef('lex.SQuote', "'"),
238                CharDef('lex.DQuote', '"'),
239                CharDef('lex.Slash', '/'),
240                CharDef('lex.Hash', '#'),
241                CharDef('lex.x', 'x'),
242                CharDef('lex.Colon', ':')
243                ]
244#
245# NameFollow: all characters that may legally follow an XML name, plus
246# any others that may not be used in names.
247# 1. All non-WS characters that may legally follow an XML name.
248namefollow = [CharSetDef('lex.NameFollow', [';', '=', '/', '>', '?', ')', '[', '|', '?', '*', '+', ','])]
249#
250# NameScan: all ASCII characters that may legally occur in a Name,
251# plus all UTF-8 prefix and suffix bytes.
252namescan = [CharSetDef('lex.NameScan', ['_', '-', '.', '0-:', 'A-Z', 'a-z', '\x80-\xFF'])]
253
254#
255namelex = [CharSetDef('lex.ASCII_name_start', ['_', ':', 'A-Z', 'a-z']),
256           CharSetDef('lex.ASCII_name_char', ['_', '-', '.', '0-:', 'A-Z', 'a-z']),
257           CharSetDef('lex.NameScan', ['_', '-', '.', '0-:', 'A-Z', 'a-z', '\x80-\xFF'])]
258
259#
260# Byte classifications in UTF-8 validation.
261UTF8_defs = [CharSetDef('u8.unibyte', ['\x00-\x7F']),
262             CharSetDef('u8.prefix', ['\xC0-\xFF']),
263             CharSetDef('u8.prefix2', ['\xC0-\xDF']),
264             CharSetDef('u8.prefix3', ['\xE0-\xEF']),
265             CharSetDef('u8.prefix4', ['\xF0-\xFF']),
266             CharSetDef('u8.suffix', ['\x80-\xBF']),
267             CharSetDef('u8.badprefix', ['\xC0-\xC1', '\xF5-\xFF']),
268             CharDef('u8.xE0', '\xE0'),
269             CharDef('u8.xED', '\xED'),
270             CharDef('u8.xF0', '\xF0'),
271             CharDef('u8.xF4', '\xF4'),
272             CharSetDef('u8.xA0_xBF', ['\xA0-\xBF']),
273             CharSetDef('u8.x80_x9F', ['\x80-\x9F']),
274             CharSetDef('u8.x90_xBF', ['\x90-\xBF']),
275             CharSetDef('u8.x80_x8F', ['\x80-\x8F'])]
276
277
278#
279UTF8_BOM_bytes = [CharDef('u8.xEF', '\xEF'), CharDef('u8.xBF', '\xBF'), CharDef('u8.xBE', '\xBE')]
280
281DefinitionSet['parabix2'] = (xml_marks + namelex + DefinitionSet['WS_Control_10']
282                             + DefinitionSet['Digit_and_Hex'] + UTF8_defs + UTF8_BOM_bytes)
283                             
284DefinitionSet['UTF8'] = UTF8_defs
285
286DefinitionSet['CSV'] = [CharDef('BackSlash', '\\'),
287                        CharDef('DQuote', '"'),
288                        CharDef('SQuote', '\''),
289                        CharDef('CR', '\x0D'),
290                        CharDef('LF', '\x0A'),
291                        CharDef('Comma', ','),
292                        CharDef('HT', '\x09'),
293                        CharDef('Period', '.')]
294
295
296#
297# Symbolic Representations of Boolean Expressions
298#
299
300class BoolExpr:
301   """The BoolExpr class and its subclasses provide a symbolic
302      representation of Boolean expressions.
303   """
304   pass
305
306class Var(BoolExpr):
307    def __init__(self, varname):
308        self.varname = varname
309    def show(self): return 'Var("' + self.varname + '")'
310
311class TrueLiteral(BoolExpr):
312    def __init__(self):
313        self.value = True
314    def show(self): return 'T'
315
316class FalseLiteral(BoolExpr):
317    def __init__(self):
318        self.value = False
319    def show(self): return 'F'
320
321class Not(BoolExpr):
322    def __init__(self, expr):
323        self.operand = expr
324    def show(self): return 'Not(%s)' % (self.operand.show())
325
326class And(BoolExpr):
327    def __init__(self, expr1, expr2):
328        self.operand1 = expr1
329        self.operand2 = expr2
330    def show(self): return 'And(%s, %s)' % (self.operand1.show(), self.operand2.show())
331
332class Or(BoolExpr):
333    def __init__(self, expr1, expr2):
334        self.operand1 = expr1
335        self.operand2 = expr2
336    def show(self): return 'Or(%s, %s)' % (self.operand1.show(), self.operand2.show())
337
338class Xor(BoolExpr):
339    def __init__(self, expr1, expr2):
340        self.operand1 = expr1
341        self.operand2 = expr2
342    def show(self): return 'Xor(%s, %s)' % (self.operand1.show(), self.operand2.show())
343
344class Sel(BoolExpr):
345    def __init__(self, expr1, expr2, expr3):
346        self.sel = expr1
347        self.true_branch = expr2
348        self.false_branch = expr3
349    def show(self): return 'Sel(%s, %s, %s)' % (self.sel.show(), self.true_branch.show(), self.false_branch.show())
350
351
352#
353# Optimizing Constructors for Boolean Expressions
354# - Maintaining Assembler Instruction Form:
355#   - All boolean algebraic rules involving true/false applied.
356#   - Negations restricted:
357#       - no negations within or (DeMorgan's to nand)
358#       - at most one negation within and
359#
360
361def make_not(expr):
362    if isinstance(expr, TrueLiteral):
363        return FalseLiteral()
364    elif isinstance(expr, FalseLiteral):
365        return TrueLiteral()
366    elif isinstance(expr, Not):
367        return expr.operand
368    else: return Not(expr)
369
370def make_and(expr1, expr2):
371    if isinstance(expr1, TrueLiteral):
372        return expr2
373    elif isinstance(expr2, TrueLiteral):
374        return expr1
375    elif isinstance(expr1, FalseLiteral):
376        return FalseLiteral()
377    elif isinstance(expr2, FalseLiteral):
378        return FalseLiteral()
379    elif equal_exprs(expr1, expr2): return expr1
380    elif isinstance(expr1, Not):
381        if isinstance(expr2, Not):
382            return make_not(make_or(expr1.operand, expr2.operand))
383        elif equal_exprs(expr1.operand, expr2): return FalseLiteral()
384        else: return And(expr1, expr2)
385    elif isinstance(expr2, Not):
386        if equal_exprs(expr1, expr2.operand): return FalseLiteral()
387        else: return And(expr1, expr2)
388    else: return And(expr1, expr2)
389
390def make_or(expr1, expr2):
391    if isinstance(expr1, FalseLiteral):
392        return expr2
393    elif isinstance(expr2, FalseLiteral):
394        return expr1
395    elif isinstance(expr1, TrueLiteral):
396        return TrueLiteral()
397    elif isinstance(expr2, TrueLiteral):
398        return TrueLiteral()
399    elif isinstance(expr1, Not):
400        return make_not(make_and(expr1.operand, make_not(expr2)))
401    elif isinstance(expr2, Not):
402        return make_not(make_and(make_not(expr1), expr2.operand))
403    elif equal_exprs(expr1, expr2): return expr1
404    elif isinstance(expr1, And) and isinstance(expr2, And):
405        # These optimizations factor out common components that
406        # can occur when sets are formed by union (e.g., union of
407        # [a-z] and [A-Z].
408        if equal_exprs(expr1.operand1, expr2.operand1):
409            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand2))
410        elif equal_exprs(expr1.operand2, expr2.operand2):
411            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand1))
412        elif equal_exprs(expr1.operand1, expr2.operand2):
413            return make_and(expr1.operand1, make_or(expr1.operand2, expr2.operand1))
414        elif equal_exprs(expr1.operand2, expr2.operand1):
415            return make_and(expr1.operand2, make_or(expr1.operand1, expr2.operand2))
416        else: return Or(expr1, expr2)
417    else: return Or(expr1, expr2)
418
419def make_sel(if_expr, T_expr, F_expr):
420    if isinstance(if_expr, TrueLiteral):
421        return T_expr
422    elif isinstance(if_expr, FalseLiteral):
423        return F_expr
424    elif isinstance(T_expr, TrueLiteral):
425        # if x then T else y = x or y
426        return make_or(if_expr, F_expr) 
427    elif isinstance(T_expr, FalseLiteral):
428        # if x then F else y = not(x) and y
429        return make_and(make_not(if_expr), F_expr) 
430    elif isinstance(F_expr, FalseLiteral):
431        # if x then y else F = x and y
432        return make_and(if_expr, T_expr) 
433    elif isinstance(F_expr, TrueLiteral):
434        # if x then y else T = not(x) or y
435        return make_or(make_not(if_expr), T_expr)
436    elif equal_exprs(T_expr, F_expr):
437        return T_expr
438    else: return Sel(if_expr, T_expr, F_expr)
439
440
441def make_xor(expr1, expr2):
442    if isinstance(expr1, FalseLiteral):
443        return expr2
444    elif isinstance(expr1, FalseLiteral):
445        return expr1
446    elif isinstance(expr1, TrueLiteral):
447        return make_not(expr2)
448    elif isinstance(expr2, TrueLiteral):
449        return make_not(expr1)
450    elif isinstance(expr1, Not) and isinstance(expr2, Not):
451        return make_xor(expr1.operand, expr2.operand)
452    else: return Xor(expr1, expr2)
453
454def equal_exprs(e1, e2):
455    if isinstance(e1, FalseLiteral): return isinstance(e2, FalseLiteral)
456    elif isinstance(e1, TrueLiteral): return isinstance(e2, TrueLiteral)
457    elif isinstance(e1, Var) and isinstance(e2, Var):
458        return e1.varname == e2.varname
459    elif isinstance(e1, Not) and isinstance(e2, Not):
460        return equal_exprs(e1.operand, e2.operand)
461    elif isinstance(e1, And) and isinstance(e2, And):
462        if equal_exprs(e1.operand1, e2.operand1):
463            return equal_exprs(e1.operand2, e2.operand2)
464        elif equal_exprs(e1.operand1, e2.operand2):
465            return equal_exprs(e1.operand2, e2.operand1)
466        else: return False
467    elif isinstance(e1, Or) and isinstance(e2, Or):
468        if equal_exprs(e1.operand1, e2.operand1):
469            return equal_exprs(e1.operand2, e2.operand2)
470        elif equal_exprs(e1.operand1, e2.operand2):
471            return equal_exprs(e1.operand2, e2.operand1)
472        else: return False
473    elif isinstance(e1, Xor) and isinstance(e2, Xor):
474        if equal_exprs(e1.operand1, e2.operand1):
475            return equal_exprs(e1.operand2, e2.operand2)
476        elif equal_exprs(e1.operand1, e2.operand2):
477            return equal_exprs(e1.operand2, e2.operand1)
478        else: return False
479    elif isinstance(e1, Sel) and isinstance(e2, Sel):
480        if equal_exprs(e1.sel, e2.sel):
481             if equal_exprs(e1.true_branch, e2.true_branch):
482                 return equal_exprs(e1.false_branch, e2.false_branch)
483             else: return False
484        else: return False
485
486
487#
488#
489#  Boolean Expressions for Character Class Definitions
490#
491
492def bit_var(n):
493    return 'bit[%i]' % n
494def make_bitv(n):
495    return Var(bit_var(n))
496
497# Deprecated
498def make_2bit_test(var1, var2, bit_pattern):
499  if bit_pattern == 0: 
500    return make_not(make_or(var1, var2))
501  elif bit_pattern == 1:
502    return make_and(make_not(var1), var2)
503  elif bit_pattern == 2:
504    return make_and(var1, make_not(var2))
505  else: return make_and(var1, var2)
506
507# Deprecated
508def make_8bit_test(bit_pattern):
509  return make_and(make_and(make_2bit_test(make_bitv(0), make_bitv(1), (bit_pattern >> 6) & 3),
510                           make_2bit_test(make_bitv(2), make_bitv(3), (bit_pattern >> 4) & 3)),
511                  make_and(make_2bit_test(make_bitv(4), make_bitv(5), (bit_pattern >> 2) & 3),
512                           make_2bit_test(make_bitv(6), make_bitv(7), (bit_pattern) & 3)))
513
514
515def make_bit_test(pattern, bit_count):
516    bit_terms = []
517    test_bit = 2**(bit_count - 1)
518    for i in range(0, bit_count):
519        if (pattern & test_bit) == 0:
520            bit_terms.append(make_not(make_bitv(i)))
521        else: bit_terms.append(make_bitv(i))
522        test_bit >>= 1
523    while len(bit_terms) > 1:
524        new_terms = []
525        for i in range(0, len(bit_terms)/ 2):
526            new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
527        if len(bit_terms) % 2 == 1:
528            new_terms.append(bit_terms[-1])
529        bit_terms = new_terms
530    return bit_terms[0]
531
532
533def char_test_expr(ch):
534    return make_bit_test(ord(ch), 8)
535    #return make_8bit_test(ord(ch))
536
537def GE_Range(N, n):
538    if N == 0: return TrueLiteral()
539    elif N % 2 == 0 and (n >> (N - 2)) == 0:
540        return make_or(make_or(make_bitv(8-N), make_bitv(9-N)),
541                        GE_Range(N - 2, n))
542    elif N % 2 == 0 and (n >> (N - 2)) == 3:   # >= 11xxxx
543        return make_and(make_and(make_bitv(8-N), make_bitv(9-N)),
544                        GE_Range(N - 2, n - (3 << (N-2))))
545    elif N >= 1:
546        hi_bit = n & (1 << (N-1))
547        lo_bits = n - hi_bit
548        lo_range = GE_Range(N-1, lo_bits)
549        if hi_bit == 0:
550            # If the hi_bit of n is not set, then whenever the corresponding bit
551            # is set in the target, the target will certainly be >=.  Otherwise,
552            # the value of GE_range(N-1, lo_bits) is required.
553            return make_or(make_bitv(8-N), lo_range)
554        else: 
555            # If the hi_bit of n is set, then the corresponding bit must be set
556            # in the target for >= and GE_range(N-1, lo_bits) must also be true.
557            return make_and(make_bitv(8-N), lo_range)
558
559def LE_Range(N, n):
560    # If an N-bit pattern is all ones, then it is always
561    # true that any n-bit value is LE this pattern.
562    # Handling this as a special case avoids an overflow
563    # issue with n+1 requiring more than N bits.
564    if n+1 == 2 ** N:
565        return TrueLiteral()
566    else:
567        return make_not(GE_Range(N, n+1))
568
569BadRange = Exception()
570
571
572def Make_Range(n1, n2):  # require n2 >= n1
573    diff_bits = n1 ^ n2
574    diff_count = 0
575    while diff_bits > 0:
576        diff_count += 1
577        diff_bits >>= 1
578    if n2 < n1 or diff_count > 8: raise BadRange()
579    common = make_bit_test(n1 >> diff_count, 8 - diff_count)
580    if diff_count == 0: return common
581    mask = 2**(diff_count-1) - 1
582    lo_test = GE_Range(diff_count-1, n1 & mask)
583    hi_test = LE_Range(diff_count-1, n2 & mask)
584    return make_and(common, make_sel(make_bitv(8-diff_count), hi_test, lo_test))
585
586# Deprecated   
587def Inclusive_Range(N, n1, n2):  # require n2 >= n1
588    if N == 0: return TrueLiteral()
589    elif n1 >= 2**(N-1):
590        return make_and(make_bitv(8-N), Inclusive_Range(N-1, n1 - 2**(N-1), n2 - 2**(N-1)))
591    elif n2 < 2**(N-1):
592        return make_and(make_not(make_bitv(8-N)), Inclusive_Range(N-1, n1, n2))
593    else:
594        n2_lo = n2 - 2**(N-1)
595        lo_test = GE_Range(N-1, n1)
596        hi_test = LE_Range(N-1, n2_lo)
597        # special optimization?
598        # if n2_lo + 1 == n1: return make_xor(make_bit_test(8-N), lo_test)
599        return make_sel(make_bitv(8-N), lo_test, hi_test)
600
601
602
603
604BadCharSetItem = Exception()
605
606def char_or_range_expr(charset_item):
607    if len(charset_item) == 1:
608        return char_test_expr(charset_item[0])
609    elif len(charset_item) == 3:
610        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
611             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
612             #  return Inclusive_Range(8, ord(charset_item[0]), ord(charset_item[2]))
613    print charset_item
614    raise BadCharSetItem
615
616def charset_expr(chardef):
617    e1 = char_or_range_expr(chardef.items[0])
618    for i in range(1, len(chardef.items)):
619        e1 = make_or(e1, char_or_range_expr(chardef.items[i]))
620    if chardef.complemented: return make_not(e1)
621    else: return e1
622
623
624
625#
626#
627#  Code Generation
628#
629class CodeGenObject:
630    def __init__(self, predeclared, typedecl='BitBlock '):
631        self.gensym_template = 'temp%i'
632        self.gensym_counter = 0
633        self.generated_code = []
634        self.common_expression_map = {}
635        for sym in predeclared: self.common_expression_map[sym] = sym
636        self.typedecl = typedecl
637    def add_assignment(self, varname, expr):
638        self.common_expression_map[expr] = varname
639        self.generated_code.append(%s%s = %s;\n' % (self.typedecl, varname, expr))
640    def expr_string_to_variable(self, expr_string):
641        if self.common_expression_map.has_key(expr_string): 
642            return self.common_expression_map[expr_string]
643        else:
644            self.gensym_counter += 1
645            sym = self.gensym_template % self.gensym_counter
646            self.add_assignment(sym, expr_string)
647            return sym
648    def showcode(self):
649        s = ''
650        for stmt in self.generated_code: s += stmt
651        return s
652
653
654
655def expr2simd(genobj, expr):
656    """Translate a Boolean expression into three-address Altivec code
657       using code generator object genobj.
658    """
659    if isinstance(expr, TrueLiteral): return 'simd_const_1(1)'
660    elif isinstance(expr, FalseLiteral): return 'simd_const_1(0)'
661    elif isinstance(expr, Var): return expr.varname
662    elif isinstance(expr, Not):
663       e = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand))
664       return 'simd_andc(simd_const_1(1), %s)' % (e)
665    elif isinstance(expr, Or):
666       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
667       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
668       return 'simd_or(%s, %s)' % (e1, e2)
669    elif isinstance(expr, Xor):
670       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
671       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
672       return 'simd_xor(%s, %s)' % (e1, e2)
673    elif isinstance(expr, And):
674       if isinstance(expr.operand1, Not):
675           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1.operand))
676           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
677           return 'simd_andc(%s, %s)' % (e2, e1)
678       elif isinstance(expr.operand2, Not):
679           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
680           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand))
681           return 'simd_andc(%s, %s)' % (e1, e2)
682       else:
683           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
684           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
685           return 'simd_and(%s, %s)' % (e1, e2)
686    elif isinstance(expr, Sel):
687       sel = genobj.expr_string_to_variable(expr2simd(genobj, expr.sel))
688       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.true_branch))
689       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.false_branch))
690       return 'simd_if(%s, %s, %s)' %(sel, e1, e2)
691
692def chardef2simd(genobj, chardef):
693    genobj.add_assignment(chardef.name, expr2simd(genobj, charset_expr(chardef)))
694
695def chardeflist2simd(chardeflist):
696    cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
697    for d in chardeflist:
698        chardef2simd(cgo, d)
699    return cgo.showcode()
700
701
702
703def expr2py(genobj, expr):
704    """Translate a Boolean expression into three-address python code
705       using code generator object genobj.
706    """
707    if isinstance(expr, TrueLiteral): return '-1'
708    elif isinstance(expr, FalseLiteral): return '0'
709    elif isinstance(expr, Var): return expr.varname
710    elif isinstance(expr, Not):
711       e = genobj.expr_string_to_variable(expr2py(genobj, expr.operand))
712       return '(~%s)' % (e)
713    elif isinstance(expr, Or):
714       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
715       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
716       return '(%s | %s)' % (e1, e2)
717    elif isinstance(expr, Xor):
718       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
719       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
720       return '(%s ^ %s)' % (e1, e2)
721    elif isinstance(expr, And):
722       if isinstance(expr.operand1, Not):
723           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1.operand))
724           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
725           return '(%s &~ %s)' % (e2, e1)
726       elif isinstance(expr.operand2, Not):
727           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
728           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2.operand))
729           return '(%s &~ %s)' % (e1, e2)
730       else:
731           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
732           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
733           return '(%s & %s)' % (e1, e2)
734    elif isinstance(expr, Sel):
735       sel = genobj.expr_string_to_variable(expr2py(genobj, expr.sel))
736       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.true_branch))
737       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.false_branch))
738       return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
739
740def chardef2py(genobj, chardef):
741    genobj.add_assignment(chardef.name, expr2py(genobj, charset_expr(chardef)))
742
743
744def py_chardefmap(chardeflist):
745    defs = ["'%s' : %s" % (d.name,d.name) for d in chardeflist]
746    return  '{%s}' % string.join(defs, ',\n\t')
747
748def chardeflist2py(chardeflist):
749    cgo = CodeGenObject([bit_var(i) for i in range(0,8)],'')
750    for d in chardeflist:
751        chardef2py(cgo, d) 
752    return cgo.showcode()# + "  return "+ py_chardefmap(chardeflist) + "\n"
753
754
755def code_gen_for_transcode(transcode_tbl_h, transcode_tbl_l):
756  cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
757  xor_tbl_l = [transcode_tbl_l[code] ^ code for code in range(256)]
758  code_gen_for_transcode_8bit(cgo, "x16h", transcode_tbl_h)
759  code_gen_for_transcode_8bit(cgo, "x16l", xor_tbl_l)
760  return cgo.showcode()
761
762def code_gen_for_transcode_8bit(cgo, pfx, tbl):
763  for bit in range(8):
764    bit_mask = 256 >> bit
765    in_run = False
766    first_expr_found = False
767    bit_expr = FalseLiteral()
768    for code in range(256):
769      if tbl[code] & bit_mask != 0:
770        if not in_run:
771          in_run = True
772          run_start = code
773      else:
774        if in_run:
775          if run_start == code-1:
776            e1 = char_test_expr(chr(code - 1))
777          else:
778            e1 = Make_Range(run_start, code - 1)
779          if first_expr_found:
780            bit_expr = make_or(bit_expr, e1)
781          else:
782            first_expr_found = True
783            bit_expr = e1
784    if first_expr_found:
785      cgo.add_assignment("%s[%i]" % (pfx, bit), expr2simd(cgo, bit_expr))
786
787# Work with tables from
788# /home/cameron/glibc-2.3.5/localedata/charmaps/
789
790charmap_line_RE = re.compile("<U([0-9A-F][0-9A-F])([0-9A-Z][0-9A-Z])>\s+/x([0-9a-f][0-9a-f])\s")
791
792def read_char_map(file):
793  f = open(file)
794  lines = f.readlines()
795  matches = [charmap_line_RE.match(l) for l in lines]
796  u16hi = [ord(binascii.unhexlify(m.group(1))) for m in matches if m]
797  u16lo = [ord(binascii.unhexlify(m.group(2))) for m in matches if m]
798  codes = [ord(binascii.unhexlify(m.group(3))) for m in matches if m]
799  codes_OK = [c for c in range(256) if codes[c] == c]
800  if len(codes_OK) != 256:
801    print("Code map failure reading %s" % file)
802  return (u16hi, u16lo)
803
804import codecs
805def ascii2ebcdic_chardeflist(defs):
806        encoder = codecs.getencoder('cp037')
807        return [xlate_chardef(d, encoder) for d in defs]
808
809def xlate_char_or_range(charset_item, encoder):
810    if len(charset_item) == 1:
811        return encoder(charset_item[0])
812    elif len(charset_item) == 3:
813        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
814             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
815             #  return Inclusive_Range(8, ord(charset_item[0]), ord(charset_item[2]))
816    print charset_item
817    raise BadCharSetItem
818       
819def xlate_chardef(chardef, encoder):
820  if isinstance(chardef, CharDef):
821    return CharDef(chardef.name, encoder(chardef.items[0])[0], chardef.complemented)
822  else:
823    cdefs = []
824    for item in chardef.items:
825        if len(item) == 1: cdefs.append(encoder(item)[0])
826        elif len(item) == 3:
827          for v in range(ord(item[0]), ord(item[-1])+1):
828            cdefs.append(encoder(chr(v))[0])
829        else: raise BadCharSetItem
830    return CharSetDef(chardef.name, cdefs, chardef.complemented)
831
832import charset_input_parser
833def input_chardef(filename):
834    """
835    Returns a list of declared CharSet from the declarations in the input file
836    """
837    defs = []
838    charset_declaration_list = charset_input_parser.processCharsetInput(filename)
839   
840    for charset_declaration in charset_declaration_list:
841        defs.append(CharSetDef (charset_declaration[0], charset_declaration[1]))
842
843    return defs
844                                 
845import sys
846def main():
847    if len(sys.argv) == 2:
848        # if the specified argument is not in the DefinitionSet, then assume that it's a filename
849        if sys.argv[1] not in DefinitionSet:
850            #define the characters in the list
851            defs = input_chardef(sys.argv[1])
852            #print chardeflist2simd(defs)
853            print chardeflist2py(defs)
854        else:
855            #print chardeflist2simd(DefinitionSet[sys.argv[1]])
856            print chardeflist2py(DefinitionSet[sys.argv[1]])
857    elif len(sys.argv) == 3 and sys.argv[2] == 'EBCDIC':
858        defs = ascii2ebcdic_chardeflist(DefinitionSet[sys.argv[1]])
859        print chardeflist2simd(defs)
860    else:
861        print "Usage python charset_compiler.py <name> [EBCDIC]"
862        for k in DefinitionSet.keys(): print k
863
864if __name__ == "__main__": main()
Note: See TracBrowser for help on using the repository browser.