rupg_func/
hash.rs

1//! The hash support functions of the types, from `hashfunc.c` and the files of the types, with `hash_bytes` and `hash_bytes_uint32` of `hashfn.c`. Each hash is the hash of PostgreSQL on a little-endian machine. A function with the suffix `extended` takes a seed and gives a hash of 64 bits. With the seed 0, the low 32 bits of the extended hash are the plain hash.
2
3use rupg_common::{Error, Result, SqlState};
4use rupg_pgcatalog::builtin;
5use rupg_types::{
6    Array, JsonItem, JsonToken as Token, JsonTree, NetFamily, Numeric, NumericSign, RANGE_EMPTY,
7    RANGE_LB_INF, RANGE_UB_INF, Range, TypeInfo, Value, format_type, numeric_in, oid,
8};
9
10use crate::{Kernel, bad_value, not_yet, type_error};
11
12/// The hash functions of the types with one fixed type of argument: the `prosrc` of the plain function, the `prosrc` of the extended function and the type.
13macro_rules! fixed {
14    ($src:expr; $($plain:literal, $seeded:literal => $ty:expr;)*) => {
15        match $src {
16            $(
17                $plain => |_, args| plain($ty, args),
18                $seeded => |_, args| seeded($ty, args),
19            )*
20            _ => return None,
21        }
22    };
23}
24
25/// The kernel of a hash function by its `prosrc`.
26pub(crate) fn by_src(src: &str) -> Option<Kernel> {
27    // The type of the argument of these functions comes from the call.
28    match src {
29        "hash_array" | "hash_range" | "hash_multirange" | "hash_record" => {
30            return Some(|call, args| plain(call.args.first().copied().unwrap_or(0), args));
31        }
32        "hash_array_extended"
33        | "hash_range_extended"
34        | "hash_multirange_extended"
35        | "hash_record_extended" => {
36            return Some(|call, args| seeded(call.args.first().copied().unwrap_or(0), args));
37        }
38        _ => {}
39    }
40    Some(fixed! { src;
41        "hashbool", "hashboolextended" => oid::BOOL;
42        "hashchar", "hashcharextended" => oid::CHAR;
43        "hashint2", "hashint2extended" => oid::INT2;
44        "hashint4", "hashint4extended" => oid::INT4;
45        "hashint8", "hashint8extended" => oid::INT8;
46        "hashoid", "hashoidextended" => oid::OID;
47        // `hashenum` hashes the OID of the label, as `hashoid` does.
48        "hashenum", "hashenumextended" => oid::OID;
49        "hashoid8", "hashoid8extended" => oid::OID8;
50        "hashxid", "hashxidextended" => oid::XID;
51        "hashxid8", "hashxid8extended" => oid::XID8;
52        "hashcid", "hashcidextended" => oid::CID;
53        "hashtid", "hashtidextended" => oid::TID;
54        "hashfloat4", "hashfloat4extended" => oid::FLOAT4;
55        "hashfloat8", "hashfloat8extended" => oid::FLOAT8;
56        "hash_numeric", "hash_numeric_extended" => oid::NUMERIC;
57        "hashoidvector", "hashoidvectorextended" => oid::OIDVECTOR;
58        "hashname", "hashnameextended" => oid::NAME;
59        "hashtext", "hashtextextended" => oid::TEXT;
60        "hashbpchar", "hashbpcharextended" => oid::BPCHAR;
61        "hashbytea", "hashbyteaextended" => oid::BYTEA;
62        "hashdate", "hashdateextended" => oid::DATE;
63        "time_hash", "time_hash_extended" => oid::TIME;
64        "timetz_hash", "timetz_hash_extended" => oid::TIMETZ;
65        "timestamp_hash", "timestamp_hash_extended" => oid::TIMESTAMP;
66        "timestamptz_hash", "timestamptz_hash_extended" => oid::TIMESTAMPTZ;
67        "interval_hash", "interval_hash_extended" => oid::INTERVAL;
68        "uuid_hash", "uuid_hash_extended" => oid::UUID;
69        "hashmacaddr", "hashmacaddrextended" => oid::MACADDR;
70        "hashmacaddr8", "hashmacaddr8extended" => oid::MACADDR8;
71        "hashinet", "hashinetextended" => oid::INET;
72        "pg_lsn_hash", "pg_lsn_hash_extended" => oid::PG_LSN;
73        "jsonb_hash", "jsonb_hash_extended" => oid::JSONB;
74    })
75}
76
77/// A plain hash function: the hash of 32 bits as `integer`.
78fn plain(ty: u32, args: &[Value]) -> Result<Value> {
79    let value = args.first().ok_or_else(bad_value)?;
80    let hash = hash(ty, value, Seed::Plain)?;
81    #[allow(clippy::cast_possible_truncation)]
82    Ok(Value::Int4((hash as u32).cast_signed()))
83}
84
85/// An extended hash function: the hash of 64 bits with the seed of the second argument as `bigint`.
86fn seeded(ty: u32, args: &[Value]) -> Result<Value> {
87    let (Some(value), Some(Value::Int8(seed))) = (args.first(), args.get(1)) else {
88        return Err(bad_value());
89    };
90    Ok(Value::Int8(hash(ty, value, Seed::Extended(seed.cast_unsigned()))?.cast_signed()))
91}
92
93/// The kind of a hash: the plain hash of 32 bits, or the extended hash of 64 bits with a seed.
94#[derive(Clone, Copy)]
95enum Seed {
96    Plain,
97    Extended(u64),
98}
99
100impl Seed {
101    /// `hash_any` or `hash_any_extended` of some bytes.
102    fn bytes(self, data: &[u8]) -> u64 {
103        match self {
104            Seed::Plain => u64::from(hash_bytes(data, 0).1),
105            Seed::Extended(seed) => {
106                let (b, c) = hash_bytes(data, seed);
107                u64::from(b) << 32 | u64::from(c)
108            }
109        }
110    }
111
112    /// `hash_uint32` or `hash_uint32_extended` of a word.
113    fn word(self, word: u32) -> u64 {
114        match self {
115            Seed::Plain => u64::from(hash_word(word, 0).1),
116            Seed::Extended(seed) => {
117                let (b, c) = hash_word(word, seed);
118                u64::from(b) << 32 | u64::from(c)
119            }
120        }
121    }
122
123    /// `hashint8` or `hashint8extended`: the hash of the low half with the high half, or its complement for a negative value. So an equal `integer` has the same hash.
124    fn int8(self, value: i64) -> u64 {
125        #[allow(clippy::cast_possible_truncation)]
126        let (low, high) = (value as u32, (value >> 32) as u32);
127        self.word(low ^ if value >= 0 { high } else { !high })
128    }
129
130    /// The hash of a value that has no hash of its own, such as a zero or a `NaN`: 0 for a plain hash and the seed for an extended hash.
131    fn zero(self) -> u64 {
132        match self {
133            Seed::Plain => 0,
134            Seed::Extended(seed) => seed,
135        }
136    }
137
138    /// The step of `hash_array`, `hash_multirange` and `hash_record` that adds the hash of one more element.
139    fn combine(self, result: u64, element: u64) -> u64 {
140        let next = (result << 5).wrapping_sub(result).wrapping_add(element);
141        match self {
142            Seed::Plain => next & u64::from(u32::MAX),
143            Seed::Extended(_) => next,
144        }
145    }
146}
147
148/// `compute_partition_hash_value`: the hash of the key of a row of a table that `PARTITION BY HASH` partitions. Each value that is not null gets the extended hash of its type with the seed `HASH_PARTITION_SEED`, and `hash_combine64` adds it to the hash. A row goes in the partition whose remainder is this hash modulo its modulus.
149///
150/// # Errors
151///
152/// `42883` for a type with no hash function.
153pub fn partition_hash(values: &[(u32, Value)]) -> Result<u64> {
154    let mut row = 0u64;
155    for (ty, value) in values {
156        if value.is_null() {
157            continue;
158        }
159        row = hash_combine64(row, extended_hash(*ty, value, HASH_PARTITION_SEED)?);
160    }
161    Ok(row)
162}
163
164/// `HASH_PARTITION_SEED`: the seed of the hashes of the keys of `PARTITION BY HASH`.
165pub const HASH_PARTITION_SEED: u64 = 0x7A5B_2236_7996_DCFD;
166
167/// `hash_combine64`: the hash `row` with the hash `one` added to it.
168pub fn hash_combine64(row: u64, one: u64) -> u64 {
169    row ^ one.wrapping_add(0x49a0_f4dd_15e5_a8e3).wrapping_add(row << 54).wrapping_add(row >> 7)
170}
171
172/// The extended hash of a value of the type `ty` with the seed, as the support function 2 of the default hash operator class of the type gives it.
173///
174/// # Errors
175///
176/// `42883` for a type with no hash function.
177pub fn extended_hash(ty: u32, value: &Value, seed: u64) -> Result<u64> {
178    hash(crate::io::base_type(ty), value, Seed::Extended(seed))
179}
180
181/// The hash of a value of the type `ty`. A plain hash has only the low 32 bits.
182fn hash(ty: u32, value: &Value, seed: Seed) -> Result<u64> {
183    Ok(match (ty, value) {
184        (oid::BOOL, Value::Bool(v)) => seed.word(u32::from(*v)),
185        // `char` is signed on the machines of the hashes.
186        (oid::CHAR, Value::Char(v)) => seed.word(i32::from(v.cast_signed()).cast_unsigned()),
187        (oid::INT2, Value::Int2(v)) => seed.word(i32::from(*v).cast_unsigned()),
188        (oid::INT4 | oid::DATE, Value::Int4(v) | Value::Date(v)) => seed.word(v.cast_unsigned()),
189        (oid::INT8 | oid::OID8 | oid::XID8 | oid::PG_LSN, Value::Int8(v))
190        | (oid::TIME, Value::Time(v))
191        | (oid::TIMESTAMP, Value::Timestamp(v))
192        | (oid::TIMESTAMPTZ, Value::TimestampTz(v)) => seed.int8(*v),
193        (_, Value::Oid(v)) if is_oid(ty) => seed.word(*v),
194        (oid::TID, Value::Int8(v)) => {
195            let (block, offset) = crate::io::tid_parts(*v)?;
196            let mut data = [0; 6];
197            #[allow(clippy::cast_possible_truncation)]
198            {
199                data[..2].copy_from_slice(&((block >> 16) as u16).to_le_bytes());
200                data[2..4].copy_from_slice(&(block as u16).to_le_bytes());
201            }
202            data[4..].copy_from_slice(&offset.to_le_bytes());
203            seed.bytes(&data)
204        }
205        (oid::FLOAT4, Value::Float4(v)) => float(f64::from(*v), seed),
206        (oid::FLOAT8, Value::Float8(v)) => float(*v, seed),
207        (oid::NUMERIC, Value::Numeric(v)) => numeric(v, seed),
208        (oid::OIDVECTOR, Value::Array(array)) => {
209            let mut data = Vec::with_capacity(array.values.len() * 4);
210            for value in &array.values {
211                let Some(Value::Oid(v)) = value else { return Err(bad_value()) };
212                data.extend_from_slice(&v.to_le_bytes());
213            }
214            seed.bytes(&data)
215        }
216        (oid::TEXT | oid::VARCHAR | oid::NAME, Value::Text(v)) => seed.bytes(v.as_bytes()),
217        (oid::BPCHAR, Value::Text(v)) => seed.bytes(v.trim_end_matches(' ').as_bytes()),
218        (oid::BYTEA, Value::Bytea(v)) => seed.bytes(v),
219        (oid::TIMETZ, Value::TimeTz(time, zone)) => {
220            seed.int8(*time) ^ seed.word(zone.cast_unsigned())
221        }
222        (oid::INTERVAL, Value::Interval(v)) => {
223            // The low 64 bits of the length, as `interval_hash` keeps them.
224            #[allow(clippy::cast_possible_truncation)]
225            seed.int8(crate::compare::span(v) as i64)
226        }
227        (oid::UUID, Value::Uuid(v)) => seed.bytes(v),
228        (oid::MACADDR, Value::Int8(v)) => seed.bytes(&v.to_be_bytes()[2..]),
229        (oid::MACADDR8, Value::Int8(v)) => seed.bytes(&v.to_be_bytes()),
230        (oid::INET | oid::CIDR, Value::Inet(v)) => {
231            // The family is `PGSQL_AF_INET` or `PGSQL_AF_INET6` of Linux.
232            let (family, size) = match v.family {
233                NetFamily::V4 => (2, 4),
234                NetFamily::V6 => (3, 16),
235            };
236            let mut data = vec![family, v.bits];
237            data.extend_from_slice(&v.addr[..size]);
238            seed.bytes(&data)
239        }
240        (_, Value::Array(array)) => self::array(ty, array, seed)?,
241        (_, Value::Range(range)) => {
242            let subtype = builtin::range_subtype(ty).ok_or_else(|| no_hash(ty))?;
243            self::range(subtype, range, seed)?
244        }
245        (_, Value::Multirange(ranges)) => {
246            let subtype = builtin::multirange_range(ty)
247                .and_then(builtin::range_subtype)
248                .ok_or_else(|| no_hash(ty))?;
249            let mut result = 1;
250            for range in ranges {
251                result = seed.combine(result, self::range(subtype, range, seed)?);
252            }
253            result
254        }
255        (_, Value::Record(record)) => {
256            let mut result = 0;
257            for (&ty, value) in record.types.iter().zip(&record.values) {
258                let element = if value.is_null() {
259                    0
260                } else {
261                    // `hash_record_extended` names the extended hash function in the error.
262                    hash(ty, value, seed).map_err(|err| {
263                        if err.message() == no_hash(ty).message() {
264                            no_hash_for(ty, seed)
265                        } else {
266                            err
267                        }
268                    })?
269                };
270                result = seed.combine(result, element);
271            }
272            result
273        }
274        (oid::JSONB, _) => jsonb(value.as_str().ok_or_else(bad_value)?, seed)?,
275        (oid::ACLITEM, _) => return Err(not_yet("the hash of aclitem")),
276        _ if has_hash(ty) => return Err(bad_value()),
277        _ => return Err(no_hash(ty)),
278    })
279}
280
281/// True for `oid`, the types of `xid` and `cid`, and the types of the OIDs of objects, which `hashoid` hashes as the OID.
282fn is_oid(ty: u32) -> bool {
283    matches!(
284        ty,
285        oid::OID
286            | oid::XID
287            | oid::CID
288            | oid::REGPROC
289            | oid::REGPROCEDURE
290            | oid::REGOPER
291            | oid::REGOPERATOR
292            | oid::REGCLASS
293            | oid::REGTYPE
294            | oid::REGCONFIG
295            | oid::REGDICTIONARY
296            | oid::REGNAMESPACE
297            | oid::REGROLE
298            | oid::REGCOLLATION
299            | oid::REGDATABASE
300    )
301}
302
303/// True for a type that has a hash function in the catalog.
304fn has_hash(ty: u32) -> bool {
305    matches!(
306        ty,
307        oid::JSONB
308            | oid::ACLITEM
309            | oid::BOOL
310            | oid::CHAR
311            | oid::INT2
312            | oid::INT4
313            | oid::INT8
314            | oid::OID8
315            | oid::XID8
316            | oid::PG_LSN
317            | oid::DATE
318            | oid::TIME
319            | oid::TIMESTAMP
320            | oid::TIMESTAMPTZ
321            | oid::TID
322            | oid::FLOAT4
323            | oid::FLOAT8
324            | oid::NUMERIC
325            | oid::OIDVECTOR
326            | oid::TEXT
327            | oid::VARCHAR
328            | oid::NAME
329            | oid::BPCHAR
330            | oid::BYTEA
331            | oid::TIMETZ
332            | oid::INTERVAL
333            | oid::UUID
334            | oid::MACADDR
335            | oid::MACADDR8
336            | oid::INET
337            | oid::CIDR
338    ) || is_oid(ty)
339}
340
341/// The error of a type with no hash function.
342fn no_hash(ty: u32) -> Error {
343    Error::new(
344        SqlState::UNDEFINED_FUNCTION,
345        format!("could not identify a hash function for type {}", format_type(ty)),
346    )
347}
348
349/// The error of a type with no hash function for the kind of the hash, as `hash_array_extended` and `hash_record_extended` give it.
350fn no_hash_for(ty: u32, seed: Seed) -> Error {
351    match seed {
352        Seed::Plain => no_hash(ty),
353        Seed::Extended(_) => Error::new(
354            SqlState::UNDEFINED_FUNCTION,
355            format!("could not identify an extended hash function for type {}", format_type(ty)),
356        ),
357    }
358}
359
360/// `hash_uint32_extended`, which `hash_aclitem_extended` uses for a seed that is not 0.
361pub(crate) fn uint32_extended(word: u32, seed: u64) -> u64 {
362    Seed::Extended(seed).word(word)
363}
364
365/// `JB_FARRAY` and `JB_FOBJECT`, the flags of the header of an array and of an object of `jsonb`.
366const JB_FARRAY: u32 = 0x4000_0000;
367const JB_FOBJECT: u32 = 0x2000_0000;
368
369/// `jsonb_hash` and `jsonb_hash_extended` with `JsonbHashScalarValue` and `JsonbHashScalarValueExtended`: the tokens in the order of `JsonbIteratorNext`. The start of an array or of an object adds its flag, and each key, value and element rotates the hash and adds its own hash. An empty array or object at the root has the hash of [`Seed::zero`].
370fn jsonb(text: &str, seed: Seed) -> Result<u64> {
371    let tree = JsonTree::parse(text).map_err(type_error)?;
372    if matches!(tree.item(0), JsonItem::Array(v) if v.is_empty())
373        || matches!(tree.item(0), JsonItem::Object(v) if v.is_empty())
374    {
375        return Ok(seed.zero());
376    }
377    let mut result = 0;
378    for token in tree.tokens() {
379        let element = match token {
380            Token::Begin { node, raw, .. } => {
381                let flag = if raw || matches!(tree.item(node), JsonItem::Array(_)) {
382                    JB_FARRAY
383                } else {
384                    JB_FOBJECT
385                };
386                result ^= match seed {
387                    Seed::Plain => u64::from(flag),
388                    Seed::Extended(_) => u64::from(flag) << 32 | u64::from(flag),
389                };
390                continue;
391            }
392            Token::End { .. } => continue,
393            Token::Key(key, _) => seed.bytes(key.as_bytes()),
394            Token::Scalar { node, .. } => match tree.item(node) {
395                JsonItem::Null => seed.zero().wrapping_add(1),
396                JsonItem::Bool(v) => match seed {
397                    // `hashcharextended` of the boolean.
398                    Seed::Extended(value) if value != 0 => seed.word(u32::from(*v)),
399                    _ => {
400                        if *v {
401                            2
402                        } else {
403                            4
404                        }
405                    }
406                },
407                JsonItem::String(v) => seed.bytes(v.as_bytes()),
408                JsonItem::Number => {
409                    numeric(&numeric_in(tree.text(node), -1).map_err(type_error)?, seed)
410                }
411                JsonItem::Array(_) | JsonItem::Object(_) => return Err(bad_value()),
412            },
413        };
414        result = match seed {
415            Seed::Plain =>
416            {
417                #[allow(clippy::cast_possible_truncation)]
418                u64::from((result as u32).rotate_left(1))
419            }
420            Seed::Extended(_) => {
421                (result << 1) & 0xffff_fffe_ffff_fffe | (result >> 31) & 0x0000_0001_0000_0001
422            }
423        } ^ element;
424    }
425    Ok(result)
426}
427
428/// `hashfloat8` and `hashfloat4`, which widens the value to `double precision` first: a zero of each sign has the hash of [`Seed::zero`], and each `NaN` has the hash of the standard `NaN`.
429fn float(value: f64, seed: Seed) -> u64 {
430    if value == 0.0 {
431        return seed.zero();
432    }
433    let value = if value.is_nan() { f64::NAN } else { value };
434    seed.bytes(&value.to_le_bytes())
435}
436
437/// `hashfloat8` of the seed of `TABLESAMPLE ... REPEATABLE`.
438pub(crate) fn float8_hash(value: f64) -> u32 {
439    #[allow(clippy::cast_possible_truncation)]
440    let hash = float(value, Seed::Plain) as u32;
441    hash
442}
443
444/// The hash of the number of a row and the seed of a sample, which `TABLESAMPLE` compares with its cutoff. `tsm_bernoulli.c` hashes the block, the offset and the seed of a row. A row of rupg has no block, so its number takes the place of the block and the offset.
445pub(crate) fn sample_hash(row: u64, seed: u32) -> u32 {
446    let mut data = [0; 12];
447    data[..8].copy_from_slice(&row.to_le_bytes());
448    data[8..].copy_from_slice(&seed.to_le_bytes());
449    hash_bytes(&data, 0).1
450}
451
452/// `hash_numeric`: the hash of the digits of base 10000 with no zeros at the two ends, then the weight of the first digit that is not zero. A special value has the hash of [`Seed::zero`], and zero has the hash of [`Seed::zero`] less 1.
453fn numeric(value: &Numeric, seed: Seed) -> u64 {
454    if matches!(
455        value.sign(),
456        NumericSign::NaN | NumericSign::Infinity | NumericSign::NegativeInfinity
457    ) {
458        return seed.zero();
459    }
460    let digits = value.digits();
461    let Some(first) = digits.iter().position(|&d| d != 0) else {
462        return match seed {
463            Seed::Plain => u64::from(u32::MAX),
464            Seed::Extended(seed) => seed.wrapping_sub(1),
465        };
466    };
467    let last = digits.iter().rposition(|&d| d != 0).unwrap_or(first);
468    let data: Vec<u8> = digits[first..=last].iter().flat_map(|d| d.to_le_bytes()).collect();
469    #[allow(clippy::cast_possible_truncation, clippy::cast_possible_wrap)]
470    let weight = i64::from(value.weight()) - first as i64;
471    let weight = weight.cast_unsigned();
472    match seed {
473        Seed::Plain => (seed.bytes(&data) ^ weight) & u64::from(u32::MAX),
474        Seed::Extended(_) => seed.bytes(&data) ^ weight,
475    }
476}
477
478/// `hash_array`: the hashes of the elements in order, with 0 for a null element.
479fn array(ty: u32, array: &Array<Value>, seed: Seed) -> Result<u64> {
480    let element = TypeInfo::get(ty).filter(|info| info.is_array()).ok_or_else(|| no_hash(ty))?.elem;
481    if element != oid::RECORD && !has_hash(element) && !is_container(element) {
482        return Err(no_hash_for(element, seed));
483    }
484    let mut result = 1;
485    for value in &array.values {
486        let hash = match value {
487            None => 0,
488            Some(value) => hash(element, value, seed)?,
489        };
490        result = seed.combine(result, hash);
491    }
492    Ok(result)
493}
494
495/// True for an array, a range or a multirange type, whose hash is the hash of its parts.
496fn is_container(ty: u32) -> bool {
497    builtin::range_subtype(ty).is_some()
498        || builtin::multirange_range(ty).is_some()
499        || TypeInfo::get(ty).is_some_and(TypeInfo::is_array)
500}
501
502/// `hash_range`: the hash of the flags, then the hash of the lower bound, a rotation of one bit, and the hash of the upper bound. A missing bound has the hash 0. For an extended hash, the rotation is of each half of 32 bits.
503fn range(subtype: u32, range: &Range, seed: Seed) -> Result<u64> {
504    let bound = |value: &Value, missing: u8| -> Result<u64> {
505        if range.flags & (RANGE_EMPTY | missing) != 0 { Ok(0) } else { hash(subtype, value, seed) }
506    };
507    let lower = bound(&range.lower, RANGE_LB_INF)?;
508    let upper = bound(&range.upper, RANGE_UB_INF)?;
509    let result = seed.word(u32::from(range.flags)) ^ lower;
510    let result = match seed {
511        Seed::Plain =>
512        {
513            #[allow(clippy::cast_possible_truncation)]
514            u64::from((result as u32).rotate_left(1))
515        }
516        Seed::Extended(_) => {
517            (result << 1) & 0xffff_fffe_ffff_fffe | (result >> 31) & 0x0000_0001_0000_0001
518        }
519    };
520    Ok(result ^ upper)
521}
522
523/// The `mix` step of `hashfn.c`.
524fn mix(a: &mut u32, b: &mut u32, c: &mut u32) {
525    *a = a.wrapping_sub(*c) ^ c.rotate_left(4);
526    *c = c.wrapping_add(*b);
527    *b = b.wrapping_sub(*a) ^ a.rotate_left(6);
528    *a = a.wrapping_add(*c);
529    *c = c.wrapping_sub(*b) ^ b.rotate_left(8);
530    *b = b.wrapping_add(*a);
531    *a = a.wrapping_sub(*c) ^ c.rotate_left(16);
532    *c = c.wrapping_add(*b);
533    *b = b.wrapping_sub(*a) ^ a.rotate_left(19);
534    *a = a.wrapping_add(*c);
535    *c = c.wrapping_sub(*b) ^ b.rotate_left(4);
536    *b = b.wrapping_add(*a);
537}
538
539/// The `final` step of `hashfn.c`.
540fn finish(a: &mut u32, b: &mut u32, c: &mut u32) {
541    *c = (*c ^ *b).wrapping_sub(b.rotate_left(14));
542    *a = (*a ^ *c).wrapping_sub(c.rotate_left(11));
543    *b = (*b ^ *a).wrapping_sub(a.rotate_left(25));
544    *c = (*c ^ *b).wrapping_sub(b.rotate_left(16));
545    *a = (*a ^ *c).wrapping_sub(c.rotate_left(4));
546    *b = (*b ^ *a).wrapping_sub(a.rotate_left(14));
547    *c = (*c ^ *b).wrapping_sub(b.rotate_left(24));
548}
549
550/// The start of the state for some bytes of the length `len`, with a seed that is not zero mixed in.
551fn start(len: u32, seed: u64) -> (u32, u32, u32) {
552    let init = 0x9e37_79b9_u32.wrapping_add(len).wrapping_add(3_923_095);
553    let (mut a, mut b, mut c) = (init, init, init);
554    if seed != 0 {
555        #[allow(clippy::cast_possible_truncation)]
556        {
557            a = a.wrapping_add((seed >> 32) as u32);
558            b = b.wrapping_add(seed as u32);
559        }
560        mix(&mut a, &mut b, &mut c);
561    }
562    (a, b, c)
563}
564
565/// `hash_bytes_extended` of little-endian words: the words `b` and `c` of the state at the end. `hash_bytes` is `c`, with the seed 0.
566fn hash_bytes(data: &[u8], seed: u64) -> (u32, u32) {
567    #[allow(clippy::cast_possible_truncation)]
568    let (mut a, mut b, mut c) = start(data.len() as u32, seed);
569    let word = |bytes: &[u8]| u32::from_le_bytes([bytes[0], bytes[1], bytes[2], bytes[3]]);
570    let (chunks, tail) = data.as_chunks::<12>();
571    for chunk in chunks {
572        a = a.wrapping_add(word(&chunk[..4]));
573        b = b.wrapping_add(word(&chunk[4..8]));
574        c = c.wrapping_add(word(&chunk[8..]));
575        mix(&mut a, &mut b, &mut c);
576    }
577    // The last bytes. The lowest byte of `c` is for the length.
578    let mut rest = [0; 12];
579    rest[..tail.len()].copy_from_slice(tail);
580    a = a.wrapping_add(word(&rest[..4]));
581    b = b.wrapping_add(word(&rest[4..8]));
582    c = c.wrapping_add(word(&rest[8..]) << 8);
583    finish(&mut a, &mut b, &mut c);
584    (b, c)
585}
586
587/// `hash_bytes_uint32_extended`: the words `b` and `c` of the state at the end. `hash_bytes_uint32` is `c`, with the seed 0.
588fn hash_word(word: u32, seed: u64) -> (u32, u32) {
589    let (mut a, mut b, mut c) = start(4, seed);
590    a = a.wrapping_add(word);
591    finish(&mut a, &mut b, &mut c);
592    (b, c)
593}
rupg_func/hash.rs

rupg_func/
hash.rs
