Diffstat (limited to 'noncore/apps/opie-reader/ppm.h') (more/less context) (show whitespace changes)
| -rw-r--r-- | noncore/apps/opie-reader/ppm.h | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/noncore/apps/opie-reader/ppm.h b/noncore/apps/opie-reader/ppm.h new file mode 100644 index 0000000..4df9085 --- a/dev/null +++ b/noncore/apps/opie-reader/ppm.h @@ -0,0 +1,179 @@ +#include "utypes.h" + +#ifndef PPM_H + +#define PPM_H + +#include "arith.h" + +/* pour le calcul éventuel de quelques statistiques */ +/* #define STAT */ + +/* mise en mode debogage */ +/* #define DEBUG */ + +/* nombre de noeuds maximum: peut être modifié, mais doit être tel que: + * HASH_SIZE+NODE_NBMAX<65530 + */ +//#define NODE_NBMAX 40000 + +/* + * taille des buffers d'entrée/sortie + */ +#define BUFSIZE 1024 + +/* + * Taille de la table de hachage + */ +#define HASH_SIZE 16384 + +/* ordre maximale de prédiction utilisé (Phi) */ +#define ORDER_MAX 4 + +/* fréquence maximale d'un symbole */ +#define RENORM_FREQSYM 250 + +/* fréquence maximale pour la somme des fréquences des symboles d'un contexte */ +#define RENORM_FREQTOT 15000 + +/* nombre de couples symbole,fréquence dans les structures de noeuds + * ajusté pour faire au total 16 octets */ +#define NODE_SFNB 7 +#define HDR_SFNB 2 + +/* nombre de symboles à coder sans compter les symboles spéciaux */ +#define SYM_NB 256 + +/* nombre de symboles spéciaux: pour extension si besoin de signalisation */ +#define SYM_SPECIAL_NB 1 + +/* code associé au symbole ESCAPE (jamais codé de façon explicite) */ +#define SYM_ESCAPE 256 + +/* code de fin de fichier */ +#define SYM_EOF 256 + +/* valeur NULL pour les pointeurs stockés dans des USHORT */ +#define NIL 0xFFFF + +/* codage de NIL utilisé pour retrouver l'adresse dans la table de hachage + * d'un contexte en regardant seulement CTXHDR.hash_next */ +#define HASH_ADDRESS (65530-HASH_SIZE) + + +/* stockage d'un couple symbole, fréquence */ +typedef struct { + UCHAR sym; /* numéro du symbole */ + UCHAR freq; /* fréquence du symbole */ +} SYMFREQ; + + +/* header pour gérer un contexte */ +typedef struct { + USHORT ctx_next; /* contexte suivant (moins utilisé) */ + USHORT ctx_prev; /* contexte précédent (plus utilisé) */ + USHORT hash_next; /* contexte suivant dans une entrée de la table + * de hachage */ + UCHAR order; /* ordre du contexte */ + UCHAR sym[ORDER_MAX]; /* symboles constituant le contexte */ + UCHAR sf_max; /* nombre de symboles-1 dans la liste L */ + union { + SYMFREQ sf[HDR_SFNB]; /* s'il y a moins de HDR_SFNB symboles dans + * le contexte, on les stocke directement ici + */ + struct { + USHORT freq_tot; /* sinon on stocke la fréquence totale (c) */ + USHORT sf_next; /* et un pointeur sur le premier noeud + * constituant la liste L des symboles associés + * au contexte */ + } l; + } sf; +} CTXHDR; + +/* structure pour gérer NODE_SFNB éléments de la liste des symboles associés + * à un contexte */ +typedef struct { + SYMFREQ sf[NODE_SFNB]; /* les couples symbole, fréquence */ + USHORT sf_next; /* pointeur sur l'éventuel bloc suivant */ +} CTXSYMFREQ; + +/* + * structure de base pour la gestion de la mémoire: le noeud + */ + +typedef union _NODE { + CTXHDR hdr; /* si le noeud contient un header de contexte */ + CTXSYMFREQ sf; /* si le noeud contient une partie de la liste L */ + USHORT free_next; /* si le noeud est vide: pointeur sur un noeud vide + * suivant */ +} NODE; + +class ppm_worker +{ + +/* gestion des noeuds */ +NODE *node_heap; /* heap contenant tous les noeuds */ +UINT node_free_nb; /* nombre de noeuds vides */ +UINT node_free_first; /* premier noeud de la liste des noeuds vides */ +UINT node_free_last; /* dernier noeud de la liste des noeuds vides */ + +/* gestion de la liste des contextes les plus utilisés */ +USHORT *hash_table; /* table de hachage pour rechercher un contexte */ +UINT ctx_first; /* premier contexte: le plus utilisé */ +UINT ctx_last; /* dernier contexte: le moins utilisé */ +UINT ctx_nb; /* nombre de contextes */ + +/* données caractérisant le contexte courant */ +UCHAR sym_context[ORDER_MAX+1]; /* symboles précédants le symbole en cours + * de codage */ +int sym_hash[ORDER_MAX+1]; /* index dans la table de hachage + * correspondants aux différentes longueurs + * de contextes + */ + +/* système d'exclusion des caractères */ +UCHAR sym_excl[SYM_NB]; /* tableau pour l'exclusion */ +UCHAR sym_excl_code; /* code courant pour l'exclusion */ + + +/* déclaration des fonctions de base */ + +/* noeuds */ +void Node_Free(UINT p); +UINT Node_Alloc(void); + +/* contextes */ +void Context_DeleteLast(void); +void Context_MoveFirst(UINT c); +void Context_New(int sym,int order); +void Context_NewSym(int sym,UINT c); +UINT Context_Search(int order); +void Context_Renorm(UINT ctx); +void Hash_Update(int sym); + void Sym_ExcludeReset(void); + +/* codage */ +/* +void Encode_NewSym(int sym); +int Encode_NoExclude(int sym,UINT ctx); +int Decode_Exclude(UINT ctx); +int PPM_Decode(void); +*/ + +/* décodage */ +int Decode_NewSym(void); +int Decode_NoExclude(UINT ctx); +int Decode_Exclude(UINT ctx); + +#ifdef STAT +void PrintStat(void); +#endif + public: + ArithClass arith; + int PPM_Init(unsigned short); + void PPM_End(void); + int PPM_Decode(void); +}; + +#endif + |