zircon/system/ulib/bitmap/raw-bitmap.cc

// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <bitmap/raw-bitmap.h>
#include <bitmap/storage.h>

#include <limits.h>
#include <stddef.h>

#include <fbl/algorithm.h>
#include <fbl/macros.h>
#include <zircon/types.h>

namespace bitmap {
namespace {

// Translates a bit offset into a starting index in the bitmap array.
constexpr size_t FirstIdx(size_t bitoff) { return bitoff / kBits; }

// GetMask returns a 64-bit bitmask. If the block of the bitmap we're looking
// at isn't the first or last, all bits are set.  Otherwise, the bits outside of
// [off,max) are cleared.  Bits are counted with the LSB as 0 and the MSB as 63.
//
// Examples:
//  GetMask(false, false, 16, 48) => 0xffffffffffffffff
//  GetMask(true,  false, 16, 48) => 0xffffffffffff0000
//  GetMask(false,  true, 16, 48) => 0x0000ffffffffffff
//  GetMask(true,   true, 16, 48) => 0x0000ffffffff0000
size_t GetMask(bool first, bool last, size_t off, size_t max) {
  size_t ones = ~(size_t(0));
  size_t mask = ones;
  if (first) {
    mask &= ones << (off % kBits);
  }
  if (last) {
    mask &= ones >> ((kBits - (max % kBits)) % kBits);
  }
  return mask;
}

// Applies a bitmask to the given data value. The result value has bits set
// which fall within the mask but do not match is_set.
size_t MaskBits(size_t data, size_t idx, size_t bitoff, size_t bitmax, bool is_set) {
  size_t mask = GetMask(idx == FirstIdx(bitoff), idx == LastIdx(bitmax), bitoff, bitmax);
  if (is_set) {
    // If is_set=true, invert the mask, OR it with the value, and invert
    // it again to hopefully get all zeros.
    return ~(~mask | data);
  } else {
    // If is_set=false, just AND the mask with the value to hopefully
    // get all zeros.
    return mask & data;
  }
}

// Counts the number of zeros.  It assumes everything in the array up to
// bits_[idx] is zero.
#if (SIZE_MAX == UINT_MAX)
#define CLZ(x) (x == 0 ? kBits : __builtin_clz(x))
#define CTZ(x) (x == 0 ? kBits : __builtin_ctz(x))
#elif (SIZE_MAX == ULONG_MAX)
#define CLZ(x) (x == 0 ? kBits : __builtin_clzl(x))
#define CTZ(x) (x == 0 ? kBits : __builtin_ctzl(x))
#elif (SIZE_MAX == ULLONG_MAX)
#define CLZ(x) (x == 0 ? kBits : __builtin_clzll(x))
#define CTZ(x) (x == 0 ? kBits : __builtin_ctzll(x))
#else
#error "Unsupported size_t length"
#endif

}  // namespace

zx_status_t RawBitmapBase::Shrink(size_t size) {
  if (size > size_) {
    return ZX_ERR_NO_MEMORY;
  }
  size_ = size;
  return ZX_OK;
}

bool RawBitmapBase::Scan(size_t bitoff, size_t bitmax, bool is_set, size_t* out) const {
  bitmax = fbl::min(bitmax, size_);
  if (bitoff >= bitmax) {
    return true;
  }
  size_t i = FirstIdx(bitoff);
  while (true) {
    size_t masked = MaskBits(data_[i], i, bitoff, bitmax, is_set);
    if (masked != 0) {
      if (out) {
        *out = i * bitmap::kBits + CTZ(masked);
      }
      return false;
    }
    if (i == LastIdx(bitmax)) {
      return true;
    }
    ++i;
  }
}

bool RawBitmapBase::ReverseScan(size_t bitoff, size_t bitmax, bool is_set, size_t* out) const {
  bitmax = fbl::min(bitmax, size_);
  if (bitoff >= bitmax) {
    return true;
  }
  size_t i = LastIdx(bitmax);
  while (true) {
    size_t masked = MaskBits(data_[i], i, bitoff, bitmax, is_set);
    if (masked != 0) {
      if (out) {
        *out = (i + 1) * bitmap::kBits - (CLZ(masked) + 1);
      }
      return false;
    }
    if (i == FirstIdx(bitoff)) {
      return true;
    }
    --i;
  }
}

zx_status_t RawBitmapBase::Find(bool is_set, size_t bitoff, size_t bitmax, size_t run_len,
                                size_t* out) const {
  if (!out || bitmax <= bitoff) {
    return ZX_ERR_INVALID_ARGS;
  }
  size_t start = bitoff;
  while (true) {
    if (Scan(bitoff, bitmax, !is_set, &start) || (bitmax - start < run_len)) {
      return ZX_ERR_NO_RESOURCES;
    }
    if (Scan(start, start + run_len, is_set, &bitoff)) {
      *out = start;
      return ZX_OK;
    }
  }
}

zx_status_t RawBitmapBase::ReverseFind(bool is_set, size_t bitoff, size_t bitmax, size_t run_len,
                                       size_t* out) const {
  if (!out || bitmax <= bitoff) {
    return ZX_ERR_INVALID_ARGS;
  }
  size_t start = bitmax;
  while (true) {
    if (ReverseScan(bitoff, bitmax, !is_set, &start)) {
      return ZX_ERR_NO_RESOURCES;
    }
    // Increment start to be last bit that is !is_set
    ++start;
    if ((start - bitoff < run_len)) {
      return ZX_ERR_NO_RESOURCES;
    }
    if (ReverseScan(start - run_len, start, is_set, &bitmax)) {
      *out = start - run_len;
      return ZX_OK;
    }
  }
}

bool RawBitmapBase::Get(size_t bitoff, size_t bitmax, size_t* first) const {
  bool result;
  if ((result = Scan(bitoff, bitmax, true, first)) && first) {
    *first = bitmax;
  }
  return result;
}

zx_status_t RawBitmapBase::Set(size_t bitoff, size_t bitmax) {
  if (bitoff > bitmax || bitmax > size_) {
    return ZX_ERR_INVALID_ARGS;
  }
  if (bitoff == bitmax) {
    return ZX_OK;
  }
  size_t first_idx = FirstIdx(bitoff);
  size_t last_idx = LastIdx(bitmax);
  for (size_t i = first_idx; i <= last_idx; ++i) {
    data_[i] |= GetMask(i == first_idx, i == last_idx, bitoff, bitmax);
  }
  return ZX_OK;
}

zx_status_t RawBitmapBase::Clear(size_t bitoff, size_t bitmax) {
  if (bitoff > bitmax || bitmax > size_) {
    return ZX_ERR_INVALID_ARGS;
  }
  if (bitoff == bitmax) {
    return ZX_OK;
  }
  size_t first_idx = FirstIdx(bitoff);
  size_t last_idx = LastIdx(bitmax);
  for (size_t i = first_idx; i <= last_idx; ++i) {
    data_[i] &= ~(GetMask(i == first_idx, i == last_idx, bitoff, bitmax));
  }
  return ZX_OK;
}

void RawBitmapBase::ClearAll() {
  if (size_ == 0) {
    return;
  }
  size_t last_idx = LastIdx(size_);
  for (size_t i = 0; i <= last_idx; ++i) {
    data_[i] = 0;
  }
}

}  // namespace bitmap