gcd_11.asm revision 1.1
1 dnl x86 mpn_gcd_11 optimised for processors with slow BSF. 2 3 dnl Based on C version. 4 5 dnl Copyright 2019 Free Software Foundation, Inc. 6 7 dnl This file is part of the GNU MP Library. 8 dnl 9 dnl The GNU MP Library is free software; you can redistribute it and/or modify 10 dnl it under the terms of either: 11 dnl 12 dnl * the GNU Lesser General Public License as published by the Free 13 dnl Software Foundation; either version 3 of the License, or (at your 14 dnl option) any later version. 15 dnl 16 dnl or 17 dnl 18 dnl * the GNU General Public License as published by the Free Software 19 dnl Foundation; either version 2 of the License, or (at your option) any 20 dnl later version. 21 dnl 22 dnl or both in parallel, as here. 23 dnl 24 dnl The GNU MP Library is distributed in the hope that it will be useful, but 25 dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 26 dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 27 dnl for more details. 28 dnl 29 dnl You should have received copies of the GNU General Public License and the 30 dnl GNU Lesser General Public License along with the GNU MP Library. If not, 31 dnl see https://www.gnu.org/licenses/. 32 33 include(`../config.m4') 34 35 dnl Rudimentary code for x86-32, i.e. for CPUs without cmov. Also, the bsf 36 dnl instruction is assumed to be so slow it is useless. Instead a teble is 37 dnl used. 38 dnl 39 dnl The loop benefits from OoO, in-order CPUs might want a different loop. 40 dnl The ebx and ecx registers could be combined if the assigment of ecx were 41 dnl postponed until ebx died, but that would at least hurt in-order CPUs. 42 43 C cycles/bit (approx) 44 C AMD K7 ? 45 C AMD K8,K9 ? 46 C AMD K10 ? 47 C AMD bd1 ? 48 C AMD bd2 ? 49 C AMD bd3 ? 50 C AMD bd4 ? 51 C AMD bt1 ? 52 C AMD bt2 ? 53 C AMD zn1 ? 54 C AMD zn2 ? 55 C Intel P4-2 ? 56 C Intel P4-3/4 ? 57 C Intel P6/13 ? 58 C Intel CNR ? 59 C Intel NHM ? 60 C Intel SBR ? 61 C Intel IBR ? 62 C Intel HWL ? 63 C Intel BWL ? 64 C Intel SKL ? 65 C Intel atom ? 66 C Intel SLM ? 67 C Intel GLM ? 68 C Intel GLM+ ? 69 C VIA nano ? 70 C Numbers measured with: speed -CD -s8-32 -t24 mpn_gcd_1 71 72 deflit(MAXSHIFT, 6) 73 deflit(MASK, eval((m4_lshift(1,MAXSHIFT))-1)) 74 75 DEF_OBJECT(ctz_table,64) 76 .byte MAXSHIFT 77 forloop(i,1,MASK, 78 ` .byte m4_count_trailing_zeros(i) 79 ') 80 END_OBJECT(ctz_table) 81 82 define(`u0', `%eax') 83 define(`v0', `%edx') 84 85 86 ASM_START() 87 TEXT 88 ALIGN(16) 89 PROLOGUE(mpn_gcd_11) 90 push %edi 91 push %esi 92 push %ebx 93 94 mov 16(%esp), u0 95 mov 20(%esp), v0 96 LEAL( ctz_table, %esi) 97 sub v0, u0 C u = u - v 0 98 jz L(end) 99 100 ALIGN(16) 101 L(top): sbb %ebx, %ebx C mask 1 102 mov u0, %edi C 1 103 mov u0, %ecx C 1 104 and %ebx, %edi C 2 105 xor %ebx, u0 C 2 106 add %edi, v0 C v = min(u.v) 3 107 sub %ebx, u0 C u = |u - v| 3 108 L(mid): and $MASK, %ecx C 2 109 movzbl (%esi,%ecx), %ecx C 3 110 jz L(shift_alot) 111 shr %cl, u0 C 4 112 sub v0, u0 C u = u - v 0,5 113 jnz L(top) 114 115 L(end): mov v0, %eax 116 pop %ebx 117 pop %esi 118 pop %edi 119 ret 120 121 L(shift_alot): 122 shr $MAXSHIFT, u0 123 mov u0, %ecx 124 jmp L(mid) 125 EPILOGUE() 126 ASM_END() 127
Indexes created Mon Oct 26 00:26:21 UTC 2026