Bitvec.cpp

#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;
}

//-----------------------------------------------------------------------------