1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/kernelhwsrv/kernel/eka/common/arm/carray.cia Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,1209 @@
1.4 +// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of the License "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +// e32\common\arm\carray.cia
1.18 +// Machine coded arrays for ARM
1.19 +//
1.20 +//
1.21 +
1.22 +#include <e32cia.h>
1.23 +#include "../common.h"
1.24 +
1.25 +#ifdef __ARRAY_MACHINE_CODED__
1.26 +extern "C" void PanicBadArrayFindMode();
1.27 +
1.28 +EXPORT_C __NAKED__ TAny*& RPointerArrayBase::At(TInt /*anIndex*/) const
1.29 + {
1.30 + asm("ldmia r0, {r2,r3} "); // r2=iCount, r3=iEntries
1.31 + asm("cmp r1, #0 "); // check anIndex>=0
1.32 + asm("cmpge r2, r1 "); // if so, check iCount>anIndex
1.33 + asm("addgt r0, r3, r1, lsl #2 "); // address of entry = iEntries+4*anIndex
1.34 +#ifdef __CPU_ARMV6
1.35 + asm("ble 1f "); // avoid conditional return on ARMv6
1.36 + __JUMP(,lr);
1.37 +#else
1.38 + __JUMP(gt,lr);
1.39 +#endif
1.40 + asm("1: ");
1.41 + asm("b " CSM_Z18PanicBadArrayIndexv);
1.42 + }
1.43 +
1.44 +EXPORT_C __NAKED__ TInt RPointerArrayBase::Append(const TAny* /*anEntry*/)
1.45 + {
1.46 + asm("ldmia r0, {r2,r3,r12} "); // r2=iCount, r3=iEntries, r12=iAllocated
1.47 + asm("cmp r2, r12 ");
1.48 + asm("beq ptr_append_1 ");
1.49 + asm("ptr_append_0: ");
1.50 + asm("str r1, [r3, r2, lsl #2] ");
1.51 + asm("add r2, r2, #1 ");
1.52 + asm("str r2, [r0] ");
1.53 + asm("mov r0, #0 ");
1.54 + __JUMP(,lr);
1.55 + asm("ptr_append_1: ");
1.56 + asm("stmfd sp!, {r0,r1,r2,lr} ");
1.57 + asm("bl " CSM_ZN17RPointerArrayBase4GrowEv);
1.58 + asm("cmp r0, #0 ");
1.59 + asm("bne ptr_append_2 ");
1.60 + asm("ldmfd sp!, {r0,r1,r2,lr} ");
1.61 + asm("ldmia r0, {r2, r3} ");
1.62 + asm("b ptr_append_0 ");
1.63 + asm("ptr_append_2: "); // error enlarging array
1.64 + asm("add sp, sp, #12 ");
1.65 + __POPRET("");
1.66 + }
1.67 +
1.68 +EXPORT_C __NAKED__ TInt RPointerArrayBase::Find(const TAny* /*anEntry*/) const
1.69 + {
1.70 + asm("ldmia r0, {r2,r3} "); // r2=iCount, r3=iEntries
1.71 + asm("mov r0, #0 "); // r0=0 (will be index+1)
1.72 + asm("subs r2, r2, #1 "); // r2=iCount-1
1.73 + asm("blt 0f ");
1.74 + asm("1: ");
1.75 + asm("ldr r12, [r3], #4 "); // r12=iEntries[r0]
1.76 + asm("add r0, r0, #1 "); // r0 = index+1
1.77 + asm("cmp r2, r0 "); // C=1 iff iCount-1>=index+1 iff index<=iCount-2 iff this isn't last entry
1.78 + asm("teq r12, r1 "); // check for equality, doesn't affect C
1.79 + asm("bhi 1b "); // loop if C=1 & Z=0, i.e. if no match and this isn't last entry
1.80 + asm("0: ");
1.81 + asm("movne r0, #0 "); // if no match set r0=0
1.82 + asm("sub r0, r0, #1 "); // r0 was index+1, return index
1.83 + __JUMP(,lr);
1.84 + }
1.85 +
1.86 +EXPORT_C __NAKED__ TInt RPointerArrayBase::Find(const TAny* /*anEntry*/, TGeneralIdentityRelation /*anIdentity*/) const
1.87 + {
1.88 + asm("stmfd sp!, {r4-r8,lr} ");
1.89 + __EH_FRAME_PUSH2(r4-r8,lr)
1.90 + asm("ldmia r0, {r4,r5} "); // r4=iCount, r5=iEntries
1.91 + asm("mvn r6, #0 ");
1.92 + asm("mov r7, r1 ");
1.93 + asm("mov r8, r2 ");
1.94 + asm("subs r4, r4, #1 "); // r4=iCount-1
1.95 + asm("bmi ptr_find2_return "); // if count=0, return -1
1.96 + asm("ptr_find2_loop: ");
1.97 + asm("ldr r1, [r5], #4 "); // r1=pointer to entry r6
1.98 + asm("add r6, r6, #1 ");
1.99 + asm("mov r0, r7 "); // r0=anEntry
1.100 + __JUMPL(8);
1.101 + asm("cmp r0, #0 ");
1.102 + asm("bne ptr_find2_return "); // if equal, return r6
1.103 + asm("cmp r6, r4 ");
1.104 + asm("blt ptr_find2_loop ");
1.105 + asm("mvn r6, #0 ");
1.106 + asm("ptr_find2_return: "); // return r6
1.107 + asm("mov r0, r6 ");
1.108 + __POPRET("r4-r8,");
1.109 + }
1.110 +
1.111 +EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchSigned(TInt /*anEntry*/, TInt& /*anIndex*/) const
1.112 + {
1.113 + asm("mov r3, #0 ");
1.114 + // fall through
1.115 + }
1.116 +
1.117 +EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchSigned(TInt /*anEntry*/, TInt& /*anIndex*/, TInt /*aMode*/) const
1.118 + {
1.119 + asm("stmfd sp!, {r4-r6,lr} ");
1.120 + __EH_FRAME_PUSH2(r4-r6,lr)
1.121 + asm("mov r6, r2 "); // r6=&anIndex
1.122 + asm("ldmia r0, {r2,r4} "); // r2=count, r4=iEntries
1.123 + asm("bl BinarySearchSigned ");
1.124 + asm("str r2, [r6] "); // store index
1.125 + __POPRET("r4-r6,");
1.126 +
1.127 +// Binary search list of signed integers
1.128 +// Match value in r1
1.129 +// List address in r4
1.130 +// Count in r2
1.131 +// Match mode in r3
1.132 +// Return with: r0=0 if match found, r0=-1 otherwise
1.133 +// Z flag set if match found, clear if not
1.134 +// r2=index of match or next higher
1.135 +// r5 modified
1.136 + asm("BinarySearchSigned: ");
1.137 +#ifdef _DEBUG
1.138 + asm("cmp r3, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );
1.139 + asm("bhs PanicBadArrayFindMode ");
1.140 +#endif
1.141 + asm("mov r3, r3, lsl #30 "); // match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)
1.142 + asm("orr r3, r3, #1 "); // set NOT FOUND flag
1.143 + asm("cmp r2, #0 "); // r2 will be right index
1.144 + asm("beq 0f ");
1.145 + asm("mov r5, #0 "); // r5 = left index
1.146 + asm("1: ");
1.147 + asm("add r12, r2, r5 ");
1.148 + asm("mov r12, r12, lsr #1 "); // r12 = mid index
1.149 + asm("ldr r0, [r4, r12, lsl #2] "); // r0 = entry[mid]
1.150 + asm("subs r0, r0, r1 "); // r0 = entry[mid] - match
1.151 + asm("beq 2f "); // if match branch out
1.152 + asm("3: ");
1.153 + asm("addlt r5, r12, #1 "); // else if entry<match left=mid+1
1.154 + asm("movgt r2, r12 "); // else if entry>match right=mid
1.155 + asm("subs r0, r2, r5 "); // right > left ?
1.156 + asm("bgt 1b "); // r0 = 0 when loop terminates
1.157 + asm("0: ");
1.158 + asm("tst r3, #1 "); // test not found flag
1.159 + asm("mvnnes r0, #0 "); // if set r0=-1 = KErrNotFound
1.160 + __JUMP(,lr);
1.161 + asm("2: ");
1.162 + asm("bics r3, r3, #1 "); // clear NOT FOUND flag, test for find mode ANY (Z set if so)
1.163 + asm("bne 3b "); // if not, V=0 (left from subs), N=1 for last, 0 for first, Z=0 => LAST->LT FIRST->GT
1.164 + asm("mov r2, r12 "); // if so, r2 = mid
1.165 + __JUMP(,lr); // and return with r0 = 0
1.166 + }
1.167 +
1.168 +EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchUnsigned(TUint /*anEntry*/, TInt& /*anIndex*/) const
1.169 + {
1.170 + asm("mov r3, #0 ");
1.171 + // fall through
1.172 + }
1.173 +
1.174 +EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearchUnsigned(TUint /*anEntry*/, TInt& /*anIndex*/, TInt /*aMode*/) const
1.175 + {
1.176 + asm("stmfd sp!, {r4-r6,lr} ");
1.177 + __EH_FRAME_PUSH2(r4-r6,lr)
1.178 + asm("mov r6, r2 "); // r6=&anIndex
1.179 + asm("ldmia r0, {r2,r4} "); // r2=count, r4=iEntries
1.180 + asm("bl BinarySearchUnsigned ");
1.181 + asm("str r2, [r6] "); // store index
1.182 + __POPRET("r4-r6,");
1.183 +
1.184 +// Binary search list of unsigned integers
1.185 +// Match value in r1
1.186 +// List address in r4
1.187 +// Count in r2
1.188 +// Match mode in r3
1.189 +// Return with: r0=0 if match found, r0=-1 otherwise
1.190 +// Z flag set if match found, clear if not
1.191 +// r2=index of match or next higher
1.192 +// r5 modified
1.193 + asm("BinarySearchUnsigned: ");
1.194 +#ifdef _DEBUG
1.195 + asm("cmp r3, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );
1.196 + asm("bhs PanicBadArrayFindMode ");
1.197 +#endif
1.198 + asm("mov r3, r3, lsl #30 "); // match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)
1.199 + asm("orr r3, r3, #1 "); // set NOT FOUND flag
1.200 + asm("cmp r2, #0 "); // r2 will be right index
1.201 + asm("beq 0f ");
1.202 + asm("mov r5, #0 "); // r5 = left index
1.203 + asm("1: ");
1.204 + asm("add r12, r2, r5 ");
1.205 + asm("mov r12, r12, lsr #1 "); // r12 = mid index
1.206 + asm("ldr r0, [r4, r12, lsl #2] "); // r0 = entry[mid]
1.207 + asm("subs r0, r1, r0 "); // r0 = match - entry[mid]
1.208 + asm("beq 2f "); // if match branch out
1.209 + asm("3: ");
1.210 + asm("addhi r5, r12, #1 "); // else if entry<match left=mid+1 HI = C &~ Z
1.211 + asm("movlo r2, r12 "); // else if entry>match right=mid LO = ~C
1.212 + asm("subs r0, r2, r5 "); // right > left ?
1.213 + asm("bgt 1b "); // r0 = 0 when loop terminates
1.214 + asm("0: ");
1.215 + asm("tst r3, #1 "); // test not found flag
1.216 + asm("mvnnes r0, #0 "); // if set r0=-1 = KErrNotFound
1.217 + __JUMP(,lr);
1.218 + asm("2: "); // N=0 Z=1 C=1 V=0 r0=0 here
1.219 + asm("bics r3, r3, #1 "); // clear NOT FOUND flag, test for find mode ANY (Z set if so)
1.220 + asm("cmpne r3, #0x60000000 "); // HI if LAST, LO if FIRST
1.221 + asm("bne 3b "); // if not ANY, branch back
1.222 + asm("mov r2, r12 "); // if ANY, r2 = mid
1.223 + __JUMP(,lr); // and return with r0 = 0
1.224 + }
1.225 +
1.226 +EXPORT_C __NAKED__ TInt RPointerArrayBase::BinarySearch(const TAny* /*anEntry*/, TInt& /*anIndex*/, TGeneralLinearOrder /*anOrder*/, TInt /*aMode*/) const
1.227 + {
1.228 + asm("stmfd sp!, {r2,r4-r11,lr} "); // store &anIndex, r4-r11, lr
1.229 + __EH_FRAME_ADDRESS(sp,4)
1.230 + __EH_FRAME_PUSH2(r4-r11,lr)
1.231 + asm("ldmia r0, {r5,r6} "); // r5=count, r6=iEntries
1.232 + asm("ldr r11, [sp, #40] "); // r11 = aMode
1.233 + asm("mov r7, r3 "); // r7=anOrder
1.234 + asm("mov r4, r1 "); // r1=anEntry
1.235 + asm("bl BinarySearchPointers "); // r0=KErrNone if match, KErrNotFound if not
1.236 + asm("ldmfd sp!, {r2,r4} "); // r2=&anIndex, restore r4
1.237 + // Dont need to FRAME RESTORE here since there's no barrier here
1.238 + asm("str r5, [r2] "); // store index
1.239 + __POPRET("r5-r11,"); // restore r5-r11 and return
1.240 +
1.241 +// Binary search list of pointers
1.242 +// Pointer to match value in r4
1.243 +// List address in r6
1.244 +// Count in r5
1.245 +// Pointer to ordering function in r7
1.246 +// r11 = find mode
1.247 +// Return with: r0=0 if match found, r0=-1 otherwise
1.248 +// Z flag set if match found, clear otherwise
1.249 +// r5=index of match or next higher
1.250 +// r9,r10,r11 modified
1.251 + asm("BinarySearchPointers: ");
1.252 +#ifdef _DEBUG
1.253 + asm("cmp r11, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );
1.254 + asm("bhs PanicBadArrayFindMode ");
1.255 +#endif
1.256 + asm("movs r11, r11, lsl #30 "); // match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)
1.257 + asm("eorne r11, r11, #0xC0000000 "); // match mode -> bits 30,31 (00000000=any, 80000000=first, 40000000=last)
1.258 + asm("orr r11, r11, #1 "); // set NOT FOUND flag
1.259 + asm("mov r9, lr ");
1.260 + asm("cmp r5, #0 "); // r5 will be right index
1.261 + asm("beq 0f ");
1.262 + asm("mov r10, #0 "); // r10 = left index
1.263 + asm("1: ");
1.264 + asm("add r8, r5, r10 ");
1.265 + asm("mov r8, r8, lsr #1 "); // r8 = mid index
1.266 +
1.267 +/** the latency of the indirect call should mask the latency of the ldr
1.268 + arm1136 requires base register to be valid one cycle early
1.269 +*/
1.270 + asm("mov r0, r4 "); // r0 points to match value
1.271 + asm("ldr r1, [r6, r8, lsl #2] "); // r1 points to entry[mid]
1.272 + __JUMPL(7); // call ordering function (match, entry)
1.273 + asm("cmp r0, #0 ");
1.274 + asm("biceq r11, r11, #1 "); // if match clear NOT FOUND flag
1.275 + asm("addeqs r0, r0, r11 "); // and add match mode to r0 (>0 if LAST, <0 if FIRST, 0 if ANY)
1.276 + asm("beq 2f "); // branch out if match and ANY
1.277 + asm("addgt r10, r8, #1 "); // else if match > entry, left = mid + 1
1.278 + asm("movlt r5, r8 "); // else if match < entry, right = mid
1.279 + asm("subs r0, r5, r10 "); // loop if right > left
1.280 + asm("bgt 1b "); // finish loop with r0 = 0
1.281 + asm("0: ");
1.282 + asm("tst r11, #1 "); // test not found flag
1.283 + asm("mvnnes r0, #0 "); // if set r0=-1 = KErrNotFound
1.284 + __JUMP(,r9);
1.285 + asm("2: ");
1.286 + asm("mov r5, r8 "); // if ANY, r8 = mid
1.287 + __JUMP(,r9); // and return with r0 = 0, Z=1
1.288 + }
1.289 +
1.290 +EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqSigned(TInt /*anEntry*/) const
1.291 + {
1.292 + asm("mov r2, #0 ");
1.293 + // fall through
1.294 + }
1.295 +
1.296 +EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqSigned(TInt /*anEntry*/, TInt /*aMode*/) const
1.297 + {
1.298 +#ifdef __EABI__
1.299 + // sp needs correct alignment
1.300 + asm("stmfd sp!, {r4-r6,lr} ");
1.301 + __EH_FRAME_PUSH2(r4-r6,lr)
1.302 +#else
1.303 + asm("stmfd sp!, {r4,r5,lr} ");
1.304 +#endif
1.305 + asm("mov r3, r2 "); // r3 = match mode
1.306 + asm("ldmia r0, {r2,r4} "); // r2=count, r4=iEntries
1.307 + asm("bl BinarySearchSigned ");
1.308 + asm("moveq r0, r2 "); // if match r0=match index; if no match, r0=KErrNotFound
1.309 +#ifdef __EABI__
1.310 + __POPRET("r4-r6,");
1.311 +#else
1.312 + __POPRET("r4,r5,");
1.313 +#endif
1.314 + }
1.315 +
1.316 +EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqUnsigned(TUint /*anEntry*/) const
1.317 + {
1.318 + asm("mov r2, #0 ");
1.319 + // fall through
1.320 + }
1.321 +
1.322 +EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsqUnsigned(TUint /*anEntry*/, TInt /*aMode*/) const
1.323 + {
1.324 +#ifdef __EABI__
1.325 + // sp needs correct alignment
1.326 + asm("stmfd sp!, {r4-r6,lr} ");
1.327 + __EH_FRAME_PUSH2(r4-r6,lr)
1.328 +#else
1.329 + asm("stmfd sp!, {r4,r5,lr} ");
1.330 +#endif
1.331 + asm("mov r3, r2 "); // r3 = match mode
1.332 + asm("ldmia r0, {r2,r4} "); // r2=count, r4=iEntries
1.333 + asm("bl BinarySearchUnsigned ");
1.334 + asm("moveq r0, r2 "); // if match r0=match index; if no match, r0=KErrNotFound
1.335 +#ifdef __EABI__
1.336 + __POPRET("r4-r6,");
1.337 +#else
1.338 + __POPRET("r4,r5,");
1.339 +#endif
1.340 + }
1.341 +
1.342 +EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsq(const TAny* /*anEntry*/, TGeneralLinearOrder /*anOrder*/) const
1.343 + {
1.344 + asm("mov r3, #0 ");
1.345 + // fall through
1.346 + }
1.347 +
1.348 +EXPORT_C __NAKED__ TInt RPointerArrayBase::FindIsq(const TAny* /*anEntry*/, TGeneralLinearOrder /*anOrder*/, TInt /*aMode*/) const
1.349 + {
1.350 +
1.351 + asm("stmfd sp!, {r3-r11,lr} ");
1.352 + __EH_FRAME_PUSH2(r4-r6,lr)
1.353 + asm("ldmia r0, {r5,r6} "); // r5=count, r6=iEntries
1.354 + asm("mov r11, r3 "); // r11 = aMode
1.355 + asm("mov r7, r2 "); // r7=anOrder
1.356 + asm("mov r4, r1 "); // r1=anEntry
1.357 + asm("bl BinarySearchPointers ");
1.358 + asm("moveq r0, r5 "); // if match, r0=match index
1.359 + __POPRET("r3-r11,");
1.360 + }
1.361 +
1.362 +#ifndef __KERNEL_MODE__
1.363 +EXPORT_C __NAKED__ void RPointerArrayBase::HeapSortSigned()
1.364 + {
1.365 +#ifdef __EABI__
1.366 + asm("stmfd sp!, {r4-r10,lr} ");
1.367 + __EH_FRAME_PUSH2(r4-r10,lr)
1.368 +#else
1.369 + asm("stmfd sp!, {r4-r9,lr} ");
1.370 +#endif
1.371 + asm("ldmia r0, {r4,r5} "); // r4=iCount, r5=iEntries
1.372 + asm("bl HeapSortSigned ");
1.373 +#ifdef __EABI__
1.374 + __POPRET("r4-r10,");
1.375 +#else
1.376 + __POPRET("r4-r9,");
1.377 +#endif
1.378 + // Heap sort list of signed integers
1.379 + // List address in r5, count in r4
1.380 + // r4=ss, r6=sh, r7=si
1.381 + // r8,r9 modified
1.382 + asm("HeapSortSigned: ");
1.383 + asm("cmp r4, #1 ");
1.384 + __JUMP(le,lr);
1.385 + asm("mov r6, r4, lsr #1 ");
1.386 + asm("hss_loop_start1: ");
1.387 + asm("sub r6, r6, #1 ");
1.388 + asm("ldr r7, [r5, r6, lsl #2] ");
1.389 + asm("mov r8, r6 ");
1.390 + asm("mov r9, r6 ");
1.391 + asm("b hss_loop_start2 ");
1.392 + asm("hss_loop_inner: ");
1.393 + asm("ldr r0, [r5, r8, lsl #2] ");
1.394 + asm("str r0, [r5, r9, lsl #2] ");
1.395 + asm("mov r9, r8 ");
1.396 + asm("hss_loop_start2: ");
1.397 + asm("add r8, r8, #1 ");
1.398 + asm("add r8, r8, r8 ");
1.399 + asm("cmp r8, r4 ");
1.400 + asm("bgt hss_loop_inner_end ");
1.401 + asm("add r0, r5, r8, lsl #2 ");
1.402 + asm("ldmneda r0, {r1,r2} ");
1.403 + asm("ldreq r1, [r0, #-4] ");
1.404 + asm("subeq r8, r8, #1 ");
1.405 + asm("beq hss_loop_inner2 ");
1.406 + asm("cmp r1, r2 ");
1.407 + asm("subgt r8, r8, #1 ");
1.408 + asm("movle r1, r2 ");
1.409 + asm("hss_loop_inner2: ");
1.410 + asm("cmp r1, r7 ");
1.411 + asm("bgt hss_loop_inner ");
1.412 + asm("hss_loop_inner_end: ");
1.413 + asm("str r7, [r5, r9, lsl #2] ");
1.414 + asm("cmp r6, #0 ");
1.415 + asm("bne hss_loop_start1 ");
1.416 + asm("sub r4, r4, #1 ");
1.417 + asm("ldr r7, [r5, r4, lsl #2] ");
1.418 + asm("ldr r0, [r5, #0] ");
1.419 + asm("str r0, [r5, r4, lsl #2] ");
1.420 + asm("cmp r4, #1 ");
1.421 + asm("mov r8, r6 ");
1.422 + asm("mov r9, r6 ");
1.423 + asm("bgt hss_loop_start2 ");
1.424 + asm("str r7, [r5, #0] ");
1.425 + __JUMP(,lr);
1.426 + }
1.427 +
1.428 +EXPORT_C __NAKED__ void RPointerArrayBase::HeapSortUnsigned()
1.429 + {
1.430 + asm("stmfd sp!, {r4-r9,lr} ");
1.431 + asm("ldmia r0, {r4,r5} "); // r4=iCount, r5=iEntries
1.432 + asm("bl HeapSortUnsigned ");
1.433 + __POPRET("r4-r9,");
1.434 + }
1.435 +#endif // !__KERNEL_MODE__
1.436 +
1.437 +__NAKED__ void HeapSortUnsigned(TUint* aEntries,TInt aCount)
1.438 + {
1.439 + asm("stmfd sp!, {r4-r9,lr} ");
1.440 + asm("mov r4,r1"); // r4=iCount
1.441 + asm("mov r5,r0"); // r5=iEntries
1.442 + asm("bl HeapSortUnsigned ");
1.443 + __POPRET("r4-r9,");
1.444 +
1.445 + // Heap sort list of unsigned integers
1.446 + // List address in r5, count in r4
1.447 + // r4=ss, r6=sh, r7=si
1.448 + // r8,r9 modified
1.449 + asm("HeapSortUnsigned: ");
1.450 + asm("cmp r4, #1 ");
1.451 + __JUMP(le,lr);
1.452 + asm("mov r6, r4, lsr #1 ");
1.453 + asm("hsu_loop_start1: ");
1.454 + asm("sub r6, r6, #1 ");
1.455 + asm("ldr r7, [r5, r6, lsl #2] ");
1.456 + asm("mov r8, r6 ");
1.457 + asm("mov r9, r6 ");
1.458 + asm("b hsu_loop_start2 ");
1.459 + asm("hsu_loop_inner: ");
1.460 + asm("ldr r0, [r5, r8, lsl #2] ");
1.461 + asm("str r0, [r5, r9, lsl #2] ");
1.462 + asm("mov r9, r8 ");
1.463 + asm("hsu_loop_start2: ");
1.464 + asm("add r8, r8, #1 ");
1.465 + asm("add r8, r8, r8 ");
1.466 + asm("cmp r8, r4 ");
1.467 + asm("bgt hsu_loop_inner_end ");
1.468 + asm("add r0, r5, r8, lsl #2 ");
1.469 + asm("ldmneda r0, {r1,r2} ");
1.470 + asm("ldreq r1, [r0, #-4] ");
1.471 + asm("subeq r8, r8, #1 ");
1.472 + asm("beq hsu_loop_inner2 ");
1.473 + asm("cmp r1, r2 ");
1.474 + asm("subhi r8, r8, #1 ");
1.475 + asm("movls r1, r2 ");
1.476 + asm("hsu_loop_inner2: ");
1.477 + asm("cmp r1, r7 ");
1.478 + asm("bhi hsu_loop_inner ");
1.479 + asm("hsu_loop_inner_end: ");
1.480 + asm("str r7, [r5, r9, lsl #2] ");
1.481 + asm("cmp r6, #0 ");
1.482 + asm("bne hsu_loop_start1 ");
1.483 + asm("sub r4, r4, #1 ");
1.484 + asm("ldr r7, [r5, r4, lsl #2] ");
1.485 + asm("ldr r0, [r5, #0] ");
1.486 + asm("str r0, [r5, r4, lsl #2] ");
1.487 + asm("cmp r4, #1 ");
1.488 + asm("mov r8, r6 ");
1.489 + asm("mov r9, r6 ");
1.490 + asm("bgt hsu_loop_start2 ");
1.491 + asm("str r7, [r5, #0] ");
1.492 + __JUMP(,lr);
1.493 + }
1.494 +
1.495 +#ifndef __KERNEL_MODE__
1.496 +EXPORT_C __NAKED__ void RPointerArrayBase::HeapSort(TGeneralLinearOrder /*anOrder*/)
1.497 + {
1.498 + asm("stmfd sp!, {r3-r11,lr} ");
1.499 + // r3 is caller save
1.500 + __EH_FRAME_ADDRESS(sp,4)
1.501 + // we can push the callee save regs
1.502 + __EH_FRAME_PUSH2(r4-r11,lr)
1.503 + asm("ldmia r0, {r4,r5} "); // r4=iCount, r5=iEntries
1.504 + asm("mov r10, r1 "); // r10=anOrder
1.505 + asm("bl HeapSortPointers ");
1.506 + __POPRET("r3-r11,");
1.507 +
1.508 + // Heap sort list of pointers
1.509 + // List address in r5, count in r4, r10 points to ordering function
1.510 + // r4=ss, r6=sh, r7=si
1.511 + // r8,r9,r11 modified
1.512 + asm("HeapSortPointers: ");
1.513 + asm("cmp r4, #1 ");
1.514 + __JUMP(le,lr);
1.515 + asm("mov r11, lr ");
1.516 + asm("mov r6, r4, lsr #1 ");
1.517 + asm("hsp_loop_start1: ");
1.518 + asm("sub r6, r6, #1 ");
1.519 + asm("ldr r7, [r5, r6, lsl #2] ");
1.520 + asm("mov r8, r6 ");
1.521 + asm("mov r9, r6 ");
1.522 + asm("b hsp_loop_start2 ");
1.523 + asm("hsp_loop_inner: ");
1.524 + asm("ldr r0, [r5, r8, lsl #2] ");
1.525 + asm("str r0, [r5, r9, lsl #2] ");
1.526 + asm("mov r9, r8 ");
1.527 + asm("hsp_loop_start2: ");
1.528 + asm("add r8, r8, #1 ");
1.529 + asm("add r8, r8, r8 ");
1.530 + asm("cmp r8, r4 ");
1.531 + asm("bgt hsp_loop_inner_end ");
1.532 + asm("subeq r8, r8, #1 ");
1.533 + asm("beq hsp_loop_inner2 ");
1.534 + asm("add r0, r5, r8, lsl #2 ");
1.535 + asm("ldmda r0, {r0,r1} ");
1.536 + __JUMPL(10);
1.537 + asm("cmp r0, #0 ");
1.538 + asm("subgt r8, r8, #1 ");
1.539 + asm("hsp_loop_inner2: ");
1.540 + asm("ldr r0, [r5, r8, lsl #2] ");
1.541 + asm("mov r1, r7 ");
1.542 + __JUMPL(10);
1.543 + asm("cmp r0, #0 ");
1.544 + asm("bgt hsp_loop_inner ");
1.545 + asm("hsp_loop_inner_end: ");
1.546 + asm("str r7, [r5, r9, lsl #2] ");
1.547 + asm("cmp r6, #0 ");
1.548 + asm("bne hsp_loop_start1 ");
1.549 + asm("sub r4, r4, #1 ");
1.550 + asm("ldr r7, [r5, r4, lsl #2] ");
1.551 + asm("ldr r0, [r5, #0] ");
1.552 + asm("str r0, [r5, r4, lsl #2] ");
1.553 + asm("cmp r4, #1 ");
1.554 + asm("mov r8, r6 ");
1.555 + asm("mov r9, r6 ");
1.556 + asm("bgt hsp_loop_start2 ");
1.557 + asm("str r7, [r5, #0] ");
1.558 + __JUMP(,r11);
1.559 + }
1.560 +#endif // __KERNEL_MODE__
1.561 +
1.562 +EXPORT_C __NAKED__ TAny* RArrayBase::At(TInt /*anIndex*/) const
1.563 + {
1.564 + asm("ldmia r0, {r2,r3,r12} "); // r2=iCount, r3=iEntries, r12=iEntrySize
1.565 + asm("cmp r1, #0 "); // check anIndex>=0
1.566 + asm("cmpge r2, r1 "); // if so, check iCount>anIndex
1.567 + asm("mlagt r0, r1, r12, r3 "); // if ok, r0=anIndex*iEntrySize+iEntries
1.568 +#ifdef __CPU_ARMV6
1.569 + asm("ble 1f ");
1.570 + __JUMP(,lr);
1.571 +#else
1.572 + __JUMP(gt,lr);
1.573 +#endif
1.574 + asm("1: ");
1.575 + asm("b " CSM_Z18PanicBadArrayIndexv);
1.576 + }
1.577 +
1.578 +EXPORT_C __NAKED__ TInt RArrayBase::Append(const TAny* /*anEntry*/)
1.579 + {
1.580 + asm("stmfd sp!, {lr} ");
1.581 + asm("ldmia r0, {r3,r12} "); // r3=iCount, r12=iEntries
1.582 + asm("ldr r2, [r0, #%a0]" : : "i" _FOFF(RArrayBase,iAllocated));
1.583 + asm("cmp r3, r2 ");
1.584 + asm("beq simple_append_1 ");
1.585 + asm("simple_append_0: ");
1.586 + asm("add r2, r3, #1 ");
1.587 + asm("str r2, [r0] "); // iCount++
1.588 + asm("ldr r2, [r0, #%a0]" : : "i" _FOFF(RArrayBase,iEntrySize));
1.589 + asm("mla r0, r2, r3, r12 "); // r0=iEntries+iEntrySize*iCount
1.590 + asm("bl wordmove "); // r1=anEntry, r2=iEntrySize, do copy
1.591 + asm("mov r0, #0 "); // return KErrNone;
1.592 + __POPRET("");
1.593 +
1.594 + asm("simple_append_1: ");
1.595 + asm("stmfd sp!, {r0,r1,r2} ");
1.596 + asm("bl " CSM_ZN10RArrayBase4GrowEv);
1.597 + asm("cmp r0, #0 ");
1.598 + asm("bne simple_append_2 ");
1.599 + asm("ldmfd sp!, {r0,r1,r2} ");
1.600 + asm("ldmia r0, {r3, r12} ");
1.601 + asm("b simple_append_0 ");
1.602 + asm("simple_append_2: "); // error enlarging array
1.603 + asm("add sp, sp, #12 ");
1.604 + __POPRET("");
1.605 + }
1.606 +
1.607 +EXPORT_C __NAKED__ TInt RArrayBase::Find(const TAny* /*anEntry*/) const
1.608 + {
1.609 + asm("ldmia r0, {r0,r2,r3,r12} "); // r0=count, r2=iEntries, r3=iEntrySize, r12=iKeyOffset
1.610 + asm("stmfd sp!, {r4,lr} "); // save r4,lr
1.611 + asm("subs r0, r0, #1 "); // r0 = count-1
1.612 + asm("blt 0f "); // skip if count was zero
1.613 + asm("ldr r1, [r1, r12] "); // r1=key of match entry
1.614 + asm("sub r4, r0, #1 "); // r4 = iCount-2
1.615 + asm("1: ");
1.616 + asm("ldr lr, [r2, r12] "); // lr=key of current entry
1.617 + asm("add r2, r2, r3 "); // step r2 to next entry
1.618 + asm("subs r0, r0, #1 "); // C=1 iff this isn't last entry
1.619 + asm("teq lr, r1 "); // check for match - C unaffected
1.620 + asm("bhi 1b "); // loop if C=1 & Z=0, i.e. if no match and this isn't last entry
1.621 + asm("0: ");
1.622 + asm("mvnne r0, #0 "); // if no match, return -1
1.623 + asm("subeq r0, r4, r0 "); // if match, index = (iCount-2)-r0
1.624 + __POPRET("r4,");
1.625 + }
1.626 +
1.627 +EXPORT_C __NAKED__ TInt RArrayBase::Find(const TAny* /*anEntry*/, TGeneralIdentityRelation /*anIdentity*/) const
1.628 + {
1.629 + asm("stmfd sp!, {r4-r10,lr} "); // save r4-r10,lr
1.630 + __EH_FRAME_PUSH2(r4-r10,lr)
1.631 + asm("ldmia r0, {r4,r5,r6} "); // r4=count, r5=iEntries, r6=iEntrySize
1.632 + asm("mov r8, r1 "); // r8=anEntry
1.633 + asm("mov r9, r2 "); // r9=anIdentity
1.634 + asm("sub r7, r4, #1 "); // r7=iCount-1
1.635 + asm("b simple_find2_start ");
1.636 + asm("simple_find2_loop: ");
1.637 + asm("mov r1, r5 "); // r1->current entry
1.638 + asm("mov r0, r8 "); // r0=anEntry
1.639 + __JUMPL(9);
1.640 + asm("cmp r0, #0 ");
1.641 + asm("bne simple_find2_return ");
1.642 + asm("add r5, r5, r6 "); // else step to next entry
1.643 + asm("simple_find2_start: ");
1.644 + asm("subs r4, r4, #1 ");
1.645 + asm("bpl simple_find2_loop ");
1.646 + asm("add r4, r7, #1 "); // no match, arrange to return -1
1.647 + asm("simple_find2_return: ");
1.648 + asm("sub r0, r7, r4 "); // index=count-r4
1.649 + __POPRET("r4-r10,");
1.650 + }
1.651 +
1.652 +EXPORT_C __NAKED__ TInt RArrayBase::BinarySearchSigned(const TAny* /*anEntry*/, TInt& /*anIndex*/) const
1.653 + {
1.654 + asm("mov r3, #0 ");
1.655 + // fall through
1.656 + }
1.657 +
1.658 +EXPORT_C __NAKED__ TInt RArrayBase::BinarySearchSigned(const TAny* /*anEntry*/, TInt& /*anIndex*/, TInt /*aMode*/) const
1.659 + {
1.660 + asm("stmfd sp!, {r4-r8,lr} ");
1.661 + __EH_FRAME_PUSH2(r4-r8,lr)
1.662 + asm("mov r8, r2 "); // r8=&anIndex
1.663 + asm("ldmia r0, {r2,r4,r5,r6} "); // r2=count, r3=iEntries, r5=entry size, r6=key offset
1.664 + asm("cmp r5, #4 "); // check for 4 byte entries
1.665 + asm("ldr r1, [r1, r6] "); // r1=match key
1.666 + asm("beq 1f "); // if 4 byte entries, call simpler routine
1.667 + asm("bl BinarySearchSignedKey "); // if not, call general routine
1.668 + asm("b 2f ");
1.669 + asm("1: ");
1.670 + asm("bl BinarySearchSigned "); // use simpler routine for 4 byte entries
1.671 + asm("2: ");
1.672 + asm("str r2, [r8] ");
1.673 + __POPRET("r4-r8,");
1.674 +
1.675 +// Binary search list of signed integers
1.676 +// Match key in r1
1.677 +// List address in r4
1.678 +// Count in r2
1.679 +// Match mode in r3
1.680 +// EntrySize in r5, KeyOffset in r6
1.681 +// Return with: r0=0 if match found, r0 nonzero otherwise
1.682 +// r2=index of match or next higher
1.683 +// r7 modified
1.684 + asm("BinarySearchSignedKey: ");
1.685 +#ifdef _DEBUG
1.686 + asm("cmp r3, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );
1.687 + asm("bhs PanicBadArrayFindMode ");
1.688 +#endif
1.689 + asm("mov r3, r3, lsl #30 "); // match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)
1.690 + asm("orr r3, r3, #1 "); // set NOT FOUND flag
1.691 + asm("cmp r2, #0 "); // r2 will be right index
1.692 + asm("beq 0f ");
1.693 + asm("mov r7, #0 "); // r7 will be left index
1.694 + asm("1: ");
1.695 + asm("add r12, r2, r7 ");
1.696 + asm("mov r12, r12, lsr #1 "); // r12 = mid index
1.697 + asm("mla r0, r12, r5, r6 "); // r0 = key offset + entry size * mid index
1.698 + asm("ldr r0, [r4, r0] "); // r0 = key[mid]
1.699 + asm("subs r0, r0, r1 "); // r0 = entry[mid] - match
1.700 + asm("beq 2f "); // if match branch out
1.701 + asm("3: ");
1.702 + asm("addlt r7, r12, #1 "); // else if entry<match left=mid+1
1.703 + asm("movgt r2, r12 "); // else if entry>match right=mid
1.704 + asm("subs r0, r2, r7 "); // right > left ?
1.705 + asm("bgt 1b "); // r0 = 0 when loop terminates
1.706 + asm("0: ");
1.707 + asm("tst r3, #1 "); // test not found flag
1.708 + asm("mvnnes r0, #0 "); // if set r0=-1 = KErrNotFound
1.709 + __JUMP(,lr);
1.710 + asm("2: ");
1.711 + asm("bics r3, r3, #1 "); // clear NOT FOUND flag, test for find mode ANY (Z set if so)
1.712 + asm("bne 3b "); // if not, V=0 (left from subs), N=1 for last, 0 for first, Z=0 => LAST->LT FIRST->GT
1.713 + asm("mov r2, r12 "); // if so, r2 = mid
1.714 + __JUMP(,lr); // and return with r0 = 0
1.715 + }
1.716 +
1.717 +EXPORT_C __NAKED__ TInt RArrayBase::BinarySearchUnsigned(const TAny* /*anEntry*/, TInt& /*anIndex*/) const
1.718 + {
1.719 + asm("mov r3, #0 ");
1.720 + // fall through
1.721 + }
1.722 +
1.723 +EXPORT_C __NAKED__ TInt RArrayBase::BinarySearchUnsigned(const TAny* /*anEntry*/, TInt& /*anIndex*/, TInt /*aMode*/) const
1.724 + {
1.725 + asm("stmfd sp!, {r4-r8,lr} ");
1.726 + __EH_FRAME_PUSH2(r4-r8,lr)
1.727 + asm("mov r8, r2 "); // r8=&anIndex
1.728 + asm("ldmia r0, {r2,r4,r5,r6} "); // r2=count, r4=iEntries, r5=entry size, r6=key offset
1.729 + asm("cmp r5, #4 "); // check for 4 byte entries
1.730 + asm("ldr r1, [r1, r6] "); // r1=match key
1.731 + asm("beq 1f "); // if 4 byte entries, call simpler routine
1.732 + asm("bl BinarySearchUnsignedKey "); // if not, call general routine
1.733 + asm("b 2f ");
1.734 + asm("1: ");
1.735 + asm("bl BinarySearchUnsigned "); // use simpler routine for 4 byte entries
1.736 + asm("2: ");
1.737 + asm("str r2, [r8] ");
1.738 + __POPRET("r4-r8,");
1.739 +
1.740 +// Binary search list of unsigned integers
1.741 +// Match key in r1
1.742 +// List address in r4
1.743 +// Count in r2
1.744 +// Match mode in r3
1.745 +// EntrySize in r5, KeyOffset in r6
1.746 +// Return with: r0=0 if match found, r0 nonzero otherwise
1.747 +// r2=index of match or next higher
1.748 +// r7 modified
1.749 + asm("BinarySearchUnsignedKey: ");
1.750 +#ifdef _DEBUG
1.751 + asm("cmp r3, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );
1.752 + asm("bhs PanicBadArrayFindMode ");
1.753 +#endif
1.754 + asm("mov r3, r3, lsl #30 "); // match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)
1.755 + asm("orr r3, r3, #1 "); // set NOT FOUND flag
1.756 + asm("cmp r2, #0 "); // r2 will be right index
1.757 + asm("beq 0f ");
1.758 + asm("mov r7, #0 "); // r7 will be left index
1.759 + asm("1: ");
1.760 + asm("add r12, r2, r7 ");
1.761 + asm("mov r12, r12, lsr #1 "); // r12 = mid index
1.762 + asm("mla r0, r12, r5, r6 "); // r0 = key offset + entry size * mid index
1.763 + asm("ldr r0, [r4, r0] "); // r0 = key[mid]
1.764 + asm("subs r0, r1, r0 "); // r0 = match - entry[mid]
1.765 + asm("beq 2f "); // if match branch out
1.766 + asm("3: ");
1.767 + asm("addhi r7, r12, #1 "); // else if entry<match left=mid+1 HI = C &~ Z
1.768 + asm("movlo r2, r12 "); // else if entry>match right=mid LO = ~C
1.769 + asm("subs r0, r2, r7 "); // right > left ?
1.770 + asm("bgt 1b "); // r0 = 0 when loop terminates
1.771 + asm("0: ");
1.772 + asm("tst r3, #1 "); // test not found flag
1.773 + asm("mvnnes r0, #0 "); // if set r0=-1 = KErrNotFound
1.774 + __JUMP(,lr);
1.775 + asm("2: "); // N=0 Z=1 C=1 V=0 r0=0 here
1.776 + asm("bics r3, r3, #1 "); // clear NOT FOUND flag, test for find mode ANY (Z set if so)
1.777 + asm("cmpne r3, #0x60000000 "); // HI if LAST, LO if FIRST
1.778 + asm("bne 3b "); // if not ANY, branch back
1.779 + asm("mov r2, r12 "); // if ANY, r2 = mid
1.780 + __JUMP(,lr); // and return with r0 = 0
1.781 + }
1.782 +
1.783 +EXPORT_C __NAKED__ TInt RArrayBase::BinarySearch(const TAny* /*anEntry*/, TInt& /*anIndex*/, TGeneralLinearOrder /*anOrder*/, TInt /*aMode*/) const
1.784 + {
1.785 + asm("stmfd sp!, {r3-r11,lr} ");
1.786 + // r3 is caller save
1.787 + __EH_FRAME_ADDRESS(sp,4)
1.788 + // we can push the callee save regs
1.789 + __EH_FRAME_PUSH2(r4-r11,lr)
1.790 + asm("ldmia r0, {r5,r6,r11} "); // r5=count, r6=iEntries, r11=entry size
1.791 + asm("ldr r9, [sp, #40] "); // r9 = aMode
1.792 + asm("mov r4, r1 "); // r4=anEntry
1.793 + asm("mov r7, r3 "); // r7=anOrder
1.794 + asm("bl BinarySearchEntries ");
1.795 + asm("str r5, [r2] "); // store index
1.796 + __POPRET("r3-r11,");
1.797 +
1.798 + // Binary search list of general entries
1.799 + // Pointer to match value in r4
1.800 + // List address in r6
1.801 + // Count in r5
1.802 + // Match mode in r9
1.803 + // Pointer to ordering function in r7
1.804 + // Entry size in r11
1.805 + // Return with: r0=0 if match found, r0 nonzero otherwise
1.806 + // r5=index of match or next higher
1.807 + // r9,r10 modified
1.808 + // r2 preserved
1.809 + asm("BinarySearchEntries: ");
1.810 +#ifdef _DEBUG
1.811 + asm("cmp r9, #%a0" : : "i" ((TInt)EArrayFindMode_Limit) );
1.812 + asm("bhs PanicBadArrayFindMode ");
1.813 +#endif
1.814 + asm("stmfd sp!, {r2,lr} ");
1.815 + asm("movs r9, r9, lsl #30 "); // match mode -> bits 30,31 (00000000=any, 40000000=first, 80000000=last)
1.816 + asm("eorne r9, r9, #0xC0000000 "); // match mode -> bits 30,31 (00000000=any, 80000000=first, 40000000=last)
1.817 + asm("orr r9, r9, #1 "); // set NOT FOUND flag
1.818 + asm("cmp r5, #0 "); // r5 will be right index
1.819 + asm("beq 0f ");
1.820 + asm("mov r10, #0 "); // r10 will be left index
1.821 + asm("1: ");
1.822 + asm("add r8, r5, r10 ");
1.823 + asm("mov r8, r8, lsr #1 "); // r8 = mid index
1.824 + asm("mla r1, r8, r11, r6 "); // r1 = r8*entry size + list address = &entry[mid]
1.825 + asm("mov r0, r4 "); // r0 points to match value
1.826 + __JUMPL(7); // call ordering function (match, entry)
1.827 + asm("cmp r0, #0 ");
1.828 + asm("biceq r9, r9, #1 "); // if match clear NOT FOUND flag
1.829 + asm("addeqs r0, r0, r9 "); // and add match mode to r0 (>0 if LAST, <0 if FIRST, 0 if ANY)
1.830 + asm("beq 2f "); // branch out if match and ANY
1.831 + asm("addgt r10, r8, #1 "); // else if match > entry, left = mid + 1
1.832 + asm("movlt r5, r8 "); // else if match < entry, right = mid
1.833 + asm("subs r0, r5, r10 "); // loop if right > left
1.834 + asm("bgt 1b "); // finish loop with r0 = 0
1.835 + asm("0: ");
1.836 + asm("tst r9, #1 "); // test not found flag
1.837 + asm("mvnnes r0, #0 "); // if set r0=-1 = KErrNotFound
1.838 + __POPRET("r2,");
1.839 + asm("2: ");
1.840 + asm("mov r5, r8 "); // if ANY, r8 = mid
1.841 + __POPRET("r2,"); // and return with r0 = 0, Z=1
1.842 + }
1.843 +
1.844 +EXPORT_C __NAKED__ TInt RArrayBase::FindIsqSigned(const TAny* /*anEntry*/) const
1.845 + {
1.846 + asm("mov r2, #0 ");
1.847 + // fall through
1.848 + }
1.849 +
1.850 +EXPORT_C __NAKED__ TInt RArrayBase::FindIsqSigned(const TAny* /*anEntry*/, TInt /*aMode*/) const
1.851 + {
1.852 +#ifdef __EABI__
1.853 + // sp needs to be aligned correctly
1.854 + asm("stmfd sp!, {r4-r8,lr} ");
1.855 + __EH_FRAME_PUSH2(r4-r8,lr)
1.856 +#else
1.857 + asm("stmfd sp!, {r4-r7,lr} ");
1.858 +#endif
1.859 + asm("mov r3, r2 "); // r3 = match mode
1.860 + asm("ldmia r0, {r2,r4,r5,r6} "); // r2=count, r4=iEntries, r5=entry size, r6=key offset
1.861 + asm("cmp r5, #4 "); // check for 4 byte entries
1.862 + asm("ldr r1, [r1, r6] "); // r1=match key
1.863 + asm("beq 1f "); // use simpler routine for 4 byte entries
1.864 + asm("bl BinarySearchSignedKey "); // else call general routine
1.865 + asm("b 2f ");
1.866 + asm("1: ");
1.867 + asm("bl BinarySearchSigned ");
1.868 + asm("2: ");
1.869 + asm("moveq r0, r2 "); // if match r0=index else r0=KErrNotFound
1.870 +#ifdef __EABI__
1.871 + __POPRET("r4-r8,");
1.872 +#else
1.873 + __POPRET("r4-r7,");
1.874 +#endif
1.875 + }
1.876 +
1.877 +EXPORT_C __NAKED__ TInt RArrayBase::FindIsqUnsigned(const TAny* /*anEntry*/) const
1.878 + {
1.879 + asm("mov r2, #0 ");
1.880 + // fall through
1.881 + }
1.882 +
1.883 +EXPORT_C __NAKED__ TInt RArrayBase::FindIsqUnsigned(const TAny* /*anEntry*/, TInt /*aMode*/) const
1.884 + {
1.885 +#ifdef __EABI__
1.886 + // sp needs to be aligned correctly
1.887 + asm("stmfd sp!, {r4-r8,lr} ");
1.888 + __EH_FRAME_PUSH2(r4-r8,lr)
1.889 +#else
1.890 + asm("stmfd sp!, {r4-r7,lr} ");
1.891 +#endif
1.892 + asm("mov r3, r2 "); // r3 = match mode
1.893 + asm("ldmia r0, {r2,r4,r5,r6} "); // r2=count, r4=iEntries, r5=entry size, r6=key offset
1.894 + asm("cmp r5, #4 "); // check for 4 byte entries
1.895 + asm("ldr r1, [r1, r6] "); // r1=match key
1.896 + asm("beq 1f "); // use simpler routine for 4 byte entries
1.897 + asm("bl BinarySearchUnsignedKey "); // else call general routine
1.898 + asm("b 2f ");
1.899 + asm("1: ");
1.900 + asm("bl BinarySearchUnsigned ");
1.901 + asm("2: ");
1.902 + asm("moveq r0, r2 "); // if match r0=index else r0=KErrNotFound
1.903 +#ifdef __EABI__
1.904 + __POPRET("r4-r8,");
1.905 +#else
1.906 + __POPRET("r4-r7,");
1.907 +#endif
1.908 + }
1.909 +
1.910 +EXPORT_C __NAKED__ TInt RArrayBase::FindIsq(const TAny* /*anEntry*/, TGeneralLinearOrder /*anOrder*/) const
1.911 + {
1.912 + asm("mov r3, #0 ");
1.913 + // fall through
1.914 + }
1.915 +
1.916 +EXPORT_C __NAKED__ TInt RArrayBase::FindIsq(const TAny* /*anEntry*/, TGeneralLinearOrder /*anOrder*/, TInt /*aMode*/) const
1.917 + {
1.918 + asm("stmfd sp!, {r3-r11,lr} ");
1.919 + // r3 is caller save
1.920 + __EH_FRAME_ADDRESS(sp,4)
1.921 + // we can push the callee save regs
1.922 + __EH_FRAME_PUSH2(r4-r11,lr)
1.923 + asm("ldmia r0, {r5,r6,r11} "); // r5=count, r6=iEntries, r11=entry size
1.924 + asm("mov r4, r1 "); // r4=anEntry
1.925 + asm("mov r7, r2 "); // r7=anOrder
1.926 + asm("mov r9, r3 "); // r9 = aMode
1.927 + asm("bl BinarySearchEntries ");
1.928 + asm("moveq r0, r5 "); // if match r0=index
1.929 + __POPRET("r3-r11,");
1.930 + }
1.931 +
1.932 +#ifndef __KERNEL_MODE__
1.933 +EXPORT_C __NAKED__ void RArrayBase::HeapSortSigned()
1.934 + {
1.935 +#ifdef __EABI__
1.936 + // need sp aligned correctly
1.937 + asm("stmfd sp!, {r3-r11,lr} ");
1.938 + __EH_FRAME_ADDRESS(sp,4)
1.939 + __EH_FRAME_PUSH2(r4-r11,lr)
1.940 +#else
1.941 + asm("stmfd sp!, {r4-r11,lr} ");
1.942 +#endif
1.943 + asm("ldmia r0, {r4,r5,r10,r11} "); // r4=iCount, r5=iEntries, r10=entry size, r11=key offset
1.944 + asm("cmp r10, #4 ");
1.945 + asm("bleq HeapSortSigned ");
1.946 + asm("cmp r10, #4 ");
1.947 + asm("blne HeapSortSignedKey ");
1.948 +#ifdef __EABI__
1.949 + __POPRET("r3-r11,");
1.950 +#else
1.951 + __POPRET("r4-r11,");
1.952 +#endif
1.953 +
1.954 + // Heap sort list of entries by signed key
1.955 + // List address in r5, count in r4, entry size in r10, key offset in r11
1.956 + // r4=ss, r6=sh
1.957 + // r8,r9 modified
1.958 + asm("HeapSortSignedKey: ");
1.959 + asm("cmp r4, #1 ");
1.960 + __JUMP(le,lr);
1.961 + asm("mov r7, lr "); // save lr in r7
1.962 + asm("sub sp, sp, r10 "); // get some temporary space on the stack
1.963 + asm("mov r6, r4, lsr #1 ");
1.964 + asm("hssk_loop_start1: ");
1.965 + asm("sub r6, r6, #1 ");
1.966 + asm("mla r1, r6, r10, r5 "); // [sp]=entry[r6]
1.967 + asm("mov r0, sp ");
1.968 + asm("mov r2, r10 ");
1.969 + asm("bl wordmove ");
1.970 + asm("mov r8, r6 ");
1.971 + asm("mov r9, r6 ");
1.972 + asm("b hssk_loop_start2 ");
1.973 + asm("hssk_loop_inner: ");
1.974 + asm("mla r0, r9, r10, r5 "); // r0=&entry[r9]
1.975 + asm("mla r1, r8, r10, r5 "); // r1=&entry[r8]
1.976 + asm("mov r2, r10 ");
1.977 + asm("bl wordmove "); // entry[r9]=entry[r8]
1.978 + asm("mov r9, r8 ");
1.979 + asm("hssk_loop_start2: ");
1.980 + asm("add r8, r8, #1 ");
1.981 + asm("add r8, r8, r8 ");
1.982 + asm("cmp r8, r4 ");
1.983 + asm("bgt hssk_loop_inner_end ");
1.984 + asm("mla r0, r8, r10, r5 ");
1.985 + asm("ldrne r2, [r0, r11]! "); // r2=key[r8]
1.986 + asm("addeq r0, r0, r11 ");
1.987 + asm("ldr r1, [r0, -r10] "); // r1=key[r8-1]
1.988 + asm("subeq r8, r8, #1 ");
1.989 + asm("beq hssk_loop_inner2 ");
1.990 + asm("cmp r1, r2 ");
1.991 + asm("subgt r8, r8, #1 ");
1.992 + asm("movle r1, r2 ");
1.993 + asm("hssk_loop_inner2: ");
1.994 + asm("ldr r2, [sp, r11] "); // r2=key[sp]
1.995 + asm("cmp r1, r2 ");
1.996 + asm("bgt hssk_loop_inner ");
1.997 + asm("hssk_loop_inner_end: ");
1.998 + asm("mla r0, r9, r10, r5 "); // r0=&entry[r9]
1.999 + asm("mov r1, sp ");
1.1000 + asm("mov r2, r10 ");
1.1001 + asm("bl wordmove "); // entry[r9]=[sp]
1.1002 + asm("cmp r6, #0 ");
1.1003 + asm("bne hssk_loop_start1 ");
1.1004 + asm("sub r4, r4, #1 ");
1.1005 + asm("mla r1, r4, r10, r5 "); // r1=&entry[r4]
1.1006 + asm("mov r0, sp ");
1.1007 + asm("mov r2, r10 ");
1.1008 + asm("bl wordmove "); // [sp]=entry[r4]
1.1009 + asm("mla r0, r4, r10, r5 "); // r0=&entry[r4]
1.1010 + asm("mov r1, r5 "); // r1=&entry[0]
1.1011 + asm("mov r2, r10 ");
1.1012 + asm("bl wordmove "); // entry[0]=entry[r4]
1.1013 + asm("cmp r4, #1 ");
1.1014 + asm("mov r8, r6 ");
1.1015 + asm("mov r9, r6 ");
1.1016 + asm("bgt hssk_loop_start2 ");
1.1017 + asm("mov r0, r5 "); // r0=&entry[0]
1.1018 + asm("mov r1, sp ");
1.1019 + asm("mov r2, r10 ");
1.1020 + asm("bl wordmove "); // entry[0]=[sp]
1.1021 + asm("add sp, sp, r10 "); // free temporary stack space
1.1022 + __JUMP(,r7);
1.1023 + }
1.1024 +
1.1025 +EXPORT_C __NAKED__ void RArrayBase::HeapSortUnsigned()
1.1026 + {
1.1027 +#ifdef __EABI__
1.1028 + // need sp aligned correctly
1.1029 + asm("stmfd sp!, {r3-r11,lr} ");
1.1030 + __EH_FRAME_ADDRESS(sp,4)
1.1031 + __EH_FRAME_PUSH2(r4-r11,lr)
1.1032 +#else
1.1033 + asm("stmfd sp!, {r4-r11,lr} ");
1.1034 +#endif
1.1035 + asm("ldmia r0, {r4,r5,r10,r11} "); // r4=iCount, r5=iEntries, r10=entry size, r11=key offset
1.1036 + asm("cmp r10, #4 ");
1.1037 + asm("bleq HeapSortUnsigned ");
1.1038 + asm("cmp r10, #4 ");
1.1039 + asm("blne HeapSortUnsignedKey ");
1.1040 +#ifdef __EABI__
1.1041 + __POPRET("r3-r11,");
1.1042 +#else
1.1043 + __POPRET("r4-r11,");
1.1044 +#endif
1.1045 +
1.1046 + // Heap sort list of entries by unsigned key
1.1047 + // List address in r5, count in r4, entry size in r10, key offset in r11
1.1048 + // r4=ss, r6=sh
1.1049 + // r8,r9 modified
1.1050 + asm("HeapSortUnsignedKey: ");
1.1051 + asm("cmp r4, #1 ");
1.1052 + __JUMP(le,lr);
1.1053 + asm("mov r7, lr "); // save lr in r7
1.1054 + asm("sub sp, sp, r10 "); // get some temporary space on the stack
1.1055 + asm("mov r6, r4, lsr #1 ");
1.1056 + asm("hsuk_loop_start1: ");
1.1057 + asm("sub r6, r6, #1 ");
1.1058 + asm("mla r1, r6, r10, r5 "); // [sp]=entry[r6]
1.1059 + asm("mov r0, sp ");
1.1060 + asm("mov r2, r10 ");
1.1061 + asm("bl wordmove ");
1.1062 + asm("mov r8, r6 ");
1.1063 + asm("mov r9, r6 ");
1.1064 + asm("b hsuk_loop_start2 ");
1.1065 + asm("hsuk_loop_inner: ");
1.1066 + asm("mla r0, r9, r10, r5 "); // r0=&entry[r9]
1.1067 + asm("mla r1, r8, r10, r5 "); // r1=&entry[r8]
1.1068 + asm("mov r2, r10 ");
1.1069 + asm("bl wordmove "); // entry[r9]=entry[r8]
1.1070 + asm("mov r9, r8 ");
1.1071 + asm("hsuk_loop_start2: ");
1.1072 + asm("add r8, r8, #1 ");
1.1073 + asm("add r8, r8, r8 ");
1.1074 + asm("cmp r8, r4 ");
1.1075 + asm("bgt hsuk_loop_inner_end ");
1.1076 + asm("mla r0, r8, r10, r5 ");
1.1077 + asm("ldrne r2, [r0, r11]! "); // r2=key[r8]
1.1078 + asm("addeq r0, r0, r11 ");
1.1079 + asm("ldr r1, [r0, -r10] "); // r1=key[r8-1]
1.1080 + asm("subeq r8, r8, #1 ");
1.1081 + asm("beq hsuk_loop_inner2 ");
1.1082 + asm("cmp r1, r2 ");
1.1083 + asm("subhi r8, r8, #1 ");
1.1084 + asm("movls r1, r2 ");
1.1085 + asm("hsuk_loop_inner2: ");
1.1086 + asm("ldr r2, [sp, r11] "); // r2=key[sp]
1.1087 + asm("cmp r1, r2 ");
1.1088 + asm("bhi hsuk_loop_inner ");
1.1089 + asm("hsuk_loop_inner_end: ");
1.1090 + asm("mla r0, r9, r10, r5 "); // r0=&entry[r9]
1.1091 + asm("mov r1, sp ");
1.1092 + asm("mov r2, r10 ");
1.1093 + asm("bl wordmove "); // entry[r9]=[sp]
1.1094 + asm("cmp r6, #0 ");
1.1095 + asm("bne hsuk_loop_start1 ");
1.1096 + asm("sub r4, r4, #1 ");
1.1097 + asm("mla r1, r4, r10, r5 "); // r1=&entry[r4]
1.1098 + asm("mov r0, sp ");
1.1099 + asm("mov r2, r10 ");
1.1100 + asm("bl wordmove "); // [sp]=entry[r4]
1.1101 + asm("mla r0, r4, r10, r5 "); // r0=&entry[r4]
1.1102 + asm("mov r1, r5 "); // r1=&entry[0]
1.1103 + asm("mov r2, r10 ");
1.1104 + asm("bl wordmove "); // entry[0]=entry[r4]
1.1105 + asm("cmp r4, #1 ");
1.1106 + asm("mov r8, r6 ");
1.1107 + asm("mov r9, r6 ");
1.1108 + asm("bgt hsuk_loop_start2 ");
1.1109 + asm("mov r0, r5 "); // r0=&entry[0]
1.1110 + asm("mov r1, sp ");
1.1111 + asm("mov r2, r10 ");
1.1112 + asm("bl wordmove "); // entry[0]=[sp]
1.1113 + asm("add sp, sp, r10 "); // free temporary stack space
1.1114 + __JUMP(,r7);
1.1115 + }
1.1116 +
1.1117 +EXPORT_C __NAKED__ void RArrayBase::HeapSort(TGeneralLinearOrder anOrder)
1.1118 + {
1.1119 +#ifdef __EABI__
1.1120 + // need sp aligned correctly
1.1121 + asm("stmfd sp!, {r3-r11,lr} ");
1.1122 + __EH_FRAME_ADDRESS(sp,4)
1.1123 + __EH_FRAME_PUSH2(r4-r11,lr)
1.1124 +#else
1.1125 + asm("stmfd sp!, {r4-r11,lr} ");
1.1126 +#endif
1.1127 + asm("ldmia r0, {r4,r5,r10,r11} ");
1.1128 + asm("mov r7, r1 ");
1.1129 + asm("bl HeapSortEntries ");
1.1130 +#ifdef __EABI__
1.1131 + __POPRET("r3-r11,");
1.1132 +#else
1.1133 + __POPRET("r4-r11,");
1.1134 +#endif
1.1135 +
1.1136 + // Heap sort list of entries
1.1137 + // List address in r5, count in r4, entry size in r10, key offset in r11
1.1138 + // Address of ordering function in r7
1.1139 + // r4=ss, r6=sh
1.1140 + // r8,r9 modified
1.1141 + asm("HeapSortEntries: ");
1.1142 + asm("cmp r4, #1 ");
1.1143 + __JUMP(le,lr);
1.1144 + asm("str lr, [sp, #-4]! ");
1.1145 + asm("mov r8, sp "); // original SP
1.1146 + asm("sub sp, sp, r10 "); // get some temporary space on the stack
1.1147 + asm("sub sp, sp, #4 "); // make room for original SP
1.1148 + asm("bic sp, sp, #4 "); // align stack to 8 byte boundary
1.1149 + asm("str r8, [sp, r10] "); // save original SP
1.1150 + asm("mov r6, r4, lsr #1 ");
1.1151 + asm("hse_loop_start1: ");
1.1152 + asm("sub r6, r6, #1 ");
1.1153 + asm("mla r1, r6, r10, r5 "); // [sp]=entry[r6]
1.1154 + asm("mov r0, sp ");
1.1155 + asm("mov r2, r10 ");
1.1156 + asm("bl wordmove ");
1.1157 + asm("mov r8, r6 ");
1.1158 + asm("mov r9, r6 ");
1.1159 + asm("b hse_loop_start2 ");
1.1160 + asm("hse_loop_inner: ");
1.1161 + asm("mla r0, r9, r10, r5 "); // r0=&entry[r9]
1.1162 + asm("mla r1, r8, r10, r5 "); // r1=&entry[r8]
1.1163 + asm("mov r2, r10 ");
1.1164 + asm("bl wordmove "); // entry[r9]=entry[r8]
1.1165 + asm("mov r9, r8 ");
1.1166 + asm("hse_loop_start2: ");
1.1167 + asm("add r8, r8, #1 ");
1.1168 + asm("add r8, r8, r8 ");
1.1169 + asm("cmp r8, r4 ");
1.1170 + asm("bgt hse_loop_inner_end ");
1.1171 + asm("subeq r8, r8, #1 ");
1.1172 + asm("beq hse_loop_inner2 ");
1.1173 + asm("mla r1, r8, r10, r5 "); // r1=&entry[r8]
1.1174 + asm("sub r0, r1, r10 "); // r0=&entry[r8-1]
1.1175 + __JUMPL(7);
1.1176 + asm("cmp r0, #0 "); // compare entry[r8-1] with entry[r8]
1.1177 + asm("subgt r8, r8, #1 ");
1.1178 + asm("hse_loop_inner2: ");
1.1179 + asm("mla r0, r8, r10, r5 "); // r0=&entry[r8]
1.1180 + asm("mov r1, sp ");
1.1181 + __JUMPL(7);
1.1182 + asm("cmp r0, #0 "); // compare entry[r8] with [sp]
1.1183 + asm("bgt hse_loop_inner ");
1.1184 + asm("hse_loop_inner_end: ");
1.1185 + asm("mla r0, r9, r10, r5 "); // r0=&entry[r9]
1.1186 + asm("mov r1, sp ");
1.1187 + asm("mov r2, r10 ");
1.1188 + asm("bl wordmove "); // entry[r9]=[sp]
1.1189 + asm("cmp r6, #0 ");
1.1190 + asm("bne hse_loop_start1 ");
1.1191 + asm("sub r4, r4, #1 ");
1.1192 + asm("mla r1, r4, r10, r5 "); // r1=&entry[r4]
1.1193 + asm("mov r0, sp ");
1.1194 + asm("mov r2, r10 ");
1.1195 + asm("bl wordmove "); // [sp]=entry[r4]
1.1196 + asm("mla r0, r4, r10, r5 "); // r0=&entry[r4]
1.1197 + asm("mov r1, r5 "); // r1=&entry[0]
1.1198 + asm("mov r2, r10 ");
1.1199 + asm("bl wordmove "); // entry[0]=entry[r4]
1.1200 + asm("cmp r4, #1 ");
1.1201 + asm("mov r8, r6 ");
1.1202 + asm("mov r9, r6 ");
1.1203 + asm("bgt hse_loop_start2 ");
1.1204 + asm("mov r0, r5 "); // r0=&entry[0]
1.1205 + asm("mov r1, sp ");
1.1206 + asm("mov r2, r10 ");
1.1207 + asm("bl wordmove "); // entry[0]=[sp]
1.1208 + asm("ldr sp, [sp, r10] "); // restore stack pointer, freeing temporary stack space
1.1209 + __POPRET("");
1.1210 + }
1.1211 +#endif // __KERNEL_MODE__
1.1212 +#endif // __ARRAY_MACHINE_CODED__