/* $Id: mcl_sched.cpp,v 1.2 2003/10/27 09:55:48 roca Exp $ */
/*
 *  Copyright (c) 1999-2003 INRIA - Universite Paris 6 - All rights reserved
 *  (main author: Vincent Roca - vincent.roca@inrialpes.fr)
 *
 *  This program is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU General Public License
 *  as published by the Free Software Foundation; either version 2
 *  of the License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
 *  USA.
 */

/*
 *	Transmission plannification for each new ADU.
 */

#include "mcl_includes.h"


/*
 * Create the sending tx planning after receiving a new ADU.
 * Called by the sending function of the lib.
 * NB: not implemented with processing speed in mind!
 */


#ifdef LCT_SCHED1
static void LCT1_UpdateTxPlanning	(mclcb_t *mclcb, adu_t *adu_start,
					adu_t *adu_end);
#endif
#ifdef LCT_SCHED2
static void LCT2_UpdateTxPlanning	(mclcb_t *mclcb, adu_t *adu_start,
					adu_t *adu_end);
#endif
#ifdef LCT_SCHED3
static void LCT3_UpdateTxPlanning	(mclcb_t *mclcb, adu_t *adu_start,
					adu_t *adu_end);
#endif


/*
 * scheduler switching table
 */
typedef void (*UpdateTxPlanning_func) (mclcb_t *mclcb, adu_t *adu_start, adu_t *adu_end);
static UpdateTxPlanning_func	sched_tab[MCL_SCHED_NB];


/****** LCT scheduling common functions ***************************************/


/*
 * switch according to the scheduler in use
 */
void UpdateTxPlanning (mclcb_t	*mclcb,
		       adu_t	*adu_start,
		       adu_t	*adu_end)
{
	static int	initialized = 0;

	ASSERT(adu_start && adu_end);
	if (!initialized) {
#ifdef LCT_SCHED1
		sched_tab[MCL_SCHED_LCT1] = LCT1_UpdateTxPlanning;
#endif
#ifdef LCT_SCHED2
		sched_tab[MCL_SCHED_LCT2] = LCT2_UpdateTxPlanning;
#endif
#ifdef LCT_SCHED3
		sched_tab[MCL_SCHED_LCT3] = LCT3_UpdateTxPlanning;
#endif
		initialized = 1;
	}
	ASSERT(sched_tab[mclcb->scheduler]);
	sched_tab[mclcb->scheduler](mclcb, adu_start, adu_end);
}


/*
 * Create a random permutation of (1..n)
 * (see: http://www.cs.berkeley.edu/~jfc/cs174/lecs/lec2.html)
 * Returns a table containing the random permutation.
 * WARNING: it is the caller's responsibility to free
 *	this array.
 */
#define mcl_random_permut(a,n)	mcl_pseudorandom_permut((a),(n),1)

/*
 * create a partially random permutation of (1..n)
 */
