Trabalho Prático 1

Compactação de Imagens com RLE

Programação de Baixo Nível

04/2017

1 Introdução

O objetivo deste trabalho é a implementação de um algoritmo para compactação de dados repetidos.
Uma das técnicas que podem ser usadas para compactar um vetor é a Run Length Encoded, ou Codificação pelo Comprimento da Sequência. Neste técnica, uma sequência de dados iguais em um vetor é substituída por uma instância deste dado seguida de um número que define a quantidade de vezes que este dados se repete. Por exemplo, aplicando RLE à sequência XXXXXXXXXXYYYYYYY, deve-se obter X10Y7.
No presente trabalho, a entrada do algoritmo deverá ser um vetor de caracteres, de um tamanho conhecido previamente. Como saída, o algoritmo deve gerar a compactação RLE do vetor, em um novo vetor, alocado dinamicamente. Neste vetor, a quantidade de repetições de cada dado deve ser armazenada como um unsigned char, ou seja um inteiro de 1 (um) byte. Com isto, sequências de mais de 255 caracteres deverão ser codificadas em duas ou mais partes.

2 Geração dos dados de entrada

O programa poderá usar três formas de entrada dos vetores a serem compactados:
20 10
  65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65
  66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66
  67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67
  65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65
  66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66
  67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67
  65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65
  66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66 66
  67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67
  65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65 65

P5           # indica formato PGM
311 359      # dimensões: largura x altura
255          # valor máximo armazenado (sempre 255)
[vetor com a imagem]

Para permitir a avaliação do trabalho, após a compactação, o vetor deverá ser impresso com uma função semelhante a esta:
void ImprimeVetorRLE(char *VRLE, int tamanho)
{
    unsigned char* ptr = (unsigned char*) VRLE;
    for (i=0; i< tamanho; i+=2)
    {
          printf("%d -  %d vezes\n", ptr[i], ptr[i+1]); 
     }
}

3 Avaliação

Leia com atenção os critérios de avaliação: