[Cryptography Team] Reed Solomon Erasure Coding and Error Correction

[Robert Withers]

More versions published with more speedups. Using GF>>#maskValue: &
GF>>normalizeIndex: methods, to provide separate solutions for in-image
code and plugin code, with the differing index start. These could be
easily pluginized, me thinks.

**Leaves**
26.4% {25447ms} RSFECGenericGF>>exp:
14.0% {13505ms} RSFECGenericGF>>maskValue:
12.1% {11689ms} RSFECGenericGF>>addOrSubtract:by:
11.5% {11073ms} RSFECGenericGF>>log:
9.6% {9306ms} RSFECGenericGF>>normalizeIndex:
6.9% {6617ms} RSFECGenericGF>>multiply:by:
3.4% {3247ms} RSFECGenericGFPoly>>evaluateAt:
1.8% {1764ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient:
1.8% {1698ms} RSFECGenericGFPoly>>addOrSubtractPoly:

Kindly, Robert

On 5/26/21 3:54 PM, Robert Withers wrote:
> Speedup work: I converted OrderedCollection use to Array use to improve
> #at: lookup and #at:put: set calls. Code is published to Cryptography.
> OrderedCollection has fallen off the leaves, from profiling. Plugin
> support is next...
>
> **Leaves**
> 26.5% {29474ms} RSFECGenericGF>>addOrSubtract:by:
> 8.4% {9341ms} SmallInteger(Number)>>positive
> 7.3% {8067ms} False>>|
> 7.1% {7941ms} RSFECGenericGF>>multiply:by:
> 6.7% {7435ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient:
> 3.2% {3513ms} RSErasureGalois>>add:by:
> 3.1% {3500ms} SmallInteger>>digitAt:
> 3.1% {3481ms} RSErasureGalois>>tableMultiply:by:
> 2.9% {3263ms} RSFECGenericGFPoly>>evaluateAt:
> 2.8% {3130ms} SmallInteger(Integer)>>twosComplement
> 2.4% {2723ms} RSErasureGalois>>galoisMultiply:by:
> 2.1% {2350ms} SmallInteger>>digitLength
> 1.6% {1789ms} RSErasureGaloisTest(TestCase)>>assert:equals:
> 1.5% {1713ms} RSErasureGaloisTest(TestCase)>>assert:description:
> 1.5% {1699ms} RSFECGenericGFPoly>>addOrSubtractPoly:
> 1.5% {1674ms} Array(SequenceableCollection)>>do:
> 1.4% {1523ms} LargePositiveInteger(Integer)>>bitShift:
> 1.3% {1411ms} LargePositiveInteger class(Behavior)>>new:
> 1.1% {1269ms} SmallInteger(Integer)>>areAllBitsSet
> 1.1% {1218ms} SecureHashAlgorithm>>hashInteger:seed:
>
> Kindly, Robert
>
> On 5/26/21 1:52 PM, Robert Withers wrote:
>> Whoops, I repeated myself. So sorry. The pertinent profiling for Error
>> Correction is:
>>
>> Do not allow values equal to the max 256.  it passes tests but it is
>> VERY SLOOOW. Profile 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
>>