FST  openfst-1.7.2 OpenFst Library
nthbit.h
Go to the documentation of this file.
1 // See www.openfst.org for extensive documentation on this weighted
2 // finite-state transducer library.
3
4 #ifndef FST_EXTENSIONS_NGRAM_NTHBIT_H_
5 #define FST_EXTENSIONS_NGRAM_NTHBIT_H_
6
7 #include <fst/types.h>
8
9 #ifdef __BMI2__
10 // PDEP requires BMI2.
11
12 // Returns the position (0-63) of the r-th 1 bit in v.
13 // 1 <= r <= CountOnes(v) <= 64. Therefore, v must not be 0.
14 inline uint32 nth_bit(uint64 v, uint32 r) {
15  // PDEP example from https://stackoverflow.com/a/27453505
16  return __builtin_ctzll(_pdep_u64(uint64{1} << (r - 1), v));
17 }
18
19 #else // !defined(__BMI2__)
20
21 extern const uint32 nth_bit_bit_offset[];
22
23 // Returns the position (0-63) of the r-th 1 bit in v.
24 // 1 <= r <= CountOnes(v) <= 64. Therefore, v must not be 0.
25 inline uint32 nth_bit(uint64 v, uint32 r) {
26  uint32 shift = 0;
27  uint32 c = __builtin_popcount(v & 0xffffffff);
28  uint32 mask = -(r > c);
29  r -= c & mask;
30  shift += (32 & mask);
31
32  c = __builtin_popcount((v >> shift) & 0xffff);
33  mask = -(r > c);
34  r -= c & mask;
35  shift += (16 & mask);
36
37  c = __builtin_popcount((v >> shift) & 0xff);
38  mask = -(r > c);
39  r -= c & mask;
40  shift += (8 & mask);
41
42  return shift +
43  ((nth_bit_bit_offset[(v >> shift) & 0xff] >> ((r - 1) << 2)) & 0xf);
44 }
45
46 #endif // !defined(__BMI2__)
47
48 #endif // FST_EXTENSIONS_NGRAM_NTHBIT_H_
uint32 nth_bit(uint64 v, uint32 r)
Definition: nthbit.h:25
uint64_t uint64
Definition: types.h:32
const uint32 nth_bit_bit_offset[]
Definition: nthbit.cc:29
uint32_t uint32
Definition: types.h:31