1#include "Bitvec.h" 2 3#include "Random.h" 4 5#include <assert.h> 6#include <stdio.h> 7 8#ifndef DEBUG 9#undef assert 10void assert ( bool ) 11{ 12} 13#endif 14 15//---------------------------------------------------------------------------- 16 17void printbits ( const void * blob, int len ) 18{ 19 const uint8_t * data = (const uint8_t *)blob; 20 21 printf("["); 22 for(int i = 0; i < len; i++) 23 { 24 unsigned char byte = data[i]; 25 26 int hi = (byte >> 4); 27 int lo = (byte & 0xF); 28 29 if(hi) printf("%01x",hi); 30 else printf("."); 31 32 if(lo) printf("%01x",lo); 33 else printf("."); 34 35 if(i != len-1) printf(" "); 36 } 37 printf("]"); 38} 39 40void printbits2 ( const uint8_t * k, int nbytes ) 41{ 42 printf("["); 43 44 for(int i = nbytes-1; i >= 0; i--) 45 { 46 uint8_t b = k[i]; 47 48 for(int j = 7; j >= 0; j--) 49 { 50 uint8_t c = (b & (1 << j)) ? '#' : ' '; 51 52 putc(c,stdout); 53 } 54 } 55 printf("]"); 56} 57 58void printhex32 ( const void * blob, int len ) 59{ 60 assert((len & 3) == 0); 61 62 uint32_t * d = (uint32_t*)blob; 63 64 printf("{ "); 65 66 for(int i = 0; i < len/4; i++) 67 { 68 printf("0x%08x, ",d[i]); 69 } 70 71 printf("}"); 72} 73 74void printbytes ( const void * blob, int len ) 75{ 76 uint8_t * d = (uint8_t*)blob; 77 78 printf("{ "); 79 80 for(int i = 0; i < len; i++) 81 { 82 printf("0x%02x, ",d[i]); 83 } 84 85 printf(" };"); 86} 87 88void printbytes2 ( const void * blob, int len ) 89{ 90 uint8_t * d = (uint8_t*)blob; 91 92 for(int i = 0; i < len; i++) 93 { 94 printf("%02x ",d[i]); 95 } 96} 97 98//----------------------------------------------------------------------------- 99// Bit-level manipulation 100 101// These two are from the "Bit Twiddling Hacks" webpage 102 103uint32_t popcount ( uint32_t v ) 104{ 105 v = v - ((v >> 1) & 0x55555555); // reuse input as temporary 106 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp 107 uint32_t c = ((v + ((v >> 4) & 0xF0F0F0F)) * 0x1010101) >> 24; // count 108 109 return c; 110} 111 112uint32_t parity ( uint32_t v ) 113{ 114 v ^= v >> 1; 115 v ^= v >> 2; 116 v = (v & 0x11111111U) * 0x11111111U; 117 return (v >> 28) & 1; 118} 119 120//----------------------------------------------------------------------------- 121 122uint32_t getbit ( const void * block, int len, uint32_t bit ) 123{ 124 uint8_t * b = (uint8_t*)block; 125 126 int byte = bit >> 3; 127 bit = bit & 0x7; 128 129 if(byte < len) return (b[byte] >> bit) & 1; 130 131 return 0; 132} 133 134uint32_t getbit_wrap ( const void * block, int len, uint32_t bit ) 135{ 136 uint8_t * b = (uint8_t*)block; 137 138 int byte = bit >> 3; 139 bit = bit & 0x7; 140 141 byte %= len; 142 143 return (b[byte] >> bit) & 1; 144} 145 146void setbit ( void * block, int len, uint32_t bit ) 147{ 148 uint8_t * b = (uint8_t*)block; 149 150 int byte = bit >> 3; 151 bit = bit & 0x7; 152 153 if(byte < len) b[byte] |= (1 << bit); 154} 155 156void setbit ( void * block, int len, uint32_t bit, uint32_t val ) 157{ 158 val ? setbit(block,len,bit) : clearbit(block,len,bit); 159} 160 161void clearbit ( void * block, int len, uint32_t bit ) 162{ 163 uint8_t * b = (uint8_t*)block; 164 165 int byte = bit >> 3; 166 bit = bit & 0x7; 167 168 if(byte < len) b[byte] &= ~(1 << bit); 169} 170 171void flipbit ( void * block, int len, uint32_t bit ) 172{ 173 uint8_t * b = (uint8_t*)block; 174 175 int byte = bit >> 3; 176 bit = bit & 0x7; 177 178 if(byte < len) b[byte] ^= (1 << bit); 179} 180 181// from the "Bit Twiddling Hacks" webpage 182 183int countbits ( uint32_t v ) 184{ 185 v = v - ((v >> 1) & 0x55555555); // reuse input as temporary 186 v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp 187 int c = ((v + ((v >> 4) & 0xF0F0F0F)) * 0x1010101) >> 24; // count 188 189 return c; 190} 191 192//----------------------------------------------------------------------------- 193 194void lshift1 ( void * blob, int len, int c ) 195{ 196 int nbits = len*8; 197 198 for(int i = nbits-1; i >= 0; i--) 199 { 200 setbit(blob,len,i,getbit(blob,len,i-c)); 201 } 202} 203 204 205void lshift8 ( void * blob, int nbytes, int c ) 206{ 207 uint8_t * k = (uint8_t*)blob; 208 209 if(c == 0) return; 210 211 int b = c >> 3; 212 c &= 7; 213 214 for(int i = nbytes-1; i >= b; i--) 215 { 216 k[i] = k[i-b]; 217 } 218 219 for(int i = b-1; i >= 0; i--) 220 { 221 k[i] = 0; 222 } 223 224 if(c == 0) return; 225 226 for(int i = nbytes-1; i >= 0; i--) 227 { 228 uint8_t a = k[i]; 229 uint8_t b = (i == 0) ? 0 : k[i-1]; 230 231 k[i] = (a << c) | (b >> (8-c)); 232 } 233} 234 235void lshift32 ( void * blob, int len, int c ) 236{ 237 assert((len & 3) == 0); 238 239 int nbytes = len; 240 int ndwords = nbytes / 4; 241 242 uint32_t * k = reinterpret_cast<uint32_t*>(blob); 243 244 if(c == 0) return; 245 246 //---------- 247 248 int b = c / 32; 249 c &= (32-1); 250 251 for(int i = ndwords-1; i >= b; i--) 252 { 253 k[i] = k[i-b]; 254 } 255 256 for(int i = b-1; i >= 0; i--) 257 { 258 k[i] = 0; 259 } 260 261 if(c == 0) return; 262 263 for(int i = ndwords-1; i >= 0; i--) 264 { 265 uint32_t a = k[i]; 266 uint32_t b = (i == 0) ? 0 : k[i-1]; 267 268 k[i] = (a << c) | (b >> (32-c)); 269 } 270} 271 272//----------------------------------------------------------------------------- 273 274void rshift1 ( void * blob, int len, int c ) 275{ 276 int nbits = len*8; 277 278 for(int i = 0; i < nbits; i++) 279 { 280 setbit(blob,len,i,getbit(blob,len,i+c)); 281 } 282} 283 284void rshift8 ( void * blob, int nbytes, int c ) 285{ 286 uint8_t * k = (uint8_t*)blob; 287 288 if(c == 0) return; 289 290 int b = c >> 3; 291 c &= 7; 292 293 for(int i = 0; i < nbytes-b; i++) 294 { 295 k[i] = k[i+b]; 296 } 297 298 for(int i = nbytes-b; i < nbytes; i++) 299 { 300 k[i] = 0; 301 } 302 303 if(c == 0) return; 304 305 for(int i = 0; i < nbytes; i++) 306 { 307 uint8_t a = (i == nbytes-1) ? 0 : k[i+1]; 308 uint8_t b = k[i]; 309 310 k[i] = (a << (8-c) ) | (b >> c); 311 } 312} 313 314void rshift32 ( void * blob, int len, int c ) 315{ 316 assert((len & 3) == 0); 317 318 int nbytes = len; 319 int ndwords = nbytes / 4; 320 321 uint32_t * k = (uint32_t*)blob; 322 323 //---------- 324 325 if(c == 0) return; 326 327 int b = c / 32; 328 c &= (32-1); 329 330 for(int i = 0; i < ndwords-b; i++) 331 { 332 k[i] = k[i+b]; 333 } 334 335 for(int i = ndwords-b; i < ndwords; i++) 336 { 337 k[i] = 0; 338 } 339 340 if(c == 0) return; 341 342 for(int i = 0; i < ndwords; i++) 343 { 344 uint32_t a = (i == ndwords-1) ? 0 : k[i+1]; 345 uint32_t b = k[i]; 346 347 k[i] = (a << (32-c) ) | (b >> c); 348 } 349} 350 351//----------------------------------------------------------------------------- 352 353void lrot1 ( void * blob, int len, int c ) 354{ 355 int nbits = len * 8; 356 357 for(int i = 0; i < c; i++) 358 { 359 uint32_t bit = getbit(blob,len,nbits-1); 360 361 lshift1(blob,len,1); 362 363 setbit(blob,len,0,bit); 364 } 365} 366 367void lrot8 ( void * blob, int len, int c ) 368{ 369 int nbytes = len; 370 371 uint8_t * k = (uint8_t*)blob; 372 373 if(c == 0) return; 374 375 //---------- 376 377 int b = c / 8; 378 c &= (8-1); 379 380 for(int j = 0; j < b; j++) 381 { 382 uint8_t t = k[nbytes-1]; 383 384 for(int i = nbytes-1; i > 0; i--) 385 { 386 k[i] = k[i-1]; 387 } 388 389 k[0] = t; 390 } 391 392 uint8_t t = k[nbytes-1]; 393 394 if(c == 0) return; 395 396 for(int i = nbytes-1; i >= 0; i--) 397 { 398 uint8_t a = k[i]; 399 uint8_t b = (i == 0) ? t : k[i-1]; 400 401 k[i] = (a << c) | (b >> (8-c)); 402 } 403} 404 405void lrot32 ( void * blob, int len, int c ) 406{ 407 assert((len & 3) == 0); 408 409 int nbytes = len; 410 int ndwords = nbytes/4; 411 412 uint32_t * k = (uint32_t*)blob; 413 414 if(c == 0) return; 415 416 //---------- 417 418 int b = c / 32; 419 c &= (32-1); 420 421 for(int j = 0; j < b; j++) 422 { 423 uint32_t t = k[ndwords-1]; 424 425 for(int i = ndwords-1; i > 0; i--) 426 { 427 k[i] = k[i-1]; 428 } 429 430 k[0] = t; 431 } 432 433 uint32_t t = k[ndwords-1]; 434 435 if(c == 0) return; 436 437 for(int i = ndwords-1; i >= 0; i--) 438 { 439 uint32_t a = k[i]; 440 uint32_t b = (i == 0) ? t : k[i-1]; 441 442 k[i] = (a << c) | (b >> (32-c)); 443 } 444} 445 446//----------------------------------------------------------------------------- 447 448void rrot1 ( void * blob, int len, int c ) 449{ 450 int nbits = len * 8; 451 452 for(int i = 0; i < c; i++) 453 { 454 uint32_t bit = getbit(blob,len,0); 455 456 rshift1(blob,len,1); 457 458 setbit(blob,len,nbits-1,bit); 459 } 460} 461 462void rrot8 ( void * blob, int len, int c ) 463{ 464 int nbytes = len; 465 466 uint8_t * k = (uint8_t*)blob; 467 468 if(c == 0) return; 469 470 //---------- 471 472 int b = c / 8; 473 c &= (8-1); 474 475 for(int j = 0; j < b; j++) 476 { 477 uint8_t t = k[0]; 478 479 for(int i = 0; i < nbytes-1; i++) 480 { 481 k[i] = k[i+1]; 482 } 483 484 k[nbytes-1] = t; 485 } 486 487 if(c == 0) return; 488 489 //---------- 490 491 uint8_t t = k[0]; 492 493 for(int i = 0; i < nbytes; i++) 494 { 495 uint8_t a = (i == nbytes-1) ? t : k[i+1]; 496 uint8_t b = k[i]; 497 498 k[i] = (a << (8-c)) | (b >> c); 499 } 500} 501 502void rrot32 ( void * blob, int len, int c ) 503{ 504 assert((len & 3) == 0); 505 506 int nbytes = len; 507 int ndwords = nbytes/4; 508 509 uint32_t * k = (uint32_t*)blob; 510 511 if(c == 0) return; 512 513 //---------- 514 515 int b = c / 32; 516 c &= (32-1); 517 518 for(int j = 0; j < b; j++) 519 { 520 uint32_t t = k[0]; 521 522 for(int i = 0; i < ndwords-1; i++) 523 { 524 k[i] = k[i+1]; 525 } 526 527 k[ndwords-1] = t; 528 } 529 530 if(c == 0) return; 531 532 //---------- 533 534 uint32_t t = k[0]; 535 536 for(int i = 0; i < ndwords; i++) 537 { 538 uint32_t a = (i == ndwords-1) ? t : k[i+1]; 539 uint32_t b = k[i]; 540 541 k[i] = (a << (32-c)) | (b >> c); 542 } 543} 544 545//----------------------------------------------------------------------------- 546 547uint32_t window1 ( void * blob, int len, int start, int count ) 548{ 549 int nbits = len*8; 550 start %= nbits; 551 552 uint32_t t = 0; 553 554 for(int i = 0; i < count; i++) 555 { 556 setbit(&t,sizeof(t),i, getbit_wrap(blob,len,start+i)); 557 } 558 559 return t; 560} 561 562uint32_t window8 ( void * blob, int len, int start, int count ) 563{ 564 int nbits = len*8; 565 start %= nbits; 566 567 uint32_t t = 0; 568 uint8_t * k = (uint8_t*)blob; 569 570 if(count == 0) return 0; 571 572 int c = start & (8-1); 573 int d = start / 8; 574 575 for(int i = 0; i < 4; i++) 576 { 577 int ia = (i + d + 1) % len; 578 int ib = (i + d + 0) % len; 579 580 uint32_t a = k[ia]; 581 uint32_t b = k[ib]; 582 583 uint32_t m = (a << (8-c)) | (b >> c); 584 585 t |= (m << (8*i)); 586 587 } 588 589 t &= ((1 << count)-1); 590 591 return t; 592} 593 594uint32_t window32 ( void * blob, int len, int start, int count ) 595{ 596 int nbits = len*8; 597 start %= nbits; 598 599 assert((len & 3) == 0); 600 601 int ndwords = len / 4; 602 603 uint32_t * k = (uint32_t*)blob; 604 605 if(count == 0) return 0; 606 607 int c = start & (32-1); 608 int d = start / 32; 609 610 if(c == 0) return (k[d] & ((1 << count) - 1)); 611 612 int ia = (d + 1) % ndwords; 613 int ib = (d + 0) % ndwords; 614 615 uint32_t a = k[ia]; 616 uint32_t b = k[ib]; 617 618 uint32_t t = (a << (32-c)) | (b >> c); 619 620 t &= ((1 << count)-1); 621 622 return t; 623} 624 625//----------------------------------------------------------------------------- 626 627bool test_shift ( void ) 628{ 629 Rand r(1123); 630 631 int nbits = 64; 632 int nbytes = nbits / 8; 633 int reps = 10000; 634 635 for(int j = 0; j < reps; j++) 636 { 637 if(j % (reps/10) == 0) printf("."); 638 639 uint64_t a = r.rand_u64(); 640 uint64_t b; 641 642 for(int i = 0; i < nbits; i++) 643 { 644 b = a; lshift1 (&b,nbytes,i); assert(b == (a << i)); 645 b = a; lshift8 (&b,nbytes,i); assert(b == (a << i)); 646 b = a; lshift32 (&b,nbytes,i); assert(b == (a << i)); 647 648 b = a; rshift1 (&b,nbytes,i); assert(b == (a >> i)); 649 b = a; rshift8 (&b,nbytes,i); assert(b == (a >> i)); 650 b = a; rshift32 (&b,nbytes,i); assert(b == (a >> i)); 651 652 b = a; lrot1 (&b,nbytes,i); assert(b == ROTL64(a,i)); 653 b = a; lrot8 (&b,nbytes,i); assert(b == ROTL64(a,i)); 654 b = a; lrot32 (&b,nbytes,i); assert(b == ROTL64(a,i)); 655 656 b = a; rrot1 (&b,nbytes,i); assert(b == ROTR64(a,i)); 657 b = a; rrot8 (&b,nbytes,i); assert(b == ROTR64(a,i)); 658 b = a; rrot32 (&b,nbytes,i); assert(b == ROTR64(a,i)); 659 } 660 } 661 662 printf("PASS\n"); 663 return true; 664} 665 666//----------------------------------------------------------------------------- 667 668template < int nbits > 669bool test_window2 ( void ) 670{ 671 Rand r(83874); 672 673 struct keytype 674 { 675 uint8_t bytes[nbits/8]; 676 }; 677 678 int nbytes = nbits / 8; 679 int reps = 10000; 680 681 for(int j = 0; j < reps; j++) 682 { 683 if(j % (reps/10) == 0) printf("."); 684 685 keytype k; 686 687 r.rand_p(&k,nbytes); 688 689 for(int start = 0; start < nbits; start++) 690 { 691 for(int count = 0; count < 32; count++) 692 { 693 uint32_t a = window1(&k,nbytes,start,count); 694 uint32_t b = window8(&k,nbytes,start,count); 695 uint32_t c = window(&k,nbytes,start,count); 696 697 assert(a == b); 698 assert(a == c); 699 } 700 } 701 } 702 703 printf("PASS %d\n",nbits); 704 705 return true; 706} 707 708bool test_window ( void ) 709{ 710 Rand r(48402); 711 712 int reps = 10000; 713 714 for(int j = 0; j < reps; j++) 715 { 716 if(j % (reps/10) == 0) printf("."); 717 718 int nbits = 64; 719 int nbytes = nbits / 8; 720 721 uint64_t x = r.rand_u64(); 722 723 for(int start = 0; start < nbits; start++) 724 { 725 for(int count = 0; count < 32; count++) 726 { 727 uint32_t a = (uint32_t)ROTR64(x,start); 728 a &= ((1 << count)-1); 729 730 uint32_t b = window1 (&x,nbytes,start,count); 731 uint32_t c = window8 (&x,nbytes,start,count); 732 uint32_t d = window32(&x,nbytes,start,count); 733 uint32_t e = window (x,start,count); 734 735 assert(a == b); 736 assert(a == c); 737 assert(a == d); 738 assert(a == e); 739 } 740 } 741 } 742 743 printf("PASS 64\n"); 744 745 test_window2<8>(); 746 test_window2<16>(); 747 test_window2<24>(); 748 test_window2<32>(); 749 test_window2<40>(); 750 test_window2<48>(); 751 test_window2<56>(); 752 test_window2<64>(); 753 754 return true; 755} 756 757//----------------------------------------------------------------------------- 758