1 /*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #ifndef SkMathPriv_DEFINED
9 #define SkMathPriv_DEFINED
10
11 #include "include/private/base/SkAssert.h"
12 #include "include/private/base/SkCPUTypes.h"
13 #include "include/private/base/SkTemplates.h"
14
15 #include <cstddef>
16 #include <cstdint>
17
18 /**
19 * Return the integer square root of value, with a bias of bitBias
20 */
21 int32_t SkSqrtBits(int32_t value, int bitBias);
22
23 /** Return the integer square root of n, treated as a SkFixed (16.16)
24 */
SkSqrt32(int32_t n)25 static inline int32_t SkSqrt32(int32_t n) { return SkSqrtBits(n, 15); }
26
27 /**
28 * Returns (value < 0 ? 0 : value) efficiently (i.e. no compares or branches)
29 */
SkClampPos(int value)30 static inline int SkClampPos(int value) {
31 return value & ~(value >> 31);
32 }
33
34 /**
35 * Stores numer/denom and numer%denom into div and mod respectively.
36 */
37 template <typename In, typename Out>
SkTDivMod(In numer,In denom,Out * div,Out * mod)38 inline void SkTDivMod(In numer, In denom, Out* div, Out* mod) {
39 #ifdef SK_CPU_ARM32
40 // If we wrote this as in the else branch, GCC won't fuse the two into one
41 // divmod call, but rather a div call followed by a divmod. Silly! This
42 // version is just as fast as calling __aeabi_[u]idivmod manually, but with
43 // prettier code.
44 //
45 // This benches as around 2x faster than the code in the else branch.
46 const In d = numer/denom;
47 *div = static_cast<Out>(d);
48 *mod = static_cast<Out>(numer-d*denom);
49 #else
50 // On x86 this will just be a single idiv.
51 *div = static_cast<Out>(numer/denom);
52 *mod = static_cast<Out>(numer%denom);
53 #endif
54 }
55
56 /** Returns -1 if n < 0, else returns 0
57 */
58 #define SkExtractSign(n) ((int32_t)(n) >> 31)
59
60 /** If sign == -1, returns -n, else sign must be 0, and returns n.
61 Typically used in conjunction with SkExtractSign().
62 */
SkApplySign(int32_t n,int32_t sign)63 static inline int32_t SkApplySign(int32_t n, int32_t sign) {
64 SkASSERT(sign == 0 || sign == -1);
65 return (n ^ sign) - sign;
66 }
67
68 /** Return x with the sign of y */
SkCopySign32(int32_t x,int32_t y)69 static inline int32_t SkCopySign32(int32_t x, int32_t y) {
70 return SkApplySign(x, SkExtractSign(x ^ y));
71 }
72
73 /** Given a positive value and a positive max, return the value
74 pinned against max.
75 Note: only works as long as max - value doesn't wrap around
76 @return max if value >= max, else value
77 */
SkClampUMax(unsigned value,unsigned max)78 static inline unsigned SkClampUMax(unsigned value, unsigned max) {
79 if (value > max) {
80 value = max;
81 }
82 return value;
83 }
84
85 // If a signed int holds min_int (e.g. 0x80000000) it is undefined what happens when
86 // we negate it (even though we *know* we're 2's complement and we'll get the same
87 // value back). So we create this helper function that casts to size_t (unsigned) first,
88 // to avoid the complaint.
sk_negate_to_size_t(int32_t value)89 static inline size_t sk_negate_to_size_t(int32_t value) {
90 #if defined(_MSC_VER)
91 #pragma warning(push)
92 #pragma warning(disable : 4146) // Thanks MSVC, we know what we're negating an unsigned
93 #endif
94 return -static_cast<size_t>(value);
95 #if defined(_MSC_VER)
96 #pragma warning(pop)
97 #endif
98 }
99
100 ///////////////////////////////////////////////////////////////////////////////
101
102 /** Return a*b/255, truncating away any fractional bits. Only valid if both
103 a and b are 0..255
104 */
SkMulDiv255Trunc(U8CPU a,U8CPU b)105 static inline U8CPU SkMulDiv255Trunc(U8CPU a, U8CPU b) {
106 SkASSERT((uint8_t)a == a);
107 SkASSERT((uint8_t)b == b);
108 unsigned prod = a*b + 1;
109 return (prod + (prod >> 8)) >> 8;
110 }
111
112 /** Return (a*b)/255, taking the ceiling of any fractional bits. Only valid if
113 both a and b are 0..255. The expected result equals (a * b + 254) / 255.
114 */
SkMulDiv255Ceiling(U8CPU a,U8CPU b)115 static inline U8CPU SkMulDiv255Ceiling(U8CPU a, U8CPU b) {
116 SkASSERT((uint8_t)a == a);
117 SkASSERT((uint8_t)b == b);
118 unsigned prod = a*b + 255;
119 return (prod + (prod >> 8)) >> 8;
120 }
121
122 /** Just the rounding step in SkDiv255Round: round(value / 255)
123 */
SkDiv255Round(unsigned prod)124 static inline unsigned SkDiv255Round(unsigned prod) {
125 prod += 128;
126 return (prod + (prod >> 8)) >> 8;
127 }
128
129 /**
130 * Swap byte order of a 4-byte value, e.g. 0xaarrggbb -> 0xbbggrraa.
131 */
132 #if defined(_MSC_VER)
133 #include <stdlib.h>
SkBSwap32(uint32_t v)134 static inline uint32_t SkBSwap32(uint32_t v) { return _byteswap_ulong(v); }
135 #else
SkBSwap32(uint32_t v)136 static inline uint32_t SkBSwap32(uint32_t v) { return __builtin_bswap32(v); }
137 #endif
138
139 /*
140 * Return the number of set bits (i.e., the population count) in the provided uint32_t.
141 */
142 int SkPopCount_portable(uint32_t n);
143
144 #if defined(__GNUC__) || defined(__clang__)
SkPopCount(uint32_t n)145 static inline int SkPopCount(uint32_t n) {
146 return __builtin_popcount(n);
147 }
148 #else
SkPopCount(uint32_t n)149 static inline int SkPopCount(uint32_t n) {
150 return SkPopCount_portable(n);
151 }
152 #endif
153
154 /*
155 * Return the 0-based index of the nth bit set in target
156 * Returns 32 if there is no nth bit set.
157 */
158 int SkNthSet(uint32_t target, int n);
159
160 //! Returns the number of leading zero bits (0...32)
161 // From Hacker's Delight 2nd Edition
SkCLZ_portable(uint32_t x)162 constexpr int SkCLZ_portable(uint32_t x) {
163 int n = 32;
164 uint32_t y = x >> 16; if (y != 0) {n -= 16; x = y;}
165 y = x >> 8; if (y != 0) {n -= 8; x = y;}
166 y = x >> 4; if (y != 0) {n -= 4; x = y;}
167 y = x >> 2; if (y != 0) {n -= 2; x = y;}
168 y = x >> 1; if (y != 0) {return n - 2;}
169 return n - static_cast<int>(x);
170 }
171
172 static_assert(32 == SkCLZ_portable(0));
173 static_assert(31 == SkCLZ_portable(1));
174 static_assert( 1 == SkCLZ_portable(1 << 30));
175 static_assert( 1 == SkCLZ_portable((1 << 30) | (1 << 24) | 1));
176 static_assert( 0 == SkCLZ_portable(~0U));
177
178 #if defined(SK_BUILD_FOR_WIN)
179 #include <intrin.h>
180
SkCLZ(uint32_t mask)181 static inline int SkCLZ(uint32_t mask) {
182 if (mask) {
183 unsigned long index = 0;
184 _BitScanReverse(&index, mask);
185 // Suppress this bogus /analyze warning. The check for non-zero
186 // guarantees that _BitScanReverse will succeed.
187 #pragma warning(suppress : 6102) // Using 'index' from failed function call
188 return index ^ 0x1F;
189 } else {
190 return 32;
191 }
192 }
193 #elif defined(SK_CPU_ARM32) || defined(__GNUC__) || defined(__clang__)
SkCLZ(uint32_t mask)194 static inline int SkCLZ(uint32_t mask) {
195 // __builtin_clz(0) is undefined, so we have to detect that case.
196 return mask ? __builtin_clz(mask) : 32;
197 }
198 #else
SkCLZ(uint32_t mask)199 static inline int SkCLZ(uint32_t mask) {
200 return SkCLZ_portable(mask);
201 }
202 #endif
203
204 //! Returns the number of trailing zero bits (0...32)
205 // From Hacker's Delight 2nd Edition
SkCTZ_portable(uint32_t x)206 constexpr int SkCTZ_portable(uint32_t x) {
207 return 32 - SkCLZ_portable(~x & (x - 1));
208 }
209
210 static_assert(32 == SkCTZ_portable(0));
211 static_assert( 0 == SkCTZ_portable(1));
212 static_assert(30 == SkCTZ_portable(1 << 30));
213 static_assert( 2 == SkCTZ_portable((1 << 30) | (1 << 24) | (1 << 2)));
214 static_assert( 0 == SkCTZ_portable(~0U));
215
216 #if defined(SK_BUILD_FOR_WIN)
217 #include <intrin.h>
218
SkCTZ(uint32_t mask)219 static inline int SkCTZ(uint32_t mask) {
220 if (mask) {
221 unsigned long index = 0;
222 _BitScanForward(&index, mask);
223 // Suppress this bogus /analyze warning. The check for non-zero
224 // guarantees that _BitScanReverse will succeed.
225 #pragma warning(suppress : 6102) // Using 'index' from failed function call
226 return index;
227 } else {
228 return 32;
229 }
230 }
231 #elif defined(SK_CPU_ARM32) || defined(__GNUC__) || defined(__clang__)
SkCTZ(uint32_t mask)232 static inline int SkCTZ(uint32_t mask) {
233 // __builtin_ctz(0) is undefined, so we have to detect that case.
234 return mask ? __builtin_ctz(mask) : 32;
235 }
236 #else
SkCTZ(uint32_t mask)237 static inline int SkCTZ(uint32_t mask) {
238 return SkCTZ_portable(mask);
239 }
240 #endif
241
242 /**
243 * Returns the log2 of the specified value, were that value to be rounded up
244 * to the next power of 2. It is undefined to pass 0. Examples:
245 * SkNextLog2(1) -> 0
246 * SkNextLog2(2) -> 1
247 * SkNextLog2(3) -> 2
248 * SkNextLog2(4) -> 2
249 * SkNextLog2(5) -> 3
250 */
SkNextLog2(uint32_t value)251 static inline int SkNextLog2(uint32_t value) {
252 SkASSERT(value != 0);
253 return 32 - SkCLZ(value - 1);
254 }
255
SkNextLog2_portable(uint32_t value)256 constexpr int SkNextLog2_portable(uint32_t value) {
257 SkASSERT(value != 0);
258 return 32 - SkCLZ_portable(value - 1);
259 }
260
261 /**
262 * Returns the log2 of the specified value, were that value to be rounded down
263 * to the previous power of 2. It is undefined to pass 0. Examples:
264 * SkPrevLog2(1) -> 0
265 * SkPrevLog2(2) -> 1
266 * SkPrevLog2(3) -> 1
267 * SkPrevLog2(4) -> 2
268 * SkPrevLog2(5) -> 2
269 */
SkPrevLog2(uint32_t value)270 static inline int SkPrevLog2(uint32_t value) {
271 SkASSERT(value != 0);
272 return 32 - SkCLZ(value >> 1);
273 }
274
SkPrevLog2_portable(uint32_t value)275 constexpr int SkPrevLog2_portable(uint32_t value) {
276 SkASSERT(value != 0);
277 return 32 - SkCLZ_portable(value >> 1);
278 }
279
280 /**
281 * Returns the smallest power-of-2 that is >= the specified value. If value
282 * is already a power of 2, then it is returned unchanged. It is undefined
283 * if value is <= 0.
284 */
SkNextPow2(int value)285 static inline int SkNextPow2(int value) {
286 SkASSERT(value > 0);
287 return 1 << SkNextLog2(static_cast<uint32_t>(value));
288 }
289
SkNextPow2_portable(int value)290 constexpr int SkNextPow2_portable(int value) {
291 SkASSERT(value > 0);
292 return 1 << SkNextLog2_portable(static_cast<uint32_t>(value));
293 }
294
295 /**
296 * Returns the largest power-of-2 that is <= the specified value. If value
297 * is already a power of 2, then it is returned unchanged. It is undefined
298 * if value is <= 0.
299 */
SkPrevPow2(int value)300 static inline int SkPrevPow2(int value) {
301 SkASSERT(value > 0);
302 return 1 << SkPrevLog2(static_cast<uint32_t>(value));
303 }
304
SkPrevPow2_portable(int value)305 constexpr int SkPrevPow2_portable(int value) {
306 SkASSERT(value > 0);
307 return 1 << SkPrevLog2_portable(static_cast<uint32_t>(value));
308 }
309
310 ///////////////////////////////////////////////////////////////////////////////
311
312 /**
313 * Return the smallest power-of-2 >= n.
314 */
GrNextPow2(uint32_t n)315 static inline uint32_t GrNextPow2(uint32_t n) {
316 return n ? (1 << (32 - SkCLZ(n - 1))) : 1;
317 }
318
319 /**
320 * Returns the next power of 2 >= n or n if the next power of 2 can't be represented by size_t.
321 */
GrNextSizePow2(size_t n)322 static inline size_t GrNextSizePow2(size_t n) {
323 constexpr int kNumSizeTBits = 8 * sizeof(size_t);
324 constexpr size_t kHighBitSet = size_t(1) << (kNumSizeTBits - 1);
325
326 if (!n) {
327 return 1;
328 } else if (n >= kHighBitSet) {
329 return n;
330 }
331
332 n--;
333 uint32_t shift = 1;
334 while (shift < kNumSizeTBits) {
335 n |= n >> shift;
336 shift <<= 1;
337 }
338 return n + 1;
339 }
340
341 // conservative check. will return false for very large values that "could" fit
SkFitsInFixed(T x)342 template <typename T> static inline bool SkFitsInFixed(T x) {
343 return SkTAbs(x) <= 32767.0f;
344 }
345
346 #endif
347