00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 #include "bzlib_private.h"
00063
00064
00065 #define WEIGHTOF(zz0) ((zz0) & 0xffffff00)
00066 #define DEPTHOF(zz1) ((zz1) & 0x000000ff)
00067 #define MYMAX(zz2,zz3) ((zz2) > (zz3) ? (zz2) : (zz3))
00068
00069 #define ADDWEIGHTS(zw1,zw2) \
00070 (WEIGHTOF(zw1)+WEIGHTOF(zw2)) | \
00071 (1 + MYMAX(DEPTHOF(zw1),DEPTHOF(zw2)))
00072
00073 #define UPHEAP(z) \
00074 { \
00075 Int32 zz, tmp; \
00076 zz = z; tmp = heap[zz]; \
00077 while (weight[tmp] < weight[heap[zz >> 1]]) { \
00078 heap[zz] = heap[zz >> 1]; \
00079 zz >>= 1; \
00080 } \
00081 heap[zz] = tmp; \
00082 }
00083
00084 #define DOWNHEAP(z) \
00085 { \
00086 Int32 zz, yy, tmp; \
00087 zz = z; tmp = heap[zz]; \
00088 while (True) { \
00089 yy = zz << 1; \
00090 if (yy > nHeap) break; \
00091 if (yy < nHeap && \
00092 weight[heap[yy+1]] < weight[heap[yy]]) \
00093 yy++; \
00094 if (weight[tmp] < weight[heap[yy]]) break; \
00095 heap[zz] = heap[yy]; \
00096 zz = yy; \
00097 } \
00098 heap[zz] = tmp; \
00099 }
00100
00101
00102
00103 void hbMakeCodeLengths ( UChar *len,
00104 Int32 *freq,
00105 Int32 alphaSize,
00106 Int32 maxLen )
00107 {
00108
00109
00110
00111
00112 Int32 nNodes, nHeap, n1, n2, i, j, k;
00113 Bool tooLong;
00114
00115 Int32 heap [ BZ_MAX_ALPHA_SIZE + 2 ];
00116 Int32 weight [ BZ_MAX_ALPHA_SIZE * 2 ];
00117 Int32 parent [ BZ_MAX_ALPHA_SIZE * 2 ];
00118
00119 for (i = 0; i < alphaSize; i++)
00120 weight[i+1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
00121
00122 while (True) {
00123
00124 nNodes = alphaSize;
00125 nHeap = 0;
00126
00127 heap[0] = 0;
00128 weight[0] = 0;
00129 parent[0] = -2;
00130
00131 for (i = 1; i <= alphaSize; i++) {
00132 parent[i] = -1;
00133 nHeap++;
00134 heap[nHeap] = i;
00135 UPHEAP(nHeap);
00136 }
00137
00138 AssertH( nHeap < (BZ_MAX_ALPHA_SIZE+2), 2001 );
00139
00140 while (nHeap > 1) {
00141 n1 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
00142 n2 = heap[1]; heap[1] = heap[nHeap]; nHeap--; DOWNHEAP(1);
00143 nNodes++;
00144 parent[n1] = parent[n2] = nNodes;
00145 weight[nNodes] = ADDWEIGHTS(weight[n1], weight[n2]);
00146 parent[nNodes] = -1;
00147 nHeap++;
00148 heap[nHeap] = nNodes;
00149 UPHEAP(nHeap);
00150 }
00151
00152 AssertH( nNodes < (BZ_MAX_ALPHA_SIZE * 2), 2002 );
00153
00154 tooLong = False;
00155 for (i = 1; i <= alphaSize; i++) {
00156 j = 0;
00157 k = i;
00158 while (parent[k] >= 0) { k = parent[k]; j++; }
00159 len[i-1] = j;
00160 if (j > maxLen) tooLong = True;
00161 }
00162
00163 if (! tooLong) break;
00164
00165 for (i = 1; i < alphaSize; i++) {
00166 j = weight[i] >> 8;
00167 j = 1 + (j / 2);
00168 weight[i] = j << 8;
00169 }
00170 }
00171 }
00172
00173
00174
00175 void hbAssignCodes ( Int32 *code,
00176 UChar *length,
00177 Int32 minLen,
00178 Int32 maxLen,
00179 Int32 alphaSize )
00180 {
00181 Int32 n, vec, i;
00182
00183 vec = 0;
00184 for (n = minLen; n <= maxLen; n++) {
00185 for (i = 0; i < alphaSize; i++)
00186 if (length[i] == n) { code[i] = vec; vec++; };
00187 vec <<= 1;
00188 }
00189 }
00190
00191
00192
00193 void hbCreateDecodeTables ( Int32 *limit,
00194 Int32 *base,
00195 Int32 *perm,
00196 UChar *length,
00197 Int32 minLen,
00198 Int32 maxLen,
00199 Int32 alphaSize )
00200 {
00201 Int32 pp, i, j, vec;
00202
00203 pp = 0;
00204 for (i = minLen; i <= maxLen; i++)
00205 for (j = 0; j < alphaSize; j++)
00206 if (length[j] == i) { perm[pp] = j; pp++; };
00207
00208 for (i = 0; i < BZ_MAX_CODE_LEN; i++) base[i] = 0;
00209 for (i = 0; i < alphaSize; i++) base[length[i]+1]++;
00210
00211 for (i = 1; i < BZ_MAX_CODE_LEN; i++) base[i] += base[i-1];
00212
00213 for (i = 0; i < BZ_MAX_CODE_LEN; i++) limit[i] = 0;
00214 vec = 0;
00215
00216 for (i = minLen; i <= maxLen; i++) {
00217 vec += (base[i+1] - base[i]);
00218 limit[i] = vec-1;
00219 vec <<= 1;
00220 }
00221 for (i = minLen + 1; i <= maxLen; i++)
00222 base[i] = ((limit[i-1] + 1) << 1) - base[i];
00223 }
00224
00225
00226
00227
00228