scripts/decodetree.py

   1 #!/usr/bin/env python
   2 # Copyright (c) 2018 Linaro Limited
   3 #
   4 # This library is free software; you can redistribute it and/or
   5 # modify it under the terms of the GNU Lesser General Public
   6 # License as published by the Free Software Foundation; either
   7 # version 2 of the License, or (at your option) any later version.
   8 #
   9 # This library is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12 # Lesser General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU Lesser General Public
  15 # License along with this library; if not, see <http://www.gnu.org/licenses/>.
  16 #
  17
  18 #
  19 # Generate a decoding tree from a specification file.
  20 # See the syntax and semantics in docs/devel/decodetree.rst.
  21 #
  22
  23 import os
  24 import re
  25 import sys
  26 import getopt
  27
  28 insnwidth = 32
  29 insnmask = 0xffffffff
  30 variablewidth = False
  31 fields = {}
  32 arguments = {}
  33 formats = {}
  34 patterns = []
  35 allpatterns = []
  36
  37 translate_prefix = 'trans'
  38 translate_scope = 'static '
  39 input_file = ''
  40 output_file = None
  41 output_fd = None
  42 insntype = 'uint32_t'
  43 decode_function = 'decode'
  44
  45 re_ident = '[a-zA-Z][a-zA-Z0-9_]*'
  46
  47
  48 def error_with_file(file, lineno, *args):
  49     """Print an error message from file:line and args and exit."""
  50     global output_file
  51     global output_fd
  52
  53     if lineno:
  54         r = '{0}:{1}: error:'.format(file, lineno)
  55     elif input_file:
  56         r = '{0}: error:'.format(file)
  57     else:
  58         r = 'error:'
  59     for a in args:
  60         r += ' ' + str(a)
  61     r += '\n'
  62     sys.stderr.write(r)
  63     if output_file and output_fd:
  64         output_fd.close()
  65         os.remove(output_file)
  66     exit(1)
  67
  68 def error(lineno, *args):
  69     error_with_file(input_file, lineno, args)
  70
  71 def output(*args):
  72     global output_fd
  73     for a in args:
  74         output_fd.write(a)
  75
  76
  77 if sys.version_info >= (3, 4):
  78     re_fullmatch = re.fullmatch
  79 else:
  80     def re_fullmatch(pat, str):
  81         return re.match('^' + pat + '$', str)
  82
  83
  84 def output_autogen():
  85     output('/* This file is autogenerated by scripts/decodetree.py.  */\n\n')
  86
  87
  88 def str_indent(c):
  89     """Return a string with C spaces"""
  90     return ' ' * c
  91
  92
  93 def str_fields(fields):
  94     """Return a string uniquely identifing FIELDS"""
  95     r = ''
  96     for n in sorted(fields.keys()):
  97         r += '_' + n
  98     return r[1:]
  99
 100
 101 def str_match_bits(bits, mask):
 102     """Return a string pretty-printing BITS/MASK"""
 103     global insnwidth
 104
 105     i = 1 << (insnwidth - 1)
 106     space = 0x01010100
 107     r = ''
 108     while i != 0:
 109         if i & mask:
 110             if i & bits:
 111                 r += '1'
 112             else:
 113                 r += '0'
 114         else:
 115             r += '.'
 116         if i & space:
 117             r += ' '
 118         i >>= 1
 119     return r
 120
 121
 122 def is_pow2(x):
 123     """Return true iff X is equal to a power of 2."""
 124     return (x & (x - 1)) == 0
 125
 126
 127 def ctz(x):
 128     """Return the number of times 2 factors into X."""
 129     r = 0
 130     while ((x >> r) & 1) == 0:
 131         r += 1
 132     return r
 133
 134
 135 def is_contiguous(bits):
 136     shift = ctz(bits)
 137     if is_pow2((bits >> shift) + 1):
 138         return shift
 139     else:
 140         return -1
 141
 142
 143 def eq_fields_for_args(flds_a, flds_b):
 144     if len(flds_a) != len(flds_b):
 145         return False
 146     for k, a in flds_a.items():
 147         if k not in flds_b:
 148             return False
 149     return True
 150
 151
 152 def eq_fields_for_fmts(flds_a, flds_b):
 153     if len(flds_a) != len(flds_b):
 154         return False
 155     for k, a in flds_a.items():
 156         if k not in flds_b:
 157             return False
 158         b = flds_b[k]
 159         if a.__class__ != b.__class__ or a != b:
 160             return False
 161     return True
 162
 163
 164 class Field:
 165     """Class representing a simple instruction field"""
 166     def __init__(self, sign, pos, len):
 167         self.sign = sign
 168         self.pos = pos
 169         self.len = len
 170         self.mask = ((1 << len) - 1) << pos
 171
 172     def __str__(self):
 173         if self.sign:
 174             s = 's'
 175         else:
 176             s = ''
 177         return str(self.pos) + ':' + s + str(self.len)
 178
 179     def str_extract(self):
 180         if self.sign:
 181             extr = 'sextract32'
 182         else:
 183             extr = 'extract32'
 184         return '{0}(insn, {1}, {2})'.format(extr, self.pos, self.len)
 185
 186     def __eq__(self, other):
 187         return self.sign == other.sign and self.mask == other.mask
 188
 189     def __ne__(self, other):
 190         return not self.__eq__(other)
 191 # end Field
 192
 193
 194 class MultiField:
 195     """Class representing a compound instruction field"""
 196     def __init__(self, subs, mask):
 197         self.subs = subs
 198         self.sign = subs[0].sign
 199         self.mask = mask
 200
 201     def __str__(self):
 202         return str(self.subs)
 203
 204     def str_extract(self):
 205         ret = '0'
 206         pos = 0
 207         for f in reversed(self.subs):
 208             if pos == 0:
 209                 ret = f.str_extract()
 210             else:
 211                 ret = 'deposit32({0}, {1}, {2}, {3})' \
 212                       .format(ret, pos, 32 - pos, f.str_extract())
 213             pos += f.len
 214         return ret
 215
 216     def __ne__(self, other):
 217         if len(self.subs) != len(other.subs):
 218             return True
 219         for a, b in zip(self.subs, other.subs):
 220             if a.__class__ != b.__class__ or a != b:
 221                 return True
 222         return False
 223
 224     def __eq__(self, other):
 225         return not self.__ne__(other)
 226 # end MultiField
 227
 228
 229 class ConstField:
 230     """Class representing an argument field with constant value"""
 231     def __init__(self, value):
 232         self.value = value
 233         self.mask = 0
 234         self.sign = value < 0
 235
 236     def __str__(self):
 237         return str(self.value)
 238
 239     def str_extract(self):
 240         return str(self.value)
 241
 242     def __cmp__(self, other):
 243         return self.value - other.value
 244 # end ConstField
 245
 246
 247 class FunctionField:
 248     """Class representing a field passed through an expander"""
 249     def __init__(self, func, base):
 250         self.mask = base.mask
 251         self.sign = base.sign
 252         self.base = base
 253         self.func = func
 254
 255     def __str__(self):
 256         return self.func + '(' + str(self.base) + ')'
 257
 258     def str_extract(self):
 259         return self.func + '(ctx, ' + self.base.str_extract() + ')'
 260
 261     def __eq__(self, other):
 262         return self.func == other.func and self.base == other.base
 263
 264     def __ne__(self, other):
 265         return not self.__eq__(other)
 266 # end FunctionField
 267
 268
 269 class Arguments:
 270     """Class representing the extracted fields of a format"""
 271     def __init__(self, nm, flds, extern):
 272         self.name = nm
 273         self.extern = extern
 274         self.fields = sorted(flds)
 275
 276     def __str__(self):
 277         return self.name + ' ' + str(self.fields)
 278
 279     def struct_name(self):
 280         return 'arg_' + self.name
 281
 282     def output_def(self):
 283         if not self.extern:
 284             output('typedef struct {\n')
 285             for n in self.fields:
 286                 output('    int ', n, ';\n')
 287             output('} ', self.struct_name(), ';\n\n')
 288 # end Arguments
 289
 290
 291 class General:
 292     """Common code between instruction formats and instruction patterns"""
 293     def __init__(self, name, lineno, base, fixb, fixm, udfm, fldm, flds, w):
 294         self.name = name
 295         self.file = input_file
 296         self.lineno = lineno
 297         self.base = base
 298         self.fixedbits = fixb
 299         self.fixedmask = fixm
 300         self.undefmask = udfm
 301         self.fieldmask = fldm
 302         self.fields = flds
 303         self.width = w
 304
 305     def __str__(self):
 306         return self.name + ' ' + str_match_bits(self.fixedbits, self.fixedmask)
 307
 308     def str1(self, i):
 309         return str_indent(i) + self.__str__()
 310 # end General
 311
 312
 313 class Format(General):
 314     """Class representing an instruction format"""
 315
 316     def extract_name(self):
 317         global decode_function
 318         return decode_function + '_extract_' + self.name
 319
 320     def output_extract(self):
 321         output('static void ', self.extract_name(), '(DisasContext *ctx, ',
 322                self.base.struct_name(), ' *a, ', insntype, ' insn)\n{\n')
 323         for n, f in self.fields.items():
 324             output('    a->', n, ' = ', f.str_extract(), ';\n')
 325         output('}\n\n')
 326 # end Format
 327
 328
 329 class Pattern(General):
 330     """Class representing an instruction pattern"""
 331
 332     def output_decl(self):
 333         global translate_scope
 334         global translate_prefix
 335         output('typedef ', self.base.base.struct_name(),
 336                ' arg_', self.name, ';\n')
 337         output(translate_scope, 'bool ', translate_prefix, '_', self.name,
 338                '(DisasContext *ctx, arg_', self.name, ' *a);\n')
 339
 340     def output_code(self, i, extracted, outerbits, outermask):
 341         global translate_prefix
 342         ind = str_indent(i)
 343         arg = self.base.base.name
 344         output(ind, '/* ', self.file, ':', str(self.lineno), ' */\n')
 345         if not extracted:
 346             output(ind, self.base.extract_name(),
 347                    '(ctx, &u.f_', arg, ', insn);\n')
 348         for n, f in self.fields.items():
 349             output(ind, 'u.f_', arg, '.', n, ' = ', f.str_extract(), ';\n')
 350         output(ind, 'if (', translate_prefix, '_', self.name,
 351                '(ctx, &u.f_', arg, ')) return true;\n')
 352 # end Pattern
 353
 354
 355 class MultiPattern(General):
 356     """Class representing an overlapping set of instruction patterns"""
 357
 358     def __init__(self, lineno, pats, fixb, fixm, udfm, w):
 359         self.file = input_file
 360         self.lineno = lineno
 361         self.pats = pats
 362         self.base = None
 363         self.fixedbits = fixb
 364         self.fixedmask = fixm
 365         self.undefmask = udfm
 366         self.width = w
 367
 368     def __str__(self):
 369         r = "{"
 370         for p in self.pats:
 371            r = r + ' ' + str(p)
 372         return r + "}"
 373
 374     def output_decl(self):
 375         for p in self.pats:
 376             p.output_decl()
 377
 378     def output_code(self, i, extracted, outerbits, outermask):
 379         global translate_prefix
 380         ind = str_indent(i)
 381         for p in self.pats:
 382             if outermask != p.fixedmask:
 383                 innermask = p.fixedmask & ~outermask
 384                 innerbits = p.fixedbits & ~outermask
 385                 output(ind, 'if ((insn & ',
 386                        '0x{0:08x}) == 0x{1:08x}'.format(innermask, innerbits),
 387                        ') {\n')
 388                 output(ind, '    /* ',
 389                        str_match_bits(p.fixedbits, p.fixedmask), ' */\n')
 390                 p.output_code(i + 4, extracted, p.fixedbits, p.fixedmask)
 391                 output(ind, '}\n')
 392             else:
 393                 p.output_code(i, extracted, p.fixedbits, p.fixedmask)
 394 #end MultiPattern
 395
 396
 397 def parse_field(lineno, name, toks):
 398     """Parse one instruction field from TOKS at LINENO"""
 399     global fields
 400     global re_ident
 401     global insnwidth
 402
 403     # A "simple" field will have only one entry;
 404     # a "multifield" will have several.
 405     subs = []
 406     width = 0
 407     func = None
 408     for t in toks:
 409         if re_fullmatch('!function=' + re_ident, t):
 410             if func:
 411                 error(lineno, 'duplicate function')
 412             func = t.split('=')
 413             func = func[1]
 414             continue
 415
 416         if re_fullmatch('[0-9]+:s[0-9]+', t):
 417             # Signed field extract
 418             subtoks = t.split(':s')
 419             sign = True
 420         elif re_fullmatch('[0-9]+:[0-9]+', t):
 421             # Unsigned field extract
 422             subtoks = t.split(':')
 423             sign = False
 424         else:
 425             error(lineno, 'invalid field token "{0}"'.format(t))
 426         po = int(subtoks[0])
 427         le = int(subtoks[1])
 428         if po + le > insnwidth:
 429             error(lineno, 'field {0} too large'.format(t))
 430         f = Field(sign, po, le)
 431         subs.append(f)
 432         width += le
 433
 434     if width > insnwidth:
 435         error(lineno, 'field too large')
 436     if len(subs) == 1:
 437         f = subs[0]
 438     else:
 439         mask = 0
 440         for s in subs:
 441             if mask & s.mask:
 442                 error(lineno, 'field components overlap')
 443             mask |= s.mask
 444         f = MultiField(subs, mask)
 445     if func:
 446         f = FunctionField(func, f)
 447
 448     if name in fields:
 449         error(lineno, 'duplicate field', name)
 450     fields[name] = f
 451 # end parse_field
 452
 453
 454 def parse_arguments(lineno, name, toks):
 455     """Parse one argument set from TOKS at LINENO"""
 456     global arguments
 457     global re_ident
 458
 459     flds = []
 460     extern = False
 461     for t in toks:
 462         if re_fullmatch('!extern', t):
 463             extern = True
 464             continue
 465         if not re_fullmatch(re_ident, t):
 466             error(lineno, 'invalid argument set token "{0}"'.format(t))
 467         if t in flds:
 468             error(lineno, 'duplicate argument "{0}"'.format(t))
 469         flds.append(t)
 470
 471     if name in arguments:
 472         error(lineno, 'duplicate argument set', name)
 473     arguments[name] = Arguments(name, flds, extern)
 474 # end parse_arguments
 475
 476
 477 def lookup_field(lineno, name):
 478     global fields
 479     if name in fields:
 480         return fields[name]
 481     error(lineno, 'undefined field', name)
 482
 483
 484 def add_field(lineno, flds, new_name, f):
 485     if new_name in flds:
 486         error(lineno, 'duplicate field', new_name)
 487     flds[new_name] = f
 488     return flds
 489
 490
 491 def add_field_byname(lineno, flds, new_name, old_name):
 492     return add_field(lineno, flds, new_name, lookup_field(lineno, old_name))
 493
 494
 495 def infer_argument_set(flds):
 496     global arguments
 497     global decode_function
 498
 499     for arg in arguments.values():
 500         if eq_fields_for_args(flds, arg.fields):
 501             return arg
 502
 503     name = decode_function + str(len(arguments))
 504     arg = Arguments(name, flds.keys(), False)
 505     arguments[name] = arg
 506     return arg
 507
 508
 509 def infer_format(arg, fieldmask, flds, width):
 510     global arguments
 511     global formats
 512     global decode_function
 513
 514     const_flds = {}
 515     var_flds = {}
 516     for n, c in flds.items():
 517         if c is ConstField:
 518             const_flds[n] = c
 519         else:
 520             var_flds[n] = c
 521
 522     # Look for an existing format with the same argument set and fields
 523     for fmt in formats.values():
 524         if arg and fmt.base != arg:
 525             continue
 526         if fieldmask != fmt.fieldmask:
 527             continue
 528         if width != fmt.width:
 529             continue
 530         if not eq_fields_for_fmts(flds, fmt.fields):
 531             continue
 532         return (fmt, const_flds)
 533
 534     name = decode_function + '_Fmt_' + str(len(formats))
 535     if not arg:
 536         arg = infer_argument_set(flds)
 537
 538     fmt = Format(name, 0, arg, 0, 0, 0, fieldmask, var_flds, width)
 539     formats[name] = fmt
 540
 541     return (fmt, const_flds)
 542 # end infer_format
 543
 544
 545 def parse_generic(lineno, is_format, name, toks):
 546     """Parse one instruction format from TOKS at LINENO"""
 547     global fields
 548     global arguments
 549     global formats
 550     global patterns
 551     global allpatterns
 552     global re_ident
 553     global insnwidth
 554     global insnmask
 555     global variablewidth
 556
 557     fixedmask = 0
 558     fixedbits = 0
 559     undefmask = 0
 560     width = 0
 561     flds = {}
 562     arg = None
 563     fmt = None
 564     for t in toks:
 565         # '&Foo' gives a format an explcit argument set.
 566         if t[0] == '&':
 567             tt = t[1:]
 568             if arg:
 569                 error(lineno, 'multiple argument sets')
 570             if tt in arguments:
 571                 arg = arguments[tt]
 572             else:
 573                 error(lineno, 'undefined argument set', t)
 574             continue
 575
 576         # '@Foo' gives a pattern an explicit format.
 577         if t[0] == '@':
 578             tt = t[1:]
 579             if fmt:
 580                 error(lineno, 'multiple formats')
 581             if tt in formats:
 582                 fmt = formats[tt]
 583             else:
 584                 error(lineno, 'undefined format', t)
 585             continue
 586
 587         # '%Foo' imports a field.
 588         if t[0] == '%':
 589             tt = t[1:]
 590             flds = add_field_byname(lineno, flds, tt, tt)
 591             continue
 592
 593         # 'Foo=%Bar' imports a field with a different name.
 594         if re_fullmatch(re_ident + '=%' + re_ident, t):
 595             (fname, iname) = t.split('=%')
 596             flds = add_field_byname(lineno, flds, fname, iname)
 597             continue
 598
 599         # 'Foo=number' sets an argument field to a constant value
 600         if re_fullmatch(re_ident + '=[+-]?[0-9]+', t):
 601             (fname, value) = t.split('=')
 602             value = int(value)
 603             flds = add_field(lineno, flds, fname, ConstField(value))
 604             continue
 605
 606         # Pattern of 0s, 1s, dots and dashes indicate required zeros,
 607         # required ones, or dont-cares.
 608         if re_fullmatch('[01.-]+', t):
 609             shift = len(t)
 610             fms = t.replace('0', '1')
 611             fms = fms.replace('.', '0')
 612             fms = fms.replace('-', '0')
 613             fbs = t.replace('.', '0')
 614             fbs = fbs.replace('-', '0')
 615             ubm = t.replace('1', '0')
 616             ubm = ubm.replace('.', '0')
 617             ubm = ubm.replace('-', '1')
 618             fms = int(fms, 2)
 619             fbs = int(fbs, 2)
 620             ubm = int(ubm, 2)
 621             fixedbits = (fixedbits << shift) | fbs
 622             fixedmask = (fixedmask << shift) | fms
 623             undefmask = (undefmask << shift) | ubm
 624         # Otherwise, fieldname:fieldwidth
 625         elif re_fullmatch(re_ident + ':s?[0-9]+', t):
 626             (fname, flen) = t.split(':')
 627             sign = False
 628             if flen[0] == 's':
 629                 sign = True
 630                 flen = flen[1:]
 631             shift = int(flen, 10)
 632             if shift + width > insnwidth:
 633                 error(lineno, 'field {0} exceeds insnwidth'.format(fname))
 634             f = Field(sign, insnwidth - width - shift, shift)
 635             flds = add_field(lineno, flds, fname, f)
 636             fixedbits <<= shift
 637             fixedmask <<= shift
 638             undefmask <<= shift
 639         else:
 640             error(lineno, 'invalid token "{0}"'.format(t))
 641         width += shift
 642
 643     if variablewidth and width < insnwidth and width % 8 == 0:
 644         shift = insnwidth - width
 645         fixedbits <<= shift
 646         fixedmask <<= shift
 647         undefmask <<= shift
 648         undefmask |= (1 << shift) - 1
 649
 650     # We should have filled in all of the bits of the instruction.
 651     elif not (is_format and width == 0) and width != insnwidth:
 652         error(lineno, 'definition has {0} bits'.format(width))
 653
 654     # Do not check for fields overlaping fields; one valid usage
 655     # is to be able to duplicate fields via import.
 656     fieldmask = 0
 657     for f in flds.values():
 658         fieldmask |= f.mask
 659
 660     # Fix up what we've parsed to match either a format or a pattern.
 661     if is_format:
 662         # Formats cannot reference formats.
 663         if fmt:
 664             error(lineno, 'format referencing format')
 665         # If an argument set is given, then there should be no fields
 666         # without a place to store it.
 667         if arg:
 668             for f in flds.keys():
 669                 if f not in arg.fields:
 670                     error(lineno, 'field {0} not in argument set {1}'
 671                                   .format(f, arg.name))
 672         else:
 673             arg = infer_argument_set(flds)
 674         if name in formats:
 675             error(lineno, 'duplicate format name', name)
 676         fmt = Format(name, lineno, arg, fixedbits, fixedmask,
 677                      undefmask, fieldmask, flds, width)
 678         formats[name] = fmt
 679     else:
 680         # Patterns can reference a format ...
 681         if fmt:
 682             # ... but not an argument simultaneously
 683             if arg:
 684                 error(lineno, 'pattern specifies both format and argument set')
 685             if fixedmask & fmt.fixedmask:
 686                 error(lineno, 'pattern fixed bits overlap format fixed bits')
 687             if width != fmt.width:
 688                 error(lineno, 'pattern uses format of different width')
 689             fieldmask |= fmt.fieldmask
 690             fixedbits |= fmt.fixedbits
 691             fixedmask |= fmt.fixedmask
 692             undefmask |= fmt.undefmask
 693         else:
 694             (fmt, flds) = infer_format(arg, fieldmask, flds, width)
 695         arg = fmt.base
 696         for f in flds.keys():
 697             if f not in arg.fields:
 698                 error(lineno, 'field {0} not in argument set {1}'
 699                               .format(f, arg.name))
 700             if f in fmt.fields.keys():
 701                 error(lineno, 'field {0} set by format and pattern'.format(f))
 702         for f in arg.fields:
 703             if f not in flds.keys() and f not in fmt.fields.keys():
 704                 error(lineno, 'field {0} not initialized'.format(f))
 705         pat = Pattern(name, lineno, fmt, fixedbits, fixedmask,
 706                       undefmask, fieldmask, flds, width)
 707         patterns.append(pat)
 708         allpatterns.append(pat)
 709
 710     # Validate the masks that we have assembled.
 711     if fieldmask & fixedmask:
 712         error(lineno, 'fieldmask overlaps fixedmask (0x{0:08x} & 0x{1:08x})'
 713                       .format(fieldmask, fixedmask))
 714     if fieldmask & undefmask:
 715         error(lineno, 'fieldmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 716                       .format(fieldmask, undefmask))
 717     if fixedmask & undefmask:
 718         error(lineno, 'fixedmask overlaps undefmask (0x{0:08x} & 0x{1:08x})'
 719                       .format(fixedmask, undefmask))
 720     if not is_format:
 721         allbits = fieldmask | fixedmask | undefmask
 722         if allbits != insnmask:
 723             error(lineno, 'bits left unspecified (0x{0:08x})'
 724                           .format(allbits ^ insnmask))
 725 # end parse_general
 726
 727 def build_multi_pattern(lineno, pats):
 728     """Validate the Patterns going into a MultiPattern."""
 729     global patterns
 730     global insnmask
 731
 732     if len(pats) < 2:
 733         error(lineno, 'less than two patterns within braces')
 734
 735     fixedmask = insnmask
 736     undefmask = insnmask
 737
 738     # Collect fixed/undefmask for all of the children.
 739     # Move the defining lineno back to that of the first child.
 740     for p in pats:
 741         fixedmask &= p.fixedmask
 742         undefmask &= p.undefmask
 743         if p.lineno < lineno:
 744             lineno = p.lineno
 745
 746     width = None
 747     for p in pats:
 748         if width is None:
 749             width = p.width
 750         elif width != p.width:
 751             error(lineno, 'width mismatch in patterns within braces')
 752
 753     repeat = True
 754     while repeat:
 755         if fixedmask == 0:
 756             error(lineno, 'no overlap in patterns within braces')
 757         fixedbits = None
 758         for p in pats:
 759             thisbits = p.fixedbits & fixedmask
 760             if fixedbits is None:
 761                 fixedbits = thisbits
 762             elif fixedbits != thisbits:
 763                 fixedmask &= ~(fixedbits ^ thisbits)
 764                 break
 765         else:
 766             repeat = False
 767
 768     mp = MultiPattern(lineno, pats, fixedbits, fixedmask, undefmask, width)
 769     patterns.append(mp)
 770 # end build_multi_pattern
 771
 772 def parse_file(f):
 773     """Parse all of the patterns within a file"""
 774
 775     global patterns
 776
 777     # Read all of the lines of the file.  Concatenate lines
 778     # ending in backslash; discard empty lines and comments.
 779     toks = []
 780     lineno = 0
 781     nesting = 0
 782     saved_pats = []
 783
 784     for line in f:
 785         lineno += 1
 786
 787         # Expand and strip spaces, to find indent.
 788         line = line.rstrip()
 789         line = line.expandtabs()
 790         len1 = len(line)
 791         line = line.lstrip()
 792         len2 = len(line)
 793
 794         # Discard comments
 795         end = line.find('#')
 796         if end >= 0:
 797             line = line[:end]
 798
 799         t = line.split()
 800         if len(toks) != 0:
 801             # Next line after continuation
 802             toks.extend(t)
 803         else:
 804             # Allow completely blank lines.
 805             if len1 == 0:
 806                 continue
 807             indent = len1 - len2
 808             # Empty line due to comment.
 809             if len(t) == 0:
 810                 # Indentation must be correct, even for comment lines.
 811                 if indent != nesting:
 812                     error(lineno, 'indentation ', indent, ' != ', nesting)
 813                 continue
 814             start_lineno = lineno
 815             toks = t
 816
 817         # Continuation?
 818         if toks[-1] == '\\':
 819             toks.pop()
 820             continue
 821
 822         name = toks[0]
 823         del toks[0]
 824
 825         # End nesting?
 826         if name == '}':
 827             if nesting == 0:
 828                 error(start_lineno, 'mismatched close brace')
 829             if len(toks) != 0:
 830                 error(start_lineno, 'extra tokens after close brace')
 831             nesting -= 2
 832             if indent != nesting:
 833                 error(start_lineno, 'indentation ', indent, ' != ', nesting)
 834             pats = patterns
 835             patterns = saved_pats.pop()
 836             build_multi_pattern(lineno, pats)
 837             toks = []
 838             continue
 839
 840         # Everything else should have current indentation.
 841         if indent != nesting:
 842             error(start_lineno, 'indentation ', indent, ' != ', nesting)
 843
 844         # Start nesting?
 845         if name == '{':
 846             if len(toks) != 0:
 847                 error(start_lineno, 'extra tokens after open brace')
 848             saved_pats.append(patterns)
 849             patterns = []
 850             nesting += 2
 851             toks = []
 852             continue
 853
 854         # Determine the type of object needing to be parsed.
 855         if name[0] == '%':
 856             parse_field(start_lineno, name[1:], toks)
 857         elif name[0] == '&':
 858             parse_arguments(start_lineno, name[1:], toks)
 859         elif name[0] == '@':
 860             parse_generic(start_lineno, True, name[1:], toks)
 861         else:
 862             parse_generic(start_lineno, False, name, toks)
 863         toks = []
 864 # end parse_file
 865
 866
 867 class Tree:
 868     """Class representing a node in a decode tree"""
 869
 870     def __init__(self, fm, tm):
 871         self.fixedmask = fm
 872         self.thismask = tm
 873         self.subs = []
 874         self.base = None
 875
 876     def str1(self, i):
 877         ind = str_indent(i)
 878         r = '{0}{1:08x}'.format(ind, self.fixedmask)
 879         if self.format:
 880             r += ' ' + self.format.name
 881         r += ' [\n'
 882         for (b, s) in self.subs:
 883             r += '{0}  {1:08x}:\n'.format(ind, b)
 884             r += s.str1(i + 4) + '\n'
 885         r += ind + ']'
 886         return r
 887
 888     def __str__(self):
 889         return self.str1(0)
 890
 891     def output_code(self, i, extracted, outerbits, outermask):
 892         ind = str_indent(i)
 893
 894         # If we identified all nodes below have the same format,
 895         # extract the fields now.
 896         if not extracted and self.base:
 897             output(ind, self.base.extract_name(),
 898                    '(ctx, &u.f_', self.base.base.name, ', insn);\n')
 899             extracted = True
 900
 901         # Attempt to aid the compiler in producing compact switch statements.
 902         # If the bits in the mask are contiguous, extract them.
 903         sh = is_contiguous(self.thismask)
 904         if sh > 0:
 905             # Propagate SH down into the local functions.
 906             def str_switch(b, sh=sh):
 907                 return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh)
 908
 909             def str_case(b, sh=sh):
 910                 return '0x{0:x}'.format(b >> sh)
 911         else:
 912             def str_switch(b):
 913                 return 'insn & 0x{0:08x}'.format(b)
 914
 915             def str_case(b):
 916                 return '0x{0:08x}'.format(b)
 917
 918         output(ind, 'switch (', str_switch(self.thismask), ') {\n')
 919         for b, s in sorted(self.subs):
 920             assert (self.thismask & ~s.fixedmask) == 0
 921             innermask = outermask | self.thismask
 922             innerbits = outerbits | b
 923             output(ind, 'case ', str_case(b), ':\n')
 924             output(ind, '    /* ',
 925                    str_match_bits(innerbits, innermask), ' */\n')
 926             s.output_code(i + 4, extracted, innerbits, innermask)
 927             output(ind, '    return false;\n')
 928         output(ind, '}\n')
 929 # end Tree
 930
 931
 932 def build_tree(pats, outerbits, outermask):
 933     # Find the intersection of all remaining fixedmask.
 934     innermask = ~outermask & insnmask
 935     for i in pats:
 936         innermask &= i.fixedmask
 937
 938     if innermask == 0:
 939         text = 'overlapping patterns:'
 940         for p in pats:
 941             text += '\n' + p.file + ':' + str(p.lineno) + ': ' + str(p)
 942         error_with_file(pats[0].file, pats[0].lineno, text)
 943
 944     fullmask = outermask | innermask
 945
 946     # Sort each element of pats into the bin selected by the mask.
 947     bins = {}
 948     for i in pats:
 949         fb = i.fixedbits & innermask
 950         if fb in bins:
 951             bins[fb].append(i)
 952         else:
 953             bins[fb] = [i]
 954
 955     # We must recurse if any bin has more than one element or if
 956     # the single element in the bin has not been fully matched.
 957     t = Tree(fullmask, innermask)
 958
 959     for b, l in bins.items():
 960         s = l[0]
 961         if len(l) > 1 or s.fixedmask & ~fullmask != 0:
 962             s = build_tree(l, b | outerbits, fullmask)
 963         t.subs.append((b, s))
 964
 965     return t
 966 # end build_tree
 967
 968
 969 class SizeTree:
 970     """Class representing a node in a size decode tree"""
 971
 972     def __init__(self, m, w):
 973         self.mask = m
 974         self.subs = []
 975         self.base = None
 976         self.width = w
 977
 978     def str1(self, i):
 979         ind = str_indent(i)
 980         r = '{0}{1:08x}'.format(ind, self.mask)
 981         r += ' [\n'
 982         for (b, s) in self.subs:
 983             r += '{0}  {1:08x}:\n'.format(ind, b)
 984             r += s.str1(i + 4) + '\n'
 985         r += ind + ']'
 986         return r
 987
 988     def __str__(self):
 989         return self.str1(0)
 990
 991     def output_code(self, i, extracted, outerbits, outermask):
 992         ind = str_indent(i)
 993
 994         # If we need to load more bytes to test, do so now.
 995         if extracted < self.width:
 996             output(ind, 'insn = ', decode_function,
 997                    '_load_bytes(ctx, insn, {0}, {1});\n'
 998                    .format(extracted / 8, self.width / 8));
 999             extracted = self.width
