libzstd_rs_sys/lib/compress/
zstd_preSplit.rs

1use core::ptr;
2
3use core::ffi::{c_char, c_int, c_uint, c_ulong, c_void};
4use libc::size_t;
5
6use crate::lib::common::mem::MEM_read16;
7use crate::lib::compress::hist::HIST_add;
8
9const ZSTD_SLIPBLOCK_WORKSPACESIZE: usize = 8208;
10
11pub const BLOCKSIZE_MIN: c_int = 3500;
12pub const THRESHOLD_PENALTY_RATE: c_int = 16;
13pub const THRESHOLD_BASE: c_int = THRESHOLD_PENALTY_RATE - 2;
14pub const THRESHOLD_PENALTY: c_int = 3;
15
16pub const HASHLENGTH: c_int = 2;
17pub const HASHLOG_MAX: c_uint = 10;
18pub const HASHTABLESIZE: c_int = (1) << HASHLOG_MAX;
19pub const KNUTH: c_uint = 0x9e3779b9;
20
21/// for `hashLog` > 8, hash 2 bytes.
22/// for `hashLog` == 8, just take the byte, no hashing.
23/// The speed of this method relies on compile-time constant propagation
24#[inline(always)]
25unsafe fn hash2(p: *const c_void, hashLog: c_uint) -> c_uint {
26    debug_assert!(hashLog >= 8);
27    if hashLog == 8 {
28        return *(p as *const u8) as u32;
29    }
30    debug_assert!(hashLog <= HASHLOG_MAX);
31    (MEM_read16(p) as u32).wrapping_mul(KNUTH) >> (32 as c_uint).wrapping_sub(hashLog)
32}
33
34#[repr(C)]
35pub struct Fingerprint {
36    pub events: [c_uint; 1024],
37    pub nbEvents: size_t,
38}
39
40#[repr(C)]
41pub struct FPStats {
42    pub pastEvents: Fingerprint,
43    pub newEvents: Fingerprint,
44}
45
46unsafe fn initStats(fpstats: *mut FPStats) {
47    ptr::write_bytes(fpstats as *mut u8, 0, size_of::<FPStats>());
48}
49
50#[inline(always)]
51unsafe fn addEvents_generic(
52    fp: &mut Fingerprint,
53    src: *const c_void,
54    srcSize: size_t,
55    samplingRate: size_t,
56    hashLog: c_uint,
57) {
58    let p = src as *const c_char;
59    let limit = srcSize.wrapping_sub(HASHLENGTH as size_t).wrapping_add(1);
60    let mut n: size_t = 0;
61
62    debug_assert!(srcSize >= HASHLENGTH as usize);
63    while n < limit {
64        fp.events[hash2(p.add(n) as *const c_void, hashLog) as usize] += 1;
65        n = n.wrapping_add(samplingRate);
66    }
67
68    fp.nbEvents += limit / samplingRate;
69}
70
71#[inline(always)]
72unsafe fn recordFingerprint_generic<const SAMPLING_RATE: size_t, const HASH_LOG: c_uint>(
73    fp: &mut Fingerprint,
74    src: *const c_void,
75    srcSize: size_t,
76) {
77    ptr::write_bytes(fp as *mut _ as *mut u8, 0, size_of::<c_uint>() << HASH_LOG);
78    fp.nbEvents = 0;
79    addEvents_generic(fp, src, srcSize, SAMPLING_RATE, HASH_LOG);
80}
81
82fn abs64(s64: i64) -> u64 {
83    s64.unsigned_abs()
84}
85
86unsafe fn fpDistance(fp1: &Fingerprint, fp2: *const Fingerprint, hashLog: c_uint) -> u64 {
87    let mut distance = 0u64;
88
89    debug_assert!(hashLog <= HASHLOG_MAX);
90
91    for n in 0..((1) << hashLog) {
92        distance = distance.wrapping_add(abs64(
93            fp1.events[n as usize] as i64 * (*fp2).nbEvents as i64
94                - ((*fp2).events)[n as usize] as i64 * fp1.nbEvents as i64,
95        ));
96    }
97    distance
98}
99
100/// Compares new events with past events.
101///
102/// Returns `1` when the fingerprints are considered "too different", `0` otherwise.
103unsafe fn compareFingerprints(
104    ref_0: &Fingerprint,
105    newfp: &Fingerprint,
106    penalty: c_int,
107    hashLog: c_uint,
108) -> c_int {
109    debug_assert!(ref_0.nbEvents > 0);
110    debug_assert!(newfp.nbEvents > 0);
111
112    let p50 = ref_0.nbEvents * newfp.nbEvents;
113    let deviation = fpDistance(ref_0, newfp, hashLog);
114    let threshold = p50 as u64 * (THRESHOLD_BASE + penalty) as u64 / THRESHOLD_PENALTY_RATE as u64;
115    (deviation >= threshold) as c_int
116}
117
118fn mergeEvents(acc: &mut Fingerprint, newfp: &Fingerprint) {
119    for n in 0..HASHTABLESIZE as usize {
120        acc.events[n] += newfp.events[n];
121    }
122    acc.nbEvents += newfp.nbEvents;
123}
124
125pub const CHUNKSIZE: c_int = (8) << 10;
126
127unsafe fn ZSTD_splitBlock_byChunks(
128    blockStart: *const c_void,
129    blockSize: size_t,
130    level: c_int,
131    workspace: *mut c_void,
132    wkspSize: size_t,
133) -> size_t {
134    static records_fs: [unsafe fn(&mut Fingerprint, *const c_void, size_t) -> (); 4] = [
135        recordFingerprint_generic::<1, 10>,
136        recordFingerprint_generic::<5, 10>,
137        recordFingerprint_generic::<11, 9>,
138        recordFingerprint_generic::<43, 8>,
139    ];
140
141    static hashParams: [c_uint; 4] = [8, 9, 10, 10];
142    debug_assert!((0..=3).contains(&level));
143    let record_f = *records_fs.as_ptr().offset(level as isize);
144    let fpstats = workspace as *mut FPStats;
145    let p = blockStart as *const c_char;
146    let mut penalty = THRESHOLD_PENALTY;
147    let mut pos = 0;
148
149    debug_assert_eq!(blockSize, (128 << 10));
150    debug_assert!(!workspace.is_null());
151    debug_assert!(workspace.cast::<FPStats>().is_aligned());
152    const { debug_assert!(ZSTD_SLIPBLOCK_WORKSPACESIZE >= size_of::<FPStats>()) }
153    debug_assert!(wkspSize >= size_of::<FPStats>());
154
155    initStats(fpstats);
156    record_f(
157        &mut (*fpstats).pastEvents,
158        p as *const c_void,
159        CHUNKSIZE as size_t,
160    );
161    pos = CHUNKSIZE as size_t;
162    while pos <= blockSize.wrapping_sub(CHUNKSIZE as size_t) {
163        record_f(
164            &mut (*fpstats).newEvents,
165            p.add(pos) as *const c_void,
166            CHUNKSIZE as size_t,
167        );
168        if compareFingerprints(
169            &(*fpstats).pastEvents,
170            &(*fpstats).newEvents,
171            penalty,
172            *hashParams.as_ptr().offset(level as isize),
173        ) != 0
174        {
175            return pos;
176        } else {
177            mergeEvents(&mut (*fpstats).pastEvents, &(*fpstats).newEvents);
178            if penalty > 0 {
179                penalty -= 1;
180            }
181        }
182        pos = pos.wrapping_add(CHUNKSIZE as size_t);
183    }
184    debug_assert!(pos == blockSize);
185    blockSize
186}
187
188/// Very fast block splitting strategy.
189///
190/// Compares fingerprints from the beginning and end of the block, and derives from their
191/// difference whether it's preferable to split in the middle. The process is repeated a
192/// second time for finer-grained decisions.
193///
194/// Testing showed that 3 iterations did not bring improvements, so stopped at 2.
195/// Benefits are good enough for a cheap heuristic. More accurate splitting saves more,
196/// but speed impact is also more perceptible.
197///
198/// For better accuracy, use the more elaborate `*_byChunks` variant.
199unsafe fn ZSTD_splitBlock_fromBorders(
200    blockStart: *const c_void,
201    blockSize: size_t,
202    workspace: *mut c_void,
203    wkspSize: size_t,
204) -> size_t {
205    const SEGMENT_SIZE: c_int = 512;
206
207    let fpstats = workspace as *mut FPStats;
208    let middleEvents = (workspace as *mut c_char)
209        .offset((512 as c_ulong).wrapping_mul(size_of::<c_uint>() as c_ulong) as isize)
210        as *mut c_void as *mut Fingerprint;
211
212    debug_assert_eq!(blockSize, (128 << 10));
213    debug_assert!(!workspace.is_null());
214    debug_assert!(workspace.cast::<FPStats>().is_aligned());
215    const { assert!(ZSTD_SLIPBLOCK_WORKSPACESIZE >= size_of::<FPStats>()) }
216    debug_assert!(wkspSize >= size_of::<FPStats>());
217
218    initStats(fpstats);
219    HIST_add(
220        ((*fpstats).pastEvents.events).as_mut_ptr(),
221        blockStart,
222        SEGMENT_SIZE as size_t,
223    );
224    HIST_add(
225        ((*fpstats).newEvents.events).as_mut_ptr(),
226        (blockStart as *const c_char)
227            .add(blockSize)
228            .offset(-(SEGMENT_SIZE as isize)) as *const c_void,
229        SEGMENT_SIZE as size_t,
230    );
231    (*fpstats).newEvents.nbEvents = SEGMENT_SIZE as size_t;
232    (*fpstats).pastEvents.nbEvents = (*fpstats).newEvents.nbEvents;
233    if compareFingerprints(&(*fpstats).pastEvents, &(*fpstats).newEvents, 0, 8) == 0 {
234        return blockSize;
235    }
236    HIST_add(
237        ((*middleEvents).events).as_mut_ptr(),
238        (blockStart as *const c_char)
239            .add(blockSize / 2)
240            .offset(-((SEGMENT_SIZE / 2) as isize)) as *const c_void,
241        SEGMENT_SIZE as size_t,
242    );
243    (*middleEvents).nbEvents = SEGMENT_SIZE as size_t;
244    let distFromBegin = fpDistance(&(*fpstats).pastEvents, middleEvents, 8);
245    let distFromEnd = fpDistance(&(*fpstats).newEvents, middleEvents, 8);
246    let minDistance = (SEGMENT_SIZE * SEGMENT_SIZE / 3) as u64;
247    if abs64(distFromBegin as i64 - distFromEnd as i64) < minDistance {
248        return (64 * ((1) << 10)) as size_t;
249    }
250    (if distFromBegin > distFromEnd {
251        32 * ((1) << 10)
252    } else {
253        96 * ((1) << 10)
254    }) as size_t
255}
256
257/// Splits a block to find the optimal boundary for compression.
258///
259/// # Parameters
260///
261/// * `blockStart` - Pointer to the start of the block
262/// * `blockSize` - Size of the block (must be 128 KB)
263/// * `level` - Detection level (0-4). Higher levels spend more energy to detect block boundaries.
264/// * `workspace` - Workspace buffer (must be aligned for `size_t`)
265/// * `wkspSize` - Workspace size (must be at least `ZSTD_SLIPBLOCK_WORKSPACESIZE`)
266///
267/// # Note
268///
269/// For the time being, this function only accepts full 128 KB blocks.
270/// While this could be extended to smaller sizes in the future,
271/// it is not yet clear if this would be useful. TBD.
272pub unsafe fn ZSTD_splitBlock(
273    blockStart: *const c_void,
274    blockSize: size_t,
275    level: c_int,
276    workspace: *mut c_void,
277    wkspSize: size_t,
278) -> size_t {
279    debug_assert!((0..=4).contains(&level));
280    if level == 0 {
281        return ZSTD_splitBlock_fromBorders(blockStart, blockSize, workspace, wkspSize);
282    }
283
284    // level >= 1
285    ZSTD_splitBlock_byChunks(blockStart, blockSize, level - 1, workspace, wkspSize)
286}
libzstd_rs_sys/lib/compress/zstd_preSplit.rs

libzstd_rs_sys/lib/compress/
zstd_preSplit.rs
