make/jdk/src/classes/build/tools/intpoly/FieldGen.java - master - githubmirror/jdk22

make/jdk/src/classes/build/tools/intpoly/FieldGen.java
995 строк34 KB
Daniel Jeliński
8294997: Improve ECC math operations
13 окт 2022, 13:16
13 окт 2022, 13:162f60675
/*
 * Copyright (c) 2018, 2022, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code 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 General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */

/*
 * This file is used to generated optimized finite field implementations.
 */
package build.tools.intpoly;

import java.io.*;
import java.math.BigInteger;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.*;

public class FieldGen {

    static FieldParams Curve25519 = new FieldParams(
            "IntegerPolynomial25519", 26, 10, 1, 255,
            Arrays.asList(
                    new Term(0, -19)
            ),
            Curve25519CrSequence(), simpleSmallCrSequence(10)
    );

    private static List<CarryReduce> Curve25519CrSequence() {
        List<CarryReduce> result = new ArrayList<CarryReduce>();

        // reduce(7,2)
        result.add(new Reduce(17));
        result.add(new Reduce(18));

        // carry(8,2)
        result.add(new Carry(8));
        result.add(new Carry(9));

        // reduce(0,7)
        for (int i = 10; i < 17; i++) {
            result.add(new Reduce(i));
        }

        // carry(0,9)
        result.addAll(fullCarry(10));

        return result;
    }

    static FieldParams Curve448 = new FieldParams(
            "IntegerPolynomial448", 28, 16, 1, 448,
            Arrays.asList(
                    new Term(224, -1),
                    new Term(0, -1)
            ),
            Curve448CrSequence(), simpleSmallCrSequence(16)
    );

    private static List<CarryReduce> Curve448CrSequence() {
        List<CarryReduce> result = new ArrayList<CarryReduce>();

        // reduce(8, 7)
        for (int i = 24; i < 31; i++) {
            result.add(new Reduce(i));
        }
        // reduce(4, 4)
        for (int i = 20; i < 24; i++) {
            result.add(new Reduce(i));
        }

        //carry(14, 2)
        result.add(new Carry(14));
        result.add(new Carry(15));

        // reduce(0, 4)
        for (int i = 16; i < 20; i++) {
            result.add(new Reduce(i));
        }

        // carry(0, 15)
        result.addAll(fullCarry(16));

        return result;
    }

    static FieldParams P256 = new FieldParams(
            "IntegerPolynomialP256", 26, 10, 2, 256,
            Arrays.asList(
                    new Term(224, -1),
                    new Term(192, 1),
                    new Term(96, 1),
                    new Term(0, -1)
            ),
            P256CrSequence(), simpleSmallCrSequence(10)
    );

    private static List<CarryReduce> P256CrSequence() {
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        result.addAll(fullReduce(10));
        result.addAll(simpleSmallCrSequence(10));
        return result;
    }

    static FieldParams P384 = new FieldParams(
            "IntegerPolynomialP384", 28, 14, 2, 384,
            Arrays.asList(
                    new Term(128, -1),
                    new Term(96, -1),
                    new Term(32, 1),
                    new Term(0, -1)
            ),
            P384CrSequence(), simpleSmallCrSequence(14)
    );

    private static List<CarryReduce> P384CrSequence() {
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        result.addAll(fullReduce(14));
        result.addAll(simpleSmallCrSequence(14));
        return result;
    }

    static FieldParams P521 = new FieldParams(
            "IntegerPolynomialP521", 28, 19, 2, 521,
            Arrays.asList(
                    new Term(0, -1)
            ),
            P521CrSequence(), simpleSmallCrSequence(19)
    );

    private static List<CarryReduce> P521CrSequence() {
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        result.addAll(fullReduce(19));
        result.addAll(simpleSmallCrSequence(19));
        return result;
    }

    static FieldParams O256 = new FieldParams(
            "P256OrderField", 26, 10, 1, 256,
            "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
            orderFieldCrSequence(10), orderFieldSmallCrSequence(10)
    );

    static FieldParams O384 = new FieldParams(
            "P384OrderField", 28, 14, 1, 384,
            "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
            orderFieldCrSequence(14), orderFieldSmallCrSequence(14)
    );

    static FieldParams O521 = new FieldParams(
            "P521OrderField", 28, 19, 1, 521,
            "01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
            o521crSequence(19), orderFieldSmallCrSequence(19)
    );

