/*-
 * Copyright (c) 2023 The FreeBSD Foundation
 *
 * This software was developed by Robert Clausecker <fuz@FreeBSD.org>
 * 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 <machine/asm.h>
#include <machine/param.h>

#include "amd64_archlevel.h"

#define ALIGN_TEXT      .p2align 4, 0x90

ARCHFUNCS(strncmp)
        ARCHFUNC(strncmp, scalar)
        ARCHFUNC(strncmp, baseline)
ENDARCHFUNCS(strncmp)

/*
 * This is just the scalar loop unrolled a bunch of times.
 */
ARCHENTRY(strncmp, scalar)
        xor     %eax, %eax
        sub     $4, %rdx        # 4 chars left to compare?
        jbe     1f

        ALIGN_TEXT
0:      movzbl  (%rdi), %ecx
        test    %ecx, %ecx      # NUL char in first string?
        jz      .L0
        cmpb    (%rsi), %cl     # mismatch between strings?
        jnz     .L0

        movzbl  1(%rdi), %ecx
        test    %ecx, %ecx
        jz      .L1
        cmpb    1(%rsi), %cl
        jnz     .L1

        movzbl  2(%rdi), %ecx
        test    %ecx, %ecx
        jz      .L2
        cmpb    2(%rsi), %cl
        jnz     .L2

        movzbl  3(%rdi), %ecx
        test    %ecx, %ecx
        jz      .L3
        cmpb    3(%rsi), %cl
        jnz     .L3

        add     $4, %rdi        # advance to next iteration
        add     $4, %rsi
        sub     $4, %rdx
        ja      0b

        /* end of string within the next 4 characters */
1:      cmp     $-4, %edx       # end of string reached immediately?
        jz      .Leq
        movzbl  (%rdi), %ecx
        test    %ecx, %ecx
        jz      .L0
        cmpb    (%rsi), %cl
        jnz     .L0

        cmp     $-3, %edx       # end of string reached after 1 char?
        jz      .Leq
        movzbl  1(%rdi), %ecx
        test    %ecx, %ecx
        jz      .L1
        cmpb    1(%rsi), %cl
        jnz     .L1

        cmp     $-2, %edx
        jz      .Leq
        movzbl  2(%rdi), %ecx
        test    %ecx, %ecx
        jz      .L2
        cmpb    2(%rsi), %cl
        jnz     .L2

        cmp     $-1, %edx       # either end of string after 3 chars,
        jz      .Leq            # or it boils down to the last char

.L3:    inc     %eax
.L2:    inc     %eax
.L1:    inc     %eax
.L0:    movzbl  (%rsi, %rax, 1), %ecx
        movzbl  (%rdi, %rax, 1), %eax
        sub     %ecx, %eax
.Leq:   ret
ARCHEND(strncmp, scalar)

ARCHENTRY(strncmp, baseline)
        push            %rbx
        sub             $1, %rdx        # RDX--, so RDX points to the last byte to compare
        jb              .Lempty         # where there any bytes to compare at all?

        lea             15(%rdi), %r8d  # end of head
        lea             15(%rsi), %r9d
        mov             %edi, %eax
        mov             %esi, %ebx
        xor             %edi, %r8d      # bits that changed between first and last byte
        xor             %esi, %r9d
        and             $~0xf, %rdi     # align heads to 16 bytes
        and             $~0xf, %rsi
        or              %r8d, %r9d
        and             $0xf, %eax      # offset from alignment
        and             $0xf, %ebx
        movdqa          (%rdi), %xmm0   # load aligned heads
        movdqa          (%rsi), %xmm2
        pxor            %xmm1, %xmm1
        cmp             $16, %rdx       # end of buffer within the first 32 bytes?
        jb              .Llt16

        test            $PAGE_SIZE, %r9d # did the page change?
        jz              0f              # if not, take fast path


        /* heads may cross page boundary, avoid unmapped loads */
        movdqa          %xmm0, -32(%rsp) # stash copies of the heads on the stack
        movdqa          %xmm2, -16(%rsp)
        mov             $-1, %r8d
        mov             $-1, %r9d
        mov             %eax, %ecx
        shl             %cl, %r8d       # string head in XMM0
        mov             %ebx, %ecx
        shl             %cl, %r9d       # string head in XMM2
        pcmpeqb         %xmm1, %xmm0
        pcmpeqb         %xmm1, %xmm2
        pmovmskb        %xmm0, %r10d
        pmovmskb        %xmm2, %r11d
        test            %r8d, %r10d     # NUL byte present in first string?
        lea             -32(%rsp), %r8
        cmovz           %rdi, %r8
        test            %r9d, %r11d     # NUL byte present in second string?
        lea             -16(%rsp), %r9
        cmovz           %rsi, %r9
        movdqu          (%r8, %rax, 1), %xmm0 # load true (or fake) heads
        movdqu          (%r9, %rbx, 1), %xmm4
        jmp             1f

        /* rdx == 0 */
