# -*- Mode: ruby; indent-tabs-mode: nil -*-
# vim:expandtab softtabstop=2 shiftwidth=2

# Net::CIDR
#
# Copyright 2001-2003 Sam Varshavchik.
#
# with contributions from David Cantrell.
#
# Ruby version Copyright 2006 Jos Backus.
#
# This program is free software; you can redistribute it
# and/or modify it under the same terms as Perl itself.
#
# Ruby version 1.1
#
# $Revision: 1.17 $

class Array
  def to_i
    self.map {|e| e.to_i}
  end
end

module Net
  module CIDR
    VERSION = "0.11"
    DEBUG = false

    class << self

      def debug(*msg)
        puts msg if DEBUG
      end

      def cidr2range(*cidrs_list)
        cidrs = cidrs_list.dup
        r = []

        until cidrs.empty?
          cidr = cidrs.shift

          cidr.gsub!(/\s/, '')

          unless cidr =~ /(.*)\/(.*)/
            r.push cidr
            next
          end

          ip, pfix = $1, $2

          isipv6, ip = _ipv6to4(ip)

          ips = ip.split(/\.+/)

          ips.each do |ip|
            raise unless ip.to_i >= 0 && ip.to_i <= 255 && ip =~ /^[0-9]+$/
          end

          raise unless pfix.to_i >= 0 && pfix.to_i <= ips.size * 8 && pfix =~ /^[0-9]+$/

          rr = _cidr2iprange(pfix, ips)

          until rr.empty?
            a = rr.shift
            b = rr.shift

            a.sub!(/\.$/, '')
            b.sub!(/\.$/, '')

            if isipv6
              a = _ipv4to6(a)
              b = _ipv4to6(b)
            end

            r.push "#{a}-#{b}"
          end
        end

        r
      end

      #
      # If the input is an IPv6-formatted address, convert it to an IPv4 decimal
      # format, since the other functions know how to deal with it.  The hexadecimal
      # IPv6 address is represented in dotted-decimal form, like IPv4.
      #

      def _ipv6to4(ipv6)

        return nil, ipv6 unless ipv6 =~ /:/

        raise "Syntax error: #{ipv6}" unless ipv6 =~ /^[a-fA-F0-9:\.]+$/

        ip4_suffix = ""

        ipv6, ip4_suffix = $1, $2 if ipv6 =~ /^(.*:)([0-9]+\.[0-9\.]+)$/

        ipv6.gsub!(/([a-fA-F0-9]+)/) {|m| _h62d(m)}

        ipv6_suffix = ""

        if ipv6 =~ /(.*)::(.*)/
          ipv6, ipv6_suffix = $1, $2
          ipv6_suffix += ".#{ip4_suffix}"
        else
          ipv6 += ".#{ip4_suffix}"
        end

        p = ipv6.split(/[^0-9]+/).grep(/./)

        s = ipv6_suffix.split(/[^0-9]+/).grep(/./)

        p.push 0 while (p.size - 1) + (s.size - 1) < 14

        n = (p + s).join(".")

        #    return false, $1 if n =~ /^0\.0\.0\.0\.0\.0\.0\.0\.0\.0\.255\.255\.(.*)$/

        return true, n
      end

      # Let's go the other way around

      def _ipv4to6(arg)
        octets = arg.split(/[^0-9]+/)

        raise "Internal error in _ipv4to6" unless octets.size == 16

        dummy = octets.dup

        return ("::ffff:" +
                [$octets[12], $octets[13], $octets[14], $octets[15]].join('.')) if \
                dummy[0, 12].join('.') == "0.0.0.0.0.0.0.0.0.0.255.255"

        words = []

        0.upto(7) do |i|
          words[i] = sprintf("%x", octets[i*2].to_i * 256 + octets[i*2+1].to_i)
        end

        ind = -1
        indlen = -1

        i = 0
        while i < 8
          unless words[i] == "0"
            i += 1
            next
          end

          j = i
          while j < 8
            debug "words[#{j}]=#{words[j]}"
            break if words[j] != "0"
            j += 1
          end
          debug "j=#{j}"

          if j - i > indlen
            indlen = j - i
            ind = i
            i = j - 1
          end
          i += 1
        end

        return "::" if indlen == 8

        return words.join(":") if ind < 0

        s = words.slice!(ind + indlen) || []

        return words[0, ind].join(":") + "::" + s.join(":")
      end

      def _h62d(h)
        h = h.hex

        return Integer(h / 256.0).to_s + "." + (h % 256).to_s
      end

      def _cidr2iprange(pfix, ips_list)
        ips = ips_list.dup.to_i
        pfix = pfix.to_i
        debug "ips=#{ips.inspect}, pfix=#{pfix}"

        if pfix == 0
          debug "A0 ips=#{ips.inspect}"
          ips.fill(0)
          debug "A1 ips=#{ips.inspect}"

          ips2 = ips.dup

          debug "B0 ips=#{ips2.inspect}"
          ips2.fill(255)
          debug "B1 ips=#{ips2.inspect}"

          debug "pfix == 0: #{ips.join(".") + ips2.join(".")}"
          return [ips.join("."), ips2.join(".")]
        end

        if pfix >= 8
          octet = ips.shift

          debug "_cidr2iprange(#{pfix - 8}, #{ips.inspect})"
          ips = _cidr2iprange(pfix - 8, ips)
          debug "from _cidr2iprange: ips=#{ips.inspect}"

          ips.map! {|i| i = "#{octet}.#{i}"}
          debug "pfix > 8: #{ips.inspect}"
          return ips
        end

        octet = ips.shift

        ips.fill(0)

        ips2 = ips.dup

        ips2.fill(255)

        debug "_cidr2range8([#{octet}, #{pfix}])"
        r = _cidr2range8([octet, pfix])
        debug "r=#{r.inspect}"

        r[0] = ([r[0]] + ips).join(".")
        r[1] = ([r[1]] + ips2).join(".")

        return r
      end

      #
      # ADDRESS to list of CIDR netblocks
      #

      def addr2cidr(arg)
        blocks = []
        isIPv6, addr = _ipv6to4(arg)
        bitsInAddress = isIPv6 ? 128 : 32

        address = 0

        addr.split(/\./).each do |a|
          address = address << 8
          address = address + a.to_i
        end

        bitsInAddress.downto(0) do |bits|
          octetstash = 255
          bitmask = 0
          1.upto(bits) { bitmask = (bitmask << 1) + 1 }
          bitmask = bitmask << (bitsInAddress - bits)
          net = address & bitmask
          debug "octetstash=#{octetstash}, bitmask=#{bitmask}"

          blocks.push((0..(bitsInAddress / 8 - 1)).map {|i|
            temp = (octetstash & net) >> (i * 8)
            octetstash = octetstash << 8
            temp
          }.reverse.join('.').map {|i|
            i.gsub!(/\+/, '')
            isIPv6 ? _ipv4to6(i) : i
          }[0] + "/#{bits}")
        end

        return blocks
      end

      # Address and netmask to CIDR

      def addrandmask2cidr(address, arg)
        a_isIPv6, = _ipv6to4(address)
        n_isIPv6, netmask = _ipv6to4(arg)
        debug "a_isIPv6=#{a_isIPv6}, n_isIPv6=#{n_isIPv6}, netmask=#{netmask}"
        raise "Both address and netmask must be the same type" if a_isIPv6 && n_isIPv6 && a_isIPv6 != n_isIPv6
        bitsInNetmask = 0
        previousNMoctet = 255
        netmask.split(/\./).to_i.each do |octet|
          raise "Invalid netmask" if previousNMoctet != 255 && octet != 0
          previousNMoctet = octet
          bitsInNetmask +=
            (octet == 255) ? 8 :
            (octet == 254) ? 7 :
            (octet == 252) ? 6 :
            (octet == 248) ? 5 :
            (octet == 240) ? 4 :
            (octet == 224) ? 3 :
            (octet == 192) ? 2 :
            (octet == 128) ? 1 :
            (octet == 0) ? 0 : raise("Invalid netmask")
        end
        return addr2cidr(address).grep(/\/#{bitsInNetmask}$/)[0]
      end

        #
        # START-FINISH to CIDR list
        #

      def range2cidr(*r_arg)
        r = r_arg.dup
        c = []

        0.upto(r.size - 1) do |i|
          r[i].gsub!(/\s/, '')

          if r[i] =~ /\//
            c.push r[i]
            next
          end

          r[i] = "#{r[i]}-#{r[i]}" unless r[i] =~ /(.*)-(.*)/
          r[i] =~ /(.*)-(.*)/

          a, b = $1, $2

          isipv6_1, a = _ipv6to4(a)
          isipv6_2, b = _ipv6to4(b)

          if isipv6_1 || isipv6_2
            raise "Invalid netblock range: #{r[i]}" unless isipv6_1 && isipv6_2
          end

          a_arr = a.split(/\.+/)
          b_arr = b.split(/\.+/)

          raise unless a_arr.size == b_arr.size

          cc = _range2cidr(a_arr, b_arr)
          debug "cc=#{cc.inspect}"

          until cc.empty?
            a = cc.shift
            b = cc.shift

            a = _ipv4to6(a) if isipv6_1
            debug "a=#{a}"

            c.push "#{a}/#{b}"
          end
        end
        return c
      end

      def _range2cidr(a_arr_arg, b_arr_arg)
        a_arr = a_arr_arg.dup.to_i
        b_arr = b_arr_arg.dup.to_i
        a = a_arr.shift.to_i
        b = b_arr.shift.to_i

        # XXX
        return _range2cidr8(a, b) if a_arr.size < 0; # Least significant octet pair.

        raise unless a >= 0 && a <= 255 && a.to_s =~ /^[0-9]+$/
        raise unless b >= 0 && b <= 255 && b.to_s =~ /^[0-9]+$/ && b >= a

        c = []

        if a == b # Same start/end octet
          debug "same start/end octet"
          debug "recursing into _range2cidr(#{a_arr.inspect}, #{b_arr.inspect})"
          cc = _range2cidr(a_arr, b_arr)
          debug "recursed from _range2cidr: cc=#{cc.inspect}"

          until cc.empty?
            c1 = cc.shift
            c.push "#{a}.#{c1}"

            c1 = cc.shift
            c.push c1 + 8
          end
          debug "_range2cidr: c=#{c.inspect}"
          return c
        end

        start0 = 1
        end255 = 1

        a_arr.each { |e| start0 = 0 unless e == 0 }
        b_arr.each { |e| end255 = 0 unless e == 255 }

        debug "start0=#{start0}"
        if start0 == 0
          debug "start0 (#{start0}) == 0"
          b_arr_copy = b_arr.dup

          b_arr_copy.fill(255)

          debug "recursing 2 into _range2cidr(#{a_arr.inspect}, #{b_arr_copy.inspect})"
          cc = _range2cidr(a_arr, b_arr_copy)
          debug "recursed 2 from _range2cidr: cc=#{cc.inspect}"

          until cc.empty?
            c1 = cc.shift
            c.push "#{a}.#{c1}"

            c1 = cc.shift
            c.push c1 + 8
          end

          a += 1
        end

        if end255 == 0
          debug "end255 (#{end255}) == 0"
          a_arr_copy = a_arr.dup

          a_arr_copy.fill(0)

          debug "recursing 3 into _range2cidr(#{a_arr_copy.inspect}, #{b_arr.inspect})"
          cc = _range2cidr(a_arr_copy, b_arr)
          debug "recursed 3 from _range2cidr: cc=#{cc.inspect}"

          until cc.empty?
            c1 = cc.shift
            c.push "#{b}.#{c1}"

            c1 = cc.shift
            c.push c1 + 8
          end

          b -= 1
        end

        if a <= b
          a_arr.fill(0)

          pfix = a_arr.join(".")

          debug "calling _range2cidr8(#{a}, #{b})"
          cc = _range2cidr8(a, b)
          debug "returning from _range2cidr8: cc=#{cc.inspect}"

          until cc.empty?
            c1 = cc.shift
            c.push "#{c1}.#{pfix}"

            c1 = cc.shift
            c.push c1
          end
        end
        return c
      end

      def _range2cidr8(*r_arg)
        debug "_range2cidr8(#{r_arg.inspect})"
        r = r_arg.dup
        c = []
        until r.empty?
          a = r.shift
          b = r.shift

          raise unless a >= 0 && a <= 255 && a.to_s =~ /^[0-9]+$/
          raise unless b >= 0 && b <= 255 && b.to_s =~ /^[0-9]+$/ && b >= a

          b += 1

          while a < b
            i = 0
            n = 1

            while (n & a) == 0
              i += 1
              n <<= 1
              break if i >= 8
            end

            while i && n + a > b
              i -= 1
              n >>= 1
            end

            c.push a
            c.push 8 - i

            a += n
          end
        end

        debug "_range2cidr8 -> (#{c.inspect})"
        return c
      end

      def _cidr2range8(c_arg)
        c = c_arg.dup

        r = []

        until c.empty?
          a = c.shift
          b = c.shift

          raise unless a >= 0 && a <= 255 && a.to_s =~ /^[0-9]+$/
          raise unless b >= 0 && b <= 8 && b.to_s =~ /^[0-9]+$/

          n = 1 << (8 - b)

          a &= (n - 1) ^ 255

          r.push a
          r.push a + (n - 1)
        end
        return r
      end

      def _ipcmp(aa, bb)
        debug "_ipcmp(#{aa}, #{bb})"
        isipv6_1, aa =_ipv6to4(aa)
        isipv6_2, bb =_ipv6to4(bb)

        if isipv6_1 || isipv6_2
          raise "Invalid netblock: #{aa}-#{bb}" unless isipv6_1 && isipv6_2
        end

        debug "aa=#{aa}"
        raise unless aa
        a = aa.split(/\./)
        b = bb.split(/\./)

        raise unless a.size == b.size

        while !a.empty? && a[0] == b[0]
          a.shift
          b.shift
        end

        return 0 if a.empty?

        return a[0] <=> b[0]
      end

=begin

   =head2 @octet_list=Net::CIDR::cidr2octets(@cidr_list)

   cidr2octets() takes @cidr_list and returns a list of leading octets
   representing those netblocks.  Example:

     @octet_list=Net::CIDR::cidr2octets("10.0.0.0/14", "192.68.0.0/24")

   The result is the following five-element array:
     ("10.0", "10.1", "10.2", "10.3", "192.68.0").

     For IPv6 addresses, the hexadecimal words in the resulting list are
   zero-padded:

     @octet_list=Net::CIDR::cidr2octets("::dead:beef:0:0/110")

   The result is a four-element array:
     ("0000:0000:0000:0000:dead:beef:0000",
      "0000:0000:0000:0000:dead:beef:0001",
      "0000:0000:0000:0000:dead:beef:0002",
      "0000:0000:0000:0000:dead:beef:0003").
      Prefixes of IPv6 CIDR blocks should be even multiples of 16 bits, otherwise
   they can potentially expand out to a 32,768-element array, each!

=end

      def cidr2octets(*cidr_list)
        cidr = cidr_list.dup
        r = []

        until cidr.empty?
          cidr1 = cidr.shift

          cidr1.gsub!(/\s/, '')

          raise unless cidr1 =~ /(.*)\/(.*)/

          ip, pfix = $1, $2.to_i

          isipv6, ip =_ipv6to4(ip)

          ips = ip.split(/\.+/).to_i

          ips.each do |i|
            raise unless i >= 0 && i <= 255 && i.to_s =~ /^[0-9]+$/
          end

          raise unless pfix >= 0 && pfix <= ips.size * 8 && pfix.to_s =~ /^[0-9]+$/

          i = 0
          0.upto(ips.size) do |i|
            break if pfix - i * 8 < 8
          end

          msb = ips.slice!(0, i)

          bitsleft = pfix - i * 8
          debug "bitsleft=#{bitsleft}"

          if ips.empty? || bitsleft == 0
            if isipv6
              _push_ipv6_octets(r, msb)
            else
              r.push msb.join(".")
            end
            next
          end

          debug "_cidr2range8([#{ips[0]}, #{bitsleft}])"
          rr = _cidr2range8([ips[0], bitsleft])
          debug "rr=#{rr.inspect}"

          debug "r (begin)=#{r.inspect}"
          until rr.empty?
            a = rr.shift
            b = rr.shift

            (a..b).each do |i|
              if isipv6
                msb.push i
                _push_ipv6_octets(r, msb)
                debug "r=#{r.inspect}"
                msb.pop
              else
                r.push [msb + [i]].join(".")
              end
            end
          end
        end

        return r
      end

      def _push_ipv6_octets(ary_ref, octets_arg)
        octets = octets_arg.dup
        debug "ary_ref=#{ary_ref.inspect}, octets_arg=#{octets_arg.inspect}"

        if octets.size - 1 % 2 == 0    # Odd number of octets
          (0..255).each do |i|
            octets.push i
            _push_ipv6_octets(ary_ref, octets)
            octets.pop
          end
          return
        end

        s = ""

        (0..octets.size - 1).step(2) do |i|
          s += ":" unless s.empty?
          s += sprintf("%02x%02x", octets[i], octets[i + 1])
        end
        ary_ref.push s
      end

=begin

   =head2 @cidr_list=Net::CIDR::cidradd($block, @cidr_list)

   The cidradd() functions allows a CIDR list to be built one CIDR netblock
   at a time, merging adjacent and overlapping ranges.
     $block is a single netblock, expressed as either "start-finish", or
   "address/prefix".
     Example:

     @cidr_list=Net::CIDR::range2cidr("192.68.0.0-192.68.0.255")
   @cidr_list=Net::CIDR::cidradd("10.0.0.0/8", @cidr_list)
   @cidr_list=Net::CIDR::cidradd("192.68.1.0-192.68.1.255", @cidr_list)

   The result is a two-element array: ("10.0.0.0/8", "192.68.0.0/23").
     IPv6 addresses are handled in an analogous fashion.

=end

      def cidradd(ip, cidr_list)
        cidr = cidr_list.dup

        ip = "#{ip}-#{ip}" unless ip =~ /[-\/]/

        cidr.unshift ip

        debug "cidradd: cidr=#{cidr.inspect}"
        cidr = cidr2range(*cidr)

        a = []
        b = []

        cidr.each do |e|
          raise unless e =~ /(.*)-(.*)/
          a.push $1
          b.push $2
        end

        lo = a.shift
        hi = b.shift

        debug "a=#{a.inspect}"
        debug "b=#{b.inspect}"

        0.upto(a.size - 1) do |i|
          debug "iter=#{i}"
          break if _ipcmp(lo, hi) > 0

          next if _ipcmp(b[i], lo) < 0
          next if _ipcmp(hi, a[i]) < 0

          if _ipcmp(a[i], lo) <= 0 && _ipcmp(hi, b[i]) <= 0
            lo = _add1(hi)
            break
          end

          if _ipcmp(a[i], lo) <= 0
            lo = _add1(b[i])
            next
          end

          if _ipcmp(hi, b[i]) <= 0
            hi = _sub1(a[i])
            next
          end

          a[i] = nil
          b[i] = nil
        end

        unless (! lo) || (! hi) || _ipcmp(lo, hi) > 0
          a.push lo
          b.push hi
        end

        cidr = []

        a.compact!
        b.compact!

        0.upto(a.size - 1) do |i|
          cidr.push "#{a[i]}-#{b[i]}"
        end

        @cidr = cidr.sort {|a, b|
          a =~ /(.*)-/
          c = $1
          b =~ /(.*)-/
          d = $1
          e = _ipcmp(c, d)
          e
        }

        i = 0
        while i < cidr.size - 1
          cidr[i] =~ /(.*)-(.*)/

          k, l = $1, $2

          cidr[i + 1] =~ /(.*)-(.*)/

          m, n = $1, $2

          if _ipcmp( _add1(l), m) == 0
            cidr[i, 2] = "#{k}-#{n}"
            next
          end
          i += 1
        end

        return range2cidr(*cidr)
      end


      def _add1(n)
        isipv6, n = _ipv6to4(n)

        ip = n.split(/\./).to_i

        i = ip.size - 1

        while i >= 0
          break if (ip[i] += 1) < 256
          ip[i] = 0
          i -= 1
        end

        return nil if i < 0

        i = ip.join(".")
        i = _ipv4to6(i) if isipv6
        return i
      end

      def _sub1(n)
        isipv6, n = _ipv6to4(n)

        ip = n.split(/\./).to_i

        i = ip.size - 1

        while i >= 0
          break if (ip[i] -= 1) >= 0
          ip[i] = 255
          i -= 1
        end

        return nil if i < 0

        i = ip.join(".")
        i = _ipv4to6(i) if isipv6
        return i
      end

=begin

   =head2 $found=Net::CIDR::cidrlookup($ip, @cidr_list)

   Search for $ip in @cidr_list.  $ip can be a single IP address, or a
   netblock in CIDR or start-finish notation.
     lookup() returns 1 if $ip overlaps any netblock in @cidr_list, 0 if not.

=end

      def cidrlookup(ip, cidr_list)
        cidr = cidr_list.dup

        ip = "#{ip}-#{ip}" unless ip =~ /[-\/]/

        cidr.unshift ip

        cidr = cidr2range(*cidr)
        debug "cidr=#{cidr.inspect}"

        a = []
        b = []

        cidr.each do |e|
          debug "-> #{e}"
          raise unless e =~ /(.*)-(.*)/
          a.push $1
          b.push $2
        end
        debug "a=#{a.inspect}"
        debug "b=#{b.inspect}"

        lo = a.shift
        hi = b.shift

        0.upto(a.size - 1) do |i|
          next if _ipcmp(b[i], lo) < 0
          next if _ipcmp(hi, a[i]) < 0
          return true
        end

        return false
      end

=begin

   =head2 $ip=Net::CIDR::cidrvalidate($ip)

   Validate whether $ip is a valid IPv4 or IPv6 address.
     Returns its argument or undef.
     Spaces are removed, and IPv6 hexadecimal address are converted to lowercase.

=end

      def cidrvalidate(v_arg)
        v = v_arg.dup
        v.gsub!(/\s/, '')

        v.downcase!

        if v =~ /^([0-9\.]+)$/ || v =~ /^::ffff:([0-9\.]+)$/ ||
          v =~ /^:([0-9\.]+)$/
          n = $1

          return nil if n =~ /^\./ || n =~ /\.$/ || n =~ /\.\./

          o = n.split(/\./).to_i

          return nil if o.size - 1 != 3

          o.each do |e|
            return nil if e.to_s =~ /^0./
            return nil if e < 0 || e > 255
          end
          return v
        end

        return nil unless v =~ /^[0-9a-f:]+$/

        return nil if v =~ /:::/ || v =~ /^:[^:]/ || v =~ /[^:]:$/ || v =~ /::.*::/

        o = v.split(/:/).grep(/./)

        return nil if (o.size - 1 >= 8 || (o.size - 1 < 7 && v !~ /::/))

        o.each do |e|
          return nil if e.length > 4
        end

        return v
      end

    end # class << self

  end # module CIDR
end # module Net

=begin

=head1 BUGS

Garbage in, garbage out.
Always use validate() before doing anything with untrusted input.
Otherwise,
"slightly" invalid input will work (extraneous whitespace
is generally OK),
but the functions will croak if you're totally off the wall.

=head1 AUTHOR

Sam Varshavchik <sam@email-scan.com>

With some contributions from David Cantrell <david@cantrell.org.uk>

Ruby translation by Jos Backus <jos@catnook.com>

=end

__END__