static void
mcl_pseudorandom_permut (int	*a,	/* input/output array */
			 int	n,	/* number of elements in array */
			 int	l)	/* permut one elt out of l */
{
	int	i, j, temp;

	ASSERT(l <= n);
	for (i = 0; i < n; i++)
		a[i] = i;
	for (i = 0; i < n; i+=l) {	/* skip some indexes */
		j = random() % n;
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}


/****** LCT scheduling version 1 **********************************************/
#if defined(LCT_SCHED1)		/* { */


/*
 * struct used to identify ADUs given a DU index
 */
typedef struct {
	adu_t	*adu;			/* for this ADU */
	int	first_idx;		/* DUs start at this (flat) index... */
	int	last_idx;		/* ... up to this one */
	int	du_nb;			/* total nb of data DUs in all blocks */
	/* fields required by LCT_SCHED2 */
	int	nb_fec_layers;		/* nb of FEC layers in LCT_SCHED2 */
} idx_range_t;


/* binary search more efficient with sessions having very large number of ADU */
#define BIN_SEARCH

#ifdef BIN_SEARCH
/*
 * binary tree search version...
 * usefull in case of very large ADU sessions
 */
static int
mcl_flat_index_to_adu_bsearch (idx_range_t	*idx_range_tab,
				int		low,  /* low index, included */
				int		high, /* high index, included */
				int		index)
{
	int	mid;	/* mid index */
	ASSERT(low <= high);
	/*if (low == high) { return low; }*/
	mid = ((low + high) >> 1);
	if (index <= idx_range_tab[mid].last_idx) {
		if (index >= idx_range_tab[mid].first_idx)
			return mid;	/* found */
		return mcl_flat_index_to_adu_bsearch(idx_range_tab, low, mid,
						     index);
	} else {
		return mcl_flat_index_to_adu_bsearch(idx_range_tab, mid+1, high,
						     index);
	}
}


/*
 * retrieve the idx_range_t struct of the adu corresponding to the flat
 * index given.
 */
#ifdef DEBUG
static idx_range_t*
mcl_flat_index_to_adu (mclcb_t		*mclcb,
		       idx_range_t	*idx_range_tab,
		       int		nb_entries,
		       int		index)
{
	int	idx;
	TRACELVL(5, (mcl_stdout, "-> mcl_flat_index_to_adu: index=%d\n", index))
	ASSERT(index >= 0 && index <= idx_range_tab[nb_entries-1].last_idx);
	idx = mcl_flat_index_to_adu_bsearch (idx_range_tab, 0,
					     nb_entries-1, index);
	TRACELVL(5, (mcl_stdout, "<- mcl_flat_index_to_adu: adu=x%x\n",
		(int)idx_range_tab[idx].adu))
	return &(idx_range_tab[idx]);
}
#else  /* DEBUG */
#define mcl_flat_index_to_adu(mclcb,idx_range_tab,nb_entries,index)	\
	&(idx_range_tab[mcl_flat_index_to_adu_bsearch(idx_range_tab, 0,	\
						      (nb_entries)-1, (index))])
#endif /* DEBUG */


#else  /* BIN_SEARCH */


/*
 * retrieve the idx_range_t struct of the adu corresponding to the flat
 * index given.
 */
static idx_range_t*
mcl_flat_index_to_adu (mclcb_t		*mclcb,
		       idx_range_t	*idx_range,
		       int		nb_entries,
		       int		index)
{
	/*TRACELVL(5, (mcl_stdout, "-> mcl_flat_index_to_adu: index=%d\n", index))*/
	ASSERT(index >= 0);
	while (1) {
		ASSERT(idx_range->adu != NULL);
		if (index <= idx_range->last_idx &&	/* more efficient */
		    index >= idx_range->first_idx) {	/* in this order! */
			/* found */
			TRACELVL(5, (mcl_stdout, "   mcl_flat_index_to_adu: idx=%d, adu=x%x\n",
				index, (int)idx_range->adu));
			return idx_range;
		}
		idx_range++;
	}
	ASSERT(0);	/* unreachable */
	return NULL;
}


#endif /* BIN_SEARCH */


static int	LCT1_mcl_get_tot_nb_of_du	(mclcb_t *mclcb, adu_t *adu);
static du_t*	LCT1_mcl_flat_index_to_du	(mclcb_t *mclcb, adu_t *adu, int index);


/*
 * Send everything on each layer.
 * Currently uses a straightforward algorithm: all the DUs are sent
 * on all the layers using a random permutation
 */
void
LCT1_UpdateTxPlanning (mclcb_t	*mclcb,
		  adu_t		*adu_start,	/* first ADU (included) */
		  adu_t		*adu_end)	/* last ADU (included) */
{
	int	i;		/* */
	int	j;		/* flat index in random permutation array */
	int	lay;		/* layer nb */
	txlvl_t	*tl;
	int	*permut;	/* random permutation array */
	int	adu_nb;		/* number of ADUs */
	adu_t	*adu;
	int	du_nb;		/* number of DUs */
	int	tot_du_nb;	/* total DU nb (incl. FEC) for all blks, all ADUs */
	du_t	*du;
	idx_range_t *idx_range;	/* table */

	TRACELVL(5, (mcl_stdout, "-> LCT1_UpdateTxPlanning:\n"))
	if (adu_start == adu_end) {
		/* the easy traditional case: only one adu */
		/*
		 * tot_du_nb includes both plain DUs and FEC DUs of all blocks
		 */
		TRACELVL(5, (mcl_stdout, "   LCT1_UpdateTxPlanning: LCT org1/sequential object order\n"))
		adu = adu_start;
		tot_du_nb = LCT1_mcl_get_tot_nb_of_du(mclcb, adu);
		if (!(permut = (int*)malloc(tot_du_nb * sizeof(int)))) {
			goto no_memory;
		}
		/*
		 * for each layer, create a random permutation of all the DUs
		 * and register them
		 */
		for (lay = 0, tl = mclcb->txlvl_tab; lay < mclcb->max_level;
		     lay++, tl++) {
			mcl_random_permut(permut, tot_du_nb);
			ASSERT(permut);
			for (j = 0; j < tot_du_nb; j++) {
				du = LCT1_mcl_flat_index_to_du(mclcb, adu, permut[j]);
				ASSERT(du);
#ifdef VIRTUAL_TX_MEM
				du->vtm_info.du_in_seq_in_txtab = 1;
#endif
				mcl_register_du(mclcb, tl, du, mclcb->nb_tx);
			}
		}
	} else if (mclcb->adu_scheduling == MCL_SCHED_RANDOM_OBJ_ORDER) {
		/* a bit more complex: list of adus */
		/*
		 * send ADUs in a different random order on each layer
		 */
		int		*permut2;	/* random DU permutation array*/
		idx_range_t	*ir;		/* table */
		int		max_du_nb;	/* max number of DUs in ADUs */

		TRACELVL(5, (mcl_stdout, "   LCT1_UpdateTxPlanning: LCT org1/random obj order\n"))
		adu_nb = adu_end->seq - adu_start->seq + 1;
		if (!(permut = (int*)malloc(adu_nb * sizeof(int))) ||
		    !(idx_range = (idx_range_t *)malloc(adu_nb * sizeof(idx_range_t)))) {
			goto no_memory;
		}
		max_du_nb = -1;
		for (i = 0, adu = adu_start, ir = idx_range;
		     i < adu_nb;
		     i++, adu = adu->next, ir++) {
			ir->du_nb = LCT1_mcl_get_tot_nb_of_du(mclcb, adu);
			if (ir->du_nb > max_du_nb)
				max_du_nb = ir->du_nb;
			ir->adu = adu;
			ir->first_idx = 0; /* register adu id only */
			ir->last_idx = 0;  /* register adu id only */
		}
		/* allocate this tab only once */
		if (!(permut2 = (int*)malloc(max_du_nb * sizeof(int)))) {
			goto no_memory;
		}
		/*
		 * for each layer, create a random permutation of all the ADUs
		 * and then a random permutation of all the DUs for each ADU.
		 */
		for (lay = 0, tl = mclcb->txlvl_tab; lay < mclcb->max_level;
		     lay++, tl++) {
			mcl_random_permut(permut, adu_nb);
			for (i = 0; i < adu_nb; i++) {
				adu = idx_range[permut[i]].adu;
				du_nb = idx_range[permut[i]].du_nb;
				mcl_random_permut(permut2, du_nb);
				for (j = 0; j < du_nb; j++) {
					du = LCT1_mcl_flat_index_to_du(mclcb,
							adu, permut2[j]);
					ASSERT(du);
#ifdef VIRTUAL_TX_MEM
					du->vtm_info.du_in_seq_in_txtab = 1;
#endif
					mcl_register_du(mclcb, tl, du, mclcb->nb_tx);
				}
			}
		}
	} else {
		/* a bit more complex: list of adus */
		/*
		 * mix everything: all the DUs of all the ADUs are sent
		 * on all the layers using a random permutation
		 */
		/*
		 * how many DUs per ADU; remember it for future index->du access
		 */
		idx_range_t	*idx_entry;
		int		idx;		/* index */

		TRACELVL(5, (mcl_stdout, "   LCT1_UpdateTxPlanning: LCT org1/mixed order\n"))
		adu_nb = adu_end->seq - adu_start->seq + 1;
		if (!(idx_range = (idx_range_t *)malloc(adu_nb * sizeof(idx_range_t)))) {
			goto no_memory;
		}
		tot_du_nb = 0;
		for (i = 0, adu = adu_start; i < adu_nb; i++, adu = adu->next) {
			du_nb = LCT1_mcl_get_tot_nb_of_du(mclcb, adu);
			idx_range[i].adu = adu;
			idx_range[i].first_idx = tot_du_nb;
			tot_du_nb += du_nb;
			idx_range[i].last_idx = tot_du_nb - 1;
		}
		if (!(permut = (int*)malloc(tot_du_nb * sizeof(int)))) {
			goto no_memory;
		}
		/*
		 * for each layer, create a random permutation of all the DUs
		 * and register them
		 */
		for (lay = 0, tl = mclcb->txlvl_tab; lay < mclcb->max_level;
		     lay++, tl++) {
			/*mcl_random_permut(permut, tot_du_nb);*/
			if (mclcb->adu_scheduling == MCL_SCHED_MIXED_ORDER) {
				mcl_random_permut(permut, tot_du_nb);
			} else if (mclcb->adu_scheduling == MCL_SCHED_PARTIALLY_MIXED_ORDER) {
				/*
				 * if you want you can change the spacing parameter
				 * to modify the probability for a DU not to be
				 * permutted. The higher the value, the less random!
				 */
				mcl_pseudorandom_permut(permut, tot_du_nb, 2);
			} else {
				PRINT_ERR((mcl_stderr, "LCT1_UpdateTxPlanning: ERROR, ADU scheduler %d not possible in LCT1\n", mclcb->adu_scheduling))
				mcl_exit(-1);
			}
			ASSERT(permut);
			for (j = 0; j < tot_du_nb; j++) {
				idx_entry = mcl_flat_index_to_adu(mclcb,
						idx_range, adu_nb, permut[j]);
				adu = idx_entry->adu;
				idx = permut[j] - idx_entry->first_idx;
				ASSERT(idx >= 0);
				ASSERT(adu);
				du = LCT1_mcl_flat_index_to_du(mclcb, adu, idx);
				ASSERT(du);
#ifdef VIRTUAL_TX_MEM
				du->vtm_info.du_in_seq_in_txtab = 1;
#endif
				mcl_register_du(mclcb, tl, du, mclcb->nb_tx);
			}
		}
		free(idx_range);
	}
	free(permut);
	TRACELVL(5, (mcl_stdout, "<- LCT1_UpdateTxPlanning:\n"))
	return;

no_memory:
	PRINT_ERR((mcl_stderr, "LCT1_UpdateTxPlanning: ERROR, no memory"))
	mcl_exit(-1);
}


static int
LCT1_mcl_get_tot_nb_of_du (mclcb_t	*mclcb,
		      adu_t	*adu)
{
	int	i;
	block_t	*blk;
	int	nb = 0;

	/*TRACELVL(5, (mcl_stdout, "-> LCT1_mcl_get_tot_nb_of_du:\n"))*/
	for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++) {
		nb += blk->k;
#ifdef FEC
		nb += blk->fec_du_nb_in_list;
#endif
	}
	TRACELVL(5, (mcl_stdout, "   LCT1_mcl_get_tot_nb_of_du: %d du\n", nb))
	return nb;
}


