intmath.hh revision 1642
12SN/A/* 21762SN/A * Copyright (c) 2001, 2003 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 292665Ssaidi@eecs.umich.edu#ifndef __INTMATH_HH__ 302SN/A#define __INTMATH_HH__ 312SN/A 321388SN/A#include <assert.h> 332SN/A 342SN/A#include "sim/host.hh" 352SN/A 361191SN/A// Returns the prime number one less than n. 371191SN/Aint PrevPrime(int n); 381191SN/A 391388SN/A// Determine if a number is prime 405529Snate@binkert.orgtemplate <class T> 411717SN/Ainline bool 422651Ssaidi@eecs.umich.eduIsPrime(T n) 432680Sktlim@umich.edu{ 441977SN/A T i; 455529Snate@binkert.org 463144Shsul@eecs.umich.edu if (n == 2 || n == 3) 472190SN/A return true; 4856SN/A 492190SN/A // Don't try every odd number to prove if it is a prime. 502SN/A // Toggle between every 2nd and 4th number. 512359SN/A // (This is because every 6th odd number is divisible by 3.) 522359SN/A for (i = 5; i*i <= n; i += 6) { 532359SN/A if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 542SN/A return false; 552SN/A } 562SN/A } 572SN/A 582SN/A return true; 592SN/A} 602SN/A 612SN/Atemplate <class T> 622SN/Ainline T 633126Sktlim@umich.eduLeastSigBit(T n) 643126Sktlim@umich.edu{ 654075Sbinkertn@umich.edu return n & ~(n - 1); 663126Sktlim@umich.edu} 673126Sktlim@umich.edu 683126Sktlim@umich.edutemplate <class T> 693126Sktlim@umich.eduinline bool 703126Sktlim@umich.eduIsPowerOf2(T n) 713126Sktlim@umich.edu{ 722356SN/A return n != 0 && LeastSigBit(n) == n; 732356SN/A} 742356SN/A 752367SN/Ainline int 762356SN/AFloorLog2(unsigned x) 775100Ssaidi@eecs.umich.edu{ 782367SN/A assert(x > 0); 792356SN/A 802356SN/A int y = 0; 812356SN/A 822367SN/A if (x & 0xffff0000) { y += 16; x >>= 16; } 832367SN/A if (x & 0x0000ff00) { y += 8; x >>= 8; } 842367SN/A if (x & 0x000000f0) { y += 4; x >>= 4; } 852367SN/A if (x & 0x0000000c) { y += 2; x >>= 2; } 862356SN/A if (x & 0x00000002) { y += 1; } 872356SN/A 882356SN/A return y; 892356SN/A} 902356SN/A 915336Shines@cs.fsu.eduinline int 922356SN/AFloorLog2(unsigned long x) 934873Sstever@eecs.umich.edu{ 942356SN/A assert(x > 0); 952356SN/A 961858SN/A int y = 0; 971400SN/A 985529Snate@binkert.org#if defined(__LP64__) 995529Snate@binkert.org if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1003661Srdreslin@umich.edu#endif 1012SN/A if (x & 0xffff0000) { y += 16; x >>= 16; } 1021400SN/A if (x & 0x0000ff00) { y += 8; x >>= 8; } 1035529Snate@binkert.org if (x & 0x000000f0) { y += 4; x >>= 4; } 1045529Snate@binkert.org if (x & 0x0000000c) { y += 2; x >>= 2; } 1053661Srdreslin@umich.edu if (x & 0x00000002) { y += 1; } 1062SN/A 1072SN/A return y; 1082359SN/A} 1091062SN/A 1102SN/Ainline int 1112SN/AFloorLog2(unsigned long long x) 1122SN/A{ 1132SN/A assert(x > 0); 1142SN/A 1152SN/A int y = 0; 1162SN/A 1171354SN/A if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1182SN/A if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 119503SN/A if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 1202SN/A if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 1212SN/A if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 1222SN/A if (x & ULL(0x0000000000000002)) { y += 1; } 1232SN/A 1241400SN/A return y; 1252SN/A} 1263144Shsul@eecs.umich.edu 1273144Shsul@eecs.umich.eduinline int 1283144Shsul@eecs.umich.eduFloorLog2(int x) 1292SN/A{ 1301400SN/A assert(x > 0); 1312SN/A return FloorLog2((unsigned)x); 1322SN/A} 1332SN/A 1342SN/Ainline int 1352SN/AFloorLog2(long x) 1362SN/A{ 137503SN/A assert(x > 0); 1382SN/A return FloorLog2((unsigned long)x); 1391400SN/A} 1402SN/A 1412SN/Ainline int 142124SN/AFloorLog2(long long x) 1431354SN/A{ 144124SN/A assert(x > 0); 145124SN/A return FloorLog2((unsigned long long)x); 146124SN/A} 147124SN/A 148124SN/A#if defined(__APPLE__) 149124SN/Ainline int 1501400SN/AFloorLog2(size_t x) 151124SN/A{ 1523144Shsul@eecs.umich.edu assert(x > 0); 1533144Shsul@eecs.umich.edu assert(sizeof(size_t) == 4 || sizeof(size_t) == 8); 1543144Shsul@eecs.umich.edu 155124SN/A // It's my hope that this is optimized away? 1561400SN/A if (sizeof(size_t) == 4) 157124SN/A return FloorLog2((uint32_t)x); 158124SN/A else if (sizeof(size_t) == 8) 159124SN/A return FloorLog2((uint64_t)x); 160124SN/A 161124SN/A} 162124SN/A#endif 163124SN/A 164124SN/Atemplate <class T> 1651400SN/Ainline int 166124SN/ACeilLog2(T n) 167124SN/A{ 1681191SN/A if (n == 1) 1695529Snate@binkert.org return 0; 1701388SN/A 1711191SN/A return FloorLog2(n - (T)1) + 1; 1725529Snate@binkert.org} 1731191SN/A 1745529Snate@binkert.orgtemplate <class T> 1751191SN/Ainline T 1761191SN/AFloorPow2(T n) 1775529Snate@binkert.org{ 1785529Snate@binkert.org return (T)1 << FloorLog2(n); 1795529Snate@binkert.org} 1801191SN/A 1811191SN/Atemplate <class T> 1821917SN/Ainline T 1831917SN/ACeilPow2(T n) 1845529Snate@binkert.org{ 1855529Snate@binkert.org return (T)1 << CeilLog2(n); 1861917SN/A} 1875529Snate@binkert.org 1881917SN/Atemplate <class T> 1891191SN/Ainline T 1901191SN/ADivCeil(T a, T b) 1911191SN/A{ 1921191SN/A return (a + b - 1) / b; 1931191SN/A} 1941191SN/A 1951191SN/Atemplate <class T> 1961191SN/Ainline T 1971191SN/ARoundUp(T val, T align) 1981191SN/A{ 1991191SN/A T mask = align - 1; 2001129SN/A return (val + mask) & ~mask; 2011129SN/A} 2021129SN/A 2035529Snate@binkert.orgtemplate <class T> 2042680Sktlim@umich.eduinline T 2051129SN/ARoundDown(T val, T align) 206180SN/A{ 2072SN/A T mask = align - 1; 2081917SN/A return val & ~mask; 2091917SN/A} 2101917SN/A 2115529Snate@binkert.orginline bool 2121917SN/AIsHex(char c) 2131917SN/A{ 2142356SN/A return c >= '0' && c <= '9' || 2155529Snate@binkert.org c >= 'A' && c <= 'F' || 2164031Sktlim@umich.edu c >= 'a' && c <= 'f'; 2175529Snate@binkert.org} 2182356SN/A 2192356SN/Ainline bool 2201917SN/AIsOct(char c) 2211917SN/A{ 2221917SN/A return c >= '0' && c <= '7'; 2231917SN/A} 2242SN/A 2252SN/Ainline bool 226729SN/AIsDec(char c) 227707SN/A{ 228707SN/A return c >= '0' && c <= '9'; 229707SN/A} 230707SN/A 231707SN/Ainline int 232707SN/AHex2Int(char c) 2332680Sktlim@umich.edu{ 2342SN/A if (c >= '0' && c <= '9') 2352SN/A return (c - '0'); 2362SN/A 2372SN/A if (c >= 'A' && c <= 'F') 2382680Sktlim@umich.edu return (c - 'A') + 10; 2392SN/A 2402SN/A if (c >= 'a' && c <= 'f') 2412680Sktlim@umich.edu return (c - 'a') + 10; 2422190SN/A 2432190SN/A return 0; 2442190SN/A} 2452SN/A 2462SN/A#endif // __INTMATH_HH__ 2473495Sktlim@umich.edu