bitset.cc

// Copyright 2010-2018 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "ortools/util/bitset.h"

#include "ortools/base/commandlineflags.h"
#include "ortools/base/logging.h"

DEFINE_int32(bitset_small_bitset_count, 8,
             "threshold to count bits with buckets");

namespace operations_research {

// ---------- Bit Operations ----------

#define BIT_COUNT_RANGE(size, zero)                                           \
  uint##size BitCountRange##size(const uint##size* const bits,                \
                                 uint##size start, uint##size end) {          \
    if (end - start > FLAGS_bitset_small_bitset_count) {                      \
      const int offset_start = BitOffset##size(start);                        \
      const int pos_start = BitPos##size(start);                              \
      const int offset_end = BitOffset##size(end);                            \
      const int pos_end = BitPos##size(end);                                  \
      if (offset_end == offset_start) {                                       \
        return BitCount##size(bits[offset_start] &                            \
                              OneRange##size(pos_start, pos_end));            \
      } else {                                                                \
        uint##size bit_count = zero;                                          \
        bit_count +=                                                          \
            BitCount##size(bits[offset_start] & IntervalUp##size(pos_start)); \
        for (int offset = offset_start + 1; offset < offset_end; ++offset) {  \
          bit_count += BitCount##size(bits[offset]);                          \
        }                                                                     \
        bit_count +=                                                          \
            BitCount##size(bits[offset_end] & IntervalDown##size(pos_end));   \
        return bit_count;                                                     \
      }                                                                       \
    } else {                                                                  \
      uint##size bit_count = zero;                                            \
      for (uint##size i = start; i <= end; ++i) {                             \
        bit_count += IsBitSet##size(bits, i);                                 \
      }                                                                       \
      return bit_count;                                                       \
    }                                                                         \
  }

BIT_COUNT_RANGE(64, GG_ULONGLONG(0))
BIT_COUNT_RANGE(32, 0U)

#undef BIT_COUNT_RANGE

#define IS_EMPTY_RANGE(size)                                               \
  bool IsEmptyRange##size(const uint##size* const bits, uint##size start,  \
                          uint##size end) {                                \
    const int offset_start = BitOffset##size(start);                       \
    const int pos_start = BitPos##size(start);                             \
    const int offset_end = BitOffset##size(end);                           \
    const int pos_end = BitPos##size(end);                                 \
    if (offset_end == offset_start) {                                      \
      if (bits[offset_start] & OneRange##size(pos_start, pos_end)) {       \
        return false;                                                      \
      }                                                                    \
    } else {                                                               \
      if (bits[offset_start] & IntervalUp##size(pos_start)) {              \
        return false;                                                      \
      }                                                                    \
      for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
        if (bits[offset]) {                                                \
          return false;                                                    \
        }                                                                  \
      }                                                                    \
      if (bits[offset_end] & IntervalDown##size(pos_end)) {                \
        return false;                                                      \
      }                                                                    \
    }                                                                      \
    return true;                                                           \
  }

IS_EMPTY_RANGE(64)
IS_EMPTY_RANGE(32)

#undef IS_EMPTY_RANGE

#define LEAST_SIGNIFCANT_BIT_POSITION(size)                                  \
  int##size LeastSignificantBitPosition##size(                               \
      const uint##size* const bits, uint##size start, uint##size end) {      \
    DCHECK_LE(start, end);                                                   \
    if (IsBitSet##size(bits, start)) {                                       \
      return start;                                                          \
    }                                                                        \
    const int offset_start = BitOffset##size(start);                         \
    const int offset_end = BitOffset##size(end);                             \
    const int pos_start = BitPos##size(start);                               \
    if (offset_start == offset_end) {                                        \
      const int pos_end = BitPos##size(end);                                 \
      const uint##size active_range =                                        \
          bits[offset_start] & OneRange##size(pos_start, pos_end);           \
      if (active_range) {                                                    \
        return BitShift##size(offset_start) +                                \
               LeastSignificantBitPosition##size(active_range);              \
      }                                                                      \
      return -1;                                                             \
    } else {                                                                 \
      const uint##size start_mask =                                          \
          bits[offset_start] & IntervalUp##size(pos_start);                  \
      if (start_mask) {                                                      \
        return BitShift##size(offset_start) +                                \
               LeastSignificantBitPosition##size(start_mask);                \
      } else {                                                               \
        for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
          if (bits[offset]) {                                                \
            return BitShift##size(offset) +                                  \
                   LeastSignificantBitPosition##size(bits[offset]);          \
          }                                                                  \
        }                                                                    \
        const int pos_end = BitPos##size(end);                               \
        const uint##size active_range =                                      \
            bits[offset_end] & IntervalDown##size(pos_end);                  \
        if (active_range) {                                                  \
          return BitShift##size(offset_end) +                                \
                 LeastSignificantBitPosition##size(active_range);            \
        } else {                                                             \
          return -1;                                                         \
        }                                                                    \
      }                                                                      \
    }                                                                        \
  }

