FST  openfst-1.8.3
OpenFst Library
nthbit.cc
Go to the documentation of this file.
1 // Copyright 2005-2024 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the 'License');
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an 'AS IS' BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 
18 #include <fst/extensions/ngram/nthbit.h>
19 
20 #include <cstdint>
21 
22 
23 namespace fst {
24 
25 #if !defined(__BMI2__) // BMI2 has everything in the header
26 #if SIZE_MAX == UINT32_MAX
27 
28 // 32-bit platforms will be slow when using 64-bit operations; use this
29 // table-based version instead. This only contains constant shifts, which
30 // have been benchmarked to be fast.
31 
32 // These tables were generated using:
33 //
34 // uint32_t nth_bit_scan(uint64_t v, uint32_t r) {
35 // for (int i = 0; i < 64; ++i) {
36 // if ((r -= v & 1) == 0) return i;
37 // v >>= 1;
38 // }
39 // return -1;
40 // }
41 //
42 // printf("static const uint8_t nth_bit_bit_count[256] = {\n");
43 // for (size_t i = 0; i < 256; ++i) {
44 // printf("%d, ", __builtin_popcount(i));
45 // if (i % 16 == 15) printf("\n");
46 // }
47 // printf("};\n");
48 //
49 // printf("static const uint8_t nth_bit_bit_pos[8][256] = {{\n");
50 // for (size_t j = 0; j < 8; ++j) {
51 // for (size_t i = 0; i < 256; ++i) {
52 // uint8_t pos = nth_bit_scan(i, j);
53 // printf("%d, ", pos);
54 // if (i % 16 == 15) printf("\n");
55 // }
56 // if (j != 7) printf("}, {\n");
57 // }
58 // printf("}};\n");
59 //
60 // This table contains the popcount of 1-byte values:
61 // nth_bit_bit_count[v] == __builtin_popcount(v).
62 static const uint8_t nth_bit_bit_count[256] = {
63  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
64  2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
65  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
66  2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
67  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
68  4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
69  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
70  3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
71  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
72  4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
73  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
74 };
75 
76 // This table contains the bit position of the r-th set bit in v, for 1-byte v,
77 // (or 255 if there are fewer than r bits set, but those values are never used):
78 // nth_bit_bit_pos[r][v] == nth_bit_scan(v, r).
79 static const uint8_t nth_bit_bit_pos[8][256] = {
80  {
81  255, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0,
82  1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
83  2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0,
84  1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
85  3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
86  1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0,
87  2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,
88  1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
89  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0,
90  1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
91  2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0,
92  1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
93  },
94  {
95  255, 255, 255, 1, 255, 2, 2, 1, 255, 3, 3, 1, 3, 2, 2, 1, 255, 4,
96  4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 255, 5, 5, 1,
97  5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2,
98  2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 255, 6, 6, 1, 6, 2, 2, 1,
99  6, 3, 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1, 4, 3,
100  3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1,
101  3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2,
102  2, 1, 255, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
103  7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 7, 5,
104  5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1, 5, 4, 4, 1,
105  4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1, 7, 6, 6, 1, 6, 2,
106  2, 1, 6, 3, 3, 1, 3, 2, 2, 1, 6, 4, 4, 1, 4, 2, 2, 1,
107  4, 3, 3, 1, 3, 2, 2, 1, 6, 5, 5, 1, 5, 2, 2, 1, 5, 3,
108  3, 1, 3, 2, 2, 1, 5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1,
109  3, 2, 2, 1,
110  },
111  {
112  255, 255, 255, 255, 255, 255, 255, 2, 255, 255, 255, 3, 255, 3, 3, 2,
113  255, 255, 255, 4, 255, 4, 4, 2, 255, 4, 4, 3, 4, 3, 3, 2,
114  255, 255, 255, 5, 255, 5, 5, 2, 255, 5, 5, 3, 5, 3, 3, 2,
115  255, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
116  255, 255, 255, 6, 255, 6, 6, 2, 255, 6, 6, 3, 6, 3, 3, 2,
117  255, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
118  255, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
119  6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
120  255, 255, 255, 7, 255, 7, 7, 2, 255, 7, 7, 3, 7, 3, 3, 2,
121  255, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
122  255, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
123  7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
124  255, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
125  7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
126  7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
127  6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
128  },
129  {
130  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
131  255, 3, 255, 255, 255, 255, 255, 255, 255, 4, 255, 255, 255, 4,
132  255, 4, 4, 3, 255, 255, 255, 255, 255, 255, 255, 5, 255, 255,
133  255, 5, 255, 5, 5, 3, 255, 255, 255, 5, 255, 5, 5, 4,
134  255, 5, 5, 4, 5, 4, 4, 3, 255, 255, 255, 255, 255, 255,
135  255, 6, 255, 255, 255, 6, 255, 6, 6, 3, 255, 255, 255, 6,
136  255, 6, 6, 4, 255, 6, 6, 4, 6, 4, 4, 3, 255, 255,
137  255, 6, 255, 6, 6, 5, 255, 6, 6, 5, 6, 5, 5, 3,
138  255, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4,
139  4, 3, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 7,
140  255, 7, 7, 3, 255, 255, 255, 7, 255, 7, 7, 4, 255, 7,
141  7, 4, 7, 4, 4, 3, 255, 255, 255, 7, 255, 7, 7, 5,
142  255, 7, 7, 5, 7, 5, 5, 3, 255, 7, 7, 5, 7, 5,
143  5, 4, 7, 5, 5, 4, 5, 4, 4, 3, 255, 255, 255, 7,
144  255, 7, 7, 6, 255, 7, 7, 6, 7, 6, 6, 3, 255, 7,
145  7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
146  255, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5,
147  5, 3, 7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4,
148  5, 4, 4, 3,
149  },
150  {
151  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
152  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
153  255, 255, 255, 4, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
154  255, 255, 255, 255, 255, 5, 255, 255, 255, 255, 255, 255, 255, 5,
155  255, 255, 255, 5, 255, 5, 5, 4, 255, 255, 255, 255, 255, 255,
156  255, 255, 255, 255, 255, 255, 255, 255, 255, 6, 255, 255, 255, 255,
157  255, 255, 255, 6, 255, 255, 255, 6, 255, 6, 6, 4, 255, 255,
158  255, 255, 255, 255, 255, 6, 255, 255, 255, 6, 255, 6, 6, 5,
159  255, 255, 255, 6, 255, 6, 6, 5, 255, 6, 6, 5, 6, 5,
160  5, 4, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
161  255, 255, 255, 7, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255,
162  255, 7, 255, 7, 7, 4, 255, 255, 255, 255, 255, 255, 255, 7,
163  255, 255, 255, 7, 255, 7, 7, 5, 255, 255, 255, 7, 255, 7,
164  7, 5, 255, 7, 7, 5, 7, 5, 5, 4, 255, 255, 255, 255,
165  255, 255, 255, 7, 255, 255, 255, 7, 255, 7, 7, 6, 255, 255,
166  255, 7, 255, 7, 7, 6, 255, 7, 7, 6, 7, 6, 6, 4,
167  255, 255, 255, 7, 255, 7, 7, 6, 255, 7, 7, 6, 7, 6,
168  6, 5, 255, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5,
169  6, 5, 5, 4,
170  },
171  {
172  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
173  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
174  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
175  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
176  255, 255, 255, 255, 255, 255, 255, 5, 255, 255, 255, 255, 255, 255,
177  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
178  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 6, 255, 255,
179  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 6,
180  255, 255, 255, 255, 255, 255, 255, 6, 255, 255, 255, 6, 255, 6,
181  6, 5, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
182  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
183  255, 255, 255, 255, 255, 7, 255, 255, 255, 255, 255, 255, 255, 255,
184  255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 255, 255, 255,
185  255, 7, 255, 255, 255, 7, 255, 7, 7, 5, 255, 255, 255, 255,
186  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255,
187  255, 255, 255, 255, 255, 7, 255, 255, 255, 7, 255, 7, 7, 6,
188  255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 7, 255, 7,
189  7, 6, 255, 255, 255, 7, 255, 7, 7, 6, 255, 7, 7, 6,
190  7, 6, 6, 5,
191  },
192  {
193  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
194  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
195  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
196  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
197  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
198  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
199  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
200  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
201  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
202  255, 6, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
203  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
204  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
205  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
206  255, 255, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 255,
207  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
208  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 7,
209  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
210  255, 7, 255, 255, 255, 255, 255, 255, 255, 7, 255, 255, 255, 7,
211  255, 7, 7, 6,
212  },
213  {
214  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
215  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
216  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
217  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
218  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
219  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
220  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
221  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
222  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
223  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
224  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
225  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
226  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
227  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
228  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
229  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
230  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
231  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
232  255, 255, 255, 7,
233  }};
234 
235 int nth_bit(const uint64_t v, uint32_t r) {
236  DCHECK_NE(v, 0);
237  DCHECK_LE(0, r);
238  DCHECK_LT(r, __builtin_popcountll(v));
239 
240  uint32_t next_byte = v & 255;
241  uint32_t byte_popcount = nth_bit_bit_count[next_byte];
242  if (r < byte_popcount) return nth_bit_bit_pos[r][next_byte];
243  r -= byte_popcount;
244  next_byte = (v >> 8) & 255;
245  byte_popcount = nth_bit_bit_count[next_byte];
246  if (r < byte_popcount) return 8 + nth_bit_bit_pos[r][next_byte];
247  r -= byte_popcount;
248  next_byte = (v >> 16) & 255;
249  byte_popcount = nth_bit_bit_count[next_byte];
250  if (r < byte_popcount) return 16 + nth_bit_bit_pos[r][next_byte];
251  r -= byte_popcount;
252  next_byte = (v >> 24) & 255;
253  byte_popcount = nth_bit_bit_count[next_byte];
254  if (r < byte_popcount) return 24 + nth_bit_bit_pos[r][next_byte];
255  r -= byte_popcount;
256  next_byte = (v >> 32) & 255;
257  byte_popcount = nth_bit_bit_count[next_byte];
258  if (r < byte_popcount) return 32 + nth_bit_bit_pos[r][next_byte];
259  r -= byte_popcount;
260  next_byte = (v >> 40) & 255;
261  byte_popcount = nth_bit_bit_count[next_byte];
262  if (r < byte_popcount) return 40 + nth_bit_bit_pos[r][next_byte];
263  r -= byte_popcount;
264  next_byte = (v >> 48) & 255;
265  byte_popcount = nth_bit_bit_count[next_byte];
266  if (r < byte_popcount) return 48 + nth_bit_bit_pos[r][next_byte];
267  r -= byte_popcount;
268  next_byte = (v >> 56) & 255;
269  byte_popcount = nth_bit_bit_count[next_byte];
270  if (r < byte_popcount) return 56 + nth_bit_bit_pos[r][next_byte];
271  return -1;
272 }
273 
274 #elif SIZE_MAX == UINT64_MAX // 64-bit, non-BMI2
275 // This table is generated using:
276 //
277 // printf("const uint8_t kSelectInByte[8 * 256] = {\n");
278 // for (int j = 0; j < 8; ++j) {
279 // for (int i = 0; i < 256; ++i) {
280 // if (i > 0) printf(" ");
281 // if (i % 16 == 0) printf("\n ");
282 // const int k = findbitn(i, j);
283 // printf("%d,", k == -1 ? 0 : k);
284 // }
285 // printf("\n");
286 // }
287 // printf("};\n");
288 //
289 namespace internal {
290 
291 const uint8_t kSelectInByte[8 * 256] = {
292  0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
293  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
294  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
295  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
296  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
297  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
298  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
299  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
300  7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
301  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
302  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
303  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
304  6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
305  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
306  5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
307  4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
308 
309  0, 0, 0, 1, 0, 2, 2, 1, 0, 3, 3, 1, 3, 2, 2, 1,
310  0, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
311  0, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
312  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
313  0, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
314  6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
315  6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
316  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
317  0, 7, 7, 1, 7, 2, 2, 1, 7, 3, 3, 1, 3, 2, 2, 1,
318  7, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
319  7, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
320  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
321  7, 6, 6, 1, 6, 2, 2, 1, 6, 3, 3, 1, 3, 2, 2, 1,
322  6, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
323  6, 5, 5, 1, 5, 2, 2, 1, 5, 3, 3, 1, 3, 2, 2, 1,
324  5, 4, 4, 1, 4, 2, 2, 1, 4, 3, 3, 1, 3, 2, 2, 1,
325 
326  0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 3, 3, 2,
327  0, 0, 0, 4, 0, 4, 4, 2, 0, 4, 4, 3, 4, 3, 3, 2,
328  0, 0, 0, 5, 0, 5, 5, 2, 0, 5, 5, 3, 5, 3, 3, 2,
329  0, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
330  0, 0, 0, 6, 0, 6, 6, 2, 0, 6, 6, 3, 6, 3, 3, 2,
331  0, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
332  0, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
333  6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
334  0, 0, 0, 7, 0, 7, 7, 2, 0, 7, 7, 3, 7, 3, 3, 2,
335  0, 7, 7, 4, 7, 4, 4, 2, 7, 4, 4, 3, 4, 3, 3, 2,
336  0, 7, 7, 5, 7, 5, 5, 2, 7, 5, 5, 3, 5, 3, 3, 2,
337  7, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
338  0, 7, 7, 6, 7, 6, 6, 2, 7, 6, 6, 3, 6, 3, 3, 2,
339  7, 6, 6, 4, 6, 4, 4, 2, 6, 4, 4, 3, 4, 3, 3, 2,
340  7, 6, 6, 5, 6, 5, 5, 2, 6, 5, 5, 3, 5, 3, 3, 2,
341  6, 5, 5, 4, 5, 4, 4, 2, 5, 4, 4, 3, 4, 3, 3, 2,
342 
343  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3,
344  0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 4, 0, 4, 4, 3,
345  0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 3,
346  0, 0, 0, 5, 0, 5, 5, 4, 0, 5, 5, 4, 5, 4, 4, 3,
347  0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 3,
348  0, 0, 0, 6, 0, 6, 6, 4, 0, 6, 6, 4, 6, 4, 4, 3,
349  0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5, 3,
350  0, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
351  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 3,
352  0, 0, 0, 7, 0, 7, 7, 4, 0, 7, 7, 4, 7, 4, 4, 3,
353  0, 0, 0, 7, 0, 7, 7, 5, 0, 7, 7, 5, 7, 5, 5, 3,
354  0, 7, 7, 5, 7, 5, 5, 4, 7, 5, 5, 4, 5, 4, 4, 3,
355  0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 3,
356  0, 7, 7, 6, 7, 6, 6, 4, 7, 6, 6, 4, 6, 4, 4, 3,
357  0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 3,
358  7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
359 
360  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
361  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4,
362  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
363  0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 5, 0, 5, 5, 4,
364  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
365  0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 4,
366  0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 5,
367  0, 0, 0, 6, 0, 6, 6, 5, 0, 6, 6, 5, 6, 5, 5, 4,
368  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
369  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 4,
370  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 5,
371  0, 0, 0, 7, 0, 7, 7, 5, 0, 7, 7, 5, 7, 5, 5, 4,
372  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
373  0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 4,
374  0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5,
375  0, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
376 
377  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
378  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
379  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
380  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5,
381  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
382  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
383  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
384  0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 6, 0, 6, 6, 5,
385  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
386  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
387  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
388  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 5,
389  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
390  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
391  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
392  0, 0, 0, 7, 0, 7, 7, 6, 0, 7, 7, 6, 7, 6, 6, 5,
393 
394  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
395  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
396  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
397  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
398  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
399  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
400  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
401  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6,
402  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
403  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
404  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
405  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
406  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
407  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
408  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7,
409  0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 7, 0, 7, 7, 6,
410 
411  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
412  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
413  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
414  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
415  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
416  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
417  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
418  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
419  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
420  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
421  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
422  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
423  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
424  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
425  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
426  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7
427 };
428 // clang-format on
429 
430 } // namespace internal
431 #endif // 64-bit, non-BMI2
432 #endif // !defined(__BMI2__)
433 
434 } // namespace fst
DCHECK_LT
#define DCHECK_LT(x, y)
Definition: log.h:76
DCHECK_LE
#define DCHECK_LE(x, y)
Definition: log.h:78
DCHECK_NE
#define DCHECK_NE(x, y)
Definition: log.h:80
fst::nth_bit
int nth_bit(const uint64_t v, uint32_t r)
Definition: nthbit.cc:235
Generated by   doxygen 1.8.11