intmath.hh revision 1642
12SN/A/*
21762SN/A * Copyright (c) 2001, 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
292665Ssaidi@eecs.umich.edu#ifndef __INTMATH_HH__
302SN/A#define __INTMATH_HH__
312SN/A
321388SN/A#include <assert.h>
332SN/A
342SN/A#include "sim/host.hh"
352SN/A
361191SN/A// Returns the prime number one less than n.
371191SN/Aint PrevPrime(int n);
381191SN/A
391388SN/A// Determine if a number is prime
405529Snate@binkert.orgtemplate <class T>
411717SN/Ainline bool
422651Ssaidi@eecs.umich.eduIsPrime(T n)
432680Sktlim@umich.edu{
441977SN/A    T i;
455529Snate@binkert.org
463144Shsul@eecs.umich.edu    if (n == 2 || n == 3)
472190SN/A        return true;
4856SN/A
492190SN/A    // Don't try every odd number to prove if it is a prime.
502SN/A    // Toggle between every 2nd and 4th number.
512359SN/A    // (This is because every 6th odd number is divisible by 3.)
522359SN/A    for (i = 5; i*i <= n; i += 6) {
532359SN/A        if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) {
542SN/A            return false;
552SN/A        }
562SN/A    }
572SN/A
582SN/A    return true;
592SN/A}
602SN/A
612SN/Atemplate <class T>
622SN/Ainline T
633126Sktlim@umich.eduLeastSigBit(T n)
643126Sktlim@umich.edu{
654075Sbinkertn@umich.edu    return n & ~(n - 1);
663126Sktlim@umich.edu}
673126Sktlim@umich.edu
683126Sktlim@umich.edutemplate <class T>
693126Sktlim@umich.eduinline bool
703126Sktlim@umich.eduIsPowerOf2(T n)
713126Sktlim@umich.edu{
722356SN/A    return n != 0 && LeastSigBit(n) == n;
732356SN/A}
742356SN/A
752367SN/Ainline int
762356SN/AFloorLog2(unsigned x)
775100Ssaidi@eecs.umich.edu{
782367SN/A    assert(x > 0);
792356SN/A
802356SN/A    int y = 0;
812356SN/A
822367SN/A    if (x & 0xffff0000) { y += 16; x >>= 16; }
832367SN/A    if (x & 0x0000ff00) { y +=  8; x >>=  8; }
842367SN/A    if (x & 0x000000f0) { y +=  4; x >>=  4; }
852367SN/A    if (x & 0x0000000c) { y +=  2; x >>=  2; }
862356SN/A    if (x & 0x00000002) { y +=  1; }
872356SN/A
882356SN/A    return y;
892356SN/A}
902356SN/A
915336Shines@cs.fsu.eduinline int
922356SN/AFloorLog2(unsigned long x)
934873Sstever@eecs.umich.edu{
942356SN/A    assert(x > 0);
952356SN/A
961858SN/A    int y = 0;
971400SN/A
985529Snate@binkert.org#if defined(__LP64__)
995529Snate@binkert.org    if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; }
1003661Srdreslin@umich.edu#endif
1012SN/A    if (x & 0xffff0000) { y += 16; x >>= 16; }
1021400SN/A    if (x & 0x0000ff00) { y +=  8; x >>=  8; }
1035529Snate@binkert.org    if (x & 0x000000f0) { y +=  4; x >>=  4; }
1045529Snate@binkert.org    if (x & 0x0000000c) { y +=  2; x >>=  2; }
1053661Srdreslin@umich.edu    if (x & 0x00000002) { y +=  1; }
1062SN/A
1072SN/A    return y;
1082359SN/A}
1091062SN/A
1102SN/Ainline int
1112SN/AFloorLog2(unsigned long long x)
1122SN/A{
1132SN/A    assert(x > 0);
1142SN/A
1152SN/A    int y = 0;
1162SN/A
1171354SN/A    if (x & ULL(0xffffffff00000000)) { y += 32; x >>= 32; }
1182SN/A    if (x & ULL(0x00000000ffff0000)) { y += 16; x >>= 16; }
119503SN/A    if (x & ULL(0x000000000000ff00)) { y +=  8; x >>=  8; }
1202SN/A    if (x & ULL(0x00000000000000f0)) { y +=  4; x >>=  4; }
1212SN/A    if (x & ULL(0x000000000000000c)) { y +=  2; x >>=  2; }
1222SN/A    if (x & ULL(0x0000000000000002)) { y +=  1; }
1232SN/A
1241400SN/A    return y;
1252SN/A}
1263144Shsul@eecs.umich.edu
1273144Shsul@eecs.umich.eduinline int
1283144Shsul@eecs.umich.eduFloorLog2(int x)
1292SN/A{
1301400SN/A    assert(x > 0);
1312SN/A    return FloorLog2((unsigned)x);
1322SN/A}
1332SN/A
1342SN/Ainline int
1352SN/AFloorLog2(long x)
1362SN/A{
137503SN/A    assert(x > 0);
1382SN/A    return FloorLog2((unsigned long)x);
1391400SN/A}
1402SN/A
1412SN/Ainline int
142124SN/AFloorLog2(long long x)
1431354SN/A{
144124SN/A    assert(x > 0);
145124SN/A    return FloorLog2((unsigned long long)x);
146124SN/A}
147124SN/A
148124SN/A#if defined(__APPLE__)
149124SN/Ainline int
1501400SN/AFloorLog2(size_t x)
151124SN/A{
1523144Shsul@eecs.umich.edu    assert(x > 0);
1533144Shsul@eecs.umich.edu    assert(sizeof(size_t) == 4 || sizeof(size_t) == 8);
1543144Shsul@eecs.umich.edu
155124SN/A    // It's my hope that this is optimized away?
1561400SN/A    if (sizeof(size_t) == 4)
157124SN/A        return FloorLog2((uint32_t)x);
158124SN/A     else if (sizeof(size_t) == 8)
159124SN/A        return FloorLog2((uint64_t)x);
160124SN/A
161124SN/A}
162124SN/A#endif
163124SN/A
164124SN/Atemplate <class T>
1651400SN/Ainline int
166124SN/ACeilLog2(T n)
167124SN/A{
1681191SN/A    if (n == 1)
1695529Snate@binkert.org        return 0;
1701388SN/A
1711191SN/A    return FloorLog2(n - (T)1) + 1;
1725529Snate@binkert.org}
1731191SN/A
1745529Snate@binkert.orgtemplate <class T>
1751191SN/Ainline T
1761191SN/AFloorPow2(T n)
1775529Snate@binkert.org{
1785529Snate@binkert.org    return (T)1 << FloorLog2(n);
1795529Snate@binkert.org}
1801191SN/A
1811191SN/Atemplate <class T>
1821917SN/Ainline T
1831917SN/ACeilPow2(T n)
1845529Snate@binkert.org{
1855529Snate@binkert.org    return (T)1 << CeilLog2(n);
1861917SN/A}
1875529Snate@binkert.org
1881917SN/Atemplate <class T>
1891191SN/Ainline T
1901191SN/ADivCeil(T a, T b)
1911191SN/A{
1921191SN/A    return (a + b - 1) / b;
1931191SN/A}
1941191SN/A
1951191SN/Atemplate <class T>
1961191SN/Ainline T
1971191SN/ARoundUp(T val, T align)
1981191SN/A{
1991191SN/A    T mask = align - 1;
2001129SN/A    return (val + mask) & ~mask;
2011129SN/A}
2021129SN/A
2035529Snate@binkert.orgtemplate <class T>
2042680Sktlim@umich.eduinline T
2051129SN/ARoundDown(T val, T align)
206180SN/A{
2072SN/A    T mask = align - 1;
2081917SN/A    return val & ~mask;
2091917SN/A}
2101917SN/A
2115529Snate@binkert.orginline bool
2121917SN/AIsHex(char c)
2131917SN/A{
2142356SN/A    return c >= '0' && c <= '9' ||
2155529Snate@binkert.org        c >= 'A' && c <= 'F' ||
2164031Sktlim@umich.edu        c >= 'a' && c <= 'f';
2175529Snate@binkert.org}
2182356SN/A
2192356SN/Ainline bool
2201917SN/AIsOct(char c)
2211917SN/A{
2221917SN/A    return c >= '0' && c <= '7';
2231917SN/A}
2242SN/A
2252SN/Ainline bool
226729SN/AIsDec(char c)
227707SN/A{
228707SN/A    return c >= '0' && c <= '9';
229707SN/A}
230707SN/A
231707SN/Ainline int
232707SN/AHex2Int(char c)
2332680Sktlim@umich.edu{
2342SN/A  if (c >= '0' && c <= '9')
2352SN/A    return (c - '0');
2362SN/A
2372SN/A  if (c >= 'A' && c <= 'F')
2382680Sktlim@umich.edu    return (c - 'A') + 10;
2392SN/A
2402SN/A  if (c >= 'a' && c <= 'f')
2412680Sktlim@umich.edu    return (c - 'a') + 10;
2422190SN/A
2432190SN/A  return 0;
2442190SN/A}
2452SN/A
2462SN/A#endif // __INTMATH_HH__
2473495Sktlim@umich.edu