HashTable.cpp

/*
 * This file is part of the BSGS distribution (https://github.com/JeanLucPons/Kangaroo).
 * Copyright (c) 2020 Jean Luc PONS.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, version 3.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

#include "HashTable.h"
#include <stdio.h>
#include <math.h>
#ifndef WIN64
#include <string.h>
#endif

#define GET(hash,id) E[hash].items[id]

HashTable::HashTable() {

  memset(E,0,sizeof(E));
  
}

void HashTable::Reset() {

  for(uint32_t h = 0; h < HASH_SIZE; h++) {
    if(E[h].items) {
      for(uint32_t i = 0; i<E[h].nbItem; i++)
        free(E[h].items[i]);
    }
    safe_free(E[h].items);
    E[h].maxItem = 0;
    E[h].nbItem = 0;
  }

}

uint64_t HashTable::GetNbItem() {

  uint64_t totalItem = 0;
  for(uint64_t h = 0; h < HASH_SIZE; h++) 
    totalItem += (uint64_t)E[h].nbItem;

  return totalItem;

}

ENTRY *HashTable::CreateEntry(int128_t *x,int128_t *d) {

  ENTRY *e = (ENTRY *)malloc(sizeof(ENTRY));
  e->x.i64[0] = x->i64[0];
  e->x.i64[1] = x->i64[1];
  e->d.i64[0] = d->i64[0];
  e->d.i64[1] = d->i64[1];
  return e;

}

#define ADD_ENTRY(entry) {                 \
  /* Shift the end of the index table */   \
  for (int i = E[h].nbItem; i > st; i--)   \
    E[h].items[i] = E[h].items[i - 1];     \
  E[h].items[st] = entry;                  \
  E[h].nbItem++;}

void HashTable::Convert(Int *x,Int *d,uint32_t type,uint64_t *h,int128_t *X,int128_t *D) {

  uint64_t sign = 0;
  uint64_t type64 = (uint64_t)type << 62;

  X->i64[0] = x->bits64[0];
  X->i64[1] = x->bits64[1];

  // Probability of failure (1/2^128)
  if(d->bits64[3] > 0x7FFFFFFFFFFFFFFFULL) {
    Int N(d);
    N.ModNegK1order();
    D->i64[0] = N.bits64[0];
    D->i64[1] = N.bits64[1] & 0x3FFFFFFFFFFFFFFFULL;
    sign = 1ULL << 63;
  } else {
    D->i64[0] = d->bits64[0];
    D->i64[1] = d->bits64[1] & 0x3FFFFFFFFFFFFFFFULL;
  }

  D->i64[1] |= sign;
  D->i64[1] |= type64;

  *h = (x->bits64[2] & HASH_MASK);

}


#define AV1() if(pnb1) { ::fread(&e1,32,1,f1); pnb1--; }
#define AV2() if(pnb2) { ::fread(&e2,32,1,f2); pnb2--; }

int HashTable::MergeH(uint32_t h,FILE* f1,FILE* f2,FILE* fd,uint32_t* nbDP,uint32_t *duplicate,Int* d1,uint32_t* k1,Int* d2,uint32_t* k2) {

  // Merge by line
  // N comparison but avoid slow item allocation
  // return ADD_OK or ADD_COLLISION if a COLLISION is detected

  uint32_t nb1;
  uint32_t m1;
  uint32_t nb2;
  uint32_t m2;
  *duplicate = 0;
  *nbDP = 0;

  ::fread(&nb1,sizeof(uint32_t),1,f1);
  ::fread(&m1,sizeof(uint32_t),1,f1);
  ::fread(&nb2,sizeof(uint32_t),1,f2);
  ::fread(&m2,sizeof(uint32_t),1,f2);

  // Maximum in destination
  uint32_t nbd = 0;
  uint32_t md = nb1 + nb2;

  if(md==0) {

    ::fwrite(&md,sizeof(uint32_t),1,fd);
    ::fwrite(&md,sizeof(uint32_t),1,fd);
    return ADD_OK;

  }

  ENTRY *output = (ENTRY *)malloc( md * sizeof(ENTRY) );

  ENTRY e1;
  ENTRY e2;

  uint32_t pnb1 = nb1;
  uint32_t pnb2 = nb2;
  AV1();
  AV2();
  bool end1 = (nb1 == 0);
  bool end2 = (nb2 == 0);
  bool collisionFound = false;

  while(!(end1 && end2)) {

    if( !end1 && !end2 ) {

      int comp = compare(&e1.x,&e2.x);
      if(comp < 0) {
        memcpy(output+nbd,&e1,32);
        nbd++;
        AV1();
        nb1--;
      } else if (comp==0) {
        if((e1.d.i64[0] == e2.d.i64[0]) && (e1.d.i64[1] == e2.d.i64[1])) {
          *duplicate = *duplicate + 1;
        } else {
          // Collision
          CalcDistAndType(e1.d,d1,k1);
          CalcDistAndType(e2.d,d2,k2);
          collisionFound = true;
        }
        memcpy(output + nbd,&e1,32);
        nbd++;
        AV1();
        AV2();
        nb1--;
        nb2--;
      } else {
        memcpy(output + nbd,&e2,32);
        nbd++;
        AV2();
        nb2--;
      }

    } else if( !end1 && end2 ) {

      memcpy(output + nbd,&e1,32);
      nbd++;
      AV1();
      nb1--;

    } else if( end1 && !end2) {

      memcpy(output + nbd,&e2,32);
      nbd++;
      AV2();
      nb2--;

    }

    end1 = (nb1 == 0);
    end2 = (nb2 == 0);

  }

  // write output

  // Round md to next multiple of 4
  if(nbd%4==0) {
    md = nbd;
  } else {
    md = ((nbd/4)+1)*4;
  }

  ::fwrite(&nbd,sizeof(uint32_t),1,fd);
  ::fwrite(&md,sizeof(uint32_t),1,fd);
  ::fwrite(output,32,nbd,fd);
  free(output);

  *nbDP = nbd;
  return (collisionFound?ADD_COLLISION:ADD_OK);

}

