sysdeps/aarch64/memrchr.S

   1 /* memrchr - find the last occurrence of a byte in a memory block
   2
   3    Copyright (C) 2015-2023 Free Software Foundation, Inc.
   4
   5    This file is part of the GNU C Library.
   6
   7    The GNU C Library is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU Lesser General Public
   9    License as published by the Free Software Foundation; either
  10    version 2.1 of the License, or (at your option) any later version.
  11
  12    The GNU C Library is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    Lesser General Public License for more details.
  16
  17    You should have received a copy of the GNU Lesser General Public
  18    License along with the GNU C Library.  If not, see
  19    <https://www.gnu.org/licenses/>.  */
  20
  21 #include <sysdep.h>
  22
  23 /* Assumptions:
  24  *
  25  * ARMv8-a, AArch64, Advanced SIMD.
  26  * MTE compatible.
  27  */
  28
  29 #define srcin           x0
  30 #define chrin           w1
  31 #define cntin           x2
  32 #define result          x0
  33
  34 #define src             x3
  35 #define cntrem          x4
  36 #define synd            x5
  37 #define shift           x6
  38 #define tmp             x7
  39 #define end             x8
  40 #define endm1           x9
  41
  42 #define vrepchr         v0
  43 #define qdata           q1
  44 #define vdata           v1
  45 #define vhas_chr        v2
  46 #define vend            v3
  47 #define dend            d3
  48
  49 /*
  50    Core algorithm:
  51    For each 16-byte chunk we calculate a 64-bit nibble mask value with four bits
  52    per byte. We take 4 bits of every comparison byte with shift right and narrow
  53    by 4 instruction. Since the bits in the nibble mask reflect the order in
  54    which things occur in the original string, counting leading zeros identifies
  55    exactly which byte matched.  */
  56
  57 ENTRY (__memrchr)
  58         PTR_ARG (0)
  59         SIZE_ARG (2)
  60         add     end, srcin, cntin
  61         sub     endm1, end, 1
  62         bic     src, endm1, 15
  63         cbz     cntin, L(nomatch)
  64         ld1     {vdata.16b}, [src]
  65         dup     vrepchr.16b, chrin
  66         cmeq    vhas_chr.16b, vdata.16b, vrepchr.16b
  67         neg     shift, end, lsl 2
  68         shrn    vend.8b, vhas_chr.8h, 4         /* 128->64 */
  69         fmov    synd, dend
  70         lsl     synd, synd, shift
  71         cbz     synd, L(start_loop)
  72
  73         clz     synd, synd
  74         sub     result, endm1, synd, lsr 2
  75         cmp     cntin, synd, lsr 2
  76         csel    result, result, xzr, hi
  77         ret
  78
  79         nop
  80 L(start_loop):
  81         subs    cntrem, src, srcin
  82         b.ls    L(nomatch)
  83
  84         /* Make sure that it won't overread by a 16-byte chunk */
  85         sub     cntrem, cntrem, 1
  86         tbz     cntrem, 4, L(loop32_2)
  87         add     src, src, 16
  88
  89         .p2align 5
  90 L(loop32):
  91         ldr     qdata, [src, -32]!
  92         cmeq    vhas_chr.16b, vdata.16b, vrepchr.16b
  93         umaxp   vend.16b, vhas_chr.16b, vhas_chr.16b            /* 128->64 */
  94         fmov    synd, dend
  95         cbnz    synd, L(end)
  96
  97 L(loop32_2):
  98         ldr     qdata, [src, -16]
  99         subs    cntrem, cntrem, 32
 100         cmeq    vhas_chr.16b, vdata.16b, vrepchr.16b
 101         b.lo    L(end_2)
 102         umaxp   vend.16b, vhas_chr.16b, vhas_chr.16b            /* 128->64 */
 103         fmov    synd, dend
 104         cbz     synd, L(loop32)
 105 L(end_2):
 106         sub     src, src, 16
 107 L(end):
 108         shrn    vend.8b, vhas_chr.8h, 4         /* 128->64 */
 109         fmov    synd, dend
 110
 111         add     tmp, src, 15
 112 #ifdef __AARCH64EB__
 113         rbit    synd, synd
 114 #endif
 115         clz     synd, synd
 116         sub     tmp, tmp, synd, lsr 2
 117         cmp     tmp, srcin
 118         csel    result, tmp, xzr, hs
 119         ret
 120
 121 L(nomatch):
 122         mov     result, 0
 123         ret
 124
 125 END (__memrchr)
 126 libc_hidden_def (__memrchr)
 127 weak_alias (__memrchr, memrchr)
 128 libc_hidden_builtin_def (memrchr)