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