SHA256 for all Ataris

[JeanMars]

Hi all,

When debuging VISION, I needed to compute some basic hash to know if a given buffer has been changed; I made something pretty simple but by curiosity I looked if there is a SHA256 implementation on Ataris.
The ones I've seen, like polarSSL, looked too much 'C' oriented for me, I expected some 68k implementation I did not find for ST.
However, I found an Amiga implementation by Leffmann with a nice assembly code for SHA256 calculations.
So I ported it to ST (Assembly/PureC) with just some basic accomodations.

You can find it at https://github.com/JeanMars/SHA256

Have fun!
Jean

[ThorstenOtto]

Nice. Did you compare it to a C version, or some other language implementation?

[JeanMars]

No, I did not take time to investigate this; just considering the way assembly code looks to make optimum usage of registers and code compacity, I would expect some pretty nice speed benefit compared to 'C' codes I've seen (openssl, polarSSL).
If someone has some benchmark with these, that would be interesting to compare.

[ThorstenOtto]

I would expect some pretty nice speed benefit compared to 'C' codes

I did some quick tests using the builtin performance tests, and these are the results (all test were run with Hatari, configured for ST/8Mhz/68000):

Your assembly routines, compiled by Pure-C:

Code: Select all

SHA256 on 1KB took 5ms (200KB/s)
SHA256 on 2KB took 10ms (200KB/s)
SHA256 on 4KB took 20ms (200KB/s)
SHA256 on 8KB took 40ms (200KB/s)
SHA256 on 16KB took 75ms (213KB/s)
SHA256 on 32KB took 155ms (206KB/s)
SHA256 on 64KB took 310ms (206KB/s)
SHA256 on 128KB took 615ms (208KB/s)
SHA256 on 256KB took 1230ms (208KB/s)
SHA256 on 512KB took 2460ms (208KB/s)

A plain C version, also compiled by Pure-C:

Code: Select all

SHA256 on 1KB took 10ms (100KB/s)
SHA256 on 2KB took 15ms (133KB/s)
SHA256 on 4KB took 35ms (114KB/s)
SHA256 on 8KB took 65ms (123KB/s)
SHA256 on 16KB took 130ms (123KB/s)
SHA256 on 32KB took 260ms (123KB/s)
SHA256 on 64KB took 520ms (123KB/s)
SHA256 on 128KB took 1040ms (123KB/s)
SHA256 on 256KB took 2085ms (122KB/s)

The same plain C version, compiled by gcc 4.6.4:

Code: Select all

SHA256 on 1KB took 5ms (200KB/s)
SHA256 on 2KB took 15ms (133KB/s)
SHA256 on 4KB took 25ms (160KB/s)
SHA256 on 8KB took 50ms (160KB/s)
SHA256 on 16KB took 100ms (160KB/s)
SHA256 on 32KB took 200ms (160KB/s)
SHA256 on 64KB took 395ms (162KB/s)
SHA256 on 128KB took 790ms (162KB/s)
SHA256 on 256KB took 1585ms (161KB/s)
SHA256 on 512KB took 3160ms (162KB/s)

The same plain C version, compiled by gcc 8.2:

Code: Select all

SHA256 on 1KB took 5ms (200KB/s)
SHA256 on 2KB took 10ms (200KB/s)
SHA256 on 4KB took 20ms (200KB/s)
SHA256 on 8KB took 45ms (177KB/s)
SHA256 on 16KB took 90ms (177KB/s)
SHA256 on 32KB took 180ms (177KB/s)
SHA256 on 64KB took 350ms (182KB/s)
SHA256 on 128KB took 710ms (180KB/s)
SHA256 on 256KB took 1410ms (181KB/s)
SHA256 on 512KB took 2820ms (181KB/s)

If you compare the last one to your assembler version, that is 2820 vs. 2460 ms for the largest block, which is about 12-15% faster. Sorry to disappoint you, but i wouldn't call that really spectacular, given the non-portability of an assembler version, and the effort to maintain it.

[ThorstenOtto]

And one more test: i tried to be clever, by providing a small inline assembly function for the RORu32() function, until i realized that gcc is smart enough to do that itself from the C-code. When i disable that, i get:

Code: Select all

SHA256 on 1KB took 5ms (200KB/s)
SHA256 on 2KB took 10ms (200KB/s)
SHA256 on 4KB took 15ms (266KB/s)
SHA256 on 8KB took 35ms (228KB/s)
SHA256 on 16KB took 75ms (213KB/s)
SHA256 on 32KB took 150ms (213KB/s)
SHA256 on 64KB took 300ms (213KB/s)
SHA256 on 128KB took 600ms (213KB/s)
SHA256 on 256KB took 1200ms (213KB/s)
SHA256 on 512KB took 2395ms (213KB/s)

