/*
 *                  Unofficial release 1.3.0
 *                        B I N G
 *
 * Using the InterNet Control Message Protocol (ICMP) "ECHO" facility,
 * measure point-to-point bandwidth.
 *
 * Hack by Pierre Beyssac (pb@fasterix.freenix.fr), based on FreeBSD ping.
 * Comments and bug reports welcome !
 *
 * Original ping author -
 *        Mike Muuss
 *        U. S. Army Ballistic Research Laboratory
 *        December, 1983
 *
 *
 * Copyright (c) 1995,1997 Pierre Beyssac.
 * 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. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *        This product includes software developed by Pierre Beyssac,
 *        Mike Muss, the University of California, Berkeley and its contributors.
 * 4. Neither the name of the author nor the names of any co-contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY PIERRE BEYSSAC 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 REGENTS 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.
 *
 */

/* The original UCB copyright notice follows */

/*
 * Copyright (c) 1989 The Regents of the University of California.
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Mike Muuss.
 *
 * 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. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *        This product includes software developed by the University of
 *        California, Berkeley and its contributors.
 * 4. Neither the name of the University 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 REGENTS 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 REGENTS 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.
 *
 */

/* $Id: bing.c,v 1.12 1999/10/24 22:45:03 fgouget Exp $ */

#ifndef lint
char copyright[] =
"@(#) Copyright (c) 1989 The Regents of the University of California.\n\
 All rights reserved.\n";
#endif /* not lint */

#ifndef lint
static char rcsid[] = "$Id: bing.c,v 1.12 1999/10/24 22:45:03 fgouget Exp $";
#endif /* not lint */


/* ------------------------------------------------------------------------- */


#include <stdio.h>
#ifndef WIN32
#include <unistd.h>
#include <stdlib.h>
#endif
#include <malloc.h>
#include <string.h>

/* ctype.h provides endian-ness information (on Linux) */
#include <ctype.h>
/* types.h provides u_short on HPUX10 and Solaris */
#include <sys/types.h>

/* Network includes/definitions */

#ifdef WIN32

#include "win32/win32.h"
#include <winsock.h>
#include "win32/types.h"

#ifdef _DEBUG
#include <crtdbg.h>
#endif

/* This variable is expected by getopt.c */
/* char* __progname; */

#else

#include <netdb.h>
#include <netinet/in.h>
#include <netinet/in_systm.h>

#endif        /* WIN32 */

#include <float.h>
#include <math.h>

#include <netinet/ip.h>

#include "bing_defs.h"
#include "bing_misc.h"
#include "bing_probes.h"
#include "bing_stats.h"

#ifdef WIN32
#include <getopt.h>
#endif



/*
 * Command line options default values
 */
#define DEF_OPT_k         0
#define DEF_OPT_n         0
#define DEF_OPT_s         PAD_PKT_SIZE
#define DEF_OPT_S         1500
#define DEF_OPT_t         3
#define DEF_OPT_u         -1
#define DEF_OPT_U         10

/*
 * Just a few global variables
 */
char* tool_name;               /* Store the name of the tool as retrieved 
                                * from argv[0]
                                */

int bing_options;              /* Top level flags, i.e. not related with a 
                                * lower bing layer
                                */
#define F_RESOLVE         1    /* Do not attempt to convert IP adresses to
                                * symbolic host names
                                */

bing_stats_t bing_stats;       /* Stores the data of the bing_stats module.
                                * Most bing data is stored here (packet sizes,
                                * list of key hosts, measurements...)
                                */
struct sockaddr addr_none={PF_INET,0,0};


#ifdef WIN32
BOOL PASCAL ConsoleCtrlHandler(DWORD dwCtrlType)
{
        if (dwCtrlType==CTRL_C_EVENT) {
                /* (!!) this should be changed to a clean exit */
                exit(1);
        }
        return FALSE;
}
#endif

