intmath.hh revision 2665
111723Sar4jc@virginia.edu/* 211723Sar4jc@virginia.edu * Copyright (c) 2001, 2003-2005 The Regents of The University of Michigan 311723Sar4jc@virginia.edu * All rights reserved. 412808Srobert.scheffel1@tu-dresden.de * 511723Sar4jc@virginia.edu * Redistribution and use in source and binary forms, with or without 611723Sar4jc@virginia.edu * modification, are permitted provided that the following conditions are 711723Sar4jc@virginia.edu * met: redistributions of source code must retain the above copyright 811723Sar4jc@virginia.edu * notice, this list of conditions and the following disclaimer; 911723Sar4jc@virginia.edu * redistributions in binary form must reproduce the above copyright 1011723Sar4jc@virginia.edu * notice, this list of conditions and the following disclaimer in the 1111723Sar4jc@virginia.edu * documentation and/or other materials provided with the distribution; 1211723Sar4jc@virginia.edu * neither the name of the copyright holders nor the names of its 1311723Sar4jc@virginia.edu * contributors may be used to endorse or promote products derived from 1411723Sar4jc@virginia.edu * this software without specific prior written permission. 1511723Sar4jc@virginia.edu * 1611723Sar4jc@virginia.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1711723Sar4jc@virginia.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1811723Sar4jc@virginia.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1911723Sar4jc@virginia.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2011723Sar4jc@virginia.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2111723Sar4jc@virginia.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2211723Sar4jc@virginia.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2311723Sar4jc@virginia.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2411723Sar4jc@virginia.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2511723Sar4jc@virginia.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2611723Sar4jc@virginia.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2711723Sar4jc@virginia.edu * 2811723Sar4jc@virginia.edu * Authors: Nathan Binkert 2911723Sar4jc@virginia.edu */ 3011723Sar4jc@virginia.edu 3112808Srobert.scheffel1@tu-dresden.de#ifndef __INTMATH_HH__ 3211723Sar4jc@virginia.edu#define __INTMATH_HH__ 3311723Sar4jc@virginia.edu 3411723Sar4jc@virginia.edu#include <assert.h> 3512848Sar4jc@virginia.edu 3612848Sar4jc@virginia.edu#include "sim/host.hh" 3712808Srobert.scheffel1@tu-dresden.de 3811723Sar4jc@virginia.edu// Returns the prime number one less than n. 3912808Srobert.scheffel1@tu-dresden.deint prevPrime(int n); 4011723Sar4jc@virginia.edu 4111723Sar4jc@virginia.edu// Determine if a number is prime 4211723Sar4jc@virginia.edutemplate <class T> 4311723Sar4jc@virginia.eduinline bool 4412848Sar4jc@virginia.eduisPrime(T n) 4512848Sar4jc@virginia.edu{ 4611723Sar4jc@virginia.edu T i; 4711723Sar4jc@virginia.edu 4812848Sar4jc@virginia.edu if (n == 2 || n == 3) 4911723Sar4jc@virginia.edu return true; 5011723Sar4jc@virginia.edu 5111723Sar4jc@virginia.edu // Don't try every odd number to prove if it is a prime. 5211723Sar4jc@virginia.edu // Toggle between every 2nd and 4th number. 5311723Sar4jc@virginia.edu // (This is because every 6th odd number is divisible by 3.) 5411723Sar4jc@virginia.edu for (i = 5; i*i <= n; i += 6) { 5511723Sar4jc@virginia.edu if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 5612848Sar4jc@virginia.edu return false; 5712848Sar4jc@virginia.edu } 5811723Sar4jc@virginia.edu } 5912848Sar4jc@virginia.edu 6012848Sar4jc@virginia.edu return true; 6112848Sar4jc@virginia.edu} 6212848Sar4jc@virginia.edu 6312848Sar4jc@virginia.edutemplate <class T> 6413548Salec.roelke@gmail.cominline T 6513548Salec.roelke@gmail.comleastSigBit(T n) 6613548Salec.roelke@gmail.com{ 6713548Salec.roelke@gmail.com return n & ~(n - 1); 6813548Salec.roelke@gmail.com} 6913548Salec.roelke@gmail.com 7013548Salec.roelke@gmail.comtemplate <class T> 7113548Salec.roelke@gmail.cominline bool 7213548Salec.roelke@gmail.comisPowerOf2(T n) 7313548Salec.roelke@gmail.com{ 7413548Salec.roelke@gmail.com return n != 0 && leastSigBit(n) == n; 7513548Salec.roelke@gmail.com} 7613548Salec.roelke@gmail.com 7713548Salec.roelke@gmail.cominline int 7813548Salec.roelke@gmail.comfloorLog2(unsigned x) 7913548Salec.roelke@gmail.com{ 8013548Salec.roelke@gmail.com assert(x > 0); 8113548Salec.roelke@gmail.com 8212848Sar4jc@virginia.edu int y = 0; 8312848Sar4jc@virginia.edu 8412848Sar4jc@virginia.edu if (x & 0xffff0000) { y += 16; x >>= 16; } 8512849Sar4jc@virginia.edu if (x & 0x0000ff00) { y += 8; x >>= 8; } 8612848Sar4jc@virginia.edu if (x & 0x000000f0) { y += 4; x >>= 4; } 8712848Sar4jc@virginia.edu if (x & 0x0000000c) { y += 2; x >>= 2; } 8812848Sar4jc@virginia.edu if (x & 0x00000002) { y += 1; } 8912848Sar4jc@virginia.edu 9012848Sar4jc@virginia.edu return y; 9112849Sar4jc@virginia.edu} 9212848Sar4jc@virginia.edu 9312848Sar4jc@virginia.eduinline int 9412848Sar4jc@virginia.edufloorLog2(unsigned long x) 9512848Sar4jc@virginia.edu{ 9612848Sar4jc@virginia.edu assert(x > 0); 9712848Sar4jc@virginia.edu 9812848Sar4jc@virginia.edu int y = 0; 9912848Sar4jc@virginia.edu 10012849Sar4jc@virginia.edu#if defined(__LP64__) 10112848Sar4jc@virginia.edu if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 10212848Sar4jc@virginia.edu#endif 10312848Sar4jc@virginia.edu if (x & 0xffff0000) { y += 16; x >>= 16; } 10412848Sar4jc@virginia.edu if (x & 0x0000ff00) { y += 8; x >>= 8; } 10512848Sar4jc@virginia.edu if (x & 0x000000f0) { y += 4; x >>= 4; } 10612848Sar4jc@virginia.edu if (x & 0x0000000c) { y += 2; x >>= 2; } 10712848Sar4jc@virginia.edu if (x & 0x00000002) { y += 1; } 10812848Sar4jc@virginia.edu 10912848Sar4jc@virginia.edu return y; 11012849Sar4jc@virginia.edu} 11112848Sar4jc@virginia.edu 11212848Sar4jc@virginia.eduinline int 11312848Sar4jc@virginia.edufloorLog2(unsigned long long x) 11412848Sar4jc@virginia.edu{ 11512848Sar4jc@virginia.edu assert(x > 0); 11612848Sar4jc@virginia.edu 11712848Sar4jc@virginia.edu int y = 0; 11812848Sar4jc@virginia.edu 11912848Sar4jc@virginia.edu if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; } 12012848Sar4jc@virginia.edu if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; } 12112848Sar4jc@virginia.edu if (x & ULL(0x000000000000ff00)) { y += 8; x >>= 8; } 12212848Sar4jc@virginia.edu if (x & ULL(0x00000000000000f0)) { y += 4; x >>= 4; } 12313612Sgabeblack@google.com if (x & ULL(0x000000000000000c)) { y += 2; x >>= 2; } 12412848Sar4jc@virginia.edu if (x & ULL(0x0000000000000002)) { y += 1; } 12512849Sar4jc@virginia.edu 12612848Sar4jc@virginia.edu return y; 12712848Sar4jc@virginia.edu} 12812848Sar4jc@virginia.edu 12912848Sar4jc@virginia.eduinline int 13013548Salec.roelke@gmail.comfloorLog2(int x) 13113548Salec.roelke@gmail.com{ 13213548Salec.roelke@gmail.com assert(x > 0); 13313548Salec.roelke@gmail.com return floorLog2((unsigned)x); 13411723Sar4jc@virginia.edu} 13512848Sar4jc@virginia.edu 13611723Sar4jc@virginia.eduinline int 13711723Sar4jc@virginia.edufloorLog2(long x) 13812848Sar4jc@virginia.edu{ 13911723Sar4jc@virginia.edu assert(x > 0); 14011723Sar4jc@virginia.edu return floorLog2((unsigned long)x); 14112808Srobert.scheffel1@tu-dresden.de} 14212808Srobert.scheffel1@tu-dresden.de 14313547Sar4jc@virginia.eduinline int 14413547Sar4jc@virginia.edufloorLog2(long long x) 14513547Sar4jc@virginia.edu{ 14613547Sar4jc@virginia.edu assert(x > 0); 14713547Sar4jc@virginia.edu return floorLog2((unsigned long long)x); 14813547Sar4jc@virginia.edu} 14913547Sar4jc@virginia.edu 15012808Srobert.scheffel1@tu-dresden.detemplate <class T> 15112808Srobert.scheffel1@tu-dresden.deinline int 15212808Srobert.scheffel1@tu-dresden.deceilLog2(T n) 15312808Srobert.scheffel1@tu-dresden.de{ 15412808Srobert.scheffel1@tu-dresden.de if (n == 1) 15511723Sar4jc@virginia.edu return 0; 15612848Sar4jc@virginia.edu 15711723Sar4jc@virginia.edu return floorLog2(n - (T)1) + 1; 15811723Sar4jc@virginia.edu} 15911723Sar4jc@virginia.edu 16011723Sar4jc@virginia.edutemplate <class T> 16111723Sar4jc@virginia.eduinline T 16211723Sar4jc@virginia.edufloorPow2(T n) 16312848Sar4jc@virginia.edu{ 16412136Sar4jc@virginia.edu return (T)1 << floorLog2(n); 16512136Sar4jc@virginia.edu} 16612136Sar4jc@virginia.edu 16712136Sar4jc@virginia.edutemplate <class T> 16812136Sar4jc@virginia.eduinline T 16912136Sar4jc@virginia.educeilPow2(T n) 17012848Sar4jc@virginia.edu{ 17111723Sar4jc@virginia.edu return (T)1 << ceilLog2(n); 17211723Sar4jc@virginia.edu} 17311723Sar4jc@virginia.edu 17411723Sar4jc@virginia.edutemplate <class T> 17511723Sar4jc@virginia.eduinline T 17611723Sar4jc@virginia.edudivCeil(T a, T b) 17711723Sar4jc@virginia.edu{ 17812848Sar4jc@virginia.edu return (a + b - 1) / b; 17911725Sar4jc@virginia.edu} 18011725Sar4jc@virginia.edu 18111725Sar4jc@virginia.edutemplate <class T> 18211725Sar4jc@virginia.eduinline T 18311725Sar4jc@virginia.eduroundUp(T val, int align) 18411725Sar4jc@virginia.edu{ 18512848Sar4jc@virginia.edu T mask = (T)align - 1; 18611723Sar4jc@virginia.edu return (val + mask) & ~mask; 18711723Sar4jc@virginia.edu} 18811723Sar4jc@virginia.edu 18911723Sar4jc@virginia.edutemplate <class T> 19011723Sar4jc@virginia.eduinline T 19112848Sar4jc@virginia.eduroundDown(T val, int align) 19211723Sar4jc@virginia.edu{ 19311877Sbrandon.potter@amd.com T mask = (T)align - 1; 19411877Sbrandon.potter@amd.com return val & ~mask; 19511723Sar4jc@virginia.edu} 19612848Sar4jc@virginia.edu 19713612Sgabeblack@google.cominline bool 198isHex(char c) 199{ 200 return c >= '0' && c <= '9' || 201 c >= 'A' && c <= 'F' || 202 c >= 'a' && c <= 'f'; 203} 204 205inline bool 206isOct(char c) 207{ 208 return c >= '0' && c <= '7'; 209} 210 211inline bool 212isDec(char c) 213{ 214 return c >= '0' && c <= '9'; 215} 216 217inline int 218hex2Int(char c) 219{ 220 if (c >= '0' && c <= '9') 221 return (c - '0'); 222 223 if (c >= 'A' && c <= 'F') 224 return (c - 'A') + 10; 225 226 if (c >= 'a' && c <= 'f') 227 return (c - 'a') + 10; 228 229 return 0; 230} 231 232#endif // __INTMATH_HH__ 233