    static FieldParams O25519 = new FieldParams(
            "Curve25519OrderField", 26, 10, 1, 252,
            "1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed",
            orderFieldCrSequence(10), orderFieldSmallCrSequence(10)
    );

    static FieldParams O448 = new FieldParams(
            "Curve448OrderField", 28, 16, 1, 446,
            "3fffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3",
            //"ffffffffffffffffffffffffffffffffffffffffffffffffffffffff7cca23e9c44edb49aed63690216cc2728dc58f552378c292ab5844f3",
            orderFieldCrSequence(16), orderFieldSmallCrSequence(16)
    );

    private static List<CarryReduce> o521crSequence(int numLimbs) {

        // split the full reduce in half, with a carry in between
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        result.addAll(fullCarry(2 * numLimbs));
        for (int i = 2 * numLimbs - 1; i >= numLimbs + numLimbs / 2; i--) {
            result.add(new Reduce(i));
        }
        // carry
        for (int i = numLimbs; i < numLimbs + numLimbs / 2 - 1; i++) {
            result.add(new Carry(i));
        }
        // rest of reduce
        for (int i = numLimbs + numLimbs / 2 - 1; i >= numLimbs; i--) {
            result.add(new Reduce(i));
        }
        result.addAll(orderFieldSmallCrSequence(numLimbs));

        return result;
    }

    private static List<CarryReduce> orderFieldCrSequence(int numLimbs) {
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        result.addAll(fullCarry(2 * numLimbs));
        result.add(new Reduce(2 * numLimbs - 1));
        result.addAll(fullReduce(numLimbs));
        result.addAll(fullCarry(numLimbs + 1));
        result.add(new Reduce(numLimbs));
        result.addAll(fullCarry(numLimbs));

        return result;
    }

    private static List<CarryReduce> orderFieldSmallCrSequence(int numLimbs) {
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        result.addAll(fullCarry(numLimbs + 1));
        result.add(new Reduce(numLimbs));
        result.addAll(fullCarry(numLimbs));
        return result;
    }

    static final FieldParams[] ALL_FIELDS = {
            Curve25519, Curve448,
            P256, P384, P521, O256, O384, O521, O25519, O448
    };

    public static class Term {
        private final int power;
        private final int coefficient;

        public Term(int power, int coefficient) {
            this.power = power;
            this.coefficient = coefficient;
        }

        public int getPower() {
            return power;
        }

        public int getCoefficient() {
            return coefficient;
        }

        public BigInteger getValue() {
            return BigInteger.valueOf(coefficient).shiftLeft(power);
        }

        public String toString() {
            return "2^" + power + " * " + coefficient;
        }
    }

    static abstract class CarryReduce {
        private final int index;

        protected CarryReduce(int index) {
            this.index = index;
        }

        public int getIndex() {
            return index;
        }

        public abstract void write(CodeBuffer out, FieldParams params,
                String prefix, Iterable<CarryReduce> remaining);
    }

    static class Carry extends CarryReduce {
        public Carry(int index) {
            super(index);
        }

        public void write(CodeBuffer out, FieldParams params, String prefix,
                Iterable<CarryReduce> remaining) {
            carry(out, params, prefix, getIndex());
        }
    }

    static class Reduce extends CarryReduce {
        public Reduce(int index) {
            super(index);
        }

        public void write(CodeBuffer out, FieldParams params, String prefix,
                Iterable<CarryReduce> remaining) {
            reduce(out, params, prefix, getIndex(), remaining);
        }
    }

    static class FieldParams {
        private final String className;
        private final int bitsPerLimb;
        private final int numLimbs;
        private final int maxAdds;
        private final int power;
        private final Iterable<Term> terms;
        private final List<CarryReduce> crSequence;
        private final List<CarryReduce> smallCrSequence;

        public FieldParams(String className, int bitsPerLimb, int numLimbs,
                int maxAdds, int power,
                Iterable<Term> terms, List<CarryReduce> crSequence,
                List<CarryReduce> smallCrSequence) {
            this.className = className;
            this.bitsPerLimb = bitsPerLimb;
            this.numLimbs = numLimbs;
            this.maxAdds = maxAdds;
            this.power = power;
            this.terms = terms;
            this.crSequence = crSequence;
            this.smallCrSequence = smallCrSequence;
        }

