Source Code Cross Referenced for CBZip2OutputStream.java in  » Security » Bouncy-Castle » org » bouncycastle » apache » bzip2 » Java Source Code / Java DocumentationJava Source Code and Java Documentation

Java Source Code / Java Documentation
1. 6.0 JDK Core
2. 6.0 JDK Modules
3. 6.0 JDK Modules com.sun
4. 6.0 JDK Modules com.sun.java
5. 6.0 JDK Modules sun
6. 6.0 JDK Platform
7. Ajax
8. Apache Harmony Java SE
9. Aspect oriented
10. Authentication Authorization
11. Blogger System
12. Build
13. Byte Code
14. Cache
15. Chart
16. Chat
17. Code Analyzer
18. Collaboration
19. Content Management System
20. Database Client
21. Database DBMS
22. Database JDBC Connection Pool
23. Database ORM
24. Development
25. EJB Server geronimo
26. EJB Server GlassFish
27. EJB Server JBoss 4.2.1
28. EJB Server resin 3.1.5
29. ERP CRM Financial
30. ESB
31. Forum
32. GIS
33. Graphic Library
34. Groupware
35. HTML Parser
36. IDE
37. IDE Eclipse
38. IDE Netbeans
39. Installer
40. Internationalization Localization
41. Inversion of Control
42. Issue Tracking
43. J2EE
44. JBoss
45. JMS
46. JMX
47. Library
48. Mail Clients
49. Net
50. Parser
51. PDF
52. Portal
53. Profiler
54. Project Management
55. Report
56. RSS RDF
57. Rule Engine
58. Science
59. Scripting
60. Search Engine
61. Security
62. Sevlet Container
63. Source Control
64. Swing Library
65. Template Engine
66. Test Coverage
67. Testing
68. UML
69. Web Crawler
70. Web Framework
71. Web Mail
72. Web Server
73. Web Services
74. Web Services apache cxf 2.0.1
75. Web Services AXIS2
76. Wiki Engine
77. Workflow Engines
78. XML
79. XML UI
Java
Java Tutorial
Java Open Source
Jar File Download
Java Articles
Java Products
Java by API
Photoshop Tutorials
Maya Tutorials
Flash Tutorials
3ds-Max Tutorials
Illustrator Tutorials
GIMP Tutorials
C# / C Sharp
C# / CSharp Tutorial
C# / CSharp Open Source
ASP.Net
ASP.NET Tutorial
JavaScript DHTML
JavaScript Tutorial
JavaScript Reference
HTML / CSS
HTML CSS Reference
C / ANSI-C
C Tutorial
C++
C++ Tutorial
Ruby
PHP
Python
Python Tutorial
Python Open Source
SQL Server / T-SQL
SQL Server / T-SQL Tutorial
Oracle PL / SQL
Oracle PL/SQL Tutorial
PostgreSQL
SQL / MySQL
MySQL Tutorial
VB.Net
VB.Net Tutorial
Flash / Flex / ActionScript
VBA / Excel / Access / Word
XML
XML Tutorial
Microsoft Office PowerPoint 2007 Tutorial
Microsoft Office Excel 2007 Tutorial
Microsoft Office Word 2007 Tutorial
Java Source Code / Java Documentation » Security » Bouncy Castle » org.bouncycastle.apache.bzip2 
Source Cross Referenced  Class Diagram Java Document (Java Doc) 


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:        }
www.java2java.com | Contact Us
Copyright 2009 - 12 Demo Source and Support. All rights reserved.
All other trademarks are property of their respective owners.