intmath.hh revision 6214
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 3150SN/A#ifndef __INTMATH_HH__ 3250SN/A#define __INTMATH_HH__ 332SN/A 34100SN/A#include <assert.h> 35100SN/A 366214Snate@binkert.org#include "base/types.hh" 37100SN/A 382SN/A// Returns the prime number one less than n. 392020SN/Aint prevPrime(int n); 402SN/A 412SN/A// Determine if a number is prime 4250SN/Atemplate <class T> 432SN/Ainline bool 442020SN/AisPrime(T n) 452SN/A{ 4650SN/A T i; 472SN/A 4850SN/A if (n == 2 || n == 3) 4950SN/A return true; 5050SN/A 5150SN/A // Don't try every odd number to prove if it is a prime. 5250SN/A // Toggle between every 2nd and 4th number. 5350SN/A // (This is because every 6th odd number is divisible by 3.) 5450SN/A for (i = 5; i*i <= n; i += 6) { 5550SN/A if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 5650SN/A return false; 5750SN/A } 5850SN/A } 5950SN/A 602SN/A return true; 612SN/A} 622SN/A 6350SN/Atemplate <class T> 6450SN/Ainline T 652020SN/AleastSigBit(T n) 662SN/A{ 6750SN/A return n & ~(n - 1); 682SN/A} 692SN/A 7050SN/Atemplate <class T> 7150SN/Ainline bool 722020SN/AisPowerOf2(T n) 7350SN/A{ 742020SN/A return n != 0 && leastSigBit(n) == n; 7550SN/A} 7650SN/A 772SN/Ainline int 782020SN/AfloorLog2(unsigned x) 7950SN/A{ 80100SN/A assert(x > 0); 812SN/A 8250SN/A int y = 0; 832SN/A 8450SN/A if (x & 0xffff0000) { y += 16; x >>= 16; } 8550SN/A if (x & 0x0000ff00) { y += 8; x >>= 8; } 8650SN/A if (x & 0x000000f0) { y += 4; x >>= 4; } 8750SN/A if (x & 0x0000000c) { y += 2; x >>= 2; } 8850SN/A if (x & 0x00000002) { y += 1; } 8950SN/A 9050SN/A return y; 9150SN/A} 9250SN/A 93100SN/Ainline int 942020SN/AfloorLog2(unsigned long x) 951642SN/A{ 961642SN/A assert(x > 0); 971642SN/A 981642SN/A int y = 0; 991642SN/A 1001642SN/A#if defined(__LP64__) 1011642SN/A if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1021642SN/A#endif 1031642SN/A if (x & 0xffff0000) { y += 16; x >>= 16; } 1041642SN/A if (x & 0x0000ff00) { y += 8; x >>= 8; } 1051642SN/A if (x & 0x000000f0) { y += 4; x >>= 4; } 1061642SN/A if (x & 0x0000000c) { y += 2; x >>= 2; } 1071642SN/A if (x & 0x00000002) { y += 1; } 1081642SN/A 1091642SN/A return y; 1101642SN/A} 1111642SN/A 1121642SN/Ainline int 1132020SN/AfloorLog2(unsigned long long x) 114100SN/A{ 115100SN/A assert(x > 0); 116100SN/A 117100SN/A int y = 0; 118100SN/A 119100SN/A if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 120100SN/A if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 121100SN/A if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 122100SN/A if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 123100SN/A if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 124100SN/A if (x & ULL(0x0000000000000002)) { y += 1; } 125100SN/A 126100SN/A return y; 127100SN/A} 128100SN/A 129100SN/Ainline int 1302020SN/AfloorLog2(int x) 131100SN/A{ 132100SN/A assert(x > 0); 1332020SN/A return floorLog2((unsigned)x); 134100SN/A} 135100SN/A 136100SN/Ainline int 1372020SN/AfloorLog2(long x) 138100SN/A{ 139100SN/A assert(x > 0); 1402020SN/A return floorLog2((unsigned long)x); 1411642SN/A} 1421642SN/A 1431642SN/Ainline int 1442020SN/AfloorLog2(long long x) 1451642SN/A{ 1461642SN/A assert(x > 0); 1472020SN/A return floorLog2((unsigned long long)x); 148100SN/A} 149100SN/A 15050SN/Atemplate <class T> 15150SN/Ainline int 1522020SN/AceilLog2(T n) 15350SN/A{ 154100SN/A if (n == 1) 155100SN/A return 0; 156100SN/A 1572020SN/A return floorLog2(n - (T)1) + 1; 15850SN/A} 15950SN/A 16050SN/Atemplate <class T> 16150SN/Ainline T 1622020SN/AfloorPow2(T n) 16350SN/A{ 1642020SN/A return (T)1 << floorLog2(n); 16550SN/A} 16650SN/A 16750SN/Atemplate <class T> 16850SN/Ainline T 1692020SN/AceilPow2(T n) 17050SN/A{ 1712020SN/A return (T)1 << ceilLog2(n); 17250SN/A} 1732SN/A 17452SN/Atemplate <class T> 17552SN/Ainline T 1762020SN/AdivCeil(T a, T b) 17752SN/A{ 17852SN/A return (a + b - 1) / b; 17952SN/A} 18052SN/A 18152SN/Atemplate <class T> 18252SN/Ainline T 1832021SN/AroundUp(T val, int align) 18452SN/A{ 1852021SN/A T mask = (T)align - 1; 18652SN/A return (val + mask) & ~mask; 18752SN/A} 18852SN/A 18952SN/Atemplate <class T> 19052SN/Ainline T 1912418SN/AroundDown(T val, int align) 19252SN/A{ 1932418SN/A T mask = (T)align - 1; 19452SN/A return val & ~mask; 19552SN/A} 19652SN/A 1972SN/Ainline bool 1982020SN/AisHex(char c) 19950SN/A{ 2005570Snate@binkert.org return (c >= '0' && c <= '9') || 2015570Snate@binkert.org (c >= 'A' && c <= 'F') || 2025570Snate@binkert.org (c >= 'a' && c <= 'f'); 2032SN/A} 2042SN/A 2052SN/Ainline bool 2062020SN/AisOct(char c) 20750SN/A{ 20850SN/A return c >= '0' && c <= '7'; 20950SN/A} 2102SN/A 2112SN/Ainline bool 2122020SN/AisDec(char c) 21350SN/A{ 21450SN/A return c >= '0' && c <= '9'; 21550SN/A} 2162SN/A 2172SN/Ainline int 2182020SN/Ahex2Int(char c) 2192SN/A{ 2202SN/A if (c >= '0' && c <= '9') 2212SN/A return (c - '0'); 2222SN/A 223105SN/A if (c >= 'A' && c <= 'F') 2242SN/A return (c - 'A') + 10; 2252SN/A 2262SN/A if (c >= 'a' && c <= 'f') 2272SN/A return (c - 'a') + 10; 2282SN/A 2292SN/A return 0; 2302SN/A} 2312SN/A 23250SN/A#endif // __INTMATH_HH__ 233