Twitter iPhone pliant OnePlus 11 PS5 Disney+ Orange Livebox Windows 11

Description de strcmp dans la norme

55 réponses
Avatar
candide
Bonjour,

Deux choses me gênent dans la description de la fonction strcmp dans la
norme (C90 tout comme C99) :

1er point :

--------------------------------8<-----------------------------------
7.21.4 Comparison functions
1 The sign of a nonzero value returned by the comparison functions
memcmp, strcmp, and strncmp is determined by the sign of the difference
between the values of the first pair of characters (both interpreted as
unsigned char) that differ in the objects being compared.
-------------------------------->8-----------------------------------

Pourquoi employer l'expression "is determined" qui est assez vague
(pour moi, ici ça veut dire "est déterminé") ? Pourquoi ne pas dire
que les signes sont identiques (donc "coincides with" ou "matches" ou
"is identical to", etc) ?

2ème point :

--------------------------------8<-----------------------------------
7.21.4.2 p3 The strcmp function returns an integer greater than, equal
to, or less than zero, accordingly as the string pointed to by s1 is
greater than, equal to, or less than the string pointed to by s2.
-------------------------------->8-----------------------------------

Où dans la norme la notion de "chaîne plus grande qu'une autre" est-elle
définie ?

Merci

10 réponses

2 3 4 5 6
Avatar
Charlie Gordon
"Antoine Leca" a écrit dans le message de news:
g7gt6i$jra$
En news:g7g96t$n8s$, Charlie Gordon va
escriure:
candide a écrit dans le message de news:
489b67ef$0$19939$
Donc pour reformuler la question, comment un processeur est-il
programmé pour comparer des entiers ? fait-il une soustraction puis
examine t-il un bit de signe ? Ou alors, procède-t-il justement
lexicographiquement ? Pi si ça se trouve ça va dépendre des
processeurs.



Dans le cas des x86, le CPU fait effectivement la soustraction mais ne
stocke pas le resultat, seulement les flags. C'est en tous cas comme
cela qu'était documentée l'instruction SUB dans les manuels Intel il
y a une vingtaine d'années.



C'est bien sûr l'instruction CMP qui documente cela.



Oui bien sûr, un lapsus tecladi.

En fait, aujourd'hui il ne stocke pas les flags (qui ne sont plus
implantés
comme tel ; je me demande d'ailleurs depuis combien de temps les flags
sont
virtuels dans le silicium, à mon avis cela remonte au 486 : les temps
d'exécution de POPF etc. y sont supérieurs à ceux du 386) : il garde
seulement la trace des informations nécessaires pour les recalculer le cas
échéant.
Ainsi si ton CMP est suivi d'un JNE, le flag ZF sera évalué mais le
processeur va faire l'économie du calcul de AF, PF et compagnie.
Ainsi, il y a eu des annonces de corrections de défaut (errata) concernant
des « oublis » de traitement de certains flags dans des cas tordus (genre
entrée en mode SMM avec une interruption au milieu).



Tu as raison, mais un peu d'historique correspondait mieux à la question de
l'OP.

Les arcanes de l'implementation des processeurs modernes sont au langage
machine ce que l'assembleur est au C, ce que le C est au javascript, etc.
L'informatique moderne, c'est comme peler un oignon, tu crois avoir enfin
enlevé la peau et compris comment ça fonctionne à l'intérieur, et hop il y a
encore une couche en dessous... et une complexité insoupçonnée, on en
chialerait.

char buf[20];
some_func(buf);
if (!strcmp(buf, "err"))
return -1;

Le compilateur sait que buf et "err" sont correctement alignés
puisqu'il qu'il préside à leur allocation (respectivement dans la
pile et un segment de données). Sur une machine 32 bits, il pourrait
générer le code quasi-optimal suivant:

if (*(uint32_t*)buf == *(uint32_t)"err")
return -1;

Je ne sais pas si d'aucuns compilateurs font cela correctement,



