1/* memchr - find a character in a memory zone
2
3 Copyright (C) 2015-2024 Free Software Foundation, Inc.
4
5 This file is part of the GNU C Library.
6
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 2.1 of the License, or (at your option) any later version.
11
12 The GNU C Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
16
17 You should have received a copy of the GNU Lesser General Public
18 License along with the GNU C Library. If not, see
19 <https://www.gnu.org/licenses/>. */
20
21#include <sysdep.h>
22
23/* Assumptions:
24 *
25 * ARMv8-a, AArch64, Advanced SIMD.
26 * MTE compatible.
27 */
28
29#ifndef MEMCHR
30# define MEMCHR __memchr
31#endif
32
33#define srcin x0
34#define chrin w1
35#define cntin x2
36#define result x0
37
38#define src x3
39#define cntrem x4
40#define synd x5
41#define shift x6
42#define tmp x7
43
44#define vrepchr v0
45#define qdata q1
46#define vdata v1
47#define vhas_chr v2
48#define vend v3
49#define dend d3
50
51/*
52 Core algorithm:
53 For each 16-byte chunk we calculate a 64-bit nibble mask value with four bits
54 per byte. We take 4 bits of every comparison byte with shift right and narrow
55 by 4 instruction. Since the bits in the nibble mask reflect the order in
56 which things occur in the original string, counting leading zeros identifies
57 exactly which byte matched. */
58
59ENTRY (MEMCHR)
60 PTR_ARG (0)
61 SIZE_ARG (2)
62 bic src, srcin, 15
63 cbz cntin, L(nomatch)
64 ld1 {vdata.16b}, [src]
65 dup vrepchr.16b, chrin
66 cmeq vhas_chr.16b, vdata.16b, vrepchr.16b
67 lsl shift, srcin, 2
68 shrn vend.8b, vhas_chr.8h, 4 /* 128->64 */
69 fmov synd, dend
70 lsr synd, synd, shift
71 cbz synd, L(start_loop)
72
73 rbit synd, synd
74 clz synd, synd
75 cmp cntin, synd, lsr 2
76 add result, srcin, synd, lsr 2
77 csel result, result, xzr, hi
78 ret
79
80 .p2align 3
81L(start_loop):
82 sub tmp, src, srcin
83 add tmp, tmp, 17
84 subs cntrem, cntin, tmp
85 b.lo L(nomatch)
86
87 /* Make sure that it won't overread by a 16-byte chunk */
88 tbz cntrem, 4, L(loop32_2)
89 sub src, src, 16
90 .p2align 4
91L(loop32):
92 ldr qdata, [src, 32]!
93 cmeq vhas_chr.16b, vdata.16b, vrepchr.16b
94 umaxp vend.16b, vhas_chr.16b, vhas_chr.16b /* 128->64 */
95 fmov synd, dend
96 cbnz synd, L(end)
97
98L(loop32_2):
99 ldr qdata, [src, 16]
100 cmeq vhas_chr.16b, vdata.16b, vrepchr.16b
101 subs cntrem, cntrem, 32
102 b.lo L(end_2)
103 umaxp vend.16b, vhas_chr.16b, vhas_chr.16b /* 128->64 */
104 fmov synd, dend
105 cbz synd, L(loop32)
106L(end_2):
107 add src, src, 16
108L(end):
109 shrn vend.8b, vhas_chr.8h, 4 /* 128->64 */
110 sub cntrem, src, srcin
111 fmov synd, dend
112 sub cntrem, cntin, cntrem
113#ifndef __AARCH64EB__
114 rbit synd, synd
115#endif
116 clz synd, synd
117 cmp cntrem, synd, lsr 2
118 add result, src, synd, lsr 2
119 csel result, result, xzr, hi
120 ret
121
122L(nomatch):
123 mov result, 0
124 ret
125
126END (MEMCHR)
127weak_alias (MEMCHR, memchr)
128libc_hidden_builtin_def (memchr)
129

source code of glibc/sysdeps/aarch64/memchr.S