efd: parse three-operand code

Operand types observed:

4518 mul        w4 = K*t11
2230 square     J = A^2
2189 sub        t10 = t7-t6
2088 add        t10 = t9+t8
 590 double     Q = 2*t12
 335 assign     w3 = w1
 140 cube       t51 = Z1^3
 124 mul4       t17 = 4*t16
  80 inverse    t11 = 1/t10
  77 triple     Y3 = 3*t39
  69 mul8       t10 = 8*Q1
  47 pow4       t31 = X1^4
  44 one        Z3 = 1
  23 oneplus    t0 = 1+w2
  19 oneminus   Z3 = 1-t3
  17 plusone    t7 = X3+1
   9 mul6       t5 = 6*t4
   9 error      error: not sure how to handle (R*(-t14)-P^3*t15)/2
   6 neg        Y3 = -t5
   6 mul16      t14 = 16*t12
   6 minusone   Z3 = A-1
   4 mul12      t4 = 12*t3
   3 unknown    t7 = 2d*t6
   3 minustwo   t3 = G-2
   2 mul64      t6 = 64*C
   1 twoplus    G = 2+C
   1 twominus   F = 2-C
   1 mul9       t5 = 9*C
   1 mul32      t2 = 32*C
   1 mul256     t9 = 256*C
   1 fourminus  Z3 = 4-t5

Note:

There are still three unknown entries. These appear to be variables which start with a number, that did not parse as identifiers by the Python script. Need to verify these are in fact valid.
There are some errors from the script that produced these. Need to detect these in the parser.

The unknowns are:

unknown t1 = A-2P
unknown t3 = X1*2P
unknown t7 = 2d*t6

Originals:

https://hyperelliptic.org/EFD/g1p/auto-code/twistedhessian/projective/doubling/dbl-2012-c.op3 https://hyperelliptic.org/EFD/g1p/auto-code/twistedhessian/projective/doubling/dbl-2009-bkl-3.op3

Results produced by this script on all the .op3 files in the EFD.

import sys
import re
import collections

def split(op):
    return op.split(' = ')

def is_identifier(s):
    return re.fullmatch(r'[a-zA-Z][a-zA-Z0-9]*', s)

def classify(op):
    if op.startswith('error:'):
        return 'error'

    _, expr = split(op)

    # Const.
    if expr == "1":
        return "one"

    # Look for known prefixes.
    prefixes = [
            ("-", "neg"),
            ("1+", "oneplus"),
            ("1-", "oneminus"),
            ("2+", "twoplus"),
            ("2-", "twominus"),
            ("4-", "fourminus"),
            ("1/", "inverse"),
            ("2*", "double"),
            ("3*", "triple"),
            ("4*", "mul4"),
            ("6*", "mul6"),
            ("8*", "mul8"),
            ("9*", "mul9"),
            ("12*", "mul12"),
            ("16*", "mul16"),
            ("32*", "mul32"),
            ("64*", "mul64"),
            ("256*", "mul256"),
            ]

    for prefix, name in prefixes:
        if expr.startswith(prefix):
            return name

    # Known suffix.
    suffixes = [
            ("+1", "plusone"),
            ("-1", "minusone"),
            ("-2", "minustwo"),
            ("^2", "square"),
            ("^3", "cube"),
            ("^4", "pow4"),
            ]
    for suffix, name in suffixes:
        if expr.endswith(suffix):
            return name

    # Binary operators.
    operators = [
            ("*", "mul"),
            ("+", "add"),
            ("-", "sub"),
            ]
    for sym, name in operators:
        parts = expr.split(sym)
        if len(parts) != 2:
            continue
        if is_identifier(parts[0]) and is_identifier(parts[1]):
            return name

    # Assignment.
    if is_identifier(expr):
        return "assign"

    return 'unknown'

if __name__ == '__main__':
    example = dict()
    count = collections.Counter()

    # Process them all.
    for op in sys.stdin:
        op = op.strip()
        name = classify(op)
        # print("{}\t{}".format(name, op))
        count[name] += 1
        example[name] = op

    for name in count:
        print("{:4d} {:10s} {}".format(count[name], name, example[name]))

mmcloughlin / ec3

efd: parse three-operand code #37