Design of internal functions taking out parameters (addition, additionInt, etc.)

[konsumlamm]

The internal functions currently take a var BigInt argument as first parameter, which is used to store the result (essentially an out parameter). I suppose that is so that a buffer can be preallocated, however, that's never done afaict. In this light, it would be more ergonomic to just return a new BigInt (using the result variable).

Another possibility is instead of defining functions like func addition(a: var BigInt, b, c: BigInt) to do a = b + c, use func addition(a: var BigInt, b: BigInt) to do a += b. That would avoid copying the first argument for +=. a + b would then be implemented as result = a; result += b, but I'm not sure if that avoids a copy (I think it should, at least with ARC/ORC). (I'm just using addition as an example, the same applies to other operations).

If there is no flaw in my analysis, I'd prefer the last possibility, as I think it's the most efficient and ergonomic.

cc @narimiran @mratsim

[mratsim]

See my comment to #78 (comment)

Offering functions with signatures proc add(r: var BigInt, a, b: BigInt) that allows algorithm implementers to reuse buffers.
Those function should properly deal with aliasing.

It's much easier for maintenance, optimization and future development to have a single high-level function that can handle aliasing, sign, a > b and b < a.
Then if needed you can specialize for the aliasing case. But it becomes very tricky if you want BigInt to work in the compile-time VM, it would be nice if we had overloads based on {.noalias.} that worked in the VM or some magic to compare if 2 parameters are actually pointing to the same memory.

This is what I do in Constantine:
At a low-level I have:

func add*(a: var Limbs, b: Limbs): Carry =
  ## Limbs addition
  ## Returns the carry
  when UseASM_X86_32:
    result = add_asm(a, a, b)
  else:
    result = Carry(0)
    for i in 0 ..< a.len:
      addC(result, a[i], a[i], b[i], result)

func add*(a: var Limbs, w: SecretWord): Carry =
  ## Limbs addition, add a number that fits in a word
  ## Returns the carry
  result = Carry(0)
  addC(result, a[0], a[0], w, result)
  for i in 1 ..< a.len:
    addC(result, a[i], a[i], Zero, result)

func sum*(r: var Limbs, a, b: Limbs): Carry =
  ## Sum `a` and `b` into `r`
  ## `r` is initialized/overwritten
  ##
  ## Returns the carry
  when UseASM_X86_32:
    result = add_asm(r, a, b)
  else:
    result = Carry(0)
    for i in 0 ..< a.len:
      addC(result, r[i], a[i], b[i], result)

https://github.com/mratsim/constantine/blob/50717d8/constantine/arithmetic/limbs.nim#L198-L226

And at a high-level I offer: https://github.com/mratsim/constantine/blob/50717d8/constantine/arithmetic/bigints.nim#L196-L246

func add*(a: var BigInt, b: BigInt): SecretBool =
  ## Constant-time in-place addition
  ## Returns the carry
  (SecretBool) add(a.limbs, b.limbs)

func add*(a: var BigInt, b: SecretWord): SecretBool =
  ## Constant-time in-place addition
  ## Returns the carry
  (SecretBool) add(a.limbs, b)

func `+=`*(a: var BigInt, b: BigInt) =
  ## Constant-time in-place addition
  ## Discards the carry
  discard add(a.limbs, b.limbs)

func `+=`*(a: var BigInt, b: SecretWord) =
  ## Constant-time in-place addition
  ## Discards the carry
  discard add(a.limbs, b)

func double*(a: var BigInt): SecretBool =
  ## Constant-time in-place doubling
  ## Returns the carry
  (SecretBool) add(a.limbs, a.limbs)

func sum*(r: var BigInt, a, b: BigInt): SecretBool =
  ## Sum `a` and `b` into `r`.
  ## `r` is initialized/overwritten
  ##
  ## Returns the carry
  (SecretBool) sum(r.limbs, a.limbs, b.limbs)

Note that sum can deal with aliasing.
That said Constantine has other limiting constraints, for example code must be constant-time so no branches that may depend on secret data so if/else. And on the other hand inputs are always positive and (almost always) same size, known at compile-time.

[konsumlamm]

Hmm, one use case I see is optimizing a = b + c to addition(a, b, c), but I'd rather not expose the functions taking a buffer, so that would be limited to bigints functions. I think we should definitely optimize += etc.

[mratsim]

If you want others to build more complex algorithm on top, having functions that do not allocate is very important for optimization.

People would be able to provide a pool of BigInt and recycle them in perf-critical code (this is done in Go for example).
People would be able to reuse a buffer for thousands of limbs for stuff like FFT, Prime algorithm and what not without stressing the allocator, especially in a multithreaded context.

[mratsim]

Regarding optimizations, the representation must use uint64 on 64-bit arch and on x86 64-bit use extended precision multiplication 64x64->128 and 2-by-1 division.