[deliverable/linux.git] / net / dccp / ccids / lib / tfrc_equation.c

/*
 *  net/dccp/ccids/lib/tfrc_equation.c
 *
 *  Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
 *  Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
 *  Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
 *  Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
 *
 *  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.
 */

#include <linux/config.h>
#include <linux/module.h>

#include <asm/div64.h>

#include "tfrc.h"

#define TFRC_CALC_X_ARRSIZE 500

#define TFRC_CALC_X_SPLIT 50000
/* equivalent to 0.05 */

static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
	{     37172,   8172 },
	{     53499,  11567 },
	{     66664,  14180 },
	{     78298,  16388 },
	{     89021,  18339 },
	{     99147,  20108 },
	{    108858,  21738 },
	{    118273,  23260 },
	{    127474,  24693 },
	{    136520,  26052 },
	{    145456,  27348 },
	{    154316,  28589 },
	{    163130,  29783 },
	{    171919,  30935 },
	{    180704,  32049 },
	{    189502,  33130 },
	{    198328,  34180 },
	{    207194,  35202 },
	{    216114,  36198 },
	{    225097,  37172 },
	{    234153,  38123 },
	{    243294,  39055 },
	{    252527,  39968 },
	{    261861,  40864 },
	{    271305,  41743 },
	{    280866,  42607 },
	{    290553,  43457 },
	{    300372,  44293 },
	{    310333,  45117 },
	{    320441,  45929 },
	{    330705,  46729 },
	{    341131,  47518 },
	{    351728,  48297 },
	{    362501,  49066 },
	{    373460,  49826 },
	{    384609,  50577 },
	{    395958,  51320 },
	{    407513,  52054 },
	{    419281,  52780 },
	{    431270,  53499 },
	{    443487,  54211 },
	{    455940,  54916 },
	{    468635,  55614 },
	{    481581,  56306 },
	{    494785,  56991 },
	{    508254,  57671 },
	{    521996,  58345 },
	{    536019,  59014 },
	{    550331,  59677 },
	{    564939,  60335 },
	{    579851,  60988 },
	{    595075,  61636 },
	{    610619,  62279 },
	{    626491,  62918 },
	{    642700,  63553 },
	{    659253,  64183 },
	{    676158,  64809 },
	{    693424,  65431 },
	{    711060,  66050 },
	{    729073,  66664 },
	{    747472,  67275 },
	{    766266,  67882 },
	{    785464,  68486 },
	{    805073,  69087 },
	{    825103,  69684 },
	{    845562,  70278 },
	{    866460,  70868 },
	{    887805,  71456 },
	{    909606,  72041 },
	{    931873,  72623 },
	{    954614,  73202 },
	{    977839,  73778 },
	{   1001557,  74352 },
	{   1025777,  74923 },
	{   1050508,  75492 },
	{   1075761,  76058 },
	{   1101544,  76621 },
	{   1127867,  77183 },
	{   1154739,  77741 },
	{   1182172,  78298 },
	{   1210173,  78852 },
	{   1238753,  79405 },
	{   1267922,  79955 },
	{   1297689,  80503 },
	{   1328066,  81049 },
	{   1359060,  81593 },
	{   1390684,  82135 },
	{   1422947,  82675 },
	{   1455859,  83213 },
	{   1489430,  83750 },
	{   1523671,  84284 },
	{   1558593,  84817 },
	{   1594205,  85348 },
	{   1630518,  85878 },
	{   1667543,  86406 },
	{   1705290,  86932 },
	{   1743770,  87457 },
	{   1782994,  87980 },
	{   1822973,  88501 },
	{   1863717,  89021 },
	{   1905237,  89540 },
	{   1947545,  90057 },
	{   1990650,  90573 },
	{   2034566,  91087 },
	{   2079301,  91600 },
	{   2124869,  92111 },
	{   2171279,  92622 },
	{   2218543,  93131 },
	{   2266673,  93639 },
	{   2315680,  94145 },
	{   2365575,  94650 },
	{   2416371,  95154 },
	{   2468077,  95657 },
	{   2520707,  96159 },
	{   2574271,  96660 },
	{   2628782,  97159 },
	{   2684250,  97658 },
	{   2740689,  98155 },
	{   2798110,  98651 },
	{   2856524,  99147 },
	{   2915944,  99641 },
	{   2976382, 100134 },
	{   3037850, 100626 },
	{   3100360, 101117 },
	{   3163924, 101608 },
	{   3228554, 102097 },
	{   3294263, 102586 },
	{   3361063, 103073 },
	{   3428966, 103560 },
	{   3497984, 104045 },
	{   3568131, 104530 },
	{   3639419, 105014 },
	{   3711860, 105498 },
	{   3785467, 105980 },
	{   3860253, 106462 },
	{   3936229, 106942 },
	{   4013410, 107422 },
	{   4091808, 107902 },
	{   4171435, 108380 },
	{   4252306, 108858 },
	{   4334431, 109335 },
	{   4417825, 109811 },
	{   4502501, 110287 },
	{   4588472, 110762 },
	{   4675750, 111236 },
	{   4764349, 111709 },
	{   4854283, 112182 },
	{   4945564, 112654 },
	{   5038206, 113126 },
	{   5132223, 113597 },
	{   5227627, 114067 },
	{   5324432, 114537 },
	{   5422652, 115006 },
	{   5522299, 115474 },
	{   5623389, 115942 },
	{   5725934, 116409 },
	{   5829948, 116876 },
	{   5935446, 117342 },
	{   6042439, 117808 },
	{   6150943, 118273 },
	{   6260972, 118738 },
	{   6372538, 119202 },
	{   6485657, 119665 },
	{   6600342, 120128 },
	{   6716607, 120591 },
	{   6834467, 121053 },
	{   6953935, 121514 },
	{   7075025, 121976 },
	{   7197752, 122436 },
	{   7322131, 122896 },
	{   7448175, 123356 },
	{   7575898, 123815 },
	{   7705316, 124274 },
	{   7836442, 124733 },
	{   7969291, 125191 },
	{   8103877, 125648 },
	{   8240216, 126105 },
	{   8378321, 126562 },
	{   8518208, 127018 },
	{   8659890, 127474 },
	{   8803384, 127930 },
	{   8948702, 128385 },
	{   9095861, 128840 },
	{   9244875, 129294 },
	{   9395760, 129748 },
	{   9548529, 130202 },
	{   9703198, 130655 },
	{   9859782, 131108 },
	{  10018296, 131561 },
	{  10178755, 132014 },
	{  10341174, 132466 },
	{  10505569, 132917 },
	{  10671954, 133369 },
	{  10840345, 133820 },
	{  11010757, 134271 },
	{  11183206, 134721 },
	{  11357706, 135171 },
	{  11534274, 135621 },
	{  11712924, 136071 },
	{  11893673, 136520 },
	{  12076536, 136969 },
	{  12261527, 137418 },
	{  12448664, 137867 },
	{  12637961, 138315 },
	{  12829435, 138763 },
	{  13023101, 139211 },
	{  13218974, 139658 },
	{  13417071, 140106 },
	{  13617407, 140553 },
	{  13819999, 140999 },
	{  14024862, 141446 },
	{  14232012, 141892 },
	{  14441465, 142339 },
	{  14653238, 142785 },
	{  14867346, 143230 },
	{  15083805, 143676 },
	{  15302632, 144121 },
	{  15523842, 144566 },
	{  15747453, 145011 },
	{  15973479, 145456 },
	{  16201939, 145900 },
	{  16432847, 146345 },
	{  16666221, 146789 },
	{  16902076, 147233 },
	{  17140429, 147677 },
	{  17381297, 148121 },
	{  17624696, 148564 },
	{  17870643, 149007 },
	{  18119154, 149451 },
	{  18370247, 149894 },
	{  18623936, 150336 },
	{  18880241, 150779 },
	{  19139176, 151222 },
	{  19400759, 151664 },
	{  19665007, 152107 },
	{  19931936, 152549 },
	{  20201564, 152991 },
	{  20473907, 153433 },
	{  20748982, 153875 },
	{  21026807, 154316 },
	{  21307399, 154758 },
	{  21590773, 155199 },
	{  21876949, 155641 },
	{  22165941, 156082 },
	{  22457769, 156523 },
	{  22752449, 156964 },
	{  23049999, 157405 },
	{  23350435, 157846 },
	{  23653774, 158287 },
	{  23960036, 158727 },
	{  24269236, 159168 },
	{  24581392, 159608 },
	{  24896521, 160049 },
	{  25214642, 160489 },
	{  25535772, 160929 },
	{  25859927, 161370 },
	{  26187127, 161810 },
	{  26517388, 162250 },
	{  26850728, 162690 },
	{  27187165, 163130 },
	{  27526716, 163569 },
	{  27869400, 164009 },
	{  28215234, 164449 },
	{  28564236, 164889 },
	{  28916423, 165328 },
	{  29271815, 165768 },
	{  29630428, 166208 },
	{  29992281, 166647 },
	{  30357392, 167087 },
	{  30725779, 167526 },
	{  31097459, 167965 },
	{  31472452, 168405 },
	{  31850774, 168844 },
	{  32232445, 169283 },
	{  32617482, 169723 },
	{  33005904, 170162 },
	{  33397730, 170601 },
	{  33792976, 171041 },
	{  34191663, 171480 },
	{  34593807, 171919 },
	{  34999428, 172358 },
	{  35408544, 172797 },
	{  35821174, 173237 },
	{  36237335, 173676 },
	{  36657047, 174115 },
	{  37080329, 174554 },
	{  37507197, 174993 },
	{  37937673, 175433 },
	{  38371773, 175872 },
	{  38809517, 176311 },
	{  39250924, 176750 },
	{  39696012, 177190 },
	{  40144800, 177629 },
	{  40597308, 178068 },
	{  41053553, 178507 },
	{  41513554, 178947 },
	{  41977332, 179386 },
	{  42444904, 179825 },
	{  42916290, 180265 },
	{  43391509, 180704 },
	{  43870579, 181144 },
	{  44353520, 181583 },
	{  44840352, 182023 },
	{  45331092, 182462 },
	{  45825761, 182902 },
	{  46324378, 183342 },
	{  46826961, 183781 },
	{  47333531, 184221 },
	{  47844106, 184661 },
	{  48358706, 185101 },
	{  48877350, 185541 },
	{  49400058, 185981 },
	{  49926849, 186421 },
	{  50457743, 186861 },
	{  50992759, 187301 },
	{  51531916, 187741 },
	{  52075235, 188181 },
	{  52622735, 188622 },
	{  53174435, 189062 },
	{  53730355, 189502 },
	{  54290515, 189943 },
	{  54854935, 190383 },
	{  55423634, 190824 },
	{  55996633, 191265 },
	{  56573950, 191706 },
	{  57155606, 192146 },
	{  57741621, 192587 },
	{  58332014, 193028 },
	{  58926806, 193470 },
	{  59526017, 193911 },
	{  60129666, 194352 },
	{  60737774, 194793 },
	{  61350361, 195235 },
	{  61967446, 195677 },
	{  62589050, 196118 },
	{  63215194, 196560 },
	{  63845897, 197002 },
	{  64481179, 197444 },
	{  65121061, 197886 },
	{  65765563, 198328 },
	{  66414705, 198770 },
	{  67068508, 199213 },
	{  67726992, 199655 },
	{  68390177, 200098 },
	{  69058085, 200540 },
	{  69730735, 200983 },
	{  70408147, 201426 },
	{  71090343, 201869 },
	{  71777343, 202312 },
	{  72469168, 202755 },
	{  73165837, 203199 },
	{  73867373, 203642 },
	{  74573795, 204086 },
	{  75285124, 204529 },
	{  76001380, 204973 },
	{  76722586, 205417 },
	{  77448761, 205861 },
	{  78179926, 206306 },
	{  78916102, 206750 },
	{  79657310, 207194 },
	{  80403571, 207639 },
	{  81154906, 208084 },
	{  81911335, 208529 },
	{  82672880, 208974 },
	{  83439562, 209419 },
	{  84211402, 209864 },
	{  84988421, 210309 },
	{  85770640, 210755 },
	{  86558080, 211201 },
	{  87350762, 211647 },
	{  88148708, 212093 },
	{  88951938, 212539 },
	{  89760475, 212985 },
	{  90574339, 213432 },
	{  91393551, 213878 },
	{  92218133, 214325 },
	{  93048107, 214772 },
	{  93883493, 215219 },
	{  94724314, 215666 },
	{  95570590, 216114 },
	{  96422343, 216561 },
	{  97279594, 217009 },
	{  98142366, 217457 },
	{  99010679, 217905 },
	{  99884556, 218353 },
	{ 100764018, 218801 },
	{ 101649086, 219250 },
	{ 102539782, 219698 },
	{ 103436128, 220147 },
	{ 104338146, 220596 },
	{ 105245857, 221046 },
	{ 106159284, 221495 },
	{ 107078448, 221945 },
	{ 108003370, 222394 },
	{ 108934074, 222844 },
	{ 109870580, 223294 },
	{ 110812910, 223745 },
	{ 111761087, 224195 },
	{ 112715133, 224646 },
	{ 113675069, 225097 },
	{ 114640918, 225548 },
	{ 115612702, 225999 },
	{ 116590442, 226450 },
	{ 117574162, 226902 },
	{ 118563882, 227353 },
	{ 119559626, 227805 },
	{ 120561415, 228258 },
	{ 121569272, 228710 },
	{ 122583219, 229162 },
	{ 123603278, 229615 },
	{ 124629471, 230068 },
	{ 125661822, 230521 },
	{ 126700352, 230974 },
	{ 127745083, 231428 },
	{ 128796039, 231882 },
	{ 129853241, 232336 },
	{ 130916713, 232790 },
	{ 131986475, 233244 },
	{ 133062553, 233699 },
	{ 134144966, 234153 },
	{ 135233739, 234608 },
	{ 136328894, 235064 },
	{ 137430453, 235519 },
	{ 138538440, 235975 },
	{ 139652876, 236430 },
	{ 140773786, 236886 },
	{ 141901190, 237343 },
	{ 143035113, 237799 },
	{ 144175576, 238256 },
	{ 145322604, 238713 },
	{ 146476218, 239170 },
	{ 147636442, 239627 },
	{ 148803298, 240085 },
	{ 149976809, 240542 },
	{ 151156999, 241000 },
	{ 152343890, 241459 },
	{ 153537506, 241917 },
	{ 154737869, 242376 },
	{ 155945002, 242835 },
	{ 157158929, 243294 },
	{ 158379673, 243753 },
	{ 159607257, 244213 },
	{ 160841704, 244673 },
	{ 162083037, 245133 },
	{ 163331279, 245593 },
	{ 164586455, 246054 },
	{ 165848586, 246514 },
	{ 167117696, 246975 },
	{ 168393810, 247437 },
	{ 169676949, 247898 },
	{ 170967138, 248360 },
	{ 172264399, 248822 },
	{ 173568757, 249284 },
	{ 174880235, 249747 },
	{ 176198856, 250209 },
	{ 177524643, 250672 },
	{ 178857621, 251136 },
	{ 180197813, 251599 },
	{ 181545242, 252063 },
	{ 182899933, 252527 },
	{ 184261908, 252991 },
	{ 185631191, 253456 },
	{ 187007807, 253920 },
	{ 188391778, 254385 },
	{ 189783129, 254851 },
	{ 191181884, 255316 },
	{ 192588065, 255782 },
	{ 194001698, 256248 },
	{ 195422805, 256714 },
	{ 196851411, 257181 },
	{ 198287540, 257648 },
	{ 199731215, 258115 },
	{ 201182461, 258582 },
	{ 202641302, 259050 },
	{ 204107760, 259518 },
	{ 205581862, 259986 },
	{ 207063630, 260454 },
	{ 208553088, 260923 },
	{ 210050262, 261392 },
	{ 211555174, 261861 },
	{ 213067849, 262331 },
	{ 214588312, 262800 },
	{ 216116586, 263270 },
	{ 217652696, 263741 },
	{ 219196666, 264211 },
	{ 220748520, 264682 },
	{ 222308282, 265153 },
	{ 223875978, 265625 },
	{ 225451630, 266097 },
	{ 227035265, 266569 },
	{ 228626905, 267041 },
	{ 230226576, 267514 },
	{ 231834302, 267986 },
	{ 233450107, 268460 },
	{ 235074016, 268933 },
	{ 236706054, 269407 },
	{ 238346244, 269881 },
	{ 239994613, 270355 },
	{ 241651183, 270830 },
	{ 243315981, 271305 }
};

