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
80
81
82
83

//! Utility functions for bignums that don't make too much sense to turn into methods.

// FIXME This module's name is a bit unfortunate, since other modules also import `core::num`.

use crate::cmp::Ordering::{self, Less, Equal, Greater};

pub use crate::num::bignum::Big32x40 as Big;

/// Test whether truncating all bits less significant than `ones_place` introduces
/// a relative error less, equal, or greater than 0.5 ULP.
pub fn compare_with_half_ulp(f: &Big, ones_place: usize) -> Ordering {
    if ones_place == 0 {
        return Less;
    }
    let half_bit = ones_place - 1;
    if f.get_bit(half_bit) == 0 {
        // < 0.5 ULP
        return Less;
    }
    // If all remaining bits are zero, it's = 0.5 ULP, otherwise > 0.5
    // If there are no more bits (half_bit == 0), the below also correctly returns Equal.
    for i in 0..half_bit {
        if f.get_bit(i) == 1 {
            return Greater;
        }
    }
    Equal
}

/// Converts an ASCII string containing only decimal digits to a `u64`.
///
/// Does not perform checks for overflow or invalid characters, so if the caller is not careful,
/// the result is bogus and can panic (though it won't be `unsafe`). Additionally, empty strings
/// are treated as zero. This function exists because
///
/// 1. using `FromStr` on `&[u8]` requires `from_utf8_unchecked`, which is bad, and
/// 2. piecing together the results of `integral.parse()` and `fractional.parse()` is
///    more complicated than this entire function.
pub fn from_str_unchecked<'a, T>(bytes: T) -> u64 where T : IntoIterator<Item=&'a u8> {
    let mut result = 0;
    for &c in bytes {
        result = result * 10 + (c - b'0') as u64;
    }
    result
}

/// Converts a string of ASCII digits into a bignum.
///
/// Like `from_str_unchecked`, this function relies on the parser to weed out non-digits.
pub fn digits_to_big(integral: &[u8], fractional: &[u8]) -> Big {
    let mut f = Big::from_small(0);
    for &c in integral.iter().chain(fractional) {
        let n = (c - b'0') as u32;
        f.mul_small(10);
        f.add_small(n);
    }
    f
}

/// Unwraps a bignum into a 64 bit integer. Panics if the number is too large.
pub fn to_u64(x: &Big) -> u64 {
    assert!(x.bit_length() < 64);
    let d = x.digits();
    if d.len() < 2 {
        d[0] as u64
    } else {
        (d[1] as u64) << 32 | d[0] as u64
    }
}


/// Extracts a range of bits.

/// Index 0 is the least significant bit and the range is half-open as usual.
/// Panics if asked to extract more bits than fit into the return type.
pub fn get_bits(x: &Big, start: usize, end: usize) -> u64 {
    assert!(end - start <= 64);
    let mut result: u64 = 0;
    for i in (start..end).rev() {
        result = result << 1 | x.get_bit(i) as u64;
    }
    result
}