1 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 // 14 // Copyright 2005-2010 Google, Inc. 15 // Author: sorenj (at) google.com (Jeffrey Sorensen) 16 // dr (at) google.com (Doug Rohde) 17 18 #ifndef FST_EXTENSIONS_NGRAM_NTHBIT_H_ 19 #define FST_EXTENSIONS_NGRAM_NTHBIT_H_ 20 21 #include <fst/types.h> 22 23 extern uint32 nth_bit_bit_offset[]; 24 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 + ((nth_bit_bit_offset[(v >> shift) & 0xff] >> 43 ((r - 1) << 2)) & 0xf); 44 } 45 46 #endif // FST_EXTENSIONS_NGRAM_NTHBIT_H_ 47
