如何安全明智地确定指针是否指向特定缓冲区中的某个位置？

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;，它允许 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;
}

然而，编译器很难优化掉这个循环。

有没有一种有效的方法来编写这个代码，在当前的编译器和启用了优化的情况下，结果可以在常数时间内确定？

- user743382

---

C++11 [comparisons]p8中写道："对于模板greater、less、greater_equal和less_equal，即使内置的运算符<、>、<=、>=不成立，任何指针类型的特化都会产生一个全序。" - user743382

@JeremyLaumon 是的，这就是为什么我在问题中指出它可能会产生错误结果的原因。如果这是一种安全的方法，我就不会问这个问题了。:) （顺便说一下，它不能产生假阴性。当p < q的结果被定义时，std::less<T *>()(p, q)必须给出相同的结果，其他运算符也是如此。） - user743382

从语言律师的角度来看，这并没有什么帮助，但实际上，我们可能会安慰地知道甚至GNU可移植性库（gnulib） 做出了同样的假设，而且似乎还没有报告说这在真实世界的平台上会出现问题。 - 5gon12eder

@jdlugosz 这再次假定一个线性地址空间，这是普遍的，但不普遍，我想避免这种假设。 - user743382

@jdlugosz，已经有一些没有简单线性地址空间的系统了，GNU网站也没有声称有这样的系统。 （至少，在实模式和那些在保护模式下使用段的少数操作系统中，存在x86段+偏移量“fat”指针。）它只是说他们不知道任何一个是“实际移植目标”，这可能是真的。 - user743382

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没有保证具有有意义的值。但是没关系：只要函数找到某个n，使得reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n，函数就会返回true。它只使用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    $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或地址比简单整数更复杂的系统上，将使用循环。

- user743382

---

hvd：明白了。这很不道德，但非常聪明。 - InsideLoop

Answer 2

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

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是否正确对齐，但你可以通过添加一个%的测试来轻松解决。

- Jerem

---

这并不能保证在所有实现上都能正常工作。你假设了一个线性地址空间，这是很普遍的情况，但并不是普适的。 - user743382

好观点。这是一种定义行为（实际上是实现定义），但它可能不是正确的行为。我不确定是否有平台无关的解决方案。 - Jerem