Brevet FR2947926A1 — publié le 20110114

Procédé de compaction du contenu d'un CD-ROM sur une mémoire de faible capacité L'invention concerne de façon générale la compaction de données. Elle consiste à mettre en oeuvre un mécanisme de compaction de données pour stocker le contenu d'un CD-ROM virtuel sur un système embarqué disposant d'une mémoire interne de capacité limitée, très inférieure à la capacité du CD-ROM virtuel. Le io procécé de l'invention couvre aussi bien la méthode de compaction que la méthode de restitution (décompaction) des données. L'invention sera plus particulièrement décrite dans son application à un microcontrôleur pourvu de peu de mémoire interne. On rencontre ce type de microcontrôleurs notamment dans certaines clés de type USB, notamment lorsque 15 ces clés sont dédiées à des applications qui doivent consommer peu de mémoire, pour être les plus économiques possible. On rencontre notamment ce type d'applications par exemple dans le cas où une clé USB équipée d'un microcontrôleur pourvu uniquement de quelques dizaines à quelques centaines de kilo-octets de mémoire, doit émuler le contenu d'un CD-ROM, 20 et notamment sa fonction � autorun �, lors de la connexion de la clé USB à un dispositif hôte comme un ordinateur personnel. L'invention sera par conséquent décrite dans ce contexte applicatif, mais uniquement à titre d'exemple non limitatif, étant entendu que l'invention s'applique à d'autres objects portables associés à un microcontrôleur ayant peu de mémoire 25 interne. ETAT DE LA TECHNIQUE On connaît déjà dans l'état de la technique, le fait de stocker l'image complète d'un CD-ROM, encore appelée CD-ROM virtuel, sous sa forme originale et 30 complète sur une mémoire interne ou externe d'un système informatique. Cela requiert que la mémoire sur laquelle le CD-ROM virtuel est copié soit de capacité suffisante, sachant que la taille binaire maximale d'un CD-ROM virtuel est de l'ordre de 700 mégaoctets. Il est donc évident que cette technique de copie de l'image d'un CD-ROM virtuel ne convient pas du tout lorsque la quantité de mémoire disponible au niveau de la mémoire cible est faible, à fortiori lorsque seulement quelques dizaines à quelques centaines de kilo-octets sont disponibles, comme cela peut être le cas pour le microcontrôleur d'une clé USB pourvu uniquement d'une petite mémoire flash. Bien entendu, de façon générale, les mémoires flash externes au contrôleur peuvent être de grande taille, mais l'invention se place dans le contexte dans lequel io une telle mémoire flash de grande taille n'est pas disponible, notamment pour des raisons de coût. En effet, un microcontrôleur de clé USB dédiée à des applications à faible coût, possède une mémoire flash interne limitée de l'ordre de 32 à 512 Ko. On connaît par ailleurs de multiples procédés de compression de données, is comme par exemple les algorithmes ZIP, LHA, ARC ou RLE, qui sont bien connus de l'homme du métier. Ils sont très efficaces en termes de taux de compression, mais leur code prend trop de place pour être stocké dans le faible espace mémoire disponible par exemple dans la mémoire interne d'un microcontrôleur de clé USB dédié à des applications où le coût de la mémoire peut poser problème. En outre, la 20 mémoire volatile requise pour leur exécution est également plus importante que celle disponible dans le microcontrôleur d'une clé USB. Par conséquent ces systèmes de compression connus ne conviennent pas lorsque la capacité de la mémoire flash interne disponible pour stocker le code du procédé de compaction, est limitée à quelques dizaines ou centaines de Ko. 25 Or il peut être très intéressant de copier certaines parties de l'image d'un CD-ROM dans la mémoire interne du microcontrôleur d'une clé USB, ou dans la mémoire interne de faible capacité d'un autre dispositif. Les parties de l'image virtuelle d'un CD-ROM qu'il serait utile de pouvoir copier concernent notamment la fonction dite � autorun � (lancement automatique d'un programme à l'insertion), qui est souvent mise en oeuvre par un fichier AUTORUN.INF qui référence d'autres fichiers, dont par exemple un programme qui peut être lancé depuis le CD-ROM. Cette fonction � autorun �, Si elle était disponible sur une clé USB, permettrait de lancer automatiquement la reconnaissance et le lancement d'un programme applicatif stocké sur une clé USB dont le microcontrôleur ne possède qu'une mémoire flash de faible capacité. Or le contenu d'un CD-ROM (réel ou virtuel) est formaté suivant la norme ISO/IEC 9660. Ce format normalisé organise par exemple les données en blocs de 2 kilo-octets, dont une grande partie est souvent inutilisée. io Ainsi, le problème technique posé consiste à pouvoir stocker le contenu utile d'un CD-ROM virtuel dans une mémoire de faible capacité, par exemple la mémoire flash interne de faible capacité du microcontrôleur d'une clé USB. Buts de l'invention 15 Un but de l'invention est par conséquent de remédier aux problèmes posés et de proposer un procédé de compaction du contenu d'un CD-ROM permettant de le stocker dans une mémoire de faible capacité, par exemple la mémoire flash interne du microcontrôleur d'un composant de type clé USB. 20 Un autre but de l'invention est de proposer un procédé de compaction apte à ne conserver que les données � utiles � de l'image d'origine d'un CD-ROM, puis de stocker cette image compactée dans la mémoire interne du microcontrôleur. Un autre but de l'invention est de proposer un procédé de décompaction devant être capable de restituer l'image d'origine du CD-ROM virtuel lors de la 25 lecture, par un système hôte tel qu'un ordinateur portable, de la mémoire flash associée au microcontrôleur de la clé USB. Résumé de l'invention L'invention a donc pour objet un procédé de compaction et de stockage dans 30 une mémoire cible, de l'image d'un CD-ROM virtuel organisé en blocs binaires selon 4 la norme ISO/IEC 9660, certains blocs binaires contenant des données utiles et d'autres étant vides c'est-à-dire constitués uniquement de zéros, chaque bloc étant identifié par un numéro de bloc, procédé caractérisé en ce qu'il comporte des étapes consistant à, pour chaque bloc binaire : - identifier s'il s'agit d'un bloc vide ou d'un bloc non vide, et s'il s'agit d'un bloc vide, écarter ce bloc et passer au bloc suivant ; - pour chaque bloc non vide, générer un descripteur de bloc apte à identifier ledit bloc, et ranger ledit descripteur de bloc dans une table de descripteurs de blocs; io - itérer les étapes précédentes pour l'ensemble des blocs de l'image du CD-ROM ; - copier uniquement les blocs non vides et la table de descripteurs de blocs dans la mémoire cible. On a donc une compaction globale qui consiste à ne conserver que les 15 blocs non vides. Il est à noter que par compaction, on entend ici un procédé global consistant à isoler les données utiles, et à générer des descripteurs de ces données utiles. Cette compaction globale est éventuellement suivie, au niveau local d'un bloc de données utiles, par une compression locale des données utiles. 20 De cette manière, il est possible de n'inscrire dans la mémoire cible de petite taille, que des données utiles compactées, avec leurs descripteurs, en étant débarrassé de la plus grande partie de l'image binaire du CD-ROM, constituée uniquement de zéros. De façon avantageuse, les descripteurs de blocs non vides comportent 25 au moins les champs suivants : - un numéro de bloc ; un décalage à partir du début du bloc, correspondant à la position du début du champ de données utiles dans le bloc ; ce champ indique où sont copiées les données utiles dans la mémoire cible ; 30 une indication de la longueur du champ de données utiles ; une indication de localisation des données utiles, qui indique d'où viennent les données (source); De préférence, les blocs non vides sont eux-mêmes compressés au moyen d'une compaction locale qui consiste à compresser les données utiles d'un bloc. Dans ce cas, les descripteurs de blocs non vides comportent en outre une indication du type d'algorithme de compression des données utiles incluses dans les blocs non vides. En outre, dans le cas où seuls des octets nuls sont trouvés dans un bloc, aucun descripteur n'est généré pour ce bloc. io L'invention a également pour objet un procédé de décompaction de données compactées selon le procédé décrit plus haut, caractérisé en ce qu'il comporte, pour la lecture du bloc n, les étapes suivantes : lire les descripteurs de blocs dans la mémoire cible de façon à localiser les données utiles compactées ; 15 copier les données utiles dans un registre tampon, ou � buffer � de sortie ; - pour chaque bloc de données utiles copié ayant une taille inférieure à la longueur d'un bloc normalisé (2 kilo-octets), compléter ce bloc avec des zéros avant et après les données utiles pour construire un bloc complet ayant la taille normalisée, soit 2 kilo-octets dans notre exemple; 20 Dans un mode de réalisation avantageux, le procédé de décompaction comporte en outre, dans le cas où les données utiles ont été préalablement compressées, une étape de décompression des données utiles compressées, avant l'étape de recontruction d'un bloc de données utiles de taille normalisée. 25 D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description détaillée des dessins annexés dans lesquels : - la figure 1 représente un schéma simplifié de l'architecture matérielle typique qui supporte l'invention ; - la figure 2 représente l'architecture typique de l'image binaire d'un CD- 30 ROM ; - la figure 3 représente un organigramme du procédé de compaction selon l'invention ; - la figure 4 représente un organigramme du procédé de décompaction selon l'invention. Description détaillée de l'invention On se réfère à la figure 1. Dans cette figure, on a représenté l'architecture matérielle typique à laquelle le procédé selon l'invention va s'appliquer, à savoir un microcontrôleur 1 pourvu d'un processeur (non représenté) et d'une mémoire lo interne 2,3 . Le microcontrôleur 1 possède une mémoire flash interne de faible taille, par exemple de 256 kilo-octets, répartie entre une partie 2 dédiée au système d'exploitation et au code de décompaction, et une partie 3 dédiée au contenu du CD-ROM virtuel compacté. 15 Comme on le voit, lorsque les contraintes matérielles sur la taille de la mémoire sont aussi drastiques, notamment pour des raisons de coût de la mémoire, il n'est pas possible de simplement copier l'image binaire d'un CD-ROM (dont la taille maximale est de l'ordre de 700 mégaoctets) afin de récupérer les données utiles, par exemple le code de la fonctionnalité autorun, mais il faut extraire de cette image 20 binaire seulement les informations utiles et les stocker de manière à pouvoir les reconstituer aisément lorsque le dispositif qui abrite le microcontrôleur, par exemple une clé USB, est connecté à un système hôte tel qu'un ordinateur portable. Dans la figure 2, on a représenté l'architecture typique des fichiers binaires 25 stockés sur un CD-ROM. Cette architecture comporte, selon la norme ISO/IEC 9660, une partie système 21 du CD-ROM, une partie d'allocation de fichiers 22 notée FAT, pour � File Allocation Table � en terminologie anglo-saxonne, et une série de fichiers utiles tels que AUTORUN.INF, AUTORUN.ICO, ou d'autres fichiers utiles. Les données utiles sont généralement organisées en blocs de 2 kilo-octets, et une grande partie 30 du contenu de ces blocs est le plus souvent inutilisée car la taille des données est 7 inférieure à la taille des blocs. En outre, entre les différents blocs 21, 22, 23 utiles ou non vides, peuvent se trouver des blocs non utilisés 24, c'est-à-dire remplis de zéros. A titre d'exemple, on peut imaginer un contenu de CD-ROM comportant simplement un petit fichier AUTORUN.INF et un petit fichier AUTORUN.ICO qui ensemble occupent environ 46 kilo-octets (en comptant la zone système de 32 kilo-octets), alors que la taille de l'ensemble de l'image binaire du CD-ROM est de l'ordre de 700 mégaoctets, essentiellement vides. Dans l'exemple où la partie utile d'une image de CD-ROM représente 46 Ko et io contient des fichiers AUTORUN.INF et AUTORUN.ICO, l'algorithme de compaction selon l'invention permet de stocker cette image dans une mémoire de 4 Ko. Le but de l'invention est donc de proposer un procédé de compaction/décompaction qui permette de ne stocker dans la mémoire flash cible que la partie utile (à savoir dans notre exemple, un fichier AUTORUN.INF et un 15 fichier AUTORUN.ICO compactés occupant chacun par exemple moins de 1 kilo-octet), en écartant tout le reste, puis de reformer ultérieurement une image complète de l'image du CD-ROM lorsque le dispositif contenant la mémoire cible est connecté à un système hôte à des fins de lecture. 20 Dans la figure 3, on a représenté l'organigramme plus détaillé du procédé de compaction selon l'invention. Le principe du procédé de compaction consiste à assembler les parties utiles de l'image binaire du CD-ROM à compacter, et de leur ajouter une table de descripteurs de blocs, faisant le lien avec la partie compactée, de façon à pouvoir ultérieurement retrouver les données compactées, lors de la 25 decompaction. La première étape du procédé de compaction, connue et non représentée en Figure 3, consiste à construire, à l'aide d'un système hôte auquel le dispositif comportant la mémoire cible est connecté, une image binaire au format d'un CD-ROM, obtenue à partir de fichiers originaux à compacter. Ainsi, on obtient des blocs 30 logiques numérotés, chacun ayant une taille de 2 kilo-octets, dans lesquels les 8 données utiles (par exemple un fichier autorun) sont disposées. On suppose que tous les blocs disposés après le dernier bloc utile sont tous vides de données, c'est-à-dire remplis de zéros. La seconde étape, référencée 32, consiste alors, selon l'invention, à écarter les parties inutilisées de l'image binaire du CD-ROM, et à générer une table de descripteurs permettant de ne pointer que vers les parties utiles de chaque bloc non vide. Dans une étape optionnelle supplémentaire, il est prévu que des descripteurs puissent aussi être générés pour ceux des blocs qui contiennent des données utiles io répétitives, ce qui permettra d'augmenter l'efficacité de la compaction. L'image binaire compactée ainsi obtenue peut alors être mémorisée dans la mémoire cible de petite taille, par exemple dans la mémoire interne du microcontrôleur d'une clé USB. Comme représenté plus en détail dans la Figure 3, on commence en 32 par is initialiser la table des descripteurs, de façon que la liste des descripteurs soit vide. Puis on démarre en 34 le traitement successif des blocs de l'image binaire du CD-ROM obtenue dans la première étape, avec une itération 36 jusqu'au dernier bloc traité, qui déclenche la fin du processus en 38. Pour chaque bloc de 2 kilo-octets, on identifie en 40 les données utiles à 20 compacter dans le bloc, et on les copie en 44 pour stockage ultérieur dans la mémoire cible. Il s'agit typiquement des premiers octets non nuls du bloc, jusqu'à une zone du bloc à partir de laquelle tous les octets subséquents sont à zéro. De façon optionnelle, on compresse en 42 les données utiles du bloc considéré avec un algorithme de compression ad hoc, par exemple RLE, et on copie 25 en 44 les données compactées du bloc en cours, pour stockage ultérieur dans la mémoire cible. En outre, on ajoute pour chaque bloc compressé, un descripteur dans la table des descripteurs, permettant ultérieurement de retrouver les blocs compressés, pour procéder à la décompression. A la fin du traitement d'un bloc, on incrémente en 46 le numéro du prochain bloc CD-ROM à examiner. 9 De façon avantageuse, pour chaque bloc binaire, il est intéressant d'ignorer les octets nuls de début de bloc et de démarrer l'examen à partir des derniers octets du bloc, en progressant vers le début du bloc. En effet, dans l'hypothèse où les octets utiles, non nuls, sont disposés en tête de bloc, cela permet de localiser aisément le dernier octet utile dans le bloc, en sachant que des octets localisés avant celui-ci dans le bloc sont des octets de données utiles, sur lesquels doit porter l'algorithme de compression. Puis on passe au bloc suivant de données utiles du CD-ROM à compacter, et on itère en 36 ce processus jusqu'à arriver au dernier bloc compacté. A ce stade, io l'ensemble des blocs utiles de l'image binaire au format CD-ROM a été identifié comme utile, puis compacté, prêt à être copié dans sa forme compactée dans la mémoire cible. L'image cible comporte alors une en-tête indiquant le nombre de descripteurs de l'image compactée, un ensemble de descripteurs, et un ensemble de blocs 15 compactés. Il en résulte que l'on dispose alors dans la mémoire cible, d'une image compactée des seuls blocs utiles de l'image binaire au format CD-ROM, correspondant aux fichiers de départ, et des descripteurs associés. De façon avantageuse, chaque descripteur contient au moins un champ de 20 numéro de bloc, un champ de localisation des données compactées, un champ indiquant la position des données logiques à l'intérieur du bloc, un champ indiquant la longueur (par exemple en nombre d'octets) des données utiles, et un champ indiquant le type de compression du bloc. Ainsi, il est possible de caractériser suffisamment la taille et la localisation des données utiles de chaque bloc binaire de 25 l'image au format CD-ROM. Le procédé de compaction selon l'invention prévoit aussi que dans le cas où seuls des octets nuls sont trouvés dans un bloc (c'est le cas d'un bloc vide de données utiles), aucun descripteur n'est généré pour ce bloc, ce qui permet de gagner de la place en mémoire. 2947926 io Il est à noter que l'algorithme de compression en tant que tel ne fait pas partie de l'invention. L'homme du métier pourra choisir tout algorithme susceptible de convenir, en fonction notamment de l'efficacité de compaction requise. Simplement, l'algorithme utilisé sera précisé dans l'un des champs des 5 descripteurs. Dans la figure 4, on a représenté l'organigramme du procédé de décompaction. La mémoire cible qui contient l'image compactée est pour cela connectée à un dispositif hôte comportant une mémoire de taille suffisante pour io recevoir l'image après décompaction. Pour décompacter l'image d'un bloc numéro n de données utiles stockée dans la mémoire cible, on procède de la manière suivante. Après réception en 50 de la commande de lecture du bloc numéro n de la part du dispositif hôte (typiquement un ordinateur personnel), l'algorithme de décompaction parcourt en 52 la liste des 15 descripteurs, à la recherche du bloc de données numéro n, qui correspond par exemple à un numéro de bloc que le système hôte veut lire. Un test en 52 permet de vérifier si n est inférieur à 16, ce qui permet d'écarter le cas échéant du procédé de décompaction les 16 premiers blocs, qui sont typiquement des blocs système non utilisés par le système hôte. Dans le cas d'un 20 bloc système, l'opération de décompaction sera simplement remplacée en 60 par la génération d'un bloc vide de longueur standardisée (2 Ko), constitué uniquement de zéros. Pour un bloc numéro n qui n'est pas un bloc système, l'algorithme vérifie en 54 si la liste de descripteurs est vide ou non vide. 25 Si la liste de descripteurs est vide, le procédé de décompaction construit en 60 un bloc de 2 kilo-octets à zéro (puisque le dispositif hôte s'attend à lire des blocs de 2 kilo-octets car cela correspond à la norme de l'image binaire d'un CD-ROM), et le retourne au dispositif hôte. Si la liste de descripteurs est non vide, l'algorithme prend en 56 30 successivement tous les descripteurs de la liste et teste en 58 si le descripteur Il courant est le dernier descripteur traité, auquel cas un bloc constitué uniquement de zéros est retourné en 60. Si le descripteur courant n'est pas le dernier descripteur traité, l'algorithme teste en 62 si le descripteur courant concerne le bloc de données utiles numéro n que le système hôte veut lire. Si tel n'est pas le cas, l'algorithme incrémente en 66 le numéro de descripteur jusqu'à trouver un descripteur qui concerne le bloc de données utiles numéro n. Dans ce cas, il s'agit en 64 de reconstruire le contenu du bloc numéro n simplement à partir des informations du descripteur courant, afin de pouvoir io retourner en 68 le bloc complet numéro n décompacté. Pour cela, l'algorithme mettant en oeuvre le procédé interprête les octets du descripteur pour en déduire la longueur et la position des octets utiles dans le bloc. L'algorithme copie alors les données utiles dans un buffer de sortie, et complète si besoin ces données en reconstruisant un bloc de 2 kilo-octets de long, dans lesquels 15 les données décompactées sont repositionnées en fonction de l'information de décalage du descripteur, les autres octets étant complétés à zéro. Il est à noter que l'opération de décompression ou de reconstruction en 64 du contenu du bloc numéro n dépendra de l'algorithme qui a été utilisé lors de la compression du bloc numéro n. Ainsi, si la phase de compaction a fait appel à un 20 algorithme de compression locale du bloc, par exemple de type RLE, alors la phase de décompaction comprendra une étape de décompression locale du bloc avec le même algorithme que celui qui a servi à la compression locale, à savoir par exemple RLE, sachant que l'information concernant l'algorithme est disponible dans les descripteurs du bloc numéro n. 25 La décompression locale délivre les données utiles décompressées du bloc numéro n. Puis l'algorithme retourne au système hôte un bloc complet de 2 kilo-octets, après décompaction et reconstruction comme expliqué ci-dessus. Avantages du procédé selon l'invention 12 L'invention répond aux objectifs fixés. En particulier, elle permet de proposer un nouveau procédé de compaction/décompaction permettant de compresser (par exemple) les fichiers de la fonction AUTORUN d'un CD-ROM, afin de l'installer sur des produits dont le microcontrôleur a une mémoire interne de faible taille, inférieure à la taille de l'image binaire du CD-ROM. L'invention est donc particulièrement utile pour stocker la fonction dite AUTORUN dans la mémoire flash interne de petite taille d'un microcontrôleur pour des objets électroniques portables de type clé USB. Comme la taille de la mémoire peut être de ce fait limitée, il devient alors lo possible d'utiliser des clés USB très économiques pourvues de tous les avantages de la fonction AUTORUN, ce qui permet de viser de nouvelles applications pour les clés USB, dans lesquelles le coût est un facteur déterminant. REVENDICATIONS1. Procédé de compaction et de stockage dans une mémoire cible, de l'image d'un CD-ROM virtuel organisé en blocs binaires selon la norme ISO/IEC 9660, certains blocs binaires contenant des données utiles et d'autres étant vides, chaque bloc étant identifié par un numéro de bloc, procédé caractérisé en ce qu'il comporte des étapes consistant à, pour chaque bloc binaire : - identifier s'il s'agit d'un bloc vide ou d'un bloc non vide, et s'il s'agit lo d'un bloc vide, écarter ce bloc et passer au bloc suivant ; - pour chaque bloc non vide, générer un descripteur de bloc apte à identifier ledit bloc, et ranger ledit descripteur de bloc dans une table de descripteurs de blocs; - itérer les étapes précédentes pour l'ensemble des blocs de l'image du 15 CD-ROM virtuel ; - copier uniquement les blocs non vides et la table de descripteurs de blocs dans la mémoire cible. 2. Procédé de compaction selon la revendication 1, caractérisé en ce que 20 les descripteurs de blocs non vides comportent au moins les champs suivants : un numéro de bloc ; un décalage à partir du début du bloc, correspondant à la position du début du champ de données utiles dans le bloc ; une indication de la longueur du champ de données utiles; 25 - une indication de localisation des données utiles. 3. Procédé de compaction selon la revendication 1 ou la revendication 2, caractérisé en ce que les blocs non vides sont en outre compressés à l'aide d'un algorithme de compression. 4. Procédé de compaction selon la revendication 3, caractérisé en ce les descripteurs de blocs non vides comportent en outre une indication du type d'algorithme de compression des données utiles incluses dans les blocs non vides. 5. Procédé de compaction selon la revendication 1 ou la revendication 2, caractérisé en ce que dans le cas où seuls des octets nuls sont trouvés dans un bloc, aucun descripteur n'est généré pour ce bloc. 6. Procédé de décompaction de données compactées selon le procédé conforme à l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il comporte, pour décompacter l'image compactée d'un bloc numéro n, les étapes suivantes : - lire les descripteurs de blocs dans la mémoire cible de façon à localiser les données utiles; - copier les données utiles dans un buffer de sortie ; - pour chaque bloc copié ayant une taille inférieure à la longueur d'un bloc normalisé (2 kilo-octets), compléter ce bloc avec des zéros avant et après les données utiles pour construire un bloc complet ayant la taille normalisée ; - retourner au système hôte, le bloc de données utiles copié et complété à la taille normalisée. 7. Procédé de décompaction selon la revendication 6, caractérisé en ce qu'il comporte en outre, dans le cas où les données utiles ont été préalablement compressées, une étape de décompression des données utiles compressées, avant l'étape de recontruction d'un bloc de données utiles de taille normalisée.