Accueil Ti-Gen Foire Aux Questions Chat sur le chan #tigcc sur IRC
Liste des membres Rechercher Aide
Bienvenue Invité !   Se connecter             Mes sujets   
Administrer
0 membre(s) et 1 visiteur(s) actif(s) durant les 5 dernières minutes Utilisateurs actifs : Aucun membre + 1 visiteur
Avant de poster sur le forum, il y a des régles de bases à respecter pour une bonne entente et un respect de tous.
Veuillez lire la charte du forum.
  :: Index » Forum Ti68K » Programmation C » Compression huffman (13 réponse(s))
./POST DE DEPART (post n°0)   Marquer comme non lu.
LionelA Ecrit le: Mercredi 20 avril 2005 à 01:57 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


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 :p)

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.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));
  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 :)
[i]-Edité le Mardi 10 mai 2005 à 19:54 par LionelA-
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°1   Marquer comme non lu.
Onur Ecrit le: Dimanche 24 avril 2005 à 14:41 Déconnecté(e)    Voir le profil de Onur Envoyer un email à Onur Visiter le site WEB de Onur Envoyer un message privé à Onur  


je n'ai pas le courage de tout lire. J'en avais fais un Ada.

Je prendrais le tien si un jour j'en ai besoin ;) c'est cool de le donner comme ca.
Je ne veux pas faire quelque chose de bien, je cherche l'excellence:ETP Studio...


et autres projets à finir avant 2010
    
./Post n°2   Marquer comme non lu.
geogeo Ecrit le: Mardi 10 mai 2005 à 20:51 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


Juste un truc pourquoi tu utilises la compression Huffman? Perso je pense qu'en appliquant une compression LZ77 voir même LZSS ça serait plus rapide et plus petit avec un taux plus interessant.

Par exemple j'ai réalisé un compresseur LZSS copiant celui de Capcom pour un projet de traduction sur GBA et ça donne ceci pour des taux bien mieux que Huffman. (Huffman est vraiment utile à mes yeux pour des fichiers où les données sont peu redondantes (fichiers audios)).

Le code est assez crade mais vraiment facil e à optimiser en vitesse et en taille (j'essayerai un jour de l'adapter sur TI en asm). Par contre manque le décompresseur mais ce n'est vraiment pas difficile à coder.

http://tisofts.free.fr/divers/LZSS_Capcom.zip

Je sais que ça peut te vexer mon post mais franchement je pense que tu peux avoir bien plus rapide et bien mieux en te passant de Huffman, Huffman n'est pas pour moi une une méthode de compression optimale pour tes données.
Si tu veux des détails sur la méthode de compression LZSS de Capcom pas de pb. :)
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°3   Marquer comme non lu.
LionelA Ecrit le: Mardi 10 mai 2005 à 21:24 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


bah non je me vexerais pas, j'ai plein de fichiers de style 4ko max et ils se compressent a environ 50% tout le temps donc le taux me satisfait deja, en plus le decompresseur fait 600 octets (en fait un peu moins depuis que j'ai passé les fonctions en static inline)

Sinon je viens de voir un petit bug, la balise [ i ] fait tout foirer dans le code (à l'endroit ou ca part en italique y'a normalement codes[ i ].nbbit

si tu veux je le poste dans les bugs forum :)
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°4   Marquer comme non lu.
geogeo Ecrit le: Mardi 10 mai 2005 à 21:29 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


En effet faut que je recode cette balise mais pas le temps en ce moment :(
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°5   Marquer comme non lu.
limmt Ecrit le: Mardi 10 mai 2005 à 21:43 Déconnecté(e)    Voir le profil de limmt Envoyer un email à limmt Visiter le site WEB de limmt Envoyer un message privé à limmt  


faudrait que désactiver les smileysd désactive les balises aussi ;)
http://www.falco-fr.com/ - http://www.jump67.com/ - http://www.msf-league.com/
    
./Post n°6   Marquer comme non lu.
LionelA Ecrit le: Mardi 10 mai 2005 à 21:43 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


ben non parce que la balise code ne marcherait plus non plus :p
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°7   Marquer comme non lu.
limmt Ecrit le: Mardi 10 mai 2005 à 21:45 Déconnecté(e)    Voir le profil de limmt Envoyer un email à limmt Visiter le site WEB de limmt Envoyer un message privé à limmt  


ou alors désactiver les balises standard ainsi que les smileys à l'intérieur de code ;)
EDIT:ortho
-Edité le Mardi 10 mai 2005 à 21:45 par limmt-
http://www.falco-fr.com/ - http://www.jump67.com/ - http://www.msf-league.com/
    
./Post n°8   Marquer comme non lu.
LionelA Ecrit le: Mardi 10 mai 2005 à 21:50 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


ou alors pouvoir ouvrir un panneau avec des case a cocher pour choisir quelles balises/smileys on souhaite activer/desactiver (ca ca serait le top a mon avis)
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°9   Marquer comme non lu.
Lionel Debroux Ecrit le: Mercredi 11 mai 2005 à 08:34 Déconnecté(e)    Voir le profil de Lionel Debroux Envoyer un email à Lionel Debroux Visiter le site WEB de Lionel Debroux Envoyer un message privé à Lionel Debroux  

> en fait un peu moins depuis que j'ai passé les fonctions en static inline
C'est souvent le cas, quand les fonctions sont simples et en très peu d'exemplaires dans le programme.
Lionel Debroux - membre de TICT.
    
./Post n°10   Marquer comme non lu.
Sasume Ecrit le: Mercredi 11 mai 2005 à 10:21 Déconnecté(e)    Voir le profil de Sasume Envoyer un email à Sasume Visiter le site WEB de Sasume Envoyer un message privé à Sasume  

geogeo> J'aimerais bien que tu présentes la compression LZSS :)
    
./Post n°11   Marquer comme non lu.
geogeo Ecrit le: Mercredi 11 mai 2005 à 12:08 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


ici? Si LionelA veut bien!
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°12   Marquer comme non lu.
LionelA Ecrit le: Mercredi 11 mai 2005 à 16:09 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


Bien sur :)
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°13   Marquer comme non lu.
geogeo Ecrit le: Dimanche 15 mai 2005 à 11:41 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


Y a une description de LZSS sur le site dans les articles voir même dans les archives concernant mon TPE de 2 ans.
-Edité le Dimanche 15 mai 2005 à 11:42 par geogeo-
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
  :: Index » Forum Ti68K » Programmation C » Compression huffman (13 réponse(s))
Pages : 1/1     « [1] » »|

.Répondre à ce sujet
Les boutons de code
[B]old[I]talic[U]nderline[S]trikethrough[L]ine Flip Hori[Z]ontallyFlip [V]erticallySha[D]ow[G]low[S]poilerCode [G][C]ite
Bullet [L]istList Item [K] Link [H][E]mail[P]icture SmileysHelp
Couleurs :
Saisissez votre message
Activer les smileys
     

Forum de Ti-Gen v3.0 Copyright ©2004 by Geoffrey ANNEHEIM
Webmaster: Kevin KOFLER, Content Admins: list, Server Admins: Tyler CASSIDY and Kevin KOFLER, DNS Admin: squalyl
Page générée en 40.5ms avec 18 requetes