/****************************************************************************
 * Copyright (C) 2009-2015 EPAM Systems
 * 
 * This file is part of Indigo toolkit.
 * 
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 3 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 ***************************************************************************/

#include <stdlib.h>
#include <string.h>

#include "base_c/bitarray.h"

int bitGetBit (const void *bitarray, int bitno)
{
   return ((((char *)bitarray)[bitno / 8] & (char)(1 << (bitno % 8))) == 0) ? 0 : 1;
}

void bitSetBit (void *bitarray, int bitno, int value)
{
   if (value)
      ((char *)bitarray)[bitno / 8] |= (1 << (bitno % 8));
   else
      ((char *)bitarray)[bitno / 8] &= ~(1 << (bitno % 8));
}

void bitFlipBit (void *bitarray, int bitno)
{
   ((char *)bitarray)[bitno / 8] ^= (1 << (bitno % 8));
}


int bitTestEquality (const void *bits1, const void *bits2, int nbits)
{
   char *chars1 = (char *)bits1;
   char *chars2 = (char *)bits2;
   char mask = ~(0xFF << (nbits & 7));
   int i;

   for (i = 0; i < nbits / 8; i++)
      if (chars1[i] != chars2[i])
         return 0;

   if ((chars1[nbits / 8] & mask) != (chars2[nbits / 8] & mask))
      return 0;

   return 1;
}

int bitTestEquality_Array (const void *bits, const void *bitarray, 
                           int array_start, int nbits)
{
   int i;

   for (i = 0; i < nbits; i++)
      if (bitGetBit(bits, i) != bitGetBit(bitarray, array_start + i))
         return 0;

   return 1;
}

int bitTestEqualityByMask (const void *bits1, const void *bits2, const void *bitMaskVoid, int nbits)
{
   const char *chars1 = (const char *)bits1;
   const char *chars2 = (const char *)bits2;
   const char *bitMask = (const char *)bitMaskVoid;
   char mask = ~(0xFF << (nbits & 7));
   int i;

   for (i = 0; i < nbits / 8; i++)
      if ((chars1[i] & bitMask[i]) != (chars2[i] & bitMask[i]))
         return 0;

   if (((chars1[nbits / 8] & bitMask[nbits / 8]) & mask) != ((chars2[nbits / 8] & bitMask[nbits / 8]) & mask))
      return 0;

   return 1;
}

// res = a & (b ^ ~c)
int bitGetAandBxorNotC (const void *a, const void *b, const void *c, void *res, int nbits)
{
   const char *ac = (const char *)a;
   const char *bc = (const char *)b;
   const char *cc = (const char *)c;
   char *rc = (char *)res;
   int i;

   for (i = 0; i < nbits / 8; i++)
      rc[i] = ac[i] & (bc[i] ^ ~cc[i]);

   if ((nbits & 7) != 0)
      rc[i] = ac[i] & (bc[i] ^ ~cc[i]);

   return 1;
}

int bitGetOnesCountByte (byte value)
{
   static const int onesCount[] = 
     {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
      1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
      1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
      2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
      1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
      2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
      2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
      3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
      1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
      2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
      2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
      3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
      2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
      3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
      3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
      4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};
   return onesCount[value];
}

int bitGetOnesCountDword (dword v)
{
   // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
   v = v - ((v >> 1) & 0x55555555);                       // reuse input as temporary
   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);        // temp
   return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
}

int bitGetOnesCountQword (qword value)
{
   return bitGetOnesCountDword((dword)value) + bitGetOnesCountDword((dword)(value >> 32));
}

int bitGetOnesCount (const byte *data, int size)
{
   int count = 0;
   while (size-- > 0)
      count += bitGetOnesCountByte(*data++);
   return count;
}

int bitGetOneHOIndex  (byte value)
{
   static const int oneHOIndex[] =
     {0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
      5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
      6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
      6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
      8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8};
   return oneHOIndex[value];
}

int bitGetOneLOIndex  (byte value)
{
   static const int oneLOIndex[] =
     {8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
      4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0};
   return oneLOIndex[value];
}

int bitGetSize (int nbits)
{
   return (nbits + 7) / 8;
}

int bitTestOnes (const byte *pattern, const byte *candidate, int n_bytes)
{
   int qwords_count = n_bytes / sizeof(qword);
   int bytes_left = n_bytes - qwords_count * sizeof(qword);

   const qword *pattern_ptr = (const qword *)pattern;
   const qword *candidate_ptr = (const qword *)candidate;
   while (qwords_count-- > 0)
   {
      if ((*candidate_ptr & *pattern_ptr) != *pattern_ptr)
         return 0;
      pattern_ptr++;
      candidate_ptr++;
   }

   if (bytes_left != 0)
   {
      qword mask = ~(qword)0 >> (64 - 8 * bytes_left);

      if ((*candidate_ptr & *pattern_ptr & mask) != (*pattern_ptr & mask))
         return 0;
   }
   return 1;
}

