Brevet FR2878668A1 — publié le 20060602

Dans différents secteurs industriels (par exemple la fabrication de calculateurs moteur ou de téléphones portables), des données numériques sont classiquement transmises par une liaison série entre un serveur et une unité de programmation d'une mémoire non volatile sur une ligne de fabrication ou lors de phases de mise à jour (comme la reprogrammation en garage de calculateurs de véhicules automobiles). La transmission de ces données occupe une bande passante importante sur le réseau de transmission, de plus le temps de programmation de la mémoire est souvent inférieur au temps de transmission sur le réseau. Ce problème est d'autant plus présent que la taille des mémoires non volatiles et des données/programmes qui y sont mémorisées s'accroît considérablement. Des algorithmes de compression /décompression de données numériques, tels que RLE (Run Length Encoding), ZIP, Hufman or LZW (Lempel-Ziv-Welch) (marques déposées), sont largement diffusés pour l'informatique grand public. Ces algorithmes nécessitent généralement beaucoup de mémoire vive pour gérer des données dans une table de correspondance, un dictionnaire ou un arbre binaire. Lors d'un processus de programmation, on doit souvent stocker dans une quantité limitée de mémoire vive des routines de dialogue, de tests, de programmation et de compression. Ce logiciel de décompression ne doit donc pas être trop volumineux (arbre binaire) et ne doit pas nécessiter une puissance de calcul trop importante (compression arithmétique). Si de tels logiciels présentent des taux de compression intéressants, ils sont cependant peu adaptés à être exécutés sur des machines présentant des capacités de traitement réduites et n'exploitant pas des spécificités liées à une famille de processeur. Il existe donc un besoin pour un procédé de compression d'un train de données binaires, comprenant les étapes consistant à : -dans un train binaire à compresser, déterminer une séquence de référence, répétée plusieurs fois dans la suite du train binaire; -générer un train de données compressé à partir du train de données à compresser, en remplaçant chaque répétition de la séquence de référence par un vecteur définissant directement un renvoi à cette séquence de référence. Selon une variante, le procédé comprend les étapes consistant à : déterminer des séquences binaires à ne pas compresser; - générer le train de données compressé en insérant avant chaque séquence binaire à ne pas compresser un vecteur identifiant que la séquence suivante n'est pas compressée; -générer le train de données compressé en insérant un vecteur identifiant une commande suivie d'une séquence de commande au début du train binaire à compresser. Selon encore une variante, chaque vecteur présente un champs identifiant sa longueur, et au moins deux autres champs dont la combinaison de valeurs identifie le type et les valeurs de ce vecteur. Selon une autre variante, la génération du train de données compressé comprend en outre l'insertion de vecteurs de commande suivis de séquences de commande en des endroits appropriés du train binaire à compresser, les séquences de commande définissant la structure des vecteurs ultérieurs, définissant la taille respective des champs des vecteurs ultérieurs, définissant des valeurs seuil de champs des vecteurs ultérieurs, contenant des informations sur le fichier compressé ou contenant des bits de vérification de l'intégrité du fichier compressé. Selon encore une autre variante, le vecteur identifiant une séquence suivante non compressée comprend un champs définissant la taille de ladite séquence suivante. La taille du champs définissant la taille de la séquence suivante peut être définie dans une séquence de commande insérée dans le train binaire compressé. Le vecteur de renvoi peut comprendre un champs définissant la taille de la séquence de référence et un champs définissant la position de la séquence de référence. Selon une variante, la taille du champs définissant la taille de la séquence de référence et la taille du champs définissant la position de la séquence de référence sont définies automatiquement dans une séquence de commande insérée dans le train binaire compressé. Selon encore une variante, la position de la séquence de référence est définie par la distance, dans le fichier à compresser, entre la séquence de référence et la répétition remplacée par le vecteur. L'invention porte également sur un procédé de décompression d'un train binaire compressé, le train binaire compressé comprenant une séquence de référence et des vecteurs de renvoi à la séquence de référence remplaçant des répétitions de la séquence de référence, et le procédé comprenant une étape consistant à générer un train binaire décompressé en remplaçant les vecteurs de renvoi par la séquence de référence à laquelle ils renvoient. Selon une variante, la génération du train binaire comprend la génération à la volée du train binaire décompressé lors de la lecture du train binaire compressé. Selon encore une variante, la génération à la volée du train binaire décompressé est effectuée par mémorisation progressive du train binaire décompressé dans une mémoire non volatile; lors de la lecture d'un vecteur de renvoi à une séquence de référence dans le train binaire compressé, la séquence de référence est récupérée dans la partie du train binaire déjà mémorisée dans la mémoire non volatile et le train binaire est complété en recopiant la séquence de référence récupérée. Selon une autre variante: -le train binaire compressé comprend un vecteur de commande suivi d'une séquence de commande; -la génération du train binaire décompressé comprend l'exécution de la séquence 5 de commande et la suppression du vecteur de commande et de la séquence de commande dans le train binaire décompressé. Selon une variante: -le train binaire compressé comprend un vecteur identifiant une séquence binaire non compressée suivi de la séquence binaire non compressée; -la génération du train binaire décompressé comprend la suppression de ce vecteur et la recopie de la séquence binaire non compressée dans le train binaire décompressé. L'invention porte encore sur un support de stockage mémorisant un logiciel compressé selon un tel procédé de compression. L'invention porte en outre sur un support de stockage mémorisant un logiciel de compression susceptible de mettre en oeuvre un tel procédé de compression. L'invention porte par ailleurs sur un support de stockage mémorisant un logiciel de décompression susceptible de mettre en oeuvre un tel procédé de décompression. L'invention sera mieux comprise à la lecture de la description qui suit, accompagnée des dessins annexés qui représentent: -Figure 1, un algorithme simplifié d'un procédé de compression de données selon l'invention; -Figure 2, un algorithme simplifié d'un procédé de décompression de données selon l'invention; -Figure 3, une représentation d'un exemple de vecteur générique; -Figure 4, la représentation d'un exemple de vecteur de données directes; -Figure 5, la représentation d'un exemple de vecteur de recopie; -Figure 6, la représentation d'un exemple de vecteur de commande; -Figure 7, la représentation d'une portion d'un train binaire à compresser; -Figure 8, la représentation d'une portion du train binaire compressé selon une variante de l'invention. L'invention propose ainsi de compresser un train binaire de la manière suivante: on détermine dans le train binaire des séquences de référence qui présentent chacune des répétitions dans la suite du train binaire. On génère ensuite un train binaire compressé en remplaçant chaque répétition de la séquence de référence par un vecteur renvoyant à cette séquence de référence. Le remplacement d'une répétition par un vecteur de renvoi de taille sensiblement inférieure permet ainsi de compresser le train binaire. Selon une variante facilitant la décompression, d'autres types vecteurs sont utilisés: Avant de générer le train binaire compressé, on peut déterminer des séquences dont la compression par un vecteur de renvoi présente peu d'intérêt. C'est notamment le cas pour les séquences courtes ou ne présentant pas ou peu de répétitions dans les données déjà décompressées du train binaire. Lors de la génération du train binaire compressé, on insère un vecteur de données directes avant de telles séquences. Les séquences non compressées sont ainsi identifiées et les données transmises. Des vecteurs de commande peuvent également être insérés dans le train binaire compressé. Ces vecteurs de commande précèdent des commandes dont des exemples seront donnés par la suite. Les commandes sont destinées à être traitées durant la décompression. On insère notamment un vecteur de commande au début du train binaire afin de définir certains paramètres de compression ou le nom du fichier par exemple. Lors de la décompression, le train binaire décompressé est généré de la façon suivante: les séquences de commande sont exécutées, les séquences de référence sont recopiées à chaque lecture d'un vecteur de renvoi correspondant et les vecteurs sont éliminés. Le train binaire compressé renvoyant directement à des séquences de référence du train binaire en cours de décompression, la décompression n'implique pas la lecture d'une table annexe. La figure 1 illustre un exemple d'algorithme de compression pouvant être mis en oeuvre. Lors d'une étape 101, un compresseur récupère un train binaire à compresser, se présentant par exemple sous la forme d'un fichier. Lors de l'étape 102, le compresseur lit le contenu du train binaire et répertorie des séquences de référence présentant des répétitions. Le compresseur peut ainsi détecter la première occurrence de séquences binaires et détecter les répétitions ultérieures. Le compresseur mémorise l'emplacement et la taille de la séquence de référence et des répétitions. A l'étape 103, le compresseur effectue de façon connue en soi un traitement statistique à partir des informations mémorisées. Le compresseur détermine alors les séquences pour lesquelles une compression s'avère avantageuse. A l'étape 104, le compresseur génère un train binaire compressé à partir du train à compresser. Pour cela, le compresseur remplace les répétitions de séquences sélectionnées par un vecteur renvoyant directement à leur séquence de référence. Le vecteur indique notamment la taille et l'emplacement de cette séquence de référence. Le compresseur n'a donc pas à inclure dans le train compressé une table annexe définissant les renvois aux séquences de référence. Le compresseur place également des vecteurs de données directes et de commande le cas échéant. Les vecteurs de commande peuvent contenir des informations sur le fichier compressé (par exemple le CRC, le nom de fichier) des paramètres définissant la compression (par exemple des tailles de vecteurs associés à différents codes, des positions de pivots dans les vecteurs, des valeurs seuil pour des champs des vecteurs, des multiplicateurs des valeurs des champs des vecteurs, des zones à ne pas programmer...) ou des informations de commande (indication d'un début de fichier ou de sousfichier, indication de fin de fichier ou de sous-fichier, nom de fichier ou de sous-fichier, bits de vérification CRC, clé de codage...). On notera que ce procédé de compression est conservatif, c'est à dire qu'il n'y a 10 pas de perte de données entre le train binaire à compresser et le train binaire décompressé. En outre, le procédé de compression permet d'obtenir des taux de compression intéressants. Un logiciel mettant en oeuvre un tel procédé a notamment permis d'obtenir les performances de compression suivantes: Type de fichier Taille d'origine Taille après Gain en compression % Applications contrôle moteur Power PC externe avec 1048576 241749 77 zone vide Power PC externe 442587 235525 49 sans zone vide Power PC interne sans 298910 148716 50 zone vide Hitachi interne zone 524288 325214 38 vide La figure 2 illustre un exemple d'algorithme de décompression associé. L'algorithme traite le train binaire compressé en parallèle à sa réception (il n'y a potentiellement pas de stockage ou d'attente de données dans le flux binaire). Lors de l'étape 201, le décompresseur attend la réception d'un vecteur complet. Lors de l'étape 202, il décode le type de vecteur (commande, direct, copie de référence). On passe à l'étape 203 pour un vecteur de commande qui va, si nécessaire, récupérer des paramètres dans le flux de données arrivant. Ce vecteur de commande est exécuté durant l'étape 204. Après le traitement du vecteur, on repasse à l'étape 201. On passe à l'étape 213 pour un vecteur de données directe: à partir des données, on décode dans le vecteur la taille de la zone directe. Dans l'étape 214, on récupère dans le flux de données les données directes qui sont immédiatement recopiées dans la mémoire à remplir. Après le traitement du vecteur, on repasse à l'étape 201. On passe à l'étape 223 pour un vecteur de copie de référence: on décode à partir des données dans le vecteur la taille et la position de la référence. Dans l'étape 224, on copie la zone de référence en faisant une recopie des données déjà écrites dans la mémoire à remplir (processus généralement très rapide). Après traitement du vecteur, on repasse à l'étape 201. Le procédé de décompression associé peut être mis en oeuvre avec des moyens simples comprenant essentiellement des registres à décalage et des masques grâce a la structure originale des vecteurs. Le procédé de décompression associé permet également d'utiliser au minimum la mémoire vive du dispositif de décompression (le stockage d'une table en mémoire vive n'est plus indispensable). Ce procédé de décompression est particulièrement adapté aux mémoires non volatiles. En effet, les vecteurs de recopie sont utilisés pour recopier directement des données déjà mémorisées dans une séquence de référence de la mémoire non volatile. L'accès à des données de la mémoire non volatile lors de la recopie ne ralentit pas excessivement le procédé de décompression. Bien que l'on puisse considérer que le temps de compression nécessaire est relativement long, il faut noter que le procédé de décompression associé nécessite une mémoire vive réduite, est très rapide et est utilisable avec des processeurs de capacités limitées. La figure 3 illustre un exemple de vecteur utilisable pour les différents types de vecteurs inclus dans le train binaire compressé. Le vecteur présente un premier champs 31 dans lequel on identifie sa longueur. Différents modes d'identification de la longueur seront illustrés par la suite. Le second champ 32 est utilisé pour définir une dimension de séquence binaire, un emplacement de données à copier ou le type de vecteur. Le champ 33 est utilisé pour définir la taille d'une séquence à copier ou le type de vecteur. Le pivot 34 sert à définir la séparation entre le champs 32 et le champs 33. En connaissant la position du pivot, le décompresseur saura de lui-même délimiter les champs 32 et 33. La figure 4 illustre un exemple de structure d'un vecteur de données directes 4. Le champ 41 comprend une combinaison de bits 01 indiquant que le vecteur 4 occupe 16 bits. Le champ 42 définit la taille de la séquence non compressée qui suit le vecteur 4. Le champs 43 comprend une valeur nulle. La combinaison des champs 42 et 43 permet au décompresseur d'identifier le vecteur 4 comme un vecteur de données directes. En effet, le décompresseur identifiera une valeur non nulle dans le champs 42 et une valeur nulle dans le champs 43, cette combinaison désignant dans l'exemple un vecteur de données directes. La figure 5 illustre un exemple de structure d'un vecteur de recopie 5. Le champ 51 comprend une combinaison de bits 01 indiquant que le vecteur 5 occupe 16 bits. Le champ 52 définit l'emplacement des données à recopier dans le train binaire décompressé. Le champ 53 définit la taille des données à recopier à l'emplacement indiqué. La figure 6 illustre un exemple de structure d'un vecteur de commande 6. Le champ 61 comprend la valeur 00 qui définit que le vecteur 6 occupe 8 bits. Les champs 62 et 63 prennent une valeur nulle. Le décompresseur identifiera les valeurs nulles des champs 62 et 63 et déterminera que le vecteur 6 est un vecteur de commande suivi d'un type et des paramètres de la commande. Dans l'exemple, le vecteur de commande n'indique pas de taille pour la séquence de commande qui suit. On pourra alors utiliser une taille prédéterminée des séquences de commandes en fonction de leur type. La figure 7 illustre une portion de train binaire à compresser présentant successivement trois séquences Dl, une séquence D2 et une séquence Dl. Le compresseur identifie les redondances et crée un train binaire compressé dont une portion est illustrée à la figure 8. Ce train binaire comprend un premier vecteur de commande VC1, suivi de sa commande et de ses paramètres Cl. Pour la séquence de référence de la séquence Dl, le compresseur place ensuite un vecteur de données directes VD1 suivi de la séquence Dl dans le train binaire. Le compresseur place ensuite un vecteur de recopie Vr1*2 indiquant un décalage de huit bits et la recopie de 16 bits (le vecteur Vr1*2 permet ainsi la recopie des deux premières répétitions de Dl). Le compresseur place ensuite un vecteur de données directes VD2, la séquence D2, puis un vecteur de recopie Vrl*1 indiquant un décalage de 16 bits et la recopie de huit bits. L'algorithme de compression utilisé peut utiliser un certain nombre de méthodes statistiques connues pour déterminer si des répétitions doivent être compressées ou non. On peut notamment prévoir de comparer la taille d'une séquence répétée à la taille du vecteur de recopie envisagé pour déterminer si cette séquence doit être remplacée par ce vecteur de recopie. On peut ainsi noter que la taille nécessaire au champ 52 sera variable en fonction du décalage entre la séquence de référence et sa répétition. Cette taille sera par exemple fixée par une commande de positionnement de pivot décrite ultérieurement. Le codage de la taille des vecteurs peut être effectué de la manière suivante. Dans les exemples simplifiés qui suivent, on admettra que les vecteurs présentent une dimension de 8, 16, 32 ou 64 bits. Dans l'exemple des figures 4 à 6, la taille du vecteur est codée sur deux bits dans les champs 41, 51 et 61. La combinaison 00 identifie un vecteur d'une taille de 8bits, 01 un vecteur de 16 bits, 10 un vecteur de 32 bits et 11 un vecteur de 64 bits. Une seconde possibilité consiste à détecter la position du premier bit à 1 du champ 31. Ainsi, un bit à 1 en première position identifie un vecteur de 8bits, un bit à 1 en seconde position un vecteur de 16 bits, un bit à 1 en troisième position un vecteur de 32 bits et un bit à 1 en quatrième position un vecteur de 64 bits. Le champ définissant la taille du vecteur peut ainsi présenter une longueur variable en fonction de la taille du vecteur. Une troisième possibilité consiste à détecter la position du premier bit à 0 dans le champs 31. Un bit à 0 en première position identifie un vecteur de 8 bits et ainsi de suite. Pour détecter la position du premier bit à 0 ou 1, on peut utiliser des instructions assembleurs présentes sur la plupart des processeurs qui font ce type de détection. On peut prévoir que la position du pivot soit prédéfinie en fonction de la taille des vecteurs. La position du pivot peut aussi être initialisée et adaptée dynamiquement au fur et à mesure du train binaire, en fonction des conditions de compression rencontrées, avec des vecteurs de commande. Plusieurs perfectionnements permettent de coder un maximum d'informations avec 15 des vecteurs ayant des tailles aussi réduites que possible. Ainsi, on peut prévoir que le compresseur et le décompresseur associent une valeur différente à la valeur du champ 42 ou 52. La valeur associée sera par exemple la somme de la valeur du champ et d'une valeur seuil. Ainsi, si la valeur du champ 42 ou 52 est 11 et si la valeur seuil vaut 1, la valeur associée vaudra 12. En effet, la distance minimale entre la séquence de référence et sa répétition n'est jamais nulle: on ne code ainsi que des distances supérieures à 1 avec un tel vecteur de recopie 5. De façon analogue, la taille d'une séquence directe n'est jamais nulle: on ne code ainsi que des tailles de séquence supérieures à 1 avec un tel vecteur de données directes 25 4. La valeur du seuil définit ainsi respectivement la distance minimum de la séquence de référence et la taille minimum de la séquence directe. De façon similaire, on pourra associer des valeurs de seuil distinctes en fonction de la taille des vecteurs. Ci-dessous un exemple pratique: On dispose de vecteurs 4 et 5 respectivement de 8 bits et 16 bits, dont les champs 42 et 52 comportent 4 et 8 bits. Avec une valeur de seuil de 1, les valeurs associées au vecteur 4 iront de 1 à 16. Le vecteur 5 sur 16bits fournira un gain moindre que le vecteur 4 sur 8 bits pour des valeur de 1 a 16. On peut donc fixer le seuil du vecteur 5 à 17, les valeurs associées 35 au vecteur 5 iront donc de 17 à 272. REVENDICATIONS 1. Procédé de compression d'un train de données binaires, caractérisé en ce qu'il comprend les étapes consistant à : - dans un train binaire à compresser, déterminer (102) une séquence de référence, répétée plusieurs fois dans la suite du train binaire; -générer un train de données compressé (104) à partir du train de données à compresser, en remplaçant chaque répétition de la séquence de référence par un vecteur définissant directement un renvoi à cette séquence de référence. 2. Procédé de compression selon la revendication 1, caractérisé en ce que le procédé comprend les étapes consistant à : -déterminer des séquences binaires à ne pas compresser (103) ; -générer le train de données compressé en insérant avant chaque séquence binaire à ne pas compresser un vecteur (4) identifiant que la séquence suivante n'est pas compressée; -générer le train de données compressé en insérant un vecteur (6) identifiant une commande suivie d'une séquence de commande au début du train binaire à compresser. 3. Procédé de compression selon la revendication 2, caractérisé en ce que chaque vecteur présente un champs identifiant sa longueur (41, 51, 61), et au moins deux autres champs dont la combinaison de valeurs identifie le type et les valeurs de ce vecteur. 4. Procédé de compression selon la revendication 2 ou 3, caractérisé en ce que la génération du train de données compressé comprend en outre l'insertion de vecteurs de commande suivis de séquences de commande en des endroits appropriés du train binaire à compresser, les séquences de commande définissant la structure des vecteurs ultérieurs, définissant la taille respective des champs des vecteurs ultérieurs, définissant des valeurs seuil de champs des vecteurs ultérieurs, contenant des informations sur le fichier compressé ou contenant des bits de vérification de l'intégrité du fichier compressé. 5. Procédé de compression selon l'une quelconque des revendications 2 à 4, caractérisé en ce que le vecteur identifiant une séquence suivante non compressée comprend un champs (42) définissant la taille de ladite séquence suivante. 6. Procédé de compression selon les revendications 3 et 5, caractérisé en ce que la taille du champs définissant la taille de la séquence suivante est définie dans une séquence de commande insérée dans le train binaire compressé. 7. Procédé de compression selon l'une quelconque des revendications précédentes, caractérisé en ce que le vecteur de renvoi comprend un champs (53) définissant la taille de la séquence de référence et un champs (52) définissant la position de la séquence de référence. 8. Procédé de compression selon les revendications 3 et 7, caractérisé en ce que la taille du champs définissant la taille de la séquence de référence et la taille du champs définissant la position de la séquence de référence sont définies automatiquement dans une séquence de commande insérée dans le train binaire compressé. 9. Procédé de compression selon la revendication 7 ou 8, caractérisé en ce que la position de la séquence de référence est définie par la distance, dans le fichier à compresser, entre la séquence de référence et la répétition remplacée par le vecteur. 10. Procédé de décompression d'un train binaire compressé, caractérisé en ce que le train binaire compressé comprend une séquence de référence et des vecteurs de renvoi direct à la séquence de référence remplaçant des répétitions de la séquence de référence, et en ce que le procédé comprend une étape consistant à générer un train binaire décompressé en remplaçant les vecteurs de renvoi par la séquence de référence à laquelle ils renvoient. 11. Procédé de décompression selon la revendication 10, caractérisé en ce que la génération du train binaire comprend la génération à la volée du train binaire décompressé lors de la lecture du train binaire compressé. 12. Procédé de décompression selon la revendication Il, caractérisé en ce que: -la génération à la volée du train binaire décompressé est effectuée par mémorisation progressive du train binaire décompressé dans une mémoire non volatile; -lors de la lecture d'un vecteur de renvoi à une séquence de référence dans le train binaire compressé, la séquence de référence est récupérée dans la partie du train binaire déjà mémorisée dans la mémoire non volatile et le train binaire est complété en recopiant la séquence de référence récupérée. 13. Procédé de décompression selon l'une quelconque des revendications 10 à 12, caractérisé en ce que: - le train binaire compressé comprend un vecteur de commande suivi d'une séquence de commande; - la génération du train binaire décompressé comprend l'exécution de la séquence de commande et la suppression du vecteur de commande et de la séquence de commande dans le train binaire décompressé. 14. Procédé de décompression selon l'une quelconque des revendications 10 à 13, caractérisé en ce que: -le train binaire compressé comprend un vecteur (VD1) identifiant une séquence binaire non compressée suivi de la séquence binaire non compressée (Dl) ; -la génération du train binaire décompressé comprend la suppression de ce vecteur et la recopie de la séquence binaire non compressée dans le train binaire décompressé. 15. Support de stockage mémorisant un logiciel compressé selon le procédé de l'une 5 quelconque des revendications 1 à 9. 16. Support de stockage mémorisant un logiciel de compression susceptible de mettre en oeuvre le procédé selon l'une quelconque des revendications 1 à 9. 17. Support de stockage mémorisant un logiciel de décompression susceptible de mettre en oeuvre le procédé selon l'une quelconque des revendications 10 à 14.