include/common/clz.h

   1 /*
   2         SuperCollider real time audio synthesis system
   3     Copyright (c) 2002 James McCartney. All rights reserved.
   4         http://www.audiosynth.com
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  19 */
  20 /*
  21
  22 count leading zeroes function and those that can be derived from it
  23
  24 */
  25
  26
  27 #ifndef _CLZ_
  28 #define _CLZ_
  29
  30 #include "SC_Types.h"
  31
  32 #ifdef __MWERKS__
  33
  34 #define __PPC__ 1
  35 #define __X86__ 0
  36
  37 // powerpc native count leading zeroes instruction:
  38 #define CLZ(x)  ((int)__cntlzw((unsigned int)x))
  39
  40 #elif defined(__GNUC__)
  41
  42 /* use gcc's builtins */
  43 static __inline__ int32 CLZ(int32 arg)
  44 {
  45     if (arg)
  46         return __builtin_clz(arg);
  47     else
  48         return 32;
  49 }
  50
  51 #elif defined(_MSC_VER)
  52
  53 #include <intrin.h>
  54 #pragma intrinsic(_BitScanReverse)
  55
  56 __forceinline static int32 CLZ( int32 arg )
  57 {
  58         unsigned long idx;
  59         if (_BitScanReverse(&idx, (unsigned long)arg))
  60         {
  61                 return (int32)(31-idx);
  62         }
  63         return 32;
  64 }
  65
  66 #elif defined(__ppc__) || defined(__powerpc__) || defined(__PPC__)
  67
  68 static __inline__ int32 CLZ(int32 arg) {
  69         __asm__ volatile("cntlzw %0, %1" : "=r" (arg) : "r" (arg));
  70         return arg;
  71 }
  72
  73 #elif defined(__i386__) || defined(__x86_64__)
  74 static __inline__ int32 CLZ(int32 arg) {
  75         if (arg) {
  76                 __asm__ volatile("bsrl %0, %0\nxorl $31, %0\n"
  77                                                  : "=r" (arg) : "0" (arg));
  78         } else {
  79                 arg = 32;
  80         }
  81         return arg;
  82 }
  83
  84 #elif defined(SC_IPHONE)
  85 static __inline__ int32 CLZ(int32 arg)
  86 {
  87         return __builtin_clz(arg);
  88 }
  89
  90 #else
  91 # error "clz.h: Unsupported architecture"
  92 #endif
  93
  94 // count trailing zeroes
  95 inline int32 CTZ(int32 x)
  96 {
  97         return 32 - CLZ(~x & (x-1));
  98 }
  99
 100 // count leading ones
 101 inline int32 CLO(int32 x)
 102 {
 103         return CLZ(~x);
 104 }
 105
 106 // count trailing ones
 107 inline int32 CTO(int32 x)
 108 {
 109         return 32 - CLZ(x & (~x-1));
 110 }
 111
 112 // number of bits required to represent x.
 113 inline int32 NUMBITS(int32 x)
 114 {
 115         return 32 - CLZ(x);
 116 }
 117
 118 // log2 of the next power of two greater than or equal to x.
 119 inline int32 LOG2CEIL(int32 x)
 120 {
 121         return 32 - CLZ(x - 1);
 122 }
 123
 124 // is x a power of two
 125 inline bool ISPOWEROFTWO(int32 x)
 126 {
 127         return (x & (x-1)) == 0;
 128 }
 129
 130 // next power of two greater than or equal to x
 131 inline int32 NEXTPOWEROFTWO(int32 x)
 132 {
 133         return 1L << LOG2CEIL(x);
 134 }
 135
 136 // previous power of two less than or equal to x
 137 inline int32 PREVIOUSPOWEROFTWO(int32 x)
 138 {
 139         if (ISPOWEROFTWO(x))
 140                 return x;
 141         return 1L << (LOG2CEIL(x) - 1);
 142 }
 143
 144 // input a series of counting integers, outputs a series of gray codes .
 145 inline int32 GRAYCODE(int32 x)
 146 {
 147         return x ^ (x>>1);
 148 }
 149
 150 // find least significant bit
 151 inline int32 LSBit(int32 x)
 152 {
 153         return x & -x;
 154 }
 155
 156 // find least significant bit position
 157 inline int32 LSBitPos(int32 x)
 158 {
 159         return CTZ(x & -x);
 160 }
 161
 162 // find most significant bit position
 163 inline int32 MSBitPos(int32 x)
 164 {
 165         return 31 - CLZ(x);
 166 }
 167
 168 // find most significant bit
 169 inline int32 MSBit(int32 x)
 170 {
 171         return 1L << MSBitPos(x);
 172 }
 173
 174 // count number of one bits
 175 inline uint32 ONES(uint32 x)
 176 {
 177         uint32 t;
 178         x = x - ((x >> 1) & 0x55555555);
 179         t = ((x >> 2) & 0x33333333);
 180         x = (x & 0x33333333) + t;
 181         x = (x + (x >> 4)) & 0x0F0F0F0F;
 182         x = x + (x << 8);
 183         x = x + (x << 16);
 184         return x >> 24;
 185 }
 186
 187 // count number of zero bits
 188 inline uint32 ZEROES(uint32 x)
 189 {
 190         return ONES(~x);
 191 }
 192
 193
 194 // reverse bits in a word
 195 inline uint32 BitReverse(uint32 x)
 196 {
 197   x = ((x & 0xAAAAAAAA) >>  1) | ((x & 0x55555555) <<  1);
 198   x = ((x & 0xCCCCCCCC) >>  2) | ((x & 0x33333333) <<  2);
 199   x = ((x & 0xF0F0F0F0) >>  4) | ((x & 0x0F0F0F0F) <<  4);
 200   x = ((x & 0xFF00FF00) >>  8) | ((x & 0x00FF00FF) <<  8);
 201   return (x >> 16) | (x << 16);
 202 }
 203
 204 // barrel shifts
 205 inline uint32 RotateRight (uint32 x, uint32 s)
 206 {
 207         s = s & 31;
 208         return (x << (32-s)) | (x >> s);
 209 }
 210
 211 inline uint32 RotateLeft (uint32 x, uint32 s)
 212 {
 213         s = s & 31;
 214         return (x >> (32-s)) | (x << s);
 215 }
 216
 217 #endif
 218