/* Calculate the send rate as per section 3.1 of RFC3448
 
Returns send rate in bytes per second

Integer maths and lookups are used as not allowed floating point in kernel

The function for Xcalc as per section 3.1 of RFC3448 is:

X =                            s
     -------------------------------------------------------------
     R*sqrt(2*b*p/3) + (t_RTO * (3*sqrt(3*b*p/8) * p * (1+32*p^2)))

where 
X is the trasmit rate in bytes/second
s is the packet size in bytes
R is the round trip time in seconds
p is the loss event rate, between 0 and 1.0, of the number of loss events 
  as a fraction of the number of packets transmitted
t_RTO is the TCP retransmission timeout value in seconds
b is the number of packets acknowledged by a single TCP acknowledgement

we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:

X =                            s
     -----------------------------------------------------------------------
     R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))


which we can break down into:

X =     s
     --------
     R * f(p)

where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))

Function parameters:
s - bytes
R - RTT in usecs
p - loss rate (decimal fraction multiplied by 1,000,000)

Returns Xcalc in bytes per second

DON'T alter this code unless you run test cases against it as the code
has been manipulated to stop underflow/overlow.

*/
u32 tfrc_calc_x(u16 s, u32 R, u32 p)
{
	int index;
	u32 f;
	u64 tmp1, tmp2;

	if (p < TFRC_CALC_X_SPLIT)
		index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
	else
		index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;

	if (index < 0)
		/* p should be 0 unless there is a bug in my code */
		index = 0;

	if (R == 0)
		R = 1; /* RTT can't be zero or else divide by zero */

	BUG_ON(index >= TFRC_CALC_X_ARRSIZE);

	if (p >= TFRC_CALC_X_SPLIT)
		f = tfrc_calc_x_lookup[index][0];
	else
		f = tfrc_calc_x_lookup[index][1];

	tmp1 = ((u64)s * 100000000);
	tmp2 = ((u64)R * (u64)f);
	do_div(tmp2, 10000);
	do_div(tmp1, tmp2); 
	/* Don't alter above math unless you test due to overflow on 32 bit */

	return (u32)tmp1; 
}