/*
 * retrieve the du corresponding to the (flat) index given.
 */
static du_t*
LCT1_mcl_flat_index_to_du (mclcb_t	*mclcb,
			   adu_t	*adu,
			   int		index)
{
	int	i;
	block_t	*blk;

	/*TRACELVL(5, (mcl_stdout, "-> LCT1_mcl_flat_index_to_du: index=%d\n", index))*/
	ASSERT(index >= 0);
	ASSERT(index < LCT1_mcl_get_tot_nb_of_du(mclcb, adu));
	for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++) {
		if (index < (int)blk->k) {
			TRACELVL(5, (mcl_stdout, "   LCT1_mcl_flat_index_to_du: idx=%d, du=x%x\n",
				index, (int)&(blk->du_head[index])))
			return &(blk->du_head[index]);
		}
		index -= blk->k;
#ifdef FEC
		if (index < (int)blk->fec_du_nb_in_list) {
			TRACELVL(5, (mcl_stdout, "   LCT1_mcl_flat_index_to_du: fec idx=%d, du=x%x\n",
				index, (int)&(blk->du_head[index])))
			return &(blk->fec_du_head[index]);
		}
		index -= blk->fec_du_nb_in_list;
#endif
	}
	ASSERT(0);	/* unreachable */
	return NULL;
}


