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
31 import sys as SYS; stdout = SYS.stdout
34 ###--------------------------------------------------------------------------
37 def write_header(mode, name):
39 Write a C-language file header.
41 The header comment identifies the processing MODE, and the NAME of the
45 /* -*-c-*- GENERATED by mpgen (%s)
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))))
56 class struct (object):
58 A struct object exists so that you can set attributes on it.
62 R_IDBAD = RX.compile('[^0-9A-Za-z]')
64 """Replace non-alphanumeric characters in NAME with underscores."""
65 return R_IDBAD.sub('_', name)
67 if SYS.version_info >= (3,):
68 def func_name(func): return func.__name__
72 def func_name(func): return func.func_name
74 def with_metaclass(meta, *supers):
75 return meta('#<anonymous base %s>' % meta.__name__,
76 supers or (object,), dict())
79 with open(file) as f: text = f.read()
80 code = compile(text, file, 'exec')
83 ###--------------------------------------------------------------------------
84 ### Determining the appropriate types.
86 ## A dictionary mapping type tags to subclasses of BasicIntType.
89 class IntClass (type):
91 The IntClass is a metaclass for integer-type classes.
93 It associates the type class with its tag in the `TYPEMAP' dictionary.
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
101 class BasicIntType (with_metaclass(IntClass)):
103 A base class for integer-type classes, providing defaults and protocol.
105 Integer-type classes have the following attributes and methods.
107 preamble Some code to be emitted to a header file to make use
108 of the type. Defaults to the empty string.
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.
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'.
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.
123 Instances also carry additional attributes.
125 bits The width of the integer type, in bits.
127 rank An integer giving the conversion rank of the type.
128 Higher values generally denote wider types.
130 litwd The width of a literal of the type, in characters.
132 __metaclass__ = IntClass
136 def __init__(me, bits, 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)
144 class UnsignedCharType (BasicIntType):
146 name = 'unsigned char'
148 class UnsignedShortType (BasicIntType):
150 name = 'unsigned short'
152 class UnsignedIntType (BasicIntType):
154 name = 'unsigned int'
156 class UnsignedLongType (BasicIntType):
158 name = 'unsigned long'
161 class UnsignedLongLongType (BasicIntType):
163 name = 'unsigned long long'
165 #if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 91)
166 # define CATACOMB_GCC_EXTENSION __extension__
168 # define CATACOMB_GCC_EXTENSION
171 typedef_prefix = 'CATACOMB_GCC_EXTENSION '
172 literalfmt = 'CATACOMB_GCC_EXTENSION %sull'
174 class UIntMaxType (BasicIntType):
177 preamble = "\n#include <stdint.h>\n"
179 class TypeChoice (object):
181 A TypeChoice object selects C integer types for multiprecision integers.
183 It exports its decisions as attributes:
185 mpwbits The width of an `mpw', in bits.
187 mpw The integer type for single-precision values.
189 mpd The integer type for double-precision values.
191 ti An object bearing raw information about the available
192 integer types, as follows...
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.
198 LIMITS A list of items (TAG, LO, HI) describing the ranges
199 of integer types, for constructing the `mplimits'
203 def __init__(me, tifile):
205 Read the definitions from TIFILE, and select types appropriately.
207 The TIFILE is a tiny fragment of Python code which should set `TYPEINFO'
208 and `LIMITS' in its global namespace.
211 ## Load the captured type information.
212 me.ti = TY.ModuleType('typeinfo')
213 load(opts.typeinfo, me.ti.__dict__)
215 ## Build a map of the available types.
218 for tag, bits in me.ti.TYPEINFO:
221 byrank.append(TYPEMAP[tag](bits, rank))
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.
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:
237 ## If that didn't work, then we'll start with the largest type available
238 ## and go with half its size.
240 mpwbits = byrank[-1].bits//2
242 ## Make sure we've not ended up somewhere really silly.
244 raise Exception("`mpw' type is too small: your C environment is weird")
246 ## Now figure out suitable types for `mpw' and `mpd'.
247 def find_type(bits, what):
249 if ty.bits >= bits: return ty
251 ("failed to find suitable %d-bit type, for %s" % (bits, what))
253 ## Store our decisions.
255 me.mpw = find_type(mpwbits, 'mpw')
256 me.mpd = find_type(mpwbits*2, 'mpd')
258 ###--------------------------------------------------------------------------
259 ### Outputting constant multiprecision integers.
261 ## The margin for outputting MP literals.
264 def write_preamble():
266 Write a preamble for files containing multiprecision literals.
268 We define a number of macros for use by the rest of the code:
270 ZERO_MP An `mp' initializer denoting the value zero.
272 POS_MP(NAME) Constructs an `mp' initializer denoting a positive
273 integer whose limbs were emitted with the given
276 NEG_MP(NAME) Constructs an `mp' initializer denoting a negative
277 integer whose limbs were emitted with the given
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)
291 def write_limbs(name, x):
293 Write the limbs of the value X, with the given NAME.
296 ## We don't need to do anything special for zero.
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)
306 mask = (1 << TC.mpwbits) - 1
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.
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)
317 stdout.write(sep + '\n ' + f)
321 ## We're done. Finish off the initializer.
322 stdout.write("\n};\n")
324 def mp_body(name, x):
326 Write the body of an `mp' object, for the value NAME.
328 return "%s_MP(%s)" % (x >= 0 and "POS" or "NEG", name)
330 ###--------------------------------------------------------------------------
331 ### Mode definition machinery.
333 ## A dictionary mapping mode names to their handler functions.
338 Function decorator: associate the function with the name of a mode.
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
345 name = func_name(func)
346 if name.startswith('m_'): name = name[2:]
350 ###--------------------------------------------------------------------------
351 ### The basic types header.
356 Write the `mptypes.h' header.
358 This establishes the following types.
360 mpw An integer type for single-precision values.
362 mpd An integer type for double-precision values.
364 And, for t being each of `w' or `d', the following constants:
366 MPt_BITS The width of the type, in bits.
368 MPt_P2 The smallest integer k such that 2^k is not less than
369 MPt_BITS. (This is used for binary searches.)
371 MPt_MAX The largest value which may be stored in an object of
375 ## Write the preamble.
376 write_header("mptypes", "mptypes.h")
378 #ifndef CATACOMB_MPTYPES_H
379 #define CATACOMB_MPTYPES_H
382 ## Write any additional premable for the types we've selected.
383 have = set([TC.mpw, TC.mpd])
385 stdout.write(t.preamble)
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))
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")))
400 stdout.write("\n#endif\n")
402 ###--------------------------------------------------------------------------
408 Write the `mplimits.c' source file.
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
416 ## Write the preamble.
417 write_header("mplimits_c", "mplimits.c")
418 stdout.write('#include "mplimits.h"\n')
421 ## Write out limbs for limits as we come across them.
425 if not x or x in seen: return
427 write_limbs('limits_%d' % len(v), x)
429 for tag, lo, hi in TC.ti.LIMITS:
433 ## Write the main vector.
434 stdout.write("\nmp mp_limits[] = {")
438 stdout.write("%s%s_MP(limits_%d)" % (sep, x < 0 and "NEG" or "POS", i))
441 stdout.write("\n};\n");
446 Write the `mplimits.h' source file.
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.
452 ## Write the preamble.
453 write_header("mplimits_h", "mplimits.h")
455 #ifndef CATACOMB_MPLIMITS_H
456 #define CATACOMB_MPLIMITS_H
458 #ifndef CATACOMB_MP_H
462 extern mp mp_limits[];
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" }
474 r = seen[x] = '(&mp_limits[%d])' % slot[0]
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)))
482 stdout.write("\n#endif\n")
484 ###--------------------------------------------------------------------------
487 class GroupTableClass (type):
489 Metaclass for group tables, which registers them in the `MODEMAP'.
491 Such a class must define an attribute `mode' giving the mode name, and a
492 class method `run' which writes the necessary output.
494 def __new__(cls, name, supers, dict):
495 c = type.__new__(cls, name, supers, dict)
497 except AttributeError: pass
498 else: MODEMAP[c.mode] = c.run
501 class GroupTable (with_metaclass(GroupTableClass)):
503 Base class for group tables objects.
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.
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
515 KEYWORD NAME [HEAD-VALUE ...]
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.
523 Subclasses must define the following attributes.
525 data_t The name of the type for describing a particular
528 entry_t The name of the type which associates a name with
529 some group data; this will be defined as
531 typedef struct ENTRY_T {
538 filename The filename, typically `SOMETHING.c', to put in the
541 header The header file to include, so as to establish the
542 necessary types and other definitions.
544 keyword The keyword beginning a new definition in the input
545 file. The default is `group'.
547 mode The mode name, used to invoke this kind of table
548 operation (used by GroupTableClass).
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
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.
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.
565 mpmap A dictionary mapping values (integers, or `None') to
566 C initializers (typically, actually, macro
569 name The name of the group currently being parsed.
571 nextmp Index for the next `mp' object to be written.
574 ## Additional attributes, for internal use:
576 ## _defs A set of known names for groups.
578 ## _headslots A list of slots filled in from the headline.
580 ## _names A list of pairs (ALIAS, DATA) mapping alias names to
581 ## the actual group data.
583 ## _slotmap A dictionary mapping slot names to their
592 Initialize a group table object.
595 me.st = st = struct()
597 st.mpmap = { None: 'NO_MP', 0: 'ZERO_MP' }
602 me._slotmap = dict([(s.name, s) for s in me.slots])
603 me._headslots = [s for s in me.slots if s.headline]
607 Write out the data for a group once we've detected the end of its stanza.
610 ## If there's no current stanza, then do nothing.
611 if me.st.name is None: return
613 ## Start emitting the object.
614 stdout.write("/* --- %s --- */\n" % me.st.name)
616 ## Get the various slots to compute themselves.
617 for s in me.slots: s.setup(me.st)
619 ## Write the initializer.
620 stdout.write("\nstatic %s c_%s = {" % (me.data_t, fix_name(me.st.name)))
626 stdout.write("\n};\n\n")
628 ## Clear the state for the next stanza.
635 Main output for a group table. Reads the file INPUT.
638 ## Make an object for us to work on.
641 ## Write the output preamble.
642 write_header(me.mode, me.filename)
643 stdout.write('#include "%s"\n' % me.header)
645 stdout.write("#define NO_MP { 0, 0, 0, 0, 0, 0 }\n\n")
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")
651 with open(input) as file:
654 ## Parse the line into fields.
656 if not ff or ff[0].startswith('#'): continue
659 ## An alias. Just remember this.
660 if len(ff) != 3: raise Exception("wrong number of alias arguments")
662 me._names.append((ff[1], ff[2]))
664 elif ff[0] == me.keyword:
665 ## A headline for a new group.
667 ## Check the headline syntax. Headline slots may be set here, or
669 if len(ff) < 2 or len(ff) > 2 + len(me._headslots):
670 raise Exception("bad number of headline arguments")
672 ## Flush out the previous stanza.
675 ## Remember the new stanza's name, and add it to the list.
676 me.st.name = name = ff[1]
678 me._names.append((name, name))
680 ## Set headline slots from the remaining headline words.
681 for f, s in zip(ff[2:], me._headslots): s.set(me.st, f)
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")
688 raise Exception("bad number of values for slot `%s'" % ff[0])
689 me._slotmap[ff[0]].set(me.st, ff[1])
692 ## Something incomprehensible.
693 raise Exception("unknown keyword `%s'" % ff[0])
695 ## End of the input. Write out the final stanza.
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")
708 write_banner("That's all, folks")
710 class BaseSlot (object):
712 Base class for slot types.
714 The slot protocol works as follows. Throughout, ST is a state object as
715 maintained by a GroupTable.
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
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
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.
738 write(ST) Write an initializer for the slot to standard
739 output. There is no default.
741 The following attributes are exported.
743 headline A flag: can the slot be initialized from the stanza
746 name The slot's name.
749 def __init__(me, name, headline = False, omitp = None, allowp = None):
751 Initialize a new slot object, setting the necessary attributes.
754 me.headline = headline
758 def set(me, st, value):
760 Store a VALUE for the slot.
762 if me._allowp and not me._allowp(st, value):
763 raise Exception("slot `%s' not allowed here" % me.name)
768 Prepare the slot for output, checking its value and so on.
770 if me not in st.d and (not me._omitp or not me._omitp(st)):
771 raise Exception("missing slot `%s'" % me.name)
773 class EnumSlot (BaseSlot):
775 An EnumSlot object represents a slot which can contain one of a number of
778 An omitted value is written as a literal `0'.
781 def __init__(me, name, prefix, values, **kw):
783 Initialize an EnumSlot object.
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.
788 super(EnumSlot, me).__init__(name, **kw)
789 me._values = set(values)
792 def set(me, st, value):
794 Check that the VALUE is one of the ones we know.
796 if value not in me._values:
797 raise Exception("invalid %s value `%s'" % (me.name, value))
798 super(EnumSlot, me).set(st, value)
802 Convert the slot value to the C constant name.
804 try: stdout.write('%s_%s' % (me._prefix, st.d[me].upper()))
805 except KeyError: stdout.write('0')
807 class MPSlot (BaseSlot):
809 An MPSlot object represents a slot which can contain a multiprecision
812 An omitted value is written as a invalid `mp' object.
815 def set(me, st, value):
817 Set a value; convert it to a Python integer.
819 super(MPSlot, me).set(st, long(value, 0))
823 Prepare to write the slot.
825 If this is a new integer, then write out a limb vector. Names for the
826 limbs are generated unimaginitively, using a counter.
828 super(MPSlot, me).setup(st)
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)
837 Write out an `mp' initializer for the slot.
839 stdout.write(st.mpmap[st.d.get(me)])
841 class BinaryGroupTable (GroupTable):
843 filename = 'bintab.c'
848 slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]
850 class EllipticCurveTable (GroupTable):
858 _typeslot = EnumSlot('type', 'FTAG',
859 ['prime', 'niceprime', 'binpoly', 'binnorm'],
864 allowp = lambda st, _:
865 st.d[EllipticCurveTable._typeslot] == 'binnorm',
867 st.d[EllipticCurveTable._typeslot] != 'binnorm'),
868 MPSlot('a'), MPSlot('b'), MPSlot('r'), MPSlot('h'),
869 MPSlot('gx'), MPSlot('gy')]
871 class PrimeGroupTable (GroupTable):
878 slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]
880 ###--------------------------------------------------------------------------
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()
895 ## Parse the positional arguments.
896 if len(args) < 1: op.error('missing MODE')
899 ## Establish the choice of low-level C types.
900 TC = TypeChoice(opts.typeinfo)
902 ## Find the selected mode, and invoke the appropriate handler.
903 try: modefunc = MODEMAP[mode]
904 except KeyError: op.error("unknown mode `%s'" % mode)
907 ###----- That's all, folks --------------------------------------------------