/*
  --------------------------------------------------------------------------
            Parse the command line options to extract the operational 
        parameters. The distinction here is that the value for the option 's'
        is a parameter while the list of packet sizes is an operational 
        parameter. Note that some processing may be required to translate the 
        first one into the other
        Most operational parameters are stored in the bing_stats structure, 
        the remainder being simple flags.
  ------------+----+-----+--------------------------------------------------
  Parameter   | IN | OUT | Role
  ------------+----+-----+--------------------------------------------------
  argc        | X  |     | Number of command line arguments
  argv        | X  |     | Command line arguments
  bing_stats  | X  |  X  | Stores all the operation bing parameters, i.e.
              |    |     | the packet sizes to use, the list of hosts...
  bing_options|    |  X  | Remainder of the options.
  ------------+----+-----+--------------------------------------------------
  RETURN      |    |  X  | 0 if successful, error code to return otherwise
  ------------+----+-----+--------------------------------------------------
*/
int parse_command_line(int argc,char** argv,
    bing_stats_t *bing_stats,int *bing_options,
    int *nb_kh,char** *kh_names,struct sockaddr* *kh_addrs,
    int *retries,int *opt_k)
{
    /* The following two are needed by Solaris */
    extern int optind;
    extern char *optarg;

    int retcode;

    /* first used in command line parsing */
    int opt;
    char* opt_p;
    int opt_n,opt_s,opt_S,opt_t,opt_u,opt_U,opt_z;
    int opt_nb_hosts;
    int i;

    /* first used in hostname resolution */
    int j;
    struct sockaddr addr;
    int errors;

    retcode=1;
    *kh_names=NULL; /* to avoid memory leaks */
    *kh_addrs=NULL; /* to avoid memory leaks */

    /*
     * Initialise the options with their default values
     */
    *opt_k=DEF_OPT_k;
    opt_n=DEF_OPT_n;
    opt_p=NULL;
    opt_s=DEF_OPT_s;
    opt_S=DEF_OPT_S;
    opt_t=DEF_OPT_t;
    opt_u=-1; /* Set both opt_u and opt_U to "uninitialised". Their default */
    opt_U=-1; /* value will be set, if necessary, after the options have been */
              /* parsed. */
    opt_z=0;

    /*
     * 1. Parse the command line parameters
     */

    while ((opt = getopt(argc, argv, "knp:s:S:t:u:U:z")) != EOF) {
        switch(opt) {
        case 'k':
            /* the listed hosts are the only key hosts. Note that this is 
             * implicit if more than 3 hosts are given on the command line
             */
            *opt_k=1;
            break;
        case 'n':
            /* disable IP address to host name conversion */
            opt_n=1;
            break;
        case 'p':
            if (opt_z!=0) {
                fprintf(stderr,"%s: warning: pattern specified. Ignoring random fill\n",tool_name);
                opt_z=0;
            }
            opt_p=optarg;
            break;
        case 's':
            /* minimum packet size */
            if (sscanf(optarg,"%d",&opt_s)!=1) {
                fprintf(stderr,"%s: error: small packet size expected after option 's'\n",tool_name);
                goto usage;
            }
            if (opt_s>MAX_PKT_SIZE) {
                fprintf(stderr,"%s: error: small packet size must be < %d\n",tool_name,MAX_PKT_SIZE+1);
                goto usage;
            }
            if (opt_s<0) {
                fprintf(stderr,"%s: error: small packet size must be >= 0\n",tool_name);
                goto usage;
            }
            if (opt_s<PAD_PKT_SIZE) {
                fprintf(stderr,"%s: warning: packets of less than %d bytes may require padding\n",tool_name,PAD_PKT_SIZE);
            }
            break;
        case 'S':
            /* maximum packet size */
            if (sscanf(optarg,"%d",&opt_S)!=1) {
                fprintf(stderr,"%s: error: big packet size expected after option 's'\n",tool_name);
                goto usage;
            }
            if (opt_S>MAX_PKT_SIZE) {
                fprintf(stderr,"%s: error: big packet size must be < %d\n",tool_name,MAX_PKT_SIZE+1);
                goto usage;
            }
            if (opt_S<0) {
                fprintf(stderr,"%s: error: big packet size must be >= 0\n",tool_name);
                goto usage;
            }
            if (opt_S<PAD_PKT_SIZE) {
                fprintf(stderr,"%s: warning: packets of less than %d bytes may require padding\n",tool_name,PAD_PKT_SIZE);
            }
            break;
        case 't':
            if (sscanf(optarg,"%d",&opt_t)!=1) {
                fprintf(stderr,"%s: error: number of traceroute attempts expected after option 't'\n",tool_name);
                goto usage;
            }
            if (opt_t<0) {
                fprintf(stderr,"%s: warning: number of traceroute attempts must be >= 0\n",tool_name);
            }
            break;
        case 'u':
            /* packet size increment */
            if (sscanf(optarg,"%d",&opt_u)!=1) {
                fprintf(stderr,"%s: error: packet size increment expected after 'u' option\n",tool_name);
                goto usage;
            }
            if (opt_u<=0) {
                fprintf(stderr,"%s: error: packet size increment must be > 0\n",tool_name);
                goto usage;
            }
            if (opt_U!=-1) {
                fprintf(stderr,"%s: warning: packet size increment specified. Ignoring '-U %d' specification\n",tool_name,opt_U);
                opt_U=-1;
            }
            break;
        case 'U':
            /* number of packet sizes */
            if (sscanf(optarg,"%d",&opt_U)!=1) {
                fprintf(stderr,"%s: error: number of sample packet sizes expected after 'U' option\n",tool_name);
                goto usage;
            }
            if (opt_U<2) {
                fprintf(stderr,"%s: error: the number of sample packet sizes must be > 2\n",tool_name);
                goto usage;
            }
            if (opt_u!=-1) {
                fprintf(stderr,"%s: warning: number of sample packet sizes specified. Ignoring '-u %d' specification\n",tool_name,opt_u);
                opt_u=-1;
            }
            break;      
        case 'z':
            if (opt_p!=NULL) {
                fprintf(stderr,"%s: warning: random fill specified. Ignoring pattern\n",tool_name);
                opt_p=NULL;
            }
            opt_z=1;
            break;
        default:
            fprintf(stderr,"%s: error: unknown option '%c'\n",tool_name,opt);
            goto usage;
        }
    }
    if ((opt_u==-1) && (opt_U==-1)) {
        opt_u=DEF_OPT_u;
        opt_U=DEF_OPT_U;
    }
    opt_nb_hosts=argc-optind;

    /* (!!) methods */
    bing_stats->nb_methods=1;
    bing_stats->methods=calloc(bing_stats->nb_methods,sizeof(*bing_stats->methods));
    bing_stats->methods[0]=BP_OM_ECHO_REPLY;

    /*
     * 2. Compute the operational parameters
     */
    if (opt_n==0)
        *bing_options|=F_RESOLVE;
    *retries=opt_t;
    if ((opt_p!=NULL) && (opt_p[0]!='\0')) {
        /* Set the packets payload pattern
         * First decode the pattern.
         */
        int len,src,dst;
        int b;
        char subpattern[3];
        char* pattern;

        /* check parameter and reallocate the pattern buffer */
        len=strlen(opt_p);
        if (len % 2!=0) {
            fprintf(stderr,"%s: error: invalid pattern specification\n",tool_name);
            goto usage;
        }
        len=len/2;
        pattern=malloc(len);
        if (pattern==NULL) {
            fprintf(stderr,"%s: error: out of memory (l%d) !\n",tool_name,__LINE__);
            goto end;
        }

        /* fill the pattern buffer with the new pattern */
        src=0;
        dst=0;
        subpattern[2]='\0';
        while (opt_p[src]!='\0') {
            subpattern[0]=opt_p[src++];
            subpattern[1]=opt_p[src++];
            if (sscanf(subpattern,"%x",&b)!=1) {
                free(pattern);
                fprintf(stderr,"%s: error: %s is not a valid hexadecimal number\n",tool_name,subpattern);
                goto usage;
            }
            pattern[dst++]=(char)b;
        }

        /* Then configure the probe handle */
        if (probe_set_option(bing_stats->probe_handle,SOL_BP,BPO_PATTERN,pattern,len)<0) {
            free(pattern);
            fprintf(stderr,"%s: error: failed to set the pattern\n",tool_name);
            goto end;
        }
        free(pattern);
        i=BP_FILL_PATTERN;
        if (probe_set_option(bing_stats->probe_handle,SOL_BP,BPO_FILLING,&i,sizeof(i))<0) {
            fprintf(stderr,"%s: error: unexpected error (l%d)\n",tool_name,__LINE__);
            goto end;
        }
    }
    if (opt_z!=0) {
        /* Specify the random fill */
        i=BP_FILL_RANDOM;
        if (probe_set_option(bing_stats->probe_handle,SOL_BP,BPO_FILLING,&i,sizeof(i))<0) {
            fprintf(stderr,"%s: error: unexpected error (l%d)\n",tool_name,__LINE__);
            goto end;
        }
    }

    /*
     * 2.1. compute the actual packet sizes
     */
    if (opt_s==opt_S) {
        fprintf(stderr,"%s: error: small packet size must be < big packet size\n",tool_name);
        goto usage;
    }
    if (opt_s>opt_S) {
        int swap_tmp;
        fprintf(stderr,"%s: warning: small packet size > big packet size. Switching packet sizes\n",tool_name);
        swap_tmp=opt_s;
        opt_s=opt_S;
        opt_S=swap_tmp;
    }
    if (opt_u==-1) {
        if (opt_U>opt_S-opt_s) {
            opt_U=opt_S-opt_s;
            fprintf(stderr,"%s: warning: the packet size interval is too small for the required number of size samples, using only %d samples\n",tool_name,opt_U);
        }
        bing_stats->nb_sizes=opt_U;
        bing_stats->packet_sizes=calloc(bing_stats->nb_sizes,sizeof(*(bing_stats->packet_sizes)));
        if (bing_stats->packet_sizes==NULL) {
            fprintf(stderr,"%s: error: out of memory (l%d) !\n",tool_name,__LINE__);
            goto end;
        }
        for (i=0;i<opt_U;i++) {
            bing_stats->packet_sizes[i]=opt_s+(opt_S-opt_s)*i/(opt_U-1);
        }
    } else {
        if (opt_u>opt_S-opt_s) {
            opt_u=opt_S-opt_s;
            fprintf(stderr,"%s: warning: the specified packet size increment is too big, using %d\n",tool_name,opt_u);
        }

        if ((opt_S-opt_s)%opt_u==0)
            bing_stats->nb_sizes=1+(opt_S-opt_s)/opt_u;
        else {
            /* the division must be rounded up, hence the final +1 */
            bing_stats->nb_sizes=1+(opt_S-opt_s)/opt_u+1;
        }
        bing_stats->packet_sizes=calloc(bing_stats->nb_sizes,sizeof(*(bing_stats->packet_sizes)));
        if (bing_stats->packet_sizes==NULL) {
            fprintf(stderr,"%s: error: out of memory (l%d) !\n",tool_name,__LINE__);
            goto end;
        }
        for (i=0;i<bing_stats->nb_sizes-1;i++) {
            bing_stats->packet_sizes[i]=opt_s+opt_u*i;
        }
        bing_stats->packet_sizes[i]=opt_S;
    }

    /*
     * 2.2. Determine the key host list.
     * 2.2.1. Translate the list of host names into a list of hosts adresses
     *     This step allows us to:
     *      - detect incorrect host names
     *      - detect and eliminate duplicates
     */
    *kh_names=(char**)calloc(opt_nb_hosts,sizeof(**kh_names));
    *kh_addrs=(struct sockaddr*)calloc(opt_nb_hosts,sizeof(**kh_addrs));
    if ((*kh_names==NULL) || (*kh_addrs==NULL)) {
        fprintf(stderr,"%s: error: out of memory (l%d) !\n",tool_name,__LINE__);
        goto end;
    }
    errors=0;
    *nb_kh=0;
    for (i=0;i<opt_nb_hosts;i++) {
        if (host_name2addr(argv[optind+i],&addr)<0) {
            fprintf(stderr,"%s: error: unknown host %s\n",tool_name,argv[optind+i]);
            errors++;
        } else {
            /*
             * Check for duplicate hosts
             */
            j=0;
            while ((j<*nb_kh) && (addrcmp((*kh_addrs)+j,&addr)!=0)) {
                j++;
            }
            if (j<*nb_kh) {
                fprintf(stderr,"%s: warning: ignoring duplicated host %s (%s) = %s\n",
                    tool_name,argv[optind+i],host_addr2name(&addr,0),(*kh_names)[j]);
            } else {
                (*kh_names)[*nb_kh]=argv[optind+i];
                addrcpy(&(*kh_addrs)[*nb_kh],&addr);
                (*nb_kh)++;
            }
        }
    }

    if (errors!=0)
        goto end;

    if (*nb_kh==0) {
        fprintf(stderr,"%s: error: you must specify at least one host name\n",tool_name);
        goto usage;
    } else if ((*opt_k==1) || (opt_t==0)) {
        if (*nb_kh==1) {
            fprintf(stderr,"%s: error: when option 'k' is used, more than one host name must be given\n",tool_name);
            goto usage;
        }
    } else {
        if (*nb_kh>2) {
            fprintf(stderr,"%s: warning: more than two hosts were specified, option 'k' is assumed\n",tool_name);
            *opt_k=1;
        }
    }

    if (errors!=0)
        goto end;

    retcode=0;

end:
    /* Check for memory leaks */
    /* (!!) free bing_stats->hosts in case of error */
    /*if (*kh_names!=NULL)
        free(*kh_names);
    if (*kh_addrs!=NULL)
        free(*kh_addrs);
    */

    return retcode;

usage:
    retcode=2;
    fprintf(stderr,"Usage: %s [-k] [-n] [-p hexadecimal_pattern | -z] [-s small_packet_size] [-S big_packet_size] [-u packet_size_increment | -U nb_packet_size_samples] [-t traceroute_attempts] host ...\n",tool_name);
    goto end;
}

