graph/encoding/{,di}graph6: fix bit handling for graph size encoding
MODIFY
graph/encoding/digraph6/digraph6.go
graph/encoding/digraph6/digraph6.go
@@ -62,13 +62,16 @@ func Encode(g graph.Graph) Graph {
// those machines n will not be this large, since it came
// from a length, but explicitly convert to 64 bits to
// allow the package to build on those architectures.
+ //
+ // See the section Small nonnegative integers in the spec
+ // for details of this section.
switch n := int64(n); {
case n < 63:
buf.WriteByte(byte(n) + 63)
case n < 258048:
- buf.Write([]byte{126, byte(n>>12) + 63, byte(n>>6) + 63, byte(n) + 63})
+ buf.Write([]byte{126, bit6(n>>12) + 63, bit6(n>>6) + 63, bit6(n) + 63})
case n < 68719476736:
- buf.Write([]byte{126, 126, byte(n>>30) + 63, byte(n>>24) + 63, byte(n>>18) + 63, byte(n>>12) + 63, byte(n>>6) + 63, byte(n) + 63})
+ buf.Write([]byte{126, 126, bit6(n>>30) + 63, bit6(n>>24) + 63, bit6(n>>18) + 63, bit6(n>>12) + 63, bit6(n>>6) + 63, bit6(n) + 63})
default:
panic("digraph6: too large")
}
@@ -89,6 +92,11 @@ func Encode(g graph.Graph) Graph {
return Graph(buf.String())
}
+// bit6 returns only the lower 6 bits of b.
+func bit6(b int64) byte {
+ return byte(b) & 0x3f
+}
+
// IsValid returns whether the graph is a valid digraph6 encoding. An invalid Graph
// behaves as the null graph.
func IsValid(g Graph) bool {
@@ -270,6 +278,11 @@ func numberOf(g Graph) int64 {
return -1
}
g = g[1:]
+ for _, b := range []byte(g) {
+ if b < 63 || 126 < b {
+ return -1
+ }
+ }
if g[0] != 126 {
return int64(g[0] - 63)
}

MODIFY
graph/encoding/digraph6/digraph6_test.go
graph/encoding/digraph6/digraph6_test.go
@@ -9,6 +9,7 @@ import (
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/iterator"
"gonum.org/v1/gonum/graph/simple"
)
@@ -278,3 +279,44 @@ func linksTo(nodes ...graph.Node) map[int]struct{} {
}
return s
}
+
+func TestLargeEncoding(t *testing.T) {
+ for _, l := range []int{
+ 50, 60, 70, 80, 100, 1e4,
+ } {
+ d6 := Encode(implicitCycle(l))
+ if !IsValid(d6) {
+ t.Errorf("digraph6-encoding unexpectedly invalid: %v", d6)
+ }
+ for i, b := range []byte(d6[1:]) {
+ if b < 63 || 126 < b {
+ t.Errorf("digraph6-encoding contains invalid character at %d: %q", i, b)
+ }
+ }
+ }
+}
+
+type implicitCycle int32
+
+func (i implicitCycle) Node(id int64) graph.Node {
+ if id < int64(i) {
+ return node(id)
+ }
+ return nil
+}
+func (i implicitCycle) Nodes() graph.Nodes {
+ return iterator.NewImplicitNodes(0, int(i), func(id int) graph.Node { return node(id) })
+}
+func (i implicitCycle) From(id int64) graph.Nodes {
+ if i < 2 {
+ return graph.Empty
+ }
+ next := int(id+1) % int(i)
+ return iterator.NewImplicitNodes(next, next+1, func(id int) graph.Node { return node(id) })
+}
+func (i implicitCycle) HasEdgeBetween(xid, yid int64) bool { return false }
+func (i implicitCycle) Edge(xid, yid int64) graph.Edge { return nil }
+
+type node int32
+
+func (n node) ID() int64 { return int64(n) }

MODIFY
graph/encoding/graph6/graph6.go
graph/encoding/graph6/graph6.go
@@ -63,13 +63,16 @@ func Encode(g graph.Graph) Graph {
// those machines n will not be this large, since it came
// from a length, but explicitly convert to 64 bits to
// allow the package to build on those architectures.
+ //
+ // See the section Small nonnegative integers in the spec
+ // for details of this section.
switch n := int64(n); {
case n < 63:
buf.WriteByte(byte(n) + 63)
case n < 258048:
- buf.Write([]byte{126, byte(n>>12) + 63, byte(n>>6) + 63, byte(n) + 63})
+ buf.Write([]byte{126, bit6(n>>12) + 63, bit6(n>>6) + 63, bit6(n) + 63})
case n < 68719476736:
- buf.Write([]byte{126, 126, byte(n>>30) + 63, byte(n>>24) + 63, byte(n>>18) + 63, byte(n>>12) + 63, byte(n>>6) + 63, byte(n) + 63})
+ buf.Write([]byte{126, 126, bit6(n>>30) + 63, bit6(n>>24) + 63, bit6(n>>18) + 63, bit6(n>>12) + 63, bit6(n>>6) + 63, bit6(n) + 63})
default:
panic("graph6: too large")
}
@@ -90,6 +93,11 @@ func Encode(g graph.Graph) Graph {
return Graph(buf.String())
}
+// bit6 returns only the lower 6 bits of b.
+func bit6(b int64) byte {
+ return byte(b) & 0x3f
+}
+
// IsValid returns whether the graph is a valid graph6 encoding. An invalid Graph
// behaves as the null graph.
func IsValid(g Graph) bool {
@@ -217,6 +225,11 @@ func numberOf(g Graph) int64 {
if len(g) < 1 {
return -1
}
+ for _, b := range []byte(g) {
+ if b < 63 || 126 < b {
+ return -1
+ }
+ }
if g[0] != 126 {
return int64(g[0] - 63)
}

MODIFY
graph/encoding/graph6/graph6_test.go
graph/encoding/graph6/graph6_test.go
@@ -9,6 +9,7 @@ import (
"testing"
"gonum.org/v1/gonum/graph"
+ "gonum.org/v1/gonum/graph/iterator"
"gonum.org/v1/gonum/graph/simple"
)
@@ -217,3 +218,46 @@ func linksTo(nodes ...graph.Node) map[int]struct{} {
}
return s
}
+
+func TestLargeEncoding(t *testing.T) {
+ for _, l := range []int{
+ 50, 60, 70, 80, 100, 1e4,
+ } {
+ g6 := Encode(implicitCycle(l))
+ if !IsValid(g6) {
+ t.Errorf("graph6-encoding unexpectedly invalid: %v", g6)
+ }
+ for i, b := range []byte(g6) {
+ if b < 63 || 126 < b {
+ t.Errorf("graph6-encoding contains invalid character at %d: %q", i, b)
+ }
+ }
+ }
+}
+
+type implicitCycle int32
+
+func (i implicitCycle) Node(id int64) graph.Node {
+ if id < int64(i) {
+ return node(id)
+ }
+ return nil
+}
+func (i implicitCycle) Nodes() graph.Nodes {
+ return iterator.NewImplicitNodes(0, int(i), func(id int) graph.Node { return node(id) })
+}
+func (i implicitCycle) From(id int64) graph.Nodes {
+ if i < 2 {
+ return graph.Empty
+ }
+ // This is not a valid undirected cycle, but it gets bits
+ // into the routine for testing and that is all we care about.
+ next := int(id+1) % int(i)
+ return iterator.NewImplicitNodes(next, next+1, func(id int) graph.Node { return node(id) })
+}
+func (i implicitCycle) HasEdgeBetween(xid, yid int64) bool { return false }
+func (i implicitCycle) Edge(xid, yid int64) graph.Edge { return nil }
+
+type node int32
+
+func (n node) ID() int64 { return int64(n) }

graph/encoding/{,di}graph6: fix bit handling for graph size encoding