Unroll bigint_monty_redc for various sizes

Speedup of 10 to 30% depending on algo

1 files changed, 91 insertions, 0 deletions

diff --git a/src/scripts/monty.py b/src/scripts/monty.py
new file mode 100755
index 000000000..e63442824
--- /dev/null
+++ b/src/scripts/monty.py
@@ -0,0 +1,91 @@
+#!/usr/bin/python3
+
+import sys
+import datetime
+
+# (C) 2018 Jack Lloyd
+# Botan is released under the Simplified BSD License (see license.txt)
+
+# Used to generate src/lib/math/mp/mp_monty_n.cpp
+
+def monty_redc_code(n):
+
+    lines = []
+
+    lines.append("word w2 = 0, w1 = 0, w0 = 0;")
+    lines.append("w0 = z[0];")
+    lines.append("ws[0] = w0 * p_dash;")
+
+    lines.append("word3_muladd(&w2, &w1, &w0, ws[0], p[0]);")
+    lines.append("w0 = w1; w1 = w2; w2 = 0;")
+
+    for i in range(1, n):
+        for j in range(0, i):
+            lines.append("word3_muladd(&w2, &w1, &w0, ws[%d], p[%d]);" % (j, i-j))
+
+        lines.append("word3_add(&w2, &w1, &w0, z[%d]);" % (i))
+        lines.append("ws[%d] = w0 * p_dash;" % (i))
+
+        lines.append("word3_muladd(&w2, &w1, &w0, ws[%d], p[0]);" % (i))
+        lines.append("w0 = w1; w1 = w2; w2 = 0;")
+
+    for i in range(0, n):
+        for j in range(i + 1, n):
+            lines.append("word3_muladd(&w2, &w1, &w0, ws[%d], p[%d]);" % (j, n + i-j))
+
+        lines.append("word3_add(&w2, &w1, &w0, z[%d]);" % (n+i))
+        lines.append("ws[%d] = w0;" % (i))
+        lines.append("w0 = w1; w1 = w2; w2 = 0;")
+
+    lines.append("word3_add(&w2, &w1, &w0, z[%d]);" % (2*(n+1) - 1))
+
+    lines.append("ws[%d] = w0;" % (n))
+    lines.append("ws[%d] = w1;" % (n+1))
+
+    if n < 16:
+        lines.append("word borrow = 0;")
+        for i in range(n):
+            lines.append("ws[%d] = word_sub(ws[%d], p[%d], &borrow);" % (n + 1 + i, i, i))
+        lines.append("ws[%d] = word_sub(ws[%d], 0, &borrow);" % (2*n+1, n))
+    else:
+        lines.append("word borrow = bigint_sub3(ws + %d + 1, ws, %d + 1, p, %d);" % (n, n, n))
+
+    lines.append("CT::conditional_copy_mem(borrow, z, ws, ws + %d, %d);" % (n + 1, n + 1))
+    lines.append("clear_mem(z + %d, 2*(%d+1) - %d);" % (n, n, n))
+
+    for line in lines:
+        print("   %s" % (line))
+
+def main(args = None):
+    if args is None:
+        args = sys.argv
+
+    print("""/*
+* This file was automatically generated by %s on %s
+* All manual changes will be lost. Edit the script instead.
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/mp_monty.h>
+#include <botan/internal/mp_core.h>
+#include <botan/internal/mp_asmi.h>
+#include <botan/internal/ct_utils.h>
+
+namespace Botan {
+""" % (sys.argv[0], datetime.date.today().strftime("%Y-%m-%d")))
+
+    for n in [4, 6, 8, 16, 24, 32]:
+        print("void bigint_monty_redc_%d(word z[], const word p[%d], word p_dash, word ws[])" % (n, n))
+        print("   {")
+
+        monty_redc_code(n)
+
+        print("   }\n")
+
+    print("}")
+
+if __name__ == '__main__':
+    sys.exit(main())
+
+