Rule Length Encoded

Algorithme utilisé par Up ! System

L'algorithme Rule Length Encoded (RLE) a pour principe de grouper les octets consécutifs identiques :

Suite d'octets similaires.
Un préfixe indique que la suite d'octets est compressée.
Un compteur indique le nombre d'occurrences d'octets identiques.
Le modèle est à répéter est écrit dans le flux.
Suite d'octets non similaires.
Un préfixe indique que la suite d'octets est non compressée.
Un compteur indique le nombre d'octets différents.
Les octets non compressés sont écrits dans le flux.

Cet algorithme n'est pas une norme : rien ne définit quels sont les préfixes, quelles sont les limites des compteurs, à partir de combien de répétitions il est obligatoire de compresser, etc.

Ce paramétrage varie en fonction de l'application utilisant l'algorithme. Voici deux exemples :

Compression pour les images au format Bitmap de Microsoft.
- Suite d'octets similaires.
  Le préfixe est le nombre d'occurrences identiques.
  Le compteur est l'octet suivant. Il est non signé.
  Le modèle est l'octet suivant.
- Suite d'octets non similaires.
  Le préfixe est l'octet 0x00.
  Le compteur est l'octet suivant. Il est non signé.
Compression pour les flux File Transfer Protocol du World Wide Web Consortium.
- Suite d'octets similaires.
  Le préfixe est le premier bit à 1 de l'octet i.e. en appliquant le masque 0x80.
  Si le bit 0x40 a pour valeur 1 alors :
  - Le compteur est le résidu de l'octet en appliquant le masque 0x3F.
  - Le modèle est :
    - L'octet 0x00 si le flux est en mode binaire.
    - L'octet 0x20 si le flux est en mode texte Ascii.
    - L'octet 0x40 si le flux est en mode texte Ebcdic.
  Sinon :
  - Le compteur est le résidu de l'octet en appliquant le masque 0x3F.
  - Le modèle est l'octet suivant.
- Suite d'octets non similaires.
  Le préfixe est le premier bit à 0 de l'octet i.e. en appliquant le masque 0x00.
  Le compteur est le résidu de l'octet en appliquant le masque 0x7F.

Voici la convention retenue par défaut par Up ! System dès lors que l'algorithme Rle n'est pas encapsulé dans une norme telle l'une des deux précédentes :

Suite d'octets similaires.
Le préfixe est le premier bit à 1 de l'octet i.e. en appliquant le masque 0x80.
Si le bit 0x40 a pour valeur 1 alors :
- Le compteur est le résidu de l'octet en appliquant le masque 0x3F.
- Le modèle est l'octet 0x00.
Sinon :
- Le compteur est le résidu de l'octet en appliquant le masque 0x3F.
- Le modèle est l'octet suivant.
Suite d'octets non similaires.
Le préfixe est le premier bit à 0 de l'octet i.e. en appliquant le masque 0x00.
Le compteur est le résidu de l'octet en appliquant le masque 0x7F.

De plus la compression n'a lieu que si elle est efficace i.e. dès lors qu'il y a au moins quatre octets consécutifs identiques.

Exemple d'un flux compressé par l'algorithme Rle

Flux non compressé

/* ------------------------------------------------------------------- */ /* Fichier : clientftp.upl */ /* Objet : Exemple d'emploi d'Up ! Network. */ /* */ /* Module : Up ! Application System. */ /* Auteur-Date : DUVAL Jean-Pierre - Novembre 2003. */ /* ------------------------------------------------------------------- */ /* Observations */ /* */ /* */ /* ------------------------------------------------------------------- */ Source Composant "Exemple d'emploi d'Up ! Network" Version 4.0.0; ImporterModule UpsFts(, ImporterDefinitions); Variable /******/ MonServeur : Nul Ou ServeurFtp; Principal /*******/ Debut MonServeur=ServeurFtp("ftp://local:21"); MonServeur.ChangerConnexion("anonymous", "contact@mon-domaine.com"); MonServeur.ChangerEtatTypeDonnees(TypeDonneesAscii); CopierFichier("C:/tmp2/essai.txt", "ftp://local:21/tmp/essai.txt"); MonServeur.ChangerEtatTypeDonnees(TypeDonneesImage); CopierFichier("ftp://local:21/tmp/essai.doc", "C:/tmp2/essai.doc"); MonServeur=Nul; Fin Principal

Flux compressé

