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 return n == 0 ? -1 : 31 ^ __builtin_clz(n); 39 } 40 #elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86)) 41 #include <intrin.h> 42 #pragma intrinsic(_BitScanReverse) 43 44 static WEBP_INLINE int BitsLog2Floor(uint32_t n) { 45 unsigned long first_set_bit; 46 return _BitScanReverse(&first_set_bit, n) ? first_set_bit : -1; 47 } 48 #else 49 static WEBP_INLINE int BitsLog2Floor(uint32_t n) { 50 int log = 0; 51 uint32_t value = n; 52 int i; 53 54 if (value == 0) return -1; 55 for (i = 4; i >= 0; --i) { 56 const int shift = (1 << i); 57 const uint32_t x = value >> shift; 58 if (x != 0) { 59 value = x; 60 log += shift; 61 } 62 } 63 return log; 64 } 65 #endif 66 67 static WEBP_INLINE int VP8LBitsLog2Ceiling(uint32_t n) { 68 const int floor = BitsLog2Floor(n); 69 if (n == (n & ~(n - 1))) // zero or a power of two. 70 return floor; 71 else 72 return floor + 1; 73 } 74 75 // Splitting of distance and length codes into prefixes and 76 // extra bits. The prefixes are encoded with an entropy code 77 // while the extra bits are stored just as normal bits. 78 static WEBP_INLINE void PrefixEncode(int distance, int* const code, 79 int* const extra_bits_count, 80 int* const extra_bits_value) { 81 // Collect the two most significant bits where the highest bit is 1. 82 const int highest_bit = BitsLog2Floor(--distance); 83 // & 0x3f is to make behavior well defined when highest_bit 84 // does not exist or is the least significant bit. 85 const int second_highest_bit = 86 (distance >> ((highest_bit - 1) & 0x3f)) & 1; 87 *extra_bits_count = (highest_bit > 0) ? (highest_bit - 1) : 0; 88 *extra_bits_value = distance & ((1 << *extra_bits_count) - 1); 89 *code = (highest_bit > 0) ? (2 * highest_bit + second_highest_bit) 90 : (highest_bit == 0) ? 1 : 0; 91 } 92 93 // ----------------------------------------------------------------------------- 94 // PixOrCopy 95 96 enum Mode { 97 kLiteral, 98 kCacheIdx, 99 kCopy, 100 kNone 101 }; 102 103 typedef struct { 104 // mode as uint8_t to make the memory layout to be exactly 8 bytes. 105 uint8_t mode; 106 uint16_t len; 107 uint32_t argb_or_distance; 108 } PixOrCopy; 109 110 static WEBP_INLINE PixOrCopy PixOrCopyCreateCopy(uint32_t distance, 111 uint16_t len) { 112 PixOrCopy retval; 113 retval.mode = kCopy; 114 retval.argb_or_distance = distance; 115 retval.len = len; 116 return retval; 117 } 118 119 static WEBP_INLINE PixOrCopy PixOrCopyCreateCacheIdx(int idx) { 120 PixOrCopy retval; 121 assert(idx >= 0); 122 assert(idx < (1 << MAX_COLOR_CACHE_BITS)); 123 retval.mode = kCacheIdx; 124 retval.argb_or_distance = idx; 125 retval.len = 1; 126 return retval; 127 } 128 129 static WEBP_INLINE PixOrCopy PixOrCopyCreateLiteral(uint32_t argb) { 130 PixOrCopy retval; 131 retval.mode = kLiteral; 132 retval.argb_or_distance = argb; 133 retval.len = 1; 134 return retval; 135 } 136 137 static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) { 138 return (p->mode == kLiteral); 139 } 140 141 static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) { 142 return (p->mode == kCacheIdx); 143 } 144 145 static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) { 146 return (p->mode == kCopy); 147 } 148 149 static WEBP_INLINE uint32_t PixOrCopyLiteral(const PixOrCopy* const p, 150 int component) { 151 assert(p->mode == kLiteral); 152 return (p->argb_or_distance >> (component * 8)) & 0xff; 153 } 154 155 static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) { 156 return p->len; 157 } 158 159 static WEBP_INLINE uint32_t PixOrCopyArgb(const PixOrCopy* const p) { 160 assert(p->mode == kLiteral); 161 return p->argb_or_distance; 162 } 163 164 static WEBP_INLINE uint32_t PixOrCopyCacheIdx(const PixOrCopy* const p) { 165 assert(p->mode == kCacheIdx); 166 assert(p->argb_or_distance < (1U << MAX_COLOR_CACHE_BITS)); 167 return p->argb_or_distance; 168 } 169 170 static WEBP_INLINE uint32_t PixOrCopyDistance(const PixOrCopy* const p) { 171 assert(p->mode == kCopy); 172 return p->argb_or_distance; 173 } 174 175 // ----------------------------------------------------------------------------- 176 // VP8LBackwardRefs 177 178 typedef struct { 179 PixOrCopy* refs; 180 int size; // currently used 181 int max_size; // maximum capacity 182 } VP8LBackwardRefs; 183 184 // Initialize the object. Must be called first. 'refs' can be NULL. 185 void VP8LInitBackwardRefs(VP8LBackwardRefs* const refs); 186 187 // Release memory and re-initialize the object. 'refs' can be NULL. 188 void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); 189 190 // Allocate 'max_size' references. Returns false in case of memory error. 191 int VP8LBackwardRefsAlloc(VP8LBackwardRefs* const refs, int max_size); 192 193 // ----------------------------------------------------------------------------- 194 // Main entry points 195 196 // Evaluates best possible backward references for specified quality. 197 // Further optimize for 2D locality if use_2d_locality flag is set. 198 int VP8LGetBackwardReferences(int width, int height, 199 const uint32_t* const argb, 200 int quality, int cache_bits, int use_2d_locality, 201 VP8LBackwardRefs* const best); 202 203 // Produce an estimate for a good color cache size for the image. 204 int VP8LCalculateEstimateForCacheSize(const uint32_t* const argb, 205 int xsize, int ysize, 206 int* const best_cache_bits); 207 208 #if defined(__cplusplus) || defined(c_plusplus) 209 } 210 #endif 211 212 #endif // WEBP_ENC_BACKWARD_REFERENCES_H_ 213
