path: root/src/main/stanza/bigint2.stanza

;Copyright (c) 2014 - 2016 The Regents of the University of
;California (Regents). All Rights Reserved.  Redistribution and use in
;source and binary forms, with or without modification, are permitted
;provided that the following conditions are met:
;   * Redistributions of source code must retain the above
;     copyright notice, this list of conditions and the following
;     two paragraphs of disclaimer.
;   * Redistributions in binary form must reproduce the above
;     copyright notice, this list of conditions and the following
;     two paragraphs of disclaimer in the documentation and/or other materials
;     provided with the distribution.
;   * Neither the name of the Regents nor the names of its contributors
;     may be used to endorse or promote products derived from this
;     software without specific prior written permission.
;IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT,
;SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS,
;ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
;REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
;REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
;LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
;A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION, IF
;ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO OBLIGATION
;TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
;MODIFICATIONS.

defpackage bigint2 :
   import core
   import verse

;============ Big Int Library =============

; d contains the Array<Int>, stored so the least significant word is at
;  index 0.

;------------ Helper Functions ------------
public defn pow (x:Int,y:Int) -> Int :
   var x* = 1
   var y* = y
   while y* != 0 :
      x* = times(x*,x)
      y* = minus(y*,1)
   x*

public defn pow (x:Long,y:Long) -> Long :
   var x* = to-long(1)
   var y* = y
   while y* != to-long(0) :
      x* = times(x*,x)
      y* = minus(y*,to-long(1))
   x*
public defn to-int (x:Long) -> Int :
   if x > to-long(2147483647) or x < to-long(-2147483648) : error("Long too big to convert to Int")
   else : to-int(to-string(x))

public defn to-int (x:BigInt) -> Int :
   if length(d(x)) > 1 : error("BigInt too big to convert to Int")
   else : d(x)[0]

public defn req-num-bits (i: Int) -> Int :
  val i* = 
     if i < 0 : ((-1 * i) - 1)
     else : i
  ceil-log2(i* + 1) + 1
val word-size = 32
val all-digits = "0123456789abcdef"

defn as-digit (c: Char) -> Int :
  index-of(all-digits, c) as Int

defn num-words (b:BigInt) : length(d(b))

defn shamt (c:Char) : 
   if c == 'b': 1 
   else if c == 'h': 4 
   else: error("Unsupported BigInt base.")

defn req-words (num-bits:Int) : (num-bits + word-size - 1) / word-size

defn to-hex (b:BigInt) -> String :
   defn as-hex (i: Int) -> String : substring(all-digits,i,i + 1)
   var li = List<String>()
   val tib = num-bits(b) % 4
   for i in 0 to num-bits(b) by 4 do :
      val word-index = i / 32
      val bit-index = i % 32
      var mask = 15
      
      val digit = 
         if (i + tib) == num-bits(b) :
            (d(b)[word-index] >> bit-index) & (pow(2,tib) - 1)
         else :
            (d(b)[word-index] >> bit-index) & 15 
      li = List(as-hex(digit),li)
   var saw-not-zero? = false
   val li* = Vector<String>()
   for i in 0 to length(li) do :
      val x = li[i]
      if saw-not-zero? == false and x == "0" and i < length(li) - 1 : false
      else :
         saw-not-zero? = true
         add(li*,x)
      
   string-join([ '\"' 'h' string-join(li*) '\"'])

defn to-bin (b:BigInt) -> String :
  string-join $ generate<Char> :
    defn* loop (pos:Int) :
      if (pos >= 0) :
        yield(if (d(b)[pos / 32] >> (pos % 32))&1 == 1: '1' else: '0')
        loop(pos - 1)
    loop(num-bits(b) - 1)

defn check-index (index:Int) -> False :
   if index < 0 : error("Bit index cannot be negative")
   false

defn check-bit (bit:Int) -> False :
   if bit != 0 and bit != 1 : error("Cannot set a bit other than 0 or 1")

