187 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.12 */13 14#include "../asmdefs.h"15 16/* Arguments and results. */17#define srcin x018#define len x019 20/* Locals and temporaries. */21#define src x122#define data1 x223#define data2 x324#define has_nul1 x425#define has_nul2 x526#define tmp1 x427#define tmp2 x528#define tmp3 x629#define tmp4 x730#define zeroones x831#define offset x932 33 /* NUL detection works on the principle that (X - 1) & (~X) & 0x8034 (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and35 can be done in parallel across the entire word. A faster check36 (X - 1) & 0x80 is zero for non-NUL ASCII characters, but gives37 false hits for characters 129..255. */38 39#define REP8_01 0x010101010101010140#define REP8_7f 0x7f7f7f7f7f7f7f7f41 42 /* This implementation is compatible with Memory Tagging. All loads43 are 16 bytes in size and 16 bytes aligned. This also avoids the44 need for page boundary checks. This implementation is correct45 even without Memory Tagging, but other implementations could be46 more beneficial if Memory Tagging is not enabled.47 48 First load is aligned down and can contain bytes that are located49 before the string. This is handled by modifying the "zeroones"50 mask. The bytes that need to be ignored are set to zero.51 If the string is aligned in such a way that 8 or more bytes from52 the first load should be ignored, there is a special case53 (skip_first_8_bytes) which only compares the second 8 bytes.54 55 If there is a NUL byte in the first load, we calculate the length56 from the 2 8-byte words using conditional select to reduce branch57 mispredictions.58 59 If the string is longer than 16 bytes, we check 32 bytes per60 iteration using the fast NUL check (main_loop). If we encounter61 non-ASCII characters, we fallback to a second loop62 (nonascii_loop) using the full NUL check. */63 64ENTRY(__strlen_aarch64_mte)65 bic src, srcin, 15 /* Align down to 16 bytes. */66 mov zeroones, REP8_0167 /* (offset & 63) holds number of bits to ignore in a register.*/68 lsl offset, srcin, 369 ldp data1, data2, [src], -1670 lsl tmp1, zeroones, offset /* Shift (offset & 63). */71#ifdef __AARCH64EB__72 /* For big-endian, carry propagation (if the final byte in the73 string is 0x01) means we cannot use has_nul1/2 directly.74 e.g. 0x0100 - 0x0101 = 0xffff, so 0x01 will be mistaken for NUL.75 Since we expect strings to be small and early-exit,76 byte-swap the data now so has_null1/2 will be correct. */77 rev data1, data178 rev data2, data279#endif80 tbnz srcin, 3, L(skip_first_8_bytes)81 sub tmp1, data1, tmp182 orr tmp2, data1, REP8_7f83 sub tmp3, data2, zeroones84 orr tmp4, data2, REP8_7f85 bics has_nul1, tmp1, tmp286 bic has_nul2, tmp3, tmp487 /* If comparison happens, C flag is always set. */88 ccmp has_nul2, 0, 0, eq89 beq L(main_loop)90 91 /* Enter with C = has_nul1 == 0. */92 csel has_nul1, has_nul1, has_nul2, cc93 and tmp2, srcin, 7 /* Bytes to ignore. */94 rev has_nul1, has_nul195 neg tmp2, tmp296 clz tmp1, has_nul1 /* Count bits before NUL. */97 /* Add 8 if NUL byte is not in first register. */98 add tmp3, tmp2, 899 csel len, tmp2, tmp3, cc100 add len, len, tmp1, lsr 3101 ret102 103L(skip_first_8_bytes):104 sub tmp1, data2, tmp1105 orr tmp2, data2, REP8_7f106 bics has_nul1, tmp1, tmp2107 beq L(main_loop)108 109 rev has_nul1, has_nul1110 lsl tmp1, has_nul1, offset /* Ignore bytes before string. */111 clz tmp1, tmp1 /* Count bits before NUL. */112 lsr len, tmp1, 3113 ret114 115 /* The inner loop processes 32 bytes per iteration and uses the fast116 NUL check. If we encounter non-ASCII characters, use a second117 loop with the accurate NUL check. */118 .p2align 4119L(main_loop):120 ldp data1, data2, [src, 32]!121 sub tmp1, data1, zeroones122 sub tmp3, data2, zeroones123 orr tmp2, tmp1, tmp3124 tst tmp2, zeroones, lsl 7125 bne 1f126 ldp data1, data2, [src, 16]127 sub tmp1, data1, zeroones128 sub tmp3, data2, zeroones129 orr tmp2, tmp1, tmp3130 tst tmp2, zeroones, lsl 7131 beq L(main_loop)132 add src, src, 161331:134 /* The fast check failed, so do the slower, accurate NUL check. */135 orr tmp2, data1, REP8_7f136 orr tmp4, data2, REP8_7f137 bics has_nul1, tmp1, tmp2138 bic has_nul2, tmp3, tmp4139 ccmp has_nul2, 0, 0, eq140 beq L(nonascii_loop)141 142 /* Enter with C = has_nul1 == 0. */143L(tail):144#ifdef __AARCH64EB__145 /* For big-endian, carry propagation (if the final byte in the146 string is 0x01) means we cannot use has_nul1/2 directly. The147 easiest way to get the correct byte is to byte-swap the data148 and calculate the syndrome a second time. */149 csel data1, data1, data2, cc150 rev data1, data1151 sub tmp1, data1, zeroones152 orr tmp2, data1, REP8_7f153 bic has_nul1, tmp1, tmp2154#else155 csel has_nul1, has_nul1, has_nul2, cc156#endif157 sub len, src, srcin158 rev has_nul1, has_nul1159 add tmp2, len, 8160 clz tmp1, has_nul1161 csel len, len, tmp2, cc162 add len, len, tmp1, lsr 3163 ret164 165L(nonascii_loop):166 ldp data1, data2, [src, 16]!167 sub tmp1, data1, zeroones168 orr tmp2, data1, REP8_7f169 sub tmp3, data2, zeroones170 orr tmp4, data2, REP8_7f171 bics has_nul1, tmp1, tmp2172 bic has_nul2, tmp3, tmp4173 ccmp has_nul2, 0, 0, eq174 bne L(tail)175 ldp data1, data2, [src, 16]!176 sub tmp1, data1, zeroones177 orr tmp2, data1, REP8_7f178 sub tmp3, data2, zeroones179 orr tmp4, data2, REP8_7f180 bics has_nul1, tmp1, tmp2181 bic has_nul2, tmp3, tmp4182 ccmp has_nul2, 0, 0, eq183 beq L(nonascii_loop)184 b L(tail)185 186END(__strlen_aarch64_mte)187