/**
 * Performs a traceroute and returns the hosts that were found. Also 
 * displays warnings and error messages is any anomaly is detected.
 *
 * @param hosts the return structure that will contain the list of 
 *        all the hosts that were found during the traceroute
 * @param nb_kh the number of specified key hosts. This is the list 
 *        of hosts to return if khOnly is true
 * @param kh_names the names of the key hosts
 * @param kh_addrs the addresses of the key hosts
 * @param khOnly if true then don't return intermediate hosts that 
 *        were not specified in the key host list. In this mode the 
 *        traceroute will just compute the ttls of the key hosts and 
 *        check that there is no inconsistency
 * @return the number of hosts in the hosts array if successful, 
 *         -1 otherwise
 */
int traceroute(bing_stats_t* bing_stats, int* bing_options, 
    int nb_kh, char** kh_names, struct sockaddr* kh_addrs, 
    int khOnly, int retries)
{
    struct sockaddr host_addr,last_addr;
    int add_all_hosts;
    int hosts_size;
    int kh,t;
    int ttl;
    char* name;

    int probe_res;
    bp_probedata_t probe;
    int add_host;
    /* (!!) fix the error handling */

    /* Start by allocating the array for the returned hosts. There will be 
     * at least nb_kh hosts in this list
     */
    bing_stats->nb_hosts=0;
    hosts_size=nb_kh;
    bing_stats->hosts=malloc(hosts_size*sizeof(*bing_stats->hosts));

    /* If we are in the 'bing host' case then we should start adding all 
     * intermediate hosts right away.
     */
    add_all_hosts=(nb_kh==1);
    addrcpy(&host_addr,&addr_none);
    addrcpy(&last_addr,&addr_none);
    ttl=0;
    for (kh=0;kh<nb_kh;kh++) {
        int host_reached;
        if (ttl>=1) {
            /*
             * We have already done a traceroute to a host. Check that this new host is 
             * somewhere further on the same path. Sending a probe to this new host 
             * with the ttl of the last host should fail when reaching the last host.
             */

            DEBUG_MSG((stderr,"sending probe to %s, ttl=%d",host_addr2name(&kh_addrs[kh],0),ttl));
            t=0;
            while (t<retries) {
                probe_res=do_probe(bing_stats->probe_handle,&kh_addrs[kh],PAD_PKT_SIZE,ttl,&probe);
                if (probe.contents!=NULL)
                    free(probe.contents);
                /* (!!) maybe we should not break for source_quench ? Any others ? */
                if (probe_res!=BP_RES_TIMEOUT)
                    break;
                t++;
            }
            switch (probe_res) {
            case BP_RES_HIT:
                DEBUG_MSG((stderr," -> hit"));
                fprintf(stderr,"%s: error: reached %s with a ttl of %d\n",
                    tool_name,
                    kh_names[kh],
                    ttl);
                fprintf(stderr,"%s: error: %s is not on the same network path as %s or the hosts order is wrong\n",
                    tool_name,
                    kh_names[kh],
                    bing_stats->hosts[bing_stats->nb_hosts-1].name);
                /* Skip to the next key host */ /* (!!) shouldn't we just abort ? */
                continue;
            case BP_RES_TTL_EXCEEDED:
                DEBUG_MSG((stderr," -> ttl exceeded"));
                if (addrcmp(&probe.src_addr,
                    &(bing_stats->hosts[bing_stats->nb_hosts-1].address))!=0) {
                    fprintf(stderr,"%s: error: probe to host %s with ttl %d failed at host %s instead of %s\n",
                        tool_name,
                        kh_names[kh],
                        ttl,
                        host_addr2name(&probe.src_addr,0),
                        bing_stats->hosts[bing_stats->nb_hosts-1].name);
                    fprintf(stderr,"%s: error: host %s is not on the same network path as %s\n",
                        tool_name,
                        kh_names[kh],
                        bing_stats->hosts[bing_stats->nb_hosts-1].name);
                    continue;
                }
                break;
            default:
                DEBUG_MSG((stderr," -> neither: res=%d",probe_res));
                fprintf(stderr,"%s: warning: route check step failed at ttl %d for %s (%s)\n",
                    tool_name,ttl,kh_names[kh],host_addr2name(&kh_addrs[kh],0));
                return -1;
            }
        }

        host_reached=0;
        while ((host_reached==0) && (ttl<STD_TTL_LIMIT)) {
            ttl++;

            t=0;
            while (t<retries) {
                probe_res=do_probe(bing_stats->probe_handle,&kh_addrs[kh],PAD_PKT_SIZE,ttl,&probe);
                if (probe.contents!=NULL)
                    free(probe.contents);
                /* (!!) maybe we should not break for source_quench ? Any others ? */
                if (probe_res!=BP_RES_TIMEOUT)
                    break;
                t++;
            }
            fprintf(stderr,"ttl=%d probe_res=%d host=%s\n",ttl,probe_res,host_addr2name(&kh_addrs[kh],0));

            /* Check the return path */
            if (probe_res<0)
                return -1;
            if (probe_res!=BP_RES_TIMEOUT) {
                if (addrcmp(&host_addr,&addr_none)==0) {
                    /* We don't know yet what is the address of the local host. The best 
                     * thing to do is to take the destination address of the return packet 
                     * because this is going to be the address of the right network interface
                     */
                    addrcpy(&host_addr,&probe.dst_addr);

                    if (addrcmp(&host_addr,&probe.src_addr)!=0) {
                        if (add_all_hosts!=0) {
                            /* No need to worry about reallocating bing_stats->hosts yet, this is 
                             * our first host. Note that necessarily here khOnly==false.
                             */
                            bing_stats->hosts[bing_stats->nb_hosts].name=strdup(host_addr2name(&host_addr,*bing_options & F_RESOLVE));
                            addrcpy(&bing_stats->hosts[bing_stats->nb_hosts].address,&host_addr);
                            bing_stats->hosts[bing_stats->nb_hosts].ttl=0;
                            fprintf(stderr,"  adding host %s at ttl 0\n",bing_stats->hosts[bing_stats->nb_hosts].name);
                            bing_stats->nb_hosts++;
                        }
                    } else {
                        /* We'll let the regular code handle adding this host but first 
                       * fix up the ttl.
                       */
                        ttl=0;
                    }
                } else if (addrcmp(&host_addr,&probe.dst_addr)!=0) {
                        fprintf(stderr,"%s: error: at ttl %d the return path from %s went through the %s interface instead of %s for the other hosts\n",
                            tool_name,
                            ttl,
                            kh_names[kh],
                            host_addr2name(&probe.dst_addr,0),
                            host_addr2name(&host_addr,0));
                        break; /* (!!) break, really ??? */
                }
            }

            add_host=0;
            switch (probe_res) {
            case BP_RES_HIT:
                DEBUG_MSG((stderr," -> hit"));
                host_reached=1;
                name=kh_names[kh];
                add_host=1;

                /* If we are in the 'bing host1 host2' and we have just reached host1 and 
                 * khOnly is not set then from now on we should add all intermediate hosts
                 */
                if ((khOnly==0) && (nb_kh==2)) {
                    add_all_hosts=1;
                }
                break;
            case BP_RES_TTL_EXCEEDED:
                DEBUG_MSG((stderr," -> ttl exceeded probe.src=%s",host_addr2name(&probe.src_addr,0)));
                /* We might get stuck on a host for a few ttls */
                if (addrcmp(&last_addr,&probe.src_addr)!=0) {
                    name=NULL;
                    add_host=add_all_hosts;
                }
                break;
            case BP_RES_TIMEOUT:
                /* print a warning and continue as for the default case */
                break;
            default:
                DEBUG_MSG((stderr," -> neither: probe_res=%d",probe_res));
                /* print a warning with the decoded icmp packet that we received */
                fprintf(stderr,"%s: error: failed traceroute step %d to %s (%s)\n",
                        tool_name,ttl,kh_names[kh],host_addr2name(&kh_addrs[kh],0));
                /* Continue anyway. This might just be that this particular host sets 
                 * the return ttl with a value which is too low. A few ttls later it 
                 * might all be fine again.
                 */
            }
            if (add_host==1) {
                /*
                 * Add this host to the bing_stats list of hosts. This is the 
                 * list of actual key hosts, i.e. the hosts between which are 
                 * the links to analyse. Note that there may be many hops 
                 * between two key hosts if the user wants so. In that case he
                 * will get a composite bandwidth estimation.
                 */
                if (bing_stats->nb_hosts==hosts_size) {
                    hosts_size++;
                    bing_stats->hosts=realloc(bing_stats->hosts,hosts_size*sizeof(*(bing_stats->hosts)));
                    if (bing_stats->hosts==NULL) {
                        fprintf(stderr,"%s: error: out of memory (l%d)\n",tool_name,__LINE__);
                        return -1;
                    }
                }
                bing_stats->hosts[bing_stats->nb_hosts].name=strdup(name!=NULL?name:host_addr2name(&probe.src_addr,*bing_options & F_RESOLVE));
                addrcpy(&bing_stats->hosts[bing_stats->nb_hosts].address,&probe.src_addr);
                bing_stats->hosts[bing_stats->nb_hosts].ttl=ttl;
                fprintf(stderr,"  adding host %s at ttl %d\n",bing_stats->hosts[bing_stats->nb_hosts].name,ttl);
                bing_stats->nb_hosts++;
            }
            addrcpy(&last_addr,&probe.src_addr);
        }
    }

    return bing_stats->nb_hosts;
}

