lossless_common.h revision fa39824bb690c5806358871f46940d0450973d8a
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 19fa39824bb690c5806358871f46940d0450973d8aJames Zern#include "../webp/types.h" 20fa39824bb690c5806358871f46940d0450973d8aJames Zern 21fa39824bb690c5806358871f46940d0450973d8aJames Zern#include "../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 Zernstatic WEBP_INLINE int VP8LBitsLog2Ceiling(uint32_t n) { 97fa39824bb690c5806358871f46940d0450973d8aJames Zern const int log_floor = BitsLog2Floor(n); 98fa39824bb690c5806358871f46940d0450973d8aJames Zern if (n == (n & ~(n - 1))) { // zero or a power of two. 99fa39824bb690c5806358871f46940d0450973d8aJames Zern return log_floor; 100fa39824bb690c5806358871f46940d0450973d8aJames Zern } 101fa39824bb690c5806358871f46940d0450973d8aJames Zern return log_floor + 1; 102fa39824bb690c5806358871f46940d0450973d8aJames Zern} 103fa39824bb690c5806358871f46940d0450973d8aJames Zern 104fa39824bb690c5806358871f46940d0450973d8aJames Zern// Splitting of distance and length codes into prefixes and 105fa39824bb690c5806358871f46940d0450973d8aJames Zern// extra bits. The prefixes are encoded with an entropy code 106fa39824bb690c5806358871f46940d0450973d8aJames Zern// while the extra bits are stored just as normal bits. 107fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncodeBitsNoLUT(int distance, int* const code, 108fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits) { 109fa39824bb690c5806358871f46940d0450973d8aJames Zern const int highest_bit = BitsLog2Floor(--distance); 110fa39824bb690c5806358871f46940d0450973d8aJames Zern const int second_highest_bit = (distance >> (highest_bit - 1)) & 1; 111fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = highest_bit - 1; 112fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = 2 * highest_bit + second_highest_bit; 113fa39824bb690c5806358871f46940d0450973d8aJames Zern} 114fa39824bb690c5806358871f46940d0450973d8aJames Zern 115fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncodeNoLUT(int distance, int* const code, 116fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits, 117fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits_value) { 118fa39824bb690c5806358871f46940d0450973d8aJames Zern const int highest_bit = BitsLog2Floor(--distance); 119fa39824bb690c5806358871f46940d0450973d8aJames Zern const int second_highest_bit = (distance >> (highest_bit - 1)) & 1; 120fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = highest_bit - 1; 121fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits_value = distance & ((1 << *extra_bits) - 1); 122fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = 2 * highest_bit + second_highest_bit; 123fa39824bb690c5806358871f46940d0450973d8aJames Zern} 124fa39824bb690c5806358871f46940d0450973d8aJames Zern 125fa39824bb690c5806358871f46940d0450973d8aJames Zern#define PREFIX_LOOKUP_IDX_MAX 512 126fa39824bb690c5806358871f46940d0450973d8aJames Zerntypedef struct { 127fa39824bb690c5806358871f46940d0450973d8aJames Zern int8_t code_; 128fa39824bb690c5806358871f46940d0450973d8aJames Zern int8_t extra_bits_; 129fa39824bb690c5806358871f46940d0450973d8aJames Zern} VP8LPrefixCode; 130fa39824bb690c5806358871f46940d0450973d8aJames Zern 131fa39824bb690c5806358871f46940d0450973d8aJames Zern// These tables are derived using VP8LPrefixEncodeNoLUT. 132fa39824bb690c5806358871f46940d0450973d8aJames Zernextern const VP8LPrefixCode kPrefixEncodeCode[PREFIX_LOOKUP_IDX_MAX]; 133fa39824bb690c5806358871f46940d0450973d8aJames Zernextern const uint8_t kPrefixEncodeExtraBitsValue[PREFIX_LOOKUP_IDX_MAX]; 134fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncodeBits(int distance, int* const code, 135fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits) { 136fa39824bb690c5806358871f46940d0450973d8aJames Zern if (distance < PREFIX_LOOKUP_IDX_MAX) { 137fa39824bb690c5806358871f46940d0450973d8aJames Zern const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance]; 138fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = prefix_code.code_; 139fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = prefix_code.extra_bits_; 140fa39824bb690c5806358871f46940d0450973d8aJames Zern } else { 141fa39824bb690c5806358871f46940d0450973d8aJames Zern VP8LPrefixEncodeBitsNoLUT(distance, code, extra_bits); 142fa39824bb690c5806358871f46940d0450973d8aJames Zern } 143fa39824bb690c5806358871f46940d0450973d8aJames Zern} 144fa39824bb690c5806358871f46940d0450973d8aJames Zern 145fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_INLINE void VP8LPrefixEncode(int distance, int* const code, 146fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits, 147fa39824bb690c5806358871f46940d0450973d8aJames Zern int* const extra_bits_value) { 148fa39824bb690c5806358871f46940d0450973d8aJames Zern if (distance < PREFIX_LOOKUP_IDX_MAX) { 149fa39824bb690c5806358871f46940d0450973d8aJames Zern const VP8LPrefixCode prefix_code = kPrefixEncodeCode[distance]; 150fa39824bb690c5806358871f46940d0450973d8aJames Zern *code = prefix_code.code_; 151fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits = prefix_code.extra_bits_; 152fa39824bb690c5806358871f46940d0450973d8aJames Zern *extra_bits_value = kPrefixEncodeExtraBitsValue[distance]; 153fa39824bb690c5806358871f46940d0450973d8aJames Zern } else { 154fa39824bb690c5806358871f46940d0450973d8aJames Zern VP8LPrefixEncodeNoLUT(distance, code, extra_bits, extra_bits_value); 155fa39824bb690c5806358871f46940d0450973d8aJames Zern } 156fa39824bb690c5806358871f46940d0450973d8aJames Zern} 157fa39824bb690c5806358871f46940d0450973d8aJames Zern 158fa39824bb690c5806358871f46940d0450973d8aJames Zern// Sum of each component, mod 256. 159fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE 160fa39824bb690c5806358871f46940d0450973d8aJames Zernuint32_t VP8LAddPixels(uint32_t a, uint32_t b) { 161fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t alpha_and_green = (a & 0xff00ff00u) + (b & 0xff00ff00u); 162fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t red_and_blue = (a & 0x00ff00ffu) + (b & 0x00ff00ffu); 163fa39824bb690c5806358871f46940d0450973d8aJames Zern return (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu); 164fa39824bb690c5806358871f46940d0450973d8aJames Zern} 165fa39824bb690c5806358871f46940d0450973d8aJames Zern 166fa39824bb690c5806358871f46940d0450973d8aJames Zern// Difference of each component, mod 256. 167fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE 168fa39824bb690c5806358871f46940d0450973d8aJames Zernuint32_t VP8LSubPixels(uint32_t a, uint32_t b) { 169fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t alpha_and_green = 170fa39824bb690c5806358871f46940d0450973d8aJames Zern 0x00ff00ffu + (a & 0xff00ff00u) - (b & 0xff00ff00u); 171fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t red_and_blue = 172fa39824bb690c5806358871f46940d0450973d8aJames Zern 0xff00ff00u + (a & 0x00ff00ffu) - (b & 0x00ff00ffu); 173fa39824bb690c5806358871f46940d0450973d8aJames Zern return (alpha_and_green & 0xff00ff00u) | (red_and_blue & 0x00ff00ffu); 174fa39824bb690c5806358871f46940d0450973d8aJames Zern} 175fa39824bb690c5806358871f46940d0450973d8aJames Zern 176fa39824bb690c5806358871f46940d0450973d8aJames Zern//------------------------------------------------------------------------------ 177fa39824bb690c5806358871f46940d0450973d8aJames Zern// Transform-related functions use din both encoding and decoding. 178fa39824bb690c5806358871f46940d0450973d8aJames Zern 179fa39824bb690c5806358871f46940d0450973d8aJames Zern// Macros used to create a batch predictor that iteratively uses a 180fa39824bb690c5806358871f46940d0450973d8aJames Zern// one-pixel predictor. 181fa39824bb690c5806358871f46940d0450973d8aJames Zern 182fa39824bb690c5806358871f46940d0450973d8aJames Zern// The predictor is added to the output pixel (which 183fa39824bb690c5806358871f46940d0450973d8aJames Zern// is therefore considered as a residual) to get the final prediction. 184fa39824bb690c5806358871f46940d0450973d8aJames Zern#define GENERATE_PREDICTOR_ADD(PREDICTOR, PREDICTOR_ADD) \ 185fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic void PREDICTOR_ADD(const uint32_t* in, const uint32_t* upper, \ 186fa39824bb690c5806358871f46940d0450973d8aJames Zern int num_pixels, uint32_t* out) { \ 187fa39824bb690c5806358871f46940d0450973d8aJames Zern int x; \ 188fa39824bb690c5806358871f46940d0450973d8aJames Zern for (x = 0; x < num_pixels; ++x) { \ 189fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t pred = (PREDICTOR)(out[x - 1], upper + x); \ 190fa39824bb690c5806358871f46940d0450973d8aJames Zern out[x] = VP8LAddPixels(in[x], pred); \ 191fa39824bb690c5806358871f46940d0450973d8aJames Zern } \ 192fa39824bb690c5806358871f46940d0450973d8aJames Zern} 193fa39824bb690c5806358871f46940d0450973d8aJames Zern 194fa39824bb690c5806358871f46940d0450973d8aJames Zern// It subtracts the prediction from the input pixel and stores the residual 195fa39824bb690c5806358871f46940d0450973d8aJames Zern// in the output pixel. 196fa39824bb690c5806358871f46940d0450973d8aJames Zern#define GENERATE_PREDICTOR_SUB(PREDICTOR, PREDICTOR_SUB) \ 197fa39824bb690c5806358871f46940d0450973d8aJames Zernstatic void PREDICTOR_SUB(const uint32_t* in, const uint32_t* upper, \ 198fa39824bb690c5806358871f46940d0450973d8aJames Zern int num_pixels, uint32_t* out) { \ 199fa39824bb690c5806358871f46940d0450973d8aJames Zern int x; \ 200fa39824bb690c5806358871f46940d0450973d8aJames Zern for (x = 0; x < num_pixels; ++x) { \ 201fa39824bb690c5806358871f46940d0450973d8aJames Zern const uint32_t pred = (PREDICTOR)(in[x - 1], upper + x); \ 202fa39824bb690c5806358871f46940d0450973d8aJames Zern out[x] = VP8LSubPixels(in[x], pred); \ 203fa39824bb690c5806358871f46940d0450973d8aJames Zern } \ 204fa39824bb690c5806358871f46940d0450973d8aJames Zern} 205fa39824bb690c5806358871f46940d0450973d8aJames Zern 206fa39824bb690c5806358871f46940d0450973d8aJames Zern#ifdef __cplusplus 207fa39824bb690c5806358871f46940d0450973d8aJames Zern} // extern "C" 208fa39824bb690c5806358871f46940d0450973d8aJames Zern#endif 209fa39824bb690c5806358871f46940d0450973d8aJames Zern 210fa39824bb690c5806358871f46940d0450973d8aJames Zern#endif // WEBP_DSP_LOSSLESS_COMMON_H_ 211