1 | /* Copyright 2013 Google Inc. All Rights Reserved. |
2 | |
3 | Distributed under MIT license. |
4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT |
5 | */ |
6 | |
7 | /* Build per-context histograms of literals, commands and distance codes. */ |
8 | |
9 | #include "./histogram.h" |
10 | |
11 | #include "../common/context.h" |
12 | #include "./block_splitter.h" |
13 | #include "./command.h" |
14 | |
15 | #if defined(__cplusplus) || defined(c_plusplus) |
16 | extern "C" { |
17 | #endif |
18 | |
19 | typedef struct BlockSplitIterator { |
20 | const BlockSplit* split_; /* Not owned. */ |
21 | size_t idx_; |
22 | size_t type_; |
23 | size_t length_; |
24 | } BlockSplitIterator; |
25 | |
26 | static void InitBlockSplitIterator(BlockSplitIterator* self, |
27 | const BlockSplit* split) { |
28 | self->split_ = split; |
29 | self->idx_ = 0; |
30 | self->type_ = 0; |
31 | self->length_ = split->lengths ? split->lengths[0] : 0; |
32 | } |
33 | |
34 | static void BlockSplitIteratorNext(BlockSplitIterator* self) { |
35 | if (self->length_ == 0) { |
36 | ++self->idx_; |
37 | self->type_ = self->split_->types[self->idx_]; |
38 | self->length_ = self->split_->lengths[self->idx_]; |
39 | } |
40 | --self->length_; |
41 | } |
42 | |
43 | void BrotliBuildHistogramsWithContext( |
44 | const Command* cmds, const size_t num_commands, |
45 | const BlockSplit* literal_split, const BlockSplit* insert_and_copy_split, |
46 | const BlockSplit* dist_split, const uint8_t* ringbuffer, size_t start_pos, |
47 | size_t mask, uint8_t prev_byte, uint8_t prev_byte2, |
48 | const ContextType* context_modes, HistogramLiteral* literal_histograms, |
49 | HistogramCommand* insert_and_copy_histograms, |
50 | HistogramDistance* copy_dist_histograms) { |
51 | size_t pos = start_pos; |
52 | BlockSplitIterator literal_it; |
53 | BlockSplitIterator insert_and_copy_it; |
54 | BlockSplitIterator dist_it; |
55 | size_t i; |
56 | |
57 | InitBlockSplitIterator(&literal_it, literal_split); |
58 | InitBlockSplitIterator(&insert_and_copy_it, insert_and_copy_split); |
59 | InitBlockSplitIterator(&dist_it, dist_split); |
60 | for (i = 0; i < num_commands; ++i) { |
61 | const Command* cmd = &cmds[i]; |
62 | size_t j; |
63 | BlockSplitIteratorNext(&insert_and_copy_it); |
64 | HistogramAddCommand(&insert_and_copy_histograms[insert_and_copy_it.type_], |
65 | cmd->cmd_prefix_); |
66 | /* TODO: unwrap iterator blocks. */ |
67 | for (j = cmd->insert_len_; j != 0; --j) { |
68 | size_t context; |
69 | BlockSplitIteratorNext(&literal_it); |
70 | context = literal_it.type_; |
71 | if (context_modes) { |
72 | ContextLut lut = BROTLI_CONTEXT_LUT(context_modes[context]); |
73 | context = (context << BROTLI_LITERAL_CONTEXT_BITS) + |
74 | BROTLI_CONTEXT(prev_byte, prev_byte2, lut); |
75 | } |
76 | HistogramAddLiteral(&literal_histograms[context], |
77 | ringbuffer[pos & mask]); |
78 | prev_byte2 = prev_byte; |
79 | prev_byte = ringbuffer[pos & mask]; |
80 | ++pos; |
81 | } |
82 | pos += CommandCopyLen(cmd); |
83 | if (CommandCopyLen(cmd)) { |
84 | prev_byte2 = ringbuffer[(pos - 2) & mask]; |
85 | prev_byte = ringbuffer[(pos - 1) & mask]; |
86 | if (cmd->cmd_prefix_ >= 128) { |
87 | size_t context; |
88 | BlockSplitIteratorNext(&dist_it); |
89 | context = (dist_it.type_ << BROTLI_DISTANCE_CONTEXT_BITS) + |
90 | CommandDistanceContext(cmd); |
91 | HistogramAddDistance(©_dist_histograms[context], |
92 | cmd->dist_prefix_ & 0x3FF); |
93 | } |
94 | } |
95 | } |
96 | } |
97 | |
98 | #if defined(__cplusplus) || defined(c_plusplus) |
99 | } /* extern "C" */ |
100 | #endif |
101 | |