diff options
| author | Liang Qi <liang.qi@digia.com> | 2014-01-23 11:21:03 +0100 |
|---|---|---|
| committer | The Qt Project <gerrit-noreply@qt-project.org> | 2014-02-13 08:41:28 +0100 |
| commit | ca167cb978d5687067a6f498adb2bd466440360f (patch) | |
| tree | f0f80c98c019651015786811df521ec6c93226e9 /src/3rdparty/libwebp/src/utils | |
| parent | 95b6cf26837dba0ac215db552ce47031f3abfc6e (diff) | |
Adding libwebp: Adding clean copy of libwebp 0.4.0
This commit imports libwebp 0.4.0, including AUTHORS, COPYING, ChangeLog,
NEWS, PATENTS, README and src directories. In src, only includes header
and source files.
The patches required to build it in Qt will follow in separate
commit(s).
Task-number: QTBUG-14205
Change-Id: I747918fe2a07716f66cffb795129f7aa5e067759
Reviewed-by: Lars Knoll <lars.knoll@digia.com>
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_ */ |