149 lines · plain
1/*2 * strrchr - find last position of a character in a string.3 *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/* Assumptions:10 *11 * ARMv8-a, AArch6412 * Neon Available.13 */14 15#include "../asmdefs.h"16 17/* Arguments and results. */18#define srcin x019#define chrin w120 21#define result x022 23#define src x224#define tmp1 x325#define wtmp2 w426#define tmp3 x527#define src_match x628#define src_offset x729#define const_m1 x830#define tmp4 x931#define nul_match x1032#define chr_match x1133 34#define vrepchr v035#define vdata1 v136#define vdata2 v237#define vhas_nul1 v338#define vhas_nul2 v439#define vhas_chr1 v540#define vhas_chr2 v641#define vrepmask_0 v742#define vrepmask_c v1643#define vend1 v1744#define vend2 v1845 46/* Core algorithm.47 48 For each 32-byte hunk we calculate a 64-bit syndrome value, with49 two bits per byte (LSB is always in bits 0 and 1, for both big50 and little-endian systems). For each tuple, bit 0 is set iff51 the relevant byte matched the requested character; bit 1 is set52 iff the relevant byte matched the NUL end of string (we trigger53 off bit0 for the special case of looking for NUL). Since the bits54 in the syndrome reflect exactly the order in which things occur55 in the original string a count_trailing_zeros() operation will56 identify exactly which byte is causing the termination, and why. */57 58ENTRY (__strrchr_aarch64)59 /* Magic constant 0x40100401 to allow us to identify which lane60 matches the requested byte. Magic constant 0x80200802 used61 similarly for NUL termination. */62 mov wtmp2, #0x040163 movk wtmp2, #0x4010, lsl #1664 dup vrepchr.16b, chrin65 bic src, srcin, #31 /* Work with aligned 32-byte hunks. */66 dup vrepmask_c.4s, wtmp267 mov src_offset, #068 ands tmp1, srcin, #3169 add vrepmask_0.4s, vrepmask_c.4s, vrepmask_c.4s /* equiv: lsl #1 */70 b.eq L(aligned)71 72 /* Input string is not 32-byte aligned. Rather than forcing73 the padding bytes to a safe value, we calculate the syndrome74 for all the bytes, but then mask off those bits of the75 syndrome that are related to the padding. */76 ld1 {vdata1.16b, vdata2.16b}, [src], #3277 neg tmp1, tmp178 cmeq vhas_nul1.16b, vdata1.16b, #079 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b80 cmeq vhas_nul2.16b, vdata2.16b, #081 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b82 and vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b83 and vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b84 and vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b85 and vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b86 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b // 256->12887 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b // 256->12888 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul1.16b // 128->6489 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr1.16b // 128->6490 mov nul_match, vhas_nul1.d[0]91 lsl tmp1, tmp1, #192 mov const_m1, #~093 mov chr_match, vhas_chr1.d[0]94 lsr tmp3, const_m1, tmp195 96 bic nul_match, nul_match, tmp3 // Mask padding bits.97 bic chr_match, chr_match, tmp3 // Mask padding bits.98 cbnz nul_match, L(tail)99 100L(loop):101 cmp chr_match, #0102 csel src_match, src, src_match, ne103 csel src_offset, chr_match, src_offset, ne104L(aligned):105 ld1 {vdata1.16b, vdata2.16b}, [src], #32106 cmeq vhas_nul1.16b, vdata1.16b, #0107 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b108 cmeq vhas_nul2.16b, vdata2.16b, #0109 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b110 addp vend1.16b, vhas_nul1.16b, vhas_nul2.16b // 256->128111 and vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b112 and vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b113 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b // 256->128114 addp vend1.16b, vend1.16b, vend1.16b // 128->64115 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr1.16b // 128->64116 mov nul_match, vend1.d[0]117 mov chr_match, vhas_chr1.d[0]118 cbz nul_match, L(loop)119 120 and vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b121 and vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b122 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b123 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul1.16b124 mov nul_match, vhas_nul1.d[0]125 126L(tail):127 /* Work out exactly where the string ends. */128 sub tmp4, nul_match, #1129 eor tmp4, tmp4, nul_match130 ands chr_match, chr_match, tmp4131 /* And pick the values corresponding to the last match. */132 csel src_match, src, src_match, ne133 csel src_offset, chr_match, src_offset, ne134 135 /* Count down from the top of the syndrome to find the last match. */136 clz tmp3, src_offset137 /* Src_match points beyond the word containing the match, so we can138 simply subtract half the bit-offset into the syndrome. Because139 we are counting down, we need to go back one more character. */140 add tmp3, tmp3, #2141 sub result, src_match, tmp3, lsr #1142 /* But if the syndrome shows no match was found, then return NULL. */143 cmp src_offset, #0144 csel result, result, xzr, ne145 146 ret147 148END (__strrchr_aarch64)149