intmath.hh revision 100
13569Sgblack@eecs.umich.edu/* 23569Sgblack@eecs.umich.edu * Copyright (c) 2003 The Regents of The University of Michigan 33569Sgblack@eecs.umich.edu * All rights reserved. 43569Sgblack@eecs.umich.edu * 53569Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 63569Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 73569Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 83569Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 93569Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 103569Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 113569Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 123569Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 133569Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 143569Sgblack@eecs.umich.edu * this software without specific prior written permission. 153569Sgblack@eecs.umich.edu * 163569Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 173569Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 183569Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 193569Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 203569Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 213569Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 223569Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 233569Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 243569Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 253569Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 263569Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 273569Sgblack@eecs.umich.edu */ 283804Ssaidi@eecs.umich.edu 293569Sgblack@eecs.umich.edu#ifndef __INTMATH_HH__ 303569Sgblack@eecs.umich.edu#define __INTMATH_HH__ 313918Ssaidi@eecs.umich.edu 323918Ssaidi@eecs.umich.edu#include <assert.h> 333804Ssaidi@eecs.umich.edu 343811Ssaidi@eecs.umich.edu#include "sim/host.hh" 353569Sgblack@eecs.umich.edu 363824Ssaidi@eecs.umich.edu// Returns the prime number one less than n. 373811Ssaidi@eecs.umich.eduint PrevPrime(int n); 383811Ssaidi@eecs.umich.edu 393823Ssaidi@eecs.umich.edu// Determine if a number is prime 403823Ssaidi@eecs.umich.edutemplate <class T> 413823Ssaidi@eecs.umich.eduinline bool 424762Snate@binkert.orgIsPrime(T n) 434762Snate@binkert.org{ 444103Ssaidi@eecs.umich.edu T i; 453569Sgblack@eecs.umich.edu 463804Ssaidi@eecs.umich.edu if (n == 2 || n == 3) 473804Ssaidi@eecs.umich.edu return true; 484088Sbinkertn@umich.edu 493569Sgblack@eecs.umich.edu // Don't try every odd number to prove if it is a prime. 503804Ssaidi@eecs.umich.edu // Toggle between every 2nd and 4th number. 513881Ssaidi@eecs.umich.edu // (This is because every 6th odd number is divisible by 3.) 523881Ssaidi@eecs.umich.edu for (i = 5; i*i <= n; i += 6) { 533804Ssaidi@eecs.umich.edu if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 543804Ssaidi@eecs.umich.edu return false; 553804Ssaidi@eecs.umich.edu } 563804Ssaidi@eecs.umich.edu } 573569Sgblack@eecs.umich.edu 583804Ssaidi@eecs.umich.edu return true; 593918Ssaidi@eecs.umich.edu} 603881Ssaidi@eecs.umich.edu 613881Ssaidi@eecs.umich.edutemplate <class T> 623881Ssaidi@eecs.umich.eduinline T 634990Sgblack@eecs.umich.eduLeastSigBit(T n) 644990Sgblack@eecs.umich.edu{ 654990Sgblack@eecs.umich.edu return n & ~(n - 1); 664990Sgblack@eecs.umich.edu} 674990Sgblack@eecs.umich.edu 684990Sgblack@eecs.umich.edutemplate <class T> 694990Sgblack@eecs.umich.eduinline bool 704990Sgblack@eecs.umich.eduIsPowerOf2(T n) 714990Sgblack@eecs.umich.edu{ 723804Ssaidi@eecs.umich.edu return n != 0 && LeastSigBit(n) == n; 733569Sgblack@eecs.umich.edu} 743804Ssaidi@eecs.umich.edu 753804Ssaidi@eecs.umich.eduinline int 763804Ssaidi@eecs.umich.eduFloorLog2(uint32_t x) 773804Ssaidi@eecs.umich.edu{ 783881Ssaidi@eecs.umich.edu assert(x > 0); 793804Ssaidi@eecs.umich.edu 803804Ssaidi@eecs.umich.edu int y = 0; 813804Ssaidi@eecs.umich.edu 823804Ssaidi@eecs.umich.edu if (x & 0xffff0000) { y += 16; x >>= 16; } 833804Ssaidi@eecs.umich.edu if (x & 0x0000ff00) { y += 8; x >>= 8; } 843804Ssaidi@eecs.umich.edu if (x & 0x000000f0) { y += 4; x >>= 4; } 853804Ssaidi@eecs.umich.edu if (x & 0x0000000c) { y += 2; x >>= 2; } 863569Sgblack@eecs.umich.edu if (x & 0x00000002) { y += 1; } 873569Sgblack@eecs.umich.edu 883804Ssaidi@eecs.umich.edu return y; 893804Ssaidi@eecs.umich.edu} 903826Ssaidi@eecs.umich.edu 913804Ssaidi@eecs.umich.eduinline int 923569Sgblack@eecs.umich.eduFloorLog2(uint64_t x) 933569Sgblack@eecs.umich.edu{ 943804Ssaidi@eecs.umich.edu assert(x > 0); 953826Ssaidi@eecs.umich.edu 963907Ssaidi@eecs.umich.edu int y = 0; 973826Ssaidi@eecs.umich.edu 983811Ssaidi@eecs.umich.edu if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 993836Ssaidi@eecs.umich.edu if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 1003915Ssaidi@eecs.umich.edu if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 1013907Ssaidi@eecs.umich.edu if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 1023881Ssaidi@eecs.umich.edu if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 1033881Ssaidi@eecs.umich.edu if (x & ULL(0x0000000000000002)) { y += 1; } 1043881Ssaidi@eecs.umich.edu 1053881Ssaidi@eecs.umich.edu return y; 1063907Ssaidi@eecs.umich.edu} 1073881Ssaidi@eecs.umich.edu 1083881Ssaidi@eecs.umich.eduinline int 1093881Ssaidi@eecs.umich.eduFloorLog2(int32_t x) 1103881Ssaidi@eecs.umich.edu{ 1113881Ssaidi@eecs.umich.edu assert(x > 0); 1123907Ssaidi@eecs.umich.edu return FloorLog2(x); 1133907Ssaidi@eecs.umich.edu} 1143907Ssaidi@eecs.umich.edu 1153907Ssaidi@eecs.umich.eduinline int 1163907Ssaidi@eecs.umich.eduFloorLog2(int64_t x) 1173907Ssaidi@eecs.umich.edu{ 1183907Ssaidi@eecs.umich.edu assert(x > 0); 1193907Ssaidi@eecs.umich.edu return FloorLog2(x); 1203907Ssaidi@eecs.umich.edu} 1213907Ssaidi@eecs.umich.edu 1223907Ssaidi@eecs.umich.edutemplate <class T> 1233907Ssaidi@eecs.umich.eduinline int 1243907Ssaidi@eecs.umich.eduCeilLog2(T n) 1253907Ssaidi@eecs.umich.edu{ 1263907Ssaidi@eecs.umich.edu if (n == 1) 1273907Ssaidi@eecs.umich.edu return 0; 1283907Ssaidi@eecs.umich.edu 1293907Ssaidi@eecs.umich.edu return FloorLog2(n - (T)1) + 1; 1303907Ssaidi@eecs.umich.edu} 1313907Ssaidi@eecs.umich.edu 1323907Ssaidi@eecs.umich.edutemplate <class T> 1333907Ssaidi@eecs.umich.eduinline T 1343907Ssaidi@eecs.umich.eduFloorPow2(T n) 1353881Ssaidi@eecs.umich.edu{ 1363881Ssaidi@eecs.umich.edu return (T)1 << FloorLog2(n); 1373881Ssaidi@eecs.umich.edu} 1383881Ssaidi@eecs.umich.edu 1393881Ssaidi@eecs.umich.edutemplate <class T> 1403881Ssaidi@eecs.umich.eduinline T 1413881Ssaidi@eecs.umich.eduCeilPow2(T n) 1423881Ssaidi@eecs.umich.edu{ 1433881Ssaidi@eecs.umich.edu return (T)1 << CeilLog2(n); 1443881Ssaidi@eecs.umich.edu} 1453881Ssaidi@eecs.umich.edu 1463881Ssaidi@eecs.umich.edutemplate <class T> 1473907Ssaidi@eecs.umich.eduinline T 1483811Ssaidi@eecs.umich.eduDivCeil(T a, T b) 1493826Ssaidi@eecs.umich.edu{ 1503826Ssaidi@eecs.umich.edu return (a + b - 1) / b; 1513826Ssaidi@eecs.umich.edu} 1523826Ssaidi@eecs.umich.edu 1533881Ssaidi@eecs.umich.edutemplate <class T> 1543881Ssaidi@eecs.umich.eduinline T 1553881Ssaidi@eecs.umich.eduRoundUp(T val, T align) 1563881Ssaidi@eecs.umich.edu{ 1573881Ssaidi@eecs.umich.edu T mask = align - 1; 1583881Ssaidi@eecs.umich.edu return (val + mask) & ~mask; 1593881Ssaidi@eecs.umich.edu} 1603881Ssaidi@eecs.umich.edu 1613881Ssaidi@eecs.umich.edutemplate <class T> 1623881Ssaidi@eecs.umich.eduinline T 1633881Ssaidi@eecs.umich.eduRoundDown(T val, T align) 1643881Ssaidi@eecs.umich.edu{ 1653881Ssaidi@eecs.umich.edu T mask = align - 1; 1663881Ssaidi@eecs.umich.edu return val & ~mask; 1673881Ssaidi@eecs.umich.edu} 1683826Ssaidi@eecs.umich.edu 1693826Ssaidi@eecs.umich.eduinline bool 1703826Ssaidi@eecs.umich.eduIsHex(char c) 1713826Ssaidi@eecs.umich.edu{ 1723826Ssaidi@eecs.umich.edu return c >= '0' && c <= '9' || 1733881Ssaidi@eecs.umich.edu c >= 'A' && c <= 'F' || 1743569Sgblack@eecs.umich.edu c >= 'a' && c <= 'f'; 1753569Sgblack@eecs.umich.edu} 1763881Ssaidi@eecs.umich.edu 1773804Ssaidi@eecs.umich.eduinline bool 1783881Ssaidi@eecs.umich.eduIsOct(char c) 1793826Ssaidi@eecs.umich.edu{ 1803881Ssaidi@eecs.umich.edu return c >= '0' && c <= '7'; 1813881Ssaidi@eecs.umich.edu} 1823881Ssaidi@eecs.umich.edu 1833907Ssaidi@eecs.umich.eduinline bool 1843907Ssaidi@eecs.umich.eduIsDec(char c) 1853929Ssaidi@eecs.umich.edu{ 1863929Ssaidi@eecs.umich.edu return c >= '0' && c <= '9'; 1873907Ssaidi@eecs.umich.edu} 1883907Ssaidi@eecs.umich.edu 1893804Ssaidi@eecs.umich.eduinline int 1903804Ssaidi@eecs.umich.eduHex2Int(char c) 1913881Ssaidi@eecs.umich.edu{ 1923804Ssaidi@eecs.umich.edu if (c >= '0' && c <= '9') 1933804Ssaidi@eecs.umich.edu return (c - '0'); 1943804Ssaidi@eecs.umich.edu 1953804Ssaidi@eecs.umich.edu if(c >= 'A' && c <= 'F') 1963804Ssaidi@eecs.umich.edu return (c - 'A') + 10; 1973804Ssaidi@eecs.umich.edu 1983804Ssaidi@eecs.umich.edu if (c >= 'a' && c <= 'f') 1993569Sgblack@eecs.umich.edu return (c - 'a') + 10; 2003569Sgblack@eecs.umich.edu 2013569Sgblack@eecs.umich.edu return 0; 2023863Ssaidi@eecs.umich.edu} 2033863Ssaidi@eecs.umich.edu 2043804Ssaidi@eecs.umich.edu#endif // __INTMATH_HH__ 2053804Ssaidi@eecs.umich.edu