xref: /llvm-project-15.0.7/libc/src/string/memory_utils/algorithm.h (revision 7f5d7bc8)

//===-- Algorithms to compose sized memory operations ---------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Higher order primitives that build upon the SizedOpT facility.
// They constitute the basic blocks for composing memory functions.
// This file defines the following operations:
// - Skip
// - Tail
// - HeadTail
// - Loop
// - Align
//
// See each class for documentation.
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ALGORITHM_H
#define LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ALGORITHM_H

#include "src/string/memory_utils/address.h" // Address
#include "src/string/memory_utils/utils.h"   // offset_to_next_aligned

#include <stddef.h> // ptrdiff_t

namespace __llvm_libc {

// We are not yet allowed to use asserts in low level memory operations as
// assert itself could depend on them.
// We define this empty macro so we can enable them as soon as possible and keep
// track of invariants.
#define LIBC_ASSERT(COND)

// An operation that allows to skip the specified amount of bytes.
template <ptrdiff_t Bytes> struct Skip {
  template <typename NextT> struct Then {
    template <typename DstAddrT>
    static inline void set(DstAddrT dst, ubyte value) {
      static_assert(NextT::IS_FIXED_SIZE);
      NextT::set(offsetAddr<Bytes>(dst), value);
    }

    template <typename SrcAddrT1, typename SrcAddrT2>
    static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2) {
      static_assert(NextT::IS_FIXED_SIZE);
      return NextT::isDifferent(offsetAddr<Bytes>(src1),
                                offsetAddr<Bytes>(src2));
    }

    template <typename SrcAddrT1, typename SrcAddrT2>
    static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2) {
      static_assert(NextT::IS_FIXED_SIZE);
      return NextT::threeWayCmp(offsetAddr<Bytes>(src1),
                                offsetAddr<Bytes>(src2));
    }

    template <typename SrcAddrT1, typename SrcAddrT2>
    static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2,
                                      size_t runtime_size) {
      static_assert(NextT::IS_RUNTIME_SIZE);
      return NextT::threeWayCmp(offsetAddr<Bytes>(src1),
                                offsetAddr<Bytes>(src2), runtime_size - Bytes);
    }
  };
};

// Compute the address of a tail operation.
// Because of the runtime size, we loose the alignment information.
template <size_t Size, typename AddrT>
static auto tailAddr(AddrT addr, size_t runtime_size) {
  static_assert(IsAddressType<AddrT>::Value);
  return offsetAddrAssumeAligned<1>(addr, runtime_size - Size);
}

// Perform the operation on the last 'Size' bytes of the buffer.
//
// e.g. with
// [1234567812345678123]
// [__XXXXXXXXXXXXXX___]
// [________XXXXXXXX___]
//
// Precondition: `runtime_size >= Size`.
template <typename SizedOpT> struct Tail {
  static_assert(SizedOpT::IS_FIXED_SIZE);
  static constexpr bool IS_RUNTIME_SIZE = true;
  static constexpr size_t SIZE = SizedOpT::SIZE;

  template <typename DstAddrT, typename SrcAddrT>
  static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
    SizedOpT::copy(tailAddr<SIZE>(dst, runtime_size),
                   tailAddr<SIZE>(src, runtime_size));
  }

  template <typename DstAddrT, typename SrcAddrT>
  static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
    SizedOpT::move(tailAddr<SIZE>(dst, runtime_size),
                   tailAddr<SIZE>(src, runtime_size));
  }

  template <typename DstAddrT>
  static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) {
    SizedOpT::set(tailAddr<SIZE>(dst, runtime_size), value);
  }

  template <typename SrcAddrT1, typename SrcAddrT2>
  static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2,
                                     size_t runtime_size) {
    return SizedOpT::isDifferent(tailAddr<SIZE>(src1, runtime_size),
                                 tailAddr<SIZE>(src2, runtime_size));
  }

  template <typename SrcAddrT1, typename SrcAddrT2>
  static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2,
                                    size_t runtime_size) {
    return SizedOpT::threeWayCmp(tailAddr<SIZE>(src1, runtime_size),
                                 tailAddr<SIZE>(src2, runtime_size));
  }
};

