Merge branch chandlerc_dev

git-svn-id: http://smhasher.googlecode.com/svn/trunk@144 77a7d1d3-4c08-bdc2-d393-d5859734b01a

1 files changed, 757 insertions, 757 deletions

diff --git a/Bitvec.cpp b/Bitvec.cpp
index 6c74bcc..4855f8f 100644
--- a/Bitvec.cpp
+++ b/Bitvec.cpp
@@ -1,757 +1,757 @@
-#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;

-}

-

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

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