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 | |
b8dc834f | 31 | import sys as SYS; stdout = SYS.stdout |
1c3d4cf5 MW |
32 | import types as TY |
33 | ||
1c3d4cf5 MW |
34 | ###-------------------------------------------------------------------------- |
35 | ### Random utilities. | |
36 | ||
37 | def write_header(mode, name): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
44 | stdout.write("""\ |
45 | /* -*-c-*- GENERATED by mpgen (%s) | |
46 | * | |
47 | * %s | |
48 | */ | |
49 | ||
50 | """ % (mode, name)) | |
51 | ||
52 | def write_banner(text): | |
e7abc7ea | 53 | """Write a separator banner to the output, with header TEXT.""" |
1c3d4cf5 MW |
54 | stdout.write("/*----- %s %s*/\n" % (text, '-' * (66 - len(text)))) |
55 | ||
e7abc7ea MW |
56 | class struct (object): |
57 | """ | |
58 | A struct object exists so that you can set attributes on it. | |
59 | """ | |
60 | pass | |
1c3d4cf5 MW |
61 | |
62 | R_IDBAD = RX.compile('[^0-9A-Za-z]') | |
e7abc7ea MW |
63 | def fix_name(name): |
64 | """Replace non-alphanumeric characters in NAME with underscores.""" | |
65 | return R_IDBAD.sub('_', name) | |
1c3d4cf5 | 66 | |
b8dc834f MW |
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 | ||
1c3d4cf5 MW |
83 | ###-------------------------------------------------------------------------- |
84 | ### Determining the appropriate types. | |
85 | ||
e7abc7ea | 86 | ## A dictionary mapping type tags to subclasses of BasicIntType. |
1c3d4cf5 MW |
87 | TYPEMAP = {} |
88 | ||
89 | class IntClass (type): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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 | ||
b8dc834f | 101 | class BasicIntType (with_metaclass(IntClass)): |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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 | ||
1c3d4cf5 | 203 | def __init__(me, tifile): |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
210 | |
211 | ## Load the captured type information. | |
212 | me.ti = TY.ModuleType('typeinfo') | |
b8dc834f | 213 | load(opts.typeinfo, me.ti.__dict__) |
1c3d4cf5 MW |
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: | |
b8dc834f | 244 | raise Exception("`mpw' type is too small: your C environment is weird") |
1c3d4cf5 MW |
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 | |
b8dc834f MW |
250 | raise Exception \ |
251 | ("failed to find suitable %d-bit type, for %s" % (bits, what)) | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 261 | ## The margin for outputting MP literals. |
1c3d4cf5 MW |
262 | MARGIN = 72 |
263 | ||
264 | def write_preamble(): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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): | |
e7abc7ea MW |
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. | |
1c3d4cf5 | 297 | if not x: return |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 321 | ## We're done. Finish off the initializer. |
1c3d4cf5 MW |
322 | stdout.write("\n};\n") |
323 | ||
324 | def mp_body(name, x): | |
e7abc7ea MW |
325 | """ |
326 | Write the body of an `mp' object, for the value NAME. | |
327 | """ | |
1c3d4cf5 MW |
328 | return "%s_MP(%s)" % (x >= 0 and "POS" or "NEG", name) |
329 | ||
330 | ###-------------------------------------------------------------------------- | |
331 | ### Mode definition machinery. | |
332 | ||
e7abc7ea | 333 | ## A dictionary mapping mode names to their handler functions. |
1c3d4cf5 MW |
334 | MODEMAP = {} |
335 | ||
336 | def defmode(func): | |
e7abc7ea MW |
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 | """ | |
b8dc834f | 345 | name = func_name(func) |
1c3d4cf5 MW |
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(): | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
376 | write_header("mptypes", "mptypes.h") |
377 | stdout.write("""\ | |
378 | #ifndef CATACOMB_MPTYPES_H | |
379 | #define CATACOMB_MPTYPES_H | |
380 | """) | |
381 | ||
e7abc7ea | 382 | ## Write any additional premable for the types we've selected. |
1c3d4cf5 MW |
383 | have = set([TC.mpw, TC.mpd]) |
384 | for t in have: | |
385 | stdout.write(t.preamble) | |
386 | ||
e7abc7ea | 387 | ## Emit the types and constants. |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 399 | ## Done. |
1c3d4cf5 MW |
400 | stdout.write("\n#endif\n") |
401 | ||
402 | ###-------------------------------------------------------------------------- | |
403 | ### Constant tables. | |
404 | ||
405 | @defmode | |
406 | def m_mplimits_c(): | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
417 | write_header("mplimits_c", "mplimits.c") |
418 | stdout.write('#include "mplimits.h"\n') | |
419 | write_preamble() | |
e7abc7ea MW |
420 | |
421 | ## Write out limbs for limits as we come across them. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 433 | ## Write the main vector. |
1c3d4cf5 MW |
434 | stdout.write("\nmp mp_limits[] = {") |
435 | i = 0 | |
436 | sep = "\n " | |
437 | for x in v: | |
c7a23204 | 438 | stdout.write("%s%s_MP(limits_%d)" % (sep, x < 0 and "NEG" or "POS", i)) |
1c3d4cf5 MW |
439 | i += 1 |
440 | sep = ",\n " | |
441 | stdout.write("\n};\n"); | |
442 | ||
443 | @defmode | |
444 | def m_mplimits_h(): | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 481 | ## All done. |
1c3d4cf5 MW |
482 | stdout.write("\n#endif\n") |
483 | ||
484 | ###-------------------------------------------------------------------------- | |
485 | ### Group tables. | |
486 | ||
487 | class GroupTableClass (type): | |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
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 | ||
b8dc834f | 501 | class GroupTable (with_metaclass(GroupTableClass)): |
e7abc7ea MW |
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 | ||
e7abc7ea | 586 | ## Default values. |
1c3d4cf5 MW |
587 | keyword = 'group' |
588 | slots = [] | |
e7abc7ea | 589 | |
1c3d4cf5 | 590 | def __init__(me): |
e7abc7ea MW |
591 | """ |
592 | Initialize a group table object. | |
593 | """ | |
594 | ||
1c3d4cf5 MW |
595 | me.st = st = struct() |
596 | st.nextmp = 0 | |
597 | st.mpmap = { None: 'NO_MP', 0: 'ZERO_MP' } | |
598 | st.d = {} | |
3ece2113 | 599 | st.name = None |
1c3d4cf5 MW |
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] | |
e7abc7ea | 604 | |
1c3d4cf5 | 605 | def _flush(me): |
e7abc7ea MW |
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. | |
1c3d4cf5 | 611 | if me.st.name is None: return |
e7abc7ea MW |
612 | |
613 | ## Start emitting the object. | |
1c3d4cf5 | 614 | stdout.write("/* --- %s --- */\n" % me.st.name) |
e7abc7ea MW |
615 | |
616 | ## Get the various slots to compute themselves. | |
1c3d4cf5 | 617 | for s in me.slots: s.setup(me.st) |
e7abc7ea MW |
618 | |
619 | ## Write the initializer. | |
1c3d4cf5 MW |
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") | |
e7abc7ea MW |
627 | |
628 | ## Clear the state for the next stanza. | |
1c3d4cf5 MW |
629 | me.st.d = {} |
630 | me.st.name = None | |
e7abc7ea | 631 | |
1c3d4cf5 MW |
632 | @classmethod |
633 | def run(cls, input): | |
e7abc7ea MW |
634 | """ |
635 | Main output for a group table. Reads the file INPUT. | |
636 | """ | |
637 | ||
638 | ## Make an object for us to work on. | |
1c3d4cf5 | 639 | me = cls() |
e7abc7ea MW |
640 | |
641 | ## Write the output preamble. | |
1c3d4cf5 MW |
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") | |
e7abc7ea MW |
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. | |
1c3d4cf5 MW |
649 | write_banner("Group data") |
650 | stdout.write('\n') | |
651 | with open(input) as file: | |
652 | for line in file: | |
e7abc7ea MW |
653 | |
654 | ## Parse the line into fields. | |
1c3d4cf5 MW |
655 | ff = line.split() |
656 | if not ff or ff[0].startswith('#'): continue | |
e7abc7ea | 657 | |
1c3d4cf5 | 658 | if ff[0] == 'alias': |
e7abc7ea | 659 | ## An alias. Just remember this. |
b8dc834f | 660 | if len(ff) != 3: raise Exception("wrong number of alias arguments") |
1c3d4cf5 MW |
661 | me._flush() |
662 | me._names.append((ff[1], ff[2])) | |
e7abc7ea | 663 | |
1c3d4cf5 | 664 | elif ff[0] == me.keyword: |
e7abc7ea MW |
665 | ## A headline for a new group. |
666 | ||
667 | ## Check the headline syntax. Headline slots may be set here, or | |
668 | ## later by name. | |
1c3d4cf5 | 669 | if len(ff) < 2 or len(ff) > 2 + len(me._headslots): |
b8dc834f | 670 | raise Exception("bad number of headline arguments") |
e7abc7ea MW |
671 | |
672 | ## Flush out the previous stanza. | |
1c3d4cf5 | 673 | me._flush() |
e7abc7ea MW |
674 | |
675 | ## Remember the new stanza's name, and add it to the list. | |
1c3d4cf5 MW |
676 | me.st.name = name = ff[1] |
677 | me._defs.add(name) | |
678 | me._names.append((name, name)) | |
e7abc7ea MW |
679 | |
680 | ## Set headline slots from the remaining headline words. | |
1c3d4cf5 | 681 | for f, s in zip(ff[2:], me._headslots): s.set(me.st, f) |
e7abc7ea | 682 | |
1c3d4cf5 | 683 | elif ff[0] in me._slotmap: |
e7abc7ea MW |
684 | ## A slot assignment. Get the slot to store a value. |
685 | if me.st.name is None: | |
b8dc834f | 686 | raise Exception("no group currently being defined") |
1c3d4cf5 | 687 | if len(ff) != 2: |
b8dc834f | 688 | raise Exception("bad number of values for slot `%s'" % ff[0]) |
1c3d4cf5 | 689 | me._slotmap[ff[0]].set(me.st, ff[1]) |
e7abc7ea | 690 | |
1c3d4cf5 | 691 | else: |
e7abc7ea | 692 | ## Something incomprehensible. |
b8dc834f | 693 | raise Exception("unknown keyword `%s'" % ff[0]) |
e7abc7ea MW |
694 | |
695 | ## End of the input. Write out the final stanza. | |
1c3d4cf5 | 696 | me._flush() |
e7abc7ea MW |
697 | |
698 | ## Now for the name-to-data mapping. | |
1c3d4cf5 MW |
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: | |
b8dc834f | 703 | raise Exception("alias `%s' refers to unknown group `%s'" % (a, n)) |
1c3d4cf5 MW |
704 | stdout.write(' { "%s", &c_%s },\n' % (a, fix_name(n))) |
705 | stdout.write(" { 0, 0 }\n};\n\n") | |
e7abc7ea MW |
706 | |
707 | ## We're done. | |
1c3d4cf5 MW |
708 | write_banner("That's all, folks") |
709 | ||
710 | class BaseSlot (object): | |
e7abc7ea MW |
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 | ||
1c3d4cf5 | 749 | def __init__(me, name, headline = False, omitp = None, allowp = None): |
e7abc7ea MW |
750 | """ |
751 | Initialize a new slot object, setting the necessary attributes. | |
752 | """ | |
1c3d4cf5 MW |
753 | me.name = name |
754 | me.headline = headline | |
18533217 MW |
755 | me._omitp = omitp |
756 | me._allowp = allowp | |
e7abc7ea | 757 | |
1c3d4cf5 | 758 | def set(me, st, value): |
e7abc7ea MW |
759 | """ |
760 | Store a VALUE for the slot. | |
761 | """ | |
1c3d4cf5 | 762 | if me._allowp and not me._allowp(st, value): |
b8dc834f | 763 | raise Exception("slot `%s' not allowed here" % me.name) |
1c3d4cf5 | 764 | st.d[me] = value |
e7abc7ea | 765 | |
1c3d4cf5 | 766 | def setup(me, st): |
e7abc7ea MW |
767 | """ |
768 | Prepare the slot for output, checking its value and so on. | |
769 | """ | |
1c3d4cf5 | 770 | if me not in st.d and (not me._omitp or not me._omitp(st)): |
b8dc834f | 771 | raise Exception("missing slot `%s'" % me.name) |
1c3d4cf5 MW |
772 | |
773 | class EnumSlot (BaseSlot): | |
e7abc7ea MW |
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 | ||
1c3d4cf5 | 781 | def __init__(me, name, prefix, values, **kw): |
e7abc7ea MW |
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 | """ | |
1c3d4cf5 MW |
788 | super(EnumSlot, me).__init__(name, **kw) |
789 | me._values = set(values) | |
790 | me._prefix = prefix | |
e7abc7ea | 791 | |
1c3d4cf5 | 792 | def set(me, st, value): |
e7abc7ea MW |
793 | """ |
794 | Check that the VALUE is one of the ones we know. | |
795 | """ | |
1c3d4cf5 | 796 | if value not in me._values: |
b8dc834f | 797 | raise Exception("invalid %s value `%s'" % (me.name, value)) |
1c3d4cf5 | 798 | super(EnumSlot, me).set(st, value) |
e7abc7ea | 799 | |
1c3d4cf5 | 800 | def write(me, st): |
e7abc7ea MW |
801 | """ |
802 | Convert the slot value to the C constant name. | |
803 | """ | |
1c3d4cf5 MW |
804 | try: stdout.write('%s_%s' % (me._prefix, st.d[me].upper())) |
805 | except KeyError: stdout.write('0') | |
806 | ||
807 | class MPSlot (BaseSlot): | |
e7abc7ea MW |
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 | ||
3ece2113 | 815 | def set(me, st, value): |
e7abc7ea MW |
816 | """ |
817 | Set a value; convert it to a Python integer. | |
818 | """ | |
3ece2113 | 819 | super(MPSlot, me).set(st, long(value, 0)) |
e7abc7ea | 820 | |
1c3d4cf5 | 821 | def setup(me, st): |
e7abc7ea MW |
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 | """ | |
18533217 | 828 | super(MPSlot, me).setup(st) |
1c3d4cf5 MW |
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 | |
e7abc7ea | 834 | |
1c3d4cf5 | 835 | def write(me, st): |
e7abc7ea MW |
836 | """ |
837 | Write out an `mp' initializer for the slot. | |
838 | """ | |
1c3d4cf5 MW |
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' | |
18533217 MW |
858 | _typeslot = EnumSlot('type', 'FTAG', |
859 | ['prime', 'niceprime', 'binpoly', 'binnorm'], | |
860 | headline = True) | |
861 | slots = [_typeslot, | |
1c3d4cf5 MW |
862 | MPSlot('p'), |
863 | MPSlot('beta', | |
18533217 MW |
864 | allowp = lambda st, _: |
865 | st.d[EllipticCurveTable._typeslot] == 'binnorm', | |
866 | omitp = lambda st: | |
867 | st.d[EllipticCurveTable._typeslot] != 'binnorm'), | |
1c3d4cf5 MW |
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 | ||
e7abc7ea | 895 | ## Parse the positional arguments. |
1c3d4cf5 MW |
896 | if len(args) < 1: op.error('missing MODE') |
897 | mode = args[0] | |
898 | ||
e7abc7ea | 899 | ## Establish the choice of low-level C types. |
1c3d4cf5 MW |
900 | TC = TypeChoice(opts.typeinfo) |
901 | ||
e7abc7ea | 902 | ## Find the selected mode, and invoke the appropriate handler. |
1c3d4cf5 MW |
903 | try: modefunc = MODEMAP[mode] |
904 | except KeyError: op.error("unknown mode `%s'" % mode) | |
905 | modefunc(*args[1:]) | |
906 | ||
907 | ###----- That's all, folks -------------------------------------------------- |