gcd.s

	# binary gcd algorithm in amd64 assembly
	# gcd(u, v);
	.text
	.globl gcd
	.type gcd,@function
gcd:
	# u is in edi
	# v is in esi

	# abs routines are not branch free because we need to test
	# anyway to catch u == 0 or v == 0
	test %edi,%edi
	jns .Lupos		# u < 0
	jz .Luzero		# u == 0
	neg %edi		# u = abs(u)
.Lupos:

	test %esi,%esi
	jns .Lvpos		# v < 0
	jz .Lvzero		# u == 0
	neg %esi		# v = abs(v)
.Lvpos:

	mov %edi,%ecx		# k is in %ecx
	or %esi,%ecx
	bsf %ecx,%ecx		# k = bsf(u | v);
	sar %cl,%edi		# u >>= k
	sar %cl,%esi		# v >>= k

	mov %ecx,%eax		# make %ecx free for later use

	# step B2, t = (u & 1) ? -v : u;
	mov %edi,%edx		# t is in %edx
	neg %edx
	test $1,%dil
	cmovz %esi,%edx

	test %edx,%edx		# if t == 0 return
	jz .Lend

.Lloop:
	neg %esi

	bsf %edx,%ecx		# t >>= bsf(t)
	sar %cl,%edx

	cmovns %edx,%edi
	cmovs %edx,%esi
	neg %esi

	mov %edi,%edx
	sub %esi,%edx
	jnz .Lloop

.Lend:
	mov %eax,%ecx
	mov %edi,%eax
	shl %cl,%eax
	ret

	# when u == 0 or v == 0
.Luzero:
	mov %esi,%edx		# v = abs(v)
	sar $31,%edx
	xor %edx,%esi
	sub %edx,%esi

.Lvzero:
	mov %edi,%eax
	or %esi,%eax
	ret

	.size gcd,.-gcd