reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2006 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | #ifndef SkMath_DEFINED |
| 18 | #define SkMath_DEFINED |
| 19 | |
| 20 | #include "SkTypes.h" |
| 21 | |
| 22 | //! Returns the number of leading zero bits (0...32) |
| 23 | int SkCLZ_portable(uint32_t); |
| 24 | |
| 25 | /** Computes the 64bit product of a * b, and then shifts the answer down by |
| 26 | shift bits, returning the low 32bits. shift must be [0..63] |
| 27 | e.g. to perform a fixedmul, call SkMulShift(a, b, 16) |
| 28 | */ |
| 29 | int32_t SkMulShift(int32_t a, int32_t b, unsigned shift); |
| 30 | |
| 31 | /** Computes numer1 * numer2 / denom in full 64 intermediate precision. |
| 32 | It is an error for denom to be 0. There is no special handling if |
| 33 | the result overflows 32bits. |
| 34 | */ |
| 35 | int32_t SkMulDiv(int32_t numer1, int32_t numer2, int32_t denom); |
| 36 | |
| 37 | /** Computes (numer1 << shift) / denom in full 64 intermediate precision. |
| 38 | It is an error for denom to be 0. There is no special handling if |
| 39 | the result overflows 32bits. |
| 40 | */ |
| 41 | int32_t SkDivBits(int32_t numer, int32_t denom, int shift); |
| 42 | |
| 43 | /** Return the integer square root of value, with a bias of bitBias |
| 44 | */ |
| 45 | int32_t SkSqrtBits(int32_t value, int bitBias); |
| 46 | |
| 47 | /** Return the integer square root of n, treated as a SkFixed (16.16) |
| 48 | */ |
| 49 | #define SkSqrt32(n) SkSqrtBits(n, 15) |
| 50 | |
| 51 | /** Return the integer cube root of value, with a bias of bitBias |
| 52 | */ |
| 53 | int32_t SkCubeRootBits(int32_t value, int bitBias); |
| 54 | |
| 55 | /** Returns -1 if n < 0, else returns 0 |
| 56 | */ |
| 57 | #define SkExtractSign(n) ((int32_t)(n) >> 31) |
| 58 | |
| 59 | /** If sign == -1, returns -n, else sign must be 0, and returns n. |
| 60 | Typically used in conjunction with SkExtractSign(). |
| 61 | */ |
| 62 | static inline int32_t SkApplySign(int32_t n, int32_t sign) { |
| 63 | SkASSERT(sign == 0 || sign == -1); |
| 64 | return (n ^ sign) - sign; |
| 65 | } |
| 66 | |
reed@android.com | eebf5cb | 2010-02-09 18:30:59 +0000 | [diff] [blame] | 67 | /** Return x with the sign of y */ |
| 68 | static inline int32_t SkCopySign32(int32_t x, int32_t y) { |
| 69 | return SkApplySign(x, SkExtractSign(x ^ y)); |
| 70 | } |
| 71 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 72 | /** Returns (value < 0 ? 0 : value) efficiently (i.e. no compares or branches) |
| 73 | */ |
| 74 | static inline int SkClampPos(int value) { |
| 75 | return value & ~(value >> 31); |
| 76 | } |
| 77 | |
| 78 | /** Given an integer and a positive (max) integer, return the value |
| 79 | pinned against 0 and max, inclusive. |
| 80 | Note: only works as long as max - value doesn't wrap around |
| 81 | @param value The value we want returned pinned between [0...max] |
| 82 | @param max The positive max value |
| 83 | @return 0 if value < 0, max if value > max, else value |
| 84 | */ |
| 85 | static inline int SkClampMax(int value, int max) { |
| 86 | // ensure that max is positive |
| 87 | SkASSERT(max >= 0); |
| 88 | // ensure that if value is negative, max - value doesn't wrap around |
| 89 | SkASSERT(value >= 0 || max - value > 0); |
| 90 | |
| 91 | #ifdef SK_CPU_HAS_CONDITIONAL_INSTR |
| 92 | if (value < 0) { |
| 93 | value = 0; |
| 94 | } |
| 95 | if (value > max) { |
| 96 | value = max; |
| 97 | } |
| 98 | return value; |
| 99 | #else |
| 100 | |
| 101 | int diff = max - value; |
| 102 | // clear diff if diff is positive |
| 103 | diff &= diff >> 31; |
| 104 | |
| 105 | // clear the result if value < 0 |
| 106 | return (value + diff) & ~(value >> 31); |
| 107 | #endif |
| 108 | } |
| 109 | |
| 110 | /** Given a positive value and a positive max, return the value |
| 111 | pinned against max. |
| 112 | Note: only works as long as max - value doesn't wrap around |
| 113 | @return max if value >= max, else value |
| 114 | */ |
| 115 | static inline unsigned SkClampUMax(unsigned value, unsigned max) { |
| 116 | #ifdef SK_CPU_HAS_CONDITIONAL_INSTR |
| 117 | if (value > max) { |
| 118 | value = max; |
| 119 | } |
| 120 | return value; |
| 121 | #else |
| 122 | int diff = max - value; |
| 123 | // clear diff if diff is positive |
| 124 | diff &= diff >> 31; |
| 125 | |
| 126 | return value + diff; |
| 127 | #endif |
| 128 | } |
| 129 | |
| 130 | /////////////////////////////////////////////////////////////////////////////// |
| 131 | |
| 132 | #if defined(__arm__) && !defined(__thumb__) |
| 133 | #define SkCLZ(x) __builtin_clz(x) |
| 134 | #endif |
| 135 | |
| 136 | #ifndef SkCLZ |
| 137 | #define SkCLZ(x) SkCLZ_portable(x) |
| 138 | #endif |
| 139 | |
| 140 | /////////////////////////////////////////////////////////////////////////////// |
| 141 | |
| 142 | /** Returns the smallest power-of-2 that is >= the specified value. If value |
| 143 | is already a power of 2, then it is returned unchanged. It is undefined |
| 144 | if value is <= 0. |
| 145 | */ |
| 146 | static inline int SkNextPow2(int value) { |
| 147 | SkASSERT(value > 0); |
| 148 | return 1 << (32 - SkCLZ(value - 1)); |
| 149 | } |
| 150 | |
| 151 | /** Returns the log2 of the specified value, were that value to be rounded up |
| 152 | to the next power of 2. It is undefined to pass 0. Examples: |
| 153 | SkNextLog2(1) -> 0 |
| 154 | SkNextLog2(2) -> 1 |
| 155 | SkNextLog2(3) -> 2 |
| 156 | SkNextLog2(4) -> 2 |
| 157 | SkNextLog2(5) -> 3 |
| 158 | */ |
| 159 | static inline int SkNextLog2(uint32_t value) { |
| 160 | SkASSERT(value != 0); |
| 161 | return 32 - SkCLZ(value - 1); |
| 162 | } |
| 163 | |
| 164 | /////////////////////////////////////////////////////////////////////////////// |
| 165 | |
| 166 | /** SkMulS16(a, b) multiplies a * b, but requires that a and b are both int16_t. |
| 167 | With this requirement, we can generate faster instructions on some |
| 168 | architectures. |
| 169 | */ |
deanm@chromium.org | d5ed395 | 2009-08-21 17:17:35 +0000 | [diff] [blame] | 170 | #if defined(__arm__) \ |
| 171 | && !defined(__thumb__) \ |
reed@android.com | 69975b0 | 2010-01-04 19:23:32 +0000 | [diff] [blame] | 172 | && !defined(__ARM_ARCH_4T__) \ |
deanm@chromium.org | d5ed395 | 2009-08-21 17:17:35 +0000 | [diff] [blame] | 173 | && !defined(__ARM_ARCH_5T__) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 174 | static inline int32_t SkMulS16(S16CPU x, S16CPU y) { |
| 175 | SkASSERT((int16_t)x == x); |
| 176 | SkASSERT((int16_t)y == y); |
| 177 | int32_t product; |
| 178 | asm("smulbb %0, %1, %2 \n" |
| 179 | : "=r"(product) |
| 180 | : "r"(x), "r"(y) |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 181 | ); |
| 182 | return product; |
| 183 | } |
| 184 | #else |
| 185 | #ifdef SK_DEBUG |
| 186 | static inline int32_t SkMulS16(S16CPU x, S16CPU y) { |
| 187 | SkASSERT((int16_t)x == x); |
| 188 | SkASSERT((int16_t)y == y); |
| 189 | return x * y; |
| 190 | } |
| 191 | #else |
| 192 | #define SkMulS16(x, y) ((x) * (y)) |
| 193 | #endif |
| 194 | #endif |
| 195 | |
| 196 | /** Return a*b/255, truncating away any fractional bits. Only valid if both |
| 197 | a and b are 0..255 |
| 198 | */ |
| 199 | static inline U8CPU SkMulDiv255Trunc(U8CPU a, U8CPU b) { |
| 200 | SkASSERT((uint8_t)a == a); |
| 201 | SkASSERT((uint8_t)b == b); |
| 202 | unsigned prod = SkMulS16(a, b) + 1; |
| 203 | return (prod + (prod >> 8)) >> 8; |
| 204 | } |
| 205 | |
| 206 | /** Return a*b/255, rounding any fractional bits. Only valid if both |
| 207 | a and b are 0..255 |
| 208 | */ |
| 209 | static inline U8CPU SkMulDiv255Round(U8CPU a, U8CPU b) { |
| 210 | SkASSERT((uint8_t)a == a); |
| 211 | SkASSERT((uint8_t)b == b); |
| 212 | unsigned prod = SkMulS16(a, b) + 128; |
| 213 | return (prod + (prod >> 8)) >> 8; |
| 214 | } |
| 215 | |
senorblanco@chromium.org | ec7a30c | 2010-12-07 21:07:56 +0000 | [diff] [blame] | 216 | /** Return (a*b)/255, taking the ceiling of any fractional bits. Only valid if |
| 217 | both a and b are 0..255. The expected result equals (a * b + 254) / 255. |
| 218 | */ |
| 219 | static inline U8CPU SkMulDiv255Ceiling(U8CPU a, U8CPU b) { |
| 220 | SkASSERT((uint8_t)a == a); |
| 221 | SkASSERT((uint8_t)b == b); |
| 222 | unsigned prod = SkMulS16(a, b) + 255; |
| 223 | return (prod + (prod >> 8)) >> 8; |
| 224 | } |
| 225 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 226 | /** Return a*b/((1 << shift) - 1), rounding any fractional bits. |
| 227 | Only valid if a and b are unsigned and <= 32767 and shift is > 0 and <= 8 |
| 228 | */ |
| 229 | static inline unsigned SkMul16ShiftRound(unsigned a, unsigned b, int shift) { |
| 230 | SkASSERT(a <= 32767); |
| 231 | SkASSERT(b <= 32767); |
| 232 | SkASSERT(shift > 0 && shift <= 8); |
| 233 | unsigned prod = SkMulS16(a, b) + (1 << (shift - 1)); |
| 234 | return (prod + (prod >> shift)) >> shift; |
| 235 | } |
| 236 | |
reed@android.com | a0f5d15 | 2009-06-22 17:38:10 +0000 | [diff] [blame] | 237 | /** Just the rounding step in SkDiv255Round: round(value / 255) |
| 238 | */ |
| 239 | static inline unsigned SkDiv255Round(unsigned prod) { |
| 240 | prod += 128; |
| 241 | return (prod + (prod >> 8)) >> 8; |
| 242 | } |
| 243 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 244 | #endif |
| 245 | |