GF2p8 Кодирование Рида-Соломона в изоморфном представлении поля

Коды Рида-Соломона считаются через экспоненты и логарифмы по таблице. А у нас с внедренеием инструкций Intel GFNI появилось две другие возможности: использовать инструкцию умножения и аффинные преобразования.

Для примера я взял коды РС из проекта библиотеки генеации QR-кодов. Там используется полином поля G(2^8) P = 0x11D. Кодирование производится в цикле. При переходе к операциям умножения в поле 0x11D, цикл кодрования выглядит так.

	for(i = 0; i < data_length; i++) {
		uint8_t fb =  data[i] ^ Z[0];
		for(j = 0; j < ecc_length-1; j++) {
			Z[j] = Z[j+1] ^ gf2p8_mul(fb, g[j], 0x11D);
		}
		Z[j] = gf2p8_mul(fb, g[j], 0x11D);
	}
	for(i = 0; i < ecc_length; i++) {
		ecc[i] = Z[i];
	}

Преобразование алгоритма для расчета в изоморфном представлении поля с образующим полиномом 0x11B:

	const uint64_t M = 0xFFAACC88F0A0C080;
	const uint64_t Mr= 0xFFAACC88F0A0C080;

	for(i = 0; i < data_length; i++) {
		uint8_t fb =  affine(M,data[i]) ^ Z[0];
		for(j = 0; j < ecc_length-1; j++) {
			Z[j] = Z[j+1] ^ gf2p8_mul(fb, g[j], 0x11B);
		}
		Z[j] = gf2p8_mul(fb, g[j], 0x11B);
	}
	for(i = 0; i < ecc_length; i++) {
		ecc[i] = affine(Mr, Z[i]);
	}

Данное преобразование предполагает так же изоморфные преобразования компонент вектора генератора кодов (g). Векторизация алгоритма может быть выполнена по вложенному циклу.

[1]The comeback of Reed Solomon codes N.Drucker, Sh.Gueron, V.Krasnov

Приложение

Довеском идет код для расчета остатка от деления на 255. Когда в контроллере нет полиномиального умножения, приходится использовать способ расчета умножения и инверсии с использованием таблиц логарифмов и экспонент.

// Multiplication in Galua Fields
int gf_mul(int x, int y) {
    if (x == 0 || y == 0) return 0;
    return exp_[(log_[x] + log_[y])%255];
}
// Inversion in Galua Fields
int gf_inv(int x) {
    return exp_[255 - log_[x]];
}
// Division in Galua Fields
int gf_div(int x, int y) {
    if (x == 0) return 0;
    return exp_[(log_[x] + 255 - log_[y]) % 255];
}

Самая неудобная операция в этом случае - вычисление остатка от деления на 255. Избавился от деления.

// Остаток от деления на 255
uint8_t mod255(unsigned v) {
	uint32_t q = (v*0x1010102UL)>>(24);
	return q;
}

// Остаток от деления на 255
uint8_t mod255(unsigned v) {
	return v + (v>>8);
}

А этот вариант самый простой, применим для сложения логарифмов.

Такая вот оптимизация.

[2] Исходники на Github