        public FieldParams(String className, int bitsPerLimb, int numLimbs,
                int maxAdds, int power,
                String term, List<CarryReduce> crSequence,
                List<CarryReduce> smallCrSequence) {
            this.className = className;
            this.bitsPerLimb = bitsPerLimb;
            this.numLimbs = numLimbs;
            this.maxAdds = maxAdds;
            this.power = power;
            this.crSequence = crSequence;
            this.smallCrSequence = smallCrSequence;

            terms = buildTerms(BigInteger.ONE.shiftLeft(power)
                    .subtract(new BigInteger(term, 16)));
        }

        private Iterable<Term> buildTerms(BigInteger sub) {
            // split a large subtrahend into smaller terms
            // that are aligned with limbs
            boolean negate = false;
            if (sub.compareTo(BigInteger.ZERO) < 0) {
                negate = true;
                sub = sub.negate();
            }
            List<Term> result = new ArrayList<Term>();
            BigInteger mod = BigInteger.valueOf(1 << bitsPerLimb);
            int termIndex = 0;
            while (!sub.equals(BigInteger.ZERO)) {
                int coef = sub.mod(mod).intValue();
                boolean plusOne = false;
                if (coef > (1 << (bitsPerLimb - 1))) {
                    coef = coef - (1 << bitsPerLimb);
                    plusOne = true;
                }
                if (negate) {
                    coef = 0 - coef;
                }
                if (coef != 0) {
                    int pow = termIndex * bitsPerLimb;
                    result.add(new Term(pow, -coef));
                }
                sub = sub.shiftRight(bitsPerLimb);
                if (plusOne) {
                    sub = sub.add(BigInteger.ONE);
                }
                ++termIndex;
            }
            return result;
        }

        public String getClassName() {
            return className;
        }

        public int getBitsPerLimb() {
            return bitsPerLimb;
        }

        public int getNumLimbs() {
            return numLimbs;
        }

        public int getMaxAdds() {
            return maxAdds;
        }

        public int getPower() {
            return power;
        }

        public Iterable<Term> getTerms() {
            return terms;
        }

        public List<CarryReduce> getCrSequence() {
            return crSequence;
        }

        public List<CarryReduce> getSmallCrSequence() {
            return smallCrSequence;
        }
    }

    static Collection<Carry> fullCarry(int numLimbs) {
        List<Carry> result = new ArrayList<Carry>();
        for (int i = 0; i < numLimbs - 1; i++) {
            result.add(new Carry(i));
        }
        return result;
    }

    static Collection<Reduce> fullReduce(int numLimbs) {
        List<Reduce> result = new ArrayList<Reduce>();
        for (int i = numLimbs - 2; i >= 0; i--) {
            result.add(new Reduce(i + numLimbs));
        }
        return result;
    }

    static List<CarryReduce> simpleCrSequence(int numLimbs) {
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        for (int i = 0; i < 4; i++) {
            result.addAll(fullCarry(2 * numLimbs - 1));
            result.addAll(fullReduce(numLimbs));
        }

        return result;
    }

    static List<CarryReduce> simpleSmallCrSequence(int numLimbs) {
        List<CarryReduce> result = new ArrayList<CarryReduce>();
        // carry a few positions at the end
        for (int i = numLimbs - 2; i < numLimbs; i++) {
            result.add(new Carry(i));
        }
        // this carries out a single value that must be reduced back in
        result.add(new Reduce(numLimbs));
        // finish with a full carry
        result.addAll(fullCarry(numLimbs));
        return result;
    }

    private final String packageName;
    private final String parentName;

    private final Path headerPath;
    private final Path destPath;

    public FieldGen(String packageName, String parentName,
            Path headerPath, Path destRoot) throws IOException {
        this.packageName = packageName;
        this.parentName = parentName;
        this.headerPath = headerPath;
        this.destPath = destRoot.resolve(packageName.replace(".", "/"));
        Files.createDirectories(destPath);
    }

    // args: header.txt destpath
    public static void main(String[] args) throws Exception {

        FieldGen gen = new FieldGen(
                "sun.security.util.math.intpoly",
                "IntegerPolynomial",
                Path.of(args[0]),
                Path.of(args[1]));
        for (FieldParams p : ALL_FIELDS) {
            System.out.println(p.className);
            System.out.println(p.terms);
            System.out.println();
            gen.generateFile(p);
        }
    }

