brotli/enc/
metablock.rs

Help
1use core;
2use core::cmp::{max, min};
3
4use super::super::alloc;
5use super::super::alloc::{Allocator, SliceWrapper, SliceWrapperMut};
6use super::backward_references::BrotliEncoderParams;
7use super::bit_cost::{BitsEntropy, BrotliPopulationCost};
8use super::block_split::BlockSplit;
9use super::block_splitter::BrotliSplitBlock;
10use super::brotli_bit_stream::MetaBlockSplit;
11use super::cluster::BrotliClusterHistograms;
12use super::combined_alloc::BrotliAlloc;
13use super::command::{BrotliDistanceParams, Command, PrefixEncodeCopyDistance};
14use super::constants::BROTLI_MAX_NPOSTFIX;
15use super::encode::{
16    BROTLI_DISTANCE_ALPHABET_SIZE, BROTLI_LARGE_MAX_DISTANCE_BITS, BROTLI_MAX_ALLOWED_DISTANCE,
17    BROTLI_MAX_DISTANCE_BITS,
18};
19use super::entropy_encode::BrotliOptimizeHuffmanCountsForRle;
20use super::histogram::{
21    BrotliBuildHistogramsWithContext, ClearHistograms, Context, ContextType, CostAccessors,
22    HistogramAddHistogram, HistogramAddItem, HistogramClear, HistogramCommand, HistogramDistance,
23    HistogramLiteral,
24};
25use crate::enc::combined_alloc::{alloc_default, allocate};
26use crate::enc::floatX;
27
28pub fn BrotliInitDistanceParams(params: &mut BrotliEncoderParams, npostfix: u32, ndirect: u32) {
29    let dist_params = &mut params.dist;
30    let mut alphabet_size;
31    let mut max_distance;
32
33    dist_params.distance_postfix_bits = npostfix;
34    dist_params.num_direct_distance_codes = ndirect;
35
36    alphabet_size = BROTLI_DISTANCE_ALPHABET_SIZE(npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS);
37    max_distance =
38        ndirect + (1u32 << (BROTLI_MAX_DISTANCE_BITS + npostfix + 2)) - (1u32 << (npostfix + 2));
39
40    if (params.large_window) {
41        let bound: [u32; BROTLI_MAX_NPOSTFIX + 1] = [0, 4, 12, 28];
42        let postfix = 1u32 << npostfix;
43        alphabet_size =
44            BROTLI_DISTANCE_ALPHABET_SIZE(npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS);
45        /* The maximum distance is set so that no distance symbol used can encode
46        a distance larger than BROTLI_MAX_ALLOWED_DISTANCE with all
47        its extra bits set. */
48        if (ndirect < bound[npostfix as usize]) {
49            max_distance =
50                BROTLI_MAX_ALLOWED_DISTANCE as u32 - (bound[npostfix as usize] - ndirect);
51        } else if (ndirect >= bound[npostfix as usize] + postfix) {
52            max_distance = (3u32 << 29) - 4 + (ndirect - bound[npostfix as usize]);
53        } else {
54            max_distance = BROTLI_MAX_ALLOWED_DISTANCE as u32;
55        }
56    }
57
58    dist_params.alphabet_size = alphabet_size;
59    dist_params.max_distance = max_distance as usize;
60}
61
62fn RecomputeDistancePrefixes(
63    cmds: &mut [Command],
64    num_commands: usize,
65    orig_params: &BrotliDistanceParams,
66    new_params: &BrotliDistanceParams,
67) {
68    if orig_params.distance_postfix_bits == new_params.distance_postfix_bits
69        && orig_params.num_direct_distance_codes == new_params.num_direct_distance_codes
70    {
71        return;
72    }
73
74    for cmd in cmds.split_at_mut(num_commands).0.iter_mut() {
75        if (cmd.copy_len() != 0 && cmd.cmd_prefix_ >= 128) {
76            let ret = cmd.restore_distance_code(orig_params);
77            PrefixEncodeCopyDistance(
78                ret as usize,
79                new_params.num_direct_distance_codes as usize,
80                new_params.distance_postfix_bits as u64,
81                &mut cmd.dist_prefix_,
82                &mut cmd.dist_extra_,
83            );
84        }
85    }
86}
87
88fn ComputeDistanceCost(
89    cmds: &[Command],
90    num_commands: usize,
91    orig_params: &BrotliDistanceParams,
92    new_params: &BrotliDistanceParams,
93    scratch: &mut <HistogramDistance as CostAccessors>::i32vec,
94    cost: &mut f64,
95) -> bool {
96    let mut equal_params = false;
97    let mut dist_prefix: u16 = 0;
98    let mut dist_extra: u32 = 0;
99    let mut extra_bits: f64 = 0.0;
100    let mut histo = HistogramDistance::default();
101
102    if (orig_params.distance_postfix_bits == new_params.distance_postfix_bits
103        && orig_params.num_direct_distance_codes == new_params.num_direct_distance_codes)
104    {
105        equal_params = true;
106    }
107    for cmd in cmds.split_at(num_commands).0 {
108        if cmd.copy_len() != 0 && cmd.cmd_prefix_ >= 128 {
109            if equal_params {
110                dist_prefix = cmd.dist_prefix_;
111            } else {
112                let distance = cmd.restore_distance_code(orig_params);
113                if distance > new_params.max_distance as u32 {
114                    return false;
115                }
116                PrefixEncodeCopyDistance(
117                    distance as usize,
118                    new_params.num_direct_distance_codes as usize,
119                    new_params.distance_postfix_bits as u64,
120                    &mut dist_prefix,
121                    &mut dist_extra,
122                );
123            }
124            HistogramAddItem(&mut histo, (dist_prefix & 0x03ff) as usize);
125            extra_bits += (dist_prefix >> 10) as f64;
126        }
127    }
128
129    *cost = BrotliPopulationCost(&histo, scratch) as f64 + extra_bits;
130    true
131}
132
133pub fn BrotliBuildMetaBlock<Alloc: BrotliAlloc>(
134    alloc: &mut Alloc,
135    ringbuffer: &[u8],
136    pos: usize,
137    mask: usize,
138    params: &mut BrotliEncoderParams,
139    prev_byte: u8,
140    prev_byte2: u8,
141    cmds: &mut [Command],
142    num_commands: usize,
143    literal_context_mode: ContextType,
144    lit_scratch_space: &mut <HistogramLiteral as CostAccessors>::i32vec,
145    cmd_scratch_space: &mut <HistogramCommand as CostAccessors>::i32vec,
146    dst_scratch_space: &mut <HistogramDistance as CostAccessors>::i32vec,
147    mb: &mut MetaBlockSplit<Alloc>,
148) {
149    static kMaxNumberOfHistograms: usize = 256usize;
150    let mut distance_histograms: <Alloc as Allocator<HistogramDistance>>::AllocatedMemory;
151    let mut literal_histograms: <Alloc as Allocator<HistogramLiteral>>::AllocatedMemory;
152    let mut literal_context_modes = alloc_default::<ContextType, Alloc>();
153
154    let mut i: usize;
155    let mut literal_context_multiplier: usize = 1;
156    let mut ndirect_msb: u32 = 0;
157    let mut check_orig = true;
158    if !params.avoid_distance_prefix_search {
159        let mut best_dist_cost: f64 = 1e99;
160        let orig_params = params.clone();
161        let mut new_params = params.clone();
162
163        for npostfix in 0..(BROTLI_MAX_NPOSTFIX + 1) {
164            while ndirect_msb < 16 {
165                let ndirect = ndirect_msb << npostfix;
166
167                let mut dist_cost: f64 = 0.0;
168                BrotliInitDistanceParams(&mut new_params, npostfix as u32, ndirect);
169                if npostfix as u32 == orig_params.dist.distance_postfix_bits
170                    && ndirect == orig_params.dist.num_direct_distance_codes
171                {
172                    check_orig = false;
173                }
174                let skip: bool = !ComputeDistanceCost(
175                    cmds,
176                    num_commands,
177                    &orig_params.dist,
178                    &new_params.dist,
179                    dst_scratch_space,
180                    &mut dist_cost,
181                );
182                if skip || (dist_cost > best_dist_cost) {
183                    break;
184                }
185                best_dist_cost = dist_cost;
186                params.dist = new_params.dist;
187                ndirect_msb += 1;
188            }
189            ndirect_msb = ndirect_msb.saturating_sub(1);
190            ndirect_msb /= 2;
191        }
192        if check_orig {
193            let mut dist_cost: f64 = 0.0;
194            ComputeDistanceCost(
195                cmds,
196                num_commands,
197                &orig_params.dist,
198                &orig_params.dist,
199                dst_scratch_space,
200                &mut dist_cost,
201            );
202            if dist_cost < best_dist_cost {
203                // best_dist_cost = dist_cost; unused
204                params.dist = orig_params.dist;
205            }
206        }
207        RecomputeDistancePrefixes(cmds, num_commands, &orig_params.dist, &params.dist);
208    }
209    BrotliSplitBlock(
210        alloc,
211        cmds,
212        num_commands,
213        ringbuffer,
214        pos,
215        mask,
216        params,
217        lit_scratch_space,
218        cmd_scratch_space,
219        dst_scratch_space,
220        &mut mb.literal_split,
221        &mut mb.command_split,
222        &mut mb.distance_split,
223    );
224    if params.disable_literal_context_modeling == 0 {
225        literal_context_multiplier = (1i32 << 6) as usize;
226        literal_context_modes = allocate::<ContextType, _>(alloc, mb.literal_split.num_types);
227        for item in literal_context_modes.slice_mut().iter_mut() {
228            *item = literal_context_mode;
229        }
230    }
231    let literal_histograms_size: usize = mb
232        .literal_split
233        .num_types
234        .wrapping_mul(literal_context_multiplier);
235    literal_histograms = allocate::<HistogramLiteral, _>(alloc, literal_histograms_size);
236    let distance_histograms_size: usize = mb.distance_split.num_types << 2;
237    distance_histograms = allocate::<HistogramDistance, _>(alloc, distance_histograms_size);
238    mb.command_histograms_size = mb.command_split.num_types;
239    mb.command_histograms = allocate::<HistogramCommand, _>(alloc, mb.command_histograms_size);
240    BrotliBuildHistogramsWithContext(
241        cmds,
242        num_commands,
243        &mut mb.literal_split,
244        &mut mb.command_split,
245        &mut mb.distance_split,
246        ringbuffer,
247        pos,
248        mask,
249        prev_byte,
250        prev_byte2,
251        literal_context_modes.slice(),
252        literal_histograms.slice_mut(),
253        mb.command_histograms.slice_mut(),
254        distance_histograms.slice_mut(),
255    );
256    <Alloc as Allocator<ContextType>>::free_cell(alloc, literal_context_modes);
257    mb.literal_context_map_size = mb.literal_split.num_types << 6;
258    mb.literal_context_map = allocate::<u32, _>(alloc, mb.literal_context_map_size);
259    mb.literal_histograms_size = mb.literal_context_map_size;
260    mb.literal_histograms = allocate::<HistogramLiteral, _>(alloc, mb.literal_histograms_size);
261    BrotliClusterHistograms(
262        alloc,
263        literal_histograms.slice(),
264        literal_histograms_size,
265        kMaxNumberOfHistograms,
266        lit_scratch_space,
267        mb.literal_histograms.slice_mut(),
268        &mut mb.literal_histograms_size,
269        mb.literal_context_map.slice_mut(),
270    );
271    <Alloc as Allocator<HistogramLiteral>>::free_cell(alloc, literal_histograms);
272    if params.disable_literal_context_modeling != 0 {
273        i = mb.literal_split.num_types;
274        while i != 0usize {
275            let mut j: usize = 0usize;
276            i = i.wrapping_sub(1);
277            while j < (1i32 << 6) as usize {
278                {
279                    let val = mb.literal_context_map.slice()[i];
280                    mb.literal_context_map.slice_mut()[(i << 6).wrapping_add(j)] = val;
281                }
282                j = j.wrapping_add(1);
283            }
284        }
285    }
286    mb.distance_context_map_size = mb.distance_split.num_types << 2;
287    mb.distance_context_map = allocate::<u32, _>(alloc, mb.distance_context_map_size);
288    mb.distance_histograms_size = mb.distance_context_map_size;
289    mb.distance_histograms = allocate::<HistogramDistance, _>(alloc, mb.distance_histograms_size);
290    BrotliClusterHistograms(
291        alloc,
292        distance_histograms.slice(),
293        mb.distance_context_map_size,
294        kMaxNumberOfHistograms,
295        dst_scratch_space,
296        mb.distance_histograms.slice_mut(),
297        &mut mb.distance_histograms_size,
298        mb.distance_context_map.slice_mut(),
299    );
300    <Alloc as Allocator<HistogramDistance>>::free_cell(alloc, distance_histograms);
301}
302
303/*
304pub struct BlockSplitter<'a, HistogramType:SliceWrapper<u32>+SliceWrapperMut<u32> +CostAccessors,
305                         AllocU8:alloc::Allocator<u8>+'a,
306                         AllocU32:alloc::Allocator<u32>+'a,
307                         AllocHT:alloc::Allocator<HistogramType>+'a > {
308                         */
309pub struct BlockSplitter {
310    pub alphabet_size_: usize,
311    pub min_block_size_: usize,
312    pub split_threshold_: floatX,
313    pub num_blocks_: usize,
314    //  pub split_: &'a mut BlockSplit<AllocU8, AllocU32>,
315    //  pub histograms_: AllocHT::AllocatedMemory, // FIXME: pull this one out at the end
316    //  pub histograms_size_: &'a mut usize, // FIXME: pull this one out at the end
317    pub target_block_size_: usize,
318    pub block_size_: usize,
319    pub curr_histogram_ix_: usize,
320    pub last_histogram_ix_: [usize; 2],
321    pub last_entropy_: [floatX; 2],
322    pub merge_last_count_: usize,
323}
324
325pub struct ContextBlockSplitter {
326    pub alphabet_size_: usize,
327    pub num_contexts_: usize,
328    pub max_block_types_: usize,
329    pub min_block_size_: usize,
330    pub split_threshold_: floatX,
331    pub num_blocks_: usize,
332    //  pub split_: &'a mut BlockSplit<AllocU8, AllocU32>,
333    //  pub histograms_: AllocHL::AllocatedMemory,
334    //  pub histograms_size_: &'a mut usize, // FIXME: pull this one out at the end
335    pub target_block_size_: usize,
336    pub block_size_: usize,
337    pub curr_histogram_ix_: usize,
338    pub last_histogram_ix_: [usize; 2],
339    pub last_entropy_: [floatX; 2 * BROTLI_MAX_STATIC_CONTEXTS],
340    pub merge_last_count_: usize,
341}
342
343enum LitBlocks {
344    plain(BlockSplitter),      //<'a, HistogramLiteral, AllocU8, AllocU32, AllocHL>,
345    ctx(ContextBlockSplitter), //<'a, AllocU8, AllocU32, AllocHL>,
346}
347
348/*
349
350pub struct BlockSplitterCommand {
351  pub alphabet_size_: usize,
352  pub min_block_size_: usize,
353  pub split_threshold_: floatX,
354  pub num_blocks_: usize,
355  pub split_: *mut BlockSplit,
356  pub histograms_: *mut HistogramCommand,
357  pub histograms_size_: *mut usize,
358  pub target_block_size_: usize,
359  pub block_size_: usize,
360  pub curr_histogram_ix_: usize,
361  pub last_histogram_ix_: [usize; 2],
362  pub last_entropy_: [floatX; 2],
363  pub merge_last_count_: usize,
364}
365
366
367
368pub struct BlockSplitterDistance {
369  pub alphabet_size_: usize,
370  pub min_block_size_: usize,
371  pub split_threshold_: floatX,
372  pub num_blocks_: usize,
373  pub split_: *mut BlockSplit,
374  pub histograms_: *mut HistogramDistance,
375  pub histograms_size_: *mut usize,
376  pub target_block_size_: usize,
377  pub block_size_: usize,
378  pub curr_histogram_ix_: usize,
379  pub last_histogram_ix_: [usize; 2],
380  pub last_entropy_: [floatX; 2],
381  pub merge_last_count_: usize,
382}
383*/
384
385fn InitBlockSplitter<
386    HistogramType: SliceWrapper<u32> + SliceWrapperMut<u32> + CostAccessors,
387    Alloc: alloc::Allocator<u8> + alloc::Allocator<u32> + alloc::Allocator<HistogramType>,
388>(
389    alloc: &mut Alloc,
390    alphabet_size: usize,
391    min_block_size: usize,
392    split_threshold: floatX,
393    num_symbols: usize,
394    split: &mut BlockSplit<Alloc>,
395    histograms: &mut <Alloc as Allocator<HistogramType>>::AllocatedMemory,
396    histograms_size: &mut usize,
397) -> BlockSplitter {
398    let max_num_blocks: usize = num_symbols.wrapping_div(min_block_size).wrapping_add(1);
399    let max_num_types: usize = min(max_num_blocks, (256i32 + 1i32) as usize);
400    let mut xself = BlockSplitter {
401        last_entropy_: [0.0; 2],
402        alphabet_size_: alphabet_size,
403        min_block_size_: min_block_size,
404        split_threshold_: split_threshold,
405        num_blocks_: 0usize,
406        //xself.split_ : split,
407        //xself.histograms_size_ : histograms_size,
408        target_block_size_: min_block_size,
409        block_size_: 0usize,
410        curr_histogram_ix_: 0usize,
411        merge_last_count_: 0usize,
412        last_histogram_ix_: [0; 2],
413    };
414    {
415        if split.types.slice().len() < max_num_blocks {
416            let mut _new_size: usize = if split.types.slice().is_empty() {
417                max_num_blocks
418            } else {
419                split.types.slice().len()
420            };
421            let mut new_array: <Alloc as Allocator<u8>>::AllocatedMemory;
422            while _new_size < max_num_blocks {
423                _new_size = _new_size.wrapping_mul(2);
424            }
425            new_array = allocate::<u8, _>(alloc, _new_size);
426            if (!split.types.slice().is_empty()) {
427                new_array.slice_mut()[..split.types.slice().len()]
428                    .clone_from_slice(split.types.slice());
429            }
430            <Alloc as Allocator<u8>>::free_cell(
431                alloc,
432                core::mem::replace(&mut split.types, new_array),
433            );
434        }
435    }
436    {
437        if split.lengths.slice().len() < max_num_blocks {
438            let mut _new_size: usize = if split.lengths.slice().is_empty() {
439                max_num_blocks
440            } else {
441                split.lengths.slice().len()
442            };
443            while _new_size < max_num_blocks {
444                _new_size = _new_size.wrapping_mul(2);
445            }
446            let mut new_array = allocate::<u32, _>(alloc, _new_size);
447            new_array.slice_mut()[..split.lengths.slice().len()]
448                .clone_from_slice(split.lengths.slice());
449            <Alloc as Allocator<u32>>::free_cell(
450                alloc,
451                core::mem::replace(&mut split.lengths, new_array),
452            );
453        }
454    }
455    split.num_blocks = max_num_blocks;
456    *histograms_size = max_num_types;
457    let hlocal = allocate::<HistogramType, _>(alloc, *histograms_size);
458    <Alloc as Allocator<HistogramType>>::free_cell(
459        alloc,
460        core::mem::replace(&mut *histograms, hlocal),
461    );
462    HistogramClear(&mut histograms.slice_mut()[0]);
463    xself.last_histogram_ix_[0] = 0;
464    xself.last_histogram_ix_[1] = 0;
465    xself
466}
467fn InitContextBlockSplitter<
468    Alloc: alloc::Allocator<u8> + alloc::Allocator<u32> + alloc::Allocator<HistogramLiteral>,
469>(
470    alloc: &mut Alloc,
471    alphabet_size: usize,
472    num_contexts: usize,
473    min_block_size: usize,
474    split_threshold: floatX,
475    num_symbols: usize,
476    split: &mut BlockSplit<Alloc>,
477    histograms: &mut <Alloc as Allocator<HistogramLiteral>>::AllocatedMemory,
478    histograms_size: &mut usize,
479) -> ContextBlockSplitter {
480    let max_num_blocks: usize = num_symbols.wrapping_div(min_block_size).wrapping_add(1);
481
482    assert!(num_contexts <= BROTLI_MAX_STATIC_CONTEXTS);
483    let mut xself = ContextBlockSplitter {
484        alphabet_size_: alphabet_size,
485        num_contexts_: num_contexts,
486        max_block_types_: (256usize).wrapping_div(num_contexts),
487        min_block_size_: min_block_size,
488        split_threshold_: split_threshold,
489        num_blocks_: 0usize,
490        //        histograms_size_: histograms_size,
491        target_block_size_: min_block_size,
492        block_size_: 0usize,
493        curr_histogram_ix_: 0usize,
494        merge_last_count_: 0usize,
495        last_histogram_ix_: [0; 2],
496        last_entropy_: [0.0; 2 * BROTLI_MAX_STATIC_CONTEXTS],
497    };
498    let max_num_types: usize = min(max_num_blocks, xself.max_block_types_.wrapping_add(1));
499    {
500        if split.types.slice().len() < max_num_blocks {
501            let mut _new_size: usize = if split.types.slice().is_empty() {
502                max_num_blocks
503            } else {
504                split.types.slice().len()
505            };
506            while _new_size < max_num_blocks {
507                _new_size = _new_size.wrapping_mul(2);
508            }
509            let mut new_array = allocate::<u8, _>(alloc, _new_size);
510            if (!split.types.slice().is_empty()) {
511                new_array.slice_mut()[..split.types.slice().len()]
512                    .clone_from_slice(split.types.slice());
513            }
514            <Alloc as Allocator<u8>>::free_cell(
515                alloc,
516                core::mem::replace(&mut split.types, new_array),
517            );
518        }
519    }
520    {
521        if split.lengths.slice().len() < max_num_blocks {
522            let mut _new_size: usize = if split.lengths.slice().is_empty() {
523                max_num_blocks
524            } else {
525                split.lengths.slice().len()
526            };
527            while _new_size < max_num_blocks {
528                _new_size = _new_size.wrapping_mul(2);
529            }
530            let mut new_array = allocate::<u32, _>(alloc, _new_size);
531            if (!split.lengths.slice().is_empty()) {
532                new_array.slice_mut()[..split.lengths.slice().len()]
533                    .clone_from_slice(split.lengths.slice());
534            }
535            <Alloc as Allocator<u32>>::free_cell(
536                alloc,
537                core::mem::replace(&mut split.lengths, new_array),
538            );
539        }
540    }
541    split.num_blocks = max_num_blocks;
542    *histograms_size = max_num_types.wrapping_mul(num_contexts);
543    *histograms = allocate::<HistogramLiteral, _>(alloc, *histograms_size);
544    //xself.histograms_ = *histograms;
545    ClearHistograms(&mut histograms.slice_mut()[0..], num_contexts);
546    xself.last_histogram_ix_[0] = 0;
547    xself.last_histogram_ix_[1] = 0;
548    xself
549}
550
551fn BlockSplitterFinishBlock<
552    HistogramType: SliceWrapper<u32> + SliceWrapperMut<u32> + CostAccessors + Clone,
553    Alloc: alloc::Allocator<u8> + alloc::Allocator<u32>,
554>(
555    xself: &mut BlockSplitter,
556    split: &mut BlockSplit<Alloc>,
557    histograms: &mut [HistogramType],
558    histograms_size: &mut usize,
559    is_final: bool,
560) {
561    xself.block_size_ = max(xself.block_size_, xself.min_block_size_);
562    if xself.num_blocks_ == 0usize {
563        split.lengths.slice_mut()[0] = xself.block_size_ as u32;
564        split.types.slice_mut()[0] = 0u8;
565        xself.last_entropy_[0] = BitsEntropy((histograms[0]).slice(), xself.alphabet_size_);
566        xself.last_entropy_[1] = xself.last_entropy_[0];
567        xself.num_blocks_ = xself.num_blocks_.wrapping_add(1);
568        split.num_types = split.num_types.wrapping_add(1);
569        xself.curr_histogram_ix_ = xself.curr_histogram_ix_.wrapping_add(1);
570        if xself.curr_histogram_ix_ < *histograms_size {
571            HistogramClear(&mut histograms[xself.curr_histogram_ix_]);
572        }
573        xself.block_size_ = 0usize;
574    } else if xself.block_size_ > 0usize {
575        let entropy = BitsEntropy(
576            (histograms[xself.curr_histogram_ix_]).slice(),
577            xself.alphabet_size_,
578        );
579        let mut combined_histo: [HistogramType; 2] = [
580            histograms[xself.curr_histogram_ix_].clone(),
581            histograms[xself.curr_histogram_ix_].clone(),
582        ];
583
584        let mut combined_entropy: [floatX; 2] = [0.0, 0.0];
585        let mut diff: [floatX; 2] = [0.0, 0.0];
586        for j in 0..2 {
587            let last_histogram_ix: usize = xself.last_histogram_ix_[j];
588            HistogramAddHistogram(&mut combined_histo[j], &histograms[last_histogram_ix]);
589            combined_entropy[j] = BitsEntropy(
590                &mut combined_histo[j].slice_mut()[0..],
591                xself.alphabet_size_,
592            );
593            diff[j] = combined_entropy[j] - entropy - xself.last_entropy_[j];
594        }
595        if split.num_types < 256usize
596            && (diff[0] > xself.split_threshold_)
597            && (diff[1] > xself.split_threshold_)
598        {
599            split.lengths.slice_mut()[xself.num_blocks_] = xself.block_size_ as u32;
600            split.types.slice_mut()[xself.num_blocks_] = split.num_types as u8;
601            xself.last_histogram_ix_[1] = xself.last_histogram_ix_[0];
602            xself.last_histogram_ix_[0] = split.num_types as u8 as usize;
603            xself.last_entropy_[1] = xself.last_entropy_[0];
604            xself.last_entropy_[0] = entropy;
605            xself.num_blocks_ = xself.num_blocks_.wrapping_add(1);
606            split.num_types = split.num_types.wrapping_add(1);
607            xself.curr_histogram_ix_ = xself.curr_histogram_ix_.wrapping_add(1);
608            if xself.curr_histogram_ix_ < *histograms_size {
609                HistogramClear(&mut histograms[xself.curr_histogram_ix_]);
610            }
611            xself.block_size_ = 0usize;
612            xself.merge_last_count_ = 0usize;
613            xself.target_block_size_ = xself.min_block_size_;
614        } else if diff[1] < diff[0] - 20.0 {
615            split.lengths.slice_mut()[xself.num_blocks_] = xself.block_size_ as u32;
616            split.types.slice_mut()[xself.num_blocks_] =
617                split.types.slice()[xself.num_blocks_.wrapping_sub(2)]; //FIXME: investigate copy?
618            {
619                xself.last_histogram_ix_.swap(0, 1);
620            }
621            histograms[xself.last_histogram_ix_[0]] = combined_histo[1].clone();
622            xself.last_entropy_[1] = xself.last_entropy_[0];
623            xself.last_entropy_[0] = combined_entropy[1];
624            xself.num_blocks_ = xself.num_blocks_.wrapping_add(1);
625            xself.block_size_ = 0usize;
626            HistogramClear(&mut histograms[xself.curr_histogram_ix_]);
627            xself.merge_last_count_ = 0usize;
628            xself.target_block_size_ = xself.min_block_size_;
629        } else {
630            {
631                let _rhs = xself.block_size_ as u32;
632                let _lhs = &mut split.lengths.slice_mut()[xself.num_blocks_.wrapping_sub(1)];
633                *_lhs = (*_lhs).wrapping_add(_rhs);
634            }
635            histograms[xself.last_histogram_ix_[0]] = combined_histo[0].clone();
636            xself.last_entropy_[0] = combined_entropy[0];
637            if split.num_types == 1 {
638                xself.last_entropy_[1] = xself.last_entropy_[0];
639            }
640            xself.block_size_ = 0usize;
641            HistogramClear(&mut histograms[xself.curr_histogram_ix_]);
642            if {
643                xself.merge_last_count_ = xself.merge_last_count_.wrapping_add(1);
644                xself.merge_last_count_
645            } > 1
646            {
647                xself.target_block_size_ =
648                    xself.target_block_size_.wrapping_add(xself.min_block_size_);
649            }
650        }
651    }
652    if is_final {
653        *histograms_size = split.num_types;
654        split.num_blocks = xself.num_blocks_;
655    }
656}
657const BROTLI_MAX_STATIC_CONTEXTS: usize = 13;
658
659fn ContextBlockSplitterFinishBlock<
660    Alloc: alloc::Allocator<u8> + alloc::Allocator<u32> + alloc::Allocator<HistogramLiteral>,
661    AllocHL: alloc::Allocator<HistogramLiteral>,
662>(
663    xself: &mut ContextBlockSplitter,
664    m: &mut AllocHL,
665    split: &mut BlockSplit<Alloc>,
666    histograms: &mut [HistogramLiteral],
667    histograms_size: &mut usize,
668    is_final: bool,
669) {
670    let num_contexts: usize = xself.num_contexts_;
671    if xself.block_size_ < xself.min_block_size_ {
672        xself.block_size_ = xself.min_block_size_;
673    }
674    if xself.num_blocks_ == 0usize {
675        split.lengths.slice_mut()[0] = xself.block_size_ as u32;
676        split.types.slice_mut()[0] = 0u8;
677        for i in 0usize..num_contexts {
678            xself.last_entropy_[i] = BitsEntropy((histograms[i]).slice(), xself.alphabet_size_);
679            xself.last_entropy_[num_contexts.wrapping_add(i)] = xself.last_entropy_[i];
680        }
681        xself.num_blocks_ = xself.num_blocks_.wrapping_add(1);
682        split.num_types = split.num_types.wrapping_add(1);
683        xself.curr_histogram_ix_ = xself.curr_histogram_ix_.wrapping_add(num_contexts);
684        if xself.curr_histogram_ix_ < *histograms_size {
685            ClearHistograms(
686                &mut histograms[xself.curr_histogram_ix_..],
687                xself.num_contexts_,
688            );
689        }
690        xself.block_size_ = 0usize;
691    } else if xself.block_size_ > 0usize {
692        let mut entropy = [0.0; BROTLI_MAX_STATIC_CONTEXTS];
693        let mut combined_histo = m.alloc_cell(2 * num_contexts);
694        let mut combined_entropy = [0.0; 2 * BROTLI_MAX_STATIC_CONTEXTS];
695        let mut diff = [0.0; 2];
696        for i in 0usize..num_contexts {
697            let curr_histo_ix: usize = xself.curr_histogram_ix_.wrapping_add(i);
698            let mut j: usize;
699            entropy[i] = BitsEntropy((histograms[curr_histo_ix]).slice(), xself.alphabet_size_);
700            j = 0usize;
701            while j < 2usize {
702                {
703                    let jx: usize = j.wrapping_mul(num_contexts).wrapping_add(i);
704                    let last_histogram_ix: usize = xself.last_histogram_ix_[j].wrapping_add(i);
705                    combined_histo.slice_mut()[jx] = histograms[curr_histo_ix].clone();
706                    HistogramAddHistogram(
707                        &mut combined_histo.slice_mut()[jx],
708                        &mut histograms[last_histogram_ix],
709                    );
710                    combined_entropy[jx] =
711                        BitsEntropy(combined_histo.slice()[jx].slice(), xself.alphabet_size_);
712                    diff[j] += combined_entropy[jx] - entropy[i] - xself.last_entropy_[jx];
713                }
714                j = j.wrapping_add(1);
715            }
716        }
717        if split.num_types < xself.max_block_types_
718            && (diff[0] > xself.split_threshold_)
719            && (diff[1] > xself.split_threshold_)
720        {
721            split.lengths.slice_mut()[xself.num_blocks_] = xself.block_size_ as u32;
722            split.types.slice_mut()[xself.num_blocks_] = split.num_types as u8;
723            xself.last_histogram_ix_[1] = xself.last_histogram_ix_[0];
724            xself.last_histogram_ix_[0] = split.num_types.wrapping_mul(num_contexts);
725            for i in 0usize..num_contexts {
726                xself.last_entropy_[num_contexts.wrapping_add(i)] = xself.last_entropy_[i];
727                xself.last_entropy_[i] = entropy[i];
728            }
729            xself.num_blocks_ = xself.num_blocks_.wrapping_add(1);
730            split.num_types = split.num_types.wrapping_add(1);
731            xself.curr_histogram_ix_ = xself.curr_histogram_ix_.wrapping_add(num_contexts);
732            if xself.curr_histogram_ix_ < *histograms_size {
733                ClearHistograms(
734                    &mut histograms[xself.curr_histogram_ix_..],
735                    xself.num_contexts_,
736                );
737            }
738            xself.block_size_ = 0usize;
739            xself.merge_last_count_ = 0usize;
740            xself.target_block_size_ = xself.min_block_size_;
741        } else if diff[1] < diff[0] - 20.0 {
742            split.lengths.slice_mut()[xself.num_blocks_] = xself.block_size_ as u32;
743            let nbm2 = split.types.slice()[xself.num_blocks_.wrapping_sub(2)];
744            split.types.slice_mut()[xself.num_blocks_] = nbm2;
745
746            {
747                xself.last_histogram_ix_.swap(0, 1);
748            }
749            for i in 0usize..num_contexts {
750                histograms[xself.last_histogram_ix_[0].wrapping_add(i)] =
751                    combined_histo.slice()[num_contexts.wrapping_add(i)].clone();
752                xself.last_entropy_[num_contexts.wrapping_add(i)] = xself.last_entropy_[i];
753                xself.last_entropy_[i] = combined_entropy[num_contexts.wrapping_add(i)];
754                HistogramClear(&mut histograms[xself.curr_histogram_ix_.wrapping_add(i)]);
755            }
756            xself.num_blocks_ = xself.num_blocks_.wrapping_add(1);
757            xself.block_size_ = 0usize;
758            xself.merge_last_count_ = 0usize;
759            xself.target_block_size_ = xself.min_block_size_;
760        } else {
761            {
762                let _rhs = xself.block_size_ as u32;
763                let _lhs = &mut split.lengths.slice_mut()[xself.num_blocks_.wrapping_sub(1)];
764                let old_split_length = *_lhs;
765                *_lhs = old_split_length.wrapping_add(_rhs);
766            }
767            for i in 0usize..num_contexts {
768                histograms[xself.last_histogram_ix_[0].wrapping_add(i)] =
769                    combined_histo.slice()[i].clone();
770                xself.last_entropy_[i] = combined_entropy[i];
771                if split.num_types == 1 {
772                    xself.last_entropy_[num_contexts.wrapping_add(i)] = xself.last_entropy_[i];
773                }
774                HistogramClear(&mut histograms[xself.curr_histogram_ix_.wrapping_add(i)]);
775            }
776            xself.block_size_ = 0usize;
777            if {
778                xself.merge_last_count_ = xself.merge_last_count_.wrapping_add(1);
779                xself.merge_last_count_
780            } > 1
781            {
782                xself.target_block_size_ =
783                    xself.target_block_size_.wrapping_add(xself.min_block_size_);
784            }
785        }
786        m.free_cell(combined_histo);
787    }
788    if is_final {
789        *histograms_size = split.num_types.wrapping_mul(num_contexts);
790        split.num_blocks = xself.num_blocks_;
791    }
792}
793
794fn BlockSplitterAddSymbol<
795    HistogramType: SliceWrapper<u32> + SliceWrapperMut<u32> + CostAccessors + Clone,
796    Alloc: alloc::Allocator<u8> + alloc::Allocator<u32>,
797>(
798    xself: &mut BlockSplitter,
799    split: &mut BlockSplit<Alloc>,
800    histograms: &mut [HistogramType],
801    histograms_size: &mut usize,
802    symbol: usize,
803) {
804    HistogramAddItem(&mut histograms[xself.curr_histogram_ix_], symbol);
805    xself.block_size_ = xself.block_size_.wrapping_add(1);
806    if xself.block_size_ == xself.target_block_size_ {
807        BlockSplitterFinishBlock(xself, split, histograms, histograms_size, false);
808    }
809}
810
811fn ContextBlockSplitterAddSymbol<
812    Alloc: alloc::Allocator<u8> + alloc::Allocator<u32> + alloc::Allocator<HistogramLiteral>,
813>(
814    xself: &mut ContextBlockSplitter,
815    m: &mut Alloc,
816    split: &mut BlockSplit<Alloc>,
817    histograms: &mut [HistogramLiteral],
818    histograms_size: &mut usize,
819    symbol: usize,
820    context: usize,
821) {
822    HistogramAddItem(
823        &mut histograms[xself.curr_histogram_ix_.wrapping_add(context)],
824        symbol,
825    );
826    xself.block_size_ = xself.block_size_.wrapping_add(1);
827    if xself.block_size_ == xself.target_block_size_ {
828        ContextBlockSplitterFinishBlock(xself, m, split, histograms, histograms_size, false);
829    }
830}
831
832fn MapStaticContexts<
833    Alloc: alloc::Allocator<u8>
834        + alloc::Allocator<u32>
835        + alloc::Allocator<HistogramLiteral>
836        + alloc::Allocator<HistogramCommand>
837        + alloc::Allocator<HistogramDistance>,
838>(
839    m32: &mut Alloc,
840    num_contexts: usize,
841    static_context_map: &[u32],
842    mb: &mut MetaBlockSplit<Alloc>,
843) {
844    mb.literal_context_map_size = mb.literal_split.num_types << 6;
845    let new_literal_context_map = allocate::<u32, _>(m32, mb.literal_context_map_size);
846    <Alloc as Allocator<u32>>::free_cell(
847        m32,
848        core::mem::replace(&mut mb.literal_context_map, new_literal_context_map),
849    );
850    for i in 0usize..mb.literal_split.num_types {
851        let offset: u32 = i.wrapping_mul(num_contexts) as u32;
852        for j in 0usize..(1u32 << 6) as usize {
853            mb.literal_context_map.slice_mut()[(i << 6).wrapping_add(j)] =
854                offset.wrapping_add(static_context_map[j]);
855        }
856    }
857}
858pub fn BrotliBuildMetaBlockGreedyInternal<
859    Alloc: alloc::Allocator<u8>
860        + alloc::Allocator<u32>
861        + alloc::Allocator<HistogramLiteral>
862        + alloc::Allocator<HistogramCommand>
863        + alloc::Allocator<HistogramDistance>,
864>(
865    alloc: &mut Alloc,
866    ringbuffer: &[u8],
867    mut pos: usize,
868    mask: usize,
869    mut prev_byte: u8,
870    mut prev_byte2: u8,
871    literal_context_mode: ContextType,
872    num_contexts: usize,
873    static_context_map: &[u32],
874    commands: &[Command],
875    n_commands: usize,
876    mb: &mut MetaBlockSplit<Alloc>,
877) {
878    let mut lit_blocks: LitBlocks;
879    let mut cmd_blocks: BlockSplitter;
880    let mut dist_blocks: BlockSplitter;
881    let mut num_literals: usize = 0usize;
882    for i in 0usize..n_commands {
883        num_literals = num_literals.wrapping_add((commands[i]).insert_len_ as usize);
884    }
885    lit_blocks = if num_contexts == 1 {
886        LitBlocks::plain(InitBlockSplitter::<HistogramLiteral, Alloc>(
887            alloc,
888            256usize,
889            512usize,
890            400.0,
891            num_literals,
892            &mut mb.literal_split,
893            &mut mb.literal_histograms,
894            &mut mb.literal_histograms_size,
895        ))
896    } else {
897        LitBlocks::ctx(InitContextBlockSplitter::<Alloc>(
898            alloc,
899            256usize,
900            num_contexts,
901            512usize,
902            400.0,
903            num_literals,
904            &mut mb.literal_split,
905            &mut mb.literal_histograms,
906            &mut mb.literal_histograms_size,
907        ))
908    };
909    cmd_blocks = InitBlockSplitter::<HistogramCommand, Alloc>(
910        alloc,
911        704usize,
912        1024usize,
913        500.0,
914        n_commands,
915        &mut mb.command_split,
916        &mut mb.command_histograms,
917        &mut mb.command_histograms_size,
918    );
919    dist_blocks = InitBlockSplitter::<HistogramDistance, Alloc>(
920        alloc,
921        64usize,
922        512usize,
923        100.0,
924        n_commands,
925        &mut mb.distance_split,
926        &mut mb.distance_histograms,
927        &mut mb.distance_histograms_size,
928    );
929
930    for i in 0usize..n_commands {
931        let cmd: Command = commands[i];
932        let mut j: usize;
933        BlockSplitterAddSymbol(
934            &mut cmd_blocks,
935            &mut mb.command_split,
936            mb.command_histograms.slice_mut(),
937            &mut mb.command_histograms_size,
938            cmd.cmd_prefix_ as usize,
939        );
940        j = cmd.insert_len_ as usize;
941        while j != 0usize {
942            {
943                let literal: u8 = ringbuffer[(pos & mask)];
944                match (&mut lit_blocks) {
945                    &mut LitBlocks::plain(ref mut lit_blocks_plain) => BlockSplitterAddSymbol(
946                        lit_blocks_plain,
947                        &mut mb.literal_split,
948                        mb.literal_histograms.slice_mut(),
949                        &mut mb.literal_histograms_size,
950                        literal as usize,
951                    ),
952                    &mut LitBlocks::ctx(ref mut lit_blocks_ctx) => {
953                        let context: usize =
954                            Context(prev_byte, prev_byte2, literal_context_mode) as usize;
955                        ContextBlockSplitterAddSymbol(
956                            lit_blocks_ctx,
957                            alloc,
958                            &mut mb.literal_split,
959                            mb.literal_histograms.slice_mut(),
960                            &mut mb.literal_histograms_size,
961                            literal as usize,
962                            static_context_map[(context as usize)] as usize,
963                        );
964                    }
965                }
966                prev_byte2 = prev_byte;
967                prev_byte = literal;
968                pos = pos.wrapping_add(1);
969            }
970            j = j.wrapping_sub(1);
971        }
972        pos = pos.wrapping_add(cmd.copy_len() as usize);
973        if cmd.copy_len() != 0 {
974            prev_byte2 = ringbuffer[(pos.wrapping_sub(2) & mask)];
975            prev_byte = ringbuffer[(pos.wrapping_sub(1) & mask)];
976            if cmd.cmd_prefix_ as i32 >= 128i32 {
977                BlockSplitterAddSymbol(
978                    &mut dist_blocks,
979                    &mut mb.distance_split,
980                    mb.distance_histograms.slice_mut(),
981                    &mut mb.distance_histograms_size,
982                    cmd.dist_prefix_ as usize & 0x3ff,
983                );
984            }
985        }
986    }
987    match (&mut lit_blocks) {
988        &mut LitBlocks::plain(ref mut lit_blocks_plain) => BlockSplitterFinishBlock(
989            lit_blocks_plain,
990            &mut mb.literal_split,
991            mb.literal_histograms.slice_mut(),
992            &mut mb.literal_histograms_size,
993            true,
994        ),
995        &mut LitBlocks::ctx(ref mut lit_blocks_ctx) => ContextBlockSplitterFinishBlock(
996            lit_blocks_ctx,
997            alloc,
998            &mut mb.literal_split,
999            mb.literal_histograms.slice_mut(),
1000            &mut mb.literal_histograms_size,
1001            true,
1002        ),
1003    }
1004    BlockSplitterFinishBlock(
1005        &mut cmd_blocks,
1006        &mut mb.command_split,
1007        mb.command_histograms.slice_mut(),
1008        &mut mb.command_histograms_size,
1009        true,
1010    );
1011    BlockSplitterFinishBlock(
1012        &mut dist_blocks,
1013        &mut mb.distance_split,
1014        mb.distance_histograms.slice_mut(),
1015        &mut mb.distance_histograms_size,
1016        true,
1017    );
1018    if num_contexts > 1 {
1019        MapStaticContexts(alloc, num_contexts, static_context_map, mb);
1020    }
1021}
1022pub fn BrotliBuildMetaBlockGreedy<
1023    Alloc: alloc::Allocator<u8>
1024        + alloc::Allocator<u32>
1025        + alloc::Allocator<HistogramLiteral>
1026        + alloc::Allocator<HistogramCommand>
1027        + alloc::Allocator<HistogramDistance>,
1028>(
1029    alloc: &mut Alloc,
1030    ringbuffer: &[u8],
1031    pos: usize,
1032    mask: usize,
1033    prev_byte: u8,
1034    prev_byte2: u8,
1035    literal_context_mode: ContextType,
1036    _literal_context_lut: &[u8],
1037    num_contexts: usize,
1038    static_context_map: &[u32],
1039    commands: &[Command],
1040    n_commands: usize,
1041    mb: &mut MetaBlockSplit<Alloc>,
1042) {
1043    if num_contexts == 1 {
1044        BrotliBuildMetaBlockGreedyInternal(
1045            alloc,
1046            ringbuffer,
1047            pos,
1048            mask,
1049            prev_byte,
1050            prev_byte2,
1051            literal_context_mode,
1052            1,
1053            &[],
1054            commands,
1055            n_commands,
1056            mb,
1057        );
1058    } else {
1059        BrotliBuildMetaBlockGreedyInternal(
1060            alloc,
1061            ringbuffer,
1062            pos,
1063            mask,
1064            prev_byte,
1065            prev_byte2,
1066            literal_context_mode,
1067            num_contexts,
1068            static_context_map,
1069            commands,
1070            n_commands,
1071            mb,
1072        );
1073    }
1074}
1075
1076pub fn BrotliOptimizeHistograms<
1077    Alloc: alloc::Allocator<u8>
1078        + alloc::Allocator<u32>
1079        + alloc::Allocator<HistogramLiteral>
1080        + alloc::Allocator<HistogramCommand>
1081        + alloc::Allocator<HistogramDistance>,
1082>(
1083    num_distance_codes: usize,
1084    mb: &mut MetaBlockSplit<Alloc>,
1085) {
1086    let mut good_for_rle: [u8; 704] = [0; 704];
1087    for i in 0usize..mb.literal_histograms_size {
1088        BrotliOptimizeHuffmanCountsForRle(
1089            256usize,
1090            mb.literal_histograms.slice_mut()[i].slice_mut(),
1091            &mut good_for_rle[..],
1092        );
1093    }
1094    for i in 0usize..mb.command_histograms_size {
1095        BrotliOptimizeHuffmanCountsForRle(
1096            704usize,
1097            mb.command_histograms.slice_mut()[i].slice_mut(),
1098            &mut good_for_rle[..],
1099        );
1100    }
1101    for i in 0usize..mb.distance_histograms_size {
1102        BrotliOptimizeHuffmanCountsForRle(
1103            num_distance_codes,
1104            mb.distance_histograms.slice_mut()[i].slice_mut(),
1105            &mut good_for_rle[..],
1106        );
1107    }
1108}
brotli/enc/metablock.rs

brotli/enc/
metablock.rs
