OLD | NEW |
(Empty) | |
| 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@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_ |
OLD | NEW |