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