Packed recoding for endomorphism accelerated ECC Scalar Multiplication

recoding.nim

import typetraits, strutils

const
  BitSize   = 2
  Shift     = 2    # log2(4) - we can store 4 digit per byte
  ByteMask  = 3    # we need (mod 4) to access a packed bytearray
  DigitMask = 0b11 # Digits take 2-bit

type
  Recoded[NumDigits: static int] = distinct array[(NumDigits + 3) div 4 + 1, byte]

  SignExtender = object
    digit {.bitsize:2.}: int8

proc len(recoding: Recoded): int =
  distinctBase(recoding).len

proc `[]`(recoding: Recoded,
          digitIdx: int): int8 {.inline.}=
  ## 0 <= intID < N, the recoded integer index
  ## 0 <= digitIdx < Length
  ## returns digit ∈ {0, 1, −1}
  let slot = distinctBase(recoding)[
    recoding.len-1 - (digitIdx shr Shift)
  ]
  let recoded = slot shr (BitSize*(digitIdx and ByteMask)) and DigitMask
  var signExtender: SignExtender
  # Hack with C assignment that return values
  {.emit: [result, " = ", signExtender, ".digit = ", recoded, ";"].}
  # " # Fix highlighting bug in VScode

proc `[]=`(recoding: var Recoded,
           digitIdx: int, value: int8) {.inline.}=
  ## 0 <= intID < N, the recoded integer index
  ## digit ∈ {0, 1, −1}
  ## This is write-once
  let slot = distinctBase(recoding)[
    recoding.len-1 - (digitIdx shr Shift)
  ].addr
  let shifted = byte((value and DigitMask) shl (BitSize*(digitIdx and ByteMask)))
  slot[] = slot[] or shifted

var a: Recoded[16]

proc toString(a: Recoded): string =
  result = "[" & $a[0]
  for i in 1 ..< a.NumDigits:
    result &= ", "
    result &= $a[i]
  result &= "]"

echo a.toString
a[5] = 1'i8
a[6] = -1'i8
a[10] = -1'i8
echo a.toString