.Lempty:
        xor             %eax, %eax      # zero-length buffers compare equal
        pop             %rbx
        ret

0:      movdqu          (%rdi, %rax, 1), %xmm0 # load true heads
        movdqu          (%rsi, %rbx, 1), %xmm4
1:      pxor            %xmm2, %xmm2
        pcmpeqb         %xmm0, %xmm2    # NUL byte present?
        pcmpeqb         %xmm0, %xmm4    # which bytes match?
        pandn           %xmm4, %xmm2    # match and not NUL byte?
        pmovmskb        %xmm2, %r9d
        xor             $0xffff, %r9d   # mismatch or NUL byte?
        jnz             .Lhead_mismatch

        /* load head and second chunk */
        movdqa          16(%rdi), %xmm2 # load second chunks
        movdqa          16(%rsi), %xmm3
        lea             -16(%rdx, %rbx, 1), %rdx # account for length of RSI chunk
        sub             %rbx, %rax      # is a&0xf >= b&0xf?
        jb              .Lswapped       # if not, proceed with swapped operands
        jmp             .Lnormal

        /* buffer ends within the first 16 bytes */
.Llt16: test            $PAGE_SIZE, %r9d # did the page change?
        jz              0f              # if not, take fast path

        /* heads may cross page boundary */
        movdqa          %xmm0, -32(%rsp) # stash copies of the heads on the stack
        movdqa          %xmm2, -16(%rsp)
        mov             $-1, %r8d
        mov             $-1, %r9d
        mov             %eax, %ecx
        shl             %cl, %r8d       # string head in XMM0
        mov             %ebx, %ecx
        shl             %cl, %r9d       # string head in XMM2
        pcmpeqb         %xmm1, %xmm0
        pcmpeqb         %xmm1, %xmm2
        pmovmskb        %xmm0, %r10d
        pmovmskb        %xmm2, %r11d
        lea             (%rdx, %rax, 1), %ecx # location of last buffer byte in xmm0
        bts             %ecx, %r10d     # treat as if NUL byte present
        lea             (%rdx, %rbx, 1), %ecx
        bts             %ecx, %r11d
        test            %r8w, %r10w     # NUL byte present in first string head?
        lea             -32(%rsp), %r8
        cmovz           %rdi, %r8
        test            %r9w, %r11w     # NUL byte present in second string head?
        lea             -16(%rsp), %r9
        cmovz           %rsi, %r9
        movdqu          (%r8, %rax, 1), %xmm0 # load true (or fake) heads
        movdqu          (%r9, %rbx, 1), %xmm4
        jmp             1f

0:      movdqu          (%rdi, %rax, 1), %xmm0 # load true heads
        movdqu          (%rsi, %rbx, 1), %xmm4
1:      pxor            %xmm2, %xmm2
        pcmpeqb         %xmm0, %xmm2    # NUL byte present?
        pcmpeqb         %xmm0, %xmm4    # which bytes match?
        pandn           %xmm4, %xmm2    # match and not NUL byte?
        pmovmskb        %xmm2, %r9d
        btr             %edx, %r9d      # induce mismatch in last byte of buffer
        not             %r9d            # mismatch or NUL byte?

        /* mismatch in true heads */
        ALIGN_TEXT
.Lhead_mismatch:
        tzcnt           %r9d, %r9d      # where is the mismatch?
        add             %rax, %rdi      # return to true heads
        add             %rbx, %rsi
        movzbl          (%rdi, %r9, 1), %eax # mismatching characters
        movzbl          (%rsi, %r9, 1), %ecx
        sub             %ecx, %eax
        pop             %rbx
        ret

        /* rax >= 0 */
        ALIGN_TEXT
.Lnormal:
        neg             %rax
        movdqu          16(%rsi, %rax, 1), %xmm0
        sub             %rdi, %rsi      # express RSI as distance from RDI
        lea             (%rsi, %rax, 1), %rbx # point RBX to offset in second string
        neg             %rax            # ... corresponding to RDI
        pcmpeqb         %xmm3, %xmm1    # NUL present?
        pcmpeqb         %xmm2, %xmm0    # Mismatch between chunks?
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        mov             $16, %ecx
        cmp             %rcx, %rdx      # does the buffer end within (RDI,RSI,1)?
        cmovb           %edx, %ecx      # ECX = min(16, RDX)
        add             $32, %rdi       # advance to next iteration
        bts             %ecx, %r8d      # mark end-of-buffer as if there was a NUL byte
        test            %r8w, %r8w      # NUL or end of buffer found?
        jnz             .Lnul_found2
        xor             $0xffff, %r9d
        jnz             .Lmismatch2
        sub             $48, %rdx       # end of buffer within first main loop iteration?
        jb              .Ltail          # if yes, process tail

        /*
         * During the main loop, the layout of the two strings is something like:
         *
         *          v ------1------ v ------2------ v
         *     RDI:    AAAAAAAAAAAAABBBBBBBBBBBBBBBB...
         *     RSI: AAAAAAAAAAAAABBBBBBBBBBBBBBBBCCC...
         *
         * where v indicates the alignment boundaries and corresponding chunks
         * of the strings have the same letters.  Chunk A has been checked in
         * the previous iteration.  This iteration, we first check that string
         * RSI doesn't end within region 2, then we compare chunk B between the
         * two strings.  As RSI is known not to hold a NUL byte in regsions 1
         * and 2 at this point, this also ensures that RDI has not ended yet.
         */
        ALIGN_TEXT