EXPORT_SYMBOL_GPL(tfrc_calc_x);

/*
 * args: fvalue - function value to match
 * returns: p closest to that value
 *
 * both fvalue and p are multiplied by 1,000,000 to use ints
 */
u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
{
	int ctr = 0;
	int small;

	if (fvalue < tfrc_calc_x_lookup[0][1])
		return 0;

	if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1])
		small = 1;
	else if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0])
		return 1000000;
	else
		small = 0;

	while (fvalue > tfrc_calc_x_lookup[ctr][small])
		ctr++;

	if (small)
		return TFRC_CALC_X_SPLIT * ctr / TFRC_CALC_X_ARRSIZE;
	else
		return 1000000 * ctr / TFRC_CALC_X_ARRSIZE;
}

EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);
Commit	Line	Data
36729c1a ACM	1	/*
	2	* net/dccp/ccids/lib/tfrc_equation.c
	3	*
	4	* Copyright (c) 2005 The University of Waikato, Hamilton, New Zealand.
	5	* Copyright (c) 2005 Ian McDonald <iam4@cs.waikato.ac.nz>
	6	* Copyright (c) 2005 Arnaldo Carvalho de Melo <acme@conectiva.com.br>
	7	* Copyright (c) 2003 Nils-Erik Mattsson, Joacim Haggmark, Magnus Erixzon
	8	*
	9	* This program is free software; you can redistribute it and/or modify
	10	* it under the terms of the GNU General Public License as published by
	11	* the Free Software Foundation; either version 2 of the License, or
	12	* (at your option) any later version.
	13	*/
	14
	15	#include <linux/config.h>
	16	#include <linux/module.h>
	17
