Jamoma API  0.6.0.a19
CABitOperations.h
1 /* Copyright 2007 Apple Inc. All Rights Reserved.
2 
3  Disclaimer: IMPORTANT: This Apple software is supplied to you by
4  Apple Inc. ("Apple") in consideration of your agreement to the
5  following terms, and your use, installation, modification or
6  redistribution of this Apple software constitutes acceptance of these
7  terms. If you do not agree with these terms, please do not use,
8  install, modify or redistribute this Apple software.
9 
10  In consideration of your agreement to abide by the following terms, and
11  subject to these terms, Apple grants you a personal, non-exclusive
12  license, under Apple's copyrights in this original Apple software (the
13  "Apple Software"), to use, reproduce, modify and redistribute the Apple
14  Software, with or without modifications, in source and/or binary forms;
15  provided that if you redistribute the Apple Software in its entirety and
16  without modifications, you must retain this notice and the following
17  text and disclaimers in all such redistributions of the Apple Software.
18  Neither the name, trademarks, service marks or logos of Apple Inc.
19  may be used to endorse or promote products derived from the Apple
20  Software without specific prior written permission from Apple. Except
21  as expressly stated in this notice, no other rights or licenses, express
22  or implied, are granted by Apple herein, including but not limited to
23  any patent rights that may be infringed by your derivative works or by
24  other works in which the Apple Software may be incorporated.
25 
26  The Apple Software is provided by Apple on an "AS IS" basis. APPLE
27  MAKES NO WARRANTIES, EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION
28  THE IMPLIED WARRANTIES OF NON-INFRINGEMENT, MERCHANTABILITY AND FITNESS
29  FOR A PARTICULAR PURPOSE, REGARDING THE APPLE SOFTWARE OR ITS USE AND
30  OPERATION ALONE OR IN COMBINATION WITH YOUR PRODUCTS.
31 
32  IN NO EVENT SHALL APPLE BE LIABLE FOR ANY SPECIAL, INDIRECT, INCIDENTAL
33  OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
34  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
35  INTERRUPTION) ARISING IN ANY WAY OUT OF THE USE, REPRODUCTION,
36  MODIFICATION AND/OR DISTRIBUTION OF THE APPLE SOFTWARE, HOWEVER CAUSED
37  AND WHETHER UNDER THEORY OF CONTRACT, TORT (INCLUDING NEGLIGENCE),
38  STRICT LIABILITY OR OTHERWISE, EVEN IF APPLE HAS BEEN ADVISED OF THE
39  POSSIBILITY OF SUCH DAMAGE.
40 */
41 #ifndef _CABitOperations_h_
42 #define _CABitOperations_h_
43 
44 #if !defined(__COREAUDIO_USE_FLAT_INCLUDES__)
45  //#include <CoreServices/../Frameworks/CarbonCore.framework/Headers/MacTypes.h>
46  #include <CoreFoundation/CFBase.h>
47 #else
48 // #include <MacTypes.h>
49  #include "CFBase.h"
50 #endif
51 #include <TargetConditionals.h>
52 
53 // return whether a number is a power of two
54 inline UInt32 IsPowerOfTwo(UInt32 x)
55 {
56  return (x & (x-1)) == 0;
57 }
58 
59 // count the leading zeroes in a word
60 #ifdef __MWERKS__
61 
62 // Metrowerks Codewarrior. powerpc native count leading zeroes instruction:
63 #define CountLeadingZeroes(x) ((int)__cntlzw((unsigned int)x))
64 
65 #elif TARGET_OS_WIN32
66 
67 static int CountLeadingZeroes( int arg )
68 {
69  __asm{
70  bsr eax, arg
71  mov ecx, 63
72  cmovz eax, ecx
73  xor eax, 31
74  }
75  return arg;
76 }
77 
78 #else
79 
80 static __inline__ int CountLeadingZeroes(int arg) {
81 #if TARGET_CPU_PPC || TARGET_CPU_PPC64
82  __asm__ volatile("cntlzw %0, %1" : "=r" (arg) : "r" (arg));
83  return arg;
84 #elif TARGET_CPU_X86 || TARGET_CPU_X86_64
85  __asm__ volatile(
86  "bsrl %0, %0\n\t"
87  "movl $63, %%ecx\n\t"
88  "cmove %%ecx, %0\n\t"
89  "xorl $31, %0"
90  : "=r" (arg)
91  : "0" (arg) : "%ecx"
92  );
93  return arg;
94 #else
95  if (arg == 0) return 32;
96  return __builtin_clz(arg);
97 #endif
98 }
99 
100 #endif
101 
102 // count trailing zeroes
103 inline UInt32 CountTrailingZeroes(UInt32 x)
104 {
105  return 32 - CountLeadingZeroes(~x & (x-1));
106 }
107 
108 // count leading ones
109 inline UInt32 CountLeadingOnes(UInt32 x)
110 {
111  return CountLeadingZeroes(~x);
112 }
113 
114 // count trailing ones
115 inline UInt32 CountTrailingOnes(UInt32 x)
116 {
117  return 32 - CountLeadingZeroes(x & (~x-1));
118 }
119 
120 // number of bits required to represent x.
121 inline UInt32 NumBits(UInt32 x)
122 {
123  return 32 - CountLeadingZeroes(x);
124 }
125 
126 // base 2 log of next power of two greater or equal to x
127 inline UInt32 Log2Ceil(UInt32 x)
128 {
129  return 32 - CountLeadingZeroes(x - 1);
130 }
131 
132 // next power of two greater or equal to x
133 inline UInt32 NextPowerOfTwo(UInt32 x)
134 {
135  return 1L << Log2Ceil(x);
136 }
137 
138 // counting the one bits in a word
139 inline UInt32 CountOnes(UInt32 x)
140 {
141  // secret magic algorithm for counting bits in a word.
142  UInt32 t;
143  x = x - ((x >> 1) & 0x55555555);
144  t = ((x >> 2) & 0x33333333);
145  x = (x & 0x33333333) + t;
146  x = (x + (x >> 4)) & 0x0F0F0F0F;
147  x = x + (x << 8);
148  x = x + (x << 16);
149  return x >> 24;
150 }
151 
152 // counting the zero bits in a word
153 inline UInt32 CountZeroes(UInt32 x)
154 {
155  return CountOnes(~x);
156 }
157 
158 // return the bit position (0..31) of the least significant bit
159 inline UInt32 LSBitPos(UInt32 x)
160 {
161  return CountTrailingZeroes(x & -(SInt32)x);
162 }
163 
164 // isolate the least significant bit
165 inline UInt32 LSBit(UInt32 x)
166 {
167  return x & -(SInt32)x;
168 }
169 
170 // return the bit position (0..31) of the most significant bit
171 inline UInt32 MSBitPos(UInt32 x)
172 {
173  return 31 - CountLeadingZeroes(x);
174 }
175 
176 // isolate the most significant bit
177 inline UInt32 MSBit(UInt32 x)
178 {
179  return 1UL << MSBitPos(x);
180 }
181 
182 // Division optimized for power of 2 denominators
183 inline UInt32 DivInt(UInt32 numerator, UInt32 denominator)
184 {
185  if(IsPowerOfTwo(denominator))
186  return numerator >> (31 - CountLeadingZeroes(denominator));
187  else
188  return numerator/denominator;
189 }
190 
191 #endif
192