1/* SPDX-License-Identifier: MIT */
2/* Copyright © 2022 Max Bachmann */
3
4#pragma once
5
6#include <cstdint>
7
8#if defined(_MSC_VER) && !defined(__clang__)
9# include <intrin.h>
10#endif
11
12namespace duckdb_jaro_winkler {
13namespace intrinsics {
14
15template <typename T>
16T bit_mask_lsb(int n)
17{
18 T mask = -1;
19 if (n < static_cast<int>(sizeof(T) * 8)) {
20 mask += static_cast<T>(1) << n;
21 }
22 return mask;
23}
24
25template <typename T>
26bool bittest(T a, int bit)
27{
28 return (a >> bit) & 1;
29}
30
31static inline int64_t popcount(uint64_t x)
32{
33 const uint64_t m1 = 0x5555555555555555;
34 const uint64_t m2 = 0x3333333333333333;
35 const uint64_t m4 = 0x0f0f0f0f0f0f0f0f;
36 const uint64_t h01 = 0x0101010101010101;
37
38 x -= (x >> 1) & m1;
39 x = (x & m2) + ((x >> 2) & m2);
40 x = (x + (x >> 4)) & m4;
41 return static_cast<int64_t>((x * h01) >> 56);
42}
43
44/**
45 * Extract the lowest set bit from a. If no bits are set in a returns 0.
46 */
47template <typename T>
48T blsi(T a)
49{
50#if _MSC_VER && !defined(__clang__)
51# pragma warning(push)
52/* unary minus operator applied to unsigned type, result still unsigned */
53# pragma warning(disable: 4146)
54#endif
55 return a & -a;
56#if _MSC_VER && !defined(__clang__)
57# pragma warning(pop)
58#endif
59}
60
61/**
62 * Clear the lowest set bit in a.
63 */
64template <typename T>
65T blsr(T x)
66{
67 return x & (x - 1);
68}
69
70#if defined(_MSC_VER) && !defined(__clang__)
71static inline int tzcnt(uint32_t x)
72{
73 unsigned long trailing_zero = 0;
74 _BitScanForward(&trailing_zero, x);
75 return trailing_zero;
76}
77
78# if defined(_M_ARM) || defined(_M_X64)
79static inline int tzcnt(uint64_t x)
80{
81 unsigned long trailing_zero = 0;
82 _BitScanForward64(&trailing_zero, x);
83 return trailing_zero;
84}
85# else
86static inline int tzcnt(uint64_t x)
87{
88 uint32_t msh = (uint32_t)(x >> 32);
89 uint32_t lsh = (uint32_t)(x & 0xFFFFFFFF);
90 if (lsh != 0) {
91 return tzcnt(lsh);
92 }
93 return 32 + tzcnt(msh);
94}
95# endif
96
97#else /* gcc / clang */
98//static inline int tzcnt(uint32_t x)
99//{
100// return __builtin_ctz(x);
101//}
102
103static inline int tzcnt(uint64_t x)
104{
105 return __builtin_ctzll(x);
106}
107#endif
108
109} // namespace intrinsics
110} // namespace duckdb_jaro_winkler
111