base/intmath.hh

   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.
  33 int PrevPrime(int n);
  34
  35 // Determine if a number is prime
  36 template <class T>
  37 inline bool
  38 IsPrime(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
  57 template <class T>
  58 inline T
  59 LeastSigBit(T n)
  60 {
  61     return n & ~(n - 1);
  62 }
  63
  64 template <class T>
  65 inline bool
  66 IsPowerOf2(T n)
  67 {
  68     return n != 0 && LeastSigBit(n) == n;
  69 }
  70
  71 template <class T>
  72 inline int
  73 FloorLog2(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
  89 template <class T>
  90 inline int
  91 CeilLog2(T n)
  92 {
  93     return FloorLog2(n - 1) + 1;
  94 }
  95
  96 template <class T>
  97 inline T
  98 FloorPow2(T n)
  99 {
 100     return (T)1 << FloorLog2(n);
 101 }
 102
 103 template <class T>
 104 inline T
 105 CeilPow2(T n)
 106 {
 107     return (T)1 << CeilLog2(n);
 108 }
 109
 110 template <class T>
 111 inline T
 112 DivCeil(T a, T b)
 113 {
 114     return (a + b - 1) / b;
 115 }
 116
 117 template <class T>
 118 inline T
 119 RoundUp(T val, T align)
 120 {
 121     T mask = align - 1;
 122     return (val + mask) & ~mask;
 123 }
 124
 125 template <class T>
 126 inline T
 127 RoundDown(T val, T align)
 128 {
 129     T mask = align - 1;
 130     return val & ~mask;
 131 }
 132
 133 inline bool
 134 IsHex(char c)
 135 {
 136     return c >= '0' && c <= '9' ||
 137         c >= 'A' && c <= 'F' ||
 138         c >= 'a' && c <= 'f';
 139 }
 140
 141 inline bool
 142 IsOct(char c)
 143 {
 144     return c >= '0' && c <= '7';
 145 }
 146
 147 inline bool
 148 IsDec(char c)
 149 {
 150     return c >= '0' && c <= '9';
 151 }
 152
 153 inline int
 154 Hex2Int(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__