Mirror of forum.nim-lang.org

9522 :: Packing integers and GMP bignums in a single value

• drkameleon (orginal) [2022-10-11T12:45:43+02:00] view original

  So, I've already said (https://forum.nim-lang.org/t/9478) I've been experimenting with some like NaN-boxing.

  This time the question is about something similar, but simpler.

  Let's say we could have simple 64-bit int values that could hold infinitely-large integers:

  • if the number is <= 0x7FFFFFFFFFFFFFFF (that is: it can fit in 63 bits), we set the first bit to 0 and "add" the number
  • if the number is greater than 63bits, then we create a GMP int (mpz_t), we set the first bit to 1 and store the pointer to this GMP int in the remaining 63 bits (obviously, we don't need that many)

  I'm using:

  • a slightly customized wrapper for GMP (https://github.com/arturo-lang/arturo/blob/master/src/extras/gmp.nim) and another one for MPFR (https://github.com/arturo-lang/arturo/blob/master/src/extras/mpfr.nim)
  • a helper for the two libraries (https://github.com/arturo-lang/arturo/blob/master/src/helpers/bignums.nim)

  All of them have been working consistently, so there is no issue whatsoever on that part (at least nothing I have noticed after thousands of tests).

  Now, the biggest challenge is getting a pointer to one of this Int objects (which are nothing but ref mpz_t), stuff it in an int64 and hold on to it - until we don't want to anymore...

  Here's an experimental module I have created that does precisely this:

  #=======================================
  # Libraries
  #=======================================
  
  import hashes, strutils
  import src/helpers/bignums
  
  #=======================================
  # Types
  #=======================================
  
  type
      VInteger* = distinct int64
  
  #=======================================
  # Constants
  #=======================================
  
  const
      IntegerMask*    = 0x7FFFFFFFFFFFFFFF
      IntegerBit*     = 0x8000000000000000
  
  #=======================================
  # Helpers
  #=======================================
  
  template pack*(x: untyped): VInteger =
      VInteger(x)
  
  template packBig*(x: untyped, doCreate: static bool = true): VInteger =
      when doCreate:
          var r = newInt(x)
      
      VInteger(IntegerBit or cast[int64](
              when doCreate   : addr r
              else            : addr x
          )
      )
  
  func isBig*(x: VInteger): bool {.inline,enforceNoRaises.} =
      (x.int64 and IntegerBit) != 0
  
  func getBig*(x: VInteger): Int {.inline.} =
      return (cast[ptr Int](x.int64 and IntegerMask))[]
  
  #=======================================
  # Methods
  #=======================================
  
  proc newVInteger*(i: int64): VInteger {.inline,enforceNoRaises.} =
      if i < IntegerMask  : pack(i)
      else                : packBig((int)i)
  
  func newVInteger*(i: var Int): VInteger {.inline,enforceNoRaises.} =
      packBig(i, doCreate=false)
  
  proc newVInteger*(s: string): VInteger {.inline.} =
      try:
          newVInteger(parseInt(s))
      except ValueError:
          return packBig(s)
  
  #=======================================
  # Overloads
  #=======================================
  
  func `$`(x: VInteger): string {.inline,enforceNoRaises.} =
      if isBig(x) : $(getBig(x))
      else        : $(x.int64)
  
  func hash*(x: VInteger): Hash {.inline.} =
      cast[Hash](x)
  
  #=======================================
  # Tests
  #=======================================
  
  when isMainModule:
      let v1 = newVInteger(1)
      let v2 = newVInteger("1231312312312312")
      let v3 = newVInteger("234726384762384762384762384723634873264")
      
      echo $(v1)
      echo $(v2)
      echo $(v3)
  Run

  I compile with nim r -d:danger --mm:orc.

  The problem comes with the v3 value (and its accompanying $(v3) which triggers a "Illegal storage access" error. And quite obviously so, since after stuffing the pointer in packBig our newInt in variable r seems to have been destroyed. If I bring r outside, declared as some global var, the whole thing seems to be working fine. But it's obviously not the point (just a verification that the whole logic is correct).

  I have also tried using a GC_ref for this variable, but it's still not working.

  So, the question is simple: How do I get this to work as intended?

---

• Araq (orginal) [2022-10-11T18:27:21+02:00] view original

  Via GC_ref. Alternatively use ptr instead of ref and alloc0. Figuring how where to call dealloc is the same task as figuring out where to call GC_unref.

---