在C语言中（不涉及未定义行为），是否有可能检查两个对象是否重叠？

Question

当比较两个指针时，结果取决于所指对象在地址空间中的相对位置。如果两个指向对象或不完全类型的指针都指向同一对象，或者都指向同一数组对象的最后一个元素之后，它们将相等。如果所指对象是同一聚合对象的成员，则声明在结构中较晚的结构成员的指针比先前声明的成员的指针更大，并且具有较大下标值的数组元素的指针比具有较低下标值的同一数组的元素的指针更大。所有指向同一联合对象的成员的指针都相等。如果表达式P指向数组对象的一个元素，而表达式Q指向同一数组对象的最后一个元素，则指针表达式Q+1比P更大。在所有其他情况下，行为是未定义的。

如果我们有两个指向相同类型的数组的指针，并且我们有这些数组的长度，我们能否找到这些数组是否不重叠而不引发未定义行为？

备注：我不感兴趣的是展示在实际生活中（实现等）可以完成的示例。因此，请不要展示代码（除非您可以证明[标准上]没有未定义行为）。

- 0___________

---

在定义行为的情况下，对象之间是否可以相互重叠而没有一个是另一个的成员，或者两个都不在同一个显式的union中？ - Karl Knechtel

我想知道你的使用场景是什么？ - jcaron

来到C++的“黑暗面”，使用std::less。 - Ayxan Haqverdili

请注意，std::less允许交错无关数组的元素，因此可能会产生误报。 - Raymond Chen

@RaymondChen，您能详细说明一下吗？这是我定义的一个良好的“overlaps”函数的示例在此处。您能告诉我如何在满足“严格全序”的要求的同时失败吗？ - Ayxan Haqverdili

Answer 1

在标准C中是可能的，但不如非标准方法高效。

上述引用来自第6.5.8p5节的C11标准，适用于关系运算符，即<、>、<=和>=。相等运算符==和!=没有此限制。它们可以用于比较任何两个对象指针的相等性。

具体而言，关于相等运算符的第6.5.9p6节规定：

当且仅当两个空指针都是null指针、都是指向同一对象（包括指向对象及其开头的子对象）或函数、都是指向同一数组对象的最后一个元素之后的一个指针，或者一个是指向一个数组对象的末尾之后的一个指针，另一个是指向紧随第一个数组对象之后的不同数组对象的开头的指针时，两个指针才相等。

你可以通过使用一对unsigned char *来迭代每个对象的字节并比较它们的地址是否相等，以此符合标准的方式来检查重叠。

例如：

int overlap = 0;
unsigned char *o1 = (unsigned char *)&obj1;
unsigned char *o2 = (unsigned char *)&obj2;
for (int i=0; !overlap && i < sizeof obj1; i++) {
    for (int j=0; !overlap && j < sizeof obj2; j++) {
        if (o1 + i == o2 + j) {
            overlap = 1;
        }
    }
}

---

更高效的方法是仅检查一个对象的第一个字节的地址与另一个对象中每个字节的地址，因为如果存在重叠，则一个对象的开头必须在另一个对象内部。

int overlap(const void *p1, size_t size1, const void *p2, size_t size2)
{
    const unsigned char *o1 = p1;
    const unsigned char *o2 = p2;
    for (int i=0; i < size1; i++) {
        if (o1 + i == o2) {
            return 1;
        }
    }
    for (int i=0; i < size2; i++) {
        if (o2 + i == o1) {
            return 1;
        }
    }
    return 0;
}

- dbush

---

评论不适合进行长时间的讨论；此对话已被移至聊天室。 - Henry Ecker

Answer 2

被接受的答案通过引用语言标准的适当部分来回答OP的问题。但是，在第一个对象（数组）是第二个对象（数组）的子集的情况下，被接受的答案中发布的第二段代码将失败，这种情况下第一个对象完全被第二个对象覆盖，但不包括第二个对象的起始和结束元素，即像这样重叠 -

                             object 2
                                |
    +-----------------------------------------------------------+
    |                                                           |
    |                                                           |

    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

        |                                                   |
        |                                                   |
        +---------------------------------------------------+
                                |
                             object 1 (any subset of this region)