0:      movdqu          (%rdi, %rbx, 1), %xmm0 # chunk of 2nd string corresponding to RDI
        pxor            %xmm1, %xmm1
        pcmpeqb         (%rdi, %rsi, 1), %xmm1 # end of string in RSI?
        pcmpeqb         (%rdi), %xmm0   # where do the chunks match?
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        test            %r8d, %r8d
        jnz             .Lnul_found
        xor             $0xffff, %r9d   # any mismatches?
        jnz             .Lmismatch

        /* main loop unrolled twice */
        movdqu          16(%rdi, %rbx, 1), %xmm0
        pxor            %xmm1, %xmm1
        pcmpeqb         16(%rdi, %rsi, 1), %xmm1
        pcmpeqb         16(%rdi), %xmm0
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        add             $32, %rdi
        test            %r8d, %r8d
        jnz             .Lnul_found2
        xor             $0xffff, %r9d
        jnz             .Lmismatch2
        sub             $32, %rdx       # end of buffer within next iteration?
        jae             0b

        /* end of buffer will occur in next 32 bytes */
.Ltail: movdqu          (%rdi, %rbx, 1), %xmm0 # chunk of 2nd string corresponding to RDI
        pxor            %xmm1, %xmm1
        pcmpeqb         (%rdi, %rsi, 1), %xmm1 # end of string in RSI?
        pcmpeqb         (%rdi), %xmm0   # where do the chunks match?
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        bts             %edx, %r8d      # indicate NUL byte at last byte in buffer
        test            %r8w, %r8w      # NUL byte in first chunk?
        jnz             .Lnul_found
        xor             $0xffff, %r9d   # any mismatches?
        jnz             .Lmismatch

        /* main loop unrolled twice */
        movdqu          16(%rdi, %rbx, 1), %xmm0
        pxor            %xmm1, %xmm1
        pcmpeqb         16(%rdi, %rsi, 1), %xmm1
        pcmpeqb         16(%rdi), %xmm0
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        sub             $16, %edx       # take first half into account
        bts             %edx, %r8d      # indicate NUL byte at last byte in buffer
        add             $32, %rdi

.Lnul_found2:
        sub             $16, %rdi

.Lnul_found:
        mov             %eax, %ecx
        mov             %r8d, %r10d
        shl             %cl, %r8d       # adjust NUL mask to positions in RDI/RBX
        not             %r9d            # mask of mismatches
        or              %r8w, %r9w      # NUL bytes als count as mismatches
        jnz             .Lmismatch

        /*
         * (RDI) == (RSI) and NUL is past the string.
         * compare (RSI) with the corresponding part
         * of the other string until the NUL byte.
         */
        movdqu          (%rdi, %rax, 1), %xmm0
        pcmpeqb         (%rdi, %rsi, 1), %xmm0
        add             %rdi, %rsi      # restore RSI pointer
        add             %rax, %rdi      # point RDI to chunk corresponding to (RSI)
        pmovmskb        %xmm0, %ecx     # mask of matches
        not             %ecx            # mask of mismatches
        or              %r10d, %ecx     # mask of mismatches or NUL bytes
        tzcnt           %ecx, %ecx      # location of first mismatch
        movzbl          (%rdi, %rcx, 1), %eax
        movzbl          (%rsi, %rcx, 1), %ecx
        sub             %ecx, %eax
        pop             %rbx
        ret

.Lmismatch2:
        sub             $16, %rdi

        /* a mismatch has been found between RBX and RSI */
.Lmismatch:
        tzcnt           %r9d, %r9d      # where is the mismatch?
        add             %rdi, %rbx      # turn RBX from offset into pointer
        movzbl          (%rbx, %r9, 1), %ecx
        movzbl          (%rdi, %r9, 1), %eax
        sub             %ecx, %eax
        pop             %rbx
        ret

        /* rax < 0 */
        ALIGN_TEXT
