-2
\$\begingroup\$

You can read about my Squeak code release implementing ZXing's Reed Solomon Error Correction. It was suggested to me that I ask a question here.

The speedup is 568% so far.

NOTE: I got plugganized GF and GFPoly functions working, with the exception of #dividePoly:. Got some Decoder methods working. I am updating the example here to be the plugganized #findErrorLocations: code.

CryptographyRSPluginExtending-rww.7.mcz now has all 7 missing primitives, for the FECDecoder, the GFPoly and the GaloisCodingLoop. Building and deploying this RSPlugin iwll blow the image up on GFFEC class>>#startUp:. This is for debugging. Here is the list.

GaloisCodingLoopOutputByteInputExpCodingLoopWithPlugin>>#primCheckSomeShardsMatrixRows: matrixRows
    inputs: inputs
    toCheck: toCheck
    offset: offset
    byteCount: byteCount
GaloisCodingLoopOutputByteInputExpCodingLoopWithPlugin>>#primCodeSomeShardsMatrixRows: matrixRows
    inputs: inputs
    outputs: outputs
    offset: offset
    byteCount: byteCount
GaloisCodingLoopOutputByteInputExpCodingLoopWithPlugin>>#primComputeValueMatrixRow: matrixRow
    inputs: inputs
    inputIndex: inputIndex
    byteIndex: byteIndex
    value: value
FECGFPolyWithPlugin>>#primInitializePolyFieldSize:  fieldSize
    coefficients: localCoefficients
FECGFPolyWithPlugin>>#primDividePolySelfCoefficients: coefficients
    otherCoefficients: otherCoefficients
    fieldSize: fieldSize
FECDecoderWithPlugin>>#primDecode: decoded
    twoS: twoS
    generatorBase: generatorBase
FECDecoderWithPlugin>>#primRunEuclideanAlgorithmPolyA: polyA
    polyB: polyB
    degrees: fieldSize

Here is the DoIt to load everything into a Squeak VMMaker image, build in the image directory of the opensmalltalk-vm git clone. [1][2][3].

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

VM and project links:

[1] Opensmalltalk-vm

[2] VMMaker Squeak repository

[3] Cryptography Squeak repository

[4] RSFEC Squeak and C code/compiled:linked plugins

Currently failing at DecoderWithPlugin>>#findErrorLocations: primitive call. Strange thing, argument goes nil , it looks like. How'd that happen? Here's the debug log/crash package.

I have generated C code from RSFEC's GF Squeak plugin code using the Squeak CCodeGenerator. Now the RSFECPlugin Smalltalk methods for the Decoder.

findErrorLocationsDegree: degree 
    coefficients: coefficients 
    count: count 
    fieldSize: fieldSize 
    result: result

    "// This is a direct application of Chien's search"

    <var: 'coefficients' type: #'unsigned char*'>
    <var: 'result' type: #'unsigned char*'>

    | numErrors e index | 
    numErrors := degree.
    (numErrors = 1)
            ifTrue: [^ result at: 0 put:(coefficients at: 0)].

    e := 0.
    index := 1.
    [(index < fieldSize) & (e < numErrors)]
        whileTrue: [
            ((self evaluateAt: index coefficients: coefficients count: count fieldSize: fieldSize) = 0)
                ifTrue: [
                    result at: e put: (self inverse: index withSize: fieldSize).
                    e := e + 1].
        index := index + 1].

    (e = numErrors)
        ifFalse: [ ^interpreterProxy primitiveFailFor: PrimErrBadArgument ].
    ^ result

And here is the resulting C Code from the Translator.

/*  // This is a direct application of Chien's search */
/* RSFECPlugin>>#findErrorLocationsDegree:
    coefficients:
    count:
    fieldSize:
    result: */
static unsigned char * findErrorLocationsDegreecoefficientscountfieldSizeresult(
    sqInt degree, 
    unsigned char *coefficients, 
    sqInt count, 
    sqInt fieldSize, 
    unsigned char *result) {

        sqInt e;
        sqInt index;
        sqInt numErrors;

        numErrors = degree;
        if (numErrors == 1) {
            return result[0] = (coefficients[0]);
        }
        e = 0;
        index = 1;
        while ((index < fieldSize) && (e < numErrors)) {
            if ((evaluateAtcoefficientscountfieldSize(index, coefficients, count, fieldSize)) == 0) {
                result[e] = (inversewithSize(index, fieldSize));
                e += 1;
            }
            index += 1;
        }
        if (!(e == numErrors)) {
            return primitiveFailFor(PrimErrBadArgument);
        }
        return result;
    }

