Как безопасно и разумно определить, указывает ли указатель где-то в указанный буфер?

Я ищу реализацию функции, которая определяет, указывает ли данный указатель на данный буфер. Спецификация:

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, поведение undefined.

В противном случае возвращает false.

Очевидная реализация будет выглядеть примерно так:

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

но имеет поведение undefined в стандартном С++: реляционные сравнения указателей определяются только для указателей в один и тот же массив.

Альтернативой может быть использование стандартных объектов сравнения библиотек:

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, и избегает поведения undefined, но допускает ложные срабатывания: данный 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;
}

Однако компиляторы не могут оптимизировать этот цикл.

Есть ли допустимый способ записи, где с включенными текущими компиляторами и оптимизациями результат определяется в постоянное время?

Ответы

Ответ 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.

Он опирается на условия оптимизации компилятора, которые не всегда известны во время компиляции, но известны во время компиляции для конкретной платформы. Условия для операторов if, помеченные как #1 и #2, определяются 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 недоступен или где адреса более сложны, чем простые целые числа, вместо этого используется цикл.

Ответ 2

Если вы наложите указатели на достаточно большие целые числа без знака и добавьте количество байтов вместо количества объектов, поведение undefined исчезнет.

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, но вы можете легко добавить тест с помощью%.