diff options
Diffstat (limited to 'src/3rdparty/libwebp/src/utils')
26 files changed, 3526 insertions, 0 deletions
diff --git a/src/3rdparty/libwebp/src/utils/alpha_processing.c b/src/3rdparty/libwebp/src/utils/alpha_processing.c new file mode 100644 index 0000000..7362ff9 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/alpha_processing.c @@ -0,0 +1,196 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Utilities for processing transparent channel. +// +// Author: Skal (pascal.massimino@gmail.com) + +#include <assert.h> +#include "./alpha_processing.h" + +// Tables can be faster on some platform but incur some extra binary size (~2k). +// #define USE_TABLES_FOR_ALPHA_MULT + +// ----------------------------------------------------------------------------- + +#define MFIX 24 // 24bit fixed-point arithmetic +#define HALF ((1u << MFIX) >> 1) +#define KINV_255 ((1u << MFIX) / 255u) + +static uint32_t Mult(uint8_t x, uint32_t mult) { + const uint32_t v = (x * mult + HALF) >> MFIX; + assert(v <= 255); // <- 24bit precision is enough to ensure that. + return v; +} + +#ifdef USE_TABLES_FOR_ALPHA_MULT + +static const uint32_t kMultTables[2][256] = { + { // (255u << MFIX) / alpha + 0x00000000, 0xff000000, 0x7f800000, 0x55000000, 0x3fc00000, 0x33000000, + 0x2a800000, 0x246db6db, 0x1fe00000, 0x1c555555, 0x19800000, 0x172e8ba2, + 0x15400000, 0x139d89d8, 0x1236db6d, 0x11000000, 0x0ff00000, 0x0f000000, + 0x0e2aaaaa, 0x0d6bca1a, 0x0cc00000, 0x0c249249, 0x0b9745d1, 0x0b1642c8, + 0x0aa00000, 0x0a333333, 0x09cec4ec, 0x0971c71c, 0x091b6db6, 0x08cb08d3, + 0x08800000, 0x0839ce73, 0x07f80000, 0x07ba2e8b, 0x07800000, 0x07492492, + 0x07155555, 0x06e45306, 0x06b5e50d, 0x0689d89d, 0x06600000, 0x063831f3, + 0x06124924, 0x05ee23b8, 0x05cba2e8, 0x05aaaaaa, 0x058b2164, 0x056cefa8, + 0x05500000, 0x05343eb1, 0x05199999, 0x05000000, 0x04e76276, 0x04cfb2b7, + 0x04b8e38e, 0x04a2e8ba, 0x048db6db, 0x0479435e, 0x04658469, 0x045270d0, + 0x04400000, 0x042e29f7, 0x041ce739, 0x040c30c3, 0x03fc0000, 0x03ec4ec4, + 0x03dd1745, 0x03ce540f, 0x03c00000, 0x03b21642, 0x03a49249, 0x03976fc6, + 0x038aaaaa, 0x037e3f1f, 0x03722983, 0x03666666, 0x035af286, 0x034fcace, + 0x0344ec4e, 0x033a5440, 0x03300000, 0x0325ed09, 0x031c18f9, 0x0312818a, + 0x03092492, 0x03000000, 0x02f711dc, 0x02ee5846, 0x02e5d174, 0x02dd7baf, + 0x02d55555, 0x02cd5cd5, 0x02c590b2, 0x02bdef7b, 0x02b677d4, 0x02af286b, + 0x02a80000, 0x02a0fd5c, 0x029a1f58, 0x029364d9, 0x028ccccc, 0x0286562d, + 0x02800000, 0x0279c952, 0x0273b13b, 0x026db6db, 0x0267d95b, 0x026217ec, + 0x025c71c7, 0x0256e62a, 0x0251745d, 0x024c1bac, 0x0246db6d, 0x0241b2f9, + 0x023ca1af, 0x0237a6f4, 0x0232c234, 0x022df2df, 0x02293868, 0x02249249, + 0x02200000, 0x021b810e, 0x021714fb, 0x0212bb51, 0x020e739c, 0x020a3d70, + 0x02061861, 0x02020408, 0x01fe0000, 0x01fa0be8, 0x01f62762, 0x01f25213, + 0x01ee8ba2, 0x01ead3ba, 0x01e72a07, 0x01e38e38, 0x01e00000, 0x01dc7f10, + 0x01d90b21, 0x01d5a3e9, 0x01d24924, 0x01cefa8d, 0x01cbb7e3, 0x01c880e5, + 0x01c55555, 0x01c234f7, 0x01bf1f8f, 0x01bc14e5, 0x01b914c1, 0x01b61eed, + 0x01b33333, 0x01b05160, 0x01ad7943, 0x01aaaaaa, 0x01a7e567, 0x01a5294a, + 0x01a27627, 0x019fcbd2, 0x019d2a20, 0x019a90e7, 0x01980000, 0x01957741, + 0x0192f684, 0x01907da4, 0x018e0c7c, 0x018ba2e8, 0x018940c5, 0x0186e5f0, + 0x01849249, 0x018245ae, 0x01800000, 0x017dc11f, 0x017b88ee, 0x0179574e, + 0x01772c23, 0x01750750, 0x0172e8ba, 0x0170d045, 0x016ebdd7, 0x016cb157, + 0x016aaaaa, 0x0168a9b9, 0x0166ae6a, 0x0164b8a7, 0x0162c859, 0x0160dd67, + 0x015ef7bd, 0x015d1745, 0x015b3bea, 0x01596596, 0x01579435, 0x0155c7b4, + 0x01540000, 0x01523d03, 0x01507eae, 0x014ec4ec, 0x014d0fac, 0x014b5edc, + 0x0149b26c, 0x01480a4a, 0x01466666, 0x0144c6af, 0x01432b16, 0x0141938b, + 0x01400000, 0x013e7063, 0x013ce4a9, 0x013b5cc0, 0x0139d89d, 0x01385830, + 0x0136db6d, 0x01356246, 0x0133ecad, 0x01327a97, 0x01310bf6, 0x012fa0be, + 0x012e38e3, 0x012cd459, 0x012b7315, 0x012a150a, 0x0128ba2e, 0x01276276, + 0x01260dd6, 0x0124bc44, 0x01236db6, 0x01222222, 0x0120d97c, 0x011f93bc, + 0x011e50d7, 0x011d10c4, 0x011bd37a, 0x011a98ef, 0x0119611a, 0x01182bf2, + 0x0116f96f, 0x0115c988, 0x01149c34, 0x0113716a, 0x01124924, 0x01112358, + 0x01100000, 0x010edf12, 0x010dc087, 0x010ca458, 0x010b8a7d, 0x010a72f0, + 0x01095da8, 0x01084a9f, 0x010739ce, 0x01062b2e, 0x01051eb8, 0x01041465, + 0x01030c30, 0x01020612, 0x01010204, 0x01000000 }, + { // alpha * KINV_255 + 0x00000000, 0x00010101, 0x00020202, 0x00030303, 0x00040404, 0x00050505, + 0x00060606, 0x00070707, 0x00080808, 0x00090909, 0x000a0a0a, 0x000b0b0b, + 0x000c0c0c, 0x000d0d0d, 0x000e0e0e, 0x000f0f0f, 0x00101010, 0x00111111, + 0x00121212, 0x00131313, 0x00141414, 0x00151515, 0x00161616, 0x00171717, + 0x00181818, 0x00191919, 0x001a1a1a, 0x001b1b1b, 0x001c1c1c, 0x001d1d1d, + 0x001e1e1e, 0x001f1f1f, 0x00202020, 0x00212121, 0x00222222, 0x00232323, + 0x00242424, 0x00252525, 0x00262626, 0x00272727, 0x00282828, 0x00292929, + 0x002a2a2a, 0x002b2b2b, 0x002c2c2c, 0x002d2d2d, 0x002e2e2e, 0x002f2f2f, + 0x00303030, 0x00313131, 0x00323232, 0x00333333, 0x00343434, 0x00353535, + 0x00363636, 0x00373737, 0x00383838, 0x00393939, 0x003a3a3a, 0x003b3b3b, + 0x003c3c3c, 0x003d3d3d, 0x003e3e3e, 0x003f3f3f, 0x00404040, 0x00414141, + 0x00424242, 0x00434343, 0x00444444, 0x00454545, 0x00464646, 0x00474747, + 0x00484848, 0x00494949, 0x004a4a4a, 0x004b4b4b, 0x004c4c4c, 0x004d4d4d, + 0x004e4e4e, 0x004f4f4f, 0x00505050, 0x00515151, 0x00525252, 0x00535353, + 0x00545454, 0x00555555, 0x00565656, 0x00575757, 0x00585858, 0x00595959, + 0x005a5a5a, 0x005b5b5b, 0x005c5c5c, 0x005d5d5d, 0x005e5e5e, 0x005f5f5f, + 0x00606060, 0x00616161, 0x00626262, 0x00636363, 0x00646464, 0x00656565, + 0x00666666, 0x00676767, 0x00686868, 0x00696969, 0x006a6a6a, 0x006b6b6b, + 0x006c6c6c, 0x006d6d6d, 0x006e6e6e, 0x006f6f6f, 0x00707070, 0x00717171, + 0x00727272, 0x00737373, 0x00747474, 0x00757575, 0x00767676, 0x00777777, + 0x00787878, 0x00797979, 0x007a7a7a, 0x007b7b7b, 0x007c7c7c, 0x007d7d7d, + 0x007e7e7e, 0x007f7f7f, 0x00808080, 0x00818181, 0x00828282, 0x00838383, + 0x00848484, 0x00858585, 0x00868686, 0x00878787, 0x00888888, 0x00898989, + 0x008a8a8a, 0x008b8b8b, 0x008c8c8c, 0x008d8d8d, 0x008e8e8e, 0x008f8f8f, + 0x00909090, 0x00919191, 0x00929292, 0x00939393, 0x00949494, 0x00959595, + 0x00969696, 0x00979797, 0x00989898, 0x00999999, 0x009a9a9a, 0x009b9b9b, + 0x009c9c9c, 0x009d9d9d, 0x009e9e9e, 0x009f9f9f, 0x00a0a0a0, 0x00a1a1a1, + 0x00a2a2a2, 0x00a3a3a3, 0x00a4a4a4, 0x00a5a5a5, 0x00a6a6a6, 0x00a7a7a7, + 0x00a8a8a8, 0x00a9a9a9, 0x00aaaaaa, 0x00ababab, 0x00acacac, 0x00adadad, + 0x00aeaeae, 0x00afafaf, 0x00b0b0b0, 0x00b1b1b1, 0x00b2b2b2, 0x00b3b3b3, + 0x00b4b4b4, 0x00b5b5b5, 0x00b6b6b6, 0x00b7b7b7, 0x00b8b8b8, 0x00b9b9b9, + 0x00bababa, 0x00bbbbbb, 0x00bcbcbc, 0x00bdbdbd, 0x00bebebe, 0x00bfbfbf, + 0x00c0c0c0, 0x00c1c1c1, 0x00c2c2c2, 0x00c3c3c3, 0x00c4c4c4, 0x00c5c5c5, + 0x00c6c6c6, 0x00c7c7c7, 0x00c8c8c8, 0x00c9c9c9, 0x00cacaca, 0x00cbcbcb, + 0x00cccccc, 0x00cdcdcd, 0x00cecece, 0x00cfcfcf, 0x00d0d0d0, 0x00d1d1d1, + 0x00d2d2d2, 0x00d3d3d3, 0x00d4d4d4, 0x00d5d5d5, 0x00d6d6d6, 0x00d7d7d7, + 0x00d8d8d8, 0x00d9d9d9, 0x00dadada, 0x00dbdbdb, 0x00dcdcdc, 0x00dddddd, + 0x00dedede, 0x00dfdfdf, 0x00e0e0e0, 0x00e1e1e1, 0x00e2e2e2, 0x00e3e3e3, + 0x00e4e4e4, 0x00e5e5e5, 0x00e6e6e6, 0x00e7e7e7, 0x00e8e8e8, 0x00e9e9e9, + 0x00eaeaea, 0x00ebebeb, 0x00ececec, 0x00ededed, 0x00eeeeee, 0x00efefef, + 0x00f0f0f0, 0x00f1f1f1, 0x00f2f2f2, 0x00f3f3f3, 0x00f4f4f4, 0x00f5f5f5, + 0x00f6f6f6, 0x00f7f7f7, 0x00f8f8f8, 0x00f9f9f9, 0x00fafafa, 0x00fbfbfb, + 0x00fcfcfc, 0x00fdfdfd, 0x00fefefe, 0x00ffffff } +}; + +static WEBP_INLINE uint32_t GetScale(uint32_t a, int inverse) { + return kMultTables[!inverse][a]; +} + +#else + +static WEBP_INLINE uint32_t GetScale(uint32_t a, int inverse) { + return inverse ? (255u << MFIX) / a : a * KINV_255; +} + +#endif // USE_TABLES_FOR_ALPHA_MULT + +void WebPMultARGBRow(uint32_t* const ptr, int width, int inverse) { + int x; + for (x = 0; x < width; ++x) { + const uint32_t argb = ptr[x]; + if (argb < 0xff000000u) { // alpha < 255 + if (argb <= 0x00ffffffu) { // alpha == 0 + ptr[x] = 0; + } else { + const uint32_t alpha = (argb >> 24) & 0xff; + const uint32_t scale = GetScale(alpha, inverse); + uint32_t out = argb & 0xff000000u; + out |= Mult(argb >> 0, scale) << 0; + out |= Mult(argb >> 8, scale) << 8; + out |= Mult(argb >> 16, scale) << 16; + ptr[x] = out; + } + } + } +} + +void WebPMultARGBRows(uint8_t* ptr, int stride, int width, int num_rows, + int inverse) { + int n; + for (n = 0; n < num_rows; ++n) { + WebPMultARGBRow((uint32_t*)ptr, width, inverse); + ptr += stride; + } +} + +void WebPMultRow(uint8_t* const ptr, const uint8_t* const alpha, + int width, int inverse) { + int x; + for (x = 0; x < width; ++x) { + const uint32_t a = alpha[x]; + if (a != 255) { + if (a == 0) { + ptr[x] = 0; + } else { + const uint32_t scale = GetScale(a, inverse); + ptr[x] = Mult(ptr[x], scale); + } + } + } +} + +void WebPMultRows(uint8_t* ptr, int stride, + const uint8_t* alpha, int alpha_stride, + int width, int num_rows, int inverse) { + int n; + for (n = 0; n < num_rows; ++n) { + WebPMultRow(ptr, alpha, width, inverse); + ptr += stride; + alpha += alpha_stride; + } +} + +#undef KINV_255 +#undef HALF +#undef MFIX + diff --git a/src/3rdparty/libwebp/src/utils/alpha_processing.h b/src/3rdparty/libwebp/src/utils/alpha_processing.h new file mode 100644 index 0000000..80e1ae4 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/alpha_processing.h @@ -0,0 +1,46 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Utilities for processing transparent channel. +// +// Author: Skal (pascal.massimino@gmail.com) + +#ifndef WEBP_UTILS_ALPHA_PROCESSING_H_ +#define WEBP_UTILS_ALPHA_PROCESSING_H_ + +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +// Pre-Multiply operation transforms x into x * A / 255 (where x=Y,R,G or B). +// Un-Multiply operation transforms x into x * 255 / A. + +// Pre-Multiply or Un-Multiply (if 'inverse' is true) argb values in a row. +void WebPMultARGBRow(uint32_t* const ptr, int width, int inverse); + +// Same a WebPMultARGBRow(), but for several rows. +void WebPMultARGBRows(uint8_t* ptr, int stride, int width, int num_rows, + int inverse); + +// Same for a row of single values, with side alpha values. +void WebPMultRow(uint8_t* const ptr, const uint8_t* const alpha, + int width, int inverse); + +// Same a WebPMultRow(), but for several 'num_rows' rows. +void WebPMultRows(uint8_t* ptr, int stride, + const uint8_t* alpha, int alpha_stride, + int width, int num_rows, int inverse); + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif // WEBP_UTILS_ALPHA_PROCESSING_H_ diff --git a/src/3rdparty/libwebp/src/utils/bit_reader.c b/src/3rdparty/libwebp/src/utils/bit_reader.c new file mode 100644 index 0000000..bfa4d7d --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/bit_reader.c @@ -0,0 +1,207 @@ +// Copyright 2010 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Boolean decoder +// +// Author: Skal (pascal.massimino@gmail.com) + +#include "./bit_reader.h" + +#ifndef USE_RIGHT_JUSTIFY +#define MK(X) (((range_t)(X) << (BITS)) | (MASK)) +#else +#define MK(X) ((range_t)(X)) +#endif + +//------------------------------------------------------------------------------ +// 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->bits_ = -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 range_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_) { +#ifndef USE_RIGHT_JUSTIFY + br->value_ |= (bit_t)(*br->buf_++) << ((BITS) - 8 - br->bits_); +#else + br->value_ = (bit_t)(*br->buf_++) | (br->value_ << 8); +#endif + br->bits_ += 8; + } else if (!br->eof_) { +#ifdef USE_RIGHT_JUSTIFY + // These are not strictly needed, but it makes the behaviour + // consistent for both USE_RIGHT_JUSTIFY and !USE_RIGHT_JUSTIFY. + br->value_ <<= 8; + br->bits_ += 8; +#endif + 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 + +#define LBITS 64 // Number of bits prefetched. +#define WBITS 32 // Minimum number of bytes needed after VP8LFillBitWindow. +#define LOG8_WBITS 4 // Number of bytes needed to store WBITS bits. + +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_ |= ((vp8l_val_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; +} + +// If not at EOS, reload up to LBITS byte-by-byte +static void ShiftBytes(VP8LBitReader* const br) { + while (br->bit_pos_ >= 8 && br->pos_ < br->len_) { + br->val_ >>= 8; + br->val_ |= ((vp8l_val_t)br->buf_[br->pos_]) << (LBITS - 8); + ++br->pos_; + br->bit_pos_ -= 8; + } +} + +void VP8LFillBitWindow(VP8LBitReader* const br) { + if (br->bit_pos_ >= WBITS) { +#if (defined(__x86_64__) || defined(_M_X64)) + if (br->pos_ + sizeof(br->val_) < br->len_) { + br->val_ >>= WBITS; + br->bit_pos_ -= WBITS; + // The expression below needs a little-endian arch to work correctly. + // This gives a large speedup for decoding speed. + br->val_ |= *(const vp8l_val_t*)(br->buf_ + br->pos_) << (LBITS - WBITS); + br->pos_ += LOG8_WBITS; + return; + } +#endif + ShiftBytes(br); // Slow path. + if (br->pos_ == br->len_ && br->bit_pos_ >= LBITS) { + br->eos_ = 1; + } + } +} + +uint32_t VP8LReadBits(VP8LBitReader* const br, int n_bits) { + assert(n_bits >= 0); + // Flag an error if end_of_stream or n_bits is more than allowed limit. + if (!br->eos_ && n_bits < MAX_NUM_BIT_READ) { + const uint32_t val = + (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits]; + const int new_bits = br->bit_pos_ + n_bits; + br->bit_pos_ = new_bits; + // If this read is going to cross the read buffer, set the eos flag. + if (br->pos_ == br->len_) { + if (new_bits >= LBITS) { + br->eos_ = 1; + } + } + ShiftBytes(br); + return val; + } else { + br->error_ = 1; + return 0; + } +} + +//------------------------------------------------------------------------------ + diff --git a/src/3rdparty/libwebp/src/utils/bit_reader.h b/src/3rdparty/libwebp/src/utils/bit_reader.h new file mode 100644 index 0000000..98df98a --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/bit_reader.h @@ -0,0 +1,334 @@ +// Copyright 2010 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Boolean decoder +// +// Author: Skal (pascal.massimino@gmail.com) +// Vikas Arora (vikaas.arora@gmail.com) + +#ifndef WEBP_UTILS_BIT_READER_H_ +#define WEBP_UTILS_BIT_READER_H_ + +#include <assert.h> +#ifdef _MSC_VER +#include <stdlib.h> // _byteswap_ulong +#endif +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +// The Boolean decoder needs to maintain infinite precision on the value_ field. +// However, since range_ is only 8bit, we only need an active window of 8 bits +// for value_. Left bits (MSB) gets zeroed and shifted away when value_ falls +// below 128, range_ is updated, and fresh bits read from the bitstream are +// brought in as LSB. +// To avoid reading the fresh bits one by one (slow), we cache a few of them +// ahead (actually, we cache BITS of them ahead. See below). There's two +// strategies regarding how to shift these looked-ahead fresh bits into the +// 8bit window of value_: either we shift them in, while keeping the position of +// the window fixed. Or we slide the window to the right while keeping the cache +// bits at a fixed, right-justified, position. +// +// Example, for BITS=16: here is the content of value_ for both strategies: +// +// !USE_RIGHT_JUSTIFY || USE_RIGHT_JUSTIFY +// || +// <- 8b -><- 8b -><- BITS bits -> || <- 8b+3b -><- 8b -><- 13 bits -> +// [unused][value_][cached bits][0] || [unused...][value_][cached bits] +// [........00vvvvvvBBBBBBBBBBBBB000]LSB || [...........00vvvvvvBBBBBBBBBBBBB] +// || +// After calling VP8Shift(), where we need to shift away two zeros: +// [........vvvvvvvvBBBBBBBBBBB00000]LSB || [.............vvvvvvvvBBBBBBBBBBB] +// || +// Just before we need to call VP8LoadNewBytes(), the situation is: +// [........vvvvvv000000000000000000]LSB || [..........................vvvvvv] +// || +// And just after calling VP8LoadNewBytes(): +// [........vvvvvvvvBBBBBBBBBBBBBBBB]LSB || [........vvvvvvvvBBBBBBBBBBBBBBBB] +// +// -> we're back to eight active 'value_' bits (marked 'v') and BITS cached +// bits (marked 'B') +// +// The right-justify strategy tends to use less shifts and is often faster. + +//------------------------------------------------------------------------------ +// BITS can be any multiple of 8 from 8 to 56 (inclusive). +// Pick values that fit natural register size. + +#if !defined(WEBP_REFERENCE_IMPLEMENTATION) + +#define USE_RIGHT_JUSTIFY + +#if defined(__i386__) || defined(_M_IX86) // x86 32bit +#define BITS 16 +#elif defined(__x86_64__) || defined(_M_X64) // x86 64bit +#define BITS 56 +#elif defined(__arm__) || defined(_M_ARM) // ARM +#define BITS 24 +#else // reasonable default +#define BITS 24 +#endif + +#else // reference choices + +#define USE_RIGHT_JUSTIFY +#define BITS 8 + +#endif + +//------------------------------------------------------------------------------ +// Derived types and constants + +// bit_t = natural register type +// lbit_t = natural type for memory I/O + +#if (BITS > 32) +typedef uint64_t bit_t; +typedef uint64_t lbit_t; +#elif (BITS == 32) +typedef uint64_t bit_t; +typedef uint32_t lbit_t; +#elif (BITS == 24) +typedef uint32_t bit_t; +typedef uint32_t lbit_t; +#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 + +#ifndef USE_RIGHT_JUSTIFY +typedef bit_t range_t; // type for storing range_ +#define MASK ((((bit_t)1) << (BITS)) - 1) +#else +typedef uint32_t range_t; // range_ only uses 8bits here. No need for bit_t. +#endif + +//------------------------------------------------------------------------------ +// Bitreader + +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 + range_t range_; // current range minus 1. In [127, 254] interval. + bit_t value_; // current value + int bits_; // number of valid bits left +}; + +// 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 range_t kVP8NewRange[128]; + +void VP8LoadFinalBytes(VP8BitReader* const br); // special case for the tail + +static WEBP_INLINE void VP8LoadNewBytes(VP8BitReader* const br) { + assert(br != NULL && br->buf_ != NULL); + // Read 'BITS' bits at a time if possible. + if (br->buf_ + sizeof(lbit_t) <= br->buf_end_) { + // convert memory type to register type (with some zero'ing!) + bit_t bits; + const lbit_t in_bits = *(const lbit_t*)br->buf_; + br->buf_ += (BITS) >> 3; +#if !defined(__BIG_ENDIAN__) +#if (BITS > 32) +// gcc 4.3 has builtin functions for swap32/swap64 +#if defined(__GNUC__) && \ + (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3)) + bits = (bit_t)__builtin_bswap64(in_bits); +#elif defined(_MSC_VER) + bits = (bit_t)_byteswap_uint64(in_bits); +#elif defined(__x86_64__) + __asm__ volatile("bswapq %0" : "=r"(bits) : "0"(in_bits)); +#else // generic code for swapping 64-bit values (suggested by bdb@) + bits = (bit_t)in_bits; + bits = ((bits & 0xffffffff00000000ull) >> 32) | + ((bits & 0x00000000ffffffffull) << 32); + bits = ((bits & 0xffff0000ffff0000ull) >> 16) | + ((bits & 0x0000ffff0000ffffull) << 16); + bits = ((bits & 0xff00ff00ff00ff00ull) >> 8) | + ((bits & 0x00ff00ff00ff00ffull) << 8); +#endif + bits >>= 64 - BITS; +#elif (BITS >= 24) +#if defined(__i386__) || defined(__x86_64__) + { + lbit_t swapped_in_bits; + __asm__ volatile("bswap %k0" : "=r"(swapped_in_bits) : "0"(in_bits)); + bits = (bit_t)swapped_in_bits; // 24b/32b -> 32b/64b zero-extension + } +#elif defined(_MSC_VER) + bits = (bit_t)_byteswap_ulong(in_bits); +#else + bits = (bit_t)(in_bits >> 24) | ((in_bits >> 8) & 0xff00) + | ((in_bits << 8) & 0xff0000) | (in_bits << 24); +#endif // x86 + bits >>= (32 - BITS); +#elif (BITS == 16) + // gcc will recognize a 'rorw $8, ...' here: + bits = (bit_t)(in_bits >> 8) | ((in_bits & 0xff) << 8); +#else // BITS == 8 + bits = (bit_t)in_bits; +#endif +#else // BIG_ENDIAN + bits = (bit_t)in_bits; + if (BITS != 8 * sizeof(bit_t)) bits >>= (8 * sizeof(bit_t) - BITS); +#endif +#ifndef USE_RIGHT_JUSTIFY + br->value_ |= bits << (-br->bits_); +#else + br->value_ = bits | (br->value_ << (BITS)); +#endif + br->bits_ += (BITS); + } else { + VP8LoadFinalBytes(br); // no need to be inlined + } +} + +static WEBP_INLINE int VP8BitUpdate(VP8BitReader* const br, range_t split) { + if (br->bits_ < 0) { // Make sure we have a least BITS bits in 'value_' + VP8LoadNewBytes(br); + } +#ifndef USE_RIGHT_JUSTIFY + split |= (MASK); + if (br->value_ > split) { + br->range_ -= split + 1; + br->value_ -= split + 1; + return 1; + } else { + br->range_ = split; + return 0; + } +#else + { + const int pos = br->bits_; + const range_t value = (range_t)(br->value_ >> pos); + if (value > split) { + br->range_ -= split + 1; + br->value_ -= (bit_t)(split + 1) << pos; + return 1; + } else { + br->range_ = split; + return 0; + } + } +#endif +} + +static WEBP_INLINE void VP8Shift(VP8BitReader* const br) { +#ifndef USE_RIGHT_JUSTIFY + // range_ is in [0..127] interval here. + const bit_t idx = br->range_ >> (BITS); + const int shift = kVP8Log2Range[idx]; + br->range_ = kVP8NewRange[idx]; + br->value_ <<= shift; + br->bits_ -= shift; +#else + const int shift = kVP8Log2Range[br->range_]; + assert(br->range_ < (range_t)128); + br->range_ = kVP8NewRange[br->range_]; + br->bits_ -= shift; +#endif +} + +static WEBP_INLINE int VP8GetBit(VP8BitReader* const br, int prob) { +#ifndef USE_RIGHT_JUSTIFY + // It's important to avoid generating a 64bit x 64bit multiply here. + // We just need an 8b x 8b after all. + const range_t split = + (range_t)((uint32_t)(br->range_ >> (BITS)) * prob) << ((BITS) - 8); + const int bit = VP8BitUpdate(br, split); + if (br->range_ <= (((range_t)0x7e << (BITS)) | (MASK))) { + VP8Shift(br); + } + return bit; +#else + const range_t split = (br->range_ * prob) >> 8; + const int bit = VP8BitUpdate(br, split); + if (br->range_ <= (range_t)0x7e) { + VP8Shift(br); + } + return bit; +#endif +} + +static WEBP_INLINE int VP8GetSigned(VP8BitReader* const br, int v) { + const range_t split = (br->range_ >> 1); + const int bit = VP8BitUpdate(br, split); + VP8Shift(br); + return bit ? -v : v; +} + +// ----------------------------------------------------------------------------- +// Bitreader for lossless format + +typedef uint64_t vp8l_val_t; // right now, this bit-reader can only use 64bit. + +typedef struct { + vp8l_val_t val_; // pre-fetched bits + const uint8_t* buf_; // input byte buffer + size_t len_; // buffer length + size_t pos_; // byte position in buf_ + int bit_pos_; // current bit-reading position in val_ + int eos_; // bitstream is finished + int error_; // an error occurred (buffer overflow attempt...) +} 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); + +// Return the prefetched bits, so they can be looked up. +static WEBP_INLINE uint32_t VP8LPrefetchBits(VP8LBitReader* const br) { + return (uint32_t)(br->val_ >> br->bit_pos_); +} + +// For jumping over a number of bits in the bit stream when accessed with +// VP8LPrefetchBits and VP8LFillBitWindow. +static WEBP_INLINE void VP8LSetBitPos(VP8LBitReader* const br, int val) { + br->bit_pos_ = val; +} + +// Advances the read buffer by 4 bytes to make room for reading next 32 bits. +void VP8LFillBitWindow(VP8LBitReader* const br); + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_BIT_READER_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/bit_writer.c b/src/3rdparty/libwebp/src/utils/bit_writer.c new file mode 100644 index 0000000..29810a1 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/bit_writer.c @@ -0,0 +1,282 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Bit writing and boolean coder +// +// Author: Skal (pascal.massimino@gmail.com) +// Vikas Arora (vikaas.arora@gmail.com) + +#include <assert.h> +#include <string.h> // for memcpy() +#include <stdlib.h> +#include "./bit_writer.h" + +//------------------------------------------------------------------------------ +// VP8BitWriter + +static int BitWriterResize(VP8BitWriter* const bw, size_t extra_size) { + uint8_t* new_buf; + size_t new_size; + const uint64_t needed_size_64b = (uint64_t)bw->pos_ + extra_size; + const size_t needed_size = (size_t)needed_size_64b; + if (needed_size_64b != needed_size) { + bw->error_ = 1; + return 0; + } + if (needed_size <= bw->max_pos_) return 1; + // If the following line wraps over 32bit, the test just after will catch it. + new_size = 2 * bw->max_pos_; + if (new_size < needed_size) new_size = needed_size; + if (new_size < 1024) new_size = 1024; + new_buf = (uint8_t*)malloc(new_size); + if (new_buf == NULL) { + bw->error_ = 1; + return 0; + } + if (bw->pos_ > 0) { + assert(bw->buf_ != NULL); + memcpy(new_buf, bw->buf_, bw->pos_); + } + 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 arithmetic + *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; + } + } +} + +//------------------------------------------------------------------------------ + diff --git a/src/3rdparty/libwebp/src/utils/bit_writer.h b/src/3rdparty/libwebp/src/utils/bit_writer.h new file mode 100644 index 0000000..89a9ead --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/bit_writer.h @@ -0,0 +1,125 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Bit writing and boolean coder +// +// Author: Skal (pascal.massimino@gmail.com) + +#ifndef WEBP_UTILS_BIT_WRITER_H_ +#define WEBP_UTILS_BIT_WRITER_H_ + +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +//------------------------------------------------------------------------------ +// Bit-writing + +typedef struct VP8BitWriter VP8BitWriter; +struct VP8BitWriter { + int32_t range_; // range-1 + int32_t value_; + int run_; // number of outstanding bits + int nb_bits_; // number of pending bits + uint8_t* buf_; // internal buffer. Re-allocated regularly. Not owned. + size_t pos_; + size_t max_pos_; + int error_; // true in case of error +}; + +// Initialize the object. Allocates some initial memory based on expected_size. +int VP8BitWriterInit(VP8BitWriter* const bw, size_t expected_size); +// Finalize the bitstream coding. Returns a pointer to the internal buffer. +uint8_t* VP8BitWriterFinish(VP8BitWriter* const bw); +// Release any pending memory and zeroes the object. Not a mandatory call. +// Only useful in case of error, when the internal buffer hasn't been grabbed! +void VP8BitWriterWipeOut(VP8BitWriter* const bw); + +int VP8PutBit(VP8BitWriter* const bw, int bit, int prob); +int VP8PutBitUniform(VP8BitWriter* const bw, int bit); +void 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); + +//------------------------------------------------------------------------------ + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_BIT_WRITER_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/color_cache.c b/src/3rdparty/libwebp/src/utils/color_cache.c new file mode 100644 index 0000000..66a4464 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/color_cache.c @@ -0,0 +1,39 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Color Cache for WebP Lossless +// +// Author: Jyrki Alakuijala (jyrki@google.com) + +#include <assert.h> +#include <stdlib.h> +#include "./color_cache.h" +#include "../utils/utils.h" + +//------------------------------------------------------------------------------ +// 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; + } +} + diff --git a/src/3rdparty/libwebp/src/utils/color_cache.h b/src/3rdparty/libwebp/src/utils/color_cache.h new file mode 100644 index 0000000..0f824ed --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/color_cache.h @@ -0,0 +1,70 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Color Cache for WebP Lossless +// +// Authors: Jyrki Alakuijala (jyrki@google.com) +// Urvang Joshi (urvang@google.com) + +#ifndef WEBP_UTILS_COLOR_CACHE_H_ +#define WEBP_UTILS_COLOR_CACHE_H_ + +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +// Main color cache struct. +typedef struct { + uint32_t *colors_; // color entries + int hash_shift_; // Hash shift: 32 - hash_bits. +} 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); + +//------------------------------------------------------------------------------ + +#ifdef __cplusplus +} +#endif + +#endif // WEBP_UTILS_COLOR_CACHE_H_ diff --git a/src/3rdparty/libwebp/src/utils/filters.c b/src/3rdparty/libwebp/src/utils/filters.c new file mode 100644 index 0000000..2d15bd0 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/filters.c @@ -0,0 +1,266 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Spatial prediction using various filters +// +// Author: Urvang (urvang@google.com) + +#include "./filters.h" +#include <assert.h> +#include <stdlib.h> +#include <string.h> + +//------------------------------------------------------------------------------ +// Helpful macro. + +# define SANITY_CHECK(in, out) \ + assert(in != NULL); \ + assert(out != NULL); \ + assert(width > 0); \ + assert(height > 0); \ + assert(stride >= width); \ + assert(row >= 0 && num_rows > 0 && row + num_rows <= height); \ + (void)height; // Silence unused warning. + +static WEBP_INLINE void PredictLine(const uint8_t* src, const uint8_t* pred, + uint8_t* dst, int length, int inverse) { + int i; + if (inverse) { + for (i = 0; i < length; ++i) dst[i] = src[i] + pred[i]; + } else { + for (i = 0; i < length; ++i) dst[i] = src[i] - pred[i]; + } +} + +//------------------------------------------------------------------------------ +// Horizontal filter. + +static WEBP_INLINE void DoHorizontalFilter(const uint8_t* in, + int width, int height, int stride, + int row, int num_rows, + int inverse, uint8_t* out) { + const uint8_t* preds; + const size_t start_offset = row * stride; + const int last_row = row + num_rows; + SANITY_CHECK(in, out); + in += start_offset; + out += start_offset; + preds = inverse ? out : in; + + if (row == 0) { + // Leftmost pixel is the same as input for topmost scanline. + out[0] = in[0]; + PredictLine(in + 1, preds, out + 1, width - 1, inverse); + row = 1; + preds += stride; + in += stride; + out += stride; + } + + // Filter line-by-line. + while (row < last_row) { + // Leftmost pixel is predicted from above. + PredictLine(in, preds - stride, out, 1, inverse); + PredictLine(in + 1, preds, out + 1, width - 1, inverse); + ++row; + preds += stride; + in += stride; + out += stride; + } +} + +static void HorizontalFilter(const uint8_t* data, int width, int height, + int stride, uint8_t* filtered_data) { + DoHorizontalFilter(data, width, height, stride, 0, height, 0, filtered_data); +} + +static void HorizontalUnfilter(int width, int height, int stride, int row, + int num_rows, uint8_t* data) { + DoHorizontalFilter(data, width, height, stride, row, num_rows, 1, data); +} + +//------------------------------------------------------------------------------ +// Vertical filter. + +static WEBP_INLINE void DoVerticalFilter(const uint8_t* in, + int width, int height, int stride, + int row, int num_rows, + int inverse, uint8_t* out) { + const uint8_t* preds; + const size_t start_offset = row * stride; + const int last_row = row + num_rows; + SANITY_CHECK(in, out); + in += start_offset; + out += start_offset; + preds = inverse ? out : in; + + if (row == 0) { + // Very first top-left pixel is copied. + out[0] = in[0]; + // Rest of top scan-line is left-predicted. + PredictLine(in + 1, preds, out + 1, width - 1, inverse); + row = 1; + in += stride; + out += stride; + } else { + // We are starting from in-between. Make sure 'preds' points to prev row. + preds -= stride; + } + + // Filter line-by-line. + while (row < last_row) { + PredictLine(in, preds, out, width, inverse); + ++row; + preds += stride; + in += stride; + out += stride; + } +} + +static void VerticalFilter(const uint8_t* data, int width, int height, + int stride, uint8_t* filtered_data) { + DoVerticalFilter(data, width, height, stride, 0, height, 0, filtered_data); +} + +static void VerticalUnfilter(int width, int height, int stride, int row, + int num_rows, uint8_t* data) { + DoVerticalFilter(data, width, height, stride, row, num_rows, 1, data); +} + +//------------------------------------------------------------------------------ +// Gradient filter. + +static WEBP_INLINE int GradientPredictor(uint8_t a, uint8_t b, uint8_t c) { + const int g = a + b - c; + return ((g & ~0xff) == 0) ? g : (g < 0) ? 0 : 255; // clip to 8bit +} + +static WEBP_INLINE void DoGradientFilter(const uint8_t* in, + int width, int height, int stride, + int row, int num_rows, + int inverse, uint8_t* out) { + const uint8_t* preds; + const size_t start_offset = row * stride; + const int last_row = row + num_rows; + SANITY_CHECK(in, out); + in += start_offset; + out += start_offset; + preds = inverse ? out : in; + + // left prediction for top scan-line + if (row == 0) { + out[0] = in[0]; + PredictLine(in + 1, preds, out + 1, width - 1, inverse); + row = 1; + preds += stride; + in += stride; + out += stride; + } + + // Filter line-by-line. + while (row < last_row) { + int w; + // leftmost pixel: predict from above. + PredictLine(in, preds - stride, out, 1, inverse); + for (w = 1; w < width; ++w) { + const int pred = GradientPredictor(preds[w - 1], + preds[w - stride], + preds[w - stride - 1]); + out[w] = in[w] + (inverse ? pred : -pred); + } + ++row; + preds += stride; + in += stride; + out += stride; + } +} + +static void GradientFilter(const uint8_t* data, int width, int height, + int stride, uint8_t* filtered_data) { + DoGradientFilter(data, width, height, stride, 0, height, 0, filtered_data); +} + +static void GradientUnfilter(int width, int height, int stride, int row, + int num_rows, uint8_t* data) { + DoGradientFilter(data, width, height, stride, row, num_rows, 1, data); +} + +#undef SANITY_CHECK + +// ----------------------------------------------------------------------------- +// Quick estimate of a potentially interesting filter mode to try. + +#define SMAX 16 +#define SDIFF(a, b) (abs((a) - (b)) >> 4) // Scoring diff, in [0..SMAX) + +WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, + int width, int height, int stride) { + int i, j; + int bins[WEBP_FILTER_LAST][SMAX]; + memset(bins, 0, sizeof(bins)); + + // We only sample every other pixels. That's enough. + for (j = 2; j < height - 1; j += 2) { + const uint8_t* const p = data + j * stride; + int mean = p[0]; + for (i = 2; i < width - 1; i += 2) { + const int diff0 = SDIFF(p[i], mean); + const int diff1 = SDIFF(p[i], p[i - 1]); + const int diff2 = SDIFF(p[i], p[i - width]); + const int grad_pred = + GradientPredictor(p[i - 1], p[i - width], p[i - width - 1]); + const int diff3 = SDIFF(p[i], grad_pred); + bins[WEBP_FILTER_NONE][diff0] = 1; + bins[WEBP_FILTER_HORIZONTAL][diff1] = 1; + bins[WEBP_FILTER_VERTICAL][diff2] = 1; + bins[WEBP_FILTER_GRADIENT][diff3] = 1; + mean = (3 * mean + p[i] + 2) >> 2; + } + } + { + int filter; + WEBP_FILTER_TYPE best_filter = WEBP_FILTER_NONE; + int best_score = 0x7fffffff; + for (filter = WEBP_FILTER_NONE; filter < WEBP_FILTER_LAST; ++filter) { + int score = 0; + for (i = 0; i < SMAX; ++i) { + if (bins[filter][i] > 0) { + score += i; + } + } + if (score < best_score) { + best_score = score; + best_filter = (WEBP_FILTER_TYPE)filter; + } + } + return best_filter; + } +} + +#undef SMAX +#undef SDIFF + +//------------------------------------------------------------------------------ + +const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST] = { + NULL, // WEBP_FILTER_NONE + HorizontalFilter, // WEBP_FILTER_HORIZONTAL + VerticalFilter, // WEBP_FILTER_VERTICAL + GradientFilter // WEBP_FILTER_GRADIENT +}; + +const WebPUnfilterFunc WebPUnfilters[WEBP_FILTER_LAST] = { + NULL, // WEBP_FILTER_NONE + HorizontalUnfilter, // WEBP_FILTER_HORIZONTAL + VerticalUnfilter, // WEBP_FILTER_VERTICAL + GradientUnfilter // WEBP_FILTER_GRADIENT +}; + +//------------------------------------------------------------------------------ + diff --git a/src/3rdparty/libwebp/src/utils/filters.h b/src/3rdparty/libwebp/src/utils/filters.h new file mode 100644 index 0000000..dde39cb --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/filters.h @@ -0,0 +1,59 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Spatial prediction using various filters +// +// Author: Urvang (urvang@google.com) + +#ifndef WEBP_UTILS_FILTERS_H_ +#define WEBP_UTILS_FILTERS_H_ + +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +// Filters. +typedef enum { + WEBP_FILTER_NONE = 0, + WEBP_FILTER_HORIZONTAL, + WEBP_FILTER_VERTICAL, + WEBP_FILTER_GRADIENT, + WEBP_FILTER_LAST = WEBP_FILTER_GRADIENT + 1, // end marker + WEBP_FILTER_BEST, + WEBP_FILTER_FAST +} WEBP_FILTER_TYPE; + +typedef void (*WebPFilterFunc)(const uint8_t* in, int width, int height, + int stride, uint8_t* out); +typedef void (*WebPUnfilterFunc)(int width, int height, int stride, + int row, int num_rows, uint8_t* data); + +// Filter the given data using the given predictor. +// 'in' corresponds to a 2-dimensional pixel array of size (stride * height) +// in raster order. +// 'stride' is number of bytes per scan line (with possible padding). +// 'out' should be pre-allocated. +extern const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST]; + +// In-place reconstruct the original data from the given filtered data. +// The reconstruction will be done for 'num_rows' rows starting from 'row' +// (assuming rows upto 'row - 1' are already reconstructed). +extern const WebPUnfilterFunc WebPUnfilters[WEBP_FILTER_LAST]; + +// Fast estimate of a potentially good filter. +WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data, + int width, int height, int stride); + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_FILTERS_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/huffman.c b/src/3rdparty/libwebp/src/utils/huffman.c new file mode 100644 index 0000000..8c5739f --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/huffman.c @@ -0,0 +1,288 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Utilities for building and looking up Huffman trees. +// +// Author: Urvang Joshi (urvang@google.com) + +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#include "./huffman.h" +#include "../utils/utils.h" +#include "../webp/format_constants.h" + +// Uncomment the following to use look-up table for ReverseBits() +// (might be faster on some platform) +// #define USE_LUT_REVERSE_BITS + +#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; + assert(tree->max_nodes_ < (1 << 16)); // limit for the lut_jump_ table + 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; + memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_)); + memset(tree->lut_jump_, 0, sizeof(tree->lut_jump_)); + 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; +} + +#ifndef USE_LUT_REVERSE_BITS + +static int ReverseBitsShort(int bits, int num_bits) { + int retval = 0; + int i; + assert(num_bits <= 8); // Not a hard requirement, just for coherency. + for (i = 0; i < num_bits; ++i) { + retval <<= 1; + retval |= bits & 1; + bits >>= 1; + } + return retval; +} + +#else + +static const uint8_t kReversedBits[16] = { // Pre-reversed 4-bit values. + 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, + 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf +}; + +static int ReverseBitsShort(int bits, int num_bits) { + const uint8_t v = (kReversedBits[bits & 0xf] << 4) | kReversedBits[bits >> 4]; + assert(num_bits <= 8); + return v >> (8 - num_bits); +} + +#endif + +static int TreeAddSymbol(HuffmanTree* const tree, + int symbol, int code, int code_length) { + int step = HUFF_LUT_BITS; + int base_code; + HuffmanTreeNode* node = tree->root_; + const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_; + assert(symbol == (int16_t)symbol); + if (code_length <= HUFF_LUT_BITS) { + int i; + base_code = ReverseBitsShort(code, code_length); + for (i = 0; i < (1 << (HUFF_LUT_BITS - code_length)); ++i) { + const int idx = base_code | (i << code_length); + tree->lut_symbol_[idx] = (int16_t)symbol; + tree->lut_bits_[idx] = code_length; + } + } else { + base_code = ReverseBitsShort((code >> (code_length - HUFF_LUT_BITS)), + HUFF_LUT_BITS); + } + while (code_length-- > 0) { + if (node >= max_node) { + return 0; + } + if (NodeIsEmpty(node)) { + if (IsFull(tree)) return 0; // error: too many symbols. + AssignChildren(tree, node); + } else if (!HuffmanTreeNodeIsNotLeaf(node)) { + return 0; // leaf is already occupied. + } + node += node->children_ + ((code >> code_length) & 1); + if (--step == 0) { + tree->lut_jump_[base_code] = (int16_t)(node - tree->root_); + } + } + if (NodeIsEmpty(node)) { + node->children_ = 0; // turn newly created node into a leaf. + } else if (HuffmanTreeNodeIsNotLeaf(node)) { + return 0; // trying to assign a symbol to already used code. + } + 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; +} + diff --git a/src/3rdparty/libwebp/src/utils/huffman.h b/src/3rdparty/libwebp/src/utils/huffman.h new file mode 100644 index 0000000..e8afd27 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/huffman.h @@ -0,0 +1,87 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Utilities for building and looking up Huffman trees. +// +// Author: Urvang Joshi (urvang@google.com) + +#ifndef WEBP_UTILS_HUFFMAN_H_ +#define WEBP_UTILS_HUFFMAN_H_ + +#include <assert.h> +#include "../webp/types.h" + +#ifdef __cplusplus +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. +#define HUFF_LUT_BITS 7 +#define HUFF_LUT (1U << HUFF_LUT_BITS) +typedef struct HuffmanTree HuffmanTree; +struct HuffmanTree { + // Fast lookup for short bit lengths. + uint8_t lut_bits_[HUFF_LUT]; + int16_t lut_symbol_[HUFF_LUT]; + int16_t lut_jump_[HUFF_LUT]; + // Complete tree for lookups. + HuffmanTreeNode* root_; // all the nodes, starting at root. + int max_nodes_; // max number of nodes + int num_nodes_; // number of currently occupied nodes +}; + +// Returns true if the given node is not a leaf of the Huffman tree. +static WEBP_INLINE int HuffmanTreeNodeIsNotLeaf( + const HuffmanTreeNode* const node) { + return node->children_; +} + +// Go down one level. Most critical function. 'right_child' must be 0 or 1. +static WEBP_INLINE const HuffmanTreeNode* HuffmanTreeNextNode( + const HuffmanTreeNode* node, int right_child) { + return node + node->children_ + right_child; +} + +// Releases the nodes of the Huffman tree. +// Note: It does NOT free 'tree' itself. +void 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); + + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif // WEBP_UTILS_HUFFMAN_H_ diff --git a/src/3rdparty/libwebp/src/utils/huffman_encode.c b/src/3rdparty/libwebp/src/utils/huffman_encode.c new file mode 100644 index 0000000..9c59867 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/huffman_encode.c @@ -0,0 +1,440 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Author: Jyrki Alakuijala (jyrki@google.com) +// +// Entropy encoding (Huffman) for webp lossless. + +#include <assert.h> +#include <stdlib.h> +#include <string.h> +#include "./huffman_encode.h" +#include "../utils/utils.h" +#include "../webp/format_constants.h" + +// ----------------------------------------------------------------------------- +// Util function to optimize the symbol map for RLE coding + +// Heuristics for selecting the stride ranges to collapse. +static int ValuesShouldBeCollapsedToStrideAverage(int a, int b) { + return abs(a - b) < 4; +} + +// Change the population counts in a way that the consequent +// Huffman tree compression, especially its RLE-part, give smaller output. +static 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 { + assert(t1->value_ != t2->value_); + return (t1->value_ < t2->value_) ? -1 : 1; + } +} + +static void SetBitDepths(const HuffmanTree* const tree, + const HuffmanTree* const pool, + uint8_t* const bit_depths, int level) { + if (tree->pool_index_left_ >= 0) { + SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1); + SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1); + } else { + bit_depths[tree->value_] = level; + } +} + +// Create an optimal Huffman tree. +// +// (data,length): population counts. +// tree_limit: maximum bit depth (inclusive) of the codes. +// bit_depths[]: how many bits are used for the symbol. +// +// Returns 0 when an error has occurred. +// +// The catch here is that the tree cannot be arbitrarily deep +// +// count_limit is the value that is to be faked as the minimum value +// and this minimum value is raised until the tree matches the +// maximum length requirement. +// +// This algorithm is not of excellent performance for very long data blocks, +// especially when population counts are longer than 2**tree_limit, but +// we are not planning to use this with extremely long blocks. +// +// See 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; + } + } + + if (tree_size_orig == 0) { // pretty optimal already! + return 1; + } + + // 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/src/3rdparty/libwebp/src/utils/huffman_encode.h b/src/3rdparty/libwebp/src/utils/huffman_encode.h new file mode 100644 index 0000000..ee51c68 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/huffman_encode.h @@ -0,0 +1,49 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Author: Jyrki Alakuijala (jyrki@google.com) +// +// Entropy encoding (Huffman) for webp lossless + +#ifndef WEBP_UTILS_HUFFMAN_ENCODE_H_ +#define WEBP_UTILS_HUFFMAN_ENCODE_H_ + +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +// Struct for holding the tree header in coded form. +typedef struct { + uint8_t code; // value (0..15) or escape code (16,17,18) + uint8_t extra_bits; // extra bits for escape codes +} HuffmanTreeToken; + +// Struct to represent the tree codes (depth and bits array). +typedef struct { + int num_symbols; // Number of symbols. + uint8_t* code_lengths; // Code lengths of the symbols. + uint16_t* codes; // Symbol Codes. +} HuffmanTreeCode; + +// 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); + +#ifdef __cplusplus +} +#endif + +#endif // WEBP_UTILS_HUFFMAN_ENCODE_H_ diff --git a/src/3rdparty/libwebp/src/utils/quant_levels.c b/src/3rdparty/libwebp/src/utils/quant_levels.c new file mode 100644 index 0000000..d7c8aab --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/quant_levels.c @@ -0,0 +1,140 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Quantize levels for specified number of quantization-levels ([2, 256]). +// Min and max values are preserved (usual 0 and 255 for alpha plane). +// +// Author: Skal (pascal.massimino@gmail.com) + +#include <assert.h> + +#include "./quant_levels.h" + +#define NUM_SYMBOLS 256 + +#define MAX_ITER 6 // Maximum number of convergence steps. +#define ERROR_THRESHOLD 1e-4 // MSE stopping criterion. + +// ----------------------------------------------------------------------------- +// Quantize levels. + +int QuantizeLevels(uint8_t* const data, int width, int height, + int num_levels, uint64_t* const sse) { + int freq[NUM_SYMBOLS] = { 0 }; + int q_level[NUM_SYMBOLS] = { 0 }; + double inv_q_level[NUM_SYMBOLS] = { 0 }; + int min_s = 255, max_s = 0; + const size_t data_size = height * width; + int i, num_levels_in, iter; + double last_err = 1.e38, err = 0.; + const double err_threshold = ERROR_THRESHOLD * data_size; + + if (data == NULL) { + return 0; + } + + if (width <= 0 || height <= 0) { + return 0; + } + + if (num_levels < 2 || num_levels > 256) { + return 0; + } + + { + size_t n; + num_levels_in = 0; + for (n = 0; n < data_size; ++n) { + num_levels_in += (freq[data[n]] == 0); + if (min_s > data[n]) min_s = data[n]; + if (max_s < data[n]) max_s = data[n]; + ++freq[data[n]]; + } + } + + if (num_levels_in <= num_levels) goto End; // nothing to do! + + // Start with uniformly spread centroids. + for (i = 0; i < num_levels; ++i) { + inv_q_level[i] = min_s + (double)(max_s - min_s) * i / (num_levels - 1); + } + + // Fixed values. Won't be changed. + q_level[min_s] = 0; + q_level[max_s] = num_levels - 1; + assert(inv_q_level[0] == min_s); + assert(inv_q_level[num_levels - 1] == max_s); + + // k-Means iterations. + for (iter = 0; iter < MAX_ITER; ++iter) { + double q_sum[NUM_SYMBOLS] = { 0 }; + double q_count[NUM_SYMBOLS] = { 0 }; + int s, slot = 0; + + // Assign classes to representatives. + for (s = min_s; s <= max_s; ++s) { + // Keep track of the nearest neighbour 'slot' + while (slot < num_levels - 1 && + 2 * s > inv_q_level[slot] + inv_q_level[slot + 1]) { + ++slot; + } + if (freq[s] > 0) { + q_sum[slot] += s * freq[s]; + q_count[slot] += freq[s]; + } + q_level[s] = slot; + } + + // Assign new representatives to classes. + if (num_levels > 2) { + for (slot = 1; slot < num_levels - 1; ++slot) { + const double count = q_count[slot]; + if (count > 0.) { + inv_q_level[slot] = q_sum[slot] / count; + } + } + } + + // Compute convergence error. + err = 0.; + for (s = min_s; s <= max_s; ++s) { + const double error = s - inv_q_level[q_level[s]]; + err += freq[s] * error * error; + } + + // Check for convergence: we stop as soon as the error is no + // longer improving. + if (last_err - err < err_threshold) break; + last_err = err; + } + + // Remap the alpha plane to quantized values. + { + // double->int rounding operation can be costly, so we do it + // once for all before remapping. We also perform the data[] -> slot + // mapping, while at it (avoid one indirection in the final loop). + uint8_t map[NUM_SYMBOLS]; + int s; + size_t n; + for (s = min_s; s <= max_s; ++s) { + const int slot = q_level[s]; + map[s] = (uint8_t)(inv_q_level[slot] + .5); + } + // Final pass. + for (n = 0; n < data_size; ++n) { + data[n] = map[data[n]]; + } + } + End: + // Store sum of squared error if needed. + if (sse != NULL) *sse = (uint64_t)err; + + return 1; +} + diff --git a/src/3rdparty/libwebp/src/utils/quant_levels.h b/src/3rdparty/libwebp/src/utils/quant_levels.h new file mode 100644 index 0000000..1cb5a32 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/quant_levels.h @@ -0,0 +1,36 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Alpha plane quantization utility +// +// Author: Vikas Arora (vikasa@google.com) + +#ifndef WEBP_UTILS_QUANT_LEVELS_H_ +#define WEBP_UTILS_QUANT_LEVELS_H_ + +#include <stdlib.h> + +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +// Replace the input 'data' of size 'width'x'height' with 'num-levels' +// quantized values. If not NULL, 'sse' will contain the sum of squared error. +// Valid range for 'num_levels' is [2, 256]. +// Returns false in case of error (data is NULL, or parameters are invalid). +int QuantizeLevels(uint8_t* const data, int width, int height, int num_levels, + uint64_t* const sse); + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_QUANT_LEVELS_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/quant_levels_dec.c b/src/3rdparty/libwebp/src/utils/quant_levels_dec.c new file mode 100644 index 0000000..8489705 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/quant_levels_dec.c @@ -0,0 +1,24 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// TODO(skal): implement gradient smoothing. +// +// Author: Skal (pascal.massimino@gmail.com) + +#include "./quant_levels_dec.h" + +int DequantizeLevels(uint8_t* const data, int width, int height, + int row, int num_rows) { + if (data == NULL || width <= 0 || height <= 0 || row < 0 || num_rows < 0 || + row + num_rows > height) { + return 0; + } + return 1; +} + diff --git a/src/3rdparty/libwebp/src/utils/quant_levels_dec.h b/src/3rdparty/libwebp/src/utils/quant_levels_dec.h new file mode 100644 index 0000000..0288383 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/quant_levels_dec.h @@ -0,0 +1,34 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Alpha plane de-quantization utility +// +// Author: Vikas Arora (vikasa@google.com) + +#ifndef WEBP_UTILS_QUANT_LEVELS_DEC_H_ +#define WEBP_UTILS_QUANT_LEVELS_DEC_H_ + +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +// Apply post-processing to input 'data' of size 'width'x'height' assuming that +// the source was quantized to a reduced number of levels. The post-processing +// will be applied to 'num_rows' rows of 'data' starting from 'row'. +// Returns false in case of error (data is NULL, invalid parameters, ...). +int DequantizeLevels(uint8_t* const data, int width, int height, + int row, int num_rows); + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_QUANT_LEVELS_DEC_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/random.c b/src/3rdparty/libwebp/src/utils/random.c new file mode 100644 index 0000000..24e96ad --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/random.c @@ -0,0 +1,43 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Pseudo-random utilities +// +// Author: Skal (pascal.massimino@gmail.com) + +#include <string.h> +#include "./random.h" + +//------------------------------------------------------------------------------ + +// 31b-range values +static const uint32_t kRandomTable[VP8_RANDOM_TABLE_SIZE] = { + 0x0de15230, 0x03b31886, 0x775faccb, 0x1c88626a, 0x68385c55, 0x14b3b828, + 0x4a85fef8, 0x49ddb84b, 0x64fcf397, 0x5c550289, 0x4a290000, 0x0d7ec1da, + 0x5940b7ab, 0x5492577d, 0x4e19ca72, 0x38d38c69, 0x0c01ee65, 0x32a1755f, + 0x5437f652, 0x5abb2c32, 0x0faa57b1, 0x73f533e7, 0x685feeda, 0x7563cce2, + 0x6e990e83, 0x4730a7ed, 0x4fc0d9c6, 0x496b153c, 0x4f1403fa, 0x541afb0c, + 0x73990b32, 0x26d7cb1c, 0x6fcc3706, 0x2cbb77d8, 0x75762f2a, 0x6425ccdd, + 0x24b35461, 0x0a7d8715, 0x220414a8, 0x141ebf67, 0x56b41583, 0x73e502e3, + 0x44cab16f, 0x28264d42, 0x73baaefb, 0x0a50ebed, 0x1d6ab6fb, 0x0d3ad40b, + 0x35db3b68, 0x2b081e83, 0x77ce6b95, 0x5181e5f0, 0x78853bbc, 0x009f9494, + 0x27e5ed3c +}; + +void VP8InitRandom(VP8Random* const rg, float dithering) { + memcpy(rg->tab_, kRandomTable, sizeof(rg->tab_)); + rg->index1_ = 0; + rg->index2_ = 31; + rg->amp_ = (dithering < 0.0) ? 0 + : (dithering > 1.0) ? (1 << VP8_RANDOM_DITHER_FIX) + : (uint32_t)((1 << VP8_RANDOM_DITHER_FIX) * dithering); +} + +//------------------------------------------------------------------------------ + diff --git a/src/3rdparty/libwebp/src/utils/random.h b/src/3rdparty/libwebp/src/utils/random.h new file mode 100644 index 0000000..08a83e9 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/random.h @@ -0,0 +1,62 @@ +// Copyright 2013 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Pseudo-random utilities +// +// Author: Skal (pascal.massimino@gmail.com) + +#ifndef WEBP_UTILS_RANDOM_H_ +#define WEBP_UTILS_RANDOM_H_ + +#include <assert.h> +#include "../webp/types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +#define VP8_RANDOM_DITHER_FIX 8 // fixed-point precision for dithering +#define VP8_RANDOM_TABLE_SIZE 55 + +typedef struct { + int index1_, index2_; + uint32_t tab_[VP8_RANDOM_TABLE_SIZE]; + int amp_; +} VP8Random; + +// Initializes random generator with an amplitude 'dithering' in range [0..1]. +void VP8InitRandom(VP8Random* const rg, float dithering); + +// Returns a centered pseudo-random number with 'num_bits' amplitude. +// (uses D.Knuth's Difference-based random generator). +// 'amp' is in VP8_RANDOM_DITHER_FIX fixed-point precision. +static WEBP_INLINE int VP8RandomBits2(VP8Random* const rg, int num_bits, + int amp) { + int diff; + assert(num_bits + VP8_RANDOM_DITHER_FIX <= 31); + diff = rg->tab_[rg->index1_] - rg->tab_[rg->index2_]; + if (diff < 0) diff += (1u << 31); + rg->tab_[rg->index1_] = diff; + if (++rg->index1_ == VP8_RANDOM_TABLE_SIZE) rg->index1_ = 0; + if (++rg->index2_ == VP8_RANDOM_TABLE_SIZE) rg->index2_ = 0; + diff = (diff << 1) >> (32 - num_bits); // sign-extend, 0-center + diff = (diff * amp) >> VP8_RANDOM_DITHER_FIX; // restrict range + diff += 1 << (num_bits - 1); // shift back to 0.5-center + return diff; +} + +static WEBP_INLINE int VP8RandomBits(VP8Random* const rg, int num_bits) { + return VP8RandomBits2(rg, num_bits, rg->amp_); +} + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_RANDOM_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/rescaler.c b/src/3rdparty/libwebp/src/utils/rescaler.c new file mode 100644 index 0000000..7061246 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/rescaler.c @@ -0,0 +1,152 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Rescaling functions +// +// Author: Skal (pascal.massimino@gmail.com) + +#include <assert.h> +#include <stdlib.h> +#include "./rescaler.h" + +//------------------------------------------------------------------------------ + +#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 WebPRescaleNeededLines(const WebPRescaler* const wrk, int max_num_lines) { + const int num_lines = (wrk->y_accum + wrk->y_sub - 1) / wrk->y_sub; + return (num_lines > max_num_lines) ? max_num_lines : num_lines; +} + +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; +} + +//------------------------------------------------------------------------------ + diff --git a/src/3rdparty/libwebp/src/utils/rescaler.h b/src/3rdparty/libwebp/src/utils/rescaler.h new file mode 100644 index 0000000..68e49ce --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/rescaler.h @@ -0,0 +1,84 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Rescaling functions +// +// Author: Skal (pascal.massimino@gmail.com) + +#ifndef WEBP_UTILS_RESCALER_H_ +#define WEBP_UTILS_RESCALER_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include "../webp/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 rescaler, + 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); + +// Returns the number of input lines needed next to produce one output line, +// considering that the maximum available input lines are 'max_num_lines'. +int WebPRescaleNeededLines(const WebPRescaler* const rescaler, + int max_num_lines); + +// Import 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 rescaler); + +// Export as many rows as possible. Return the numbers of rows written. +int WebPRescalerExport(WebPRescaler* const rescaler); + +//------------------------------------------------------------------------------ + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_RESCALER_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/thread.c b/src/3rdparty/libwebp/src/utils/thread.c new file mode 100644 index 0000000..a9e3fae --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/thread.c @@ -0,0 +1,241 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Multi-threaded worker +// +// Author: Skal (pascal.massimino@gmail.com) + +#include <assert.h> +#include <string.h> // for memset() +#include "./thread.h" + +#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 // _WIN32 + +//------------------------------------------------------------------------------ + +static THREADFN ThreadLoop(void* ptr) { + 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) { + WebPWorkerExecute(worker); + worker->status_ = OK; + } else if (worker->status_ == NOT_OK) { // finish the worker + done = 1; + } + // signal to the main thread that we're done (for Sync()) + pthread_cond_signal(&worker->condition_); + pthread_mutex_unlock(&worker->mutex_); + } + return THREAD_RETURN(NULL); // Thread is finished +} + +// main thread state control +static void ChangeState(WebPWorker* const worker, + WebPWorkerStatus new_status) { + // no-op when attempting to change state on a thread that didn't come up + 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 // WEBP_USE_THREAD + +//------------------------------------------------------------------------------ + +void WebPWorkerInit(WebPWorker* const worker) { + memset(worker, 0, sizeof(*worker)); + worker->status_ = NOT_OK; +} + +int WebPWorkerSync(WebPWorker* const worker) { +#ifdef WEBP_USE_THREAD + ChangeState(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, ThreadLoop, 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 WebPWorkerExecute(WebPWorker* const worker) { + if (worker->hook != NULL) { + worker->had_error |= !worker->hook(worker->data1, worker->data2); + } +} + +void WebPWorkerLaunch(WebPWorker* const worker) { +#ifdef WEBP_USE_THREAD + ChangeState(worker, WORK); +#else + WebPWorkerExecute(worker); +#endif +} + +void WebPWorkerEnd(WebPWorker* const worker) { + if (worker->status_ >= OK) { +#ifdef WEBP_USE_THREAD + ChangeState(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); +} + +//------------------------------------------------------------------------------ + diff --git a/src/3rdparty/libwebp/src/utils/thread.h b/src/3rdparty/libwebp/src/utils/thread.h new file mode 100644 index 0000000..aef33bd --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/thread.h @@ -0,0 +1,97 @@ +// Copyright 2011 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Multi-threaded worker +// +// Author: Skal (pascal.massimino@gmail.com) + +#ifndef WEBP_UTILS_THREAD_H_ +#define WEBP_UTILS_THREAD_H_ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +#ifdef 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 { +#ifdef 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 to 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); +// Makes sure the previous work is finished. Returns true if worker->had_error +// was not set and no error condition was triggered by the working thread. +int WebPWorkerSync(WebPWorker* const worker); +// Triggers 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); +// This function is similar to WebPWorkerLaunch() except that it calls the +// hook directly instead of using a thread. Convenient to bypass the thread +// mechanism while still using the WebPWorker structs. WebPWorkerSync() must +// still be called afterward (for error reporting). +void WebPWorkerExecute(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); + +//------------------------------------------------------------------------------ + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_THREAD_H_ */ diff --git a/src/3rdparty/libwebp/src/utils/utils.c b/src/3rdparty/libwebp/src/utils/utils.c new file mode 100644 index 0000000..5592538 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/utils.c @@ -0,0 +1,42 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Misc. common utility functions +// +// Author: Skal (pascal.massimino@gmail.com) + +#include <stdlib.h> +#include "./utils.h" + +//------------------------------------------------------------------------------ +// Checked memory allocation + +// Returns 0 in case of overflow of nmemb * size. +static int CheckSizeArgumentsOverflow(uint64_t nmemb, size_t size) { + const uint64_t total_size = nmemb * size; + if (nmemb == 0) return 1; + if ((uint64_t)size > WEBP_MAX_ALLOCABLE_MEMORY / nmemb) return 0; + if (total_size != (size_t)total_size) return 0; + return 1; +} + +void* WebPSafeMalloc(uint64_t nmemb, size_t size) { + if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL; + assert(nmemb * size > 0); + return malloc((size_t)(nmemb * size)); +} + +void* WebPSafeCalloc(uint64_t nmemb, size_t size) { + if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL; + assert(nmemb * size > 0); + return calloc((size_t)nmemb, size); +} + +//------------------------------------------------------------------------------ + diff --git a/src/3rdparty/libwebp/src/utils/utils.h b/src/3rdparty/libwebp/src/utils/utils.h new file mode 100644 index 0000000..8bdf0f0 --- /dev/null +++ b/src/3rdparty/libwebp/src/utils/utils.h @@ -0,0 +1,83 @@ +// Copyright 2012 Google Inc. All Rights Reserved. +// +// Use of this source code is governed by a BSD-style license +// that can be found in the COPYING file in the root of the source +// tree. An additional intellectual property rights grant can be found +// in the file PATENTS. All contributing project authors may +// be found in the AUTHORS file in the root of the source tree. +// ----------------------------------------------------------------------------- +// +// Misc. common utility functions +// +// Authors: Skal (pascal.massimino@gmail.com) +// Urvang (urvang@google.com) + +#ifndef WEBP_UTILS_UTILS_H_ +#define WEBP_UTILS_UTILS_H_ + +#include <assert.h> + +#include "../webp/types.h" + +#ifdef __cplusplus +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); + +//------------------------------------------------------------------------------ +// Reading/writing data. + +// Read 16, 24 or 32 bits stored in little-endian order. +static WEBP_INLINE int GetLE16(const uint8_t* const data) { + return (int)(data[0] << 0) | (data[1] << 8); +} + +static WEBP_INLINE int GetLE24(const uint8_t* const data) { + return GetLE16(data) | (data[2] << 16); +} + +static WEBP_INLINE uint32_t GetLE32(const uint8_t* const data) { + return (uint32_t)GetLE16(data) | (GetLE16(data + 2) << 16); +} + +// Store 16, 24 or 32 bits in little-endian order. +static WEBP_INLINE void PutLE16(uint8_t* const data, int val) { + assert(val < (1 << 16)); + data[0] = (val >> 0); + data[1] = (val >> 8); +} + +static WEBP_INLINE void PutLE24(uint8_t* const data, int val) { + assert(val < (1 << 24)); + PutLE16(data, val & 0xffff); + data[2] = (val >> 16); +} + +static WEBP_INLINE void PutLE32(uint8_t* const data, uint32_t val) { + PutLE16(data, (int)(val & 0xffff)); + PutLE16(data + 2, (int)(val >> 16)); +} + +//------------------------------------------------------------------------------ + +#ifdef __cplusplus +} // extern "C" +#endif + +#endif /* WEBP_UTILS_UTILS_H_ */ |