1 //! Simple heap-allocated vector.
2 
3 #![cfg(feature = "alloc")]
4 #![doc(hidden)]
5 
6 use crate::bigint;
7 #[cfg(not(feature = "std"))]
8 use alloc::vec::Vec;
9 use core::{cmp, ops};
10 #[cfg(feature = "std")]
11 use std::vec::Vec;
12 
13 /// Simple heap vector implementation.
14 #[derive(Clone)]
15 pub struct HeapVec {
16     /// The heap-allocated buffer for the elements.
17     data: Vec<bigint::Limb>,
18 }
19 
20 #[allow(clippy::new_without_default)]
21 impl HeapVec {
22     /// Construct an empty vector.
23     #[inline]
new() -> Self24     pub fn new() -> Self {
25         Self {
26             data: Vec::with_capacity(bigint::BIGINT_LIMBS),
27         }
28     }
29 
30     /// Construct a vector from an existing slice.
31     #[inline]
try_from(x: &[bigint::Limb]) -> Option<Self>32     pub fn try_from(x: &[bigint::Limb]) -> Option<Self> {
33         let mut vec = Self::new();
34         vec.try_extend(x)?;
35         Some(vec)
36     }
37 
38     /// Sets the length of a vector.
39     ///
40     /// This will explicitly set the size of the vector, without actually
41     /// modifying its buffers, so it is up to the caller to ensure that the
42     /// vector is actually the specified size.
43     ///
44     /// # Safety
45     ///
46     /// Safe as long as `len` is less than `self.capacity()` and has been initialized.
47     #[inline]
set_len(&mut self, len: usize)48     pub unsafe fn set_len(&mut self, len: usize) {
49         debug_assert!(len <= bigint::BIGINT_LIMBS);
50         unsafe { self.data.set_len(len) };
51     }
52 
53     /// The number of elements stored in the vector.
54     #[inline]
len(&self) -> usize55     pub fn len(&self) -> usize {
56         self.data.len()
57     }
58 
59     /// If the vector is empty.
60     #[inline]
is_empty(&self) -> bool61     pub fn is_empty(&self) -> bool {
62         self.len() == 0
63     }
64 
65     /// The number of items the vector can hold.
66     #[inline]
capacity(&self) -> usize67     pub fn capacity(&self) -> usize {
68         self.data.capacity()
69     }
70 
71     /// Append an item to the vector.
72     #[inline]
try_push(&mut self, value: bigint::Limb) -> Option<()>73     pub fn try_push(&mut self, value: bigint::Limb) -> Option<()> {
74         self.data.push(value);
75         Some(())
76     }
77 
78     /// Remove an item from the end of the vector and return it, or None if empty.
79     #[inline]
pop(&mut self) -> Option<bigint::Limb>80     pub fn pop(&mut self) -> Option<bigint::Limb> {
81         self.data.pop()
82     }
83 
84     /// Copy elements from a slice and append them to the vector.
85     #[inline]
try_extend(&mut self, slc: &[bigint::Limb]) -> Option<()>86     pub fn try_extend(&mut self, slc: &[bigint::Limb]) -> Option<()> {
87         self.data.extend_from_slice(slc);
88         Some(())
89     }
90 
91     /// Try to resize the buffer.
92     ///
93     /// If the new length is smaller than the current length, truncate
94     /// the input. If it's larger, then append elements to the buffer.
95     #[inline]
try_resize(&mut self, len: usize, value: bigint::Limb) -> Option<()>96     pub fn try_resize(&mut self, len: usize, value: bigint::Limb) -> Option<()> {
97         self.data.resize(len, value);
98         Some(())
99     }
100 
101     // HI
102 
103     /// Get the high 64 bits from the vector.
104     #[inline(always)]
hi64(&self) -> (u64, bool)105     pub fn hi64(&self) -> (u64, bool) {
106         bigint::hi64(&self.data)
107     }
108 
109     // FROM
110 
111     /// Create StackVec from u64 value.
112     #[inline(always)]
from_u64(x: u64) -> Self113     pub fn from_u64(x: u64) -> Self {
114         bigint::from_u64(x)
115     }
116 
117     // MATH
118 
119     /// Normalize the integer, so any leading zero values are removed.
120     #[inline]
normalize(&mut self)121     pub fn normalize(&mut self) {
122         bigint::normalize(self)
123     }
124 
125     /// Get if the big integer is normalized.
126     #[inline]
is_normalized(&self) -> bool127     pub fn is_normalized(&self) -> bool {
128         bigint::is_normalized(self)
129     }
130 
131     /// AddAssign small integer.
132     #[inline]
add_small(&mut self, y: bigint::Limb) -> Option<()>133     pub fn add_small(&mut self, y: bigint::Limb) -> Option<()> {
134         bigint::small_add(self, y)
135     }
136 
137     /// MulAssign small integer.
138     #[inline]
mul_small(&mut self, y: bigint::Limb) -> Option<()>139     pub fn mul_small(&mut self, y: bigint::Limb) -> Option<()> {
140         bigint::small_mul(self, y)
141     }
142 }
143 
144 impl PartialEq for HeapVec {
145     #[inline]
146     #[allow(clippy::op_ref)]
eq(&self, other: &Self) -> bool147     fn eq(&self, other: &Self) -> bool {
148         use core::ops::Deref;
149         self.len() == other.len() && self.deref() == other.deref()
150     }
151 }
152 
153 impl Eq for HeapVec {
154 }
155 
156 impl cmp::PartialOrd for HeapVec {
157     #[inline]
partial_cmp(&self, other: &Self) -> Option<cmp::Ordering>158     fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
159         Some(bigint::compare(self, other))
160     }
161 }
162 
163 impl cmp::Ord for HeapVec {
164     #[inline]
cmp(&self, other: &Self) -> cmp::Ordering165     fn cmp(&self, other: &Self) -> cmp::Ordering {
166         bigint::compare(self, other)
167     }
168 }
169 
170 impl ops::Deref for HeapVec {
171     type Target = [bigint::Limb];
172     #[inline]
deref(&self) -> &[bigint::Limb]173     fn deref(&self) -> &[bigint::Limb] {
174         &self.data
175     }
176 }
177 
178 impl ops::DerefMut for HeapVec {
179     #[inline]
deref_mut(&mut self) -> &mut [bigint::Limb]180     fn deref_mut(&mut self) -> &mut [bigint::Limb] {
181         &mut self.data
182     }
183 }
184 
185 impl ops::MulAssign<&[bigint::Limb]> for HeapVec {
186     #[inline]
mul_assign(&mut self, rhs: &[bigint::Limb])187     fn mul_assign(&mut self, rhs: &[bigint::Limb]) {
188         bigint::large_mul(self, rhs).unwrap();
189     }
190 }
191