fork download 
  1. #include <stdio.h>
  2. #include <assert.h>
  3.  
  4. unsigned char bitseq[50] = { 0 };
  5.  
  6. int store(unsigned a) {
  7.   unsigned b, lo, hi, bitpos, byteno, cur;
  8.   assert(a < 4032);                        // a has range 0 .. 0xfbf
  9.  
  10.   // shuffle
  11.   b = (a << 9) + (a << 6) + a + 64;        // range 0x40 ..0x237dbf
  12.   b = (b & 0xfff) + ((b & 0xfff000) >> 6); // range 0x40 .. 0x9d7f
  13.   b = (b & 0xfff) + ((b & 0xfff000) >> 6); // range 0x40 .. 0x11ff
  14.   b = (b & 0xfff) + ((b & 0xfff000) >> 6); // range 0x40 .. 0xfff
  15.   assert(b >= 0x40 && b <= 0xfff);
  16.   b -= 64;                                 // range 0x00 .. 0xfbf
  17.  
  18.   // split
  19.   lo = b & 63;                             // range 0x00 .. 0x3f
  20.   hi = b >> 6;                             // range 0x00 .. 0x3e
  21.  
  22.   // access bit sequence
  23.   bitpos = (lo << 2) + (lo << 1);          // range 0x00 .. 0x17a
  24.   byteno = (bitpos >> 3);                  // range 0x00 .. 0x30
  25.   bitpos &= 7;                             // range 0x00 .. 0x7
  26.   cur = (((bitseq[byteno + 1] << 8) | bitseq[byteno]) >> bitpos) & 0xff;
  27.   if (cur != 0) return 1; // slot already occupied.
  28.   cur = hi + 1;           // range 0x01 .. 0x3f means occupied
  29.   assert(cur >= 0x01 && cur <= 0x3f);
  30.   bitseq[byteno] |= (cur << bitpos) & 0xff;
  31.   bitseq[byteno + 1] |= ((cur << bitpos) & 0xff00) >> 8;
  32.   /*
  33.   printf("Storing %02x (now %02x) in %02x and %02x (now %02x) in %02x for %02x shift %d shifted %04x\n",
  34.          (cur << bitpos) & 0xff, bitseq[byteno], byteno,
  35.          ((cur << bitpos) & 0xff00) >> 8, bitseq[byteno + 1], byteno + 1,
  36.          cur, bitpos, cur << bitpos);
  37.   */
  38.   return 0;               // slot was free, value stored
  39. }
  40.  
  41. void list_all() {
  42.   unsigned b, lo, hi, bitpos, byteno, cur;
  43.   for (lo = 0; lo != 64; ++lo) {
  44.     // access bit sequence
  45.     bitpos = (lo << 2) + (lo << 1);
  46.     byteno = (bitpos >> 3);
  47.     bitpos &= 7;
  48.     cur = (((bitseq[byteno + 1] << 8) | bitseq[byteno]) >> bitpos) & 0x3f;
  49.     if (cur == 0) continue;
  50.  
  51.     /*
  52.     printf("read %02x (now %02x) from %02x and %02x (now %02x) from %02x for %02x shift %d shifted %04x\n",
  53.          (cur << bitpos) & 0xff, bitseq[byteno], byteno,
  54.          ((cur << bitpos) & 0xff00) >> 8, bitseq[byteno + 1], byteno + 1,
  55.          cur, bitpos, cur << bitpos);
  56.     */
  57.  
  58.     // recombine
  59.     hi = cur - 1;
  60.     b = (hi << 6) | lo;
  61.  
  62.     // unshuffle
  63.     b = (b << 10) + (b << 7) + b + 64;
  64.     b = (b & 0xfff) + ((b & 0xfff000) >> 6);
  65.     b = (b & 0xfff) + ((b & 0xfff000) >> 6);
  66.     b = (b & 0xfff) + ((b & 0xfff000) >> 6);
  67.     assert(b >= 0x40 && b <= 0xfff);
  68.     b -= 64;
  69.  
  70.     // report
  71.     printf("%4d was stored in slot %2d using value %2d.\n", b, lo, cur);
  72.   }
  73. }
  74.  
  75. int main() {
  76.   int res;
  77.   res = store(123); assert(res == 0);
  78.   res = store(452); assert(res == 0);
  79.   res = store(68); assert(res == 1); // will collide with 452
  80.   list_all();
  81.   return 0;
  82. }
  83.  
Success #stdin #stdout 0s 2292KB
comments (?)
stdin 
Standard input is empty
stdout 
 452 was stored in slot  4 using value 44.
 123 was stored in slot 59 using value 38.
https://ideone.com/qHuvIl
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!