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