ftape-ecc.c

h内核

	for (i = 0; i < n; ++i) {
		dot_prod = 0;
		for (j = 0; j < n; ++j) {
			dot_prod = gfadd(dot_prod, gfmul(A[i][j], s[j]));
		}
		b[i] = dot_prod;
	}
}



/* The Reed Solomon ECC codes are computed over the N-th byte of each
 * block, where N=SECTOR_SIZE.  There are up to 29 blocks of data, and
 * 3 blocks of ECC.  The blocks are stored contiguously in memory.  A
 * segment, consequently, is assumed to have at least 4 blocks: one or
 * more data blocks plus three ECC blocks.
 *
 * Notice: In QIC-80 speak, a CRC error is a sector with an incorrect
 *         CRC.  A CRC failure is a sector with incorrect data, but
 *         a valid CRC.  In the error control literature, the former
 *         is usually called "erasure", the latter "error."
 */
/* Compute the parity bytes for C columns of data, where C is the
 * number of bytes that fit into a long integer.  We use a linear
 * feed-back register to do this.  The parity bytes P[0], P[STRIDE],
 * P[2*STRIDE] are computed such that:
 *
 *              x^k * p(x) + m(x) = 0 (modulo g(x))
 *
 * where k = NBLOCKS,
 *       p(x) = P[0] + P[STRIDE]*x + P[2*STRIDE]*x^2, and
 *       m(x) = sum_{i=0}^k m_i*x^i.
 *       m_i = DATA[i*SECTOR_SIZE]
 */
static inline void set_parity(unsigned long *data,
			      int nblocks, 
			      unsigned long *p, 
			      int stride)
{
	unsigned long p0, p1, p2, t1, t2, *end;

	end = data + nblocks * (FT_SECTOR_SIZE / sizeof(long));
	p0 = p1 = p2 = 0;
	while (data < end) {
		/* The new parity bytes p0_i, p1_i, p2_i are computed
		 * from the old values p0_{i-1}, p1_{i-1}, p2_{i-1}
		 * recursively as:
		 *
		 *        p0_i = p1_{i-1} + r^105 * (m_{i-1} - p0_{i-1})
		 *        p1_i = p2_{i-1} + r^105 * (m_{i-1} - p0_{i-1})
		 *        p2_i =                    (m_{i-1} - p0_{i-1})
		 *
		 * With the initial condition: p0_0 = p1_0 = p2_0 = 0.
		 */
		t1 = gfadd_long(*data, p0);
		/*
		 * Multiply each byte in t1 by 0xc0:
		 */
		if (sizeof(long) == 4) {
			t2= (((__u32) gfmul_c0[(__u32)t1 >> 24 & 0xff]) << 24 |
			     ((__u32) gfmul_c0[(__u32)t1 >> 16 & 0xff]) << 16 |
			     ((__u32) gfmul_c0[(__u32)t1 >>  8 & 0xff]) <<  8 |
			     ((__u32) gfmul_c0[(__u32)t1 >>  0 & 0xff]) <<  0);
		} else if (sizeof(long) == 8) {
			t2= (((__u64) gfmul_c0[(__u64)t1 >> 56 & 0xff]) << 56 |
			     ((__u64) gfmul_c0[(__u64)t1 >> 48 & 0xff]) << 48 |
			     ((__u64) gfmul_c0[(__u64)t1 >> 40 & 0xff]) << 40 |
			     ((__u64) gfmul_c0[(__u64)t1 >> 32 & 0xff]) << 32 |
			     ((__u64) gfmul_c0[(__u64)t1 >> 24 & 0xff]) << 24 |
			     ((__u64) gfmul_c0[(__u64)t1 >> 16 & 0xff]) << 16 |
			     ((__u64) gfmul_c0[(__u64)t1 >>  8 & 0xff]) <<  8 |
			     ((__u64) gfmul_c0[(__u64)t1 >>  0 & 0xff]) <<  0);
		} else {
			TRACE_FUN(ft_t_any);
			TRACE(ft_t_err, "Error: long is of size %d",
			      (int) sizeof(long));
			TRACE_EXIT;
		}
		p0 = gfadd_long(t2, p1);
		p1 = gfadd_long(t2, p2);
		p2 = t1;
		data += FT_SECTOR_SIZE / sizeof(long);
	}
	*p = p0;
	p += stride;
	*p = p1;
	p += stride;
	*p = p2;
	return;
}


