in src/ICSharpCode.SharpZipLib/BZip2/BZip2OutputStream.cs [627:1013]
private void SendMTFValues()
{
char[][] len = new char[BZip2Constants.GroupCount][];
for (int i = 0; i < BZip2Constants.GroupCount; ++i)
{
len[i] = new char[BZip2Constants.MaximumAlphaSize];
}
int gs, ge, totc, bt, bc, iter;
int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;
int nGroups;
alphaSize = nInUse + 2;
for (int t = 0; t < BZip2Constants.GroupCount; t++)
{
for (int v = 0; v < alphaSize; v++)
{
len[t][v] = (char)GREATER_ICOST;
}
}
/*--- Decide how many coding tables to use ---*/
if (nMTF <= 0)
{
Panic();
}
if (nMTF < 200)
{
nGroups = 2;
}
else if (nMTF < 600)
{
nGroups = 3;
}
else if (nMTF < 1200)
{
nGroups = 4;
}
else if (nMTF < 2400)
{
nGroups = 5;
}
else
{
nGroups = 6;
}
/*--- Generate an initial set of coding tables ---*/
int nPart = nGroups;
int remF = nMTF;
gs = 0;
while (nPart > 0)
{
int tFreq = remF / nPart;
int aFreq = 0;
ge = gs - 1;
while (aFreq < tFreq && ge < alphaSize - 1)
{
ge++;
aFreq += mtfFreq[ge];
}
if (ge > gs && nPart != nGroups && nPart != 1 && ((nGroups - nPart) % 2 == 1))
{
aFreq -= mtfFreq[ge];
ge--;
}
for (int v = 0; v < alphaSize; v++)
{
if (v >= gs && v <= ge)
{
len[nPart - 1][v] = (char)LESSER_ICOST;
}
else
{
len[nPart - 1][v] = (char)GREATER_ICOST;
}
}
nPart--;
gs = ge + 1;
remF -= aFreq;
}
int[][] rfreq = new int[BZip2Constants.GroupCount][];
for (int i = 0; i < BZip2Constants.GroupCount; ++i)
{
rfreq[i] = new int[BZip2Constants.MaximumAlphaSize];
}
int[] fave = new int[BZip2Constants.GroupCount];
short[] cost = new short[BZip2Constants.GroupCount];
/*---
Iterate up to N_ITERS times to improve the tables.
---*/
for (iter = 0; iter < BZip2Constants.NumberOfIterations; ++iter)
{
for (int t = 0; t < nGroups; ++t)
{
fave[t] = 0;
}
for (int t = 0; t < nGroups; ++t)
{
for (int v = 0; v < alphaSize; ++v)
{
rfreq[t][v] = 0;
}
}
nSelectors = 0;
totc = 0;
gs = 0;
while (true)
{
/*--- Set group start & end marks. --*/
if (gs >= nMTF)
{
break;
}
ge = gs + BZip2Constants.GroupSize - 1;
if (ge >= nMTF)
{
ge = nMTF - 1;
}
/*--
Calculate the cost of this group as coded
by each of the coding tables.
--*/
for (int t = 0; t < nGroups; t++)
{
cost[t] = 0;
}
if (nGroups == 6)
{
short cost0, cost1, cost2, cost3, cost4, cost5;
cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
for (int i = gs; i <= ge; ++i)
{
short icv = szptr[i];
cost0 += (short)len[0][icv];
cost1 += (short)len[1][icv];
cost2 += (short)len[2][icv];
cost3 += (short)len[3][icv];
cost4 += (short)len[4][icv];
cost5 += (short)len[5][icv];
}
cost[0] = cost0;
cost[1] = cost1;
cost[2] = cost2;
cost[3] = cost3;
cost[4] = cost4;
cost[5] = cost5;
}
else
{
for (int i = gs; i <= ge; ++i)
{
short icv = szptr[i];
for (int t = 0; t < nGroups; t++)
{
cost[t] += (short)len[t][icv];
}
}
}
/*--
Find the coding table which is best for this group,
and record its identity in the selector table.
--*/
bc = 999999999;
bt = -1;
for (int t = 0; t < nGroups; ++t)
{
if (cost[t] < bc)
{
bc = cost[t];
bt = t;
}
}
totc += bc;
fave[bt]++;
selector[nSelectors] = (char)bt;
nSelectors++;
/*--
Increment the symbol frequencies for the selected table.
--*/
for (int i = gs; i <= ge; ++i)
{
++rfreq[bt][szptr[i]];
}
gs = ge + 1;
}
/*--
Recompute the tables based on the accumulated frequencies.
--*/
for (int t = 0; t < nGroups; ++t)
{
HbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20);
}
}
rfreq = null;
fave = null;
cost = null;
if (!(nGroups < 8))
{
Panic();
}
if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / BZip2Constants.GroupSize))))
{
Panic();
}
/*--- Compute MTF values for the selectors. ---*/
char[] pos = new char[BZip2Constants.GroupCount];
char ll_i, tmp2, tmp;
for (int i = 0; i < nGroups; i++)
{
pos[i] = (char)i;
}
for (int i = 0; i < nSelectors; i++)
{
ll_i = selector[i];
int j = 0;
tmp = pos[j];
while (ll_i != tmp)
{
j++;
tmp2 = tmp;
tmp = pos[j];
pos[j] = tmp2;
}
pos[0] = tmp;
selectorMtf[i] = (char)j;
}
int[][] code = new int[BZip2Constants.GroupCount][];
for (int i = 0; i < BZip2Constants.GroupCount; ++i)
{
code[i] = new int[BZip2Constants.MaximumAlphaSize];
}
/*--- Assign actual codes for the tables. --*/
for (int t = 0; t < nGroups; t++)
{
minLen = 32;
maxLen = 0;
for (int i = 0; i < alphaSize; i++)
{
if (len[t][i] > maxLen)
{
maxLen = len[t][i];
}
if (len[t][i] < minLen)
{
minLen = len[t][i];
}
}
if (maxLen > 20)
{
Panic();
}
if (minLen < 1)
{
Panic();
}
HbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
}
/*--- Transmit the mapping table. ---*/
bool[] inUse16 = new bool[16];
for (int i = 0; i < 16; ++i)
{
inUse16[i] = false;
for (int j = 0; j < 16; ++j)
{
if (inUse[i * 16 + j])
{
inUse16[i] = true;
}
}
}
for (int i = 0; i < 16; ++i)
{
if (inUse16[i])
{
BsW(1, 1);
}
else
{
BsW(1, 0);
}
}
for (int i = 0; i < 16; ++i)
{
if (inUse16[i])
{
for (int j = 0; j < 16; ++j)
{
if (inUse[i * 16 + j])
{
BsW(1, 1);
}
else
{
BsW(1, 0);
}
}
}
}
/*--- Now the selectors. ---*/
BsW(3, nGroups);
BsW(15, nSelectors);
for (int i = 0; i < nSelectors; ++i)
{
for (int j = 0; j < selectorMtf[i]; ++j)
{
BsW(1, 1);
}
BsW(1, 0);
}
/*--- Now the coding tables. ---*/
for (int t = 0; t < nGroups; ++t)
{
int curr = len[t][0];
BsW(5, curr);
for (int i = 0; i < alphaSize; ++i)
{
while (curr < len[t][i])
{
BsW(2, 2);
curr++; /* 10 */
}
while (curr > len[t][i])
{
BsW(2, 3);
curr--; /* 11 */
}
BsW(1, 0);
}
}
/*--- And finally, the block data proper ---*/
selCtr = 0;
gs = 0;
while (true)
{
if (gs >= nMTF)
{
break;
}
ge = gs + BZip2Constants.GroupSize - 1;
if (ge >= nMTF)
{
ge = nMTF - 1;
}
for (int i = gs; i <= ge; i++)
{
BsW(len[selector[selCtr]][szptr[i]], code[selector[selCtr]][szptr[i]]);
}
gs = ge + 1;
++selCtr;
}
if (!(selCtr == nSelectors))
{
Panic();
}
}