;------------ Library ----------------
public defstruct BigInt <: Gettable & Settable :
   d : Array<Int>
   num-bits : Int
with : 
   constructor => #BigInt

public defn BigInt (d:Array<Int>, num-bits:Int) :
   check-index(num-bits)
   if num-bits > length(d) * word-size : 
      error("Number of bits greater than size of BigInt")
   val msw-index = req-words(num-bits) - 1
   val msb-index = num-bits % word-size
   ;Zero out all bits above num-bits
   if msb-index != 0 :
      d[msw-index] = d[msw-index] & (2 ^ msb-index - 1)
      for x in (msw-index + 1) to length(d) do :
         d[msw-index] = 0
   #BigInt(d,num-bits)

public defmethod get (b:BigInt, index:Int) -> Int : 
   check-index(index)
   if index >= num-bits(b) : error("Bit index is too high")
   val word-index = index / 32
   val bit-index = index % 32
   (d(b)[word-index] >> bit-index) & 1

defmethod set (b:BigInt, index:Int, bit:Int) -> False :
   check-index(index)
   check-bit(bit)
   val word-index = index / 32
   val bit-index = index % 32
   d(b)[word-index] = ((bit & 1) << bit-index) | d(b)[word-index]
   
public defmethod to-string (b:BigInt) : to-hex(b)
   ;string-join([to-hex(b) "'" num-bits(b)])

public defmethod print (o:OutputStream, b:BigInt) :
   print(o, to-string(b))

public defn req-num-bits (b:BigInt) -> Int :
   var msb = 0
   var seen? = false
   for i in 0 to num-bits(b) do :
      val index = num-bits(b) - 1 - i
      if b[index] != 0 and seen? == false :
         msb = index
         seen? = true
   msb + 1

public defn BigIntZero (num-bits:Int) -> BigInt :
   val num-words = (num-bits + word-size - 1) / word-size
   val d = Array<Int>(num-words)
   for i in 0 to length(d) do :
      d[i] = 0
   BigInt(d,num-bits)

public defn BigIntLit (data:Int) -> BigInt : 
   BigIntLit(data,req-num-bits(data))

public defn BigIntLit (data:Int, num-bits:Int) -> BigInt :
   val b = BigIntZero(num-bits)
   d(b)[0] = data
   b

public defn BigIntLit (data:String) -> BigInt :
  val num-bits = (length(data) - 1) * shamt(data[0])
  BigIntLit(data,num-bits)

public defn BigIntLit (data:String, num-bits:Int) -> BigInt :
  val lit     = BigIntZero(num-bits)
  val digits  = substring(data, 1)
  ;; println-all(["BASE " base " SHAMT " shamt " DIGITS " digits])
  for i in 0 to num-words(lit) do :
    d(lit)[i] = 0
  for i in 0 to length(digits) do :
    val off   = (length(digits) - 1 - i) * shamt(data[0])
    val wi    = off / word-size
    val bi    = off % word-size
    d(lit)[wi]   = d(lit)[wi] | (as-digit(digits[i]) << bi)
    ;; println-all(["OFF " off " wi " wi " bi " bi " lit[wi] " lit[wi] " => " lit])
  ;; println-all(["RES = " lit])
  lit

;------------------- Library API -----------------


;High is NOT inclusive
public defn bits (b:BigInt, high:Int, low:Int) -> BigInt : 
   check-index(high)
   check-index(low)
   if high <= low : error("High bit is less than or equal to low bit")
   val b* = BigIntZero(high - low)
   for i in 0 to num-bits(b*) do :
      b*[i] = b[i + low]
   b*
   
public defn bit (b:BigInt, index:Int) -> BigInt : 
   check-index(index)
   val b* = BigIntZero(1)
   b*[0] = b[index]
   b*

public defn rsh (b:BigInt, amount:Int) -> BigInt : 
   check-index(amount)
   bits(b,num-bits(b), amount)