source: proto/charsetcompiler/charset_compiler2.py

Last change on this file was 3947, checked in by cameron, 5 years ago

Rename bitwise-expr to pablo-expr;add advance expression, pablo-stmt

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