36729c1a ACM	18	#include <asm/div64.h>
	19
	20	#include "tfrc.h"
	21
	22	#define TFRC_CALC_X_ARRSIZE 500
	23
	24	#define TFRC_CALC_X_SPLIT 50000
	25	/* equivalent to 0.05 */
	26
	27	static const u32 tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE][2] = {
	28	{ 37172, 8172 },
	29	{ 53499, 11567 },
	30	{ 66664, 14180 },
	31	{ 78298, 16388 },
	32	{ 89021, 18339 },
	33	{ 99147, 20108 },
	34	{ 108858, 21738 },
	35	{ 118273, 23260 },
	36	{ 127474, 24693 },
	37	{ 136520, 26052 },
	38	{ 145456, 27348 },
	39	{ 154316, 28589 },
	40	{ 163130, 29783 },
	41	{ 171919, 30935 },
	42	{ 180704, 32049 },
	43	{ 189502, 33130 },
	44	{ 198328, 34180 },
	45	{ 207194, 35202 },
	46	{ 216114, 36198 },
	47	{ 225097, 37172 },
	48	{ 234153, 38123 },
	49	{ 243294, 39055 },
	50	{ 252527, 39968 },
	51	{ 261861, 40864 },
	52	{ 271305, 41743 },
	53	{ 280866, 42607 },
	54	{ 290553, 43457 },
	55	{ 300372, 44293 },
	56	{ 310333, 45117 },
	57	{ 320441, 45929 },
	58	{ 330705, 46729 },
	59	{ 341131, 47518 },
	60	{ 351728, 48297 },
	61	{ 362501, 49066 },
	62	{ 373460, 49826 },
	63	{ 384609, 50577 },
	64	{ 395958, 51320 },
	65	{ 407513, 52054 },
	66	{ 419281, 52780 },
	67	{ 431270, 53499 },
	68	{ 443487, 54211 },
	69	{ 455940, 54916 },
	70	{ 468635, 55614 },
	71	{ 481581, 56306 },
	72	{ 494785, 56991 },
	73	{ 508254, 57671 },
	74	{ 521996, 58345 },
	75	{ 536019, 59014 },
	76	{ 550331, 59677 },
	77	{ 564939, 60335 },
	78	{ 579851, 60988 },
	79	{ 595075, 61636 },
	80	{ 610619, 62279 },
	81	{ 626491, 62918 },
82	{ 642700, 63553 },
83	{ 659253, 64183 },
84	{ 676158, 64809 },
85	{ 693424, 65431 },
86	{ 711060, 66050 },
87	{ 729073, 66664 },
88	{ 747472, 67275 },
89	{ 766266, 67882 },
90	{ 785464, 68486 },
91	{ 805073, 69087 },
92	{ 825103, 69684 },
93	{ 845562, 70278 },
94	{ 866460, 70868 },
95	{ 887805, 71456 },
96	{ 909606, 72041 },
97	{ 931873, 72623 },
98	{ 954614, 73202 },
99	{ 977839, 73778 },
100	{ 1001557, 74352 },
101	{ 1025777, 74923 },
102	{ 1050508, 75492 },
103	{ 1075761, 76058 },
104	{ 1101544, 76621 },
105	{ 1127867, 77183 },
106	{ 1154739, 77741 },
107	{ 1182172, 78298 },
108	{ 1210173, 78852 },
109	{ 1238753, 79405 },
110	{ 1267922, 79955 },
111	{ 1297689, 80503 },
112	{ 1328066, 81049 },
113	{ 1359060, 81593 },
114	{ 1390684, 82135 },
115	{ 1422947, 82675 },
116	{ 1455859, 83213 },
117	{ 1489430, 83750 },
118	{ 1523671, 84284 },
119	{ 1558593, 84817 },
120	{ 1594205, 85348 },
121	{ 1630518, 85878 },
122	{ 1667543, 86406 },
123	{ 1705290, 86932 },
124	{ 1743770, 87457 },
125	{ 1782994, 87980 },
126	{ 1822973, 88501 },
127	{ 1863717, 89021 },
128	{ 1905237, 89540 },
129	{ 1947545, 90057 },
130	{ 1990650, 90573 },
131	{ 2034566, 91087 },
132	{ 2079301, 91600 },
133	{ 2124869, 92111 },
134	{ 2171279, 92622 },
135	{ 2218543, 93131 },
136	{ 2266673, 93639 },
137	{ 2315680, 94145 },
138	{ 2365575, 94650 },
139	{ 2416371, 95154 },
140	{ 2468077, 95657 },
141	{ 2520707, 96159 },
142	{ 2574271, 96660 },
143	{ 2628782, 97159 },
144	{ 2684250, 97658 },
145	{ 2740689, 98155 },
146	{ 2798110, 98651 },
147	{ 2856524, 99147 },
148	{ 2915944, 99641 },
149	{ 2976382, 100134 },
150	{ 3037850, 100626 },
151	{ 3100360, 101117 },
152	{ 3163924, 101608 },
153	{ 3228554, 102097 },
154	{ 3294263, 102586 },
155	{ 3361063, 103073 },
156	{ 3428966, 103560 },
157	{ 3497984, 104045 },
158	{ 3568131, 104530 },
159	{ 3639419, 105014 },
160	{ 3711860, 105498 },
161	{ 3785467, 105980 },
162	{ 3860253, 106462 },
163	{ 3936229, 106942 },
164	{ 4013410, 107422 },
165	{ 4091808, 107902 },
166	{ 4171435, 108380 },
167	{ 4252306, 108858 },
168	{ 4334431, 109335 },
169	{ 4417825, 109811 },
170	{ 4502501, 110287 },
171	{ 4588472, 110762 },
172	{ 4675750, 111236 },
173	{ 4764349, 111709 },
174	{ 4854283, 112182 },
175	{ 4945564, 112654 },
176	{ 5038206, 113126 },
177	{ 5132223, 113597 },
178	{ 5227627, 114067 },
179	{ 5324432, 114537 },
180	{ 5422652, 115006 },
181	{ 5522299, 115474 },
182	{ 5623389, 115942 },
183	{ 5725934, 116409 },
184	{ 5829948, 116876 },
185	{ 5935446, 117342 },
186	{ 6042439, 117808 },
187	{ 6150943, 118273 },
188	{ 6260972, 118738 },
189	{ 6372538, 119202 },
190	{ 6485657, 119665 },
191	{ 6600342, 120128 },
192	{ 6716607, 120591 },
193	{ 6834467, 121053 },
194	{ 6953935, 121514 },
195	{ 7075025, 121976 },
196	{ 7197752, 122436 },
197	{ 7322131, 122896 },
198	{ 7448175, 123356 },
199	{ 7575898, 123815 },
200	{ 7705316, 124274 },
201	{ 7836442, 124733 },
202	{ 7969291, 125191 },
203	{ 8103877, 125648 },
204	{ 8240216, 126105 },
205	{ 8378321, 126562 },
206	{ 8518208, 127018 },
207	{ 8659890, 127474 },
208	{ 8803384, 127930 },
209	{ 8948702, 128385 },
210	{ 9095861, 128840 },
211	{ 9244875, 129294 },
212	{ 9395760, 129748 },
213	{ 9548529, 130202 },
214	{ 9703198, 130655 },
215	{ 9859782, 131108 },
216	{ 10018296, 131561 },
217	{ 10178755, 132014 },
218	{ 10341174, 132466 },
219	{ 10505569, 132917 },
220	{ 10671954, 133369 },
221	{ 10840345, 133820 },
222	{ 11010757, 134271 },
223	{ 11183206, 134721 },
224	{ 11357706, 135171 },
225	{ 11534274, 135621 },
226	{ 11712924, 136071 },
227	{ 11893673, 136520 },
228	{ 12076536, 136969 },
229	{ 12261527, 137418 },
230	{ 12448664, 137867 },
231	{ 12637961, 138315 },
232	{ 12829435, 138763 },
233	{ 13023101, 139211 },
234	{ 13218974, 139658 },
235	{ 13417071, 140106 },
236	{ 13617407, 140553 },
237	{ 13819999, 140999 },
238	{ 14024862, 141446 },
239	{ 14232012, 141892 },
240	{ 14441465, 142339 },
241	{ 14653238, 142785 },
242	{ 14867346, 143230 },
243	{ 15083805, 143676 },
244	{ 15302632, 144121 },
245	{ 15523842, 144566 },
246	{ 15747453, 145011 },
247	{ 15973479, 145456 },
248	{ 16201939, 145900 },
249	{ 16432847, 146345 },
250	{ 16666221, 146789 },
251	{ 16902076, 147233 },
252	{ 17140429, 147677 },
253	{ 17381297, 148121 },
254	{ 17624696, 148564 },
255	{ 17870643, 149007 },
256	{ 18119154, 149451 },
257	{ 18370247, 149894 },
258	{ 18623936, 150336 },
259	{ 18880241, 150779 },
260	{ 19139176, 151222 },
261	{ 19400759, 151664 },
262	{ 19665007, 152107 },
263	{ 19931936, 152549 },
264	{ 20201564, 152991 },
265	{ 20473907, 153433 },
266	{ 20748982, 153875 },
267	{ 21026807, 154316 },
268	{ 21307399, 154758 },
269	{ 21590773, 155199 },
270	{ 21876949, 155641 },
271	{ 22165941, 156082 },
272	{ 22457769, 156523 },
273	{ 22752449, 156964 },
274	{ 23049999, 157405 },
275	{ 23350435, 157846 },
276	{ 23653774, 158287 },
277	{ 23960036, 158727 },
278	{ 24269236, 159168 },
279	{ 24581392, 159608 },
280	{ 24896521, 160049 },
281	{ 25214642, 160489 },
282	{ 25535772, 160929 },
283	{ 25859927, 161370 },
284	{ 26187127, 161810 },
285	{ 26517388, 162250 },
286	{ 26850728, 162690 },
287	{ 27187165, 163130 },
288	{ 27526716, 163569 },
289	{ 27869400, 164009 },
290	{ 28215234, 164449 },
291	{ 28564236, 164889 },
292	{ 28916423, 165328 },
293	{ 29271815, 165768 },
294	{ 29630428, 166208 },
295	{ 29992281, 166647 },
296	{ 30357392, 167087 },
297	{ 30725779, 167526 },
298	{ 31097459, 167965 },
299	{ 31472452, 168405 },
300	{ 31850774, 168844 },
301	{ 32232445, 169283 },
302	{ 32617482, 169723 },
303	{ 33005904, 170162 },
304	{ 33397730, 170601 },
305	{ 33792976, 171041 },
306	{ 34191663, 171480 },
307	{ 34593807, 171919 },
308	{ 34999428, 172358 },
309	{ 35408544, 172797 },
310	{ 35821174, 173237 },
311	{ 36237335, 173676 },
312	{ 36657047, 174115 },
313	{ 37080329, 174554 },
314	{ 37507197, 174993 },
315	{ 37937673, 175433 },
316	{ 38371773, 175872 },
317	{ 38809517, 176311 },
318	{ 39250924, 176750 },
319	{ 39696012, 177190 },
320	{ 40144800, 177629 },
321	{ 40597308, 178068 },
322	{ 41053553, 178507 },
323	{ 41513554, 178947 },
324	{ 41977332, 179386 },
325	{ 42444904, 179825 },
326	{ 42916290, 180265 },
327	{ 43391509, 180704 },
328	{ 43870579, 181144 },
329	{ 44353520, 181583 },
330	{ 44840352, 182023 },
331	{ 45331092, 182462 },
332	{ 45825761, 182902 },
333	{ 46324378, 183342 },
334	{ 46826961, 183781 },
335	{ 47333531, 184221 },
336	{ 47844106, 184661 },
337	{ 48358706, 185101 },
338	{ 48877350, 185541 },
339	{ 49400058, 185981 },
340	{ 49926849, 186421 },
341	{ 50457743, 186861 },
342	{ 50992759, 187301 },
343	{ 51531916, 187741 },
344	{ 52075235, 188181 },
345	{ 52622735, 188622 },
346	{ 53174435, 189062 },
347	{ 53730355, 189502 },
348	{ 54290515, 189943 },
349	{ 54854935, 190383 },
350	{ 55423634, 190824 },
351	{ 55996633, 191265 },
352	{ 56573950, 191706 },
353	{ 57155606, 192146 },
354	{ 57741621, 192587 },
355	{ 58332014, 193028 },
356	{ 58926806, 193470 },
357	{ 59526017, 193911 },
358	{ 60129666, 194352 },
359	{ 60737774, 194793 },
360	{ 61350361, 195235 },
361	{ 61967446, 195677 },
362	{ 62589050, 196118 },
363	{ 63215194, 196560 },
364	{ 63845897, 197002 },
365	{ 64481179, 197444 },
366	{ 65121061, 197886 },
367	{ 65765563, 198328 },
368	{ 66414705, 198770 },
369	{ 67068508, 199213 },
370	{ 67726992, 199655 },
371	{ 68390177, 200098 },
372	{ 69058085, 200540 },
373	{ 69730735, 200983 },
374	{ 70408147, 201426 },
375	{ 71090343, 201869 },
376	{ 71777343, 202312 },
377	{ 72469168, 202755 },
378	{ 73165837, 203199 },
379	{ 73867373, 203642 },
380	{ 74573795, 204086 },
381	{ 75285124, 204529 },
382	{ 76001380, 204973 },
383	{ 76722586, 205417 },
384	{ 77448761, 205861 },
385	{ 78179926, 206306 },
386	{ 78916102, 206750 },
387	{ 79657310, 207194 },
388	{ 80403571, 207639 },
389	{ 81154906, 208084 },
390	{ 81911335, 208529 },
391	{ 82672880, 208974 },
392	{ 83439562, 209419 },
393	{ 84211402, 209864 },
394	{ 84988421, 210309 },
395	{ 85770640, 210755 },
396	{ 86558080, 211201 },
397	{ 87350762, 211647 },
398	{ 88148708, 212093 },
399	{ 88951938, 212539 },
400	{ 89760475, 212985 },
401	{ 90574339, 213432 },
402	{ 91393551, 213878 },
403	{ 92218133, 214325 },
404	{ 93048107, 214772 },
405	{ 93883493, 215219 },
406	{ 94724314, 215666 },
407	{ 95570590, 216114 },
408	{ 96422343, 216561 },
409	{ 97279594, 217009 },
410	{ 98142366, 217457 },
411	{ 99010679, 217905 },
412	{ 99884556, 218353 },
413	{ 100764018, 218801 },
414	{ 101649086, 219250 },
415	{ 102539782, 219698 },
416	{ 103436128, 220147 },
417	{ 104338146, 220596 },
418	{ 105245857, 221046 },
419	{ 106159284, 221495 },
420	{ 107078448, 221945 },
421	{ 108003370, 222394 },
422	{ 108934074, 222844 },
423	{ 109870580, 223294 },
424	{ 110812910, 223745 },
425	{ 111761087, 224195 },
426	{ 112715133, 224646 },
427	{ 113675069, 225097 },
428	{ 114640918, 225548 },
429	{ 115612702, 225999 },
430	{ 116590442, 226450 },
431	{ 117574162, 226902 },
432	{ 118563882, 227353 },
433	{ 119559626, 227805 },
434	{ 120561415, 228258 },
435	{ 121569272, 228710 },
436	{ 122583219, 229162 },
437	{ 123603278, 229615 },
438	{ 124629471, 230068 },
439	{ 125661822, 230521 },
440	{ 126700352, 230974 },
441	{ 127745083, 231428 },
442	{ 128796039, 231882 },
443	{ 129853241, 232336 },
444	{ 130916713, 232790 },
445	{ 131986475, 233244 },
446	{ 133062553, 233699 },
447	{ 134144966, 234153 },
448	{ 135233739, 234608 },
449	{ 136328894, 235064 },
450	{ 137430453, 235519 },
451	{ 138538440, 235975 },
452	{ 139652876, 236430 },
453	{ 140773786, 236886 },
454	{ 141901190, 237343 },
455	{ 143035113, 237799 },
456	{ 144175576, 238256 },
457	{ 145322604, 238713 },
458	{ 146476218, 239170 },
459	{ 147636442, 239627 },
460	{ 148803298, 240085 },
461	{ 149976809, 240542 },
462	{ 151156999, 241000 },
463	{ 152343890, 241459 },
464	{ 153537506, 241917 },
465	{ 154737869, 242376 },
466	{ 155945002, 242835 },
467	{ 157158929, 243294 },
468	{ 158379673, 243753 },
469	{ 159607257, 244213 },
470	{ 160841704, 244673 },
471	{ 162083037, 245133 },
472	{ 163331279, 245593 },
473	{ 164586455, 246054 },
474	{ 165848586, 246514 },
475	{ 167117696, 246975 },
476	{ 168393810, 247437 },
477	{ 169676949, 247898 },
478	{ 170967138, 248360 },
479	{ 172264399, 248822 },
480	{ 173568757, 249284 },
481	{ 174880235, 249747 },
482	{ 176198856, 250209 },
483	{ 177524643, 250672 },
484	{ 178857621, 251136 },
485	{ 180197813, 251599 },
486	{ 181545242, 252063 },
487	{ 182899933, 252527 },
488	{ 184261908, 252991 },
489	{ 185631191, 253456 },
490	{ 187007807, 253920 },
491	{ 188391778, 254385 },
492	{ 189783129, 254851 },
493	{ 191181884, 255316 },
494	{ 192588065, 255782 },
495	{ 194001698, 256248 },
496	{ 195422805, 256714 },
497	{ 196851411, 257181 },
498	{ 198287540, 257648 },
499	{ 199731215, 258115 },
500	{ 201182461, 258582 },
501	{ 202641302, 259050 },
502	{ 204107760, 259518 },
503	{ 205581862, 259986 },
504	{ 207063630, 260454 },
505	{ 208553088, 260923 },
506	{ 210050262, 261392 },
507	{ 211555174, 261861 },
508	{ 213067849, 262331 },
509	{ 214588312, 262800 },
510	{ 216116586, 263270 },
511	{ 217652696, 263741 },
512	{ 219196666, 264211 },
513	{ 220748520, 264682 },
514	{ 222308282, 265153 },
515	{ 223875978, 265625 },
516	{ 225451630, 266097 },
517	{ 227035265, 266569 },
518	{ 228626905, 267041 },
519	{ 230226576, 267514 },
520	{ 231834302, 267986 },
521	{ 233450107, 268460 },
522	{ 235074016, 268933 },
523	{ 236706054, 269407 },
524	{ 238346244, 269881 },
525	{ 239994613, 270355 },
526	{ 241651183, 270830 },
527	{ 243315981, 271305 }
528	};
529
530	/* Calculate the send rate as per section 3.1 of RFC3448
531
532	Returns send rate in bytes per second
533
534	Integer maths and lookups are used as not allowed floating point in kernel
535
536	The function for Xcalc as per section 3.1 of RFC3448 is:
537
538	X = s
539	-------------------------------------------------------------
540	Rsqrt(2bp/3) + (t_RTO (3sqrt(3bp/8) p * (1+32*p^2)))
541
542	where
543	X is the trasmit rate in bytes/second
544	s is the packet size in bytes
545	R is the round trip time in seconds
546	p is the loss event rate, between 0 and 1.0, of the number of loss events
547	as a fraction of the number of packets transmitted
548	t_RTO is the TCP retransmission timeout value in seconds
549	b is the number of packets acknowledged by a single TCP acknowledgement
550
551	we can assume that b = 1 and t_RTO is 4 * R. With this the equation becomes:
552
553	X = s
554	-----------------------------------------------------------------------
555	R * sqrt(2 * p / 3) + (12 * R * (sqrt(3 * p / 8) * p * (1 + 32 * p^2)))
556
557
558	which we can break down into:
559
560	X = s
561	--------
562	R * f(p)
563
564	where f(p) = sqrt(2 * p / 3) + (12 * sqrt(3 * p / 8) * p * (1 + 32 * p * p))
565
566	Function parameters:
567	s - bytes
568	R - RTT in usecs
569	p - loss rate (decimal fraction multiplied by 1,000,000)
570
571	Returns Xcalc in bytes per second
572
573	DON'T alter this code unless you run test cases against it as the code
574	has been manipulated to stop underflow/overlow.
575
576	*/
577	u32 tfrc_calc_x(u16 s, u32 R, u32 p)
578	{
579	int index;
580	u32 f;
581	u64 tmp1, tmp2;
582
583	if (p < TFRC_CALC_X_SPLIT)
584	index = (p / (TFRC_CALC_X_SPLIT / TFRC_CALC_X_ARRSIZE)) - 1;
585	else
586	index = (p / (1000000 / TFRC_CALC_X_ARRSIZE)) - 1;
587
588	if (index < 0)
589	/* p should be 0 unless there is a bug in my code */
590	index = 0;
591
592	if (R == 0)
593	R = 1; /* RTT can't be zero or else divide by zero */
594
595	BUG_ON(index >= TFRC_CALC_X_ARRSIZE);
596
597	if (p >= TFRC_CALC_X_SPLIT)
598	f = tfrc_calc_x_lookup[index][0];
599	else
600	f = tfrc_calc_x_lookup[index][1];
601
602	tmp1 = ((u64)s * 100000000);
603	tmp2 = ((u64)R * (u64)f);
604	do_div(tmp2, 10000);
605	do_div(tmp1, tmp2);
606	/* Don't alter above math unless you test due to overflow on 32 bit */
607
608	return (u32)tmp1;
609	}
610
611	EXPORT_SYMBOL_GPL(tfrc_calc_x);
612
613	/*
614	* args: fvalue - function value to match
615	* returns: p closest to that value
616	*
617	* both fvalue and p are multiplied by 1,000,000 to use ints
618	*/
619	u32 tfrc_calc_x_reverse_lookup(u32 fvalue)
620	{
621	int ctr = 0;
622	int small;
623
624	if (fvalue < tfrc_calc_x_lookup[0][1])
625	return 0;
626
627	if (fvalue <= tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][1])
628	small = 1;
629	else if (fvalue > tfrc_calc_x_lookup[TFRC_CALC_X_ARRSIZE - 1][0])
630	return 1000000;
631	else
632	small = 0;
633
634	while (fvalue > tfrc_calc_x_lookup[ctr][small])
635	ctr++;
636
637	if (small)
638	return TFRC_CALC_X_SPLIT * ctr / TFRC_CALC_X_ARRSIZE;
639	else
640	return 1000000 * ctr / TFRC_CALC_X_ARRSIZE;
641	}
642
643	EXPORT_SYMBOL_GPL(tfrc_calc_x_reverse_lookup);