/*      $KAME: dccp_tfrc.c,v 1.16 2006/03/01 17:34:08 nishida Exp $     */
/*      $NetBSD: dccp_tfrc.c,v 1.12 2024/05/12 23:55:58 msaitoh Exp $ */

/*
 * Copyright (c) 2003  Nils-Erik Mattsson
 * 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. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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: dccp_tfrc.c,v 1.47 2003/05/28 17:36:15 nilmat-8 Exp
 */

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: dccp_tfrc.c,v 1.12 2024/05/12 23:55:58 msaitoh Exp $");

#ifdef _KERNEL_OPT
#include "opt_dccp.h"
#endif

/*
 * This implementation conforms to the drafts of DCCP dated Mars 2003.
 * The options used are window counter, elapsed time, loss event rate
 * and receive rate.  No support for history discounting or oscillation
 * prevention.
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/domain.h>
#include <sys/kernel.h>
#include <sys/lock.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/proc.h>
#include <sys/protosw.h>
#include <sys/signalvar.h>
#include <sys/socket.h>
#include <sys/socketvar.h>
#include <sys/mutex.h>
#include <sys/sysctl.h>
#include <sys/syslog.h>
#include <sys/queue.h>
#include <sys/callout.h>

#include <net/if.h>

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

#include <netinet/in_pcb.h>
#include <netinet/in_var.h>
#include <netinet/ip_icmp.h>
#include <netinet/icmp_var.h>
#include <netinet/ip_var.h>

#include <netinet/dccp.h>
#include <netinet/dccp_var.h>
#include <netinet/dccp_tfrc.h>
#include <netinet/dccp_tfrc_lookup.h>

#define TFRCDEBUG
#if 0
#define TFRCDEBUGTIMERS
#define NOTFRCSENDER
#define NOTFRCRECV
#endif

#ifdef TFRCDEBUG
#ifdef __FreeBSD__
#define TFRC_DEBUG(args) log args
#else
#define TFRC_DEBUG(args) dccp_log args
#endif
#else
#define TFRC_DEBUG(args)
#endif

#ifdef TFRCDEBUGTIMERS
#ifdef __FreeBSD__
#define TFRC_DEBUG_TIME(args) log args
#else
#define TFRC_DEBUG_TIME(args) dccp_log args
#endif
#else
#define TFRC_DEBUG_TIME(args)
#endif

#if !defined(__FreeBSD__) || __FreeBSD_version < 500000
#define INP_INFO_LOCK_INIT(x,y)
#define INP_INFO_WLOCK(x)
#define INP_INFO_WUNLOCK(x)
#define INP_INFO_RLOCK(x)
#define INP_INFO_RUNLOCK(x)
#define INP_LOCK(x)
#define INP_UNLOCK(x)
#endif


/* Timeval operations */
const struct timeval delta_half = {0, TFRC_OPSYS_TIME_GRAN / 2};

/*
 * Half time value struct (accurate to +- 0.5us)
 * args:  tvp  -  pointer to timeval structure
 * Tested u:OK
 */
#define HALFTIMEVAL(tvp) \
        do { \
                if ((tvp)->tv_sec & 1)                          \
                        (tvp)->tv_usec += 1000000;              \
                (tvp)->tv_sec = (tvp)->tv_sec >> 1;             \
                (tvp)->tv_usec = (tvp)->tv_usec >> 1;           \
        } while (0)

/* Sender side */

/* Calculate new t_ipi (inter packet interval) by
 *    t_ipi = s/X_inst;
 * args:  ccbp - pointer to sender ccb block
 * Tested u:OK - Note: No check for x = 0 -> t_ipi = {0xFFF...,0xFFF}
 */
#define CALCNEWTIPI(ccbp) \
        do { \
                        struct fixpoint x1, y1;                                                                 \
                        x1.num = ccbp->s;                                                                               \
                        x1.denom = 1;                                                                                   \
                        fixpoint_div(&x1, &x1, &(ccbp)->x);                                             \
                        y1.num = (ccbp)->t_ipi.tv_sec = fixpoint_getlong(&x1);  \
                        y1.denom = 1;                                                                                   \
                        fixpoint_sub(&x1, &x1, &y1);                                                            \
                        y1.num = 1000000;                                                                               \
                        y1.denom = 1;                                                                                   \
                        fixpoint_mul(&x1, &x1, &y1);                                                            \
                        (ccbp)->t_ipi.tv_usec = fixpoint_getlong(&x1);                  \
        } while (0)

/* Calculate new delta by
 *    delta = min(t_ipi/2, t_gran/2);
 * args: ccbp - pointer to sender ccb block
 * Tested u:OK
 */
#define CALCNEWDELTA(ccbp) \
         do {                                                                                                   \
                        (ccbp)->delta = delta_half;                                                     \
                        if ((ccbp)->t_ipi.tv_sec == 0 &&                                        \
                            (ccbp)->t_ipi.tv_usec < TFRC_OPSYS_TIME_GRAN) {     \
                                (ccbp)->delta = (ccbp)->t_ipi;                                  \
                                HALFTIMEVAL(&((ccbp)->delta));                                  \
                        }                                                                                                       \
                 } while (0)

#ifdef TFRCDEBUG
#define PRINTFLOAT(x) TFRC_DEBUG((LOG_INFO, "%lld/%lld", (x)->num, (x)->denom));
#endif

const struct fixpoint tfrc_smallest_p = { 4LL, 1000000LL };

/* External declarations */
extern int dccp_get_option(char *, int, int, char *, int);

/* Forward declarations */
void tfrc_time_no_feedback(void *);
void tfrc_time_send(void *);
void tfrc_set_send_timer(struct tfrc_send_ccb *, struct timeval);
void tfrc_updateX(struct tfrc_send_ccb *, struct timeval);
const struct fixpoint *tfrc_calcX(u_int16_t, u_int32_t,
        const struct fixpoint *);
void tfrc_send_term(void *);

static void normalize(long long *, long long *);
struct fixpoint *fixpoint_add(struct fixpoint *, const struct fixpoint *,
        const struct fixpoint *);
struct fixpoint *fixpoint_sub(struct fixpoint *, const struct fixpoint *,
        const struct fixpoint *);
int fixpoint_cmp(const struct fixpoint *, const struct fixpoint *);
struct fixpoint *fixpoint_mul(struct fixpoint *, const struct fixpoint *,
        const struct fixpoint *);
struct fixpoint *fixpoint_div(struct fixpoint *, const struct fixpoint *,
        const struct fixpoint *);
long fixpoint_getlong(const struct fixpoint *);

const struct fixpoint *flookup(const struct fixpoint *);
const struct fixpoint *tfrc_flookup_reverse(const struct fixpoint *);

/*
 * Calculate the send rate according to TCP throughput eq.
 * args: s - packet size (in bytes)
 *       R - Round trip time  (in micro seconds)
 *       p - loss event rate  (0<=p<=1)
 * returns:  calculated send rate (in bytes per second)
 * Tested u:OK
 */
__inline const struct fixpoint *
tfrc_calcX(u_int16_t s, u_int32_t r, const struct fixpoint *p)
{
        static struct fixpoint x;

        x.num = 1000000 * s;
        x.denom = 1 * r;
        fixpoint_div(&x, &x, p);
        return &x;
}

/*
 * Function called by the send timer (to send packet)
 * args: cb -  sender congestion control block
 */
void
tfrc_time_send(void *ccb)
{
        struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
        int s;
        /*struct inpcb *inp;*/

        if (cb->state == TFRC_SSTATE_TERM) {
                TFRC_DEBUG((LOG_INFO, 
                        "TFRC - Send timer is ordered to terminate. (tfrc_time_send)\n"));
                return;
        }
        if (callout_pending(&cb->ch_stimer)) {
                TFRC_DEBUG((LOG_INFO,
                    "TFRC - Callout pending. (tfrc_time_send)\n"));
                return;
        }
        /* acquire locks for dccp_output */
        s = splsoftnet();
        INP_INFO_RLOCK(&dccpbinfo);
        /*inp = cb->pcb->d_inpcb;*/
        INP_LOCK(inp);
        INP_INFO_RUNLOCK(&dccpbinfo);

        callout_stop(&cb->ch_stimer);

        dccp_output(cb->pcb, 1);
        /* make sure we schedule next send time */
        tfrc_send_packet_sent(cb, 0, -1);

        /* release locks */
        INP_UNLOCK(inp);
        splx(s);
}
/*
 * Calculate and set when the send timer should expire
 * args: cb -  sender congestion control block
 *       t_now - timeval struct containing actual time
 * Tested u:OK
 */
void
tfrc_set_send_timer(struct tfrc_send_ccb * cb, struct timeval t_now)
{
        struct timeval t_temp;
        long t_ticks;

        /* set send timer to fire in t_ipi - (t_now-t_nom_old) or in other
         * words after t_nom - t_now */
        t_temp = cb->t_nom;
        timersub(&t_temp, &t_now, &t_temp);

#ifdef TFRCDEBUG
        if (t_temp.tv_sec < 0 || t_temp.tv_usec < 0)
                panic("TFRC - scheduled a negative time! (tfrc_set_send_timer)");
#endif

        t_ticks = (t_temp.tv_usec + 1000000 * t_temp.tv_sec) / (1000000 / hz);
        if (t_ticks == 0) t_ticks = 1;

        TFRC_DEBUG_TIME((LOG_INFO,
            "TFRC scheduled send timer to expire in %ld ticks (hz=%lu)\n", t_ticks, (unsigned long)hz));

        callout_reset(&cb->ch_stimer, t_ticks, tfrc_time_send, cb);
}

