1 /* This code is part of the tng compression routines.
2 *
3 * Written by Daniel Spangberg
4 * Copyright (c) 2010, 2013, The GROMACS development team.
5 *
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the Revised BSD License.
9 */
10
11
12 #include <stdio.h>
13 #include <stdlib.h>
14 #include <string.h>
15 #include "../../include/compression/warnmalloc.h"
16 #include "../../include/compression/tng_compress.h"
17 #include "../../include/compression/bwlzh.h"
18 #include "../../include/compression/dict.h"
19 #include "../../include/compression/vals16.h"
20 #include "../../include/compression/rle.h"
21 #include "../../include/compression/mtf.h"
22 #include "../../include/compression/bwt.h"
23 #include "../../include/compression/lz77.h"
24
25 #if 0
26 #define SHOWIT
27 #endif
28
29 #if 0
30 #define SHOWTEST
31 #endif
32
33 #define MAX_VALS_PER_BLOCK 200000
34
35 #if 1
36 #define PARTIAL_MTF3
37 #endif
38
39 #if 0
40 #define PARTIAL_MTF
41 #endif
42
bwlzh_get_buflen(const int nvals)43 int bwlzh_get_buflen(const int nvals)
44 {
45 return 132000+nvals*8+12*((nvals+MAX_VALS_PER_BLOCK)/MAX_VALS_PER_BLOCK);
46 }
47
48 #ifdef SHOWIT
printvals(const char * name,unsigned int * vals,const int nvals)49 static void printvals(const char *name, unsigned int *vals, const int nvals)
50 {
51 int i;
52 int nvalsmax=nvals;
53 if (nvalsmax>99)
54 nvalsmax=99;
55 #if 0
56 for (i=0; i<nvalsmax; i++)
57 fprintf(stderr,"%s %d %u\n",name,i,vals[i]);
58 #else
59 fprintf(stderr,"%s\n",name);
60 {
61 unsigned char *x=(unsigned char*)vals;
62 for (i=0; i<nvalsmax*4; i++)
63 fprintf(stderr,"%02x",(unsigned int)x[i]);
64 fprintf(stderr,"\n");
65 }
66 #endif
67
68 }
69 #endif
70
71
bwlzh_compress_gen(unsigned int * vals,const int nvals,unsigned char * output,int * output_len,const int enable_lz77,const int verbose)72 static void bwlzh_compress_gen(unsigned int *vals, const int nvals,
73 unsigned char *output, int *output_len,
74 const int enable_lz77,
75 const int verbose)
76 {
77 unsigned int *vals16;
78 int nvals16;
79 int huffdatalen;
80 int nhufflen[N_HUFFMAN_ALGO];
81 int huffalgo;
82 int bwt_index;
83 unsigned int *bwt=NULL;
84 #ifdef PARTIAL_MTF3
85 unsigned char *mtf3=NULL;
86 int imtfinner;
87 #endif
88 unsigned int *mtf=NULL;
89 unsigned int *rle=NULL;
90 unsigned int *offsets=NULL;
91 unsigned int *lens=NULL;
92 unsigned int *dict=warnmalloc(0x20004*sizeof *dict);
93 unsigned int *hist=warnmalloc(0x20004*sizeof *hist);
94 int nrle;
95 int noffsets;
96 int nlens;
97 unsigned char *bwlzhhuff=NULL;
98 int bwlzhhufflen;
99 int max_vals_per_block=MAX_VALS_PER_BLOCK;
100 int valsleft;
101 int thisvals;
102 int valstart;
103 int outdata=0;
104
105 unsigned int *tmpmem=warnmalloc(max_vals_per_block*18*sizeof *tmpmem);
106
107 #if 0
108 verbose=1;
109 #endif
110
111 bwlzhhuff=warnmalloc(Ptngc_comp_huff_buflen(3*nvals));
112 vals16=tmpmem;
113 bwt=tmpmem+max_vals_per_block*3;
114 mtf=tmpmem+max_vals_per_block*6;
115 rle=tmpmem+max_vals_per_block*9;
116 offsets=tmpmem+max_vals_per_block*12;
117 lens=tmpmem+max_vals_per_block*15;
118 #ifdef PARTIAL_MTF3
119 mtf3=warnmalloc(max_vals_per_block*3*3*sizeof *mtf3); /* 3 due to expansion of 32 bit to 16 bit, 3 due to up to 3 bytes
120 per 16 value. */
121 #endif
122 if (verbose)
123 {
124 fprintf(stderr,"Number of input values: %d\n",nvals);
125 }
126
127 /* Store the number of real values in the whole block. */
128 output[outdata++]=((unsigned int)nvals)&0xFFU;
129 output[outdata++]=(((unsigned int)nvals)>>8)&0xFFU;
130 output[outdata++]=(((unsigned int)nvals)>>16)&0xFFU;
131 output[outdata++]=(((unsigned int)nvals)>>24)&0xFFU;
132
133 valsleft=nvals;
134 valstart=0;
135 while (valsleft)
136 {
137 int reducealgo=1; /* Reduce algo is LZ77. */
138 if (!enable_lz77)
139 reducealgo=0;
140 thisvals=valsleft;
141 if (thisvals>max_vals_per_block)
142 thisvals=max_vals_per_block;
143 valsleft-=thisvals;
144 if (verbose)
145 fprintf(stderr,"Creating vals16 block from %d values.\n",thisvals);
146
147 #ifdef SHOWIT
148 printvals("vals",vals+valstart,thisvals);
149 #endif
150
151 Ptngc_comp_conv_to_vals16(vals+valstart,thisvals,vals16,&nvals16);
152 valstart+=thisvals;
153
154 #ifdef SHOWTEST
155 nvals16=99;
156 #endif
157
158 #ifdef SHOWIT
159 printvals("vals16",vals16,nvals16);
160 #endif
161
162 if (verbose)
163 {
164 fprintf(stderr,"Resulting vals16 values: %d\n",nvals16);
165 }
166 if (verbose)
167 {
168 fprintf(stderr,"BWT\n");
169 }
170 Ptngc_comp_to_bwt(vals16,nvals16,bwt,&bwt_index);
171
172 #ifdef SHOWIT
173 printvals("bwt",bwt,nvals16);
174 fprintf(stderr,"BWT INDEX is %d\n",bwt_index);
175 #endif
176
177 /* Store the number of real values in this block. */
178 output[outdata++]=((unsigned int)thisvals)&0xFFU;
179 output[outdata++]=(((unsigned int)thisvals)>>8)&0xFFU;
180 output[outdata++]=(((unsigned int)thisvals)>>16)&0xFFU;
181 output[outdata++]=(((unsigned int)thisvals)>>24)&0xFFU;
182
183 /* Store the number of nvals16 values in this block. */
184 output[outdata++]=((unsigned int)nvals16)&0xFFU;
185 output[outdata++]=(((unsigned int)nvals16)>>8)&0xFFU;
186 output[outdata++]=(((unsigned int)nvals16)>>16)&0xFFU;
187 output[outdata++]=(((unsigned int)nvals16)>>24)&0xFFU;
188
189 /* Store the BWT index. */
190 output[outdata++]=((unsigned int)bwt_index)&0xFFU;
191 output[outdata++]=(((unsigned int)bwt_index)>>8)&0xFFU;
192 output[outdata++]=(((unsigned int)bwt_index)>>16)&0xFFU;
193 output[outdata++]=(((unsigned int)bwt_index)>>24)&0xFFU;
194
195 if (verbose)
196 fprintf(stderr,"MTF\n");
197 #ifdef PARTIAL_MTF3
198 Ptngc_comp_conv_to_mtf_partial3(bwt,nvals16,
199 mtf3);
200 for (imtfinner=0; imtfinner<3; imtfinner++)
201 {
202 int i;
203 if (verbose)
204 fprintf(stderr,"Doing partial MTF: %d\n",imtfinner);
205 for (i=0; i<nvals16; i++)
206 mtf[i]=(unsigned int)mtf3[imtfinner*nvals16+i];
207 #else
208 #ifdef PARTIAL_MTF
209 Ptngc_comp_conv_to_mtf_partial(bwt,nvals16,mtf);
210 #else
211 int ndict;
212 Ptngc_comp_canonical_dict(dict,&ndict);
213 Ptngc_comp_conv_to_mtf(bwt,nvals16,
214 dict,ndict,mtf);
215 #endif
216
217 #ifdef SHOWIT
218 printvals("mtf",mtf,nvals16);
219 #endif
220 #endif
221
222
223 if (reducealgo==1)
224 {
225 if (verbose)
226 fprintf(stderr,"LZ77\n");
227 reducealgo=1;
228 Ptngc_comp_to_lz77(mtf,nvals16,rle,&nrle,lens,&nlens,offsets,&noffsets);
229
230 if (verbose)
231 {
232 fprintf(stderr,"Resulting LZ77 values: %d\n",nrle);
233 fprintf(stderr,"Resulting LZ77 lens: %d\n",nlens);
234 fprintf(stderr,"Resulting LZ77 offsets: %d\n",noffsets);
235 }
236 #ifdef SHOWIT
237 printvals("lz77 table",rle,nrle);
238 printvals("lz77 lengths",lens,nlens);
239 printvals("lz77 offsets",offsets,noffsets);
240 #endif
241
242 #if 0
243 if (noffsets)
244 {
245 unsigned int thist[0x20004];
246 unsigned int coarse[17]={0,};
247 int jj;
248 Ptngc_comp_make_dict_hist(lens,nlens,dict,&ndict,thist);
249 for (jj=0; jj<ndict; jj++)
250 fprintf(stderr,"%d %u %u L\n",jj,dict[jj],thist[jj]);
251
252 Ptngc_comp_make_dict_hist(offsets,noffsets,dict,&ndict,thist);
253 for (jj=0; jj<ndict; jj++)
254 {
255 unsigned int v=dict[jj];
256 int numbits=0;
257 while (v)
258 {
259 numbits++;
260 v>>=1;
261 }
262 coarse[numbits-1]+=thist[jj];
263 }
264 #if 1
265 for (jj=0; jj<ndict; jj++)
266 fprintf(stderr,"%d %u %u O\n",jj,dict[jj],thist[jj]);
267 #else
268 for (jj=0; jj<17; jj++)
269 fprintf(stderr,"%d %u\n",jj+1,coarse[jj]);
270 #endif
271
272 }
273 exit(0);
274 #endif
275
276 if (nlens<2)
277 reducealgo=0;
278
279 #ifdef SHOWTEST
280 reducealgo=1;
281 #endif
282 }
283 if (reducealgo==0)
284 {
285 if (verbose)
286 fprintf(stderr,"RLE\n");
287 /* Do RLE. For any repetetitive characters. */
288 Ptngc_comp_conv_to_rle(mtf,nvals16,rle,&nrle,1);
289
290 #ifdef SHOWIT
291 printvals("rle",rle,nrle);
292 #endif
293 if (verbose)
294 fprintf(stderr,"Resulting RLE values: %d\n",nrle);
295 }
296
297 /* reducealgo: RLE == 0, LZ77 == 1 */
298 output[outdata++]=reducealgo;
299
300 if (verbose)
301 fprintf(stderr,"Huffman\n");
302
303 huffalgo=-1;
304 Ptngc_comp_huff_compress_verbose(rle,nrle,bwlzhhuff,&bwlzhhufflen,&huffdatalen,nhufflen,&huffalgo,1);
305 #ifdef SHOWTEST
306 {
307 int i;
308 fprintf(stderr,"Huffman\n");
309 for (i=0; i<bwlzhhufflen; i++)
310 fprintf(stderr,"%02x",(unsigned int)bwlzhhuff[i]);
311 fprintf(stderr,"\n");
312 exit(0);
313 }
314 #endif
315 if (verbose)
316 {
317 int i;
318 fprintf(stderr,"Huffman data length is %d B.\n",huffdatalen);
319 for (i=0; i<N_HUFFMAN_ALGO; i++)
320 fprintf(stderr,"Huffman dictionary for algorithm %s is %d B.\n",Ptngc_comp_get_huff_algo_name(i),nhufflen[i]-huffdatalen);
321 fprintf(stderr,"Resulting algorithm: %s. Size=%d B\n",Ptngc_comp_get_huff_algo_name(huffalgo),bwlzhhufflen);
322 }
323
324 /* Store the number of huffman values in this block. */
325 output[outdata++]=((unsigned int)nrle)&0xFFU;
326 output[outdata++]=(((unsigned int)nrle)>>8)&0xFFU;
327 output[outdata++]=(((unsigned int)nrle)>>16)&0xFFU;
328 output[outdata++]=(((unsigned int)nrle)>>24)&0xFFU;
329
330 /* Store the size of the huffman block. */
331 output[outdata++]=((unsigned int)bwlzhhufflen)&0xFFU;
332 output[outdata++]=(((unsigned int)bwlzhhufflen)>>8)&0xFFU;
333 output[outdata++]=(((unsigned int)bwlzhhufflen)>>16)&0xFFU;
334 output[outdata++]=(((unsigned int)bwlzhhufflen)>>24)&0xFFU;
335
336 /* Store the huffman block. */
337 memcpy(output+outdata,bwlzhhuff,bwlzhhufflen);
338 outdata+=bwlzhhufflen;
339
340 if (reducealgo==1)
341 {
342 /* Store the number of values in this block. */
343 output[outdata++]=((unsigned int)noffsets)&0xFFU;
344 output[outdata++]=(((unsigned int)noffsets)>>8)&0xFFU;
345 output[outdata++]=(((unsigned int)noffsets)>>16)&0xFFU;
346 output[outdata++]=(((unsigned int)noffsets)>>24)&0xFFU;
347
348 if (noffsets>0)
349 {
350 if (verbose)
351 fprintf(stderr,"Huffman for offsets\n");
352
353 huffalgo=-1;
354 Ptngc_comp_huff_compress_verbose(offsets,noffsets,bwlzhhuff,&bwlzhhufflen,&huffdatalen,nhufflen,&huffalgo,1);
355 if (verbose)
356 {
357 int i;
358 fprintf(stderr,"Huffman data length is %d B.\n",huffdatalen);
359 for (i=0; i<N_HUFFMAN_ALGO; i++)
360 fprintf(stderr,"Huffman dictionary for algorithm %s is %d B.\n",Ptngc_comp_get_huff_algo_name(i),nhufflen[i]-huffdatalen);
361 fprintf(stderr,"Resulting algorithm: %s. Size=%d B\n",Ptngc_comp_get_huff_algo_name(huffalgo),bwlzhhufflen);
362 }
363
364 /* If huffman was bad for these offsets, just store the offsets as pairs of bytes. */
365 if (bwlzhhufflen<noffsets*2)
366 {
367 output[outdata++]=0;
368
369 /* Store the size of the huffman block. */
370 output[outdata++]=((unsigned int)bwlzhhufflen)&0xFFU;
371 output[outdata++]=(((unsigned int)bwlzhhufflen)>>8)&0xFFU;
372 output[outdata++]=(((unsigned int)bwlzhhufflen)>>16)&0xFFU;
373 output[outdata++]=(((unsigned int)bwlzhhufflen)>>24)&0xFFU;
374
375 /* Store the huffman block. */
376 memcpy(output+outdata,bwlzhhuff,bwlzhhufflen);
377 outdata+=bwlzhhufflen;
378 }
379 else
380 {
381 int i;
382 output[outdata++]=1;
383 for (i=0; i<noffsets; i++)
384 {
385 output[outdata++]=((unsigned int)offsets[i])&0xFFU;
386 output[outdata++]=(((unsigned int)offsets[i])>>8)&0xFFU;
387 }
388 if (verbose)
389 fprintf(stderr,"Store raw offsets: %d B\n",noffsets*2);
390 }
391 }
392
393 #if 0
394 {
395 int i,ndict;
396 FILE *f=fopen("len.dict","w");
397 Ptngc_comp_make_dict_hist(lens,nlens,dict,&ndict,hist);
398 for (i=0; i<ndict; i++)
399 fprintf(f,"%d %d %d\n",i,dict[i],hist[i]);
400 fclose(f);
401 f=fopen("off.dict","w");
402 Ptngc_comp_make_dict_hist(offsets,noffsets,dict,&ndict,hist);
403 for (i=0; i<ndict; i++)
404 fprintf(f,"%d %d %d\n",i,dict[i],hist[i]);
405 fclose(f);
406 f=fopen("len.time","w");
407 for (i=0; i<ndict; i++)
408 fprintf(f,"%d\n",lens[i]);
409 fclose(f);
410 f=fopen("off.time","w");
411 for (i=0; i<ndict; i++)
412 fprintf(f,"%d\n",offsets[i]);
413 fclose(f);
414 }
415 #endif
416
417 if (verbose)
418 fprintf(stderr,"Huffman for lengths\n");
419
420 huffalgo=-1;
421 Ptngc_comp_huff_compress_verbose(lens,nlens,bwlzhhuff,&bwlzhhufflen,&huffdatalen,nhufflen,&huffalgo,1);
422 if (verbose)
423 {
424 int i;
425 fprintf(stderr,"Huffman data length is %d B.\n",huffdatalen);
426 for (i=0; i<N_HUFFMAN_ALGO; i++)
427 fprintf(stderr,"Huffman dictionary for algorithm %s is %d B.\n",Ptngc_comp_get_huff_algo_name(i),nhufflen[i]-huffdatalen);
428 fprintf(stderr,"Resulting algorithm: %s. Size=%d B\n",Ptngc_comp_get_huff_algo_name(huffalgo),bwlzhhufflen);
429 }
430
431 /* Store the number of values in this block. */
432 output[outdata++]=((unsigned int)nlens)&0xFFU;
433 output[outdata++]=(((unsigned int)nlens)>>8)&0xFFU;
434 output[outdata++]=(((unsigned int)nlens)>>16)&0xFFU;
435 output[outdata++]=(((unsigned int)nlens)>>24)&0xFFU;
436
437 /* Store the size of the huffman block. */
438 output[outdata++]=((unsigned int)bwlzhhufflen)&0xFFU;
439 output[outdata++]=(((unsigned int)bwlzhhufflen)>>8)&0xFFU;
440 output[outdata++]=(((unsigned int)bwlzhhufflen)>>16)&0xFFU;
441 output[outdata++]=(((unsigned int)bwlzhhufflen)>>24)&0xFFU;
442
443 /* Store the huffman block. */
444 memcpy(output+outdata,bwlzhhuff,bwlzhhufflen);
445 outdata+=bwlzhhufflen;
446 }
447 #ifdef PARTIAL_MTF3
448 }
449 #endif
450 }
451
452 *output_len=outdata;
453 free(hist);
454 free(dict);
455 free(bwlzhhuff);
456 #ifdef PARTIAL_MTF3
457 free(mtf3);
458 #endif
459 free(tmpmem);
460 }
461
462
bwlzh_compress(unsigned int * vals,const int nvals,unsigned char * output,int * output_len)463 void DECLSPECDLLEXPORT bwlzh_compress(unsigned int *vals, const int nvals,
464 unsigned char *output, int *output_len)
465 {
466 bwlzh_compress_gen(vals,nvals,output,output_len,1,0);
467 }
468
bwlzh_compress_verbose(unsigned int * vals,const int nvals,unsigned char * output,int * output_len)469 void DECLSPECDLLEXPORT bwlzh_compress_verbose(unsigned int *vals, const int nvals,
470 unsigned char *output, int *output_len)
471 {
472 bwlzh_compress_gen(vals,nvals,output,output_len,1,1);
473 }
474
475
bwlzh_compress_no_lz77(unsigned int * vals,const int nvals,unsigned char * output,int * output_len)476 void DECLSPECDLLEXPORT bwlzh_compress_no_lz77(unsigned int *vals, const int nvals,
477 unsigned char *output, int *output_len)
478 {
479 bwlzh_compress_gen(vals,nvals,output,output_len,0,0);
480 }
481
bwlzh_compress_no_lz77_verbose(unsigned int * vals,const int nvals,unsigned char * output,int * output_len)482 void DECLSPECDLLEXPORT bwlzh_compress_no_lz77_verbose(unsigned int *vals, const int nvals,
483 unsigned char *output, int *output_len)
484 {
485 bwlzh_compress_gen(vals,nvals,output,output_len,0,1);
486 }
487
488
bwlzh_decompress_gen(unsigned char * input,const int nvals,unsigned int * vals,const int verbose)489 static void bwlzh_decompress_gen(unsigned char *input, const int nvals,
490 unsigned int *vals,
491 const int verbose)
492 {
493 unsigned int *vals16;
494 int nvals16;
495 int bwt_index;
496 unsigned int *bwt=NULL;
497 unsigned int *mtf=NULL;
498 #ifdef PARTIAL_MTF3
499 unsigned char *mtf3=NULL;
500 int imtfinner;
501 #endif
502 unsigned int *rle=NULL;
503 unsigned int *offsets=NULL;
504 unsigned int *lens=NULL;
505 unsigned int *dict=warnmalloc(0x20004*sizeof *dict);
506 unsigned int *hist=warnmalloc(0x20004*sizeof *hist);
507 int nrle, noffsets, nlens;
508 unsigned char *bwlzhhuff=NULL;
509 int bwlzhhufflen;
510 int max_vals_per_block=MAX_VALS_PER_BLOCK;
511 int valsleft;
512 int thisvals;
513 int valstart;
514 int inpdata=0;
515 int nvalsfile;
516
517 unsigned int *tmpmem=warnmalloc(max_vals_per_block*18*sizeof *tmpmem);
518
519 #if 0
520 verbose=1;
521 #endif
522
523
524 bwlzhhuff=warnmalloc(Ptngc_comp_huff_buflen(3*nvals));
525 vals16=tmpmem;
526 bwt=tmpmem+max_vals_per_block*3;
527 mtf=tmpmem+max_vals_per_block*6;
528 rle=tmpmem+max_vals_per_block*9;
529 offsets=tmpmem+max_vals_per_block*12;
530 lens=tmpmem+max_vals_per_block*15;
531 #ifdef PARTIAL_MTF3
532 mtf3=warnmalloc(max_vals_per_block*3*3*sizeof *mtf3); /* 3 due to expansion of 32 bit to 16 bit, 3 due to up to 3 bytes
533 per 16 value. */
534 #endif
535
536 if (verbose)
537 {
538 fprintf(stderr,"Number of input values: %d\n",nvals);
539 }
540
541 /* Read the number of real values in the whole block. */
542 nvalsfile=(int)(((unsigned int)input[inpdata]) |
543 (((unsigned int)input[inpdata+1])<<8) |
544 (((unsigned int)input[inpdata+2])<<16) |
545 (((unsigned int)input[inpdata+3])<<24));
546 inpdata+=4;
547
548 if (nvalsfile!=nvals)
549 {
550 fprintf(stderr,"BWLZH: The number of values found in the file is different from the number of values expected.\n");
551 exit(EXIT_FAILURE);
552 }
553
554 valsleft=nvals;
555 valstart=0;
556 while (valsleft)
557 {
558 int valsnew;
559 int reducealgo;
560 /* Read the number of real values in this block. */
561 thisvals=(int)(((unsigned int)input[inpdata]) |
562 (((unsigned int)input[inpdata+1])<<8) |
563 (((unsigned int)input[inpdata+2])<<16) |
564 (((unsigned int)input[inpdata+3])<<24));
565 inpdata+=4;
566
567 valsleft-=thisvals;
568
569 /* Read the number of nvals16 values in this block. */
570 nvals16=(int)(((unsigned int)input[inpdata]) |
571 (((unsigned int)input[inpdata+1])<<8) |
572 (((unsigned int)input[inpdata+2])<<16) |
573 (((unsigned int)input[inpdata+3])<<24));
574 inpdata+=4;
575
576 /* Read the BWT index. */
577 bwt_index=(int)(((unsigned int)input[inpdata]) |
578 (((unsigned int)input[inpdata+1])<<8) |
579 (((unsigned int)input[inpdata+2])<<16) |
580 (((unsigned int)input[inpdata+3])<<24));
581 inpdata+=4;
582
583 if (thisvals>max_vals_per_block)
584 {
585 /* More memory must be allocated for decompression. */
586 max_vals_per_block=thisvals;
587 if (verbose)
588 fprintf(stderr,"Allocating more memory: %d B\n",(int)(max_vals_per_block*15*sizeof *tmpmem));
589 tmpmem=warnrealloc(tmpmem,max_vals_per_block*18*sizeof *tmpmem);
590 vals16=tmpmem;
591 bwt=tmpmem+max_vals_per_block*3;
592 mtf=tmpmem+max_vals_per_block*6;
593 rle=tmpmem+max_vals_per_block*9;
594 offsets=tmpmem+max_vals_per_block*12;
595 lens=tmpmem+max_vals_per_block*15;
596 #ifdef PARTIAL_MTF3
597 mtf3=warnrealloc(mtf3,max_vals_per_block*3*3*sizeof *mtf3); /* 3 due to expansion of 32 bit to 16 bit, 3 due to up to 3 bytes
598 per 16 value. */
599 #endif
600 }
601
602 #ifdef PARTIAL_MTF3
603 for (imtfinner=0; imtfinner<3; imtfinner++)
604 {
605 int i;
606 if (verbose)
607 fprintf(stderr,"Doing partial MTF: %d\n",imtfinner);
608 #endif
609
610 reducealgo=(int)input[inpdata];
611 inpdata++;
612
613 /* Read the number of huffman values in this block. */
614 nrle=(int)(((unsigned int)input[inpdata]) |
615 (((unsigned int)input[inpdata+1])<<8) |
616 (((unsigned int)input[inpdata+2])<<16) |
617 (((unsigned int)input[inpdata+3])<<24));
618 inpdata+=4;
619
620 /* Read the size of the huffman block. */
621 bwlzhhufflen=(int)(((unsigned int)input[inpdata]) |
622 (((unsigned int)input[inpdata+1])<<8) |
623 (((unsigned int)input[inpdata+2])<<16) |
624 (((unsigned int)input[inpdata+3])<<24));
625 inpdata+=4;
626
627 if (verbose)
628 fprintf(stderr,"Decompressing huffman block of length %d.\n",bwlzhhufflen);
629 /* Decompress the huffman block. */
630 Ptngc_comp_huff_decompress(input+inpdata,bwlzhhufflen,rle);
631 inpdata+=bwlzhhufflen;
632
633 if (reducealgo==1) /* LZ77 */
634 {
635 int offstore;
636 /* Read the number of huffman values in this block. */
637 noffsets=(int)(((unsigned int)input[inpdata]) |
638 (((unsigned int)input[inpdata+1])<<8) |
639 (((unsigned int)input[inpdata+2])<<16) |
640 (((unsigned int)input[inpdata+3])<<24));
641 inpdata+=4;
642
643 if (noffsets>0)
644 {
645 /* How are the offsets stored? */
646 offstore=(int)input[inpdata++];
647 if (offstore==0)
648 {
649 /* Read the size of the huffman block. */
650 bwlzhhufflen=(int)(((unsigned int)input[inpdata]) |
651 (((unsigned int)input[inpdata+1])<<8) |
652 (((unsigned int)input[inpdata+2])<<16) |
653 (((unsigned int)input[inpdata+3])<<24));
654 inpdata+=4;
655
656 if (verbose)
657 fprintf(stderr,"Decompressing offset huffman block.\n");
658
659 /* Decompress the huffman block. */
660 Ptngc_comp_huff_decompress(input+inpdata,bwlzhhufflen,offsets);
661 inpdata+=bwlzhhufflen;
662 }
663 else
664 {
665 int i;
666 if (verbose)
667 fprintf(stderr,"Reading offset block.\n");
668 for (i=0; i<noffsets; i++)
669 {
670 offsets[i]=(int)(((unsigned int)input[inpdata]) |
671 (((unsigned int)input[inpdata+1])<<8));
672 inpdata+=2;
673 }
674 }
675 }
676 #if 0
677 {
678 int i;
679 for (i=0; i<nrle; i++)
680 fprintf(stderr,"RLE %d: %d\n",i,rle[i]);
681 for (i=0; i<noffsets; i++)
682 fprintf(stderr,"OFFSET %d: %d\n",i,offsets[i]);
683 }
684 #endif
685
686
687 /* Read the number of huffman values in this block. */
688 nlens=(int)(((unsigned int)input[inpdata]) |
689 (((unsigned int)input[inpdata+1])<<8) |
690 (((unsigned int)input[inpdata+2])<<16) |
691 (((unsigned int)input[inpdata+3])<<24));
692 inpdata+=4;
693
694 /* Read the size of the huffman block. */
695 bwlzhhufflen=(int)(((unsigned int)input[inpdata]) |
696 (((unsigned int)input[inpdata+1])<<8) |
697 (((unsigned int)input[inpdata+2])<<16) |
698 (((unsigned int)input[inpdata+3])<<24));
699 inpdata+=4;
700
701 if (verbose)
702 fprintf(stderr,"Decompressing length huffman block.\n");
703
704 /* Decompress the huffman block. */
705 Ptngc_comp_huff_decompress(input+inpdata,bwlzhhufflen,lens);
706 inpdata+=bwlzhhufflen;
707
708 if (verbose)
709 fprintf(stderr,"Decompressing LZ77.\n");
710
711 Ptngc_comp_from_lz77(rle,nrle,lens,nlens,offsets,noffsets,mtf,nvals16);
712 }
713 else if (reducealgo==0) /* RLE */
714 {
715 #ifdef SHOWIT
716 printvals("rle",rle,nrle);
717 #endif
718
719 if (verbose)
720 fprintf(stderr,"Decompressing rle block.\n");
721 Ptngc_comp_conv_from_rle(rle,mtf,nvals16);
722 }
723
724 #ifdef PARTIAL_MTF3
725 for (i=0; i<nvals16; i++)
726 mtf3[imtfinner*nvals16+i]=(unsigned char)mtf[i];
727 }
728 #else
729 #ifdef SHOWIT
730 printvals("mtf",mtf,nvals16);
731 #endif
732
733 #endif
734
735
736 if (verbose)
737 fprintf(stderr,"Inverse MTF.\n");
738 #ifdef PARTIAL_MTF3
739 Ptngc_comp_conv_from_mtf_partial3(mtf3,nvals16,bwt);
740 #else
741 #ifdef PARTIAL_MTF
742 Ptngc_comp_conv_from_mtf_partial(mtf,nvals16,bwt);
743 #else
744 int ndict;
745 Ptngc_comp_canonical_dict(dict,&ndict);
746 Ptngc_comp_conv_from_mtf(mtf,nvals16,dict,ndict,bwt);
747 #endif
748 #endif
749
750 #ifdef SHOWIT
751 printvals("bwt",bwt,nvals16);
752 fprintf(stderr,"BWT INDEX is %d\n",bwt_index);
753 #endif
754
755 if (verbose)
756 fprintf(stderr,"Inverse BWT.\n");
757 Ptngc_comp_from_bwt(bwt,nvals16,bwt_index,vals16);
758
759 #ifdef SHOWIT
760 printvals("vals16",vals16,nvals16);
761 #endif
762
763 if (verbose)
764 fprintf(stderr,"Decompressing vals16 block.\n");
765 Ptngc_comp_conv_from_vals16(vals16,nvals16,vals+valstart,&valsnew);
766
767 #ifdef SHOWIT
768 printvals("vals",vals+valstart,thisvals);
769 #endif
770
771 if (valsnew!=thisvals)
772 {
773 fprintf(stderr,"BWLZH: Block contained different number of values than expected.\n");
774 exit(EXIT_FAILURE);
775 }
776 valstart+=thisvals;
777 }
778 free(hist);
779 free(dict);
780 free(bwlzhhuff);
781 #ifdef PARTIAL_MTF3
782 free(mtf3);
783 #endif
784 free(tmpmem);
785 }
786
787
bwlzh_decompress(unsigned char * input,const int nvals,unsigned int * vals)788 void DECLSPECDLLEXPORT bwlzh_decompress(unsigned char *input, const int nvals,
789 unsigned int *vals)
790 {
791 bwlzh_decompress_gen(input,nvals,vals,0);
792 }
793
bwlzh_decompress_verbose(unsigned char * input,const int nvals,unsigned int * vals)794 void DECLSPECDLLEXPORT bwlzh_decompress_verbose(unsigned char *input, const int nvals,
795 unsigned int *vals)
796 {
797 bwlzh_decompress_gen(input,nvals,vals,1);
798 }
799
800