什么时候确定指针差异？

Question

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

C99§6.5.6(9)说:

当减去两个指针时,两个指针都指向同一个数组对象的元素,或者指向数组对象的最后一个元素的元素; 结果是两个数组元素的下标的差异.结果的大小是实现定义的,其类型(有符号整数类型)ptrdiff_t在头文件中定义.如果结果在该类型的对象中无法表示,则行为未定义.换句话说,如果表达式P和Q分别指向数组对象的第i和第j个元素,则表达式(P) - (Q)具有值i-j,条件是该值适合于对象类型ptrdiff_t.

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

我感兴趣的是如果结果太大则未定义的行为.我无法在标准版本中找到任何与签名版本size_t或类似内容相同的范围.所以,现在我的问题是:符合标准的实现是否可以生成ptrdiff_t带符号的16位类型但size_t64位？[编辑:正如Guntram Blohm指出的那样,16位签名最多为32767,所以我的例子显然不符合]据我所知,我不能在严格符合代码甚至超过65535个元素的数组上做任何指针减法如果实现支持比这大得多的对象.此外,该程序甚至可能崩溃.

理由(V5.10)§6.5.6说:

重要的是要对这个类型[ ptrdiff_t]进行签名,以便在处理同一数组中的指针时获得适当的代数排序.但是,指针差异的大小可以与可以声明的最大对象的大小一样大; 由于这是一个无符号类型,两个指针之间的差异可能会导致某些实现溢出.

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

为了说明,假设T是任何对象类型和编译时未知n的对象size_t.我想为n对象分配空间T,我想用指定范围内的地址进行指针减法.

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[编辑:更改>为>=]或类似的东西)？

(*)第一个版本中的一半是我在写这篇文章时认出的东西,我有

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

首先,用一半SIZE_MAX来解决基本原理中提到的问题; 但后来我意识到SIZE_MAX只要sizeof(T)是1,我们只需要减半.鉴于这个代码,第二个版本(肯定是严格符合的版本)似乎并不那么糟糕.但是,如果我是对的,我仍感兴趣.

C11保留了§6.5.6(9)的措辞,C++相关的答案也很受欢迎.

Answer 1

我记得,在过去,一些16位80x86编译器有"大"或"巨大"数据模型,其中指针有32位,但整数仍然只有16位.这些编译器允许您创建大于65536字节的数组,但是,只有16位的整数,访问不在第一个64K所需指针操作中的元素(这是非常奇怪的,一个由16位段组成的指针值和16位偏移值,实际地址为((段<< 4)+偏移))

我不知道这些编译器的兼容性如何,但是他们必须将SIZE_MAX定义为类似于1M的东西(因为这是你可以在奇怪的指针模型下解决的最大对象),但是ptrdiff_t将是一个16位整数(其中由于范围仅为-32768到+32767,因此不符合要求.

因此,在理智的硬件上实现理智的C实现没有任何理由让PTRDIFF_MAX小于SIZE_MAX.但是可能存在异国情调的硬件(在80x86的情况下,当时并不是异国情调),它允许您定义大型数组,但不允许您"同时"访问所有这些硬件.在这种情况下,PTRDIFF_MAX可能低于SIZE_MAX/2.

Answer 2

为了给出标题中问题的答案:指针差异本身不能用于确定两个指针的差异而不会最终导致未定义的行为.正如您所注意到的,这对于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))