1 // Copyright 2010-2021 Google LLC 2 // Licensed under the Apache License, Version 2.0 (the "License"); 3 // you may not use this file except in compliance with the License. 4 // You may obtain a copy of the License at 5 // 6 // http://www.apache.org/licenses/LICENSE-2.0 7 // 8 // Unless required by applicable law or agreed to in writing, software 9 // distributed under the License is distributed on an "AS IS" BASIS, 10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11 // See the License for the specific language governing permissions and 12 // limitations under the License. 13 14 #include "ortools/util/bitset.h" 15 16 #include "ortools/base/commandlineflags.h" 17 #include "ortools/base/logging.h" 18 19 ABSL_FLAG(int, bitset_small_bitset_count, 8, 20 "threshold to count bits with buckets"); 21 22 namespace operations_research { 23 24 // ---------- Bit Operations ---------- 25 26 #define BIT_COUNT_RANGE(size, zero) \ 27 uint##size##_t BitCountRange##size(const uint##size##_t* const bits, \ 28 uint##size##_t start, \ 29 uint##size##_t end) { \ 30 if (end - start > absl::GetFlag(FLAGS_bitset_small_bitset_count)) { \ 31 const int offset_start = BitOffset##size(start); \ 32 const int pos_start = BitPos##size(start); \ 33 const int offset_end = BitOffset##size(end); \ 34 const int pos_end = BitPos##size(end); \ 35 if (offset_end == offset_start) { \ 36 return BitCount##size(bits[offset_start] & \ 37 OneRange##size(pos_start, pos_end)); \ 38 } else { \ 39 uint##size##_t bit_count = zero; \ 40 bit_count += \ 41 BitCount##size(bits[offset_start] & IntervalUp##size(pos_start)); \ 42 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \ 43 bit_count += BitCount##size(bits[offset]); \ 44 } \ 45 bit_count += \ 46 BitCount##size(bits[offset_end] & IntervalDown##size(pos_end)); \ 47 return bit_count; \ 48 } \ 49 } else { \ 50 uint##size##_t bit_count = zero; \ 51 for (uint##size##_t i = start; i <= end; ++i) { \ 52 bit_count += IsBitSet##size(bits, i); \ 53 } \ 54 return bit_count; \ 55 } \ 56 } 57 58 BIT_COUNT_RANGE(64, uint64_t{0}) 59 BIT_COUNT_RANGE(32, 0U) 60 61 #undef BIT_COUNT_RANGE 62 63 #define IS_EMPTY_RANGE(size) \ 64 bool IsEmptyRange##size(const uint##size##_t* const bits, \ 65 uint##size##_t start, uint##size##_t end) { \ 66 const int offset_start = BitOffset##size(start); \ 67 const int pos_start = BitPos##size(start); \ 68 const int offset_end = BitOffset##size(end); \ 69 const int pos_end = BitPos##size(end); \ 70 if (offset_end == offset_start) { \ 71 if (bits[offset_start] & OneRange##size(pos_start, pos_end)) { \ 72 return false; \ 73 } \ 74 } else { \ 75 if (bits[offset_start] & IntervalUp##size(pos_start)) { \ 76 return false; \ 77 } \ 78 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \ 79 if (bits[offset]) { \ 80 return false; \ 81 } \ 82 } \ 83 if (bits[offset_end] & IntervalDown##size(pos_end)) { \ 84 return false; \ 85 } \ 86 } \ 87 return true; \ 88 } 89 90 IS_EMPTY_RANGE(64) 91 IS_EMPTY_RANGE(32) 92 93 #undef IS_EMPTY_RANGE 94 95 #define LEAST_SIGNIFCANT_BIT_POSITION(size) \ 96 int##size##_t LeastSignificantBitPosition##size( \ 97 const uint##size##_t* const bits, uint##size##_t start, \ 98 uint##size##_t end) { \ 99 DCHECK_LE(start, end); \ 100 if (IsBitSet##size(bits, start)) { \ 101 return start; \ 102 } \ 103 const int offset_start = BitOffset##size(start); \ 104 const int offset_end = BitOffset##size(end); \ 105 const int pos_start = BitPos##size(start); \ 106 if (offset_start == offset_end) { \ 107 const int pos_end = BitPos##size(end); \ 108 const uint##size##_t active_range = \ 109 bits[offset_start] & OneRange##size(pos_start, pos_end); \ 110 if (active_range) { \ 111 return BitShift##size(offset_start) + \ 112 LeastSignificantBitPosition##size(active_range); \ 113 } \ 114 return -1; \ 115 } else { \ 116 const uint##size##_t start_mask = \ 117 bits[offset_start] & IntervalUp##size(pos_start); \ 118 if (start_mask) { \ 119 return BitShift##size(offset_start) + \ 120 LeastSignificantBitPosition##size(start_mask); \ 121 } else { \ 122 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \ 123 if (bits[offset]) { \ 124 return BitShift##size(offset) + \ 125 LeastSignificantBitPosition##size(bits[offset]); \ 126 } \ 127 } \ 128 const int pos_end = BitPos##size(end); \ 129 const uint##size##_t active_range = \ 130 bits[offset_end] & IntervalDown##size(pos_end); \ 131 if (active_range) { \ 132 return BitShift##size(offset_end) + \ 133 LeastSignificantBitPosition##size(active_range); \ 134 } else { \ 135 return -1; \ 136 } \ 137 } \ 138 } \ 139 } 140 141 LEAST_SIGNIFCANT_BIT_POSITION(64) 142 LEAST_SIGNIFCANT_BIT_POSITION(32) 143 144 #undef LEAST_SIGNIFCANT_BIT_POSITION 145 146 #define MOST_SIGNIFICANT_BIT_POSITION(size) \ 147 int##size##_t MostSignificantBitPosition##size( \ 148 const uint##size##_t* const bits, uint##size##_t start, \ 149 uint##size##_t end) { \ 150 DCHECK_GE(end, start); \ 151 if (IsBitSet##size(bits, end)) { \ 152 return end; \ 153 } \ 154 const int offset_start = BitOffset##size(start); \ 155 const int offset_end = BitOffset##size(end); \ 156 const int pos_end = BitPos##size(end); \ 157 if (offset_start == offset_end) { \ 158 const int pos_start = BitPos##size(start); \ 159 const uint##size##_t active_range = \ 160 bits[offset_start] & OneRange##size(pos_start, pos_end); \ 161 if (active_range) { \ 162 return BitShift##size(offset_end) + \ 163 MostSignificantBitPosition##size(active_range); \ 164 } else { \ 165 return -1; \ 166 } \ 167 } else { \ 168 const uint##size##_t end_mask = \ 169 bits[offset_end] & IntervalDown##size(pos_end); \ 170 if (end_mask) { \ 171 return BitShift##size(offset_end) + \ 172 MostSignificantBitPosition##size(end_mask); \ 173 } else { \ 174 for (int offset = offset_end - 1; offset > offset_start; --offset) { \ 175 if (bits[offset]) { \ 176 return BitShift##size(offset) + \ 177 MostSignificantBitPosition##size(bits[offset]); \ 178 } \ 179 } \ 180 const int pos_start = BitPos##size(start); \ 181 const uint##size##_t active_range = \ 182 bits[offset_start] & IntervalUp##size(pos_start); \ 183 if (active_range) { \ 184 return BitShift##size(offset_start) + \ 185 MostSignificantBitPosition##size(active_range); \ 186 } else { \ 187 return -1; \ 188 } \ 189 } \ 190 } \ 191 } 192 193 MOST_SIGNIFICANT_BIT_POSITION(64) 194 MOST_SIGNIFICANT_BIT_POSITION(32) 195 196 #undef MOST_SIGNIFICANT_BIT_POSITION 197 198 #define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size) \ 199 int##size##_t UnsafeLeastSignificantBitPosition##size( \ 200 const uint##size##_t* const bits, uint##size##_t start, \ 201 uint##size##_t end) { \ 202 DCHECK_LE(start, end); \ 203 DCHECK(IsBitSet##size(bits, end)); \ 204 if (IsBitSet##size(bits, start)) { \ 205 return start; \ 206 } \ 207 const int offset_start = BitOffset##size(start); \ 208 const int offset_end = BitOffset##size(end); \ 209 const int pos_start = BitPos##size(start); \ 210 const uint##size##_t start_mask = \ 211 bits[offset_start] & IntervalUp##size(pos_start); \ 212 if (start_mask) { \ 213 return BitShift##size(offset_start) + \ 214 LeastSignificantBitPosition##size(start_mask); \ 215 } \ 216 for (int offset = offset_start + 1; offset <= offset_end; ++offset) { \ 217 if (bits[offset]) { \ 218 return BitShift##size(offset) + \ 219 LeastSignificantBitPosition##size(bits[offset]); \ 220 } \ 221 } \ 222 return -1; \ 223 } 224 225 UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(64) 226 UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(32) 227 228 #undef UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION 229 230 #define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size) \ 231 int##size##_t UnsafeMostSignificantBitPosition##size( \ 232 const uint##size##_t* const bits, uint##size##_t start, \ 233 uint##size##_t end) { \ 234 DCHECK_GE(end, start); \ 235 DCHECK(IsBitSet##size(bits, start)); \ 236 if (IsBitSet##size(bits, end)) { \ 237 return end; \ 238 } \ 239 const int offset_start = BitOffset##size(start); \ 240 const int offset_end = BitOffset##size(end); \ 241 const int pos_end = BitPos##size(end); \ 242 const uint##size##_t end_mask = \ 243 bits[offset_end] & IntervalDown##size(pos_end); \ 244 if (end_mask) { \ 245 return BitShift##size(offset_end) + \ 246 MostSignificantBitPosition##size(end_mask); \ 247 } \ 248 for (int offset = offset_end - 1; offset >= offset_start; --offset) { \ 249 if (bits[offset]) { \ 250 return BitShift##size(offset) + \ 251 MostSignificantBitPosition##size(bits[offset]); \ 252 } \ 253 } \ 254 return -1; \ 255 } 256 257 UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(64) 258 UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(32) 259 260 #undef UNSAFE_MOST_SIGNIFICANT_BIT_POSITION 261 262 } // namespace operations_research 263