3 ### Generate multiprecision integer representations
5 ### (c) 2013 Straylight/Edgeware
8 ###----- Licensing notice ---------------------------------------------------
10 ### This file is part of Catacomb.
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.
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.
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.
27 from __future__ import with_statement
33 from sys import stdout
35 ###--------------------------------------------------------------------------
38 def write_header(mode, name):
40 /* -*-c-*- GENERATED by mpgen (%s)
47 def write_banner(text):
48 stdout.write("/*----- %s %s*/\n" % (text, '-' * (66 - len(text))))
50 class struct (object): pass
52 R_IDBAD = RX.compile('[^0-9A-Za-z]')
53 def fix_name(name): return R_IDBAD.sub('_', name)
55 ###--------------------------------------------------------------------------
56 ### Determining the appropriate types.
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
67 class BasicIntType (object):
68 __metaclass__ = IntClass
72 def __init__(me, bits, 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)
80 class UnsignedCharType (BasicIntType):
82 name = 'unsigned char'
84 class UnsignedShortType (BasicIntType):
86 name = 'unsigned short'
88 class UnsignedIntType (BasicIntType):
92 class UnsignedLongType (BasicIntType):
94 name = 'unsigned long'
97 class UnsignedLongLongType (BasicIntType):
99 name = 'unsigned long long'
101 #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 91)
102 # define CATACOMB_GCC_EXTENSION __extension__
104 # define CATACOMB_GCC_EXTENSION
107 typedef_prefix = 'CATACOMB_GCC_EXTENSION '
108 literalfmt = 'CATACOMB_GCC_EXTENSION %sull'
110 class UIntMaxType (BasicIntType):
113 preamble = "\n#include <stdint.h>\n"
115 class TypeChoice (object):
116 def __init__(me, tifile):
118 ## Load the captured type information.
119 me.ti = TY.ModuleType('typeinfo')
120 execfile(opts.typeinfo, me.ti.__dict__)
122 ## Build a map of the available types.
125 for tag, bits in me.ti.TYPEINFO:
128 byrank.append(TYPEMAP[tag](bits, rank))
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.
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:
144 ## If that didn't work, then we'll start with the largest type available
145 ## and go with half its size.
147 mpwbits = byrank[-1].bits//2
149 ## Make sure we've not ended up somewhere really silly.
151 raise Exception, "`mpw' type is too small: your C environment is weird"
153 ## Now figure out suitable types for `mpw' and `mpd'.
154 def find_type(bits, what):
156 if ty.bits >= bits: return ty
158 "failed to find suitable %d-bit type, for %s" % (bits, what)
160 ## Store our decisions.
162 me.mpw = find_type(mpwbits, 'mpw')
163 me.mpd = find_type(mpwbits*2, 'mpd')
165 ###--------------------------------------------------------------------------
166 ### Outputting constant multiprecision integers.
170 def write_preamble():
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)
182 def write_limbs(name, x):
184 stdout.write("\nstatic const mpw %s__mpw[] = {" % name)
188 mask = (1 << TC.mpwbits) - 1
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)
197 stdout.write(sep + '\n ' + f)
201 stdout.write("\n};\n")
203 def mp_body(name, x):
204 return "%s_MP(%s)" % (x >= 0 and "POS" or "NEG", name)
206 ###--------------------------------------------------------------------------
207 ### Mode definition machinery.
212 name = func.func_name
213 if name.startswith('m_'): name = name[2:]
217 ###--------------------------------------------------------------------------
218 ### The basic types header.
222 write_header("mptypes", "mptypes.h")
224 #ifndef CATACOMB_MPTYPES_H
225 #define CATACOMB_MPTYPES_H
228 have = set([TC.mpw, TC.mpd])
230 stdout.write(t.preamble)
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))
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")))
243 stdout.write("\n#endif\n")
245 ###--------------------------------------------------------------------------
250 write_header("mplimits_c", "mplimits.c")
251 stdout.write('#include "mplimits.h"\n')
256 if not x or x in seen: return
258 write_limbs('limits_%d' % len(v), x)
260 for tag, lo, hi in TC.ti.LIMITS:
264 stdout.write("\nmp mp_limits[] = {")
268 stdout.write("%s%s_MP(limits_%d)" % (sep, x < 0 and "NEG" or "POS", i))
271 stdout.write("\n};\n");
275 write_header("mplimits_h", "mplimits.h")
277 #ifndef CATACOMB_MPLIMITS_H
278 #define CATACOMB_MPLIMITS_H
280 #ifndef CATACOMB_MP_H
284 extern mp mp_limits[];
288 seen = { 0: "MP_ZERO" }
294 r = seen[x] = '(&mp_limits[%d])' % slot[0]
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)))
301 stdout.write("\n#endif\n")
303 ###--------------------------------------------------------------------------
306 class GroupTableClass (type):
307 def __new__(cls, name, supers, dict):
308 c = type.__new__(cls, name, supers, dict)
310 except AttributeError: pass
311 else: MODEMAP[c.mode] = c.run
314 class GroupTable (object):
315 __metaclass__ = GroupTableClass
319 me.st = st = struct()
321 st.mpmap = { None: 'NO_MP', 0: 'ZERO_MP' }
326 me._slotmap = dict([(s.name, s) for s in me.slots])
327 me._headslots = [s for s in me.slots if s.headline]
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)))
338 stdout.write("\n};\n\n")
344 write_header(me.mode, me.filename)
345 stdout.write('#include "%s"\n' % me.header)
347 stdout.write("#define NO_MP { 0, 0, 0, 0, 0, 0 }\n\n")
348 write_banner("Group data")
350 with open(input) as file:
353 if not ff or ff[0].startswith('#'): continue
355 if len(ff) != 3: raise Exception, "wrong number of alias arguments"
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"
362 me.st.name = name = ff[1]
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:
368 raise Exception, "bad number of values for slot `%s'" % ff[0]
369 me._slotmap[ff[0]].set(me.st, ff[1])
371 raise Exception, "unknown keyword `%s'" % ff[0]
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")
382 class BaseSlot (object):
383 def __init__(me, name, headline = False, omitp = None, allowp = None):
385 me.headline = headline
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
393 if me not in st.d and (not me._omitp or not me._omitp(st)):
394 raise Exception, "missing slot `%s'" % me.name
396 class EnumSlot (BaseSlot):
397 def __init__(me, name, prefix, values, **kw):
398 super(EnumSlot, me).__init__(name, **kw)
399 me._values = set(values)
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)
406 try: stdout.write('%s_%s' % (me._prefix, st.d[me].upper()))
407 except KeyError: stdout.write('0')
409 class MPSlot (BaseSlot):
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)
416 def set(me, st, value):
417 super(MPSlot, me).set(st, long(value, 0))
419 stdout.write(st.mpmap[st.d.get(me)])
421 class BinaryGroupTable (GroupTable):
423 filename = 'bintab.c'
428 slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]
430 class EllipticCurveTable (GroupTable):
438 slots = [EnumSlot('type', 'FTAG',
439 ['prime', 'niceprime', 'binpoly', 'binnorm'],
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')]
448 class PrimeGroupTable (GroupTable):
455 slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]
457 ###--------------------------------------------------------------------------
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()
472 if len(args) < 1: op.error('missing MODE')
475 TC = TypeChoice(opts.typeinfo)
477 try: modefunc = MODEMAP[mode]
478 except KeyError: op.error("unknown mode `%s'" % mode)
481 ###----- That's all, folks --------------------------------------------------