1fa39824bb690c5806358871f46940d0450973d8aJames Zern// Copyright 2012 Google Inc. All Rights Reserved. 2fa39824bb690c5806358871f46940d0450973d8aJames Zern// 3fa39824bb690c5806358871f46940d0450973d8aJames Zern// Use of this source code is governed by a BSD-style license 4fa39824bb690c5806358871f46940d0450973d8aJames Zern// that can be found in the COPYING file in the root of the source 5fa39824bb690c5806358871f46940d0450973d8aJames Zern// tree. An additional intellectual property rights grant can be found 6fa39824bb690c5806358871f46940d0450973d8aJames Zern// in the file PATENTS. All contributing project authors may 7fa39824bb690c5806358871f46940d0450973d8aJames Zern// be found in the AUTHORS file in the root of the source tree. 8fa39824bb690c5806358871f46940d0450973d8aJames Zern// ----------------------------------------------------------------------------- 9fa39824bb690c5806358871f46940d0450973d8aJames Zern// 10fa39824bb690c5806358871f46940d0450973d8aJames Zern// Image transforms and color space conversion methods for lossless decoder. 11fa39824bb690c5806358871f46940d0450973d8aJames Zern// 12fa39824bb690c5806358871f46940d0450973d8aJames Zern// Authors: Vikas Arora (vikaas.arora@gmail.com) 13fa39824bb690c5806358871f46940d0450973d8aJames Zern// Jyrki Alakuijala (jyrki@google.com) 14fa39824bb690c5806358871f46940d0450973d8aJames Zern// Vincent Rabaud (vrabaud@google.com) 15fa39824bb690c5806358871f46940d0450973d8aJames Zern 16fa39824bb690c5806358871f46940d0450973d8aJames Zern#ifndef WEBP_DSP_LOSSLESS_COMMON_H_ 17fa39824bb690c5806358871f46940d0450973d8aJames Zern#define WEBP_DSP_LOSSLESS_COMMON_H_ 18fa39824bb690c5806358871f46940d0450973d8aJames Zern 19a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern#include "src/webp/types.h" 20fa39824bb690c5806358871f46940d0450973d8aJames Zern 21a187300ff9a8a7c10b1fb2ec84223fdd14e6d47bJames Zern#include "src/utils/utils.h" 22fa39824bb690c5806358871f46940d0450973d8aJames Zern 23fa39824bb690c5806358871f46940d0450973d8aJames Zern#ifdef __cplusplus 24fa39824bb690c5806358871f46940d0450973d8aJames Zernextern "C" { 25fa39824bb690c5806358871f46940d0450973d8aJames Zern#endif 26fa39824bb690c5806358871f46940d0450973d8aJames Zern 27fa39824bb690c5806358871f46940d0450973d8aJames Zern//------------------------------------------------------------------------------ 28fa39824bb690c5806358871f46940d0450973d8aJames Zern// Decoding 29fa39824bb690c5806358871f46940d0450973d8aJames Zern 30fa39824bb690c5806358871f46940d0450973d8aJames Zern// color mapping related functions. 31fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE uint32_t VP8GetARGBIndex(uint32_t idx) { 32fa39824bb690c5806358871f46940d0450973d8aJames Zern return (idx >> 8) & 0xff; 33fa39824bb690c5806358871f46940d0450973d8aJames Zern} 34fa39824bb690c5806358871f46940d0450973d8aJames Zern 35fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE uint8_t VP8GetAlphaIndex(uint8_t idx) { 36fa39824bb690c5806358871f46940d0450973d8aJames Zern return idx; 37fa39824bb690c5806358871f46940d0450973d8aJames Zern} 38fa39824bb690c5806358871f46940d0450973d8aJames Zern 39fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE uint32_t VP8GetARGBValue(uint32_t val) { 40fa39824bb690c5806358871f46940d0450973d8aJames Zern return val; 41fa39824bb690c5806358871f46940d0450973d8aJames Zern} 42fa39824bb690c5806358871f46940d0450973d8aJames Zern 43fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE uint8_t VP8GetAlphaValue(uint32_t val) { 44fa39824bb690c5806358871f46940d0450973d8aJames Zern return (val >> 8) & 0xff; 45fa39824bb690c5806358871f46940d0450973d8aJames Zern} 46fa39824bb690c5806358871f46940d0450973d8aJames Zern 47fa39824bb690c5806358871f46940d0450973d8aJames Zern//------------------------------------------------------------------------------ 48fa39824bb690c5806358871f46940d0450973d8aJames Zern// Misc methods. 49fa39824bb690c5806358871f46940d0450973d8aJames Zern 50fa39824bb690c5806358871f46940d0450973d8aJames Zern// Computes sampled size of 'size' when sampling using 'sampling bits'. 51fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE uint32_t VP8LSubSampleSize(uint32_t size, 52fa39824bb690c5806358871f46940d0450973d8aJames Zern uint32_t sampling_bits) { 53fa39824bb690c5806358871f46940d0450973d8aJames Zern return (size + (1 << sampling_bits) - 1) >> sampling_bits; 54fa39824bb690c5806358871f46940d0450973d8aJames Zern} 55fa39824bb690c5806358871f46940d0450973d8aJames Zern 56fa39824bb690c5806358871f46940d0450973d8aJames Zern// Converts near lossless quality into max number of bits shaved off. 57fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE int VP8LNearLosslessBits(int near_lossless_quality) { 58fa39824bb690c5806358871f46940d0450973d8aJames Zern // 100 -> 0 59fa39824bb690c5806358871f46940d0450973d8aJames Zern // 80..99 -> 1 60fa39824bb690c5806358871f46940d0450973d8aJames Zern // 60..79 -> 2 61fa39824bb690c5806358871f46940d0450973d8aJames Zern // 40..59 -> 3 62fa39824bb690c5806358871f46940d0450973d8aJames Zern // 20..39 -> 4 63fa39824bb690c5806358871f46940d0450973d8aJames Zern // 0..19 -> 5 64fa39824bb690c5806358871f46940d0450973d8aJames Zern return 5 - near_lossless_quality / 20; 65fa39824bb690c5806358871f46940d0450973d8aJames Zern} 66fa39824bb690c5806358871f46940d0450973d8aJames Zern 67fa39824bb690c5806358871f46940d0450973d8aJames Zern// ----------------------------------------------------------------------------- 68fa39824bb690c5806358871f46940d0450973d8aJames Zern// Faster logarithm for integers. Small values use a look-up table. 69fa39824bb690c5806358871f46940d0450973d8aJames Zern 70fa39824bb690c5806358871f46940d0450973d8aJames Zern// The threshold till approximate version of log_2 can be used. 71fa39824bb690c5806358871f46940d0450973d8aJames Zern// Practically, we can get rid of the call to log() as the two values match to 72fa39824bb690c5806358871f46940d0450973d8aJames Zern// very high degree (the ratio of these two is 0.99999x). 73fa39824bb690c5806358871f46940d0450973d8aJames Zern// Keeping a high threshold for now. 74fa39824bb690c5806358871f46940d0450973d8aJames Zern#define APPROX_LOG_WITH_CORRECTION_MAX 65536 75fa39824bb690c5806358871f46940d0450973d8aJames Zern#define APPROX_LOG_MAX 4096 76fa39824bb690c5806358871f46940d0450973d8aJames Zern#define LOG_2_RECIPROCAL 1.44269504088896338700465094007086 77fa39824bb690c5806358871f46940d0450973d8aJames Zern#define LOG_LOOKUP_IDX_MAX 256 78fa39824bb690c5806358871f46940d0450973d8aJames Zernextern const float kLog2Table[LOG_LOOKUP_IDX_MAX]; 79fa39824bb690c5806358871f46940d0450973d8aJames Zernextern const float kSLog2Table[LOG_LOOKUP_IDX_MAX]; 80fa39824bb690c5806358871f46940d0450973d8aJames Zerntypedef float (*VP8LFastLog2SlowFunc)(uint32_t v); 81fa39824bb690c5806358871f46940d0450973d8aJames Zern 82fa39824bb690c5806358871f46940d0450973d8aJames Zernextern VP8LFastLog2SlowFunc VP8LFastLog2Slow; 83fa39824bb690c5806358871f46940d0450973d8aJames Zernextern VP8LFastLog2SlowFunc VP8LFastSLog2Slow; 84fa39824bb690c5806358871f46940d0450973d8aJames Zern 85fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE float VP8LFastLog2(uint32_t v) { 86fa39824bb690c5806358871f46940d0450973d8aJames Zern return (v < LOG_LOOKUP_IDX_MAX) ? kLog2Table[v] : VP8LFastLog2Slow(v); 87fa39824bb690c5806358871f46940d0450973d8aJames Zern} 88fa39824bb690c5806358871f46940d0450973d8aJames Zern// Fast calculation of v * log2(v) for integer input. 89fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE float VP8LFastSLog2(uint32_t v) { 90fa39824bb690c5806358871f46940d0450973d8aJames Zern return (v < LOG_LOOKUP_IDX_MAX) ? kSLog2Table[v] : VP8LFastSLog2Slow(v); 91fa39824bb690c5806358871f46940d0450973d8aJames Zern} 92fa39824bb690c5806358871f46940d0450973d8aJames Zern 93fa39824bb690c5806358871f46940d0450973d8aJames Zern// ----------------------------------------------------------------------------- 94fa39824bb690c5806358871f46940d0450973d8aJames Zern// PrefixEncode() 95fa39824bb690c5806358871f46940d0450973d8aJames Zern 96fa39824bb690c5806358871f46940d0450973d8aJames Zern// Splitting of distance and length codes into prefixes and 97fa39824bb690c5806358871f46940d0450973d8aJames Zern// extra bits. The prefixes are encoded with an entropy code 98fa39824bb690c5806358871f46940d0450973d8aJames Zern// while the extra bits are stored just as normal bits. 99fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncodeBitsNoLUT(int distance, int* const code, 100fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits) { 101fa39824bb690c5806358871f46940d0450973d8aJames Zern const int highest_bit = BitsLog2Floor(--distance); 102fa39824bb690c5806358871f46940d0450973d8aJames Zern const int second_highest_bit = (distance >> (highest_bit - 1)) & 1; 103fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = highest_bit - 1; 104fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = 2 * highest_bit + second_highest_bit; 105fa39824bb690c5806358871f46940d0450973d8aJames Zern} 106fa39824bb690c5806358871f46940d0450973d8aJames Zern 107fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncodeNoLUT(int distance, int* const code, 108fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits, 109fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits_value) { 110fa39824bb690c5806358871f46940d0450973d8aJames Zern const int highest_bit = BitsLog2Floor(--distance); 111fa39824bb690c5806358871f46940d0450973d8aJames Zern const int second_highest_bit = (distance >> (highest_bit - 1)) & 1; 112fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = highest_bit - 1; 113fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits_value = distance & ((1 << *extra_bits) - 1); 114fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = 2 * highest_bit + second_highest_bit; 115fa39824bb690c5806358871f46940d0450973d8aJames Zern} 116fa39824bb690c5806358871f46940d0450973d8aJames Zern 117fa39824bb690c5806358871f46940d0450973d8aJames Zern#define PREFIX_LOOKUP_IDX_MAX 512 118fa39824bb690c5806358871f46940d0450973d8aJames Zerntypedef struct { 119fa39824bb690c5806358871f46940d0450973d8aJames Zern int8_t code_; 120fa39824bb690c5806358871f46940d0450973d8aJames Zern int8_t extra_bits_; 121fa39824bb690c5806358871f46940d0450973d8aJames Zern} VP8LPrefixCode; 122fa39824bb690c5806358871f46940d0450973d8aJames Zern 123fa39824bb690c5806358871f46940d0450973d8aJames Zern// These tables are derived using VP8LPrefixEncodeNoLUT. 124fa39824bb690c5806358871f46940d0450973d8aJames Zernextern const VP8LPrefixCode kPrefixEncodeCode[PREFIX_LOOKUP_IDX_MAX]; 125fa39824bb690c5806358871f46940d0450973d8aJames Zernextern const uint8_t kPrefixEncodeExtraBitsValue[PREFIX_LOOKUP_IDX_MAX]; 126fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncodeBits(int distance, int* const code, 127fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits) { 128fa39824bb690c5806358871f46940d0450973d8aJames Zern if (distance < PREFIX_LOOKUP_IDX_MAX) { 129fa39824bb690c5806358871f46940d0450973d8aJames Zern const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance]; 130fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = prefix_code.code_; 131fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = prefix_code.extra_bits_; 132fa39824bb690c5806358871f46940d0450973d8aJames Zern } else { 133fa39824bb690c5806358871f46940d0450973d8aJames Zern VP8LPrefixEncodeBitsNoLUT(distance, code, extra_bits); 134fa39824bb690c5806358871f46940d0450973d8aJames Zern } 135fa39824bb690c5806358871f46940d0450973d8aJames Zern} 136fa39824bb690c5806358871f46940d0450973d8aJames Zern 137fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncode(int distance, int* const code, 138fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits, 139fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits_value) { 140fa39824bb690c5806358871f46940d0450973d8aJames Zern if (distance < PREFIX_LOOKUP_IDX_MAX) { 141fa39824bb690c5806358871f46940d0450973d8aJames Zern const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance]; 142fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = prefix_code.code_; 143fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = prefix_code.extra_bits_; 144fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits_value = kPrefixEncodeExtraBitsValue[distance]; 145fa39824bb690c5806358871f46940d0450973d8aJames Zern } else { 146fa39824bb690c5806358871f46940d0450973d8aJames Zern VP8LPrefixEncodeNoLUT(distance, code, extra_bits, extra_bits_value); 147fa39824bb690c5806358871f46940d0450973d8aJames Zern } 148fa39824bb690c5806358871f46940d0450973d8aJames Zern} 149fa39824bb690c5806358871f46940d0450973d8aJames Zern 150fa39824bb690c5806358871f46940d0450973d8aJames Zern// Sum of each component, mod 256. 151fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE 152fa39824bb690c5806358871f46940d0450973d8aJames Zernuint32_t VP8LAddPixels(uint32_t a, uint32_t b) { 153fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t alpha_and_green = (a & 0xff00ff00u) + (b & 0xff00ff00u); 154fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t red_and_blue = (a & 0x00ff00ffu) + (b & 0x00ff00ffu); 155fa39824bb690c5806358871f46940d0450973d8aJames Zern return (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu); 156fa39824bb690c5806358871f46940d0450973d8aJames Zern} 157fa39824bb690c5806358871f46940d0450973d8aJames Zern 158fa39824bb690c5806358871f46940d0450973d8aJames Zern// Difference of each component, mod 256. 159fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE 160fa39824bb690c5806358871f46940d0450973d8aJames Zernuint32_t VP8LSubPixels(uint32_t a, uint32_t b) { 161fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t alpha_and_green = 162fa39824bb690c5806358871f46940d0450973d8aJames Zern 0x00ff00ffu + (a & 0xff00ff00u) - (b & 0xff00ff00u); 163fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t red_and_blue = 164fa39824bb690c5806358871f46940d0450973d8aJames Zern 0xff00ff00u + (a & 0x00ff00ffu) - (b & 0x00ff00ffu); 165fa39824bb690c5806358871f46940d0450973d8aJames Zern return (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu); 166fa39824bb690c5806358871f46940d0450973d8aJames Zern} 167fa39824bb690c5806358871f46940d0450973d8aJames Zern 168fa39824bb690c5806358871f46940d0450973d8aJames Zern//------------------------------------------------------------------------------ 169fa39824bb690c5806358871f46940d0450973d8aJames Zern// Transform-related functions use din both encoding and decoding. 170fa39824bb690c5806358871f46940d0450973d8aJames Zern 171fa39824bb690c5806358871f46940d0450973d8aJames Zern// Macros used to create a batch predictor that iteratively uses a 172fa39824bb690c5806358871f46940d0450973d8aJames Zern// one-pixel predictor. 173fa39824bb690c5806358871f46940d0450973d8aJames Zern 174fa39824bb690c5806358871f46940d0450973d8aJames Zern// The predictor is added to the output pixel (which 175fa39824bb690c5806358871f46940d0450973d8aJames Zern// is therefore considered as a residual) to get the final prediction. 176fa39824bb690c5806358871f46940d0450973d8aJames Zern#define GENERATE_PREDICTOR_ADD(PREDICTOR, PREDICTOR_ADD) \ 177fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic void PREDICTOR_ADD(const uint32_t* in, const uint32_t* upper, \ 178fa39824bb690c5806358871f46940d0450973d8aJames Zern int num_pixels, uint32_t* out) { \ 179fa39824bb690c5806358871f46940d0450973d8aJames Zern int x; \ 180fa39824bb690c5806358871f46940d0450973d8aJames Zern for (x = 0; x < num_pixels; ++x) { \ 181fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t pred = (PREDICTOR)(out[x - 1], upper + x); \ 182fa39824bb690c5806358871f46940d0450973d8aJames Zern out[x] = VP8LAddPixels(in[x], pred); \ 183fa39824bb690c5806358871f46940d0450973d8aJames Zern } \ 184fa39824bb690c5806358871f46940d0450973d8aJames Zern} 185fa39824bb690c5806358871f46940d0450973d8aJames Zern 186fa39824bb690c5806358871f46940d0450973d8aJames Zern// It subtracts the prediction from the input pixel and stores the residual 187fa39824bb690c5806358871f46940d0450973d8aJames Zern// in the output pixel. 188fa39824bb690c5806358871f46940d0450973d8aJames Zern#define GENERATE_PREDICTOR_SUB(PREDICTOR, PREDICTOR_SUB) \ 189fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic void PREDICTOR_SUB(const uint32_t* in, const uint32_t* upper, \ 190fa39824bb690c5806358871f46940d0450973d8aJames Zern int num_pixels, uint32_t* out) { \ 191fa39824bb690c5806358871f46940d0450973d8aJames Zern int x; \ 192fa39824bb690c5806358871f46940d0450973d8aJames Zern for (x = 0; x < num_pixels; ++x) { \ 193fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t pred = (PREDICTOR)(in[x - 1], upper + x); \ 194fa39824bb690c5806358871f46940d0450973d8aJames Zern out[x] = VP8LSubPixels(in[x], pred); \ 195fa39824bb690c5806358871f46940d0450973d8aJames Zern } \ 196fa39824bb690c5806358871f46940d0450973d8aJames Zern} 197fa39824bb690c5806358871f46940d0450973d8aJames Zern 198fa39824bb690c5806358871f46940d0450973d8aJames Zern#ifdef __cplusplus 199fa39824bb690c5806358871f46940d0450973d8aJames Zern} // extern "C" 200fa39824bb690c5806358871f46940d0450973d8aJames Zern#endif 201fa39824bb690c5806358871f46940d0450973d8aJames Zern 202fa39824bb690c5806358871f46940d0450973d8aJames Zern#endif // WEBP_DSP_LOSSLESS_COMMON_H_ 203