Which is even minimal faster than the assembler version. Conclusion: it's not always smart to use assembler, a better algorithm might achieve the same results.

[czietz]

Do you mind posting (or linking to) the SHA256 C version that you used for your tests?

[ThorstenOtto]

No, of course not

The C version is in sh2.c. i just added the last 2 functions to provide the same interface as he used.

BTW: when you need that only to get a checksum, other algorithms like MD5 might be more appropriate.

Edit: attachment removed. See new version in http://atari-forum.com/viewtopic.php?f= ... 25#p373980

[czietz]

I still wonder how you managed to get this impressive performance from an 68000 at 8 MHz. When I take the code you posted, compile it with your version of gcc 8.2.1 (with your Makefile, i.e. -O2) and run it on an ST with 8 MHz, I see "32KB took 2965ms (10KB/s)". With the numbers you posted, you claim to have processed 218112 bytes in 8000000 clock cycles, i.e. 37 cycles per byte. I find this hard to believe for an algorithm of such a complexity as SHA256, considering that for example a single ROR.L by 13 bits (like it occurs in SHA256) takes 34 cycles on a 68000.

[ThorstenOtto]

Hm, maybe some setting in Hatari was wrong then for benchmarks. But at least it was the same for all tests. maybe someone can run test tests again on real hardware?

[czietz]

The assembler version comes out "32KB took 2465ms (12KB/s)", ca. 20% faster. It still shows that gcc 8 is quite good at optimizing C code.

[ThorstenOtto]

And it also shows that things like sha256 are not meant to be run on 68k@8Mhz

[lp]

And it also shows that things like sha256 are not meant to be run on 68k@8Mhz

To be fair, seeing how it was ported, probably not meant for 68k@7.1Mhz either.

[JeanMars]

Hi,

Thorsten, you ruined my day
wow I'm very impressed by how much efficient is code generated by gcc; honestly I did not expect a 'C' code to be faster than 68k one in this context.
Typically I expected a about a 1/2 ratio, like code generated by PureC.
I don't think 68020 instructions would help, but your gcc code was generated for pure 68000 right?
If some 68k assembly guru is willing to optimize this assembly code, I am curious to know what a good 68k coder can achieve versus a very good compiler such as gcc 8.2.

For this context, MD5 would be a better choice but the one I did is even much simpler; cracking hash algoithms is not a concern here BTW, MD5, SHA1 are cracked, SHA256 still resists.

Cheers,
Jean

[ThorstenOtto]

Hi,
Thorsten, you ruined my day

Sorry

wow I'm very impressed by how much efficient is code generated by gcc; honestly I did not expect a 'C' code to be faster than 68k one in this context.

Maybe not real faster, Christian pointed out that numbers can't be correct. But it's not much slower.

Typically I expected a about a 1/2 ratio, like code generated by PureC.

Pure-C has a problem here, since it does not have real inline functions. If you look at the code you will notice that i inlined the ROR function there. However, although that trick speeds up the code, it is still treated as a function call, meaning that Pure-C assumes it may destroy d0-d2/a0-a1, which makes those registers unavailable in the function that calls it.

I don't think 68020 instructions would help, but your gcc code was generated for pure 68000 right?

Yes, i did my tests for 68000. I don't think that this would help much, at least i can't think of any instruction. But of course, a 68030 is much faster in doing all those shifts.

If some 68k assembly guru is willing to optimize this assembly code, I am curious to know what a good 68k coder can achieve versus a very good compiler such as gcc 8.2.

That will be tough. The implementation i used already has everything "unrolled", and does not use a table like your assembler version.

BTW, MD5, SHA1 are cracked, SHA256 still resists.

But you don't won't to encrypt the data, just get a checksum. MD5 is definitely better for this purpose, although even that might too slow on 68k. Maybe CRC32 will do.

[JeanMars]

Hi,

That will be tough. The implementation i used already has everything "unrolled", and does not use a table like your assembler version.
.

I don't get your point here. Do you refer to .constants label in assembly file? To me it should be faster accessing these by an address register (a5) than using immediate adressing like it looks in 'C' code (no idea what gcc does BTW).
BTW, I'm not skilled for this but I'm pretty sure someone like Leonard could drastically improve this 68k routine.

