OLD | NEW |
| (Empty) |
1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ | |
2 /* This Source Code Form is subject to the terms of the Mozilla Public | |
3 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
5 | |
6 #ifndef prbit_h___ | |
7 #define prbit_h___ | |
8 | |
9 #include "prtypes.h" | |
10 PR_BEGIN_EXTERN_C | |
11 | |
12 /* | |
13 ** Replace compare/jump/add/shift sequence with compiler built-in/intrinsic | |
14 ** functions. | |
15 */ | |
16 #if defined(_WIN32) && (_MSC_VER >= 1300) && \ | |
17 (defined(_M_IX86) || defined(_M_AMD64) || defined(_M_ARM)) | |
18 # include <intrin.h> | |
19 # pragma intrinsic(_BitScanForward,_BitScanReverse) | |
20 __forceinline static int __prBitScanForward32(unsigned int val) | |
21 { | |
22 unsigned long idx; | |
23 _BitScanForward(&idx, (unsigned long)val); | |
24 return( (int)idx ); | |
25 } | |
26 __forceinline static int __prBitScanReverse32(unsigned int val) | |
27 { | |
28 unsigned long idx; | |
29 _BitScanReverse(&idx, (unsigned long)val); | |
30 return( (int)(31-idx) ); | |
31 } | |
32 # define pr_bitscan_ctz32(val) __prBitScanForward32(val) | |
33 # define pr_bitscan_clz32(val) __prBitScanReverse32(val) | |
34 # define PR_HAVE_BUILTIN_BITSCAN32 | |
35 #elif ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) && \ | |
36 (defined(__i386__) || defined(__x86_64__) || defined(__arm__)) | |
37 # define pr_bitscan_ctz32(val) __builtin_ctz(val) | |
38 # define pr_bitscan_clz32(val) __builtin_clz(val) | |
39 # define PR_HAVE_BUILTIN_BITSCAN32 | |
40 #endif /* MSVC || GCC */ | |
41 | |
42 /* | |
43 ** A prbitmap_t is a long integer that can be used for bitmaps | |
44 */ | |
45 typedef unsigned long prbitmap_t; | |
46 | |
47 #define PR_TEST_BIT(_map,_bit) \ | |
48 ((_map)[(_bit)>>PR_BITS_PER_LONG_LOG2] & (1L << ((_bit) & (PR_BITS_PER_LONG-
1)))) | |
49 #define PR_SET_BIT(_map,_bit) \ | |
50 ((_map)[(_bit)>>PR_BITS_PER_LONG_LOG2] |= (1L << ((_bit) & (PR_BITS_PER_LONG
-1)))) | |
51 #define PR_CLEAR_BIT(_map,_bit) \ | |
52 ((_map)[(_bit)>>PR_BITS_PER_LONG_LOG2] &= ~(1L << ((_bit) & (PR_BITS_PER_LON
G-1)))) | |
53 | |
54 /* | |
55 ** Compute the log of the least power of 2 greater than or equal to n | |
56 */ | |
57 NSPR_API(PRIntn) PR_CeilingLog2(PRUint32 i); | |
58 | |
59 /* | |
60 ** Compute the log of the greatest power of 2 less than or equal to n | |
61 */ | |
62 NSPR_API(PRIntn) PR_FloorLog2(PRUint32 i); | |
63 | |
64 /* | |
65 ** Macro version of PR_CeilingLog2: Compute the log of the least power of | |
66 ** 2 greater than or equal to _n. The result is returned in _log2. | |
67 */ | |
68 #ifdef PR_HAVE_BUILTIN_BITSCAN32 | |
69 #define PR_CEILING_LOG2(_log2,_n) \ | |
70 PR_BEGIN_MACRO \ | |
71 PRUint32 j_ = (PRUint32)(_n); \ | |
72 (_log2) = (j_ <= 1 ? 0 : 32 - pr_bitscan_clz32(j_ - 1)); \ | |
73 PR_END_MACRO | |
74 #else | |
75 #define PR_CEILING_LOG2(_log2,_n) \ | |
76 PR_BEGIN_MACRO \ | |
77 PRUint32 j_ = (PRUint32)(_n); \ | |
78 (_log2) = 0; \ | |
79 if ((j_) & ((j_)-1)) \ | |
80 (_log2) += 1; \ | |
81 if ((j_) >> 16) \ | |
82 (_log2) += 16, (j_) >>= 16; \ | |
83 if ((j_) >> 8) \ | |
84 (_log2) += 8, (j_) >>= 8; \ | |
85 if ((j_) >> 4) \ | |
86 (_log2) += 4, (j_) >>= 4; \ | |
87 if ((j_) >> 2) \ | |
88 (_log2) += 2, (j_) >>= 2; \ | |
89 if ((j_) >> 1) \ | |
90 (_log2) += 1; \ | |
91 PR_END_MACRO | |
92 #endif /* PR_HAVE_BUILTIN_BITSCAN32 */ | |
93 | |
94 /* | |
95 ** Macro version of PR_FloorLog2: Compute the log of the greatest power of | |
96 ** 2 less than or equal to _n. The result is returned in _log2. | |
97 ** | |
98 ** This is equivalent to finding the highest set bit in the word. | |
99 */ | |
100 #ifdef PR_HAVE_BUILTIN_BITSCAN32 | |
101 #define PR_FLOOR_LOG2(_log2,_n) \ | |
102 PR_BEGIN_MACRO \ | |
103 PRUint32 j_ = (PRUint32)(_n); \ | |
104 (_log2) = 31 - pr_bitscan_clz32((j_) | 1); \ | |
105 PR_END_MACRO | |
106 #else | |
107 #define PR_FLOOR_LOG2(_log2,_n) \ | |
108 PR_BEGIN_MACRO \ | |
109 PRUint32 j_ = (PRUint32)(_n); \ | |
110 (_log2) = 0; \ | |
111 if ((j_) >> 16) \ | |
112 (_log2) += 16, (j_) >>= 16; \ | |
113 if ((j_) >> 8) \ | |
114 (_log2) += 8, (j_) >>= 8; \ | |
115 if ((j_) >> 4) \ | |
116 (_log2) += 4, (j_) >>= 4; \ | |
117 if ((j_) >> 2) \ | |
118 (_log2) += 2, (j_) >>= 2; \ | |
119 if ((j_) >> 1) \ | |
120 (_log2) += 1; \ | |
121 PR_END_MACRO | |
122 #endif /* PR_HAVE_BUILTIN_BITSCAN32 */ | |
123 | |
124 /* | |
125 ** Macros for rotate left and right. The argument 'a' must be an unsigned | |
126 ** 32-bit integer type such as PRUint32. | |
127 ** | |
128 ** There is no rotate operation in the C Language, so the construct | |
129 ** (a << 4) | (a >> 28) is frequently used instead. Most compilers convert | |
130 ** this to a rotate instruction, but MSVC doesn't without a little help. | |
131 ** To get MSVC to generate a rotate instruction, we have to use the _rotl | |
132 ** or _rotr intrinsic and use a pragma to make it inline. | |
133 ** | |
134 ** Note: MSVC in VS2005 will do an inline rotate instruction on the above | |
135 ** construct. | |
136 */ | |
137 | |
138 #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_AMD64) || \ | |
139 defined(_M_X64) || defined(_M_ARM)) | |
140 #include <stdlib.h> | |
141 #pragma intrinsic(_rotl, _rotr) | |
142 #define PR_ROTATE_LEFT32(a, bits) _rotl(a, bits) | |
143 #define PR_ROTATE_RIGHT32(a, bits) _rotr(a, bits) | |
144 #else | |
145 #define PR_ROTATE_LEFT32(a, bits) (((a) << (bits)) | ((a) >> (32 - (bits)))) | |
146 #define PR_ROTATE_RIGHT32(a, bits) (((a) >> (bits)) | ((a) << (32 - (bits)))) | |
147 #endif | |
148 | |
149 PR_END_EXTERN_C | |
150 #endif /* prbit_h___ */ | |
OLD | NEW |