14b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/* 24b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Copyright 2012 Google Inc. 34b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * 44b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Use of this source code is governed by a BSD-style license that can be 54b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * found in the LICENSE file. 64b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 74b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 84b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#ifndef SkMathPriv_DEFINED 94b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#define SkMathPriv_DEFINED 104b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 114b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#include "SkMath.h" 124b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 134760f32f2a68acdcfee53eae98bbdabb19238e8dbungeman#if defined(SK_BUILD_FOR_IOS) && (defined(SK_BUILD_FOR_ARM32) || defined(SK_BUILD_FOR_ARM64)) 144760f32f2a68acdcfee53eae98bbdabb19238e8dbungeman// iOS on ARM starts processes with the Flush-To-Zero (FTZ) and 154760f32f2a68acdcfee53eae98bbdabb19238e8dbungeman// Denormals-Are-Zero (DAZ) bits in the fpscr register set. 16936b73424f7393994be832376287da988a52b993caryclark// Algorithms that rely on denormalized numbers need alternative implementations. 174760f32f2a68acdcfee53eae98bbdabb19238e8dbungeman// This can also be controlled in SSE with the MXCSR register, 184760f32f2a68acdcfee53eae98bbdabb19238e8dbungeman// x87 with FSTCW/FLDCW, and mips with FCSR. This should be detected at runtime, 194760f32f2a68acdcfee53eae98bbdabb19238e8dbungeman// or the library built one way or the other more generally (by the build). 204760f32f2a68acdcfee53eae98bbdabb19238e8dbungeman#define SK_CPU_FLUSH_TO_ZERO 21936b73424f7393994be832376287da988a52b993caryclark#endif 22936b73424f7393994be832376287da988a52b993caryclark 234b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** Returns -1 if n < 0, else returns 0 244b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 254b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#define SkExtractSign(n) ((int32_t)(n) >> 31) 264b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 274b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** If sign == -1, returns -n, else sign must be 0, and returns n. 284b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com Typically used in conjunction with SkExtractSign(). 294b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 304b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.comstatic inline int32_t SkApplySign(int32_t n, int32_t sign) { 314b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com SkASSERT(sign == 0 || sign == -1); 324b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com return (n ^ sign) - sign; 334b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com} 344b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 354b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** Return x with the sign of y */ 364b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.comstatic inline int32_t SkCopySign32(int32_t x, int32_t y) { 374b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com return SkApplySign(x, SkExtractSign(x ^ y)); 384b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com} 394b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 404b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** Given a positive value and a positive max, return the value 414b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com pinned against max. 424b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com Note: only works as long as max - value doesn't wrap around 434b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com @return max if value >= max, else value 444b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 454b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.comstatic inline unsigned SkClampUMax(unsigned value, unsigned max) { 464b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com if (value > max) { 474b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com value = max; 484b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com } 494b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com return value; 504b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com} 514b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 5245ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed// If a signed int holds min_int (e.g. 0x80000000) it is undefined what happens when 5345ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed// we negate it (even though we *know* we're 2's complement and we'll get the same 5445ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed// value back). So we create this helper function that casts to size_t (unsigned) first, 5545ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed// to avoid the complaint. 5645ab630045ec72dcc0c4546cc1e96ac518897896Mike Reedstatic inline size_t sk_negate_to_size_t(int32_t value) { 5745ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed#if defined(_MSC_VER) 5845ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed#pragma warning(push) 5945ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed#pragma warning(disable : 4146) // Thanks MSVC, we know what we're negating an unsigned 6045ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed#endif 6145ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed return -static_cast<size_t>(value); 6245ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed#if defined(_MSC_VER) 6345ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed#pragma warning(pop) 6445ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed#endif 6545ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed} 6645ab630045ec72dcc0c4546cc1e96ac518897896Mike Reed 674b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/////////////////////////////////////////////////////////////////////////////// 684b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 694b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** Return a*b/255, truncating away any fractional bits. Only valid if both 704b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com a and b are 0..255 714b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 724b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.comstatic inline U8CPU SkMulDiv255Trunc(U8CPU a, U8CPU b) { 734b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com SkASSERT((uint8_t)a == a); 744b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com SkASSERT((uint8_t)b == b); 753848427d884b72114854c8eef9662691f23fae7bmtklein unsigned prod = a*b + 1; 764b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com return (prod + (prod >> 8)) >> 8; 774b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com} 784b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 794b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** Return (a*b)/255, taking the ceiling of any fractional bits. Only valid if 804b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com both a and b are 0..255. The expected result equals (a * b + 254) / 255. 814b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 824b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.comstatic inline U8CPU SkMulDiv255Ceiling(U8CPU a, U8CPU b) { 834b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com SkASSERT((uint8_t)a == a); 844b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com SkASSERT((uint8_t)b == b); 853848427d884b72114854c8eef9662691f23fae7bmtklein unsigned prod = a*b + 255; 864b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com return (prod + (prod >> 8)) >> 8; 874b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com} 884b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 894b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** Just the rounding step in SkDiv255Round: round(value / 255) 904b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 914b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.comstatic inline unsigned SkDiv255Round(unsigned prod) { 924b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com prod += 128; 934b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com return (prod + (prod >> 8)) >> 8; 944b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com} 954b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 966d3cef930ad19b0f55543ca40f7a07030f4fe508reedstatic inline float SkPinToUnitFloat(float x) { 976d3cef930ad19b0f55543ca40f7a07030f4fe508reed return SkTMin(SkTMax(x, 0.0f), 1.0f); 986d3cef930ad19b0f55543ca40f7a07030f4fe508reed} 996d3cef930ad19b0f55543ca40f7a07030f4fe508reed 1006a377e629dc93e9d2cede4082a43e9f723f968e4mtklein/** 1016a377e629dc93e9d2cede4082a43e9f723f968e4mtklein * Swap byte order of a 4-byte value, e.g. 0xaarrggbb -> 0xbbggrraa. 1026a377e629dc93e9d2cede4082a43e9f723f968e4mtklein */ 1036a377e629dc93e9d2cede4082a43e9f723f968e4mtklein#if defined(_MSC_VER) 1046a377e629dc93e9d2cede4082a43e9f723f968e4mtklein #include <intrin.h> 1056a377e629dc93e9d2cede4082a43e9f723f968e4mtklein static inline uint32_t SkBSwap32(uint32_t v) { return _byteswap_ulong(v); } 1066a377e629dc93e9d2cede4082a43e9f723f968e4mtklein#else 1076a377e629dc93e9d2cede4082a43e9f723f968e4mtklein static inline uint32_t SkBSwap32(uint32_t v) { return __builtin_bswap32(v); } 1086a377e629dc93e9d2cede4082a43e9f723f968e4mtklein#endif 1096a377e629dc93e9d2cede4082a43e9f723f968e4mtklein 1104dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary//! Returns the number of leading zero bits (0...32) 1114dbbd04314cc0606f8d3bafe515c97e52c180f73halcanaryint SkCLZ_portable(uint32_t); 1124dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary 1134dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary#ifndef SkCLZ 1148f11d4dcafef4447fa68ea0ab28a72589241e9fdMike Klein #if defined(SK_BUILD_FOR_WIN) 1154dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary #include <intrin.h> 1164dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary 1174dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary static inline int SkCLZ(uint32_t mask) { 1184dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary if (mask) { 1194dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary unsigned long index; 1204dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary _BitScanReverse(&index, mask); 1214dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary // Suppress this bogus /analyze warning. The check for non-zero 1224dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary // guarantees that _BitScanReverse will succeed. 1234dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary#pragma warning(suppress : 6102) // Using 'index' from failed function call 1244dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary return index ^ 0x1F; 1254dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary } else { 1264dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary return 32; 1274dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary } 1284dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary } 1294dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary #elif defined(SK_CPU_ARM32) || defined(__GNUC__) || defined(__clang__) 1304dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary static inline int SkCLZ(uint32_t mask) { 1314dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary // __builtin_clz(0) is undefined, so we have to detect that case. 1324dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary return mask ? __builtin_clz(mask) : 32; 1334dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary } 1344dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary #else 1354dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary #define SkCLZ(x) SkCLZ_portable(x) 1364dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary #endif 1374dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary#endif 1384dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary 1394dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary/** 1404dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * Returns the smallest power-of-2 that is >= the specified value. If value 1414dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * is already a power of 2, then it is returned unchanged. It is undefined 1424dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * if value is <= 0. 1434dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary */ 1444dbbd04314cc0606f8d3bafe515c97e52c180f73halcanarystatic inline int SkNextPow2(int value) { 1454dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary SkASSERT(value > 0); 1464dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary return 1 << (32 - SkCLZ(value - 1)); 1474dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary} 1484dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary 1494dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary/** 150f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* Returns the largest power-of-2 that is <= the specified value. If value 151f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* is already a power of 2, then it is returned unchanged. It is undefined 152f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* if value is <= 0. 153f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth*/ 154f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verthstatic inline int SkPrevPow2(int value) { 155f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth SkASSERT(value > 0); 156f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth return 1 << (32 - SkCLZ(value >> 1)); 157f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth} 158f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth 159f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth/** 1604dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * Returns the log2 of the specified value, were that value to be rounded up 1614dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * to the next power of 2. It is undefined to pass 0. Examples: 1624dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * SkNextLog2(1) -> 0 1634dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * SkNextLog2(2) -> 1 1644dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * SkNextLog2(3) -> 2 1654dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * SkNextLog2(4) -> 2 1664dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * SkNextLog2(5) -> 3 1674dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary */ 1684dbbd04314cc0606f8d3bafe515c97e52c180f73halcanarystatic inline int SkNextLog2(uint32_t value) { 1694dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary SkASSERT(value != 0); 1704dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary return 32 - SkCLZ(value - 1); 1714dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary} 1724dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary 173f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth/** 174f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* Returns the log2 of the specified value, were that value to be rounded down 175f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* to the previous power of 2. It is undefined to pass 0. Examples: 176f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* SkPrevLog2(1) -> 0 177f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* SkPrevLog2(2) -> 1 178f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* SkPrevLog2(3) -> 1 179f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* SkPrevLog2(4) -> 2 180f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth* SkPrevLog2(5) -> 2 181f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth*/ 182f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verthstatic inline int SkPrevLog2(uint32_t value) { 183f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth SkASSERT(value != 0); 184f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth return 32 - SkCLZ(value >> 1); 185f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth} 186f9e678d6964bc5a6c2b38edbc36d9f23cf96c37fJim Van Verth 1874dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary/////////////////////////////////////////////////////////////////////////////// 1884dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary 1894dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary/** 1904dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary * Return the next power of 2 >= n. 1914dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary */ 1924dbbd04314cc0606f8d3bafe515c97e52c180f73halcanarystatic inline uint32_t GrNextPow2(uint32_t n) { 1934dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary return n ? (1 << (32 - SkCLZ(n - 1))) : 1; 1944dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary} 1954dbbd04314cc0606f8d3bafe515c97e52c180f73halcanary 1969e38047c56f8dff4440fe00002264be692440902Robert Phillips/** 1979e38047c56f8dff4440fe00002264be692440902Robert Phillips * Returns the next power of 2 >= n or n if the next power of 2 can't be represented by size_t. 1989e38047c56f8dff4440fe00002264be692440902Robert Phillips */ 1999e38047c56f8dff4440fe00002264be692440902Robert Phillipsstatic inline size_t GrNextSizePow2(size_t n) { 2009e38047c56f8dff4440fe00002264be692440902Robert Phillips constexpr int kNumSizeTBits = 8 * sizeof(size_t); 2019e38047c56f8dff4440fe00002264be692440902Robert Phillips constexpr size_t kHighBitSet = size_t(1) << (kNumSizeTBits - 1); 2029e38047c56f8dff4440fe00002264be692440902Robert Phillips 2039e38047c56f8dff4440fe00002264be692440902Robert Phillips if (!n) { 2049e38047c56f8dff4440fe00002264be692440902Robert Phillips return 1; 2059e38047c56f8dff4440fe00002264be692440902Robert Phillips } else if (n >= kHighBitSet) { 2069e38047c56f8dff4440fe00002264be692440902Robert Phillips return n; 2079e38047c56f8dff4440fe00002264be692440902Robert Phillips } 2089e38047c56f8dff4440fe00002264be692440902Robert Phillips 2099e38047c56f8dff4440fe00002264be692440902Robert Phillips n--; 2109e38047c56f8dff4440fe00002264be692440902Robert Phillips uint32_t shift = 1; 2119e38047c56f8dff4440fe00002264be692440902Robert Phillips while (shift < kNumSizeTBits) { 2129e38047c56f8dff4440fe00002264be692440902Robert Phillips n |= n >> shift; 2139e38047c56f8dff4440fe00002264be692440902Robert Phillips shift <<= 1; 2149e38047c56f8dff4440fe00002264be692440902Robert Phillips } 2159e38047c56f8dff4440fe00002264be692440902Robert Phillips return n + 1; 2169e38047c56f8dff4440fe00002264be692440902Robert Phillips} 2179e38047c56f8dff4440fe00002264be692440902Robert Phillips 2187b6ea19c9c42a4d24168f80fcfd44de4498604e3Mike Reed// conservative check. will return false for very large values that "could" fit 2197b6ea19c9c42a4d24168f80fcfd44de4498604e3Mike Reedtemplate <typename T> static inline bool SkFitsInFixed(T x) { 2207b6ea19c9c42a4d24168f80fcfd44de4498604e3Mike Reed return SkTAbs(x) <= 32767.0f; 2217b6ea19c9c42a4d24168f80fcfd44de4498604e3Mike Reed} 2227b6ea19c9c42a4d24168f80fcfd44de4498604e3Mike Reed 2234b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#endif 224