Combinaison CRC32 en Rust

An English version of this post is available.

Je travaille sur un projet en Rust où je dois vérifier la somme de contrôle CRC32 d'un fichier. C'est assez facile de le faire en utilisant la crate CRC. Cette crate fourni plusieurs méthodes pour calculer un CRC32.

CRC, Cyclic Redundancy Code, computing enable one receiver to check that transmitted data is error free. To do so, the data sender compute a checksum that depends on the sent data and transmit it. The receiver also compute the checksum, this time from the received data and match it against the sender's one. If they are equal, data was transmitted without error.

Traduction:

Le calcul d'une somme de contrôle de redondance cyclique, CRC, permet à un destinataire de vérifier que les données transmises ne comportent pas d'erreurs. Pour cela, l'expéditeur calcule une somme de contrôle qui dépend des données envoyées et le transmet. Le destinataire calcule aussi la somme de contrôle, cette fois depuis les données reçues et la compare avec celle de l'expéditeur. Si elles sont égales, les données ont été transmises sans erreur.

Mon but était de reconstruire un fichier découpé en plusieurs parties encodées. yEnc ça parle à quelqu'un ?

Chaque partie à sa propre somme de contrôle embarquée en chaine hexadécimale, que je peux utiliser pour vérifier une fois que j'en ai décodé les données pour vérifier qu'elles sont exactes.

Quelque chose du genre :

fn check_crc32(input: &String, crc32: u32) -> bool {
    match u32::from_str_radix(input, 16) {
        Ok(parsed_crc32) => parsed_crc32 == crc32,
        Err(_) => false
    }
}
...
check_crc32("aca76043", my_computed_crc)

Une fois que j'ai décodé toutes les parties d'un fichier, je recrée le fichier en écrivant toutes les parties à leur offset de destination dans mon fichier de sortie.

Une des parties peut contenir la somme de contrôle CRC32 totale du fichier. Si c'est le cas, je voudrais la comparer avec celle de mon fichier reconstruit.

Premier essai

En décodant les parties, je pensais d'abord partager un crc32::Digest et le mettre à jour tout en écrivant mes données décodées vers mon buffer Vec<u8> de destination. Une fois toutes les parties décodées, j'aurais alors demandé le digest de la somme de contrôle CRC32.

Après avoir galéré un peu avec le borrow checker, j'ai réussi à décoder un fichier de 175 parties de 100Mo. Coul !

Cependant, quand j'ai vérifié mon CRC32 calculé, il :

• n'était pas le même que celui fourni dans les parties du fichier et surtout
• n'était pas le même que celui calculé par l'utilitaire Unix crc32.

Mais mes données écrites sur disque correspondaient bien au CRC32 fourni. Donc à l'évidence je m'étais foiré quelque part.

Pas si vite, imbécile

Pour accélérer le décodage, je lisais une partie à la fois, la décodait en mémoire et mettait à jour le digest dans la volée. De temps en temps, je flushais les données décodées vers le disque, ne gardant en mémoire que les métadonnées à propos des parties déjà lues.

Je remarquais alors rapidement que lire les parties des données dans un ordre aléatoire n'était pas une si bonne idée...

En effet, la somme de contrôle CRC32 est calculée au fur et à mesure que les données sont écrite vers le digest. Donc la mettre à jour en lui balançant les parties décodées dans un ordre aléatoire n'était pas la bonne manière de faire.

J'aurais pu réouvrir le fichier, en relire tous les octets et reconstruire la somme de contrôle. Mais si je devais reconstruire un fichier de 4Go je ne voulais pas passer mon temps à recalculer la somme de contrôle en relisant une nouvelle fois l'intégralité des données que je venais juste de décoder.

De plus, je voulais multithreader fearlessly le décodage ou le calcul de la somme de contrôle, je devais donc trouver une autre solution.

Et... si je pouvais calculer le CRC32 de l'intégralité du fichier en combinant toutes les sommes de contrôle des parties données ? ÇA ça serait top.

Debout sur les épaules des géants

Évidemment, d'autres avaient déjà traité ce problème. Et bien mieux que vous ne pourriez l'imaginer avec votre seul esprit.

Dans la fameuse bibliothèque zlib Mark Adler a écrit cette fonction pas trop documentée : https://github.com/madler/zlib/blob/master/crc32.c#L372 .

Je ne vais pas m'épancher sur les détails de comment ça fonctionne, il l'a déjà expliqué en long et en large ici.

