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)
BitsLog2Floor(uint32_t n)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
VP8LBitsLog2Ceiling(uint32_t n)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.
PrefixEncode(int distance,int * const code,int * const extra_bits_count,int * const extra_bits_value)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
PixOrCopyCreateCopy(uint32_t distance,uint16_t len)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
PixOrCopyCreateCacheIdx(int idx)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
PixOrCopyCreateLiteral(uint32_t argb)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
PixOrCopyIsLiteral(const PixOrCopy * const p)137 static WEBP_INLINE int PixOrCopyIsLiteral(const PixOrCopy* const p) {
138 return (p->mode == kLiteral);
139 }
140
PixOrCopyIsCacheIdx(const PixOrCopy * const p)141 static WEBP_INLINE int PixOrCopyIsCacheIdx(const PixOrCopy* const p) {
142 return (p->mode == kCacheIdx);
143 }
144
PixOrCopyIsCopy(const PixOrCopy * const p)145 static WEBP_INLINE int PixOrCopyIsCopy(const PixOrCopy* const p) {
146 return (p->mode == kCopy);
147 }
148
PixOrCopyLiteral(const PixOrCopy * const p,int component)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
PixOrCopyLength(const PixOrCopy * const p)155 static WEBP_INLINE uint32_t PixOrCopyLength(const PixOrCopy* const p) {
156 return p->len;
157 }
158
PixOrCopyArgb(const PixOrCopy * const p)159 static WEBP_INLINE uint32_t PixOrCopyArgb(const PixOrCopy* const p) {
160 assert(p->mode == kLiteral);
161 return p->argb_or_distance;
162 }
163
PixOrCopyCacheIdx(const PixOrCopy * const p)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
PixOrCopyDistance(const PixOrCopy * const p)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