1dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 2dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// Licensed under the Apache License, Version 2.0 (the "License"); 3dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// you may not use this file except in compliance with the License. 4dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// You may obtain a copy of the License at 5dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// 6dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// http://www.apache.org/licenses/LICENSE-2.0 7dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// 8dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// Unless required by applicable law or agreed to in writing, software 9dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// distributed under the License is distributed on an "AS IS" BASIS, 10dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// See the License for the specific language governing permissions and 12dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// limitations under the License. 13dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// 14dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// Copyright 2005-2010 Google, Inc. 15dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// Author: sorenj@google.com (Jeffrey Sorensen) 16dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin// dr@google.com (Doug Rohde) 17dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 18dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin#ifndef FST_EXTENSIONS_NGRAM_NTHBIT_H_ 19dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin#define FST_EXTENSIONS_NGRAM_NTHBIT_H_ 20dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 21dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin#include <fst/types.h> 22dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 23dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkinextern uint32 nth_bit_bit_offset[]; 24dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 25dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkininline uint32 nth_bit(uint64 v, uint32 r) { 26dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin uint32 shift = 0; 27dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin uint32 c = __builtin_popcount(v & 0xffffffff); 28dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin uint32 mask = -(r > c); 29dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin r -= c & mask; 30dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin shift += (32 & mask); 31dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 32dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin c = __builtin_popcount((v >> shift) & 0xffff); 33dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin mask = -(r > c); 34dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin r -= c & mask; 35dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin shift += (16 & mask); 36dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 37dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin c = __builtin_popcount((v >> shift) & 0xff); 38dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin mask = -(r > c); 39dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin r -= c & mask; 40dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin shift += (8 & mask); 41dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 42dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin return shift + ((nth_bit_bit_offset[(v >> shift) & 0xff] >> 43dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin ((r - 1) << 2)) & 0xf); 44dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin} 45dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin 46dfd8b8327b93660601d016cdc6f29f433b45a8d8Alexander Gutkin#endif // FST_EXTENSIONS_NGRAM_NTHBIT_H_ 47