#!/usr/bin/env python

"""
CIDR Merge

Merge and de-dupe overlapping or adjacent IP ranges.

Copyright (c) 2018, Kris Feldmann
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

  1. Redistributions of source code must retain the above copyright
     notice, this list of conditions and the following disclaimer.

  2. Redistributions in binary form must reproduce the above
     copyright notice, this list of conditions and the following
     disclaimer in the documentation and/or other materials provided
     with the distribution.

  3. Neither the name of the copyright holder nor the names of its
     contributors may be used to endorse or promote products derived
     from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER
OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
"""


import sys
import os
import copy

def usage():
    """
    Print the usage statement to stderr and exit.
    """
    sys.stderr.write( \
        'Usage: ./cidrmerge < cidr_list [cidr_list...] > output\n')
    raise SystemExit(2)

def _d(message):
    """
    If the environment variable DEBUG has been set, write
    a debugging message to stderr.
    """
    if os.environ.get('DEBUG'):
        sys.stderr.write('DEBUG: %s\n' % message)
    return None

def _e(message):
    """
    Print an ERROR message to stderr and exit.
    """
    sys.stderr.write('ERROR: %s\n' % message)
    raise SystemExit(1)

def __ip_to_int(ipaddr): # return int
    """
    Convert an ipv4 "dotted-quad" string to an integer.
    """
    _d('Starting __ip_to_int() with %s' % ipaddr)
    a, b, c, d = ipaddr.split('.')
    i = int(a)*(2**24)
    i += int(b)*(2**16)
    i += int(c)*(2**8)
    i += int(d)
    _d('Returning from __ip_to_int() with %d' % i)
    return i

def __int_to_ip(i): # return string
    """
    Convert an integer to an ipv4 "dotted-quad" string.
    """
    _d('Starting __int_to_ip() with %d' % i)
    a = i // 2**24
    b = (i - a * 2**24) // 2**16
    c = (i - a * 2**24 - b * 2**16) // 2**8
    d = (i - a * 2**24 - b * 2**16 - c * 2**8)
    _d('Returning from __int_to_ip() with %d.%d.%d.%d' % (a, b, c, d))
    return '%d.%d.%d.%d' % (a, b, c, d)

def __cidr_to_range(cidr): # return tuple of 2 ints
    """
    Find starting and ending IPs of the provided CIDR
    and return those two addresses as a tuple of integers.
    """
    if '/' in cidr:
        ip, maskbits_s = cidr.split('/', 1)
        mbits = int(maskbits_s)
        if mbits < 1 or mbits > 32:
            raise ValueError( \
                '[%s] Invalid network mask size: %d' % (cidr, mbits))
        start = __ip_to_int(ip)
        end = start + 2 ** (32 - mbits) - 1
        if start % (2 ** (32 - mbits)) != 0:
            x = start - (start % (2 ** (32 - mbits)))
            suggested_start0 = __int_to_ip(x)
            suggested_start1 = __int_to_ip(x + (1 << (32 - mbits)))
            raise ValueError( \
                '[%s] Invalid starting address for /%d. Try %s or %s' \
                % (cidr, mbits, suggested_start0, suggested_start1))
    else:
        start = __ip_to_int(cidr)
        end = start
    return (start, end)

