Implement bigint mulAdd and sqrAdd intrinsics on ARM.

runtime/vm/intrinsifier_arm.cc

Index: runtime/vm/intrinsifier_arm.cc
===================================================================
--- runtime/vm/intrinsifier_arm.cc	(revision 40991)
+++ runtime/vm/intrinsifier_arm.cc	(working copy)
@@ -913,12 +913,219 @@
 
 
 void Intrinsifier::Bigint_mulAdd(Assembler* assembler) {
-  // TODO(regis): Implement.
+  if (TargetCPUFeatures::arm_version() != ARMv7) return;

[Cutch, 2014/10/08 15:22:26]

if (TargetCPUFeatures::arm_version() != ARMv7) {
  return;
}

here and elsewhere.

[regis, 2014/10/08 16:58:00]

Done.

+  // Pseudo code:
+  // static void _mulAdd(Uint32List x_digits, int xi,
+  //                     Uint32List m_digits, int i,
+  //                     Uint32List a_digits, int j, int n) {
+  //   uint32_t x = x_digits[xi >> 1];  // xi is Smi.
+  //   if (x == 0 || n == 0) {
+  //     return;
+  //   }
+  //   uint32_t* mip = &m_digits[i >> 1];  // i is Smi.
+  //   uint32_t* ajp = &a_digits[j >> 1];  // j is Smi.
+  //   uint32_t c = 0;
+  //   SmiUntag(n);
+  //   do {
+  //     uint32_t mi = *mip++;
+  //     uint32_t aj = *ajp;
+  //     uint64_t t = x*mi + aj + c;  // 32-bit * 32-bit -> 64-bit.
+  //     *ajp++ = low32(t);
+  //     c = high32(t);
+  //   } while (--n > 0);
+  //   while (c != 0) {
+  //     uint64_t t = *ajp + c;
+  //     *ajp++ = low32(t);
+  //     c = high32(t);  // c == 0 or 1.
+  //   }
+  // }
+
+  Label done;
+  // R3 = x, no_op if x == 0
+  __ ldr(R1, Address(SP, 6 * kWordSize));  // x_digits
+  __ ldr(R0, Address(SP, 5 * kWordSize));  // xi is Smi
+  __ add(R1, R1, Operand(R0, LSL, 1));
+  __ ldr(R3, FieldAddress(R1, TypedData::data_offset()));
+  __ tst(R3, Operand(R3));
+  __ b(&done, EQ);
+
+  // R6 = SmiUntag(n), no_op if n == 0
+  __ ldr(R6, Address(SP, 0 * kWordSize));
+  __ Asrs(R6, R6, Operand(kSmiTagSize));
+  __ b(&done, EQ);
+
+  // R4 = mip = &m_digits[i >> 1]
+  __ ldr(R1, Address(SP, 4 * kWordSize));  // m_digits
+  __ ldr(R0, Address(SP, 3 * kWordSize));  // i is Smi
+  __ add(R1, R1, Operand(R0, LSL, 1));
+  __ add(R4, R1, Operand(TypedData::data_offset() - kHeapObjectTag));
+
+  // R5 = ajp = &a_digits[j >> 1]
+  __ ldr(R1, Address(SP, 2 * kWordSize));  // a_digits
+  __ ldr(R0, Address(SP, 1 * kWordSize));  // j is Smi
+  __ add(R1, R1, Operand(R0, LSL, 1));
+  __ add(R5, R1, Operand(TypedData::data_offset() - kHeapObjectTag));
+
+  // R1 = c = 0
+  __ mov(R1, Operand(0));
+
+  Label muladd_loop;
+  __ Bind(&muladd_loop);
+  // x:   R3
+  // mip: R4
+  // ajp: R5
+  // c:   R1
+  // n:   R6
+
+  // uint32_t mi = *mip++
+  __ ldr(R2, Address(R4, kWordSize, Address::PostIndex));
+
+  // uint32_t aj = *ajp
+  __ ldr(R0, Address(R5, 0));
+
+  // uint64_t t = x*mi + aj + c
+  __ umaal(R0, R1, R2, R3);  // R1:R0 = R2*R3 + R1 + R0.
+
+  // *ajp++ = low32(t) = R0
+  __ str(R0, Address(R5, kWordSize, Address::PostIndex));
+
+  // c = high32(t) = R1
+
+  // while (--n > 0)
+  __ subs(R6, R6, Operand(1));  // --n
+  __ b(&muladd_loop, NE);
+
+  __ tst(R1, Operand(R1));
+  __ b(&done, EQ);
+
+  // *ajp++ += c
+  __ ldr(R0, Address(R5, 0));
+  __ adds(R0, R0, Operand(R1));
+  __ str(R0, Address(R5, kWordSize, Address::PostIndex));
+  __ b(&done, CC);
+
+  Label propagate_carry_loop;
+  __ Bind(&propagate_carry_loop);
+  __ ldr(R0, Address(R5, 0));
+  __ adds(R0, R0, Operand(1));
+  __ str(R0, Address(R5, kWordSize, Address::PostIndex));
+  __ b(&propagate_carry_loop, CS);
+
+  __ Bind(&done);
+  __ Ret();
 }
 
 
 void Intrinsifier::Bigint_sqrAdd(Assembler* assembler) {
-  // TODO(regis): Implement.
+  if (TargetCPUFeatures::arm_version() != ARMv7) return;
+  // Pseudo code:
+  // static void _sqrAdd(Uint32List x_digits, int i,
+  //                     Uint32List a_digits, int used) {
+  //   uint32_t* xip = &x_digits[i >> 1];  // i is Smi.
+  //   uint32_t x = *xip++;
+  //   if (x == 0) return;
+  //   uint32_t* ajp = &a_digits[i];  // j == 2*i, i is Smi.
+  //   uint32_t aj = *ajp;
+  //   uint64_t t = x*x + aj;
+  //   *ajp++ = low32(t);
+  //   uint64_t c = high32(t);
+  //   int n = ((used - i) >> 1) - 1;  // used and i are Smi.
+  //   while (--n >= 0) {
+  //     uint32_t xi = *xip++;
+  //     uint32_t aj = *ajp;
+  //     uint96_t t = 2*x*xi + aj + c;  // 2-bit * 32-bit * 32-bit -> 65-bit.
+  //     *ajp++ = low32(t);
+  //     c = high64(t);  // 33-bit.
+  //   }
+  //   uint32_t aj = *ajp;
+  //   uint64_t t = aj + c;  // 32-bit + 33-bit -> 34-bit.
+  //   *ajp++ = low32(t);
+  //   *ajp = high32(t);
+  // }
+
+  // R4 = xip = &x_digits[i >> 1]
+  __ ldr(R1, Address(SP, 3 * kWordSize));  // x_digits
+  __ ldr(R6, Address(SP, 2 * kWordSize));  // i is Smi
+  __ add(R1, R1, Operand(R6, LSL, 1));
+  __ add(R4, R1, Operand(TypedData::data_offset() - kHeapObjectTag));
+
+  // R3 = x = *xip++, return if x == 0
+  Label x_zero;
+  __ ldr(R3, Address(R4, kWordSize, Address::PostIndex));
+  __ tst(R3, Operand(R3));
+  __ b(&x_zero, EQ);
+
+  // R5 = ajp = &a_digits[i]
+  __ ldr(R1, Address(SP, 1 * kWordSize));  // a_digits
+  __ add(R1, R1, Operand(R6, LSL, 2));  // j == 2*i, i is Smi.
+  __ add(R5, R1, Operand(TypedData::data_offset() - kHeapObjectTag));
+
+  // R7:R0 = t = x*x + *ajp
+  __ ldr(R0, Address(R5, 0));
+  __ mov(R7, Operand(0));
+  __ umaal(R0, R7, R3, R3);  // R7:R0 = R3*R3 + R7 + R0.
+
+  // *ajp++ = low32(t) = R0
+  __ str(R0, Address(R5, kWordSize, Address::PostIndex));
+
+  // R7 = low32(c) = high32(t)
+  // R8 = high32(c) = 0
+  __ mov(R8, Operand(0));
+
+  // int n = used - i - 1
+  __ ldr(R0, Address(SP, 0 * kWordSize));  // used is Smi
+  __ sub(R6, R0, Operand(R6));
+  __ mov(R0, Operand(2));  // while (--n >= 0)
+  __ rsbs(R6, R0, Operand(R6, ASR, kSmiTagSize));
+
+  Label loop, done;
+  __ b(&done, MI);
+
+  __ Bind(&loop);
+  // x:   R3
+  // xip: R4
+  // ajp: R5
+  // c:   R8:R7
+  // t:   R2:R1:R0 (not live at loop entry)
+  // n:   R6
+
+  // uint32_t xi = *xip++
+  __ ldr(R2, Address(R4, kWordSize, Address::PostIndex));
+
+  // uint32_t aj = *ajp
+  __ ldr(R1, Address(R5, 0));
+
+  // uint96_t t = R2:R1:R0 = 2*x*xi + aj + c
+  __ mov(R0, Operand(0));
+  __ umaal(R0, R1, R2, R3);  // R1:R0 = R3*R2 + R1 + R0 = x*xi + aj + 0.
+  __ umlal(R7, R8, R2, R3);  // R8:R7 += R3*R2; c += x*xi.
+  __ adds(R0, R0, Operand(R7));
+  __ adcs(R7, R1, Operand(R8));
+  __ mov(R8, Operand(0));
+  __ adc(R8, R8, Operand(0));  // R8:R7:R0 = R1:R0 + R8:R7 = 2*x*xi + aj + c.
+
+  // *ajp++ = low32(t) = R0
+  __ str(R0, Address(R5, kWordSize, Address::PostIndex));
+
+  // while (--n >= 0)
+  __ subs(R6, R6, Operand(1));  // --n
+  __ b(&loop, PL);
+
+  __ Bind(&done);
+  // uint32_t aj = *ajp
+  __ ldr(R0, Address(R5, 0));
+
+  // uint64_t t = aj + c
+  __ adds(R7, R7, Operand(R0));
+  __ adc(R8, R8, Operand(0));
+
+  // *ajp++ = low32(t)
+  // *ajp = high32(t)
+  __ str(R7, Address(R5, 0));
+  __ str(R8, Address(R5, kWordSize));
+
+  __ Bind(&x_zero);
+  __ Ret();
 }