Overhaul `math' representation machinery.

[u/mdw/catacomb] / math / mpgen

#! @PYTHON@
###
### Generate multiprecision integer representations
###
### (c) 2013 Straylight/Edgeware
###

###----- Licensing notice ---------------------------------------------------
###
### This file is part of Catacomb.
###
### Catacomb is free software; you can redistribute it and/or modify
### it under the terms of the GNU Library General Public License as
### published by the Free Software Foundation; either version 2 of the
### License, or (at your option) any later version.
###
### Catacomb is distributed in the hope that it will be useful,
### but WITHOUT ANY WARRANTY; without even the implied warranty of
### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
### GNU Library General Public License for more details.
###
### You should have received a copy of the GNU Library General Public
### License along with Catacomb; if not, write to the Free
### Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
### MA 02111-1307, USA.

from __future__ import with_statement

import re as RX
import optparse as OP
import types as TY

from sys import stdout

###--------------------------------------------------------------------------
### Random utilities.

def write_header(mode, name):
  stdout.write("""\
/* -*-c-*- GENERATED by mpgen (%s)
 *
 * %s
 */

""" % (mode, name))

def write_banner(text):
  stdout.write("/*----- %s %s*/\n" % (text, '-' * (66 - len(text))))

class struct (object): pass

R_IDBAD = RX.compile('[^0-9A-Za-z]')
def fix_name(name): return R_IDBAD.sub('_', name)

###--------------------------------------------------------------------------
### Determining the appropriate types.

TYPEMAP = {}

class IntClass (type):
  def __new__(cls, name, supers, dict):
    c = type.__new__(cls, name, supers, dict)
    try: TYPEMAP[c.tag] = c
    except AttributeError: pass
    return c

class BasicIntType (object):
  __metaclass__ = IntClass
  preamble = ''
  typedef_prefix = ''
  literalfmt = '%su'
  def __init__(me, bits, rank):
    me.bits = bits
    me.rank = rank
    me.litwd = len(me.literal(0))
  def literal(me, value, fmt = None):
    if fmt is None: fmt = '0x%0' + str((me.bits + 3)//4) + 'x'
    return me.literalfmt % (fmt % value)

class UnsignedCharType (BasicIntType):
  tag = 'uchar'
  name = 'unsigned char'

class UnsignedShortType (BasicIntType):
  tag = 'ushort'
  name = 'unsigned short'

class UnsignedIntType (BasicIntType):
  tag = 'uint'
  name = 'unsigned int'

class UnsignedLongType (BasicIntType):
  tag = 'ulong'
  name = 'unsigned long'
  literalfmt = '%sul'

class UnsignedLongLongType (BasicIntType):
  tag = 'ullong'
  name = 'unsigned long long'
  preamble = """
#if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 91)
#  define CATACOMB_GCC_EXTENSION __extension__
#else
#  define CATACOMB_GCC_EXTENSION
#endif
"""
  typedef_prefix = 'CATACOMB_GCC_EXTENSION '
  literalfmt = 'CATACOMB_GCC_EXTENSION %sull'

class UIntMaxType (BasicIntType):
  tag = 'uintmax'
  name = 'uintmax_t'
  preamble = "\n#include <stdint.h>\n"

class TypeChoice (object):
  def __init__(me, tifile):

    ## Load the captured type information.
    me.ti = TY.ModuleType('typeinfo')
    execfile(opts.typeinfo, me.ti.__dict__)

    ## Build a map of the available types.
    tymap = {}
    byrank = []
    for tag, bits in me.ti.TYPEINFO:
      rank = len(byrank)
      tymap[tag] = rank
      byrank.append(TYPEMAP[tag](bits, rank))

    ## First pass: determine a suitable word size.  The criteria are (a)
    ## there exists another type at least twice as long (so that we can do a
    ## single x single -> double multiplication), and (b) operations on a
    ## word are efficient (so we'd prefer a plain machine word).  We'll start
    ## at `int' and work down.  Maybe this won't work: there's a plan B.
    mpwbits = 0
    i = tymap['uint']
    while not mpwbits and i >= 0:
      ibits = byrank[i].bits
      for j in xrange(i + 1, len(byrank)):
        if byrank[j].bits >= 2*ibits:
          mpwbits = ibits
          break

    ## If that didn't work, then we'll start with the largest type available
    ## and go with half its size.
    if not mpwbits:
      mpwbits = byrank[-1].bits//2

    ## Make sure we've not ended up somewhere really silly.
    if mpwbits < 16:
      raise Exception, "`mpw' type is too small: your C environment is weird"

    ## Now figure out suitable types for `mpw' and `mpd'.
    def find_type(bits, what):
      for ty in byrank:
        if ty.bits >= bits: return ty
      raise Exception, \
          "failed to find suitable %d-bit type, for %s" % (bits, what)

    ## Store our decisions.
    me.mpwbits = mpwbits
    me.mpw = find_type(mpwbits, 'mpw')
    me.mpd = find_type(mpwbits*2, 'mpd')

