BaseTools/Source/C/BrotliCompress/enc/backward_references.h

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