Commit | Line | Data |
---|---|---|
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
45 | stdout.write("""\ |
46 | /* -*-c-*- GENERATED by mpgen (%s) | |
47 | * | |
48 | * %s | |
49 | */ | |
50 | ||
51 | """ % (mode, name)) | |
52 | ||
53 | def write_banner(text): | |
e7abc7ea | 54 | """Write a separator banner to the output, with header TEXT.""" |
1c3d4cf5 MW |
55 | stdout.write("/*----- %s %s*/\n" % (text, '-' * (66 - len(text)))) |
56 | ||
e7abc7ea MW |
57 | class struct (object): |
58 | """ | |
59 | A struct object exists so that you can set attributes on it. | |
60 | """ | |
61 | pass | |
1c3d4cf5 MW |
62 | |
63 | R_IDBAD = RX.compile('[^0-9A-Za-z]') | |
e7abc7ea MW |
64 | def fix_name(name): |
65 | """Replace non-alphanumeric characters in NAME with underscores.""" | |
66 | return R_IDBAD.sub('_', name) | |
1c3d4cf5 MW |
67 | |
68 | ###-------------------------------------------------------------------------- | |
69 | ### Determining the appropriate types. | |
70 | ||
e7abc7ea | 71 | ## A dictionary mapping type tags to subclasses of BasicIntType. |
1c3d4cf5 MW |
72 | TYPEMAP = {} |
73 | ||
74 | class IntClass (type): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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 | ||
1c3d4cf5 | 188 | def __init__(me, tifile): |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 246 | ## The margin for outputting MP literals. |
1c3d4cf5 MW |
247 | MARGIN = 72 |
248 | ||
249 | def write_preamble(): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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. | |
1c3d4cf5 | 282 | if not x: return |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 306 | ## We're done. Finish off the initializer. |
1c3d4cf5 MW |
307 | stdout.write("\n};\n") |
308 | ||
309 | def mp_body(name, x): | |
e7abc7ea MW |
310 | """ |
311 | Write the body of an `mp' object, for the value NAME. | |
312 | """ | |
1c3d4cf5 MW |
313 | return "%s_MP(%s)" % (x >= 0 and "POS" or "NEG", name) |
314 | ||
315 | ###-------------------------------------------------------------------------- | |
316 | ### Mode definition machinery. | |
317 | ||
e7abc7ea | 318 | ## A dictionary mapping mode names to their handler functions. |
1c3d4cf5 MW |
319 | MODEMAP = {} |
320 | ||
321 | def defmode(func): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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(): | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
361 | write_header("mptypes", "mptypes.h") |
362 | stdout.write("""\ | |
363 | #ifndef CATACOMB_MPTYPES_H | |
364 | #define CATACOMB_MPTYPES_H | |
365 | """) | |
366 | ||
e7abc7ea | 367 | ## Write any additional premable for the types we've selected. |
1c3d4cf5 MW |
368 | have = set([TC.mpw, TC.mpd]) |
369 | for t in have: | |
370 | stdout.write(t.preamble) | |
371 | ||
e7abc7ea | 372 | ## Emit the types and constants. |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 384 | ## Done. |
1c3d4cf5 MW |
385 | stdout.write("\n#endif\n") |
386 | ||
387 | ###-------------------------------------------------------------------------- | |
388 | ### Constant tables. | |
389 | ||
390 | @defmode | |
391 | def m_mplimits_c(): | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
402 | write_header("mplimits_c", "mplimits.c") |
403 | stdout.write('#include "mplimits.h"\n') | |
404 | write_preamble() | |
e7abc7ea MW |
405 | |
406 | ## Write out limbs for limits as we come across them. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 418 | ## Write the main vector. |
1c3d4cf5 MW |
419 | stdout.write("\nmp mp_limits[] = {") |
420 | i = 0 | |
421 | sep = "\n " | |
422 | for x in v: | |
c7a23204 | 423 | stdout.write("%s%s_MP(limits_%d)" % (sep, x < 0 and "NEG" or "POS", i)) |
1c3d4cf5 MW |
424 | i += 1 |
425 | sep = ",\n " | |
426 | stdout.write("\n};\n"); | |
427 | ||
428 | @defmode | |
429 | def m_mplimits_h(): | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 466 | ## All done. |
1c3d4cf5 MW |
467 | stdout.write("\n#endif\n") |
468 | ||
469 | ###-------------------------------------------------------------------------- | |
470 | ### Group tables. | |
471 | ||
472 | class GroupTableClass (type): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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 | ||
1c3d4cf5 | 571 | __metaclass__ = GroupTableClass |
e7abc7ea MW |
572 | |
573 | ## Default values. | |
1c3d4cf5 MW |
574 | keyword = 'group' |
575 | slots = [] | |
e7abc7ea | 576 | |
1c3d4cf5 | 577 | def __init__(me): |
e7abc7ea MW |
578 | """ |
579 | Initialize a group table object. | |
580 | """ | |
581 | ||
1c3d4cf5 MW |
582 | me.st = st = struct() |
583 | st.nextmp = 0 | |
584 | st.mpmap = { None: 'NO_MP', 0: 'ZERO_MP' } | |
585 | st.d = {} | |
3ece2113 | 586 | st.name = None |
1c3d4cf5 MW |
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] | |
e7abc7ea | 591 | |
1c3d4cf5 | 592 | def _flush(me): |
e7abc7ea MW |
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. | |
1c3d4cf5 | 598 | if me.st.name is None: return |
e7abc7ea MW |
599 | |
600 | ## Start emitting the object. | |
1c3d4cf5 | 601 | stdout.write("/* --- %s --- */\n" % me.st.name) |
e7abc7ea MW |
602 | |
603 | ## Get the various slots to compute themselves. | |
1c3d4cf5 | 604 | for s in me.slots: s.setup(me.st) |
e7abc7ea MW |
605 | |
606 | ## Write the initializer. | |
1c3d4cf5 MW |
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") | |
e7abc7ea MW |
614 | |
615 | ## Clear the state for the next stanza. | |
1c3d4cf5 MW |
616 | me.st.d = {} |
617 | me.st.name = None | |
e7abc7ea | 618 | |
1c3d4cf5 MW |
619 | @classmethod |
620 | def run(cls, input): | |
e7abc7ea MW |
621 | """ |
622 | Main output for a group table. Reads the file INPUT. | |
623 | """ | |
624 | ||
625 | ## Make an object for us to work on. | |
1c3d4cf5 | 626 | me = cls() |
e7abc7ea MW |
627 | |
628 | ## Write the output preamble. | |
1c3d4cf5 MW |
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") | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
636 | write_banner("Group data") |
637 | stdout.write('\n') | |
638 | with open(input) as file: | |
639 | for line in file: | |
e7abc7ea MW |
640 | |
641 | ## Parse the line into fields. | |
1c3d4cf5 MW |
642 | ff = line.split() |
643 | if not ff or ff[0].startswith('#'): continue | |
e7abc7ea | 644 | |
1c3d4cf5 | 645 | if ff[0] == 'alias': |
e7abc7ea | 646 | ## An alias. Just remember this. |
1c3d4cf5 MW |
647 | if len(ff) != 3: raise Exception, "wrong number of alias arguments" |
648 | me._flush() | |
649 | me._names.append((ff[1], ff[2])) | |
e7abc7ea | 650 | |
1c3d4cf5 | 651 | elif ff[0] == me.keyword: |
e7abc7ea MW |
652 | ## A headline for a new group. |
653 | ||
654 | ## Check the headline syntax. Headline slots may be set here, or | |
655 | ## later by name. | |
1c3d4cf5 MW |
656 | if len(ff) < 2 or len(ff) > 2 + len(me._headslots): |
657 | raise Exception, "bad number of headline arguments" | |
e7abc7ea MW |
658 | |
659 | ## Flush out the previous stanza. | |
1c3d4cf5 | 660 | me._flush() |
e7abc7ea MW |
661 | |
662 | ## Remember the new stanza's name, and add it to the list. | |
1c3d4cf5 MW |
663 | me.st.name = name = ff[1] |
664 | me._defs.add(name) | |
665 | me._names.append((name, name)) | |
e7abc7ea MW |
666 | |
667 | ## Set headline slots from the remaining headline words. | |
1c3d4cf5 | 668 | for f, s in zip(ff[2:], me._headslots): s.set(me.st, f) |
e7abc7ea | 669 | |
1c3d4cf5 | 670 | elif ff[0] in me._slotmap: |
e7abc7ea MW |
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" | |
1c3d4cf5 MW |
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]) | |
e7abc7ea | 677 | |
1c3d4cf5 | 678 | else: |
e7abc7ea | 679 | ## Something incomprehensible. |
1c3d4cf5 | 680 | raise Exception, "unknown keyword `%s'" % ff[0] |
e7abc7ea MW |
681 | |
682 | ## End of the input. Write out the final stanza. | |
1c3d4cf5 | 683 | me._flush() |
e7abc7ea MW |
684 | |
685 | ## Now for the name-to-data mapping. | |
1c3d4cf5 MW |
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") | |
e7abc7ea MW |
693 | |
694 | ## We're done. | |
1c3d4cf5 MW |
695 | write_banner("That's all, folks") |
696 | ||
697 | class BaseSlot (object): | |
e7abc7ea MW |
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 | ||
1c3d4cf5 | 736 | def __init__(me, name, headline = False, omitp = None, allowp = None): |
e7abc7ea MW |
737 | """ |
738 | Initialize a new slot object, setting the necessary attributes. | |
739 | """ | |
1c3d4cf5 MW |
740 | me.name = name |
741 | me.headline = headline | |
18533217 MW |
742 | me._omitp = omitp |
743 | me._allowp = allowp | |
e7abc7ea | 744 | |
1c3d4cf5 | 745 | def set(me, st, value): |
e7abc7ea MW |
746 | """ |
747 | Store a VALUE for the slot. | |
748 | """ | |
1c3d4cf5 MW |
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 | |
e7abc7ea | 752 | |
1c3d4cf5 | 753 | def setup(me, st): |
e7abc7ea MW |
754 | """ |
755 | Prepare the slot for output, checking its value and so on. | |
756 | """ | |
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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 | ||
1c3d4cf5 | 768 | def __init__(me, name, prefix, values, **kw): |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
775 | super(EnumSlot, me).__init__(name, **kw) |
776 | me._values = set(values) | |
777 | me._prefix = prefix | |
e7abc7ea | 778 | |
1c3d4cf5 | 779 | def set(me, st, value): |
e7abc7ea MW |
780 | """ |
781 | Check that the VALUE is one of the ones we know. | |
782 | """ | |
1c3d4cf5 MW |
783 | if value not in me._values: |
784 | raise Exception, "invalid %s value `%s'" % (me.name, value) | |
785 | super(EnumSlot, me).set(st, value) | |
e7abc7ea | 786 | |
1c3d4cf5 | 787 | def write(me, st): |
e7abc7ea MW |
788 | """ |
789 | Convert the slot value to the C constant name. | |
790 | """ | |
1c3d4cf5 MW |
791 | try: stdout.write('%s_%s' % (me._prefix, st.d[me].upper())) |
792 | except KeyError: stdout.write('0') | |
793 | ||
794 | class MPSlot (BaseSlot): | |
e7abc7ea MW |
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 | ||
3ece2113 | 802 | def set(me, st, value): |
e7abc7ea MW |
803 | """ |
804 | Set a value; convert it to a Python integer. | |
805 | """ | |
3ece2113 | 806 | super(MPSlot, me).set(st, long(value, 0)) |
e7abc7ea | 807 | |
1c3d4cf5 | 808 | def setup(me, st): |
e7abc7ea MW |
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 | """ | |
18533217 | 815 | super(MPSlot, me).setup(st) |
1c3d4cf5 MW |
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 | |
e7abc7ea | 821 | |
1c3d4cf5 | 822 | def write(me, st): |
e7abc7ea MW |
823 | """ |
824 | Write out an `mp' initializer for the slot. | |
825 | """ | |
1c3d4cf5 MW |
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' | |
18533217 MW |
845 | _typeslot = EnumSlot('type', 'FTAG', |
846 | ['prime', 'niceprime', 'binpoly', 'binnorm'], | |
847 | headline = True) | |
848 | slots = [_typeslot, | |
1c3d4cf5 MW |
849 | MPSlot('p'), |
850 | MPSlot('beta', | |
18533217 MW |
851 | allowp = lambda st, _: |
852 | st.d[EllipticCurveTable._typeslot] == 'binnorm', | |
853 | omitp = lambda st: | |
854 | st.d[EllipticCurveTable._typeslot] != 'binnorm'), | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 882 | ## Parse the positional arguments. |
1c3d4cf5 MW |
883 | if len(args) < 1: op.error('missing MODE') |
884 | mode = args[0] | |
885 | ||
e7abc7ea | 886 | ## Establish the choice of low-level C types. |
1c3d4cf5 MW |
887 | TC = TypeChoice(opts.typeinfo) |
888 | ||
e7abc7ea | 889 | ## Find the selected mode, and invoke the appropriate handler. |
1c3d4cf5 MW |
890 | try: modefunc = MODEMAP[mode] |
891 | except KeyError: op.error("unknown mode `%s'" % mode) | |
892 | modefunc(*args[1:]) | |
893 | ||
894 | ###----- That's all, folks -------------------------------------------------- |