]>
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 | /* Block split point selection utilities. */\r | |
8 | \r | |
9 | #include "./block_splitter.h"\r | |
10 | \r | |
11b7501a SB |
11 | #include <string.h> /* memcpy, memset */\r |
12 | \r | |
dd4f667e | 13 | #include "../common/platform.h"\r |
11b7501a SB |
14 | #include "./bit_cost.h"\r |
15 | #include "./cluster.h"\r | |
16 | #include "./command.h"\r | |
17 | #include "./fast_log.h"\r | |
18 | #include "./histogram.h"\r | |
19 | #include "./memory.h"\r | |
11b7501a SB |
20 | #include "./quality.h"\r |
21 | \r | |
22 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
23 | extern "C" {\r | |
24 | #endif\r | |
25 | \r | |
26 | static const size_t kMaxLiteralHistograms = 100;\r | |
27 | static const size_t kMaxCommandHistograms = 50;\r | |
28 | static const double kLiteralBlockSwitchCost = 28.1;\r | |
29 | static const double kCommandBlockSwitchCost = 13.5;\r | |
30 | static const double kDistanceBlockSwitchCost = 14.6;\r | |
31 | static const size_t kLiteralStrideLength = 70;\r | |
32 | static const size_t kCommandStrideLength = 40;\r | |
33 | static const size_t kSymbolsPerLiteralHistogram = 544;\r | |
34 | static const size_t kSymbolsPerCommandHistogram = 530;\r | |
35 | static const size_t kSymbolsPerDistanceHistogram = 544;\r | |
36 | static const size_t kMinLengthForBlockSplitting = 128;\r | |
37 | static const size_t kIterMulForRefining = 2;\r | |
38 | static const size_t kMinItersForRefining = 100;\r | |
39 | \r | |
40 | static size_t CountLiterals(const Command* cmds, const size_t num_commands) {\r | |
41 | /* Count how many we have. */\r | |
42 | size_t total_length = 0;\r | |
43 | size_t i;\r | |
44 | for (i = 0; i < num_commands; ++i) {\r | |
45 | total_length += cmds[i].insert_len_;\r | |
46 | }\r | |
47 | return total_length;\r | |
48 | }\r | |
49 | \r | |
50 | static void CopyLiteralsToByteArray(const Command* cmds,\r | |
51 | const size_t num_commands,\r | |
52 | const uint8_t* data,\r | |
53 | const size_t offset,\r | |
54 | const size_t mask,\r | |
55 | uint8_t* literals) {\r | |
56 | size_t pos = 0;\r | |
57 | size_t from_pos = offset & mask;\r | |
58 | size_t i;\r | |
59 | for (i = 0; i < num_commands; ++i) {\r | |
60 | size_t insert_len = cmds[i].insert_len_;\r | |
61 | if (from_pos + insert_len > mask) {\r | |
62 | size_t head_size = mask + 1 - from_pos;\r | |
63 | memcpy(literals + pos, data + from_pos, head_size);\r | |
64 | from_pos = 0;\r | |
65 | pos += head_size;\r | |
66 | insert_len -= head_size;\r | |
67 | }\r | |
68 | if (insert_len > 0) {\r | |
69 | memcpy(literals + pos, data + from_pos, insert_len);\r | |
70 | pos += insert_len;\r | |
71 | }\r | |
72 | from_pos = (from_pos + insert_len + CommandCopyLen(&cmds[i])) & mask;\r | |
73 | }\r | |
74 | }\r | |
75 | \r | |
dd4f667e LG |
76 | static BROTLI_INLINE uint32_t MyRand(uint32_t* seed) {\r |
77 | /* Initial seed should be 7. In this case, loop length is (1 << 29). */\r | |
11b7501a | 78 | *seed *= 16807U;\r |
11b7501a SB |
79 | return *seed;\r |
80 | }\r | |
81 | \r | |
82 | static BROTLI_INLINE double BitCost(size_t count) {\r | |
83 | return count == 0 ? -2.0 : FastLog2(count);\r | |
84 | }\r | |
85 | \r | |
86 | #define HISTOGRAMS_PER_BATCH 64\r | |
87 | #define CLUSTERS_PER_BATCH 16\r | |
88 | \r | |
89 | #define FN(X) X ## Literal\r | |
90 | #define DataType uint8_t\r | |
91 | /* NOLINTNEXTLINE(build/include) */\r | |
92 | #include "./block_splitter_inc.h"\r | |
93 | #undef DataType\r | |
94 | #undef FN\r | |
95 | \r | |
96 | #define FN(X) X ## Command\r | |
97 | #define DataType uint16_t\r | |
98 | /* NOLINTNEXTLINE(build/include) */\r | |
99 | #include "./block_splitter_inc.h"\r | |
100 | #undef FN\r | |
101 | \r | |
102 | #define FN(X) X ## Distance\r | |
103 | /* NOLINTNEXTLINE(build/include) */\r | |
104 | #include "./block_splitter_inc.h"\r | |
105 | #undef DataType\r | |
106 | #undef FN\r | |
107 | \r | |
108 | void BrotliInitBlockSplit(BlockSplit* self) {\r | |
109 | self->num_types = 0;\r | |
110 | self->num_blocks = 0;\r | |
111 | self->types = 0;\r | |
112 | self->lengths = 0;\r | |
113 | self->types_alloc_size = 0;\r | |
114 | self->lengths_alloc_size = 0;\r | |
115 | }\r | |
116 | \r | |
117 | void BrotliDestroyBlockSplit(MemoryManager* m, BlockSplit* self) {\r | |
118 | BROTLI_FREE(m, self->types);\r | |
119 | BROTLI_FREE(m, self->lengths);\r | |
120 | }\r | |
121 | \r | |
122 | void BrotliSplitBlock(MemoryManager* m,\r | |
123 | const Command* cmds,\r | |
124 | const size_t num_commands,\r | |
125 | const uint8_t* data,\r | |
126 | const size_t pos,\r | |
127 | const size_t mask,\r | |
128 | const BrotliEncoderParams* params,\r | |
129 | BlockSplit* literal_split,\r | |
130 | BlockSplit* insert_and_copy_split,\r | |
131 | BlockSplit* dist_split) {\r | |
132 | {\r | |
133 | size_t literals_count = CountLiterals(cmds, num_commands);\r | |
134 | uint8_t* literals = BROTLI_ALLOC(m, uint8_t, literals_count);\r | |
135 | if (BROTLI_IS_OOM(m)) return;\r | |
136 | /* Create a continuous array of literals. */\r | |
137 | CopyLiteralsToByteArray(cmds, num_commands, data, pos, mask, literals);\r | |
138 | /* Create the block split on the array of literals.\r | |
139 | Literal histograms have alphabet size 256. */\r | |
140 | SplitByteVectorLiteral(\r | |
141 | m, literals, literals_count,\r | |
142 | kSymbolsPerLiteralHistogram, kMaxLiteralHistograms,\r | |
143 | kLiteralStrideLength, kLiteralBlockSwitchCost, params,\r | |
144 | literal_split);\r | |
145 | if (BROTLI_IS_OOM(m)) return;\r | |
146 | BROTLI_FREE(m, literals);\r | |
147 | }\r | |
148 | \r | |
149 | {\r | |
150 | /* Compute prefix codes for commands. */\r | |
151 | uint16_t* insert_and_copy_codes = BROTLI_ALLOC(m, uint16_t, num_commands);\r | |
152 | size_t i;\r | |
153 | if (BROTLI_IS_OOM(m)) return;\r | |
154 | for (i = 0; i < num_commands; ++i) {\r | |
155 | insert_and_copy_codes[i] = cmds[i].cmd_prefix_;\r | |
156 | }\r | |
157 | /* Create the block split on the array of command prefixes. */\r | |
158 | SplitByteVectorCommand(\r | |
159 | m, insert_and_copy_codes, num_commands,\r | |
160 | kSymbolsPerCommandHistogram, kMaxCommandHistograms,\r | |
161 | kCommandStrideLength, kCommandBlockSwitchCost, params,\r | |
162 | insert_and_copy_split);\r | |
163 | if (BROTLI_IS_OOM(m)) return;\r | |
164 | /* TODO: reuse for distances? */\r | |
165 | BROTLI_FREE(m, insert_and_copy_codes);\r | |
166 | }\r | |
167 | \r | |
168 | {\r | |
169 | /* Create a continuous array of distance prefixes. */\r | |
170 | uint16_t* distance_prefixes = BROTLI_ALLOC(m, uint16_t, num_commands);\r | |
171 | size_t j = 0;\r | |
172 | size_t i;\r | |
173 | if (BROTLI_IS_OOM(m)) return;\r | |
174 | for (i = 0; i < num_commands; ++i) {\r | |
175 | const Command* cmd = &cmds[i];\r | |
176 | if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {\r | |
dd4f667e | 177 | distance_prefixes[j++] = cmd->dist_prefix_ & 0x3FF;\r |
11b7501a SB |
178 | }\r |
179 | }\r | |
180 | /* Create the block split on the array of distance prefixes. */\r | |
181 | SplitByteVectorDistance(\r | |
182 | m, distance_prefixes, j,\r | |
183 | kSymbolsPerDistanceHistogram, kMaxCommandHistograms,\r | |
184 | kCommandStrideLength, kDistanceBlockSwitchCost, params,\r | |
185 | dist_split);\r | |
186 | if (BROTLI_IS_OOM(m)) return;\r | |
187 | BROTLI_FREE(m, distance_prefixes);\r | |
188 | }\r | |
189 | }\r | |
190 | \r | |
191 | \r | |
192 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
193 | } /* extern "C" */\r | |
194 | #endif\r |