brotli/enc/
metablock.rs

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

brotli/enc/
metablock.rs
