LCOV - code coverage report
Current view: top level - include/common/arithmetic - arithmetic.hpp (source / functions) Hit Total Coverage
Test: coverage.info Lines: 35 35 100.0 %
Date: 2024-04-23 00:09:24 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*
       2             :   Copyright 2018-2024, Barcelona Supercomputing Center (BSC), Spain
       3             :   Copyright 2015-2024, Johannes Gutenberg Universitaet Mainz, Germany
       4             : 
       5             :   This software was partially supported by the
       6             :   EC H2020 funded project NEXTGenIO (Project ID: 671951, www.nextgenio.eu).
       7             : 
       8             :   This software was partially supported by the
       9             :   ADA-FS project under the SPPEXA project funded by the DFG.
      10             : 
      11             :   This file is part of GekkoFS.
      12             : 
      13             :   GekkoFS is free software: you can redistribute it and/or modify
      14             :   it under the terms of the GNU General Public License as published by
      15             :   the Free Software Foundation, either version 3 of the License, or
      16             :   (at your option) any later version.
      17             : 
      18             :   GekkoFS is distributed in the hope that it will be useful,
      19             :   but WITHOUT ANY WARRANTY; without even the implied warranty of
      20             :   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      21             :   GNU General Public License for more details.
      22             : 
      23             :   You should have received a copy of the GNU General Public License
      24             :   along with GekkoFS.  If not, see <https://www.gnu.org/licenses/>.
      25             : 
      26             :   SPDX-License-Identifier: GPL-3.0-or-later
      27             : */
      28             : 
      29             : #ifndef GKFS_COMMON_ARITHMETIC_HPP
      30             : #define GKFS_COMMON_ARITHMETIC_HPP
      31             : 
      32             : #include <cstdint>
      33             : #include <unistd.h>
      34             : #include <cassert>
      35             : 
      36             : namespace gkfs::utils::arithmetic {
      37             : 
      38             : /**
      39             :  * Check whether integer `n` is a power of 2.
      40             :  *
      41             :  * @param [in] n the number to check.
      42             :  * @returns `true` if `n` is a power of 2; `false` otherwise.
      43             :  */
      44             : constexpr bool
      45    51741437 : is_power_of_2(uint64_t n) {
      46    51741279 :     return n && (!(n & (n - 1u)));
      47             : }
      48             : 
      49             : /**
      50             :  * Compute the base2 logarithm for 64 bit integers.
      51             :  *
      52             :  * @param [in] n the number from which to compute the log2.
      53             :  * @returns the base 2 logarithm of `n`.
      54             :  */
      55             : constexpr std::size_t
      56     5564647 : log2(uint64_t n) {
      57     5564647 :     return 8u * sizeof(uint64_t) - __builtin_clzll(n) - 1;
      58             : }
      59             : 
      60             : /**
      61             :  * Check whether @n is aligned to a block boundary, i.e. if it is divisible by
      62             :  * @block_size.
      63             :  *
      64             :  * @note This function assumes that block_size is a power of 2.
      65             :  *
      66             :  * @param [in] n the number to check.
      67             :  * @param [in] block_size
      68             :  * @returns true if @n is divisible by @block_size; false otherwise.
      69             :  */
      70             : constexpr bool
      71     2806845 : is_aligned(const uint64_t n, const size_t block_size) {
      72     2806845 :     using gkfs::utils::arithmetic::log2;
      73     2806845 :     assert(is_power_of_2(block_size));
      74     2806845 :     return !(n & ((1u << log2(block_size)) - 1));
      75             : }
      76             : 
      77             : /**
      78             :  * Given a file @offset and a @block_size, align the @offset to its
      79             :  * closest left-side block boundary.
      80             :  *
      81             :  * @note This function assumes that block_size is a power of 2.
      82             :  *
      83             :  * @param [in] offset the offset to align.
      84             :  * @param [in] block_size the block size used to compute boundaries.
      85             :  * @returns an offset aligned to the left-side block boundary.
      86             :  */
      87             : constexpr uint64_t
      88     5529114 : align_left(const uint64_t offset, const size_t block_size) {
      89             :     // This check is automatically removed in release builds
      90     5529114 :     assert(is_power_of_2(block_size));
      91     5529114 :     return offset & ~(block_size - 1u);
      92             : }
      93             : 
      94             : 
      95             : /**
      96             :  * Given a file @offset and a @block_size, align the @offset to its
      97             :  * closest right-side block boundary.
      98             :  *
      99             :  * @note This function assumes that block_size is a power of 2.
     100             :  *
     101             :  * @param [in] offset the offset to align.
     102             :  * @param [in] block_size the block size used to compute boundaries.
     103             :  * @returns an offset aligned to the right-side block boundary.
     104             :  */
     105             : constexpr uint64_t
     106       13742 : align_right(const uint64_t offset, const size_t block_size) {
     107             :     // This check is automatically removed in release builds
     108       13742 :     assert(is_power_of_2(block_size));
     109       13742 :     return align_left(offset, block_size) + block_size;
     110             : }
     111             : 
     112             : 
     113             : /**
     114             :  * Return the overrun bytes that separate @offset from the closest left side
     115             :  * block boundary.
     116             :  *
     117             :  * @note This function assumes that block_size is a power of 2.
     118             :  *
     119             :  * @param [in] offset the offset for which the overrun distance should be
     120             :  * computed.
     121             :  * @param [in] block_size the block size used to compute boundaries.
     122             :  * @returns the distance in bytes between the left-side boundary of @offset
     123             :  */
     124             : constexpr size_t
     125        7009 : block_overrun(const uint64_t offset, const size_t block_size) {
     126             :     // This check is automatically removed in release builds
     127        7009 :     assert(is_power_of_2(block_size));
     128        7009 :     return offset & (block_size - 1u);
     129             : }
     130             : 
     131             : 
     132             : /**
     133             :  * Return the underrun bytes that separate @offset from the closest right side
     134             :  * block boundary.
     135             :  *
     136             :  * @note This function assumes that block_size is a power of 2.
     137             :  *
     138             :  * @param [in] offset the offset for which the overrun distance should be
     139             :  * computed.
     140             :  * @param [in] block_size the block size used to compute boundaries.
     141             :  * @returns the distance in bytes between the right-side boundary of @offset
     142             :  */
     143             : constexpr size_t
     144        6925 : block_underrun(const uint64_t offset, const size_t block_size) {
     145             :     // This check is automatically removed in release builds
     146        6925 :     assert(is_power_of_2(block_size));
     147        6925 :     return align_right(offset, block_size) - offset;
     148             : }
     149             : 
     150             : 
     151             : /**
     152             :  * Given an @offset and a @block_size, compute the block index to which @offset
     153             :  * belongs.
     154             :  *
     155             :  * @note Block indexes are (conceptually) computed by dividing @offset
     156             :  * by @block_size, with index 0 referring to block [0, block_size - 1],
     157             :  * index 1 to block [block_size, 2 * block_size - 1], and so on up to
     158             :  * a maximum index FILE_LENGTH / block_size.
     159             :  *
     160             :  * @note This function assumes that @block_size is a power of 2.
     161             :  *
     162             :  * @param [in] offset the offset for which the block index should be computed.
     163             :  * @param [in] block_size the block_size that should be used to compute the
     164             :  * index.
     165             :  * @returns the index of the block containing @offset.
     166             :  */
     167             : constexpr uint64_t
     168        7049 : block_index(const uint64_t offset, const size_t block_size) {
     169             : 
     170        7049 :     using gkfs::utils::arithmetic::log2;
     171             : 
     172             :     // This check is automatically removed in release builds
     173        7049 :     assert(is_power_of_2(block_size));
     174        7049 :     return align_left(offset, block_size) >> log2(block_size);
     175             : }
     176             : 
     177             : 
     178             : /**
     179             :  * Compute the number of blocks involved in an operation affecting the
     180             :  * regions from [@offset, to @offset + @count).
     181             :  *
     182             :  * @note This function assumes that @block_size is a power of 2.
     183             :  * @note This function assumes that @offset + @count does not
     184             :  * overflow.
     185             :  *
     186             :  * @param [in] offset the operation's initial offset.
     187             :  * @param [in] size the number of bytes affected by the operation.
     188             :  * @param [in] block_size the block size that should be used to compute the
     189             :  * number of blocks.
     190             :  * @returns the number of blocks affected by the operation.
     191             :  */
     192             : constexpr std::size_t
     193     2750753 : block_count(const uint64_t offset, const size_t size, const size_t block_size) {
     194             : 
     195     2750753 :     using gkfs::utils::arithmetic::log2;
     196             : 
     197             :     // These checks are automatically removed in release builds
     198     2750753 :     assert(is_power_of_2(block_size));
     199             : 
     200             : #if defined(__GNUC__) && !defined(__clang__)
     201     2750753 :     assert(!__builtin_add_overflow_p(offset, size, uint64_t{0}));
     202             : #else
     203             :     assert(offset + size > offset);
     204             : #endif
     205             : 
     206     2750753 :     const uint64_t first_block = align_left(offset, block_size);
     207     2750753 :     const uint64_t final_block = align_left(offset + size, block_size);
     208     2750753 :     const size_t mask = -!!size; // this is either 0 or ~0
     209             : 
     210     2750753 :     return (((final_block >> log2(block_size)) -
     211     5501506 :              (first_block >> log2(block_size)) +
     212     2750753 :              !is_aligned(offset + size, block_size))) &
     213     2750753 :            mask;
     214             : }
     215             : 
     216             : } // namespace gkfs::utils::arithmetic
     217             : 
     218             : #endif // GKFS_COMMON_ARITHMETIC_HPP

Generated by: LCOV version 1.16