/*
   Unix SMB/Netbios implementation.
   Version 1.9.
   simple bitmap functions
   Copyright (C) Andrew Tridgell 1992-1998

   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 of the License, 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; if not, write to the Free Software
   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include "includes.h"


#define	BITMAP_ALIGN	32
#define	UINT32_BITS	32
#define UINT32_ALLONE	(0xffffffffUL)

/* these functions provide a simple way to allocate integers from a
   pool without repitition */

static int     find_bitmap_one( uint32 bitmaps );

/****************************************************************************
allocate a bitmap of the specified size
****************************************************************************/
struct bitmap *bitmap_allocate(int n)
{
    size_t        structsize, bitmapsize;
    struct bitmap *bm;

    structsize  = sizeof(*bm);
    bitmapsize  = ( sizeof( bm->b[0] ) * ( n + UINT32_BITS-1 )/ UINT32_BITS );

    bm  = (struct bitmap *)malloc( structsize + bitmapsize );
    if (!bm) {
		return NULL;
	}

    bm->n  = n;
    bm->b  = (uint32 *)(bm+1);

    memset( bm->b, 0, bitmapsize );
	return bm;
}

/****************************************************************************
free a bitmap.
****************************************************************************/

void bitmap_free(struct bitmap *bm)
{
	if (!bm)
		return;

	SAFE_FREE(bm->b);
	SAFE_FREE(bm);
}

/****************************************************************************
set a bit in a bitmap
****************************************************************************/
BOOL bitmap_set(struct bitmap *bm, unsigned i)
{
	if (i >= bm->n) {
		DEBUG(0,("Setting invalid bitmap entry %d (of %d)\n",
		      i, bm->n));
		return False;
	}
	bm->b[i/UINT32_BITS] |= (1<<(i%UINT32_BITS));
	return True;
}

/****************************************************************************
clear a bit in a bitmap
****************************************************************************/
BOOL bitmap_clear(struct bitmap *bm, unsigned i)
{
	if (i >= bm->n) {
		DEBUG(0,("clearing invalid bitmap entry %d (of %d)\n",
		      i, bm->n));
		return False;
	}
	bm->b[i/UINT32_BITS] &= ~(1<<(i%UINT32_BITS));
	return True;
}

/****************************************************************************
query a bit in a bitmap
****************************************************************************/
BOOL bitmap_query(struct bitmap *bm, unsigned i)
{
	if (i >= bm->n) return False;
	if (bm->b[i/UINT32_BITS] & (1<<(i%UINT32_BITS))) {
		return True;
	}
	return False;
}

/****************************************************************************
find a zero bit in a bitmap starting at the specified offset, with
wraparound
****************************************************************************/
int bitmap_find(struct bitmap *bm, unsigned ofs)
{
    uint32	ofs_negimage;
    uint32	cur_negimage;
    int         ofsseg, ofsoff;
    int         iseg;
    int		result;

    if ( ofs >= bm->n ) {
        ofs     = 0;
    }

    ofsseg      = ofs / UINT32_BITS;
    ofsoff	= ofs % UINT32_BITS;

    /* first, we have to treat first segment special */
    ofs_negimage = ( ~( bm->b[ofsseg] ));

    cur_negimage	= ofs_negimage & ( UINT32_ALLONE << ofsoff );
    ofs_negimage	= ofs_negimage & ( ~( UINT32_ALLONE << ofsoff ));

    result	= find_bitmap_one( cur_negimage );
    if ( result >= 0 ) {
        if ( result + ( ofsseg * UINT32_BITS ) < bm->n ) {
            return result + ( ofsseg * UINT32_BITS );
        }
    }

    for ( iseg = ofsseg+1;
          iseg < (( bm->n + UINT32_BITS - 1) / UINT32_BITS ); iseg++ ) {
        result  = find_bitmap_one( ~(bm->b[iseg]) );
        if ( result >= 0 ) {

            /* This is bit special case. you might be over-running */
            if ( result + ( iseg * UINT32_BITS ) < bm->n ) {
                return result + ( iseg * UINT32_BITS );
            }
        }
    }

    for ( iseg = 0; iseg < ofsseg; iseg++ ) {
        result  = find_bitmap_one( ~(bm->b[iseg]) );
        if ( result >= 0 ) {
            return result + ( iseg * UINT32_BITS );
        }
    }

    /* finally look at first segment again */
    if ( ofs_negimage ) {
        result  = find_bitmap_one( ofs_negimage );
        if ( result >= 0 ) {
            return result + ( ofsseg * UINT32_BITS );
        }
    }

    return -1;
}


/*
 * find bit with 1, from LSB.
 *
 * I first saw this hack at X11R3's source code. I don't know where it
 * came from. --- Kenichi Okuyama.
 */
static int find_bitmap_one( uint32 bitmaps )
{
    uint32	only_lsb_is_one;
    int         result;

    /* Somebody, tell me if you know. Who first found this ? */
    only_lsb_is_one	= bitmaps & (( ~bitmaps )+ 1 );

    if ( only_lsb_is_one ) {
        result  = 0;

        if ( !( only_lsb_is_one & 0xffff )) {
            result      += 16;
            only_lsb_is_one	>>= 16;
        }

        if ( !( only_lsb_is_one & 0xff )) {
            result      += 8;
            only_lsb_is_one	>>= 8;
        }

        if ( !( only_lsb_is_one & 0xf )) {
            result      += 4;
            only_lsb_is_one	>>= 4;
		}

        if ( !( only_lsb_is_one & 0x3 )) {
            result      += 2;
            only_lsb_is_one	>>= 2;
	}

        if ( !( only_lsb_is_one & 0x1 )) {
            result      += 1;
            only_lsb_is_one	>>= 1;
        }

        return result;
    }
	return -1;
}