Cryptography May 2021

cryptography@lists.squeakfoundation.org

1 participants
10 discussions

Re: [Cryptography Team] [Vm-dev] Reed Solomon plugins & performance slow down
by Robert Withers 31 May '21

31 May '21

Hi Levente, Thank you for having a look-see and letting me know your thoughts! It makes sense what you are saying. so I think the only way to speed it up is to embed the loops into primitives. I have 5 of 6 methods from Poly that I am stuffing into the plugin. The #dividePoly: is a bit more complicated, updating the remainder poly and so forth. I do not think a Poly can be within a primitive. Hopefully, {product := Array new: size withAll: 0} will work in translation. I fixed #initializeExpTable per your suggestion. Thanks! --- Kindly, Robert On 5/30/21 8:18 PM, Levente Uzonyi wrote: > Hi Robert, > > I had a quick look at the plugin code. The operations you implemented in > the plugin are way too simple. The VM's JIT makes the smalltalk code run > faster, because it has the same operations implemented, and it can avoid > calling the overhead of calling the primitive many times. Hence the > slowdown. > > For example, RSFECPlugin >> #primitiveAddOrSubtractby seems to implement > bitwise xor on two 32-bit unsigned values, but the arguments are always > 0-255. The VM has primitive 16, which does bitwise xor and covers that > input range, so the JIT, combined with other operations can generate > machine code directly with that without jumping back and forth between > native code and smalltalk. > > If you want a plugin to provide any noticable speedup, you need to do > more computation in a single primtiive call. > > > Levente > > P.S.: I think, in RSFECGenericGC >> #initializeExpTable, the lines > > x := x bitXor: primitive. > x bitAnd: (size - 1)]]. > > should read > > x := (x bitXor: primitive) bitAnd: size - 1 ]].

1 5

Reed Solomon plugins & performance slow down
by Robert Withers 31 May '21

31 May '21

Hey all'y'all, I got the plugins working correctly. Published to Cryptography. The plugins are attached. Unfortunately profiling indicates a slow down. The leaves did change from GaloisField methods to GaloisFieldPoly methods. I will work on pluginizing the GFPoly methods, such as #evaluateAt: & #multiplyByMonomialDegree:coefficient:... Here are the results without plugins (135 seconds): > WITHOUT PLUGINS > > - 132032 tallies, 135390 msec. > > **Tree** > -------------------------------- > Process: (40) 57626: nil > -------------------------------- > > **Leaves** > 16.9% {22843ms} RSFECGenericGF>>exp: > 9.2% {12450ms} RSFECGenericGF>>maskValue: > 8.6% {11659ms} RSFECGenericGF>>addOrSubtract:by: > 7.2% {9806ms} RSFECGenericGF>>log: > 6.6% {8958ms} RSFECGenericGF>>normalizeIndex: > 4.9% {6578ms} RSFECGenericGF>>multiply:by: > 2.3% {3130ms} RSErasureGalois>>maskValue: > 2.3% {3118ms} RSFECGenericGFPoly>>evaluateAt: > 1.6% {2175ms} RSErasureGalois>>normalizeIndex: > 1.3% {1718ms} RSFECGenericGFPoly>>addOrSubtractPoly: > 1.3% {1702ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: > 1.2% {1606ms} RSErasureGalois>>log: > 1.1% {1516ms} RSErasureGalois>>galoisMultiply:by: And here are the results with plugins (152 seconds): > WITH PLUGINS > > - 149040 tallies, 152531 msec. > > **Tree** > -------------------------------- > Process: (40) 89223: nil > -------------------------------- > > **Leaves** > 27.9% {42565ms} RSFECGenericGFWithPlugin>>addOrSubtract:by: > 17.3% {26440ms} RSFECGenericGFPoly>>evaluateAt: > 8.5% {12926ms} RSFECGenericGFWithPlugin>>maskValue: > 7.3% {11062ms} RSFECGenericGFPoly>>multiplyByMonomialDegree:coefficient: > 6.5% {9854ms} RSFECGenericGFPoly>>addOrSubtractPoly: > 5.6% {8598ms} RSFECGenericGFWithPlugin>>multiply:by: > 2.6% {4032ms} RSErasureGaloisWithPlugin>>galoisMultiply:by: > 2.4% {3601ms} RSErasureGaloisWithPlugin>>addOrSubtract:by: > 2.1% {3137ms} RSErasureGaloisWithPlugin>>maskValue: > 1.6% {2436ms} RSFECGenericGFPoly>>multiplyPoly: -- --- Kindly, Robert

1 0

A group for Squeakers on clubhouse
by Robert 28 May '21