/* Compute the 3 syndrome values.  DATA should point to the first byte
 * of the column for which the syndromes are desired.  The syndromes
 * are computed over the first NBLOCKS of rows.  The three bytes will
 * be placed in S[0], S[1], and S[2].
 *
 * S[i] is the value of the "message" polynomial m(x) evaluated at the
 * i-th root of the generator polynomial g(x).
 *
 * As g(x)=(x-r^-1)(x-1)(x-r^1) we evaluate the message polynomial at
 * x=r^-1 to get S[0], at x=r^0=1 to get S[1], and at x=r to get S[2].
 * This could be done directly and efficiently via the Horner scheme.
 * However, it would require multiplication tables for the factors
 * r^-1 (0xc3) and r (0x02).  The following scheme does not require
 * any multiplication tables beyond what's needed for set_parity()
 * anyway and is slightly faster if there are no errors and slightly
 * slower if there are errors.  The latter is hopefully the infrequent
 * case.
 *
 * To understand the alternative algorithm, notice that set_parity(m,
 * k, p) computes parity bytes such that:
 *
 *      x^k * p(x) = m(x) (modulo g(x)).
 *
 * That is, to evaluate m(r^m), where r^m is a root of g(x), we can
 * simply evaluate (r^m)^k*p(r^m).  Also, notice that p is 0 if and
 * only if s is zero.  That is, if all parity bytes are 0, we know
 * there is no error in the data and consequently there is no need to
 * compute s(x) at all!  In all other cases, we compute s(x) from p(x)
 * by evaluating (r^m)^k*p(r^m) for m=-1, m=0, and m=1.  The p(x)
 * polynomial is evaluated via the Horner scheme.
 */
static int compute_syndromes(unsigned long *data, int nblocks, unsigned long *s)
{
	unsigned long p[3];

	set_parity(data, nblocks, p, 1);
	if (p[0] | p[1] | p[2]) {
		/* Some of the checked columns do not have a zero
		 * syndrome.  For simplicity, we compute the syndromes
		 * for all columns that we have computed the
		 * remainders for.
		 */
		s[0] = gfmul_exp_long(
			gfadd_long(p[0], 
				   gfmul_exp_long(
					   gfadd_long(p[1], 
						      gfmul_exp_long(p[2], -1)),
					   -1)), 
			-nblocks);
		s[1] = gfadd_long(gfadd_long(p[2], p[1]), p[0]);
		s[2] = gfmul_exp_long(
			gfadd_long(p[0], 
				   gfmul_exp_long(
					   gfadd_long(p[1],
						      gfmul_exp_long(p[2], 1)),
					   1)),
			nblocks);
		return 0;
	} else {
		return 1;
	}
}


/* Correct the block in the column pointed to by DATA.  There are NBAD
 * CRC errors and their indices are in BAD_LOC[0], up to
 * BAD_LOC[NBAD-1].  If NBAD>1, Ainv holds the inverse of the matrix
 * of the linear system that needs to be solved to determine the error
 * magnitudes.  S[0], S[1], and S[2] are the syndrome values.  If row
 * j gets corrected, then bit j will be set in CORRECTION_MAP.
 */
