donet_core/
hashgen.rs

1/*
2    This file is part of Donet.
3
4    Copyright © 2024 Max Rodriguez
5
6    Donet is free software; you can redistribute it and/or modify
7    it under the terms of the GNU Affero General Public License,
8    as published by the Free Software Foundation, either version 3
9    of the License, or (at your option) any later version.
10
11    Donet is distributed in the hope that it will be useful,
12    but WITHOUT ANY WARRANTY; without even the implied warranty of
13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14    GNU Affero General Public License for more details.
15
16    You should have received a copy of the GNU Affero General Public
17    License along with Donet. If not, see <https://www.gnu.org/licenses/>.
18*/
19
20//! Prime Number Generator and 32-bit DC File Hash generator based off Panda3D.
21
22use crate::globals::{DCFileHash, MAX_PRIME_NUMBERS};
23
24/// Trait shared by all DC element structures to generate the DC file hash
25/// using the same hashing method as the original DClass library from Panda.
26pub trait LegacyDCHash {
27    /// Accumulates the properties of this DC element into the file hash.
28    fn generate_hash(&self, hashgen: &mut DCHashGenerator);
29}
30
31/// Prime number generator based off Panda's.
32pub struct PrimeNumberGenerator {
33    primes: Vec<u16>,
34}
35
36impl Default for PrimeNumberGenerator {
37    fn default() -> Self {
38        Self { primes: vec![2_u16] }
39    }
40}
41
42impl PrimeNumberGenerator {
43    /// Returns the nth prime number. this\[0\] returns 2, this\[1\] returns 3;
44    /// successively larger values of n return larger prime numbers, up to the
45    /// largest prime number that can be represented in an int.
46    pub fn get_prime(&mut self, n: u16) -> u16 {
47        // Compute the prime numbers between the last-computed prime number and n.
48        let mut candidate: u16 = self.primes.last().unwrap() + 1_u16;
49
50        while self.primes.len() <= usize::from(n) {
51            // Is candidate prime?  It is not if any one of the already-found prime
52            // numbers (up to its square root) divides it evenly.
53            let mut maybe_prime: bool = true;
54            let mut j: usize = 0;
55
56            while maybe_prime && self.primes.get(j).unwrap() * self.primes.get(j).unwrap() <= candidate {
57                if (self.primes.get(j).unwrap() * (candidate / self.primes.get(j).unwrap())) == candidate {
58                    // This one is not prime.
59                    maybe_prime = false;
60                }
61                j += 1;
62                assert!(j < self.primes.len());
63            }
64
65            if maybe_prime {
66                self.primes.push(candidate);
67            }
68            candidate += 1;
69        }
70        *self.primes.get(usize::from(n)).unwrap()
71    }
72}
73
74/// The following is an excerpt from Panda3D's source:
75///
76/// We multiply each consecutive integer by the next prime number and add it to
77/// the total. This will generate pretty evenly-distributed hash numbers for
78/// an arbitrary sequence of integers.
79///
80/// We do recycle the prime number table at some point, just to keep it from
81/// growing insanely large, however (and to avoid wasting time computing large
82/// prime numbers unnecessarily), and we also truncate the result to the low-
83/// order 32 bits.
84#[derive(Default)]
85pub struct DCHashGenerator {
86    hash: i32,
87    index: u16,
88    primes: PrimeNumberGenerator,
89}
90
91impl DCHashGenerator {
92    /// Adds another integer to the hash so far.
93    pub fn add_int(&mut self, number: i32) {
94        assert!(self.index < MAX_PRIME_NUMBERS);
95
96        self.hash += i32::from(self.primes.get_prime(self.index)) * number;
97        self.index = (self.index + 1) % MAX_PRIME_NUMBERS;
98    }
99
100    /// Adds a blob to the hash, by breaking it down into a sequence of integers.
101    pub fn add_blob(&mut self, blob: Vec<u8>) {
102        self.add_int(blob.len().try_into().unwrap());
103
104        for byte in blob.into_iter() {
105            self.add_int(i32::from(byte));
106        }
107    }
108
109    /// Adds a string to the hash, by breaking it down into a sequence of integers.
110    pub fn add_string(&mut self, string: String) {
111        self.add_blob(string.into_bytes());
112    }
113
114    pub const fn get_hash(&self) -> DCFileHash {
115        self.hash as u32
116    }
117}
118
119#[cfg(test)]
120mod tests {
121    use super::PrimeNumberGenerator;
122
123    #[test]
124    fn prime_number_generator_integrity() {
125        let mut generator: PrimeNumberGenerator = PrimeNumberGenerator::default();
126
127        let prime_numbers: Vec<u16> = vec![
128            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
129            101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
130            197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307,
131            311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
132            431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547,
133            557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
134            661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
135            809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929,
136        ];
137
138        for (i, target_prime) in prime_numbers.into_iter().enumerate() {
139            assert_eq!(target_prime, generator.get_prime(i.try_into().unwrap()));
140        }
141    }
142}
donet_core/hashgen.rs

donet_core/
hashgen.rs
