epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 2 | /* |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 3 | * Copyright 2006 The Android Open Source Project |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 4 | * |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 5 | * Use of this source code is governed by a BSD-style license that can be |
| 6 | * found in the LICENSE file. |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 7 | */ |
| 8 | |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 9 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 10 | #ifndef SkMath_DEFINED |
| 11 | #define SkMath_DEFINED |
| 12 | |
| 13 | #include "SkTypes.h" |
| 14 | |
reed@google.com | 57212f9 | 2013-12-30 14:40:38 +0000 | [diff] [blame] | 15 | // 64bit -> 32bit utilities |
| 16 | |
| 17 | /** |
| 18 | * Return true iff the 64bit value can exactly be represented in signed 32bits |
| 19 | */ |
| 20 | static inline bool sk_64_isS32(int64_t value) { |
| 21 | return (int32_t)value == value; |
| 22 | } |
| 23 | |
| 24 | /** |
| 25 | * Return the 64bit argument as signed 32bits, asserting in debug that the arg |
| 26 | * exactly fits in signed 32bits. In the release build, no checks are preformed |
| 27 | * and the return value if the arg does not fit is undefined. |
| 28 | */ |
| 29 | static inline int32_t sk_64_asS32(int64_t value) { |
| 30 | SkASSERT(sk_64_isS32(value)); |
| 31 | return (int32_t)value; |
| 32 | } |
| 33 | |
| 34 | // Handy util that can be passed two ints, and will automatically promote to |
| 35 | // 64bits before the multiply, so the caller doesn't have to remember to cast |
| 36 | // e.g. (int64_t)a * b; |
| 37 | static inline int64_t sk_64_mul(int64_t a, int64_t b) { |
| 38 | return a * b; |
| 39 | } |
| 40 | |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 41 | /////////////////////////////////////////////////////////////////////////////// |
| 42 | |
commit-bot@chromium.org | 0f1fef8 | 2014-04-19 22:12:35 +0000 | [diff] [blame] | 43 | /** |
| 44 | * Computes numer1 * numer2 / denom in full 64 intermediate precision. |
| 45 | * It is an error for denom to be 0. There is no special handling if |
| 46 | * the result overflows 32bits. |
| 47 | */ |
| 48 | static inline int32_t SkMulDiv(int32_t numer1, int32_t numer2, int32_t denom) { |
| 49 | SkASSERT(denom); |
skia.committer@gmail.com | f7927dd | 2014-04-20 03:04:55 +0000 | [diff] [blame] | 50 | |
commit-bot@chromium.org | 0f1fef8 | 2014-04-19 22:12:35 +0000 | [diff] [blame] | 51 | int64_t tmp = sk_64_mul(numer1, numer2) / denom; |
| 52 | return sk_64_asS32(tmp); |
| 53 | } |
| 54 | |
| 55 | /** |
| 56 | * Computes (numer1 << shift) / denom in full 64 intermediate precision. |
| 57 | * It is an error for denom to be 0. There is no special handling if |
| 58 | * the result overflows 32bits. |
| 59 | */ |
| 60 | int32_t SkDivBits(int32_t numer, int32_t denom, int shift); |
| 61 | |
| 62 | /** |
| 63 | * Return the integer square root of value, with a bias of bitBias |
| 64 | */ |
| 65 | int32_t SkSqrtBits(int32_t value, int bitBias); |
| 66 | |
| 67 | /** Return the integer square root of n, treated as a SkFixed (16.16) |
| 68 | */ |
| 69 | #define SkSqrt32(n) SkSqrtBits(n, 15) |
| 70 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 71 | //! Returns the number of leading zero bits (0...32) |
| 72 | int SkCLZ_portable(uint32_t); |
| 73 | |
reed@google.com | 44d37d9 | 2013-04-29 14:31:29 +0000 | [diff] [blame] | 74 | #ifndef SkCLZ |
reed@google.com | 7729534d | 2013-04-29 14:43:50 +0000 | [diff] [blame] | 75 | #if defined(_MSC_VER) && _MSC_VER >= 1400 |
| 76 | #include <intrin.h> |
| 77 | |
| 78 | static inline int SkCLZ(uint32_t mask) { |
| 79 | if (mask) { |
| 80 | DWORD index; |
| 81 | _BitScanReverse(&index, mask); |
brucedawson | aea85dc | 2015-01-30 12:57:50 -0800 | [diff] [blame] | 82 | // Suppress this bogus /analyze warning. The check for non-zero |
| 83 | // guarantees that _BitScanReverse will succeed. |
| 84 | #pragma warning(suppress : 6102) // Using 'index' from failed function call |
reed@google.com | 7729534d | 2013-04-29 14:43:50 +0000 | [diff] [blame] | 85 | return index ^ 0x1F; |
| 86 | } else { |
| 87 | return 32; |
| 88 | } |
| 89 | } |
mtklein | 3a2682a | 2014-06-03 12:07:31 -0700 | [diff] [blame] | 90 | #elif defined(SK_CPU_ARM32) || defined(__GNUC__) || defined(__clang__) |
reed@google.com | 5c341d1 | 2013-04-29 15:34:35 +0000 | [diff] [blame] | 91 | static inline int SkCLZ(uint32_t mask) { |
| 92 | // __builtin_clz(0) is undefined, so we have to detect that case. |
| 93 | return mask ? __builtin_clz(mask) : 32; |
| 94 | } |
reed@google.com | 7729534d | 2013-04-29 14:43:50 +0000 | [diff] [blame] | 95 | #else |
| 96 | #define SkCLZ(x) SkCLZ_portable(x) |
| 97 | #endif |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 98 | #endif |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 99 | |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 100 | /** |
| 101 | * Returns (value < 0 ? 0 : value) efficiently (i.e. no compares or branches) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 102 | */ |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 103 | static inline int SkClampPos(int value) { |
| 104 | return value & ~(value >> 31); |
| 105 | } |
| 106 | |
| 107 | /** Given an integer and a positive (max) integer, return the value |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 108 | * pinned against 0 and max, inclusive. |
| 109 | * @param value The value we want returned pinned between [0...max] |
| 110 | * @param max The positive max value |
| 111 | * @return 0 if value < 0, max if value > max, else value |
| 112 | */ |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 113 | static inline int SkClampMax(int value, int max) { |
| 114 | // ensure that max is positive |
| 115 | SkASSERT(max >= 0); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 116 | if (value < 0) { |
| 117 | value = 0; |
| 118 | } |
| 119 | if (value > max) { |
| 120 | value = max; |
| 121 | } |
| 122 | return value; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 123 | } |
| 124 | |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 125 | /** |
| 126 | * Returns the smallest power-of-2 that is >= the specified value. If value |
| 127 | * is already a power of 2, then it is returned unchanged. It is undefined |
| 128 | * if value is <= 0. |
| 129 | */ |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 130 | static inline int SkNextPow2(int value) { |
| 131 | SkASSERT(value > 0); |
| 132 | return 1 << (32 - SkCLZ(value - 1)); |
| 133 | } |
| 134 | |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 135 | /** |
| 136 | * Returns the log2 of the specified value, were that value to be rounded up |
| 137 | * to the next power of 2. It is undefined to pass 0. Examples: |
| 138 | * SkNextLog2(1) -> 0 |
| 139 | * SkNextLog2(2) -> 1 |
| 140 | * SkNextLog2(3) -> 2 |
| 141 | * SkNextLog2(4) -> 2 |
| 142 | * SkNextLog2(5) -> 3 |
| 143 | */ |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 144 | static inline int SkNextLog2(uint32_t value) { |
| 145 | SkASSERT(value != 0); |
| 146 | return 32 - SkCLZ(value - 1); |
| 147 | } |
| 148 | |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 149 | /** |
| 150 | * Returns true if value is a power of 2. Does not explicitly check for |
| 151 | * value <= 0. |
reed@android.com | f2b98d6 | 2010-12-20 18:26:13 +0000 | [diff] [blame] | 152 | */ |
bsalomon | 1421aee | 2015-07-31 08:22:17 -0700 | [diff] [blame] | 153 | template <typename T> inline bool SkIsPow2(T value) { |
reed@android.com | f2b98d6 | 2010-12-20 18:26:13 +0000 | [diff] [blame] | 154 | return (value & (value - 1)) == 0; |
| 155 | } |
| 156 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 157 | /////////////////////////////////////////////////////////////////////////////// |
| 158 | |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 159 | /** |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 160 | * Return a*b/((1 << shift) - 1), rounding any fractional bits. |
| 161 | * Only valid if a and b are unsigned and <= 32767 and shift is > 0 and <= 8 |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 162 | */ |
reed@google.com | ea774d2 | 2013-04-22 20:21:56 +0000 | [diff] [blame] | 163 | static inline unsigned SkMul16ShiftRound(U16CPU a, U16CPU b, int shift) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 164 | SkASSERT(a <= 32767); |
| 165 | SkASSERT(b <= 32767); |
| 166 | SkASSERT(shift > 0 && shift <= 8); |
mtklein | 3848427 | 2015-08-07 08:48:12 -0700 | [diff] [blame^] | 167 | unsigned prod = a*b + (1 << (shift - 1)); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 168 | return (prod + (prod >> shift)) >> shift; |
| 169 | } |
| 170 | |
reed@google.com | 4b163ed | 2012-08-07 21:35:13 +0000 | [diff] [blame] | 171 | /** |
reed@google.com | ea774d2 | 2013-04-22 20:21:56 +0000 | [diff] [blame] | 172 | * Return a*b/255, rounding any fractional bits. |
| 173 | * Only valid if a and b are unsigned and <= 32767. |
reed@android.com | a0f5d15 | 2009-06-22 17:38:10 +0000 | [diff] [blame] | 174 | */ |
reed@google.com | ea774d2 | 2013-04-22 20:21:56 +0000 | [diff] [blame] | 175 | static inline U8CPU SkMulDiv255Round(U16CPU a, U16CPU b) { |
| 176 | SkASSERT(a <= 32767); |
| 177 | SkASSERT(b <= 32767); |
mtklein | 3848427 | 2015-08-07 08:48:12 -0700 | [diff] [blame^] | 178 | unsigned prod = a*b + 128; |
reed@android.com | a0f5d15 | 2009-06-22 17:38:10 +0000 | [diff] [blame] | 179 | return (prod + (prod >> 8)) >> 8; |
| 180 | } |
| 181 | |
commit-bot@chromium.org | 2c86fbb | 2013-09-26 19:22:54 +0000 | [diff] [blame] | 182 | /** |
| 183 | * Stores numer/denom and numer%denom into div and mod respectively. |
| 184 | */ |
| 185 | template <typename In, typename Out> |
| 186 | inline void SkTDivMod(In numer, In denom, Out* div, Out* mod) { |
mtklein | 3a2682a | 2014-06-03 12:07:31 -0700 | [diff] [blame] | 187 | #ifdef SK_CPU_ARM32 |
commit-bot@chromium.org | 2c86fbb | 2013-09-26 19:22:54 +0000 | [diff] [blame] | 188 | // If we wrote this as in the else branch, GCC won't fuse the two into one |
| 189 | // divmod call, but rather a div call followed by a divmod. Silly! This |
| 190 | // version is just as fast as calling __aeabi_[u]idivmod manually, but with |
| 191 | // prettier code. |
| 192 | // |
| 193 | // This benches as around 2x faster than the code in the else branch. |
| 194 | const In d = numer/denom; |
| 195 | *div = static_cast<Out>(d); |
| 196 | *mod = static_cast<Out>(numer-d*denom); |
| 197 | #else |
| 198 | // On x86 this will just be a single idiv. |
| 199 | *div = static_cast<Out>(numer/denom); |
| 200 | *mod = static_cast<Out>(numer%denom); |
mtklein | 3a2682a | 2014-06-03 12:07:31 -0700 | [diff] [blame] | 201 | #endif |
commit-bot@chromium.org | 2c86fbb | 2013-09-26 19:22:54 +0000 | [diff] [blame] | 202 | } |
| 203 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 204 | #endif |