    private void generateFile(FieldParams params) throws IOException {
        String text = generate(params);
        String fileName = params.getClassName() + ".java";
        PrintWriter out = new PrintWriter(Files.newBufferedWriter(
                destPath.resolve(fileName)));
        out.println(text);
        out.close();
    }

    static class CodeBuffer {

        private int nextTemporary = 0;
        private Set<String> temporaries = new HashSet<String>();
        private StringBuffer buffer = new StringBuffer();
        private int indent = 0;
        private Class<?> lastCR;
        private int lastCrCount = 0;
        private int crMethodBreakCount = 0;
        private int crNumLimbs = 0;

        public void incrIndent() {
            indent++;
        }

        public void decrIndent() {
            indent--;
        }

        public void newTempScope() {
            nextTemporary = 0;
            temporaries.clear();
        }

        public void appendLine(String s) {
            appendIndent();
            buffer.append(s + "\n");
        }

        public void appendLine() {
            buffer.append("\n");
        }

        public String toString() {
            return buffer.toString();
        }

        public void startCrSequence(int numLimbs) {
            this.crNumLimbs = numLimbs;
            lastCrCount = 0;
            crMethodBreakCount = 0;
            lastCR = null;
        }

        /*
         * Record a carry/reduce of the specified type. This method is used to
         * break up large carry/reduce sequences into multiple methods to make
         * JIT/optimization easier
         */
        public void record(Class<?> type) {
            if (type == lastCR) {
                lastCrCount++;
            } else {

                if (lastCrCount >= 8) {
                    insertCrMethodBreak();
                }

                lastCR = type;
                lastCrCount = 0;
            }
        }

        private void insertCrMethodBreak() {

            appendLine();

            // call the new method
            appendIndent();
            append("carryReduce" + crMethodBreakCount + "(r");
            for (int i = 0; i < crNumLimbs; i++) {
                append(", c" + i);
            }
            // temporaries are not live between operations, no need to send
            append(");\n");

            decrIndent();
            appendLine("}");

            // make the method
            appendIndent();
            append("void carryReduce" + crMethodBreakCount + "(long[] r");
            for (int i = 0; i < crNumLimbs; i++) {
                append(", long c" + i);
            }
            append(") {\n");
            incrIndent();
            // declare temporaries
            for (String temp : temporaries) {
                appendLine("long " + temp + ";");
            }
            append("\n");

            crMethodBreakCount++;
        }

        public String getTemporary(String type, String value) {
            Iterator<String> iter = temporaries.iterator();
            if (iter.hasNext()) {
                String result = iter.next();
                iter.remove();
                appendLine(result + " = " + value + ";");
                return result;
            } else {
                String result = "t" + (nextTemporary++);
                appendLine(type + " " + result + " = " + value + ";");
                return result;
            }
        }

        public void freeTemporary(String temp) {
            temporaries.add(temp);
        }

        public void appendIndent() {
            for (int i = 0; i < indent; i++) {
                buffer.append("    ");
            }
        }

        public void append(String s) {
            buffer.append(s);
        }
    }