###--------------------------------------------------------------------------
### Outputting constant multiprecision integers.

MARGIN = 72

def write_preamble():
  stdout.write("""
#include <mLib/macros.h>
#define MP_(name, flags) \\
  { (/*unconst*/ mpw *)name##__mpw, \\
    (/*unconst*/ mpw *)name##__mpw + N(name##__mpw), \\
    N(name##__mpw), 0, MP_CONST | flags, 0 }
#define ZERO_MP { 0, 0, 0, 0, MP_CONST, 0 }
#define POS_MP(name) MP_(name, 0)
#define NEG_MP(name) MP_(name, MP_NEG)
""")

def write_limbs(name, x):
  if not x: return
  stdout.write("\nstatic const mpw %s__mpw[] = {" % name)
  sep = ''
  pos = MARGIN
  if x < 0: x = -x
  mask = (1 << TC.mpwbits) - 1

  while x > 0:
    w, x = x & mask, x >> TC.mpwbits
    f = TC.mpw.literal(w)
    if pos + 2 + len(f) <= MARGIN:
      stdout.write(sep + ' ' + f)
    else:
      pos = 2
      stdout.write(sep + '\n  ' + f)
    pos += len(f) + 2
    sep = ','

  stdout.write("\n};\n")

def mp_body(name, x):
  return "%s_MP(%s)" % (x >= 0 and "POS" or "NEG", name)

###--------------------------------------------------------------------------
### Mode definition machinery.

MODEMAP = {}

def defmode(func):
  name = func.func_name
  if name.startswith('m_'): name = name[2:]
  MODEMAP[name] = func
  return func

###--------------------------------------------------------------------------
### The basic types header.

@defmode
def m_mptypes():
  write_header("mptypes", "mptypes.h")
  stdout.write("""\
#ifndef CATACOMB_MPTYPES_H
#define CATACOMB_MPTYPES_H
""")

  have = set([TC.mpw, TC.mpd])
  for t in have:
    stdout.write(t.preamble)

  for label, t, bits in [('mpw', TC.mpw, TC.mpwbits),
                         ('mpd', TC.mpd, TC.mpwbits*2)]:
    LABEL = label.upper()
    stdout.write("\n%stypedef %s %s;\n" % (t.typedef_prefix, t.name, label))
    stdout.write("#define %s_BITS %d\n" % (LABEL, bits))
    i = 1
    while 2*i < bits: i *= 2
    stdout.write("#define %s_P2 %d\n" % (LABEL, i))
    stdout.write("#define %s_MAX %s\n" % (LABEL,
                                          t.literal((1 << bits) - 1, "%d")))

  stdout.write("\n#endif\n")

###--------------------------------------------------------------------------
### Constant tables.