/**
 * Redoes a probe for all the RTTs which are not in the RTT_STATE_OK 
 * state.
 *
 * @param bing_stats the bing_stats
 * @param h index of the host
 * @param m method for which to redo the probes
 * @param randomizer an array used to randomize the order in which the 
 *        packet sizes are used. This is because the first probe that we 
 *        send to a host seems to always be rather bad so we try to make 
 *        sure it's not always the same one
 * @return 0 if no RTT was updated. This includes the case where no RTT 
 *         needed to be updated in the first place. Otherwise returns 1.
 */
int do_probes(bing_stats_t* bing_stats, int h, int m, int* randomizer)
{
    int s;
    host_stats_t* host=&bing_stats->hosts[h];
    rtt_law_t* rtt_law=&bing_stats->hosts[h].rtt_laws[m];
    int updated=0;

    if ((rtt_law->nb_hinvalid==0) && (rtt_law->nb_linvalid==0) && (rtt_law->nb_redo==0))
        return 0;

    for (s=0;s<bing_stats->nb_sizes;s++) {
        /* This internal loop is kind of a random experiment. */
        int i;
        for (i=0;i<3;i++) {
            if (rtt_law->rtt_stats[randomizer[s]].state!=RTT_STATE_OK) {
                updated|=method_do_probe(bing_stats->probe_handle,
                    host,
                    bing_stats->packet_sizes[randomizer[s]],
                    rtt_law,
                    randomizer[s]);
            }
        }
    }
    return updated;
}

/**
 * Updates the linear regression results for this {host,method} and eliminates 
 * any RTT which does not satisfy the following criteria:
 *  - intra host rtt[size1] < rtt[size2] if size1 < size2
 *  - inter host rtt[host h] < rtt[host h+1] for any given size
 *  - the last check is done for both hosts (h-1,h) and hosts (h,h+1)
 * and at the same time:
 *  - update the linear regression for the host h-1
 *  - redo from scratch (for fear that the errors accumulate) the 
 *    linear regression on the host h
 *
 * @param bing_stats the bing_stats
 * @param h the host's index
 * @param m the method's index
 */
void do_host_regression(bing_stats_t* bing_stats,int h,int m)
{
    int s;
    rtt_law_t* prtt_law=&bing_stats->hosts[h-1].rtt_laws[m];
    rtt_law_t* rtt_law=&bing_stats->hosts[h].rtt_laws[m];
    rtt_law_t* nrtt_law=&bing_stats->hosts[h+1].rtt_laws[m];
    double max_rtt=DBL_MAX;
    linreg_init(&rtt_law->host_reg);
    for (s=bing_stats->nb_sizes-1;s>=0;s--) {
        if ((h+1<bing_stats->nb_hosts) && 
            (nrtt_law->rtt_stats[s].min_rtt<max_rtt)
           ) {
           max_rtt=nrtt_law->rtt_stats[s].min_rtt;
        }

        if (rtt_law->rtt_stats[s].min_rtt>=max_rtt) {
            /* Any RTT in the invalid state will end up here because min_rtt>=max_rtt. 
             * Any RTT for which we don't have any data yet will also end up here 
             * because min_rtt==DBL_MAX
             */
            rtt_law_set_rtt_state(rtt_law,s,RTT_STATE_HINVALID,max_rtt);
        } else {
            /* So here the RTT has to be valid */
            linreg_add_sample(&rtt_law->host_reg,
                rtt_law->rtt_stats[s].nb_bits,
                rtt_law->rtt_stats[s].min_rtt,0);
            max_rtt=rtt_law->rtt_stats[s].min_rtt;

            /* Update the previous host's RTT and linear regression result */
            if ((h>0) && 
                (prtt_law->rtt_stats[s].min_rtt>=max_rtt) && 
                (prtt_law->rtt_stats[s].state!=RTT_STATE_HINVALID)
                ) {
                rtt_law_set_rtt_state(prtt_law,s,RTT_STATE_HINVALID,max_rtt);
                linreg_del_sample(&prtt_law->host_reg,
                    prtt_law->rtt_stats[s].nb_bits,
                    prtt_law->rtt_stats[s].min_rtt,1);
           }
        }
    }
    linreg_update(&rtt_law->host_reg);
}

