zrip-encode 0.9.8

zstd encoder for zrip (internal crate)
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
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
//! Sans-io frame state shared by [`FrameEncoder`](crate::streaming::FrameEncoder)
//! and [`PushEncoder`](crate::push::PushEncoder).
//!
//! Buffers input up to one block, encodes blocks with the window and match
//! tables carried across them, and appends frame bytes to a caller's `Vec`.
#![forbid(unsafe_code)]

use alloc::vec::Vec;

use crate::block_encoder::{self, BlockEncodeWorkspace};
use crate::context;
use crate::dfast;
use crate::fast;
#[cfg(feature = "ldm")]
use crate::ldm::LdmState;
use crate::rebase::reduce_hash_table;
use crate::strategy::{self, LevelParams, Strategy};
use crate::table::MatchTable;
use crate::write_frame_header_without_content_size;
use zrip_core::Sequence;
use zrip_core::dict::Dictionary;
use zrip_core::error::CompressError;
use zrip_core::frame::MAX_BLOCK_SIZE;
use zrip_core::huffman::encode::HuffmanEncodeTable;
use zrip_core::xxhash::Xxh64State;

/// Smallest growth step for the window once a frame spans blocks.
const GROW_STEP: usize = 8 << 20;

/// How many table entries a whole clear must zero per slot store before
/// rehashing a window to zero just the slots its positions went to pays.
/// Measured break-even: 16-23 entries per store.
const SLOT_CLEAR_RATIO: usize = 24;

/// Whether rehashing a `window`-byte window into `tables` tables to zero the
/// slots it filled beats clearing their `entries` entries whole.
pub(crate) fn slot_clear_pays(window: usize, tables: usize, entries: usize) -> bool {
    window.saturating_mul(tables * SLOT_CLEAR_RATIO) <= entries
}

pub(crate) struct EncodeState {
    params: LevelParams,
    rep_offsets: [u32; 3],
    hasher: Xxh64State,
    workspace: BlockEncodeWorkspace,
    dict: Option<Dictionary>,
    first_block: bool,
    hash_table: MatchTable,
    hash_long: MatchTable,
    sequences: Vec<Sequence>,
    /// The window: dictionary, then input, then the next block's input from
    /// `block_start`. Input goes straight here, so blocks need no copy.
    window_buf: Vec<u8>,
    block_start: usize,
    /// The tables are clean or hold this frame's positions. Set by the
    /// frame's first block that searches for matches.
    tables_ready: bool,
    /// A copy of the last window that wrote the tables, while they still
    /// hold its positions and it was small: the next frame zeroes just the
    /// slots those positions went to instead of the whole tables.
    stale_window: Vec<u8>,
    /// Buffers of frames encoded in one pass, kept for the next.
    dict_hash: MatchTable,
    combined: Vec<u8>,
    #[cfg(feature = "ldm")]
    ldm_state: Option<LdmState>,
}

impl EncodeState {
    pub(crate) fn new(params: LevelParams, dict: Option<Dictionary>) -> Self {
        let (rep_offsets, first_block) = match &dict {
            Some(d) => (*d.rep_offsets(), true),
            None => ([1, 4, 8], false),
        };
        let mut window_buf = Vec::new();
        if let Some(ref d) = dict {
            window_buf.extend_from_slice(d.content());
        }
        let block_start = window_buf.len();
        #[cfg(feature = "ldm")]
        let ldm_state = params.ldm_params.as_ref().map(LdmState::new);
        Self {
            params,
            rep_offsets,
            hasher: Xxh64State::new(0),
            workspace: BlockEncodeWorkspace::new(),
            dict,
            first_block,
            // Allocated by the first block, so frames that never need them
            // (see `PushEncoder`) skip zeroing them.
            hash_table: MatchTable::new(),
            hash_long: MatchTable::new(),
            sequences: Vec::new(),
            window_buf,
            block_start,
            tables_ready: false,
            stale_window: Vec::new(),
            dict_hash: MatchTable::new(),
            combined: Vec::new(),
            #[cfg(feature = "ldm")]
            ldm_state,
        }
    }