1000
1001         # Attempt to aid the compiler in producing compact switch statements.
1002         # If the bits in the mask are contiguous, extract them.
1003         sh = is_contiguous(self.mask)
1004         if sh > 0:
1005             # Propagate SH down into the local functions.
1006             def str_switch(b, sh=sh):
1007                 return '(insn >> {0}) & 0x{1:x}'.format(sh, b >> sh)
1008
1009             def str_case(b, sh=sh):
1010                 return '0x{0:x}'.format(b >> sh)
1011         else:
1012             def str_switch(b):
1013                 return 'insn & 0x{0:08x}'.format(b)
1014
1015             def str_case(b):
1016                 return '0x{0:08x}'.format(b)
1017
1018         output(ind, 'switch (', str_switch(self.mask), ') {\n')
1019         for b, s in sorted(self.subs):
1020             innermask = outermask | self.mask
1021             innerbits = outerbits | b
1022             output(ind, 'case ', str_case(b), ':\n')
1023             output(ind, '    /* ',
1024                    str_match_bits(innerbits, innermask), ' */\n')
1025             s.output_code(i + 4, extracted, innerbits, innermask)
1026         output(ind, '}\n')
1027         output(ind, 'return insn;\n')
1028 # end SizeTree
1029
1030 class SizeLeaf:
1031     """Class representing a leaf node in a size decode tree"""
1032
1033     def __init__(self, m, w):
1034         self.mask = m
1035         self.width = w
1036
1037     def str1(self, i):
1038         ind = str_indent(i)
1039         return '{0}{1:08x}'.format(ind, self.mask)
1040
1041     def __str__(self):
1042         return self.str1(0)
1043
1044     def output_code(self, i, extracted, outerbits, outermask):
1045         global decode_function
1046         ind = str_indent(i)
1047
1048         # If we need to load more bytes, do so now.
1049         if extracted < self.width:
1050             output(ind, 'insn = ', decode_function,
1051                    '_load_bytes(ctx, insn, {0}, {1});\n'
1052                    .format(extracted / 8, self.width / 8));
1053             extracted = self.width
1054         output(ind, 'return insn;\n')
1055 # end SizeLeaf
1056
1057
1058 def build_size_tree(pats, width, outerbits, outermask):
1059     global insnwidth
1060
1061     # Collect the mask of bits that are fixed in this width
1062     innermask = 0xff << (insnwidth - width)
1063     innermask &= ~outermask
1064     minwidth = None
1065     onewidth = True
1066     for i in pats:
1067         innermask &= i.fixedmask
1068         if minwidth is None:
1069             minwidth = i.width
1070         elif minwidth != i.width:
1071             onewidth = False;
1072             if minwidth < i.width:
1073                 minwidth = i.width
1074
1075     if onewidth:
1076         return SizeLeaf(innermask, minwidth)
1077
1078     if innermask == 0:
1079         if width < minwidth:
1080             return build_size_tree(pats, width + 8, outerbits, outermask)
1081
1082         pnames = []
1083         for p in pats:
1084             pnames.append(p.name + ':' + p.file + ':' + str(p.lineno))
1085         error_with_file(pats[0].file, pats[0].lineno,
1086                         'overlapping patterns size {0}:'.format(width), pnames)
1087
1088     bins = {}
1089     for i in pats:
1090         fb = i.fixedbits & innermask
1091         if fb in bins:
1092             bins[fb].append(i)
1093         else:
1094             bins[fb] = [i]
1095
1096     fullmask = outermask | innermask
1097     lens = sorted(bins.keys())
1098     if len(lens) == 1:
1099         b = lens[0]
1100         return build_size_tree(bins[b], width + 8, b | outerbits, fullmask)
1101
1102     r = SizeTree(innermask, width)
1103     for b, l in bins.items():
1104         s = build_size_tree(l, width, b | outerbits, fullmask)
1105         r.subs.append((b, s))
1106     return r
1107 # end build_size_tree
1108
1109
1110 def prop_format(tree):
1111     """Propagate Format objects into the decode tree"""
1112
1113     # Depth first search.
1114     for (b, s) in tree.subs:
1115         if isinstance(s, Tree):
1116             prop_format(s)
1117
1118     # If all entries in SUBS have the same format, then
1119     # propagate that into the tree.
1120     f = None
1121     for (b, s) in tree.subs:
1122         if f is None:
1123             f = s.base
1124             if f is None:
1125                 return
1126         if f is not s.base:
1127             return
1128     tree.base = f
1129 # end prop_format
1130
1131
1132 def prop_size(tree):
1133     """Propagate minimum widths up the decode size tree"""
1134
1135     if isinstance(tree, SizeTree):
1136         min = None
1137         for (b, s) in tree.subs:
1138             width = prop_size(s)
1139             if min is None or min > width:
1140                 min = width
1141         assert min >= tree.width
1142         tree.width = min
1143     else:
1144         min = tree.width
1145     return min
1146 # end prop_size
1147
1148
1149 def main():
1150     global arguments
1151     global formats
1152     global patterns
1153     global allpatterns
1154     global translate_scope
1155     global translate_prefix
1156     global output_fd
1157     global output_file
1158     global input_file
1159     global insnwidth
1160     global insntype
1161     global insnmask
1162     global decode_function
1163     global variablewidth
1164
1165     decode_scope = 'static '
1166
1167     long_opts = ['decode=', 'translate=', 'output=', 'insnwidth=',
1168                  'static-decode=', 'varinsnwidth=']
1169     try:
1170         (opts, args) = getopt.getopt(sys.argv[1:], 'o:vw:', long_opts)
1171     except getopt.GetoptError as err:
1172         error(0, err)
1173     for o, a in opts:
1174         if o in ('-o', '--output'):
1175             output_file = a
1176         elif o == '--decode':
1177             decode_function = a
1178             decode_scope = ''
1179         elif o == '--static-decode':
1180             decode_function = a
1181         elif o == '--translate':
1182             translate_prefix = a
1183             translate_scope = ''
1184         elif o in ('-w', '--insnwidth', '--varinsnwidth'):
1185             if o == '--varinsnwidth':
1186                 variablewidth = True
1187             insnwidth = int(a)
1188             if insnwidth == 16:
1189                 insntype = 'uint16_t'
1190                 insnmask = 0xffff
1191             elif insnwidth != 32:
1192                 error(0, 'cannot handle insns of width', insnwidth)
1193         else:
1194             assert False, 'unhandled option'
1195
1196     if len(args) < 1:
1197         error(0, 'missing input file')
1198     for filename in args:
1199         input_file = filename
1200         f = open(filename, 'r')
1201         parse_file(f)
1202         f.close()
1203
1204     if variablewidth:
1205         stree = build_size_tree(patterns, 8, 0, 0)
1206         prop_size(stree)
1207
1208     dtree = build_tree(patterns, 0, 0)
1209     prop_format(dtree)
1210
1211     if output_file:
1212         output_fd = open(output_file, 'w')
1213     else:
1214         output_fd = sys.stdout
1215
1216     output_autogen()
1217     for n in sorted(arguments.keys()):
1218         f = arguments[n]
1219         f.output_def()
1220
1221     # A single translate function can be invoked for different patterns.
1222     # Make sure that the argument sets are the same, and declare the
1223     # function only once.
1224     out_pats = {}
1225     for i in allpatterns:
1226         if i.name in out_pats:
1227             p = out_pats[i.name]
1228             if i.base.base != p.base.base:
1229                 error(0, i.name, ' has conflicting argument sets')
1230         else:
1231             i.output_decl()
1232             out_pats[i.name] = i
1233     output('\n')
1234
1235     for n in sorted(formats.keys()):
1236         f = formats[n]
1237         f.output_extract()
1238
1239     output(decode_scope, 'bool ', decode_function,
1240            '(DisasContext *ctx, ', insntype, ' insn)\n{\n')
1241
1242     i4 = str_indent(4)
1243
1244     if len(allpatterns) != 0:
1245         output(i4, 'union {\n')
1246         for n in sorted(arguments.keys()):
1247             f = arguments[n]
1248             output(i4, i4, f.struct_name(), ' f_', f.name, ';\n')
1249         output(i4, '} u;\n\n')
1250         dtree.output_code(4, False, 0, 0)
1251
1252     output(i4, 'return false;\n')
1253     output('}\n')
1254
1255     if variablewidth:
1256         output('\n', decode_scope, insntype, ' ', decode_function,
1257                '_load(DisasContext *ctx)\n{\n',
1258                '    ', insntype, ' insn = 0;\n\n')
1259         stree.output_code(4, 0, 0, 0)
1260         output('}\n')
1261
1262     if output_file:
1263         output_fd.close()
1264 # end main
1265
1266
1267 if __name__ == '__main__':
1268     main()