1 /* This code is part of the tng compression routines.
3 * Written by Daniel Spangberg
4 * Copyright (c) 2010, 2013, The GROMACS development team.
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the Revised BSD License.
14 #include "../../include/compression/warnmalloc.h"
15 #include "../../include/compression/tng_compress.h"
16 #include "../../include/compression/bwlzh.h"
17 #include "../../include/compression/huffman.h"
18 #include "../../include/compression/dict.h"
19 #include "../../include/compression/rle.h"
20 #include "../../include/compression/vals16.h"
22 int Ptngc_comp_huff_buflen(const int nvals
)
24 return 132000+nvals
*8;
27 /* the value pointed to by chosen_algo should be sent as -1 for autodetect. */
28 void Ptngc_comp_huff_compress_verbose(unsigned int *vals
, int nvals
,
29 unsigned char *huffman
, int *huffman_len
,
31 int *huffman_lengths
,int *chosen_algo
,
34 unsigned int *dict
=warnmalloc(0x20005*sizeof *dict
);
35 unsigned int *hist
=warnmalloc(0x20005*sizeof *hist
);
36 unsigned int *vals16
=NULL
;
37 unsigned char *huffdict
=warnmalloc(0x20005*sizeof *huffdict
);
38 unsigned int *huffdictunpack
=warnmalloc(0x20005*sizeof *huffdictunpack
);
39 unsigned char *huffman1
=warnmalloc(2*0x20005*sizeof *huffman1
);
40 unsigned char *huffdict1
=warnmalloc(0x20005*sizeof *huffdict1
);
41 unsigned int *huffdictunpack1
=warnmalloc(0x20005*sizeof *huffdictunpack1
);
42 unsigned int *huffdictrle
=warnmalloc((3*0x20005+3)*sizeof *huffdictrle
);
43 unsigned char *huffman2
=warnmalloc(6*0x20005*sizeof *huffman2
);
44 unsigned char *huffdict2
=warnmalloc(0x20005*sizeof *huffdict2
);
45 unsigned int *huffdictunpack2
=warnmalloc(0x20005*sizeof *huffdictunpack2
);
47 int ndict
,ndict1
,ndict2
;
48 int nhuff
,nhuffdict
,nhuffdictunpack
;
49 int nhuff1
,nhuffdict1
,nhuffdictunpack1
;
50 int nhuffrle
,nhuff2
,nhuffdict2
,nhuffdictunpack2
;
53 /* Do I need to convert to vals16? */
56 vals16
=warnmalloc(nvals
*3*sizeof *vals16
);
57 Ptngc_comp_conv_to_vals16(vals
,nvals
,vals16
,&nvals16
);
64 /* Determine probabilities. */
65 Ptngc_comp_make_dict_hist(vals
,nvals
,dict
,&ndict
,hist
);
67 /* First compress the data using huffman coding (place it ready for output at 14 (code for algorithm+length etc.). */
68 Ptngc_comp_conv_to_huffman(vals
,nvals
,dict
,ndict
,hist
,
71 huffdictunpack
,&nhuffdictunpack
);
74 /* Algorithm 0 stores the huffman dictionary directly (+ a code for
75 the algorithm) + lengths of the huffman buffer (4) and the huffman dictionary (3). */
76 huffman_lengths
[0]=nhuff
+nhuffdict
+1*2+3*4+3+3;
77 /* Next we try to compress the huffman dictionary using huffman
78 coding ... (algorithm 1) */
80 /* Determine probabilities. */
81 Ptngc_comp_make_dict_hist(huffdictunpack
,nhuffdictunpack
,dict
,&ndict1
,hist
);
82 /* Pack huffman dictionary */
83 Ptngc_comp_conv_to_huffman(huffdictunpack
,nhuffdictunpack
,
86 huffdict1
,&nhuffdict1
,
87 huffdictunpack1
,&nhuffdictunpack1
);
88 huffman_lengths
[1]=nhuff
+nhuff1
+nhuffdict1
+1*2+3*4+3+3+3+3+3;
90 /* ... and rle + huffman coding ... (algorithm 2) Pack any repetetitive patterns. */
91 Ptngc_comp_conv_to_rle(huffdictunpack
,nhuffdictunpack
,
92 huffdictrle
,&nhuffrle
,1);
94 /* Determine probabilities. */
95 Ptngc_comp_make_dict_hist(huffdictrle
,nhuffrle
,dict
,&ndict2
,hist
);
96 /* Pack huffman dictionary */
97 Ptngc_comp_conv_to_huffman(huffdictrle
,nhuffrle
,
100 huffdict2
,&nhuffdict2
,
101 huffdictunpack2
,&nhuffdictunpack2
);
102 huffman_lengths
[2]=nhuff
+nhuff2
+nhuffdict2
+1*2+3*4+3+3+3+3+3+3;
104 /* Choose the best algorithm and output the data. */
105 if ((*chosen_algo
==0) || ((*chosen_algo
==-1) &&
106 (((huffman_lengths
[0]<huffman_lengths
[1]) &&
107 (huffman_lengths
[0]<huffman_lengths
[2])))))
110 *huffman_len
=huffman_lengths
[0];
113 huffman
[2]=((unsigned int)nvals16
)&0xFFU
;
114 huffman
[3]=(((unsigned int)nvals16
)>>8)&0xFFU
;
115 huffman
[4]=(((unsigned int)nvals16
)>>16)&0xFFU
;
116 huffman
[5]=(((unsigned int)nvals16
)>>24)&0xFFU
;
117 huffman
[6]=((unsigned int)nvals
)&0xFFU
;
118 huffman
[7]=(((unsigned int)nvals
)>>8)&0xFFU
;
119 huffman
[8]=(((unsigned int)nvals
)>>16)&0xFFU
;
120 huffman
[9]=(((unsigned int)nvals
)>>24)&0xFFU
;
121 huffman
[10]=((unsigned int)nhuff
)&0xFFU
;
122 huffman
[11]=(((unsigned int)nhuff
)>>8)&0xFFU
;
123 huffman
[12]=(((unsigned int)nhuff
)>>16)&0xFFU
;
124 huffman
[13]=(((unsigned int)nhuff
)>>24)&0xFFU
;
125 huffman
[14+nhuff
]=((unsigned int)nhuffdict
)&0xFFU
;
126 huffman
[15+nhuff
]=(((unsigned int)nhuffdict
)>>8)&0xFFU
;
127 huffman
[16+nhuff
]=(((unsigned int)nhuffdict
)>>16)&0xFFU
;
128 huffman
[17+nhuff
]=((unsigned int)ndict
)&0xFFU
;
129 huffman
[18+nhuff
]=(((unsigned int)ndict
)>>8)&0xFFU
;
130 huffman
[19+nhuff
]=(((unsigned int)ndict
)>>16)&0xFFU
;
131 for (i
=0; i
<nhuffdict
; i
++)
132 huffman
[20+nhuff
+i
]=huffdict
[i
];
134 else if ((*chosen_algo
==1) || ((*chosen_algo
==-1) &&
135 ((huffman_lengths
[1]<huffman_lengths
[2]))))
138 *huffman_len
=huffman_lengths
[1];
141 huffman
[2]=((unsigned int)nvals16
)&0xFFU
;
142 huffman
[3]=(((unsigned int)nvals16
)>>8)&0xFFU
;
143 huffman
[4]=(((unsigned int)nvals16
)>>16)&0xFFU
;
144 huffman
[5]=(((unsigned int)nvals16
)>>24)&0xFFU
;
145 huffman
[6]=((unsigned int)nvals
)&0xFFU
;
146 huffman
[7]=(((unsigned int)nvals
)>>8)&0xFFU
;
147 huffman
[8]=(((unsigned int)nvals
)>>16)&0xFFU
;
148 huffman
[9]=(((unsigned int)nvals
)>>24)&0xFFU
;
149 huffman
[10]=((unsigned int)nhuff
)&0xFFU
;
150 huffman
[11]=(((unsigned int)nhuff
)>>8)&0xFFU
;
151 huffman
[12]=(((unsigned int)nhuff
)>>16)&0xFFU
;
152 huffman
[13]=(((unsigned int)nhuff
)>>24)&0xFFU
;
153 huffman
[14+nhuff
]=((unsigned int)nhuffdictunpack
)&0xFFU
;
154 huffman
[15+nhuff
]=(((unsigned int)nhuffdictunpack
)>>8)&0xFFU
;
155 huffman
[16+nhuff
]=(((unsigned int)nhuffdictunpack
)>>16)&0xFFU
;
156 huffman
[17+nhuff
]=((unsigned int)ndict
)&0xFFU
;
157 huffman
[18+nhuff
]=(((unsigned int)ndict
)>>8)&0xFFU
;
158 huffman
[19+nhuff
]=(((unsigned int)ndict
)>>16)&0xFFU
;
159 huffman
[20+nhuff
]=((unsigned int)nhuff1
)&0xFFU
;
160 huffman
[21+nhuff
]=(((unsigned int)nhuff1
)>>8)&0xFFU
;
161 huffman
[22+nhuff
]=(((unsigned int)nhuff1
)>>16)&0xFFU
;
162 huffman
[23+nhuff
]=((unsigned int)nhuffdict1
)&0xFFU
;
163 huffman
[24+nhuff
]=(((unsigned int)nhuffdict1
)>>8)&0xFFU
;
164 huffman
[25+nhuff
]=(((unsigned int)nhuffdict1
)>>16)&0xFFU
;
165 huffman
[26+nhuff
]=((unsigned int)ndict1
)&0xFFU
;
166 huffman
[27+nhuff
]=(((unsigned int)ndict1
)>>8)&0xFFU
;
167 huffman
[28+nhuff
]=(((unsigned int)ndict1
)>>16)&0xFFU
;
168 for (i
=0; i
<nhuff1
; i
++)
169 huffman
[29+nhuff
+i
]=huffman1
[i
];
170 for (i
=0; i
<nhuffdict1
; i
++)
171 huffman
[29+nhuff
+nhuff1
+i
]=huffdict1
[i
];
176 *huffman_len
=huffman_lengths
[2];
179 huffman
[2]=((unsigned int)nvals16
)&0xFFU
;
180 huffman
[3]=(((unsigned int)nvals16
)>>8)&0xFFU
;
181 huffman
[4]=(((unsigned int)nvals16
)>>16)&0xFFU
;
182 huffman
[5]=(((unsigned int)nvals16
)>>24)&0xFFU
;
183 huffman
[6]=((unsigned int)nvals
)&0xFFU
;
184 huffman
[7]=(((unsigned int)nvals
)>>8)&0xFFU
;
185 huffman
[8]=(((unsigned int)nvals
)>>16)&0xFFU
;
186 huffman
[9]=(((unsigned int)nvals
)>>24)&0xFFU
;
187 huffman
[10]=((unsigned int)nhuff
)&0xFFU
;
188 huffman
[11]=(((unsigned int)nhuff
)>>8)&0xFFU
;
189 huffman
[12]=(((unsigned int)nhuff
)>>16)&0xFFU
;
190 huffman
[13]=(((unsigned int)nhuff
)>>24)&0xFFU
;
191 huffman
[14+nhuff
]=((unsigned int)nhuffdictunpack
)&0xFFU
;
192 huffman
[15+nhuff
]=(((unsigned int)nhuffdictunpack
)>>8)&0xFFU
;
193 huffman
[16+nhuff
]=(((unsigned int)nhuffdictunpack
)>>16)&0xFFU
;
194 huffman
[17+nhuff
]=((unsigned int)ndict
)&0xFFU
;
195 huffman
[18+nhuff
]=(((unsigned int)ndict
)>>8)&0xFFU
;
196 huffman
[19+nhuff
]=(((unsigned int)ndict
)>>16)&0xFFU
;
197 huffman
[20+nhuff
]=((unsigned int)nhuffrle
)&0xFFU
;
198 huffman
[21+nhuff
]=(((unsigned int)nhuffrle
)>>8)&0xFFU
;
199 huffman
[22+nhuff
]=(((unsigned int)nhuffrle
)>>16)&0xFFU
;
200 huffman
[23+nhuff
]=((unsigned int)nhuff2
)&0xFFU
;
201 huffman
[24+nhuff
]=(((unsigned int)nhuff2
)>>8)&0xFFU
;
202 huffman
[25+nhuff
]=(((unsigned int)nhuff2
)>>16)&0xFFU
;
203 huffman
[26+nhuff
]=((unsigned int)nhuffdict2
)&0xFFU
;
204 huffman
[27+nhuff
]=(((unsigned int)nhuffdict2
)>>8)&0xFFU
;
205 huffman
[28+nhuff
]=(((unsigned int)nhuffdict2
)>>16)&0xFFU
;
206 huffman
[29+nhuff
]=((unsigned int)ndict2
)&0xFFU
;
207 huffman
[30+nhuff
]=(((unsigned int)ndict2
)>>8)&0xFFU
;
208 huffman
[31+nhuff
]=(((unsigned int)ndict2
)>>16)&0xFFU
;
209 for (i
=0; i
<nhuff2
; i
++)
210 huffman
[32+nhuff
+i
]=huffman2
[i
];
211 for (i
=0; i
<nhuffdict2
; i
++)
212 huffman
[32+nhuff
+nhuff2
+i
]=huffdict2
[i
];
217 free(huffdictunpack2
);
221 free(huffdictunpack1
);
224 free(huffdictunpack
);
230 void Ptngc_comp_huff_compress(unsigned int *vals
, const int nvals
,
231 unsigned char *huffman
, int *huffman_len
)
233 int huffman_lengths
[N_HUFFMAN_ALGO
];
236 Ptngc_comp_huff_compress_verbose(vals
,nvals
,huffman
,huffman_len
,&huffdatalen
,
237 huffman_lengths
,&algo
,0);
240 void Ptngc_comp_huff_decompress(unsigned char *huffman
, const int huffman_len
,
243 int isvals16
=(int)huffman
[0];
244 unsigned int *vals16
=NULL
;
245 int algo
=(int)huffman
[1];
246 int nvals16
=(int)((unsigned int)huffman
[2]|
247 (((unsigned int)huffman
[3])<<8)|
248 (((unsigned int)huffman
[4])<<16)|
249 (((unsigned int)huffman
[5])<<24));
250 int nvals
=(int)((unsigned int)huffman
[6]|
251 (((unsigned int)huffman
[7])<<8)|
252 (((unsigned int)huffman
[8])<<16)|
253 (((unsigned int)huffman
[9])<<24));
254 int nhuff
=(int)((unsigned int)huffman
[10]|
255 (((unsigned int)huffman
[11])<<8)|
256 (((unsigned int)huffman
[12])<<16)|
257 (((unsigned int)huffman
[13])<<24));
258 int ndict
=(int)((unsigned int)huffman
[17+nhuff
]|
259 (((unsigned int)huffman
[18+nhuff
])<<8)|
260 (((unsigned int)huffman
[19+nhuff
])<<16));
263 vals16
=warnmalloc(nvals16
*sizeof *vals16
);
271 int nhuffdict
=(int)((unsigned int)huffman
[14+nhuff
]|
272 (((unsigned int)huffman
[15+nhuff
])<<8)|
273 (((unsigned int)huffman
[16+nhuff
])<<16));
274 Ptngc_comp_conv_from_huffman(huffman
+14,vals16
,nvals16
,ndict
,
275 huffman
+20+nhuff
,nhuffdict
,NULL
,0);
279 unsigned int *huffdictunpack
=warnmalloc(0x20005*sizeof *huffdictunpack
);
280 /* First the dictionary needs to be uncompressed. */
281 int nhuffdictunpack
=(int)((unsigned int)huffman
[14+nhuff
]|
282 (((unsigned int)huffman
[15+nhuff
])<<8)|
283 (((unsigned int)huffman
[16+nhuff
])<<16));
284 int nhuff1
=(int)((unsigned int)huffman
[20+nhuff
]|
285 (((unsigned int)huffman
[21+nhuff
])<<8)|
286 (((unsigned int)huffman
[22+nhuff
])<<16));
287 int nhuffdict1
=(int)((unsigned int)huffman
[23+nhuff
]|
288 (((unsigned int)huffman
[24+nhuff
])<<8)|
289 (((unsigned int)huffman
[25+nhuff
])<<16));
290 int ndict1
=(int)((unsigned int)huffman
[26+nhuff
]|
291 (((unsigned int)huffman
[27+nhuff
])<<8)|
292 (((unsigned int)huffman
[28+nhuff
])<<16));
293 Ptngc_comp_conv_from_huffman(huffman
+29+nhuff
,huffdictunpack
,
294 nhuffdictunpack
,ndict1
,
295 huffman
+29+nhuff
+nhuff1
,nhuffdict1
,NULL
,0);
296 /* Then decompress the "real" data. */
297 Ptngc_comp_conv_from_huffman(huffman
+14,vals16
,nvals16
,ndict
,
298 NULL
,0,huffdictunpack
,nhuffdictunpack
);
299 free(huffdictunpack
);
303 unsigned int *huffdictunpack
=warnmalloc(0x20005*sizeof *huffdictunpack
);
304 unsigned int *huffdictrle
=warnmalloc((3*0x20005+3)*sizeof *huffdictrle
);
305 /* First the dictionary needs to be uncompressed. */
306 int nhuffdictunpack
=(int)((unsigned int)huffman
[14+nhuff
]|
307 (((unsigned int)huffman
[15+nhuff
])<<8)|
308 (((unsigned int)huffman
[16+nhuff
])<<16));
309 int nhuffrle
=(int)((unsigned int)huffman
[20+nhuff
]|
310 (((unsigned int)huffman
[21+nhuff
])<<8)|
311 (((unsigned int)huffman
[22+nhuff
])<<16));
312 int nhuff2
=(int)((unsigned int)huffman
[23+nhuff
]|
313 (((unsigned int)huffman
[24+nhuff
])<<8)|
314 (((unsigned int)huffman
[25+nhuff
])<<16));
315 int nhuffdict2
=(int)((unsigned int)huffman
[26+nhuff
]|
316 (((unsigned int)huffman
[27+nhuff
])<<8)|
317 (((unsigned int)huffman
[28+nhuff
])<<16));
318 int ndict2
=(int)((unsigned int)huffman
[29+nhuff
]|
319 (((unsigned int)huffman
[30+nhuff
])<<8)|
320 (((unsigned int)huffman
[31+nhuff
])<<16));
321 Ptngc_comp_conv_from_huffman(huffman
+32+nhuff
,huffdictrle
,
323 huffman
+32+nhuff
+nhuff2
,nhuffdict2
,NULL
,0);
324 /* Then uncompress the rle data */
325 Ptngc_comp_conv_from_rle(huffdictrle
,huffdictunpack
,nhuffdictunpack
);
326 /* Then decompress the "real" data. */
327 Ptngc_comp_conv_from_huffman(huffman
+14,vals16
,nvals16
,ndict
,
328 NULL
,0,huffdictunpack
,nhuffdictunpack
);
330 free(huffdictunpack
);
333 /* Do I need to convert from vals16? */
337 Ptngc_comp_conv_from_vals16(vals16
,nvals16
,vals
,&nvalsx
);
342 static char *huff_algo_names
[N_HUFFMAN_ALGO
]=
344 "Huffman (dict=raw)",
345 "Huffman (dict=Huffman)",
346 "Huffman (dict=RLE+Huffman)"
349 char *Ptngc_comp_get_huff_algo_name(const int algo
)
353 else if (algo
>=N_HUFFMAN_ALGO
)
355 return huff_algo_names
[algo
];