donet_core/
hashgen.rs

1/*
2    This file is part of Donet.
3
4    Copyright © 2024-2025 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 Astron.
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 dclass library from Astron.
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: i64,
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 += i64::from(self.primes.get_prime(self.index)) * i64::from(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    /// Gets the DC file hash, a 32-bit value.
115    ///
116    /// It is internally stored as an `i64`, but gets truncated to a `u32`.
117    pub const fn get_hash(&self) -> DCFileHash {
118        self.hash as u32
119    }
120}
121
122#[cfg(test)]
123mod tests {
124    use super::PrimeNumberGenerator;
125
126    #[test]
127    fn prime_number_generator_integrity() {
128        let mut generator: PrimeNumberGenerator = PrimeNumberGenerator::default();
129
130        let prime_numbers: Vec<u16> = vec![
131            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,
132            101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
133            197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307,
134            311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
135            431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547,
136            557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
137            661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
138            809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929,
139        ];
140
141        for (i, target_prime) in prime_numbers.into_iter().enumerate() {
142            assert_eq!(target_prime, generator.get_prime(i.try_into().unwrap()));
143        }
144    }
145}
donet_core/hashgen.rs

donet_core/
hashgen.rs
