OpenCores
URL https://opencores.org/ocsvn/reedsolomon/reedsolomon/trunk

Subversion Repositories reedsolomon

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /
    from Rev 1 to Rev 2
    ↔ Reverse comparison
  •

Rev 1 → Rev 2

/reedsolomon/trunk/bluespec-source/ErrorMagnitude.bsv
0,0 → 1,220
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import FIFO::*;
import GFArith::*;
import GFTypes::*;
import Vector::*;
 
// ---------------------------------------------------------
// Reed-Solomon Error Magnitude computer interface
// ---------------------------------------------------------
interface IErrorMagnitude;
method Action k_in(Byte k_new);
method Action no_error_flag_in(Bool no_error_new);
method Action loc_in(Maybe#(Byte) loc_new);
method Action alpha_inv_in(Maybe#(Byte) alpha_inv_new);
method Action lambda_in(Syndrome#(T) lambda_new);
method Action omega_in(Syndrome#(T) omega_new);
method ActionValue#(Byte) error_out();
endinterface
 
// ---------------------------------------------------------
// Reed-Solomon Error Magnitude computer module
// ---------------------------------------------------------
(* synthesize *)
module mkErrorMagnitude (IErrorMagnitude);
// input queues
FIFO#(Byte) k_q <- mkSizedFIFO(1);
FIFO#(Bool) no_error_flag_q <- mkSizedFIFO(1);
FIFO#(Syndrome#(T)) lambda_q <- mkSizedFIFO(1);
FIFO#(Syndrome#(T)) omega_q <- mkSizedFIFO(1);
FIFO#(Maybe#(Byte)) loc_q <- mkSizedFIFO(valueOf(TwoT));
FIFO#(Maybe#(Byte)) alpha_inv_q <- mkSizedFIFO(valueOf(T));
// output queues
FIFO#(Byte) err_q <- mkSizedFIFO(2);
// internal quques
FIFO#(Byte) int_err_q <- mkSizedFIFO(valueOf(T));
// booking state
Reg#(Byte) omega_val <- mkReg(0);
Reg#(Byte) lambda_d_val <- mkReg(0);
 
Reg#(Byte) i <- mkReg(0);
Reg#(Byte) count <- mkReg(0);
Reg#(Byte) block_number <- mkReg(1);
// variables
Byte t = fromInteger(valueOf(T));
let k = k_q.first();
let no_error_flag = no_error_flag_q.first();
let loc = fromMaybe(255,loc_q.first()); // next location has no error?
let alpha_inv = fromMaybe(?,alpha_inv_q.first());
let lambda = lambda_q.first();
let omega = omega_q.first();
// -----------------------------------------------
rule eval_lambda_omega (count < t && isValid(alpha_inv_q.first()));
// Derivative of Lambda is done by dropping even terms and shifting odd terms by one
// So count is incremented by 2
// valid_t - 2 is the index used as the final term since valid_t - 1 term gets dropped
Byte idx = (t - 1) - count;
Byte lambda_add_val = ((count & 8'd1) == 8'd1) ? lambda[idx] : 0;
lambda_d_val <= gf_add(gf_mult(lambda_d_val, alpha_inv),lambda_add_val);
omega_val <= gf_mult(omega_val, alpha_inv) ^ omega[idx];
count <= count + 1;
 
$display (" [errMag %d] Evaluating Lambda_der count : %d, lambda_d_val[prev] : %d, lambda_add_val : %d, idx : %d",
block_number, count, lambda_d_val, lambda_add_val, idx);
$display (" [errMag %d] Evaluating Omega count : %d, omega_val[prev] : %d",
block_number, count, omega_val);
endrule
// ------------------------------------------------
rule enq_error (count == t);
$display (" [errMag %d] Finish Evaluating Lambda Omega", block_number);
 
let err_val = gf_mult(omega_val, gf_inv(lambda_d_val));
int_err_q.enq(err_val);
count <= 0;
lambda_d_val <= 0;
omega_val <= 0;
alpha_inv_q.deq();
endrule
rule deq_invalid_alpha_inv (alpha_inv_q.first() matches Invalid);
$display (" [errMag %d] Deq Invalid Alpha Inv", block_number);
alpha_inv_q.deq();
lambda_q.deq();
omega_q.deq();
endrule
// ------------------------------------------------
rule process_error_no_error (i < k && !no_error_flag);
Byte err_val;
if (i == loc)
begin
$display (" [errMag %d] Processing location %d which is in error ", block_number, i);
 
err_val = int_err_q.first();
int_err_q.deq();
loc_q.deq();
end
else
begin
$display (" [errMag %d] process location %d which has no error ", block_number, i);
err_val = 0;
end
err_q.enq(err_val);
i <= i + 1;
endrule
 
// ------------------------------------------------
rule bypass(i < k && no_error_flag);
$display (" [errMag %d] process location %d bypass which has no error ", block_number, i);
i <= k;
endrule
// ------------------------------------------------
rule start_next_errMag (i == k);
$display ("Start Next ErrMag");
k_q.deq();
no_error_flag_q.deq();
i <= 0;
block_number <= block_number + 1;
if (!no_error_flag)
begin
loc_q.deq(); // this one should be the Invalid denomiator
end
endrule
 
// ------------------------------------------------
method Action k_in(Byte k_new);
$display (" [errMag %d] k_in : %d", block_number, k_new);
k_q.enq(k_new);
endmethod
// ------------------------------------------------
method Action no_error_flag_in(Bool no_error_new);
$display (" [errMag %d] no_error_flag_in : %d", block_number, no_error_new);
no_error_flag_q.enq(no_error_new);
endmethod
// ------------------------------------------------
method Action loc_in(Maybe#(Byte) loc_new);
$display (" [errMag %d] loc_in : %d", block_number, loc_new);
loc_q.enq(loc_new);
endmethod
// ------------------------------------------------
method Action alpha_inv_in(Maybe#(Byte) alpha_inv_new);
$display (" [errMag %d] alpha_inv_in : %d", block_number, alpha_inv_new);
alpha_inv_q.enq(alpha_inv_new);
endmethod
// ------------------------------------------------
method Action lambda_in(Syndrome#(T) lambda_new);
$display (" [errMag %d] lambda_in : %d", block_number, lambda_new);
lambda_q.enq(lambda_new);
endmethod
// ------------------------------------------------
method Action omega_in(Syndrome#(T) omega_new);
$display (" [errMag %d] w_in : %d", block_number, omega_new);
omega_q.enq(omega_new);
endmethod
// ------------------------------------------------
method ActionValue#(Byte) error_out();
$display (" [errMag %d] err_out: %d", block_number, err_q.first());
err_q.deq();
return err_q.first();
endmethod
endmodule
 
 
 
 
 
 
/reedsolomon/trunk/bluespec-source/file_interface.cpp
0,0 → 1,108
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
#include <iostream>
#include <fstream>
using namespace std;
 
 
extern "C"
{
void loadByteStream (void);
char getNextStreamByte (void);
void storeByteStream (void);
void putNextStreamByte (unsigned char byte);
void putMACData (unsigned char n, unsigned char t);
unsigned char isStreamActive (void);
void closeOutputFile ();
}
 
 
ifstream ifs_Input;
ofstream ofs_Output;
 
 
//---------------------------------------------------------------------
void loadByteStream (void)
{
cout << " reading from file '" << DATA_FILE_PATH << "'" << endl;
ifs_Input.open (DATA_FILE_PATH);
if (false == ifs_Input.is_open ())
cout << "[ERROR] failed to open input file." << endl;
}
 
 
//---------------------------------------------------------------------
char getNextStreamByte (void)
{
int byte;
ifs_Input >> byte;
 
if (true == ifs_Input.eof ())
cout << " end of file reached." << endl;
 
return (unsigned char) byte;
}
 
 
//---------------------------------------------------------------------
void storeByteStream (void)
{
cout << " writing to file '" << OUT_DATA_FILE_PATH << "'" << endl;
ofs_Output.open (OUT_DATA_FILE_PATH);
if (false == ofs_Output.is_open ())
cout << "[ERROR] failed to open output file." << endl;
}
 
 
//---------------------------------------------------------------------
void putNextStreamByte (unsigned char byte)
{
ofs_Output << (int) byte << endl;
}
 
 
//---------------------------------------------------------------------
void putMACData (unsigned char n, unsigned char t)
{
ofs_Output << (int) n << ' ' << (int)t << endl;
}
 
 
//---------------------------------------------------------------------
unsigned char isStreamActive (void)
{
return ((true == ifs_Input.is_open ()) && (false == ifs_Input.eof ()));
}
 
 
//---------------------------------------------------------------------
void closeOutputFile ()
{
ofs_Output.flush ();
ofs_Output.close ();
}
/reedsolomon/trunk/bluespec-source/funcunit.bsv
0,0 → 1,93
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import FIFO::*;
import GetPut::*;
import GFTypes::*;
import mkReedSolomon::*;
 
import Transfer::*;
 
typedef enum{ ReadN, ReadT, ReadD } FPGAState deriving (Eq, Bits);
 
// ---------------------------------------------------------
// FPGA Reed-Solomon Wrapper module
// ---------------------------------------------------------
(* synthesize *)
module mkfuncunit (ProcSide);
Transfer transfer <- mkTransfer();
IReedSolomon decoder <- mkReedSolomon();
Reg#(FPGAState) state <- mkReg(ReadN);
Reg#(Byte) n <- mkReg(0);
rule readN(state == ReadN);
let inData <- transfer.funcSideGet.get();
n <= truncate(inData);
state <= ReadT;
 
$display(" [mkFPGAReedSolomon] readN n : %d", inData);
endrule
rule readT(state == ReadT);
let inData <- transfer.funcSideGet.get();
let t = truncate(inData);
let k = n - 2 * t;
decoder.rs_t_in.put(t);
decoder.rs_k_in.put(k);
state <= ReadD;
 
$display(" [mkFPGAReedSolomon] readT t : %d", inData);
endrule
rule readD(state == ReadD);
let inData <- transfer.funcSideGet.get();
decoder.rs_input.put(truncate(inData));
n <= n - 1;
if (n == 1) // last element, start to ReadN again
state <= ReadN;
 
$display(" [mkFPGAReedSolomon] readD i : %d, data in : %d", n, inData);
endrule
rule discardFlag(True);
let rs_flag <- decoder.rs_flag.get();
 
$display(" [mkFPGAReedSolomon] discardFlag flag : %d", rs_flag);
endrule
 
rule enqOut(True);
let datum <- decoder.rs_output.get();
transfer.funcSidePut.put(zeroExtend(datum));
$display(" [mkFPGAReedSolomon] enqOut data out : %d", datum);
endrule
return transfer.procSide();
endmodule
/reedsolomon/trunk/bluespec-source/MFIFO.bsv
0,0 → 1,222
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import FIFOF::*;
import RWire::*;
 
// -------------------------------------------------------------------
// MFIFO Interface: a fifo allow to the value of the first element to be modified
// -------------------------------------------------------------------
 
interface MFIFO#(numeric type sz, type a);
method Action enq(a in);
method Action deq();
method Action clear();
interface Reg#(a) first;
endinterface
 
interface MFIFOF#(numeric type sz, type a);
method Action enq(a in);
method Action deq();
method Action clear();
method Bool notEmpty();
method Bool notFull();
interface Reg#(a) first;
endinterface
 
// ---------------------------------------------------------
// MFIFO module
// ---------------------------------------------------------
// a mfifof of size 1
module mkMFIFOF1 (MFIFOF#(1,a))
provisos (Bits#(a,a_sz));
Reg#(Maybe#(a)) buffer <- mkReg(tagged Invalid);
RWire#(a) upW <- mkRWire();
RWire#(Bit#(0)) deqW <- mkRWire();
rule writeBuffer(isValid(upW.wget())
|| isValid(deqW.wget()));
if (isValid(deqW.wget()))
buffer <= tagged Invalid;
else
buffer <= tagged Valid fromMaybe(?,upW.wget());
endrule
method Action enq(a in) if (!isValid(buffer));
buffer <= tagged Valid in;
endmethod
method Action deq() if (isValid(buffer));
deqW.wset(?);
endmethod
method Action clear();
buffer <= tagged Invalid;
endmethod
method Bool notEmpty();
return isValid(buffer);
endmethod
method Bool notFull();
return !isValid(buffer);
endmethod
interface Reg first;
method Action _write(a in) if (isValid(buffer));
upW.wset(in);
endmethod
method a _read() if (buffer matches tagged Valid .val);
return val;
endmethod
endinterface
 
endmodule
 
// a mfifof of size > 1
module mkMFIFOF (MFIFOF#(sz,a))
provisos (Add#(2,xxA,sz), // sz >= 2
Bits#(a,a_sz));
Reg#(Maybe#(a)) buffer <- mkReg(tagged Invalid);
FIFOF#(a) fifo <- mkSizedFIFOF(valueOf(sz)-1);
RWire#(a) upW <- mkRWire();
RWire#(Bit#(0)) deqW <- mkRWire();
let isNotEmpty = isValid(buffer) || fifo.notEmpty;
rule writeBuffer(True);
if (isValid(deqW.wget()))
buffer <= tagged Invalid;
else
if (isValid(upW.wget()))
buffer <= tagged Valid fromMaybe(?,upW.wget());
else
if (!isValid(buffer))
buffer <= tagged Valid fifo.first();
if (!isValid(buffer))
fifo.deq();
endrule
method Action enq(a in);
fifo.enq(in);
endmethod
method Action deq() if (isNotEmpty);
deqW.wset(?);
endmethod
method Action clear();
fifo.clear();
buffer <= tagged Invalid;
endmethod
 
method Bool notEmpty();
return isNotEmpty;
endmethod
method Bool notFull();
return fifo.notFull();
endmethod
 
interface Reg first;
method Action _write(a in) if (isNotEmpty);
upW.wset(in);
endmethod
 
method a _read() if (isNotEmpty);
return isValid(buffer) ? fromMaybe(?,buffer) : fifo.first();
endmethod
endinterface
endmodule
 
// a mfifo of size 1
module mkMFIFO1 (MFIFO#(1,a))
provisos (Bits#(a,a_sz));
MFIFOF#(1,a) fifo <- mkMFIFOF1();
method Action enq(a in) = fifo.enq(in);
method Action deq() = fifo.deq();
method Action clear() = fifo.clear();
interface Reg first = fifo.first;
endmodule
 
// a mfifo of size > 1
module mkMFIFO (MFIFO#(sz,a))
provisos (Add#(2,xxA,sz), // sz >= 2
Bits#(a,a_sz));
MFIFOF#(sz,a) fifo <- mkMFIFOF();
method Action enq(a in) = fifo.enq(in);
method Action deq() = fifo.deq();
method Action clear() = fifo.clear();
interface Reg first = fifo.first;
endmodule
 
// ---------------------------------------------------------
// MFIFO Test module
// ---------------------------------------------------------
//(* synthesize *)
(* execution_order = "updOrDeqFIFO, enqFIFO, incrCounter" *)
module mkMFIFOTest(Empty);
Reg#(Bit#(16)) counter <- mkReg(0);
MFIFO#(10,Bit#(16)) fifo <- mkMFIFO();
Reg#(Bit#(16)) fstElm = fifo.first;
rule enqFIFO(True);
$display("enq fifo: %d",counter);
fifo.enq(counter);
endrule
rule updOrDeqFIFO(True);
if ((counter & 16'h0007) == 16'h0007)
begin
$display("deq fifo: %d",fstElm);
fifo.deq();
end
else
begin
$display("update fifo: %d = %d * 3",fstElm * 3,fstElm);
fstElm <= fstElm * 3;
end
endrule
rule incrCounter(True);
$display("cycle: %d",counter);
$display("----------------------------------------------------------");
if (counter == 1000)
$finish();
counter <= counter + 1;
endrule
endmodule
/reedsolomon/trunk/bluespec-source/preproc.cpp
0,0 → 1,286
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
#include <iostream>
#include <fstream>
#include <list>
#include <cstring>
#include <cstdlib>
#include <regex.h>
using namespace std;
 
#define mm 8
#define nn 255
 
int pp [mm + 1];
int alpha_to [255 + 2];
int index_of [255 + 2];
 
// --------------------------------------------------------------------
void generate_gf (int* pp)
{
int mask = 1;
 
alpha_to [mm] = 0 ;
for (int i = 0; i < mm; ++ i)
{
alpha_to [i] = mask;
index_of [alpha_to [i]] = i;
if (0 != pp [i])
alpha_to[mm] ^= mask;
mask <<= 1;
}
index_of [alpha_to [mm]] = mm;
mask >>= 1;
for (int i = mm + 1; i < nn; ++ i)
{
if (alpha_to [i - 1] >= mask)
alpha_to [i] = alpha_to [mm] ^ ((alpha_to [i - 1] ^ mask) << 1);
else
alpha_to [i] = alpha_to [i - 1] << 1;
index_of [alpha_to [i]] = i;
}
index_of [0] = -1;
}
 
 
// --------------------------------------------------------------------
unsigned char gfinv_lut (unsigned char a)
{
unsigned char result = (nn - index_of [a]) % nn;
return alpha_to[result];
}
 
 
// --------------------------------------------------------------------
void print (string& rLine)
{
string sLine (rLine);
string::size_type iLength = sLine.length ();
for (string::size_type i = 0; i < iLength; ++ i)
if ('\t' == sLine.at (i))
sLine [i] = ' ';
 
string::size_type iStart = sLine.find (" ");
while (string::npos != iStart)
{
string::size_type iEnd = iStart + 1;
while ((iEnd < iLength) && (' ' == sLine.at (iEnd)))
++ iEnd;
 
sLine.replace (iStart, iEnd - iStart, " ");
iLength = sLine.length ();
iStart = sLine.find (" ");
}
if (' ' == sLine.at (0))
sLine = sLine.substr (1);
cout << sLine << endl;
}
 
// --------------------------------------------------------------------
int main (int argc, char* argv [])
{
ifstream file;
file.open (argv [1]);
if (false == file.is_open ())
{
cerr << "Failed to open file '" << argv [1] << "'. Quitting." << endl;
return 1;
}
cout << endl;
 
string sPolynomial;
 
list <string> lstPotentialPolyDefs;
// while (false == file.eof ())
//{
char zLine [1000];
file.getline (zLine, 1000);
string sLine (zLine);
if (0 != strstr (zLine, "Polynomial "))
{
// we've found a line that may have the primitive
// polynomial defined in it. Now we need to read
// till the end of the line (till a ;) and store
// all that for later...
while (0 != strchr (zLine, ';'))
{
file.getline (zLine, 1000);
sLine += zLine;
}
lstPotentialPolyDefs.push_back (sLine);
}
// else if (0 != strstr (zLine, "IReedSolomon "))
// {
// // we've found the line where the ReedSolomon
// // decoder is instantiated. The primitive
// // polynomial will be used here. We can use this
// // to extract it...
// string sLine (zLine);
// while (0 == strchr (zLine, ';'))
// {
// file.getline (zLine, 1000);
// sLine += zLine;
// }
// cout << "Line with ReedSolomon decoder instantiation." << endl;
// cout << endl << "\t";
// print (sLine);
// cout << endl;
// // check that we have the correct line...
// if ((string::npos == sLine.find ("<-")) ||
// (string::npos == sLine.find ("mkReedSolomon")))
// {
// cout << "Got the wrong line! Can't continue." << endl;
// return 1;
// }
 
// // extract the polynomial used in the
// // mkReedSolomon line...
// string::size_type iStart = sLine.find ("(");
// string::size_type iEnd = sLine.rfind (")");
// string sPolynomialVariable = sLine.substr (iStart + 1, iEnd - iStart - 1);
 
// // check if the polynomial has been defined
// // in-place...
// regex_t regexp;
// string sPattern = "[0-9]'[bdohBDOH][0-9]*";
// int ret = regcomp (&regexp, sPattern.c_str (), REG_EXTENDED);
// if (0 != ret)
// {
// char zError [1000];
// regerror (ret, &regexp, zError, 1000);
// cerr << "Regular expression " << sPattern
// << " failed to compile. Error : " << zError << endl;
// return 1;
// }
// if (0 == regexec (&regexp, sPolynomialVariable.c_str (), 0, NULL, 0))
// {
// // we have an in-line definition of the poly...
// sPolynomial = sPolynomialVariable;
// cout << "Primitive polynomial found inline." << endl;
// cout << "polynomial : " << sPolynomial << endl;
// break;
// }
// else
// {
// we need to search through the lines we
// previously saved to find the location where
// the polynomial was defined...
cout << endl;
cout << "ReedSolomon instantiation uses a polynomial declared elsewhere."
<< endl << "Searching for the declaration." << endl << endl;
 
bool bPolynomialFound = false;
list <string>::iterator ite;
for (ite = lstPotentialPolyDefs.begin ();
ite != lstPotentialPolyDefs.end ();
++ ite)
{
string& rLine = *ite;
cout << "\t";
print (rLine);
cout << endl;
// if (string::npos != sLine.find ("primitive_polynomial"))
// {
string::size_type iStart = rLine.find ("=");
string::size_type iEnd = rLine.rfind (";");
++ iStart;
while (rLine.at (iStart) == ' ')
++ iStart;
 
sPolynomial = rLine.substr (iStart, iEnd - iStart);
cout << endl;
cout << "Primitive polynomial found as a separate declaration." << endl;
cout << "polynomial : " << sPolynomial << endl;
bPolynomialFound = true;
break;
// }
}
if (false == bPolynomialFound)
{
cerr << "Failed to find polynomial as a separate declaration, " << endl
<< "and polynomial is not present inline. Cannot continue." << endl;
return 1;
}
// }
// }
//}
 
 
// process extracted polynomial...
 
if (string::npos == sPolynomial.find ("b"))
{
cerr << "Currently only polynomials declared in the binary format are supported."
<< "Quitting. " << endl;
return 1;
}
int iLength = sPolynomial.length ();
int j = 0;
for (int i = iLength - 1; i > 2; -- i)
pp [j++] = ('1' == sPolynomial.at (i))? 1 : 0;
// The MSB of the primitive polynomial is always 1.
// This bit is not included in the polynomial
// declared in mkReedSolomon.
pp [j] = 1;
 
generate_gf (pp);
 
 
// generate the BlueSpec file with gf_inv...
cout << "Generating BlueSpec file with Galois field inversion code..." << endl;
ofstream ofsGenerated (argv [2]);
if (false == ofsGenerated.is_open ())
{
cerr << "Failed to open file '" << argv [2] << "' for writing. Quitting." << endl;
return 1;
}
 
// ofsGenerated << "import GFTypes::*;" << endl;
// ofsGenerated << endl << endl;
ofsGenerated << "// ---------------------------------------------------------" << endl;
ofsGenerated << "function Byte gf_inv (Byte a);" << endl;
ofsGenerated << endl;
ofsGenerated << " case (a) matches" << endl;
 
for (int i = 0; i < 256; ++ i)
{
unsigned char inv = gfinv_lut ((unsigned char) i);
ofsGenerated << " " << i << " : return " << (int) inv << ";" << endl;
}
 
ofsGenerated << " endcase" << endl;
ofsGenerated << "endfunction" << endl;
ofsGenerated << endl;
cout << "Done." << endl << endl;
}
 
 
 
 
 
 
/reedsolomon/trunk/bluespec-source/Berlekamp.bsv
0,0 → 1,244
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import FIFO::*;
import GFArith::*;
import GFTypes::*;
import MFIFO::*;
import UniqueWrappers::*;
import Vector::*;
 
typedef enum
{ CALC_D,
CALC_LAMBDA,
CALC_LAMBDA_2,
CALC_LAMBDA_3,
START,
BERLEKAMP_DONE
} Stage deriving (Bits, Eq);
 
// ---------------------------------------------------------
// Reed-Solomon Berlekamp algoritm interface
// ---------------------------------------------------------
interface IBerlekamp;
// input methods
method Action t_in(Byte t_new);
method Action s_in(Syndrome#(TwoT) syndrome_new);
// output methods
method ActionValue#(Bool) no_error_flag_out();
method ActionValue#(Syndrome#(T)) lambda_out();
method ActionValue#(Syndrome#(T)) omega_out();
endinterface
 
// ---------------------------------------------------------
// Reed-Solomon Berlekamp module
// ---------------------------------------------------------
(* synthesize *)
module mkBerlekamp(IBerlekamp);
// state elements
// ------------------------------------------------
// input fifos, to increase throughput, can have size > 1
FIFO#(Byte) t_q <- mkSizedFIFO(1);
FIFO#(Syndrome#(TwoT)) syndrome_q <- mkSizedFIFO(1);
// output fifos, for correctness, size need to be 1
MFIFO#(1,Syndrome#(TPlusTwo)) c_q <- mkMFIFO1(); // lambda
MFIFO#(1,Syndrome#(TPlusTwo)) w_q <- mkMFIFO1(); // omega
MFIFO#(1,Bool) no_error_flag_q <- mkMFIFO1();
// regs
Reg#(Syndrome#(TPlusTwo)) syn_shf_reg <- mkRegU;
Reg#(Syndrome#(TPlusTwo)) p <- mkRegU; // B
Reg#(Syndrome#(TPlusTwo)) a <- mkRegU; // A
 
Reg#(Byte) d <- mkRegU;
Reg#(Byte) dstar <- mkRegU;
Reg#(Byte) d_dstar <- mkRegU;
 
Reg#(Byte) i <- mkRegU;
Reg#(Byte) l <- mkRegU;
Reg#(Bool) is_i_gt_2l <- mkRegU; // is i + 1 > 2*l?
Reg#(Stage) stage <- mkReg(BERLEKAMP_DONE);
Reg#(Byte) block_number <- mkReg(0);
// function wrapper (for resource sharing)
// ------------------------------------------------
Wrapper2#(Syndrome#(TPlusTwo),
Syndrome#(TPlusTwo),
Syndrome#(TPlusTwo)) gf_mult_vec <- mkUniqueWrapper2(zipWith(gf_mult_inst));
Wrapper2#(Syndrome#(TPlusTwo),
Syndrome#(TPlusTwo),
Syndrome#(TPlusTwo)) gf_add_vec <- mkUniqueWrapper2(zipWith(gf_add_inst));
// define constants
// ------------------------------------------------
Syndrome#(TPlusTwo) p_init = replicate(0);
Syndrome#(TPlusTwo) c_init = replicate(0);
Syndrome#(TPlusTwo) w_init = replicate(0);
Syndrome#(TPlusTwo) a_init = replicate(0);
c_init[0] = 1;
p_init[0] = 1;
a_init[0] = 1;
let t = t_q.first();
let syndrome = syndrome_q.first();
Reg#(Syndrome#(TPlusTwo)) c = c_q.first;
Reg#(Syndrome#(TPlusTwo)) w = w_q.first;
Reg#(Bool) no_error_flag = no_error_flag_q.first;
// ------------------------------------------------
rule calc_d (stage == CALC_D);
let syn = syndrome[i];
let newSynShiftReg = shiftInAt0(syn_shf_reg,syn); // shift in one syndrome input to syn
let d_vec <- gf_mult_vec.func(c, newSynShiftReg); // get convolution
let new_d = fold( \^ ,d_vec);
let new_no_err_flag = no_error_flag && syndrome[i] == 0;
if (i < 2 * t)
begin
syn_shf_reg <= newSynShiftReg;
d <= new_d;
stage <= CALC_LAMBDA;
i <= i + 1;
no_error_flag <= new_no_err_flag;
end
else // i == 2 * t
begin
stage <= BERLEKAMP_DONE;
t_q.deq();
syndrome_q.deq();
if (no_error_flag) // no error, don't need to send lambda and omega
begin
c_q.deq();
w_q.deq();
end
end
$display (" [berlekamp %d] calc_d, L = %d, i = %d, d = %d, s [%d] = %d",
block_number, l, i, new_d, i, syn);
endrule
 
// ------------------------------------------------
rule calc_lambda (stage == CALC_LAMBDA);
stage <= (d == 0) ? CALC_D : CALC_LAMBDA_2;
d_dstar <= gf_mult_inst(d, dstar); // d_dstar = d * dstar
p <= shiftInAt0(p,0); // increase polynomial p degree by 1
a <= shiftInAt0(a,0); // increase polynomial a degree by 1
is_i_gt_2l <= (i > 2 * l); // check i + 2 > 2 * l?
 
//$display (" [berlekamp %d] calc_lambda. d = %d, dstar = %d, i(%d) > 2*L(%d)?", block_number, d, dstar, i, l);
endrule
// ------------------------------------------------
rule calc_lambda_2 (stage == CALC_LAMBDA_2);
let d_dstar_p <- gf_mult_vec.func(replicate(d_dstar),p);
let new_c <- gf_add_vec.func(c,d_dstar_p);
c <= new_c;
stage <= CALC_LAMBDA_3;
if (is_i_gt_2l) // p = old_c only if i + 1 > 2 * l
p <= c;
 
//$display (" [berlekamp %d] calc_lambda_2. c (%x) = d_d* (%x) x p (%x)", block_number, new_c, d_dstar, p);
endrule
// ------------------------------------------------
rule calc_lambda_3 (stage == CALC_LAMBDA_3);
let d_dstar_a <- gf_mult_vec.func(replicate(d_dstar),a);
let new_w <- gf_add_vec.func(w,d_dstar_a);
w <= new_w;
stage <= CALC_D;
if (is_i_gt_2l) // a = old_w only if i + 1 > 2 * l
begin
a <= w;
l <= i - l;
dstar <= gf_inv(d);
end
 
//$display (" [berlekamp %d] calc_lambda_3. w (%x) = d_d* (%x) x a (%x)", block_number, new_w, d_dstar, a);
endrule
 
// ------------------------------------------------
rule start_new_syndrome (stage == START);
//$display (" [berlekamp %d] start_new_syndrome t : %d, s : %x", block_number, t, syndrome);
 
block_number <= block_number + 1;
// initiatize state
p <= p_init;
a <= a_init;
c_q.enq(c_init);
w_q.enq(w_init);
no_error_flag_q.enq(True);
d <= 0;
dstar <= 1;
i <= 0;
l <= 0;
syn_shf_reg <= replicate(0);
// next state becomes calc_d
stage <= CALC_D;
endrule
// ------------------------------------------------
method Action t_in (Byte t_new);
$display (" [berlekamp %d] t_in : %d", block_number, t_new);
t_q.enq(t_new);
endmethod
// ------------------------------------------------
method Action s_in(Syndrome#(TwoT) syndrome_new) if (stage == BERLEKAMP_DONE);
//$display (" [berlekamp %d] s_in : %x", block_number, syndrome_new);
stage <= START;
syndrome_q.enq(syndrome_new);
endmethod
// ------------------------------------------------
method ActionValue#(Bool) no_error_flag_out() if (stage == BERLEKAMP_DONE);
$display (" [berlekamp %d] no_error_flag_out : %d", block_number, no_error_flag);
no_error_flag_q.deq();
return no_error_flag;
endmethod
// ------------------------------------------------
method ActionValue#(Syndrome#(T)) lambda_out() if (stage == BERLEKAMP_DONE);
//$display (" [berlekamp %d] lambda_out : %x", block_number, c);
c_q.deq();
return take(tail(c)); // drop lsb && msb
endmethod
// ------------------------------------------------
method ActionValue#(Syndrome#(T)) omega_out() if (stage == BERLEKAMP_DONE);
//$display (" [berlekamp %d] omega_out : %x", block_number, w);
w_q.deq();
return take(tail(w)); // drop lsb && msb
endmethod
endmodule
/reedsolomon/trunk/bluespec-source/README
0,0 → 1,9
Top level file for the decoder: mkReedSolomon.bsv
Top level testbench: mkTestbench.bsv
 
The testbench reads the corrupted data from the file input.dat
(with the first 2 terms being 'n' and 't' parameters) and writes
the decoded output to output.dat
 
Bluespec license required to compile the code to verilog.
Bluesim license required for running the testbench simulation.
/reedsolomon/trunk/bluespec-source/mkTestBench.bsv
0,0 → 1,192
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import GetPut::*;
import Vector::*;
import GFTypes::*;
import FIFO::*;
import Assert::*;
import RegFile::*;
import mkReedSolomon::*;
 
import "BDPI" function Action loadByteStream ();
import "BDPI" function ActionValue# (Byte) getNextStreamByte ();
import "BDPI" function Action storeByteStream ();
import "BDPI" function Action putNextStreamByte (Byte writeByte);
import "BDPI" function Action putMACData (Byte n, Byte t);
import "BDPI" function ActionValue# (Byte) isStreamActive ();
import "BDPI" function Action closeOutputFile ();
//Polynomial primitive_Sypolynomial = 8'b00011101;
module mkTestBench ();
 
// Define Primitive polynomial
// P (x) = x**8 + x**4 + x**3 + x**2 + 1 = 0 ; Ignore highest degree (8)
IReedSolomon rs <- mkReedSolomon;
 
Reg# (Bool) read_done <- mkReg (False);
Reg# (int) bytes_in <- mkReg (0);
Reg# (Bit#(32)) bytes_out <- mkReg (0);
Reg# (Bit#(32)) last_bytes_out <- mkReg (0);
Reg# (int) last_bytes_in <- mkReg (0);
Reg# (int) watchdog <- mkReg (0);
Reg# (Bool) finished <- mkReg (False);
Reg# (int) state <- mkReg (0);
Reg# (Byte) bytes_in_block <- mkReg (0);
Reg# (Byte) t <- mkReg (0);
Reg# (Byte) n <- mkReg (0);
Reg# (Bit#(32)) bytes_out_exp <- mkReg (0);
 
FIFO#(Bit#(32)) ff_bytes_out_exp <- mkSizedFIFO (10);
FIFO#(Byte) ff_n <- mkSizedFIFO (10);
FIFO#(Byte) ff_t <- mkSizedFIFO (10);
 
// -------------------------------------------
rule init (state==0);
$display ("init\n");
loadByteStream ();
storeByteStream ();
state <= 1;
endrule
 
// -------------------------------------------
rule input_control_info (state == 1 && read_done == False && bytes_in_block == n);
 
let n_in <- getNextStreamByte ();
let t_in <- getNextStreamByte ();
let not_eof <- isStreamActive ();
 
if (not_eof != 0)
begin
n <= n_in;
t <= t_in;
bytes_in_block <= 0;
rs.rs_t_in.put (t_in);
rs.rs_k_in.put (n_in - 2*t_in);
 
Byte temp = n_in - 2*t_in;
bytes_out_exp <= bytes_out_exp + zeroExtend(temp);
 
ff_bytes_out_exp.enq (bytes_out_exp);
ff_n.enq (n_in);
ff_t.enq (t_in);
 
$display (" [mac in] n = %d, t = %d, k = %d", n_in, t_in, n_in - 2*t_in);
end
else
begin
read_done <= True;
$display (" [reads done] bytes in : %d", bytes_in - 1);
end
endrule
 
 
// -------------------------------------------
rule input_data (state == 1 && read_done == False && bytes_in_block < n);
Byte not_eof <- isStreamActive ();
if (not_eof != 0)
begin
Byte datum <- getNextStreamByte ();
rs.rs_input.put (datum);
 
bytes_in_block <= bytes_in_block + 1;
 
// the way getNextStreamByte operates, we'll get one more character
// than what is in the input file. So we need to adjust for this in
// the way we use bytes_in...
bytes_in <= bytes_in + 1;
$display (" [bytes in] byte (%d) = %d, block bytes %d", bytes_in, datum, bytes_in_block);
end
else
begin
read_done <= True;
$display (" [reads done] bytes in : %d", bytes_in - 1);
end
endrule
 
 
// -------------------------------------------
rule output_data (state == 1);
Byte next_byte <- rs.rs_output.get ();
putNextStreamByte (next_byte);
bytes_out <= bytes_out + 1;
$display (" [bytes out] %d / %d", bytes_out, bytes_in - 1);
endrule
 
 
// -------------------------------------------
rule output_mac (state == 1 && bytes_out == ff_bytes_out_exp.first ());
ff_bytes_out_exp.deq ();
ff_n.deq ();
ff_t.deq ();
putMACData (ff_n.first (), ff_t.first ());
endrule
 
 
// -------------------------------------------
rule print_flag (state == 1);
Bool cant_correct_flag <- rs.rs_flag.get ();
$display (" [cant correct flag] %d", cant_correct_flag);
endrule
 
// -------------------------------------------
rule watchdog_timer (state == 1);
if ((last_bytes_out == bytes_out) &&
(last_bytes_in == bytes_in))
watchdog <= watchdog + 1;
else
begin
last_bytes_in <= bytes_in;
last_bytes_out <= bytes_out;
watchdog <= 0;
end
 
if (watchdog == 2000)
begin
$display ("[WARNING] Watchdog timer expired.");
$display ("There has been no output in the last 100 clock cycles.");
$display ("Exiting");
 
closeOutputFile ();
$finish (0);
end
endrule
 
 
// -------------------------------------------
rule exit (read_done == True && (bytes_out_exp) == bytes_out);
closeOutputFile ();
$display (" [bytes written] %d", bytes_out);
$finish (0);
endrule
endmodule
/reedsolomon/trunk/bluespec-source/RSParameters.bsv
0,0 → 1,42
Polynomial primitive_poly = 8'b00011101;
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
//**********************************************************************
// Reed-Solomon Decoder Parameters
//----------------------------------------------------------------------
// $Id: RSParameters.bsv
//
 
// compile-time parameters that can be changed by users, K + 2T = 255
 
// no. bytes of actual data out of 255 bytes of codeword
typedef 223 K;
 
// 2T = no. byte parity bytes
typedef 16 T;
 
/reedsolomon/trunk/bluespec-source/GFInv.bsv
0,0 → 1,263
// ---------------------------------------------------------
function Byte gf_inv (Byte a);
 
case (a) matches
0 : return 2;
1 : return 1;
2 : return 142;
3 : return 244;
4 : return 71;
5 : return 167;
6 : return 122;
7 : return 186;
8 : return 173;
9 : return 157;
10 : return 221;
11 : return 152;
12 : return 61;
13 : return 170;
14 : return 93;
15 : return 150;
16 : return 216;
17 : return 114;
18 : return 192;
19 : return 88;
20 : return 224;
21 : return 62;
22 : return 76;
23 : return 102;
24 : return 144;
25 : return 222;
26 : return 85;
27 : return 128;
28 : return 160;
29 : return 131;
30 : return 75;
31 : return 42;
32 : return 108;
33 : return 237;
34 : return 57;
35 : return 81;
36 : return 96;
37 : return 86;
38 : return 44;
39 : return 138;
40 : return 112;
41 : return 208;
42 : return 31;
43 : return 74;
44 : return 38;
45 : return 139;
46 : return 51;
47 : return 110;
48 : return 72;
49 : return 137;
50 : return 111;
51 : return 46;
52 : return 164;
53 : return 195;
54 : return 64;
55 : return 94;
56 : return 80;
57 : return 34;
58 : return 207;
59 : return 169;
60 : return 171;
61 : return 12;
62 : return 21;
63 : return 225;
64 : return 54;
65 : return 95;
66 : return 248;
67 : return 213;
68 : return 146;
69 : return 78;
70 : return 166;
71 : return 4;
72 : return 48;
73 : return 136;
74 : return 43;
75 : return 30;
76 : return 22;
77 : return 103;
78 : return 69;
79 : return 147;
80 : return 56;
81 : return 35;
82 : return 104;
83 : return 140;
84 : return 129;
85 : return 26;
86 : return 37;
87 : return 97;
88 : return 19;
89 : return 193;
90 : return 203;
91 : return 99;
92 : return 151;
93 : return 14;
94 : return 55;
95 : return 65;
96 : return 36;
97 : return 87;
98 : return 202;
99 : return 91;
100 : return 185;
101 : return 196;
102 : return 23;
103 : return 77;
104 : return 82;
105 : return 141;
106 : return 239;
107 : return 179;
108 : return 32;
109 : return 236;
110 : return 47;
111 : return 50;
112 : return 40;
113 : return 209;
114 : return 17;
115 : return 217;
116 : return 233;
117 : return 251;
118 : return 218;
119 : return 121;
120 : return 219;
121 : return 119;
122 : return 6;
123 : return 187;
124 : return 132;
125 : return 205;
126 : return 254;
127 : return 252;
128 : return 27;
129 : return 84;
130 : return 161;
131 : return 29;
132 : return 124;
133 : return 204;
134 : return 228;
135 : return 176;
136 : return 73;
137 : return 49;
138 : return 39;
139 : return 45;
140 : return 83;
141 : return 105;
142 : return 2;
143 : return 245;
144 : return 24;
145 : return 223;
146 : return 68;
147 : return 79;
148 : return 155;
149 : return 188;
150 : return 15;
151 : return 92;
152 : return 11;
153 : return 220;
154 : return 189;
155 : return 148;
156 : return 172;
157 : return 9;
158 : return 199;
159 : return 162;
160 : return 28;
161 : return 130;
162 : return 159;
163 : return 198;
164 : return 52;
165 : return 194;
166 : return 70;
167 : return 5;
168 : return 206;
169 : return 59;
170 : return 13;
171 : return 60;
172 : return 156;
173 : return 8;
174 : return 190;
175 : return 183;
176 : return 135;
177 : return 229;
178 : return 238;
179 : return 107;
180 : return 235;
181 : return 242;
182 : return 191;
183 : return 175;
184 : return 197;
185 : return 100;
186 : return 7;
187 : return 123;
188 : return 149;
189 : return 154;
190 : return 174;
191 : return 182;
192 : return 18;
193 : return 89;
194 : return 165;
195 : return 53;
196 : return 101;
197 : return 184;
198 : return 163;
199 : return 158;
200 : return 210;
201 : return 247;
202 : return 98;
203 : return 90;
204 : return 133;
205 : return 125;
206 : return 168;
207 : return 58;
208 : return 41;
209 : return 113;
210 : return 200;
211 : return 246;
212 : return 249;
213 : return 67;
214 : return 215;
215 : return 214;
216 : return 16;
217 : return 115;
218 : return 118;
219 : return 120;
220 : return 153;
221 : return 10;
222 : return 25;
223 : return 145;
224 : return 20;
225 : return 63;
226 : return 230;
227 : return 240;
228 : return 134;
229 : return 177;
230 : return 226;
231 : return 241;
232 : return 250;
233 : return 116;
234 : return 243;
235 : return 180;
236 : return 109;
237 : return 33;
238 : return 178;
239 : return 106;
240 : return 227;
241 : return 231;
242 : return 181;
243 : return 234;
244 : return 3;
245 : return 143;
246 : return 211;
247 : return 201;
248 : return 66;
249 : return 212;
250 : return 232;
251 : return 117;
252 : return 127;
253 : return 255;
254 : return 126;
255 : return 253;
endcase
endfunction
 
/reedsolomon/trunk/bluespec-source/ChienSearch.bsv
0,0 → 1,247
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import FIFO::*;
import GFArith::*;
import GFTypes::*;
import MFIFO::*;
import UniqueWrappers::*;
import Vector::*;
 
typedef enum
{
LOC_SEARCH,
LOC_DONE
} Stage deriving (Bits, Eq);
 
// ---------------------------------------------------------
// Reed-Solomon Chien Error Magnitude computer interface
// ---------------------------------------------------------
interface IChienSearch;
// input methods
method Action t_in(Byte t_new);
method Action k_in(Byte k_new);
method Action no_error_flag_in(Bool no_error_new);
method Action lambda_in(Syndrome#(T) lamdba_new);
// output methods
method ActionValue#(Maybe#(Byte)) loc_out(); // use Invalid to show new packet
method ActionValue#(Maybe#(Byte)) alpha_inv_out(); // the alpha_inv of location that has error
method ActionValue#(Bool) cant_correct_flag_out();
method ActionValue#(Syndrome#(T)) lambda_out();
endinterface
 
// ---------------------------------------------------------
// Auxiliary Function
// ---------------------------------------------------------
(* noinline *)
function Syndrome#(T) times_alpha_n_v(Syndrome#(T) lambda_a, Byte t);
Syndrome#(T) lambda_a_new = lambda_a;
for (Byte x = 0; x < fromInteger(valueOf(T)); x = x + 1)
lambda_a_new[x] = times_alpha_n(lambda_a[x], x + 1) & ((x < t)? 8'hFF : 8'h00);
return lambda_a_new;
endfunction
 
// ---------------------------------------------------------
// Reed-Solomon Chien Error Magnitude computer module
// ---------------------------------------------------------
(* synthesize *)
module mkChienSearch (IChienSearch);
// comb. circuit sharing
Wrapper2#(Syndrome#(T),Byte,
Syndrome#(T)) times_alpha_n_vec <- mkUniqueWrapper2(times_alpha_n_v);
// input queues
FIFO#(Bool) no_error_flag_q <- mkSizedFIFO(1);
FIFO#(Byte) t_q <- mkSizedFIFO(1);
FIFO#(Byte) k_q <- mkSizedFIFO(1);
FIFO#(Syndrome#(T)) lambda_q <- mkSizedFIFO(1);
// output queues
FIFO#(Bool) cant_correct_flag_q <- mkSizedFIFO(1);
FIFO#(Maybe#(Byte)) loc_q <- mkSizedFIFO(2);
FIFO#(Maybe#(Byte)) alpha_inv_q <- mkSizedFIFO(2);
MFIFO#(1,Syndrome#(T)) lambda_a_q <- mkMFIFO1();
// book-keep state
Reg#(Byte) i <- mkRegU();
Reg#(Byte) count_error <- mkRegU();
Reg#(Stage) stage <- mkReg(LOC_DONE);
Reg#(Byte) block_number <- mkReg(0);
Reg#(Byte) alpha_inv <- mkRegU();
 
// variables
let no_error_flag = no_error_flag_q.first();
let t = t_q.first();
let k = k_q.first();
Reg#(Syndrome#(T)) lambda_a = lambda_a_q.first;
// ------------------------------------------------
rule calc_loc (stage == LOC_SEARCH);
$display (" [chien %d] calc_loc, i = %d", block_number, i);
let zero_padding = (i >= k + 2 * t);
let parity_bytes = (i < 2 * t);
let process_error = ((i < k + 2 * t) && (i >= 2 * t));
Byte result_location = 1;
 
if (!no_error_flag)
begin
result_location = fold(gf_add, cons(1,lambda_a)); // lambda_a add up + 1
alpha_inv <= times_alpha(alpha_inv);
 
$display (" [chien %d] calc_loc, result location = %d", block_number, result_location);
end
let is_no_error = (result_location != 0);
if (!is_no_error)
count_error <= count_error + 1;
if (i == 0)
begin
stage <= LOC_DONE;
cant_correct_flag_q.enq(count_error == 0);
t_q.deq();
k_q.deq();
no_error_flag_q.deq();
if (!no_error_flag)
begin
lambda_a_q.deq();
loc_q.enq(tagged Invalid);
alpha_inv_q.enq(tagged Invalid);
end
end
else
begin
i <= i - 1;
if (!no_error_flag)
begin
let lambda_a_new <- times_alpha_n_vec.func(lambda_a,t);
lambda_a <= lambda_a_new;
 
//$display (" [chien %d] calc_loc, lambda_a = %d", block_number, lambda_a_new);
end
if (process_error)
begin
if (!is_no_error) // enq loc_q an alpha_inv_q if there is error
begin
alpha_inv_q.enq(tagged Valid alpha_inv);
loc_q.enq(tagged Valid (k + 2 * t - i - 1)); // process range 1 - k
end
end
 
end
endrule
// ------------------------------------------------
rule start_next_chien (stage == LOC_DONE);
$display ("Start Next Chien ");
stage <= LOC_SEARCH;
i <= 254;
count_error <= no_error_flag ? 1 : 0;
block_number <= block_number + 1;
if (!no_error_flag)
begin
let lambda_a_new <- times_alpha_n_vec.func(lambda_a,t);
lambda_a <= lambda_a_new; // if correctable, initialize lambda_a
alpha_inv <= 2; // = alpha^(1) = alpha^(-254)
end
endrule
 
// ------------------------------------------------
method Action no_error_flag_in (Bool no_error_new);
$display (" [chien %d] no_error_in : %d", block_number, no_error_new);
no_error_flag_q.enq(no_error_new);
endmethod
// ------------------------------------------------
method Action t_in (Byte t_new);
$display (" [chien %d] t_in : %d", block_number, t_new);
 
t_q.enq(t_new);
endmethod
// ------------------------------------------------
method Action k_in (Byte k_new);
$display (" [chien %d] k_in : %d", block_number, k_new);
k_q.enq(k_new);
endmethod
// ------------------------------------------------
method Action lambda_in(Syndrome#(T) lambda_new);
//$display (" [chien %d] lambda_in : %d", block_number, lambda_new);
lambda_a_q.enq(lambda_new);
lambda_q.enq(lambda_new);
endmethod
// ------------------------------------------------
method ActionValue#(Maybe#(Byte)) loc_out();
$display (" [chien %d] loc_out : %d, stage : %d", block_number, loc_q.first(), stage);
loc_q.deq();
$display ("No of Errors %d", count_error);
return loc_q.first();
endmethod
// ------------------------------------------------
method ActionValue#(Maybe#(Byte)) alpha_inv_out();
$display (" [chien %d] alpha_inv_out : %d, stage : %d", block_number, alpha_inv_q.first(), stage);
alpha_inv_q.deq();
$display ("No of Errors %d", count_error);
return alpha_inv_q.first();
endmethod
// ------------------------------------------------
method ActionValue#(Bool) cant_correct_flag_out();
$display (" [chien %d] Can't Correct Flag : %d", block_number, cant_correct_flag_q.first());
 
cant_correct_flag_q.deq();
return cant_correct_flag_q.first();
endmethod
// ------------------------------------------------
method ActionValue#(Syndrome#(T)) lambda_out();
//$display (" [chien %d] lambda_out : %d", block_number, lambda_q.first());
lambda_q.deq();
return lambda_q.first();
endmethod
endmodule
 
 
 
 
 
 
/reedsolomon/trunk/bluespec-source/ErrorCorrector.bsv
0,0 → 1,128
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import GFArith::*;
import GFTypes::*;
import Vector::*;
import GetPut::*;
import FIFO::*;
 
// ---------------------------------------------------------
// Reed-Solomon error corrector interface
// ---------------------------------------------------------
interface IErrorCorrector;
method Action r_in (Byte datum);
method Action e_in (Byte datum);
method Action k_in (Byte k_new);
method Action no_error_flag_in (Bool no_error);
 
method ActionValue#(Byte) d_out ();
endinterface
 
// ---------------------------------------------------------
// Reed-Solomon error corrector module
// ---------------------------------------------------------
(* synthesize *)
module mkErrorCorrector (IErrorCorrector);
 
FIFO#(Byte) r <- mkSizedFIFO(2);
FIFO#(Byte) e <- mkSizedFIFO(2);
FIFO#(Byte) d <- mkSizedFIFO(2);
FIFO#(Byte) k <- mkSizedFIFO(1);
FIFO#(Bool) no_error_flag <- mkSizedFIFO(1);
Reg#(Byte) e_cnt <- mkReg(0);
Reg#(Byte) block_number <- mkReg(0);
 
rule d_no_error (e_cnt < k.first() && no_error_flag.first());
$display (" [error corrector %d] No Error processing", block_number);
r.deq();
d.enq(r.first());
if (e_cnt == k.first()-1)
begin
block_number <= block_number + 1;
k.deq();
no_error_flag.deq();
e_cnt <= 0;
end
else
e_cnt <= e_cnt + 1;
endrule
 
rule d_corrected (e_cnt < k.first() && !no_error_flag.first());
$display (" [error corrector %d] Correction processing", block_number);
r.deq();
e.deq();
d.enq(r.first() ^ e.first());
if (e_cnt == k.first()-1)
begin
block_number <= block_number + 1;
k.deq();
no_error_flag.deq();
e_cnt <= 0;
end
else
e_cnt <= e_cnt + 1;
endrule
 
// ------------------------------------------------
method Action r_in (Byte datum);
$display (" [error corrector %d] r_in : %d)", block_number, datum);
r.enq(datum);
endmethod
 
// ------------------------------------------------
method Action e_in (Byte datum);
e.enq(datum);
$display (" [error corrector %d] Valid e_in : %d)", block_number, datum);
endmethod
 
// ------------------------------------------------
method Action k_in (Byte k_new);
$display (" [error corrector %d] k_in : %d", block_number, k_new);
 
k.enq(k_new);
endmethod
 
// ------------------------------------------------
method Action no_error_flag_in (Bool no_error);
$display (" [error corrector %d] no_error : %d", block_number, no_error);
 
no_error_flag.enq(no_error);
endmethod
 
// ------------------------------------------------
method ActionValue#(Byte) d_out ();
$display (" [error corrector %d] d_out (%d)", block_number, d.first());
d.deq();
return d.first();
endmethod
 
endmodule
 
 
 
/reedsolomon/trunk/bluespec-source/input.dat
0,0 → 1,2560
255 16
31
58
124
130
132
223
158
20
15
174
246
1
1
100
79
109
113
171
134
96
51
162
106
91
137
76
15
131
155
106
236
43
246
179
106
209
123
171
179
79
32
50
70
175
196
112
27
16
120
226
245
215
25
29
75
6
176
164
150
112
115
56
192
36
56
189
29
44
138
129
8
112
109
213
147
179
246
55
26
160
201
216
139
19
108
166
110
64
48
93
174
78
 
2
7
12
51
155
35
26
19
50
219
184
221
91
153
86
109
64
20
182
108
228
163
43
117
17
144
225
93
172
71
243
206
107
231
25
135
240
61
89
83
128
31
134
237
88
66
181
211
47
19
64
111
146
154
147
178
226
153
104
221
219
12
180
226
245
219
45
157
187
58
203
145
197
68
55
131
18
162
147
191
128
164
218
222
182
248
73
5
189
92
40
247
21
216
181
88
31
241
208
41
115
134
89
66
49
148
239
82
33
237
227
161
236
225
148
177
59
236
220
196
71
79
66
188
184
194
134
244
126
73
201
84
74
46
164
157
40
128
200
195
237
40
41
77
115
34
189
171
245
163
203
137
250
40
84
206
103
37
209
220
17
127
255 16
29
199
104
172
153
57
217
205
158
145
109
92
244
73
137
12
47
221
211
18
158
227
220
189
17
193
40
25
15
155
187
43
104
235
87
93
7
156
125
193
139
37
253
26
192
160
16
28
62
238
53
224
209
27
149
247
177
139
93
227
51
206
211
10
227
185
223
68
16
88
194
113
100
92
9
163
98
32
230
92
29
26
75
217
104
9
154
205
88
141
16
40
233
25
42
159
169
135
128
158
242
102
103
191
248
232
188
6
3
203
17
67
177
66
62
153
175
13
189
48
162
245
252
74
111
162
30
11
147
26
54
51
108
126
3
242
229
239
243
191
26
206
4
23
145
49
219
126
105
198
50
87
134
90
44
100
15
3
211
96
173
182
47
120
152
19
254
37
212
36
186
3
60
209
59
19
199
20
76
17
64
215
43
34
75
40
143
174
85
29
48
53
30
27
120
114
61
217
106
209
231
232
198
41
10
39
198
181
211
115
229
29
140
2
146
155
210
114
125
31
253
20
187
2
60
32
92
235
151
35
48
236
58
67
231
220
136
59
253
254
14
55
251
31
98
87
207
25
181
4
48
217
144
96
205
255 16
69
193
182
145
61
192
140
25
40
128
7
160
134
98
84
202
117
148
241
131
111
191
58
247
120
155
241
11
127
189
138
229
233
222
6
100
150
187
39
175
125
119
135
64
76
165
198
240
36
50
72
118
71
158
6
108
27
52
128
153
210
170
222
133
72
73
61
229
62
174
39
61
42
225
120
90
128
147
168
173
234
169
111
217
130
209
234
128
96
213
186
77
97
148
72
97
11
141
190
1
132
69
195
206
96
227
177
210
168
254
61
16
38
157
237
1
112
21
197
19
115
37
4
 
137
185
162
10
8
120
60
180
228
222
29
141
59
177
149
151
216
159
33
36
44
216
59
92
161
160
15
114
154
73
92
127
177
42
204
82
146
92
151
87
163
106
247
162
216
244
117
179
114
72
232
206
54
153
77
46
5
196
22
27
151
50
177
94
150
111
186
59
184
45
95
 
144
2
44
36
130
45
202
162
17
78
129
8
147
136
24
232
44
226
105
57
154
65
163
90
182
140
219
178
222
63
56
197
214
106
150
220
222
215
191
17
185
82
80
15
143
76
37
133
132
99
161
178
37
233
144
98
137
121
10
255 16
122
239
240
81
255
29
209
165
98
51
209
191
211
64
177
211
186
149
189
64
82
165
208
13
109
59
31
40
199
122
27
130
84
208
188
229
232
167
228
22
74
76
226
199
178
81
173
121
67
23
110
68
56
149
237
69
114
164
13
69
37
73
196
110
230
21
 
210
92
152
50
129
153
145
26
56
14
149
11
253
222
215
86
242
35
73
55
45
126
194
127
182
97
175
109
20
183
103
159
218
253
160
103
97
131
131
44
15
182
50
167
235
180
13
186
245
202
115
172
198
97
207
72
76
246
6
116
220
104
254
114
156
29
226
52
115
204
249
103
202
124
154
48
190
65
70
72
3
18
219
125
20
215
65
215
26
157
117
105
202
224
143
104
169
22
57
11
2
125
204
153
188
88
233
117
62
51
108
133
252
4
59
59
188
163
98
176
209
147
216
98
55
121
46
157
20
187
62
103
191
116
174
71
26
181
9
184
54
103
73
193
70
151
215
12
208
206
214
110
92
95
52
153
54
14
116
123
133
31
255
236
126
125
241
64
226
200
111
12
250
 
47
101
143
126
84
172
203
199
219
102
153
40
50
216
255 16
202
187
222
68
98
 
186
225
75
48
94
150
51
105
145
44
57
160
198
170
127
63
150
251
230
116
233
45
24
241
226
17
 
99
228
232
198
180
192
62
42
146
208
54
157
244
209
141
32
135
20
131
88
34
17
184
92
247
74
7
241
127
44
23
155
47
40
136
138
45
108
242
243
219
100
15
211
74
121
156
47
241
114
158
196
25
110
85
6
201
217
218
227
251
238
19
164
249
27
150
56
144
142
227
7
26
149
55
26
135
42
143
44
88
48
111
18
163
122
43
229
220
234
207
87
243
246
13
192
138
8
83
136
116
78
207
254
13
12
137
91
208
95
187
69
139
244
230
189
156
63
21
133
246
216
73
51
107
5
108
2
147
5
183
116
64
194
117
177
59
41
158
138
211
198
94
204
87
167
167
23
72
59
59
195
108
67
197
105
113
103
73
30
195
243
254
141
135
75
19
176
85
215
44
6
110
181
37
64
95
108
218
131
206
247
253
2
209
93
32
83
162
84
108
32
134
205
61
33
239
122
34
199
154
128
29
231
247
43
250
64
46
174
109
8
244
252
239
67
87
194
188
40
22
211
255 16
214
117
71
12
39
218
127
209
184
138
152
146
97
106
9
57
237
133
165
184
200
202
152
154
28
210
77
216
72
50
2
190
222
235
75
191
91
159
240
82
132
101
214
209
59
212
81
52
188
217
32
46
174
196
76
67
138
27
213
136
82
22
115
31
144
170
206
8
26
139
123
177
42
2
128
6
24
118
20
141
43
90
225
107
58
49
108
1
199
191
21
51
132
199
80
135
144
66
140
103
97
120
49
35
233
9
240
137
75
185
171
190
31
175
253
57
104
172
234
147
58
77
226
251
55
13
250
40
223
19
54
61
142
39
50
95
188
54
221
139
153
250
192
229
71
81
77
211
113
157
176
62
21
212
1
14
44
231
241
162
131
15
11
47
105
250
128
49
155
226
202
179
179
111
151
114
222
175
35
51
135
218
61
7
167
25
28
137
99
226
150
84
164
15
173
56
94
157
101
231
47
90
28
64
143
230
78
171
39
71
245
128
50
35
233
30
180
57
241
14
61
135
166
60
125
121
141
227
255
66
143
107
183
251
229
40
199
215
38
96
41
192
207
 
178
243
58
119
250
81
232
59
19
67
152
255 16
174
151
119
113
111
110
85
157
176
202
166
204
198
109
199
113
61
40
23
157
122
51
170
143
156
149
205
118
211
51
9
184
25
191
220
211
226
55
168
116
164
159
87
229
57
252
212
158
172
227
242
234
149
20
192
38
193
153
109
27
26
72
218
68
219
164
43
110
145
8
29
189
102
90
17
153
79
240
171
193
78
221
41
110
82
39
184
166
126
36
63
213
108
54
24
109
19
35
81
210
160
193
172
203
10
31
237
141
162
205
151
222
138
1
180
171
168
148
102
168
183
9
188
253
34
244
27
63
129
142
38
211
183
141
221
124
124
31
244
194
66
149
42
222
88
31
68
 
220
93
234
184
229
198
225
226
114
140
25
172
214
151
245
58
17
189
134
184
220
95
152
99
61
10
153
87
66
230
20
36
119
35
213
2
84
85
201
196
181
128
182
155
134
55
179
87
224
39
32
120
33
141
200
228
199
178
67
30
111
239
77
116
206
128
56
142
159
72
14
26
248
127
230
252
154
136
177
249
173
86
199
234
157
240
7
162
245
246
247
17
64
238
15
240
144
50
40
5
15
166
187
205
201
165
58
255 16
182
27
152
89
21
205
80
25
207
124
170
185
127
211
205
93
50
115
166
105
105
124
124
221
166
39
38
133
140
245
250
163
61
214
47
94
215
144
26
42
90
79
209
88
207
90
132
200
9
42
235
139
212
84
183
33
153
47
137
232
183
35
116
222
254
158
67
173
53
202
88
1
126
118
211
7
81
89
219
125
84
151
210
179
186
136
150
176
118
102
115
216
36
213
154
81
104
120
84
52
75
224
44
119
37
121
43
211
5
68
169
160
219
74
29
9
17
47
61
157
66
157
61
209
109
34
251
51
45
114
8
210
187
177
76
81
116
229
41
100
103
95
131
210
56
236
203
115
236
158
95
111
48
26
212
57
244
137
43
89
182
85
134
106
61
101
39
16
126
201
223
147
38
150
7
196
254
44
19
125
109
68
153
246
37
75
14
155
210
213
209
75
23
32
66
45
230
93
47
233
162
73
140
97
150
217
176
129
189
205
226
118
31
77
232
137
120
55
200
134
189
176
9
141
37
128
81
29
 
126
190
56
159
93
40
115
99
196
125
170
224
228
159
221
7
149
168
101
43
137
165
89
244
235
67
255 16
178
41
150
214
2
139
202
152
222
124
233
121
105
197
93
8
70
138
173
76
172
12
185
204
127
95
36
167
120
67
165
219
27
120
158
214
7
62
90
211
109
119
245
86
180
207
150
248
221
161
146
222
139
90
168
215
229
224
2
155
39
44
60
68
113
96
123
51
207
226
220
23
193
38
190
187
241
244
102
254
21
56
54
178
115
198
213
73
184
213
95
226
186
218
200
62
144
151
85
184
32
182
87
6
52
200
84
242
223
45
199
97
195
110
220
42
14
 
233
213
27
131
26
124
74
48
231
214
119
158
96
26
129
142
176
65
232
39
42
125
105
89
132
152
95
220
64
56
228
101
187
158
56
232
147
115
184
73
118
92
28
209
104
64
164
137
23
107
188
207
248
207
248
166
88
39
247
217
124
70
45
209
10
196
48
73
251
91
45
164
243
218
44
222
41
57
203
70
113
236
214
81
118
208
173
125
170
177
172
170
59
104
160
191
199
212
28
87
103
81
119
21
176
179
55
45
249
201
64
106
177
187
195
83
37
57
229
243
234
128
76
38
219
121
55
24
46
186
159
23
47
214
110
108
28
255 16
30
226
143
154
143
173
153
80
143
26
119
177
190
83
69
45
148
218
174
17
62
230
115
8
42
153
6
63
90
195
43
125
108
194
154
102
99
86
154
208
177
82
248
172
224
222
77
131
155
199
156
53
187
217
2
233
62
65
20
220
87
104
226
6
95
68
202
145
163
72
215
4
113
25
95
93
66
133
229
102
11
194
51
209
155
192
213
97
232
171
249
81
8
158
59
205
159
130
184
158
213
189
164
20
214
217
118
219
121
34
50
57
39
113
250
57
214
42
103
151
162
90
21
58
253
184
20
 
171
249
249
193
230
202
156
250
95
83
168
64
250
191
61
236
154
208
209
63
134
12
129
103
92
92
38
252
12
25
6
233
19
46
36
235
106
72
81
30
88
231
3
13
37
107
26
91
74
197
188
30
175
37
65
94
80
12
245
34
6
215
196
38
195
219
153
76
239
104
26
74
194
151
241
201
33
84
157
43
22
151
220
80
212
52
103
45
6
30
93
222
20
231
140
204
252
68
230
204
86
75
76
232
228
149
55
241
88
107
134
91
85
74
92
48
116
37
14
32
65
60
211
210
244
188
129
/reedsolomon/trunk/bluespec-source/SyndromeParallel.bsv
0,0 → 1,95
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import FIFO::*;
import GFArith::*;
import GFTypes::*;
import Vector::*;
 
// ---------------------------------------------------------
// Reed-Solomon Syndrome calculator interface
// ---------------------------------------------------------
interface ISyndrome;
method Action n_in(Byte n_new); // dynamic n (shorten/punctured codeword)
method Action r_in(Byte datum);
 
method ActionValue#(Syndrome#(TwoT)) s_out();
endinterface
 
// ---------------------------------------------------------
// Reed-Solomon Syndrome calculation module
// ---------------------------------------------------------
(* synthesize *)
module mkSyndromeParallel(ISyndrome);
 
Reg#(Syndrome#(32)) syndrome <- mkReg(replicate(0));
FIFO#(Byte) n_q <- mkSizedFIFO(2);
Reg#(Byte) i <- mkReg(0);
Reg#(Byte) block_number <- mkReg(1);
let n = n_q.first();
 
// ------------------------------------------------
method Action r_in (Byte datum) if (i < n);
$display (" [syndrome %d] r_in (%d): %d", block_number, i, datum);
Syndrome#(TwoT) syndrome_temp = replicate(0);
for (Byte x = 0; x < fromInteger(valueOf(TwoT)); x = x + 1)
begin
syndrome_temp[x] = times_alpha_n(syndrome[x], x + 1);
syndrome_temp[x] = gf_add(syndrome_temp[x], datum);
end
syndrome <= syndrome_temp;
i <= i + 1;
endmethod
 
// ------------------------------------------------
method ActionValue#(Syndrome#(TwoT)) s_out() if (i == n);
$display (" [syndrome %d] s_out", block_number);
// consider the next n
n_q.deq();
// reset state
i <= 0;
syndrome <= replicate(0);
// incr block_numer (just for bookkeeping)
block_number <= block_number + 1;
return syndrome;
endmethod
// ------------------------------------------------
method Action n_in (Byte n_new);
$display (" [syndrome %d] n_in : %d", block_number, n_new);
 
n_q.enq(n_new);
endmethod
endmodule
 
 
 
/reedsolomon/trunk/bluespec-source/mkReedSolomon.bsv
0,0 → 1,371
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
import GetPut::*;
import FIFO::*;
import GFTypes::*;
import GFArith::*;
import SyndromeParallel::*;
import Berlekamp::*;
import ChienSearch::*;
import ErrorMagnitude::*;
import ErrorCorrector::*;
 
// Uncomment line below which defines BUFFER_LENGTH if
// you get a compile error regarding BUFFER_LENGTH
 
`define BUFFER_LENGTH 255
 
// ---------------------------------------------------------
// Reed-Solomon interface
// ---------------------------------------------------------
interface IReedSolomon;
interface Put#(Byte) rs_t_in;
interface Put#(Byte) rs_k_in;
interface Put#(Byte) rs_input;
interface Get#(Byte) rs_output;
interface Get#(Bool) rs_flag;
endinterface
 
// ---------------------------------------------------------
// Reed-Solomon module
// ---------------------------------------------------------
(* synthesize *)
module mkReedSolomon (IReedSolomon);
 
ISyndrome syndrome <- mkSyndromeParallel;
IBerlekamp berl <- mkBerlekamp;
IChienSearch chien_search <- mkChienSearch;
IErrorMagnitude error_magnitude <- mkErrorMagnitude;
IErrorCorrector error_corrector <- mkErrorCorrector;
// FIFOs
FIFO#(Byte) t_in <- mkSizedFIFO(2);
FIFO#(Byte) k_in <- mkSizedFIFO(2);
FIFO#(Byte) stream_in <- mkSizedFIFO(2);
FIFO#(Byte) stream_out <- mkSizedFIFO(2);
FIFO#(Bool) cant_correct_out <- mkSizedFIFO(3);
// FIFOs for input of syndrome module
FIFO#(Byte) ff_n_to_syndrome <- mkSizedFIFO(1);
FIFO#(Byte) ff_r_to_syndrome <- mkSizedFIFO(2);
// FIFOs for input of berlekamp module
FIFO#(Byte) ff_t_to_berl <- mkSizedFIFO(2);
FIFO#(Syndrome#(TwoT)) ff_s_to_berl <- mkSizedFIFO(1);
 
// FIFOs for input of chien searach module
FIFO#(Byte) ff_t_to_chien <- mkSizedFIFO(3);
FIFO#(Byte) ff_k_to_chien <- mkSizedFIFO(3);
FIFO#(Bool) ff_no_error_flag_to_chien <- mkSizedFIFO(1);
FIFO#(Syndrome#(T)) ff_l_to_chien <- mkSizedFIFO(1);
// FIFOs for input of error magnitude module
FIFO#(Byte) ff_k_to_errormag <- mkSizedFIFO(4);
FIFO#(Bool) ff_no_error_flag_to_errormag <- mkSizedFIFO(2);
FIFO#(Maybe#(Byte)) ff_loc_to_errormag <- mkSizedFIFO(2);
FIFO#(Maybe#(Byte)) ff_alpha_inv_to_errormag <- mkSizedFIFO(2);
FIFO#(Syndrome#(T)) ff_l_to_errormag <- mkSizedFIFO(1);
FIFO#(Syndrome#(T)) ff_w_to_errormag <- mkSizedFIFO(2);
// FIFOs for input of error corrector module
FIFO#(Byte) ff_r_to_errorcor <- mkSizedFIFO(`BUFFER_LENGTH);
FIFO#(Byte) ff_e_to_errorcor <- mkSizedFIFO(2);
FIFO#(Byte) ff_k_to_errorcor <- mkSizedFIFO(5);
FIFO#(Bool) ff_no_error_flag_to_errorcor <- mkSizedFIFO(3);
// Regs
Reg#(Bool) info_count_done <- mkReg (True);
Reg#(Bool) parity_count_done <- mkReg (True);
Reg#(Byte) state <- mkReg (0);
Reg#(Bit#(32)) cycle_count <- mkReg (0);
Reg#(Byte) info_count <- mkReg (0);
Reg#(Byte) parity_count <- mkReg (0);
 
// ----------------------------------
rule init (state == 0);
state <= 1;
endrule
// ----------------------------------
rule read_mac (state == 1 && info_count_done == True && parity_count_done == True);
let k = k_in.first();
k_in.deq ();
info_count <= k;
// k = 0, means no info bytes, stupid special case!
if (k == 0)
info_count_done <= True;
else
info_count_done <= False;
ff_k_to_chien.enq(k);
ff_k_to_errormag.enq(k);
ff_k_to_errorcor.enq(k);
 
let t = t_in.first();
t_in.deq();
ff_t_to_berl.enq(t);
ff_t_to_chien.enq(t);
let n = k + 2 * t;
ff_n_to_syndrome.enq(n);
 
parity_count <= 2 * t ;
if (t == 0)
parity_count_done <= True;
else
parity_count_done <= False;
$display (" [reedsol] read_mac z = %d, k = %d, t = %d", 255 - k - 2*t, k, t);
endrule
 
rule read_input (state == 1 && info_count_done == False);
let datum = stream_in.first ();
$display (" [reedsol] read_input [%d] = %d", info_count, datum);
stream_in.deq();
ff_r_to_syndrome.enq(datum);
ff_r_to_errorcor.enq(datum);
if (info_count == 1)
info_count_done <= True;
info_count <= info_count - 1;
endrule
rule read_parity (state == 1 && info_count_done == True && parity_count_done == False);
let datum = stream_in.first ();
$display (" [reedsol] read_parity [%d] = %d", parity_count, datum);
stream_in.deq();
ff_r_to_syndrome.enq (datum);
if (parity_count == 1)
parity_count_done <= True;
parity_count <= parity_count - 1;
endrule
 
// ----------------------------------
// rule for syndrome
rule n_to_syndrome (state == 1);
// $display (" > > [t to syndrome] cycle count: %d", cycle_count);
ff_n_to_syndrome.deq();
let datum = ff_n_to_syndrome.first();
syndrome.n_in(datum);
endrule
 
rule r_to_syndrome (state == 1);
// $display (" > > [r to syndrome] cycle count: %d", cycle_count);
ff_r_to_syndrome.deq();
let datum = ff_r_to_syndrome.first();
syndrome.r_in(datum);
endrule
 
rule s_from_syndrome (state == 1);
// $display (" > > [s from syndrome] cycle count: %d", cycle_count);
let datum <- syndrome.s_out();
ff_s_to_berl.enq(datum);
endrule
 
// ----------------------------------
// rules for berlekamp
rule s_to_berl (state == 1);
// $display (" > > [s to berlekamp] cycle count: %d", cycle_count);
ff_s_to_berl.deq();
let datum = ff_s_to_berl.first();
berl.s_in(datum);
endrule
 
rule t_to_berl (state == 1);
// $display (" > > [t to berlekamp] cycle count: %d", cycle_count);
ff_t_to_berl.deq();
let datum = ff_t_to_berl.first();
berl.t_in(datum);
endrule
 
rule flag_from_berl (state == 1);
// $display (" > > [no error flag from syndrome] cycle count: %d", cycle_count);
let no_error <- berl.no_error_flag_out();
ff_no_error_flag_to_chien.enq(no_error);
ff_no_error_flag_to_errormag.enq(no_error);
ff_no_error_flag_to_errorcor.enq(no_error);
endrule
 
rule l_from_berl (state == 1);
// $display (" > > [l from berlekamp] cycle count: %d", cycle_count);
let datum <- berl.lambda_out();
ff_l_to_chien.enq(datum);
endrule
 
rule w_from_berl(state == 1);
// $display (" > > [w from berlekamp] cycle count: %d", cycle_count);
let datum <- berl.omega_out();
ff_w_to_errormag.enq(datum);
endrule
 
// ----------------------------------
// rules for chien_search
rule t_to_chien (state == 1);
// $display (" > > [t to chien] cycle count: %d", cycle_count);
ff_t_to_chien.deq();
let datum = ff_t_to_chien.first();
chien_search.t_in(datum);
endrule
 
rule k_to_chien (state == 1);
ff_k_to_chien.deq ();
let datum = ff_k_to_chien.first ();
chien_search.k_in (datum);
endrule
 
rule l_to_chien (state == 1);
// $display (" > > [l to chien] cycle count: %d", cycle_count);
ff_l_to_chien.deq();
let datum = ff_l_to_chien.first();
chien_search.lambda_in(datum);
endrule
 
rule no_error_flag_to_chien (state == 1);
// $display (" > > [no_error to chien] cycle count: %d", cycle_count);
ff_no_error_flag_to_chien.deq ();
let no_error = ff_no_error_flag_to_chien.first ();
chien_search.no_error_flag_in (no_error);
endrule
 
rule flag_from_chien (state == 1);
// $display (" > > [flag from chien] cycle count: %d", cycle_count);
let datum <- chien_search.cant_correct_flag_out();
cant_correct_out.enq(datum);
endrule
rule loc_from_chien (state == 1);
// $display (" > > [loc from chien] cycle count: %d", cycle_count);
let datum <- chien_search.loc_out();
ff_loc_to_errormag.enq(datum);
endrule
rule alpha_inv_from_chien (state == 1);
// $display (" > > [alpha inv from chien] cycle count: %d", cycle_count);
let datum <- chien_search.alpha_inv_out();
ff_alpha_inv_to_errormag.enq(datum);
endrule
 
rule l_from_chien (state == 1);
// $display (" > > [l from berlekamp] cycle count: %d", cycle_count);
let datum <- chien_search.lambda_out();
ff_l_to_errormag.enq(datum);
endrule
// ----------------------------------
// rules for error_magnitude
rule k_to_errormag (state == 1);
ff_k_to_errormag.deq();
let datum = ff_k_to_errormag.first();
error_magnitude.k_in(datum);
endrule
 
rule no_error_flag_to_errormag (state == 1);
ff_no_error_flag_to_errormag.deq();
let datum = ff_no_error_flag_to_errormag.first();
error_magnitude.no_error_flag_in(datum);
endrule
rule loc_to_errormag (state == 1);
ff_loc_to_errormag.deq();
let datum = ff_loc_to_errormag.first();
error_magnitude.loc_in(datum);
endrule
rule alpha_inv_to_errormag (state == 1);
ff_alpha_inv_to_errormag.deq();
let datum = ff_alpha_inv_to_errormag.first();
error_magnitude.alpha_inv_in(datum);
endrule
 
rule l_to_errormag (state == 1);
ff_l_to_errormag.deq();
let datum = ff_l_to_errormag.first();
error_magnitude.lambda_in(datum);
endrule
rule w_to_errormag (state == 1);
// $display (" > > [w to chien] cycle count: %d", cycle_count);
ff_w_to_errormag.deq();
let datum = ff_w_to_errormag.first();
error_magnitude.omega_in(datum);
endrule
rule e_from_errormag (state == 1);
// $display (" > > [e from chien] cycle count: %d", cycle_count);
let datum <- error_magnitude.error_out();
ff_e_to_errorcor.enq(datum);
endrule
// ----------------------------------
// rules for error_corrector
rule k_to_error_corrector (state == 1);
// $display (" > > [t to error_corrector] cycle count: %d", cycle_count);
ff_k_to_errorcor.deq ();
let datum = ff_k_to_errorcor.first ();
error_corrector.k_in (datum);
endrule
 
rule no_error_flag_to_error_corrector (state == 1);
// $display (" > > [no_error to error_corrector] cycle count: %d", cycle_count);
ff_no_error_flag_to_errorcor.deq();
let no_error = ff_no_error_flag_to_errorcor.first();
error_corrector.no_error_flag_in(no_error);
endrule
 
rule r_to_error_corrector (state == 1);
// $display (" > > [r to error corrector] cycle count: %d", cycle_count);
ff_r_to_errorcor.deq ();
let datum = ff_r_to_errorcor.first ();
error_corrector.r_in (datum);
endrule
rule e_to_error_corrector (state == 1);
// $display (" > > [e to error corector] cycle count: %d", cycle_count);
ff_e_to_errorcor.deq ();
let error = ff_e_to_errorcor.first ();
error_corrector.e_in (error);
endrule
rule d_from_error_corrector (state == 1);
// $display (" > > [d from error corector] cycle count: %d", cycle_count);
let corrected_datum <- error_corrector.d_out ();
stream_out.enq (corrected_datum);
endrule
// ----------------------------------
rule cycle (state == 1);
$display ("%d -------------------------", cycle_count);
cycle_count <= cycle_count + 1;
endrule
interface Put rs_t_in = fifoToPut(t_in);
interface Put rs_k_in = fifoToPut(k_in);
interface Put rs_input = fifoToPut(stream_in);
interface Get rs_output = fifoToGet(stream_out);
interface Get rs_flag = fifoToGet(cant_correct_out);
endmodule
 
/reedsolomon/trunk/bluespec-source/output.dat
0,0 → 1,2240
255 16
181
230
226
138
239
46
31
30
178
115
105
99
82
54
29
162
113
171
134
96
51
162
106
91
137
76
15
131
155
106
236
43
246
179
106
209
123
171
179
79
32
50
70
175
196
112
27
16
120
226
245
215
25
29
75
6
176
164
150
112
115
56
192
36
56
189
29
44
138
129
8
112
109
213
147
179
246
55
26
160
201
216
139
19
108
166
110
64
48
93
174
78
 
2
7
12
51
155
35
26
19
50
219
184
221
91
153
86
109
64
20
182
108
228
163
43
117
17
144
225
93
172
71
243
206
107
231
25
135
240
61
89
83
128
31
134
237
88
66
181
211
47
19
64
111
146
154
147
178
226
153
104
221
219
12
180
226
245
219
45
157
187
58
203
145
197
68
55
131
18
162
147
191
128
164
218
222
182
248
73
5
189
92
40
247
21
216
181
88
31
241
208
41
115
134
89
66
49
148
239
82
33
237
227
161
236
225
148
177
59
236
220
196
71
79
66
188
184
194
134
244
126
73
255 16
170
92
52
127
242
71
39
148
64
138
22
125
253
240
126
227
47
221
211
18
158
227
220
189
17
193
40
25
15
155
187
43
104
235
87
93
7
156
125
193
139
37
253
26
192
160
16
28
62
238
53
224
209
27
149
247
177
139
93
227
51
206
211
10
227
185
223
68
16
88
194
113
100
92
9
163
98
32
230
92
29
26
75
217
104
9
154
205
88
141
16
40
233
25
42
159
169
135
128
158
242
102
103
191
248
232
188
6
3
203
17
67
177
66
62
153
175
13
189
48
162
245
252
74
111
162
30
11
147
26
54
51
108
126
3
242
229
239
243
191
26
206
4
23
145
49
219
126
105
198
50
87
134
90
44
100
15
3
211
96
173
182
47
120
152
19
254
37
212
36
186
3
60
209
59
19
199
20
76
17
64
215
43
34
75
40
143
174
85
29
48
53
30
27
120
114
61
217
106
209
231
232
198
41
10
39
198
181
211
115
229
29
140
2
146
155
210
114
125
31
253
20
187
255 16
32
176
232
58
198
9
52
97
114
119
58
193
249
194
58
185
117
148
241
131
111
191
58
247
120
155
241
11
127
189
138
229
233
222
6
100
150
187
39
175
125
119
135
64
76
165
198
240
36
50
72
118
71
158
6
108
27
52
128
153
210
170
222
133
72
73
61
229
62
174
39
61
42
225
120
90
128
147
168
173
234
169
111
217
130
209
234
128
96
213
186
77
97
148
72
97
11
141
190
1
132
69
195
206
96
227
177
210
168
254
61
16
38
157
237
1
112
21
197
19
115
37
4
 
137
185
162
10
8
120
60
180
228
222
29
141
59
177
149
151
216
159
33
36
44
216
59
92
161
160
15
114
154
73
92
127
177
42
204
82
146
92
151
87
163
106
247
162
216
244
117
179
114
72
232
206
54
153
77
46
5
196
22
27
151
50
177
94
150
111
186
59
184
45
95
 
144
2
44
36
130
45
202
162
17
78
129
8
147
136
24
232
44
226
105
57
154
65
163
90
182
140
219
255 16
101
218
156
226
133
203
37
159
225
125
185
202
51
109
231
107
186
149
189
64
82
165
208
13
109
59
31
40
199
122
27
130
84
208
188
229
232
167
228
22
74
76
226
199
178
81
173
121
67
23
110
68
56
149
237
69
114
164
13
69
37
73
196
110
230
21
 
210
92
152
50
129
153
145
26
56
14
149
11
253
222
215
86
242
35
73
55
45
126
194
127
182
97
175
109
20
183
103
159
218
253
160
103
97
131
131
44
15
182
50
167
235
180
13
186
245
202
115
172
198
97
207
72
76
246
6
116
220
104
254
114
156
29
226
52
115
204
249
103
202
124
154
48
190
65
70
72
3
18
219
125
20
215
65
215
26
157
117
105
202
224
143
104
169
22
57
11
2
125
204
153
188
88
233
117
62
51
108
133
252
4
59
59
188
163
98
176
209
147
216
98
55
121
46
157
20
187
62
103
191
116
174
71
26
181
9
184
54
103
73
193
70
151
215
12
208
206
214
110
92
95
52
153
255 16
166
20
209
149
20
110
176
43
166
250
106
103
208
214
150
153
57
160
198
170
127
63
150
251
230
116
233
45
24
241
226
17
 
99
228
232
198
180
192
62
42
146
208
54
157
244
209
141
32
135
20
131
88
34
17
184
92
247
74
7
241
127
44
23
155
47
40
136
138
45
108
242
243
219
100
15
211
74
121
156
47
241
114
158
196
25
110
85
6
201
217
218
227
251
238
19
164
249
27
150
56
144
142
227
7
26
149
55
26
135
42
143
44
88
48
111
18
163
122
43
229
220
234
207
87
243
246
13
192
138
8
83
136
116
78
207
254
13
12
137
91
208
95
187
69
139
244
230
189
156
63
21
133
246
216
73
51
107
5
108
2
147
5
183
116
64
194
117
177
59
41
158
138
211
198
94
204
87
167
167
23
72
59
59
195
108
67
197
105
113
103
73
30
195
243
254
141
135
75
19
176
85
215
44
6
110
181
37
64
95
108
218
131
206
247
253
2
209
93
32
83
162
84
255 16
249
32
204
59
64
223
238
127
132
79
142
50
201
41
90
246
237
133
165
184
200
202
152
154
28
210
77
216
72
50
2
190
222
235
75
191
91
159
240
82
132
101
214
209
59
212
81
52
188
217
32
46
174
196
76
67
138
27
213
136
82
22
115
31
144
170
206
8
26
139
123
177
42
2
128
6
24
118
20
141
43
90
225
107
58
49
108
1
199
191
21
51
132
199
80
135
144
66
140
103
97
120
49
35
233
9
240
137
75
185
171
190
31
175
253
57
104
172
234
147
58
77
226
251
55
13
250
40
223
19
54
61
142
39
50
95
188
54
221
139
153
250
192
229
71
81
77
211
113
157
176
62
21
212
1
14
44
231
241
162
131
15
11
47
105
250
128
49
155
226
202
179
179
111
151
114
222
175
35
51
135
218
61
7
167
25
28
137
99
226
150
84
164
15
173
56
94
157
101
231
47
90
28
64
143
230
78
171
39
71
245
128
50
35
233
30
180
57
241
14
61
135
166
255 16
71
174
148
141
148
212
176
192
240
120
23
124
211
118
37
236
61
40
23
157
122
51
170
143
156
149
205
118
211
51
9
184
25
191
220
211
226
55
168
116
164
159
87
229
57
252
212
158
172
227
242
234
149
20
192
38
193
153
109
27
26
72
218
68
219
164
43
110
145
8
29
189
102
90
17
153
79
240
171
193
78
221
41
110
82
39
184
166
126
36
63
213
108
54
24
109
19
35
81
210
160
193
172
203
10
31
237
141
162
205
151
222
138
1
180
171
168
148
102
168
183
9
188
253
34
244
27
63
129
142
38
211
183
141
221
124
124
31
244
194
66
149
42
222
88
31
68
 
220
93
234
184
229
198
225
226
114
140
25
172
214
151
245
58
17
189
134
184
220
95
152
99
61
10
153
87
66
230
20
36
119
35
213
2
84
85
201
196
181
128
182
155
134
55
179
87
224
39
32
120
33
141
200
228
199
178
67
30
111
239
77
116
206
128
56
142
159
72
14
26
248
127
230
255 16
68
9
122
159
203
162
112
108
202
222
82
159
132
3
205
43
50
115
166
105
105
124
124
221
166
39
38
133
140
245
250
163
61
214
47
94
215
144
26
42
90
79
209
88
207
90
132
200
9
42
235
139
212
84
183
33
153
47
137
232
183
35
116
222
254
158
67
173
53
202
88
1
126
118
211
7
81
89
219
125
84
151
210
179
186
136
150
176
118
102
115
216
36
213
154
81
104
120
84
52
75
224
44
119
37
121
43
211
5
68
169
160
219
74
29
9
17
47
61
157
66
157
61
209
109
34
251
51
45
114
8
210
187
177
76
81
116
229
41
100
103
95
131
210
56
236
203
115
236
158
95
111
48
26
212
57
244
137
43
89
182
85
134
106
61
101
39
16
126
201
223
147
38
150
7
196
254
44
19
125
109
68
153
246
37
75
14
155
210
213
209
75
23
32
66
45
230
93
47
233
162
73
140
97
150
217
176
129
189
205
226
118
31
77
232
137
120
55
200
134
189
176
9
255 16
196
194
167
231
166
46
72
207
38
10
116
82
156
251
91
69
70
138
173
76
172
12
185
204
127
95
36
167
120
67
165
219
27
120
158
214
7
62
90
211
109
119
245
86
180
207
150
248
221
161
146
222
139
90
168
215
229
224
2
155
39
44
60
68
113
96
123
51
207
226
220
23
193
38
190
187
241
244
102
254
21
56
54
178
115
198
213
73
184
213
95
226
186
218
200
62
144
151
85
184
32
182
87
6
52
200
84
242
223
45
199
97
195
110
220
42
14
 
233
213
27
131
26
124
74
48
231
214
119
158
96
26
129
142
176
65
232
39
42
125
105
89
132
152
95
220
64
56
228
101
187
158
56
232
147
115
184
73
118
92
28
209
104
64
164
137
23
107
188
207
248
207
248
166
88
39
247
217
124
70
45
209
10
196
48
73
251
91
45
164
243
218
44
222
41
57
203
70
113
236
214
81
118
208
173
125
170
177
172
170
59
104
160
191
199
212
28
87
103
81
119
21
176
255 16
202
56
170
77
202
231
177
100
132
91
200
178
169
118
185
251
148
218
174
17
62
230
115
8
42
153
6
63
90
195
43
125
108
194
154
102
99
86
154
208
177
82
248
172
224
222
77
131
155
199
156
53
187
217
2
233
62
65
20
220
87
104
226
6
95
68
202
145
163
72
215
4
113
25
95
93
66
133
229
102
11
194
51
209
155
192
213
97
232
171
249
81
8
158
59
205
159
130
184
158
213
189
164
20
214
217
118
219
121
34
50
57
39
113
250
57
214
42
103
151
162
90
21
58
253
184
20
 
171
249
249
193
230
202
156
250
95
83
168
64
250
191
61
236
154
208
209
63
134
12
129
103
92
92
38
252
12
25
6
233
19
46
36
235
106
72
81
30
88
231
3
13
37
107
26
91
74
197
188
30
175
37
65
94
80
12
245
34
6
215
196
38
195
219
153
76
239
104
26
74
194
151
241
201
33
84
157
43
22
151
220
80
212
52
103
45
6
30
93
222
20
231
140
/reedsolomon/trunk/bluespec-source/GFTypes.bsv
0,0 → 1,60
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
//*************************************************************
// Type definitions for use in the Reed-Solomon modules
//-------------------------------------------------------------
 
import Vector::*;
 
typedef Bit#(8) Byte;
typedef Byte Polynomial;
typedef Vector#(n,Byte) Syndrome#(numeric type n);
 
typedef enum
{ NO_ERROR,
CORRECTABLE,
INCORRECTABLE
} ErrInfo deriving (Bits, Eq);
 
`include "RSParameters.bsv"
 
typedef TMul#(T,2) TwoT; // 2 * T
typedef TAdd#(T,2) TPlusTwo; // T + 2
typedef TDiv#(T,2) HalfT; // T/2
 
// -----------------------------------------------------------
// The primitive polynomial defines the Galois field in which
// Reed-Solomon decoder operates, and all the following
// arithmetic operations are defined under. Changing this
// value cause the whole Reed-Solomon decoder to operate
// under the new primitive polynomial.
// primitive_polynomial[i] = Coefficient of x**i for i = 0:7
 
// -----------------------------------------------------------
Byte n_param = 8'd255;
Byte t_param = fromInteger(valueOf(T));
/reedsolomon/trunk/bluespec-source/Makefile
0,0 → 1,133
# //----------------------------------------------------------------------//
# // The MIT License
# //
# // Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
# // Contact: abhiag@gmail.com
# //
# // Permission is hereby granted, free of charge, to any person
# // obtaining a copy of this software and associated documentation
# // files (the "Software"), to deal in the Software without
# // restriction, including without limitation the rights to use,
# // copy, modify, merge, publish, distribute, sublicense, and/or sell
# // copies of the Software, and to permit persons to whom the
# // Software is furnished to do so, subject to the following conditions:
# //
# // The above copyright notice and this permission notice shall be
# // included in all copies or substantial portions of the Software.
# //
# // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
# // OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
# // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
# // HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
# // WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
# // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# // OTHER DEALINGS IN THE SOFTWARE.
# //----------------------------------------------------------------------//
 
#=======================================================================
# Makefile for Reed Solomon decoder
#-----------------------------------------------------------------------
 
default : mkTestBench
 
#--------------------------------------------------------------------
# Sources
#--------------------------------------------------------------------
 
 
 
# Bluespec sources
 
srcdir = .
sim_srcdir = $(srcdir)/simulate
 
toplevel_module = mkTestBench
 
 
bsvsrcs = \
$(srcdir)/RSParameters.bsv \
$(srcdir)/GFTypes.bsv \
$(srcdir)/GFArith.bsv \
$(srcdir)/MFIFO.bsv \
$(srcdir)/SyndromeParallel.bsv \
$(srcdir)/Berlekamp.bsv \
$(srcdir)/ChienSearch.bsv \
$(srcdir)/ErrorMagnitude.bsv \
$(srcdir)/ErrorCorrector.bsv \
$(srcdir)/mkReedSolomon.bsv \
$(srcdir)/file_interface.cpp \
$(srcdir)/mkTestBench.bsv \
$(srcdir)/funcunit.bsv
 
 
sim_bsvsrcs = \
 
 
cppdir = $(srcdir)
 
cppsrcs = $(cppdir)/preproc.cpp
 
#--------------------------------------------------------------------
# Build rules
#--------------------------------------------------------------------
 
# compile & run the preproc to generate the GF inverse logic.
 
preproc.o : $(notdir $(cppsrcs))
$(CXX) -c -o preproc.o preproc.cpp
 
preproc : preproc.o
$(CXX) -o preproc preproc.o
 
 
GFInv.bsv : preproc $(notdir $(bsvsrcs))
./preproc RSParameters.bsv GFInv.bsv
 
BSC_COMP = bsc
 
BSC_FLAGS = -u -aggressive-conditions -keep-fires -no-show-method-conf \
-steps-warn-interval 200000 -steps-max-intervals 10 -show-schedule +RTS -K4000M -RTS
 
BSC_VOPTS = -elab -verilog
 
BSC_BAOPTS = -sim
 
# run gcc
 
file_interface.o : file_interface.cpp
gcc -c -DDATA_FILE_PATH=\"./input.dat\" \
-DOUT_DATA_FILE_PATH=\"./output.dat\" \
file_interface.cpp
 
# Run the bluespec compiler
 
 
mkTestBench.ba : GFInv.bsv $(notdir $(bsvsrcs) $(sim_bsvsrcs))
$(BSC_COMP) $(BSC_FLAGS) $(BSC_VOPTS) mkReedSolomon.bsv
$(BSC_COMP) $(BSC_FLAGS) $(BSC_BAOPTS) -g $(toplevel_module) $(toplevel_module).bsv
 
mkTestBench : mkTestBench.ba file_interface.o
$(BSC_COMP) $(BSC_BAOPTS) -e $(toplevel_module) *.ba file_interface.o
 
 
# Create a schedule file
 
schedule_rpt = schedule.rpt
$(schedule_rpt) : $(notdir $(bsvsrcs) $(bsvclibsrcs))
rm -rf *.v
$(BSC_COMP) $(BSC_FLAGS) $(BSC_BAOPTS) -show-schedule -show-rule-rel \* \* -g $(toplevel_module) $(toplevel_module).bsv
 
 
#--------------------------------------------------------------------
# Clean up
#--------------------------------------------------------------------
 
junk += $(schedule_rpt) *.use *.bi *.bo *.v bsc.log \
diff.out *.sched directc.*
 
.PHONY: clean
 
clean :
rm -rf $(junk) *~ \#* *.h *.o *.cxx *.ba a.out preproc
 
/reedsolomon/trunk/bluespec-source/GFArith.bsv
0,0 → 1,375
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
//**********************************************************************
// Galois field arithmetic
//----------------------------------------------------------------------
// $Id: GFArith.bsv
//
import GFTypes::*;
import Vector::*;
 
`include "GFInv.bsv"
 
// -----------------------------------------------------------
//(* noinline *)
function Byte gf_mult(Byte left, Byte right);
 
Bit#(15) first = 15'b0;
Bit#(15) result = 15'b0;
// this function bring back higher degree values back to the field
function Bit#(15) getNewResult(Integer shift, Bit#(15) res);
Bit#(15) shiftPoly = zeroExtend(primitive_poly) << shift;
Bit#(15) newRes = res ^ ((res[8+shift] == 1'b1) ? shiftPoly : 0);
return newRes;
endfunction
for (Integer i = 0; i < 8; i = i + 1)
for (Integer j = 0; j < 8 ; j = j + 1)
begin
if (first[i+j] == 0) // initialize result[i+j]
result[i+j] = (left[i] & right[j]);
else // accumulate
result[i+j] = result[i+j] ^ (left[i] & right[j]);
first[i+j] = 1; // only initialize each signal once
end
Vector#(7,Integer) shftAmntV = genVector;
Bit#(15) finalResult = foldr(getNewResult,result,shftAmntV);
return finalResult[7:0];
 
endfunction
 
(* noinline *)
function Byte gf_mult_inst(Byte x, Byte y);
return gf_mult(x,y);
endfunction
 
// -----------------------------------------------------------
function Byte gf_add(Byte left, Byte right);
return (left ^ right);
endfunction
 
(* noinline *)
function Byte gf_add_inst(Byte x, Byte y);
return gf_add(x,y);
endfunction
 
 
// -----------------------------------------------------------
//(* noinline *)
function Byte alpha_n(Byte n);
return times_alpha_n(1,n);
endfunction
 
// -----------------------------------------------------------
//(* noinline *)
function Byte times_alpha_n(Byte a, Byte n);
// Byte multVal = 1 << n;
// return gf_mult(primitive_poly,a,multVal);
 
Byte b=a;
for (Byte i = 0; i < n; i = i + 1)
b=times_alpha(b);
return b;
endfunction
 
// -----------------------------------------------------------
//(* noinline *)
function Byte times_alpha(Byte a);
// return gf_mult(primitive_poly, a, 2);
 
return (a<<1)^({a[7],a[7],a[7],a[7],a[7],a[7],a[7],a[7]} & primitive_poly);
endfunction
 
// -----------------------------------------------------------
/*
function Byte gf_inv (Byte a);
 
case (a) matches
0 : return 2;
1 : return 1;
2 : return 142;
3 : return 244;
4 : return 71;
5 : return 167;
6 : return 122;
7 : return 186;
8 : return 173;
9 : return 157;
10 : return 221;
11 : return 152;
12 : return 61;
13 : return 170;
14 : return 93;
15 : return 150;
16 : return 216;
17 : return 114;
18 : return 192;
19 : return 88;
20 : return 224;
21 : return 62;
22 : return 76;
23 : return 102;
24 : return 144;
25 : return 222;
26 : return 85;
27 : return 128;
28 : return 160;
29 : return 131;
30 : return 75;
31 : return 42;
32 : return 108;
33 : return 237;
34 : return 57;
35 : return 81;
36 : return 96;
37 : return 86;
38 : return 44;
39 : return 138;
40 : return 112;
41 : return 208;
42 : return 31;
43 : return 74;
44 : return 38;
45 : return 139;
46 : return 51;
47 : return 110;
48 : return 72;
49 : return 137;
50 : return 111;
51 : return 46;
52 : return 164;
53 : return 195;
54 : return 64;
55 : return 94;
56 : return 80;
57 : return 34;
58 : return 207;
59 : return 169;
60 : return 171;
61 : return 12;
62 : return 21;
63 : return 225;
64 : return 54;
65 : return 95;
66 : return 248;
67 : return 213;
68 : return 146;
69 : return 78;
70 : return 166;
71 : return 4;
72 : return 48;
73 : return 136;
74 : return 43;
75 : return 30;
76 : return 22;
77 : return 103;
78 : return 69;
79 : return 147;
80 : return 56;
81 : return 35;
82 : return 104;
83 : return 140;
84 : return 129;
85 : return 26;
86 : return 37;
87 : return 97;
88 : return 19;
89 : return 193;
90 : return 203;
91 : return 99;
92 : return 151;
93 : return 14;
94 : return 55;
95 : return 65;
96 : return 36;
97 : return 87;
98 : return 202;
99 : return 91;
100 : return 185;
101 : return 196;
102 : return 23;
103 : return 77;
104 : return 82;
105 : return 141;
106 : return 239;
107 : return 179;
108 : return 32;
109 : return 236;
110 : return 47;
111 : return 50;
112 : return 40;
113 : return 209;
114 : return 17;
115 : return 217;
116 : return 233;
117 : return 251;
118 : return 218;
119 : return 121;
120 : return 219;
121 : return 119;
122 : return 6;
123 : return 187;
124 : return 132;
125 : return 205;
126 : return 254;
127 : return 252;
128 : return 27;
129 : return 84;
130 : return 161;
131 : return 29;
132 : return 124;
133 : return 204;
134 : return 228;
135 : return 176;
136 : return 73;
137 : return 49;
138 : return 39;
139 : return 45;
140 : return 83;
141 : return 105;
142 : return 2;
143 : return 245;
144 : return 24;
145 : return 223;
146 : return 68;
147 : return 79;
148 : return 155;
149 : return 188;
150 : return 15;
151 : return 92;
152 : return 11;
153 : return 220;
154 : return 189;
155 : return 148;
156 : return 172;
157 : return 9;
158 : return 199;
159 : return 162;
160 : return 28;
161 : return 130;
162 : return 159;
163 : return 198;
164 : return 52;
165 : return 194;
166 : return 70;
167 : return 5;
168 : return 206;
169 : return 59;
170 : return 13;
171 : return 60;
172 : return 156;
173 : return 8;
174 : return 190;
175 : return 183;
176 : return 135;
177 : return 229;
178 : return 238;
179 : return 107;
180 : return 235;
181 : return 242;
182 : return 191;
183 : return 175;
184 : return 197;
185 : return 100;
186 : return 7;
187 : return 123;
188 : return 149;
189 : return 154;
190 : return 174;
191 : return 182;
192 : return 18;
193 : return 89;
194 : return 165;
195 : return 53;
196 : return 101;
197 : return 184;
198 : return 163;
199 : return 158;
200 : return 210;
201 : return 247;
202 : return 98;
203 : return 90;
204 : return 133;
205 : return 125;
206 : return 168;
207 : return 58;
208 : return 41;
209 : return 113;
210 : return 200;
211 : return 246;
212 : return 249;
213 : return 67;
214 : return 215;
215 : return 214;
216 : return 16;
217 : return 115;
218 : return 118;
219 : return 120;
220 : return 153;
221 : return 10;
222 : return 25;
223 : return 145;
224 : return 20;
225 : return 63;
226 : return 230;
227 : return 240;
228 : return 134;
229 : return 177;
230 : return 226;
231 : return 241;
232 : return 250;
233 : return 116;
234 : return 243;
235 : return 180;
236 : return 109;
237 : return 33;
238 : return 178;
239 : return 106;
240 : return 227;
241 : return 231;
242 : return 181;
243 : return 234;
244 : return 3;
245 : return 143;
246 : return 211;
247 : return 201;
248 : return 66;
249 : return 212;
250 : return 232;
251 : return 117;
252 : return 127;
253 : return 255;
254 : return 126;
255 : return 253;
endcase
endfunction
*/
/reedsolomon/trunk/cpp-source/syndrome.cpp
0,0 → 1,55
//----------------------------------------------------------------------//
// The MIT License
//
// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng
// Contact: abhiag@gmail.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//----------------------------------------------------------------------//
 
#include "global_rs.h"
#include "gf_arith.h"
#include "syndrome.h"
 
 
// Parameters k and t need to be dynamically used for each packet
// However, this version uses static values for simplicity
 
// Directive: Synthesize independently
void syndrome (unsigned char k, unsigned char t, unsigned char r[nn], unsigned char s[2*tt])
{
unsigned char r_temp;
 
// Directive: Unroll loop maximally
Syn_Init: for (int j=0; j<2*tt; j++)
s[j]=0;
 
Syn_Outer: for (int i = 0; i < nn; ++ i)
{
r_temp = r[i];
// Directive: Unroll loop maximally
Syn_Inner: for (int j = 0; j < 2*tt; ++ j)
{
s[j] = gfmult_hw (s [j], alpha(j+1)) ^ r_temp;
}
}
}
reedsolomon/trunk/cpp-source/syndrome.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/berlekamp.cpp =================================================================== --- reedsolomon/trunk/cpp-source/berlekamp.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/berlekamp.cpp (revision 2) @@ -0,0 +1,178 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" +#include "gf_arith.h" +#include "berlekamp.h" + +// Directive: Synthesize independently +void gfmult_array_array_hw (unsigned char res_vec[tt+2], unsigned char in_vec0[tt+2], unsigned char in_vec1[tt+2]) +{ +// Directive: Unroll loop maximally + for (int i = 0; i < tt+2; ++i) + res_vec[i] = gfmult_hw(in_vec0[i],in_vec1[i]); +} + +// Directive: Synthesize independently +void gfmult_scalar_array_hw1 (unsigned char res_vec[tt+2], unsigned char val, unsigned char in_vec[tt+2]) +{ +// Directive: Unroll loop maximally + for (int i = 0; i < tt+2; ++i) + res_vec[i] = gfmult_hw(val,in_vec[i]); +} + +// Directive: Synthesize independently +void gfmult_scalar_array_hw2 (unsigned char res_vec[tt+2], unsigned char val, unsigned char in_vec[tt+2]) +{ +// Directive: Unroll loop maximally + for (int i = 0; i < tt+2; ++i) + res_vec[i] = gfmult_hw(val,in_vec[i]); +} + +// Directive: Synthesize independently +void gfadd_array_array_hw1 (unsigned char in_vec0[tt+2], unsigned char in_vec1[tt+2]) +{ +// Directive: Unroll loop maximally + for (int i = 0; i < tt+2; ++i) + in_vec0[i] = gfadd_hw(in_vec0[i], in_vec1[i]); +} + +// Directive: Synthesize independently +void gfadd_array_array_hw2 (unsigned char in_vec0[tt+2], unsigned char in_vec1[tt+2]) +{ +// Directive: Unroll loop maximally + for (int i = 0; i < tt+2; ++i) + in_vec0[i] = gfadd_hw(in_vec0[i], in_vec1[i]); +} + + +// Directive: Synthesize independently +unsigned char gfsum_array_hw (unsigned char in_vec[tt+2]) +{ + unsigned char res = 0; + + // Directive: Unroll loop maximally + for (int i = 0; i < tt+2; ++i) + res = gfadd_hw(res, in_vec[i]); + + return res; +} + +#pragma hls_design +void berlekamp (unsigned char t, unsigned char s[2*tt], unsigned char c_out[tt], unsigned char w_out[tt]) +{ + unsigned char l = 0; + unsigned char p[tt+2]; + unsigned char a[tt+2]; + unsigned char t1[tt+2]; + unsigned char t2[tt+2]; + unsigned char syn_shift_reg[tt+2]; + unsigned char temp[tt+2]; + unsigned char c[tt+2]; + unsigned char w[tt+2]; + + c[0] = 1; + p[0] = 1; + w[0] = 0; + a[0] = 1; + syn_shift_reg[0] = 0; + temp[0] = 0; + + // Directive: Unroll loop maximally + BerlInit: for (int i = 1; i < tt+2; i++) + { + c [i] = 0; + w [i] = 0; + p [i] = 0; + a [i] = 0; + t1[i] = 0; + t2[i] = 0; + syn_shift_reg[i] = 0; + temp[i] = 0; + } + + unsigned char dstar = 1; + unsigned char d = 0; + unsigned char ddstar = 1; + BerlOuter: + for (int i = 0; i < 2*tt; i++ ) + { + // Directive: Unroll loop maximally + BerlShift: for (int k = tt+1; k > 0; --k) + { + syn_shift_reg[k] = syn_shift_reg[k-1]; + p[k] = p[k-1]; + a[k] = a[k-1]; + } + syn_shift_reg[0] = s[i]; + p[0] = 0; + a[0] = 0; + + gfmult_array_array_hw(temp, c, syn_shift_reg); + d = gfsum_array_hw(temp); + + if (d != 0) + { + ddstar = gfmult_hw(d, dstar); + // Directive: Unroll loop maximally + BerlSimple1: for (int k = 0; k < tt+2; ++k) + { + t1 [k] = p [k]; + t2 [k] = a [k]; + } + + if (i + 1 > 2*l) + { + l = i - l + 1; + + // Directive: Unroll loop maximally + BerlSimple2: for (int k = 0; k < tt+2; ++k) + { + p [k] = c [k]; + a [k] = w [k]; + } + dstar = gfinv_lut ( d ); + } + + gfmult_scalar_array_hw1(temp, ddstar, t1); + gfadd_array_array_hw1(c,temp); + gfmult_scalar_array_hw2(temp, ddstar, t2); + gfadd_array_array_hw2(w,temp); + + } + } + + // Directive: Unroll loop maximally + BerlCopy: for (int k = 0; k < tt; ++k) + { + c_out[k] = c[k+1]; + w_out[k] = w[k+1]; + } +} + + +
reedsolomon/trunk/cpp-source/berlekamp.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/syndrome.h =================================================================== --- reedsolomon/trunk/cpp-source/syndrome.h (nonexistent) +++ reedsolomon/trunk/cpp-source/syndrome.h (revision 2) @@ -0,0 +1,30 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" + +void syndrome (unsigned char k, unsigned char t, unsigned char r[nn], unsigned char s[2*tt]);
reedsolomon/trunk/cpp-source/syndrome.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/berlekamp.h =================================================================== --- reedsolomon/trunk/cpp-source/berlekamp.h (nonexistent) +++ reedsolomon/trunk/cpp-source/berlekamp.h (revision 2) @@ -0,0 +1,30 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" + +void berlekamp (unsigned char t, unsigned char s[2*tt], unsigned char c_out[tt], unsigned char w_out[tt]);
reedsolomon/trunk/cpp-source/berlekamp.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/global_rs.h =================================================================== --- reedsolomon/trunk/cpp-source/global_rs.h (nonexistent) +++ reedsolomon/trunk/cpp-source/global_rs.h (revision 2) @@ -0,0 +1,34 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +// Reed Solomon Decoder Static Constants used throughout + +#define mm 8 +#define nn 255 +#define tt 16 +#define kk 223 +
reedsolomon/trunk/cpp-source/global_rs.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/error_correct.cpp =================================================================== --- reedsolomon/trunk/cpp-source/error_correct.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/error_correct.cpp (revision 2) @@ -0,0 +1,38 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" +#include "gf_arith.h" +#include "error_correct.h" + +// Directive: Synthesize independently +void error_correct( unsigned char k, unsigned char in_data[kk], unsigned char err[kk], + unsigned char out_data[kk]) +{ + for (int i = 0; i < kk; i++) + out_data[i] = gfadd_hw(in_data[i],err[i]); +}
reedsolomon/trunk/cpp-source/error_correct.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/chien_search.cpp =================================================================== --- reedsolomon/trunk/cpp-source/chien_search.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/chien_search.cpp (revision 2) @@ -0,0 +1,77 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" +#include "gf_arith.h" +#include "chien_search.h" + +// Directive: Synthesize independently +void chien_search( unsigned char k, unsigned char t, unsigned char lambda[tt], + unsigned char *err_no, unsigned char err_loc[tt], unsigned char alpha_inv[tt]) +{ + unsigned char accum = 0; + unsigned char err_cnt = 0; + unsigned char alphainv = 1; + unsigned char lambda_a[tt]; + unsigned char err_loc_temp[tt]; + unsigned char alpha_inv_temp[tt]; + + // Directive: Unroll loop maximally + Chien_AssignInArray: for (int i = 0; i < tt; i++) + lambda_a[i] = lambda[i]; + + for (int i = nn-1; i >= 0; i--) + { + // Directive: Unroll loop maximally + Chien_Inner1: for (int j = 0; j < tt; j++) + lambda_a[j] = gfmult_hw(lambda_a[j], alpha(j+1)); + + accum = 1; + + // Directive: Unroll loop maximally + Chien_Inner2: for (int j = 0; j < tt; j++) + accum = gfadd_hw(accum, lambda_a[j]); + + alphainv = gfmult_hw(alphainv, 2); + + if ((i >= 2*tt) && (i < kk+2*tt) && (accum == 0)) + { + err_loc_temp[err_cnt] = i-2*tt; + alpha_inv_temp[err_cnt] = alphainv; + err_cnt++ ; + } + } + + // Directive: Unroll loop maximally + Chien_AssignOutArray: for (int i = 0; i < tt; i++) + { + err_loc[i] = err_loc_temp[i]; + alpha_inv[i] = alpha_inv_temp[i]; + } + + *err_no = err_cnt; +}
reedsolomon/trunk/cpp-source/chien_search.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/README =================================================================== --- reedsolomon/trunk/cpp-source/README (nonexistent) +++ reedsolomon/trunk/cpp-source/README (revision 2) @@ -0,0 +1,37 @@ +Reed-Solomon decoder design for C-based synthesis + +Top level decoder module: rs_decode.cpp +Simple Testbench: test_rs_decode.cpp + +Presently dynamic values of k and t are not used in the decoding process. +Instead the static constants in global_rs.h are used for simplicity. + +Executing make compiles the decoder and the testbench and creates an executable. +Correct execution is indicated by the decoded output being a descending count +from 223 to 1, repeated 3 times. + +For synthesis, import into a C based design tool, set appropriate HW parameters +and synthesize for a particular platform. + +For our case study of generating hardware from this code, the following +transformations and directives were used for improving performance: + +- Break up complex functions into smaller & simpler computational + segments/loops to allow independent optimizations, for example see + berlekamp.cpp, each loop labelled for further directives. + +- Modify loops dependent on dynamic bounds to use static bounds and + mask output to give correct result. + +- Unroll 'For' loops with fixed static bounds maximally, marked in + code as comments corresponding to each loop to be unrolled. Loops + unrolled in berlekamp.cpp, chien_search.cpp, gf_arith.cpp, + syndrome.cpp. + +- Synthesize hardware units for individual functions rather than the + entire logic as a single unit, marked in code as comments for + independent synthesis. + +- Use appropriate streaming buffers for communication between + functional units. Buffers should allow fine-grained pipeline + parallelism across a single data block where possible. Index: reedsolomon/trunk/cpp-source/error_mag.cpp =================================================================== --- reedsolomon/trunk/cpp-source/error_mag.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/error_mag.cpp (revision 2) @@ -0,0 +1,88 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" +#include "gf_arith.h" +#include "error_mag.h" + +// Directive: Synthesize independently +unsigned char poly_eval_inst1 (unsigned char poly[tt], unsigned char alpha_inv) +{ + return poly_eval(poly, alpha_inv); +} + +// Directive: Synthesize independently +unsigned char poly_eval_inst2 (unsigned char poly[tt], unsigned char alpha_inv) +{ + return poly_eval(poly, alpha_inv); +} + +// Directive: Synthesize independently +unsigned char gfdiv_lut_inst (unsigned char dividend, unsigned char divisor) +{ + return gfdiv_lut(dividend, divisor); +} + +// Directive: Synthesize independently +void compute_deriv_inst (unsigned char lambda[tt], unsigned char lambda_deriv[tt]) +{ + compute_deriv(lambda, lambda_deriv); +} + + +// Directive: Synthesize independently +void error_mag(unsigned char k, unsigned char lambda[tt], unsigned char omega[tt], unsigned char err_no, unsigned char err_loc[tt], unsigned char alpha_inv[tt], + unsigned char err[kk]) +{ + int loc_idx = 0; + unsigned char lambda_val = 0; + unsigned char omega_val = 0; + unsigned char lambda_deriv[tt]; + unsigned char err_temp[tt]; + + compute_deriv(lambda, lambda_deriv); + for (int i = 0; i < tt; i++) + { + lambda_val = poly_eval_inst1(lambda_deriv, alpha_inv[i]); + omega_val = poly_eval_inst2(omega, alpha_inv[i]); + err_temp[i] = gfdiv_lut_inst(omega_val, lambda_val); + } + + for (int i = 0; i < kk; i++) + { + if ((err_loc[loc_idx] == kk-1-i) && (loc_idx < err_no)) + { + err[i] = err_temp[loc_idx]; + loc_idx++; + } + else + { + err[i] = 0; + } + } +} +
reedsolomon/trunk/cpp-source/error_mag.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/error_correct.h =================================================================== --- reedsolomon/trunk/cpp-source/error_correct.h (nonexistent) +++ reedsolomon/trunk/cpp-source/error_correct.h (revision 2) @@ -0,0 +1,31 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" + +void error_correct( unsigned char k, unsigned char in_data[kk], unsigned char err[kk], + unsigned char out_data[kk]);
reedsolomon/trunk/cpp-source/error_correct.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/chien_search.h =================================================================== --- reedsolomon/trunk/cpp-source/chien_search.h (nonexistent) +++ reedsolomon/trunk/cpp-source/chien_search.h (revision 2) @@ -0,0 +1,32 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" +void chien_search( unsigned char k, unsigned char t, unsigned char lambda[tt], + unsigned char *err_no, unsigned char err_loc[tt], unsigned char alpha_inv[tt]); +//void chien_search( unsigned char k, unsigned char t, unsigned char lambda[tt], +// unsigned char loc[kk]);
reedsolomon/trunk/cpp-source/chien_search.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/error_mag.h =================================================================== --- reedsolomon/trunk/cpp-source/error_mag.h (nonexistent) +++ reedsolomon/trunk/cpp-source/error_mag.h (revision 2) @@ -0,0 +1,33 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" + +void error_mag(unsigned char k, unsigned char lambda[tt], unsigned char omega[tt], unsigned char err_no, + unsigned char err_loc[tt], unsigned char alpha_inv[tt], unsigned char err[kk]); + +
reedsolomon/trunk/cpp-source/error_mag.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/gf_arith.cpp =================================================================== --- reedsolomon/trunk/cpp-source/gf_arith.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/gf_arith.cpp (revision 2) @@ -0,0 +1,413 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +/* + Incorporates all GF arithmetic used in various modules +*/ +//#include "ac_int.h" +#include "gf_arith.h" + + +unsigned char gfadd_hw(unsigned char a, unsigned char b) +{ + return a^b; +} + +unsigned char gfmult_hw(unsigned char a, unsigned char b) +{ + + unsigned int temp = 0; + + // Directive: Unroll loop maximally + for (int i = 0; i < 8; i++) + if (b & (1 << i)) + temp ^= (unsigned int)(a << i); + + // Directive: Unroll loop maximally + for (int k = 15; k > 7; k--) + if (temp & (1 << k)) + temp ^= (unsigned int)(pp_char << (k - 8)); + + return (temp & 255); + +} + +unsigned char alpha (unsigned char n) +{ + unsigned char alpha_lut[256] = { + 1, + 2, + 4, + 8, + 16, + 32, + 64, + 128, + 29, + 58, + 116, + 232, + 205, + 135, + 19, + 38, + 76, + 152, + 45, + 90, + 180, + 117, + 234, + 201, + 143, + 3, + 6, + 12, + 24, + 48, + 96, + 192, + 157, + 39, + 78, + 157, + 37, + 74, + 148, + 53, + 106, + 212,181, 119, 238, 193,159,35, 70, 140, 5, 10, 20, 40, 80, 160, + 93, 186, 105,210, 185,111,222,161,95,190,97,194,153,47,94,188,101,202,137,15,30,60,120,240,253, + 231,211,187,107,214,177,127,254,225,223,163,91,182,113,226,217,175,65,134,17,34,68,136,13,26,52,104, + 208,189,103,206,129,31,62,124,248,237,199,147,59,118,236,197,151,51,102,204,133,23,46,92,184,109,218, + 169,79,158,33,66,132,21,42,84,168,77,154,41,82,164,85,170,73,146,57,114,228,213,183,115,230,209, + 191,99,198,145,63,126,252,229,215,179,123,246,241,255,227,219,171,75,150,49,98,196,149,55,110,220,165,87,174, + 65,130,25,50,100,200,141,7,14,28,56,112,224,221,167,83,166,81,162,89,178,121,242,249,239,195,155,43,86,172, + 69,138,9,18,36,72,144,61,122,244,245,247,243,251,235,203,139,11,22,44,88,176,125,250,233,207,131,27,54,108,216, + 173,71,142,0}; + return alpha_lut[n]; +} + +unsigned char gfinv_lut (unsigned char a) +{ + +unsigned char lut[256] = { +2 +,1 +,142 +,244 +,71 +,167 +,122 +,186 +,173 +,157 +,221 +,152 +,61 +,170 +,93 +,150 +,216 +,114 +,192 +,88 +,224 +,62 +,76 +,102 +,144 +,222 +,85 +,128 +,160 +,131 +,75 +,42 +,108 +,237 +,57 +,81 +,96 +,86 +,44 +,138 +,112 +,208 +,31 +,74 +,38 +,139 +,51 +,110 +,72 +,137 +,111 +,46 +,164 +,195 +,64 +,94 +,80 +,34 +,207 +,169 +,171 +,12 +,21 +,225 +,54 +,95 +,248 +,213 +,146 +,78 +,166 +,4 +,48 +,136 +,43 +,30 +,22 +,103 +,69 +,147 +,56 +,35 +,104 +,140 +,129 +,26 +,37 +,97 +,19 +,193 +,203 +,99 +,151 +,14 +,55 +,65 +,36 +,87 +,202 +,91 +,185 +,196 +,23 +,77 +,82 +,141 +,239 +,179 +,32 +,236 +,47 +,50 +,40 +,209 +,17 +,217 +,233 +,251 +,218 +,121 +,219 +,119 +,6 +,187 +,132 +,205 +,254 +,252 +,27 +,84 +,161 +,29 +,124 +,204 +,228 +,176 +,73 +,49 +,39 +,45 +,83 +,105 +,2 +,245 +,24 +,223 +,68 +,79 +,155 +,188 +,15 +,92 +,11 +,220 +,189 +,148 +,172 +,9 +,199 +,162 +,28 +,130 +,159 +,198 +,52 +,194 +,70 +,5 +,206 +,59 +,13 +,60 +,156 +,8 +,190 +,183 +,135 +,229 +,238 +,107 +,235 +,242 +,191 +,175 +,197 +,100 +,7 +,123 +,149 +,154 +,174 +,182 +,18 +,89 +,165 +,53 +,101 +,184 +,163 +,158 +,210 +,247 +,98 +,90 +,133 +,125 +,168 +,58 +,41 +,113 +,200 +,246 +,249 +,67 +,215 +,214 +,16 +,115 +,118 +,120 +,153 +,10 +,25 +,145 +,20 +,63 +,230 +,240 +,134 +,177 +,226 +,241 +,250 +,116 +,243 +,180 +,109 +,33 +,178 +,106 +,227 +,231 +,181 +,234 +,3 +,143 +,211 +,201 +,66 +,212 +,232 +,117 +,127 +,255 +,126 +,253}; + + return lut[a]; +} + +unsigned char alphainv_lut (unsigned char n) +{ + if (n == 0) + return 1; + return gfinv_lut( alpha (n) ); +} + +unsigned char gfdiv_lut (unsigned char dividend, unsigned char divisor) +{ + return gfmult_hw ( dividend, gfinv_lut(divisor)); +} + + + +// Assumption: First bit of Lambda (alpha**0) is not transmitted +void compute_deriv (unsigned char lambda[tt], unsigned char lambda_deriv[tt]) +{ + // Directive: Unroll loop maximally + for (int i = 0; i < tt; i++) + lambda_deriv[i] = (i % 2 == 0) ? lambda[i] : 0; +} + + +unsigned char poly_eval (unsigned char poly[tt], unsigned char alpha_inv) +{ + unsigned char val = 0; + + // Directive: Unroll loop maximally + for (int j = tt-1; j >= 0; j--) + { + val = gfadd_hw(gfmult_hw(val, alpha_inv), poly[j]); + } + return val; +} +
reedsolomon/trunk/cpp-source/gf_arith.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/test_rs_decode.cpp =================================================================== --- reedsolomon/trunk/cpp-source/test_rs_decode.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/test_rs_decode.cpp (revision 2) @@ -0,0 +1,53 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + + +#include +#include "global_rs.h" +#include "rs_decode.h" +using namespace std; + + +int main () +{ + //Send one encoded file with errors (16 bytes set to 0) multiple times. + unsigned char n = nn; + unsigned char t = tt; + unsigned char r [255] = {223, 0, 221, 220, 219, 218, 217, 216, 215, 214, 213, 212, 211, 210, 209, 208, 207, 206, 205, 204, 203, 202, 201, 200, 199, 198, 197, 196, 195, 194, 193, 192, 191, 190, 189, 188, 187, 186, 185, 184, 183, 182, 181, 180, 179, 178, 177, 176, 175, 174, 173, 172, 171, 170, 169, 168, 167, 166, 165, 164, 163, 162, 161, 160, 159, 158, 157, 156, 155, 154, 153, 152, 151, 150, 149, 148, 147, 146, 145, 144, 143, 142, 141, 140, 139, 138, 137, 136, 135, 134, 133, 132, 131, 130, 129, 128, 127, 126, 125, 124, 123, 122, 121, 120, 119, 118, 117, 116, 115, 114, 113, 112, 111, 110, 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 253, 9, 60, 220, 91, 202, 48, 83, 201, 181, 81, 123, 117, 63, 98, 219, 20, 9, 71, 13, 231, 180, 105, 110, 114, 104, 147, 18, 55, 145, 170, 26}; + + // unsigned char s[16] + unsigned char k = 0; + unsigned char out_d[kk]; + +for (int j = 0; j < 3; ++j) +{ + rs_decode(n, t, r, &k, out_d); + + for (int i = 0; i < k; ++ i) + cout << "out_d["<
reedsolomon/trunk/cpp-source/test_rs_decode.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/rs_fifo.cpp =================================================================== --- reedsolomon/trunk/cpp-source/rs_fifo.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/rs_fifo.cpp (revision 2) @@ -0,0 +1,35 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" +#include "rs_fifo.h" + +void rs_fifo(unsigned char k, unsigned char in_d[nn], unsigned char out_d[kk]) +{ + for (int i = 0; i < kk; i++) + out_d[i] = (i < k) ? in_d[i] : 0; +}
reedsolomon/trunk/cpp-source/rs_fifo.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/rs_decode.cpp =================================================================== --- reedsolomon/trunk/cpp-source/rs_decode.cpp (nonexistent) +++ reedsolomon/trunk/cpp-source/rs_decode.cpp (revision 2) @@ -0,0 +1,67 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" +#include "syndrome.h" +#include "berlekamp.h" +#include "chien_search.h" +#include "error_mag.h" +#include "error_correct.h" +#include "rs_fifo.h" + + +// Top level decoder module +void rs_decode (unsigned char n, unsigned char t, unsigned char in_d[nn], + unsigned char *k, unsigned char out_d[kk]) +{ + unsigned char temp_k = n - 2*t; + unsigned char s[2*tt]; + unsigned char c[tt+2]; + unsigned char w[tt+2]; + unsigned char lambda[tt]; + unsigned char omega[tt]; + unsigned char err_no; + unsigned char err_loc[kk]; + unsigned char alpha_inv[tt]; + unsigned char err[kk]; + unsigned char in_data[kk]; + unsigned char in_d_2[nn]; + + // Create copy of input to pass to fifo to error corrector + // Directive: Unroll loop maximally +Simple_rs1: for (int i = 0; i < nn; i++) + in_d_2[i] = in_d[i]; + + *k = temp_k; + rs_fifo(temp_k, in_d, in_data); + syndrome(temp_k, t, in_d_2, s); + berlekamp(t, s, lambda, omega); + chien_search(kk, tt, lambda, &err_no, err_loc, alpha_inv); + error_mag(kk, lambda, omega, err_no, err_loc, alpha_inv, err); + error_correct(temp_k, in_data, err, out_d); + +}
reedsolomon/trunk/cpp-source/rs_decode.cpp Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/gf_arith.h =================================================================== --- reedsolomon/trunk/cpp-source/gf_arith.h (nonexistent) +++ reedsolomon/trunk/cpp-source/gf_arith.h (revision 2) @@ -0,0 +1,46 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" + +const unsigned int pp [mm+1] = { 1, 0, 1, 1, 1, 0, 0, 0, 1} ; /* specify irreducible polynomial coeffts */ +const unsigned char pp_char = 29; + +void generate_gf( int *alpha_to, int *index_of); +unsigned char gfmult_lut(unsigned char a, unsigned char b, int *alpha_to, int *index_of); +unsigned char gfmult_hw(unsigned char a, unsigned char b); +unsigned char gfadd_hw(unsigned char a, unsigned char b); +unsigned char gfinv_lut(unsigned char a); +unsigned char alpha (unsigned char n); +unsigned char alphainv_lut (unsigned char n); +unsigned char gfdiv_lut (unsigned char dividend, unsigned char divisor); +void polymult_mod2t (unsigned char *result, unsigned char *left, unsigned char *right); +void compute_deriv (unsigned char lambda[tt], unsigned char lambda_deriv[tt]); +unsigned char poly_eval (unsigned char poly[tt], unsigned char alpha_inv); + + +
reedsolomon/trunk/cpp-source/gf_arith.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/rs_fifo.h =================================================================== --- reedsolomon/trunk/cpp-source/rs_fifo.h (nonexistent) +++ reedsolomon/trunk/cpp-source/rs_fifo.h (revision 2) @@ -0,0 +1,31 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" + +void rs_fifo(unsigned char k, unsigned char in_d[nn], unsigned char out_d[kk]); +
reedsolomon/trunk/cpp-source/rs_fifo.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/Makefile =================================================================== --- reedsolomon/trunk/cpp-source/Makefile (nonexistent) +++ reedsolomon/trunk/cpp-source/Makefile (revision 2) @@ -0,0 +1,24 @@ +default: rs_decode + +chien_search: + g++ test_chien_search.cpp gf_arith.h gf_arith.cpp chien_search.cpp chien_search.h + +error_mag: + g++ test_error_mag.cpp gf_arith.h gf_arith.cpp error_mag.cpp error_mag.h + +error_correct: + g++ test_error_correct.cpp gf_arith.h gf_arith.cpp error_correct.cpp error_correct.h + +syndrome: + g++ test_syndrome.cpp gf_arith.h gf_arith.cpp syndrome.cpp syndrome.h + +berlekamp: + g++ test_berlkamp.cpp gf_arith.h gf_arith.cpp berlekamp.cpp berlekamp.h + +rs_decode: + g++ test_rs_decode.cpp gf_arith.h gf_arith.cpp rs_decode.h rs_decode.cpp syndrome.h syndrome.cpp \ + berlekamp.h berlekamp.cpp chien_search.h chien_search.cpp error_mag.h error_mag.cpp \ + error_correct.h error_correct.cpp rs_fifo.h rs_fifo.cpp + +clean: + rm a.out *.gch \ No newline at end of file
reedsolomon/trunk/cpp-source/Makefile Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property Index: reedsolomon/trunk/cpp-source/rs_decode.h =================================================================== --- reedsolomon/trunk/cpp-source/rs_decode.h (nonexistent) +++ reedsolomon/trunk/cpp-source/rs_decode.h (revision 2) @@ -0,0 +1,31 @@ +//----------------------------------------------------------------------// +// The MIT License +// +// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng +// Contact: abhiag@gmail.com +// +// Permission is hereby granted, free of charge, to any person +// obtaining a copy of this software and associated documentation +// files (the "Software"), to deal in the Software without +// restriction, including without limitation the rights to use, +// copy, modify, merge, publish, distribute, sublicense, and/or sell +// copies of the Software, and to permit persons to whom the +// Software is furnished to do so, subject to the following conditions: +// +// The above copyright notice and this permission notice shall be +// included in all copies or substantial portions of the Software. +// +// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, +// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES +// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND +// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT +// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, +// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR +// OTHER DEALINGS IN THE SOFTWARE. +//----------------------------------------------------------------------// + +#include "global_rs.h" + +void rs_decode (unsigned char n, unsigned char t, unsigned char in_d[nn], + unsigned char *k, unsigned char out_d[kk]);
reedsolomon/trunk/cpp-source/rs_decode.h Property changes : Added: svn:executable ## -0,0 +1 ## +* \ No newline at end of property

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.