/[projet1]/public/pc/tools/osdk/main/filepack/sources/lz_pack.cpp
Defence Force logotype

Contents of /public/pc/tools/osdk/main/filepack/sources/lz_pack.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 406 - (show annotations)
Mon Sep 20 18:59:17 2010 UTC (9 years, 1 month ago) by dbug
File size: 11918 byte(s)
Updated the OSDK with the latest code of most of the tools.

1
2
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <memory.h>
6
7
8
9 #define max(a,b) ((a)>(b)?(a):(b))
10
11
12
13 // ne doit jamais depasser 16 les deux !!!
14 //4
15 #define _LZ77_NB_BIT_SIZE 4
16 #define _LZ77_NB_BIT_OFFSET 12
17 #define _LZ77_MAX_SIZE (1<<_LZ77_NB_BIT_SIZE) // 1<<4 -> 16
18 #define _LZ77_MAX_OFFSET ((1<<_LZ77_NB_BIT_OFFSET)+1) // 1<<12 -> 4096+1 = 4097
19 #define _LZ77_ROOT (_LZ77_MAX_OFFSET)
20
21 #define _LZ77_SEARCH_SIZE (_LZ77_MAX_SIZE+1)
22
23
24 typedef struct
25 {
26 short smaller_child;
27 short larger_child;
28 short parent;
29 short branch; // par quel branche du parent est il venue
30 }LZ77_TREE;
31
32
33 LZ77_TREE BigTree[_LZ77_MAX_OFFSET+2];
34
35 unsigned char gLZ77_XorMask=0;
36
37 long LZ77_Compress(void* buf_src_void,void *buf_dest_void,long size_buf_src)
38 {
39 unsigned char *buf_src =(unsigned char*)buf_src_void;
40 unsigned char *buf_dest=(unsigned char*)buf_dest_void;
41 LZ77_TREE *tree,*real_tree,*current_tree,*del_tree;
42
43 unsigned char *ptr_decoding_mask;
44 unsigned char *ptr_search_src;
45
46 unsigned char andvalue;
47
48 long nb_rec;
49 long size;
50 long delta_value;
51 long offset_src;
52
53 short i,k;
54 short best_match;
55 short best_node;
56 short current_node;
57 short num_tree;
58 short search_index;
59 short branch_value;
60
61
62
63 real_tree=BigTree;
64
65 // ruse pour eviter les test kan les child sont … -1
66 // mon tableau commence … +1 donc ce ki sera patch‚ en 0
67 // rien … faire !!
68 tree=real_tree+1;
69
70
71 // init tree
72 memset(tree,-1,(_LZ77_MAX_OFFSET+1)*sizeof(LZ77_TREE));
73
74 offset_src=0;
75
76 nb_rec=1;
77
78 size=0;
79 andvalue=0;
80
81 while (offset_src+nb_rec-1<size_buf_src)
82 {
83 //
84 // Reload encoding type mask
85 //
86 if (!andvalue)
87 {
88 andvalue=1;
89
90 ptr_decoding_mask=buf_dest++;
91 *ptr_decoding_mask=0; // No match
92 size++;
93 }
94
95 // delete string de 'num_index'
96 // en recherchant ds tree celui ki a 'num_index+last advance'
97 while (nb_rec>0)
98 {
99 i=(short)(offset_src % _LZ77_MAX_OFFSET);
100 num_tree=i;
101 current_tree=&tree[i];
102
103 if (current_tree->parent>=0)
104 {
105 // supprime ca
106 if ( (current_tree->smaller_child<0) || (current_tree->larger_child<0) )
107 { // facile a faire
108 branch_value=current_tree->larger_child;
109 if (branch_value>=0)
110 {
111 tree[branch_value].parent=current_tree->parent;
112 tree[branch_value].branch=current_tree->branch;
113 }
114 else
115 {
116 branch_value=current_tree->smaller_child;
117 if (branch_value>=0)
118 {
119 tree[branch_value].parent=current_tree->parent;
120 tree[branch_value].branch=current_tree->branch;
121 }
122 else // no child
123 {
124 branch_value=-1;
125 }
126 }
127 }
128 else
129 {
130
131 // supprime noeud ki a 2 fils
132 // d'ou ruse :
133 // au choix rechercher le plus grand du fils 'larger'
134 // ou recherche le plus grand du fils 'smaller'
135 // de toute facon ca revient au meme.... ( ce qui est logique d'ailleur)
136
137 branch_value=current_tree->smaller_child;
138 del_tree=&tree[branch_value];
139
140 if (del_tree->larger_child<0)
141 current_tree->smaller_child=del_tree->smaller_child;
142 else
143 {
144 while (del_tree->larger_child>=0)
145 {
146 branch_value=del_tree->larger_child;
147 del_tree=&tree[branch_value];
148 }
149
150 // supprime del
151 tree[del_tree->parent].larger_child=del_tree->smaller_child;
152 }
153
154 tree[del_tree->smaller_child].parent=del_tree->parent;
155 tree[del_tree->smaller_child].branch=del_tree->branch;
156
157 //remplacement
158 del_tree->smaller_child=current_tree->smaller_child;
159 del_tree->larger_child =current_tree->larger_child;
160
161 tree[del_tree->smaller_child].parent=branch_value;
162 tree[del_tree->larger_child].parent =branch_value;
163
164 del_tree->parent=current_tree->parent;
165 del_tree->branch=current_tree->branch;
166 }
167
168 // update chez parent de i
169 if (!current_tree->branch) tree[current_tree->parent].smaller_child=branch_value;
170 else tree[current_tree->parent].larger_child =branch_value;
171 }
172
173 current_tree->larger_child =-1;
174 current_tree->smaller_child=-1;
175
176 // donc on va ecrire ds tree[numtree]
177 current_node=tree[_LZ77_ROOT].smaller_child; // init with root
178
179
180 if (current_node<0) // remplis racine de l'arbre...
181 {
182 tree[num_tree].parent=_LZ77_ROOT;
183 tree[num_tree].branch=0; // weil immer smaller branch for root
184 tree[_LZ77_ROOT].smaller_child=num_tree;
185 best_match=0;
186 }
187 else
188 {
189 best_match=2;
190 best_node=0;
191 while (1)
192 {
193 i=num_tree-current_node; // offset
194 if (i<0) i+=(_LZ77_MAX_OFFSET);
195
196 //k= _SearchSequence(src-i,src,_LZ77_MAX_SIZE+2);
197
198 ptr_search_src=buf_src-i;
199
200 search_index=0;
201 while (ptr_search_src[search_index] == buf_src[search_index])
202 {
203 if (search_index==_LZ77_SEARCH_SIZE) break;
204 search_index++;
205 }
206
207 delta_value=ptr_search_src[search_index] - buf_src[search_index];
208 //k=_LZ77_SEARCH_SIZE-search_index; // 17-
209
210
211 if ( (search_index==_LZ77_SEARCH_SIZE) && (!delta_value) )
212 {
213 //
214 // 1) On a trouvé une chaine de la taille maximale
215 // possible pour l'encoding...
216 // On stocke cette entrée, et on se casse.
217 // On ne trouvera jamais mieux !
218 //
219 tree[num_tree]=tree[current_node];
220
221 // on s'occupe du parent
222 if (!tree[num_tree].branch) tree[tree[num_tree].parent].smaller_child=num_tree;
223 else tree[tree[num_tree].parent].larger_child =num_tree;
224
225 // et des fils
226 tree[tree[num_tree].smaller_child].parent=num_tree;
227 tree[tree[num_tree].larger_child].parent =num_tree;
228
229 // on efface l'ancien noeud proprement...
230 tree[current_node].parent=-1;
231
232 best_match=_LZ77_MAX_SIZE+2; // 18 octets à copier=maximum possible avec l'encodage 4:12
233 best_node =current_node;
234 break;
235 }
236 else
237 {
238 //
239 // 2) On a pas trouvé une chaine de taille maximale
240 //
241 k=_LZ77_SEARCH_SIZE-(_LZ77_SEARCH_SIZE-search_index);
242 if (k>best_match)
243 {
244 best_match=k;
245 best_node=current_node;
246 }
247
248 if (delta_value>=0)
249 { // suivre larger
250 k=tree[current_node].larger_child;
251 if (k<0)
252 {
253 tree[num_tree].parent =current_node;
254 tree[current_node].larger_child =num_tree;
255 tree[num_tree].branch =-1; // comming from larger
256 break;
257 }
258 else current_node=k;
259
260 }
261 else // suivre smaller
262 {
263 k=tree[current_node].smaller_child;
264 if (k<0)
265 {
266 tree[num_tree].parent =current_node;
267 tree[current_node].smaller_child=num_tree;
268 tree[num_tree].branch =0; // comming from smaller
269 break;
270 }
271 else current_node=k;
272 }
273 }
274
275 }
276 }
277
278 nb_rec--;
279 if (nb_rec>0)
280 {
281 buf_src++;
282 offset_src++;
283 }
284 }
285
286 // bindage de taille
287 if (size>=size_buf_src-2)
288 {
289 return -1;
290 }
291
292 nb_rec=best_match;
293 //value>>=1;
294 if ( (nb_rec>2) && (offset_src+nb_rec<=size_buf_src) ) // 2 match 0 bits win ....
295 {
296 unsigned int value_short;
297
298 //
299 // Copy with offset
300 //
301 i=(offset_src % (_LZ77_MAX_OFFSET))-best_node;
302 if (i<0) i+=(_LZ77_MAX_OFFSET);
303
304 value_short=((nb_rec-3)<<(16-_LZ77_NB_BIT_SIZE)) | (i-1);
305
306 *buf_dest++=(unsigned char)(value_short & 255);
307 *buf_dest++=(unsigned char)(value_short>>8);
308 size+=2;
309 if (gLZ77_XorMask) *ptr_decoding_mask|=andvalue;
310 }
311 else
312 {
313 //
314 // Just put the byte, without compression
315 // and put '1' in the encoding mask
316 //
317 if (!gLZ77_XorMask) *ptr_decoding_mask|=andvalue;
318
319 *buf_dest++=*buf_src;
320 size++;
321
322 nb_rec=1;
323 }
324
325 offset_src++;
326 buf_src++;
327
328 andvalue<<=1;
329 }
330 return size;
331 //return ((size+3)&(~3));
332 }
333
334
335 void LZ77_UnCompress(void* buf_src_void,void* buf_dest_void, long size)
336 {
337 unsigned char *buf_src =(unsigned char*)buf_src_void;
338 unsigned char *buf_dest=(unsigned char*)buf_dest_void;
339
340 unsigned char value;
341 unsigned char andvalue;
342 long offset,nb;
343
344 andvalue=0;
345 while (size>0)
346 {
347 //
348 // Reload encoding type mask
349 //
350 if (!andvalue)
351 {
352 andvalue=1;
353 value=(*buf_src++);
354 }
355 if ((value^gLZ77_XorMask) & andvalue)
356 {
357 //
358 // Copy 1 unsigned char
359 //
360 *buf_dest++=*buf_src++;
361 size--;
362 }
363 else
364 {
365 //
366 // Copy with offset
367 //
368 // At this point, the source pointer points to a two byte
369 // value that actually contains a 4 bits counter, and a
370 // 12 bit offset to point back into the depacked stream.
371 // The counter is in the 4 high order bits.
372 //
373 offset = buf_src[0]; // Read 16 bits non alligned datas...
374 offset|=(buf_src[1]&0x0F)<<8;
375 offset+=1;
376
377 nb =(buf_src[1]>>4)+3;
378
379 buf_src+=2;
380
381 size-=nb;
382 while (nb>0)
383 {
384 *buf_dest++=*(buf_dest-offset);
385 nb--;
386 }
387 }
388 andvalue<<=1;
389 }
390 }
391
392
393 long LZ77_ComputeDelta(unsigned char *buf_comp,long size_uncomp,long size_comp)
394 {
395 unsigned char *buf_src =(unsigned char*)buf_comp;
396 unsigned char *buf_dest=(unsigned char*)buf_comp+size_comp-size_uncomp;
397
398 unsigned char value;
399 unsigned char andvalue;
400 long offset,nb;
401
402 long max_delta_space;
403
404 max_delta_space=0;
405 andvalue=0;
406 while (size_uncomp>0)
407 {
408 //
409 // Reload encoding type mask
410 //
411 if (!andvalue)
412 {
413 andvalue=1;
414 value=(*buf_src++);
415 }
416 if ((value^gLZ77_XorMask) & andvalue)
417 {
418 //
419 // Copy 1 unsigned char
420 //
421 //*buf_dest++=*buf_src++;
422 if (buf_dest>=buf_src)
423 {
424 max_delta_space=max(max_delta_space,buf_dest-buf_src);
425 }
426 buf_dest++;
427 buf_src++;
428
429 size_uncomp--;
430 }
431 else
432 {
433 //
434 // Copy with offset
435 //
436 // At this point, the source pointer points to a two byte
437 // value that actually contains a 4 bits counter, and a
438 // 12 bit offset to point back into the depacked stream.
439 // The counter is in the 4 high order bits.
440 //
441 offset = buf_src[0]; // Read 16 bits non alligned datas...
442 offset|=(buf_src[1]&0x0F)<<8;
443 offset+=1;
444
445 nb =(buf_src[1]>>4)+3;
446
447 buf_src+=2;
448
449 size_uncomp-=nb;
450 while (nb>0)
451 {
452 //*buf_dest++=*(buf_dest-offset);
453 if (buf_dest>=buf_src)
454 {
455 max_delta_space=max(max_delta_space,buf_dest-buf_src);
456 }
457 buf_dest++;
458
459 nb--;
460 }
461 }
462 andvalue<<=1;
463 }
464 return max_delta_space;
465 }
466
467
468
469
470 long LZ77_ComputeDeltaOld(unsigned char *buf_comp,long size_uncomp,long size_comp)
471 {
472 unsigned char value;
473 unsigned char andvalue;
474 long offset,nb;
475 long offset_comp;
476 long offset_uncomp;
477 long max_delta_space;
478
479
480 offset_comp=size_uncomp-size_comp;
481 offset_uncomp=0;
482 max_delta_space=0;
483
484 andvalue=0;
485 while (size_uncomp>0)
486 {
487 //
488 // Reload encoding type mask
489 //
490 if (!andvalue)
491 {
492 andvalue=1;
493 value=*buf_comp++;
494 offset_comp++;
495 }
496 if (value & andvalue)
497 {
498 //
499 // Copy 1 unsigned char
500 //
501 buf_comp++;
502 offset_uncomp++;
503 if (offset_comp<=offset_uncomp)
504 {
505 max_delta_space=max(offset_uncomp-offset_comp+1,max_delta_space);
506 }
507 offset_comp++;
508 size_uncomp--;
509 }
510 else
511 {
512 //
513 // Copy with offset
514 //
515 offset =*buf_comp++; // Read 16 bits non alligned datas...
516 offset|=(*buf_comp++)<<8;
517
518 nb=(offset & (0xff >> (8-_LZ77_NB_BIT_SIZE)) )+2+1;
519 offset=((offset>>_LZ77_NB_BIT_SIZE) & (0xffff >> (16-_LZ77_NB_BIT_OFFSET))) +1;
520
521 size_uncomp-=nb;
522 offset_uncomp+=nb;
523 if (offset_comp<=offset_uncomp)
524 {
525 max_delta_space=max(offset_uncomp-offset_comp+1,max_delta_space);
526 }
527 offset_comp+=2;
528
529 }
530 andvalue<<=1;
531 }
532 return((max_delta_space+3)&(~3)); // padd to four.
533 }
534
535
536

  ViewVC Help
Powered by ViewVC 1.1.26