Ce que JE savais, c'est que j'en avais besoin. Et il n'y a pas de fonction correspondante dans la crate CRC.

Une rapide recherche à son sujet indiquait que la plupart du temps, les gens préférent dépendre de la crate libz-sys. Mais je ne voulais pas dépendre de plusieurs crates pour mon petit projet pour jouer.

Plutôt que de faire du rust unsafe en appelant la bibliothèque C, j'ai décidé de prendre le taureau par les cornes et d'y aller à la rouille !

La solution

Si vous cherchez une fonction crc32_combine en pur rust, voila mon implémentation. Vous aurez deviné qu'elle est massivement inspirée de la fonction C de la Zlib.

Combines deux sommes de contrôle CRC en une. Pour deux jeux de données, Data1 et Data2 avec des tailles de len1 et len2, avec des sommes de contrôles CRC crc1 et crc2. Cette fonction retourne la somme de contrôle CRC de [Data1,Data2], en ne nécessitant que crc1, crc2, et len2.

/* zlib.h -- interface of the 'zlib' general purpose compression library
  version 1.2.11, January 15th, 2017

  Copyright (C) 1995-2017 Jean-loup Gailly and Mark Adler

  This software is provided 'as-is', without any express or implied
  warranty.  In no event will the authors be held liable for any damages
  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.

  Jean-loup Gailly        Mark Adler
  jloup@gzip.org          madler@alumni.caltech.edu

*/
const GF2_DIM: usize = 32; // dimension of GF(2) vectors (length of CRC)

fn gf2_matrix_times(mat: &[u32], vec: u32) -> u32 {
    let mut sum = 0;
    let mut idx = 0;
    let mut vec = vec;
    while vec != 0 {
        if (vec & 1) != 0 {
            sum ^= mat[idx];
        }
        vec >>= 1;
        idx += 1;
    }
    sum
}

fn gf2_matrix_square(square: &mut [u32; GF2_DIM], mat: &[u32; GF2_DIM]) {
    for n in 0..GF2_DIM {
        let d = mat[n];
        square[n] = gf2_matrix_times(mat, d);
    }
}

fn crc32_combine(crc1: u32, crc2: u32, len2: u32) -> u32 {
    let mut even: [u32; GF2_DIM] = [0; GF2_DIM]; // even-power-of-two zeros operator
    let mut odd: [u32; GF2_DIM] = [0; GF2_DIM]; // odd-power-of-two zeros operator

    let mut crc1 = crc1;
    let mut len2 = len2;

    // degenerate case (also disallow negative lengths
    if len2 <= 0 {
        return crc1;
    }

    // put operator for one zero bit in odd
    odd[0] = 0xedb88320; // CRC-32 polynomial
    let mut row = 1;
    for i in 1..GF2_DIM {
        odd[i] = row;
        row <<= 1;
    }

    // put operator for two zero bits in even
    gf2_matrix_square(&mut even, &odd);

    // put operator for four zero bits in odd
    gf2_matrix_square(&mut odd, &even);

    // apply len2 zeros to crc1 (first square will put the operator for one
    // zero byte, eight zero bits, in even)
    loop {
        // apply zeros operator for this bit of len2
        gf2_matrix_square(&mut even, &odd);

        if (len2 & 1) != 0 {
            crc1 = gf2_matrix_times(&even, crc1);
        }
        len2 >>= 1;

        // if no more bits set; then done
        if len2 == 0 {
            break;
        }

        // another iteration of the loop with odd and even swapped
        gf2_matrix_square(&mut odd, &mut even);
        if (len2 & 1) != 0 {
            crc1 = gf2_matrix_times(&odd, crc1);
        }
        len2 >>= 1;

        if len2 == 0 {
            break;
        }
    }

    // return combined crc
    crc1 ^= crc2;
    return crc1;
}

Exemple d'utilisation :

let mut computed_crc32 = 0;
for part in &self.parts {
    let part_crc32 = match u32::from_str_radix(
        &part.infos.trailer.part_crc32.as_ref().unwrap().clone(),
        16,
    ) {
        Ok(parsed_crc32) => parsed_crc32,
        Err(error) => return Err(decoding_error("gnuh".to_string())),
    };
    println!("parsed pcrc32 {:x}", part_crc32);
    computed_crc32 = crc32_combine(computed_crc32, part_crc32, part.infos.trailer.file_size);
}
println!("combined crc32 : {:x}", computed_crc32);