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
154
155
156
157
158
159
160
161
|
use alloc::boxed::Box;
use core::convert::TryInto;
/// The Hashtable trait used by the compression to store hashed bytes to their position.
/// `val` can be maximum the size of the input in bytes.
///
/// `pos` can have a maximum value of u16::MAX or 65535
/// If the hashtable is smaller it needs to reduce the pos to its space, e.g. by right
/// shifting.
///
/// Duplication dictionary size.
///
/// Every four bytes is assigned an entry. When this number is lower, fewer entries exists, and
/// thus collisions are more likely, hurting the compression ratio.
/// hashes and right shifts to a maximum value of 16bit, 65535
/// The right shift is done in order to not exceed, the hashtables capacity
#[inline]
fn hash(sequence: u32) -> u32 {
(sequence.wrapping_mul(2654435761_u32)) >> 16
}
/// hashes and right shifts to a maximum value of 16bit, 65535
/// The right shift is done in order to not exceed, the hashtables capacity
#[cfg(target_pointer_width = "64")]
#[inline]
fn hash5(sequence: usize) -> u32 {
let primebytes = if cfg!(target_endian = "little") {
889523592379_usize
} else {
11400714785074694791_usize
};
(((sequence << 24).wrapping_mul(primebytes)) >> 48) as u32
}
pub trait HashTable {
fn get_at(&self, pos: usize) -> usize;
fn put_at(&mut self, pos: usize, val: usize);
fn clear(&mut self);
#[inline]
#[cfg(target_pointer_width = "64")]
fn get_hash_at(input: &[u8], pos: usize) -> usize {
hash5(super::compress::get_batch_arch(input, pos)) as usize
}
#[inline]
#[cfg(target_pointer_width = "32")]
fn get_hash_at(input: &[u8], pos: usize) -> usize {
hash(super::compress::get_batch(input, pos)) as usize
}
}
const HASHTABLE_SIZE_4K: usize = 4 * 1024;
const HASHTABLE_BIT_SHIFT_4K: usize = 4;
#[derive(Debug)]
#[repr(align(64))]
pub struct HashTable4KU16 {
dict: Box<[u16; HASHTABLE_SIZE_4K]>,
}
impl HashTable4KU16 {
#[inline]
pub fn new() -> Self {
// This generates more efficient assembly in contrast to Box::new(slice), because of an
// optmized call alloc_zeroed, vs. alloc + memset
// try_into is optimized away
let dict = alloc::vec![0; HASHTABLE_SIZE_4K]
.into_boxed_slice()
.try_into()
.unwrap();
Self { dict }
}
}
impl HashTable for HashTable4KU16 {
#[inline]
fn get_at(&self, hash: usize) -> usize {
self.dict[hash >> HASHTABLE_BIT_SHIFT_4K] as usize
}
#[inline]
fn put_at(&mut self, hash: usize, val: usize) {
self.dict[hash >> HASHTABLE_BIT_SHIFT_4K] = val as u16;
}
#[inline]
fn clear(&mut self) {
self.dict.fill(0);
}
#[inline]
fn get_hash_at(input: &[u8], pos: usize) -> usize {
hash(super::get_batch(input, pos)) as usize
}
}
#[derive(Debug)]
pub struct HashTable4K {
dict: Box<[u32; HASHTABLE_SIZE_4K]>,
}
impl HashTable4K {
#[inline]
pub fn new() -> Self {
let dict = alloc::vec![0; HASHTABLE_SIZE_4K]
.into_boxed_slice()
.try_into()
.unwrap();
Self { dict }
}
#[cold]
#[allow(dead_code)]
pub fn reposition(&mut self, offset: u32) {
for i in self.dict.iter_mut() {
*i = i.saturating_sub(offset);
}
}
}
impl HashTable for HashTable4K {
#[inline]
fn get_at(&self, hash: usize) -> usize {
self.dict[hash >> HASHTABLE_BIT_SHIFT_4K] as usize
}
#[inline]
fn put_at(&mut self, hash: usize, val: usize) {
self.dict[hash >> HASHTABLE_BIT_SHIFT_4K] = val as u32;
}
#[inline]
fn clear(&mut self) {
self.dict.fill(0);
}
}
const HASHTABLE_SIZE_8K: usize = 8 * 1024;
const HASH_TABLE_BIT_SHIFT_8K: usize = 3;
#[derive(Debug)]
pub struct HashTable8K {
dict: Box<[u32; HASHTABLE_SIZE_8K]>,
}
#[allow(dead_code)]
impl HashTable8K {
#[inline]
pub fn new() -> Self {
let dict = alloc::vec![0; HASHTABLE_SIZE_8K]
.into_boxed_slice()
.try_into()
.unwrap();
Self { dict }
}
}
impl HashTable for HashTable8K {
#[inline]
fn get_at(&self, hash: usize) -> usize {
self.dict[hash >> HASH_TABLE_BIT_SHIFT_8K] as usize
}
#[inline]
fn put_at(&mut self, hash: usize, val: usize) {
self.dict[hash >> HASH_TABLE_BIT_SHIFT_8K] = val as u32;
}
#[inline]
fn clear(&mut self) {
self.dict.fill(0);
}
}
|
