← Back to branch summary

~ubuntu-branches/ubuntu/wily/ruby-ferret/wily

« back to all changes in this revision

Viewing changes to ext/BZLIB_huffman.c

  • Committer: Package Import Robot
  • Author(s): Cédric Boutillier
  • Date: 2013-11-25 01:09:16 UTC
  • mfrom: (1.1.2)
  • Revision ID: package-import@ubuntu.com-20131125010916-4wj3pwzcjjp8b9et
Tags: 0.11.8.5-1
* Imported Upstream version 0.11.8.5
* debian/control:
  + remove obsolete DM-Upload-Allowed flag
  + use canonical URI in Vcs-* fields
  + update my email address
  + bump Standards-Version to 3.9.5 (no changes needed)
  + drop transitional packages
* Remove single-debian-patch option
* Drop fix_compatibility_with_minitest.patch and
  block_variables_have_local_scopes.patch (applied upstream)
* Remove indications that the source has been repacked (not true anymore)
* Remove embedded copy of bzlib when cleaning instead of repacking
* Add copyright notice for the embedded copy of bzlib
* Install RELEASE_NOTES as documentation

Show diffs side-by-side

added added

removed removed

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