I am trying to write a SHA-256 hash function for practice. In the wikipedia stands that the initial hash values are given by the fractional parts of the square roots of the first 8 primes 2..19. Now i am trying to calculate them. What i have done so far:
#include <vector>
#include <cstdint>
#include <cmath>
#include <cstdio>
// fill primes with all prime values between min and max value
int getPrimes(uint32_t min, uint32_t max, std::vector<uint32_t>* primes)
{
if (min < 1) min = 1; // primes can only be >= 1
if (min > max) return 0; // max has to be larger than min
for (uint32_t value = min; value <= max; value++)
{
uint32_t tmp;
for (tmp = 2; tmp <= sqrt(value); tmp++) // start to check with 2, because 1 is always going to work
{
if (value % tmp == 0)
{
break;
}
}
if (tmp > sqrt(value)) primes->push_back(value); // if no other integer divisor is found, add number to vector
}
return 0;
}
int main()
{
std::vector<uint32_t> primes;
getPrimes(2, 20, &primes); // fills vector with all prime values between 2 and 20
double tmp = sqrt(primes[0]); // get square root, returns double
printf("value %f\n", tmp); // debug
printf("size of double %i\n", sizeof(double)); // get representation byte size
double * tmpOffset = &tmp; // get value offset
unsigned char * tmpChar = (unsigned char*)tmpOffset; // convert to char pointer
printf("address of variable %i\n", &tmp); // debug
printf("raw values\n1:%X\n2:%X\n3:%X\n4:%X\n5:%X\n6:%X\n7:%X\n8:%X\n",
(uint8_t)tmpChar[0], (uint8_t)tmpChar[1], (uint8_t)tmpChar[2], (uint8_t)tmpChar[3],
(uint8_t)tmpChar[4], (uint8_t)tmpChar[5], (uint8_t)tmpChar[6], (uint8_t)tmpChar[7]);
return 0;
}
This returns the first 8 primes, calculates the square root of 2 and fetches directly from the memory location where it is stored the actual byte values:
value 1.414214
size of double 8
address of variable 6881016
raw values
1:CD
2:3B
3:7F
4:66
5:9E
6:A0
7:F6
8:3F
Compared to the value given in the wikipedia article 0x6a09e667 it looks awfully wrong what i am doing here. Is there a remapping happening or how excatly is the binary reresentation of a double?Can someone point me in the right direction how to correctly calculate the fractional part in hex?
Edit: Thanks for your help! It is not pretty but does work for now.
printf("raw fractional part:\n0x%02X %02X %02X %02X %02X %02X %02X\n",
(uint8_t)(0xf & tmpChar[6]), (uint8_t)tmpChar[5], (uint8_t)tmpChar[4], (uint8_t)tmpChar[3],
(uint8_t)tmpChar[2], (uint8_t)tmpChar[1], (uint8_t)tmpChar[0]);
uint32_t fracPart = (0xf & tmpChar[6]);
fracPart <<= 8;
fracPart |= tmpChar[5];
fracPart <<= 8;
fracPart |= tmpChar[4] ;
fracPart <<= 8;
fracPart |= tmpChar[3];
fracPart <<= 4;
fracPart |= (0xf0 & tmpChar[2]) >> 4;
printf("fractional part: %X\n", fracPart);
Edit2 A little bit of a nicer implementation:
uint32_t fracPart2 = *(uint32_t*)((char*)&tmp + 3); // point to fractional part - 4 bit
fracPart2 <<= 4; // shift to correct value
fracPart2 |= (0xf0 & *((char*)&tmp + 2)) >> 4; // append last 4 bit
printf("beautiful fractional part: %X\n", fracPart2);
This solution is highly platform dependant and in a second approach i am going for something like in the link of comment 2.
Edit3
So this is my final solution, which does not depend on the internal representation of a double and calculates the fraction just using math.
uint32_t getFractionalPart(double value)
{
uint32_t retValue = 0;
for (uint8_t i = 0; i < 8; i++)
{
value = value - floor(value);
retValue <<= 4;
value *= 16;
retValue += floor(value);
}
return retValue;
}
One thing to keep in mind is that the double here is 64 bits. If you look at the IEEE representation of doubles at the below link, it has 1 sign bit, 11 exponent bits and the remaining are the precision bits.
Now when you look at the output you've gotten, take a look at the nibbles I've put in quotes, do they look familiar? The reason the number is backwards is because of endianness. The 12th bit is where the fractional part is starting in this case, and then it moves backwards.
1:CD
2:3B
3:'7'F
4:'66'
5:'9E'
6:'A0'
7:F'6'
8:3F
or
8:3F
7:F'6'
6:'A0'
5:'9E'
4:'66'
3:'7'F
2:3B
1:CD
https://en.wikipedia.org/wiki/Double-precision_floating-point_format