datasketches-cpp
•All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
count_zeros.hpp
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19
20#ifndef _COUNT_ZEROS_HPP_
21#define _COUNT_ZEROS_HPP_
22
23#include <cstdint>
24
25namespace datasketches {
26
27static const uint8_t byte_leading_zeros_table[256] = {
28 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
29 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
30 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
31 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
32 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
33 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
34 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
35 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
36 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
37 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
38 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
39 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
40 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
41 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
42 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
43 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
44};
45
46static const uint8_t byte_trailing_zeros_table[256] = {
47 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
48 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
49 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
50 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
51 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
52 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
53 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
54 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
55 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
56 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
57 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
58 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
59 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
60 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
61 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
62 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
63};
64
65static const uint64_t FCLZ_MASK_56 = 0x00ffffffffffffff;
66static const uint64_t FCLZ_MASK_48 = 0x0000ffffffffffff;
67static const uint64_t FCLZ_MASK_40 = 0x000000ffffffffff;
68static const uint64_t FCLZ_MASK_32 = 0x00000000ffffffff;
69static const uint64_t FCLZ_MASK_24 = 0x0000000000ffffff;
70static const uint64_t FCLZ_MASK_16 = 0x000000000000ffff;
71static const uint64_t FCLZ_MASK_08 = 0x00000000000000ff;
72
73static inline uint8_t count_leading_zeros_in_u64(uint64_t input) {
74 if (input > FCLZ_MASK_56)
75 return byte_leading_zeros_table[(input >> 56) & FCLZ_MASK_08];
76 if (input > FCLZ_MASK_48)
77 return 8 + byte_leading_zeros_table[(input >> 48) & FCLZ_MASK_08];
78 if (input > FCLZ_MASK_40)
79 return 16 + byte_leading_zeros_table[(input >> 40) & FCLZ_MASK_08];
80 if (input > FCLZ_MASK_32)
81 return 24 + byte_leading_zeros_table[(input >> 32) & FCLZ_MASK_08];
82 if (input > FCLZ_MASK_24)
83 return 32 + byte_leading_zeros_table[(input >> 24) & FCLZ_MASK_08];
84 if (input > FCLZ_MASK_16)
85 return 40 + byte_leading_zeros_table[(input >> 16) & FCLZ_MASK_08];
86 if (input > FCLZ_MASK_08)
87 return 48 + byte_leading_zeros_table[(input >> 8) & FCLZ_MASK_08];
88 if (true)
89 return 56 + byte_leading_zeros_table[(input ) & FCLZ_MASK_08];
90}
91
92static inline uint8_t count_leading_zeros_in_u32(uint32_t input) {
93 if (input > FCLZ_MASK_24)
94 return byte_leading_zeros_table[(input >> 24) & FCLZ_MASK_08];
95 if (input > FCLZ_MASK_16)
96 return 8 + byte_leading_zeros_table[(input >> 16) & FCLZ_MASK_08];
97 if (input > FCLZ_MASK_08)
98 return 16 + byte_leading_zeros_table[(input >> 8) & FCLZ_MASK_08];
99 if (true)
100 return 24 + byte_leading_zeros_table[(input ) & FCLZ_MASK_08];
101}
102
103static inline uint8_t count_trailing_zeros_in_u32(uint32_t input) {
104 for (int i = 0; i < 4; i++) {
105 const int byte = input & 0xff;
106 if (byte != 0) return static_cast<uint8_t>((i << 3) + byte_trailing_zeros_table[byte]);
107 input >>= 8;
108 }
109 return 32;
110}
111
112static inline uint8_t count_trailing_zeros_in_u64(uint64_t input) {
113 for (int i = 0; i < 8; i++) {
114 const int byte = input & 0xff;
115 if (byte != 0) return static_cast<uint8_t>((i << 3) + byte_trailing_zeros_table[byte]);
116 input >>= 8;
117 }
118 return 64;
119}
120
121} /* namespace datasketches */
122
123#endif // _COUNT_ZEROS_HPP_
datasketches
DataSketches namespace.
Definition binomial_bounds.hpp:38
Generated by doxygen 1.9.8