1 | // Copyright 2017-2023 Brian Smith. |
2 | // |
3 | // Permission to use, copy, modify, and/or distribute this software for any |
4 | // purpose with or without fee is hereby granted, provided that the above |
5 | // copyright notice and this permission notice appear in all copies. |
6 | // |
7 | // THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHORS DISCLAIM ALL WARRANTIES |
8 | // WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
9 | // MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY |
10 | // SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
11 | // WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
12 | // OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
13 | // CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
14 | |
15 | pub use super::n0::N0; |
16 | use crate::cpu; |
17 | |
18 | // Indicates that the element is not encoded; there is no *R* factor |
19 | // that needs to be canceled out. |
20 | #[derive (Copy, Clone)] |
21 | pub enum Unencoded {} |
22 | |
23 | // Indicates that the element is encoded; the value has one *R* |
24 | // factor that needs to be canceled out. |
25 | #[derive (Copy, Clone)] |
26 | pub enum R {} |
27 | |
28 | // Indicates the element is encoded three times; the value has three |
29 | // *R* factors that need to be canceled out. |
30 | #[allow (clippy::upper_case_acronyms)] |
31 | #[derive (Copy, Clone)] |
32 | pub enum RRR {} |
33 | |
34 | // Indicates the element is encoded twice; the value has two *R* |
35 | // factors that need to be canceled out. |
36 | #[derive (Copy, Clone)] |
37 | pub enum RR {} |
38 | |
39 | // Indicates the element is inversely encoded; the value has one |
40 | // 1/*R* factor that needs to be canceled out. |
41 | #[derive (Copy, Clone)] |
42 | pub enum RInverse {} |
43 | |
44 | pub trait Encoding {} |
45 | |
46 | impl Encoding for RRR {} |
47 | impl Encoding for RR {} |
48 | impl Encoding for R {} |
49 | impl Encoding for Unencoded {} |
50 | impl Encoding for RInverse {} |
51 | |
52 | /// The encoding of the result of a reduction. |
53 | pub trait ReductionEncoding { |
54 | type Output: Encoding; |
55 | } |
56 | |
57 | impl ReductionEncoding for RRR { |
58 | type Output = RR; |
59 | } |
60 | |
61 | impl ReductionEncoding for RR { |
62 | type Output = R; |
63 | } |
64 | impl ReductionEncoding for R { |
65 | type Output = Unencoded; |
66 | } |
67 | impl ReductionEncoding for Unencoded { |
68 | type Output = RInverse; |
69 | } |
70 | |
71 | /// The encoding of the result of a multiplication. |
72 | pub trait ProductEncoding { |
73 | type Output: Encoding; |
74 | } |
75 | |
76 | impl<E: ReductionEncoding> ProductEncoding for (Unencoded, E) { |
77 | type Output = E::Output; |
78 | } |
79 | |
80 | impl<E: Encoding> ProductEncoding for (R, E) { |
81 | type Output = E; |
82 | } |
83 | |
84 | impl ProductEncoding for (RR, RR) { |
85 | type Output = RRR; |
86 | } |
87 | |
88 | impl<E: ReductionEncoding> ProductEncoding for (RInverse, E) |
89 | where |
90 | E::Output: ReductionEncoding, |
91 | { |
92 | type Output = <<E as ReductionEncoding>::Output as ReductionEncoding>::Output; |
93 | } |
94 | |
95 | // XXX: Rust doesn't allow overlapping impls, |
96 | // TODO (if/when Rust allows it): |
97 | // impl<E1, E2: ReductionEncoding> ProductEncoding for |
98 | // (E1, E2) { |
99 | // type Output = <(E2, E1) as ProductEncoding>::Output; |
100 | // } |
101 | impl ProductEncoding for (RR, Unencoded) { |
102 | type Output = <(Unencoded, RR) as ProductEncoding>::Output; |
103 | } |
104 | impl ProductEncoding for (RR, RInverse) { |
105 | type Output = <(RInverse, RR) as ProductEncoding>::Output; |
106 | } |
107 | |
108 | impl ProductEncoding for (RRR, RInverse) { |
109 | type Output = <(RInverse, RRR) as ProductEncoding>::Output; |
110 | } |
111 | |
112 | #[allow (unused_imports)] |
113 | use crate::{bssl, c, limb::Limb}; |
114 | |
115 | #[inline (always)] |
116 | unsafe fn mul_mont( |
117 | r: *mut Limb, |
118 | a: *const Limb, |
119 | b: *const Limb, |
120 | n: *const Limb, |
121 | n0: &N0, |
122 | num_limbs: c::size_t, |
123 | _: cpu::Features, |
124 | ) { |
125 | bn_mul_mont(r, a, b, n, n0, num_limbs) |
126 | } |
127 | |
128 | #[cfg (not(any( |
129 | target_arch = "aarch64" , |
130 | target_arch = "arm" , |
131 | target_arch = "x86" , |
132 | target_arch = "x86_64" |
133 | )))] |
134 | // TODO: Stop calling this from C and un-export it. |
135 | #[allow (deprecated)] |
136 | prefixed_export! { |
137 | unsafe fn bn_mul_mont( |
138 | r: *mut Limb, |
139 | a: *const Limb, |
140 | b: *const Limb, |
141 | n: *const Limb, |
142 | n0: &N0, |
143 | num_limbs: c::size_t, |
144 | ) { |
145 | // The mutable pointer `r` may alias `a` and/or `b`, so the lifetimes of |
146 | // any slices for `a` or `b` must not overlap with the lifetime of any |
147 | // mutable for `r`. |
148 | |
149 | // Nothing aliases `n` |
150 | let n = unsafe { core::slice::from_raw_parts(n, num_limbs) }; |
151 | |
152 | let mut tmp = [0; 2 * super::BIGINT_MODULUS_MAX_LIMBS]; |
153 | let tmp = &mut tmp[..(2 * num_limbs)]; |
154 | { |
155 | let a: &[Limb] = unsafe { core::slice::from_raw_parts(a, num_limbs) }; |
156 | let b: &[Limb] = unsafe { core::slice::from_raw_parts(b, num_limbs) }; |
157 | limbs_mul(tmp, a, b); |
158 | } |
159 | let r: &mut [Limb] = unsafe { core::slice::from_raw_parts_mut(r, num_limbs) }; |
160 | limbs_from_mont_in_place(r, tmp, n, n0); |
161 | } |
162 | } |
163 | |
164 | // `bigint` needs then when the `alloc` feature is enabled. `bn_mul_mont` above needs this when |
165 | // we are using the platforms for which we don't have `bn_mul_mont` in assembly. |
166 | #[cfg (any( |
167 | feature = "alloc" , |
168 | not(any( |
169 | target_arch = "aarch64" , |
170 | target_arch = "arm" , |
171 | target_arch = "x86" , |
172 | target_arch = "x86_64" |
173 | )) |
174 | ))] |
175 | pub(super) fn limbs_from_mont_in_place(r: &mut [Limb], tmp: &mut [Limb], m: &[Limb], n0: &N0) { |
176 | prefixed_extern! { |
177 | fn bn_from_montgomery_in_place( |
178 | r: *mut Limb, |
179 | num_r: c::size_t, |
180 | a: *mut Limb, |
181 | num_a: c::size_t, |
182 | n: *const Limb, |
183 | num_n: c::size_t, |
184 | n0: &N0, |
185 | ) -> bssl::Result; |
186 | } |
187 | Result::from(unsafe { |
188 | bn_from_montgomery_in_place( |
189 | r.as_mut_ptr(), |
190 | r.len(), |
191 | tmp.as_mut_ptr(), |
192 | tmp.len(), |
193 | m.as_ptr(), |
194 | m.len(), |
195 | n0, |
196 | ) |
197 | }) |
198 | .unwrap() |
199 | } |
200 | |
201 | #[cfg (not(any( |
202 | target_arch = "aarch64" , |
203 | target_arch = "arm" , |
204 | target_arch = "x86" , |
205 | target_arch = "x86_64" |
206 | )))] |
207 | fn limbs_mul(r: &mut [Limb], a: &[Limb], b: &[Limb]) { |
208 | debug_assert_eq!(r.len(), 2 * a.len()); |
209 | debug_assert_eq!(a.len(), b.len()); |
210 | let ab_len = a.len(); |
211 | |
212 | r[..ab_len].fill(0); |
213 | for (i, &b_limb) in b.iter().enumerate() { |
214 | r[ab_len + i] = unsafe { |
215 | limbs_mul_add_limb(r[i..][..ab_len].as_mut_ptr(), a.as_ptr(), b_limb, ab_len) |
216 | }; |
217 | } |
218 | } |
219 | |
220 | #[cfg (any( |
221 | test, |
222 | not(any( |
223 | target_arch = "aarch64" , |
224 | target_arch = "arm" , |
225 | target_arch = "x86_64" , |
226 | target_arch = "x86" |
227 | )) |
228 | ))] |
229 | prefixed_extern! { |
230 | // `r` must not alias `a` |
231 | #[must_use ] |
232 | fn limbs_mul_add_limb(r: *mut Limb, a: *const Limb, b: Limb, num_limbs: c::size_t) -> Limb; |
233 | } |
234 | |
235 | #[cfg (any( |
236 | target_arch = "aarch64" , |
237 | target_arch = "arm" , |
238 | target_arch = "x86_64" , |
239 | target_arch = "x86" |
240 | ))] |
241 | prefixed_extern! { |
242 | // `r` and/or 'a' and/or 'b' may alias. |
243 | fn bn_mul_mont( |
244 | r: *mut Limb, |
245 | a: *const Limb, |
246 | b: *const Limb, |
247 | n: *const Limb, |
248 | n0: &N0, |
249 | num_limbs: c::size_t, |
250 | ); |
251 | } |
252 | |
253 | /// r *= a |
254 | pub(super) fn limbs_mont_mul( |
255 | r: &mut [Limb], |
256 | a: &[Limb], |
257 | m: &[Limb], |
258 | n0: &N0, |
259 | cpu_features: cpu::Features, |
260 | ) { |
261 | debug_assert_eq!(r.len(), m.len()); |
262 | debug_assert_eq!(a.len(), m.len()); |
263 | unsafe { |
264 | mul_mont( |
265 | r:r.as_mut_ptr(), |
266 | a:r.as_ptr(), |
267 | b:a.as_ptr(), |
268 | n:m.as_ptr(), |
269 | n0, |
270 | num_limbs:r.len(), |
271 | cpu_features, |
272 | ) |
273 | } |
274 | } |
275 | |
276 | /// r = a * b |
277 | #[cfg (not(target_arch = "x86_64" ))] |
278 | pub(super) fn limbs_mont_product( |
279 | r: &mut [Limb], |
280 | a: &[Limb], |
281 | b: &[Limb], |
282 | m: &[Limb], |
283 | n0: &N0, |
284 | cpu_features: cpu::Features, |
285 | ) { |
286 | debug_assert_eq!(r.len(), m.len()); |
287 | debug_assert_eq!(a.len(), m.len()); |
288 | debug_assert_eq!(b.len(), m.len()); |
289 | |
290 | unsafe { |
291 | mul_mont( |
292 | r.as_mut_ptr(), |
293 | a.as_ptr(), |
294 | b.as_ptr(), |
295 | m.as_ptr(), |
296 | n0, |
297 | r.len(), |
298 | cpu_features, |
299 | ) |
300 | } |
301 | } |
302 | |
303 | /// r = r**2 |
304 | pub(super) fn limbs_mont_square(r: &mut [Limb], m: &[Limb], n0: &N0, cpu_features: cpu::Features) { |
305 | debug_assert_eq!(r.len(), m.len()); |
306 | unsafe { |
307 | mul_mont( |
308 | r:r.as_mut_ptr(), |
309 | a:r.as_ptr(), |
310 | b:r.as_ptr(), |
311 | n:m.as_ptr(), |
312 | n0, |
313 | num_limbs:r.len(), |
314 | cpu_features, |
315 | ) |
316 | } |
317 | } |
318 | #[cfg (test)] |
319 | mod tests { |
320 | use super::*; |
321 | use crate::limb::Limb; |
322 | |
323 | #[test ] |
324 | // TODO: wasm |
325 | fn test_mul_add_words() { |
326 | const ZERO: Limb = 0; |
327 | const MAX: Limb = ZERO.wrapping_sub(1); |
328 | static TEST_CASES: &[(&[Limb], &[Limb], Limb, Limb, &[Limb])] = &[ |
329 | (&[0], &[0], 0, 0, &[0]), |
330 | (&[MAX], &[0], MAX, 0, &[MAX]), |
331 | (&[0], &[MAX], MAX, MAX - 1, &[1]), |
332 | (&[MAX], &[MAX], MAX, MAX, &[0]), |
333 | (&[0, 0], &[MAX, MAX], MAX, MAX - 1, &[1, MAX]), |
334 | (&[1, 0], &[MAX, MAX], MAX, MAX - 1, &[2, MAX]), |
335 | (&[MAX, 0], &[MAX, MAX], MAX, MAX, &[0, 0]), |
336 | (&[0, 1], &[MAX, MAX], MAX, MAX, &[1, 0]), |
337 | (&[MAX, MAX], &[MAX, MAX], MAX, MAX, &[0, MAX]), |
338 | ]; |
339 | |
340 | for (i, (r_input, a, w, expected_retval, expected_r)) in TEST_CASES.iter().enumerate() { |
341 | let mut r = [0; super::super::BIGINT_MODULUS_MAX_LIMBS]; |
342 | let r = { |
343 | let r = &mut r[..r_input.len()]; |
344 | r.copy_from_slice(r_input); |
345 | r |
346 | }; |
347 | assert_eq!(r.len(), a.len()); // Sanity check |
348 | let actual_retval = |
349 | unsafe { limbs_mul_add_limb(r.as_mut_ptr(), a.as_ptr(), *w, a.len()) }; |
350 | assert_eq!(&r, expected_r, " {}: {:x?} != {:x?}" , i, r, expected_r); |
351 | assert_eq!( |
352 | actual_retval, *expected_retval, |
353 | " {}: {:x?} != {:x?}" , |
354 | i, actual_retval, *expected_retval |
355 | ); |
356 | } |
357 | } |
358 | } |
359 | |