src/bithacks.h

   1 /*
   2  * nao-ulib
   3  * Copyright (C) 2009 Daniel Borkmann <borkmann@gnumaniacs.org>
   4  * Copyright (C) 2009 Thomas Reinhardt <treinhar@imn.htwk-leipzig.de>
   5  * Copyright (C) 2009 Rico Tilgner <rtilgner@imn.htwk-leipzig.de>
   6  * Subject to the GPL.
   7  * Nao-Team HTWK,
   8  * Faculty of Computer Science, Mathematics and Natural Sciences,
   9  * Leipzig University of Applied Sciences (HTWK Leipzig)
  10  */
  11
  12 /*
  13  * Some stuff is from the Hacker's Delight book, some from
  14  * http://graphics.stanford.edu/~seander/bithacks.html, some
  15  * from Quake 3 Arena and some from ourselfes.
  16  */
  17
  18 #ifndef BITHACKS_H
  19 #define BITHACKS_H
  20
  21 #include <stdbool.h>
  22
  23 /* Inverse square root for floats */
  24 static inline float finvsqrt(float x)
  25 {
  26         int bf;
  27         float x_half;
  28
  29         x_half = .5f * x;
  30         bf = *(int *) &x;
  31         bf = 0x5F3759DF - (bf >> 1);
  32         x = *(float *) &bf;
  33         x = x * (1.5f - x_half * x * x);
  34
  35         return x;
  36 }
  37
  38 /* Branch-free absolute function for floats */
  39 static inline float fabs2(float x)
  40 {
  41         int bf;
  42
  43         bf = *(int *) &x;
  44         bf = bf & 0x7FFFFFFF;
  45         x = *(float *) &bf;
  46
  47         return x;
  48 }
  49
  50 /* Branch-free compare function for two integers */
  51 static inline int cmp(int x, int y)
  52 {
  53         return (x > y) - (x < y);
  54 }
  55
  56 /* Check if two integers have opposite signs */
  57 static inline int opp_sign(int x, int y)
  58 {
  59         return ((x ^ y) < 0);
  60 }
  61
  62 /* Returns sign of interger */
  63 static inline int sign(int x)
  64 {
  65         return (+1 | (x >> (sizeof(int) * 8 - 1)));
  66 }
  67
  68 /* Return absolute value of integer */
  69 static inline unsigned int iabs(int x)
  70 {
  71         int const mask = x >> sizeof(int) * 8 - 1;
  72         return (x + mask) ^ mask;
  73 }
  74
  75 /* Return minimum of x,y */
  76 static inline int min(int x, int y)
  77 {
  78         return y ^ ((x ^ y) & -(x < y));
  79 }
  80
  81 /* Return maximum of x,y */
  82 static inline int max(int x, int y)
  83 {
  84         return x ^ ((x ^ y) & -(x < y));
  85 }
  86
  87 /* Determine if x is power of 2 */
  88 static inline int ispow2(unsigned int x)
  89 {
  90         return x && !(x & (x - 1));
  91 }
  92
  93 /* if (cond) reg |= mask; else reg &= ~mask; */
  94 static inline unsigned int cond_set_bit(bool cond, unsigned int mask,
  95                                         unsigned int *reg)
  96 {
  97         (*reg) ^= (-cond ^ (*reg)) & mask;
  98 }
  99
 100 /* if (cond) reg |= mask; else reg &= ~mask; */
 101 static inline unsigned int cond_set_bit2(int cond, unsigned int mask,
 102                                          unsigned int *reg)
 103 {
 104         (*reg) ^= (-(!!(cond)) ^ (*reg)) & mask;
 105 }
 106
 107 /* Negate is negate is true */
 108 static inline int cond_negate(bool negate, int x)
 109 {
 110         return (x ^ -negate) + negate;
 111 }
 112
 113 /* Count Bits in x */
 114 static inline unsigned int count_bits_set(unsigned int x)
 115 {
 116         unsigned int c = 0;
 117
 118         for (c = 0; v; c++) {
 119                 v &= v - 1;
 120         }
 121
 122         return c;
 123 }
 124
 125 /* Square root calculus for integers */
 126 static inline int sqrt(unsigned x)
 127 {
 128         unsigned m, b, y;
 129
 130         m = 0x40000000;
 131         y = 0;
 132
 133         while (m != 0) {
 134                 b = y | m;
 135                 y = y >> 1;
 136
 137                 if (x >= b) {
 138                         x -= b;
 139                         y |= m;
 140                 }
 141                 m = m >> 2;
 142         }
 143
 144         return y;
 145 }
 146
 147 /* Cube root calculus for integers */
 148 static inline int cbrt(unsigned int x)
 149 {
 150         int s;
 151         unsigned b, y;
 152
 153         s = 30;
 154         y = 0;
 155
 156         while (s >= 0) {
 157                 y = y << 1;
 158                 b = (3 * y * (y + 1) + 1) << s;
 159                 s -= 3;
 160
 161                 if (x >= b) {
 162                         x -= b;
 163                         y++;
 164                 }
 165         }
 166
 167         return y;
 168 }
 169
 170 /* Exponentiation function for integers */
 171 static inline int exp(int x, unsigned n)
 172 {
 173         int p, y;
 174
 175         y = 1;
 176         p = x;
 177
 178         while (1) {
 179                 if (n & 1)
 180                         y *= p;
 181                 n = n >> 1;
 182                 if (n == 0)
 183                         return y;
 184                 p *= p;
 185         }
 186 }
 187
 188 #endif /* BITHACKS_H */