diff options
Diffstat (limited to 'src/erasure-code/jerasure/gf-complete/include')
11 files changed, 892 insertions, 0 deletions
diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_complete.h b/src/erasure-code/jerasure/gf-complete/include/gf_complete.h new file mode 100644 index 000000000..c4783e80a --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_complete.h @@ -0,0 +1,204 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_complete.h + * + * The main include file for gf_complete. + */ + +#ifndef _GF_COMPLETE_H_ +#define _GF_COMPLETE_H_ +#include <stdint.h> + +#ifdef INTEL_SSE4 + #ifdef __SSE4_2__ + #include <nmmintrin.h> + #endif + #ifdef __SSE4_1__ + #include <smmintrin.h> + #endif +#endif + +#ifdef INTEL_SSSE3 + #include <tmmintrin.h> +#endif + +#ifdef INTEL_SSE2 + #include <emmintrin.h> +#endif + +#ifdef INTEL_SSE4_PCLMUL + #include <wmmintrin.h> +#endif + +#if defined(ARM_NEON) + #include <arm_neon.h> +#endif + + +/* These are the different ways to perform multiplication. + Not all are implemented for all values of w. + See the paper for an explanation of how they work. */ + +typedef enum {GF_MULT_DEFAULT, + GF_MULT_SHIFT, + GF_MULT_CARRY_FREE, + GF_MULT_CARRY_FREE_GK, + GF_MULT_GROUP, + GF_MULT_BYTWO_p, + GF_MULT_BYTWO_b, + GF_MULT_TABLE, + GF_MULT_LOG_TABLE, + GF_MULT_LOG_ZERO, + GF_MULT_LOG_ZERO_EXT, + GF_MULT_SPLIT_TABLE, + GF_MULT_COMPOSITE } gf_mult_type_t; + +/* These are the different ways to optimize region + operations. They are bits because you can compose them. + Certain optimizations only apply to certain gf_mult_type_t's. + Again, please see documentation for how to use these */ + +#define GF_REGION_DEFAULT (0x0) +#define GF_REGION_DOUBLE_TABLE (0x1) +#define GF_REGION_QUAD_TABLE (0x2) +#define GF_REGION_LAZY (0x4) +#define GF_REGION_SIMD (0x8) +#define GF_REGION_SSE (0x8) +#define GF_REGION_NOSIMD (0x10) +#define GF_REGION_NOSSE (0x10) +#define GF_REGION_ALTMAP (0x20) +#define GF_REGION_CAUCHY (0x40) + +typedef uint32_t gf_region_type_t; + +/* These are different ways to implement division. + Once again, it's best to use "DEFAULT". However, + there are times when you may want to experiment + with the others. */ + +typedef enum { GF_DIVIDE_DEFAULT, + GF_DIVIDE_MATRIX, + GF_DIVIDE_EUCLID } gf_division_type_t; + +/* We support w=4,8,16,32,64 and 128 with their own data types and + operations for multiplication, division, etc. We also support + a "gen" type so that you can do general gf arithmetic for any + value of w from 1 to 32. You can perform a "region" operation + on these if you use "CAUCHY" as the mapping. + */ + +typedef uint32_t gf_val_32_t; +typedef uint64_t gf_val_64_t; +typedef uint64_t *gf_val_128_t; + +extern int _gf_errno; +extern void gf_error(); + +typedef struct gf *GFP; + +typedef union gf_func_a_b { + gf_val_32_t (*w32) (GFP gf, gf_val_32_t a, gf_val_32_t b); + gf_val_64_t (*w64) (GFP gf, gf_val_64_t a, gf_val_64_t b); + void (*w128)(GFP gf, gf_val_128_t a, gf_val_128_t b, gf_val_128_t c); +} gf_func_a_b; + +typedef union { + gf_val_32_t (*w32) (GFP gf, gf_val_32_t a); + gf_val_64_t (*w64) (GFP gf, gf_val_64_t a); + void (*w128)(GFP gf, gf_val_128_t a, gf_val_128_t b); +} gf_func_a; + +typedef union { + void (*w32) (GFP gf, void *src, void *dest, gf_val_32_t val, int bytes, int add); + void (*w64) (GFP gf, void *src, void *dest, gf_val_64_t val, int bytes, int add); + void (*w128)(GFP gf, void *src, void *dest, gf_val_128_t val, int bytes, int add); +} gf_region; + +typedef union { + gf_val_32_t (*w32) (GFP gf, void *start, int bytes, int index); + gf_val_64_t (*w64) (GFP gf, void *start, int bytes, int index); + void (*w128)(GFP gf, void *start, int bytes, int index, gf_val_128_t rv); +} gf_extract; + +typedef struct gf { + gf_func_a_b multiply; + gf_func_a_b divide; + gf_func_a inverse; + gf_region multiply_region; + gf_extract extract_word; + void *scratch; +} gf_t; + +/* Initializes the GF to defaults. Pass it a pointer to a gf_t. + Returns 0 on failure, 1 on success. */ + +extern int gf_init_easy(GFP gf, int w); + +/* Initializes the GF changing the defaults. + Returns 0 on failure, 1 on success. + Pass it a pointer to a gf_t. + For mult_type and divide_type, use one of gf_mult_type_t gf_divide_type_t . + For region_type, OR together the GF_REGION_xxx's defined above. + Use 0 as prim_poly for defaults. Otherwise, the leading 1 is optional. + Use NULL for scratch_memory to have init_hard allocate memory. Otherwise, + use gf_scratch_size() to determine how big scratch_memory has to be. + */ + +extern int gf_init_hard(GFP gf, + int w, + int mult_type, + int region_type, + int divide_type, + uint64_t prim_poly, + int arg1, + int arg2, + GFP base_gf, + void *scratch_memory); + +/* Determines the size for scratch_memory. + Returns 0 on failure and non-zero on success. */ + +extern int gf_scratch_size(int w, + int mult_type, + int region_type, + int divide_type, + int arg1, + int arg2); + +/* This reports the gf_scratch_size of a gf_t that has already been created */ + +extern int gf_size(GFP gf); + +/* Frees scratch memory if gf_init_easy/gf_init_hard called malloc. + If recursive = 1, then it calls itself recursively on base_gf. */ + +extern int gf_free(GFP gf, int recursive); + +/* This is support for inline single multiplications and divisions. + I know it's yucky, but if you've got to be fast, you've got to be fast. + We support inlining for w=4, w=8 and w=16. + + To use inline multiplication and division with w=4 or 8, you should use the + default gf_t, or one with a single table. Otherwise, gf_w4/8_get_mult_table() + will return NULL. Similarly, with w=16, the gf_t must be LOG */ + +uint8_t *gf_w4_get_mult_table(GFP gf); +uint8_t *gf_w4_get_div_table(GFP gf); + +#define GF_W4_INLINE_MULTDIV(table, a, b) (table[((a)<<4)|(b)]) + +uint8_t *gf_w8_get_mult_table(GFP gf); +uint8_t *gf_w8_get_div_table(GFP gf); + +#define GF_W8_INLINE_MULTDIV(table, a, b) (table[(((uint32_t) (a))<<8)|(b)]) + +uint16_t *gf_w16_get_log_table(GFP gf); +uint16_t *gf_w16_get_mult_alog_table(GFP gf); +uint16_t *gf_w16_get_div_alog_table(GFP gf); + +#define GF_W16_INLINE_MULT(log, alog, a, b) ((a) == 0 || (b) == 0) ? 0 : (alog[(uint32_t)log[a]+(uint32_t)log[b]]) +#define GF_W16_INLINE_DIV(log, alog, a, b) ((a) == 0 || (b) == 0) ? 0 : (alog[(int)log[a]-(int)log[b]]) +#endif diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_cpu.h b/src/erasure-code/jerasure/gf-complete/include/gf_cpu.h new file mode 100644 index 000000000..71c722706 --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_cpu.h @@ -0,0 +1,20 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_cpu.h + * + * Identifies whether the CPU supports SIMD instructions at runtime. + */ + +#pragma once + +extern int gf_cpu_supports_intel_pclmul; +extern int gf_cpu_supports_intel_sse4; +extern int gf_cpu_supports_intel_ssse3; +extern int gf_cpu_supports_intel_sse3; +extern int gf_cpu_supports_intel_sse2; +extern int gf_cpu_supports_arm_neon; + +void gf_cpu_identify(void); diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_general.h b/src/erasure-code/jerasure/gf-complete/include/gf_general.h new file mode 100644 index 000000000..9a5de529d --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_general.h @@ -0,0 +1,61 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_general.h + * + * This file has helper routines for doing basic GF operations with any + * legal value of w. The problem is that w <= 32, w=64 and w=128 all have + * different data types, which is a pain. The procedures in this file try + * to alleviate that pain. They are used in gf_unit and gf_time. + */ + +#pragma once + +#include <stdio.h> +#include <getopt.h> +#include <stdint.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> + +#include "gf_complete.h" + +typedef union { + uint32_t w32; + uint64_t w64; + uint64_t w128[2]; +} gf_general_t; + +void gf_general_set_zero(gf_general_t *v, int w); +void gf_general_set_one(gf_general_t *v, int w); +void gf_general_set_two(gf_general_t *v, int w); + +int gf_general_is_zero(gf_general_t *v, int w); +int gf_general_is_one(gf_general_t *v, int w); +int gf_general_are_equal(gf_general_t *v1, gf_general_t *v2, int w); + +void gf_general_val_to_s(gf_general_t *v, int w, char *s, int hex); +int gf_general_s_to_val(gf_general_t *v, int w, char *s, int hex); + +void gf_general_set_random(gf_general_t *v, int w, int zero_ok); + +void gf_general_add(gf_t *gf, gf_general_t *a, gf_general_t *b, gf_general_t *c); +void gf_general_multiply(gf_t *gf, gf_general_t *a, gf_general_t *b, gf_general_t *c); +void gf_general_divide(gf_t *gf, gf_general_t *a, gf_general_t *b, gf_general_t *c); +void gf_general_inverse(gf_t *gf, gf_general_t *a, gf_general_t *b); + +void gf_general_do_region_multiply(gf_t *gf, gf_general_t *a, + void *ra, void *rb, + int bytes, int xor); + +void gf_general_do_region_check(gf_t *gf, gf_general_t *a, + void *orig_a, void *orig_target, void *final_target, + int bytes, int xor); + + +/* Which is M, D or I for multiply, divide or inverse. */ + +void gf_general_set_up_single_timing_test(int w, void *ra, void *rb, int size); +int gf_general_do_single_timing_test(gf_t *gf, void *ra, void *rb, int size, char which); diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_int.h b/src/erasure-code/jerasure/gf-complete/include/gf_int.h new file mode 100644 index 000000000..0356920fd --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_int.h @@ -0,0 +1,216 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_int.h + * + * Internal code for Galois field routines. This is not meant for + * users to include, but for the internal GF files to use. + */ + +#pragma once + +#include "gf_complete.h" + +#include <string.h> + +extern void timer_start (double *t); +extern double timer_split (const double *t); +extern void galois_fill_random (void *buf, int len, unsigned int seed); + +typedef struct { + int mult_type; + int region_type; + int divide_type; + int w; + uint64_t prim_poly; + int free_me; + int arg1; + int arg2; + gf_t *base_gf; + void *private; +#ifdef DEBUG_FUNCTIONS + const char *multiply; + const char *divide; + const char *inverse; + const char *multiply_region; + const char *extract_word; +#endif +} gf_internal_t; + +#ifdef DEBUG_FUNCTIONS +#define SET_FUNCTION(gf,method,size,func) \ + { (gf)->method.size = (func); \ + ((gf_internal_t*)(gf)->scratch)->method = #func; } +#else +#define SET_FUNCTION(gf,method,size,func) \ + (gf)->method.size = (func); +#endif + +extern int gf_w4_init (gf_t *gf); +extern int gf_w4_scratch_size(int mult_type, int region_type, int divide_type, int arg1, int arg2); + +extern int gf_w8_init (gf_t *gf); +extern int gf_w8_scratch_size(int mult_type, int region_type, int divide_type, int arg1, int arg2); + +extern int gf_w16_init (gf_t *gf); +extern int gf_w16_scratch_size(int mult_type, int region_type, int divide_type, int arg1, int arg2); + +extern int gf_w32_init (gf_t *gf); +extern int gf_w32_scratch_size(int mult_type, int region_type, int divide_type, int arg1, int arg2); + +extern int gf_w64_init (gf_t *gf); +extern int gf_w64_scratch_size(int mult_type, int region_type, int divide_type, int arg1, int arg2); + +extern int gf_w128_init (gf_t *gf); +extern int gf_w128_scratch_size(int mult_type, int region_type, int divide_type, int arg1, int arg2); + +extern int gf_wgen_init (gf_t *gf); +extern int gf_wgen_scratch_size(int w, int mult_type, int region_type, int divide_type, int arg1, int arg2); + +void gf_wgen_cauchy_region(gf_t *gf, void *src, void *dest, gf_val_32_t val, int bytes, int xor); +gf_val_32_t gf_wgen_extract_word(gf_t *gf, void *start, int bytes, int index); + +extern void gf_alignment_error(char *s, int a); + +extern uint32_t gf_bitmatrix_inverse(uint32_t y, int w, uint32_t pp); + +/* This returns the correct default for prim_poly when base is used as the base + field for COMPOSITE. It returns 0 if we don't have a default prim_poly. */ + +extern uint64_t gf_composite_get_default_poly(gf_t *base); + +/* This structure lets you define a region multiply. It helps because you can handle + unaligned portions of the data with the procedures below, which really cleans + up the code. */ + +typedef struct { + gf_t *gf; + void *src; + void *dest; + int bytes; + uint64_t val; + int xor; + int align; /* The number of bytes to which to align. */ + void *s_start; /* The start and the top of the aligned region. */ + void *d_start; + void *s_top; + void *d_top; +} gf_region_data; + +/* This lets you set up one of these in one call. It also sets the start/top pointers. */ + +void gf_set_region_data(gf_region_data *rd, + gf_t *gf, + void *src, + void *dest, + int bytes, + uint64_t val, + int xor, + int align); + +/* This performs gf->multiply.32() on all of the unaligned bytes in the beginning of the region */ + +extern void gf_do_initial_region_alignment(gf_region_data *rd); + +/* This performs gf->multiply.32() on all of the unaligned bytes in the end of the region */ + +extern void gf_do_final_region_alignment(gf_region_data *rd); + +extern void gf_two_byte_region_table_multiply(gf_region_data *rd, uint16_t *base); + +extern void gf_multby_zero(void *dest, int bytes, int xor); +extern void gf_multby_one(void *src, void *dest, int bytes, int xor); + +typedef enum {GF_E_MDEFDIV, /* Dev != Default && Mult == Default */ + GF_E_MDEFREG, /* Reg != Default && Mult == Default */ + GF_E_MDEFARG, /* Args != Default && Mult == Default */ + GF_E_DIVCOMP, /* Mult == Composite && Div != Default */ + GF_E_CAUCOMP, /* Mult == Composite && Reg == CAUCHY */ + GF_E_DOUQUAD, /* Reg == DOUBLE && Reg == QUAD */ + GF_E_SIMD_NO, /* Reg == SIMD && Reg == NOSIMD */ + GF_E_CAUCHYB, /* Reg == CAUCHY && Other Reg */ + GF_E_CAUGT32, /* Reg == CAUCHY && w > 32*/ + GF_E_ARG1SET, /* Arg1 != 0 && Mult \notin COMPOSITE/SPLIT/GROUP */ + GF_E_ARG2SET, /* Arg2 != 0 && Mult \notin SPLIT/GROUP */ + GF_E_MATRIXW, /* Div == MATRIX && w > 32 */ + GF_E_BAD___W, /* Illegal w */ + GF_E_DOUBLET, /* Reg == DOUBLE && Mult != TABLE */ + GF_E_DOUBLEW, /* Reg == DOUBLE && w \notin {4,8} */ + GF_E_DOUBLEJ, /* Reg == DOUBLE && other Reg */ + GF_E_DOUBLEL, /* Reg == DOUBLE & LAZY but w = 4 */ + GF_E_QUAD__T, /* Reg == QUAD && Mult != TABLE */ + GF_E_QUAD__W, /* Reg == QUAD && w != 4 */ + GF_E_QUAD__J, /* Reg == QUAD && other Reg */ + GF_E_LAZY__X, /* Reg == LAZY && not DOUBLE or QUAD*/ + GF_E_ALTSHIF, /* Mult == Shift && Reg == ALTMAP */ + GF_E_SSESHIF, /* Mult == Shift && Reg == SIMD|NOSIMD */ + GF_E_ALT_CFM, /* Mult == CARRY_FREE && Reg == ALTMAP */ + GF_E_SSE_CFM, /* Mult == CARRY_FREE && Reg == SIMD|NOSIMD */ + GF_E_PCLMULX, /* Mult == Carry_Free && No PCLMUL */ + GF_E_ALT_BY2, /* Mult == Bytwo_x && Reg == ALTMAP */ + GF_E_BY2_SSE, /* Mult == Bytwo_x && Reg == SSE && No SSE2 */ + GF_E_LOGBADW, /* Mult == LOGx, w too big*/ + GF_E_LOG___J, /* Mult == LOGx, && Reg == SSE|ALTMAP|NOSSE */ + GF_E_ZERBADW, /* Mult == LOG_ZERO, w \notin {8,16} */ + GF_E_ZEXBADW, /* Mult == LOG_ZERO_EXT, w != 8 */ + GF_E_LOGPOLY, /* Mult == LOG & poly not primitive */ + GF_E_GR_ARGX, /* Mult == GROUP, Bad arg1/2 */ + GF_E_GR_W_48, /* Mult == GROUP, w \in { 4, 8 } */ + GF_E_GR_W_16, /* Mult == GROUP, w == 16, arg1 != 4 || arg2 != 4 */ + GF_E_GR_128A, /* Mult == GROUP, w == 128, bad args */ + GF_E_GR_A_27, /* Mult == GROUP, either arg > 27 */ + GF_E_GR_AR_W, /* Mult == GROUP, either arg > w */ + GF_E_GR____J, /* Mult == GROUP, Reg == SSE|ALTMAP|NOSSE */ + GF_E_TABLE_W, /* Mult == TABLE, w too big */ + GF_E_TAB_SSE, /* Mult == TABLE, SIMD|NOSIMD only apply to w == 4 */ + GF_E_TABSSE3, /* Mult == TABLE, Need SSSE3 for SSE */ + GF_E_TAB_ALT, /* Mult == TABLE, Reg == ALTMAP */ + GF_E_SP128AR, /* Mult == SPLIT, w=128, Bad arg1/arg2 */ + GF_E_SP128AL, /* Mult == SPLIT, w=128, SSE requires ALTMAP */ + GF_E_SP128AS, /* Mult == SPLIT, w=128, ALTMAP requires SSE */ + GF_E_SP128_A, /* Mult == SPLIT, w=128, ALTMAP only with 4/128 */ + GF_E_SP128_S, /* Mult == SPLIT, w=128, SSE only with 4/128 */ + GF_E_SPLIT_W, /* Mult == SPLIT, Bad w (8, 16, 32, 64, 128) */ + GF_E_SP_16AR, /* Mult == SPLIT, w=16, Bad arg1/arg2 */ + GF_E_SP_16_A, /* Mult == SPLIT, w=16, ALTMAP only with 4/16 */ + GF_E_SP_16_S, /* Mult == SPLIT, w=16, SSE only with 4/16 */ + GF_E_SP_32AR, /* Mult == SPLIT, w=32, Bad arg1/arg2 */ + GF_E_SP_32AS, /* Mult == SPLIT, w=32, ALTMAP requires SSE */ + GF_E_SP_32_A, /* Mult == SPLIT, w=32, ALTMAP only with 4/32 */ + GF_E_SP_32_S, /* Mult == SPLIT, w=32, SSE only with 4/32 */ + GF_E_SP_64AR, /* Mult == SPLIT, w=64, Bad arg1/arg2 */ + GF_E_SP_64AS, /* Mult == SPLIT, w=64, ALTMAP requires SSE */ + GF_E_SP_64_A, /* Mult == SPLIT, w=64, ALTMAP only with 4/64 */ + GF_E_SP_64_S, /* Mult == SPLIT, w=64, SSE only with 4/64 */ + GF_E_SP_8_AR, /* Mult == SPLIT, w=8, Bad arg1/arg2 */ + GF_E_SP_8__A, /* Mult == SPLIT, w=8, no ALTMAP */ + GF_E_SP_SSE3, /* Mult == SPLIT, Need SSSE3 for SSE */ + GF_E_COMP_A2, /* Mult == COMP, arg1 must be = 2 */ + GF_E_COMP_SS, /* Mult == COMP, SIMD|NOSIMD */ + GF_E_COMP__W, /* Mult == COMP, Bad w. */ + GF_E_UNKFLAG, /* Unknown flag in create_from.... */ + GF_E_UNKNOWN, /* Unknown mult_type. */ + GF_E_UNK_REG, /* Unknown region_type. */ + GF_E_UNK_DIV, /* Unknown divide_type. */ + GF_E_CFM___W, /* Mult == CFM, Bad w. */ + GF_E_CFM4POL, /* Mult == CFM & Prim Poly has high bits set. */ + GF_E_CFM8POL, /* Mult == CFM & Prim Poly has high bits set. */ + GF_E_CF16POL, /* Mult == CFM & Prim Poly has high bits set. */ + GF_E_CF32POL, /* Mult == CFM & Prim Poly has high bits set. */ + GF_E_CF64POL, /* Mult == CFM & Prim Poly has high bits set. */ + GF_E_FEWARGS, /* Too few args in argc/argv. */ + GF_E_BADPOLY, /* Bad primitive polynomial -- too many bits set. */ + GF_E_COMP_PP, /* Bad primitive polynomial -- bigger than sub-field. */ + GF_E_COMPXPP, /* Can't derive a default pp for composite field. */ + GF_E_BASE__W, /* Composite -- Base field is the wrong size. */ + GF_E_TWOMULT, /* In create_from... two -m's. */ + GF_E_TWO_DIV, /* In create_from... two -d's. */ + GF_E_POLYSPC, /* Bad numbera after -p. */ + GF_E_SPLITAR, /* Ran out of arguments in SPLIT */ + GF_E_SPLITNU, /* Arguments not integers in SPLIT. */ + GF_E_GROUPAR, /* Ran out of arguments in GROUP */ + GF_E_GROUPNU, /* Arguments not integers in GROUP. */ + GF_E_DEFAULT } gf_error_type_t; + diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_method.h b/src/erasure-code/jerasure/gf-complete/include/gf_method.h new file mode 100644 index 000000000..880b34967 --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_method.h @@ -0,0 +1,20 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_method.h + * + * Parses argv to figure out the flags and arguments. Creates the gf. + */ + +#pragma once + +#include "gf_complete.h" + +/* Parses argv starting at "starting". + + Returns 0 on failure. + On success, it returns one past the last argument it read in argv. */ + +extern int create_gf_from_argv(gf_t *gf, int w, int argc, char **argv, int starting); diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_rand.h b/src/erasure-code/jerasure/gf-complete/include/gf_rand.h new file mode 100644 index 000000000..24294adc7 --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_rand.h @@ -0,0 +1,22 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_rand.h + * + * Random number generation, using the "Mother of All" random number generator. */ + +#pragma once +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +/* These are all pretty self-explanatory */ +uint32_t MOA_Random_32(); +uint64_t MOA_Random_64(); +void MOA_Random_128(uint64_t *x); +uint32_t MOA_Random_W(int w, int zero_ok); +void MOA_Fill_Random_Region (void *reg, int size); /* reg should be aligned to 4 bytes, but + size can be anything. */ +void MOA_Seed(uint32_t seed); diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_w16.h b/src/erasure-code/jerasure/gf-complete/include/gf_w16.h new file mode 100644 index 000000000..fb4c0e98f --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_w16.h @@ -0,0 +1,66 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_w16.h + * + * Defines and data structures for 16-bit Galois fields + */ + +#ifndef GF_COMPLETE_GF_W16_H +#define GF_COMPLETE_GF_W16_H + +#include <stdint.h> + +#define GF_FIELD_WIDTH (16) +#define GF_FIELD_SIZE (1 << GF_FIELD_WIDTH) +#define GF_MULT_GROUP_SIZE GF_FIELD_SIZE-1 + +#define GF_BASE_FIELD_WIDTH (8) +#define GF_BASE_FIELD_SIZE (1 << GF_BASE_FIELD_WIDTH) + +struct gf_w16_logtable_data { + uint16_t log_tbl[GF_FIELD_SIZE]; + uint16_t antilog_tbl[GF_FIELD_SIZE * 2]; + uint16_t inv_tbl[GF_FIELD_SIZE]; + uint16_t *d_antilog; +}; + +struct gf_w16_zero_logtable_data { + int log_tbl[GF_FIELD_SIZE]; + uint16_t _antilog_tbl[GF_FIELD_SIZE * 4]; + uint16_t *antilog_tbl; + uint16_t inv_tbl[GF_FIELD_SIZE]; +}; + +struct gf_w16_lazytable_data { + uint16_t log_tbl[GF_FIELD_SIZE]; + uint16_t antilog_tbl[GF_FIELD_SIZE * 2]; + uint16_t inv_tbl[GF_FIELD_SIZE]; + uint16_t *d_antilog; + uint16_t lazytable[GF_FIELD_SIZE]; +}; + +struct gf_w16_bytwo_data { + uint64_t prim_poly; + uint64_t mask1; + uint64_t mask2; +}; + +struct gf_w16_split_8_8_data { + uint16_t tables[3][256][256]; +}; + +struct gf_w16_group_4_4_data { + uint16_t reduce[16]; + uint16_t shift[16]; +}; + +struct gf_w16_composite_data { + uint8_t *mult_table; +}; + +void gf_w16_neon_split_init(gf_t *gf); + +#endif /* GF_COMPLETE_GF_W16_H */ diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_w32.h b/src/erasure-code/jerasure/gf-complete/include/gf_w32.h new file mode 100644 index 000000000..7734f30ff --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_w32.h @@ -0,0 +1,71 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_w32.h + * + * Defines and data structures for 32-bit Galois fields + */ + +#ifndef GF_COMPLETE_GF_W32_H +#define GF_COMPLETE_GF_W32_H + +#include <stdint.h> + +#define GF_FIELD_WIDTH (32) +#define GF_FIRST_BIT ((gf_val_32_t)1 << 31) + +#define GF_BASE_FIELD_WIDTH (16) +#define GF_BASE_FIELD_SIZE (1 << GF_BASE_FIELD_WIDTH) +#define GF_BASE_FIELD_GROUP_SIZE GF_BASE_FIELD_SIZE-1 +#define GF_MULTBY_TWO(p) (((p) & GF_FIRST_BIT) ? (((p) << 1) ^ h->prim_poly) : (p) << 1) + +struct gf_split_2_32_lazy_data { + uint32_t tables[16][4]; + uint32_t last_value; +}; + +struct gf_w32_split_8_8_data { + uint32_t tables[7][256][256]; + uint32_t region_tables[4][256]; + uint32_t last_value; +}; + +struct gf_w32_group_data { + uint32_t *reduce; + uint32_t *shift; + int tshift; + uint64_t rmask; + uint32_t *memory; +}; + +struct gf_split_16_32_lazy_data { + uint32_t tables[2][(1<<16)]; + uint32_t last_value; +}; + +struct gf_split_8_32_lazy_data { + uint32_t tables[4][256]; + uint32_t last_value; +}; + +struct gf_split_4_32_lazy_data { + uint32_t tables[8][16]; + uint32_t last_value; +}; + +struct gf_w32_bytwo_data { + uint64_t prim_poly; + uint64_t mask1; + uint64_t mask2; +}; + +struct gf_w32_composite_data { + uint16_t *log; + uint16_t *alog; +}; + +void gf_w32_neon_split_init(gf_t *gf); + +#endif /* GF_COMPLETE_GF_W32_H */ diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_w4.h b/src/erasure-code/jerasure/gf-complete/include/gf_w4.h new file mode 100644 index 000000000..8ee94a339 --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_w4.h @@ -0,0 +1,63 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_w4.h + * + * Defines and data structures for 4-bit Galois fields + */ + +#ifndef GF_COMPLETE_GF_W4_H +#define GF_COMPLETE_GF_W4_H + +#include <stdint.h> + +#define GF_FIELD_WIDTH 4 +#define GF_DOUBLE_WIDTH (GF_FIELD_WIDTH*2) +#define GF_FIELD_SIZE (1 << GF_FIELD_WIDTH) +#define GF_MULT_GROUP_SIZE (GF_FIELD_SIZE-1) + +/* ------------------------------------------------------------ + JSP: Each implementation has its own data, which is allocated + at one time as part of the handle. For that reason, it + shouldn't be hierarchical -- i.e. one should be able to + allocate it with one call to malloc. */ + +struct gf_logtable_data { + uint8_t log_tbl[GF_FIELD_SIZE]; + uint8_t antilog_tbl[GF_FIELD_SIZE * 2]; + uint8_t *antilog_tbl_div; +}; + +struct gf_single_table_data { + uint8_t mult[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint8_t div[GF_FIELD_SIZE][GF_FIELD_SIZE]; +}; + +struct gf_double_table_data { + uint8_t div[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint8_t mult[GF_FIELD_SIZE][GF_FIELD_SIZE*GF_FIELD_SIZE]; +}; +struct gf_quad_table_data { + uint8_t div[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint16_t mult[GF_FIELD_SIZE][(1<<16)]; +}; + +struct gf_quad_table_lazy_data { + uint8_t div[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint8_t smult[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint16_t mult[(1 << 16)]; +}; + +struct gf_bytwo_data { + uint64_t prim_poly; + uint64_t mask1; + uint64_t mask2; +}; + +// ARM NEON init functions +int gf_w4_neon_cfm_init(gf_t *gf); +void gf_w4_neon_single_table_init(gf_t *gf); + +#endif /* GF_COMPLETE_GF_W4_H */ diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_w64.h b/src/erasure-code/jerasure/gf-complete/include/gf_w64.h new file mode 100644 index 000000000..9a74a8125 --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_w64.h @@ -0,0 +1,50 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_w64.h + * + * Defines and data structures for 64-bit Galois fields + */ + +#ifndef GF_COMPLETE_GF_W64_H +#define GF_COMPLETE_GF_W64_H + +#include <stdint.h> + +#define GF_FIELD_WIDTH (64) +#define GF_FIRST_BIT (1ULL << 63) + +#define GF_BASE_FIELD_WIDTH (32) +#define GF_BASE_FIELD_SIZE (1ULL << GF_BASE_FIELD_WIDTH) +#define GF_BASE_FIELD_GROUP_SIZE GF_BASE_FIELD_SIZE-1 + +struct gf_w64_group_data { + uint64_t *reduce; + uint64_t *shift; + uint64_t *memory; +}; + +struct gf_split_4_64_lazy_data { + uint64_t tables[16][16]; + uint64_t last_value; +}; + +struct gf_split_8_64_lazy_data { + uint64_t tables[8][(1<<8)]; + uint64_t last_value; +}; + +struct gf_split_16_64_lazy_data { + uint64_t tables[4][(1<<16)]; + uint64_t last_value; +}; + +struct gf_split_8_8_data { + uint64_t tables[15][256][256]; +}; + +void gf_w64_neon_split_init(gf_t *gf); + +#endif /* GF_COMPLETE_GF_W64_H */ diff --git a/src/erasure-code/jerasure/gf-complete/include/gf_w8.h b/src/erasure-code/jerasure/gf-complete/include/gf_w8.h new file mode 100644 index 000000000..938fcfdf1 --- /dev/null +++ b/src/erasure-code/jerasure/gf-complete/include/gf_w8.h @@ -0,0 +1,99 @@ +/* + * GF-Complete: A Comprehensive Open Source Library for Galois Field Arithmetic + * James S. Plank, Ethan L. Miller, Kevin M. Greenan, + * Benjamin A. Arnold, John A. Burnum, Adam W. Disney, Allen C. McBride. + * + * gf_w8.c + * + * Defines and data stuctures for 8-bit Galois fields + */ + +#ifndef GF_COMPLETE_GF_W8_H +#define GF_COMPLETE_GF_W8_H + +#include "gf_int.h" +#include <stdint.h> + +#define GF_FIELD_WIDTH (8) +#define GF_FIELD_SIZE (1 << GF_FIELD_WIDTH) +#define GF_HALF_SIZE (1 << (GF_FIELD_WIDTH/2)) +#define GF_MULT_GROUP_SIZE GF_FIELD_SIZE-1 + +#define GF_BASE_FIELD_WIDTH (4) +#define GF_BASE_FIELD_SIZE (1 << GF_BASE_FIELD_WIDTH) + +struct gf_w8_logtable_data { + uint8_t log_tbl[GF_FIELD_SIZE]; + uint8_t antilog_tbl[GF_FIELD_SIZE * 2]; + uint8_t inv_tbl[GF_FIELD_SIZE]; +}; + +struct gf_w8_logzero_table_data { + short log_tbl[GF_FIELD_SIZE]; /* Make this signed, so that we can divide easily */ + uint8_t antilog_tbl[512+512+1]; + uint8_t *div_tbl; + uint8_t *inv_tbl; +}; + +struct gf_w8_logzero_small_table_data { + short log_tbl[GF_FIELD_SIZE]; /* Make this signed, so that we can divide easily */ + uint8_t antilog_tbl[255*3]; + uint8_t inv_tbl[GF_FIELD_SIZE]; + uint8_t *div_tbl; +}; + +struct gf_w8_composite_data { + uint8_t *mult_table; +}; + +/* Don't change the order of these relative to gf_w8_half_table_data */ + +struct gf_w8_default_data { + uint8_t high[GF_FIELD_SIZE][GF_HALF_SIZE]; + uint8_t low[GF_FIELD_SIZE][GF_HALF_SIZE]; + uint8_t divtable[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint8_t multtable[GF_FIELD_SIZE][GF_FIELD_SIZE]; +}; + +struct gf_w8_half_table_data { + uint8_t high[GF_FIELD_SIZE][GF_HALF_SIZE]; + uint8_t low[GF_FIELD_SIZE][GF_HALF_SIZE]; +}; + +struct gf_w8_single_table_data { + uint8_t divtable[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint8_t multtable[GF_FIELD_SIZE][GF_FIELD_SIZE]; +}; + +struct gf_w8_double_table_data { + uint8_t div[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint16_t mult[GF_FIELD_SIZE][GF_FIELD_SIZE*GF_FIELD_SIZE]; +}; + +struct gf_w8_double_table_lazy_data { + uint8_t div[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint8_t smult[GF_FIELD_SIZE][GF_FIELD_SIZE]; + uint16_t mult[GF_FIELD_SIZE*GF_FIELD_SIZE]; +}; + +struct gf_w4_logtable_data { + uint8_t log_tbl[GF_BASE_FIELD_SIZE]; + uint8_t antilog_tbl[GF_BASE_FIELD_SIZE * 2]; + uint8_t *antilog_tbl_div; +}; + +struct gf_w4_single_table_data { + uint8_t div[GF_BASE_FIELD_SIZE][GF_BASE_FIELD_SIZE]; + uint8_t mult[GF_BASE_FIELD_SIZE][GF_BASE_FIELD_SIZE]; +}; + +struct gf_w8_bytwo_data { + uint64_t prim_poly; + uint64_t mask1; + uint64_t mask2; +}; + +int gf_w8_neon_cfm_init(gf_t *gf); +void gf_w8_neon_split_init(gf_t *gf); + +#endif /* GF_COMPLETE_GF_W8_H */ |