uboot/lib_generic/bzlib_huffman.c
<<
>>
Prefs
   1#include <config.h>
   2
   3/*-------------------------------------------------------------*/
   4/*--- Huffman coding low-level stuff                        ---*/
   5/*---                                             huffman.c ---*/
   6/*-------------------------------------------------------------*/
   7
   8/*--
   9  This file is a part of bzip2 and/or libbzip2, a program and
  10  library for lossless, block-sorting data compression.
  11
  12  Copyright (C) 1996-2002 Julian R Seward.  All rights reserved.
  13
  14  Redistribution and use in source and binary forms, with or without
  15  modification, are permitted provided that the following conditions
  16  are met:
  17
  18  1. Redistributions of source code must retain the above copyright
  19     notice, this list of conditions and the following disclaimer.
  20
  21  2. The origin of this software must not be misrepresented; you must
  22     not claim that you wrote the original software.  If you use this
  23     software in a product, an acknowledgment in the product
  24     documentation would be appreciated but is not required.
  25
  26  3. Altered source versions must be plainly marked as such, and must
  27     not be misrepresented as being the original software.
  28
  29  4. The name of the author may not be used to endorse or promote
  30     products derived from this software without specific prior written
  31     permission.
  32
  33  THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
  34  OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  35  WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  36  ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  37  DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  38  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
  39  GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  40  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  41  WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  42  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  43  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  44
  45  Julian Seward, Cambridge, UK.
  46  jseward@acm.org
  47  bzip2/libbzip2 version 1.0 of 21 March 2000
  48
  49  This program is based on (at least) the work of:
  50     Mike Burrows
  51     David Wheeler
  52     Peter Fenwick
  53     Alistair Moffat
  54     Radford Neal
  55     Ian H. Witten
  56     Robert Sedgewick
  57     Jon L. Bentley
  58
  59  For more information on these sources, see the manual.
  60--*/
  61
  62
  63#include "bzlib_private.h"
  64
  65/*---------------------------------------------------*/
  66#define WEIGHTOF(zz0)  ((zz0) & 0xffffff00)
  67#define DEPTHOF(zz1)   ((zz1) & 0x000000ff)
  68#define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
  69
  70#define ADDWEIGHTS(zw1,zw2)                           \
  71   (WEIGHTOF(zw1)+WEIGHTOF(zw2)) |                    \
  72   (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
  73
  74#define UPHEAP(z)                                     \
  75{                                                     \
  76   Int32 zz, tmp;                                     \
  77   zz = z; tmp = heap[zz];                            \
  78   while (weight[tmp] < weight[heap[zz >> 1]]) {      \
  79      heap[zz] = heap[zz >> 1];                       \
  80      zz >>= 1;                                       \
  81   }                                                  \
  82   heap[zz] = tmp;                                    \
  83}
  84
  85#define DOWNHEAP(z)                                   \
  86{                                                     \
  87   Int32 zz, yy, tmp;                                 \
  88   zz = z; tmp = heap[zz];                            \
  89   while (True) {                                     \
  90      yy = zz << 1;                                   \
  91      if (yy > nHeap) break;                          \
  92      if (yy < nHeap &&                               \
  93          weight[heap[yy+1]] < weight[heap[yy]])      \
  94         yy++;                                        \
  95      if (weight[tmp] < weight[heap[yy]]) break;      \
  96      heap[zz] = heap[yy];                            \
  97      zz = yy;                                        \
  98   }                                                  \
  99   heap[zz] = tmp;                                    \
 100}
 101
 102
 103/*---------------------------------------------------*/
 104void BZ2_hbMakeCodeLengths ( UChar *len,
 105                             Int32 *freq,
 106                             Int32 alphaSize,
 107                             Int32 maxLen )
 108{
 109   /*--
 110      Nodes and heap entries run from 1.  Entry 0
 111      for both the heap and nodes is a sentinel.
 112   --*/
 113   Int32 nNodes, nHeap, n1, n2, i, j, k;
 114   Bool  tooLong;
 115
 116   Int32 heap   [ BZ_MAX_ALPHA_SIZE + 2 ];
 117   Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
 118   Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
 119
 120   for (i = 0; i < alphaSize; i++)
 121      weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
 122
 123   while (True) {
 124
 125      nNodes = alphaSize;
 126      nHeap = 0;
 127
 128      heap[0] = 0;
 129      weight[0] = 0;
 130      parent[0] = -2;
 131
 132      for (i = 1; i <= alphaSize; i++) {
 133         parent[i] = -1;
 134         nHeap++;
 135         heap[nHeap] = i;
 136         UPHEAP(nHeap);
 137      }
 138
 139      AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
 140
 141      while (nHeap > 1) {
 142         n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
 143         n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
 144         nNodes++;
 145         parent[n1] = parent[n2] = nNodes;
 146         weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
 147         parent[nNodes] = -1;
 148         nHeap++;
 149         heap[nHeap] = nNodes;
 150         UPHEAP(nHeap);
 151      }
 152
 153      AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
 154
 155      tooLong = False;
 156      for (i = 1; i <= alphaSize; i++) {
 157         j = 0;
 158         k = i;
 159         while (parent[k] >= 0) { k = parent[k]; j++; }
 160         len[i-1] = j;
 161         if (j > maxLen) tooLong = True;
 162      }
 163
 164      if (! tooLong) break;
 165
 166      for (i = 1; i < alphaSize; i++) {
 167         j = weight[i] >> 8;
 168         j = 1 + (j / 2);
 169         weight[i] = j << 8;
 170      }
 171   }
 172}
 173
 174
 175/*---------------------------------------------------*/
 176void BZ2_hbAssignCodes ( Int32 *code,
 177                         UChar *length,
 178                         Int32 minLen,
 179                         Int32 maxLen,
 180                         Int32 alphaSize )
 181{
 182   Int32 n, vec, i;
 183
 184   vec = 0;
 185   for (n = minLen; n <= maxLen; n++) {
 186      for (i = 0; i < alphaSize; i++)
 187         if (length[i] == n) { code[i] = vec; vec++; };
 188      vec <<= 1;
 189   }
 190}
 191
 192
 193/*---------------------------------------------------*/
 194void BZ2_hbCreateDecodeTables ( Int32 *limit,
 195                                Int32 *base,
 196                                Int32 *perm,
 197                                UChar *length,
 198                                Int32 minLen,
 199                                Int32 maxLen,
 200                                Int32 alphaSize )
 201{
 202   Int32 pp, i, j, vec;
 203
 204   pp = 0;
 205   for (i = minLen; i <= maxLen; i++)
 206      for (j = 0; j < alphaSize; j++)
 207         if (length[j] == i) { perm[pp] = j; pp++; };
 208
 209   for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
 210   for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
 211
 212   for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
 213
 214   for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
 215   vec = 0;
 216
 217   for (i = minLen; i <= maxLen; i++) {
 218      vec += (base[i+1] - base[i]);
 219      limit[i] = vec-1;
 220      vec <<= 1;
 221   }
 222   for (i = minLen + 1; i <= maxLen; i++)
 223      base[i] = ((limit[i-1] + 1) << 1) - base[i];
 224}
 225
 226
 227/*-------------------------------------------------------------*/
 228/*--- end                                         huffman.c ---*/
 229/*-------------------------------------------------------------*/
 230