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/SubAllocator.java | 427 +++++++++++++++++++++ 1 file changed, 427 insertions(+) create mode 100644 org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/SubAllocator.java (limited to 'org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/SubAllocator.java') diff --git a/org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/SubAllocator.java b/org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/SubAllocator.java new file mode 100644 index 0000000..8844736 --- /dev/null +++ b/org.fox.ttcomics/src/main/java/com/github/junrar/unpack/ppm/SubAllocator.java @@ -0,0 +1,427 @@ +/* + * 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.util.Arrays; + +/** + * DOCUMENT ME + * + * @author $LastChangedBy$ + * @version $LastChangedRevision$ + */ +public class SubAllocator { + public static final int N1 = 4, N2 = 4, N3 = 4, N4 = (128 + 3 - 1 * N1 - 2 + * N2 - 3 * N3) / 4; + + public static final int N_INDEXES = N1 + N2 + N3 + N4; + + public static final int UNIT_SIZE = Math.max(PPMContext.size, + RarMemBlock.size); + + public static final int FIXED_UNIT_SIZE = 12; + + private int subAllocatorSize; + + // byte Indx2Units[N_INDEXES], Units2Indx[128], GlueCount; + private int[] indx2Units = new int[N_INDEXES]; + private int[] units2Indx = new int[128]; + private int glueCount; + + // byte *HeapStart,*LoUnit, *HiUnit; + private int heapStart, loUnit, hiUnit; + + private final RarNode[] freeList = new RarNode[N_INDEXES]; + + // byte *pText, *UnitsStart,*HeapEnd,*FakeUnitsStart; + private int pText, unitsStart, heapEnd, fakeUnitsStart; + + private byte[] heap; + + private int freeListPos; + + private int tempMemBlockPos; + + // Temp fields + private RarNode tempRarNode = null; + private RarMemBlock tempRarMemBlock1 = null; + private RarMemBlock tempRarMemBlock2 = null; + private RarMemBlock tempRarMemBlock3 = null; + + public SubAllocator() { + clean(); + } + + public void clean() { + subAllocatorSize = 0; + } + + private void insertNode(int p/* rarnode ptr */, int indx) { + RarNode temp = tempRarNode; + temp.setAddress(p); + temp.setNext(freeList[indx].getNext()); + freeList[indx].setNext(temp); + } + + public void incPText() { + pText++; + } + + private int removeNode(int indx) { + int retVal = freeList[indx].getNext(); + RarNode temp = tempRarNode; + temp.setAddress(retVal); + freeList[indx].setNext(temp.getNext()); + return retVal; + } + + private int U2B(int NU) { + return /* 8*NU+4*NU */UNIT_SIZE * NU; + } + + /* memblockptr */ + private int MBPtr(int BasePtr, int Items) { + return (BasePtr + U2B(Items)); + } + + private void splitBlock(int pv/* ptr */, int oldIndx, int newIndx) { + int i, uDiff = indx2Units[oldIndx] - indx2Units[newIndx]; + int p = pv + U2B(indx2Units[newIndx]); + if (indx2Units[i = units2Indx[uDiff - 1]] != uDiff) { + insertNode(p, --i); + p += U2B(i = indx2Units[i]); + uDiff -= i; + } + insertNode(p, units2Indx[uDiff - 1]); + } + + public void stopSubAllocator() { + if (subAllocatorSize != 0) { + subAllocatorSize = 0; + heap = null; + heapStart = 1; + // rarfree(HeapStart); + // Free temp fields + tempRarNode = null; + tempRarMemBlock1 = null; + tempRarMemBlock2 = null; + tempRarMemBlock3 = null; + } + } + + public int GetAllocatedMemory() { + return subAllocatorSize; + }; + + public boolean startSubAllocator(int SASize) { + int t = SASize << 20; + if (subAllocatorSize == t) { + return true; + } + stopSubAllocator(); + int allocSize = t / FIXED_UNIT_SIZE * UNIT_SIZE + UNIT_SIZE; + + // adding space for freelist (needed for poiters) + // 1+ for null pointer + int realAllocSize = 1 + allocSize + 4 * N_INDEXES; + // adding space for an additional memblock + tempMemBlockPos = realAllocSize; + realAllocSize += RarMemBlock.size; + + heap = new byte[realAllocSize]; + heapStart = 1; + heapEnd = heapStart + allocSize - UNIT_SIZE; + subAllocatorSize = t; + // Bug fixed + freeListPos = heapStart + allocSize; + assert (realAllocSize - tempMemBlockPos == RarMemBlock.size) : realAllocSize + + " " + tempMemBlockPos + " " + RarMemBlock.size; + + // Init freeList + for (int i = 0, pos = freeListPos; i < freeList.length; i++, pos += RarNode.size) { + freeList[i] = new RarNode(heap); + freeList[i].setAddress(pos); + } + + // Init temp fields + tempRarNode = new RarNode(heap); + tempRarMemBlock1 = new RarMemBlock(heap); + tempRarMemBlock2 = new RarMemBlock(heap); + tempRarMemBlock3 = new RarMemBlock(heap); + + return true; + } + + private void glueFreeBlocks() { + RarMemBlock s0 = tempRarMemBlock1; + s0.setAddress(tempMemBlockPos); + RarMemBlock p = tempRarMemBlock2; + RarMemBlock p1 = tempRarMemBlock3; + int i, k, sz; + if (loUnit != hiUnit) { + heap[loUnit] = 0; + } + for (i = 0, s0.setPrev(s0), s0.setNext(s0); i < N_INDEXES; i++) { + while (freeList[i].getNext() != 0) { + p.setAddress(removeNode(i));// =(RAR_MEM_BLK*)RemoveNode(i); + p.insertAt(s0);// p->insertAt(&s0); + p.setStamp(0xFFFF);// p->Stamp=0xFFFF; + p.setNU(indx2Units[i]);// p->NU=Indx2Units[i]; + } + } + for (p.setAddress(s0.getNext()); p.getAddress() != s0.getAddress(); p + .setAddress(p.getNext())) { + // while ((p1=MBPtr(p,p->NU))->Stamp == 0xFFFF && int(p->NU)+p1->NU + // < 0x10000) + // Bug fixed + p1.setAddress(MBPtr(p.getAddress(), p.getNU())); + while (p1.getStamp() == 0xFFFF && p.getNU() + p1.getNU() < 0x10000) { + p1.remove(); + p.setNU(p.getNU() + p1.getNU());// ->NU += p1->NU; + p1.setAddress(MBPtr(p.getAddress(), p.getNU())); + } + } + // while ((p=s0.next) != &s0) + // Bug fixed + p.setAddress(s0.getNext()); + while (p.getAddress() != s0.getAddress()) { + for (p.remove(), sz = p.getNU(); sz > 128; sz -= 128, p + .setAddress(MBPtr(p.getAddress(), 128))) { + insertNode(p.getAddress(), N_INDEXES - 1); + } + if (indx2Units[i = units2Indx[sz - 1]] != sz) { + k = sz - indx2Units[--i]; + insertNode(MBPtr(p.getAddress(), sz - k), k - 1); + } + insertNode(p.getAddress(), i); + p.setAddress(s0.getNext()); + } + } + + private int allocUnitsRare(int indx) { + if (glueCount == 0) { + glueCount = 255; + glueFreeBlocks(); + if (freeList[indx].getNext() != 0) { + return removeNode(indx); + } + } + int i = indx; + do { + if (++i == N_INDEXES) { + glueCount--; + i = U2B(indx2Units[indx]); + int j = FIXED_UNIT_SIZE * indx2Units[indx]; + if (fakeUnitsStart - pText > j) { + fakeUnitsStart -= j; + unitsStart -= i; + return unitsStart; + } + return (0); + } + } while (freeList[i].getNext() == 0); + int retVal = removeNode(i); + splitBlock(retVal, i, indx); + return retVal; + } + + public int allocUnits(int NU) { + int indx = units2Indx[NU - 1]; + if (freeList[indx].getNext() != 0) { + return removeNode(indx); + } + int retVal = loUnit; + loUnit += U2B(indx2Units[indx]); + if (loUnit <= hiUnit) { + return retVal; + } + loUnit -= U2B(indx2Units[indx]); + return allocUnitsRare(indx); + } + + public int allocContext() { + if (hiUnit != loUnit) + return (hiUnit -= UNIT_SIZE); + if (freeList[0].getNext() != 0) { + return removeNode(0); + } + return allocUnitsRare(0); + } + + public int expandUnits(int oldPtr, int OldNU) { + int i0 = units2Indx[OldNU - 1]; + int i1 = units2Indx[OldNU - 1 + 1]; + if (i0 == i1) { + return oldPtr; + } + int ptr = allocUnits(OldNU + 1); + if (ptr != 0) { + // memcpy(ptr,OldPtr,U2B(OldNU)); + System.arraycopy(heap, oldPtr, heap, ptr, U2B(OldNU)); + insertNode(oldPtr, i0); + } + return ptr; + } + + public int shrinkUnits(int oldPtr, int oldNU, int newNU) { + // System.out.println("SubAllocator.shrinkUnits(" + OldPtr + ", " + + // OldNU + ", " + NewNU + ")"); + int i0 = units2Indx[oldNU - 1]; + int i1 = units2Indx[newNU - 1]; + if (i0 == i1) { + return oldPtr; + } + if (freeList[i1].getNext() != 0) { + int ptr = removeNode(i1); + // memcpy(ptr,OldPtr,U2B(NewNU)); + // for (int i = 0; i < U2B(NewNU); i++) { + // heap[ptr + i] = heap[OldPtr + i]; + // } + System.arraycopy(heap, oldPtr, heap, ptr, U2B(newNU)); + insertNode(oldPtr, i0); + return ptr; + } else { + splitBlock(oldPtr, i0, i1); + return oldPtr; + } + } + + public void freeUnits(int ptr, int OldNU) { + insertNode(ptr, units2Indx[OldNU - 1]); + } + + public int getFakeUnitsStart() { + return fakeUnitsStart; + } + + public void setFakeUnitsStart(int fakeUnitsStart) { + this.fakeUnitsStart = fakeUnitsStart; + } + + public int getHeapEnd() { + return heapEnd; + } + + public int getPText() { + return pText; + } + + public void setPText(int text) { + pText = text; + } + + public void decPText(int dPText) { + setPText(getPText() - dPText); + } + + public int getUnitsStart() { + return unitsStart; + } + + public void setUnitsStart(int unitsStart) { + this.unitsStart = unitsStart; + } + + public void initSubAllocator() { + int i, k; + Arrays + .fill(heap, freeListPos, freeListPos + sizeOfFreeList(), + (byte) 0); + + pText = heapStart; + + int size2 = FIXED_UNIT_SIZE + * (subAllocatorSize / 8 / FIXED_UNIT_SIZE * 7); + int realSize2 = size2 / FIXED_UNIT_SIZE * UNIT_SIZE; + int size1 = subAllocatorSize - size2; + int realSize1 = size1 / FIXED_UNIT_SIZE * UNIT_SIZE + size1 + % FIXED_UNIT_SIZE; + hiUnit = heapStart + subAllocatorSize; + loUnit = unitsStart = heapStart + realSize1; + fakeUnitsStart = heapStart + size1; + hiUnit = loUnit + realSize2; + + for (i = 0, k = 1; i < N1; i++, k += 1) { + indx2Units[i] = k & 0xff; + } + for (k++; i < N1 + N2; i++, k += 2) { + indx2Units[i] = k & 0xff; + } + for (k++; i < N1 + N2 + N3; i++, k += 3) { + indx2Units[i] = k & 0xff; + } + for (k++; i < (N1 + N2 + N3 + N4); i++, k += 4) { + indx2Units[i] = k & 0xff; + } + + for (glueCount = 0, k = 0, i = 0; k < 128; k++) { + i += ((indx2Units[i] < (k + 1)) ? 1 : 0); + units2Indx[k] = i & 0xff; + } + + } + + private int sizeOfFreeList() { + return freeList.length * RarNode.size; + } + + public byte[] getHeap() { + return heap; + } + + // Debug + // public void dumpHeap() { + // File file = new File("P:\\test\\heapdumpj"); + // OutputStream out = null; + // try { + // out = new FileOutputStream(file); + // out.write(heap, heapStart, heapEnd - heapStart); + // out.flush(); + // System.out.println("Heap dumped to " + file.getAbsolutePath()); + // } + // catch (IOException e) { + // e.printStackTrace(); + // } + // finally { + // FileUtil.close(out); + // } + // } + + // Debug + public String toString() { + StringBuilder buffer = new StringBuilder(); + buffer.append("SubAllocator["); + buffer.append("\n subAllocatorSize="); + buffer.append(subAllocatorSize); + buffer.append("\n glueCount="); + buffer.append(glueCount); + buffer.append("\n heapStart="); + buffer.append(heapStart); + buffer.append("\n loUnit="); + buffer.append(loUnit); + buffer.append("\n hiUnit="); + buffer.append(hiUnit); + buffer.append("\n pText="); + buffer.append(pText); + buffer.append("\n unitsStart="); + buffer.append(unitsStart); + buffer.append("\n]"); + return buffer.toString(); + } + +} -- cgit v1.2.3