intmath.hh revision 2020
19793Sakash.bagdia@arm.com/* 29518SAndreas.Sandberg@ARM.com * Copyright (c) 2001, 2003-2005 The Regents of The University of Michigan 311320Ssteve.reinhardt@amd.com * All rights reserved. 49518SAndreas.Sandberg@ARM.com * 59518SAndreas.Sandberg@ARM.com * Redistribution and use in source and binary forms, with or without 69518SAndreas.Sandberg@ARM.com * modification, are permitted provided that the following conditions are 79518SAndreas.Sandberg@ARM.com * met: redistributions of source code must retain the above copyright 89518SAndreas.Sandberg@ARM.com * notice, this list of conditions and the following disclaimer; 99518SAndreas.Sandberg@ARM.com * redistributions in binary form must reproduce the above copyright 109518SAndreas.Sandberg@ARM.com * notice, this list of conditions and the following disclaimer in the 119518SAndreas.Sandberg@ARM.com * documentation and/or other materials provided with the distribution; 129518SAndreas.Sandberg@ARM.com * neither the name of the copyright holders nor the names of its 135347Ssaidi@eecs.umich.edu * contributors may be used to endorse or promote products derived from 147534Ssteve.reinhardt@amd.com * this software without specific prior written permission. 153395Shsul@eecs.umich.edu * 163395Shsul@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 173395Shsul@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 183395Shsul@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 193395Shsul@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 203395Shsul@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 213395Shsul@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 223395Shsul@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233395Shsul@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243395Shsul@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253395Shsul@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 263395Shsul@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273395Shsul@eecs.umich.edu */ 283395Shsul@eecs.umich.edu 293395Shsul@eecs.umich.edu#ifndef __INTMATH_HH__ 303395Shsul@eecs.umich.edu#define __INTMATH_HH__ 313395Shsul@eecs.umich.edu 323395Shsul@eecs.umich.edu#include <assert.h> 333395Shsul@eecs.umich.edu 343395Shsul@eecs.umich.edu#include "sim/host.hh" 353395Shsul@eecs.umich.edu 363395Shsul@eecs.umich.edu// Returns the prime number one less than n. 373395Shsul@eecs.umich.eduint prevPrime(int n); 383395Shsul@eecs.umich.edu 393395Shsul@eecs.umich.edu// Determine if a number is prime 403395Shsul@eecs.umich.edutemplate <class T> 413395Shsul@eecs.umich.eduinline bool 4212564Sgabeblack@google.comisPrime(T n) 4312564Sgabeblack@google.com{ 449457Svilanova@ac.upc.edu T i; 453395Shsul@eecs.umich.edu 463509Shsul@eecs.umich.edu if (n == 2 || n == 3) 476654Snate@binkert.org return true; 4811688Sandreas.hansson@arm.com 4911688Sandreas.hansson@arm.com // Don't try every odd number to prove if it is a prime. 509520SAndreas.Sandberg@ARM.com // Toggle between every 2nd and 4th number. 513395Shsul@eecs.umich.edu // (This is because every 6th odd number is divisible by 3.) 526654Snate@binkert.org for (i = 5; i*i <= n; i += 6) { 533395Shsul@eecs.umich.edu if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 546654Snate@binkert.org return false; 556654Snate@binkert.org } 566654Snate@binkert.org } 573395Shsul@eecs.umich.edu 589139Snilay@cs.wisc.edu return true; 599520SAndreas.Sandberg@ARM.com} 609520SAndreas.Sandberg@ARM.com 619520SAndreas.Sandberg@ARM.comtemplate <class T> 629139Snilay@cs.wisc.eduinline T 633481Shsul@eecs.umich.eduleastSigBit(T n) 649139Snilay@cs.wisc.edu{ 653481Shsul@eecs.umich.edu return n & ~(n - 1); 669139Snilay@cs.wisc.edu} 679139Snilay@cs.wisc.edu 689139Snilay@cs.wisc.edutemplate <class T> 699139Snilay@cs.wisc.eduinline bool 709139Snilay@cs.wisc.eduisPowerOf2(T n) 719139Snilay@cs.wisc.edu{ 729139Snilay@cs.wisc.edu return n != 0 && leastSigBit(n) == n; 739139Snilay@cs.wisc.edu} 743481Shsul@eecs.umich.edu 759518SAndreas.Sandberg@ARM.cominline int 769518SAndreas.Sandberg@ARM.comfloorLog2(unsigned x) 779518SAndreas.Sandberg@ARM.com{ 783481Shsul@eecs.umich.edu assert(x > 0); 799139Snilay@cs.wisc.edu 809139Snilay@cs.wisc.edu int y = 0; 813481Shsul@eecs.umich.edu 829139Snilay@cs.wisc.edu if (x & 0xffff0000) { y += 16; x >>= 16; } 839139Snilay@cs.wisc.edu if (x & 0x0000ff00) { y += 8; x >>= 8; } 849139Snilay@cs.wisc.edu if (x & 0x000000f0) { y += 4; x >>= 4; } 859139Snilay@cs.wisc.edu if (x & 0x0000000c) { y += 2; x >>= 2; } 869139Snilay@cs.wisc.edu if (x & 0x00000002) { y += 1; } 873481Shsul@eecs.umich.edu 8812395Sswapnilster@gmail.com return y; 8912395Sswapnilster@gmail.com} 9012395Sswapnilster@gmail.com 9112395Sswapnilster@gmail.cominline int 9212395Sswapnilster@gmail.comfloorLog2(unsigned long x) 933481Shsul@eecs.umich.edu{ 943481Shsul@eecs.umich.edu assert(x > 0); 959665Sandreas.hansson@arm.com 969665Sandreas.hansson@arm.com int y = 0; 979665Sandreas.hansson@arm.com 989665Sandreas.hansson@arm.com#if defined(__LP64__) 999665Sandreas.hansson@arm.com if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1008919Snilay@cs.wisc.edu#endif 1018919Snilay@cs.wisc.edu if (x & 0xffff0000) { y += 16; x >>= 16; } 1028919Snilay@cs.wisc.edu if (x & 0x0000ff00) { y += 8; x >>= 8; } 10310159Sgedare@rtems.org if (x & 0x000000f0) { y += 4; x >>= 4; } 10410159Sgedare@rtems.org if (x & 0x0000000c) { y += 2; x >>= 2; } 1058919Snilay@cs.wisc.edu if (x & 0x00000002) { y += 1; } 1068919Snilay@cs.wisc.edu 1078919Snilay@cs.wisc.edu return y; 1088919Snilay@cs.wisc.edu} 1098919Snilay@cs.wisc.edu 1108919Snilay@cs.wisc.eduinline int 1118919Snilay@cs.wisc.edufloorLog2(unsigned long long x) 1128919Snilay@cs.wisc.edu{ 1138919Snilay@cs.wisc.edu assert(x > 0); 1148919Snilay@cs.wisc.edu 1158919Snilay@cs.wisc.edu int y = 0; 1168919Snilay@cs.wisc.edu 1173481Shsul@eecs.umich.edu if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 1189816Sjthestness@gmail.com if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 1199140Snilay@cs.wisc.edu if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 1209140Snilay@cs.wisc.edu if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 1219140Snilay@cs.wisc.edu if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 1229140Snilay@cs.wisc.edu if (x & ULL(0x0000000000000002)) { y += 1; } 1239140Snilay@cs.wisc.edu 1249140Snilay@cs.wisc.edu return y; 1259140Snilay@cs.wisc.edu} 1269140Snilay@cs.wisc.edu 1279140Snilay@cs.wisc.eduinline int 1289140Snilay@cs.wisc.edufloorLog2(int x) 1299140Snilay@cs.wisc.edu{ 1309140Snilay@cs.wisc.edu assert(x > 0); 1319140Snilay@cs.wisc.edu return floorLog2((unsigned)x); 1329140Snilay@cs.wisc.edu} 1339140Snilay@cs.wisc.edu 1349140Snilay@cs.wisc.eduinline int 1359140Snilay@cs.wisc.edufloorLog2(long x) 1369140Snilay@cs.wisc.edu{ 1379140Snilay@cs.wisc.edu assert(x > 0); 1389867Sjthestness@gmail.com return floorLog2((unsigned long)x); 1399140Snilay@cs.wisc.edu} 1409140Snilay@cs.wisc.edu 1419140Snilay@cs.wisc.eduinline int 1429140Snilay@cs.wisc.edufloorLog2(long long x) 1439140Snilay@cs.wisc.edu{ 1449140Snilay@cs.wisc.edu assert(x > 0); 1459140Snilay@cs.wisc.edu return floorLog2((unsigned long long)x); 1469140Snilay@cs.wisc.edu} 1479140Snilay@cs.wisc.edu 1489140Snilay@cs.wisc.edu#if defined(__APPLE__) 1499140Snilay@cs.wisc.eduinline int 15010608Sdam.sunwoo@arm.comfloorLog2(size_t x) 15110608Sdam.sunwoo@arm.com{ 15210608Sdam.sunwoo@arm.com assert(x > 0); 15310608Sdam.sunwoo@arm.com assert(sizeof(size_t) == 4 || sizeof(size_t) == 8); 15410608Sdam.sunwoo@arm.com 15510608Sdam.sunwoo@arm.com // It's my hope that this is optimized away? 15610608Sdam.sunwoo@arm.com if (sizeof(size_t) == 4) 15710608Sdam.sunwoo@arm.com return floorLog2((uint32_t)x); 15810608Sdam.sunwoo@arm.com else if (sizeof(size_t) == 8) 15910608Sdam.sunwoo@arm.com return floorLog2((uint64_t)x); 16010608Sdam.sunwoo@arm.com 16110608Sdam.sunwoo@arm.com} 16210608Sdam.sunwoo@arm.com#endif 16310608Sdam.sunwoo@arm.com 16410608Sdam.sunwoo@arm.comtemplate <class T> 16510608Sdam.sunwoo@arm.cominline int 16610608Sdam.sunwoo@arm.comceilLog2(T n) 16710608Sdam.sunwoo@arm.com{ 16810608Sdam.sunwoo@arm.com if (n == 1) 16910608Sdam.sunwoo@arm.com return 0; 17010608Sdam.sunwoo@arm.com 17110608Sdam.sunwoo@arm.com return floorLog2(n - (T)1) + 1; 17210608Sdam.sunwoo@arm.com} 17310608Sdam.sunwoo@arm.com 17410608Sdam.sunwoo@arm.comtemplate <class T> 17512564Sgabeblack@google.cominline T 17610608Sdam.sunwoo@arm.comfloorPow2(T n) 17710608Sdam.sunwoo@arm.com{ 17810608Sdam.sunwoo@arm.com return (T)1 << floorLog2(n); 17910608Sdam.sunwoo@arm.com} 18010608Sdam.sunwoo@arm.com 18110608Sdam.sunwoo@arm.comtemplate <class T> 18210608Sdam.sunwoo@arm.cominline T 18312564Sgabeblack@google.comceilPow2(T n) 18412564Sgabeblack@google.com{ 18512564Sgabeblack@google.com return (T)1 << ceilLog2(n); 18610608Sdam.sunwoo@arm.com} 1879140Snilay@cs.wisc.edu 1889140Snilay@cs.wisc.edutemplate <class T> 18910608Sdam.sunwoo@arm.cominline T 1909140Snilay@cs.wisc.edudivCeil(T a, T b) 1919140Snilay@cs.wisc.edu{ 1929140Snilay@cs.wisc.edu return (a + b - 1) / b; 1939140Snilay@cs.wisc.edu} 1949140Snilay@cs.wisc.edu 1959140Snilay@cs.wisc.edutemplate <class T> 1969140Snilay@cs.wisc.eduinline T 1979140Snilay@cs.wisc.eduroundUp(T val, T align) 1989140Snilay@cs.wisc.edu{ 1999140Snilay@cs.wisc.edu T mask = align - 1; 2009140Snilay@cs.wisc.edu return (val + mask) & ~mask; 2019140Snilay@cs.wisc.edu} 2029816Sjthestness@gmail.com 2039140Snilay@cs.wisc.edutemplate <class T> 2049140Snilay@cs.wisc.eduinline T 2059816Sjthestness@gmail.comroundDown(T val, T align) 2069140Snilay@cs.wisc.edu{ 2079215Sandreas.hansson@arm.com T mask = align - 1; 2089140Snilay@cs.wisc.edu return val & ~mask; 2099140Snilay@cs.wisc.edu} 2109140Snilay@cs.wisc.edu 2119140Snilay@cs.wisc.eduinline bool 2129140Snilay@cs.wisc.eduisHex(char c) 2139140Snilay@cs.wisc.edu{ 2149140Snilay@cs.wisc.edu return c >= '0' && c <= '9' || 21512564Sgabeblack@google.com c >= 'A' && c <= 'F' || 2169140Snilay@cs.wisc.edu c >= 'a' && c <= 'f'; 2179140Snilay@cs.wisc.edu} 21812564Sgabeblack@google.com 2199140Snilay@cs.wisc.eduinline bool 2209140Snilay@cs.wisc.eduisOct(char c) 2219140Snilay@cs.wisc.edu{ 2229140Snilay@cs.wisc.edu return c >= '0' && c <= '7'; 2239140Snilay@cs.wisc.edu} 2249140Snilay@cs.wisc.edu 2259140Snilay@cs.wisc.eduinline bool 2269140Snilay@cs.wisc.eduisDec(char c) 2279140Snilay@cs.wisc.edu{ 22812564Sgabeblack@google.com return c >= '0' && c <= '9'; 2299140Snilay@cs.wisc.edu} 2309140Snilay@cs.wisc.edu 2319140Snilay@cs.wisc.eduinline int 2329140Snilay@cs.wisc.eduhex2Int(char c) 2339140Snilay@cs.wisc.edu{ 2349156Sandreas.hansson@arm.com if (c >= '0' && c <= '9') 2359140Snilay@cs.wisc.edu return (c - '0'); 2369634Sjthestness@gmail.com 2379140Snilay@cs.wisc.edu if (c >= 'A' && c <= 'F') 2389140Snilay@cs.wisc.edu return (c - 'A') + 10; 2399140Snilay@cs.wisc.edu 2409140Snilay@cs.wisc.edu if (c >= 'a' && c <= 'f') 2419140Snilay@cs.wisc.edu return (c - 'a') + 10; 2429140Snilay@cs.wisc.edu 2439140Snilay@cs.wisc.edu return 0; 2449140Snilay@cs.wisc.edu} 2459140Snilay@cs.wisc.edu 2469140Snilay@cs.wisc.edu#endif // __INTMATH_HH__ 2479140Snilay@cs.wisc.edu