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

Contents of /public/pc/tools/osdk/main/common/lz_pack.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1035 - (show annotations)
Sun Dec 15 15:35:39 2013 UTC (5 years, 11 months ago) by dbug
File size: 11918 byte(s)
FloppyBuilder 0.9
- Added the 'SetCompressionMode' command. Possible parameters are 'None' (default value) and 'FilePack'
The lzpack.cpp file moved out from FilePack and is now in Common, this means it will be usable in other projects (Like PictConv)
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