145 lines · plain
1/*2 * memchr - find a character in a memory zone3 *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#define cntin x221 22#define result x023 24#define src x325#define tmp x426#define wtmp2 w527#define synd x628#define soff x929#define cntrem x1030 31#define vrepchr v032#define vdata1 v133#define vdata2 v234#define vhas_chr1 v335#define vhas_chr2 v436#define vrepmask v537#define vend v638 39/*40 * Core algorithm:41 *42 * For each 32-byte chunk we calculate a 64-bit syndrome value, with two bits43 * per byte. For each tuple, bit 0 is set if the relevant byte matched the44 * requested character and bit 1 is not used (faster than using a 32bit45 * syndrome). Since the bits in the syndrome reflect exactly the order in which46 * things occur in the original string, counting trailing zeros allows to47 * identify exactly which byte has matched.48 */49 50ENTRY (__memchr_aarch64)51 /* Do not dereference srcin if no bytes to compare. */52 cbz cntin, L(zero_length)53 /*54 * Magic constant 0x40100401 allows us to identify which lane matches55 * the requested byte.56 */57 mov wtmp2, #0x040158 movk wtmp2, #0x4010, lsl #1659 dup vrepchr.16b, chrin60 /* Work with aligned 32-byte chunks */61 bic src, srcin, #3162 dup vrepmask.4s, wtmp263 ands soff, srcin, #3164 and cntrem, cntin, #3165 b.eq L(loop)66 67 /*68 * Input string is not 32-byte aligned. We calculate the syndrome69 * value for the aligned 32 bytes block containing the first bytes70 * and mask the irrelevant part.71 */72 73 ld1 {vdata1.16b, vdata2.16b}, [src], #3274 sub tmp, soff, #3275 adds cntin, cntin, tmp76 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b77 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b78 and vhas_chr1.16b, vhas_chr1.16b, vrepmask.16b79 and vhas_chr2.16b, vhas_chr2.16b, vrepmask.16b80 addp vend.16b, vhas_chr1.16b, vhas_chr2.16b /* 256->128 */81 addp vend.16b, vend.16b, vend.16b /* 128->64 */82 mov synd, vend.d[0]83 /* Clear the soff*2 lower bits */84 lsl tmp, soff, #185 lsr synd, synd, tmp86 lsl synd, synd, tmp87 /* The first block can also be the last */88 b.ls L(masklast)89 /* Have we found something already? */90 cbnz synd, L(tail)91 92L(loop):93 ld1 {vdata1.16b, vdata2.16b}, [src], #3294 subs cntin, cntin, #3295 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b96 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b97 /* If we're out of data we finish regardless of the result */98 b.ls L(end)99 /* Use a fast check for the termination condition */100 orr vend.16b, vhas_chr1.16b, vhas_chr2.16b101 addp vend.2d, vend.2d, vend.2d102 mov synd, vend.d[0]103 /* We're not out of data, loop if we haven't found the character */104 cbz synd, L(loop)105 106L(end):107 /* Termination condition found, let's calculate the syndrome value */108 and vhas_chr1.16b, vhas_chr1.16b, vrepmask.16b109 and vhas_chr2.16b, vhas_chr2.16b, vrepmask.16b110 addp vend.16b, vhas_chr1.16b, vhas_chr2.16b /* 256->128 */111 addp vend.16b, vend.16b, vend.16b /* 128->64 */112 mov synd, vend.d[0]113 /* Only do the clear for the last possible block */114 b.hi L(tail)115 116L(masklast):117 /* Clear the (32 - ((cntrem + soff) % 32)) * 2 upper bits */118 add tmp, cntrem, soff119 and tmp, tmp, #31120 sub tmp, tmp, #32121 neg tmp, tmp, lsl #1122 lsl synd, synd, tmp123 lsr synd, synd, tmp124 125L(tail):126 /* Count the trailing zeros using bit reversing */127 rbit synd, synd128 /* Compensate the last post-increment */129 sub src, src, #32130 /* Check that we have found a character */131 cmp synd, #0132 /* And count the leading zeros */133 clz synd, synd134 /* Compute the potential result */135 add result, src, synd, lsr #1136 /* Select result or NULL */137 csel result, xzr, result, eq138 ret139 140L(zero_length):141 mov result, #0142 ret143 144END (__memchr_aarch64)145