c - sirven - tipos de punteros de power point

¿Cuándo exactamente se define una diferencia de puntero?

Question

Tengo una pregunta sobre las diferencias de punteros y el tipo resultante, ptrdiff_t .

C99 §6.5.6 (9) dice:

Cuando se restan dos punteros, ambos apuntarán a elementos del mismo objeto de matriz, o uno más allá del último elemento del objeto de matriz; el resultado es la diferencia de los subíndices de los dos elementos de la matriz. El tamaño del resultado está definido por la implementación, y su tipo (un tipo entero con signo) se define como ptrdiff_t en el encabezado. Si el resultado no se puede representar en un objeto de ese tipo, el comportamiento no está definido. En otras palabras, si las expresiones P y Q apuntan, respectivamente, a los elementos i-th y j-th de un objeto de matriz, la expresión (P) - (Q) tiene el valor i − j siempre que el valor se ajuste a una objeto de tipo ptrdiff_t .

§7.18.3 (2) requiere que ptrdiff_t tenga un rango de al menos [−65535, +65535]

Lo que me interesa es el comportamiento indefinido si el resultado es demasiado grande. No pude encontrar nada en el estándar que garantice al menos el mismo rango que la versión firmada de size_t o algo similar. Entonces, aquí está mi pregunta: ¿podría una implementación conforme hacer que ptrdiff_t un tipo de 16 bits firmado pero size_t 64 bits? [Editar: como señaló Guntram Blohm , 16 bits firmados hacen un máximo de 32767, así que mi ejemplo obviamente no es conforme] Por lo que veo, no puedo hacer ninguna resta de punteros en arreglos con más de 65535 elementos en código estrictamente conforme incluso si la implementación soporta objetos mucho más grandes que esto. Además, el programa puede incluso bloquearse.

La justificación (V5.10) § 6.5.6 dice:

Es importante que este tipo [ ptrdiff_t ] esté firmado para obtener un orden algebraico adecuado al tratar con punteros dentro de la misma matriz. Sin embargo, la magnitud de una diferencia de puntero puede ser tan grande como el tamaño del objeto más grande que se puede declarar; y dado que es un tipo sin signo, la diferencia entre dos punteros puede causar un desbordamiento en algunas implementaciones.

lo que puede explicar por qué no se requiere que se definan todas las diferencias de punteros (a elementos de la misma matriz), pero no explica por qué no hay una restricción en PTRDIFF_MAX para que sea al menos SIZE_MAX/2 (con división entera) .

Para ilustrar, supongamos que T es cualquier tipo de objeto y n un objeto de size_t no conocido en el momento de la compilación. Quiero asignar espacio para n objetos de T y quiero hacer una resta de puntero con direcciones en el rango asignado.

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) /* ... */;

No sería estrictamente conforme, tenía que hacer.

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

en lugar. ¿Es realmente así? Y si es así, ¿alguien sabe una razón para eso (es decir, para no requerir PTRDIFF_MAX >= SIZE_MAX/2 [editar: cambiado > a >= ] o algo similar)?

(*) La mitad de las cosas en la primera versión es algo que reconocí mientras escribía este texto, tenía

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

primero, tomando la mitad de SIZE_MAX para resolver los problemas mencionados en la Razón SIZE_MAX ; pero luego me di cuenta de que solo necesitamos la mitad de SIZE_MAX si sizeof(T) es 1. Dado este código, la segunda versión (la que seguramente es estrictamente conforme) no parece ser tan mala en absoluto. Pero aún así, estoy interesado si tengo razón.

C11 mantiene la redacción de §6.5.6 (9), las respuestas relacionadas con C ++ a este tema también son bienvenidas.

Answer 1

Para darle una respuesta a la pregunta en el título: la diferencia de puntero en sí no se puede usar para determinar la diferencia de dos punteros sin que finalmente conduzca a un comportamiento indefinido. Esto podría ser una restricción severa, como se observa, en sistemas donde PTRDIFF_MAX es mucho más pequeño que el tamaño posible de un objeto. Pero tales sistemas son raros (no conozco ninguno), así que si tuvieras un código que dependiera de poder hacer la diferencia con objetos grandes, siempre pones algo como

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

Pero incluso en ese caso ( ptrdiff_t demasiado estrecho) siempre podrá calcular la diferencia entre dos punteros del mismo objeto más grande.

1. Determine cuál de los dos ( p o q ) es más pequeño. Esto siempre está bien definido.
2. Digamos que p es el más pequeño, luego prueba todos los p + i para size_t i comenzando en 1 hasta que alcances q o i sea SIZE_MAX .
3. Si la i final es SIZE_MAX y no alcanzó q la diferencia no se puede representar. De lo contrario, más un signo final es la información que está buscando.

Esto no es realmente satisfactorio, pero no pude averiguar cómo mejorar ese algoritmo lineal a algo logarítmico: para evitar la UB no se nos permitiría ir más allá de q con la comparación.

Y, como dije, solo necesitarías eso para el caso de una arquitectura realmente exótica.

Editar:

Con el truco de mafso para obtener el bit más significativo de la diferencia de puntero, esto se puede hacer en O(log(n)) donde n es la distancia requerida. Primero declara dos funciones internas que asumen que 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;
}

Luego defina la función que calcula la diferencia en bytes y agrega una convención en caso de que la diferencia no se intmax_t representar en 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;
  }
}

Finalmente, una macro que se ajusta al tipo de *p .

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

Answer 2

Recuerdo que en los viejos tiempos, algunos compiladores de 80x86 de 16 bits tenían datamodels "grandes" o "enormes", donde los punteros tenían 32 bits, pero los enteros todavía tenían solo 16 bits. Estos compiladores le permitieron crear arreglos que tenían más de 65536 bytes, pero, como los enteros eran solo de 16 bits, los elementos de acceso que no estaban en los primeros 64 K requerían manipulación de punteros (lo que era realmente extraño, un puntero consistía en un segmento de 16 bits) valor y un valor de desplazamiento de 16 bits, con la dirección real ((segmento << 4) + desplazamiento))

No sé qué tan compatibles eran estos compiladores, pero habrían tenido que definir SIZE_MAX a algo así como 1M (ya que ese es el objeto más grande al que se puede dirigir dado el extraño modelo de puntero), pero ptrdiff_t habría sido un entero de 16 bits (que no sería compatible ya que el rango es de -32768 a +32767).

Por lo tanto, una implementación de C en un hardware sano no tendría ninguna razón para tener PTRDIFF_MAX menos que SIZE_MAX. Pero podría haber hardware exótico (que, en el caso de los 80x86, no era realmente exótico en ese momento), que le permite definir arreglos grandes, pero no le permite acceder a todos ellos "a la vez". En ese caso, PTRDIFF_MAX podría estar por debajo de SIZE_MAX / 2.