How to check that two arbitrary memory ranges are not overlapped in c/c++

Question

Let say I need to implement a very general utility function which has to copy one buffer to another. According to the c/c++ standard using memcpy with overlapped memory is UB on the other hand memmove is potentially slower. I would like to be able to use memcmp implementation whenever I can and switch to memmove when I have to.

void copy(const void* src, int src_size, void* dst, int dst_size, int count)
{
    assert(src);
    asserc(dst);
    assert(0 < count);
    assert(count < src_size);
    assert(count < dst_size);

    if (are_overlaped(src, dst, count))
        std::memove(dst, src, count);
    else
        std::memcmp(dst, src, count);
}

According to the c/c++ standard, it is UB to compare or subtract to arbitrary pointers. In order to write a naive implementation of are_overlaped both pointers have to points to items of the same array. So this is UB in general case

bool are_overlaped(const void* first, const void* second, int size)
{
    assert(first);
    asserc(second);
    assert(0 < size);

    return std::abs(reinterpret_cast<const char*>(first)
        - reinterpret_cast<const char*>(second)) < size;
}

So my question is how to implement are_overlaped correctly for arbitrary pointers? Or is there a standard way to check this?

PS. Example with copy is just a context for a better understanding. I want to know how to implement are_overlaped rather than use or implement copy.

Answer 1

Don't do that.
memmove is as efficient as memcpy, except for one check for overlap.

Answer 2

Whereas comparison on pointer is UB if those 2 pointers don't belong to same array, std::less can be used, something like:

template <typename T>
bool are_overlaped(const T* first, const T* second, int size)
{
    // `first` and `second` should be arrays of size greater or equal to `size`
    return first && second
    && (!std::less<>{}(second, first) && std::less<>{}(second, first + size)
      || !std::less<>{}(first, second) && std::less<>{}(first, second + size));


}

Answer 3

I think a lot about both answers. Even though @Yakk - Adam Nevraumont is perfectly correct his solution is unlikely usable. On the other hand, @Jarod42 's answer is usable but not 100% correct. Can we mix both of the solutions having enough correctness for the reasonable price? I think this is possible with a limitation of course.

bool may_be_overlapped(void const* lhs, size_t lhs_size_in_bytes, void const* rhs, size_t rhs_size_in_bytes)
{
    if (lhs_size_in_bytes == 0 || rhs_size_in_bytes == 0)
        return false;

    assert(lhs != nullptr);
    assert(rhs != nullptr);

    if (std::less<>(reiterpret_cast<const char*>(lhs) + lhs_size_in_bytes - 1, rhs)
        || std::less<>(reiterpret_cast<const char*>(rhs) + rhs_size_in_bytes - 1, lhs))
        return false;

    return true;
}

// wide contract
[[nodiscard]]
bool safe_copy(void* dst, size_t dst_size_in_bytes, const void* src, size_t src_size_in_bytes, size_t count_in_bytes)
{
    if (count_in_bytes == 0)
        return true;

    if (dst == nullptr || src == nullptr
     || dst_size_in_bytes < count_in_bytes
     || src_size_in_bytes < count_in_bytes)
    {
        return false;
    }

    std::memmove(dst, src, count_in_bytes);
    return true;
}

// narrow contract
void not_overlaped_copy(void* dst, size_t dst_size_in_bytes, const void* src, size_t src_size_in_bytes, size_t count_in_bytes)
{
    if (count_in_bytes == 0)
        return;

    assert(dst != nullptr);
    assert(src != nullptr);
    assert(dst_size_in_bytes >= count_in_bytes);
    assert(src_size_in_bytes >= count_in_bytes);
    assert(!may_be_overlapped(dst, count_in_bytes, src, count_in_bytes));

    std::memcpy(dst, src, count_in_bytes);
}

// narrow contract
void copy(void* dst, size_t dst_size_in_bytes, const void* src, size_t src_size_in_bytes, size_t count_in_bytes)
{
    if (count_in_bytes == 0)
        return;

    assert(dst != nullptr);
    assert(src != nullptr);
    assert(dst_size_in_bytes >= count_in_bytes);
    assert(src_size_in_bytes >= count_in_bytes);

    std::memmove(dst, src, count_in_bytes);
}

PS. If you do really need are_overlapped which can be used regardless of memory copy context then following is a set_intersection version of Yakk's solution:

bool are_overlapped(void const* lhs, size_t lhs_size_in_bytes, void const* rhs, size_t rhs_size_in_bytes)
{
    if (lhs_size_in_bytes == 0 || rhs_size_in_bytes == 0)
        return false;

    assert(lhs != nullptr);
    assert(rhs != nullptr);

    auto first1 = reiterpret_cast<const char*>(lhs);
    const auto last1 = first1 + lhs_size_in_bytes - 1;
    auto first2 = reiterpret_cast<const char*>(rhs);
    const auto last2 = first2 + rhs_size_in_bytes - 1;

    if (std::less<>(last1, first2) || std::less<>(last2, first1))
        return false;

    while (first1 <= last1 && first2 <= last2)
    {
        if (std::less<>(first1, first2))
            ++first1;
        else if (std::less<>(first2, first1))
            ++first2;
        else
            retun true;
    }

    return false;
}

Answer 4

This is legal:

bool inside( void const* a, void const* b, size_t count ){
  if (count==0) return false;
  if (count==1) return ptr_equal(a,b);
  return inside(a, b, count/2)||inside(a,static_cast<char const*>(b)+count/2, count-count/2 );
}

where ptr_equal(a,b) does either !std::less<>{}(a,b)&&!std::less<>{}(b,a) or a==b; I think the 2nd one is well defined, but first one is equivalent and will be well defined.

Next

bool overlap(void const* lhs, size_t lhs_size, void const* rhs, size_t rhs_size ){
  if (!lhs_size || !rhs_size) return false;
  auto a0 = static_cast<char const*>(lhs);
  auto b0 = static_cast<char const*>(rhs);
  return inside(a0, b0, rhs_size) || inside(a0+lhs_size-1, b0, rhs_size) || inside(b0, a0, lhs_size) || inside(b0+rhs_size-1, a0, lhs_size);
}

and pray your optimizer does its job on sane platforms. Well, check.