#include #include #include "arith.h" #include "ppm.h" /**************************************************************************** * Gestion des noeuds ****************************************************************************/ /* * Désallocation du noeud p */ void ppm_worker::Node_Free(UINT p) { node_heap[node_free_last].free_next=p; node_heap[p].free_next=NIL; node_free_last=p; node_free_nb++; } /* * Allocation d'un noeud * s'il ne reste plus de place, on désalloue le contexte le moins utilisé. */ UINT ppm_worker::Node_Alloc(void) { UINT p; if (node_free_nb<=2) Context_DeleteLast(); p=node_free_first; node_free_first=node_heap[node_free_first].free_next; node_free_nb--; #ifdef DEBUG printf("Node_Alloc: p=%d\n",p); #endif return p; } /**************************************************************************** * Gestion des contextes ****************************************************************************/ /* * Mise au début de la liste des contextes du contexte c */ void ppm_worker::Context_MoveFirst(UINT c) { NODE *ctx; if (c!=ctx_first) { ctx=&node_heap[c]; /* suppression du contexte dans la liste */ if (c==ctx_last) { ctx_last=ctx->hdr.ctx_prev; } else { node_heap[ctx->hdr.ctx_prev].hdr.ctx_next=ctx->hdr.ctx_next; node_heap[ctx->hdr.ctx_next].hdr.ctx_prev=ctx->hdr.ctx_prev; } /* insertion au début de la liste */ node_heap[ctx_first].hdr.ctx_prev=c; ctx->hdr.ctx_next=ctx_first; ctx_first=c; } } /* * Destruction du contexte le moins utilisé (ctx_last) */ void ppm_worker::Context_DeleteLast(void) { NODE *n; UINT h,h_next,node,node_next; USHORT *p; n=&node_heap[ctx_last]; /* libération dans la table de hachage. Comme on ne dispose pas de * pointeur hash_prev dans les contextes, il faut parcourir toute * la liste. Heureusement, celle-ci est de longueur faible en moyenne */ h_next=n->hdr.hash_next; h=h_next; while (hhdr.sf_max>=2) { node=n->hdr.sf.l.sf_next; while (1) { node_next=node_heap[node].sf.sf_next; Node_Free(node); if (node_next==NIL) break; node=node_next; } } node=ctx_last; ctx_last=n->hdr.ctx_prev; Node_Free(node); ctx_nb--; } /* * Création d'un nouveau contexte avec un seul symbole sym de fréquence 1 * Utilisation implicite de sym_context et sym_hash. * Libération de mémoire si nécessaire, et mise en premier dans la liste */ void ppm_worker::Context_New(int sym,int order) { NODE *ctx; UINT i,c; #ifdef DEBUG printf("Context_New: sym=%d o=%d\n",sym,order); #endif c=Node_Alloc(); ctx=&node_heap[c]; /* mise du contexte en tête de la liste */ ctx->hdr.ctx_next=ctx_first; node_heap[ctx_first].hdr.ctx_prev=c; ctx_first=c; ctx_nb++; /* insertion dans la table de hachage */ ctx->hdr.hash_next=hash_table[sym_hash[order]]; hash_table[sym_hash[order]]=ctx_first; /* initialisation du contexte */ ctx->hdr.order=order; for(i=0;ihdr.sym[i]=sym_context[i+1]; ctx->hdr.sf_max=0; ctx->hdr.sf.sf[0].sym=sym; ctx->hdr.sf.sf[0].freq=1; #ifdef DEBUG Context_Print(ctx_first); #endif } /* * Ajout d'un nouveau symbole au contexte c */ void ppm_worker::Context_NewSym(int sym,UINT c) { NODE *n,*m; UINT p,sf_max; #ifdef DEBUG printf("Context_NewSym: sym=%d c=%d\n",sym,c); Context_Print(c); #endif n=&node_heap[c]; sf_max=n->hdr.sf_max; n->hdr.sf_max++; if (sf_max==0) { n->hdr.sf.sf[1].sym=sym; n->hdr.sf.sf[1].freq=1; } else if (sf_max==1) { p=Node_Alloc(); m=&node_heap[p]; m->sf.sf[0]=n->hdr.sf.sf[0]; m->sf.sf[1]=n->hdr.sf.sf[1]; m->sf.sf[2].sym=sym; m->sf.sf[2].freq=1; m->sf.sf_next=NIL; n->hdr.sf.l.sf_next=p; n->hdr.sf.l.freq_tot=((UINT)m->sf.sf[0].freq+(UINT)m->sf.sf[1].freq+1); } else { n->hdr.sf.l.freq_tot++; m=&node_heap[n->hdr.sf.l.sf_next]; while (sf_max>=NODE_SFNB) { sf_max-=NODE_SFNB; m=&node_heap[m->sf.sf_next]; } sf_max++; if (sf_max==NODE_SFNB) { p=Node_Alloc(); m->sf.sf_next=p; m=&node_heap[p]; m->sf.sf_next=NIL; sf_max=0; } m->sf.sf[sf_max].sym=sym; m->sf.sf[sf_max].freq=1; } #ifdef DEBUG Context_Print(c); #endif } #ifdef STAT int hash_nb=1; int hash_cnt=0; #endif /* * Recherche d'un contexte, utilisation de façon implicite de sym_context * et de sym_hash. * C'est une procédure très critique qui doit être particulièrement optimisée */ UINT ppm_worker::Context_Search(int order) { UCHAR *sym; UINT i,p; NODE *n; #ifdef DEBUG printf("Context_Search: o=%d\n",order); #endif p=hash_table[sym_hash[order]]; sym=&sym_context[1]; #ifdef STAT hash_nb++; #endif while (phdr.order==order) { if (order==0) return p; i=0; while (sym[i]==n->hdr.sym[i]) { i++; if (i==order) return p; } } p=n->hdr.hash_next; } return HASH_ADDRESS; } /* * Cette macro est HORRIBLE mais permet de simplifier beaucoup le parcours * des listes de couples symbole,fréquence tout en ayant un code rapide. * Une alternative élégante mais lente aurait été de passer une fonction * en paramètre contenant le code à exécuter */ #define SF_Read(n,p,code_to_execute) \ {\ UINT nb,i;\ nb=(UINT)n->hdr.sf_max+1;\ if (nb<=HDR_SFNB) {\ p=&n->hdr.sf.sf[0];\ } else {\ p=&node_heap[n->hdr.sf.l.sf_next].sf.sf[0];\ while (nb>NODE_SFNB) {\ for(i=0;ihdr.sf_max>=HDR_SFNB) { a=n->hdr.sf.l.sf_next; do { b=node_heap[a].sf.sf_next; Node_Free(a); a=b; } while (a!=NIL); } /* reconstruction de la liste des "sf_nb" symboles d'apres le tableau * "tab_sf" */ n->hdr.sf_max=sf_nb-1; if (sf_nb<=HDR_SFNB) { for(i=0;ihdr.sf.sf[i]=tab_sf[i]; } else { a=Node_Alloc(); n->hdr.sf.l.sf_next=a; n->hdr.sf.l.freq_tot=freq_tot; m=&node_heap[a]; i=0; c=0; while (1) { m->sf.sf[c]=tab_sf[i]; i++; if (i==sf_nb) break; c++; if (c==NODE_SFNB) { c=0; a=Node_Alloc(); m->sf.sf_next=a; m=&node_heap[a]; } } m->sf.sf_next=NIL; } #ifdef DEBUG Context_Print(ctx); #endif } /* * Mise à jour des index dans la table de hachage et des caractères du * contexte courant. * La fonction de hachage a été choisie de façon empirique en controlant * qu'elle donne en moyenne de bons résultats. */ void ppm_worker::Hash_Update(int sym) { UINT i,k; for(i=ORDER_MAX;i>=2;i--) sym_context[i]=sym_context[i-1]; sym_context[1]=sym; for(i=ORDER_MAX;i>=2;i--) { k=sym_hash[i-1]; sym_hash[i]=( (k<<6)-k+sym ) & (HASH_SIZE-1); } sym_hash[1]=sym+1; } /**************************************************************************** * Système d'exclusion des symboles ****************************************************************************/ /* * Remise à zéro du tableau d'exclusion des symboles */ void ppm_worker::Sym_ExcludeReset(void) { UINT i; sym_excl_code++; if (sym_excl_code==0) { for(i=0;i=freq_tot) { /* cas d'un symbole spécial */ arith.Arith_Decode(f,f+1,freq_tot+SYM_SPECIAL_NB); return SYM_NB+f-freq_tot; } else { i=0; freq_cum=0; while (1) { if (sym_excl[i]!=code) { freq_cum++; if (freq_cum>f) break; } i++; } arith.Arith_Decode(freq_cum-1,freq_cum,freq_tot+SYM_SPECIAL_NB); return i; } } /* * Décodage: cf Decode_NoExclude */ int ppm_worker::Decode_NoExclude(UINT ctx) { NODE *n; UCHAR code; UINT i,f,freq_tot,freq_cum,freq_sym,sf_nb; SYMFREQ *p,s; n=&node_heap[ctx]; code=sym_excl_code; /* Calcul de la somme des fréquences des caractères */ if (n->hdr.sf_maxhdr.sf_max;i++) freq_tot+=n->hdr.sf.sf[i].freq; } else { freq_tot=n->hdr.sf.l.freq_tot; } /* décodage */ sf_nb=(UINT) n->hdr.sf_max+1; f=arith.Arith_DecodeVal(freq_tot+sf_nb); if (f>=freq_tot) { /* gestion du code ESCAPE */ /* marquage des caractères utilisés */ SF_Read(n,p, { sym_excl[p->sym]=code; }); /* décodage ESCAPE */ arith.Arith_Decode(freq_tot,freq_tot+sf_nb,freq_tot+sf_nb); return SYM_ESCAPE; } /* recherche du caractère en calculant la fréquence */ freq_cum=0; SF_Read(n,p, { s=*p; freq_cum+=s.freq; if (freq_cum>f) goto decode_sym; } ); decode_sym: freq_sym=s.freq; p->freq=freq_sym+1; if (n->hdr.sf_max>=HDR_SFNB) n->hdr.sf.l.freq_tot=freq_tot+1; arith.Arith_Decode(freq_cum-freq_sym,freq_cum,freq_tot+sf_nb); /* test de la renormalisation */ if (freq_sym==(RENORM_FREQSYM-1) || freq_tot>=RENORM_FREQTOT) { Context_Renorm(ctx); } return s.sym; } /* * Décodage: cf Encode_Exclude */ int ppm_worker::Decode_Exclude(UINT ctx) { UINT sf_nb,freq_sym,freq_cum,freq_tot,f; NODE *n; SYMFREQ s,*p; UCHAR code; n=&node_heap[ctx]; code=sym_excl_code; freq_tot=0; sf_nb=0; SF_Read( n,p, { s=*p; if (sym_excl[s.sym]!=code) { freq_tot+=s.freq; sf_nb++; } } ); f=arith.Arith_DecodeVal(freq_tot+sf_nb); if (f>=freq_tot) { /* ESCAPE */ SF_Read(n,p, { sym_excl[p->sym]=code; } ); arith.Arith_Decode(freq_tot,freq_tot+sf_nb,freq_tot+sf_nb); return SYM_ESCAPE; } else { /* recherche du caractère */ freq_cum=0; SF_Read(n,p, { s=*p; if (sym_excl[s.sym]!=code) { freq_cum+=s.freq; if (freq_cum>f) goto decode_sym; } } ); decode_sym: /* incrémentation de la fréquence */ freq_sym=p->freq; p->freq=freq_sym+1; if (n->hdr.sf_max>=HDR_SFNB) n->hdr.sf.l.freq_tot++; /* décodage du caractère */ arith.Arith_Decode(freq_cum-freq_sym,freq_cum,freq_tot+sf_nb); if (freq_sym==(RENORM_FREQSYM-1) || freq_tot>=RENORM_FREQTOT) { Context_Renorm(ctx); } return s.sym; } } /* * Décodage d'un symbole */ int ppm_worker::PPM_Decode(void) { int i,order,sym; UINT ctx,ctx_tab[ORDER_MAX+1],ctx_last; /* recherche de l'ordre maximum */ Sym_ExcludeReset(); order=ORDER_MAX; ctx_last=NIL; while (1) { ctx=Context_Search(order); ctx_tab[order]=ctx; if (ctx=SYM_NB) return sym; break; } } for(i=order+1;i<=ORDER_MAX;i++) { if (ctx_tab[i]>=HASH_ADDRESS) Context_New(sym,i); else Context_NewSym(sym,ctx_tab[i]); } Hash_Update(sym); return sym; } /* * Décompression: idem */ #ifdef STAT /**************************************************************************** * Statistiques ****************************************************************************/ void ppm_worker::PrintStat(void) { fprintf(stderr,"free=%d ctx_nb=%d hash_moy=%0.2f\n", node_free_nb,ctx_nb, (float)hash_cnt/(float)hash_nb); } /* * Impression d'un caractère */ void ppm_worker::Sym_Print(int c) { if (c>=32 && c<=126) printf("%c",c); else printf("\\%2X",c); } /* * Impression couple SYMFREQ */ void ppm_worker::SF_Print(SYMFREQ s) { Sym_Print(s.sym); printf(":%d ",s.freq); } /* * Impression du contenu d'un contexte * utilisé pour les tests */ void ppm_worker::Context_Print(UINT c) { NODE *n; int i,sf_max,sf_nb,sf_freq; n=&node_heap[c]; sf_max=n->hdr.sf_max; sf_nb=sf_max+1; if (sf_max>=2) sf_freq=n->hdr.sf.l.freq_tot; else { sf_freq=0; for(i=0;i<=sf_max;i++) sf_freq+=n->hdr.sf.sf[i].freq; } printf("Ctx=%d: hash_n=%d ctx_p=%d ctx_n=%d o=%d sf_nb=%d sf_freq=%d\n", c,n->hdr.hash_next,n->hdr.ctx_prev,n->hdr.ctx_next, n->hdr.order,sf_nb,sf_freq); for(i=0;ihdr.order;i++) Sym_Print(n->hdr.sym[i]); printf(": "); if (sf_max<=1) { for(i=0;i<=sf_max;i++) SF_Print(n->hdr.sf.sf[i]); } else { n=&node_heap[n->hdr.sf.l.sf_next]; i=0; while (1) { SF_Print(n->sf.sf[i]); if (sf_max==0) break; i++; sf_max--; if (i==NODE_SFNB) { i=0; n=&node_heap[n->sf.sf_next]; } } } printf("\n"); } /* * Nombre total de contextes et nombre de contextes de longueur données. * Utilisé pour les statistiques */ void ppm_worker::Context_Statistic(void) { UINT i,p; int tab[SYM_NB+1],tot,cnt; for(i=0;i<=SYM_NB;i++) tab[i]=0; tot=0; p=ctx_first; do { cnt=node_heap[p].hdr.sf_max+1; tab[cnt]++; tot++; p=node_heap[p].hdr.ctx_next; } while (p!=ctx_last); printf("Context_Statistic: "); for(i=1;i<=SYM_NB;i++) { printf("%d:%d (%0.2f%%),",i,tab[i],(float)tab[i]/(float)tot*100.0); } printf("\n"); } #endif