如何安全、明智地确定指针是否指向指定缓冲区的某处？

Question

我正在寻找实现一个函数来确定给定指针是否指向给定缓冲区。规格：

template <typename T>
bool points_into_buffer (T *p, T *buf, std::size_t len);

如果有n、0 <= n && n < len，其中p == buf + n、returns true.

否则，如果有n、0 <= n && n < len * sizeof(T)，reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n，则行为未定义。

否则，returns false.

明显的实现看起来像

template <typename T>
bool points_into_buffer (T *p, T *buf, std::size_t len) {
    return p >= buf && p < buf + len;
}

但这在标准 C++ 中具有未定义的行为：指针的关系比较仅针对指向同一数组的指针定义。

另一种方法是使用标准库的比较器对象：

template <typename T>
bool points_into_buffer (T *p, T *buf, std::size_t len) {
    return std::greater_equal<T *>()(p, buf) && std::less<T *>()(p, buf + len);
}

当我希望它达到 return true 时保证 return true，并避免未定义的行为，但允许误报：给定 int a; int b;，它允许 points_into_buffer(&a, &b, 1).

的结果为 true

可以循环实现：

template <typename T>
bool points_into_buffer (T *p, T *buf, std::size_t len) {
    for (std::size_t i = 0; i != len; i++)
        if (p == buf + i)
            return true;
    return false;
}

但是，编译器无法优化该循环。

是否有一种有效的写法，在启用当前编译器和优化的情况下，结果是在恒定时间内确定的？

Answer 1

如果您将指针转换为足够大的无符号整数并添加字节数而不是对象数，未定义的行为就会消失。

template <typename T>
bool points_into_buffer (T *p, T *buf, std::size_t len) {
    uintptr_t ip = (uintptr_t)p;
    uintptr_t ibuf = (uintptr_t)buf;
    return ip >= ibuf && ip < (ibuf + sizeof(T) * len);
}

此代码不会检测 p 是否未正确对齐，但您可以轻松添加带有 %.

的测试

Answer 2

据我所知，这是我为所有可能的实现所追求的功能的可移植实现：

#ifdef UINTPTR_MAX

bool points_into_buffer(std::uintptr_t p, std::uintptr_t buf, std::size_t len)
{
  const auto diff = p + 0u - buf;
  if (diff < len)
    // #1
    if (reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + diff)
      return true;
  for (std::size_t n = 0; n != len; n++)
    if (reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n)
      // #2
      if (reinterpret_cast<char *>(p) - reinterpret_cast<char *>(buf) != diff)
        return true;
  return false;
}

template <typename T>
bool points_into_buffer(T *p, T *buf, std::size_t len)
{
  return points_into_buffer(reinterpret_cast<std::uintptr_t>(p),
                            reinterpret_cast<std::uintptr_t>(buf),
                            len * sizeof(T));
}

#else

template <typename T>
bool points_into_buffer(T *p, T *buf, std::size_t len)
{
  for (std::size_t n = 0; n != len; n++)
    if (p == buf + n)
      return true;
  return false;
}

#endif

一般来说，diff不保证有一个有意义的值。但这没关系：函数 returns true 当且仅当它找到一些 n 使得 reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n。它仅使用 diff 作为提示来更快地找到 n 的值。

它依赖于编译器优化条件，这些条件通常在编译时不一定是已知的，但在特定平台的编译时是已知的。标记为 #1 和 #2 的 if 语句的条件由 GCC 在编译时确定为始终分别为 true 和 false，因为 diff 被定义，允许 GCC 看到循环内没有执行任何有用的操作，并允许删除整个循环。

points_into_buffer<char> 和 points_into_buffer<int> 的生成代码如下所示：

bool points_into_buffer(char*, char*, unsigned int):
        movl    4(%esp), %edx
        movl    , %eax
        movl    12(%esp), %ecx
        subl    8(%esp), %edx
        cmpl    %edx, %ecx
        ja      L11
        xorl    %eax, %eax
L11:    rep ret

bool points_into_buffer(int*, int*, unsigned int):
        movl    4(%esp), %edx
        movl    12(%esp), %eax
        subl    8(%esp), %edx
        leal    0(,%eax,4), %ecx
        movl    , %eax
        cmpl    %edx, %ecx
        ja      L19
        xorl    %eax, %eax
L19:    rep ret

在 std::uintptr_t 不可用或地址比简单整数更复杂的系统上，将使用循环代替。

如何安全、明智地确定指针是否指向指定缓冲区的某处？

How do I safely and sensibly determine whether a pointer points somewhere into a specified buffer?

c++

pointers

undefined-behavior