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