From 88d570291cd42aa8984e1801b9120e1cf9bf4adf Mon Sep 17 00:00:00 2001
From: Matt Joiner <anacrolix@gmail.com>
Date: Fri, 28 Nov 2014 12:04:15 -0600
Subject: [PATCH] Implement iplist package, for block lists

---
 iplist/iplist.go      | 70 +++++++++++++++++++++++++++++++++++++++++++
 iplist/iplist_test.go | 59 ++++++++++++++++++++++++++++++++++++
 2 files changed, 129 insertions(+)
 create mode 100644 iplist/iplist.go
 create mode 100644 iplist/iplist_test.go

diff --git a/iplist/iplist.go b/iplist/iplist.go
new file mode 100644
index 00000000..b25c8228
--- /dev/null
+++ b/iplist/iplist.go
@@ -0,0 +1,70 @@
+package iplist
+
+import (
+	"bytes"
+	"fmt"
+	"net"
+	"regexp"
+	"sort"
+	"strings"
+)
+
+type IPList struct {
+	ranges []Range
+}
+
+type Range struct {
+	First, Last net.IP
+	Description string
+}
+
+// Create a new IP list. The given range must already sorted by the lower IP
+// in the range. Behaviour is undefined for lists of overlapping ranges.
+func New(initSorted []Range) *IPList {
+	return &IPList{
+		ranges: initSorted,
+	}
+}
+
+// Return the range the given IP is in. Returns nil if no range is found.
+func (me *IPList) Lookup(ip net.IP) (r *Range) {
+	// Find the index of the first range for which the following range exceeds
+	// it.
+	i := sort.Search(len(me.ranges), func(i int) bool {
+		if i+1 >= len(me.ranges) {
+			return true
+		}
+		return bytes.Compare(ip, me.ranges[i+1].First) < 0
+	})
+	if i == len(me.ranges) {
+		return
+	}
+	r = &me.ranges[i]
+	if bytes.Compare(ip, r.First) < 0 || bytes.Compare(ip, r.Last) > 0 {
+		r = nil
+	}
+	return
+}
+
+// Parse a line of the PeerGuardian Text Lists (P2P) Format. Returns !ok but
+// no error if a line doesn't contain a range but isn't erroneous, such as
+// comment and blank lines.
+func ParseBlocklistP2PLine(l string) (r Range, ok bool, err error) {
+	l = strings.TrimSpace(l)
+	if l == "" || strings.HasPrefix(l, "#") {
+		return
+	}
+	sms := regexp.MustCompile(`(.*):([\d.]+)-([\d.]+)`).FindStringSubmatch(l)
+	if sms == nil {
+		err = fmt.Errorf("error parsing %q", l)
+		return
+	}
+	r.Description = sms[1]
+	r.First = net.ParseIP(sms[2])
+	r.Last = net.ParseIP(sms[3])
+	if r.First == nil || r.Last == nil {
+		return
+	}
+	ok = true
+	return
+}
diff --git a/iplist/iplist_test.go b/iplist/iplist_test.go
new file mode 100644
index 00000000..d6ef083a
--- /dev/null
+++ b/iplist/iplist_test.go
@@ -0,0 +1,59 @@
+package iplist
+
+import (
+	"bufio"
+	"net"
+	"strings"
+	"testing"
+)
+
+var sample = `
+# List distributed by iblocklist.com
+
+a:1.2.4.0-1.2.4.255
+b:1.2.8.0-1.2.8.255`
+
+func TestSimple(t *testing.T) {
+	var ranges []Range
+	scanner := bufio.NewScanner(strings.NewReader(sample))
+	for scanner.Scan() {
+		r, ok, _ := ParseBlocklistP2PLine(scanner.Text())
+		if ok {
+			t.Log(r)
+			ranges = append(ranges, r)
+		}
+	}
+	if err := scanner.Err(); err != nil {
+		t.Fatalf("error while scanning: %s", err)
+	}
+	if len(ranges) != 2 {
+		t.Fatalf("expected 2 ranges but got %d", len(ranges))
+	}
+	iplist := New(ranges)
+	for _, _case := range []struct {
+		IP   string
+		Hit  bool
+		Desc string
+	}{
+		{"1.2.3.255", false, ""},
+		{"1.2.8.0", true, "b"},
+		{"1.2.4.255", true, "a"},
+		// Try to roll over to the next octet on the parse.
+		{"1.2.7.256", false, ""},
+		{"1.2.8.254", true, "b"},
+	} {
+		r := iplist.Lookup(net.ParseIP(_case.IP))
+		if !_case.Hit {
+			if r != nil {
+				t.Fatalf("got hit when none was expected")
+			}
+			continue
+		}
+		if r == nil {
+			t.Fatalf("expected hit for %q", _case.IP)
+		}
+		if r.Description != _case.Desc {
+			t.Fatalf("%q != %q", r.Description, _case.Desc)
+		}
+	}
+}
-- 
2.44.0