1                 : /*
       2                 :  * Copyright (c) 2012 The Native Client Authors. All rights reserved.
       3                 :  * Use of this source code is governed by a BSD-style license that can be
       4                 :  * found in the LICENSE file.
       5                 :  */
       6                 : 
       7                 : #ifndef NATIVE_CLIENT_SRC_INCLUDE_PORTABILITY_BITS_H_
       8                 : #define NATIVE_CLIENT_SRC_INCLUDE_PORTABILITY_BITS_H_ 1
       9                 : 
      10                 : /*
      11                 :  * Portable bit functions.
      12                 :  *
      13                 :  * Not all platforms offer fast intrinsics for these functions, and some
      14                 :  * compilers require checking CPUID at runtime before using the intrinsic.
      15                 :  *
      16                 :  * We instead use portable and reasonably-fast implementations, while
      17                 :  * avoiding implementations with large lookup tables.
      18                 :  *
      19                 :  * When adding functions, also add tests in:
      20                 :  *   tests/unittests/trusted/bits/bits_test.cc
      21                 :  */
      22                 : 
      23                 : #include "native_client/src/include/portability.h"
      24                 : #include "native_client/src/include/nacl_compiler_annotations.h"
      25                 : #include "native_client/src/include/nacl_macros.h"
      26                 : 
      27                 : namespace nacl {
      28                 : 
      29                 : // Only the specialized templates should be instantiated, getting
      30                 : // a linker error with these functions means an unsupported type was used.
      31                 : 
      32                 : template<typename T> INLINE int PopCount(T /* v */);
      33                 : template<typename T> INLINE T BitReverse(T /* v */);
      34                 : template<typename T> INLINE int CountTrailingZeroes(T /* v */);
      35                 : template<typename T> INLINE int CountLeadingZeroes(T /* v */);
      36                 : 
      37                 : // Implementations for the above templates.
      38                 : 
      39               1 : template<> INLINE int PopCount<uint8_t>(uint8_t v) {
      40                 :   // Small table lookup.
      41                 :   static const uint8_t tbl[32] = {
      42                 :     0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
      43                 :     1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5
      44                 :   };
      45               1 :   return tbl[v & 0xf] + tbl[v >> 4];
      46               1 : }
      47               1 : template<> INLINE int PopCount<uint16_t>(uint16_t v) {
      48               1 :   return PopCount<uint8_t>(v & 0xff) + PopCount<uint8_t>(v >> 8);
      49               1 : }
      50               1 : template<> INLINE int PopCount<uint32_t>(uint32_t v) {
      51                 :   // See Stanford bithacks, counting bits set in parallel, "best method":
      52                 :   // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
      53               1 :   v = v - ((v >> 1) & 0x55555555);
      54               1 :   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
      55               1 :   return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
      56               1 : }
      57               1 : template<> INLINE int PopCount<uint64_t>(uint64_t v) {
      58               1 :   return PopCount<uint32_t>((uint32_t)v) + PopCount<uint32_t>(v >> 32);
      59               1 : }
      60                 : 
      61               1 : template<> INLINE uint32_t BitReverse<uint32_t>(uint32_t v) {
      62                 :   // See Hacker's Delight, first edition, figure 7-1.
      63               1 :   v = ((v & 0x55555555) << 1) | ((v >> 1) & 0x55555555);
      64               1 :   v = ((v & 0x33333333) << 2) | ((v >> 2) & 0x33333333);
      65               1 :   v = ((v & 0x0F0F0F0F) << 4) | ((v >> 4) & 0x0F0F0F0F);
      66                 :   v = (v << 24) | ((v & 0xFF00) << 8) |
      67               1 :       ((v >> 8) & 0xFF00) | (v >> 24);
      68               1 :   return v;
      69               1 : }
      70                 : 
      71               1 : template<> INLINE int CountTrailingZeroes<uint32_t>(uint32_t v) {
      72                 :   // See Stanford bithacks, count the consecutive zero bits (trailing) on the
      73                 :   // right with multiply and lookup:
      74                 :   // http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup
      75                 :   static const uint8_t tbl[32] = {
      76                 :     0,   1, 28,  2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17,  4, 8,
      77                 :     31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18,  6, 11,  5, 10, 9
      78                 :   };
      79                 :   return v ?
      80                 :       (int)tbl[((uint32_t)((v & -(int32_t)v) * 0x077CB531U)) >> 27] :
      81               1 :       -1;
      82               1 : }
      83                 : 
      84               1 : template<> INLINE int CountLeadingZeroes<uint32_t>(uint32_t v) {
      85                 :   // See Stanford bithacks, find the log base 2 of an N-bit integer in
      86                 :   // O(lg(N)) operations with multiply and lookup:
      87                 :   // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
      88                 :   static const uint8_t tbl[32] = {
      89                 :     31, 22, 30, 21, 18, 10, 29,  2, 20, 17, 15, 13, 9,  6, 28, 1,
      90                 :     23, 19, 11,  3, 16, 14,  7, 24, 12,  4,  8, 25, 5, 26, 27, 0
      91                 :   };
      92               1 :   v = v | (v >>  1);
      93               1 :   v = v | (v >>  2);
      94               1 :   v = v | (v >>  4);
      95               1 :   v = v | (v >>  8);
      96               1 :   v = v | (v >> 16);
      97                 :   return v ?
      98                 :       (int)tbl[((uint32_t)(v * 0x07C4ACDDU)) >> 27] :
      99               1 :       -1;
     100               1 : }
     101                 : 
     102                 : }  // namespace nacl
     103                 : 
     104                 : #endif  /* NATIVE_CLIENT_SRC_INCLUDE_PORTABILITY_BITS_H_ */