1 // Copyright 2013 Google Inc. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Build per-context histograms of literals, commands and distance codes. 16 17 #include "./histogram.h" 18 19 #include <stdint.h> 20 #include <cmath> 21 22 #include "./block_splitter.h" 23 #include "./command.h" 24 #include "./context.h" 25 #include "./prefix.h" 26 27 namespace brotli { 28 29 void BuildHistograms( 30 const std::vector<Command>& cmds, 31 const BlockSplit& literal_split, 32 const BlockSplit& insert_and_copy_split, 33 const BlockSplit& dist_split, 34 const uint8_t* ringbuffer, 35 size_t pos, 36 size_t mask, 37 const std::vector<int>& context_modes, 38 std::vector<HistogramLiteral>* literal_histograms, 39 std::vector<HistogramCommand>* insert_and_copy_histograms, 40 std::vector<HistogramDistance>* copy_dist_histograms) { 41 BlockSplitIterator literal_it(literal_split); 42 BlockSplitIterator insert_and_copy_it(insert_and_copy_split); 43 BlockSplitIterator dist_it(dist_split); 44 for (int i = 0; i < cmds.size(); ++i) { 45 const Command &cmd = cmds[i]; 46 insert_and_copy_it.Next(); 47 (*insert_and_copy_histograms)[insert_and_copy_it.type_].Add( 48 cmd.command_prefix_); 49 for (int j = 0; j < cmd.insert_length_; ++j) { 50 literal_it.Next(); 51 uint8_t prev_byte = pos > 0 ? ringbuffer[(pos - 1) & mask] : 0; 52 uint8_t prev_byte2 = pos > 1 ? ringbuffer[(pos - 2) & mask] : 0; 53 int context = (literal_it.type_ << kLiteralContextBits) + 54 Context(prev_byte, prev_byte2, context_modes[literal_it.type_]); 55 (*literal_histograms)[context].Add(ringbuffer[pos & mask]); 56 ++pos; 57 } 58 pos += cmd.copy_length_; 59 if (cmd.copy_length_ > 0 && cmd.distance_prefix_ != 0xffff) { 60 dist_it.Next(); 61 int context = (dist_it.type_ << kDistanceContextBits) + 62 ((cmd.copy_length_code_ > 4) ? 3 : cmd.copy_length_code_ - 2); 63 (*copy_dist_histograms)[context].Add(cmd.distance_prefix_); 64 } 65 } 66 } 67 68 void BuildLiteralHistogramsForBlockType( 69 const std::vector<Command>& cmds, 70 const BlockSplit& literal_split, 71 const uint8_t* ringbuffer, 72 size_t pos, 73 size_t mask, 74 int block_type, 75 int context_mode, 76 std::vector<HistogramLiteral>* histograms) { 77 BlockSplitIterator literal_it(literal_split); 78 for (int i = 0; i < cmds.size(); ++i) { 79 const Command &cmd = cmds[i]; 80 for (int j = 0; j < cmd.insert_length_; ++j) { 81 literal_it.Next(); 82 if (literal_it.type_ == block_type) { 83 uint8_t prev_byte = pos > 0 ? ringbuffer[(pos - 1) & mask] : 0; 84 uint8_t prev_byte2 = pos > 1 ? ringbuffer[(pos - 2) & mask] : 0; 85 int context = Context(prev_byte, prev_byte2, context_mode); 86 (*histograms)[context].Add(ringbuffer[pos & mask]); 87 } 88 ++pos; 89 } 90 pos += cmd.copy_length_; 91 } 92 } 93 94 } // namespace brotli 95
