bitcoin/util/
uint.rs

1// Rust Bitcoin Library
2// Written in 2014 by
3//     Andrew Poelstra <apoelstra@wpsoftware.net>
4//
5// To the extent possible under law, the author(s) have dedicated all
6// copyright and related and neighboring rights to this software to
7// the public domain worldwide. This software is distributed without
8// any warranty.
9//
10// You should have received a copy of the CC0 Public Domain Dedication
11// along with this software.
12// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
13//
14
15//! Big unsigned integer types
16//!
17//! Implementation of a various large-but-fixed sized unsigned integer types.
18//! The functions here are designed to be fast.
19//!
20
21use std::fmt;
22
23use consensus::encode;
24use util::BitArray;
25
26macro_rules! construct_uint {
27    ($name:ident, $n_words:expr) => (
28        /// Little-endian large integer type
29        #[repr(C)]
30        pub struct $name(pub [u64; $n_words]);
31        impl_array_newtype!($name, u64, $n_words);
32
33        impl $name {
34            /// Conversion to u32
35            #[inline]
36            pub fn low_u32(&self) -> u32 {
37                let &$name(ref arr) = self;
38                arr[0] as u32
39            }
40
41            /// Conversion to u64
42            #[inline]
43            pub fn low_u64(&self) -> u64 {
44                let &$name(ref arr) = self;
45                arr[0] as u64
46            }
47
48
49            /// Return the least number of bits needed to represent the number
50            #[inline]
51            pub fn bits(&self) -> usize {
52                let &$name(ref arr) = self;
53                for i in 1..$n_words {
54                    if arr[$n_words - i] > 0 { return (0x40 * ($n_words - i + 1)) - arr[$n_words - i].leading_zeros() as usize; }
55                }
56                0x40 - arr[0].leading_zeros() as usize
57            }
58
59            /// Multiplication by u32
60            pub fn mul_u32(self, other: u32) -> $name {
61                let $name(ref arr) = self;
62                let mut carry = [0u64; $n_words];
63                let mut ret = [0u64; $n_words];
64                for i in 0..$n_words {
65                    let not_last_word = i < $n_words - 1;
66                    let upper = other as u64 * (arr[i] >> 32);
67                    let lower = other as u64 * (arr[i] & 0xFFFFFFFF);
68                    if not_last_word {
69                        carry[i + 1] += upper >> 32;
70                    }
71                    let (sum, overflow) = lower.overflowing_add(upper << 32);
72                    ret[i] = sum;
73                    if overflow && not_last_word {
74                        carry[i + 1] += 1;
75                    }
76                }
77                $name(ret) + $name(carry)
78            }
79
80            /// Create an object from a given unsigned 64-bit integer
81            pub fn from_u64(init: u64) -> Option<$name> {
82                let mut ret = [0; $n_words];
83                ret[0] = init;
84                Some($name(ret))
85            }
86
87            /// Create an object from a given signed 64-bit integer
88            pub fn from_i64(init: i64) -> Option<$name> {
89                assert!(init >= 0);
90                $name::from_u64(init as u64)
91            }
92        }
93
94        impl ::std::ops::Add<$name> for $name {
95            type Output = $name;
96
97            fn add(self, other: $name) -> $name {
98                let $name(ref me) = self;
99                let $name(ref you) = other;
100                let mut ret = [0u64; $n_words];
101                let mut carry = [0u64; $n_words];
102                let mut b_carry = false;
103                for i in 0..$n_words {
104                    ret[i] = me[i].wrapping_add(you[i]);
105                    if i < $n_words - 1 && ret[i] < me[i] {
106                        carry[i + 1] = 1;
107                        b_carry = true;
108                    }
109                }
110                if b_carry { $name(ret) + $name(carry) } else { $name(ret) }
111            }
112        }
113
114        impl ::std::ops::Sub<$name> for $name {
115            type Output = $name;
116
117            #[inline]
118            fn sub(self, other: $name) -> $name {
119                self + !other + BitArray::one()
120            }
121        }
122
123        impl ::std::ops::Mul<$name> for $name {
124            type Output = $name;
125
126            fn mul(self, other: $name) -> $name {
127                let mut me = $name::zero();
128                // TODO: be more efficient about this
129                for i in 0..(2 * $n_words) {
130                    let to_mul = (other >> (32 * i)).low_u32();
131                    me = me + (self.mul_u32(to_mul) << (32 * i));
132                }
133                me
134            }
135        }
136
137        impl ::std::ops::Div<$name> for $name {
138            type Output = $name;
139
140            fn div(self, other: $name) -> $name {
141                let mut sub_copy = self;
142                let mut shift_copy = other;
143                let mut ret = [0u64; $n_words];
144        
145                let my_bits = self.bits();
146                let your_bits = other.bits();
147
148                // Check for division by 0
149                assert!(your_bits != 0);
150
151                // Early return in case we are dividing by a larger number than us
152                if my_bits < your_bits {
153                    return $name(ret);
154                }
155
156                // Bitwise long division
157                let mut shift = my_bits - your_bits;
158                shift_copy = shift_copy << shift;
159                loop {
160                    if sub_copy >= shift_copy {
161                        ret[shift / 64] |= 1 << (shift % 64);
162                        sub_copy = sub_copy - shift_copy;
163                    }
164                    shift_copy = shift_copy >> 1;
165                    if shift == 0 { break; }
166                    shift -= 1;
167                }
168
169                $name(ret)
170            }
171        }
172
173        impl BitArray for $name {
174            #[inline]
175            fn bit(&self, index: usize) -> bool {
176                let &$name(ref arr) = self;
177                arr[index / 64] & (1 << (index % 64)) != 0
178            }
179
180            #[inline]
181            fn bit_slice(&self, start: usize, end: usize) -> $name {
182                (*self >> start).mask(end - start)
183            }
184
185            #[inline]
186            fn mask(&self, n: usize) -> $name {
187                let &$name(ref arr) = self;
188                let mut ret = [0; $n_words];
189                for i in 0..$n_words {
190                    if n >= 0x40 * (i + 1) {
191                        ret[i] = arr[i];
192                    } else {
193                        ret[i] = arr[i] & ((1 << (n - 0x40 * i)) - 1);
194                        break;
195                    }
196                }
197                $name(ret)
198            }
199
200            #[inline]
201            fn trailing_zeros(&self) -> usize {
202                let &$name(ref arr) = self;
203                for i in 0..($n_words - 1) {
204                    if arr[i] > 0 { return (0x40 * i) + arr[i].trailing_zeros() as usize; }
205                }
206                (0x40 * ($n_words - 1)) + arr[$n_words - 1].trailing_zeros() as usize
207            }
208
209            fn zero() -> $name { $name([0; $n_words]) }
210            fn one() -> $name {
211                $name({ let mut ret = [0; $n_words]; ret[0] = 1; ret })
212            }
213        }
214
215        impl ::std::default::Default for $name {
216            fn default() -> $name {
217                BitArray::zero()
218            }
219        }
220
221        impl ::std::ops::BitAnd<$name> for $name {
222            type Output = $name;
223
224            #[inline]
225            fn bitand(self, other: $name) -> $name {
226                let $name(ref arr1) = self;
227                let $name(ref arr2) = other;
228                let mut ret = [0u64; $n_words];
229                for i in 0..$n_words {
230                    ret[i] = arr1[i] & arr2[i];
231                }
232                $name(ret)
233            }
234        }
235
236        impl ::std::ops::BitXor<$name> for $name {
237            type Output = $name;
238
239            #[inline]
240            fn bitxor(self, other: $name) -> $name {
241                let $name(ref arr1) = self;
242                let $name(ref arr2) = other;
243                let mut ret = [0u64; $n_words];
244                for i in 0..$n_words {
245                    ret[i] = arr1[i] ^ arr2[i];
246                }
247                $name(ret)
248            }
249        }
250
251        impl ::std::ops::BitOr<$name> for $name {
252            type Output = $name;
253
254            #[inline]
255            fn bitor(self, other: $name) -> $name {
256                let $name(ref arr1) = self;
257                let $name(ref arr2) = other;
258                let mut ret = [0u64; $n_words];
259                for i in 0..$n_words {
260                    ret[i] = arr1[i] | arr2[i];
261                }
262                $name(ret)
263            }
264        }
265
266        impl ::std::ops::Not for $name {
267            type Output = $name;
268
269            #[inline]
270            fn not(self) -> $name {
271                let $name(ref arr) = self;
272                let mut ret = [0u64; $n_words];
273                for i in 0..$n_words {
274                    ret[i] = !arr[i];
275                }
276                $name(ret)
277            }
278        }
279
280        impl ::std::ops::Shl<usize> for $name {
281            type Output = $name;
282
283            fn shl(self, shift: usize) -> $name {
284                let $name(ref original) = self;
285                let mut ret = [0u64; $n_words];
286                let word_shift = shift / 64;
287                let bit_shift = shift % 64;
288                for i in 0..$n_words {
289                    // Shift
290                    if bit_shift < 64 && i + word_shift < $n_words {
291                        ret[i + word_shift] += original[i] << bit_shift;
292                    }
293                    // Carry
294                    if bit_shift > 0 && i + word_shift + 1 < $n_words {
295                        ret[i + word_shift + 1] += original[i] >> (64 - bit_shift);
296                    }
297                }
298                $name(ret)
299            }
300        }
301
302        impl ::std::ops::Shr<usize> for $name {
303            type Output = $name;
304
305            fn shr(self, shift: usize) -> $name {
306                let $name(ref original) = self;
307                let mut ret = [0u64; $n_words];
308                let word_shift = shift / 64;
309                let bit_shift = shift % 64;
310                for i in word_shift..$n_words {
311                    // Shift
312                    ret[i - word_shift] += original[i] >> bit_shift;
313                    // Carry
314                    if bit_shift > 0 && i < $n_words - 1 {
315                        ret[i - word_shift] += original[i + 1] << (64 - bit_shift);
316                    }
317                }
318                $name(ret)
319            }
320        }
321
322        impl fmt::Debug for $name {
323            fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
324                let &$name(ref data) = self;
325                write!(f, "0x")?;
326                for ch in data.iter().rev() {
327                    write!(f, "{:016x}", ch)?;
328                }
329                Ok(())
330            }
331        }
332
333        impl fmt::Display for $name {
334            fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
335                <fmt::Debug>::fmt(self, f)
336            }
337        }
338
339        impl<S: ::consensus::encode::Encoder> ::consensus::encode::Encodable<S> for $name {
340            #[inline]
341            fn consensus_encode(&self, s: &mut S) -> Result<(), encode::Error> {
342                let &$name(ref data) = self;
343                for word in data.iter() { word.consensus_encode(s)?; }
344                Ok(())
345            }
346        }
347
348        impl<D: ::consensus::encode::Decoder> ::consensus::encode::Decodable<D> for $name {
349            fn consensus_decode(d: &mut D) -> Result<$name, encode::Error> {
350                use consensus::encode::Decodable;
351                let ret: [u64; $n_words] = Decodable::consensus_decode(d)?;
352                Ok($name(ret))
353            }
354        }
355    );
356}
357
358construct_uint!(Uint256, 4);
359construct_uint!(Uint128, 2);
360
361impl Uint256 {
362    /// Increment by 1
363    #[inline]
364    pub fn increment(&mut self) {
365        let &mut Uint256(ref mut arr) = self;
366        arr[0] += 1;
367        if arr[0] == 0 {
368            arr[1] += 1;
369            if arr[1] == 0 {
370                arr[2] += 1;
371                if arr[2] == 0 {
372                    arr[3] += 1;
373                }
374            }
375        }
376    }
377
378    /// Decay to a uint128
379    #[inline]
380    pub fn low_128(&self) -> Uint128 {
381        let &Uint256(data) = self;
382        Uint128([data[0], data[1]])
383    }
384}
385
386#[cfg(test)]
387mod tests {
388    use consensus::encode::{deserialize, serialize};
389    use util::uint::Uint256;
390    use util::BitArray;
391
392    #[test]
393    pub fn uint256_bits_test() {
394        assert_eq!(Uint256::from_u64(255).unwrap().bits(), 8);
395        assert_eq!(Uint256::from_u64(256).unwrap().bits(), 9);
396        assert_eq!(Uint256::from_u64(300).unwrap().bits(), 9);
397        assert_eq!(Uint256::from_u64(60000).unwrap().bits(), 16);
398        assert_eq!(Uint256::from_u64(70000).unwrap().bits(), 17);
399
400        // Try to read the following lines out loud quickly
401        let mut shl = Uint256::from_u64(70000).unwrap();
402        shl = shl << 100;
403        assert_eq!(shl.bits(), 117);
404        shl = shl << 100;
405        assert_eq!(shl.bits(), 217);
406        shl = shl << 100;
407        assert_eq!(shl.bits(), 0);
408
409        // Bit set check
410        assert!(!Uint256::from_u64(10).unwrap().bit(0));
411        assert!(Uint256::from_u64(10).unwrap().bit(1));
412        assert!(!Uint256::from_u64(10).unwrap().bit(2));
413        assert!(Uint256::from_u64(10).unwrap().bit(3));
414        assert!(!Uint256::from_u64(10).unwrap().bit(4));
415    }
416
417    #[test]
418    pub fn uint256_display_test() {
419        assert_eq!(format!("{}", Uint256::from_u64(0xDEADBEEF).unwrap()),
420                   "0x00000000000000000000000000000000000000000000000000000000deadbeef");
421        assert_eq!(format!("{}", Uint256::from_u64(u64::max_value()).unwrap()),
422                   "0x000000000000000000000000000000000000000000000000ffffffffffffffff");
423
424        let max_val = Uint256([0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
425                               0xFFFFFFFFFFFFFFFF]);
426        assert_eq!(format!("{}", max_val),
427                   "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff");
428    }
429
430    #[test]
431    pub fn uint256_comp_test() {
432        let small = Uint256([10u64, 0, 0, 0]);
433        let big = Uint256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]);
434        let bigger = Uint256([0x9C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]);
435        let biggest = Uint256([0x5C8C3EE70C644118u64, 0x0209E7378231E632, 0, 1]);
436
437        assert!(small < big);
438        assert!(big < bigger);
439        assert!(bigger < biggest);
440        assert!(bigger <= biggest);
441        assert!(biggest <= biggest);
442        assert!(bigger >= big);
443        assert!(bigger >= small);
444        assert!(small <= small);
445    }
446
447    #[test]
448    pub fn uint256_arithmetic_test() {
449        let init = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
450        let copy = init;
451
452        let add = init + copy;
453        assert_eq!(add, Uint256([0xBD5B7DDFBD5B7DDEu64, 1, 0, 0]));
454        // Bitshifts
455        let shl = add << 88;
456        assert_eq!(shl, Uint256([0u64, 0xDFBD5B7DDE000000, 0x1BD5B7D, 0]));
457        let shr = shl >> 40;
458        assert_eq!(shr, Uint256([0x7DDE000000000000u64, 0x0001BD5B7DDFBD5B, 0, 0]));
459        // Increment
460        let mut incr = shr;
461        incr.increment();
462        assert_eq!(incr, Uint256([0x7DDE000000000001u64, 0x0001BD5B7DDFBD5B, 0, 0]));
463        // Subtraction
464        let sub = incr - init;
465        assert_eq!(sub, Uint256([0x9F30411021524112u64, 0x0001BD5B7DDFBD5A, 0, 0]));
466        // Multiplication
467        let mult = sub.mul_u32(300);
468        assert_eq!(mult, Uint256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]));
469        // Division
470        assert_eq!(Uint256::from_u64(105).unwrap() /
471                   Uint256::from_u64(5).unwrap(),
472                   Uint256::from_u64(21).unwrap());
473        let div = mult / Uint256::from_u64(300).unwrap();
474        assert_eq!(div, Uint256([0x9F30411021524112u64, 0x0001BD5B7DDFBD5A, 0, 0]));
475        // TODO: bit inversion
476    }
477
478    #[test]
479    pub fn mul_u32_test() {
480        let u64_val = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
481
482        let u96_res = u64_val.mul_u32(0xFFFFFFFF);
483        let u128_res = u96_res.mul_u32(0xFFFFFFFF);
484        let u160_res = u128_res.mul_u32(0xFFFFFFFF);
485        let u192_res = u160_res.mul_u32(0xFFFFFFFF);
486        let u224_res = u192_res.mul_u32(0xFFFFFFFF);
487        let u256_res = u224_res.mul_u32(0xFFFFFFFF);
488
489        assert_eq!(u96_res, Uint256([0xffffffff21524111u64, 0xDEADBEEE, 0, 0]));
490        assert_eq!(u128_res, Uint256([0x21524111DEADBEEFu64, 0xDEADBEEE21524110, 0, 0]));
491        assert_eq!(u160_res, Uint256([0xBD5B7DDD21524111u64, 0x42A4822200000001, 0xDEADBEED, 0]));
492        assert_eq!(u192_res, Uint256([0x63F6C333DEADBEEFu64, 0xBD5B7DDFBD5B7DDB, 0xDEADBEEC63F6C334, 0]));
493        assert_eq!(u224_res, Uint256([0x7AB6FBBB21524111u64, 0xFFFFFFFBA69B4558, 0x854904485964BAAA, 0xDEADBEEB]));
494        assert_eq!(u256_res, Uint256([0xA69B4555DEADBEEFu64, 0xA69B455CD41BB662, 0xD41BB662A69B4550, 0xDEADBEEAA69B455C]));
495    }
496
497    #[test]
498    pub fn multiplication_test() {
499        let u64_val = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
500
501        let u128_res = u64_val * u64_val;
502
503        assert_eq!(u128_res, Uint256([0x048D1354216DA321u64, 0xC1B1CD13A4D13D46, 0, 0]));
504
505        let u256_res = u128_res * u128_res;
506
507        assert_eq!(u256_res, Uint256([0xF4E166AAD40D0A41u64, 0xF5CF7F3618C2C886u64,
508                                      0x4AFCFF6F0375C608u64, 0x928D92B4D7F5DF33u64]));
509    }
510
511    #[test]
512    pub fn uint256_bitslice_test() {
513        let init = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
514        let add = init + (init << 64);
515        assert_eq!(add.bit_slice(64, 128), init);
516        assert_eq!(add.mask(64), init);
517    }
518
519    #[test]
520    pub fn uint256_extreme_bitshift_test() {
521        // Shifting a u64 by 64 bits gives an undefined value, so make sure that
522        // we're doing the Right Thing here
523        let init = Uint256::from_u64(0xDEADBEEFDEADBEEF).unwrap();
524
525        assert_eq!(init << 64, Uint256([0, 0xDEADBEEFDEADBEEF, 0, 0]));
526        let add = (init << 64) + init;
527        assert_eq!(add, Uint256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0]));
528        assert_eq!(add >> 0, Uint256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0]));
529        assert_eq!(add << 0, Uint256([0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0, 0]));
530        assert_eq!(add >> 64, Uint256([0xDEADBEEFDEADBEEF, 0, 0, 0]));
531        assert_eq!(add << 64, Uint256([0, 0xDEADBEEFDEADBEEF, 0xDEADBEEFDEADBEEF, 0]));
532    }
533
534    #[test]
535    pub fn uint256_serialize_test() {
536        let start1 = Uint256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0, 0]);
537        let start2 = Uint256([0x8C8C3EE70C644118u64, 0x0209E7378231E632, 0xABCD, 0xFFFF]);
538        let serial1 = serialize(&start1);
539        let serial2 = serialize(&start2);
540        let end1: Result<Uint256, _> = deserialize(&serial1);
541        let end2: Result<Uint256, _> = deserialize(&serial2);
542
543        assert_eq!(end1.ok(), Some(start1));
544        assert_eq!(end2.ok(), Some(start2));
545    }
546}
547
bitcoin/util/uint.rs

bitcoin/util/
uint.rs
