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) 25 extern "C" { 26 #endif 27 28 static const float kInfinity = 1.7e38f; /* ~= 2 ^ 127 */ 29 30 static const uint32_t kDistanceCacheIndex[] = { 31 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 32 }; 33 static const int kDistanceCacheOffset[] = { 34 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 35 }; 36 37 void 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 47 static BROTLI_INLINE uint32_t ZopfliNodeCopyLength(const ZopfliNode* self) { 48 return self->length & 0xffffff; 49 } 50 51 static BROTLI_INLINE uint32_t ZopfliNodeLengthCode(const ZopfliNode* self) { 52 const uint32_t modifier = self->length >> 24; 53 return ZopfliNodeCopyLength(self) + 9u - modifier; 54 } 55 56 static BROTLI_INLINE uint32_t ZopfliNodeCopyDistance(const ZopfliNode* self) { 57 return self->distance & 0x1ffffff; 58 } 59 60 static 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 67 static BROTLI_INLINE uint32_t ZopfliNodeCommandLength(const ZopfliNode* self) { 68 return ZopfliNodeCopyLength(self) + self->insert_length; 69 } 70 71 /* Histogram based cost model for zopflification. */ 72 typedef 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 82 static 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 89 static void CleanupZopfliCostModel(MemoryManager* m, ZopfliCostModel* self) { 90 BROTLI_FREE(m, self->literal_costs_); 91 } 92 93 static 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 116 static 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 173 static 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 197 static BROTLI_INLINE float ZopfliCostModelGetCommandCost( 198 const ZopfliCostModel* self, uint16_t cmdcode) { 199 return self->cost_cmd_[cmdcode]; 200 } 201 202 static BROTLI_INLINE float ZopfliCostModelGetDistanceCost( 203 const ZopfliCostModel* self, size_t distcode) { 204 return self->cost_dist_[distcode]; 205 } 206 207 static 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 212 static 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". */ 220 static 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 230 typedef 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 */ 238 typedef struct StartPosQueue { 239 PosData q_[8]; 240 size_t idx_; 241 } StartPosQueue; 242 243 static BROTLI_INLINE void InitStartPosQueue(StartPosQueue* self) { 244 self->idx_ = 0; 245 } 246 247 static size_t StartPosQueueSize(const StartPosQueue* self) { 248 return BROTLI_MIN(size_t, self->idx_, 8); 249 } 250 251 static 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 267 static 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. */ 273 static 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". */ 300 static uint32_t ComputeDistanceShortcut(const size_t block_start, 301 const size_t pos, 302 const size_t max_backward, 303 const ZopfliNode* nodes) { 304 const size_t clen = ZopfliNodeCopyLength(&nodes[pos]); 305 const size_t ilen = nodes[pos].insert_length; 306 const size_t dist = ZopfliNodeCopyDistance(&nodes[pos]); 307 /* Since |block_start + pos| is the end position of the command, the copy part 308 starts from |block_start + pos - clen|. Distances that are greater than 309 this or greater than |max_backward| are static dictionary references, and 310 do not update the last distances. Also distance code 0 (last distance) 311 does not update the last distances. */ 312 if (pos == 0) { 313 return 0; 314 } else if (dist + clen <= block_start + pos && 315 dist <= max_backward && 316 ZopfliNodeDistanceCode(&nodes[pos]) > 0) { 317 return (uint32_t)pos; 318 } else { 319 return nodes[pos - clen - ilen].u.shortcut; 320 } 321 } 322 323 /* Fills in dist_cache[0..3] with the last four distances (as defined by 324 Section 4. of the Spec) that would be used at (block_start + pos) if we 325 used the shortest path of commands from block_start, computed from 326 nodes[0..pos]. The last four distances at block_start are in 327 starting_dist_cache[0..3]. 328 REQUIRES: nodes[pos].cost < kInfinity 329 REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */ 330 static void ComputeDistanceCache(const size_t pos, 331 const int* starting_dist_cache, 332 const ZopfliNode* nodes, 333 int* dist_cache) { 334 int idx = 0; 335 size_t p = nodes[pos].u.shortcut; 336 while (idx < 4 && p > 0) { 337 const size_t ilen = nodes[p].insert_length; 338 const size_t clen = ZopfliNodeCopyLength(&nodes[p]); 339 const size_t dist = ZopfliNodeCopyDistance(&nodes[p]); 340 dist_cache[idx++] = (int)dist; 341 /* Because of prerequisite, p >= clen + ilen >= 2. */ 342 p = nodes[p - clen - ilen].u.shortcut; 343 } 344 for (; idx < 4; ++idx) { 345 dist_cache[idx] = *starting_dist_cache++; 346 } 347 } 348 349 /* Maintains "ZopfliNode array invariant" and pushes node to the queue, if it 350 is eligible. */ 351 static void EvaluateNode( 352 const size_t block_start, const size_t pos, const size_t max_backward_limit, 353 const int* starting_dist_cache, const ZopfliCostModel* model, 354 StartPosQueue* queue, ZopfliNode* nodes) { 355 /* Save cost, because ComputeDistanceCache invalidates it. */ 356 float node_cost = nodes[pos].u.cost; 357 nodes[pos].u.shortcut = ComputeDistanceShortcut( 358 block_start, pos, max_backward_limit, nodes); 359 if (node_cost <= ZopfliCostModelGetLiteralCosts(model, 0, pos)) { 360 PosData posdata; 361 posdata.pos = pos; 362 posdata.cost = node_cost; 363 posdata.costdiff = node_cost - 364 ZopfliCostModelGetLiteralCosts(model, 0, pos); 365 ComputeDistanceCache( 366 pos, starting_dist_cache, nodes, posdata.distance_cache); 367 StartPosQueuePush(queue, &posdata); 368 } 369 } 370 371 /* Returns longest copy length. */ 372 static size_t UpdateNodes( 373 const size_t num_bytes, const size_t block_start, const size_t pos, 374 const uint8_t* ringbuffer, const size_t ringbuffer_mask, 375 const BrotliEncoderParams* params, const size_t max_backward_limit, 376 const int* starting_dist_cache, const size_t num_matches, 377 const BackwardMatch* matches, const ZopfliCostModel* model, 378 StartPosQueue* queue, ZopfliNode* nodes) { 379 const size_t cur_ix = block_start + pos; 380 const size_t cur_ix_masked = cur_ix & ringbuffer_mask; 381 const size_t max_distance = BROTLI_MIN(size_t, cur_ix, max_backward_limit); 382 const size_t max_len = num_bytes - pos; 383 const size_t max_zopfli_len = MaxZopfliLen(params); 384 const size_t max_iters = MaxZopfliCandidates(params); 385 size_t min_len; 386 size_t result = 0; 387 size_t k; 388 389 EvaluateNode(block_start, pos, max_backward_limit, starting_dist_cache, model, 390 queue, nodes); 391 392 { 393 const PosData* posdata = StartPosQueueAt(queue, 0); 394 float min_cost = (posdata->cost + ZopfliCostModelGetMinCostCmd(model) + 395 ZopfliCostModelGetLiteralCosts(model, posdata->pos, pos)); 396 min_len = ComputeMinimumCopyLength(min_cost, nodes, num_bytes, pos); 397 } 398 399 /* Go over the command starting positions in order of increasing cost 400 difference. */ 401 for (k = 0; k < max_iters && k < StartPosQueueSize(queue); ++k) { 402 const PosData* posdata = StartPosQueueAt(queue, k); 403 const size_t start = posdata->pos; 404 const uint16_t inscode = GetInsertLengthCode(pos - start); 405 const float start_costdiff = posdata->costdiff; 406 const float base_cost = start_costdiff + (float)GetInsertExtra(inscode) + 407 ZopfliCostModelGetLiteralCosts(model, 0, pos); 408 409 /* Look for last distance matches using the distance cache from this 410 starting position. */ 411 size_t best_len = min_len - 1; 412 size_t j = 0; 413 for (; j < BROTLI_NUM_DISTANCE_SHORT_CODES && best_len < max_len; ++j) { 414 const size_t idx = kDistanceCacheIndex[j]; 415 const size_t backward = 416 (size_t)(posdata->distance_cache[idx] + kDistanceCacheOffset[j]); 417 size_t prev_ix = cur_ix - backward; 418 if (prev_ix >= cur_ix) { 419 continue; 420 } 421 if (BROTLI_PREDICT_FALSE(backward > max_distance)) { 422 continue; 423 } 424 prev_ix &= ringbuffer_mask; 425 426 if (cur_ix_masked + best_len > ringbuffer_mask || 427 prev_ix + best_len > ringbuffer_mask || 428 ringbuffer[cur_ix_masked + best_len] != 429 ringbuffer[prev_ix + best_len]) { 430 continue; 431 } 432 { 433 const size_t len = 434 FindMatchLengthWithLimit(&ringbuffer[prev_ix], 435 &ringbuffer[cur_ix_masked], 436 max_len); 437 const float dist_cost = base_cost + 438 ZopfliCostModelGetDistanceCost(model, j); 439 size_t l; 440 for (l = best_len + 1; l <= len; ++l) { 441 const uint16_t copycode = GetCopyLengthCode(l); 442 const uint16_t cmdcode = 443 CombineLengthCodes(inscode, copycode, j == 0); 444 const float cost = (cmdcode < 128 ? base_cost : dist_cost) + 445 (float)GetCopyExtra(copycode) + 446 ZopfliCostModelGetCommandCost(model, cmdcode); 447 if (cost < nodes[pos + l].u.cost) { 448 UpdateZopfliNode(nodes, pos, start, l, l, backward, j + 1, cost); 449 result = BROTLI_MAX(size_t, result, l); 450 } 451 best_len = l; 452 } 453 } 454 } 455 456 /* At higher iterations look only for new last distance matches, since 457 looking only for new command start positions with the same distances 458 does not help much. */ 459 if (k >= 2) continue; 460 461 { 462 /* Loop through all possible copy lengths at this position. */ 463 size_t len = min_len; 464 for (j = 0; j < num_matches; ++j) { 465 BackwardMatch match = matches[j]; 466 size_t dist = match.distance; 467 BROTLI_BOOL is_dictionary_match = TO_BROTLI_BOOL(dist > max_distance); 468 /* We already tried all possible last distance matches, so we can use 469 normal distance code here. */ 470 size_t dist_code = dist + BROTLI_NUM_DISTANCE_SHORT_CODES - 1; 471 uint16_t dist_symbol; 472 uint32_t distextra; 473 uint32_t distnumextra; 474 float dist_cost; 475 size_t max_match_len; 476 PrefixEncodeCopyDistance(dist_code, 0, 0, &dist_symbol, &distextra); 477 distnumextra = distextra >> 24; 478 dist_cost = base_cost + (float)distnumextra + 479 ZopfliCostModelGetDistanceCost(model, dist_symbol); 480 481 /* Try all copy lengths up until the maximum copy length corresponding 482 to this distance. If the distance refers to the static dictionary, or 483 the maximum length is long enough, try only one maximum length. */ 484 max_match_len = BackwardMatchLength(&match); 485 if (len < max_match_len && 486 (is_dictionary_match || max_match_len > max_zopfli_len)) { 487 len = max_match_len; 488 } 489 for (; len <= max_match_len; ++len) { 490 const size_t len_code = 491 is_dictionary_match ? BackwardMatchLengthCode(&match) : len; 492 const uint16_t copycode = GetCopyLengthCode(len_code); 493 const uint16_t cmdcode = CombineLengthCodes(inscode, copycode, 0); 494 const float cost = dist_cost + (float)GetCopyExtra(copycode) + 495 ZopfliCostModelGetCommandCost(model, cmdcode); 496 if (cost < nodes[pos + len].u.cost) { 497 UpdateZopfliNode(nodes, pos, start, len, len_code, dist, 0, cost); 498 result = BROTLI_MAX(size_t, result, len); 499 } 500 } 501 } 502 } 503 } 504 return result; 505 } 506 507 static size_t ComputeShortestPathFromNodes(size_t num_bytes, 508 ZopfliNode* nodes) { 509 size_t index = num_bytes; 510 size_t num_commands = 0; 511 while (nodes[index].insert_length == 0 && nodes[index].length == 1) --index; 512 nodes[index].u.next = BROTLI_UINT32_MAX; 513 while (index != 0) { 514 size_t len = ZopfliNodeCommandLength(&nodes[index]); 515 index -= len; 516 nodes[index].u.next = (uint32_t)len; 517 num_commands++; 518 } 519 return num_commands; 520 } 521 522 /* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */ 523 void BrotliZopfliCreateCommands(const size_t num_bytes, 524 const size_t block_start, 525 const size_t max_backward_limit, 526 const ZopfliNode* nodes, 527 int* dist_cache, 528 size_t* last_insert_len, 529 Command* commands, 530 size_t* num_literals) { 531 size_t pos = 0; 532 uint32_t offset = nodes[0].u.next; 533 size_t i; 534 for (i = 0; offset != BROTLI_UINT32_MAX; i++) { 535 const ZopfliNode* next = &nodes[pos + offset]; 536 size_t copy_length = ZopfliNodeCopyLength(next); 537 size_t insert_length = next->insert_length; 538 pos += insert_length; 539 offset = next->u.next; 540 if (i == 0) { 541 insert_length += *last_insert_len; 542 *last_insert_len = 0; 543 } 544 { 545 size_t distance = ZopfliNodeCopyDistance(next); 546 size_t len_code = ZopfliNodeLengthCode(next); 547 size_t max_distance = 548 BROTLI_MIN(size_t, block_start + pos, max_backward_limit); 549 BROTLI_BOOL is_dictionary = TO_BROTLI_BOOL(distance > max_distance); 550 size_t dist_code = ZopfliNodeDistanceCode(next); 551 552 InitCommand( 553 &commands[i], insert_length, copy_length, len_code, dist_code); 554 555 if (!is_dictionary && dist_code > 0) { 556 dist_cache[3] = dist_cache[2]; 557 dist_cache[2] = dist_cache[1]; 558 dist_cache[1] = dist_cache[0]; 559 dist_cache[0] = (int)distance; 560 } 561 } 562 563 *num_literals += insert_length; 564 pos += copy_length; 565 } 566 *last_insert_len += num_bytes - pos; 567 } 568 569 static size_t ZopfliIterate(size_t num_bytes, 570 size_t position, 571 const uint8_t* ringbuffer, 572 size_t ringbuffer_mask, 573 const BrotliEncoderParams* params, 574 const size_t max_backward_limit, 575 const int* dist_cache, 576 const ZopfliCostModel* model, 577 const uint32_t* num_matches, 578 const BackwardMatch* matches, 579 ZopfliNode* nodes) { 580 const size_t max_zopfli_len = MaxZopfliLen(params); 581 StartPosQueue queue; 582 size_t cur_match_pos = 0; 583 size_t i; 584 nodes[0].length = 0; 585 nodes[0].u.cost = 0; 586 InitStartPosQueue(&queue); 587 for (i = 0; i + 3 < num_bytes; i++) { 588 size_t skip = UpdateNodes(num_bytes, position, i, ringbuffer, 589 ringbuffer_mask, params, max_backward_limit, dist_cache, 590 num_matches[i], &matches[cur_match_pos], model, &queue, nodes); 591 if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0; 592 cur_match_pos += num_matches[i]; 593 if (num_matches[i] == 1 && 594 BackwardMatchLength(&matches[cur_match_pos - 1]) > max_zopfli_len) { 595 skip = BROTLI_MAX(size_t, 596 BackwardMatchLength(&matches[cur_match_pos - 1]), skip); 597 } 598 if (skip > 1) { 599 skip--; 600 while (skip) { 601 i++; 602 if (i + 3 >= num_bytes) break; 603 EvaluateNode( 604 position, i, max_backward_limit, dist_cache, model, &queue, nodes); 605 cur_match_pos += num_matches[i]; 606 skip--; 607 } 608 } 609 } 610 return ComputeShortestPathFromNodes(num_bytes, nodes); 611 } 612 613 /* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */ 614 size_t BrotliZopfliComputeShortestPath(MemoryManager* m, 615 const BrotliDictionary* dictionary, 616 size_t num_bytes, 617 size_t position, 618 const uint8_t* ringbuffer, 619 size_t ringbuffer_mask, 620 const BrotliEncoderParams* params, 621 const size_t max_backward_limit, 622 const int* dist_cache, 623 HasherHandle hasher, 624 ZopfliNode* nodes) { 625 const size_t max_zopfli_len = MaxZopfliLen(params); 626 ZopfliCostModel model; 627 StartPosQueue queue; 628 BackwardMatch matches[MAX_NUM_MATCHES_H10]; 629 const size_t store_end = num_bytes >= StoreLookaheadH10() ? 630 position + num_bytes - StoreLookaheadH10() + 1 : position; 631 size_t i; 632 nodes[0].length = 0; 633 nodes[0].u.cost = 0; 634 InitZopfliCostModel(m, &model, num_bytes); 635 if (BROTLI_IS_OOM(m)) return 0; 636 ZopfliCostModelSetFromLiteralCosts( 637 &model, position, ringbuffer, ringbuffer_mask); 638 InitStartPosQueue(&queue); 639 for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; i++) { 640 const size_t pos = position + i; 641 const size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit); 642 size_t num_matches = FindAllMatchesH10(hasher, dictionary, ringbuffer, 643 ringbuffer_mask, pos, num_bytes - i, max_distance, params, matches); 644 size_t skip; 645 if (num_matches > 0 && 646 BackwardMatchLength(&matches[num_matches - 1]) > max_zopfli_len) { 647 matches[0] = matches[num_matches - 1]; 648 num_matches = 1; 649 } 650 skip = UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask, 651 params, max_backward_limit, dist_cache, num_matches, matches, &model, 652 &queue, nodes); 653 if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0; 654 if (num_matches == 1 && BackwardMatchLength(&matches[0]) > max_zopfli_len) { 655 skip = BROTLI_MAX(size_t, BackwardMatchLength(&matches[0]), skip); 656 } 657 if (skip > 1) { 658 /* Add the tail of the copy to the hasher. */ 659 StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, BROTLI_MIN( 660 size_t, pos + skip, store_end)); 661 skip--; 662 while (skip) { 663 i++; 664 if (i + HashTypeLengthH10() - 1 >= num_bytes) break; 665 EvaluateNode( 666 position, i, max_backward_limit, dist_cache, &model, &queue, nodes); 667 skip--; 668 } 669 } 670 } 671 CleanupZopfliCostModel(m, &model); 672 return ComputeShortestPathFromNodes(num_bytes, nodes); 673 } 674 675 void BrotliCreateZopfliBackwardReferences( 676 MemoryManager* m, const BrotliDictionary* dictionary, size_t num_bytes, 677 size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, 678 const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache, 679 size_t* last_insert_len, Command* commands, size_t* num_commands, 680 size_t* num_literals) { 681 const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); 682 ZopfliNode* nodes; 683 nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1); 684 if (BROTLI_IS_OOM(m)) return; 685 BrotliInitZopfliNodes(nodes, num_bytes + 1); 686 *num_commands += BrotliZopfliComputeShortestPath(m, dictionary, num_bytes, 687 position, ringbuffer, ringbuffer_mask, params, max_backward_limit, 688 dist_cache, hasher, nodes); 689 if (BROTLI_IS_OOM(m)) return; 690 BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit, nodes, 691 dist_cache, last_insert_len, commands, num_literals); 692 BROTLI_FREE(m, nodes); 693 } 694 695 void BrotliCreateHqZopfliBackwardReferences( 696 MemoryManager* m, const BrotliDictionary* dictionary, size_t num_bytes, 697 size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, 698 const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache, 699 size_t* last_insert_len, Command* commands, size_t* num_commands, 700 size_t* num_literals) { 701 const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin); 702 uint32_t* num_matches = BROTLI_ALLOC(m, uint32_t, num_bytes); 703 size_t matches_size = 4 * num_bytes; 704 const size_t store_end = num_bytes >= StoreLookaheadH10() ? 705 position + num_bytes - StoreLookaheadH10() + 1 : position; 706 size_t cur_match_pos = 0; 707 size_t i; 708 size_t orig_num_literals; 709 size_t orig_last_insert_len; 710 int orig_dist_cache[4]; 711 size_t orig_num_commands; 712 ZopfliCostModel model; 713 ZopfliNode* nodes; 714 BackwardMatch* matches = BROTLI_ALLOC(m, BackwardMatch, matches_size); 715 if (BROTLI_IS_OOM(m)) return; 716 for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; ++i) { 717 const size_t pos = position + i; 718 size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit); 719 size_t max_length = num_bytes - i; 720 size_t num_found_matches; 721 size_t cur_match_end; 722 size_t j; 723 /* Ensure that we have enough free slots. */ 724 BROTLI_ENSURE_CAPACITY(m, BackwardMatch, matches, matches_size, 725 cur_match_pos + MAX_NUM_MATCHES_H10); 726 if (BROTLI_IS_OOM(m)) return; 727 num_found_matches = FindAllMatchesH10(hasher, dictionary, ringbuffer, 728 ringbuffer_mask, pos, max_length, max_distance, params, 729 &matches[cur_match_pos]); 730 cur_match_end = cur_match_pos + num_found_matches; 731 for (j = cur_match_pos; j + 1 < cur_match_end; ++j) { 732 assert(BackwardMatchLength(&matches[j]) < 733 BackwardMatchLength(&matches[j + 1])); 734 assert(matches[j].distance > max_distance || 735 matches[j].distance <= matches[j + 1].distance); 736 } 737 num_matches[i] = (uint32_t)num_found_matches; 738 if (num_found_matches > 0) { 739 const size_t match_len = BackwardMatchLength(&matches[cur_match_end - 1]); 740 if (match_len > MAX_ZOPFLI_LEN_QUALITY_11) { 741 const size_t skip = match_len - 1; 742 matches[cur_match_pos++] = matches[cur_match_end - 1]; 743 num_matches[i] = 1; 744 /* Add the tail of the copy to the hasher. */ 745 StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, 746 BROTLI_MIN(size_t, pos + match_len, store_end)); 747 memset(&num_matches[i + 1], 0, skip * sizeof(num_matches[0])); 748 i += skip; 749 } else { 750 cur_match_pos = cur_match_end; 751 } 752 } 753 } 754 orig_num_literals = *num_literals; 755 orig_last_insert_len = *last_insert_len; 756 memcpy(orig_dist_cache, dist_cache, 4 * sizeof(dist_cache[0])); 757 orig_num_commands = *num_commands; 758 nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1); 759 if (BROTLI_IS_OOM(m)) return; 760 InitZopfliCostModel(m, &model, num_bytes); 761 if (BROTLI_IS_OOM(m)) return; 762 for (i = 0; i < 2; i++) { 763 BrotliInitZopfliNodes(nodes, num_bytes + 1); 764 if (i == 0) { 765 ZopfliCostModelSetFromLiteralCosts( 766 &model, position, ringbuffer, ringbuffer_mask); 767 } else { 768 ZopfliCostModelSetFromCommands(&model, position, ringbuffer, 769 ringbuffer_mask, commands, *num_commands - orig_num_commands, 770 orig_last_insert_len); 771 } 772 *num_commands = orig_num_commands; 773 *num_literals = orig_num_literals; 774 *last_insert_len = orig_last_insert_len; 775 memcpy(dist_cache, orig_dist_cache, 4 * sizeof(dist_cache[0])); 776 *num_commands += ZopfliIterate(num_bytes, position, ringbuffer, 777 ringbuffer_mask, params, max_backward_limit, dist_cache, 778 &model, num_matches, matches, nodes); 779 BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit, 780 nodes, dist_cache, last_insert_len, commands, num_literals); 781 } 782 CleanupZopfliCostModel(m, &model); 783 BROTLI_FREE(m, nodes); 784 BROTLI_FREE(m, matches); 785 BROTLI_FREE(m, num_matches); 786 } 787 788 #if defined(__cplusplus) || defined(c_plusplus) 789 } /* extern "C" */ 790 #endif 791