/**
 * Updates the link level regression for the specified host (so this is for the 
 * link between host h-1 and h). RTTs which do not satisfy the following criteria 
 * are put in the RTT_STATE_LINVALID state:
 *  - for any give size, rtt[h,s]-rtt[h-1,s]<rtt[h,s+1]-rtt[h-1,s+1]
 * Note, however, that we are not propagating the bound thus obtained because the 
 * RTT could be too small just as well as it could be too big. So all we can say 
 * is that adjacent RTT differences should be consistent.
 *
 * @param bing_stats the bing_stats
 * @param h the host's index
 */
void do_link_regression(bing_stats_t* bing_stats,int h)
{
    int m;
    for (m=0;m<bing_stats->nb_methods;m++) {
        rtt_law_t* prtt_law=&bing_stats->hosts[h-1].rtt_laws[m];
        rtt_law_t* rtt_law=&bing_stats->hosts[h].rtt_laws[m];
        double last_rttd=DBL_MAX;
        int last_added;
        int s;

        linreg_init(&rtt_law->link_reg);
        for (s=0;s<bing_stats->nb_sizes;s++) {
            /* Reset the flags that were set during the last probe round */
            rtt_law_set_rtt_state(prtt_law,s,RTT_STATE_OK|RTT_STATE_LINVALID2,0.0);
            rtt_law_set_rtt_state(rtt_law,s,RTT_STATE_OK|RTT_STATE_LINVALID1,0.0);

            if ((prtt_law->rtt_stats[s].state!=RTT_STATE_HINVALID) && 
                (rtt_law->rtt_stats[s].state!=RTT_STATE_HINVALID)
               ) {
                double rttd=rtt_law->rtt_stats[s].min_rtt-prtt_law->rtt_stats[s].min_rtt;
                if ((last_rttd!=DBL_MAX) && (last_rttd>=rttd)) {
                    /* There is a local inconsistency, schedule all the involved 
                   * RTTs for the next probe round. Note that this cannot happen 
                   * if s==0.
                   */
                    rtt_law_set_rtt_state(prtt_law,s,RTT_STATE_LINVALID|RTT_STATE_LINVALID2,0.0);
                    rtt_law_set_rtt_state(prtt_law,s-1,RTT_STATE_LINVALID|RTT_STATE_LINVALID2,0.0);
                    rtt_law_set_rtt_state(rtt_law,s,RTT_STATE_LINVALID|RTT_STATE_LINVALID1,0.0);
                    rtt_law_set_rtt_state(rtt_law,s-1,RTT_STATE_LINVALID|RTT_STATE_LINVALID1,0.0);
                    if (last_added!=0) {
                        linreg_del_sample(&bing_stats->hosts[h].rtt_laws[m].link_reg,
                            rtt_law->rtt_stats[s-1].nb_bits,
                            last_rttd,0);
                    }
                    last_added=0;
                } else {
                    linreg_add_sample(&bing_stats->hosts[h].rtt_laws[m].link_reg,
                        rtt_law->rtt_stats[s].nb_bits,
                        rttd,0);
                    last_added=1;
                }
                last_rttd=rttd;
            } else {
                last_rttd=DBL_MAX;
                /* last_added not significant in this case */
            }
        }
        linreg_update(&rtt_law->link_reg);
    }
}

/**
 * Performs a global, across all hosts, methods and sizes, elimination 
 * of invalid RTTs.
 * @param bing_stats the bing_stats
 */
void do_host_cleanup(bing_stats_t* bing_stats)
{
    int h,m,s;

    /* Do a global elimination of inter-host errors:
     *  - for any given size, rtt[host 1] < rtt[host 2] if host 1 comes before host 2
     */
    for (h=bing_stats->nb_hosts-1;h>=0;h--) {
        for (m=0;m<bing_stats->nb_methods;m++) {
            double max_rtt=DBL_MAX;
            for (s=bing_stats->nb_sizes-1;s>=0;s--) {
                if ((h+1<bing_stats->nb_hosts) && 
                    (bing_stats->hosts[h+1].rtt_laws[m].rtt_stats[s].min_rtt<max_rtt)
                   ) {
                    max_rtt=bing_stats->hosts[h+1].rtt_laws[m].rtt_stats[s].min_rtt;
                }
                if (bing_stats->hosts[h].rtt_laws[m].rtt_stats[s].min_rtt>=max_rtt) {
                    rtt_law_set_rtt_state(&bing_stats->hosts[h].rtt_laws[m],s,RTT_STATE_HINVALID,max_rtt);
                } else {
                    max_rtt=bing_stats->hosts[h].rtt_laws[m].rtt_stats[s].min_rtt;
                }
            }
        }
    }
}

typedef struct {
    int index;
    double v;
} double_sort_t;

int double_sort(const void* e1,const void* e2)
{
    double v1=((double_sort_t*)e1)->v;
    double v2=((double_sort_t*)e2)->v;

    if (v1<v2)
        return -1;
    else if (v1>v2)
        return 1;
    return 0;
}

int double_rabs_sort(const void* e1,const void* e2)
{
    double v1=fabs(((double_sort_t*)e1)->v);
    double v2=fabs(((double_sort_t*)e2)->v);

    if (v1>v2)
        return -1;
    else if (v1<v2)
        return 1;
    return 0;
}

/**
 * Analyze the current results and decide which probes to redo for the 
 * next round. This process is based on an analysis of the link level 
 * correlation and how each probe matches the results. First we sort the 
 * links based on their correlation. Then for all the links in the bottom 
 * 50% we sort the RTT differences according to how well they fit the linear 
 * regression result. Then for each RTT difference in the bottom 50% we 
 * schedule one or both of the corresponding probes.
 *
 * Note that:
 * <ol>
 *   <li>Links for which no correlation is available due to lack of data 
 *     points and links for which the correlation is based on less than 50% 
 *     of the points are automatically put at the bottom of the list (corr=-1).
 *   <li>Links with a 'resulting' correlation of -1 are systematically processed, 
 *     whether or not they are in the first 50%.
 *   <li>Link sthat have a very low correlation are very likely to already have 
 *     most of their probes in the RTT_STATE_REDO state because of link level 
 *     inconsistencies. For these links it is not even necessary to schedule 
 *     additional probes. So we substract the probes already scheduled for update 
 *     from the target 50% of additional probes.
 *   <li>If the correlation is less than 0.8 both probes are being marked 
 *     for update. Otherwise only one of the two is marked for update.
 * </ol>
 *
 * I think this algorithm should work fine. But it may be possible that under 
 * some circumstances the worst points are actually those that actually fit the 
 * linear regression the best although it seems quite unlikely due to their 
 * random nature.
 */
