third_party/libwebp/enc/backward_references.h

   1 // Copyright 2012 Google Inc. All Rights Reserved.
   2 //
   3 // Use of this source code is governed by a BSD-style license
   4 // that can be found in the COPYING file in the root of the source
   5 // tree. An additional intellectual property rights grant can be found
   6 // in the file PATENTS. All contributing project authors may
   7 // be found in the AUTHORS file in the root of the source tree.
   8 // -----------------------------------------------------------------------------
   9 //
  10 // Author: Jyrki Alakuijala (jyrki@google.com)
  11 //
  12
  13 #ifndef WEBP_ENC_BACKWARD_REFERENCES_H_
  14 #define WEBP_ENC_BACKWARD_REFERENCES_H_
  15
  16 #include <assert.h>
  17 #include <stdlib.h>
  18 #include "../webp/types.h"
  19 #include "../webp/format_constants.h"
  20
  21 #ifdef __cplusplus
  22 extern "C" {
  23 #endif
  24
  25 // The spec allows 11, we use 9 bits to reduce memory consumption in encoding.
  26 // Having 9 instead of 11 only removes about 0.25 % of compression density.
  27 #define MAX_COLOR_CACHE_BITS 9
  28
  29 // Max ever number of codes we'll use:
  30 #define PIX_OR_COPY_CODES_MAX \
  31     (NUM_LITERAL_CODES + NUM_LENGTH_CODES + (1 << MAX_COLOR_CACHE_BITS))
  32
  33 // -----------------------------------------------------------------------------
  34 // PixOrCopy
  35
  36 enum Mode {
  37   kLiteral,
  38   kCacheIdx,
  39   kCopy,
  40   kNone
  41 };
  42
  43 typedef struct {
  44   // mode as uint8_t to make the memory layout to be exactly 8 bytes.
  45   uint8_t mode;
  46   uint16_t len;
  47   uint32_t argb_or_distance;
  48 } PixOrCopy;
  49
  50 static WEBP_INLINE PixOrCopy PixOrCopyCreateCopy(uint32_t distance,
  51                                                  uint16_t len) {
  52   PixOrCopy retval;
  53   retval.mode = kCopy;
  54   retval.argb_or_distance = distance;
  55   retval.len = len;
  56   return retval;
  57 }
  58
  59 static WEBP_INLINE PixOrCopy PixOrCopyCreateCacheIdx(int idx) {
  60   PixOrCopy retval;
  61   assert(idx >= 0);
  62   assert(idx < (1 << MAX_COLOR_CACHE_BITS));
  63   retval.mode = kCacheIdx;
  64   retval.argb_or_distance = idx;
  65   retval.len = 1;
  66   return retval;
  67 }
  68
  69 static WEBP_INLINE PixOrCopy PixOrCopyCreateLiteral(uint32_t argb) {
  70   PixOrCopy retval;
  71   retval.mode = kLiteral;
  72   retval.argb_or_distance = argb;
  73   retval.len = 1;
  74   return retval;
  75 }
  76
  77 static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
  78   return (p->mode == kLiteral);
  79 }
  80
  81 static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
  82   return (p->mode == kCacheIdx);
  83 }
  84
  85 static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
  86   return (p->mode == kCopy);
  87 }
  88
  89 static WEBP_INLINE uint32_t PixOrCopyLiteral(const PixOrCopy* const p,
  90                                              int component) {
  91   assert(p->mode == kLiteral);
  92   return (p->argb_or_distance >> (component * 8)) & 0xff;
  93 }
  94
  95 static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
  96   return p->len;
  97 }
  98
  99 static WEBP_INLINE uint32_t PixOrCopyArgb(const PixOrCopy* const p) {
 100   assert(p->mode == kLiteral);
 101   return p->argb_or_distance;
 102 }
 103
 104 static WEBP_INLINE uint32_t PixOrCopyCacheIdx(const PixOrCopy* const p) {
 105   assert(p->mode == kCacheIdx);
 106   assert(p->argb_or_distance < (1U << MAX_COLOR_CACHE_BITS));
 107   return p->argb_or_distance;
 108 }
 109
 110 static WEBP_INLINE uint32_t PixOrCopyDistance(const PixOrCopy* const p) {
 111   assert(p->mode == kCopy);
 112   return p->argb_or_distance;
 113 }
 114
 115 // -----------------------------------------------------------------------------
 116 // VP8LHashChain
 117
 118 #define HASH_BITS 18
 119 #define HASH_SIZE (1 << HASH_BITS)
 120
 121 typedef struct VP8LHashChain VP8LHashChain;
 122 struct VP8LHashChain {
 123   // Stores the most recently added position with the given hash value.
 124   int32_t hash_to_first_index_[HASH_SIZE];
 125   // chain_[pos] stores the previous position with the same hash value
 126   // for every pixel in the image.
 127   int32_t* chain_;
 128   // This is the maximum size of the hash_chain that can be constructed.
 129   // Typically this is the pixel count (width x height) for a given image.
 130   int size_;
 131 };
 132
 133 // Must be called first, to set size.
 134 int VP8LHashChainInit(VP8LHashChain* const p, int size);
 135 void VP8LHashChainClear(VP8LHashChain* const p);  // release memory
 136
 137 // -----------------------------------------------------------------------------
 138 // VP8LBackwardRefs (block-based backward-references storage)
 139
 140 // maximum number of reference blocks the image will be segmented into
 141 #define MAX_REFS_BLOCK_PER_IMAGE 16
 142
 143 typedef struct PixOrCopyBlock PixOrCopyBlock;   // forward declaration
 144 typedef struct VP8LBackwardRefs VP8LBackwardRefs;
 145
 146 // Container for blocks chain
 147 struct VP8LBackwardRefs {
 148   int block_size_;               // common block-size
 149   int error_;                    // set to true if some memory error occurred
 150   PixOrCopyBlock* refs_;         // list of currently used blocks
 151   PixOrCopyBlock** tail_;        // for list recycling
 152   PixOrCopyBlock* free_blocks_;  // free-list
 153   PixOrCopyBlock* last_block_;   // used for adding new refs (internal)
 154 };
 155
 156 // Initialize the object. 'block_size' is the common block size to store
 157 // references (typically, width * height / MAX_REFS_BLOCK_PER_IMAGE).
 158 void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size);
 159 // Release memory for backward references.
 160 void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs);
 161 // Copies the 'src' backward refs to the 'dst'. Returns 0 in case of error.
 162 int VP8LBackwardRefsCopy(const VP8LBackwardRefs* const src,
 163                          VP8LBackwardRefs* const dst);
 164
 165 // Cursor for iterating on references content
 166 typedef struct {
 167   // public:
 168   PixOrCopy* cur_pos;           // current position
 169   // private:
 170   PixOrCopyBlock* cur_block_;   // current block in the refs list
 171   const PixOrCopy* last_pos_;   // sentinel for switching to next block
 172 } VP8LRefsCursor;
 173
 174 // Returns a cursor positioned at the beginning of the references list.
 175 VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs);
 176 // Returns true if cursor is pointing at a valid position.
 177 static WEBP_INLINE int VP8LRefsCursorOk(const VP8LRefsCursor* const c) {
 178   return (c->cur_pos != NULL);
 179 }
 180 // Move to next block of references. Internal, not to be called directly.
 181 void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c);
 182 // Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk().
 183 static WEBP_INLINE void VP8LRefsCursorNext(VP8LRefsCursor* const c) {
 184   assert(c != NULL);
 185   assert(VP8LRefsCursorOk(c));
 186   if (++c->cur_pos == c->last_pos_) VP8LRefsCursorNextBlock(c);
 187 }
 188
 189 // -----------------------------------------------------------------------------
 190 // Main entry points
 191
 192 // Evaluates best possible backward references for specified quality.
 193 // Further optimize for 2D locality if use_2d_locality flag is set.
 194 // The return value is the pointer to the best of the two backward refs viz,
 195 // refs[0] or refs[1].
 196 VP8LBackwardRefs* VP8LGetBackwardReferences(
 197     int width, int height, const uint32_t* const argb, int quality,
 198     int cache_bits, int use_2d_locality, VP8LHashChain* const hash_chain,
 199     VP8LBackwardRefs refs[2]);
 200
 201 // Produce an estimate for a good color cache size for the image.
 202 int VP8LCalculateEstimateForCacheSize(const uint32_t* const argb,
 203                                       int xsize, int ysize, int quality,
 204                                       VP8LHashChain* const hash_chain,
 205                                       VP8LBackwardRefs* const ref,
 206                                       int* const best_cache_bits);
 207
 208 #ifdef __cplusplus
 209 }
 210 #endif
 211
 212 #endif  // WEBP_ENC_BACKWARD_REFERENCES_H_