    private String generate(FieldParams params) throws IOException {
        CodeBuffer result = new CodeBuffer();
        String header = readHeader();
        result.appendLine(header);

        if (packageName != null) {
            result.appendLine("package " + packageName + ";");
            result.appendLine();
        }
        result.appendLine("import java.math.BigInteger;");

        result.appendLine("public final class " + params.getClassName()
                + " extends " + this.parentName + " {");
        result.incrIndent();

        result.appendLine("private static final int BITS_PER_LIMB = "
                + params.getBitsPerLimb() + ";");
        result.appendLine("private static final int NUM_LIMBS = "
                + params.getNumLimbs() + ";");
        result.appendLine("private static final int MAX_ADDS = "
                + params.getMaxAdds() + ";");
        result.appendLine(
                "public static final BigInteger MODULUS = evaluateModulus();");
        result.appendLine("private static final long CARRY_ADD = 1 << "
                + (params.getBitsPerLimb() - 1) + ";");
        if (params.getBitsPerLimb() * params.getNumLimbs() != params.getPower()) {
            result.appendLine("private static final int LIMB_MASK = -1 "
                    + ">>> (64 - BITS_PER_LIMB);");
        }

        result.appendLine();
        result.appendLine("public static final " + params.getClassName() + " ONE = new "
                          + params.getClassName() + "();");
        result.appendLine();
        result.appendLine("private " + params.getClassName() + "() {");
        result.appendLine();
        result.appendLine("    super(BITS_PER_LIMB, NUM_LIMBS, MAX_ADDS, MODULUS);");
        result.appendLine();
        result.appendLine("}");

        StringBuilder coqTerms = new StringBuilder("//");
        for (Term t : params.getTerms()) {
            coqTerms.append("(" + t.getPower() + "%nat,");
            coqTerms.append(t.getCoefficient() + ")::");
        }
        coqTerms.append("nil.");
        result.appendLine(coqTerms.toString());

        result.appendLine("private static BigInteger evaluateModulus() {");
        result.incrIndent();
        result.appendLine("BigInteger result = BigInteger.valueOf(2).pow("
                + params.getPower() + ");");
        for (Term t : params.getTerms()) {
            boolean subtract = false;
            int coefValue = t.getCoefficient();
            if (coefValue < 0) {
                coefValue = 0 - coefValue;
                subtract = true;
            }
            String coefExpr = "BigInteger.valueOf(" + coefValue + ")";
            String powExpr = ".shiftLeft(" + t.getPower() + ")";
            String termExpr = "ERROR";
            if (t.getPower() == 0) {
                termExpr = coefExpr;
            } else {
                termExpr = coefExpr + powExpr;
            }
            if (subtract) {
                result.appendLine("result = result.subtract(" + termExpr + ");");
            } else {
                result.appendLine("result = result.add(" + termExpr + ");");
            }
        }
        result.appendLine("return result;");
        result.decrIndent();
        result.appendLine("}");

        result.appendLine("@Override");
        result.appendLine("protected void reduceIn(long[] limbs, long v, int i) {");
        result.incrIndent();
        String c = "v";
        for (Term t : params.getTerms()) {
            int reduceBits = params.getPower() - t.getPower();
            int coefficient = -1 * t.getCoefficient();

            String x = coefficient + " * " + c;
            String accOp = "+=";
            String temp = null;
            if (coefficient == 1) {
                x = c;
            } else if (coefficient == -1) {
                x = c;
                accOp = "-=";
            } else {
                temp = result.getTemporary("long", x);
                x = temp;
            }

            if (reduceBits % params.getBitsPerLimb() == 0) {
                int pos = reduceBits / params.getBitsPerLimb();
                result.appendLine("limbs[i - " + pos + "] " + accOp + " " + x + ";");
            } else {
                int secondPos = reduceBits / params.getBitsPerLimb();
                int bitOffset = (secondPos + 1) * params.getBitsPerLimb() - reduceBits;
                int rightBitOffset = params.getBitsPerLimb() - bitOffset;
                result.appendLine("limbs[i - " + (secondPos + 1) + "] " + accOp + " (" + x + " << " + bitOffset + ") & LIMB_MASK;");
                result.appendLine("limbs[i - " + secondPos + "] " + accOp + " " + x + " >> " + rightBitOffset + ";");
            }
        }
        result.decrIndent();
        result.appendLine("}");

        result.appendLine("@Override");
        result.appendLine("protected void finalCarryReduceLast(long[] limbs) {");
        result.incrIndent();
        int extraBits = params.getBitsPerLimb() * params.getNumLimbs()
                - params.getPower();
        int highBits = params.getBitsPerLimb() - extraBits;
        result.appendLine("long c = limbs[" + (params.getNumLimbs() - 1)
                + "] >> " + highBits + ";");
        result.appendLine("limbs[" + (params.getNumLimbs() - 1) + "] -= c << "
                + highBits + ";");
        for (Term t : params.getTerms()) {
            int reduceBits = params.getPower() + extraBits - t.getPower();
            int negatedCoefficient = -1 * t.getCoefficient();
            modReduceInBits(result, params, true, "limbs", params.getNumLimbs(),
                    reduceBits, negatedCoefficient, "c");
        }
        result.decrIndent();
        result.appendLine("}");

        // full carry/reduce sequence
        result.appendIndent();
        result.append("private void carryReduce(long[] r, ");
        for (int i = 0; i < 2 * params.getNumLimbs() - 1; i++) {
            result.append("long c" + i);
            if (i < 2 * params.getNumLimbs() - 2) {
                result.append(", ");
            }
        }
        result.append(") {\n");
        result.newTempScope();
        result.incrIndent();
        result.appendLine("long c" + (2 * params.getNumLimbs() - 1) + " = 0;");
        write(result, params.getCrSequence(), params, "c",
                2 * params.getNumLimbs());
        result.appendLine();
        for (int i = 0; i < params.getNumLimbs(); i++) {
            result.appendLine("r[" + i + "] = c" + i + ";");
        }
        result.decrIndent();
        result.appendLine("}");

        // small carry/reduce sequence
        result.appendIndent();
        result.append("private void carryReduce(long[] r, ");
        for (int i = 0; i < params.getNumLimbs(); i++) {
            result.append("long c" + i);
            if (i < params.getNumLimbs() - 1) {
                result.append(", ");
            }
        }
        result.append(") {\n");
        result.newTempScope();
        result.incrIndent();
        result.appendLine("long c" + params.getNumLimbs() + " = 0;");
        write(result, params.getSmallCrSequence(), params,
                "c", params.getNumLimbs() + 1);
        result.appendLine();
        for (int i = 0; i < params.getNumLimbs(); i++) {
            result.appendLine("r[" + i + "] = c" + i + ";");
        }
        result.decrIndent();
        result.appendLine("}");

        result.appendLine("@Override");
        result.appendLine("protected void mult(long[] a, long[] b, long[] r) {");
        result.incrIndent();
        for (int i = 0; i < 2 * params.getNumLimbs() - 1; i++) {
            result.appendIndent();
            result.append("long c" + i + " = ");
            int startJ = Math.max(i + 1 - params.getNumLimbs(), 0);
            int endJ = Math.min(params.getNumLimbs(), i + 1);
            for (int j = startJ; j < endJ; j++) {
                int bIndex = i - j;
                result.append("(a[" + j + "] * b[" + bIndex + "])");
                if (j < endJ - 1) {
                    result.append(" + ");
                }
            }
            result.append(";\n");
        }
        result.appendLine();
        result.appendIndent();
        result.append("carryReduce(r, ");
        for (int i = 0; i < 2 * params.getNumLimbs() - 1; i++) {
            result.append("c" + i);
            if (i < 2 * params.getNumLimbs() - 2) {
                result.append(", ");
            }
        }
        result.append(");\n");
        result.decrIndent();
        result.appendLine("}");

        result.appendLine("@Override");
        result.appendLine("protected void reduce(long[] a) {");
        result.incrIndent();
        result.appendIndent();
        result.append("carryReduce(a, ");
        for (int i = 0; i < params.getNumLimbs(); i++) {
            result.append("a[" + i + "]");
            if (i < params.getNumLimbs() - 1) {
                result.append(", ");
            }
        }
        result.append(");\n");
        result.decrIndent();
        result.appendLine("}");

        // Use grade-school multiplication with a simple squaring optimization.
        // Multiply into primitives to avoid the temporary array allocation.
        // This is equivalent to the following code:
        //  long[] c = new long[2 * NUM_LIMBS - 1];
        //  for(int i = 0; i < NUM_LIMBS; i++) {
        //      c[2 * i] = a[i] * a[i];
        //      for(int j = i + 1; j < NUM_LIMBS; j++) {
        //          c[i + j] += 2 * a[i] * a[j]
        //      }
        //  }
        result.appendLine("@Override");
        result.appendLine("protected void square(long[] a, long[] r) {");
        result.incrIndent();
        for (int i = 0; i < 2 * params.getNumLimbs() - 1; i++) {
            result.appendIndent();
            result.append("long c" + i + " = ");
            int startJ = Math.max(i + 1 - params.getNumLimbs(), 0);
            int endJ = Math.min(params.getNumLimbs(), i + 1);
            int jDiff = endJ - startJ;
            if (jDiff > 1) {
                result.append("2 * (");
            }
            for (int j = 0; j < jDiff / 2; j++) {
                int aIndex = j + startJ;
                int bIndex = i - aIndex;
                result.append("(a[" + aIndex + "] * a[" + bIndex + "])");
                if (j < (jDiff / 2) - 1) {
                    result.append(" + ");
                }
            }
            if (jDiff > 1) {
                result.append(")");
            }
            if (jDiff % 2 == 1) {
                int aIndex = i / 2;
                if (jDiff > 1) {
                    result.append(" + ");
                }
                result.append("(a[" + aIndex + "] * a[" + aIndex + "])");
            }
            result.append(";\n");
        }
        result.appendLine();
        result.appendIndent();
        result.append("carryReduce(r, ");
        for (int i = 0; i < 2 * params.getNumLimbs() - 1; i++) {
            result.append("c" + i);
            if (i < 2 * params.getNumLimbs() - 2) {
                result.append(", ");
            }
        }
        result.append(");\n");
        result.decrIndent();
        result.appendLine("}");

        result.decrIndent();
        result.appendLine("}"); // end class

        return result.toString();
    }

