1 | /* Optimized version of the standard memchr() function. |
2 | This file is part of the GNU C Library. |
3 | Copyright (C) 2000-2022 Free Software Foundation, Inc. |
4 | |
5 | The GNU C Library is free software; you can redistribute it and/or |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either |
8 | version 2.1 of the License, or (at your option) any later version. |
9 | |
10 | The GNU C Library is distributed in the hope that it will be useful, |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Lesser General Public License for more details. |
14 | |
15 | You should have received a copy of the GNU Lesser General Public |
16 | License along with the GNU C Library; if not, see |
17 | <https://www.gnu.org/licenses/>. */ |
18 | |
19 | /* Return: the address of the first occurence of chr in str or NULL |
20 | |
21 | Inputs: |
22 | in0: str |
23 | in1: chr |
24 | in2: byte count |
25 | |
26 | This implementation assumes little endian mode. For big endian mode, |
27 | the instruction czx1.r should be replaced by czx1.l. |
28 | |
29 | The algorithm is fairly straightforward: search byte by byte until we |
30 | we get to a word aligned address, then search word by word as much as |
31 | possible; the remaining few bytes are searched one at a time. |
32 | |
33 | The word by word search is performed by xor-ing the word with a word |
34 | containing chr in every byte. If there is a hit, the result will |
35 | contain a zero byte in the corresponding position. The presence and |
36 | position of that zero byte is detected with a czx instruction. |
37 | |
38 | All the loops in this function could have had the internal branch removed |
39 | if br.ctop and br.cloop could be predicated :-(. */ |
40 | |
41 | #include <sysdep.h> |
42 | #undef ret |
43 | |
44 | #define saved_pr r15 |
45 | #define saved_lc r16 |
46 | #define chr r17 |
47 | #define len r18 |
48 | #define last r20 |
49 | #define val r21 |
50 | #define tmp r24 |
51 | #define chrx8 r25 |
52 | #define loopcnt r30 |
53 | |
54 | #define str in0 |
55 | |
56 | ENTRY(__memchr) |
57 | .prologue |
58 | alloc r2 = ar.pfs, 3, 0, 29, 32 |
59 | #include "softpipe.h" |
60 | .rotr value[MEMLAT+1], addr[MEMLAT+3], aux[2], poschr[2] |
61 | .rotp p[MEMLAT+3] |
62 | .save ar.lc, saved_lc |
63 | mov saved_lc = ar.lc // save the loop counter |
64 | .save pr, saved_pr |
65 | mov saved_pr = pr // save the predicates |
66 | .body |
67 | mov ret0 = str |
68 | add last = str, in2 // last byte |
69 | ;; |
70 | cmp.ltu p6, p0 = last, str |
71 | ;; |
72 | (p6) mov last = -1 |
73 | and tmp = 7, str // tmp = str % 8 |
74 | cmp.ne p7, p0 = r0, r0 // clear p7 |
75 | extr.u chr = in1, 0, 8 // chr = (unsigned char) in1 |
76 | mov len = in2 |
77 | cmp.gtu p6, p0 = 16, in2 // use a simple loop for short |
78 | (p6) br.cond.spnt .srchfew ;; // searches |
79 | sub loopcnt = 8, tmp // loopcnt = 8 - tmp |
80 | cmp.eq p6, p0 = tmp, r0 |
81 | (p6) br.cond.sptk .str_aligned;; |
82 | sub len = len, loopcnt |
83 | adds loopcnt = -1, loopcnt;; |
84 | mov ar.lc = loopcnt |
85 | .l1: |
86 | ld1 val = [ret0], 1 |
87 | ;; |
88 | cmp.eq p6, p0 = val, chr |
89 | (p6) br.cond.spnt .foundit |
90 | br.cloop.sptk .l1 ;; |
91 | .str_aligned: |
92 | cmp.ne p6, p0 = r0, r0 // clear p6 |
93 | shr.u loopcnt = len, 3 // loopcnt = len / 8 |
94 | and len = 7, len ;; // remaining len = len & 7 |
95 | adds loopcnt = -1, loopcnt |
96 | mov ar.ec = MEMLAT + 3 |
97 | mux1 chrx8 = chr, @brcst ;; // get a word full of chr |
98 | mov ar.lc = loopcnt |
99 | mov pr.rot = 1 << 16 ;; |
100 | .l2: |
101 | (p[0]) mov addr[0] = ret0 |
102 | (p[0]) ld8.s value[0] = [ret0], 8 // speculative load |
103 | (p[MEMLAT]) chk.s value[MEMLAT], .recovery // check and recovery |
104 | (p[MEMLAT]) xor aux[0] = value[MEMLAT], chrx8 |
105 | (p[MEMLAT+1]) czx1.r poschr[0] = aux[1] |
106 | (p[MEMLAT+2]) cmp.ne p7, p0 = 8, poschr[1] |
107 | (p7) br.cond.dpnt .foundit |
108 | br.ctop.dptk .l2 |
109 | .srchfew: |
110 | adds loopcnt = -1, len |
111 | cmp.eq p6, p0 = len, r0 |
112 | (p6) br.cond.spnt .notfound ;; |
113 | mov ar.lc = loopcnt |
114 | .l3: |
115 | ld1 val = [ret0], 1 |
116 | ;; |
117 | cmp.eq p6, p0 = val, chr |
118 | (p6) br.cond.dpnt .foundit |
119 | br.cloop.sptk .l3 ;; |
120 | .notfound: |
121 | cmp.ne p6, p0 = r0, r0 // clear p6 (p7 was already 0 when we got here) |
122 | mov ret0 = r0 ;; // return NULL |
123 | .foundit: |
124 | .pred.rel "mutex" p6, p7 |
125 | (p6) adds ret0 = -1, ret0 // if we got here from l1 or l3 |
126 | (p7) add ret0 = addr[MEMLAT+2], poschr[1] // if we got here from l2 |
127 | mov pr = saved_pr, -1 |
128 | mov ar.lc = saved_lc |
129 | br.ret.sptk.many b0 |
130 | |
131 | .recovery: |
132 | #if MEMLAT != 6 |
133 | # error "MEMLAT must be 6!" |
134 | #endif |
135 | (p[MEMLAT-6]) add ret0 = -8, ret0;; |
136 | (p[MEMLAT-5]) add ret0 = -8, ret0;; |
137 | (p[MEMLAT-4]) add ret0 = -8, ret0;; |
138 | (p[MEMLAT-3]) add ret0 = -8, ret0;; |
139 | (p[MEMLAT-2]) add ret0 = -8, ret0;; |
140 | (p[MEMLAT-1]) add ret0 = -8, ret0;; |
141 | (p[MEMLAT]) add ret0 = -8, ret0;; |
142 | (p[MEMLAT+1]) add ret0 = -8, ret0;; |
143 | (p[MEMLAT+2]) add ret0 = -8, ret0;; |
144 | .l4: |
145 | mov addr[MEMLAT+2] = ret0 |
146 | ld8 tmp = [ret0];; // load the first unchecked 8byte |
147 | xor aux[1] = tmp, chrx8;; |
148 | czx1.r poschr[1] = aux[1];; |
149 | cmp.ne p7, p0 = 8, poschr[1];; |
150 | (p7) add ret0 = addr[MEMLAT+2], poschr[1];; |
151 | (p7) cmp.geu p6, p7 = ret0, last // don't go over the last byte |
152 | (p6) br.cond.spnt .notfound;; |
153 | (p7) br.cond.spnt .foundit;; |
154 | adds ret0 = 8, ret0 // load the next unchecked 8byte |
155 | br.sptk .l4;; |
156 | |
157 | END(__memchr) |
158 | |
159 | weak_alias (__memchr, memchr) |
160 | libc_hidden_builtin_def (memchr) |
161 | |