CoCalc -- bn.c

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

GitHub Repository: hrydgard/ppsspp
Path: blob/master/ext/libkirk/bn.c
Views: ¹⁴⁰¹

1
// Copyright 2007-2022  Segher Boessenkool  <[email protected]>
2
// Licensed under the terms of the GNU GPL, either version 2 or version 3
3
// https://www.gnu.org/licenses/old-licenses/gpl-2.0.txt
4
// https://www.gnu.org/licenses/gpl-3.0.html
5
// Updated and simplified for use by Kirk Engine - July 2011
6

7
#include <string.h>
8
#include <stdio.h>
9

10
// Include definitions from kirk header
11
#include "kirk_engine.h"
12

13
void bn_print(char *name, u8 *a, u32 n)
14
{
15
	u32 i;
16

17
	printf("%s = ", name);
18

19
	for (i = 0; i < n; i++)
20
		printf("%02x", a[i]);
21

22
	printf("\n");
23
}
24

25
static void bn_zero(u8 *d, u32 n)
26
{
27
	memset(d, 0, n);
28
}
29

30
void bn_copy(u8 *d, u8 *a, u32 n)
31
{
32
	memcpy(d, a, n);
33
}
34

35
int bn_compare(u8 *a, u8 *b, u32 n)
36
{
37
	u32 i;
38

39
	for (i = 0; i < n; i++) {
40
		if (a[i] < b[i])
41
			return -1;
42
		if (a[i] > b[i])
43
			return 1;
44
	}
45

46
	return 0;
47
}
48

49
static u8 bn_add_1(u8 *d, u8 *a, u8 *b, u32 n)
50
{
51
	u32 i;
52
	u32 dig;
53
	u8 c;
54

55
	c = 0;
56
	for (i = n - 1; i < n; i--) {
57
		dig = a[i] + b[i] + c;
58
		c = dig >> 8;
59
		d[i] = dig;
60
	}
61

62
	return c;
63
}
64

65
static u8 bn_sub_1(u8 *d, u8 *a, u8 *b, u32 n)
66
{
67
	u32 i;
68
	u32 dig;
69
	u8 c;
70

71
	c = 1;
72
	for (i = n - 1; i < n; i--) {
73
		dig = a[i] + 255 - b[i] + c;
74
		c = dig >> 8;
75
		d[i] = dig;
76
	}
77

78
	return 1 - c;
79
}
80

81
void bn_reduce(u8 *d, u8 *N, u32 n)
82
{
83
	if (bn_compare(d, N, n) >= 0)
84
		bn_sub_1(d, d, N, n);
85
}
86

87
void bn_add(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
88
{
89
	if (bn_add_1(d, a, b, n))
90
		bn_sub_1(d, d, N, n);
91

92
	bn_reduce(d, N, n);
93
}
94

95
void bn_sub(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
96
{
97
	if (bn_sub_1(d, a, b, n))
98
		bn_add_1(d, d, N, n);
99
}
100

101
static const u8 inv256[0x80] = {
102
	0x01, 0xab, 0xcd, 0xb7, 0x39, 0xa3, 0xc5, 0xef,
103
	0xf1, 0x1b, 0x3d, 0xa7, 0x29, 0x13, 0x35, 0xdf,
104
	0xe1, 0x8b, 0xad, 0x97, 0x19, 0x83, 0xa5, 0xcf,
105
	0xd1, 0xfb, 0x1d, 0x87, 0x09, 0xf3, 0x15, 0xbf,
106
	0xc1, 0x6b, 0x8d, 0x77, 0xf9, 0x63, 0x85, 0xaf,
107
	0xb1, 0xdb, 0xfd, 0x67, 0xe9, 0xd3, 0xf5, 0x9f,
108
	0xa1, 0x4b, 0x6d, 0x57, 0xd9, 0x43, 0x65, 0x8f,
109
	0x91, 0xbb, 0xdd, 0x47, 0xc9, 0xb3, 0xd5, 0x7f,
110
	0x81, 0x2b, 0x4d, 0x37, 0xb9, 0x23, 0x45, 0x6f,
111
	0x71, 0x9b, 0xbd, 0x27, 0xa9, 0x93, 0xb5, 0x5f,
112
	0x61, 0x0b, 0x2d, 0x17, 0x99, 0x03, 0x25, 0x4f,
113
	0x51, 0x7b, 0x9d, 0x07, 0x89, 0x73, 0x95, 0x3f,
114
	0x41, 0xeb, 0x0d, 0xf7, 0x79, 0xe3, 0x05, 0x2f,
115
	0x31, 0x5b, 0x7d, 0xe7, 0x69, 0x53, 0x75, 0x1f,
116
	0x21, 0xcb, 0xed, 0xd7, 0x59, 0xc3, 0xe5, 0x0f,
117
	0x11, 0x3b, 0x5d, 0xc7, 0x49, 0x33, 0x55, 0xff,
118
};
119

120
static void bn_mon_muladd_dig(u8 *d, u8 *a, u8 b, u8 *N, u32 n)
121
{
122
	u32 dig;
123
	u32 i;
124

125
	u8 z = -(d[n-1] + a[n-1]*b) * inv256[N[n-1]/2];
126

127
	dig = d[n-1] + a[n-1]*b + N[n-1]*z;
128
	dig >>= 8;
129

130
	for (i = n - 2; i < n; i--) {
131
		dig += d[i] + a[i]*b + N[i]*z;
132
		d[i+1] = dig;
133
		dig >>= 8;
134
	}
135

136
	d[0] = dig;
137
	dig >>= 8;
138

139
	if (dig)
140
		bn_sub_1(d, d, N, n);
141

142
	bn_reduce(d, N, n);
143
}
144

145
void bn_mon_mul(u8 *d, u8 *a, u8 *b, u8 *N, u32 n)
146
{
147
	u8 t[512];
148
	u32 i;
149

150
	bn_zero(t, n);
151

152
	for (i = n - 1; i < n; i--)
153
		bn_mon_muladd_dig(t, a, b[i], N, n);
154

155
	bn_copy(d, t, n);
156
}
157

158
void bn_to_mon(u8 *d, u8 *N, u32 n)
159
{
160
	u32 i;
161

162
	for (i = 0; i < 8*n; i++)
163
		bn_add(d, d, d, N, n);
164
}
165

166
void bn_from_mon(u8 *d, u8 *N, u32 n)
167
{
168
	u8 t[512];
169

170
	bn_zero(t, n);
171
	t[n-1] = 1;
172
	bn_mon_mul(d, d, t, N, n);
173
}
174

175
static void bn_mon_exp(u8 *d, u8 *a, u8 *N, u32 n, u8 *e, u32 en)
176
{
177
	u8 t[512];
178
	u32 i;
179
	u8 mask;
180

181
	bn_zero(d, n);
182
	d[n-1] = 1;
183
	bn_to_mon(d, N, n);
184

185
	for (i = 0; i < en; i++)
186
		for (mask = 0x80; mask != 0; mask >>= 1) {
187
			bn_mon_mul(t, d, d, N, n);
188
			if ((e[i] & mask) != 0)
189
				bn_mon_mul(d, t, a, N, n);
190
			else
191
				bn_copy(d, t, n);
192
		}
193
}
194

195
void bn_mon_inv(u8 *d, u8 *a, u8 *N, u32 n)
196
{
197
	u8 t[512], s[512];
198

199
	bn_zero(s, n);
200
	s[n-1] = 2;
201
	bn_sub_1(t, N, s, n);
202
	bn_mon_exp(d, a, N, n, t, n);
203
}
204

205

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

Product

Resources

Company