vpx_ports/bitops.h

   1 /*
   2  *  Copyright (c) 2010 The WebM project authors. All Rights Reserved.
   3  *
   4  *  Use of this source code is governed by a BSD-style license
   5  *  that can be found in the LICENSE file in the root of the source
   6  *  tree. An additional intellectual property rights grant can be found
   7  *  in the file PATENTS.  All contributing project authors may
   8  *  be found in the AUTHORS file in the root of the source tree.
   9  */
  10
  11 #ifndef VPX_VPX_PORTS_BITOPS_H_
  12 #define VPX_VPX_PORTS_BITOPS_H_
  13
  14 #include <assert.h>
  15
  16 #include "vpx_ports/msvc.h"
  17
  18 #ifdef _MSC_VER
  19 #if defined(_M_X64) || defined(_M_IX86)
  20 #include <intrin.h>
  21 #define USE_MSC_INTRINSICS
  22 #endif
  23 #endif
  24
  25 #ifdef __cplusplus
  26 extern "C" {
  27 #endif
  28
  29 // These versions of get_lsb() and get_msb() are only valid when n != 0
  30 // because all of the optimized versions are undefined when n == 0:
  31 // https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
  32
  33 // use GNU builtins where available.
  34 #if defined(__GNUC__) && \
  35     ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4)
  36 static INLINE int get_lsb(unsigned int n) {
  37   assert(n != 0);
  38   return __builtin_ctz(n);
  39 }
  40
  41 static INLINE int get_msb(unsigned int n) {
  42   assert(n != 0);
  43   return 31 ^ __builtin_clz(n);
  44 }
  45 #elif defined(USE_MSC_INTRINSICS)
  46 #pragma intrinsic(_BitScanForward)
  47 #pragma intrinsic(_BitScanReverse)
  48
  49 static INLINE int get_lsb(unsigned int n) {
  50   unsigned long first_set_bit;  // NOLINT(runtime/int)
  51   _BitScanForward(&first_set_bit, n);
  52   return first_set_bit;
  53 }
  54
  55 static INLINE int get_msb(unsigned int n) {
  56   unsigned long first_set_bit;
  57   assert(n != 0);
  58   _BitScanReverse(&first_set_bit, n);
  59   return first_set_bit;
  60 }
  61 #undef USE_MSC_INTRINSICS
  62 #else
  63 static INLINE int get_lsb(unsigned int n) {
  64   int i;
  65   assert(n != 0);
  66   for (i = 0; i < 32 && !(n & 1); ++i) n >>= 1;
  67   return i;
  68 }
  69
  70 // Returns (int)floor(log2(n)). n must be > 0.
  71 static INLINE int get_msb(unsigned int n) {
  72   int log = 0;
  73   unsigned int value = n;
  74   int i;
  75
  76   assert(n != 0);
  77
  78   for (i = 4; i >= 0; --i) {
  79     const int shift = (1 << i);
  80     const unsigned int x = value >> shift;
  81     if (x != 0) {
  82       value = x;
  83       log += shift;
  84     }
  85   }
  86   return log;
  87 }
  88 #endif
  89
  90 #ifdef __cplusplus
  91 }  // extern "C"
  92 #endif
  93
  94 #endif  // VPX_VPX_PORTS_BITOPS_H_