1 files changed, 126 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/scripts/comba.py b/comm/third_party/botan/src/scripts/comba.py
new file mode 100755
index 0000000000..309dca0821
--- /dev/null
+++ b/comm/third_party/botan/src/scripts/comba.py
@@ -0,0 +1,126 @@
+#!/usr/bin/python3
+
+import sys
+import datetime
+
+# (C) 2011,2014,2015,2016 Jack Lloyd
+# Botan is released under the Simplified BSD License (see license.txt)
+
+# Used to generate src/lib/math/mp/mp_comba.cpp
+
+def comba_indexes(N):
+
+    indexes = []
+
+    for i in range(0, 2*N):
+        x = []
+
+        for j in range(max(0, i-N+1), min(N, i+1)):
+            x += [(j,i-j)]
+        indexes += [sorted(x)]
+
+    return indexes
+
+def comba_sqr_indexes(N):
+
+    indexes = []
+
+    for i in range(0, 2*N):
+        x = []
+
+        for j in range(max(0, i-N+1), min(N, i+1)):
+            if j < i-j:
+                x += [(j,i-j)]
+            else:
+                x += [(i-j,j)]
+        indexes += [sorted(x)]
+
+    return indexes
+
+def comba_multiply_code(N):
+    indexes = comba_indexes(N)
+
+    w2 = 'w2'
+    w1 = 'w1'
+    w0 = 'w0'
+
+    for (i,idx) in zip(range(0, len(indexes)), indexes):
+        for pair in idx:
+            print("   word3_muladd(&%s, &%s, &%s, x[%2d], y[%2d]);" % (w2, w1, w0, pair[0], pair[1]))
+
+        if i < 2*N-2:
+            print("   z[%2d] = %s; %s = 0;\n" % (i, w0, w0))
+        else:
+            print("   z[%2d] = %s;" % (i, w0))
+        (w0,w1,w2) = (w1,w2,w0)
+        #print("z[%2d] = w0; w0 = w1; w1 = w2; w2 = 0;" % (i))
+
+def comba_square_code(N):
+    indexes = comba_sqr_indexes(N)
+
+    w2 = 'w2'
+    w1 = 'w1'
+    w0 = 'w0'
+
+    for (rnd,idx) in zip(range(0, len(indexes)), indexes):
+        for (i,pair) in zip(range(0, len(idx)), idx):
+            if pair[0] == pair[1]:
+                print("   word3_muladd  (&%s, &%s, &%s, x[%2d], x[%2d]);" % (w2, w1, w0, pair[0], pair[1]))
+            elif i % 2 == 0:
+                print("   word3_muladd_2(&%s, &%s, &%s, x[%2d], x[%2d]);" % (w2, w1, w0, pair[0], pair[1]))
+
+        if rnd < 2*N-2:
+            print("   z[%2d] = %s; %s = 0;\n" % (rnd, w0, w0))
+        else:
+            print("   z[%2d] = %s;" % (rnd, w0))
+
+        (w0,w1,w2) = (w1,w2,w0)
+
+def main(args = None):
+    if args is None:
+        args = sys.argv
+
+    if len(args) <= 1:
+        sizes = [4, 6, 8, 9, 16, 24]
+    else:
+        sizes = map(int, args[1:])
+
+    print("""/*
+* Comba Multiplication and Squaring
+*
+* This file was automatically generated by %s on %s
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/mp_core.h>
+#include <botan/internal/mp_asmi.h>
+
+namespace Botan {
+""" % (sys.argv[0], datetime.date.today().strftime("%Y-%m-%d")))
+
+    for n in sizes:
+        print("/*\n* Comba %dx%d Squaring\n*/" % (n, n))
+        print("void bigint_comba_sqr%d(word z[%d], const word x[%d])" % (n, 2*n, n))
+        print("   {")
+        print("   word w2 = 0, w1 = 0, w0 = 0;\n")
+
+        comba_square_code(n)
+
+        print("   }\n")
+
+        print("/*\n* Comba %dx%d Multiplication\n*/" % (n, n))
+        print("void bigint_comba_mul%d(word z[%d], const word x[%d], const word y[%d])" % (n, 2*n, n, n))
+        print("   {")
+        print("   word w2 = 0, w1 = 0, w0 = 0;\n")
+
+        comba_multiply_code(n)
+
+        print("   }\n")
+
+    print("}")
+
+    return 0
+
+if __name__ == '__main__':
+    sys.exit(main())