Merge branch 'next'

6 files changed, 267 insertions, 153 deletions

diff --git a/lib/Kconfig b/lib/Kconfig
index 15019d2c65..ad0cd52edd 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -674,6 +674,13 @@ config GENERATE_SMBIOS_TABLE
 	  See also SMBIOS_SYSINFO which allows SMBIOS values to be provided in
 	  the devicetree.
 
+config LIB_RATIONAL
+	bool "enable continued fraction calculation routines"
+
+config SPL_LIB_RATIONAL
+	bool "enable continued fraction calculation routines for SPL"
+	depends on SPL
+
 endmenu
 
 config ASN1_COMPILER
diff --git a/lib/Makefile b/lib/Makefile
index b4795a62a0..881034f4ae 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -73,6 +73,8 @@ obj-$(CONFIG_$(SPL_)LZO) += lzo/
 obj-$(CONFIG_$(SPL_)LZMA) += lzma/
 obj-$(CONFIG_$(SPL_)LZ4) += lz4_wrapper.o
 
+obj-$(CONFIG_$(SPL_)LIB_RATIONAL) += rational.o
+
 obj-$(CONFIG_LIBAVB) += libavb/
 
 obj-$(CONFIG_$(SPL_TPL_)OF_LIBFDT) += libfdt/
diff --git a/lib/display_options.c b/lib/display_options.c
index cd48998b6d..c08a87e316 100644
--- a/lib/display_options.c
+++ b/lib/display_options.c
@@ -131,10 +131,11 @@ void print_size(uint64_t size, const char *s)
 	printf (" %ciB%s", c, s);
 }
 
