From f24d303df6cb125ca19b953bb364955cc6e8c246 Mon Sep 17 00:00:00 2001 From: Cyril SIX Date: Fri, 9 Nov 2018 17:07:13 +0100 Subject: Fixed consistency between the different tests mmult, prng and sort --- test/mppa/lib/.gitignore | 2 -- test/mppa/lib/Makefile | 30 ---------------- test/mppa/lib/prng.c | 39 --------------------- test/mppa/lib/prng.h | 10 ------ test/mppa/lib/types.h | 7 ---- test/mppa/mmult/Makefile | 72 ++++++++++++-------------------------- test/mppa/mmult/README.md | 17 +++++++++ test/mppa/mmult/mmult.c | 44 +++++++++++++---------- test/mppa/prng/.gitignore | 2 ++ test/mppa/prng/Makefile | 49 ++++++++++++++++++++++++++ test/mppa/prng/README.md | 17 +++++++++ test/mppa/prng/prng.c | 41 ++++++++++++++++++++++ test/mppa/prng/prng.h | 10 ++++++ test/mppa/prng/types.h | 7 ++++ test/mppa/sort/Makefile | 87 ++++++++++++++++++++-------------------------- test/mppa/sort/README.md | 17 +++++++++ test/mppa/sort/insertion.c | 17 +++++---- test/mppa/sort/main.c | 34 ++++++++++++++++++ test/mppa/sort/merge.c | 25 +++++++------ test/mppa/sort/selection.c | 21 ++++++----- test/mppa/sort/test.c | 33 ------------------ 21 files changed, 315 insertions(+), 266 deletions(-) delete mode 100644 test/mppa/lib/.gitignore delete mode 100644 test/mppa/lib/Makefile delete mode 100644 test/mppa/lib/prng.c delete mode 100644 test/mppa/lib/prng.h delete mode 100644 test/mppa/lib/types.h create mode 100644 test/mppa/mmult/README.md create mode 100644 test/mppa/prng/.gitignore create mode 100644 test/mppa/prng/Makefile create mode 100644 test/mppa/prng/README.md create mode 100644 test/mppa/prng/prng.c create mode 100644 test/mppa/prng/prng.h create mode 100644 test/mppa/prng/types.h create mode 100644 test/mppa/sort/README.md create mode 100644 test/mppa/sort/main.c delete mode 100644 test/mppa/sort/test.c (limited to 'test/mppa') diff --git a/test/mppa/lib/.gitignore b/test/mppa/lib/.gitignore deleted file mode 100644 index 1879eaee..00000000 --- a/test/mppa/lib/.gitignore +++ /dev/null @@ -1,2 +0,0 @@ -prng-test-k1c -prng-test-x86 diff --git a/test/mppa/lib/Makefile b/test/mppa/lib/Makefile deleted file mode 100644 index 74e7ca8b..00000000 --- a/test/mppa/lib/Makefile +++ /dev/null @@ -1,30 +0,0 @@ -prng-test-x86: prng.c - gcc -D__UNIT_TEST_PRNG__ -O2 -std=c99 $< -o $@ - -prng-test-k1c: prng.c - k1-mbr-gcc -D__UNIT_TEST_PRNG__ -O2 -std=c99 $< -o $@ - -.PHONY: -test: test-x86 test-k1c - -.PHONY: -test-x86: prng-test-x86 - @if ! ./$<; then\ - >&2 echo "ERROR: $< failed";\ - exit;\ - else\ - echo "x86: Test Succeeded";\ - fi - -.PHONY: -test-k1c: prng-test-k1c - @if ! k1-cluster -- ./$<; then\ - >&2 echo "ERROR: $< failed";\ - exit;\ - else\ - echo "k1c: Test Succeeded";\ - fi - -.PHONY: -clean: - rm -f prng-test-x86 prng-test-k1c diff --git a/test/mppa/lib/prng.c b/test/mppa/lib/prng.c deleted file mode 100644 index af3903d6..00000000 --- a/test/mppa/lib/prng.c +++ /dev/null @@ -1,39 +0,0 @@ -// https://en.wikipedia.org/wiki/Linear_congruential_generator -> MMIX Donald Knuth -// modulo 2^64 = no need to do it explicitly - -#include "types.h" - -#define MULTIPLIER 6364136223846793005LL -#define INCREMENT 1442695040888963407LL - -static uint64_t current; - -void srand(uint64_t seed){ - current = seed; -} - -uint64_t randlong(void){ - return (current = MULTIPLIER * current + INCREMENT); -} - -#ifdef __UNIT_TEST_PRNG__ -char bytewise_sum(uint64_t to_check){ - char sum = 0; - - for (int i = 0 ; i < 8 ; i++) - sum += (to_check & (uint64_t)(0xFFULL << i*8)) >> i*8; - - return sum; -} - -int main(void){ - srand(42); - - for (int i = 0 ; i < 1000 ; i++) - randlong(); - - uint64_t last = randlong(); - - return !((unsigned char)bytewise_sum(last) == 155); -} -#endif // __UNIT_TEST_PRNG__ diff --git a/test/mppa/lib/prng.h b/test/mppa/lib/prng.h deleted file mode 100644 index 6abdb45a..00000000 --- a/test/mppa/lib/prng.h +++ /dev/null @@ -1,10 +0,0 @@ -#ifndef __PRNG_H__ -#define __PRNG_H__ - -#include "types.h" - -void srand(uint64_t seed); - -uint64_t randlong(void); - -#endif // __PRNG_H__ diff --git a/test/mppa/lib/types.h b/test/mppa/lib/types.h deleted file mode 100644 index 584023e3..00000000 --- a/test/mppa/lib/types.h +++ /dev/null @@ -1,7 +0,0 @@ -#ifndef __TYPES_H__ -#define __TYPES_H__ - -#define uint64_t unsigned long long -#define int64_t signed long long - -#endif // __TYPES_H__ diff --git a/test/mppa/mmult/Makefile b/test/mppa/mmult/Makefile index 9c00f8b0..2e077f5e 100644 --- a/test/mppa/mmult/Makefile +++ b/test/mppa/mmult/Makefile @@ -1,44 +1,28 @@ -PRNG=../lib/prng.c -CCOMP=../../../ccomp +K1CC ?= k1-mbr-gcc +CC ?= gcc +CCOMP ?= ccomp +CFLAGS ?= -O2 -ALL= mmult-test-x86 mmult-test-k1c\ +PRNG=../prng/prng.c -all: $(ALL) - -%-test-x86: %.c $(PRNG) - gcc -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ -O2 -std=c99 $^ -o $@ - -%-test-k1c: %.c $(PRNG) - k1-mbr-gcc -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ -O2 -std=c99 $^ -o $@ - -test-x86: mmult.c $(PRNG) - gcc -O2 -std=c99 $^ -o $@ - -test-k1c: mmult.c $(PRNG) - k1-mbr-gcc -O2 -std=c99 $^ -o $@ +ALL= mmult-test-gcc-x86 mmult-test-gcc-k1c mmult-test-ccomp-k1c\ -%.s: %.c $(CCOMP) - ccomp -O2 -S $< -o $@ +all: $(ALL) -test-ccomp: mmult.s $(subst .c,.s,$(PRNG)) - k1-mbr-gcc $^ -o $@ +mmult-test-gcc-x86: mmult.c $(PRNG) + $(CC) $(CFLAGS) $^ -o $@ -.PHONY: -unittest: unittest-x86 unittest-k1c +mmult-test-gcc-k1c: mmult.c $(PRNG) + $(K1CC) $(CFLAGS) $^ -o $@ -.PHONY: -check: check-x86 check-k1c +mmult-test-ccomp-k1c: mmult.c $(PRNG) + $(CCOMP) $(CFLAGS) $^ -o $@ .PHONY: -compc-check: test-ccomp - @if ! k1-cluster -- ./$<; then\ - >&2 echo "ERROR k1c: mmult $< failed";\ - else\ - echo "k1c: Test mmult $< succeeded";\ - fi +test: test-x86 test-k1c .PHONY: -check-x86: test-x86 +test-x86: mmult-test-gcc-x86 @if ! ./$<; then\ >&2 echo "ERROR x86: $< failed";\ else\ @@ -46,7 +30,7 @@ check-x86: test-x86 fi .PHONY: -check-k1c: test-k1c +test-k1c: mmult-test-gcc-k1c @if ! k1-cluster -- ./$<; then\ >&2 echo "ERROR k1c: $< failed";\ else\ @@ -54,24 +38,12 @@ check-k1c: test-k1c fi .PHONY: -unittest-x86: mmult-test-x86 - @for test in $^; do\ - if ! ./$$test; then\ - >&2 echo "ERROR x86: $$test failed";\ - else\ - echo "x86: Test $$test Succeeded";\ - fi;\ - done - -.PHONY: -unittest-k1c: mmult-test-k1c - @for test in $^; do\ - if ! k1-cluster -- ./$$test; then\ - >&2 echo "ERROR k1c: $$test failed";\ - else\ - echo "k1c: Test $$test Succeeded";\ - fi;\ - done +check: mmult-test-ccomp-k1c + @if ! k1-cluster -- ./$<; then\ + >&2 echo "ERROR k1c: mmult $< failed";\ + else\ + echo "k1c: Test mmult $< succeeded";\ + fi .PHONY: clean: diff --git a/test/mppa/mmult/README.md b/test/mppa/mmult/README.md new file mode 100644 index 00000000..ef2bff7e --- /dev/null +++ b/test/mppa/mmult/README.md @@ -0,0 +1,17 @@ +MMULT +===== + +Examples of matrix multiplication using different methods. + +We compute matrix multiplication using column-based matrix multiplication, then row-based, and finally block based. + +The test verifies that the result is the same on the three methods. If it is the same, 0 will be returned. + +The following commands can be run inside the folder: + +- `make`: produces the unitary test binaries + - `mmult-test-gcc-x86` : binary from gcc on x86 + - `mmult-test-k1c-x86` : binary from gcc on k1c + - `mmult-test-ccomp-x86` : binary from ccomp on k1c +- `make test`: tests the return value of the binaries produced by gcc. +- `make check`: tests the return value of the binary produced by CompCert. diff --git a/test/mppa/mmult/mmult.c b/test/mppa/mmult/mmult.c index b674ca80..aeb91d48 100644 --- a/test/mppa/mmult/mmult.c +++ b/test/mppa/mmult/mmult.c @@ -1,5 +1,5 @@ -#include "../lib/types.h" -#include "../lib/prng.h" +#include "../prng/types.h" +#include "../prng/prng.h" #define __UNIT_TEST_MMULT__ @@ -10,24 +10,28 @@ #endif void mmult_row(uint64_t C[][SIZE], uint64_t A[][SIZE], uint64_t B[][SIZE]){ - for (int i = 0 ; i < SIZE ; i++) - for (int j = 0 ; j < SIZE ; j++) + int i, j, k; + + for (i = 0 ; i < SIZE ; i++) + for (j = 0 ; j < SIZE ; j++) C[i][j] = 0; - for (int i = 0 ; i < SIZE ; i++) - for (int j = 0 ; j < SIZE ; j++) - for (int k = 0 ; k < SIZE ; k++) + for (i = 0 ; i < SIZE ; i++) + for (j = 0 ; j < SIZE ; j++) + for (k = 0 ; k < SIZE ; k++) C[i][j] += A[i][k] * B[k][j]; } void mmult_col(uint64_t C[][SIZE], uint64_t A[][SIZE], uint64_t B[][SIZE]){ - for (int i = 0 ; i < SIZE ; i++) - for (int j = 0 ; j < SIZE ; j++) + int i, j, k; + + for (i = 0 ; i < SIZE ; i++) + for (j = 0 ; j < SIZE ; j++) C[i][j] = 0; - for (int k = 0 ; k < SIZE ; k++) - for (int i = 0 ; i < SIZE ; i++) - for (int j = 0 ; j < SIZE ; j++) + for (k = 0 ; k < SIZE ; k++) + for (i = 0 ; i < SIZE ; i++) + for (j = 0 ; j < SIZE ; j++) C[i][j] += A[i][k] * B[k][j]; } @@ -41,10 +45,11 @@ typedef struct mblock { void divac_mul(mblock *C, const mblock *A, const mblock *B){ const int size = C->imax - C->imin; + int i, j, k; - for (int i = 0 ; i < size ; i++) - for (int j = 0 ; j < size ; j++) - for (int k = 0 ; k < size ; k++) + for (i = 0 ; i < size ; i++) + for (j = 0 ; j < size ; j++) + for (k = 0 ; k < size ; k++) MAT_IJ(C, i, j) += MAT_IJ(A, i, k) * MAT_IJ(B, k, j); } @@ -119,9 +124,10 @@ static uint64_t A[SIZE][SIZE], B[SIZE][SIZE]; int main(void){ srand(42); + int i, j; - for (int i = 0 ; i < SIZE ; i++) - for (int j = 0 ; j < SIZE ; j++){ + for (i = 0 ; i < SIZE ; i++) + for (j = 0 ; j < SIZE ; j++){ A[i][j] = randlong(); B[i][j] = randlong(); } @@ -130,8 +136,8 @@ int main(void){ mmult_col(C2, A, B); mmult_divac(C3, A, B); - for (int i = 0 ; i < SIZE ; i++) - for (int j = 0 ; j < SIZE ; j++) + for (i = 0 ; i < SIZE ; i++) + for (j = 0 ; j < SIZE ; j++) if (!(C1[i][j] == C2[i][j] && C1[i][j] == C3[i][j])) return -1; diff --git a/test/mppa/prng/.gitignore b/test/mppa/prng/.gitignore new file mode 100644 index 00000000..1879eaee --- /dev/null +++ b/test/mppa/prng/.gitignore @@ -0,0 +1,2 @@ +prng-test-k1c +prng-test-x86 diff --git a/test/mppa/prng/Makefile b/test/mppa/prng/Makefile new file mode 100644 index 00000000..481a3fca --- /dev/null +++ b/test/mppa/prng/Makefile @@ -0,0 +1,49 @@ +K1CC ?= k1-mbr-gcc +CC ?= gcc +CCOMP ?= ccomp +CFLAGS ?= -O2 + +all: prng-test-gcc-x86 prng-test-gcc-k1c prng-test-ccomp-k1c + +prng-test-gcc-x86: prng.c + $(CC) -D__UNIT_TEST_PRNG__ $(CFLAGS) $< -o $@ + +prng-test-gcc-k1c: prng.c + $(K1CC) -D__UNIT_TEST_PRNG__ $(CFLAGS) $< -o $@ + +prng-test-ccomp-k1c: prng.c + $(CCOMP) -D__UNIT_TEST_PRNG__ $(CFLAGS) $< -o $@ + +.PHONY: +test: test-x86 test-k1c + +.PHONY: +test-x86: prng-test-gcc-x86 + @if ! ./$<; then\ + >&2 echo "ERROR: $< failed";\ + exit;\ + else\ + echo "$< Succeeded";\ + fi + +.PHONY: +test-k1c: prng-test-gcc-k1c + @if ! k1-cluster -- ./$<; then\ + >&2 echo "ERROR: $< failed";\ + exit;\ + else\ + echo "$< Succeeded";\ + fi + +.PHONY: +check: prng-test-ccomp-k1c + @if ! k1-cluster -- ./$<; then\ + >&2 echo "ERROR: $< failed";\ + exit;\ + else\ + echo "$< Succeeded";\ + fi + +.PHONY: +clean: + rm -f prng-test-gcc-x86 prng-test-gcc-k1c prng-test-ccomp-k1c diff --git a/test/mppa/prng/README.md b/test/mppa/prng/README.md new file mode 100644 index 00000000..b4c2279b --- /dev/null +++ b/test/mppa/prng/README.md @@ -0,0 +1,17 @@ +PRNG +==== + +This is a simple Pseudo Random Number Generator. + +`prng.c` contains a simple unitary test that compares the sum of the "bytewise sum" +of 1000 generated numbers to a hardcoded result, that is the one obtained with +`gcc -O2` on a x86 processor, and returns 0 if the result is correct. + +The following commands can be run inside that folder: + +- `make`: produces the unitary test binaries + - `prng-test-gcc-x86` : binary from gcc on x86 + - `prng-test-k1c-x86` : binary from gcc on k1c + - `prng-test-ccomp-x86` : binary from ccomp on k1c +- `make test`: tests the return value of the binaries produced by gcc. +- `make check`: tests the return value of the binary produced by CompCert. diff --git a/test/mppa/prng/prng.c b/test/mppa/prng/prng.c new file mode 100644 index 00000000..71de1dc3 --- /dev/null +++ b/test/mppa/prng/prng.c @@ -0,0 +1,41 @@ +// https://en.wikipedia.org/wiki/Linear_congruential_generator -> MMIX Donald Knuth +// modulo 2^64 = no need to do it explicitly + +#include "types.h" + +#define MULTIPLIER 6364136223846793005LL +#define INCREMENT 1442695040888963407LL + +static uint64_t current; + +void srand(uint64_t seed){ + current = seed; +} + +uint64_t randlong(void){ + return (current = MULTIPLIER * current + INCREMENT); +} + +#ifdef __UNIT_TEST_PRNG__ +char bytewise_sum(uint64_t to_check){ + char sum = 0; + int i; + + for (i = 0 ; i < 8 ; i++) + sum += (to_check & (uint64_t)(0xFFULL << i*8)) >> i*8; + + return sum; +} + +int main(void){ + srand(42); + int i; + + for (i = 0 ; i < 1000 ; i++) + randlong(); + + uint64_t last = randlong(); + + return !((unsigned char)bytewise_sum(last) == 155); +} +#endif // __UNIT_TEST_PRNG__ diff --git a/test/mppa/prng/prng.h b/test/mppa/prng/prng.h new file mode 100644 index 00000000..6abdb45a --- /dev/null +++ b/test/mppa/prng/prng.h @@ -0,0 +1,10 @@ +#ifndef __PRNG_H__ +#define __PRNG_H__ + +#include "types.h" + +void srand(uint64_t seed); + +uint64_t randlong(void); + +#endif // __PRNG_H__ diff --git a/test/mppa/prng/types.h b/test/mppa/prng/types.h new file mode 100644 index 00000000..584023e3 --- /dev/null +++ b/test/mppa/prng/types.h @@ -0,0 +1,7 @@ +#ifndef __TYPES_H__ +#define __TYPES_H__ + +#define uint64_t unsigned long long +#define int64_t signed long long + +#endif // __TYPES_H__ diff --git a/test/mppa/sort/Makefile b/test/mppa/sort/Makefile index 26c597be..c0c9347d 100644 --- a/test/mppa/sort/Makefile +++ b/test/mppa/sort/Makefile @@ -1,64 +1,40 @@ -PRNG=../lib/prng.c -CCOMP=../../../ccomp +K1CC ?= k1-mbr-gcc +CC ?= gcc +CCOMP ?= ccomp +CFLAGS ?= -O2 -ALL= insertion-test-x86 insertion-test-k1c\ - selection-test-x86 selection-test-k1c\ - merge-test-x86 merge-test-k1c\ - test-x86 test-k1c\ - test-ccomp +PRNG=../prng/prng.c -all: $(ALL) - -%-test-x86: %.c $(PRNG) - gcc -g -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ -O2 -std=c99 $^ -o $@ +CFILES=insertion.c merge.c selection.c main.c -%-test-k1c: %.c $(PRNG) - k1-mbr-gcc -g -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ -O2 -std=c99 $^ -o $@ +ALL= insertion-test-gcc-x86 insertion-test-gcc-k1c\ + selection-test-gcc-x86 selection-test-gcc-k1c\ + merge-test-gcc-x86 merge-test-gcc-k1c\ + main-test-gcc-x86 main-test-gcc-k1c\ + main-test-ccomp-k1c -test-x86: selection.c merge.c insertion.c test.c $(PRNG) - gcc -g -O2 -std=c99 $^ -o $@ +all: $(ALL) -test-k1c: selection.c merge.c insertion.c test.c $(PRNG) - k1-mbr-gcc -g -O2 -std=c99 $^ -o $@ +main-test-gcc-x86: $(CFILES) $(PRNG) + $(CC) $(CFLAGS) $^ -o $@ -%.s: %.c $(CCOMP) - ccomp -O2 -S $< -o $@ +%-test-gcc-x86: %.c $(PRNG) + $(CC) -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ $(CFLAGS) $^ -o $@ -test-ccomp: selection.s merge.s insertion.s test.s $(subst .c,.s,$(PRNG)) - k1-mbr-gcc $^ -o $@ +main-test-gcc-k1c: $(CFILES) $(PRNG) + $(K1CC) $(CFLAGS) $^ -o $@ -.PHONY: -unittest: unittest-x86 unittest-k1c +%-test-gcc-k1c: %.c $(PRNG) + $(K1CC) -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ $(CFLAGS) $^ -o $@ -.PHONY: -check: check-x86 check-k1c +main-test-ccomp-k1c: $(CFILES) $(PRNG) + $(CCOMP) $(CFLAGS) $^ -o $@ -.PHONY: -compc-check: test-ccomp - @if ! k1-cluster -- ./$<; then\ - >&2 echo "ERROR k1c: sort $< failed";\ - else\ - echo "k1c: Test sort $< succeeded";\ - fi - -.PHONY: -check-x86: test-x86 - @if ! ./$<; then\ - >&2 echo "ERROR x86: $< failed";\ - else\ - echo "x86: Test $< succeeded";\ - fi +%-test-ccomp-k1c: %.c $(PRNG) + $(CCOMP) -D__UNIT_TEST_$$(echo $(basename $<) | tr a-z A-Z)__ $(CFLAGS) $^ -o $@ .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 +test-x86: insertion-test-gcc-x86 selection-test-gcc-x86 merge-test-gcc-x86 main-test-gcc-x86 @for test in $^; do\ if ! ./$$test; then\ >&2 echo "ERROR x86: $$test failed";\ @@ -68,7 +44,7 @@ unittest-x86: insertion-test-x86 selection-test-x86 merge-test-x86 done .PHONY: -unittest-k1c: insertion-test-k1c selection-test-k1c merge-test-k1c +test-k1c: insertion-test-gcc-k1c selection-test-gcc-k1c merge-test-gcc-k1c main-test-gcc-k1c @for test in $^; do\ if ! k1-cluster -- ./$$test; then\ >&2 echo "ERROR k1c: $$test failed";\ @@ -77,6 +53,17 @@ unittest-k1c: insertion-test-k1c selection-test-k1c merge-test-k1c fi;\ done +.PHONY: +test: test-x86 test-k1c + +.PHONY: +check: main-test-ccomp-k1c + @if ! k1-cluster -- ./$<; then\ + >&2 echo "ERROR k1c: sort $< failed";\ + else\ + echo "k1c: Test sort $< succeeded";\ + fi + .PHONY: clean: rm -f $(ALL) diff --git a/test/mppa/sort/README.md b/test/mppa/sort/README.md new file mode 100644 index 00000000..b4c2279b --- /dev/null +++ b/test/mppa/sort/README.md @@ -0,0 +1,17 @@ +PRNG +==== + +This is a simple Pseudo Random Number Generator. + +`prng.c` contains a simple unitary test that compares the sum of the "bytewise sum" +of 1000 generated numbers to a hardcoded result, that is the one obtained with +`gcc -O2` on a x86 processor, and returns 0 if the result is correct. + +The following commands can be run inside that folder: + +- `make`: produces the unitary test binaries + - `prng-test-gcc-x86` : binary from gcc on x86 + - `prng-test-k1c-x86` : binary from gcc on k1c + - `prng-test-ccomp-x86` : binary from ccomp on k1c +- `make test`: tests the return value of the binaries produced by gcc. +- `make check`: tests the return value of the binary produced by CompCert. diff --git a/test/mppa/sort/insertion.c b/test/mppa/sort/insertion.c index 88093b64..bca09599 100644 --- a/test/mppa/sort/insertion.c +++ b/test/mppa/sort/insertion.c @@ -1,5 +1,5 @@ -#include "../lib/prng.h" -#include "../lib/types.h" +#include "../prng/prng.h" +#include "../prng/types.h" #ifdef __UNIT_TEST_INSERTION__ #define SIZE 100 @@ -14,16 +14,18 @@ void swap_ins(uint64_t *a, uint64_t *b){ } int insert_sort(uint64_t *res, const uint64_t *T){ + int i, j; + if (SIZE <= 0) return -1; - for (int i = 0 ; i < SIZE ; i++) + for (i = 0 ; i < SIZE ; i++) res[i] = T[i]; - for (int i = 0 ; i < SIZE-1 ; i++){ + for (i = 0 ; i < SIZE-1 ; i++){ if (res[i] > res[i+1]){ swap_ins(&res[i], &res[i+1]); - for (int j = i ; j > 0 ; j--) + for (j = i ; j > 0 ; j--) if (res[j-1] > res[j]) swap_ins(&res[j-1], &res[j]); } @@ -36,9 +38,10 @@ int insert_sort(uint64_t *res, const uint64_t *T){ int main(void){ uint64_t T[SIZE]; uint64_t res[SIZE]; + int i; srand(42); - for (int i = 0 ; i < SIZE ; i++) + for (i = 0 ; i < SIZE ; i++) T[i] = randlong(); /* Sorting the table */ @@ -46,7 +49,7 @@ int main(void){ /* Computing max(T) */ uint64_t max = T[0]; - for (int i = 1 ; i < SIZE ; i++) + for (i = 1 ; i < SIZE ; i++) if (T[i] > max) max = T[i]; diff --git a/test/mppa/sort/main.c b/test/mppa/sort/main.c new file mode 100644 index 00000000..aef419aa --- /dev/null +++ b/test/mppa/sort/main.c @@ -0,0 +1,34 @@ +#include "../prng/prng.h" +#include "../prng/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]; + int i; + srand(42); + + for (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 (i = 0 ; i < SIZE ; i++){ + if (!(res1[i] == res2[i] && res2[i] == res3[i])) + return -4; + } + + return 0; +} diff --git a/test/mppa/sort/merge.c b/test/mppa/sort/merge.c index b2d41ce3..99f8ba85 100644 --- a/test/mppa/sort/merge.c +++ b/test/mppa/sort/merge.c @@ -1,5 +1,5 @@ -#include "../lib/prng.h" -#include "../lib/types.h" +#include "../prng/prng.h" +#include "../prng/types.h" //https://en.wikipedia.org/wiki/Merge_sort @@ -15,8 +15,8 @@ int min(int a, int b){ void BottomUpMerge(const uint64_t *A, int iLeft, int iRight, int iEnd, uint64_t *B) { - int i = iLeft, j = iRight; - for (int k = iLeft; k < iEnd; k++) { + int i = iLeft, j = iRight, k; + for (k = iLeft; k < iEnd; k++) { if (i < iRight && (j >= iEnd || A[i] <= A[j])) { B[k] = A[i]; i = i + 1; @@ -30,18 +30,20 @@ void BottomUpMerge(const uint64_t *A, int iLeft, int iRight, int iEnd, uint64_t void CopyArray(uint64_t *to, const uint64_t *from) { const int n = SIZE; + int i; - for(int i = 0; i < n; i++) + for(i = 0; i < n; i++) to[i] = from[i]; } void BottomUpMergeSort(uint64_t *A, uint64_t *B) { const int n = SIZE; + int width, i; - for (int width = 1; width < n; width = 2 * width) + for (width = 1; width < n; width = 2 * width) { - for (int i = 0; i < n; i = i + 2 * width) + for (i = 0; i < n; i = i + 2 * width) { BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B); } @@ -50,12 +52,14 @@ void BottomUpMergeSort(uint64_t *A, uint64_t *B) } int merge_sort(uint64_t *res, const uint64_t *T){ + int i; + if (SIZE <= 0) return -1; uint64_t B[SIZE]; uint64_t *A = res; - for (int i = 0 ; i < SIZE ; i++) + for (i = 0 ; i < SIZE ; i++) A[i] = T[i]; BottomUpMergeSort(A, B); @@ -67,9 +71,10 @@ int merge_sort(uint64_t *res, const uint64_t *T){ int main(void){ uint64_t T[SIZE]; uint64_t res[SIZE]; + int i; srand(42); - for (int i = 0 ; i < SIZE ; i++) + for (i = 0 ; i < SIZE ; i++) T[i] = randlong(); /* Sorting the table */ @@ -77,7 +82,7 @@ int main(void){ /* Computing max(T) */ uint64_t max = T[0]; - for (int i = 1 ; i < SIZE ; i++) + for (i = 1 ; i < SIZE ; i++) if (T[i] > max) max = T[i]; diff --git a/test/mppa/sort/selection.c b/test/mppa/sort/selection.c index 89bc2c65..df4be04f 100644 --- a/test/mppa/sort/selection.c +++ b/test/mppa/sort/selection.c @@ -1,5 +1,5 @@ -#include "../lib/prng.h" -#include "../lib/types.h" +#include "../prng/prng.h" +#include "../prng/types.h" #ifdef __UNIT_TEST_SELECTION__ #define SIZE 100 @@ -14,15 +14,16 @@ void swap_sel(uint64_t *a, uint64_t *b){ } int select_sort(uint64_t *res, const uint64_t *T){ + int i, j, iMin; + if (SIZE <= 0) return -1; - for (int i = 0 ; i < SIZE ; i++) + for (i = 0 ; i < SIZE ; i++) res[i] = T[i]; - for (int j = 0 ; j < SIZE ; j++){ - int i; - int iMin = j; + for (j = 0 ; j < SIZE ; j++){ + iMin = j; for (i = j+1 ; i < SIZE ; i++) if (res[i] < res[iMin]) iMin = i; @@ -38,17 +39,19 @@ int select_sort(uint64_t *res, const uint64_t *T){ int main(void){ uint64_t T[SIZE]; uint64_t res[SIZE]; + uint64_t max; + int i; srand(42); - for (int i = 0 ; i < SIZE ; i++) + for (i = 0 ; i < SIZE ; i++) T[i] = randlong(); /* Sorting the table */ if (select_sort(res, T) < 0) return -1; /* Computing max(T) */ - uint64_t max = T[0]; - for (int i = 1 ; i < SIZE ; i++) + max = T[0]; + for (i = 1 ; i < SIZE ; i++) if (T[i] > max) max = T[i]; diff --git a/test/mppa/sort/test.c b/test/mppa/sort/test.c deleted file mode 100644 index e5e14fef..00000000 --- a/test/mppa/sort/test.c +++ /dev/null @@ -1,33 +0,0 @@ -#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; -} -- cgit