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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

use num_traits::Float;
use std::hash::{Hash, Hasher};

use {Primitive, Real};

const SIGN_MASK: u64 = 0x8000000000000000u64;
const EXPONENT_MASK: u64 = 0x7ff0000000000000u64;
const MANTISSA_MASK: u64 = 0x000fffffffffffffu64;

const CANONICAL_NAN: u64 = 0x7ff8000000000000u64;
const CANONICAL_ZERO: u64 = 0x0u64;

pub trait FloatArray {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher;
}

// TODO: Is there a better way to implement this macro? See `hash_float_array`.
macro_rules! float_array {
    (lengths => $($N:expr),*) => {$(
        impl<T> FloatArray for [T; $N]
        where
            T: Float + Primitive,
        {
            fn hash<H>(&self, state: &mut H)
            where
                H: Hasher
            {
                hash_float_slice(self, state)
            }
        }
    )*};
}
float_array!(lengths => 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16);

/// Hashes a raw floating point value.
///
/// To perform the hash, the floating point value is normalized. If `NaN` or
/// zero, a canonical form is used, so all `NaN`s result in the same hash and
/// all zeroes (positive and negative) result in the same hash.
#[inline(always)]
pub fn hash_float<T, H>(value: T, state: &mut H)
where
    T: Float + Primitive,
    H: Hasher,
{
    canonicalize_float(value).hash(state);
}

/// Hashes a slice of raw floating point values.
///
/// See `hash_float` for details.
pub fn hash_float_slice<T, H>(values: &[T], state: &mut H)
where
    T: Float + Primitive,
    H: Hasher,
{
    for value in values {
        hash_float(*value, state);
    }
}

// TODO: Use integer generics to implement hashing over arrays.
/// Hashes an array of raw floating point values.
///
/// Supports arrays up to length 16. See `hash_float` for details.
pub fn hash_float_array<T, H>(array: &T, state: &mut H)
where
    T: FloatArray,
    H: Hasher,
{
    array.hash(state);
}

fn canonicalize_float<T>(value: T) -> u64
where
    T: Float + Primitive,
{
    if value.is_nan() {
        CANONICAL_NAN
    }
    else {
        canonicalize_not_nan(value)
    }
}

fn canonicalize_not_nan<T>(value: T) -> u64
where
    T: Primitive + Real,
{
    use std::mem;

    let (mantissa, exponent, sign) = value.integer_decode();
    if mantissa == 0 {
        CANONICAL_ZERO
    }
    else {
        let exponent = unsafe { mem::transmute::<i16, u16>(exponent) } as u64;
        let sign = if sign > 0 { 1u64 } else { 0u64 };

        (mantissa & MANTISSA_MASK) | ((exponent << 52) & EXPONENT_MASK) | ((sign << 63) & SIGN_MASK)
    }
}