newlib/libc/machine/arc64/strlen.S

   1 /*
   2    Copyright (c) 2024, Synopsys, Inc. All rights reserved.
   3
   4    Redistribution and use in source and binary forms, with or without
   5    modification, are permitted provided that the following conditions are met:
   6
   7    1) Redistributions of source code must retain the above copyright notice,
   8    this list of conditions and the following disclaimer.
   9
  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.
  13
  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.
  17
  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 */
  30
  31 #include <sys/asm.h>
  32
  33 ; Code Brief (more info at the bottom):
  34 ; Searches the provided string, 32 bytes at a time, using 128 bit loads
  35 ; Finds the NULL bytes inside the loaded data
  36 ; Analyzes the first NULL byte containing double word and calculates
  37 ; size appropriately
  38 ;
  39 ; R0 const char* ptr (string to measure)
  40 ; ret (R0):
  41 ;               - unsigned (string size)
  42 ;
  43
  44 #if defined (__ARC64_ARCH32__)
  45
  46 ENTRY (strlen)
  47
  48 ; Preserve r0 for size calculation when returning
  49         mov     r13, r0
  50         xor     r12, r12, r12
  51
  52 ; Setup byte detector (more information bellow) [1]
  53         mov     r8, NULL_32DT_1
  54 ; Set r9 as a copy of r8 for vectorized sub
  55         mov     r9, r8
  56
  57         asl     r1, r8, 7
  58
  59 .L_4_4B_search:
  60
  61 #if defined (__ARC64_LL64__)
  62
  63         ldd.ab  r2r3, [r13, +8]
  64         ldd.ab  r4r5, [r13, +8]
  65
  66 #else
  67
  68         ld.ab   r2, [r13, +4]
  69         ld.ab   r3, [r13, +4]
  70         ld.ab   r4, [r13, +4]
  71         ld.ab   r5, [r13, +4]
  72
  73 #endif
  74
  75 ; NULL byte position is detected and encoded in r12 [0] [9]
  76
  77         vsub2   r10, r2, r8
  78         vsub2   r6, r4, r8
  79
  80         bic     r10, r10, r2
  81         bic     r11, r11, r3
  82         bic     r6, r6, r4
  83         bic     r7, r7, r5
  84
  85         tst     r10, r1
  86         bset.ne r12, r12, 4
  87
  88         tst     r11, r1
  89         bset.ne r12, r12, 3
  90
  91         tst     r6, r1
  92         bset.ne r12, r12, 2
  93
  94         tst     r7, r1
  95         bset.ne r12, r12, 1
  96
  97         breq.d  r12, 0, @.L_4_4B_search
  98
  99         fls     r5, r12 ; [2]
 100
 101 ; Point r13 to first NULL byte containing double word [3]
 102         sub2    r13, r13, r5
 103
 104 ; Select appropriate register to analyze [4]
 105         mov     r2, r7
 106
 107         asr.f   r12, r12, 3
 108         mov.c   r2, r6
 109
 110         asr.f   r12, r12, 1
 111         mov.c   r2, r11
 112
 113         asr.f   r12, r12, 1
 114         mov.c   r2, r10
 115
 116 ; Point r13 to first NULL byte in selected double word
 117 .L_fix_r13:
 118         and     r1, r2, r1 ; [5]
 119
 120         ffs     r1, r1 ; [6]
 121
 122         xbfu    r1, r1, 0b0111000011 ; [7]
 123
 124         add r13, r13, r1 ; [8]
 125
 126         j_s.d   [blink]
 127         sub     r0, r13, r0
 128
 129
 130 ENDFUNC (strlen)
 131
 132 #else
 133
 134 ENTRY (strlen)
 135
 136 ; Preserve r0 for size calculation when returning
 137         movl    r13, r0
 138         xor     r12, r12, r12
 139
 140 ; Setup byte detector (more information bellow) [1]
 141         vpack2wl        r8, NULL_32DT_1, NULL_32DT_1
 142
 143         asll    r1, r8, 7
 144
 145 .L_4_8B_search:
 146
 147 ; Using 128-bit memory operations
 148 #if defined (__ARC64_M128__)
 149
 150         lddl.ab r2r3, [r13, +16]
 151         lddl.ab r4r5, [r13, +16]
 152
 153 ; The 64-bit crunching implementation.
 154 #elif defined (__ARC64_ARCH64__)
 155
 156         ldl.ab  r2, [r13, +8]
 157         ldl.ab  r3, [r13, +8]
 158         ldl.ab  r4, [r13, +8]
 159         ldl.ab  r5, [r13, +8]
 160
 161 #else
 162         # error Unknown configuration
 163 #endif
 164
 165 ; NULL byte position is detected and encoded in r6 [0] [9]
 166         subl    r10, r2, r8
 167         subl    r11, r3, r8
 168         subl    r6, r4, r8
 169         subl    r7, r5, r8
 170
 171         bicl    r10, r10, r2
 172         bicl    r11, r11, r3
 173         bicl    r6, r6, r4
 174         bicl    r7, r7, r5
 175
 176         tstl    r10, r1
 177         bset.ne r12, r12, 4
 178
 179         tstl    r11, r1
 180         bset.ne r12, r12, 3
 181
 182         tstl    r6, r1
 183         bset.ne r12, r12, 2
 184
 185         tstl    r7, r1
 186         bset.ne r12, r12, 1
 187
 188         breq.d  r12, 0, @.L_4_8B_search
 189
 190         flsl    r5, r12 ; [2]
 191
 192 ; Point r13 to first NULL byte containing double word [3]
 193         sub3l   r13, r13, r5
 194
 195 ; Select appropriate register to analyze [4]
 196         movl    r2, r7
 197
 198         asr.f   r12, r12, 3
 199         movl.c  r2, r6
 200
 201         asr.f   r12, r12, 1
 202         movl.c  r2, r11
 203
 204         asr.f   r12, r12, 1
 205         movl.c  r2, r10
 206
 207 ; Point r13 to first NULL byte in selected double word
 208 .L_fix_r13:
 209         andl    r1, r2, r1 ; [5]
 210
 211         ffsl    r1, r1 ; [6]
 212
 213         xbful   r1, r1, 0b0111000011 ; [7]
 214
 215         addl r13, r13, r1 ; [8]
 216
 217         j_s.d   [blink]
 218         subl    r0, r13, r0
 219
 220
 221 ENDFUNC (strlen)
 222
 223 #endif
 224
 225 ;; This code uses a common technique for NULL byte detection inside a word.
 226 ;; Details on this technique can be found in:
 227 ;; (https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord)
 228 ;
 229 ; In sum, this technique allows for detecting a NULL byte inside any given
 230 ; amount of bits by performing the following operation
 231 ;               DETECTNULL(X) (((X) - 0x01010101) & ~(X) & 0x80808080) [0]
 232 ;
 233 ; The code above implements this by setting r8 to a
 234 ; 0x01010101... sequence and r1 to a 0x80808080... sequence of
 235 ; appropriate length As LIMM are 32 bit only, we need to perform MOVHL
 236 ; and ORL [1] operations to have the appropriate 64 bit values in
 237 ; place
 238 ;
 239 ;; Search is done 32 bytes at a time, either with 64 bit loads or 128
 240 ;; bit loads If a NULL byte is detected, the position of the double
 241 ;; word is encoded in r12, which is then used to adjust r13
 242 ;
 243 ; r12 is set via bset, which means we can simply use a fls to obtain
 244 ; the first match (or ffs depending on the values in bset) [2].  The
 245 ; reason for starting at 1 and not 0 is so r12 encodes how many double
 246 ; words to go back, and it wouldnt make sense to go back 0 (the NULL
 247 ; would be in the next loop iteration).
 248 ;
 249 ; The first step to take is point r13 to the appropriate double word.
 250 ; As the chosen encoded information is how many double words to go
 251 ; back, we can simply multiply r12 by 8 and reduce r13 by that amount
 252 ; [3]
 253 ;
 254 ; Then, we need to place the loaded double word containing the first
 255 ; NULL byte into a "common" register we can operate on later [4].
 256 ;
 257 ; To do this without any jumps, we can shift r12 and perform a
 258 ; conditional mov based on the carry flag value.  The order is very
 259 ; important because the NULL byte can appear in several double words,
 260 ; so we want to analyze from last to first.
 261 ;
 262 ; We can ignore the first asr (which would be asr.f 2, as we started
 263 ; r12 on 1) because if r7 isnt the NULL byte, r2 will always be
 264 ; overwritten so we can just decide to start at r7, and overwrite it
 265 ; if needed.
 266 ;
 267 ; Now comes the tricky part. In order to obtain the first NULL byte,
 268 ; we need to understand the NULL byte detection operation. It is
 269 ; explained in depth in the link above but in short, it works by first
 270 ; setting the highest bit of each byte to 1, if the corresponding byte
 271 ; is either 0 or more than 0x80 Then, separately, it makes the highest
 272 ; bit of each byte 1, if the byte is less than 0x80. The last step is
 273 ; to AND these two values (this operation is simplified with the SUB,
 274 ; BIC and TST instructions).
 275 ;
 276 ; This means that the evaluated equation result value [5] has zeros
 277 ; for all non zero bytes, except for the NULL bytes. Therefore, we can
 278 ; simply find the first non zero bit (counting from bit 0) which will
 279 ; be inside the position of the first NULL byte.
 280 ;
 281 ; One thing to note, is that ffs oddly returns 31 if no bit is found,
 282 ; setting the zero flag. As r9 is never all 0s at this stage (would
 283 ; mean there is no NULL byte and we wouldnt be here) we dont need to
 284 ; worry about that. [6]
 285 ;
 286 ; We can then convert the bit position into the last byte position by
 287 ; looking into bits 3 to 5, and shifting 3 bits to the right. This can
 288 ; be combined into a single xbful operation. The bottom 000011
 289 ; represent shift by 3 and the top 0111 represents the mask (3 to 5
 290 ; shifted by 3 is 0 to 2). We dont need to worry about the case where
 291 ; ffs does not find a bit, because we know for sure there is at least
 292 ; one NULL byte, and therefore one of the highest bits is set to 1 [7]
 293 ;
 294 ; Finally, we can add the NULL byte position inside the loaded double
 295 ; word to r13 and subtract r0 from r13 to obtain the string size [8]
 296 ;
 297 ;
 298 ; Some operations are re-ordered such that register dependency is
 299 ; reduced, allowing the CPU to run more instructions in parallel [9]
 300 ;
 301 ;