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 #pragma once
  18
  19 #if !defined(__x86_64__) && !defined(__aarch64__)
  20 #include <folly/Bits.h>
  21 #endif
  22
  23 #include "hphp/util/assertions.h"
  24
  25 namespace HPHP {
  26
  27 // GLIBC doesn't provide an fls primitive. Since we're rolling our own
  28 // anyway, fix ffs's wacky offset-by-one historical implementation. These
  29 // guys return success/failure (failure for input of all zeros) and the
  30 // unoffset bit position in their reference param.
  31 template<typename I64, typename J64>
  32 inline bool ffs64(I64 input, J64 &out) {
  33   bool retval = false;
  34 #if defined(__x86_64__)
  35   asm volatile (
  36     "bsfq  %2, %1\n\t"   // bit scan forward
  37     "setnz %0\n\t":      // zero retval if input == 0
  38     "=r"(retval), "=r"(out):
  39     "r"(input):
  40     "cc"
  41   );
  42 #elif defined(__aarch64__)
  43   asm volatile (
  44     "rbit  %2, %2\n\t"  // reverse bits
  45     "clz   %1, %2\n\t"  // count leading zeros
  46     "cmp   %1, #64\n\t"
  47     "cset  %w0, NE":    // return (result != 64)
  48     "=r"(retval), "=r"(out), "+r"(input):
  49     :
  50     "cc"
  51   );
  52 #elif defined(__powerpc64__)
  53   // In PowerPC 64, bit 0 is the most significant
  54   asm volatile (
  55     "neg    %0, %2\n\t"     // 2-complement of input, using retval as temp
  56     "and    %0, %2, %0\n\t"
  57     "cntlzd %1, %0\n\t"     // count leading zeros (starting from index 0)
  58     "cmpdi  %1, 64\n\t"
  59     "li     %0, 1\n\t"      // using retval as temp
  60     "iseleq %0, 0, %0\n\t"  // (input == 0) ? 0 : 1
  61     "neg    %1, %1\n\t"
  62     "addi   %1, %1, 63\n\t":// 63 - amount of leading zeros -> position in LSB
  63     "+r"(retval), "=r"(out):// +r else %0 and %2 will be the same register
  64     "r"(input):
  65     "cr0"
  66   );
  67 #else
  68   out = folly::findFirstSet(input);
  69   retval = input != 0;
  70 #endif
  71   return retval;
  72 }
  73
  74 template<typename I64, typename J64>
  75 inline bool fls64(I64 input, J64 &out) {
  76   bool retval;
  77 #if defined(__x86_64__)
  78   asm volatile (
  79     "bsrq  %2, %1\n\t"   // bit scan reverse
  80     "setnz %0\n\t":      // zero retval if input == 0
  81     "=r"(retval), "=r"(out):
  82     "r"(input):
  83     "cc"
  84   );
  85 #elif defined(__aarch64__)
  86   asm volatile (
  87     "clz   %1, %2\n\t"      // count leading zeros
  88     "neg   %1, %1\n\t"
  89     "adds  %1, %1, #63\n\t" // result = 63 - (# of leading zeros)
  90                             // "s" suffix sets condition flags
  91     "cset  %w0, PL":        // return (result >= 0)
  92                             //   because result < 0 iff input == 0
  93     "=r"(retval), "=r"(out):
  94     "r"(input):
  95     "cc"
  96   );
  97 #elif defined(__powerpc64__)
  98   // In PowerPC 64, bit 0 is the most significant
  99   asm volatile (
 100     "cntlzd %1, %2\n\t"     // count leading zeros (starting from index 0)
 101     "cmpdi  %1, 64\n\t"
 102     "li     %0, 1\n\t"      // using retval as temp
 103     "iseleq %0, 0, %0\n\t"  // (input == 0) ? 0 : 1
 104     "neg    %1, %1\n\t"
 105     "addi   %1, %1, 63\n\t":// 63 - amount of leading zeros -> position in LSB
 106     "=r"(retval), "=r"(out):
 107     "r"(input):
 108     "cr0"
 109   );
 110 #else
 111   out = folly::findLastSet(input) - 1;
 112   retval = input != 0;
 113 #endif
 114   return retval;
 115 }
 116
 117 /*
 118  * Return the index (0..63) of the most significant bit in x.
 119  * x must be nonzero.
 120  */
 121 inline size_t fls64(size_t x) {
 122   assertx(x);
 123 #if defined(__x86_64__)
 124   size_t ret;
 125   __asm__ ("bsrq %1, %0"
 126            : "=r"(ret) // Outputs.
 127            : "r"(x)    // Inputs.
 128            );
 129   return ret;
 130 #elif defined(__powerpc64__)
 131   size_t ret;
 132   __asm__ ("cntlzd %0, %1"
 133            : "=r"(ret) // Outputs.
 134            : "r"(x)    // Inputs.
 135            );
 136   return 63 - ret;
 137 #elif defined(__aarch64__)
 138   size_t ret;
 139   __asm__ ("clz %x0, %x1"
 140            : "=r"(ret) // Outputs.
 141            : "r"(x)    // Inputs.
 142            );
 143   return 63 - ret;
 144 #else
 145   // Equivalent (but incompletely strength-reduced by gcc):
 146   return 63 - __builtin_clzl(x);
 147 #endif
 148 }
 149
 150 /*
 151  * Return the index (0..63) of the least significant bit in x.
 152  * x must be nonzero.
 153  */
 154 inline size_t ffs64(size_t x) {
 155   assertx(x);
 156 #if defined(__x86_64__)
 157   size_t ret;
 158   __asm__ ("bsfq %1, %0"
 159            : "=r"(ret) // Outputs.
 160            : "r"(x)    // Inputs.
 161            );
 162   return ret;
 163 #elif defined(__aarch64__)
 164   size_t ret;
 165   __asm__ ("rbit %0, %1\n\t"
 166            "clz %0, %0"
 167            : "=r"(ret) // Outputs.
 168            : "r"(x)    // Inputs.
 169            );
 170   return ret;
 171 #else
 172   return __builtin_ffsll(x) - 1;
 173 #endif
 174 }
 175
 176 inline void bitvec_set(uint64_t* bits, size_t index) {
 177 #if defined(__x86_64__)
 178   asm ("bts %1,%0" : "+m"(*bits) : "r"(index));
 179 #else
 180   bits[index / 64] |= 1ull << (index % 64);
 181 #endif
 182 }
 183
 184 inline void bitvec_clear(uint64_t* bits, size_t index) {
 185 #if defined(__x86_64__)
 186   asm ("btr %1,%0" : "+m"(*bits) : "r"(index));
 187 #else
 188   bits[index / 64] &= ~(1ull << (index % 64));
 189 #endif
 190 }
 191
 192 inline bool bitvec_test(const uint64_t* bits, size_t index) {
 193 #if defined(__x86_64__)
 194   bool b;
 195   asm ("bt %2,%1\n"
 196        "setc %0\n" : "=r"(b) : "m"(*bits), "r"(index));
 197   return b;
 198 #else
 199   return (bits[index / 64] & (1ull << (index % 64))) != 0;
 200 #endif
 201 }
 202
 203 } // HPHP
 204