    private static void write(CodeBuffer out, List<CarryReduce> sequence,
            FieldParams params, String prefix, int numLimbs) {

        out.startCrSequence(numLimbs);
        for (int i = 0; i < sequence.size(); i++) {
            CarryReduce cr = sequence.get(i);
            Iterator<CarryReduce> remainingIter = sequence.listIterator(i + 1);
            List<CarryReduce> remaining = new ArrayList<CarryReduce>();
            remainingIter.forEachRemaining(remaining::add);
            cr.write(out, params, prefix, remaining);
        }
    }

    private static void reduce(CodeBuffer out, FieldParams params,
            String prefix, int index, Iterable<CarryReduce> remaining) {

        out.record(Reduce.class);

        out.appendLine("//reduce from position " + index);
        String reduceFrom = indexedExpr(false, prefix, index);
        boolean referenced = false;
        for (CarryReduce cr : remaining) {
            if (cr.index == index) {
                referenced = true;
            }
        }
        for (Term t : params.getTerms()) {
            int reduceBits = params.getPower() - t.getPower();
            int negatedCoefficient = -1 * t.getCoefficient();
            modReduceInBits(out, params, false, prefix, index, reduceBits,
                    negatedCoefficient, reduceFrom);
        }
        if (referenced) {
            out.appendLine(reduceFrom + " = 0;");
        }
    }

