#if HAVE_CONFIG_H
#include <ntm_conf.h>
#endif

#include <stdlib.h>                 /* exit() */
#include <stdio.h>                  /* printf() FILE */
#include <string.h>                 /* strlen() strcat() */

#include "../integrat/subnet.h"     /* Subnet SubnetTree boolean */
#include "../wattcp/tcp.h"          /* inet_ntoa() */
#include "../integrat/constant.h"   /* DO_FOREGROUND_STATS */
#include "../dpmi32/flat.h"         /* flat_alloc() */
#ifdef __unix__
#define heapcheck() 1
#else
#include "../intel/byteswap.h"      /* htonl() */
#include <alloc.h>                  /* heapcheck() */
#endif



/* none of this code gets compiled in
 * if it's isn't going to be called
 */
#if DO_FOREGROUND_STATS



#define SUBNET_FIND_TIMING      TRUE



/* how many nodes should be in the tree now?
 */
static unsigned subnet_node_count = 0;

static unsigned subnets_per_mask_length[ MAX_ADDR_BITS ];
static unsigned find_refcnt = 0;
#if !defined(__unix__) && !NETRAMET
    static PentiumClock find_timing = (Bit32) 0;
#endif

/* lookup tables
 */
static unsigned msb_of_byte[ 256 ];
static unsigned lsb_of_byte[ 256 ];



/* finds out the least significant set bit
 *
 * counts most significant bit as length*8 - 1, least as 0
 *
 * returns length*8 if no bits are set
 *
 * assumes that argument is in network byte order
 * (most significant first)
 */
unsigned lsb_of_array( Bit8 *array, unsigned length )
{
    register unsigned byte_count;
    register Bit8 byte;

    for( byte_count=length; byte_count>0; byte_count-- )
    {
        byte = array[ byte_count  - 1 ];
        if( byte != 0 )
            return (8 * (length - byte_count)) + lsb_of_byte[ byte ];
    }

    return( 8 * length );
}



/* finds out the least significant set bit
 *
 * counts most significant bit as 31, least as 0
 *
 * returns MAX_ADDR_BITS if no bits are set
 *
 * assumes that argument is host's interpretation
 * of a value that was in network byte order
 */
unsigned lsb_of_long( Bit32 value )
{
    register unsigned byte_count;
    union {
        Bit8  b_value[ 4 ];
        Bit32 l_value;
    } merged;
    register Bit8 byte;

    merged.l_value = value;
    for( byte_count=4; byte_count>0; byte_count-- )
    {
        byte = merged.b_value[ byte_count - 1 ];
        if( byte != 0 )
            return (8 * (4 - byte_count)) + lsb_of_byte[ byte ];
    }

    return MAX_ADDR_BITS;
}



/* finds out the most significant set bit
 *
 * counts most significant bit as 31, least as 0
 *
 * returns MAX_ADDR_BITS if no bits are set
 *
 * assumes that argument is in network byte order
 */
static unsigned msb_of_long( Bit32 value )
{
    register unsigned byte_count;
    union {
        Bit8  b_value[ 4 ];
        Bit32 l_value;
    } merged;
    register Bit8 byte;

    merged.l_value = value;
    for( byte_count=0; byte_count<4; byte_count++ )
    {
        byte = merged.b_value[ byte_count ];
        if( byte != 0 )
            return (8 * (3 - byte_count)) + msb_of_byte[ byte ];
    }

    return MAX_ADDR_BITS;
}



/* finds out the most significant set bit
 *
 * counts most significant bit as 31, least as 0
 *
 * returns -1 if no bits are set
 *
 * assumes that argument is in host byte order
 */
int msb_of_native_long( Bit32 value )
{
    if( value == 0 )
        return -1;

    if( value <= BIT8_MAX )
        return msb_of_byte[ value ];

    if( value <= BIT16_MAX )
        return 8 + msb_of_byte[ value >> 8 ];

    if( value <= BIT24_MAX )
        return 16 + msb_of_byte[ value >> 16 ];

    return 24 + msb_of_byte[ value >> 24 ];
}



/* finds out the most significant set bit
 *
 * counts most significant bit as 15, least as 0
 *
 * returns -1 if no bits are set
 *
 * assumes that argument is in host byte order
 */
int msb_of_native_short( Bit16 value )
{
    if( value == 0 )
        return -1;

    if( value <= BIT8_MAX )
        return msb_of_byte[ value ];

    return 8 + msb_of_byte[ value >> 8 ];
}



/* does any initialization necessary for this module
 *
 * returns TRUE if successful, FALSE if failure
 */
