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