#endif /* } */


/****** LCT scheduling version 2 **********************************************/
#if defined(LCT_SCHED2)	/* { */


static int	LCT2_mcl_get_tot_nb_of_data_du	(mclcb_t *mclcb, adu_t *adu);
static int	LCT2_init_fi2du			(mclcb_t *mclcb, int lay,
						adu_t *adu, du_t **fi2du,
						int fi_base);

/*
 * Transmit original DUs on layer 0, FEC DUs of order 1 on layer 1,
 * FEC DUs of order 2 on layer 2, etc.
 * Requires the use of Reed-Solomon FEC code and a small block size
 * to enable the creation of a high number of FEC DUs.
 * Called with a list of adus (possibly only one)
 *
 * example: 3 FEC layers, each with k FEC DUs, 7 layers
 *
 * L6	fec	2k..3k-1  blk->fec_du_head[k+index]	eq_layer=2
 * L5	fec	k..2k-1	  blk->fec_du_head[index]	eq_layer=1
 * L4	data	0..k-1	  blk->du_head[index]		eq_layer=0
 * L3	fec	3k..4k-1  blk->fec_du_head[2k+index]	eq_layer=3
 * L2	fec	2k..3k-1  blk->fec_du_head[k+index]	eq_layer=2
 * L1	fec	k..2k-1	  blk->fec_du_head[index]	eq_layer=1
 * L0	data	0..k-1	  blk->du_head[index]		eq_layer=0
 *
 * Use: - a virtual flat index (fi) table, fi_permut, of size tot_du_nb.
 * 	  This table is randomized with the mcl_random_permut() function.
 *	- a fi2du table, of size tot_du_nb, containing a prt to the DU.
 *	  Used by the fi->DU mapping.
 * 
 * 	fi2du [fi_permut[index]]  --> du to register in txtab
 */
void
LCT2_UpdateTxPlanning (mclcb_t	*mclcb,
		  adu_t		*adu_start,	/* first ADU (included) */
		  adu_t		*adu_end)	/* last ADU (included) */
{
	int	lay;		/* layer */
	int	eq_lay;		/* equivalent layer in first cycle */
	int	nb_lay_in_cycle;
	int	i;
	int	fi;		/* flat index in random permutation array */
	txlvl_t	*tl;
	int	*fi_permut;	/* random permutation array of flat indexes */
	du_t	**fi2du;	/* for a layer gives flat_index->du mapping */
	du_t	**fi2du_lay[MAX_TX_LEVEL]; /* ptr to fi2du tab for each layer */
	du_t	*du;
	adu_t	*adu;
	int	adu_nb;		/* number of ADUs */
	int	tot_du_nb;	/* total data DUs nb for all blks of all ADUs */

#ifndef FEC
	bug, FEC must be defined with LCT_SCHED2!
#endif /* !FEC */
#ifdef DEBUG
	TRACELVL(5, (mcl_stdout, "-> LCT2_UpdateTxPlanning:\n"))
	if (adu_start == adu_end) {
		TRACELVL(5, (mcl_stdout, "   LCT2_UpdateTxPlanning: LCT org2/seqential ADU order\n"))
	 } else if (mclcb->adu_scheduling == MCL_SCHED_PARTIALLY_MIXED_ORDER) {
		TRACELVL(5, (mcl_stdout, "   LCT2_UpdateTxPlanning: LCT org2/partially random order\n"))
	} else if (mclcb->adu_scheduling == MCL_SCHED_MIXED_ORDER) {
		TRACELVL(5, (mcl_stdout, "   LCT2_UpdateTxPlanning: LCT org2/random order\n"))
	}
#endif /* DEBUG */
	adu_nb = adu_end->seq - adu_start->seq + 1;
	tot_du_nb = 0;
	for (i = adu_nb, adu = adu_start; i > 0; i--, adu = adu->next) {
		tot_du_nb += LCT2_mcl_get_tot_nb_of_data_du(mclcb, adu);
	}
	nb_lay_in_cycle = 1 + mcl_get_nb_fec_layers(mclcb,
						    adu->block_head->k);
	if (!(fi_permut = (int*)malloc(tot_du_nb * sizeof(int)))) {
		PRINT_ERR((mcl_stderr, "LCT2_UpdateTxPlanning: ERROR, no memory\n"))
		mcl_exit(-1);
	}
	for (lay = 0, tl = mclcb->txlvl_tab; lay < mclcb->max_level;
	     lay++, tl++) {
		/*
		 * allocate and initialize the fi2du table
		 */
		if (lay < nb_lay_in_cycle) {
			/* for the 1st cycle, create the fi2du table */
			eq_lay = lay;
			if (!(fi2du = (du_t **)malloc(tot_du_nb * sizeof(du_t *)))) {
				PRINT_ERR((mcl_stderr, "LCT2_UpdateTxPlanning: ERROR, no memory\n"))
				mcl_exit(-1);
			}
			/* initialize the fi2du table for all ADUs */
			for (i = adu_nb, adu = adu_start, fi = 0; i > 0;
			     i--, adu = adu->next) {
				fi += LCT2_init_fi2du(mclcb, lay, adu, fi2du, fi);
			}
			fi2du_lay[lay] = fi2du;	/* remember */
		} else {
			/* for extra cycles, point to equiv fi2du of cycle 1 */
			eq_lay = lay % nb_lay_in_cycle;
			fi2du = fi2du_lay[eq_lay];
		}
		/*
		 * then create a random permutation of all the DUs
		 */
		ASSERT(mclcb->adu_scheduling == MCL_SCHED_MIXED_ORDER ||
		       mclcb->adu_scheduling == MCL_SCHED_PARTIALLY_MIXED_ORDER);
		if (mclcb->adu_scheduling == MCL_SCHED_MIXED_ORDER) {
			mcl_random_permut(fi_permut, tot_du_nb);
		} else {
			/*
			 * if you want you can change the spacing parameter
			 * to modify the probability for a DU not to be
			 * permutted. The higher the value, the less random!
			 */
			mcl_pseudorandom_permut(fi_permut, tot_du_nb, 2);
		}
		for (fi = 0; fi < tot_du_nb; fi++) {
			du = fi2du[fi_permut[fi]];
			ASSERT(du);
#ifdef VIRTUAL_TX_MEM
			du->vtm_info.du_in_seq_in_txtab = 1;
#endif
			mcl_register_du(mclcb, tl, du, mclcb->nb_tx);
		}
	}
	for (lay = 0; lay < nb_lay_in_cycle; lay++) {
		free(fi2du_lay[lay]);
	}
	free(fi_permut);
	TRACELVL(5, (mcl_stdout, "<- LCT2_UpdateTxPlanning:\n"))
}


