iplist/iplist.go

   1 // Package iplist handles the P2P Plaintext Format described by
   2 // https://en.wikipedia.org/wiki/PeerGuardian#P2P_plaintext_format.
   3 package iplist
   4
   5 import (
   6         "bufio"
   7         "bytes"
   8         "errors"
   9         "fmt"
  10         "io"
  11         "net"
  12         "sort"
  13 )
  14
  15 // An abstraction of IP list implementations.
  16 type Ranger interface {
  17         // Return a Range containing the IP.
  18         Lookup(net.IP) (r Range, ok bool)
  19         // If your ranges hurt, use this.
  20         NumRanges() int
  21 }
  22
  23 type IPList struct {
  24         ranges []Range
  25 }
  26
  27 type Range struct {
  28         First, Last net.IP
  29         Description string
  30 }
  31
  32 func (r Range) String() string {
  33         return fmt.Sprintf("%s-%s: %s", r.First, r.Last, r.Description)
  34 }
  35
  36 // Create a new IP list. The given ranges must already sorted by the lower
  37 // bound IP in each range. Behaviour is undefined for lists of overlapping
  38 // ranges.
  39 func New(initSorted []Range) *IPList {
  40         return &IPList{
  41                 ranges: initSorted,
  42         }
  43 }
  44
  45 func (ipl *IPList) NumRanges() int {
  46         if ipl == nil {
  47                 return 0
  48         }
  49         return len(ipl.ranges)
  50 }
  51
  52 // Return the range the given IP is in. ok if false if no range is found.
  53 func (ipl *IPList) Lookup(ip net.IP) (r Range, ok bool) {
  54         if ipl == nil {
  55                 return
  56         }
  57         // TODO: Perhaps all addresses should be converted to IPv6, if the future
  58         // of IP is to always be backwards compatible. But this will cost 4x the
  59         // memory for IPv4 addresses?
  60         v4 := ip.To4()
  61         if v4 != nil {
  62                 r, ok = ipl.lookup(v4)
  63                 if ok {
  64                         return
  65                 }
  66         }
  67         v6 := ip.To16()
  68         if v6 != nil {
  69                 return ipl.lookup(v6)
  70         }
  71         if v4 == nil && v6 == nil {
  72                 r = Range{
  73                         Description: "bad IP",
  74                 }
  75                 ok = true
  76         }
  77         return
  78 }
  79
  80 // Return a range that contains ip, or nil.
  81 func lookup(
  82         first func(i int) net.IP,
  83         full func(i int) Range,
  84         n int,
  85         ip net.IP,
  86 ) (
  87         r Range, ok bool,
  88 ) {
  89         // Find the index of the first range for which the following range exceeds
  90         // it.
  91         i := sort.Search(n, func(i int) bool {
  92                 if i+1 >= n {
  93                         return true
  94                 }
  95                 return bytes.Compare(ip, first(i+1)) < 0
  96         })
  97         if i == n {
  98                 return
  99         }
 100         r = full(i)
 101         ok = bytes.Compare(r.First, ip) <= 0 && bytes.Compare(ip, r.Last) <= 0
 102         return
 103 }
 104
 105 // Return the range the given IP is in. Returns nil if no range is found.
 106 func (ipl *IPList) lookup(ip net.IP) (Range, bool) {
 107         return lookup(func(i int) net.IP {
 108                 return ipl.ranges[i].First
 109         }, func(i int) Range {
 110                 return ipl.ranges[i]
 111         }, len(ipl.ranges), ip)
 112 }
 113
 114 func minifyIP(ip *net.IP) {
 115         v4 := ip.To4()
 116         if v4 != nil {
 117                 *ip = append(make([]byte, 0, 4), v4...)
 118         }
 119 }
 120
 121 // Parse a line of the PeerGuardian Text Lists (P2P) Format. Returns !ok but
 122 // no error if a line doesn't contain a range but isn't erroneous, such as
 123 // comment and blank lines.
 124 func ParseBlocklistP2PLine(l []byte) (r Range, ok bool, err error) {
 125         l = bytes.TrimSpace(l)
 126         if len(l) == 0 || bytes.HasPrefix(l, []byte("#")) {
 127                 return
 128         }
 129         // TODO: Check this when IPv6 blocklists are available.
 130         colon := bytes.LastIndexAny(l, ":")
 131         if colon == -1 {
 132                 err = errors.New("missing colon")
 133                 return
 134         }
 135         hyphen := bytes.IndexByte(l[colon+1:], '-')
 136         if hyphen == -1 {
 137                 err = errors.New("missing hyphen")
 138                 return
 139         }
 140         hyphen += colon + 1
 141         r.Description = string(l[:colon])
 142         r.First = net.ParseIP(string(l[colon+1 : hyphen]))
 143         minifyIP(&r.First)
 144         r.Last = net.ParseIP(string(l[hyphen+1:]))
 145         minifyIP(&r.Last)
 146         if r.First == nil || r.Last == nil || len(r.First) != len(r.Last) {
 147                 err = errors.New("bad IP range")
 148                 return
 149         }
 150         ok = true
 151         return
 152 }
 153
 154 // Creates an IPList from a line-delimited P2P Plaintext file.
 155 func NewFromReader(f io.Reader) (ret *IPList, err error) {
 156         var ranges []Range
 157         // There's a lot of similar descriptions, so we maintain a pool and reuse
 158         // them to reduce memory overhead.
 159         uniqStrs := make(map[string]string)
 160         scanner := bufio.NewScanner(f)
 161         lineNum := 1
 162         for scanner.Scan() {
 163                 r, ok, lineErr := ParseBlocklistP2PLine(scanner.Bytes())
 164                 if lineErr != nil {
 165                         err = fmt.Errorf("error parsing line %d: %s", lineNum, lineErr)
 166                         return
 167                 }
 168                 lineNum++
 169                 if !ok {
 170                         continue
 171                 }
 172                 if s, ok := uniqStrs[r.Description]; ok {
 173                         r.Description = s
 174                 } else {
 175                         uniqStrs[r.Description] = r.Description
 176                 }
 177                 ranges = append(ranges, r)
 178         }
 179         err = scanner.Err()
 180         if err != nil {
 181                 return
 182         }
 183         ret = New(ranges)
 184         return
 185 }