1*4882a593Smuzhiyun/* SPDX-License-Identifier: GPL-2.0-only */ 2*4882a593Smuzhiyun/* 3*4882a593Smuzhiyun * Copyright (C) 2013 ARM Ltd. 4*4882a593Smuzhiyun * Copyright (C) 2013 Linaro. 5*4882a593Smuzhiyun * 6*4882a593Smuzhiyun * This code is based on glibc cortex strings work originally authored by Linaro 7*4882a593Smuzhiyun * be found @ 8*4882a593Smuzhiyun * 9*4882a593Smuzhiyun * http://bazaar.launchpad.net/~linaro-toolchain-dev/cortex-strings/trunk/ 10*4882a593Smuzhiyun * files/head:/src/aarch64/ 11*4882a593Smuzhiyun */ 12*4882a593Smuzhiyun 13*4882a593Smuzhiyun#include <linux/linkage.h> 14*4882a593Smuzhiyun#include <asm/assembler.h> 15*4882a593Smuzhiyun 16*4882a593Smuzhiyun/* 17*4882a593Smuzhiyun * compare two strings 18*4882a593Smuzhiyun * 19*4882a593Smuzhiyun * Parameters: 20*4882a593Smuzhiyun * x0 - const string 1 pointer 21*4882a593Smuzhiyun * x1 - const string 2 pointer 22*4882a593Smuzhiyun * Returns: 23*4882a593Smuzhiyun * x0 - an integer less than, equal to, or greater than zero 24*4882a593Smuzhiyun * if s1 is found, respectively, to be less than, to match, 25*4882a593Smuzhiyun * or be greater than s2. 26*4882a593Smuzhiyun */ 27*4882a593Smuzhiyun 28*4882a593Smuzhiyun#define REP8_01 0x0101010101010101 29*4882a593Smuzhiyun#define REP8_7f 0x7f7f7f7f7f7f7f7f 30*4882a593Smuzhiyun#define REP8_80 0x8080808080808080 31*4882a593Smuzhiyun 32*4882a593Smuzhiyun/* Parameters and result. */ 33*4882a593Smuzhiyunsrc1 .req x0 34*4882a593Smuzhiyunsrc2 .req x1 35*4882a593Smuzhiyunresult .req x0 36*4882a593Smuzhiyun 37*4882a593Smuzhiyun/* Internal variables. */ 38*4882a593Smuzhiyundata1 .req x2 39*4882a593Smuzhiyundata1w .req w2 40*4882a593Smuzhiyundata2 .req x3 41*4882a593Smuzhiyundata2w .req w3 42*4882a593Smuzhiyunhas_nul .req x4 43*4882a593Smuzhiyundiff .req x5 44*4882a593Smuzhiyunsyndrome .req x6 45*4882a593Smuzhiyuntmp1 .req x7 46*4882a593Smuzhiyuntmp2 .req x8 47*4882a593Smuzhiyuntmp3 .req x9 48*4882a593Smuzhiyunzeroones .req x10 49*4882a593Smuzhiyunpos .req x11 50*4882a593Smuzhiyun 51*4882a593SmuzhiyunSYM_FUNC_START_WEAK_PI(strcmp) 52*4882a593Smuzhiyun eor tmp1, src1, src2 53*4882a593Smuzhiyun mov zeroones, #REP8_01 54*4882a593Smuzhiyun tst tmp1, #7 55*4882a593Smuzhiyun b.ne .Lmisaligned8 56*4882a593Smuzhiyun ands tmp1, src1, #7 57*4882a593Smuzhiyun b.ne .Lmutual_align 58*4882a593Smuzhiyun 59*4882a593Smuzhiyun /* 60*4882a593Smuzhiyun * NUL detection works on the principle that (X - 1) & (~X) & 0x80 61*4882a593Smuzhiyun * (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and 62*4882a593Smuzhiyun * can be done in parallel across the entire word. 63*4882a593Smuzhiyun */ 64*4882a593Smuzhiyun.Lloop_aligned: 65*4882a593Smuzhiyun ldr data1, [src1], #8 66*4882a593Smuzhiyun ldr data2, [src2], #8 67*4882a593Smuzhiyun.Lstart_realigned: 68*4882a593Smuzhiyun sub tmp1, data1, zeroones 69*4882a593Smuzhiyun orr tmp2, data1, #REP8_7f 70*4882a593Smuzhiyun eor diff, data1, data2 /* Non-zero if differences found. */ 71*4882a593Smuzhiyun bic has_nul, tmp1, tmp2 /* Non-zero if NUL terminator. */ 72*4882a593Smuzhiyun orr syndrome, diff, has_nul 73*4882a593Smuzhiyun cbz syndrome, .Lloop_aligned 74*4882a593Smuzhiyun b .Lcal_cmpresult 75*4882a593Smuzhiyun 76*4882a593Smuzhiyun.Lmutual_align: 77*4882a593Smuzhiyun /* 78*4882a593Smuzhiyun * Sources are mutually aligned, but are not currently at an 79*4882a593Smuzhiyun * alignment boundary. Round down the addresses and then mask off 80*4882a593Smuzhiyun * the bytes that preceed the start point. 81*4882a593Smuzhiyun */ 82*4882a593Smuzhiyun bic src1, src1, #7 83*4882a593Smuzhiyun bic src2, src2, #7 84*4882a593Smuzhiyun lsl tmp1, tmp1, #3 /* Bytes beyond alignment -> bits. */ 85*4882a593Smuzhiyun ldr data1, [src1], #8 86*4882a593Smuzhiyun neg tmp1, tmp1 /* Bits to alignment -64. */ 87*4882a593Smuzhiyun ldr data2, [src2], #8 88*4882a593Smuzhiyun mov tmp2, #~0 89*4882a593Smuzhiyun /* Big-endian. Early bytes are at MSB. */ 90*4882a593SmuzhiyunCPU_BE( lsl tmp2, tmp2, tmp1 ) /* Shift (tmp1 & 63). */ 91*4882a593Smuzhiyun /* Little-endian. Early bytes are at LSB. */ 92*4882a593SmuzhiyunCPU_LE( lsr tmp2, tmp2, tmp1 ) /* Shift (tmp1 & 63). */ 93*4882a593Smuzhiyun 94*4882a593Smuzhiyun orr data1, data1, tmp2 95*4882a593Smuzhiyun orr data2, data2, tmp2 96*4882a593Smuzhiyun b .Lstart_realigned 97*4882a593Smuzhiyun 98*4882a593Smuzhiyun.Lmisaligned8: 99*4882a593Smuzhiyun /* 100*4882a593Smuzhiyun * Get the align offset length to compare per byte first. 101*4882a593Smuzhiyun * After this process, one string's address will be aligned. 102*4882a593Smuzhiyun */ 103*4882a593Smuzhiyun and tmp1, src1, #7 104*4882a593Smuzhiyun neg tmp1, tmp1 105*4882a593Smuzhiyun add tmp1, tmp1, #8 106*4882a593Smuzhiyun and tmp2, src2, #7 107*4882a593Smuzhiyun neg tmp2, tmp2 108*4882a593Smuzhiyun add tmp2, tmp2, #8 109*4882a593Smuzhiyun subs tmp3, tmp1, tmp2 110*4882a593Smuzhiyun csel pos, tmp1, tmp2, hi /*Choose the maximum. */ 111*4882a593Smuzhiyun.Ltinycmp: 112*4882a593Smuzhiyun ldrb data1w, [src1], #1 113*4882a593Smuzhiyun ldrb data2w, [src2], #1 114*4882a593Smuzhiyun subs pos, pos, #1 115*4882a593Smuzhiyun ccmp data1w, #1, #0, ne /* NZCV = 0b0000. */ 116*4882a593Smuzhiyun ccmp data1w, data2w, #0, cs /* NZCV = 0b0000. */ 117*4882a593Smuzhiyun b.eq .Ltinycmp 118*4882a593Smuzhiyun cbnz pos, 1f /*find the null or unequal...*/ 119*4882a593Smuzhiyun cmp data1w, #1 120*4882a593Smuzhiyun ccmp data1w, data2w, #0, cs 121*4882a593Smuzhiyun b.eq .Lstart_align /*the last bytes are equal....*/ 122*4882a593Smuzhiyun1: 123*4882a593Smuzhiyun sub result, data1, data2 124*4882a593Smuzhiyun ret 125*4882a593Smuzhiyun 126*4882a593Smuzhiyun.Lstart_align: 127*4882a593Smuzhiyun ands xzr, src1, #7 128*4882a593Smuzhiyun b.eq .Lrecal_offset 129*4882a593Smuzhiyun /*process more leading bytes to make str1 aligned...*/ 130*4882a593Smuzhiyun add src1, src1, tmp3 131*4882a593Smuzhiyun add src2, src2, tmp3 132*4882a593Smuzhiyun /*load 8 bytes from aligned str1 and non-aligned str2..*/ 133*4882a593Smuzhiyun ldr data1, [src1], #8 134*4882a593Smuzhiyun ldr data2, [src2], #8 135*4882a593Smuzhiyun 136*4882a593Smuzhiyun sub tmp1, data1, zeroones 137*4882a593Smuzhiyun orr tmp2, data1, #REP8_7f 138*4882a593Smuzhiyun bic has_nul, tmp1, tmp2 139*4882a593Smuzhiyun eor diff, data1, data2 /* Non-zero if differences found. */ 140*4882a593Smuzhiyun orr syndrome, diff, has_nul 141*4882a593Smuzhiyun cbnz syndrome, .Lcal_cmpresult 142*4882a593Smuzhiyun /*How far is the current str2 from the alignment boundary...*/ 143*4882a593Smuzhiyun and tmp3, tmp3, #7 144*4882a593Smuzhiyun.Lrecal_offset: 145*4882a593Smuzhiyun neg pos, tmp3 146*4882a593Smuzhiyun.Lloopcmp_proc: 147*4882a593Smuzhiyun /* 148*4882a593Smuzhiyun * Divide the eight bytes into two parts. First,backwards the src2 149*4882a593Smuzhiyun * to an alignment boundary,load eight bytes from the SRC2 alignment 150*4882a593Smuzhiyun * boundary,then compare with the relative bytes from SRC1. 151*4882a593Smuzhiyun * If all 8 bytes are equal,then start the second part's comparison. 152*4882a593Smuzhiyun * Otherwise finish the comparison. 153*4882a593Smuzhiyun * This special handle can garantee all the accesses are in the 154*4882a593Smuzhiyun * thread/task space in avoid to overrange access. 155*4882a593Smuzhiyun */ 156*4882a593Smuzhiyun ldr data1, [src1,pos] 157*4882a593Smuzhiyun ldr data2, [src2,pos] 158*4882a593Smuzhiyun sub tmp1, data1, zeroones 159*4882a593Smuzhiyun orr tmp2, data1, #REP8_7f 160*4882a593Smuzhiyun bic has_nul, tmp1, tmp2 161*4882a593Smuzhiyun eor diff, data1, data2 /* Non-zero if differences found. */ 162*4882a593Smuzhiyun orr syndrome, diff, has_nul 163*4882a593Smuzhiyun cbnz syndrome, .Lcal_cmpresult 164*4882a593Smuzhiyun 165*4882a593Smuzhiyun /*The second part process*/ 166*4882a593Smuzhiyun ldr data1, [src1], #8 167*4882a593Smuzhiyun ldr data2, [src2], #8 168*4882a593Smuzhiyun sub tmp1, data1, zeroones 169*4882a593Smuzhiyun orr tmp2, data1, #REP8_7f 170*4882a593Smuzhiyun bic has_nul, tmp1, tmp2 171*4882a593Smuzhiyun eor diff, data1, data2 /* Non-zero if differences found. */ 172*4882a593Smuzhiyun orr syndrome, diff, has_nul 173*4882a593Smuzhiyun cbz syndrome, .Lloopcmp_proc 174*4882a593Smuzhiyun 175*4882a593Smuzhiyun.Lcal_cmpresult: 176*4882a593Smuzhiyun /* 177*4882a593Smuzhiyun * reversed the byte-order as big-endian,then CLZ can find the most 178*4882a593Smuzhiyun * significant zero bits. 179*4882a593Smuzhiyun */ 180*4882a593SmuzhiyunCPU_LE( rev syndrome, syndrome ) 181*4882a593SmuzhiyunCPU_LE( rev data1, data1 ) 182*4882a593SmuzhiyunCPU_LE( rev data2, data2 ) 183*4882a593Smuzhiyun 184*4882a593Smuzhiyun /* 185*4882a593Smuzhiyun * For big-endian we cannot use the trick with the syndrome value 186*4882a593Smuzhiyun * as carry-propagation can corrupt the upper bits if the trailing 187*4882a593Smuzhiyun * bytes in the string contain 0x01. 188*4882a593Smuzhiyun * However, if there is no NUL byte in the dword, we can generate 189*4882a593Smuzhiyun * the result directly. We cannot just subtract the bytes as the 190*4882a593Smuzhiyun * MSB might be significant. 191*4882a593Smuzhiyun */ 192*4882a593SmuzhiyunCPU_BE( cbnz has_nul, 1f ) 193*4882a593SmuzhiyunCPU_BE( cmp data1, data2 ) 194*4882a593SmuzhiyunCPU_BE( cset result, ne ) 195*4882a593SmuzhiyunCPU_BE( cneg result, result, lo ) 196*4882a593SmuzhiyunCPU_BE( ret ) 197*4882a593SmuzhiyunCPU_BE( 1: ) 198*4882a593Smuzhiyun /*Re-compute the NUL-byte detection, using a byte-reversed value. */ 199*4882a593SmuzhiyunCPU_BE( rev tmp3, data1 ) 200*4882a593SmuzhiyunCPU_BE( sub tmp1, tmp3, zeroones ) 201*4882a593SmuzhiyunCPU_BE( orr tmp2, tmp3, #REP8_7f ) 202*4882a593SmuzhiyunCPU_BE( bic has_nul, tmp1, tmp2 ) 203*4882a593SmuzhiyunCPU_BE( rev has_nul, has_nul ) 204*4882a593SmuzhiyunCPU_BE( orr syndrome, diff, has_nul ) 205*4882a593Smuzhiyun 206*4882a593Smuzhiyun clz pos, syndrome 207*4882a593Smuzhiyun /* 208*4882a593Smuzhiyun * The MS-non-zero bit of the syndrome marks either the first bit 209*4882a593Smuzhiyun * that is different, or the top bit of the first zero byte. 210*4882a593Smuzhiyun * Shifting left now will bring the critical information into the 211*4882a593Smuzhiyun * top bits. 212*4882a593Smuzhiyun */ 213*4882a593Smuzhiyun lsl data1, data1, pos 214*4882a593Smuzhiyun lsl data2, data2, pos 215*4882a593Smuzhiyun /* 216*4882a593Smuzhiyun * But we need to zero-extend (char is unsigned) the value and then 217*4882a593Smuzhiyun * perform a signed 32-bit subtraction. 218*4882a593Smuzhiyun */ 219*4882a593Smuzhiyun lsr data1, data1, #56 220*4882a593Smuzhiyun sub result, data1, data2, lsr #56 221*4882a593Smuzhiyun ret 222*4882a593SmuzhiyunSYM_FUNC_END_PI(strcmp) 223*4882a593SmuzhiyunEXPORT_SYMBOL_NOKASAN(strcmp) 224