MPPA - added merge sort + corrected bug in insertion + testing them together

10 files changed, 205 insertions, 38 deletions

diff --git a/test/mppa/lib/prng.c b/test/mppa/lib/prng.c
index dfa97834..c902cc3e 100644
--- a/test/mppa/lib/prng.c
+++ b/test/mppa/lib/prng.c
@@ -9,11 +9,13 @@
 static uint64_t current;
 
 void srand(uint64_t seed){
-    seed = current;
+    //seed = current;
+    current=100;
 }
 
 uint64_t randlong(void){
-    return (current = MULTIPLIER * current + INCREMENT);
+    //return (current = MULTIPLIER * current + INCREMENT);
+    return current--;
 }
 
 #ifdef __UNIT_TEST_PRNG__
diff --git a/test/mppa/sort/Makefile b/test/mppa/sort/Makefile
index 1f4a0d51..ce86017d 100644
--- a/test/mppa/sort/Makefile
+++ b/test/mppa/sort/Makefile
@@ -1,35 +1,61 @@
 PRNG=../lib/prng.c
 
-insertion-test-x86: insertion.c $(PRNG)
-	gcc -g -D__UNIT_TEST_INSERTION__ -O2 -std=c99 $^ -o $@
+ALL= insertion-test-x86 insertion-test-k1c\
+     selection-test-x86 selection-test-k1c\
+     merge-test-x86     merge-test-k1c\
+     test-x86           test-k1c
 
-insertion-test-k1c: insertion.c $(PRNG)
-	k1-gcc -D__UNIT_TEST_INSERTION__ -O2 -std=c99 $^ -o $@
+all: $(ALL)
 
-selection-test-x86: selection.c $(PRNG)
-	gcc -g -D__UNIT_TEST_SELECTION__ -O2 -std=c99 $^ -o $@
+%-test-x86: %.c $(PRNG)
+	gcc -g -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ -O2 -std=c99 $^ -o $@
 
-selection-test-k1c: selection.c $(PRNG)
-	k1-gcc -D__UNIT_TEST_SELECTION__ -O2 -std=c99 $^ -o $@
+%-test-k1c: %.c $(PRNG)
+	k1-gcc -g -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ -O2 -std=c99 $^ -o $@
+
+test-x86: selection.c merge.c insertion.c test.c $(PRNG)
+	gcc -g -O2 -std=c99 $^ -o $@
+
+test-k1c: selection.c merge.c insertion.c test.c $(PRNG)
+	k1-gcc -g -O2 -std=c99 $^ -o $@
 
 .PHONY:
 unittest: unittest-x86 unittest-k1c
 
 .PHONY:
-unittest-x86: insertion-test-x86 selection-test-x86
+check: check-x86 check-k1c
+
+.PHONY:
+check-x86: test-x86
+	@if ! ./$<; then\
+		>&2 echo "ERROR x86: $< failed";\
+	else\
+		echo "x86: Test $< succeeded";\
+	fi
+
+.PHONY:
+check-k1c: test-k1c
+	@if ! k1-cluster -- ./$<; then\
+		>&2 echo "ERROR k1c: $< failed";\
+	else\
+		echo "k1c: Test $< succeeded";\
+	fi
+
+.PHONY:
+unittest-x86: insertion-test-x86 selection-test-x86 merge-test-x86
 	@for test in $^; do\
 		if ! ./$$test; then\
-			>&2 echo "ERROR: $$test failed";\
+			>&2 echo "ERROR x86: $$test failed";\
 		else\
 			echo "x86: Test $$test Succeeded";\
 		fi;\
 	done
 
 .PHONY:
-unittest-k1c: insertion-test-k1c selection-test-k1c
+unittest-k1c: insertion-test-k1c selection-test-k1c merge-test-k1c
 	@for test in $^; do\
 		if ! k1-cluster -- ./$$test; then\
-			>&2 echo "ERROR: $$test failed";\
+			>&2 echo "ERROR k1c: $$test failed";\
 		else\
 			echo "k1c: Test $$test Succeeded";\
 		fi;\
@@ -37,4 +63,4 @@ unittest-k1c: insertion-test-k1c selection-test-k1c
 
 .PHONY:
 clean:
-	rm -f insertion-test-x86 insertion-test-k1c selection-test-k1c selection-test-x86
+	rm -f $(ALL)
diff --git a/test/mppa/sort/insertion.c b/test/mppa/sort/insertion.c
index 2c6065e7..88093b64 100644
--- a/test/mppa/sort/insertion.c
+++ b/test/mppa/sort/insertion.c
@@ -1,25 +1,31 @@
 #include "../lib/prng.h"
 #include "../lib/types.h"
 