int HashTable::Add(Int *x,Int *d,uint32_t type) {

  int128_t X;
  int128_t D;
  uint64_t h;
  Convert(x,d,type,&h,&X,&D);
  ENTRY* e = CreateEntry(&X,&D);
  return Add(h,e);

}

void HashTable::ReAllocate(uint64_t h,uint32_t add) {

  E[h].maxItem += add;
  ENTRY** nitems = (ENTRY**)malloc(sizeof(ENTRY*) * E[h].maxItem);
  memcpy(nitems,E[h].items,sizeof(ENTRY*) * E[h].nbItem);
  free(E[h].items);
  E[h].items = nitems;

}

int HashTable::Add(uint64_t h,int128_t *x,int128_t *d) {

  ENTRY *e = CreateEntry(x,d);
  return Add(h,e);

}

void HashTable::CalcDistAndType(int128_t d,Int* kDist,uint32_t* kType) {

  *kType = (d.i64[1] & 0x4000000000000000ULL) != 0;
  int sign = (d.i64[1] & 0x8000000000000000ULL) != 0;
  d.i64[1] &= 0x3FFFFFFFFFFFFFFFULL;

  kDist->SetInt32(0);
  kDist->bits64[0] = d.i64[0];
  kDist->bits64[1] = d.i64[1];
  if(sign) kDist->ModNegK1order();

}

int HashTable::Add(uint64_t h,ENTRY* e) {

  if(E[h].maxItem == 0) {
    E[h].maxItem = 16;
    E[h].items = (ENTRY **)malloc(sizeof(ENTRY *) * E[h].maxItem);
  }

  if(E[h].nbItem == 0) {
    E[h].items[0] = e;
    E[h].nbItem = 1;
    return ADD_OK;
  }

  if(E[h].nbItem >= E[h].maxItem - 1) {
    // We need to reallocate
    ReAllocate(h,4);
  }

  // Search insertion position
  int st,ed,mi;
  st = 0; ed = E[h].nbItem - 1;
  while(st <= ed) {
    mi = (st + ed) / 2;
    int comp = compare(&e->x,&GET(h,mi)->x);
    if(comp<0) {
      ed = mi - 1;
    } else if (comp==0) {

      if((e->d.i64[0] == GET(h,mi)->d.i64[0]) && (e->d.i64[1] == GET(h,mi)->d.i64[1])) {
        // Same point added 2 times or collision in same herd !
        return ADD_DUPLICATE;
      }

      // Collision
      CalcDistAndType(GET(h,mi)->d , &kDist, &kType);
      return ADD_COLLISION;

    } else {
      st = mi + 1;
    }
  }

  ADD_ENTRY(e);
  return ADD_OK;

}

int HashTable::compare(int128_t *i1,int128_t *i2) {

  uint64_t *a = i1->i64;
  uint64_t *b = i2->i64;

  if(a[1] == b[1]) {
    if(a[0] == b[0]) {
      return 0;
    } else {
      return (a[0] > b[0]) ? 1 : -1;
    }
  } else {
    return (a[1] > b[1]) ? 1 : -1;
  }

}

std::string HashTable::GetSizeInfo() {

  char *unit;
  uint64_t totalByte = sizeof(E);
  uint64_t usedByte = HASH_SIZE*2*sizeof(uint32_t);

  for (int h = 0; h < HASH_SIZE; h++) {
    totalByte += sizeof(ENTRY *) * E[h].maxItem;
    totalByte += sizeof(ENTRY) * E[h].nbItem;
    usedByte += sizeof(ENTRY) * E[h].nbItem;
  }

  unit = "MB";
  double totalMB = (double)totalByte / (1024.0*1024.0);
  double usedMB = (double)usedByte / (1024.0*1024.0);
  if(totalMB > 1024) {
    totalMB /= 1024;
    usedMB /= 1024;
    unit = "GB";
  }
  if(totalMB > 1024) {
    totalMB /= 1024;
    usedMB /= 1024;
    unit = "TB";
  }

  char ret[256];
  sprintf(ret,"%.1f/%.1f%s",usedMB,totalMB,unit);

  return std::string(ret);

}

