J'ai une question relative aux mathématiques et à la programmation sur les calculs CRC, pour éviter de recalculer le CRC complet pour un bloc lorsque vous ne devez en changer qu'une petite partie.

Mon problème est le suivant: j'ai un bloc de 1K de structures de 4 octets, chacune représentant un champ de données. Le bloc 1K complet a un bloc CRC16 à la fin, calculé sur le 1K complet. Quand je dois changer seulement une structure de 4 octets, je devrais recalculer le CRC du bloc complet mais je recherche une solution plus efficace à ce problème. Quelque chose où:

  1. Je prends le CRC16 courant de bloc complet de 1K

  2. Je calcule quelque chose sur l'ancien bloc de 4 octets

  3. Je "soustrais" quelque chose obtenu à l'étape 2 du CRC16 1K complet

  4. Je calcule quelque chose sur le nouveau bloc de 4 octets

  5. J'ajoute quelque chose obtenu à l'étape 4 au résultat obtenu à l'étape 3

Pour résumer, je pense à quelque chose comme ceci:

CRC (nouveau-complet) = [CRC (ancien-complet) - CRC (ancien bloc) + CRC (bloc-nouveau)]

Mais je manque le calcul derrière et ce qu'il faut faire pour obtenir ce résultat, compte tenu également d'une «formule générale».

Merci d'avance.

2
PeppeA82 26 janv. 2019 à 14:57

3 réponses

Meilleure réponse

Prenez votre bloc A initial de 1024 octets et votre nouveau bloc de 1024 octets B.Exclusif - ou eux pour obtenir le bloc C.Depuis que vous n'avez changé que quatre octets, C sera un tas de zéros, quatre octets qui sont l'exclusif ou du précédent et nouveau quatre octets, et un tas de zéros supplémentaires.

Calculez maintenant le CRC-16 du bloc C, mais sans aucun pré ou post-traitement. Nous appellerons cela CRC-16 '. (J'aurais besoin de voir le CRC-16 spécifique que vous utilisez pour voir quel est ce traitement, le cas échéant.) Exclusif - ou le CRC-16 du bloc A avec le CRC-16 'du bloc C, et vous avez maintenant le CRC-16 du bloc B.

À première vue, cela peut ne pas sembler un grand gain par rapport au simple calcul du CRC du bloc B. Cependant, il existe des astuces pour calculer rapidement le CRC d'un groupe de zéros. Tout d'abord, les zéros précédant les quatre octets qui ont été modifiés donnent un CRC-16 'de zéro, quel que soit le nombre de zéros. Donc, vous commencez simplement à calculer le CRC-16 'avec l'exclusif-ou des quatre octets précédents et nouveaux.

Maintenant, vous continuez à calculer le CRC-16 'sur les n zéros restants après les octets modifiés. Normalement, il faut O ( n ) temps pour calculer un CRC sur n octets. Cependant, si vous savez qu'ils sont tous des zéros (ou tous une valeur constante), alors il peut être calculé en temps O (log n ). Vous pouvez voir un exemple de la façon dont cela est fait dans zlib's {{X0} } routine et appliquez-la à votre CRC.

Compte tenu de vos paramètres CRC-16 / DNP, la routine zeros() ci-dessous appliquera le nombre demandé de zéro octet au CRC en temps O (log n ).

// Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC
// polynomial, reflected. For speed, this requires that a not be zero.
uint16_t multmodp(uint16_t a, uint16_t b) {
    uint16_t m = (uint16_t)1 << 15;
    uint16_t p = 0;
    for (;;) {
        if (a & m) {
            p ^= b;
            if ((a & (m - 1)) == 0)
                break;
        }
        m >>= 1;
        b = b & 1 ? (b >> 1) ^ 0xa6bc : b >> 1;
    }
    return p;
}

// Table of x^2^n modulo p(x).
uint16_t const x2n_table[] = {
    0x4000, 0x2000, 0x0800, 0x0080, 0xa6bc, 0x55a7, 0xfc4f, 0x1f78,
    0xa31f, 0x78c1, 0xbe76, 0xac8f, 0xb26b, 0x3370, 0xb090
};

// Return x^(n*2^k) modulo p(x).
uint16_t x2nmodp(size_t n, unsigned k) {
    k %= 15;
    uint16_t p = (uint16_t)1 << 15;
    for (;;) {
        if (n & 1)
            p = multmodp(x2n_table[k], p);
        n >>= 1;
        if (n == 0)
            break;
        if (++k == 15)
            k = 0;
    }
    return p;
}

// Apply n zero bytes to crc.
uint16_t zeros(uint16_t crc, size_t n) {
    return multmodp(x2nmodp(n, 3), crc);
}
3
Mark Adler 5 févr. 2019 à 04:33

Le CRC dépend du CRC calculé des données avant. La seule optimisation est donc de diviser de manière logique les données en N segments et de stocker l'état CRC calculé pour chaque segment.

Puis, par exemple modifier le segment 6 (de 0..9), obtenir l'état CRC du segment 5 et continuer à calculer le CRC en commençant par le segment 6 et en terminant par 9.

Quoi qu'il en soit, les calculs CRC sont très rapides. Alors réfléchissez, si cela en vaut la peine.

0
Wiimm 26 janv. 2019 à 12:03

Le CRC en fait une chose facile à faire.

En examinant cela, je suis sûr que vous avez commencé à lire que les CRC sont calculés avec des polynômes sur GF (2), et ont probablement passé cette partie aux informations immédiatement utiles. Eh bien, il semble qu'il soit probablement temps pour vous de revenir sur ces choses et de les relire plusieurs fois pour que vous puissiez vraiment les comprendre.

Mais peu importe...

En raison de la façon dont les CRC sont calculés, ils ont une propriété qui, étant donné deux blocs A et B, CRC (A xor B) = CRC (A) xor CRC (B)

Donc, la première simplification que vous pouvez faire est qu'il vous suffit de calculer le CRC des bits modifiés. Vous pouvez en fait précalculer les CRC de chaque bit du bloc, de sorte que lorsque vous changez un peu, vous pouvez simplement xor c'est CRC dans le CRC du bloc.

Les CRC ont également la propriété que CRC (A * B) = CRC (A * CRC (B)), où cela * est une multiplication polynomiale sur GF (2). Si vous remplissez le bloc avec des zéros à la fin, ne faites pas cela pour CRC (B).

Cela vous permet de vous en sortir avec une table précalculée plus petite. "Multiplication polynomiale sur GF (2)" est une convolution binaire, donc multiplier par 1000 équivaut à un décalage de 3 bits. Avec cette règle, vous pouvez précalculer le CRC du décalage de chaque champ. Ensuite, il suffit de multiplier (convoluer) les bits modifiés par le CRC de décalage (calculé sans bourrage nul), de calculer le CRC de ces 8 octets et de les xor dans le bloc CRC.

2
Matt Timmermans 26 janv. 2019 à 13:35