swcsa/utils/huffDec.h

   1
   2 // implements canonical Huffman !! Just for decoding when symbols were sorted before creating huffman
   3
   4 #ifndef HUFFDECINCLUDED
   5 #define HUFFDECINCLUDED
   6
   7 #include "basics.h"
   8 #define SORTED 1
   9 #define UNSORTED 0
  10
  11 typedef struct
  12    { //uint lim;
  13      uint depth; // max symbol length
  14      uint *num;  // first pos of each length (dec), number of each length (enc)
  15      uint *fst;  // first code (numeric) of each length (dec)
  16    } THuffDec;
  17
  18
  19 //typedef struct
  20 //   { uint max,lim;   // maximum symbol (0..max), same excluding zero freqs
  21 //     uint depth; // max symbol length
  22 //     union
  23 //       { uint *spos; // symbol positions after sorting by decr freq (enc)
  24 //       uint *symb; // symbols sorted by freq (dec)
  25 //       } s;
  26 //     uint *num;  // first pos of each length (dec), number of each length (enc)
  27 //     uint *fst;  // first code (numeric) of each length (dec)
  28 //     uint total; // total length to achieve, in bits
  29 //   } THuff;
  30
  31
  32         // Decodes *symb using H, over stream[ptr...lim] (ptr and lim are
  33         // bit positions of stream). Returns the new ptr.
  34 int decodeHuffDec (THuffDec *H, uint *symb, uint *stream, uint ptr);
  35
  36         // Writes H in file f
  37 void saveHuffDec (THuffDec H, FILE *f);
  38
  39         // Frees H
  40 void freeHuffDec (THuffDec H);
  41
  42         // the number of bytes used by HuffDecman struct.
  43 uint sizeHuffDec (THuffDec H);
  44
  45         // Loads H from file f, prepared for encoding or decoding depending
  46         // on enc
  47
  48 THuffDec loadHuffDec (FILE *f, int enc);
  49
  50
  51 //Decodes a code starting in position ptr from stream. Returns the ranking in the
  52 //vector of symbols.
  53 #define decodeHuffDecMacro(H, symb, stream, ptr) \
  54    { uint pos; \
  55      int d; \
  56      pos = 0; \
  57      d = 0; \
  58      while (pos < H->fst[d]) \
  59         { pos = (pos << 1) | bitget(stream,ptr); \
  60           ptr++; d++; \
  61         } \
  62      fflush(stdout); \
  63      symb = H->num[d]+pos-H->fst[d]; \
  64    }
  65
  66 #endif
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83 //#define decodeHuffDecMacroVALIDWORDS decodeHuffDecMacro
  84
  85 //Decodes a code starting in position ptr from stream. Returns the ranking in the
  86 //vector of symbols.
  87 //Saves space, as the last level for num[] and fst[] are not needed.
  88 //             at expenses of an extra-IF (the last line).
  89 #define decodeHuffDecMacroVALIDWORDS(H, symb, stream, ptr, depth) \
  90    { uint pos; \
  91      int d; \
  92      pos = 0; \
  93      d = 0; \
  94      while ((pos < H->fst[d])  && (d< depth)) \
  95         { pos = (pos << 1) | bitget(stream,ptr); \
  96           ptr++; d++; \
  97         } \
  98      fflush(stdout); \
  99      symb = (depth==d) ? pos : H->num[d]+pos-H->fst[d]; \
 100    }
 101
 102
 103 //Decodes a code starting in position ptr from stream. Returns the ranking in the
 104 //vector of symbols.
 105 #define decodeHuffDecMacroVariantWordxx(fst,num, symb, stream, ptr, depth) \
 106    { uint pos; \
 107      int d; \
 108      pos = 0; \
 109      d = 0; \
 110      while ((pos < fst[d])  && (d< depth)) \
 111         { pos = (pos << 1) | bitget(stream,ptr); \
 112           ptr++; d++; \
 113         } \
 114      fflush(stdout); \
 115      symb = (depth==d) ? pos : num[d] + pos - fst[d]; \
 116    }
 117
 118
 119
 120 //Decodes a code starting in position ptr from stream. Returns the ranking in the
 121 //vector of symbols.
 122 // #define decodeHuffDecMacroVariantWord(fst,symb, stream, ptr, depth) \
 123 //    { uint pos; \
 124 //      int d; \
 125 //      pos = 0; \
 126 //      d = 0; \
 127 //      while ((d< depth) && (pos < fst[d*2])  ) \
 128 //         { pos = (pos << 1) | bitget(stream,ptr); \
 129 //           ptr++; d++; \
 130 //         } \
 131 //      symb = (depth==d) ? pos : fst[d*2+1] + pos - fst[d*2]; \
 132 //    }
 133
 134
 135 /** Decodes a variant of a word from a stream of compressed bits, starting in the ptr-th bit
 136         The starting bucket in fstnum is "offbucket" [fst|num|fst|num|fst|num]
 137         */
 138 #define decodeHuffDecMacroVariantWordPos(fstnum, offbucket, symb, stream, ptr, depth) \
 139    { uint pos; \
 140      register uint d; \
 141      pos = 0; \
 142      d = 0; \
 143      while ((d< depth) && (pos < fstnum[offbucket + d*2])  ) \
 144         { pos = (pos << 1) | bitget(stream,ptr); \
 145           ptr++; d++; \
 146         } \
 147      symb = (depth==d) ? pos : fstnum[offbucket+d*2+1] + pos - fstnum[offbucket+d*2]; \
 148    }
 149 #define decodeHuffDecMacroVariantWordPos2(HV, symb, stream, ptr, idCanonical) \
 150    { uint pos; \
 151      register uint d; \
 152      uint *offfstnum = HV.offsetNumAndFst; \
 153      uint *fstnum = HV.zoneNumFst; \
 154          register uint offbucket = offfstnum[idCanonical]; \
 155          register uint depth = (offfstnum[idCanonical+1] - offbucket)/2; \
 156      pos = 0; \
 157      d = 0; \
 158      while ((d< depth) && (pos < fstnum[offbucket + d*2])  ) \
 159         { pos = (pos << 1) | bitget(stream,ptr); \
 160           ptr++; d++; \
 161         } \
 162      symb = (depth==d) ? pos : fstnum[offbucket+d*2+1] + pos - fstnum[offbucket+d*2]; \
 163    }
 164
 165
 166      //fst[0] = zone[0  ];
 167          //fst[1] = zone[1*2];
 168          //fst[i] = zone[i*2];
 169
 170      //num[0] = zone[0  +1];
 171          //num[1] = zone[1*2+1];
 172          //num[i] = zone[i*2+1];
 173
 174
 175
 176 //#define decodeHuffDecMacroVariantWordPos2bits(HV, symb, stream, ptr, idCanonical) \
 177 //   { uint pos; \
 178 //     register uint d; \
 179 //     uint sizeBuckbits= HV.sizeBuckbits; \
 180 //     uint dirbElemSize = HV.dirbElemSize; \
 181 //     uint sizeFstbits = HV.sizeFstbits; \
 182 //     uint sizeNumbits = HV.sizeNumbits; \
 183 //     uint *dirb = HV.Dirb; \
 184 //     uint *zonefstnum = HV.zoneMem; \
 185 //       register uint offbucket; \
 186 //       offbucket = bitread (dirb, idCanonical*dirbElemSize, dirbElemSize); \
 187 //       register uint depth; \
 188 //       depth = bitread (dirb, (idCanonical+1)*dirbElemSize, dirbElemSize); \
 189 //       depth = (depth - offbucket)/sizeBuckbits; \
 190 //     pos = 0; \
 191 //     d = 0; \
 192 //     register uint currfst; \
 193 //     currfst = bitread (zonefstnum, (offbucket + d*sizeBuckbits), sizeFstbits); \
 194 //     while ((pos < currfst)  ) \
 195 //        { pos = (pos << 1) | bitget(stream,ptr); \
 196 //          ptr++; d++; \
 197 //          if (d<depth) \
 198 //              currfst = bitread (zonefstnum, (offbucket + d*sizeBuckbits), sizeFstbits); \
 199 //          else break; \
 200 //        } \
 201 //    if (depth==d) \
 202 //      symb=pos; \
 203 //    else { \
 204 //      uint currNum; \
 205 //      currNum = bitread (zonefstnum, (offbucket + d*sizeBuckbits+ sizeFstbits), sizeNumbits); \
 206 //     symb = currNum + pos - currfst; \
 207 //    } \
 208 //  }
 209
 210
 211
 212 // int decodeHuffDecVariantWord (uint *fst , uint *symb, uint *stream, uint ptr, uint depth);
 213
 214