While we wait, perhaps y'all would like to take a gander at the Smalltalk code [3] that gets translated into the posted C code....I am supposed to include the source being discussed:

VM and project links:

[1] Opensmalltalk-vm

[2] VMMaker Squeak repository

[4] RSFEC Squeak and C code/compiled:linked plugins

primitiveMultiplyPolySelfCoefficientsOtherCoefficientsProductFieldSize

    <export: true>
    <var: 'selfCoefficients' type: 'unsigned char*' >
    <var: 'otherCoefficients' type: 'unsigned char*' >
    <var: 'product' type: 'unsigned char*' >

    | otherCoefficients selfCoefficients product otherCount selfCount otherCoefficientsOop productOop selfCoefficientsOop fieldSize |
    interpreterProxy methodArgumentCount = 4
        ifFalse: [ ^interpreterProxy primitiveFailFor: PrimErrBadNumArgs ].
    selfCoefficientsOop := interpreterProxy stackObjectValue: 3.
    otherCoefficientsOop := interpreterProxy stackObjectValue: 2.
    productOop := interpreterProxy stackObjectValue: 1.
    fieldSize := interpreterProxy stackIntegerValue: 0.

    selfCount := interpreterProxy stSizeOf: selfCoefficientsOop.
    otherCount := interpreterProxy stSizeOf: otherCoefficientsOop.
    selfCoefficients := interpreterProxy firstIndexableField: selfCoefficientsOop.
    otherCoefficients := interpreterProxy firstIndexableField: otherCoefficientsOop.
    product := interpreterProxy firstIndexableField: productOop.

    self 
        multiplyPolySelfCoefficients: selfCoefficients 
        selfCount: selfCount 
        otherCoefficients: otherCoefficients 
        otherCount: otherCount 
        product: product
        fieldSize: fieldSize.

    interpreterProxy methodReturnReceiver.

Here is the Squeak code for translation that does the actual polynomial multiply. NOTE: This method's translated C code is in-lined into the primitive function.

multiplyPolySelfCoefficients: selfCoefficients 
    selfCount: selfCount 
    otherCoefficients: otherCoefficients 
    otherCount: otherCount 
    product: product 
    fieldSize: fieldSize

    <var: 'selfCoefficients' type: #'unsigned char*'>
    <var: 'otherCoefficients' type: #'unsigned char*'>
    <var: 'product' type: #'unsigned char*'>

    | aCoeff aCoefficients aLength bCoefficients bLength |
    aCoefficients := selfCoefficients.
    aLength := selfCount.
    bCoefficients := otherCoefficients.
    bLength := otherCount.

    0 to: (aLength - 1)
        do: [:aIndex | 
            aCoeff := aCoefficients at: aIndex.
            0 to: (bLength - 1)
                do: [:bIndex |
                    product at: (aIndex + bIndex) put: ((self 
                        addOrSubtract: (product at: (aIndex + bIndex))
                        by: (self multiply: aCoeff by: (bCoefficients at: bIndex) withSize: fieldSize))) ]].
    ^ product

Pretty sweet right? Yo, Stylin' Squeak. .. ... '...*,^

We run on top of Spur (memory mgr), Cog (JITting language process engine) + Sista (active advancing JITting). The mysteries of the Squeak VM...

Hopefully the hot spots will change and the plugins have helped. They did: 407%! We shall see what more can be done...

I have completed plugin work. I now have a running plugin. The speedup is 568% and all the hotspots changed again. Here are the profiling results from just the RSFEC code alone, no RSErasure code is in the profiles. The new hotspots are, with RSFECPlugin, then without.

