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 #include <stdint.h>
  28
  29 /*---------------------------------------------------*/
  30 #define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
  31 #define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
  32 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
  33
  34 #define ADDWEIGHTS(zw1,zw2) \
  35         (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
  36         (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
  37
  38 #define UPHEAP(z) \
  39 { \
  40         int32_t zz, tmp; \
  41         zz = z; \
  42         tmp = heap[zz]; \
  43         while (weight[tmp] < weight[heap[zz >> 1]]) { \
  44                 heap[zz] = heap[zz >> 1]; \
  45                 zz >>= 1; \
  46         } \
  47         heap[zz] = tmp; \
  48 }
  49
  50
  51 /* 90 bytes, 0.3% of overall compress speed */
  52 #if BZIP2_SPEED >= 1
  53
  54 /* macro works better than inline (gcc 4.2.1) */
  55 #define BZ_DOWNHEAP1(heap, weight, Heap) \
  56 { \
  57         int32_t zz, yy, tmp; \
  58         zz = 1; \
  59         tmp = heap[zz]; \
  60         while (1) { \
  61                 yy = zz << 1; \
  62                 if (yy > nHeap) \
  63                         break; \
  64                 if (yy < nHeap \
  65                  && weight[heap[yy+1]] < weight[heap[yy]]) \
  66                         yy++; \
  67                 if (weight[tmp] < weight[heap[yy]]) \
  68                         break; \
  69                 heap[zz] = heap[yy]; \
  70                 zz = yy; \
  71         } \
  72         heap[zz] = tmp; \
  73 }
  74
  75 #else
  76
  77 BB_STATIC
  78 void BB_DOWNHEAP1(int32_t *heap, int32_t *weight, int32_t nHeap)
  79 {
  80         int32_t zz, yy, tmp;
  81         zz = 1;
  82         tmp = heap[zz];
  83         while (1) {
  84                 yy = zz << 1;
  85                 if (yy > nHeap)
  86                         break;
  87                 if (yy < nHeap
  88                  && weight[heap[yy + 1]] < weight[heap[yy]])
  89                         yy++;
  90                 if (weight[tmp] < weight[heap[yy]])
  91                         break;
  92                 heap[zz] = heap[yy];
  93                 zz = yy;
  94         }
  95         heap[zz] = tmp;
  96 }
  97
  98 #endif
  99
 100 /*---------------------------------------------------*/
 101 BB_STATIC
 102 void BZ2_hbMakeCodeLengths(struct bz_EState *s,
 103                 uint8_t *len,
 104                 int32_t *freq,
 105                 int32_t alphaSize,
 106                 int32_t maxLen)
 107 {
 108         /*
 109          * Nodes and heap entries run from 1.  Entry 0
 110          * for both the heap and nodes is a sentinel.
 111          */
 112         int32_t nNodes, nHeap, n1, n2, i, j, k;
 113         bz_Bool  tooLong;
 114
 115         /* bbox: moved to EState to save stack
 116         int32_t heap  [BZ_MAX_ALPHA_SIZE + 2];
 117         int32_t weight[BZ_MAX_ALPHA_SIZE * 2];
 118         int32_t parent[BZ_MAX_ALPHA_SIZE * 2];
 119         */
 120 #define heap   (s->BZ2_hbMakeCodeLengths__heap)
 121 #define weight (s->BZ2_hbMakeCodeLengths__weight)
 122 #define parent (s->BZ2_hbMakeCodeLengths__parent)
 123
 124         for (i = 0; i < alphaSize; i++)
 125                 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
 126
 127         while (1) {
 128                 nNodes = alphaSize;
 129                 nHeap = 0;
 130
 131                 heap[0] = 0;
 132                 weight[0] = 0;
 133                 parent[0] = -2;
 134
 135                 for (i = 1; i <= alphaSize; i++) {
 136                         parent[i] = -1;
 137                         nHeap++;
 138                         heap[nHeap] = i;
 139                         UPHEAP(nHeap);
 140                 }
 141
 142                 bz_AssertH(nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001);
 143
 144                 while (nHeap > 1) {
 145                         n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; BZ_DOWNHEAP1(heap, weight, nHeap);
 146                         n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; BZ_DOWNHEAP1(heap, weight, nHeap);
 147                         nNodes++;
 148                         parent[n1] = parent[n2] = nNodes;
 149                         weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
 150                         parent[nNodes] = -1;
 151                         nHeap++;
 152                         heap[nHeap] = nNodes;
 153                         UPHEAP(nHeap);
 154                 }
 155
 156                 bz_AssertH(nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002);
 157
 158                 tooLong = bz_False;
 159                 for (i = 1; i <= alphaSize; i++) {
 160                         j = 0;
 161                         k = i;
 162                         while (parent[k] >= 0) {
 163                                 k = parent[k];
 164                                 j++;
 165                         }
 166                         len[i-1] = j;
 167                         if (j > maxLen)
 168                                 tooLong = bz_True;
 169                 }
 170
 171                 if (!tooLong)
 172                         break;
 173
 174                 /* 17 Oct 04: keep-going condition for the following loop used
 175                 to be 'i < alphaSize', which missed the last element,
 176                 theoretically leading to the possibility of the compressor
 177                 looping.  However, this count-scaling step is only needed if
 178                 one of the generated Huffman code words is longer than
 179                 maxLen, which up to and including version 1.0.2 was 20 bits,
 180                 which is extremely unlikely.  In version 1.0.3 maxLen was
 181                 changed to 17 bits, which has minimal effect on compression
 182                 ratio, but does mean this scaling step is used from time to
 183                 time, enough to verify that it works.
 184
 185                 This means that bzip2-1.0.3 and later will only produce
 186                 Huffman codes with a maximum length of 17 bits.  However, in
 187                 order to preserve backwards compatibility with bitstreams
 188                 produced by versions pre-1.0.3, the decompressor must still
 189                 handle lengths of up to 20. */
 190
 191                 for (i = 1; i <= alphaSize; i++) {
 192                         j = weight[i] >> 8;
 193                         /* bbox: yes, it is a signed division.
 194                          * don't replace with shift! */
 195                         j = 1 + (j / 2);
 196                         weight[i] = j << 8;
 197                 }
 198         }
 199 #undef heap
 200 #undef weight
 201 #undef parent
 202 }
 203
 204
 205 /*---------------------------------------------------*/
 206 BB_STATIC
 207 void BZ2_hbAssignCodes(int32_t *code,
 208                 uint8_t *length,
 209                 int32_t minLen,
 210                 int32_t maxLen,
 211                 int32_t alphaSize)
 212 {
 213         int32_t n, vec, i;
 214
 215         vec = 0;
 216         for (n = minLen; n <= maxLen; n++) {
 217                 for (i = 0; i < alphaSize; i++) {
 218                         if (length[i] == n) {
 219                                 code[i] = vec;
 220                                 vec++;
 221                         }
 222                 }
 223                 vec <<= 1;
 224         }
 225 }
 226
 227 /* cleanup */
 228 #undef WEIGHTOF
 229 #undef DEPTHOF
 230 #undef MYMAX
 231
 232 #undef ADDWEIGHTS
 233 #undef UPHEAP
 234 #if BZIP2_SPEED
 235 #undef BB_DOWNHEAP1
 236 #endif
 237
 238 /*-------------------------------------------------------------*/
 239 /*--- end                                         huffman.c ---*/
 240 /*-------------------------------------------------------------*/