diff options
Diffstat (limited to 'src/3rdparty/libwebp/src/utils')
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/bit_reader.c | 42 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/bit_reader.h | 19 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/bit_reader_inl.h | 4 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/bit_writer.c | 64 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/bit_writer.h | 37 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/color_cache.c | 10 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/color_cache.h | 16 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/filters.c | 204 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/filters.h | 33 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/huffman.c | 392 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/huffman.h | 110 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/huffman_encode.h | 5 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/rescaler.c | 492 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/rescaler.h | 22 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/thread.c | 49 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/thread.h | 2 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/utils.c | 30 | ||||
| -rw-r--r-- | src/3rdparty/libwebp/src/utils/utils.h | 47 |
18 files changed, 503 insertions, 1075 deletions
diff --git a/src/3rdparty/libwebp/src/utils/bit_reader.c b/src/3rdparty/libwebp/src/utils/bit_reader.c index 64503e6..45198e1 100644 --- a/src/3rdparty/libwebp/src/utils/bit_reader.c +++ b/src/3rdparty/libwebp/src/utils/bit_reader.c @@ -20,17 +20,26 @@ //------------------------------------------------------------------------------ // VP8BitReader +void VP8BitReaderSetBuffer(VP8BitReader* const br, + const uint8_t* const start, + size_t size) { + br->buf_ = start; + br->buf_end_ = start + size; + br->buf_max_ = + (size >= sizeof(lbit_t)) ? start + size - sizeof(lbit_t) + 1 + : start; +} + void VP8InitBitReader(VP8BitReader* const br, - const uint8_t* const start, const uint8_t* const end) { + const uint8_t* const start, size_t size) { assert(br != NULL); assert(start != NULL); - assert(start <= end); + assert(size < (1u << 31)); // limit ensured by format and upstream checks br->range_ = 255 - 1; - br->buf_ = start; - br->buf_end_ = end; br->value_ = 0; br->bits_ = -8; // to load the very first 8bits br->eof_ = 0; + VP8BitReaderSetBuffer(br, start, size); VP8LoadNewBytes(br); } @@ -38,6 +47,7 @@ void VP8RemapBitReader(VP8BitReader* const br, ptrdiff_t offset) { if (br->buf_ != NULL) { br->buf_ += offset; br->buf_end_ += offset; + br->buf_max_ += offset; } } @@ -54,7 +64,7 @@ const uint8_t kVP8Log2Range[128] = { }; // range = ((range - 1) << kVP8Log2Range[range]) + 1 -const range_t kVP8NewRange[128] = { +const uint8_t kVP8NewRange[128] = { 127, 127, 191, 127, 159, 191, 223, 127, 143, 159, 175, 191, 207, 223, 239, 127, 135, 143, 151, 159, 167, 175, 183, 191, @@ -83,6 +93,8 @@ void VP8LoadFinalBytes(VP8BitReader* const br) { br->value_ <<= 8; br->bits_ += 8; br->eof_ = 1; + } else { + br->bits_ = 0; // This is to avoid undefined behaviour with shifts. } } @@ -136,7 +148,6 @@ void VP8LInitBitReader(VP8LBitReader* const br, const uint8_t* const start, br->val_ = 0; br->bit_pos_ = 0; br->eos_ = 0; - br->error_ = 0; if (length > sizeof(br->val_)) { length = sizeof(br->val_); @@ -157,8 +168,12 @@ void VP8LBitReaderSetBuffer(VP8LBitReader* const br, br->buf_ = buf; br->len_ = len; // pos_ > len_ should be considered a param error. - br->error_ = (br->pos_ > br->len_); - br->eos_ = br->error_ || VP8LIsEndOfStream(br); + br->eos_ = (br->pos_ > br->len_) || VP8LIsEndOfStream(br); +} + +static void VP8LSetEndOfStream(VP8LBitReader* const br) { + br->eos_ = 1; + br->bit_pos_ = 0; // To avoid undefined behaviour with shifts. } // If not at EOS, reload up to VP8L_LBITS byte-by-byte @@ -169,7 +184,9 @@ static void ShiftBytes(VP8LBitReader* const br) { ++br->pos_; br->bit_pos_ -= 8; } - br->eos_ = VP8LIsEndOfStream(br); + if (VP8LIsEndOfStream(br)) { + VP8LSetEndOfStream(br); + } } void VP8LDoFillBitWindow(VP8LBitReader* const br) { @@ -182,7 +199,7 @@ void VP8LDoFillBitWindow(VP8LBitReader* const br) { br->bit_pos_ -= VP8L_WBITS; // The expression below needs a little-endian arch to work correctly. // This gives a large speedup for decoding speed. - br->val_ |= (vp8l_val_t)*(const uint32_t*)(br->buf_ + br->pos_) << + br->val_ |= (vp8l_val_t)WebPMemToUint32(br->buf_ + br->pos_) << (VP8L_LBITS - VP8L_WBITS); br->pos_ += VP8L_LOG8_WBITS; return; @@ -195,14 +212,13 @@ uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) { assert(n_bits >= 0); // Flag an error if end_of_stream or n_bits is more than allowed limit. if (!br->eos_ && n_bits <= VP8L_MAX_NUM_BIT_READ) { - const uint32_t val = - (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits]; + const uint32_t val = VP8LPrefetchBits(br) & kBitMask[n_bits]; const int new_bits = br->bit_pos_ + n_bits; br->bit_pos_ = new_bits; ShiftBytes(br); return val; } else { - br->error_ = 1; + VP8LSetEndOfStream(br); return 0; } } diff --git a/src/3rdparty/libwebp/src/utils/bit_reader.h b/src/3rdparty/libwebp/src/utils/bit_reader.h index f569734..ec3426c 100644 --- a/src/3rdparty/libwebp/src/utils/bit_reader.h +++ b/src/3rdparty/libwebp/src/utils/bit_reader.h @@ -43,10 +43,12 @@ extern "C" { #define BITS 56 #elif defined(__arm__) || defined(_M_ARM) // ARM #define BITS 24 +#elif defined(__aarch64__) // ARM 64bit +#define BITS 56 #elif defined(__mips__) // MIPS #define BITS 24 #else // reasonable default -#define BITS 24 // TODO(skal): test aarch64 and find the proper BITS value. +#define BITS 24 #endif //------------------------------------------------------------------------------ @@ -74,12 +76,16 @@ struct VP8BitReader { // read buffer const uint8_t* buf_; // next byte to be read const uint8_t* buf_end_; // end of read buffer + const uint8_t* buf_max_; // max packed-read position on buffer int eof_; // true if input is exhausted }; // Initialize the bit reader and the boolean decoder. void VP8InitBitReader(VP8BitReader* const br, - const uint8_t* const start, const uint8_t* const end); + const uint8_t* const start, size_t size); +// Sets the working read buffer. +void VP8BitReaderSetBuffer(VP8BitReader* const br, + const uint8_t* const start, size_t size); // Update internal pointers to displace the byte buffer by the // relative offset 'offset'. @@ -107,7 +113,7 @@ int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits); // maximum number of bits (inclusive) the bit-reader can handle: #define VP8L_MAX_NUM_BIT_READ 24 -#define VP8L_LBITS 64 // Number of bits prefetched. +#define VP8L_LBITS 64 // Number of bits prefetched (= bit-size of vp8l_val_t). #define VP8L_WBITS 32 // Minimum number of bytes ready after VP8LFillBitWindow. typedef uint64_t vp8l_val_t; // right now, this bit-reader can only use 64bit. @@ -118,8 +124,7 @@ typedef struct { size_t len_; // buffer length size_t pos_; // byte position in buf_ int bit_pos_; // current bit-reading position in val_ - int eos_; // bitstream is finished - int error_; // an error occurred (buffer overflow attempt...) + int eos_; // true if a bit was read past the end of buffer } VP8LBitReader; void VP8LInitBitReader(VP8LBitReader* const br, @@ -138,14 +143,14 @@ uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits); // Return the prefetched bits, so they can be looked up. static WEBP_INLINE uint32_t VP8LPrefetchBits(VP8LBitReader* const br) { - return (uint32_t)(br->val_ >> br->bit_pos_); + return (uint32_t)(br->val_ >> (br->bit_pos_ & (VP8L_LBITS - 1))); } // Returns true if there was an attempt at reading bit past the end of // the buffer. Doesn't set br->eos_ flag. static WEBP_INLINE int VP8LIsEndOfStream(const VP8LBitReader* const br) { assert(br->pos_ <= br->len_); - return (br->pos_ == br->len_) && (br->bit_pos_ > VP8L_LBITS); + return br->eos_ || ((br->pos_ == br->len_) && (br->bit_pos_ > VP8L_LBITS)); } // For jumping over a number of bits in the bit stream when accessed with diff --git a/src/3rdparty/libwebp/src/utils/bit_reader_inl.h b/src/3rdparty/libwebp/src/utils/bit_reader_inl.h index 81427c6..3721570 100644 --- a/src/3rdparty/libwebp/src/utils/bit_reader_inl.h +++ b/src/3rdparty/libwebp/src/utils/bit_reader_inl.h @@ -46,7 +46,7 @@ typedef uint8_t lbit_t; #endif extern const uint8_t kVP8Log2Range[128]; -extern const range_t kVP8NewRange[128]; +extern const uint8_t kVP8NewRange[128]; // special case for the tail byte-reading void VP8LoadFinalBytes(VP8BitReader* const br); @@ -58,7 +58,7 @@ void VP8LoadFinalBytes(VP8BitReader* const br); static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) { assert(br != NULL && br->buf_ != NULL); // Read 'BITS' bits at a time if possible. - if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) { + if (br->buf_ < br->buf_max_) { // convert memory type to register type (with some zero'ing!) bit_t bits; #if defined(WEBP_FORCE_ALIGNED) diff --git a/src/3rdparty/libwebp/src/utils/bit_writer.c b/src/3rdparty/libwebp/src/utils/bit_writer.c index 9875ca6..0644286 100644 --- a/src/3rdparty/libwebp/src/utils/bit_writer.c +++ b/src/3rdparty/libwebp/src/utils/bit_writer.c @@ -140,19 +140,20 @@ int VP8PutBitUniform(VP8BitWriter* const bw, int bit) { return bit; } -void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) { - int mask; - for (mask = 1 << (nb_bits - 1); mask; mask >>= 1) +void VP8PutBits(VP8BitWriter* const bw, uint32_t value, int nb_bits) { + uint32_t mask; + assert(nb_bits > 0 && nb_bits < 32); + for (mask = 1u << (nb_bits - 1); mask; mask >>= 1) VP8PutBitUniform(bw, value & mask); } -void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) { +void VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) { if (!VP8PutBitUniform(bw, value != 0)) return; if (value < 0) { - VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1); + VP8PutBits(bw, ((-value) << 1) | 1, nb_bits + 1); } else { - VP8PutValue(bw, value << 1, nb_bits + 1); + VP8PutBits(bw, value << 1, nb_bits + 1); } } @@ -171,7 +172,7 @@ int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) { } uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) { - VP8PutValue(bw, 0, 9 - bw->nb_bits_); + VP8PutBits(bw, 0, 9 - bw->nb_bits_); bw->nb_bits_ = 0; // pad with zeroes Flush(bw); return bw->buf_; @@ -201,10 +202,6 @@ void VP8BitWriterWipeOut(VP8BitWriter* const bw) { // when extra space is needed. #define MIN_EXTRA_SIZE (32768ULL) -#define VP8L_WRITER_BYTES ((int)sizeof(vp8l_wtype_t)) -#define VP8L_WRITER_BITS (VP8L_WRITER_BYTES * 8) -#define VP8L_WRITER_MAX_BITS (8 * (int)sizeof(vp8l_atype_t)) - // Returns 1 on success. static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) { uint8_t* allocated_buf; @@ -242,33 +239,49 @@ int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) { return VP8LBitWriterResize(bw, expected_size); } -void VP8LBitWriterDestroy(VP8LBitWriter* const bw) { +void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) { if (bw != NULL) { WebPSafeFree(bw->buf_); memset(bw, 0, sizeof(*bw)); } } -void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) { +void VP8LPutBitsFlushBits(VP8LBitWriter* const bw) { + // If needed, make some room by flushing some bits out. + if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) { + const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE; + if (extra_size != (size_t)extra_size || + !VP8LBitWriterResize(bw, (size_t)extra_size)) { + bw->cur_ = bw->buf_; + bw->error_ = 1; + return; + } + } + *(vp8l_wtype_t*)bw->cur_ = (vp8l_wtype_t)WSWAP((vp8l_wtype_t)bw->bits_); + bw->cur_ += VP8L_WRITER_BYTES; + bw->bits_ >>= VP8L_WRITER_BITS; + bw->used_ -= VP8L_WRITER_BITS; +} + +void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits) { assert(n_bits <= 32); // That's the max we can handle: - assert(bw->used_ + n_bits <= 2 * VP8L_WRITER_MAX_BITS); + assert(sizeof(vp8l_wtype_t) == 2); if (n_bits > 0) { - // Local field copy. vp8l_atype_t lbits = bw->bits_; int used = bw->used_; // Special case of overflow handling for 32bit accumulator (2-steps flush). - if (VP8L_WRITER_BITS == 16) { - if (used + n_bits >= VP8L_WRITER_MAX_BITS) { - // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below. - const int shift = VP8L_WRITER_MAX_BITS - used; - lbits |= (vp8l_atype_t)bits << used; - used = VP8L_WRITER_MAX_BITS; - n_bits -= shift; - bits >>= shift; - assert(n_bits <= VP8L_WRITER_MAX_BITS); - } +#if VP8L_WRITER_BITS == 16 + if (used + n_bits >= VP8L_WRITER_MAX_BITS) { + // Fill up all the VP8L_WRITER_MAX_BITS so it can be flushed out below. + const int shift = VP8L_WRITER_MAX_BITS - used; + lbits |= (vp8l_atype_t)bits << used; + used = VP8L_WRITER_MAX_BITS; + n_bits -= shift; + bits >>= shift; + assert(n_bits <= VP8L_WRITER_MAX_BITS); } +#endif // If needed, make some room by flushing some bits out. while (used >= VP8L_WRITER_BITS) { if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) { @@ -285,7 +298,6 @@ void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) { lbits >>= VP8L_WRITER_BITS; used -= VP8L_WRITER_BITS; } - // Eventually, insert new bits. bw->bits_ = lbits | ((vp8l_atype_t)bits << used); bw->used_ = used + n_bits; } diff --git a/src/3rdparty/libwebp/src/utils/bit_writer.h b/src/3rdparty/libwebp/src/utils/bit_writer.h index c80d22a..ef360d1 100644 --- a/src/3rdparty/libwebp/src/utils/bit_writer.h +++ b/src/3rdparty/libwebp/src/utils/bit_writer.h @@ -45,8 +45,8 @@ void VP8BitWriterWipeOut(VP8BitWriter* const bw); int VP8PutBit(VP8BitWriter* const bw, int bit, int prob); int VP8PutBitUniform(VP8BitWriter* const bw, int bit); -void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits); -void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits); +void VP8PutBits(VP8BitWriter* const bw, uint32_t value, int nb_bits); +void VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits); // Appends some bytes to the internal buffer. Data is copied. int VP8BitWriterAppend(VP8BitWriter* const bw, @@ -73,10 +73,16 @@ static WEBP_INLINE size_t VP8BitWriterSize(const VP8BitWriter* const bw) { typedef uint64_t vp8l_atype_t; // accumulator type typedef uint32_t vp8l_wtype_t; // writing type #define WSWAP HToLE32 +#define VP8L_WRITER_BYTES 4 // sizeof(vp8l_wtype_t) +#define VP8L_WRITER_BITS 32 // 8 * sizeof(vp8l_wtype_t) +#define VP8L_WRITER_MAX_BITS 64 // 8 * sizeof(vp8l_atype_t) #else typedef uint32_t vp8l_atype_t; typedef uint16_t vp8l_wtype_t; #define WSWAP HToLE16 +#define VP8L_WRITER_BYTES 2 +#define VP8L_WRITER_BITS 16 +#define VP8L_WRITER_MAX_BITS 32 #endif typedef struct { @@ -97,19 +103,38 @@ static WEBP_INLINE size_t VP8LBitWriterNumBytes(VP8LBitWriter* const bw) { return (bw->cur_ - bw->buf_) + ((bw->used_ + 7) >> 3); } +// Returns false in case of memory allocation error. +int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size); +// Finalize the bitstream coding. Returns a pointer to the internal buffer. uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw); +// Release any pending memory and zeroes the object. +void VP8LBitWriterWipeOut(VP8LBitWriter* const bw); -// Returns 0 in case of memory allocation error. -int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size); +// Internal function for VP8LPutBits flushing 32 bits from the written state. +void VP8LPutBitsFlushBits(VP8LBitWriter* const bw); -void VP8LBitWriterDestroy(VP8LBitWriter* const bw); +// PutBits internal function used in the 16 bit vp8l_wtype_t case. +void VP8LPutBitsInternal(VP8LBitWriter* const bw, uint32_t bits, int n_bits); // This function writes bits into bytes in increasing addresses (little endian), // and within a byte least-significant-bit first. // This function can write up to 32 bits in one go, but VP8LBitReader can only // read 24 bits max (VP8L_MAX_NUM_BIT_READ). // VP8LBitWriter's error_ flag is set in case of memory allocation error. -void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits); +static WEBP_INLINE void VP8LPutBits(VP8LBitWriter* const bw, + uint32_t bits, int n_bits) { + if (sizeof(vp8l_wtype_t) == 4) { + if (n_bits > 0) { + if (bw->used_ >= 32) { + VP8LPutBitsFlushBits(bw); + } + bw->bits_ |= (vp8l_atype_t)bits << bw->used_; + bw->used_ += n_bits; + } + } else { + VP8LPutBitsInternal(bw, bits, n_bits); + } +} //------------------------------------------------------------------------------ diff --git a/src/3rdparty/libwebp/src/utils/color_cache.c b/src/3rdparty/libwebp/src/utils/color_cache.c index 8a88f08..f9ff4b5 100644 --- a/src/3rdparty/libwebp/src/utils/color_cache.c +++ b/src/3rdparty/libwebp/src/utils/color_cache.c @@ -13,6 +13,7 @@ #include <assert.h> #include <stdlib.h> +#include <string.h> #include "./color_cache.h" #include "../utils/utils.h" @@ -27,6 +28,7 @@ int VP8LColorCacheInit(VP8LColorCache* const cc, int hash_bits) { sizeof(*cc->colors_)); if (cc->colors_ == NULL) return 0; cc->hash_shift_ = 32 - hash_bits; + cc->hash_bits_ = hash_bits; return 1; } @@ -37,3 +39,11 @@ void VP8LColorCacheClear(VP8LColorCache* const cc) { } } +void VP8LColorCacheCopy(const VP8LColorCache* const src, + VP8LColorCache* const dst) { + assert(src != NULL); + assert(dst != NULL); + assert(src->hash_bits_ == dst->hash_bits_); + memcpy(dst->colors_, src->colors_, + ((size_t)1u << dst->hash_bits_) * sizeof(*dst->colors_)); +} diff --git a/src/3rdparty/libwebp/src/utils/color_cache.h b/src/3rdparty/libwebp/src/utils/color_cache.h index 0f824ed..a9a9f64 100644 --- a/src/3rdparty/libwebp/src/utils/color_cache.h +++ b/src/3rdparty/libwebp/src/utils/color_cache.h @@ -24,17 +24,24 @@ extern "C" { // Main color cache struct. typedef struct { uint32_t *colors_; // color entries - int hash_shift_; // Hash shift: 32 - hash_bits. + int hash_shift_; // Hash shift: 32 - hash_bits_. + int hash_bits_; } VP8LColorCache; static const uint32_t kHashMul = 0x1e35a7bd; static WEBP_INLINE uint32_t VP8LColorCacheLookup( const VP8LColorCache* const cc, uint32_t key) { - assert(key <= (~0U >> cc->hash_shift_)); + assert((key >> cc->hash_bits_) == 0u); return cc->colors_[key]; } +static WEBP_INLINE void VP8LColorCacheSet(const VP8LColorCache* const cc, + uint32_t key, uint32_t argb) { + assert((key >> cc->hash_bits_) == 0u); + cc->colors_[key] = argb; +} + static WEBP_INLINE void VP8LColorCacheInsert(const VP8LColorCache* const cc, uint32_t argb) { const uint32_t key = (kHashMul * argb) >> cc->hash_shift_; @@ -49,7 +56,7 @@ static WEBP_INLINE int VP8LColorCacheGetIndex(const VP8LColorCache* const cc, static WEBP_INLINE int VP8LColorCacheContains(const VP8LColorCache* const cc, uint32_t argb) { const uint32_t key = (kHashMul * argb) >> cc->hash_shift_; - return cc->colors_[key] == argb; + return (cc->colors_[key] == argb); } //------------------------------------------------------------------------------ @@ -58,6 +65,9 @@ static WEBP_INLINE int VP8LColorCacheContains(const VP8LColorCache* const cc, // Returns false in case of memory error. int VP8LColorCacheInit(VP8LColorCache* const color_cache, int hash_bits); +void VP8LColorCacheCopy(const VP8LColorCache* const src, + VP8LColorCache* const dst); + // Delete the memory associated to color cache. void VP8LColorCacheClear(VP8LColorCache* const color_cache); diff --git a/src/3rdparty/libwebp/src/utils/filters.c b/src/3rdparty/libwebp/src/utils/filters.c index 2d15bd0..15543b1 100644 --- a/src/3rdparty/libwebp/src/utils/filters.c +++ b/src/3rdparty/libwebp/src/utils/filters.c @@ -7,200 +7,27 @@ // be found in the AUTHORS file in the root of the source tree. // ----------------------------------------------------------------------------- // -// Spatial prediction using various filters +// filter estimation // // Author: Urvang (urvang@google.com) #include "./filters.h" -#include <assert.h> #include <stdlib.h> #include <string.h> -//------------------------------------------------------------------------------ -// Helpful macro. - -# define SANITY_CHECK(in, out) \ - assert(in != NULL); \ - assert(out != NULL); \ - assert(width > 0); \ - assert(height > 0); \ - assert(stride >= width); \ - assert(row >= 0 && num_rows > 0 && row + num_rows <= height); \ - (void)height; // Silence unused warning. - -static WEBP_INLINE void PredictLine(const uint8_t* src, const uint8_t* pred, - uint8_t* dst, int length, int inverse) { - int i; - if (inverse) { - for (i = 0; i < length; ++i) dst[i] = src[i] + pred[i]; - } else { - for (i = 0; i < length; ++i) dst[i] = src[i] - pred[i]; - } -} - -//------------------------------------------------------------------------------ -// Horizontal filter. - -static WEBP_INLINE void DoHorizontalFilter(const uint8_t* in, - int width, int height, int stride, - int row, int num_rows, - int inverse, uint8_t* out) { - const uint8_t* preds; - const size_t start_offset = row * stride; - const int last_row = row + num_rows; - SANITY_CHECK(in, out); - in += start_offset; - out += start_offset; - preds = inverse ? out : in; - - if (row == 0) { - // Leftmost pixel is the same as input for topmost scanline. - out[0] = in[0]; - PredictLine(in + 1, preds, out + 1, width - 1, inverse); - row = 1; - preds += stride; - in += stride; - out += stride; - } - - // Filter line-by-line. - while (row < last_row) { - // Leftmost pixel is predicted from above. - PredictLine(in, preds - stride, out, 1, inverse); - PredictLine(in + 1, preds, out + 1, width - 1, inverse); - ++row; - preds += stride; - in += stride; - out += stride; - } -} - -static void HorizontalFilter(const uint8_t* data, int width, int height, - int stride, uint8_t* filtered_data) { - DoHorizontalFilter(data, width, height, stride, 0, height, 0, filtered_data); -} - -static void HorizontalUnfilter(int width, int height, int stride, int row, - int num_rows, uint8_t* data) { - DoHorizontalFilter(data, width, height, stride, row, num_rows, 1, data); -} - -//------------------------------------------------------------------------------ -// Vertical filter. - -static WEBP_INLINE void DoVerticalFilter(const uint8_t* in, - int width, int height, int stride, - int row, int num_rows, - int inverse, uint8_t* out) { - const uint8_t* preds; - const size_t start_offset = row * stride; - const int last_row = row + num_rows; - SANITY_CHECK(in, out); - in += start_offset; - out += start_offset; - preds = inverse ? out : in; - - if (row == 0) { - // Very first top-left pixel is copied. - out[0] = in[0]; - // Rest of top scan-line is left-predicted. - PredictLine(in + 1, preds, out + 1, width - 1, inverse); - row = 1; - in += stride; - out += stride; - } else { - // We are starting from in-between. Make sure 'preds' points to prev row. - preds -= stride; - } - - // Filter line-by-line. - while (row < last_row) { - PredictLine(in, preds, out, width, inverse); - ++row; - preds += stride; - in += stride; - out += stride; - } -} - -static void VerticalFilter(const uint8_t* data, int width, int height, - int stride, uint8_t* filtered_data) { - DoVerticalFilter(data, width, height, stride, 0, height, 0, filtered_data); -} - -static void VerticalUnfilter(int width, int height, int stride, int row, - int num_rows, uint8_t* data) { - DoVerticalFilter(data, width, height, stride, row, num_rows, 1, data); -} +// ----------------------------------------------------------------------------- +// Quick estimate of a potentially interesting filter mode to try. -//------------------------------------------------------------------------------ -// Gradient filter. +#define SMAX 16 +#define SDIFF(a, b) (abs((a) - (b)) >> 4) // Scoring diff, in [0..SMAX) static WEBP_INLINE int GradientPredictor(uint8_t a, uint8_t b, uint8_t c) { const int g = a + b - c; return ((g & ~0xff) == 0) ? g : (g < 0) ? 0 : 255; // clip to 8bit } -static WEBP_INLINE void DoGradientFilter(const uint8_t* in, - int width, int height, int stride, - int row, int num_rows, - int inverse, uint8_t* out) { - const uint8_t* preds; - const size_t start_offset = row * stride; - const int last_row = row + num_rows; - SANITY_CHECK(in, out); - in += start_offset; - out += start_offset; - preds = inverse ? out : in; - - // left prediction for top scan-line - if (row == 0) { - out[0] = in[0]; - PredictLine(in + 1, preds, out + 1, width - 1, inverse); - row = 1; - preds += stride; - in += stride; - out += stride; - } - - // Filter line-by-line. - while (row < last_row) { - int w; - // leftmost pixel: predict from above. - PredictLine(in, preds - stride, out, 1, inverse); - for (w = 1; w < width; ++w) { - const int pred = GradientPredictor(preds[w - 1], - preds[w - stride], - preds[w - stride - 1]); - out[w] = in[w] + (inverse ? pred : -pred); - } - ++row; - preds += stride; - in += stride; - out += stride; - } -} - -static void GradientFilter(const uint8_t* data, int width, int height, - int stride, uint8_t* filtered_data) { - DoGradientFilter(data, width, height, stride, 0, height, 0, filtered_data); -} - -static void GradientUnfilter(int width, int height, int stride, int row, - int num_rows, uint8_t* data) { - DoGradientFilter(data, width, height, stride, row, num_rows, 1, data); -} - -#undef SANITY_CHECK - -// ----------------------------------------------------------------------------- -// Quick estimate of a potentially interesting filter mode to try. - -#define SMAX 16 -#define SDIFF(a, b) (abs((a) - (b)) >> 4) // Scoring diff, in [0..SMAX) - -WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, - int width, int height, int stride) { +WEBP_FILTER_TYPE WebPEstimateBestFilter(const uint8_t* data, + int width, int height, int stride) { int i, j; int bins[WEBP_FILTER_LAST][SMAX]; memset(bins, 0, sizeof(bins)); @@ -247,20 +74,3 @@ WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, #undef SDIFF //------------------------------------------------------------------------------ - -const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST] = { - NULL, // WEBP_FILTER_NONE - HorizontalFilter, // WEBP_FILTER_HORIZONTAL - VerticalFilter, // WEBP_FILTER_VERTICAL - GradientFilter // WEBP_FILTER_GRADIENT -}; - -const WebPUnfilterFunc WebPUnfilters[WEBP_FILTER_LAST] = { - NULL, // WEBP_FILTER_NONE - HorizontalUnfilter, // WEBP_FILTER_HORIZONTAL - VerticalUnfilter, // WEBP_FILTER_VERTICAL - GradientUnfilter // WEBP_FILTER_GRADIENT -}; - -//------------------------------------------------------------------------------ - diff --git a/src/3rdparty/libwebp/src/utils/filters.h b/src/3rdparty/libwebp/src/utils/filters.h index dde39cb..088b132 100644 --- a/src/3rdparty/libwebp/src/utils/filters.h +++ b/src/3rdparty/libwebp/src/utils/filters.h @@ -15,42 +15,15 @@ #define WEBP_UTILS_FILTERS_H_ #include "../webp/types.h" +#include "../dsp/dsp.h" #ifdef __cplusplus extern "C" { #endif -// Filters. -typedef enum { - WEBP_FILTER_NONE = 0, - WEBP_FILTER_HORIZONTAL, - WEBP_FILTER_VERTICAL, - WEBP_FILTER_GRADIENT, - WEBP_FILTER_LAST = WEBP_FILTER_GRADIENT + 1, // end marker - WEBP_FILTER_BEST, - WEBP_FILTER_FAST -} WEBP_FILTER_TYPE; - -typedef void (*WebPFilterFunc)(const uint8_t* in, int width, int height, - int stride, uint8_t* out); -typedef void (*WebPUnfilterFunc)(int width, int height, int stride, - int row, int num_rows, uint8_t* data); - -// Filter the given data using the given predictor. -// 'in' corresponds to a 2-dimensional pixel array of size (stride * height) -// in raster order. -// 'stride' is number of bytes per scan line (with possible padding). -// 'out' should be pre-allocated. -extern const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST]; - -// In-place reconstruct the original data from the given filtered data. -// The reconstruction will be done for 'num_rows' rows starting from 'row' -// (assuming rows upto 'row - 1' are already reconstructed). -extern const WebPUnfilterFunc WebPUnfilters[WEBP_FILTER_LAST]; - // Fast estimate of a potentially good filter. -WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, - int width, int height, int stride); +WEBP_FILTER_TYPE WebPEstimateBestFilter(const uint8_t* data, + int width, int height, int stride); #ifdef __cplusplus } // extern "C" diff --git a/src/3rdparty/libwebp/src/utils/huffman.c b/src/3rdparty/libwebp/src/utils/huffman.c index c4c16d9..d57376a 100644 --- a/src/3rdparty/libwebp/src/utils/huffman.c +++ b/src/3rdparty/libwebp/src/utils/huffman.c @@ -18,302 +18,188 @@ #include "../utils/utils.h" #include "../webp/format_constants.h" -// Uncomment the following to use look-up table for ReverseBits() -// (might be faster on some platform) -// #define USE_LUT_REVERSE_BITS - // Huffman data read via DecodeImageStream is represented in two (red and green) // bytes. #define MAX_HTREE_GROUPS 0x10000 -#define NON_EXISTENT_SYMBOL (-1) - -static void TreeNodeInit(HuffmanTreeNode* const node) { - node->children_ = -1; // means: 'unassigned so far' -} - -static int NodeIsEmpty(const HuffmanTreeNode* const node) { - return (node->children_ < 0); -} - -static int IsFull(const HuffmanTree* const tree) { - return (tree->num_nodes_ == tree->max_nodes_); -} - -static void AssignChildren(HuffmanTree* const tree, - HuffmanTreeNode* const node) { - HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_; - node->children_ = (int)(children - node); - assert(children - node == (int)(children - node)); - tree->num_nodes_ += 2; - TreeNodeInit(children + 0); - TreeNodeInit(children + 1); -} - -// A Huffman tree is a full binary tree; and in a full binary tree with L -// leaves, the total number of nodes N = 2 * L - 1. -static int HuffmanTreeMaxNodes(int num_leaves) { - return (2 * num_leaves - 1); -} - -static int HuffmanTreeAllocate(HuffmanTree* const tree, int num_nodes) { - assert(tree != NULL); - tree->root_ = - (HuffmanTreeNode*)WebPSafeMalloc(num_nodes, sizeof(*tree->root_)); - return (tree->root_ != NULL); -} - -static int TreeInit(HuffmanTree* const tree, int num_leaves) { - assert(tree != NULL); - if (num_leaves == 0) return 0; - tree->max_nodes_ = HuffmanTreeMaxNodes(num_leaves); - assert(tree->max_nodes_ < (1 << 16)); // limit for the lut_jump_ table - if (!HuffmanTreeAllocate(tree, tree->max_nodes_)) return 0; - TreeNodeInit(tree->root_); // Initialize root. - tree->num_nodes_ = 1; - memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_)); - memset(tree->lut_jump_, 0, sizeof(tree->lut_jump_)); - return 1; -} - -void VP8LHuffmanTreeFree(HuffmanTree* const tree) { - if (tree != NULL) { - WebPSafeFree(tree->root_); - tree->root_ = NULL; - tree->max_nodes_ = 0; - tree->num_nodes_ = 0; - } -} HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) { HTreeGroup* const htree_groups = - (HTreeGroup*)WebPSafeCalloc(num_htree_groups, sizeof(*htree_groups)); - assert(num_htree_groups <= MAX_HTREE_GROUPS); + (HTreeGroup*)WebPSafeMalloc(num_htree_groups, sizeof(*htree_groups)); if (htree_groups == NULL) { return NULL; } + assert(num_htree_groups <= MAX_HTREE_GROUPS); return htree_groups; } -void VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups) { +void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) { if (htree_groups != NULL) { - int i, j; - for (i = 0; i < num_htree_groups; ++i) { - HuffmanTree* const htrees = htree_groups[i].htrees_; - for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) { - VP8LHuffmanTreeFree(&htrees[j]); - } - } WebPSafeFree(htree_groups); } } -int VP8LHuffmanCodeLengthsToCodes( - const int* const code_lengths, int code_lengths_size, - int* const huff_codes) { - int symbol; - int code_len; - int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; - int curr_code; - int next_codes[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; - int max_code_length = 0; - - assert(code_lengths != NULL); - assert(code_lengths_size > 0); - assert(huff_codes != NULL); - - // Calculate max code length. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - if (code_lengths[symbol] > max_code_length) { - max_code_length = code_lengths[symbol]; - } - } - if (max_code_length > MAX_ALLOWED_CODE_LENGTH) return 0; - - // Calculate code length histogram. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - ++code_length_hist[code_lengths[symbol]]; +// Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the +// bit-wise reversal of the len least significant bits of key. +static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) { + uint32_t step = 1 << (len - 1); + while (key & step) { + step >>= 1; } - code_length_hist[0] = 0; - - // Calculate the initial values of 'next_codes' for each code length. - // next_codes[code_len] denotes the code to be assigned to the next symbol - // of code length 'code_len'. - curr_code = 0; - next_codes[0] = -1; // Unused, as code length = 0 implies code doesn't exist. - for (code_len = 1; code_len <= max_code_length; ++code_len) { - curr_code = (curr_code + code_length_hist[code_len - 1]) << 1; - next_codes[code_len] = curr_code; + return (key & (step - 1)) + step; +} + +// Stores code in table[0], table[step], table[2*step], ..., table[end]. +// Assumes that end is an integer multiple of step. +static WEBP_INLINE void ReplicateValue(HuffmanCode* table, + int step, int end, + HuffmanCode code) { + assert(end % step == 0); + do { + end -= step; + table[end] = code; + } while (end > 0); +} + +// Returns the table width of the next 2nd level table. count is the histogram +// of bit lengths for the remaining symbols, len is the code length of the next +// processed symbol +static WEBP_INLINE int NextTableBitSize(const int* const count, + int len, int root_bits) { + int left = 1 << (len - root_bits); + while (len < MAX_ALLOWED_CODE_LENGTH) { + left -= count[len]; + if (left <= 0) break; + ++len; + left <<= 1; } + return len - root_bits; +} + +int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, + const int code_lengths[], int code_lengths_size) { + HuffmanCode* table = root_table; // next available space in table + int total_size = 1 << root_bits; // total size root table + 2nd level table + int* sorted = NULL; // symbols sorted by code length + int len; // current code length + int symbol; // symbol index in original or sorted table + // number of codes of each length: + int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; + // offsets in sorted table for each length: + int offset[MAX_ALLOWED_CODE_LENGTH + 1]; + + assert(code_lengths_size != 0); + assert(code_lengths != NULL); + assert(root_table != NULL); + assert(root_bits > 0); - // Get symbols. + // Build histogram of code lengths. for (symbol = 0; symbol < code_lengths_size; ++symbol) { - if (code_lengths[symbol] > 0) { - huff_codes[symbol] = next_codes[code_lengths[symbol]]++; - } else { - huff_codes[symbol] = NON_EXISTENT_SYMBOL; + if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) { + return 0; } + ++count[code_lengths[symbol]]; } - return 1; -} - -#ifndef USE_LUT_REVERSE_BITS -static int ReverseBitsShort(int bits, int num_bits) { - int retval = 0; - int i; - assert(num_bits <= 8); // Not a hard requirement, just for coherency. - for (i = 0; i < num_bits; ++i) { - retval <<= 1; - retval |= bits & 1; - bits >>= 1; + // Error, all code lengths are zeros. + if (count[0] == code_lengths_size) { + return 0; } - return retval; -} - -#else - -static const uint8_t kReversedBits[16] = { // Pre-reversed 4-bit values. - 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, - 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf -}; -static int ReverseBitsShort(int bits, int num_bits) { - const uint8_t v = (kReversedBits[bits & 0xf] << 4) | kReversedBits[bits >> 4]; - assert(num_bits <= 8); - return v >> (8 - num_bits); -} - -#endif - -static int TreeAddSymbol(HuffmanTree* const tree, - int symbol, int code, int code_length) { - int step = HUFF_LUT_BITS; - int base_code; - HuffmanTreeNode* node = tree->root_; - const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_; - assert(symbol == (int16_t)symbol); - if (code_length <= HUFF_LUT_BITS) { - int i; - base_code = ReverseBitsShort(code, code_length); - for (i = 0; i < (1 << (HUFF_LUT_BITS - code_length)); ++i) { - const int idx = base_code | (i << code_length); - tree->lut_symbol_[idx] = (int16_t)symbol; - tree->lut_bits_[idx] = code_length; - } - } else { - base_code = ReverseBitsShort((code >> (code_length - HUFF_LUT_BITS)), - HUFF_LUT_BITS); - } - while (code_length-- > 0) { - if (node >= max_node) { + // Generate offsets into sorted symbol table by code length. + offset[1] = 0; + for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) { + if (count[len] > (1 << len)) { return 0; } - if (NodeIsEmpty(node)) { - if (IsFull(tree)) return 0; // error: too many symbols. - AssignChildren(tree, node); - } else if (!HuffmanTreeNodeIsNotLeaf(node)) { - return 0; // leaf is already occupied. - } - node += node->children_ + ((code >> code_length) & 1); - if (--step == 0) { - tree->lut_jump_[base_code] = (int16_t)(node - tree->root_); - } - } - if (NodeIsEmpty(node)) { - node->children_ = 0; // turn newly created node into a leaf. - } else if (HuffmanTreeNodeIsNotLeaf(node)) { - return 0; // trying to assign a symbol to already used code. + offset[len + 1] = offset[len] + count[len]; } - node->symbol_ = symbol; // Add symbol in this node. - return 1; -} - -int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree, - const int* const code_lengths, - int* const codes, - int code_lengths_size) { - int symbol; - int num_symbols = 0; - int root_symbol = 0; - assert(tree != NULL); - assert(code_lengths != NULL); + sorted = (int*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted)); + if (sorted == NULL) { + return 0; + } - // Find out number of symbols and the root symbol. + // Sort symbols by length, by symbol order within each length. for (symbol = 0; symbol < code_lengths_size; ++symbol) { + const int symbol_code_length = code_lengths[symbol]; if (code_lengths[symbol] > 0) { - // Note: code length = 0 indicates non-existent symbol. - ++num_symbols; - root_symbol = symbol; + sorted[offset[symbol_code_length]++] = symbol; } } - // Initialize the tree. Will fail for num_symbols = 0 - if (!TreeInit(tree, num_symbols)) return 0; - - // Build tree. - if (num_symbols == 1) { // Trivial case. - const int max_symbol = code_lengths_size; - if (root_symbol < 0 || root_symbol >= max_symbol) { - VP8LHuffmanTreeFree(tree); - return 0; - } - return TreeAddSymbol(tree, root_symbol, 0, 0); - } else { // Normal case. - int ok = 0; - memset(codes, 0, code_lengths_size * sizeof(*codes)); + // Special case code with only one value. + if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) { + HuffmanCode code; + code.bits = 0; + code.value = (uint16_t)sorted[0]; + ReplicateValue(table, 1, total_size, code); + WebPSafeFree(sorted); + return total_size; + } - if (!VP8LHuffmanCodeLengthsToCodes(code_lengths, code_lengths_size, - codes)) { - goto End; + { + int step; // step size to replicate values in current table + uint32_t low = -1; // low bits for current root entry + uint32_t mask = total_size - 1; // mask for low bits + uint32_t key = 0; // reversed prefix code + int num_nodes = 1; // number of Huffman tree nodes + int num_open = 1; // number of open branches in current tree level + int table_bits = root_bits; // key length of current table + int table_size = 1 << table_bits; // size of current table + symbol = 0; + // Fill in root table. + for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) { + num_open <<= 1; + num_nodes += num_open; + num_open -= count[len]; + if (num_open < 0) { + WebPSafeFree(sorted); + return 0; + } + for (; count[len] > 0; --count[len]) { + HuffmanCode code; + code.bits = (uint8_t)len; + code.value = (uint16_t)sorted[symbol++]; + ReplicateValue(&table[key], step, table_size, code); + key = GetNextKey(key, len); + } } - // Add symbols one-by-one. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - if (code_lengths[symbol] > 0) { - if (!TreeAddSymbol(tree, symbol, codes[symbol], - code_lengths[symbol])) { - goto End; + // Fill in 2nd level tables and add pointers to root table. + for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH; + ++len, step <<= 1) { + num_open <<= 1; + num_nodes += num_open; + num_open -= count[len]; + if (num_open < 0) { + WebPSafeFree(sorted); + return 0; + } + for (; count[len] > 0; --count[len]) { + HuffmanCode code; + if ((key & mask) != low) { + table += table_size; + table_bits = NextTableBitSize(count, len, root_bits); + table_size = 1 << table_bits; + total_size += table_size; + low = key & mask; + root_table[low].bits = (uint8_t)(table_bits + root_bits); + root_table[low].value = (uint16_t)((table - root_table) - low); } + code.bits = (uint8_t)(len - root_bits); + code.value = (uint16_t)sorted[symbol++]; + ReplicateValue(&table[key >> root_bits], step, table_size, code); + key = GetNextKey(key, len); } } - ok = 1; - End: - ok = ok && IsFull(tree); - if (!ok) VP8LHuffmanTreeFree(tree); - return ok; - } -} - -int VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree, - const int* const code_lengths, - const int* const codes, - const int* const symbols, int max_symbol, - int num_symbols) { - int ok = 0; - int i; - assert(tree != NULL); - assert(code_lengths != NULL); - assert(codes != NULL); - assert(symbols != NULL); - - // Initialize the tree. Will fail if num_symbols = 0. - if (!TreeInit(tree, num_symbols)) return 0; - // Add symbols one-by-one. - for (i = 0; i < num_symbols; ++i) { - if (codes[i] != NON_EXISTENT_SYMBOL) { - if (symbols[i] < 0 || symbols[i] >= max_symbol) { - goto End; - } - if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) { - goto End; - } + // Check if tree is full. + if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) { + WebPSafeFree(sorted); + return 0; } } - ok = 1; - End: - ok = ok && IsFull(tree); - if (!ok) VP8LHuffmanTreeFree(tree); - return ok; + + WebPSafeFree(sorted); + return total_size; } diff --git a/src/3rdparty/libwebp/src/utils/huffman.h b/src/3rdparty/libwebp/src/utils/huffman.h index 624bc17..c6dd6aa 100644 --- a/src/3rdparty/libwebp/src/utils/huffman.h +++ b/src/3rdparty/libwebp/src/utils/huffman.h @@ -22,78 +22,64 @@ extern "C" { #endif -// A node of a Huffman tree. -typedef struct { - int symbol_; - int children_; // delta offset to both children (contiguous) or 0 if leaf. -} HuffmanTreeNode; +#define HUFFMAN_TABLE_BITS 8 +#define HUFFMAN_TABLE_MASK ((1 << HUFFMAN_TABLE_BITS) - 1) + +#define LENGTHS_TABLE_BITS 7 +#define LENGTHS_TABLE_MASK ((1 << LENGTHS_TABLE_BITS) - 1) -// Huffman Tree. -#define HUFF_LUT_BITS 7 -#define HUFF_LUT (1U << HUFF_LUT_BITS) -typedef struct HuffmanTree HuffmanTree; -struct HuffmanTree { - // Fast lookup for short bit lengths. - uint8_t lut_bits_[HUFF_LUT]; - int16_t lut_symbol_[HUFF_LUT]; - int16_t lut_jump_[HUFF_LUT]; - // Complete tree for lookups. - HuffmanTreeNode* root_; // all the nodes, starting at root. - int max_nodes_; // max number of nodes - int num_nodes_; // number of currently occupied nodes -}; -// Huffman Tree group. +// Huffman lookup table entry +typedef struct { + uint8_t bits; // number of bits used for this symbol + uint16_t value; // symbol value or table offset +} HuffmanCode; + +// long version for holding 32b values +typedef struct { + int bits; // number of bits used for this symbol, + // or an impossible value if not a literal code. + uint32_t value; // 32b packed ARGB value if literal, + // or non-literal symbol otherwise +} HuffmanCode32; + +#define HUFFMAN_PACKED_BITS 6 +#define HUFFMAN_PACKED_TABLE_SIZE (1u << HUFFMAN_PACKED_BITS) + +// Huffman table group. +// Includes special handling for the following cases: +// - is_trivial_literal: one common literal base for RED/BLUE/ALPHA (not GREEN) +// - is_trivial_code: only 1 code (no bit is read from bitstream) +// - use_packed_table: few enough literal symbols, so all the bit codes +// can fit into a small look-up table packed_table[] +// The common literal base, if applicable, is stored in 'literal_arb'. typedef struct HTreeGroup HTreeGroup; struct HTreeGroup { - HuffmanTree htrees_[HUFFMAN_CODES_PER_META_CODE]; + HuffmanCode* htrees[HUFFMAN_CODES_PER_META_CODE]; + int is_trivial_literal; // True, if huffman trees for Red, Blue & Alpha + // Symbols are trivial (have a single code). + uint32_t literal_arb; // If is_trivial_literal is true, this is the + // ARGB value of the pixel, with Green channel + // being set to zero. + int is_trivial_code; // true if is_trivial_literal with only one code + int use_packed_table; // use packed table below for short literal code + // table mapping input bits to a packed values, or escape case to literal code + HuffmanCode32 packed_table[HUFFMAN_PACKED_TABLE_SIZE]; }; -// Returns true if the given node is not a leaf of the Huffman tree. -static WEBP_INLINE int HuffmanTreeNodeIsNotLeaf( - const HuffmanTreeNode* const node) { - return node->children_; -} - -// Go down one level. Most critical function. 'right_child' must be 0 or 1. -static WEBP_INLINE const HuffmanTreeNode* HuffmanTreeNextNode( - const HuffmanTreeNode* node, int right_child) { - return node + node->children_ + right_child; -} - -// Releases the nodes of the Huffman tree. -// Note: It does NOT free 'tree' itself. -void VP8LHuffmanTreeFree(HuffmanTree* const tree); - // Creates the instance of HTreeGroup with specified number of tree-groups. HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); // Releases the memory allocated for HTreeGroup. -void VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups); - -// Builds Huffman tree assuming code lengths are implicitly in symbol order. -// The 'huff_codes' and 'code_lengths' are pre-allocated temporary memory -// buffers, used for creating the huffman tree. -// Returns false in case of error (invalid tree or memory error). -int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree, - const int* const code_lengths, - int* const huff_codes, - int code_lengths_size); - -// Build a Huffman tree with explicitly given lists of code lengths, codes -// and symbols. Verifies that all symbols added are smaller than max_symbol. -// Returns false in case of an invalid symbol, invalid tree or memory error. -int VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree, - const int* const code_lengths, - const int* const codes, - const int* const symbols, int max_symbol, - int num_symbols); - -// Utility: converts Huffman code lengths to corresponding Huffman codes. -// 'huff_codes' should be pre-allocated. -// Returns false in case of error (memory allocation, invalid codes). -int VP8LHuffmanCodeLengthsToCodes(const int* const code_lengths, - int code_lengths_size, int* const huff_codes); +void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups); + +// Builds Huffman lookup table assuming code lengths are in symbol order. +// The 'code_lengths' is pre-allocated temporary memory buffer used for creating +// the huffman table. +// Returns built table size or 0 in case of error (invalid tree or +// memory error). +int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, + const int code_lengths[], int code_lengths_size); #ifdef __cplusplus } // extern "C" diff --git a/src/3rdparty/libwebp/src/utils/huffman_encode.h b/src/3rdparty/libwebp/src/utils/huffman_encode.h index 91aa18f..a157165 100644 --- a/src/3rdparty/libwebp/src/utils/huffman_encode.h +++ b/src/3rdparty/libwebp/src/utils/huffman_encode.h @@ -34,10 +34,9 @@ typedef struct { } HuffmanTreeCode; // Struct to represent the Huffman tree. -// TODO(vikasa): Add comment for the fields of the Struct. typedef struct { - uint32_t total_count_; - int value_; + uint32_t total_count_; // Symbol frequency. + int value_; // Symbol value. int pool_index_left_; // Index for the left sub-tree. int pool_index_right_; // Index for the right sub-tree. } HuffmanTree; diff --git a/src/3rdparty/libwebp/src/utils/rescaler.c b/src/3rdparty/libwebp/src/utils/rescaler.c index 3a43229..00c9300 100644 --- a/src/3rdparty/libwebp/src/utils/rescaler.c +++ b/src/3rdparty/libwebp/src/utils/rescaler.c @@ -14,451 +14,8 @@ #include <assert.h> #include <stdlib.h> #include <string.h> -#include "./rescaler.h" #include "../dsp/dsp.h" - -//------------------------------------------------------------------------------ -// Implementations of critical functions ImportRow / ExportRow - -// Import a row of data and save its contribution in the rescaler. -// 'channel' denotes the channel number to be imported. 'Expand' corresponds to -// the wrk->x_expand case. Otherwise, 'Shrink' is to be used. -typedef void (*WebPRescalerImportRowFunc)(WebPRescaler* const wrk, - const uint8_t* src); -static WebPRescalerImportRowFunc WebPRescalerImportRowExpand; -static WebPRescalerImportRowFunc WebPRescalerImportRowShrink; - -// Export one row (starting at x_out position) from rescaler. -// 'Expand' corresponds to the wrk->y_expand case. -// Otherwise 'Shrink' is to be used -typedef void (*WebPRescalerExportRowFunc)(WebPRescaler* const wrk); -static WebPRescalerExportRowFunc WebPRescalerExportRowExpand; -static WebPRescalerExportRowFunc WebPRescalerExportRowShrink; - -#define WEBP_RESCALER_RFIX 32 // fixed-point precision for multiplies -#define WEBP_RESCALER_ONE (1ull << WEBP_RESCALER_RFIX) -#define WEBP_RESCALER_FRAC(x, y) \ - ((uint32_t)(((uint64_t)(x) << WEBP_RESCALER_RFIX) / (y))) -#define ROUNDER (WEBP_RESCALER_ONE >> 1) -#define MULT_FIX(x, y) (((uint64_t)(x) * (y) + ROUNDER) >> WEBP_RESCALER_RFIX) - -static void ImportRowExpandC(WebPRescaler* const wrk, const uint8_t* src) { - const int x_stride = wrk->num_channels; - const int x_out_max = wrk->dst_width * wrk->num_channels; - int channel; - assert(!WebPRescalerInputDone(wrk)); - assert(wrk->x_expand); - for (channel = 0; channel < x_stride; ++channel) { - int x_in = channel; - int x_out = channel; - // simple bilinear interpolation - int accum = wrk->x_add; - int left = src[x_in]; - int right = (wrk->src_width > 1) ? src[x_in + x_stride] : left; - x_in += x_stride; - while (1) { - wrk->frow[x_out] = right * wrk->x_add + (left - right) * accum; - x_out += x_stride; - if (x_out >= x_out_max) break; - accum -= wrk->x_sub; - if (accum < 0) { - left = right; - x_in += x_stride; - assert(x_in < wrk->src_width * x_stride); - right = src[x_in]; - accum += wrk->x_add; - } - } - assert(wrk->x_sub == 0 /* <- special case for src_width=1 */ || accum == 0); - } -} - -static void ImportRowShrinkC(WebPRescaler* const wrk, const uint8_t* src) { - const int x_stride = wrk->num_channels; - const int x_out_max = wrk->dst_width * wrk->num_channels; - int channel; - assert(!WebPRescalerInputDone(wrk)); - assert(!wrk->x_expand); - for (channel = 0; channel < x_stride; ++channel) { - int x_in = channel; - int x_out = channel; - uint32_t sum = 0; - int accum = 0; - while (x_out < x_out_max) { - uint32_t base = 0; - accum += wrk->x_add; - while (accum > 0) { - accum -= wrk->x_sub; - assert(x_in < wrk->src_width * x_stride); - base = src[x_in]; - sum += base; - x_in += x_stride; - } - { // Emit next horizontal pixel. - const rescaler_t frac = base * (-accum); - wrk->frow[x_out] = sum * wrk->x_sub - frac; - // fresh fractional start for next pixel - sum = (int)MULT_FIX(frac, wrk->fx_scale); - } - x_out += x_stride; - } - assert(accum == 0); - } -} - -//------------------------------------------------------------------------------ -// Row export - -static void ExportRowExpandC(WebPRescaler* const wrk) { - int x_out; - uint8_t* const dst = wrk->dst; - rescaler_t* const irow = wrk->irow; - const int x_out_max = wrk->dst_width * wrk->num_channels; - const rescaler_t* const frow = wrk->frow; - assert(!WebPRescalerOutputDone(wrk)); - assert(wrk->y_accum <= 0); - assert(wrk->y_expand); - assert(wrk->y_sub != 0); - if (wrk->y_accum == 0) { - for (x_out = 0; x_out < x_out_max; ++x_out) { - const uint32_t J = frow[x_out]; - const int v = (int)MULT_FIX(J, wrk->fy_scale); - assert(v >= 0 && v <= 255); - dst[x_out] = v; - } - } else { - const uint32_t B = WEBP_RESCALER_FRAC(-wrk->y_accum, wrk->y_sub); - const uint32_t A = (uint32_t)(WEBP_RESCALER_ONE - B); - for (x_out = 0; x_out < x_out_max; ++x_out) { - const uint64_t I = (uint64_t)A * frow[x_out] - + (uint64_t)B * irow[x_out]; - const uint32_t J = (uint32_t)((I + ROUNDER) >> WEBP_RESCALER_RFIX); - const int v = (int)MULT_FIX(J, wrk->fy_scale); - assert(v >= 0 && v <= 255); - dst[x_out] = v; - } - } -} - -static void ExportRowShrinkC(WebPRescaler* const wrk) { - int x_out; - uint8_t* const dst = wrk->dst; - rescaler_t* const irow = wrk->irow; - const int x_out_max = wrk->dst_width * wrk->num_channels; - const rescaler_t* const frow = wrk->frow; - const uint32_t yscale = wrk->fy_scale * (-wrk->y_accum); - assert(!WebPRescalerOutputDone(wrk)); - assert(wrk->y_accum <= 0); - assert(!wrk->y_expand); - if (yscale) { - for (x_out = 0; x_out < x_out_max; ++x_out) { - const uint32_t frac = (uint32_t)MULT_FIX(frow[x_out], yscale); - const int v = (int)MULT_FIX(irow[x_out] - frac, wrk->fxy_scale); - assert(v >= 0 && v <= 255); - dst[x_out] = v; - irow[x_out] = frac; // new fractional start - } - } else { - for (x_out = 0; x_out < x_out_max; ++x_out) { - const int v = (int)MULT_FIX(irow[x_out], wrk->fxy_scale); - assert(v >= 0 && v <= 255); - dst[x_out] = v; - irow[x_out] = 0; - } - } -} - -//------------------------------------------------------------------------------ -// Main entry calls - -void WebPRescalerImportRow(WebPRescaler* const wrk, const uint8_t* src) { - assert(!WebPRescalerInputDone(wrk)); - if (!wrk->x_expand) { - WebPRescalerImportRowShrink(wrk, src); - } else { - WebPRescalerImportRowExpand(wrk, src); - } -} - -void WebPRescalerExportRow(WebPRescaler* const wrk) { - if (wrk->y_accum <= 0) { - assert(!WebPRescalerOutputDone(wrk)); - if (wrk->y_expand) { - WebPRescalerExportRowExpand(wrk); - } else if (wrk->fxy_scale) { - WebPRescalerExportRowShrink(wrk); - } else { // very special case for src = dst = 1x1 - int i; - assert(wrk->src_width == 1 && wrk->dst_width <= 2); - assert(wrk->src_height == 1 && wrk->dst_height == 1); - for (i = 0; i < wrk->num_channels * wrk->dst_width; ++i) { - wrk->dst[i] = wrk->irow[i]; - wrk->irow[i] = 0; - } - } - wrk->y_accum += wrk->y_add; - wrk->dst += wrk->dst_stride; - ++wrk->dst_y; - } -} - -//------------------------------------------------------------------------------ -// MIPS version - -#if defined(WEBP_USE_MIPS32) - -static void ImportRowShrinkMIPS(WebPRescaler* const wrk, const uint8_t* src) { - const int x_stride = wrk->num_channels; - const int x_out_max = wrk->dst_width * wrk->num_channels; - const int fx_scale = wrk->fx_scale; - const int x_add = wrk->x_add; - const int x_sub = wrk->x_sub; - const int x_stride1 = x_stride << 2; - int channel; - assert(!wrk->x_expand); - assert(!WebPRescalerInputDone(wrk)); - - for (channel = 0; channel < x_stride; ++channel) { - const uint8_t* src1 = src + channel; - rescaler_t* frow = wrk->frow + channel; - int temp1, temp2, temp3; - int base, frac, sum; - int accum, accum1; - int loop_c = x_out_max - channel; - - __asm__ volatile ( - "li %[temp1], 0x8000 \n\t" - "li %[temp2], 0x10000 \n\t" - "li %[sum], 0 \n\t" - "li %[accum], 0 \n\t" - "1: \n\t" - "addu %[accum], %[accum], %[x_add] \n\t" - "li %[base], 0 \n\t" - "blez %[accum], 3f \n\t" - "2: \n\t" - "lbu %[base], 0(%[src1]) \n\t" - "subu %[accum], %[accum], %[x_sub] \n\t" - "addu %[src1], %[src1], %[x_stride] \n\t" - "addu %[sum], %[sum], %[base] \n\t" - "bgtz %[accum], 2b \n\t" - "3: \n\t" - "negu %[accum1], %[accum] \n\t" - "mul %[frac], %[base], %[accum1] \n\t" - "mul %[temp3], %[sum], %[x_sub] \n\t" - "subu %[loop_c], %[loop_c], %[x_stride] \n\t" - "mult %[temp1], %[temp2] \n\t" - "maddu %[frac], %[fx_scale] \n\t" - "mfhi %[sum] \n\t" - "subu %[temp3], %[temp3], %[frac] \n\t" - "sw %[temp3], 0(%[frow]) \n\t" - "addu %[frow], %[frow], %[x_stride1] \n\t" - "bgtz %[loop_c], 1b \n\t" - : [accum]"=&r"(accum), [src1]"+r"(src1), [temp3]"=&r"(temp3), - [sum]"=&r"(sum), [base]"=&r"(base), [frac]"=&r"(frac), - [frow]"+r"(frow), [accum1]"=&r"(accum1), - [temp2]"=&r"(temp2), [temp1]"=&r"(temp1) - : [x_stride]"r"(x_stride), [fx_scale]"r"(fx_scale), - [x_sub]"r"(x_sub), [x_add]"r"(x_add), - [loop_c]"r"(loop_c), [x_stride1]"r"(x_stride1) - : "memory", "hi", "lo" - ); - assert(accum == 0); - } -} - -static void ImportRowExpandMIPS(WebPRescaler* const wrk, const uint8_t* src) { - const int x_stride = wrk->num_channels; - const int x_out_max = wrk->dst_width * wrk->num_channels; - const int x_add = wrk->x_add; - const int x_sub = wrk->x_sub; - const int src_width = wrk->src_width; - const int x_stride1 = x_stride << 2; - int channel; - assert(wrk->x_expand); - assert(!WebPRescalerInputDone(wrk)); - - for (channel = 0; channel < x_stride; ++channel) { - const uint8_t* src1 = src + channel; - rescaler_t* frow = wrk->frow + channel; - int temp1, temp2, temp3, temp4; - int frac; - int accum; - int x_out = channel; - - __asm__ volatile ( - "addiu %[temp3], %[src_width], -1 \n\t" - "lbu %[temp2], 0(%[src1]) \n\t" - "addu %[src1], %[src1], %[x_stride] \n\t" - "bgtz %[temp3], 0f \n\t" - "addiu %[temp1], %[temp2], 0 \n\t" - "b 3f \n\t" - "0: \n\t" - "lbu %[temp1], 0(%[src1]) \n\t" - "3: \n\t" - "addiu %[accum], %[x_add], 0 \n\t" - "1: \n\t" - "subu %[temp3], %[temp2], %[temp1] \n\t" - "mul %[temp3], %[temp3], %[accum] \n\t" - "mul %[temp4], %[temp1], %[x_add] \n\t" - "addu %[temp3], %[temp4], %[temp3] \n\t" - "sw %[temp3], 0(%[frow]) \n\t" - "addu %[frow], %[frow], %[x_stride1] \n\t" - "addu %[x_out], %[x_out], %[x_stride] \n\t" - "subu %[temp3], %[x_out], %[x_out_max] \n\t" - "bgez %[temp3], 2f \n\t" - "subu %[accum], %[accum], %[x_sub] \n\t" - "bgez %[accum], 4f \n\t" - "addiu %[temp2], %[temp1], 0 \n\t" - "addu %[src1], %[src1], %[x_stride] \n\t" - "lbu %[temp1], 0(%[src1]) \n\t" - "addu %[accum], %[accum], %[x_add] \n\t" - "4: \n\t" - "b 1b \n\t" - "2: \n\t" - : [src1]"+r"(src1), [accum]"=&r"(accum), [temp1]"=&r"(temp1), - [temp2]"=&r"(temp2), [temp3]"=&r"(temp3), [temp4]"=&r"(temp4), - [x_out]"+r"(x_out), [frac]"=&r"(frac), [frow]"+r"(frow) - : [x_stride]"r"(x_stride), [x_add]"r"(x_add), [x_sub]"r"(x_sub), - [x_stride1]"r"(x_stride1), [src_width]"r"(src_width), - [x_out_max]"r"(x_out_max) - : "memory", "hi", "lo" - ); - assert(wrk->x_sub == 0 /* <- special case for src_width=1 */ || accum == 0); - } -} - -//------------------------------------------------------------------------------ -// Row export - -static void ExportRowExpandMIPS(WebPRescaler* const wrk) { - uint8_t* dst = wrk->dst; - rescaler_t* irow = wrk->irow; - const int x_out_max = wrk->dst_width * wrk->num_channels; - const rescaler_t* frow = wrk->frow; - int temp0, temp1, temp3, temp4, temp5, loop_end; - const int temp2 = (int)wrk->fy_scale; - const int temp6 = x_out_max << 2; - assert(!WebPRescalerOutputDone(wrk)); - assert(wrk->y_accum <= 0); - assert(wrk->y_expand); - assert(wrk->y_sub != 0); - if (wrk->y_accum == 0) { - __asm__ volatile ( - "li %[temp3], 0x10000 \n\t" - "li %[temp4], 0x8000 \n\t" - "addu %[loop_end], %[frow], %[temp6] \n\t" - "1: \n\t" - "lw %[temp0], 0(%[frow]) \n\t" - "addiu %[dst], %[dst], 1 \n\t" - "addiu %[frow], %[frow], 4 \n\t" - "mult %[temp3], %[temp4] \n\t" - "maddu %[temp0], %[temp2] \n\t" - "mfhi %[temp5] \n\t" - "sb %[temp5], -1(%[dst]) \n\t" - "bne %[frow], %[loop_end], 1b \n\t" - : [temp0]"=&r"(temp0), [temp1]"=&r"(temp1), [temp3]"=&r"(temp3), - [temp4]"=&r"(temp4), [temp5]"=&r"(temp5), [frow]"+r"(frow), - [dst]"+r"(dst), [loop_end]"=&r"(loop_end) - : [temp2]"r"(temp2), [temp6]"r"(temp6) - : "memory", "hi", "lo" - ); - } else { - const uint32_t B = WEBP_RESCALER_FRAC(-wrk->y_accum, wrk->y_sub); - const uint32_t A = (uint32_t)(WEBP_RESCALER_ONE - B); - __asm__ volatile ( - "li %[temp3], 0x10000 \n\t" - "li %[temp4], 0x8000 \n\t" - "addu %[loop_end], %[frow], %[temp6] \n\t" - "1: \n\t" - "lw %[temp0], 0(%[frow]) \n\t" - "lw %[temp1], 0(%[irow]) \n\t" - "addiu %[dst], %[dst], 1 \n\t" - "mult %[temp3], %[temp4] \n\t" - "maddu %[A], %[temp0] \n\t" - "maddu %[B], %[temp1] \n\t" - "addiu %[frow], %[frow], 4 \n\t" - "addiu %[irow], %[irow], 4 \n\t" - "mfhi %[temp5] \n\t" - "mult %[temp3], %[temp4] \n\t" - "maddu %[temp5], %[temp2] \n\t" - "mfhi %[temp5] \n\t" - "sb %[temp5], -1(%[dst]) \n\t" - "bne %[frow], %[loop_end], 1b \n\t" - : [temp0]"=&r"(temp0), [temp1]"=&r"(temp1), [temp3]"=&r"(temp3), - [temp4]"=&r"(temp4), [temp5]"=&r"(temp5), [frow]"+r"(frow), - [irow]"+r"(irow), [dst]"+r"(dst), [loop_end]"=&r"(loop_end) - : [temp2]"r"(temp2), [temp6]"r"(temp6), [A]"r"(A), [B]"r"(B) - : "memory", "hi", "lo" - ); - } -} - -static void ExportRowShrinkMIPS(WebPRescaler* const wrk) { - const int x_out_max = wrk->dst_width * wrk->num_channels; - uint8_t* dst = wrk->dst; - rescaler_t* irow = wrk->irow; - const rescaler_t* frow = wrk->frow; - const int yscale = wrk->fy_scale * (-wrk->y_accum); - int temp0, temp1, temp3, temp4, temp5, loop_end; - const int temp2 = (int)wrk->fxy_scale; - const int temp6 = x_out_max << 2; - - assert(!WebPRescalerOutputDone(wrk)); - assert(wrk->y_accum <= 0); - assert(!wrk->y_expand); - assert(wrk->fxy_scale != 0); - if (yscale) { - __asm__ volatile ( - "li %[temp3], 0x10000 \n\t" - "li %[temp4], 0x8000 \n\t" - "addu %[loop_end], %[frow], %[temp6] \n\t" - "1: \n\t" - "lw %[temp0], 0(%[frow]) \n\t" - "mult %[temp3], %[temp4] \n\t" - "addiu %[frow], %[frow], 4 \n\t" - "maddu %[temp0], %[yscale] \n\t" - "mfhi %[temp1] \n\t" - "lw %[temp0], 0(%[irow]) \n\t" - "addiu %[dst], %[dst], 1 \n\t" - "addiu %[irow], %[irow], 4 \n\t" - "subu %[temp0], %[temp0], %[temp1] \n\t" - "mult %[temp3], %[temp4] \n\t" - "maddu %[temp0], %[temp2] \n\t" - "mfhi %[temp5] \n\t" - "sw %[temp1], -4(%[irow]) \n\t" - "sb %[temp5], -1(%[dst]) \n\t" - "bne %[frow], %[loop_end], 1b \n\t" - : [temp0]"=&r"(temp0), [temp1]"=&r"(temp1), [temp3]"=&r"(temp3), - [temp4]"=&r"(temp4), [temp5]"=&r"(temp5), [frow]"+r"(frow), - [irow]"+r"(irow), [dst]"+r"(dst), [loop_end]"=&r"(loop_end) - : [temp2]"r"(temp2), [yscale]"r"(yscale), [temp6]"r"(temp6) - : "memory", "hi", "lo" - ); - } else { - __asm__ volatile ( - "li %[temp3], 0x10000 \n\t" - "li %[temp4], 0x8000 \n\t" - "addu %[loop_end], %[irow], %[temp6] \n\t" - "1: \n\t" - "lw %[temp0], 0(%[irow]) \n\t" - "addiu %[dst], %[dst], 1 \n\t" - "addiu %[irow], %[irow], 4 \n\t" - "mult %[temp3], %[temp4] \n\t" - "maddu %[temp0], %[temp2] \n\t" - "mfhi %[temp5] \n\t" - "sw $zero, -4(%[irow]) \n\t" - "sb %[temp5], -1(%[dst]) \n\t" - "bne %[irow], %[loop_end], 1b \n\t" - : [temp0]"=&r"(temp0), [temp1]"=&r"(temp1), [temp3]"=&r"(temp3), - [temp4]"=&r"(temp4), [temp5]"=&r"(temp5), [irow]"+r"(irow), - [dst]"+r"(dst), [loop_end]"=&r"(loop_end) - : [temp2]"r"(temp2), [temp6]"r"(temp6) - : "memory", "hi", "lo" - ); - } -} - -#endif // WEBP_USE_MIPS32 +#include "./rescaler.h" //------------------------------------------------------------------------------ @@ -510,30 +67,37 @@ void WebPRescalerInit(WebPRescaler* const wrk, int src_width, int src_height, wrk->frow = work + num_channels * dst_width; memset(work, 0, 2 * dst_width * num_channels * sizeof(*work)); - if (WebPRescalerImportRowExpand == NULL) { - WebPRescalerImportRowExpand = ImportRowExpandC; - WebPRescalerImportRowShrink = ImportRowShrinkC; - WebPRescalerExportRowExpand = ExportRowExpandC; - WebPRescalerExportRowShrink = ExportRowShrinkC; - if (VP8GetCPUInfo != NULL) { -#if defined(WEBP_USE_MIPS32) - if (VP8GetCPUInfo(kMIPS32)) { - WebPRescalerImportRowExpand = ImportRowExpandMIPS; - WebPRescalerImportRowShrink = ImportRowShrinkMIPS; - WebPRescalerExportRowExpand = ExportRowExpandMIPS; - WebPRescalerExportRowShrink = ExportRowShrinkMIPS; - } -#endif + WebPRescalerDspInit(); +} + +int WebPRescalerGetScaledDimensions(int src_width, int src_height, + int* const scaled_width, + int* const scaled_height) { + assert(scaled_width != NULL); + assert(scaled_height != NULL); + { + int width = *scaled_width; + int height = *scaled_height; + + // if width is unspecified, scale original proportionally to height ratio. + if (width == 0) { + width = (src_width * height + src_height / 2) / src_height; } + // if height is unspecified, scale original proportionally to width ratio. + if (height == 0) { + height = (src_height * width + src_width / 2) / src_width; + } + // Check if the overall dimensions still make sense. + if (width <= 0 || height <= 0) { + return 0; + } + + *scaled_width = width; + *scaled_height = height; + return 1; } } -#undef MULT_FIX -#undef WEBP_RESCALER_RFIX -#undef WEBP_RESCALER_ONE -#undef WEBP_RESCALER_FRAC -#undef ROUNDER - //------------------------------------------------------------------------------ // all-in-one calls diff --git a/src/3rdparty/libwebp/src/utils/rescaler.h b/src/3rdparty/libwebp/src/utils/rescaler.h index 8244cfe..98b01a7 100644 --- a/src/3rdparty/libwebp/src/utils/rescaler.h +++ b/src/3rdparty/libwebp/src/utils/rescaler.h @@ -20,9 +20,15 @@ extern "C" { #include "../webp/types.h" +#define WEBP_RESCALER_RFIX 32 // fixed-point precision for multiplies +#define WEBP_RESCALER_ONE (1ull << WEBP_RESCALER_RFIX) +#define WEBP_RESCALER_FRAC(x, y) \ + ((uint32_t)(((uint64_t)(x) << WEBP_RESCALER_RFIX) / (y))) + // Structure used for on-the-fly rescaling typedef uint32_t rescaler_t; // type for side-buffer -typedef struct { +typedef struct WebPRescaler WebPRescaler; +struct WebPRescaler { int x_expand; // true if we're expanding in the x direction int y_expand; // true if we're expanding in the y direction int num_channels; // bytes to jump between pixels @@ -38,7 +44,7 @@ typedef struct { uint8_t* dst; int dst_stride; rescaler_t* irow, *frow; // work buffer -} WebPRescaler; +}; // Initialize a rescaler given scratch area 'work' and dimensions of src & dst. void WebPRescalerInit(WebPRescaler* const rescaler, @@ -48,6 +54,14 @@ void WebPRescalerInit(WebPRescaler* const rescaler, int num_channels, rescaler_t* const work); +// If either 'scaled_width' or 'scaled_height' (but not both) is 0 the value +// will be calculated preserving the aspect ratio, otherwise the values are +// left unmodified. Returns true on success, false if either value is 0 after +// performing the scaling calculation. +int WebPRescalerGetScaledDimensions(int src_width, int src_height, + int* const scaled_width, + int* const scaled_height); + // Returns the number of input lines needed next to produce one output line, // considering that the maximum available input lines are 'max_num_lines'. int WebPRescaleNeededLines(const WebPRescaler* const rescaler, @@ -60,10 +74,6 @@ int WebPRescalerImport(WebPRescaler* const rescaler, int num_rows, // Export as many rows as possible. Return the numbers of rows written. int WebPRescalerExport(WebPRescaler* const rescaler); -void WebPRescalerImportRow(WebPRescaler* const wrk, - const uint8_t* src); -// Export one row (starting at x_out position) from rescaler. -void WebPRescalerExportRow(WebPRescaler* const wrk); // Return true if input is finished static WEBP_INLINE diff --git a/src/3rdparty/libwebp/src/utils/thread.c b/src/3rdparty/libwebp/src/utils/thread.c index 264210b..93f7622 100644 --- a/src/3rdparty/libwebp/src/utils/thread.c +++ b/src/3rdparty/libwebp/src/utils/thread.c @@ -23,11 +23,26 @@ #include <windows.h> typedef HANDLE pthread_t; typedef CRITICAL_SECTION pthread_mutex_t; + +#if _WIN32_WINNT >= 0x0600 // Windows Vista / Server 2008 or greater +#define USE_WINDOWS_CONDITION_VARIABLE +typedef CONDITION_VARIABLE pthread_cond_t; +#else typedef struct { HANDLE waiting_sem_; HANDLE received_sem_; HANDLE signal_event_; } pthread_cond_t; +#endif // _WIN32_WINNT >= 0x600 + +#ifndef WINAPI_FAMILY_PARTITION +#define WINAPI_PARTITION_DESKTOP 1 +#define WINAPI_FAMILY_PARTITION(x) x +#endif + +#if !WINAPI_FAMILY_PARTITION(WINAPI_PARTITION_DESKTOP) +#define USE_CREATE_THREAD +#endif #else // !_WIN32 @@ -52,15 +67,29 @@ struct WebPWorkerImpl { #define THREADFN unsigned int __stdcall #define THREAD_RETURN(val) (unsigned int)((DWORD_PTR)val) +#if _WIN32_WINNT >= 0x0501 // Windows XP or greater +#define WaitForSingleObject(obj, timeout) \ + WaitForSingleObjectEx(obj, timeout, FALSE /*bAlertable*/) +#endif + static int pthread_create(pthread_t* const thread, const void* attr, unsigned int (__stdcall *start)(void*), void* arg) { (void)attr; +#ifdef USE_CREATE_THREAD + *thread = CreateThread(NULL, /* lpThreadAttributes */ + 0, /* dwStackSize */ + start, + arg, + 0, /* dwStackSize */ + NULL); /* lpThreadId */ +#else *thread = (pthread_t)_beginthreadex(NULL, /* void *security */ 0, /* unsigned stack_size */ start, arg, 0, /* unsigned initflag */ NULL); /* unsigned *thrdaddr */ +#endif if (*thread == NULL) return 1; SetThreadPriority(*thread, THREAD_PRIORITY_ABOVE_NORMAL); return 0; @@ -75,7 +104,11 @@ static int pthread_join(pthread_t thread, void** value_ptr) { // Mutex static int pthread_mutex_init(pthread_mutex_t* const mutex, void* mutexattr) { (void)mutexattr; +#if _WIN32_WINNT >= 0x0600 // Windows Vista / Server 2008 or greater + InitializeCriticalSectionEx(mutex, 0 /*dwSpinCount*/, 0 /*Flags*/); +#else InitializeCriticalSection(mutex); +#endif return 0; } @@ -97,14 +130,21 @@ static int pthread_mutex_destroy(pthread_mutex_t* const mutex) { // Condition static int pthread_cond_destroy(pthread_cond_t* const condition) { int ok = 1; +#ifdef USE_WINDOWS_CONDITION_VARIABLE + (void)condition; +#else ok &= (CloseHandle(condition->waiting_sem_) != 0); ok &= (CloseHandle(condition->received_sem_) != 0); ok &= (CloseHandle(condition->signal_event_) != 0); +#endif return !ok; } static int pthread_cond_init(pthread_cond_t* const condition, void* cond_attr) { (void)cond_attr; +#ifdef USE_WINDOWS_CONDITION_VARIABLE + InitializeConditionVariable(condition); +#else condition->waiting_sem_ = CreateSemaphore(NULL, 0, 1, NULL); condition->received_sem_ = CreateSemaphore(NULL, 0, 1, NULL); condition->signal_event_ = CreateEvent(NULL, FALSE, FALSE, NULL); @@ -114,11 +154,15 @@ static int pthread_cond_init(pthread_cond_t* const condition, void* cond_attr) { pthread_cond_destroy(condition); return 1; } +#endif return 0; } static int pthread_cond_signal(pthread_cond_t* const condition) { int ok = 1; +#ifdef USE_WINDOWS_CONDITION_VARIABLE + WakeConditionVariable(condition); +#else if (WaitForSingleObject(condition->waiting_sem_, 0) == WAIT_OBJECT_0) { // a thread is waiting in pthread_cond_wait: allow it to be notified ok = SetEvent(condition->signal_event_); @@ -127,12 +171,16 @@ static int pthread_cond_signal(pthread_cond_t* const condition) { ok &= (WaitForSingleObject(condition->received_sem_, INFINITE) != WAIT_OBJECT_0); } +#endif return !ok; } static int pthread_cond_wait(pthread_cond_t* const condition, pthread_mutex_t* const mutex) { int ok; +#ifdef USE_WINDOWS_CONDITION_VARIABLE + ok = SleepConditionVariableCS(condition, mutex, INFINITE); +#else // note that there is a consumer available so the signal isn't dropped in // pthread_cond_signal if (!ReleaseSemaphore(condition->waiting_sem_, 1, NULL)) @@ -143,6 +191,7 @@ static int pthread_cond_wait(pthread_cond_t* const condition, WAIT_OBJECT_0); ok &= ReleaseSemaphore(condition->received_sem_, 1, NULL); pthread_mutex_lock(mutex); +#endif return !ok; } diff --git a/src/3rdparty/libwebp/src/utils/thread.h b/src/3rdparty/libwebp/src/utils/thread.h index 7bd451b..8408311 100644 --- a/src/3rdparty/libwebp/src/utils/thread.h +++ b/src/3rdparty/libwebp/src/utils/thread.h @@ -79,7 +79,7 @@ typedef struct { // is safe to free the corresponding memory after this call. This function is // not thread-safe. Return false in case of invalid pointer or methods. WEBP_EXTERN(int) WebPSetWorkerInterface( - const WebPWorkerInterface* const interface); + const WebPWorkerInterface* const winterface); // Retrieve the currently set thread worker interface. WEBP_EXTERN(const WebPWorkerInterface*) WebPGetWorkerInterface(void); diff --git a/src/3rdparty/libwebp/src/utils/utils.c b/src/3rdparty/libwebp/src/utils/utils.c index 8ff7f12..d8e3093 100644 --- a/src/3rdparty/libwebp/src/utils/utils.c +++ b/src/3rdparty/libwebp/src/utils/utils.c @@ -12,6 +12,9 @@ // Author: Skal (pascal.massimino@gmail.com) #include <stdlib.h> +#include <string.h> // for memcpy() +#include "../webp/decode.h" +#include "../webp/encode.h" #include "./utils.h" // If PRINT_MEM_INFO is defined, extra info (like total memory used, number of @@ -47,7 +50,6 @@ #if defined(PRINT_MEM_INFO) #include <stdio.h> -#include <stdlib.h> // for abort() static int num_malloc_calls = 0; static int num_calloc_calls = 0; @@ -208,4 +210,30 @@ void WebPSafeFree(void* const ptr) { free(ptr); } +// Public API function. +void WebPFree(void* ptr) { + free(ptr); +} + +//------------------------------------------------------------------------------ + +void WebPCopyPlane(const uint8_t* src, int src_stride, + uint8_t* dst, int dst_stride, int width, int height) { + assert(src != NULL && dst != NULL); + assert(src_stride >= width && dst_stride >= width); + while (height-- > 0) { + memcpy(dst, src, width); + src += src_stride; + dst += dst_stride; + } +} + +void WebPCopyPixels(const WebPPicture* const src, WebPPicture* const dst) { + assert(src != NULL && dst != NULL); + assert(src->width == dst->width && src->height == dst->height); + assert(src->use_argb && dst->use_argb); + WebPCopyPlane((uint8_t*)src->argb, 4 * src->argb_stride, (uint8_t*)dst->argb, + 4 * dst->argb_stride, 4 * src->width, src->height); +} + //------------------------------------------------------------------------------ diff --git a/src/3rdparty/libwebp/src/utils/utils.h b/src/3rdparty/libwebp/src/utils/utils.h index 0bbbcab..f506d66 100644 --- a/src/3rdparty/libwebp/src/utils/utils.h +++ b/src/3rdparty/libwebp/src/utils/utils.h @@ -15,6 +15,10 @@ #ifndef WEBP_UTILS_UTILS_H_ #define WEBP_UTILS_UTILS_H_ +#ifdef HAVE_CONFIG_H +#include "../webp/config.h" +#endif + #include <assert.h> #include "../webp/types.h" @@ -44,6 +48,32 @@ WEBP_EXTERN(void*) WebPSafeCalloc(uint64_t nmemb, size_t size); WEBP_EXTERN(void) WebPSafeFree(void* const ptr); //------------------------------------------------------------------------------ +// Alignment + +#define WEBP_ALIGN_CST 31 +#define WEBP_ALIGN(PTR) ((uintptr_t)((PTR) + WEBP_ALIGN_CST) & ~WEBP_ALIGN_CST) + +#if defined(WEBP_FORCE_ALIGNED) +#include <string.h> +// memcpy() is the safe way of moving potentially unaligned 32b memory. +static WEBP_INLINE uint32_t WebPMemToUint32(const uint8_t* const ptr) { + uint32_t A; + memcpy(&A, (const int*)ptr, sizeof(A)); + return A; +} +static WEBP_INLINE void WebPUint32ToMem(uint8_t* const ptr, uint32_t val) { + memcpy(ptr, &val, sizeof(val)); +} +#else +static WEBP_INLINE uint32_t WebPMemToUint32(const uint8_t* const ptr) { + return *(const uint32_t*)ptr; +} +static WEBP_INLINE void WebPUint32ToMem(uint8_t* const ptr, uint32_t val) { + *(uint32_t*)ptr = val; +} +#endif + +//------------------------------------------------------------------------------ // Reading/writing data. // Read 16, 24 or 32 bits stored in little-endian order. @@ -56,7 +86,7 @@ static WEBP_INLINE int GetLE24(const uint8_t* const data) { } static WEBP_INLINE uint32_t GetLE32(const uint8_t* const data) { - return (uint32_t)GetLE16(data) | (GetLE16(data + 2) << 16); + return GetLE16(data) | ((uint32_t)GetLE16(data + 2) << 16); } // Store 16, 24 or 32 bits in little-endian order. @@ -113,6 +143,21 @@ static WEBP_INLINE int BitsLog2Floor(uint32_t n) { #endif //------------------------------------------------------------------------------ +// Pixel copying. + +struct WebPPicture; + +// Copy width x height pixels from 'src' to 'dst' honoring the strides. +WEBP_EXTERN(void) WebPCopyPlane(const uint8_t* src, int src_stride, + uint8_t* dst, int dst_stride, + int width, int height); + +// Copy ARGB pixels from 'src' to 'dst' honoring strides. 'src' and 'dst' are +// assumed to be already allocated and using ARGB data. +WEBP_EXTERN(void) WebPCopyPixels(const struct WebPPicture* const src, + struct WebPPicture* const dst); + +//------------------------------------------------------------------------------ #ifdef __cplusplus } // extern "C" |