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 */
21int32_t SkSqrtBits(int32_t value, int bitBias);
22
23/** Return the integer square root of n, treated as a SkFixed (16.16)
24 */
25static inline int32_t SkSqrt32(int32_t n) { return SkSqrtBits(value: n, bitBias: 15); }
26
27/**
28 * Returns (value < 0 ? 0 : value) efficiently (i.e. no compares or branches)
29 */
30static 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 */
37template <typename In, typename Out>
38inline 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 */
63static 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 */
69static inline int32_t SkCopySign32(int32_t x, int32_t y) {
70 return SkApplySign(n: 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 */
78static 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.
89static 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 */
105static 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 */
115static 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 */
124static 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>
134 static inline uint32_t SkBSwap32(uint32_t v) { return _byteswap_ulong(v); }
135#else
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 */
142int SkPopCount_portable(uint32_t n);
143
144#if defined(__GNUC__) || defined(__clang__)
145 static inline int SkPopCount(uint32_t n) {
146 return __builtin_popcount(n);
147 }
148#else
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 */
158int SkNthSet(uint32_t target, int n);
159
160//! Returns the number of leading zero bits (0...32)
161// From Hacker's Delight 2nd Edition
162constexpr 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
172static_assert(32 == SkCLZ_portable(x: 0));
173static_assert(31 == SkCLZ_portable(x: 1));
174static_assert( 1 == SkCLZ_portable(x: 1 << 30));
175static_assert( 1 == SkCLZ_portable(x: (1 << 30) | (1 << 24) | 1));
176static_assert( 0 == SkCLZ_portable(x: ~0U));
177
178#if defined(SK_BUILD_FOR_WIN)
179 #include <intrin.h>
180
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__)
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
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
206constexpr int SkCTZ_portable(uint32_t x) {
207 return 32 - SkCLZ_portable(x: ~x & (x - 1));
208}
209
210static_assert(32 == SkCTZ_portable(x: 0));
211static_assert( 0 == SkCTZ_portable(x: 1));
212static_assert(30 == SkCTZ_portable(x: 1 << 30));
213static_assert( 2 == SkCTZ_portable(x: (1 << 30) | (1 << 24) | (1 << 2)));
214static_assert( 0 == SkCTZ_portable(x: ~0U));
215
216#if defined(SK_BUILD_FOR_WIN)
217 #include <intrin.h>
218
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__)
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
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 */
251static inline int SkNextLog2(uint32_t value) {
252 SkASSERT(value != 0);
253 return 32 - SkCLZ(mask: value - 1);
254}
255
256constexpr int SkNextLog2_portable(uint32_t value) {
257 SkASSERT(value != 0);
258 return 32 - SkCLZ_portable(x: 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*/
270static inline int SkPrevLog2(uint32_t value) {
271 SkASSERT(value != 0);
272 return 32 - SkCLZ(mask: value >> 1);
273}
274
275constexpr int SkPrevLog2_portable(uint32_t value) {
276 SkASSERT(value != 0);
277 return 32 - SkCLZ_portable(x: 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 */
285static inline int SkNextPow2(int value) {
286 SkASSERT(value > 0);
287 return 1 << SkNextLog2(value: static_cast<uint32_t>(value));
288}
289
290constexpr int SkNextPow2_portable(int value) {
291 SkASSERT(value > 0);
292 return 1 << SkNextLog2_portable(value: 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*/
300static inline int SkPrevPow2(int value) {
301 SkASSERT(value > 0);
302 return 1 << SkPrevLog2(value: static_cast<uint32_t>(value));
303}
304
305constexpr int SkPrevPow2_portable(int value) {
306 SkASSERT(value > 0);
307 return 1 << SkPrevLog2_portable(value: static_cast<uint32_t>(value));
308}
309
310///////////////////////////////////////////////////////////////////////////////
311
312/**
313 * Return the smallest power-of-2 >= n.
314 */
315static inline uint32_t GrNextPow2(uint32_t n) {
316 return n ? (1 << (32 - SkCLZ(mask: 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 */
322static 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
342template <typename T> static inline bool SkFitsInFixed(T x) {
343 return SkTAbs(x) <= 32767.0f;
344}
345
346#endif
347

Provided by KDAB

Privacy Policy
Learn more about Flutter for embedded and desktop on industrialflutter.com

source code of flutter_engine/third_party/skia/src/base/SkMathPriv.h