archival/libarchive/bz/huffman.c

   1 /*
   2  * bzip2 is written by Julian Seward <jseward@bzip.org>.
   3  * Adapted for busybox by Denys Vlasenko <vda.linux@googlemail.com>.
   4  * See README and LICENSE files in this directory for more information.
   5  */
   6
   7 /*-------------------------------------------------------------*/
   8 /*--- Huffman coding low-level stuff                        ---*/
   9 /*---                                             huffman.c ---*/
  10 /*-------------------------------------------------------------*/
  11
  12 /* ------------------------------------------------------------------
  13 This file is part of bzip2/libbzip2, a program and library for
  14 lossless, block-sorting data compression.
  15
  16 bzip2/libbzip2 version 1.0.4 of 20 December 2006
  17 Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
  18
  19 Please read the WARNING, DISCLAIMER and PATENTS sections in the
  20 README file.
  21
  22 This program is released under the terms of the license contained
  23 in the file LICENSE.
  24 ------------------------------------------------------------------ */
  25
  26 /* #include "bzlib_private.h" */
  27
  28 /*---------------------------------------------------*/
  29 #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
  30 #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
  31 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
  32
  33 #define ADDWEIGHTS(zw1,zw2) \
  34         (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
  35         (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
  36
  37 #define UPHEAP(z) \
  38 { \
  39         int32_t zz, tmp; \
  40         zz = z; \
  41         tmp = heap[zz]; \
  42         while (weight[tmp] < weight[heap[zz >> 1]]) { \
  43                 heap[zz] = heap[zz >> 1]; \
  44                 zz >>= 1; \
  45         } \
  46         heap[zz] = tmp; \
  47 }
  48
  49
  50 /* 90 bytes, 0.3% of overall compress speed */
  51 #if CONFIG_BZIP2_FEATURE_SPEED >= 1
  52
  53 /* macro works better than inline (gcc 4.2.1) */
  54 #define DOWNHEAP1(heap, weight, Heap) \
  55 { \
  56         int32_t zz, yy, tmp; \
  57         zz = 1; \
  58         tmp = heap[zz]; \
  59         while (1) { \
  60                 yy = zz << 1; \
  61                 if (yy > nHeap) \
  62                         break; \
  63                 if (yy < nHeap \
  64                  && weight[heap[yy+1]] < weight[heap[yy]]) \
  65                         yy++; \
  66                 if (weight[tmp] < weight[heap[yy]]) \
  67                         break; \
  68                 heap[zz] = heap[yy]; \
  69                 zz = yy; \
  70         } \
  71         heap[zz] = tmp; \
  72 }
  73
  74 #else
  75
  76 static
  77 void DOWNHEAP1(int32_t *heap, int32_t *weight, int32_t nHeap)
  78 {
  79         int32_t zz, yy, tmp;
  80         zz = 1;
  81         tmp = heap[zz];
  82         while (1) {
  83                 yy = zz << 1;
  84                 if (yy > nHeap)
  85                         break;
  86                 if (yy < nHeap
  87                  && weight[heap[yy + 1]] < weight[heap[yy]])
  88                         yy++;
  89                 if (weight[tmp] < weight[heap[yy]])
  90                         break;
  91                 heap[zz] = heap[yy];
  92                 zz = yy;
  93         }
  94         heap[zz] = tmp;
  95 }
  96
  97 #endif
  98
  99 /*---------------------------------------------------*/
 100 static
 101 void BZ2_hbMakeCodeLengths(EState *s,
 102                 uint8_t *len,
 103                 int32_t *freq,
 104                 int32_t alphaSize,
 105                 int32_t maxLen)
 106 {
 107         /*
 108          * Nodes and heap entries run from 1.  Entry 0
 109          * for both the heap and nodes is a sentinel.
 110          */
 111         int32_t nNodes, nHeap, n1, n2, i, j, k;
 112         Bool  tooLong;
 113
 114         /* bbox: moved to EState to save stack
 115         int32_t heap  [BZ_MAX_ALPHA_SIZE + 2];
 116         int32_t weight[BZ_MAX_ALPHA_SIZE * 2];
 117         int32_t parent[BZ_MAX_ALPHA_SIZE * 2];
 118         */
 119 #define heap   (s->BZ2_hbMakeCodeLengths__heap)
 120 #define weight (s->BZ2_hbMakeCodeLengths__weight)
 121 #define parent (s->BZ2_hbMakeCodeLengths__parent)
 122
 123         for (i = 0; i < alphaSize; i++)
 124                 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
 125
 126         while (1) {
 127                 nNodes = alphaSize;
 128                 nHeap = 0;
 129
 130                 heap[0] = 0;
 131                 weight[0] = 0;
 132                 parent[0] = -2;
 133
 134                 for (i = 1; i <= alphaSize; i++) {
 135                         parent[i] = -1;
 136                         nHeap++;
 137                         heap[nHeap] = i;
 138                         UPHEAP(nHeap);
 139                 }
 140
 141                 AssertH(nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001);
 142
 143                 while (nHeap > 1) {
 144                         n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP1(heap, weight, nHeap);
 145                         n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP1(heap, weight, nHeap);
 146                         nNodes++;
 147                         parent[n1] = parent[n2] = nNodes;
 148                         weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
 149                         parent[nNodes] = -1;
 150                         nHeap++;
 151                         heap[nHeap] = nNodes;
 152                         UPHEAP(nHeap);
 153                 }
 154
 155                 AssertH(nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002);
 156
 157                 tooLong = False;
 158                 for (i = 1; i <= alphaSize; i++) {
 159                         j = 0;
 160                         k = i;
 161                         while (parent[k] >= 0) {
 162                                 k = parent[k];
 163                                 j++;
 164                         }
 165                         len[i-1] = j;
 166                         if (j > maxLen)
 167                                 tooLong = True;
 168                 }
 169
 170                 if (!tooLong)
 171                         break;
 172
 173                 /* 17 Oct 04: keep-going condition for the following loop used
 174                 to be 'i < alphaSize', which missed the last element,
 175                 theoretically leading to the possibility of the compressor
 176                 looping.  However, this count-scaling step is only needed if
 177                 one of the generated Huffman code words is longer than
 178                 maxLen, which up to and including version 1.0.2 was 20 bits,
 179                 which is extremely unlikely.  In version 1.0.3 maxLen was
 180                 changed to 17 bits, which has minimal effect on compression
 181                 ratio, but does mean this scaling step is used from time to
 182                 time, enough to verify that it works.
 183
 184                 This means that bzip2-1.0.3 and later will only produce
 185                 Huffman codes with a maximum length of 17 bits.  However, in
 186                 order to preserve backwards compatibility with bitstreams
 187                 produced by versions pre-1.0.3, the decompressor must still
 188                 handle lengths of up to 20. */
 189
 190                 for (i = 1; i <= alphaSize; i++) {
 191                         j = weight[i] >> 8;
 192                         /* bbox: yes, it is a signed division.
 193                          * don't replace with shift! */
 194                         j = 1 + (j / 2);
 195                         weight[i] = j << 8;
 196                 }
 197         }
 198 #undef heap
 199 #undef weight
 200 #undef parent
 201 }
 202
 203
 204 /*---------------------------------------------------*/
 205 static
 206 void BZ2_hbAssignCodes(int32_t *code,
 207                 uint8_t *length,
 208                 int32_t minLen,
 209                 int32_t maxLen,
 210                 int32_t alphaSize)
 211 {
 212         int32_t n, vec, i;
 213
 214         vec = 0;
 215         for (n = minLen; n <= maxLen; n++) {
 216                 for (i = 0; i < alphaSize; i++) {
 217                         if (length[i] == n) {
 218                                 code[i] = vec;
 219                                 vec++;
 220                         };
 221                 }
 222                 vec <<= 1;
 223         }
 224 }
 225
 226
 227 /*-------------------------------------------------------------*/
 228 /*--- end                                         huffman.c ---*/
 229 /*-------------------------------------------------------------*/