aboutsummaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
authorOskar Schirmer <os@emlix.com>2009-06-11 09:51:15 -0400
committerLinus Torvalds <torvalds@linux-foundation.org>2009-06-11 11:51:08 -0400
commit8759ef32d992fc6c0bcbe40fca7aa302190918a5 (patch)
tree316df64d3456597bf7f8ef7508654c82faf6a5fe /lib
parent9f322ad064f9210e7d472dfe77e702274d5c9dba (diff)
lib: isolate rational fractions helper function
Provide a helper function to determine optimum numerator denominator value pairs taking into account restricted register size. Useful especially with PLL and other clock configurations. Signed-off-by: Oskar Schirmer <os@emlix.com> Signed-off-by: Alan Cox <alan@linux.intel.com> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib')
-rw-r--r--lib/Kconfig3
-rw-r--r--lib/Makefile1
-rw-r--r--lib/rational.c62
3 files changed, 66 insertions, 0 deletions
diff --git a/lib/Kconfig b/lib/Kconfig
index 8ade0a7a91e0..9960be04cbbe 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -10,6 +10,9 @@ menu "Library routines"
10config BITREVERSE 10config BITREVERSE
11 tristate 11 tristate
12 12
13config RATIONAL
14 boolean
15
13config GENERIC_FIND_FIRST_BIT 16config GENERIC_FIND_FIRST_BIT
14 bool 17 bool
15 18
diff --git a/lib/Makefile b/lib/Makefile
index 33a40e40e3ee..1f6edefebffe 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -50,6 +50,7 @@ ifneq ($(CONFIG_HAVE_DEC_LOCK),y)
50endif 50endif
51 51
52obj-$(CONFIG_BITREVERSE) += bitrev.o 52obj-$(CONFIG_BITREVERSE) += bitrev.o
53obj-$(CONFIG_RATIONAL) += rational.o
53obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o 54obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o
54obj-$(CONFIG_CRC16) += crc16.o 55obj-$(CONFIG_CRC16) += crc16.o
55obj-$(CONFIG_CRC_T10DIF)+= crc-t10dif.o 56obj-$(CONFIG_CRC_T10DIF)+= crc-t10dif.o
diff --git a/lib/rational.c b/lib/rational.c
new file mode 100644
index 000000000000..b3c099b5478e
--- /dev/null
+++ b/lib/rational.c
@@ -0,0 +1,62 @@
1/*
2 * rational fractions
3 *
4 * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <os@emlix.com>
5 *
6 * helper functions when coping with rational numbers
7 */
8
9#include <linux/rational.h>
10
11/*
12 * calculate best rational approximation for a given fraction
13 * taking into account restricted register size, e.g. to find
14 * appropriate values for a pll with 5 bit denominator and
15 * 8 bit numerator register fields, trying to set up with a
16 * frequency ratio of 3.1415, one would say:
17 *
18 * rational_best_approximation(31415, 10000,
19 * (1 << 8) - 1, (1 << 5) - 1, &n, &d);
20 *
21 * you may look at given_numerator as a fixed point number,
22 * with the fractional part size described in given_denominator.
23 *
24 * for theoretical background, see:
25 * http://en.wikipedia.org/wiki/Continued_fraction
26 */
27
28void rational_best_approximation(
29 unsigned long given_numerator, unsigned long given_denominator,
30 unsigned long max_numerator, unsigned long max_denominator,
31 unsigned long *best_numerator, unsigned long *best_denominator)
32{
33 unsigned long n, d, n0, d0, n1, d1;
34 n = given_numerator;
35 d = given_denominator;
36 n0 = d1 = 0;
37 n1 = d0 = 1;
38 for (;;) {
39 unsigned long t, a;
40 if ((n1 > max_numerator) || (d1 > max_denominator)) {
41 n1 = n0;
42 d1 = d0;
43 break;
44 }
45 if (d == 0)
46 break;
47 t = d;
48 a = n / d;
49 d = n % d;
50 n = t;
51 t = n0 + a * n1;
52 n0 = n1;
53 n1 = t;
54 t = d0 + a * d1;
55 d0 = d1;
56 d1 = t;
57 }
58 *best_numerator = n1;
59 *best_denominator = d1;
60}
61
62EXPORT_SYMBOL(rational_best_approximation);