Qual seria uma boa rotina de compressão (DE) para este cenário

Question

Preciso de uma rotina de descompressão rápida otimizada para um ambiente de recursos restritos, como sistemas incorporados em binários (dados hexadecimais) que possuem as seguintes características:

1. Os dados são de 8 bits (byte) (o barramento de dados tem 8 bits de largura).
2. Os valores de bytes não variam uniformemente de 0 - 0xFF, mas têm uma distribuição de Poisson (curva de sino) em cada conjunto de dados.
3. O conjunto de dados é corrigido em avançado (a ser queimado no flash) e cada conjunto raramente é> 1 - 2MB

A compressão pode levar o tempo necessário, mas a descompressão de um byte deve levar 23us no pior cenário com o mínimo de pegada de memória, como será feito em um ambiente de recursos restritos como um sistema incorporado (núcleo de 3MHz - 12MHz, 2K byte RAM) .

Qual seria uma boa rotina de descompressão?

A codificação básica do comprimento da execução parece muito desperdiçada - posso ver imediatamente que adicionar um conjunto de cabeçalho aos dados compactados para colocar para usar valores de bytes não utilizados para representar padrões repetidos de maneira fenomenal!

Com mim, que investiu apenas alguns minutos, certamente já deve existir algoritmos muito melhores de pessoas que amam essas coisas?

Gostaria de ter alguns exemplos "prontos para ir" para experimentar um PC para que eu possa comparar o desempenho em relação ao RLE básico.

Answer 1

As duas soluções que eu uso quando o desempenho são a única preocupação:

• LZO Tem uma licença GPL.
• Liblzf Tem uma licença BSD.
• Minilzo.tar.gz Isto é LZO, basta reembalar -se em uma versão 'minificada' que é mais adequada ao desenvolvimento incorporado.

Ambos são extremamente rápido ao descomprimir. Eu encontrei isso LZO criará dados compactados um pouco menores do que liblzf na maioria dos casos. Você precisará fazer seus próprios benchmarks por velocidades, mas eu os considero "essencialmente iguais". Ambos são anos-luz mais rápido do que zlib, embora nenhum deles se comprime tão bem (como seria de esperar).

LZO, em particular miniLZO, e liblzf são excelentes para alvos incorporados.

Answer 2

Se você tiver uma distribuição predefinida de valores, significa que a propenso de cada valor é fixada em todos os conjuntos de dados, poderá criar uma codificação de Huffman com códigos fixos (a árvore de código não deve ser incorporada aos dados).

Dependendo dos dados, eu tentaria Huffman com códigos fixos ou LZ77 (consulte Links of Brian).

Answer 3

Bem, os dois principais algoritmos que vêm à mente são Huffman e Lz.

O primeiro basicamente apenas cria um dicionário. Se você restringir o tamanho do dicionário suficientemente, deve ser muito rápido ... mas não espere compressão muito boa.

O último funciona adicionando referências de volta à repetição de partes do arquivo de saída. Provavelmente, isso levaria muito pouca memória para ser executada, exceto que você precisaria usar a E/S do arquivo para ler as referências de volta ou armazenar um pedaço dos dados de leitura recentemente na RAM.

Eu suspeito que o LZ é sua melhor opção, se as seções repetidas tenderem a estar próximas uma da outra. Huffman trabalha tendo um dicionário de elementos frequentemente repetidos, como você mencionou.

Answer 4

Como isso parece ser áudio, eu examinaria o PCM ou ADPCM diferencial, ou algo semelhante, o que o reduzirá para 4 bits/amostra sem muita perda de qualidade.

Com a implementação do PCM diferencial mais básica, você apenas armazena uma diferença assinada de 4 bits entre a amostra atual e um acumulador e adiciona essa diferença ao acumulador e passa para a próxima amostra. Se a diferença fora de [-8,7], você precisará prender o valor e pode levar várias amostras para o acumulador recuperar o atraso. A decodificação é muito rápida usando quase nenhuma memória, apenas adicionando cada valor ao acumulador e emitindo o acumulador como o próximo exemplo.

Uma pequena melhoria em relação ao DPCM básico para ajudar o acumulador a alcançar mais rápido quando o sinal fica mais alto e mais alto, é usar uma tabela de pesquisa para decodificar os valores de 4 bits para uma faixa não linear maior, onde ainda estão 1 separados perto de zero , mas aumente em incrementos maiores em direção aos limites. E/ou você pode reservar um dos valores para alternar um multiplicador. Decidir quando usá -lo até o codificador. Com essas melhorias, você pode obter melhor qualidade ou se safar com 3 bits por amostra em vez de 4.

Se o seu dispositivo tiver um μ-law não linear ou ADC A-Law, você poderá obter qualidade comparável a 11-12 bits com amostras de 8 bits. Ou você provavelmente pode fazer isso sozinho no seu decodificador. http://en.wikipedia.org/wiki/m-law_algorithm

Pode haver chips baratos por aí que já fazem tudo isso por você, dependendo do que você está fazendo. Eu não olhei em nenhum.

Answer 5

Você deve experimentar diferentes algoritmos de compactação com uma ferramenta de software de compactação com interruptores de linha de comando ou uma biblioteca de compactação onde você pode experimentar algoritmos diferentes. Use dados típicos para o seu aplicativo. Então você sabe qual algoritmo é mais adequado para suas necessidades.

Answer 6

Eu usei o ZLIB em sistemas incorporados para um carregador de inicialização que descomprima a imagem do aplicativo para RAM na inicialização. A licença é bem permissiva, sem bobagens GPL. Ele faz uma única chamada malloc, mas, no meu caso, eu simplesmente substituí isso por um stub que retornou um ponteiro para um bloco estático e um stub free () correspondente. Fiz isso monitorando seu uso de alocação de memória para obter o tamanho certo. Se o seu sistema puder suportar a alocação de memória dinâmica, será muito mais simples.

http://www.zlib.net/