memtest86+: Initial commit of 5.01 codebase

This is the initial commit of memtest86+

The tarball was downloaded from www.memtest.org on Feb 24,2016
and unpacked.  No changes have yet been made.
Version: Memtest86+ V5.01 (27/09/2013)

sha1sum of tarball:
eb4b6d70114db3c9ed320785da44c0ba8349c10c *memtest86+-5.01.tar.gz

Change-Id: I1ed925c85925ff5d98e61a11ad1dc6b3c44f79b7
Signed-off-by: Martin Roth <martinroth@google.com>
Reviewed-on: https://review.coreboot.org/13818
Reviewed-by: Stefan Reinauer <stefan.reinauer@coreboot.org>
Tested-by: Stefan Reinauer <stefan.reinauer@coreboot.org>
diff --git a/patn.c b/patn.c
new file mode 100644
index 0000000..0c5b490
--- /dev/null
+++ b/patn.c
@@ -0,0 +1,144 @@
+/* Pattern extension for memtest86
+ *
+ * Generates patterns for the Linux kernel's BadRAM extension that avoids
+ * allocation of faulty pages.
+ *
+ * Released under version 2 of the Gnu Public License.
+ *
+ * By Rick van Rein, vanrein@zonnet.nl
+ * ----------------------------------------------------
+ * MemTest86+ V1.60 Specific code (GPL V2.0)
+ * By Samuel DEMEULEMEESTER, sdemeule@memtest.org
+ * http://www.x86-secret.com - http://www.memtest.org 
+ */
+
+
+#include "test.h"
+
+
+/*
+ * DEFAULT_MASK covers a longword, since that is the testing granularity.
+ */
+#define DEFAULT_MASK ((~0L) << 2)
+
+
+/* extern struct vars *v; */
+
+
+/* What it does:
+ *  - Keep track of a number of BadRAM patterns in an array;
+ *  - Combine new faulty addresses with it whenever possible;
+ *  - Keep masks as selective as possible by minimising resulting faults;
+ *  - Print a new pattern only when the pattern array is changed.
+ */
+
+#define COMBINE_MASK(a,b,c,d) ((a & b & c & d) | (~a & b & ~c & d))
+
+/* Combine two adr/mask pairs to one adr/mask pair.
+ */
+void combine (ulong adr1, ulong mask1, ulong adr2, ulong mask2,
+		ulong *adr, ulong *mask) {
+
+	*mask = COMBINE_MASK (adr1, mask1, adr2, mask2);
+
+	*adr  = adr1 | adr2;
+	*adr &= *mask;	// Normalise, no fundamental need for this
+}
+
+/* Count the number of addresses covered with a mask.
+ */
+ulong addresses (ulong mask) {
+	ulong ctr=1;
+	int i=32;
+	while (i-- > 0) {
+		if (! (mask & 1)) {
+			ctr += ctr;
+		}
+		mask >>= 1;
+	}
+	return ctr;
+}
+
+/* Count how much more addresses would be covered by adr1/mask1 when combined
+ * with adr2/mask2.
+ */
+ulong combicost (ulong adr1, ulong mask1, ulong adr2, ulong mask2) {
+	ulong cost1=addresses (mask1);
+	ulong tmp, mask;
+	combine (adr1, mask1, adr2, mask2, &tmp, &mask);
+	return addresses (mask) - cost1;
+}
+
+/* Find the cheapest array index to extend with the given adr/mask pair.
+ * Return -1 if nothing below the given minimum cost can be found.
+ */
+int cheapindex (ulong adr1, ulong mask1, ulong mincost) {
+	int i=v->numpatn;
+	int idx=-1;
+	while (i-- > 0) {
+		ulong tmpcost=combicost(v->patn[i].adr, v->patn[i].mask, adr1, mask1);
+		if (tmpcost < mincost) {
+			mincost=tmpcost;
+			idx=i;
+		}
+	}
+	return idx;
+}
+
+/* Try to find a relocation index for idx if it costs nothing.
+ * Return -1 if no such index exists.
+ */
+int relocateidx (int idx) {
+	ulong adr =v->patn[idx].adr;
+	ulong mask=v->patn[idx].mask;
+	int new;
+	v->patn[idx].adr ^= ~0L;	// Never select idx
+	new=cheapindex (adr, mask, 1+addresses (mask));
+	v->patn[idx].adr = adr;
+	return new;
+}
+
+/* Relocate the given index idx only if free of charge.
+ * This is useful to combine to `neighbouring' sections to integrate.
+ * Inspired on the Buddy memalloc principle in the Linux kernel.
+ */
+void relocateiffree (int idx) {
+	int newidx=relocateidx (idx);
+	if (newidx>=0) {
+		ulong cadr, cmask;
+		combine (v->patn [newidx].adr, v->patn[newidx].mask,
+		         v->patn [   idx].adr, v->patn[   idx].mask,
+			 &cadr, &cmask);
+		v->patn[newidx].adr =cadr;
+		v->patn[newidx].mask=cmask;
+		if (idx < --v->numpatn) {
+			v->patn[idx].adr =v->patn[v->numpatn].adr;
+			v->patn[idx].mask=v->patn[v->numpatn].mask;
+		}
+		relocateiffree (newidx);
+	}
+}
+
+/* Insert a single faulty address in the pattern array.
+ * Return 1 only if the array was changed.
+ */
+int insertaddress (ulong adr) {
+	if (cheapindex (adr, DEFAULT_MASK, 1L) != -1)
+		return 0;
+
+	if (v->numpatn < BADRAM_MAXPATNS) {
+		v->patn[v->numpatn].adr =adr;
+		v->patn[v->numpatn].mask=DEFAULT_MASK;
+		v->numpatn++;
+		relocateiffree (v->numpatn-1);
+	} else {
+		int idx=cheapindex (adr, DEFAULT_MASK, ~0L);
+		ulong cadr, cmask;
+		combine (v->patn [idx].adr, v->patn[idx].mask,
+		         adr, DEFAULT_MASK, &cadr, &cmask);
+		v->patn[idx].adr =cadr;
+		v->patn[idx].mask=cmask;
+		relocateiffree (idx);
+	}
+	return 1;
+}