I am implemented further methods {#findErrorLocations:, #findErrorMagnitudes:errorLocations:, #decode:twoS:}.

The remaining potential plugganization relates to complex object instantiation inside the plugin functions. {#decode:twoS:, #runEuclideanAlgorithm: and #initializeField:coefficients:}. The best value for work return is to plugganize #initializeField:coefficients: at 3.3 seconds (14%)

Calls to unplugganized GFPoly/Decoder methods:

WITH GF & GFPOLY &  DECODER PRIMITIVES

- 22194 tallies, 22648 msec.

(128683 / 22648 ) asFloat

**Leaves**
29.1% {6586ms} RSFECDecoderWithPlugin>>decode:twoS:
14.7% {3329ms} RSFECGenericGFPoly class>>newField:coefficients:
1.0% {237ms} RSFECDecoderWithPlugin>>runEuclideanAlgorithmPoly:poly:rDegrees:

Calls to plugganized GF/GFPoly/Decoder methods:

7.3% {1646ms} RSFECDecoderWithPlugin>>primFindErrorLocationsDegree:coefficients:result:fieldSize:
2.9% {654ms} RSFECDecoderWithPlugin>>findErrorMagnitudes:errorLocations:
1.4% {317ms} RSFECGenericGFWithPlugin>>log:

And:

WITHOUT GF & GFPOLY PRIMITIVES - NO RSFEC PRIMITIVES

- 98352 tallies, 128683 msec.

**Leaves**
GF arithmetic
23.4% {30126ms} RSFECGenericGF>>exp:
13.4% {17229ms} RSFECGenericGF>>addOrSubtract:by:
11.9% {15251ms} RSFECGenericGF>>maskValue:
10.0% {12916ms} RSFECGenericGF>>log:
8.6% {11059ms} RSFECGenericGF>>normalizeIndex:
6.8% {8792ms} RSFECGenericGF>>multiply:by:
GFPoly arithmetic
2.7% {3529ms} RSFECGenericGFPoly>>evaluateAt:
2.1% {2715ms} RSFECGenericGFPoly>>addOrSubtractPoly:
2.0% {2578ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient:

Grazie, rabbit . .. ... '...'^,^

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Welcome to Code Review. If you haven't tested the program, how can you be sure it's correct? The program being correct to the best of your knowledge is one of our requirements, as stated in the help center. \$\endgroup\$ – Mast May 28 at 4:12
  • \$\begingroup\$ I was unaware of this requirement. The generated code comes from working Squeak code. I thought code review can look at code without such requirement. The code I showed was for GF multiplication. I will hit you up again when I get it compiling and tested. \$\endgroup\$ – rabbit May 28 at 14:53
  • \$\begingroup\$ While we wait, perhaps y'all would like to take a gander at the Smalltalk code that gets translated into the posted C code....I am supposed to include the source being discussed: See the editorial update to my OP. dropbox.com/s/l76k8yq7cpjnodc/RSFECPlugin.st?dl=0 \$\endgroup\$ – rabbit May 28 at 20:07
  • 2
    \$\begingroup\$ What is it you want reviewed exactly? Since the C code is generated by a tool, it seems it makes more sense to review that tool than the generated code. \$\endgroup\$ – G. Sliepen May 29 at 16:52
  • \$\begingroup\$ I wanted my Squeak code reviewed that gets translated into C code. I was not asking for the translator to be reviewed as that is not my work. If interested in the tool, you can find it in the VMMaker repository/package on source.squeak.org. I got everything compiling for RS and the speedup is 407 %.. I updated the OP with the latest code: Squeak & C, and the profiling numbers for RSFECPlugin. \$\endgroup\$ – rabbit Jun 2 at 15:31
0
\$\begingroup\$

Well, yes, let's call this the answer. Increased performance by 568%.

I finally got the changes made. You know that time when you have 2 images and you do the work in one and forget, then delete that one and have to recode all those changes? Exactly.

Nonetheless, I got the changes made and did a test of creating a ByteArray in a primitive/computation method:

    #fecAddOrSubtractPolySelfCoefficients:selfCount:otherCoefficients:otherCount:.

In my case, I decided to create the result ByteArray in the computation method and return the resultOop to the primitive for #methodReturnValue:. Here is the primitive, followed by the computation method. This seems to work as I compiled and tested it. One consideration is that if we are in a primitive and call another, like happens in the decode methods, then I must remember to #interpreterProxy firstIndexableField: resultOop to access the array again (pass as argument to yet another compute method, for instance). Is this the best approach?

    resultOop := self
        fecAddOrSubtractPolySelfCoefficients: selfCoefficients
        selfCount: selfCount
        otherCoefficients: otherCoefficients
        otherCount: otherCount.

    ^ interpreterProxy failed
            ifTrue: [interpreterProxy primitiveFail]
            ifFalse: [interpreterProxy methodReturnValue: resultOop].

And the computation method

    resultOop := interpreterProxy
                instantiateClass: interpreterProxy classByteArray
                indexableSize: (selfCount max: otherCount).
    result := interpreterProxy firstIndexableField: resultOop.

    "COMPUTATIONS filling #result"

    ^ resultOop
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.