| OLD | NEW |
|---|
| (Empty) |
| 1 /* Copyright 2013 Google Inc. All Rights Reserved. | |
| 2 | |
| 3 Distributed under MIT license. | |
| 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT | |
| 5 */ | |
| 6 | |
| 7 // Implementation of parallel Brotli compressor. | |
| 8 | |
| 9 #include "./encode_parallel.h" | |
| 10 | |
| 11 #include <algorithm> | |
| 12 #include <limits> | |
| 13 | |
| 14 #include "./backward_references.h" | |
| 15 #include "./bit_cost.h" | |
| 16 #include "./block_splitter.h" | |
| 17 #include "./brotli_bit_stream.h" | |
| 18 #include "./cluster.h" | |
| 19 #include "./context.h" | |
| 20 #include "./metablock.h" | |
| 21 #include "./transform.h" | |
| 22 #include "./entropy_encode.h" | |
| 23 #include "./fast_log.h" | |
| 24 #include "./hash.h" | |
| 25 #include "./histogram.h" | |
| 26 #include "./prefix.h" | |
| 27 #include "./utf8_util.h" | |
| 28 #include "./write_bits.h" | |
| 29 | |
| 30 namespace brotli { | |
| 31 | |
| 32 namespace { | |
| 33 | |
| 34 void RecomputeDistancePrefixes(Command* cmds, size_t num_commands, | |
| 35 uint32_t num_direct_distance_codes, | |
| 36 uint32_t distance_postfix_bits) { | |
| 37 if (num_direct_distance_codes == 0 && | |
| 38 distance_postfix_bits == 0) { | |
| 39 return; | |
| 40 } | |
| 41 for (size_t i = 0; i < num_commands; ++i) { | |
| 42 Command* cmd = &cmds[i]; | |
| 43 if (cmd->copy_len() && cmd->cmd_prefix_ >= 128) { | |
| 44 PrefixEncodeCopyDistance(cmd->DistanceCode(), | |
| 45 num_direct_distance_codes, | |
| 46 distance_postfix_bits, | |
| 47 &cmd->dist_prefix_, | |
| 48 &cmd->dist_extra_); | |
| 49 } | |
| 50 } | |
| 51 } | |
| 52 | |
| 53 bool WriteMetaBlockParallel(const BrotliParams& params, | |
| 54 const uint32_t input_size, | |
| 55 const uint8_t* input_buffer, | |
| 56 const uint32_t prefix_size, | |
| 57 const uint8_t* prefix_buffer, | |
| 58 const bool is_first, | |
| 59 const bool is_last, | |
| 60 size_t* encoded_size, | |
| 61 uint8_t* encoded_buffer) { | |
| 62 if (input_size == 0) { | |
| 63 return false; | |
| 64 } | |
| 65 | |
| 66 // Copy prefix + next input block into a continuous area. | |
| 67 uint32_t input_pos = prefix_size; | |
| 68 // CreateBackwardReferences reads up to 3 bytes past the end of input if the | |
| 69 // mask points past the end of input. | |
| 70 // FindMatchLengthWithLimit could do another 8 bytes look-forward. | |
| 71 std::vector<uint8_t> input(prefix_size + input_size + 4 + 8); | |
| 72 memcpy(&input[0], prefix_buffer, prefix_size); | |
| 73 memcpy(&input[input_pos], input_buffer, input_size); | |
| 74 // Since we don't have a ringbuffer, masking is a no-op. | |
| 75 // We use one less bit than the full range because some of the code uses | |
| 76 // mask + 1 as the size of the ringbuffer. | |
| 77 const uint32_t mask = std::numeric_limits<uint32_t>::max() >> 1; | |
| 78 | |
| 79 uint8_t prev_byte = input_pos > 0 ? input[(input_pos - 1) & mask] : 0; | |
| 80 uint8_t prev_byte2 = input_pos > 1 ? input[(input_pos - 2) & mask] : 0; | |
| 81 | |
| 82 // Decide about UTF8 mode. | |
| 83 static const double kMinUTF8Ratio = 0.75; | |
| 84 bool utf8_mode = IsMostlyUTF8(&input[0], input_pos, mask, input_size, | |
| 85 kMinUTF8Ratio); | |
| 86 | |
| 87 // Initialize hashers. | |
| 88 int hash_type = std::min(10, params.quality); | |
| 89 Hashers* hashers = new Hashers(); | |
| 90 hashers->Init(hash_type); | |
| 91 | |
| 92 // Compute backward references. | |
| 93 size_t last_insert_len = 0; | |
| 94 size_t num_commands = 0; | |
| 95 size_t num_literals = 0; | |
| 96 int dist_cache[4] = { -4, -4, -4, -4 }; | |
| 97 Command* commands = static_cast<Command*>( | |
| 98 malloc(sizeof(Command) * ((input_size + 1) >> 1))); | |
| 99 if (commands == 0) { | |
| 100 delete hashers; | |
| 101 return false; | |
| 102 } | |
| 103 CreateBackwardReferences( | |
| 104 input_size, input_pos, is_last, | |
| 105 &input[0], mask, | |
| 106 params.quality, | |
| 107 params.lgwin, | |
| 108 hashers, | |
| 109 hash_type, | |
| 110 dist_cache, | |
| 111 &last_insert_len, | |
| 112 commands, | |
| 113 &num_commands, | |
| 114 &num_literals); | |
| 115 delete hashers; | |
| 116 if (last_insert_len > 0) { | |
| 117 commands[num_commands++] = Command(last_insert_len); | |
| 118 num_literals += last_insert_len; | |
| 119 } | |
| 120 assert(num_commands != 0); | |
| 121 | |
| 122 // Build the meta-block. | |
| 123 MetaBlockSplit mb; | |
| 124 uint32_t num_direct_distance_codes = | |
| 125 params.mode == BrotliParams::MODE_FONT ? 12 : 0; | |
| 126 uint32_t distance_postfix_bits = | |
| 127 params.mode == BrotliParams::MODE_FONT ? 1 : 0; | |
| 128 ContextType literal_context_mode = utf8_mode ? CONTEXT_UTF8 : CONTEXT_SIGNED; | |
| 129 RecomputeDistancePrefixes(commands, num_commands, | |
| 130 num_direct_distance_codes, | |
| 131 distance_postfix_bits); | |
| 132 if (params.quality <= 9) { | |
| 133 BuildMetaBlockGreedy(&input[0], input_pos, mask, | |
| 134 commands, num_commands, | |
| 135 &mb); | |
| 136 } else { | |
| 137 BuildMetaBlock(&input[0], input_pos, mask, | |
| 138 prev_byte, prev_byte2, | |
| 139 commands, num_commands, | |
| 140 literal_context_mode, | |
| 141 &mb); | |
| 142 } | |
| 143 | |
| 144 // Set up the temporary output storage. | |
| 145 const size_t max_out_size = 2 * input_size + 500; | |
| 146 std::vector<uint8_t> storage(max_out_size); | |
| 147 uint8_t first_byte = 0; | |
| 148 size_t first_byte_bits = 0; | |
| 149 if (is_first) { | |
| 150 if (params.lgwin == 16) { | |
| 151 first_byte = 0; | |
| 152 first_byte_bits = 1; | |
| 153 } else if (params.lgwin == 17) { | |
| 154 first_byte = 1; | |
| 155 first_byte_bits = 7; | |
| 156 } else { | |
| 157 first_byte = static_cast<uint8_t>(((params.lgwin - 17) << 1) | 1); | |
| 158 first_byte_bits = 4; | |
| 159 } | |
| 160 } | |
| 161 storage[0] = static_cast<uint8_t>(first_byte); | |
| 162 size_t storage_ix = first_byte_bits; | |
| 163 | |
| 164 // Store the meta-block to the temporary output. | |
| 165 StoreMetaBlock(&input[0], input_pos, input_size, mask, | |
| 166 prev_byte, prev_byte2, | |
| 167 is_last, | |
| 168 num_direct_distance_codes, | |
| 169 distance_postfix_bits, | |
| 170 literal_context_mode, | |
| 171 commands, num_commands, | |
| 172 mb, | |
| 173 &storage_ix, &storage[0]); | |
| 174 free(commands); | |
| 175 | |
| 176 // If this is not the last meta-block, store an empty metadata | |
| 177 // meta-block so that the meta-block will end at a byte boundary. | |
| 178 if (!is_last) { | |
| 179 StoreSyncMetaBlock(&storage_ix, &storage[0]); | |
| 180 } | |
| 181 | |
| 182 // If the compressed data is too large, fall back to an uncompressed | |
| 183 // meta-block. | |
| 184 size_t output_size = storage_ix >> 3; | |
| 185 if (input_size + 4 < output_size) { | |
| 186 storage[0] = static_cast<uint8_t>(first_byte); | |
| 187 storage_ix = first_byte_bits; | |
| 188 StoreUncompressedMetaBlock(is_last, &input[0], input_pos, mask, | |
| 189 input_size, | |
| 190 &storage_ix, &storage[0]); | |
| 191 output_size = storage_ix >> 3; | |
| 192 } | |
| 193 | |
| 194 // Copy the temporary output with size-check to the output. | |
| 195 if (output_size > *encoded_size) { | |
| 196 return false; | |
| 197 } | |
| 198 memcpy(encoded_buffer, &storage[0], output_size); | |
| 199 *encoded_size = output_size; | |
| 200 return true; | |
| 201 } | |
| 202 | |
| 203 } // namespace | |
| 204 | |
| 205 int BrotliCompressBufferParallel(BrotliParams params, | |
| 206 size_t input_size, | |
| 207 const uint8_t* input_buffer, | |
| 208 size_t* encoded_size, | |
| 209 uint8_t* encoded_buffer) { | |
| 210 if (*encoded_size == 0) { | |
| 211 // Output buffer needs at least one byte. | |
| 212 return 0; | |
| 213 } else if (input_size == 0) { | |
| 214 encoded_buffer[0] = 6; | |
| 215 *encoded_size = 1; | |
| 216 return 1; | |
| 217 } | |
| 218 | |
| 219 // Sanitize params. | |
| 220 if (params.lgwin < kMinWindowBits) { | |
| 221 params.lgwin = kMinWindowBits; | |
| 222 } else if (params.lgwin > kMaxWindowBits) { | |
| 223 params.lgwin = kMaxWindowBits; | |
| 224 } | |
| 225 if (params.lgblock == 0) { | |
| 226 params.lgblock = 16; | |
| 227 if (params.quality >= 9 && params.lgwin > params.lgblock) { | |
| 228 params.lgblock = std::min(21, params.lgwin); | |
| 229 } | |
| 230 } else if (params.lgblock < kMinInputBlockBits) { | |
| 231 params.lgblock = kMinInputBlockBits; | |
| 232 } else if (params.lgblock > kMaxInputBlockBits) { | |
| 233 params.lgblock = kMaxInputBlockBits; | |
| 234 } | |
| 235 size_t max_input_block_size = 1 << params.lgblock; | |
| 236 size_t max_prefix_size = 1u << params.lgwin; | |
| 237 | |
| 238 std::vector<std::vector<uint8_t> > compressed_pieces; | |
| 239 | |
| 240 // Compress block-by-block independently. | |
| 241 for (size_t pos = 0; pos < input_size; ) { | |
| 242 uint32_t input_block_size = | |
| 243 static_cast<uint32_t>(std::min(max_input_block_size, input_size - pos)); | |
| 244 uint32_t prefix_size = | |
| 245 static_cast<uint32_t>(std::min(max_prefix_size, pos)); | |
| 246 size_t out_size = input_block_size + (input_block_size >> 3) + 1024; | |
| 247 std::vector<uint8_t> out(out_size); | |
| 248 if (!WriteMetaBlockParallel(params, | |
| 249 input_block_size, | |
| 250 &input_buffer[pos], | |
| 251 prefix_size, | |
| 252 &input_buffer[pos - prefix_size], | |
| 253 pos == 0, | |
| 254 pos + input_block_size == input_size, | |
| 255 &out_size, | |
| 256 &out[0])) { | |
| 257 return false; | |
| 258 } | |
| 259 out.resize(out_size); | |
| 260 compressed_pieces.push_back(out); | |
| 261 pos += input_block_size; | |
| 262 } | |
| 263 | |
| 264 // Piece together the output. | |
| 265 size_t out_pos = 0; | |
| 266 for (size_t i = 0; i < compressed_pieces.size(); ++i) { | |
| 267 const std::vector<uint8_t>& out = compressed_pieces[i]; | |
| 268 if (out_pos + out.size() > *encoded_size) { | |
| 269 return false; | |
| 270 } | |
| 271 memcpy(&encoded_buffer[out_pos], &out[0], out.size()); | |
| 272 out_pos += out.size(); | |
| 273 } | |
| 274 *encoded_size = out_pos; | |
| 275 | |
| 276 return true; | |
| 277 } | |
| 278 | |
| 279 } // namespace brotli | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2537133002:
Update brotli to v1.0.0-snapshot. (Closed)