static inline int correct_block(__u8 *data, int nblocks,
				int nbad, int *bad_loc, Matrix Ainv,
				__u8 *s,
				SectorMap * correction_map)
{
	int ncorrected = 0;
	int i;
	__u8 t1, t2;
	__u8 c0, c1, c2;	/* check bytes */
	__u8 error_mag[3], log_error_mag;
	__u8 *dp, l, e;
	TRACE_FUN(ft_t_any);

	switch (nbad) {
	case 0:
		/* might have a CRC failure: */
		if (s[0] == 0) {
			/* more than one error */
			TRACE_ABORT(-1, ft_t_err,
				 "ECC failed (0 CRC errors, >1 CRC failures)");
		}
		t1 = gfdiv(s[1], s[0]);
		if ((bad_loc[nbad++] = gflog[t1]) >= nblocks) {
			TRACE(ft_t_err,
			      "ECC failed (0 CRC errors, >1 CRC failures)");
			TRACE_ABORT(-1, ft_t_err,
				  "attempt to correct data at %d", bad_loc[0]);
		}
		error_mag[0] = s[1];
		break;
	case 1:
		t1 = gfadd(gfmul_exp(s[1], bad_loc[0]), s[2]);
		t2 = gfadd(gfmul_exp(s[0], bad_loc[0]), s[1]);
		if (t1 == 0 && t2 == 0) {
			/* one erasure, no error: */
			Ainv[0][0] = gfpow[bad_loc[0]];
		} else if (t1 == 0 || t2 == 0) {
			/* one erasure and more than one error: */
			TRACE_ABORT(-1, ft_t_err,
				    "ECC failed (1 erasure, >1 error)");
		} else {
			/* one erasure, one error: */
			if ((bad_loc[nbad++] = gflog[gfdiv(t1, t2)]) 
			    >= nblocks) {
				TRACE(ft_t_err, "ECC failed "
				      "(1 CRC errors, >1 CRC failures)");
				TRACE_ABORT(-1, ft_t_err,
					    "attempt to correct data at %d",
					    bad_loc[1]);
			}
			if (!gfinv2(bad_loc[0], bad_loc[1], Ainv)) {
				/* inversion failed---must have more
                                 *  than one error 
				 */
				TRACE_EXIT -1;
			}
		}
		/* FALL THROUGH TO ERROR MAGNITUDE COMPUTATION:
		 */
	case 2:
	case 3:
		/* compute error magnitudes: */
		gfmat_mul(nbad, Ainv, s, error_mag);
		break;

	default:
		TRACE_ABORT(-1, ft_t_err,
			    "Internal Error: number of CRC errors > 3");
	}

	/* Perform correction by adding ERROR_MAG[i] to the byte at
	 * offset BAD_LOC[i].  Also add the value of the computed
	 * error polynomial to the syndrome values.  If the correction
	 * was successful, the resulting check bytes should be zero
	 * (i.e., the corrected data is a valid code word).
	 */
	c0 = s[0];
	c1 = s[1];
	c2 = s[2];
	for (i = 0; i < nbad; ++i) {
		e = error_mag[i];
		if (e) {
			/* correct the byte at offset L by magnitude E: */
			l = bad_loc[i];
			dp = &data[l * FT_SECTOR_SIZE];
			*dp = gfadd(*dp, e);
			*correction_map |= 1 << l;
			++ncorrected;

			log_error_mag = gflog[e];
			c0 = gfadd(c0, gfpow[mod255(log_error_mag - l)]);
			c1 = gfadd(c1, e);
			c2 = gfadd(c2, gfpow[mod255(log_error_mag + l)]);
		}
	}
	if (c0 || c1 || c2) {
		TRACE_ABORT(-1, ft_t_err,
			    "ECC self-check failed, too many errors");
	}
	TRACE_EXIT ncorrected;
}


#if defined(ECC_SANITY_CHECK) || defined(ECC_PARANOID)

/* Perform a sanity check on the computed parity bytes:
 */
static int sanity_check(unsigned long *data, int nblocks)
{
	TRACE_FUN(ft_t_any);
	unsigned long s[3];

	if (!compute_syndromes(data, nblocks, s)) {
		TRACE_ABORT(0, ft_bug,
			    "Internal Error: syndrome self-check failed");
	}
	TRACE_EXIT 1;
}

#endif /* defined(ECC_SANITY_CHECK) || defined(ECC_PARANOID) */

/* Compute the parity for an entire segment of data.
 */
int ftape_ecc_set_segment_parity(struct memory_segment *mseg)
{
	int i;
	__u8 *parity_bytes;

	parity_bytes = &mseg->data[(mseg->blocks - 3) * FT_SECTOR_SIZE];
	for (i = 0; i < FT_SECTOR_SIZE; i += sizeof(long)) {
		set_parity((unsigned long *) &mseg->data[i], mseg->blocks - 3,
			   (unsigned long *) &parity_bytes[i],
			   FT_SECTOR_SIZE / sizeof(long));
#ifdef ECC_PARANOID
		if (!sanity_check((unsigned long *) &mseg->data[i],
				   mseg->blocks)) {
			return -1;
		}
#endif				/* ECC_PARANOID */
	}
	return 0;
}


