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