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