preflate_rs/estimator/
preflate_parameter_estimator.rs

1/*---------------------------------------------------------------------------------------------
2 *  Copyright (c) Microsoft Corporation. All rights reserved.
3 *  Licensed under the Apache License, Version 2.0. See LICENSE.txt in the project root for license information.
4 *  This software incorporates material from third parties. See NOTICE.txt for details.
5 *--------------------------------------------------------------------------------------------*/
6
7use bitcode::{Decode, Encode};
8
9use crate::{
10    bit_helper::bit_length,
11    deflate::{deflate_constants, deflate_reader::DeflateContents},
12    estimator::{add_policy_estimator::DictionaryAddPolicy, preflate_parse_config::MatchingType},
13    hash_algorithm::HashAlgorithm,
14    preflate_error::Result,
15    preflate_input::PlainText,
16};
17
18use super::{
19    add_policy_estimator::estimate_add_policy,
20    complevel_estimator::estimate_preflate_comp_level,
21    preflate_stream_info::{PreflateStreamInfo, extract_preflate_info},
22};
23
24#[derive(Encode, Decode, Debug, Copy, Clone, Eq, PartialEq)]
25pub struct TokenPredictorParameters {
26    /// Zlib does not match to first byte of a file in order to reserve 0 for the end of chain
27    pub matches_to_start_detected: bool,
28
29    /// if there are matches that have a distance larger than window_size - MAX_MATCH.
30    /// Zlib does not allow these.
31    pub very_far_matches_detected: bool,
32    pub window_bits: u32,
33
34    pub strategy: PreflateStrategy,
35    pub nice_length: u32,
36
37    /// if something, then we use the "fast" compressor, which only adds smaller substrings
38    /// to the dictionary
39    pub add_policy: DictionaryAddPolicy,
40
41    pub max_token_count: u16,
42
43    pub zlib_compatible: bool,
44    pub max_dist_3_matches: u32,
45    pub matching_type: MatchingType,
46    pub max_chain: u32,
47    pub min_len: u32,
48
49    pub hash_algorithm: HashAlgorithm,
50
51    pub block_type_strategy: BlockTypeStrategy,
52}
53
54#[derive(Encode, Decode, Debug, Copy, Clone, Eq, PartialEq)]
55#[repr(u8)]
56pub enum BlockTypeStrategy {
57    Dynamic,
58    Mixed,
59    Static,
60    Uncompressed,
61}
62
63/// From the plain text and the preflate blocks, estimate the preflate parameters
64pub fn estimate_preflate_parameters(
65    deflate_contents: &DeflateContents,
66    plain_text: &PlainText,
67) -> Result<TokenPredictorParameters> {
68    let info = extract_preflate_info(&deflate_contents.blocks);
69
70    let preflate_strategy = estimate_preflate_strategy(&info);
71    let huff_strategy = estimate_preflate_huff_strategy(&info);
72
73    if preflate_strategy == PreflateStrategy::Store
74        || preflate_strategy == PreflateStrategy::HuffOnly
75    {
76        // No dictionary used
77        return Ok(TokenPredictorParameters {
78            window_bits: 0,
79            very_far_matches_detected: false,
80            matches_to_start_detected: false,
81            strategy: preflate_strategy,
82            nice_length: 0,
83            add_policy: DictionaryAddPolicy::AddAll,
84            max_token_count: 16386,
85            zlib_compatible: true,
86            max_dist_3_matches: 0,
87            matching_type: MatchingType::Greedy,
88            max_chain: 0,
89            min_len: 0,
90            hash_algorithm: HashAlgorithm::None,
91            block_type_strategy: huff_strategy,
92        });
93    }
94
95    let window_bits = estimate_preflate_window_bits(info.max_dist);
96    let mem_level = estimate_preflate_mem_level(info.max_tokens_per_block);
97    let add_policy = estimate_add_policy(&deflate_contents.blocks);
98
99    //let hash_shift = 5;
100    //let hash_mask = 32767;
101
102    let max_token_count = (1 << (6 + mem_level)) - 1;
103
104    let cl = estimate_preflate_comp_level(
105        window_bits,
106        mem_level,
107        info.min_len,
108        deflate_contents,
109        plain_text,
110        add_policy,
111    )?;
112
113    let zlib_compatible = !info.matches_to_start_detected
114        && !cl.very_far_matches_detected
115        && (info.max_dist_3_matches < 4096 || add_policy != DictionaryAddPolicy::AddAll);
116
117    Ok(TokenPredictorParameters {
118        window_bits,
119        very_far_matches_detected: cl.very_far_matches_detected,
120        matches_to_start_detected: info.matches_to_start_detected,
121        strategy: estimate_preflate_strategy(&info),
122        nice_length: cl.nice_length,
123        add_policy: add_policy,
124        max_token_count,
125        zlib_compatible,
126        max_dist_3_matches: info.max_dist_3_matches,
127        matching_type: cl.match_type,
128        max_chain: cl.max_chain,
129        min_len: info.min_len,
130        hash_algorithm: cl.hash_algorithm,
131        block_type_strategy: estimate_preflate_huff_strategy(&info),
132    })
133}
134
135#[derive(Encode, Decode, Debug, Copy, Clone, Eq, PartialEq)]
136#[repr(u8)]
137pub enum PreflateStrategy {
138    Default,
139    RleOnly,
140    HuffOnly,
141    Store,
142}
143
144fn estimate_preflate_mem_level(max_block_size_: u32) -> u32 {
145    let mut max_block_size = max_block_size_;
146    let mut mbits = 0;
147    while max_block_size > 0 {
148        mbits += 1;
149        max_block_size >>= 1;
150    }
151    mbits = std::cmp::min(std::cmp::max(mbits, 7), 15);
152    mbits - 6
153}
154
155fn estimate_preflate_window_bits(max_dist_: u32) -> u32 {
156    let mut max_dist = max_dist_;
157    max_dist += deflate_constants::MIN_LOOKAHEAD;
158    let wbits = bit_length(max_dist - 1);
159    std::cmp::min(std::cmp::max(wbits, 9), 15)
160}
161
162fn estimate_preflate_strategy(info: &PreflateStreamInfo) -> PreflateStrategy {
163    if info.count_stored_blocks == info.count_blocks {
164        return PreflateStrategy::Store;
165    }
166    if info.count_huff_blocks == info.count_blocks {
167        return PreflateStrategy::HuffOnly;
168    }
169    if info.count_rle_blocks == info.count_blocks {
170        return PreflateStrategy::RleOnly;
171    }
172    PreflateStrategy::Default
173}
174
175fn estimate_preflate_huff_strategy(info: &PreflateStreamInfo) -> BlockTypeStrategy {
176    if info.count_static_huff_tree_blocks == info.count_blocks {
177        return BlockTypeStrategy::Static;
178    }
179    if info.count_stored_blocks == info.count_blocks {
180        return BlockTypeStrategy::Uncompressed;
181    }
182    if info.count_static_huff_tree_blocks == 0 {
183        return BlockTypeStrategy::Dynamic;
184    }
185    BlockTypeStrategy::Mixed
186}
187
188#[test]
189fn verify_zlib_recognition() {
190    use crate::{
191        deflate::deflate_reader::parse_deflate_whole,
192        estimator::preflate_parse_config::{
193            SLOW_PREFLATE_PARSER_SETTINGS, ZLIB_PREFLATE_PARSER_SETTINGS,
194        },
195        utils::read_file,
196    };
197
198    for i in 0..=9 {
199        let v = read_file(&format!("compressed_zlib_level{}.deflate", i));
200        let (contents, plain_text) = parse_deflate_whole(&v).unwrap();
201
202        let params = estimate_preflate_parameters(&contents, &plain_text).unwrap();
203
204        assert_eq!(params.zlib_compatible, true);
205        if i == 0 {
206            assert_eq!(params.strategy, PreflateStrategy::Store);
207        } else if i >= 1 && i < 4 {
208            let config = &ZLIB_PREFLATE_PARSER_SETTINGS[i as usize - 1];
209            assert!(
210                params.max_chain <= config.max_chain,
211                "max_chain mismatch {} should be <= {}",
212                params.max_chain,
213                config.max_chain
214            );
215            assert_eq!(params.matching_type, config.match_type);
216            assert_eq!(params.add_policy, config.dictionary_add_policy);
217            assert_eq!(params.nice_length, config.nice_length);
218            assert_eq!(params.strategy, PreflateStrategy::Default);
219        } else if i >= 4 {
220            let config = &SLOW_PREFLATE_PARSER_SETTINGS[i as usize - 4];
221            assert!(
222                params.max_chain <= config.max_chain,
223                "max_chain mismatch {} should be <= {}",
224                params.max_chain,
225                config.max_chain
226            );
227            assert_eq!(params.matching_type, config.match_type);
228            assert_eq!(params.add_policy, config.dictionary_add_policy);
229            assert_eq!(params.nice_length, config.nice_length);
230            assert_eq!(params.strategy, PreflateStrategy::Default);
231        }
232    }
233}
234
235#[test]
236fn verify_miniz_recognition() {
237    use crate::deflate::deflate_reader::parse_deflate_whole;
238    use crate::utils::read_file;
239
240    for i in 0..=9 {
241        let v = read_file(&format!("compressed_flate2_level{}.deflate", i));
242        let (contents, plain_text) = parse_deflate_whole(&v).unwrap();
243
244        let params = estimate_preflate_parameters(&contents, &plain_text).unwrap();
245
246        if i == 0 {
247            assert_eq!(params.strategy, PreflateStrategy::Store);
248        } else if i == 1 {
249            println!("{:?}", params);
250        } else {
251            println!("{:?}", params);
252        }
253    }
254}
255
256#[test]
257fn verify_zlibng_recognition() {
258    use crate::deflate::deflate_reader::parse_deflate_whole;
259    use crate::utils::read_file;
260
261    for i in 1..=2 {
262        let v = read_file(&format!("compressed_zlibng_level{}.deflate", i));
263        let (contents, plain_text) = parse_deflate_whole(&v).unwrap();
264
265        let params = estimate_preflate_parameters(&contents, &plain_text).unwrap();
266
267        if i == 0 {
268            assert_eq!(params.strategy, PreflateStrategy::Store);
269        } else if i == 1 {
270            println!("{:?}", params);
271        } else {
272            println!("{:?}", params);
273        }
274    }
275}
preflate_rs/estimator/preflate_parameter_estimator.rs

preflate_rs/estimator/
preflate_parameter_estimator.rs
