Creating an internal Vandermonde-based encoder/decoder.

This is pretty unoptimized and should only be used by folks
not wanting Jerasure (optimized for both Intel and ARM) or ISA-L
(optimized for Intel).

3 files changed, 96 insertions, 6 deletions

diff --git a/include/erasurecode/erasurecode.h b/include/erasurecode/erasurecode.h
index 4604c2a..cfceb7b 100644
--- a/include/erasurecode/erasurecode.h
+++ b/include/erasurecode/erasurecode.h
@@ -40,12 +40,13 @@ extern "C" {
 /* =~=*=~==~=*=~==~=*=~= Supported EC backends =~=*=~==~=*=~==~=*=~==~=*=~== */
 
 typedef enum {
-    EC_BACKEND_NULL                 = 0,
-    EC_BACKEND_JERASURE_RS_VAND     = 1,
-    EC_BACKEND_JERASURE_RS_CAUCHY   = 2,
-    EC_BACKEND_FLAT_XOR_HD          = 3,
-    EC_BACKEND_ISA_L_RS_VAND        = 4,
-    EC_BACKEND_SHSS                 = 5,
+    EC_BACKEND_NULL                   = 0,
+    EC_BACKEND_JERASURE_RS_VAND       = 1,
+    EC_BACKEND_JERASURE_RS_CAUCHY     = 2,
+    EC_BACKEND_FLAT_XOR_HD            = 3,
+    EC_BACKEND_ISA_L_RS_VAND          = 4,
+    EC_BACKEND_SHSS                   = 5,
+    EC_BACKEND_LIBERASURECODE_RS_VAND = 6,
     EC_BACKENDS_MAX,
 } ec_backend_id_t;
 
diff --git a/include/rs_vand/rs_galois.h b/include/rs_vand/rs_galois.h
new file mode 100644
index 0000000..f17bbd3
--- /dev/null
+++ b/include/rs_vand/rs_galois.h
@@ -0,0 +1,45 @@
+/* 
+ * 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:
+ */
+
+// DISCLAIMER: This is a totally basic implementation of RS used if a user does not
+// want to install one of the supported backends, such as Jerasure and ISA-L.
+// This is not expected to perform as well as the other supported backends,
+// but does not make any assumptions about the host system.  Using a library
+// like Jerasure with GF-Complete will give users the ability to tune to their
+// architecture (Intel or ARM), CPU and memory (lots of options).
+
+// We are only implementing w=16 here.  If you want to use something
+// else, then use Jerasure with GF-Complete or ISA-L.
+#define PRIM_POLY 0x1100b
+#define FIELD_SIZE (1 << 16)
+#define GROUP_SIZE (FIELD_SIZE - 1)
+
+void rs_galois_init_tables();
+void rs_galois_deinit_tables();
+int rs_galois_mult(int x, int y);
+int rs_galois_div(int x, int y);
+int rs_galois_inverse(int x);
+
diff --git a/include/rs_vand/rs_vand_internal.h b/include/rs_vand/rs_vand_internal.h
new file mode 100644
index 0000000..a9e26a0
--- /dev/null
+++ b/include/rs_vand/rs_vand_internal.h
@@ -0,0 +1,44 @@
+/*
+ * 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:
+ */
+
+int* create_non_systematic_vand_matrix(int k, int m);
+void free_systematic_matrix(int *matrix);
+int* make_systematic_matrix(int k, int m);
+int is_missing(int *missing_idxs, int index_to_check);
+int gaussj_inversion(int *matrix, int *inverse, int n);
+int get_non_zero_diagonal(int *matrix, int row, int num_rows, int num_cols);
+int rs_galois_div(int x, int y);
+int rs_galois_inverse(int x);
+int rs_galois_mult(int x, int y);
+void init_rs_vand(int k, int m);
+void deinit_rs_vand();
+void print_matrix(int *matrix, int rows, int cols);
+void square_matrix_multiply(int *m1, int *m2, int *prod, int n);
+int create_decoding_matrix(int *gen_matrix, int *dec_matrix, int *missing_idxs, int k, int m);
+int is_identity_matrix(int *matrix, int n);
+int liberasurecode_rs_vand_encode(int *generator_matrix, char **data, char **parity, int k, int m, int blocksize);
+int liberasurecode_rs_vand_decode(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int blocksize, int rebuild_parity);
+int liberasurecode_rs_vand_reconstruct(int *generator_matrix, char **data, char **parity, int k, int m, int *missing, int destination_idx, int blocksize);