pkg/math/bits: complete operations
- add shift operations
- rewritten and simplified several functions
- remove reverse operations as not sure what they mean
Closes #156
Change-Id: I0769c771e1a1e310d672d39a72b4c888e464be21
Reviewed-on: https://cue-review.googlesource.com/c/cue/+/3965
Reviewed-by: Marcel van Lohuizen <mpvl@golang.org>
diff --git a/cue/builtin_test.go b/cue/builtin_test.go
index 41f8861..3752689 100644
--- a/cue/builtin_test.go
+++ b/cue/builtin_test.go
@@ -510,6 +510,18 @@
test("struct", `struct.MaxFields(2) & {a: 1}`),
`{a: 1}`,
}, {
+ test("math/bits", `bits.Lsh(0x8, 4)`), `128`,
+ }, {
+ test("math/bits", `bits.Rsh(0x100, 4)`), `16`,
+ }, {
+ test("math/bits", `bits.At(0x100, 8)`), `1`,
+ }, {
+ test("math/bits", `bits.At(0x100, 9)`), `0`,
+ }, {
+ test("math/bits", `bits.Set(0x100, 7, 1)`), `384`,
+ }, {
+ test("math/bits", `bits.Set(0x100, 8, 0)`), `0`,
+ }, {
test("math/bits", `bits.And(0x10000000000000F0E, 0xF0F7)`), `6`,
}, {
test("math/bits", `bits.Or(0x100000000000000F0, 0x0F)`),
diff --git a/cue/builtins.go b/cue/builtins.go
index 46d0971..b1c215e 100644
--- a/cue/builtins.go
+++ b/cue/builtins.go
@@ -1570,25 +1570,64 @@
},
"math/bits": &builtinPkg{
native: []*builtin{{
+ Name: "Lsh",
+ Params: []kind{intKind, intKind},
+ Result: intKind,
+ Func: func(c *callCtxt) {
+ x, n := c.bigInt(0), c.uint(1)
+ c.ret = func() interface{} {
+ var z big.Int
+ z.Lsh(x, n)
+ return &z
+ }()
+ },
+ }, {
+ Name: "Rsh",
+ Params: []kind{intKind, intKind},
+ Result: intKind,
+ Func: func(c *callCtxt) {
+ x, n := c.bigInt(0), c.uint(1)
+ c.ret = func() interface{} {
+ var z big.Int
+ z.Rsh(x, n)
+ return &z
+ }()
+ },
+ }, {
+ Name: "At",
+ Params: []kind{intKind, intKind},
+ Result: intKind,
+ Func: func(c *callCtxt) {
+ x, i := c.bigInt(0), c.uint(1)
+ c.ret, c.err = func() (interface{}, error) {
+ if i > 1<<62 {
+ return 0, fmt.Errorf("bit index too large")
+ }
+ return x.Bit(int(i)), nil
+ }()
+ },
+ }, {
+ Name: "Set",
+ Params: []kind{intKind, intKind, intKind},
+ Result: intKind,
+ Func: func(c *callCtxt) {
+ x, i, bit := c.bigInt(0), c.int(1), c.uint(2)
+ c.ret = func() interface{} {
+ var z big.Int
+ z.SetBit(x, i, bit)
+ return &z
+ }()
+ },
+ }, {
Name: "And",
Params: []kind{intKind, intKind},
Result: intKind,
Func: func(c *callCtxt) {
a, b := c.bigInt(0), c.bigInt(1)
c.ret = func() interface{} {
- wa := a.Bits()
- wb := b.Bits()
- n := len(wa)
- if len(wb) < n {
- n = len(wb)
- }
- w := make([]big.Word, n)
- for i := range w {
- w[i] = wa[i] & wb[i]
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.And(a, b)
+ return &z
}()
},
}, {
@@ -1598,22 +1637,9 @@
Func: func(c *callCtxt) {
a, b := c.bigInt(0), c.bigInt(1)
c.ret = func() interface{} {
- wa := a.Bits()
- wb := b.Bits()
- var w []big.Word
- n := len(wa)
- if len(wa) > len(wb) {
- w = append(w, wa...)
- n = len(wb)
- } else {
- w = append(w, wb...)
- }
- for i := 0; i < n; i++ {
- w[i] = wa[i] | wb[i]
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.Or(a, b)
+ return &z
}()
},
}, {
@@ -1623,22 +1649,9 @@
Func: func(c *callCtxt) {
a, b := c.bigInt(0), c.bigInt(1)
c.ret = func() interface{} {
- wa := a.Bits()
- wb := b.Bits()
- var w []big.Word
- n := len(wa)
- if len(wa) > len(wb) {
- w = append(w, wa...)
- n = len(wb)
- } else {
- w = append(w, wb...)
- }
- for i := 0; i < n; i++ {
- w[i] = wa[i] ^ wb[i]
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.Xor(a, b)
+ return &z
}()
},
}, {
@@ -1648,18 +1661,9 @@
Func: func(c *callCtxt) {
a, b := c.bigInt(0), c.bigInt(1)
c.ret = func() interface{} {
- wa := a.Bits()
- wb := b.Bits()
- w := append([]big.Word(nil), wa...)
- for i, m := range wb {
- if i >= len(w) {
- break
- }
- w[i] = wa[i] &^ m
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.AndNot(a, b)
+ return &z
}()
},
}, {
@@ -1667,29 +1671,13 @@
Params: []kind{intKind},
Result: intKind,
Func: func(c *callCtxt) {
- x := c.uint64(0)
+ x := c.bigInt(0)
c.ret = func() interface{} {
- return bits.OnesCount64(x)
- }()
- },
- }, {
- Name: "Reverse",
- Params: []kind{intKind},
- Result: intKind,
- Func: func(c *callCtxt) {
- x := c.uint64(0)
- c.ret = func() interface{} {
- return bits.Reverse64(x)
- }()
- },
- }, {
- Name: "ReverseBytes",
- Params: []kind{intKind},
- Result: intKind,
- Func: func(c *callCtxt) {
- x := c.uint64(0)
- c.ret = func() interface{} {
- return bits.ReverseBytes64(x)
+ var count int
+ for _, w := range x.Bits() {
+ count += bits.OnesCount64(uint64(w))
+ }
+ return count
}()
},
}, {
@@ -1697,9 +1685,9 @@
Params: []kind{intKind},
Result: intKind,
Func: func(c *callCtxt) {
- x := c.uint64(0)
+ x := c.bigInt(0)
c.ret = func() interface{} {
- return bits.Len64(x)
+ return x.BitLen()
}()
},
}},
@@ -3042,7 +3030,7 @@
short?: string
long?: string
tasks: {
- [name=_]: Task
+ [name=string]: Task
}
}
Task: {
@@ -3067,7 +3055,7 @@
cmd: string | [string, ...string]
install?: string | [string, ...string]
env: {
- [Key=_]: string
+ [Key=string]: string
}
stdout: *null | string | bytes
stderr: *null | string | bytes
@@ -3115,10 +3103,10 @@
response: {
body: *bytes | string
header: {
- [Name=_]: string | [...string]
+ [Name=string]: string | [...string]
}
trailer: {
- [Name=_]: string | [...string]
+ [Name=string]: string | [...string]
}
status: string
statusCode: int
@@ -3127,10 +3115,10 @@
request: {
body: *bytes | string
header: {
- [Name=_]: string | [...string]
+ [Name=string]: string | [...string]
}
trailer: {
- [Name=_]: string | [...string]
+ [Name=string]: string | [...string]
}
}
}
diff --git a/pkg/math/bits/manual.go b/pkg/math/bits/manual.go
index 64ea5bb..506d4f1 100644
--- a/pkg/math/bits/manual.go
+++ b/pkg/math/bits/manual.go
@@ -19,105 +19,94 @@
package bits
import (
+ "fmt"
"math/big"
"math/bits"
)
-// And returns the bitwise and of a and b (a & b in Go).
-//
+// Lsh returns x shifted left by n bits.
+func Lsh(x *big.Int, n uint) *big.Int {
+ var z big.Int
+ z.Lsh(x, n)
+ return &z
+}
+
+// Rsh returns x shifted right by n bits.
+func Rsh(x *big.Int, n uint) *big.Int {
+ var z big.Int
+ z.Rsh(x, n)
+ return &z
+}
+
+// At returns the value of the i'th bit of x.
+func At(x *big.Int, i uint) (uint, error) {
+ if i > 1<<62 {
+ return 0, fmt.Errorf("bit index too large")
+ }
+ return x.Bit(int(i)), nil
+}
+
+// SetBit returns x with x's i'th bit set to b (0 or 1). That is, if b is 1
+// SetBit returns x with its i'th bit set; if b is 0 SetBit returns x with
+// its i'th bit cleared.
+func Set(x *big.Int, i int, bit uint) *big.Int {
+ var z big.Int
+ z.SetBit(x, i, bit)
+ return &z
+}
+
+// And returns the bitwise and of a and b.
func And(a, b *big.Int) *big.Int {
- wa := a.Bits()
- wb := b.Bits()
- n := len(wa)
- if len(wb) < n {
- n = len(wb)
- }
- w := make([]big.Word, n)
- for i := range w {
- w[i] = wa[i] & wb[i]
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.And(a, b)
+ return &z
}
// Or returns the bitwise or of a and b (a | b in Go).
-//
func Or(a, b *big.Int) *big.Int {
- wa := a.Bits()
- wb := b.Bits()
- var w []big.Word
- n := len(wa)
- if len(wa) > len(wb) {
- w = append(w, wa...)
- n = len(wb)
- } else {
- w = append(w, wb...)
- }
- for i := 0; i < n; i++ {
- w[i] = wa[i] | wb[i]
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.Or(a, b)
+ return &z
}
// Xor returns the bitwise xor of a and b (a ^ b in Go).
-//
func Xor(a, b *big.Int) *big.Int {
- wa := a.Bits()
- wb := b.Bits()
- var w []big.Word
- n := len(wa)
- if len(wa) > len(wb) {
- w = append(w, wa...)
- n = len(wb)
- } else {
- w = append(w, wb...)
- }
- for i := 0; i < n; i++ {
- w[i] = wa[i] ^ wb[i]
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.Xor(a, b)
+ return &z
}
// Clear returns the bitwise and not of a and b (a &^ b in Go).
//
func Clear(a, b *big.Int) *big.Int {
- wa := a.Bits()
- wb := b.Bits()
- w := append([]big.Word(nil), wa...)
- for i, m := range wb {
- if i >= len(w) {
- break
- }
- w[i] = wa[i] &^ m
- }
- i := &big.Int{}
- i.SetBits(w)
- return i
+ var z big.Int
+ z.AndNot(a, b)
+ return &z
}
-// TODO: ShiftLeft, maybe trailing and leading zeros
-
// OnesCount returns the number of one bits ("population count") in x.
-func OnesCount(x uint64) int {
- return bits.OnesCount64(x)
+func OnesCount(x *big.Int) int {
+ var count int
+ for _, w := range x.Bits() {
+ count += bits.OnesCount64(uint64(w))
+ }
+ return count
}
+// TODO: Reverse, ReverseBytes?
+// Not entirely sure what that means for infinite precision.
// Reverse returns the value of x with its bits in reversed order.
-func Reverse(x uint64) uint64 {
- return bits.Reverse64(x)
-}
+// func Reverse(x uint64) uint64 {
+// return bits.Reverse64(x)
+// }
-// ReverseBytes returns the value of x with its bytes in reversed order.
-func ReverseBytes(x uint64) uint64 {
- return bits.ReverseBytes64(x)
-}
+// // ReverseBytes returns the value of x with its bytes in reversed order.
+// func ReverseBytes(x uint64) uint64 {
+// return bits.ReverseBytes64(x)
+// }
-// Len returns the minimum number of bits required to represent x; the result is 0 for x == 0.
-func Len(x uint64) int {
- return bits.Len64(x)
+// Len returns the length of the absolute value of x in bits. The bit length
+// of 0 is 0.
+func Len(x *big.Int) int {
+ return x.BitLen()
}
