{

protected const int SETMASK = (1 << 21);

protected const int CLEARMASK = (~SETMASK);

protected const int GREATER_ICOST = 15;

protected const int LESSER_ICOST = 0;

protected const int SMALL_THRESH = 20;

protected const int DEPTH_THRESH = 10;

/*

protected const int QSORT_STACK_SIZE = 1000;

private bool finished;

private static void Panic() {

//System.out.Println("panic");

//throw new CError();

}

private void MakeMaps() {

int i;

nInUse = 0;

for (i = 0; i < 256; i++) {

if (inUse[i]) {

seqToUnseq[nInUse] = (char) i;

unseqToSeq[i] = (char) nInUse;

nInUse++;

}

}

}

protected static void HbMakeCodeLengths(char[] len, int[] freq,

int alphaSize, int maxLen) {

/*

int nNodes, nHeap, n1, n2, i, j, k;

bool tooLong;

int[] heap = new int[BZip2Constants.MAX_ALPHA_SIZE + 2];

int[] weight = new int[BZip2Constants.MAX_ALPHA_SIZE * 2];

int[] parent = new int[BZip2Constants.MAX_ALPHA_SIZE * 2];

for (i = 0; i < alphaSize; i++) {

weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;

}

while (true) {

nNodes = alphaSize;

nHeap = 0;

heap[0] = 0;

weight[0] = 0;

parent[0] = -2;

for (i = 1; i <= alphaSize; i++) {

parent[i] = -1;

nHeap++;

heap[nHeap] = i;

{

int zz, tmp;

zz = nHeap;

tmp = heap[zz];

while (weight[tmp] < weight[heap[zz >> 1]]) {

heap[zz] = heap[zz >> 1];

zz >>= 1;

}

heap[zz] = tmp;

}

}

if (!(nHeap < (BZip2Constants.MAX_ALPHA_SIZE + 2))) {

Panic();

}

while (nHeap > 1) {

n1 = heap[1];

heap[1] = heap[nHeap];

nHeap--;

{

int zz = 0, yy = 0, tmp = 0;

zz = 1;

tmp = heap[zz];

while (true) {

yy = zz << 1;

if (yy > nHeap) {

break;

}

if (yy < nHeap

&& weight[heap[yy + 1]] < weight[heap[yy]]) {

yy++;

}

if (weight[tmp] < weight[heap[yy]]) {

break;

}

heap[zz] = heap[yy];

zz = yy;

}

heap[zz] = tmp;

}

n2 = heap[1];

heap[1] = heap[nHeap];

nHeap--;

{

int zz = 0, yy = 0, tmp = 0;

zz = 1;

tmp = heap[zz];

while (true) {

yy = zz << 1;

if (yy > nHeap) {

break;

}

if (yy < nHeap

&& weight[heap[yy + 1]] < weight[heap[yy]]) {

yy++;

}

if (weight[tmp] < weight[heap[yy]]) {

break;

}

heap[zz] = heap[yy];

zz = yy;

}

heap[zz] = tmp;

}

nNodes++;

parent[n1] = parent[n2] = nNodes;

weight[nNodes] = (int)((uint)((weight[n1] & 0xffffff00)

+ (weight[n2] & 0xffffff00))

| (uint)(1 + (((weight[n1] & 0x000000ff) >

(weight[n2] & 0x000000ff)) ?

(weight[n1] & 0x000000ff) :

(weight[n2] & 0x000000ff))));

parent[nNodes] = -1;

nHeap++;

heap[nHeap] = nNodes;

{

int zz = 0, tmp = 0;

zz = nHeap;

tmp = heap[zz];

while (weight[tmp] < weight[heap[zz >> 1]]) {

heap[zz] = heap[zz >> 1];

zz >>= 1;

}

heap[zz] = tmp;

}

}

if (!(nNodes < (BZip2Constants.MAX_ALPHA_SIZE * 2))) {

Panic();

}

tooLong = false;

for (i = 1; i <= alphaSize; i++) {

j = 0;

k = i;

while (parent[k] >= 0) {

k = parent[k];

j++;

}

len[i - 1] = (char) j;

if (j > maxLen) {

tooLong = true;

}

}

if (!tooLong) {

break;

}

for (i = 1; i < alphaSize; i++) {

j = weight[i] >> 8;

j = 1 + (j / 2);

weight[i] = j << 8;

}

}

}

/*

int last;

/*

int origPtr;

/*

int blockSize100k;

bool blockRandomised;

int bytesOut;

int bsBuff;

int bsLive;

CRC mCrc = new CRC();

private bool[] inUse = new bool[256];

private int nInUse;

private char[] seqToUnseq = new char[256];

private char[] unseqToSeq = new char[256];

private char[] selector = new char[BZip2Constants.MAX_SELECTORS];

private char[] selectorMtf = new char[BZip2Constants.MAX_SELECTORS];

private char[] block;

private int[] quadrant;

private int[] zptr;

private short[] szptr;

private int[] ftab;

private int nMTF;

private int[] mtfFreq = new int[BZip2Constants.MAX_ALPHA_SIZE];

/*

private int workFactor;

private int workDone;

private int workLimit;

private bool firstAttempt;

private int nBlocksRandomised;

private int currentChar = -1;

private int runLength = 0;

public CBZip2OutputStream(Stream inStream) : this(inStream, 9) {

}

public CBZip2OutputStream(Stream inStream, int inBlockSize)

{

block = null;

quadrant = null;

zptr = null;

ftab = null;

inStream.WriteByte((byte)'B');

inStream.WriteByte((byte)'Z');

BsSetStream(inStream);

workFactor = 50;

if (inBlockSize > 9) {

inBlockSize = 9;

}

if (inBlockSize < 1) {

inBlockSize = 1;

}

blockSize100k = inBlockSize;

AllocateCompressStructures();

Initialize();

InitBlock();

}

/**

public override void WriteByte(byte bv) {

int b = (256 + bv) % 256;

if (currentChar != -1) {

if (currentChar == b) {

runLength++;

if (runLength > 254) {

WriteRun();

currentChar = -1;

runLength = 0;

}

} else {

WriteRun();

runLength = 1;

currentChar = b;

}

} else {

currentChar = b;

runLength++;

}

}

private void WriteRun() {

if (last < allowableBlockSize) {

inUse[currentChar] = true;

for (int i = 0; i < runLength; i++) {

mCrc.UpdateCRC((char) currentChar);

}

switch (runLength) {

case 1:

last++;

block[last + 1] = (char) currentChar;

break;

case 2:

last++;

block[last + 1] = (char) currentChar;

last++;

block[last + 1] = (char) currentChar;

break;

case 3:

last++;

block[last + 1] = (char) currentChar;

last++;

block[last + 1] = (char) currentChar;

last++;

block[last + 1] = (char) currentChar;

break;

default:

inUse[runLength - 4] = true;

last++;

block[last + 1] = (char) currentChar;

last++;

block[last + 1] = (char) currentChar;

last++;

block[last + 1] = (char) currentChar;

last++;

block[last + 1] = (char) currentChar;

last++;

block[last + 1] = (char) (runLength - 4);

break;

}

} else {

EndBlock();

InitBlock();

WriteRun();

}

}

bool closed = false;

#if PORTABLE

protected override void Dispose(bool disposing)

{

if (disposing)

{

if (closed)

return;

Finish();

closed = true;

Platform.Dispose(this.bsStream);

}

base.Dispose(disposing);

}

#else

public override void Close() {

if (closed)

return;

Finish();

closed = true;

Platform.Dispose(this.bsStream);

base.Close();

}

#endif

public void Finish() {

if (finished) {

return;

}

if (runLength > 0) {

WriteRun();

}

currentChar = -1;

EndBlock();

EndCompression();

finished = true;

Flush();

}

public override void Flush() {

bsStream.Flush();

}

private int blockCRC, combinedCRC;

private void Initialize() {

bytesOut = 0;

nBlocksRandomised = 0;

/* Write `magic' bytes h indicating file-format == huffmanised,

BsPutUChar('h');

BsPutUChar('0' + blockSize100k);

combinedCRC = 0;

}

private int allowableBlockSize;

private void InitBlock() {

// blockNo++;

mCrc.InitialiseCRC();

last = -1;

// ch = 0;

for (int i = 0; i < 256; i++) {

inUse[i] = false;

}

/* 20 is just a paranoia constant */

allowableBlockSize = BZip2Constants.baseBlockSize * blockSize100k - 20;

}

