3.27 OpenMP.
(lower addresses)
[amsg(): 100 bytes]
[RA] <- current SP
[two amsg() arguments]
[interim() stuff, incl. 8000 bytes]
[something else]
[main() local variables]
(upper addresses)
Now the stack state at the moment when interim() returns control tomain():
(lower addresses)
[amsg(): 100 bytes]
[RA]
[two amsg() arguments]
[interim() stuff, incl. 8000 bytes]
[something else] <- current SP
[main() local variables]
(upper addresses)
So whenmain()callsprintf(), it uses stack at the place where interim()’s buffer was allocated, and
doesn’tzap100byteswitherrormessageinside, because8000bytes(ormaybemuchless)isjustenough
for everythingprintf()and other descending functions do!
It may also work if there are many functions between, like:main()→f1()→f2()→f3() ...→amsg(), and
then the result of amsg() is used inmain(). The distance betweenSPinmain()and address ofbuf[]
must be long enough,
This is why bugs like these are dangerous: sometimes your code works (and bug can be hiding unnoticed),
sometimes not. Bugs like these are jokingly called heisenbugs or schrödinbugs^55.
3.27 OpenMP
OpenMP is one of the simplest ways to parallelize simple algorithms.
As an example, let’s try to build a program to compute a cryptographicnonce.
In my simplistic example, thenonceis a number added to the plain unencrypted text in order to produce
a hash with some specific features.
For example, at some step, the Bitcoin protocol requires to find suchnonceso the resulting hash contains
a specific number of consecutive zeros. This is also called “proof of work”^56 (i.e., the system proves that
it did some intensive calculations and spent some time for it).
My example is not related to Bitcoin in any way, it will try to add numbers to the “hello, world!” string in
order to find such number that when “hello, world!
will contain at least 3 zero bytes.
Let’s limit our brute-force to the interval in 0..INT32_MAX-1 (i.e.,0x7FFFFFFEor 2147483646).
The algorithm is pretty straightforward:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include "sha512.h"
int found=0;
int32_t checked=0;
int32_t* __min;
(^55) https://en.wikipedia.org/wiki/Heisenbug
(^56) wikipedia