From 124f869faae3a0f75a3825e6a8e195c17f3c626a Mon Sep 17 00:00:00 2001 From: Andrew Dolgov Date: Thu, 16 Oct 2014 23:34:20 +0400 Subject: initial for idea --- .../com/github/junrar/unpack/ppm/ModelPPM.java | 696 +++++++++++++++++++++ 1 file changed, 696 insertions(+) create mode 100644 org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/ModelPPM.java (limited to 'org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/ModelPPM.java') diff --git a/org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/ModelPPM.java b/org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/ModelPPM.java new file mode 100644 index 0000000..25e20bb --- /dev/null +++ b/org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/ModelPPM.java @@ -0,0 +1,696 @@ +/* + * Copyright (c) 2007 innoSysTec (R) GmbH, Germany. All rights reserved. + * Original author: Edmund Wagner + * Creation date: 31.05.2007 + * + * Source: $HeadURL$ + * Last changed: $LastChangedDate$ + * + * the unrar licence applies to all junrar source and binary distributions + * you are not allowed to use this source to re-create the RAR compression algorithm + * + * Here some html entities which can be used for escaping javadoc tags: + * "&": "&" or "&" + * "<": "<" or "<" + * ">": ">" or ">" + * "@": "@" + */ +package com.github.junrar.unpack.ppm; + +import java.io.IOException; +import java.util.Arrays; + +import com.github.junrar.exception.RarException; +import com.github.junrar.unpack.Unpack; + + +/** + * DOCUMENT ME + * + * @author $LastChangedBy$ + * @version $LastChangedRevision$ + */ +public class ModelPPM +{ + public static final int MAX_O = 64; /* maximum allowed model order */ + + public static final int INT_BITS = 7; + + public static final int PERIOD_BITS = 7; + + public static final int TOT_BITS = INT_BITS + PERIOD_BITS; + + public static final int INTERVAL = 1 << INT_BITS; + + public static final int BIN_SCALE = 1 << TOT_BITS; + + public static final int MAX_FREQ = 124; + + private SEE2Context[][] SEE2Cont = new SEE2Context[25][16]; + + private SEE2Context dummySEE2Cont; + + private PPMContext minContext, medContext, maxContext; + + private State foundState; // found next state transition + + private int numMasked, initEsc, orderFall, maxOrder, runLength, initRL; + + private int[] charMask = new int[256]; + + private int[] NS2Indx = new int[256]; + + private int[] NS2BSIndx = new int[256]; + + private int[] HB2Flag = new int[256]; + + // byte EscCount, PrevSuccess, HiBitsFlag; + private int escCount, prevSuccess, hiBitsFlag; + + private int[][] binSumm = new int[128][64]; // binary SEE-contexts + + private RangeCoder coder = new RangeCoder(); + + private SubAllocator subAlloc = new SubAllocator(); + + private static int InitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, + 0x64A1, 0x5ABC, 0x6632, 0x6051 }; + + // Temp fields + private final State tempState1 = new State(null); + private final State tempState2 = new State(null); + private final State tempState3 = new State(null); + private final State tempState4 = new State(null); + private final StateRef tempStateRef1 = new StateRef(); + private final StateRef tempStateRef2 = new StateRef(); + private final PPMContext tempPPMContext1 = new PPMContext(null); + private final PPMContext tempPPMContext2 = new PPMContext(null); + private final PPMContext tempPPMContext3 = new PPMContext(null); + private final PPMContext tempPPMContext4 = new PPMContext(null); + private final int[] ps = new int[MAX_O]; + + public ModelPPM() + { + minContext = null; + maxContext = null; + medContext = null; + } + + public SubAllocator getSubAlloc() + { + return subAlloc; + } + + private void restartModelRare() + { + Arrays.fill(charMask, 0); + subAlloc.initSubAllocator(); + initRL = -(maxOrder < 12 ? maxOrder : 12) - 1; + int addr = subAlloc.allocContext(); + minContext.setAddress(addr); + maxContext.setAddress(addr); + minContext.setSuffix(0); + orderFall = maxOrder; + minContext.setNumStats(256); + minContext.getFreqData().setSummFreq(minContext.getNumStats()+1); + + addr = subAlloc.allocUnits(256 / 2); + foundState.setAddress(addr); + minContext.getFreqData().setStats(addr); + + State state = new State(subAlloc.getHeap()); + addr = minContext.getFreqData().getStats(); + runLength = initRL; + prevSuccess = 0; + for (int i = 0; i < 256; i++) { + state.setAddress(addr + i * State.size); + state.setSymbol(i); + state.setFreq(1); + state.setSuccessor(0); + } + + for (int i = 0; i < 128; i++) { + for (int k = 0; k < 8; k++) { + for (int m = 0; m < 64; m += 8) { + binSumm[i][k + m] = BIN_SCALE - InitBinEsc[k] / (i + 2); + } + } + } + for (int i = 0; i < 25; i++) { + for (int k = 0; k < 16; k++) { + SEE2Cont[i][k].init(5 * i + 10); + } + } + } + + private void startModelRare(int MaxOrder) + { + int i, k, m, Step; + escCount = 1; + this.maxOrder = MaxOrder; + restartModelRare(); + // Bug Fixed + NS2BSIndx[0] = 0; + NS2BSIndx[1] = 2; + for (int j = 0; j < 9; j++) { + NS2BSIndx[2 + j] = 4; + } + for (int j = 0; j < 256 - 11; j++) { + NS2BSIndx[11 + j] = 6; + } + for (i = 0; i < 3; i++) { + NS2Indx[i] = i; + } + for (m = i, k = 1, Step = 1; i < 256; i++) { + NS2Indx[i] = m; + if ((--k) == 0) { + k = ++Step; + m++; + } + } + for (int j = 0; j < 0x40; j++) { + HB2Flag[j] = 0; + } + for (int j = 0; j < 0x100 - 0x40; j++) { + HB2Flag[0x40 + j] = 0x08; + } + dummySEE2Cont.setShift(PERIOD_BITS); + + } + + private void clearMask() + { + escCount = 1; + Arrays.fill(charMask, 0); + } + + public boolean decodeInit(Unpack unpackRead, int escChar/* ref */) + throws IOException, RarException + { + + int MaxOrder = unpackRead.getChar() & 0xff; + boolean reset = ((MaxOrder & 0x20) != 0); + + int MaxMB = 0; + if (reset) { + MaxMB = unpackRead.getChar(); + } else { + if (subAlloc.GetAllocatedMemory() == 0) { + return (false); + } + } + if ((MaxOrder & 0x40) != 0) { + escChar = unpackRead.getChar(); + unpackRead.setPpmEscChar(escChar); + } + coder.initDecoder(unpackRead); + if (reset) { + MaxOrder = (MaxOrder & 0x1f) + 1; + if (MaxOrder > 16) { + MaxOrder = 16 + (MaxOrder - 16) * 3; + } + if (MaxOrder == 1) { + subAlloc.stopSubAllocator(); + return (false); + } + subAlloc.startSubAllocator(MaxMB + 1); + minContext = new PPMContext(getHeap()); + medContext = new PPMContext(getHeap()); + maxContext = new PPMContext(getHeap()); + foundState = new State(getHeap()); + dummySEE2Cont = new SEE2Context(); + for (int i = 0; i < 25; i++) { + for (int j = 0; j < 16; j++) { + SEE2Cont[i][j] = new SEE2Context(); + } + } + startModelRare(MaxOrder); + } + return (minContext.getAddress() != 0); + } + + public int decodeChar() throws IOException, RarException + { + // Debug + //subAlloc.dumpHeap(); + + if (minContext.getAddress() <= subAlloc.getPText() + || minContext.getAddress() > subAlloc.getHeapEnd()) { + return (-1); + } + + if (minContext.getNumStats() != 1) { + if (minContext.getFreqData().getStats() <= subAlloc.getPText() + || minContext.getFreqData().getStats() > subAlloc.getHeapEnd()) { + return (-1); + } + if (!minContext.decodeSymbol1(this)) { + return (-1); + } + } else { + minContext.decodeBinSymbol(this); + } + coder.decode(); + while (foundState.getAddress() == 0) { + coder.ariDecNormalize(); + do { + orderFall++; + minContext.setAddress(minContext.getSuffix());// =MinContext->Suffix; + if (minContext.getAddress() <= subAlloc.getPText() + || minContext.getAddress() > subAlloc.getHeapEnd()) { + return (-1); + } + } while (minContext.getNumStats() == numMasked); + if (!minContext.decodeSymbol2(this)) { + return (-1); + } + coder.decode(); + } + int Symbol = foundState.getSymbol(); + if ((orderFall == 0) && foundState.getSuccessor() > subAlloc.getPText()) { + // MinContext=MaxContext=FoundState->Successor; + int addr = foundState.getSuccessor(); + minContext.setAddress(addr); + maxContext.setAddress(addr); + } else { + updateModel(); + //this.foundState.setAddress(foundState.getAddress());//TODO just 4 debugging + if (escCount == 0) { + clearMask(); + } + } + coder.ariDecNormalize();// ARI_DEC_NORMALIZE(Coder.code,Coder.low,Coder.range,Coder.UnpackRead); + return (Symbol); + } + + public SEE2Context[][] getSEE2Cont() + { + return SEE2Cont; + } + + public SEE2Context getDummySEE2Cont() + { + return dummySEE2Cont; + } + + public int getInitRL() + { + return initRL; + } + + public void setEscCount(int escCount) + { + this.escCount = escCount&0xff; + } + + public int getEscCount() + { + return escCount; + } + + public void incEscCount(int dEscCount) { + setEscCount(getEscCount() + dEscCount); + } + + public int[] getCharMask() + { + return charMask; + } + + public int getNumMasked() + { + return numMasked; + } + + public void setNumMasked(int numMasked) + { + this.numMasked = numMasked; + } + + public void setPrevSuccess(int prevSuccess) + { + this.prevSuccess = prevSuccess&0xff; + } + + public int getInitEsc() + { + return initEsc; + } + + public void setInitEsc(int initEsc) + { + this.initEsc = initEsc; + } + + public void setRunLength(int runLength) + { + this.runLength = runLength; + } + + public int getRunLength() + { + return runLength; + } + + public void incRunLength(int dRunLength) { + setRunLength(getRunLength() + dRunLength); + } + + public int getPrevSuccess() + { + return prevSuccess; + } + + public int getHiBitsFlag() + { + return hiBitsFlag; + } + + public void setHiBitsFlag(int hiBitsFlag) + { + this.hiBitsFlag = hiBitsFlag&0xff; + } + + public int[][] getBinSumm() + { + return binSumm; + } + + public RangeCoder getCoder() + { + return coder; + } + + public int[] getHB2Flag() + { + return HB2Flag; + } + + public int[] getNS2BSIndx() + { + return NS2BSIndx; + } + + public int[] getNS2Indx() + { + return NS2Indx; + } + + public State getFoundState() + { + return foundState; + } + + public byte[] getHeap() + { + return subAlloc.getHeap(); + } + + public int getOrderFall() + { + return orderFall; + } + + private int /* ppmcontext ptr */createSuccessors(boolean Skip, + State p1 /* state ptr */) { + //State upState = tempState1.init(null); + StateRef upState = tempStateRef2; + State tempState = tempState1.init(getHeap()); + + // PPM_CONTEXT* pc=MinContext, * UpBranch=FoundState->Successor; + PPMContext pc = tempPPMContext1.init(getHeap()); + pc.setAddress(minContext.getAddress()); + PPMContext upBranch = tempPPMContext2.init(getHeap()); + upBranch.setAddress(foundState.getSuccessor()); + + // STATE * p, * ps[MAX_O], ** pps=ps; + State p = tempState2.init(getHeap()); + int pps = 0; + + boolean noLoop = false; + + if (!Skip) { + ps[pps++] = foundState.getAddress();// *pps++ = FoundState; + if (pc.getSuffix() == 0) { + noLoop = true; + } + } + if (!noLoop) { + boolean loopEntry = false; + if (p1.getAddress() != 0) { + p.setAddress(p1.getAddress()); + pc.setAddress(pc.getSuffix());// =pc->Suffix; + loopEntry = true; + } + do { + if (!loopEntry) { + pc.setAddress(pc.getSuffix());// pc=pc->Suffix; + if (pc.getNumStats() != 1) { + p.setAddress(pc.getFreqData().getStats());// p=pc->U.Stats + if (p.getSymbol() != foundState.getSymbol()) { + do { + p.incAddress(); + } while (p.getSymbol() != foundState.getSymbol()); + } + } else { + p.setAddress(pc.getOneState().getAddress());// p=&(pc->OneState); + } + }// LOOP_ENTRY: + loopEntry = false; + if (p.getSuccessor() != upBranch.getAddress()) { + pc.setAddress(p.getSuccessor());// =p->Successor; + break; + } + ps[pps++] = p.getAddress(); + } while (pc.getSuffix() != 0); + + } // NO_LOOP: + if (pps == 0) { + return pc.getAddress(); + } + upState.setSymbol(getHeap()[upBranch.getAddress()]);// UpState.Symbol=*(byte*) + // UpBranch; + // UpState.Successor=(PPM_CONTEXT*) (((byte*) UpBranch)+1); + upState.setSuccessor(upBranch.getAddress() + 1); //TODO check if +1 necessary + if (pc.getNumStats() != 1) { + if (pc.getAddress() <= subAlloc.getPText()) { + return (0); + } + p.setAddress(pc.getFreqData().getStats()); + if (p.getSymbol() != upState.getSymbol()) { + do { + p.incAddress(); + } while (p.getSymbol() != upState.getSymbol()); + } + int cf = p.getFreq() - 1; + int s0 = pc.getFreqData().getSummFreq() - pc.getNumStats() - cf; + // UpState.Freq=1+((2*cf <= s0)?(5*cf > s0):((2*cf+3*s0-1)/(2*s0))); + upState.setFreq(1 + ((2 * cf <= s0) ? (5 * cf > s0 ? 1 : 0) : + ((2 * cf + 3 * s0 - 1) / (2 * s0)))); + } else { + upState.setFreq(pc.getOneState().getFreq());// UpState.Freq=pc->OneState.Freq; + } + do { + // pc = pc->createChild(this,*--pps,UpState); + tempState.setAddress(ps[--pps]); + pc.setAddress(pc.createChild(this, tempState, upState)); + if (pc.getAddress() == 0) { + return 0; + } + } while (pps != 0); + return pc.getAddress(); + } + + private void updateModelRestart() + { + restartModelRare(); + escCount = 0; + } + + private void updateModel() + { + //System.out.println("ModelPPM.updateModel()"); + // STATE fs = *FoundState, *p = NULL; + StateRef fs = tempStateRef1; + fs.setValues(foundState); + State p = tempState3.init(getHeap()); + State tempState = tempState4.init(getHeap()); + + PPMContext pc = tempPPMContext3.init(getHeap()); + PPMContext successor = tempPPMContext4.init(getHeap()); + + int ns1, ns, cf, sf, s0; + pc.setAddress(minContext.getSuffix()); + if (fs.getFreq() < MAX_FREQ / 4 && pc.getAddress() != 0) { + if (pc.getNumStats() != 1) { + p.setAddress(pc.getFreqData().getStats()); + if (p.getSymbol() != fs.getSymbol()) { + do { + p.incAddress(); + } while (p.getSymbol() != fs.getSymbol()); + tempState.setAddress(p.getAddress() - State.size); + if (p.getFreq() >= tempState.getFreq()) { + State.ppmdSwap(p, tempState); + p.decAddress(); + } + } + if (p.getFreq() < MAX_FREQ - 9) { + p.incFreq(2); + pc.getFreqData().incSummFreq(2); + } + } else { + p.setAddress(pc.getOneState().getAddress()); + if (p.getFreq() < 32) { + p.incFreq(1); + } + } + } + if (orderFall == 0) { + foundState.setSuccessor(createSuccessors(true, p)); + minContext.setAddress(foundState.getSuccessor()); + maxContext.setAddress(foundState.getSuccessor()); + if (minContext.getAddress() == 0) { + updateModelRestart(); + return; + } + return; + } + subAlloc.getHeap()[subAlloc.getPText()] = (byte)fs.getSymbol(); + subAlloc.incPText(); + successor.setAddress(subAlloc.getPText()); + if (subAlloc.getPText() >= subAlloc.getFakeUnitsStart()) { + updateModelRestart(); + return; + } +// // Debug +// subAlloc.dumpHeap(); + if (fs.getSuccessor() != 0) { + if (fs.getSuccessor() <= subAlloc.getPText()) { + fs.setSuccessor(createSuccessors(false, p)); + if (fs.getSuccessor() == 0) { + updateModelRestart(); + return; + } + } + if (--orderFall == 0) { + successor.setAddress(fs.getSuccessor()); + if (maxContext.getAddress() != minContext.getAddress()) { + subAlloc.decPText(1); + } + } + } + else { + foundState.setSuccessor(successor.getAddress()); + fs.setSuccessor(minContext); + } +// // Debug +// subAlloc.dumpHeap(); + ns = minContext.getNumStats(); + s0 = minContext.getFreqData().getSummFreq() - (ns) - (fs.getFreq() - 1); + for (pc.setAddress(maxContext.getAddress()); + pc.getAddress() != minContext.getAddress(); + pc.setAddress(pc.getSuffix())) { + if ((ns1 = pc.getNumStats()) != 1) { + if ((ns1 & 1) == 0) { + //System.out.println(ns1); + pc.getFreqData().setStats( + subAlloc.expandUnits(pc.getFreqData().getStats(), + ns1 >>> 1)); + if (pc.getFreqData().getStats() == 0) { + updateModelRestart(); + return; + } + } + // bug fixed +// int sum = ((2 * ns1 < ns) ? 1 : 0) + +// 2 * ((4 * ((ns1 <= ns) ? 1 : 0)) & ((pc.getFreqData() +// .getSummFreq() <= 8 * ns1) ? 1 : 0)); + int sum = ((2 * ns1 < ns) ? 1 : 0) + 2 * ( + ((4 * ns1 <= ns) ? 1 : 0) & + ((pc.getFreqData().getSummFreq() <= 8 * ns1) ? 1 : 0) + ); + pc.getFreqData().incSummFreq(sum); + } + else { + p.setAddress(subAlloc.allocUnits(1)); + if (p.getAddress() == 0) { + updateModelRestart(); + return; + } + p.setValues(pc.getOneState()); + pc.getFreqData().setStats(p); + if (p.getFreq() < MAX_FREQ / 4 - 1) { + p.incFreq(p.getFreq()); + } + else { + p.setFreq(MAX_FREQ - 4); + } + pc.getFreqData().setSummFreq( + (p.getFreq() + initEsc + (ns > 3 ? 1 : 0))); + } + cf = 2 * fs.getFreq() * (pc.getFreqData().getSummFreq() + 6); + sf = s0 + pc.getFreqData().getSummFreq(); + if (cf < 6 * sf) { + cf = 1 + (cf > sf ? 1 : 0) + (cf >= 4 * sf ? 1 : 0); + pc.getFreqData().incSummFreq(3); + } + else { + cf = 4 + (cf >= 9 * sf ? 1 : 0) + (cf >= 12 * sf ? 1 : 0) + + (cf >= 15 * sf ? 1 : 0); + pc.getFreqData().incSummFreq(cf); + } + p.setAddress(pc.getFreqData().getStats() + ns1*State.size); + p.setSuccessor(successor); + p.setSymbol(fs.getSymbol()); + p.setFreq(cf); + pc.setNumStats(++ns1); + } + + int address = fs.getSuccessor(); + maxContext.setAddress(address); + minContext.setAddress(address); + //TODO-----debug +// int pos = minContext.getFreqData().getStats(); +// State a = new State(getHeap()); +// a.setAddress(pos); +// pos+=State.size; +// a.setAddress(pos); + //--dbg end + return; + } + + // Debug + public String toString() { + StringBuilder buffer = new StringBuilder(); + buffer.append("ModelPPM["); + buffer.append("\n numMasked="); + buffer.append(numMasked); + buffer.append("\n initEsc="); + buffer.append(initEsc); + buffer.append("\n orderFall="); + buffer.append(orderFall); + buffer.append("\n maxOrder="); + buffer.append(maxOrder); + buffer.append("\n runLength="); + buffer.append(runLength); + buffer.append("\n initRL="); + buffer.append(initRL); + buffer.append("\n escCount="); + buffer.append(escCount); + buffer.append("\n prevSuccess="); + buffer.append(prevSuccess); + buffer.append("\n foundState="); + buffer.append(foundState); + buffer.append("\n coder="); + buffer.append(coder); + buffer.append("\n subAlloc="); + buffer.append(subAlloc); + buffer.append("\n]"); + return buffer.toString(); + } + + // Debug +// public void dumpHeap() { +// subAlloc.dumpHeap(); +// } +} -- cgit v1.2.3