/* Checks and corrects (if possible) the segment MSEG.  Returns one of
 * ECC_OK, ECC_CORRECTED, and ECC_FAILED.
 */
int ftape_ecc_correct_data(struct memory_segment *mseg)
{
	int col, i, result;
	int ncorrected = 0;
	int nerasures = 0;	/* # of erasures (CRC errors) */
	int erasure_loc[3];	/* erasure locations */
	unsigned long ss[3];
	__u8 s[3];
	Matrix Ainv;
	TRACE_FUN(ft_t_flow);

	mseg->corrected = 0;

	/* find first column that has non-zero syndromes: */
	for (col = 0; col < FT_SECTOR_SIZE; col += sizeof(long)) {
		if (!compute_syndromes((unsigned long *) &mseg->data[col],
				       mseg->blocks, ss)) {
			/* something is wrong---have to fix things */
			break;
		}
	}
	if (col >= FT_SECTOR_SIZE) {
		/* all syndromes are ok, therefore nothing to correct */
		TRACE_EXIT ECC_OK;
	}
	/* count the number of CRC errors if there were any: */
	if (mseg->read_bad) {
		for (i = 0; i < mseg->blocks; i++) {
			if (BAD_CHECK(mseg->read_bad, i)) {
				if (nerasures >= 3) {
					/* this is too much for ECC */
					TRACE_ABORT(ECC_FAILED, ft_t_err,
						"ECC failed (>3 CRC errors)");
				}	/* if */
				erasure_loc[nerasures++] = i;
			}
		}
	}
	/*
	 * If there are at least 2 CRC errors, determine inverse of matrix
	 * of linear system to be solved:
	 */
	switch (nerasures) {
	case 2:
		if (!gfinv2(erasure_loc[0], erasure_loc[1], Ainv)) {
			TRACE_EXIT ECC_FAILED;
		}
		break;
	case 3:
		if (!gfinv3(erasure_loc[0], erasure_loc[1],
			    erasure_loc[2], Ainv)) {
			TRACE_EXIT ECC_FAILED;
		}
		break;
	default:
		/* this is not an error condition... */
		break;
	}

	do {
		for (i = 0; i < sizeof(long); ++i) {
			s[0] = ss[0];
			s[1] = ss[1];
			s[2] = ss[2];
			if (s[0] | s[1] | s[2]) {
#ifdef BIG_ENDIAN
				result = correct_block(
					&mseg->data[col + sizeof(long) - 1 - i],
					mseg->blocks,
					nerasures,
					erasure_loc,
					Ainv,
					s,
					&mseg->corrected);
#else
				result = correct_block(&mseg->data[col + i],
						       mseg->blocks,
						       nerasures,
						       erasure_loc,
						       Ainv,
						       s,
						       &mseg->corrected);
#endif
				if (result < 0) {
					TRACE_EXIT ECC_FAILED;
				}
				ncorrected += result;
			}
			ss[0] >>= 8;
			ss[1] >>= 8;
			ss[2] >>= 8;
		}

#ifdef ECC_SANITY_CHECK
		if (!sanity_check((unsigned long *) &mseg->data[col],
				  mseg->blocks)) {
			TRACE_EXIT ECC_FAILED;
		}
#endif				/* ECC_SANITY_CHECK */

		/* find next column with non-zero syndromes: */
		while ((col += sizeof(long)) < FT_SECTOR_SIZE) {
			if (!compute_syndromes((unsigned long *)
				    &mseg->data[col], mseg->blocks, ss)) {
				/* something is wrong---have to fix things */
				break;
			}
		}
	} while (col < FT_SECTOR_SIZE);
	if (ncorrected && nerasures == 0) {
		TRACE(ft_t_warn, "block contained error not caught by CRC");
	}
	TRACE((ncorrected > 0) ? ft_t_noise : ft_t_any, "number of corrections: %d", ncorrected);
	TRACE_EXIT ncorrected ? ECC_CORRECTED : ECC_OK;
}