LEAST_SIGNIFCANT_BIT_POSITION(64)
LEAST_SIGNIFCANT_BIT_POSITION(32)

#undef LEAST_SIGNIFCANT_BIT_POSITION

#define MOST_SIGNIFICANT_BIT_POSITION(size)                                  \
  int##size MostSignificantBitPosition##size(                                \
      const uint##size* const bits, uint##size start, uint##size end) {      \
    DCHECK_GE(end, start);                                                   \
    if (IsBitSet##size(bits, end)) {                                         \
      return end;                                                            \
    }                                                                        \
    const int offset_start = BitOffset##size(start);                         \
    const int offset_end = BitOffset##size(end);                             \
    const int pos_end = BitPos##size(end);                                   \
    if (offset_start == offset_end) {                                        \
      const int pos_start = BitPos##size(start);                             \
      const uint##size active_range =                                        \
          bits[offset_start] & OneRange##size(pos_start, pos_end);           \
      if (active_range) {                                                    \
        return BitShift##size(offset_end) +                                  \
               MostSignificantBitPosition##size(active_range);               \
      } else {                                                               \
        return -1;                                                           \
      }                                                                      \
    } else {                                                                 \
      const uint##size end_mask =                                            \
          bits[offset_end] & IntervalDown##size(pos_end);                    \
      if (end_mask) {                                                        \
        return BitShift##size(offset_end) +                                  \
               MostSignificantBitPosition##size(end_mask);                   \
      } else {                                                               \
        for (int offset = offset_end - 1; offset > offset_start; --offset) { \
          if (bits[offset]) {                                                \
            return BitShift##size(offset) +                                  \
                   MostSignificantBitPosition##size(bits[offset]);           \
          }                                                                  \
        }                                                                    \
        const int pos_start = BitPos##size(start);                           \
        const uint##size active_range =                                      \
            bits[offset_start] & IntervalUp##size(pos_start);                \
        if (active_range) {                                                  \
          return BitShift##size(offset_start) +                              \
                 MostSignificantBitPosition##size(active_range);             \
        } else {                                                             \
          return -1;                                                         \
        }                                                                    \
      }                                                                      \
    }                                                                        \
  }

MOST_SIGNIFICANT_BIT_POSITION(64)
MOST_SIGNIFICANT_BIT_POSITION(32)

#undef MOST_SIGNIFICANT_BIT_POSITION

#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size)                       \
  int##size UnsafeLeastSignificantBitPosition##size(                      \
      const uint##size* const bits, uint##size start, uint##size end) {   \
    DCHECK_LE(start, end);                                                \
    DCHECK(IsBitSet##size(bits, end));                                    \
    if (IsBitSet##size(bits, start)) {                                    \
      return start;                                                       \
    }                                                                     \
    const int offset_start = BitOffset##size(start);                      \
    const int offset_end = BitOffset##size(end);                          \
    const int pos_start = BitPos##size(start);                            \
    const uint##size start_mask =                                         \
        bits[offset_start] & IntervalUp##size(pos_start);                 \
    if (start_mask) {                                                     \
      return BitShift##size(offset_start) +                               \
             LeastSignificantBitPosition##size(start_mask);               \
    }                                                                     \
    for (int offset = offset_start + 1; offset <= offset_end; ++offset) { \
      if (bits[offset]) {                                                 \
        return BitShift##size(offset) +                                   \
               LeastSignificantBitPosition##size(bits[offset]);           \
      }                                                                   \
    }                                                                     \
    return -1;                                                            \
  }

UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(64)
UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(32)

#undef UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION

#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size)                        \
  int##size UnsafeMostSignificantBitPosition##size(                       \
      const uint##size* const bits, uint##size start, uint##size end) {   \
    DCHECK_GE(end, start);                                                \
    DCHECK(IsBitSet##size(bits, start));                                  \
    if (IsBitSet##size(bits, end)) {                                      \
      return end;                                                         \
    }                                                                     \
    const int offset_start = BitOffset##size(start);                      \
    const int offset_end = BitOffset##size(end);                          \
    const int pos_end = BitPos##size(end);                                \
    const uint##size end_mask =                                           \
        bits[offset_end] & IntervalDown##size(pos_end);                   \
    if (end_mask) {                                                       \
      return BitShift##size(offset_end) +                                 \
             MostSignificantBitPosition##size(end_mask);                  \
    }                                                                     \
    for (int offset = offset_end - 1; offset >= offset_start; --offset) { \
      if (bits[offset]) {                                                 \
        return BitShift##size(offset) +                                   \
               MostSignificantBitPosition##size(bits[offset]);            \
      }                                                                   \
    }                                                                     \
    return -1;                                                            \
  }

UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(64)
UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(32)

#undef UNSAFE_MOST_SIGNIFICANT_BIT_POSITION

}  // namespace operations_research