chiark - git - mdw - catacomb/blob - math/mpgen

   1 #! @PYTHON@
   2 ###
   3 ### Generate multiprecision integer representations
   4 ###
   5 ### (c) 2013 Straylight/Edgeware
   6 ###
   7
   8 ###----- Licensing notice ---------------------------------------------------
   9 ###
  10 ### This file is part of Catacomb.
  11 ###
  12 ### Catacomb is free software; you can redistribute it and/or modify
  13 ### it under the terms of the GNU Library General Public License as
  14 ### published by the Free Software Foundation; either version 2 of the
  15 ### License, or (at your option) any later version.
  16 ###
  17 ### Catacomb is distributed in the hope that it will be useful,
  18 ### but WITHOUT ANY WARRANTY; without even the implied warranty of
  19 ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20 ### GNU Library General Public License for more details.
  21 ###
  22 ### You should have received a copy of the GNU Library General Public
  23 ### License along with Catacomb; if not, write to the Free
  24 ### Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25 ### MA 02111-1307, USA.
  26
  27 from __future__ import with_statement
  28
  29 import re as RX
  30 import optparse as OP
  31 import sys as SYS; stdout = SYS.stdout
  32 import types as TY
  33
  34 ###--------------------------------------------------------------------------
  35 ### Random utilities.
  36
  37 def write_header(mode, name):
  38   """
  39   Write a C-language file header.
  40
  41   The header comment identifies the processing MODE, and the NAME of the
  42   output file.
  43   """
  44   stdout.write("""\
  45 /* -*-c-*- GENERATED by mpgen (%s)
  46  *
  47  * %s
  48  */
  49
  50 """ % (mode, name))
  51
  52 def write_banner(text):
  53   """Write a separator banner to the output, with header TEXT."""
  54   stdout.write("/*----- %s %s*/\n" % (text, '-' * (66 - len(text))))
  55
  56 class struct (object):
  57   """
  58   A struct object exists so that you can set attributes on it.
  59   """
  60   pass
  61
  62 R_IDBAD = RX.compile('[^0-9A-Za-z]')
  63 def fix_name(name):
  64   """Replace non-alphanumeric characters in NAME with underscores."""
  65   return R_IDBAD.sub('_', name)
  66
  67 if SYS.version_info >= (3,):
  68   def func_name(func): return func.__name__
  69   xrange = range
  70   long = int
  71 else:
  72   def func_name(func): return func.func_name
  73
  74 def with_metaclass(meta, *supers):
  75   return meta('#<anonymous base %s>' % meta.__name__,
  76               supers or (object,), dict())
  77
  78 def load(file, mod):
  79   with open(file) as f: text = f.read()
  80   code = compile(text, file, 'exec')
  81   exec(code, mod)
  82
  83 ###--------------------------------------------------------------------------
  84 ### Determining the appropriate types.
  85
  86 ## A dictionary mapping type tags to subclasses of BasicIntType.
  87 TYPEMAP = {}
  88
  89 class IntClass (type):
  90   """
  91   The IntClass is a metaclass for integer-type classes.
  92
  93   It associates the type class with its tag in the `TYPEMAP' dictionary.
  94   """
  95   def __new__(cls, name, supers, dict):
  96     c = type.__new__(cls, name, supers, dict)
  97     try: TYPEMAP[c.tag] = c
  98     except AttributeError: pass
  99     return c
 100
 101 class BasicIntType (with_metaclass(IntClass)):
 102   """
 103   A base class for integer-type classes, providing defaults and protocol.
 104
 105   Integer-type classes have the following attributes and methods.
 106
 107   preamble              Some code to be emitted to a header file to make use
 108                         of the type.  Defaults to the empty string.
 109
 110   typedef_prefix        A prefix to be written before the type's name in a
 111                         `typedef' declaration, possibly to muffle warnings.
 112                         Defaults to the empty string.
 113
 114   literalfmt            A Python `%' format string for generating literal
 115                         values of the type; used by the default `literal'
 116                         method (so if you override it then you don't need to
 117                         set this).  Defaults to `%su'.
 118
 119   literal(VALUE, [FMT]) Emit a literal value of the type, encoding VALUE.
 120                         The default FMT has the form `0x%0Nx', so as to emit
 121                         in hex with the appropriate number of leading zeros.
 122
 123   Instances also carry additional attributes.
 124
 125   bits                  The width of the integer type, in bits.
 126
 127   rank                  An integer giving the conversion rank of the type.
 128                         Higher values generally denote wider types.
 129
 130   litwd                 The width of a literal of the type, in characters.
 131   """
 132   __metaclass__ = IntClass
 133   preamble = ''
 134   typedef_prefix = ''
 135   literalfmt = '%su'
 136   def __init__(me, bits, rank):
 137     me.bits = bits
 138     me.rank = rank
 139     me.litwd = len(me.literal(0))
 140   def literal(me, value, fmt = None):
 141     if fmt is None: fmt = '0x%0' + str((me.bits + 3)//4) + 'x'
 142     return me.literalfmt % (fmt % value)
 143
 144 class UnsignedCharType (BasicIntType):
 145   tag = 'uchar'
 146   name = 'unsigned char'
 147
 148 class UnsignedShortType (BasicIntType):
 149   tag = 'ushort'
 150   name = 'unsigned short'
 151
 152 class UnsignedIntType (BasicIntType):
 153   tag = 'uint'
 154   name = 'unsigned int'
 155
 156 class UnsignedLongType (BasicIntType):
 157   tag = 'ulong'
 158   name = 'unsigned long'
 159   literalfmt = '%sul'
 160
 161 class UnsignedLongLongType (BasicIntType):
 162   tag = 'ullong'
 163   name = 'unsigned long long'
 164   preamble = """
 165 #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 91)
 166 #  define CATACOMB_GCC_EXTENSION __extension__
 167 #else
 168 #  define CATACOMB_GCC_EXTENSION
 169 #endif
 170 """
 171   typedef_prefix = 'CATACOMB_GCC_EXTENSION '
 172   literalfmt = 'CATACOMB_GCC_EXTENSION %sull'
 173
 174 class UIntMaxType (BasicIntType):
 175   tag = 'uintmax'
 176   name = 'uintmax_t'
 177   preamble = "\n#include <stdint.h>\n"
 178
 179 class TypeChoice (object):
 180   """
 181   A TypeChoice object selects C integer types for multiprecision integers.
 182
 183   It exports its decisions as attributes:
 184
 185   mpwbits               The width of an `mpw', in bits.
 186
 187   mpw                   The integer type for single-precision values.
 188
 189   mpd                   The integer type for double-precision values.
 190
 191   ti                    An object bearing raw information about the available
 192                         integer types, as follows...
 193
 194     TYPEINFO            A list of items (TAG, BITS) describing the widths of
 195                         the available types suitable for multiprecision use,
 196                         in ascending order of rank.
 197
 198     LIMITS              A list of items (TAG, LO, HI) describing the ranges
 199                         of integer types, for constructing the `mplimits'
 200                         files.
 201   """
 202
 203   def __init__(me, tifile):
 204     """
 205     Read the definitions from TIFILE, and select types appropriately.
 206
 207     The TIFILE is a tiny fragment of Python code which should set `TYPEINFO'
 208     and `LIMITS' in its global namespace.
 209     """
 210
 211     ## Load the captured type information.
 212     me.ti = TY.ModuleType('typeinfo')
 213     load(opts.typeinfo, me.ti.__dict__)
 214
 215     ## Build a map of the available types.
 216     tymap = {}
 217     byrank = []
 218     for tag, bits in me.ti.TYPEINFO:
 219       rank = len(byrank)
 220       tymap[tag] = rank
 221       byrank.append(TYPEMAP[tag](bits, rank))
 222
 223     ## First pass: determine a suitable word size.  The criteria are (a)
 224     ## there exists another type at least twice as long (so that we can do a
 225     ## single x single -> double multiplication), and (b) operations on a
 226     ## word are efficient (so we'd prefer a plain machine word).  We'll start
 227     ## at `int' and work down.  Maybe this won't work: there's a plan B.
 228     mpwbits = 0
 229     i = tymap['uint']
 230     while not mpwbits and i >= 0:
 231       ibits = byrank[i].bits
 232       for j in xrange(i + 1, len(byrank)):
 233         if byrank[j].bits >= 2*ibits:
 234           mpwbits = ibits
 235           break
 236
 237     ## If that didn't work, then we'll start with the largest type available
 238     ## and go with half its size.
 239     if not mpwbits:
 240       mpwbits = byrank[-1].bits//2
 241
 242     ## Make sure we've not ended up somewhere really silly.
 243     if mpwbits < 16:
 244       raise Exception("`mpw' type is too small: your C environment is weird")
 245
 246     ## Now figure out suitable types for `mpw' and `mpd'.
 247     def find_type(bits, what):
 248       for ty in byrank:
 249         if ty.bits >= bits: return ty
 250       raise Exception \
 251         ("failed to find suitable %d-bit type, for %s" % (bits, what))
 252
 253     ## Store our decisions.
 254     me.mpwbits = mpwbits
 255     me.mpw = find_type(mpwbits, 'mpw')
 256     me.mpd = find_type(mpwbits*2, 'mpd')
 257
 258 ###--------------------------------------------------------------------------
 259 ### Outputting constant multiprecision integers.
 260
 261 ## The margin for outputting MP literals.
 262 MARGIN = 72
 263
 264 def write_preamble():
 265   """
 266   Write a preamble for files containing multiprecision literals.
 267
 268   We define a number of macros for use by the rest of the code:
 269
 270   ZERO_MP               An `mp' initializer denoting the value zero.
 271
 272   POS_MP(NAME)          Constructs an `mp' initializer denoting a positive
 273                         integer whose limbs were emitted with the given
 274                         NAME.
 275
 276   NEG_MP(NAME)          Constructs an `mp' initializer denoting a negative
 277                         integer whose limbs were emitted with the given
 278                         NAME.
 279   """
 280   stdout.write("""
 281 #include <mLib/macros.h>
 282 #define MP_(name, flags) \\
 283   { (/*unconst*/ mpw *)name##__mpw, \\
 284     (/*unconst*/ mpw *)name##__mpw + N(name##__mpw), \\
 285     N(name##__mpw), 0, MP_CONST | flags, 0 }
 286 #define ZERO_MP { 0, 0, 0, 0, MP_CONST, 0 }
 287 #define POS_MP(name) MP_(name, 0)
 288 #define NEG_MP(name) MP_(name, MP_NEG)
 289 """)
 290
 291 def write_limbs(name, x):
 292   """
 293   Write the limbs of the value X, with the given NAME.
 294   """
 295
 296   ## We don't need to do anything special for zero.
 297   if not x: return
 298
 299   ## Start on the limb vector.  No delimiter needed, and we shall need to
 300   ## start a new line before any actual output.  We want to write the
 301   ## absolute value here, because we use a signed-magnitude representation.
 302   stdout.write("\nstatic const mpw %s__mpw[] = {" % name)
 303   sep = ''
 304   pos = MARGIN
 305   if x < 0: x = -x
 306   mask = (1 << TC.mpwbits) - 1
 307
 308   ## We work from the little-end up, picking off `mpwbits' at a time.  Start
 309   ## a new line if we can't fit the value on the current one.
 310   while x > 0:
 311     w, x = x & mask, x >> TC.mpwbits
 312     f = TC.mpw.literal(w)
 313     if pos + 2 + len(f) <= MARGIN:
 314       stdout.write(sep + ' ' + f)
 315     else:
 316       pos = 2
 317       stdout.write(sep + '\n  ' + f)
 318     pos += len(f) + 2
 319     sep = ','
 320
 321   ## We're done.  Finish off the initializer.
 322   stdout.write("\n};\n")
 323
 324 def mp_body(name, x):
 325   """
 326   Write the body of an `mp' object, for the value NAME.
 327   """
 328   return "%s_MP(%s)" % (x >= 0 and "POS" or "NEG", name)
 329
 330 ###--------------------------------------------------------------------------
 331 ### Mode definition machinery.
 332
 333 ## A dictionary mapping mode names to their handler functions.
 334 MODEMAP = {}
 335
 336 def defmode(func):
 337   """
 338   Function decorator: associate the function with the name of a mode.
 339
 340   The mode name is taken from the function's name: a leading `m_' is stripped
 341   off, if there is one.  Mode functions are invoked with the positional
 342   arguments from the command and are expected to write their output to
 343   stdout.
 344   """
 345   name = func_name(func)
 346   if name.startswith('m_'): name = name[2:]
 347   MODEMAP[name] = func
 348   return func
 349
 350 ###--------------------------------------------------------------------------
 351 ### The basic types header.
 352
 353 @defmode
 354 def m_mptypes():
 355   """
 356   Write the `mptypes.h' header.
 357
 358   This establishes the following types.
 359
 360   mpw                   An integer type for single-precision values.
 361
 362   mpd                   An integer type for double-precision values.
 363
 364   And, for t being each of `w' or `d', the following constants:
 365
 366   MPt_BITS              The width of the type, in bits.
 367
 368   MPt_P2                The smallest integer k such that 2^k is not less than
 369                         MPt_BITS.  (This is used for binary searches.)
 370
 371   MPt_MAX               The largest value which may be stored in an object of
 372                         the type.
 373   """
 374
 375   ## Write the preamble.
 376   write_header("mptypes", "mptypes.h")
 377   stdout.write("""\
 378 #ifndef CATACOMB_MPTYPES_H
 379 #define CATACOMB_MPTYPES_H
 380 """)
 381
 382   ## Write any additional premable for the types we've selected.
 383   have = set([TC.mpw, TC.mpd])
 384   for t in have:
 385     stdout.write(t.preamble)
 386
 387   ## Emit the types and constants.
 388   for label, t, bits in [('mpw', TC.mpw, TC.mpwbits),
 389                          ('mpd', TC.mpd, TC.mpwbits*2)]:
 390     LABEL = label.upper()
 391     stdout.write("\n%stypedef %s %s;\n" % (t.typedef_prefix, t.name, label))
 392     stdout.write("#define %s_BITS %d\n" % (LABEL, bits))
 393     i = 1
 394     while 2*i < bits: i *= 2
 395     stdout.write("#define %s_P2 %d\n" % (LABEL, i))
 396     stdout.write("#define %s_MAX %s\n" % (LABEL,
 397                                           t.literal((1 << bits) - 1, "%d")))
 398
 399   ## Done.
 400   stdout.write("\n#endif\n")
 401
 402 ###--------------------------------------------------------------------------
 403 ### Constant tables.
 404
 405 @defmode
 406 def m_mplimits_c():
 407   """
 408   Write the `mplimits.c' source file.
 409
 410   This contains `mp' constants corresponding to the various integer types'
 411   upper and lower bounds.  The output is a vector `mp_limits' consisting of
 412   the distinct nonzero bounds, in order of their first occurrence in the
 413   `ti.LIMITS' list.
 414   """
 415
 416   ## Write the preamble.
 417   write_header("mplimits_c", "mplimits.c")
 418   stdout.write('#include "mplimits.h"\n')
 419   write_preamble()
 420
 421   ## Write out limbs for limits as we come across them.
 422   seen = {}
 423   v = []
 424   def write(x):
 425     if not x or x in seen: return
 426     seen[x] = 1
 427     write_limbs('limits_%d' % len(v), x)
 428     v.append(x)
 429   for tag, lo, hi in TC.ti.LIMITS:
 430     write(lo)
 431     write(hi)
 432
 433   ## Write the main vector.
 434   stdout.write("\nmp mp_limits[] = {")
 435   i = 0
 436   sep = "\n  "
 437   for x in v:
 438     stdout.write("%s%s_MP(limits_%d)" % (sep, x < 0 and "NEG" or "POS", i))
 439     i += 1
 440     sep = ",\n  "
 441   stdout.write("\n};\n");
 442
 443 @defmode
 444 def m_mplimits_h():
 445   """
 446   Write the `mplimits.h' source file.
 447
 448   For each type TAG, this defines constants MP_TAG_MIN and MP_TAG_MAX
 449   representing the lower and upper bounds of the type.
 450   """
 451
 452   ## Write the preamble.
 453   write_header("mplimits_h", "mplimits.h")
 454   stdout.write("""\
 455 #ifndef CATACOMB_MPLIMITS_H
 456 #define CATACOMB_MPLIMITS_H
 457
 458 #ifndef CATACOMB_MP_H
 459 #  include "mp.h"
 460 #endif
 461
 462 extern mp mp_limits[];
 463
 464 """)
 465
 466   ## Now define constants for the bounds.  Things which are zero can go to
 467   ## our existing `MP_ZERO'; otherwise we index the `mp_limits' vector.
 468   seen = { 0: "MP_ZERO" }
 469   slot = [0]
 470   def find(x):
 471     try:
 472       r = seen[x]
 473     except KeyError:
 474       r = seen[x] = '(&mp_limits[%d])' % slot[0]
 475       slot[0] += 1
 476     return r
 477   for tag, lo, hi in TC.ti.LIMITS:
 478     stdout.write("#define MP_%s_MIN %s\n" % (tag, find(lo)))
 479     stdout.write("#define MP_%s_MAX %s\n" % (tag, find(hi)))
 480
 481   ## All done.
 482   stdout.write("\n#endif\n")
 483
 484 ###--------------------------------------------------------------------------
 485 ### Group tables.
 486
 487 class GroupTableClass (type):
 488   """
 489   Metaclass for group tables, which registers them in the `MODEMAP'.
 490
 491   Such a class must define an attribute `mode' giving the mode name, and a
 492   class method `run' which writes the necessary output.
 493   """
 494   def __new__(cls, name, supers, dict):
 495     c = type.__new__(cls, name, supers, dict)
 496     try: mode = c.mode
 497     except AttributeError: pass
 498     else: MODEMAP[c.mode] = c.run
 499     return c
 500
 501 class GroupTable (with_metaclass(GroupTableClass)):
 502   """
 503   Base class for group tables objects.
 504
 505   A `group table' is a table of constants, typically defining a cyclic group
 506   or something similar.  We read the values from an input file, and write
 507   them out as C definitions.  These have a somewhat stereotyped format, so we
 508   can mostly handle them uniformly.
 509
 510   Specifically, input files consist of lines which are split into
 511   whitespace-separated words.  Blank lines, and lines beginning with `#', are
 512   ignored.  The remaining lines are gathered together into stanzas of the
 513   form
 514
 515   KEYWORD NAME [HEAD-VALUE ...]
 516         SLOT VALUE
 517         ...
 518
 519   (Indentation is shown for clarity only.)  Such a stanza describes a group
 520   NAME; some slots are assigned values from the headline, and others from
 521   their own individual lines.
 522
 523   Subclasses must define the following attributes.
 524
 525   data_t                The name of the type for describing a particular
 526                         group.
 527
 528   entry_t               The name of the type which associates a name with
 529                         some group data; this will be defined as
 530
 531                                 typedef struct ENTRY_T {
 532                                   const char *name;
 533                                   DATA_T *data;
 534                                 } ENTRY_T;
 535
 536                         or similar.
 537
 538   filename              The filename, typically `SOMETHING.c', to put in the
 539                         output header.
 540
 541   header                The header file to include, so as to establish the
 542                         necessary types and other definitions.
 543
 544   keyword               The keyword beginning a new definition in the input
 545                         file.  The default is `group'.
 546
 547   mode                  The mode name, used to invoke this kind of table
 548                         operation (used by GroupTableClass).
 549
 550   slots                 A vector of slot objects (see BaseSlot for the
 551                         protocol) describing the structure of this particular
 552                         kind of group, in the order they should be written in
 553                         an initializer.
 554
 555   Instances carry an `st' attribute, which contains a `struct' object in
 556   which slots can maintain some state.  This object carries the following
 557   attributes maintained by this class.
 558
 559   d                     A dictionary mapping slots (not their names!) to
 560                         values assigned in the current stanza.  This is reset
 561                         at the start of each stanza.  Slot implementations
 562                         a free to use this or not, and the representation is
 563                         internal to the specific slot class.
 564
 565   mpmap                 A dictionary mapping values (integers, or `None') to
 566                         C initializers (typically, actually, macro
 567                         invocations).
 568
 569   name                  The name of the group currently being parsed.
 570
 571   nextmp                Index for the next `mp' object to be written.
 572   """
 573
 574   ## Additional attributes, for internal use:
 575   ##
 576   ## _defs              A set of known names for groups.
 577   ##
 578   ## _headslots         A list of slots filled in from the headline.
 579   ##
 580   ## _names             A list of pairs (ALIAS, DATA) mapping alias names to
 581   ##                    the actual group data.
 582   ##
 583   ## _slotmap           A dictionary mapping slot names to their
 584   ##                    descriptions.
 585
 586   ## Default values.
 587   keyword = 'group'
 588   slots = []
 589
 590   def __init__(me):
 591     """
 592     Initialize a group table object.
 593     """
 594
 595     me.st = st = struct()
 596     st.nextmp = 0
 597     st.mpmap = { None: 'NO_MP', 0: 'ZERO_MP' }
 598     st.d = {}
 599     st.name = None
 600     me._names = []
 601     me._defs = set()
 602     me._slotmap = dict([(s.name, s) for s in me.slots])
 603     me._headslots = [s for s in me.slots if s.headline]
 604
 605   def _flush(me):
 606     """
 607     Write out the data for a group once we've detected the end of its stanza.
 608     """
 609
 610     ## If there's no current stanza, then do nothing.
 611     if me.st.name is None: return
 612
 613     ## Start emitting the object.
 614     stdout.write("/* --- %s --- */\n" % me.st.name)
 615
 616     ## Get the various slots to compute themselves.
 617     for s in me.slots: s.setup(me.st)
 618
 619     ## Write the initializer.
 620     stdout.write("\nstatic %s c_%s = {" % (me.data_t, fix_name(me.st.name)))
 621     sep = "\n  "
 622     for s in me.slots:
 623       stdout.write(sep)
 624       s.write(me.st)
 625       sep = ",\n  "
 626     stdout.write("\n};\n\n")
 627
 628     ## Clear the state for the next stanza.
 629     me.st.d = {}
 630     me.st.name = None
 631
 632   @classmethod
 633   def run(cls, input):
 634     """
 635     Main output for a group table.  Reads the file INPUT.
 636     """
 637
 638     ## Make an object for us to work on.
 639     me = cls()
 640
 641     ## Write the output preamble.
 642     write_header(me.mode, me.filename)
 643     stdout.write('#include "%s"\n' % me.header)
 644     write_preamble()
 645     stdout.write("#define NO_MP { 0, 0, 0, 0, 0, 0 }\n\n")
 646
 647     ## The main group data.  This will contain a `data_t' object for each
 648     ## group we read.  We'll also build the name to data map as we go.
 649     write_banner("Group data")
 650     stdout.write('\n')
 651     with open(input) as file:
 652       for line in file:
 653
 654         ## Parse the line into fields.
 655         ff = line.split()
 656         if not ff or ff[0].startswith('#'): continue
 657
 658         if ff[0] == 'alias':
 659           ## An alias.  Just remember this.
 660           if len(ff) != 3: raise Exception("wrong number of alias arguments")
 661           me._flush()
 662           me._names.append((ff[1], ff[2]))
 663
 664         elif ff[0] == me.keyword:
 665           ## A headline for a new group.
 666
 667           ## Check the headline syntax.  Headline slots may be set here, or
 668           ## later by name.
 669           if len(ff) < 2 or len(ff) > 2 + len(me._headslots):
 670             raise Exception("bad number of headline arguments")
 671
 672           ## Flush out the previous stanza.
 673           me._flush()
 674
 675           ## Remember the new stanza's name, and add it to the list.
 676           me.st.name = name = ff[1]
 677           me._defs.add(name)
 678           me._names.append((name, name))
 679
 680           ## Set headline slots from the remaining headline words.
 681           for f, s in zip(ff[2:], me._headslots): s.set(me.st, f)
 682
 683         elif ff[0] in me._slotmap:
 684           ## A slot assignment.  Get the slot to store a value.
 685           if me.st.name is None:
 686             raise Exception("no group currently being defined")
 687           if len(ff) != 2:
 688             raise Exception("bad number of values for slot `%s'" % ff[0])
 689           me._slotmap[ff[0]].set(me.st, ff[1])
 690
 691         else:
 692           ## Something incomprehensible.
 693           raise Exception("unknown keyword `%s'" % ff[0])
 694
 695     ## End of the input.  Write out the final stanza.
 696     me._flush()
 697
 698     ## Now for the name-to-data mapping.
 699     write_banner("Main table")
 700     stdout.write("\nconst %s %s[] = {\n" % (me.entry_t, me.tabname))
 701     for a, n in me._names:
 702       if n not in me._defs:
 703         raise Exception("alias `%s' refers to unknown group `%s'" % (a, n))
 704       stdout.write('  { "%s", &c_%s },\n' % (a, fix_name(n)))
 705     stdout.write("  { 0, 0 }\n};\n\n")
 706
 707     ## We're done.
 708     write_banner("That's all, folks")
 709
 710 class BaseSlot (object):
 711   """
 712   Base class for slot types.
 713
 714   The slot protocol works as follows.  Throughout, ST is a state object as
 715   maintained by a GroupTable.
 716
 717   __init__(NAME, [HEADLINE], [OMITP], [ALLOWP], ...)
 718                         Initialize the slot.  The NAME identifies the slot,
 719                         and the keyword used to set it in input files.  If
 720                         HEADLINE is true then the slot can be set from the
 721                         stanza headline.  OMITP and ALLOWP are optional
 722                         functions: if OMITP(ST) returns true then the slot
 723                         may be omitted; conversely, if ALLOWP(ST, VALUE)
 724                         returns false then the slot cannot be assigned the
 725                         given VALUE.  Other arguments may be allowed by
 726                         specific slot types.
 727
 728   set(ST, VALUE)        Set the slot to the given VALUE, typically by setting
 729                         ST.d[me].  The default just stores the VALUE without
 730                         interpreting it.
 731
 732   setup(ST)             Prepare the slot for output.  The default method just
 733                         checks that ST.d contains a mapping for the slot.
 734                         All of the stanza's slots are set up before starting
 735                         on the initializer for the group data, so slots can
 736                         use this opportunity to emit preparatory definitions.
 737
 738   write(ST)             Write an initializer for the slot to standard
 739                         output.  There is no default.
 740
 741   The following attributes are exported.
 742
 743   headline              A flag: can the slot be initialized from the stanza
 744                         headline?
 745
 746   name                  The slot's name.
 747   """
 748
 749   def __init__(me, name, headline = False, omitp = None, allowp = None):
 750     """
 751     Initialize a new slot object, setting the necessary attributes.
 752     """
 753     me.name = name
 754     me.headline = headline
 755     me._omitp = omitp
 756     me._allowp = allowp
 757
 758   def set(me, st, value):
 759     """
 760     Store a VALUE for the slot.
 761     """
 762     if me._allowp and not me._allowp(st, value):
 763       raise Exception("slot `%s' not allowed here" % me.name)
 764     st.d[me] = value
 765
 766   def setup(me, st):
 767     """
 768     Prepare the slot for output, checking its value and so on.
 769     """
 770     if me not in st.d and (not me._omitp or not me._omitp(st)):
 771       raise Exception("missing slot `%s'" % me.name)
 772
 773 class EnumSlot (BaseSlot):
 774   """
 775   An EnumSlot object represents a slot which can contain one of a number of
 776   named values.
 777
 778   An omitted value is written as a literal `0'.
 779   """
 780
 781   def __init__(me, name, prefix, values, **kw):
 782     """
 783     Initialize an EnumSlot object.
 784
 785     The VALUES are a set of value names.  On output, a value is converted to
 786     uppercase, and prefixed by the PREFIX and an underscore.
 787     """
 788     super(EnumSlot, me).__init__(name, **kw)
 789     me._values = set(values)
 790     me._prefix = prefix
 791
 792   def set(me, st, value):
 793     """
 794     Check that the VALUE is one of the ones we know.
 795     """
 796     if value not in me._values:
 797       raise Exception("invalid %s value `%s'" % (me.name, value))
 798     super(EnumSlot, me).set(st, value)
 799
 800   def write(me, st):
 801     """
 802     Convert the slot value to the C constant name.
 803     """
 804     try: stdout.write('%s_%s' % (me._prefix, st.d[me].upper()))
 805     except KeyError: stdout.write('0')
 806
 807 class MPSlot (BaseSlot):
 808   """
 809   An MPSlot object represents a slot which can contain a multiprecision
 810   integer.
 811
 812   An omitted value is written as a invalid `mp' object.
 813   """
 814
 815   def set(me, st, value):
 816     """
 817     Set a value; convert it to a Python integer.
 818     """
 819     super(MPSlot, me).set(st, long(value, 0))
 820
 821   def setup(me, st):
 822     """
 823     Prepare to write the slot.
 824
 825     If this is a new integer, then write out a limb vector.  Names for the
 826     limbs are generated unimaginitively, using a counter.
 827     """
 828     super(MPSlot, me).setup(st)
 829     v = st.d.get(me)
 830     if v not in st.mpmap:
 831       write_limbs('v%d' % st.nextmp, v)
 832       st.mpmap[v] = mp_body('v%d' % st.nextmp, v)
 833       st.nextmp += 1
 834
 835   def write(me, st):
 836     """
 837     Write out an `mp' initializer for the slot.
 838     """
 839     stdout.write(st.mpmap[st.d.get(me)])
 840
 841 class BinaryGroupTable (GroupTable):
 842   mode = 'bintab'
 843   filename = 'bintab.c'
 844   header = 'bintab.h'
 845   data_t = 'bindata'
 846   entry_t = 'binentry'
 847   tabname = 'bintab'
 848   slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]
 849
 850 class EllipticCurveTable (GroupTable):
 851   mode = 'ectab'
 852   filename = 'ectab.c'
 853   header = 'ectab.h'
 854   keyword = 'curve'
 855   data_t = 'ecdata'
 856   entry_t = 'ecentry'
 857   tabname = 'ectab'
 858   _typeslot = EnumSlot('type', 'FTAG',
 859                        ['prime', 'niceprime', 'binpoly', 'binnorm'],
 860                        headline = True)
 861   slots = [_typeslot,
 862            MPSlot('p'),
 863            MPSlot('beta',
 864                   allowp = lambda st, _:
 865                     st.d[EllipticCurveTable._typeslot] == 'binnorm',
 866                   omitp = lambda st:
 867                     st.d[EllipticCurveTable._typeslot] != 'binnorm'),
 868            MPSlot('a'), MPSlot('b'), MPSlot('r'), MPSlot('h'),
 869            MPSlot('gx'), MPSlot('gy')]
 870
 871 class PrimeGroupTable (GroupTable):
 872   mode = 'ptab'
 873   filename = 'ptab.c'
 874   header = 'ptab.h'
 875   data_t = 'pdata'
 876   entry_t = 'pentry'
 877   tabname = 'ptab'
 878   slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]
 879
 880 ###--------------------------------------------------------------------------
 881 ### Main program.
 882
 883 op = OP.OptionParser(
 884   description = 'Generate multiprecision integer representations',
 885   usage = 'usage: %prog [-t TYPEINFO] MODE [ARGS ...]',
 886   version = 'Catacomb, version @VERSION@')
 887 for shortopt, longopt, kw in [
 888   ('-t', '--typeinfo', dict(
 889       action = 'store', metavar = 'PATH', dest = 'typeinfo',
 890       help = 'alternative typeinfo file'))]:
 891   op.add_option(shortopt, longopt, **kw)
 892 op.set_defaults(typeinfo = './typeinfo.py')
 893 opts, args = op.parse_args()
 894
 895 ## Parse the positional arguments.
 896 if len(args) < 1: op.error('missing MODE')
 897 mode = args[0]
 898
 899 ## Establish the choice of low-level C types.
 900 TC = TypeChoice(opts.typeinfo)
 901
 902 ## Find the selected mode, and invoke the appropriate handler.
 903 try: modefunc = MODEMAP[mode]
 904 except KeyError: op.error("unknown mode `%s'" % mode)
 905 modefunc(*args[1:])
 906
 907 ###----- That's all, folks --------------------------------------------------