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@google.com (Jeffrey Sorensen) 16// dr@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 23extern uint32 nth_bit_bit_offset[]; 24 25inline 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