First post in what will (hopefully?) be building an extremely simple BitTorrent client in Go. At the very least we’ll aimto parse .torrent files, connect to peers and download files. Just to manage expectations, incoming requests (uploads), DHT and the like will likely be left as an exercise to the reader.
Note: most (if not all) of the snippets should be using any instead of interface{} - the 2 are now interchangeable
bencode- Approach
- Interface, “data” holders
- Parsing
- Encoding
- Struct tags and parsing a
.torrentfile! - Taking it further
bencode
If you have ever downloaded a .torrent file from say, Ubuntu and tried to open it in a file editor, you’ll be hard pressed to call this readable. The file is encoded in a format called bencode, the specification of which is available here. Here’s the first few lines for reference:
~/r/c/go-bt ❯❯❯ head src/ubuntu.torrent | fold -w 80
d8:announce35:https://torrent.ubuntu.com/announce13:announce-listll35:https://to
rrent.ubuntu.com/announceel40:https://ipv6.torrent.ubuntu.com/announceee7:commen
t29:Ubuntu CD releases.ubuntu.com10:created by13:mktorrent 1.113:creation datei1
681992889e4:infod6:lengthi2641264640e4:name34:ubuntu-23.04-live-server-amd64.iso
12:piece lengthi262144e6:pieces201520:%
The TL;DR is that we can use it to represent basic types - e.g. a positive integer is represented as a stream starting with i and ending with e. So 123 would be encoded as i123e. Lists have a similar setup - with l being the start delimiter. So the list [123,456] would be represented as li123ei456ee. Lists can contain other lists too!
Byte strings (I guess that’d be char in C?) are a little different in that they start with a number representing the length, delimited by : - so “foo” would be encoded as 3:foo. Don’t confuse this with UTF-8 type strings you have in Python - len("😜".encode("utf-8")) is actually 4 bytes!
Maps are similar to lists, starting with a d (easy heh?). Keys must be sorted in byte order and must be byte strings - so the Python dict {'foo': 123} would be encoded as d3:fooi123ee.
Approach
If you have ever used a stream-based parser like StAX for XML, or PyYAML, we’ll be doing something somewhat similar. Take this list with a nested element for example:
[1, [2], 3] = li1eli2eei3ee
As we process the stream, the structure looks a little bit like a tree:
[
1,
[
2
],
3
]
When we encounter the first [ we set the “node type” to a list, and recursively call our parser with the remaining of the stream. After reading 1 we look to see if we had a root note - we had and it’s a list, so we append the value to it. We keep recursively call ourselves with the remaining bytes of the stream. In pseudo code, this looks a bit like:
parse(<holder>, 'li1eli2eei3ee')
parse([, 'i1eli2eei3ee')
parse([1, 'li2eei3ee')
parse([1,[,'i2eei3ee')
parse([1,[2,'ei3ee')
return [2]
parse([1,[2],'i3ee')
parse([1,[2],3, 'e')
parse([1,[2],3], '')
return [1,[2],3]
Interface, “data” holders
Here’s the general interface - we only need 2 methods. One to add value as we see them, and one to return the contents.
type Holder interface {
Add(value any)
Obj() any
}Here are the basic type (List, Dict and Value - the latter is for scalars of all kinds):
type ListHolder struct {
List []any
}
type DictHolder struct {
Dict map[string]any
// tracks the current key
Key string
}
type ValueHolder struct {
Val any
}Their implementation of the Holder interface is as follows:
// Add methods
func (c *ListHolder) Add(value any) {
c.List = append(c.List, value)
}
func (c *DictHolder) Add(value any) {
if c.Key == "" {
c.Key = value.(string)
} else {
c.Dict[c.Key] = value
// reset
c.Key = ""
}
}
func (c *ValueHolder) Add(value any) {
c.Val = value
}
// Obj methods
func (c *ListHolder) Obj() any {
return c.List
}
func (c *DictHolder) Obj() any {
return c.Dict
}
func (c *ValueHolder) Obj() any {
return c.Val
}The only one worth a mention is the DictHolder. When we finish processing an element inside the dict, we need to know hwhether it was a key or a value - so we use c.Key internally as a toggle. If it’s set, the next call to Add is for a value - and if not, it’s the start of a key.
Parsing
Now we almost ready to start parsing the stream! Let’s start with some basic tests (TDD FTW!) to ensure we’re doing the right thing. It’s not full coverage but should be enough to help us flush out silly mistakes.
func TestBencodeRecursiveParser(t *testing.T) {
// negative int!
r := bytes.NewReader([]byte("i-42e"))
ret := data.ParseBencoded2(r)
if ret != -42 {
t.Errorf("expected -42, got %v", ret)
}
// string, below 10 chars
r = bytes.NewReader([]byte("3:foo"))
ret = data.ParseBencoded2(r).(string)
if ret != "foo" {
t.Errorf("expected 'foo', got %v", ret)
}
// string, above 10 chars
r = bytes.NewReader([]byte("12:foobarraboof"))
ret = data.ParseBencoded2(r).(string)
if ret != "foobarraboof" {
t.Errorf("expected 'foo', got %v", ret)
}
// list with one int
r = bytes.NewReader([]byte("li42ee"))
retSlice, _ := data.ParseBencoded2(r).([]interface{})
if len(retSlice) != 1 && retSlice[0] != 42 {
t.Errorf("expected [42], got %v", ret)
}
// list with two items
r = bytes.NewReader([]byte("li42ei43ee"))
retSlice, _ = data.ParseBencoded2(r).([]interface{})
if len(retSlice) != 2 && retSlice[0] != 42 && retSlice[1] != 43 {
t.Errorf("expected [42, 43], got %v", ret)
}
// a simple map
r = bytes.NewReader([]byte("d3:fooi42ee"))
retMap, _ := data.ParseBencoded2(r).(map[string]interface{})
if retMap["foo"] != 42 {
t.Errorf("expected [42], got %v", retMap)
}
// a map with a list
r = bytes.NewReader([]byte("d3:fooli42eee"))
retMap, _ = data.ParseBencoded2(r).(map[string]interface{})
retSlice = retMap["foo"].([]interface{})
if len(retSlice) != 1 && retSlice[0] != 42 {
t.Errorf("expected {'foo': [42]}, got %v", ret)
}
}The parsing is split into 2 - we have the public interface ParseBencoded2 (2 because my first impl wasn’t something to be proud of), and the internal recursive parsing function called parseBencodeStream. The check function is a little helper to help catch issues early. I like a good debugging session as much as the next person but that’s simpler than letting errors propagate.
func check(err error) {
if err != nil {
if err != io.EOF {
panic(err)
}
}
}
func parseBencodeStream(container Holder, reader *bufio.Reader) Holder {
b, err := reader.ReadByte()
if err != nil {
return container
}
switch b {
case 'e':
return container
case 'i':
buff, err := reader.ReadBytes('e')
check(err)
val, err := strconv.Atoi(string(buff[:len(buff)-1]))
check(err)
container.Add(val)
return parseBencodeStream(container, reader)
case 'l':
c := parseBencodeStream(&ListHolder{List: make([]any, 0)}, reader)
container.Add(c.(*ListHolder).List)
return parseBencodeStream(container, reader)
case 'd':
c := parseBencodeStream(&DictHolder{Dict: make(map[string]any)}, reader)
container.Add(c.(*DictHolder).Dict)
return parseBencodeStream(container, reader)
case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
buff, err := reader.ReadBytes(':')
check(err)
strLen := string(b)
if len(buff) > 1 {
strLen += string(buff[:len(buff)-1])
}
strLenInt, err := strconv.Atoi(strLen)
check(err)
val := make([]byte, strLenInt)
for i := 0; i < strLenInt; i++ {
b, err = reader.ReadByte()
check(err)
val[i] = b
}
container.Add(string(val[:])
return parseBencodeStream(container, reader)
}
return container
}
func ParseBencoded2(r io.Reader) any {
reader := bufio.NewReader(r)
// kick this off by passing an empty holder
container := parseBencodeStream(&ValueHolder{}, reader)
return container.Obj()
}We kick things off with a ValueHolder (because we expect to return a single value - i1ei2e wouldn’t be “valid” per se, it’d need to be in a container) and a pointer to bufio.Reader, which allows us to continuously read form the same stream. We read a byte at a time in some cases, and in others until we hit a specific delimiter (e.g. e for integers, : for strings etc…). If we find a new container delimiter we create the appropriate holder (for a list or a map) and recurse accordingly.
Running our tests shows we’re home free:
/V/r/c/g/src ❯❯❯ go test ./data
ok go-bt/data 0.351s
Encoding
We’re half-way there. We can parse data, let’s make sure we can serialise it back. The beauty of this is that from a test perspective, encode(parse(data)) is equivalent to the identity function! That is, this is just equal to data. A bit like decompressing a compressed file.
Caveat emptor: the encoding code will be sufficient for BitTorrent but isn’t comprehensive enough to support all kinds of types!
If you’ve ever used reflection in say, Java, you’ll appreciate how terse it is in golang! As with the parser, we’ll need to recurse on each value in a container. For maps that means we’ll need to first encode the key, then the value. For lists, we’ll need to encode each elemenet.
As done previously, let’s start with some tests - we only need to specify the input and ensure that’s what we get back:
func TestBencodeDecode(t *testing.T) {
testCases := []struct {
data []byte
}{
{[]byte("i-42e")},
{[]byte("3:foo")},
{[]byte("12:foobarraboof")},
{[]byte("li42ee")},
{[]byte("li42ei43ee")},
{[]byte("d3:fooi42ee")},
{[]byte("d3:fooli42eee")},
{[]byte("d3:fooi42e3:zari1ee")},
}
buf := &bytes.Buffer{}
for _, testCase := range testCases {
buf.Reset()
data.Encode(buf, data.ParseBencoded2(bytes.NewReader(testCase.data)))
if bytes.Compare(buf.Bytes(), testCase.data) != 0 {
t.Errorf("expected %s, got %s", testCase.data, buf.Bytes())
}
}
}Now for abusing reflect with all kinds of types:
func Encode(buffer *bytes.Buffer, o any) {
value := reflect.ValueOf(o)
switch value.Kind() {
case reflect.Int, reflect.Int16, reflect.Int32, reflect.Int64:
buffer.WriteByte('i')
buffer.WriteString(strconv.Itoa(int(value.Int())))
buffer.WriteByte('e')
case reflect.Uint, reflect.Uint16, reflect.Uint32, reflect.Uint64:
buffer.WriteByte('i')
buffer.WriteString(strconv.Itoa(int(value.Uint())))
buffer.WriteByte('e')
case reflect.String:
buffer.WriteString(strconv.Itoa(len(value.Interface().(string))))
buffer.WriteString(":")
buffer.WriteString(value.Interface().(string))
case reflect.Slice:
buffer.WriteByte('l')
// so this is a bit funky - we can't convert e.g. []int to []any directly
temp := make([]any, value.Len())
for i := 0; i < value.Len(); i++ {
temp[i] = value.Index(i).Interface()
}
for _, val := range temp {
Encode(buffer, val)
}
buffer.WriteByte('e')
case reflect.Map:
buffer.WriteByte('d')
temp := make(map[string]any, value.Len())
// we need a map[string]any
iter := value.MapRange()
for iter.Next() {
k := iter.Key()
v := iter.Value()
temp[k.Interface().(string)] = v.Interface()
}
// keys need to be sorted alphabetically
keys := make([]string, 0, len(temp))
for k := range temp {
keys = append(keys, k)
}
slices.Sort(keys)
for _, key := range keys {
// first we write the key
Encode(buffer, key)
// then the value
Encode(buffer, temp[key])
}
buffer.WriteByte('e')
default:
panic(fmt.Sprintf("can't handle type %s", value.Kind()))
}
}Note the default in the switch - there may be types we’re not aware of, and those will cause us to panic. Particularly if we passed in a struct of some kind we’d be toast.
Struct tags and parsing a .torrent file!
Be warned, this abuses reflect even moar
Now that we can marshall data in and out what we ideally want is to represent a .torrent file as a series of struct (it contains nested fields so it won’t be just one) and have it be populated automagically on the back of a bencoded stream. This is where tags come in handy - similarly to what one might do when marshalling to/from JSON.
Note that we only need to define tags for the fields we want populated automatically - fields that don’t contain tags will be left alone. Furthermore, we can nest data types - for example a .torrent file is, at the outset, nothing more than a map with some predefined keys - and some of those keys (like info) are maps themselves.
A subset of the fields could be represented as such:
type BETorrent struct {
InfoHash [20]byte
Announce string `bencode:"announce"`
AnnounceList [][]string `bencode:"announce-list"`
Info BEInfo `bencode:"info"`
}
type BEInfo struct {
Name string `bencode:"name"`
PieceLength uint64 `bencode:"piece length"` // bytes per piece
Pieces string `bencode:"pieces"` // byte string, 20-byte SHA1 for each piece
Length uint64 `bencode:"length"` // of file(s), in bytes
}Filling in a BETorrent struct consists of iterating through each field and finding the appropriate match in the encoded data. Side note, announce-list is a list of list of strings… :shrug:
func ParseTorrentFile2(r io.Reader) *BETorrent {
obj := ParseBencoded2(r)
d, ok := obj.(map[string]any)
if !ok {
panic("Unable to parse torrent")
}
betorrent := &BETorrent{}
fillStruct(betorrent, d)
return betorrent
}fillStruct is the workhorse that parses data both iteratively and recursively:
func fillStruct(o any, d map[string]any) {
var structure reflect.Type
if reflect.TypeOf(o).Kind() != reflect.Struct {
structure = reflect.TypeOf(o).Elem()
} else {
structure = reflect.TypeOf(o)
}
var fill func(containerType reflect.Type, val any, field reflect.Value)
// using this for recursive calls for e.g. slices of slices
fill = func(containerType reflect.Type, val any, field reflect.Value) {
switch containerType.Kind() {
case reflect.Struct:
oo := reflect.New(containerType)
fillStruct(oo.Interface(), val.(map[string]any))
field.Set(oo.Elem())
case reflect.Slice:
s := reflect.ValueOf(val)
// reflect.SliceOf(string) say, returns a []string type
valueSlice := reflect.MakeSlice(reflect.SliceOf(containerType.Elem()), s.Len(), s.Len())
for i := 0; i < s.Len(); i++ {
fill(containerType.Elem(), s.Index(i).Interface(), valueSlice.Index(i))
}
field.Set(valueSlice.Convert(containerType))
default:
bindat := reflect.ValueOf(val).Convert(containerType)
field.Set(bindat)
}
}
for i := 0; i < structure.NumField(); i++ {
f := structure.Field(i)
tag := f.Tag.Get("bencode")
if val, ok := d[tag]; ok {
fill(f.Type, val, reflect.ValueOf(o).Elem().Field(i))
}
}
}note it isn’t fully generic. For one it expects a map[string]any for the data that needs to be deserialised. Also the handling of reflect.Slice feels a bit wonky even though it works.
But can we go back?
We can parse a .torrent into a struct, and we can encode an arbitrary dictionary. But can we go from a struct back into a bencoded map? It turns out we’ll need this later, so let’s get it out of the way now. In a nutshell, those are the tests we want to satisfy. Note that the return value should be a map[string]any - we already know how to encode this kind of datastructure:
func TestBencodeStruct(t *testing.T) {
// info dict with multiple files
beinfo := data.BEInfo{
Name: "foo",
PieceLength: 65536,
Files: []data.BEFile{
{
Path: []string{"path1"},
Length: 123,
},
{
Path: []string{"path2"},
Length: 456,
},
},
}
val := bencode.ToDict(beinfo)
// due to how we encode, note how we need to specify unit64
expected := map[string]any{
"name": "foo",
"piece length": uint64(65536),
// "length": uint64(0),
// "pieces": "",
"files": []map[string]any{
{"path": []string{"path1"}, "length": 123},
{"path": []string{"path2"}, "length": 456},
},
}
if !reflect.DeepEqual(val, expected) {
t.Errorf("exepcted %+v, got %+v", expected, val)
}
// info dict with a single file
beinfo = data.BEInfo{
Name: "foo",
PieceLength: 65536,
Pieces: "deadbeef",
Length: 123456,
}
val = bencode.ToDict(beinfo)
// due to how we encode, note how we need to specify unit64
expected = map[string]any{
"name": "foo",
"piece length": uint64(65536),
"length": uint64(123456),
"pieces": "deadbeef",
// "files": make([]map[string]any, 0),
}
if !reflect.DeepEqual(val, expected) {
t.Errorf("exepcted %+v, got %+v", expected, val)
}
}Leveraging the pattern that allowed us to go from dictionary to struct, we can reverse the order to through the struct and look for fields with a bencode tag (ignoring those that don’t have one or just as importantly, those that aren’t set):
func ToDict(val any) map[string]any {
structure := reflect.TypeOf(val)
ret := map[string]any{}
var fill func(val any) any
fill = func(obj any) any {
t := reflect.TypeOf(obj)
switch t.Kind() {
case reflect.Struct:
return ToDict(obj)
case reflect.Slice:
v := reflect.ValueOf(obj)
switch t.Elem().Kind() {
case reflect.Struct:
valueSlice := make([]map[string]any, v.Len())
for i := 0; i < v.Len(); i++ {
o := ToDict(v.Index(i).Interface())
valueSlice[i] = o
}
return valueSlice
default:
valueSlice := reflect.MakeSlice(reflect.SliceOf(t.Elem()), v.Len(), v.Len())
for i := 0; i < v.Len(); i++ {
o := fill(v.Index(i).Interface())
valueSlice.Index(i).Set(reflect.ValueOf(o))
}
return valueSlice.Convert(t).Interface()
}
default:
return obj
}
}
for i := 0; i < structure.NumField(); i++ {
f := structure.Field(i)
tag := f.Tag.Get("bencode")
// idk if this is the correct thing to do, but it does help flush out unset values
if tag != "" && !reflect.ValueOf(val).FieldByName(f.Name).IsZero() {
ret[tag] = fill(reflect.ValueOf(val).FieldByName(f.Name).Interface())
}
}
return ret
}Taking it further
.torrent files aren’t the only files leveraging bencode in BitTorrent. The tracker response for instance is another. I had to make a few changes to leverage generics - e.g.
func ParseFromReader[S BETorrent | BETrackerResponse](r io.Reader) *S {
obj := ParseBencoded2(r)
d, ok := obj.(map[string]any)
if !ok {
panic("Unable to parse torrent")
}
var s S
fillStruct(&s, d)
return &s
}where a subset of the relevant structs are defined as:
type BEPeer struct {
Id string `bencode:"peer id"`
IP string `bencode:"ip"`
Port int64 `bencode:"port"`
}
type BETrackerResponse struct {
Complete int64 `bencode:"complete"` // seeds
Incomplete int64 `bencode:"incomplete"` // leechers
Interval int64 `bencode:"interval"` // in seconds
Peers []BEPeer `bencode:"peers"`
}All in all this was rather fun - except the reflect part, which whilst satisfying to get right, was more of a pain than I care to admit. But it does make the structs that much easier to use!
Join me for part 2!