lib/reed_solomon/decode_rs.c

1 // SPDX-License-Identifier: GPL-2.0
13 	struct rs_codec *rs = rsc->codec;
15 	int i, j, r, k, pad;  variable
16 	int nn = rs->nn;
17 	int nroots = rs->nroots;
18 	int fcr = rs->fcr;
19 	int prim = rs->prim;
20 	int iprim = rs->iprim;
21 	uint16_t *alpha_to = rs->alpha_to;
22 	uint16_t *index_of = rs->index_of;
26 	uint16_t msk = (uint16_t) rs->nn;
32 	uint16_t *lambda = rsc->buffers + RS_DECODE_LAMBDA * (nroots + 1);
33 	uint16_t *syn = rsc->buffers + RS_DECODE_SYN * (nroots + 1);
34 	uint16_t *b = rsc->buffers + RS_DECODE_B * (nroots + 1);
35 	uint16_t *t = rsc->buffers + RS_DECODE_T * (nroots + 1);
36 	uint16_t *omega = rsc->buffers + RS_DECODE_OMEGA * (nroots + 1);
37 	uint16_t *root = rsc->buffers + RS_DECODE_ROOT * (nroots + 1);
38 	uint16_t *reg = rsc->buffers + RS_DECODE_REG * (nroots + 1);
39 	uint16_t *loc = rsc->buffers + RS_DECODE_LOC * (nroots + 1);
42 	pad = nn - nroots - len;
43 	BUG_ON(pad < 0 || pad >= nn - nroots);
47 		for (i = 0; i < nroots; i++) {
51 			if (s[i] != nn)
59 	/* form the syndromes; i.e., evaluate data(x) at roots of
61 	for (i = 0; i < nroots; i++)
62 		syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk;
65 		for (i = 0; i < nroots; i++) {
66 			if (syn[i] == 0) {
67 				syn[i] = (((uint16_t) data[j]) ^
70 				syn[i] = ((((uint16_t) data[j]) ^
72 					alpha_to[rs_modnn(rs, index_of[syn[i]] +
73 						       (fcr + i) * prim)];
79 		for (i = 0; i < nroots; i++) {
80 			if (syn[i] == 0) {
81 				syn[i] = ((uint16_t) par[j]) & msk;
83 				syn[i] = (((uint16_t) par[j]) & msk) ^
84 					alpha_to[rs_modnn(rs, index_of[syn[i]] +
85 						       (fcr+i)*prim)];
93 	for (i = 0; i < nroots; i++) {
94 		syn_error |= s[i];
95 		s[i] = index_of[s[i]];
112 					prim * (nn - 1 - (eras_pos[0] + pad)))];
113 		for (i = 1; i < no_eras; i++) {
114 			u = rs_modnn(rs, prim * (nn - 1 - (eras_pos[i] + pad)));
115 			for (j = i + 1; j > 0; j--) {
116 				tmp = index_of[lambda[j - 1]];
125 	for (i = 0; i < nroots + 1; i++)
126 		b[i] = index_of[lambda[i]];
129 	 * Begin Berlekamp-Massey algorithm to determine error+erasure
135 		/* Compute discrepancy at the r-th step in poly-form */
137 		for (i = 0; i < r; i++) {
138 			if ((lambda[i] != 0) && (s[r - i - 1] != nn)) {
141 							  index_of[lambda[i]] +
142 							  s[r - i - 1])];
147 			/* 2 lines below: B(x) <-- x*B(x) */
151 			/* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */
153 			for (i = 0; i < nroots; i++) {
154 				if (b[i] != nn) {
155 					t[i + 1] = lambda[i + 1] ^
157 								  b[i])];
159 					t[i + 1] = lambda[i + 1];
161 			if (2 * el <= r + no_eras - 1) {
162 				el = r + no_eras - el;
164 				 * 2 lines below: B(x) <-- inv(discr_r) *
167 				for (i = 0; i <= nroots; i++) {
168 					b[i] = (lambda[i] == 0) ? nn :
169 						rs_modnn(rs, index_of[lambda[i]]
170 							 - discr_r + nn);
173 				/* 2 lines below: B(x) <-- x*B(x) */
183 	for (i = 0; i < nroots + 1; i++) {
184 		lambda[i] = index_of[lambda[i]];
185 		if (lambda[i] != nn)
186 			deg_lambda = i;
191 		 * deg(lambda) is zero even though the syndrome is non-zero
194 		return -EBADMSG;
200 	for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) {
202 		for (j = deg_lambda; j > 0; j--) {
213 			return -EBADMSG;
216 		/* store root (index-form) and error location number */
217 		root[count] = i;
230 		return -EBADMSG;
236 	deg_omega = deg_lambda - 1;
237 	for (i = 0; i <= deg_omega; i++) {
239 		for (j = i; j >= 0; j--) {
240 			if ((s[i - j] != nn) && (lambda[j] != nn))
242 				    alpha_to[rs_modnn(rs, s[i - j] + lambda[j])];
244 		omega[i] = index_of[tmp];
248 	 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
249 	 * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form
253 	for (j = count - 1; j >= 0; j--) {
255 		for (i = deg_omega; i >= 0; i--) {
256 			if (omega[i] != nn)
257 				num1 ^= alpha_to[rs_modnn(rs, omega[i] +
258 							i * root[j])];
267 		num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)];
270 		/* lambda[i+1] for i even is the formal derivative
271 		 * lambda_pr of lambda[i] */
272 		for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) {
273 			if (lambda[i + 1] != nn) {
274 				den ^= alpha_to[rs_modnn(rs, lambda[i + 1] +
275 						       i * root[j])];
281 					       nn - index_of[den])];
289 	for (i = 0; i < nroots; i++) {
295 			k = (fcr + i) * prim * (nn-loc[j]-1);
299 		if (tmp != alpha_to[s[i]])
300 			return -EBADMSG;
309 		for (i = 0; i < count; i++) {
310 			if (b[i]) {
311 				corr[j] = b[i];
312 				eras_pos[j++] = loc[i] - pad;
317 		for (i = 0; i < count; i++) {
318 			if (loc[i] < (nn - nroots))
319 				data[loc[i] - pad] ^= b[i];
321 				par[loc[i] - pad - len] ^= b[i];