ca-tiling.H

Go to the documentation of this file.

/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
#ifndef CA_TILING_H
#define CA_TILING_H
 
#include <array>
#include <cstddef>
#include <cstdint>
 
#include <ah-errors.H>
 
#include <ca-traits.H>
 
namespace Aleph {
namespace CA {
 
struct Range1D
{
  ca_size_t begin = 0;
  ca_size_t end = 0;
 
  [[nodiscard]] constexpr ca_size_t size() const noexcept
  {
    return end > begin ? end - begin : 0;
  }
 
  [[nodiscard]] constexpr bool empty() const noexcept
  {
    return end <= begin;
  }
};
 
[[nodiscard]] inline constexpr Range1D split_range_balanced(const ca_size_t n,
                                                            const ca_size_t parts,
                                                            const ca_size_t idx) noexcept
{
  if (parts <= 1 or n == 0)
    {
      if (idx == 0)
        return Range1D{0, n};
      return Range1D{n, n};
    }
  if (idx >= parts)
    return Range1D{n, n};
 
  const ca_size_t base = n / parts;
  const ca_size_t rem = n % parts;
  const ca_size_t begin = idx * base + (idx < rem ? idx : rem);
  const ca_size_t extra = idx < rem ? 1 : 0;
  const ca_size_t end = begin + base + extra;
  return Range1D{begin, end};
}
 
[[nodiscard]] inline constexpr bool should_run_sequential(const ca_size_t cells,
                                                          const ca_size_t num_partitions,
                                                          const ca_size_t min_cells) noexcept
{
  return num_partitions <= 1 or cells == 0 or cells < min_cells;
}
 
template <std::size_t Rank>
struct Row_Partition
{
  static_assert(Rank >= 1, "Row_Partition requires Rank >= 1");
 
  [[nodiscard]] static constexpr Range1D slab(const std::array<ca_size_t, Rank> &extents,
                                              const ca_size_t parts,
                                              const ca_size_t idx) noexcept
  {
    return split_range_balanced(extents[0], parts, idx);
  }
};
 
template <std::size_t Rank>
struct Column_Partition
{
  static_assert(Rank >= 1, "Column_Partition requires Rank >= 1");
 
  [[nodiscard]] static constexpr Range1D slab(const std::array<ca_size_t, Rank> &extents,
                                              const ca_size_t parts,
                                              const ca_size_t idx) noexcept
  {
    return split_range_balanced(extents[Rank - 1], parts, idx);
  }
};
 
struct Tile2D_Range
{
  Range1D rows{};
  Range1D cols{};
 
  [[nodiscard]] constexpr ca_size_t size() const noexcept
  {
    return rows.size() * cols.size();
  }
 
  [[nodiscard]] constexpr bool empty() const noexcept
  {
    return rows.empty() or cols.empty();
  }
};
 
struct Block_Partition_2D
{
  [[nodiscard]] static constexpr Tile2D_Range tile(const std::array<ca_size_t, 2> &extents,
                                                   const ca_size_t parts_y,
                                                   const ca_size_t parts_x,
                                                   const ca_size_t tile_index) noexcept
  {
    const ca_size_t py = parts_y == 0 ? 1 : parts_y;
    const ca_size_t px = parts_x == 0 ? 1 : parts_x;
    const ca_size_t total = py * px;
    if (tile_index >= total)
      return Tile2D_Range{Range1D{extents[0], extents[0]}, Range1D{extents[1], extents[1]}};
    const ca_size_t ty = tile_index / px;
    const ca_size_t tx = tile_index % px;
    return Tile2D_Range{split_range_balanced(extents[0], py, ty),
                        split_range_balanced(extents[1], px, tx)};
  }
 
  [[nodiscard]] static constexpr std::array<ca_size_t, 2> factor_partitions(
    const std::array<ca_size_t, 2> &extents, const ca_size_t parts) noexcept
  {
    if (parts <= 1)
      return {1, 1};
 
    // Find the divisor pair (a, b) of `parts` whose ratio b/a best
    // matches cols/rows. Iterate over divisors only; `parts` is small
    // (a few dozen at most) so the linear search is trivial.
    ca_size_t best_y = 1;
    ca_size_t best_x = parts;
    long long best_score = -1;
    const long long rows = static_cast<long long>(extents[0]);
    const long long cols = static_cast<long long>(extents[1]);
 
    for (ca_size_t y = 1; y <= parts; ++y)
      {
        if (parts % y != 0)
          continue;
        const ca_size_t x = parts / y;
        // score = - |rows / y - cols / x| (closer to balanced => better)
        const long long ry = rows / static_cast<long long>(y);
        const long long rx = cols / static_cast<long long>(x);
        long long diff = ry - rx;
        if (diff < 0)
          diff = -diff;
        const long long score = -diff;
        if (score > best_score)
          {
            best_score = score;
            best_y = y;
            best_x = x;
          }
      }
    return {best_y, best_x};
  }
};
 
// ---------------------------------------------------------------------------
// Z-order (Morton) encoding helpers.
//
// They are not used by the default partitioner, but they are documented as
// part of the Phase-5 deliverables and exposed here so that future engines
// (parallel 3D, hashlife streaming) can opt into a cache-friendly visit
// order without having to redefine the bit-twiddling each time.
// ---------------------------------------------------------------------------
 
namespace ca_tiling_detail {
 
inline constexpr std::uint64_t spread_bits_2(const std::uint32_t v) noexcept
{
  std::uint64_t r = 0;
  for (std::size_t i = 0; i < 32; ++i)
    r |= (static_cast<std::uint64_t>(v >> i) & 1ULL) << (2 * i);
  return r;
}
 
inline constexpr std::uint64_t spread_bits_3(const std::uint32_t v) noexcept
{
  std::uint64_t r = 0;
  for (std::size_t i = 0; i < 21; ++i)
    r |= (static_cast<std::uint64_t>(v >> i) & 1ULL) << (3 * i);
  return r;
}
 
}  // namespace ca_tiling_detail
 
[[nodiscard]] inline constexpr std::uint64_t morton_encode_2d(const std::uint32_t x,
                                                              const std::uint32_t y) noexcept
{
  return ca_tiling_detail::spread_bits_2(x) | (ca_tiling_detail::spread_bits_2(y) << 1);
}
 
[[nodiscard]] inline constexpr std::uint64_t morton_encode_3d(const std::uint32_t x,
                                                              const std::uint32_t y,
                                                              const std::uint32_t z) noexcept
{
  return ca_tiling_detail::spread_bits_3(x) | (ca_tiling_detail::spread_bits_3(y) << 1)
       | (ca_tiling_detail::spread_bits_3(z) << 2);
}
 
}  // namespace CA
}  // namespace Aleph
 
#endif  // CA_TILING_H