/*
 * Update X by
 *    If (p > 0)
 *       x_calc = calcX(s,R,p);
 *       X = max(min(X_calc, 2*X_recv), s/t_mbi);
 *    Else
 *       If (t_now - tld >= R)
 *          X = max(min("2*X, 2*X_recv),s/R);
 *          tld = t_now;
 * args: cb -  sender congestion control block
 *       t_now - timeval struct containing actual time
 * Tested u:OK
 */
void
tfrc_updateX(struct tfrc_send_ccb * cb, struct timeval t_now)
{
        struct fixpoint temp, temp2;
        struct timeval t_temp, t_rtt = {0, 0};

        /* to avoid large error in calcX */
        if (fixpoint_cmp(&cb->p, &tfrc_smallest_p) >= 0) {
                cb->x_calc = *tfrc_calcX(cb->s, cb->rtt, &cb->p);
                temp = cb->x_recv;
                temp.num *= 2;
                if (fixpoint_cmp(&cb->x_calc, &temp) < 0)
                        temp = cb->x_calc;
                cb->x = temp;
                temp2.num = cb->s;
                temp2.denom = TFRC_MAX_BACK_OFF_TIME;
                if (fixpoint_cmp(&temp, &temp2) < 0)
                        cb->x = temp2;
                normalize(&cb->x.num, &cb->x.denom);
                TFRC_DEBUG((LOG_INFO, "TFRC updated send rate to "));
                PRINTFLOAT(&cb->x);
                TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_updateX, p>0)\n"));
        } else {
                t_rtt.tv_usec = cb->rtt % 1000000;
                t_rtt.tv_sec = cb->rtt / 1000000;
                t_temp = t_now;
                timersub(&t_temp, &cb->t_ld, &t_temp);
                if (timercmp(&t_temp, &t_rtt, >=)) {
                        temp = cb->x_recv;
                        temp.num *= 2;
                        temp2 = cb->x;
                        temp2.num *= 2;
                        if (fixpoint_cmp(&temp2, &temp) < 0)
                                temp = temp2;
                        cb->x.num = cb->s;
                        cb->x.denom = 1;
                        cb->x.num *= 1000000;
                        cb->x.denom *= cb->rtt;
                        if (fixpoint_cmp(&temp, &cb->x) > 0)
                                cb->x = temp;
                        normalize(&cb->x.num, &cb->x.denom);
                        cb->t_ld = t_now;
                        TFRC_DEBUG((LOG_INFO, "TFRC updated send rate to "));
                        PRINTFLOAT(&cb->x);
                        TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_updateX, p==0)\n"));
                } else
                        TFRC_DEBUG((LOG_INFO, "TFRC didn't update send rate! (tfrc_updateX, p==0)\n"));
        }
}

/*
 * Function called by the no feedback timer
 * args:  cb -  sender congestion control block
 * Tested u:OK
 */
void
tfrc_time_no_feedback(void *ccb)
{
        struct fixpoint v, w;
        u_int32_t next_time_out = 1;    /* remove init! */
        struct timeval t_now;
        struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;

        mutex_enter(&(cb->mutex));

        if (cb->state == TFRC_SSTATE_TERM) {
                TFRC_DEBUG((LOG_INFO, "TFRC - No feedback timer is ordered to terminate\n"));
                goto nf_release;
        }
        if (callout_pending(&(cb)->ch_nftimer)) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Callout pending, exiting...(tfrc_time_no_feedback)\n"));
                goto nf_release;
        }
        switch (cb->state) {
        case TFRC_SSTATE_NO_FBACK:
                TFRC_DEBUG((LOG_INFO, "TFRC - no feedback timer expired, state NO_FBACK\n"));
                /* half send rate */
                cb->x.denom *= 2;
                v.num = cb->s;
                v.denom = TFRC_MAX_BACK_OFF_TIME;
                if (fixpoint_cmp(&cb->x, &v) < 0)
                        cb->x = v;

                TFRC_DEBUG((LOG_INFO, "TFRC updated send rate to "));
                PRINTFLOAT(&cb->x);
                TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_time_no_feedback\n"));

                /* reschedule next time out */

                v.num = 2;
                v.denom = 1;
                w.num = cb->s;
                w.denom = 1;
                fixpoint_mul(&v, &v, &w);
                fixpoint_div(&v, &v, &(cb->x));
                v.num *= 1000000;
                normalize(&v.num, &v.denom);
                next_time_out = v.num / v.denom;
                if (next_time_out < TFRC_INITIAL_TIMEOUT * 1000000)
                        next_time_out = TFRC_INITIAL_TIMEOUT * 1000000;
                break;
        case TFRC_SSTATE_FBACK:
                /*
                 * Check if IDLE since last timeout and recv rate is less than
                 * 4 packets per RTT
                 */

                v.num = cb->s;
                v.num *= 4;
                v.denom = cb->rtt;
                v.num *= 1000000;
                normalize(&v.num, &v.denom);
                if (!cb->idle || fixpoint_cmp(&cb->x_recv, &v) >= 0) {
                        TFRC_DEBUG((LOG_INFO, "TFRC - no feedback timer expired, state FBACK, not idle\n"));
                        /* Half sending rate */

                        /*
                         * If (X_calc > 2* X_recv) X_recv = max(X_recv/2,
                         * s/(2*t_mbi)); Else X_recv = X_calc/4;
                         */
                        v.num = TFRC_SMALLEST_P;
                        v.denom = 1;
                        if (fixpoint_cmp(&cb->p, &v) < 0 && cb->x_calc.num == 0)
                                panic("TFRC - X_calc is zero! (tfrc_time_no_feedback)\n");

                        /* check also if p i zero -> x_calc is infinity ?? */
                        w = cb->x_recv;
                        w.num *= 2;
                        if (fixpoint_cmp(&cb->p, &v) || fixpoint_cmp(&cb->x_calc, &w) > 0) {
                                cb->x_recv.denom *= 2;
                                w.num = cb->s;
                                w.denom *= (2 * TFRC_MAX_BACK_OFF_TIME);
                                if (fixpoint_cmp(&cb->x_recv, &w) < 0)
                                        cb->x_recv = w;
                        } else
                                cb->x_recv.denom *= 4;
                        normalize(&cb->x_recv.num, &cb->x_recv.denom);

                        /* Update sending rate */
                        microtime(&t_now);
                        tfrc_updateX(cb, t_now);
                }
                /* Schedule no feedback timer to expire in max(4*R, 2*s/X) */
                v.num = cb->s;
                v.num *= 2;
                fixpoint_div(&v, &v, &cb->x);
                v.num *= 1000000;
                next_time_out = v.num / v.denom;
                if (next_time_out < cb->t_rto)
                        next_time_out = cb->t_rto;
                break;
        default:
                panic("tfrc_no_feedback: Illegal state!");
                break;
        }

        /* Set timer */

        next_time_out = next_time_out / (1000000 / hz);
        if (next_time_out == 0)
                next_time_out = 1;

        TFRC_DEBUG_TIME((LOG_INFO, "TFRC scheduled no feedback timer to expire in %u ticks (hz=%u)\n", next_time_out, hz));

        callout_reset(&cb->ch_nftimer, next_time_out, tfrc_time_no_feedback, cb);

        /* set idle flag */
        cb->idle = 1;
nf_release:
        mutex_exit(&(cb->mutex));
}

/*
 * Removes ccb from memory
 * args: ccb - ccb of sender
 */
void
tfrc_send_term(void *ccb)
{
        struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;

        if (ccb == 0)
                panic("TFRC - Sender ccb is null! (free)");

        /* free sender */

        mutex_destroy(&(cb->mutex));

        free(cb, M_PCB);
        TFRC_DEBUG((LOG_INFO, "TFRC sender is destroyed\n"));
}

/* Functions declared in struct dccp_cc_sw */

/*
 * Initialises the sender side
 * args:  pcb - dccp protocol control block
 * returns: pointer to a tfrc_send_ccb struct on success, otherwise 0
 * Tested u:OK
 */
void *
tfrc_send_init(struct dccpcb * pcb)
{
        struct tfrc_send_ccb *ccb;

        ccb = malloc(sizeof(struct tfrc_send_ccb), M_PCB, M_NOWAIT | M_ZERO);
        if (ccb == 0) {
                TFRC_DEBUG((LOG_INFO, "Unable to allocate memory for tfrc_send_ccb!\n"));
                return 0;
        }
        /* init sender */

        mutex_init(&(ccb->mutex), MUTEX_DEFAULT, IPL_SOFTNET);

        ccb->pcb = pcb;
        if (ccb->pcb->avgpsize >= TFRC_MIN_PACKET_SIZE && ccb->pcb->avgpsize <= TFRC_MAX_PACKET_SIZE)
                ccb->s = (u_int16_t) ccb->pcb->avgpsize;
        else
                ccb->s = TFRC_STD_PACKET_SIZE;

        TFRC_DEBUG((LOG_INFO, "TFRC - Sender is using packet size %u\n", ccb->s));

        ccb->x.num = ccb->s;    /* set transmissionrate to 1 packet per second */
        ccb->x.denom = 1;
                                         
        ccb->t_ld.tv_sec = -1;
        ccb->t_ld.tv_usec = 0;

#ifdef TFRCDEBUG
        ccb->t_last_win_count.tv_sec = -1;
#endif
        callout_init(&ccb->ch_stimer, 0);
        callout_init(&ccb->ch_nftimer, 0);

        /* init packet history */
        TAILQ_INIT(&(ccb->hist));

        ccb->state = TFRC_SSTATE_NO_SENT;

        TFRC_DEBUG((LOG_INFO, "TFRC sender initialised!\n"));
        dccpstat.tfrcs_send_conn++;
        return ccb;
}

