Discussion :

[Dihydrro]

Bonjour je cherche à faire une copie d'un tableau 2D

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
char    **init_sudok(char **sudoku)
{
    char    **sudoku_init;
    int i;
    int j;
 
    sudoku_init = malloc(9);
    i = -1;
    while (sudoku_init && ++i < 9)
    {
        j = -1;
        sudoku_init[i] = malloc(9 + 1);
        while (sudoku_init[i] && ++j < 10)
            sudoku_init[i][j] = sudoku[i][j];
        ft_putstr(1, "Tour ");
        putnbr(1, (i + 1));
        ft_putstr(1, "\n");
        ft_putstr(1, sudoku_init[0]);
        if (i > 0)
            ft_putstr(1, sudoku_init[1]);
        ft_putstr(1, "\n");
    }
    return (sudoku_init);
}

L'initialisation se déroule correctement, au début, mais au fur et à mesure les données des deux premières lignes changent. Pour voir l'évolution des ces lignes je les affiches à chaque tour de la grande boucle, voici ce que ça donne :

Tour 1
1...32..7
Tour 2
1...32..7
..56...4.
Tour 3
1...32..7
..56...4.
Tour 4
1...32..7
..56...4.
Tour 5
▒32..7
..56...4.
Tour 6
▒@▒7
..56...4.
Tour 7
▒@▒`▒..56...4.
Tour 8
▒@▒`▒▒▒1..56...4.
Tour 9
▒@▒`▒▒▒▒▒..56...4.
Je ne vois pas d'où sortes ces caractères et comment y remédier. :/

[o_Nejma]

Bonjour,

Je pense que l'erreur provient de la zone mémoire pointée par le paramètre de service char **sudoku. Est-ce que tu peux nous donner le bout de code où cette fonction est appelée?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
char    **init_sudok(char **sudoku)
 
            sudoku_init[i][j] = sudoku[i][j];//sudoku[i][j]: source de données et peut être mal initialisée

[Dihydrro]

Je reçois le sudoku de base en argument de mon programme, un argument = une ligne et je le stock de cette manière :

Exemple : ./solver.exe "..578..6." "...1.9.8." ""89.....5." "4...7..39" "..6...1.." "97..6...5" ".3.....26" ".8.6.7..." .2..938.."

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int	main(int argc, char **argv)
{
	char  **sudoku;
	int   i;
	int   j;
 
	if (argc != 10)
    		return (0);
  	sudoku = malloc(9 * 9 + 9);
  	i = -1;
  	j = 0;
  	while (++i < 9)
  	{
    		sudoku[i] = malloc(9 + 1);
    		sudoku[i] = argv[++j];
    		sudoku[i][9] = '\n';
  	}
	prepare_solv(sudoku);
  	return (0);
}

Et voici ma fonction qui fais appel à init_sudok() :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void	prepare_solv(char **sudoku)
{
	char **first_sudok;
	char **second_sudok;
 
	first_sudok = init_sudok(sudoku);
	solver(first_sudok, sudoku, 0, 0, 1);
	second_sudok = init_sudok(sudoku);
	solver(second_sudok, sudoku, 8, 8, -1);
	if (compare_sudok(first_sudok, second_sudok))
		putsudoku(second_sudok);
	else
		write(1, "Plusieurs solutions", 20);
}

[Sve@r]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
	char **sudoku;
	sudoku = malloc(9 * 9 + 9);

Bonjour

Déjà ici ça ne va pas. sudoku est un char** donc un truc destiné à recevoir l'adresse de départ d'une zone de char*. Chaque char* de ladite zone recevra ensuite, lui, l'adresse de départ d'une zone de char.
Il s'ensuit que sudoku doit allouer n <char*>. Or toi, tu lui alloues n <char>. Et comme un char (zone prévue pour stocker un caractère) n'est pas un char* (zone prévue pour stocker l'adresse d'un caractère), ça ne peut pas aller.
Accessoirement, si le "+9" veut montrer l'espace pour le '\0', alors vaut mieux écrire "9 * (9+1)" pour bien montrer aux autres lecteurs qu'on alloue 9 chaines de 9 caractères (parce que moi j'ai galéré 10mn avant de comprendre le but)...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
   		sudoku[i] = malloc(9 + 1);
    		sudoku[i] = argv[++j];

Bon ben que dire devant ce genre d'instruction. Le plus terrible, c'est que ça ne te choque même pas d'affecter deux valeurs différentes à la même variable. Tu peux me dire à quoi tu penses au moment exact où tu écris ça ???

[Médinoc]

En fait, vu qu'un sudoku est un tableau 2D de taille connue à la compilation, le plus simple serait de le déclarer en tant que tableau statique 9×9 dans une struct; ainsi, pour chaque nouvelle grille, il suffira d'un malloc(sizeof(struct sudoku)) et la copie peut se faire par un simple memcpy()...

[Dihydrro]

Par contre je ne peux pas utiliser memcpy, pour effectuer ce programme j'ai seulement le droit d'utiliser malloc/free/write.
C'est vrai que le main ne ressemblait à rien je l'avais codé il y a un bon moment, je l'ai corrigé, mais mon problème reste le même.

Mon problème risque-t-il pas d'être le même avec une structure? Tout comme il devrait être le même dans un tableau de char de 81 cases, non?

Ce qui m'étonne vraiment c'est que lorsque je copie la première ligne cela se déroule correctement. Mais à partir de la cinquième ligne, les caractères de la première ligne se modifient par ces caractères étranges petit à petit après chaque copie de ligne.

[Médinoc]

Si c'est pour une histoire d'Epita, memcpy() n'est pas difficile à réimplermznter...

[Sve@r]

Mon problème risque-t-il pas d'être le même avec une structure? Tout comme il devrait être le même dans un tableau de char de 81 cases, non?

T'as le droit d'utiliser ce que tu veux. Mais faut le déclarer correctement et l'allouer encore plus correctement. Un tableau de 81 "trucs" c'est truc tab[81] (ou bien truc *tab; tab=malloc(81 * sizeof(truc)) même si c'est idiot de faire de l'allocation dynamique avec une taille connue).
Donc si "truc" représente un "int" alors tu remplaces. Et si "truc" représente un "char*" alors tu remplaces là aussi...

Ce qui m'étonne vraiment c'est que lorsque je copie la première ligne cela se déroule correctement. Mais à partir de la cinquième ligne, les caractères de la première ligne se modifient par ces caractères étranges petit à petit après chaque copie de ligne.

N'essaye pas de chercher une logique à un comportemet indéterminé. Un comportement "indéterminé" ne peut pas, par essence, ni être déterminé ni rationalisé...

Si c'est pour une histoire d'Epita, memcpy() n'est pas difficile à réimplermznter...

Faut quand-même faire attention si les zones se chevauchent et au sens du chevauchement

[Médinoc]

Faut quand-même faire attention si les zones se chevauchent et au sens du chevauchement

Tu n'as pas à t'en soucier si tu recodes memcpy(), car elle n'est pas censée s'en soucier (bien sûr, tu peux toujours faire if(detect_overlap(desc, src, sizeInBytes)) SummonNasalDemons();).
Par contre, si tu recodes memmove(), là en effet il faut supporter l'overlap (généralement en choisissant de partir de la fin ou du début selon une comparaison des pointeurs).

[Dihydrro]

Merci pour vos explications !

[Sve@r]

Tu n'as pas à t'en soucier si tu recodes memcpy(), car elle n'est pas censée s'en soucier...

C'est bizarre parce que ce code semble (pour moi) démontrer que memcpy s'en soucie bel et bien...

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h> 
#include <string.h>
 
void mymemcpy(char *d, char *s, size_t n)
{
	size_t i;
	for (i=0; i < n; i++, *(d++)=*(s++));
}
 
int main()
{
	char ch1[40]="abcdefghijklmnopqrstuvwxyz";
	char ch2[40]="abcdefghijklmnopqrstuvwxyz";
 
	memcpy(ch1+3, ch1, strlen(ch1)+1);
	printf("%s\n", ch1);
 
	mymemcpy(ch2+3, ch2, strlen(ch2)+1);
	printf("%s\n", ch2);
}

La première chaine contient au final "abcabcdefghijklmnopqrstuvwxyz" ce qui montre que tout ch1 a bien été copié à 3 positions du départ ; malgré le fait que copier "a" directement à la position "d" transformait la chaine d'origine "abcde..." en "abcae...". Une copie ainsi faite sans précaution aurait alors donné la chaine finale "abcabcabc...".
Ce qui se passe d'ailleurs pour ch2, qui passe par une copie bécasse qui se soucie de que dalle, et qui contient au final "abcabcabcabcabcabcabcabcabcabc"...

[Médinoc]

Ce qui est bien avec les comportements indéfinis, c'est que l'implémentation peut faire ce qu'elle veut.
Je viens de regarder le code de la C Run-Time Library de Visual 2005 (car je ne crois pas avoir les sources pour les autres versions, qui sont des Express alors que ma 2005 est une Pro), et ça fait distinctement de la copie aveugle (du moins, en 32 bits):

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
/***
*memcpy - Copy source buffer to destination buffer
*
*Purpose:
*       memcpy() copies a source memory buffer to a destination memory buffer.
*       This routine does NOT recognize overlapping buffers, and thus can lead
*       to propogation.
*
*       For cases where propogation must be avoided, memmove() must be used.
<snip>*/

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
        /*
         * copy from lower addresses to higher addresses
         */
        while (count--) {
                *(char *)dst = *(char *)src;
                dst = (char *)dst + 1;
                src = (char *)src + 1;
        }

Si ça se trouve, sur ta plate-forme, memcpy() a été directement mappé sur memmove() pour raisons de sécurité...

---

Edit: Wow, je suis tombé sur un memcpy.asm qui n'est pas d'accord avec le source C:
Dans memcpy.asm, je vois un commentaire qui dit ça:

Code asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
;       Algorithm:
;
;           Same as memmove. See Below

Et voici le code asm qui introduit la fonction:

Code asm :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
ifdef MEM_MOVE
        _MEM_     equ <memmove>
else  ; MEM_MOVE
        _MEM_     equ <memcpy>
endif  ; MEM_MOVE
 
%       public  _MEM_
_MEM_   proc \
        dst:ptr byte, \
        src:ptr byte, \
        count:IWORD

Traduit en C, ça donnerait ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
#ifdef MEM_MOVE
#define _MEM_ memmove
#else
#define _MEM_ memcpy
#endif
 
void _MEM_(void* dst, void const* src, size_t count)
{

Et derrière, exactement le même code.
Donc dans le asm, memcpy() est mappé sur memmove()!

[Sve@r]

Ce qui est bien avec les comportements indéfinis, c'est que l'implémentation peut faire ce qu'elle veut.

Peut-on vraiment parler de comportement indéfini dans ce cas ? Je préfère plutôt penser que les développeurs de la libC de ma plateforme (une Linux Debian Wheezy mais je suis certain que ce serait pareil sur toutes les autres distribs et peut-être même aussi sur de vrais Unix) ont codé le truc de façon correcte. C'est vrai quoi, on te demande de coder un truc, le fait que ledit truc doive fonctionne correctement dans toutes les configurations est une condition implcite même si elle n'est pas expressément écrite...
Sinon bon t'as regardé le code source de memcpy de ton Visual C, trouvé aussi un code asm qui semble contredire ledit source, mais est-ce que t'as essayé de tester ton memcpy avec mon code de test ??? C'est finalement le plus simple. Tiens par exemple je viens de tester mon code sur Code::Blocks (W7) et le comportement est exactement le même

[Médinoc]

Peut-on vraiment parler de comportement indéfini dans ce cas ?

C'est indéfini parce que la norme dit que c'est indéfini, et que la version sans aucun test est considérée comme une implémentation correcte.

mais est-ce que t'as essayé de tester ton memcpy avec mon code de test ??? C'est finalement le plus simple. Tiens par exemple je viens de tester mon code sur Code::Blocks (W7) et le comportement est exactement le mêm

Tu as raison.
Je viens de tester sous Visual Studio 2005:

• Debug Win32: Il utilise précisément l'asm que j'ai regardé, d'après le debugger. --> Comportement memmove().
• Debug Win64: Il utilise un asm aussi (mais que je n'ai pas), que je présume être une version 64 bits du précédent. --> Comportement memmove().
• Release Win32: Pareil que Debug (le contraire aurait été stupide, dans ce sens)
• Release Win64: Pareil que Debug

En fait, le fameux memcpy() en C, il n'a pas l'air de l'utiliser, il utilise systématiquement la version asm qui est une copie de memmove().
Et c'est parfaitement logique: Accent sur la sécurité, etc., et de nos jours, la performance étant ce qu'elle est, le memcpy() de la norme, qui sacrifie la sécurité pour quelques cycles, n'a plus lieu d'être.

[Sve@r]

C'est indéfini parce que la norme dit que c'est indéfini

Exact - Je viens d'ailleurs de retomber sur cette discussion à laquelle tu avais déjà participé. Mais là encore il y a un truc qui me chiffonne: ok, les programmeurs originels ont programmé memcpy() de façon brute, sans aucune vérification afin de probablement produire le code le plus rapide possible (le code d'origine devrait d'ailleurs ressembler furieusement à mon mymemcpy() qui peut être encore raccourci si on supprime "i" mais qui peut difficilement ensuite l'être plus). Mais en quoi cela produit un comportement indéterminé ??? Les zones de travail sont parfaitement licites. Par exemple en prog normale j'ai parfaitement le droit d'écrire char tab[10]="abcdefghi"; for (i=1; i < 10; tab[i]=tab[i-1],i++); et ce code ne produit pas de comportement indéterminé. Dans mon code de test j'ai fourni à ma fonction mymemcpy() deux zones de travail de 40 octets en lui demandant d'en copier 27 à un endroit où je savais que ces 27 y rentreraient. Et donc bien que ces zones se chevauchent, ma fonction mymemcpy() ne produit pas un comportement indéterminé mais justement parfaitement déterminé. Alors qu'est-ce qui fait que le vieux memcpy() avait un comportement indéterminé dans ce cas ? Aurait-il été programmé avec des routines spéciales en plus pour détecter que les zones se chevauchent afin de forcer le comportement indéterminé dans ce cas là ???

Ou alors le comportement est indéterminé dans le cas où les paramètres passés à memcpy() la conduisent à écrire dans une zone qui n'est normalement pas accessible mais dans ce cas ce n'est pas la peine de le dire car ce comportement sera le même quelle que soit la fonction appelée...

[Médinoc]

Franchement, je ne sais pas. Probablement parce que c'était plus simple et moins contraignant que de décider "le contenu du buffer au retour de la fonction dépend de l'implémentation"; et la liberté semblait être le mot d'ordre quand la norme a été écrite.
Je pense qu'à l'époque si ça avait été mon boulot, j'aurais dit "implémentation". De nos jours, soit je n'aurais pas fait de fonction séparée, soit j'aurais fait une fonction qui détecte l'overlap et "échoue" (retour de valeur d'erreur, exception, signal etc.) dans ce cas.


Par contre, je viens de penser qu'il existe toujours une raison d'être à memcpy() (et au comportement indéfini), (en ignorant la compatibilité ascendante): Les paramètres de memcpy() sont probablement déclarés restrict, ce qui permet à l'appelant de faire des optimisations en supposant qu'il n'y a pas de chevauchement, et donc que le buffer source ne sera pas modifié par la fonction. L'optimiseur adore les comportements indéterminés, car il peut supposer ce qu'il veut (y compris rétroactivement supprimer toute une branche du code si elle mène inconditionnellement à un UB).