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
25extern "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
35typedef uint32_t (*VP8LPredictorFunc)(uint32_t left, const uint32_t* const top);
36extern VP8LPredictorFunc VP8LPredictors[16];
37
38typedef void (*VP8LProcessBlueAndRedFunc)(uint32_t* argb_data, int num_pixels);
39extern VP8LProcessBlueAndRedFunc VP8LAddGreenToBlueAndRed;
40
41typedef 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;
48typedef void (*VP8LTransformColorFunc)(const VP8LMultipliers* const m,
49                                       uint32_t* argb_data, int num_pixels);
50extern VP8LTransformColorFunc VP8LTransformColorInverse;
51
52struct 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).
58void 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.
63typedef void (*VP8LConvertFunc)(const uint32_t* src, int num_pixels,
64                                uint8_t* dst);
65extern VP8LConvertFunc VP8LConvertBGRAToRGB;
66extern VP8LConvertFunc VP8LConvertBGRAToRGBA;
67extern VP8LConvertFunc VP8LConvertBGRAToRGBA4444;
68extern VP8LConvertFunc VP8LConvertBGRAToRGB565;
69extern VP8LConvertFunc VP8LConvertBGRAToBGR;
70
71// Converts from BGRA to other color spaces.
72void 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.
76static WEBP_INLINE uint32_t VP8GetARGBIndex(uint32_t idx) {
77  return (idx >> 8) & 0xff;
78}
79
80static WEBP_INLINE uint8_t VP8GetAlphaIndex(uint8_t idx) {
81  return idx;
82}
83
84static WEBP_INLINE uint32_t VP8GetARGBValue(uint32_t val) {
85  return val;
86}
87
88static WEBP_INLINE uint8_t VP8GetAlphaValue(uint32_t val) {
89  return (val >> 8) & 0xff;
90}
91
92typedef 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);
96typedef 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
101extern VP8LMapARGBFunc VP8LMapColor32b;
102extern 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'.
107void 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
112void VP8LTransformColorInverse_C(const VP8LMultipliers* const m,
113                                 uint32_t* data, int num_pixels);
114
115void VP8LConvertBGRAToRGB_C(const uint32_t* src, int num_pixels, uint8_t* dst);
116void VP8LConvertBGRAToRGBA_C(const uint32_t* src, int num_pixels, uint8_t* dst);
117void VP8LConvertBGRAToRGBA4444_C(const uint32_t* src,
118                                 int num_pixels, uint8_t* dst);
119void VP8LConvertBGRAToRGB565_C(const uint32_t* src,
120                               int num_pixels, uint8_t* dst);
121void VP8LConvertBGRAToBGR_C(const uint32_t* src, int num_pixels, uint8_t* dst);
122void VP8LAddGreenToBlueAndRed_C(uint32_t* data, int num_pixels);
123
124// Must be called before calling any of the above methods.
125void VP8LDspInit(void);
126
127//------------------------------------------------------------------------------
128// Encoding
129
130extern VP8LProcessBlueAndRedFunc VP8LSubtractGreenFromBlueAndRed;
131extern VP8LTransformColorFunc VP8LTransformColor;
132typedef 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[]);
136extern VP8LCollectColorBlueTransformsFunc VP8LCollectColorBlueTransforms;
137
138typedef void (*VP8LCollectColorRedTransformsFunc)(
139    const uint32_t* argb, int stride,
140    int tile_width, int tile_height,
141    int green_to_red, int histo[]);
142extern VP8LCollectColorRedTransformsFunc VP8LCollectColorRedTransforms;
143
144// Expose some C-only fallback functions
145void VP8LTransformColor_C(const VP8LMultipliers* const m,
146                          uint32_t* data, int num_pixels);
147void VP8LSubtractGreenFromBlueAndRed_C(uint32_t* argb_data, int num_pixels);
148void VP8LCollectColorRedTransforms_C(const uint32_t* argb, int stride,
149                                     int tile_width, int tile_height,
150                                     int green_to_red, int histo[]);
151void 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
159void 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
163void 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'.
170static 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
186extern const float kLog2Table[LOG_LOOKUP_IDX_MAX];
187extern const float kSLog2Table[LOG_LOOKUP_IDX_MAX];
188typedef float (*VP8LFastLog2SlowFunc)(uint32_t v);
189
190extern VP8LFastLog2SlowFunc VP8LFastLog2Slow;
191extern VP8LFastLog2SlowFunc VP8LFastSLog2Slow;
192
193static 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.
197static 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
204typedef double (*VP8LCostFunc)(const uint32_t* population, int length);
205typedef double (*VP8LCostCombinedFunc)(const uint32_t* X, const uint32_t* Y,
206                                       int length);
207typedef float (*VP8LCombinedShannonEntropyFunc)(const int X[256],
208                                                const int Y[256]);
209
210extern VP8LCostFunc VP8LExtraCost;
211extern VP8LCostCombinedFunc VP8LExtraCostCombined;
212extern VP8LCombinedShannonEntropyFunc VP8LCombinedShannonEntropy;
213
214typedef 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
219typedef VP8LStreaks (*VP8LCostCombinedCountFunc)(const uint32_t* X,
220                                                 const uint32_t* Y, int length);
221
222extern VP8LCostCombinedCountFunc VP8LHuffmanCostCombinedCount;
223
224typedef 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
232void 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.
237void 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'.
242void VP8LGetEntropyUnrefined(const uint32_t* const X, int length,
243                             VP8LBitEntropy* const bit_entropy,
244                             VP8LStreaks* const stats);
245
246void VP8LBitsEntropyUnrefined(const uint32_t* const array, int n,
247                              VP8LBitEntropy* const entropy);
248
249typedef 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.
255extern GetEntropyUnrefinedHelperFunc VP8LGetEntropyUnrefinedHelper;
256
257typedef void (*VP8LHistogramAddFunc)(const VP8LHistogram* const a,
258                                     const VP8LHistogram* const b,
259                                     VP8LHistogram* const out);
260extern VP8LHistogramAddFunc VP8LHistogramAdd;
261
262// -----------------------------------------------------------------------------
263// PrefixEncode()
264
265static 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.
276static 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
284static 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
295typedef struct {
296  int8_t code_;
297  int8_t extra_bits_;
298} VP8LPrefixCode;
299
300// These tables are derived using VP8LPrefixEncodeNoLUT.
301extern const VP8LPrefixCode kPrefixEncodeCode[PREFIX_LOOKUP_IDX_MAX];
302extern const uint8_t kPrefixEncodeExtraBitsValue[PREFIX_LOOKUP_IDX_MAX];
303static 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
314static 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.
328static 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
336void 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.
340void VP8LEncDspInit(void);
341
342//------------------------------------------------------------------------------
343
344#ifdef __cplusplus
345}    // extern "C"
346#endif
347
348#endif  // WEBP_DSP_LOSSLESS_H_
349