smhasher/Bitvec.cpp

#include "Bitvec.h"

#include "Random.h"

#include <assert.h>
#include <stdio.h>

#ifndef DEBUG
#undef assert
void assert ( bool )
{
}
#endif

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

void printbits ( const void * blob, int len )
{
  const uint8_t * data = (const 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 ( const 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 ( const 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("}");
}

void printbytes ( const void * blob, int len )
{
  uint8_t * d = (uint8_t*)blob;

  printf("{ ");

  for(int i = 0; i < len; i++)
  {
    printf("0x%02x, ",d[i]);
  }

  printf(" };");
}

void printbytes2 ( const void * blob, int len )
{
  uint8_t * d = (uint8_t*)blob;

  for(int i = 0; i < len; i++)
  {
    printf("%02x ",d[i]);
  }
}

//-----------------------------------------------------------------------------
// Bit-level manipulation

// These two 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 parity ( uint32_t v )
{
	v ^= v >> 1;
	v ^= v >> 2;
	v = (v & 0x11111111U) * 0x11111111U;
	return (v >> 28) & 1;
}

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

uint32_t getbit ( const 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 ( const 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);
}

// from the "Bit Twiddling Hacks" webpage

int countbits ( uint32_t v )
{
  v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
  int c = ((v + ((v >> 4) & 0xF0F0F0F)) * 0x1010101) >> 24; // count

  return c;
}

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

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 = reinterpret_cast<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 )
{
  Rand r(1123);

  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 = r.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 )
{
  Rand r(83874);
  
  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;

    r.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 )
{
  Rand r(48402);
  
  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 = r.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;
}

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