CRC-32 Pas très clair

Version imprimable

Bonjour les djeuns :]

En lisant l'article de developpez.com sur l'implémentation du CRC-16, donc après avoir cru comprendre l'algorithme j'ai essayé de le refaire en 32bits :$
Mais bon j'ai découvert que je n'avais compris que dale et mon algorithme marche pas car qu'on j'ajoute un espace DEVANT ma phrase la cléf reste la même :/
Voilà ma source en C, et merci pour votre aide

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define _CCIT_POLYNOME		0x04c11db7
#define _CCIT_INIT_VALUE	0x00000000
 
 
/**************************************************/
		/*Types definition*/
typedef unsigned long long int  uint_64; /*unsigned 64bits*/ 
typedef unsigned int   		uint_32; /*unsigned 32bits*/
typedef unsigned short 		uint_16; /*unsigned 16bits*/
typedef unsigned char  		uint_8;  /*unsigned 8bits*/
 
typedef union{
		uint_64 value;
		struct{
			uint_8 tail;
			uint_32 remainder;
			uint_8 head;
		}part;
}CRC32_PART;
 
/**************************************************/
 
/**************************************************/
		/*Global declarations*/
static CRC32_PART ccit_reg;
 
/**************************************************/
 
/**************************************************/
		/*functions*/
void OneBytesCrc32 (uint_8 byte){
 
	int bitscounter = 8;
 
		ccit_reg.part.tail = byte;
 
 
			do{
				ccit_reg.value <<= 1;	
					if (ccit_reg.part.head & 0x01)
						ccit_reg.part.remainder ^= _CCIT_POLYNOME;
			}while (--bitscounter);
 
}
 
uint_32 StringtoCCIT32 (char* str, unsigned len){
 
	int i;	
 
		ccit_reg.part.remainder = _CCIT_INIT_VALUE;
			for (i=0; i<len; i++)
				OneBytesCrc32 (str[i]);
 
		OneBytesCrc32 (0x00);
		OneBytesCrc32 (0x00);
		//OneBytesCrc32 (0x00);
		//OneBytesCrc32 (0x00);
	return ccit_reg.part.remainder;
}
 
/**************************************************/
 
int main (int argc, char* argv[]){
 
	char *p = "Developpez";
	uint_32 crc;
 
		crc = StringtoCCIT32 (p, strlen (p));
	printf ("0x%x\n", crc);
 
 
 return 0;
}

Au passage, pourquoi on doit faire:

Code:

1
2
OneBytesCrc32 (0x00);
OneBytesCrc32 (0x00);

?
Merci encore ;)

16/10/2006, 15h05
Goundy

rhooo les mecs, que dale? personne ne peut me dire ou j'ai mauvais ? :(
16/10/2006, 16h47
Sivrît
Code:

ccit_reg.part.remainder = _CCIT_INIT_VALUE

L'initialisation est incomplète mais je chipotte.

Head est toujours à 0, donc pas de XOR. Bref on a juste un décalage à gauche et un caractère ajouté au début ne laisse aucune trace quand on arrive au 'z'.

Les adresses des différents morceaux :
Code:

1 2 3 4 5 v=0x403010 t=0x403010 r=0x403014 h=0x403018
Voilà l'explication : tail mobilise 4 octets ce qui met head en dehors de nos 64 bits. Je suppose que c'est une question d'alignement sur des mots de 32 bits. Plus qu'à trouver une solution...

Conclusion: printf est l'outil de débogage ultime :mouarf:

Une solution avec gcc:

Code:

1
2
3
4
5
6
7
8
9
 
typedef union{
                uint_64 value;
                struct{
                        uint_8 tail;
                        uint_32 remainder;
                        uint_8 head;
                } __attribute__ ((__packed__)) part;
} CRC32_PART;

Un peu bof. Sinon sortir l'arithmétique des pointeurs... bien bof aussi :?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#define _CCIT_POLYNOME		0x00000004c11db700ULL
#define _CCIT_INIT_VALUE	0x0000000000000000ULL
 
typedef union{
        uint_64 value;
        uint_8 tail;
}CRC32_PART;
 
void OneBytesCrc32 (uint_8 byte){
    int bitscounter = 8;
    ccit_reg.tail = byte;
    do {
        ccit_reg.value <<= 1;	
        if (ccit_reg.value & 0x0000010000000000ULL)
            ccit_reg.value ^= _CCIT_POLYNOME;
    } while (--bitscounter);
}
 
uint_32 StringtoCCIT32 (char* str, unsigned len){
    int i;	
 
    ccit_reg.value = _CCIT_INIT_VALUE;
    for (i=0; i<len; i++)
        OneBytesCrc32 (str[i]);
 
    OneBytesCrc32 (0x00);
    OneBytesCrc32 (0x00);
 
    return (ccit_reg.value>>8) & 0xffffffff;
}

Edit: enfin trouvé comment entrer les litéraux de 64 bits

17/10/2006, 15h46
Goundy

Merci beaucoup, çà marche nickel maintenant par contre c'est assez sombre pour moi, comment tail pourrait-il mobiliser 4octets alors qu'il ne fait que 1 bit ???
J'avoue que j'ai du mal, je croyais avoir compris mais là ...

Sinon, pourquoi encore :
OneBytesCrc32 (0x00);
OneBytesCrc32 (0x00);
?

merci ;)
17/10/2006, 16h42
Sivrît

Citation:

Envoyé par Goundy

Merci beaucoup, çà marche nickel maintenant par contre c'est assez sombre pour moi, comment tail pourrait-il mobiliser 4octets alors qu'il ne fait que 1 bit ???
J'avoue que j'ai du mal, je croyais avoir compris mais là ...

Question d'alignement. Les processeurs actuels travaillent en 32bits donc par paquets de 4 octets. Il est donc possible que le compilateur aligne les adresses de façon à ce qu'elles tombent sur des multiples de 4. Ou bien ( :alerte: supposition) il est possible que le processeur ait du mal à travailler sur un octet (du moins sans devoir utiliser des masques et multiplier les opérations pour faire tenir le 1 dans ses 4 octets et réciproquement) et que le compilateur s'en réserve donc 4 pour utiliser ses opérations usuelles en ignorant les 3 derniers octets. Un peu comme le booléen qui fait toujours un octet.
Les structures masquent tout cela (encore heureux) mais ne garantissent manifestement pas que "&item2 = (&item1)+sizeof(item1)"

Citation:

Envoyé par Goundy

Sinon, pourquoi encore :
OneBytesCrc32 (0x00);
OneBytesCrc32 (0x00);
?

Alors là... peut-être pour garantir que l'algo ait un minimum tourné ?
17/10/2006, 21h04
Goundy

Merci mon vieux, j'ai tout compris :)
Merci beaucoup !!!