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