From nobody Mon Dec 25 14:26:00 2023 X-Original-To: dev-commits-src-main@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4SzKvY1GhQz54n40; Mon, 25 Dec 2023 14:26:01 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R3" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4SzKvX6F5zz3N7j; Mon, 25 Dec 2023 14:26:00 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1703514360; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=wBLkyjzlCsvToJYFGe6QPN2qBI9pBjhAzAB+f/Gctsk=; b=eC+Q9WfpHJ0LsqOztFfjzo8Jd8choXAH6qQuP8SSohXQmGhoxYC16UpaFUp/9UJswyMFx8 iGXNa6unZb1kMioJmUboJnn7wh1hmV2DG9NL5sA0n1zTS/Fj9ulNN1G8S2N8D5t5oMSC+Y 9K84KYVdZpuw4zBCYwU8WdQMUl0IF4CDKsJqbOhLH82slIQ9/PUxJdozLO9wr29RxVFPj4 EaNyCuSfrGWR6cIZ/Bnz4UxKI9135fHRsT7RCkj0j+b2gIeV1i4WtzO/9oQMfLPb7dPp54 /agzHRLUDqmH/eGMd4pssAhQ9TjcMJNpnjN5wSxlIkGTbJwNoCY3/wrwiOQbZw== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1703514360; a=rsa-sha256; cv=none; b=PseaP0DQlho5sOfqZRwRHiSL7sO2KUhfWG03lLopnittnl/p0CMsvkgpWtT9D1EO8m9Lwh tDCDzM+iDsYFZBUwfha8l7PmyYEEjd1dG6lhiYltfJwdO1VrNMfnjAOxcIjDK55MHS8hpM EZWy2t8SJzH+aF7gCBXD2Gugxjuy+U5TCfcAp2/4EchIAquJam0hJx4CozUAOaXVQIGmUi qCWk923wGIO4qtI/6T8IdpTAr/C+k6GA2t6keCfRHqC5WWHtcQ6wew+3d7Jp5aNMLnNolj xhK/dTvtVX7I7UQ0yUEqT7GY1if4/QHvdkXedvn3tkYZXdvErvgMm7zMmcVHVQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1703514360; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=wBLkyjzlCsvToJYFGe6QPN2qBI9pBjhAzAB+f/Gctsk=; b=mjOrXK3CbiEw+nN3bQemaLgXCIuUtl0WTp2AVwMkC6RxLejfJ/EMgB0qn8bhydxpqNKf0F dZYTHXpL0WqTuMs1xQWCGCNBiMGULufhZlLhl4xWsY+/Ja/1BFnmK6vZ5LZK2G3o5gMZcX qrT1g9G0tHOg3velIj4KrlQnmbtathUGitbslI5s3JsauTi4SPRBQcGXf4U3UpFpLS5xiM kdQkNpxbOz7MGS1q14IjVOfEuq0s4U10qDFx4z7CX+50FwDfx3svmkbAt9zEAplqc9SdB5 2XRZCyFVlbahvqe3WTwGGyVGC0kPIn84YoMvRnbhXz96KegMvqNwNUm5G+GA5A== Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4SzKvX5MGQzmP; Mon, 25 Dec 2023 14:26:00 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.17.1/8.17.1) with ESMTP id 3BPEQ0Du023795; Mon, 25 Dec 2023 14:26:00 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.17.1/8.17.1/Submit) id 3BPEQ0jH023792; Mon, 25 Dec 2023 14:26:00 GMT (envelope-from git) Date: Mon, 25 Dec 2023 14:26:00 GMT Message-Id: <202312251426.3BPEQ0jH023792@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Robert Clausecker Subject: git: fc0e38a7a67a - main - lib/libc/amd64/string: add memccpy scalar, baseline implementation List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: Sender: owner-dev-commits-src-main@freebsd.org X-BeenThere: dev-commits-src-main@freebsd.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: fuz X-Git-Repository: src X-Git-Refname: refs/heads/main X-Git-Reftype: branch X-Git-Commit: fc0e38a7a67a6d43095efb00cf19ee5f95dcf710 Auto-Submitted: auto-generated The branch main has been updated by fuz: URL: https://cgit.FreeBSD.org/src/commit/?id=fc0e38a7a67a6d43095efb00cf19ee5f95dcf710 commit fc0e38a7a67a6d43095efb00cf19ee5f95dcf710 Author: Robert Clausecker AuthorDate: 2023-12-02 12:28:05 +0000 Commit: Robert Clausecker CommitDate: 2023-12-25 13:59:42 +0000 lib/libc/amd64/string: add memccpy scalar, baseline implementation Based on the strlcpy code from D42863, this patch adds a SIMD-enhanced implementation of memccpy for amd64. A scalar implementation calling into memchr and memcpy to do the job is provided, too. Please note that this code does not behave exactly the same as the C implementation of memccpy for overlapping inputs. However, overlapping inputs are not allowed for this function by ISO/IEC 9899:1999 and neither has the C implementation any code to deal with the possibility. It just proceeds byte-by-byte, which may or may not do the expected thing for some overlaps. We do not document whether overlapping inputs are supported in memccpy(3). Tested by: developers@, exp-run Approved by: mjg MFC after: 1 month MFC to: stable/14 PR: 275785 Differential Revision: https://reviews.freebsd.org/D42902 --- lib/libc/amd64/string/Makefile.inc | 1 + lib/libc/amd64/string/memccpy.S | 259 +++++++++++++++++++++++++++++++++++++ 2 files changed, 260 insertions(+) diff --git a/lib/libc/amd64/string/Makefile.inc b/lib/libc/amd64/string/Makefile.inc index 2b1e276cb3da..b569d2cb8be8 100644 --- a/lib/libc/amd64/string/Makefile.inc +++ b/lib/libc/amd64/string/Makefile.inc @@ -3,6 +3,7 @@ MDSRCS+= \ bcmp.S \ memchr.S \ memcmp.S \ + memccpy.S \ memcpy.S \ memmove.S \ memset.S \ diff --git a/lib/libc/amd64/string/memccpy.S b/lib/libc/amd64/string/memccpy.S new file mode 100644 index 000000000000..a2d9e33b3d36 --- /dev/null +++ b/lib/libc/amd64/string/memccpy.S @@ -0,0 +1,259 @@ +/* + * Copyright (c) 2023 The FreeBSD Foundation + * + * This software was developed by Robert Clausecker + * under sponsorship from the FreeBSD Foundation. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ''AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE + */ + +#include + +#include "amd64_archlevel.h" + +#define ALIGN_TEXT .p2align 4, 0x90 + + .weak memccpy + .set memccpy, __memccpy +ARCHFUNCS(__memccpy) + ARCHFUNC(__memccpy, scalar) + ARCHFUNC(__memccpy, baseline) +ENDARCHFUNCS(__memccpy) + +ARCHENTRY(__memccpy, scalar) + push %rbp # establish stack frame + mov %rsp, %rbp + push %rax # dummy push for alignment + push %rbx + push %rdi + push %rsi + + mov %rsi, %rdi + mov %edx, %esi + mov %rcx, %rdx + mov %rcx, %rbx + call CNAME(__memchr) # ptr = memchr(src, c, len) + + pop %rsi + pop %rdi + lea 1(%rax), %rdx + sub %rsi, %rdx # size = ptr - src + 1 + mov %rbx, %rcx + lea (%rdi, %rdx, 1), %rbx # res = dest + size + test %rax, %rax # if (ptr == NULL) + cmovz %rcx, %rdx # size = len + cmovz %rax, %rbx # res = NULL + call CNAME(memcpy) + + mov %rbx, %rax # return (res) + pop %rbx + leave + ret +ARCHEND(__memccpy, scalar) + +ARCHENTRY(__memccpy, baseline) + sub $1, %rcx # RCX refers to last character in buffer + jb .L0 # go to special code path if len was 0 + + movd %edx, %xmm4 + mov %rcx, %rdx + punpcklbw %xmm4, %xmm4 # c -> cc + mov %esi, %ecx + punpcklwd %xmm4, %xmm4 # cc -> cccc + mov %rsi, %r9 # stash a copy of the source pointer for later + pshufd $0, %xmm4, %xmm4 # cccc -> cccccccccccccccc + and $~0xf, %rsi + movdqa %xmm4, %xmm1 + pcmpeqb (%rsi), %xmm1 # NUL found in head? + mov $-1, %r8d + and $0xf, %ecx + shl %cl, %r8d # mask of bytes in the string + pmovmskb %xmm1, %eax + and %r8d, %eax + jnz .Lhead_nul + + movdqa 16(%rsi), %xmm3 # load second string chunk + movdqu (%r9), %xmm2 # load unaligned string head + mov $32, %r8d + sub %ecx, %r8d # head length + length of second chunk + movdqa %xmm4, %xmm1 + pcmpeqb %xmm3, %xmm1 # NUL found in second chunk? + + sub %r8, %rdx # enough space left for the second chunk? + jb .Lhead_buf_end + + /* process second chunk */ + pmovmskb %xmm1, %eax + test %eax, %eax + jnz .Lsecond_nul + + /* string didn't end in second chunk and neither did buffer -- not a runt! */ + movdqa 32(%rsi), %xmm0 # load next string chunk + movdqa %xmm4, %xmm1 + movdqu %xmm2, (%rdi) # deposit head into buffer + sub %rcx, %rdi # adjust RDI to correspond to RSI + movdqu %xmm3, 16(%rdi) # deposit second chunk + sub %rsi, %rdi # express RDI as distance from RSI + add $32, %rsi # advance RSI past first two chunks + sub $16, %rdx # enough left for another round? + jb 1f + + /* main loop unrolled twice */ + ALIGN_TEXT +0: pcmpeqb %xmm0, %xmm1 # NUL byte encountered? + pmovmskb %xmm1, %eax + test %eax, %eax + jnz 3f + + movdqu %xmm0, (%rsi, %rdi) + movdqa 16(%rsi), %xmm0 # load next string chunk + movdqa %xmm4, %xmm1 + cmp $16, %rdx # more than a full chunk left? + jb 2f + + add $32, %rsi # advance pointers to next chunk + pcmpeqb %xmm0, %xmm1 # NUL byte encountered? + pmovmskb %xmm1, %eax + test %eax, %eax + jnz 4f + + movdqu %xmm0, -16(%rsi, %rdi) + movdqa (%rsi), %xmm0 # load next string chunk + movdqa %xmm4, %xmm1 + sub $32, %rdx + jae 0b + +1: sub $16, %rsi # undo second advancement + add $16, %edx + + /* 1--16 bytes left in the buffer but string has not ended yet */ +2: pcmpeqb %xmm1, %xmm0 # NUL byte encountered? + pmovmskb %xmm0, %r8d + mov %r8d, %ecx + bts %edx, %r8d # treat end of buffer as end of string + or $0x10000, %eax # ensure TZCNT finds a set bit + tzcnt %r8d, %r8d # find tail length + add %rsi, %rdi # restore RDI + movdqu 1(%rsi, %r8, 1), %xmm0 # load string tail + movdqu %xmm0, 1(%rdi, %r8, 1) # store string tail + lea 17(%rdi, %r8, 1), %rsi # return value if terminator encountered + xor %eax, %eax # return value if no terminator encountered + bt %r8d, %ecx # terminator encountered inside buffer? + cmovc %rsi, %rax # if yes, return pointer, else NULL + ret + +4: sub $16, %rsi # undo second advancement + add $16, %rdx # restore number of remaining bytes + + /* string has ended but buffer has not */ +3: tzcnt %eax, %eax # find length of string tail + movdqu -15(%rsi, %rax, 1), %xmm0 # load string tail (incl. NUL) + add %rsi, %rdi # restore destination pointer + movdqu %xmm0, -15(%rdi, %rax, 1) # store string tail (incl. NUL) + lea 1(%rdi, %rax, 1), %rax # compute return value + ret + +.Lhead_buf_end: + pmovmskb %xmm1, %r8d + add $32, %edx # restore edx to (len-1) + ecx + shl $16, %r8d # place 2nd chunk NUL mask into bits 16--31 + mov %r8d, %r10d + bts %rdx, %r8 # treat end of buffer as if terminator present + xor %eax, %eax # return value if terminator not found + tzcnt %r8, %rdx # find string/buffer len from alignment boundary + lea 1(%rdi, %rdx, 1), %r8 # return value if terminator found + rcx + sub %rcx, %r8 # subtract rcx + bt %rdx, %r10 # was the terminator present? + cmovc %r8, %rax # if yes, return pointer, else NULL + sub %ecx, %edx # find actual string/buffer len + jmp .L0132 + +.Lsecond_nul: + add %r8, %rdx # restore buffer length + tzcnt %eax, %r8d # where is the NUL byte? + lea -16(%rcx), %eax + sub %eax, %r8d # string length + lea 1(%rdi, %r8, 1), %rax # return value if NUL before end of buffer + xor %ecx, %ecx # return value if not + cmp %r8, %rdx # is the string shorter than the buffer? + cmova %r8, %rdx # copy only min(buflen, srclen) bytes + cmovb %rcx, %rax # return NUL if buffer ended before string +.L0132: cmp $16, %rdx # at least 17 bytes to copy (not incl NUL)? + jb .L0116 + + /* copy 17--32 bytes */ + movdqu (%r9), %xmm0 # load first 16 bytes + movdqu -15(%r9, %rdx, 1), %xmm1 # load last 16 bytes + movdqu %xmm0, (%rdi) + movdqu %xmm1, -15(%rdi, %rdx, 1) + ret + +.Lhead_nul: + tzcnt %eax, %r8d # where is the NUL byte? + sub %ecx, %r8d # ... from the beginning of the string? + lea 1(%rdi, %r8, 1), %rax # return value if NUL before end of buffer + xor %ecx, %ecx # return value if not + cmp %r8, %rdx # is the string shorter than the buffer? + cmova %r8, %rdx # copy only min(buflen, srclen) bytes + cmovb %rcx, %rax # return NUL if buffer ended before string + + /* process strings of 1--16 bytes (rdx: min(buflen, srclen), rax: srclen) */ +.L0116: cmp $8, %rdx # at least 9 bytes to copy? + jae .L0916 + + cmp $4, %rdx # at least 5 bytes to copy? + jae .L0508 + + cmp $2, %rdx # at least 3 bytes to copy? + jae .L0304 + + /* copy one or two bytes */ + movzbl (%r9), %ecx # load first byte from src + movzbl (%r9, %rdx, 1), %esi # load last byte from src + mov %cl, (%rdi) # deposit into destination + mov %sil, (%rdi, %rdx, 1) + ret + +.L0304: movzwl (%r9), %ecx + movzwl -1(%r9, %rdx, 1), %esi + mov %cx, (%rdi) + mov %si, -1(%rdi, %rdx, 1) + ret + +.L0508: mov (%r9), %ecx + mov -3(%r9, %rdx, 1), %esi + mov %ecx, (%rdi) + mov %esi, -3(%rdi, %rdx, 1) + ret + +.L0916: mov (%r9), %rcx + mov -7(%r9, %rdx, 1), %rsi + mov %rcx, (%rdi) + mov %rsi, -7(%rdi, %rdx, 1) + ret + + /* length zero destination: return null pointer */ +.L0: xor %eax, %eax + ret +ARCHEND(__memccpy, baseline) + + .section .note.GNU-stack,"",%progbits