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#ifndef BROTLI_ENC_BACKWARD_REFERENCES_HQ_H_
10#define BROTLI_ENC_BACKWARD_REFERENCES_HQ_H_
11
12#include "../common/constants.h"
13#include "../common/dictionary.h"
14#include <brotli/types.h>
15#include "./command.h"
16#include "./hash.h"
17#include "./memory.h"
18#include "./port.h"
19#include "./quality.h"
20
21#if defined(__cplusplus) || defined(c_plusplus)
22extern "C" {
23#endif
24
25BROTLI_INTERNAL void BrotliCreateZopfliBackwardReferences(
26    MemoryManager* m, const BrotliDictionary* dictionary, size_t num_bytes,
27    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
28    const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache,
29    size_t* last_insert_len, Command* commands, size_t* num_commands,
30    size_t* num_literals);
31
32BROTLI_INTERNAL void BrotliCreateHqZopfliBackwardReferences(
33    MemoryManager* m, const BrotliDictionary* dictionary, size_t num_bytes,
34    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
35    const BrotliEncoderParams* params, HasherHandle hasher, int* dist_cache,
36    size_t* last_insert_len, Command* commands, size_t* num_commands,
37    size_t* num_literals);
38
39typedef struct ZopfliNode {
40  /* best length to get up to this byte (not including this byte itself)
41     highest 8 bit is used to reconstruct the length code */
42  uint32_t length;
43  /* distance associated with the length
44     highest 7 bit contains distance short code + 1 (or zero if no short code)
45  */
46  uint32_t distance;
47  /* number of literal inserts before this copy */
48  uint32_t insert_length;
49
50  /* This union holds information used by dynamic-programming. During forward
51     pass |cost| it used to store the goal function. When node is processed its
52     |cost| is invalidated in favor of |shortcut|. On path back-tracing pass
53     |next| is assigned the offset to next node on the path. */
54  union {
55    /* Smallest cost to get to this byte from the beginning, as found so far. */
56    float cost;
57    /* Offset to the next node on the path. Equals to command_length() of the
58       next node on the path. For last node equals to BROTLI_UINT32_MAX */
59    uint32_t next;
60    /* Node position that provides next distance for distance cache. */
61    uint32_t shortcut;
62  } u;
63} ZopfliNode;
64
65BROTLI_INTERNAL void BrotliInitZopfliNodes(ZopfliNode* array, size_t length);
66
67/* Computes the shortest path of commands from position to at most
68   position + num_bytes.
69
70   On return, path->size() is the number of commands found and path[i] is the
71   length of the i-th command (copy length plus insert length).
72   Note that the sum of the lengths of all commands can be less than num_bytes.
73
74   On return, the nodes[0..num_bytes] array will have the following
75   "ZopfliNode array invariant":
76   For each i in [1..num_bytes], if nodes[i].cost < kInfinity, then
77     (1) nodes[i].copy_length() >= 2
78     (2) nodes[i].command_length() <= i and
79     (3) nodes[i - nodes[i].command_length()].cost < kInfinity */
80BROTLI_INTERNAL size_t BrotliZopfliComputeShortestPath(
81    MemoryManager* m, const BrotliDictionary* dictionary, size_t num_bytes,
82    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
83    const BrotliEncoderParams* params, const size_t max_backward_limit,
84    const int* dist_cache, HasherHandle hasher, ZopfliNode* nodes);
85
86BROTLI_INTERNAL void BrotliZopfliCreateCommands(
87    const size_t num_bytes, const size_t block_start,
88    const size_t max_backward_limit, const ZopfliNode* nodes,
89    int* dist_cache, size_t* last_insert_len, const BrotliEncoderParams* params,
90    Command* commands, size_t* num_literals);
91
92#if defined(__cplusplus) || defined(c_plusplus)
93}  /* extern "C" */
94#endif
95
96#endif  /* BROTLI_ENC_BACKWARD_REFERENCES_HQ_H_ */
97