135 lines · plain
1/*2 * memchr - scan memory for a character3 *4 * Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5 * See https://llvm.org/LICENSE.txt for license information.6 * SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7 */8 9/*10 Written by Dave Gilbert <david.gilbert@linaro.org>11 12 This __memchr_arm routine is optimised on a Cortex-A9 and should work on13 all ARMv7 processors. It has a fast past for short sizes, and has14 an optimised path for large data sets; the worst case is finding the15 match early in a large data set.16 17 */18 19@ 2011-02-07 david.gilbert@linaro.org20@ Extracted from local git a5b438d86121@ 2011-07-14 david.gilbert@linaro.org22@ Import endianness fix from local git ea786f1b23@ 2011-12-07 david.gilbert@linaro.org24@ Removed unneeded cbz from align loop25 26 .syntax unified27 .arch armv7-a28 29@ this lets us check a flag in a 00/ff byte easily in either endianness30#ifdef __ARMEB__31#define CHARTSTMASK(c) 1<<(31-(c*8))32#else33#define CHARTSTMASK(c) 1<<(c*8)34#endif35 .text36 .thumb37 38@ ---------------------------------------------------------------------------39 .thumb_func40 .align 241 .p2align 4,,1542 .global __memchr_arm43 .type __memchr_arm,%function44__memchr_arm:45 @ r0 = start of memory to scan46 @ r1 = character to look for47 @ r2 = length48 @ returns r0 = pointer to character or NULL if not found49 and r1,r1,#0xff @ Don't think we can trust the caller to actually pass a char50 51 cmp r2,#16 @ If it's short don't bother with anything clever52 blt 20f53 54 tst r0, #7 @ If it's already aligned skip the next bit55 beq 10f56 57 @ Work up to an aligned point585:59 ldrb r3, [r0],#160 subs r2, r2, #161 cmp r3, r162 beq 50f @ If it matches exit found63 tst r0, #764 bne 5b @ If not aligned yet then do next byte65 6610:67 @ At this point, we are aligned, we know we have at least 8 bytes to work with68 push {r4,r5,r6,r7}69 orr r1, r1, r1, lsl #8 @ expand the match word across to all bytes70 orr r1, r1, r1, lsl #1671 bic r4, r2, #7 @ Number of double words to work with72 mvns r7, #0 @ all F's73 movs r3, #074 7515:76 ldmia r0!,{r5,r6}77 subs r4, r4, #878 eor r5,r5, r1 @ Get it so that r5,r6 have 00's where the bytes match the target79 eor r6,r6, r180 uadd8 r5, r5, r7 @ Parallel add 0xff - sets the GE bits for anything that wasn't 081 sel r5, r3, r7 @ bytes are 00 for none-00 bytes, or ff for 00 bytes - NOTE INVERSION82 uadd8 r6, r6, r7 @ Parallel add 0xff - sets the GE bits for anything that wasn't 083 sel r6, r5, r7 @ chained....bytes are 00 for none-00 bytes, or ff for 00 bytes - NOTE INVERSION84 cbnz r6, 60f85 bne 15b @ (Flags from the subs above) If not run out of bytes then go around again86 87 pop {r4,r5,r6,r7}88 and r1,r1,#0xff @ Get r1 back to a single character from the expansion above89 and r2,r2,#7 @ Leave the count remaining as the number after the double words have been done90 9120:92 cbz r2, 40f @ 0 length or hit the end already then not found93 9421: @ Post aligned section, or just a short call95 ldrb r3,[r0],#196 subs r2,r2,#197 eor r3,r3,r1 @ r3 = 0 if match - doesn't break flags from sub98 cbz r3, 50f99 bne 21b @ on r2 flags100 10140:102 movs r0,#0 @ not found103 bx lr104 10550:106 subs r0,r0,#1 @ found107 bx lr108 10960: @ We're here because the fast path found a hit - now we have to track down exactly which word it was110 @ r0 points to the start of the double word after the one that was tested111 @ r5 has the 00/ff pattern for the first word, r6 has the chained value112 cmp r5, #0113 itte eq114 moveq r5, r6 @ the end is in the 2nd word115 subeq r0,r0,#3 @ Points to 2nd byte of 2nd word116 subne r0,r0,#7 @ or 2nd byte of 1st word117 118 @ r0 currently points to the 3rd byte of the word containing the hit119 tst r5, # CHARTSTMASK(0) @ 1st character120 bne 61f121 adds r0,r0,#1122 tst r5, # CHARTSTMASK(1) @ 2nd character123 ittt eq124 addeq r0,r0,#1125 tsteq r5, # (3<<15) @ 2nd & 3rd character126 @ If not the 3rd must be the last one127 addeq r0,r0,#1128 12961:130 pop {r4,r5,r6,r7}131 subs r0,r0,#1132 bx lr133 134 .size __memchr_arm, . - __memchr_arm135