diff options
Diffstat (limited to 'comm/third_party/botan/src/scripts/monty.py')
-rwxr-xr-x | comm/third_party/botan/src/scripts/monty.py | 98 |
1 files changed, 98 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/scripts/monty.py b/comm/third_party/botan/src/scripts/monty.py new file mode 100755 index 0000000000..f253da3f67 --- /dev/null +++ b/comm/third_party/botan/src/scripts/monty.py @@ -0,0 +1,98 @@ +#!/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 + + if len(args) <= 1: + sizes = [4, 6, 8, 16, 24, 32] + else: + sizes = map(int, args[1:]) + + 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 sizes: + 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("}") + + return 0 + +if __name__ == '__main__': + sys.exit(main()) + + |