// Perform the operation on the first and the last `SizedOpT::Size` bytes of the
// buffer. This is useful for overlapping operations.
//
// e.g. with
// [1234567812345678123]
// [__XXXXXXXXXXXXXX___]
// [__XXXXXXXX_________]
// [________XXXXXXXX___]
//
// Precondition: `runtime_size >= Size && runtime_size <= 2 x Size`.
template <typename SizedOpT> struct HeadTail {
  static_assert(SizedOpT::IS_FIXED_SIZE);
  static constexpr bool IS_RUNTIME_SIZE = true;

  template <typename DstAddrT, typename SrcAddrT>
  static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
    LIBC_ASSERT(runtime_size >= SizedOpT::SIZE);
    SizedOpT::copy(dst, src);
    Tail<SizedOpT>::copy(dst, src, runtime_size);
  }

  template <typename DstAddrT, typename SrcAddrT>
  static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
    LIBC_ASSERT(runtime_size >= SizedOpT::SIZE);
    static constexpr size_t BLOCK_SIZE = SizedOpT::SIZE;
    // The load and store operations can be performed in any order as long as
    // they are not interleaved. More investigations are needed to determine the
    // best order.
    auto head = SizedOpT::load(src);
    auto tail = SizedOpT::load(tailAddr<BLOCK_SIZE>(src, runtime_size));
    SizedOpT::store(tailAddr<BLOCK_SIZE>(dst, runtime_size), tail);
    SizedOpT::store(dst, head);
  }

  template <typename DstAddrT>
  static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) {
    LIBC_ASSERT(runtime_size >= SizedOpT::SIZE);
    SizedOpT::set(dst, value);
    Tail<SizedOpT>::set(dst, value, runtime_size);
  }

  template <typename SrcAddrT1, typename SrcAddrT2>
  static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2,
                                     size_t runtime_size) {
    LIBC_ASSERT(runtime_size >= SizedOpT::SIZE);
    // Two strategies can be applied here:
    // 1. Compute head and tail and compose them with a bitwise or operation.
    // 2. Stop early if head is different.
    // We chose the later because HeadTail operations are typically performed
    // with sizes ranging from 4 to 256 bytes. The cost of the loads is then
    // significantly larger than the cost of the branch.
    if (const uint64_t res = SizedOpT::isDifferent(src1, src2))
      return res;
    return Tail<SizedOpT>::isDifferent(src1, src2, runtime_size);
  }

  template <typename SrcAddrT1, typename SrcAddrT2>
  static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2,
                                    size_t runtime_size) {
    LIBC_ASSERT(runtime_size >= SizedOpT::SIZE &&
                runtime_size <= 2 * SizedOpT::SIZE);
    if (const int32_t res = SizedOpT::threeWayCmp(src1, src2))
      return res;
    return Tail<SizedOpT>::threeWayCmp(src1, src2, runtime_size);
  }
};

