datasketches-cpp
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 
25 namespace datasketches {
26 
27 static 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 
46 static 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 
65 static const uint64_t FCLZ_MASK_56 = 0x00ffffffffffffff;
66 static const uint64_t FCLZ_MASK_48 = 0x0000ffffffffffff;
67 static const uint64_t FCLZ_MASK_40 = 0x000000ffffffffff;
68 static const uint64_t FCLZ_MASK_32 = 0x00000000ffffffff;
69 static const uint64_t FCLZ_MASK_24 = 0x0000000000ffffff;
70 static const uint64_t FCLZ_MASK_16 = 0x000000000000ffff;
71 static const uint64_t FCLZ_MASK_08 = 0x00000000000000ff;
72 
73 static 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 
92 static 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 
103 static 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 
112 static 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.1