intmath.hh revision 1762
17635SBrad.Beckmann@amd.com/* 27635SBrad.Beckmann@amd.com * Copyright (c) 2001, 2003-2005 The Regents of The University of Michigan 37635SBrad.Beckmann@amd.com * All rights reserved. 47635SBrad.Beckmann@amd.com * 57635SBrad.Beckmann@amd.com * Redistribution and use in source and binary forms, with or without 67635SBrad.Beckmann@amd.com * modification, are permitted provided that the following conditions are 77635SBrad.Beckmann@amd.com * met: redistributions of source code must retain the above copyright 87635SBrad.Beckmann@amd.com * notice, this list of conditions and the following disclaimer; 97635SBrad.Beckmann@amd.com * redistributions in binary form must reproduce the above copyright 107635SBrad.Beckmann@amd.com * notice, this list of conditions and the following disclaimer in the 117635SBrad.Beckmann@amd.com * documentation and/or other materials provided with the distribution; 127635SBrad.Beckmann@amd.com * neither the name of the copyright holders nor the names of its 137635SBrad.Beckmann@amd.com * contributors may be used to endorse or promote products derived from 147635SBrad.Beckmann@amd.com * this software without specific prior written permission. 157635SBrad.Beckmann@amd.com * 167635SBrad.Beckmann@amd.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 177635SBrad.Beckmann@amd.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 187635SBrad.Beckmann@amd.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 197635SBrad.Beckmann@amd.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 207635SBrad.Beckmann@amd.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 217635SBrad.Beckmann@amd.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 227635SBrad.Beckmann@amd.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 237635SBrad.Beckmann@amd.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 247635SBrad.Beckmann@amd.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 257635SBrad.Beckmann@amd.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 267635SBrad.Beckmann@amd.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 277635SBrad.Beckmann@amd.com */ 287635SBrad.Beckmann@amd.com 297635SBrad.Beckmann@amd.com#ifndef __INTMATH_HH__ 307635SBrad.Beckmann@amd.com#define __INTMATH_HH__ 3112564Sgabeblack@google.com 3212564Sgabeblack@google.com#include <assert.h> 337635SBrad.Beckmann@amd.com 347635SBrad.Beckmann@amd.com#include "sim/host.hh" 357635SBrad.Beckmann@amd.com 367635SBrad.Beckmann@amd.com// Returns the prime number one less than n. 377635SBrad.Beckmann@amd.comint PrevPrime(int n); 3811682Sandreas.hansson@arm.com 3911670Sandreas.hansson@arm.com// Determine if a number is prime 407635SBrad.Beckmann@amd.comtemplate <class T> 4111682Sandreas.hansson@arm.cominline bool 4211670Sandreas.hansson@arm.comIsPrime(T n) 437635SBrad.Beckmann@amd.com{ 447635SBrad.Beckmann@amd.com T i; 457635SBrad.Beckmann@amd.com 467635SBrad.Beckmann@amd.com if (n == 2 || n == 3) 477635SBrad.Beckmann@amd.com return true; 487635SBrad.Beckmann@amd.com 4911688Sandreas.hansson@arm.com // Don't try every odd number to prove if it is a prime. 507635SBrad.Beckmann@amd.com // Toggle between every 2nd and 4th number. 5110083Snilay@cs.wisc.edu // (This is because every 6th odd number is divisible by 3.) 527635SBrad.Beckmann@amd.com for (i = 5; i*i <= n; i += 6) { 537635SBrad.Beckmann@amd.com if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 547635SBrad.Beckmann@amd.com return false; 557635SBrad.Beckmann@amd.com } 567635SBrad.Beckmann@amd.com } 577635SBrad.Beckmann@amd.com 588436SBrad.Beckmann@amd.com return true; 598436SBrad.Beckmann@amd.com} 608436SBrad.Beckmann@amd.com 618436SBrad.Beckmann@amd.comtemplate <class T> 627635SBrad.Beckmann@amd.cominline T 637635SBrad.Beckmann@amd.comLeastSigBit(T n) 647635SBrad.Beckmann@amd.com{ 657635SBrad.Beckmann@amd.com return n & ~(n - 1); 667635SBrad.Beckmann@amd.com} 677635SBrad.Beckmann@amd.com 6813731Sandreas.sandberg@arm.comtemplate <class T> 6913731Sandreas.sandberg@arm.cominline bool 7013731Sandreas.sandberg@arm.comIsPowerOf2(T n) 717635SBrad.Beckmann@amd.com{ 727635SBrad.Beckmann@amd.com return n != 0 && LeastSigBit(n) == n; 737635SBrad.Beckmann@amd.com} 747635SBrad.Beckmann@amd.com 757635SBrad.Beckmann@amd.cominline int 767635SBrad.Beckmann@amd.comFloorLog2(unsigned x) 777635SBrad.Beckmann@amd.com{ 787635SBrad.Beckmann@amd.com assert(x > 0); 797635SBrad.Beckmann@amd.com 807635SBrad.Beckmann@amd.com int y = 0; 817635SBrad.Beckmann@amd.com 827635SBrad.Beckmann@amd.com if (x & 0xffff0000) { y += 16; x >>= 16; } 837635SBrad.Beckmann@amd.com if (x & 0x0000ff00) { y += 8; x >>= 8; } 847635SBrad.Beckmann@amd.com if (x & 0x000000f0) { y += 4; x >>= 4; } 857635SBrad.Beckmann@amd.com if (x & 0x0000000c) { y += 2; x >>= 2; } 867635SBrad.Beckmann@amd.com if (x & 0x00000002) { y += 1; } 877635SBrad.Beckmann@amd.com 8812564Sgabeblack@google.com return y; 897635SBrad.Beckmann@amd.com} 907635SBrad.Beckmann@amd.com 917635SBrad.Beckmann@amd.cominline int 927635SBrad.Beckmann@amd.comFloorLog2(unsigned long x) 937635SBrad.Beckmann@amd.com{ 9412564Sgabeblack@google.com assert(x > 0); 9512564Sgabeblack@google.com 967635SBrad.Beckmann@amd.com int y = 0; 977635SBrad.Beckmann@amd.com 987635SBrad.Beckmann@amd.com#if defined(__LP64__) 998436SBrad.Beckmann@amd.com if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1007635SBrad.Beckmann@amd.com#endif 10113408Snikos.nikoleris@arm.com if (x & 0xffff0000) { y += 16; x >>= 16; } 1028437SBrad.Beckmann@amd.com if (x & 0x0000ff00) { y += 8; x >>= 8; } 1038437SBrad.Beckmann@amd.com if (x & 0x000000f0) { y += 4; x >>= 4; } 1048437SBrad.Beckmann@amd.com if (x & 0x0000000c) { y += 2; x >>= 2; } 1058436SBrad.Beckmann@amd.com if (x & 0x00000002) { y += 1; } 10613731Sandreas.sandberg@arm.com 1077635SBrad.Beckmann@amd.com return y; 1087635SBrad.Beckmann@amd.com} 1099909Snilay@cs.wisc.edu 1109909Snilay@cs.wisc.eduinline int 1117635SBrad.Beckmann@amd.comFloorLog2(unsigned long long x) 1127635SBrad.Beckmann@amd.com{ 11313408Snikos.nikoleris@arm.com assert(x > 0); 1148437SBrad.Beckmann@amd.com 1158437SBrad.Beckmann@amd.com int y = 0; 1168437SBrad.Beckmann@amd.com 1178929Snilay@cs.wisc.edu if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1188929Snilay@cs.wisc.edu if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 11913731Sandreas.sandberg@arm.com if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 1207635SBrad.Beckmann@amd.com if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 1217635SBrad.Beckmann@amd.com if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 1227635SBrad.Beckmann@amd.com if (x & ULL(0x0000000000000002)) { y += 1; } 1237635SBrad.Beckmann@amd.com 1248929Snilay@cs.wisc.edu return y; 1258929Snilay@cs.wisc.edu} 1268929Snilay@cs.wisc.edu 12710519Snilay@cs.wisc.eduinline int 1287635SBrad.Beckmann@amd.comFloorLog2(int x) 1299909Snilay@cs.wisc.edu{ 1309909Snilay@cs.wisc.edu assert(x > 0); 1319909Snilay@cs.wisc.edu return FloorLog2((unsigned)x); 1329909Snilay@cs.wisc.edu} 1339793Sakash.bagdia@arm.com 1349909Snilay@cs.wisc.eduinline int 1359909Snilay@cs.wisc.eduFloorLog2(long x) 1369793Sakash.bagdia@arm.com{ 1377635SBrad.Beckmann@amd.com assert(x > 0); 1387635SBrad.Beckmann@amd.com return FloorLog2((unsigned long)x); 1397635SBrad.Beckmann@amd.com} 1407635SBrad.Beckmann@amd.com 1417635SBrad.Beckmann@amd.cominline int 14211320Ssteve.reinhardt@amd.comFloorLog2(long long x) 14310120Snilay@cs.wisc.edu{ 1447635SBrad.Beckmann@amd.com assert(x > 0); 1457635SBrad.Beckmann@amd.com return FloorLog2((unsigned long long)x); 1467635SBrad.Beckmann@amd.com} 1477635SBrad.Beckmann@amd.com 1487635SBrad.Beckmann@amd.com#if defined(__APPLE__) 14913408Snikos.nikoleris@arm.cominline int 1507635SBrad.Beckmann@amd.comFloorLog2(size_t x) 1517938SBrad.Beckmann@amd.com{ 1527938SBrad.Beckmann@amd.com assert(x > 0); 1537938SBrad.Beckmann@amd.com assert(sizeof(size_t) == 4 || sizeof(size_t) == 8); 1547938SBrad.Beckmann@amd.com 15510120Snilay@cs.wisc.edu // It's my hope that this is optimized away? 1567938SBrad.Beckmann@amd.com if (sizeof(size_t) == 4) 1577635SBrad.Beckmann@amd.com return FloorLog2((uint32_t)x); 1587635SBrad.Beckmann@amd.com else if (sizeof(size_t) == 8) 1597635SBrad.Beckmann@amd.com return FloorLog2((uint64_t)x); 1607635SBrad.Beckmann@amd.com 1618801Sgblack@eecs.umich.edu} 1627635SBrad.Beckmann@amd.com#endif 1637635SBrad.Beckmann@amd.com 1647635SBrad.Beckmann@amd.comtemplate <class T> 1657635SBrad.Beckmann@amd.cominline int 1667635SBrad.Beckmann@amd.comCeilLog2(T n) 1677635SBrad.Beckmann@amd.com{ 1687635SBrad.Beckmann@amd.com if (n == 1) 1697635SBrad.Beckmann@amd.com return 0; 1707635SBrad.Beckmann@amd.com 1719909Snilay@cs.wisc.edu return FloorLog2(n - (T)1) + 1; 1727635SBrad.Beckmann@amd.com} 17312564Sgabeblack@google.com 174template <class T> 175inline T 176FloorPow2(T n) 177{ 178 return (T)1 << FloorLog2(n); 179} 180 181template <class T> 182inline T 183CeilPow2(T n) 184{ 185 return (T)1 << CeilLog2(n); 186} 187 188template <class T> 189inline T 190DivCeil(T a, T b) 191{ 192 return (a + b - 1) / b; 193} 194 195template <class T> 196inline T 197RoundUp(T val, T align) 198{ 199 T mask = align - 1; 200 return (val + mask) & ~mask; 201} 202 203template <class T> 204inline T 205RoundDown(T val, T align) 206{ 207 T mask = align - 1; 208 return val & ~mask; 209} 210 211inline bool 212IsHex(char c) 213{ 214 return c >= '0' && c <= '9' || 215 c >= 'A' && c <= 'F' || 216 c >= 'a' && c <= 'f'; 217} 218 219inline bool 220IsOct(char c) 221{ 222 return c >= '0' && c <= '7'; 223} 224 225inline bool 226IsDec(char c) 227{ 228 return c >= '0' && c <= '9'; 229} 230 231inline int 232Hex2Int(char c) 233{ 234 if (c >= '0' && c <= '9') 235 return (c - '0'); 236 237 if (c >= 'A' && c <= 'F') 238 return (c - 'A') + 10; 239 240 if (c >= 'a' && c <= 'f') 241 return (c - 'a') + 10; 242 243 return 0; 244} 245 246#endif // __INTMATH_HH__ 247