// Simple loop ending with a Tail operation.
//
// e.g. with
// [12345678123456781234567812345678]
// [__XXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
// [__XXXXXXXX_______________________]
// [__________XXXXXXXX_______________]
// [__________________XXXXXXXX_______]
// [______________________XXXXXXXX___]
//
// Precondition:
// - runtime_size >= Size
template <typename SizedOpT> struct Loop {
  static_assert(SizedOpT::IS_FIXED_SIZE);
  static constexpr bool IS_RUNTIME_SIZE = true;
  static constexpr size_t BLOCK_SIZE = SizedOpT::SIZE;

  template <typename DstAddrT, typename SrcAddrT>
  static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
    size_t offset = 0;
    do {
      SizedOpT::copy(offsetAddrMultiplesOf<BLOCK_SIZE>(dst, offset),
                     offsetAddrMultiplesOf<BLOCK_SIZE>(src, offset));
      offset += BLOCK_SIZE;
    } while (offset < runtime_size - BLOCK_SIZE);
    Tail<SizedOpT>::copy(dst, src, runtime_size);
  }

  // Move forward suitable when dst < src. We load the tail bytes before
  // handling the loop.
  //
  // e.g. Moving two bytes
  // [   |       |       |       |       |]
  // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
  // [_________________________LLLLLLLL___]
  // [___LLLLLLLL_________________________]
  // [_SSSSSSSS___________________________]
  // [___________LLLLLLLL_________________]
  // [_________SSSSSSSS___________________]
  // [___________________LLLLLLLL_________]
  // [_________________SSSSSSSS___________]
  // [_______________________SSSSSSSS_____]
  template <typename DstAddrT, typename SrcAddrT>
  static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
    const auto tail_value =
        SizedOpT::load(tailAddr<BLOCK_SIZE>(src, runtime_size));
    size_t offset = 0;
    do {
      SizedOpT::move(offsetAddrMultiplesOf<BLOCK_SIZE>(dst, offset),
                     offsetAddrMultiplesOf<BLOCK_SIZE>(src, offset));
      offset += BLOCK_SIZE;
    } while (offset < runtime_size - BLOCK_SIZE);
    SizedOpT::store(tailAddr<BLOCK_SIZE>(dst, runtime_size), tail_value);
  }

  // Move backward suitable when dst > src. We load the head bytes before
  // handling the loop.
  //
  // e.g. Moving two bytes
  // [   |       |       |       |       |]
  // [___XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX___]
  // [___LLLLLLLL_________________________]
  // [_________________________LLLLLLLL___]
  // [___________________________SSSSSSSS_]
  // [_________________LLLLLLLL___________]
  // [___________________SSSSSSSS_________]
  // [_________LLLLLLLL___________________]
  // [___________SSSSSSSS_________________]
  // [_____SSSSSSSS_______________________]
  template <typename DstAddrT, typename SrcAddrT>
  static inline void move_backward(DstAddrT dst, SrcAddrT src,
                                   size_t runtime_size) {
    const auto head_value = SizedOpT::load(src);
    ptrdiff_t offset = runtime_size - BLOCK_SIZE;
    do {
      SizedOpT::move(offsetAddrMultiplesOf<BLOCK_SIZE>(dst, offset),
                     offsetAddrMultiplesOf<BLOCK_SIZE>(src, offset));
      offset -= BLOCK_SIZE;
    } while (offset >= 0);
    SizedOpT::store(dst, head_value);
  }

  template <typename DstAddrT>
  static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) {
    size_t offset = 0;
    do {
      SizedOpT::set(offsetAddrMultiplesOf<BLOCK_SIZE>(dst, offset), value);
      offset += BLOCK_SIZE;
    } while (offset < runtime_size - BLOCK_SIZE);
    Tail<SizedOpT>::set(dst, value, runtime_size);
  }

  template <typename SrcAddrT1, typename SrcAddrT2>
  static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2,
                                     size_t runtime_size) {
    size_t offset = 0;
    do {
      if (uint64_t res = SizedOpT::isDifferent(
              offsetAddrMultiplesOf<BLOCK_SIZE>(src1, offset),
              offsetAddrMultiplesOf<BLOCK_SIZE>(src2, offset)))
        return res;
      offset += BLOCK_SIZE;
    } while (offset < runtime_size - BLOCK_SIZE);
    return Tail<SizedOpT>::isDifferent(src1, src2, runtime_size);
  }

  template <typename SrcAddrT1, typename SrcAddrT2>
  static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2,
                                    size_t runtime_size) {
    size_t offset = 0;
    do {
      if (int32_t res = SizedOpT::threeWayCmp(
              offsetAddrMultiplesOf<BLOCK_SIZE>(src1, offset),
              offsetAddrMultiplesOf<BLOCK_SIZE>(src2, offset)))
        return res;
      offset += BLOCK_SIZE;
    } while (offset < runtime_size - BLOCK_SIZE);
    return Tail<SizedOpT>::threeWayCmp(src1, src2, runtime_size);
  }
};

