Коды Рида-Соломона считаются через экспоненты и логарифмы по таблице. А у нас с внедренеием инструкций 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
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
