| blob | 48e6ce1f2735ba610177e3401cc736b1cef38a5a |
1 /*
2 Copyright (c) 2024, Synopsys, Inc. All rights reserved.
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions are met:
7 1) Redistributions of source code must retain the above copyright notice,
8 this list of conditions and the following disclaimer.
10 2) Redistributions in binary form must reproduce the above copyright notice,
11 this list of conditions and the following disclaimer in the documentation
12 and/or other materials provided with the distribution.
14 3) Neither the name of the Synopsys, Inc., nor the names of its contributors
15 may be used to endorse or promote products derived from this software
16 without specific prior written permission.
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 POSSIBILITY OF SUCH DAMAGE.
29 */
31 #include <sys/asm.h>
34 ; r0 char* dest
35 ; r1 const char* src
37 ; dest and src MUST NOT intercept
39 ; Brief:
40 ; Perform the same operation as strlen for finding the end of r0 string
41 ; If r0 and r1 have
42 ; If 4 byte aligned
43 ; Do 4 byte search until there are no more 4 byte chunks
44 ; Then, do 1 byte search
45 ; Otherwise, 1 byte search until alignment
46 ; Then, do 4 byte search as previously specified
47 ;
48 ;; More in depth description at the end
49 ;
50 ; R0 char* dest (destination string)
51 ; R1 const char* src (source string)
52 ; ret (R0):
53 ; - char* (destiantion string)
54 ;
56 #if defined (__ARC64_ARCH32__)
58 ENTRY (strcat)
59 ; Find end of r0 string
60 ; ========================== STRLEN CODE START ==========================
62 ; Preserve r0 for size calculation when returning
63 mov r13, r0
64 xor r6, r6, r6
66 ; Setup byte detector (more information below) [1]
67 mov r8, NULL_32DT_1
68 asl r9, r8, 7
70 .L_4_4B_search:
72 #if defined (__ARC64_LL64__)
74 ldd.ab r2r3, [r13, +8]
75 ldd.ab r4r5, [r13, +8]
77 #else
79 ld.ab r2, [r13, +4]
80 ld.ab r3, [r13, +4]
81 ld.ab r4, [r13, +4]
82 ld.ab r5, [r13, +4]
84 #endif
86 ; NULL byte position is detected and encoded in r6 [0] [9]
87 sub r10, r2, r8
88 sub r11, r3, r8
89 sub r12, r4, r8
90 sub r7, r5, r8
92 bic r10, r10, r2
93 bic r11, r11, r3
94 bic r12, r12, r4
95 bic r7, r7, r5
97 tst r10, r9
98 bset.ne r6, r6, 4
100 tst r11, r9
101 bset.ne r6, r6, 3
103 tst r12, r9
104 bset.ne r6, r6, 2
106 tst r7, r9
107 bset.ne r6, r6, 1
109 breq.d r6, 0, @.L_4_4B_search
111 fls r5, r6 ; [2]
113 ; Point r13 to first NULL byte containing double word [3]
114 sub2 r13, r13, r5
116 ; Select appropriate register to analyze [4]
117 mov r2, r7
119 asr.f r6, r6, 3
120 mov.c r2, r12
122 asr.f r6, r6, 1
123 mov.c r2, r11
125 asr.f r6, r6, 1
126 mov.c r2, r10
128 ; Point r13 to first NULL byte in selected double word
129 and r2, r2, r9 ; [5]
131 ffs r2, r2 ; [6]
133 xbfu r2, r2, 0b0111000011 ; [7]
135 add r13, r13, r2 ; [8]
138 ; ========================== STRLEN CODE END >|< ==========================
140 xor r6, r6, r6
142 .L_4_4B_search_src:
144 #if defined (__ARC64_LL64__)
146 ldd.ab r2r3, [r1, +8]
147 ldd.ab r4r5, [r1, +8]
149 #else
151 ld.ab r2, [r1, +4]
152 ld.ab r3, [r1, +4]
153 ld.ab r4, [r1, +4]
154 ld.ab r5, [r1, +4]
156 #endif
158 ; NULL byte position is detected and encoded in r6 [0] [9]
159 sub r10, r2, r8
160 sub r11, r3, r8
161 sub r12, r4, r8
162 sub r7, r5, r8
164 bic r10, r10, r2
165 bic r11, r11, r3
166 bic r12, r12, r4
167 bic r7, r7, r5
169 tst r10, r9
170 bset.ne r6, r6, 4
172 tst r11, r9
173 bset.ne r6, r6, 3
175 tst r12, r9
176 bset.ne r6, r6, 2
178 tst r7, r9
179 bset.ne r6, r6, 1
181 brne r6, 0, @.L_found_in_32B
183 #if defined (__ARC64_LL64__)
185 std.ab r2r3, [r13, +8]
186 std.ab r4r5, [r13, +8]
188 #else
190 st.ab r2, [r13, +4]
191 st.ab r3, [r13, +4]
192 st.ab r4, [r13, +4]
193 st.ab r5, [r13, +4]
195 #endif
197 b @.L_4_4B_search_src
199 .L_found_in_32B:
201 fls r6, r6 ; [2]
203 ; Point r1 to first NULL byte containing double word [3]
204 sub2 r1, r1, r6
206 ;; Store the already loaded data
208 ; 4 -> 1 to 3 -> 0
209 ;subl r6, r6, 1
211 ; Invert so the biggest branch is at the end, and we dont need to increase
212 ; block size
213 ; 3 -> 0 to 0 -> 3
214 ;subl r6, 3, r6
216 ; Condense the two subs here
217 rsub r6, r6, 4
219 asl r6, r6, 2
221 ; Store double words
222 bi [r6]
224 b.d @.L_store_lastL32bits
225 mov r11, r2
226 nop
227 nop
229 st.ab r2, [r13, +4]
230 b.d @.L_store_lastL32bits
231 mov r11, r3
232 nop
234 st.ab r2, [r13, +4]
235 st.ab r3, [r13, +4]
236 b.d @.L_store_lastL32bits
237 mov r11, r4
239 st.ab r2, [r13, +4]
240 st.ab r3, [r13, +4]
241 st.ab r4, [r13, +4]
242 mov r11, r5
244 ; r11 now contains the data to write
245 .L_store_lastL32bits:
246 sub r10, r11, r8
247 bic r10, r10, r11
248 and r10, r10, r9 ; [5]
250 ffs r2, r10 ; [6]
251 add r2, r2, 1
253 xbfu r2, r2, 0b0111000011 ; [7]
255 mov r3, -1; Bitmask setup
257 ; If the NULL byte is in byte 3 (starting from the right)
258 ; we want to store 8-3 bytes
259 rsub r2, r2, 8
260 asl r2, r2, 3
262 ; According to the target byte, setup masks
263 lsr r3, r3, r2
264 not r4, r3
266 ; Obtain relevant data from destination
267 ld r10, [r13]
269 ; Get which data from dest is not to be overwritten and OR it
270 ; with the relevant data to write
271 and r3, r3, r11
272 and r4, r4, r10
274 or r3, r3, r4
276 j_s.d [blink]
277 st.ab r3, [r13, +4]
281 ENDFUNC (strcat)
283 #else
285 ENTRY (strcat)
286 ; Find end of r0 string
287 ; ========================== STRLEN CODE START ==========================
289 ; Preserve r0 for size calculation when returning
290 movl r13, r0
291 xorl r6, r6, r6
293 ; Setup byte detector (more information below) [1]
294 vpack2wl r8, NULL_32DT_1, NULL_32DT_1
295 asll r9, r8, 7
297 .L_4_8B_search:
299 ; Using 128-bit memory operations
300 #if defined (__ARC64_M128__)
302 lddl.ab r2r3, [r13, +16]
303 lddl.ab r4r5, [r13, +16]
305 ; The 64-bit crunching implementation.
306 #elif defined (__ARC64_ARCH64__)
308 ldl.ab r2, [r13, +8]
309 ldl.ab r3, [r13, +8]
310 ldl.ab r4, [r13, +8]
311 ldl.ab r5, [r13, +8]
313 #else
314 # error Unknown configuration
315 #endif
317 ; NULL byte position is detected and encoded in r6 [0] [9]
318 subl r10, r2, r8
319 subl r11, r3, r8
320 subl r12, r4, r8
321 subl r7, r5, r8
323 bicl r10, r10, r2
324 bicl r11, r11, r3
325 bicl r12, r12, r4
326 bicl r7, r7, r5
328 tstl r10, r9
329 bset.ne r6, r6, 4
331 tstl r11, r9
332 bset.ne r6, r6, 3
334 tstl r12, r9
335 bset.ne r6, r6, 2
337 tstl r7, r9
338 bset.ne r6, r6, 1
340 breq.d r6, 0, @.L_4_8B_search
342 fls r5, r6 ; [2]
344 ; Point r13 to first NULL byte containing double word [3]
345 sub3l r13, r13, r5
347 ; Select appropriate register to analyze [4]
348 MOVP r2, r7
350 asr.f r6, r6, 3
351 MOVP.c r2, r12
353 asr.f r6, r6, 1
354 MOVP.c r2, r11
356 asr.f r6, r6, 1
357 MOVP.c r2, r10
359 ; Point r13 to first NULL byte in selected double word
360 andl r2, r2, r9 ; [5]
362 ffsl r2, r2 ; [6]
364 xbful r2, r2, 0b0111000011 ; [7]
366 addl r13, r13, r2 ; [8]
369 ; ========================== STRLEN CODE END >|< ==========================
371 xorl r6, r6, r6
373 .L_4_8B_search_src:
374 #if defined (__ARC64_M128__)
376 lddl.ab r2r3, [r1, +16]
377 lddl.ab r4r5, [r1, +16]
379 #elif defined (__ARC64_ARCH64__)
381 ldl.ab r2, [r1, +8]
382 ldl.ab r3, [r1, +8]
383 ldl.ab r4, [r1, +8]
384 ldl.ab r5, [r1, +8]
386 #else
387 # error Unknown configuration
388 #endif
390 ; NULL byte position is detected and encoded in r6 [0] [9]
391 subl r10, r2, r8
392 subl r11, r3, r8
393 subl r12, r4, r8
394 subl r7, r5, r8
396 bicl r10, r10, r2
397 bicl r11, r11, r3
398 bicl r12, r12, r4
399 bicl r7, r7, r5
401 tstl r10, r9
402 bset.ne r6, r6, 4
404 tstl r11, r9
405 bset.ne r6, r6, 3
407 tstl r12, r9
408 bset.ne r6, r6, 2
410 tstl r7, r9
411 bset.ne r6, r6, 1
413 brne r6, 0, @.L_found_in_32B
415 #if defined (__ARC64_M128__)
417 stdl.ab r2r3, [r13, +16]
418 stdl.ab r4r5, [r13, +16]
420 #elif defined (__ARC64_ARCH64__)
422 stl.ab r2, [r13, +8]
423 stl.ab r3, [r13, +8]
424 stl.ab r4, [r13, +8]
425 stl.ab r5, [r13, +8]
427 #else
428 # error Unknown configuration
429 #endif
431 b @.L_4_8B_search_src
433 .L_found_in_32B:
435 fls r6, r6 ; [2]
437 ; Point r1 to first NULL byte containing double word [3]
438 sub3l r1, r1, r6
440 ;; Store the already loaded data
442 ; 4 -> 1 to 3 -> 0
443 ;subl r6, r6, 1
445 ; Invert so the biggest branch is at the end, and we dont need to increase
446 ; block size
447 ; 3 -> 0 to 0 -> 3
448 ;subl r6, 3, r6
450 ; Condense the two subs here
451 rsubl r6, r6, 4
453 asll r6, r6, 2
455 ; Store double words
456 bi [r6]
458 b.d @.L_store_lastL64bits
459 MOVP r11, r2
460 nop
461 nop
463 stl.ab r2, [r13, +8]
464 b.d @.L_store_lastL64bits
465 MOVP r11, r3
466 nop
468 stl.ab r2, [r13, +8]
469 stl.ab r3, [r13, +8]
470 b.d @.L_store_lastL64bits
471 MOVP r11, r4
473 stl.ab r2, [r13, +8]
474 stl.ab r3, [r13, +8]
475 stl.ab r4, [r13, +8]
476 MOVP r11, r5
478 ; r11 now contains the data to write
479 .L_store_lastL64bits:
480 subl r10, r11, r8
481 bicl r10, r10, r11
483 andl r10, r10, r9 ; [5]
485 ffsl r2, r10 ; [6]
486 addl r2, r2, 1
488 xbful r2, r2, 0b0111000011 ; [7]
490 movl r3, -1; Bitmask setup
492 ; If the NULL byte is in byte 3 (starting from the right)
493 ; we want to store 8-3 bytes
494 rsubl r2, r2, 8
495 asl r2, r2, 3
497 ; According to the target byte, setup masks
498 lsrl r3, r3, r2
499 notl r4, r3
501 ; Obtain relevant data from destination
502 ldl r10, [r13]
504 ; Get which data from dest is not to be overwritten and OR it
505 ; with the relevant data to write
506 andl r3, r3, r11
507 andl r4, r4, r10
509 orl r3, r3, r4
511 j_s.d [blink]
512 stl.ab r3, [r13, +8]
515 ENDFUNC (strcat)
517 #endif
519 ;; This code uses a common technique for NULL byte detection inside a word.
520 ;; Details on this technique can be found in:
521 ;; (https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord)
522 ;
523 ; In sum, this technique allows for detecting a NULL byte inside any given
524 ; amount of bits by performing the following operation
525 ; DETECTNULL(X) (((X) - 0x01010101) & ~(X) & 0x80808080) [0]
526 ;
527 ; The code above implements this by setting r8 to a 0x01010101... sequence and
528 ; r9 to a 0x80808080... sequence of appropriate length
529 ; As LIMM are 32 bit only, we need to perform MOVHL and ORL [1] operations to
530 ; have the appropriate 64 bit values in place
531 ;
532 ;; Search is done 32 bytes at a time, either with 64 bit loads or 128 bit loads
533 ;; If a NULL byte is detected, the position of the double word is encoded
534 ;; in r6, which is then used to adjust r13 to the exact byte
535 ;
536 ; r6 is set via bset, which means we can simply use a fls to obtain the first
537 ; match (or ffs depending on the values in bset) [2].
538 ; The reason for starting at 1 and not 0 is so r6 encodes how many double
539 ; words to go back, and it wouldnt make sense to go back 0 (the NULL would be
540 ; in the next loop iteration).
541 ;
542 ; The first step to take is point r13 to the appropriate double word.
543 ; As the chosen encoded information is how many double words to go back,
544 ; we can simply multiply r6 by 8 and reduce r13 by that amount [3]
545 ;
546 ; Then, we need to place the loaded double word containing the first NULL byte
547 ; into a "common" register we can operate on later [4].
548 ;
549 ; To do this without any jumps, we can shift r6 and perform a conditional mov
550 ; based on the carry flag value.
551 ; The order is very important because the NULL byte can appear in several
552 ; double words, so we want to analyze from last to first.
553 ;
554 ; We can ignore the first asr (which would be asr.f 2, as we started r6 on 1)
555 ; because if r7 isnt the NULL byte, r2 will always be overwritten so we can
556 ; just decide to start at r7, and overwrite it if needed.
557 ;
558 ; Now comes the tricky part. In order to obtain the first NULL byte, we need to
559 ; understand the NULL byte detection operation. It is explained in depth in the
560 ; link above but in short, it works by first setting the highest bit of each
561 ; byte to 1, if the corresponding byte is either 0 or less than 0x80
562 ; Then, separately, it makes the highest bit of each byte 1, if the byte is
563 ; less than 0x80. The last step is to and these two values (this operation is
564 ; simplified with the subl, bicl and tst instructions).
565 ;
566 ; This means that the evaluated equation result value [5] has zeros for all non
567 ; zero bytes, except for the NULL bytes. Therefore, we can simply find the
568 ; first non zero bit (counting from bit 0) which will be inside the position of
569 ; the first NULL byte.
570 ;
571 ; One thing to note, is that ffs oddly returns 31 if no bit is found, setting
572 ; the zero flag. As r9 is never all 0s at this stage (would mean there is no
573 ; NULL byte and we wouldnt be here) we dont need to worry about that. [6]
574 ;
575 ; We can then convert the bit position into the last byte position by looking
576 ; into bits 3 to 5, and shifting 3 bits to the right. This can be combined into
577 ; a single xbful operation. The bottom 000011 represent shift by 3 and the top
578 ; 0111 represents the mask (3 to 5 shifted by 3 is 0 to 2). We dont need to worry
579 ; about the case where ffs does not find a bit, because we know for sure there is
580 ; at least one NULL byte, and therefore one of the highest bits is set to 1 [7]
581 ;
582 ; Finally, we can add the NULL byte position inside the loaded double word to
583 ; r13 and subtract r0 from r13 to obtain the string size [8]
584 ;
585 ; Some operations are re-ordered such that register dependency is reduced,
586 ; allowing the CPU to run more instructions in parallel [9]
587 ;
588 ;
589 ; Some data was already read, and needs to be stored following the same read
590 ; order. To do this, we need to make the
591 ;
592 ;