如何安全合理地确定指针是否指向某个指定缓冲区？

Question

我正在寻找一个函数来确定给定的指针是否指向给定的缓冲区.规格:

---

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

如果有一些n,0 <= n && n < len为这p == buf + n,退货true.

否则,如果有一些n,0 <= n && n < len * sizeof(T)为它reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n的行为是不确定的.

否则,返回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);
}

保证true在我希望它返回时返回true,并避免未定义的行为,但允许误报:给定int a; int b;,它允许结果true为points_into_buffer(&a, &b, 1).

它可以实现为循环:

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

据我所知,这是我所能实现的功能的可移植实现:

#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不保证具有有意义的值.但是没关系:true当且仅当它找到一些n这样的函数时,函数才会返回reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n.它仅用diff作提示来n更快地找到值.

它依赖于编译器优化条件,这些条件通常在编译时不一定是已知的,但在编译时对于特定平台是已知的.由于如何定义,GCC在编译时if标记为#1和#2由GCC确定的语句的条件总是true和,允许GCC看到在循环内没有执行有用的操作,并允许丢弃整个循环.falsediff

生成的代码points_into_buffer<char>和points_into_buffer<int>看起来像:

bool points_into_buffer(char*, char*, unsigned int):
        movl    4(%esp), %edx
        movl    $1, %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    $1, %eax
        cmpl    %edx, %ecx
        ja      L19
        xorl    %eax, %eax
L19:    rep ret

在std::uintptr_t不可用的系统上,或者地址比简单整数更复杂的系统中,使用循环.