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) |
22 | extern "C" { |
23 | #endif |
24 | |
25 | BROTLI_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 | |
32 | BROTLI_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 | |
39 | typedef 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 | |
64 | BROTLI_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 */ |
79 | BROTLI_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 | |
85 | BROTLI_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 | |