// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of the License "Eclipse Public License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.eclipse.org/legal/epl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// e32\common\arm\carray.cia

// Machine coded arrays for ARM

// 

//

#include <e32cia.h>

#include "../common.h"

#ifdef __ARRAY_MACHINE_CODED__

extern "C" void PanicBadArrayFindMode();

EXPORT_C __NAKED__ TAny*& RPointerArrayBase::At(TInt /*anIndex*/) const

	{

	asm("ldmia r0, {r2,r3} ");			// r2=iCount, r3=iEntries

	asm("cmp r1, #0 ");					// check anIndex>=0

	asm("cmpge r2, r1 ");				// if so, check iCount>anIndex

	asm("addgt r0, r3, r1, lsl #2 ");	// address of entry = iEntries+4*anIndex

#ifdef __CPU_ARMV6

	asm("ble 1f ");						// avoid conditional return on ARMv6

 	__JUMP(,lr);

#else

 	__JUMP(gt,lr);

#endif

	asm("1: ");

	asm("b  " CSM_Z18PanicBadArrayIndexv);

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::Append(const TAny* /*anEntry*/)

	{

	asm("ldmia r0, {r2,r3,r12} ");		// r2=iCount, r3=iEntries, r12=iAllocated

	asm("cmp r2, r12 ");

	asm("beq ptr_append_1 ");

	asm("ptr_append_0: ");

	asm("str r1, [r3, r2, lsl #2] ");

	asm("add r2, r2, #1 ");

	asm("str r2, [r0] ");

	asm("mov r0, #0 ");

	__JUMP(,lr);

	asm("ptr_append_1: ");

	asm("stmfd sp!, {r0,r1,r2,lr} ");

	asm("bl  " CSM_ZN17RPointerArrayBase4GrowEv);

	asm("cmp r0, #0 ");

	asm("bne ptr_append_2 ");

	asm("ldmfd sp!, {r0,r1,r2,lr} ");

	asm("ldmia r0, {r2, r3} ");

	asm("b ptr_append_0 ");

	asm("ptr_append_2: ");				// error enlarging array

	asm("add sp, sp, #12 ");

	__POPRET("");

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::Find(const TAny* /*anEntry*/) const

	{

	asm("ldmia r0, {r2,r3} ");			// r2=iCount, r3=iEntries

	asm("mov r0, #0 ");					// r0=0 (will be index+1)

	asm("subs r2, r2, #1 ");			// r2=iCount-1

	asm("blt 0f ");

	asm("1: ");

	asm("ldr r12, [r3], #4 ");			// r12=iEntries[r0]

	asm("add r0, r0, #1 ");				// r0 = index+1

	asm("cmp r2, r0 ");					// C=1 iff iCount-1>=index+1 iff index<=iCount-2 iff this isn't last entry

	asm("teq r12, r1 ");				// check for equality, doesn't affect C

	asm("bhi 1b ");						// loop if C=1 & Z=0, i.e. if no match and this isn't last entry

	asm("0: ");

	asm("movne r0, #0 ");				// if no match set r0=0

	asm("sub r0, r0, #1 ");				// r0 was index+1, return index

	__JUMP(,lr);

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::Find(const TAny* /*anEntry*/, TGeneralIdentityRelation /*anIdentity*/) const

	{

	asm("stmfd sp!, {r4-r8,lr} ");

	__EH_FRAME_PUSH2(r4-r8,lr)

	asm("ldmia r0, {r4,r5} ");			// r4=iCount, r5=iEntries

	asm("mvn r6, #0 ");

	asm("mov r7, r1 ");

	asm("mov r8, r2 ");

	asm("subs r4, r4, #1 ");			// r4=iCount-1

	asm("bmi ptr_find2_return ");		// if count=0, return -1

	asm("ptr_find2_loop: ");

	asm("ldr r1, [r5], #4 ");			// r1=pointer to entry r6

	asm("add r6, r6, #1 ");

	asm("mov r0, r7 ");					// r0=anEntry

	__JUMPL(8);

	asm("cmp r0, #0 ");

	asm("bne ptr_find2_return ");		// if equal, return r6

	asm("cmp r6, r4 ");

	asm("blt ptr_find2_loop ");

	asm("mvn r6, #0 ");

	asm("ptr_find2_return: ");			// return r6

	asm("mov r0, r6 ");

	__POPRET("r4-r8,");

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchSigned(TInt /*anEntry*/, TInt& /*anIndex*/) const

	{

	asm("mov r3, #0 ");

	// fall through

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchSigned(TInt /*anEntry*/, TInt& /*anIndex*/, TInt /*aMode*/) const

	{

	asm("stmfd sp!, {r4-r6,lr} ");

	__EH_FRAME_PUSH2(r4-r6,lr)

	asm("mov r6, r2 ");					// r6=&anIndex

	asm("ldmia r0, {r2,r4} ");			// r2=count, r4=iEntries

	asm("bl BinarySearchSigned ");

	asm("str r2, [r6] ");				// store index

	__POPRET("r4-r6,");

// Binary search list of signed integers

// Match value in r1

// List address in r4

// Count in r2

// Match mode in r3

// Return with: r0=0 if match found, r0=-1 otherwise

//				Z flag set if match found, clear if not

//				r2=index of match or next higher

// r5 modified

	asm("BinarySearchSigned: ");

#ifdef _DEBUG

	asm("cmp r3, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );

	asm("bhs PanicBadArrayFindMode ");

#endif

	asm("mov r3, r3, lsl #30 ");		// match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)

	asm("orr r3, r3, #1 ");				// set NOT FOUND flag

	asm("cmp r2, #0 ");					// r2 will be right index

	asm("beq 0f ");

	asm("mov r5, #0 ");					// r5 = left index

	asm("1: ");

	asm("add r12, r2, r5 ");

	asm("mov r12, r12, lsr #1 ");		// r12 = mid index

	asm("ldr r0, [r4, r12, lsl #2] ");	// r0 = entry[mid]

	asm("subs r0, r0, r1 ");			// r0 = entry[mid] - match

	asm("beq 2f ");						// if match branch out

	asm("3: ");

	asm("addlt r5, r12, #1 ");			// else if entry<match left=mid+1

	asm("movgt r2, r12 ");				// else if entry>match right=mid

	asm("subs r0, r2, r5 ");			// right > left ?

	asm("bgt 1b ");						// r0 = 0 when loop terminates

	asm("0: ");

	asm("tst r3, #1 ");					// test not found flag

	asm("mvnnes r0, #0 ");				// if set r0=-1 = KErrNotFound

	__JUMP(,lr);

	asm("2: ");

	asm("bics r3, r3, #1 ");			// clear NOT FOUND flag, test for find mode ANY (Z set if so)

	asm("bne 3b ");						// if not, V=0 (left from subs), N=1 for last, 0 for first, Z=0 => LAST->LT FIRST->GT

	asm("mov r2, r12 ");				// if so, r2 = mid

	__JUMP(,lr);						// and return with r0 = 0

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchUnsigned(TUint /*anEntry*/, TInt& /*anIndex*/) const

	{

	asm("mov r3, #0 ");

	// fall through

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchUnsigned(TUint /*anEntry*/, TInt& /*anIndex*/, TInt /*aMode*/) const

	{

	asm("stmfd sp!, {r4-r6,lr} ");

	__EH_FRAME_PUSH2(r4-r6,lr)

	asm("mov r6, r2 ");					// r6=&anIndex

	asm("ldmia r0, {r2,r4} ");			// r2=count, r4=iEntries

	asm("bl BinarySearchUnsigned ");

	asm("str r2, [r6] ");				// store index

	__POPRET("r4-r6,");

// Binary search list of unsigned integers

// Match value in r1

// List address in r4

// Count in r2

// Match mode in r3

// Return with: r0=0 if match found, r0=-1 otherwise

//				Z flag set if match found, clear if not

//				r2=index of match or next higher

// r5 modified

	asm("BinarySearchUnsigned: ");

#ifdef _DEBUG

	asm("cmp r3, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );

	asm("bhs PanicBadArrayFindMode ");

#endif

	asm("mov r3, r3, lsl #30 ");		// match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)

	asm("orr r3, r3, #1 ");				// set NOT FOUND flag

	asm("cmp r2, #0 ");					// r2 will be right index

	asm("beq 0f ");

	asm("mov r5, #0 ");					// r5 = left index

	asm("1: ");

	asm("add r12, r2, r5 ");

	asm("mov r12, r12, lsr #1 ");		// r12 = mid index

	asm("ldr r0, [r4, r12, lsl #2] ");	// r0 = entry[mid]

	asm("subs r0, r1, r0 ");			// r0 = match - entry[mid]

	asm("beq 2f ");						// if match branch out

	asm("3: ");

	asm("addhi r5, r12, #1 ");			// else if entry<match left=mid+1	HI = C &~ Z

	asm("movlo r2, r12 ");				// else if entry>match right=mid	LO = ~C

	asm("subs r0, r2, r5 ");			// right > left ?

	asm("bgt 1b ");						// r0 = 0 when loop terminates

	asm("0: ");

	asm("tst r3, #1 ");					// test not found flag

	asm("mvnnes r0, #0 ");				// if set r0=-1 = KErrNotFound

	__JUMP(,lr);

	asm("2: ");							// N=0 Z=1 C=1 V=0 r0=0 here

	asm("bics r3, r3, #1 ");			// clear NOT FOUND flag, test for find mode ANY (Z set if so)

	asm("cmpne r3, #0x60000000 ");		// HI if LAST, LO if FIRST

	asm("bne 3b ");						// if not ANY, branch back

	asm("mov r2, r12 ");				// if ANY, r2 = mid

	__JUMP(,lr);						// and return with r0 = 0

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearch(const TAny* /*anEntry*/, TInt& /*anIndex*/, TGeneralLinearOrder /*anOrder*/, TInt /*aMode*/) const

	{

	asm("stmfd sp!, {r2,r4-r11,lr} ");	// store &anIndex, r4-r11, lr

	__EH_FRAME_ADDRESS(sp,4)

	__EH_FRAME_PUSH2(r4-r11,lr)

	asm("ldmia r0, {r5,r6} ");			// r5=count, r6=iEntries

	asm("ldr r11, [sp, #40] ");			// r11 = aMode

	asm("mov r7, r3 ");					// r7=anOrder

	asm("mov r4, r1 ");					// r1=anEntry

	asm("bl BinarySearchPointers ");	// r0=KErrNone if match, KErrNotFound if not

	asm("ldmfd sp!, {r2,r4} ");			// r2=&anIndex, restore r4

	// Dont need to FRAME RESTORE here since there's no barrier here

	asm("str r5, [r2] ");				// store index

	__POPRET("r5-r11,");				// restore r5-r11 and return

// Binary search list of pointers

// Pointer to match value in r4

// List address in r6

// Count in r5

// Pointer to ordering function in r7

// r11 = find mode

// Return with: r0=0 if match found, r0=-1 otherwise

//				Z flag set if match found, clear otherwise

//				r5=index of match or next higher

// r9,r10,r11 modified

	asm("BinarySearchPointers: ");

#ifdef _DEBUG

	asm("cmp r11, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );

	asm("bhs PanicBadArrayFindMode ");

#endif

	asm("movs r11, r11, lsl #30 ");		// match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)

	asm("eorne r11, r11, #0xC0000000 ");	// match mode -> bits 30,31 (00000000=any, 80000000=first, 40000000=last)

	asm("orr r11, r11, #1 ");			// set NOT FOUND flag

	asm("mov r9, lr ");

	asm("cmp r5, #0 ");					// r5 will be right index

	asm("beq 0f ");

	asm("mov r10, #0 ");				// r10 = left index

	asm("1: ");

	asm("add r8, r5, r10 ");

	asm("mov r8, r8, lsr #1 ");			// r8 = mid index

/** the latency of the indirect call should mask the latency of the ldr

	arm1136 requires base register to be valid one cycle early

*/

	asm("mov r0, r4 ");					// r0 points to match value

	asm("ldr r1, [r6, r8, lsl #2] ");	// r1 points to entry[mid]

	__JUMPL(7);							// call ordering function (match, entry)

	asm("cmp r0, #0 ");

	asm("biceq r11, r11, #1 ");			// if match clear NOT FOUND flag

	asm("addeqs r0, r0, r11 ");			// and add match mode to r0 (>0 if LAST, <0 if FIRST, 0 if ANY)

	asm("beq 2f ");						// branch out if match and ANY

	asm("addgt r10, r8, #1 ");			// else if match > entry, left = mid + 1

	asm("movlt r5, r8 ");				// else if match < entry, right = mid

	asm("subs r0, r5, r10 ");			// loop if right > left

	asm("bgt 1b ");						// finish loop with r0 = 0

	asm("0: ");

	asm("tst r11, #1 ");				// test not found flag

	asm("mvnnes r0, #0 ");				// if set r0=-1 = KErrNotFound

	__JUMP(,r9);

	asm("2: ");

	asm("mov r5, r8 ");					// if ANY, r8 = mid

	__JUMP(,r9);						// and return with r0 = 0, Z=1

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqSigned(TInt /*anEntry*/) const

	{

	asm("mov r2, #0 ");

	// fall through

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqSigned(TInt /*anEntry*/, TInt /*aMode*/) const

	{

#ifdef __EABI__

	// sp needs correct alignment

	asm("stmfd sp!, {r4-r6,lr} ");

	__EH_FRAME_PUSH2(r4-r6,lr)

#else

	asm("stmfd sp!, {r4,r5,lr} ");

#endif

	asm("mov r3, r2 ");					// r3 = match mode

	asm("ldmia r0, {r2,r4} ");			// r2=count, r4=iEntries

	asm("bl BinarySearchSigned ");

	asm("moveq r0, r2 ");				// if match r0=match index; if no match, r0=KErrNotFound

#ifdef __EABI__

	__POPRET("r4-r6,");

#else

	__POPRET("r4,r5,");

#endif

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqUnsigned(TUint /*anEntry*/) const

	{

	asm("mov r2, #0 ");

	// fall through

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqUnsigned(TUint /*anEntry*/, TInt /*aMode*/) const

	{

#ifdef __EABI__

	// sp needs correct alignment

	asm("stmfd sp!, {r4-r6,lr} ");

	__EH_FRAME_PUSH2(r4-r6,lr)

#else

	asm("stmfd sp!, {r4,r5,lr} ");

#endif

	asm("mov r3, r2 ");					// r3 = match mode

	asm("ldmia r0, {r2,r4} ");			// r2=count, r4=iEntries

	asm("bl BinarySearchUnsigned ");

	asm("moveq r0, r2 ");				// if match r0=match index; if no match, r0=KErrNotFound

#ifdef __EABI__

	__POPRET("r4-r6,");

#else

	__POPRET("r4,r5,");

#endif

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsq(const TAny* /*anEntry*/, TGeneralLinearOrder /*anOrder*/) const

	{

	asm("mov r3, #0 ");

	// fall through

	}

EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsq(const TAny* /*anEntry*/, TGeneralLinearOrder /*anOrder*/, TInt /*aMode*/) const

	{

	asm("stmfd sp!, {r3-r11,lr} ");

	__EH_FRAME_PUSH2(r4-r6,lr)

	asm("ldmia r0, {r5,r6} ");			// r5=count, r6=iEntries

	asm("mov r11, r3 ");				// r11 = aMode

	asm("mov r7, r2 ");					// r7=anOrder

	asm("mov r4, r1 ");					// r1=anEntry

	asm("bl BinarySearchPointers ");

	asm("moveq r0, r5 ");				// if match, r0=match index

	__POPRET("r3-r11,");

	}

#ifndef __KERNEL_MODE__

EXPORT_C __NAKED__ void RPointerArrayBase::HeapSortSigned()

	{

#ifdef __EABI__

	asm("stmfd sp!, {r4-r10,lr} ");

	__EH_FRAME_PUSH2(r4-r10,lr)

#else

	asm("stmfd sp!, {r4-r9,lr} ");

#endif

	asm("ldmia r0, {r4,r5} ");			// r4=iCount, r5=iEntries

	asm("bl HeapSortSigned ");

#ifdef __EABI__

	__POPRET("r4-r10,");

#else

	__POPRET("r4-r9,");

#endif

	// Heap sort list of signed integers

	// List address in r5, count in r4

	// r4=ss, r6=sh, r7=si

	// r8,r9 modified

	asm("HeapSortSigned: ");

	asm("cmp r4, #1 ");

	__JUMP(le,lr);

	asm("mov r6, r4, lsr #1 ");

	asm("hss_loop_start1: ");

	asm("sub r6, r6, #1 ");

	asm("ldr r7, [r5, r6, lsl #2] ");

	asm("mov r8, r6 ");

	asm("mov r9, r6 ");

	asm("b hss_loop_start2 ");

	asm("hss_loop_inner: ");

	asm("ldr r0, [r5, r8, lsl #2] ");

	asm("str r0, [r5, r9, lsl #2] ");

	asm("mov r9, r8 ");

	asm("hss_loop_start2: ");

	asm("add r8, r8, #1 ");

	asm("add r8, r8, r8 ");

	asm("cmp r8, r4 ");

	asm("bgt hss_loop_inner_end ");

	asm("add r0, r5, r8, lsl #2 ");

	asm("ldmneda r0, {r1,r2} ");

	asm("ldreq r1, [r0, #-4] ");

	asm("subeq r8, r8, #1 ");

	asm("beq hss_loop_inner2 ");

	asm("cmp r1, r2 ");

	asm("subgt r8, r8, #1 ");

	asm("movle r1, r2 ");

	asm("hss_loop_inner2: ");

	asm("cmp r1, r7 ");

	asm("bgt hss_loop_inner ");

	asm("hss_loop_inner_end: ");

	asm("str r7, [r5, r9, lsl #2] ");

	asm("cmp r6, #0 ");

	asm("bne hss_loop_start1 ");

	asm("sub r4, r4, #1 ");

	asm("ldr r7, [r5, r4, lsl #2] ");

	asm("ldr r0, [r5, #0] ");

	asm("str r0, [r5, r4, lsl #2] ");

	asm("cmp r4, #1 ");

	asm("mov r8, r6 ");

	asm("mov r9, r6 ");

	asm("bgt hss_loop_start2 ");

	asm("str r7, [r5, #0] ");

	__JUMP(,lr);

	}

EXPORT_C __NAKED__ void RPointerArrayBase::HeapSortUnsigned()

	{

	asm("stmfd sp!, {r4-r9,lr} ");

	asm("ldmia r0, {r4,r5} ");			// r4=iCount, r5=iEntries

	asm("bl HeapSortUnsigned ");

	__POPRET("r4-r9,");

	}

#endif  // !__KERNEL_MODE__

__NAKED__ void HeapSortUnsigned(TUint* aEntries,TInt aCount)

	{

	asm("stmfd sp!, {r4-r9,lr} ");

	asm("mov r4,r1");			// r4=iCount

	asm("mov r5,r0");			// r5=iEntries

	asm("bl HeapSortUnsigned ");

	__POPRET("r4-r9,");

	// Heap sort list of unsigned integers

	// List address in r5, count in r4

	// r4=ss, r6=sh, r7=si

	// r8,r9 modified

	asm("HeapSortUnsigned: ");

	asm("cmp r4, #1 ");

	__JUMP(le,lr);

	asm("mov r6, r4, lsr #1 ");

	asm("hsu_loop_start1: ");

	asm("sub r6, r6, #1 ");

	asm("ldr r7, [r5, r6, lsl #2] ");

	asm("mov r8, r6 ");

	asm("mov r9, r6 ");

	asm("b hsu_loop_start2 ");

	asm("hsu_loop_inner: ");

	asm("ldr r0, [r5, r8, lsl #2] ");

	asm("str r0, [r5, r9, lsl #2] ");

	asm("mov r9, r8 ");

	asm("hsu_loop_start2: ");

	asm("add r8, r8, #1 ");

	asm("add r8, r8, r8 ");

	asm("cmp r8, r4 ");

	asm("bgt hsu_loop_inner_end ");

	asm("add r0, r5, r8, lsl #2 ");

	asm("ldmneda r0, {r1,r2} ");

	asm("ldreq r1, [r0, #-4] ");

	asm("subeq r8, r8, #1 ");

	asm("beq hsu_loop_inner2 ");

	asm("cmp r1, r2 ");

	asm("subhi r8, r8, #1 ");

	asm("movls r1, r2 ");

	asm("hsu_loop_inner2: ");

	asm("cmp r1, r7 ");

	asm("bhi hsu_loop_inner ");

	asm("hsu_loop_inner_end: ");

	asm("str r7, [r5, r9, lsl #2] ");

	asm("cmp r6, #0 ");

	asm("bne hsu_loop_start1 ");

	asm("sub r4, r4, #1 ");

	asm("ldr r7, [r5, r4, lsl #2] ");

	asm("ldr r0, [r5, #0] ");

	asm("str r0, [r5, r4, lsl #2] ");

	asm("cmp r4, #1 ");

	asm("mov r8, r6 ");

	asm("mov r9, r6 ");

	asm("bgt hsu_loop_start2 ");

	asm("str r7, [r5, #0] ");

	__JUMP(,lr);

	}

#ifndef __KERNEL_MODE__

EXPORT_C __NAKED__ void RPointerArrayBase::HeapSort(TGeneralLinearOrder /*anOrder*/)

	{

	asm("stmfd sp!, {r3-r11,lr} ");

	// r3 is caller save

	__EH_FRAME_ADDRESS(sp,4)

	// we can push the callee save regs

	__EH_FRAME_PUSH2(r4-r11,lr)

	asm("ldmia r0, {r4,r5} ");			// r4=iCount, r5=iEntries

	asm("mov r10, r1 ");				// r10=anOrder

	asm("bl HeapSortPointers ");

	__POPRET("r3-r11,");

	// Heap sort list of pointers

	// List address in r5, count in r4, r10 points to ordering function

	// r4=ss, r6=sh, r7=si

	// r8,r9,r11 modified

	asm("HeapSortPointers: ");

	asm("cmp r4, #1 ");

	__JUMP(le,lr);

	asm("mov r11, lr ");

	asm("mov r6, r4, lsr #1 ");

	asm("hsp_loop_start1: ");

	asm("sub r6, r6, #1 ");

	asm("ldr r7, [r5, r6, lsl #2] ");

	asm("mov r8, r6 ");

	asm("mov r9, r6 ");

	asm("b hsp_loop_start2 ");

	asm("hsp_loop_inner: ");

	asm("ldr r0, [r5, r8, lsl #2] ");

	asm("str r0, [r5, r9, lsl #2] ");

	asm("mov r9, r8 ");

	asm("hsp_loop_start2: ");

	asm("add r8, r8, #1 ");

	asm("add r8, r8, r8 ");

	asm("cmp r8, r4 ");

	asm("bgt hsp_loop_inner_end ");