diff options
author | Jiyoung Yun <jy910.yun@samsung.com> | 2016-11-23 19:09:09 +0900 |
---|---|---|
committer | Jiyoung Yun <jy910.yun@samsung.com> | 2016-11-23 19:09:09 +0900 |
commit | 4b4aad7217d3292650e77eec2cf4c198ea9c3b4b (patch) | |
tree | 98110734c91668dfdbb126fcc0e15ddbd93738ca /src/inc/bitposition.h | |
parent | fa45f57ed55137c75ac870356a1b8f76c84b229c (diff) | |
download | coreclr-4b4aad7217d3292650e77eec2cf4c198ea9c3b4b.tar.gz coreclr-4b4aad7217d3292650e77eec2cf4c198ea9c3b4b.tar.bz2 coreclr-4b4aad7217d3292650e77eec2cf4c198ea9c3b4b.zip |
Imported Upstream version 1.1.0upstream/1.1.0
Diffstat (limited to 'src/inc/bitposition.h')
-rw-r--r-- | src/inc/bitposition.h | 55 |
1 files changed, 55 insertions, 0 deletions
diff --git a/src/inc/bitposition.h b/src/inc/bitposition.h new file mode 100644 index 0000000000..0f3831fce9 --- /dev/null +++ b/src/inc/bitposition.h @@ -0,0 +1,55 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +#ifndef _BITPOSITION_H_ +#define _BITPOSITION_H_ + +//------------------------------------------------------------------------ +// BitPosition: Return the position of the single bit that is set in 'value'. +// +// Return Value: +// The position (0 is LSB) of bit that is set in 'value' +// +// Notes: +// 'value' must have exactly one bit set. +// The algorithm is as follows: +// - PRIME is a prime bigger than sizeof(unsigned int), which is not of the +// form 2^n-1. +// - Taking the modulo of 'value' with this will produce a unique hash for all +// powers of 2 (which is what "value" is). +// - Entries in hashTable[] which are -1 should never be used. There +// should be PRIME-8*sizeof(value) entries which are -1 . +// +inline +unsigned BitPosition(unsigned value) +{ + _ASSERTE((value != 0) && ((value & (value-1)) == 0)); +#ifndef _TARGET_AMD64_ + const unsigned PRIME = 37; + + static const char hashTable[PRIME] = + { + -1, 0, 1, 26, 2, 23, 27, -1, 3, 16, + 24, 30, 28, 11, -1, 13, 4, 7, 17, -1, + 25, 22, 31, 15, 29, 10, 12, 6, -1, 21, + 14, 9, 5, 20, 8, 19, 18 + }; + + _ASSERTE(PRIME >= 8*sizeof(value)); + _ASSERTE(sizeof(hashTable) == PRIME); + + + unsigned hash = value % PRIME; + unsigned index = hashTable[hash]; + _ASSERTE(index != (unsigned char)-1); +#else + // not enabled for x86 because BSF is extremely slow on Atom + // (15 clock cycles vs 1-3 on any other Intel CPU post-P4) + DWORD index; + BitScanForward(&index, value); +#endif + return index; +} + +#endif |