1/*- 2 * Copyright (c) 2013 The NetBSD Foundation, Inc. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to The NetBSD Foundation 6 * by Matt Thomas of 3am Software Foundry. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 18 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 19 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 21 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 22 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 23 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 25 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 27 * POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30#include <machine/asm.h> 31 32RCSID("$NetBSD: strrchr_arm.S,v 1.3 2013/02/08 02:19:36 matt Exp $") 33 34#ifdef __ARMEL__ 35#define BYTE0 0x000000ff 36#define BYTE1 0x0000ff00 37#define BYTE2 0x00ff0000 38#define BYTE3 0xff000000 39#define lshi lsl 40#else 41#define BYTE0 0xff000000 42#define BYTE1 0x00ff0000 43#define BYTE2 0x0000ff00 44#define BYTE3 0x000000ff 45#define lshi lsr 46#endif 47 48 .text 49ENTRY(strrchr) 50 teq r1, #0 /* searching for NUL? */ 51 bne 1f /* no, do it the hard way */ 52 push {r0, lr} /* save pointer and return addr */ 53 bl PLT_SYM(strlen) /* get length */ 54 pop {r1, lr} /* restore pointer and returna addr */ 55 add r0, r0, r1 /* add pointer to length */ 56 RET /* return */ 57 581: mov ip, r0 /* we use r0 at the return value */ 59 mov r0, #0 /* return NULL by default */ 60 and r2, r1, #0xff /* restrict to byte value */ 612: tst ip, #3 /* test for word alignment */ 62 beq .Lpre_main_loop /* finally word aligned */ 63 ldrb r3, [ip], #1 /* load a byte */ 64 cmp r3, r2 /* did it match? */ 65 subeq r0, ip, #1 /* yes, remember that it did */ 66 teq r3, #0 /* was it NUL? */ 67 bne 2b /* no, try next byte */ 68 RET /* return */ 69.Lpre_main_loop: 70 push {r4, r5} /* save some registers */ 71#if defined(_ARM_ARCH_7) 72 movw r1, #0xfefe /* magic constant; 254 in each byte */ 73 movt r1, #0xfefe /* magic constant; 254 in each byte */ 74#elif defined(_ARM_ARCH_6) 75 mov r1, #0xfe /* put 254 in low byte */ 76 orr r1, r1, r1, lsl #8 /* move to next byte */ 77 orr r1, r1, r1, lsl #16 /* move to next halfword */ 78#endif /* _ARM_ARCH_6 */ 79 orr r2, r2, r2, lsl #8 /* move to next byte */ 80 orr r2, r2, r2, lsl #16 /* move to next halfword */ 81.Lmain_loop: 82 ldr r3, [ip], #4 /* load next word */ 83#if defined(_ARM_ARCH_6) 84 /* 85 * Add 254 to each byte using the UQADD8 (unsigned saturating add 8) 86 * instruction. For every non-NUL byte, the result for that byte will 87 * become 255. For NUL, it will be 254. When we complement the 88 * result, if the result is non-0 then we must have encountered a NUL. 89 */ 90 uqadd8 r4, r3, r1 /* NUL detection happens here */ 91 usub8 r3, r3, r2 /* bias for char looked for? */ 92 uqadd8 r5, r3, r1 /* char detection happens here */ 93 and r3, r4, r5 /* merge results */ 94 mvns r3, r3 /* is the complement non-0? */ 95 beq .Lmain_loop /* no, then keep going */ 96 97 mvns r5, r5 /* get we find any matching bytes? */ 98 beq .Ldone /* no, then we hit the end, return */ 99 mvns r4, r4 /* did we encounter a NUL? */ 100 beq .Lfind_match /* no, find matching byte */ 101 /* 102 * Copy the NUL bit to the following byte lanes. Then clear any match 103 * bits in those byte lanes to prevent false positives in those bytes. 104 */ 105 bics r5, r5, r4 /* clear any NUL match bits */ 106 beq .Ldone /* no remaining matches, we're done */ 107 movs r3, r4, lshi #8 /* shift up a byte */ 108 orrnes r3, r3, r3, lshi #8 /* if non 0, copy up to next byte */ 109 orrnes r3, r3, r3, lshi #8 /* if non 0, copy up to last byte */ 110 bics r5, r5, r3 /* clear match bits */ 111 beq .Ldone /* no remaining matches, we're done */ 112.Lfind_match: 113#ifdef __ARMEL__ 114 rev r5, r5 /* we want this in BE for the CLZ */ 115#endif 116 /* 117 * If we have multiple matches, we want to the select the "last" match 118 * in the word which will be the lowest bit set. 119 */ 120 sub r3, r5, #1 /* subtract 1 */ 121 and r3, r3, r5 /* and with mask */ 122 eor r5, r5, r3 /* only have the lowest bit set left */ 123 clz r5, r5 /* count how many leading zeros */ 124 add r0, ip, r5, lsr #3 /* divide that by 8 and add to count */ 125 sub r0, r0, #4 /* compensate for the post-inc */ 126 teq r4, #0 /* did we read any NULs? */ 127 beq .Lmain_loop /* no, get next word */ 128#else 129 /* 130 * No fancy shortcuts so just test each byte lane for a NUL. 131 * (other tests for NULs in a word take more instructions/cycles). 132 */ 133 eor r4, r3, r2 /* xor .. */ 134 tst r3, #BYTE0 /* is byte 0 a NUL? */ 135 beq .Ldone /* yes, then we're done */ 136 tst r4, #BYTE0 /* is byte 0 a match? */ 137 subeq r0, ip, #4 /* yes, remember its location */ 138 tst r3, #BYTE1 /* is byte 1 a NUL? */ 139 beq .Ldone /* yes, then we're done */ 140 tst r4, #BYTE1 /* is byte 1 a match? */ 141 subeq r0, ip, #3 /* yes, remember its location */ 142 tst r3, #BYTE2 /* is byte 2 a NUL? */ 143 beq .Ldone /* yes, then we're done */ 144 tst r4, #BYTE2 /* is byte 2 a match? */ 145 subeq r0, ip, #2 /* yes, remember its location */ 146 tst r3, #BYTE3 /* is byte 3 a NUL? */ 147 beq .Ldone /* yes, then we're done */ 148 tst r4, #BYTE3 /* is byte 3 a match? */ 149 subeq r0, ip, #1 /* yes, remember its location */ 150 b .Lmain_loop 151#endif /* _ARM_ARCH_6 */ 152.Ldone: 153 pop {r4, r5} 154 RET 155END(strrchr) 156