263 lines · plain
1/*2 * strncmp - compare two strings3 *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, AArch6412 */13 14#include "../asmdefs.h"15 16#define REP8_01 0x010101010101010117#define REP8_7f 0x7f7f7f7f7f7f7f7f18#define REP8_80 0x808080808080808019 20/* Parameters and result. */21#define src1 x022#define src2 x123#define limit x224#define result x025 26/* Internal variables. */27#define data1 x328#define data1w w329#define data2 x430#define data2w w431#define has_nul x532#define diff x633#define syndrome x734#define tmp1 x835#define tmp2 x936#define tmp3 x1037#define zeroones x1138#define pos x1239#define limit_wd x1340#define mask x1441#define endloop x1542#define count mask43 44 .text45 .p2align 646 .rep 747 nop /* Pad so that the loop below fits a cache line. */48 .endr49ENTRY_ALIGN (__strncmp_aarch64, 0)50 cbz limit, L(ret0)51 eor tmp1, src1, src252 mov zeroones, #REP8_0153 tst tmp1, #754 and count, src1, #755 b.ne L(misaligned8)56 cbnz count, L(mutual_align)57 /* Calculate the number of full and partial words -1. */58 sub limit_wd, limit, #1 /* limit != 0, so no underflow. */59 lsr limit_wd, limit_wd, #3 /* Convert to Dwords. */60 61 /* NUL detection works on the principle that (X - 1) & (~X) & 0x8062 (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and63 can be done in parallel across the entire word. */64 /* Start of performance-critical section -- one 64B cache line. */65L(loop_aligned):66 ldr data1, [src1], #867 ldr data2, [src2], #868L(start_realigned):69 subs limit_wd, limit_wd, #170 sub tmp1, data1, zeroones71 orr tmp2, data1, #REP8_7f72 eor diff, data1, data2 /* Non-zero if differences found. */73 csinv endloop, diff, xzr, pl /* Last Dword or differences. */74 bics has_nul, tmp1, tmp2 /* Non-zero if NUL terminator. */75 ccmp endloop, #0, #0, eq76 b.eq L(loop_aligned)77 /* End of performance-critical section -- one 64B cache line. */78 79 /* Not reached the limit, must have found the end or a diff. */80 tbz limit_wd, #63, L(not_limit)81 82 /* Limit % 8 == 0 => all bytes significant. */83 ands limit, limit, #784 b.eq L(not_limit)85 86 lsl limit, limit, #3 /* Bits -> bytes. */87 mov mask, #~088#ifdef __AARCH64EB__89 lsr mask, mask, limit90#else91 lsl mask, mask, limit92#endif93 bic data1, data1, mask94 bic data2, data2, mask95 96 /* Make sure that the NUL byte is marked in the syndrome. */97 orr has_nul, has_nul, mask98 99L(not_limit):100 orr syndrome, diff, has_nul101 102#ifndef __AARCH64EB__103 rev syndrome, syndrome104 rev data1, data1105 /* The MS-non-zero bit of the syndrome marks either the first bit106 that is different, or the top bit of the first zero byte.107 Shifting left now will bring the critical information into the108 top bits. */109 clz pos, syndrome110 rev data2, data2111 lsl data1, data1, pos112 lsl data2, data2, pos113 /* But we need to zero-extend (char is unsigned) the value and then114 perform a signed 32-bit subtraction. */115 lsr data1, data1, #56116 sub result, data1, data2, lsr #56117 ret118#else119 /* For big-endian we cannot use the trick with the syndrome value120 as carry-propagation can corrupt the upper bits if the trailing121 bytes in the string contain 0x01. */122 /* However, if there is no NUL byte in the dword, we can generate123 the result directly. We can't just subtract the bytes as the124 MSB might be significant. */125 cbnz has_nul, 1f126 cmp data1, data2127 cset result, ne128 cneg result, result, lo129 ret1301:131 /* Re-compute the NUL-byte detection, using a byte-reversed value. */132 rev tmp3, data1133 sub tmp1, tmp3, zeroones134 orr tmp2, tmp3, #REP8_7f135 bic has_nul, tmp1, tmp2136 rev has_nul, has_nul137 orr syndrome, diff, has_nul138 clz pos, syndrome139 /* The MS-non-zero bit of the syndrome marks either the first bit140 that is different, or the top bit of the first zero byte.141 Shifting left now will bring the critical information into the142 top bits. */143 lsl data1, data1, pos144 lsl data2, data2, pos145 /* But we need to zero-extend (char is unsigned) the value and then146 perform a signed 32-bit subtraction. */147 lsr data1, data1, #56148 sub result, data1, data2, lsr #56149 ret150#endif151 152L(mutual_align):153 /* Sources are mutually aligned, but are not currently at an154 alignment boundary. Round down the addresses and then mask off155 the bytes that precede the start point.156 We also need to adjust the limit calculations, but without157 overflowing if the limit is near ULONG_MAX. */158 bic src1, src1, #7159 bic src2, src2, #7160 ldr data1, [src1], #8161 neg tmp3, count, lsl #3 /* 64 - bits(bytes beyond align). */162 ldr data2, [src2], #8163 mov tmp2, #~0164 sub limit_wd, limit, #1 /* limit != 0, so no underflow. */165#ifdef __AARCH64EB__166 /* Big-endian. Early bytes are at MSB. */167 lsl tmp2, tmp2, tmp3 /* Shift (count & 63). */168#else169 /* Little-endian. Early bytes are at LSB. */170 lsr tmp2, tmp2, tmp3 /* Shift (count & 63). */171#endif172 and tmp3, limit_wd, #7173 lsr limit_wd, limit_wd, #3174 /* Adjust the limit. Only low 3 bits used, so overflow irrelevant. */175 add limit, limit, count176 add tmp3, tmp3, count177 orr data1, data1, tmp2178 orr data2, data2, tmp2179 add limit_wd, limit_wd, tmp3, lsr #3180 b L(start_realigned)181 182 .p2align 6183 /* Don't bother with dwords for up to 16 bytes. */184L(misaligned8):185 cmp limit, #16186 b.hs L(try_misaligned_words)187 188L(byte_loop):189 /* Perhaps we can do better than this. */190 ldrb data1w, [src1], #1191 ldrb data2w, [src2], #1192 subs limit, limit, #1193 ccmp data1w, #1, #0, hi /* NZCV = 0b0000. */194 ccmp data1w, data2w, #0, cs /* NZCV = 0b0000. */195 b.eq L(byte_loop)196L(done):197 sub result, data1, data2198 ret199 /* Align the SRC1 to a dword by doing a bytewise compare and then do200 the dword loop. */201L(try_misaligned_words):202 lsr limit_wd, limit, #3203 cbz count, L(do_misaligned)204 205 neg count, count206 and count, count, #7207 sub limit, limit, count208 lsr limit_wd, limit, #3209 210L(page_end_loop):211 ldrb data1w, [src1], #1212 ldrb data2w, [src2], #1213 cmp data1w, #1214 ccmp data1w, data2w, #0, cs /* NZCV = 0b0000. */215 b.ne L(done)216 subs count, count, #1217 b.hi L(page_end_loop)218 219L(do_misaligned):220 /* Prepare ourselves for the next page crossing. Unlike the aligned221 loop, we fetch 1 less dword because we risk crossing bounds on222 SRC2. */223 mov count, #8224 subs limit_wd, limit_wd, #1225 b.lo L(done_loop)226L(loop_misaligned):227 and tmp2, src2, #0xff8228 eor tmp2, tmp2, #0xff8229 cbz tmp2, L(page_end_loop)230 231 ldr data1, [src1], #8232 ldr data2, [src2], #8233 sub tmp1, data1, zeroones234 orr tmp2, data1, #REP8_7f235 eor diff, data1, data2 /* Non-zero if differences found. */236 bics has_nul, tmp1, tmp2 /* Non-zero if NUL terminator. */237 ccmp diff, #0, #0, eq238 b.ne L(not_limit)239 subs limit_wd, limit_wd, #1240 b.pl L(loop_misaligned)241 242L(done_loop):243 /* We found a difference or a NULL before the limit was reached. */244 and limit, limit, #7245 cbz limit, L(not_limit)246 /* Read the last word. */247 sub src1, src1, 8248 sub src2, src2, 8249 ldr data1, [src1, limit]250 ldr data2, [src2, limit]251 sub tmp1, data1, zeroones252 orr tmp2, data1, #REP8_7f253 eor diff, data1, data2 /* Non-zero if differences found. */254 bics has_nul, tmp1, tmp2 /* Non-zero if NUL terminator. */255 ccmp diff, #0, #0, eq256 b.ne L(not_limit)257 258L(ret0):259 mov result, #0260 ret261 262END ( __strncmp_aarch64)263