Diffstat (limited to 'noncore/apps/opie-reader/ppm.cpp') (more/less context) (ignore whitespace changes)
-rw-r--r-- | noncore/apps/opie-reader/ppm.cpp | 756 |
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 @@ | |||
1 | #include <stdlib.h> | ||
2 | #include <stdio.h> | ||
3 | #include "arith.h" | ||
4 | #include "ppm.h" | ||
5 | |||
6 | /**************************************************************************** | ||
7 | * Gestion des noeuds | ||
8 | ****************************************************************************/ | ||
9 | |||
10 | /* | ||
11 | * Désallocation du noeud p | ||
12 | */ | ||
13 | |||
14 | void ppm_worker::Node_Free(UINT p) { | ||
15 | node_heap[node_free_last].free_next=p; | ||
16 | node_heap[p].free_next=NIL; | ||
17 | node_free_last=p; | ||
18 | node_free_nb++; | ||
19 | } | ||
20 | |||
21 | /* | ||
22 | * Allocation d'un noeud | ||
23 | * s'il ne reste plus de place, on désalloue le contexte le moins utilisé. | ||
24 | */ | ||
25 | |||
26 | UINT ppm_worker::Node_Alloc(void) { | ||
27 | UINT p; | ||
28 | if (node_free_nb<=2) Context_DeleteLast(); | ||
29 | p=node_free_first; | ||
30 | node_free_first=node_heap[node_free_first].free_next; | ||
31 | node_free_nb--; | ||
32 | #ifdef DEBUG | ||
33 | printf("Node_Alloc: p=%d\n",p); | ||
34 | #endif | ||
35 | return p; | ||
36 | } | ||
37 | |||
38 | /**************************************************************************** | ||
39 | * Gestion des contextes | ||
40 | ****************************************************************************/ | ||
41 | |||
42 | |||
43 | /* | ||
44 | * Mise au début de la liste des contextes du contexte c | ||
45 | */ | ||
46 | void ppm_worker::Context_MoveFirst(UINT c) { | ||
47 | NODE *ctx; | ||
48 | |||
49 | if (c!=ctx_first) { | ||
50 | ctx=&node_heap[c]; | ||
51 | /* suppression du contexte dans la liste */ | ||
52 | if (c==ctx_last) { | ||
53 | ctx_last=ctx->hdr.ctx_prev; | ||
54 | } else { | ||
55 | node_heap[ctx->hdr.ctx_prev].hdr.ctx_next=ctx->hdr.ctx_next; | ||
56 | node_heap[ctx->hdr.ctx_next].hdr.ctx_prev=ctx->hdr.ctx_prev; | ||
57 | } | ||
58 | /* insertion au début de la liste */ | ||
59 | node_heap[ctx_first].hdr.ctx_prev=c; | ||
60 | ctx->hdr.ctx_next=ctx_first; | ||
61 | ctx_first=c; | ||
62 | } | ||
63 | } | ||
64 | |||
65 | /* | ||
66 | * Destruction du contexte le moins utilisé (ctx_last) | ||
67 | */ | ||
68 | void ppm_worker::Context_DeleteLast(void) { | ||
69 | NODE *n; | ||
70 | UINT h,h_next,node,node_next; | ||
71 | USHORT *p; | ||
72 | |||
73 | n=&node_heap[ctx_last]; | ||
74 | |||
75 | /* libération dans la table de hachage. Comme on ne dispose pas de | ||
76 | * pointeur hash_prev dans les contextes, il faut parcourir toute | ||
77 | * la liste. Heureusement, celle-ci est de longueur faible en moyenne | ||
78 | */ | ||
79 | h_next=n->hdr.hash_next; | ||
80 | h=h_next; | ||
81 | while (h<HASH_ADDRESS) h=node_heap[h].hdr.hash_next; | ||
82 | p=&hash_table[h-HASH_ADDRESS]; | ||
83 | while (*p!=ctx_last) p=&node_heap[*p].hdr.hash_next; | ||
84 | *p=h_next; | ||
85 | |||
86 | /* libération des noeuds & modification de ctx_last */ | ||
87 | |||
88 | if (n->hdr.sf_max>=2) { | ||
89 | node=n->hdr.sf.l.sf_next; | ||
90 | while (1) { | ||
91 | node_next=node_heap[node].sf.sf_next; | ||
92 | Node_Free(node); | ||
93 | if (node_next==NIL) break; | ||
94 | node=node_next; | ||
95 | } | ||
96 | } | ||
97 | |||
98 | node=ctx_last; | ||
99 | ctx_last=n->hdr.ctx_prev; | ||
100 | Node_Free(node); | ||
101 | ctx_nb--; | ||
102 | } | ||
103 | |||
104 | /* | ||
105 | * Création d'un nouveau contexte avec un seul symbole sym de fréquence 1 | ||
106 | * Utilisation implicite de sym_context et sym_hash. | ||
107 | * Libération de mémoire si nécessaire, et mise en premier dans la liste | ||
108 | */ | ||
109 | void ppm_worker::Context_New(int sym,int order) { | ||
110 | NODE *ctx; | ||
111 | UINT i,c; | ||
112 | |||
113 | #ifdef DEBUG | ||
114 | printf("Context_New: sym=%d o=%d\n",sym,order); | ||
115 | #endif | ||
116 | |||
117 | c=Node_Alloc(); | ||
118 | ctx=&node_heap[c]; | ||
119 | |||
120 | /* mise du contexte en tête de la liste */ | ||
121 | ctx->hdr.ctx_next=ctx_first; | ||
122 | node_heap[ctx_first].hdr.ctx_prev=c; | ||
123 | ctx_first=c; | ||
124 | ctx_nb++; | ||
125 | |||
126 | /* insertion dans la table de hachage */ | ||
127 | ctx->hdr.hash_next=hash_table[sym_hash[order]]; | ||
128 | hash_table[sym_hash[order]]=ctx_first; | ||
129 | |||
130 | /* initialisation du contexte */ | ||
131 | ctx->hdr.order=order; | ||
132 | for(i=0;i<order;i++) ctx->hdr.sym[i]=sym_context[i+1]; | ||
133 | |||
134 | ctx->hdr.sf_max=0; | ||
135 | ctx->hdr.sf.sf[0].sym=sym; | ||
136 | ctx->hdr.sf.sf[0].freq=1; | ||
137 | #ifdef DEBUG | ||
138 | Context_Print(ctx_first); | ||
139 | #endif | ||
140 | } | ||
141 | |||
142 | /* | ||
143 | * Ajout d'un nouveau symbole au contexte c | ||
144 | */ | ||
145 | |||
146 | void ppm_worker::Context_NewSym(int sym,UINT c) { | ||
147 | NODE *n,*m; | ||
148 | UINT p,sf_max; | ||
149 | |||
150 | #ifdef DEBUG | ||
151 | printf("Context_NewSym: sym=%d c=%d\n",sym,c); | ||
152 | Context_Print(c); | ||
153 | #endif | ||
154 | |||
155 | n=&node_heap[c]; | ||
156 | sf_max=n->hdr.sf_max; | ||
157 | n->hdr.sf_max++; | ||
158 | if (sf_max==0) { | ||
159 | n->hdr.sf.sf[1].sym=sym; | ||
160 | n->hdr.sf.sf[1].freq=1; | ||
161 | } else if (sf_max==1) { | ||
162 | p=Node_Alloc(); | ||
163 | m=&node_heap[p]; | ||
164 | m->sf.sf[0]=n->hdr.sf.sf[0]; | ||
165 | m->sf.sf[1]=n->hdr.sf.sf[1]; | ||
166 | m->sf.sf[2].sym=sym; | ||
167 | m->sf.sf[2].freq=1; | ||
168 | m->sf.sf_next=NIL; | ||
169 | n->hdr.sf.l.sf_next=p; | ||
170 | n->hdr.sf.l.freq_tot=((UINT)m->sf.sf[0].freq+(UINT)m->sf.sf[1].freq+1); | ||
171 | } else { | ||
172 | n->hdr.sf.l.freq_tot++; | ||
173 | m=&node_heap[n->hdr.sf.l.sf_next]; | ||
174 | while (sf_max>=NODE_SFNB) { | ||
175 | sf_max-=NODE_SFNB; | ||
176 | m=&node_heap[m->sf.sf_next]; | ||
177 | } | ||
178 | sf_max++; | ||
179 | if (sf_max==NODE_SFNB) { | ||
180 | p=Node_Alloc(); | ||
181 | m->sf.sf_next=p; | ||
182 | m=&node_heap[p]; | ||
183 | m->sf.sf_next=NIL; | ||
184 | sf_max=0; | ||
185 | } | ||
186 | m->sf.sf[sf_max].sym=sym; | ||
187 | m->sf.sf[sf_max].freq=1; | ||
188 | } | ||
189 | #ifdef DEBUG | ||
190 | Context_Print(c); | ||
191 | #endif | ||
192 | } | ||
193 | |||
194 | |||
195 | #ifdef STAT | ||
196 | int hash_nb=1; | ||
197 | int hash_cnt=0; | ||
198 | #endif | ||
199 | |||
200 | /* | ||
201 | * Recherche d'un contexte, utilisation de façon implicite de sym_context | ||
202 | * et de sym_hash. | ||
203 | * C'est une procédure très critique qui doit être particulièrement optimisée | ||
204 | */ | ||
205 | |||
206 | UINT ppm_worker::Context_Search(int order) { | ||
207 | UCHAR *sym; | ||
208 | UINT i,p; | ||
209 | NODE *n; | ||
210 | #ifdef DEBUG | ||
211 | printf("Context_Search: o=%d\n",order); | ||
212 | #endif | ||
213 | |||
214 | p=hash_table[sym_hash[order]]; | ||
215 | sym=&sym_context[1]; | ||
216 | #ifdef STAT | ||
217 | hash_nb++; | ||
218 | #endif | ||
219 | while (p<HASH_ADDRESS) { | ||
220 | #ifdef STAT | ||
221 | hash_cnt++; | ||
222 | #endif | ||
223 | n=&node_heap[p]; | ||
224 | if (n->hdr.order==order) { | ||
225 | if (order==0) return p; | ||
226 | i=0; | ||
227 | while (sym[i]==n->hdr.sym[i]) { | ||
228 | i++; | ||
229 | if (i==order) return p; | ||
230 | } | ||
231 | } | ||
232 | p=n->hdr.hash_next; | ||
233 | } | ||
234 | return HASH_ADDRESS; | ||
235 | } | ||
236 | |||
237 | /* | ||
238 | * Cette macro est HORRIBLE mais permet de simplifier beaucoup le parcours | ||
239 | * des listes de couples symbole,fréquence tout en ayant un code rapide. | ||
240 | * Une alternative élégante mais lente aurait été de passer une fonction | ||
241 | * en paramètre contenant le code à exécuter | ||
242 | */ | ||
243 | |||
244 | #define SF_Read(n,p,code_to_execute) \ | ||
245 | {\ | ||
246 | UINT nb,i;\ | ||
247 | nb=(UINT)n->hdr.sf_max+1;\ | ||
248 | if (nb<=HDR_SFNB) {\ | ||
249 | p=&n->hdr.sf.sf[0];\ | ||
250 | } else {\ | ||
251 | p=&node_heap[n->hdr.sf.l.sf_next].sf.sf[0];\ | ||
252 | while (nb>NODE_SFNB) {\ | ||
253 | for(i=0;i<NODE_SFNB;i++) {\ | ||
254 | code_to_execute;\ | ||
255 | p++;\ | ||
256 | }\ | ||
257 | p=&node_heap[ *((USHORT *)p) ].sf.sf[0];\ | ||
258 | nb-=NODE_SFNB;\ | ||
259 | }\ | ||
260 | }\ | ||
261 | for(i=0;i<nb;i++) {\ | ||
262 | code_to_execute;\ | ||
263 | p++;\ | ||
264 | }\ | ||
265 | } | ||
266 | |||
267 | |||
268 | /* | ||
269 | * Renormalisation d'un contexte, ie, division de toutes les fréquences | ||
270 | * par 2 et élimination des symboles de fréquence nulle | ||
271 | * Note: le contexte obtenu n'est jamais vide. | ||
272 | * Une amélioration prévue mais non implémentée serait de trier le contexte | ||
273 | * dans l'ordre des fréquences décroissantes pour accélérer la recherche. | ||
274 | * Les gains en vitesse seraient de toute façon assez faibles car les | ||
275 | * contextes sont de toute façon à peu près triés vu leur méthode de | ||
276 | * construction: les caractères sont ajoutés à la fin de la liste | ||
277 | */ | ||
278 | void ppm_worker::Context_Renorm(UINT ctx) { | ||
279 | NODE *n,*m; | ||
280 | UINT a,b,c,i,freq_tot,sf_nb; | ||
281 | SYMFREQ s,*p,tab_sf[SYM_NB]; | ||
282 | |||
283 | #ifdef DEBUG | ||
284 | printf("Context_Renorm: c=%d\n",ctx); | ||
285 | Context_Print(ctx); | ||
286 | #endif | ||
287 | |||
288 | n=&node_heap[ctx]; | ||
289 | freq_tot=0; | ||
290 | sf_nb=0; | ||
291 | |||
292 | SF_Read(n,p, { | ||
293 | s=*p; | ||
294 | s.freq=s.freq/2; | ||
295 | if (s.freq!=0) { | ||
296 | freq_tot+=s.freq; | ||
297 | tab_sf[sf_nb]=s; | ||
298 | sf_nb++; | ||
299 | } | ||
300 | } ); | ||
301 | |||
302 | |||
303 | /* libération des noeuds utilisés pour stocker les symboles */ | ||
304 | if (n->hdr.sf_max>=HDR_SFNB) { | ||
305 | a=n->hdr.sf.l.sf_next; | ||
306 | do { | ||
307 | b=node_heap[a].sf.sf_next; | ||
308 | Node_Free(a); | ||
309 | a=b; | ||
310 | } while (a!=NIL); | ||
311 | } | ||
312 | |||
313 | /* reconstruction de la liste des "sf_nb" symboles d'apres le tableau | ||
314 | * "tab_sf" | ||
315 | */ | ||
316 | |||
317 | n->hdr.sf_max=sf_nb-1; | ||
318 | if (sf_nb<=HDR_SFNB) { | ||
319 | for(i=0;i<sf_nb;i++) n->hdr.sf.sf[i]=tab_sf[i]; | ||
320 | } else { | ||
321 | a=Node_Alloc(); | ||
322 | n->hdr.sf.l.sf_next=a; | ||
323 | n->hdr.sf.l.freq_tot=freq_tot; | ||
324 | m=&node_heap[a]; | ||
325 | i=0; | ||
326 | c=0; | ||
327 | while (1) { | ||
328 | m->sf.sf[c]=tab_sf[i]; | ||
329 | i++; | ||
330 | if (i==sf_nb) break; | ||
331 | c++; | ||
332 | if (c==NODE_SFNB) { | ||
333 | c=0; | ||
334 | a=Node_Alloc(); | ||
335 | m->sf.sf_next=a; | ||
336 | m=&node_heap[a]; | ||
337 | } | ||
338 | } | ||
339 | m->sf.sf_next=NIL; | ||
340 | } | ||
341 | |||
342 | #ifdef DEBUG | ||
343 | Context_Print(ctx); | ||
344 | #endif | ||
345 | } | ||
346 | |||
347 | |||
348 | /* | ||
349 | * Mise à jour des index dans la table de hachage et des caractères du | ||
350 | * contexte courant. | ||
351 | * La fonction de hachage a été choisie de façon empirique en controlant | ||
352 | * qu'elle donne en moyenne de bons résultats. | ||
353 | */ | ||
354 | void ppm_worker::Hash_Update(int sym) { | ||
355 | UINT i,k; | ||
356 | |||
357 | for(i=ORDER_MAX;i>=2;i--) | ||
358 | sym_context[i]=sym_context[i-1]; | ||
359 | sym_context[1]=sym; | ||
360 | |||
361 | for(i=ORDER_MAX;i>=2;i--) { | ||
362 | k=sym_hash[i-1]; | ||
363 | sym_hash[i]=( (k<<6)-k+sym ) & (HASH_SIZE-1); | ||
364 | } | ||
365 | sym_hash[1]=sym+1; | ||
366 | } | ||
367 | |||
368 | |||
369 | /**************************************************************************** | ||
370 | * Système d'exclusion des symboles | ||
371 | ****************************************************************************/ | ||
372 | |||
373 | |||
374 | /* | ||
375 | * Remise à zéro du tableau d'exclusion des symboles | ||
376 | */ | ||
377 | void ppm_worker::Sym_ExcludeReset(void) { | ||
378 | UINT i; | ||
379 | |||
380 | sym_excl_code++; | ||
381 | if (sym_excl_code==0) { | ||
382 | for(i=0;i<SYM_NB;i++) sym_excl[i]=0; | ||
383 | sym_excl_code=1; | ||
384 | } | ||
385 | } | ||
386 | |||
387 | |||
388 | /**************************************************************************** | ||
389 | * Initialisation et Libération mémoire | ||
390 | ****************************************************************************/ | ||
391 | |||
392 | /* | ||
393 | * Initialisation des structures de données du compresseur/décompresseur | ||
394 | * retourne 0 si tout va bien | ||
395 | */ | ||
396 | int ppm_worker::PPM_Init(unsigned short NODE_NBMAX) { | ||
397 | UINT i; | ||
398 | node_heap= new NODE[NODE_NBMAX]; | ||
399 | hash_table= new USHORT[HASH_SIZE]; | ||
400 | if (node_heap==NULL || hash_table==NULL) { | ||
401 | if (node_heap!=NULL) delete [] node_heap; | ||
402 | if (hash_table!=NULL) delete [] hash_table; | ||
403 | return 1; | ||
404 | } | ||
405 | /* noeuds: tous vides */ | ||
406 | for(i=0;i<=(NODE_NBMAX-2);i++) node_heap[i].free_next=i+1; | ||
407 | node_heap[NODE_NBMAX-1].free_next=NIL; | ||
408 | node_free_first=0; | ||
409 | node_free_last=NODE_NBMAX-1; | ||
410 | node_free_nb=NODE_NBMAX; | ||
411 | |||
412 | /* contextes */ | ||
413 | for(i=0;i<HASH_SIZE;i++) hash_table[i]=HASH_ADDRESS+i; | ||
414 | |||
415 | /* cette initialisation n'est pas sûre mais simplifie beaucoup le code: | ||
416 | * on suppose que le premier contexte sera alloué dans le noeud 0 | ||
417 | */ | ||
418 | ctx_first=0; | ||
419 | ctx_last=0; | ||
420 | ctx_nb=0; | ||
421 | |||
422 | /* contexte courant */ | ||
423 | for(i=0;i<=ORDER_MAX;i++) sym_context[i]=0; | ||
424 | for(i=0;i<=ORDER_MAX;i++) sym_hash[i]=0; | ||
425 | |||
426 | /* système d'exclusion des caractères */ | ||
427 | sym_excl_code=0xFF; | ||
428 | |||
429 | return 0; | ||
430 | } | ||
431 | |||
432 | /* | ||
433 | * Fin de la compression/décompression: on libère la mémoire | ||
434 | */ | ||
435 | void ppm_worker::PPM_End(void) { | ||
436 | free(hash_table); | ||
437 | free(node_heap); | ||
438 | } | ||
439 | |||
440 | /**************************************************************************** | ||
441 | * Décodage et décompression | ||
442 | ****************************************************************************/ | ||
443 | |||
444 | /* | ||
445 | * Décodage: cf Encode_NewSym | ||
446 | */ | ||
447 | int ppm_worker::Decode_NewSym(void) { | ||
448 | UINT i,freq_tot,freq_cum,f; | ||
449 | UCHAR code; | ||
450 | |||
451 | code=sym_excl_code; | ||
452 | freq_tot=0; | ||
453 | for(i=0;i<SYM_NB;i++) if (sym_excl[i]!=code) freq_tot++; | ||
454 | f=arith.Arith_DecodeVal(freq_tot+SYM_SPECIAL_NB); | ||
455 | if (f>=freq_tot) { | ||
456 | /* cas d'un symbole spécial */ | ||
457 | arith.Arith_Decode(f,f+1,freq_tot+SYM_SPECIAL_NB); | ||
458 | return SYM_NB+f-freq_tot; | ||
459 | } else { | ||
460 | i=0; | ||
461 | freq_cum=0; | ||
462 | while (1) { | ||
463 | if (sym_excl[i]!=code) { | ||
464 | freq_cum++; | ||
465 | if (freq_cum>f) break; | ||
466 | } | ||
467 | i++; | ||
468 | } | ||
469 | arith.Arith_Decode(freq_cum-1,freq_cum,freq_tot+SYM_SPECIAL_NB); | ||
470 | return i; | ||
471 | } | ||
472 | } | ||
473 | |||
474 | /* | ||
475 | * Décodage: cf Decode_NoExclude | ||
476 | */ | ||
477 | int ppm_worker::Decode_NoExclude(UINT ctx) { | ||
478 | NODE *n; | ||
479 | UCHAR code; | ||
480 | UINT i,f,freq_tot,freq_cum,freq_sym,sf_nb; | ||
481 | SYMFREQ *p,s; | ||
482 | |||
483 | |||
484 | n=&node_heap[ctx]; | ||
485 | code=sym_excl_code; | ||
486 | |||
487 | /* Calcul de la somme des fréquences des caractères */ | ||
488 | if (n->hdr.sf_max<HDR_SFNB) { | ||
489 | freq_tot=0; | ||
490 | for(i=0;i<=n->hdr.sf_max;i++) freq_tot+=n->hdr.sf.sf[i].freq; | ||
491 | } else { | ||
492 | freq_tot=n->hdr.sf.l.freq_tot; | ||
493 | } | ||
494 | |||
495 | /* décodage */ | ||
496 | sf_nb=(UINT) n->hdr.sf_max+1; | ||
497 | f=arith.Arith_DecodeVal(freq_tot+sf_nb); | ||
498 | if (f>=freq_tot) { | ||
499 | /* gestion du code ESCAPE */ | ||
500 | |||
501 | /* marquage des caractères utilisés */ | ||
502 | SF_Read(n,p, { sym_excl[p->sym]=code; }); | ||
503 | |||
504 | /* décodage ESCAPE */ | ||
505 | arith.Arith_Decode(freq_tot,freq_tot+sf_nb,freq_tot+sf_nb); | ||
506 | return SYM_ESCAPE; | ||
507 | } | ||
508 | |||
509 | /* recherche du caractère en calculant la fréquence */ | ||
510 | freq_cum=0; | ||
511 | SF_Read(n,p, { | ||
512 | s=*p; | ||
513 | freq_cum+=s.freq; | ||
514 | if (freq_cum>f) goto decode_sym; | ||
515 | } ); | ||
516 | |||
517 | decode_sym: | ||
518 | |||
519 | freq_sym=s.freq; | ||
520 | p->freq=freq_sym+1; | ||
521 | if (n->hdr.sf_max>=HDR_SFNB) n->hdr.sf.l.freq_tot=freq_tot+1; | ||
522 | |||
523 | arith.Arith_Decode(freq_cum-freq_sym,freq_cum,freq_tot+sf_nb); | ||
524 | |||
525 | /* test de la renormalisation */ | ||
526 | if (freq_sym==(RENORM_FREQSYM-1) || freq_tot>=RENORM_FREQTOT) { | ||
527 | Context_Renorm(ctx); | ||
528 | } | ||
529 | return s.sym; | ||
530 | } | ||
531 | |||
532 | |||
533 | /* | ||
534 | * Décodage: cf Encode_Exclude | ||
535 | */ | ||
536 | |||
537 | int ppm_worker::Decode_Exclude(UINT ctx) { | ||
538 | UINT sf_nb,freq_sym,freq_cum,freq_tot,f; | ||
539 | NODE *n; | ||
540 | SYMFREQ s,*p; | ||
541 | UCHAR code; | ||
542 | |||
543 | n=&node_heap[ctx]; | ||
544 | code=sym_excl_code; | ||
545 | |||
546 | freq_tot=0; | ||
547 | sf_nb=0; | ||
548 | |||
549 | SF_Read( n,p, { | ||
550 | s=*p; | ||
551 | if (sym_excl[s.sym]!=code) | ||
552 | { | ||
553 | freq_tot+=s.freq; | ||
554 | sf_nb++; | ||
555 | } | ||
556 | } ); | ||
557 | |||
558 | |||
559 | f=arith.Arith_DecodeVal(freq_tot+sf_nb); | ||
560 | |||
561 | if (f>=freq_tot) { | ||
562 | |||
563 | /* ESCAPE */ | ||
564 | |||
565 | SF_Read(n,p, { sym_excl[p->sym]=code; } ); | ||
566 | |||
567 | arith.Arith_Decode(freq_tot,freq_tot+sf_nb,freq_tot+sf_nb); | ||
568 | |||
569 | return SYM_ESCAPE; | ||
570 | } else { | ||
571 | |||
572 | /* recherche du caractère */ | ||
573 | |||
574 | freq_cum=0; | ||
575 | SF_Read(n,p, { | ||
576 | s=*p; | ||
577 | if (sym_excl[s.sym]!=code) { | ||
578 | freq_cum+=s.freq; | ||
579 | if (freq_cum>f) goto decode_sym; | ||
580 | } | ||
581 | } ); | ||
582 | |||
583 | decode_sym: | ||
584 | |||
585 | /* incrémentation de la fréquence */ | ||
586 | |||
587 | freq_sym=p->freq; | ||
588 | p->freq=freq_sym+1; | ||
589 | if (n->hdr.sf_max>=HDR_SFNB) n->hdr.sf.l.freq_tot++; | ||
590 | |||
591 | /* décodage du caractère */ | ||
592 | |||
593 | arith.Arith_Decode(freq_cum-freq_sym,freq_cum,freq_tot+sf_nb); | ||
594 | |||
595 | if (freq_sym==(RENORM_FREQSYM-1) || freq_tot>=RENORM_FREQTOT) { | ||
596 | Context_Renorm(ctx); | ||
597 | } | ||
598 | |||
599 | return s.sym; | ||
600 | } | ||
601 | } | ||
602 | |||
603 | |||
604 | /* | ||
605 | * Décodage d'un symbole | ||
606 | */ | ||
607 | int ppm_worker::PPM_Decode(void) { | ||
608 | int i,order,sym; | ||
609 | UINT ctx,ctx_tab[ORDER_MAX+1],ctx_last; | ||
610 | |||
611 | |||
612 | /* recherche de l'ordre maximum */ | ||
613 | |||
614 | Sym_ExcludeReset(); | ||
615 | order=ORDER_MAX; | ||
616 | ctx_last=NIL; | ||
617 | while (1) { | ||
618 | ctx=Context_Search(order); | ||
619 | ctx_tab[order]=ctx; | ||
620 | if (ctx<HASH_ADDRESS) { | ||
621 | Context_MoveFirst(ctx); | ||
622 | if (ctx_last==NIL) | ||
623 | sym=Decode_NoExclude(ctx); | ||
624 | else | ||
625 | sym=Decode_Exclude(ctx); | ||
626 | if (sym!=SYM_ESCAPE) break; | ||
627 | ctx_last=ctx; | ||
628 | } | ||
629 | order--; | ||
630 | if (order==-1) { | ||
631 | sym=Decode_NewSym(); | ||
632 | if (sym>=SYM_NB) return sym; | ||
633 | break; | ||
634 | } | ||
635 | } | ||
636 | |||
637 | for(i=order+1;i<=ORDER_MAX;i++) { | ||
638 | if (ctx_tab[i]>=HASH_ADDRESS) | ||
639 | Context_New(sym,i); | ||
640 | else | ||
641 | Context_NewSym(sym,ctx_tab[i]); | ||
642 | } | ||
643 | |||
644 | Hash_Update(sym); | ||
645 | |||
646 | return sym; | ||
647 | } | ||
648 | |||
649 | /* | ||
650 | * Décompression: idem | ||
651 | */ | ||
652 | |||
653 | #ifdef STAT | ||
654 | |||
655 | /**************************************************************************** | ||
656 | * Statistiques | ||
657 | ****************************************************************************/ | ||
658 | |||
659 | |||
660 | void ppm_worker::PrintStat(void) { | ||
661 | fprintf(stderr,"free=%d ctx_nb=%d hash_moy=%0.2f\n", | ||
662 | node_free_nb,ctx_nb, | ||
663 | (float)hash_cnt/(float)hash_nb); | ||
664 | |||
665 | } | ||
666 | |||
667 | /* | ||
668 | * Impression d'un caractère | ||
669 | */ | ||
670 | void ppm_worker::Sym_Print(int c) { | ||
671 | if (c>=32 && c<=126) printf("%c",c); else printf("\\%2X",c); | ||
672 | } | ||
673 | |||
674 | /* | ||
675 | * Impression couple SYMFREQ | ||
676 | */ | ||
677 | |||
678 | void ppm_worker::SF_Print(SYMFREQ s) { | ||
679 | Sym_Print(s.sym); | ||
680 | printf(":%d ",s.freq); | ||
681 | } | ||
682 | |||
683 | /* | ||
684 | * Impression du contenu d'un contexte | ||
685 | * utilisé pour les tests | ||
686 | */ | ||
687 | |||
688 | void ppm_worker::Context_Print(UINT c) { | ||
689 | NODE *n; | ||
690 | int i,sf_max,sf_nb,sf_freq; | ||
691 | |||
692 | n=&node_heap[c]; | ||
693 | |||
694 | sf_max=n->hdr.sf_max; | ||
695 | sf_nb=sf_max+1; | ||
696 | if (sf_max>=2) sf_freq=n->hdr.sf.l.freq_tot; | ||
697 | else { | ||
698 | sf_freq=0; | ||
699 | for(i=0;i<=sf_max;i++) sf_freq+=n->hdr.sf.sf[i].freq; | ||
700 | } | ||
701 | |||
702 | printf("Ctx=%d: hash_n=%d ctx_p=%d ctx_n=%d o=%d sf_nb=%d sf_freq=%d\n", | ||
703 | c,n->hdr.hash_next,n->hdr.ctx_prev,n->hdr.ctx_next, | ||
704 | n->hdr.order,sf_nb,sf_freq); | ||
705 | for(i=0;i<n->hdr.order;i++) Sym_Print(n->hdr.sym[i]); | ||
706 | printf(": "); | ||
707 | if (sf_max<=1) { | ||
708 | for(i=0;i<=sf_max;i++) SF_Print(n->hdr.sf.sf[i]); | ||
709 | } else { | ||
710 | n=&node_heap[n->hdr.sf.l.sf_next]; | ||
711 | i=0; | ||
712 | while (1) { | ||
713 | SF_Print(n->sf.sf[i]); | ||
714 | if (sf_max==0) break; | ||
715 | i++; | ||
716 | sf_max--; | ||
717 | if (i==NODE_SFNB) { | ||
718 | i=0; | ||
719 | n=&node_heap[n->sf.sf_next]; | ||
720 | } | ||
721 | } | ||
722 | } | ||
723 | printf("\n"); | ||
724 | } | ||
725 | |||
726 | |||
727 | /* | ||
728 | * Nombre total de contextes et nombre de contextes de longueur données. | ||
729 | * Utilisé pour les statistiques | ||
730 | */ | ||
731 | |||
732 | void ppm_worker::Context_Statistic(void) { | ||
733 | UINT i,p; | ||
734 | int tab[SYM_NB+1],tot,cnt; | ||
735 | |||
736 | for(i=0;i<=SYM_NB;i++) tab[i]=0; | ||
737 | tot=0; | ||
738 | |||
739 | p=ctx_first; | ||
740 | do { | ||
741 | cnt=node_heap[p].hdr.sf_max+1; | ||
742 | tab[cnt]++; | ||
743 | tot++; | ||
744 | p=node_heap[p].hdr.ctx_next; | ||
745 | } while (p!=ctx_last); | ||
746 | |||
747 | |||
748 | printf("Context_Statistic: "); | ||
749 | for(i=1;i<=SYM_NB;i++) { | ||
750 | printf("%d:%d (%0.2f%%),",i,tab[i],(float)tab[i]/(float)tot*100.0); | ||
751 | } | ||
752 | printf("\n"); | ||
753 | } | ||
754 | |||
755 | #endif | ||
756 | |||