-void swap(uint64_t *a, uint64_t *b){
+#ifdef __UNIT_TEST_INSERTION__
+#define SIZE 100
+#else
+#include "test.h"
+#endif
+
+void swap_ins(uint64_t *a, uint64_t *b){
     uint64_t tmp = *a;
     *a = *b;
     *b = tmp;
 }
 
-int insert_sort(uint64_t *res, const uint64_t *T, int size){
-    if (size <= 0)
+int insert_sort(uint64_t *res, const uint64_t *T){
+    if (SIZE <= 0)
         return -1;
 
-    for (int i = 0 ; i < size ; i++)
+    for (int i = 0 ; i < SIZE ; i++)
         res[i] = T[i];
 
-    for (int i = 0 ; i < size-1 ; i++){
+    for (int i = 0 ; i < SIZE-1 ; i++){
         if (res[i] > res[i+1]){
-            swap(&res[i], &res[i+1]);
-            for (int j = i ; j > 1 ; j--)
+            swap_ins(&res[i], &res[i+1]);
+            for (int j = i ; j > 0 ; j--)
                 if (res[j-1] > res[j])
-                    swap(&res[j-1], &res[j]);
+                    swap_ins(&res[j-1], &res[j]);
         }
     }
 
@@ -27,8 +33,6 @@ int insert_sort(uint64_t *res, const uint64_t *T, int size){
 }
 
 #ifdef __UNIT_TEST_INSERTION__
-#define SIZE 100
-
 int main(void){
     uint64_t T[SIZE];
     uint64_t res[SIZE];
@@ -38,7 +42,7 @@ int main(void){
         T[i] = randlong();
 
     /* Sorting the table */
-    if (insert_sort(res, T, SIZE) < 0) return -1;
+    if (insert_sort(res, T) < 0) return -1;
 
     /* Computing max(T) */
     uint64_t max = T[0];
diff --git a/test/mppa/sort/insertion.h b/test/mppa/sort/insertion.h
index 135b3bc1..6e37c5fe 100644
--- a/test/mppa/sort/insertion.h
+++ b/test/mppa/sort/insertion.h
@@ -1,6 +1,6 @@
 #ifndef __INSERTION_H__
 #define __INSERTION_H__
 
-int insert_sort(uint64_t *res, const uint64_t *T, int size);
+int insert_sort(uint64_t *res, const uint64_t *T);
 
 #endif // __INSERTION_H__
diff --git a/test/mppa/sort/merge.c b/test/mppa/sort/merge.c
new file mode 100644
index 00000000..63f662ac
--- /dev/null
+++ b/test/mppa/sort/merge.c
@@ -0,0 +1,85 @@
+#include "../lib/prng.h"
+#include "../lib/types.h"
+
+//https://en.wikipedia.org/wiki/Merge_sort
+
+#ifdef __UNIT_TEST_MERGE__
+#define SIZE 100
+#else
+#include "test.h"
+#endif
+
+int min(int a, int b){
+    return (a < b)?a:b;
+}
+
+void BottomUpMerge(const uint64_t *A, int iLeft, int iRight, int iEnd, int64_t *B)
+{
+    int i = iLeft, j = iRight;
+    for (int k = iLeft; k < iEnd; k++) {
+        if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
+            B[k] = A[i];
+            i = i + 1;
+        } else {
+            B[k] = A[j];
+            j = j + 1;    
+        }
+    } 
+}
+
+void CopyArray(uint64_t *to, const uint64_t *from)
+{
+    const int n = SIZE;
+
+    for(int i = 0; i < n; i++)
+        to[i] = from[i];
+}
+
+void BottomUpMergeSort(uint64_t *A, uint64_t *B)
+{
+    const int n = SIZE;
+
+    for (int width = 1; width < n; width = 2 * width)
+    {
+        for (int i = 0; i < n; i = i + 2 * width)
+        {
+            BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
+        }
+        CopyArray(A, B);
+    }
+}
+
+int merge_sort(uint64_t *res, const uint64_t *T){
+    if (SIZE <= 0)
+        return -1;
+
+    uint64_t B[SIZE];
+    uint64_t *A = res;
+    for (int i = 0 ; i < SIZE ; i++)
+        A[i] = T[i];
+
+    BottomUpMergeSort(A, B);
+}
+
+#ifdef __UNIT_TEST_MERGE__
+int main(void){
+    uint64_t T[SIZE];
+    uint64_t res[SIZE];
+    srand(42);
+
+    for (int i = 0 ; i < SIZE ; i++)
+        T[i] = randlong();
+
+    /* Sorting the table */
+    if (merge_sort(res, T) < 0) return -1;
+
+    /* Computing max(T) */
+    uint64_t max = T[0];
+    for (int i = 1 ; i < SIZE ; i++)
+        if (T[i] > max)
+            max = T[i];
+
+    /* We should have: max(T) == res[SIZE] */
+    return !(max == res[SIZE-1]);
+}
+#endif // __UNIT_TEST_MERGE__
diff --git a/test/mppa/sort/merge.h b/test/mppa/sort/merge.h
new file mode 100644
index 00000000..439ce64a
--- /dev/null
+++ b/test/mppa/sort/merge.h
@@ -0,0 +1,7 @@
+#ifndef __MERGE_H__
+#define __MERGE_H__
+
+int merge_sort(uint64_t *res, const uint64_t *T);
+
+#endif // __MERGE_H__
+
diff --git a/test/mppa/sort/selection.c b/test/mppa/sort/selection.c
index 432bbf49..89bc2c65 100644
--- a/test/mppa/sort/selection.c
+++ b/test/mppa/sort/selection.c
@@ -1,36 +1,40 @@
 #include "../lib/prng.h"
 #include "../lib/types.h"
 
-void swap(uint64_t *a, uint64_t *b){
+#ifdef __UNIT_TEST_SELECTION__
+#define SIZE 100
+#else
+#include "test.h"
+#endif
+
+void swap_sel(uint64_t *a, uint64_t *b){
     uint64_t tmp = *a;
     *a = *b;
     *b = tmp;
 }
 
-int selection_sort(uint64_t *res, const uint64_t *T, int size){
-    if (size <= 0)
+int select_sort(uint64_t *res, const uint64_t *T){
+    if (SIZE <= 0)
         return -1;
 
-    for (int i = 0 ; i < size ; i++)
+    for (int i = 0 ; i < SIZE ; i++)
         res[i] = T[i];
 
-    for (int j = 0 ; j < size ; j++){
+    for (int j = 0 ; j < SIZE ; j++){
         int i;
         int iMin = j;
-        for (i = j+1 ; i < size ; i++)
+        for (i = j+1 ; i < SIZE ; i++)
             if (res[i] < res[iMin])
                 iMin = i;
 
         if (iMin != j)
-            swap (&res[j], &res[iMin]);
+            swap_sel (&res[j], &res[iMin]);
     }
 
     return 0;
 }
 
 #ifdef __UNIT_TEST_SELECTION__
-#define SIZE 100
-
 int main(void){
     uint64_t T[SIZE];
     uint64_t res[SIZE];
@@ -40,7 +44,7 @@ int main(void){
         T[i] = randlong();
 
     /* Sorting the table */
-    if (selection_sort(res, T, SIZE) < 0) return -1;
+    if (select_sort(res, T) < 0) return -1;
 
     /* Computing max(T) */
     uint64_t max = T[0];
diff --git a/test/mppa/sort/selection.h b/test/mppa/sort/selection.h
index b2b4aebe..92a6b461 100644
--- a/test/mppa/sort/selection.h
+++ b/test/mppa/sort/selection.h
@@ -1,6 +1,6 @@
 #ifndef __SELECTION_H__
 #define __SELECTION_H__
 
-int selection_sort(uint64_t *res, const uint64_t *T, int size);
+int select_sort(uint64_t *res, const uint64_t *T);
 
 #endif // __SELECTION_H__
diff --git a/test/mppa/sort/test.c b/test/mppa/sort/test.c
new file mode 100644
index 00000000..e5e14fef
--- /dev/null
+++ b/test/mppa/sort/test.c
@@ -0,0 +1,33 @@
+#include "../lib/prng.h"
+#include "../lib/types.h"
+
+#include "test.h"
+#include "insertion.h"
+#include "selection.h"
+#include "merge.h"
+
+int main(void){
+    uint64_t T[SIZE];
+    uint64_t res1[SIZE], res2[SIZE], res3[SIZE];
+    srand(42);
+
+    for (int i = 0 ; i < SIZE ; i++)
+        T[i] = randlong();
+
+    /* insertion sort */
+    if (insert_sort(res1, T) < 0) return -1;
+
+    /* selection sort */
+    if (select_sort(res2, T) < 0) return -2;
+
+    /* merge sort */
+    if (merge_sort(res3, T) < 0) return -3;
+
+    /* We should have: res1[i] == res2[i] == res3[i] */
+    for (int i = 0 ; i < SIZE ; i++){
+        if (!(res1[i] == res2[i] && res2[i] == res3[i]))
+            return -4;
+    }
+
+    return 0;
+}
diff --git a/test/mppa/sort/test.h b/test/mppa/sort/test.h
new file mode 100644
index 00000000..4501ee38
--- /dev/null
+++ b/test/mppa/sort/test.h
@@ -0,0 +1,6 @@
+#ifndef __TEST_H__
+#define __TEST_H__
+
+#define SIZE 100
+
+#endif