chiark / gitweb /
math/pgen.c: Don't free the tester if it's not set up.
[catacomb] / math / scmul.h
CommitLineData
581ac808
MW
1/* -*-c-*-
2 *
3 * Scalar multiplication on elliptic curves
4 *
5 * (c) 2017 Straylight/Edgeware
6 */
7
8/*----- Licensing notice --------------------------------------------------*
9 *
10 * This file is part of Catacomb.
11 *
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
16 *
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
21 *
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
25 * MA 02111-1307, USA.
26 */
27
28#ifndef CATACOMB_SCMUL_H
29#define CATACOMB_SCMUL_H
30
31#ifdef __cplusplus
32 extern "C" {
33#endif
34
35/*----- Macros provided ---------------------------------------------------*/
36
37#define SCMUL_WINLIM(winwd) (1 << (winwd))
38#define SCMUL_WINMASK(winwd) (SCMUL_WINLIM(winwd) - 1)
39#define SCMUL_TABSZ(winwd) (SCMUL_WINLIM(winwd)/2 + 1)
40
41#define DEFINE_SCMUL(mulfn, f, winwd, scafwd, npiece, addfn, dblfn) \
42void mulfn(f *X, f *Y, f *Z, const scaf_piece n[npiece], \
43 const f *X0, const f *Y0, const f *Z0) \
44{ \
45 f VX[SCMUL_TABSZ(winwd)], \
46 VY[SCMUL_TABSZ(winwd)], \
47 VZ[SCMUL_TABSZ(winwd)]; \
48 f TX, TY, TZ, UX, UY, UZ; \
49 unsigned i, j, k, w; \
50 uint32 m_neg; \
51 scaf_piece ni; \
52 \
53 /* Build a table of small multiples. */ \
54 f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1); \
55 VX[1] = *X0; VY[1] = *Y0; VZ[1] = *Z0; \
56 ptdbl(&VX[2], &VY[2], &VZ[2], &VX[1], &VY[1], &VZ[1]); \
57 for (i = 3; i < SCMUL_TABSZ(winwd); i += 2) { \
58 addfn(&VX[i], &VY[i], &VZ[i], \
59 &VX[i - 1], &VY[i - 1], &VZ[i - 1], X0, Y0, Z0); \
60 dblfn(&VX[i + 1], &VY[i + 1], &VZ[i + 1], \
61 &VX[(i + 1)/2], &VY[(i + 1)/2], &VZ[(i + 1)/2]); \
62 } \
63 \
64 /* Now do the multiplication. We lag a window behind the cursor \
65 * position because of the scalar recoding we do. \
66 */ \
67 f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1); \
68 for (i = (npiece), w = 0, m_neg = 0; i--; ) { \
69 ni = n[i]; \
70 \
71 /* Work through each window in the scalar piece. */ \
72 for (j = 0; j < (scafwd); j += (winwd)) { \
73 \
74 /* Shift along by a window. */ \
75 for (k = 0; k < (winwd); k++) \
76 dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
77 \
78 /* Peek at the next window of four bits. If the top bit is set \
79 * we lend a bit leftwards, into w. It's too late for this to \
80 * affect the sign now, but if we negated earlier then the \
81 * addition would be wrong. \
82 */ \
83 w += (ni >> ((scafwd) - 1))&0x1u; \
84 w = ((SCMUL_WINLIM(winwd) - w)&m_neg) | (w&~m_neg); \
85 \
86 /* Collect the entry from the table, and add or subtract. */ \
87 f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w); \
88 f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w); \
89 f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w); \
90 f##_condneg(&UX, &UX, m_neg); \
91 addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); \
92 \
93 /* Move the next window into the delay slot. If its top bit is \
94 * set, then negate it and set m_neg. \
95 */ \
96 w = (ni >> ((scafwd) - (winwd)))&SCMUL_WINMASK(winwd); \
97 m_neg = -(uint32)((w >> ((winwd) - 1))&0x1u); \
98 ni <<= (winwd); \
99 } \
100 } \
101 \
102 /* Do the final window. Just fix the sign and go. */ \
103 for (k = 0; k < (winwd); k++) \
104 dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
105 w = ((SCMUL_WINLIM(winwd) - w)&m_neg) | (w&~m_neg); \
106 f##_pickn(&UX, VX, SCMUL_TABSZ(winwd), w); \
107 f##_pickn(&UY, VY, SCMUL_TABSZ(winwd), w); \
108 f##_pickn(&UZ, VZ, SCMUL_TABSZ(winwd), w); \
109 f##_condneg(&UX, &UX, m_neg); \
110 addfn(X, Y, Z, &TX, &TY, &TZ, &UX, &UY, &UZ); \
111}
112
113#define SCSIMMUL_WINLIM(winwd) (1 << (winwd))
114#define SCSIMMUL_WINMASK(winwd) (SCSIMMUL_WINLIM(winwd) - 1)
115#define SCSIMMUL_TABSZ(winwd) (1 << 2*(winwd))
116
117#define DEFINE_SCSIMMUL(simmulfn, f, winwd, \
118 scafwd, npiece, addfn, dblfn) \
119void simmulfn(f *X, f *Y, f *Z, \
120 const scaf_piece n0[npiece], \
121 const f *X0, const f *Y0, const f *Z0, \
122 const scaf_piece n1[npiece], \
123 const f *X1, const f *Y1, const f *Z1) \
124{ \
125 f VX[SCSIMMUL_TABSZ(winwd)], \
126 VY[SCSIMMUL_TABSZ(winwd)], \
127 VZ[SCSIMMUL_TABSZ(winwd)]; \
128 f TX, TY, TZ, UX, UY, UZ; \
129 unsigned i, j, k, w, ni0, ni1; \
130 \
131 /* Build a table of small linear combinations. */ \
132 f##_set(&VX[0], 0); f##_set(&VY[0], 1); f##_set(&VZ[0], 1); \
133 VX[1] = *X0; VX[SCSIMMUL_WINLIM(winwd)] = *X1; \
134 VY[1] = *Y0; VY[SCSIMMUL_WINLIM(winwd)] = *Y1; \
135 VZ[1] = *Z0; VZ[SCSIMMUL_WINLIM(winwd)] = *Z1; \
136 for (i = 2; i < SCSIMMUL_WINLIM(winwd); i <<= 1) { \
137 dblfn(&VX[i], &VY[i], &VZ[i], \
138 &VX[i/2], &VY[i/2], &VZ[i/2]); \
139 dblfn(&VX[i*SCSIMMUL_WINLIM(winwd)], \
140 &VY[i*SCSIMMUL_WINLIM(winwd)], \
141 &VZ[i*SCSIMMUL_WINLIM(winwd)], \
142 &VX[i*SCSIMMUL_WINLIM(winwd)/2], \
143 &VY[i*SCSIMMUL_WINLIM(winwd)/2], \
144 &VZ[i*SCSIMMUL_WINLIM(winwd)/2]); \
145 } \
146 for (i = 2; i < SCSIMMUL_TABSZ(winwd); i <<= 1) { \
147 for (j = 1; j < i; j++) \
148 addfn(&VX[i + j], &VY[i + j], &VZ[i + j], \
149 &VX[i], &VY[i], &VZ[i], &VX[j], &VY[j], &VZ[j]); \
150 } \
151 \
152 /* Do the multiplication. */ \
153 f##_set(&TX, 0); f##_set(&TY, 1); f##_set(&TZ, 1); \
154 for (i = (npiece); i--; ) { \
155 ni0 = n0[i]; ni1 = n1[i]; \
156 \
157 /* Work through each window in the scalar pieces. */ \
158 for (j = 0; j < (scafwd); j += (winwd)) { \
159 \
160 /* Shift along by a window. */ \
161 for (k = 0; k < (winwd); k++) \
162 dblfn(&TX, &TY, &TZ, &TX, &TY, &TZ); \
163 \
164 /* Collect the next window from the scalars. */ \
165 w = (((ni0 >> ((scafwd) - (winwd)))& \
166 SCSIMMUL_WINMASK(winwd)) | \
167 ((ni1 >> ((scafwd) - 2*(winwd)))& \
168 (SCSIMMUL_WINMASK(winwd) << (winwd)))); \
169 ni0 <<= (winwd); ni1 <<= (winwd); \
170 \
171 /* Collect the entry from the table, and add. */ \
172 f##_pickn(&UX, VX, SCSIMMUL_TABSZ(winwd), w); \
173 f##_pickn(&UY, VY, SCSIMMUL_TABSZ(winwd), w); \
174 f##_pickn(&UZ, VZ, SCSIMMUL_TABSZ(winwd), w); \
175 addfn(&TX, &TY, &TZ, &TX, &TY, &TZ, &UX, &UY, &UZ); \
176 } \
177 } \
178 \
179 /* Done. */ \
180 *X = TX; *Y = TY; *Z = TZ; \
181}
182
183/*----- That's all, folks -------------------------------------------------*/
184
185#ifdef __cplusplus
186 }
187#endif
188
189#endif