private void EndBlock() {

blockCRC = mCrc.GetFinalCRC();

combinedCRC = (combinedCRC << 1) | (int)(((uint)combinedCRC) >> 31);

combinedCRC ^= blockCRC;

/* sort the block and establish posn of original string */

DoReversibleTransformation();

/*

BsPutUChar(0x31);

BsPutUChar(0x41);

BsPutUChar(0x59);

BsPutUChar(0x26);

BsPutUChar(0x53);

BsPutUChar(0x59);

/* Now the block's CRC, so it is in a known place. */

BsPutint(blockCRC);

/* Now a single bit indicating randomisation. */

if (blockRandomised) {

BsW(1, 1);

nBlocksRandomised++;

} else {

BsW(1, 0);

}

/* Finally, block's contents proper. */

MoveToFrontCodeAndSend();

}

private void EndCompression() {

/*

BsPutUChar(0x17);

BsPutUChar(0x72);

BsPutUChar(0x45);

BsPutUChar(0x38);

BsPutUChar(0x50);

BsPutUChar(0x90);

BsPutint(combinedCRC);

BsFinishedWithStream();

}

private void HbAssignCodes(int[] code, char[] length, int minLen,

int maxLen, int alphaSize) {

int n, vec, i;

vec = 0;

for (n = minLen; n <= maxLen; n++) {

for (i = 0; i < alphaSize; i++) {

if (length[i] == n) {

code[i] = vec;

vec++;

}

};

vec <<= 1;

}

}

private void BsSetStream(Stream f) {

bsStream = f;

bsLive = 0;

bsBuff = 0;

bytesOut = 0;

}

private void BsFinishedWithStream() {

while (bsLive > 0) {

int ch = (bsBuff >> 24);

try {

bsStream.WriteByte((byte)ch); // write 8-bit

} catch (IOException e) {

throw e;

}

bsBuff <<= 8;

bsLive -= 8;

bytesOut++;

}

}

private void BsW(int n, int v) {

while (bsLive >= 8) {

int ch = (bsBuff >> 24);

try {

bsStream.WriteByte((byte)ch); // write 8-bit

} catch (IOException e) {

throw e;

}

bsBuff <<= 8;

bsLive -= 8;

bytesOut++;

}

bsBuff |= (v << (32 - bsLive - n));

bsLive += n;

}

private void BsPutUChar(int c) {

BsW(8, c);

}

private void BsPutint(int u) {

BsW(8, (u >> 24) & 0xff);

BsW(8, (u >> 16) & 0xff);

BsW(8, (u >> 8) & 0xff);

BsW(8, u & 0xff);

}

private void BsPutIntVS(int numBits, int c) {

BsW(numBits, c);

}

private void SendMTFValues() {

char[][] len = CBZip2InputStream.InitCharArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE);

int v, t, i, j, gs, ge, totc, bt, bc, iter;

int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;

int nGroups;

alphaSize = nInUse + 2;

for (t = 0; t < BZip2Constants.N_GROUPS; t++) {

for (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, remF, tFreq, aFreq;

nPart = nGroups;

remF = nMTF;

gs = 0;

while (nPart > 0) {

tFreq = remF / nPart;

ge = gs - 1;

aFreq = 0;

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 (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 = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE);

int[] fave = new int[BZip2Constants.N_GROUPS];

short[] cost = new short[BZip2Constants.N_GROUPS];

/*

for (iter = 0; iter < BZip2Constants.N_ITERS; iter++) {

for (t = 0; t < nGroups; t++) {

fave[t] = 0;

}

for (t = 0; t < nGroups; t++) {

for (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.G_SIZE - 1;

if (ge >= nMTF) {

ge = nMTF - 1;

}

/*

for (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 (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 (i = gs; i <= ge; i++) {

short icv = szptr[i];

for (t = 0; t < nGroups; t++) {

cost[t] += (short)len[t][icv];

}

}

}

/*

bc = 999999999;

bt = -1;

for (t = 0; t < nGroups; t++) {

if (cost[t] < bc) {

bc = cost[t];

bt = t;

}

};

totc += bc;

fave[bt]++;

selector[nSelectors] = (char) bt;

nSelectors++;

/*

for (i = gs; i <= ge; i++) {

rfreq[bt][szptr[i]]++;

}

gs = ge + 1;

}

/*

for (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.G_SIZE)))) {

Panic();

}

/* Compute MTF values for the selectors. */

{

char[] pos = new char[BZip2Constants.N_GROUPS];

char ll_i, tmp2, tmp;

for (i = 0; i < nGroups; i++) {

pos[i] = (char) i;

}

for (i = 0; i < nSelectors; i++) {

ll_i = selector[i];

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 = CBZip2InputStream.InitIntArray(BZip2Constants.N_GROUPS, BZip2Constants.MAX_ALPHA_SIZE);

/* Assign actual codes for the tables. */

for (t = 0; t < nGroups; t++) {

minLen = 32;

maxLen = 0;

for (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 (i = 0; i < 16; i++) {

inUse16[i] = false;

for (j = 0; j < 16; j++) {

if (inUse[i * 16 + j]) {

inUse16[i] = true;

}

}

}

for (i = 0; i < 16; i++) {

if (inUse16[i]) {

BsW(1, 1);

} else {

BsW(1, 0);

}

}

for (i = 0; i < 16; i++) {

if (inUse16[i]) {

for (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 (i = 0; i < nSelectors; i++) {

for (j = 0; j < selectorMtf[i]; j++) {

BsW(1, 1);

}

BsW(1, 0);