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 /* Function to find backward reference copies. */ 8 9 #include "./backward_references_hq.h" 10 11 #include <string.h> /* memcpy, memset */ 12 13 #include "../common/constants.h" 14 #include "../common/platform.h" 15 #include <brotli/types.h> 16 #include "./command.h" 17 #include "./fast_log.h" 18 #include "./find_match_length.h" 19 #include "./literal_cost.h" 20 #include "./memory.h" 21 #include "./params.h" 22 #include "./prefix.h" 23 #include "./quality.h" 24 25 #if defined(__cplusplus) || defined(c_plusplus) 26 extern "C" { 27 #endif 28 29 #define BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE 544 30 31 static const float kInfinity = 1.7e38f; /* ~= 2 ^ 127 */ 32 33 static const uint32_t kDistanceCacheIndex[] = { 34 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 35 }; 36 static const int kDistanceCacheOffset[] = { 37 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 38 }; 39 40 void BrotliInitZopfliNodes(ZopfliNode* array, size_t length) { 41 ZopfliNode stub; 42 size_t i; 43 stub.length = 1; 44 stub.distance = 0; 45 stub.dcode_insert_length = 0; 46 stub.u.cost = kInfinity; 47 for (i = 0; i < length; ++i) array[i] = stub; 48 } 49 50 static BROTLI_INLINE uint32_t ZopfliNodeCopyLength(const ZopfliNode* self) { 51 return self->length & 0x1FFFFFF; 52 } 53 54 static BROTLI_INLINE uint32_t ZopfliNodeLengthCode(const ZopfliNode* self) { 55 const uint32_t modifier = self->length >> 25; 56 return ZopfliNodeCopyLength(self) + 9u - modifier; 57 } 58 59 static BROTLI_INLINE uint32_t ZopfliNodeCopyDistance(const ZopfliNode* self) { 60 return self->distance; 61 } 62 63 static BROTLI_INLINE uint32_t ZopfliNodeDistanceCode(const ZopfliNode* self) { 64 const uint32_t short_code = self->dcode_insert_length >> 27; 65 return short_code == 0 ? 66 ZopfliNodeCopyDistance(self) + BROTLI_NUM_DISTANCE_SHORT_CODES - 1 : 67 short_code - 1; 68 } 69 70 static BROTLI_INLINE uint32_t ZopfliNodeCommandLength(const ZopfliNode* self) { 71 return ZopfliNodeCopyLength(self) + (self->dcode_insert_length & 0x7FFFFFF); 72 } 73 74 /* Histogram based cost model for zopflification. */ 75 typedef struct ZopfliCostModel { 76 /* The insert and copy length symbols. */ 77 float cost_cmd_[BROTLI_NUM_COMMAND_SYMBOLS]; 78 float* cost_dist_; 79 uint32_t distance_histogram_size; 80 /* Cumulative costs of literals per position in the stream. */ 81 float* literal_costs_; 82 float min_cost_cmd_; 83 size_t num_bytes_; 84 } ZopfliCostModel; 85 86 static void InitZopfliCostModel( 87 MemoryManager* m, ZopfliCostModel* self, const BrotliDistanceParams* dist, 88 size_t num_bytes) { 89 uint32_t distance_histogram_size = dist->alphabet_size; 90 if (distance_histogram_size > BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE) { 91 distance_histogram_size = BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE; 92 } 93 self->num_bytes_ = num_bytes; 94 self->literal_costs_ = BROTLI_ALLOC(m, float, num_bytes + 2); 95 self->cost_dist_ = BROTLI_ALLOC(m, float, dist->alphabet_size); 96 self->distance_histogram_size = distance_histogram_size; 97 if (BROTLI_IS_OOM(m)) return; 98 } 99 100 static void CleanupZopfliCostModel(MemoryManager* m, ZopfliCostModel* self) { 101 BROTLI_FREE(m, self->literal_costs_); 102 BROTLI_FREE(m, self->cost_dist_); 103 } 104 105 static void SetCost(const uint32_t* histogram, size_t histogram_size, 106 BROTLI_BOOL literal_histogram, float* cost) { 107 size_t sum = 0; 108 size_t missing_symbol_sum; 109 float log2sum; 110 float missing_symbol_cost; 111 size_t i; 112 for (i = 0; i < histogram_size; i++) { 113 sum += histogram[i]; 114 } 115 log2sum = (float)FastLog2(sum); 116 missing_symbol_sum = sum; 117 if (!literal_histogram) { 118 for (i = 0; i < histogram_size; i++) { 119 if (histogram[i] == 0) missing_symbol_sum++; 120 } 121 } 122 missing_symbol_cost = (float)FastLog2(missing_symbol_sum) + 2; 123 for (i = 0; i < histogram_size; i++) { 124 if (histogram[i] == 0) { 125 cost[i] = missing_symbol_cost; 126 continue; 127 } 128 129 /* Shannon bits for this symbol. */ 130 cost[i] = log2sum - (float)FastLog2(histogram[i]); 131 132 /* Cannot be coded with less than 1 bit */ 133 if (cost[i] < 1) cost[i] = 1; 134 } 135 } 136 137 static void ZopfliCostModelSetFromCommands(ZopfliCostModel* self, 138 size_t position, 139 const uint8_t* ringbuffer, 140 size_t ringbuffer_mask, 141 const Command* commands, 142 size_t num_commands, 143 size_t last_insert_len) { 144 uint32_t histogram_literal[BROTLI_NUM_LITERAL_SYMBOLS]; 145 uint32_t histogram_cmd[BROTLI_NUM_COMMAND_SYMBOLS]; 146 uint32_t histogram_dist[BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE]; 147 float cost_literal[BROTLI_NUM_LITERAL_SYMBOLS]; 148 size_t pos = position - last_insert_len; 149 float min_cost_cmd = kInfinity; 150 size_t i; 151 float* cost_cmd = self->cost_cmd_; 152 153 memset(histogram_literal, 0, sizeof(histogram_literal)); 154 memset(histogram_cmd, 0, sizeof(histogram_cmd)); 155 memset(histogram_dist, 0, sizeof(histogram_dist)); 156 157 for (i = 0; i < num_commands; i++) { 158 size_t inslength = commands[i].insert_len_; 159 size_t copylength = CommandCopyLen(&commands[i]); 160 size_t distcode = commands[i].dist_prefix_ & 0x3FF; 161 size_t cmdcode = commands[i].cmd_prefix_; 162 size_t j; 163 164 histogram_cmd[cmdcode]++; 165 if (cmdcode >= 128) histogram_dist[distcode]++; 166 167 for (j = 0; j < inslength; j++) { 168 histogram_literal[ringbuffer[(pos + j) & ringbuffer_mask]]++; 169 } 170 171 pos += inslength + copylength; 172 } 173 174 SetCost(histogram_literal, BROTLI_NUM_LITERAL_SYMBOLS, BROTLI_TRUE, 175 cost_literal); 176 SetCost(histogram_cmd, BROTLI_NUM_COMMAND_SYMBOLS, BROTLI_FALSE, 177 cost_cmd); 178 SetCost(histogram_dist, self->distance_histogram_size, BROTLI_FALSE, 179 self->cost_dist_); 180 181 for (i = 0; i < BROTLI_NUM_COMMAND_SYMBOLS; ++i) { 182 min_cost_cmd = BROTLI_MIN(float, min_cost_cmd, cost_cmd[i]); 183 } 184 self->min_cost_cmd_ = min_cost_cmd; 185 186 { 187 float* literal_costs = self->literal_costs_; 188 float literal_carry = 0.0; 189 size_t num_bytes = self->num_bytes_; 190 literal_costs[0] = 0.0; 191 for (i = 0; i < num_bytes; ++i) { 192 literal_carry += 193 cost_literal[ringbuffer[(position + i) & ringbuffer_mask]]; 194 literal_costs[i + 1] = literal_costs[i] + literal_carry; 195 literal_carry -= literal_costs[i + 1] - literal_costs[i]; 196 } 197 } 198 } 199 200 static void ZopfliCostModelSetFromLiteralCosts(ZopfliCostModel* self, 201 size_t position, 202 const uint8_t* ringbuffer, 203 size_t ringbuffer_mask) { 204 float* literal_costs = self->literal_costs_; 205 float literal_carry = 0.0; 206 float* cost_dist = self->cost_dist_; 207 float* cost_cmd = self->cost_cmd_; 208 size_t num_bytes = self->num_bytes_; 209 size_t i; 210 BrotliEstimateBitCostsForLiterals(position, num_bytes, ringbuffer_mask, 211 ringbuffer, &literal_costs[1]); 212 literal_costs[0] = 0.0; 213 for (i = 0; i < num_bytes; ++i) { 214 literal_carry += literal_costs[i + 1]; 215 literal_costs[i + 1] = literal_costs[i] + literal_carry; 216 literal_carry -= literal_costs[i + 1] - literal_costs[i]; 217 } 218 for (i = 0; i < BROTLI_NUM_COMMAND_SYMBOLS; ++i) { 219 cost_cmd[i] = (float)FastLog2(11 + (uint32_t)i); 220 } 221 for (i = 0; i < self->distance_histogram_size; ++i) { 222 cost_dist[i] = (float)FastLog2(20 + (uint32_t)i); 223 } 224 self->min_cost_cmd_ = (float)FastLog2(11); 225 } 226 227 static BROTLI_INLINE float ZopfliCostModelGetCommandCost( 228 const ZopfliCostModel* self, uint16_t cmdcode) { 229 return self->cost_cmd_[cmdcode]; 230 } 231 232 static BROTLI_INLINE float ZopfliCostModelGetDistanceCost( 233 const ZopfliCostModel* self, size_t distcode) { 234 return self->cost_dist_[distcode]; 235 } 236 237 static BROTLI_INLINE float ZopfliCostModelGetLiteralCosts( 238 const ZopfliCostModel* self, size_t from, size_t to) { 239 return self->literal_costs_[to] - self->literal_costs_[from]; 240 } 241 242 static BROTLI_INLINE float ZopfliCostModelGetMinCostCmd( 243 const ZopfliCostModel* self) { 244 return self->min_cost_cmd_; 245 } 246 247 /* REQUIRES: len >= 2, start_pos <= pos */ 248 /* REQUIRES: cost < kInfinity, nodes[start_pos].cost < kInfinity */ 249 /* Maintains the "ZopfliNode array invariant". */ 250 static BROTLI_INLINE void UpdateZopfliNode(ZopfliNode* nodes, size_t pos, 251 size_t start_pos, size_t len, size_t len_code, size_t dist, 252 size_t short_code, float cost) { 253 ZopfliNode* next = &nodes[pos + len]; 254 next->length = (uint32_t)(len | ((len + 9u - len_code) << 25)); 255 next->distance = (uint32_t)dist; 256 next->dcode_insert_length = (uint32_t)( 257 (short_code << 27) | (pos - start_pos)); 258 next->u.cost = cost; 259 } 260 261 typedef struct PosData { 262 size_t pos; 263 int distance_cache[4]; 264 float costdiff; 265 float cost; 266 } PosData; 267 268 /* Maintains the smallest 8 cost difference together with their positions */ 269 typedef struct StartPosQueue { 270 PosData q_[8]; 271 size_t idx_; 272 } StartPosQueue; 273 274 static BROTLI_INLINE void InitStartPosQueue(StartPosQueue* self) { 275 self->idx_ = 0; 276 } 277 278 static size_t StartPosQueueSize(const StartPosQueue* self) { 279 return BROTLI_MIN(size_t, self->idx_, 8); 280 } 281 282 static void StartPosQueuePush(StartPosQueue* self, const PosData* posdata) { 283 size_t offset = ~(self->idx_++) & 7; 284 size_t len = StartPosQueueSize(self); 285 size_t i; 286 PosData* q = self->q_; 287 q[offset] = *posdata; 288 /* Restore the sorted order. In the list of |len| items at most |len - 1| 289 adjacent element comparisons / swaps are required. */ 290 for (i = 1; i < len; ++i) { 291 if (q[offset & 7].costdiff > q[(offset + 1) & 7].costdiff) { 292 BROTLI_SWAP(PosData, q, offset & 7, (offset + 1) & 7); 293 } 294 ++offset; 295 } 296 } 297 298 static const PosData* StartPosQueueAt(const StartPosQueue* self, size_t k) { 299 return &self->q_[(k - self->idx_) & 7]; 300 } 301 302 /* Returns the minimum possible copy length that can improve the cost of any */ 303 /* future position. */ 304 static size_t ComputeMinimumCopyLength(const float start_cost, 305 const ZopfliNode* nodes, 306 const size_t num_bytes, 307 const size_t pos) { 308 /* Compute the minimum possible cost of reaching any future position. */ 309 float min_cost = start_cost; 310 size_t len = 2; 311 size_t next_len_bucket = 4; 312 size_t next_len_offset = 10; 313 while (pos + len <= num_bytes && nodes[pos + len].u.cost <= min_cost) { 314 /* We already reached (pos + len) with no more cost than the minimum 315 possible cost of reaching anything from this pos, so there is no point in 316 looking for lengths <= len. */ 317 ++len; 318 if (len == next_len_offset) { 319 /* We reached the next copy length code bucket, so we add one more 320 extra bit to the minimum cost. */ 321 min_cost += 1.0f; 322 next_len_offset += next_len_bucket; 323 next_len_bucket *= 2; 324 } 325 } 326 return len; 327 } 328 329 /* REQUIRES: nodes[pos].cost < kInfinity 330 REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */ 331 static uint32_t ComputeDistanceShortcut(const size_t block_start, 332 const size_t pos, 333 const size_t max_backward_limit, 334 const size_t gap, 335 const ZopfliNode* nodes) { 336 const size_t clen = ZopfliNodeCopyLength(&nodes[pos]); 337 const size_t ilen = nodes[pos].dcode_insert_length & 0x7FFFFFF; 338 const size_t dist = ZopfliNodeCopyDistance(&nodes[pos]); 339 /* Since |block_start + pos| is the end position of the command, the copy part 340 starts from |block_start + pos - clen|. Distances that are greater than 341 this or greater than |max_backward_limit| + |gap| are static dictionary 342 references, and do not update the last distances. 343 Also distance code 0 (last distance) does not update the last distances. */ 344 if (pos == 0) { 345 return 0; 346 } else if (dist + clen <= block_start + pos + gap && 347 dist <= max_backward_limit + gap && 348 ZopfliNodeDistanceCode(&nodes[pos]) > 0) { 349 return (uint32_t)pos; 350 } else { 351 return nodes[pos - clen - ilen].u.shortcut; 352 } 353 } 354 355 /* Fills in dist_cache[0..3] with the last four distances (as defined by 356 Section 4. of the Spec) that would be used at (block_start + pos) if we 357 used the shortest path of commands from block_start, computed from 358 nodes[0..pos]. The last four distances at block_start are in 359 starting_dist_cache[0..3]. 360 REQUIRES: nodes[pos].cost < kInfinity 361 REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */ 362 static void ComputeDistanceCache(const size_t pos, 363 const int* starting_dist_cache, 364 const ZopfliNode* nodes, 365 int* dist_cache) { 366 int idx = 0; 367 size_t p = nodes[pos].u.shortcut; 368 while (idx < 4 && p > 0) { 369 const size_t ilen = nodes[p].dcode_insert_length & 0x7FFFFFF; 370 const size_t clen = ZopfliNodeCopyLength(&nodes[p]); 371 const size_t dist = ZopfliNodeCopyDistance(&nodes[p]); 372 dist_cache[idx++] = (int)dist; 373 /* Because of prerequisite, p >= clen + ilen >= 2. */ 374 p = nodes[p - clen - ilen].u.shortcut; 375 } 376 for (; idx < 4; ++idx) { 377 dist_cache[idx] = *starting_dist_cache++; 378 } 379 } 380 381 /* Maintains "ZopfliNode array invariant" and pushes node to the queue, if it 382 is eligible. */ 383 static void EvaluateNode( 384 const size_t block_start, const size_t pos, const size_t max_backward_limit, 385 const size_t gap, const int* starting_dist_cache, 386 const ZopfliCostModel* model, StartPosQueue* queue, ZopfliNode* nodes) { 387 /* Save cost, because ComputeDistanceCache invalidates it. */ 388 float node_cost = nodes[pos].u.cost; 389 nodes[pos].u.shortcut = ComputeDistanceShortcut( 390 block_start, pos, max_backward_limit, gap, nodes); 391 if (node_cost <= ZopfliCostModelGetLiteralCosts(model, 0, pos)) { 392 PosData posdata; 393 posdata.pos = pos; 394 posdata.cost = node_cost; 395 posdata.costdiff = node_cost - 396 ZopfliCostModelGetLiteralCosts(model, 0, pos); 397 ComputeDistanceCache( 398 pos, starting_dist_cache, nodes, posdata.distance_cache); 399 StartPosQueuePush(queue, &posdata); 400 } 401 } 402 403 /* Returns longest copy length. */ 404 static size_t UpdateNodes( 405 const size_t num_bytes, const size_t block_start, const size_t pos, 406 const uint8_t* ringbuffer, const size_t ringbuffer_mask, 407 const BrotliEncoderParams* params, const size_t max_backward_limit, 408 const int* starting_dist_cache, const size_t num_matches, 409 const BackwardMatch* matches, const ZopfliCostModel* model, 410 StartPosQueue* queue, ZopfliNode* nodes) { 411 const size_t cur_ix = block_start + pos; 412 const size_t cur_ix_masked = cur_ix & ringbuffer_mask; 413 const size_t max_distance = BROTLI_MIN(size_t, cur_ix, max_backward_limit); 414 const size_t max_len = num_bytes - pos; 415 const size_t max_zopfli_len = MaxZopfliLen(params); 416 const size_t max_iters = MaxZopfliCandidates(params); 417 size_t min_len; 418 size_t result = 0; 419 size_t k; 420 size_t gap = 0; 421 422 EvaluateNode(block_start, pos, max_backward_limit, gap, starting_dist_cache, 423 model, queue, nodes); 424 425 { 426 const PosData* posdata = StartPosQueueAt(queue, 0); 427 float min_cost = (posdata->cost + ZopfliCostModelGetMinCostCmd(model) + 428 ZopfliCostModelGetLiteralCosts(model, posdata->pos, pos)); 429 min_len = ComputeMinimumCopyLength(min_cost, nodes, num_bytes, pos); 430 } 431 432 /* Go over the command starting positions in order of increasing cost 433 difference. */ 434 for (k = 0; k < max_iters && k < StartPosQueueSize(queue); ++k) { 435 const PosData* posdata = StartPosQueueAt(queue, k); 436 const size_t start = posdata->pos; 437 const uint16_t inscode = GetInsertLengthCode(pos - start); 438 const float start_costdiff = posdata->costdiff; 439 const float base_cost = start_costdiff + (float)GetInsertExtra(inscode) + 440 ZopfliCostModelGetLiteralCosts(model, 0, pos); 441 442 /* Look for last distance matches using the distance cache from this 443 starting position. */ 444 size_t best_len = min_len - 1; 445 size_t j = 0; 446 for (; j < BROTLI_NUM_DISTANCE_SHORT_CODES && best_len < max_len; ++j) { 447 const size_t idx = kDistanceCacheIndex[j]; 448 const size_t backward = 449 (size_t)(posdata->distance_cache[idx] + kDistanceCacheOffset[j]); 450 size_t prev_ix = cur_ix - backward; 451 size_t len = 0; 452 uint8_t continuation = ringbuffer[cur_ix_masked + best_len]; 453 if (cur_ix_masked + best_len > ringbuffer_mask) { 454 break; 455 } 456 if (BROTLI_PREDICT_FALSE(backward > max_distance + gap)) { 457 /* Word dictionary -> ignore. */ 458 continue; 459 } 460 if (backward <= max_distance) { 461 /* Regular backward reference. */ 462 if (prev_ix >= cur_ix) { 463 continue; 464 } 465 466 prev_ix &= ringbuffer_mask; 467 if (prev_ix + best_len > ringbuffer_mask || 468 continuation != ringbuffer[prev_ix + best_len]) { 469 continue; 470 } 471 len = FindMatchLengthWithLimit(&ringbuffer[prev_ix], 472 &ringbuffer[cur_ix_masked], 473 max_len); 474 } else { 475 continue; 476 } 477 { 478 const float dist_cost = base_cost + 479 ZopfliCostModelGetDistanceCost(model, j); 480 size_t l; 481 for (l = best_len + 1; l <= len; ++l) { 482 const uint16_t copycode = GetCopyLengthCode(l); 483 const uint16_t cmdcode = 484 CombineLengthCodes(inscode, copycode, j == 0); 485 const float cost = (cmdcode < 128 ? base_cost : dist_cost) + 486 (float)GetCopyExtra(copycode) + 487 ZopfliCostModelGetCommandCost(model, cmdcode); 488 if (cost < nodes[pos + l].u.cost) { 489 UpdateZopfliNode(nodes, pos, start, l, l, backward, j + 1, cost); 490 result = BROTLI_MAX(size_t, result, l); 491 } 492 best_len = l; 493 } 494 } 495 } 496 497 /* At higher iterations look only for new last distance matches, since 498 looking only for new command start positions with the same distances 499 does not help much. */ 500 if (k >= 2) continue; 501 502 { 503 /* Loop through all possible copy lengths at this position. */ 504 size_t len = min_len; 505 for (j = 0; j < num_matches; ++j) { 506 BackwardMatch match = matches[j]; 507 size_t dist = match.distance; 508 BROTLI_BOOL is_dictionary_match = 509 TO_BROTLI_BOOL(dist > max_distance + gap); 510 /* We already tried all possible last distance matches, so we can use 511 normal distance code here. */ 512 size_t dist_code = dist + BROTLI_NUM_DISTANCE_SHORT_CODES - 1; 513 uint16_t dist_symbol; 514 uint32_t distextra; 515 uint32_t distnumextra; 516 float dist_cost; 517 size_t max_match_len; 518 PrefixEncodeCopyDistance( 519 dist_code, params->dist.num_direct_distance_codes, 520 params->dist.distance_postfix_bits, &dist_symbol, &distextra); 521 distnumextra = dist_symbol >> 10; 522 dist_cost = base_cost + (float)distnumextra + 523 ZopfliCostModelGetDistanceCost(model, dist_symbol & 0x3FF); 524 525 /* Try all copy lengths up until the maximum copy length corresponding 526 to this distance. If the distance refers to the static dictionary, or 527 the maximum length is long enough, try only one maximum length. */ 528 max_match_len = BackwardMatchLength(&match); 529 if (len < max_match_len && 530 (is_dictionary_match || max_match_len > max_zopfli_len)) { 531 len = max_match_len; 532 } 533 for (; len <= max_match_len; ++len) { 534 const size_t len_code = 535 is_dictionary_match ? BackwardMatchLengthCode(&match) : len; 536 const uint16_t copycode = GetCopyLengthCode(len_code); 537 const uint16_t cmdcode = CombineLengthCodes(inscode, copycode, 0); 538 const float cost = dist_cost + (float)GetCopyExtra(copycode) + 539 ZopfliCostModelGetCommandCost(model, cmdcode); 540 if (cost < nodes[pos + len].u.cost) { 541 UpdateZopfliNode(nodes, pos, start, len, len_code, dist, 0, cost); 542 result = BROTLI_MAX(size_t, result, len); 543 } 544 } 545 } 546 } 547 } 548 return result; 549 } 550 551 static size_t ComputeShortestPathFromNodes(size_t num_bytes, 552 ZopfliNode* nodes) { 553 size_t index = num_bytes; 554 size_t num_commands = 0; 555 while ((nodes[index].dcode_insert_length & 0x7FFFFFF) == 0 && 556 nodes[index].length == 1) --index; 557 nodes[index].u.next = BROTLI_UINT32_MAX; 558 while (index != 0) { 559 size_t len = ZopfliNodeCommandLength(&nodes[index]); 560 index -= len; 561 nodes[index].u.next = (uint32_t)len; 562 num_commands++; 563 } 564 return num_commands; 565 } 566 567 /* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */ 568 void BrotliZopfliCreateCommands(const size_t num_bytes, 569 const size_t block_start, const ZopfliNode* nodes, int* dist_cache, 570 size_t* last_insert_len, const BrotliEncoderParams* params, 571 Command* commands, size_t* num_literals) { 572 const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); 573 size_t pos = 0; 574 uint32_t offset = nodes[0].u.next; 575 size_t i; 576 size_t gap = 0; 577 for (i = 0; offset != BROTLI_UINT32_MAX; i++) { 578 const ZopfliNode* next = &nodes[pos + offset]; 579 size_t copy_length = ZopfliNodeCopyLength(next); 580 size_t insert_length = next->dcode_insert_length & 0x7FFFFFF; 581 pos += insert_length; 582 offset = next->u.next; 583 if (i == 0) { 584 insert_length += *last_insert_len; 585 *last_insert_len = 0; 586 } 587 { 588 size_t distance = ZopfliNodeCopyDistance(next); 589 size_t len_code = ZopfliNodeLengthCode(next); 590 size_t max_distance = 591 BROTLI_MIN(size_t, block_start + pos, max_backward_limit); 592 BROTLI_BOOL is_dictionary = TO_BROTLI_BOOL(distance > max_distance + gap); 593 size_t dist_code = ZopfliNodeDistanceCode(next); 594 InitCommand(&commands[i], ¶ms->dist, insert_length, 595 copy_length, (int)len_code - (int)copy_length, dist_code); 596 597 if (!is_dictionary && dist_code > 0) { 598 dist_cache[3] = dist_cache[2]; 599 dist_cache[2] = dist_cache[1]; 600 dist_cache[1] = dist_cache[0]; 601 dist_cache[0] = (int)distance; 602 } 603 } 604 605 *num_literals += insert_length; 606 pos += copy_length; 607 } 608 *last_insert_len += num_bytes - pos; 609 } 610 611 static size_t ZopfliIterate(size_t num_bytes, size_t position, 612 const uint8_t* ringbuffer, size_t ringbuffer_mask, 613 const BrotliEncoderParams* params, const size_t gap, const int* dist_cache, 614 const ZopfliCostModel* model, const uint32_t* num_matches, 615 const BackwardMatch* matches, ZopfliNode* nodes) { 616 const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); 617 const size_t max_zopfli_len = MaxZopfliLen(params); 618 StartPosQueue queue; 619 size_t cur_match_pos = 0; 620 size_t i; 621 nodes[0].length = 0; 622 nodes[0].u.cost = 0; 623 InitStartPosQueue(&queue); 624 for (i = 0; i + 3 < num_bytes; i++) { 625 size_t skip = UpdateNodes(num_bytes, position, i, ringbuffer, 626 ringbuffer_mask, params, max_backward_limit, dist_cache, 627 num_matches[i], &matches[cur_match_pos], model, &queue, nodes); 628 if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0; 629 cur_match_pos += num_matches[i]; 630 if (num_matches[i] == 1 && 631 BackwardMatchLength(&matches[cur_match_pos - 1]) > max_zopfli_len) { 632 skip = BROTLI_MAX(size_t, 633 BackwardMatchLength(&matches[cur_match_pos - 1]), skip); 634 } 635 if (skip > 1) { 636 skip--; 637 while (skip) { 638 i++; 639 if (i + 3 >= num_bytes) break; 640 EvaluateNode(position, i, max_backward_limit, gap, 641 dist_cache, model, &queue, nodes); 642 cur_match_pos += num_matches[i]; 643 skip--; 644 } 645 } 646 } 647 return ComputeShortestPathFromNodes(num_bytes, nodes); 648 } 649 650 /* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */ 651 size_t BrotliZopfliComputeShortestPath(MemoryManager* m, size_t num_bytes, 652 size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, 653 const BrotliEncoderParams* params, 654 const int* dist_cache, HasherHandle hasher, ZopfliNode* nodes) { 655 const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); 656 const size_t max_zopfli_len = MaxZopfliLen(params); 657 ZopfliCostModel model; 658 StartPosQueue queue; 659 BackwardMatch matches[2 * (MAX_NUM_MATCHES_H10 + 64)]; 660 const size_t store_end = num_bytes >= StoreLookaheadH10() ? 661 position + num_bytes - StoreLookaheadH10() + 1 : position; 662 size_t i; 663 size_t gap = 0; 664 size_t lz_matches_offset = 0; 665 nodes[0].length = 0; 666 nodes[0].u.cost = 0; 667 InitZopfliCostModel(m, &model, ¶ms->dist, num_bytes); 668 if (BROTLI_IS_OOM(m)) return 0; 669 ZopfliCostModelSetFromLiteralCosts( 670 &model, position, ringbuffer, ringbuffer_mask); 671 InitStartPosQueue(&queue); 672 for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; i++) { 673 const size_t pos = position + i; 674 const size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit); 675 size_t skip; 676 size_t num_matches; 677 num_matches = FindAllMatchesH10(hasher, 678 ¶ms->dictionary, 679 ringbuffer, ringbuffer_mask, pos, num_bytes - i, max_distance, 680 gap, params, &matches[lz_matches_offset]); 681 if (num_matches > 0 && 682 BackwardMatchLength(&matches[num_matches - 1]) > max_zopfli_len) { 683 matches[0] = matches[num_matches - 1]; 684 num_matches = 1; 685 } 686 skip = UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask, 687 params, max_backward_limit, dist_cache, num_matches, matches, &model, 688 &queue, nodes); 689 if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0; 690 if (num_matches == 1 && BackwardMatchLength(&matches[0]) > max_zopfli_len) { 691 skip = BROTLI_MAX(size_t, BackwardMatchLength(&matches[0]), skip); 692 } 693 if (skip > 1) { 694 /* Add the tail of the copy to the hasher. */ 695 StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, BROTLI_MIN( 696 size_t, pos + skip, store_end)); 697 skip--; 698 while (skip) { 699 i++; 700 if (i + HashTypeLengthH10() - 1 >= num_bytes) break; 701 EvaluateNode(position, i, max_backward_limit, gap, 702 dist_cache, &model, &queue, nodes); 703 skip--; 704 } 705 } 706 } 707 CleanupZopfliCostModel(m, &model); 708 return ComputeShortestPathFromNodes(num_bytes, nodes); 709 } 710 711 void BrotliCreateZopfliBackwardReferences(MemoryManager* m, size_t num_bytes, 712 size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, 713 const BrotliEncoderParams* params, 714 HasherHandle hasher, int* dist_cache, size_t* last_insert_len, 715 Command* commands, size_t* num_commands, size_t* num_literals) { 716 ZopfliNode* nodes; 717 nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1); 718 if (BROTLI_IS_OOM(m)) return; 719 BrotliInitZopfliNodes(nodes, num_bytes + 1); 720 *num_commands += BrotliZopfliComputeShortestPath(m, num_bytes, 721 position, ringbuffer, ringbuffer_mask, params, 722 dist_cache, hasher, nodes); 723 if (BROTLI_IS_OOM(m)) return; 724 BrotliZopfliCreateCommands(num_bytes, position, nodes, dist_cache, 725 last_insert_len, params, commands, num_literals); 726 BROTLI_FREE(m, nodes); 727 } 728 729 void BrotliCreateHqZopfliBackwardReferences(MemoryManager* m, size_t num_bytes, 730 size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, 731 const BrotliEncoderParams* params, 732 HasherHandle hasher, int* dist_cache, size_t* last_insert_len, 733 Command* commands, size_t* num_commands, size_t* num_literals) { 734 const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); 735 uint32_t* num_matches = BROTLI_ALLOC(m, uint32_t, num_bytes); 736 size_t matches_size = 4 * num_bytes; 737 const size_t store_end = num_bytes >= StoreLookaheadH10() ? 738 position + num_bytes - StoreLookaheadH10() + 1 : position; 739 size_t cur_match_pos = 0; 740 size_t i; 741 size_t orig_num_literals; 742 size_t orig_last_insert_len; 743 int orig_dist_cache[4]; 744 size_t orig_num_commands; 745 ZopfliCostModel model; 746 ZopfliNode* nodes; 747 BackwardMatch* matches = BROTLI_ALLOC(m, BackwardMatch, matches_size); 748 size_t gap = 0; 749 size_t shadow_matches = 0; 750 if (BROTLI_IS_OOM(m)) return; 751 for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; ++i) { 752 const size_t pos = position + i; 753 size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit); 754 size_t max_length = num_bytes - i; 755 size_t num_found_matches; 756 size_t cur_match_end; 757 size_t j; 758 /* Ensure that we have enough free slots. */ 759 BROTLI_ENSURE_CAPACITY(m, BackwardMatch, matches, matches_size, 760 cur_match_pos + MAX_NUM_MATCHES_H10 + shadow_matches); 761 if (BROTLI_IS_OOM(m)) return; 762 num_found_matches = FindAllMatchesH10(hasher, 763 ¶ms->dictionary, 764 ringbuffer, ringbuffer_mask, pos, max_length, 765 max_distance, gap, params, 766 &matches[cur_match_pos + shadow_matches]); 767 cur_match_end = cur_match_pos + num_found_matches; 768 for (j = cur_match_pos; j + 1 < cur_match_end; ++j) { 769 BROTLI_DCHECK(BackwardMatchLength(&matches[j]) <= 770 BackwardMatchLength(&matches[j + 1])); 771 } 772 num_matches[i] = (uint32_t)num_found_matches; 773 if (num_found_matches > 0) { 774 const size_t match_len = BackwardMatchLength(&matches[cur_match_end - 1]); 775 if (match_len > MAX_ZOPFLI_LEN_QUALITY_11) { 776 const size_t skip = match_len - 1; 777 matches[cur_match_pos++] = matches[cur_match_end - 1]; 778 num_matches[i] = 1; 779 /* Add the tail of the copy to the hasher. */ 780 StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, 781 BROTLI_MIN(size_t, pos + match_len, store_end)); 782 memset(&num_matches[i + 1], 0, skip * sizeof(num_matches[0])); 783 i += skip; 784 } else { 785 cur_match_pos = cur_match_end; 786 } 787 } 788 } 789 orig_num_literals = *num_literals; 790 orig_last_insert_len = *last_insert_len; 791 memcpy(orig_dist_cache, dist_cache, 4 * sizeof(dist_cache[0])); 792 orig_num_commands = *num_commands; 793 nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1); 794 if (BROTLI_IS_OOM(m)) return; 795 InitZopfliCostModel(m, &model, ¶ms->dist, num_bytes); 796 if (BROTLI_IS_OOM(m)) return; 797 for (i = 0; i < 2; i++) { 798 BrotliInitZopfliNodes(nodes, num_bytes + 1); 799 if (i == 0) { 800 ZopfliCostModelSetFromLiteralCosts( 801 &model, position, ringbuffer, ringbuffer_mask); 802 } else { 803 ZopfliCostModelSetFromCommands(&model, position, ringbuffer, 804 ringbuffer_mask, commands, *num_commands - orig_num_commands, 805 orig_last_insert_len); 806 } 807 *num_commands = orig_num_commands; 808 *num_literals = orig_num_literals; 809 *last_insert_len = orig_last_insert_len; 810 memcpy(dist_cache, orig_dist_cache, 4 * sizeof(dist_cache[0])); 811 *num_commands += ZopfliIterate(num_bytes, position, ringbuffer, 812 ringbuffer_mask, params, gap, dist_cache, &model, num_matches, matches, 813 nodes); 814 BrotliZopfliCreateCommands(num_bytes, position, nodes, dist_cache, 815 last_insert_len, params, commands, num_literals); 816 } 817 CleanupZopfliCostModel(m, &model); 818 BROTLI_FREE(m, nodes); 819 BROTLI_FREE(m, matches); 820 BROTLI_FREE(m, num_matches); 821 } 822 823 #if defined(__cplusplus) || defined(c_plusplus) 824 } /* extern "C" */ 825 #endif 826