Je ne serais pas surpris qu'ils le fassent, mais je ne vais pas aller
vérifier.
Il faut dependant noter que cette optimisation n'est possible que parce
que
"err" compte 4 caractères, cela ne marcherait plus avec 3, 5, 6 ou 7 (OK,
cela /peut/ marcher avec 5 sur votre espèce de @[*! de TMS et ses long sur
40 bits réels).



En fait cela peut marcher aussei pour d'autres longueurs, par exemple :

if (((*(uint32_t)buf ^ *(uint32_t)"OK ") & MASK_3_BYTES) == 0)

avec MASK_3_BYTES qui vaut 0xffffff00 en big endian, et 0xffffff en little
endian.

Avec des tas de variantes possibles pour differentes tailles et en fonction
de l'architecture ciblée.

La vraie contrainte, c'est plutot l'alignement de buf sur les architectures
ou c'est nécessaire.

En fait, j'ai déjà vu sur des machines gros-boutiennes (donc pas x86) des
comparaisons de chaînes implémentées (y compris le signe) comme des
comparaisons d'entiers, donc l'équivalent de strcmp remplacé par un CMP.l
dans une boucle serrée ! Cela fonctionnait parce que sur une machine gros
boutienne la comparaison des entiers opère de la même manière que la
comparaison des chaînes (même opération d'ordre des suites), et parce que
dans ce cas-là les fins de chaîne étaient toujours remplies à 0 au-delà du
Avatar
candide
Charlie Gordon a écrit :

Dans le cas des x86, le CPU fait effectivement la soustraction mais ne
stocke pas le resultat, seulement les flags.


> (...)

Merci des ces précisions.
Avatar
Jean-Marc Bourguet
candide writes:

Donc pour reformuler la question, comment un processeur est-il programmé
pour comparer des entiers ? fait-il une soustraction puis examine t-il un
bit de signe ?



C'est plus ou moins ça. On a généralement un machin appelé ALU (arithmetic
and logic unit) dans lequel entre les deux nombres et des signaux de
contrôles et qui est capable aussi bien de faire une addition qu'une
soustraction que certaines opérations logiques bit à bit et qui en plus
fournit certains drapeaux donnant des informations sur le résultat (carry
sortante, overflow si on considère les nombres comme signé, résultat nul).
Chercher à décomposer l'ALU, dans certains cas on va trouver quelque chose
d'assez simple à comprendre (on va avoir en gros un additionneur composé de
l'assemblage d'une cellule qui prenant trois bits en entrée en donne deux
indiquant combien sont à un -- les trois entrées sont les deux nombres à
additionner et la carry du bit précédant, les deux sorties la valeur du bit
et la carry sortante -- et un peu de logique autour pour assurer le choix
entre additionneur et soustracteur -- pour ce dernier, on complémente une
entrée et la carry entrante du premier bit est un 1 plutôt qu'un 0 -- et
opération logique) à des choses plus compliquées (la propagation de la
carry prend du temps, donc on cherche à l'éviter quitte à dupliquer
certains calculs; ne pas oublier que les circuits sont intrinsèquement
parallèle et qu'une bonne partie des progrès des années 90 dans les
micro-processeur a été de permettre de profiter de ce parallélisme sans
changer l'interface fortement séquentielle; on est arrivé au bout de ce qui
est possible -- certains processeurs peuvent avoir plus de 100 instructions
en cours d'exécution simultanées *par core* -- et le seul moyen qu'on voit
de profiter de la place disponible, c'est de fournir du parallélisme
explicite -- les différents cores).

Après suivant l'instruction et le processeur, certains résultats de l'ALU
sont conservés et les autres purement et simplement ignorés. Une
instruction de comparaison va classiquement générer le même controle qu'une
soustraction et n'utiliser que les drapeaux.

Dans les cas où on n'a besoin que de la comparaison -- vraisemblablement
pas pour les instructions du processeur, mais dans un processeur par
exemple pour vérifier les bornes des segments --, on peut ne pas utiliser
une ALU mais une version simplifiée basée sur le même principe (cad
globalement des signaux se propageant du moins significatif au plus
significatif), on pourrait aussi utiliser quelque chose avec des signaux se
propageant dans l'autre sens que tu pourrais appeler lexicographique. Il
est possible aussi de combiner les deux et d'avoir donc des signaux se
propageant des extrémités vers le milieu ce qui permet de diminuer la
profondeur totale -- à nouveau ne pas oublier que tout ça fonctionne en
parallèle.

A+

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Avatar
Jean-Marc Bourguet
"Antoine Leca" writes:

En fait, aujourd'hui il ne stocke pas les flags (qui ne sont plus implantés
comme tel ; je me demande d'ailleurs depuis combien de temps les flags sont
virtuels dans le silicium, à mon avis cela remonte au 486 : les temps
d'exécution de POPF etc. y sont supérieurs à ceux du 386) : il garde
seulement la trace des informations nécessaires pour les recalculer le cas
échéant.