    private static void carry(CodeBuffer out, FieldParams params,
            String prefix, int index) {

        out.record(Carry.class);

        out.appendLine("//carry from position " + index);
        String carryFrom = prefix + index;
        String carryTo = prefix + (index + 1);
        String carry = "(" + carryFrom + " + CARRY_ADD) >> "
                + params.getBitsPerLimb();
        String temp = out.getTemporary("long", carry);
        out.appendLine(carryFrom + " -= (" + temp + " << "
                + params.getBitsPerLimb() + ");");
        out.appendLine(carryTo + " += " + temp + ";");
        out.freeTemporary(temp);
    }

    private static String indexedExpr(
            boolean isArray, String prefix, int index) {
        String result = prefix + index;
        if (isArray) {
            result = prefix + "[" + index + "]";
        }
        return result;
    }

    private static void modReduceInBits(CodeBuffer result, FieldParams params,
            boolean isArray, String prefix, int index, int reduceBits,
            int coefficient, String c) {

        String x = coefficient + " * " + c;
        String accOp = "+=";
        String temp = null;
        if (coefficient == 1) {
            x = c;
        } else if (coefficient == -1) {
            x = c;
            accOp = "-=";
        } else {
            temp = result.getTemporary("long", x);
            x = temp;
        }

        if (reduceBits % params.getBitsPerLimb() == 0) {
            int pos = reduceBits / params.getBitsPerLimb();
            result.appendLine(indexedExpr(isArray, prefix, (index - pos))
                    + " " + accOp + " " + x + ";");
        } else {
            int secondPos = reduceBits / params.getBitsPerLimb();
            int bitOffset = (secondPos + 1) * params.getBitsPerLimb()
                    - reduceBits;
            int rightBitOffset = params.getBitsPerLimb() - bitOffset;
            result.appendLine(indexedExpr(isArray, prefix,
                    (index - (secondPos + 1))) + " " + accOp
                    + " (" + x + " << " + bitOffset + ") & LIMB_MASK;");
            result.appendLine(indexedExpr(isArray, prefix,
                    (index - secondPos)) + " " + accOp + " " + x
                    + " >> " + rightBitOffset + ";");
        }

        if (temp != null) {
            result.freeTemporary(temp);
        }
    }

    private String readHeader() throws IOException {
        BufferedReader reader
                = Files.newBufferedReader(headerPath);
        StringBuffer result = new StringBuffer();
        reader.lines().forEach(s -> result.append(s + "\n"));
        return result.toString();
    }
}