/*
 * returns the total number of data du in this adu
 */
static int
LCT2_mcl_get_tot_nb_of_data_du (mclcb_t	*mclcb,
				adu_t	*adu)
{
	int	i;
	block_t	*blk;
	int	nb = 0;

	/*TRACELVL(5, (mcl_stdout, "-> LCT2_mcl_get_tot_nb_of_data_du:\n"))*/
	for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++)
		nb += blk->k;
	/*TRACELVL(5, (mcl_stdout, "<- LCT2_mcl_get_tot_nb_of_data_du: %d du\n", nb))*/
	return nb;
}


/*
 * initializes the fi2du table for this layer with a ptr to the data/FEC DU.
 * the layer necessarily belongs to the first cycle!
 * returns the number of du stored
 */
static int
LCT2_init_fi2du (mclcb_t	*mclcb,
		 int		lay,
		 adu_t		*adu,
		 du_t		**fi2du,
		 int		fi_base)	/* fi of 1st du of this adu */
{
	u_int	i;		/* block index in adu */
	u_int	j;		/* du index in block */
	int	fi;		/* flat index */
	int	j_off;		/* offset in du index with FEC layers */
	block_t	*blk;

	TRACELVL(5, (mcl_stdout, "-> LCT2_init_fi2du:\n"))
	fi = fi_base;
	if (lay == 0) {
		/*
		 * we are on a data layer, so search DU
		 * in du_head[]
		 */
		for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++) {
			for (j = 0; j < blk->k; j++, fi++) { 
				fi2du[fi] = &(blk->du_head[j]);
			}
		}
	} else {
		/*
		 * we are on a FEC layer, so search DU
		 * in fec_du_head[]
		 */
		for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++) {
			j_off = (lay - 1) * blk->k;
			for (j = 0; j < blk->k; j++, fi++) { 
				fi2du[fi] = &(blk->fec_du_head[j_off + j]);
			}
		}
	}
	TRACELVL(5, (mcl_stdout, "<- LCT2_init_fi2du: %d du stored\n", fi - fi_base))
	return(fi - fi_base);
}


#endif /* } */


/****** LCT scheduling version 3, or Disk-Aware Scheduling ********************/
#if defined(LCT_SCHED3)	/* { */


/*
 * In Sequence Data Unit struct
 * identifies a sequence of DUs that are stored sequentially on the disk
 */
typedef struct {
	du_t	*du;		/* 1st DU of the ISDU sequence */
	int	du_nb;		/* number of elements in the ISDU sequence */
} isdu_t;


static int	LCT3_mcl_get_tot_nb_of_data_du	(mclcb_t *mclcb, adu_t *adu);
static int	LCT3_init_fi2isdu		(mclcb_t *mclcb, int lay,
						adu_t *adu, isdu_t *fi2isdu,
						int *est_du_nb, int fi_base);

