source: proto/charsetcompiler/charset_compiler2.py @ 3944

Last change on this file since 3944 was 3942, checked in by cameron, 5 years ago

Refactor pulling out bitwise_expr module; prepare toAst method

File size: 15.9 KB
Line 
1#
2#  Character Class Compiler
3#
4#  Version 0.8 - Feb. 17, 2012
5#     Add command-line option for specifying basis_pattern
6#  Copyright (c) 2007-12, Robert D. Cameron
7#  All rights reserved.
8#
9#  TO DO Notes
10#
11#  1.  Perhaps the character set definition should be extended to
12#      allow other set operations.   For example, the 'Restricted' set
13#      of XML might be defined as ['\x00-\x1f'] - ['\x09', '\x0a', '\x0d']
14#      This would require fewer operations to compute.
15#
16#  2.  The range logic generator should be modified to group
17#      bit variables the same way as the individual character logic
18#      generator (i.e., combining bits 0 and 1, 2 and 3, 4 and 5 and
19#      6 and 7 first.
20#
21#  3.  Extend for 16-bit and full Unicode character values.
22#
23#
24#--------------------------------------------------------------------------
25#
26#  Data types
27#  1. Character Set Definitions
28#  2. Boolean Expressions
29#  3. Code Generator Objects
30#
31import sys, optparse
32import re, binascii, string
33import EBCDIC
34
35import charset_def
36CharDef = charset_def.CharDef
37CharSetDef = charset_def.CharSetDef
38
39import charsets
40DefinitionSet = charsets.DefinitionSet
41
42import charset_input_parser
43
44from bitwise_expr import *
45
46def bit_var(n):
47    global options
48#    return 'bit[%i]' % n
49    return options.basis_pattern % n
50
51def make_bitv(n):
52    return Var(bit_var(7-n))
53
54
55def bit_pattern_expr(pattern, selected_bits):
56    if selected_bits == 0: return TrueLiteral()
57    bit_terms = []
58    bit_no = 0
59    while selected_bits:
60      test_bit = 1 << bit_no
61      if selected_bits & test_bit:
62        if (pattern & test_bit) == 0:
63            bit_terms = [make_not(make_bitv(bit_no))] + bit_terms
64        else: bit_terms = [make_bitv(bit_no)] + bit_terms
65      else: bit_terms = [TrueLiteral()] + bit_terms
66      # Appending TrueLiteral() for nonselected bits is intended
67      # to keep consistent grouping of variables in the next loop.
68      selected_bits &= ~test_bit
69      bit_no += 1
70    while len(bit_terms) > 1:
71        new_terms = []
72        for i in range(0, len(bit_terms)/ 2):
73            new_terms.append(make_and(bit_terms[2*i], bit_terms[2*i+1]))
74        if len(bit_terms) % 2 == 1:
75            new_terms.append(bit_terms[-1])
76        bit_terms = new_terms
77    return bit_terms[0]
78   
79
80def char_test_expr(ch):
81    #return make_bit_test(ord(ch), 8)
82    return bit_pattern_expr(ord(ch), 0xFF)
83
84
85BadRange = Exception()
86
87BadCharSetItem = Exception()
88
89def char_or_range_expr(charset_item):
90    if len(charset_item) == 1:
91        return char_test_expr(charset_item[0])
92    elif len(charset_item) == 3:
93        if charset_item[1] == '-' and ord(charset_item[0]) <= ord(charset_item[2]):
94             return Make_Range(ord(charset_item[0]), ord(charset_item[2]))
95    print charset_item
96    raise BadCharSetItem
97
98def charset_expr(chardef):
99    if chardef.items == []: return FalseLiteral()
100    e1 = char_or_range_expr(chardef.items[0])
101    for i in range(1, len(chardef.items)):
102        e1 = make_or(e1, char_or_range_expr(chardef.items[i]))
103    if chardef.complemented: return make_not(e1)
104    else: return e1
105
106
107def count_leading_zeroes(strm):
108        zeroes = 0
109        while (strm & 0xFFFFFFFF) == 0: 
110                zeroes += 32
111                strm >>= 32
112        while (strm & 1) == 0:
113                zeroes += 1
114                strm >>= 1
115        return zeroes
116
117def popcount(strm): 
118        pop = 0
119        while strm > 0: 
120                p1 = (strm & 0x5555555555555555) + ((strm >> 1) & 0x5555555555555555)
121                p1 = (p1 & 0x3333333333333333) + ((p1 >> 2) & 0x3333333333333333)
122                p1 = (p1 & 0x0F0F0F0F0F0F0F0F) + ((p1 >> 4) & 0x0F0F0F0F0F0F0F0F)
123                p1 = (p1 & 0x00FF00FF00FF00FF) + ((p1 >> 8) & 0x00FF00FF00FF00FF)
124                p1 = (p1 & 0x0000FFFF0000FFFF) + ((p1 >> 16) & 0x0000FFFF0000FFFF)
125                pop += (p1 & 0x00000000FFFFFFFF) + ((p1 >> 32) & 0x00000000FFFFFFFF)
126                strm >>= 64
127        return pop
128
129#
130# New charset processing using a bitset representation
131#
132def cset_universe(N):
133  return (1<<(1<<N)) - 1
134
135def cset_intersect(s1, s2): 
136  return s1 & s2
137
138def cset_union(s1, s2):
139  return s1 | s2
140
141def cset_isempty(s):
142  return s == 0
143
144# precondition not cset_isempty(s)
145def cset_min(s):
146  return count_leading_zeroes(s)
147
148# precondition not cset_isempty(s)
149def cset_max(s):
150  s1 = s & (s - 1)
151  while not cset_isempty(s1):
152    s = s1
153    s1 = s & (s - 1)
154  return count_leading_zeroes(s)
155
156# compute [c in s if c < n]
157def cset_select_if_less(s, n):
158  return s & ((1 << n) - 1)
159
160# compute [c in s if c >= n]
161def cset_select_if_greater_or_equal(s, n):
162  return s - cset_select_if_less(s, n)
163
164def subtract_all(cset, n):
165  return cset >> n
166
167def cset_from_charset_expr(chardef):
168    cset = 0
169    for item in chardef.items:
170      if len(item) == 1:
171        cset |= 1 << ord(item[0])
172      else:
173        lo = ord(item[0])
174        hi = ord(item[2])
175        # compute a run of 1 bits of length hi - lo + 1
176        range_run = (1 << (hi - lo + 1)) - 1
177        cset |= (range_run << lo)
178    return cset
179
180#
181# Given a set of characters cset, build an expression to
182# produce a character class bit stream from the N low order
183# basis bit streams of # the transposed character representations.   
184#
185def CharSetExpr(N, cset):
186  characterMask = (1 << N) - 1
187  U = cset_universe(N)
188  #print "N = %i, cset = %x" % (N, cset)
189  if cset &~ U: # characters that cannot be represented in N bits
190    raise BadCharSetItem
191  if cset_isempty(cset): return FalseLiteral()
192  pop = popcount(cset)
193  if (pop > 2**(N-1)): return make_not(CharSetExpr(N, cset^U))
194  #if cset == U: return TrueLiteral()
195  if N == 1: 
196    if cset == 1: return make_not(make_bitv(0))
197    elif cset == 2: return make_bitv(0)
198    elif cset == 3: return TrueLiteral()
199  else:
200    h = cset_max(cset)
201    l = cset_min(cset)
202    if h == l: return bit_pattern_expr(l, characterMask)
203    diff_bits = h ^ l
204    Nd = 0
205    while diff_bits > 0:
206        Nd += 1
207        diff_bits >>= 1
208    mask = (1 << Nd) - 1
209    characterMask ^= mask
210    #print "h = %x, l = %x, Nd= %i" %(h, l, Nd)
211    hbase = h &~ (mask >> 1)
212    lbase = l &~ mask
213    # if only one bit differs, then it is a don't care.
214    if Nd == 1: return bit_pattern_expr(lbase, characterMask)
215    # hi = [c - hbase in cset if c >= hbase]
216    hi = subtract_all(cset_select_if_greater_or_equal(cset, hbase), hbase)
217    lo = subtract_all(cset_select_if_less(cset, hbase), lbase) # [c - lbase in cset if c < hbase]
218    if Nd == N: return make_sel(make_bitv(Nd-1), CharSetExpr(Nd-1, hi), CharSetExpr(Nd-1, lo))
219    c_expr = bit_pattern_expr(lbase, characterMask)
220    #print "hi = %x, lo = %x, hbase= %x, lbase= %x" %(hi, lo, hbase, lbase)
221    # heuristics
222    if hi == lo: # set equality 
223       return make_and(c_expr, CharSetExpr(Nd-1, lo))
224    #elif cset_isempty(cset_intersect(hi, lo)) and cset_union(hi,lo) == cset_universe(Nd):
225    #   return make_and(c_expr, make_xor(make_bitv(Nd-1), CharSetExpr(Nd-1, lo)))
226    #else: return make_and(c_expr, make_or(CharSetExpr(Nd, lo), CharSetExpr(Nd, hi)))
227    else: 
228      #print "hi = %x, lo = %x, Nd = %i" %(hi, lo, Nd)
229      return make_and(c_expr, make_sel(make_bitv(Nd-1), CharSetExpr(Nd-1, hi), CharSetExpr(Nd-1, lo)))
230
231
232
233
234
235def charset_expr_from_cset(chardef):
236    cset = cset_from_charset_expr(chardef)
237    return CharSetExpr(8, cset)
238   
239#
240#
241#  Code Generation
242#
243class CodeGenObject:
244    def __init__(self, predeclared, typedecl='BitBlock '):
245        self.gensym_template = options.gensym_pattern
246        self.gensym_counter = 0
247        self.generated_code = []
248        self.common_expression_map = {}
249        for sym in predeclared: self.common_expression_map[sym] = sym
250        self.typedecl = typedecl
251    def add_assignment(self, varname, expr):
252        self.common_expression_map[expr] = varname
253        #self.generated_code.append('%s%s = %s;\n' % (self.typedecl, varname, expr))
254        self.generated_code.append('\t%s%s = %s\n' % (self.typedecl, varname, expr))
255    def expr_string_to_variable(self, expr_string):
256        if self.common_expression_map.has_key(expr_string): 
257            return self.common_expression_map[expr_string]
258        else:
259            self.gensym_counter += 1
260            sym = self.gensym_template % self.gensym_counter
261            self.add_assignment(sym, expr_string)
262            return sym
263    def showcode(self):
264        s = ''
265        for stmt in self.generated_code: s += stmt
266        return s
267
268def expr2simd(genobj, expr):
269    """Translate a Boolean expression into three-address Altivec code
270       using code generator object genobj.
271    """
272    if isinstance(expr, TrueLiteral): return 'simd_const_1(1)'
273    elif isinstance(expr, FalseLiteral): return 'simd_const_1(0)'
274    elif isinstance(expr, Var): return expr.varname
275    elif isinstance(expr, Not):
276       e = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand))
277       return 'simd_andc(simd_const_1(1), %s)' % (e)
278    elif isinstance(expr, Or):
279       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
280       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
281       return 'simd_or(%s, %s)' % (e1, e2)
282    elif isinstance(expr, Xor):
283       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
284       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
285       return 'simd_xor(%s, %s)' % (e1, e2)
286    elif isinstance(expr, And):
287       if isinstance(expr.operand1, Not):
288           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1.operand))
289           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
290           return 'simd_andc(%s, %s)' % (e2, e1)
291       elif isinstance(expr.operand2, Not):
292           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
293           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2.operand))
294           return 'simd_andc(%s, %s)' % (e1, e2)
295       else:
296           e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand1))
297           e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.operand2))
298           return 'simd_and(%s, %s)' % (e1, e2)
299    elif isinstance(expr, Sel):
300       sel = genobj.expr_string_to_variable(expr2simd(genobj, expr.sel))
301       e1 = genobj.expr_string_to_variable(expr2simd(genobj, expr.true_branch))
302       e2 = genobj.expr_string_to_variable(expr2simd(genobj, expr.false_branch))
303       return 'simd_if(%s, %s, %s)' %(sel, e1, e2)
304
305def chardef2simd(genobj, chardef):
306    genobj.add_assignment(chardef.name, expr2simd(genobj, charset_expr(chardef)))
307
308def chardeflist2simd(chardeflist):
309    cgo = CodeGenObject([bit_var(i) for i in range(0,8)])
310    for d in chardeflist:
311        chardef2simd(cgo, d)
312    return cgo.showcode()
313
314def expr2py(genobj, expr):
315    """Translate a Boolean expression into three-address python code
316       using code generator object genobj.
317    """
318    if isinstance(expr, TrueLiteral): return '-1'
319    elif isinstance(expr, FalseLiteral): return '0'
320    elif isinstance(expr, Var): return expr.varname
321    elif isinstance(expr, Not):
322       e = genobj.expr_string_to_variable(expr2py(genobj, expr.operand))
323       return '(~%s)' % (e)
324    elif isinstance(expr, Or):
325       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
326       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
327       return '(%s | %s)' % (e1, e2)
328    elif isinstance(expr, Xor):
329       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
330       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
331       return '(%s ^ %s)' % (e1, e2)
332    elif isinstance(expr, And):
333       if isinstance(expr.operand1, Not):
334           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1.operand))
335           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
336           return '(%s &~ %s)' % (e2, e1)
337       elif isinstance(expr.operand2, Not):
338           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
339           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2.operand))
340           return '(%s &~ %s)' % (e1, e2)
341       else:
342           e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand1))
343           e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.operand2))
344           return '(%s & %s)' % (e1, e2)
345    elif isinstance(expr, Sel):
346       sel = genobj.expr_string_to_variable(expr2py(genobj, expr.sel))
347       e1 = genobj.expr_string_to_variable(expr2py(genobj, expr.true_branch))
348       e2 = genobj.expr_string_to_variable(expr2py(genobj, expr.false_branch))
349       return '((%s & %s)|(~(%s) & %s))' %(sel, e1, sel, e2)
350
351def chardef2py(genobj, chardef):
352    genobj.add_assignment(chardef.name, expr2py(genobj, charset_expr_from_cset(chardef)))
353    #genobj.add_assignment(chardef.name, expr2py(genobj, charset_expr(chardef)))
354
355
356def py_chardefmap(chardeflist):
357    defs = ["'%s' : %s" % (d.name,d.name) for d in chardeflist]
358    return  '{%s}' % string.join(defs, ',\n\t')
359
360def chardeflist2py(chardeflist):
361    cgo = CodeGenObject([bit_var(i) for i in range(0,8)],'')
362    for d in chardeflist:
363        chardef2py(cgo, d) 
364    return cgo.showcode()# + "  return "+ py_chardefmap(chardeflist) + "\n"
365
366
367
368def main():
369
370    global options
371    # Option definition
372    option_parser = optparse.OptionParser(usage='python %prog [options] <input file>', version='0.8')
373
374    option_parser.add_option('-b', '--basis_pattern', 
375                             dest='basis_pattern',
376                             type='string',
377                             default='basis_bits.bit_%i',
378                             help='pattern for basis bit streams; default: basis_bits.bit_%i',
379                             )
380    option_parser.add_option('-g', '--gensym_pattern', 
381                             dest='gensym_pattern',
382                             type='string',
383                             default='temp%i',
384                             help='pattern for generated temporaries; default: temp%i',
385                             )
386    option_parser.add_option('-E', '--EBCDIC', 
387                             dest='use_EBCDIC',
388                             action='store_true', 
389                             default=False,
390                             help='generate definitions for EBCDIC input',
391                             )
392    option_parser.add_option('-p', '--pablo', 
393                             dest='Pablo_skeleton',
394                             action='store_true', 
395                             default=False,
396                             help='generate pablo skeleton',
397                             )
398    option_parser.add_option('-t', '--test', 
399                             dest='test_skeleton',
400                             action='store_true', 
401                             default=False,
402                             help='generate pablo test skeleton',
403                             )
404    options, args = option_parser.parse_args(sys.argv[1:])
405
406    # Positional arguments
407    if len(args) == 1:
408        # if the specified argument is not in the DefinitionSet, then assume that it's a filename
409        if args[0] not in DefinitionSet:
410            #define the characters in the list
411            defs = charset_input_parser.input_chardef(args[0])
412        else: defs = DefinitionSet[args[1]]
413        if options.use_EBCDIC:
414            defs = EBCDIC.ascii2ebcdic_chardeflist(defs)       
415        stmts = chardeflist2py(defs)
416        if options.Pablo_skeleton or options.test_skeleton:
417          b = string.split(options.basis_pattern, ".")
418          if len(b) == 2: 
419            basis_struct = string.upper(b[0][0]) + b[0][1:]
420            basis_struct_var = b[0]
421            bit_pattern = b[1]
422          else: 
423            basis_struct = 'Bits'
424            basis_stuct_var = 'bits'
425            bit_pattern = bit[0]
426          struct_defs = "class %s():\n" % basis_struct
427          for i in range(8): struct_defs += "\t" + bit_pattern % i + " = 0\n"
428          struct_sets = {}
429          for d in defs:
430            n = string.split(d.name, ".")
431            if len(n) == 2:
432              if not n[0] in struct_sets.keys(): struct_sets[n[0]] = []
433              struct_sets[n[0]].append(n[1])
434          for k in struct_sets.keys():
435            struct_defs += "\nclass %s():\n" % (string.upper(k[0])+k[1:])
436            for f in struct_sets[k]: struct_defs += "\t" + f + " = 0\n"
437          print struct_defs
438          params = ", ".join([basis_struct_var] + struct_sets.keys())
439          print "\ndef Do_defs(%s):\n" % params
440          print stmts
441          if options.test_skeleton:
442            for d in defs:
443              print '\tprint_register<BitBlock>("%s",%s);\n' % (d.name, d.name)
444          print "\ndef main():\n\tDo_defs(%s)\n" % params
445        else: print stmts 
446
447    else:
448        option_parser.print_usage()
449
450if __name__ == "__main__": main()
451
Note: See TracBrowser for help on using the repository browser.