| 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 -------------------------------------------------- |