a test matrix is needed which copes with poly1305 having some rare-occurrences of "carry-roll-over" internally. a strategy is needed which detects some of these occurrences, then puts some test vectors together to ensure that the assembler (which is much slower to run) also passes. the one that will have confidence that such errors will not occur is the pure-python Poly1305 class which performs full python "Long" integer arithmetic. this can be used to help track down potential/actual 64-bit carry arithmetic errors. for this strategy to work it is important that the assembler (and poly1305-donna.py) faithfully implement the poly1305-donna-64bit.h algorithm exactly. --- * TODO strategy to deliberately introduce carry-rollover errors (to create test vectors to run against the assembler) * TODO miniature unit tests of fragments of poly1305-donna.py (to be used also against test_caller_svp64_poly1305.py) * TODO comparison matrix against: 1. python Poly1305 class instance 2. python Poly1305Donna class instance 3. c-based wrapper module around poly1305-donna.h 4. SVP64 assembler (in test_caller_xxxyyy.py) 5. pypowersim running svp64.
Rough brainstorming: To implement comprehensive unit tests we need to understand what we're testing, figure out the normal cases, edge cases, and additional behavior that is specifically related to SVP64. I'll organize this list in order of complexity. numbers are in bytes, m = message, k = key, h' = received MAC, h = generated MAC Message size: -m[0] is received, nothing to authenticate, exit - m[16] is received, algorithm needs to process exactly one block and is done. - m[16*n] is received, algorithm needs to process exactly n blocks using the same function and is done. -m[1<n<16] is received, algorithm needs to process leftover data as opposed to full data (I have to study this a bit more) -m[17<n] where n%16=/=0 received, algorithm processes n/16 blocks normally and the last block is processed as leftover.
(In reply to Sadoon Albader from comment #1) > Rough brainstorming: > > To implement comprehensive unit tests we need to understand what we're > testing, figure out the normal cases, edge cases, and additional behavior > that is specifically related to SVP64. so just like in the Test API, there are actually *three* things to test (all with the same data). actually 4 when it comes to it. no, 5! no 6! 1. python Poly1305 class instance 2. python Poly1305Donna class instance 3. SVP64 assembler (in test_caller_xxxyyy.py) 4. HDL (when it is able to run REMAP and elwidth overrides) 5. pypowersim (this is "optional" for you as it is extra work) running the poly1305-donna.h program compiled to *SFFS* which you would be converting slowly using (3) to... 6. pypowersim running svp64. but i would suggest stopping at (3), i will happily sign-off the entire RFP up to there :) nice thing is, you can actually write the unit tests *right now* for 1 and 2 but please do also write some "mini" intermediary unit tests for each group of 3-6 lines (a group doing h0+= h1 += h2 +=) so that you are *truly* confident that each group does the job; then when you come to plug all those "bits" together you will go "pffh, i *know* this should work"
(In reply to Luke Kenneth Casson Leighton from comment #2) > (In reply to Sadoon Albader from comment #1) > 1. python Poly1305 class instance > 2. python Poly1305Donna class instance > 3. SVP64 assembler (in test_caller_xxxyyy.py) 1. and 2. are simple enough, I've already added some known-working values from the original poly1305-donna project and they do work fine. Importantly, they are *not* multiples of 16-bytes and not less than 16-bytes which should put any implementation through its paces. But for a proper unit test I think at least 10 vectors with different sizes and different keys should be added, which I will do before attempting anything else. I've been reading https://libre-soc.org/docs/firststeps/ to better understand how test_caller_* works, is there any other relevant documentation to help steer me in a good direction? Not necessary as I feel I already understand 80% of how it works, but nice to have if available. EDIT: forgot one more thing: in addition to the 10 vectors, I'd also add a function that generates random data of random sizes and random keys and tests using all 3 implementations.
(In reply to Sadoon Albader from comment #3) > (In reply to Luke Kenneth Casson Leighton from comment #2) > > (In reply to Sadoon Albader from comment #1) > > 1. python Poly1305 class instance > > 2. python Poly1305Donna class instance > > 3. SVP64 assembler (in test_caller_xxxyyy.py) > > 1. and 2. are simple enough, I've already added some known-working values > from the original poly1305-donna project and they do work fine. git push! always always always push immediately. this is a key project workflow procedure. > Importantly, > they are *not* multiples of 16-bytes and not less than 16-bytes which should > put any implementation through its paces. > > But for a proper unit test I think at least 10 vectors with different sizes > and different keys should be added, which I will do before attempting > anything else. push the existing ones first. you'll see in HDL_workflow the rule is 5-15 lines of code per commit (with exceptions of course) > I've been reading https://libre-soc.org/docs/firststeps/ to better > understand how test_caller_* works, is there any other relevant > documentation to help steer me in a good direction? Not necessary as I feel > I already understand 80% of how it works, but nice to have if available. not really... there are however hundreds of unit tests, they are all the same. i just cut/paste an existing one, test_caller_svp64_chacha20.py is your best bet. > EDIT: forgot one more thing: in addition to the 10 vectors, I'd also add a > function that generates random data of random sizes and random keys and > tests using all 3 implementations. awesome. and that puts the work you're about to commit right now at way above the limit for commits? :) that's 3 separate commits you should have made, just in the past hour alone! this is how we can do review. nobody else can see your screen nor what is on your local hard drive.
(In reply to Luke Kenneth Casson Leighton from comment #4) > (In reply to Sadoon Albader from comment #3) > git push! always always always push immediately. this is a key project > workflow procedure. When I said "added" what I really meant was I was messing around with the code and *replaced* the original values :P I'll push it once it's actually added as opposed to replaced of course. > not really... there are however hundreds of unit tests, they are all the > same. i just cut/paste an existing one, test_caller_svp64_chacha20.py > is your best bet. Yes I noticed after sending, the tests are quite simple to write so I should have 80-90% of what we need done by next weekend. > this is how we can do review. > > nobody else can see your screen nor what is on your local hard drive. Most of what I sent was more of a brainstorming than actual code being written. So far the only change I made was the message and key to test against poly1305-donna, the rest is what I plan to write and then push, and of course, gradually. Not one huge commit-git-push :)
(In reply to Sadoon Albader from comment #5) > When I said "added" what I really meant was I was messing around with the > code and *replaced* the original values :P yyeah i did that too :) ah this is a... it just occurred to me, of course the tests will be very specific to the algorithm internals, it will be quite fragile. as in: if you don't *exactly* faithfully replicate the poly1305-donna algorithm (even from the original c) then you could end up missing something important, as it is so rare an occurrence. hm i tell you what, i will create a python wrapper around poly1305-donna.h so that *that* can also be added to the test matrix. i won't do the unit tests themselves (other than a real basic one), just to get it not to segfault ok? then you can run huge numbers of tests very quickly, on the c-based module *and* the poly1305-donna.py conversion, and at least have a degree of confidence that i did the conversion correctly! we *must* make sure that there is a "chain of confidence", absolutely no more than one "unknown" at any one time, no matter how small and "seemingly ridiculous" ok? just like in that word game.
(In reply to Luke Kenneth Casson Leighton from comment #6) > (In reply to Sadoon Albader from comment #5) > > we *must* make sure that there is a "chain of confidence", absolutely > no more than one "unknown" at any one time, no matter how small and > "seemingly ridiculous" ok? just like in that word game. Sure :)
siiiigh i don't know if you worked it out already sadoon, we need to *actually find* places where carry-roll-over errors might occur, and put specific values in that ensure they get tested. argh :) ok so some random tests are needed with an "accumulator list" when there are non-zero carrys... eurgh :)
(In reply to Luke Kenneth Casson Leighton from comment #8) > siiiigh i don't know if you worked it out already sadoon, we need to > *actually find* places where carry-roll-over errors might occur, > and put specific values in that ensure they get tested. > > argh :) > > ok so some random tests are needed with an "accumulator list" when > there are non-zero carrys... eurgh :) Not quite yet, will do this week though.
(In reply to Sadoon Albader from comment #9) > Not quite yet, will do this week though. am bored am on the case, am going to do some "decorators" to trap the ADD MUL ADDLO and SHF functions, trying hard to make the code "look like it's still the c code" i'll get it to print out a list of what it finds, just realised that when c=0b000 this is still a legitimate test-case not just c=0b001 to 0b100 first step: convert all use of "+" to call ADD(a,b) https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=539eda3c
next step in the (word-game-like) chain: rename the 64/128-bit math primitives, provide intercepts in the class, but provide *function-local* renames so that the code remains true to poly1305-donna-64bit.h https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=8cd4e8272a btw i'm not going to do all of this! i'm providing _you_ with the pieces ok? :)
carrying on from https://bugs.libre-soc.org/show_bug.cgi?id=1157#c26 the strategy needed is quite involved but straightforward: anything looking like it is carry-roll-over has to be reproduceable / replayable against *other implementations* of the algorithm. that in turn implies capturing *all* state information at the time of the math-operation. therefore what i am going to do is do a... what is it called... Context Manager that allows full input/output capture, in a clean and clear way.
(In reply to Luke Kenneth Casson Leighton from comment #12) > therefore what i am going to do is do a... what is it called... > Context Manager that allows full input/output capture, in a clean > and clear way. https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff;h=6479aa6ed404829f6a1eab296b42be772b532e39 done partly, i am working out how to make it clean. i also realised that this technique potentially could be used to *auto-generate* the required unit test values but it may be better explicitly spelled out?
(In reply to Luke Kenneth Casson Leighton from comment #13) > (In reply to Luke Kenneth Casson Leighton from comment #12) > > > therefore what i am going to do is do a... what is it called... > > Context Manager that allows full input/output capture, in a clean > > and clear way. > > https://git.libre-soc.org/?p=openpower-isa.git;a=commitdiff; > h=6479aa6ed404829f6a1eab296b42be772b532e39 > > done partly, i am working out how to make it clean. i also realised > that this technique potentially could be used to *auto-generate* > the required unit test values but it may be better explicitly spelled > out? Just had the chance to look at this, brilliant. I'll try to start and finish the test suite that generates random messages and keys and tests against the poly1305-donna C implementation tonight. Speedrun time to catch up :) I'll push whatever is ready.
(In reply to Sadoon Albader from comment #14) > Just had the chance to look at this, brilliant. bit of a hack but the context manager helps a lot also perhaps useful (at some point) is to capture the *instance* arguments so that those link back to the input that *caused* whatever intermediary variables to have their values, such that you can create a *top level* unit test that happens to reproduce those exact intermediaries. > I'll try to start and finish the test suite that generates random messages > and keys and tests against the poly1305-donna C implementation tonight. ah it is much simpler (like... 2 minutes vs 1 hour simpler) to test against the *python* poly1305.py the advantage is that the python poly1305.py uses arbitrary-length precision math and is therefore bloody obvious not to have any carry rollover errors.
(In reply to Luke Kenneth Casson Leighton from comment #15) > ah it is much simpler (like... 2 minutes vs 1 hour simpler) to test > against the *python* poly1305.py > > the advantage is that the python poly1305.py uses arbitrary-length > precision math and is therefore bloody obvious not to have any carry > rollover errors. I seem to have misunderstood then, aren't we supposed to test against both the python and C implementations, since the C one is being used as the source that we ported to python and then porting to SVP64?
At any rate the C unit test is done, output is conveniently in CSV format (lol) This means we can use pure python to convert the 3 arrays, now figuring out the correct output formatting needed before pushing. EDIT: I don't have permissions to push to openpower-isa, could someone please add me?
(In reply to Sadoon Albader from comment #16) > I seem to have misunderstood then, aren't we supposed to test against both > the python and C implementations, since the C one is being used as the > source that we ported to python and then porting to SVP64? yes? :) i tend to think in terms of "shortest path"... (In reply to Sadoon Albader from comment #17) > At any rate the C unit test is done, output is conveniently in CSV format > (lol) niiice. see csvreader although with open(fname) as f: map(lambda x : x.split(","), f.readlines()) does the same job in 2 lines... > This means we can use pure python to convert the 3 arrays, now figuring out > the correct output formatting needed before pushing. > > EDIT: I don't have permissions to push to openpower-isa, could someone > please add me? eep 1 sec.. done
Confirmed working but the python edits are dirty, cleaning up and pushing in a bit.
Pushed to master, only added new files so no point in creating new branch this time around. https://git.libre-soc.org/?p=openpower-isa.git;a=commit;h=200ebca86abc2f5535cf02fc64f1b379a9fede5f It's 5 commits but this is the last one as of today. Woohoo!
strategy for generating data https://git.libre-soc.org/?p=openpower-isa.git;a=blob;f=src/openpower/test/bigint/powmod.py;h=8cdeeabdbf38d58a2a0c667bb987eabaa373e491;hb=HEAD#l284
sadoon shriya this is worth studying what jacob has done here. https://bugs.libre-soc.org/show_bug.cgi?id=1044#c72 it is also how i recommended to tackle this one, through an incremental extremely patient "ONLY a few assembler lines at a time" approach.