int bitIdecticalBits (const byte *bit1, const byte *bit2, int n_bytes)
{
   int qwords_count = n_bytes / sizeof(qword);
   int bytes_left = n_bytes - qwords_count * sizeof(qword);

   int count = 0;
   const qword *bit1_ptr = (const qword *)bit1;
   const qword *bit2_ptr = (const qword *)bit2;
   while (qwords_count-- > 0)
   {
      qword id = ~(*bit1_ptr ^ *bit2_ptr);
      count += bitGetOnesCountQword(id);

      bit1_ptr++;
      bit2_ptr++;
   }

   if (bytes_left != 0)
   {
      qword mask = ~(qword)0 >> (64 - 8 * bytes_left);
      qword id = (~(*bit1_ptr ^ *bit2_ptr)) & mask;
      count += bitGetOnesCountQword(id);
   }
   return count;
}

int bitCommonOnes (const byte *bit1, const byte *bit2, int n_bytes)
{
   int qwords_count = n_bytes / sizeof(qword);
   int bytes_left = n_bytes - qwords_count * sizeof(qword);

   int count = 0;
   const qword *bit1_ptr = (const qword *)bit1;
   const qword *bit2_ptr = (const qword *)bit2;
   while (qwords_count-- > 0)
   {
      qword id = *bit1_ptr & *bit2_ptr;
      count += bitGetOnesCountQword(id);

      bit1_ptr++;
      bit2_ptr++;
   }

   if (bytes_left != 0)
   {
      qword mask = ~(qword)0 >> (64 - 8 * bytes_left);
      qword id = *bit1_ptr & *bit2_ptr & mask;
      count += bitGetOnesCountQword(id);
   }
   return count;
}

int bitUniqueOnes (const byte *bit1, const byte *bit2, int n_bytes)
{
   int qwords_count = n_bytes / sizeof(qword);
   int bytes_left = n_bytes - qwords_count * sizeof(qword);

   int count = 0;
   const qword *bit1_ptr = (const qword *)bit1;
   const qword *bit2_ptr = (const qword *)bit2;
   while (qwords_count-- > 0)
   {
      qword id = *bit1_ptr & ~*bit2_ptr;
      count += bitGetOnesCountQword(id);

      bit1_ptr++;
      bit2_ptr++;
   }

   if (bytes_left != 0)
   {
      qword mask = ~(qword)0 >> (64 - 8 * bytes_left);
      qword id = *bit1_ptr & ~*bit2_ptr & mask;
      count += bitGetOnesCountQword(id);
   }
   return count;
}

int bitDifferentOnes (const byte *bit1, const byte *bit2, int n_bytes)
{
   int qwords_count = n_bytes / sizeof(qword);
   int bytes_left = n_bytes - qwords_count * sizeof(qword);

   int count = 0;
   const qword *bit1_ptr = (const qword *)bit1;
   const qword *bit2_ptr = (const qword *)bit2;
   while (qwords_count-- > 0)
   {
      qword id = *bit1_ptr ^ *bit2_ptr;
      count += bitGetOnesCount((byte*)&id, sizeof(qword));

      bit1_ptr++;
      bit2_ptr++;
   }

   if (bytes_left != 0)
   {
      qword mask = ~(qword)0 >> (64 - 8 * bytes_left);
      qword id = (*bit1_ptr ^ *bit2_ptr) & mask;
      count += bitGetOnesCountQword(id);
   }
   return count;
}

int bitUnionOnes (const byte *bit1, const byte *bit2, int n_bytes)
{
   int qwords_count = n_bytes / sizeof(qword);
   int bytes_left = n_bytes - qwords_count * sizeof(qword);

   int count = 0;
   const qword *bit1_ptr = (const qword *)bit1;
   const qword *bit2_ptr = (const qword *)bit2;
   while (qwords_count-- > 0)
   {
      qword id = *bit1_ptr | *bit2_ptr;
      count += bitGetOnesCountQword(id);

      bit1_ptr++;
      bit2_ptr++;
   }

   if (bytes_left != 0)
   {
      qword mask = ~(qword)0 >> (64 - 8 * bytes_left);
      qword id = (*bit1_ptr | *bit2_ptr) & mask;
      count += bitGetOnesCountQword(id);
   }
   return count;
}

// a &= b
void bitAnd (byte *a, const byte *b, int nbytes)
{
   while (nbytes-- > 0)
   {
      *a = *a & *b;
      a++;
      b++;
   }
}

// a |= b
void bitOr (byte *a, const byte *b, int nbytes)
{
   while (nbytes-- > 0)
   {
      *a = *a | *b;
      a++;
      b++;
   }
}

int bitIsAllZero (const void *bits, int nbytes)
{
   const byte *a = (const byte *)bits;

   while (nbytes-- > 0)
   {
      if (*a != 0)
         return 0;
      a++;
   }
   return 1;
}

int bitLog2Dword (dword input)
{
   int count = 0;
   while (input > 0)
   {
      count++;
      input >>= 1;
   }
   return count;
}