const VERIFY_KEY: u32 = 0x1A2B3C4D;
pub(crate) struct VersionGen {
pub hash1: u32,
pub hash2: u32,
pub(crate) v2_results: Vec<u32>,
pub(crate) v3_results: Vec<u32>,
current_idx: usize,
}
#[derive(Debug)]
pub(crate) struct HashGenInfo<'a, F: Fn(u32, u32, u32) -> bool> {
s: u32,
low_bit_len: u32,
low_bits: u32,
target: u32,
carries: &'a mut [u32],
lhs_bits: &'a mut [u32],
validator: &'a F,
results: &'a mut Vec<u32>,
}
impl<'a, F: Fn(u32, u32, u32) -> bool> HashGenInfo<'a, F> {
pub fn new(
low_bit_len: u32,
target: u32,
carries: &'a mut [u32],
lhs_bits: &'a mut [u32],
results: &'a mut Vec<u32>,
validator: &'a F,
) -> Self {
Self {
s: 0,
low_bits: 0,
low_bit_len,
target,
carries,
lhs_bits,
results,
validator,
}
}
}
impl VersionGen {
pub fn new(hash1: u32, hash2: u32) -> Self {
Self {
hash1,
hash2,
v2_results: Vec::new(),
v3_results: Vec::new(),
current_idx: 0,
}
}
pub fn calc_hash_version_v1(&mut self) -> u32 {
self.hash1.rotate_left(7) ^ self.hash2
}
pub fn calc_hash_version_v2(&mut self) -> Vec<u32> {
let mut results: Vec<u32> = Vec::new();
let mut carries = [0; 33];
let mut lhs_bits = [0; 32];
let mut info = HashGenInfo::new(
5,
self.hash2,
&mut carries,
&mut lhs_bits,
&mut results,
&hash_verifier::verify_v2,
);
for s_candidate in 0..32 {
info.carries.fill(0);
info.lhs_bits.fill(0);
info.s = s_candidate;
info.low_bits = s_candidate;
self.backtrack(0, 0, &mut info);
}
results
}
pub fn calc_hash_version_v3(&mut self) -> Vec<u32> {
let mut results: Vec<u32> = Vec::new();
let mut carries = [0; 33];
let mut lhs_bits = [0; 32];
let mut info = HashGenInfo::new(
4,
(!self.hash2) ^ self.hash1,
&mut carries,
&mut lhs_bits,
&mut results,
&hash_verifier::verify_v3,
);
for s_candidate in 0_u32..16_u32 {
info.carries.fill(0);
info.lhs_bits.fill(0);
info.s = s_candidate.wrapping_add(self.hash1 & 0xf) as i32 as u32;
info.low_bits = s_candidate;
self.backtrack(0, 0, &mut info);
}
results
}
pub fn backtrack<'a, F: Fn(u32, u32, u32) -> bool>(
&mut self,
bit_idx: u32,
v_hash: u32,
info: &mut HashGenInfo<'a, F>,
) {
if bit_idx == 32 {
if (info.validator)(self.hash1, self.hash2, v_hash) {
info.results.push(v_hash);
}
return;
}
let start = if bit_idx < info.low_bit_len {
(info.low_bits >> bit_idx) & 1
} else {
0
};
let end = if bit_idx < info.low_bit_len {
(info.low_bits >> bit_idx) & 1
} else {
1
};
for v_bit in start..=end {
let prev_lhs_idx = (bit_idx.wrapping_sub(info.s).wrapping_add(32)) & 0x1f;
if prev_lhs_idx < bit_idx {
let v_xor_h2 = v_bit ^ ((info.target >> bit_idx) & 1);
if v_xor_h2 != info.lhs_bits[prev_lhs_idx as usize] {
continue;
}
}
let sum = v_bit + ((VERIFY_KEY >> bit_idx) & 1) + info.carries[bit_idx as usize];
let current_lhs_bit = (sum ^ (self.hash1 >> bit_idx)) & 1;
let future_v_idx = (bit_idx.wrapping_add(info.s)) & 0x1f;
if future_v_idx <= bit_idx {
let known_v_bit = (v_hash >> future_v_idx) & 1;
let target_v_xor_h2 = known_v_bit ^ ((info.target >> future_v_idx) & 1);
if current_lhs_bit != target_v_xor_h2 {
continue;
}
} else if future_v_idx < info.low_bit_len {
let known_v_bit = (info.low_bits >> future_v_idx) & 1;
let target_v_xor_h2 = known_v_bit ^ ((info.target >> future_v_idx) & 1);
if current_lhs_bit != target_v_xor_h2 {
continue;
}
}
info.lhs_bits[bit_idx as usize] = current_lhs_bit;
info.carries[bit_idx as usize + 1] = sum >> 1;
self.backtrack(bit_idx + 1, v_hash | (v_bit << bit_idx), info);
}
}
}
mod hash_verifier {
use super::VERIFY_KEY;
pub fn verify_v1(hash1: u32, hash2: u32, target_hash: u32) -> bool {
let lt = hash1.rotate_left(7) ^ target_hash;
lt == hash2
}
pub fn verify_v2(hash1: u32, hash2: u32, target_hash: u32) -> bool {
let rotate_base = hash1 ^ (target_hash.wrapping_add(VERIFY_KEY));
let lt = rotate_base.rotate_left((target_hash & 0x1f) as u32);
(lt ^ target_hash) == hash2
}
pub fn verify_v3(hash1: u32, hash2: u32, target_hash: u32) -> bool {
let rotate_base = hash1 ^ (target_hash.wrapping_add(VERIFY_KEY));
let rotate_amount = (target_hash & 0xf) + (hash1 & 0xf);
let lt = rotate_base.rotate_left(rotate_amount);
!(lt ^ target_hash ^ hash1) == hash2
}
}
impl Iterator for VersionGen {
type Item = u32;
fn next(&mut self) -> Option<Self::Item> {
if self.v3_results.len() == 0 {
self.v3_results = self.calc_hash_version_v3();
}
if self.current_idx < self.v3_results.len() {
let result = self.v3_results.get(self.current_idx).cloned();
self.current_idx += 1;
return result;
}
if self.v2_results.len() == 0 {
self.v2_results = self.calc_hash_version_v2();
}
if self.current_idx < self.v2_results.len() + self.v3_results.len() {
let result = self
.v2_results
.get(self.current_idx - self.v3_results.len())
.cloned();
self.current_idx += 1;
return result;
}
if self.current_idx <= self.v2_results.len() + self.v3_results.len() {
self.current_idx += 1;
Some(self.calc_hash_version_v1())
} else {
None
}
}
}
#[cfg(test)]
mod tests {
use super::*;
const HASH1: u32 = 0x0000abcd;
const HASH2: u32 = 0x12340000;
#[test]
fn test_pkg2_version_gen_v1() {
let mut version_gen = VersionGen::new(HASH1, HASH2);
let v = version_gen.calc_hash_version_v1();
assert!(hash_verifier::verify_v1(
version_gen.hash1,
version_gen.hash2,
v
));
}
#[test]
fn test_pkg2_version_gen_v2() {
let mut version_gen = VersionGen::new(HASH1, HASH2);
let result = version_gen.calc_hash_version_v2();
assert!(result.len() > 0);
assert!(hash_verifier::verify_v2(
version_gen.hash1,
version_gen.hash2,
result[0]
));
}
#[test]
fn test_pkg2_version_gen_v3() {
let mut version_gen = VersionGen::new(HASH1, HASH2);
let result = version_gen.calc_hash_version_v3();
assert!(result.len() > 0);
assert!(hash_verifier::verify_v3(
version_gen.hash1,
version_gen.hash2,
result[0]
));
}
#[test]
fn test_pkg2_version_gen_iterator() {
let mut version_gen = VersionGen::new(HASH1, HASH2);
let v = version_gen.next().unwrap();
assert!(version_gen.v3_results.len() > 0);
assert!(hash_verifier::verify_v3(
version_gen.hash1,
version_gen.hash2,
v
));
for _ in 0..version_gen.v3_results.len() - 1 {
_ = version_gen.next();
}
let v = version_gen.next().unwrap();
assert!(version_gen.v2_results.len() > 0);
assert!(hash_verifier::verify_v2(
version_gen.hash1,
version_gen.hash2,
v
));
for _ in 0..version_gen.v2_results.len() - 1 {
_ = version_gen.next();
}
let v = version_gen.next().unwrap();
assert!(hash_verifier::verify_v1(
version_gen.hash1,
version_gen.hash2,
v
));
assert!(version_gen.next().is_none());
}
}