/*
 * Free the sender side
 * args: ccb - ccb of sender
 * Tested u:OK
 */
void
tfrc_send_free(void *ccb)
{
        struct s_hist_entry *elm, *elm2;
        struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;

        TFRC_DEBUG((LOG_INFO, "TFRC send free called!\n"));

        if (ccb == 0)
                return;

        /* uninit sender */

        /* get mutex */
        mutex_enter(&(cb->mutex));

        cb->state = TFRC_SSTATE_TERM;
        /* unschedule timers */
        callout_stop(&cb->ch_stimer);
        callout_stop(&cb->ch_nftimer);

        /* Empty packet history */
        elm = TAILQ_FIRST(&(cb->hist));
        while (elm != NULL) {
                elm2 = TAILQ_NEXT(elm, linfo);
                free(elm, M_TEMP);      /* M_TEMP ?? */
                elm = elm2;
        }
        TAILQ_INIT(&(cb->hist));

        mutex_exit(&(cb->mutex));

        /* schedule the removal of ccb */
        callout_reset(&cb->ch_stimer, TFRC_SEND_WAIT_TERM * hz, tfrc_send_term, cb);
}

/*
 * Ask TFRC whether one can send a packet or not
 * args: ccb  -  ccb block for current connection
 * returns: 1 if ok, else 0.
 */
int
tfrc_send_packet(void *ccb, long datasize)
{
        struct s_hist_entry *new_packet;
        u_int8_t answer = 0;
        u_int8_t win_count = 0;
        u_int32_t uw_win_count = 0;
        struct timeval t_now, t_temp;
        struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;
#ifdef NOTFRCSENDER
        return 1;
#endif

        /* check if pure ACK or Terminating */
        if (datasize == 0 || cb->state == TFRC_SSTATE_TERM) {
                return 1;
        } else if (cb->state == TFRC_SSTATE_TERM) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Asked to send packet when terminating!\n"));
                return 0;
        }
        /* we have data to send */
        mutex_enter(&(cb->mutex));

        /* check to see if we already have allocated memory last time */
        new_packet = TAILQ_FIRST(&(cb->hist));

        if ((new_packet != NULL && new_packet->t_sent.tv_sec >= 0) || new_packet == NULL) {
                /* check to see if we have memory to add to packet history */
                new_packet = malloc(sizeof(struct s_hist_entry), M_TEMP, M_NOWAIT);     /* M_TEMP?? */
                if (new_packet == NULL) {
                        TFRC_DEBUG((LOG_INFO, "TFRC - Not enough memory to add packet to packet history (send refused)! (tfrc_send_packet)\n"));
                        answer = 0;
                        dccpstat.tfrcs_send_nomem++;
                        goto sp_release;
                }
                new_packet->t_sent.tv_sec = -1; /* mark as unsent */
                TAILQ_INSERT_HEAD(&(cb->hist), new_packet, linfo);
        }
        switch (cb->state) {
        case TFRC_SSTATE_NO_SENT:
                TFRC_DEBUG((LOG_INFO, "TFRC - DCCP ask permission to send first data packet (tfrc_send_packet)\n"));
                microtime(&(cb->t_nom));        /* set nominal send time for initial packet */
                t_now = cb->t_nom;

                /* init feedback timer */

                callout_reset(&cb->ch_nftimer, TFRC_INITIAL_TIMEOUT * hz, tfrc_time_no_feedback, cb);
                win_count = 0;
                cb->t_last_win_count = t_now;
                TFRC_DEBUG((LOG_INFO, "TFRC - Permission granted. Scheduled no feedback timer (initial) to expire in %u ticks (hz=%u) (tfrc_send_packet)\n", TFRC_INITIAL_TIMEOUT * hz, hz));
                /* start send timer */

                /* Calculate new t_ipi */
                CALCNEWTIPI(cb);
                timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
                /* Calculate new delta */
                CALCNEWDELTA(cb);
                tfrc_set_send_timer(cb, t_now); /* if so schedule sendtimer */
                cb->state = TFRC_SSTATE_NO_FBACK;
                answer = 1;
                break;
        case TFRC_SSTATE_NO_FBACK:
        case TFRC_SSTATE_FBACK:
                if (!callout_pending(&cb->ch_stimer)) {
                        microtime(&t_now);

                        t_temp = t_now;
                        timeradd(&t_temp, &cb->delta, &t_temp);

                        if ((timercmp(&(t_temp), &(cb->t_nom), >))) {
                                /* Packet can be sent */

#ifdef TFRCDEBUG
                                if (cb->t_last_win_count.tv_sec == -1)
                                        panic("TFRC - t_last_win_count uninitialized (tfrc_send_packet)\n");
#endif
                                t_temp = t_now;
                                timersub(&t_temp, &(cb->t_last_win_count), &t_temp);

                                /* XXX calculate window counter */
                                if (cb->state == TFRC_SSTATE_NO_FBACK) {
                                        /* Assume RTT = t_rto(initial)/4 */
                                        uw_win_count = (t_temp.tv_sec + (t_temp.tv_usec / 1000000)) 
                                                        / TFRC_INITIAL_TIMEOUT / (4 * TFRC_WIN_COUNT_PER_RTT);
                                } else {
                                        if (cb->rtt)
                                                uw_win_count = (t_temp.tv_sec * 1000000 + t_temp.tv_usec) 
                                                                / cb->rtt / TFRC_WIN_COUNT_PER_RTT;
                                        else 
                                                uw_win_count = 0;
                                }
                                uw_win_count += cb->last_win_count;
                                win_count = uw_win_count % TFRC_WIN_COUNT_LIMIT;
                                answer = 1;
                        } else {
                                answer = 0;
                        }
                } else {
                        answer = 0;
                }
                break;
        default:
                panic("tfrc_send_packet: Illegal state!");
                break;
        }

        if (answer) {
                cb->pcb->ccval = win_count;
                new_packet->win_count = win_count;
        }

sp_release:
        mutex_exit(&(cb->mutex));
        return answer;
}
/* Notify sender that a packet has been sent
 * args: ccb - ccb block for current connection
 *       moreToSend - if there exists more packets to send
 *       dataSize -   packet size
 */
void
tfrc_send_packet_sent(void *ccb, int moreToSend, long datasize)
{
        struct timeval t_now, t_temp;
        struct s_hist_entry *packet;
        struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;

#ifdef NOTFRCSENDER
        return;
#endif

        if (cb->state == TFRC_SSTATE_TERM) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Packet sent when terminating!\n"));
                return;
        }
        mutex_enter(&(cb->mutex));
        microtime(&t_now);

        /* check if we have sent a data packet */
        if (datasize > 0) {
                /* add send time to history */
                packet = TAILQ_FIRST(&(cb->hist));
                if (packet == NULL)
                        panic("TFRC - Packet does not exist in history! (tfrc_send_packet_sent)");
                else if (packet != NULL && packet->t_sent.tv_sec >= 0)
                        panic("TFRC - No unsent packet in history! (tfrc_send_packet_sent)");
                packet->t_sent = t_now;
                packet->seq = cb->pcb->seq_snd;
                /* check if win_count have changed */
                if (packet->win_count != cb->last_win_count) {
                        cb->t_last_win_count = t_now;
                        cb->last_win_count = packet->win_count;
                }
                TFRC_DEBUG((LOG_INFO, "TFRC - Packet sent (%llu, %u, (%lu.%lu)", 
                        packet->seq, packet->win_count, packet->t_sent.tv_sec, packet->t_sent.tv_usec));
                cb->idle = 0;
        }

        /* if timer is running, do nothing */
        if (callout_pending(&cb->ch_stimer)) {
                goto sps_release;
        }

        switch (cb->state) {
        case TFRC_SSTATE_NO_SENT:
                /* if first was pure ack */
                if (datasize == 0) {
                        goto sps_release;
                } else
                        panic("TFRC - First packet sent is noted as a data packet in tfrc_send_packet_sent\n");
                break;
        case TFRC_SSTATE_NO_FBACK:
        case TFRC_SSTATE_FBACK:
                if (datasize <= 0) {    /* we have ack (or simulate a sent
                                                                 * packet which never can have
                                                                 * moreToSend */
                        moreToSend = 0;
                } else {
                        /* Calculate new t_ipi */
                        CALCNEWTIPI(cb);
                        timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
                        /* Calculate new delta */
                        CALCNEWDELTA(cb);
                }

                if (!moreToSend) {
                        /* loop until we find a send time in the future */
                        microtime(&t_now);
                        t_temp = t_now;
                        timeradd(&t_temp, &cb->delta, &t_temp);
                        while ((timercmp(&(t_temp), &(cb->t_nom), >))) {
                                /* Calculate new t_ipi */
                                CALCNEWTIPI(cb);
                                timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);

                                /* Calculate new delta */
                                CALCNEWDELTA(cb);

                                microtime(&t_now);
                                t_temp = t_now;
                                timeradd(&t_temp, &cb->delta, &t_temp);
                        }
                        tfrc_set_send_timer(cb, t_now);
                } else {
                        microtime(&t_now);
                        t_temp = t_now;
                        timeradd(&t_temp, &cb->delta, &t_temp);

                        /* Check if next packet can not be sent immediately */
                        if (!(timercmp(&(t_temp), &(cb->t_nom), >))) {
                                tfrc_set_send_timer(cb, t_now);         /* if so schedule sendtimer */
                        }
                }
                break;
        default:
                panic("tfrc_send_packet_sent: Illegal state!");
                break;
        }