def __range_to_cidrs(range_list): # return list of strings
    """
    From a list of IP ranges (each provided as a tuple of integers),
    produce a list of CIDR strings that together cover all ranges
    without duplication or overlap.
    """
    _d('Starting __range_to_cidrs() with input: %s(%s)' \
       % (type(range_list), repr(range_list)))
    outlist = []
    a = range_list[0]
    b = range_list[1]
    span = b - a + 1
    _d('Span = %d' % span)
    if span == 1:
        _d('outlist.append: %s - %s --> %s/32' \
           % (a, b, __int_to_ip(a)))
        outlist.append('%s/32' % __int_to_ip(a))
        return outlist
    i = 0
    while i < 33:
        x = span >> i
        if x == 1:
            while True:
                if a % (2 ** i) == 0:
                    break
                elif i == -1:
                    raise ValueError('Failed to construct a valid CIDR!')
                else:
                    _d('Invalid mask. Working backwards now to find one that will work.')
                    i -= 1
            mbits = 32 - i
            _d('outlist.append: %s - %s --> %s/%d' % \
             (a, b, __int_to_ip(a), mbits))
            outlist.append('%s/%d' % (__int_to_ip(a), mbits))
            consumed = (1 << i)
            remainder = span - consumed
            _d('Remainder = %d' % remainder)
            if remainder > 0:
                a += consumed
                span = remainder
                _d('remainder > 0; new starting point a = %s, span = %s' % (a, span))
                i = 0
            else:
                break
        elif x == 0:
            raise ValueError( \
                "Failed to identify suitable mask size for span=%s" \
                % span)
        else:
            i += 1
    return outlist

def __compare_ranges(a, b): # return None or tuple
    """
    Compare two ranges. If the two can be replaced with one,
    return that one range (tuple), otherwise return None.
    """
    # identical
    if a[0] == b[0] and a[1] == b[1]:
        _d("__compare_ranges: %s and %s are identical" \
           % (repr(a), repr(b)))
        return None
    # a completely inside b
    if a[0] >= b[0] and a[1] <= b[1]:
        _d("__compare_ranges: %s is inside %s" \
           % (repr(a), repr(b)))
        return b
    # b completely inside a
    if b[0] >= a[0] and b[1] <= a[1]:
        _d("__compare_ranges: %s is inside %s" \
           % (repr(b), repr(a)))
        return None
    # aaaa
    #   bbbb  <- a/b overlap or immediately adjacent
    if a[0] < b[0] and a[1] < b[1] and b[0] <= a[1]+1:
        _d("__compare_ranges: a/b overlap: a=%s, b=%s" \
           % (repr(a), repr(b)))
        return (a[0], b[1])
    #   aaaa
    # bbbb    <- b/a overlap or immediately adjacent
    if b[0] < a[0] and b[1] < a[1] and a[0] <= b[1]+1:
        _d("__compare_ranges: b/a overlap: a=%s, b=%s" \
           % (repr(a), repr(b)))
        return (b[0], a[1])
    # no change
    _d("__compare_ranges: a and b do not overlap: a=%s, b=%s" \
       % (repr(a), repr(b)))
    return None


RANGES = []
OUT_RANGES = []
ITERATIONS = 0

if len(sys.argv) > 1:
    usage()

# Input
while True:
    LINE = sys.stdin.readline()
    if LINE == '':
        break
    C = LINE.find('#')
    if C != -1:
        LINE = LINE[:C]
    if LINE.strip() == '':
        continue
    try:
        _d('%s -> %s' % (LINE.strip(), __cidr_to_range(LINE.strip())))
        RANGES.append(__cidr_to_range(LINE.strip()))
    except ValueError as ex:
        _e(str(ex))

# Merge
while True:
    ITERATIONS += 1
    _d('Starting merge iteration %d' % ITERATIONS)
    RANGES.sort()
    for A in RANGES:
        for B in RANGES:
            result = __compare_ranges(A, B)
            if result:
                _d('Replacing %s with %s' % (repr(A), repr(result)))
                A = copy.deepcopy(result)
            else:
                _d('No merge; continue with %s' % repr(A))
        if not A in OUT_RANGES:
            _d('Adding %s to the output' % repr(A))
            OUT_RANGES.append(A)
        else:
            _d('%s is already in the output, skipping' % repr(A))
    if sorted(RANGES) == sorted(OUT_RANGES):
        break
    else:
        RANGES = copy.deepcopy(OUT_RANGES)
        OUT_RANGES = []

# Output
for R in sorted(OUT_RANGES):
    try:
        for C in  __range_to_cidrs(R):
            sys.stdout.write('%s\n' % C)
    except ValueError as ex:
        _e(str(ex))
