C(UB를 호출하지 않음)에서 두 개체가 겹치는지 확인할 수 있습니까?

C(UB를 호출하지 않음)에서 두 개체가 겹치는지 확인할 수 있습니까?

두 포인터를 비교할 때, 그 결과는 가리키는 객체의 주소 공간에서의 상대적인 위치에 따라 달라집니다.개체 또는 불완전한 유형에 대한 두 포인터가 둘 다 동일한 개체를 가리키거나 둘 다 동일한 배열 개체의 마지막 요소를 지나 하나를 가리키면 동일한 개체를 비교합니다.가리키는 개체가 동일한 집계 개체의 멤버인 경우 나중에 선언된 구조 구성원에 대한 포인터는 구조의 이전에 선언된 구성원에 대한 포인터보다 크고, 첨자 값이 더 큰 배열 요소에 대한 포인터는 더 낮은 동일한 배열의 요소에 대한 포인터보다 큽니다.동일한 연합 개체의 구성원에 대한 모든 포인터가 동일하게 비교됩니다.식 P가 배열 개체의 요소를 가리키고 식 Q가 동일한 배열 개체의 마지막 요소를 가리키면 포인터 식 Q+1이 P보다 크게 비교됩니다.다른 모든 경우에는 동작이 정의되지 않습니다.

동일한 유형의 배열을 참조하는 포인터가 두 개 있는데 그 배열의 길이가 UB를 호출하지 않고 겹치지 않는지 확인할 수 있습니까?

비고: 저는 실생활(실행 등)에서 할 수 있다는 것을 보여주는 예에는 관심이 없습니다.그러니 코드를 보여주지 말아주세요 (UB가 무료라는 것을 [표준적으로] 증명할 수 없는 한).

비표준 접근 방식만큼 효율적이지는 않지만 표준 C에서는 가능합니다.

C11 표준의 섹션 6.5.8p5에서 인용된 위의 구절은 관계형 운영자에게 적용됩니다.<,>,<=,그리고.>=..==그리고.!=이 제한이 없습니다.동일성을 위해 임의의 두 객체 포인터를 비교하는 데 사용할 수 있습니다.

구체적으로 평등 연산자에 관한 섹션 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;
}

수용된 답변은 언어 표준의 적절한 섹션을 참조하여 OP의 질문을 다루고 있습니다.그러나 제1 객체(어레이)가 제2 객체(어레이)에 의해 완전히 중첩되지만 제2 객체의 시작 요소와 끝 요소를 제외하는 방식으로 제1 객체(어레이)가 제2 객체(어레이)의 하위 집합일 경우, 즉 이와 같이 중첩되는 코드의 제2 스니펫은 실패할 것입니다 -

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

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

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

이 게시물은 @dbush post second code snippet의 문제를 해결하기 위한 몇 가지 수정 사항일 뿐이며 문제가 되는 요소 유형의 배열 크기를 고려하여 조금 더 효율적으로 만들 수 있습니다.

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

휴대용으로는 안 됩니다.몇 가지 거짓 부정이 있습니다.

카운터 예제 #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 ~ 0xE0 주소로 나타납니다.FF. 그러나 0xE100 ~ 0xE1에서도 나타납니다.FF. 실제로 주소 공간에 16번, 0xEz00~0xEz 블록에 모두 나타납니다.FF. 더 나쁜 것은 이 블록들 각각이 물리적으로 같은 것을 가리킨다는 것입니다.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겹친

하지만 운영 체제에 따라 포인터가xx그리고.yy공정 B는 겹쳐진 물체처럼 보이지 않을 수 있습니다.하지만 실제로는 서로 겹치는 물체를 가리키기도 합니다.그래서 당신은 거짓 음성을 얻게 될 것입니다.

이론적으로 여러 프로세스에 걸쳐 중복 여부를 확인하는 함수를 작성하는 것이 가능합니까?그럴지도 모르지만, 제가 그 문제를 더 어렵게 만들 수 있다는 것을 명심하세요.하위 집합을 생성할 수 있습니다.xx그리고.yy그것은 여전히 겹칩니다. 저는 B 프로세스에서 세 번째 프로세스까지 메모리를 공유할 수 있습니다.어떤 경우에도 그러한 솔루션은 휴대가 불가능합니다.

카운터 예제 #3: 8086 far pointers

원래 IBM PC의 8086 아키텍처는 "세분화"라고 불리는 메모리 매핑의 한 종류를 사용했습니다.세그먼트라고 불리는 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서로 다른 비트 패턴을 가지고 있기 때문에 거짓인 것입니다.다른 컴파일러들은 (성능 패널티와 함께) 연산을 하고 참으로 돌아올 것입니다.r을 선택할 수 .#pragma.

---

OP는 이러한 예들이 "표준에 부합하지 않는" 컴파일러들을 나타낸다고 불평합니다.은 만약 두 면,다를 .==.