00000000 032f 2a20 bf2d 842d 0e20 2a2f 0a2f 2a20 ./* ?-.-. */./* 00000010 4669 6368 6965 7284 200f 3a20 636c 6965 Fichier. .: clie 00000020 6e74 6674 702e 7570 6caa 200b 2a2f 0a2f ntftp.upl* .*/./ 00000030 2a20 4f62 6a65 7486 2022 3a20 4578 656d * Objet. ": Exem 00000040 706c 6520 6427 656d 706c 6f69 2064 2755 ple d'emploi d'U 00000050 7020 2120 4e65 7477 6f72 6b2e 9720 052a p ! Network.. .* 00000060 2f0a 2f2a bf20 8620 0c2a 2f0a 2f2a 204d /./*? . .*/./* M 00000070 6f64 756c 6586 201a 3a20 5570 2021 2041 odule. .: Up ! A 00000080 7070 6c69 6361 7469 6f6e 2053 7973 7465 pplication Syste 00000090 6d2e 9d20 362a 2f0a 2f2a 2041 7574 6575 m.. 6*/./* Auteu 000000a0 722d 4461 7465 203a 2044 5556 414c 204a r-Date : DUVAL J 000000b0 6561 6e2d 5069 6572 7265 202d 204e 6f76 ean-Pierre - Nov 000000c0 656d 6272 6520 3230 3033 2e94 2006 2a2f embre 2003.. .*/ 000000d0 0a2f 2a20 bf2d 842d 0620 2a2f 0a2f 2a9a ./* ?-.-. */./*. 000000e0 200c 4f62 7365 7276 6174 696f 6e73 9f20 .Observations. 000000f0 052a 2f0a 2f2a bf20 8620 062a 2f20 0a2f .*/./*? . .*/ ./ 00000100 2abf 2086 2007 2a2f 200a 2f2a 20bf 2d84 *? . .*/ ./* ?-. 00000110 2d7f 202a 2f0a 0a53 6f75 7263 6520 436f -. */..Source Co 00000120 6d70 6f73 616e 7420 2245 7865 6d70 6c65 mposant "Exemple 00000130 2064 2765 6d70 6c6f 6920 6427 5570 2021 d'emploi d'Up ! 00000140 204e 6574 776f 726b 2220 5665 7273 696f Network" Versio 00000150 6e20 312e 322e 303b 0a0a 496d 706f 7274 n 4.0.0;..Import 00000160 6572 4d6f 6475 6c65 200a 2020 2055 7073 erModule . Ups 00000170 4674 7028 3c55 7073 4674 703e 2c20 496d Ftp(, Im 00000180 706f 7274 6572 4465 6669 6e69 7469 6f6e porterDefinition 00000190 730e 293b 0a0a 5661 7269 6162 6c65 0a2f s.);..Variable./ 000001a0 862a 312f 0a20 2020 4d6f 6e53 6572 7665 .*1/. MonServe 000001b0 7572 203a 204e 756c 204f 7520 5365 7276 ur : Nul Ou Serv 000001c0 6575 7246 7470 3b0a 0a50 7269 6e63 6970 eurFtp;..Princip 000001d0 616c 0a2f 872a 7f2f 0a44 6562 7574 0a4d al./.*./.Debut.M 000001e0 6f6e 5365 7276 6575 723d 5365 7276 6575 onServeur=Serveu 000001f0 7246 7470 2822 5570 7346 7470 3a2f 2f6c rFtp("ftp://l 00000200 6f63 616c 3a32 3122 293b 0a0a 4d6f 6e53 ocal:21");..MonS 00000210 6572 7665 7572 2e43 6861 6e67 6572 436f erveur.ChangerCo 00000220 6e6e 6578 696f 6e28 2261 6e6f 6e79 6d6f nnexion("anonymo 00000230 7573 222c 2022 636f 6e74 6163 7440 7570 us", "contact@up 00000240 2d63 6f6d 702e 636f 6d22 293b 0a4d 6f6e -comp.com");.Mon 00000250 5365 7276 6575 7f72 2e43 6861 6e67 6572 Serveu.r.Changer 00000260 4574 6174 5479 7065 446f 6e6e 6565 7328 EtatTypeDonnees( 00000270 5479 7065 446f 6e6e 6565 7341 7363 6969 TypeDonneesAscii 00000280 293b 0a43 6f70 6965 7246 6963 6869 6572 );.CopierFichier 00000290 2822 433a 2f74 6d70 322f 6573 7361 692e ("C:/tmp2/essai. 000002a0 7478 7422 2c20 2255 7073 4674 703a 2f2f txt", "ftp:// 000002b0 6c6f 6361 6c3a 3231 2f74 6d70 2f65 7373 local:21/tmp/ess 000002c0 6169 2e74 7874 2229 3b0a 4d6f 6e53 6572 ai.txt");.MonSer 000002d0 7665 7572 2e43 7f68 616e 6765 7245 7461 veur.C.hangerEta 000002e0 7454 7970 6544 6f6e 6e65 6573 2854 7970 tTypeDonnees(Typ 000002f0 6544 6f6e 6e65 6573 496d 6167 6529 3b0a eDonneesImage);. 00000300 436f 7069 6572 4669 6368 6965 7228 2255 CopierFichier("U 00000310 7073 4674 703a 2f2f 6c6f 6361 6c3a 3231 psFtp://local:21 00000320 2f74 6d70 2f65 7373 6169 2e64 6f63 222c /tmp/essai.doc", 00000330 2022 433a 2f74 6d70 322f 6573 7361 692e "C:/tmp2/essai. 00000340 646f 6322 293b 0a4d 6f6e 5365 7276 6575 doc");.MonServeu 00000350 723d 4e75 6c3b 100a 4669 6e20 5072 696e r=Nul;..Fin Prin 00000360 6369 7061 6c0a 0a cipal..