+++ /dev/null
-/* Copyright 2013 Google Inc. All Rights Reserved.\r
-\r
- Distributed under MIT license.\r
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
-*/\r
-\r
-/* Function to find backward reference copies. */\r
-\r
-#include "./backward_references_hq.h"\r
-\r
-#include <string.h> /* memcpy, memset */\r
-\r
-#include "../common/constants.h"\r
-#include "../common/platform.h"\r
-#include <brotli/types.h>\r
-#include "./command.h"\r
-#include "./fast_log.h"\r
-#include "./find_match_length.h"\r
-#include "./literal_cost.h"\r
-#include "./memory.h"\r
-#include "./params.h"\r
-#include "./prefix.h"\r
-#include "./quality.h"\r
-\r
-#if defined(__cplusplus) || defined(c_plusplus)\r
-extern "C" {\r
-#endif\r
-\r
-#define BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE 544\r
-\r
-static const float kInfinity = 1.7e38f; /* ~= 2 ^ 127 */\r
-\r
-static const uint32_t kDistanceCacheIndex[] = {\r
- 0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,\r
-};\r
-static const int kDistanceCacheOffset[] = {\r
- 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3\r
-};\r
-\r
-void BrotliInitZopfliNodes(ZopfliNode* array, size_t length) {\r
- ZopfliNode stub;\r
- size_t i;\r
- stub.length = 1;\r
- stub.distance = 0;\r
- stub.dcode_insert_length = 0;\r
- stub.u.cost = kInfinity;\r
- for (i = 0; i < length; ++i) array[i] = stub;\r
-}\r
-\r
-static BROTLI_INLINE uint32_t ZopfliNodeCopyLength(const ZopfliNode* self) {\r
- return self->length & 0x1FFFFFF;\r
-}\r
-\r
-static BROTLI_INLINE uint32_t ZopfliNodeLengthCode(const ZopfliNode* self) {\r
- const uint32_t modifier = self->length >> 25;\r
- return ZopfliNodeCopyLength(self) + 9u - modifier;\r
-}\r
-\r
-static BROTLI_INLINE uint32_t ZopfliNodeCopyDistance(const ZopfliNode* self) {\r
- return self->distance;\r
-}\r
-\r
-static BROTLI_INLINE uint32_t ZopfliNodeDistanceCode(const ZopfliNode* self) {\r
- const uint32_t short_code = self->dcode_insert_length >> 27;\r
- return short_code == 0 ?\r
- ZopfliNodeCopyDistance(self) + BROTLI_NUM_DISTANCE_SHORT_CODES - 1 :\r
- short_code - 1;\r
-}\r
-\r
-static BROTLI_INLINE uint32_t ZopfliNodeCommandLength(const ZopfliNode* self) {\r
- return ZopfliNodeCopyLength(self) + (self->dcode_insert_length & 0x7FFFFFF);\r
-}\r
-\r
-/* Histogram based cost model for zopflification. */\r
-typedef struct ZopfliCostModel {\r
- /* The insert and copy length symbols. */\r
- float cost_cmd_[BROTLI_NUM_COMMAND_SYMBOLS];\r
- float* cost_dist_;\r
- uint32_t distance_histogram_size;\r
- /* Cumulative costs of literals per position in the stream. */\r
- float* literal_costs_;\r
- float min_cost_cmd_;\r
- size_t num_bytes_;\r
-} ZopfliCostModel;\r
-\r
-static void InitZopfliCostModel(\r
- MemoryManager* m, ZopfliCostModel* self, const BrotliDistanceParams* dist,\r
- size_t num_bytes) {\r
- uint32_t distance_histogram_size = dist->alphabet_size;\r
- if (distance_histogram_size > BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE) {\r
- distance_histogram_size = BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE;\r
- }\r
- self->num_bytes_ = num_bytes;\r
- self->literal_costs_ = BROTLI_ALLOC(m, float, num_bytes + 2);\r
- self->cost_dist_ = BROTLI_ALLOC(m, float, dist->alphabet_size);\r
- self->distance_histogram_size = distance_histogram_size;\r
- if (BROTLI_IS_OOM(m)) return;\r
-}\r
-\r
-static void CleanupZopfliCostModel(MemoryManager* m, ZopfliCostModel* self) {\r
- BROTLI_FREE(m, self->literal_costs_);\r
- BROTLI_FREE(m, self->cost_dist_);\r
-}\r
-\r
-static void SetCost(const uint32_t* histogram, size_t histogram_size,\r
- BROTLI_BOOL literal_histogram, float* cost) {\r
- size_t sum = 0;\r
- size_t missing_symbol_sum;\r
- float log2sum;\r
- float missing_symbol_cost;\r
- size_t i;\r
- for (i = 0; i < histogram_size; i++) {\r
- sum += histogram[i];\r
- }\r
- log2sum = (float)FastLog2(sum);\r
- missing_symbol_sum = sum;\r
- if (!literal_histogram) {\r
- for (i = 0; i < histogram_size; i++) {\r
- if (histogram[i] == 0) missing_symbol_sum++;\r
- }\r
- }\r
- missing_symbol_cost = (float)FastLog2(missing_symbol_sum) + 2;\r
- for (i = 0; i < histogram_size; i++) {\r
- if (histogram[i] == 0) {\r
- cost[i] = missing_symbol_cost;\r
- continue;\r
- }\r
-\r
- /* Shannon bits for this symbol. */\r
- cost[i] = log2sum - (float)FastLog2(histogram[i]);\r
-\r
- /* Cannot be coded with less than 1 bit */\r
- if (cost[i] < 1) cost[i] = 1;\r
- }\r
-}\r
-\r
-static void ZopfliCostModelSetFromCommands(ZopfliCostModel* self,\r
- size_t position,\r
- const uint8_t* ringbuffer,\r
- size_t ringbuffer_mask,\r
- const Command* commands,\r
- size_t num_commands,\r
- size_t last_insert_len) {\r
- uint32_t histogram_literal[BROTLI_NUM_LITERAL_SYMBOLS];\r
- uint32_t histogram_cmd[BROTLI_NUM_COMMAND_SYMBOLS];\r
- uint32_t histogram_dist[BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE];\r
- float cost_literal[BROTLI_NUM_LITERAL_SYMBOLS];\r
- size_t pos = position - last_insert_len;\r
- float min_cost_cmd = kInfinity;\r
- size_t i;\r
- float* cost_cmd = self->cost_cmd_;\r
-\r
- memset(histogram_literal, 0, sizeof(histogram_literal));\r
- memset(histogram_cmd, 0, sizeof(histogram_cmd));\r
- memset(histogram_dist, 0, sizeof(histogram_dist));\r
-\r
- for (i = 0; i < num_commands; i++) {\r
- size_t inslength = commands[i].insert_len_;\r
- size_t copylength = CommandCopyLen(&commands[i]);\r
- size_t distcode = commands[i].dist_prefix_ & 0x3FF;\r
- size_t cmdcode = commands[i].cmd_prefix_;\r
- size_t j;\r
-\r
- histogram_cmd[cmdcode]++;\r
- if (cmdcode >= 128) histogram_dist[distcode]++;\r
-\r
- for (j = 0; j < inslength; j++) {\r
- histogram_literal[ringbuffer[(pos + j) & ringbuffer_mask]]++;\r
- }\r
-\r
- pos += inslength + copylength;\r
- }\r
-\r
- SetCost(histogram_literal, BROTLI_NUM_LITERAL_SYMBOLS, BROTLI_TRUE,\r
- cost_literal);\r
- SetCost(histogram_cmd, BROTLI_NUM_COMMAND_SYMBOLS, BROTLI_FALSE,\r
- cost_cmd);\r
- SetCost(histogram_dist, self->distance_histogram_size, BROTLI_FALSE,\r
- self->cost_dist_);\r
-\r
- for (i = 0; i < BROTLI_NUM_COMMAND_SYMBOLS; ++i) {\r
- min_cost_cmd = BROTLI_MIN(float, min_cost_cmd, cost_cmd[i]);\r
- }\r
- self->min_cost_cmd_ = min_cost_cmd;\r
-\r
- {\r
- float* literal_costs = self->literal_costs_;\r
- float literal_carry = 0.0;\r
- size_t num_bytes = self->num_bytes_;\r
- literal_costs[0] = 0.0;\r
- for (i = 0; i < num_bytes; ++i) {\r
- literal_carry +=\r
- cost_literal[ringbuffer[(position + i) & ringbuffer_mask]];\r
- literal_costs[i + 1] = literal_costs[i] + literal_carry;\r
- literal_carry -= literal_costs[i + 1] - literal_costs[i];\r
- }\r
- }\r
-}\r
-\r
-static void ZopfliCostModelSetFromLiteralCosts(ZopfliCostModel* self,\r
- size_t position,\r
- const uint8_t* ringbuffer,\r
- size_t ringbuffer_mask) {\r
- float* literal_costs = self->literal_costs_;\r
- float literal_carry = 0.0;\r
- float* cost_dist = self->cost_dist_;\r
- float* cost_cmd = self->cost_cmd_;\r
- size_t num_bytes = self->num_bytes_;\r
- size_t i;\r
- BrotliEstimateBitCostsForLiterals(position, num_bytes, ringbuffer_mask,\r
- ringbuffer, &literal_costs[1]);\r
- literal_costs[0] = 0.0;\r
- for (i = 0; i < num_bytes; ++i) {\r
- literal_carry += literal_costs[i + 1];\r
- literal_costs[i + 1] = literal_costs[i] + literal_carry;\r
- literal_carry -= literal_costs[i + 1] - literal_costs[i];\r
- }\r
- for (i = 0; i < BROTLI_NUM_COMMAND_SYMBOLS; ++i) {\r
- cost_cmd[i] = (float)FastLog2(11 + (uint32_t)i);\r
- }\r
- for (i = 0; i < self->distance_histogram_size; ++i) {\r
- cost_dist[i] = (float)FastLog2(20 + (uint32_t)i);\r
- }\r
- self->min_cost_cmd_ = (float)FastLog2(11);\r
-}\r
-\r
-static BROTLI_INLINE float ZopfliCostModelGetCommandCost(\r
- const ZopfliCostModel* self, uint16_t cmdcode) {\r
- return self->cost_cmd_[cmdcode];\r
-}\r
-\r
-static BROTLI_INLINE float ZopfliCostModelGetDistanceCost(\r
- const ZopfliCostModel* self, size_t distcode) {\r
- return self->cost_dist_[distcode];\r
-}\r
-\r
-static BROTLI_INLINE float ZopfliCostModelGetLiteralCosts(\r
- const ZopfliCostModel* self, size_t from, size_t to) {\r
- return self->literal_costs_[to] - self->literal_costs_[from];\r
-}\r
-\r
-static BROTLI_INLINE float ZopfliCostModelGetMinCostCmd(\r
- const ZopfliCostModel* self) {\r
- return self->min_cost_cmd_;\r
-}\r
-\r
-/* REQUIRES: len >= 2, start_pos <= pos */\r
-/* REQUIRES: cost < kInfinity, nodes[start_pos].cost < kInfinity */\r
-/* Maintains the "ZopfliNode array invariant". */\r
-static BROTLI_INLINE void UpdateZopfliNode(ZopfliNode* nodes, size_t pos,\r
- size_t start_pos, size_t len, size_t len_code, size_t dist,\r
- size_t short_code, float cost) {\r
- ZopfliNode* next = &nodes[pos + len];\r
- next->length = (uint32_t)(len | ((len + 9u - len_code) << 25));\r
- next->distance = (uint32_t)dist;\r
- next->dcode_insert_length = (uint32_t)(\r
- (short_code << 27) | (pos - start_pos));\r
- next->u.cost = cost;\r
-}\r
-\r
-typedef struct PosData {\r
- size_t pos;\r
- int distance_cache[4];\r
- float costdiff;\r
- float cost;\r
-} PosData;\r
-\r
-/* Maintains the smallest 8 cost difference together with their positions */\r
-typedef struct StartPosQueue {\r
- PosData q_[8];\r
- size_t idx_;\r
-} StartPosQueue;\r
-\r
-static BROTLI_INLINE void InitStartPosQueue(StartPosQueue* self) {\r
- self->idx_ = 0;\r
-}\r
-\r
-static size_t StartPosQueueSize(const StartPosQueue* self) {\r
- return BROTLI_MIN(size_t, self->idx_, 8);\r
-}\r
-\r
-static void StartPosQueuePush(StartPosQueue* self, const PosData* posdata) {\r
- size_t offset = ~(self->idx_++) & 7;\r
- size_t len = StartPosQueueSize(self);\r
- size_t i;\r
- PosData* q = self->q_;\r
- q[offset] = *posdata;\r
- /* Restore the sorted order. In the list of |len| items at most |len - 1|\r
- adjacent element comparisons / swaps are required. */\r
- for (i = 1; i < len; ++i) {\r
- if (q[offset & 7].costdiff > q[(offset + 1) & 7].costdiff) {\r
- BROTLI_SWAP(PosData, q, offset & 7, (offset + 1) & 7);\r
- }\r
- ++offset;\r
- }\r
-}\r
-\r
-static const PosData* StartPosQueueAt(const StartPosQueue* self, size_t k) {\r
- return &self->q_[(k - self->idx_) & 7];\r
-}\r
-\r
-/* Returns the minimum possible copy length that can improve the cost of any */\r
-/* future position. */\r
-static size_t ComputeMinimumCopyLength(const float start_cost,\r
- const ZopfliNode* nodes,\r
- const size_t num_bytes,\r
- const size_t pos) {\r
- /* Compute the minimum possible cost of reaching any future position. */\r
- float min_cost = start_cost;\r
- size_t len = 2;\r
- size_t next_len_bucket = 4;\r
- size_t next_len_offset = 10;\r
- while (pos + len <= num_bytes && nodes[pos + len].u.cost <= min_cost) {\r
- /* We already reached (pos + len) with no more cost than the minimum\r
- possible cost of reaching anything from this pos, so there is no point in\r
- looking for lengths <= len. */\r
- ++len;\r
- if (len == next_len_offset) {\r
- /* We reached the next copy length code bucket, so we add one more\r
- extra bit to the minimum cost. */\r
- min_cost += 1.0f;\r
- next_len_offset += next_len_bucket;\r
- next_len_bucket *= 2;\r
- }\r
- }\r
- return len;\r
-}\r
-\r
-/* REQUIRES: nodes[pos].cost < kInfinity\r
- REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */\r
-static uint32_t ComputeDistanceShortcut(const size_t block_start,\r
- const size_t pos,\r
- const size_t max_backward,\r
- const size_t gap,\r
- const ZopfliNode* nodes) {\r
- const size_t clen = ZopfliNodeCopyLength(&nodes[pos]);\r
- const size_t ilen = nodes[pos].dcode_insert_length & 0x7FFFFFF;\r
- const size_t dist = ZopfliNodeCopyDistance(&nodes[pos]);\r
- /* Since |block_start + pos| is the end position of the command, the copy part\r
- starts from |block_start + pos - clen|. Distances that are greater than\r
- this or greater than |max_backward| are static dictionary references, and\r
- do not update the last distances. Also distance code 0 (last distance)\r
- does not update the last distances. */\r
- if (pos == 0) {\r
- return 0;\r
- } else if (dist + clen <= block_start + pos + gap &&\r
- dist <= max_backward + gap &&\r
- ZopfliNodeDistanceCode(&nodes[pos]) > 0) {\r
- return (uint32_t)pos;\r
- } else {\r
- return nodes[pos - clen - ilen].u.shortcut;\r
- }\r
-}\r
-\r
-/* Fills in dist_cache[0..3] with the last four distances (as defined by\r
- Section 4. of the Spec) that would be used at (block_start + pos) if we\r
- used the shortest path of commands from block_start, computed from\r
- nodes[0..pos]. The last four distances at block_start are in\r
- starting_dist_cache[0..3].\r
- REQUIRES: nodes[pos].cost < kInfinity\r
- REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */\r
-static void ComputeDistanceCache(const size_t pos,\r
- const int* starting_dist_cache,\r
- const ZopfliNode* nodes,\r
- int* dist_cache) {\r
- int idx = 0;\r
- size_t p = nodes[pos].u.shortcut;\r
- while (idx < 4 && p > 0) {\r
- const size_t ilen = nodes[p].dcode_insert_length & 0x7FFFFFF;\r
- const size_t clen = ZopfliNodeCopyLength(&nodes[p]);\r
- const size_t dist = ZopfliNodeCopyDistance(&nodes[p]);\r
- dist_cache[idx++] = (int)dist;\r
- /* Because of prerequisite, p >= clen + ilen >= 2. */\r
- p = nodes[p - clen - ilen].u.shortcut;\r
- }\r
- for (; idx < 4; ++idx) {\r
- dist_cache[idx] = *starting_dist_cache++;\r
- }\r
-}\r
-\r
-/* Maintains "ZopfliNode array invariant" and pushes node to the queue, if it\r
- is eligible. */\r
-static void EvaluateNode(\r
- const size_t block_start, const size_t pos, const size_t max_backward_limit,\r
- const size_t gap, const int* starting_dist_cache,\r
- const ZopfliCostModel* model, StartPosQueue* queue, ZopfliNode* nodes) {\r
- /* Save cost, because ComputeDistanceCache invalidates it. */\r
- float node_cost = nodes[pos].u.cost;\r
- nodes[pos].u.shortcut = ComputeDistanceShortcut(\r
- block_start, pos, max_backward_limit, gap, nodes);\r
- if (node_cost <= ZopfliCostModelGetLiteralCosts(model, 0, pos)) {\r
- PosData posdata;\r
- posdata.pos = pos;\r
- posdata.cost = node_cost;\r
- posdata.costdiff = node_cost -\r
- ZopfliCostModelGetLiteralCosts(model, 0, pos);\r
- ComputeDistanceCache(\r
- pos, starting_dist_cache, nodes, posdata.distance_cache);\r
- StartPosQueuePush(queue, &posdata);\r
- }\r
-}\r
-\r
-/* Returns longest copy length. */\r
-static size_t UpdateNodes(\r
- const size_t num_bytes, const size_t block_start, const size_t pos,\r
- const uint8_t* ringbuffer, const size_t ringbuffer_mask,\r
- const BrotliEncoderParams* params, const size_t max_backward_limit,\r
- const int* starting_dist_cache, const size_t num_matches,\r
- const BackwardMatch* matches, const ZopfliCostModel* model,\r
- StartPosQueue* queue, ZopfliNode* nodes) {\r
- const size_t cur_ix = block_start + pos;\r
- const size_t cur_ix_masked = cur_ix & ringbuffer_mask;\r
- const size_t max_distance = BROTLI_MIN(size_t, cur_ix, max_backward_limit);\r
- const size_t max_len = num_bytes - pos;\r
- const size_t max_zopfli_len = MaxZopfliLen(params);\r
- const size_t max_iters = MaxZopfliCandidates(params);\r
- size_t min_len;\r
- size_t result = 0;\r
- size_t k;\r
- size_t gap = 0;\r
-\r
- EvaluateNode(block_start, pos, max_backward_limit, gap, starting_dist_cache,\r
- model, queue, nodes);\r
-\r
- {\r
- const PosData* posdata = StartPosQueueAt(queue, 0);\r
- float min_cost = (posdata->cost + ZopfliCostModelGetMinCostCmd(model) +\r
- ZopfliCostModelGetLiteralCosts(model, posdata->pos, pos));\r
- min_len = ComputeMinimumCopyLength(min_cost, nodes, num_bytes, pos);\r
- }\r
-\r
- /* Go over the command starting positions in order of increasing cost\r
- difference. */\r
- for (k = 0; k < max_iters && k < StartPosQueueSize(queue); ++k) {\r
- const PosData* posdata = StartPosQueueAt(queue, k);\r
- const size_t start = posdata->pos;\r
- const uint16_t inscode = GetInsertLengthCode(pos - start);\r
- const float start_costdiff = posdata->costdiff;\r
- const float base_cost = start_costdiff + (float)GetInsertExtra(inscode) +\r
- ZopfliCostModelGetLiteralCosts(model, 0, pos);\r
-\r
- /* Look for last distance matches using the distance cache from this\r
- starting position. */\r
- size_t best_len = min_len - 1;\r
- size_t j = 0;\r
- for (; j < BROTLI_NUM_DISTANCE_SHORT_CODES && best_len < max_len; ++j) {\r
- const size_t idx = kDistanceCacheIndex[j];\r
- const size_t backward =\r
- (size_t)(posdata->distance_cache[idx] + kDistanceCacheOffset[j]);\r
- size_t prev_ix = cur_ix - backward;\r
- size_t len = 0;\r
- uint8_t continuation = ringbuffer[cur_ix_masked + best_len];\r
- if (cur_ix_masked + best_len > ringbuffer_mask) {\r
- break;\r
- }\r
- if (BROTLI_PREDICT_FALSE(backward > max_distance + gap)) {\r
- continue;\r
- }\r
- if (backward <= max_distance) {\r
- if (prev_ix >= cur_ix) {\r
- continue;\r
- }\r
-\r
- prev_ix &= ringbuffer_mask;\r
- if (prev_ix + best_len > ringbuffer_mask ||\r
- continuation != ringbuffer[prev_ix + best_len]) {\r
- continue;\r
- }\r
- len = FindMatchLengthWithLimit(&ringbuffer[prev_ix],\r
- &ringbuffer[cur_ix_masked],\r
- max_len);\r
- } else {\r
- continue;\r
- }\r
- {\r
- const float dist_cost = base_cost +\r
- ZopfliCostModelGetDistanceCost(model, j);\r
- size_t l;\r
- for (l = best_len + 1; l <= len; ++l) {\r
- const uint16_t copycode = GetCopyLengthCode(l);\r
- const uint16_t cmdcode =\r
- CombineLengthCodes(inscode, copycode, j == 0);\r
- const float cost = (cmdcode < 128 ? base_cost : dist_cost) +\r
- (float)GetCopyExtra(copycode) +\r
- ZopfliCostModelGetCommandCost(model, cmdcode);\r
- if (cost < nodes[pos + l].u.cost) {\r
- UpdateZopfliNode(nodes, pos, start, l, l, backward, j + 1, cost);\r
- result = BROTLI_MAX(size_t, result, l);\r
- }\r
- best_len = l;\r
- }\r
- }\r
- }\r
-\r
- /* At higher iterations look only for new last distance matches, since\r
- looking only for new command start positions with the same distances\r
- does not help much. */\r
- if (k >= 2) continue;\r
-\r
- {\r
- /* Loop through all possible copy lengths at this position. */\r
- size_t len = min_len;\r
- for (j = 0; j < num_matches; ++j) {\r
- BackwardMatch match = matches[j];\r
- size_t dist = match.distance;\r
- BROTLI_BOOL is_dictionary_match =\r
- TO_BROTLI_BOOL(dist > max_distance + gap);\r
- /* We already tried all possible last distance matches, so we can use\r
- normal distance code here. */\r
- size_t dist_code = dist + BROTLI_NUM_DISTANCE_SHORT_CODES - 1;\r
- uint16_t dist_symbol;\r
- uint32_t distextra;\r
- uint32_t distnumextra;\r
- float dist_cost;\r
- size_t max_match_len;\r
- PrefixEncodeCopyDistance(\r
- dist_code, params->dist.num_direct_distance_codes,\r
- params->dist.distance_postfix_bits, &dist_symbol, &distextra);\r
- distnumextra = dist_symbol >> 10;\r
- dist_cost = base_cost + (float)distnumextra +\r
- ZopfliCostModelGetDistanceCost(model, dist_symbol & 0x3FF);\r
-\r
- /* Try all copy lengths up until the maximum copy length corresponding\r
- to this distance. If the distance refers to the static dictionary, or\r
- the maximum length is long enough, try only one maximum length. */\r
- max_match_len = BackwardMatchLength(&match);\r
- if (len < max_match_len &&\r
- (is_dictionary_match || max_match_len > max_zopfli_len)) {\r
- len = max_match_len;\r
- }\r
- for (; len <= max_match_len; ++len) {\r
- const size_t len_code =\r
- is_dictionary_match ? BackwardMatchLengthCode(&match) : len;\r
- const uint16_t copycode = GetCopyLengthCode(len_code);\r
- const uint16_t cmdcode = CombineLengthCodes(inscode, copycode, 0);\r
- const float cost = dist_cost + (float)GetCopyExtra(copycode) +\r
- ZopfliCostModelGetCommandCost(model, cmdcode);\r
- if (cost < nodes[pos + len].u.cost) {\r
- UpdateZopfliNode(nodes, pos, start, len, len_code, dist, 0, cost);\r
- result = BROTLI_MAX(size_t, result, len);\r
- }\r
- }\r
- }\r
- }\r
- }\r
- return result;\r
-}\r
-\r
-static size_t ComputeShortestPathFromNodes(size_t num_bytes,\r
- ZopfliNode* nodes) {\r
- size_t index = num_bytes;\r
- size_t num_commands = 0;\r
- while ((nodes[index].dcode_insert_length & 0x7FFFFFF) == 0 &&\r
- nodes[index].length == 1) --index;\r
- nodes[index].u.next = BROTLI_UINT32_MAX;\r
- while (index != 0) {\r
- size_t len = ZopfliNodeCommandLength(&nodes[index]);\r
- index -= len;\r
- nodes[index].u.next = (uint32_t)len;\r
- num_commands++;\r
- }\r
- return num_commands;\r
-}\r
-\r
-/* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */\r
-void BrotliZopfliCreateCommands(const size_t num_bytes,\r
- const size_t block_start,\r
- const size_t max_backward_limit,\r
- const ZopfliNode* nodes,\r
- int* dist_cache,\r
- size_t* last_insert_len,\r
- const BrotliEncoderParams* params,\r
- Command* commands,\r
- size_t* num_literals) {\r
- size_t pos = 0;\r
- uint32_t offset = nodes[0].u.next;\r
- size_t i;\r
- size_t gap = 0;\r
- for (i = 0; offset != BROTLI_UINT32_MAX; i++) {\r
- const ZopfliNode* next = &nodes[pos + offset];\r
- size_t copy_length = ZopfliNodeCopyLength(next);\r
- size_t insert_length = next->dcode_insert_length & 0x7FFFFFF;\r
- pos += insert_length;\r
- offset = next->u.next;\r
- if (i == 0) {\r
- insert_length += *last_insert_len;\r
- *last_insert_len = 0;\r
- }\r
- {\r
- size_t distance = ZopfliNodeCopyDistance(next);\r
- size_t len_code = ZopfliNodeLengthCode(next);\r
- size_t max_distance =\r
- BROTLI_MIN(size_t, block_start + pos, max_backward_limit);\r
- BROTLI_BOOL is_dictionary = TO_BROTLI_BOOL(distance > max_distance + gap);\r
- size_t dist_code = ZopfliNodeDistanceCode(next);\r
- InitCommand(&commands[i], ¶ms->dist, insert_length,\r
- copy_length, (int)len_code - (int)copy_length, dist_code);\r
-\r
- if (!is_dictionary && dist_code > 0) {\r
- dist_cache[3] = dist_cache[2];\r
- dist_cache[2] = dist_cache[1];\r
- dist_cache[1] = dist_cache[0];\r
- dist_cache[0] = (int)distance;\r
- }\r
- }\r
-\r
- *num_literals += insert_length;\r
- pos += copy_length;\r
- }\r
- *last_insert_len += num_bytes - pos;\r
-}\r
-\r
-static size_t ZopfliIterate(size_t num_bytes,\r
- size_t position,\r
- const uint8_t* ringbuffer,\r
- size_t ringbuffer_mask,\r
- const BrotliEncoderParams* params,\r
- const size_t max_backward_limit,\r
- const size_t gap,\r
- const int* dist_cache,\r
- const ZopfliCostModel* model,\r
- const uint32_t* num_matches,\r
- const BackwardMatch* matches,\r
- ZopfliNode* nodes) {\r
- const size_t max_zopfli_len = MaxZopfliLen(params);\r
- StartPosQueue queue;\r
- size_t cur_match_pos = 0;\r
- size_t i;\r
- nodes[0].length = 0;\r
- nodes[0].u.cost = 0;\r
- InitStartPosQueue(&queue);\r
- for (i = 0; i + 3 < num_bytes; i++) {\r
- size_t skip = UpdateNodes(num_bytes, position, i, ringbuffer,\r
- ringbuffer_mask, params, max_backward_limit, dist_cache,\r
- num_matches[i], &matches[cur_match_pos], model, &queue, nodes);\r
- if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0;\r
- cur_match_pos += num_matches[i];\r
- if (num_matches[i] == 1 &&\r
- BackwardMatchLength(&matches[cur_match_pos - 1]) > max_zopfli_len) {\r
- skip = BROTLI_MAX(size_t,\r
- BackwardMatchLength(&matches[cur_match_pos - 1]), skip);\r
- }\r
- if (skip > 1) {\r
- skip--;\r
- while (skip) {\r
- i++;\r
- if (i + 3 >= num_bytes) break;\r
- EvaluateNode(position, i, max_backward_limit, gap, dist_cache, model,\r
- &queue, nodes);\r
- cur_match_pos += num_matches[i];\r
- skip--;\r
- }\r
- }\r
- }\r
- return ComputeShortestPathFromNodes(num_bytes, nodes);\r
-}\r
-\r
-/* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */\r
-size_t BrotliZopfliComputeShortestPath(MemoryManager* m,\r
- size_t num_bytes, size_t position, const uint8_t* ringbuffer,\r
- size_t ringbuffer_mask, const BrotliEncoderParams* params,\r
- const size_t max_backward_limit, const int* dist_cache, HasherHandle hasher,\r
- ZopfliNode* nodes) {\r
- const size_t max_zopfli_len = MaxZopfliLen(params);\r
- ZopfliCostModel model;\r
- StartPosQueue queue;\r
- BackwardMatch matches[2 * (MAX_NUM_MATCHES_H10 + 64)];\r
- const size_t store_end = num_bytes >= StoreLookaheadH10() ?\r
- position + num_bytes - StoreLookaheadH10() + 1 : position;\r
- size_t i;\r
- size_t gap = 0;\r
- size_t lz_matches_offset = 0;\r
- nodes[0].length = 0;\r
- nodes[0].u.cost = 0;\r
- InitZopfliCostModel(m, &model, ¶ms->dist, num_bytes);\r
- if (BROTLI_IS_OOM(m)) return 0;\r
- ZopfliCostModelSetFromLiteralCosts(\r
- &model, position, ringbuffer, ringbuffer_mask);\r
- InitStartPosQueue(&queue);\r
- for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; i++) {\r
- const size_t pos = position + i;\r
- const size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit);\r
- size_t skip;\r
- size_t num_matches = FindAllMatchesH10(hasher, ¶ms->dictionary,\r
- ringbuffer, ringbuffer_mask, pos, num_bytes - i, max_distance, gap,\r
- params, &matches[lz_matches_offset]);\r
- if (num_matches > 0 &&\r
- BackwardMatchLength(&matches[num_matches - 1]) > max_zopfli_len) {\r
- matches[0] = matches[num_matches - 1];\r
- num_matches = 1;\r
- }\r
- skip = UpdateNodes(num_bytes, position, i, ringbuffer, ringbuffer_mask,\r
- params, max_backward_limit, dist_cache, num_matches, matches, &model,\r
- &queue, nodes);\r
- if (skip < BROTLI_LONG_COPY_QUICK_STEP) skip = 0;\r
- if (num_matches == 1 && BackwardMatchLength(&matches[0]) > max_zopfli_len) {\r
- skip = BROTLI_MAX(size_t, BackwardMatchLength(&matches[0]), skip);\r
- }\r
- if (skip > 1) {\r
- /* Add the tail of the copy to the hasher. */\r
- StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1, BROTLI_MIN(\r
- size_t, pos + skip, store_end));\r
- skip--;\r
- while (skip) {\r
- i++;\r
- if (i + HashTypeLengthH10() - 1 >= num_bytes) break;\r
- EvaluateNode(position, i, max_backward_limit, gap, dist_cache, &model,\r
- &queue, nodes);\r
- skip--;\r
- }\r
- }\r
- }\r
- CleanupZopfliCostModel(m, &model);\r
- return ComputeShortestPathFromNodes(num_bytes, nodes);\r
-}\r
-\r
-void BrotliCreateZopfliBackwardReferences(MemoryManager* m,\r
- size_t num_bytes, size_t position, const uint8_t* ringbuffer,\r
- size_t ringbuffer_mask, const BrotliEncoderParams* params,\r
- HasherHandle hasher, int* dist_cache, size_t* last_insert_len,\r
- Command* commands, size_t* num_commands, size_t* num_literals) {\r
- const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);\r
- ZopfliNode* nodes;\r
- nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1);\r
- if (BROTLI_IS_OOM(m)) return;\r
- BrotliInitZopfliNodes(nodes, num_bytes + 1);\r
- *num_commands += BrotliZopfliComputeShortestPath(m,\r
- num_bytes, position, ringbuffer, ringbuffer_mask,\r
- params, max_backward_limit, dist_cache, hasher, nodes);\r
- if (BROTLI_IS_OOM(m)) return;\r
- BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit, nodes,\r
- dist_cache, last_insert_len, params, commands, num_literals);\r
- BROTLI_FREE(m, nodes);\r
-}\r
-\r
-void BrotliCreateHqZopfliBackwardReferences(MemoryManager* m,\r
- size_t num_bytes, size_t position, const uint8_t* ringbuffer,\r
- size_t ringbuffer_mask, const BrotliEncoderParams* params,\r
- HasherHandle hasher, int* dist_cache, size_t* last_insert_len,\r
- Command* commands, size_t* num_commands, size_t* num_literals) {\r
- const size_t max_backward_limit = BROTLI_MAX_BACKWARD_LIMIT(params->lgwin);\r
- uint32_t* num_matches = BROTLI_ALLOC(m, uint32_t, num_bytes);\r
- size_t matches_size = 4 * num_bytes;\r
- const size_t store_end = num_bytes >= StoreLookaheadH10() ?\r
- position + num_bytes - StoreLookaheadH10() + 1 : position;\r
- size_t cur_match_pos = 0;\r
- size_t i;\r
- size_t orig_num_literals;\r
- size_t orig_last_insert_len;\r
- int orig_dist_cache[4];\r
- size_t orig_num_commands;\r
- ZopfliCostModel model;\r
- ZopfliNode* nodes;\r
- BackwardMatch* matches = BROTLI_ALLOC(m, BackwardMatch, matches_size);\r
- size_t gap = 0;\r
- size_t shadow_matches = 0;\r
- if (BROTLI_IS_OOM(m)) return;\r
- for (i = 0; i + HashTypeLengthH10() - 1 < num_bytes; ++i) {\r
- const size_t pos = position + i;\r
- size_t max_distance = BROTLI_MIN(size_t, pos, max_backward_limit);\r
- size_t max_length = num_bytes - i;\r
- size_t num_found_matches;\r
- size_t cur_match_end;\r
- size_t j;\r
- /* Ensure that we have enough free slots. */\r
- BROTLI_ENSURE_CAPACITY(m, BackwardMatch, matches, matches_size,\r
- cur_match_pos + MAX_NUM_MATCHES_H10 + shadow_matches);\r
- if (BROTLI_IS_OOM(m)) return;\r
- num_found_matches = FindAllMatchesH10(hasher,\r
- ¶ms->dictionary, ringbuffer, ringbuffer_mask, pos, max_length,\r
- max_distance, gap, params, &matches[cur_match_pos + shadow_matches]);\r
- cur_match_end = cur_match_pos + num_found_matches;\r
- for (j = cur_match_pos; j + 1 < cur_match_end; ++j) {\r
- BROTLI_DCHECK(BackwardMatchLength(&matches[j]) <=\r
- BackwardMatchLength(&matches[j + 1]));\r
- }\r
- num_matches[i] = (uint32_t)num_found_matches;\r
- if (num_found_matches > 0) {\r
- const size_t match_len = BackwardMatchLength(&matches[cur_match_end - 1]);\r
- if (match_len > MAX_ZOPFLI_LEN_QUALITY_11) {\r
- const size_t skip = match_len - 1;\r
- matches[cur_match_pos++] = matches[cur_match_end - 1];\r
- num_matches[i] = 1;\r
- /* Add the tail of the copy to the hasher. */\r
- StoreRangeH10(hasher, ringbuffer, ringbuffer_mask, pos + 1,\r
- BROTLI_MIN(size_t, pos + match_len, store_end));\r
- memset(&num_matches[i + 1], 0, skip * sizeof(num_matches[0]));\r
- i += skip;\r
- } else {\r
- cur_match_pos = cur_match_end;\r
- }\r
- }\r
- }\r
- orig_num_literals = *num_literals;\r
- orig_last_insert_len = *last_insert_len;\r
- memcpy(orig_dist_cache, dist_cache, 4 * sizeof(dist_cache[0]));\r
- orig_num_commands = *num_commands;\r
- nodes = BROTLI_ALLOC(m, ZopfliNode, num_bytes + 1);\r
- if (BROTLI_IS_OOM(m)) return;\r
- InitZopfliCostModel(m, &model, ¶ms->dist, num_bytes);\r
- if (BROTLI_IS_OOM(m)) return;\r
- for (i = 0; i < 2; i++) {\r
- BrotliInitZopfliNodes(nodes, num_bytes + 1);\r
- if (i == 0) {\r
- ZopfliCostModelSetFromLiteralCosts(\r
- &model, position, ringbuffer, ringbuffer_mask);\r
- } else {\r
- ZopfliCostModelSetFromCommands(&model, position, ringbuffer,\r
- ringbuffer_mask, commands, *num_commands - orig_num_commands,\r
- orig_last_insert_len);\r
- }\r
- *num_commands = orig_num_commands;\r
- *num_literals = orig_num_literals;\r
- *last_insert_len = orig_last_insert_len;\r
- memcpy(dist_cache, orig_dist_cache, 4 * sizeof(dist_cache[0]));\r
- *num_commands += ZopfliIterate(num_bytes, position, ringbuffer,\r
- ringbuffer_mask, params, max_backward_limit, gap, dist_cache,\r
- &model, num_matches, matches, nodes);\r
- BrotliZopfliCreateCommands(num_bytes, position, max_backward_limit,\r
- nodes, dist_cache, last_insert_len, params, commands, num_literals);\r
- }\r
- CleanupZopfliCostModel(m, &model);\r
- BROTLI_FREE(m, nodes);\r
- BROTLI_FREE(m, matches);\r
- BROTLI_FREE(m, num_matches);\r
-}\r
-\r
-#if defined(__cplusplus) || defined(c_plusplus)\r
-} /* extern "C" */\r
-#endif\r
projects / mirror_edk2.git / blobdiff