sps_release:
        mutex_exit(&(cb->mutex));
}
/* Notify that a an ack package was received (i.e. a feedback packet)
 * args: ccb  -  ccb block for current connection
 */
void
tfrc_send_packet_recv(void *ccb, char *options, int optlen)
{
        u_int32_t next_time_out;
        struct timeval t_now;
        struct fixpoint x,y;
        int res;
        u_int16_t t_elapsed = 0;
        u_int32_t t_elapsed_l = 0;
        u_int32_t pinv;
        u_int32_t x_recv;

        u_int32_t r_sample;

        struct s_hist_entry *elm, *elm2;
        struct tfrc_send_ccb *cb = (struct tfrc_send_ccb *) ccb;

#ifdef NOTFRCSENDER
        return;
#endif

        if (cb->state == TFRC_SSTATE_TERM) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Sender received a packet when terminating!\n"));
                return;
        }
        /* we are only interested in ACKs */
        if (!(cb->pcb->type_rcv == DCCP_TYPE_ACK || cb->pcb->type_rcv == DCCP_TYPE_DATAACK))
                return;

        res = dccp_get_option(options, optlen, TFRC_OPT_LOSS_RATE, (char *) &pinv, 6);
        if (res == 0) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Missing Loss rate option! (tfrc_send_packet_recv)\n"));
                dccpstat.tfrcs_send_noopt++;
                return;
        }

        res = dccp_get_option(options, optlen, DCCP_OPT_ELAPSEDTIME, (char *) &t_elapsed_l, 6);
        if (res == 0) {
                /* try 2 bytes elapsed time */
                res = dccp_get_option(options, optlen, DCCP_OPT_ELAPSEDTIME, (char *) &t_elapsed, 4);
                if (res == 0){
                        TFRC_DEBUG((LOG_INFO, "TFRC - Missing elapsed time option! (tfrc_send_packet_recv)\n"));
                        dccpstat.tfrcs_send_noopt++;
                        return;
                }
        }
        res = dccp_get_option(options, optlen, TFRC_OPT_RECEIVE_RATE, (char *) &x_recv, 4);
        if (res == 0) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Missing x_recv option! (tfrc_send_packet_recv)\n"));
                dccpstat.tfrcs_send_noopt++;
                return;
        }
        dccpstat.tfrcs_send_fbacks++;
        /* change byte order */
        if (t_elapsed)
                t_elapsed = ntohs(t_elapsed);
        else
                t_elapsed_l = ntohl(t_elapsed_l);
        x_recv = ntohl(x_recv);
        pinv = ntohl(pinv);
        if (pinv == 0xFFFFFFFF) pinv = 0;

        if (t_elapsed)
                TFRC_DEBUG((LOG_INFO, "TFRC - Received options on ack %llu: pinv=%u, t_elapsed=%u, x_recv=%u ! (tfrc_send_packet_recv)\n", cb->pcb->ack_rcv, pinv, t_elapsed, x_recv));
        else
                TFRC_DEBUG((LOG_INFO, "TFRC - Received options on ack %llu: pinv=%u, t_elapsed=%u, x_recv=%u ! (tfrc_send_packet_recv)\n", cb->pcb->ack_rcv, pinv, t_elapsed_l, x_recv));

        mutex_enter(&(cb->mutex));

        switch (cb->state) {
        case TFRC_SSTATE_NO_FBACK:
        case TFRC_SSTATE_FBACK:
                /* Calculate new round trip sample by R_sample = (t_now -
                 * t_recvdata)-t_delay; */

                /* get t_recvdata from history */
                elm = TAILQ_FIRST(&(cb->hist));
                while (elm != NULL) {
                        if (elm->seq == cb->pcb->ack_rcv)
                                break;
                        elm = TAILQ_NEXT(elm, linfo);
                }

                if (elm == NULL) {
                        TFRC_DEBUG((LOG_INFO, 
                                "TFRC - Packet does not exist in history (seq=%llu)! (tfrc_send_packet_recv)", cb->pcb->ack_rcv));
                        goto sar_release;
                }
                /* Update RTT */
                microtime(&t_now);
                timersub(&t_now, &(elm->t_sent), &t_now);
                r_sample = t_now.tv_sec * 1000000 + t_now.tv_usec;
                if (t_elapsed)
                        r_sample = r_sample - ((u_int32_t) t_elapsed * 10); /* t_elapsed in us */       
                else
                        r_sample = r_sample - (t_elapsed_l * 10);       /* t_elapsed in us */

                /* Update RTT estimate by If (No feedback recv) R = R_sample;
                 * Else R = q*R+(1-q)*R_sample; */
                if (cb->state == TFRC_SSTATE_NO_FBACK) {
                        cb->state = TFRC_SSTATE_FBACK;
                        cb->rtt = r_sample;
                } else {
                        cb->rtt = (u_int32_t) (TFRC_RTT_FILTER_CONST * cb->rtt +
                            (1 - TFRC_RTT_FILTER_CONST) * r_sample);
                }

                TFRC_DEBUG((LOG_INFO, "TFRC - New RTT estimate %u (tfrc_send_packet_recv)\n", cb->rtt));

                /* Update timeout interval */
                cb->t_rto = 4 * cb->rtt;

                /* Update receive rate */
                x.num = x_recv;
                y.num = 8;
                x.denom = y.denom = 1;
                fixpoint_div(&(cb)->x_recv, &x, &y);

                /* Update loss event rate */
                if (pinv == 0) {
                        cb->p.num = cb->p.denom = 0;
                } else {
                        cb->p.num  = 1.0;
                        cb->p.denom = pinv;
                        if (fixpoint_cmp(&cb->p, &tfrc_smallest_p) <= 0) {
                                cb->p.num  = tfrc_smallest_p.num;
                                cb->p.denom  = tfrc_smallest_p.denom;
                                TFRC_DEBUG((LOG_INFO, "TFRC - Smallest p used!\n"));
                        }
                }

                /* unschedule no feedback timer */
                if (!callout_pending(&cb->ch_nftimer)) {
                        callout_stop(&cb->ch_nftimer);
                }
                /* Update sending rate */
                microtime(&t_now);
                tfrc_updateX(cb, t_now);

                /* Update next send time */
                timersub(&cb->t_nom, &cb->t_ipi, &cb->t_nom);

                /* Calculate new t_ipi */
                CALCNEWTIPI(cb);
                timeradd(&cb->t_nom, &cb->t_ipi, &cb->t_nom);
                /* Calculate new delta */
                CALCNEWDELTA(cb);

                if (callout_pending(&cb->ch_stimer)) {
                        callout_stop(&cb->ch_stimer);
                }

#if 0 /* XXX do not send ack of ack so far */ 
                dccp_output(cb->pcb, 1);
                tfrc_send_packet_sent(cb, 0, -1);       /* make sure we schedule next send time */
#endif

                /* remove all packets older than the one acked from history */
                /* elm points to acked package! */

                elm2 = TAILQ_NEXT(elm, linfo);

                while (elm2 != NULL) {
                        TAILQ_REMOVE(&(cb->hist), elm2, linfo);
                        free(elm2, M_TEMP);
                        elm2 = TAILQ_NEXT(elm, linfo);
                }

                /* Schedule no feedback timer to expire in max(4*R, 2*s/X) */
                /* next_time_out = (u_int32_t) (2 * cb->s * 1000000 / cb->x); */

                x.num = 2;
                x.denom = 1;
                y.num = cb->s;
                y.denom = 1;
                fixpoint_mul(&x, &x, &y);
                fixpoint_div(&x, &x, &(cb->x));
                x.num *= 1000000;
                normalize(&x.num, &x.denom);
                next_time_out = x.num / x.denom;

                if (next_time_out < cb->t_rto)
                        next_time_out = cb->t_rto;
                TFRC_DEBUG_TIME((LOG_INFO,
                        "TFRC - Scheduled no feedback timer to expire in %u ticks (%u us) (hz=%u)(tfrc_send_packet_recv)\n",
                        next_time_out / (1000000 / hz), next_time_out, hz));
                next_time_out = next_time_out / (1000000 / hz);
                if (next_time_out == 0)
                        next_time_out = 1;

                callout_reset(&cb->ch_nftimer, next_time_out, tfrc_time_no_feedback, cb);

                /* set idle flag */
                cb->idle = 1;
                break;
        default:
                panic("tfrc_send_packet_recv: Illegal state!");
                break;
        }
sar_release:
        mutex_exit(&(cb->mutex));
}
/* Receiver side */

