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