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