#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int newElem(const int &x)
//расчет одного эл-та поля Галуа
{
if(x<128)
return (x<<1);
else return ((x<<1)^285);
}
void createArrGf(int *gf,int *gfLog,int n)
//создание поля Галуа(массив gf) и обратное поле Галуа(массив gfLog)
{
gf[0]=1;
gf[255]=0;
for (int i=1; i<255; ++i)
{
gf[i]=newElem(gf[i-1]);
}
for(int i=0; i<n;++i)
{
bool f=true;
int k=0;
while(f)
{
if(gf[k]==i)
{
gfLog[i]=k;
f=false;
}
++k;
}
}
}
void showArr(int *x, int &n)
//вывод массива
{
for (int i=0; i<n; ++i)
cout<<"Arr["<<i<<"]="<<x[i]<<endl;
}
int mult(int &x,int &y,int *gflog,int *gf)
//умножение х и у по правилам полей Галуа
{
if(x==0||y==0)
return 0;
int k=gflog[x]+gflog[y];
if(k<255)
return gf[k];
return gf[k-255];
}
int dev(int &x,int &y,int *gflog,int *gf)
//деление х на у по правилам полей Галуа
{
if(x==0 && y!=0)
return 0;
int k=gflog[x]-gflog[y];
if(k>=0)
return gf[k];
return gf[k+255];
}
void sumPol(int *a,int na, int *b,int nb, int *&c,int &nc)
//Сложение полнима а и b, с - результат сложения
{
cout<<"sumPol"<<endl;
if(na>=nb)
nc=na;
else nc=nb;
cout<<"nc========"<<nc<<endl;
cout<<"na========"<<na<<endl;
cout<<"nb========"<<nb<<endl;
cout<<"B"<<endl;
showArr(b,nb);
cout<<"A"<<endl;
showArr(a,na);
c=new int[nc];
for (int i=0; i<nc; ++i)
{
if(i>=na)
{c[i]=(0^b[i]);cout<<"0^"<<"b["<<i<<"]="<<"0^"<<b[i]<<"="<<(0^b[i])<<endl;}
else if(i>=nb)
{c[i]=(a[i]^0);cout<<"a["<<i<<"]"<<"^0="<<a[i]<<"^0"<<"="<<(a[i]^0)<<endl;}
else {c[i]=(a[i]^b[i]);cout<<"a["<<i<<"]^"<<"b["<<i<<"]="<<a[i]<<"^"<<b[i]<<"="<<(a[i]^b[i])<<endl;}
}
}
void multOnConst(int *&c,int &nc,int &x,int *gflog,int *gf)
//умножение полинома на константу х
{
cout<<"multOnConst "<<x<<endl;
for(int i=0; i<nc;++i)
c[i]=mult(c[i],x,gflog,gf);
}
void eq(int *&a, int *b, int nb)
//скопировать полином а куда копировать b что копировать
{
for(int i=0;i<=nb;i++)
a[i]=b[i];
}
void sdvig(int *&c,int &nc)
//"Сдвиг влево" полинома С на одну позицию
{
// cout<<"sdvig"<<endl;
nc+=1;
for(int i=nc-1; i>=0;--i)
{
int t=c[i];
c[i]=c[i-1];
c[i-1]=t;
}
c[0]=0;
}
void pribost(int *&a,int na,int b)
//прибавление заданного элемента в конец указаного
//полинома со сдвигом на одну позицию влево(размер не увеличивается)
{
for(int i=na-1;i>=0;--i)
{
int t=a[i];
a[i]=a[i-1];
a[i-1]=t;
}
a[0]=b;
}
void multiPol(int *a,int na, int *b,int nb,int *&c,int &nc,int *gflog,int *gf)
//умножение полинома А на полином В, С-результат умножения
//na>=nb
{
cout<<"multiPol"<<endl;
nc=nb;
c=new int[nc];
for(int k1=0; k1<nc; ++k1)
c[k1]=b[k1];
cout<<"na============"<<na<<endl;
cout<<"nb============"<<nb<<endl;
cout<<"nc============"<<nc<<endl;
cout<<"C:"<<endl;
showArr(c,nc);
cout<<"B:"<<endl;
showArr(b,nb);
cout<<"A:"<<endl;
showArr(a,na);
for(int i=0; i<na; ++i)
{
cout<<"i=================="<<i<<endl;
if (i==0)
{
multOnConst(c,nc,a[i],gflog,gf);
cout<<"C posle i=0"<<endl;
showArr(c,nc);
}
else {
int nt=nb;
cout<<"nt============="<<nt<<endl;
int *t=new int[nt];
for (int k=0; k<nt; ++k)
t[k]=b[k];
cout<<"T pered multOn"<<endl;
showArr(t,nt);
multOnConst(t,nt,a[i],gflog,gf);
cout<<"T pered sdvig"<<endl;
showArr(t,nt);
for(int k1=0; k1<i; ++k1)
sdvig(t,nt);
cout<<"T pered sum"<<endl;
showArr(t,nt);
cout<<"C pered sum"<<endl;
showArr(c,nc);
sumPol(c,nc,t,nt,c,nc);
}
}
}
int nenul(int *c,int nc)
{
for(int i=nc-1;i>=0;i--)
{
if (c[i]!=0)
{
return c[i];
}
}
}
void devPolOst(int *a,int na, int *b,int nb,int *&c,int &nc,int *gflog,int *gf, int *&qi, int &nq)
//деление одного полинома(а) на другой(b) и остаток(c) от их деления
{
nc=nb;
c = new int[nc];
if (na>nb)
{
int *temp = new int[nb];
int *r = new int[nb];
int qc = nq-1;
cout<<"A:"<<endl;
showArr(a,na);
cout<<"B:"<<endl;
showArr(b,nb);
for(int k=na-1;k>=nb-1;k--)
{
int q = a[k];
if (k!=na-1)
{
q = nenul(c,nb);
}
qi[qc]=q;
eq(temp,b,nb);
eq(r,c,nb);
multOnConst(temp,nb,q,gflog,gf);
int y=0;
pribost(r,nb,a[k-(na-nb)]);
for(int i=nb-1;i>=0;i--)
{
if (k==na-1)
{
int t=k-y;
c[i]=a[t]^temp[i];
y++;
}
else
{
c[i]=r[i]^temp[i];
}
}
qc--;
}
}
else
cout<<"Error"<<endl;
}
string coderRS(string s,int er, int lt)
//Кодирование элементов в код Рида-Соломона
//s-строка на входе, er - предельное число иск байтов, lt - максимальная длина пакета
{
int n=256;
//создаем массивы значений для полей Галуа
int *gf=new int[n];
int *gflog=new int[n];
string result;
createArrGf(gf,gflog,n);
cout<<"=========NACHALO============"<<endl;
int lkp=2*er+s.length();//Длина конечного пакета
int *kp = new int[lkp];//Конечный пакет
int uk = 0;
for (int i=lkp-1;i>=(2*er);i--)
{
kp[i]=s[uk];
uk++;
}
//kp[8]=213;kp[7]=224;kp[6]=234;kp[5]=229;kp[4]=240;
for(int i=2*er-1;i>=0;i--)
kp[i]=0;
showArr(kp,lkp);
//int *g=new int[2*er];
int *g;
int ng=0;
for(int i=0; i<(2*er); ++i)
{
cout<<"i Code============"<<i<<endl;
if(i==0)
{
ng=2;
g=new int[ng];
g[0]=gf[i+1];
g[1]=1;
cout<<"g pri i==0"<<endl;
showArr(g,ng);
}
else
{
int ng2=2;
int *g2=new int[ng2];
g2[0]=gf[i+1];
g2[1]=1;
int ng3=ng;
int *g3=new int[ng3];
cout<<"g2 pered multi:"<<endl;
showArr(g2,ng2);
for(int k=0; k<ng3;++k)
{
g3[k]=g[k];
}
cout<<"g3 pered multi:"<<endl;
showArr(g3,ng3);
multiPol(g3,ng3,g2,ng2,g,ng,gflog,gf);
cout<<"g posle multi:"<<endl;
showArr(g,ng);
}
}
//содание остатка от деления полинома kp на g
int nq=ng;
int *q=new int[ng];
int *r;
int nr=0;
int ntes = 5;
devPolOst(kp,lkp,g,ng,r,nr,gflog,gf,q,nq);
cout<<"R:"<<endl;
showArr(r,nr);
//создание результирующего кадра f, равного сумме kp и r
for (int i=0;i<nr-1;i++)
kp[i]=r[i];
showArr(kp,lkp);
//создание результирующей строки
for(int i=0;i<lkp;i++)
result.append(1, (char)kp[i]);
return result;
}
int main()
{
string s = "hello";
string h;
h = coderRS(s,2,10);
cout<<h<<endl;
cout<<h.length()<<endl;
return 0;
}