nthbit.h revision dfd8b8327b93660601d016cdc6f29f433b45a8d8
19682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 29682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Licensed under the Apache License, Version 2.0 (the "License"); 39682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// you may not use this file except in compliance with the License. 49682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// You may obtain a copy of the License at 59682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 69682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// http://www.apache.org/licenses/LICENSE-2.0 79682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 89682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Unless required by applicable law or agreed to in writing, software 99682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// distributed under the License is distributed on an "AS IS" BASIS, 109682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 119682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// See the License for the specific language governing permissions and 129682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// limitations under the License. 139682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// 149682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Copyright 2005-2010 Google, Inc. 159682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// Author: sorenj@google.com (Jeffrey Sorensen) 169682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall// dr@google.com (Doug Rohde) 179682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 189682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#ifndef FST_EXTENSIONS_NGRAM_NTHBIT_H_ 199682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#define FST_EXTENSIONS_NGRAM_NTHBIT_H_ 209682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 219682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#include <fst/types.h> 229682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 239682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallextern uint32 nth_bit_bit_offset[]; 249682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 259682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hallinline uint32 nth_bit(uint64 v, uint32 r) { 269682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall uint32 shift = 0; 279682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall uint32 c = __builtin_popcount(v & 0xffffffff); 289682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall uint32 mask = -(r > c); 299682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall r -= c & mask; 309682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall shift += (32 & mask); 319682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 329682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall c = __builtin_popcount((v >> shift) & 0xffff); 339682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall mask = -(r > c); 349682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall r -= c & mask; 359682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall shift += (16 & mask); 369682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 379682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall c = __builtin_popcount((v >> shift) & 0xff); 389682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall mask = -(r > c); 399682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall r -= c & mask; 409682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall shift += (8 & mask); 419682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 429682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall return shift + ((nth_bit_bit_offset[(v >> shift) & 0xff] >> 439682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall ((r - 1) << 2)) & 0xf); 449682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall} 459682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall 469682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall#endif // FST_EXTENSIONS_NGRAM_NTHBIT_H_ 479682c8870b8ff5e4ac2e4c70b759f791c6f38c1fJesse Hall