1pub mod murmur3;
56pub mod rapid;
57pub mod siphash;
58
59use crate::lang::protocol::HashType;
60
61pub const DEFAULT_HASH: HashType = HashType::Rapid;
63
64pub trait JavaHash {
70 fn java_hash(&self, hash_type: HashType) -> i64;
71}
72
73impl JavaHash for bool {
74 fn java_hash(&self, _: HashType) -> i64 {
75 hash_bool(*self) as i64
76 }
77}
78
79impl JavaHash for char {
80 fn java_hash(&self, _: HashType) -> i64 {
81 hash_char(*self) as i64
82 }
83}
84
85impl JavaHash for i64 {
86 fn java_hash(&self, _: HashType) -> i64 {
87 hash_long(*self) as i64
88 }
89}
90
91impl JavaHash for i32 {
92 fn java_hash(&self, _: HashType) -> i64 {
93 hash_long(*self as i64) as i64
94 }
95}
96
97impl JavaHash for usize {
98 fn java_hash(&self, _: HashType) -> i64 {
99 hash_long(*self as i64) as i64
100 }
101}
102
103impl JavaHash for u64 {
104 fn java_hash(&self, _: HashType) -> i64 {
105 hash_long(*self as i64) as i64
106 }
107}
108
109impl JavaHash for f64 {
110 fn java_hash(&self, _: HashType) -> i64 {
111 hash_double(*self) as i64
112 }
113}
114
115impl JavaHash for String {
119 fn java_hash(&self, _: HashType) -> i64 {
120 java_string_hash(self) as i64
121 }
122}
123
124impl JavaHash for &str {
125 fn java_hash(&self, _: HashType) -> i64 {
126 java_string_hash(self) as i64
127 }
128}
129
130pub fn java_string_hash(s: &str) -> i32 {
136 let mut h = 0i32;
137 for unit in s.encode_utf16() {
138 h = h.wrapping_mul(31).wrapping_add(unit as i32);
139 }
140 h
141}
142
143pub fn hash_seed(obj_name: &str) -> i32 {
145 java_string_hash(&format!("::{obj_name}"))
146}
147
148pub fn hash_bool(b: bool) -> i32 {
150 if b {
151 1231
152 } else {
153 1237
154 }
155}
156
157pub fn hash_char(c: char) -> i32 {
161 c as i32
162}
163
164pub fn hash_bytes(bytes: &[u8]) -> i32 {
166 let mut h = 1i32;
167 for b in bytes {
168 h = h.wrapping_mul(31).wrapping_add(*b as i8 as i32);
169 }
170 h
171}
172
173pub fn hash_long(n: i64) -> i32 {
176 hash_long_placement(n)
177}
178
179pub fn hash_long_placement(n: i64) -> i32 {
183 let text = n.to_string();
184 let Some((signum, digits, scale)) = parse_decimal(&text) else {
185 return java_string_hash(&text);
186 };
187 bigdecimal_hash(&digits_to_words_be(&digits), signum, scale as i32)
188}
189
190pub fn hash_double(d: f64) -> i32 {
194 assert!(d.is_finite(), "non-finite number");
195 if d == 0.0 {
196 return 0;
197 }
198 canonical_decimal_str_hash(&format!("{d}"))
201}
202
203pub fn canonical_decimal_str_hash(s: &str) -> i32 {
208 match parse_decimal(s) {
209 Some((signum, digits, scale)) => canonical_decimal_hash(signum, digits, scale),
210 None => java_string_hash(s),
211 }
212}
213
214pub fn hash_string_type(hash_type: HashType, hashed: &str) -> i64 {
222 match hash_type {
223 HashType::System => java_string_hash(hashed) as i64,
224 HashType::Rapid => rapid::hash(hashed.as_bytes()) as i64,
225 HashType::Murmur3 => murmur3::hash_chars(hashed) as i64,
226 HashType::Sip => -1,
227 }
228}
229
230pub fn compose_ordered(obj_name: &str, items: impl IntoIterator<Item = i64>) -> i64 {
237 let mut acc = hash_seed(obj_name) as i64;
238 for h in items {
239 acc = acc.wrapping_mul(31).wrapping_add(h);
240 }
241 acc
242}
243
244pub fn compose_unordered(obj_name: &str, items: impl IntoIterator<Item = i64>) -> i64 {
247 let mut acc = hash_seed(obj_name) as i64;
248 for h in items {
249 acc = acc.wrapping_add(h);
250 }
251 acc
252}
253
254pub fn compose_entry(key_hash: i64, value_hash: i64) -> i64 {
258 compose_ordered("SEQUENTIAL", [key_hash, value_hash])
259}
260
261fn biginteger_hash(words_be: &[u32], signum: i32) -> i32 {
268 let mut h = 0i32;
269 for w in words_be {
270 h = h.wrapping_mul(31).wrapping_add(*w as i32);
271 }
272 h.wrapping_mul(signum)
273}
274
275fn bigdecimal_hash(words_be: &[u32], signum: i32, scale: i32) -> i32 {
288 if signum == 0 {
289 return scale;
291 }
292 let mag: u128 = words_be
293 .iter()
294 .fold(0u128, |acc, w| (acc << 32) | (*w as u128));
295 if mag < (1u128 << 63) {
298 let val2 = mag as u64;
299 let temp = ((((val2 >> 32) as u32) as i32).wrapping_mul(31) as i64
300 + (val2 & 0xffff_ffff) as i64) as i32;
301 let signed = if signum < 0 {
302 temp.wrapping_neg()
303 } else {
304 temp
305 };
306 31i32.wrapping_mul(signed).wrapping_add(scale)
307 } else {
308 31i32
309 .wrapping_mul(biginteger_hash(words_be, signum))
310 .wrapping_add(scale)
311 }
312}
313
314fn parse_decimal(s: &str) -> Option<(i32, Vec<u8>, i64)> {
317 let b = s.as_bytes();
318 let mut i = 0usize;
319 let mut neg = false;
320 if i < b.len() && (b[i] == b'-' || b[i] == b'+') {
321 neg = b[i] == b'-';
322 i += 1;
323 }
324 let mut digits: Vec<u8> = Vec::new();
325 let mut seen_dot = false;
326 let mut scale: i64 = 0;
327 let mut any_digit = false;
328 while i < b.len() {
329 match b[i] {
330 c @ b'0'..=b'9' => {
331 digits.push(c - b'0');
332 if seen_dot {
333 scale += 1;
334 }
335 any_digit = true;
336 }
337 b'.' if !seen_dot => seen_dot = true,
338 b'e' | b'E' => {
339 i += 1;
340 let mut eneg = false;
341 if i < b.len() && (b[i] == b'-' || b[i] == b'+') {
342 eneg = b[i] == b'-';
343 i += 1;
344 }
345 let mut exp: i64 = 0;
346 let mut any_exp = false;
347 while i < b.len() && b[i].is_ascii_digit() {
348 exp = exp.saturating_mul(10).saturating_add((b[i] - b'0') as i64);
349 any_exp = true;
350 i += 1;
351 }
352 if !any_exp {
353 return None;
354 }
355 scale -= if eneg { -exp } else { exp };
356 break;
357 }
358 _ => return None,
359 }
360 i += 1;
361 }
362 if !any_digit {
363 return None;
364 }
365 match digits.iter().position(|d| *d != 0) {
366 None => Some((0, vec![0], 0)),
367 Some(first) => Some((if neg { -1 } else { 1 }, digits[first..].to_vec(), scale)),
368 }
369}
370
371fn canonical_decimal_hash(signum: i32, mut digits: Vec<u8>, mut scale: i64) -> i32 {
375 if signum == 0 {
376 return 0;
377 }
378 while digits.last() == Some(&0) {
379 digits.pop();
380 scale -= 1;
381 }
382 let words = digits_to_words_be(&digits);
383 bigdecimal_hash(&words, signum, scale as i32)
384}
385
386fn digits_to_words_be(digits: &[u8]) -> Vec<u32> {
389 let mut le: Vec<u32> = vec![0];
390 for d in digits {
391 let mut carry = *d as u64;
392 for w in le.iter_mut() {
393 let v = (*w as u64) * 10 + carry;
394 *w = v as u32;
395 carry = v >> 32;
396 }
397 while carry > 0 {
398 le.push(carry as u32);
399 carry >>= 32;
400 }
401 }
402 while le.len() > 1 && le.last() == Some(&0) {
403 le.pop();
404 }
405 le.iter().rev().copied().collect()
406}
407
408#[cfg(test)]
413mod tests {
414 use super::*;
415 use crate::core::Value;
416 use crate::kernel::parser::parse_forms;
417 use crate::kernel::Form;
418 use crate::lang::data::{
419 Keyword, Map as PMap, MapEntry as PMapEntry, Set as PSet, Symbol, Tuple as PTuple,
420 };
421 use crate::lang::protocol::{IDisplay, IHash, IObjType};
422
423 fn corpus_path(relative: &str) -> Option<std::path::PathBuf> {
426 crate::spec_registry::resolve(relative).filter(|candidate| candidate.is_file())
427 }
428
429 fn field<'a>(case: &'a Form, key: &str) -> &'a Form {
430 match case {
431 Form::Map(entries) => entries
432 .iter()
433 .find(|(k, _)| matches!(k, Form::Keyword(kw) if kw == key))
434 .map(|(_, v)| v)
435 .unwrap_or_else(|| panic!("case missing :{key}: {case}")),
436 other => panic!("case is not a map: {other}"),
437 }
438 }
439
440 fn kw_of(form: &Form) -> &str {
441 match form {
442 Form::Keyword(s) => s,
443 other => panic!("expected keyword, got {other}"),
444 }
445 }
446
447 fn num_of(form: &Form) -> i64 {
448 match form {
449 Form::Number(n) => *n,
450 other => panic!("expected number, got {other}"),
451 }
452 }
453
454 fn str_of(form: &Form) -> &str {
455 match form {
456 Form::String(s) => s,
457 other => panic!("expected string, got {other}"),
458 }
459 }
460
461 fn hash_type(id: &str) -> HashType {
462 match id {
463 "system" => HashType::System,
464 "rapid" => HashType::Rapid,
465 "murmur3" => HashType::Murmur3,
466 "sip" => HashType::Sip,
467 other => panic!("unknown hash type: {other}"),
468 }
469 }
470
471 fn element_value(form: &Form) -> Value {
474 match form {
475 Form::Nil => Value::Nil,
476 Form::Bool(b) => Value::Bool(*b),
477 Form::Number(n) => Value::Number(*n),
478 Form::Float(f) => Value::Float(*f),
479 Form::String(s) => Value::String(s.clone().into()),
480 Form::Vector(items) => Value::Vector(items.iter().map(element_value).collect()),
481 Form::List(items) => Value::List(items.iter().map(element_value).collect()),
482 Form::Map(pairs) => Value::Map(
483 pairs
484 .iter()
485 .map(|(k, v)| (element_value(k), element_value(v)))
486 .collect::<PMap<Value, Value>>(),
487 ),
488 Form::Set(items) => {
489 Value::Set(items.iter().map(element_value).collect::<PSet<Value>>())
490 }
491 other => panic!("unsupported collection element: {other}"),
492 }
493 }
494
495 fn collection_value(structure: &str, input: &Form) -> Value {
499 match structure {
500 "vector" | "list" | "map" | "set" => element_value(input),
501 "queue" => match input {
502 Form::Vector(items) => {
503 Value::Queue(Box::new(items.iter().map(element_value).collect()))
504 }
505 other => panic!("queue input must be a vector: {other}"),
506 },
507 "compact-vector2" => match input {
508 Form::Vector(items) if items.len() == 2 => Value::Tuple(Box::new(
509 PTuple::from_values(items.iter().map(element_value).collect()).unwrap(),
510 )),
511 other => panic!("compact-vector2 input must be a 2-vector: {other}"),
512 },
513 "map-entry" => match input {
514 Form::Vector(items) if items.len() == 2 => Value::MapEntry(Box::new(
515 PMapEntry::new(element_value(&items[0]), element_value(&items[1])),
516 )),
517 other => panic!("map-entry input must be a 2-vector: {other}"),
518 },
519 other => panic!("unknown collection structure: {other}"),
520 }
521 }
522
523 fn eval_case(case: &Form) -> i64 {
524 let hash = kw_of(field(case, "hash"));
525 let kind = kw_of(field(case, "kind"));
526 let input = field(case, "input");
527 match kind {
528 "string" => {
529 let s = str_of(input);
530 match hash {
531 "rapid" => rapid::hash(s.as_bytes()) as i64,
532 "murmur3" => murmur3::hash_chars(s) as i64,
533 "sip" => siphash::hash(&siphash::HARA, s.as_bytes()) as i64,
534 "system" => java_string_hash(s) as i64,
535 other => panic!("unknown string hash type: {other}"),
536 }
537 }
538 "int" => murmur3::hash_int(num_of(input) as i32) as i64,
539 "long" => match hash {
540 "murmur3" => murmur3::hash_long(num_of(input)) as i64,
541 "system" => hash_long(num_of(input)) as i64,
542 other => panic!("unknown long hash type: {other}"),
543 },
544 "double" => match input {
545 Form::Float(f) => hash_double(*f) as i64,
546 other => panic!("double input must be a float: {other}"),
547 },
548 "bigint" => canonical_decimal_str_hash(str_of(input)) as i64,
549 "bool" => match input {
550 Form::Bool(b) => hash_bool(*b) as i64,
551 other => panic!("bool input must be a boolean: {other}"),
552 },
553 "char" => match input {
554 Form::Character(c) => hash_char(*c) as i64,
555 other => panic!("char input must be a character: {other}"),
556 },
557 "bytes" => match input {
558 Form::Vector(items) => {
559 let bytes: Vec<u8> = items.iter().map(|f| num_of(f) as i8 as u8).collect();
560 hash_bytes(&bytes) as i64
561 }
562 other => panic!("bytes input must be a vector: {other}"),
563 },
564 "nil" => 0,
565 "seed" => hash_seed(str_of(input)) as i64,
566 "keyword" => match input {
567 Form::Keyword(s) => Keyword::parse(s).unwrap().hash_calc(hash_type(hash)) as i64,
568 other => panic!("keyword input must be a keyword: {other}"),
569 },
570 "symbol" => match input {
571 Form::Symbol(s) => Symbol::parse(s).hash_calc(hash_type(hash)) as i64,
572 other => panic!("symbol input must be a symbol: {other}"),
573 },
574 "collection" => {
575 let structure = kw_of(field(case, "structure"));
576 let value = collection_value(structure, input);
577 match hash {
578 "rapid" => value.stable_hash() as i64,
579 "murmur3" => value.java_hash(HashType::Murmur3),
580 other => panic!("unknown collection hash type: {other}"),
581 }
582 }
583 other => panic!("unknown case kind: {other}"),
584 }
585 }
586
587 #[test]
591 fn java_parity_fixture() {
592 let Some(path) =
593 corpus_path("01-lang/020-data-structures/draft/conformance/hash-parity.edn")
594 else {
595 eprintln!(
596 "skipping hash-parity corpus: specs checkout not found from {}",
597 env!("CARGO_MANIFEST_DIR")
598 );
599 return;
600 };
601 let source = std::fs::read_to_string(&path)
602 .unwrap_or_else(|e| panic!("cannot read {}: {e}", path.display()));
603 let forms = parse_forms(&source).expect("hash-parity corpus must parse");
604 assert_eq!(forms.len(), 1, "corpus must be a single map form");
605 let Form::Vector(cases) = field(&forms[0], "cases") else {
606 panic!("corpus :cases must be a vector");
607 };
608 let mut failures: Vec<String> = Vec::new();
609 for case in cases {
610 if kw_of(field(case, "kind")) == "decimal" {
611 continue;
612 }
613 let id = kw_of(field(case, "id")).to_string();
614 let expected = num_of(field(case, "expect"));
615 let actual = eval_case(case);
616 if actual != expected {
617 failures.push(format!(":{id}: expected {expected}, got {actual}"));
618 }
619 }
620 assert!(
621 cases.len() >= 270,
622 "only {} hash-parity cases found",
623 cases.len()
624 );
625 if !failures.is_empty() {
626 panic!(
627 "{} of {} hash-parity cases failed:\n{}",
628 failures.len(),
629 cases.len(),
630 failures.join("\n")
631 );
632 }
633 }
634
635 #[test]
636 fn cross_type_numeric_equality() {
637 assert_eq!(hash_double(1.0), canonical_decimal_str_hash("1"));
640 assert_eq!(hash_double(1.0), canonical_decimal_str_hash("1.0"));
641 assert_eq!(hash_double(2.5), canonical_decimal_str_hash("2.50"));
642 assert_eq!(hash_double(100.0), canonical_decimal_str_hash("100"));
643 assert_eq!(hash_double(100.0), canonical_decimal_str_hash("100.0"));
644 }
645
646 #[test]
647 fn subnormal_double_known_divergence() {
648 assert_eq!(hash_double(f64::from_bits(1)), 479);
652 assert_eq!(hash_double(5e-324), 479);
653 }
654
655 #[test]
656 fn keyword_display_form_deviation() {
657 let kw = Keyword::create(None, "a").unwrap();
660 assert_eq!(
661 kw.hash_calc(HashType::Rapid) as i64,
662 rapid::hash("::KEYWORD|:a".as_bytes()) as i64
663 );
664 let sym = Symbol::create(None, "a");
665 assert_eq!(
666 sym.hash_calc(HashType::Rapid) as i64,
667 rapid::hash("::SYMBOL|hara.lang.data.Symbol<a>".as_bytes()) as i64
668 );
669 assert_eq!(kw.hash_calc(HashType::Sip) as i64, -1);
671 assert_eq!(kw.display(), ":a");
673 assert_eq!(sym.display(), "a");
674 assert_eq!(kw.hash_seed(), "::KEYWORD");
675 assert_eq!(sym.hash_seed(), "::SYMBOL");
676 }
677}