nsprpub/pr/include/prbit.h

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