int do_probe_scheduling(bing_stats_t* bing_stats,
    double_sort_t* links,double_sort_t* link_errors,
    int* nb_hinvalid,int* nb_linvalid)
{
    int h,m,s;
    int nb_redo=0;

    for (m=0;m<bing_stats->nb_methods;m++) {
        *nb_hinvalid=0;
        *nb_linvalid=0;

        /* Sort the links based on their correlation (more or less) */
        for (h=0;h<bing_stats->nb_hosts;h++) {
            rtt_law_t* rtt_law=&bing_stats->hosts[h].rtt_laws[m];

            if (h>0) {
                linreg_t* link_reg=&rtt_law->link_reg;

                links[h-1].index=h;
                if ((link_reg->nb_samples<bing_stats->nb_sizes/2) || 
                    (link_reg->nb_samples==0) || 
                    (link_reg->corr<0)
                   ) {
                    links[h-1].v=-1;
                } else {
                    links[h-1].v=link_reg->corr;
                }
            }

            for (s=0;s<bing_stats->nb_sizes;s++) {
                if (rtt_law->rtt_stats[s].state==RTT_STATE_REDO)
                    rtt_law_set_rtt_state(rtt_law,s,RTT_STATE_OK,0.0);
            }

            *nb_hinvalid+=rtt_law->nb_hinvalid;
            *nb_linvalid+=rtt_law->nb_linvalid;
        }
        qsort(links,bing_stats->nb_hosts-1,sizeof(double_sort_t),&double_sort);

#if 0
        printf("links from worst to best\n");
        for (h=0;h<bing_stats->nb_hosts-1;h++) {
            printf("h=%d corr=%f\n",links[h].index,links[h].v); 
        }
#endif

        /* For the worst links see which probes are causing trouble */
        h=0;
        while (((h<bing_stats->nb_hosts/2) || (links[h].v<0)) && (h<bing_stats->nb_hosts-1)) {
            rtt_law_t* prtt_law=&bing_stats->hosts[links[h].index-1].rtt_laws[m];
            rtt_law_t* rtt_law=&bing_stats->hosts[links[h].index].rtt_laws[m];
            int nb_samples;

#if 0
            printf("scheduling probes for %d, link_reg.nb_samples=%d\n",links[h].index,rtt_law->link_reg.nb_samples);
#endif

            if (rtt_law->link_reg.nb_samples<bing_stats->nb_sizes/2) {
                /* More than half the probes are invalid and are thus already scheduled
                  * for the next probe round. There is no need to add more.
                  */
#if 0
                printf("  skipping %d\n",links[h].index);
#endif
                h++;
                continue;
            }

            /* Sort the probes according to how well they fit the linear regression */
            nb_samples=0;
            for (s=0;s<bing_stats->nb_sizes;s++) {
                if ((prtt_law->rtt_stats[s].state==RTT_STATE_OK) && 
                    (rtt_law->rtt_stats[s].state==RTT_STATE_OK)
                   ) {
                    double measured_rttd=rtt_law->rtt_stats[s].min_rtt-prtt_law->rtt_stats[s].min_rtt;
                    double predicted_rttd=rtt_law->link_reg.a*rtt_law->rtt_stats[s].nb_bits+rtt_law->link_reg.b;
                    link_errors[nb_samples].v=measured_rttd-predicted_rttd;
                    link_errors[nb_samples].index=s;
                    nb_samples++;
                }
            }
            qsort(link_errors,nb_samples,sizeof(double_sort_t),&double_rabs_sort);

#if 0
            printf("probes of link %d from worst to best will schedule the first %d\n",links[h].index,nb_samples-bing_stats->nb_sizes/2+1);
            for (s=0;s<nb_samples;s++) {
                printf("s=%d index=%d error=%f\n",s,link_errors[s].index,link_errors[s].v); 
        }
#endif

            /* Now schedule some probes */
            for (s=0;s<nb_samples-bing_stats->nb_sizes/2+1;s++) {
                if ((links[h].v<0.8) || (link_errors[s].v>0)) {
                    rtt_law_set_rtt_state(prtt_law,link_errors[s].index,RTT_STATE_REDO,0.0);
                    nb_redo++;
                }
                if ((links[h].v<0.8) || (link_errors[s].v<0)) {
                    rtt_law_set_rtt_state(rtt_law,link_errors[s].index,RTT_STATE_REDO,0.0);
                }
            }
            nb_redo+=rtt_law->nb_redo;
            h++;
        }
    }

    return nb_redo;
}

/**
 * Prints the characteristics of the given host:
 * 208.199.87.56/208.199.87.56: 15 ms, corr=0.999, invalid 23%, dropped 0%
 * host name and address, rtt of a 0bit packet, correlation, % invalid 
 * measures, % dropped packets
 *
 * @param bing_stats the bing_stats
 * @param h the host's index
 */
void print_host_statistics(bing_stats_t* bing_stats,int h)
{
    host_stats_t* host=&bing_stats->hosts[h];
    double latency=DBL_MAX;
    double corr;
    int nb_hinvalid;
    int nb_dropped;
    int nb_probes=0;

    printf("%2d %-42s ",h,host->name);
    if (bing_stats->nb_methods==1) {
        if (host->rtt_laws[0].host_reg.a!=0) {
            latency=host->rtt_laws[0].host_reg.b;
            corr=host->rtt_laws[0].host_reg.corr;
        }
        nb_hinvalid=host->rtt_laws[0].nb_hinvalid;
        nb_dropped=host->rtt_laws[0].nb_dropped;
        nb_probes=nb_dropped+host->rtt_laws[0].nb_samples;
    } else {
        if (host->rtt_laws[0].host_reg.a!=0) {
            if (host->rtt_laws[1].host_reg.a!=0) {
                latency=(host->rtt_laws[0].host_reg.b+host->rtt_laws[1].host_reg.b)/2;
                corr=(host->rtt_laws[0].host_reg.corr+host->rtt_laws[1].host_reg.corr)/2;
            } else {
                latency=host->rtt_laws[0].host_reg.b;
                corr=host->rtt_laws[0].host_reg.corr;
            }
        } else if (host->rtt_laws[1].host_reg.a!=0) {
            latency=host->rtt_laws[1].host_reg.b;
            corr=host->rtt_laws[1].host_reg.corr;
        }
        nb_hinvalid=host->rtt_laws[0].nb_hinvalid+host->rtt_laws[1].nb_hinvalid;
        nb_dropped=host->rtt_laws[0].nb_dropped+host->rtt_laws[1].nb_dropped;
        nb_probes=nb_dropped+host->rtt_laws[0].nb_samples+host->rtt_laws[1].nb_samples;
    }
    if (corr==0.0) {
        /* (!!) shouldn't we use the nb_samples field instead ? */
        printf("---.--- ms, -.---/--, ");
    } else {
        printf("%7.3f ms, %5.3f/%-2d, ",latency,corr,host->rtt_laws[0].host_reg.nb_samples);
    }
    printf("%5.1f%%, ",((double)100.0*nb_hinvalid)/bing_stats->nb_sizes);
    if (nb_probes==0) {
        printf("--.-%%\n");
    } else {
        printf("%5.1f%%\n",((double)100.0*nb_dropped)/nb_probes);
    }
}

/**
 * Prints the characteristics of the link in the following format:
 *  |  38Mb/s, 100 ms (145 bits), corr=0.75
 *    bandwidth delay in ms and in bits, correlation
 * or (for bidirectional)
 *  |< 38Mb/s, 100 ms (145 bits), corr=0.75
 *  |> 40Mb/s,  80 ms (130 bits), corr=0.80
 *     where "| ", "|<" and "|>" are the prefixes for a composite 
 *     link, a downlink and an uplink
 */
void print_link_statistics(const char* prefix, linreg_t* link_data)
{
    printf(" %s  ",prefix);
    /* (!!) it is possible to have the bandwidth but not the correlation, 
     * if host h-1 and host h have disjoint valid rtts for instance. 
     * We should deal with this here.
     *
     * Also if the bandwidth is negative the latency does not mean anything 
     * anyway and thus should not be displayed.
     */
    if (link_data->a==0) {
        printf("----.-- b/s, ---.-- ms (----- bytes), -.---/--\n");
    } else {
        double bandwidth=1/link_data->a;
        if (bandwidth<0)
            printf("---.--- b/s, ");
        else if (bandwidth<10)
            printf("%7g b/s, ",bandwidth*1e3);
        else if (bandwidth<1e4)
            printf("%7.2fKb/s, ",bandwidth);
        else
            printf("%7.2fMb/s, ",bandwidth/1e3);
        if (link_data->b<0) {
            printf("---.-- ms (----- bytes)");
        } else {
            if (link_data->b<1)
                printf("%6.2f us ",link_data->b*1e3);
            else
                printf("%6.2f ms ",link_data->b);
            if (link_data->a<=0.0) {
                printf("(----- bytes)");
            } else {
                printf("(%5.0f bytes)",link_data->b/link_data->a/8);
            }
        }
        if (link_data->corr!=0.0) {
            /* (!!) to fix, corr could really be 0 */
            if (link_data->nb_samples<2) {
                printf(", -----/%d\n",link_data->nb_samples);
            } else {
                printf(", %5.3f/%d\n",link_data->corr,link_data->nb_samples);
            }
        } else {
            printf("\n");
        }
    }
}

/**
 * Prints the bing results.
 *
 * @param bing_stats the bing_stats
 * @param last_update the index of the last host for which we printed 
 *        the statistics. For the first call this should be -1. This 
 *        parameter is updated to be equal to current. 
 * @param current this is the index of the current host
 */