@defmode
def m_mplimits_c():
  write_header("mplimits_c", "mplimits.c")
  stdout.write('#include "mplimits.h"\n')
  write_preamble()
  seen = {}
  v = []
  def write(x):
    if not x or x in seen: return
    seen[x] = 1
    write_limbs('limits_%d' % len(v), x)
    v.append(x)
  for tag, lo, hi in TC.ti.LIMITS:
    write(lo)
    write(hi)

  stdout.write("\nmp mp_limits[] = {")
  i = 0
  sep = "\n  "
  for x in v:
    stdout.write("%s%s_MP(limits_%d)\n" % (sep, x < 0 and "NEG" or "POS", i))
    i += 1
    sep = ",\n  "
  stdout.write("\n};\n");

@defmode
def m_mplimits_h():
  write_header("mplimits_h", "mplimits.h")
  stdout.write("""\
#ifndef CATACOMB_MPLIMITS_H
#define CATACOMB_MPLIMITS_H

#ifndef CATACOMB_MP_H
#  include "mp.h"
#endif

extern mp mp_limits[];

""")

  seen = { 0: "MP_ZERO" }
  slot = [0]
  def find(x):
    try:
      r = seen[x]
    except KeyError:
      r = seen[x] = '(&mp_limits[%d])' % slot[0]
      slot[0] += 1
    return r
  for tag, lo, hi in TC.ti.LIMITS:
    stdout.write("#define MP_%s_MIN %s\n" % (tag, find(lo)))
    stdout.write("#define MP_%s_MAX %s\n" % (tag, find(hi)))

  stdout.write("\n#endif\n")

###--------------------------------------------------------------------------
### Group tables.

class GroupTableClass (type):
  def __new__(cls, name, supers, dict):
    c = type.__new__(cls, name, supers, dict)
    try: mode = c.mode
    except AttributeError: pass
    else: MODEMAP[c.mode] = c.run
    return c

class GroupTable (object):
  __metaclass__ = GroupTableClass
  keyword = 'group'
  slots = []
  def __init__(me):
    me.st = st = struct()
    st.nextmp = 0
    st.mpmap = { None: 'NO_MP', 0: 'ZERO_MP' }
    st.d = {}
    me.st.name = None
    me._names = []
    me._defs = set()
    me._slotmap = dict([(s.name, s) for s in me.slots])
    me._headslots = [s for s in me.slots if s.headline]
  def _flush(me):
    if me.st.name is None: return
    stdout.write("/* --- %s --- */\n" % me.st.name)
    for s in me.slots: s.setup(me.st)
    stdout.write("\nstatic %s c_%s = {" % (me.data_t, fix_name(me.st.name)))
    sep = "\n  "
    for s in me.slots:
      stdout.write(sep)
      s.write(me.st)
      sep = ",\n  "
    stdout.write("\n};\n\n")
    me.st.d = {}
    me.st.name = None
  @classmethod
  def run(cls, input):
    me = cls()
    write_header(me.mode, me.filename)
    stdout.write('#include "%s"\n' % me.header)
    write_preamble()
    stdout.write("#define NO_MP { 0, 0, 0, 0, 0, 0 }\n\n")
    write_banner("Group data")
    stdout.write('\n')
    with open(input) as file:
      for line in file:
        ff = line.split()
        if not ff or ff[0].startswith('#'): continue
        if ff[0] == 'alias':
          if len(ff) != 3: raise Exception, "wrong number of alias arguments"
          me._flush()
          me._names.append((ff[1], ff[2]))
        elif ff[0] == me.keyword:
          if len(ff) < 2 or len(ff) > 2 + len(me._headslots):
            raise Exception, "bad number of headline arguments"
          me._flush()
          me.st.name = name = ff[1]
          me._defs.add(name)
          me._names.append((name, name))
          for f, s in zip(ff[2:], me._headslots): s.set(me.st, f)
        elif ff[0] in me._slotmap:
          if len(ff) != 2:
            raise Exception, "bad number of values for slot `%s'" % ff[0]
          me._slotmap[ff[0]].set(me.st, ff[1])
        else:
          raise Exception, "unknown keyword `%s'" % ff[0]
    me._flush()
    write_banner("Main table")
    stdout.write("\nconst %s %s[] = {\n" % (me.entry_t, me.tabname))
    for a, n in me._names:
      if n not in me._defs:
        raise Exception, "alias `%s' refers to unknown group `%s'" % (a, n)
      stdout.write('  { "%s", &c_%s },\n' % (a, fix_name(n)))
    stdout.write("  { 0, 0 }\n};\n\n")
    write_banner("That's all, folks")

