aboutsummaryrefslogtreecommitdiffstats
path: root/src/scripts/monty.py
blob: d3e9b5cb37e299e8f3c10f50b4e968a889a1aa39 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#!/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("}")

if __name__ == '__main__':
    sys.exit(main())