-#define MAX_LINE_LENGTH_BYTES (64)
-#define DEFAULT_LINE_LENGTH_BYTES (16)
-int print_buffer(ulong addr, const void *data, uint width, uint count,
-		 uint linelen)
+#define MAX_LINE_LENGTH_BYTES		64
+#define DEFAULT_LINE_LENGTH_BYTES	16
+
+int hexdump_line(ulong addr, const void *data, uint width, uint count,
+		 uint linelen, char *out, int size)
 {
 	/* linebuf as a union causes proper alignment */
 	union linebuf {
@@ -143,62 +144,86 @@ int print_buffer(ulong addr, const void *data, uint width, uint count,
 		uint16_t us[MAX_LINE_LENGTH_BYTES/sizeof(uint16_t) + 1];
 		uint8_t  uc[MAX_LINE_LENGTH_BYTES/sizeof(uint8_t) + 1];
 	} lb;
+	uint thislinelen;
 	int i;
 	ulong x;
 
+	if (linelen * width > MAX_LINE_LENGTH_BYTES)
+		linelen = MAX_LINE_LENGTH_BYTES / width;
+	if (linelen < 1)
+		linelen = DEFAULT_LINE_LENGTH_BYTES / width;
+
+	/*
+	 * Check the size here so that we don't need to use snprintf(). This
+	 * helps to reduce code size
+	 */
+	if (size < HEXDUMP_MAX_BUF_LENGTH(linelen * width))
+		return -ENOSPC;
+
+	thislinelen = linelen;
+	out += sprintf(out, "%08lx:", addr);
+
+	/* check for overflow condition */
+	if (count < thislinelen)
+		thislinelen = count;
+
+	/* Copy from memory into linebuf and print hex values */
+	for (i = 0; i < thislinelen; i++) {
+		if (width == 4)
+			x = lb.ui[i] = *(volatile uint32_t *)data;
+		else if (MEM_SUPPORT_64BIT_DATA && width == 8)
+			x = lb.uq[i] = *(volatile ulong *)data;
+		else if (width == 2)
+			x = lb.us[i] = *(volatile uint16_t *)data;
+		else
+			x = lb.uc[i] = *(volatile uint8_t *)data;
+		if (CONFIG_IS_ENABLED(USE_TINY_PRINTF))
+			out += sprintf(out, " %x", (uint)x);
+		else
+			out += sprintf(out, " %0*lx", width * 2, x);
+		data += width;
+	}
+
+	/* fill line with whitespace for nice ASCII print */
+	for (i = 0; i < (linelen - thislinelen) * (width * 2 + 1); i++)
+		*out++ = ' ';
+
+	/* Print data in ASCII characters */
+	for (i = 0; i < thislinelen * width; i++) {
+		if (!isprint(lb.uc[i]) || lb.uc[i] >= 0x80)
+			lb.uc[i] = '.';
+	}
+	lb.uc[i] = '\0';
+	out += sprintf(out, "  %s", lb.uc);
+
+	return thislinelen;
+}
+
+int print_buffer(ulong addr, const void *data, uint width, uint count,
+		 uint linelen)
+{
 	if (linelen*width > MAX_LINE_LENGTH_BYTES)
 		linelen = MAX_LINE_LENGTH_BYTES / width;
 	if (linelen < 1)
 		linelen = DEFAULT_LINE_LENGTH_BYTES / width;
 
 	while (count) {
-		uint thislinelen = linelen;
-		printf("%08lx:", addr);
-
-		/* check for overflow condition */
-		if (count < thislinelen)
-			thislinelen = count;
-
-		/* Copy from memory into linebuf and print hex values */
-		for (i = 0; i < thislinelen; i++) {
-			if (width == 4)
-				x = lb.ui[i] = *(volatile uint32_t *)data;
-			else if (MEM_SUPPORT_64BIT_DATA && width == 8)
-				x = lb.uq[i] = *(volatile ulong *)data;
-			else if (width == 2)
-				x = lb.us[i] = *(volatile uint16_t *)data;
-			else
-				x = lb.uc[i] = *(volatile uint8_t *)data;
-			if (CONFIG_IS_ENABLED(USE_TINY_PRINTF))
-				printf(" %x", (uint)x);
-			else
-				printf(" %0*lx", width * 2, x);
-			data += width;
-		}
+		uint thislinelen;
+		char buf[HEXDUMP_MAX_BUF_LENGTH(width * linelen)];
 
-		while (thislinelen < linelen) {
-			/* fill line with whitespace for nice ASCII print */
-			for (i=0; i<width*2+1; i++)
-				puts(" ");
-			linelen--;
-		}
-
-		/* Print data in ASCII characters */
-		for (i = 0; i < thislinelen * width; i++) {
-			if (!isprint(lb.uc[i]) || lb.uc[i] >= 0x80)
-				lb.uc[i] = '.';
-		}
-		lb.uc[i] = '\0';
-		printf("    %s\n", lb.uc);
+		thislinelen = hexdump_line(addr, data, width, count, linelen,
+					   buf, sizeof(buf));
+		assert(thislinelen >= 0);
+		puts(buf);
+		putc('\n');
 
 		/* update references */
+		data += thislinelen * width;
 		addr += thislinelen * width;
 		count -= thislinelen;
 
-#ifndef CONFIG_SPL_BUILD
-		if (ctrlc())
-			return -1;
-#endif
+		if (!IS_ENABLED(CONFIG_SPL_BUILD) && ctrlc())
+			return -EINTR;
 	}
 
 	return 0;
diff --git a/lib/hexdump.c b/lib/hexdump.c
index a3f219a874..149c93ead8 100644
--- a/lib/hexdump.c
+++ b/lib/hexdump.c
@@ -10,45 +10,18 @@
 
 #include <common.h>
 #include <hexdump.h>
+#include <mapmem.h>
 #include <linux/ctype.h>
 #include <linux/compat.h>
 #include <linux/log2.h>
 #include <asm/unaligned.h>
 
+#define MAX_LINE_LENGTH_BYTES	64
+
 const char hex_asc[] = "0123456789abcdef";
 const char hex_asc_upper[] = "0123456789ABCDEF";
 
 #if CONFIG_IS_ENABLED(HEXDUMP)
-/**
- * hex_dump_to_buffer - convert a blob of data to "hex ASCII" in memory
- * @buf: data blob to dump
- * @len: number of bytes in the @buf
- * @rowsize: number of bytes to print per line; must be 16 or 32
- * @groupsize: number of bytes to print at a time (1, 2, 4, 8; default = 1)
- * @linebuf: where to put the converted data
- * @linebuflen: total size of @linebuf, including space for terminating NUL
- * @ascii: include ASCII after the hex output
- *
- * hex_dump_to_buffer() works on one "line" of output at a time, i.e.,
- * 16 or 32 bytes of input data converted to hex + ASCII output.
- *
- * Given a buffer of u8 data, hex_dump_to_buffer() converts the input data
- * to a hex + ASCII dump at the supplied memory location.
- * The converted output is always NUL-terminated.
- *
- * E.g.:
- *   hex_dump_to_buffer(frame->data, frame->len, 16, 1,
- *			linebuf, sizeof(linebuf), true);
- *
- * example output buffer:
- * 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f  @ABCDEFGHIJKLMNO
- *
- * Return:
- * The amount of bytes placed in the buffer without terminating NUL. If the
- * output was truncated, then the return value is the number of bytes
- * (excluding the terminating NUL) which would have been written to the final
- * string if enough space had been available.
- */
 int hex_dump_to_buffer(const void *buf, size_t len, int rowsize, int groupsize,
 		       char *linebuf, size_t linebuflen, bool ascii)
 {
@@ -59,8 +32,10 @@ int hex_dump_to_buffer(const void *buf, size_t len, int rowsize, int groupsize,
 	int ascii_column;
 	int ret;
 
-	if (rowsize != 16 && rowsize != 32)
+	if (!rowsize)
 		rowsize = 16;
+	else
+		rowsize = min(rowsize, MAX_LINE_LENGTH_BYTES);
 
 	if (len > rowsize)		/* limit to one line at a time */
 		len = rowsize;
@@ -150,44 +125,17 @@ overflow1:
 	return ascii ? ascii_column + len : (groupsize * 2 + 1) * ngroups - 1;
 }
 
-/**
- * print_hex_dump - print a text hex dump to syslog for a binary blob of data
- * @prefix_str: string to prefix each line with;
- *  caller supplies trailing spaces for alignment if desired
- * @prefix_type: controls whether prefix of an offset, address, or none
- *  is printed (%DUMP_PREFIX_OFFSET, %DUMP_PREFIX_ADDRESS, %DUMP_PREFIX_NONE)
- * @rowsize: number of bytes to print per line; must be 16 or 32
- * @groupsize: number of bytes to print at a time (1, 2, 4, 8; default = 1)
- * @buf: data blob to dump
- * @len: number of bytes in the @buf
- * @ascii: include ASCII after the hex output
- *
- * Given a buffer of u8 data, print_hex_dump() prints a hex + ASCII dump
- * to the stdio, with an optional leading prefix.
- *
- * print_hex_dump() works on one "line" of output at a time, i.e.,
- * 16 or 32 bytes of input data converted to hex + ASCII output.
- * print_hex_dump() iterates over the entire input @buf, breaking it into
- * "line size" chunks to format and print.
- *
- * E.g.:
- *   print_hex_dump("raw data: ", DUMP_PREFIX_ADDRESS, 16, 1, frame->data,
- *                  frame->len, true);
- *
- * Example output using %DUMP_PREFIX_OFFSET and 1-byte mode:
- * 0009ab42: 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f  @ABCDEFGHIJKLMNO
- * Example output using %DUMP_PREFIX_ADDRESS and 4-byte mode:
- * ffffffff88089af0: 73727170 77767574 7b7a7978 7f7e7d7c  pqrstuvwxyz{|}~.
- */
-void print_hex_dump(const char *prefix_str, int prefix_type, int rowsize,
-		    int groupsize, const void *buf, size_t len, bool ascii)
+int print_hex_dump(const char *prefix_str, int prefix_type, int rowsize,
+		   int groupsize, const void *buf, size_t len, bool ascii)
 {
 	const u8 *ptr = buf;
 	int i, linelen, remaining = len;
-	char linebuf[32 * 3 + 2 + 32 + 1];
+	char linebuf[MAX_LINE_LENGTH_BYTES * 3 + 2 + MAX_LINE_LENGTH_BYTES + 1];
 
-	if (rowsize != 16 && rowsize != 32)
+	if (!rowsize)
 		rowsize = 16;
+	else
+		rowsize = min(rowsize, MAX_LINE_LENGTH_BYTES);
 
 	for (i = 0; i < len; i += rowsize) {
 		linelen = min(remaining, rowsize);
@@ -198,7 +146,9 @@ void print_hex_dump(const char *prefix_str, int prefix_type, int rowsize,
 
 		switch (prefix_type) {
 		case DUMP_PREFIX_ADDRESS:
-			printf("%s%p: %s\n", prefix_str, ptr + i, linebuf);
+			printf("%s%0*lx: %s\n", prefix_str,
+			       IS_ENABLED(CONFIG_PHYS_64BIT) ? 16 : 8,
+			       (ulong)map_to_sysmem(ptr) + i, linebuf);
 			break;
 		case DUMP_PREFIX_OFFSET:
 			printf("%s%.8x: %s\n", prefix_str, i, linebuf);
@@ -207,21 +157,13 @@ void print_hex_dump(const char *prefix_str, int prefix_type, int rowsize,
 			printf("%s%s\n", prefix_str, linebuf);
 			break;
 		}
+		if (!IS_ENABLED(CONFIG_SPL_BUILD) && ctrlc())
+			return -EINTR;
 	}
+
+	return 0;
 }
 
-/**
- * print_hex_dump_bytes - shorthand form of print_hex_dump() with default params
- * @prefix_str: string to prefix each line with;
- *  caller supplies trailing spaces for alignment if desired
- * @prefix_type: controls whether prefix of an offset, address, or none
- *  is printed (%DUMP_PREFIX_OFFSET, %DUMP_PREFIX_ADDRESS, %DUMP_PREFIX_NONE)
- * @buf: data blob to dump
- * @len: number of bytes in the @buf
- *
- * Calls print_hex_dump(), rowsize of 16, groupsize of 1,
- * and ASCII output included.
- */
 void print_hex_dump_bytes(const char *prefix_str, int prefix_type,
 			  const void *buf, size_t len)
 {
@@ -232,14 +174,14 @@ void print_hex_dump_bytes(const char *prefix_str, int prefix_type,
  * Some code in U-Boot copy-pasted from Linux kernel uses both
  * functions below so to keep stuff compilable we keep these stubs here.
  */
-void print_hex_dump(const char *prefix_str, int prefix_type,
-				  int rowsize, int groupsize, const void *buf,
-				  size_t len, bool ascii)
+int print_hex_dump(const char *prefix_str, int prefix_type, int rowsize,
+		   int groupsize, const void *buf, size_t len, bool ascii)
 {
+	return -ENOSYS;
 }
 
 void print_hex_dump_bytes(const char *prefix_str, int prefix_type,
-					const void *buf, size_t len)
+			  const void *buf, size_t len)
 {
 }
 #endif /* CONFIG_HEXDUMP */
diff --git a/lib/lmb.c b/lib/lmb.c
index c08c4d942b..7bd1255f7a 100644
--- a/lib/lmb.c
+++ b/lib/lmb.c
@@ -14,28 +14,32 @@
 
 #define LMB_ALLOC_ANYWHERE	0
 
-void lmb_dump_all_force(struct lmb *lmb)
+static void lmb_dump_region(struct lmb_region *rgn, char *name)
 {
-	unsigned long i;
+	unsigned long long base, size, end;
+	enum lmb_flags flags;
+	int i;
 
-	printf("lmb_dump_all:\n");
-	printf("    memory.cnt		   = 0x%lx\n", lmb->memory.cnt);
-	for (i = 0; i < lmb->memory.cnt; i++) {
-		printf("    memory.reg[0x%lx].base   = 0x%llx\n", i,
-		       (unsigned long long)lmb->memory.region[i].base);
-		printf("		   .size   = 0x%llx\n",
-		       (unsigned long long)lmb->memory.region[i].size);
-	}
+	printf(" %s.cnt  = 0x%lx\n", name, rgn->cnt);
 
-	printf("\n    reserved.cnt	   = 0x%lx\n", lmb->reserved.cnt);
-	for (i = 0; i < lmb->reserved.cnt; i++) {
-		printf("    reserved.reg[0x%lx].base = 0x%llx\n", i,
-		       (unsigned long long)lmb->reserved.region[i].base);
-		printf("		     .size = 0x%llx\n",
-		       (unsigned long long)lmb->reserved.region[i].size);
+	for (i = 0; i < rgn->cnt; i++) {
+		base = rgn->region[i].base;
+		size = rgn->region[i].size;
+		end = base + size - 1;
+		flags = rgn->region[i].flags;
+
+		printf(" %s[%d]\t[0x%llx-0x%llx], 0x%08llx bytes flags: %x\n",
+		       name, i, base, end, size, flags);
 	}
 }
 
+void lmb_dump_all_force(struct lmb *lmb)
+{
+	printf("lmb_dump_all:\n");
+	lmb_dump_region(&lmb->memory, "memory");
+	lmb_dump_region(&lmb->reserved, "reserved");
+}
+
 void lmb_dump_all(struct lmb *lmb)
 {
 #ifdef DEBUG
@@ -81,6 +85,7 @@ static void lmb_remove_region(struct lmb_region *rgn, unsigned long r)
 	for (i = r; i < rgn->cnt - 1; i++) {
 		rgn->region[i].base = rgn->region[i + 1].base;
 		rgn->region[i].size = rgn->region[i + 1].size;
+		rgn->region[i].flags = rgn->region[i + 1].flags;
 	}
 	rgn->cnt--;
 }
@@ -144,7 +149,8 @@ void lmb_init_and_reserve_range(struct lmb *lmb, phys_addr_t base,
 }
 
 /* This routine called with relocation disabled. */
-static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t size)
+static long lmb_add_region_flags(struct lmb_region *rgn, phys_addr_t base,
+				 phys_size_t size, enum lmb_flags flags)
 {
 	unsigned long coalesced = 0;
 	long adjacent, i;
@@ -152,6 +158,7 @@ static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t
 	if (rgn->cnt == 0) {
 		rgn->region[0].base = base;
 		rgn->region[0].size = size;
+		rgn->region[0].flags = flags;
 		rgn->cnt = 1;
 		return 0;
 	}
@@ -160,18 +167,27 @@ static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t
 	for (i = 0; i < rgn->cnt; i++) {
 		phys_addr_t rgnbase = rgn->region[i].base;
 		phys_size_t rgnsize = rgn->region[i].size;
+		phys_size_t rgnflags = rgn->region[i].flags;
 
-		if ((rgnbase == base) && (rgnsize == size))
-			/* Already have this region, so we're done */
-			return 0;
+		if (rgnbase == base && rgnsize == size) {
+			if (flags == rgnflags)
+				/* Already have this region, so we're done */
+				return 0;
+			else
+				return -1; /* regions with new flags */
+		}
 
 		adjacent = lmb_addrs_adjacent(base, size, rgnbase, rgnsize);
 		if (adjacent > 0) {
+			if (flags != rgnflags)
+				break;
 			rgn->region[i].base -= size;
 			rgn->region[i].size += size;
 			coalesced++;
 			break;
 		} else if (adjacent < 0) {
+			if (flags != rgnflags)
+				break;
 			rgn->region[i].size += size;
 			coalesced++;
 			break;
@@ -182,8 +198,10 @@ static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t
 	}
 
 	if ((i < rgn->cnt - 1) && lmb_regions_adjacent(rgn, i, i + 1)) {
-		lmb_coalesce_regions(rgn, i, i + 1);
-		coalesced++;
+		if (rgn->region[i].flags == rgn->region[i + 1].flags) {
+			lmb_coalesce_regions(rgn, i, i + 1);
+			coalesced++;
+		}
 	}
 
 	if (coalesced)
@@ -196,9 +214,11 @@ static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t
 		if (base < rgn->region[i].base) {
 			rgn->region[i + 1].base = rgn->region[i].base;
 			rgn->region[i + 1].size = rgn->region[i].size;
+			rgn->region[i + 1].flags = rgn->region[i].flags;
 		} else {
 			rgn->region[i + 1].base = base;
 			rgn->region[i + 1].size = size;
+			rgn->region[i + 1].flags = flags;
 			break;
 		}
 	}
@@ -206,6 +226,7 @@ static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t
 	if (base < rgn->region[0].base) {
 		rgn->region[0].base = base;
 		rgn->region[0].size = size;
+		rgn->region[0].flags = flags;
 	}
 
 	rgn->cnt++;
@@ -213,6 +234,12 @@ static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base, phys_size_t
 	return 0;
 }
 
+static long lmb_add_region(struct lmb_region *rgn, phys_addr_t base,
+			   phys_size_t size)
+{
+	return lmb_add_region_flags(rgn, base, size, LMB_NONE);
+}
+
 /* This routine may be called with relocation disabled. */
 long lmb_add(struct lmb *lmb, phys_addr_t base, phys_size_t size)
 {
@@ -267,14 +294,21 @@ long lmb_free(struct lmb *lmb, phys_addr_t base, phys_size_t size)
 	 * beginging of the hole and add the region after hole.
 	 */
 	rgn->region[i].size = base - rgn->region[i].base;
-	return lmb_add_region(rgn, end + 1, rgnend - end);
+	return lmb_add_region_flags(rgn, end + 1, rgnend - end,
+				    rgn->region[i].flags);
 }
 
-long lmb_reserve(struct lmb *lmb, phys_addr_t base, phys_size_t size)
+long lmb_reserve_flags(struct lmb *lmb, phys_addr_t base, phys_size_t size,
+		       enum lmb_flags flags)
 {
 	struct lmb_region *_rgn = &(lmb->reserved);
 
-	return lmb_add_region(_rgn, base, size);
+	return lmb_add_region_flags(_rgn, base, size, flags);
+}
+
+long lmb_reserve(struct lmb *lmb, phys_addr_t base, phys_size_t size)
+{
+	return lmb_reserve_flags(lmb, base, size, LMB_NONE);
 }
 
 static long lmb_overlaps_region(struct lmb_region *rgn, phys_addr_t base,
@@ -409,7 +443,7 @@ phys_size_t lmb_get_free_size(struct lmb *lmb, phys_addr_t addr)
 	return 0;
 }
 
-int lmb_is_reserved(struct lmb *lmb, phys_addr_t addr)
+int lmb_is_reserved_flags(struct lmb *lmb, phys_addr_t addr, int flags)
 {
 	int i;
 
@@ -417,11 +451,16 @@ int lmb_is_reserved(struct lmb *lmb, phys_addr_t addr)
 		phys_addr_t upper = lmb->reserved.region[i].base +
 			lmb->reserved.region[i].size - 1;
 		if ((addr >= lmb->reserved.region[i].base) && (addr <= upper))
-			return 1;
+			return (lmb->reserved.region[i].flags & flags) == flags;
 	}
 	return 0;
 }
 
+int lmb_is_reserved(struct lmb *lmb, phys_addr_t addr)
+{
+	return lmb_is_reserved_flags(lmb, addr, LMB_NONE);
+}
+
 __weak void board_lmb_reserve(struct lmb *lmb)
 {
 	/* please define platform specific board_lmb_reserve() */
diff --git a/lib/rational.c b/lib/rational.c
new file mode 100644
index 0000000000..316db3b590
--- /dev/null
+++ b/lib/rational.c
@@ -0,0 +1,99 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * rational fractions
+ *
+ * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com>
+ * Copyright (C) 2019 Trent Piepho <tpiepho@gmail.com>
+ *
+ * helper functions when coping with rational numbers
+ */
+
+#include <linux/rational.h>
+#include <linux/compiler.h>
+#include <linux/kernel.h>
+
+/*
+ * calculate best rational approximation for a given fraction
+ * taking into account restricted register size, e.g. to find
+ * appropriate values for a pll with 5 bit denominator and
+ * 8 bit numerator register fields, trying to set up with a
+ * frequency ratio of 3.1415, one would say:
+ *
+ * rational_best_approximation(31415, 10000,
+ *		(1 << 8) - 1, (1 << 5) - 1, &n, &d);
+ *
+ * you may look at given_numerator as a fixed point number,
+ * with the fractional part size described in given_denominator.
+ *
+ * for theoretical background, see:
+ * http://en.wikipedia.org/wiki/Continued_fraction
+ */
+
+void rational_best_approximation(
+	unsigned long given_numerator, unsigned long given_denominator,
+	unsigned long max_numerator, unsigned long max_denominator,
+	unsigned long *best_numerator, unsigned long *best_denominator)
+{
+	/* n/d is the starting rational, which is continually
+	 * decreased each iteration using the Euclidean algorithm.
+	 *
+	 * dp is the value of d from the prior iteration.
+	 *
+	 * n2/d2, n1/d1, and n0/d0 are our successively more accurate
+	 * approximations of the rational.  They are, respectively,
+	 * the current, previous, and two prior iterations of it.
+	 *
+	 * a is current term of the continued fraction.
+	 */
+	unsigned long n, d, n0, d0, n1, d1, n2, d2;
+	n = given_numerator;
+	d = given_denominator;
+	n0 = d1 = 0;
+	n1 = d0 = 1;
+
+	for (;;) {
+		unsigned long dp, a;
+
+		if (d == 0)
+			break;
+		/* Find next term in continued fraction, 'a', via
+		 * Euclidean algorithm.
+		 */
+		dp = d;
+		a = n / d;
+		d = n % d;
+		n = dp;
+
+		/* Calculate the current rational approximation (aka
+		 * convergent), n2/d2, using the term just found and
+		 * the two prior approximations.
+		 */
+		n2 = n0 + a * n1;
+		d2 = d0 + a * d1;
+
+		/* If the current convergent exceeds the maxes, then
+		 * return either the previous convergent or the
+		 * largest semi-convergent, the final term of which is
+		 * found below as 't'.
+		 */
+		if ((n2 > max_numerator) || (d2 > max_denominator)) {
+			unsigned long t = min((max_numerator - n0) / n1,
+					      (max_denominator - d0) / d1);
+
+			/* This tests if the semi-convergent is closer
+			 * than the previous convergent.
+			 */
+			if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
+				n1 = n0 + t * n1;
+				d1 = d0 + t * d1;
+			}
+			break;
+		}
+		n0 = n1;
+		n1 = n2;
+		d0 = d1;
+		d1 = d2;
+	}
+	*best_numerator = n1;
+	*best_denominator = d1;
+}