1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2018, Knut Reinert, FU Berlin
5 // Copyright (c) 2013 NVIDIA Corporation
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions are met:
10 //
11 // * Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // * Redistributions in binary form must reproduce the above copyright
14 // notice, this list of conditions and the following disclaimer in the
15 // documentation and/or other materials provided with the distribution.
16 // * Neither the name of Knut Reinert or the FU Berlin nor the names of
17 // its contributors may be used to endorse or promote products derived
18 // from this software without specific prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
24 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
27 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
30 // DAMAGE.
31 //
32 // ==========================================================================
33 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>
34 // ==========================================================================
35 // Various useful bit-twiddling routines, mostly taken from the website
36 // https://graphics.stanford.edu/~seander/bithacks.html
37 // ==========================================================================
38
39 #ifndef SEQAN_MISC_BIT_TWIDDLING_H_
40 #define SEQAN_MISC_BIT_TWIDDLING_H_
41
42 #ifdef STDLIB_VS
43
44 // Make intrinsics visible. It appears that this is not necessary with VS 10
45 // any more, for VS 9, it must be included.
46 #include <intrin.h>
47
48 #ifdef __SSE4_2__
49 #include <nmmintrin.h>
50 #endif
51
52 #endif // #ifdef STDLIB_VS
53
54 // TODO(holtgrew): Test this!
55
56 namespace seqan {
57
58 // ============================================================================
59 // Forwards
60 // ============================================================================
61
62 template <typename TWord>
63 struct SimdVectorConcept;
64
65 // ============================================================================
66 // Classes, Structs, Enums, Tags
67 // ============================================================================
68
69 // DeBruijn sequence for 64 bit bitScanReverse.
70 static const int DeBruijnMultiplyLookupBSR64[64] =
71 {
72 0, 47, 1, 56, 48, 27, 2, 60,
73 57, 49, 41, 37, 28, 16, 3, 61,
74 54, 58, 35, 52, 50, 42, 21, 44,
75 38, 32, 29, 23, 17, 11, 4, 62,
76 46, 55, 26, 59, 40, 36, 15, 53,
77 34, 51, 20, 43, 31, 22, 10, 45,
78 25, 39, 14, 33, 19, 30, 9, 24,
79 13, 18, 8, 12, 7, 6, 5, 63
80 };
81
82 // DeBruijn sequence for 64 bit bitScanForward.
83 static const int DeBruijnMultiplyLookupBSF64[64] =
84 {
85 0, 1, 48, 2, 57, 49, 28, 3,
86 61, 58, 50, 42, 38, 29, 17, 4,
87 62, 55, 59, 36, 53, 51, 43, 22,
88 45, 39, 33, 30, 24, 18, 12, 5,
89 63, 47, 56, 27, 60, 41, 37, 16,
90 54, 35, 52, 21, 44, 32, 23, 11,
91 46, 26, 40, 15, 34, 20, 31, 10,
92 25, 14, 19, 9, 13, 8, 7, 6
93 };
94
95 // DeBruijn sequence for 32 bit bitScanForward and bitScanReverse.
96 static const int DeBruijnMultiplyLookup[32] =
97 {
98 0, 1, 28, 2, 29, 14, 24, 3,
99 30, 22, 20, 15, 25, 17, 4, 8,
100 31, 27, 13, 23, 21, 19, 16, 7,
101 26, 12, 18, 6, 11, 5, 10, 9
102 };
103
104 // ----------------------------------------------------------------------------
105 // Tag WordSize_
106 // ----------------------------------------------------------------------------
107 // This parametrized tag is used for selecting a _popCountImpl() implementation.
108
109 template <unsigned int NUM_BITS>
110 struct WordSize_ {};
111
112 // ============================================================================
113 // Functions
114 // ============================================================================
115
116 // ----------------------------------------------------------------------------
117 // Function setBitTo()
118 // ----------------------------------------------------------------------------
119
120 /*!
121 * @fn setBitTo
122 * @headerfile <seqan/misc/bit_twiddling.h>
123 * @brief Set the bit with the given index to the given value.
124 *
125 * @signature void setBitTo(word, index, value);
126 *
127 * @param[in,out] word The machine word (number) to set bits of (@link IntegerConcept @endlink).
128 * @param[in] index The index of the bit in the word to set (@link IntegerConcept @endlink).
129 * @param[in] value The value to set to, <tt>bool</tt>.
130 */
131
132 template <typename TWord, typename TPos>
133 inline void
setBitTo(TWord & word,TPos index,bool value)134 setBitTo(TWord & word, TPos index, bool value)
135 {
136 // See http://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching
137 word = (word & ~(1u << index)) | (-value & (1u << index));
138 }
139
140 // ----------------------------------------------------------------------------
141 // Function setBit()
142 // ----------------------------------------------------------------------------
143
144 /*!
145 * @fn setBit
146 * @headerfile <seqan/misc/bit_twiddling.h>
147 * @brief Set the bit with the given index to 1.
148 *
149 * @signature void setBit(word, index);
150 *
151 * @param[in,out] word The word to set the bit of (@link IntegerConcept @endlink).
152 * @param[in] index The index of the bit to set (@link IntegerConcept @endlink).
153 */
154
155 template <typename TWord, typename TPos>
156 inline void
setBit(TWord & word,TPos index)157 setBit(TWord & word, TPos index)
158 {
159 word |= (1u << index);
160 }
161
162 // ----------------------------------------------------------------------------
163 // Function clearBit()
164 // ----------------------------------------------------------------------------
165
166 /*!
167 * @fn clearBit
168 * @headerfile <seqan/misc/bit_twiddling.h>
169 * @brief Set the bit with the given index to 0.
170 *
171 * @signature void clearBit(word, index);
172 *
173 * @param[in,out] word The machine word to set the bit of (@link IntegerConcept @endlink).
174 * @param[in] index The index of the bit to set to 0 (@link IntegerConcept @endlink).
175 */
176
177 template <typename TWord, typename TPos>
178 inline void
clearBit(TWord & word,TPos index)179 clearBit(TWord & word, TPos index)
180 {
181 word &= ~(1u << index);
182 }
183
184 // ----------------------------------------------------------------------------
185 // Function clearAllBits()
186 // ----------------------------------------------------------------------------
187
188 /*!
189 * @fn clearAllBits
190 * @headerfile <seqan/misc/bit_twiddling.h>
191 * @brief Set all bits to 0.
192 *
193 * @signature void clearAllBits(word);
194 *
195 * @param[in,out] word The word to clear all bits of (@link IntegerConcept @endlink).
196 */
197
198 template <typename TWord>
199 inline void
clearBits(TWord & word)200 clearBits(TWord & word)
201 {
202 word = 0;
203 }
204
205 // ----------------------------------------------------------------------------
206 // Function isBitSet()
207 // ----------------------------------------------------------------------------
208
209 /*!
210 * @fn isBitSet
211 * @headerfile <seqan/misc/bit_twiddling.h>
212 * @brief Returns whether the bit with the given index is set to 1.
213 *
214 * @signature bool isBitSet(word, index);
215 *
216 * @param[in] word The word to check (@link IntegerConcept @endlink).
217 * @param[in] index The index of the bit to check (@link IntegerConcept @endlink).
218 *
219 * @return bool Whether the bit with the given index is set in <tt>word</tt>.
220 */
221
222 template <typename TWord, typename TIndex>
223 inline bool
isBitSet(TWord word,TIndex index)224 isBitSet(TWord word, TIndex index)
225 {
226 typedef typename MakeUnsigned<TWord>::Type TUnsignedWord;
227 return (word & (TUnsignedWord(1) << index)) != static_cast<TWord>(0);
228 }
229
230 // ----------------------------------------------------------------------------
231 // Function hiBits()
232 // ----------------------------------------------------------------------------
233
234 template <typename TWord, typename TPos>
235 inline TWord
hiBits(TWord word,TPos index)236 hiBits(TWord word, TPos index)
237 {
238 return word & ~((TWord(1) << (BitsPerValue<TWord>::VALUE - index)) - TWord(1));
239 }
240
241 // ----------------------------------------------------------------------------
242 // Function popCount()
243 // ----------------------------------------------------------------------------
244 // The compiler-dependent implementations of _popCountImpl() follow.
245
246 /*!
247 * @fn popCount
248 * @headerfile <seqan/misc/bit_twiddling.h>
249 * @brief Returns number of set bits in an integer.
250 *
251 * @signature unsigned popCount(words);
252 *
253 * @param[in] word The word to count the number of set bits of (@link IntegerConcept @endlink).
254 *
255 * @return unsigned The number of set bits in <tt>word</tt>.
256 */
257
258 template <typename TWord>
259 inline unsigned
popCount(TWord word)260 popCount(TWord word)
261 {
262 return _popCountImpl(word, WordSize_<BitsPerValue<TWord>::VALUE>());
263 }
264
265 // Implementing this platform-independent is tricky. There are two points to platform independentness. First, the
266 // choice of compiler and second the used CPU. Currently, we do not perform any checks for the CPU and assume that
267 // the Intel intrinsic POPCNT is available. The function is implemented to work on the supported compilers GCC/MINGW,
268 // CLANG (which has the same interface as GCC here) and Visual C++.
269 //
270 // GCC, MINGW and CLANG provide the intrinsics __builtin_popcount, __builtin_popcountl, and __builtin_popcountll for
271 // the types unsigned, unsigned long, and unsigned long long. Starting with version 2008, Visual C++ provides the
272 // intrinsics __popcnt16, __popcnt, and __popcnt64 for 16, 32, and 64 bit words.
273
274 // MSVC >= 2008, has intrinsic
275 #if defined(COMPILER_MSVC) || defined(COMPILER_WINTEL)
276
277 // ----------------------------------------------------------------------------
278 // Function _popCountImpl()
279 // ----------------------------------------------------------------------------
280 // MSVC implementations.
281
282 template <typename TWord>
283 inline unsigned
_popCountImpl(TWord word,WordSize_<64> const &)284 _popCountImpl(TWord word, WordSize_<64> const & /*tag*/)
285 {
286 #if defined(_WIN64)
287
288 #if defined(__SSE4_2__)
289 // 64-bit Windows, SSE4.2 bit intrinsic available
290 return _mm_popcnt_u64(static_cast<uint64_t>(word));
291 #elif defined(COMPILER_WINTEL)
292 return _popcnt64(static_cast<uint64_t>(word));
293 #else
294 // 64-bit Windows, 64 bit intrinsic available
295 return __popcnt64(static_cast<uint64_t>(word));
296 #endif
297
298 #else // #if defined(_WIN64)
299
300 // 32-bit Windows, 64 bit intrinsic not available
301 return _popCountImpl(static_cast<const uint32_t>(word), WordSize_<32>())
302 + _popCountImpl(static_cast<const uint32_t>(word >> 32), WordSize_<32>());
303
304 #endif // #if defined(_WIN64)
305 }
306
307 template <typename TWord>
308 inline unsigned
_popCountImpl(TWord word,WordSize_<32> const &)309 _popCountImpl(TWord word, WordSize_<32> const & /*tag*/)
310 {
311 #if defined(__SSE4_2__)
312 // SSE4.2 bit intrinsic available
313 return _mm_popcnt_u32(static_cast<uint32_t>(word));
314 #elif defined(COMPILER_WINTEL)
315 return _popcnt32(static_cast<uint32_t>(word));
316 #else
317 return __popcnt(static_cast<uint32_t>(word));
318 #endif
319 }
320
321 template <typename TWord>
322 inline unsigned
_popCountImpl(TWord word,WordSize_<16> const &)323 _popCountImpl(TWord word, WordSize_<16> const & /*tag*/)
324 {
325 return __popcnt16(static_cast<uint16_t>(word));
326 }
327
328 template <typename TWord>
329 inline unsigned
_popCountImpl(TWord word,WordSize_<8> const &)330 _popCountImpl(TWord word, WordSize_<8> const & /*tag*/)
331 {
332 return _popCountImpl(static_cast<const uint16_t>(word), WordSize_<16>());
333 }
334
335 // GCC or CLANG
336 #elif !(defined(COMPILER_MSVC) || defined(COMPILER_WINTEL))
337
338 // ----------------------------------------------------------------------------
339 // Function _popCountImpl()
340 // ----------------------------------------------------------------------------
341 // GCC or CLANG implementations.
342 // SSE4.2 popcnt is emitted when compiling with -mpopcnt or -march=corei7
343
344 template <typename TWord>
345 inline unsigned
_popCountImpl(TWord word,WordSize_<64> const &)346 _popCountImpl(TWord word, WordSize_<64> const & /*tag*/)
347 {
348 return __builtin_popcountll(static_cast<uint64_t>(word));
349 }
350
351 template <typename TWord>
352 inline unsigned
_popCountImpl(TWord word,WordSize_<32> const &)353 _popCountImpl(TWord word, WordSize_<32> const & /*tag*/)
354 {
355 return __builtin_popcount(static_cast<uint32_t>(word));
356 }
357
358 template <typename TWord>
359 inline unsigned
_popCountImpl(TWord word,WordSize_<16> const &)360 _popCountImpl(TWord word, WordSize_<16> const & /*tag*/)
361 {
362 return _popCountImpl(static_cast<uint32_t>(word), WordSize_<32>());
363 }
364
365 template <typename TWord>
366 inline unsigned
_popCountImpl(TWord word,WordSize_<8> const &)367 _popCountImpl(TWord word, WordSize_<8> const & /*tag*/)
368 {
369 return _popCountImpl(static_cast<uint32_t>(word), WordSize_<32>());
370 }
371
372 #endif // #if !(defined(COMPILER_MSVC) || defined(COMPILER_WINTEL))
373
374 // ----------------------------------------------------------------------------
375 // Function printBits()
376 // ----------------------------------------------------------------------------
377
378 //template <typename TValue>
379 //inline void printBits(TValue word)
380 //{
381 // unsigned bitsPerValue = BitsPerValue<TValue>::VALUE;
382 // TValue one = 1;
383 // for (TValue i = 0; i < bitsPerValue; ++i)
384 // std::cout << ((word >> i) & one);
385 // std::cout << std::endl;
386 //}
387
388 //template <typename TValue, typename TSize>
389 //inline std::ostream & printBits(std::ostream & stream, TValue word, TSize blockSize)
390 //{
391 // unsigned bitsPerValue = BitsPerValue<TValue>::VALUE;
392 // bool temp;
393 // for (int i = bitsPerValue - 1; i >= 0; --i)
394 // {
395 // temp = (word >> i) & 1;
396 // stream << temp;
397 // if ((bitsPerValue - i) % blockSize == 0)
398 // stream << " ";
399 // }
400 // return stream;
401 //}
402
403 // ----------------------------------------------------------------------------
404 // Function testAllZeros()
405 // ----------------------------------------------------------------------------
406
407 /*!
408 * @fn testAllZeros
409 * @headerfile <seqan/misc.h>
410 * @brief Tests whether all bits of the given value are set to <b>0</b>.
411 *
412 * @signature bool testAllZeros(val)
413 *
414 * @param[in] val The value to check the bits for. Must be of type @link IntegerConcept @endlink.
415 *
416 * @return bool <tt>true</tt> if all bits are set to <b>0</b>, <tt>false</tt> otherwise.
417 *
418 * @see testAllOnes
419 */
420
421 template <typename TWord>
testAllZeros(TWord const & val)422 inline bool testAllZeros(TWord const & val)
423 {
424 return val == 0;
425 }
426
427 // ----------------------------------------------------------------------------
428 // Function testAllOnes()
429 // ----------------------------------------------------------------------------
430
431 /*!
432 * @fn testAllOnes
433 * @headerfile <seqan/misc.h>
434 * @brief Tests whether all bits of the given value are set to <b>1</b>.
435 *
436 * @signature bool testAllOnes(val)
437 *
438 * @param[in] val The value to check the bits for. Must be of type @link IntegerConcept @endlink.
439 *
440 * @return bool <tt>true</tt> if all bits are set to <b>1</b>, <tt>false</tt> otherwise.
441 *
442 * @see testAllZeros
443 */
444
445 template <typename TWord>
_testAllOnes(TWord const & val,False)446 inline bool _testAllOnes(TWord const & val, False)
447 {
448 return val == ~static_cast<TWord>(0);
449 }
450
451 template <typename TWord>
testAllOnes(TWord const & val)452 inline bool testAllOnes(TWord const & val)
453 {
454 return _testAllOnes(val, typename Is<SimdVectorConcept<TWord> >::Type());
455 }
456
457 // ----------------------------------------------------------------------------
458 // Function _bitScanReverseGeneric() [Platform independent]
459 // ----------------------------------------------------------------------------
460
461 // bitScanReverse for 32 bit integers using DeBruijn sequence by Eric Cole, January 8, 2006.
462 template <typename TWord>
463 inline TWord
_bitScanReverseGeneric(TWord word,WordSize_<32>)464 _bitScanReverseGeneric(TWord word, WordSize_<32>)
465 {
466 return DeBruijnMultiplyLookup[static_cast<uint32_t>(word * 0x077CB531U) >> 27];
467 }
468
469 // bitScanReverse for 64 bit integers using DeBruijn sequence by Kim Walisch and Mark Dickinson.
470 template <typename TWord>
471 inline TWord
_bitScanReverseGeneric(TWord word,WordSize_<64>)472 _bitScanReverseGeneric(TWord word, WordSize_<64>)
473 {
474 word |= word >> 1; word |= word >> 2; word |= word >> 4; word |= word >> 8; word |= word >> 16; word |= word >> 32;
475 return DeBruijnMultiplyLookupBSR64[static_cast<uint64_t>(word * 0x03f79d71b4cb0a89ULL) >> 58];
476 }
477
478 // ----------------------------------------------------------------------------
479 // Function _bitScanReverse() [Platform independent]
480 // ----------------------------------------------------------------------------
481
482 template <typename TWord, unsigned int NUM_BITS>
483 inline TWord
_bitScanReverse(TWord word,WordSize_<NUM_BITS>)484 _bitScanReverse(TWord word, WordSize_<NUM_BITS>)
485 {
486 return _bitScanReverseGeneric(word, WordSize_<NUM_BITS>());
487 }
488
489 // ----------------------------------------------------------------------------
490 // Function _bitScanForwardGeneric() [Platform independent]
491 // ----------------------------------------------------------------------------
492
493 // bitScanForward implementations for 64 and 32 bit values using DeBruijn sequence by Martin L�uter, Charles E. Leiserson,
494 // Harald Prokop and Keith H. Randall; "Using de Bruijn Sequences to Index a 1 in a Computer Word"; (1997)
495
496 // Note, the cast of word to a signed integer is necessary to fix compiler warning C4146 on Windows platforms.
497 template <typename TWord>
498 inline TWord
_bitScanForwardGeneric(TWord word,WordSize_<32>)499 _bitScanForwardGeneric(TWord word, WordSize_<32>)
500 {
501 return DeBruijnMultiplyLookup[static_cast<uint32_t>(((word & -static_cast<int32_t>(word)) * 0x077CB531U)) >> 27];
502 }
503
504 template <typename TWord>
505 inline TWord
_bitScanForwardGeneric(TWord word,WordSize_<64>)506 _bitScanForwardGeneric(TWord word, WordSize_<64>)
507 {
508 return DeBruijnMultiplyLookupBSF64[static_cast<uint64_t>((word & -static_cast<int64_t>(word)) * 0x03f79d71b4cb0a89ULL) >> 58];
509 }
510
511 // ----------------------------------------------------------------------------
512 // Function _bitScanForward() [Platform independent]
513 // ----------------------------------------------------------------------------
514
515 template <typename TWord, unsigned int NUM_BITS>
516 inline TWord
_bitScanForward(TWord word,WordSize_<NUM_BITS>)517 _bitScanForward(TWord word, WordSize_<NUM_BITS>)
518 {
519 return _bitScanForwardGeneric(word, WordSize_<NUM_BITS>());
520 }
521
522 // NOTE(marehr): The Intel compiler on windows behaves the same as the visual
523 // studio compiler and on *nix the same as gcc. Thus, the __builtin_clz is only
524 // available on *nix.
525 #if defined(COMPILER_GCC) || defined(COMPILER_CLANG) || defined(COMPILER_LINTEL)
526
527 template <typename TWord>
528 inline TWord
_bitScanReverse(TWord word,WordSize_<64>)529 _bitScanReverse(TWord word, WordSize_<64>)
530 {
531 return 63 - __builtin_clzll(static_cast<unsigned long long>(word));
532 }
533
534 template <typename TWord>
535 inline TWord
_bitScanReverse(TWord word,WordSize_<32>)536 _bitScanReverse(TWord word, WordSize_<32>)
537 {
538 return 31 - __builtin_clz(static_cast<unsigned int>(word));
539 }
540
541
542 template <typename TWord>
543 inline TWord
_bitScanForward(TWord word,WordSize_<64>)544 _bitScanForward(TWord word, WordSize_<64>)
545 {
546 return __builtin_ctzll(static_cast<unsigned long long>(word));
547 }
548
549 template <typename TWord>
550 inline TWord
_bitScanForward(TWord word,WordSize_<32>)551 _bitScanForward(TWord word, WordSize_<32>)
552 {
553 return __builtin_ctz(static_cast<unsigned int>(word));
554 }
555
556 #elif defined(STDLIB_VS) // #if !(defined(COMPILER_GCC) || defined(COMPILER_CLANG) || defined(COMPILER_LINTEL)) && defined(STDLIB_VS)
557
558 #if (SEQAN_IS_64_BIT)
559
560 template <typename TWord>
561 inline TWord
_bitScanReverse(TWord word,WordSize_<64>)562 _bitScanReverse(TWord word, WordSize_<64>)
563 {
564 unsigned long index;
565 _BitScanReverse64(&index, static_cast<uint64_t>(word));
566 return index;
567 }
568
569 template <typename TWord>
570 inline TWord
_bitScanForward(TWord word,WordSize_<64>)571 _bitScanForward(TWord word, WordSize_<64>)
572 {
573 unsigned long index;
574 _BitScanForward64(&index, static_cast<uint64_t>(word));
575 return index;
576 }
577 #else
578
579 template <typename TWord>
580 inline TWord
_bitScanReverse(TWord word,WordSize_<64>)581 _bitScanReverse(TWord word, WordSize_<64>)
582 {
583 unsigned long index;
584 unsigned long hi = word >> 32;
585 if (hi == 0u)
586 {
587 _BitScanReverse(&index, word);
588 return index;
589 }
590 _BitScanReverse(&index, hi);
591 return index + 32;
592 }
593
594 template <typename TWord>
595 inline TWord
_bitScanForward(TWord word,WordSize_<64>)596 _bitScanForward(TWord word, WordSize_<64>)
597 {
598 unsigned long index;
599 unsigned long lo = word & ~static_cast<unsigned long>(0);
600 if (lo == 0u)
601 {
602 _BitScanForward(&index, word >> 32);
603 return index + 32;
604 }
605 _BitScanForward(&index, lo);
606 return index;
607 }
608 #endif // if (SEQAN_IS_64_BIT)
609
610 template <typename TWord>
611 inline TWord
_bitScanReverse(TWord word,WordSize_<32>)612 _bitScanReverse(TWord word, WordSize_<32>)
613 {
614 unsigned long index;
615 _BitScanReverse(&index, static_cast<unsigned long>(word));
616 return index;
617 }
618
619 template <typename TWord>
620 inline TWord
_bitScanForward(TWord word,WordSize_<32>)621 _bitScanForward(TWord word, WordSize_<32>)
622 {
623 unsigned long index;
624 _BitScanForward(&index, static_cast<unsigned long>(word));
625 return index;
626 }
627 #endif // #if !(defined(COMPILER_GCC) || defined(COMPILER_CLANG) || defined(COMPILER_LINTEL)) && defined(STDLIB_VS)
628
629 // ----------------------------------------------------------------------------
630 // Function bitScanReverse()
631 // ----------------------------------------------------------------------------
632
633 /*!
634 * @fn bitScanReverse
635 * @headerfile <seqan/misc.h>
636 * @brief Returns the index of the last set bit in the binary representation of the given value.
637 * @note If <tt>val</tt> is 0 the return value is undefined.
638 *
639 * @signature TWord bitScanReverse(val)
640 *
641 * @param[in] val The value to scan. Has to be non-zero.
642 *
643 * @return TWord The index of the last set bit in <tt>val</tt>, where <tt>TWord</tt> is the value of <tt>val</tt>.
644 *
645 * @see bitScanForward
646 */
647
648 template <typename TWord>
SEQAN_FUNC_ENABLE_IF(Is<IntegerConcept<TWord>>,TWord)649 inline SEQAN_FUNC_ENABLE_IF(Is<IntegerConcept<TWord> >, TWord)
650 bitScanReverse(TWord word)
651 {
652 SEQAN_ASSERT_NEQ(word, static_cast<TWord>(0));
653
654 return _bitScanReverse(word, WordSize_<(BitsPerValue<TWord>::VALUE <= 32) ? 32 : BitsPerValue<TWord>::VALUE>());
655 }
656
657 // ----------------------------------------------------------------------------
658 // Function bitScanForward()
659 // ----------------------------------------------------------------------------
660
661 /*!
662 * @fn bitScanForward
663 * @headerfile <seqan/misc.h>
664 * @brief Returns the index of the first set bit in the binary representation of the given value.
665 * @note If <tt>val</tt> is 0 the return value is undefined.
666 *
667 * @signature TWord bitScanForward(val)
668 *
669 * @param[in] val The value to scan. Has to be non-zero.
670 *
671 * @return TWord The index of the first set bit in <tt>val</tt>, where <tt>TWord</tt> is the value of <tt>val</tt>.
672 *
673 * @see bitScanReverse
674 */
675
676 template <typename TWord>
SEQAN_FUNC_ENABLE_IF(Is<IntegerConcept<TWord>>,TWord)677 inline SEQAN_FUNC_ENABLE_IF( Is<IntegerConcept<TWord> >, TWord)
678 bitScanForward(TWord word)
679 {
680 SEQAN_ASSERT_NEQ(word, static_cast<TWord>(0));
681 return _bitScanForward(word, WordSize_<(BitsPerValue<TWord>::VALUE <= 32) ? 32 : BitsPerValue<TWord>::VALUE>());
682 }
683
684 } // namespace seqan
685
686 #endif // #ifndef SEQAN_MISC_BIT_TWIDDLING_H_
687