| blob | e267044761c6f2c1b4cadcba729e8d0dbe79f766 |
1 /*
2 * Copyright (C) 2013 ARM Ltd.
3 * Copyright (C) 2013 Linaro.
4 *
5 * This code is based on glibc cortex strings work originally authored by Linaro
6 * and re-licensed under GPLv2 for the Linux kernel. The original code can
7 * be found @
8 *
9 * http://bazaar.launchpad.net/~linaro-toolchain-dev/cortex-strings/trunk/
10 * files/head:/src/aarch64/
11 *
12 * This program is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU General Public License version 2 as
14 * published by the Free Software Foundation.
15 *
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License
22 * along with this program. If not, see <http://www.gnu.org/licenses/>.
23 */
25 #include <linux/linkage.h>
26 #include <asm/assembler.h>
28 /*
29 * compare two strings
30 *
31 * Parameters:
32 * x0 - const string 1 pointer
33 * x1 - const string 2 pointer
34 * x2 - the maximal length to be compared
35 * Returns:
36 * x0 - an integer less than, equal to, or greater than zero if s1 is found,
37 * respectively, to be less than, to match, or be greater than s2.
38 */
40 #define REP8_01 0x0101010101010101
41 #define REP8_7f 0x7f7f7f7f7f7f7f7f
42 #define REP8_80 0x8080808080808080
44 /* Parameters and result. */
45 src1 .req x0
46 src2 .req x1
47 limit .req x2
48 result .req x0
50 /* Internal variables. */
51 data1 .req x3
52 data1w .req w3
53 data2 .req x4
54 data2w .req w4
55 has_nul .req x5
56 diff .req x6
57 syndrome .req x7
58 tmp1 .req x8
59 tmp2 .req x9
60 tmp3 .req x10
61 zeroones .req x11
62 pos .req x12
63 limit_wd .req x13
64 mask .req x14
65 endloop .req x15
67 ENTRY(strncmp)
68 cbz limit, .Lret0
69 eor tmp1, src1, src2
70 mov zeroones, #REP8_01
71 tst tmp1, #7
72 b.ne .Lmisaligned8
73 ands tmp1, src1, #7
74 b.ne .Lmutual_align
75 /* Calculate the number of full and partial words -1. */
76 /*
77 * when limit is mulitply of 8, if not sub 1,
78 * the judgement of last dword will wrong.
79 */
80 sub limit_wd, limit, #1 /* limit != 0, so no underflow. */
81 lsr limit_wd, limit_wd, #3 /* Convert to Dwords. */
83 /*
84 * NUL detection works on the principle that (X - 1) & (~X) & 0x80
85 * (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
86 * can be done in parallel across the entire word.
87 */
88 .Lloop_aligned:
89 ldr data1, [src1], #8
90 ldr data2, [src2], #8
91 .Lstart_realigned:
92 subs limit_wd, limit_wd, #1
93 sub tmp1, data1, zeroones
94 orr tmp2, data1, #REP8_7f
95 eor diff, data1, data2 /* Non-zero if differences found. */
96 csinv endloop, diff, xzr, pl /* Last Dword or differences.*/
97 bics has_nul, tmp1, tmp2 /* Non-zero if NUL terminator. */
98 ccmp endloop, #0, #0, eq
99 b.eq .Lloop_aligned
101 /*Not reached the limit, must have found the end or a diff. */
102 tbz limit_wd, #63, .Lnot_limit
104 /* Limit % 8 == 0 => all bytes significant. */
105 ands limit, limit, #7
106 b.eq .Lnot_limit
108 lsl limit, limit, #3 /* Bits -> bytes. */
109 mov mask, #~0
110 CPU_BE( lsr mask, mask, limit )
111 CPU_LE( lsl mask, mask, limit )
112 bic data1, data1, mask
113 bic data2, data2, mask
115 /* Make sure that the NUL byte is marked in the syndrome. */
116 orr has_nul, has_nul, mask
118 .Lnot_limit:
119 orr syndrome, diff, has_nul
120 b .Lcal_cmpresult
122 .Lmutual_align:
123 /*
124 * Sources are mutually aligned, but are not currently at an
125 * alignment boundary. Round down the addresses and then mask off
126 * the bytes that precede the start point.
127 * We also need to adjust the limit calculations, but without
128 * overflowing if the limit is near ULONG_MAX.
129 */
130 bic src1, src1, #7
131 bic src2, src2, #7
132 ldr data1, [src1], #8
133 neg tmp3, tmp1, lsl #3 /* 64 - bits(bytes beyond align). */
134 ldr data2, [src2], #8
135 mov tmp2, #~0
136 sub limit_wd, limit, #1 /* limit != 0, so no underflow. */
137 /* Big-endian. Early bytes are at MSB. */
138 CPU_BE( lsl tmp2, tmp2, tmp3 ) /* Shift (tmp1 & 63). */
139 /* Little-endian. Early bytes are at LSB. */
140 CPU_LE( lsr tmp2, tmp2, tmp3 ) /* Shift (tmp1 & 63). */
142 and tmp3, limit_wd, #7
143 lsr limit_wd, limit_wd, #3
144 /* Adjust the limit. Only low 3 bits used, so overflow irrelevant.*/
145 add limit, limit, tmp1
146 add tmp3, tmp3, tmp1
147 orr data1, data1, tmp2
148 orr data2, data2, tmp2
149 add limit_wd, limit_wd, tmp3, lsr #3
150 b .Lstart_realigned
152 /*when src1 offset is not equal to src2 offset...*/
153 .Lmisaligned8:
154 cmp limit, #8
155 b.lo .Ltiny8proc /*limit < 8... */
156 /*
157 * Get the align offset length to compare per byte first.
158 * After this process, one string's address will be aligned.*/
159 and tmp1, src1, #7
160 neg tmp1, tmp1
161 add tmp1, tmp1, #8
162 and tmp2, src2, #7
163 neg tmp2, tmp2
164 add tmp2, tmp2, #8
165 subs tmp3, tmp1, tmp2
166 csel pos, tmp1, tmp2, hi /*Choose the maximum. */
167 /*
168 * Here, limit is not less than 8, so directly run .Ltinycmp
169 * without checking the limit.*/
170 sub limit, limit, pos
171 .Ltinycmp:
172 ldrb data1w, [src1], #1
173 ldrb data2w, [src2], #1
174 subs pos, pos, #1
175 ccmp data1w, #1, #0, ne /* NZCV = 0b0000. */
176 ccmp data1w, data2w, #0, cs /* NZCV = 0b0000. */
177 b.eq .Ltinycmp
178 cbnz pos, 1f /*find the null or unequal...*/
179 cmp data1w, #1
180 ccmp data1w, data2w, #0, cs
181 b.eq .Lstart_align /*the last bytes are equal....*/
182 1:
183 sub result, data1, data2
184 ret
186 .Lstart_align:
187 lsr limit_wd, limit, #3
188 cbz limit_wd, .Lremain8
189 /*process more leading bytes to make str1 aligned...*/
190 ands xzr, src1, #7
191 b.eq .Lrecal_offset
192 add src1, src1, tmp3 /*tmp3 is positive in this branch.*/
193 add src2, src2, tmp3
194 ldr data1, [src1], #8
195 ldr data2, [src2], #8
197 sub limit, limit, tmp3
198 lsr limit_wd, limit, #3
199 subs limit_wd, limit_wd, #1
201 sub tmp1, data1, zeroones
202 orr tmp2, data1, #REP8_7f
203 eor diff, data1, data2 /* Non-zero if differences found. */
204 csinv endloop, diff, xzr, ne/*if limit_wd is 0,will finish the cmp*/
205 bics has_nul, tmp1, tmp2
206 ccmp endloop, #0, #0, eq /*has_null is ZERO: no null byte*/
207 b.ne .Lunequal_proc
208 /*How far is the current str2 from the alignment boundary...*/
209 and tmp3, tmp3, #7
210 .Lrecal_offset:
211 neg pos, tmp3
212 .Lloopcmp_proc:
213 /*
214 * Divide the eight bytes into two parts. First,backwards the src2
215 * to an alignment boundary,load eight bytes from the SRC2 alignment
216 * boundary,then compare with the relative bytes from SRC1.
217 * If all 8 bytes are equal,then start the second part's comparison.
218 * Otherwise finish the comparison.
219 * This special handle can garantee all the accesses are in the
220 * thread/task space in avoid to overrange access.
221 */
222 ldr data1, [src1,pos]
223 ldr data2, [src2,pos]
224 sub tmp1, data1, zeroones
225 orr tmp2, data1, #REP8_7f
226 bics has_nul, tmp1, tmp2 /* Non-zero if NUL terminator. */
227 eor diff, data1, data2 /* Non-zero if differences found. */
228 csinv endloop, diff, xzr, eq
229 cbnz endloop, .Lunequal_proc
231 /*The second part process*/
232 ldr data1, [src1], #8
233 ldr data2, [src2], #8
234 subs limit_wd, limit_wd, #1
235 sub tmp1, data1, zeroones
236 orr tmp2, data1, #REP8_7f
237 eor diff, data1, data2 /* Non-zero if differences found. */
238 csinv endloop, diff, xzr, ne/*if limit_wd is 0,will finish the cmp*/
239 bics has_nul, tmp1, tmp2
240 ccmp endloop, #0, #0, eq /*has_null is ZERO: no null byte*/
241 b.eq .Lloopcmp_proc
243 .Lunequal_proc:
244 orr syndrome, diff, has_nul
245 cbz syndrome, .Lremain8
246 .Lcal_cmpresult:
247 /*
248 * reversed the byte-order as big-endian,then CLZ can find the most
249 * significant zero bits.
250 */
251 CPU_LE( rev syndrome, syndrome )
252 CPU_LE( rev data1, data1 )
253 CPU_LE( rev data2, data2 )
254 /*
255 * For big-endian we cannot use the trick with the syndrome value
256 * as carry-propagation can corrupt the upper bits if the trailing
257 * bytes in the string contain 0x01.
258 * However, if there is no NUL byte in the dword, we can generate
259 * the result directly. We can't just subtract the bytes as the
260 * MSB might be significant.
261 */
262 CPU_BE( cbnz has_nul, 1f )
263 CPU_BE( cmp data1, data2 )
264 CPU_BE( cset result, ne )
265 CPU_BE( cneg result, result, lo )
266 CPU_BE( ret )
267 CPU_BE( 1: )
268 /* Re-compute the NUL-byte detection, using a byte-reversed value.*/
269 CPU_BE( rev tmp3, data1 )
270 CPU_BE( sub tmp1, tmp3, zeroones )
271 CPU_BE( orr tmp2, tmp3, #REP8_7f )
272 CPU_BE( bic has_nul, tmp1, tmp2 )
273 CPU_BE( rev has_nul, has_nul )
274 CPU_BE( orr syndrome, diff, has_nul )
275 /*
276 * The MS-non-zero bit of the syndrome marks either the first bit
277 * that is different, or the top bit of the first zero byte.
278 * Shifting left now will bring the critical information into the
279 * top bits.
280 */
281 clz pos, syndrome
282 lsl data1, data1, pos
283 lsl data2, data2, pos
284 /*
285 * But we need to zero-extend (char is unsigned) the value and then
286 * perform a signed 32-bit subtraction.
287 */
288 lsr data1, data1, #56
289 sub result, data1, data2, lsr #56
290 ret
292 .Lremain8:
293 /* Limit % 8 == 0 => all bytes significant. */
294 ands limit, limit, #7
295 b.eq .Lret0
296 .Ltiny8proc:
297 ldrb data1w, [src1], #1
298 ldrb data2w, [src2], #1
299 subs limit, limit, #1
301 ccmp data1w, #1, #0, ne /* NZCV = 0b0000. */
302 ccmp data1w, data2w, #0, cs /* NZCV = 0b0000. */
303 b.eq .Ltiny8proc
304 sub result, data1, data2
305 ret
307 .Lret0:
308 mov result, #0
309 ret
310 ENDPIPROC(strncmp)