/* Forward declarations */
long tfrc_calclmean(struct tfrc_recv_ccb *);
void tfrc_recv_send_feedback(struct tfrc_recv_ccb *);
int tfrc_recv_add_hist(struct tfrc_recv_ccb *, struct r_hist_entry *);
void tfrc_recv_detectLoss(struct tfrc_recv_ccb *);
u_int32_t tfrc_recv_calcFirstLI(struct tfrc_recv_ccb *);
void tfrc_recv_updateLI(struct tfrc_recv_ccb *, long, u_int8_t);

/* Weights used to calculate loss event rate */
/* const double tfrc_recv_w[] = { 1,  1,   1,   1,  0.8,  0.6, 0.4, 0.2}; */
const struct fixpoint tfrc_recv_w[] = {{1,1},  {1,1},  {1,1},  {1,1},  {4,5},  {3,5}, {2,5}, {1,5}};

/* Find a data packet in history
 * args:  cb - ccb of receiver
 *        elm - pointer to element (variable)
 *        num - number in history (variable)
 * returns:  elm points to found packet, otherwise NULL
 * Tested u:OK
 */
#define TFRC_RECV_FINDDATAPACKET(cb,elm,num) \
  do { \
    elm = TAILQ_FIRST(&((cb)->hist)); \
      while ((elm) != NULL) { \
        if ((elm)->type == DCCP_TYPE_DATA || (elm)->type == DCCP_TYPE_DATAACK) \
          (num)--; \
        if (num == 0) \
          break; \
        elm = TAILQ_NEXT((elm), linfo); \
      } \
  } while (0)

/* Find next data packet in history
 * args:  cb - ccb of receiver
 *        elm - pointer to element (variable)
 * returns:  elm points to found packet, otherwise NULL
 * Tested u:OK
 */
#define TFRC_RECV_NEXTDATAPACKET(cb,elm) \
  do { \
    if (elm != NULL) { \
      elm = TAILQ_NEXT(elm, linfo); \
      while ((elm) != NULL && (elm)->type != DCCP_TYPE_DATA && (elm)->type != DCCP_TYPE_DATAACK) { \
        elm = TAILQ_NEXT((elm), linfo); \
      } \
    } \
  } while (0)

/*
 * Calculate avarage loss Interval I_mean
 * args: cb - ccb of receiver
 * returns: avarage loss interval
 * Tested u:OK
 */
long 
tfrc_calclmean(struct tfrc_recv_ccb * cb)
{
        struct li_hist_entry *elm;
        struct fixpoint l_tot;
        struct fixpoint l_tot0 = {0,0};
        struct fixpoint l_tot1 = {0,0};
        struct fixpoint W_tot = {0, 0};
        struct fixpoint tmp;
        int i;
        elm = TAILQ_FIRST(&(cb->li_hist));

        for (i = 0; i < TFRC_RECV_IVAL_F_LENGTH; i++) {
#ifdef TFRCDEBUG
                if (elm == 0)
                        goto I_panic;
#endif

/* 
                I_tot0 = I_tot0 + (elm->interval * tfrc_recv_w[i]);
                W_tot = W_tot + tfrc_recv_w[i];
*/
                tmp.num = elm->interval;
                tmp.denom = 1;
                fixpoint_mul(&tmp, &tmp, &tfrc_recv_w[i]);
                fixpoint_add(&l_tot0, &l_tot0, &tmp);
                fixpoint_add(&W_tot, &W_tot, &tfrc_recv_w[i]);

                elm = TAILQ_NEXT(elm, linfo);
        }

        elm = TAILQ_FIRST(&(cb->li_hist));
        elm = TAILQ_NEXT(elm, linfo);

        for (i = 1; i <= TFRC_RECV_IVAL_F_LENGTH; i++) {
#ifdef TFRCDEBUG
                if (elm == 0)
                        goto I_panic;
#endif
/* 
                I_tot1 = I_tot1 + (elm->interval * tfrc_recv_w[i - 1]);
*/
                tmp.num = elm->interval;
                tmp.denom = 1;
                fixpoint_mul(&tmp, &tmp, &tfrc_recv_w[i-1]);
                fixpoint_add(&l_tot1, &l_tot1, &tmp);

                elm = TAILQ_NEXT(elm, linfo);
        }

        /* I_tot = max(I_tot0, I_tot1) */
        /*
        I_tot = I_tot0;
        if (I_tot0 < I_tot1)
                I_tot = I_tot1;

        if (I_tot < W_tot)
                I_tot = W_tot;
        return (I_tot / W_tot);
        */

        l_tot.num = l_tot0.num;
        l_tot.denom = l_tot0.denom;
        if (fixpoint_cmp(&l_tot0, &l_tot1) < 0){
                l_tot.num = l_tot1.num;
                l_tot.denom = l_tot1.denom;
        }

        if (fixpoint_cmp(&l_tot, &W_tot) < 0){
                l_tot.num = W_tot.num;
                l_tot.denom = W_tot.denom;
        }
        fixpoint_div(&tmp, &l_tot, &W_tot);
        return(fixpoint_getlong(&tmp));

#ifdef TFRCDEBUG
I_panic:
        panic("TFRC - Missing entry in interval history! (tfrc_calclmean)");
#endif
}

/*
 * Send a feedback packet
 * args: cb - ccb for receiver
 * Tested u:OK
 */
void
tfrc_recv_send_feedback(struct tfrc_recv_ccb * cb)
{
        u_int32_t x_recv, pinv;
        u_int32_t t_elapsed;
        struct r_hist_entry *elm;
        struct fixpoint x;
        struct timeval t_now, t_temp;
        int num;

        x.num = 1;
        x.denom = 4000000000LL;         /* -> 1/p > 4 000 000 000 */
        if (fixpoint_cmp(&cb->p, &x) < 0)       
                /*  if (cb->p < 0.00000000025)  -> 1/p > 4 000 000 000 */
                pinv = 0xFFFFFFFF;
        else {
                /*      pinv = (u_int32_t) (1.0 / cb->p); */
                x.num = 1;
                x.denom = 1;
                fixpoint_div(&x, &x, &(cb)->p);
                pinv = fixpoint_getlong(&x);
        }                       

        switch (cb->state) {
        case TFRC_RSTATE_NO_DATA:
                x_recv = 0;
                break;
        case TFRC_RSTATE_DATA:
                /* Calculate x_recv */
                microtime(&t_temp);
                timersub(&t_temp, &cb->t_last_feedback, &t_temp);

                x_recv = (u_int32_t) (cb->bytes_recv * 8 * 1000000) / (t_temp.tv_sec * 1000000 + t_temp.tv_usec);

                break;
        default:
                panic("tfrc_recv_send_feedback: Illegal state!");
                break;
        }

        /* Find largest win_count so far (data packet with highest seqnum so far) */
        num = 1;
        TFRC_RECV_FINDDATAPACKET(cb, elm, num);

        if (elm == NULL)
                panic("No data packet in history! (tfrc_recv_send_feedback)");


        microtime(&t_now);
        timersub(&t_now, &elm->t_recv, &t_now);
        t_elapsed = (u_int32_t) (t_now.tv_sec * 100000 + t_now.tv_usec / 10);

        /* change byte order */
        t_elapsed = htonl(t_elapsed);
        x_recv = htonl(x_recv);
        pinv = htonl(pinv);

        /* add options from variables above */
        if (dccp_add_option(cb->pcb, TFRC_OPT_LOSS_RATE, (char *) &pinv, 4)
            || dccp_add_option(cb->pcb, DCCP_OPT_ELAPSEDTIME, (char *) &t_elapsed, 4)
            || dccp_add_option(cb->pcb, TFRC_OPT_RECEIVE_RATE, (char *) &x_recv, 4)) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Can't add options, aborting send feedback (tfrc_send_feedback)"));
                /* todo: remove options */
                dccpstat.tfrcs_recv_erropt++;
                return;
        }
        cb->pcb->ack_snd = elm->seq;
        cb->last_counter = elm->win_count;
        cb->seq_last_counter = elm->seq;
        microtime(&(cb->t_last_feedback));
        cb->bytes_recv = 0;

        TFRC_DEBUG_TIME((LOG_INFO, "TFRC - Sending a feedback packet with (t_elapsed %u, pinv %x, x_recv %u, ack=%llu) (tfrc_recv_send_feedback)\n", ntohs(t_elapsed), ntohl(pinv), ntohl(x_recv), elm->seq));

        dccpstat.tfrcs_recv_fbacks++;
        dccp_output(cb->pcb, 1);
}
/*
 * Calculate first loss interval
 * args: cb - ccb of the receiver
 * returns: loss interval
 * Tested u:OK
 */
