208 lines · plain
1/*2 * strlen - calculate the length of a string3 *4 * Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5 * See https://llvm.org/LICENSE.txt for license information.6 * SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7 */8 9/* Assumptions:10 *11 * ARMv8-a, AArch64, unaligned accesses, min page size 4k.12 */13 14#include "../asmdefs.h"15 16/* To test the page crossing code path more thoroughly, compile with17 -DTEST_PAGE_CROSS - this will force all calls through the slower18 entry path. This option is not intended for production use. */19 20/* Arguments and results. */21#define srcin x022#define len x023 24/* Locals and temporaries. */25#define src x126#define data1 x227#define data2 x328#define has_nul1 x429#define has_nul2 x530#define tmp1 x431#define tmp2 x532#define tmp3 x633#define tmp4 x734#define zeroones x835 36 /* NUL detection works on the principle that (X - 1) & (~X) & 0x8037 (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and38 can be done in parallel across the entire word. A faster check39 (X - 1) & 0x80 is zero for non-NUL ASCII characters, but gives40 false hits for characters 129..255. */41 42#define REP8_01 0x010101010101010143#define REP8_7f 0x7f7f7f7f7f7f7f7f44#define REP8_80 0x808080808080808045 46#ifdef TEST_PAGE_CROSS47# define MIN_PAGE_SIZE 1548#else49# define MIN_PAGE_SIZE 409650#endif51 52 /* Since strings are short on average, we check the first 16 bytes53 of the string for a NUL character. In order to do an unaligned ldp54 safely we have to do a page cross check first. If there is a NUL55 byte we calculate the length from the 2 8-byte words using56 conditional select to reduce branch mispredictions (it is unlikely57 __strlen_aarch64 will be repeatedly called on strings with the same length).58 59 If the string is longer than 16 bytes, we align src so don't need60 further page cross checks, and process 32 bytes per iteration61 using the fast NUL check. If we encounter non-ASCII characters,62 fallback to a second loop using the full NUL check.63 64 If the page cross check fails, we read 16 bytes from an aligned65 address, remove any characters before the string, and continue66 in the main loop using aligned loads. Since strings crossing a67 page in the first 16 bytes are rare (probability of68 16/MIN_PAGE_SIZE ~= 0.4%), this case does not need to be optimized.69 70 AArch64 systems have a minimum page size of 4k. We don't bother71 checking for larger page sizes - the cost of setting up the correct72 page size is just not worth the extra gain from a small reduction in73 the cases taking the slow path. Note that we only care about74 whether the first fetch, which may be misaligned, crosses a page75 boundary. */76 77ENTRY (__strlen_aarch64)78 and tmp1, srcin, MIN_PAGE_SIZE - 179 mov zeroones, REP8_0180 cmp tmp1, MIN_PAGE_SIZE - 1681 b.gt L(page_cross)82 ldp data1, data2, [srcin]83#ifdef __AARCH64EB__84 /* For big-endian, carry propagation (if the final byte in the85 string is 0x01) means we cannot use has_nul1/2 directly.86 Since we expect strings to be small and early-exit,87 byte-swap the data now so has_null1/2 will be correct. */88 rev data1, data189 rev data2, data290#endif91 sub tmp1, data1, zeroones92 orr tmp2, data1, REP8_7f93 sub tmp3, data2, zeroones94 orr tmp4, data2, REP8_7f95 bics has_nul1, tmp1, tmp296 bic has_nul2, tmp3, tmp497 ccmp has_nul2, 0, 0, eq98 beq L(main_loop_entry)99 100 /* Enter with C = has_nul1 == 0. */101 csel has_nul1, has_nul1, has_nul2, cc102 mov len, 8103 rev has_nul1, has_nul1104 clz tmp1, has_nul1105 csel len, xzr, len, cc106 add len, len, tmp1, lsr 3107 ret108 109 /* The inner loop processes 32 bytes per iteration and uses the fast110 NUL check. If we encounter non-ASCII characters, use a second111 loop with the accurate NUL check. */112 .p2align 4113L(main_loop_entry):114 bic src, srcin, 15115 sub src, src, 16116L(main_loop):117 ldp data1, data2, [src, 32]!118L(page_cross_entry):119 sub tmp1, data1, zeroones120 sub tmp3, data2, zeroones121 orr tmp2, tmp1, tmp3122 tst tmp2, zeroones, lsl 7123 bne 1f124 ldp data1, data2, [src, 16]125 sub tmp1, data1, zeroones126 sub tmp3, data2, zeroones127 orr tmp2, tmp1, tmp3128 tst tmp2, zeroones, lsl 7129 beq L(main_loop)130 add src, src, 161311:132 /* The fast check failed, so do the slower, accurate NUL check. */133 orr tmp2, data1, REP8_7f134 orr tmp4, data2, REP8_7f135 bics has_nul1, tmp1, tmp2136 bic has_nul2, tmp3, tmp4137 ccmp has_nul2, 0, 0, eq138 beq L(nonascii_loop)139 140 /* Enter with C = has_nul1 == 0. */141L(tail):142#ifdef __AARCH64EB__143 /* For big-endian, carry propagation (if the final byte in the144 string is 0x01) means we cannot use has_nul1/2 directly. The145 easiest way to get the correct byte is to byte-swap the data146 and calculate the syndrome a second time. */147 csel data1, data1, data2, cc148 rev data1, data1149 sub tmp1, data1, zeroones150 orr tmp2, data1, REP8_7f151 bic has_nul1, tmp1, tmp2152#else153 csel has_nul1, has_nul1, has_nul2, cc154#endif155 sub len, src, srcin156 rev has_nul1, has_nul1157 add tmp2, len, 8158 clz tmp1, has_nul1159 csel len, len, tmp2, cc160 add len, len, tmp1, lsr 3161 ret162 163L(nonascii_loop):164 ldp data1, data2, [src, 16]!165 sub tmp1, data1, zeroones166 orr tmp2, data1, REP8_7f167 sub tmp3, data2, zeroones168 orr tmp4, data2, REP8_7f169 bics has_nul1, tmp1, tmp2170 bic has_nul2, tmp3, tmp4171 ccmp has_nul2, 0, 0, eq172 bne L(tail)173 ldp data1, data2, [src, 16]!174 sub tmp1, data1, zeroones175 orr tmp2, data1, REP8_7f176 sub tmp3, data2, zeroones177 orr tmp4, data2, REP8_7f178 bics has_nul1, tmp1, tmp2179 bic has_nul2, tmp3, tmp4180 ccmp has_nul2, 0, 0, eq181 beq L(nonascii_loop)182 b L(tail)183 184 /* Load 16 bytes from [srcin & ~15] and force the bytes that precede185 srcin to 0x7f, so we ignore any NUL bytes before the string.186 Then continue in the aligned loop. */187L(page_cross):188 bic src, srcin, 15189 ldp data1, data2, [src]190 lsl tmp1, srcin, 3191 mov tmp4, -1192#ifdef __AARCH64EB__193 /* Big-endian. Early bytes are at MSB. */194 lsr tmp1, tmp4, tmp1 /* Shift (tmp1 & 63). */195#else196 /* Little-endian. Early bytes are at LSB. */197 lsl tmp1, tmp4, tmp1 /* Shift (tmp1 & 63). */198#endif199 orr tmp1, tmp1, REP8_80200 orn data1, data1, tmp1201 orn tmp2, data2, tmp1202 tst srcin, 8203 csel data1, data1, tmp4, eq204 csel data2, data2, tmp2, eq205 b L(page_cross_entry)206 207END (__strlen_aarch64)208