| ; LzFindOpt.asm -- ASM version of GetMatchesSpecN_2() function |
| ; 2024-06-18: Igor Pavlov : Public domain |
| ; |
| |
| ifndef x64 |
| ; x64=1 |
| ; .err <x64_IS_REQUIRED> |
| endif |
| |
| include 7zAsm.asm |
| |
| MY_ASM_START |
| |
| ifndef Z7_LZ_FIND_OPT_ASM_USE_SEGMENT |
| if (IS_LINUX gt 0) |
| Z7_LZ_FIND_OPT_ASM_USE_SEGMENT equ 1 |
| else |
| Z7_LZ_FIND_OPT_ASM_USE_SEGMENT equ 1 |
| endif |
| endif |
| |
| ifdef Z7_LZ_FIND_OPT_ASM_USE_SEGMENT |
| _TEXT$LZFINDOPT SEGMENT ALIGN(64) 'CODE' |
| MY_ALIGN macro num:req |
| align num |
| ; align 16 |
| endm |
| else |
| MY_ALIGN macro num:req |
| ; We expect that ".text" is aligned for 16-bytes. |
| ; So we don't need large alignment inside our function. |
| align 16 |
| endm |
| endif |
| |
| |
| MY_ALIGN_16 macro |
| MY_ALIGN 16 |
| endm |
| |
| MY_ALIGN_32 macro |
| MY_ALIGN 32 |
| endm |
| |
| MY_ALIGN_64 macro |
| MY_ALIGN 64 |
| endm |
| |
| |
| t0_L equ x0_L |
| t0_x equ x0 |
| t0 equ r0 |
| t1_x equ x3 |
| t1 equ r3 |
| |
| cp_x equ t1_x |
| cp_r equ t1 |
| m equ x5 |
| m_r equ r5 |
| len_x equ x6 |
| len equ r6 |
| diff_x equ x7 |
| diff equ r7 |
| len0 equ r10 |
| len1_x equ x11 |
| len1 equ r11 |
| maxLen_x equ x12 |
| maxLen equ r12 |
| d equ r13 |
| ptr0 equ r14 |
| ptr1 equ r15 |
| |
| d_lim equ m_r |
| cycSize equ len_x |
| hash_lim equ len0 |
| delta1_x equ len1_x |
| delta1_r equ len1 |
| delta_x equ maxLen_x |
| delta_r equ maxLen |
| hash equ ptr0 |
| src equ ptr1 |
| |
| |
| |
| if (IS_LINUX gt 0) |
| |
| ; r1 r2 r8 r9 : win32 |
| ; r7 r6 r2 r1 r8 r9 : linux |
| |
| lenLimit equ r8 |
| lenLimit_x equ x8 |
| ; pos_r equ r2 |
| pos equ x2 |
| cur equ r1 |
| son equ r9 |
| |
| else |
| |
| lenLimit equ REG_ABI_PARAM_2 |
| lenLimit_x equ REG_ABI_PARAM_2_x |
| pos equ REG_ABI_PARAM_1_x |
| cur equ REG_ABI_PARAM_0 |
| son equ REG_ABI_PARAM_3 |
| |
| endif |
| |
| |
| if (IS_LINUX gt 0) |
| maxLen_OFFS equ (REG_SIZE * (6 + 1)) |
| else |
| cutValue_OFFS equ (REG_SIZE * (8 + 1 + 4)) |
| d_OFFS equ (REG_SIZE + cutValue_OFFS) |
| maxLen_OFFS equ (REG_SIZE + d_OFFS) |
| endif |
| hash_OFFS equ (REG_SIZE + maxLen_OFFS) |
| limit_OFFS equ (REG_SIZE + hash_OFFS) |
| size_OFFS equ (REG_SIZE + limit_OFFS) |
| cycPos_OFFS equ (REG_SIZE + size_OFFS) |
| cycSize_OFFS equ (REG_SIZE + cycPos_OFFS) |
| posRes_OFFS equ (REG_SIZE + cycSize_OFFS) |
| |
| if (IS_LINUX gt 0) |
| else |
| cutValue_PAR equ [r0 + cutValue_OFFS] |
| d_PAR equ [r0 + d_OFFS] |
| endif |
| maxLen_PAR equ [r0 + maxLen_OFFS] |
| hash_PAR equ [r0 + hash_OFFS] |
| limit_PAR equ [r0 + limit_OFFS] |
| size_PAR equ [r0 + size_OFFS] |
| cycPos_PAR equ [r0 + cycPos_OFFS] |
| cycSize_PAR equ [r0 + cycSize_OFFS] |
| posRes_PAR equ [r0 + posRes_OFFS] |
| |
| |
| cutValue_VAR equ DWORD PTR [r4 + 8 * 0] |
| cutValueCur_VAR equ DWORD PTR [r4 + 8 * 0 + 4] |
| cycPos_VAR equ DWORD PTR [r4 + 8 * 1 + 0] |
| cycSize_VAR equ DWORD PTR [r4 + 8 * 1 + 4] |
| hash_VAR equ QWORD PTR [r4 + 8 * 2] |
| limit_VAR equ QWORD PTR [r4 + 8 * 3] |
| size_VAR equ QWORD PTR [r4 + 8 * 4] |
| distances equ QWORD PTR [r4 + 8 * 5] |
| maxLen_VAR equ QWORD PTR [r4 + 8 * 6] |
| |
| Old_RSP equ QWORD PTR [r4 + 8 * 7] |
| LOCAL_SIZE equ 8 * 8 |
| |
| COPY_VAR_32 macro dest_var, src_var |
| mov x3, src_var |
| mov dest_var, x3 |
| endm |
| |
| COPY_VAR_64 macro dest_var, src_var |
| mov r3, src_var |
| mov dest_var, r3 |
| endm |
| |
| |
| ifdef Z7_LZ_FIND_OPT_ASM_USE_SEGMENT |
| ; MY_ALIGN_64 |
| else |
| MY_ALIGN_16 |
| endif |
| MY_PROC GetMatchesSpecN_2, 13 |
| MY_PUSH_PRESERVED_ABI_REGS |
| mov r0, RSP |
| lea r3, [r0 - LOCAL_SIZE] |
| and r3, -64 |
| mov RSP, r3 |
| mov Old_RSP, r0 |
| |
| if (IS_LINUX gt 0) |
| mov d, REG_ABI_PARAM_5 ; r13 = r9 |
| mov cutValue_VAR, REG_ABI_PARAM_4_x ; = r8 |
| mov son, REG_ABI_PARAM_3 ; r9 = r1 |
| mov r8, REG_ABI_PARAM_2 ; r8 = r2 |
| mov pos, REG_ABI_PARAM_1_x ; r2 = x6 |
| mov r1, REG_ABI_PARAM_0 ; r1 = r7 |
| else |
| COPY_VAR_32 cutValue_VAR, cutValue_PAR |
| mov d, d_PAR |
| endif |
| |
| COPY_VAR_64 limit_VAR, limit_PAR |
| |
| mov hash_lim, size_PAR |
| mov size_VAR, hash_lim |
| |
| mov cp_x, cycPos_PAR |
| mov hash, hash_PAR |
| |
| mov cycSize, cycSize_PAR |
| mov cycSize_VAR, cycSize |
| |
| ; we want cur in (rcx). So we change the cur and lenLimit variables |
| sub lenLimit, cur |
| neg lenLimit_x |
| inc lenLimit_x |
| |
| mov t0_x, maxLen_PAR |
| sub t0, lenLimit |
| mov maxLen_VAR, t0 |
| |
| jmp main_loop |
| |
| MY_ALIGN_64 |
| fill_empty: |
| ; ptr0 = *ptr1 = kEmptyHashValue; |
| mov QWORD PTR [ptr1], 0 |
| inc pos |
| inc cp_x |
| mov DWORD PTR [d - 4], 0 |
| cmp d, limit_VAR |
| jae fin |
| cmp hash, hash_lim |
| je fin |
| |
| ; MY_ALIGN_64 |
| main_loop: |
| ; UInt32 delta = *hash++; |
| mov diff_x, [hash] ; delta |
| add hash, 4 |
| ; mov cycPos_VAR, cp_x |
| |
| inc cur |
| add d, 4 |
| mov m, pos |
| sub m, diff_x; ; matchPos |
| |
| ; CLzRef *ptr1 = son + ((size_t)(pos) << 1) - CYC_TO_POS_OFFSET * 2; |
| lea ptr1, [son + 8 * cp_r] |
| ; mov cycSize, cycSize_VAR |
| cmp pos, cycSize |
| jb directMode ; if (pos < cycSize_VAR) |
| |
| ; CYC MODE |
| |
| cmp diff_x, cycSize |
| jae fill_empty ; if (delta >= cycSize_VAR) |
| |
| xor t0_x, t0_x |
| mov cycPos_VAR, cp_x |
| sub cp_x, diff_x |
| ; jae prepare_for_tree_loop |
| ; add cp_x, cycSize |
| cmovb t0_x, cycSize |
| add cp_x, t0_x ; cp_x += (cycPos < delta ? cycSize : 0) |
| jmp prepare_for_tree_loop |
| |
| |
| directMode: |
| cmp diff_x, pos |
| je fill_empty ; if (delta == pos) |
| jae fin_error ; if (delta >= pos) |
| |
| mov cycPos_VAR, cp_x |
| mov cp_x, m |
| |
| prepare_for_tree_loop: |
| mov len0, lenLimit |
| mov hash_VAR, hash |
| ; CLzRef *ptr0 = son + ((size_t)(pos) << 1) - CYC_TO_POS_OFFSET * 2 + 1; |
| lea ptr0, [ptr1 + 4] |
| ; UInt32 *_distances = ++d; |
| mov distances, d |
| |
| neg len0 |
| mov len1, len0 |
| |
| mov t0_x, cutValue_VAR |
| mov maxLen, maxLen_VAR |
| mov cutValueCur_VAR, t0_x |
| |
| MY_ALIGN_32 |
| tree_loop: |
| neg diff |
| mov len, len0 |
| cmp len1, len0 |
| cmovb len, len1 ; len = (len1 < len0 ? len1 : len0); |
| add diff, cur |
| |
| mov t0_x, [son + cp_r * 8] ; prefetch |
| movzx t0_x, BYTE PTR [diff + 1 * len] |
| lea cp_r, [son + cp_r * 8] |
| cmp [cur + 1 * len], t0_L |
| je matched_1 |
| |
| jb left_0 |
| |
| mov [ptr1], m |
| mov m, [cp_r + 4] |
| lea ptr1, [cp_r + 4] |
| sub diff, cur ; FIX32 |
| jmp next_node |
| |
| MY_ALIGN_32 |
| left_0: |
| mov [ptr0], m |
| mov m, [cp_r] |
| mov ptr0, cp_r |
| sub diff, cur ; FIX32 |
| ; jmp next_node |
| |
| ; ------------ NEXT NODE ------------ |
| ; MY_ALIGN_32 |
| next_node: |
| mov cycSize, cycSize_VAR |
| dec cutValueCur_VAR |
| je finish_tree |
| |
| add diff_x, pos ; prev_match = pos + diff |
| cmp m, diff_x |
| jae fin_error ; if (new_match >= prev_match) |
| |
| mov diff_x, pos |
| sub diff_x, m ; delta = pos - new_match |
| cmp pos, cycSize |
| jae cyc_mode_2 ; if (pos >= cycSize) |
| |
| mov cp_x, m |
| test m, m |
| jne tree_loop ; if (m != 0) |
| |
| finish_tree: |
| ; ptr0 = *ptr1 = kEmptyHashValue; |
| mov DWORD PTR [ptr0], 0 |
| mov DWORD PTR [ptr1], 0 |
| |
| inc pos |
| |
| ; _distances[-1] = (UInt32)(d - _distances); |
| mov t0, distances |
| mov t1, d |
| sub t1, t0 |
| shr t1_x, 2 |
| mov [t0 - 4], t1_x |
| |
| cmp d, limit_VAR |
| jae fin ; if (d >= limit) |
| |
| mov cp_x, cycPos_VAR |
| mov hash, hash_VAR |
| mov hash_lim, size_VAR |
| inc cp_x |
| cmp hash, hash_lim |
| jne main_loop ; if (hash != size) |
| jmp fin |
| |
| |
| MY_ALIGN_32 |
| cyc_mode_2: |
| cmp diff_x, cycSize |
| jae finish_tree ; if (delta >= cycSize) |
| |
| mov cp_x, cycPos_VAR |
| xor t0_x, t0_x |
| sub cp_x, diff_x ; cp_x = cycPos - delta |
| cmovb t0_x, cycSize |
| add cp_x, t0_x ; cp_x += (cycPos < delta ? cycSize : 0) |
| jmp tree_loop |
| |
| |
| MY_ALIGN_32 |
| matched_1: |
| |
| inc len |
| ; cmp len_x, lenLimit_x |
| je short lenLimit_reach |
| movzx t0_x, BYTE PTR [diff + 1 * len] |
| cmp [cur + 1 * len], t0_L |
| jne mismatch |
| |
| |
| MY_ALIGN_32 |
| match_loop: |
| ; while (++len != lenLimit) (len[diff] != len[0]) ; |
| |
| inc len |
| ; cmp len_x, lenLimit_x |
| je short lenLimit_reach |
| movzx t0_x, BYTE PTR [diff + 1 * len] |
| cmp BYTE PTR [cur + 1 * len], t0_L |
| je match_loop |
| |
| mismatch: |
| jb left_2 |
| |
| mov [ptr1], m |
| mov m, [cp_r + 4] |
| lea ptr1, [cp_r + 4] |
| mov len1, len |
| |
| jmp max_update |
| |
| MY_ALIGN_32 |
| left_2: |
| mov [ptr0], m |
| mov m, [cp_r] |
| mov ptr0, cp_r |
| mov len0, len |
| |
| max_update: |
| sub diff, cur ; restore diff |
| |
| cmp maxLen, len |
| jae next_node |
| |
| mov maxLen, len |
| add len, lenLimit |
| mov [d], len_x |
| mov t0_x, diff_x |
| not t0_x |
| mov [d + 4], t0_x |
| add d, 8 |
| |
| jmp next_node |
| |
| |
| |
| MY_ALIGN_32 |
| lenLimit_reach: |
| |
| mov delta_r, cur |
| sub delta_r, diff |
| lea delta1_r, [delta_r - 1] |
| |
| mov t0_x, [cp_r] |
| mov [ptr1], t0_x |
| mov t0_x, [cp_r + 4] |
| mov [ptr0], t0_x |
| |
| mov [d], lenLimit_x |
| mov [d + 4], delta1_x |
| add d, 8 |
| |
| ; _distances[-1] = (UInt32)(d - _distances); |
| mov t0, distances |
| mov t1, d |
| sub t1, t0 |
| shr t1_x, 2 |
| mov [t0 - 4], t1_x |
| |
| mov hash, hash_VAR |
| mov hash_lim, size_VAR |
| |
| inc pos |
| mov cp_x, cycPos_VAR |
| inc cp_x |
| |
| mov d_lim, limit_VAR |
| mov cycSize, cycSize_VAR |
| ; if (hash == size || *hash != delta || lenLimit[diff] != lenLimit[0] || d >= limit) |
| ; break; |
| cmp hash, hash_lim |
| je fin |
| cmp d, d_lim |
| jae fin |
| cmp delta_x, [hash] |
| jne main_loop |
| movzx t0_x, BYTE PTR [diff] |
| cmp [cur], t0_L |
| jne main_loop |
| |
| ; jmp main_loop ; bypass for debug |
| |
| mov cycPos_VAR, cp_x |
| shl len, 3 ; cycSize * 8 |
| sub diff, cur ; restore diff |
| xor t0_x, t0_x |
| cmp cp_x, delta_x ; cmp (cycPos_VAR, delta) |
| lea cp_r, [son + 8 * cp_r] ; dest |
| lea src, [cp_r + 8 * diff] |
| cmovb t0, len ; t0 = (cycPos_VAR < delta ? cycSize * 8 : 0) |
| add src, t0 |
| add len, son ; len = son + cycSize * 8 |
| |
| |
| MY_ALIGN_32 |
| long_loop: |
| add hash, 4 |
| |
| ; *(UInt64 *)(void *)ptr = ((const UInt64 *)(const void *)ptr)[diff]; |
| |
| mov t0, [src] |
| add src, 8 |
| mov [cp_r], t0 |
| add cp_r, 8 |
| cmp src, len |
| cmove src, son ; if end of (son) buffer is reached, we wrap to begin |
| |
| mov DWORD PTR [d], 2 |
| mov [d + 4], lenLimit_x |
| mov [d + 8], delta1_x |
| add d, 12 |
| |
| inc cur |
| |
| cmp hash, hash_lim |
| je long_footer |
| cmp delta_x, [hash] |
| jne long_footer |
| movzx t0_x, BYTE PTR [diff + 1 * cur] |
| cmp [cur], t0_L |
| jne long_footer |
| cmp d, d_lim |
| jb long_loop |
| |
| long_footer: |
| sub cp_r, son |
| shr cp_r, 3 |
| add pos, cp_x |
| sub pos, cycPos_VAR |
| mov cycSize, cycSize_VAR |
| |
| cmp d, d_lim |
| jae fin |
| cmp hash, hash_lim |
| jne main_loop |
| jmp fin |
| |
| |
| |
| fin_error: |
| xor d, d |
| |
| fin: |
| mov RSP, Old_RSP |
| mov t0, [r4 + posRes_OFFS] |
| mov [t0], pos |
| mov r0, d |
| |
| MY_POP_PRESERVED_ABI_REGS |
| MY_ENDP |
| |
| ifdef Z7_LZ_FIND_OPT_ASM_USE_SEGMENT |
| _TEXT$LZFINDOPT ENDS |
| endif |
| |
| end |
