summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--test/Makefile.am12
-rw-r--r--test/builtin/rs_vand/rs_galois_test.c64
-rw-r--r--test/builtin/rs_vand/rs_vand_internal_test.c334
3 files changed, 409 insertions, 1 deletions
diff --git a/test/Makefile.am b/test/Makefile.am
index f625ec9..e45d400 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -1,5 +1,5 @@
noinst_HEADERS = builtin/xor_codes/test_xor_hd_code.h
-noinst_PROGRAMS = test_xor_hd_code alg_sig_test liberasurecode_test libec_slap
+noinst_PROGRAMS = test_xor_hd_code alg_sig_test liberasurecode_test libec_slap rs_galois_test rs_vand_internal_test
test_xor_hd_code_SOURCES = \
builtin/xor_codes/test_xor_hd_code.c \
@@ -23,6 +23,16 @@ libec_slap_CPPFLAGS = -I. -I$(top_srcdir)/include -I$(top_srcdir)/include/erasur
libec_slap_LDFLAGS = @GCOV_LDFLAGS@ $(top_srcdir)/src/liberasurecode.la -ldl -lpthread
check_PROGRAMS += libec_slap
+rs_galois_test_SOURCES = builtin/rs_vand/rs_galois_test.c
+rs_galois_test_CPPFLAGS = -I$(top_srcdir)/include -I$(top_srcdir)/include/rs_vand @GCOV_FLAGS@
+rs_galois_test_LDFLAGS = @GCOV_LDFLAGS@ -static-libtool-libs $(top_srcdir)/src/builtin/rs_vand/liberasurecode_rsvand.la
+check_PROGRAMS += rs_galois_test
+
+rs_vand_internal_test_SOURCES = builtin/rs_vand/rs_vand_internal_test.c
+rs_vand_internal_test_CPPFLAGS = -I$(top_srcdir)/include -I$(top_srcdir)/include/rs_vand @GCOV_FLAGS@
+rs_vand_internal_test_LDFLAGS = @GCOV_LDFLAGS@ -static-libtool-libs $(top_srcdir)/src/builtin/rs_vand/liberasurecode_rsvand.la
+check_PROGRAMS += rs_vand_internal_test
+
MOSTLYCLEANFILES = *.gcda *.gcno *.gcov \
./builtin/xor_codes/*.gcda ./builtin/xor_codes/*.gcno ./builtin/xor_codes/*.gcov \
./utils/chksum/*.gcda ./utils/chksum/*.gcno ./utils/chksum/*.gcov
diff --git a/test/builtin/rs_vand/rs_galois_test.c b/test/builtin/rs_vand/rs_galois_test.c
new file mode 100644
index 0000000..b727755
--- /dev/null
+++ b/test/builtin/rs_vand/rs_galois_test.c
@@ -0,0 +1,64 @@
+/*
+ * Copyright 2015 Kevin M Greenan
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * Redistributions of source code must retain the above copyright notice, this
+ * list of conditions and the following disclaimer.
+ *
+ * Redistributions in binary form must reproduce the above copyright notice, this
+ * list of conditions and the following disclaimer in the documentation and/or
+ * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY
+ * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * vi: set noai tw=79 ts=4 sw=4:
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <rs_galois.h>
+
+int test_inverse()
+{
+ int *uniq = (int*)malloc(sizeof(int)*FIELD_SIZE);
+ int i = 0;
+
+ memset(uniq, 0, sizeof(int)*FIELD_SIZE);
+
+ rs_galois_init_tables();
+
+ for (i = 1; i < FIELD_SIZE; i++) {
+ if (uniq[i] != 0) {
+ fprintf(stderr, "Duplicate %d: %d , %d \n", i, uniq[i], rs_galois_inverse(i));
+ return 1;
+ }
+ uniq[i] = rs_galois_inverse(i);
+ int one = rs_galois_mult(rs_galois_inverse(i), i);
+ if (one != 1) {
+ fprintf(stderr, "%d is not the inverse of %d = %d\n", rs_galois_inverse(i), i, one);
+ return 1;
+ }
+ }
+ return 0;
+}
+
+int main(int argc, char **argv)
+{
+ int ret = 0;
+ if (test_inverse() != 0) {
+ fprintf(stderr, "test_inverse() failed\n");
+ ret = 1;
+ }
+ return ret;
+}
diff --git a/test/builtin/rs_vand/rs_vand_internal_test.c b/test/builtin/rs_vand/rs_vand_internal_test.c
new file mode 100644
index 0000000..139c91f
--- /dev/null
+++ b/test/builtin/rs_vand/rs_vand_internal_test.c
@@ -0,0 +1,334 @@
+/*
+ * Copyright 2015 Kevin M Greenan
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * Redistributions of source code must retain the above copyright notice, this
+ * list of conditions and the following disclaimer.
+ *
+ * Redistributions in binary form must reproduce the above copyright notice, this
+ * list of conditions and the following disclaimer in the documentation and/or
+ * other materials provided with the distribution. THIS SOFTWARE IS PROVIDED BY
+ * THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+ * EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
+ * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * vi: set noai tw=79 ts=4 sw=4:
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <time.h>
+#include <rs_vand_internal.h>
+
+int test_make_systematic_matrix(int k, int m)
+{
+ int *matrix = make_systematic_matrix(k, m);
+ int is_identity = is_identity_matrix(matrix, k);
+
+ if (!is_identity) {
+ printf("Generating systematic matrix did not work!\n");
+ printf("Generator matrix: \n\n");
+ print_matrix(matrix, m+k, k);
+ }
+
+ free_systematic_matrix(matrix);
+
+ return is_identity;
+}
+
+void dump_buffer(char *buf, int size, const char* filename)
+{
+ int fd = open(filename, O_RDWR | O_CREAT);
+ write(fd, buf, size);
+ close(fd);
+}
+
+int test_invert_systematic_matrix(int k, int m, int num_missing)
+{
+ int *inverse = (int*)malloc(sizeof(int)*k*k);
+ int *prod = (int*)malloc(sizeof(int)*k*k);
+ int *missing = (int*)malloc(sizeof(int)*(num_missing+1));
+ int *matrix = make_systematic_matrix(k, m);
+ int *decoding_matrix = (int*)malloc(sizeof(int)*k*k);
+ int *decoding_matrix_cpy = (int*)malloc(sizeof(int)*k*k);
+ int n = k+m;
+ int i, res;
+
+ srand((unsigned int)time(0));
+
+ for (i = 0;i < num_missing+1; i++) {
+ missing[i] = -1;
+ }
+
+ for (i = 0;i < num_missing; i++) {
+ int idx = rand() % n;
+ while (is_missing(missing, idx)) {
+ idx = rand() % n;
+ }
+ missing[i] = idx;
+ }
+
+ create_decoding_matrix(matrix, decoding_matrix, missing, k, m);
+ create_decoding_matrix(matrix, decoding_matrix_cpy, missing, k, m);
+
+ gaussj_inversion(decoding_matrix, inverse, k);
+
+ square_matrix_multiply(decoding_matrix_cpy, inverse, prod, k);
+
+ res = is_identity_matrix(prod, k);
+
+ if (!res) {
+ printf("Inverting decoding matrix did not work!\n");
+ printf("Generator matrix: \n\n");
+ print_matrix(matrix, n, k);
+ printf("Decoding matrix: \n\n");
+ print_matrix(decoding_matrix_cpy, k, k);
+ printf("Inverse Decoding matrix: \n\n");
+ print_matrix(inverse, k, k);
+ printf("Missing: \n\n");
+ print_matrix(missing, 1, num_missing);
+ }
+
+ free(inverse);
+ free(prod);
+ free(missing);
+ free(decoding_matrix);
+ free(decoding_matrix_cpy);
+ free_systematic_matrix(matrix);
+
+ return res;
+}
+
+char* gen_random_buffer(int blocksize)
+{
+ int i;
+ char *buf = (char*)malloc(blocksize);
+
+ for (i = 0; i < blocksize; i++) {
+ buf[i] = (char)(rand() % 255);
+ }
+
+ return buf;
+}
+
+int test_encode_decode(int k, int m, int num_missing, int blocksize)
+{
+ char **data = (char**)malloc(sizeof(char*)*k);
+ char **parity = (char**)malloc(sizeof(char*)*m);
+ char **missing_bufs = (char**)malloc(sizeof(char*)*num_missing);
+ int *missing = (int*)malloc(sizeof(int)*(num_missing+1));
+ int *matrix = make_systematic_matrix(k, m);
+ int n = k + m;
+ int i;
+ int ret = 1;
+
+ srand((unsigned int)time(0));
+
+ for (i = 0; i < k; i++) {
+ data[i] = gen_random_buffer(blocksize);
+ }
+
+ for (i = 0; i < m; i++) {
+ parity[i] = (char*)malloc(blocksize);
+ }
+
+ for (i = 0;i < num_missing+1; i++) {
+ missing[i] = -1;
+ }
+
+ // Encode
+ internal_rs_vand_encode(matrix, data, parity, k, m, blocksize);
+
+ // Copy data and parity
+ for (i = 0;i < num_missing; i++) {
+ int idx = rand() % n;
+ while (is_missing(missing, idx)) {
+ idx = rand() % n;
+ }
+ missing_bufs[i] = (char*)malloc(blocksize);
+ memcpy(missing_bufs[i], idx < k ? data[idx] : parity[idx - k], blocksize);
+ missing[i] = idx;
+ }
+
+ // Zero missing bufs
+ for (i = 0;i < num_missing; i++) {
+ if (missing[i] < k) {
+ memset(data[missing[i]], 0, blocksize);
+ } else {
+ memset(parity[missing[i] - k], 0, blocksize);
+ }
+ }
+
+ // Decode and check
+ internal_rs_vand_decode(matrix, data, parity, k, m, missing, blocksize, 1);
+
+ for (i = 0; i < num_missing; i++) {
+ int idx = missing[i];
+ if (idx < k) {
+ if (memcmp(data[idx], missing_bufs[i], blocksize)) {
+ dump_buffer(data[idx], blocksize, "decoded_buffer");
+ dump_buffer(missing_bufs[i], blocksize, "orig_buffer");
+ ret = 0;
+ }
+ } else if (memcmp(parity[idx - k], missing_bufs[i], blocksize)) {
+ ret = 0;
+ }
+ }
+
+ for (i = 0; i < k; i++) {
+ free(data[i]);
+ }
+ free(data);
+ for (i = 0; i < m; i++) {
+ free(parity[i]);
+ }
+ free(parity);
+ for (i = 0; i < num_missing; i++) {
+ free(missing_bufs[i]);
+ }
+ free(missing_bufs);
+ free(missing);
+ free(matrix);
+
+ return ret;
+}
+
+int test_reconstruct(int k, int m, int num_missing, int blocksize)
+{
+ char **data = (char**)malloc(sizeof(char*)*k);
+ char **parity = (char**)malloc(sizeof(char*)*m);
+ char **missing_bufs = (char**)malloc(sizeof(char*)*num_missing);
+ int *missing = (int*)malloc(sizeof(int)*(num_missing+1));
+ int *matrix = make_systematic_matrix(k, m);
+ int destination_idx;
+ int n = k + m;
+ int i;
+ int ret = 1;
+
+ srand((unsigned int)time(0));
+
+ for (i = 0; i < k; i++) {
+ data[i] = gen_random_buffer(blocksize);
+ }
+
+ for (i = 0; i < m; i++) {
+ parity[i] = (char*)malloc(blocksize);
+ }
+
+ for (i = 0;i < num_missing+1; i++) {
+ missing[i] = -1;
+ }
+
+ // Encode
+ internal_rs_vand_encode(matrix, data, parity, k, m, blocksize);
+
+ // Copy data and parity
+ for (i = 0; i < num_missing; i++) {
+ int idx = rand() % n;
+ while (is_missing(missing, idx)) {
+ idx = rand() % n;
+ }
+ missing_bufs[i] = (char*)malloc(blocksize);
+ memcpy(missing_bufs[i], idx < k ? data[idx] : parity[idx - k], blocksize);
+ missing[i] = idx;
+ if (i == 0) {
+ destination_idx = missing[i];
+ }
+ }
+
+ // Zero missing bufs
+ for (i = 0;i < num_missing; i++) {
+ if (missing[i] < k) {
+ memset(data[missing[i]], 0, blocksize);
+ } else {
+ memset(parity[missing[i] - k], 0, blocksize);
+ }
+ }
+
+ // Reconstruct and check destination buffer
+ internal_rs_vand_reconstruct(matrix, data, parity, k, m, missing, destination_idx, blocksize);
+
+ // The original copy of the destination buffer is in the 0th buffer (see above)
+ if (destination_idx < k) {
+ if (memcmp(data[destination_idx], missing_bufs[0], blocksize)) {
+ dump_buffer(data[destination_idx], blocksize, "decoded_buffer");
+ dump_buffer(missing_bufs[0], blocksize, "orig_buffer");
+ ret = 0;
+ }
+ } else if (memcmp(parity[destination_idx - k], missing_bufs[0], blocksize)) {
+ ret = 0;
+ }
+
+ for (i = 0; i < k; i++) {
+ free(data[i]);
+ }
+ free(data);
+ for (i = 0; i < m; i++) {
+ free(parity[i]);
+ }
+ free(parity);
+ for (i = 0; i < num_missing; i++) {
+ free(missing_bufs[i]);
+ }
+ free(missing_bufs);
+ free(missing);
+ free(matrix);
+
+ return ret;
+}
+
+int matrix_dimensions[][2] = { {12, 6}, {12, 3}, {12, 2}, {12, 1}, {5, 3}, {5, 2}, {5, 1}, {1, 1}, {-1, -1} };
+
+int main()
+{
+ int i = 0;
+ int blocksize = 4096;
+
+ while (matrix_dimensions[i][0] >= 0) {
+ int k = matrix_dimensions[i][0], m = matrix_dimensions[i][1];
+
+ init_rs_vand(k, m);
+
+ int make_systematic_res = test_make_systematic_matrix(k, m);
+ if (!make_systematic_res) {
+ fprintf(stderr, "Error running make systematic matrix for k=%d, m=%d\n", k, m);
+ return 1;
+ }
+
+ int invert_res = test_invert_systematic_matrix(k, m, m);
+ if (!invert_res) {
+ fprintf(stderr, "Error running inversion test for k=%d, m=%d\n", k, m);
+ return 1;
+ }
+
+ int enc_dec_res = test_encode_decode(k, m, m, blocksize);
+ if (!enc_dec_res) {
+ fprintf(stderr, "Error running encode/decode test for k=%d, m=%d, bs=%d\n", k, m, blocksize);
+ return 1;
+ }
+
+ int reconstr_res = test_reconstruct(k, m, m, blocksize);
+ if (!reconstr_res) {
+ fprintf(stderr, "Error running reconstruction test for k=%d, m=%d, bs=%d\n", k, m, blocksize);
+ return 1;
+ }
+
+
+ deinit_rs_vand(k, m);
+ i++;
+ }
+
+ return 0;
+}