[Cryptography Team] Reed Solomon Erasure Coding and Error Correction

[Robert Withers]

Hey everyone,

I hope you all are well, having the time of your lives!

Would anyone wish to help me develop plugins to speedup ReedSolomon?

I am feeling the dopamine high from finally finishing (mostly) my Reed Solomon implementation, both Erasure Coding from Backblaze [1] and Error Correction from ZXing [2]. I got decoding working correctly, with dataMatrix256 and QRCode, including corruption repair, within t/2 errors.

It is VERY SLOOOW, way to slow to use yet. I am working on writing plugins for the hot spots, which are on the decode side: GFPoly evaluateAt (40.1%), Decoder runEuclideanAlgorithm(38.5%), Decoder findErrorLocations(12.6%) and Decoder find ErrorMagnitudes(2.3%). At the bottom, an exposition of performance profiling the GF FEC code.

It is written in Squeak, my favorite all-time language environment. I have used it for over 20 years. It is so beautiful! The rule of development is #GetItWorking, #GetItWorkingRight #GetItWorkingFast.

If you are interested in checking out the code, go to http://squeak.org and grab squeak. Once you have it running, right click for the World Menu and select open...Monticello Browser. Add a new repository of type HTTP and enter the Cryptography repository.

MCHttpRepository
    location: '
https://www.squeaksource.com/Cryptography
'
    user: 'squeak'
    password: 'squeak'

Open a Workspace (World Menu -> Workspace) & run this code (paste into Workspace, select it and right click do it.):

Installer ss
    project: 'Cryptography';
    install: 'ProCrypto-1-1-1';
    install: 'ProCryptoTests-1-1-1'.

Now you can open a Browser to look at the code (categories: CryptographyRSFEC & CryptographyRSFECTests) or open a TestRunner to test it (World Menu -> *).

[1] Backblze RS erasure code -  https://stackoverflow.com/posts/67696209/timeline

I am feeling the dopamine high from finally finishing (mostly) my Reed Solomon implementation. I got decoding working correctly, with dataMatrix256 and QRCode, including corruption repair, within t/2 errors. It is VERY SLOOOW, way to slow to use yet. There are speedups possible in writing a plugin for the hot spots, which are on the decode side: GFPoly evaluateAt (40.1%), Decoder runEuclideanAlgorithm(38.5%), Decoder findErrorLocations(12.6%) and Decoder find ErrorMagnitudes(2.3%).

It is written in Squeak, my favorite all-time language environment. I have used it for over 20 years. It is so beautiful! The rule of development is #GetItWorking, #GetItWorkingRight #GetItWorkingFast.

If you are interested in checking out the code, go to http://squeak.org and grab squeak. Once you have it running, right click for the World Menu and select open...Monticello Browser. Add a new repository of type HTTP and enter the Cryptography repository.

MCHttpRepository
    location: '
https://www.squeaksource.com/Cryptography
'
    user: 'squeak'
    password: 'squeak'

Open a Workspace (World Menu -> Workspace) & run this code (paste into Workspace, select it and right click do it.):

Installer ss
    project: 'Cryptography';
    install: 'ProCrypto-1-1-1';
    install: 'ProCryptoTests-1-1-1'.

Now you can open a Browser to look at the code (categories: CryptographyRSFEC & CryptographyRSFECTests) or open a TestRunner to test it (World Menu -> *).

[1] Backblaze Open-sources Reed-Solomon Erasure Coding Source Code - https://www.backblaze.com/blog/reed-solomon/
[2] ZXing github -https://github.com/zxing/zxing/tree/master/core/src/main/java/com/google/zxing/common/reedsolomon

---

From the comment on CryptographyRSErrorCorrection-rww.12.mcz...

Fixed decoding. Some test pass green (DataMatrix & QRCodes) with encoding, decoding AND error correction all working. So the algorithms are working correctly. #GetItWorking, #GetItWorkingRight #GetItWorkingFast. AztecParam GF is still failing.

Do not allow values equal to the max 256. it passes tests but it is VERY SLOOOW. Profilie looks like, top tree branches, then summary. I may need to pluginize both GF and GFPoly. The costly methods are in decode, with GF Polynomial evaluation, the Euclidean Algorithm, the Chein's search (#findErrorLocations) and the Forney's formula (#findErrorMagnitudes). In the leaves, I can see that OrderedColection access is expensive.

Top tree branches:
[| 93.7% {136540ms} RSFECDecoder>>decode:twoS:
[| 40.1% {58370ms} RSFECGenericGFPoly>>evaluateAt:
[| 38.5% {56167ms} RSFECDecoder>>runEuclideanAlgorithmPoly:poly:rDegrees:
[| 12.6% {18331ms} RSFECDecoder>>findErrorLocations:
[| 2.3% {3423ms} RSFECDecoder>>findErrorMagnitudes:errorLlocations:
[ 5.4% {7842ms} RSFECReedSolomonTest>>corrupt:howMany:random:max:

**Leaves**
44.7% {65149ms} OrderedCollection>>at:
12.8% {18619ms} SmallInteger(Number)>>positive
8.0% {11589ms} RSFECGenericGF>>addOrSubtract:by:
5.7% {8332ms} RSFECGenericGF>>multiply:by:
5.0% {7352ms} RSFECGenericGFPoly>>evaluateAt:
5.0% {7270ms} OrderedCollection>>at:put:
4.6% {6727ms} False>>|
1.7% {2537ms} RSFECGenericGFPoly>>addOrSubtractPoly:
1.4% {1996ms} OrderedCollection(SequenceableCollection)>>replaceFrom:to:with:startingAt:
1.3% {1851ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient:
1.1% {1562ms} LargePositiveInteger(Integer)>>bitShift:

**Memory**
old -16,777,216 bytes
young +15,072,816 bytes
used -1,704,400 bytes
free -15,072,816 bytes

**GCs**
full 2 totalling 171 ms (0.12% uptime), avg 85.5 ms
incr 4193 totalling 764 ms (0.5% uptime), avg 0.2 ms
tenures 6,093 (avg 0 GCs/tenure)
root table 0 overflows

--

Kindly, Robert
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/cryptography/attachments/20210526/e34d5214/attachment.html>