intmath.hh revision 105
12SN/A/* 21762SN/A * Copyright (c) 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 292741Sksewell@umich.edu#ifndef __INTMATH_HH__ 302SN/A#define __INTMATH_HH__ 312SN/A 322439SN/A#include <assert.h> 33146SN/A 34146SN/A#include "sim/host.hh" 35146SN/A 36146SN/A// Returns the prime number one less than n. 37146SN/Aint PrevPrime(int n); 38146SN/A 391717SN/A// Determine if a number is prime 40146SN/Atemplate <class T> 411717SN/Ainline bool 42146SN/AIsPrime(T n) 431977SN/A{ 442623SN/A T i; 452683Sktlim@umich.edu 461717SN/A if (n == 2 || n == 3) 47146SN/A return true; 482683Sktlim@umich.edu 491917SN/A // Don't try every odd number to prove if it is a prime. 502592SN/A // Toggle between every 2nd and 4th number. 512683Sktlim@umich.edu // (This is because every 6th odd number is divisible by 3.) 522036SN/A for (i = 5; i*i <= n; i += 6) { 53146SN/A if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 5456SN/A return false; 5556SN/A } 5656SN/A } 57695SN/A 582901Ssaidi@eecs.umich.edu return true; 592SN/A} 601858SN/A 6156SN/Atemplate <class T> 622171SN/Ainline T 632170SN/ALeastSigBit(T n) 642170SN/A{ 65146SN/A return n & ~(n - 1); 662462SN/A} 67146SN/A 682SN/Atemplate <class T> 692SN/Ainline bool 702449SN/AIsPowerOf2(T n) 711355SN/A{ 722623SN/A return n != 0 && LeastSigBit(n) == n; 732683Sktlim@umich.edu} 74224SN/A 751858SN/Ainline int 762683Sktlim@umich.eduFloorLog2(uint32_t x) 772420SN/A{ 782683Sktlim@umich.edu assert(x > 0); 792520SN/A 802420SN/A int y = 0; 812SN/A 822683Sktlim@umich.edu if (x & 0xffff0000) { y += 16; x >>= 16; } 832672Sktlim@umich.edu if (x & 0x0000ff00) { y += 8; x >>= 8; } 842683Sktlim@umich.edu if (x & 0x000000f0) { y += 4; x >>= 4; } 852SN/A if (x & 0x0000000c) { y += 2; x >>= 2; } 862SN/A if (x & 0x00000002) { y += 1; } 87334SN/A 88140SN/A return y; 89334SN/A} 902SN/A 912SN/Ainline int 922SN/AFloorLog2(uint64_t x) 932680Sktlim@umich.edu{ 942SN/A assert(x > 0); 952SN/A 962623SN/A int y = 0; 972SN/A 982SN/A if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 992SN/A if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 100180SN/A if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 1012623SN/A if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 102393SN/A if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 103393SN/A if (x & ULL(0x0000000000000002)) { y += 1; } 104393SN/A 105393SN/A return y; 106384SN/A} 107384SN/A 108393SN/Ainline int 1092623SN/AFloorLog2(int32_t x) 110393SN/A{ 111393SN/A assert(x > 0); 112393SN/A return FloorLog2(x); 113393SN/A} 114384SN/A 115189SN/Ainline int 116189SN/AFloorLog2(int64_t x) 1172623SN/A{ 1182SN/A assert(x > 0); 119729SN/A return FloorLog2(x); 120334SN/A} 1212SN/A 1222SN/Atemplate <class T> 1232SN/Ainline int 1242SN/ACeilLog2(T n) 1252SN/A{ 1262SN/A if (n == 1) 1272SN/A return 0; 1282SN/A 1292SN/A return FloorLog2(n - (T)1) + 1; 1302SN/A} 1312SN/A 1322SN/Atemplate <class T> 1331001SN/Ainline T 1341001SN/AFloorPow2(T n) 1351001SN/A{ 1361001SN/A return (T)1 << FloorLog2(n); 1371001SN/A} 1382SN/A 1392SN/Atemplate <class T> 1402SN/Ainline T 1412SN/ACeilPow2(T n) 1422SN/A{ 1432SN/A return (T)1 << CeilLog2(n); 1442SN/A} 1452SN/A 1462SN/Atemplate <class T> 1472SN/Ainline T 1482SN/ADivCeil(T a, T b) 1492SN/A{ 1502SN/A return (a + b - 1) / b; 1512SN/A} 1522SN/A 1532SN/Atemplate <class T> 1542SN/Ainline T 1552390SN/ARoundUp(T val, T align) 1562390SN/A{ 1572390SN/A T mask = align - 1; 1582390SN/A return (val + mask) & ~mask; 1592390SN/A} 1602390SN/A 1612390SN/Atemplate <class T> 1622390SN/Ainline T 1632390SN/ARoundDown(T val, T align) 1642390SN/A{ 1652390SN/A T mask = align - 1; 1662390SN/A return val & ~mask; 167385SN/A} 1682SN/A 1692SN/Ainline bool 1702SN/AIsHex(char c) 1712623SN/A{ 172334SN/A return c >= '0' && c <= '9' || 173334SN/A c >= 'A' && c <= 'F' || 1742623SN/A c >= 'a' && c <= 'f'; 175334SN/A} 176334SN/A 177334SN/Ainline bool 1782623SN/AIsOct(char c) 1792SN/A{ 180921SN/A return c >= '0' && c <= '7'; 181224SN/A} 182237SN/A 1832683Sktlim@umich.eduinline bool 1842SN/AIsDec(char c) 1852SN/A{ 1862SN/A return c >= '0' && c <= '9'; 1872623SN/A} 1882SN/A 189921SN/Ainline int 190224SN/AHex2Int(char c) 1912683Sktlim@umich.edu{ 1922SN/A if (c >= '0' && c <= '9') 1932SN/A return (c - '0'); 1942SN/A 1952SN/A if (c >= 'A' && c <= 'F') 1962SN/A return (c - 'A') + 10; 1972SN/A 1982SN/A if (c >= 'a' && c <= 'f') 199595SN/A return (c - 'a') + 10; 2002623SN/A 201595SN/A return 0; 2022390SN/A} 2031080SN/A 2041080SN/A#endif // __INTMATH_HH__ 2051080SN/A