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