Program Listing for File arithmetic.hpp

↰ Return to documentation for file (include/common/arithmetic/arithmetic.hpp)

/*
  Copyright 2018-2024, Barcelona Supercomputing Center (BSC), Spain
  Copyright 2015-2024, Johannes Gutenberg Universitaet Mainz, Germany

  This software was partially supported by the
  EC H2020 funded project NEXTGenIO (Project ID: 671951, www.nextgenio.eu).

  This software was partially supported by the
  ADA-FS project under the SPPEXA project funded by the DFG.

  This file is part of GekkoFS.

  GekkoFS is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  GekkoFS is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with GekkoFS.  If not, see <https://www.gnu.org/licenses/>.

  SPDX-License-Identifier: GPL-3.0-or-later
*/

#ifndef GKFS_COMMON_ARITHMETIC_HPP
#define GKFS_COMMON_ARITHMETIC_HPP

#include <cstdint>
#include <unistd.h>
#include <cassert>

namespace gkfs::utils::arithmetic {

constexpr bool
is_power_of_2(uint64_t n) {
    return n && (!(n & (n - 1u)));
}

constexpr std::size_t
log2(uint64_t n) {
    return 8u * sizeof(uint64_t) - __builtin_clzll(n) - 1;
}

constexpr bool
is_aligned(const uint64_t n, const size_t block_size) {
    using gkfs::utils::arithmetic::log2;
    assert(is_power_of_2(block_size));
    return !(n & ((1u << log2(block_size)) - 1));
}

constexpr uint64_t
align_left(const uint64_t offset, const size_t block_size) {
    // This check is automatically removed in release builds
    assert(is_power_of_2(block_size));
    return offset & ~(block_size - 1u);
}


constexpr uint64_t
align_right(const uint64_t offset, const size_t block_size) {
    // This check is automatically removed in release builds
    assert(is_power_of_2(block_size));
    return align_left(offset, block_size) + block_size;
}


constexpr size_t
block_overrun(const uint64_t offset, const size_t block_size) {
    // This check is automatically removed in release builds
    assert(is_power_of_2(block_size));
    return offset & (block_size - 1u);
}


constexpr size_t
block_underrun(const uint64_t offset, const size_t block_size) {
    // This check is automatically removed in release builds
    assert(is_power_of_2(block_size));
    return align_right(offset, block_size) - offset;
}


constexpr uint64_t
block_index(const uint64_t offset, const size_t block_size) {

    using gkfs::utils::arithmetic::log2;

    // This check is automatically removed in release builds
    assert(is_power_of_2(block_size));
    return align_left(offset, block_size) >> log2(block_size);
}


constexpr std::size_t
block_count(const uint64_t offset, const size_t size, const size_t block_size) {

    using gkfs::utils::arithmetic::log2;

    // These checks are automatically removed in release builds
    assert(is_power_of_2(block_size));

#if defined(__GNUC__) && !defined(__clang__)
    assert(!__builtin_add_overflow_p(offset, size, uint64_t{0}));
#else
    assert(offset + size > offset);
#endif

    const uint64_t first_block = align_left(offset, block_size);
    const uint64_t final_block = align_left(offset + size, block_size);
    const size_t mask = -!!size; // this is either 0 or ~0

    return (((final_block >> log2(block_size)) -
             (first_block >> log2(block_size)) +
             !is_aligned(offset + size, block_size))) &
           mask;
}

} // namespace gkfs::utils::arithmetic

#endif // GKFS_COMMON_ARITHMETIC_HPP