initial

1 files changed, 756 insertions, 0 deletions

diff --git a/noncore/apps/opie-reader/ppm.cpp b/noncore/apps/opie-reader/ppm.cpp
new file mode 100644
index 0000000..e8bf110
--- a/dev/null
+++ b/noncore/apps/opie-reader/ppm.cpp
@@ -0,0 +1,756 @@
+#include <stdlib.h>
+#include <stdio.h>
+#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 (h<HASH_ADDRESS) h=node_heap[h].hdr.hash_next;
+  p=&hash_table[h-HASH_ADDRESS];
+  while (*p!=ctx_last) p=&node_heap[*p].hdr.hash_next;
+  *p=h_next;
+   
+  /* libération des noeuds & modification de ctx_last */
+   
+  if (n->hdr.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;i<order;i++) ctx->hdr.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 (p<HASH_ADDRESS)  {
+#ifdef STAT
+    hash_cnt++;
+#endif
+    n=&node_heap[p];
+    if (n->hdr.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;i<NODE_SFNB;i++)  {\
+						code_to_execute;\
+						p++;\
+				 }\
+				 p=&node_heap[ *((USHORT *)p) ].sf.sf[0];\
+				 nb-=NODE_SFNB;\
+      }\
+   }\
+   for(i=0;i<nb;i++)  {\
+			code_to_execute;\
+      p++;\
+   }\
+}
+
+
+/* 
+ * Renormalisation d'un contexte, ie, division de toutes les fréquences 
+ * par 2 et élimination des symboles de fréquence nulle  
+ * Note: le contexte obtenu n'est jamais vide. 
+ * Une amélioration prévue mais non implémentée serait de trier le contexte
+ * dans l'ordre des fréquences décroissantes pour accélérer la recherche.
+ * Les gains en vitesse seraient de toute façon assez faibles car les
+ * contextes sont de toute façon à peu près triés vu leur méthode de 
+ * construction: les caractères sont ajoutés à la fin de la liste 
+ */
+void ppm_worker::Context_Renorm(UINT ctx) {
+  NODE *n,*m;
+  UINT a,b,c,i,freq_tot,sf_nb;
+  SYMFREQ s,*p,tab_sf[SYM_NB];
+	 
+#ifdef DEBUG   
+  printf("Context_Renorm: c=%d\n",ctx);
+  Context_Print(ctx);
+#endif 
+   
+  n=&node_heap[ctx];
+  freq_tot=0;
+  sf_nb=0;
+	 
+  SF_Read(n,p, {
+    s=*p;
+    s.freq=s.freq/2;
+    if (s.freq!=0) {
+      freq_tot+=s.freq;
+      tab_sf[sf_nb]=s;
+      sf_nb++;
+    }
+  } );
+	 
+	 
+  /* libération des noeuds utilisés pour stocker les symboles */
+  if (n->hdr.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;i<sf_nb;i++) n->hdr.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<SYM_NB;i++) sym_excl[i]=0;
+    sym_excl_code=1;
+  }
+}
+
+
+/****************************************************************************
+ * Initialisation et Libération mémoire 
+ ****************************************************************************/
+
+/*
+ * Initialisation des structures de données du compresseur/décompresseur
+ * retourne 0 si tout va bien
+ */
+int ppm_worker::PPM_Init(unsigned short NODE_NBMAX) {
+  UINT i;
+  node_heap= new NODE[NODE_NBMAX];
+  hash_table= new USHORT[HASH_SIZE];
+  if (node_heap==NULL || hash_table==NULL)  {
+    if (node_heap!=NULL) delete [] node_heap;
+    if (hash_table!=NULL) delete [] hash_table;
+    return 1;
+  }
+  /* noeuds: tous vides */
+  for(i=0;i<=(NODE_NBMAX-2);i++) node_heap[i].free_next=i+1;
+  node_heap[NODE_NBMAX-1].free_next=NIL;
+  node_free_first=0;
+  node_free_last=NODE_NBMAX-1;
+  node_free_nb=NODE_NBMAX;
+   
+  /* contextes */
+  for(i=0;i<HASH_SIZE;i++) hash_table[i]=HASH_ADDRESS+i;
+   
+  /* cette initialisation n'est pas sûre mais simplifie beaucoup le code:
+   * on suppose que le premier contexte sera alloué dans le noeud 0
+   */
+  ctx_first=0;
+  ctx_last=0;
+  ctx_nb=0;
+   
+  /* contexte courant */
+  for(i=0;i<=ORDER_MAX;i++) sym_context[i]=0;
+  for(i=0;i<=ORDER_MAX;i++) sym_hash[i]=0;
+
+  /* système d'exclusion des caractères */
+  sym_excl_code=0xFF;
+	 
+  return 0;
+}
+
+/*
+ * Fin de la compression/décompression: on libère la mémoire
+ */
+void ppm_worker::PPM_End(void) {
+  free(hash_table);
+  free(node_heap);
+}
+
+/****************************************************************************
+ * Décodage et décompression
+ ****************************************************************************/
+
+/*
+ * Décodage: cf Encode_NewSym
+ */
+int ppm_worker::Decode_NewSym(void) {
+  UINT i,freq_tot,freq_cum,f;
+  UCHAR code;
+	 
+  code=sym_excl_code;
+  freq_tot=0;
+  for(i=0;i<SYM_NB;i++) if (sym_excl[i]!=code) freq_tot++;
+  f=arith.Arith_DecodeVal(freq_tot+SYM_SPECIAL_NB);
+  if (f>=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_max<HDR_SFNB)  {
+    freq_tot=0;
+    for(i=0;i<=n->hdr.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<HASH_ADDRESS)  {
+      Context_MoveFirst(ctx); 
+      if (ctx_last==NIL)
+	sym=Decode_NoExclude(ctx);
+      else
+	sym=Decode_Exclude(ctx);
+      if (sym!=SYM_ESCAPE) break;
+      ctx_last=ctx;
+    } 
+    order--;
+    if (order==-1)  {
+      sym=Decode_NewSym();
+      if (sym>=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;i<n->hdr.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
+