compression huffman - Page 1

Je copy/paste un poste que je viens de mettre sur tigen en esperant avoir aussi quelques réponses ici
merci


Voici mon implémentation de l'algorithme de compression Huffman (que je vais utiliser dans F-Zero) :
Quatres fichiers (deux .h et deux .c) pour la compression et la decompression On-Calc.
Le compresseur fait un peu moins de 2ko et le décompresseur un peu moins de 600 octets.
On ne peut pas compresser directement les fichiers car je travaille seulement avec des zones de mémoires (mais c'est possible en recuperant le pointeur avec les truc de vat.h).
Donc voilà je me demandais si quelqu'un pouvait trouver des optimisations en taille surtout pour le décompresseur ?
downloadez le projet complet : huff.zip

les sources pour ceux qui ont la flemme de downloader mais qui veulent juste voir a quoi ca ressemble (et oui c'est pas commenté et c'est illisible )

main.c

// C Source File
// Created 05/04/2005; 12:00:48


#include <tigcclib.h>
#include "compress.h"
#include "uncompress.h"

unsigned char data[] = "test";
unsigned short size = 4;

// Main Function
void _main(void)
{
	unsigned char * dataComp;
	unsigned short sizeComp;
	unsigned char * data2;
	unsigned short size2;

	dataComp = compress(data, size, &sizeComp);
	data2 = uncompress(dataComp, &size2);

	free(dataComp);
	free(data2);
}

compress.h

// Header File
// Created 16/04/2005; 21:18:10

unsigned char * compress(unsigned char * data, unsigned short size, unsigned short * sizeComp);

compress.c

// C Source File
// Created 16/04/2005; 21:18:36

#include <tigcclib.h>
#include "compress.h"

typedef struct node {
	unsigned short nbocc;
	unsigned char isleaf;
	unsigned char l_id;
	unsigned char r_id;
	struct node * l_node;
	struct node * r_node;
} node;

typedef struct leaf {
	unsigned short nbocc;
	unsigned char isleaf;
	unsigned char id;
} leaf;

typedef struct code {
	unsigned char nbbit;
	unsigned char bits[16];
} code;

CALLBACK short leaf_comp(const void *a, const void *b) {
	return ((leaf*)a)->nbocc - ((leaf*)b)->nbocc;
}

code lbit(code cod) {
	cod.bits[cod.nbbit >> 3] &= ~(0x80 >> (((cod.nbbit)++) & 0x7));
	return cod;
}

code rbit(code cod) {
	cod.bits[cod.nbbit >> 3] |= (0x80 >> (((cod.nbbit)++) & 0x7));
	return cod;
}

unsigned char * comp;
unsigned char numbit;

void wbit(unsigned char bit) {
	if(bit) *comp |= (0x80 >> numbit);
	else  *comp &= ~(0x80 >> numbit);
	if(!((++numbit) & 0x7)) {++comp;numbit=0;}
}

void wid(unsigned char id) {
	unsigned short i;
	for(i=8;i--; )
		wbit(id & 0x80), id<<=1;
}

void wcode(code cod) {
	unsigned short i;
	for(i=0; i<cod.nbbit; i++)
		wbit(cod.bits[i>>3] & 0x80>>(i&0x7));
}

void btree_read(node * tree, code * codes, code cod) {
	wbit(0);
	if(!(tree->l_node)) codes[tree->l_id] = lbit(cod), wbit(1), wid(tree->l_id);
	else btree_read(tree->l_node, codes, lbit(cod));
	if(!(tree->r_node)) codes[tree->r_id] = rbit(cod), wbit(1), wid(tree->r_id);
	else btree_read(tree->r_node, codes, rbit(cod));
}

unsigned char * compress(unsigned char * data, unsigned short size, unsigned short * sizeComp) {
	unsigned char * dataComp;
	unsigned short nbleaf;
	code codes[256];
	leaf leafs[256];
	leaf *tableaf;
	unsigned short i;

	for(i=256;i--; ) codes[i].nbbit = 0;

	for(i=256;i--; ) {
		leafs[i].nbocc = 0;
		leafs[i].id = i;
		leafs[i].isleaf = 1;
	}

	for(i=size; i--; ) leafs[data[i]].nbocc++;
		
	qsort(leafs, 256, sizeof(leaf), leaf_comp);
	for(i=256; i-- && leafs[i].nbocc; );
	tableaf = &leafs[256];
	nbleaf = 255-i;

	node * nodes;
	node ** nodesptrs;

	if(nbleaf!=1) {

		nodes = (node*)calloc((nbleaf-1), sizeof(node)) + nbleaf-1;
	
		nodesptrs = (node **)malloc(sizeof(node *) * nbleaf);
	
		for(i=nbleaf; i--; )
			*(nodesptrs++) = (node*)(--tableaf);
	
		nodesptrs -= nbleaf;
	
		for(i = nbleaf-1; i--; ) {
			(*(node*)(--nodes)).nbocc = (*(node**)(nodesptrs+i))->nbocc + (*(node**)(nodesptrs+i+1))->nbocc;
			
			if((*(node**)(nodesptrs+i))->isleaf) (*(node*)(nodes)).l_id = (*(leaf**)(nodesptrs+i))->id;
			else (*(node*)(nodes)).l_node = *(node**)(nodesptrs+i);
			if((*(node**)(nodesptrs+i+1))->isleaf) (*(node*)(nodes)).r_id = (*(leaf**)(nodesptrs+i+1))->id;
			else (*(node*)(nodes)).r_node = *(node**)(nodesptrs+i+1);
			unsigned short j;
			for(j=i;j--; ) if((*(node*)(nodes)).nbocc <= (*(node**)(nodesptrs+j))->nbocc) break;
			j++;
			
			memmove(nodesptrs+j+1,nodesptrs+j,(i-j)*sizeof(void*));
			*(node**)(nodesptrs+j) = nodes;
		}
		free(nodesptrs);

	} else {
		nodes = (node*)calloc(1, sizeof(node));
		nodes->l_id = leafs[255].id;
		nbleaf++;
		tableaf--;
	}

	unsigned short offset = ((nbleaf<<1)-1) + (nbleaf<<3) + 16;
	*sizeComp = (offset>>3) + ((offset & 0x7)?1:0);
	dataComp = (unsigned char *)malloc(sizeof(unsigned char) * (*sizeComp));
	comp = dataComp+2;
	code cod;
	cod.nbbit = 0;
	numbit = 0;
	btree_read(nodes, codes, cod);
	
	unsigned long sum = 0;
	
	for(i=nbleaf; i--; )
		sum += tableaf->nbocc * codes[tableaf->id].nbbit, tableaf++;

	*sizeComp = ((sum+offset)>>3) + (((sum+offset) & 0x7)?1:0);
	*(unsigned short*)dataComp = size;
	comp -= (long)dataComp;
	dataComp = (unsigned char *)realloc(dataComp, sizeof(unsigned char) * (*sizeComp));
	comp += (long)dataComp;
	
	for(i=0; i<size; i++) wcode(codes[data[i]]);
		
	free(nodes);
	return dataComp;
}

uncompress.h

// Header File
// Created 18/04/2005; 16:15:38

unsigned char * uncompress(unsigned char * dataComp, unsigned short * size);

uncompress.c

// C Source File
// Created 18/04/2005; 16:15:49

#include <tigcclib.h>
#include "uncompress.h"

typedef struct node {
	unsigned char l_id;
	unsigned char r_id;
	struct node * l_node;
	struct node * r_node;
} node;

unsigned char * comp;
unsigned char numbit;
node * nod;

unsigned char rbit() {
	if(!((++numbit) & 0x7)) {++comp;numbit=0;}
	return *comp & (0x80 >> numbit);
}

unsigned char rid() {
	unsigned short i;
	unsigned char id=0;
	for(i=8;i--; )
		id <<= 1, id |= (rbit()?1:0);
	return id;
}

node * mtree_read(unsigned char * id) {
	node * n = nod;
	if(rbit()) { *id = rid(); return NULL;	}
	nod++;
	n->l_node = mtree_read(&(n->l_id));
	n->r_node = mtree_read(&(n->r_id));
	return n;
}

unsigned char rcode(node * n) {
	if(!rbit()) {
		if(!(n->l_node)) return n->l_id;
		else return rcode(n->l_node);
	}
	if(!(n->r_node)) return n->r_id;
	else return rcode(n->r_node);
}

unsigned char * uncompress(unsigned char * dataComp, unsigned short * size) {
	unsigned char * data;
	node nodes[255];
	nod = nodes;
	comp = dataComp+1;
	numbit = 7;
	mtree_read(NULL);
	*size = *(unsigned short*)dataComp;
	data = (unsigned char *)malloc(sizeof(unsigned char) * (*size)); // gerer ca avec realloc etc..
	unsigned short i;
	for(i=0;i<(*size);i++)
		data[i] = rcode(nodes);
	return data;
}

Si vous voulez utiliser ce code, ben vous pouvez faire ce qui vous plait avec, c'est gratos

Je voudrais pas briser ta motivation, mais huffman a déjà été implémenté dix fois, mais à chaque fois dans un format différent.
Y'a par exemple ziplib, komp, un autre de Thibaut, etc...
Si tu veux être compatible avec ziplib, regarde mon site à complib. Mon code n'est pas du tout optimisé, c'était surtout pour être compatible avec komp et ziplib. Si mes sources t'interesse vraiment, j'ai une autre release à faire pour cause de bugs.
Et huffman n'est pas très performant. Si tu veux un bon algo de compression, rapide et efficace, regarde à lzfo, il y a un thread sur TICT.

LZFO est efficace mais plutôt lent, et il me semble que le code est plus gros. En revanche, elle marche dans les deux sens on-calc.
Si c'est à sens unique (décompression seulement), la compression ttpackest à peu près aussi efficace en taux de compression que la LZFO, mais extrêmement rapide (du moins, dans la version optimisée vitesse, qui fait moins de 600 octets). La version optimisée taille est maintenant par défaut dans TIGCC. C'est un retour de deux ans en arrière en termes de vitesse, par rapport à la routine de SuperStart 1.20, mais elle est presque quatre fois plus petite...

Oui je suis au courant par Kevin pour les truc existants plus efficaces en termes de compression et tout mais à la base je dois compresser des fichiers de 4ko max (donc si ca compresse 20% au lieu de 30% c'est kifkif) et je voulais faire un truc par moi même parce que j'ai quasiment tout fait sur mon projet (fonctions d'affichage des sprites, concatenation des fichiers, ...) et donc je voulais aussi m'amuser à faire la compression.

FMI, que veux-tu compresser ET décompresser on-calc (si c'est ça que tu veux faire) ?

Oui c'est bien ca, je veux integrer le compresseur a mon editeur de map et le decompresseur au moteur de mode7 pour charger ces dernières.

les map font au max 4098 octets : 1 char dimX, 1 char dimY, suivi des données sachant que les dimension X et Y sont limitées à 64 tiles et que 1 tile est codé par 1 char (qui d'ailleurs est compris entre 0 et moins que 128)

OK. S'il y a beaucoup de maps, ça se justifie, mais il faudrait en effet optimiser les routines de compression - décompression...
Deux classiques d'optimisation:
* déclarer inline les routines utilisées une fois seulement.
* passer à des pointeurs auxiliaires au lieu de redemander les index à chaque fois:
for(i=0; i<size; i++) wcode(codes[data[ i]]); ->
ptr = &data[ 0];
for (i=size; (i--); ) {
wcode(codes[ptr]);
ptr++;
}

(warning, non testé).
Pour les écritures, on gagnerait de la place et du temps en passant à des bits - si GCC ne le fait pas de lui-même.

Un Huffman est en effet un bon compromis ici, car une compression RLE ne ferait pas grand chose sur ce type de données, et une LZx est plus lourde.

[EDIT: Ximoon m'a averti que yAronet interprétait le code posté et le post ne ressemblait plus à rien]

lionelA
: Oui je suis au courant par Kevin pour les truc existants plus efficaces en termes de compression et tout mais à la base je dois compresser des fichiers de 4ko max (donc si ca compresse 20% au lieu de 30% c'est kifkif)

je te conseillerais de quand meme essayer lzfo, au moins pour voir. Ce serait bete de te passer d'un bon compresseur.
<troll>sinon utilise ziplib, 90% des users l'ont sur leur Ti. Comment ca tu peux pas ? ton prog n'est pas un prog kernel ? :-D </troll>

cross avec lionel : je ne connais pas comment se comportent les compresseurs en fonctions des donnees, c'est pour cela que je disais qu'il fallait tester. Mais si Lionel dit que c'est pas approprie...

C'est quoi le topic qui parle de LZFO sur tict ?

c'est ici

merci

ouais j'ai fais un test avec une map du genre le plus general possible et la compression huffman me la passe de 3729 octets à 2161 octets, c'est tout a fait honnete je trouve, sachant que certaines map auront beaucoup plus de tiles redondants et donc se compresseront mieux (exemple le fond de carte de whiteland : 1031 octets -> 412 octets pour une taille de 32x32 tiles (je ne compresse pas le type "MAP" et le tag OTH_TAG qui font que le fichier fait 1031 au lieu de 1026))

Sinon Ok pour les optimisations avec pointeurs je vais corriger ca mais je ne comprends pas la phrase qui dit que pour les ecritures il faut passer a des bits ?
Merci

Sinon pour ziplib, ouais je suis en nostub et puis ziplib fait 4.5ko et des choses qui ne me serviront pas

Quand tu passes à des pointeurs auxiliaires, vérifie quand même bien ce que GCC 4.0 fait...
Les écritures de bits, c'est poke(IO)_bset/bclr - ce que Samuel Stearley a fait (en ASM pur évidemment) pour exploser la vitesse des routines de décompression PPG.

Ah je ne savais pas ça !
Super, ce Samuel ! Merci.

Oui, il est très fort en optimisation ASM.