sysdeps/aarch64/memchr.S

   1 /* memchr - find a character in a memory zone
   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 #ifndef MEMCHR
  30 # define MEMCHR __memchr
  31 #endif
  32
  33 #define srcin           x0
  34 #define chrin           w1
  35 #define cntin           x2
  36 #define result          x0
  37
  38 #define src             x3
  39 #define cntrem          x4
  40 #define synd            x5
  41 #define shift           x6
  42 #define tmp             x7
  43
  44 #define vrepchr         v0
  45 #define qdata           q1
  46 #define vdata           v1
  47 #define vhas_chr        v2
  48 #define vend            v3
  49 #define dend            d3
  50
  51 /*
  52    Core algorithm:
  53    For each 16-byte chunk we calculate a 64-bit nibble mask value with four bits
  54    per byte. We take 4 bits of every comparison byte with shift right and narrow
  55    by 4 instruction. Since the bits in the nibble mask reflect the order in
  56    which things occur in the original string, counting leading zeros identifies
  57    exactly which byte matched.  */
  58
  59 ENTRY (MEMCHR)
  60         PTR_ARG (0)
  61         SIZE_ARG (2)
  62         bic     src, srcin, 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         lsl     shift, srcin, 2
  68         shrn    vend.8b, vhas_chr.8h, 4         /* 128->64 */
  69         fmov    synd, dend
  70         lsr     synd, synd, shift
  71         cbz     synd, L(start_loop)
  72
  73         rbit    synd, synd
  74         clz     synd, synd
  75         cmp     cntin, synd, lsr 2
  76         add     result, srcin, synd, lsr 2
  77         csel    result, result, xzr, hi
  78         ret
  79
  80         .p2align 3
  81 L(start_loop):
  82         sub     tmp, src, srcin
  83         add     tmp, tmp, 17
  84         subs    cntrem, cntin, tmp
  85         b.lo    L(nomatch)
  86
  87         /* Make sure that it won't overread by a 16-byte chunk */
  88         tbz     cntrem, 4, L(loop32_2)
  89         sub     src, src, 16
  90         .p2align 4
  91 L(loop32):
  92         ldr     qdata, [src, 32]!
  93         cmeq    vhas_chr.16b, vdata.16b, vrepchr.16b
  94         umaxp   vend.16b, vhas_chr.16b, vhas_chr.16b            /* 128->64 */
  95         fmov    synd, dend
  96         cbnz    synd, L(end)
  97
  98 L(loop32_2):
  99         ldr     qdata, [src, 16]
 100         cmeq    vhas_chr.16b, vdata.16b, vrepchr.16b
 101         subs    cntrem, cntrem, 32
 102         b.lo    L(end_2)
 103         umaxp   vend.16b, vhas_chr.16b, vhas_chr.16b            /* 128->64 */
 104         fmov    synd, dend
 105         cbz     synd, L(loop32)
 106 L(end_2):
 107         add     src, src, 16
 108 L(end):
 109         shrn    vend.8b, vhas_chr.8h, 4         /* 128->64 */
 110         sub     cntrem, src, srcin
 111         fmov    synd, dend
 112         sub     cntrem, cntin, cntrem
 113 #ifndef __AARCH64EB__
 114         rbit    synd, synd
 115 #endif
 116         clz     synd, synd
 117         cmp     cntrem, synd, lsr 2
 118         add     result, src, synd, lsr 2
 119         csel    result, result, xzr, hi
 120         ret
 121
 122 L(nomatch):
 123         mov     result, 0
 124         ret
 125
 126 END (MEMCHR)
 127 weak_alias (MEMCHR, memchr)
 128 libc_hidden_builtin_def (memchr)