만약 당신이 그런 언어 변호사가 되려 한다면, 어떤 컴파일러도 표준에 부합하지 않습니다.gcc도 아니고 마이크로소프트 C도 아닙니다. (컴파일러 두 명이 자신들의 적합성을 자랑합니다.)기본적으로 C 컴파일러를 가진 모든 시스템은 어느 정도의 메모리 앨리어싱을 가지고 있습니다(반례 #1).그래서 모든 C 컴파일러는 두개를 허용한 죄가 있습니다.!=포인터는 같은 것을 가리킵니다.

반면, 표준을 문자 그대로의 의미가 아닌 의도된 의미로 해석하면 해당 컴파일러는 표준을 준수합니다.

네, 엣지 케이스입니다.대부분의 프로그램은 #1이 숨겨져 있는 사용자 공간에 있습니다.공유 메모리(#2)를 사용하는 프로그램은 거의 없습니다.그리고 세그먼트 메모리 모델에서의 프로그래밍을 좋아하는 사람은 아무도 없습니다(#3).그러나 이와 같은 예외로 인해 표준에는 정의되지 않은 동작의 인스턴스가 매우 많습니다. 한 경우에 작동하는 많은 것들이 다른 경우에는 그렇게 작동할 수 없습니다.

우리가 언어 변호사가 될거라면, 내가 너한테 이걸 제기할게.

// 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] 분명히, 이것은 결코 휴대용이 아니지만, 대부분의 경우 이것은 작동할 것입니다.

---

[1]: ISO/IEC 9899:2018, § 6.3.2.3, par. 6 ("어떤 포인터 유형이든 정수형으로 변환 가능합니다.이전에 지정한 것을 제외하고는 구현이 정의된 결과입니다.")

데이터 보존에 대해서는 아무 말도 안 하셨으니까요.

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

이것은 완전히 잘 정의되어 있습니다.

표준이 기술하기 위해 작성된 언어로, 등비 비교 연산자를 사용하여 다른 개체 내의 가능한 모든 주소로 각 개체의 시작 주소를 확인할 수 있습니다.개체가 겹치면 이러한 비교를 통해 일치를 보고해야 합니다.

그러나 clang과 gcc에 의해 처리되는 언어에서 등식 비교 연산자는 각 개체에서 바이트를 식별하는 두 개의 포인터, 또는 각 점이 일부 개체의 마지막 바이트를 바로 지난 두 개의 포인터, 또는 위의 범주 중 하나의 널 포인터와 포인터와 함께 사용될 수 있습니다.처음 두 범주에서 각각 하나의 포인터와 함께 사용할 수 없습니다.

처음 두 범주의 포인터 간의 비교를 포함하는 코너 케이스를 clang과 gcc가 안정적으로 처리할 수 없는 것은 몇 년 전 두 컴파일러의 버그 보고 시스템에 입력되었습니다. 두 컴파일러 모두 이러한 경우에 발생하는 "최적화"를 계속한다는 사실은 유지 관리자가 해당 언어가 그러한 경우를 금지한다고 믿는다는 것을 의미합니다.이를 수행하는 모든 프로그램의 동작을 비교하고 어떠한 요구사항도 부과하지 않습니다.

선형 시간에서 일부 i의 경우 &obj1[i] == &obj2[0]인지, 일부 i의 경우 &obj1[0] == &obj2[i]인지 확인하고 중복 여부를 결정할 수 있습니다.

이를 수행하기 전에 obj1과 obj2를 uintr_t에 캐스팅하고, uintr_t에 캐스팅된 포인터가 char*와 유사하게 동작한다고 (증거 없이) 가정하고, &obj1[i]가 &obj2[j]와 같아야 하며, 두 지수 모두 유효합니다.등식 또는 부등식에 대해 관련 없는 포인터를 비교하는 것은 UB를 호출하지 않기 때문에 배열이 이런 방식으로 중첩되어 있음을 증명할 수 있습니다.구현이 이상하다면 이는 도움이 되지 않을 뿐만 아니라 잘못된 결과를 제공하지도 않습니다.그리고 배열이 겹치지 않으면 역시 작동하지 않습니다.이 경우 첫 번째 방법으로 돌아갑니다.

문제는 이 객체들이 다른(그리고 다른) 객체들을 멤버(하위 객체)로 가지고 있을 때 더 복잡해질 수 있습니다.끈들의 배열처럼 말입니다.

중복 문제는 프로그램 논리 문제에 더 가깝습니다. 모든 개체는 자신의 메모리 또는 데이터 저장소의 일부 공유 데이터를 가지고 있어야 하며, 이 데이터는 아무도 가지고 있지 않기 때문입니다.문제에 따라 구성 요소의 시작 주소와 끝 주소를 모두 유지하고 주소만 비교하는 추가 메모리 구조 배열을 사용할 수도 있습니다.

언급URL : https://stackoverflow.com/questions/74946095/is-it-possible-in-c-not-invoking-ub-to-check-if-two-objects-overlap