diff options
-rw-r--r-- | Makefile.am | 12 | ||||
-rw-r--r-- | configure.ac | 18 | ||||
-rw-r--r-- | include/config.h.in | 3 | ||||
-rw-r--r-- | include/erasurecode/galois.h (renamed from src/utils/chksum/galois.h) | 14 | ||||
-rw-r--r-- | src/backends/xor/.dirstamp | 0 | ||||
-rw-r--r-- | src/utils/chksum/Makefile.am | 4 | ||||
-rw-r--r-- | src/utils/chksum/galois.c | 351 |
7 files changed, 386 insertions, 16 deletions
diff --git a/Makefile.am b/Makefile.am index 6cf8ebb..3f276e8 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,3 +1,6 @@ +# Top-level liberasurecode automake configuration +SUBDIRS = src/utils/chksum + ACLOCAL_AMFLAGS = -I m4 if DEBUG @@ -34,26 +37,27 @@ libXorcode_la_LDFLAGS = -rpath '$(libdir)' -version-info 1:1:0 liberasurecode_la_SOURCES = \ src/main.c \ src/backends/xor/flat_xor_3.c \ + src/utils/chksum/galois.c \ src/utils/chksum/crc32.c \ src/utils/chksum/alg_sig.c -liberasurecode_la_LIBADD = -lXorcode +liberasurecode_la_LIBADD = -lXorcode -lgf_complete # Version format (C - A).(A).(R) for C:R:A input liberasurecode_la_LDFLAGS = -rpath '$(libdir)' -version-info 9:4:9 -noinst_HEADERS = tests/test_xor_hd_code.h +noinst_HEADERS = test/builtin/xor_codes/test_xor_hd_code.h noinst_PROGRAMS = test_xor_hd_code alg_sig_test test_xor_hd_code_SOURCES = \ test/builtin/xor_codes/test_xor_hd_code.c \ test/builtin/xor_codes/test_xor_hd_code.h -test_xor_hd_code_LDFLAGS = -lerasurecode -lXorcode +test_xor_hd_code_LDFLAGS = -lerasurecode -lXorcode -lgf_complete check_PROGRAMS = test_xor_hd_code alg_sig_test_SOURCES = test/utils/chksum/test_alg_sig.c -alg_sig_test_LDFLAGS = -lerasurecode -lXorcode +alg_sig_test_LDFLAGS = -lerasurecode -lXorcode -lgf_complete check_PROGRAMS += alg_sig_test test: check diff --git a/configure.ac b/configure.ac index 65f22f0..4a9695e 100644 --- a/configure.ac +++ b/configure.ac @@ -9,7 +9,6 @@ AC_PREREQ([2.61]) AM_INIT_AUTOMAKE([subdir-objects no-dependencies]) LT_INIT # libtool -AC_CONFIG_SRCDIR(src) AC_CONFIG_HEADER(include/config.h) # Making releases: @@ -79,6 +78,15 @@ AC_CHECK_HEADERS(sys/types.h stdio.h stdlib.h stddef.h stdarg.h \ stdint.h ctype.h math.h iconv.h signal.h dlfcn.h) AC_CHECK_FUNCS(malloc calloc realloc free) +# Enable this check when gf_complete is external +AC_CHECK_LIB([gf_complete], [gf_init_easy], [], +[ + echo "Error! You need to have gf_complete installed." + echo "gf_complete is available from https://bitbucket.org/jimplank/gf-complete.git" + exit -1 +]) + + # C sources SOURCES="$SOURCES $srcdir/src/*.c" SOURCES="$SOURCES $srcdir/src/backends/null/*.c" @@ -116,7 +124,9 @@ AC_SUBST(EXTRA_CFLAGS) AC_SUBST(BUILD_LDFLAGS) AC_SUBST(EXTRA_LDFLAGS) -AC_OUTPUT(Makefile) -AC_OUTPUT(erasurecode.pc) -AC_OUTPUT(Xorcode.pc) +AC_CONFIG_FILES([Makefile \ + src/utils/chksum/Makefile \ + erasurecode.pc \ + Xorcode.pc]) +AC_OUTPUT diff --git a/include/config.h.in b/include/config.h.in index a0c15b4..462461b 100644 --- a/include/config.h.in +++ b/include/config.h.in @@ -39,6 +39,9 @@ /* Define to 1 if you have the <liberation.h> header file. */ #undef HAVE_LIBERATION_H +/* Define to 1 if you have the `gf_complete' library (-lgf_complete). */ +#undef HAVE_LIBGF_COMPLETE + /* Define to 1 if you have the `malloc' function. */ #undef HAVE_MALLOC diff --git a/src/utils/chksum/galois.h b/include/erasurecode/galois.h index 4a2715e..d75be6a 100644 --- a/src/utils/chksum/galois.h +++ b/include/erasurecode/galois.h @@ -37,14 +37,13 @@ * POSSIBILITY OF SUCH DAMAGE. */ -#pragma once -#include <stdint.h> -#include <gf_complete.h> +#ifndef _GALOIS_H +#define _GALOIS_H -#ifdef __cplusplus -extern "C" { -#endif +#include <stdio.h> +#include <stdlib.h> +#include <gf_complete.h> extern void galois_change_technique(gf_t *gf, int w); @@ -96,6 +95,5 @@ gf_t* galois_init_composite_field(int w, gf_t * galois_get_field_ptr(int w); -#ifdef __cplusplus -} + #endif diff --git a/src/backends/xor/.dirstamp b/src/backends/xor/.dirstamp deleted file mode 100644 index e69de29..0000000 --- a/src/backends/xor/.dirstamp +++ /dev/null diff --git a/src/utils/chksum/Makefile.am b/src/utils/chksum/Makefile.am new file mode 100644 index 0000000..d89c380 --- /dev/null +++ b/src/utils/chksum/Makefile.am @@ -0,0 +1,4 @@ +INCLUDES=-I./ -I../../../include +AM_CFLAGS = -O3 $(SIMD_FLAGS) -fPIC $(INCLUDES) + +SOURCES = crc32.c alg_sig.c galois.c diff --git a/src/utils/chksum/galois.c b/src/utils/chksum/galois.c new file mode 100644 index 0000000..2cfa284 --- /dev/null +++ b/src/utils/chksum/galois.c @@ -0,0 +1,351 @@ +/* * + * Copyright (c) 2014, James S. Plank and Kevin Greenan + * All rights reserved. + * + * Jerasure - A C/C++ Library for a Variety of Reed-Solomon and RAID-6 Erasure + * Coding Techniques + * + * Revision 2.0: Galois Field backend now links to GF-Complete + * + * 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. + * + * - Neither the name of the University of Tennessee nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * 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. + */ + +/* Jerasure's authors: + + Revision 2.x - 2014: James S. Plank and Kevin M. Greenan + Revision 1.2 - 2008: James S. Plank, Scott Simmerman and Catherine D. Schuman. + Revision 1.0 - 2007: James S. Plank + */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "galois.h" + +#define MAX_GF_INSTANCES 64 +gf_t *gfp_array[MAX_GF_INSTANCES] = { 0 }; +int gfp_is_composite[MAX_GF_INSTANCES] = { 0 }; + +gf_t *galois_get_field_ptr(int w) +{ + if (gfp_array[w] != NULL) { + return gfp_array[w]; + } + + return NULL; +} + +gf_t* galois_init_field(int w, + int mult_type, + int region_type, + int divide_type, + uint64_t prim_poly, + int arg1, + int arg2) +{ + int scratch_size; + void *scratch_memory; + gf_t *gfp; + + if (w <= 0 || w > 32) { + fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w); + exit(1); + } + + gfp = (gf_t *) malloc(sizeof(gf_t)); + if (!gfp) { + fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w); + exit(1); + } + + scratch_size = gf_scratch_size(w, mult_type, region_type, divide_type, arg1, arg2); + if (!scratch_size) { + fprintf(stderr, "ERROR -- cannot get scratch size for base field w=%d\n", w); + exit(1); + } + + scratch_memory = malloc(scratch_size); + if (!scratch_memory) { + fprintf(stderr, "ERROR -- cannot get scratch memory for base field w=%d\n", w); + exit(1); + } + + if(!gf_init_hard(gfp, + w, + mult_type, + region_type, + divide_type, + prim_poly, + arg1, + arg2, + NULL, + scratch_memory)) + { + fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w); + exit(1); + } + + gfp_is_composite[w] = 0; + return gfp; +} + +gf_t* galois_init_composite_field(int w, + int region_type, + int divide_type, + int degree, + gf_t* base_gf) +{ + int scratch_size; + void *scratch_memory; + gf_t *gfp; + + if (w <= 0 || w > 32) { + fprintf(stderr, "ERROR -- cannot init composite field for w=%d\n", w); + exit(1); + } + + gfp = (gf_t *) malloc(sizeof(gf_t)); + if (!gfp) { + fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w); + exit(1); + } + + scratch_size = gf_scratch_size(w, GF_MULT_COMPOSITE, region_type, divide_type, degree, 0); + if (!scratch_size) { + fprintf(stderr, "ERROR -- cannot get scratch size for composite field w=%d\n", w); + exit(1); + } + + scratch_memory = malloc(scratch_size); + if (!scratch_memory) { + fprintf(stderr, "ERROR -- cannot get scratch memory for composite field w=%d\n", w); + exit(1); + } + + if(!gf_init_hard(gfp, + w, + GF_MULT_COMPOSITE, + region_type, + divide_type, + 0, + degree, + 0, + base_gf, + scratch_memory)) + { + fprintf(stderr, "ERROR -- cannot init default composite field for w=%d\n", w); + exit(1); + } + gfp_is_composite[w] = 1; + return gfp; +} + +static void galois_init_default_field(int w) +{ + if (w <= 0 || w > 32) { + fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w); + exit(1); + } + + if (gfp_array[w] == NULL) { + gfp_array[w] = (gf_t*)malloc(sizeof(gf_t)); + if (gfp_array[w] == NULL) { + fprintf(stderr, "ERROR -- cannot allocate memory for Galois field w=%d\n", w); + exit(1); + } + } + + if (!gf_init_easy(gfp_array[w], w)) { + fprintf(stderr, "ERROR -- cannot init default Galois field for w=%d\n", w); + exit(1); + } +} + + +static int is_valid_gf(gf_t *gf, int w) +{ + // TODO: I assume we may eventually + // want to do w=64 and 128, so w + // will be needed to perform this check + (void)w; + + if (gf == NULL) { + return 0; + } + if (gf->multiply.w32 == NULL) { + return 0; + } + if (gf->multiply_region.w32 == NULL) { + return 0; + } + if (gf->divide.w32 == NULL) { + return 0; + } + if (gf->inverse.w32 == NULL) { + return 0; + } + if (gf->extract_word.w32 == NULL) { + return 0; + } + + return 1; +} + +void galois_change_technique(gf_t *gf, int w) +{ + if (w <= 0 || w > 32) { + fprintf(stderr, "ERROR -- cannot support Galois field for w=%d\n", w); + exit(1); + } + + if (!is_valid_gf(gf, w)) { + fprintf(stderr, "ERROR -- overriding with invalid Galois field for w=%d\n", w); + exit(1); + } + + if (gfp_array[w] != NULL) { + gf_free(gfp_array[w], gfp_is_composite[w]); + } + + gfp_array[w] = gf; +} + +int galois_single_multiply(int x, int y, int w) +{ + if (x == 0 || y == 0) return 0; + + if (gfp_array[w] == NULL) { + galois_init_default_field(w); + } + + if (w <= 32) { + return gfp_array[w]->multiply.w32(gfp_array[w], x, y); + } else { + fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w); + } +} + +int galois_single_divide(int x, int y, int w) +{ + if (x == 0) return 0; + if (y == 0) return -1; + + if (gfp_array[w] == NULL) { + galois_init_default_field(w); + } + + if (w <= 32) { + return gfp_array[w]->divide.w32(gfp_array[w], x, y); + } else { + fprintf(stderr, "ERROR -- Galois field not implemented for w=%d\n", w); + } +} + +void galois_w08_region_multiply(char *region, /* Region to multiply */ + int multby, /* Number to multiply by */ + int nbytes, /* Number of bytes in region */ + char *r2, /* If r2 != NULL, products go here */ + int add) +{ + if (gfp_array[8] == NULL) { + galois_init_default_field(8); + } + gfp_array[8]->multiply_region.w32(gfp_array[8], region, r2, multby, nbytes, add); +} + +void galois_w16_region_multiply(char *region, /* Region to multiply */ + int multby, /* Number to multiply by */ + int nbytes, /* Number of bytes in region */ + char *r2, /* If r2 != NULL, products go here */ + int add) +{ + if (gfp_array[16] == NULL) { + galois_init_default_field(16); + } + gfp_array[16]->multiply_region.w32(gfp_array[16], region, r2, multby, nbytes, add); +} + + +void galois_w32_region_multiply(char *region, /* Region to multiply */ + int multby, /* Number to multiply by */ + int nbytes, /* Number of bytes in region */ + char *r2, /* If r2 != NULL, products go here */ + int add) +{ + if (gfp_array[32] == NULL) { + galois_init_default_field(32); + } + gfp_array[32]->multiply_region.w32(gfp_array[32], region, r2, multby, nbytes, add); +} + +void galois_w8_region_xor(void *src, void *dest, int nbytes) +{ + if (gfp_array[8] == NULL) { + galois_init_default_field(8); + } + gfp_array[8]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1); +} + +void galois_w16_region_xor(void *src, void *dest, int nbytes) +{ + if (gfp_array[16] == NULL) { + galois_init_default_field(16); + } + gfp_array[16]->multiply_region.w32(gfp_array[16], src, dest, 1, nbytes, 1); +} + +void galois_w32_region_xor(void *src, void *dest, int nbytes) +{ + if (gfp_array[32] == NULL) { + galois_init_default_field(32); + } + gfp_array[32]->multiply_region.w32(gfp_array[32], src, dest, 1, nbytes, 1); +} + +void galois_region_xor(char *src, char *dest, int nbytes) +{ + if (nbytes >= 16) { + galois_w32_region_xor(src, dest, nbytes); + } else { + int i = 0; + for (i = 0; i < nbytes; i++) { + *dest ^= *src; + dest++; + src++; + } + } +} + +int galois_inverse(int y, int w) +{ + if (y == 0) return -1; + return galois_single_divide(1, y, w); +} |