/*
 * Same as LCT2 but taking into account disk limitations.
 *
 * Transmit original DUs on layer 0, FEC DUs of order 1 on layer 1,
 * FEC DUs of order 2 on layer 2, etc.
 * Requires the use of Reed-Solomon FEC code and a small block size
 * to enable the creation of a high number of FEC DUs.
 * Called with a list of adus (possibly only one)
 *
 * example: 3 FEC layers, each with k FEC DUs, 7 layers
 *
 * L6	fec	2k..3k-1  blk->fec_du_head[k+index]	eq_layer=2
 * L5	fec	k..2k-1	  blk->fec_du_head[index]	eq_layer=1
 * L4	data	0..k-1	  blk->du_head[index]		eq_layer=0
 * L3	fec	3k..4k-1  blk->fec_du_head[2k+index]	eq_layer=3
 * L2	fec	2k..3k-1  blk->fec_du_head[k+index]	eq_layer=2
 * L1	fec	k..2k-1	  blk->fec_du_head[index]	eq_layer=1
 * L0	data	0..k-1	  blk->du_head[index]		eq_layer=0
 *
 * Use: - a virtual flat index (fi) table, fi_permut, of size tot_isdu_nb.
 * 	  This table is randomized with the mcl_random_permut() function.
 *	- a fi2isdu table, of size tot_isdu_nb, containing a prt to the isDU.
 *	  Used by the fi->ISDU mapping.
 * 
 * 	fi2isdu [fi_permut[index]]  --> sequence of DUs to register in txtab
 */
void
LCT3_UpdateTxPlanning (mclcb_t	*mclcb,
		  adu_t		*adu_start,	/* first ADU (included) */
		  adu_t		*adu_end)	/* last ADU (included) */
{
	int	lay;		/* layer */
	int	eq_lay;		/* equivalent layer in first cycle */
	int	nb_lay_in_cycle;
	int	i;
	int	fi;		/* flat index in random permutation array */
	txlvl_t	*tl;
	int	*fi_permut;	/* random permutation array of flat indexes */
	isdu_t	*fi2isdu;	/* for a layer gives flat_index->isdu (or In */
				/* Sequence DU) mapping */
	isdu_t	*fi2isdu_lay[MAX_TX_LEVEL]; /*ptr to fi2isdu tab for each lay*/
	du_t	*du;
	isdu_t	*isdu;
	adu_t	*adu;
	int	adu_nb;		/* number of ADUs */
	int	tot_du_nb;	/* total data DUs nb for all blks of all ADUs */
	int	tot_isdu_nb;	/* total nb of ISDUs on current layer */
	int	est_isdu_nb;	/* estimated nb of ISDUs on current layer */
	int	tot_isdu_nb_lay[MAX_TX_LEVEL]; /* tab of tot_isdu_nb per layer*/

#ifndef FEC
	bug, FEC must be defined with LCT_SCHED3!
#endif /* !FEC */
#ifdef DEBUG
	TRACELVL(5, (mcl_stdout, "-> LCT3_UpdateTxPlanning:\n"))
	if (adu_start == adu_end) {
		TRACELVL(5, (mcl_stdout, "   LCT3_UpdateTxPlanning: LCT org3/seqential ADU order\n"))
	 } else if (mclcb->adu_scheduling == MCL_SCHED_PARTIALLY_MIXED_ORDER) {
		TRACELVL(5, (mcl_stdout, "   LCT3_UpdateTxPlanning: LCT org3/partially random order\n"))
	} else if (mclcb->adu_scheduling == MCL_SCHED_MIXED_ORDER) {
		TRACELVL(5, (mcl_stdout, "   LCT3_UpdateTxPlanning: LCT org3/random order\n"))
	}
#endif /* DEBUG */
	adu_nb = adu_end->seq - adu_start->seq + 1;
	tot_du_nb = 0;
	for (i = adu_nb, adu = adu_start; i > 0; i--, adu = adu->next) {
		tot_du_nb += LCT3_mcl_get_tot_nb_of_data_du(mclcb, adu);
	}
	nb_lay_in_cycle = 1 + mcl_get_nb_fec_layers(mclcb,
						    adu->block_head->k);
	if (!(fi_permut = (int*)malloc(tot_du_nb * sizeof(int)))) {
		PRINT_ERR((mcl_stderr, "LCT3_UpdateTxPlanning: ERROR, no memory\n"))
		mcl_exit(-1);
	}
	for (lay = 0, tl = mclcb->txlvl_tab; lay < mclcb->max_level;
	     lay++, tl++) {
		/*
		 * allocate and initialize the fi2isdu table
		 */
		if (lay < nb_lay_in_cycle) {
			/*
			 * for the 1st cycle, calculate the number of isdu
			 * and create the fi2isdu table
			 */
			eq_lay = lay;
			/* estimate the nb of isdu */
			// est_isdu_nb = (int)(1.5 * tot_du_nb /
			//		    mclcb->desired_du_in_seq_in_txtab);
			est_isdu_nb = tot_du_nb;	/* the easy way */
			if (!(fi2isdu = (isdu_t *)malloc(est_isdu_nb * sizeof(isdu_t)))) {
				PRINT_ERR((mcl_stderr, "LCT3_UpdateTxPlanning: ERROR, no memory\n"))
				mcl_exit(-1);
			}
			/* initialize the fi2isdu table for all ADUs */
			for (i = adu_nb, adu = adu_start, fi = 0; i > 0;
			     i--, adu = adu->next) {
				fi += LCT3_init_fi2isdu(mclcb, lay, adu, fi2isdu, &est_isdu_nb, fi);
				/* WARNING: LCT3_init_fi2isdu may reallocate */
				/* the fi2isdu buffer and adjust est_isdu_nb */
			}
			fi2isdu_lay[lay] = fi2isdu;	/* remember */
			tot_isdu_nb_lay [eq_lay] = tot_isdu_nb = fi;
			ASSERT(tot_isdu_nb <= tot_du_nb);
		} else {
			/* for extra cycles point to equiv fi2isdu of cycle 1 */
			eq_lay = lay % nb_lay_in_cycle;
			fi2isdu = fi2isdu_lay[eq_lay];
			tot_isdu_nb = tot_isdu_nb_lay[eq_lay];
		}
		/*
		 * then create a random permutation of all the DUs
		 */
		ASSERT(mclcb->adu_scheduling == MCL_SCHED_MIXED_ORDER ||
		       mclcb->adu_scheduling == MCL_SCHED_PARTIALLY_MIXED_ORDER);
		if (mclcb->adu_scheduling == MCL_SCHED_MIXED_ORDER) {
			mcl_random_permut(fi_permut, tot_isdu_nb);
		} else {
			/*
			 * if you want you can change the spacing parameter
			 * to modify the probability for a DU not to be
			 * permutted. The higher the value, the less random
			 * the permutation!
			 */
			mcl_pseudorandom_permut(fi_permut, tot_isdu_nb, 2);
		}
		for (fi = 0; fi < tot_isdu_nb; fi++) {
			isdu = &(fi2isdu[fi_permut[fi]]);
			for (i = isdu->du_nb, du = isdu->du; i > 0; i--, du++) {
				ASSERT(du);
#ifdef VIRTUAL_TX_MEM
				du->vtm_info.du_in_seq_in_txtab = i;
#endif
				mcl_register_du(mclcb, tl, du, mclcb->nb_tx);
			}
		}
	}
#ifdef DEBUG
	for (lay = 0; lay < nb_lay_in_cycle; lay++) {
		TRACELVL(4, (mcl_stdout,
			"   LCT3_UpdateTxPlanning: layer %d, tot_isdu_nb=%d, aver %.3f DUs/ISDU\n",
			lay, tot_isdu_nb_lay[lay],
			(float)tot_du_nb/(float)tot_isdu_nb_lay[lay]))
	}
#endif /* DEBUG */
	for (lay = 0; lay < nb_lay_in_cycle; lay++) {
		free(fi2isdu_lay[lay]);
	}
	free(fi_permut);
	TRACELVL(5, (mcl_stdout, "<- LCT3_UpdateTxPlanning:\n"))
}


