code review 881050: big: Add Lsh and Value; convert pidigits to use big

src/pkg/big/nat.go

 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 // This file contains operations on unsigned multi-precision integers.
 // These are the building blocks for the operations on signed integers
 // and rationals.
 
 // This package implements multi-precision arithmetic (big numbers).
 // The following numeric types are supported:
@@ skipping 284 matching lines @@
 //    len(uIn) >= len(v)
 func divLargeNN(z, z2, uIn, v []Word) (q, r []Word) {
         n := len(v)
         m := len(uIn) - len(v)
 
         u := makeN(z2, len(uIn)+1, false)
         qhatv := make([]Word, len(v)+1)
         q = makeN(z, m+1, false)
 
         // D1.
-        shift := leadingZeroBits(v[n-1])
+        shift := uint(leadingZeroBits(v[n-1]))
         shiftLeft(v, v, shift)
         shiftLeft(u, uIn, shift)
         u[len(uIn)] = uIn[len(uIn)-1] >> (_W - uint(shift))
 
         // D2.
         for j := m; j >= 0; j-- {
                 // D3.
                 var qhat Word
                 if u[j+n] == v[n-1] {
                         qhat = _B - 1
@@ skipping 207 matching lines @@
         case 64:
                 return int(deBruijn64Lookup[((x&-x)*(deBruijn64&_M))>>58])
         default:
                 panic("Unknown word size")
         }
 
         return 0
 }
 
 
-func shiftLeft(dst, src []Word, n int) {
+// To avoid losing the top n bits, dst should be sized so that
+// len(dst) == len(src) + 1.
+func shiftLeft(dst, src []Word, n uint) {
         if len(src) == 0 {
                 return
         }
 
-        ñ := _W - uint(n)
+        ñ := _W - n
+        if len(dst) > len(src) {
+                dst[len(src)] |= src[len(src)-1] >> ñ
+        }
         for i := len(src) - 1; i >= 1; i-- {
-                dst[i] = src[i] << uint(n)
-                dst[i] |= src[i-1] >> ñ
+                dst[i] = src[i]<<n | src[i-1]>>ñ
         }
-        dst[0] = src[0] << uint(n)
+        dst[0] = src[0] << n
 }
 
 
-func shiftRight(dst, src []Word, n int) {
+func shiftRight(dst, src []Word, n uint) {
         if len(src) == 0 {
                 return
         }
 
-        ñ := _W - uint(n)
+        ñ := _W - n
         for i := 0; i < len(src)-1; i++ {
-                dst[i] = src[i] >> uint(n)
-                dst[i] |= src[i+1] << ñ
+                dst[i] = src[i]>>n | src[i+1]<<ñ
         }
-        dst[len(src)-1] = src[len(src)-1] >> uint(n)
+        dst[len(src)-1] = src[len(src)-1] >> n
 }
 
 
 // greaterThan returns true iff (x1<<_W + x2) > (y1<<_W + y2)
 func greaterThan(x1, x2, y1, y2 Word) bool { return x1 > y1 || x1 == y1 && x2 > y2 }
 
 
 // modNW returns x % d.
 func modNW(x []Word, d Word) (r Word) {
         // TODO(agl): we don't actually need to store the q value.
@@ skipping 10 matching lines @@
 
         zeroWords := 0
         for n[zeroWords] == 0 {
                 zeroWords++
         }
         // One of the words must be non-zero by invariant, therefore
         // zeroWords < len(n).
         x := trailingZeroBits(n[zeroWords])
 
         q = makeN(nil, len(n)-zeroWords, false)
-        shiftRight(q, n[zeroWords:], x)
+        shiftRight(q, n[zeroWords:], uint(x))
         q = normN(q)
 
         k = Word(_W*zeroWords + x)
         return
 }
 
 
 // randomN creates a random integer in [0..limit), using the space in z if
 // possible. n is the bit length of limit.
 func randomN(z []Word, rand *rand.Rand, limit []Word, n int) []Word {
@@ skipping 180 matching lines @@
                         }
                         if cmpNN(y, bigOne) == 0 {
                                 return false
                         }
                 }
                 return false
         }
 
         return true
 }