/*
** Copyright (C) 2007 by Carnegie Mellon University.
**
** @OPENSOURCE_HEADER_START@
** 
** Use of the SILK system and related source code is subject to the terms 
** of the following licenses:
** 
** GNU Public License (GPL) Rights pursuant to Version 2, June 1991
** Government Purpose License Rights (GPLR) pursuant to DFARS 252.225-7013
** 
** NO WARRANTY
** 
** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER 
** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY 
** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN 
** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY 
** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT 
** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE, 
** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE 
** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT, 
** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY 
** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF 
** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES. 
** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF 
** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON 
** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE 
** DELIVERABLES UNDER THIS LICENSE.
** 
** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie 
** Mellon University, its trustees, officers, employees, and agents from 
** all claims or demands made against them (and any related losses, 
** expenses, or attorney's fees) arising out of, or relating to Licensee's 
** and/or its sub licensees' negligent use or willful misuse of or 
** negligent conduct or willful misconduct regarding the Software, 
** facilities, or other rights or assistance granted by Carnegie Mellon 
** University under this License, including, but not limited to, any 
** claims of product liability, personal injury, death, damage to 
** property, or violation of any laws or regulations.
** 
** Carnegie Mellon University Software Engineering Institute authored 
** documents are sponsored by the U.S. Department of Defense under 
** Contract F19628-00-C-0003. Carnegie Mellon University retains 
** copyrights in all material produced under this contract. The U.S. 
** Government retains a non-exclusive, royalty-free license to publish or 
** reproduce these documents, or allow others to do so, for U.S. 
** Government purposes only pursuant to the copyright license under the 
** contract clause at 252.227.7013.
** 
** @OPENSOURCE_HEADER_END@
*/

/*
**  Miscellaneous functions for dealing with IP addresses.
**
*/


#include "silk.h"

RCSIDENT("$SiLK: sku-ips.c 6961 2007-04-18 18:01:43Z mthomas $");

#include "utils.h"


/* LOCAL VARIABLES */

/* masks of various sizes used when computing CIDR blocks */
static const uint32_t bitmask[] = {
    /*  0- 3 */ 4294967295U, 2147483647, 1073741823,  536870911,
    /*  4- 7 */  268435455,   134217727,   67108863,   33554431,
    /*  8-11 */   16777215,     8388607,    4194303,    2097151,
    /* 12-15 */    1048575,      524287,     262143,     131071,
    /* 16-19 */      65535,       32767,      16383,       8191,
    /* 20-23 */       4095,        2047,       1023,        511,
    /* 24-27 */        255,         127,         63,         31,
    /* 28-31 */         15,           7,          3,          1,
    /* 32    */          0
};


/* FUNCTION DEFINITIONS */


/* compute a CIDR block */
int skComputeCIDR(
    uint32_t    start_ip,
    uint32_t    end_ip,
    uint32_t   *new_start_ip)
{
    uint32_t xor_bits;
    int bit_count;
    uint32_t range_start;

    if (end_ip < start_ip) {
        return -1;
    }
    if (start_ip == end_ip) {
        if (new_start_ip) {
            *new_start_ip = 0;
        }
        return 32;
    }

    /* find the location of the most significant bit where the
     * start_ip and end_ip differ by taking the bitwise XOR of them
     * and then masking bits until we find the value. */
    xor_bits = (start_ip ^ end_ip);
    for (bit_count = 31;
         (bitmask[bit_count] <= xor_bits) && (bit_count > 0);
         --bit_count);

    /* the range is too wide; tighten it until we match the start of
     * the range */
    do {
        /* need to back-up one */
        ++bit_count;

        /* get the range of IPs covered by 'bit_count' bits */
        range_start = (start_ip & ~(bitmask[bit_count]));
    } while (range_start < start_ip);

    /* assert that the CIDR block is within the limits */
    assert(range_start == start_ip);
    assert((range_start | (bitmask[bit_count])) <= end_ip);

    if (new_start_ip) {
        /* compute the start of the next CIDR block, which is the IP
         * after the block we just finished.  In the case of
         * roll-over, the 'else' clause will be invoked, and we will
         * return 0. */
        start_ip = 1 + (range_start | (bitmask[bit_count]));
        if (start_ip > end_ip) {
            *new_start_ip = 0;
        } else {
            *new_start_ip = start_ip;
        }
    }
    return bit_count;
}


/*
** Local Variables:
** mode:c
** indent-tabs-mode:nil
** c-basic-offset:4
** End:
*/