/* Pepito v1.59  -- file: bitop.c --
   Copyright (c) 2000-02 Carlos del Cacho

   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; either version 2, or (at your option)
   any later version.

   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; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.

   Contact the author: guggenjaimito@yahoo.com
*/

#ifndef UNIQUE_SOURCE_FILE
#  include <stdlib.h>
#  include "datos.h"
#endif

#define m1 ((entero64) 0x5555555555555555)
#define m2 ((entero64) 0x3333333333333333)

#define ma1 (entero64) 0xffff000000000000
#define ma2 (entero64) 0x0000ffff00000000
#define ma3 (entero64) 0x00000000ffff0000
#define ma4 (entero64) 0x000000000000ffff



#ifndef USE_ASSEMBLY
//----------------------------------------------------------------------------------
#ifdef USE_LOOKUP
/* A list of the number of bits in numbers from 0-255. */
static int      inbits[256] = {
    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,
};
// contador de bits by table lookup (D. Corbit)
int             PopCnt(entero64 B)
{
    return inbits[(unsigned char) B] +
    inbits[(unsigned char) (B >> 8)] +
    inbits[(unsigned char) (B >> 16)] +
    inbits[(unsigned char) (B >> 24)] +
    inbits[(unsigned char) (B >> 32)] +
    inbits[(unsigned char) (B >> 40)] +
    inbits[(unsigned char) (B >> 48)] +
    inbits[(unsigned char) (B >> 56)];
}
#else
// contador de bits iterativo
int             PopCnt(entero64 b)
{
    unsigned int    n;
    for (n = 0; b; n++, b &= (b - 1));
    return n;
}
#endif
#endif
//----------------------------------------------------------------------
// contador de bits no iterativo para un entero de 8 bytes (Ernst Heinz)

unsigned int    non_iterative_popcount(const entero64 b)
{
    unsigned long   n;
    const entero64  a = b - ((b >> 1) & m1);
    const entero64  c = (a & m2) + ((a >> 2) & m2);

    n = ((unsigned long) c) + ((unsigned long) (c >> 32));
    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
    n = (n & 0xFFFF) + (n >> 16);
    n = (n & 0xFF) + (n >> 8);
    return n;
}
//------------------------------------------------------------------
// función q calcula la posición del MSB del índice num

int             Calc_MSB(int num)
{
    int             i;
    for (i = 15; !(num & 0x8000) && (num); i--, num <<= 1);
    return (num ? i : 0);
}
//----------------------------------------------------------------------------------
// función q calcula la posición del LSB del índice num

int             Calc_LSB(int num)
{
    int             i;
    for (i = 0; !(num & 0x0001) && (num); i++, num >>= 1);
    return (num ? i : 0);
}
//----------------------------------------------------------------------------------
// inicialización de las tablas LSB y MSB. Debe ser llamada
// antes de cualquier otra referencia a Lsb y Msb (salvo en el caso de q empleemos
// las versiones en ensamblador).

void            Init_MSB(char msb[], char lsb[])
{
    int             n;
    for (n = 0; n < 65536; n++) {
        msb[n] = Calc_MSB(n);
        lsb[n] = Calc_LSB(n);
    }
}
//----------------------------------------------------------------------------------
#define ma1 (entero64) 0xffff000000000000
#define ma2 (entero64) 0x0000ffff00000000
#define ma3 (entero64) 0x00000000ffff0000
#define ma4 (entero64) 0x000000000000ffff

//#define USE_ASSEMBLY


// devuelve la posición del MSB en un entero de 8 bytes

int             MsbC(register entero64 num)
{
    if (num & ma1)
        return (48 + MSB[num >> 48]);
    else if (num & ma2)
        return (32 + MSB[num >> 32]);
    else if (num & ma3)
        return (16 + MSB[num >> 16]);
    else
        return MSB[num];
}


//----------------------------------------------------------------------------------
// devuelve la posición del LSB en un entero de 8 bytes

int             LsbC(register entero64 num)
{
    if (num & ma4)
        return (LSB[num & ma4]);
    else if (num & ma3)
        return (16 + LSB[(num & ma3) >> 16]);
    else if (num & ma2)
        return (32 + LSB[(num & ma2) >> 32]);
    else
        return (48 + LSB[num >> 48]);
}
//----------------------------------------------------------------------------------
