Pregunta Implementación de C strcmp usando resta de caracteres


Vi esta implementación de strcmp Hace un tiempo, y tengo una pregunta con fines puramente educativos. ¿Por qué es necesario convertir las entradas a enteros de 16 bits, hacer los cálculos y luego convertir de nuevo a 8 bits? ¿Qué hay de malo en hacer la resta en 8 bits?

int8_t strcmp (const uint8_t* s1, const uint8_t* s2)
{
  while ( *s1 && (*s1 == *s2) )
  {
    s1++; 
    s2++;
  }

  return (int8_t)( (int16_t)*s1 - (int16_t)*s2 );
}

Nota: el código supone 16 bits int tipo.

EDITAR: Se mencionó que C hace la conversión a int (suponga 32 bits) de forma predeterminada. Es ese el caso, incluso cuando el código explícitamente establece para lanzar a 16 bits int ?


32
2018-01-18 16:08


origen


Respuestas:


los strcmp (a, b) se espera que la función regrese

  • <0 Si string a < string b
  • >0 Si string a > string b
  • 0 Si string a == string b

La prueba se realiza realmente en el primer char que es diferente en las dos cadenas en la misma ubicación (0, el terminador de cadena, también funciona).

Aquí ya que la función toma dos uint8_t (char sin signo), el desarrollador probablemente estaba preocupado por hacer una comparación en dos caracteres sin signo que daría un número entre 0 y 255, por lo tanto, nunca se devolverá un valor negativo. Por ejemplo, 118 - 236 volvería -118, pero en 8 bits volvería 138.

Por lo tanto, el programador decidió lanzar a int_16, entero con signo (16 bits).

Eso podría haber funcionado, y dados los valores negativos / positivos correctos (siempre que la función regrese int_16 en lugar de int_8)

(* editar: comentario de @zwol a continuación, la promoción de enteros es inevitable, por lo tanto esto int16_t casting no es necesario)

Sin embargo, el final int_8 el yeso rompe la lógica. Dado que los valores devueltos pueden ser de -255 a 255, algunos de estos valores verán su signo invertido después del lanzamiento a int_8.

Por ejemplo, haciendo 255 - 0 da el positivo 255 (en 16 bits, todos 8 bits inferiores a 1, MSB a 0) pero en el int_8 mundo (firmado int de 8 bits) esto es negativo, -1, ya que solo tenemos los últimos 8 bits bajos configurados como binarios 11111111, o decimal -1.


Definitivamente no es un buen ejemplo de programación.

Ese función de trabajo de Apple es mejor

for ( ; *s1 == *s2; s1++, s2++)
    if (*s1 == '\0')
        return 0;
return ((*(unsigned char *)s1 < *(unsigned char *)s2) ? -1 : +1);

(Linux lo hace en código ensamblador ...)


24
2018-01-18 16:46



En realidad, la diferencia se debe hacer en al menos 16 bits¹ por la razón obvia de que el rango del resultado es de -255 a 255 y que no cabe en 8 bits. Sin embargo, sfstewman está en lo cierto al señalar que sucedería debido a la promoción de entero implícito de todos modos.

El lanzamiento eventual a 8 bits es incorrecto, porque puede desbordarse ya que el rango todavía no cabe en 8 bits. Y de todas formas, strcmp de hecho se supone que volverá simple int.


¹ 9 sería suficiente, pero los bits normalmente vienen en lotes de 8.


9
2018-01-18 16:28



Los datos de entrada no tienen signo de 8 bits, por lo que para evitar el truncamiento y los efectos de desbordamiento / desbordamiento se debe convertir a al menos 9 bits firmado, por lo tanto, se utiliza int16.


3
2018-01-18 16:27



return (int8_t)( (int16_t)*s1 - (int16_t)*s2 );

Esto podría significar una de estas dos opciones:

  • O el programador estaba confundido acerca de cómo las promociones de tipo implícito funcionan en C. Ambos operandos se convertirán implícitamente en intno importa los moldes para int16_t. Así que si intes por ejemplo 32 bits, el código no tiene sentido. O de lo contrario si int es equivalente a int16_t para el sistema específico - entonces no tiene lugar ninguna conversión.

  • O bien, el programador es consciente de cómo funcionan las promociones de tipo y está escribiendo un código que debe confirmar a un estándar que prohíbe las promociones de tipo implícito, como MISRA-C. En ese caso, y en el caso int Hay 16 bits en el sistema dado, el código tiene perfecto sentido: fuerza una promoción de tipo explícita para esquivar las advertencias del compilador / analizador estático.

Me gustaría adivinar que la segunda opción es la más probable, y que este código está indended para un sistema de microcontrolador pequeño.


2
2018-01-18 16:30



Hay ciertos valores que causarían que la diferencia entre los dos números sea diferente si el int16_t no estaban allí debido al desbordamiento. En una int8_t su rango es -128 a 127, en un uint8_t su rango es de 0 a 255, y en una int16_t su rango sería -32,768 a 32,767.

Cubriendo a un int8_t a partir de una uint8_t hará que los valores por encima de 127 cambien los signos debido al desbordamiento, por lo que esto no sucederá, sin embargo, la salida debería ser un int16_t debido a que si tuvieras un resultado de 255-0, sería un retorno truncado.


1
2018-01-18 16:32