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) 22 extern "C" { 23 #endif 24 25 BROTLI_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 32 BROTLI_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 39 typedef 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 65 BROTLI_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 */ 80 BROTLI_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 86 BROTLI_INTERNAL void BrotliZopfliCreateCommands(const size_t num_bytes, 87 const size_t block_start, 88 const size_t max_backward_limit, 89 const ZopfliNode* nodes, 90 int* dist_cache, 91 size_t* last_insert_len, 92 Command* commands, 93 size_t* num_literals); 94 95 #if defined(__cplusplus) || defined(c_plusplus) 96 } /* extern "C" */ 97 #endif 98 99 #endif /* BROTLI_ENC_BACKWARD_REFERENCES_HQ_H_ */ 100