.Lswapped:
        movdqu          16(%rdi, %rax, 1), %xmm0
        sub             %rsi, %rdi      # express RDI as distance from RDI
        lea             (%rdi, %rax, 1), %rbx # point RBX to offset in first string
        pcmpeqb         %xmm2, %xmm1    # NUL present?
        pcmpeqb         %xmm3, %xmm0    # mismatch between chunks?
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        add             %rax, %rdx      # RDX points to buffer end in RSI
        neg             %rax            # ... corresponding to RSI
        mov             $16, %ecx
        cmp             %rcx, %rdx      # does the buffer end within (RSI,RDI,1)?
        cmovb           %edx, %ecx      # ECX = min(16, RDX)
        add             $32, %rsi
        bts             %ecx, %r8d      # mark end-of-buffer as if there was a NUL byte
        test            %r8w, %r8w      # NUL or end of buffer found?
        jnz             .Lnul_found2s
        xor             $0xffff, %r9d
        jnz             .Lmismatch2s
        sub             $48, %rdx       # end of buffer within first main loop iteration?
        jb              .Ltails         # if yes, process tail

        ALIGN_TEXT
0:      movdqu          (%rsi, %rbx, 1), %xmm0 # chunk of 1st string corresponding to RSI
        pxor            %xmm1, %xmm1
        pcmpeqb         (%rsi, %rdi, 1), %xmm1 # end of string in RDI?
        pcmpeqb         (%rsi), %xmm0   # where do the chunks match?
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        test            %r8d, %r8d
        jnz             .Lnul_founds
        xor             $0xffff, %r9d   # any mismatches?
        jnz             .Lmismatchs

        /* main loop unrolled twice */
        movdqu          16(%rsi, %rbx, 1), %xmm0
        pxor            %xmm1, %xmm1
        pcmpeqb         16(%rsi, %rdi, 1), %xmm1
        pcmpeqb         16(%rsi), %xmm0
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        add             $32, %rsi
        test            %r8d, %r8d
        jnz             .Lnul_found2s
        xor             $0xffff, %r9d
        jnz             .Lmismatch2s
        sub             $32, %rdx       # end of buffer within next iteration?
        jae             0b

        /* end of buffer will occur in next 32 bytes */
.Ltails:
        movdqu          (%rsi, %rbx, 1), %xmm0 # chunk of 1st string corresponding to RSI
        pxor            %xmm1, %xmm1
        pcmpeqb         (%rsi, %rdi, 1), %xmm1 # end of string in RDI?
        pcmpeqb         (%rsi), %xmm0   # where do the chunks match?
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        bts             %edx, %r8d      # indicate NUL byte at laste byte in buffer
        test            %r8w, %r8w      # NUL byte in first chunk?
        jnz             .Lnul_founds
        xor             $0xffff, %r9d   # any mismatches?
        jnz             .Lmismatchs

        /* main loop unrolled twice */
        movdqu          16(%rsi, %rbx, 1), %xmm0
        pxor            %xmm1, %xmm1
        pcmpeqb         16(%rsi, %rdi, 1), %xmm1
        pcmpeqb         16(%rsi), %xmm0
        pmovmskb        %xmm1, %r8d
        pmovmskb        %xmm0, %r9d
        sub             $16, %edx       # take first half into account
        bts             %edx, %r8d      # indicate NUL byte at laste byte in buffer
        add             $32, %rsi

.Lnul_found2s:
        sub             $16, %rsi

.Lnul_founds:
        mov             %eax, %ecx
        mov             %r8d, %r10d
        shl             %cl, %r8d       # adjust NUL mask to positions in RSI/RBX
        not             %r9d            # mask of mismatches
        or              %r8w, %r9w      # NUL bytes also count as mismatches
        jnz             .Lmismatchs

        movdqu          (%rsi, %rax, 1), %xmm0
        pcmpeqb         (%rsi, %rdi, 1), %xmm0
        add             %rsi, %rdi      # restore RDI pointer
        add             %rax, %rsi      # point RSI to chunk corresponding to (RDI)
        pmovmskb        %xmm0, %ecx     # mask of matches
        not             %ecx            # mask of mismatches
        or              %r10d, %ecx     # mask of mismatches or NUL bytes
        tzcnt           %ecx, %ecx      # location of first mismatch
        movzbl          (%rdi, %rcx, 1), %eax
        movzbl          (%rsi, %rcx, 1), %ecx
        sub             %ecx, %eax
        pop             %rbx
        ret

.Lmismatch2s:
        sub             $16, %rsi

.Lmismatchs:
        tzcnt           %r9d, %r9d      # where is the mismatch?
        add             %rsi, %rbx      # turn RBX from offset into pointer
        movzbl          (%rbx, %r9, 1), %eax
        movzbl          (%rsi, %r9, 1), %ecx
        sub             %ecx, %eax
        pop             %rbx
        ret
ARCHEND(strncmp, baseline)

        .section .note.GNU-stack,"",%progbits