brotli/enc/
metablock.rs

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

brotli/enc/
metablock.rs
