newlib/libc/machine/aarch64/memchr.S

   1 /*
   2  * memchr - find a character in a memory zone
   3  *
   4  * Copyright (c) 2014-2022, Arm Limited.
   5  * SPDX-License-Identifier: MIT OR Apache-2.0 WITH LLVM-exception
   6  */
   7
   8 #if (defined (__OPTIMIZE_SIZE__) || defined (PREFER_SIZE_OVER_SPEED))
   9 /* See memchr-stub.c  */
  10 #else
  11 /* Assumptions:
  12  *
  13  * ARMv8-a, AArch64
  14  * Neon Available.
  15  */
  16
  17 #include "asmdefs.h"
  18
  19 /* Arguments and results.  */
  20 #define srcin           x0
  21 #define chrin           w1
  22 #define cntin           x2
  23
  24 #define result          x0
  25
  26 #define src             x3
  27 #define tmp             x4
  28 #define wtmp2           w5
  29 #define synd            x6
  30 #define soff            x9
  31 #define cntrem          x10
  32
  33 #define vrepchr         v0
  34 #define vdata1          v1
  35 #define vdata2          v2
  36 #define vhas_chr1       v3
  37 #define vhas_chr2       v4
  38 #define vrepmask        v5
  39 #define vend            v6
  40
  41 /*
  42  * Core algorithm:
  43  *
  44  * For each 32-byte chunk we calculate a 64-bit syndrome value, with two bits
  45  * per byte. For each tuple, bit 0 is set if the relevant byte matched the
  46  * requested character and bit 1 is not used (faster than using a 32bit
  47  * syndrome). Since the bits in the syndrome reflect exactly the order in which
  48  * things occur in the original string, counting trailing zeros allows to
  49  * identify exactly which byte has matched.
  50  */
  51
  52 ENTRY (memchr)
  53         PTR_ARG (0)
  54         SIZE_ARG (2)
  55         /* Do not dereference srcin if no bytes to compare.  */
  56         cbz     cntin, L(zero_length)
  57         /*
  58          * Magic constant 0x40100401 allows us to identify which lane matches
  59          * the requested byte.
  60          */
  61         mov     wtmp2, #0x0401
  62         movk    wtmp2, #0x4010, lsl #16
  63         dup     vrepchr.16b, chrin
  64         /* Work with aligned 32-byte chunks */
  65         bic     src, srcin, #31
  66         dup     vrepmask.4s, wtmp2
  67         ands    soff, srcin, #31
  68         and     cntrem, cntin, #31
  69         b.eq    L(loop)
  70
  71         /*
  72          * Input string is not 32-byte aligned. We calculate the syndrome
  73          * value for the aligned 32 bytes block containing the first bytes
  74          * and mask the irrelevant part.
  75          */
  76
  77         ld1     {vdata1.16b, vdata2.16b}, [src], #32
  78         sub     tmp, soff, #32
  79         adds    cntin, cntin, tmp
  80         cmeq    vhas_chr1.16b, vdata1.16b, vrepchr.16b
  81         cmeq    vhas_chr2.16b, vdata2.16b, vrepchr.16b
  82         and     vhas_chr1.16b, vhas_chr1.16b, vrepmask.16b
  83         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask.16b
  84         addp    vend.16b, vhas_chr1.16b, vhas_chr2.16b          /* 256->128 */
  85         addp    vend.16b, vend.16b, vend.16b                    /* 128->64 */
  86         mov     synd, vend.d[0]
  87         /* Clear the soff*2 lower bits */
  88         lsl     tmp, soff, #1
  89         lsr     synd, synd, tmp
  90         lsl     synd, synd, tmp
  91         /* The first block can also be the last */
  92         b.ls    L(masklast)
  93         /* Have we found something already? */
  94         cbnz    synd, L(tail)
  95
  96 L(loop):
  97         ld1     {vdata1.16b, vdata2.16b}, [src], #32
  98         subs    cntin, cntin, #32
  99         cmeq    vhas_chr1.16b, vdata1.16b, vrepchr.16b
 100         cmeq    vhas_chr2.16b, vdata2.16b, vrepchr.16b
 101         /* If we're out of data we finish regardless of the result */
 102         b.ls    L(end)
 103         /* Use a fast check for the termination condition */
 104         orr     vend.16b, vhas_chr1.16b, vhas_chr2.16b
 105         addp    vend.2d, vend.2d, vend.2d
 106         mov     synd, vend.d[0]
 107         /* We're not out of data, loop if we haven't found the character */
 108         cbz     synd, L(loop)
 109
 110 L(end):
 111         /* Termination condition found, let's calculate the syndrome value */
 112         and     vhas_chr1.16b, vhas_chr1.16b, vrepmask.16b
 113         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask.16b
 114         addp    vend.16b, vhas_chr1.16b, vhas_chr2.16b          /* 256->128 */
 115         addp    vend.16b, vend.16b, vend.16b                    /* 128->64 */
 116         mov     synd, vend.d[0]
 117         /* Only do the clear for the last possible block */
 118         b.hs    L(tail)
 119
 120 L(masklast):
 121         /* Clear the (32 - ((cntrem + soff) % 32)) * 2 upper bits */
 122         add     tmp, cntrem, soff
 123         and     tmp, tmp, #31
 124         sub     tmp, tmp, #32
 125         neg     tmp, tmp, lsl #1
 126         lsl     synd, synd, tmp
 127         lsr     synd, synd, tmp
 128
 129 L(tail):
 130         /* Count the trailing zeros using bit reversing */
 131         rbit    synd, synd
 132         /* Compensate the last post-increment */
 133         sub     src, src, #32
 134         /* Check that we have found a character */
 135         cmp     synd, #0
 136         /* And count the leading zeros */
 137         clz     synd, synd
 138         /* Compute the potential result */
 139         add     result, src, synd, lsr #1
 140         /* Select result or NULL */
 141         csel    result, xzr, result, eq
 142         ret
 143
 144 L(zero_length):
 145         mov     result, #0
 146         ret
 147
 148 END (memchr)
 149 #endif