class BaseSlot (object):
  def __init__(me, name, headline = False, omitp = None, allowp = None):
    me.name = name
    me.headline = headline
    me._omitp = None
    me._allowp = None
  def set(me, st, value):
    if me._allowp and not me._allowp(st, value):
      raise Exception, "slot `%s' not allowed here" % me.name
    st.d[me] = value
  def setup(me, st):
    if me not in st.d and (not me._omitp or not me._omitp(st)):
      raise Exception, "missing slot `%s'" % me.name

class EnumSlot (BaseSlot):
  def __init__(me, name, prefix, values, **kw):
    super(EnumSlot, me).__init__(name, **kw)
    me._values = set(values)
    me._prefix = prefix
  def set(me, st, value):
    if value not in me._values:
      raise Exception, "invalid %s value `%s'" % (me.name, value)
    super(EnumSlot, me).set(st, value)
  def write(me, st):
    try: stdout.write('%s_%s' % (me._prefix, st.d[me].upper()))
    except KeyError: stdout.write('0')

class MPSlot (BaseSlot):
  def setup(me, st):
    v = st.d.get(me)
    if v not in st.mpmap:
      write_limbs('v%d' % st.nextmp, v)
      st.mpmap[v] = mp_body('v%d' % st.nextmp, v)
      st.nextmp += 1
  def set(me, st, value):
    super(MPSlot, me).set(st, long(value, 0))
  def write(me, st):
    stdout.write(st.mpmap[st.d.get(me)])

class BinaryGroupTable (GroupTable):
  mode = 'bintab'
  filename = 'bintab.c'
  header = 'bintab.h'
  data_t = 'bindata'
  entry_t = 'binentry'
  tabname = 'bintab'
  slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]

class EllipticCurveTable (GroupTable):
  mode = 'ectab'
  filename = 'ectab.c'
  header = 'ectab.h'
  keyword = 'curve'
  data_t = 'ecdata'
  entry_t = 'ecentry'
  tabname = 'ectab'
  slots = [EnumSlot('type', 'FTAG',
                    ['prime', 'niceprime', 'binpoly', 'binnorm'],
                    headline = True),
           MPSlot('p'),
           MPSlot('beta',
                  allowp = lambda st, _: st.d['type'] == 'binnorm',
                  omitp = lambda st: st.d['type'] != 'binnorm'),
           MPSlot('a'), MPSlot('b'), MPSlot('r'), MPSlot('h'),
           MPSlot('gx'), MPSlot('gy')]

class PrimeGroupTable (GroupTable):
  mode = 'ptab'
  filename = 'ptab.c'
  header = 'ptab.h'
  data_t = 'pdata'
  entry_t = 'pentry'
  tabname = 'ptab'
  slots = [MPSlot('p'), MPSlot('q'), MPSlot('g')]

###--------------------------------------------------------------------------
### Main program.

op = OP.OptionParser(
  description = 'Generate multiprecision integer representations',
  usage = 'usage: %prog [-t TYPEINFO] MODE [ARGS ...]',
  version = 'Catacomb, version @VERSION@')
for shortopt, longopt, kw in [
  ('-t', '--typeinfo', dict(
      action = 'store', metavar = 'PATH', dest = 'typeinfo',
      help = 'alternative typeinfo file'))]:
  op.add_option(shortopt, longopt, **kw)
op.set_defaults(typeinfo = './typeinfo.py')
opts, args = op.parse_args()

if len(args) < 1: op.error('missing MODE')
mode = args[0]

TC = TypeChoice(opts.typeinfo)

try: modefunc = MODEMAP[mode]
except KeyError: op.error("unknown mode `%s'" % mode)
modefunc(*args[1:])

###----- That's all, folks --------------------------------------------------