xref: /openssl/crypto/ec/curve448/arch_64/f_impl64.c (revision b6461792)
1 /*
2  * Copyright 2017-2024 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright 2014 Cryptography Research, Inc.
4  *
5  * Licensed under the Apache License 2.0 (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  *
10  * Originally written by Mike Hamburg
11  */
12 
13 #include "internal/e_os.h"
14 #include <openssl/macros.h>
15 #include "internal/numbers.h"
16 
17 #ifndef UINT128_MAX
18 /* No support for 128 bit ints, so do nothing here */
19 NON_EMPTY_TRANSLATION_UNIT
20 #else
21 
22 # include "../field.h"
23 
24 void ossl_gf_mul(gf_s * RESTRICT cs, const gf as, const gf bs)
25 {
26     const uint64_t *a = as->limb, *b = bs->limb;
27     uint64_t *c = cs->limb;
28     uint128_t accum0 = 0, accum1 = 0, accum2;
29     uint64_t mask = (1ULL << 56) - 1;
30     uint64_t aa[4], bb[4], bbb[4];
31     unsigned int i, j;
32 
33     for (i = 0; i < 4; i++) {
34         aa[i] = a[i] + a[i + 4];
35         bb[i] = b[i] + b[i + 4];
36         bbb[i] = bb[i] + b[i + 4];
37     }
38 
39     for (i = 0; i < 4; i++) {
40         accum2 = 0;
41 
42         for (j = 0; j <= i; j++) {
43             accum2 += widemul(a[j], b[i - j]);
44             accum1 += widemul(aa[j], bb[i - j]);
45             accum0 += widemul(a[j + 4], b[i - j + 4]);
46         }
47         for (; j < 4; j++) {
48             accum2 += widemul(a[j], b[i + 8 - j]);
49             accum1 += widemul(aa[j], bbb[i + 4 - j]);
50             accum0 += widemul(a[j + 4], bb[i + 4 - j]);
51         }
52 
53         accum1 -= accum2;
54         accum0 += accum2;
55 
56         c[i] = ((uint64_t)(accum0)) & mask;
57         c[i + 4] = ((uint64_t)(accum1)) & mask;
58 
59         accum0 >>= 56;
60         accum1 >>= 56;
61     }
62 
63     accum0 += accum1;
64     accum0 += c[4];
65     accum1 += c[0];
66     c[4] = ((uint64_t)(accum0)) & mask;
67     c[0] = ((uint64_t)(accum1)) & mask;
68 
69     accum0 >>= 56;
70     accum1 >>= 56;
71 
72     c[5] += ((uint64_t)(accum0));
73     c[1] += ((uint64_t)(accum1));
74 }
75 
76 void ossl_gf_mulw_unsigned(gf_s * RESTRICT cs, const gf as, uint32_t b)
77 {
78     const uint64_t *a = as->limb;
79     uint64_t *c = cs->limb;
80     uint128_t accum0 = 0, accum4 = 0;
81     uint64_t mask = (1ULL << 56) - 1;
82     int i;
83 
84     for (i = 0; i < 4; i++) {
85         accum0 += widemul(b, a[i]);
86         accum4 += widemul(b, a[i + 4]);
87         c[i] = accum0 & mask;
88         accum0 >>= 56;
89         c[i + 4] = accum4 & mask;
90         accum4 >>= 56;
91     }
92 
93     accum0 += accum4 + c[4];
94     c[4] = accum0 & mask;
95     c[5] += accum0 >> 56;
96 
97     accum4 += c[0];
98     c[0] = accum4 & mask;
99     c[1] += accum4 >> 56;
100 }
101 
102 void ossl_gf_sqr(gf_s * RESTRICT cs, const gf as)
103 {
104     const uint64_t *a = as->limb;
105     uint64_t *c = cs->limb;
106     uint128_t accum0 = 0, accum1 = 0, accum2;
107     uint64_t mask = (1ULL << 56) - 1;
108     uint64_t aa[4];
109     unsigned int i;
110 
111     /* For some reason clang doesn't vectorize this without prompting? */
112     for (i = 0; i < 4; i++)
113         aa[i] = a[i] + a[i + 4];
114 
115     accum2 = widemul(a[0], a[3]);
116     accum0 = widemul(aa[0], aa[3]);
117     accum1 = widemul(a[4], a[7]);
118 
119     accum2 += widemul(a[1], a[2]);
120     accum0 += widemul(aa[1], aa[2]);
121     accum1 += widemul(a[5], a[6]);
122 
123     accum0 -= accum2;
124     accum1 += accum2;
125 
126     c[3] = ((uint64_t)(accum1)) << 1 & mask;
127     c[7] = ((uint64_t)(accum0)) << 1 & mask;
128 
129     accum0 >>= 55;
130     accum1 >>= 55;
131 
132     accum0 += widemul(2 * aa[1], aa[3]);
133     accum1 += widemul(2 * a[5], a[7]);
134     accum0 += widemul(aa[2], aa[2]);
135     accum1 += accum0;
136 
137     accum0 -= widemul(2 * a[1], a[3]);
138     accum1 += widemul(a[6], a[6]);
139 
140     accum2 = widemul(a[0], a[0]);
141     accum1 -= accum2;
142     accum0 += accum2;
143 
144     accum0 -= widemul(a[2], a[2]);
145     accum1 += widemul(aa[0], aa[0]);
146     accum0 += widemul(a[4], a[4]);
147 
148     c[0] = ((uint64_t)(accum0)) & mask;
149     c[4] = ((uint64_t)(accum1)) & mask;
150 
151     accum0 >>= 56;
152     accum1 >>= 56;
153 
154     accum2 = widemul(2 * aa[2], aa[3]);
155     accum0 -= widemul(2 * a[2], a[3]);
156     accum1 += widemul(2 * a[6], a[7]);
157 
158     accum1 += accum2;
159     accum0 += accum2;
160 
161     accum2 = widemul(2 * a[0], a[1]);
162     accum1 += widemul(2 * aa[0], aa[1]);
163     accum0 += widemul(2 * a[4], a[5]);
164 
165     accum1 -= accum2;
166     accum0 += accum2;
167 
168     c[1] = ((uint64_t)(accum0)) & mask;
169     c[5] = ((uint64_t)(accum1)) & mask;
170 
171     accum0 >>= 56;
172     accum1 >>= 56;
173 
174     accum2 = widemul(aa[3], aa[3]);
175     accum0 -= widemul(a[3], a[3]);
176     accum1 += widemul(a[7], a[7]);
177 
178     accum1 += accum2;
179     accum0 += accum2;
180 
181     accum2 = widemul(2 * a[0], a[2]);
182     accum1 += widemul(2 * aa[0], aa[2]);
183     accum0 += widemul(2 * a[4], a[6]);
184 
185     accum2 += widemul(a[1], a[1]);
186     accum1 += widemul(aa[1], aa[1]);
187     accum0 += widemul(a[5], a[5]);
188 
189     accum1 -= accum2;
190     accum0 += accum2;
191 
192     c[2] = ((uint64_t)(accum0)) & mask;
193     c[6] = ((uint64_t)(accum1)) & mask;
194 
195     accum0 >>= 56;
196     accum1 >>= 56;
197 
198     accum0 += c[3];
199     accum1 += c[7];
200     c[3] = ((uint64_t)(accum0)) & mask;
201     c[7] = ((uint64_t)(accum1)) & mask;
202 
203     /* we could almost stop here, but it wouldn't be stable, so... */
204 
205     accum0 >>= 56;
206     accum1 >>= 56;
207     c[4] += ((uint64_t)(accum0)) + ((uint64_t)(accum1));
208     c[0] += ((uint64_t)(accum1));
209 }
210 #endif
211