hphp/util/bitops.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_BITOPS_H_
  18 #define incl_HPHP_BITOPS_H_
  19
  20 #if !defined(__x86_64__) && !defined(__aarch64__)
  21 #include <folly/Bits.h>
  22 #endif
  23
  24 #include "hphp/util/assertions.h"
  25
  26 namespace HPHP {
  27
  28 // GLIBC doesn't provide an fls primitive. Since we're rolling our own
  29 // anyway, fix ffs's wacky offset-by-one historical implementation. These
  30 // guys return success/failure (failure for input of all zeros) and the
  31 // unoffset bit position in their reference param.
  32 template<typename I64, typename J64>
  33 inline bool ffs64(I64 input, J64 &out) {
  34   bool retval = false;
  35 #if defined(__x86_64__)
  36   asm volatile (
  37     "bsfq  %2, %1\n\t"   // bit scan forward
  38     "setnz %0\n\t":      // zero retval if input == 0
  39     "=r"(retval), "=r"(out):
  40     "r"(input):
  41     "cc"
  42   );
  43 #elif defined(__aarch64__)
  44   asm volatile (
  45     "rbit  %2, %2\n\t"  // reverse bits
  46     "clz   %1, %2\n\t"  // count leading zeros
  47     "cmp   %1, #64\n\t"
  48     "cset  %0, NE":     // return (result != 64)
  49     "=r"(retval), "=r"(out), "+r"(input):
  50     :
  51     "cc"
  52   );
  53 #elif defined(__powerpc64__)
  54   // In PowerPC 64, bit 0 is the most significant
  55   asm volatile (
  56     "neg    %0, %2\n\t"     // 2-complement of input, using retval as temp
  57     "and    %0, %2, %0\n\t"
  58     "cntlzd %1, %0\n\t"     // count leading zeros (starting from index 0)
  59     "cmpdi  %1, 64\n\t"
  60     "li     %0, 1\n\t"      // using retval as temp
  61     "iseleq %0, 0, %0\n\t"  // (input == 0) ? 0 : 1
  62     "neg    %1, %1\n\t"
  63     "addi   %1, %1, 63\n\t":// 63 - amount of leading zeros -> position in LSB
  64     "+r"(retval), "=r"(out):// +r else %0 and %2 will be the same register
  65     "r"(input):
  66     "cr0"
  67   );
  68 #else
  69   out = folly::findFirstSet(input);
  70   retval = input != 0;
  71 #endif
  72   return retval;
  73 }
  74
  75 template<typename I64, typename J64>
  76 inline bool fls64(I64 input, J64 &out) {
  77   bool retval;
  78 #if defined(__x86_64__)
  79   asm volatile (
  80     "bsrq  %2, %1\n\t"   // bit scan reverse
  81     "setnz %0\n\t":      // zero retval if input == 0
  82     "=r"(retval), "=r"(out):
  83     "r"(input):
  84     "cc"
  85   );
  86 #elif defined(__aarch64__)
  87   asm volatile (
  88     "clz   %1, %2\n\t"      // count leading zeros
  89     "neg   %1, %1\n\t"
  90     "adds  %1, %1, #63\n\t" // result = 63 - (# of leading zeros)
  91                             // "s" suffix sets condition flags
  92     "cset  %0, PL":         // return (result >= 0)
  93                             //   because result < 0 iff input == 0
  94     "=r"(retval), "=r"(out):
  95     "r"(input):
  96     "cc"
  97   );
  98 #elif defined(__powerpc64__)
  99   // In PowerPC 64, bit 0 is the most significant
 100   asm volatile (
 101     "cntlzd %1, %2\n\t"     // count leading zeros (starting from index 0)
 102     "cmpdi  %1, 64\n\t"
 103     "li     %0, 1\n\t"      // using retval as temp
 104     "iseleq %0, 0, %0\n\t"  // (input == 0) ? 0 : 1
 105     "neg    %1, %1\n\t"
 106     "addi   %1, %1, 63\n\t":// 63 - amount of leading zeros -> position in LSB
 107     "=r"(retval), "=r"(out):
 108     "r"(input):
 109     "cr0"
 110   );
 111 #else
 112   out = folly::findLastSet(input) - 1;
 113   retval = input != 0;
 114 #endif
 115   return retval;
 116 }
 117
 118 /*
 119  * Return the index (0..63) of the most significant bit in x.
 120  * x must be nonzero.
 121  */
 122 inline size_t fls64(size_t x) {
 123   assertx(x);
 124 #if defined(__x86_64__)
 125   size_t ret;
 126   __asm__ ("bsrq %1, %0"
 127            : "=r"(ret) // Outputs.
 128            : "r"(x)    // Inputs.
 129            );
 130   return ret;
 131 #elif defined(__powerpc64__)
 132   size_t ret;
 133   __asm__ ("cntlzd %0, %1"
 134            : "=r"(ret) // Outputs.
 135            : "r"(x)    // Inputs.
 136            );
 137   return 63 - ret;
 138 #elif defined(__aarch64__)
 139   size_t ret;
 140   __asm__ ("clz %x0, %x1"
 141            : "=r"(ret) // Outputs.
 142            : "r"(x)    // Inputs.
 143            );
 144   return 63 - ret;
 145 #else
 146   // Equivalent (but incompletely strength-reduced by gcc):
 147   return 63 - __builtin_clzl(x);
 148 #endif
 149 }
 150
 151 } // HPHP
 152
 153 #endif