#include "Bitvec.h" | |
#include "Random.h" | |
#include <assert.h> | |
#include <stdio.h> | |
#ifndef DEBUG | |
#undef assert | |
void assert ( bool ) | |
{ | |
} | |
#endif | |
//---------------------------------------------------------------------------- | |
void printbits ( void * blob, int len ) | |
{ | |
uint8_t * data = (uint8_t*)blob; | |
printf("["); | |
for(int i = 0; i < len; i++) | |
{ | |
unsigned char byte = data[i]; | |
int hi = (byte >> 4); | |
int lo = (byte & 0xF); | |
if(hi) printf("%01x",hi); | |
else printf("."); | |
if(lo) printf("%01x",lo); | |
else printf("."); | |
if(i != len-1) printf(" "); | |
} | |
printf("]"); | |
} | |
void printbits2 ( uint8_t * k, int nbytes ) | |
{ | |
printf("["); | |
for(int i = nbytes-1; i >= 0; i--) | |
{ | |
uint8_t b = k[i]; | |
for(int j = 7; j >= 0; j--) | |
{ | |
uint8_t c = (b & (1 << j)) ? '#' : ' '; | |
putc(c,stdout); | |
} | |
} | |
printf("]"); | |
} | |
void printhex32 ( void * blob, int len ) | |
{ | |
assert((len & 3) == 0); | |
uint32_t * d = (uint32_t*)blob; | |
printf("{ "); | |
for(int i = 0; i < len/4; i++) | |
{ | |
printf("0x%08x, ",d[i]); | |
} | |
printf("}"); | |
} | |
//----------------------------------------------------------------------------- | |
// Bit-level manipulation | |
// These are from the "Bit Twiddling Hacks" webpage | |
uint32_t popcount ( uint32_t v ) | |
{ | |
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary | |
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp | |
uint32_t c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count | |
return c; | |
} | |
uint32_t popcount128 ( uint32_t * v ) | |
{ | |
uint32_t c = popcount(v[0]); | |
c += popcount(v[1]); | |
c += popcount(v[2]); | |
c += popcount(v[3]); | |
return c; | |
} | |
uint32_t parity ( uint32_t v ) | |
{ | |
v ^= v >> 16; | |
v ^= v >> 8; | |
v ^= v >> 4; | |
v &= 0xf; | |
return (0x6996 >> v) & 1; | |
} | |
uint64_t parity ( uint64_t v ) | |
{ | |
v ^= v >> 32; | |
v ^= v >> 16; | |
v ^= v >> 8; | |
v ^= v >> 4; | |
v &= 0xf; | |
return (0x6996 >> v) & 1; | |
} | |
//----------------------------------------------------------------------------- | |
uint32_t getbit ( void * block, int len, uint32_t bit ) | |
{ | |
uint8_t * b = (uint8_t*)block; | |
int byte = bit >> 3; | |
bit = bit & 0x7; | |
if(byte < len) return (b[byte] >> bit) & 1; | |
return 0; | |
} | |
uint32_t getbit_wrap ( void * block, int len, uint32_t bit ) | |
{ | |
uint8_t * b = (uint8_t*)block; | |
int byte = bit >> 3; | |
bit = bit & 0x7; | |
byte %= len; | |
return (b[byte] >> bit) & 1; | |
} | |
void setbit ( void * block, int len, uint32_t bit ) | |
{ | |
uint8_t * b = (uint8_t*)block; | |
int byte = bit >> 3; | |
bit = bit & 0x7; | |
if(byte < len) b[byte] |= (1 << bit); | |
} | |
void setbit ( void * block, int len, uint32_t bit, uint32_t val ) | |
{ | |
val ? setbit(block,len,bit) : clearbit(block,len,bit); | |
} | |
void clearbit ( void * block, int len, uint32_t bit ) | |
{ | |
uint8_t * b = (uint8_t*)block; | |
int byte = bit >> 3; | |
bit = bit & 0x7; | |
if(byte < len) b[byte] &= ~(1 << bit); | |
} | |
void flipbit ( void * block, int len, uint32_t bit ) | |
{ | |
uint8_t * b = (uint8_t*)block; | |
int byte = bit >> 3; | |
bit = bit & 0x7; | |
if(byte < len) b[byte] ^= (1 << bit); | |
} | |
//----------------------------------------------------------------------------- | |
void lshift1 ( void * blob, int len, int c ) | |
{ | |
int nbits = len*8; | |
for(int i = nbits-1; i >= 0; i--) | |
{ | |
setbit(blob,len,i,getbit(blob,len,i-c)); | |
} | |
} | |
void lshift8 ( void * blob, int nbytes, int c ) | |
{ | |
uint8_t * k = (uint8_t*)blob; | |
if(c == 0) return; | |
int b = c >> 3; | |
c &= 7; | |
for(int i = nbytes-1; i >= b; i--) | |
{ | |
k[i] = k[i-b]; | |
} | |
for(int i = b-1; i >= 0; i--) | |
{ | |
k[i] = 0; | |
} | |
if(c == 0) return; | |
for(int i = nbytes-1; i >= 0; i--) | |
{ | |
uint8_t a = k[i]; | |
uint8_t b = (i == 0) ? 0 : k[i-1]; | |
k[i] = (a << c) | (b >> (8-c)); | |
} | |
} | |
void lshift32 ( void * blob, int len, int c ) | |
{ | |
assert((len & 3) == 0); | |
int nbytes = len; | |
int ndwords = nbytes / 4; | |
uint32_t * k = (uint32_t*)blob; | |
if(c == 0) return; | |
//---------- | |
int b = c / 32; | |
c &= (32-1); | |
for(int i = ndwords-1; i >= b; i--) | |
{ | |
k[i] = k[i-b]; | |
} | |
for(int i = b-1; i >= 0; i--) | |
{ | |
k[i] = 0; | |
} | |
if(c == 0) return; | |
for(int i = ndwords-1; i >= 0; i--) | |
{ | |
uint32_t a = k[i]; | |
uint32_t b = (i == 0) ? 0 : k[i-1]; | |
k[i] = (a << c) | (b >> (32-c)); | |
} | |
} | |
//----------------------------------------------------------------------------- | |
void rshift1 ( void * blob, int len, int c ) | |
{ | |
int nbits = len*8; | |
for(int i = 0; i < nbits; i++) | |
{ | |
setbit(blob,len,i,getbit(blob,len,i+c)); | |
} | |
} | |
void rshift8 ( void * blob, int nbytes, int c ) | |
{ | |
uint8_t * k = (uint8_t*)blob; | |
if(c == 0) return; | |
int b = c >> 3; | |
c &= 7; | |
for(int i = 0; i < nbytes-b; i++) | |
{ | |
k[i] = k[i+b]; | |
} | |
for(int i = nbytes-b; i < nbytes; i++) | |
{ | |
k[i] = 0; | |
} | |
if(c == 0) return; | |
for(int i = 0; i < nbytes; i++) | |
{ | |
uint8_t a = (i == nbytes-1) ? 0 : k[i+1]; | |
uint8_t b = k[i]; | |
k[i] = (a << (8-c) ) | (b >> c); | |
} | |
} | |
void rshift32 ( void * blob, int len, int c ) | |
{ | |
assert((len & 3) == 0); | |
int nbytes = len; | |
int ndwords = nbytes / 4; | |
uint32_t * k = (uint32_t*)blob; | |
//---------- | |
if(c == 0) return; | |
int b = c / 32; | |
c &= (32-1); | |
for(int i = 0; i < ndwords-b; i++) | |
{ | |
k[i] = k[i+b]; | |
} | |
for(int i = ndwords-b; i < ndwords; i++) | |
{ | |
k[i] = 0; | |
} | |
if(c == 0) return; | |
for(int i = 0; i < ndwords; i++) | |
{ | |
uint32_t a = (i == ndwords-1) ? 0 : k[i+1]; | |
uint32_t b = k[i]; | |
k[i] = (a << (32-c) ) | (b >> c); | |
} | |
} | |
//----------------------------------------------------------------------------- | |
void lrot1 ( void * blob, int len, int c ) | |
{ | |
int nbits = len * 8; | |
for(int i = 0; i < c; i++) | |
{ | |
uint32_t bit = getbit(blob,len,nbits-1); | |
lshift1(blob,len,1); | |
setbit(blob,len,0,bit); | |
} | |
} | |
void lrot8 ( void * blob, int len, int c ) | |
{ | |
int nbytes = len; | |
uint8_t * k = (uint8_t*)blob; | |
if(c == 0) return; | |
//---------- | |
int b = c / 8; | |
c &= (8-1); | |
for(int j = 0; j < b; j++) | |
{ | |
uint8_t t = k[nbytes-1]; | |
for(int i = nbytes-1; i > 0; i--) | |
{ | |
k[i] = k[i-1]; | |
} | |
k[0] = t; | |
} | |
uint8_t t = k[nbytes-1]; | |
if(c == 0) return; | |
for(int i = nbytes-1; i >= 0; i--) | |
{ | |
uint8_t a = k[i]; | |
uint8_t b = (i == 0) ? t : k[i-1]; | |
k[i] = (a << c) | (b >> (8-c)); | |
} | |
} | |
void lrot32 ( void * blob, int len, int c ) | |
{ | |
assert((len & 3) == 0); | |
int nbytes = len; | |
int ndwords = nbytes/4; | |
uint32_t * k = (uint32_t*)blob; | |
if(c == 0) return; | |
//---------- | |
int b = c / 32; | |
c &= (32-1); | |
for(int j = 0; j < b; j++) | |
{ | |
uint32_t t = k[ndwords-1]; | |
for(int i = ndwords-1; i > 0; i--) | |
{ | |
k[i] = k[i-1]; | |
} | |
k[0] = t; | |
} | |
uint32_t t = k[ndwords-1]; | |
if(c == 0) return; | |
for(int i = ndwords-1; i >= 0; i--) | |
{ | |
uint32_t a = k[i]; | |
uint32_t b = (i == 0) ? t : k[i-1]; | |
k[i] = (a << c) | (b >> (32-c)); | |
} | |
} | |
//----------------------------------------------------------------------------- | |
void rrot1 ( void * blob, int len, int c ) | |
{ | |
int nbits = len * 8; | |
for(int i = 0; i < c; i++) | |
{ | |
uint32_t bit = getbit(blob,len,0); | |
rshift1(blob,len,1); | |
setbit(blob,len,nbits-1,bit); | |
} | |
} | |
void rrot8 ( void * blob, int len, int c ) | |
{ | |
int nbytes = len; | |
uint8_t * k = (uint8_t*)blob; | |
if(c == 0) return; | |
//---------- | |
int b = c / 8; | |
c &= (8-1); | |
for(int j = 0; j < b; j++) | |
{ | |
uint8_t t = k[0]; | |
for(int i = 0; i < nbytes-1; i++) | |
{ | |
k[i] = k[i+1]; | |
} | |
k[nbytes-1] = t; | |
} | |
if(c == 0) return; | |
//---------- | |
uint8_t t = k[0]; | |
for(int i = 0; i < nbytes; i++) | |
{ | |
uint8_t a = (i == nbytes-1) ? t : k[i+1]; | |
uint8_t b = k[i]; | |
k[i] = (a << (8-c)) | (b >> c); | |
} | |
} | |
void rrot32 ( void * blob, int len, int c ) | |
{ | |
assert((len & 3) == 0); | |
int nbytes = len; | |
int ndwords = nbytes/4; | |
uint32_t * k = (uint32_t*)blob; | |
if(c == 0) return; | |
//---------- | |
int b = c / 32; | |
c &= (32-1); | |
for(int j = 0; j < b; j++) | |
{ | |
uint32_t t = k[0]; | |
for(int i = 0; i < ndwords-1; i++) | |
{ | |
k[i] = k[i+1]; | |
} | |
k[ndwords-1] = t; | |
} | |
if(c == 0) return; | |
//---------- | |
uint32_t t = k[0]; | |
for(int i = 0; i < ndwords; i++) | |
{ | |
uint32_t a = (i == ndwords-1) ? t : k[i+1]; | |
uint32_t b = k[i]; | |
k[i] = (a << (32-c)) | (b >> c); | |
} | |
} | |
//----------------------------------------------------------------------------- | |
uint32_t window1 ( void * blob, int len, int start, int count ) | |
{ | |
int nbits = len*8; | |
start %= nbits; | |
uint32_t t = 0; | |
for(int i = 0; i < count; i++) | |
{ | |
setbit(&t,sizeof(t),i, getbit_wrap(blob,len,start+i)); | |
} | |
return t; | |
} | |
uint32_t window8 ( void * blob, int len, int start, int count ) | |
{ | |
int nbits = len*8; | |
start %= nbits; | |
uint32_t t = 0; | |
uint8_t * k = (uint8_t*)blob; | |
if(count == 0) return 0; | |
int c = start & (8-1); | |
int d = start / 8; | |
for(int i = 0; i < 4; i++) | |
{ | |
int ia = (i + d + 1) % len; | |
int ib = (i + d + 0) % len; | |
uint32_t a = k[ia]; | |
uint32_t b = k[ib]; | |
uint32_t m = (a << (8-c)) | (b >> c); | |
t |= (m << (8*i)); | |
} | |
t &= ((1 << count)-1); | |
return t; | |
} | |
uint32_t window32 ( void * blob, int len, int start, int count ) | |
{ | |
int nbits = len*8; | |
start %= nbits; | |
assert((len & 3) == 0); | |
int ndwords = len / 4; | |
uint32_t * k = (uint32_t*)blob; | |
if(count == 0) return 0; | |
int c = start & (32-1); | |
int d = start / 32; | |
if(c == 0) return (k[d] & ((1 << count) - 1)); | |
int ia = (d + 1) % ndwords; | |
int ib = (d + 0) % ndwords; | |
uint32_t a = k[ia]; | |
uint32_t b = k[ib]; | |
uint32_t t = (a << (32-c)) | (b >> c); | |
t &= ((1 << count)-1); | |
return t; | |
} | |
//----------------------------------------------------------------------------- | |
bool test_shift ( void ) | |
{ | |
int nbits = 64; | |
int nbytes = nbits / 8; | |
int reps = 10000; | |
for(int j = 0; j < reps; j++) | |
{ | |
if(j % (reps/10) == 0) printf("."); | |
uint64_t a = rand_u64(); | |
uint64_t b; | |
for(int i = 0; i < nbits; i++) | |
{ | |
b = a; lshift1 (&b,nbytes,i); assert(b == (a << i)); | |
b = a; lshift8 (&b,nbytes,i); assert(b == (a << i)); | |
b = a; lshift32 (&b,nbytes,i); assert(b == (a << i)); | |
b = a; rshift1 (&b,nbytes,i); assert(b == (a >> i)); | |
b = a; rshift8 (&b,nbytes,i); assert(b == (a >> i)); | |
b = a; rshift32 (&b,nbytes,i); assert(b == (a >> i)); | |
b = a; lrot1 (&b,nbytes,i); assert(b == _rotl64(a,i)); | |
b = a; lrot8 (&b,nbytes,i); assert(b == _rotl64(a,i)); | |
b = a; lrot32 (&b,nbytes,i); assert(b == _rotl64(a,i)); | |
b = a; rrot1 (&b,nbytes,i); assert(b == _rotr64(a,i)); | |
b = a; rrot8 (&b,nbytes,i); assert(b == _rotr64(a,i)); | |
b = a; rrot32 (&b,nbytes,i); assert(b == _rotr64(a,i)); | |
} | |
} | |
printf("PASS\n"); | |
return true; | |
} | |
//----------------------------------------------------------------------------- | |
template < int nbits > | |
bool test_window2 ( void ) | |
{ | |
struct keytype | |
{ | |
uint8_t bytes[nbits/8]; | |
}; | |
int nbytes = nbits / 8; | |
int reps = 10000; | |
for(int j = 0; j < reps; j++) | |
{ | |
if(j % (reps/10) == 0) printf("."); | |
keytype k; | |
rand_p(&k,nbytes); | |
for(int start = 0; start < nbits; start++) | |
{ | |
for(int count = 0; count < 32; count++) | |
{ | |
uint32_t a = window1(&k,nbytes,start,count); | |
uint32_t b = window8(&k,nbytes,start,count); | |
uint32_t c = window(&k,nbytes,start,count); | |
assert(a == b); | |
assert(a == c); | |
} | |
} | |
} | |
printf("PASS %d\n",nbits); | |
return true; | |
} | |
bool test_window ( void ) | |
{ | |
int reps = 10000; | |
for(int j = 0; j < reps; j++) | |
{ | |
if(j % (reps/10) == 0) printf("."); | |
int nbits = 64; | |
int nbytes = nbits / 8; | |
uint64_t x = rand_u64(); | |
for(int start = 0; start < nbits; start++) | |
{ | |
for(int count = 0; count < 32; count++) | |
{ | |
uint32_t a = (uint32_t)_rotr64(x,start); | |
a &= ((1 << count)-1); | |
uint32_t b = window1 (&x,nbytes,start,count); | |
uint32_t c = window8 (&x,nbytes,start,count); | |
uint32_t d = window32(&x,nbytes,start,count); | |
uint32_t e = window (x,start,count); | |
assert(a == b); | |
assert(a == c); | |
assert(a == d); | |
assert(a == e); | |
} | |
} | |
} | |
printf("PASS 64\n"); | |
test_window2<8>(); | |
test_window2<16>(); | |
test_window2<24>(); | |
test_window2<32>(); | |
test_window2<40>(); | |
test_window2<48>(); | |
test_window2<56>(); | |
test_window2<64>(); | |
return true; | |
} | |
//----------------------------------------------------------------------------- |