Wie kann ich sicher und sinnvoll feststellen, ob ein Zeiger irgendwo in einen bestimmten Puffer zeigt?

Question

Ich bin auf der Suche nach einer Funktion, die bestimmt, ob ein bestimmter Zeiger auf einen bestimmten Puffer zeigt. Die Spezifikation:

---

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

Wenn es etwas n ist, 0 <= n && n < len, für die p == buf + n, kehrt true.

Andernfalls, wenn es einige n, 0 <= n && n < len * sizeof(T) gibt, für die reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n, ist das Verhalten nicht definiert.

Andernfalls gibt false zurück.

---

Die offensichtliche Umsetzung etwas wie

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

aussehen würde, aber das hat Verhalten in Standard C++ undefined: relationale Vergleiche von Zeigern sind nur für den Zeiger in das gleiche Array definiert.

Eine Alternative wäre die Standard-Bibliothek Vergleich Objekte zu verwenden:

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); 
} 

die true zurückzukehren garantiert, wenn ich es true zurückkehren will, und nicht definiertes Verhalten vermeidet, aber für Fehlalarme erlaubt: gegeben int a; int b; Es ermöglicht ein Ergebnis von true für points_into_buffer(&a, &b, 1).

Es kann als eine Schleife realisiert werden:

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; 
} 

jedoch Compiler Schwierigkeiten haben, zu optimieren, dass die Schleife weg.

Gibt es eine gültige Möglichkeit, dies zu schreiben, wenn bei aktuellen Compilern und Optimierungen das Ergebnis in konstanter Zeit ermittelt wird?

Answer 1

Soweit ich das beurteilen kann, ist dies eine portable Implementierung der Funktion I nach für alle möglichen Implementierungen sind:

#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 

Im Allgemeinen diff keine sinnvollen Wert haben, ist garantiert. Aber das ist in Ordnung: Die Funktion liefert true wenn und nur wenn es n so findet, dass reinterpret_cast<char *>(p) == reinterpret_cast<char *>(buf) + n. Es verwendet nur diff als einen Hinweis, um den Wert von n schneller zu finden.

Es beruht auf dem Compiler Optimierungsbedingungen, die nicht unbedingt zur Kompilierzeit im Allgemeinen bekannt sind, aber zur Kompilierzeit für eine bestimmte Plattform bekannt sind.Die Bedingungen für die if-Anweisungen, die als #1 und #2 gekennzeichnet sind, werden von GCC zur Kompilierungszeit immer true bzw. false bestimmt, weil diff definiert ist, GCC zu erkennen, dass keine nützliche Aktion innerhalb der Schleife ausgeführt wird, und ermöglicht gesamte Schleife gelöscht werden.

Der generierte Code für points_into_buffer<char> und points_into_buffer<int> wie folgt aussieht:

 
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 

Auf Systemen, auf denen std::uintptr_t nicht verfügbar ist, oder wo Adressen komplizierter als einfache, ganze Zahlen sind, wird die Schleife stattdessen verwendet.

Answer 2

Wenn Sie die Zeiger auf groß genug vorzeichenlose Ganzzahlen umwandeln und Anzahl der Bytes anstelle der Anzahl der Objekte hinzufügen, verschwindet das undefinierte Verhalten.

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); 
} 

Dieser Code erkennt nicht, ob p nicht korrekt ausgerichtet ist, aber Sie können problemlos einen Test mit% hinzufügen.