SkMath.h revision ea774d2a5a049bf89474c0f047ed6a4e521de126
1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 28a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 48a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 78a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 9ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkMath_DEFINED 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkMath_DEFINED 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkTypes.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 154b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 164b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Computes numer1 * numer2 / denom in full 64 intermediate precision. 174b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * It is an error for denom to be 0. There is no special handling if 184b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * the result overflows 32bits. 194b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint32_t SkMulDiv(int32_t numer1, int32_t numer2, int32_t denom); 218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 224b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 234b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Computes (numer1 << shift) / denom in full 64 intermediate precision. 244b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * It is an error for denom to be 0. There is no special handling if 254b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * the result overflows 32bits. 264b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint32_t SkDivBits(int32_t numer, int32_t denom, int shift); 288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 294b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 304b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Return the integer square root of value, with a bias of bitBias 314b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint32_t SkSqrtBits(int32_t value, int bitBias); 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 34586b6a5e60a1e5c0e675cc42c9a01341c688efa4reed@google.com/** Return the integer square root of n, treated as a SkFixed (16.16) 35586b6a5e60a1e5c0e675cc42c9a01341c688efa4reed@google.com */ 36586b6a5e60a1e5c0e675cc42c9a01341c688efa4reed@google.com#define SkSqrt32(n) SkSqrtBits(n, 15) 37586b6a5e60a1e5c0e675cc42c9a01341c688efa4reed@google.com 384b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/////////////////////////////////////////////////////////////////////////////// 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 404b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com//! Returns the number of leading zero bits (0...32) 414b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.comint SkCLZ_portable(uint32_t); 428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 43867cbd8bc29371a360194aed648c4d43307b0639caryclark@google.com#if defined(SK_CPU_ARM) 444b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com #define SkCLZ(x) __builtin_clz(x) 454b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#endif 464b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com 474b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#ifndef SkCLZ 484b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com #define SkCLZ(x) SkCLZ_portable(x) 494b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#endif 50eebf5cb6c0f5ed2630de2e7712d61b4ec1d49015reed@android.com 514b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 524b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns (value < 0 ? 0 : value) efficiently (i.e. no compares or branches) 534b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkClampPos(int value) { 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return value & ~(value >> 31); 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given an integer and a positive (max) integer, return the value 594b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * pinned against 0 and max, inclusive. 604b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * @param value The value we want returned pinned between [0...max] 614b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * @param max The positive max value 624b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * @return 0 if value < 0, max if value > max, else value 634b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkClampMax(int value, int max) { 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // ensure that max is positive 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(max >= 0); 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (value < 0) { 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = 0; 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (value > max) { 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = max; 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return value; 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 764b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 774b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns the smallest power-of-2 that is >= the specified value. If value 784b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * is already a power of 2, then it is returned unchanged. It is undefined 794b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * if value is <= 0. 804b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkNextPow2(int value) { 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(value > 0); 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1 << (32 - SkCLZ(value - 1)); 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 864b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 874b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns the log2 of the specified value, were that value to be rounded up 884b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * to the next power of 2. It is undefined to pass 0. Examples: 894b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(1) -> 0 904b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(2) -> 1 914b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(3) -> 2 924b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(4) -> 2 934b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(5) -> 3 944b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkNextLog2(uint32_t value) { 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(value != 0); 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 32 - SkCLZ(value - 1); 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1004b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 1014b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns true if value is a power of 2. Does not explicitly check for 1024b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * value <= 0. 103f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com */ 104f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.comstatic inline bool SkIsPow2(int value) { 105f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com return (value & (value - 1)) == 0; 106f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com} 107f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1104b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 1114b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkMulS16(a, b) multiplies a * b, but requires that a and b are both int16_t. 1124b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * With this requirement, we can generate faster instructions on some 1134b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * architectures. 1144b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 1152092c40a0d0a89a91cc4b6bb2b1b992fd4f02cd7george@mozilla.com#ifdef SK_ARM_HAS_EDSP 1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static inline int32_t SkMulS16(S16CPU x, S16CPU y) { 1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((int16_t)x == x); 1188a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((int16_t)y == y); 1198a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com int32_t product; 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com asm("smulbb %0, %1, %2 \n" 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com : "=r"(product) 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com : "r"(x), "r"(y) 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ); 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return product; 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #ifdef SK_DEBUG 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static inline int32_t SkMulS16(S16CPU x, S16CPU y) { 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((int16_t)x == x); 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((int16_t)y == y); 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return x * y; 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #else 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #define SkMulS16(x, y) ((x) * (y)) 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #endif 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1384b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 1394b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Return a*b/((1 << shift) - 1), rounding any fractional bits. 1404b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Only valid if a and b are unsigned and <= 32767 and shift is > 0 and <= 8 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 142ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.comstatic inline unsigned SkMul16ShiftRound(U16CPU a, U16CPU b, int shift) { 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(a <= 32767); 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(b <= 32767); 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(shift > 0 && shift <= 8); 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned prod = SkMulS16(a, b) + (1 << (shift - 1)); 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (prod + (prod >> shift)) >> shift; 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1504b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 151ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com * Return a*b/255, rounding any fractional bits. 152ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com * Only valid if a and b are unsigned and <= 32767. 153a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com */ 154ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.comstatic inline U8CPU SkMulDiv255Round(U16CPU a, U16CPU b) { 155ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com SkASSERT(a <= 32767); 156ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com SkASSERT(b <= 32767); 1574b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com unsigned prod = SkMulS16(a, b) + 128; 158a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com return (prod + (prod >> 8)) >> 8; 159a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com} 160a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 162