1/* x86-64 __int128 multiply/divide/remainder, called from cc1-emitted
  2 * code (see cmd/dev/cc/qbe.c's funcdiv128). qbe has no widening
  3 * multiply and no divide wider than 64 bits, and division needs a bit
  4 * serial long-division loop no ir-level codegen could express, so both
  5 * live here instead. names and abi match compiler-rt's own
  6 * __multi3/__udivmodti4, so a real libgcc could stand in unchanged.
  7 * division always takes the slower, always-correct bit serial path
  8 * rather than a divisor-fits-in-64-bits shortcut, the same "correct
  9 * first" choice this project's atomics runtime makes by always
 10 * compiling to seq_cst instead of a weaker order
 11 */
 12
 13.text
 14
 15/* truncated 128 bit product: a_hi*b_hi is entirely above bit 128 and
 16 * never computed. one widening mul (for the low*low term's own high
 17 * word) plus two truncating imul (the cross terms)
 18 */
 19.globl __multi3
 20__multi3:
 21	/* a: rdi=a_lo rsi=a_hi   b: rdx=b_lo rcx=b_hi */
 22	movq %rsi, %r8
 23	imul %rdx, %r8    /* a_hi * b_lo, low 64 */
 24	movq %rdi, %r9
 25	imul %rcx, %r9    /* a_lo * b_hi, low 64 */
 26	movq %rdi, %rax
 27	mul %rdx           /* rdx:rax = a_lo * b_lo, full 128 bit */
 28	addq %r8, %rdx
 29	addq %r9, %rdx
 30	ret
 31
 32/* unsigned quotient in rax:rdx, remainder written to *rem. bit serial
 33 * restoring division: 128 iterations, each pulling the next dividend
 34 * bit into the remainder (a 128 bit left shift built from shl/shr/or,
 35 * no shld/rcl in this assembler) and setting the matching quotient bit
 36 * once the remainder is large enough to subtract the divisor back out
 37 * (subtract-with-borrow built from cmp/setb/sub, no sbb here either;
 38 * the same technique qbe.c uses for branchless __int128 subtraction)
 39 */
 40.globl __udivmodti4
 41__udivmodti4:
 42	/* a: rdi=a_lo rsi=a_hi   b: rdx=b_lo rcx=b_hi   rem: r8 */
 43	push %r12
 44	push %r13
 45	push %r8
 46	xorq %r8, %r8    /* q_lo = 0 */
 47	xorq %r9, %r9     /* q_hi = 0 */
 48	xorq %r10, %r10    /* r_lo = 0 */
 49	xorq %r11, %r11     /* r_hi = 0 */
 50	movq $128, %rax
 51.Ludivloop:
 52	/* r12 = bit_i(a), the msb about to fall out of the 128 bit
 53	   dividend as it shifts left */
 54	movq %rsi, %r12
 55	shrq $63, %r12
 56
 57	/* a <<= 1 (128 bit): lo's old msb feeds hi's new lsb */
 58	movq %rdi, %r13
 59	shrq $63, %r13
 60	shlq $1, %rdi
 61	shlq $1, %rsi
 62	orq %r13, %rsi
 63
 64	/* r = (r << 1) | bit_i(a) */
 65	movq %r10, %r13
 66	shrq $63, %r13
 67	shlq $1, %r10
 68	shlq $1, %r11
 69	orq %r13, %r11
 70	orq %r12, %r10
 71
 72	/* q <<= 1, making room for this iteration's quotient bit */
 73	movq %r8, %r13
 74	shrq $63, %r13
 75	shlq $1, %r8
 76	shlq $1, %r9
 77	orq %r13, %r9
 78
 79	/* r >= b (128 bit unsigned)? */
 80	cmpq %rcx, %r11
 81	ja .Ludivcommit
 82	jb .Ludivskip
 83	cmpq %rdx, %r10
 84	jb .Ludivskip
 85.Ludivcommit:
 86	/* r -= b, with the borrow from the low word carried into the
 87	   high word's subtraction by hand (no sbb in this assembler) */
 88	cmpq %rdx, %r10
 89	setb %r13b
 90	movzbq %r13b, %r13
 91	subq %rdx, %r10
 92	subq %rcx, %r11
 93	subq %r13, %r11
 94	orq $1, %r8
 95.Ludivskip:
 96	subq $1, %rax
 97	jnz .Ludivloop
 98
 99	pop %rdi
100	movq %r10, (%rdi)
101	movq %r11, 8(%rdi)
102	movq %r8, %rax
103	movq %r9, %rdx
104	pop %r13
105	pop %r12
106	ret