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