// Aligns using a statically-sized operation, then calls the subsequent NextT
// operation.
//
// e.g. A 16-byte Destination Aligned 32-byte Loop Copy can be written as:
// Align<_16, Arg::Dst>::Then<Loop<_32>>::copy(dst, src, runtime_size);
enum class Arg { _1, _2, Dst = _1, Src = _2, Lhs = _1, Rhs = _2 };
template <typename SizedOpT, Arg AlignOn = Arg::_1> struct Align {
  static_assert(SizedOpT::IS_FIXED_SIZE);

  template <typename NextT> struct Then {
    static_assert(NextT::IS_RUNTIME_SIZE);

    template <typename DstAddrT, typename SrcAddrT>
    static inline void copy(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
      SizedOpT::copy(dst, src);
      auto aligned = align(dst, src, runtime_size);
      NextT::copy(aligned.arg1, aligned.arg2, aligned.size);
    }

    // Move forward suitable when dst < src. The alignment is performed with
    // an HeadTail operation of size ∈ [Alignment, 2 x Alignment].
    //
    // e.g. Moving two bytes and making sure src is then aligned.
    // [  |       |       |       |      ]
    // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_]
    // [____LLLLLLLL_____________________]
    // [___________LLLLLLLL______________]
    // [_SSSSSSSS________________________]
    // [________SSSSSSSS_________________]
    //
    // e.g. Moving two bytes and making sure dst is then aligned.
    // [  |       |       |       |      ]
    // [____XXXXXXXXXXXXXXXXXXXXXXXXXXXX_]
    // [____LLLLLLLL_____________________]
    // [______LLLLLLLL___________________]
    // [_SSSSSSSS________________________]
    // [___SSSSSSSS______________________]
    template <typename DstAddrT, typename SrcAddrT>
    static inline void move(DstAddrT dst, SrcAddrT src, size_t runtime_size) {
      auto aligned_after_begin = align(dst, src, runtime_size);
      // We move pointers forward by Size so we can perform HeadTail.
      auto aligned = aligned_after_begin.stepForward();
      HeadTail<SizedOpT>::move(dst, src, runtime_size - aligned.size);
      NextT::move(aligned.arg1, aligned.arg2, aligned.size);
    }

    // Move backward suitable when dst > src. The alignment is performed with
    // an HeadTail operation of size ∈ [Alignment, 2 x Alignment].
    //
    // e.g. Moving two bytes backward and making sure src is then aligned.
    // [  |       |       |       |      ]
    // [____XXXXXXXXXXXXXXXXXXXXXXXX_____]
    // [ _________________LLLLLLLL_______]
    // [ ___________________LLLLLLLL_____]
    // [____________________SSSSSSSS_____]
    // [______________________SSSSSSSS___]
    //
    // e.g. Moving two bytes and making sure dst is then aligned.
    // [  |       |       |       |      ]
    // [____XXXXXXXXXXXXXXXXXXXXXXXX_____]
    // [ _______________LLLLLLLL_________]
    // [ ___________________LLLLLLLL_____]
    // [__________________SSSSSSSS_______]
    // [______________________SSSSSSSS___]
    template <typename DstAddrT, typename SrcAddrT>
    static inline void move_backward(DstAddrT dst, SrcAddrT src,
                                     size_t runtime_size) {
      const auto dst_end = offsetAddrAssumeAligned<1>(dst, runtime_size);
      const auto src_end = offsetAddrAssumeAligned<1>(src, runtime_size);
      auto aligned_after_end = align(dst_end, src_end, 0);
      // We move pointers back by 2 x Size so we can perform HeadTail.
      auto aligned = aligned_after_end.stepBack().stepBack();
      HeadTail<SizedOpT>::move(aligned.arg1, aligned.arg2, aligned.size);
      NextT::move_backward(dst, src, runtime_size - aligned.size);
    }

    template <typename DstAddrT>
    static inline void set(DstAddrT dst, ubyte value, size_t runtime_size) {
      SizedOpT::set(dst, value);
      DstAddrT _(nullptr);
      auto aligned = align(dst, _, runtime_size);
      NextT::set(aligned.arg1, value, aligned.size);
    }

    template <typename SrcAddrT1, typename SrcAddrT2>
    static inline uint64_t isDifferent(SrcAddrT1 src1, SrcAddrT2 src2,
                                       size_t runtime_size) {
      if (const uint64_t res = SizedOpT::isDifferent(src1, src2))
        return res;
      auto aligned = align(src1, src2, runtime_size);
      return NextT::isDifferent(aligned.arg1, aligned.arg2, aligned.size);
    }

    template <typename SrcAddrT1, typename SrcAddrT2>
    static inline int32_t threeWayCmp(SrcAddrT1 src1, SrcAddrT2 src2,
                                      size_t runtime_size) {
      if (const int32_t res = SizedOpT::threeWayCmp(src1, src2))
        return res;
      auto aligned = align(src1, src2, runtime_size);
      return NextT::threeWayCmp(aligned.arg1, aligned.arg2, aligned.size);
    }
  };

private:
  static constexpr size_t ALIGN_OP_SIZE = SizedOpT::SIZE;
  static_assert(ALIGN_OP_SIZE > 1);

  template <typename Arg1AddrT, typename Arg2AddrT> struct Aligned {
    Arg1AddrT arg1;
    Arg2AddrT arg2;
    size_t size;

    Aligned stepForward() const {
      return Aligned{offsetAddrMultiplesOf<ALIGN_OP_SIZE>(arg1, ALIGN_OP_SIZE),
                     offsetAddrMultiplesOf<ALIGN_OP_SIZE>(arg2, ALIGN_OP_SIZE),
                     size - ALIGN_OP_SIZE};
    }

    Aligned stepBack() const {
      return Aligned{offsetAddrMultiplesOf<ALIGN_OP_SIZE>(arg1, -ALIGN_OP_SIZE),
                     offsetAddrMultiplesOf<ALIGN_OP_SIZE>(arg2, -ALIGN_OP_SIZE),
                     size + ALIGN_OP_SIZE};
    }
  };

  template <typename Arg1AddrT, typename Arg2AddrT>
  static auto makeAligned(Arg1AddrT arg1, Arg2AddrT arg2, size_t size) {
    return Aligned<Arg1AddrT, Arg2AddrT>{arg1, arg2, size};
  }

  template <typename Arg1AddrT, typename Arg2AddrT>
  static auto align(Arg1AddrT arg1, Arg2AddrT arg2, size_t runtime_size) {
    static_assert(IsAddressType<Arg1AddrT>::Value);
    static_assert(IsAddressType<Arg2AddrT>::Value);
    if constexpr (AlignOn == Arg::_1) {
      auto offset = offset_to_next_aligned<ALIGN_OP_SIZE>(arg1.ptr_);
      return makeAligned(offsetAddrAssumeAligned<ALIGN_OP_SIZE>(arg1, offset),
                         offsetAddrAssumeAligned<1>(arg2, offset),
                         runtime_size - offset);
    } else if constexpr (AlignOn == Arg::_2) {
      auto offset = offset_to_next_aligned<ALIGN_OP_SIZE>(arg2.ptr_);
      return makeAligned(offsetAddrAssumeAligned<1>(arg1, offset),
                         offsetAddrAssumeAligned<ALIGN_OP_SIZE>(arg2, offset),
                         runtime_size - offset);
    } else {
      DeferredStaticAssert("AlignOn must be either Arg::_1 or Arg::_2");
    }
  }
};

} // namespace __llvm_libc

#endif // LLVM_LIBC_SRC_STRING_MEMORY_UTILS_ALGORITHM_H