A mon avis les flags étaient calculés mais plus stockés tous ensemble à un
endroit aussi facilement accessible. Evidemment maintenant je ne cherche
même plus à savoir . Il doit y avoir plusieurs registres contenant les
flags et pas mal de logique pour savoir lequel contient la version valide
"maintenant" pour un "maintenant" qui est à définir d'une manière adéquate
pour un processeur
- pipeliné (cad que plusieurs instructions sont exécutées en même temps,
chacune dans des phases différentes)
- superscalaire (cad que plusieurs instructions peuvent se retrouver
dans la même phase en même temps)
- "multiple-issue" (cad que plusieurs instructions peuvent commencer
leur exécution en même temps)
- à exécution dans le désordre (cad que les instructions peuvent être
exécutée dans un ordre différent de celui du flux
d'instructions)
- à exécution spéculative (cad que des instructions peuvent être
exécutée après un saut sans que le processeur sache à
coup sur si le saut est pris ou non)

Ainsi si ton CMP est suivi d'un JNE, le flag ZF sera évalué mais le
processeur va faire l'économie du calcul de AF, PF et compagnie.



Je doute pour le cas du 486. Pour un processeur plus complexe, je doute
aussi, la tendance étant plutôt à calculer le plus tôt possible quite à
jeter qu'à éviter les calculs.

Ainsi, il y a eu des annonces de corrections de défaut (errata) concernant
des « oublis » de traitement de certains flags dans des cas tordus (genre
entrée en mode SMM avec une interruption au milieu).



Voir ci-dessus, il y a assez de sources de problèmes quand on cherche à
sauver un état "stable" ressemblant à celui d'une exécution purement
séquentielle.


char buf[20];
some_func(buf);
if (!strcmp(buf, "err"))
return -1;

Le compilateur sait que buf et "err" sont correctement alignés
puisqu'il qu'il préside à leur allocation (respectivement dans la
pile et un segment de données). Sur une machine 32 bits, il pourrait
générer le code quasi-optimal suivant:

if (*(uint32_t*)buf == *(uint32_t)"err")
return -1;

Je ne sais pas si d'aucuns compilateurs font cela correctement,



Je ne serais pas surpris qu'ils le fassent, mais je ne vais pas aller
vérifier.
Il faut dependant noter que cette optimisation n'est possible que parce que
"err" compte 4 caractères, cela ne marcherait plus avec 3, 5, 6 ou 7 (OK,
cela /peut/ marcher avec 5 sur votre espèce de @[*! de TMS et ses long sur
40 bits réels).

En fait, j'ai déjà vu sur des machines gros-boutiennes (donc pas x86) des
comparaisons de chaînes implémentées (y compris le signe) comme des
comparaisons d'entiers, donc l'équivalent de strcmp remplacé par un CMP.l
dans une boucle serrée ! Cela fonctionnait parce que sur une machine gros
boutienne la comparaison des entiers opère de la même manière que la
comparaison des chaînes (même opération d'ordre des suites), et parce que
dans ce cas-là les fins de chaîne étaient toujours remplies à 0 au-delà du
Avatar
Antoine Leca
En news:489b53e8$0$874$, Wykaaa va escriure:
Antoine Leca a écrit :
En news:4899f553$0$952$, Wykaaa va escriure:
Antoine Leca a écrit :
En news:48956e6b$0$945$, Wykaaa va escriure:
Par rapport à l'ordre lexicographique (codage des caractères).


Mmmm, ce n'est pas la même chose...









<snip>

Cependant, à lire ta réaction et celle de plusieurs autres, il
semblerait que je me trompai, et que pour les informaticiens (qui à
par moi doivent constituer l'essentiel du public de ce forum) la
notion de « lexicographique » a un sens particulier, différent de
celui généralement / antérieurement accepté (et repris par le
dictionnaire de l'Académie).



Absolument, oui.

Je t'encourage à lire la page 4 du document suivant :
http://www.dicosmo.org/CourseNotes/IF242/Preliminaires.pdf (ce sont
des notions mathématiques préliminaires à un cours sur "logique et
circuits". L'ordre lexicographique (au sens des informaticiens et des
mathématiciens, d'ailleurs) y est parfaitement défini.



J'ai lu. Mais je n'y ai pas trouvé l'endroit où il est affirmé que l'ordre
lexicographique ne s'appliquait _qu'à_ l'ordre des entiers sous-jacents.


En fait, j'ai même plutôt eu l'impression que la définition donnée
s'appliquait quel que soit l'ordre utilisé sur l'ensemble des éléments
constitutifs.
Par exemple, il me semble bien que l'ordre inverse (z>y) donne lui aussi un
ordre lexicographique, au sens de ce document.


Je t'accorde par contre que les tris multi-passes (tels que ceux qui sont
utilisés dans les dictionnaires, où les différences d'espacement, de casse
ou d'accent sont secondaires) ne rentrent pas dans la définition donnée
d'ordre lexicographique.


Il y a d'ailleurs un avertissement qui indique que ce n'est pas
exactement 'ordre du dictionnaire.



Il y a bien un avertissement, mais mes connaissances ne me permettent pas de
comprendre ce qui est écrit.

Ou alors c'est parce que l'ordre lexicographique tel qu'il est défini dans
ce document ne traite pas le cas des suites/n-uplets de longueurs
différentes ?


Tu pourras consulter utilement aussi :
http://www.ltam.lu/Tutoriel_Ansi_C/prg-c78.htm



Là effectivement, le propos est bien réduit.

On y trouve aussi un certain nombre d'éléments qui me font trembler, comme
la juxtaposition du code ASCII et de l'ensemble des lettres accentués
(incluant û qui n'est même pas dans la variante française de l'ASCII
considéré comme norme internationale) ;
ou la généralisation comme quoi un codage (jeu de caractères) donné serait
_le_ seul et unique « alphabet » de la machine (en C, on apprend au
contraire que le codage des caractères est indépendant de la machine...)
Enfin, le texte renvoit sur la paragraphe 8.6.2... qui exclut explicitement
les « symboles nationaux » (ou caractères étendus)
Je m'arrête là, car j'ai vu des strncpy() et gets() dans les autres
chapitres...


Antoine
Avatar
Charlie Gordon
"Antoine Leca" a écrit dans le message de news:
g7pgrr$se3$
En news:489b53e8$0$874$, Wykaaa va escriure:


...
Tu pourras consulter utilement aussi :
http://www.ltam.lu/Tutoriel_Ansi_C/prg-c78.htm



Là effectivement, le propos est bien réduit.



...
Je m'arrête là, car j'ai vu des strncpy() et gets() dans les autres
chapitres...



on peut parler de strncpy (ou gets) pour illustrer un usage utile du
preprocesseur:

#define strncpy(s,n,p) never_use_strncpy_it_has_broken_semantics(s,n,p)

avec des warnings correctement configurés (minimum
gcc -O2 -Wall -W -Werror), on ne passe pas la compilation, au pire on a un
diagnostique correct au link.

--
Chqrlie.
Avatar
Charlie Gordon
"Wykaaa" a écrit dans le message de news:
489a101f$0$906$
Charlie Gordon a écrit :
... Dans les faits, strcmp est majoritairement utilisée pour déterminer
si 2 chaines ont le même contenu, avec l'un des deux idiomes
``!strcmp(a,b)'' ou ``strcmp(a,b) == 0''.



Alors ça, ce n'est pas vrai du tout.
Exemple (en C++. Désolé mais comme la discussion est dans le forum du
langage C...):
Surcharge des opérateurs de comparaison pour une classe Chaîne faite
"maison"
int operator==(const Chaine& s1, const Chaine& s2)
{
return strcmp(s1.la_chaine, s2.la_chaine) == 0;
}

int operator!=(const Chaine& s1, const Chaine& s2)
{
return strcmp(s1.la_chaine, s2.la_chaine) != 0;
}

int operator<(const Chaine& s1, const Chaine& s2)
{
return strcmp(s1.la_chaine, s2.la_chaine) < 0;
}

int operator>(const Chaine& s1, const Chaine& s2)
{
return strcmp(s1.la_chaine, s2.la_chaine) > 0;
}
int operator<=(const Chaine& s1, const Chaine& s2)
{
return strcmp(s1.la_chaine, s2.la_chaine) <= 0;
}

int operator>=(const Chaine& s1, const Chaine& s2)
{
return strcmp(s1.la_chaine, s2.la_chaine) >= 0;
}

avec
class Chaine
{
private :
int la_longueur;
char* la_chaine;
....
};



C'était une plaisanterie ?

Donc je reprends : dans les faits, en C, strcmp() est majoritairement
utilisée pour déterminer si 2 chaines ont le même contenu, avec l'un des
deux idiomes ``!strcmp(a,b)'' ou ``strcmp(a,b) == 0'' ;-)

--
Chqrlie.
Avatar
espie
In article <g7qr45$poc$,
Charlie Gordon wrote:
on peut parler de strncpy (ou gets) pour illustrer un usage utile du
preprocesseur:

#define strncpy(s,n,p) never_use_strncpy_it_has_broken_semantics(s,n,p)

avec des warnings correctement configurés (minimum
gcc -O2 -Wall -W -Werror), on ne passe pas la compilation, au pire on a un
diagnostique correct au link.



Euh, strncpy a une utilisation utile, sous Unix: pour gerer les entrees
d'utmp, et autres trucs bizarres qui ne sont *pas* des chaines de caracteres,
mais des champs de longueur fixe, remplis avec des zeros si plus courts,
et utilisant toute la largeur du champ si necessaire.
Avatar
Charlie Gordon
"Marc Espie" a écrit dans le message de news:
g7s0gb$cpu$
In article <g7qr45$poc$,
Charlie Gordon wrote:
on peut parler de strncpy (ou gets) pour illustrer un usage utile du
preprocesseur:

#define strncpy(s,n,p) never_use_strncpy_it_has_broken_semantics(s,n,p)

avec des warnings correctement configurés (minimum
gcc -O2 -Wall -W -Werror), on ne passe pas la compilation, au pire on a un
diagnostique correct au link.



Euh, strncpy a une utilisation utile, sous Unix: pour gerer les entrees
d'utmp, et autres trucs bizarres qui ne sont *pas* des chaines de
caracteres,
mais des champs de longueur fixe, remplis avec des zeros si plus courts,
et utilisant toute la largeur du champ si necessaire.



Bien sûr, c'est pour cela qu'elle a été faite à l'origine, et c'était déjà
une erreur de design.
Les entrées de répertoire auraient déjà dû avoir une longueur variable et
les fichiers utmp auraient dû être textuels comme tous les fichiers de log.
Quant à appeler strncpy une fonction qui ne traite *pas* des chaines de
caractères, c'est une erreur de nommage.

ANSI a standardisé cette fonction parce qu'elle était beaucoup utilisée par
des programmes existants, mais ces utilisations étaient très souvent
incorrectes et buggy, comme encore aujourd'hui.

Pour les cas que tu cites, une périphrase avec memset et memcpy est très
simple, lisible et efficace.
Pour le reste, strncpy n'est pratiquement jamais la bonne solution, et trop
souvent une source de bugs.

Cette fonction ne fait pas ce que la plupart des developpeurs pensent
connaitre.
L'utiliser, même à bon escient, c'est entretenir cette confusion.

Mentionner cette fonction dans un tutoriel est une hérésie : le débutant n'a
aucune chance de comprendre la sémantique tordue de cette saloperie, surtout
s'il cherche à l'intuiter.

Donc : NE JAMAIS UTILISER LA FONCTION strncpy.

--
Chqrlie.

PS: j'invite les incrédules à (re)lire attentivement la définition de
strncpy() et strncat().
Avatar
espie
In article <g7s4bc$c7a$,
Charlie Gordon wrote:
Quant à appeler strncpy une fonction qui ne traite *pas* des chaines de
caractères, c'est une erreur de nommage.


Ca, je suis d'accord.

Pour les cas que tu cites, une périphrase avec memset et memcpy est très
simple, lisible et efficace.


Et le code avec strncpy est extremement court, certes un peu bizarre, mais
le format qui va avec l'est aussi (et c'est un peu tard pour le changer).


Pour le reste, strncpy n'est pratiquement jamais la bonne solution, et trop
souvent une source de bugs.



Totalement d'accord.

Mentionner cette fonction dans un tutoriel est une hérésie : le débutant n'a
aucune chance de comprendre la sémantique tordue de cette saloperie, surtout
s'il cherche à l'intuiter.



Egalement.

Donc : NE JAMAIS UTILISER LA FONCTION strncpy.



Oui, conseil a la Knuth. A suivre presque toujours, sauf lorsqu'on est
dans le cas de figure pre-cite et qu'on sait exactement ce qu'on fait
(et il vaut mieux mettre des gros XXX pour expliquer ce qu'il en est).
2 3 4 5 6