summaryrefslogtreecommitdiffstats
path: root/media/libwebp/src/utils
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 17:32:43 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 17:32:43 +0000
commit6bf0a5cb5034a7e684dcc3500e841785237ce2dd (patch)
treea68f146d7fa01f0134297619fbe7e33db084e0aa /media/libwebp/src/utils
parentInitial commit. (diff)
downloadthunderbird-6bf0a5cb5034a7e684dcc3500e841785237ce2dd.tar.xz
thunderbird-6bf0a5cb5034a7e684dcc3500e841785237ce2dd.zip
Adding upstream version 1:115.7.0.upstream/1%115.7.0upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'media/libwebp/src/utils')
-rw-r--r--media/libwebp/src/utils/bit_reader_inl_utils.h196
-rw-r--r--media/libwebp/src/utils/bit_reader_utils.c298
-rw-r--r--media/libwebp/src/utils/bit_reader_utils.h194
-rw-r--r--media/libwebp/src/utils/bit_writer_utils.c347
-rw-r--r--media/libwebp/src/utils/bit_writer_utils.h154
-rw-r--r--media/libwebp/src/utils/color_cache_utils.c49
-rw-r--r--media/libwebp/src/utils/color_cache_utils.h89
-rw-r--r--media/libwebp/src/utils/endian_inl_utils.h93
-rw-r--r--media/libwebp/src/utils/filters_utils.c76
-rw-r--r--media/libwebp/src/utils/filters_utils.h32
-rw-r--r--media/libwebp/src/utils/huffman_encode_utils.c416
-rw-r--r--media/libwebp/src/utils/huffman_encode_utils.h60
-rw-r--r--media/libwebp/src/utils/huffman_utils.c296
-rw-r--r--media/libwebp/src/utils/huffman_utils.h111
-rw-r--r--media/libwebp/src/utils/moz.build32
-rw-r--r--media/libwebp/src/utils/quant_levels_dec_utils.c291
-rw-r--r--media/libwebp/src/utils/quant_levels_dec_utils.h35
-rw-r--r--media/libwebp/src/utils/quant_levels_utils.c140
-rw-r--r--media/libwebp/src/utils/quant_levels_utils.h36
-rw-r--r--media/libwebp/src/utils/random_utils.c43
-rw-r--r--media/libwebp/src/utils/random_utils.h63
-rw-r--r--media/libwebp/src/utils/rescaler_utils.c160
-rw-r--r--media/libwebp/src/utils/rescaler_utils.h102
-rw-r--r--media/libwebp/src/utils/thread_utils.c369
-rw-r--r--media/libwebp/src/utils/thread_utils.h90
-rw-r--r--media/libwebp/src/utils/utils.c338
-rw-r--r--media/libwebp/src/utils/utils.h210
27 files changed, 4320 insertions, 0 deletions
diff --git a/media/libwebp/src/utils/bit_reader_inl_utils.h b/media/libwebp/src/utils/bit_reader_inl_utils.h
new file mode 100644
index 0000000000..24f3af7b54
--- /dev/null
+++ b/media/libwebp/src/utils/bit_reader_inl_utils.h
@@ -0,0 +1,196 @@
+// Copyright 2014 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Specific inlined methods for boolean decoder [VP8GetBit() ...]
+// This file should be included by the .c sources that actually need to call
+// these methods.
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#ifndef WEBP_UTILS_BIT_READER_INL_UTILS_H_
+#define WEBP_UTILS_BIT_READER_INL_UTILS_H_
+
+#ifdef HAVE_CONFIG_H
+#include "src/webp/config.h"
+#endif
+
+#include <string.h> // for memcpy
+
+#include "src/dsp/dsp.h"
+#include "src/utils/bit_reader_utils.h"
+#include "src/utils/endian_inl_utils.h"
+#include "src/utils/utils.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+//------------------------------------------------------------------------------
+// Derived type lbit_t = natural type for memory I/O
+
+#if (BITS > 32)
+typedef uint64_t lbit_t;
+#elif (BITS > 16)
+typedef uint32_t lbit_t;
+#elif (BITS > 8)
+typedef uint16_t lbit_t;
+#else
+typedef uint8_t lbit_t;
+#endif
+
+extern const uint8_t kVP8Log2Range[128];
+extern const uint8_t kVP8NewRange[128];
+
+// special case for the tail byte-reading
+void VP8LoadFinalBytes(VP8BitReader* const br);
+
+//------------------------------------------------------------------------------
+// Inlined critical functions
+
+// makes sure br->value_ has at least BITS bits worth of data
+static WEBP_UBSAN_IGNORE_UNDEF WEBP_INLINE
+void VP8LoadNewBytes(VP8BitReader* WEBP_RESTRICT const br) {
+ assert(br != NULL && br->buf_ != NULL);
+ // Read 'BITS' bits at a time if possible.
+ if (br->buf_ < br->buf_max_) {
+ // convert memory type to register type (with some zero'ing!)
+ bit_t bits;
+#if defined(WEBP_USE_MIPS32)
+ // This is needed because of un-aligned read.
+ lbit_t in_bits;
+ lbit_t* p_buf_ = (lbit_t*)br->buf_;
+ __asm__ volatile(
+ ".set push \n\t"
+ ".set at \n\t"
+ ".set macro \n\t"
+ "ulw %[in_bits], 0(%[p_buf_]) \n\t"
+ ".set pop \n\t"
+ : [in_bits]"=r"(in_bits)
+ : [p_buf_]"r"(p_buf_)
+ : "memory", "at"
+ );
+#else
+ lbit_t in_bits;
+ memcpy(&in_bits, br->buf_, sizeof(in_bits));
+#endif
+ br->buf_ += BITS >> 3;
+#if !defined(WORDS_BIGENDIAN)
+#if (BITS > 32)
+ bits = BSwap64(in_bits);
+ bits >>= 64 - BITS;
+#elif (BITS >= 24)
+ bits = BSwap32(in_bits);
+ bits >>= (32 - BITS);
+#elif (BITS == 16)
+ bits = BSwap16(in_bits);
+#else // BITS == 8
+ bits = (bit_t)in_bits;
+#endif // BITS > 32
+#else // WORDS_BIGENDIAN
+ bits = (bit_t)in_bits;
+ if (BITS != 8 * sizeof(bit_t)) bits >>= (8 * sizeof(bit_t) - BITS);
+#endif
+ br->value_ = bits | (br->value_ << BITS);
+ br->bits_ += BITS;
+ } else {
+ VP8LoadFinalBytes(br); // no need to be inlined
+ }
+}
+
+// Read a bit with proba 'prob'. Speed-critical function!
+static WEBP_INLINE int VP8GetBit(VP8BitReader* WEBP_RESTRICT const br,
+ int prob, const char label[]) {
+ // Don't move this declaration! It makes a big speed difference to store
+ // 'range' *before* calling VP8LoadNewBytes(), even if this function doesn't
+ // alter br->range_ value.
+ range_t range = br->range_;
+ if (br->bits_ < 0) {
+ VP8LoadNewBytes(br);
+ }
+ {
+ const int pos = br->bits_;
+ const range_t split = (range * prob) >> 8;
+ const range_t value = (range_t)(br->value_ >> pos);
+ const int bit = (value > split);
+ if (bit) {
+ range -= split;
+ br->value_ -= (bit_t)(split + 1) << pos;
+ } else {
+ range = split + 1;
+ }
+ {
+ const int shift = 7 ^ BitsLog2Floor(range);
+ range <<= shift;
+ br->bits_ -= shift;
+ }
+ br->range_ = range - 1;
+ BT_TRACK(br);
+ return bit;
+ }
+}
+
+// simplified version of VP8GetBit() for prob=0x80 (note shift is always 1 here)
+static WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE
+int VP8GetSigned(VP8BitReader* WEBP_RESTRICT const br, int v,
+ const char label[]) {
+ if (br->bits_ < 0) {
+ VP8LoadNewBytes(br);
+ }
+ {
+ const int pos = br->bits_;
+ const range_t split = br->range_ >> 1;
+ const range_t value = (range_t)(br->value_ >> pos);
+ const int32_t mask = (int32_t)(split - value) >> 31; // -1 or 0
+ br->bits_ -= 1;
+ br->range_ += (range_t)mask;
+ br->range_ |= 1;
+ br->value_ -= (bit_t)((split + 1) & (uint32_t)mask) << pos;
+ BT_TRACK(br);
+ return (v ^ mask) - mask;
+ }
+}
+
+static WEBP_INLINE int VP8GetBitAlt(VP8BitReader* WEBP_RESTRICT const br,
+ int prob, const char label[]) {
+ // Don't move this declaration! It makes a big speed difference to store
+ // 'range' *before* calling VP8LoadNewBytes(), even if this function doesn't
+ // alter br->range_ value.
+ range_t range = br->range_;
+ if (br->bits_ < 0) {
+ VP8LoadNewBytes(br);
+ }
+ {
+ const int pos = br->bits_;
+ const range_t split = (range * prob) >> 8;
+ const range_t value = (range_t)(br->value_ >> pos);
+ int bit; // Don't use 'const int bit = (value > split);", it's slower.
+ if (value > split) {
+ range -= split + 1;
+ br->value_ -= (bit_t)(split + 1) << pos;
+ bit = 1;
+ } else {
+ range = split;
+ bit = 0;
+ }
+ if (range <= (range_t)0x7e) {
+ const int shift = kVP8Log2Range[range];
+ range = kVP8NewRange[range];
+ br->bits_ -= shift;
+ }
+ br->range_ = range;
+ BT_TRACK(br);
+ return bit;
+ }
+}
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_BIT_READER_INL_UTILS_H_
diff --git a/media/libwebp/src/utils/bit_reader_utils.c b/media/libwebp/src/utils/bit_reader_utils.c
new file mode 100644
index 0000000000..857cd60988
--- /dev/null
+++ b/media/libwebp/src/utils/bit_reader_utils.c
@@ -0,0 +1,298 @@
+// Copyright 2010 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Boolean decoder non-inlined methods
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#ifdef HAVE_CONFIG_H
+#include "src/webp/config.h"
+#endif
+
+#include "src/utils/bit_reader_inl_utils.h"
+#include "src/utils/utils.h"
+
+//------------------------------------------------------------------------------
+// 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, size_t size) {
+ assert(br != NULL);
+ assert(start != NULL);
+ assert(size < (1u << 31)); // limit ensured by format and upstream checks
+ br->range_ = 255 - 1;
+ br->value_ = 0;
+ br->bits_ = -8; // to load the very first 8bits
+ br->eof_ = 0;
+ VP8BitReaderSetBuffer(br, start, size);
+ VP8LoadNewBytes(br);
+}
+
+void VP8RemapBitReader(VP8BitReader* const br, ptrdiff_t offset) {
+ if (br->buf_ != NULL) {
+ br->buf_ += offset;
+ br->buf_end_ += offset;
+ br->buf_max_ += offset;
+ }
+}
+
+const uint8_t kVP8Log2Range[128] = {
+ 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
+ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 0
+};
+
+// range = ((range - 1) << kVP8Log2Range[range]) + 1
+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,
+ 199, 207, 215, 223, 231, 239, 247, 127,
+ 131, 135, 139, 143, 147, 151, 155, 159,
+ 163, 167, 171, 175, 179, 183, 187, 191,
+ 195, 199, 203, 207, 211, 215, 219, 223,
+ 227, 231, 235, 239, 243, 247, 251, 127,
+ 129, 131, 133, 135, 137, 139, 141, 143,
+ 145, 147, 149, 151, 153, 155, 157, 159,
+ 161, 163, 165, 167, 169, 171, 173, 175,
+ 177, 179, 181, 183, 185, 187, 189, 191,
+ 193, 195, 197, 199, 201, 203, 205, 207,
+ 209, 211, 213, 215, 217, 219, 221, 223,
+ 225, 227, 229, 231, 233, 235, 237, 239,
+ 241, 243, 245, 247, 249, 251, 253, 127
+};
+
+void VP8LoadFinalBytes(VP8BitReader* const br) {
+ assert(br != NULL && br->buf_ != NULL);
+ // Only read 8bits at a time
+ if (br->buf_ < br->buf_end_) {
+ br->bits_ += 8;
+ br->value_ = (bit_t)(*br->buf_++) | (br->value_ << 8);
+ } else if (!br->eof_) {
+ br->value_ <<= 8;
+ br->bits_ += 8;
+ br->eof_ = 1;
+ } else {
+ br->bits_ = 0; // This is to avoid undefined behaviour with shifts.
+ }
+}
+
+//------------------------------------------------------------------------------
+// Higher-level calls
+
+uint32_t VP8GetValue(VP8BitReader* const br, int bits, const char label[]) {
+ uint32_t v = 0;
+ while (bits-- > 0) {
+ v |= VP8GetBit(br, 0x80, label) << bits;
+ }
+ return v;
+}
+
+int32_t VP8GetSignedValue(VP8BitReader* const br, int bits,
+ const char label[]) {
+ const int value = VP8GetValue(br, bits, label);
+ return VP8Get(br, label) ? -value : value;
+}
+
+//------------------------------------------------------------------------------
+// VP8LBitReader
+
+#define VP8L_LOG8_WBITS 4 // Number of bytes needed to store VP8L_WBITS bits.
+
+#if defined(__arm__) || defined(_M_ARM) || defined(__aarch64__) || \
+ defined(__i386__) || defined(_M_IX86) || \
+ defined(__x86_64__) || defined(_M_X64)
+#define VP8L_USE_FAST_LOAD
+#endif
+
+static const uint32_t kBitMask[VP8L_MAX_NUM_BIT_READ + 1] = {
+ 0,
+ 0x000001, 0x000003, 0x000007, 0x00000f,
+ 0x00001f, 0x00003f, 0x00007f, 0x0000ff,
+ 0x0001ff, 0x0003ff, 0x0007ff, 0x000fff,
+ 0x001fff, 0x003fff, 0x007fff, 0x00ffff,
+ 0x01ffff, 0x03ffff, 0x07ffff, 0x0fffff,
+ 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff
+};
+
+void VP8LInitBitReader(VP8LBitReader* const br, const uint8_t* const start,
+ size_t length) {
+ size_t i;
+ vp8l_val_t value = 0;
+ assert(br != NULL);
+ assert(start != NULL);
+ assert(length < 0xfffffff8u); // can't happen with a RIFF chunk.
+
+ br->len_ = length;
+ br->val_ = 0;
+ br->bit_pos_ = 0;
+ br->eos_ = 0;
+
+ if (length > sizeof(br->val_)) {
+ length = sizeof(br->val_);
+ }
+ for (i = 0; i < length; ++i) {
+ value |= (vp8l_val_t)start[i] << (8 * i);
+ }
+ br->val_ = value;
+ br->pos_ = length;
+ br->buf_ = start;
+}
+
+void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
+ const uint8_t* const buf, size_t len) {
+ assert(br != NULL);
+ assert(buf != NULL);
+ assert(len < 0xfffffff8u); // can't happen with a RIFF chunk.
+ br->buf_ = buf;
+ br->len_ = len;
+ // pos_ > len_ should be considered a param error.
+ 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
+static void ShiftBytes(VP8LBitReader* const br) {
+ while (br->bit_pos_ >= 8 && br->pos_ < br->len_) {
+ br->val_ >>= 8;
+ br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (VP8L_LBITS - 8);
+ ++br->pos_;
+ br->bit_pos_ -= 8;
+ }
+ if (VP8LIsEndOfStream(br)) {
+ VP8LSetEndOfStream(br);
+ }
+}
+
+void VP8LDoFillBitWindow(VP8LBitReader* const br) {
+ assert(br->bit_pos_ >= VP8L_WBITS);
+#if defined(VP8L_USE_FAST_LOAD)
+ if (br->pos_ + sizeof(br->val_) < br->len_) {
+ br->val_ >>= VP8L_WBITS;
+ br->bit_pos_ -= VP8L_WBITS;
+ br->val_ |= (vp8l_val_t)HToLE32(WebPMemToUint32(br->buf_ + br->pos_)) <<
+ (VP8L_LBITS - VP8L_WBITS);
+ br->pos_ += VP8L_LOG8_WBITS;
+ return;
+ }
+#endif
+ ShiftBytes(br); // Slow path.
+}
+
+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 = VP8LPrefetchBits(br) & kBitMask[n_bits];
+ const int new_bits = br->bit_pos_ + n_bits;
+ br->bit_pos_ = new_bits;
+ ShiftBytes(br);
+ return val;
+ } else {
+ VP8LSetEndOfStream(br);
+ return 0;
+ }
+}
+
+//------------------------------------------------------------------------------
+// Bit-tracing tool
+
+#if (BITTRACE > 0)
+
+#include <stdlib.h> // for atexit()
+#include <stdio.h>
+#include <string.h>
+
+#define MAX_NUM_LABELS 32
+static struct {
+ const char* label;
+ int size;
+ int count;
+} kLabels[MAX_NUM_LABELS];
+
+static int last_label = 0;
+static int last_pos = 0;
+static const uint8_t* buf_start = NULL;
+static int init_done = 0;
+
+static void PrintBitTraces(void) {
+ int i;
+ int scale = 1;
+ int total = 0;
+ const char* units = "bits";
+#if (BITTRACE == 2)
+ scale = 8;
+ units = "bytes";
+#endif
+ for (i = 0; i < last_label; ++i) total += kLabels[i].size;
+ if (total < 1) total = 1; // avoid rounding errors
+ printf("=== Bit traces ===\n");
+ for (i = 0; i < last_label; ++i) {
+ const int skip = 16 - (int)strlen(kLabels[i].label);
+ const int value = (kLabels[i].size + scale - 1) / scale;
+ assert(skip > 0);
+ printf("%s \%*s: %6d %s \t[%5.2f%%] [count: %7d]\n",
+ kLabels[i].label, skip, "", value, units,
+ 100.f * kLabels[i].size / total,
+ kLabels[i].count);
+ }
+ total = (total + scale - 1) / scale;
+ printf("Total: %d %s\n", total, units);
+}
+
+void BitTrace(const struct VP8BitReader* const br, const char label[]) {
+ int i, pos;
+ if (!init_done) {
+ memset(kLabels, 0, sizeof(kLabels));
+ atexit(PrintBitTraces);
+ buf_start = br->buf_;
+ init_done = 1;
+ }
+ pos = (int)(br->buf_ - buf_start) * 8 - br->bits_;
+ // if there's a too large jump, we've changed partition -> reset counter
+ if (abs(pos - last_pos) > 32) {
+ buf_start = br->buf_;
+ pos = 0;
+ last_pos = 0;
+ }
+ if (br->range_ >= 0x7f) pos += kVP8Log2Range[br->range_ - 0x7f];
+ for (i = 0; i < last_label; ++i) {
+ if (!strcmp(label, kLabels[i].label)) break;
+ }
+ if (i == MAX_NUM_LABELS) abort(); // overflow!
+ kLabels[i].label = label;
+ kLabels[i].size += pos - last_pos;
+ kLabels[i].count += 1;
+ if (i == last_label) ++last_label;
+ last_pos = pos;
+}
+
+#endif // BITTRACE > 0
+
+//------------------------------------------------------------------------------
diff --git a/media/libwebp/src/utils/bit_reader_utils.h b/media/libwebp/src/utils/bit_reader_utils.h
new file mode 100644
index 0000000000..e64156e318
--- /dev/null
+++ b/media/libwebp/src/utils/bit_reader_utils.h
@@ -0,0 +1,194 @@
+// Copyright 2010 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Boolean decoder
+//
+// Author: Skal (pascal.massimino@gmail.com)
+// Vikas Arora (vikaas.arora@gmail.com)
+
+#ifndef WEBP_UTILS_BIT_READER_UTILS_H_
+#define WEBP_UTILS_BIT_READER_UTILS_H_
+
+#include <assert.h>
+#ifdef _MSC_VER
+#include <stdlib.h> // _byteswap_ulong
+#endif
+#include "src/webp/types.h"
+
+// Warning! This macro triggers quite some MACRO wizardry around func signature!
+#if !defined(BITTRACE)
+#define BITTRACE 0 // 0 = off, 1 = print bits, 2 = print bytes
+#endif
+
+#if (BITTRACE > 0)
+struct VP8BitReader;
+extern void BitTrace(const struct VP8BitReader* const br, const char label[]);
+#define BT_TRACK(br) BitTrace(br, label)
+#define VP8Get(BR, L) VP8GetValue(BR, 1, L)
+#else
+#define BT_TRACK(br)
+// We'll REMOVE the 'const char label[]' from all signatures and calls (!!):
+#define VP8GetValue(BR, N, L) VP8GetValue(BR, N)
+#define VP8Get(BR, L) VP8GetValue(BR, 1, L)
+#define VP8GetSignedValue(BR, N, L) VP8GetSignedValue(BR, N)
+#define VP8GetBit(BR, P, L) VP8GetBit(BR, P)
+#define VP8GetBitAlt(BR, P, L) VP8GetBitAlt(BR, P)
+#define VP8GetSigned(BR, V, L) VP8GetSigned(BR, V)
+#endif
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// The Boolean decoder needs to maintain infinite precision on the value_ field.
+// However, since range_ is only 8bit, we only need an active window of 8 bits
+// for value_. Left bits (MSB) gets zeroed and shifted away when value_ falls
+// below 128, range_ is updated, and fresh bits read from the bitstream are
+// brought in as LSB. To avoid reading the fresh bits one by one (slow), we
+// cache BITS of them ahead. The total of (BITS + 8) bits must fit into a
+// natural register (with type bit_t). To fetch BITS bits from bitstream we
+// use a type lbit_t.
+//
+// BITS can be any multiple of 8 from 8 to 56 (inclusive).
+// Pick values that fit natural register size.
+
+#if defined(__i386__) || defined(_M_IX86) // x86 32bit
+#define BITS 24
+#elif defined(__x86_64__) || defined(_M_X64) // x86 64bit
+#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
+#endif
+
+//------------------------------------------------------------------------------
+// Derived types and constants:
+// bit_t = natural register type for storing 'value_' (which is BITS+8 bits)
+// range_t = register for 'range_' (which is 8bits only)
+
+#if (BITS > 24)
+typedef uint64_t bit_t;
+#else
+typedef uint32_t bit_t;
+#endif
+
+typedef uint32_t range_t;
+
+//------------------------------------------------------------------------------
+// Bitreader
+
+typedef struct VP8BitReader VP8BitReader;
+struct VP8BitReader {
+ // boolean decoder (keep the field ordering as is!)
+ bit_t value_; // current value
+ range_t range_; // current range minus 1. In [127, 254] interval.
+ int bits_; // number of valid bits left
+ // 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, 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'.
+void VP8RemapBitReader(VP8BitReader* const br, ptrdiff_t offset);
+
+// return the next value made of 'num_bits' bits
+uint32_t VP8GetValue(VP8BitReader* const br, int num_bits, const char label[]);
+
+// return the next value with sign-extension.
+int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits,
+ const char label[]);
+
+// bit_reader_inl.h will implement the following methods:
+// static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob, ...)
+// static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v, ...)
+// and should be included by the .c files that actually need them.
+// This is to avoid recompiling the whole library whenever this file is touched,
+// and also allowing platform-specific ad-hoc hacks.
+
+// -----------------------------------------------------------------------------
+// Bitreader for lossless format
+
+// 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 (= 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.
+
+typedef struct {
+ vp8l_val_t val_; // pre-fetched bits
+ const uint8_t* buf_; // input byte buffer
+ size_t len_; // buffer length
+ size_t pos_; // byte position in buf_
+ int bit_pos_; // current bit-reading position in val_
+ int eos_; // true if a bit was read past the end of buffer
+} VP8LBitReader;
+
+void VP8LInitBitReader(VP8LBitReader* const br,
+ const uint8_t* const start,
+ size_t length);
+
+// Sets a new data buffer.
+void VP8LBitReaderSetBuffer(VP8LBitReader* const br,
+ const uint8_t* const buffer, size_t length);
+
+// Reads the specified number of bits from read buffer.
+// Flags an error in case end_of_stream or n_bits is more than the allowed limit
+// of VP8L_MAX_NUM_BIT_READ (inclusive).
+// Flags eos_ if this read attempt is going to cross the read buffer.
+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_ & (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->eos_ || ((br->pos_ == br->len_) && (br->bit_pos_ > VP8L_LBITS));
+}
+
+// For jumping over a number of bits in the bit stream when accessed with
+// VP8LPrefetchBits and VP8LFillBitWindow.
+// This function does *not* set br->eos_, since it's speed-critical.
+// Use with extreme care!
+static WEBP_INLINE void VP8LSetBitPos(VP8LBitReader* const br, int val) {
+ br->bit_pos_ = val;
+}
+
+// Advances the read buffer by 4 bytes to make room for reading next 32 bits.
+// Speed critical, but infrequent part of the code can be non-inlined.
+extern void VP8LDoFillBitWindow(VP8LBitReader* const br);
+static WEBP_INLINE void VP8LFillBitWindow(VP8LBitReader* const br) {
+ if (br->bit_pos_ >= VP8L_WBITS) VP8LDoFillBitWindow(br);
+}
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_BIT_READER_UTILS_H_
diff --git a/media/libwebp/src/utils/bit_writer_utils.c b/media/libwebp/src/utils/bit_writer_utils.c
new file mode 100644
index 0000000000..2f408508f1
--- /dev/null
+++ b/media/libwebp/src/utils/bit_writer_utils.c
@@ -0,0 +1,347 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Bit writing and boolean coder
+//
+// Author: Skal (pascal.massimino@gmail.com)
+// Vikas Arora (vikaas.arora@gmail.com)
+
+#include <assert.h>
+#include <string.h> // for memcpy()
+#include <stdlib.h>
+
+#include "src/utils/bit_writer_utils.h"
+#include "src/utils/endian_inl_utils.h"
+#include "src/utils/utils.h"
+
+//------------------------------------------------------------------------------
+// VP8BitWriter
+
+static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) {
+ uint8_t* new_buf;
+ size_t new_size;
+ const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size;
+ const size_t needed_size = (size_t)needed_size_64b;
+ if (needed_size_64b != needed_size) {
+ bw->error_ = 1;
+ return 0;
+ }
+ if (needed_size <= bw->max_pos_) return 1;
+ // If the following line wraps over 32bit, the test just after will catch it.
+ new_size = 2 * bw->max_pos_;
+ if (new_size < needed_size) new_size = needed_size;
+ if (new_size < 1024) new_size = 1024;
+ new_buf = (uint8_t*)WebPSafeMalloc(1ULL, new_size);
+ if (new_buf == NULL) {
+ bw->error_ = 1;
+ return 0;
+ }
+ if (bw->pos_ > 0) {
+ assert(bw->buf_ != NULL);
+ memcpy(new_buf, bw->buf_, bw->pos_);
+ }
+ WebPSafeFree(bw->buf_);
+ bw->buf_ = new_buf;
+ bw->max_pos_ = new_size;
+ return 1;
+}
+
+static void Flush(VP8BitWriter* const bw) {
+ const int s = 8 + bw->nb_bits_;
+ const int32_t bits = bw->value_ >> s;
+ assert(bw->nb_bits_ >= 0);
+ bw->value_ -= bits << s;
+ bw->nb_bits_ -= 8;
+ if ((bits & 0xff) != 0xff) {
+ size_t pos = bw->pos_;
+ if (!BitWriterResize(bw, bw->run_ + 1)) {
+ return;
+ }
+ if (bits & 0x100) { // overflow -> propagate carry over pending 0xff's
+ if (pos > 0) bw->buf_[pos - 1]++;
+ }
+ if (bw->run_ > 0) {
+ const int value = (bits & 0x100) ? 0x00 : 0xff;
+ for (; bw->run_ > 0; --bw->run_) bw->buf_[pos++] = value;
+ }
+ bw->buf_[pos++] = bits & 0xff;
+ bw->pos_ = pos;
+ } else {
+ bw->run_++; // delay writing of bytes 0xff, pending eventual carry.
+ }
+}
+
+//------------------------------------------------------------------------------
+// renormalization
+
+static const uint8_t kNorm[128] = { // renorm_sizes[i] = 8 - log2(i)
+ 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
+ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+ 0
+};
+
+// range = ((range + 1) << kVP8Log2Range[range]) - 1
+static const uint8_t kNewRange[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, 199, 207, 215, 223, 231, 239,
+ 247, 127, 131, 135, 139, 143, 147, 151, 155, 159, 163, 167, 171, 175, 179,
+ 183, 187, 191, 195, 199, 203, 207, 211, 215, 219, 223, 227, 231, 235, 239,
+ 243, 247, 251, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 149,
+ 151, 153, 155, 157, 159, 161, 163, 165, 167, 169, 171, 173, 175, 177, 179,
+ 181, 183, 185, 187, 189, 191, 193, 195, 197, 199, 201, 203, 205, 207, 209,
+ 211, 213, 215, 217, 219, 221, 223, 225, 227, 229, 231, 233, 235, 237, 239,
+ 241, 243, 245, 247, 249, 251, 253, 127
+};
+
+int VP8PutBit(VP8BitWriter* const bw, int bit, int prob) {
+ const int split = (bw->range_ * prob) >> 8;
+ if (bit) {
+ bw->value_ += split + 1;
+ bw->range_ -= split + 1;
+ } else {
+ bw->range_ = split;
+ }
+ if (bw->range_ < 127) { // emit 'shift' bits out and renormalize
+ const int shift = kNorm[bw->range_];
+ bw->range_ = kNewRange[bw->range_];
+ bw->value_ <<= shift;
+ bw->nb_bits_ += shift;
+ if (bw->nb_bits_ > 0) Flush(bw);
+ }
+ return bit;
+}
+
+int VP8PutBitUniform(VP8BitWriter* const bw, int bit) {
+ const int split = bw->range_ >> 1;
+ if (bit) {
+ bw->value_ += split + 1;
+ bw->range_ -= split + 1;
+ } else {
+ bw->range_ = split;
+ }
+ if (bw->range_ < 127) {
+ bw->range_ = kNewRange[bw->range_];
+ bw->value_ <<= 1;
+ bw->nb_bits_ += 1;
+ if (bw->nb_bits_ > 0) Flush(bw);
+ }
+ return bit;
+}
+
+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 VP8PutSignedBits(VP8BitWriter* const bw, int value, int nb_bits) {
+ if (!VP8PutBitUniform(bw, value != 0)) return;
+ if (value < 0) {
+ VP8PutBits(bw, ((-value) << 1) | 1, nb_bits + 1);
+ } else {
+ VP8PutBits(bw, value << 1, nb_bits + 1);
+ }
+}
+
+//------------------------------------------------------------------------------
+
+int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size) {
+ bw->range_ = 255 - 1;
+ bw->value_ = 0;
+ bw->run_ = 0;
+ bw->nb_bits_ = -8;
+ bw->pos_ = 0;
+ bw->max_pos_ = 0;
+ bw->error_ = 0;
+ bw->buf_ = NULL;
+ return (expected_size > 0) ? BitWriterResize(bw, expected_size) : 1;
+}
+
+uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw) {
+ VP8PutBits(bw, 0, 9 - bw->nb_bits_);
+ bw->nb_bits_ = 0; // pad with zeroes
+ Flush(bw);
+ return bw->buf_;
+}
+
+int VP8BitWriterAppend(VP8BitWriter* const bw,
+ const uint8_t* data, size_t size) {
+ assert(data != NULL);
+ if (bw->nb_bits_ != -8) return 0; // Flush() must have been called
+ if (!BitWriterResize(bw, size)) return 0;
+ memcpy(bw->buf_ + bw->pos_, data, size);
+ bw->pos_ += size;
+ return 1;
+}
+
+void VP8BitWriterWipeOut(VP8BitWriter* const bw) {
+ if (bw != NULL) {
+ WebPSafeFree(bw->buf_);
+ memset(bw, 0, sizeof(*bw));
+ }
+}
+
+//------------------------------------------------------------------------------
+// VP8LBitWriter
+
+// This is the minimum amount of size the memory buffer is guaranteed to grow
+// when extra space is needed.
+#define MIN_EXTRA_SIZE (32768ULL)
+
+// Returns 1 on success.
+static int VP8LBitWriterResize(VP8LBitWriter* const bw, size_t extra_size) {
+ uint8_t* allocated_buf;
+ size_t allocated_size;
+ const size_t max_bytes = bw->end_ - bw->buf_;
+ const size_t current_size = bw->cur_ - bw->buf_;
+ const uint64_t size_required_64b = (uint64_t)current_size + extra_size;
+ const size_t size_required = (size_t)size_required_64b;
+ if (size_required != size_required_64b) {
+ bw->error_ = 1;
+ return 0;
+ }
+ if (max_bytes > 0 && size_required <= max_bytes) return 1;
+ allocated_size = (3 * max_bytes) >> 1;
+ if (allocated_size < size_required) allocated_size = size_required;
+ // make allocated size multiple of 1k
+ allocated_size = (((allocated_size >> 10) + 1) << 10);
+ allocated_buf = (uint8_t*)WebPSafeMalloc(1ULL, allocated_size);
+ if (allocated_buf == NULL) {
+ bw->error_ = 1;
+ return 0;
+ }
+ if (current_size > 0) {
+ memcpy(allocated_buf, bw->buf_, current_size);
+ }
+ WebPSafeFree(bw->buf_);
+ bw->buf_ = allocated_buf;
+ bw->cur_ = bw->buf_ + current_size;
+ bw->end_ = bw->buf_ + allocated_size;
+ return 1;
+}
+
+int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) {
+ memset(bw, 0, sizeof(*bw));
+ return VP8LBitWriterResize(bw, expected_size);
+}
+
+int VP8LBitWriterClone(const VP8LBitWriter* const src,
+ VP8LBitWriter* const dst) {
+ const size_t current_size = src->cur_ - src->buf_;
+ assert(src->cur_ >= src->buf_ && src->cur_ <= src->end_);
+ if (!VP8LBitWriterResize(dst, current_size)) return 0;
+ memcpy(dst->buf_, src->buf_, current_size);
+ dst->bits_ = src->bits_;
+ dst->used_ = src->used_;
+ dst->error_ = src->error_;
+ dst->cur_ = dst->buf_ + current_size;
+ return 1;
+}
+
+void VP8LBitWriterWipeOut(VP8LBitWriter* const bw) {
+ if (bw != NULL) {
+ WebPSafeFree(bw->buf_);
+ memset(bw, 0, sizeof(*bw));
+ }
+}
+
+void VP8LBitWriterReset(const VP8LBitWriter* const bw_init,
+ VP8LBitWriter* const bw) {
+ bw->bits_ = bw_init->bits_;
+ bw->used_ = bw_init->used_;
+ bw->cur_ = bw->buf_ + (bw_init->cur_ - bw_init->buf_);
+ assert(bw->cur_ <= bw->end_);
+ bw->error_ = bw_init->error_;
+}
+
+void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst) {
+ const VP8LBitWriter tmp = *src;
+ *src = *dst;
+ *dst = tmp;
+}
+
+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 (!CheckSizeOverflow(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(sizeof(vp8l_wtype_t) == 2);
+ if (n_bits > 0) {
+ 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);
+ }
+#endif
+ // If needed, make some room by flushing some bits out.
+ while (used >= VP8L_WRITER_BITS) {
+ if (bw->cur_ + VP8L_WRITER_BYTES > bw->end_) {
+ const uint64_t extra_size = (bw->end_ - bw->buf_) + MIN_EXTRA_SIZE;
+ if (!CheckSizeOverflow(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)lbits);
+ bw->cur_ += VP8L_WRITER_BYTES;
+ lbits >>= VP8L_WRITER_BITS;
+ used -= VP8L_WRITER_BITS;
+ }
+ bw->bits_ = lbits | ((vp8l_atype_t)bits << used);
+ bw->used_ = used + n_bits;
+ }
+}
+
+uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) {
+ // flush leftover bits
+ if (VP8LBitWriterResize(bw, (bw->used_ + 7) >> 3)) {
+ while (bw->used_ > 0) {
+ *bw->cur_++ = (uint8_t)bw->bits_;
+ bw->bits_ >>= 8;
+ bw->used_ -= 8;
+ }
+ bw->used_ = 0;
+ }
+ return bw->buf_;
+}
+
+//------------------------------------------------------------------------------
diff --git a/media/libwebp/src/utils/bit_writer_utils.h b/media/libwebp/src/utils/bit_writer_utils.h
new file mode 100644
index 0000000000..b9d5102a5a
--- /dev/null
+++ b/media/libwebp/src/utils/bit_writer_utils.h
@@ -0,0 +1,154 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Bit writing and boolean coder
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#ifndef WEBP_UTILS_BIT_WRITER_UTILS_H_
+#define WEBP_UTILS_BIT_WRITER_UTILS_H_
+
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+//------------------------------------------------------------------------------
+// Bit-writing
+
+typedef struct VP8BitWriter VP8BitWriter;
+struct VP8BitWriter {
+ int32_t range_; // range-1
+ int32_t value_;
+ int run_; // number of outstanding bits
+ int nb_bits_; // number of pending bits
+ uint8_t* buf_; // internal buffer. Re-allocated regularly. Not owned.
+ size_t pos_;
+ size_t max_pos_;
+ int error_; // true in case of error
+};
+
+// Initialize the object. Allocates some initial memory based on expected_size.
+int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size);
+// Finalize the bitstream coding. Returns a pointer to the internal buffer.
+uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw);
+// Release any pending memory and zeroes the object. Not a mandatory call.
+// Only useful in case of error, when the internal buffer hasn't been grabbed!
+void VP8BitWriterWipeOut(VP8BitWriter* const bw);
+
+int VP8PutBit(VP8BitWriter* const bw, int bit, int prob);
+int VP8PutBitUniform(VP8BitWriter* const bw, int bit);
+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,
+ const uint8_t* data, size_t size);
+
+// return approximate write position (in bits)
+static WEBP_INLINE uint64_t VP8BitWriterPos(const VP8BitWriter* const bw) {
+ const uint64_t nb_bits = 8 + bw->nb_bits_; // bw->nb_bits_ is <= 0, note
+ return (bw->pos_ + bw->run_) * 8 + nb_bits;
+}
+
+// Returns a pointer to the internal buffer.
+static WEBP_INLINE uint8_t* VP8BitWriterBuf(const VP8BitWriter* const bw) {
+ return bw->buf_;
+}
+// Returns the size of the internal buffer.
+static WEBP_INLINE size_t VP8BitWriterSize(const VP8BitWriter* const bw) {
+ return bw->pos_;
+}
+
+//------------------------------------------------------------------------------
+// VP8LBitWriter
+
+#if defined(__x86_64__) || defined(_M_X64) // 64bit
+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 {
+ vp8l_atype_t bits_; // bit accumulator
+ int used_; // number of bits used in accumulator
+ uint8_t* buf_; // start of buffer
+ uint8_t* cur_; // current write position
+ uint8_t* end_; // end of buffer
+
+ // After all bits are written (VP8LBitWriterFinish()), the caller must observe
+ // the state of error_. A value of 1 indicates that a memory allocation
+ // failure has happened during bit writing. A value of 0 indicates successful
+ // writing of bits.
+ int error_;
+} VP8LBitWriter;
+
+static WEBP_INLINE size_t VP8LBitWriterNumBytes(const 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);
+// Returns false in case of memory allocation error.
+int VP8LBitWriterClone(const VP8LBitWriter* const src,
+ VP8LBitWriter* const dst);
+// 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);
+// Resets the cursor of the BitWriter bw to when it was like in bw_init.
+void VP8LBitWriterReset(const VP8LBitWriter* const bw_init,
+ VP8LBitWriter* const bw);
+// Swaps the memory held by two BitWriters.
+void VP8LBitWriterSwap(VP8LBitWriter* const src, VP8LBitWriter* const dst);
+
+// Internal function for VP8LPutBits flushing 32 bits from the written state.
+void VP8LPutBitsFlushBits(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.
+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);
+ }
+}
+
+//------------------------------------------------------------------------------
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_BIT_WRITER_UTILS_H_
diff --git a/media/libwebp/src/utils/color_cache_utils.c b/media/libwebp/src/utils/color_cache_utils.c
new file mode 100644
index 0000000000..7b5222b6e5
--- /dev/null
+++ b/media/libwebp/src/utils/color_cache_utils.c
@@ -0,0 +1,49 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Color Cache for WebP Lossless
+//
+// Author: Jyrki Alakuijala (jyrki@google.com)
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include "src/utils/color_cache_utils.h"
+#include "src/utils/utils.h"
+
+//------------------------------------------------------------------------------
+// VP8LColorCache.
+
+int VP8LColorCacheInit(VP8LColorCache* const color_cache, int hash_bits) {
+ const int hash_size = 1 << hash_bits;
+ assert(color_cache != NULL);
+ assert(hash_bits > 0);
+ color_cache->colors_ = (uint32_t*)WebPSafeCalloc(
+ (uint64_t)hash_size, sizeof(*color_cache->colors_));
+ if (color_cache->colors_ == NULL) return 0;
+ color_cache->hash_shift_ = 32 - hash_bits;
+ color_cache->hash_bits_ = hash_bits;
+ return 1;
+}
+
+void VP8LColorCacheClear(VP8LColorCache* const color_cache) {
+ if (color_cache != NULL) {
+ WebPSafeFree(color_cache->colors_);
+ color_cache->colors_ = NULL;
+ }
+}
+
+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/media/libwebp/src/utils/color_cache_utils.h b/media/libwebp/src/utils/color_cache_utils.h
new file mode 100644
index 0000000000..b45d47c2d5
--- /dev/null
+++ b/media/libwebp/src/utils/color_cache_utils.h
@@ -0,0 +1,89 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Color Cache for WebP Lossless
+//
+// Authors: Jyrki Alakuijala (jyrki@google.com)
+// Urvang Joshi (urvang@google.com)
+
+#ifndef WEBP_UTILS_COLOR_CACHE_UTILS_H_
+#define WEBP_UTILS_COLOR_CACHE_UTILS_H_
+
+#include <assert.h>
+
+#include "src/dsp/dsp.h"
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// Main color cache struct.
+typedef struct {
+ uint32_t* colors_; // color entries
+ int hash_shift_; // Hash shift: 32 - hash_bits_.
+ int hash_bits_;
+} VP8LColorCache;
+
+static const uint32_t kHashMul = 0x1e35a7bdu;
+
+static WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE
+int VP8LHashPix(uint32_t argb, int shift) {
+ return (int)((argb * kHashMul) >> shift);
+}
+
+static WEBP_INLINE uint32_t VP8LColorCacheLookup(
+ const VP8LColorCache* const cc, uint32_t key) {
+ 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 int key = VP8LHashPix(argb, cc->hash_shift_);
+ cc->colors_[key] = argb;
+}
+
+static WEBP_INLINE int VP8LColorCacheGetIndex(const VP8LColorCache* const cc,
+ uint32_t argb) {
+ return VP8LHashPix(argb, cc->hash_shift_);
+}
+
+// Return the key if cc contains argb, and -1 otherwise.
+static WEBP_INLINE int VP8LColorCacheContains(const VP8LColorCache* const cc,
+ uint32_t argb) {
+ const int key = VP8LHashPix(argb, cc->hash_shift_);
+ return (cc->colors_[key] == argb) ? key : -1;
+}
+
+//------------------------------------------------------------------------------
+
+// Initializes the color cache with 'hash_bits' bits for the keys.
+// 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);
+
+//------------------------------------------------------------------------------
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif // WEBP_UTILS_COLOR_CACHE_UTILS_H_
diff --git a/media/libwebp/src/utils/endian_inl_utils.h b/media/libwebp/src/utils/endian_inl_utils.h
new file mode 100644
index 0000000000..3630a293bf
--- /dev/null
+++ b/media/libwebp/src/utils/endian_inl_utils.h
@@ -0,0 +1,93 @@
+// Copyright 2014 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Endian related functions.
+
+#ifndef WEBP_UTILS_ENDIAN_INL_UTILS_H_
+#define WEBP_UTILS_ENDIAN_INL_UTILS_H_
+
+#ifdef HAVE_CONFIG_H
+#include "src/webp/config.h"
+#endif
+
+#include "src/dsp/dsp.h"
+#include "src/webp/types.h"
+
+#if defined(WORDS_BIGENDIAN)
+#define HToLE32 BSwap32
+#define HToLE16 BSwap16
+#else
+#define HToLE32(x) (x)
+#define HToLE16(x) (x)
+#endif
+
+#if !defined(HAVE_CONFIG_H)
+#if LOCAL_GCC_PREREQ(4,8) || __has_builtin(__builtin_bswap16)
+#define HAVE_BUILTIN_BSWAP16
+#endif
+#if LOCAL_GCC_PREREQ(4,3) || __has_builtin(__builtin_bswap32)
+#define HAVE_BUILTIN_BSWAP32
+#endif
+#if LOCAL_GCC_PREREQ(4,3) || __has_builtin(__builtin_bswap64)
+#define HAVE_BUILTIN_BSWAP64
+#endif
+#endif // !HAVE_CONFIG_H
+
+static WEBP_INLINE uint16_t BSwap16(uint16_t x) {
+#if defined(HAVE_BUILTIN_BSWAP16)
+ return __builtin_bswap16(x);
+#elif defined(_MSC_VER)
+ return _byteswap_ushort(x);
+#else
+ // gcc will recognize a 'rorw $8, ...' here:
+ return (x >> 8) | ((x & 0xff) << 8);
+#endif // HAVE_BUILTIN_BSWAP16
+}
+
+static WEBP_INLINE uint32_t BSwap32(uint32_t x) {
+#if defined(WEBP_USE_MIPS32_R2)
+ uint32_t ret;
+ __asm__ volatile (
+ "wsbh %[ret], %[x] \n\t"
+ "rotr %[ret], %[ret], 16 \n\t"
+ : [ret]"=r"(ret)
+ : [x]"r"(x)
+ );
+ return ret;
+#elif defined(HAVE_BUILTIN_BSWAP32)
+ return __builtin_bswap32(x);
+#elif defined(__i386__) || defined(__x86_64__)
+ uint32_t swapped_bytes;
+ __asm__ volatile("bswap %0" : "=r"(swapped_bytes) : "0"(x));
+ return swapped_bytes;
+#elif defined(_MSC_VER)
+ return (uint32_t)_byteswap_ulong(x);
+#else
+ return (x >> 24) | ((x >> 8) & 0xff00) | ((x << 8) & 0xff0000) | (x << 24);
+#endif // HAVE_BUILTIN_BSWAP32
+}
+
+static WEBP_INLINE uint64_t BSwap64(uint64_t x) {
+#if defined(HAVE_BUILTIN_BSWAP64)
+ return __builtin_bswap64(x);
+#elif defined(__x86_64__)
+ uint64_t swapped_bytes;
+ __asm__ volatile("bswapq %0" : "=r"(swapped_bytes) : "0"(x));
+ return swapped_bytes;
+#elif defined(_MSC_VER)
+ return (uint64_t)_byteswap_uint64(x);
+#else // generic code for swapping 64-bit values (suggested by bdb@)
+ x = ((x & 0xffffffff00000000ull) >> 32) | ((x & 0x00000000ffffffffull) << 32);
+ x = ((x & 0xffff0000ffff0000ull) >> 16) | ((x & 0x0000ffff0000ffffull) << 16);
+ x = ((x & 0xff00ff00ff00ff00ull) >> 8) | ((x & 0x00ff00ff00ff00ffull) << 8);
+ return x;
+#endif // HAVE_BUILTIN_BSWAP64
+}
+
+#endif // WEBP_UTILS_ENDIAN_INL_UTILS_H_
diff --git a/media/libwebp/src/utils/filters_utils.c b/media/libwebp/src/utils/filters_utils.c
new file mode 100644
index 0000000000..bbc2c34d93
--- /dev/null
+++ b/media/libwebp/src/utils/filters_utils.c
@@ -0,0 +1,76 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// filter estimation
+//
+// Author: Urvang (urvang@google.com)
+
+#include "src/utils/filters_utils.h"
+#include <stdlib.h>
+#include <string.h>
+
+// -----------------------------------------------------------------------------
+// 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)
+
+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
+}
+
+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));
+
+ // We only sample every other pixels. That's enough.
+ for (j = 2; j < height - 1; j += 2) {
+ const uint8_t* const p = data + j * stride;
+ int mean = p[0];
+ for (i = 2; i < width - 1; i += 2) {
+ const int diff0 = SDIFF(p[i], mean);
+ const int diff1 = SDIFF(p[i], p[i - 1]);
+ const int diff2 = SDIFF(p[i], p[i - width]);
+ const int grad_pred =
+ GradientPredictor(p[i - 1], p[i - width], p[i - width - 1]);
+ const int diff3 = SDIFF(p[i], grad_pred);
+ bins[WEBP_FILTER_NONE][diff0] = 1;
+ bins[WEBP_FILTER_HORIZONTAL][diff1] = 1;
+ bins[WEBP_FILTER_VERTICAL][diff2] = 1;
+ bins[WEBP_FILTER_GRADIENT][diff3] = 1;
+ mean = (3 * mean + p[i] + 2) >> 2;
+ }
+ }
+ {
+ int filter;
+ WEBP_FILTER_TYPE best_filter = WEBP_FILTER_NONE;
+ int best_score = 0x7fffffff;
+ for (filter = WEBP_FILTER_NONE; filter < WEBP_FILTER_LAST; ++filter) {
+ int score = 0;
+ for (i = 0; i < SMAX; ++i) {
+ if (bins[filter][i] > 0) {
+ score += i;
+ }
+ }
+ if (score < best_score) {
+ best_score = score;
+ best_filter = (WEBP_FILTER_TYPE)filter;
+ }
+ }
+ return best_filter;
+ }
+}
+
+#undef SMAX
+#undef SDIFF
+
+//------------------------------------------------------------------------------
diff --git a/media/libwebp/src/utils/filters_utils.h b/media/libwebp/src/utils/filters_utils.h
new file mode 100644
index 0000000000..61da66e212
--- /dev/null
+++ b/media/libwebp/src/utils/filters_utils.h
@@ -0,0 +1,32 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Spatial prediction using various filters
+//
+// Author: Urvang (urvang@google.com)
+
+#ifndef WEBP_UTILS_FILTERS_UTILS_H_
+#define WEBP_UTILS_FILTERS_UTILS_H_
+
+#include "src/webp/types.h"
+#include "src/dsp/dsp.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// Fast estimate of a potentially good filter.
+WEBP_FILTER_TYPE WebPEstimateBestFilter(const uint8_t* data,
+ int width, int height, int stride);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_FILTERS_UTILS_H_
diff --git a/media/libwebp/src/utils/huffman_encode_utils.c b/media/libwebp/src/utils/huffman_encode_utils.c
new file mode 100644
index 0000000000..585db91951
--- /dev/null
+++ b/media/libwebp/src/utils/huffman_encode_utils.c
@@ -0,0 +1,416 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Author: Jyrki Alakuijala (jyrki@google.com)
+//
+// Entropy encoding (Huffman) for webp lossless.
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include "src/utils/huffman_encode_utils.h"
+#include "src/utils/utils.h"
+#include "src/webp/format_constants.h"
+
+// -----------------------------------------------------------------------------
+// Util function to optimize the symbol map for RLE coding
+
+// Heuristics for selecting the stride ranges to collapse.
+static int ValuesShouldBeCollapsedToStrideAverage(int a, int b) {
+ return abs(a - b) < 4;
+}
+
+// Change the population counts in a way that the consequent
+// Huffman tree compression, especially its RLE-part, give smaller output.
+static void OptimizeHuffmanForRle(int length, uint8_t* const good_for_rle,
+ uint32_t* const counts) {
+ // 1) Let's make the Huffman code more compatible with rle encoding.
+ int i;
+ for (; length >= 0; --length) {
+ if (length == 0) {
+ return; // All zeros.
+ }
+ if (counts[length - 1] != 0) {
+ // Now counts[0..length - 1] does not have trailing zeros.
+ break;
+ }
+ }
+ // 2) Let's mark all population counts that already can be encoded
+ // with an rle code.
+ {
+ // Let's not spoil any of the existing good rle codes.
+ // Mark any seq of 0's that is longer as 5 as a good_for_rle.
+ // Mark any seq of non-0's that is longer as 7 as a good_for_rle.
+ uint32_t symbol = counts[0];
+ int stride = 0;
+ for (i = 0; i < length + 1; ++i) {
+ if (i == length || counts[i] != symbol) {
+ if ((symbol == 0 && stride >= 5) ||
+ (symbol != 0 && stride >= 7)) {
+ int k;
+ for (k = 0; k < stride; ++k) {
+ good_for_rle[i - k - 1] = 1;
+ }
+ }
+ stride = 1;
+ if (i != length) {
+ symbol = counts[i];
+ }
+ } else {
+ ++stride;
+ }
+ }
+ }
+ // 3) Let's replace those population counts that lead to more rle codes.
+ {
+ uint32_t stride = 0;
+ uint32_t limit = counts[0];
+ uint32_t sum = 0;
+ for (i = 0; i < length + 1; ++i) {
+ if (i == length || good_for_rle[i] ||
+ (i != 0 && good_for_rle[i - 1]) ||
+ !ValuesShouldBeCollapsedToStrideAverage(counts[i], limit)) {
+ if (stride >= 4 || (stride >= 3 && sum == 0)) {
+ uint32_t k;
+ // The stride must end, collapse what we have, if we have enough (4).
+ uint32_t count = (sum + stride / 2) / stride;
+ if (count < 1) {
+ count = 1;
+ }
+ if (sum == 0) {
+ // Don't make an all zeros stride to be upgraded to ones.
+ count = 0;
+ }
+ for (k = 0; k < stride; ++k) {
+ // We don't want to change value at counts[i],
+ // that is already belonging to the next stride. Thus - 1.
+ counts[i - k - 1] = count;
+ }
+ }
+ stride = 0;
+ sum = 0;
+ if (i < length - 3) {
+ // All interesting strides have a count of at least 4,
+ // at least when non-zeros.
+ limit = (counts[i] + counts[i + 1] +
+ counts[i + 2] + counts[i + 3] + 2) / 4;
+ } else if (i < length) {
+ limit = counts[i];
+ } else {
+ limit = 0;
+ }
+ }
+ ++stride;
+ if (i != length) {
+ sum += counts[i];
+ if (stride >= 4) {
+ limit = (sum + stride / 2) / stride;
+ }
+ }
+ }
+ }
+}
+
+// A comparer function for two Huffman trees: sorts first by 'total count'
+// (more comes first), and then by 'value' (more comes first).
+static int CompareHuffmanTrees(const void* ptr1, const void* ptr2) {
+ const HuffmanTree* const t1 = (const HuffmanTree*)ptr1;
+ const HuffmanTree* const t2 = (const HuffmanTree*)ptr2;
+ if (t1->total_count_ > t2->total_count_) {
+ return -1;
+ } else if (t1->total_count_ < t2->total_count_) {
+ return 1;
+ } else {
+ assert(t1->value_ != t2->value_);
+ return (t1->value_ < t2->value_) ? -1 : 1;
+ }
+}
+
+static void SetBitDepths(const HuffmanTree* const tree,
+ const HuffmanTree* const pool,
+ uint8_t* const bit_depths, int level) {
+ if (tree->pool_index_left_ >= 0) {
+ SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1);
+ SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1);
+ } else {
+ bit_depths[tree->value_] = level;
+ }
+}
+
+// Create an optimal Huffman tree.
+//
+// (data,length): population counts.
+// tree_limit: maximum bit depth (inclusive) of the codes.
+// bit_depths[]: how many bits are used for the symbol.
+//
+// Returns 0 when an error has occurred.
+//
+// The catch here is that the tree cannot be arbitrarily deep
+//
+// count_limit is the value that is to be faked as the minimum value
+// and this minimum value is raised until the tree matches the
+// maximum length requirement.
+//
+// This algorithm is not of excellent performance for very long data blocks,
+// especially when population counts are longer than 2**tree_limit, but
+// we are not planning to use this with extremely long blocks.
+//
+// See https://en.wikipedia.org/wiki/Huffman_coding
+static void GenerateOptimalTree(const uint32_t* const histogram,
+ int histogram_size,
+ HuffmanTree* tree, int tree_depth_limit,
+ uint8_t* const bit_depths) {
+ uint32_t count_min;
+ HuffmanTree* tree_pool;
+ int tree_size_orig = 0;
+ int i;
+
+ for (i = 0; i < histogram_size; ++i) {
+ if (histogram[i] != 0) {
+ ++tree_size_orig;
+ }
+ }
+
+ if (tree_size_orig == 0) { // pretty optimal already!
+ return;
+ }
+
+ tree_pool = tree + tree_size_orig;
+
+ // For block sizes with less than 64k symbols we never need to do a
+ // second iteration of this loop.
+ // If we actually start running inside this loop a lot, we would perhaps
+ // be better off with the Katajainen algorithm.
+ assert(tree_size_orig <= (1 << (tree_depth_limit - 1)));
+ for (count_min = 1; ; count_min *= 2) {
+ int tree_size = tree_size_orig;
+ // We need to pack the Huffman tree in tree_depth_limit bits.
+ // So, we try by faking histogram entries to be at least 'count_min'.
+ int idx = 0;
+ int j;
+ for (j = 0; j < histogram_size; ++j) {
+ if (histogram[j] != 0) {
+ const uint32_t count =
+ (histogram[j] < count_min) ? count_min : histogram[j];
+ tree[idx].total_count_ = count;
+ tree[idx].value_ = j;
+ tree[idx].pool_index_left_ = -1;
+ tree[idx].pool_index_right_ = -1;
+ ++idx;
+ }
+ }
+
+ // Build the Huffman tree.
+ qsort(tree, tree_size, sizeof(*tree), CompareHuffmanTrees);
+
+ if (tree_size > 1) { // Normal case.
+ int tree_pool_size = 0;
+ while (tree_size > 1) { // Finish when we have only one root.
+ uint32_t count;
+ tree_pool[tree_pool_size++] = tree[tree_size - 1];
+ tree_pool[tree_pool_size++] = tree[tree_size - 2];
+ count = tree_pool[tree_pool_size - 1].total_count_ +
+ tree_pool[tree_pool_size - 2].total_count_;
+ tree_size -= 2;
+ {
+ // Search for the insertion point.
+ int k;
+ for (k = 0; k < tree_size; ++k) {
+ if (tree[k].total_count_ <= count) {
+ break;
+ }
+ }
+ memmove(tree + (k + 1), tree + k, (tree_size - k) * sizeof(*tree));
+ tree[k].total_count_ = count;
+ tree[k].value_ = -1;
+
+ tree[k].pool_index_left_ = tree_pool_size - 1;
+ tree[k].pool_index_right_ = tree_pool_size - 2;
+ tree_size = tree_size + 1;
+ }
+ }
+ SetBitDepths(&tree[0], tree_pool, bit_depths, 0);
+ } else if (tree_size == 1) { // Trivial case: only one element.
+ bit_depths[tree[0].value_] = 1;
+ }
+
+ {
+ // Test if this Huffman tree satisfies our 'tree_depth_limit' criteria.
+ int max_depth = bit_depths[0];
+ for (j = 1; j < histogram_size; ++j) {
+ if (max_depth < bit_depths[j]) {
+ max_depth = bit_depths[j];
+ }
+ }
+ if (max_depth <= tree_depth_limit) {
+ break;
+ }
+ }
+ }
+}
+
+// -----------------------------------------------------------------------------
+// Coding of the Huffman tree values
+
+static HuffmanTreeToken* CodeRepeatedValues(int repetitions,
+ HuffmanTreeToken* tokens,
+ int value, int prev_value) {
+ assert(value <= MAX_ALLOWED_CODE_LENGTH);
+ if (value != prev_value) {
+ tokens->code = value;
+ tokens->extra_bits = 0;
+ ++tokens;
+ --repetitions;
+ }
+ while (repetitions >= 1) {
+ if (repetitions < 3) {
+ int i;
+ for (i = 0; i < repetitions; ++i) {
+ tokens->code = value;
+ tokens->extra_bits = 0;
+ ++tokens;
+ }
+ break;
+ } else if (repetitions < 7) {
+ tokens->code = 16;
+ tokens->extra_bits = repetitions - 3;
+ ++tokens;
+ break;
+ } else {
+ tokens->code = 16;
+ tokens->extra_bits = 3;
+ ++tokens;
+ repetitions -= 6;
+ }
+ }
+ return tokens;
+}
+
+static HuffmanTreeToken* CodeRepeatedZeros(int repetitions,
+ HuffmanTreeToken* tokens) {
+ while (repetitions >= 1) {
+ if (repetitions < 3) {
+ int i;
+ for (i = 0; i < repetitions; ++i) {
+ tokens->code = 0; // 0-value
+ tokens->extra_bits = 0;
+ ++tokens;
+ }
+ break;
+ } else if (repetitions < 11) {
+ tokens->code = 17;
+ tokens->extra_bits = repetitions - 3;
+ ++tokens;
+ break;
+ } else if (repetitions < 139) {
+ tokens->code = 18;
+ tokens->extra_bits = repetitions - 11;
+ ++tokens;
+ break;
+ } else {
+ tokens->code = 18;
+ tokens->extra_bits = 0x7f; // 138 repeated 0s
+ ++tokens;
+ repetitions -= 138;
+ }
+ }
+ return tokens;
+}
+
+int VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree,
+ HuffmanTreeToken* tokens, int max_tokens) {
+ HuffmanTreeToken* const starting_token = tokens;
+ HuffmanTreeToken* const ending_token = tokens + max_tokens;
+ const int depth_size = tree->num_symbols;
+ int prev_value = 8; // 8 is the initial value for rle.
+ int i = 0;
+ assert(tokens != NULL);
+ while (i < depth_size) {
+ const int value = tree->code_lengths[i];
+ int k = i + 1;
+ int runs;
+ while (k < depth_size && tree->code_lengths[k] == value) ++k;
+ runs = k - i;
+ if (value == 0) {
+ tokens = CodeRepeatedZeros(runs, tokens);
+ } else {
+ tokens = CodeRepeatedValues(runs, tokens, value, prev_value);
+ prev_value = value;
+ }
+ i += runs;
+ assert(tokens <= ending_token);
+ }
+ (void)ending_token; // suppress 'unused variable' warning
+ return (int)(tokens - starting_token);
+}
+
+// -----------------------------------------------------------------------------
+
+// Pre-reversed 4-bit values.
+static const uint8_t kReversedBits[16] = {
+ 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
+ 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
+};
+
+static uint32_t ReverseBits(int num_bits, uint32_t bits) {
+ uint32_t retval = 0;
+ int i = 0;
+ while (i < num_bits) {
+ i += 4;
+ retval |= kReversedBits[bits & 0xf] << (MAX_ALLOWED_CODE_LENGTH + 1 - i);
+ bits >>= 4;
+ }
+ retval >>= (MAX_ALLOWED_CODE_LENGTH + 1 - num_bits);
+ return retval;
+}
+
+// Get the actual bit values for a tree of bit depths.
+static void ConvertBitDepthsToSymbols(HuffmanTreeCode* const tree) {
+ // 0 bit-depth means that the symbol does not exist.
+ int i;
+ int len;
+ uint32_t next_code[MAX_ALLOWED_CODE_LENGTH + 1];
+ int depth_count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
+
+ assert(tree != NULL);
+ len = tree->num_symbols;
+ for (i = 0; i < len; ++i) {
+ const int code_length = tree->code_lengths[i];
+ assert(code_length <= MAX_ALLOWED_CODE_LENGTH);
+ ++depth_count[code_length];
+ }
+ depth_count[0] = 0; // ignore unused symbol
+ next_code[0] = 0;
+ {
+ uint32_t code = 0;
+ for (i = 1; i <= MAX_ALLOWED_CODE_LENGTH; ++i) {
+ code = (code + depth_count[i - 1]) << 1;
+ next_code[i] = code;
+ }
+ }
+ for (i = 0; i < len; ++i) {
+ const int code_length = tree->code_lengths[i];
+ tree->codes[i] = ReverseBits(code_length, next_code[code_length]++);
+ }
+}
+
+// -----------------------------------------------------------------------------
+// Main entry point
+
+void VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit,
+ uint8_t* const buf_rle, HuffmanTree* const huff_tree,
+ HuffmanTreeCode* const huff_code) {
+ const int num_symbols = huff_code->num_symbols;
+ memset(buf_rle, 0, num_symbols * sizeof(*buf_rle));
+ OptimizeHuffmanForRle(num_symbols, buf_rle, histogram);
+ GenerateOptimalTree(histogram, num_symbols, huff_tree, tree_depth_limit,
+ huff_code->code_lengths);
+ // Create the actual bit codes for the bit lengths.
+ ConvertBitDepthsToSymbols(huff_code);
+}
diff --git a/media/libwebp/src/utils/huffman_encode_utils.h b/media/libwebp/src/utils/huffman_encode_utils.h
new file mode 100644
index 0000000000..3f7f1d8074
--- /dev/null
+++ b/media/libwebp/src/utils/huffman_encode_utils.h
@@ -0,0 +1,60 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Author: Jyrki Alakuijala (jyrki@google.com)
+//
+// Entropy encoding (Huffman) for webp lossless
+
+#ifndef WEBP_UTILS_HUFFMAN_ENCODE_UTILS_H_
+#define WEBP_UTILS_HUFFMAN_ENCODE_UTILS_H_
+
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// Struct for holding the tree header in coded form.
+typedef struct {
+ uint8_t code; // value (0..15) or escape code (16,17,18)
+ uint8_t extra_bits; // extra bits for escape codes
+} HuffmanTreeToken;
+
+// Struct to represent the tree codes (depth and bits array).
+typedef struct {
+ int num_symbols; // Number of symbols.
+ uint8_t* code_lengths; // Code lengths of the symbols.
+ uint16_t* codes; // Symbol Codes.
+} HuffmanTreeCode;
+
+// Struct to represent the Huffman tree.
+typedef struct {
+ 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;
+
+// Turn the Huffman tree into a token sequence.
+// Returns the number of tokens used.
+int VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree,
+ HuffmanTreeToken* tokens, int max_tokens);
+
+// Create an optimized tree, and tokenize it.
+// 'buf_rle' and 'huff_tree' are pre-allocated and the 'tree' is the constructed
+// huffman code tree.
+void VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit,
+ uint8_t* const buf_rle, HuffmanTree* const huff_tree,
+ HuffmanTreeCode* const huff_code);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif // WEBP_UTILS_HUFFMAN_ENCODE_UTILS_H_
diff --git a/media/libwebp/src/utils/huffman_utils.c b/media/libwebp/src/utils/huffman_utils.c
new file mode 100644
index 0000000000..cf73abd437
--- /dev/null
+++ b/media/libwebp/src/utils/huffman_utils.c
@@ -0,0 +1,296 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Utilities for building and looking up Huffman trees.
+//
+// Author: Urvang Joshi (urvang@google.com)
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include "src/utils/huffman_utils.h"
+#include "src/utils/utils.h"
+#include "src/webp/format_constants.h"
+
+// Huffman data read via DecodeImageStream is represented in two (red and green)
+// bytes.
+#define MAX_HTREE_GROUPS 0x10000
+
+HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
+ HTreeGroup* const 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* const htree_groups) {
+ if (htree_groups != NULL) {
+ WebPSafeFree(htree_groups);
+ }
+}
+
+// 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;
+ }
+ return step ? (key & (step - 1)) + step : key;
+}
+
+// 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;
+}
+
+// sorted[code_lengths_size] is a pre-allocated array for sorting symbols
+// by code length.
+static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
+ const int code_lengths[], int code_lengths_size,
+ uint16_t sorted[]) {
+ HuffmanCode* table = root_table; // next available space in table
+ int total_size = 1 << root_bits; // total size root table + 2nd level table
+ 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 && sorted != NULL) ||
+ (root_table == NULL && sorted == NULL));
+ assert(root_bits > 0);
+
+ // Build histogram of code lengths.
+ for (symbol = 0; symbol < code_lengths_size; ++symbol) {
+ if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) {
+ return 0;
+ }
+ ++count[code_lengths[symbol]];
+ }
+
+ // Error, all code lengths are zeros.
+ if (count[0] == code_lengths_size) {
+ return 0;
+ }
+
+ // 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;
+ }
+ offset[len + 1] = offset[len] + count[len];
+ }
+
+ // 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) {
+ if (sorted != NULL) {
+ sorted[offset[symbol_code_length]++] = symbol;
+ } else {
+ offset[symbol_code_length]++;
+ }
+ }
+ }
+
+ // Special case code with only one value.
+ if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) {
+ if (sorted != NULL) {
+ HuffmanCode code;
+ code.bits = 0;
+ code.value = (uint16_t)sorted[0];
+ ReplicateValue(table, 1, total_size, code);
+ }
+ return total_size;
+ }
+
+ {
+ int step; // step size to replicate values in current table
+ uint32_t low = 0xffffffffu; // 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) {
+ return 0;
+ }
+ if (root_table == NULL) continue;
+ 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);
+ }
+ }
+
+ // 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) {
+ return 0;
+ }
+ for (; count[len] > 0; --count[len]) {
+ HuffmanCode code;
+ if ((key & mask) != low) {
+ if (root_table != NULL) table += table_size;
+ table_bits = NextTableBitSize(count, len, root_bits);
+ table_size = 1 << table_bits;
+ total_size += table_size;
+ low = key & mask;
+ if (root_table != NULL) {
+ root_table[low].bits = (uint8_t)(table_bits + root_bits);
+ root_table[low].value = (uint16_t)((table - root_table) - low);
+ }
+ }
+ if (root_table != NULL) {
+ 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);
+ }
+ }
+
+ // Check if tree is full.
+ if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) {
+ return 0;
+ }
+ }
+
+ return total_size;
+}
+
+// Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_bits).
+// More commonly, the value is around ~280.
+#define MAX_CODE_LENGTHS_SIZE \
+ ((1 << MAX_CACHE_BITS) + NUM_LITERAL_CODES + NUM_LENGTH_CODES)
+// Cut-off value for switching between heap and stack allocation.
+#define SORTED_SIZE_CUTOFF 512
+int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits,
+ const int code_lengths[], int code_lengths_size) {
+ const int total_size =
+ BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL);
+ assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE);
+ if (total_size == 0 || root_table == NULL) return total_size;
+
+ if (root_table->curr_segment->curr_table + total_size >=
+ root_table->curr_segment->start + root_table->curr_segment->size) {
+ // If 'root_table' does not have enough memory, allocate a new segment.
+ // The available part of root_table->curr_segment is left unused because we
+ // need a contiguous buffer.
+ const int segment_size = root_table->curr_segment->size;
+ struct HuffmanTablesSegment* next =
+ (HuffmanTablesSegment*)WebPSafeMalloc(1, sizeof(*next));
+ if (next == NULL) return 0;
+ // Fill the new segment.
+ // We need at least 'total_size' but if that value is small, it is better to
+ // allocate a big chunk to prevent more allocations later. 'segment_size' is
+ // therefore chosen (any other arbitrary value could be chosen).
+ next->size = total_size > segment_size ? total_size : segment_size;
+ next->start =
+ (HuffmanCode*)WebPSafeMalloc(next->size, sizeof(*next->start));
+ if (next->start == NULL) {
+ WebPSafeFree(next);
+ return 0;
+ }
+ next->curr_table = next->start;
+ next->next = NULL;
+ // Point to the new segment.
+ root_table->curr_segment->next = next;
+ root_table->curr_segment = next;
+ }
+ if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
+ // use local stack-allocated array.
+ uint16_t sorted[SORTED_SIZE_CUTOFF];
+ BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
+ code_lengths, code_lengths_size, sorted);
+ } else { // rare case. Use heap allocation.
+ uint16_t* const sorted =
+ (uint16_t*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted));
+ if (sorted == NULL) return 0;
+ BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits,
+ code_lengths, code_lengths_size, sorted);
+ WebPSafeFree(sorted);
+ }
+ return total_size;
+}
+
+int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables) {
+ // Have 'segment' point to the first segment for now, 'root'.
+ HuffmanTablesSegment* const root = &huffman_tables->root;
+ huffman_tables->curr_segment = root;
+ // Allocate root.
+ root->start = (HuffmanCode*)WebPSafeMalloc(size, sizeof(*root->start));
+ if (root->start == NULL) return 0;
+ root->curr_table = root->start;
+ root->next = NULL;
+ root->size = size;
+ return 1;
+}
+
+void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables) {
+ HuffmanTablesSegment *current, *next;
+ if (huffman_tables == NULL) return;
+ // Free the root node.
+ current = &huffman_tables->root;
+ next = current->next;
+ WebPSafeFree(current->start);
+ current->start = NULL;
+ current->next = NULL;
+ current = next;
+ // Free the following nodes.
+ while (current != NULL) {
+ next = current->next;
+ WebPSafeFree(current->start);
+ WebPSafeFree(current);
+ current = next;
+ }
+}
diff --git a/media/libwebp/src/utils/huffman_utils.h b/media/libwebp/src/utils/huffman_utils.h
new file mode 100644
index 0000000000..98415c5328
--- /dev/null
+++ b/media/libwebp/src/utils/huffman_utils.h
@@ -0,0 +1,111 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Utilities for building and looking up Huffman trees.
+//
+// Author: Urvang Joshi (urvang@google.com)
+
+#ifndef WEBP_UTILS_HUFFMAN_UTILS_H_
+#define WEBP_UTILS_HUFFMAN_UTILS_H_
+
+#include <assert.h>
+#include "src/webp/format_constants.h"
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#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 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;
+
+// Contiguous memory segment of HuffmanCodes.
+typedef struct HuffmanTablesSegment {
+ HuffmanCode* start;
+ // Pointer to where we are writing into the segment. Starts at 'start' and
+ // cannot go beyond 'start' + 'size'.
+ HuffmanCode* curr_table;
+ // Pointer to the next segment in the chain.
+ struct HuffmanTablesSegment* next;
+ int size;
+} HuffmanTablesSegment;
+
+// Chained memory segments of HuffmanCodes.
+typedef struct HuffmanTables {
+ HuffmanTablesSegment root;
+ // Currently processed segment. At first, this is 'root'.
+ HuffmanTablesSegment* curr_segment;
+} HuffmanTables;
+
+// Allocates a HuffmanTables with 'size' contiguous HuffmanCodes. Returns 0 on
+// memory allocation error, 1 otherwise.
+int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables);
+void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables);
+
+#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 {
+ 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];
+};
+
+// 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* 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(HuffmanTables* const root_table, int root_bits,
+ const int code_lengths[], int code_lengths_size);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_HUFFMAN_UTILS_H_
diff --git a/media/libwebp/src/utils/moz.build b/media/libwebp/src/utils/moz.build
new file mode 100644
index 0000000000..b4a01a8ada
--- /dev/null
+++ b/media/libwebp/src/utils/moz.build
@@ -0,0 +1,32 @@
+# -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
+# vim: set filetype=python:
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+SOURCES += [
+ 'bit_reader_utils.c',
+ 'bit_writer_utils.c',
+ 'color_cache_utils.c',
+ 'filters_utils.c',
+ 'huffman_encode_utils.c',
+ 'huffman_utils.c',
+ 'quant_levels_dec_utils.c',
+ 'quant_levels_utils.c',
+ 'random_utils.c',
+ 'rescaler_utils.c',
+ 'thread_utils.c',
+ 'utils.c',
+]
+
+LOCAL_INCLUDES += [
+ '/media/libwebp',
+]
+
+# Add libFuzzer configuration directives
+include('/tools/fuzzing/libfuzzer-config.mozbuild')
+
+FINAL_LIBRARY = 'gkmedias'
+
+# We allow warnings for third-party code that can be updated from upstream.
+AllowCompilerWarnings()
diff --git a/media/libwebp/src/utils/quant_levels_dec_utils.c b/media/libwebp/src/utils/quant_levels_dec_utils.c
new file mode 100644
index 0000000000..97e7893704
--- /dev/null
+++ b/media/libwebp/src/utils/quant_levels_dec_utils.c
@@ -0,0 +1,291 @@
+// Copyright 2013 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Implement gradient smoothing: we replace a current alpha value by its
+// surrounding average if it's close enough (that is: the change will be less
+// than the minimum distance between two quantized level).
+// We use sliding window for computing the 2d moving average.
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#include "src/utils/quant_levels_dec_utils.h"
+
+#include <string.h> // for memset
+
+#include "src/utils/utils.h"
+
+// #define USE_DITHERING // uncomment to enable ordered dithering (not vital)
+
+#define FIX 16 // fix-point precision for averaging
+#define LFIX 2 // extra precision for look-up table
+#define LUT_SIZE ((1 << (8 + LFIX)) - 1) // look-up table size
+
+#if defined(USE_DITHERING)
+
+#define DFIX 4 // extra precision for ordered dithering
+#define DSIZE 4 // dithering size (must be a power of two)
+// cf. https://en.wikipedia.org/wiki/Ordered_dithering
+static const uint8_t kOrderedDither[DSIZE][DSIZE] = {
+ { 0, 8, 2, 10 }, // coefficients are in DFIX fixed-point precision
+ { 12, 4, 14, 6 },
+ { 3, 11, 1, 9 },
+ { 15, 7, 13, 5 }
+};
+
+#else
+#define DFIX 0
+#endif
+
+typedef struct {
+ int width_, height_; // dimension
+ int stride_; // stride in bytes
+ int row_; // current input row being processed
+ uint8_t* src_; // input pointer
+ uint8_t* dst_; // output pointer
+
+ int radius_; // filter radius (=delay)
+ int scale_; // normalization factor, in FIX bits precision
+
+ void* mem_; // all memory
+
+ // various scratch buffers
+ uint16_t* start_;
+ uint16_t* cur_;
+ uint16_t* end_;
+ uint16_t* top_;
+ uint16_t* average_;
+
+ // input levels distribution
+ int num_levels_; // number of quantized levels
+ int min_, max_; // min and max level values
+ int min_level_dist_; // smallest distance between two consecutive levels
+
+ int16_t* correction_; // size = 1 + 2*LUT_SIZE -> ~4k memory
+} SmoothParams;
+
+//------------------------------------------------------------------------------
+
+#define CLIP_8b_MASK (int)(~0U << (8 + DFIX))
+static WEBP_INLINE uint8_t clip_8b(int v) {
+ return (!(v & CLIP_8b_MASK)) ? (uint8_t)(v >> DFIX) : (v < 0) ? 0u : 255u;
+}
+#undef CLIP_8b_MASK
+
+// vertical accumulation
+static void VFilter(SmoothParams* const p) {
+ const uint8_t* src = p->src_;
+ const int w = p->width_;
+ uint16_t* const cur = p->cur_;
+ const uint16_t* const top = p->top_;
+ uint16_t* const out = p->end_;
+ uint16_t sum = 0; // all arithmetic is modulo 16bit
+ int x;
+
+ for (x = 0; x < w; ++x) {
+ uint16_t new_value;
+ sum += src[x];
+ new_value = top[x] + sum;
+ out[x] = new_value - cur[x]; // vertical sum of 'r' pixels.
+ cur[x] = new_value;
+ }
+ // move input pointers one row down
+ p->top_ = p->cur_;
+ p->cur_ += w;
+ if (p->cur_ == p->end_) p->cur_ = p->start_; // roll-over
+ // We replicate edges, as it's somewhat easier as a boundary condition.
+ // That's why we don't update the 'src' pointer on top/bottom area:
+ if (p->row_ >= 0 && p->row_ < p->height_ - 1) {
+ p->src_ += p->stride_;
+ }
+}
+
+// horizontal accumulation. We use mirror replication of missing pixels, as it's
+// a little easier to implement (surprisingly).
+static void HFilter(SmoothParams* const p) {
+ const uint16_t* const in = p->end_;
+ uint16_t* const out = p->average_;
+ const uint32_t scale = p->scale_;
+ const int w = p->width_;
+ const int r = p->radius_;
+
+ int x;
+ for (x = 0; x <= r; ++x) { // left mirroring
+ const uint16_t delta = in[x + r - 1] + in[r - x];
+ out[x] = (delta * scale) >> FIX;
+ }
+ for (; x < w - r; ++x) { // bulk middle run
+ const uint16_t delta = in[x + r] - in[x - r - 1];
+ out[x] = (delta * scale) >> FIX;
+ }
+ for (; x < w; ++x) { // right mirroring
+ const uint16_t delta =
+ 2 * in[w - 1] - in[2 * w - 2 - r - x] - in[x - r - 1];
+ out[x] = (delta * scale) >> FIX;
+ }
+}
+
+// emit one filtered output row
+static void ApplyFilter(SmoothParams* const p) {
+ const uint16_t* const average = p->average_;
+ const int w = p->width_;
+ const int16_t* const correction = p->correction_;
+#if defined(USE_DITHERING)
+ const uint8_t* const dither = kOrderedDither[p->row_ % DSIZE];
+#endif
+ uint8_t* const dst = p->dst_;
+ int x;
+ for (x = 0; x < w; ++x) {
+ const int v = dst[x];
+ if (v < p->max_ && v > p->min_) {
+ const int c = (v << DFIX) + correction[average[x] - (v << LFIX)];
+#if defined(USE_DITHERING)
+ dst[x] = clip_8b(c + dither[x % DSIZE]);
+#else
+ dst[x] = clip_8b(c);
+#endif
+ }
+ }
+ p->dst_ += p->stride_; // advance output pointer
+}
+
+//------------------------------------------------------------------------------
+// Initialize correction table
+
+static void InitCorrectionLUT(int16_t* const lut, int min_dist) {
+ // The correction curve is:
+ // f(x) = x for x <= threshold2
+ // f(x) = 0 for x >= threshold1
+ // and a linear interpolation for range x=[threshold2, threshold1]
+ // (along with f(-x) = -f(x) symmetry).
+ // Note that: threshold2 = 3/4 * threshold1
+ const int threshold1 = min_dist << LFIX;
+ const int threshold2 = (3 * threshold1) >> 2;
+ const int max_threshold = threshold2 << DFIX;
+ const int delta = threshold1 - threshold2;
+ int i;
+ for (i = 1; i <= LUT_SIZE; ++i) {
+ int c = (i <= threshold2) ? (i << DFIX)
+ : (i < threshold1) ? max_threshold * (threshold1 - i) / delta
+ : 0;
+ c >>= LFIX;
+ lut[+i] = +c;
+ lut[-i] = -c;
+ }
+ lut[0] = 0;
+}
+
+static void CountLevels(SmoothParams* const p) {
+ int i, j, last_level;
+ uint8_t used_levels[256] = { 0 };
+ const uint8_t* data = p->src_;
+ p->min_ = 255;
+ p->max_ = 0;
+ for (j = 0; j < p->height_; ++j) {
+ for (i = 0; i < p->width_; ++i) {
+ const int v = data[i];
+ if (v < p->min_) p->min_ = v;
+ if (v > p->max_) p->max_ = v;
+ used_levels[v] = 1;
+ }
+ data += p->stride_;
+ }
+ // Compute the mininum distance between two non-zero levels.
+ p->min_level_dist_ = p->max_ - p->min_;
+ last_level = -1;
+ for (i = 0; i < 256; ++i) {
+ if (used_levels[i]) {
+ ++p->num_levels_;
+ if (last_level >= 0) {
+ const int level_dist = i - last_level;
+ if (level_dist < p->min_level_dist_) {
+ p->min_level_dist_ = level_dist;
+ }
+ }
+ last_level = i;
+ }
+ }
+}
+
+// Initialize all params.
+static int InitParams(uint8_t* const data, int width, int height, int stride,
+ int radius, SmoothParams* const p) {
+ const int R = 2 * radius + 1; // total size of the kernel
+
+ const size_t size_scratch_m = (R + 1) * width * sizeof(*p->start_);
+ const size_t size_m = width * sizeof(*p->average_);
+ const size_t size_lut = (1 + 2 * LUT_SIZE) * sizeof(*p->correction_);
+ const size_t total_size = size_scratch_m + size_m + size_lut;
+ uint8_t* mem = (uint8_t*)WebPSafeMalloc(1U, total_size);
+
+ if (mem == NULL) return 0;
+ p->mem_ = (void*)mem;
+
+ p->start_ = (uint16_t*)mem;
+ p->cur_ = p->start_;
+ p->end_ = p->start_ + R * width;
+ p->top_ = p->end_ - width;
+ memset(p->top_, 0, width * sizeof(*p->top_));
+ mem += size_scratch_m;
+
+ p->average_ = (uint16_t*)mem;
+ mem += size_m;
+
+ p->width_ = width;
+ p->height_ = height;
+ p->stride_ = stride;
+ p->src_ = data;
+ p->dst_ = data;
+ p->radius_ = radius;
+ p->scale_ = (1 << (FIX + LFIX)) / (R * R); // normalization constant
+ p->row_ = -radius;
+
+ // analyze the input distribution so we can best-fit the threshold
+ CountLevels(p);
+
+ // correction table
+ p->correction_ = ((int16_t*)mem) + LUT_SIZE;
+ InitCorrectionLUT(p->correction_, p->min_level_dist_);
+
+ return 1;
+}
+
+static void CleanupParams(SmoothParams* const p) {
+ WebPSafeFree(p->mem_);
+}
+
+int WebPDequantizeLevels(uint8_t* const data, int width, int height, int stride,
+ int strength) {
+ int radius = 4 * strength / 100;
+
+ if (strength < 0 || strength > 100) return 0;
+ if (data == NULL || width <= 0 || height <= 0) return 0; // bad params
+
+ // limit the filter size to not exceed the image dimensions
+ if (2 * radius + 1 > width) radius = (width - 1) >> 1;
+ if (2 * radius + 1 > height) radius = (height - 1) >> 1;
+
+ if (radius > 0) {
+ SmoothParams p;
+ memset(&p, 0, sizeof(p));
+ if (!InitParams(data, width, height, stride, radius, &p)) return 0;
+ if (p.num_levels_ > 2) {
+ for (; p.row_ < p.height_; ++p.row_) {
+ VFilter(&p); // accumulate average of input
+ // Need to wait few rows in order to prime the filter,
+ // before emitting some output.
+ if (p.row_ >= p.radius_) {
+ HFilter(&p);
+ ApplyFilter(&p);
+ }
+ }
+ }
+ CleanupParams(&p);
+ }
+ return 1;
+}
diff --git a/media/libwebp/src/utils/quant_levels_dec_utils.h b/media/libwebp/src/utils/quant_levels_dec_utils.h
new file mode 100644
index 0000000000..327f19f336
--- /dev/null
+++ b/media/libwebp/src/utils/quant_levels_dec_utils.h
@@ -0,0 +1,35 @@
+// Copyright 2013 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Alpha plane de-quantization utility
+//
+// Author: Vikas Arora (vikasa@google.com)
+
+#ifndef WEBP_UTILS_QUANT_LEVELS_DEC_UTILS_H_
+#define WEBP_UTILS_QUANT_LEVELS_DEC_UTILS_H_
+
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// Apply post-processing to input 'data' of size 'width'x'height' assuming that
+// the source was quantized to a reduced number of levels. 'stride' is in bytes.
+// Strength is in [0..100] and controls the amount of dithering applied.
+// Returns false in case of error (data is NULL, invalid parameters,
+// malloc failure, ...).
+int WebPDequantizeLevels(uint8_t* const data, int width, int height, int stride,
+ int strength);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_QUANT_LEVELS_DEC_UTILS_H_
diff --git a/media/libwebp/src/utils/quant_levels_utils.c b/media/libwebp/src/utils/quant_levels_utils.c
new file mode 100644
index 0000000000..d65ad3c29d
--- /dev/null
+++ b/media/libwebp/src/utils/quant_levels_utils.c
@@ -0,0 +1,140 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Quantize levels for specified number of quantization-levels ([2, 256]).
+// Min and max values are preserved (usual 0 and 255 for alpha plane).
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#include <assert.h>
+
+#include "src/utils/quant_levels_utils.h"
+
+#define NUM_SYMBOLS 256
+
+#define MAX_ITER 6 // Maximum number of convergence steps.
+#define ERROR_THRESHOLD 1e-4 // MSE stopping criterion.
+
+// -----------------------------------------------------------------------------
+// Quantize levels.
+
+int QuantizeLevels(uint8_t* const data, int width, int height,
+ int num_levels, uint64_t* const sse) {
+ int freq[NUM_SYMBOLS] = { 0 };
+ int q_level[NUM_SYMBOLS] = { 0 };
+ double inv_q_level[NUM_SYMBOLS] = { 0 };
+ int min_s = 255, max_s = 0;
+ const size_t data_size = height * width;
+ int i, num_levels_in, iter;
+ double last_err = 1.e38, err = 0.;
+ const double err_threshold = ERROR_THRESHOLD * data_size;
+
+ if (data == NULL) {
+ return 0;
+ }
+
+ if (width <= 0 || height <= 0) {
+ return 0;
+ }
+
+ if (num_levels < 2 || num_levels > 256) {
+ return 0;
+ }
+
+ {
+ size_t n;
+ num_levels_in = 0;
+ for (n = 0; n < data_size; ++n) {
+ num_levels_in += (freq[data[n]] == 0);
+ if (min_s > data[n]) min_s = data[n];
+ if (max_s < data[n]) max_s = data[n];
+ ++freq[data[n]];
+ }
+ }
+
+ if (num_levels_in <= num_levels) goto End; // nothing to do!
+
+ // Start with uniformly spread centroids.
+ for (i = 0; i < num_levels; ++i) {
+ inv_q_level[i] = min_s + (double)(max_s - min_s) * i / (num_levels - 1);
+ }
+
+ // Fixed values. Won't be changed.
+ q_level[min_s] = 0;
+ q_level[max_s] = num_levels - 1;
+ assert(inv_q_level[0] == min_s);
+ assert(inv_q_level[num_levels - 1] == max_s);
+
+ // k-Means iterations.
+ for (iter = 0; iter < MAX_ITER; ++iter) {
+ double q_sum[NUM_SYMBOLS] = { 0 };
+ double q_count[NUM_SYMBOLS] = { 0 };
+ int s, slot = 0;
+
+ // Assign classes to representatives.
+ for (s = min_s; s <= max_s; ++s) {
+ // Keep track of the nearest neighbour 'slot'
+ while (slot < num_levels - 1 &&
+ 2 * s > inv_q_level[slot] + inv_q_level[slot + 1]) {
+ ++slot;
+ }
+ if (freq[s] > 0) {
+ q_sum[slot] += s * freq[s];
+ q_count[slot] += freq[s];
+ }
+ q_level[s] = slot;
+ }
+
+ // Assign new representatives to classes.
+ if (num_levels > 2) {
+ for (slot = 1; slot < num_levels - 1; ++slot) {
+ const double count = q_count[slot];
+ if (count > 0.) {
+ inv_q_level[slot] = q_sum[slot] / count;
+ }
+ }
+ }
+
+ // Compute convergence error.
+ err = 0.;
+ for (s = min_s; s <= max_s; ++s) {
+ const double error = s - inv_q_level[q_level[s]];
+ err += freq[s] * error * error;
+ }
+
+ // Check for convergence: we stop as soon as the error is no
+ // longer improving.
+ if (last_err - err < err_threshold) break;
+ last_err = err;
+ }
+
+ // Remap the alpha plane to quantized values.
+ {
+ // double->int rounding operation can be costly, so we do it
+ // once for all before remapping. We also perform the data[] -> slot
+ // mapping, while at it (avoid one indirection in the final loop).
+ uint8_t map[NUM_SYMBOLS];
+ int s;
+ size_t n;
+ for (s = min_s; s <= max_s; ++s) {
+ const int slot = q_level[s];
+ map[s] = (uint8_t)(inv_q_level[slot] + .5);
+ }
+ // Final pass.
+ for (n = 0; n < data_size; ++n) {
+ data[n] = map[data[n]];
+ }
+ }
+ End:
+ // Store sum of squared error if needed.
+ if (sse != NULL) *sse = (uint64_t)err;
+
+ return 1;
+}
+
diff --git a/media/libwebp/src/utils/quant_levels_utils.h b/media/libwebp/src/utils/quant_levels_utils.h
new file mode 100644
index 0000000000..9ee3ea0075
--- /dev/null
+++ b/media/libwebp/src/utils/quant_levels_utils.h
@@ -0,0 +1,36 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Alpha plane quantization utility
+//
+// Author: Vikas Arora (vikasa@google.com)
+
+#ifndef WEBP_UTILS_QUANT_LEVELS_UTILS_H_
+#define WEBP_UTILS_QUANT_LEVELS_UTILS_H_
+
+#include <stdlib.h>
+
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// Replace the input 'data' of size 'width'x'height' with 'num-levels'
+// quantized values. If not NULL, 'sse' will contain the sum of squared error.
+// Valid range for 'num_levels' is [2, 256].
+// Returns false in case of error (data is NULL, or parameters are invalid).
+int QuantizeLevels(uint8_t* const data, int width, int height, int num_levels,
+ uint64_t* const sse);
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_QUANT_LEVELS_UTILS_H_
diff --git a/media/libwebp/src/utils/random_utils.c b/media/libwebp/src/utils/random_utils.c
new file mode 100644
index 0000000000..7edb3fefbb
--- /dev/null
+++ b/media/libwebp/src/utils/random_utils.c
@@ -0,0 +1,43 @@
+// Copyright 2013 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Pseudo-random utilities
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#include <string.h>
+#include "src/utils/random_utils.h"
+
+//------------------------------------------------------------------------------
+
+// 31b-range values
+static const uint32_t kRandomTable[VP8_RANDOM_TABLE_SIZE] = {
+ 0x0de15230, 0x03b31886, 0x775faccb, 0x1c88626a, 0x68385c55, 0x14b3b828,
+ 0x4a85fef8, 0x49ddb84b, 0x64fcf397, 0x5c550289, 0x4a290000, 0x0d7ec1da,
+ 0x5940b7ab, 0x5492577d, 0x4e19ca72, 0x38d38c69, 0x0c01ee65, 0x32a1755f,
+ 0x5437f652, 0x5abb2c32, 0x0faa57b1, 0x73f533e7, 0x685feeda, 0x7563cce2,
+ 0x6e990e83, 0x4730a7ed, 0x4fc0d9c6, 0x496b153c, 0x4f1403fa, 0x541afb0c,
+ 0x73990b32, 0x26d7cb1c, 0x6fcc3706, 0x2cbb77d8, 0x75762f2a, 0x6425ccdd,
+ 0x24b35461, 0x0a7d8715, 0x220414a8, 0x141ebf67, 0x56b41583, 0x73e502e3,
+ 0x44cab16f, 0x28264d42, 0x73baaefb, 0x0a50ebed, 0x1d6ab6fb, 0x0d3ad40b,
+ 0x35db3b68, 0x2b081e83, 0x77ce6b95, 0x5181e5f0, 0x78853bbc, 0x009f9494,
+ 0x27e5ed3c
+};
+
+void VP8InitRandom(VP8Random* const rg, float dithering) {
+ memcpy(rg->tab_, kRandomTable, sizeof(rg->tab_));
+ rg->index1_ = 0;
+ rg->index2_ = 31;
+ rg->amp_ = (dithering < 0.0) ? 0
+ : (dithering > 1.0) ? (1 << VP8_RANDOM_DITHER_FIX)
+ : (uint32_t)((1 << VP8_RANDOM_DITHER_FIX) * dithering);
+}
+
+//------------------------------------------------------------------------------
+
diff --git a/media/libwebp/src/utils/random_utils.h b/media/libwebp/src/utils/random_utils.h
new file mode 100644
index 0000000000..a5006f84f7
--- /dev/null
+++ b/media/libwebp/src/utils/random_utils.h
@@ -0,0 +1,63 @@
+// Copyright 2013 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Pseudo-random utilities
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#ifndef WEBP_UTILS_RANDOM_UTILS_H_
+#define WEBP_UTILS_RANDOM_UTILS_H_
+
+#include <assert.h>
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define VP8_RANDOM_DITHER_FIX 8 // fixed-point precision for dithering
+#define VP8_RANDOM_TABLE_SIZE 55
+
+typedef struct {
+ int index1_, index2_;
+ uint32_t tab_[VP8_RANDOM_TABLE_SIZE];
+ int amp_;
+} VP8Random;
+
+// Initializes random generator with an amplitude 'dithering' in range [0..1].
+void VP8InitRandom(VP8Random* const rg, float dithering);
+
+// Returns a centered pseudo-random number with 'num_bits' amplitude.
+// (uses D.Knuth's Difference-based random generator).
+// 'amp' is in VP8_RANDOM_DITHER_FIX fixed-point precision.
+static WEBP_INLINE int VP8RandomBits2(VP8Random* const rg, int num_bits,
+ int amp) {
+ int diff;
+ assert(num_bits + VP8_RANDOM_DITHER_FIX <= 31);
+ diff = rg->tab_[rg->index1_] - rg->tab_[rg->index2_];
+ if (diff < 0) diff += (1u << 31);
+ rg->tab_[rg->index1_] = diff;
+ if (++rg->index1_ == VP8_RANDOM_TABLE_SIZE) rg->index1_ = 0;
+ if (++rg->index2_ == VP8_RANDOM_TABLE_SIZE) rg->index2_ = 0;
+ // sign-extend, 0-center
+ diff = (int)((uint32_t)diff << 1) >> (32 - num_bits);
+ diff = (diff * amp) >> VP8_RANDOM_DITHER_FIX; // restrict range
+ diff += 1 << (num_bits - 1); // shift back to 0.5-center
+ return diff;
+}
+
+static WEBP_INLINE int VP8RandomBits(VP8Random* const rg, int num_bits) {
+ return VP8RandomBits2(rg, num_bits, rg->amp_);
+}
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_RANDOM_UTILS_H_
diff --git a/media/libwebp/src/utils/rescaler_utils.c b/media/libwebp/src/utils/rescaler_utils.c
new file mode 100644
index 0000000000..a0581a14b1
--- /dev/null
+++ b/media/libwebp/src/utils/rescaler_utils.c
@@ -0,0 +1,160 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Rescaling functions
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#include <assert.h>
+#include <limits.h>
+#include <stdlib.h>
+#include <string.h>
+#include "src/dsp/dsp.h"
+#include "src/utils/rescaler_utils.h"
+#include "src/utils/utils.h"
+
+//------------------------------------------------------------------------------
+
+int WebPRescalerInit(WebPRescaler* const rescaler,
+ int src_width, int src_height,
+ uint8_t* const dst,
+ int dst_width, int dst_height, int dst_stride,
+ int num_channels, rescaler_t* const work) {
+ const int x_add = src_width, x_sub = dst_width;
+ const int y_add = src_height, y_sub = dst_height;
+ const uint64_t total_size = 2ull * dst_width * num_channels * sizeof(*work);
+ if (!CheckSizeOverflow(total_size)) return 0;
+
+ rescaler->x_expand = (src_width < dst_width);
+ rescaler->y_expand = (src_height < dst_height);
+ rescaler->src_width = src_width;
+ rescaler->src_height = src_height;
+ rescaler->dst_width = dst_width;
+ rescaler->dst_height = dst_height;
+ rescaler->src_y = 0;
+ rescaler->dst_y = 0;
+ rescaler->dst = dst;
+ rescaler->dst_stride = dst_stride;
+ rescaler->num_channels = num_channels;
+
+ // for 'x_expand', we use bilinear interpolation
+ rescaler->x_add = rescaler->x_expand ? (x_sub - 1) : x_add;
+ rescaler->x_sub = rescaler->x_expand ? (x_add - 1) : x_sub;
+ if (!rescaler->x_expand) { // fx_scale is not used otherwise
+ rescaler->fx_scale = WEBP_RESCALER_FRAC(1, rescaler->x_sub);
+ }
+ // vertical scaling parameters
+ rescaler->y_add = rescaler->y_expand ? y_add - 1 : y_add;
+ rescaler->y_sub = rescaler->y_expand ? y_sub - 1 : y_sub;
+ rescaler->y_accum = rescaler->y_expand ? rescaler->y_sub : rescaler->y_add;
+ if (!rescaler->y_expand) {
+ // This is WEBP_RESCALER_FRAC(dst_height, x_add * y_add) without the cast.
+ // Its value is <= WEBP_RESCALER_ONE, because dst_height <= rescaler->y_add
+ // and rescaler->x_add >= 1;
+ const uint64_t num = (uint64_t)dst_height * WEBP_RESCALER_ONE;
+ const uint64_t den = (uint64_t)rescaler->x_add * rescaler->y_add;
+ const uint64_t ratio = num / den;
+ if (ratio != (uint32_t)ratio) {
+ // When ratio == WEBP_RESCALER_ONE, we can't represent the ratio with the
+ // current fixed-point precision. This happens when src_height ==
+ // rescaler->y_add (which == src_height), and rescaler->x_add == 1.
+ // => We special-case fxy_scale = 0, in WebPRescalerExportRow().
+ rescaler->fxy_scale = 0;
+ } else {
+ rescaler->fxy_scale = (uint32_t)ratio;
+ }
+ rescaler->fy_scale = WEBP_RESCALER_FRAC(1, rescaler->y_sub);
+ } else {
+ rescaler->fy_scale = WEBP_RESCALER_FRAC(1, rescaler->x_add);
+ // rescaler->fxy_scale is unused here.
+ }
+ rescaler->irow = work;
+ rescaler->frow = work + num_channels * dst_width;
+ memset(work, 0, (size_t)total_size);
+
+ WebPRescalerDspInit();
+ return 1;
+}
+
+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;
+ const int max_size = INT_MAX / 2;
+
+ // if width is unspecified, scale original proportionally to height ratio.
+ if (width == 0 && src_height > 0) {
+ width =
+ (int)(((uint64_t)src_width * height + src_height - 1) / src_height);
+ }
+ // if height is unspecified, scale original proportionally to width ratio.
+ if (height == 0 && src_width > 0) {
+ height =
+ (int)(((uint64_t)src_height * width + src_width - 1) / src_width);
+ }
+ // Check if the overall dimensions still make sense.
+ if (width <= 0 || height <= 0 || width > max_size || height > max_size) {
+ return 0;
+ }
+
+ *scaled_width = width;
+ *scaled_height = height;
+ return 1;
+ }
+}
+
+//------------------------------------------------------------------------------
+// all-in-one calls
+
+int WebPRescaleNeededLines(const WebPRescaler* const rescaler,
+ int max_num_lines) {
+ const int num_lines =
+ (rescaler->y_accum + rescaler->y_sub - 1) / rescaler->y_sub;
+ return (num_lines > max_num_lines) ? max_num_lines : num_lines;
+}
+
+int WebPRescalerImport(WebPRescaler* const rescaler, int num_lines,
+ const uint8_t* src, int src_stride) {
+ int total_imported = 0;
+ while (total_imported < num_lines &&
+ !WebPRescalerHasPendingOutput(rescaler)) {
+ if (rescaler->y_expand) {
+ rescaler_t* const tmp = rescaler->irow;
+ rescaler->irow = rescaler->frow;
+ rescaler->frow = tmp;
+ }
+ WebPRescalerImportRow(rescaler, src);
+ if (!rescaler->y_expand) { // Accumulate the contribution of the new row.
+ int x;
+ for (x = 0; x < rescaler->num_channels * rescaler->dst_width; ++x) {
+ rescaler->irow[x] += rescaler->frow[x];
+ }
+ }
+ ++rescaler->src_y;
+ src += src_stride;
+ ++total_imported;
+ rescaler->y_accum -= rescaler->y_sub;
+ }
+ return total_imported;
+}
+
+int WebPRescalerExport(WebPRescaler* const rescaler) {
+ int total_exported = 0;
+ while (WebPRescalerHasPendingOutput(rescaler)) {
+ WebPRescalerExportRow(rescaler);
+ ++total_exported;
+ }
+ return total_exported;
+}
+
+//------------------------------------------------------------------------------
diff --git a/media/libwebp/src/utils/rescaler_utils.h b/media/libwebp/src/utils/rescaler_utils.h
new file mode 100644
index 0000000000..ef201ef86c
--- /dev/null
+++ b/media/libwebp/src/utils/rescaler_utils.h
@@ -0,0 +1,102 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Rescaling functions
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#ifndef WEBP_UTILS_RESCALER_UTILS_H_
+#define WEBP_UTILS_RESCALER_UTILS_H_
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "src/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 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
+ uint32_t fx_scale; // fixed-point scaling factors
+ uint32_t fy_scale; // ''
+ uint32_t fxy_scale; // ''
+ int y_accum; // vertical accumulator
+ int y_add, y_sub; // vertical increments
+ int x_add, x_sub; // horizontal increments
+ int src_width, src_height; // source dimensions
+ int dst_width, dst_height; // destination dimensions
+ int src_y, dst_y; // row counters for input and output
+ uint8_t* dst;
+ int dst_stride;
+ rescaler_t* irow, *frow; // work buffer
+};
+
+// Initialize a rescaler given scratch area 'work' and dimensions of src & dst.
+// Returns false in case of error.
+int WebPRescalerInit(WebPRescaler* const rescaler,
+ int src_width, int src_height,
+ uint8_t* const dst,
+ int dst_width, int dst_height, int dst_stride,
+ 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,
+ int max_num_lines);
+
+// Import multiple rows over all channels, until at least one row is ready to
+// be exported. Returns the actual number of lines that were imported.
+int WebPRescalerImport(WebPRescaler* const rescaler, int num_rows,
+ const uint8_t* src, int src_stride);
+
+// Export as many rows as possible. Return the numbers of rows written.
+int WebPRescalerExport(WebPRescaler* const rescaler);
+
+// Return true if input is finished
+static WEBP_INLINE
+int WebPRescalerInputDone(const WebPRescaler* const rescaler) {
+ return (rescaler->src_y >= rescaler->src_height);
+}
+// Return true if output is finished
+static WEBP_INLINE
+int WebPRescalerOutputDone(const WebPRescaler* const rescaler) {
+ return (rescaler->dst_y >= rescaler->dst_height);
+}
+
+// Return true if there are pending output rows ready.
+static WEBP_INLINE
+int WebPRescalerHasPendingOutput(const WebPRescaler* const rescaler) {
+ return !WebPRescalerOutputDone(rescaler) && (rescaler->y_accum <= 0);
+}
+
+//------------------------------------------------------------------------------
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_RESCALER_UTILS_H_
diff --git a/media/libwebp/src/utils/thread_utils.c b/media/libwebp/src/utils/thread_utils.c
new file mode 100644
index 0000000000..4e470e17ac
--- /dev/null
+++ b/media/libwebp/src/utils/thread_utils.c
@@ -0,0 +1,369 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Multi-threaded worker
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#include <assert.h>
+#include <string.h> // for memset()
+#include "src/utils/thread_utils.h"
+#include "src/utils/utils.h"
+
+#ifdef WEBP_USE_THREAD
+
+#if defined(_WIN32)
+
+#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
+
+#include <pthread.h>
+
+#endif // _WIN32
+
+typedef struct {
+ pthread_mutex_t mutex_;
+ pthread_cond_t condition_;
+ pthread_t thread_;
+} WebPWorkerImpl;
+
+#if defined(_WIN32)
+
+//------------------------------------------------------------------------------
+// simplistic pthread emulation layer
+
+#include <process.h>
+
+// _beginthreadex requires __stdcall
+#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;
+}
+
+static int pthread_join(pthread_t thread, void** value_ptr) {
+ (void)value_ptr;
+ return (WaitForSingleObject(thread, INFINITE) != WAIT_OBJECT_0 ||
+ CloseHandle(thread) == 0);
+}
+
+// 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;
+}
+
+static int pthread_mutex_lock(pthread_mutex_t* const mutex) {
+ EnterCriticalSection(mutex);
+ return 0;
+}
+
+static int pthread_mutex_unlock(pthread_mutex_t* const mutex) {
+ LeaveCriticalSection(mutex);
+ return 0;
+}
+
+static int pthread_mutex_destroy(pthread_mutex_t* const mutex) {
+ DeleteCriticalSection(mutex);
+ return 0;
+}
+
+// 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);
+ if (condition->waiting_sem_ == NULL ||
+ condition->received_sem_ == NULL ||
+ condition->signal_event_ == NULL) {
+ 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_);
+ // wait until the event is consumed so the signaler cannot consume
+ // the event via its own pthread_cond_wait.
+ 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)) return 1;
+ // now unlock the mutex so pthread_cond_signal may be issued
+ pthread_mutex_unlock(mutex);
+ ok = (WaitForSingleObject(condition->signal_event_, INFINITE) ==
+ WAIT_OBJECT_0);
+ ok &= ReleaseSemaphore(condition->received_sem_, 1, NULL);
+ pthread_mutex_lock(mutex);
+#endif
+ return !ok;
+}
+
+#else // !_WIN32
+# define THREADFN void*
+# define THREAD_RETURN(val) val
+#endif // _WIN32
+
+//------------------------------------------------------------------------------
+
+static THREADFN ThreadLoop(void* ptr) {
+ WebPWorker* const worker = (WebPWorker*)ptr;
+ WebPWorkerImpl* const impl = (WebPWorkerImpl*)worker->impl_;
+ int done = 0;
+ while (!done) {
+ pthread_mutex_lock(&impl->mutex_);
+ while (worker->status_ == OK) { // wait in idling mode
+ pthread_cond_wait(&impl->condition_, &impl->mutex_);
+ }
+ if (worker->status_ == WORK) {
+ WebPGetWorkerInterface()->Execute(worker);
+ worker->status_ = OK;
+ } else if (worker->status_ == NOT_OK) { // finish the worker
+ done = 1;
+ }
+ // signal to the main thread that we're done (for Sync())
+ // Note the associated mutex does not need to be held when signaling the
+ // condition. Unlocking the mutex first may improve performance in some
+ // implementations, avoiding the case where the waiting thread can't
+ // reacquire the mutex when woken.
+ pthread_mutex_unlock(&impl->mutex_);
+ pthread_cond_signal(&impl->condition_);
+ }
+ return THREAD_RETURN(NULL); // Thread is finished
+}
+
+// main thread state control
+static void ChangeState(WebPWorker* const worker, WebPWorkerStatus new_status) {
+ // No-op when attempting to change state on a thread that didn't come up.
+ // Checking status_ without acquiring the lock first would result in a data
+ // race.
+ WebPWorkerImpl* const impl = (WebPWorkerImpl*)worker->impl_;
+ if (impl == NULL) return;
+
+ pthread_mutex_lock(&impl->mutex_);
+ if (worker->status_ >= OK) {
+ // wait for the worker to finish
+ while (worker->status_ != OK) {
+ pthread_cond_wait(&impl->condition_, &impl->mutex_);
+ }
+ // assign new status and release the working thread if needed
+ if (new_status != OK) {
+ worker->status_ = new_status;
+ // Note the associated mutex does not need to be held when signaling the
+ // condition. Unlocking the mutex first may improve performance in some
+ // implementations, avoiding the case where the waiting thread can't
+ // reacquire the mutex when woken.
+ pthread_mutex_unlock(&impl->mutex_);
+ pthread_cond_signal(&impl->condition_);
+ return;
+ }
+ }
+ pthread_mutex_unlock(&impl->mutex_);
+}
+
+#endif // WEBP_USE_THREAD
+
+//------------------------------------------------------------------------------
+
+static void Init(WebPWorker* const worker) {
+ memset(worker, 0, sizeof(*worker));
+ worker->status_ = NOT_OK;
+}
+
+static int Sync(WebPWorker* const worker) {
+#ifdef WEBP_USE_THREAD
+ ChangeState(worker, OK);
+#endif
+ assert(worker->status_ <= OK);
+ return !worker->had_error;
+}
+
+static int Reset(WebPWorker* const worker) {
+ int ok = 1;
+ worker->had_error = 0;
+ if (worker->status_ < OK) {
+#ifdef WEBP_USE_THREAD
+ WebPWorkerImpl* const impl =
+ (WebPWorkerImpl*)WebPSafeCalloc(1, sizeof(WebPWorkerImpl));
+ worker->impl_ = (void*)impl;
+ if (worker->impl_ == NULL) {
+ return 0;
+ }
+ if (pthread_mutex_init(&impl->mutex_, NULL)) {
+ goto Error;
+ }
+ if (pthread_cond_init(&impl->condition_, NULL)) {
+ pthread_mutex_destroy(&impl->mutex_);
+ goto Error;
+ }
+ pthread_mutex_lock(&impl->mutex_);
+ ok = !pthread_create(&impl->thread_, NULL, ThreadLoop, worker);
+ if (ok) worker->status_ = OK;
+ pthread_mutex_unlock(&impl->mutex_);
+ if (!ok) {
+ pthread_mutex_destroy(&impl->mutex_);
+ pthread_cond_destroy(&impl->condition_);
+ Error:
+ WebPSafeFree(impl);
+ worker->impl_ = NULL;
+ return 0;
+ }
+#else
+ worker->status_ = OK;
+#endif
+ } else if (worker->status_ > OK) {
+ ok = Sync(worker);
+ }
+ assert(!ok || (worker->status_ == OK));
+ return ok;
+}
+
+static void Execute(WebPWorker* const worker) {
+ if (worker->hook != NULL) {
+ worker->had_error |= !worker->hook(worker->data1, worker->data2);
+ }
+}
+
+static void Launch(WebPWorker* const worker) {
+#ifdef WEBP_USE_THREAD
+ ChangeState(worker, WORK);
+#else
+ Execute(worker);
+#endif
+}
+
+static void End(WebPWorker* const worker) {
+#ifdef WEBP_USE_THREAD
+ if (worker->impl_ != NULL) {
+ WebPWorkerImpl* const impl = (WebPWorkerImpl*)worker->impl_;
+ ChangeState(worker, NOT_OK);
+ pthread_join(impl->thread_, NULL);
+ pthread_mutex_destroy(&impl->mutex_);
+ pthread_cond_destroy(&impl->condition_);
+ WebPSafeFree(impl);
+ worker->impl_ = NULL;
+ }
+#else
+ worker->status_ = NOT_OK;
+ assert(worker->impl_ == NULL);
+#endif
+ assert(worker->status_ == NOT_OK);
+}
+
+//------------------------------------------------------------------------------
+
+static WebPWorkerInterface g_worker_interface = {
+ Init, Reset, Sync, Launch, Execute, End
+};
+
+int WebPSetWorkerInterface(const WebPWorkerInterface* const winterface) {
+ if (winterface == NULL ||
+ winterface->Init == NULL || winterface->Reset == NULL ||
+ winterface->Sync == NULL || winterface->Launch == NULL ||
+ winterface->Execute == NULL || winterface->End == NULL) {
+ return 0;
+ }
+ g_worker_interface = *winterface;
+ return 1;
+}
+
+const WebPWorkerInterface* WebPGetWorkerInterface(void) {
+ return &g_worker_interface;
+}
+
+//------------------------------------------------------------------------------
diff --git a/media/libwebp/src/utils/thread_utils.h b/media/libwebp/src/utils/thread_utils.h
new file mode 100644
index 0000000000..29ad49f74b
--- /dev/null
+++ b/media/libwebp/src/utils/thread_utils.h
@@ -0,0 +1,90 @@
+// Copyright 2011 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Multi-threaded worker
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#ifndef WEBP_UTILS_THREAD_UTILS_H_
+#define WEBP_UTILS_THREAD_UTILS_H_
+
+#ifdef HAVE_CONFIG_H
+#include "src/webp/config.h"
+#endif
+
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+// State of the worker thread object
+typedef enum {
+ NOT_OK = 0, // object is unusable
+ OK, // ready to work
+ WORK // busy finishing the current task
+} WebPWorkerStatus;
+
+// Function to be called by the worker thread. Takes two opaque pointers as
+// arguments (data1 and data2), and should return false in case of error.
+typedef int (*WebPWorkerHook)(void*, void*);
+
+// Synchronization object used to launch job in the worker thread
+typedef struct {
+ void* impl_; // platform-dependent implementation worker details
+ WebPWorkerStatus status_;
+ WebPWorkerHook hook; // hook to call
+ void* data1; // first argument passed to 'hook'
+ void* data2; // second argument passed to 'hook'
+ int had_error; // return value of the last call to 'hook'
+} WebPWorker;
+
+// The interface for all thread-worker related functions. All these functions
+// must be implemented.
+typedef struct {
+ // Must be called first, before any other method.
+ void (*Init)(WebPWorker* const worker);
+ // Must be called to initialize the object and spawn the thread. Re-entrant.
+ // Will potentially launch the thread. Returns false in case of error.
+ int (*Reset)(WebPWorker* const worker);
+ // Makes sure the previous work is finished. Returns true if worker->had_error
+ // was not set and no error condition was triggered by the working thread.
+ int (*Sync)(WebPWorker* const worker);
+ // Triggers the thread to call hook() with data1 and data2 arguments. These
+ // hook/data1/data2 values can be changed at any time before calling this
+ // function, but not be changed afterward until the next call to Sync().
+ void (*Launch)(WebPWorker* const worker);
+ // This function is similar to Launch() except that it calls the
+ // hook directly instead of using a thread. Convenient to bypass the thread
+ // mechanism while still using the WebPWorker structs. Sync() must
+ // still be called afterward (for error reporting).
+ void (*Execute)(WebPWorker* const worker);
+ // Kill the thread and terminate the object. To use the object again, one
+ // must call Reset() again.
+ void (*End)(WebPWorker* const worker);
+} WebPWorkerInterface;
+
+// Install a new set of threading functions, overriding the defaults. This
+// should be done before any workers are started, i.e., before any encoding or
+// decoding takes place. The contents of the interface struct are copied, it
+// 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 winterface);
+
+// Retrieve the currently set thread worker interface.
+WEBP_EXTERN const WebPWorkerInterface* WebPGetWorkerInterface(void);
+
+//------------------------------------------------------------------------------
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_THREAD_UTILS_H_
diff --git a/media/libwebp/src/utils/utils.c b/media/libwebp/src/utils/utils.c
new file mode 100644
index 0000000000..a7c3a70fef
--- /dev/null
+++ b/media/libwebp/src/utils/utils.c
@@ -0,0 +1,338 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Misc. common utility functions
+//
+// Author: Skal (pascal.massimino@gmail.com)
+
+#include <stdlib.h>
+#include <string.h> // for memcpy()
+#include "src/webp/decode.h"
+#include "src/webp/encode.h"
+#include "src/webp/format_constants.h" // for MAX_PALETTE_SIZE
+#include "src/utils/color_cache_utils.h"
+#include "src/utils/utils.h"
+
+// If PRINT_MEM_INFO is defined, extra info (like total memory used, number of
+// alloc/free etc) is printed. For debugging/tuning purpose only (it's slow,
+// and not multi-thread safe!).
+// An interesting alternative is valgrind's 'massif' tool:
+// https://valgrind.org/docs/manual/ms-manual.html
+// Here is an example command line:
+/* valgrind --tool=massif --massif-out-file=massif.out \
+ --stacks=yes --alloc-fn=WebPSafeMalloc --alloc-fn=WebPSafeCalloc
+ ms_print massif.out
+*/
+// In addition:
+// * if PRINT_MEM_TRAFFIC is defined, all the details of the malloc/free cycles
+// are printed.
+// * if MALLOC_FAIL_AT is defined, the global environment variable
+// $MALLOC_FAIL_AT is used to simulate a memory error when calloc or malloc
+// is called for the nth time. Example usage:
+// export MALLOC_FAIL_AT=50 && ./examples/cwebp input.png
+// * if MALLOC_LIMIT is defined, the global environment variable $MALLOC_LIMIT
+// sets the maximum amount of memory (in bytes) made available to libwebp.
+// This can be used to emulate environment with very limited memory.
+// Example: export MALLOC_LIMIT=64000000 && ./examples/dwebp picture.webp
+
+// #define PRINT_MEM_INFO
+// #define PRINT_MEM_TRAFFIC
+// #define MALLOC_FAIL_AT
+// #define MALLOC_LIMIT
+
+//------------------------------------------------------------------------------
+// Checked memory allocation
+
+#if defined(PRINT_MEM_INFO)
+
+#include <stdio.h>
+
+static int num_malloc_calls = 0;
+static int num_calloc_calls = 0;
+static int num_free_calls = 0;
+static int countdown_to_fail = 0; // 0 = off
+
+typedef struct MemBlock MemBlock;
+struct MemBlock {
+ void* ptr_;
+ size_t size_;
+ MemBlock* next_;
+};
+
+static MemBlock* all_blocks = NULL;
+static size_t total_mem = 0;
+static size_t total_mem_allocated = 0;
+static size_t high_water_mark = 0;
+static size_t mem_limit = 0;
+
+static int exit_registered = 0;
+
+static void PrintMemInfo(void) {
+ fprintf(stderr, "\nMEMORY INFO:\n");
+ fprintf(stderr, "num calls to: malloc = %4d\n", num_malloc_calls);
+ fprintf(stderr, " calloc = %4d\n", num_calloc_calls);
+ fprintf(stderr, " free = %4d\n", num_free_calls);
+ fprintf(stderr, "total_mem: %u\n", (uint32_t)total_mem);
+ fprintf(stderr, "total_mem allocated: %u\n", (uint32_t)total_mem_allocated);
+ fprintf(stderr, "high-water mark: %u\n", (uint32_t)high_water_mark);
+ while (all_blocks != NULL) {
+ MemBlock* b = all_blocks;
+ all_blocks = b->next_;
+ free(b);
+ }
+}
+
+static void Increment(int* const v) {
+ if (!exit_registered) {
+#if defined(MALLOC_FAIL_AT)
+ {
+ const char* const malloc_fail_at_str = getenv("MALLOC_FAIL_AT");
+ if (malloc_fail_at_str != NULL) {
+ countdown_to_fail = atoi(malloc_fail_at_str);
+ }
+ }
+#endif
+#if defined(MALLOC_LIMIT)
+ {
+ const char* const malloc_limit_str = getenv("MALLOC_LIMIT");
+#if MALLOC_LIMIT > 1
+ mem_limit = (size_t)MALLOC_LIMIT;
+#endif
+ if (malloc_limit_str != NULL) {
+ mem_limit = atoi(malloc_limit_str);
+ }
+ }
+#endif
+ (void)countdown_to_fail;
+ (void)mem_limit;
+ atexit(PrintMemInfo);
+ exit_registered = 1;
+ }
+ ++*v;
+}
+
+static void AddMem(void* ptr, size_t size) {
+ if (ptr != NULL) {
+ MemBlock* const b = (MemBlock*)malloc(sizeof(*b));
+ if (b == NULL) abort();
+ b->next_ = all_blocks;
+ all_blocks = b;
+ b->ptr_ = ptr;
+ b->size_ = size;
+ total_mem += size;
+ total_mem_allocated += size;
+#if defined(PRINT_MEM_TRAFFIC)
+#if defined(MALLOC_FAIL_AT)
+ fprintf(stderr, "fail-count: %5d [mem=%u]\n",
+ num_malloc_calls + num_calloc_calls, (uint32_t)total_mem);
+#else
+ fprintf(stderr, "Mem: %u (+%u)\n", (uint32_t)total_mem, (uint32_t)size);
+#endif
+#endif
+ if (total_mem > high_water_mark) high_water_mark = total_mem;
+ }
+}
+
+static void SubMem(void* ptr) {
+ if (ptr != NULL) {
+ MemBlock** b = &all_blocks;
+ // Inefficient search, but that's just for debugging.
+ while (*b != NULL && (*b)->ptr_ != ptr) b = &(*b)->next_;
+ if (*b == NULL) {
+ fprintf(stderr, "Invalid pointer free! (%p)\n", ptr);
+ abort();
+ }
+ {
+ MemBlock* const block = *b;
+ *b = block->next_;
+ total_mem -= block->size_;
+#if defined(PRINT_MEM_TRAFFIC)
+ fprintf(stderr, "Mem: %u (-%u)\n",
+ (uint32_t)total_mem, (uint32_t)block->size_);
+#endif
+ free(block);
+ }
+ }
+}
+
+#else
+#define Increment(v) do {} while (0)
+#define AddMem(p, s) do {} while (0)
+#define SubMem(p) do {} while (0)
+#endif
+
+// Returns 0 in case of overflow of nmemb * size.
+static int CheckSizeArgumentsOverflow(uint64_t nmemb, size_t size) {
+ const uint64_t total_size = nmemb * size;
+ if (nmemb == 0) return 1;
+ if ((uint64_t)size > WEBP_MAX_ALLOCABLE_MEMORY / nmemb) return 0;
+ if (!CheckSizeOverflow(total_size)) return 0;
+#if defined(PRINT_MEM_INFO) && defined(MALLOC_FAIL_AT)
+ if (countdown_to_fail > 0 && --countdown_to_fail == 0) {
+ return 0; // fake fail!
+ }
+#endif
+#if defined(PRINT_MEM_INFO) && defined(MALLOC_LIMIT)
+ if (mem_limit > 0) {
+ const uint64_t new_total_mem = (uint64_t)total_mem + total_size;
+ if (!CheckSizeOverflow(new_total_mem) ||
+ new_total_mem > mem_limit) {
+ return 0; // fake fail!
+ }
+ }
+#endif
+
+ return 1;
+}
+
+void* WebPSafeMalloc(uint64_t nmemb, size_t size) {
+ void* ptr;
+ Increment(&num_malloc_calls);
+ if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL;
+ assert(nmemb * size > 0);
+ ptr = malloc((size_t)(nmemb * size));
+ AddMem(ptr, (size_t)(nmemb * size));
+ return ptr;
+}
+
+void* WebPSafeCalloc(uint64_t nmemb, size_t size) {
+ void* ptr;
+ Increment(&num_calloc_calls);
+ if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL;
+ assert(nmemb * size > 0);
+ ptr = calloc((size_t)nmemb, size);
+ AddMem(ptr, (size_t)(nmemb * size));
+ return ptr;
+}
+
+void WebPSafeFree(void* const ptr) {
+ if (ptr != NULL) {
+ Increment(&num_free_calls);
+ SubMem(ptr);
+ }
+ free(ptr);
+}
+
+// Public API functions.
+
+void* WebPMalloc(size_t size) {
+ return WebPSafeMalloc(1, size);
+}
+
+void WebPFree(void* ptr) {
+ WebPSafeFree(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(abs(src_stride) >= width && abs(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);
+}
+
+//------------------------------------------------------------------------------
+
+#define COLOR_HASH_SIZE (MAX_PALETTE_SIZE * 4)
+#define COLOR_HASH_RIGHT_SHIFT 22 // 32 - log2(COLOR_HASH_SIZE).
+
+int WebPGetColorPalette(const WebPPicture* const pic, uint32_t* const palette) {
+ int i;
+ int x, y;
+ int num_colors = 0;
+ uint8_t in_use[COLOR_HASH_SIZE] = { 0 };
+ uint32_t colors[COLOR_HASH_SIZE];
+ const uint32_t* argb = pic->argb;
+ const int width = pic->width;
+ const int height = pic->height;
+ uint32_t last_pix = ~argb[0]; // so we're sure that last_pix != argb[0]
+ assert(pic != NULL);
+ assert(pic->use_argb);
+
+ for (y = 0; y < height; ++y) {
+ for (x = 0; x < width; ++x) {
+ int key;
+ if (argb[x] == last_pix) {
+ continue;
+ }
+ last_pix = argb[x];
+ key = VP8LHashPix(last_pix, COLOR_HASH_RIGHT_SHIFT);
+ while (1) {
+ if (!in_use[key]) {
+ colors[key] = last_pix;
+ in_use[key] = 1;
+ ++num_colors;
+ if (num_colors > MAX_PALETTE_SIZE) {
+ return MAX_PALETTE_SIZE + 1; // Exact count not needed.
+ }
+ break;
+ } else if (colors[key] == last_pix) {
+ break; // The color is already there.
+ } else {
+ // Some other color sits here, so do linear conflict resolution.
+ ++key;
+ key &= (COLOR_HASH_SIZE - 1); // Key mask.
+ }
+ }
+ }
+ argb += pic->argb_stride;
+ }
+
+ if (palette != NULL) { // Fill the colors into palette.
+ num_colors = 0;
+ for (i = 0; i < COLOR_HASH_SIZE; ++i) {
+ if (in_use[i]) {
+ palette[num_colors] = colors[i];
+ ++num_colors;
+ }
+ }
+ }
+ return num_colors;
+}
+
+#undef COLOR_HASH_SIZE
+#undef COLOR_HASH_RIGHT_SHIFT
+
+//------------------------------------------------------------------------------
+
+#if defined(WEBP_NEED_LOG_TABLE_8BIT)
+const uint8_t WebPLogTable8bit[256] = { // 31 ^ clz(i)
+ 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
+ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
+};
+#endif
+
+//------------------------------------------------------------------------------
diff --git a/media/libwebp/src/utils/utils.h b/media/libwebp/src/utils/utils.h
new file mode 100644
index 0000000000..c5ee873357
--- /dev/null
+++ b/media/libwebp/src/utils/utils.h
@@ -0,0 +1,210 @@
+// Copyright 2012 Google Inc. All Rights Reserved.
+//
+// Use of this source code is governed by a BSD-style license
+// that can be found in the COPYING file in the root of the source
+// tree. An additional intellectual property rights grant can be found
+// in the file PATENTS. All contributing project authors may
+// be found in the AUTHORS file in the root of the source tree.
+// -----------------------------------------------------------------------------
+//
+// Misc. common utility functions
+//
+// Authors: Skal (pascal.massimino@gmail.com)
+// Urvang (urvang@google.com)
+
+#ifndef WEBP_UTILS_UTILS_H_
+#define WEBP_UTILS_UTILS_H_
+
+#ifdef HAVE_CONFIG_H
+#include "src/webp/config.h"
+#endif
+
+#include <assert.h>
+#include <limits.h>
+
+#include "src/dsp/dsp.h"
+#include "src/webp/types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+//------------------------------------------------------------------------------
+// Memory allocation
+
+// This is the maximum memory amount that libwebp will ever try to allocate.
+#ifndef WEBP_MAX_ALLOCABLE_MEMORY
+#if SIZE_MAX > (1ULL << 34)
+#define WEBP_MAX_ALLOCABLE_MEMORY (1ULL << 34)
+#else
+// For 32-bit targets keep this below INT_MAX to avoid valgrind warnings.
+#define WEBP_MAX_ALLOCABLE_MEMORY ((1ULL << 31) - (1 << 16))
+#endif
+#endif // WEBP_MAX_ALLOCABLE_MEMORY
+
+static WEBP_INLINE int CheckSizeOverflow(uint64_t size) {
+ return size == (size_t)size;
+}
+
+// size-checking safe malloc/calloc: verify that the requested size is not too
+// large, or return NULL. You don't need to call these for constructs like
+// malloc(sizeof(foo)), but only if there's picture-dependent size involved
+// somewhere (like: malloc(num_pixels * sizeof(*something))). That's why this
+// safe malloc() borrows the signature from calloc(), pointing at the dangerous
+// underlying multiply involved.
+WEBP_EXTERN void* WebPSafeMalloc(uint64_t nmemb, size_t size);
+// Note that WebPSafeCalloc() expects the second argument type to be 'size_t'
+// in order to favor the "calloc(num_foo, sizeof(foo))" pattern.
+WEBP_EXTERN void* WebPSafeCalloc(uint64_t nmemb, size_t size);
+
+// Companion deallocation function to the above allocations.
+WEBP_EXTERN void WebPSafeFree(void* const ptr);
+
+//------------------------------------------------------------------------------
+// Alignment
+
+#define WEBP_ALIGN_CST 31
+#define WEBP_ALIGN(PTR) (((uintptr_t)(PTR) + WEBP_ALIGN_CST) & \
+ ~(uintptr_t)WEBP_ALIGN_CST)
+
+#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, ptr, sizeof(A));
+ return A;
+}
+
+static WEBP_INLINE int32_t WebPMemToInt32(const uint8_t* const ptr) {
+ return (int32_t)WebPMemToUint32(ptr);
+}
+
+static WEBP_INLINE void WebPUint32ToMem(uint8_t* const ptr, uint32_t val) {
+ memcpy(ptr, &val, sizeof(val));
+}
+
+static WEBP_INLINE void WebPInt32ToMem(uint8_t* const ptr, int val) {
+ WebPUint32ToMem(ptr, (uint32_t)val);
+}
+
+//------------------------------------------------------------------------------
+// Reading/writing data.
+
+// Read 16, 24 or 32 bits stored in little-endian order.
+static WEBP_INLINE int GetLE16(const uint8_t* const data) {
+ return (int)(data[0] << 0) | (data[1] << 8);
+}
+
+static WEBP_INLINE int GetLE24(const uint8_t* const data) {
+ return GetLE16(data) | (data[2] << 16);
+}
+
+static WEBP_INLINE uint32_t GetLE32(const uint8_t* const data) {
+ return GetLE16(data) | ((uint32_t)GetLE16(data + 2) << 16);
+}
+
+// Store 16, 24 or 32 bits in little-endian order.
+static WEBP_INLINE void PutLE16(uint8_t* const data, int val) {
+ assert(val < (1 << 16));
+ data[0] = (val >> 0) & 0xff;
+ data[1] = (val >> 8) & 0xff;
+}
+
+static WEBP_INLINE void PutLE24(uint8_t* const data, int val) {
+ assert(val < (1 << 24));
+ PutLE16(data, val & 0xffff);
+ data[2] = (val >> 16) & 0xff;
+}
+
+static WEBP_INLINE void PutLE32(uint8_t* const data, uint32_t val) {
+ PutLE16(data, (int)(val & 0xffff));
+ PutLE16(data + 2, (int)(val >> 16));
+}
+
+// use GNU builtins where available.
+#if defined(__GNUC__) && \
+ ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4)
+// Returns (int)floor(log2(n)). n must be > 0.
+static WEBP_INLINE int BitsLog2Floor(uint32_t n) {
+ return 31 ^ __builtin_clz(n);
+}
+// counts the number of trailing zero
+static WEBP_INLINE int BitsCtz(uint32_t n) { return __builtin_ctz(n); }
+#elif defined(_MSC_VER) && _MSC_VER > 1310 && \
+ (defined(_M_X64) || defined(_M_IX86))
+#include <intrin.h>
+#pragma intrinsic(_BitScanReverse)
+#pragma intrinsic(_BitScanForward)
+
+static WEBP_INLINE int BitsLog2Floor(uint32_t n) {
+ unsigned long first_set_bit; // NOLINT (runtime/int)
+ _BitScanReverse(&first_set_bit, n);
+ return first_set_bit;
+}
+static WEBP_INLINE int BitsCtz(uint32_t n) {
+ unsigned long first_set_bit; // NOLINT (runtime/int)
+ _BitScanForward(&first_set_bit, n);
+ return first_set_bit;
+}
+#else // default: use the (slow) C-version.
+#define WEBP_HAVE_SLOW_CLZ_CTZ // signal that the Clz/Ctz function are slow
+// Returns 31 ^ clz(n) = log2(n). This is the default C-implementation, either
+// based on table or not. Can be used as fallback if clz() is not available.
+#define WEBP_NEED_LOG_TABLE_8BIT
+extern const uint8_t WebPLogTable8bit[256];
+static WEBP_INLINE int WebPLog2FloorC(uint32_t n) {
+ int log_value = 0;
+ while (n >= 256) {
+ log_value += 8;
+ n >>= 8;
+ }
+ return log_value + WebPLogTable8bit[n];
+}
+
+static WEBP_INLINE int BitsLog2Floor(uint32_t n) { return WebPLog2FloorC(n); }
+
+static WEBP_INLINE int BitsCtz(uint32_t n) {
+ int i;
+ for (i = 0; i < 32; ++i, n >>= 1) {
+ if (n & 1) return i;
+ }
+ return 32;
+}
+
+#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);
+
+//------------------------------------------------------------------------------
+// Unique colors.
+
+// Returns count of unique colors in 'pic', assuming pic->use_argb is true.
+// If the unique color count is more than MAX_PALETTE_SIZE, returns
+// MAX_PALETTE_SIZE+1.
+// If 'palette' is not NULL and number of unique colors is less than or equal to
+// MAX_PALETTE_SIZE, also outputs the actual unique colors into 'palette'.
+// Note: 'palette' is assumed to be an array already allocated with at least
+// MAX_PALETTE_SIZE elements.
+WEBP_EXTERN int WebPGetColorPalette(const struct WebPPicture* const pic,
+ uint32_t* const palette);
+
+//------------------------------------------------------------------------------
+
+#ifdef __cplusplus
+} // extern "C"
+#endif
+
+#endif // WEBP_UTILS_UTILS_H_