1/* SPDX-License-Identifier: GPL-2.0-only */ 2/* 3 * Copyright (c) 2013-2022, Arm Limited. 4 * 5 * Adapted from the original at: 6 * https://github.com/ARM-software/optimized-routines/blob/189dfefe37d54c5b/string/aarch64/strncmp.S 7 */ 8 9#include <linux/linkage.h> 10#include <asm/assembler.h> 11 12/* Assumptions: 13 * 14 * ARMv8-a, AArch64. 15 * MTE compatible. 16 */ 17 18#define L(label) .L ## label 19 20#define REP8_01 0x0101010101010101 21#define REP8_7f 0x7f7f7f7f7f7f7f7f 22 23/* Parameters and result. */ 24#define src1 x0 25#define src2 x1 26#define limit x2 27#define result x0 28 29/* Internal variables. */ 30#define data1 x3 31#define data1w w3 32#define data2 x4 33#define data2w w4 34#define has_nul x5 35#define diff x6 36#define syndrome x7 37#define tmp1 x8 38#define tmp2 x9 39#define tmp3 x10 40#define zeroones x11 41#define pos x12 42#define mask x13 43#define endloop x14 44#define count mask 45#define offset pos 46#define neg_offset x15 47 48SYM_FUNC_START(__pi_strncmp) 49 cbz limit, L(ret0) 50 eor tmp1, src1, src2 51 mov zeroones, #REP8_01 52 tst tmp1, #7 53 and count, src1, #7 54 b.ne L(misaligned8) 55 cbnz count, L(mutual_align) 56 57 /* NUL detection works on the principle that (X - 1) & (~X) & 0x80 58 (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and 59 can be done in parallel across the entire word. */ 60 .p2align 4 61L(loop_aligned): 62 ldr data1, [src1], #8 63 ldr data2, [src2], #8 64L(start_realigned): 65 subs limit, limit, #8 66 sub tmp1, data1, zeroones 67 orr tmp2, data1, #REP8_7f 68 eor diff, data1, data2 /* Non-zero if differences found. */ 69 csinv endloop, diff, xzr, hi /* Last Dword or differences. */ 70 bics has_nul, tmp1, tmp2 /* Non-zero if NUL terminator. */ 71 ccmp endloop, #0, #0, eq 72 b.eq L(loop_aligned) 73 /* End of main loop */ 74 75L(full_check): 76 orr syndrome, diff, has_nul 77 add limit, limit, 8 /* Rewind limit to before last subs. */ 78L(syndrome_check): 79 /* Limit was reached. Check if the NUL byte or the difference 80 is before the limit. */ 81 rev syndrome, syndrome 82 rev data1, data1 83 clz pos, syndrome 84 rev data2, data2 85 lsl data1, data1, pos 86 cmp limit, pos, lsr #3 87 lsl data2, data2, pos 88 /* But we need to zero-extend (char is unsigned) the value and then 89 perform a signed 32-bit subtraction. */ 90 lsr data1, data1, #56 91 sub result, data1, data2, lsr #56 92 csel result, result, xzr, hi 93 ret 94 95L(mutual_align): 96 /* Sources are mutually aligned, but are not currently at an 97 alignment boundary. Round down the addresses and then mask off 98 the bytes that precede the start point. 99 We also need to adjust the limit calculations, but without 100 overflowing if the limit is near ULONG_MAX. */ 101 bic src1, src1, #7 102 bic src2, src2, #7 103 ldr data1, [src1], #8 104 neg tmp3, count, lsl #3 /* 64 - bits(bytes beyond align). */ 105 ldr data2, [src2], #8 106 mov tmp2, #~0 107 lsr tmp2, tmp2, tmp3 /* Shift (count & 63). */ 108 /* Adjust the limit and ensure it doesn't overflow. */ 109 adds limit, limit, count 110 csinv limit, limit, xzr, lo 111 orr data1, data1, tmp2 112 orr data2, data2, tmp2 113 b L(start_realigned) 114 115 .p2align 4 116 /* Don't bother with dwords for up to 16 bytes. */ 117L(misaligned8): 118 cmp limit, #16 119 b.hs L(try_misaligned_words) 120 121L(byte_loop): 122 /* Perhaps we can do better than this. */ 123 ldrb data1w, [src1], #1 124 ldrb data2w, [src2], #1 125 subs limit, limit, #1 126 ccmp data1w, #1, #0, hi /* NZCV = 0b0000. */ 127 ccmp data1w, data2w, #0, cs /* NZCV = 0b0000. */ 128 b.eq L(byte_loop) 129L(done): 130 sub result, data1, data2 131 ret 132 /* Align the SRC1 to a dword by doing a bytewise compare and then do 133 the dword loop. */ 134L(try_misaligned_words): 135 cbz count, L(src1_aligned) 136 137 neg count, count 138 and count, count, #7 139 sub limit, limit, count 140 141L(page_end_loop): 142 ldrb data1w, [src1], #1 143 ldrb data2w, [src2], #1 144 cmp data1w, #1 145 ccmp data1w, data2w, #0, cs /* NZCV = 0b0000. */ 146 b.ne L(done) 147 subs count, count, #1 148 b.hi L(page_end_loop) 149 150 /* The following diagram explains the comparison of misaligned strings. 151 The bytes are shown in natural order. For little-endian, it is 152 reversed in the registers. The "x" bytes are before the string. 153 The "|" separates data that is loaded at one time. 154 src1 | a a a a a a a a | b b b c c c c c | . . . 155 src2 | x x x x x a a a a a a a a b b b | c c c c c . . . 156 157 After shifting in each step, the data looks like this: 158 STEP_A STEP_B STEP_C 159 data1 a a a a a a a a b b b c c c c c b b b c c c c c 160 data2 a a a a a a a a b b b 0 0 0 0 0 0 0 0 c c c c c 161 162 The bytes with "0" are eliminated from the syndrome via mask. 163 164 Align SRC2 down to 16 bytes. This way we can read 16 bytes at a 165 time from SRC2. The comparison happens in 3 steps. After each step 166 the loop can exit, or read from SRC1 or SRC2. */ 167L(src1_aligned): 168 /* Calculate offset from 8 byte alignment to string start in bits. No 169 need to mask offset since shifts are ignoring upper bits. */ 170 lsl offset, src2, #3 171 bic src2, src2, #0xf 172 mov mask, -1 173 neg neg_offset, offset 174 ldr data1, [src1], #8 175 ldp tmp1, tmp2, [src2], #16 176 lsl mask, mask, neg_offset 177 and neg_offset, neg_offset, #63 /* Need actual value for cmp later. */ 178 /* Skip the first compare if data in tmp1 is irrelevant. */ 179 tbnz offset, 6, L(misaligned_mid_loop) 180 181L(loop_misaligned): 182 /* STEP_A: Compare full 8 bytes when there is enough data from SRC2.*/ 183 lsr data2, tmp1, offset 184 lsl tmp1, tmp2, neg_offset 185 subs limit, limit, #8 186 orr data2, data2, tmp1 /* 8 bytes from SRC2 combined from two regs.*/ 187 sub has_nul, data1, zeroones 188 eor diff, data1, data2 /* Non-zero if differences found. */ 189 orr tmp3, data1, #REP8_7f 190 csinv endloop, diff, xzr, hi /* If limit, set to all ones. */ 191 bic has_nul, has_nul, tmp3 /* Non-zero if NUL byte found in SRC1. */ 192 orr tmp3, endloop, has_nul 193 cbnz tmp3, L(full_check) 194 195 ldr data1, [src1], #8 196L(misaligned_mid_loop): 197 /* STEP_B: Compare first part of data1 to second part of tmp2. */ 198 lsr data2, tmp2, offset 199 #define data1_fixed data1 200 sub has_nul, data1_fixed, zeroones 201 orr tmp3, data1_fixed, #REP8_7f 202 eor diff, data2, data1 /* Non-zero if differences found. */ 203 bic has_nul, has_nul, tmp3 /* Non-zero if NUL terminator. */ 204 cmp limit, neg_offset, lsr #3 205 orr syndrome, diff, has_nul 206 bic syndrome, syndrome, mask /* Ignore later bytes. */ 207 csinv tmp3, syndrome, xzr, hi /* If limit, set to all ones. */ 208 cbnz tmp3, L(syndrome_check) 209 210 /* STEP_C: Compare second part of data1 to first part of tmp1. */ 211 ldp tmp1, tmp2, [src2], #16 212 cmp limit, #8 213 lsl data2, tmp1, neg_offset 214 eor diff, data2, data1 /* Non-zero if differences found. */ 215 orr syndrome, diff, has_nul 216 and syndrome, syndrome, mask /* Ignore earlier bytes. */ 217 csinv tmp3, syndrome, xzr, hi /* If limit, set to all ones. */ 218 cbnz tmp3, L(syndrome_check) 219 220 ldr data1, [src1], #8 221 sub limit, limit, #8 222 b L(loop_misaligned) 223 224L(ret0): 225 mov result, #0 226 ret 227SYM_FUNC_END(__pi_strncmp) 228SYM_FUNC_ALIAS_WEAK(strncmp, __pi_strncmp) 229EXPORT_SYMBOL_NOKASAN(strncmp) 230