u_int32_t
tfrc_recv_calcFirstLI(struct tfrc_recv_ccb * cb)
{
        struct r_hist_entry *elm, *elm2;
        struct timeval t_temp;
        int temp;
        struct fixpoint x_recv, fval, t_rtt, x;
        const struct fixpoint *fval2;
        int win_count;

        temp = 1;
        TFRC_RECV_FINDDATAPACKET(cb, elm, temp);

        if (elm == NULL)
                panic("Packet history contains no data packets! (tfrc_recv_calcFirstLI)\n");
        t_temp = elm->t_recv;
        win_count = elm->win_count;
        elm2 = elm;
        TFRC_RECV_NEXTDATAPACKET(cb, elm2);
        while (elm2 != NULL) {
                temp = win_count - (int) (elm2->win_count);
                if (temp < 0)
                        temp = temp + TFRC_WIN_COUNT_LIMIT;

                if (temp > 4)
                        break;
                elm = elm2;
                TFRC_RECV_NEXTDATAPACKET(cb, elm2);
        }

        if (elm2 == NULL) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Could not find a win_count interval > 4 \n"));
                elm2 = elm;
                if (temp == 0) {
                        TFRC_DEBUG((LOG_INFO, "TFRC - Could not find a win_count interval > 0. Defaulting to 1 (tfrc_recv_calcFirstLI)\n"));
                        temp = 1;
                }
        }
        timersub(&t_temp, &elm2->t_recv, &t_temp);
        t_rtt.num = t_temp.tv_sec * 1000000 + t_temp.tv_usec;
        t_rtt.denom = 1000000;

        if (t_rtt.num < 0 && t_rtt.denom < 0) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Approximation of RTT is negative!\n"));
                t_rtt.num = -t_rtt.num;
                t_rtt.denom = -t_rtt.denom;
        }

        TFRC_DEBUG((LOG_INFO, "TFRC - Approximated rtt to "));
        PRINTFLOAT(&t_rtt);
        TFRC_DEBUG((LOG_INFO, " s (tfrc_recv_calcFirstLI)\n"));

        /* Calculate x_recv */
        microtime(&t_temp);
        timersub(&t_temp, &cb->t_last_feedback, &t_temp);
        /*
                x_recv = (((double) (cb->bytes_recv)) /
            (((double) t_temp.tv_sec) + ((double) t_temp.tv_usec) / 1000000.0));
        */
        x_recv.num = cb->bytes_recv * 1000000;
        x_recv.denom = t_temp.tv_sec * 1000000 + t_temp.tv_usec;

        TFRC_DEBUG((LOG_INFO, "TFRC - Receive rate XXX"));
        PRINTFLOAT(&x_recv);
        TFRC_DEBUG((LOG_INFO, " bytes/s (tfrc_recv_calcFirstLI)\n"));

        /*      fval = ((double) (cb->s)) / (x_recv * t_rtt); */
        fval.num = cb->s;
        fval.denom = 1;
        fixpoint_div(&fval, &fval, &x_recv);
        fixpoint_div(&fval, &fval, &t_rtt);

        TFRC_DEBUG((LOG_INFO, "TFRC - Fvalue to locate XXX"));
        PRINTFLOAT(&fval);
        TFRC_DEBUG((LOG_INFO, " (tfrc_recv_calcFirstLI)\n"));
        fval2 = tfrc_flookup_reverse(&fval);
        TFRC_DEBUG((LOG_INFO, "TFRC - Lookup gives p= XXX"));
        PRINTFLOAT(&fval);
        TFRC_DEBUG((LOG_INFO, " (tfrc_recv_calcFirstLI)\n"));
        if (fval2->num == 0 && fval2->denom == 0)
                return (u_int32_t) 0xFFFFFFFF;
        x.num = x.denom = 1;
        fixpoint_div(&x, &x, fval2);
        return (u_int32_t) (fixpoint_getlong(&x));
}
/* Add packet to recv history (sorted on seqnum)
 * Do not add packets that are already lost
 * args: cb - ccb of receiver
 *       packet - packet to insert
 * returns:  1 if the packet was considered lost, 0 otherwise
 * Tested u:OK
 */
int
tfrc_recv_add_hist(struct tfrc_recv_ccb * cb, struct r_hist_entry * packet)
{
        struct r_hist_entry *elm, *elm2;
        u_int8_t num_later = 0, win_count;
        u_int32_t seq_num = packet->seq;
        int temp;

        TFRC_DEBUG((LOG_INFO, "TFRC - Adding packet (seq=%llu,win_count=%u,type=%u,ndp=%u) to history! (tfrc_recv_add_hist)\n", packet->seq, packet->win_count, packet->type, packet->ndp));

        if (TAILQ_EMPTY(&(cb->hist))) {
                TAILQ_INSERT_HEAD(&(cb->hist), packet, linfo);
        } else {
                elm = TAILQ_FIRST(&(cb->hist));
                if ((seq_num > elm->seq
                        && seq_num - elm->seq < TFRC_RECV_NEW_SEQ_RANGE) ||
                    (seq_num < elm->seq
                        && elm->seq - seq_num > DCCP_SEQ_NUM_LIMIT - TFRC_RECV_NEW_SEQ_RANGE)) {
                        TAILQ_INSERT_HEAD(&(cb->hist), packet, linfo);
                } else {
                        if (elm->type == DCCP_TYPE_DATA || elm->type == DCCP_TYPE_DATAACK)
                                num_later = 1;

                        elm2 = TAILQ_NEXT(elm, linfo);
                        while (elm2 != NULL) {
                                if ((seq_num > elm2->seq
                                        && seq_num - elm2->seq < TFRC_RECV_NEW_SEQ_RANGE) ||
                                    (seq_num < elm2->seq
                                        && elm2->seq - seq_num > DCCP_SEQ_NUM_LIMIT - TFRC_RECV_NEW_SEQ_RANGE)) {
                                        TAILQ_INSERT_AFTER(&(cb->hist), elm, packet, linfo);
                                        break;
                                }
                                elm = elm2;
                                elm2 = TAILQ_NEXT(elm, linfo);

                                if (elm->type == DCCP_TYPE_DATA || elm->type == DCCP_TYPE_DATAACK)
                                        num_later++;

                                if (num_later == TFRC_RECV_NUM_LATE_LOSS) {
                                        free(packet, M_TEMP);
                                        TFRC_DEBUG((LOG_INFO, "TFRC - Packet already lost! (tfrc_recv_add_hist)\n"));
                                        return 1;
                                        break;
                                }
                        }

                        if (elm2 == NULL && num_later < TFRC_RECV_NUM_LATE_LOSS) {
                                TAILQ_INSERT_TAIL(&(cb->hist), packet, linfo);
                        }
                }
        }

        /* trim history (remove all packets after the NUM_LATE_LOSS+1 data
         * packets) */
        if (TAILQ_FIRST(&(cb->li_hist)) != NULL) {
                num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
                TFRC_RECV_FINDDATAPACKET(cb, elm, num_later);
                if (elm != NULL) {
                        elm2 = TAILQ_NEXT(elm, linfo);
                        while (elm2 != NULL) {
                                TAILQ_REMOVE(&(cb->hist), elm2, linfo);
                                free(elm2, M_TEMP);
                                elm2 = TAILQ_NEXT(elm, linfo);
                        }
                }
        } else {
                /* we have no loss interval history so we need at least one
                 * rtt:s of data packets to approximate rtt */
                num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
                TFRC_RECV_FINDDATAPACKET(cb, elm2, num_later);
                if (elm2 != NULL) {
                        num_later = 1;
                        TFRC_RECV_FINDDATAPACKET(cb, elm, num_later);
                        win_count = elm->win_count;

                        elm = elm2;
                        TFRC_RECV_NEXTDATAPACKET(cb, elm2);
                        while (elm2 != NULL) {
                                temp = win_count - (int) (elm2->win_count);
                                if (temp < 0)
                                        temp = temp + TFRC_WIN_COUNT_LIMIT;

                                if (temp > TFRC_WIN_COUNT_PER_RTT + 1) {
                                        /* we have found a packet older than
                                         * one rtt remove the rest */
                                        elm = TAILQ_NEXT(elm2, linfo);

                                        while (elm != NULL) {
                                                TAILQ_REMOVE(&(cb->hist), elm, linfo);
                                                free(elm, M_TEMP);
                                                elm = TAILQ_NEXT(elm2, linfo);
                                        }
                                        break;
                                }
                                elm = elm2;
                                TFRC_RECV_NEXTDATAPACKET(cb, elm2);
                        }
                }               /* end if (exist atleast 4 data packets) */
        }

        return 0;
}
/*
 * Detect loss events and update loss interval history
 * args: cb - ccb of the receiver
 * Tested u:OK
 */
void
tfrc_recv_detectLoss(struct tfrc_recv_ccb * cb)
{
        struct r_hist_entry *bLoss, *aLoss, *elm, *elm2;
        u_int8_t num_later = TFRC_RECV_NUM_LATE_LOSS;
        long seq_temp = 0;
        long seq_loss = -1;
        u_int8_t win_loss = 0;

        TFRC_RECV_FINDDATAPACKET(cb, bLoss, num_later);

        if (bLoss == NULL) {
                /* not enough packets yet to cause the first loss event */
        } else {                /* bloss != NULL */
                num_later = TFRC_RECV_NUM_LATE_LOSS + 1;
                TFRC_RECV_FINDDATAPACKET(cb, aLoss, num_later);
                if (aLoss == NULL) {
                        if (TAILQ_EMPTY(&(cb->li_hist))) {
                                /* no loss event have occurred yet */

                                /* todo: find a lost data packet by comparing
                                 * to initial seq num */

                        } else {
                                panic("Less than 4 data packets in history (tfrc_recv_detecLossEvent)\n");
                        }
                } else {        /* aLoss != NULL */
                        /* locate a lost data packet */
                        elm = bLoss;
                        elm2 = TAILQ_NEXT(elm, linfo);
                        do {
                                seq_temp = ((long) (elm->seq)) - ((long) elm2->seq);

                                if (seq_temp < 0)
                                        seq_temp = seq_temp + DCCP_SEQ_NUM_LIMIT;

                                if (seq_temp != 1) {
                                        /* check no data packets */
                                        if (elm->type == DCCP_TYPE_DATA || elm->type == DCCP_TYPE_DATAACK)
                                                seq_temp = seq_temp - 1;
                                        if (seq_temp % DCCP_NDP_LIMIT != ((int) elm->ndp - (int) elm2->ndp + DCCP_NDP_LIMIT) % DCCP_NDP_LIMIT)
                                                seq_loss = (elm2->seq + 1) % DCCP_SEQ_NUM_LIMIT;
                                }
                                elm = elm2;
                                elm2 = TAILQ_NEXT(elm2, linfo);
                        } while (elm != aLoss);

                        if (seq_loss != -1) {
                                win_loss = aLoss->win_count;
                        }
                }
        }                       /* end if (bLoss == NULL) */
        tfrc_recv_updateLI(cb, seq_loss, win_loss);
}
/* Updates the loss interval history
 * cb   -  congestion control block
 * seq_loss  -  sequence number of lost packet (-1 for none)
 * win_loss  -  window counter for previous (from the lost packet view) packet
 * Tested u:OK
 */
