1 /* SPDX-License-Identifier: GPL-2.0 */
2 /*
3 * arch/alpha/lib/ev6-memchr.S
4 *
5 * 21264 version contributed by Rick Gorton <ri
6 *
7 * Finds characters in a memory area. Optimiz
8 *
9 * - memory accessed as aligned quadwords o
10 * - uses cmpbge to compare 8 bytes in para
11 * - does binary search to find 0 byte in l
12 * quadword (HAKMEM needed 12 instruction
13 * do this instead of the 9 instructions
14 * binary search needs).
15 *
16 * For correctness consider that:
17 *
18 * - only minimum number of quadwords may b
19 * - the third argument is an unsigned long
20 *
21 * Much of the information about 21264 schedul
22 * Compiler Writer's Guide for the Alpha
23 * abbreviated as 'CWG' in other comments
24 * ftp.digital.com/pub/Digital/info/semic
25 * Scheduling notation:
26 * E - either cluster
27 * U - upper subcluster; U0 - subcl
28 * L - lower subcluster; L0 - subcl
29 * Try not to change the actual algorithm if p
30 */
31 #include <linux/export.h>
32 .set noreorder
33 .set noat
34
35 .align 4
36 .globl memchr
37 .ent memchr
38 memchr:
39 .frame $30,0,$26,0
40 .prologue 0
41
42 # Hack -- if someone passes in (size_t
43 # search til the end of the address sp
44 # below when we find the address of th
45 # that we will never have a 56-bit add
46 # the length is the easiest way to avo
47 zap $18, 0x80, $5 # U : Bound le
48 beq $18, $not_found # U :
49 ldq_u $1, 0($16) # L : load fir
50 and $17, 0xff, $17 # E : L L U U
51
52 insbl $17, 1, $2 # U : 00000000
53 cmpult $18, 9, $4 # E : small (<
54 or $2, $17, $17 # E : 00000000
55 lda $3, -1($31) # E : U L L U
56
57 sll $17, 16, $2 # U : 00000000
58 addq $16, $5, $5 # E : Max sear
59 or $2, $17, $17 # E : 00000000
60 sll $17, 32, $2 # U : U L L U
61
62 or $2, $17, $17 # E : chchchch
63 extql $1, $16, $7 # U : $7 is up
64 beq $4, $first_quad # U :
65 ldq_u $6, -1($5) # L : L U U L
66
67 extqh $6, $16, $6 # U : 2 cycle
68 mov $16, $0 # E :
69 nop # E :
70 or $7, $6, $1 # E : L U L U
71
72 # Deal with the case where at most 8 b
73 # in $1. E.g.:
74 # $18 = 6
75 # $1 = ????c6c5c4c3c2c1
76 $last_quad:
77 negq $18, $6 # E :
78 xor $17, $1, $1 # E :
79 srl $3, $6, $6 # U : $6 = mas
80 cmpbge $31, $1, $2 # E : L U L U
81
82 nop
83 nop
84 and $2, $6, $2 # E :
85 beq $2, $not_found # U : U L U L
86
87 $found_it:
88 #ifdef CONFIG_ALPHA_EV67
89 /*
90 * Since we are guaranteed to have set
91 * have to worry about coming back wit
92 */
93 cttz $2, $3 # U0 :
94 addq $0, $3, $0 # E : All done
95 nop # E :
96 ret # L0 : L U L U
97 #else
98 /*
99 * Slow and clunky. It can probably b
100 * An exercise left for others.
101 */
102 negq $2, $3 # E :
103 and $2, $3, $2 # E :
104 and $2, 0x0f, $1 # E :
105 addq $0, 4, $3 # E :
106
107 cmoveq $1, $3, $0 # E : Latency
108 nop # E : keep wit
109 and $2, 0x33, $1 # E :
110 addq $0, 2, $3 # E : U L U L
111
112 cmoveq $1, $3, $0 # E : Latency
113 nop # E : keep wit
114 and $2, 0x55, $1 # E :
115 addq $0, 1, $3 # E : U L U L
116
117 cmoveq $1, $3, $0 # E : Latency
118 nop
119 nop
120 ret # L0 : L U L U
121 #endif
122
123 # Deal with the case where $18 > 8 byt
124 # searched. $16 may not be aligned.
125 .align 4
126 $first_quad:
127 andnot $16, 0x7, $0 # E :
128 insqh $3, $16, $2 # U : $2 = 000
129 xor $1, $17, $1 # E :
130 or $1, $2, $1 # E : U L U L
131
132 cmpbge $31, $1, $2 # E :
133 bne $2, $found_it # U :
134 # At least one byte left to process.
135 ldq $1, 8($0) # L :
136 subq $5, 1, $18 # E : U L U L
137
138 addq $0, 8, $0 # E :
139 # Make $18 point to last quad to be ac
140 # last quad may or may not be partial)
141 andnot $18, 0x7, $18 # E :
142 cmpult $0, $18, $2 # E :
143 beq $2, $final # U : U L U L
144
145 # At least two quads remain to be acce
146
147 subq $18, $0, $4 # E : $4 <- nr
148 and $4, 8, $4 # E : odd numb
149 bne $4, $odd_quad_count # U :
150 # At least three quads remain to be ac
151 mov $1, $4 # E : L U L U
152
153 .align 4
154 $unrolled_loop:
155 ldq $1, 8($0) # L : prefetch
156 xor $17, $4, $2 # E :
157 cmpbge $31, $2, $2 # E :
158 bne $2, $found_it # U : U L U L
159
160 addq $0, 8, $0 # E :
161 nop # E :
162 nop # E :
163 nop # E :
164
165 $odd_quad_count:
166 xor $17, $1, $2 # E :
167 ldq $4, 8($0) # L : prefetch
168 cmpbge $31, $2, $2 # E :
169 addq $0, 8, $6 # E :
170
171 bne $2, $found_it # U :
172 cmpult $6, $18, $6 # E :
173 addq $0, 8, $0 # E :
174 nop # E :
175
176 bne $6, $unrolled_loop # U :
177 mov $4, $1 # E : move pre
178 nop # E :
179 nop # E :
180
181 $final: subq $5, $0, $18 # E : $18 <- n
182 nop # E :
183 nop # E :
184 bne $18, $last_quad # U :
185
186 $not_found:
187 mov $31, $0 # E :
188 nop # E :
189 nop # E :
190 ret # L0 :
191
192 .end memchr
193 EXPORT_SYMBOL(memchr)
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.