1 // Copyright 2012 Google Inc. All Rights Reserved. 2 // 3 // This code is licensed under the same terms as WebM: 4 // Software License Agreement: http://www.webmproject.org/license/software/ 5 // Additional IP Rights Grant: http://www.webmproject.org/license/additional/ 6 // ----------------------------------------------------------------------------- 7 // 8 // Author: Jyrki Alakuijala (jyrki (at) google.com) 9 // 10 11 #ifndef WEBP_ENC_BACKWARD_REFERENCES_H_ 12 #define WEBP_ENC_BACKWARD_REFERENCES_H_ 13 14 #include <assert.h> 15 #include <stdlib.h> 16 #include "webp/types.h" 17 #include "webp/format_constants.h" 18 19 #if defined(__cplusplus) || defined(c_plusplus) 20 extern "C" { 21 #endif 22 23 // The spec allows 11, we use 9 bits to reduce memory consumption in encoding. 24 // Having 9 instead of 11 only removes about 0.25 % of compression density. 25 #define MAX_COLOR_CACHE_BITS 9 26 27 // Max ever number of codes we'll use: 28 #define PIX_OR_COPY_CODES_MAX \ 29 (NUM_LITERAL_CODES + NUM_LENGTH_CODES + (1 << MAX_COLOR_CACHE_BITS)) 30 31 // ----------------------------------------------------------------------------- 32 // PrefixEncode() 33 34 // use GNU builtins where available. 35 #if defined(__GNUC__) && \ 36 ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4) 37 static WEBP_INLINE int BitsLog2Floor(uint32_t n) { 38 assert(n != 0); 39 return 31 ^ __builtin_clz(n); 40 } 41 #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86)) 42 #include <intrin.h> 43 #pragma intrinsic(_BitScanReverse) 44 45 static WEBP_INLINE int BitsLog2Floor(uint32_t n) { 46 unsigned long first_set_bit; 47 assert(n != 0); 48 _BitScanReverse(&first_set_bit, n); 49 return first_set_bit; 50 } 51 #else 52 // Returns (int)floor(log2(n)). n must be > 0. 53 static WEBP_INLINE int BitsLog2Floor(uint32_t n) { 54 int log = 0; 55 uint32_t value = n; 56 int i; 57 58 assert(n != 0); 59 for (i = 4; i >= 0; --i) { 60 const int shift = (1 << i); 61 const uint32_t x = value >> shift; 62 if (x != 0) { 63 value = x; 64 log += shift; 65 } 66 } 67 return log; 68 } 69 #endif 70 71 static WEBP_INLINE int VP8LBitsLog2Ceiling(uint32_t n) { 72 const int log_floor = BitsLog2Floor(n); 73 if (n == (n & ~(n - 1))) // zero or a power of two. 74 return log_floor; 75 else 76 return log_floor + 1; 77 } 78 79 // Splitting of distance and length codes into prefixes and 80 // extra bits. The prefixes are encoded with an entropy code 81 // while the extra bits are stored just as normal bits. 82 static WEBP_INLINE void PrefixEncode(int distance, int* const code, 83 int* const extra_bits_count, 84 int* const extra_bits_value) { 85 if (distance > 2) { // Collect the two most significant bits. 86 const int highest_bit = BitsLog2Floor(--distance); 87 const int second_highest_bit = (distance >> (highest_bit - 1)) & 1; 88 *extra_bits_count = highest_bit - 1; 89 *extra_bits_value = distance & ((1 << *extra_bits_count) - 1); 90 *code = 2 * highest_bit + second_highest_bit; 91 } else { 92 *extra_bits_count = 0; 93 *extra_bits_value = 0; 94 *code = (distance == 2) ? 1 : 0; 95 } 96 } 97 98 // ----------------------------------------------------------------------------- 99 // PixOrCopy 100 101 enum Mode { 102 kLiteral, 103 kCacheIdx, 104 kCopy, 105 kNone 106 }; 107 108 typedef struct { 109 // mode as uint8_t to make the memory layout to be exactly 8 bytes. 110 uint8_t mode; 111 uint16_t len; 112 uint32_t argb_or_distance; 113 } PixOrCopy; 114 115 static WEBP_INLINE PixOrCopy PixOrCopyCreateCopy(uint32_t distance, 116 uint16_t len) { 117 PixOrCopy retval; 118 retval.mode = kCopy; 119 retval.argb_or_distance = distance; 120 retval.len = len; 121 return retval; 122 } 123 124 static WEBP_INLINE PixOrCopy PixOrCopyCreateCacheIdx(int idx) { 125 PixOrCopy retval; 126 assert(idx >= 0); 127 assert(idx < (1 << MAX_COLOR_CACHE_BITS)); 128 retval.mode = kCacheIdx; 129 retval.argb_or_distance = idx; 130 retval.len = 1; 131 return retval; 132 } 133 134 static WEBP_INLINE PixOrCopy PixOrCopyCreateLiteral(uint32_t argb) { 135 PixOrCopy retval; 136 retval.mode = kLiteral; 137 retval.argb_or_distance = argb; 138 retval.len = 1; 139 return retval; 140 } 141 142 static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) { 143 return (p->mode == kLiteral); 144 } 145 146 static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) { 147 return (p->mode == kCacheIdx); 148 } 149 150 static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) { 151 return (p->mode == kCopy); 152 } 153 154 static WEBP_INLINE uint32_t PixOrCopyLiteral(const PixOrCopy* const p, 155 int component) { 156 assert(p->mode == kLiteral); 157 return (p->argb_or_distance >> (component * 8)) & 0xff; 158 } 159 160 static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) { 161 return p->len; 162 } 163 164 static WEBP_INLINE uint32_t PixOrCopyArgb(const PixOrCopy* const p) { 165 assert(p->mode == kLiteral); 166 return p->argb_or_distance; 167 } 168 169 static WEBP_INLINE uint32_t PixOrCopyCacheIdx(const PixOrCopy* const p) { 170 assert(p->mode == kCacheIdx); 171 assert(p->argb_or_distance < (1U << MAX_COLOR_CACHE_BITS)); 172 return p->argb_or_distance; 173 } 174 175 static WEBP_INLINE uint32_t PixOrCopyDistance(const PixOrCopy* const p) { 176 assert(p->mode == kCopy); 177 return p->argb_or_distance; 178 } 179 180 // ----------------------------------------------------------------------------- 181 // VP8LBackwardRefs 182 183 typedef struct { 184 PixOrCopy* refs; 185 int size; // currently used 186 int max_size; // maximum capacity 187 } VP8LBackwardRefs; 188 189 // Initialize the object. Must be called first. 'refs' can be NULL. 190 void VP8LInitBackwardRefs(VP8LBackwardRefs* const refs); 191 192 // Release memory and re-initialize the object. 'refs' can be NULL. 193 void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); 194 195 // Allocate 'max_size' references. Returns false in case of memory error. 196 int VP8LBackwardRefsAlloc(VP8LBackwardRefs* const refs, int max_size); 197 198 // ----------------------------------------------------------------------------- 199 // Main entry points 200 201 // Evaluates best possible backward references for specified quality. 202 // Further optimize for 2D locality if use_2d_locality flag is set. 203 int VP8LGetBackwardReferences(int width, int height, 204 const uint32_t* const argb, 205 int quality, int cache_bits, int use_2d_locality, 206 VP8LBackwardRefs* const best); 207 208 // Produce an estimate for a good color cache size for the image. 209 int VP8LCalculateEstimateForCacheSize(const uint32_t* const argb, 210 int xsize, int ysize, 211 int* const best_cache_bits); 212 213 #if defined(__cplusplus) || defined(c_plusplus) 214 } 215 #endif 216 217 #endif // WEBP_ENC_BACKWARD_REFERENCES_H_ 218
