src/external/tng_io/src/compression/huffmem.c

   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 "../../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"
  21
  22 int Ptngc_comp_huff_buflen(int nvals)
  23 {
  24   return 132000+nvals*8;
  25 }
  26
  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,
  30                                 int *huffdatalen,
  31                                 int *huffman_lengths,int *chosen_algo,
  32                                 int isvals16)
  33 {
  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);
  46   int i;
  47   int ndict,ndict1,ndict2;
  48   int nhuff,nhuffdict,nhuffdictunpack;
  49   int nhuff1,nhuffdict1,nhuffdictunpack1;
  50   int nhuffrle,nhuff2,nhuffdict2,nhuffdictunpack2;
  51   int nvals16;
  52
  53   /* Do I need to convert to vals16? */
  54   if (!isvals16)
  55   {
  56     vals16=warnmalloc(nvals*3*sizeof *vals16);
  57     Ptngc_comp_conv_to_vals16(vals,nvals,vals16,&nvals16);
  58     nvals=nvals16;
  59     vals=vals16;
  60   }
  61   else
  62     nvals16=nvals;
  63
  64   /* Determine probabilities. */
  65   Ptngc_comp_make_dict_hist(vals,nvals,dict,&ndict,hist);
  66
  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,
  69                        huffman+14,&nhuff,
  70                        huffdict,&nhuffdict,
  71                        huffdictunpack,&nhuffdictunpack);
  72   *huffdatalen=nhuff;
  73
  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) */
  79
  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,
  84                        dict,ndict1,hist,
  85                        huffman1,&nhuff1,
  86                        huffdict1,&nhuffdict1,
  87                        huffdictunpack1,&nhuffdictunpack1);
  88   huffman_lengths[1]=nhuff+nhuff1+nhuffdict1+1*2+3*4+3+3+3+3+3;
  89
  90   /* ... and rle + huffman coding ... (algorithm 2) Pack any repetetitive patterns. */
  91   Ptngc_comp_conv_to_rle(huffdictunpack,nhuffdictunpack,
  92                    huffdictrle,&nhuffrle,1);
  93
  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,
  98                        dict,ndict2,hist,
  99                        huffman2,&nhuff2,
 100                        huffdict2,&nhuffdict2,
 101                        huffdictunpack2,&nhuffdictunpack2);
 102   huffman_lengths[2]=nhuff+nhuff2+nhuffdict2+1*2+3*4+3+3+3+3+3+3;
 103
 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])))))
 108     {
 109       *chosen_algo=0;
 110       *huffman_len=huffman_lengths[0];
 111       huffman[0]=isvals16;
 112       huffman[1]=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];
 133     }
 134   else if ((*chosen_algo==1) || ((*chosen_algo==-1) &&
 135                                  ((huffman_lengths[1]<huffman_lengths[2]))))
 136     {
 137       *chosen_algo=1;
 138       *huffman_len=huffman_lengths[1];
 139       huffman[0]=isvals16;
 140       huffman[1]=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];
 172     }
 173   else
 174     {
 175       *chosen_algo=2;
 176       *huffman_len=huffman_lengths[2];
 177       huffman[0]=isvals16;
 178       huffman[1]=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];
 213     }
 214   if (!isvals16)
 215     free(vals16);
 216
 217   free(huffdictunpack2);
 218   free(huffdict2);
 219   free(huffman2);
 220   free(huffdictrle);
 221   free(huffdictunpack1);
 222   free(huffdict1);
 223   free(huffman1);
 224   free(huffdictunpack);
 225   free(huffdict);
 226   free(hist);
 227   free(dict);
 228 }
 229
 230 void Ptngc_comp_huff_compress(unsigned int *vals, int nvals,
 231                         unsigned char *huffman, int *huffman_len)
 232 {
 233   int huffman_lengths[N_HUFFMAN_ALGO];
 234   int algo=-1;
 235   int huffdatalen;
 236   Ptngc_comp_huff_compress_verbose(vals,nvals,huffman,huffman_len,&huffdatalen,
 237                              huffman_lengths,&algo,0);
 238 }
 239
 240 void Ptngc_comp_huff_decompress(unsigned char *huffman, int huffman_len,
 241                           unsigned int *vals)
 242 {
 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));
 261   (void)huffman_len;
 262   if (!isvals16)
 263     vals16=warnmalloc(nvals16*sizeof *vals16);
 264   else
 265     {
 266       vals16=vals;
 267       nvals16=nvals;
 268     }
 269   if (algo==0)
 270     {
 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);
 276     }
 277   else if (algo==1)
 278     {
 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);
 300     }
 301   else if (algo==2)
 302     {
 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,
 322                              nhuffrle,ndict2,
 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);
 329       free(huffdictrle);
 330       free(huffdictunpack);
 331     }
 332
 333   /* Do I need to convert from vals16? */
 334   if (!isvals16)
 335   {
 336     int nvalsx;
 337     Ptngc_comp_conv_from_vals16(vals16,nvals16,vals,&nvalsx);
 338     free(vals16);
 339   }
 340 }
 341
 342 static char *huff_algo_names[N_HUFFMAN_ALGO]=
 343   {
 344     "Huffman (dict=raw)",
 345     "Huffman (dict=Huffman)",
 346     "Huffman (dict=RLE+Huffman)"
 347   };
 348
 349 char *Ptngc_comp_get_huff_algo_name(int algo)
 350 {
 351   if (algo<0)
 352     return NULL;
 353   else if (algo>=N_HUFFMAN_ALGO)
 354     return NULL;
 355   return huff_algo_names[algo];
 356 }