这篇文章只是对@dbush的第二个代码片段中出现的问题进行了一些修改，并通过考虑所讨论数组的元素类型的大小，使其更加高效。

/*
 * Parameters:
 * obj1    : Pointer to array1
 * obj1_sz : Size of array1
 * obj2    : Pointer to array2
 * obj2_sz : Size of array2
 * type_sz : Size of type of elements of array
 *
 * Return:
 * 0 - No overlap
 * 1 - Overlap
 *
 * [Assumption: Both array1 and array2 are of same type]
 */

int check_overlap (const void *obj1, size_t obj1_sz, const void *obj2, size_t obj2_sz, size_t type_sz) {
    const unsigned char *pobj1 = obj1;
    const unsigned char *pobj2 = obj2;
    size_t sz1 = obj1_sz;
    size_t sz2 = obj2_sz;

    if (obj1_sz < obj2_sz) {
            pobj1 = obj2;
            pobj2 = obj1;
            sz1 = obj2_sz;
            sz2 = obj1_sz;
    }

    for (size_t i = 0; i < sz1; ++i) {
            if ((pobj1 + (i * type_sz) == pobj2) ||
                (pobj1 + (i * type_sz) == pobj2 + ((sz2 - 1) * type_sz))) {
                    return 1;
            }
    }
    return 0;
}

- H.S.

Answer 3

不具备可移植性。存在几个误判情况。

反例 #1：内存别名

设备（例如 RAM、ROM 或内存映射 I/O）通常不会使用处理器的所有地址引脚。通常，设备需要的地址线数量会连接到处理器的最低位地址线，最高位地址线用于选择设备，中间的地址线未连接：

MSB -------- Address bus -------- LSB
| | ... | |  x x ... x x  | | ... | |
chip select  unconnected   to device

这样的设备可以在地址空间中被称为块。然而，该设备在地址空间中也出现为其他几个块；每个块物理上指向设备上相同的位置！这种效果被称为内存别名，比你想象的要常见得多。

例如，假设一个系统有16位地址。可能使用顶部4个地址线来选择正在寻址的芯片。假设我们将一个设备分配给A15：A12 == 0xE。此外，该设备只有8条地址线输出，因此我们将其连接到A7：A0。

该设备出现在地址0xE000到0xE0FF处。但是，它还出现在0xE100到0xE1FF处。实际上，它在地址空间中出现了16次，在任何块0xEz00到0xEzFF处。更糟糕的是，每个块物理上都指向同一件事情。对0xE123的访问与对0xE223、0xE323、0xE423等的访问相同。

因此，您可以在内存中拥有两个对象，它们似乎指向内存的不同区域，但实际上指向相同的事物：

char *x = (char *)0xE000;
char *y = (char *)0xE300;
if (overlap(x, y, 16)) { ... }

一个天真的实现overlap()会将它们报告为两个不同的对象。但是，它们是同一个对象；对x[]的写入会改变y[]。因此，在这种情况下，您将得到一个错误的负数。正确的overlap()实现需要并依赖于系统内存映射的完全了解，使得这样的函数完全不可移植。

反例#2：共享内存

假设x和y是进程A中重叠的对象。然后，我们使用操作系统在进程A和进程B之间创建共享内存。具体而言，xx是进程B中指向x的共享内存指针，yy是进程B中指向y的共享内存指针。

回到进程A中，编写一个确定x和y确实重叠的函数并不难。

但是，根据操作系统的不同，进程B中的指针xx和yy可能看起来与重叠对象完全不同。但实际上，它们确实指向重叠对象。因此，您将得到一个错误的负面结果。

理论上是否可能编写一个跨进程检查重叠的函数？可能，但请记住，我可以让问题变得更加困难。我可以创建xx和yy的子集，仍然重叠；我可以共享从进程B到第三个进程的内存等。无论如何，任何这样的解决方案都是不可移植的。

反例#3：8086远指针

