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 // Image transforms and color space conversion methods for lossless decoder.
11 //
12 // Authors: Vikas Arora (vikaas.arora@gmail.com)
13 // Jyrki Alakuijala (jyrki@google.com)
14
15 #ifndef WEBP_DSP_LOSSLESS_H_
16 #define WEBP_DSP_LOSSLESS_H_
17
18 #include "../webp/types.h"
19 #include "../webp/decode.h"
20
21 #include "../enc/histogram.h"
22 #include "../utils/utils.h"
23
24 #ifdef __cplusplus
25 extern "C" {
26 #endif
27
28 #ifdef WEBP_EXPERIMENTAL_FEATURES
29 #include "../enc/delta_palettization.h"
30 #endif // WEBP_EXPERIMENTAL_FEATURES
31
32 //------------------------------------------------------------------------------
33 // Decoding
34
35 typedef uint32_t (*VP8LPredictorFunc)(uint32_t left, const uint32_t* const top);
36 extern VP8LPredictorFunc VP8LPredictors[16];
37
38 typedef void (*VP8LProcessBlueAndRedFunc)(uint32_t* argb_data, int num_pixels);
39 extern VP8LProcessBlueAndRedFunc VP8LAddGreenToBlueAndRed;
40
41 typedef struct {
42 // Note: the members are uint8_t, so that any negative values are
43 // automatically converted to "mod 256" values.
44 uint8_t green_to_red_;
45 uint8_t green_to_blue_;
46 uint8_t red_to_blue_;
47 } VP8LMultipliers;
48 typedef void (*VP8LTransformColorFunc)(const VP8LMultipliers* const m,
49 uint32_t* argb_data, int num_pixels);
50 extern VP8LTransformColorFunc VP8LTransformColorInverse;
51
52 struct VP8LTransform; // Defined in dec/vp8li.h.
53
54 // Performs inverse transform of data given transform information, start and end
55 // rows. Transform will be applied to rows [row_start, row_end[.
56 // The *in and *out pointers refer to source and destination data respectively
57 // corresponding to the intermediate row (row_start).
58 void VP8LInverseTransform(const struct VP8LTransform* const transform,
59 int row_start, int row_end,
60 const uint32_t* const in, uint32_t* const out);
61
62 // Color space conversion.
63 typedef void (*VP8LConvertFunc)(const uint32_t* src, int num_pixels,
64 uint8_t* dst);
65 extern VP8LConvertFunc VP8LConvertBGRAToRGB;
66 extern VP8LConvertFunc VP8LConvertBGRAToRGBA;
67 extern VP8LConvertFunc VP8LConvertBGRAToRGBA4444;
68 extern VP8LConvertFunc VP8LConvertBGRAToRGB565;
69 extern VP8LConvertFunc VP8LConvertBGRAToBGR;
70
71 // Converts from BGRA to other color spaces.
72 void VP8LConvertFromBGRA(const uint32_t* const in_data, int num_pixels,
73 WEBP_CSP_MODE out_colorspace, uint8_t* const rgba);
74
75 // color mapping related functions.
VP8GetARGBIndex(uint32_t idx)76 static WEBP_INLINE uint32_t VP8GetARGBIndex(uint32_t idx) {
77 return (idx >> 8) & 0xff;
78 }
79
VP8GetAlphaIndex(uint8_t idx)80 static WEBP_INLINE uint8_t VP8GetAlphaIndex(uint8_t idx) {
81 return idx;
82 }
83
VP8GetARGBValue(uint32_t val)84 static WEBP_INLINE uint32_t VP8GetARGBValue(uint32_t val) {
85 return val;
86 }
87
VP8GetAlphaValue(uint32_t val)88 static WEBP_INLINE uint8_t VP8GetAlphaValue(uint32_t val) {
89 return (val >> 8) & 0xff;
90 }
91
92 typedef void (*VP8LMapARGBFunc)(const uint32_t* src,
93 const uint32_t* const color_map,
94 uint32_t* dst, int y_start,
95 int y_end, int width);
96 typedef void (*VP8LMapAlphaFunc)(const uint8_t* src,
97 const uint32_t* const color_map,
98 uint8_t* dst, int y_start,
99 int y_end, int width);
100
101 extern VP8LMapARGBFunc VP8LMapColor32b;
102 extern VP8LMapAlphaFunc VP8LMapColor8b;
103
104 // Similar to the static method ColorIndexInverseTransform() that is part of
105 // lossless.c, but used only for alpha decoding. It takes uint8_t (rather than
106 // uint32_t) arguments for 'src' and 'dst'.
107 void VP8LColorIndexInverseTransformAlpha(
108 const struct VP8LTransform* const transform, int y_start, int y_end,
109 const uint8_t* src, uint8_t* dst);
110
111 // Expose some C-only fallback functions
112 void VP8LTransformColorInverse_C(const VP8LMultipliers* const m,
113 uint32_t* data, int num_pixels);
114
115 void VP8LConvertBGRAToRGB_C(const uint32_t* src, int num_pixels, uint8_t* dst);
116 void VP8LConvertBGRAToRGBA_C(const uint32_t* src, int num_pixels, uint8_t* dst);
117 void VP8LConvertBGRAToRGBA4444_C(const uint32_t* src,
118 int num_pixels, uint8_t* dst);
119 void VP8LConvertBGRAToRGB565_C(const uint32_t* src,
120 int num_pixels, uint8_t* dst);
121 void VP8LConvertBGRAToBGR_C(const uint32_t* src, int num_pixels, uint8_t* dst);
122 void VP8LAddGreenToBlueAndRed_C(uint32_t* data, int num_pixels);
123
124 // Must be called before calling any of the above methods.
125 void VP8LDspInit(void);
126
127 //------------------------------------------------------------------------------
128 // Encoding
129
130 extern VP8LProcessBlueAndRedFunc VP8LSubtractGreenFromBlueAndRed;
131 extern VP8LTransformColorFunc VP8LTransformColor;
132 typedef void (*VP8LCollectColorBlueTransformsFunc)(
133 const uint32_t* argb, int stride,
134 int tile_width, int tile_height,
135 int green_to_blue, int red_to_blue, int histo[]);
136 extern VP8LCollectColorBlueTransformsFunc VP8LCollectColorBlueTransforms;
137
138 typedef void (*VP8LCollectColorRedTransformsFunc)(
139 const uint32_t* argb, int stride,
140 int tile_width, int tile_height,
141 int green_to_red, int histo[]);
142 extern VP8LCollectColorRedTransformsFunc VP8LCollectColorRedTransforms;
143
144 // Expose some C-only fallback functions
145 void VP8LTransformColor_C(const VP8LMultipliers* const m,
146 uint32_t* data, int num_pixels);
147 void VP8LSubtractGreenFromBlueAndRed_C(uint32_t* argb_data, int num_pixels);
148 void VP8LCollectColorRedTransforms_C(const uint32_t* argb, int stride,
149 int tile_width, int tile_height,
150 int green_to_red, int histo[]);
151 void VP8LCollectColorBlueTransforms_C(const uint32_t* argb, int stride,
152 int tile_width, int tile_height,
153 int green_to_blue, int red_to_blue,
154 int histo[]);
155
156 //------------------------------------------------------------------------------
157 // Image transforms.
158
159 void VP8LResidualImage(int width, int height, int bits, int low_effort,
160 uint32_t* const argb, uint32_t* const argb_scratch,
161 uint32_t* const image, int exact);
162
163 void VP8LColorSpaceTransform(int width, int height, int bits, int quality,
164 uint32_t* const argb, uint32_t* image);
165
166 //------------------------------------------------------------------------------
167 // Misc methods.
168
169 // Computes sampled size of 'size' when sampling using 'sampling bits'.
VP8LSubSampleSize(uint32_t size,uint32_t sampling_bits)170 static WEBP_INLINE uint32_t VP8LSubSampleSize(uint32_t size,
171 uint32_t sampling_bits) {
172 return (size + (1 << sampling_bits) - 1) >> sampling_bits;
173 }
174
175 // -----------------------------------------------------------------------------
176 // Faster logarithm for integers. Small values use a look-up table.
177
178 // The threshold till approximate version of log_2 can be used.
179 // Practically, we can get rid of the call to log() as the two values match to
180 // very high degree (the ratio of these two is 0.99999x).
181 // Keeping a high threshold for now.
182 #define APPROX_LOG_WITH_CORRECTION_MAX 65536
183 #define APPROX_LOG_MAX 4096
184 #define LOG_2_RECIPROCAL 1.44269504088896338700465094007086
185 #define LOG_LOOKUP_IDX_MAX 256
186 extern const float kLog2Table[LOG_LOOKUP_IDX_MAX];
187 extern const float kSLog2Table[LOG_LOOKUP_IDX_MAX];
188 typedef float (*VP8LFastLog2SlowFunc)(uint32_t v);
189
190 extern VP8LFastLog2SlowFunc VP8LFastLog2Slow;
191 extern VP8LFastLog2SlowFunc VP8LFastSLog2Slow;
192
VP8LFastLog2(uint32_t v)193 static WEBP_INLINE float VP8LFastLog2(uint32_t v) {
194 return (v < LOG_LOOKUP_IDX_MAX) ? kLog2Table[v] : VP8LFastLog2Slow(v);
195 }
196 // Fast calculation of v * log2(v) for integer input.
VP8LFastSLog2(uint32_t v)197 static WEBP_INLINE float VP8LFastSLog2(uint32_t v) {
198 return (v < LOG_LOOKUP_IDX_MAX) ? kSLog2Table[v] : VP8LFastSLog2Slow(v);
199 }
200
201 // -----------------------------------------------------------------------------
202 // Huffman-cost related functions.
203
204 typedef double (*VP8LCostFunc)(const uint32_t* population, int length);
205 typedef double (*VP8LCostCombinedFunc)(const uint32_t* X, const uint32_t* Y,
206 int length);
207 typedef float (*VP8LCombinedShannonEntropyFunc)(const int X[256],
208 const int Y[256]);
209
210 extern VP8LCostFunc VP8LExtraCost;
211 extern VP8LCostCombinedFunc VP8LExtraCostCombined;
212 extern VP8LCombinedShannonEntropyFunc VP8LCombinedShannonEntropy;
213
214 typedef struct { // small struct to hold counters
215 int counts[2]; // index: 0=zero steak, 1=non-zero streak
216 int streaks[2][2]; // [zero/non-zero][streak<3 / streak>=3]
217 } VP8LStreaks;
218
219 typedef VP8LStreaks (*VP8LCostCombinedCountFunc)(const uint32_t* X,
220 const uint32_t* Y, int length);
221
222 extern VP8LCostCombinedCountFunc VP8LHuffmanCostCombinedCount;
223
224 typedef struct { // small struct to hold bit entropy results
225 double entropy; // entropy
226 uint32_t sum; // sum of the population
227 int nonzeros; // number of non-zero elements in the population
228 uint32_t max_val; // maximum value in the population
229 uint32_t nonzero_code; // index of the last non-zero in the population
230 } VP8LBitEntropy;
231
232 void VP8LBitEntropyInit(VP8LBitEntropy* const entropy);
233
234 // Get the combined symbol bit entropy and Huffman cost stats for the
235 // distributions 'X' and 'Y'. Those results can then be refined according to
236 // codec specific heuristics.
237 void VP8LGetCombinedEntropyUnrefined(const uint32_t* const X,
238 const uint32_t* const Y, int length,
239 VP8LBitEntropy* const bit_entropy,
240 VP8LStreaks* const stats);
241 // Get the entropy for the distribution 'X'.
242 void VP8LGetEntropyUnrefined(const uint32_t* const X, int length,
243 VP8LBitEntropy* const bit_entropy,
244 VP8LStreaks* const stats);
245
246 void VP8LBitsEntropyUnrefined(const uint32_t* const array, int n,
247 VP8LBitEntropy* const entropy);
248
249 typedef void (*GetEntropyUnrefinedHelperFunc)(uint32_t val, int i,
250 uint32_t* const val_prev,
251 int* const i_prev,
252 VP8LBitEntropy* const bit_entropy,
253 VP8LStreaks* const stats);
254 // Internal function used by VP8LGet*EntropyUnrefined.
255 extern GetEntropyUnrefinedHelperFunc VP8LGetEntropyUnrefinedHelper;
256
257 typedef void (*VP8LHistogramAddFunc)(const VP8LHistogram* const a,
258 const VP8LHistogram* const b,
259 VP8LHistogram* const out);
260 extern VP8LHistogramAddFunc VP8LHistogramAdd;
261
262 // -----------------------------------------------------------------------------
263 // PrefixEncode()
264
VP8LBitsLog2Ceiling(uint32_t n)265 static WEBP_INLINE int VP8LBitsLog2Ceiling(uint32_t n) {
266 const int log_floor = BitsLog2Floor(n);
267 if (n == (n & ~(n - 1))) // zero or a power of two.
268 return log_floor;
269 else
270 return log_floor + 1;
271 }
272
273 // Splitting of distance and length codes into prefixes and
274 // extra bits. The prefixes are encoded with an entropy code
275 // while the extra bits are stored just as normal bits.
VP8LPrefixEncodeBitsNoLUT(int distance,int * const code,int * const extra_bits)276 static WEBP_INLINE void VP8LPrefixEncodeBitsNoLUT(int distance, int* const code,
277 int* const extra_bits) {
278 const int highest_bit = BitsLog2Floor(--distance);
279 const int second_highest_bit = (distance >> (highest_bit - 1)) & 1;
280 *extra_bits = highest_bit - 1;
281 *code = 2 * highest_bit + second_highest_bit;
282 }
283
VP8LPrefixEncodeNoLUT(int distance,int * const code,int * const extra_bits,int * const extra_bits_value)284 static WEBP_INLINE void VP8LPrefixEncodeNoLUT(int distance, int* const code,
285 int* const extra_bits,
286 int* const extra_bits_value) {
287 const int highest_bit = BitsLog2Floor(--distance);
288 const int second_highest_bit = (distance >> (highest_bit - 1)) & 1;
289 *extra_bits = highest_bit - 1;
290 *extra_bits_value = distance & ((1 << *extra_bits) - 1);
291 *code = 2 * highest_bit + second_highest_bit;
292 }
293
294 #define PREFIX_LOOKUP_IDX_MAX 512
295 typedef struct {
296 int8_t code_;
297 int8_t extra_bits_;
298 } VP8LPrefixCode;
299
300 // These tables are derived using VP8LPrefixEncodeNoLUT.
301 extern const VP8LPrefixCode kPrefixEncodeCode[PREFIX_LOOKUP_IDX_MAX];
302 extern const uint8_t kPrefixEncodeExtraBitsValue[PREFIX_LOOKUP_IDX_MAX];
VP8LPrefixEncodeBits(int distance,int * const code,int * const extra_bits)303 static WEBP_INLINE void VP8LPrefixEncodeBits(int distance, int* const code,
304 int* const extra_bits) {
305 if (distance < PREFIX_LOOKUP_IDX_MAX) {
306 const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance];
307 *code = prefix_code.code_;
308 *extra_bits = prefix_code.extra_bits_;
309 } else {
310 VP8LPrefixEncodeBitsNoLUT(distance, code, extra_bits);
311 }
312 }
313
VP8LPrefixEncode(int distance,int * const code,int * const extra_bits,int * const extra_bits_value)314 static WEBP_INLINE void VP8LPrefixEncode(int distance, int* const code,
315 int* const extra_bits,
316 int* const extra_bits_value) {
317 if (distance < PREFIX_LOOKUP_IDX_MAX) {
318 const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance];
319 *code = prefix_code.code_;
320 *extra_bits = prefix_code.extra_bits_;
321 *extra_bits_value = kPrefixEncodeExtraBitsValue[distance];
322 } else {
323 VP8LPrefixEncodeNoLUT(distance, code, extra_bits, extra_bits_value);
324 }
325 }
326
327 // In-place difference of each component with mod 256.
VP8LSubPixels(uint32_t a,uint32_t b)328 static WEBP_INLINE uint32_t VP8LSubPixels(uint32_t a, uint32_t b) {
329 const uint32_t alpha_and_green =
330 0x00ff00ffu + (a & 0xff00ff00u) - (b & 0xff00ff00u);
331 const uint32_t red_and_blue =
332 0xff00ff00u + (a & 0x00ff00ffu) - (b & 0x00ff00ffu);
333 return (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu);
334 }
335
336 void VP8LBundleColorMap(const uint8_t* const row, int width,
337 int xbits, uint32_t* const dst);
338
339 // Must be called before calling any of the above methods.
340 void VP8LEncDspInit(void);
341
342 //------------------------------------------------------------------------------
343
344 #ifdef __cplusplus
345 } // extern "C"
346 #endif
347
348 #endif // WEBP_DSP_LOSSLESS_H_
349