lib/reed_solomon/decode_rs.c

21 	int i, j, r, k, pad;  variable
22 	int nn = rs->nn;
23 	int nroots = rs->nroots;
24 	int fcr = rs->fcr;
25 	int prim = rs->prim;
26 	int iprim = rs->iprim;
27 	uint16_t *alpha_to = rs->alpha_to;
28 	uint16_t *index_of = rs->index_of;
38 	uint16_t msk = (uint16_t) rs->nn;
41 	pad = nn - nroots - len;
48 	/* form the syndromes; i.e., evaluate data(x) at roots of
50 	for (i = 0; i < nroots; i++)
51 		syn[i] = (((uint16_t) data[0]) ^ invmsk) & msk;
54 		for (i = 0; i < nroots; i++) {
55 			if (syn[i] == 0) {
56 				syn[i] = (((uint16_t) data[j]) ^
59 				syn[i] = ((((uint16_t) data[j]) ^
61 					alpha_to[rs_modnn(rs, index_of[syn[i]] +
62 						       (fcr + i) * prim)];
68 		for (i = 0; i < nroots; i++) {
69 			if (syn[i] == 0) {
70 				syn[i] = ((uint16_t) par[j]) & msk;
72 				syn[i] = (((uint16_t) par[j]) & msk) ^
73 					alpha_to[rs_modnn(rs, index_of[syn[i]] +
74 						       (fcr+i)*prim)];
82 	for (i = 0; i < nroots; i++) {
83 		syn_error |= s[i];
84 		s[i] = index_of[s[i]];
102 					      prim * (nn - 1 - eras_pos[0]))];
103 		for (i = 1; i < no_eras; i++) {
104 			u = rs_modnn(rs, prim * (nn - 1 - eras_pos[i]));
105 			for (j = i + 1; j > 0; j--) {
106 				tmp = index_of[lambda[j - 1]];
115 	for (i = 0; i < nroots + 1; i++)
116 		b[i] = index_of[lambda[i]];
119 	 * Begin Berlekamp-Massey algorithm to determine error+erasure
125 		/* Compute discrepancy at the r-th step in poly-form */
127 		for (i = 0; i < r; i++) {
128 			if ((lambda[i] != 0) && (s[r - i - 1] != nn)) {
131 							  index_of[lambda[i]] +
132 							  s[r - i - 1])];
137 			/* 2 lines below: B(x) <-- x*B(x) */
141 			/* 7 lines below: T(x) <-- lambda(x)-discr_r*x*b(x) */
143 			for (i = 0; i < nroots; i++) {
144 				if (b[i] != nn) {
145 					t[i + 1] = lambda[i + 1] ^
147 								  b[i])];
149 					t[i + 1] = lambda[i + 1];
151 			if (2 * el <= r + no_eras - 1) {
152 				el = r + no_eras - el;
154 				 * 2 lines below: B(x) <-- inv(discr_r) *
157 				for (i = 0; i <= nroots; i++) {
158 					b[i] = (lambda[i] == 0) ? nn :
159 						rs_modnn(rs, index_of[lambda[i]]
160 							 - discr_r + nn);
163 				/* 2 lines below: B(x) <-- x*B(x) */
173 	for (i = 0; i < nroots + 1; i++) {
174 		lambda[i] = index_of[lambda[i]];
175 		if (lambda[i] != nn)
176 			deg_lambda = i;
181 	for (i = 1, k = iprim - 1; i <= nn; i++, k = rs_modnn(rs, k + iprim)) {
183 		for (j = deg_lambda; j > 0; j--) {
191 		/* store root (index-form) and error location number */
192 		root[count] = i;
205 		count = -EBADMSG;
212 	deg_omega = deg_lambda - 1;
213 	for (i = 0; i <= deg_omega; i++) {
215 		for (j = i; j >= 0; j--) {
216 			if ((s[i - j] != nn) && (lambda[j] != nn))
218 				    alpha_to[rs_modnn(rs, s[i - j] + lambda[j])];
220 		omega[i] = index_of[tmp];
224 	 * Compute error values in poly-form. num1 = omega(inv(X(l))), num2 =
225 	 * inv(X(l))**(fcr-1) and den = lambda_pr(inv(X(l))) all in poly-form
227 	for (j = count - 1; j >= 0; j--) {
229 		for (i = deg_omega; i >= 0; i--) {
230 			if (omega[i] != nn)
231 				num1 ^= alpha_to[rs_modnn(rs, omega[i] +
232 							i * root[j])];
234 		num2 = alpha_to[rs_modnn(rs, root[j] * (fcr - 1) + nn)];
237 		/* lambda[i+1] for i even is the formal derivative
238 		 * lambda_pr of lambda[i] */
239 		for (i = min(deg_lambda, nroots - 1) & ~1; i >= 0; i -= 2) {
240 			if (lambda[i + 1] != nn) {
241 				den ^= alpha_to[rs_modnn(rs, lambda[i + 1] +
242 						       i * root[j])];
249 						       nn - index_of[den])];
258 				if (data && (loc[j] < (nn - nroots)))
259 					data[loc[j] - pad] ^= cor;
266 		for (i = 0; i < count; i++)
267 			eras_pos[i] = loc[i] - pad;