Implémentation de strcmp en C utilisant la soustraction de caractères

Question

J'ai vu cette mise en œuvre de strcmp il y a quelque temps, et j'ai une question à des fins purement pédagogiques. Pourquoi est-il nécessaire de convertir les entrées en entiers 16 bits, de faire les calculs et de les reconvertir en 8 bits ? Qu'y a-t-il de mal à faire la soustraction 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 );
}

Remarque : le code suppose que le système est à 16 bits int type.

EDITAR: Il a été mentionné que C fait la conversion en int (supposez 32bit) par défaut. Est-ce que c'est le cas même lorsque le code indique explicitement qu'il faut passer en 16 bits ? int ?

Answer 1

El strcmp(a,b) est censée retourner

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

Le test est en fait effectué sur le premier caractère qui est différent dans les deux chaînes au même endroit (0, le terminateur de la chaîne, fonctionne également).

Ici, puisque la fonction prend deux uint8_t (unsigned char), le développeur s'inquiétait probablement du fait qu'une comparaison entre deux unsigned chars donnerait un nombre entre 0 y 255 Par conséquent, une valeur négative ne sera jamais renvoyée. Par exemple, 118 - 236 rendrait -118 mais sur 8 bits, il renvoie 138 .

Ainsi, le programmeur a décidé de faire un casting en int_16 , nombre entier signé (16 bits).

Cela aurait pu fonctionner, et étant donné les valeurs négatives/positives correctes (à condition que la fonction retourne int_16 au lieu de int_8 ).

(*mise à jour : commentaire de @zwol ci-dessous, la promotion de l'entier est inévitable, donc ceci int16_t la coulée n'est pas nécessaire)

Toutefois, la version finale int_8 La distribution rompt la logique. Puisque les valeurs retournées peuvent être de -255 a 255 certaines de ces valeurs verront leur signe inversé après le passage en int_8 .

Par exemple, en faisant 255 - 0 donne le positif 255 (sur 16 bits, tous les 8 bits inférieurs à 1, le MSB à 0) mais dans la int_8 monde (int signé de 8 bits), c'est négatif, -1 puisque nous n'avons que les 8 derniers bits bas en binaire. 11111111 ou décimal -1 .

---

Ce n'est certainement pas un bon exemple de programmation.

Ce fonction de travail d'Apple est meilleur

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

(Linux le fait en code assembleur...)

Answer 2

En fait, la différence doit être faite sur au moins 16 bits¹ pour la raison évidente que la plage du résultat est de -255 à 255 et que cela ne tient pas sur 8 bits. Cependant, sfstewman a raison de noter que cela se produirait de toute façon en raison de la promotion implicite des entiers.

L'éventuelle conversion en 8 bits est incorrect car il peut déborder car la plage ne tient toujours pas sur 8 bits. Et de toute façon, strcmp est en effet censé retourner un simple int .

---

¹ 9 suffirait, mais les bits viennent normalement par lots de 8.

Answer 3

Les données d'entrée sont des données non signées de 8 bits, donc pour éviter la troncature et les effets de débordement/sous-débordement, elles doivent être converties en données signées d'au moins 9 bits, donc int16 est utilisé.

Answer 4

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

Cela pourrait signifier l'une de ces deux options :

• Soit le programmeur n'a pas compris comment fonctionnent les promotions de type implicites en C. Les deux opérandes seront implicitement convertis en int peu importe les castings à int16_t . Donc si int est par exemple de 32 bits, le code n'a aucun sens. Ou sinon si int est équivalent à int16_t pour le système spécifique - alors aucune conversion n'a lieu.

• Ou bien le programmeur connaît bien le fonctionnement des promotions de type et écrit du code qui doit être conforme à une norme interdisant les promotions de type implicites, comme la norme MISRA-C. Dans ce cas, et dans le cas où int est de 16 bits sur le système donné, le code est parfaitement logique : il force une promotion de type explicite pour éviter les avertissements du compilateur/analyseur statique.

Je pense que la deuxième option est la plus probable, et que ce code est destiné à un petit système de microcontrôleur.

Answer 5

Il y a certaines valeurs qui feraient que la différence entre les deux nombres serait différente si le int16_t n'étaient pas là à cause d'un débordement. Dans un int8_t votre fourchette est de -128 à 127, dans une uint8_t votre plage est comprise entre 0 et 255, et dans une int16_t votre fourchette serait de -32,768 à 32,767.

Boîtier à un int8_t d'un uint8_t entraînera un changement de signe des valeurs supérieures à 127 en raison d'un dépassement de capacité, ce qui évite que cela ne se produise. int16_t car si vous aviez un résultat 255 - 0, ce serait un retour tronqué.