/*
 * returns the total number of data du in this adu
 */
static int
LCT3_mcl_get_tot_nb_of_data_du (mclcb_t	*mclcb,
				adu_t	*adu)
{
	int	i;
	block_t	*blk;
	int	nb = 0;

	/*TRACELVL(5, (mcl_stdout, "-> LCT3_mcl_get_tot_nb_of_data_du:\n"))*/
	for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++)
		nb += blk->k;
	/*TRACELVL(5, (mcl_stdout, "<- LCT3_mcl_get_tot_nb_of_data_du: %d du\n", nb))*/
	return nb;
}


/*
 * initializes the fi2isdu table for this layer with a ptr to the ISDU.
 * the layer necessarily belongs to the first cycle!
 * if fi2isdu is too short, buffer is reallocated and est_isdu_nb adjusted
 * returns the number of du stored
 *
 * A lot of intelligence (and inter-dependancies!) here:
 *    - the whole (padded) data block of an ADU is either entirely on disk or
 *	in ptm. All the data DUs of an ADU are thus contiguous.
 *    - each FEC DU is independantly stored either on disk or in ptm. 
 *
 * Assumes:
 *    - DUs are managed in a single buffer (rather than being doubly linked).
 *    - Moving to the 1st data DU of next block is possible with du++
 *    - This is not true with FEC DUs as the DU tables of each block are
 *      allocated separately.
 *    - adu->data is managed as a whole, ie. is either entirely in ptm or
 *	on disk
 *    - FEC DUs are managed independantely, ie. some of them can be in ptm
 *	whereas the next ones can be on disk for the same ADU or even block.
 */