28 May '21

Join up & join me! https://www.clubhouse.com/join/squeakers/YPbUWqn2 Kindly, Robert . .. ... ‘...^,^

1 0

My post to stackexchange's code review site [1].
by Robert Withers 28 May '21

28 May '21

A little outreach...I am referencing a CCodeGenerator, is it so? Any suggestions to clean it up, please let me know! Eliot, I mention Spur, Cog and Sista. How could I be more accurate in my descriptions of their roles? [1] [Squeak code for performant ReedSolomon error correction](https://codereview.stackexchange.com/questions/261315/squeak-co… - https://codereview.stackexchange.com/questions/261315/squeak-code-for-perfo… -- --- Kindly, Robert

1 0

Do we have Elliptic Curve Crypto?
by Robert 28 May '21

28 May '21

In the Cryptography repository? In yes, which algorithms? If no, what would it take to adopt them? Kindly, Robert . .. ... ‘...^,^

1 0

Re: [Cryptography Team] [Vm-dev] Issues: Trying to build the RS vm with the mvm script...
by Robert Withers 27 May '21

27 May '21

Awesome, let me try it! --- Kindly, Robert On 5/27/21 2:04 PM, Levente Uzonyi wrote: > The VM uses clang instead of gcc. So, you need to install clang. > > > Levente

1 0

Need a little help
by Robert Withers 27 May '21

27 May '21

Would someone knowledgeable take a look at the RS*Plugin image code and the c code that is generated. What am I missing? Thx! -- --- Kindly, Robert

1 1

Issues: Trying to build the RS vm with the mvm script...
by Robert Withers 27 May '21

27 May '21

I am trying to build the vm with RS external plugins I generated. I am getting some pushback: > rabbit@ganymede:~/vm-dev/opensmalltalk-vm/build.linux64x64/squeak.cog.spur/build$ ./mvm > clean? y > checking for gcc... clang > checking whether the C compiler works... no > configure: error: in `/home/rabbit/vm-dev/opensmalltalk-vm/build.linux64x64/squeak.cog.spur/build': > configure: error: C compiler cannot create executables > See `config.log' for more details How could I resolve this issue? I have the latest gcc, I think: > rabbit@ganymede:~/vm-dev/opensmalltalk-vm/build.linux64x64/squeak.cog.spur/build$ gcc --version > gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 I appreciate! -- --- Kindly, Robert

1 0

Implementing Reed Solomon plugins
by Robert Withers 27 May '21

27 May '21

I have the outlined definitions of 2 Plugins, 1 for RSErasurePlugin and 1 for RSFECPlugin. They are published to Cryptography. I am trying to understand how to write primitives to get the work done. Any and All assistance MOST WELCOME! Let's get her done! I believe I have properly implemented the #declareCVarsIn: and initialized for both plugins. I am looking at a primitive implementation in RSFECPlugin>>#primitiveInverseWithSize. A few questions: am I grabbing the stack arguments correctly? Testing their values correctly? Correctly calling a method to do the work. Manipulating the stack to setup a return value??? I am doing this...correct? > self pop: 2 thenPushInteger: multiplied. > ^interpreterProxy methodReturnInteger: multiplied. --- > primitiveInverseWithSize > <export: true> > <var: 'a' declareC: 'unsigned short' > > <var: 'size' declareC: 'unsigned short' > > > | a size multiplied | > interpreterProxy methodArgumentCount = 2 > ifFalse: [ ^interpreterProxy primitiveFailFor: PrimErrBadNumArgs ]. > a := interpreterProxy stackIntegerValue: 0. > size := interpreterProxy stackIntegerValue: 1. > > ((interpreterProxy isBytes: a) > and: [ (interpreterProxy stSizeOf: a) = 2 ]) > ifFalse: [ ^interpreterProxy primitiveFailFor: PrimErrBadArgument ]. > ((interpreterProxy isBytes: size) > and: [ (interpreterProxy stSizeOf: a) = 2 ]) > ifFalse: [ ^interpreterProxy primitiveFailFor: PrimErrBadArgument ]. > multiplied := self inverse: a withSize: size. > self pop: 2 thenPushInteger: multiplied. > ^interpreterProxy methodReturnInteger: multiplied. And: > inverse: a withSize: size > > (a = 0) > ifTrue: [RSErasureIllegalArgumentError signal: 'the argument is zero']. > ^ expTable at: (size - ((logTable at: (a + 1)) - 1)). -- --- Kindly, Robert

1 0

Reed Solomon Erasure Coding and Error Correction
by Robert Withers 26 May '21

26 May '21

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

1 3

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

Cryptography May 2021