310 lines · plain
1/*2 * strcpy/stpcpy - copy a string returning pointer to start/end.3 *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 build as stpcpy, define BUILD_STPCPY before compiling this file.17 18 To test the page crossing code path more thoroughly, compile with19 -DSTRCPY_TEST_PAGE_CROSS - this will force all copies through the slower20 entry path. This option is not intended for production use. */21 22/* Arguments and results. */23#define dstin x024#define srcin x125 26/* Locals and temporaries. */27#define src x228#define dst x329#define data1 x430#define data1w w431#define data2 x532#define data2w w533#define has_nul1 x634#define has_nul2 x735#define tmp1 x836#define tmp2 x937#define tmp3 x1038#define tmp4 x1139#define zeroones x1240#define data1a x1341#define data2a x1442#define pos x1543#define len x1644#define to_align x1745 46#ifdef BUILD_STPCPY47#define STRCPY __stpcpy_aarch6448#else49#define STRCPY __strcpy_aarch6450#endif51 52 /* NUL detection works on the principle that (X - 1) & (~X) & 0x8053 (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and54 can be done in parallel across the entire word. */55 56#define REP8_01 0x010101010101010157#define REP8_7f 0x7f7f7f7f7f7f7f7f58#define REP8_80 0x808080808080808059 60 /* AArch64 systems have a minimum page size of 4k. We can do a quick61 page size check for crossing this boundary on entry and if we62 do not, then we can short-circuit much of the entry code. We63 expect early page-crossing strings to be rare (probability of64 16/MIN_PAGE_SIZE ~= 0.4%), so the branch should be quite65 predictable, even with random strings.66 67 We don't bother checking for larger page sizes, the cost of setting68 up the correct page size is just not worth the extra gain from69 a small reduction in the cases taking the slow path. Note that70 we only care about whether the first fetch, which may be71 misaligned, crosses a page boundary - after that we move to aligned72 fetches for the remainder of the string. */73 74#ifdef STRCPY_TEST_PAGE_CROSS75 /* Make everything that isn't Qword aligned look like a page cross. */76#define MIN_PAGE_P2 477#else78#define MIN_PAGE_P2 1279#endif80 81#define MIN_PAGE_SIZE (1 << MIN_PAGE_P2)82 83ENTRY (STRCPY)84 /* For moderately short strings, the fastest way to do the copy is to85 calculate the length of the string in the same way as strlen, then86 essentially do a memcpy of the result. This avoids the need for87 multiple byte copies and further means that by the time we88 reach the bulk copy loop we know we can always use DWord89 accesses. We expect __strcpy_aarch64 to rarely be called repeatedly90 with the same source string, so branch prediction is likely to91 always be difficult - we mitigate against this by preferring92 conditional select operations over branches whenever this is93 feasible. */94 and tmp2, srcin, #(MIN_PAGE_SIZE - 1)95 mov zeroones, #REP8_0196 and to_align, srcin, #1597 cmp tmp2, #(MIN_PAGE_SIZE - 16)98 neg tmp1, to_align99 /* The first fetch will straddle a (possible) page boundary iff100 srcin + 15 causes bit[MIN_PAGE_P2] to change value. A 16-byte101 aligned string will never fail the page align check, so will102 always take the fast path. */103 b.gt L(page_cross)104 105L(page_cross_ok):106 ldp data1, data2, [srcin]107#ifdef __AARCH64EB__108 /* Because we expect the end to be found within 16 characters109 (profiling shows this is the most common case), it's worth110 swapping the bytes now to save having to recalculate the111 termination syndrome later. We preserve data1 and data2112 so that we can re-use the values later on. */113 rev tmp2, data1114 sub tmp1, tmp2, zeroones115 orr tmp2, tmp2, #REP8_7f116 bics has_nul1, tmp1, tmp2117 b.ne L(fp_le8)118 rev tmp4, data2119 sub tmp3, tmp4, zeroones120 orr tmp4, tmp4, #REP8_7f121#else122 sub tmp1, data1, zeroones123 orr tmp2, data1, #REP8_7f124 bics has_nul1, tmp1, tmp2125 b.ne L(fp_le8)126 sub tmp3, data2, zeroones127 orr tmp4, data2, #REP8_7f128#endif129 bics has_nul2, tmp3, tmp4130 b.eq L(bulk_entry)131 132 /* The string is short (<=16 bytes). We don't know exactly how133 short though, yet. Work out the exact length so that we can134 quickly select the optimal copy strategy. */135L(fp_gt8):136 rev has_nul2, has_nul2137 clz pos, has_nul2138 mov tmp2, #56139 add dst, dstin, pos, lsr #3 /* Bits to bytes. */140 sub pos, tmp2, pos141#ifdef __AARCH64EB__142 lsr data2, data2, pos143#else144 lsl data2, data2, pos145#endif146 str data2, [dst, #1]147 str data1, [dstin]148#ifdef BUILD_STPCPY149 add dstin, dst, #8150#endif151 ret152 153L(fp_le8):154 rev has_nul1, has_nul1155 clz pos, has_nul1156 add dst, dstin, pos, lsr #3 /* Bits to bytes. */157 subs tmp2, pos, #24 /* Pos in bits. */158 b.lt L(fp_lt4)159#ifdef __AARCH64EB__160 mov tmp2, #56161 sub pos, tmp2, pos162 lsr data2, data1, pos163 lsr data1, data1, #32164#else165 lsr data2, data1, tmp2166#endif167 /* 4->7 bytes to copy. */168 str data2w, [dst, #-3]169 str data1w, [dstin]170#ifdef BUILD_STPCPY171 mov dstin, dst172#endif173 ret174L(fp_lt4):175 cbz pos, L(fp_lt2)176 /* 2->3 bytes to copy. */177#ifdef __AARCH64EB__178 lsr data1, data1, #48179#endif180 strh data1w, [dstin]181 /* Fall-through, one byte (max) to go. */182L(fp_lt2):183 /* Null-terminated string. Last character must be zero! */184 strb wzr, [dst]185#ifdef BUILD_STPCPY186 mov dstin, dst187#endif188 ret189 190 .p2align 6191 /* Aligning here ensures that the entry code and main loop all lies192 within one 64-byte cache line. */193L(bulk_entry):194 sub to_align, to_align, #16195 stp data1, data2, [dstin]196 sub src, srcin, to_align197 sub dst, dstin, to_align198 b L(entry_no_page_cross)199 200 /* The inner loop deals with two Dwords at a time. This has a201 slightly higher start-up cost, but we should win quite quickly,202 especially on cores with a high number of issue slots per203 cycle, as we get much better parallelism out of the operations. */204L(main_loop):205 stp data1, data2, [dst], #16206L(entry_no_page_cross):207 ldp data1, data2, [src], #16208 sub tmp1, data1, zeroones209 orr tmp2, data1, #REP8_7f210 sub tmp3, data2, zeroones211 orr tmp4, data2, #REP8_7f212 bic has_nul1, tmp1, tmp2213 bics has_nul2, tmp3, tmp4214 ccmp has_nul1, #0, #0, eq /* NZCV = 0000 */215 b.eq L(main_loop)216 217 /* Since we know we are copying at least 16 bytes, the fastest way218 to deal with the tail is to determine the location of the219 trailing NUL, then (re)copy the 16 bytes leading up to that. */220 cmp has_nul1, #0221#ifdef __AARCH64EB__222 /* For big-endian, carry propagation (if the final byte in the223 string is 0x01) means we cannot use has_nul directly. The224 easiest way to get the correct byte is to byte-swap the data225 and calculate the syndrome a second time. */226 csel data1, data1, data2, ne227 rev data1, data1228 sub tmp1, data1, zeroones229 orr tmp2, data1, #REP8_7f230 bic has_nul1, tmp1, tmp2231#else232 csel has_nul1, has_nul1, has_nul2, ne233#endif234 rev has_nul1, has_nul1235 clz pos, has_nul1236 add tmp1, pos, #72237 add pos, pos, #8238 csel pos, pos, tmp1, ne239 add src, src, pos, lsr #3240 add dst, dst, pos, lsr #3241 ldp data1, data2, [src, #-32]242 stp data1, data2, [dst, #-16]243#ifdef BUILD_STPCPY244 sub dstin, dst, #1245#endif246 ret247 248L(page_cross):249 bic src, srcin, #15250 /* Start by loading two words at [srcin & ~15], then forcing the251 bytes that precede srcin to 0xff. This means they never look252 like termination bytes. */253 ldp data1, data2, [src]254 lsl tmp1, tmp1, #3 /* Bytes beyond alignment -> bits. */255 tst to_align, #7256 csetm tmp2, ne257#ifdef __AARCH64EB__258 lsl tmp2, tmp2, tmp1 /* Shift (tmp1 & 63). */259#else260 lsr tmp2, tmp2, tmp1 /* Shift (tmp1 & 63). */261#endif262 orr data1, data1, tmp2263 orr data2a, data2, tmp2264 cmp to_align, #8265 csinv data1, data1, xzr, lt266 csel data2, data2, data2a, lt267 sub tmp1, data1, zeroones268 orr tmp2, data1, #REP8_7f269 sub tmp3, data2, zeroones270 orr tmp4, data2, #REP8_7f271 bic has_nul1, tmp1, tmp2272 bics has_nul2, tmp3, tmp4273 ccmp has_nul1, #0, #0, eq /* NZCV = 0000 */274 b.eq L(page_cross_ok)275 /* We now need to make data1 and data2 look like they've been276 loaded directly from srcin. Do a rotate on the 128-bit value. */277 lsl tmp1, to_align, #3 /* Bytes->bits. */278 neg tmp2, to_align, lsl #3279#ifdef __AARCH64EB__280 lsl data1a, data1, tmp1281 lsr tmp4, data2, tmp2282 lsl data2, data2, tmp1283 orr tmp4, tmp4, data1a284 cmp to_align, #8285 csel data1, tmp4, data2, lt286 rev tmp2, data1287 rev tmp4, data2288 sub tmp1, tmp2, zeroones289 orr tmp2, tmp2, #REP8_7f290 sub tmp3, tmp4, zeroones291 orr tmp4, tmp4, #REP8_7f292#else293 lsr data1a, data1, tmp1294 lsl tmp4, data2, tmp2295 lsr data2, data2, tmp1296 orr tmp4, tmp4, data1a297 cmp to_align, #8298 csel data1, tmp4, data2, lt299 sub tmp1, data1, zeroones300 orr tmp2, data1, #REP8_7f301 sub tmp3, data2, zeroones302 orr tmp4, data2, #REP8_7f303#endif304 bic has_nul1, tmp1, tmp2305 cbnz has_nul1, L(fp_le8)306 bic has_nul2, tmp3, tmp4307 b L(fp_gt8)308 309END (STRCPY)310