summaryrefslogtreecommitdiff
path: root/Build/source/libs/gmp/gmp-6.0.0/mpn/ia64/gcd_1.asm
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/libs/gmp/gmp-6.0.0/mpn/ia64/gcd_1.asm')
-rw-r--r--Build/source/libs/gmp/gmp-6.0.0/mpn/ia64/gcd_1.asm234
1 files changed, 234 insertions, 0 deletions
diff --git a/Build/source/libs/gmp/gmp-6.0.0/mpn/ia64/gcd_1.asm b/Build/source/libs/gmp/gmp-6.0.0/mpn/ia64/gcd_1.asm
new file mode 100644
index 00000000000..28e9a63ca39
--- /dev/null
+++ b/Build/source/libs/gmp/gmp-6.0.0/mpn/ia64/gcd_1.asm
@@ -0,0 +1,234 @@
+dnl Itanium-2 mpn_gcd_1 -- mpn by 1 gcd.
+
+dnl Contributed to the GNU project by Kevin Ryde, innerloop by Torbjorn
+dnl Granlund.
+
+dnl Copyright 2002-2005, 2012, 2013 Free Software Foundation, Inc.
+
+dnl This file is part of the GNU MP Library.
+dnl
+dnl The GNU MP Library is free software; you can redistribute it and/or modify
+dnl it under the terms of either:
+dnl
+dnl * the GNU Lesser General Public License as published by the Free
+dnl Software Foundation; either version 3 of the License, or (at your
+dnl option) any later version.
+dnl
+dnl or
+dnl
+dnl * the GNU General Public License as published by the Free Software
+dnl Foundation; either version 2 of the License, or (at your option) any
+dnl later version.
+dnl
+dnl or both in parallel, as here.
+dnl
+dnl The GNU MP Library is distributed in the hope that it will be useful, but
+dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+dnl for more details.
+dnl
+dnl You should have received copies of the GNU General Public License and the
+dnl GNU Lesser General Public License along with the GNU MP Library. If not,
+dnl see https://www.gnu.org/licenses/.
+
+include(`../config.m4')
+
+
+C cycles/bitpair (1x1 gcd)
+C Itanium: ?
+C Itanium 2: 5.1
+
+
+C mpn_gcd_1 (mp_srcptr xp, mp_size_t xsize, mp_limb_t y);
+C
+C The entry sequence is designed to expect xsize>1 and hence a modexact
+C call. This ought to be more common than a 1x1 operation. Our critical
+C path is thus stripping factors of 2 from y, calling modexact, then
+C stripping factors of 2 from the x remainder returned.
+C
+C The common factors of 2 between x and y must be determined using the
+C original x, not the remainder from the modexact. This is done with
+C x_orig which is xp[0]. There's plenty of time to do this while the rest
+C of the modexact etc is happening.
+C
+C It's possible xp[0] is zero. In this case the trailing zeros calculation
+C popc((x-1)&~x) gives 63, and that's clearly no less than what y will
+C have, making min(x_twos,y_twos) == y_twos.
+C
+C The main loop consists of transforming x,y to abs(x-y),min(x,y), and then
+C stripping factors of 2 from abs(x-y). Those factors of two are
+C determined from just y-x, without the abs(), since there's the same
+C number of trailing zeros on n or -n in twos complement. That makes the
+C dependent chain 8 cycles deep.
+C
+C The selection of x-y versus y-x for abs(x-y), and the selection of the
+C minimum of x and y, is done in parallel with the critical path.
+C
+C The algorithm takes about 0.68 iterations per bit (two N bit operands) on
+C average, hence the final 5.8 cycles/bitpair.
+C
+C Not done:
+C
+C An alternate algorithm which didn't strip all twos, but instead applied
+C tbit and predicated extr on x, and then y, was attempted. The loop was 6
+C cycles, but the algorithm is an average 1.25 iterations per bitpair for a
+C total 7.25 c/bp, which is slower than the current approach.
+C
+C Alternatives:
+C
+C Perhaps we could do something tricky by extracting a few high bits and a
+C few low bits from the operands, and looking up a table which would give a
+C set of predicates to control some shifts or subtracts or whatever. That
+C could knock off multiple bits per iteration.
+C
+C The right shifts are a bit of a bottleneck (shr at 2 or 3 cycles, or extr
+C only going down I0), perhaps it'd be possible to shift left instead,
+C using add. That would mean keeping track of the lowest not-yet-zeroed
+C bit, using some sort of mask.
+C
+C TODO:
+C * Once mod_1_N exists in assembly for Itanium, add conditional calls.
+C * Call bmod_1 even for n=1 when up[0] >> v0 (like other gcd_1 impls).
+C * Probably avoid popcnt also outside of loop, instead use ctz_table.
+
+ASM_START()
+ .explicit C What does this mean?
+
+C HP's assembler requires these declarations for importing mpn_modexact_1c_odd
+ .global mpn_modexact_1c_odd
+ .type mpn_modexact_1c_odd,@function
+
+C ctz_table[n] is the number of trailing zeros on n, or MAXSHIFT if n==0.
+
+deflit(MAXSHIFT, 7)
+deflit(MASK, eval((m4_lshift(1,MAXSHIFT))-1))
+
+ .section ".rodata"
+ ALIGN(m4_lshift(1,MAXSHIFT)) C align table to allow using dep
+ctz_table:
+ .byte MAXSHIFT
+forloop(i,1,MASK,
+` .byte m4_count_trailing_zeros(i)
+')
+
+PROLOGUE(mpn_gcd_1)
+
+ C r32 xp
+ C r33 xsize
+ C r34 y
+
+define(x, r8)
+define(xp_orig, r32)
+define(xsize, r33)
+define(y, r34) define(inputs, 3)
+define(save_rp, r35)
+define(save_pfs, r36)
+define(x_orig, r37)
+define(x_orig_one, r38)
+define(y_twos, r39) define(locals, 5)
+define(out_xp, r40)
+define(out_xsize, r41)
+define(out_divisor, r42)
+define(out_carry, r43) define(outputs, 4)
+
+ .prologue
+{ .mmi;
+ifdef(`HAVE_ABI_32',
+` addp4 r9 = 0, xp_orig define(xp,r9)', C M0
+` define(xp,xp_orig)')
+ .save ar.pfs, save_pfs
+ alloc save_pfs = ar.pfs, inputs, locals, outputs, 0 C M2
+ .save rp, save_rp
+ mov save_rp = b0 C I0
+}{ .body
+ add r10 = -1, y C M3 y-1
+} ;;
+
+{ .mmi; ld8 x = [xp] C M0 x = xp[0] if no modexact
+ ld8 x_orig = [xp] C M1 orig x for common twos
+ cmp.ne p6,p0 = 1, xsize C I0
+}{ .mmi; andcm y_twos = r10, y C M2 (y-1)&~y
+ mov out_xp = xp_orig C M3
+ mov out_xsize = xsize C I1
+} ;;
+
+ mov out_carry = 0
+
+ popcnt y_twos = y_twos C I0 y twos
+ ;;
+
+{ .mmi; add x_orig_one = -1, x_orig C M0 orig x-1
+ shr.u out_divisor = y, y_twos C I0 y without twos
+}{ shr.u y = y, y_twos C I1 y without twos
+ (p6) br.call.sptk.many b0 = mpn_modexact_1c_odd C if xsize>1
+} ;;
+
+ C modexact can leave x==0
+{ .mmi; cmp.eq p6,p0 = 0, x C M0 if {xp,xsize} % y == 0
+ andcm x_orig = x_orig_one, x_orig C M1 orig (x-1)&~x
+ add r9 = -1, x C I0 x-1
+} ;;
+
+{ .mmi; andcm r9 = r9, x C M0 (x-1)&~x
+ mov b0 = save_rp C I0
+} ;;
+
+ popcnt x_orig = x_orig C I0 orig x twos
+ popcnt r9 = r9 C I0 x twos
+ ;;
+
+{ cmp.lt p7,p0 = x_orig, y_twos C M0 orig x_twos < y_twos
+ shr.u x = x, r9 C I0 x odd
+} ;;
+
+{ (p7) mov y_twos = x_orig C M0 common twos
+ add r10 = -1, y C I0 y-1
+ (p6) br.dpnt.few L(done_y) C B0 x%y==0 then result y
+} ;;
+
+ addl r22 = @ltoffx(ctz_table#), r1
+ mov r25 = m4_lshift(MASK, MAXSHIFT)
+ ;;
+ ld8.mov r22 = [r22], ctz_table#
+ br L(ent)
+
+ ALIGN(32)
+L(top): .pred.rel "mutex", p6,p7
+.mmi; (p7) mov y = x
+ (p6) sub x = x, y
+ dep r21 = r19, r22, 0, MAXSHIFT C concat(table,lowbits)
+.mmi; and r20 = MASK, r19
+ (p7) mov x = r19
+ nop 0
+ ;;
+L(mid):
+.mmb; ld1 r16 = [r21]
+ cmp.eq p10,p0 = 0, r20
+ (p10) br.spnt.few.clr L(shift_alot)
+ ;;
+.mmi; nop 0
+ nop 0
+ shr.u x = x, r16
+ ;;
+L(ent):
+.mmi; sub r19 = y, x
+ cmp.gtu p6,p7 = x, y
+ cmp.ne p8,p0 = x, y
+.mmb; nop 0
+ nop 0
+ (p8) br.sptk.few.clr L(top)
+
+
+ C result is y
+L(done_y):
+ mov ar.pfs = save_pfs C I0
+ shl r8 = y, y_twos C I common factors of 2
+ br.ret.sptk.many b0
+
+L(shift_alot):
+ and r20 = x, r25
+ shr.u x = x, MAXSHIFT
+ ;;
+ dep r21 = x, r22, 0, MAXSHIFT
+ br L(mid)
+EPILOGUE()