#!/usr/bin/env python

import sys
import struct
import socket

def dotted_quad_to_num(network):
    """Convert a 'dotted quad' string to an unsigned integer.

    '192.168.1.1' -> NUM
    The number is returned in host byte order.
    """
    try:
        return long(struct.unpack('>L',socket.inet_aton(network))[0])
    except socket.error, e:
        raise Exception(e.__str__())

def num_to_dotted_quad(network):
    """Convert an unsigned integer into a 'dotted quad' string.

    NUM -> '192.168.1.1'
    The number must be given in host byte order.
    """
    return socket.inet_ntoa(struct.pack('>L', network))

def bitcount_to_num(netmask):
    """Return an unsigned integer with 'netmask' bits set.

    ie. convert a '/24' netmask count to an integer.
    The returned value is in host byte order.
    """
    res = 0L
    for n in range(netmask):
        res |= 1<<31 - n
    return res

# This will _not_ make sure the netmask is valid.
def num_to_bitcount(netmask):
    """Count the number of bits set in a netmask number.

    The number must be given in host byte order.
    No validation is done to verify that the given value is a real
    netmask, use id_valid_netmask() for that.
    """
    bits = 0
    for n in range(32):
        if ((netmask >> n) & 1) == 1:
            bits += 1
    return bits

def fits_in_range(start, end, size, mask):
    pos = start
    while pos <= end:
        t_start = pos & mask
        t_end = t_start + (0xffffffff - mask)
        if t_start >= start and t_end <= end:
            return True
        pos += size

    return False

def snarf(start, end, size, mask):
    pos = start
    while pos <= end:
        t_start = pos & mask
        t_end = t_start + (0xffffffff - mask)
        if t_start >= start and t_end <= end:
            break
        pos += size

    ret = {}
    ret['snarfed_start'] = t_start
    ret['snarfed_mask'] = mask

    if start < t_start:
        ret['pre_start'] = start
        ret['pre_end'] = t_start - 1

    if t_end < end:
        ret['post_start'] = t_end + 1
        ret['post_end'] = end

    return ret


def main():
    if len(sys.argv) != 3:
        print 'Usage: %s start-address end-address' % (sys.argv[0])
        sys.exit(1)

    cidrsizes = {}
    for n in range(33):
        cidrsizes[n] = ((1 << 32 - n), bitcount_to_num(n))

#    print cidrsizes

    try:
        start = dotted_quad_to_num(sys.argv[1])
    except Exception, e:
        print 'Invalid start address: %s.' % (e)
        sys.exit(1)

    try:
        end = dotted_quad_to_num(sys.argv[2])
    except Exception, e:
        print 'Invalid end address: %s.' % (e)
        sys.exit(1)

    if end < start:
        print 'end > start == bad.'
        sys.exit(1)

    results = []
    ranges = [(start, end)]

    while len(ranges) > 0:
        start, end = ranges[0]
        size = end - start + 1
        for csize in cidrsizes:
            if size >= cidrsizes[csize][0]:
                if not fits_in_range(start, end, cidrsizes[csize][0],
                                     cidrsizes[csize][1]):
                    continue
                snarf_res = snarf(start, end, cidrsizes[csize][0],
                                  cidrsizes[csize][1])
                results.append((snarf_res['snarfed_start'],
                                snarf_res['snarfed_mask']))

                ranges.pop(0)
                if 'pre_start' in snarf_res:
                    ranges.append((snarf_res['pre_start'], snarf_res['pre_end']))
                if 'post_start' in snarf_res:
                    ranges.append((snarf_res['post_start'], snarf_res['post_end']))

                break

            if len(ranges) == 0:
                break

    results.sort()
    for start, mask in results:
        print '%s/%d' % (num_to_dotted_quad(start), num_to_bitcount(mask))

if __name__ == '__main__':
    main()