void
tfrc_recv_updateLI(struct tfrc_recv_ccb * cb, long seq_loss, u_int8_t win_loss)
{
        struct r_hist_entry *elm;
        struct li_hist_entry *li_elm, *li_elm2;
        u_int8_t num_later = TFRC_RECV_NUM_LATE_LOSS;
        long seq_temp = 0;
        int i;
        u_int8_t win_start;
        int debug_info = 0;
        if (seq_loss != -1) {   /* we have found a packet loss! */
                dccpstat.tfrcs_recv_losts++;
                TFRC_DEBUG((LOG_INFO, "TFRC - seqloss=%i, winloss=%i\n", (int) seq_loss, (int) win_loss));
                if (TAILQ_EMPTY(&(cb->li_hist))) {
                        debug_info = 1;
                        /* first loss detected */
                        TFRC_DEBUG((LOG_INFO, "TFRC - First loss event detected! (tfrc_recv_updateLI)\n"));
                        /* create history */
                        for (i = 0; i < TFRC_RECV_IVAL_F_LENGTH + 1; i++) {
                                li_elm = malloc(sizeof(struct li_hist_entry),
                                    M_TEMP, M_NOWAIT | M_ZERO); /* M_TEMP?? */
                                if (li_elm == NULL) {
                                        TFRC_DEBUG((LOG_INFO, "TFRC - Not enough memory for loss interval history!\n"));
                                        /* Empty loss interval history */
                                        li_elm = TAILQ_FIRST(&(cb->li_hist));
                                        while (li_elm != NULL) {
                                                li_elm2 = TAILQ_NEXT(li_elm, linfo);
                                                free(li_elm, M_TEMP);   /* M_TEMP ?? */
                                                li_elm = li_elm2;
                                        }
                                        return;
                                }
                                TAILQ_INSERT_HEAD(&(cb->li_hist), li_elm, linfo);
                        }

                        li_elm->seq = seq_loss;
                        li_elm->win_count = win_loss;

                        li_elm = TAILQ_NEXT(li_elm, linfo);
                        /* add approx interval */
                        li_elm->interval = tfrc_recv_calcFirstLI(cb);

                } else {        /* we have a loss interval history */
                        debug_info = 2;
                        /* Check if the loss is in the same loss event as
                         * interval start */
                        win_start = (TAILQ_FIRST(&(cb->li_hist)))->win_count;
                        if ((win_loss > win_start
                                && win_loss - win_start > TFRC_WIN_COUNT_PER_RTT) ||
                            (win_loss < win_start
                                && win_start - win_loss < TFRC_WIN_COUNT_LIMIT - TFRC_WIN_COUNT_PER_RTT)) {
                                /* new loss event detected */
                                /* calculate last interval length */
                                seq_temp = seq_loss - ((long) ((TAILQ_FIRST(&(cb->li_hist)))->seq));
                                if (seq_temp < 0)
                                        seq_temp = seq_temp + DCCP_SEQ_NUM_LIMIT;

                                (TAILQ_FIRST(&(cb->li_hist)))->interval = seq_temp;

                                TFRC_DEBUG((LOG_INFO, "TFRC - New loss event detected!, interval %i (tfrc_recv_updateLI)\n", (int) seq_temp));
                                /* Remove oldest interval */
                                li_elm = TAILQ_LAST(&(cb->li_hist), li_hist_head);
                                TAILQ_REMOVE(&(cb->li_hist), li_elm, linfo);

                                /* Create the newest interval */
                                li_elm->seq = seq_loss;
                                li_elm->win_count = win_loss;

                                /* insert it into history */
                                TAILQ_INSERT_HEAD(&(cb->li_hist), li_elm, linfo);
                        } else
                                TFRC_DEBUG((LOG_INFO, "TFRC - Loss belongs to previous loss event (tfrc_recv_updateLI)!\n"));
                }
        }
        if (TAILQ_FIRST(&(cb->li_hist)) != NULL) {
                /* calculate interval to last loss event */
                num_later = 1;
                TFRC_RECV_FINDDATAPACKET(cb, elm, num_later);

                seq_temp = ((long) (elm->seq)) -
                    ((long) ((TAILQ_FIRST(&(cb->li_hist)))->seq));
                if (seq_temp < 0)
                        seq_temp = seq_temp + DCCP_SEQ_NUM_LIMIT;

                (TAILQ_FIRST(&(cb->li_hist)))->interval = seq_temp;
                if (debug_info > 0) {
                        TFRC_DEBUG((LOG_INFO, "TFRC - Highest data packet received %llu (tfrc_recv_updateLI)\n", elm->seq));
                }
        }
}


/* Functions declared in struct dccp_cc_sw */
/* Initialises the receiver side
 * returns: pointer to a tfrc_recv_ccb struct on success, otherwise 0
 * Tested u:OK
 */
void *
tfrc_recv_init(struct dccpcb * pcb)
{
        struct tfrc_recv_ccb *ccb;

        ccb = malloc(sizeof(struct tfrc_recv_ccb), M_PCB, M_NOWAIT | M_ZERO);
        if (ccb == 0) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Unable to allocate memory for tfrc_recv_ccb!\n"));
                return 0;
        }
        /* init recv here */

        mutex_init(&(ccb->mutex), MUTEX_DEFAULT, IPL_SOFTNET);

        ccb->pcb = pcb;

        if (ccb->pcb->avgpsize >= TFRC_MIN_PACKET_SIZE && ccb->pcb->avgpsize <= TFRC_MAX_PACKET_SIZE)
                ccb->s = (u_int16_t) ccb->pcb->avgpsize;
        else
                ccb->s = TFRC_STD_PACKET_SIZE;

        TFRC_DEBUG((LOG_INFO, "TFRC - Receiver is using packet size %u\n", ccb->s));

        /* init packet history */
        TAILQ_INIT(&(ccb->hist));

        /* init loss interval history */
        TAILQ_INIT(&(ccb->li_hist));

        ccb->state = TFRC_RSTATE_NO_DATA;
        TFRC_DEBUG((LOG_INFO, "TFRC receiver initialised!\n"));
        dccpstat.tfrcs_recv_conn++;
        return ccb;
}
/* Free the receiver side
 * args: ccb - ccb of receiver
 * Tested u:OK
 */
void
tfrc_recv_free(void *ccb)
{
        struct r_hist_entry *elm, *elm2;
        struct li_hist_entry *li_elm, *li_elm2;
        struct tfrc_recv_ccb *cb = (struct tfrc_recv_ccb *) ccb;

        if (ccb == 0)
                panic("TFRC - Receiver ccb is null! (free)");

        /* uninit recv here */

        cb->state = TFRC_RSTATE_TERM;
        /* get mutex */
        mutex_enter(&(cb->mutex));

        /* Empty packet history */
        elm = TAILQ_FIRST(&(cb->hist));
        while (elm != NULL) {
                elm2 = TAILQ_NEXT(elm, linfo);
                free(elm, M_TEMP);      /* M_TEMP ?? */
                elm = elm2;
        }
        TAILQ_INIT(&(cb->hist));

        /* Empty loss interval history */
        li_elm = TAILQ_FIRST(&(cb->li_hist));
        while (li_elm != NULL) {
                li_elm2 = TAILQ_NEXT(li_elm, linfo);
                free(li_elm, M_TEMP);   /* M_TEMP ?? */
                li_elm = li_elm2;
        }
        TAILQ_INIT(&(cb->li_hist));

        mutex_exit(&(cb->mutex));
        mutex_destroy(&(cb->mutex));

        free(ccb, M_PCB);

        TFRC_DEBUG((LOG_INFO, "TFRC receiver is destroyed\n"));
}


/*
 * Tell TFRC that a packet has been received
 * args: ccb  -  ccb block for current connection
 */
