Run-Lenght Encoding

La compresión RLE se basa en alacenar las repeticiones c0nsecutivas de los valores que componen un fichero. se usa un contador del numero de repeticiones y el valor que se repite.

Contador de repeticiones – Datos a Repetir

Se puede observar mejor en el siguiente ejemplo:

A A B B B B B C C C C D B B B E F F (18 bytes)

2 A 5 B 4 C 1 D 3 B 1 E 2 F (14 bytes)

Existes formatos que utilizan el Run-Lenght enconding como pueden ser:

  • MacPaint: Usa PackBits (Una variante de Run-Length Encoding) con rangos de valores para el indicador de repeticiones entre [-1,127]
    • Si el valor del indicador de repeticiones esta entre [0,127] indica que los siguientes (indicador de repeticiones +1) bytes son literales
    • Si el valor del indicador de repeticiones esta entre [-127,-1] indica que el siguiente byte se repite (-1*indicador de repeticiones +1 ) veces
    • Veamoslo en el siguiente ejemplo:
    • 5 5 14 14 14 14 14 8 8 8 8 7 3 2 5 5 5
    • [-1] 5 [-4] 14 [-3] 8 [2] 7 3 2 [-2] 5
  • PCX: Utiliza los dos primeros bits de mayor peso de cada byte para diferenciar entre indicadores de repeticiones y datos
    • Si ambos bits son 1 [11XXXXXXX] indica que es un indicador de repeticiones siendo XXXXXX el numero de veces que se repite el siguiente byte
    • Para el resto de los casos [00XXXXXX],[01XXXXXX] y [10XXXXXX]  son valores literales veamoslo en el siguiente ejemplo
    • 5 5 255 254 17 255 255 255 255
    • 11000011 5 11000001 255 1100001 254 17 11000100 255
    • el código 1100001 afecta a los valores 254 17
  • Targa y TIFF

6 Replies to “Run-Lenght Encoding”

  1. Hace mucho tiempo, mucho antes de los procesadores de 64 bits, me entretenía programando en ensamblador, y creé una rutina para descomprimir fragmentos de datos comprimidos con RLE:

    uRLE proc
    ; Input:
    ; esi: offset of compressed code
    ; edi: offset of uncompressed code
    ; ecx: size of compressed code
    ; eax, ebx, edx: equal to zero
    ; Output:
    ; Nothing

    decomp: lodsb
    cmp eax, ebx
    jne EndIf
    mov edx, eax
    lodsb
    dec ecx
    push eax
    mov eax, edx
    stosb
    pop edx
    push ecx
    xor ecx, ecx
    mov ecx, edx
    rep stosb
    pop ecx
    loop decomp
    ret
    EndIf: stosb
    mov ebx, eax
    loop decomp
    ret

    uRLE endp

    Saludos 🙂

  2. Un crack sería si hubiese escrito el código para comprimir y descomprimir datos con algún tipo de codificación Huffman. RLE en el fondo es demasiado simple como para considerarlo un reto 🙂

    Saludos.

  3. Huffman tienes que adaptarlo al archivo inicialmente, por eso no es un milagrito
    si fuera LZW si que te montaba un templo

  4. Pues igual un día de estos me pongo con LZW y el ensamblador y me tienes que montar un templo xDDDD

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.