polars_ops/series/ops/
mm3_hash.rs

1use polars_core::chunked_array::ops::arity::unary_elementwise_values;
2use polars_core::prelude::*;
3
4/// 32-bit MurmurHash3 (x86 variant).
5pub fn murmur3_x86_32(bytes: &[u8], seed: u32) -> u32 {
6    const C1: u32 = 0xcc9e_2d51;
7    const C2: u32 = 0x1b87_3593;
8
9    let mut h = seed;
10    let mut chunks = bytes.chunks_exact(4);
11
12    for chunk in chunks.by_ref() {
13        let mut k = u32::from_le_bytes(chunk.try_into().unwrap());
14        k = k.wrapping_mul(C1).rotate_left(15).wrapping_mul(C2);
15        h ^= k;
16        h = h.rotate_left(13).wrapping_mul(5).wrapping_add(0xe654_6b64);
17    }
18
19    let tail = chunks.remainder();
20    if !tail.is_empty() {
21        let mut k = 0u32;
22        for (i, b) in tail.iter().enumerate() {
23            k |= (*b as u32) << (8 * i);
24        }
25        k = k.wrapping_mul(C1).rotate_left(15).wrapping_mul(C2);
26        h ^= k;
27    }
28
29    h ^= bytes.len() as u32;
30    h ^= h >> 16;
31    h = h.wrapping_mul(0x85eb_ca6b);
32    h ^= h >> 13;
33    h = h.wrapping_mul(0xc2b2_ae35);
34    h ^= h >> 16;
35    h
36}
37
38#[inline]
39fn hash_bytes(bytes: &[u8]) -> i32 {
40    murmur3_x86_32(bytes, 0) as i32
41}
42
43#[inline]
44fn hash_long(v: i64) -> i32 {
45    hash_bytes(&v.to_le_bytes())
46}
47
48/// Hash the minimum-length big-endian two's-complement representation of the unscaled value.
49#[cfg(feature = "dtype-decimal")]
50#[inline]
51fn hash_decimal(v: i128) -> i32 {
52    let magnitude = if v < 0 { !v } else { v };
53    let num_bits = 128 - magnitude.leading_zeros() as usize;
54    let num_bytes = num_bits / 8 + 1;
55    hash_bytes(&v.to_be_bytes()[16 - num_bytes..])
56}
57
58fn hash_i64_values(ca: &Int64Chunked, f: impl Fn(i64) -> i64) -> Int32Chunked {
59    unary_elementwise_values(ca, |v| hash_long(f(v)))
60}
61
62/// Hash values using the 32-bit MurmurHash3 as defined by the Iceberg specification (Appendix B).
63///
64/// Integers, dates, times and timestamps are hashed as 8-byte little-endian longs (times and
65/// timestamps in microseconds), decimals as the minimal big-endian two's-complement bytes of the
66/// unscaled value, and strings and binary as their bytes.
67pub fn mm3_hash(s: &Series) -> PolarsResult<Series> {
68    use DataType as D;
69
70    let name = s.name().clone();
71
72    let out: Int32Chunked = match s.dtype() {
73        D::Null => Int32Chunked::full_null(name.clone(), s.len()),
74        dt if dt.is_integer() => {
75            let s = s.strict_cast(&D::Int64)?;
76            hash_i64_values(s.i64()?, |v| v)
77        },
78        #[cfg(feature = "dtype-date")]
79        D::Date => {
80            let s = s.to_physical_repr().cast(&D::Int64)?;
81            hash_i64_values(s.i64()?, |v| v)
82        },
83        #[cfg(feature = "dtype-time")]
84        D::Time => {
85            let ca = s.time()?.physical();
86            hash_i64_values(ca, |ns| ns.div_euclid(1_000))
87        },
88        #[cfg(feature = "dtype-datetime")]
89        D::Datetime(tu, _) => {
90            let ca = s.datetime()?.physical();
91            match tu {
92                TimeUnit::Nanoseconds => hash_i64_values(ca, |ns| ns.div_euclid(1_000)),
93                TimeUnit::Microseconds => hash_i64_values(ca, |us| us),
94                TimeUnit::Milliseconds => {
95                    let ca = ca.try_apply_nonnull_values_generic::<Int64Type, _, _, _>(|ms| {
96                        ms.checked_mul(1_000).ok_or_else(|| {
97                            polars_err!(ComputeError: "datetime out of range for microsecond precision: {ms}ms")
98                        })
99                    })?;
100                    hash_i64_values(&ca, |us| us)
101                },
102            }
103        },
104        #[cfg(feature = "dtype-decimal")]
105        D::Decimal(_, _) => unary_elementwise_values(s.decimal()?.physical(), hash_decimal),
106        D::String => unary_elementwise_values(s.str()?, |v: &str| hash_bytes(v.as_bytes())),
107        D::Binary => unary_elementwise_values(s.binary()?, hash_bytes),
108        dt => polars_bail!(InvalidOperation: "mm3_hash not supported for dtype {dt}"),
109    };
110
111    Ok(out.with_name(name).into_series())
112}
113
114#[cfg(test)]
115mod tests {
116    use super::*;
117
118    #[test]
119    fn test_murmur3_x86_32() {
120        // Reference values from the Iceberg specification (Appendix B).
121        assert_eq!(hash_long(34), 2017239379);
122        assert_eq!(hash_bytes("iceberg".as_bytes()), 1210000089);
123        assert_eq!(hash_bytes(&[0, 1, 2, 3]), -188683207);
124        #[cfg(feature = "dtype-decimal")]
125        assert_eq!(hash_decimal(1420), -500754589);
126    }
127}
polars_ops/series/ops/mm3_hash.rs

polars_ops/series/ops/
mm3_hash.rs