std::string HashTable::GetStr(int128_t *i) {

  std::string ret;
  char tmp[256];
  for(int n=3;n>=0;n--) {
    ::sprintf(tmp,"%08X",i->i32[n]); 
    ret += std::string(tmp);
  }
  return ret;

}

void HashTable::SaveTable(FILE* f) {
  SaveTable(f,0,HASH_SIZE,true);
}

void HashTable::SaveTable(FILE* f,uint32_t from,uint32_t to,bool printPoint) {

  uint64_t point = GetNbItem() / 16;
  uint64_t pointPrint = 0;

  for(uint32_t h = from; h < to; h++) {
    fwrite(&E[h].nbItem,sizeof(uint32_t),1,f);
    fwrite(&E[h].maxItem,sizeof(uint32_t),1,f);
    for(uint32_t i = 0; i < E[h].nbItem; i++) {
      fwrite(&(E[h].items[i]->x),16,1,f);
      fwrite(&(E[h].items[i]->d),16,1,f);
      if(printPoint) {
        pointPrint++;
        if(pointPrint > point) {
          ::printf(".");
          pointPrint = 0;
        }
      }
    }
  }

}

void HashTable::SeekNbItem(FILE* f,bool restorePos) {

  Reset();

#ifdef WIN64
  uint64_t org = (uint64_t)_ftelli64(f);
#else
  uint64_t org = (uint64_t)ftello(f);
#endif

  SeekNbItem(f,0,HASH_SIZE);

  if( restorePos ) {
    // Restore position
#ifdef WIN64
    _fseeki64(f,org,SEEK_SET);
#else
    fseeko(f,org,SEEK_SET);
#endif
  }

}

void HashTable::SeekNbItem(FILE* f,uint32_t from,uint32_t to) {

  for(uint32_t h = from; h < to; h++) {

    fread(&E[h].nbItem,sizeof(uint32_t),1,f);
    fread(&E[h].maxItem,sizeof(uint32_t),1,f);

    uint64_t hSize = 32ULL * E[h].nbItem;
#ifdef WIN64
    _fseeki64(f,hSize,SEEK_CUR);
#else
    fseeko(f,hSize,SEEK_CUR);
#endif

  }

}

void HashTable::LoadTable(FILE* f,uint32_t from,uint32_t to) {

  Reset();

  for(uint32_t h = from; h < to; h++) {

    fread(&E[h].nbItem,sizeof(uint32_t),1,f);
    fread(&E[h].maxItem,sizeof(uint32_t),1,f);

    if(E[h].maxItem > 0)
      // Allocate indexes
      E[h].items = (ENTRY**)malloc(sizeof(ENTRY*) * E[h].maxItem);

    for(uint32_t i = 0; i < E[h].nbItem; i++) {
      ENTRY* e = (ENTRY*)malloc(sizeof(ENTRY));
      fread(&(e->x),16,1,f);
      fread(&(e->d),16,1,f);
      E[h].items[i] = e;
    }

  }


}

void HashTable::LoadTable(FILE *f) {

  LoadTable(f,0,HASH_SIZE);

}

void HashTable::PrintInfo() {

  uint16_t max = 0;
  uint32_t maxH = 0;
  uint16_t min = 65535;
  uint32_t minH = 0;
  double std = 0;
  double avg = (double)GetNbItem() / (double)HASH_SIZE;

  for(uint32_t h=0;h<HASH_SIZE;h++) {
    if(E[h].nbItem>max) {
      max= E[h].nbItem;
      maxH = h;
    }
    if(E[h].nbItem<min) {
      min= E[h].nbItem;
      minH = h;
    }
    std += (avg - (double)E[h].nbItem)*(avg - (double)E[h].nbItem);
  }
  std /= (double)HASH_SIZE;
  std = sqrt(std);

  uint64_t count = GetNbItem();

  ::printf("DP Size   : %s\n",GetSizeInfo().c_str());
#ifdef WIN64
  ::printf("DP Count  : %I64d 2^%.3f\n",count,log2((double)count));
#else
  ::printf("DP Count  : %" PRId64 " 2^%.3f\n",count,log2(count));
#endif
  ::printf("HT Max    : %d [@ %06X]\n",max,maxH);
  ::printf("HT Min    : %d [@ %06X]\n",min,minH);
  ::printf("HT Avg    : %.2f \n",avg);
  ::printf("HT SDev   : %.2f \n",std);

  //for(int i=0;i<(int)E[maxH].nbItem;i++) {
  //  ::printf("[%2d] %s\n",i,GetStr(&E[maxH].items[i]->x).c_str());
  //  ::printf("[%2d] %s\n",i,GetStr(&E[maxH].items[i]->d).c_str());
  //}

}