But you don't won't to encrypt the data, just get a checksum. MD5 is definitely better for this purpose, although even that might too slow on 68k. Maybe CRC32 will do.

Don't get me wrong; for my usage (Debug VISION), what I used is the simplest CRC you can imagine; this is very enough for my debugging, it just lighted me the idea of having in 68k the most robust hash algorithm which is SHA256.
BTW SHA256 does not encrypt, it is used to check integrity, mainly in a context of cryptography I agree.

Cheers,
Jean

[JeanMars]

Sorry, forgot to ask: I'd like to have a look into gcc for Atari, any resource to start from?

[ThorstenOtto]

(no idea what gcc does BTW).

You can take a look at the generated assembly code (for just the function that does the actual transformations) here. The constants are used directly in the code, not fetched up from a table.

I'd like to have a look into gcc for Atari, any resource to start from?

For native compilers, see https://github.com/freemint/m68k-atari- ... 7_3_0-mint . Cross-compilers are available at http://tho-otto.de/crossmint.php. For the native compilers, you will need MiNT.

[Eero Tamminen]

Note: while code compiled with GCC + MiNTlib is often much faster than one compiled with Pure-C, resulting binaries can also be much larger.

While GCC generated code can often be somewhat larger due to automatic inlining & unrolling that GCC optimizations passes do, the main reason for the larger binaries is the C-library, the unix / compatibility / error handling etc stuff, and their dependencies to other code within in MiNTlib.

Latter is especially visible in simpler program. Just doing file access with FILE* functions, or text output with printf style functions brings in stuff like floating point <-> string conversions, file system timezone handling (which is completely useless on plain TOS)...

If you want small binaries, either use TOS functions directly, or a replacement C-library that's missing support for the MiNT/Unix stuff.

[JeanMars]

Hi,

thanks for links. Yes I'm aware that gcc binaries are much larger than PureC ones because of posix, just wanting to give gcc a try for some tests or additional tool dev.
To me, main lack is not being able to use a debugger with gcc. PureD is so nice for that.

Wil first go for native compilation I guess.

Cheers,
Jean

[JeanMars]

Hi,

just updated https://github.com/JeanMars/SHA256 with GCC support and makefile for 68000/68000/ColdFire(untested)
Results are pretty weird to me; gcc does it better even against human assembly code, purec looks far away which is surprising.

Cheers,
Jean

[ThorstenOtto]

purec looks far away which is surprising.

Not really. For code like this, gcc does a lot of global optimizations that Pure-C isn't aware of. One example being the RORu32 macro (or inline function) which is compile into a single ror instruction. Pure-C would have compiled all the separate shifts. Another thing is that gcc is much better in eliminating common sub-expressions.

Most of the speed Pure-C compiled programs gain compared to other compilers is due to the passing of parameters in registers, which saves a lot of memory accesses.

[Eero Tamminen]

To me, main lack is not being able to use a debugger with gcc. PureD is so nice for that.

Doesn't GDB work with GCC compiled binaries for source level debugging, at least under MiNT? (At least old GDB / GCC versions did.)

If one has (MiNT) network connection, one might be able to run gdbserver on Atari and GDB GUI, such as DDD on PC:
* https://www.gnu.org/software/ddd/
* https://stackoverflow.com/questions/150 ... -gdbserver

For assembly level debugging of GCC compiled code, one can use Hatari debugger. Nowadays it loads debug symbols from the binary automatically (Thorsten contributed GCC a.out symbol format support for it).

[Eero Tamminen]

Btw. older GCC versions supported also the old DRI symbol format, which should work with most Atari debuggers. Getting that requires "-Wl,--traditional-format" GCC linker flag.

[JeanMars]

Interesting...
I should have a look into this, but first setup my Aranym/Mint on network, so far my attempts failed.

[ThorstenOtto]

[
Doesn't GDB work with GCC compiled binaries for source level debugging, at least under MiNT? (At least old GDB / GCC versions did.)

Unfortunately, no.

If one has (MiNT) network connection, one might be able to run gdbserver on Atari and GDB GUI, such as DDD on PC:

I didn't try, but i would bet that this does not work either. Problem is that the interface from gdb to mint (querying the process state, stopping it etc) is broken. gdbserver will suffer from the same problem.

For assembly level debugging of GCC compiled code, one can use Hatari debugger.

Good luck in trying to do this with gcc compiled code. Some functions you try debug won't even exist because they are inlined.

Thorsten contributed GCC a.out symbol format support for it).

Yes, but this only applies to visible symbols. Source debug information is not handled by plain a.out format.