author | llornkcor <llornkcor> | 2002-07-01 23:24:08 (UTC) |
---|---|---|
committer | llornkcor <llornkcor> | 2002-07-01 23:24:08 (UTC) |
commit | 59222a752fa4c8a1e8c2a00ee2f9e22855f12bb2 (patch) (unidiff) | |
tree | f148d4858859dac3b413e675c760acfdab24b8e6 /noncore/apps/opie-reader/ppm.h | |
parent | c08be8ae22dcc1bfb83cfdec807149b161d770f5 (diff) | |
download | opie-59222a752fa4c8a1e8c2a00ee2f9e22855f12bb2.zip opie-59222a752fa4c8a1e8c2a00ee2f9e22855f12bb2.tar.gz opie-59222a752fa4c8a1e8c2a00ee2f9e22855f12bb2.tar.bz2 |
initial
Diffstat (limited to 'noncore/apps/opie-reader/ppm.h') (more/less context) (ignore 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 @@ | |||
1 | #include "utypes.h" | ||
2 | |||
3 | #ifndef PPM_H | ||
4 | |||
5 | #define PPM_H | ||
6 | |||
7 | #include "arith.h" | ||
8 | |||
9 | /* pour le calcul éventuel de quelques statistiques */ | ||
10 | /* #define STAT */ | ||
11 | |||
12 | /* mise en mode debogage */ | ||
13 | /* #define DEBUG */ | ||
14 | |||
15 | /* nombre de noeuds maximum: peut être modifié, mais doit être tel que: | ||
16 | * HASH_SIZE+NODE_NBMAX<65530 | ||
17 | */ | ||
18 | //#define NODE_NBMAX 40000 | ||
19 | |||
20 | /* | ||
21 | * taille des buffers d'entrée/sortie | ||
22 | */ | ||
23 | #define BUFSIZE 1024 | ||
24 | |||
25 | /* | ||
26 | * Taille de la table de hachage | ||
27 | */ | ||
28 | #define HASH_SIZE 16384 | ||
29 | |||
30 | /* ordre maximale de prédiction utilisé (Phi) */ | ||
31 | #define ORDER_MAX 4 | ||
32 | |||
33 | /* fréquence maximale d'un symbole */ | ||
34 | #define RENORM_FREQSYM 250 | ||
35 | |||
36 | /* fréquence maximale pour la somme des fréquences des symboles d'un contexte */ | ||
37 | #define RENORM_FREQTOT 15000 | ||
38 | |||
39 | /* nombre de couples symbole,fréquence dans les structures de noeuds | ||
40 | * ajusté pour faire au total 16 octets */ | ||
41 | #define NODE_SFNB 7 | ||
42 | #define HDR_SFNB 2 | ||
43 | |||
44 | /* nombre de symboles à coder sans compter les symboles spéciaux */ | ||
45 | #define SYM_NB 256 | ||
46 | |||
47 | /* nombre de symboles spéciaux: pour extension si besoin de signalisation */ | ||
48 | #define SYM_SPECIAL_NB 1 | ||
49 | |||
50 | /* code associé au symbole ESCAPE (jamais codé de façon explicite) */ | ||
51 | #define SYM_ESCAPE 256 | ||
52 | |||
53 | /* code de fin de fichier */ | ||
54 | #define SYM_EOF 256 | ||
55 | |||
56 | /* valeur NULL pour les pointeurs stockés dans des USHORT */ | ||
57 | #define NIL 0xFFFF | ||
58 | |||
59 | /* codage de NIL utilisé pour retrouver l'adresse dans la table de hachage | ||
60 | * d'un contexte en regardant seulement CTXHDR.hash_next */ | ||
61 | #define HASH_ADDRESS (65530-HASH_SIZE) | ||
62 | |||
63 | |||
64 | /* stockage d'un couple symbole, fréquence */ | ||
65 | typedef struct { | ||
66 | UCHAR sym; /* numéro du symbole */ | ||
67 | UCHAR freq; /* fréquence du symbole */ | ||
68 | } SYMFREQ; | ||
69 | |||
70 | |||
71 | /* header pour gérer un contexte */ | ||
72 | typedef struct { | ||
73 | USHORT ctx_next; /* contexte suivant (moins utilisé) */ | ||
74 | USHORT ctx_prev; /* contexte précédent (plus utilisé) */ | ||
75 | USHORT hash_next; /* contexte suivant dans une entrée de la table | ||
76 | * de hachage */ | ||
77 | UCHAR order; /* ordre du contexte */ | ||
78 | UCHAR sym[ORDER_MAX]; /* symboles constituant le contexte */ | ||
79 | UCHAR sf_max; /* nombre de symboles-1 dans la liste L */ | ||
80 | union { | ||
81 | SYMFREQ sf[HDR_SFNB]; /* s'il y a moins de HDR_SFNB symboles dans | ||
82 | * le contexte, on les stocke directement ici | ||
83 | */ | ||
84 | struct { | ||
85 | USHORT freq_tot; /* sinon on stocke la fréquence totale (c) */ | ||
86 | USHORT sf_next; /* et un pointeur sur le premier noeud | ||
87 | * constituant la liste L des symboles associés | ||
88 | * au contexte */ | ||
89 | } l; | ||
90 | } sf; | ||
91 | } CTXHDR; | ||
92 | |||
93 | /* structure pour gérer NODE_SFNB éléments de la liste des symboles associés | ||
94 | * à un contexte */ | ||
95 | typedef struct { | ||
96 | SYMFREQ sf[NODE_SFNB]; /* les couples symbole, fréquence */ | ||
97 | USHORT sf_next; /* pointeur sur l'éventuel bloc suivant */ | ||
98 | } CTXSYMFREQ; | ||
99 | |||
100 | /* | ||
101 | * structure de base pour la gestion de la mémoire: le noeud | ||
102 | */ | ||
103 | |||
104 | typedef union _NODE { | ||
105 | CTXHDR hdr; /* si le noeud contient un header de contexte */ | ||
106 | CTXSYMFREQ sf; /* si le noeud contient une partie de la liste L */ | ||
107 | USHORT free_next; /* si le noeud est vide: pointeur sur un noeud vide | ||
108 | * suivant */ | ||
109 | } NODE; | ||
110 | |||
111 | class ppm_worker | ||
112 | { | ||
113 | |||
114 | /* gestion des noeuds */ | ||
115 | NODE *node_heap; /* heap contenant tous les noeuds */ | ||
116 | UINT node_free_nb; /* nombre de noeuds vides */ | ||
117 | UINT node_free_first; /* premier noeud de la liste des noeuds vides */ | ||
118 | UINT node_free_last; /* dernier noeud de la liste des noeuds vides */ | ||
119 | |||
120 | /* gestion de la liste des contextes les plus utilisés */ | ||
121 | USHORT *hash_table; /* table de hachage pour rechercher un contexte */ | ||
122 | UINT ctx_first; /* premier contexte: le plus utilisé */ | ||
123 | UINT ctx_last; /* dernier contexte: le moins utilisé */ | ||
124 | UINT ctx_nb; /* nombre de contextes */ | ||
125 | |||
126 | /* données caractérisant le contexte courant */ | ||
127 | UCHAR sym_context[ORDER_MAX+1]; /* symboles précédants le symbole en cours | ||
128 | * de codage */ | ||
129 | int sym_hash[ORDER_MAX+1]; /* index dans la table de hachage | ||
130 | * correspondants aux différentes longueurs | ||
131 | * de contextes | ||
132 | */ | ||
133 | |||
134 | /* système d'exclusion des caractères */ | ||
135 | UCHAR sym_excl[SYM_NB]; /* tableau pour l'exclusion */ | ||
136 | UCHAR sym_excl_code; /* code courant pour l'exclusion */ | ||
137 | |||
138 | |||
139 | /* déclaration des fonctions de base */ | ||
140 | |||
141 | /* noeuds */ | ||
142 | void Node_Free(UINT p); | ||
143 | UINT Node_Alloc(void); | ||
144 | |||
145 | /* contextes */ | ||
146 | void Context_DeleteLast(void); | ||
147 | void Context_MoveFirst(UINT c); | ||
148 | void Context_New(int sym,int order); | ||
149 | void Context_NewSym(int sym,UINT c); | ||
150 | UINT Context_Search(int order); | ||
151 | void Context_Renorm(UINT ctx); | ||
152 | void Hash_Update(int sym); | ||
153 | void Sym_ExcludeReset(void); | ||
154 | |||
155 | /* codage */ | ||
156 | /* | ||
157 | void Encode_NewSym(int sym); | ||
158 | int Encode_NoExclude(int sym,UINT ctx); | ||
159 | int Decode_Exclude(UINT ctx); | ||
160 | int PPM_Decode(void); | ||
161 | */ | ||
162 | |||
163 | /* décodage */ | ||
164 | int Decode_NewSym(void); | ||
165 | int Decode_NoExclude(UINT ctx); | ||
166 | int Decode_Exclude(UINT ctx); | ||
167 | |||
168 | #ifdef STAT | ||
169 | void PrintStat(void); | ||
170 | #endif | ||
171 | public: | ||
172 | ArithClass arith; | ||
173 | int PPM_Init(unsigned short); | ||
174 | void PPM_End(void); | ||
175 | int PPM_Decode(void); | ||
176 | }; | ||
177 | |||
178 | #endif | ||
179 | |||