swh_graph/java_compat/sf/
gov3.rs1use crate::java_compat::mph::spooky::{spooky_short, spooky_short_rehash};
13use anyhow::Result;
14use std::fs::File;
15use std::io::BufReader;
16use std::io::Read;
17use std::path::Path;
18
19#[derive(Debug)]
40pub struct GOV3 {
41 pub size: u64,
42 pub width: u64,
43 pub multiplier: u64,
44 pub global_seed: u64,
45 pub offset_and_seed: Vec<u64>,
46 pub array: Vec<u64>,
47}
48
49impl GOV3 {
50 pub fn load<P: AsRef<Path>>(path: P) -> Result<Self> {
53 Self::load_reader(BufReader::new(File::open(path.as_ref())?))
54 }
55
56 pub fn load_reader<F: Read>(mut file: F) -> Result<Self> {
58 macro_rules! read {
59 ($file:expr, $type:ty) => {{
60 let mut buffer: [u8; core::mem::size_of::<$type>()] =
61 [0; core::mem::size_of::<$type>()];
62 $file.read_exact(&mut buffer)?;
63 <$type>::from_le_bytes(buffer)
64 }};
65 }
66
67 macro_rules! read_array {
68 ($file:expr, $type:ty) => {{
69 let len = read!($file, u64) as usize;
71 let mut buffer: Vec<u64> = vec![0; len];
72 $file.read_exact(bytemuck::cast_slice_mut(&mut buffer))?;
74 buffer
75 }};
76 }
77 let size = read!(file, u64);
79 let width = read!(file, u64);
80 let multiplier = read!(file, u64);
81 let global_seed = read!(file, u64);
82 let offset_and_seed = read_array!(file, u64);
83 let array = read_array!(file, u64);
84
85 Ok(Self {
86 size,
87 width,
88 multiplier,
89 global_seed,
90 offset_and_seed,
91 array,
92 })
93 }
94}
95
96impl GOV3 {
97 pub fn size(&self) -> u64 {
98 self.size
99 }
100
101 pub fn get_byte_array(&self, key: &[u8]) -> u64 {
102 let signature = spooky_short(key, self.global_seed);
103 let bucket = ((((signature[0] as u128) >> 1) * (self.multiplier as u128)) >> 64) as u64;
104 let offset_seed = self.offset_and_seed[bucket as usize];
105 let bucket_offset = offset_seed & OFFSET_MASK;
106 let num_variables =
107 (self.offset_and_seed[bucket as usize + 1] & OFFSET_MASK) - bucket_offset;
108 let e = signature_to_equation(&signature, offset_seed & (!OFFSET_MASK), num_variables);
109 get_value(&self.array, e[0] + bucket_offset, self.width)
110 ^ get_value(&self.array, e[1] + bucket_offset, self.width)
111 ^ get_value(&self.array, e[2] + bucket_offset, self.width)
112 }
113}
114
115const OFFSET_MASK: u64 = u64::MAX >> 8;
116
117#[inline(always)]
118#[must_use]
119fn signature_to_equation(signature: &[u64; 4], seed: u64, num_variables: u64) -> [u64; 3] {
120 let hash = spooky_short_rehash(signature, seed);
121 let shift = num_variables.leading_zeros();
122 let mask = (1_u64 << shift) - 1;
123 [
124 ((hash[0] & mask) * num_variables) >> shift,
125 ((hash[1] & mask) * num_variables) >> shift,
126 ((hash[2] & mask) * num_variables) >> shift,
127 ]
128}
129
130#[inline(always)]
131#[must_use]
132fn get_value(array: &[u64], mut pos: u64, width: u64) -> u64 {
133 pos *= width;
134 let l = 64 - width;
135 let start_word = pos / 64;
136 let start_bit = pos % 64;
137 if start_bit <= l {
138 (array[start_word as usize] << (l - start_bit)) >> l
139 } else {
140 (array[start_word as usize] >> start_bit)
141 | ((array[start_word as usize + 1] << (64 + l - start_bit)) >> l)
142 }
143}