Re: bitset<32> and bitset<64> efficiency
On Wednesday, 28 November 2012 08:58:59 UTC, Ninds wrote:
Hi,
I would like to know whether using bitset<32> for bit operations on a 32b=
it machine would generally be as efficient as using a 32bit int.
Moreover, if the answer is yes would it also hold for bitset<64> and 64bi=
t int on a 64 bit arch.
I realise the standard says nothing about the implementation so there is =
no definitive answer but what is 'likely' to be the case ?
Thanks
N
Hi,
Thanks for the replies .. but I am afraid I am none the wiser. To put my qu=
estion in context:
I wanted to write a small concise bit of code to compute the SHA256 hash th=
at would be portable (hence free of asm) and isolated. I realised from the =
outset that with these constraints it wouldn't be the speediest kid on the =
block but I didn't want it to be ridiculously inefficient either. I couldn'=
t think of a cleaner solution that using std::bitset this way I didn't need=
to concern myself with the underlying architecture and at the same time I =
would be working with the language rather than against it.
I am however curious as to why rotations methods are not implemented for bi=
tset.
I now have a prototype which seems to work fine implemented from the pseudo=
code on Wikipedia.
#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<iomanip>
#include<bitset>
const unsigned int h[8] ={
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0=
x1f83d9ab, 0x5be0cd19};
const unsigned int k[64] ={
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, =
0x923f82a4, 0xab1c5ed5,
0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, =
0x9bdc06a7, 0xc19bf174,
0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, =
0x5cb0a9dc, 0x76f988da,
0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, =
0x06ca6351, 0x14292967,
0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, =
0x81c2c92e, 0x92722c85,
0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, =
0xf40e3585, 0x106aa070,
0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, =
0x5b9cca4f, 0x682e6ff3,
0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, =
0xbef9a3f7, 0xc67178f2};
template<size_t M>
struct bit_op
{
template<size_t N>
static std::bitset<N> &RoL(std::bitset<N> &data)
{
std::bitset<N> leftShift = data<<M;
data>>=(N-M);
data |= leftShift;
return data;
}
template<size_t N>
static std::bitset<N> &RoR(std::bitset<N> &data)
{
std::bitset<N> rightShift = data>>M;
data<<=(N-M);
data |= rightShift;
return data;
}
template<size_t N>
static std::bitset<N> roL(const std::bitset<N> &data)
{
std::bitset<N> temp(data);
return RoL(temp);
}
template<size_t N>
static std::bitset<N> roR(const std::bitset<N> &data)
{
std::bitset<N> temp(data);
return RoR(temp);
}
};
void clean(std::vector<std::bitset<32> > &chunk)
{
for(int i(0); i< chunk.size(); ++i)
{
chunk[i].reset();
}
}
int getChunck(std::istream &theStream, std::vector<std::bitset<32> > &chunk=
)
{
clean(chunk);
int Count =0;
while(!theStream.eof() && Count < 512/8)
{
char c=0;
theStream.get(c);
if(c!=0)
{
std::bitset<32> data = ((unsigned long )c);
data<<=((3-(Count & 3))*8);
chunk[(Count>>2)] |= data;
++Count;
}
}
return Count;
}
void process(std::vector<std::bitset<32> > &w,std::vector<std::bitset<32> >=
&hvec)
{
for (int i(16); i< 64; ++i)
{
std::bitset<32> s0 = (bit_op<7>::roR(w[i-15])) ^ (bit_op<18>::roR(w[i-1=
5])) ^ (w[i-15]>>3);
std::bitset<32> s1 = (bit_op<17>::roR(w[i-2])) ^ (bit_op<19>::roR(w[i-2=
])) ^ (w[i-2]>>10);
w[i] = std::bitset<32>(w[i-16].to_ulong() + s0.to_ulong() + w[i-7].to_u=
long() + s1.to_ulong());
}
std::bitset<32> a = hvec[0];
std::bitset<32> b = hvec[1];
std::bitset<32> c = hvec[2];
std::bitset<32> d = hvec[3];
std::bitset<32> e = hvec[4];
std::bitset<32> f = hvec[5];
std::bitset<32> g = hvec[6];
std::bitset<32> h = hvec[7];
for(int i(0); i< 64; ++i)
{
std::bitset<32> S0 = (bit_op<2>::roR(a)) ^ (bit_op<13>::roR(a)) ^ (bit_=
op<22>::roR(a));
std::bitset<32> maj = (a & b) ^ (a & c) ^ (b & c);
std::bitset<32> t2(S0.to_ulong() + maj.to_ulong());
std::bitset<32> S1 = (bit_op<6>::roR(e)) ^ (bit_op<11>::roR(e)) ^ (bit_=
op<25>::roR(e));
std::bitset<32> ch = (e & f) ^ ((~e) & g);
std::bitset<32> t1 = h.to_ulong() + S1.to_ulong() + ch.to_ulong() + k=
[i] + w[i].to_ulong() ;
h = g;
g = f;
f = e;
e = d.to_ulong() + t1.to_ulong();
d = c;
c = b;
b = a;
a = t1.to_ulong() + t2.to_ulong() ;
}
hvec[0] = hvec[0].to_ulong() + a.to_ulong();
hvec[1] = hvec[1].to_ulong() + b.to_ulong();
hvec[2] = hvec[2].to_ulong() + c.to_ulong();
hvec[3] = hvec[3].to_ulong() + d.to_ulong();
hvec[4] = hvec[4].to_ulong() + e.to_ulong();
hvec[5] = hvec[5].to_ulong() + f.to_ulong();
hvec[6] = hvec[6].to_ulong() + g.to_ulong();
hvec[7] = hvec[7].to_ulong() + h.to_ulong();
}
int main(int argc, char* argv[])
{
if(argc<2)
{
std::cout <<"Need a string to hash";
return -1;
}
std::string theTestString = argv[1] ;
for(int i(2); i< argc; ++i)
{
theTestString+=" ";
theTestString+= argv[i];
}
std::istringstream theStream(theTestString);
std::vector<std::bitset<32> > hvec(8);
for(int i(0); i< 8; ++i)
{
hvec[i] = h[i];
}
std::vector<std::bitset<32> > chunk(64);
bool finished = false;
unsigned int byteCount = 0;
unsigned int chunkCount = 0;
int count =0;
while((count=getChunck(theStream,chunk))==64)
{
process(chunk,hvec);
byteCount+=count;
}
byteCount+=count;
int chunkIndex = 0;
int byteIndex = 0;
if(count !=0)
{
chunkIndex = count/4;
byteIndex = count - (count/4)*4;
}
chunk[chunkIndex]|= (1<<((4-byteIndex)*8-1));
std::bitset<64> length(byteCount);
length<<=3;
unsigned long lower = (length & ((std::bitset<64>().set())>>32)).to_ulo=
ng();
unsigned long upper = (length & ((std::bitset<64>().set())<<32)).to_ulo=
ng();
if(chunkIndex > 13)
{
process(chunk,hvec);
clean(chunk);
}
chunk[14]|=upper;
chunk[15]|=lower;
process(chunk,hvec);
std::vector<unsigned char> theComputed;
for(int i(0); i< 8; ++i)
{
for(int j(0); j<4; ++j)
{
std::cout << std::hex << ((hvec[i]>>((3-j)*8))&std::bitset<32>(255)).to=
_ulong() <<"-";
}
}
}