static int
LCT3_init_fi2isdu (mclcb_t	*mclcb,
		 int		lay,
		 adu_t		*adu,
		 isdu_t		*fi2isdu,
		 int		*est_isd_nb,
		 int		fi_base)	/* fi of 1st du of this adu */
{
	u_int	i;		/* block index in adu */
	u_int	j;		/* du index in block */
	int	seq;		/* isdu seq index */
	int	fi;		/* flat index */
	int	j_off;		/* offset in du index with FEC layers */
	block_t	*blk;
	du_t	*du;

	TRACELVL(5, (mcl_stdout, "-> LCT3_init_fi2isdu: lay=%d, adu=x%x, fi=%d\n", lay, (int)adu, fi_base))
	fi = fi_base;
	if (lay == 0) {
		/*
		 * we are on a data layer, so search DU in du_head[]
		 */
		if (mcl_is_adu_in_ptm(adu)) {
			/* stored in PTM! schedule each DU independantly as
			 * there is no performance problem here */
			for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++) {
				du = blk->du_head;
				for (j = 0; j < blk->k; j++, du++, fi++) { 
					ASSERT(mcl_is_du_in_ptm(du));
					fi2isdu[fi].du = du;
					fi2isdu[fi].du_nb = 1;
				}
			}
			TRACELVL(5, (mcl_stdout,
				"<- LCT3_init_fi2isdu: in PTM, %d seq of data DU, aver %.3f DUs/seq\n",
				fi - fi_base, (float)(LCT3_mcl_get_tot_nb_of_data_du(mclcb, adu))/(float)(fi - fi_base)))
		} else {
			/* stored on disk! use Disk-aware scheduling */
			seq = 0;
			for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++) {
				for (j = 0; j < blk->k; j++) { 
					seq++;
					if (seq == 1) {
						/* first du of an isdu */
						fi2isdu[fi].du =
							&(blk->du_head[j]);
					}
					if (seq == mclcb->desired_du_in_seq_in_txtab) {
						fi2isdu[fi].du_nb = seq;
						fi++;
						seq = 0;
					}
				}
			}
			if (seq > 0) {
				/* registar the last isdu */
				fi2isdu[fi].du_nb = seq;
				fi++;
				seq = 0;
			}
			TRACELVL(5, (mcl_stdout,
				"<- LCT3_init_fi2isdu: in VTM, %d seq of data DU, aver %.3f DUs/seq\n",
				fi - fi_base, (float)(LCT3_mcl_get_tot_nb_of_data_du(mclcb, adu))/(float)(fi - fi_base)))
		}
	} else {
		/*
		 * we are on a FEC layer, so search DU in fec_du_head[]
		 */
		/*
		 * here each FEC DU is independantely stored either on disk
		 * or in PTM! Makes everything a bit more complex...
		 */
		seq = 0;
		for (i = adu->block_nb, blk = adu->block_head; i > 0; i--, blk++) {
			j_off = (lay - 1) * blk->k;
			for (j = 0; j < blk->k; j++) { 
				seq++;
				du = &(blk->fec_du_head[j_off + j]);
				if (mcl_is_du_in_ptm(du)) {
#ifdef NEVERDEF
					if (seq > 1) {
						/* register previous isdu */
						fi2isdu[fi]->du_nb = seq;
						fi++;
					}
#else  /* NEVERDEF */
					ASSERT(seq == 1);
#endif /* NEVERDEF */
					fi2isdu[fi].du = du;
					fi2isdu[fi].du_nb = 1;
					fi++;
					seq = 0;
				} else {
					if (seq == 1) {
						/* first du of an isdu */
						fi2isdu[fi].du = du;
					}
					if (seq == mclcb->desired_du_in_seq_in_txtab) {
						fi2isdu[fi].du_nb = seq;
						fi++;
						seq = 0;
					}
				}
			}
			if (seq > 0) {
				/*
				 * registar the last isdu of block (the next
				 * DU isn't in sequence on the disk)
				 */
				fi2isdu[fi].du_nb = seq;
				fi++;
				seq = 0;
			}
		}
		TRACELVL(5, (mcl_stdout,
			"<- LCT3_init_fi2isdu: %d seq of FEC DU, aver %.3f DUs/seq\n",
			fi - fi_base, (float)(LCT3_mcl_get_tot_nb_of_data_du(mclcb, adu))/(float)(fi - fi_base)))
	}
	return(fi - fi_base);
}


#endif /* } */


/****** LCT scheduling for ANTICIPATED_TX_FOR_PUSH ****************************/
#if defined(ANTICIPATED_TX_FOR_PUSH)	/* { */


static void AnticipTx_register_du_on_right_layer (mclcb_t *mclcb, du_t *du);


/*
 * Create a linear and vertical scheduling of DUs, i.e. accross all layers.
 * Always called with a single adu.
 * No FEC transmission, only data.
 * No randomization here, linear scheduling.
 */
void
AnticipTx_UpdateTxPlanning (mclcb_t	*mclcb,
			    adu_t	*adu)
{
	block_t	*blk;
	int	b_nb;		/* nb of blocks */
	int	du_nb;		/* nb of dus */
	du_t	*du;

	TRACELVL(5, (mcl_stdout, "-> AnticipTx_UpdateTxPlanning:\n"))
	/*
	 * register all the data DUs of this ADU
	 */
	for (b_nb = adu->block_nb, blk = adu->block_head; b_nb > 0; b_nb--, blk++) {
		for (du_nb = blk->k, du = blk->du_head; du_nb > 0; du_nb--, du++) {
			AnticipTx_register_du_on_right_layer(mclcb, du);
		}
	}
	TRACELVL(5, (mcl_stdout, "<- AnticipTx_UpdateTxPlanning:\n"))
}


static void
AnticipTx_register_du_on_right_layer (mclcb_t	*mclcb,
				      du_t	*du)
{
	static int	layer = 0;		/* next tx is on that layer */
	static int	rem_2_tx_on_layer = 1;	/* can send that nb of du */

	TRACELVL(5, (mcl_stdout, "   AnticipTx_register_du_on_right_layer: lay=%d, rem2tx=%d\n", layer, rem_2_tx_on_layer))
	if (rem_2_tx_on_layer <= 0) {
		/* move to next layer */
		/* only consider first 5 or max_level layers */
		if (++layer >= mclcb->max_level || layer >= 5)
			layer = 0;
		rem_2_tx_on_layer = mclcb->txlvl_tab[layer].du_per_tick;
	}
	/* schedule for a SINGLE tx */
#ifdef VIRTUAL_TX_MEM
	du->vtm_info.du_in_seq_in_txtab = 1;
#endif
	mcl_register_du(mclcb, &(mclcb->txlvl_tab[layer]), du, 1);
	rem_2_tx_on_layer--;
	/*TRACELVL(5, (mcl_stdout, "<- AnticipTx_register_du_on_right_layer: layer=%d\n", layer))*/
}


#endif /* ANTICIPATED_TX_FOR_PUSH } */