void print_statistics(bing_stats_t* bing_stats,int* last_update,int current)
{
    rtt_law_t* prtt_law0=&bing_stats->hosts[*last_update].rtt_laws[0];
    rtt_law_t* prtt_law1=&bing_stats->hosts[*last_update].rtt_laws[1];
    int h;

    if (*last_update==-1)
        printf("\n\n");
    for (h=(*last_update)+1;h<=current;h++) {
        rtt_law_t* rtt_law0;
        rtt_law_t* rtt_law1;

        rtt_law0=&bing_stats->hosts[h].rtt_laws[0];
        if (bing_stats->nb_methods!=1)
            rtt_law1=&bing_stats->hosts[h].rtt_laws[1];

        if (h>0) {
            linreg_t direct_link;
            linreg_t reverse_link;

            direct_link.a=rtt_law0->host_reg.a-prtt_law0->host_reg.a;
            direct_link.b=rtt_law0->host_reg.b-prtt_law0->host_reg.b;
            direct_link.corr=0;
            direct_link.nb_samples=0;

            /* Display the results for the link between host h-1 and host h */
            if (bing_stats->nb_methods==1) {
                print_link_statistics("| ", &rtt_law0->link_reg);
                print_link_statistics("| ", &direct_link);
            } else {
                reverse_link.a=2*(rtt_law1->host_reg.a-prtt_law1->host_reg.a)-(rtt_law0->host_reg.a-prtt_law0->host_reg.a);
                reverse_link.b=(rtt_law0->host_reg.b-prtt_law0->host_reg.b)-reverse_link.a*(bing_stats->hosts[h].rtt_laws[0].rtt_stats[0].nb_bits-(bing_stats->packet_sizes[0]+28)*8); /* (!!) urgh, this is so ugly */
                reverse_link.corr=0;
                /* or if you wish: ((a1b-a1a)-(a2b-a2a))*(s1r-s1d)+b2b-b2a) */

                /* currently there is no rtt_law.link_reg equivalent for the reverse link 
                 * so we just display the result we calculated above
                 */
                print_link_statistics("|<", &reverse_link);
                print_link_statistics("|>", &rtt_law0->link_reg);
                print_link_statistics("|>", &direct_link);
            }
        }
        print_host_statistics(bing_stats,h);

        prtt_law0=rtt_law0;
        if (bing_stats->nb_methods!=1)
            prtt_law1=rtt_law1;
    }
    *last_update=current;
}


