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
//! Computes the shift needed to extract aligned top 64 bits from `r0`.
use super::GcdState;
impl GcdState {
/// Returns the bit shift needed to extract aligned top 64 bits from `r0`.
///
/// The Lehmer algorithm operates on 63-bit approximations of the
/// full-precision remainders. This method computes how many bits to
/// right-shift `r0` (and `r1` at the same offset) so that the extracted
/// value uses exactly 63 significant bits.
///
/// Returns `0` when `r0` fits in 64 bits, meaning the low limb can be
/// used directly without shifting.
#[inline]
pub fn top_bits_shift(&self) -> u32 {
let bits = self.r0.bit_len();
match bits <= 64 {
true => 0,
false => bits - 63,
}
}
}
#[cfg(test)]
mod ai_tests {
use crate::u256::U256;
use super::*;
/// Small r0 that fits in 64 bits returns shift of 0.
#[test]
fn small_r0() {
let state = GcdState::new(
U256::from_be_limbs([0, 0, 0, 100]),
U256::from_be_limbs([0, 0, 0, 37]),
);
assert_eq!(state.top_bits_shift(), 0);
}
/// r0 with exactly 64 bits returns shift of 0.
#[test]
fn exactly_64_bits() {
let state = GcdState::new(U256::from_be_limbs([0, 0, 0, u64::MAX]), U256::ONE);
assert_eq!(state.top_bits_shift(), 0);
}
/// r0 with 65 bits returns shift of 2.
#[test]
fn just_over_64_bits() {
let state = GcdState::new(U256::from_be_limbs([0, 0, 1, 0]), U256::ONE);
// bit_len = 65, shift = 65 - 63 = 2
assert_eq!(state.top_bits_shift(), 2);
}
/// r0 with 128 bits returns shift of 65.
#[test]
fn two_limbs() {
let state = GcdState::new(U256::from_be_limbs([0, 0, u64::MAX, 0]), U256::ONE);
// bit_len = 128, shift = 128 - 63 = 65
assert_eq!(state.top_bits_shift(), 65);
}
/// Full 256-bit r0 returns shift of 193.
#[test]
fn full_256_bits() {
let state = GcdState::new(U256::MAX, U256::ONE);
// bit_len = 256, shift = 256 - 63 = 193
assert_eq!(state.top_bits_shift(), 193);
}
/// secp256k1 prime (256 bits) returns shift of 193.
#[test]
fn secp256k1_prime() {
const P: U256 = U256::from_be_limbs([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFEFFFFFC2F]);
let state = GcdState::new(P, U256::ONE);
assert_eq!(state.top_bits_shift(), 193);
}
}