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