1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5#ifndef _BITPOSITION_H_
6#define _BITPOSITION_H_
7
8//------------------------------------------------------------------------
9// BitPosition: Return the position of the single bit that is set in 'value'.
10//
11// Return Value:
12// The position (0 is LSB) of bit that is set in 'value'
13//
14// Notes:
15// 'value' must have exactly one bit set.
16// The algorithm is as follows:
17// - PRIME is a prime bigger than sizeof(unsigned int), which is not of the
18// form 2^n-1.
19// - Taking the modulo of 'value' with this will produce a unique hash for all
20// powers of 2 (which is what "value" is).
21// - Entries in hashTable[] which are -1 should never be used. There
22// should be PRIME-8*sizeof(value) entries which are -1 .
23//
24inline
25unsigned BitPosition(unsigned value)
26{
27 _ASSERTE((value != 0) && ((value & (value-1)) == 0));
28#if defined(_ARM_) && defined(__llvm__)
29 // use intrinsic functions for arm32
30 // this is applied for LLVM only but it may work for some compilers
31 DWORD index = __builtin_clz(__builtin_arm_rbit(value));
32#elif !defined(_AMD64_)
33 const unsigned PRIME = 37;
34
35 static const char hashTable[PRIME] =
36 {
37 -1, 0, 1, 26, 2, 23, 27, -1, 3, 16,
38 24, 30, 28, 11, -1, 13, 4, 7, 17, -1,
39 25, 22, 31, 15, 29, 10, 12, 6, -1, 21,
40 14, 9, 5, 20, 8, 19, 18
41 };
42
43 _ASSERTE(PRIME >= 8*sizeof(value));
44 _ASSERTE(sizeof(hashTable) == PRIME);
45
46
47 unsigned hash = value % PRIME;
48 unsigned index = hashTable[hash];
49 _ASSERTE(index != (unsigned char)-1);
50#else
51 // not enabled for x86 because BSF is extremely slow on Atom
52 // (15 clock cycles vs 1-3 on any other Intel CPU post-P4)
53 DWORD index;
54 BitScanForward(&index, value);
55#endif
56 return index;
57}
58
59#endif
60