0001: /*
0002: * The Apache Software License, Version 1.1
0003: *
0004: * Copyright (c) 2001-2003 The Apache Software Foundation. All rights
0005: * reserved.
0006: *
0007: * Redistribution and use in source and binary forms, with or without
0008: * modification, are permitted provided that the following conditions
0009: * are met:
0010: *
0011: * 1. Redistributions of source code must retain the above copyright
0012: * notice, this list of conditions and the following disclaimer.
0013: *
0014: * 2. Redistributions in binary form must reproduce the above copyright
0015: * notice, this list of conditions and the following disclaimer in
0016: * the documentation and/or other materials provided with the
0017: * distribution.
0018: *
0019: * 3. The end-user documentation included with the redistribution, if
0020: * any, must include the following acknowlegement:
0021: * "This product includes software developed by the
0022: * Apache Software Foundation (http://www.apache.org/)."
0023: * Alternately, this acknowlegement may appear in the software itself,
0024: * if and wherever such third-party acknowlegements normally appear.
0025: *
0026: * 4. The names "Ant" and "Apache Software
0027: * Foundation" must not be used to endorse or promote products derived
0028: * from this software without prior written permission. For written
0029: * permission, please contact apache@apache.org.
0030: *
0031: * 5. Products derived from this software may not be called "Apache"
0032: * nor may "Apache" appear in their names without prior written
0033: * permission of the Apache Group.
0034: *
0035: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
0036: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
0037: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
0038: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
0039: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0040: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0041: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
0042: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
0043: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
0044: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
0045: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
0046: * SUCH DAMAGE.
0047: * ====================================================================
0048: *
0049: * This software consists of voluntary contributions made by many
0050: * individuals on behalf of the Apache Software Foundation. For more
0051: * information on the Apache Software Foundation, please see
0052: * <http://www.apache.org/>.
0053: */
0054:
0055: /*
0056: * This package is based on the work done by Keiron Liddle, Aftex Software
0057: * <keiron@aftexsw.com> to whom the Ant project is very grateful for his
0058: * great code.
0059: */
0060:
0061: package org.bouncycastle.apache.bzip2;
0062:
0063: import java.io.OutputStream;
0064: import java.io.IOException;
0065:
0066: /**
0067: * An output stream that compresses into the BZip2 format (with the file
0068: * header chars) into another stream.
0069: *
0070: * @author <a href="mailto:keiron@aftexsw.com">Keiron Liddle</a>
0071: *
0072: * TODO: Update to BZip2 1.0.1
0073: * <b>NB:</b> note this class has been modified to add a leading BZ to the
0074: * start of the BZIP2 stream to make it compatible with other PGP programs.
0075: */
0076: public class CBZip2OutputStream extends OutputStream implements
0077: BZip2Constants {
0078: protected static final int SETMASK = (1 << 21);
0079: protected static final int CLEARMASK = (~SETMASK);
0080: protected static final int GREATER_ICOST = 15;
0081: protected static final int LESSER_ICOST = 0;
0082: protected static final int SMALL_THRESH = 20;
0083: protected static final int DEPTH_THRESH = 10;
0084:
0085: /*
0086: If you are ever unlucky/improbable enough
0087: to get a stack overflow whilst sorting,
0088: increase the following constant and try
0089: again. In practice I have never seen the
0090: stack go above 27 elems, so the following
0091: limit seems very generous.
0092: */
0093: protected static final int QSORT_STACK_SIZE = 1000;
0094: private boolean finished;
0095:
0096: private static void panic() {
0097: System.out.println("panic");
0098: //throw new CError();
0099: }
0100:
0101: private void makeMaps() {
0102: int i;
0103: nInUse = 0;
0104: for (i = 0; i < 256; i++) {
0105: if (inUse[i]) {
0106: seqToUnseq[nInUse] = (char) i;
0107: unseqToSeq[i] = (char) nInUse;
0108: nInUse++;
0109: }
0110: }
0111: }
0112:
0113: protected static void hbMakeCodeLengths(char[] len, int[] freq,
0114: int alphaSize, int maxLen) {
0115: /*
0116: Nodes and heap entries run from 1. Entry 0
0117: for both the heap and nodes is a sentinel.
0118: */
0119: int nNodes, nHeap, n1, n2, i, j, k;
0120: boolean tooLong;
0121:
0122: int[] heap = new int[MAX_ALPHA_SIZE + 2];
0123: int[] weight = new int[MAX_ALPHA_SIZE * 2];
0124: int[] parent = new int[MAX_ALPHA_SIZE * 2];
0125:
0126: for (i = 0; i < alphaSize; i++) {
0127: weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;
0128: }
0129:
0130: while (true) {
0131: nNodes = alphaSize;
0132: nHeap = 0;
0133:
0134: heap[0] = 0;
0135: weight[0] = 0;
0136: parent[0] = -2;
0137:
0138: for (i = 1; i <= alphaSize; i++) {
0139: parent[i] = -1;
0140: nHeap++;
0141: heap[nHeap] = i;
0142: {
0143: int zz, tmp;
0144: zz = nHeap;
0145: tmp = heap[zz];
0146: while (weight[tmp] < weight[heap[zz >> 1]]) {
0147: heap[zz] = heap[zz >> 1];
0148: zz >>= 1;
0149: }
0150: heap[zz] = tmp;
0151: }
0152: }
0153: if (!(nHeap < (MAX_ALPHA_SIZE + 2))) {
0154: panic();
0155: }
0156:
0157: while (nHeap > 1) {
0158: n1 = heap[1];
0159: heap[1] = heap[nHeap];
0160: nHeap--;
0161: {
0162: int zz = 0, yy = 0, tmp = 0;
0163: zz = 1;
0164: tmp = heap[zz];
0165: while (true) {
0166: yy = zz << 1;
0167: if (yy > nHeap) {
0168: break;
0169: }
0170: if (yy < nHeap
0171: && weight[heap[yy + 1]] < weight[heap[yy]]) {
0172: yy++;
0173: }
0174: if (weight[tmp] < weight[heap[yy]]) {
0175: break;
0176: }
0177: heap[zz] = heap[yy];
0178: zz = yy;
0179: }
0180: heap[zz] = tmp;
0181: }
0182: n2 = heap[1];
0183: heap[1] = heap[nHeap];
0184: nHeap--;
0185: {
0186: int zz = 0, yy = 0, tmp = 0;
0187: zz = 1;
0188: tmp = heap[zz];
0189: while (true) {
0190: yy = zz << 1;
0191: if (yy > nHeap) {
0192: break;
0193: }
0194: if (yy < nHeap
0195: && weight[heap[yy + 1]] < weight[heap[yy]]) {
0196: yy++;
0197: }
0198: if (weight[tmp] < weight[heap[yy]]) {
0199: break;
0200: }
0201: heap[zz] = heap[yy];
0202: zz = yy;
0203: }
0204: heap[zz] = tmp;
0205: }
0206: nNodes++;
0207: parent[n1] = parent[n2] = nNodes;
0208:
0209: weight[nNodes] = ((weight[n1] & 0xffffff00) + (weight[n2] & 0xffffff00))
0210: | (1 + (((weight[n1] & 0x000000ff) > (weight[n2] & 0x000000ff)) ? (weight[n1] & 0x000000ff)
0211: : (weight[n2] & 0x000000ff)));
0212:
0213: parent[nNodes] = -1;
0214: nHeap++;
0215: heap[nHeap] = nNodes;
0216: {
0217: int zz = 0, tmp = 0;
0218: zz = nHeap;
0219: tmp = heap[zz];
0220: while (weight[tmp] < weight[heap[zz >> 1]]) {
0221: heap[zz] = heap[zz >> 1];
0222: zz >>= 1;
0223: }
0224: heap[zz] = tmp;
0225: }
0226: }
0227: if (!(nNodes < (MAX_ALPHA_SIZE * 2))) {
0228: panic();
0229: }
0230:
0231: tooLong = false;
0232: for (i = 1; i <= alphaSize; i++) {
0233: j = 0;
0234: k = i;
0235: while (parent[k] >= 0) {
0236: k = parent[k];
0237: j++;
0238: }
0239: len[i - 1] = (char) j;
0240: if (j > maxLen) {
0241: tooLong = true;
0242: }
0243: }
0244:
0245: if (!tooLong) {
0246: break;
0247: }
0248:
0249: for (i = 1; i < alphaSize; i++) {
0250: j = weight[i] >> 8;
0251: j = 1 + (j / 2);
0252: weight[i] = j << 8;
0253: }
0254: }
0255: }
0256:
0257: /*
0258: index of the last char in the block, so
0259: the block size == last + 1.
0260: */
0261: int last;
0262:
0263: /*
0264: index in zptr[] of original string after sorting.
0265: */
0266: int origPtr;
0267:
0268: /*
0269: always: in the range 0 .. 9.
0270: The current block size is 100000 * this number.
0271: */
0272: int blockSize100k;
0273:
0274: boolean blockRandomised;
0275:
0276: int bytesOut;
0277: int bsBuff;
0278: int bsLive;
0279: CRC mCrc = new CRC();
0280:
0281: private boolean[] inUse = new boolean[256];
0282: private int nInUse;
0283:
0284: private char[] seqToUnseq = new char[256];
0285: private char[] unseqToSeq = new char[256];
0286:
0287: private char[] selector = new char[MAX_SELECTORS];
0288: private char[] selectorMtf = new char[MAX_SELECTORS];
0289:
0290: private char[] block;
0291: private int[] quadrant;
0292: private int[] zptr;
0293: private short[] szptr;
0294: private int[] ftab;
0295:
0296: private int nMTF;
0297:
0298: private int[] mtfFreq = new int[MAX_ALPHA_SIZE];
0299:
0300: /*
0301: * Used when sorting. If too many long comparisons
0302: * happen, we stop sorting, randomise the block
0303: * slightly, and try again.
0304: */
0305: private int workFactor;
0306: private int workDone;
0307: private int workLimit;
0308: private boolean firstAttempt;
0309: private int nBlocksRandomised;
0310:
0311: private int currentChar = -1;
0312: private int runLength = 0;
0313:
0314: public CBZip2OutputStream(OutputStream inStream) throws IOException {
0315: this (inStream, 9);
0316: }
0317:
0318: public CBZip2OutputStream(OutputStream inStream, int inBlockSize)
0319: throws IOException {
0320: block = null;
0321: quadrant = null;
0322: zptr = null;
0323: ftab = null;
0324:
0325: inStream.write('B');
0326: inStream.write('Z');
0327:
0328: bsSetStream(inStream);
0329:
0330: workFactor = 50;
0331: if (inBlockSize > 9) {
0332: inBlockSize = 9;
0333: }
0334: if (inBlockSize < 1) {
0335: inBlockSize = 1;
0336: }
0337: blockSize100k = inBlockSize;
0338: allocateCompressStructures();
0339: initialize();
0340: initBlock();
0341: }
0342:
0343: /**
0344: *
0345: * modified by Oliver Merkel, 010128
0346: *
0347: */
0348: public void write(int bv) throws IOException {
0349: int b = (256 + bv) % 256;
0350: if (currentChar != -1) {
0351: if (currentChar == b) {
0352: runLength++;
0353: if (runLength > 254) {
0354: writeRun();
0355: currentChar = -1;
0356: runLength = 0;
0357: }
0358: } else {
0359: writeRun();
0360: runLength = 1;
0361: currentChar = b;
0362: }
0363: } else {
0364: currentChar = b;
0365: runLength++;
0366: }
0367: }
0368:
0369: private void writeRun() throws IOException {
0370: if (last < allowableBlockSize) {
0371: inUse[currentChar] = true;
0372: for (int i = 0; i < runLength; i++) {
0373: mCrc.updateCRC((char) currentChar);
0374: }
0375: switch (runLength) {
0376: case 1:
0377: last++;
0378: block[last + 1] = (char) currentChar;
0379: break;
0380: case 2:
0381: last++;
0382: block[last + 1] = (char) currentChar;
0383: last++;
0384: block[last + 1] = (char) currentChar;
0385: break;
0386: case 3:
0387: last++;
0388: block[last + 1] = (char) currentChar;
0389: last++;
0390: block[last + 1] = (char) currentChar;
0391: last++;
0392: block[last + 1] = (char) currentChar;
0393: break;
0394: default:
0395: inUse[runLength - 4] = true;
0396: last++;
0397: block[last + 1] = (char) currentChar;
0398: last++;
0399: block[last + 1] = (char) currentChar;
0400: last++;
0401: block[last + 1] = (char) currentChar;
0402: last++;
0403: block[last + 1] = (char) currentChar;
0404: last++;
0405: block[last + 1] = (char) (runLength - 4);
0406: break;
0407: }
0408: } else {
0409: endBlock();
0410: initBlock();
0411: writeRun();
0412: }
0413: }
0414:
0415: boolean closed = false;
0416:
0417: protected void finalize() throws Throwable {
0418: close();
0419: super .finalize();
0420: }
0421:
0422: public void close() throws IOException {
0423: if (closed) {
0424: return;
0425: }
0426:
0427: finish();
0428:
0429: closed = true;
0430: super .close();
0431: bsStream.close();
0432: }
0433:
0434: public void finish() throws IOException {
0435: if (finished) {
0436: return;
0437: }
0438:
0439: if (runLength > 0) {
0440: writeRun();
0441: }
0442: currentChar = -1;
0443: endBlock();
0444: endCompression();
0445: finished = true;
0446: flush();
0447: }
0448:
0449: public void flush() throws IOException {
0450: super .flush();
0451: bsStream.flush();
0452: }
0453:
0454: private int blockCRC, combinedCRC;
0455:
0456: private void initialize() throws IOException {
0457: bytesOut = 0;
0458: nBlocksRandomised = 0;
0459:
0460: /* Write `magic' bytes h indicating file-format == huffmanised,
0461: followed by a digit indicating blockSize100k.
0462: */
0463: bsPutUChar('h');
0464: bsPutUChar('0' + blockSize100k);
0465:
0466: combinedCRC = 0;
0467: }
0468:
0469: private int allowableBlockSize;
0470:
0471: private void initBlock() {
0472: // blockNo++;
0473: mCrc.initialiseCRC();
0474: last = -1;
0475: // ch = 0;
0476:
0477: for (int i = 0; i < 256; i++) {
0478: inUse[i] = false;
0479: }
0480:
0481: /* 20 is just a paranoia constant */
0482: allowableBlockSize = baseBlockSize * blockSize100k - 20;
0483: }
0484:
0485: private void endBlock() throws IOException {
0486: blockCRC = mCrc.getFinalCRC();
0487: combinedCRC = (combinedCRC << 1) | (combinedCRC >>> 31);
0488: combinedCRC ^= blockCRC;
0489:
0490: /* sort the block and establish posn of original string */
0491: doReversibleTransformation();
0492:
0493: /*
0494: A 6-byte block header, the value chosen arbitrarily
0495: as 0x314159265359 :-). A 32 bit value does not really
0496: give a strong enough guarantee that the value will not
0497: appear by chance in the compressed datastream. Worst-case
0498: probability of this event, for a 900k block, is about
0499: 2.0e-3 for 32 bits, 1.0e-5 for 40 bits and 4.0e-8 for 48 bits.
0500: For a compressed file of size 100Gb -- about 100000 blocks --
0501: only a 48-bit marker will do. NB: normal compression/
0502: decompression do *not* rely on these statistical properties.
0503: They are only important when trying to recover blocks from
0504: damaged files.
0505: */
0506: bsPutUChar(0x31);
0507: bsPutUChar(0x41);
0508: bsPutUChar(0x59);
0509: bsPutUChar(0x26);
0510: bsPutUChar(0x53);
0511: bsPutUChar(0x59);
0512:
0513: /* Now the block's CRC, so it is in a known place. */
0514: bsPutint(blockCRC);
0515:
0516: /* Now a single bit indicating randomisation. */
0517: if (blockRandomised) {
0518: bsW(1, 1);
0519: nBlocksRandomised++;
0520: } else {
0521: bsW(1, 0);
0522: }
0523:
0524: /* Finally, block's contents proper. */
0525: moveToFrontCodeAndSend();
0526: }
0527:
0528: private void endCompression() throws IOException {
0529: /*
0530: Now another magic 48-bit number, 0x177245385090, to
0531: indicate the end of the last block. (sqrt(pi), if
0532: you want to know. I did want to use e, but it contains
0533: too much repetition -- 27 18 28 18 28 46 -- for me
0534: to feel statistically comfortable. Call me paranoid.)
0535: */
0536: bsPutUChar(0x17);
0537: bsPutUChar(0x72);
0538: bsPutUChar(0x45);
0539: bsPutUChar(0x38);
0540: bsPutUChar(0x50);
0541: bsPutUChar(0x90);
0542:
0543: bsPutint(combinedCRC);
0544:
0545: bsFinishedWithStream();
0546: }
0547:
0548: private void hbAssignCodes(int[] code, char[] length, int minLen,
0549: int maxLen, int alphaSize) {
0550: int n, vec, i;
0551:
0552: vec = 0;
0553: for (n = minLen; n <= maxLen; n++) {
0554: for (i = 0; i < alphaSize; i++) {
0555: if (length[i] == n) {
0556: code[i] = vec;
0557: vec++;
0558: }
0559: }
0560: ;
0561: vec <<= 1;
0562: }
0563: }
0564:
0565: private void bsSetStream(OutputStream f) {
0566: bsStream = f;
0567: bsLive = 0;
0568: bsBuff = 0;
0569: bytesOut = 0;
0570: }
0571:
0572: private void bsFinishedWithStream() throws IOException {
0573: while (bsLive > 0) {
0574: int ch = (bsBuff >> 24);
0575: try {
0576: bsStream.write(ch); // write 8-bit
0577: } catch (IOException e) {
0578: throw e;
0579: }
0580: bsBuff <<= 8;
0581: bsLive -= 8;
0582: bytesOut++;
0583: }
0584: }
0585:
0586: private void bsW(int n, int v) throws IOException {
0587: while (bsLive >= 8) {
0588: int ch = (bsBuff >> 24);
0589: try {
0590: bsStream.write(ch); // write 8-bit
0591: } catch (IOException e) {
0592: throw e;
0593: }
0594: bsBuff <<= 8;
0595: bsLive -= 8;
0596: bytesOut++;
0597: }
0598: bsBuff |= (v << (32 - bsLive - n));
0599: bsLive += n;
0600: }
0601:
0602: private void bsPutUChar(int c) throws IOException {
0603: bsW(8, c);
0604: }
0605:
0606: private void bsPutint(int u) throws IOException {
0607: bsW(8, (u >> 24) & 0xff);
0608: bsW(8, (u >> 16) & 0xff);
0609: bsW(8, (u >> 8) & 0xff);
0610: bsW(8, u & 0xff);
0611: }
0612:
0613: private void bsPutIntVS(int numBits, int c) throws IOException {
0614: bsW(numBits, c);
0615: }
0616:
0617: private void sendMTFValues() throws IOException {
0618: char len[][] = new char[N_GROUPS][MAX_ALPHA_SIZE];
0619:
0620: int v, t, i, j, gs, ge, totc, bt, bc, iter;
0621: int nSelectors = 0, alphaSize, minLen, maxLen, selCtr;
0622: int nGroups, nBytes;
0623:
0624: alphaSize = nInUse + 2;
0625: for (t = 0; t < N_GROUPS; t++) {
0626: for (v = 0; v < alphaSize; v++) {
0627: len[t][v] = (char) GREATER_ICOST;
0628: }
0629: }
0630:
0631: /* Decide how many coding tables to use */
0632: if (nMTF <= 0) {
0633: panic();
0634: }
0635:
0636: if (nMTF < 200) {
0637: nGroups = 2;
0638: } else if (nMTF < 600) {
0639: nGroups = 3;
0640: } else if (nMTF < 1200) {
0641: nGroups = 4;
0642: } else if (nMTF < 2400) {
0643: nGroups = 5;
0644: } else {
0645: nGroups = 6;
0646: }
0647:
0648: /* Generate an initial set of coding tables */{
0649: int nPart, remF, tFreq, aFreq;
0650:
0651: nPart = nGroups;
0652: remF = nMTF;
0653: gs = 0;
0654: while (nPart > 0) {
0655: tFreq = remF / nPart;
0656: ge = gs - 1;
0657: aFreq = 0;
0658: while (aFreq < tFreq && ge < alphaSize - 1) {
0659: ge++;
0660: aFreq += mtfFreq[ge];
0661: }
0662:
0663: if (ge > gs && nPart != nGroups && nPart != 1
0664: && ((nGroups - nPart) % 2 == 1)) {
0665: aFreq -= mtfFreq[ge];
0666: ge--;
0667: }
0668:
0669: for (v = 0; v < alphaSize; v++) {
0670: if (v >= gs && v <= ge) {
0671: len[nPart - 1][v] = (char) LESSER_ICOST;
0672: } else {
0673: len[nPart - 1][v] = (char) GREATER_ICOST;
0674: }
0675: }
0676:
0677: nPart--;
0678: gs = ge + 1;
0679: remF -= aFreq;
0680: }
0681: }
0682:
0683: int[][] rfreq = new int[N_GROUPS][MAX_ALPHA_SIZE];
0684: int[] fave = new int[N_GROUPS];
0685: short[] cost = new short[N_GROUPS];
0686: /*
0687: Iterate up to N_ITERS times to improve the tables.
0688: */
0689: for (iter = 0; iter < N_ITERS; iter++) {
0690: for (t = 0; t < nGroups; t++) {
0691: fave[t] = 0;
0692: }
0693:
0694: for (t = 0; t < nGroups; t++) {
0695: for (v = 0; v < alphaSize; v++) {
0696: rfreq[t][v] = 0;
0697: }
0698: }
0699:
0700: nSelectors = 0;
0701: totc = 0;
0702: gs = 0;
0703: while (true) {
0704:
0705: /* Set group start & end marks. */
0706: if (gs >= nMTF) {
0707: break;
0708: }
0709: ge = gs + G_SIZE - 1;
0710: if (ge >= nMTF) {
0711: ge = nMTF - 1;
0712: }
0713:
0714: /*
0715: Calculate the cost of this group as coded
0716: by each of the coding tables.
0717: */
0718: for (t = 0; t < nGroups; t++) {
0719: cost[t] = 0;
0720: }
0721:
0722: if (nGroups == 6) {
0723: short cost0, cost1, cost2, cost3, cost4, cost5;
0724: cost0 = cost1 = cost2 = cost3 = cost4 = cost5 = 0;
0725: for (i = gs; i <= ge; i++) {
0726: short icv = szptr[i];
0727: cost0 += len[0][icv];
0728: cost1 += len[1][icv];
0729: cost2 += len[2][icv];
0730: cost3 += len[3][icv];
0731: cost4 += len[4][icv];
0732: cost5 += len[5][icv];
0733: }
0734: cost[0] = cost0;
0735: cost[1] = cost1;
0736: cost[2] = cost2;
0737: cost[3] = cost3;
0738: cost[4] = cost4;
0739: cost[5] = cost5;
0740: } else {
0741: for (i = gs; i <= ge; i++) {
0742: short icv = szptr[i];
0743: for (t = 0; t < nGroups; t++) {
0744: cost[t] += len[t][icv];
0745: }
0746: }
0747: }
0748:
0749: /*
0750: Find the coding table which is best for this group,
0751: and record its identity in the selector table.
0752: */
0753: bc = 999999999;
0754: bt = -1;
0755: for (t = 0; t < nGroups; t++) {
0756: if (cost[t] < bc) {
0757: bc = cost[t];
0758: bt = t;
0759: }
0760: }
0761: ;
0762: totc += bc;
0763: fave[bt]++;
0764: selector[nSelectors] = (char) bt;
0765: nSelectors++;
0766:
0767: /*
0768: Increment the symbol frequencies for the selected table.
0769: */
0770: for (i = gs; i <= ge; i++) {
0771: rfreq[bt][szptr[i]]++;
0772: }
0773:
0774: gs = ge + 1;
0775: }
0776:
0777: /*
0778: Recompute the tables based on the accumulated frequencies.
0779: */
0780: for (t = 0; t < nGroups; t++) {
0781: hbMakeCodeLengths(len[t], rfreq[t], alphaSize, 20);
0782: }
0783: }
0784:
0785: rfreq = null;
0786: fave = null;
0787: cost = null;
0788:
0789: if (!(nGroups < 8)) {
0790: panic();
0791: }
0792: if (!(nSelectors < 32768 && nSelectors <= (2 + (900000 / G_SIZE)))) {
0793: panic();
0794: }
0795:
0796: /* Compute MTF values for the selectors. */
0797: {
0798: char[] pos = new char[N_GROUPS];
0799: char ll_i, tmp2, tmp;
0800: for (i = 0; i < nGroups; i++) {
0801: pos[i] = (char) i;
0802: }
0803: for (i = 0; i < nSelectors; i++) {
0804: ll_i = selector[i];
0805: j = 0;
0806: tmp = pos[j];
0807: while (ll_i != tmp) {
0808: j++;
0809: tmp2 = tmp;
0810: tmp = pos[j];
0811: pos[j] = tmp2;
0812: }
0813: pos[0] = tmp;
0814: selectorMtf[i] = (char) j;
0815: }
0816: }
0817:
0818: int[][] code = new int[N_GROUPS][MAX_ALPHA_SIZE];
0819:
0820: /* Assign actual codes for the tables. */
0821: for (t = 0; t < nGroups; t++) {
0822: minLen = 32;
0823: maxLen = 0;
0824: for (i = 0; i < alphaSize; i++) {
0825: if (len[t][i] > maxLen) {
0826: maxLen = len[t][i];
0827: }
0828: if (len[t][i] < minLen) {
0829: minLen = len[t][i];
0830: }
0831: }
0832: if (maxLen > 20) {
0833: panic();
0834: }
0835: if (minLen < 1) {
0836: panic();
0837: }
0838: hbAssignCodes(code[t], len[t], minLen, maxLen, alphaSize);
0839: }
0840:
0841: /* Transmit the mapping table. */
0842: {
0843: boolean[] inUse16 = new boolean[16];
0844: for (i = 0; i < 16; i++) {
0845: inUse16[i] = false;
0846: for (j = 0; j < 16; j++) {
0847: if (inUse[i * 16 + j]) {
0848: inUse16[i] = true;
0849: }
0850: }
0851: }
0852:
0853: nBytes = bytesOut;
0854: for (i = 0; i < 16; i++) {
0855: if (inUse16[i]) {
0856: bsW(1, 1);
0857: } else {
0858: bsW(1, 0);
0859: }
0860: }
0861:
0862: for (i = 0; i < 16; i++) {
0863: if (inUse16[i]) {
0864: for (j = 0; j < 16; j++) {
0865: if (inUse[i * 16 + j]) {
0866: bsW(1, 1);
0867: } else {
0868: bsW(1, 0);
0869: }
0870: }
0871: }
0872: }
0873:
0874: }
0875:
0876: /* Now the selectors. */
0877: nBytes = bytesOut;
0878: bsW(3, nGroups);
0879: bsW(15, nSelectors);
0880: for (i = 0; i < nSelectors; i++) {
0881: for (j = 0; j < selectorMtf[i]; j++) {
0882: bsW(1, 1);
0883: }
0884: bsW(1, 0);
0885: }
0886:
0887: /* Now the coding tables. */
0888: nBytes = bytesOut;
0889:
0890: for (t = 0; t < nGroups; t++) {
0891: int curr = len[t][0];
0892: bsW(5, curr);
0893: for (i = 0; i < alphaSize; i++) {
0894: while (curr < len[t][i]) {
0895: bsW(2, 2);
0896: curr++; /* 10 */
0897: }
0898: while (curr > len[t][i]) {
0899: bsW(2, 3);
0900: curr--; /* 11 */
0901: }
0902: bsW(1, 0);
0903: }
0904: }
0905:
0906: /* And finally, the block data proper */
0907: nBytes = bytesOut;
0908: selCtr = 0;
0909: gs = 0;
0910: while (true) {
0911: if (gs >= nMTF) {
0912: break;
0913: }
0914: ge = gs + G_SIZE - 1;
0915: if (ge >= nMTF) {
0916: ge = nMTF - 1;
0917: }
0918: for (i = gs; i <= ge; i++) {
0919: bsW(len[selector[selCtr]][szptr[i]],
0920: code[selector[selCtr]][szptr[i]]);
0921: }
0922:
0923: gs = ge + 1;
0924: selCtr++;
0925: }
0926: if (!(selCtr == nSelectors)) {
0927: panic();
0928: }
0929: }
0930:
0931: private void moveToFrontCodeAndSend() throws IOException {
0932: bsPutIntVS(24, origPtr);
0933: generateMTFValues();
0934: sendMTFValues();
0935: }
0936:
0937: private OutputStream bsStream;
0938:
0939: private void simpleSort(int lo, int hi, int d) {
0940: int i, j, h, bigN, hp;
0941: int v;
0942:
0943: bigN = hi - lo + 1;
0944: if (bigN < 2) {
0945: return;
0946: }
0947:
0948: hp = 0;
0949: while (incs[hp] < bigN) {
0950: hp++;
0951: }
0952: hp--;
0953:
0954: for (; hp >= 0; hp--) {
0955: h = incs[hp];
0956:
0957: i = lo + h;
0958: while (true) {
0959: /* copy 1 */
0960: if (i > hi) {
0961: break;
0962: }
0963: v = zptr[i];
0964: j = i;
0965: while (fullGtU(zptr[j - h] + d, v + d)) {
0966: zptr[j] = zptr[j - h];
0967: j = j - h;
0968: if (j <= (lo + h - 1)) {
0969: break;
0970: }
0971: }
0972: zptr[j] = v;
0973: i++;
0974:
0975: /* copy 2 */
0976: if (i > hi) {
0977: break;
0978: }
0979: v = zptr[i];
0980: j = i;
0981: while (fullGtU(zptr[j - h] + d, v + d)) {
0982: zptr[j] = zptr[j - h];
0983: j = j - h;
0984: if (j <= (lo + h - 1)) {
0985: break;
0986: }
0987: }
0988: zptr[j] = v;
0989: i++;
0990:
0991: /* copy 3 */
0992: if (i > hi) {
0993: break;
0994: }
0995: v = zptr[i];
0996: j = i;
0997: while (fullGtU(zptr[j - h] + d, v + d)) {
0998: zptr[j] = zptr[j - h];
0999: j = j - h;
1000: if (j <= (lo + h - 1)) {
1001: break;
1002: }
1003: }
1004: zptr[j] = v;
1005: i++;
1006:
1007: if (workDone > workLimit && firstAttempt) {
1008: return;
1009: }
1010: }
1011: }
1012: }
1013:
1014: private void vswap(int p1, int p2, int n) {
1015: int temp = 0;
1016: while (n > 0) {
1017: temp = zptr[p1];
1018: zptr[p1] = zptr[p2];
1019: zptr[p2] = temp;
1020: p1++;
1021: p2++;
1022: n--;
1023: }
1024: }
1025:
1026: private char med3(char a, char b, char c) {
1027: char t;
1028: if (a > b) {
1029: t = a;
1030: a = b;
1031: b = t;
1032: }
1033: if (b > c) {
1034: t = b;
1035: b = c;
1036: c = t;
1037: }
1038: if (a > b) {
1039: b = a;
1040: }
1041: return b;
1042: }
1043:
1044: private static class StackElem {
1045: int ll;
1046: int hh;
1047: int dd;
1048: }
1049:
1050: private void qSort3(int loSt, int hiSt, int dSt) {
1051: int unLo, unHi, ltLo, gtHi, med, n, m;
1052: int sp, lo, hi, d;
1053: StackElem[] stack = new StackElem[QSORT_STACK_SIZE];
1054: for (int count = 0; count < QSORT_STACK_SIZE; count++) {
1055: stack[count] = new StackElem();
1056: }
1057:
1058: sp = 0;
1059:
1060: stack[sp].ll = loSt;
1061: stack[sp].hh = hiSt;
1062: stack[sp].dd = dSt;
1063: sp++;
1064:
1065: while (sp > 0) {
1066: if (sp >= QSORT_STACK_SIZE) {
1067: panic();
1068: }
1069:
1070: sp--;
1071: lo = stack[sp].ll;
1072: hi = stack[sp].hh;
1073: d = stack[sp].dd;
1074:
1075: if (hi - lo < SMALL_THRESH || d > DEPTH_THRESH) {
1076: simpleSort(lo, hi, d);
1077: if (workDone > workLimit && firstAttempt) {
1078: return;
1079: }
1080: continue;
1081: }
1082:
1083: med = med3(block[zptr[lo] + d + 1],
1084: block[zptr[hi] + d + 1], block[zptr[(lo + hi) >> 1]
1085: + d + 1]);
1086:
1087: unLo = ltLo = lo;
1088: unHi = gtHi = hi;
1089:
1090: while (true) {
1091: while (true) {
1092: if (unLo > unHi) {
1093: break;
1094: }
1095: n = ((int) block[zptr[unLo] + d + 1]) - med;
1096: if (n == 0) {
1097: int temp = 0;
1098: temp = zptr[unLo];
1099: zptr[unLo] = zptr[ltLo];
1100: zptr[ltLo] = temp;
1101: ltLo++;
1102: unLo++;
1103: continue;
1104: }
1105: ;
1106: if (n > 0) {
1107: break;
1108: }
1109: unLo++;
1110: }
1111: while (true) {
1112: if (unLo > unHi) {
1113: break;
1114: }
1115: n = ((int) block[zptr[unHi] + d + 1]) - med;
1116: if (n == 0) {
1117: int temp = 0;
1118: temp = zptr[unHi];
1119: zptr[unHi] = zptr[gtHi];
1120: zptr[gtHi] = temp;
1121: gtHi--;
1122: unHi--;
1123: continue;
1124: }
1125: ;
1126: if (n < 0) {
1127: break;
1128: }
1129: unHi--;
1130: }
1131: if (unLo > unHi) {
1132: break;
1133: }
1134: int temp = 0;
1135: temp = zptr[unLo];
1136: zptr[unLo] = zptr[unHi];
1137: zptr[unHi] = temp;
1138: unLo++;
1139: unHi--;
1140: }
1141:
1142: if (gtHi < ltLo) {
1143: stack[sp].ll = lo;
1144: stack[sp].hh = hi;
1145: stack[sp].dd = d + 1;
1146: sp++;
1147: continue;
1148: }
1149:
1150: n = ((ltLo - lo) < (unLo - ltLo)) ? (ltLo - lo)
1151: : (unLo - ltLo);
1152: vswap(lo, unLo - n, n);
1153: m = ((hi - gtHi) < (gtHi - unHi)) ? (hi - gtHi)
1154: : (gtHi - unHi);
1155: vswap(unLo, hi - m + 1, m);
1156:
1157: n = lo + unLo - ltLo - 1;
1158: m = hi - (gtHi - unHi) + 1;
1159:
1160: stack[sp].ll = lo;
1161: stack[sp].hh = n;
1162: stack[sp].dd = d;
1163: sp++;
1164:
1165: stack[sp].ll = n + 1;
1166: stack[sp].hh = m - 1;
1167: stack[sp].dd = d + 1;
1168: sp++;
1169:
1170: stack[sp].ll = m;
1171: stack[sp].hh = hi;
1172: stack[sp].dd = d;
1173: sp++;
1174: }
1175: }
1176:
1177: private void mainSort() {
1178: int i, j, ss, sb;
1179: int[] runningOrder = new int[256];
1180: int[] copy = new int[256];
1181: boolean[] bigDone = new boolean[256];
1182: int c1, c2;
1183: int numQSorted;
1184:
1185: /*
1186: In the various block-sized structures, live data runs
1187: from 0 to last+NUM_OVERSHOOT_BYTES inclusive. First,
1188: set up the overshoot area for block.
1189: */
1190:
1191: // if (verbosity >= 4) fprintf ( stderr, " sort initialise ...\n" );
1192: for (i = 0; i < NUM_OVERSHOOT_BYTES; i++) {
1193: block[last + i + 2] = block[(i % (last + 1)) + 1];
1194: }
1195: for (i = 0; i <= last + NUM_OVERSHOOT_BYTES; i++) {
1196: quadrant[i] = 0;
1197: }
1198:
1199: block[0] = (char) (block[last + 1]);
1200:
1201: if (last < 4000) {
1202: /*
1203: Use simpleSort(), since the full sorting mechanism
1204: has quite a large constant overhead.
1205: */
1206: for (i = 0; i <= last; i++) {
1207: zptr[i] = i;
1208: }
1209: firstAttempt = false;
1210: workDone = workLimit = 0;
1211: simpleSort(0, last, 0);
1212: } else {
1213: numQSorted = 0;
1214: for (i = 0; i <= 255; i++) {
1215: bigDone[i] = false;
1216: }
1217:
1218: for (i = 0; i <= 65536; i++) {
1219: ftab[i] = 0;
1220: }
1221:
1222: c1 = block[0];
1223: for (i = 0; i <= last; i++) {
1224: c2 = block[i + 1];
1225: ftab[(c1 << 8) + c2]++;
1226: c1 = c2;
1227: }
1228:
1229: for (i = 1; i <= 65536; i++) {
1230: ftab[i] += ftab[i - 1];
1231: }
1232:
1233: c1 = block[1];
1234: for (i = 0; i < last; i++) {
1235: c2 = block[i + 2];
1236: j = (c1 << 8) + c2;
1237: c1 = c2;
1238: ftab[j]--;
1239: zptr[ftab[j]] = i;
1240: }
1241:
1242: j = ((block[last + 1]) << 8) + (block[1]);
1243: ftab[j]--;
1244: zptr[ftab[j]] = last;
1245:
1246: /*
1247: Now ftab contains the first loc of every small bucket.
1248: Calculate the running order, from smallest to largest
1249: big bucket.
1250: */
1251:
1252: for (i = 0; i <= 255; i++) {
1253: runningOrder[i] = i;
1254: }
1255:
1256: {
1257: int vv;
1258: int h = 1;
1259: do {
1260: h = 3 * h + 1;
1261: } while (h <= 256);
1262: do {
1263: h = h / 3;
1264: for (i = h; i <= 255; i++) {
1265: vv = runningOrder[i];
1266: j = i;
1267: while ((ftab[((runningOrder[j - h]) + 1) << 8] - ftab[(runningOrder[j
1268: - h]) << 8]) > (ftab[((vv) + 1) << 8] - ftab[(vv) << 8])) {
1269: runningOrder[j] = runningOrder[j - h];
1270: j = j - h;
1271: if (j <= (h - 1)) {
1272: break;
1273: }
1274: }
1275: runningOrder[j] = vv;
1276: }
1277: } while (h != 1);
1278: }
1279:
1280: /*
1281: The main sorting loop.
1282: */
1283: for (i = 0; i <= 255; i++) {
1284:
1285: /*
1286: Process big buckets, starting with the least full.
1287: */
1288: ss = runningOrder[i];
1289:
1290: /*
1291: Complete the big bucket [ss] by quicksorting
1292: any unsorted small buckets [ss, j]. Hopefully
1293: previous pointer-scanning phases have already
1294: completed many of the small buckets [ss, j], so
1295: we don't have to sort them at all.
1296: */
1297: for (j = 0; j <= 255; j++) {
1298: sb = (ss << 8) + j;
1299: if (!((ftab[sb] & SETMASK) == SETMASK)) {
1300: int lo = ftab[sb] & CLEARMASK;
1301: int hi = (ftab[sb + 1] & CLEARMASK) - 1;
1302: if (hi > lo) {
1303: qSort3(lo, hi, 2);
1304: numQSorted += (hi - lo + 1);
1305: if (workDone > workLimit && firstAttempt) {
1306: return;
1307: }
1308: }
1309: ftab[sb] |= SETMASK;
1310: }
1311: }
1312:
1313: /*
1314: The ss big bucket is now done. Record this fact,
1315: and update the quadrant descriptors. Remember to
1316: update quadrants in the overshoot area too, if
1317: necessary. The "if (i < 255)" test merely skips
1318: this updating for the last bucket processed, since
1319: updating for the last bucket is pointless.
1320: */
1321: bigDone[ss] = true;
1322:
1323: if (i < 255) {
1324: int bbStart = ftab[ss << 8] & CLEARMASK;
1325: int bbSize = (ftab[(ss + 1) << 8] & CLEARMASK)
1326: - bbStart;
1327: int shifts = 0;
1328:
1329: while ((bbSize >> shifts) > 65534) {
1330: shifts++;
1331: }
1332:
1333: for (j = 0; j < bbSize; j++) {
1334: int a2update = zptr[bbStart + j];
1335: int qVal = (j >> shifts);
1336: quadrant[a2update] = qVal;
1337: if (a2update < NUM_OVERSHOOT_BYTES) {
1338: quadrant[a2update + last + 1] = qVal;
1339: }
1340: }
1341:
1342: if (!(((bbSize - 1) >> shifts) <= 65535)) {
1343: panic();
1344: }
1345: }
1346:
1347: /*
1348: Now scan this big bucket so as to synthesise the
1349: sorted order for small buckets [t, ss] for all t != ss.
1350: */
1351: for (j = 0; j <= 255; j++) {
1352: copy[j] = ftab[(j << 8) + ss] & CLEARMASK;
1353: }
1354:
1355: for (j = ftab[ss << 8] & CLEARMASK; j < (ftab[(ss + 1) << 8] & CLEARMASK); j++) {
1356: c1 = block[zptr[j]];
1357: if (!bigDone[c1]) {
1358: zptr[copy[c1]] = zptr[j] == 0 ? last
1359: : zptr[j] - 1;
1360: copy[c1]++;
1361: }
1362: }
1363:
1364: for (j = 0; j <= 255; j++) {
1365: ftab[(j << 8) + ss] |= SETMASK;
1366: }
1367: }
1368: }
1369: }
1370:
1371: private void randomiseBlock() {
1372: int i;
1373: int rNToGo = 0;
1374: int rTPos = 0;
1375: for (i = 0; i < 256; i++) {
1376: inUse[i] = false;
1377: }
1378:
1379: for (i = 0; i <= last; i++) {
1380: if (rNToGo == 0) {
1381: rNToGo = (char) rNums[rTPos];
1382: rTPos++;
1383: if (rTPos == 512) {
1384: rTPos = 0;
1385: }
1386: }
1387: rNToGo--;
1388: block[i + 1] ^= ((rNToGo == 1) ? 1 : 0);
1389: // handle 16 bit signed numbers
1390: block[i + 1] &= 0xFF;
1391:
1392: inUse[block[i + 1]] = true;
1393: }
1394: }
1395:
1396: private void doReversibleTransformation() {
1397: int i;
1398:
1399: workLimit = workFactor * last;
1400: workDone = 0;
1401: blockRandomised = false;
1402: firstAttempt = true;
1403:
1404: mainSort();
1405:
1406: if (workDone > workLimit && firstAttempt) {
1407: randomiseBlock();
1408: workLimit = workDone = 0;
1409: blockRandomised = true;
1410: firstAttempt = false;
1411: mainSort();
1412: }
1413:
1414: origPtr = -1;
1415: for (i = 0; i <= last; i++) {
1416: if (zptr[i] == 0) {
1417: origPtr = i;
1418: break;
1419: }
1420: }
1421: ;
1422:
1423: if (origPtr == -1) {
1424: panic();
1425: }
1426: }
1427:
1428: private boolean fullGtU(int i1, int i2) {
1429: int k;
1430: char c1, c2;
1431: int s1, s2;
1432:
1433: c1 = block[i1 + 1];
1434: c2 = block[i2 + 1];
1435: if (c1 != c2) {
1436: return (c1 > c2);
1437: }
1438: i1++;
1439: i2++;
1440:
1441: c1 = block[i1 + 1];
1442: c2 = block[i2 + 1];
1443: if (c1 != c2) {
1444: return (c1 > c2);
1445: }
1446: i1++;
1447: i2++;
1448:
1449: c1 = block[i1 + 1];
1450: c2 = block[i2 + 1];
1451: if (c1 != c2) {
1452: return (c1 > c2);
1453: }
1454: i1++;
1455: i2++;
1456:
1457: c1 = block[i1 + 1];
1458: c2 = block[i2 + 1];
1459: if (c1 != c2) {
1460: return (c1 > c2);
1461: }
1462: i1++;
1463: i2++;
1464:
1465: c1 = block[i1 + 1];
1466: c2 = block[i2 + 1];
1467: if (c1 != c2) {
1468: return (c1 > c2);
1469: }
1470: i1++;
1471: i2++;
1472:
1473: c1 = block[i1 + 1];
1474: c2 = block[i2 + 1];
1475: if (c1 != c2) {
1476: return (c1 > c2);
1477: }
1478: i1++;
1479: i2++;
1480:
1481: k = last + 1;
1482:
1483: do {
1484: c1 = block[i1 + 1];
1485: c2 = block[i2 + 1];
1486: if (c1 != c2) {
1487: return (c1 > c2);
1488: }
1489: s1 = quadrant[i1];
1490: s2 = quadrant[i2];
1491: if (s1 != s2) {
1492: return (s1 > s2);
1493: }
1494: i1++;
1495: i2++;
1496:
1497: c1 = block[i1 + 1];
1498: c2 = block[i2 + 1];
1499: if (c1 != c2) {
1500: return (c1 > c2);
1501: }
1502: s1 = quadrant[i1];
1503: s2 = quadrant[i2];
1504: if (s1 != s2) {
1505: return (s1 > s2);
1506: }
1507: i1++;
1508: i2++;
1509:
1510: c1 = block[i1 + 1];
1511: c2 = block[i2 + 1];
1512: if (c1 != c2) {
1513: return (c1 > c2);
1514: }
1515: s1 = quadrant[i1];
1516: s2 = quadrant[i2];
1517: if (s1 != s2) {
1518: return (s1 > s2);
1519: }
1520: i1++;
1521: i2++;
1522:
1523: c1 = block[i1 + 1];
1524: c2 = block[i2 + 1];
1525: if (c1 != c2) {
1526: return (c1 > c2);
1527: }
1528: s1 = quadrant[i1];
1529: s2 = quadrant[i2];
1530: if (s1 != s2) {
1531: return (s1 > s2);
1532: }
1533: i1++;
1534: i2++;
1535:
1536: if (i1 > last) {
1537: i1 -= last;
1538: i1--;
1539: }
1540: ;
1541: if (i2 > last) {
1542: i2 -= last;
1543: i2--;
1544: }
1545: ;
1546:
1547: k -= 4;
1548: workDone++;
1549: } while (k >= 0);
1550:
1551: return false;
1552: }
1553:
1554: /*
1555: Knuth's increments seem to work better
1556: than Incerpi-Sedgewick here. Possibly
1557: because the number of elems to sort is
1558: usually small, typically <= 20.
1559: */
1560: private int[] incs = { 1, 4, 13, 40, 121, 364, 1093, 3280, 9841,
1561: 29524, 88573, 265720, 797161, 2391484 };
1562:
1563: private void allocateCompressStructures() {
1564: int n = baseBlockSize * blockSize100k;
1565: block = new char[(n + 1 + NUM_OVERSHOOT_BYTES)];
1566: quadrant = new int[(n + NUM_OVERSHOOT_BYTES)];
1567: zptr = new int[n];
1568: ftab = new int[65537];
1569:
1570: if (block == null || quadrant == null || zptr == null
1571: || ftab == null) {
1572: //int totalDraw = (n + 1 + NUM_OVERSHOOT_BYTES) + (n + NUM_OVERSHOOT_BYTES) + n + 65537;
1573: //compressOutOfMemory ( totalDraw, n );
1574: }
1575:
1576: /*
1577: The back end needs a place to store the MTF values
1578: whilst it calculates the coding tables. We could
1579: put them in the zptr array. However, these values
1580: will fit in a short, so we overlay szptr at the
1581: start of zptr, in the hope of reducing the number
1582: of cache misses induced by the multiple traversals
1583: of the MTF values when calculating coding tables.
1584: Seems to improve compression speed by about 1%.
1585: */
1586: // szptr = zptr;
1587:
1588: szptr = new short[2 * n];
1589: }
1590:
1591: private void generateMTFValues() {
1592: char[] yy = new char[256];
1593: int i, j;
1594: char tmp;
1595: char tmp2;
1596: int zPend;
1597: int wr;
1598: int EOB;
1599:
1600: makeMaps();
1601: EOB = nInUse + 1;
1602:
1603: for (i = 0; i <= EOB; i++) {
1604: mtfFreq[i] = 0;
1605: }
1606:
1607: wr = 0;
1608: zPend = 0;
1609: for (i = 0; i < nInUse; i++) {
1610: yy[i] = (char) i;
1611: }
1612:
1613: for (i = 0; i <= last; i++) {
1614: char ll_i;
1615:
1616: ll_i = unseqToSeq[block[zptr[i]]];
1617:
1618: j = 0;
1619: tmp = yy[j];
1620: while (ll_i != tmp) {
1621: j++;
1622: tmp2 = tmp;
1623: tmp = yy[j];
1624: yy[j] = tmp2;
1625: }
1626: ;
1627: yy[0] = tmp;
1628:
1629: if (j == 0) {
1630: zPend++;
1631: } else {
1632: if (zPend > 0) {
1633: zPend--;
1634: while (true) {
1635: switch (zPend % 2) {
1636: case 0:
1637: szptr[wr] = (short) RUNA;
1638: wr++;
1639: mtfFreq[RUNA]++;
1640: break;
1641: case 1:
1642: szptr[wr] = (short) RUNB;
1643: wr++;
1644: mtfFreq[RUNB]++;
1645: break;
1646: }
1647: ;
1648: if (zPend < 2) {
1649: break;
1650: }
1651: zPend = (zPend - 2) / 2;
1652: }
1653: ;
1654: zPend = 0;
1655: }
1656: szptr[wr] = (short) (j + 1);
1657: wr++;
1658: mtfFreq[j + 1]++;
1659: }
1660: }
1661:
1662: if (zPend > 0) {
1663: zPend--;
1664: while (true) {
1665: switch (zPend % 2) {
1666: case 0:
1667: szptr[wr] = (short) RUNA;
1668: wr++;
1669: mtfFreq[RUNA]++;
1670: break;
1671: case 1:
1672: szptr[wr] = (short) RUNB;
1673: wr++;
1674: mtfFreq[RUNB]++;
1675: break;
1676: }
1677: if (zPend < 2) {
1678: break;
1679: }
1680: zPend = (zPend - 2) / 2;
1681: }
1682: }
1683:
1684: szptr[wr] = (short) EOB;
1685: wr++;
1686: mtfFreq[EOB]++;
1687:
1688: nMTF = wr;
1689: }
1690: }
|