delta_binary.h

/* Binary interface to A5/1 tables generated by the TMTO Project.

 *** Copyright notice ***

 The following functions have been taken from DeltaLookup.cpp (and edited
 to be compilable with GCC)

 * kr02_mergebits, kr02_whitening
 - Simple hash function.

 * StartEndpointSearch, CompleteEndpointSearch, load_idx
 - Binary interface to undocumented table format.

 There exist several copies of this code with unspecified license.
 The A5/1 kernel itself is explicitly non-free, but the rest of Kraken
 (presumably by different authors) has no license given. I believe such
 binary interface to an undocumented format could qualify as fair use.

 We have tried to contact the kernel author and the project mailing list
 to clarify the situation, but no reply was received.

 I am leaving the functions here, in any problems with the copyright
 please contact me at <jenda (at) hrach (.) eu> and we will attempt
 a clean-room design.

 */

/* Begin patched DeltaLookup content. */

#define READ8()\
  bits = (mBitBuffer>>(mBitCount-8))&0xff;                 \
mBitBuffer = (mBitBuffer<<8)|pBuffer[mBufPos++];

#define READ8safe()\
  bits = (mBitBuffer>>(mBitCount-8))&0xff;                 \
if (mBufPos<4096) {                                      \
  mBitBuffer = (mBitBuffer<<8)|pBuffer[mBufPos++];     \
}

#define READN(n)\
  bits = mBitBuffer>>(mBitCount-(n));         \
bits = bits & ((1<<(n))-1);                 \
mBitCount-=(n);                             \
if(mBitCount<8) { \
  mBitBuffer = (mBitBuffer<<8)|pBuffer[mBufPos++];    \
  mBitCount+=8; \
} 

/* Whitening function to expand short table generation key to 64 bits */
static uint64_t kr02_whitening(uint64_t key) {
  uint64_t white = 0;
  uint64_t bits = 0x93cbc4077efddc15ULL;
  uint64_t b = 0x1;
  while (b) {
    if (b & key) {
      white ^= bits;
    }
    bits = (bits<<1)|(bits>>63);
    b = b << 1;
  }
  return white;
}

static uint64_t kr02_mergebits(uint64_t key) {
  uint64_t r = 0ULL;
  uint64_t b = 1ULL;
  unsigned int i;

  for(i=0;i<64;i++) {
    if (key&b) {
      r |= 1ULL << (((i<<1)&0x3e)|(i>>5));
    }
    b = b << 1;
  }
  return r;
}

uint64_t ApplyIndexFunc(uint64_t start_index, int bits)
{
  uint64_t w = kr02_whitening(start_index);
  start_index = kr02_mergebits((w<<bits)|start_index);
  return start_index;
}

/* Index of blockstarts in table */
/* The number of chains in tables generated is unknown to me. These
   index sizes have been worked out empirically... */
int mBlockIndex[40][10227760+100000];
uint64_t mPrimaryIndex[40][39952+1000];

int mNumBlocks[40];
unsigned long mStepSize[40];
int64_t mLowEndpoint[40];
int64_t mHighEndpoint[40];
int64_t mBlockOffset;

static unsigned short mBase[256]; 
static unsigned char mBits[256]; 

int mInitStatics = 0; 

/* Load index for all tables */
void load_idx() {

  for(int idx=0; idx<40; idx++) {

    /* Open index file */
    FILE* fd = fopen(files[idx],"rb");
    if (fd==0) {
      printf("Could not open %s for reading.\n", files[idx]);
    }
    assert(fd);
    fseek(fd, 0, SEEK_END);

    /* Get file size */
    long size = ftell(fd);
    unsigned int num = (size / sizeof(uint64_t))-1;
    fseek(fd ,0 ,SEEK_SET );
    size_t alloced = num*sizeof(int)+(num/256)*sizeof(int64_t);
    fprintf(stderr, "Allocated %li bytes: %i\n",alloced,idx);

    mNumBlocks[idx] = num;
    uint64_t end;

    /* Get step size for position estimation */
    mStepSize[idx] = 0xfffffffffffffLL/(num+1);
    int64_t min = 0;
    int64_t max = 0;
    int64_t last = 0;

    /* Read blocks and save block offsets */
    for(int bl=0; bl<num; bl++) {
      size_t r = fread(&end,sizeof(uint64_t),1,fd);
      assert(r==1);
      int64_t offset = (end>>12)-last-mStepSize[idx];
      last = end>>12;
      if (offset>max) max = offset;
      if (offset<min) min = offset;
      if (offset >= 0x7fffffff || offset <=-0x7fffffff) {
        fprintf(stderr,"index file corrupt: %s\n", "F");
        exit(1);
      }
      mBlockIndex[idx][bl]=offset;
      if ((bl&0xff)==0) {
        mPrimaryIndex[idx][bl>>8]=end;
      }
    }

    mBlockIndex[idx][num] = 0x7fffffff; /* for detecting last index */
    // printf("%llx %llx %llx\n", min,max,mPrimaryIndex[1]);

    mLowEndpoint[idx] = mPrimaryIndex[idx][0];
    size_t r=fread(&mHighEndpoint[idx],sizeof(uint64_t),1,fd);
    assert(r==1);
    fclose(fd);
    mBlockOffset=0ULL;
  }
  //    mDevice = dev;

  if (!mInitStatics) {
    // Fill in decoding tables
    int groups[] = {0,4,126,62,32,16,8,4,2,1};
    int gsize = 1;
    unsigned short base = 0;
    int group = 0;
    for (int i=0;i<10;i++) {
      for (int j=0; j<groups[i]; j++) {
        mBase[group] = base;
        mBits[group] = i;
        base += gsize;
        group++;
      }
      gsize = 2 * gsize;
    }
    // The rest should be unused 
    assert(group<256);
    mInitStatics = 1;
  }
}

