| 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 | stdout.write("""\ |
| 40 | /* -*-c-*- GENERATED by mpgen (%s) |
| 41 | * |
| 42 | * %s |
| 43 | */ |
| 44 | |
| 45 | """ % (mode, name)) |
| 46 | |
| 47 | def write_banner(text): |
| 48 | stdout.write("/*----- %s %s*/\n" % (text, '-' * (66 - len(text)))) |
| 49 | |
| 50 | class struct (object): pass |
| 51 | |
| 52 | R_IDBAD = RX.compile('[^0-9A-Za-z]') |
| 53 | def fix_name(name): return R_IDBAD.sub('_', name) |
| 54 | |
| 55 | ###-------------------------------------------------------------------------- |
| 56 | ### Determining the appropriate types. |
| 57 | |
| 58 | TYPEMAP = {} |
| 59 | |
| 60 | class IntClass (type): |
| 61 | def __new__(cls, name, supers, dict): |
| 62 | c = type.__new__(cls, name, supers, dict) |
| 63 | try: TYPEMAP[c.tag] = c |
| 64 | except AttributeError: pass |
| 65 | return c |
| 66 | |
| 67 | class BasicIntType (object): |
| 68 | __metaclass__ = IntClass |
| 69 | preamble = '' |
| 70 | typedef_prefix = '' |
| 71 | literalfmt = '%su' |
| 72 | def __init__(me, bits, rank): |
| 73 | me.bits = bits |
| 74 | me.rank = rank |
| 75 | me.litwd = len(me.literal(0)) |
| 76 | def literal(me, value, fmt = None): |
| 77 | if fmt is None: fmt = '0x%0' + str((me.bits + 3)//4) + 'x' |
| 78 | return me.literalfmt % (fmt % value) |
| 79 | |
| 80 | class UnsignedCharType (BasicIntType): |
| 81 | tag = 'uchar' |
| 82 | name = 'unsigned char' |
| 83 | |
| 84 | class UnsignedShortType (BasicIntType): |
| 85 | tag = 'ushort' |
| 86 | name = 'unsigned short' |
| 87 | |
| 88 | class UnsignedIntType (BasicIntType): |
| 89 | tag = 'uint' |
| 90 | name = 'unsigned int' |
| 91 | |
| 92 | class UnsignedLongType (BasicIntType): |
| 93 | tag = 'ulong' |
| 94 | name = 'unsigned long' |
| 95 | literalfmt = '%sul' |
| 96 | |
| 97 | class UnsignedLongLongType (BasicIntType): |
| 98 | tag = 'ullong' |
| 99 | name = 'unsigned long long' |
| 100 | preamble = """ |
| 101 | #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 91) |
| 102 | # define CATACOMB_GCC_EXTENSION __extension__ |
| 103 | #else |
| 104 | # define CATACOMB_GCC_EXTENSION |
| 105 | #endif |
| 106 | """ |
| 107 | typedef_prefix = 'CATACOMB_GCC_EXTENSION ' |
| 108 | literalfmt = 'CATACOMB_GCC_EXTENSION %sull' |
| 109 | |
| 110 | class UIntMaxType (BasicIntType): |
| 111 | tag = 'uintmax' |
| 112 | name = 'uintmax_t' |
| 113 | preamble = "\n#include <stdint.h>\n" |
| 114 | |
| 115 | class TypeChoice (object): |
| 116 | def __init__(me, tifile): |
| 117 | |
| 118 | ## Load the captured type information. |
| 119 | me.ti = TY.ModuleType('typeinfo') |
| 120 | execfile(opts.typeinfo, me.ti.__dict__) |
| 121 | |
| 122 | ## Build a map of the available types. |
| 123 | tymap = {} |
| 124 | byrank = [] |
| 125 | for tag, bits in me.ti.TYPEINFO: |
| 126 | rank = len(byrank) |
| 127 | tymap[tag] = rank |
| 128 | byrank.append(TYPEMAP[tag](bits, rank)) |
| 129 | |
| 130 | ## First pass: determine a suitable word size. The criteria are (a) |
| 131 | ## there exists another type at least twice as long (so that we can do a |
| 132 | ## single x single -> double multiplication), and (b) operations on a |
| 133 | ## word are efficient (so we'd prefer a plain machine word). We'll start |
| 134 | ## at `int' and work down. Maybe this won't work: there's a plan B. |
| 135 | mpwbits = 0 |
| 136 | i = tymap['uint'] |
| 137 | while not mpwbits and i >= 0: |
| 138 | ibits = byrank[i].bits |
| 139 | for j in xrange(i + 1, len(byrank)): |
| 140 | if byrank[j].bits >= 2*ibits: |
| 141 | mpwbits = ibits |
| 142 | break |
| 143 | |
| 144 | ## If that didn't work, then we'll start with the largest type available |
| 145 | ## and go with half its size. |
| 146 | if not mpwbits: |
| 147 | mpwbits = byrank[-1].bits//2 |
| 148 | |
| 149 | ## Make sure we've not ended up somewhere really silly. |
| 150 | if mpwbits < 16: |
| 151 | raise Exception, "`mpw' type is too small: your C environment is weird" |
| 152 | |
| 153 | ## Now figure out suitable types for `mpw' and `mpd'. |
| 154 | def find_type(bits, what): |
| 155 | for ty in byrank: |
| 156 | if ty.bits >= bits: return ty |
| 157 | raise Exception, \ |
| 158 | "failed to find suitable %d-bit type, for %s" % (bits, what) |
| 159 | |
| 160 | ## Store our decisions. |
| 161 | me.mpwbits = mpwbits |
| 162 | me.mpw = find_type(mpwbits, 'mpw') |
| 163 | me.mpd = find_type(mpwbits*2, 'mpd') |
| 164 | |
| 165 | ###-------------------------------------------------------------------------- |
| 166 | ### Outputting constant multiprecision integers. |
| 167 | |
| 168 | MARGIN = 72 |
| 169 | |
| 170 | def write_preamble(): |
| 171 | stdout.write(""" |
| 172 | #include <mLib/macros.h> |
| 173 | #define MP_(name, flags) \\ |
| 174 | { (/*unconst*/ mpw *)name##__mpw, \\ |
| 175 | (/*unconst*/ mpw *)name##__mpw + N(name##__mpw), \\ |
| 176 | N(name##__mpw), 0, MP_CONST | flags, 0 } |
| 177 | #define ZERO_MP { 0, 0, 0, 0, MP_CONST, 0 } |
| 178 | #define POS_MP(name) MP_(name, 0) |
| 179 | #define NEG_MP(name) MP_(name, MP_NEG) |
| 180 | """) |
| 181 | |
| 182 | def write_limbs(name, x): |
| 183 | if not x: return |
| 184 | stdout.write("\nstatic const mpw %s__mpw[] = {" % name) |
| 185 | sep = '' |
| 186 | pos = MARGIN |
| 187 | if x < 0: x = -x |
| 188 | mask = (1 << TC.mpwbits) - 1 |
| 189 | |
| 190 | while x > 0: |
| 191 | w, x = x & mask, x >> TC.mpwbits |
| 192 | f = TC.mpw.literal(w) |
| 193 | if pos + 2 + len(f) <= MARGIN: |
| 194 | stdout.write(sep + ' ' + f) |
| 195 | else: |
| 196 | pos = 2 |
| 197 | stdout.write(sep + '\n ' + f) |
| 198 | pos += len(f) + 2 |
| 199 | sep = ',' |
| 200 | |
| 201 | stdout.write("\n};\n") |
| 202 | |
| 203 | def mp_body(name, x): |
| 204 | return "%s_MP(%s)" % (x >= 0 and "POS" or "NEG", name) |
| 205 | |
| 206 | ###-------------------------------------------------------------------------- |
| 207 | ### Mode definition machinery. |
| 208 | |
| 209 | MODEMAP = {} |
| 210 | |
| 211 | def defmode(func): |
| 212 | name = func.func_name |
| 213 | if name.startswith('m_'): name = name[2:] |
| 214 | MODEMAP[name] = func |
| 215 | return func |
| 216 | |
| 217 | ###-------------------------------------------------------------------------- |
| 218 | ### The basic types header. |
| 219 | |
| 220 | @defmode |
| 221 | def m_mptypes(): |
| 222 | write_header("mptypes", "mptypes.h") |
| 223 | stdout.write("""\ |
| 224 | #ifndef CATACOMB_MPTYPES_H |
| 225 | #define CATACOMB_MPTYPES_H |
| 226 | """) |
| 227 | |
| 228 | have = set([TC.mpw, TC.mpd]) |
| 229 | for t in have: |
| 230 | stdout.write(t.preamble) |
| 231 | |
| 232 | for label, t, bits in [('mpw', TC.mpw, TC.mpwbits), |
| 233 | ('mpd', TC.mpd, TC.mpwbits*2)]: |
| 234 | LABEL = label.upper() |
| 235 | stdout.write("\n%stypedef %s %s;\n" % (t.typedef_prefix, t.name, label)) |
| 236 | stdout.write("#define %s_BITS %d\n" % (LABEL, bits)) |
| 237 | i = 1 |
| 238 | while 2*i < bits: i *= 2 |
| 239 | stdout.write("#define %s_P2 %d\n" % (LABEL, i)) |
| 240 | stdout.write("#define %s_MAX %s\n" % (LABEL, |
| 241 | t.literal((1 << bits) - 1, "%d"))) |
| 242 | |
| 243 | stdout.write("\n#endif\n") |
| 244 | |
| 245 | ###-------------------------------------------------------------------------- |
| 246 | ### Constant tables. |
| 247 | |
| 248 | @defmode |
| 249 | def m_mplimits_c(): |
| 250 | write_header("mplimits_c", "mplimits.c") |
| 251 | stdout.write('#include "mplimits.h"\n') |
| 252 | write_preamble() |
| 253 | seen = {} |
| 254 | v = [] |
| 255 | def write(x): |
| 256 | if not x or x in seen: return |
| 257 | seen[x] = 1 |
| 258 | write_limbs('limits_%d' % len(v), x) |
| 259 | v.append(x) |
| 260 | for tag, lo, hi in TC.ti.LIMITS: |
| 261 | write(lo) |
| 262 | write(hi) |
| 263 | |
| 264 | stdout.write("\nmp mp_limits[] = {") |
| 265 | i = 0 |
| 266 | sep = "\n " |
| 267 | for x in v: |
| 268 | stdout.write("%s%s_MP(limits_%d)" % (sep, x < 0 and "NEG" or "POS", i)) |
| 269 | i += 1 |
| 270 | sep = ",\n " |
| 271 | stdout.write("\n};\n"); |
| 272 | |
| 273 | @defmode |
| 274 | def m_mplimits_h(): |
| 275 | write_header("mplimits_h", "mplimits.h") |
| 276 | stdout.write("""\ |
| 277 | #ifndef CATACOMB_MPLIMITS_H |
| 278 | #define CATACOMB_MPLIMITS_H |
| 279 | |
| 280 | #ifndef CATACOMB_MP_H |
| 281 | # include "mp.h" |
| 282 | #endif |
| 283 | |
| 284 | extern mp mp_limits[]; |
| 285 | |
| 286 | """) |
| 287 | |
| 288 | seen = { 0: "MP_ZERO" } |
| 289 | slot = [0] |
| 290 | def find(x): |
| 291 | try: |
| 292 | r = seen[x] |
| 293 | except KeyError: |
| 294 | r = seen[x] = '(&mp_limits[%d])' % slot[0] |
| 295 | slot[0] += 1 |
| 296 | return r |
| 297 | for tag, lo, hi in TC.ti.LIMITS: |
| 298 | stdout.write("#define MP_%s_MIN %s\n" % (tag, find(lo))) |
| 299 | stdout.write("#define MP_%s_MAX %s\n" % (tag, find(hi))) |
| 300 | |
| 301 | stdout.write("\n#endif\n") |
| 302 | |
| 303 | ###-------------------------------------------------------------------------- |
| 304 | ### Group tables. |
| 305 | |
| 306 | class GroupTableClass (type): |
| 307 | def __new__(cls, name, supers, dict): |
| 308 | c = type.__new__(cls, name, supers, dict) |
| 309 | try: mode = c.mode |
| 310 | except AttributeError: pass |
| 311 | else: MODEMAP[c.mode] = c.run |
| 312 | return c |
| 313 | |
| 314 | class GroupTable (object): |
| 315 | __metaclass__ = GroupTableClass |
| 316 | keyword = 'group' |
| 317 | slots = [] |
| 318 | def __init__(me): |
| 319 | me.st = st = struct() |
| 320 | st.nextmp = 0 |
| 321 | st.mpmap = { None: 'NO_MP', 0: 'ZERO_MP' } |
| 322 | st.d = {} |
| 323 | me.st.name = None |
| 324 | me._names = [] |
| 325 | me._defs = set() |
| 326 | me._slotmap = dict([(s.name, s) for s in me.slots]) |
| 327 | me._headslots = [s for s in me.slots if s.headline] |
| 328 | def _flush(me): |
| 329 | if me.st.name is None: return |
| 330 | stdout.write("/* --- %s --- */\n" % me.st.name) |
| 331 | for s in me.slots: s.setup(me.st) |
| 332 | stdout.write("\nstatic %s c_%s = {" % (me.data_t, fix_name(me.st.name))) |
| 333 | sep = "\n " |
| 334 | for s in me.slots: |
| 335 | stdout.write(sep) |
| 336 | s.write(me.st) |
| 337 | sep = ",\n " |
| 338 | stdout.write("\n};\n\n") |
| 339 | me.st.d = {} |
| 340 | me.st.name = None |
| 341 | @classmethod |
| 342 | def run(cls, input): |
| 343 | me = cls() |
| 344 | write_header(me.mode, me.filename) |
| 345 | stdout.write('#include "%s"\n' % me.header) |
| 346 | write_preamble() |
| 347 | stdout.write("#define NO_MP { 0, 0, 0, 0, 0, 0 }\n\n") |
| 348 | write_banner("Group data") |
| 349 | stdout.write('\n') |
| 350 | with open(input) as file: |
| 351 | for line in file: |
| 352 | ff = line.split() |
| 353 | if not ff or ff[0].startswith('#'): continue |
| 354 | if ff[0] == 'alias': |
| 355 | if len(ff) != 3: raise Exception, "wrong number of alias arguments" |
| 356 | me._flush() |
| 357 | me._names.append((ff[1], ff[2])) |
| 358 | elif ff[0] == me.keyword: |
| 359 | if len(ff) < 2 or len(ff) > 2 + len(me._headslots): |
| 360 | raise Exception, "bad number of headline arguments" |
| 361 | me._flush() |
| 362 | me.st.name = name = ff[1] |
| 363 | me._defs.add(name) |
| 364 | me._names.append((name, name)) |
| 365 | for f, s in zip(ff[2:], me._headslots): s.set(me.st, f) |
| 366 | elif ff[0] in me._slotmap: |
| 367 | if len(ff) != 2: |
| 368 | raise Exception, "bad number of values for slot `%s'" % ff[0] |
| 369 | me._slotmap[ff[0]].set(me.st, ff[1]) |
| 370 | else: |
| 371 | raise Exception, "unknown keyword `%s'" % ff[0] |
| 372 | me._flush() |
| 373 | write_banner("Main table") |
| 374 | stdout.write("\nconst %s %s[] = {\n" % (me.entry_t, me.tabname)) |
| 375 | for a, n in me._names: |
| 376 | if n not in me._defs: |
| 377 | raise Exception, "alias `%s' refers to unknown group `%s'" % (a, n) |
| 378 | stdout.write(' { "%s", &c_%s },\n' % (a, fix_name(n))) |
| 379 | stdout.write(" { 0, 0 }\n};\n\n") |
| 380 | write_banner("That's all, folks") |
| 381 | |
| 382 | class BaseSlot (object): |
| 383 | def __init__(me, name, headline = False, omitp = None, allowp = None): |
| 384 | me.name = name |
| 385 | me.headline = headline |
| 386 | me._omitp = None |
| 387 | me._allowp = None |
| 388 | def set(me, st, value): |
| 389 | if me._allowp and not me._allowp(st, value): |
| 390 | raise Exception, "slot `%s' not allowed here" % me.name |
| 391 | st.d[me] = value |
| 392 | def setup(me, st): |
| 393 | if me not in st.d and (not me._omitp or not me._omitp(st)): |
| 394 | raise Exception, "missing slot `%s'" % me.name |
| 395 | |
| 396 | class EnumSlot (BaseSlot): |
| 397 | def __init__(me, name, prefix, values, **kw): |
| 398 | super(EnumSlot, me).__init__(name, **kw) |
| 399 | me._values = set(values) |
| 400 | me._prefix = prefix |
| 401 | def set(me, st, value): |
| 402 | if value not in me._values: |
| 403 | raise Exception, "invalid %s value `%s'" % (me.name, value) |
| 404 | super(EnumSlot, me).set(st, value) |
| 405 | def write(me, st): |
| 406 | try: stdout.write('%s_%s' % (me._prefix, st.d[me].upper())) |
| 407 | except KeyError: stdout.write('0') |
| 408 | |
| 409 | class MPSlot (BaseSlot): |
| 410 | def setup(me, st): |
| 411 | v = st.d.get(me) |
| 412 | if v not in st.mpmap: |
| 413 | write_limbs('v%d' % st.nextmp, v) |
| 414 | st.mpmap[v] = mp_body('v%d' % st.nextmp, v) |
| 415 | st.nextmp += 1 |
| 416 | def set(me, st, value): |
| 417 | super(MPSlot, me).set(st, long(value, 0)) |
| 418 | def write(me, st): |
| 419 | stdout.write(st.mpmap[st.d.get(me)]) |
| 420 | |
| 421 | class BinaryGroupTable (GroupTable): |
| 422 | mode = 'bintab' |
| 423 | filename = 'bintab.c' |
| 424 | header = 'bintab.h' |
| 425 | data_t = 'bindata' |
| 426 | entry_t = 'binentry' |
| 427 | tabname = 'bintab' |
| 428 | slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')] |
| 429 | |
| 430 | class EllipticCurveTable (GroupTable): |
| 431 | mode = 'ectab' |
| 432 | filename = 'ectab.c' |
| 433 | header = 'ectab.h' |
| 434 | keyword = 'curve' |
| 435 | data_t = 'ecdata' |
| 436 | entry_t = 'ecentry' |
| 437 | tabname = 'ectab' |
| 438 | slots = [EnumSlot('type', 'FTAG', |
| 439 | ['prime', 'niceprime', 'binpoly', 'binnorm'], |
| 440 | headline = True), |
| 441 | MPSlot('p'), |
| 442 | MPSlot('beta', |
| 443 | allowp = lambda st, _: st.d['type'] == 'binnorm', |
| 444 | omitp = lambda st: st.d['type'] != 'binnorm'), |
| 445 | MPSlot('a'), MPSlot('b'), MPSlot('r'), MPSlot('h'), |
| 446 | MPSlot('gx'), MPSlot('gy')] |
| 447 | |
| 448 | class PrimeGroupTable (GroupTable): |
| 449 | mode = 'ptab' |
| 450 | filename = 'ptab.c' |
| 451 | header = 'ptab.h' |
| 452 | data_t = 'pdata' |
| 453 | entry_t = 'pentry' |
| 454 | tabname = 'ptab' |
| 455 | slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')] |
| 456 | |
| 457 | ###-------------------------------------------------------------------------- |
| 458 | ### Main program. |
| 459 | |
| 460 | op = OP.OptionParser( |
| 461 | description = 'Generate multiprecision integer representations', |
| 462 | usage = 'usage: %prog [-t TYPEINFO] MODE [ARGS ...]', |
| 463 | version = 'Catacomb, version @VERSION@') |
| 464 | for shortopt, longopt, kw in [ |
| 465 | ('-t', '--typeinfo', dict( |
| 466 | action = 'store', metavar = 'PATH', dest = 'typeinfo', |
| 467 | help = 'alternative typeinfo file'))]: |
| 468 | op.add_option(shortopt, longopt, **kw) |
| 469 | op.set_defaults(typeinfo = './typeinfo.py') |
| 470 | opts, args = op.parse_args() |
| 471 | |
| 472 | if len(args) < 1: op.error('missing MODE') |
| 473 | mode = args[0] |
| 474 | |
| 475 | TC = TypeChoice(opts.typeinfo) |
| 476 | |
| 477 | try: modefunc = MODEMAP[mode] |
| 478 | except KeyError: op.error("unknown mode `%s'" % mode) |
| 479 | modefunc(*args[1:]) |
| 480 | |
| 481 | ###----- That's all, folks -------------------------------------------------- |