c - 究竟什么时候定义指针差异？

Question

我有一个关于指针和结果类型的差异的问题，ptrdiff_t。

C99 §6.5.6 (9) 说:

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the header. If the result is not representable in an object of that type, the behavior is undefined. In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P)-(Q) has the value i−j provided the value fits in an object of type ptrdiff_t.

§7.18.3 (2) 要求 ptrdiff_t 的范围至少为 [−65535, +65535]

我感兴趣的是结果太大时的未定义行为。我在标准中找不到任何保证至少与 size_t 或类似内容的签名版本相同的范围。所以，现在我的问题是:符合规范的实现能否使 ptrdiff_t 成为带符号的 16 位类型，但 size_t 成为 64 位类型？ [编辑:作为Guntram Blohm指出，16 位有符号最大为 32767，所以我的示例显然不符合] 据我所知，即使实现支持对象很多，我也不能在严格符合代码的情况下对元素超过 65535 的数组进行任何指针减法比这个大。此外，程序甚至可能会崩溃。

基本原理 (V5.10) § 6.5.6 说:

It is important that this type [ptrdiff_t] be signed in order to obtain proper algebraic ordering when dealing with pointers within the same array. However, the magnitude of a pointer difference can be as large as the size of the largest object that can be declared; and since that is an unsigned type, the difference between two pointers can cause an overflow on some implementations.

这可以解释为什么不需要定义指针(指向同一数组的元素)的每个差异，但它不能解释为什么没有对 PTRDIFF_MAX 的限制至少 SIZE_MAX/2(整数除法)。

为了说明，假设T 是任何对象类型并且n 是编译时未知的size_t 的对象。我想为 T 的 n 对象分配空间，我想用分配范围内的地址做指针减法。

size_t half = sizeof(T)>1 ? 1 : 2; // (*)
if( SIZE_MAX/half/sizeof(T)<n ) /* do some error handling */;
size_t size = n * sizeof(T);
T *foo = malloc(size);
if(!foo) /* ... */;

不会严格遵守，我必须这样做

if( SIZE_MAX/sizeof(T) < n || PTRDIFF_MAX < n )

相反。真的是这样吗？如果是这样，有人知道原因吗(即不需要 PTRDIFF_MAX >= SIZE_MAX/2 [edit: changed > to >=] 或类似的东西)？

(*) 第一个版本的一半内容是我在写这篇文章时认识到的，我有

if( SIZE_MAX/2/sizeof(T) < n )

首先，取SIZE_MAX的一半解决Rationale中提到的问题；但后来我意识到，如果 sizeof(T) 为 1，我们只需要将 SIZE_MAX 减半。鉴于此代码，第二个版本(肯定严格符合的版本)不似乎一点也不糟糕。但是，如果我是对的，我还是很感兴趣。

C11保留了§6.5.6(9)的写法，也欢迎C++相关的回答本主题。

Answer 1

给你一个标题中问题的答案:指针差异本身不能用来确定两个指针的差异，最终不会导致未定义的行为。正如您所注意到的，这对于 PTRDIFF_MAX 的系统来说是一个严格的限制。远小于物体的可能尺寸。但是这样的系统很少见(我什么都不知道)，所以如果你有依赖于能够对大对象进行区分的代码，你总是把类似的东西放在

#if PTRDIFF_MAX < SIZE_MAX/2
# error "we need an architecture with sufficiently wide ptrdiff_t"
#endif

但即使在这种情况下(ptrdiff_t 太窄)您也始终能够计算同一较大对象的两个指针之间的差异。

1. 确定两个(p 或 q)中哪个较小。这总是 定义明确。
2. 说 p是较小的，然后测试所有p + i对于 size_t i 从 1 开始直到你到达 q或 i是SIZE_MAX .
3. 如果最后i是SIZE_MAX而你没有达到q差异是不可表示的。否则i最后一个标志是您正在寻找的信息。

这不是很令人满意，但我无法弄清楚如何将该线性算法改进为对数算法:为了避免 UB，我们不允许超出 q。与比较。

而且，正如我所说，您只需要在某些非常奇特的架构的情况下使用它。

编辑:

利用 mafso 获取指针差异的最高有效位的技巧，这可以在 O(log(n)) 中完成。其中 n是所需的距离。首先声明两个内部函数，假设 p < q

// computes the maximum value bit of the pointer difference
//
// assumes that p < q
inline
uintmax_t ptrdiff_maxbit(char const* p, char const* q) {
  uintmax_t len = 1;
  while (p+len <= q-len)
    len <<= 1;
  return len;
}

// compute the pointer difference
//
// assumes that p < q
// assumes that len2 is a power of two
// assumes that the difference is strictly less than 2*len2
inline
uintmax_t ptrdiff_bounded(char const* p, char const* q, uintmax_t len2) {
  if (len2 < 2) return len2;
  uintmax_t len = (len2 >> 1);
  p += len;
  q -= len;
  for (; len; len >>= 1)
    if (p + len <= q) {
      len2 |= len;
      p += len;
    }
  return len2;
}

然后定义计算字节差异的函数并添加一个约定，以防差异在 intmax_t 中无法表示。 :

inline
intmax_t ptrdiff_byte(void const* p0, void const* q0) {
  char const * p = p0;
  char const * q = q0;
  if (p == q) return 0;
  if (p < q) {
    uintmax_t ret = ptrdiff_bounded(p, q, ptrdiff_maxbit(p, q));
    if (ret > (-(INTMAX_MIN+1))+UINTMAX_C(1)) return INTMAX_MIN;
    else return -ret;
  } else {
    uintmax_t ret = ptrdiff_bounded(q, p, ptrdiff_maxbit(q, p));
    if (ret > INTMAX_MAX) return INTMAX_MAX;
    else return ret;
  }
}

最后，一个适合*p类型的宏.

#define ptrdiff(P, Q) (ptrdiff_byte((P), (Q))/(intmax_t)sizeof(*Q))