/*
  --------------------------------------------------------------------------
            Arranges for the different components to be called in the proper 
        order.
  ------------+----+-----+--------------------------------------------------
  Parameter   | IN | OUT | Role
  ------------+----+-----+--------------------------------------------------
  argc        | X  |     | Number of command line arguments
  argv        | X  |     | Command line arguments
  ------------+----+-----+--------------------------------------------------
  RETURN      |    |  X  | 0 if successful, 1 if an error occurred,
              |    |     | 2 if usage was given
  ------------+----+-----+--------------------------------------------------
*/
int main(argc, argv)
    int argc;
    char** argv;
{
    int retcode;
    int h,m,s;
#ifdef WIN32
    char* slash_ptr;
#endif /* WIN32 */
    int exit; /* (!!) keep this ? */
    int* randomizer;
    int ri;
    double_sort_t* links;
    double_sort_t* link_errors;
    int round;

#ifdef _DEBUG
#ifdef WIN32
   _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif
#endif

    tool_name=strrchr(argv[0],'/');
#ifdef WIN32
    slash_ptr=tool_name;
    tool_name=strrchr((tool_name!=NULL?tool_name:argv[0]),'\\');
    if (tool_name==NULL)
        tool_name=slash_ptr;
#endif /* WIN32 */
    if (tool_name==NULL)
        tool_name=argv[0];
    else
        tool_name++;

    /*
     * Perform some initialisation tasks
     */
#ifdef WIN32
    {
        WSADATA wsaData;
        WORD wsaVersionRequested;
        int err;
        
        /* Initialise the winsock */
        wsaVersionRequested = MAKEWORD( 1, 1 );
        err = WSAStartup( wsaVersionRequested, &wsaData );
        if (err!=0) {
            fprintf(stderr,"%s: error: could not initialise the winsock\n", tool_name);
            return 1;
        }
    
        /* Install the ^C handler */
        /* Not necessary yet SetConsoleCtrlHandler(ConsoleCtrlHandler,TRUE);*/
    }
#endif

    /*
     * Obtain a handle from the probe module right now. On Unix this involves 
     * opening a RAW socket handle and must be done while we have root 
     * privilege.
     */
    bing_stats.probe_handle=probe_open();
    if (bing_stats.probe_handle == NULL) {
        fprintf(stderr, "%s: error: cannot open ICMP module\n", tool_name);
        return 1;
    }

#ifndef WIN32
    /* Relinquish root privilege */
    setgid(getgid());
    setuid(getuid());
#endif

    {
        int nb_kh;
        char** kh_names;
        struct sockaddr* kh_addrs;
        int retries;
        int opt_k;
        int kh;
        /*
        * Parse the command_line
        */
        retcode=parse_command_line(argc,argv,&bing_stats,&bing_options,&nb_kh,&kh_names,&kh_addrs,&retries,&opt_k);
        if (retcode!=0)
            return retcode;
        printf("Found %d key hosts\n",nb_kh);
        for (kh=0;kh<nb_kh;kh++) {
            printf("%d: %s (%s)\n",kh,kh_names[kh],host_addr2name(&(kh_addrs[kh]),0));
        }
        printf("--\n");
        printf("Using %d data payload sizes:\n",bing_stats.nb_sizes);
        for (kh=0;kh<bing_stats.nb_sizes;kh++) {
            printf("%d ",bing_stats.packet_sizes[kh]);
        }
        printf("\n--\n");

        /*
        * Perform the traceroute
        */
        if (retries==0) {
            int kh;
            /* Directly build the list of hosts from the list of key hosts with no ttl information */
            bing_stats.nb_hosts=nb_kh;
            bing_stats.hosts=calloc(nb_kh,sizeof(*bing_stats.hosts));
            for (kh=0;kh<nb_kh;kh++) {
                bing_stats.hosts[kh].name=strdup(kh_names[kh]);
                addrcpy(&bing_stats.hosts[kh].address,&kh_addrs[kh]);
                bing_stats.hosts[kh].ttl=-1;
            }
        } else {
            if (traceroute(&bing_stats,&bing_options,nb_kh,kh_names,kh_addrs,(opt_k==1) || (nb_kh>=3),retries)<0) {
                return 1;
            }
        }
        free(kh_names); /* Note that we don't need to free the strings themselves */
        free(kh_addrs);
    }

    /* (!!) For now, print the list of hosts that we came up with */
    printf("Found %d hosts\n",bing_stats.nb_hosts);
    for (retcode=0;retcode<bing_stats.nb_hosts;retcode++) {
        printf("%d: %d - %s (%s)\n",retcode,
            bing_stats.hosts[retcode].ttl,
            bing_stats.hosts[retcode].name,
            host_addr2name(&bing_stats.hosts[retcode].address,bing_options & F_RESOLVE)
            );
    }
    if (bing_stats.nb_hosts<2) {
        fprintf(stderr,"%s: not enough hosts were found to perform the bandwidth analysis\n",tool_name);
        return 1;
    }

    /*
     * Allocate resources
     */
    /* allocate space for the probes (1 per packet size per host) */
    links=malloc((bing_stats.nb_hosts-1)*sizeof(double_sort_t));
    link_errors=malloc(bing_stats.nb_sizes*sizeof(double_sort_t));
    for (h=0;h<bing_stats.nb_hosts;h++) {
        int m;
        bing_stats.hosts[h].rtt_laws=calloc(bing_stats.nb_methods,sizeof(*bing_stats.hosts[h].rtt_laws));
        for (m=0;m<bing_stats.nb_methods;m++) {
            rtt_law_init(&bing_stats.hosts[h].rtt_laws[m],bing_stats.nb_sizes);
        }
    }

    /*
     * Perform mesurement
     */
    randomizer=malloc(bing_stats.nb_sizes*sizeof(int));
    for (ri=0;ri<bing_stats.nb_sizes;ri++) {
        randomizer[ri]=ri;
    }

    exit=0;
    round=0;
    while (exit==0) {
        int last_update=-1;
        int updated;

        round++;

        /* I noticed that the first probe sent to an host always is way out.
         * So I completely randomize the order in which the probes are sent.
         */
        for (ri=0;ri<bing_stats.nb_sizes;ri++) {
            h=rand() % bing_stats.nb_sizes;
            if (ri!=h) {
                int tmp;
                tmp=randomizer[ri];
                randomizer[ri]=randomizer[h];
                randomizer[h]=tmp;
            }
        }

        updated=0;
        for (h=0;h<bing_stats.nb_hosts;h++) {
            for (m=0;m<bing_stats.nb_methods;m++) {

                /*printf("%d/%d:\n",h,m);*/
                /* Setup the probe handle for this method */
                method_init_probe(bing_stats.probe_handle,bing_stats.methods[m]);

                /* Perform the probes */
                if (do_probes(&bing_stats,h,m,randomizer)!=0) {
                    /* Some RTT has been updated and we should update our statistics */
                    updated=1;
                    do_host_regression(&bing_stats,h,m);
                }
            }

            if (updated!=0) {
                if (h>0)
                    do_link_regression(&bing_stats,h);
                /* Display the results for host h */
                print_statistics(&bing_stats,&last_update,h);
            }
        }

        if (last_update>=0) {
            int nb_hinvalid,nb_linvalid,nb_redo;
            int max_probes;

            do_host_cleanup(&bing_stats);
            nb_redo=do_probe_scheduling(&bing_stats,links,link_errors,&nb_hinvalid,&nb_linvalid);

            max_probes=bing_stats.nb_hosts*bing_stats.nb_sizes;
            printf("\nRound %d hinvalid: %3d (%3.1f%%), linvalid: %3d (%3.1f%%), redo: %3d (%3.1f%%), total: %4d (%3.1f%%)\n",
                round,
                nb_hinvalid,((double)100.0*nb_hinvalid)/max_probes,
                nb_linvalid,((double)100.0*nb_linvalid)/max_probes,
                nb_redo,((double)100.0*nb_redo)/max_probes,
                nb_hinvalid+nb_linvalid+nb_redo,((double)100.0*(nb_hinvalid+nb_linvalid+nb_redo))/max_probes);

#ifdef _DEBUG
            /* Display the RTTs and their state */
            for (m=0;m<bing_stats.nb_methods;m++) {
                printf("RTT status for method %d\n",m);
                for (h=0;h<bing_stats.nb_hosts;h++) {
                    printf("%d: ",h);
                    for (s=0;s<bing_stats.nb_sizes;s++) {
                        rtt_stats_t* rtt_stat=&bing_stats.hosts[h].rtt_laws[m].rtt_stats[s];
                        double rtt=(rtt_stat->state==RTT_STATE_HINVALID?rtt_stat->min_rtt_sav:rtt_stat->min_rtt);
                        if (rtt==DBL_MAX) {
                            printf("(-------) ");
                        } else {
                            char c1,c2;
                            switch (rtt_stat->state) {
                            case RTT_STATE_OK:
                                c1=c2=' ';
                                break;
                            case RTT_STATE_HINVALID:
                                c1='(';
                                c2=')';
                                break;
                            case RTT_STATE_LINVALID|RTT_STATE_LINVALID1:
                                c1='\\';
                                c2='/';
                                break;
                            case RTT_STATE_LINVALID|RTT_STATE_LINVALID2:
                                c1='/';
                                c2='\\';
                                break;
                            case RTT_STATE_LINVALID|RTT_STATE_LINVALID1|RTT_STATE_LINVALID2:
                                c1=c2='|';
                                break;
                            case RTT_STATE_REDO:
                                c1=c2='-';
                                break;
                            }
                            printf("%c%7.3f%c ",c1,rtt,c2);
                        }
                    }
                    printf("\n");
                }
            }
#endif
#ifdef _DEBUG
            /* Display the errors at the host level */
            for (m=0;m<bing_stats.nb_methods;m++) {
                printf("Host level regression errors for method %d\n",m);
                for (h=0;h<bing_stats.nb_hosts;h++) {
                    linreg_t* linreg=&bing_stats.hosts[h].rtt_laws[m].host_reg;
                    printf("%d: ",h);
                    for (s=0;s<bing_stats.nb_sizes;s++) {
                        rtt_stats_t* rtt_stat=&bing_stats.hosts[h].rtt_laws[m].rtt_stats[s];

                        if ((linreg->corr==0.0) ||
                            (rtt_stat->state==RTT_STATE_HINVALID)
                           ) {
                            printf("--------- ");
                        } else {
                            double err=rtt_stat->min_rtt-(linreg->a*rtt_stat->nb_bits+linreg->b);
                            printf("%9.4f ",err);
                        }
                    }
                    printf("\n");
                }
            }
#endif
#ifdef _DEBUG
            /* Display the link rtt differences */
            for (m=0;m<bing_stats.nb_methods;m++) {
                printf("Link level rtt differences for method %d\n",m);
                for (h=1;h<bing_stats.nb_hosts;h++) {
                    printf("%d: ",h);
                    for (s=0;s<bing_stats.nb_sizes;s++) {
                        rtt_stats_t* prtt_stat=&bing_stats.hosts[h-1].rtt_laws[m].rtt_stats[s];
                        rtt_stats_t* rtt_stat=&bing_stats.hosts[h].rtt_laws[m].rtt_stats[s];

                        if ((prtt_stat->state==RTT_STATE_HINVALID) ||
                            (prtt_stat->state==(RTT_STATE_LINVALID|RTT_STATE_LINVALID2)) ||
                            (rtt_stat->state==RTT_STATE_HINVALID) ||
                            (rtt_stat->state==(RTT_STATE_LINVALID|RTT_STATE_LINVALID1))
                           ) {
                            printf("--------- ");
                        } else {
                            double rttd=rtt_stat->min_rtt-prtt_stat->min_rtt;
                            printf("%9.4f ",rttd);
                        }
                    }
                    printf("\n");
                }
            }
#endif
#ifdef _DEBUG
            /* Display the errors at the link level */
            for (m=0;m<bing_stats.nb_methods;m++) {
                printf("Link level regression errors for method %d\n",m);
                for (h=1;h<bing_stats.nb_hosts;h++) {
                    linreg_t* linreg=&bing_stats.hosts[h].rtt_laws[m].link_reg;
                    printf("%d: ",h);
                    for (s=0;s<bing_stats.nb_sizes;s++) {
                        rtt_stats_t* prtt_stat=&bing_stats.hosts[h-1].rtt_laws[m].rtt_stats[s];
                        rtt_stats_t* rtt_stat=&bing_stats.hosts[h].rtt_laws[m].rtt_stats[s];

                        if ((linreg->corr==0.0) ||
                            (prtt_stat->state==RTT_STATE_HINVALID) ||
                            (prtt_stat->state==(RTT_STATE_LINVALID|RTT_STATE_LINVALID2)) ||
                            (rtt_stat->state==RTT_STATE_HINVALID) ||
                            (rtt_stat->state==(RTT_STATE_LINVALID|RTT_STATE_LINVALID1))
                           ) {
                            printf("--------- ");
                        } else {
                            double err=(rtt_stat->min_rtt-prtt_stat->min_rtt)-(linreg->a*rtt_stat->nb_bits+linreg->b);
                            printf("%9.4f ",err);
                        }
                    }
                    printf("\n");
                }
            }
#endif
        } else {
            printf(".");
            fflush(stdout);
        }
    }

    return 0;
}