refpack 5.0.4

A crate providing compression/decompression for the RefPack compression format, utilized by many early 2000s EA games
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

////////////////////////////////////////////////////////////////////////////////
// This Source Code Form is subject to the terms of the Mozilla Public         /
// License, v. 2.0. If a copy of the MPL was not distributed with this         /
// file, You can obtain one at https://mozilla.org/MPL/2.0/.                   /
//                                                                             /
////////////////////////////////////////////////////////////////////////////////

use std::cmp::min;

#[cfg(test)]
use crate::data::compression::match_length::match_length;
use crate::data::compression::prefix_search::HASH_CHAIN_BUFFER_SIZE;
use crate::data::compression::prefix_search::hash_table::PrefixTable;
#[cfg(test)]
use crate::data::compression::prefix_search::{PrefixSearcher, prefix};
#[cfg(test)]
use crate::data::control::LONG_LENGTH_MAX;
use crate::data::control::LONG_OFFSET_MAX;

pub(crate) struct HashChain {
    prefix_table: PrefixTable,
    hash_chain: Vec<u32>,
}

impl HashChain {
    pub fn new(bytes: usize) -> Self {
        Self {
            prefix_table: PrefixTable::new(bytes),
            hash_chain: vec![u32::MAX; min(bytes, HASH_CHAIN_BUFFER_SIZE)],
        }
    }

    pub fn insert(
        &mut self,
        prefix: [u8; 3],
        position: u32,
    ) -> impl Iterator<Item = u32> + use<'_> {
        let found_position = self
            .prefix_table
            .insert(prefix, position)
            .filter(|pos| position - pos <= LONG_OFFSET_MAX);
        self.hash_chain[position as usize % HASH_CHAIN_BUFFER_SIZE] =
            found_position.unwrap_or(u32::MAX);
        found_position.into_iter().chain(HashChainIter {
            hash_chain: self,
            orig_position: position,
            cur_position: found_position,
        })
    }
}

pub(crate) struct HashChainIter<'a> {
    hash_chain: &'a HashChain,
    orig_position: u32,
    cur_position: Option<u32>,
}

impl Iterator for HashChainIter<'_> {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        let position = self.cur_position?;

        let next_pos = self.hash_chain.hash_chain[position as usize % HASH_CHAIN_BUFFER_SIZE];
        self.cur_position =
            if next_pos == u32::MAX || self.orig_position - next_pos > LONG_OFFSET_MAX {
                None
            } else {
                Some(next_pos)
            };

        self.cur_position
    }
}

#[cfg(test)]
pub(crate) struct HashChainPrefixSearcher<'a> {
    buffer: &'a [u8],
    hash_chain: HashChain,
}

#[cfg(test)]
impl<'a> PrefixSearcher<'a> for HashChainPrefixSearcher<'a> {
    fn build(buffer: &'a [u8]) -> Self {
        let mut hash_chain = HashChain::new(buffer.len());

        let _ = hash_chain.insert(prefix(buffer), 0);

        Self { buffer, hash_chain }
    }

    fn search<F: FnMut(usize, usize, usize)>(&mut self, pos: usize, mut found_fn: F) {
        let mut min_length = 2;
        self.hash_chain
            .insert(prefix(&self.buffer[pos..]), pos as u32)
            .take_while(|found_pos| pos as u32 - found_pos <= LONG_OFFSET_MAX)
            .for_each(|found_pos| {
                let match_length = match_length(
                    self.buffer,
                    pos,
                    found_pos as usize,
                    LONG_LENGTH_MAX as usize,
                    3,
                );
                if match_length > min_length {
                    found_fn(found_pos as usize, min_length + 1, match_length + 1);
                    min_length = match_length;
                }
            });
    }
}