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.2 2013/01/28 06:23:14 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 mov ip, r0 /* we use r0 at the return value */ 51 mov r0, #0 /* return NULL by default */ 52 and r2, r1, #0xff /* restrict to byte value */ 531: tst ip, #3 /* test for word alignment */ 54 beq .Lpre_main_loop /* finally word aligned */ 55 ldrb r3, [ip], #1 /* load a byte */ 56 cmp r3, r2 /* did it match? */ 57 subeq r0, ip, #1 /* yes, remember that it did */ 58 teq r3, #0 /* was it NUL? */ 59 bne 1b /* no, try next byte */ 60 RET /* return */ 61.Lpre_main_loop: 62 push {r4, r5} /* save some registers */ 63#if defined(_ARM_ARCH_7) 64 movw r1, #0xfefe /* magic constant; 254 in each byte */ 65 movt r1, #0xfefe /* magic constant; 254 in each byte */ 66#elif defined(_ARM_ARCH_6) 67 mov r1, #0xfe /* put 254 in low byte */ 68 orr r1, r1, r1, lsl #8 /* move to next byte */ 69 orr r1, r1, r1, lsl #16 /* move to next halfword */ 70#endif /* _ARM_ARCH_6 */ 71 orr r2, r2, r2, lsl #8 /* move to next byte */ 72 orr r2, r2, r2, lsl #16 /* move to next halfword */ 73.Lmain_loop: 74 ldr r3, [ip], #4 /* load next word */ 75#if defined(_ARM_ARCH_6) 76 /* 77 * Add 254 to each byte using the UQADD8 (unsigned saturating add 8) 78 * instruction. For every non-NUL byte, the result for that byte will 79 * become 255. For NUL, it will be 254. When we complement the 80 * result, if the result is non-0 then we must have encountered a NUL. 81 */ 82 uqadd8 r4, r3, r1 /* NUL detection happens here */ 83 usub8 r3, r3, r2 /* bias for char looked for? */ 84 uqadd8 r5, r3, r1 /* char detection happens here */ 85 and r3, r4, r5 /* merge results */ 86 mvns r3, r3 /* is the complement non-0? */ 87 beq .Lmain_loop /* no, then keep going */ 88 89 mvns r5, r5 /* get we find any matching bytes? */ 90 beq .Ldone /* no, then we hit the end, return */ 91 mvns r4, r4 /* did we encounter a NUL? */ 92 beq .Lfind_match /* no, find matching byte */ 93 /* 94 * Copy the NUL bit to the following byte lanes. Then clear any match 95 * bits in those byte lanes to prevent false positives in those bytes. 96 */ 97 bics r5, r5, r4 /* clear any NUL match bits */ 98 beq .Ldone /* no remaining matches, we're done */ 99 movs r3, r4, lshi #8 /* shift up a byte */ 100 orrnes r3, r3, r3, lshi #8 /* if non 0, copy up to next byte */ 101 orrnes r3, r3, r3, lshi #8 /* if non 0, copy up to last byte */ 102 bics r5, r5, r3 /* clear match bits */ 103 beq .Ldone /* no remaining matches, we're done */ 104.Lfind_match: 105#ifdef __ARMEL__ 106 rev r5, r5 /* we want this in BE for the CLZ */ 107#endif 108 /* 109 * If we have multiple matches, we want to the select the "last" match 110 * in the word which will be the lowest bit set. 111 */ 112 sub r3, r5, #1 /* subtract 1 */ 113 and r3, r3, r5 /* and with mask */ 114 eor r5, r5, r3 /* only have the lowest bit set left */ 115 clz r5, r5 /* count how many leading zeros */ 116 add r0, ip, r5, lsr #3 /* divide that by 8 and add to count */ 117 sub r0, r0, #4 /* compensate for the post-inc */ 118 teq r4, #0 /* did we read any NULs? */ 119 beq .Lmain_loop /* no, get next word */ 120#else 121 /* 122 * No fancy shortcuts so just test each byte lane for a NUL. 123 * (other tests for NULs in a word take more instructions/cycles). 124 */ 125 eor r4, r3, r2 /* xor .. */ 126 tst r3, #BYTE0 /* is byte 0 a NUL? */ 127 beq .Ldone /* yes, then we're done */ 128 tst r4, #BYTE0 /* is byte 0 a match? */ 129 subeq r0, ip, #4 /* yes, remember its location */ 130 tst r3, #BYTE1 /* is byte 1 a NUL? */ 131 beq .Ldone /* yes, then we're done */ 132 tst r4, #BYTE1 /* is byte 1 a match? */ 133 subeq r0, ip, #3 /* yes, remember its location */ 134 tst r3, #BYTE2 /* is byte 2 a NUL? */ 135 beq .Ldone /* yes, then we're done */ 136 tst r4, #BYTE2 /* is byte 2 a match? */ 137 subeq r0, ip, #2 /* yes, remember its location */ 138 tst r3, #BYTE3 /* is byte 3 a NUL? */ 139 beq .Ldone /* yes, then we're done */ 140 tst r4, #BYTE3 /* is byte 3 a match? */ 141 subeq r0, ip, #1 /* yes, remember its location */ 142 b .Lmain_loop 143#endif /* _ARM_ARCH_6 */ 144.Ldone: 145 pop {r4, r5} 146 RET 147END(strrchr) 148