Quel serait un bon (de) la routine de compression pour ce scénario

Question

J'ai besoin d'une routine de décompression FAST optimisée pour l'environnement des ressources restreintes comme les systèmes embarqués sur des données binaires (hexagonales) qui a des caractéristiques suivantes:

1. Les données sont orienté (bus de données est de 8 bits de large) de 8 bits (octet).
2. les valeurs d'octets ne varie pas uniformément de 0 - 0xFF, mais ont une distribution de Poisson (courbe en cloche) dans chaque jeu de données
.
3. Dataset est fixé à l'avance (à brûler dans Flash) et chaque jeu est rarement> 1 - 2MB

La compression peut prendre autant que le temps nécessaire, mais la décompression d'un octet doit prendre 23uS dans le pire scénario avec une empreinte mémoire minimale que ce sera fait dans un environnement de ressources limitées comme un système embarqué (3Mhz - noyau 12Mhz, 2k RAM octet).

Quelle serait une bonne routine de décompression?

Le codage de base de longueur Run semble trop de gaspillage - je peux voir tout de suite que l'ajout d'un setion d'en-tête aux données compressées pour mettre à utiliser des valeurs d'octets non utilisés pour représenter des motifs répétés souvent donnerait des performances phénoménales

Avec moi qui n'a investi que quelques minutes, sûrement il doit déjà exister des algorithmes beaucoup mieux des gens qui aiment ce genre de choses?

Je voudrais avoir un « prêt à aller » exemples pour essayer sur un PC pour que je puisse comparer les performances vis-à-vis d'un RLE de base.

Answer 1

Les deux solutions que j'utilise lorsque la performance est la seule préoccupation:

• LZO a une licence GPL.
• liblzf a une licence BSD.
• miniLZO.tar.gz Ceci est LZO, juste remballé pour une version « minified » qui est mieux adapté au développement intégré.

Les deux sont très rapide lors de la décompression. J'ai trouvé que LZO va créer des données compressées légèrement plus petites que liblzf dans la plupart des cas. Vous aurez besoin de faire vos propres repères pour des vitesses, mais je les considère être « sensiblement égale ». Les deux sont des années-lumière plus vite que zlib, bien que ni comprime aussi bien (comme on peut s'y attendre).

LZO, en particulier miniLZO et liblzf sont excellents pour cibles embarquées.

Answer 2

Si vous avez une distribution prédéfinie de valeurs qui signifie la propability de chaque valeur est fixée sur tous les ensembles de données, vous pouvez créer un codage de Huffman avec des codes fixes (l'arbre de code n'a pas à être intégré dans les données).

Selon les données, je vais essayer huffman avec des codes fixes ou LZ77 (voir les liens de Brian).

Answer 3

Eh bien, les deux algorithmes qui viennent à l'esprit sont les principaux Huffman et LZ .

Le premier crée fondamentalement juste un dictionnaire. Si vous limitez la taille du dictionnaire suffisamment, il devrait être assez rapide ... mais ne vous attendez pas très bonne compression.

Ce dernier travaille en rajoutant des références à répéter des portions de fichier de sortie. Ce serait probablement prendre très peu de mémoire pour exécuter, sauf que vous devrez soit utiliser le fichier i / o pour lire les références arrière ou stocker un morceau des données récemment lu dans la RAM.

Je soupçonne LZ est votre meilleure option, si les sections répétées ont tendance à se rapprocher les uns des autres. Huffman fonctionne en ayant un dictionnaire d'éléments souvent répétés, comme vous l'avez mentionné.

Answer 4

Comme cela semble être audio, je regarde soit PCM ou ADPCM différentiel, ou quelque chose de similaire, ce qui réduira à 4 bits / échantillon sans beaucoup de perte de qualité.

Avec le différentiel le plus élémentaire mise en œuvre du PCM, vous stockez juste une différence de 4 bits signé entre l'échantillon courant et un accumulateur, et d'ajouter cette différence à l'accumulateur et de passer à l'échantillon suivant. Si la différence en dehors de [-8,7], vous devez serrer la valeur et il peut prendre plusieurs échantillons pour l'accumulateur pour rattraper son retard. Décodage est très rapide en utilisant presque pas de mémoire, juste en ajoutant chaque valeur à l'accumulateur et à sortir l'accumulateur que l'échantillon suivant.

Une petite amélioration par rapport à DPCM de base pour aider l'accumulateur rattraper plus rapidement lorsque le signal devient plus fort et plus aigu est d'utiliser une table de consultation pour décoder les 4 valeurs de bits à une plage non-linéaire plus grande, où ils sont encore 1 à part près de zéro, mais augmenter à des incréments plus larges vers les limites. Et / ou vous pouvez réserver une des valeurs pour activer un multiplicateur. Décider quand l'utiliser jusqu'à l'encodeur. Grâce à ces améliorations, vous pouvez obtenir une meilleure qualité ou sortir avec 3 bits par échantillon au lieu de 4.

Si votre appareil a un μ-loi ou un règlement ADC non-linéaire, vous pouvez obtenir une qualité comparable à 11-12 bits avec 8 échantillons de bits. Ou vous pouvez probablement le faire vous-même dans votre décodeur. http://en.wikipedia.org/wiki/M-law_algorithm

Il pourrait y avoir des puces bon marché là-bas qui font déjà tout cela pour vous, en fonction de ce que vous faites. Je ne l'ai pas regardé en tout.

Answer 5

Vous devriez essayer différents algorithmes de compression soit avec un outil logiciel de compression avec la ligne de commande passe ou une bibliothèque de compression où vous pouvez essayer différents algorithmes. Utiliser des données typiques pour votre application. Ensuite, vous savez quel algorithme est le mieux adapté à vos besoins.

Answer 6

Je l'ai utilisé zlib dans les systèmes embarqués pour un bootloader qui décompresse l'image d'application à la RAM au démarrage. La licence est bien permissive, pas de bêtises GPL. Cela fait un seul appel malloc, mais dans mon cas, je simplement remplacé cela avec un talon qui a renvoyé un pointeur vers un bloc statique, et un talon libre () correspondant. Je l'ai fait en surveillant son utilisation d'allocation de mémoire pour obtenir la bonne taille. Si votre système peut prendre en charge l'allocation dynamique de la mémoire, il est beaucoup plus simple.

http://www.zlib.net/