原始IBM PC上使用了一种称为“分段”的内存映射类型。一个名为“段”的16位寄存器乘以16，然后加上另一个带有“基地址”的16位寄存器，以获得20位物理地址。

需要少于64k内存的程序可以只使用16位基地址，称为“近指针”。但是需要超过64k内存的程序必须维护32位“远指针”，其中包含段和基地址。

由于分段的指针算术，很容易使两个看起来非常不同但指向同一对象的远指针：

far char *x = (far char *)0x12340005L;
far char *y = (far char *)0x10002345L;

在这种情况下，x和y都指向相同的物理地址0x12345，尽管它们的位模式非常不同。

一些编译器会将x == y视为false，因为它们具有不同的位模式。其他编译器会进行计算（带来性能损失）并返回true。还有一些编译器可以通过命令行开关或#pragma让您选择其中一种行为。

---

OP 抱怨这些示例所代表的编译器并不符合“标准规范”。他们认为，如果两个指针确实指向同一对象，则标准要求它们必须进行==比较。

如果您要成为这样的 语言律师，那么没有任何编译器符合标准。不是gcc，也不是微软C（两个自豪地遵守规范的编译器）。基本上每个拥有C编译器的系统都存在某种程度的内存别名（反例＃1）。因此，每个C编译器都允许两个！=指针指向同一个东西。

另一方面，如果您根据其预期含义而不是字面含义解释标准，则这些编译器确实符合标准。

当然，这些是边缘情况。大多数程序都在用户空间中，在那里＃1被隐藏了起来。很少有程序使用共享内存（＃2）。没有人喜欢在分段内存模型（＃3）中进行编程。但是像这样的异常情况是标准具有许多未定义行为实例的原因；许多在一种情况下可以正常工作的事情在其他情况下无法以同样的方式工作。

- DrSheldon

---

如果指针可以相等并引用相同的数组，则实现不符合规范，任何与标准相关的讨论都没有意义。 - 0___________

@0___________：不确定你的评论意思。在我的每个反例中，有两个指针引用相同（或至少重叠）的数组，但它们不相等。 - DrSheldon

那么使用的C编译器不符合规范。如果两个指针引用数组的同一元素，则它们必须相等。如果在您的实现中它们不相等，则您的实现不符合规范。因此，考虑符合规范的C实现，您的示例是错误的。 - 0___________

@0___________我认为这与编译器无关。编译器怎么可能知道特定PCB布局使用的地址引脚呢？ - Marco

即使多个位模式可以表示标识相同存储的地址，但一次只能有一个模式表示特定对象的起始指针，而且一次只能有一个模式标识特定对象的结束。 - supercat

问题在于，创建别名或共享内存的唯一方法是通过标准未涵盖的机制。以符合标准的方式创建的所有对象都将在==方面正确地表现。在标准之外创建的对象自然不受标准约束。实现会小心确保它们自己创建的对象行为正确。如果您开始以非标准的方式创建对象，则实现没有义务以标准方式处理它们。 - Raymond Chen

Answer 4

好吧，如果我们要语言律师的话，我给你提出这个问题：

// SPDX-License-Identifier: CC0-1.0

#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>

bool overlap(const void *p1, size_t s1, const void *p2, size_t s2)
{
    const uintptr_t p1b = (uintptr_t) p1;
    const uintptr_t p2b = (uintptr_t) p2;
    const uintptr_t p1e = (uintptr_t) ((char*) p1 + (s1 - 1));
    const uintptr_t p2e = (uintptr_t) ((char*) p2 + (s2 - 1));
    return (p1b <= p2b && p2b <= p1e)
        || (p2b <= p1b && p1b <= p2e);
}

这段代码调用了“实现定义”的行为，而不是“未定义”的行为。显然，这绝对不是可移植的，但在大多数情况下应该能正常工作。

---

[1]: ISO/IEC 9899:2018，§ 6.3.2.3，第6段（"任何指针类型都可以转换为整数类型。除非先前指定，否则结果是实现定义的。"）。

- nfitzen

---

如果它们重叠，您不能比较指针（或转换为整数），因为它们不引用同一数组。 - 0___________

