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// Literal cost model to allow backward reference replacement to be efficient.
16
17#include "./literal_cost.h"
18
19#include <math.h>
20#include <stdint.h>
21#include <algorithm>
22
23namespace brotli {
24
25static int UTF8Position(int last, int c, int clamp) {
26  if (c < 128) {
27    return 0;  // Next one is the 'Byte 1' again.
28  } else if (c >= 192) {
29    return std::min(1, clamp);  // Next one is the 'Byte 2' of utf-8 encoding.
30  } else {
31    // Let's decide over the last byte if this ends the sequence.
32    if (last < 0xe0) {
33      return 0;  // Completed two or three byte coding.
34    } else {
35      return std::min(2, clamp);  // Next one is the 'Byte 3' of utf-8 encoding.
36    }
37  }
38}
39
40static int DecideMultiByteStatsLevel(size_t pos, size_t len, size_t mask,
41                                     const uint8_t *data) {
42  int counts[3] = { 0 };
43  int max_utf8 = 1;  // should be 2, but 1 compresses better.
44  int last_c = 0;
45  int utf8_pos = 0;
46  for (int i = 0; i < len; ++i) {
47    int c = data[(pos + i) & mask];
48    utf8_pos = UTF8Position(last_c, c, 2);
49    ++counts[utf8_pos];
50    last_c = c;
51  }
52  if (counts[2] < 500) {
53    max_utf8 = 1;
54  }
55  if (counts[1] + counts[2] < 25) {
56    max_utf8 = 0;
57  }
58  return max_utf8;
59}
60
61void EstimateBitCostsForLiteralsUTF8(size_t pos, size_t len, size_t mask,
62                                     size_t cost_mask, const uint8_t *data,
63                                     float *cost) {
64
65  // max_utf8 is 0 (normal ascii single byte modeling),
66  // 1 (for 2-byte utf-8 modeling), or 2 (for 3-byte utf-8 modeling).
67  const int max_utf8 = DecideMultiByteStatsLevel(pos, len, mask, data);
68  int histogram[3][256] = { { 0 } };
69  int window_half = 495;
70  int in_window = std::min(static_cast<size_t>(window_half), len);
71  int in_window_utf8[3] = { 0 };
72
73  // Bootstrap histograms.
74  int last_c = 0;
75  int utf8_pos = 0;
76  for (int i = 0; i < in_window; ++i) {
77    int c = data[(pos + i) & mask];
78    ++histogram[utf8_pos][c];
79    ++in_window_utf8[utf8_pos];
80    utf8_pos = UTF8Position(last_c, c, max_utf8);
81    last_c = c;
82  }
83
84  // Compute bit costs with sliding window.
85  for (int i = 0; i < len; ++i) {
86    if (i - window_half >= 0) {
87      // Remove a byte in the past.
88      int c = (i - window_half - 1) < 0 ?
89          0 : data[(pos + i - window_half - 1) & mask];
90      int last_c = (i - window_half - 2) < 0 ?
91          0 : data[(pos + i - window_half - 2) & mask];
92      int utf8_pos2 = UTF8Position(last_c, c, max_utf8);
93      --histogram[utf8_pos2][data[(pos + i - window_half) & mask]];
94      --in_window_utf8[utf8_pos2];
95    }
96    if (i + window_half < len) {
97      // Add a byte in the future.
98      int c = (i + window_half - 1) < 0 ?
99          0 : data[(pos + i + window_half - 1) & mask];
100      int last_c = (i + window_half - 2) < 0 ?
101          0 : data[(pos + i + window_half - 2) & mask];
102      int utf8_pos2 = UTF8Position(last_c, c, max_utf8);
103      ++histogram[utf8_pos2][data[(pos + i + window_half) & mask]];
104      ++in_window_utf8[utf8_pos2];
105    }
106    int c = i < 1 ? 0 : data[(pos + i - 1) & mask];
107    int last_c = i < 2 ? 0 : data[(pos + i - 2) & mask];
108    int utf8_pos = UTF8Position(last_c, c, max_utf8);
109    int masked_pos = (pos + i) & mask;
110    int histo = histogram[utf8_pos][data[masked_pos]];
111    if (histo == 0) {
112      histo = 1;
113    }
114    float lit_cost = log2(static_cast<double>(in_window_utf8[utf8_pos])
115                          / histo);
116    lit_cost += 0.02905;
117    if (lit_cost < 1.0) {
118      lit_cost *= 0.5;
119      lit_cost += 0.5;
120    }
121    // Make the first bytes more expensive -- seems to help, not sure why.
122    // Perhaps because the entropy source is changing its properties
123    // rapidly in the beginning of the file, perhaps because the beginning
124    // of the data is a statistical "anomaly".
125    if (i < 2000) {
126      lit_cost += 0.7 - ((2000 - i) / 2000.0 * 0.35);
127    }
128    cost[(pos + i) & cost_mask] = lit_cost;
129  }
130}
131
132void EstimateBitCostsForLiterals(size_t pos, size_t len, size_t mask,
133                                 size_t cost_mask, const uint8_t *data,
134                                 float *cost) {
135  int histogram[256] = { 0 };
136  int window_half = 2000;
137  int in_window = std::min(static_cast<size_t>(window_half), len);
138
139  // Bootstrap histogram.
140  for (int i = 0; i < in_window; ++i) {
141    ++histogram[data[(pos + i) & mask]];
142  }
143
144  // Compute bit costs with sliding window.
145  for (int i = 0; i < len; ++i) {
146    if (i - window_half >= 0) {
147      // Remove a byte in the past.
148      --histogram[data[(pos + i - window_half) & mask]];
149      --in_window;
150    }
151    if (i + window_half < len) {
152      // Add a byte in the future.
153      ++histogram[data[(pos + i + window_half) & mask]];
154      ++in_window;
155    }
156    int histo = histogram[data[(pos + i) & mask]];
157    if (histo == 0) {
158      histo = 1;
159    }
160    float lit_cost = log2(static_cast<double>(in_window) / histo);
161    lit_cost += 0.029;
162    if (lit_cost < 1.0) {
163      lit_cost *= 0.5;
164      lit_cost += 0.5;
165    }
166    cost[(pos + i) & cost_mask] = lit_cost;
167  }
168}
169
170
171}  // namespace brotli
172