SkMath.h revision 7729534da419436ea6127545e9f79b0b47ccffb4
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 4344d37d9d7228e7409f4feea722c26f570434b8fdreed@google.com#ifndef SkCLZ 447729534da419436ea6127545e9f79b0b47ccffb4reed@google.com #if defined(_MSC_VER) && _MSC_VER >= 1400 457729534da419436ea6127545e9f79b0b47ccffb4reed@google.com #include <intrin.h> 467729534da419436ea6127545e9f79b0b47ccffb4reed@google.com 477729534da419436ea6127545e9f79b0b47ccffb4reed@google.com static inline int SkCLZ(uint32_t mask) { 487729534da419436ea6127545e9f79b0b47ccffb4reed@google.com if (mask) { 497729534da419436ea6127545e9f79b0b47ccffb4reed@google.com DWORD index; 507729534da419436ea6127545e9f79b0b47ccffb4reed@google.com _BitScanReverse(&index, mask); 517729534da419436ea6127545e9f79b0b47ccffb4reed@google.com return index ^ 0x1F; 527729534da419436ea6127545e9f79b0b47ccffb4reed@google.com } else { 537729534da419436ea6127545e9f79b0b47ccffb4reed@google.com return 32; 547729534da419436ea6127545e9f79b0b47ccffb4reed@google.com } 557729534da419436ea6127545e9f79b0b47ccffb4reed@google.com } 567729534da419436ea6127545e9f79b0b47ccffb4reed@google.com #elif defined(SK_CPU_ARM) || defined(__GNUC__) 577729534da419436ea6127545e9f79b0b47ccffb4reed@google.com #define SkCLZ(x) __builtin_clz(x) 587729534da419436ea6127545e9f79b0b47ccffb4reed@google.com #else 597729534da419436ea6127545e9f79b0b47ccffb4reed@google.com #define SkCLZ(x) SkCLZ_portable(x) 607729534da419436ea6127545e9f79b0b47ccffb4reed@google.com #endif 614b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com#endif 62eebf5cb6c0f5ed2630de2e7712d61b4ec1d49015reed@android.com 634b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 644b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns (value < 0 ? 0 : value) efficiently (i.e. no compares or branches) 654b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkClampPos(int value) { 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return value & ~(value >> 31); 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given an integer and a positive (max) integer, return the value 714b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * pinned against 0 and max, inclusive. 724b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * @param value The value we want returned pinned between [0...max] 734b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * @param max The positive max value 744b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * @return 0 if value < 0, max if value > max, else value 754b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkClampMax(int value, int max) { 778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com // ensure that max is positive 788a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(max >= 0); 798a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (value < 0) { 808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = 0; 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if (value > max) { 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com value = max; 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return value; 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 884b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 894b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns the smallest power-of-2 that is >= the specified value. If value 904b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * is already a power of 2, then it is returned unchanged. It is undefined 914b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * if value is <= 0. 924b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkNextPow2(int value) { 948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(value > 0); 958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 1 << (32 - SkCLZ(value - 1)); 968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 984b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 994b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns the log2 of the specified value, were that value to be rounded up 1004b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * to the next power of 2. It is undefined to pass 0. Examples: 1014b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(1) -> 0 1024b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(2) -> 1 1034b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(3) -> 2 1044b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(4) -> 2 1054b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkNextLog2(5) -> 3 1064b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comstatic inline int SkNextLog2(uint32_t value) { 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(value != 0); 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return 32 - SkCLZ(value - 1); 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1124b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 1134b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Returns true if value is a power of 2. Does not explicitly check for 1144b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * value <= 0. 115f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com */ 116f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.comstatic inline bool SkIsPow2(int value) { 117f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com return (value & (value - 1)) == 0; 118f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com} 119f2b98d67dcb6fcb3120feede9c72016fc7b3ead8reed@android.com 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1224b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 1234b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * SkMulS16(a, b) multiplies a * b, but requires that a and b are both int16_t. 1244b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * With this requirement, we can generate faster instructions on some 1254b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * architectures. 1264b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com */ 1272092c40a0d0a89a91cc4b6bb2b1b992fd4f02cd7george@mozilla.com#ifdef SK_ARM_HAS_EDSP 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 int32_t product; 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com asm("smulbb %0, %1, %2 \n" 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com : "=r"(product) 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com : "r"(x), "r"(y) 1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com ); 1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return product; 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#else 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #ifdef SK_DEBUG 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com static inline int32_t SkMulS16(S16CPU x, S16CPU y) { 1418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((int16_t)x == x); 1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT((int16_t)y == y); 1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return x * y; 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com } 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #else 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #define SkMulS16(x, y) ((x) * (y)) 1478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com #endif 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1504b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 1514b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Return a*b/((1 << shift) - 1), rounding any fractional bits. 1524b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com * Only valid if a and b are unsigned and <= 32767 and shift is > 0 and <= 8 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com */ 154ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.comstatic inline unsigned SkMul16ShiftRound(U16CPU a, U16CPU b, int shift) { 1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(a <= 32767); 1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(b <= 32767); 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkASSERT(shift > 0 && shift <= 8); 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com unsigned prod = SkMulS16(a, b) + (1 << (shift - 1)); 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com return (prod + (prod >> shift)) >> shift; 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com} 1618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1624b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com/** 163ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com * Return a*b/255, rounding any fractional bits. 164ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com * Only valid if a and b are unsigned and <= 32767. 165a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com */ 166ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.comstatic inline U8CPU SkMulDiv255Round(U16CPU a, U16CPU b) { 167ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com SkASSERT(a <= 32767); 168ea774d2a5a049bf89474c0f047ed6a4e521de126reed@google.com SkASSERT(b <= 32767); 1694b163ed2c22facbe8891616874ae07ba7827d9c9reed@google.com unsigned prod = SkMulS16(a, b) + 128; 170a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com return (prod + (prod >> 8)) >> 8; 171a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com} 172a0f5d1546d499ef0cd7dbfba9a866ae5a27e1541reed@android.com 1738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 174