C标准将比较指针视为未定义行为，但比较整数则不是。转换是否会影响这一点？ - nfitzen

否则，关于比较指针的观点就没有任何意义。您不能比较指针，但可以将指针转换为整数进行比较。那么为什么不能比较指针呢？ - 0___________

因为比较指针并不是完全可移植的，有时整数转换也没有任何语义意义。将比较任意指针这样的核心功能作为可选项是荒谬的标准。 - nfitzen

Answer 5

好的，既然您没有提到保留数据的事情：

#include <stdbool.h>
#include <stddef.h>
#include <string.h>

bool overlaps(void* p1, void* p2, size_t sz1, size_t sz2) {
    if (!p1 || !p2 || !sz1 || !sz2) return false; /* empty ranges ignored */

    memset(p1, 0, sz1);
    memset(p2, 1, sz2);

    return !!memchr(p1, 1, sz1);
}

这是完全定义明确的。

- Ayxan Haqverdili

---

不是每个数组都可修改。UB -> overlaps("123456", "123", 7,4); - 0___________

@0___________ 在你的问题中哪里提到它必须使用不可变数组？你的要求是（1）检测数组是否重叠，（2）不会引起任何未定义的行为。这个答案完美地满足了你对可变数组的所有要求。所有函数都遵循合同工作。 - Ayxan Haqverdili

非常简单 - 我没有提到任何东西，所以它必须能够与任何数组一起使用。 - 0___________

这个回答是恶意遵从的一个例子。就像有人让你帮他们打开一罐泡菜，而你通过把罐子摔在地上来解决问题。 - Raymond Chen

这可能是一个奇怪的答案，但我非常喜欢它：它出人意料，超越传统思维。很容易扩展它，以便保留原始数据（在临时数组中），如果需要的话稍后可以恢复。 - Thomas Mueller

Answer 6

在描述标准的语言中，可以使用相等比较运算符来检查每个对象的起始地址与其他对象中的每个可能地址。如果对象重叠，则应报告一次匹配。

然而，在clang和gcc处理的语言中，相等比较运算符只能用于两个指针，它们分别标识某个对象中的一个字节，或者分别指向某个对象的最后一个字节之后，或者用于空指针和上述任何一类指针之间的指针。不允许使用来自前两类的每个指针进行比较。

clang和gcc无法可靠地处理涉及第一和第二类指针之间比较的边界情况已经在这两个编译器的错误报告系统中输入多年了；这两个编译器继续进行“优化”，而这些“优化”在这种情况下会出现问题，这意味着它们的维护者认为该语言禁止这样的比较，并且对执行这些比较的任何程序的行为没有任何要求。

- supercat

Answer 7

你可以在线性时间内检查 &obj1[i] == &obj2[0] 是否成立，或者 &obj1[0] == &obj2[i] 是否成立，从而确定是否存在重叠。

在进行此操作之前，你需要将 obj1 和 obj2 转换为 uintptr_t 类型，并假设（没有证据）指针转换为 uintptr_t 类型类似于 char*，并计算 i、j 使得根据您的假设 &obj1[i] 应该等于 &obj2[j]，同时两个索引都是有效的。由于比较不相关的指针的相等或不相等不会引发 UB，因此你也许能够通过这种方式证明数组是否重叠。如果你的实现很奇怪，则这并没有什么帮助，但也不会给你错误的结果。如果数组不重叠，这种方法也无效。在这些情况下，你需要回到第一种方法。

- gnasher729

Answer 8

当这些对象有其他（不同的）对象作为成员（子对象）时，问题可能会更加复杂，而这些子对象也可能重叠，例如字符串数组。

您的重叠问题实际上是一个程序逻辑问题，因为每个对象都应该有自己的内存或一些共享数据来自于数据存储，这样就没有人拥有它了。 根据问题的不同，您还可以使用一个额外的内存结构体数组，维护所有组件的起始和结束地址，然后只需比较地址即可。

- Karsten

---

这个问题与任何实际应用无关。language-lawyer标签表明这是严格的语言层面学术问题。 - 0___________