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
27namespace brotli {
28
29void 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
68void 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