lossless.h revision 8b720228d581a84fd173b6dcb2fa295b59db489a 
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#ifdef __cplusplus
22extern "C" {
23#endif
24
25//------------------------------------------------------------------------------
26//
27
28typedef uint32_t (*VP8LPredClampedAddSubFunc)(uint32_t c0, uint32_t c1,
29                                              uint32_t c2);
30typedef uint32_t (*VP8LPredSelectFunc)(uint32_t c0, uint32_t c1, uint32_t c2);
31typedef void (*VP8LSubtractGreenFromBlueAndRedFunc)(uint32_t* argb_data,
32                                                    int num_pixs);
33typedef void (*VP8LAddGreenToBlueAndRedFunc)(uint32_t* data_start,
34                                             const uint32_t* data_end);
35
36extern VP8LPredClampedAddSubFunc VP8LClampedAddSubtractFull;
37extern VP8LPredClampedAddSubFunc VP8LClampedAddSubtractHalf;
38extern VP8LPredSelectFunc VP8LSelect;
39extern VP8LSubtractGreenFromBlueAndRedFunc VP8LSubtractGreenFromBlueAndRed;
40extern VP8LAddGreenToBlueAndRedFunc VP8LAddGreenToBlueAndRed;
41
42// Must be called before calling any of the above methods.
43void VP8LDspInit(void);
44
45//------------------------------------------------------------------------------
46// Image transforms.
47
48struct VP8LTransform;  // Defined in dec/vp8li.h.
49
50// Performs inverse transform of data given transform information, start and end
51// rows. Transform will be applied to rows [row_start, row_end[.
52// The *in and *out pointers refer to source and destination data respectively
53// corresponding to the intermediate row (row_start).
54void VP8LInverseTransform(const struct VP8LTransform* const transform,
55                          int row_start, int row_end,
56                          const uint32_t* const in, uint32_t* const out);
57
58// Similar to the static method ColorIndexInverseTransform() that is part of
59// lossless.c, but used only for alpha decoding. It takes uint8_t (rather than
60// uint32_t) arguments for 'src' and 'dst'.
61void VP8LColorIndexInverseTransformAlpha(
62    const struct VP8LTransform* const transform, int y_start, int y_end,
63    const uint8_t* src, uint8_t* dst);
64
65void VP8LResidualImage(int width, int height, int bits,
66                       uint32_t* const argb, uint32_t* const argb_scratch,
67                       uint32_t* const image);
68
69void VP8LColorSpaceTransform(int width, int height, int bits, int step,
70                             uint32_t* const argb, uint32_t* image);
71
72//------------------------------------------------------------------------------
73// Color space conversion.
74
75// Converts from BGRA to other color spaces.
76void VP8LConvertFromBGRA(const uint32_t* const in_data, int num_pixels,
77                         WEBP_CSP_MODE out_colorspace, uint8_t* const rgba);
78
79//------------------------------------------------------------------------------
80// Misc methods.
81
82// Computes sampled size of 'size' when sampling using 'sampling bits'.
83static WEBP_INLINE uint32_t VP8LSubSampleSize(uint32_t size,
84                                              uint32_t sampling_bits) {
85  return (size + (1 << sampling_bits) - 1) >> sampling_bits;
86}
87
88// Faster logarithm for integers. Small values use a look-up table.
89#define LOG_LOOKUP_IDX_MAX 256
90extern const float kLog2Table[LOG_LOOKUP_IDX_MAX];
91extern const float kSLog2Table[LOG_LOOKUP_IDX_MAX];
92float VP8LFastLog2Slow(int v);
93float VP8LFastSLog2Slow(int v);
94static WEBP_INLINE float VP8LFastLog2(int v) {
95  return (v < LOG_LOOKUP_IDX_MAX) ? kLog2Table[v] : VP8LFastLog2Slow(v);
96}
97// Fast calculation of v * log2(v) for integer input.
98static WEBP_INLINE float VP8LFastSLog2(int v) {
99  return (v < LOG_LOOKUP_IDX_MAX) ? kSLog2Table[v] : VP8LFastSLog2Slow(v);
100}
101
102// -----------------------------------------------------------------------------
103// PrefixEncode()
104
105// use GNU builtins where available.
106#if defined(__GNUC__) && \
107    ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4)
108static WEBP_INLINE int BitsLog2Floor(uint32_t n) {
109  return 31 ^ __builtin_clz(n);
110}
111#elif defined(_MSC_VER) && _MSC_VER > 1310 && \
112      (defined(_M_X64) || defined(_M_IX86))
113#include <intrin.h>
114#pragma intrinsic(_BitScanReverse)
115
116static WEBP_INLINE int BitsLog2Floor(uint32_t n) {
117  unsigned long first_set_bit;
118  _BitScanReverse(&first_set_bit, n);
119  return first_set_bit;
120}
121#else
122// Returns (int)floor(log2(n)). n must be > 0.
123static WEBP_INLINE int BitsLog2Floor(uint32_t n) {
124  int log = 0;
125  uint32_t value = n;
126  int i;
127
128  for (i = 4; i >= 0; --i) {
129    const int shift = (1 << i);
130    const uint32_t x = value >> shift;
131    if (x != 0) {
132      value = x;
133      log += shift;
134    }
135  }
136  return log;
137}
138#endif
139
140static WEBP_INLINE int VP8LBitsLog2Ceiling(uint32_t n) {
141  const int log_floor = BitsLog2Floor(n);
142  if (n == (n & ~(n - 1)))  // zero or a power of two.
143    return log_floor;
144  else
145    return log_floor + 1;
146}
147
148// Splitting of distance and length codes into prefixes and
149// extra bits. The prefixes are encoded with an entropy code
150// while the extra bits are stored just as normal bits.
151static WEBP_INLINE void VP8LPrefixEncodeBitsNoLUT(int distance, int* const code,
152                                                  int* const extra_bits) {
153  const int highest_bit = BitsLog2Floor(--distance);
154  const int second_highest_bit = (distance >> (highest_bit - 1)) & 1;
155  *extra_bits = highest_bit - 1;
156  *code = 2 * highest_bit + second_highest_bit;
157}
158
159static WEBP_INLINE void VP8LPrefixEncodeNoLUT(int distance, int* const code,
160                                              int* const extra_bits,
161                                              int* const extra_bits_value) {
162  const int highest_bit = BitsLog2Floor(--distance);
163  const int second_highest_bit = (distance >> (highest_bit - 1)) & 1;
164  *extra_bits = highest_bit - 1;
165  *extra_bits_value = distance & ((1 << *extra_bits) - 1);
166  *code = 2 * highest_bit + second_highest_bit;
167}
168
169#define PREFIX_LOOKUP_IDX_MAX   512
170typedef struct {
171  int8_t code_;
172  int8_t extra_bits_;
173} VP8LPrefixCode;
174
175// These tables are derived using VP8LPrefixEncodeNoLUT.
176extern const VP8LPrefixCode kPrefixEncodeCode[PREFIX_LOOKUP_IDX_MAX];
177extern const uint8_t kPrefixEncodeExtraBitsValue[PREFIX_LOOKUP_IDX_MAX];
178static WEBP_INLINE void VP8LPrefixEncodeBits(int distance, int* const code,
179                                             int* const extra_bits) {
180  if (distance < PREFIX_LOOKUP_IDX_MAX) {
181    const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance];
182    *code = prefix_code.code_;
183    *extra_bits = prefix_code.extra_bits_;
184  } else {
185    VP8LPrefixEncodeBitsNoLUT(distance, code, extra_bits);
186  }
187}
188
189static WEBP_INLINE void VP8LPrefixEncode(int distance, int* const code,
190                                         int* const extra_bits,
191                                         int* const extra_bits_value) {
192  if (distance < PREFIX_LOOKUP_IDX_MAX) {
193    const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance];
194    *code = prefix_code.code_;
195    *extra_bits = prefix_code.extra_bits_;
196    *extra_bits_value = kPrefixEncodeExtraBitsValue[distance];
197  } else {
198    VP8LPrefixEncodeNoLUT(distance, code, extra_bits, extra_bits_value);
199  }
200}
201
202// In-place difference of each component with mod 256.
203static WEBP_INLINE uint32_t VP8LSubPixels(uint32_t a, uint32_t b) {
204  const uint32_t alpha_and_green =
205      0x00ff00ffu + (a & 0xff00ff00u) - (b & 0xff00ff00u);
206  const uint32_t red_and_blue =
207      0xff00ff00u + (a & 0x00ff00ffu) - (b & 0x00ff00ffu);
208  return (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu);
209}
210
211void VP8LBundleColorMap(const uint8_t* const row, int width,
212                        int xbits, uint32_t* const dst);
213
214//------------------------------------------------------------------------------
215
216#ifdef __cplusplus
217}    // extern "C"
218#endif
219
220#endif  // WEBP_DSP_LOSSLESS_H_
221