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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
use super::*;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct PreparedDictionaryMatchStateKey {
pub(crate) parser_strategy: ParserStrategy,
pub(crate) hash_bits: u32,
pub(crate) chain_log: u32,
pub(crate) window_log: u32,
pub(crate) search_log: u32,
pub(crate) search_depth: usize,
pub(crate) min_match: u32,
}
impl PreparedDictionaryMatchStateKey {
/// Keyed on the geometry the tables are actually built with, which for
/// every field the dictionary has its own of is the dictionary's. Keying
/// on `applied` instead would hand back a cached state built for a
/// different table size the moment two sources of different lengths share
/// a dictionary.
///
/// So the fields here are exactly the ones
/// [`build_prepared_dictionary_match_state`] reads, and no others. Both
/// directions matter. A field the builder reads and the key omits hands
/// back tables of the wrong shape; a field the key carries and the builder
/// ignores splits the cache on a distinction that cannot change what is
/// stored, so the same tables are built again under a second key.
///
/// `secondary_hash_bits` used to be here and was the second kind. It sizes
/// the *source* side of DoubleFast's two tables
/// (`PrefixedBlockMatchState::new_with_prepared_match_state`) and reaches
/// no dictionary table on any strategy — the dictionary's short table comes
/// from `dictionary_chain_log`. Because it is derived from the *adjusted*
/// chain log, it moves with the source size below the attach cutoff, so one
/// dictionary at one level keyed three different ways across a spread of
/// small inputs and rebuilt identical tables for each. Small inputs are
/// where a prepared dictionary earns the most, so the split was worst
/// exactly where the cache mattered.
pub(crate) fn new(params: MatchFinderParameters) -> Self {
Self {
parser_strategy: params.parser_strategy,
hash_bits: params.dictionary_hash_bits(),
chain_log: params.dictionary_chain_log(),
window_log: params.dictionary_window_log(),
search_log: params.search_log,
search_depth: params.search_depth,
min_match: params.min_match,
}
}
}
#[derive(Debug, Clone)]
pub(crate) enum PreparedDictionaryMatchState {
Chain(PreparedChainDictionaryTables),
Fast(Arc<PreparedFastDictionaryTables>),
DoubleFast(Arc<PreparedDoubleFastDictionaryTables>),
Row(PreparedRowDictionaryTables),
BinaryTree(PreparedBinaryTreeDictionaryTables),
}
impl PreparedDictionaryMatchState {
pub(crate) fn chain_table_allocated(&self) -> bool {
matches!(
self,
Self::Chain(_) | Self::DoubleFast(_) | Self::BinaryTree(_)
)
}
pub(crate) fn row_hash_log(&self) -> Option<u32> {
match self {
Self::Row(finder) => Some(finder.row_hash_log()),
_ => None,
}
}
}
pub(crate) fn build_prepared_dictionary_match_state(
prefix: &[u8],
params: MatchFinderParameters,
) -> Option<PreparedDictionaryMatchState> {
if prefix.is_empty() {
return None;
}
Some(match params.parser_strategy {
strategy if strategy.is_row_hash() => {
let mut finder = RowHashFinder::new(
params.dictionary_hash_bits(),
params.search_log,
params.min_match,
);
finder.hash_salt = 0;
finder.insert_prefix(prefix);
PreparedDictionaryMatchState::Row(PreparedRowDictionaryTables {
prefix_finder: Arc::new(finder),
})
}
strategy if strategy.is_hash_chain() => {
let mut finder = MatchFinder::with_chain_log(
prefix.len(),
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
);
let prefix_refs = [prefix];
let prefix_chain = PrefixChain::new(&prefix_refs)
.expect("single prefix must not overflow")
.expect("single non-empty prefix expected");
finder.insert_prefix_chain_for_cdict(prefix_chain);
PreparedDictionaryMatchState::Chain(PreparedChainDictionaryTables {
prefix_finder: Arc::new(finder),
})
}
ParserStrategy::Fast => {
PreparedDictionaryMatchState::Fast(Arc::new(PreparedFastDictionaryTables::build(
prefix,
params.dictionary_hash_bits(),
params.min_match,
)))
}
// C reads both of DoubleFast's dictionary tables off the dictionary's
// own parameters: the long table from `dictCParams->hashLog` and the
// short one from `dictCParams->chainLog`
// (`zstd_double_fast.c:414`). `secondary_hash_bits` *is* `chain_log`
// on this strategy — see its derivation in `encode.rs` — so the
// dictionary's chain log is the right value to pass, not a second
// dictionary-specific field.
ParserStrategy::DoubleFast => PreparedDictionaryMatchState::DoubleFast(Arc::new(
PreparedDoubleFastDictionaryTables::build(
prefix,
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
),
)),
strategy if strategy.is_binary_tree() => {
let mut finder = BinaryTreeFinder::new(
params.dictionary_hash_bits(),
params.dictionary_chain_log(),
params.min_match,
)
.with_window_log(params.dictionary_window_log());
let prefix_refs = [prefix];
let prefix_chain = PrefixChain::new(&prefix_refs)
.expect("single prefix must not overflow")
.expect("single non-empty prefix expected");
finder.insert_prefix_chain(prefix_chain, &[], params.search_depth);
PreparedDictionaryMatchState::BinaryTree(PreparedBinaryTreeDictionaryTables {
prefix_finder: Arc::new(finder),
})
}
_ => return None,
})
}