CRC31 - Page 1

Hello!
En fait je ne comprends pas bien les propriétés qui font qu'un CRC32 est relativement efficace (dans un environnement où on ne va pas chercher à tricher). J'aimerais bien lui couper une patte (faire un crc32 sur 31 bits quoi) pour pouvoir réutiliser un bit.
La raison pour laquelle j'en ai besoin est assez lame mais on peut imaginer des cas où ça peut réellement être utile, comme par exemple dans un bootloader pour un firmware, de rajouter une valeur "non initialisée" utilisée la première fois, qui ferait foirer à tous les coups la vérification si aucun firmware n'a encore été programmé, même si le CRC joue quand même par hasard.
La question c'est... si un bit je dois enlever, lequel puis-je pour ne pas retirer les propriétés qui rendent le CRC32 efficace?
(je suis conscient qu'il existe un CRC30, je ne sais pas s'il est efficace, mais je désirerais garder la compatibilité avec des CRC32 déjà générés pour mon appli)
Merci d'avance

Brunni (./1) :
rajouter une valeur "non initialisée" utilisée la première fois, qui ferait foirer à tous les coups la vérification si aucun firmware n'a encore été programmé, même si le CRC joue quand même par hasard.

Si tu parles d'une mémoire vierge, le contenu est connu, et il suffit de rajouter un XOR avec une valeur bien choisie pour que le test échoue dans ce cas.

Sinon, je pense qu'il est plus simple de rajouter quelques octets constants quelque part dans ton firmware, que tu vérifies avant le calcul du CRC, et qui font échouer le test dans tous les cas s'ils ne sont pas présents. Bidouiller le CRC, ça me paraît un peu acrobatique, surtout que les capacités de détection d'erreur peuvent varier fortement pour des petites modifs de l'algorithme (c'est pour ça qu'en général on prend toujours les mêmes coefficients).

Oui, explique plutôt quelle est ta réelle intention derrière cette "réutilisation de bit"
Sinon l'idée du XOR est pas bête. Enfin, je l'utiliserais d'une autre manière que proposée par Zerosquare.
Par exemple, tu définis deux valeurs. Au pif FALSE=0xAAAAAAAA et TRUE=0x55555555. Selon la valeur de ton "flag en plus", tu stockes CRC32 ^ TRUE ou CRC32 ^ FALSE.
Ensuite pour la vérification et récupération du flag, tu calcules CRC32_REEL. Tu compares CRC32 (le champ stocké) à CRC32_REEL ^ TRUE et à CRC32_REEL ^ FALSE, si ça correspond tu sais à la fois que ton CRC32 est valide et la valeur de ton flag.

En fait tu retires juste deux cas de détection d'erreur en faisant ça, mais c'est inévitable. En gros pour un CRC32 donné il y aura deux valeurs de champ valides, et c'est pour ça qu'on prend des masques de bits bien répartis pour les flags, ça réduit beaucoup les erreurs dues à la corruption. Si quelqu'un peut modifier ton champ CRC32 les risques de sécurité ne sont pas plus élevés que sans le "hack" des flags XOR. Mais pour la valeur CRC32 XOR Flag stockée, tu pourras également valider deux valeurs de CRC32 calculé. Ça pourrait être utilisé de manière malveillante, comme ça pourrait te conduire à accepter des données corrompues, mais là c'est un risque à prendre.

(PS: Je propose d'appeler ça le CRC32 - 1 )

En fait c'est assez lame comme je l'ai dit. C'est pour mon système de coloration de jeux GB, cf http://brunni.dev-fr.org/index.php?page=pspsoft_masterboy.
En (très) gros, le CRC sélectif de certaines tiles en VRAM est utilisé pour détecter la scène courante. Une scène consiste en un petit programme affectant des palettes à chaque tile.
J'aimerais donner la possibilité de créer une scène "défaut", dont le CRC serait 0 par exemple, mais à ce moment il n'est plus possible d'avoir une scène avec un CRC 0, ce qui est problématique. C'est pourquoi j'aimerais enlever un bit pour créer une catégorie de scènes spéciales, sans avoir à rajouter un octet de plus indiquant si la scène est celle par défaut (assez dégueulasse).

Je suis pas certain de comprendre...
Tu veux définir une scène par défaut ok...
Mais pourquoi tu as besoin de lui affecter un CRC
Sinon y'a bien moyen de faire, mais je voudrais d'abord comprendre ça.

En fait ce serait pour un format binaire, une scène peut "appeler" une autre (par exemple default). Si tu veux d'un point de vue de syntaxe ce serait:

Scene #12345678 inherits #12121212, MaScènePerso is
    -- Exemple bête: tout gris
    Palette 0 is #ffffff, #aaaaaa, #555555, #0 for 0..383;
End Scene;

Les scènes perso se verraient attribuer un n° de scène ayant un bit précis mis à un qui feront qu'elles échoueront toujours au check du CRC et donc ne seront pas appelées automatiquement mais seulement par le prog utilisateur.
Dans le format binaire on aurait:

u16 nbScènes;
struct {
    u32 crc;
    u32 adresse;
} scenes[nbScènes];

// Définition de la première scène
[cmd:setPalette] [noPalette] [color (16X)]

// Définition d'une scène faisant appel à l'autre
[cmd:call] [crc]

Tu vois le truc?
J'aimerais vraiment garder le format la plus simple possible histoire que ça soit facile à intégrer dans un ému (l'adoption éventuelle du système dépendra de ça).

Brunni (./6) :
elles échoueront toujours au check du CRC

Donc tu as pas besoin de leur attribuer un CRC, non ?
Sinon, tu devrais effectivement virer un bit mais c'est clairement à éviter
Je sais pas comment fonctionne ton format actuellement, mais si tu accédais aux scènes par leur offset [dans le fichier], ou numéro dans la table, ça sera tout de suite plus propre

Rhaa ça me complexifie la compilation :P Mais c'est effectivement la meilleure solution si le troncage du CRC est si problématique ^^
Juste pour voir c'était quoi ton "moyen de faire" dont tu parlais en ./5?
Ha et merci de votre aide éclairée

Heu le moyen en ./5 c'était d'allouer un numéro CRC32 à la volée, parmi ceux non utilisés, pour la scène "par défaut". Mais ça marche que si tu en veux une seule, et ça te dispense pas de faire un test if (CRC32 != CRC32_SCENE_PAR_DEFAUT) { }.
Enfin quoi qu'il en soit c'est crade
Le problème plus général ici c'est que tu as [cherché à] mélanger deux moyens d'identification pour n'en faire qu'un seul, puis introduit un élément d'incompatibilité entre les deux (un élément qui doit exister d'un côté mais pas de l'autre -> la symétrie est brisée).
Pour ça, le meilleur moyen (mais pas le seul on est bien d'accord) est souvent de séparer à nouveau les deux moyens d'identification.