Line data Source code
1 : #ifndef HEADER_fd_src_ballet_reedsol_fd_reedsol_private_h
2 : #define HEADER_fd_src_ballet_reedsol_fd_reedsol_private_h
3 :
4 : /* Contains function declarations for the internal encoding and recovery
5 : functions. */
6 :
7 : #include "fd_reedsol.h"
8 :
9 : /* FD_REEDSOL_ARITH_IMPL is used to select which implementation of
10 : Galois Field arithmetic should be used. Supported implementations
11 : include:
12 :
13 : 0 - unaccelerated
14 : 1 - AVX accelerated
15 : 2 - GFNI accelerated with AVX2
16 : 3 - GFNI accelerated with AVX512
17 : 4 - NEON accelerated (AArch64, 128-bit vectors) */
18 :
19 : #ifndef FD_REEDSOL_ARITH_IMPL
20 : #if FD_HAS_GFNI && FD_HAS_AVX512
21 : #define FD_REEDSOL_ARITH_IMPL 3
22 : #elif FD_HAS_GFNI
23 : #define FD_REEDSOL_ARITH_IMPL 2
24 : #elif FD_HAS_AVX
25 : #define FD_REEDSOL_ARITH_IMPL 1
26 : #elif FD_HAS_NEON
27 : #define FD_REEDSOL_ARITH_IMPL 4
28 : #else
29 : #define FD_REEDSOL_ARITH_IMPL 0
30 : #endif
31 : #endif
32 :
33 : #if FD_REEDSOL_ARITH_IMPL==0
34 : #include "fd_reedsol_arith_none.h"
35 : #elif FD_REEDSOL_ARITH_IMPL==1
36 : #include "fd_reedsol_arith_avx2.h"
37 : #elif FD_REEDSOL_ARITH_IMPL==2 || FD_REEDSOL_ARITH_IMPL==3
38 : #include "fd_reedsol_arith_gfni.h"
39 : #elif FD_REEDSOL_ARITH_IMPL==4
40 : #include "fd_reedsol_arith_neon.h"
41 : #else
42 : #error "Unsupported FD_REEDSOL_ARITH_IMPL"
43 : #endif
44 :
45 : /* FALLTHRU: Tells the compiler that falling through to the next case
46 : of the switch statement is intentional and not a bug. When brutality
47 : is turned on, this must be used. Clang an GCC differ on what
48 : annotations they accept, but this works for both. */
49 : /* TODO: CONSIDER MOVING SOMETHING LIKE THIS TO UTIL_BASE.H? */
50 :
51 2184695916 : #define FALLTHRU __attribute__((fallthrough));
52 :
53 : FD_PROTOTYPES_BEGIN
54 :
55 : /* fd_reedsol_private_encode_{n} requires that data_shred_cnt <= n */
56 :
57 : void
58 : fd_reedsol_private_encode_16( ulong shred_sz,
59 : uchar const * const * data_shred,
60 : ulong data_shred_cnt,
61 : uchar * const * parity_shred,
62 : ulong parity_shred_cnt );
63 :
64 : void
65 : fd_reedsol_private_encode_32( ulong shred_sz,
66 : uchar const * const * data_shred,
67 : ulong data_shred_cnt,
68 : uchar * const * parity_shred,
69 : ulong parity_shred_cnt );
70 :
71 : void
72 : fd_reedsol_private_encode_64( ulong shred_sz,
73 : uchar const * const * data_shred,
74 : ulong data_shred_cnt,
75 : uchar * const * parity_shred,
76 : ulong parity_shred_cnt );
77 :
78 : void
79 : fd_reedsol_private_encode_128( ulong shred_sz,
80 : uchar const * const * data_shred,
81 : ulong data_shred_cnt,
82 : uchar * const * parity_shred,
83 : ulong parity_shred_cnt );
84 :
85 : #if FD_HAS_GFNI
86 : void
87 : fd_reedsol_private_encode_32_32( ulong shred_sz,
88 : uchar const * const * data_shred,
89 : uchar * const * parity_shred,
90 : uchar * _scratch );
91 : #endif
92 :
93 : /* fd_reedsol_private_recover_var_{n}: Verifies the consistency
94 : of the Reed-Solomon encoded data, and recovers any missing data.
95 : At least data_shred_cnt of the first n shreds must be un-erased,
96 : which implies data_shred_cnt <= n.
97 :
98 : Unlike the encode operations, the math doesn't care much whether a
99 : shred is a data shred or parity shred for recover operations, hence
100 : the function only has one shred array. The parity shreds come
101 : immediately after the data shreds.
102 :
103 : For each value of i in [0, data_shred_cnt+parity_shred_cnt), erased[
104 : i ] must be 0 (if shred[ i ] contains valid data) or 1 if shred[ i ]
105 : is an erasure (i.e. wasn't received, was corrupted, etc.). If
106 : erased[ i ]==1, the contents of shred[ i ] are ignored on entry, and
107 : upon return, shred[ i ][ j ] will be overwritten with the correct
108 : data for j in [0, shred_sz).
109 :
110 : Note that since data_shred_cnt+parity_shred_cnt<=134, shred[ i ] and
111 : erased[ i ] for i>=134 are completely ignored.
112 :
113 : Returns one of:
114 :
115 : FD_REEDSOL_SUCCESS if okay
116 :
117 : FD_REEDSOL_ERR_CORRUPT if the shreds are not consistent with having
118 : come from a Reed-Solomon encoding of data_shred_cnt data shreds
119 :
120 : FD_REEDSOL_ERR_PARTIAL if there's not enough un-erased data to
121 : recover data_shred_cnt data shreds
122 :
123 : TODO: Add a recover_private_first_{n} variant that imposes the
124 : additional constraint that the first data_shred_cnt shreds must be
125 : un-erased, is the case when no packets have been lost. Would be
126 : slightly faster. */
127 :
128 : int
129 : fd_reedsol_private_recover_var_16( ulong shred_sz,
130 : uchar * const * shred,
131 : ulong data_shred_cnt,
132 : ulong parity_shred_cnt,
133 : uchar const * erased );
134 :
135 : int
136 : fd_reedsol_private_recover_var_32( ulong shred_sz,
137 : uchar * const * shred,
138 : ulong data_shred_cnt,
139 : ulong parity_shred_cnt,
140 : uchar const * erased );
141 :
142 : int
143 : fd_reedsol_private_recover_var_64( ulong shred_sz,
144 : uchar * const * shred,
145 : ulong data_shred_cnt,
146 : ulong parity_shred_cnt,
147 : uchar const * erased );
148 :
149 : int
150 : fd_reedsol_private_recover_var_128( ulong shred_sz,
151 : uchar * const * shred,
152 : ulong data_shred_cnt,
153 : ulong parity_shred_cnt,
154 : uchar const * erased );
155 :
156 : int
157 : fd_reedsol_private_recover_var_256( ulong shred_sz,
158 : uchar * const * shred,
159 : ulong data_shred_cnt,
160 : ulong parity_shred_cnt,
161 : uchar const * erased );
162 :
163 : /* This below functions generate what:
164 :
165 : S. -J. Lin, T. Y. Al-Naffouri, Y. S. Han and W. -H. Chung, "Novel
166 : Polynomial Basis With Fast Fourier Transform and Its Application to
167 : Reed–Solomon Erasure Codes," in IEEE Transactions on Information
168 : Theory, vol. 62, no. 11, pp. 6284-6299, Nov. 2016, doi:
169 : 10.1109/TIT.2016.2608892.
170 :
171 : and:
172 :
173 : Didier, Frédéric. "Efficient erasure decoding of Reed-Solomon
174 : codes." arXiv preprint arXiv:0901.1886 (2009).
175 :
176 : call Pi and 1/Pi'. For more information about Pi and Pi', see the
177 : implementation or the papers referenced above.
178 :
179 : The main set of functions this file exposes is:
180 :
181 : void fd_reedsol_private_gen_pi_{N}( uchar const * is_erased, uchar * output )
182 :
183 : for N in {16, 32, 64, 128, 256}. Since Pi is only needed for
184 : elements that are not erased, Pi' is only needed for elements that
185 : are erased, and it is computationally beneficial to compute them at
186 : the same time, this function computes them both.
187 :
188 : is_erased and output must point to the first element of arrays
189 : indexed [0, N). They must be aligned to 32 bytes.
190 :
191 : Upon return, output[i] stores Pi(i) if is_erased[i]==0 and 1/Pi'(i)
192 : if is_erased[i]==1. It's undefined behavior for is_erased to contain
193 : something other than 0 or 1.
194 :
195 : Pi and Pi' are both elements of GF(2^8) stored in their normal byte
196 : representation. */
197 :
198 : void fd_reedsol_private_gen_pi_16 ( uchar const * is_erased, uchar * output );
199 : void fd_reedsol_private_gen_pi_32 ( uchar const * is_erased, uchar * output );
200 : void fd_reedsol_private_gen_pi_64 ( uchar const * is_erased, uchar * output );
201 : void fd_reedsol_private_gen_pi_128( uchar const * is_erased, uchar * output );
202 : void fd_reedsol_private_gen_pi_256( uchar const * is_erased, uchar * output );
203 :
204 : /* The following are the pre-computed values for common cases.
205 : They're exposed in this header so that the values to multiply are
206 : known at compile time to eliminate loads on the critical path. */
207 :
208 : /* TODO: Decide on pre-computed cases and add them */
209 :
210 : FD_PROTOTYPES_END
211 :
212 : #endif /* HEADER_fd_src_ballet_reedsol_fd_reedsol_private_h */
|