boolean InitSubnet( void )
{
    unsigned count, bit;
    unsigned min, max;
    unsigned step;
    Bit32 addr, addr2;                  /* debug for joel */
    int result;                         /* debug for joel */

    msb_of_byte[ 0 ] = 8;               /* indicates an error */
    min = 1;
    max = 2;
    for( bit=0; bit<8; bit++ )
    {
        for( count=min; count<max; count++ )
            msb_of_byte[ count ] = bit;

        min = max;
        max <<= 1;
    }

    lsb_of_byte[ 0 ] = 8;               /* indicates an error */
    min = 1;
    step = 2;
    for( bit=0; bit<8; bit++ )
    {
        for( count=min; count<256; count+=step )
            lsb_of_byte[ count ] = bit;

        min = step;
        step <<= 1;
    }

    for( count=0; count<MAX_ADDR_BITS; count++ )
        subnets_per_mask_length[ count ] = 0;

    if( !InitSubnet2() )
        return FALSE;

#if 0
    /* debug for joel */
    for( count=0; count<256; count++ )
        printf( "msb_of_byte[%d] = %d\n", count, msb_of_byte[count] );

    for( count=0; count<256; count++ )
        printf( "lsb_of_byte[%d] = %d\n", count, lsb_of_byte[count] );

    /* debug for joel */
    /* step a set bit from lsb to msb and see if the
     * routines identify it properly
     */
    for( addr=1,count=0; count<MAX_ADDR_BITS; count++,addr<<=1 )
    {
        addr2 = htonl( addr );
        result = lsb_of_long( addr2 );
        if( result != count )
            printf( "subnet internal error: lsb_of_long(%d) should be %d, is %d\n",
                addr, count, result );

        result = msb_of_long( addr2 );
        if( result != count )
            printf( "subnet internal error: msb_of_long(%d) should be %d, is %d\n",
                addr, count, result );
    }

    /* debug for joel */
    /* make sure zero (no bits set at all) causes
     * -1 to be returned from both functions
     */
    result = lsb_of_long( 0 );
    if( result != MAX_ADDR_BITS )
        printf( "subnet internal error: lsb_of_long(0) should be %d, is %d\n",
            MAX_ADDR_BITS, result );

    result = msb_of_long( 0 );
    if( result != MAX_ADDR_BITS )
        printf( "subnet internal error: msb_of_long(0) should be %d, is %d\n",
            MAX_ADDR_BITS, result );
#endif

    return TRUE;
}



#if !defined(__unix__) && !NETRAMET
PentiumClock GetLastFindSubnetTiming( void )
{
    return find_timing;
}
#endif



unsigned GetLastFindSubnetRefcnt( void )
{
    return MAX_SUBNET_MEMREFS - find_refcnt;
}



typedef struct
{
    char *buffer;
    unsigned max_count;
    unsigned count;
} PrintSubnetArgs;



#define SUBNET_LINE_LENGTH sizeof(" 123.123.123.123\t\t0x01020304\t\t'12345 12345 12345 12345 12345 i'\t\t 23456\n")

/* called by WalkSubnetsRecurse twice per routing,
 * once before recursion and once after
 *
 * returns TRUE if successful, FALSE if failure
 * (FALSE causes recursion to stop)
 */
static boolean PrintSubnetsHelper( boolean is_before, Subnet *external, PrintSubnetArgs *args )
{
    int width;
    char temp[ 16 ];
    char nexthop_temp[ 16 ];

    if( is_before )
    {
        if( args->count + SUBNET_LINE_LENGTH > args->max_count )
            return FALSE;
    }
    else
    {
        sprintf( args->buffer + args->count, "%s/%d %s %d '%s'\n%n",
            inet_ntoa( temp, ntohl( external->addr ) ),
            bits_in_mask( external->mask ),
            inet_ntoa( nexthop_temp, external->nexthop_addr ),
            external->line,
            external->as_path,
            &width );

        args->count += width;
    }

    return TRUE;
}



/* place one line into buffer for each routing
 *
 * they will appear in order of preference
 *
 * returns length of buffer used
 */
unsigned PrintSubnets( char *buffer, unsigned max_size )
{
    PrintSubnetArgs args;
    unsigned old_count;
    boolean result;

    strcpy( buffer, "Subnetted nets, masks, AS paths, and line numbers:\n" );
    args.buffer = buffer;
    args.max_count = max_size;
    args.count = strlen( buffer );
    old_count = args.count;

    result = WalkSubnets( (WalkSubnetFunction)PrintSubnetsHelper, &args );
    if( !result && args.count==old_count )
    {
        strcpy( buffer, "No subnets\n" );
        return strlen( buffer );
    }

    return args.count;
}



/* read-only access to global variable
 */
unsigned GetSubnetNodeCount( void )
{
    return subnet_node_count;
}



#if USE_PATRICIA_TREE
#include "../integrat/subnetp.c"
#else
#include "../integrat/subnetd.c"
#endif



#endif  // DO_FOREGROUND_STATS