intmath.hh revision 52
1/* 2 * Copyright (c) 2003 The Regents of The University of Michigan 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29#ifndef __INTMATH_HH__ 30#define __INTMATH_HH__ 31 32// Returns the prime number one less than n. 33int PrevPrime(int n); 34 35// Determine if a number is prime 36template <class T> 37inline bool 38IsPrime(T n) 39{ 40 T i; 41 42 if (n == 2 || n == 3) 43 return true; 44 45 // Don't try every odd number to prove if it is a prime. 46 // Toggle between every 2nd and 4th number. 47 // (This is because every 6th odd number is divisible by 3.) 48 for (i = 5; i*i <= n; i += 6) { 49 if (((n % i) == 0 ) || ((n % (i + 2)) == 0) ) { 50 return false; 51 } 52 } 53 54 return true; 55} 56 57template <class T> 58inline T 59LeastSigBit(T n) 60{ 61 return n & ~(n - 1); 62} 63 64template <class T> 65inline bool 66IsPowerOf2(T n) 67{ 68 return n != 0 && LeastSigBit(n) == n; 69} 70 71template <class T> 72inline int 73FloorLog2(T x) 74{ 75 if (x == 0) 76 return -1; 77 78 int y = 0; 79 80 if (x & 0xffff0000) { y += 16; x >>= 16; } 81 if (x & 0x0000ff00) { y += 8; x >>= 8; } 82 if (x & 0x000000f0) { y += 4; x >>= 4; } 83 if (x & 0x0000000c) { y += 2; x >>= 2; } 84 if (x & 0x00000002) { y += 1; } 85 86 return y; 87} 88 89template <class T> 90inline int 91CeilLog2(T n) 92{ 93 return FloorLog2(n - 1) + 1; 94} 95 96template <class T> 97inline T 98FloorPow2(T n) 99{ 100 return (T)1 << FloorLog2(n); 101} 102 103template <class T> 104inline T 105CeilPow2(T n) 106{ 107 return (T)1 << CeilLog2(n); 108} 109 110template <class T> 111inline T 112DivCeil(T a, T b) 113{ 114 return (a + b - 1) / b; 115} 116 117template <class T> 118inline T 119RoundUp(T val, T align) 120{ 121 T mask = align - 1; 122 return (val + mask) & ~mask; 123} 124 125template <class T> 126inline T 127RoundDown(T val, T align) 128{ 129 T mask = align - 1; 130 return val & ~mask; 131} 132 133inline bool 134IsHex(char c) 135{ 136 return c >= '0' && c <= '9' || 137 c >= 'A' && c <= 'F' || 138 c >= 'a' && c <= 'f'; 139} 140 141inline bool 142IsOct(char c) 143{ 144 return c >= '0' && c <= '7'; 145} 146 147inline bool 148IsDec(char c) 149{ 150 return c >= '0' && c <= '9'; 151} 152 153inline int 154Hex2Int(char c) 155{ 156 if (c >= '0' && c <= '9') 157 return (c - '0'); 158 159 if(c >= 'A' && c <= 'F') 160 return (c - 'A') + 10; 161 162 if (c >= 'a' && c <= 'f') 163 return (c - 'a') + 10; 164 165 return 0; 166} 167 168#endif // __INTMATH_HH__ 169