void
tfrc_recv_packet_recv(void *ccb, char *options, int optlen)
{
        struct r_hist_entry *packet;
        u_int8_t win_count = 0;
        struct fixpoint p_prev;
        int ins = 0;
        struct tfrc_recv_ccb *cb = (struct tfrc_recv_ccb *) ccb;

#ifdef NOTFRCRECV
        return;
#endif

        if (!(cb->state == TFRC_RSTATE_NO_DATA || cb->state == TFRC_RSTATE_DATA)) {
                panic("TFRC - Illegal state! (tfrc_recv_packet_recv)\n");
                return;
        }
        /* Check which type */
        switch (cb->pcb->type_rcv) {
        case DCCP_TYPE_ACK:
                if (cb->state == TFRC_RSTATE_NO_DATA)
                        return;
                break;
        case DCCP_TYPE_DATA:
        case DCCP_TYPE_DATAACK:
                break;
        default:
                TFRC_DEBUG((LOG_INFO, "TFRC - Received not data/dataack/ack packet! (tfrc_recv_packet_recv)"));
                return;
        }

        mutex_enter(&(cb->mutex));

        /* Add packet to history */

        packet = malloc(sizeof(struct r_hist_entry), M_TEMP, M_NOWAIT); /* M_TEMP?? */
        if (packet == NULL) {
                TFRC_DEBUG((LOG_INFO, "TFRC - Not enough memory to add received packet to history (consider it lost)! (tfrc_recv_packet_recv)"));
                dccpstat.tfrcs_recv_nomem++;
                goto rp_release;
        }
        microtime(&(packet->t_recv));
        packet->seq = cb->pcb->seq_rcv;
        packet->type = cb->pcb->type_rcv;
        packet->ndp = cb->pcb->ndp_rcv;

        /* get window counter */
        win_count = cb->pcb->ccval;
        packet->win_count = win_count;

        ins = tfrc_recv_add_hist(cb, packet);

        /* check if we got a data packet */
        if (cb->pcb->type_rcv != DCCP_TYPE_ACK) {

                switch (cb->state) {
                case TFRC_RSTATE_NO_DATA:
                        TFRC_DEBUG((LOG_INFO, "TFRC - Send an initial feedback packet (tfrc_recv_packet_recv)\n"));
                        tfrc_recv_send_feedback(cb);
                        cb->state = TFRC_RSTATE_DATA;
                        break;
                case TFRC_RSTATE_DATA:
                        cb->bytes_recv = cb->bytes_recv + cb->pcb->len_rcv;
                        if (!ins) {
                                /* find loss event */
                                tfrc_recv_detectLoss(cb);
                                p_prev.num = cb->p.num;
                                p_prev.denom = cb->p.denom;

                                /* Calculate loss event rate */
                                if (!TAILQ_EMPTY(&(cb->li_hist))) {
                                        cb->p.num = 1;
                                        cb->p.denom = tfrc_calclmean(cb);
                                }
                                /* check send conditions then send */

                                if (fixpoint_cmp(&(cb)->p, &p_prev) > 0) {
                                        TFRC_DEBUG((LOG_INFO, "TFRC - Send a feedback packet because p>p_prev (tfrc_recv_packet_recv)\n"));
                                        tfrc_recv_send_feedback(cb);
                                } else {
                                        if ((cb->pcb->seq_rcv > cb->seq_last_counter
                                                && cb->pcb->seq_rcv - cb->seq_last_counter < TFRC_RECV_NEW_SEQ_RANGE) ||
                                            (cb->pcb->seq_rcv < cb->seq_last_counter
                                                && cb->seq_last_counter - cb->pcb->seq_rcv > DCCP_SEQ_NUM_LIMIT - TFRC_RECV_NEW_SEQ_RANGE)) {

                                                /* the sequence number is
                                                 * newer than seq_last_count */
                                                if ((win_count > cb->last_counter
                                                        && win_count - cb->last_counter > TFRC_WIN_COUNT_PER_RTT) ||
                                                    (win_count < cb->last_counter
                                                        && cb->last_counter - win_count < TFRC_WIN_COUNT_LIMIT - TFRC_WIN_COUNT_PER_RTT)) {

                                                        TFRC_DEBUG((LOG_INFO, "TFRC - Send a feedback packet (%i)(win_count larger) (tfrc_recv_packet_recv)\n", (win_count - cb->last_counter + TFRC_WIN_COUNT_LIMIT) % TFRC_WIN_COUNT_LIMIT));

                                                        tfrc_recv_send_feedback(cb);
                                                }
                                        }       /* end newer seqnum */
                                }       /* end p > p_prev */

                        }
                        break;
                default:
                        panic("tfrc_recv_packet_recv: Illegal state!");
                        break;
                }

        }                       /* end if not pure ack */
rp_release:
        mutex_exit(&(cb->mutex));
}


/*
 * fixpoint routines
 */
static void
normalize(long long *num, long long *denom)
{
        static const int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 0 };
        int i;

        if (!*denom) return;
        if (*denom < 0) {
                *num *= (-1);
                *denom *= (-1);
        }

        if (*num % *denom == 0) {
                *num /= *denom;
                *denom = 1;
        }
        for (i = 0; prime[i]; i++)
                while (*num % prime[i] == 0 && *denom % prime[i] == 0) {
                        *num /= prime[i];
                        *denom /= prime[i];
                }
}

struct fixpoint *
fixpoint_add(struct fixpoint *x, const struct fixpoint *a,
             const struct fixpoint *b)
{
        long long num, denom;

        num = a->num * b->denom + a->denom * b->num;
        denom = a->denom * b->denom;
        normalize(&num, &denom);

        x->num = num;
        x->denom = denom;
        return (x);
}

struct fixpoint *
fixpoint_sub(struct fixpoint *x, const struct fixpoint *a,
             const struct fixpoint *b)
{
        long long num, denom;

        if (!a->denom) {
                x->num = -1 * b->num;
                x->denom = -1 * b->denom;
                return (x);
        }               
        if (!b->denom) {
                x->num = a->num;
                x->denom = a->denom;
                return (x);
        }               
        num = a->num * b->denom - a->denom * b->num;
        denom = a->denom * b->denom;
        normalize(&num, &denom);

        x->num = num;
        x->denom = denom;
        return (x);
}

int
fixpoint_cmp(const struct fixpoint *a, const struct fixpoint *b)
{
        struct fixpoint x;

        fixpoint_sub(&x, a, b);
        if (x.num > 0)
                return (1);
        else if (x.num < 0)
                return (-1);
        else
                return (0);
}

struct fixpoint *
fixpoint_mul(struct fixpoint *x, const struct fixpoint *a,
             const struct fixpoint *b)
{
        long long num, denom;

        num = a->num * b->num;
        denom = a->denom * b->denom;
        normalize(&num, &denom);

        x->num = num;
        x->denom = denom;
        return (x);
}

struct fixpoint *
fixpoint_div(struct fixpoint *x, const struct fixpoint *a,
             const struct fixpoint *b)
{
        long long num, denom;

        num = a->num * b->denom;
        denom = a->denom * b->num;
        normalize(&num, &denom);

        x->num = num;
        x->denom = denom;
        return (x);
}

long
fixpoint_getlong(const struct fixpoint *x)
{

        if (x->denom == 0)
                return (0);
        return (x->num / x->denom);
}

const struct fixpoint flargex = { 2LL, 1000LL };
const struct fixpoint fsmallx = { 1LL, 100000LL };
const struct fixpoint fsmallstep = { 4LL, 1000000LL };

/*
 * FLOOKUP macro. NOTE! 0<=(int x)<=1 
 * Tested u:OK
 */
const struct fixpoint *
flookup(const struct fixpoint *x)
{
        static const struct fixpoint y = { 250000, 1 };
        struct fixpoint z;
        int i;

        if (fixpoint_cmp(x, &flargex) >= 0) {
                if (x->num == 0)
                        return NULL;
                i = x->denom / x->num;
#ifdef TFRCDEBUG
                if (i >= sizeof(flarge_table) / sizeof(flarge_table[0]))
                        panic("flarge_table lookup failed");
#endif

                return &flarge_table[i];
        } else {
                fixpoint_mul(&z, x, &y);
                if (z.num == 0)
                        return NULL;
                i = fixpoint_getlong(&z);
#ifdef TFRCDEBUG
                if (i >= sizeof(fsmall_table) / sizeof(fsmall_table[0]))
                        panic("fsmall_table lookup failed");
#endif

                return &fsmall_table[i];
        }
}

/*
 * Inverse of the FLOOKUP above
 * args: fvalue - function value to match
 * returns:  p  closest to that value
 * Tested u:OK
 */
const struct fixpoint *
tfrc_flookup_reverse(const struct fixpoint *fvalue)
{
        static struct fixpoint x;
        int ctr;

        if (fixpoint_cmp(fvalue, &flarge_table[1]) >= 0) {
                /* 1.0 */
                x.num = 1;
                x.denom = 1;
                return &x;
        } else if (fixpoint_cmp(fvalue, &flarge_table[sizeof(flarge_table) /
            sizeof(flarge_table[0]) - 1]) >= 0) {
                ctr = sizeof(flarge_table) / sizeof(flarge_table[0]) - 1;
                while (ctr > 1 && fixpoint_cmp(fvalue, &flarge_table[ctr]) >= 0)
                        ctr--;

                /* round to smallest */
                ctr = ctr + 1;
    
                /* round to nearest */
                return &flarge_table[ctr];
        } else if (fixpoint_cmp(fvalue, &fsmall_table[0]) >= 0) {
                ctr = 0;
                while (ctr < sizeof(fsmall_table) / sizeof(fsmall_table[0]) &&
                    fixpoint_cmp(fvalue, &fsmall_table[ctr]) > 0)
                        ctr++;
                x = fsmallstep;
                x.num *= ctr;
                return &x;
        }
        return &fsmallstep;
}