133 lines · plain
1/*2 * strchr - find a character in a string3 *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 28#define vrepchr v029#define vdata1 v130#define vdata2 v231#define vhas_nul1 v332#define vhas_nul2 v433#define vhas_chr1 v534#define vhas_chr2 v635#define vrepmask_0 v736#define vrepmask_c v1637#define vend1 v1738#define vend2 v1839 40/* Core algorithm.41 42 For each 32-byte hunk we calculate a 64-bit syndrome value, with43 two bits per byte (LSB is always in bits 0 and 1, for both big44 and little-endian systems). For each tuple, bit 0 is set iff45 the relevant byte matched the requested character; bit 1 is set46 iff the relevant byte matched the NUL end of string (we trigger47 off bit0 for the special case of looking for NUL). Since the bits48 in the syndrome reflect exactly the order in which things occur49 in the original string a count_trailing_zeros() operation will50 identify exactly which byte is causing the termination, and why. */51 52/* Locals and temporaries. */53 54ENTRY (__strchr_aarch64)55 /* Magic constant 0x40100401 to allow us to identify which lane56 matches the requested byte. Magic constant 0x80200802 used57 similarly for NUL termination. */58 mov wtmp2, #0x040159 movk wtmp2, #0x4010, lsl #1660 dup vrepchr.16b, chrin61 bic src, srcin, #31 /* Work with aligned 32-byte hunks. */62 dup vrepmask_c.4s, wtmp263 ands tmp1, srcin, #3164 add vrepmask_0.4s, vrepmask_c.4s, vrepmask_c.4s /* equiv: lsl #1 */65 b.eq L(loop)66 67 /* Input string is not 32-byte aligned. Rather than forcing68 the padding bytes to a safe value, we calculate the syndrome69 for all the bytes, but then mask off those bits of the70 syndrome that are related to the padding. */71 ld1 {vdata1.16b, vdata2.16b}, [src], #3272 neg tmp1, tmp173 cmeq vhas_nul1.16b, vdata1.16b, #074 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b75 cmeq vhas_nul2.16b, vdata2.16b, #076 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b77 and vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b78 and vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b79 and vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b80 and vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b81 orr vend1.16b, vhas_nul1.16b, vhas_chr1.16b82 orr vend2.16b, vhas_nul2.16b, vhas_chr2.16b83 lsl tmp1, tmp1, #184 addp vend1.16b, vend1.16b, vend2.16b // 256->12885 mov tmp3, #~086 addp vend1.16b, vend1.16b, vend2.16b // 128->6487 lsr tmp1, tmp3, tmp188 89 mov tmp3, vend1.d[0]90 bic tmp1, tmp3, tmp1 // Mask padding bits.91 cbnz tmp1, L(tail)92 93L(loop):94 ld1 {vdata1.16b, vdata2.16b}, [src], #3295 cmeq vhas_nul1.16b, vdata1.16b, #096 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b97 cmeq vhas_nul2.16b, vdata2.16b, #098 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b99 /* Use a fast check for the termination condition. */100 orr vend1.16b, vhas_nul1.16b, vhas_chr1.16b101 orr vend2.16b, vhas_nul2.16b, vhas_chr2.16b102 orr vend1.16b, vend1.16b, vend2.16b103 addp vend1.2d, vend1.2d, vend1.2d104 mov tmp1, vend1.d[0]105 cbz tmp1, L(loop)106 107 /* Termination condition found. Now need to establish exactly why108 we terminated. */109 and vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b110 and vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b111 and vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b112 and vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b113 orr vend1.16b, vhas_nul1.16b, vhas_chr1.16b114 orr vend2.16b, vhas_nul2.16b, vhas_chr2.16b115 addp vend1.16b, vend1.16b, vend2.16b // 256->128116 addp vend1.16b, vend1.16b, vend2.16b // 128->64117 118 mov tmp1, vend1.d[0]119L(tail):120 /* Count the trailing zeros, by bit reversing... */121 rbit tmp1, tmp1122 /* Re-bias source. */123 sub src, src, #32124 clz tmp1, tmp1 /* And counting the leading zeros. */125 /* Tmp1 is even if the target charager was found first. Otherwise126 we've found the end of string and we weren't looking for NUL. */127 tst tmp1, #1128 add result, src, tmp1, lsr #1129 csel result, result, xzr, eq130 ret131 132END (__strchr_aarch64)133