swh_graph/java_compat/sf/
gov3.rs

1/*
2 *
3 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
4 * SPDX-FileCopyrightText: 2023 Inria
5 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
6 *
7 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
8 */
9
10//! Ported from <https://github.com/vigna/Sux4J/blob/master/c/sf3.c>
11
12use 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/// A stub to load and access Genuzio-Ottaviano-Vigna static functions.
20///
21/// To generate the structure you must use the Java version:
22/// ```bash
23/// java it.unimi.dsi.sux4j.mph.GOV3Function --byte-array SOURCE test.sf
24/// ```
25///
26/// To obtain a file that can be read by this structure, load
27/// the serialized Java instance of the static function and
28/// dump it in C-compatible format:
29/// ```shell
30/// echo '((it.unimi.dsi.sux4j.mph.GOV3Function)it.unimi.dsi.fastutil.io.BinIO.loadObject("test.sf")).dump("test.csf");' | jshell
31/// ```
32///
33/// You can now load the dumped file with the [`load`](GOV3::load) method.
34///
35/// # Reference:
36/// - [Marco Genuzio, Giuseppe Ottaviano, and Sebastiano Vigna, Fast Scalable Construction of (Minimal Perfect Hash) Functions](https://arxiv.org/pdf/1603.04330.pdf)
37/// - [Java version with `dump` method](https://github.com/vigna/Sux4J/blob/master/src/it/unimi/dsi/sux4j/mph/GOV3Function.java)
38
39#[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    /// Given a path to a file `.csf3` generated from the java version,
51    /// load a GOV3 structure from a file
52    pub fn load<P: AsRef<Path>>(path: P) -> Result<Self> {
53        Self::load_reader(BufReader::new(File::open(path.as_ref())?))
54    }
55
56    /// Given a generic `Read` implementor, load a GOV3 structure from a file.
57    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                // create a bytes buffer big enough for $len elements of type $type
70                let len = read!($file, u64) as usize;
71                let mut buffer: Vec<u64> = vec![0; len];
72                // read the file in the buffer
73                $file.read_exact(bytemuck::cast_slice_mut(&mut buffer))?;
74                buffer
75            }};
76        }
77        // actually load the data :)
78        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}
swh_graph/java_compat/sf/gov3.rs

swh_graph/java_compat/sf/
gov3.rs
