src/third_party/libwebp/dsp/lossless.h

   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 //------------------------------------------------------------------------------
  29 // Signatures and generic function-pointers
  30
  31 typedef uint32_t (*VP8LPredictorFunc)(uint32_t left, const uint32_t* const top);
  32 extern VP8LPredictorFunc VP8LPredictors[16];
  33
  34 typedef void (*VP8LProcessBlueAndRedFunc)(uint32_t* argb_data, int num_pixels);
  35 extern VP8LProcessBlueAndRedFunc VP8LSubtractGreenFromBlueAndRed;
  36 extern VP8LProcessBlueAndRedFunc VP8LAddGreenToBlueAndRed;
  37
  38 typedef struct {
  39   // Note: the members are uint8_t, so that any negative values are
  40   // automatically converted to "mod 256" values.
  41   uint8_t green_to_red_;
  42   uint8_t green_to_blue_;
  43   uint8_t red_to_blue_;
  44 } VP8LMultipliers;
  45 typedef void (*VP8LTransformColorFunc)(const VP8LMultipliers* const m,
  46                                        uint32_t* argb_data, int num_pixels);
  47 extern VP8LTransformColorFunc VP8LTransformColor;
  48 extern VP8LTransformColorFunc VP8LTransformColorInverse;
  49
  50 typedef void (*VP8LConvertFunc)(const uint32_t* src, int num_pixels,
  51                                 uint8_t* dst);
  52 extern VP8LConvertFunc VP8LConvertBGRAToRGB;
  53 extern VP8LConvertFunc VP8LConvertBGRAToRGBA;
  54 extern VP8LConvertFunc VP8LConvertBGRAToRGBA4444;
  55 extern VP8LConvertFunc VP8LConvertBGRAToRGB565;
  56 extern VP8LConvertFunc VP8LConvertBGRAToBGR;
  57
  58 // Expose some C-only fallback functions
  59 void VP8LTransformColor_C(const VP8LMultipliers* const m,
  60                           uint32_t* data, int num_pixels);
  61 void VP8LTransformColorInverse_C(const VP8LMultipliers* const m,
  62                                  uint32_t* data, int num_pixels);
  63
  64 void VP8LConvertBGRAToRGB_C(const uint32_t* src, int num_pixels, uint8_t* dst);
  65 void VP8LConvertBGRAToRGBA_C(const uint32_t* src, int num_pixels, uint8_t* dst);
  66 void VP8LConvertBGRAToRGBA4444_C(const uint32_t* src,
  67                                  int num_pixels, uint8_t* dst);
  68 void VP8LConvertBGRAToRGB565_C(const uint32_t* src,
  69                                int num_pixels, uint8_t* dst);
  70 void VP8LConvertBGRAToBGR_C(const uint32_t* src, int num_pixels, uint8_t* dst);
  71 void VP8LSubtractGreenFromBlueAndRed_C(uint32_t* argb_data, int num_pixels);
  72 void VP8LAddGreenToBlueAndRed_C(uint32_t* data, int num_pixels);
  73
  74 // Must be called before calling any of the above methods.
  75 void VP8LDspInit(void);
  76
  77 //------------------------------------------------------------------------------
  78 // Image transforms.
  79
  80 struct VP8LTransform;  // Defined in dec/vp8li.h.
  81
  82 // Performs inverse transform of data given transform information, start and end
  83 // rows. Transform will be applied to rows [row_start, row_end[.
  84 // The *in and *out pointers refer to source and destination data respectively
  85 // corresponding to the intermediate row (row_start).
  86 void VP8LInverseTransform(const struct VP8LTransform* const transform,
  87                           int row_start, int row_end,
  88                           const uint32_t* const in, uint32_t* const out);
  89
  90 // Similar to the static method ColorIndexInverseTransform() that is part of
  91 // lossless.c, but used only for alpha decoding. It takes uint8_t (rather than
  92 // uint32_t) arguments for 'src' and 'dst'.
  93 void VP8LColorIndexInverseTransformAlpha(
  94     const struct VP8LTransform* const transform, int y_start, int y_end,
  95     const uint8_t* src, uint8_t* dst);
  96
  97 void VP8LResidualImage(int width, int height, int bits,
  98                        uint32_t* const argb, uint32_t* const argb_scratch,
  99                        uint32_t* const image);
 100
 101 void VP8LColorSpaceTransform(int width, int height, int bits, int quality,
 102                              uint32_t* const argb, uint32_t* image);
 103
 104 //------------------------------------------------------------------------------
 105 // Color space conversion.
 106
 107 // Converts from BGRA to other color spaces.
 108 void VP8LConvertFromBGRA(const uint32_t* const in_data, int num_pixels,
 109                          WEBP_CSP_MODE out_colorspace, uint8_t* const rgba);
 110
 111 //------------------------------------------------------------------------------
 112 // Misc methods.
 113
 114 // Computes sampled size of 'size' when sampling using 'sampling bits'.
 115 static WEBP_INLINE uint32_t VP8LSubSampleSize(uint32_t size,
 116                                               uint32_t sampling_bits) {
 117   return (size + (1 << sampling_bits) - 1) >> sampling_bits;
 118 }
 119
 120 // -----------------------------------------------------------------------------
 121 // Faster logarithm for integers. Small values use a look-up table.
 122 #define LOG_LOOKUP_IDX_MAX 256
 123 extern const float kLog2Table[LOG_LOOKUP_IDX_MAX];
 124 extern const float kSLog2Table[LOG_LOOKUP_IDX_MAX];
 125 typedef float (*VP8LFastLog2SlowFunc)(uint32_t v);
 126
 127 extern VP8LFastLog2SlowFunc VP8LFastLog2Slow;
 128 extern VP8LFastLog2SlowFunc VP8LFastSLog2Slow;
 129
 130 static WEBP_INLINE float VP8LFastLog2(uint32_t v) {
 131   return (v < LOG_LOOKUP_IDX_MAX) ? kLog2Table[v] : VP8LFastLog2Slow(v);
 132 }
 133 // Fast calculation of v * log2(v) for integer input.
 134 static WEBP_INLINE float VP8LFastSLog2(uint32_t v) {
 135   return (v < LOG_LOOKUP_IDX_MAX) ? kSLog2Table[v] : VP8LFastSLog2Slow(v);
 136 }
 137
 138 // -----------------------------------------------------------------------------
 139 // Huffman-cost related functions.
 140
 141 typedef double (*VP8LCostFunc)(const uint32_t* population, int length);
 142 typedef double (*VP8LCostCombinedFunc)(const uint32_t* X, const uint32_t* Y,
 143                                        int length);
 144
 145 extern VP8LCostFunc VP8LExtraCost;
 146 extern VP8LCostCombinedFunc VP8LExtraCostCombined;
 147
 148 typedef struct {        // small struct to hold counters
 149   int counts[2];        // index: 0=zero steak, 1=non-zero streak
 150   int streaks[2][2];    // [zero/non-zero][streak<3 / streak>=3]
 151 } VP8LStreaks;
 152
 153 typedef VP8LStreaks (*VP8LCostCountFunc)(const uint32_t* population,
 154                                          int length);
 155 typedef VP8LStreaks (*VP8LCostCombinedCountFunc)(const uint32_t* X,
 156                                                  const uint32_t* Y, int length);
 157
 158 extern VP8LCostCountFunc VP8LHuffmanCostCount;
 159 extern VP8LCostCombinedCountFunc VP8LHuffmanCostCombinedCount;
 160
 161 typedef void (*VP8LHistogramAddFunc)(const VP8LHistogram* const a,
 162                                      const VP8LHistogram* const b,
 163                                      VP8LHistogram* const out);
 164 extern VP8LHistogramAddFunc VP8LHistogramAdd;
 165
 166 // -----------------------------------------------------------------------------
 167 // PrefixEncode()
 168
 169 static WEBP_INLINE int VP8LBitsLog2Ceiling(uint32_t n) {
 170   const int log_floor = BitsLog2Floor(n);
 171   if (n == (n & ~(n - 1)))  // zero or a power of two.
 172     return log_floor;
 173   else
 174     return log_floor + 1;
 175 }
 176
 177 // Splitting of distance and length codes into prefixes and
 178 // extra bits. The prefixes are encoded with an entropy code
 179 // while the extra bits are stored just as normal bits.
 180 static WEBP_INLINE void VP8LPrefixEncodeBitsNoLUT(int distance, int* const code,
 181                                                   int* const extra_bits) {
 182   const int highest_bit = BitsLog2Floor(--distance);
 183   const int second_highest_bit = (distance >> (highest_bit - 1)) & 1;
 184   *extra_bits = highest_bit - 1;
 185   *code = 2 * highest_bit + second_highest_bit;
 186 }
 187
 188 static WEBP_INLINE void VP8LPrefixEncodeNoLUT(int distance, int* const code,
 189                                               int* const extra_bits,
 190                                               int* const extra_bits_value) {
 191   const int highest_bit = BitsLog2Floor(--distance);
 192   const int second_highest_bit = (distance >> (highest_bit - 1)) & 1;
 193   *extra_bits = highest_bit - 1;
 194   *extra_bits_value = distance & ((1 << *extra_bits) - 1);
 195   *code = 2 * highest_bit + second_highest_bit;
 196 }
 197
 198 #define PREFIX_LOOKUP_IDX_MAX   512
 199 typedef struct {
 200   int8_t code_;
 201   int8_t extra_bits_;
 202 } VP8LPrefixCode;
 203
 204 // These tables are derived using VP8LPrefixEncodeNoLUT.
 205 extern const VP8LPrefixCode kPrefixEncodeCode[PREFIX_LOOKUP_IDX_MAX];
 206 extern const uint8_t kPrefixEncodeExtraBitsValue[PREFIX_LOOKUP_IDX_MAX];
 207 static WEBP_INLINE void VP8LPrefixEncodeBits(int distance, int* const code,
 208                                              int* const extra_bits) {
 209   if (distance < PREFIX_LOOKUP_IDX_MAX) {
 210     const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance];
 211     *code = prefix_code.code_;
 212     *extra_bits = prefix_code.extra_bits_;
 213   } else {
 214     VP8LPrefixEncodeBitsNoLUT(distance, code, extra_bits);
 215   }
 216 }
 217
 218 static WEBP_INLINE void VP8LPrefixEncode(int distance, int* const code,
 219                                          int* const extra_bits,
 220                                          int* const extra_bits_value) {
 221   if (distance < PREFIX_LOOKUP_IDX_MAX) {
 222     const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance];
 223     *code = prefix_code.code_;
 224     *extra_bits = prefix_code.extra_bits_;
 225     *extra_bits_value = kPrefixEncodeExtraBitsValue[distance];
 226   } else {
 227     VP8LPrefixEncodeNoLUT(distance, code, extra_bits, extra_bits_value);
 228   }
 229 }
 230
 231 // In-place difference of each component with mod 256.
 232 static WEBP_INLINE uint32_t VP8LSubPixels(uint32_t a, uint32_t b) {
 233   const uint32_t alpha_and_green =
 234       0x00ff00ffu + (a & 0xff00ff00u) - (b & 0xff00ff00u);
 235   const uint32_t red_and_blue =
 236       0xff00ff00u + (a & 0x00ff00ffu) - (b & 0x00ff00ffu);
 237   return (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu);
 238 }
 239
 240 void VP8LBundleColorMap(const uint8_t* const row, int width,
 241                         int xbits, uint32_t* const dst);
 242
 243 //------------------------------------------------------------------------------
 244
 245 #ifdef __cplusplus
 246 }    // extern "C"
 247 #endif
 248
 249 #endif  // WEBP_DSP_LOSSLESS_H_