intmath.hh revision 9091
12SN/A/* 21762SN/A * Copyright (c) 2001, 2003-2005 The Regents of The University of Michigan 32SN/A * All rights reserved. 42SN/A * 52SN/A * Redistribution and use in source and binary forms, with or without 62SN/A * modification, are permitted provided that the following conditions are 72SN/A * met: redistributions of source code must retain the above copyright 82SN/A * notice, this list of conditions and the following disclaimer; 92SN/A * redistributions in binary form must reproduce the above copyright 102SN/A * notice, this list of conditions and the following disclaimer in the 112SN/A * documentation and/or other materials provided with the distribution; 122SN/A * neither the name of the copyright holders nor the names of its 132SN/A * contributors may be used to endorse or promote products derived from 142SN/A * this software without specific prior written permission. 152SN/A * 162SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272665Ssaidi@eecs.umich.edu * 282665Ssaidi@eecs.umich.edu * Authors: Nathan Binkert 292SN/A */ 302SN/A 316216Snate@binkert.org#ifndef __BASE_INTMATH_HH__ 326216Snate@binkert.org#define __BASE_INTMATH_HH__ 332SN/A 346216Snate@binkert.org#include <cassert> 35100SN/A 367584SAli.Saidi@arm.com#include "base/misc.hh" 376214Snate@binkert.org#include "base/types.hh" 38100SN/A 392SN/A// Returns the prime number one less than n. 402020SN/Aint prevPrime(int n); 412SN/A 422SN/A// Determine if a number is prime 4350SN/Atemplate <class T> 442SN/Ainline bool 452020SN/AisPrime(T n) 462SN/A{ 4750SN/A T i; 482SN/A 4950SN/A if (n == 2 || n == 3) 5050SN/A return true; 5150SN/A 5250SN/A // Don't try every odd number to prove if it is a prime. 5350SN/A // Toggle between every 2nd and 4th number. 5450SN/A // (This is because every 6th odd number is divisible by 3.) 5550SN/A for (i = 5; i*i <= n; i += 6) { 5650SN/A if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 5750SN/A return false; 5850SN/A } 5950SN/A } 6050SN/A 612SN/A return true; 622SN/A} 632SN/A 6450SN/Atemplate <class T> 6550SN/Ainline T 662020SN/AleastSigBit(T n) 672SN/A{ 6850SN/A return n & ~(n - 1); 692SN/A} 702SN/A 7150SN/Atemplate <class T> 7250SN/Ainline bool 732020SN/AisPowerOf2(T n) 7450SN/A{ 752020SN/A return n != 0 && leastSigBit(n) == n; 7650SN/A} 7750SN/A 787584SAli.Saidi@arm.cominline uint64_t 797584SAli.Saidi@arm.compower(uint32_t n, uint32_t e) 807584SAli.Saidi@arm.com{ 817584SAli.Saidi@arm.com if (e > 20) 827584SAli.Saidi@arm.com warn("Warning, power() function is quite slow for large exponents\n"); 837584SAli.Saidi@arm.com 847584SAli.Saidi@arm.com if (e == 0) 857584SAli.Saidi@arm.com return 1; 867584SAli.Saidi@arm.com 877584SAli.Saidi@arm.com uint64_t result = n; 887584SAli.Saidi@arm.com uint64_t old_result = 0; 897584SAli.Saidi@arm.com for (int x = 1; x < e; x++) { 907584SAli.Saidi@arm.com old_result = result; 917584SAli.Saidi@arm.com result *= n; 927584SAli.Saidi@arm.com if (old_result > result) 937584SAli.Saidi@arm.com warn("power() overflowed!\n"); 947584SAli.Saidi@arm.com } 957584SAli.Saidi@arm.com return result; 967584SAli.Saidi@arm.com} 977584SAli.Saidi@arm.com 987584SAli.Saidi@arm.com 992SN/Ainline int 1002020SN/AfloorLog2(unsigned x) 10150SN/A{ 102100SN/A assert(x > 0); 1032SN/A 10450SN/A int y = 0; 1052SN/A 10650SN/A if (x & 0xffff0000) { y += 16; x >>= 16; } 10750SN/A if (x & 0x0000ff00) { y += 8; x >>= 8; } 10850SN/A if (x & 0x000000f0) { y += 4; x >>= 4; } 10950SN/A if (x & 0x0000000c) { y += 2; x >>= 2; } 11050SN/A if (x & 0x00000002) { y += 1; } 11150SN/A 11250SN/A return y; 11350SN/A} 11450SN/A 115100SN/Ainline int 1162020SN/AfloorLog2(unsigned long x) 1171642SN/A{ 1181642SN/A assert(x > 0); 1191642SN/A 1201642SN/A int y = 0; 1211642SN/A 1221642SN/A#if defined(__LP64__) 1231642SN/A if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1241642SN/A#endif 1251642SN/A if (x & 0xffff0000) { y += 16; x >>= 16; } 1261642SN/A if (x & 0x0000ff00) { y += 8; x >>= 8; } 1271642SN/A if (x & 0x000000f0) { y += 4; x >>= 4; } 1281642SN/A if (x & 0x0000000c) { y += 2; x >>= 2; } 1291642SN/A if (x & 0x00000002) { y += 1; } 1301642SN/A 1311642SN/A return y; 1321642SN/A} 1331642SN/A 1341642SN/Ainline int 1352020SN/AfloorLog2(unsigned long long x) 136100SN/A{ 137100SN/A assert(x > 0); 138100SN/A 139100SN/A int y = 0; 140100SN/A 141100SN/A if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 142100SN/A if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 143100SN/A if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 144100SN/A if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 145100SN/A if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 146100SN/A if (x & ULL(0x0000000000000002)) { y += 1; } 147100SN/A 148100SN/A return y; 149100SN/A} 150100SN/A 151100SN/Ainline int 1522020SN/AfloorLog2(int x) 153100SN/A{ 154100SN/A assert(x > 0); 1552020SN/A return floorLog2((unsigned)x); 156100SN/A} 157100SN/A 158100SN/Ainline int 1592020SN/AfloorLog2(long x) 160100SN/A{ 161100SN/A assert(x > 0); 1622020SN/A return floorLog2((unsigned long)x); 1631642SN/A} 1641642SN/A 1651642SN/Ainline int 1662020SN/AfloorLog2(long long x) 1671642SN/A{ 1681642SN/A assert(x > 0); 1692020SN/A return floorLog2((unsigned long long)x); 170100SN/A} 171100SN/A 17250SN/Atemplate <class T> 17350SN/Ainline int 1742020SN/AceilLog2(T n) 17550SN/A{ 176100SN/A if (n == 1) 177100SN/A return 0; 178100SN/A 1792020SN/A return floorLog2(n - (T)1) + 1; 18050SN/A} 18150SN/A 18250SN/Atemplate <class T> 18350SN/Ainline T 1842020SN/AfloorPow2(T n) 18550SN/A{ 1862020SN/A return (T)1 << floorLog2(n); 18750SN/A} 18850SN/A 18950SN/Atemplate <class T> 19050SN/Ainline T 1912020SN/AceilPow2(T n) 19250SN/A{ 1932020SN/A return (T)1 << ceilLog2(n); 19450SN/A} 1952SN/A 1969091Sandreas.hansson@arm.comtemplate <class T, class U> 19752SN/Ainline T 1989091Sandreas.hansson@arm.comdivCeil(const T& a, const U& b) 19952SN/A{ 20052SN/A return (a + b - 1) / b; 20152SN/A} 20252SN/A 20352SN/Atemplate <class T> 20452SN/Ainline T 2052021SN/AroundUp(T val, int align) 20652SN/A{ 2072021SN/A T mask = (T)align - 1; 20852SN/A return (val + mask) & ~mask; 20952SN/A} 21052SN/A 21152SN/Atemplate <class T> 21252SN/Ainline T 2132418SN/AroundDown(T val, int align) 21452SN/A{ 2152418SN/A T mask = (T)align - 1; 21652SN/A return val & ~mask; 21752SN/A} 21852SN/A 2192SN/Ainline bool 2202020SN/AisHex(char c) 22150SN/A{ 2225570Snate@binkert.org return (c >= '0' && c <= '9') || 2235570Snate@binkert.org (c >= 'A' && c <= 'F') || 2245570Snate@binkert.org (c >= 'a' && c <= 'f'); 2252SN/A} 2262SN/A 2272SN/Ainline bool 2282020SN/AisOct(char c) 22950SN/A{ 23050SN/A return c >= '0' && c <= '7'; 23150SN/A} 2322SN/A 2332SN/Ainline bool 2342020SN/AisDec(char c) 23550SN/A{ 23650SN/A return c >= '0' && c <= '9'; 23750SN/A} 2382SN/A 2392SN/Ainline int 2402020SN/Ahex2Int(char c) 2412SN/A{ 2422SN/A if (c >= '0' && c <= '9') 2432SN/A return (c - '0'); 2442SN/A 245105SN/A if (c >= 'A' && c <= 'F') 2462SN/A return (c - 'A') + 10; 2472SN/A 2482SN/A if (c >= 'a' && c <= 'f') 2492SN/A return (c - 'a') + 10; 2502SN/A 2512SN/A return 0; 2522SN/A} 2532SN/A 2546216Snate@binkert.org#endif // __BASE_INTMATH_HH__ 255