/* Find number of block that we need.

   end: target (endpoint) value
   tbl: table ID
   j:   number of fragment in burst

 */
void StartEndpointSearch(uint64_t end, int tbl, int j, FILE* fp) {

  //printf("end=%llx, blockstart=%llx\n", end, blockstart);
  if (end<mLowEndpoint[tbl]) return;
  if (end>mHighEndpoint[tbl]) return;

  uint64_t bid = (end>>12) / mStepSize[tbl];
  unsigned int bl = ((unsigned int)bid)/256;

  // Methinks the division has been done by float, and may 
  // have less precision than required
  while (bl && (mPrimaryIndex[tbl][bl]>end)) bl--;

  uint64_t here = mPrimaryIndex[tbl][bl];
  int count = 0;
  bl = bl *256;
  uint64_t delta = (mStepSize[tbl] + mBlockIndex[tbl][bl+1])<<12;

#if DEBUG_PRINT
  printf("here: %llx bl: %llu\n", here, bl);
#endif

  // XXX 41MB block => 42991616, ble (41 * 1024 * 1024)
  while(((here+delta)<=end) && (bl<mNumBlocks[tbl]+1)) {
    here+=delta;
    bl++;
    count++;
#if DEBUG_PRINT
    printf("here: %llx bl: %llu\n", here, bl);
#endif
    delta = (mStepSize[tbl] + mBlockIndex[tbl][bl+1])<<12;
  }

#if DEBUG_PRINT
  printf("%i block (%i)\n", bl, count);
#endif

  /*   if (j == 2453) {
       printf("Seq search, block %x, blockstart %lx, endpoint %lX, table %i, idx %i\n", bl, here, end, tbl, j);
       uint64_t rs = MineABlock(bl,here,end,tbl);
       printf("Returned %lx (32-bit hash input)\n", rs);
       rs=rev(ApplyIndexFunc(rs, 34));
       printf("Hashed %lx\n",rs);
       }*/


  MineABlockNCQ(bl,here,end,tbl,j, fp);
  //mDevice->Request(req, (uint64_t)bl+mBlockOffset );
}


#define DEBUG_PRINT 0

/* Find startpoint value in block read from tables.

    *pDataBlock: pointer to beginning of raw block from disk
    here:        delta-offset of the first point
    end:         target value

   Returns:
    - generation key, which needs to be hashed to get the A5/1 initial state
    - 0 in case of nothing is found in the table

    There is about 30% chance that the key is found.
 */

uint64_t CompleteEndpointSearch(const void* pDataBlock, uint64_t here,
    uint64_t end) {
  const unsigned char* pBuffer = (const unsigned char*)pDataBlock;
  unsigned int mBufPos = 0;
  unsigned int mBitBuffer = pBuffer[mBufPos++];
  unsigned int mBitCount = 8;
  unsigned char bits;
  uint64_t index;
  uint64_t tmp, result;
  uint64_t delta;


  // read generating index for first chain in block 
  READ8();
  tmp = bits;
  READ8();
  tmp = (tmp<<8)|bits;
  READ8();
  tmp = (tmp<<8)|bits;
  READ8();
  tmp = (tmp<<8)|bits;
  READN(2);
  tmp = (tmp<<2)|bits;

#if DEBUG_PRINT
  printf("%llx %llx\n", here, tmp);
#endif

  if (here==end) {
    result = tmp;
    return result;
  }

  for(;;) {
    int available = (4096-mBufPos)*8 + mBitCount;
    if (available<51) {
#if DEBUG_PRINT
      printf("End of block (%i bits left)\n", available);
#endif
      break;
    }
    READ8();
    if (bits==0xff) {
      if (available<72) {
#if DEBUG_PRINT
        printf("End of block (%i bits left)\n", available);
#endif
        break;
      }
      // Escape code 
      READ8();
      tmp = bits;
      READ8();
      tmp = (tmp<<8)|bits;
      READ8();
      tmp = (tmp<<8)|bits;
      READ8();
      tmp = (tmp<<8)|bits;
      READ8();
      tmp = (tmp<<8)|bits;
      READ8();
      tmp = (tmp<<8)|bits;
      READ8();
      tmp = (tmp<<8)|bits;
      READ8safe();
      tmp = (tmp<<8)|bits;
      delta = tmp >> 34;
      index = tmp & 0x3ffffffffULL;
    } else {
      unsigned int code = bits;
      unsigned int rb = mBits[code];
      //printf("%02x - %i - %x ",code,rb,mBase[code]);
      delta = mBase[code];
      unsigned int d2 = 0;
      if (rb>=8) {
        READ8();
        d2 = bits;
        rb-=8;
      }
      if (rb) {
        READN(rb);
        d2 = (d2<<rb)|bits;
      }
      //printf("%llx %x\n",delta,d2);
      delta+=d2;
      READ8();
      delta = (delta<<8)|bits;
      READN(2);
      delta = (delta<<2)|bits;

      READN(1);
      uint64_t idx = bits;
      READ8();
      idx = (idx<<8)|bits;
      READ8();
      idx = (idx<<8)|bits;
      READ8();
      idx = (idx<<8)|bits;
      READ8safe();
      index = (idx<<8)|bits;
    }
    here += delta<<12;
#if DEBUG_PRINT
    printf("%llx %llx\n", here, index);
#endif
    if (here==end) {
      result = index;
      return result;
    }

    if (here>end) {
#if DEBUG_PRINT
      printf("passed: %llx %llx\n", here, end);
#endif
      break;
    }
  }

  return 0;
}