diff options
Diffstat (limited to 'drivers/webpold/utils')
| -rw-r--r-- | drivers/webpold/utils/bit_reader.c | 229 | ||||
| -rw-r--r-- | drivers/webpold/utils/bit_reader.h | 198 | ||||
| -rw-r--r-- | drivers/webpold/utils/bit_writer.c | 284 | ||||
| -rw-r--r-- | drivers/webpold/utils/bit_writer.h | 123 | ||||
| -rw-r--r-- | drivers/webpold/utils/color_cache.c | 44 | ||||
| -rw-r--r-- | drivers/webpold/utils/color_cache.h | 68 | ||||
| -rw-r--r-- | drivers/webpold/utils/filters.c | 229 | ||||
| -rw-r--r-- | drivers/webpold/utils/filters.h | 54 | ||||
| -rw-r--r-- | drivers/webpold/utils/huffman.c | 238 | ||||
| -rw-r--r-- | drivers/webpold/utils/huffman.h | 78 | ||||
| -rw-r--r-- | drivers/webpold/utils/huffman_encode.c | 439 | ||||
| -rw-r--r-- | drivers/webpold/utils/huffman_encode.h | 47 | ||||
| -rw-r--r-- | drivers/webpold/utils/quant_levels.c | 154 | ||||
| -rw-r--r-- | drivers/webpold/utils/quant_levels.h | 39 | ||||
| -rw-r--r-- | drivers/webpold/utils/rescaler.c | 152 | ||||
| -rw-r--r-- | drivers/webpold/utils/rescaler.h | 76 | ||||
| -rw-r--r-- | drivers/webpold/utils/thread.c | 247 | ||||
| -rw-r--r-- | drivers/webpold/utils/thread.h | 86 | ||||
| -rw-r--r-- | drivers/webpold/utils/utils.c | 44 | ||||
| -rw-r--r-- | drivers/webpold/utils/utils.h | 44 |
20 files changed, 0 insertions, 2873 deletions
diff --git a/drivers/webpold/utils/bit_reader.c b/drivers/webpold/utils/bit_reader.c deleted file mode 100644 index 1afb1db890..0000000000 --- a/drivers/webpold/utils/bit_reader.c +++ /dev/null @@ -1,229 +0,0 @@ -// Copyright 2010 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Boolean decoder -// -// Author: Skal (pascal.massimino@gmail.com) - -#include "./bit_reader.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#define MK(X) (((bit_t)(X) << (BITS)) | (MASK)) - -//------------------------------------------------------------------------------ -// VP8BitReader - -void VP8InitBitReader(VP8BitReader* const br, - const uint8_t* const start, const uint8_t* const end) { - assert(br != NULL); - assert(start != NULL); - assert(start <= end); - br->range_ = MK(255 - 1); - br->buf_ = start; - br->buf_end_ = end; - br->value_ = 0; - br->missing_ = 8; // to load the very first 8bits - br->eof_ = 0; -} - -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 << kVP8Log2Range[range]) + trailing 1's -const bit_t kVP8NewRange[128] = { - MK(127), MK(127), MK(191), MK(127), MK(159), MK(191), MK(223), MK(127), - MK(143), MK(159), MK(175), MK(191), MK(207), MK(223), MK(239), MK(127), - MK(135), MK(143), MK(151), MK(159), MK(167), MK(175), MK(183), MK(191), - MK(199), MK(207), MK(215), MK(223), MK(231), MK(239), MK(247), MK(127), - MK(131), MK(135), MK(139), MK(143), MK(147), MK(151), MK(155), MK(159), - MK(163), MK(167), MK(171), MK(175), MK(179), MK(183), MK(187), MK(191), - MK(195), MK(199), MK(203), MK(207), MK(211), MK(215), MK(219), MK(223), - MK(227), MK(231), MK(235), MK(239), MK(243), MK(247), MK(251), MK(127), - MK(129), MK(131), MK(133), MK(135), MK(137), MK(139), MK(141), MK(143), - MK(145), MK(147), MK(149), MK(151), MK(153), MK(155), MK(157), MK(159), - MK(161), MK(163), MK(165), MK(167), MK(169), MK(171), MK(173), MK(175), - MK(177), MK(179), MK(181), MK(183), MK(185), MK(187), MK(189), MK(191), - MK(193), MK(195), MK(197), MK(199), MK(201), MK(203), MK(205), MK(207), - MK(209), MK(211), MK(213), MK(215), MK(217), MK(219), MK(221), MK(223), - MK(225), MK(227), MK(229), MK(231), MK(233), MK(235), MK(237), MK(239), - MK(241), MK(243), MK(245), MK(247), MK(249), MK(251), MK(253), MK(127) -}; - -#undef MK - -void VP8LoadFinalBytes(VP8BitReader* const br) { - assert(br != NULL && br->buf_ != NULL); - // Only read 8bits at a time - if (br->buf_ < br->buf_end_) { - br->value_ |= (bit_t)(*br->buf_++) << ((BITS) - 8 + br->missing_); - br->missing_ -= 8; - } else { - br->eof_ = 1; - } -} - -//------------------------------------------------------------------------------ -// Higher-level calls - -uint32_t VP8GetValue(VP8BitReader* const br, int bits) { - uint32_t v = 0; - while (bits-- > 0) { - v |= VP8GetBit(br, 0x80) << bits; - } - return v; -} - -int32_t VP8GetSignedValue(VP8BitReader* const br, int bits) { - const int value = VP8GetValue(br, bits); - return VP8Get(br) ? -value : value; -} - -//------------------------------------------------------------------------------ -// VP8LBitReader - -#define MAX_NUM_BIT_READ 25 - -static const uint32_t kBitMask[MAX_NUM_BIT_READ] = { - 0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, - 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215 -}; - -void VP8LInitBitReader(VP8LBitReader* const br, - const uint8_t* const start, - size_t length) { - size_t i; - assert(br != NULL); - assert(start != NULL); - assert(length < 0xfffffff8u); // can't happen with a RIFF chunk. - - br->buf_ = start; - br->len_ = length; - br->val_ = 0; - br->pos_ = 0; - br->bit_pos_ = 0; - br->eos_ = 0; - br->error_ = 0; - for (i = 0; i < sizeof(br->val_) && i < br->len_; ++i) { - br->val_ |= ((uint64_t)br->buf_[br->pos_]) << (8 * i); - ++br->pos_; - } -} - -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->eos_ = (br->pos_ >= len); - br->buf_ = buf; - br->len_ = len; -} - -static void ShiftBytes(VP8LBitReader* const br) { - while (br->bit_pos_ >= 8 && br->pos_ < br->len_) { - br->val_ >>= 8; - br->val_ |= ((uint64_t)br->buf_[br->pos_]) << 56; - ++br->pos_; - br->bit_pos_ -= 8; - } -} - -void VP8LFillBitWindow(VP8LBitReader* const br) { - if (br->bit_pos_ >= 32) { -#if defined(__x86_64__) || defined(_M_X64) - if (br->pos_ + 8 < br->len_) { - br->val_ >>= 32; - // The expression below needs a little-endian arch to work correctly. - // This gives a large speedup for decoding speed. - br->val_ |= *(const uint64_t *)(br->buf_ + br->pos_) << 32; - br->pos_ += 4; - br->bit_pos_ -= 32; - } else { - // Slow path. - ShiftBytes(br); - } -#else - // Always the slow path. - ShiftBytes(br); -#endif - } - if (br->pos_ == br->len_ && br->bit_pos_ == 64) { - br->eos_ = 1; - } -} - -uint32_t VP8LReadOneBit(VP8LBitReader* const br) { - const uint32_t val = (br->val_ >> br->bit_pos_) & 1; - // Flag an error at end_of_stream. - if (!br->eos_) { - ++br->bit_pos_; - if (br->bit_pos_ >= 32) { - ShiftBytes(br); - } - // After this last bit is read, check if eos needs to be flagged. - if (br->pos_ == br->len_ && br->bit_pos_ == 64) { - br->eos_ = 1; - } - } else { - br->error_ = 1; - } - return val; -} - -uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) { - uint32_t val = 0; - assert(n_bits >= 0); - // Flag an error if end_of_stream or n_bits is more than allowed limit. - if (!br->eos_ && n_bits < MAX_NUM_BIT_READ) { - // If this read is going to cross the read buffer, set the eos flag. - if (br->pos_ == br->len_) { - if ((br->bit_pos_ + n_bits) >= 64) { - br->eos_ = 1; - if ((br->bit_pos_ + n_bits) > 64) return val; - } - } - val = (br->val_ >> br->bit_pos_) & kBitMask[n_bits]; - br->bit_pos_ += n_bits; - if (br->bit_pos_ >= 40) { - if (br->pos_ + 5 < br->len_) { - br->val_ >>= 40; - br->val_ |= - (((uint64_t)br->buf_[br->pos_ + 0]) << 24) | - (((uint64_t)br->buf_[br->pos_ + 1]) << 32) | - (((uint64_t)br->buf_[br->pos_ + 2]) << 40) | - (((uint64_t)br->buf_[br->pos_ + 3]) << 48) | - (((uint64_t)br->buf_[br->pos_ + 4]) << 56); - br->pos_ += 5; - br->bit_pos_ -= 40; - } - if (br->bit_pos_ >= 8) { - ShiftBytes(br); - } - } - } else { - br->error_ = 1; - } - return val; -} - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/bit_reader.h b/drivers/webpold/utils/bit_reader.h deleted file mode 100644 index 43cd948fd4..0000000000 --- a/drivers/webpold/utils/bit_reader.h +++ /dev/null @@ -1,198 +0,0 @@ -// -// Copyright 2010 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Boolean decoder -// -// Author: Skal (pascal.massimino@gmail.com) -// Vikas Arora (vikaas.arora@gmail.com) - -#ifndef WEBP_UTILS_BIT_READER_H_ -#define WEBP_UTILS_BIT_READER_H_ - -#include <assert.h> -#ifdef _MSC_VER -#include <stdlib.h> // _byteswap_ulong -#endif -#include <string.h> // For memcpy -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#define BITS 32 // can be 32, 16 or 8 -#define MASK ((((bit_t)1) << (BITS)) - 1) -#if (BITS == 32) -typedef uint64_t bit_t; // natural register type -typedef uint32_t lbit_t; // natural type for memory I/O -#elif (BITS == 16) -typedef uint32_t bit_t; -typedef uint16_t lbit_t; -#else -typedef uint32_t bit_t; -typedef uint8_t lbit_t; -#endif - -//------------------------------------------------------------------------------ -// Bitreader and code-tree reader - -typedef struct VP8BitReader VP8BitReader; -struct VP8BitReader { - const uint8_t* buf_; // next byte to be read - const uint8_t* buf_end_; // end of read buffer - int eof_; // true if input is exhausted - - // boolean decoder - bit_t range_; // current range minus 1. In [127, 254] interval. - bit_t value_; // current value - int missing_; // number of missing bits in value_ (8bit) -}; - -// Initialize the bit reader and the boolean decoder. -void VP8InitBitReader(VP8BitReader* const br, - const uint8_t* const start, const uint8_t* const end); - -// return the next value made of 'num_bits' bits -uint32_t VP8GetValue(VP8BitReader* const br, int num_bits); -static WEBP_INLINE uint32_t VP8Get(VP8BitReader* const br) { - return VP8GetValue(br, 1); -} - -// return the next value with sign-extension. -int32_t VP8GetSignedValue(VP8BitReader* const br, int num_bits); - -// Read a bit with proba 'prob'. Speed-critical function! -extern const uint8_t kVP8Log2Range[128]; -extern const bit_t kVP8NewRange[128]; - -void VP8LoadFinalBytes(VP8BitReader* const br); // special case for the tail - -static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) { - assert(br && br->buf_); - // Read 'BITS' bits at a time if possible. - if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) { - // convert memory type to register type (with some zero'ing!) - bit_t bits; - lbit_t in_bits = *(lbit_t*)br->buf_; - br->buf_ += (BITS) >> 3; -#if !defined(__BIG_ENDIAN__) -#if (BITS == 32) -#if defined(__i386__) || defined(__x86_64__) - __asm__ volatile("bswap %k0" : "=r"(in_bits) : "0"(in_bits)); - bits = (bit_t)in_bits; // 32b -> 64b zero-extension -#elif defined(_MSC_VER) - bits = _byteswap_ulong(in_bits); -#else - bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00) - | ((in_bits << 8) & 0xff0000) | (in_bits << 24); -#endif // x86 -#elif (BITS == 16) - // gcc will recognize a 'rorw $8, ...' here: - bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8); -#endif -#else // LITTLE_ENDIAN - bits = (bit_t)in_bits; -#endif - br->value_ |= bits << br->missing_; - br->missing_ -= (BITS); - } else { - VP8LoadFinalBytes(br); // no need to be inlined - } -} - -static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, bit_t split) { - const bit_t value_split = split | (MASK); - if (br->missing_ > 0) { // Make sure we have a least BITS bits in 'value_' - VP8LoadNewBytes(br); - } - if (br->value_ > value_split) { - br->range_ -= value_split + 1; - br->value_ -= value_split + 1; - return 1; - } else { - br->range_ = value_split; - return 0; - } -} - -static WEBP_INLINE void VP8Shift(VP8BitReader* const br) { - // range_ is in [0..127] interval here. - const int idx = br->range_ >> (BITS); - const int shift = kVP8Log2Range[idx]; - br->range_ = kVP8NewRange[idx]; - br->value_ <<= shift; - br->missing_ += shift; -} - -static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) { - // It's important to avoid generating a 64bit x 64bit multiply here. - // We just need an 8b x 8b after all. - const bit_t split = - (bit_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8); - const int bit = VP8BitUpdate(br, split); - if (br->range_ <= (((bit_t)0x7e << (BITS)) | (MASK))) { - VP8Shift(br); - } - return bit; -} - -static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) { - const bit_t split = (br->range_ >> 1); - const int bit = VP8BitUpdate(br, split); - VP8Shift(br); - return bit ? -v : v; -} - - -// ----------------------------------------------------------------------------- -// Bitreader - -typedef struct { - uint64_t val_; - const uint8_t* buf_; - size_t len_; - size_t pos_; - int bit_pos_; - int eos_; - int error_; -} 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 allowed limit. -// Flags eos if this read attempt is going to cross the read buffer. -uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits); - -// Reads one bit from Read Buffer. Flags an error in case end_of_stream. -// Flags eos after reading last bit from the buffer. -uint32_t VP8LReadOneBit(VP8LBitReader* const br); - -// VP8LReadOneBitUnsafe is faster than VP8LReadOneBit, but it can be called only -// 32 times after the last VP8LFillBitWindow. Any subsequent calls -// (without VP8LFillBitWindow) will return invalid data. -static WEBP_INLINE uint32_t VP8LReadOneBitUnsafe(VP8LBitReader* const br) { - const uint32_t val = (br->val_ >> br->bit_pos_) & 1; - ++br->bit_pos_; - return val; -} - -// Advances the Read buffer by 4 bytes to make room for reading next 32 bits. -void VP8LFillBitWindow(VP8LBitReader* const br); - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif /* WEBP_UTILS_BIT_READER_H_ */ diff --git a/drivers/webpold/utils/bit_writer.c b/drivers/webpold/utils/bit_writer.c deleted file mode 100644 index 671159cacd..0000000000 --- a/drivers/webpold/utils/bit_writer.c +++ /dev/null @@ -1,284 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// 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 "./bit_writer.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -//------------------------------------------------------------------------------ -// 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*)malloc(new_size); - if (new_buf == NULL) { - bw->error_ = 1; - return 0; - } - memcpy(new_buf, bw->buf_, bw->pos_); - free(bw->buf_); - bw->buf_ = new_buf; - bw->max_pos_ = new_size; - return 1; -} - -static void kFlush(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; - 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) kFlush(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) kFlush(bw); - } - return bit; -} - -void VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits) { - int mask; - for (mask = 1 << (nb_bits - 1); mask; mask >>= 1) - VP8PutBitUniform(bw, value & mask); -} - -void VP8PutSignedValue(VP8BitWriter* const bw, int value, int nb_bits) { - if (!VP8PutBitUniform(bw, value != 0)) - return; - if (value < 0) { - VP8PutValue(bw, ((-value) << 1) | 1, nb_bits + 1); - } else { - VP8PutValue(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) { - VP8PutValue(bw, 0, 9 - bw->nb_bits_); - bw->nb_bits_ = 0; // pad with zeroes - kFlush(bw); - return bw->buf_; -} - -int VP8BitWriterAppend(VP8BitWriter* const bw, - const uint8_t* data, size_t size) { - assert(data); - if (bw->nb_bits_ != -8) return 0; // kFlush() 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) { - free(bw->buf_); - memset(bw, 0, sizeof(*bw)); - } -} - -//------------------------------------------------------------------------------ -// VP8LBitWriter - -// 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 current_size = VP8LBitWriterNumBytes(bw); - 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 (bw->max_bytes_ > 0 && size_required <= bw->max_bytes_) return 1; - allocated_size = (3 * bw->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*)malloc(allocated_size); - if (allocated_buf == NULL) { - bw->error_ = 1; - return 0; - } - memcpy(allocated_buf, bw->buf_, current_size); - free(bw->buf_); - bw->buf_ = allocated_buf; - bw->max_bytes_ = allocated_size; - memset(allocated_buf + current_size, 0, allocated_size - current_size); - return 1; -} - -int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size) { - memset(bw, 0, sizeof(*bw)); - return VP8LBitWriterResize(bw, expected_size); -} - -void VP8LBitWriterDestroy(VP8LBitWriter* const bw) { - if (bw != NULL) { - free(bw->buf_); - memset(bw, 0, sizeof(*bw)); - } -} - -void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits) { - if (n_bits < 1) return; -#if !defined(__BIG_ENDIAN__) - // Technically, this branch of the code can write up to 25 bits at a time, - // but in prefix encoding, the maximum number of bits written is 18 at a time. - { - uint8_t* const p = &bw->buf_[bw->bit_pos_ >> 3]; - uint32_t v = *(const uint32_t*)p; - v |= bits << (bw->bit_pos_ & 7); - *(uint32_t*)p = v; - bw->bit_pos_ += n_bits; - } -#else // BIG_ENDIAN - { - uint8_t* p = &bw->buf_[bw->bit_pos_ >> 3]; - const int bits_reserved_in_first_byte = bw->bit_pos_ & 7; - const int bits_left_to_write = n_bits - 8 + bits_reserved_in_first_byte; - // implicit & 0xff is assumed for uint8_t arithmetics - *p++ |= bits << bits_reserved_in_first_byte; - bits >>= 8 - bits_reserved_in_first_byte; - if (bits_left_to_write >= 1) { - *p++ = bits; - bits >>= 8; - if (bits_left_to_write >= 9) { - *p++ = bits; - bits >>= 8; - } - } - assert(n_bits <= 25); - *p = bits; - bw->bit_pos_ += n_bits; - } -#endif - if ((bw->bit_pos_ >> 3) > (bw->max_bytes_ - 8)) { - const uint64_t extra_size = 32768ULL + bw->max_bytes_; - if (extra_size != (size_t)extra_size || - !VP8LBitWriterResize(bw, (size_t)extra_size)) { - bw->bit_pos_ = 0; - bw->error_ = 1; - } - } -} - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/bit_writer.h b/drivers/webpold/utils/bit_writer.h deleted file mode 100644 index 57f39b11b1..0000000000 --- a/drivers/webpold/utils/bit_writer.h +++ /dev/null @@ -1,123 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Bit writing and boolean coder -// -// Author: Skal (pascal.massimino@gmail.com) - -#ifndef WEBP_UTILS_BIT_WRITER_H_ -#define WEBP_UTILS_BIT_WRITER_H_ - -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -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 VP8PutValue(VP8BitWriter* const bw, int value, int nb_bits); -void VP8PutSignedValue(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) { - return (uint64_t)(bw->pos_ + bw->run_) * 8 + 8 + bw->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 -// TODO(vikasa): VP8LBitWriter is copied as-is from lossless code. There's scope -// of re-using VP8BitWriter. Will evaluate once basic lossless encoder is -// implemented. - -typedef struct { - uint8_t* buf_; - size_t bit_pos_; - size_t max_bytes_; - - // After all bits are written, 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(VP8LBitWriter* const bw) { - return (bw->bit_pos_ + 7) >> 3; -} - -static WEBP_INLINE uint8_t* VP8LBitWriterFinish(VP8LBitWriter* const bw) { - return bw->buf_; -} - -// Returns 0 in case of memory allocation error. -int VP8LBitWriterInit(VP8LBitWriter* const bw, size_t expected_size); - -void VP8LBitWriterDestroy(VP8LBitWriter* const bw); - -// This function writes bits into bytes in increasing addresses, and within -// a byte least-significant-bit first. -// -// The function can write up to 16 bits in one go with WriteBits -// Example: let's assume that 3 bits (Rs below) have been written already: -// -// BYTE-0 BYTE+1 BYTE+2 -// -// 0000 0RRR 0000 0000 0000 0000 -// -// Now, we could write 5 or less bits in MSB by just sifting by 3 -// and OR'ing to BYTE-0. -// -// For n bits, we take the last 5 bytes, OR that with high bits in BYTE-0, -// and locate the rest in BYTE+1 and BYTE+2. -// -// VP8LBitWriter's error_ flag is set in case of memory allocation error. -void VP8LWriteBits(VP8LBitWriter* const bw, int n_bits, uint32_t bits); - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif /* WEBP_UTILS_BIT_WRITER_H_ */ diff --git a/drivers/webpold/utils/color_cache.c b/drivers/webpold/utils/color_cache.c deleted file mode 100644 index 560f81db10..0000000000 --- a/drivers/webpold/utils/color_cache.c +++ /dev/null @@ -1,44 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Color Cache for WebP Lossless -// -// Author: Jyrki Alakuijala (jyrki@google.com) - -#include <assert.h> -#include <stdlib.h> -#include "./color_cache.h" -#include "../utils/utils.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -//------------------------------------------------------------------------------ -// VP8LColorCache. - -int VP8LColorCacheInit(VP8LColorCache* const cc, int hash_bits) { - const int hash_size = 1 << hash_bits; - assert(cc != NULL); - assert(hash_bits > 0); - cc->colors_ = (uint32_t*)WebPSafeCalloc((uint64_t)hash_size, - sizeof(*cc->colors_)); - if (cc->colors_ == NULL) return 0; - cc->hash_shift_ = 32 - hash_bits; - return 1; -} - -void VP8LColorCacheClear(VP8LColorCache* const cc) { - if (cc != NULL) { - free(cc->colors_); - cc->colors_ = NULL; - } -} - -#if defined(__cplusplus) || defined(c_plusplus) -} -#endif diff --git a/drivers/webpold/utils/color_cache.h b/drivers/webpold/utils/color_cache.h deleted file mode 100644 index da5e260195..0000000000 --- a/drivers/webpold/utils/color_cache.h +++ /dev/null @@ -1,68 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Color Cache for WebP Lossless -// -// Authors: Jyrki Alakuijala (jyrki@google.com) -// Urvang Joshi (urvang@google.com) - -#ifndef WEBP_UTILS_COLOR_CACHE_H_ -#define WEBP_UTILS_COLOR_CACHE_H_ - -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -// Main color cache struct. -typedef struct { - uint32_t *colors_; // color entries - int hash_shift_; // Hash shift: 32 - hash_bits. -} VP8LColorCache; - -static const uint32_t kHashMul = 0x1e35a7bd; - -static WEBP_INLINE uint32_t VP8LColorCacheLookup( - const VP8LColorCache* const cc, uint32_t key) { - assert(key <= (~0U >> cc->hash_shift_)); - return cc->colors_[key]; -} - -static WEBP_INLINE void VP8LColorCacheInsert(const VP8LColorCache* const cc, - uint32_t argb) { - const uint32_t key = (kHashMul * argb) >> cc->hash_shift_; - cc->colors_[key] = argb; -} - -static WEBP_INLINE int VP8LColorCacheGetIndex(const VP8LColorCache* const cc, - uint32_t argb) { - return (kHashMul * argb) >> cc->hash_shift_; -} - -static WEBP_INLINE int VP8LColorCacheContains(const VP8LColorCache* const cc, - uint32_t argb) { - const uint32_t key = (kHashMul * argb) >> cc->hash_shift_; - return cc->colors_[key] == argb; -} - -//------------------------------------------------------------------------------ - -// 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); - -// Delete the memory associated to color cache. -void VP8LColorCacheClear(VP8LColorCache* const color_cache); - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} -#endif - -#endif // WEBP_UTILS_COLOR_CACHE_H_ diff --git a/drivers/webpold/utils/filters.c b/drivers/webpold/utils/filters.c deleted file mode 100644 index 08f52a3d20..0000000000 --- a/drivers/webpold/utils/filters.c +++ /dev/null @@ -1,229 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Spatial prediction using various filters -// -// Author: Urvang (urvang@google.com) - -#include "./filters.h" -#include <assert.h> -#include <stdlib.h> -#include <string.h> - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -//------------------------------------------------------------------------------ -// Helpful macro. - -# define SANITY_CHECK(in, out) \ - assert(in != NULL); \ - assert(out != NULL); \ - assert(width > 0); \ - assert(height > 0); \ - assert(bpp > 0); \ - assert(stride >= width * bpp); - -static WEBP_INLINE void PredictLine(const uint8_t* src, const uint8_t* pred, - uint8_t* dst, int length, int inverse) { - int i; - if (inverse) { - for (i = 0; i < length; ++i) dst[i] = src[i] + pred[i]; - } else { - for (i = 0; i < length; ++i) dst[i] = src[i] - pred[i]; - } -} - -//------------------------------------------------------------------------------ -// Horizontal filter. - -static WEBP_INLINE void DoHorizontalFilter(const uint8_t* in, - int width, int height, int bpp, int stride, int inverse, uint8_t* out) { - int h; - const uint8_t* preds = (inverse ? out : in); - SANITY_CHECK(in, out); - - // Filter line-by-line. - for (h = 0; h < height; ++h) { - // Leftmost pixel is predicted from above (except for topmost scanline). - if (h == 0) { - memcpy((void*)out, (const void*)in, bpp); - } else { - PredictLine(in, preds - stride, out, bpp, inverse); - } - PredictLine(in + bpp, preds, out + bpp, bpp * (width - 1), inverse); - preds += stride; - in += stride; - out += stride; - } -} - -static void HorizontalFilter(const uint8_t* data, int width, int height, - int bpp, int stride, uint8_t* filtered_data) { - DoHorizontalFilter(data, width, height, bpp, stride, 0, filtered_data); -} - -static void HorizontalUnfilter(const uint8_t* data, int width, int height, - int bpp, int stride, uint8_t* recon_data) { - DoHorizontalFilter(data, width, height, bpp, stride, 1, recon_data); -} - -//------------------------------------------------------------------------------ -// Vertical filter. - -static WEBP_INLINE void DoVerticalFilter(const uint8_t* in, - int width, int height, int bpp, int stride, int inverse, uint8_t* out) { - int h; - const uint8_t* preds = (inverse ? out : in); - SANITY_CHECK(in, out); - - // Very first top-left pixel is copied. - memcpy((void*)out, (const void*)in, bpp); - // Rest of top scan-line is left-predicted. - PredictLine(in + bpp, preds, out + bpp, bpp * (width - 1), inverse); - - // Filter line-by-line. - for (h = 1; h < height; ++h) { - in += stride; - out += stride; - PredictLine(in, preds, out, bpp * width, inverse); - preds += stride; - } -} - -static void VerticalFilter(const uint8_t* data, int width, int height, - int bpp, int stride, uint8_t* filtered_data) { - DoVerticalFilter(data, width, height, bpp, stride, 0, filtered_data); -} - -static void VerticalUnfilter(const uint8_t* data, int width, int height, - int bpp, int stride, uint8_t* recon_data) { - DoVerticalFilter(data, width, height, bpp, stride, 1, recon_data); -} - -//------------------------------------------------------------------------------ -// Gradient filter. - -static WEBP_INLINE int GradientPredictor(uint8_t a, uint8_t b, uint8_t c) { - const int g = a + b - c; - return (g < 0) ? 0 : (g > 255) ? 255 : g; -} - -static WEBP_INLINE -void DoGradientFilter(const uint8_t* in, int width, int height, - int bpp, int stride, int inverse, uint8_t* out) { - const uint8_t* preds = (inverse ? out : in); - int h; - SANITY_CHECK(in, out); - - // left prediction for top scan-line - memcpy((void*)out, (const void*)in, bpp); - PredictLine(in + bpp, preds, out + bpp, bpp * (width - 1), inverse); - - // Filter line-by-line. - for (h = 1; h < height; ++h) { - int w; - preds += stride; - in += stride; - out += stride; - // leftmost pixel: predict from above. - PredictLine(in, preds - stride, out, bpp, inverse); - for (w = bpp; w < width * bpp; ++w) { - const int pred = GradientPredictor(preds[w - bpp], - preds[w - stride], - preds[w - stride - bpp]); - out[w] = in[w] + (inverse ? pred : -pred); - } - } -} - -static void GradientFilter(const uint8_t* data, int width, int height, - int bpp, int stride, uint8_t* filtered_data) { - DoGradientFilter(data, width, height, bpp, stride, 0, filtered_data); -} - -static void GradientUnfilter(const uint8_t* data, int width, int height, - int bpp, int stride, uint8_t* recon_data) { - DoGradientFilter(data, width, height, bpp, stride, 1, recon_data); -} - -#undef SANITY_CHECK - -// ----------------------------------------------------------------------------- -// Quick estimate of a potentially interesting filter mode to try, in addition -// to the default NONE. - -#define SMAX 16 -#define SDIFF(a, b) (abs((a) - (b)) >> 4) // Scoring diff, in [0..SMAX) - -WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, - int width, int height, int stride) { - 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; - } - } - { - WEBP_FILTER_TYPE filter, 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 = filter; - } - } - return best_filter; - } -} - -#undef SMAX -#undef SDIFF - -//------------------------------------------------------------------------------ - -const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST] = { - NULL, // WEBP_FILTER_NONE - HorizontalFilter, // WEBP_FILTER_HORIZONTAL - VerticalFilter, // WEBP_FILTER_VERTICAL - GradientFilter // WEBP_FILTER_GRADIENT -}; - -const WebPFilterFunc WebPUnfilters[WEBP_FILTER_LAST] = { - NULL, // WEBP_FILTER_NONE - HorizontalUnfilter, // WEBP_FILTER_HORIZONTAL - VerticalUnfilter, // WEBP_FILTER_VERTICAL - GradientUnfilter // WEBP_FILTER_GRADIENT -}; - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/filters.h b/drivers/webpold/utils/filters.h deleted file mode 100644 index db886be29a..0000000000 --- a/drivers/webpold/utils/filters.h +++ /dev/null @@ -1,54 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Spatial prediction using various filters -// -// Author: Urvang (urvang@google.com) - -#ifndef WEBP_UTILS_FILTERS_H_ -#define WEBP_UTILS_FILTERS_H_ - -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -// Filters. -typedef enum { - WEBP_FILTER_NONE = 0, - WEBP_FILTER_HORIZONTAL, - WEBP_FILTER_VERTICAL, - WEBP_FILTER_GRADIENT, - WEBP_FILTER_LAST = WEBP_FILTER_GRADIENT + 1, // end marker - WEBP_FILTER_BEST, - WEBP_FILTER_FAST -} WEBP_FILTER_TYPE; - -typedef void (*WebPFilterFunc)(const uint8_t* in, int width, int height, - int bpp, int stride, uint8_t* out); - -// Filter the given data using the given predictor. -// 'in' corresponds to a 2-dimensional pixel array of size (stride * height) -// in raster order. -// 'bpp' is number of bytes per pixel, and -// 'stride' is number of bytes per scan line (with possible padding). -// 'out' should be pre-allocated. -extern const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST]; - -// Reconstruct the original data from the given filtered data. -extern const WebPFilterFunc WebPUnfilters[WEBP_FILTER_LAST]; - -// Fast estimate of a potentially good filter. -extern WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, - int width, int height, int stride); - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif /* WEBP_UTILS_FILTERS_H_ */ diff --git a/drivers/webpold/utils/huffman.c b/drivers/webpold/utils/huffman.c deleted file mode 100644 index 1cc1cfd355..0000000000 --- a/drivers/webpold/utils/huffman.c +++ /dev/null @@ -1,238 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Utilities for building and looking up Huffman trees. -// -// Author: Urvang Joshi (urvang@google.com) - -#include <assert.h> -#include <stdlib.h> -#include "./huffman.h" -#include "../utils/utils.h" -#include "../format_constants.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#define NON_EXISTENT_SYMBOL (-1) - -static void TreeNodeInit(HuffmanTreeNode* const node) { - node->children_ = -1; // means: 'unassigned so far' -} - -static int NodeIsEmpty(const HuffmanTreeNode* const node) { - return (node->children_ < 0); -} - -static int IsFull(const HuffmanTree* const tree) { - return (tree->num_nodes_ == tree->max_nodes_); -} - -static void AssignChildren(HuffmanTree* const tree, - HuffmanTreeNode* const node) { - HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_; - node->children_ = (int)(children - node); - assert(children - node == (int)(children - node)); - tree->num_nodes_ += 2; - TreeNodeInit(children + 0); - TreeNodeInit(children + 1); -} - -static int TreeInit(HuffmanTree* const tree, int num_leaves) { - assert(tree != NULL); - if (num_leaves == 0) return 0; - // We allocate maximum possible nodes in the tree at once. - // Note that a Huffman tree is a full binary tree; and in a full binary tree - // with L leaves, the total number of nodes N = 2 * L - 1. - tree->max_nodes_ = 2 * num_leaves - 1; - tree->root_ = (HuffmanTreeNode*)WebPSafeMalloc((uint64_t)tree->max_nodes_, - sizeof(*tree->root_)); - if (tree->root_ == NULL) return 0; - TreeNodeInit(tree->root_); // Initialize root. - tree->num_nodes_ = 1; - return 1; -} - -void HuffmanTreeRelease(HuffmanTree* const tree) { - if (tree != NULL) { - free(tree->root_); - tree->root_ = NULL; - tree->max_nodes_ = 0; - tree->num_nodes_ = 0; - } -} - -int HuffmanCodeLengthsToCodes(const int* const code_lengths, - int code_lengths_size, int* const huff_codes) { - int symbol; - int code_len; - int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; - int curr_code; - int next_codes[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; - int max_code_length = 0; - - assert(code_lengths != NULL); - assert(code_lengths_size > 0); - assert(huff_codes != NULL); - - // Calculate max code length. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - if (code_lengths[symbol] > max_code_length) { - max_code_length = code_lengths[symbol]; - } - } - if (max_code_length > MAX_ALLOWED_CODE_LENGTH) return 0; - - // Calculate code length histogram. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - ++code_length_hist[code_lengths[symbol]]; - } - code_length_hist[0] = 0; - - // Calculate the initial values of 'next_codes' for each code length. - // next_codes[code_len] denotes the code to be assigned to the next symbol - // of code length 'code_len'. - curr_code = 0; - next_codes[0] = -1; // Unused, as code length = 0 implies code doesn't exist. - for (code_len = 1; code_len <= max_code_length; ++code_len) { - curr_code = (curr_code + code_length_hist[code_len - 1]) << 1; - next_codes[code_len] = curr_code; - } - - // Get symbols. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - if (code_lengths[symbol] > 0) { - huff_codes[symbol] = next_codes[code_lengths[symbol]]++; - } else { - huff_codes[symbol] = NON_EXISTENT_SYMBOL; - } - } - return 1; -} - -static int TreeAddSymbol(HuffmanTree* const tree, - int symbol, int code, int code_length) { - HuffmanTreeNode* node = tree->root_; - const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_; - while (code_length-- > 0) { - if (node >= max_node) { - return 0; - } - if (NodeIsEmpty(node)) { - if (IsFull(tree)) return 0; // error: too many symbols. - AssignChildren(tree, node); - } else if (HuffmanTreeNodeIsLeaf(node)) { - return 0; // leaf is already occupied. - } - node += node->children_ + ((code >> code_length) & 1); - } - if (NodeIsEmpty(node)) { - node->children_ = 0; // turn newly created node into a leaf. - } else if (!HuffmanTreeNodeIsLeaf(node)) { - return 0; // trying to assign a symbol to already used code. - } - node->symbol_ = symbol; // Add symbol in this node. - return 1; -} - -int HuffmanTreeBuildImplicit(HuffmanTree* const tree, - const int* const code_lengths, - int code_lengths_size) { - int symbol; - int num_symbols = 0; - int root_symbol = 0; - - assert(tree != NULL); - assert(code_lengths != NULL); - - // Find out number of symbols and the root symbol. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - if (code_lengths[symbol] > 0) { - // Note: code length = 0 indicates non-existent symbol. - ++num_symbols; - root_symbol = symbol; - } - } - - // Initialize the tree. Will fail for num_symbols = 0 - if (!TreeInit(tree, num_symbols)) return 0; - - // Build tree. - if (num_symbols == 1) { // Trivial case. - const int max_symbol = code_lengths_size; - if (root_symbol < 0 || root_symbol >= max_symbol) { - HuffmanTreeRelease(tree); - return 0; - } - return TreeAddSymbol(tree, root_symbol, 0, 0); - } else { // Normal case. - int ok = 0; - - // Get Huffman codes from the code lengths. - int* const codes = - (int*)WebPSafeMalloc((uint64_t)code_lengths_size, sizeof(*codes)); - if (codes == NULL) goto End; - - if (!HuffmanCodeLengthsToCodes(code_lengths, code_lengths_size, codes)) { - goto End; - } - - // Add symbols one-by-one. - for (symbol = 0; symbol < code_lengths_size; ++symbol) { - if (code_lengths[symbol] > 0) { - if (!TreeAddSymbol(tree, symbol, codes[symbol], code_lengths[symbol])) { - goto End; - } - } - } - ok = 1; - End: - free(codes); - ok = ok && IsFull(tree); - if (!ok) HuffmanTreeRelease(tree); - return ok; - } -} - -int HuffmanTreeBuildExplicit(HuffmanTree* const tree, - const int* const code_lengths, - const int* const codes, - const int* const symbols, int max_symbol, - int num_symbols) { - int ok = 0; - int i; - - assert(tree != NULL); - assert(code_lengths != NULL); - assert(codes != NULL); - assert(symbols != NULL); - - // Initialize the tree. Will fail if num_symbols = 0. - if (!TreeInit(tree, num_symbols)) return 0; - - // Add symbols one-by-one. - for (i = 0; i < num_symbols; ++i) { - if (codes[i] != NON_EXISTENT_SYMBOL) { - if (symbols[i] < 0 || symbols[i] >= max_symbol) { - goto End; - } - if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) { - goto End; - } - } - } - ok = 1; - End: - ok = ok && IsFull(tree); - if (!ok) HuffmanTreeRelease(tree); - return ok; -} - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/huffman.h b/drivers/webpold/utils/huffman.h deleted file mode 100644 index f16447e649..0000000000 --- a/drivers/webpold/utils/huffman.h +++ /dev/null @@ -1,78 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Utilities for building and looking up Huffman trees. -// -// Author: Urvang Joshi (urvang@google.com) - -#ifndef WEBP_UTILS_HUFFMAN_H_ -#define WEBP_UTILS_HUFFMAN_H_ - -#include <assert.h> -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -// A node of a Huffman tree. -typedef struct { - int symbol_; - int children_; // delta offset to both children (contiguous) or 0 if leaf. -} HuffmanTreeNode; - -// Huffman Tree. -typedef struct HuffmanTree HuffmanTree; -struct HuffmanTree { - HuffmanTreeNode* root_; // all the nodes, starting at root. - int max_nodes_; // max number of nodes - int num_nodes_; // number of currently occupied nodes -}; - -// Returns true if the given node is a leaf of the Huffman tree. -static WEBP_INLINE int HuffmanTreeNodeIsLeaf( - const HuffmanTreeNode* const node) { - return (node->children_ == 0); -} - -// Go down one level. Most critical function. 'right_child' must be 0 or 1. -static WEBP_INLINE const HuffmanTreeNode* HuffmanTreeNextNode( - const HuffmanTreeNode* node, int right_child) { - return node + node->children_ + right_child; -} - -// Releases the nodes of the Huffman tree. -// Note: It does NOT free 'tree' itself. -void HuffmanTreeRelease(HuffmanTree* const tree); - -// Builds Huffman tree assuming code lengths are implicitly in symbol order. -// Returns false in case of error (invalid tree or memory error). -int HuffmanTreeBuildImplicit(HuffmanTree* const tree, - const int* const code_lengths, - int code_lengths_size); - -// Build a Huffman tree with explicitly given lists of code lengths, codes -// and symbols. Verifies that all symbols added are smaller than max_symbol. -// Returns false in case of an invalid symbol, invalid tree or memory error. -int HuffmanTreeBuildExplicit(HuffmanTree* const tree, - const int* const code_lengths, - const int* const codes, - const int* const symbols, int max_symbol, - int num_symbols); - -// Utility: converts Huffman code lengths to corresponding Huffman codes. -// 'huff_codes' should be pre-allocated. -// Returns false in case of error (memory allocation, invalid codes). -int HuffmanCodeLengthsToCodes(const int* const code_lengths, - int code_lengths_size, int* const huff_codes); - - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif // WEBP_UTILS_HUFFMAN_H_ diff --git a/drivers/webpold/utils/huffman_encode.c b/drivers/webpold/utils/huffman_encode.c deleted file mode 100644 index e172b10a85..0000000000 --- a/drivers/webpold/utils/huffman_encode.c +++ /dev/null @@ -1,439 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Author: Jyrki Alakuijala (jyrki@google.com) -// -// Entropy encoding (Huffman) for webp lossless. - -#include <assert.h> -#include <stdlib.h> -#include <string.h> -#include "./huffman_encode.h" -#include "../utils/utils.h" -#include "../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 -// Hufmann tree compression, especially its RLE-part, give smaller output. -static int OptimizeHuffmanForRle(int length, int* const counts) { - uint8_t* good_for_rle; - // 1) Let's make the Huffman code more compatible with rle encoding. - int i; - for (; length >= 0; --length) { - if (length == 0) { - return 1; // 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. - good_for_rle = (uint8_t*)calloc(length, 1); - if (good_for_rle == NULL) { - return 0; - } - { - // 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. - int 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. - { - int stride = 0; - int limit = counts[0]; - int 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)) { - int k; - // The stride must end, collapse what we have, if we have enough (4). - int 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; - } - } - } - } - free(good_for_rle); - return 1; -} - -typedef struct { - int total_count_; - int value_; - int pool_index_left_; - int pool_index_right_; -} HuffmanTree; - -// 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 { - if (t1->value_ < t2->value_) { - return -1; - } - if (t1->value_ > t2->value_) { - return 1; - } - return 0; - } -} - -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 http://en.wikipedia.org/wiki/Huffman_coding -static int GenerateOptimalTree(const int* const histogram, int histogram_size, - int tree_depth_limit, - uint8_t* const bit_depths) { - int count_min; - HuffmanTree* tree_pool; - HuffmanTree* tree; - int tree_size_orig = 0; - int i; - - for (i = 0; i < histogram_size; ++i) { - if (histogram[i] != 0) { - ++tree_size_orig; - } - } - - // 3 * tree_size is enough to cover all the nodes representing a - // population and all the inserted nodes combining two existing nodes. - // The tree pool needs 2 * (tree_size_orig - 1) entities, and the - // tree needs exactly tree_size_orig entities. - tree = (HuffmanTree*)WebPSafeMalloc(3ULL * tree_size_orig, sizeof(*tree)); - if (tree == NULL) return 0; - 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 int 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. - int 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; - } - } - } - free(tree); - return 1; -} - -// ----------------------------------------------------------------------------- -// 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 - -int VP8LCreateHuffmanTree(int* const histogram, int tree_depth_limit, - HuffmanTreeCode* const tree) { - const int num_symbols = tree->num_symbols; - if (!OptimizeHuffmanForRle(num_symbols, histogram)) { - return 0; - } - if (!GenerateOptimalTree(histogram, num_symbols, - tree_depth_limit, tree->code_lengths)) { - return 0; - } - // Create the actual bit codes for the bit lengths. - ConvertBitDepthsToSymbols(tree); - return 1; -} diff --git a/drivers/webpold/utils/huffman_encode.h b/drivers/webpold/utils/huffman_encode.h deleted file mode 100644 index 7f4aedc102..0000000000 --- a/drivers/webpold/utils/huffman_encode.h +++ /dev/null @@ -1,47 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Author: Jyrki Alakuijala (jyrki@google.com) -// -// Entropy encoding (Huffman) for webp lossless - -#ifndef WEBP_UTILS_HUFFMAN_ENCODE_H_ -#define WEBP_UTILS_HUFFMAN_ENCODE_H_ - -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -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; - -// 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. -int VP8LCreateHuffmanTree(int* const histogram, int tree_depth_limit, - HuffmanTreeCode* const tree); - -#if defined(__cplusplus) || defined(c_plusplus) -} -#endif - -#endif // WEBP_UTILS_HUFFMAN_ENCODE_H_ diff --git a/drivers/webpold/utils/quant_levels.c b/drivers/webpold/utils/quant_levels.c deleted file mode 100644 index f6884392aa..0000000000 --- a/drivers/webpold/utils/quant_levels.c +++ /dev/null @@ -1,154 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// 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 "./quant_levels.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#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; -} - -int DequantizeLevels(uint8_t* const data, int width, int height) { - if (data == NULL || width <= 0 || height <= 0) return 0; - // TODO(skal): implement gradient smoothing. - (void)data; - (void)width; - (void)height; - return 1; -} - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/quant_levels.h b/drivers/webpold/utils/quant_levels.h deleted file mode 100644 index 4f165fd230..0000000000 --- a/drivers/webpold/utils/quant_levels.h +++ /dev/null @@ -1,39 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Alpha plane quantization utility -// -// Author: Vikas Arora (vikasa@google.com) - -#ifndef WEBP_UTILS_QUANT_LEVELS_H_ -#define WEBP_UTILS_QUANT_LEVELS_H_ - -#include <stdlib.h> - -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -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); - -// Apply post-processing to input 'data' of size 'width'x'height' assuming -// that the source was quantized to a reduced number of levels. -// Returns false in case of error (data is NULL, invalid parameters, ...). -int DequantizeLevels(uint8_t* const data, int width, int height); - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif /* WEBP_UTILS_QUANT_LEVELS_H_ */ diff --git a/drivers/webpold/utils/rescaler.c b/drivers/webpold/utils/rescaler.c deleted file mode 100644 index 9825dcbc5f..0000000000 --- a/drivers/webpold/utils/rescaler.c +++ /dev/null @@ -1,152 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Rescaling functions -// -// Author: Skal (pascal.massimino@gmail.com) - -#include <assert.h> -#include <stdlib.h> -#include "./rescaler.h" - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#define RFIX 30 -#define MULT_FIX(x,y) (((int64_t)(x) * (y) + (1 << (RFIX - 1))) >> RFIX) - -void WebPRescalerInit(WebPRescaler* const wrk, int src_width, int src_height, - uint8_t* const dst, int dst_width, int dst_height, - int dst_stride, int num_channels, int x_add, int x_sub, - int y_add, int y_sub, int32_t* const work) { - wrk->x_expand = (src_width < dst_width); - wrk->src_width = src_width; - wrk->src_height = src_height; - wrk->dst_width = dst_width; - wrk->dst_height = dst_height; - wrk->dst = dst; - wrk->dst_stride = dst_stride; - wrk->num_channels = num_channels; - // for 'x_expand', we use bilinear interpolation - wrk->x_add = wrk->x_expand ? (x_sub - 1) : x_add - x_sub; - wrk->x_sub = wrk->x_expand ? (x_add - 1) : x_sub; - wrk->y_accum = y_add; - wrk->y_add = y_add; - wrk->y_sub = y_sub; - wrk->fx_scale = (1 << RFIX) / x_sub; - wrk->fy_scale = (1 << RFIX) / y_sub; - wrk->fxy_scale = wrk->x_expand ? - ((int64_t)dst_height << RFIX) / (x_sub * src_height) : - ((int64_t)dst_height << RFIX) / (x_add * src_height); - wrk->irow = work; - wrk->frow = work + num_channels * dst_width; -} - -void WebPRescalerImportRow(WebPRescaler* const wrk, - const uint8_t* const src, int channel) { - const int x_stride = wrk->num_channels; - const int x_out_max = wrk->dst_width * wrk->num_channels; - int x_in = channel; - int x_out; - int accum = 0; - if (!wrk->x_expand) { - int sum = 0; - for (x_out = channel; x_out < x_out_max; x_out += x_stride) { - accum += wrk->x_add; - for (; accum > 0; accum -= wrk->x_sub) { - sum += src[x_in]; - x_in += x_stride; - } - { // Emit next horizontal pixel. - const int32_t base = src[x_in]; - const int32_t frac = base * (-accum); - x_in += x_stride; - wrk->frow[x_out] = (sum + base) * wrk->x_sub - frac; - // fresh fractional start for next pixel - sum = (int)MULT_FIX(frac, wrk->fx_scale); - } - } - } else { // simple bilinear interpolation - int left = src[channel], right = src[channel]; - for (x_out = channel; x_out < x_out_max; x_out += x_stride) { - if (accum < 0) { - left = right; - x_in += x_stride; - right = src[x_in]; - accum += wrk->x_add; - } - wrk->frow[x_out] = right * wrk->x_add + (left - right) * accum; - accum -= wrk->x_sub; - } - } - // Accumulate the new row's contribution - for (x_out = channel; x_out < x_out_max; x_out += x_stride) { - wrk->irow[x_out] += wrk->frow[x_out]; - } -} - -uint8_t* WebPRescalerExportRow(WebPRescaler* const wrk) { - if (wrk->y_accum <= 0) { - int x_out; - uint8_t* const dst = wrk->dst; - int32_t* const irow = wrk->irow; - const int32_t* const frow = wrk->frow; - const int yscale = wrk->fy_scale * (-wrk->y_accum); - const int x_out_max = wrk->dst_width * wrk->num_channels; - - for (x_out = 0; x_out < x_out_max; ++x_out) { - const int frac = (int)MULT_FIX(frow[x_out], yscale); - const int v = (int)MULT_FIX(irow[x_out] - frac, wrk->fxy_scale); - dst[x_out] = (!(v & ~0xff)) ? v : (v < 0) ? 0 : 255; - irow[x_out] = frac; // new fractional start - } - wrk->y_accum += wrk->y_add; - wrk->dst += wrk->dst_stride; - return dst; - } else { - return NULL; - } -} - -#undef MULT_FIX -#undef RFIX - -//------------------------------------------------------------------------------ -// all-in-one calls - -int WebPRescalerImport(WebPRescaler* const wrk, int num_lines, - const uint8_t* src, int src_stride) { - int total_imported = 0; - while (total_imported < num_lines && wrk->y_accum > 0) { - int channel; - for (channel = 0; channel < wrk->num_channels; ++channel) { - WebPRescalerImportRow(wrk, src, channel); - } - src += src_stride; - ++total_imported; - wrk->y_accum -= wrk->y_sub; - } - return total_imported; -} - -int WebPRescalerExport(WebPRescaler* const rescaler) { - int total_exported = 0; - while (WebPRescalerHasPendingOutput(rescaler)) { - WebPRescalerExportRow(rescaler); - ++total_exported; - } - return total_exported; -} - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/rescaler.h b/drivers/webpold/utils/rescaler.h deleted file mode 100644 index 9c9133d19b..0000000000 --- a/drivers/webpold/utils/rescaler.h +++ /dev/null @@ -1,76 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Rescaling functions -// -// Author: Skal (pascal.massimino@gmail.com) - -#ifndef WEBP_UTILS_RESCALER_H_ -#define WEBP_UTILS_RESCALER_H_ - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#include "../types.h" - -// Structure used for on-the-fly rescaling -typedef struct { - int x_expand; // true if we're expanding in the x direction - int num_channels; // bytes to jump between pixels - int fy_scale, fx_scale; // fixed-point scaling factor - int64_t fxy_scale; // '' - // we need hpel-precise add/sub increments, for the downsampled U/V planes. - int y_accum; // vertical accumulator - int y_add, y_sub; // vertical increments (add ~= src, sub ~= dst) - int x_add, x_sub; // horizontal increments (add ~= src, sub ~= dst) - int src_width, src_height; // source dimensions - int dst_width, dst_height; // destination dimensions - uint8_t* dst; - int dst_stride; - int32_t* irow, *frow; // work buffer -} WebPRescaler; - -// Initialize a rescaler given scratch area 'work' and dimensions of src & dst. -void WebPRescalerInit(WebPRescaler* const wrk, int src_width, int src_height, - uint8_t* const dst, - int dst_width, int dst_height, int dst_stride, - int num_channels, - int x_add, int x_sub, - int y_add, int y_sub, - int32_t* const work); - -// Import a row of data and save its contribution in the rescaler. -// 'channel' denotes the channel number to be imported. -void WebPRescalerImportRow(WebPRescaler* const rescaler, - const uint8_t* const src, int channel); - -// 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); - -// Return true if there is pending output rows ready. -static WEBP_INLINE -int WebPRescalerHasPendingOutput(const WebPRescaler* const rescaler) { - return (rescaler->y_accum <= 0); -} - -// Export one row from rescaler. Returns the pointer where output was written, -// or NULL if no row was pending. -uint8_t* WebPRescalerExportRow(WebPRescaler* const wrk); - -// Export as many rows as possible. Return the numbers of rows written. -int WebPRescalerExport(WebPRescaler* const wrk); - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif /* WEBP_UTILS_RESCALER_H_ */ diff --git a/drivers/webpold/utils/thread.c b/drivers/webpold/utils/thread.c deleted file mode 100644 index ce89cf9dc7..0000000000 --- a/drivers/webpold/utils/thread.c +++ /dev/null @@ -1,247 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Multi-threaded worker -// -// Author: Skal (pascal.massimino@gmail.com) - -#ifdef HAVE_CONFIG_H -#include "config.h" -#endif - -#include <assert.h> -#include <string.h> // for memset() -#include "./thread.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#ifdef WEBP_USE_THREAD - -#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) - -static int pthread_create(pthread_t* const thread, const void* attr, - unsigned int (__stdcall *start)(void*), void* arg) { - (void)attr; - *thread = (pthread_t)_beginthreadex(NULL, /* void *security */ - 0, /* unsigned stack_size */ - start, - arg, - 0, /* unsigned initflag */ - NULL); /* unsigned *thrdaddr */ - 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; - InitializeCriticalSection(mutex); - 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; - ok &= (CloseHandle(condition->waiting_sem_) != 0); - ok &= (CloseHandle(condition->received_sem_) != 0); - ok &= (CloseHandle(condition->signal_event_) != 0); - return !ok; -} - -static int pthread_cond_init(pthread_cond_t* const condition, void* cond_attr) { - (void)cond_attr; - 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; - } - return 0; -} - -static int pthread_cond_signal(pthread_cond_t* const condition) { - int ok = 1; - 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); - } - return !ok; -} - -static int pthread_cond_wait(pthread_cond_t* const condition, - pthread_mutex_t* const mutex) { - int ok; - // 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); - return !ok; -} - -#else // _WIN32 -# define THREADFN void* -# define THREAD_RETURN(val) val -#endif - -//------------------------------------------------------------------------------ - -static THREADFN WebPWorkerThreadLoop(void *ptr) { // thread loop - WebPWorker* const worker = (WebPWorker*)ptr; - int done = 0; - while (!done) { - pthread_mutex_lock(&worker->mutex_); - while (worker->status_ == OK) { // wait in idling mode - pthread_cond_wait(&worker->condition_, &worker->mutex_); - } - if (worker->status_ == WORK) { - if (worker->hook) { - worker->had_error |= !worker->hook(worker->data1, worker->data2); - } - 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()) - pthread_cond_signal(&worker->condition_); - pthread_mutex_unlock(&worker->mutex_); - } - return THREAD_RETURN(NULL); // Thread is finished -} - -// main thread state control -static void WebPWorkerChangeState(WebPWorker* const worker, - WebPWorkerStatus new_status) { - // no-op when attempting to change state on a thread that didn't come up - if (worker->status_ < OK) return; - - pthread_mutex_lock(&worker->mutex_); - // wait for the worker to finish - while (worker->status_ != OK) { - pthread_cond_wait(&worker->condition_, &worker->mutex_); - } - // assign new status and release the working thread if needed - if (new_status != OK) { - worker->status_ = new_status; - pthread_cond_signal(&worker->condition_); - } - pthread_mutex_unlock(&worker->mutex_); -} - -#endif - -//------------------------------------------------------------------------------ - -void WebPWorkerInit(WebPWorker* const worker) { - memset(worker, 0, sizeof(*worker)); - worker->status_ = NOT_OK; -} - -int WebPWorkerSync(WebPWorker* const worker) { -#ifdef WEBP_USE_THREAD - WebPWorkerChangeState(worker, OK); -#endif - assert(worker->status_ <= OK); - return !worker->had_error; -} - -int WebPWorkerReset(WebPWorker* const worker) { - int ok = 1; - worker->had_error = 0; - if (worker->status_ < OK) { -#ifdef WEBP_USE_THREAD - if (pthread_mutex_init(&worker->mutex_, NULL) || - pthread_cond_init(&worker->condition_, NULL)) { - return 0; - } - pthread_mutex_lock(&worker->mutex_); - ok = !pthread_create(&worker->thread_, NULL, WebPWorkerThreadLoop, worker); - if (ok) worker->status_ = OK; - pthread_mutex_unlock(&worker->mutex_); -#else - worker->status_ = OK; -#endif - } else if (worker->status_ > OK) { - ok = WebPWorkerSync(worker); - } - assert(!ok || (worker->status_ == OK)); - return ok; -} - -void WebPWorkerLaunch(WebPWorker* const worker) { -#ifdef WEBP_USE_THREAD - WebPWorkerChangeState(worker, WORK); -#else - if (worker->hook) - worker->had_error |= !worker->hook(worker->data1, worker->data2); -#endif -} - -void WebPWorkerEnd(WebPWorker* const worker) { - if (worker->status_ >= OK) { -#ifdef WEBP_USE_THREAD - WebPWorkerChangeState(worker, NOT_OK); - pthread_join(worker->thread_, NULL); - pthread_mutex_destroy(&worker->mutex_); - pthread_cond_destroy(&worker->condition_); -#else - worker->status_ = NOT_OK; -#endif - } - assert(worker->status_ == NOT_OK); -} - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/thread.h b/drivers/webpold/utils/thread.h deleted file mode 100644 index 3191890b76..0000000000 --- a/drivers/webpold/utils/thread.h +++ /dev/null @@ -1,86 +0,0 @@ -// Copyright 2011 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Multi-threaded worker -// -// Author: Skal (pascal.massimino@gmail.com) - -#ifndef WEBP_UTILS_THREAD_H_ -#define WEBP_UTILS_THREAD_H_ - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#if WEBP_USE_THREAD - -#if defined(_WIN32) - -#include <windows.h> -typedef HANDLE pthread_t; -typedef CRITICAL_SECTION pthread_mutex_t; -typedef struct { - HANDLE waiting_sem_; - HANDLE received_sem_; - HANDLE signal_event_; -} pthread_cond_t; - -#else - -#include <pthread.h> - -#endif /* _WIN32 */ -#endif /* WEBP_USE_THREAD */ - -// 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*); - -// Synchronize object used to launch job in the worker thread -typedef struct { -#if WEBP_USE_THREAD - pthread_mutex_t mutex_; - pthread_cond_t condition_; - pthread_t thread_; -#endif - 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; - -// Must be called first, before any other method. -void WebPWorkerInit(WebPWorker* const worker); -// Must be called initialize the object and spawn the thread. Re-entrant. -// Will potentially launch the thread. Returns false in case of error. -int WebPWorkerReset(WebPWorker* const worker); -// Make sure the previous work is finished. Returns true if worker->had_error -// was not set and not error condition was triggered by the working thread. -int WebPWorkerSync(WebPWorker* const worker); -// Trigger the thread to call hook() with data1 and data2 argument. These -// hook/data1/data2 can be changed at any time before calling this function, -// but not be changed afterward until the next call to WebPWorkerSync(). -void WebPWorkerLaunch(WebPWorker* const worker); -// Kill the thread and terminate the object. To use the object again, one -// must call WebPWorkerReset() again. -void WebPWorkerEnd(WebPWorker* const worker); - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif /* WEBP_UTILS_THREAD_H_ */ diff --git a/drivers/webpold/utils/utils.c b/drivers/webpold/utils/utils.c deleted file mode 100644 index 673b7e284c..0000000000 --- a/drivers/webpold/utils/utils.c +++ /dev/null @@ -1,44 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Misc. common utility functions -// -// Author: Skal (pascal.massimino@gmail.com) - -#include <stdlib.h> -#include "./utils.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -//------------------------------------------------------------------------------ -// Checked memory allocation - -static int CheckSizeArguments(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 (total_size != (size_t)total_size) return 0; - return 1; -} - -void* WebPSafeMalloc(uint64_t nmemb, size_t size) { - if (!CheckSizeArguments(nmemb, size)) return NULL; - return malloc((size_t)(nmemb * size)); -} - -void* WebPSafeCalloc(uint64_t nmemb, size_t size) { - if (!CheckSizeArguments(nmemb, size)) return NULL; - return calloc((size_t)nmemb, size); -} - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif diff --git a/drivers/webpold/utils/utils.h b/drivers/webpold/utils/utils.h deleted file mode 100644 index 316ac90612..0000000000 --- a/drivers/webpold/utils/utils.h +++ /dev/null @@ -1,44 +0,0 @@ -// Copyright 2012 Google Inc. All Rights Reserved. -// -// This code is licensed under the same terms as WebM: -// Software License Agreement: http://www.webmproject.org/license/software/ -// Additional IP Rights Grant: http://www.webmproject.org/license/additional/ -// ----------------------------------------------------------------------------- -// -// Misc. common utility functions -// -// Author: Skal (pascal.massimino@gmail.com) - -#ifndef WEBP_UTILS_UTILS_H_ -#define WEBP_UTILS_UTILS_H_ - -#include "../types.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -//------------------------------------------------------------------------------ -// Memory allocation - -// This is the maximum memory amount that libwebp will ever try to allocate. -#define WEBP_MAX_ALLOCABLE_MEMORY (1ULL << 40) - -// 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. -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. -void* WebPSafeCalloc(uint64_t nmemb, size_t size); - -//------------------------------------------------------------------------------ - -#if defined(__cplusplus) || defined(c_plusplus) -} // extern "C" -#endif - -#endif /* WEBP_UTILS_UTILS_H_ */ |