Warning: That file was not part of the compilation database. It may have many parsing errors.

1/* strrchr: find the last instance of a character in a string.
2
3 Copyright (C) 2014-2019 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 <http://www.gnu.org/licenses/>. */
20
21#include <sysdep.h>
22
23/* Assumptions:
24 *
25 * ARMv8-a, AArch64
26 * Neon Available.
27 */
28
29/* Arguments and results. */
30#define srcin x0
31#define chrin w1
32
33#define result x0
34
35#define src x2
36#define tmp1 x3
37#define wtmp2 w4
38#define tmp3 x5
39#define src_match x6
40#define src_offset x7
41#define const_m1 x8
42#define tmp4 x9
43#define nul_match x10
44#define chr_match x11
45
46#define vrepchr v0
47#define vdata1 v1
48#define vdata2 v2
49#define vhas_nul1 v3
50#define vhas_nul2 v4
51#define vhas_chr1 v5
52#define vhas_chr2 v6
53#define vrepmask_0 v7
54#define vrepmask_c v16
55#define vend1 v17
56#define vend2 v18
57
58/* Core algorithm.
59
60 For each 32-byte hunk we calculate a 64-bit syndrome value, with
61 two bits per byte (LSB is always in bits 0 and 1, for both big
62 and little-endian systems). For each tuple, bit 0 is set iff
63 the relevant byte matched the requested character; bit 1 is set
64 iff the relevant byte matched the NUL end of string (we trigger
65 off bit0 for the special case of looking for NUL). Since the bits
66 in the syndrome reflect exactly the order in which things occur
67 in the original string a count_trailing_zeros() operation will
68 identify exactly which byte is causing the termination, and why. */
69
70ENTRY(strrchr)
71 DELOUSE (0)
72 cbz x1, L(null_search)
73 /* Magic constant 0x40100401 to allow us to identify which lane
74 matches the requested byte. Magic constant 0x80200802 used
75 similarly for NUL termination. */
76 mov wtmp2, #0x0401
77 movk wtmp2, #0x4010, lsl #16
78 dup vrepchr.16b, chrin
79 bic src, srcin, #31 /* Work with aligned 32-byte hunks. */
80 dup vrepmask_c.4s, wtmp2
81 mov src_offset, #0
82 ands tmp1, srcin, #31
83 add vrepmask_0.4s, vrepmask_c.4s, vrepmask_c.4s /* equiv: lsl #1 */
84 b.eq L(aligned)
85
86 /* Input string is not 32-byte aligned. Rather than forcing
87 the padding bytes to a safe value, we calculate the syndrome
88 for all the bytes, but then mask off those bits of the
89 syndrome that are related to the padding. */
90 ld1 {vdata1.16b, vdata2.16b}, [src], #32
91 neg tmp1, tmp1
92 cmeq vhas_nul1.16b, vdata1.16b, #0
93 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b
94 cmeq vhas_nul2.16b, vdata2.16b, #0
95 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b
96 and vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b
97 and vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
98 and vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
99 and vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
100 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b // 256->128
101 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b // 256->128
102 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul1.16b // 128->64
103 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr1.16b // 128->64
104 mov nul_match, vhas_nul1.2d[0]
105 lsl tmp1, tmp1, #1
106 mov const_m1, #~0
107 mov chr_match, vhas_chr1.2d[0]
108 lsr tmp3, const_m1, tmp1
109
110 bic nul_match, nul_match, tmp3 // Mask padding bits.
111 bic chr_match, chr_match, tmp3 // Mask padding bits.
112 cbnz nul_match, L(tail)
113
114L(loop):
115 cmp chr_match, #0
116 csel src_match, src, src_match, ne
117 csel src_offset, chr_match, src_offset, ne
118L(aligned):
119 ld1 {vdata1.16b, vdata2.16b}, [src], #32
120 cmeq vhas_nul1.16b, vdata1.16b, #0
121 cmeq vhas_chr1.16b, vdata1.16b, vrepchr.16b
122 cmeq vhas_nul2.16b, vdata2.16b, #0
123 cmeq vhas_chr2.16b, vdata2.16b, vrepchr.16b
124 addp vend1.16b, vhas_nul1.16b, vhas_nul2.16b // 256->128
125 and vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
126 and vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
127 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b // 256->128
128 addp vend1.16b, vend1.16b, vend1.16b // 128->64
129 addp vhas_chr1.16b, vhas_chr1.16b, vhas_chr1.16b // 128->64
130 mov nul_match, vend1.2d[0]
131 mov chr_match, vhas_chr1.2d[0]
132 cbz nul_match, L(loop)
133
134 and vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b
135 and vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
136 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b
137 addp vhas_nul1.16b, vhas_nul1.16b, vhas_nul1.16b
138 mov nul_match, vhas_nul1.2d[0]
139
140L(tail):
141 /* Work out exactly where the string ends. */
142 sub tmp4, nul_match, #1
143 eor tmp4, tmp4, nul_match
144 ands chr_match, chr_match, tmp4
145 /* And pick the values corresponding to the last match. */
146 csel src_match, src, src_match, ne
147 csel src_offset, chr_match, src_offset, ne
148
149 /* Count down from the top of the syndrome to find the last match. */
150 clz tmp3, src_offset
151 /* Src_match points beyond the word containing the match, so we can
152 simply subtract half the bit-offset into the syndrome. Because
153 we are counting down, we need to go back one more character. */
154 add tmp3, tmp3, #2
155 sub result, src_match, tmp3, lsr #1
156 /* But if the syndrome shows no match was found, then return NULL. */
157 cmp src_offset, #0
158 csel result, result, xzr, ne
159
160 ret
161L(null_search):
162 b __strchrnul
163
164END(strrchr)
165weak_alias (strrchr, rindex)
166libc_hidden_builtin_def (strrchr)
167

Warning: That file was not part of the compilation database. It may have many parsing errors.