backward_references_enc.h (8810B)
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_ENC_H_ 14 #define WEBP_ENC_BACKWARD_REFERENCES_ENC_H_ 15 16 #include <assert.h> 17 #include <stdlib.h> 18 19 #include "src/webp/encode.h" 20 #include "src/webp/format_constants.h" 21 #include "src/webp/types.h" 22 23 #ifdef __cplusplus 24 extern "C" { 25 #endif 26 27 // The maximum allowed limit is 11. 28 #define MAX_COLOR_CACHE_BITS 10 29 30 // ----------------------------------------------------------------------------- 31 // PixOrCopy 32 33 enum Mode { 34 kLiteral, 35 kCacheIdx, 36 kCopy, 37 kNone 38 }; 39 40 typedef struct { 41 // mode as uint8_t to make the memory layout to be exactly 8 bytes. 42 uint8_t mode; 43 uint16_t len; 44 uint32_t argb_or_distance; 45 } PixOrCopy; 46 47 static WEBP_INLINE PixOrCopy PixOrCopyCreateCopy(uint32_t distance, 48 uint16_t len) { 49 PixOrCopy retval; 50 retval.mode = kCopy; 51 retval.argb_or_distance = distance; 52 retval.len = len; 53 return retval; 54 } 55 56 static WEBP_INLINE PixOrCopy PixOrCopyCreateCacheIdx(int idx) { 57 PixOrCopy retval; 58 assert(idx >= 0); 59 assert(idx < (1 << MAX_COLOR_CACHE_BITS)); 60 retval.mode = kCacheIdx; 61 retval.argb_or_distance = idx; 62 retval.len = 1; 63 return retval; 64 } 65 66 static WEBP_INLINE PixOrCopy PixOrCopyCreateLiteral(uint32_t argb) { 67 PixOrCopy retval; 68 retval.mode = kLiteral; 69 retval.argb_or_distance = argb; 70 retval.len = 1; 71 return retval; 72 } 73 74 static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) { 75 return (p->mode == kLiteral); 76 } 77 78 static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) { 79 return (p->mode == kCacheIdx); 80 } 81 82 static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) { 83 return (p->mode == kCopy); 84 } 85 86 static WEBP_INLINE uint32_t PixOrCopyLiteral(const PixOrCopy* const p, 87 int component) { 88 assert(p->mode == kLiteral); 89 return (p->argb_or_distance >> (component * 8)) & 0xff; 90 } 91 92 static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) { 93 return p->len; 94 } 95 96 static WEBP_INLINE uint32_t PixOrCopyCacheIdx(const PixOrCopy* const p) { 97 assert(p->mode == kCacheIdx); 98 assert(p->argb_or_distance < (1U << MAX_COLOR_CACHE_BITS)); 99 return p->argb_or_distance; 100 } 101 102 static WEBP_INLINE uint32_t PixOrCopyDistance(const PixOrCopy* const p) { 103 assert(p->mode == kCopy); 104 return p->argb_or_distance; 105 } 106 107 // ----------------------------------------------------------------------------- 108 // VP8LHashChain 109 110 #define HASH_BITS 18 111 #define HASH_SIZE (1 << HASH_BITS) 112 113 // If you change this, you need MAX_LENGTH_BITS + WINDOW_SIZE_BITS <= 32 as it 114 // is used in VP8LHashChain. 115 #define MAX_LENGTH_BITS 12 116 #define WINDOW_SIZE_BITS 20 117 // We want the max value to be attainable and stored in MAX_LENGTH_BITS bits. 118 #define MAX_LENGTH ((1 << MAX_LENGTH_BITS) - 1) 119 #if MAX_LENGTH_BITS + WINDOW_SIZE_BITS > 32 120 #error "MAX_LENGTH_BITS + WINDOW_SIZE_BITS > 32" 121 #endif 122 123 typedef struct VP8LHashChain VP8LHashChain; 124 struct VP8LHashChain { 125 // The 20 most significant bits contain the offset at which the best match 126 // is found. These 20 bits are the limit defined by GetWindowSizeForHashChain 127 // (through WINDOW_SIZE = 1<<20). 128 // The lower 12 bits contain the length of the match. The 12 bit limit is 129 // defined in MaxFindCopyLength with MAX_LENGTH=4096. 130 uint32_t* offset_length; 131 // This is the maximum size of the hash_chain that can be constructed. 132 // Typically this is the pixel count (width x height) for a given image. 133 int size; 134 }; 135 136 // Must be called first, to set size. 137 int VP8LHashChainInit(VP8LHashChain* const p, int size); 138 // Pre-compute the best matches for argb. pic and percent are for progress. 139 int VP8LHashChainFill(VP8LHashChain* const p, int quality, 140 const uint32_t* const argb, int xsize, int ysize, 141 int low_effort, const WebPPicture* const pic, 142 int percent_range, int* const percent); 143 void VP8LHashChainClear(VP8LHashChain* const p); // release memory 144 145 static WEBP_INLINE int VP8LHashChainFindOffset(const VP8LHashChain* const p, 146 const int base_position) { 147 return p->offset_length[base_position] >> MAX_LENGTH_BITS; 148 } 149 150 static WEBP_INLINE int VP8LHashChainFindLength(const VP8LHashChain* const p, 151 const int base_position) { 152 return p->offset_length[base_position] & ((1U << MAX_LENGTH_BITS) - 1); 153 } 154 155 static WEBP_INLINE void VP8LHashChainFindCopy(const VP8LHashChain* const p, 156 int base_position, 157 int* const offset_ptr, 158 int* const length_ptr) { 159 *offset_ptr = VP8LHashChainFindOffset(p, base_position); 160 *length_ptr = VP8LHashChainFindLength(p, base_position); 161 } 162 163 // ----------------------------------------------------------------------------- 164 // VP8LBackwardRefs (block-based backward-references storage) 165 166 // maximum number of reference blocks the image will be segmented into 167 #define MAX_REFS_BLOCK_PER_IMAGE 16 168 169 typedef struct PixOrCopyBlock PixOrCopyBlock; // forward declaration 170 typedef struct VP8LBackwardRefs VP8LBackwardRefs; 171 172 // Container for blocks chain 173 struct VP8LBackwardRefs { 174 int block_size; // common block-size 175 int error; // set to true if some memory error occurred 176 PixOrCopyBlock* refs; // list of currently used blocks 177 PixOrCopyBlock** tail; // for list recycling 178 PixOrCopyBlock* free_blocks; // free-list 179 PixOrCopyBlock* last_block; // used for adding new refs (internal) 180 }; 181 182 // Initialize the object. 'block_size' is the common block size to store 183 // references (typically, width * height / MAX_REFS_BLOCK_PER_IMAGE). 184 void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size); 185 // Release memory for backward references. 186 void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs); 187 188 // Cursor for iterating on references content 189 typedef struct { 190 // public: 191 PixOrCopy* cur_pos; // current position 192 // private: 193 PixOrCopyBlock* cur_block; // current block in the refs list 194 const PixOrCopy* last_pos; // sentinel for switching to next block 195 } VP8LRefsCursor; 196 197 // Returns a cursor positioned at the beginning of the references list. 198 VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs); 199 // Returns true if cursor is pointing at a valid position. 200 static WEBP_INLINE int VP8LRefsCursorOk(const VP8LRefsCursor* const c) { 201 return (c->cur_pos != NULL); 202 } 203 // Move to next block of references. Internal, not to be called directly. 204 void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c); 205 // Move to next position, or NULL. Should not be called if !VP8LRefsCursorOk(). 206 static WEBP_INLINE void VP8LRefsCursorNext(VP8LRefsCursor* const c) { 207 assert(c != NULL); 208 assert(VP8LRefsCursorOk(c)); 209 if (++c->cur_pos == c->last_pos) VP8LRefsCursorNextBlock(c); 210 } 211 212 // ----------------------------------------------------------------------------- 213 // Main entry points 214 215 enum VP8LLZ77Type { 216 kLZ77Standard = 1, 217 kLZ77RLE = 2, 218 kLZ77Box = 4 219 }; 220 221 // Evaluates best possible backward references for specified quality. 222 // The input cache_bits to 'VP8LGetBackwardReferences' sets the maximum cache 223 // bits to use (passing 0 implies disabling the local color cache). 224 // The optimal cache bits is evaluated and set for the *cache_bits_best 225 // parameter with the matching refs_best. 226 // If do_no_cache == 0, refs is an array of 2 values and the best 227 // VP8LBackwardRefs is put in the first element. 228 // If do_no_cache != 0, refs is an array of 3 values and the best 229 // VP8LBackwardRefs is put in the first element, the best value with no-cache in 230 // the second element. 231 // In both cases, the last element is used as temporary internally. 232 // pic and percent are for progress. 233 // Returns false in case of error (stored in pic->error_code). 234 int VP8LGetBackwardReferences( 235 int width, int height, const uint32_t* const argb, int quality, 236 int low_effort, int lz77_types_to_try, int cache_bits_max, int do_no_cache, 237 const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs, 238 int* const cache_bits_best, const WebPPicture* const pic, int percent_range, 239 int* const percent); 240 241 #ifdef __cplusplus 242 } 243 #endif 244 245 #endif // WEBP_ENC_BACKWARD_REFERENCES_ENC_H_