/*
 * 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:
 * "&":  "&#038;" or "&amp;"
 * "<":  "&#060;" or "&lt;"
 * ">":  "&#062;" or "&gt;"
 * "@":  "&#064;" 
 */
package com.innosystec.unrar.unpack.ppm;

import com.classpath.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();

		do
		{
			try
			{
				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;
			}
			catch(OutOfMemoryError oome)
			{
				if(SASize > 1)
				{
					SASize--;
					t = SASize << 20;
				}
				else
				{
					throw new RuntimeException("Consider this as OutOfMemoryError");
				}
			}
		}
		while(heap == null);

		// 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() {
//        FileConnection file = new FileConnection("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()
	{
		StringBuffer buffer = new StringBuffer();
		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();
	}
}