    /// Encodes `input`, or the buffered input if `None`, as one whole frame
    /// with its size known, as the one-shot API does, but in this state's
    /// tables and buffers. Call [`Self::reset`] after it.
    pub(crate) fn encode_one_pass(
        &mut self,
        input: Option<&[u8]>,
        params: &LevelParams,
        out: &mut Vec<u8>,
    ) -> Result<(), CompressError> {
        let src = match input {
            Some(input) => input,
            None => &self.window_buf[self.block_start..],
        };
        #[cfg(feature = "ldm")]
        if params.ldm_params.is_some() {
            return crate::compress_frame(src, params, out);
        }
        // Whole clears follow: the tables no longer hold just the last
        // window's positions.
        self.stale_window.clear();
        let (dict_id, prefix, rep_offsets) = match &self.dict {
            Some(d) => {
                self.workspace.prev_ll = d
                    .ll_table()
                    .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 35));
                self.workspace.prev_of = d
                    .of_table()
                    .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 31));
                self.workspace.prev_ml = d
                    .ml_table()
                    .map(|(dt, al)| block_encoder::FseEncodeTable::from_decode_table(dt, al, 52));
                self.workspace.prev_huffman = d
                    .huf_table()
                    .and_then(|(dt, tl)| HuffmanEncodeTable::from_decode_table(dt, tl));
                (Some(d.id()), d.content(), *d.rep_offsets())
            }
            None => (None, &[][..], [1, 4, 8]),
        };
        context::compress_core(
            src,
            *params,
            dict_id,
            prefix,
            rep_offsets,
            &mut self.hash_table,
            &mut self.hash_long,
            &mut self.dict_hash,
            &mut self.sequences,
            out,
            &mut self.workspace,
            &mut self.combined,
            true,
        )
    }

    /// Starts a new frame, keeping allocations. Drops buffered input.
    pub(crate) fn reset(&mut self) {
        // The tables keep this frame's positions until the next frame uses
        // them. A small window is kept to zero just their slots then.
        if self.tables_ready {
            self.stale_window.clear();
            if self.slot_clear_pays() {
                self.stale_window.extend_from_slice(&self.window_buf);
            }
            self.tables_ready = false;
        }
        self.first_block = self.dict.is_some();
        self.rep_offsets = match &self.dict {
            Some(d) => *d.rep_offsets(),
            None => [1, 4, 8],
        };
        self.hasher = Xxh64State::new(0);
        self.workspace.prev_huffman = None;
        self.window_buf.clear();
        if let Some(ref d) = self.dict {
            self.window_buf.extend_from_slice(d.content());
        }
        self.block_start = self.window_buf.len();
        #[cfg(feature = "ldm")]
        if let Some(ref mut ldm) = self.ldm_state {
            ldm.reset();
        }
    }

    /// Whether the window's positions are few enough next to the table
    /// entries to zero their slots instead of the whole tables.
    fn slot_clear_pays(&self) -> bool {
        #[cfg(feature = "ldm")]
        if self.ldm_state.is_some() {
            return false;
        }
        let tables = if self.hash_long.is_empty() { 1 } else { 2 };
        slot_clear_pays(
            self.window_buf.len(),
            tables,
            self.hash_table.len() + self.hash_long.len(),
        )
    }

    /// Readies the tables for the frame's first match search: zero, at the
    /// sizes the parameters use. Zeroes the slots of the stale window's
    /// positions if there is one, else whole tables that are dirty.
    fn ready_tables(&mut self) {
        let p = &self.params;
        if !self.stale_window.is_empty() {
            let window = &self.stale_window;
            match p.strategy {
                Strategy::Fast => self
                    .hash_table
                    .clear_slots(|t| fast::zero_position_slots(window, p.hash_log, p.min_match, t)),
                Strategy::DFast => {
                    self.hash_table.clear_slots(|t| {
                        dfast::zero_short_slots(window, p.chain_log, p.min_match, t)
                    });
                    self.hash_long
                        .clear_slots(|t| dfast::zero_long_slots(window, p.hash_log, t));
                }
            }
            self.stale_window.clear();
        }
        match p.strategy {
            Strategy::Fast => self.hash_table.clear(1usize << p.hash_log),
            Strategy::DFast => {
                self.hash_table.clear(1usize << p.chain_log);
                self.hash_long.clear(1usize << p.hash_log);
            }
        }
        self.tables_ready = true;
    }

    /// Largest block this frame uses: 128 KiB, or the window if smaller.
    pub(crate) fn block_size(&self) -> usize {
        MAX_BLOCK_SIZE.min(1usize << self.params.window_log)
    }

    /// Bytes waiting for the next block.
    pub(crate) fn buffered(&self) -> usize {
        self.window_buf.len() - self.block_start
    }

    pub(crate) fn dict(&self) -> Option<&Dictionary> {
        self.dict.as_ref()
    }

    /// Takes as much of `input` as fits in the current block and returns how
    /// much it took.
    pub(crate) fn take_input(&mut self, input: &[u8]) -> usize {
        let n = (self.block_size() - self.buffered()).min(input.len());
        let needed = self.window_buf.len() + n;
        if needed > self.window_buf.capacity() {
            // Double up to one block, so short frames stay small. Past that,
            // jump toward the most the window holds (two windows and a block)
            // in big steps: each doubling step copies the window and faults
            // in fresh pages.
            let window = 1usize << self.params.window_log;
            let dict_len = self.dict.as_ref().map_or(0, |d| d.content().len());
            let most = (2 * window).max(dict_len + window) + self.block_size();
            let first = dict_len + self.block_size();
            let target = if needed <= first {
                (2 * self.window_buf.capacity()).min(first)
            } else {
                (2 * self.window_buf.capacity()).max(GROW_STEP).min(most)
            }
            .max(needed);
            self.window_buf
                .reserve_exact(target - self.window_buf.len());
        }
        self.window_buf.extend_from_slice(&input[..n]);
        self.hasher.update(&input[..n]);
        n
    }

    pub(crate) fn write_header(&self, out: &mut Vec<u8>) -> Result<(), CompressError> {
        write_frame_header_without_content_size(
            out,
            self.dict.as_ref().map(Dictionary::id),
            self.params.window_log,
        )
    }

    /// Appends the content checksum that ends the frame.
    pub(crate) fn write_checksum(&self, out: &mut Vec<u8>) {
        let checksum = (self.hasher.finish() & 0xFFFF_FFFF) as u32;
        out.extend_from_slice(&checksum.to_le_bytes());
    }

    /// Encodes the buffered input as one block and appends it to `out`.
    ///
    /// With nothing buffered, writes an empty last block if `last`, and
    /// nothing otherwise.
    pub(crate) fn encode_block(
        &mut self,
        last: bool,
        out: &mut Vec<u8>,
    ) -> Result<(), CompressError> {
        if self.buffered() == 0 {
            if last {
                block_encoder::encode_raw_block(&[], true, out)?;
            }
            return Ok(());
        }

        let seed_dict = self.first_block && self.dict.is_some();
        let plen = self.block_start;
        out.reserve(self.buffered() + 32);
        let raw = {
            let chunk = &self.window_buf[plen..];
            crate::skip_match_search(&self.params, chunk.len(), chunk)
        };
        if !raw && !self.tables_ready {
            self.ready_tables();
        }
        let chunk = &self.window_buf[plen..];

        if raw {
            block_encoder::encode_raw_block(chunk, last, out)?;
        } else {
            if seed_dict {
                match self.params.strategy {
                    Strategy::Fast => {
                        fast::prefill_hash_table(
                            &self.window_buf,
                            plen,
                            self.params.hash_log,
                            self.params.min_match,
                            &mut self.hash_table,
                        );
                    }
                    Strategy::DFast => {
                        dfast::prefill_hash_tables(
                            &self.window_buf,
                            plen,
                            self.params.hash_log,
                            self.params.chain_log,
                            self.params.min_match,
                            &mut self.hash_table,
                            &mut self.hash_long,
                        );
                    }
                }
            }

            #[cfg(feature = "ldm")]
            let used_ldm = if let Some(ref mut ldm) = self.ldm_state {
                ldm.compress_block(
                    &self.window_buf,
                    plen,
                    self.window_buf.len(),
                    1usize << self.params.window_log,
                    &self.params,
                    &self.rep_offsets,
                    &mut self.hash_table,
                    &mut self.hash_long,
                    &mut self.sequences,
                );
                true
            } else {
                false
            };
            #[cfg(not(feature = "ldm"))]
            let used_ldm = false;

            if !used_ldm {
                match self.params.strategy {
                    Strategy::Fast => {
                        fast::compress_fast_block(
                            &self.window_buf,
                            plen,
                            self.window_buf.len(),
                            &self.params,
                            &self.rep_offsets,
                            &mut self.hash_table,
                            &mut self.sequences,
                        );
                    }
                    Strategy::DFast => {
                        dfast::compress_dfast_block(
                            &self.window_buf,
                            plen,
                            self.window_buf.len(),
                            &self.params,
                            &self.rep_offsets,
                            &mut self.hash_table,
                            &mut self.hash_long,
                            &mut self.sequences,
                        );
                    }
                }
            }

            if self.params.force_raw_literals {
                block_encoder::encode_compressed_block_raw(
                    chunk,
                    &self.sequences,
                    &mut self.rep_offsets,
                    last,
                    out,
                    &mut self.workspace,
                )?;
            } else {
                block_encoder::encode_compressed_block(
                    chunk,
                    &self.sequences,
                    &mut self.rep_offsets,
                    last,
                    out,
                    &mut self.workspace,
                    strategy::block_policy(&self.params, chunk.len()),
                )?;
            }
        }

        let window_size = 1usize << self.params.window_log;
        if self.window_buf.len() > window_size * 2 {
            let shift = self.window_buf.len() - window_size;
            reduce_hash_table(&mut self.hash_table, shift as u32);
            if !self.hash_long.is_empty() {
                reduce_hash_table(&mut self.hash_long, shift as u32);
            }
            #[cfg(feature = "ldm")]
            if let Some(ref mut ldm) = self.ldm_state {
                ldm.reduce_positions(shift as u32);
            }
            self.window_buf.copy_within(shift.., 0);
            self.window_buf.truncate(window_size);
        }

        self.block_start = self.window_buf.len();
        self.first_block = false;
        Ok(())
    }
}