#include "clusterautoconfig.h"

#include <inttypes.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <limits.h>

#include "libgfs2.h"

#if BITS_PER_LONG == 32
#define LBITMASK   (0x55555555UL)
#define LBITSKIP55 (0x55555555UL)
#define LBITSKIP00 (0x00000000UL)
#else
#define LBITMASK   (0x5555555555555555UL)
#define LBITSKIP55 (0x5555555555555555UL)
#define LBITSKIP00 (0x0000000000000000UL)
#endif

#define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))

/**
 * gfs2_bit_search
 * @ptr: Pointer to bitmap data
 * @mask: Mask to use (normally 0x55555.... but adjusted for search start)
 * @state: The state we are searching for
 *
 * We xor the bitmap data with a patter which is the bitwise opposite
 * of what we are looking for, this gives rise to a pattern of ones
 * wherever there is a match. Since we have two bits per entry, we
 * take this pattern, shift it down by one place and then and it with
 * the original. All the even bit positions (0,2,4, etc) then represent
 * successful matches, so we mask with 0x55555..... to remove the unwanted
 * odd bit positions.
 *
 * This allows searching of a whole u64 at once (32 blocks) with a
 * single test (on 64 bit arches).
 */

static inline uint64_t gfs2_bit_search(const unsigned long long *ptr,
				       unsigned long long mask,
				       uint8_t state)
{
	unsigned long long tmp;
	static const unsigned long long search[] = {
		[0] = 0xffffffffffffffffULL,
		[1] = 0xaaaaaaaaaaaaaaaaULL,
		[2] = 0x5555555555555555ULL,
		[3] = 0x0000000000000000ULL,
	};
	tmp = le64_to_cpu(*ptr) ^ search[state];
	tmp &= (tmp >> 1);
	tmp &= mask;
	return tmp;
}

/**
 * gfs2_bitfit - Find a free block in the bitmaps
 * @buffer: the buffer that holds the bitmaps
 * @buflen: the length (in bytes) of the buffer
 * @goal: the block to try to allocate
 * @old_state: the state of the block we're looking for
 *
 * Return: the block number that was allocated
 */
unsigned long gfs2_bitfit(const unsigned char *buf, const unsigned int len,
			  unsigned long goal, unsigned char state)
{
	unsigned long spoint = (goal << 1) & ((8 * sizeof(unsigned long long)) - 1);
	const unsigned long long *ptr = ((unsigned long long *)buf) + (goal >> 5);
	const unsigned long long *end = (unsigned long long *)
		(buf + ALIGN(len, sizeof(unsigned long long)));
	unsigned long long tmp;
	unsigned long long mask = 0x5555555555555555ULL;
	unsigned long bit;

	if (state > 3)
		return 0;

	/* Mask off bits we don't care about at the start of the search */
	mask <<= spoint;
	tmp = gfs2_bit_search(ptr, mask, state);
	ptr++;
	while(tmp == 0 && ptr < end) {
		tmp = gfs2_bit_search(ptr, 0x5555555555555555ULL, state);
		ptr++;
	}
	/* Mask off any bits which are more than len bytes from the start */
	if (ptr == end && (len & (sizeof(unsigned long long) - 1)))
		tmp &= (((unsigned long long)~0) >>
			(64 - 8 * (len & (sizeof(unsigned long long) - 1))));
	/* Didn't find anything, so return */
	if (tmp == 0)
		return BFITNOENT;
	ptr--;
	bit = ffsll(tmp);
	bit /= 2;	/* two bits per entry in the bitmap */
	return (((const unsigned char *)ptr - buf) * GFS2_NBBY) + bit;
}

/*
 * check_range - check if blkno is within FS limits
 * @sdp: super block
 * @blkno: block number
 *
 * Returns: 0 if ok, -1 if out of bounds
 */
int gfs2_check_range(struct gfs2_sbd *sdp, uint64_t blkno)
{
	if((blkno > sdp->fssize) || (blkno <= LGFS2_SB_ADDR(sdp)))
		return -1;
	return 0;
}

/*
 * gfs2_set_bitmap
 * @sdp: super block
 * @blkno: block number relative to file system
 * @state: one of three possible states
 *
 * This function sets the value of a bit of the
 * file system bitmap.
 *
 * Returns: 0 on success, -1 on error
 */
int gfs2_set_bitmap(lgfs2_rgrp_t rgd, uint64_t blkno, int state)
{
	int           buf;
	uint32_t        rgrp_block;
	struct gfs2_bitmap *bits = NULL;
	unsigned char *byte, cur_state;
	unsigned int bit;

	/* FIXME: should GFS2_BLKST_INVALID be allowed */
	if ((state < GFS2_BLKST_FREE) || (state > GFS2_BLKST_DINODE))
		return -1;

	if(!rgd || blkno < rgd->ri.ri_data0)
		return -1;

	rgrp_block = (uint32_t)(blkno - rgd->ri.ri_data0);
	for(buf= 0; buf < rgd->ri.ri_length; buf++){
		bits = &(rgd->bits[buf]);
		if(rgrp_block < ((bits->bi_start + bits->bi_len)*GFS2_NBBY))
			break;
	}

	if (bits == NULL)
		return -1;
	byte = (unsigned char *)(bits->bi_bh->b_data + bits->bi_offset) +
		(rgrp_block/GFS2_NBBY - bits->bi_start);
	bit = (rgrp_block % GFS2_NBBY) * GFS2_BIT_SIZE;

	cur_state = (*byte >> bit) & GFS2_BIT_MASK;
	*byte ^= cur_state << bit;
	*byte |= state << bit;

	bmodified(bits->bi_bh);
	return 0;
}

/*
 * gfs2_get_bitmap - get value of FS bitmap
 * @sdp: super block
 * @blkno: block number relative to file system
 *
 * This function gets the value of a bit of the
 * file system bitmap.
 * Possible state values for a block in the bitmap are:
 *  GFS_BLKST_FREE     (0)
 *  GFS_BLKST_USED     (1)
 *  GFS_BLKST_INVALID  (2)
 *  GFS_BLKST_DINODE   (3)
 *
 * Returns: state on success, -1 on error
 */
int lgfs2_get_bitmap(struct gfs2_sbd *sdp, uint64_t blkno, struct rgrp_tree *rgd)
{
	uint64_t offset;
	uint32_t i = 0;
	char *byte;
	unsigned int bit;
	struct gfs2_bitmap *bi;

	if (rgd == NULL) {
		rgd = gfs2_blk2rgrpd(sdp, blkno);
		if(rgd == NULL)
			return -1;
	}

	offset = blkno - rgd->ri.ri_data0;
	if (offset > UINT_MAX) {
		errno = EINVAL;
		return -1;
	}
	if (offset >= rgd->ri.ri_data0 + rgd->ri.ri_data) {
		errno = E2BIG;
		return -1;
	}

	if (offset >= (rgd->bits->bi_start + rgd->bits->bi_len) * GFS2_NBBY) {
		offset += (sizeof(struct gfs2_rgrp) - sizeof(struct gfs2_meta_header))
		          * GFS2_NBBY;
		i = offset / sdp->sd_blocks_per_bitmap;
		offset -= i * sdp->sd_blocks_per_bitmap;
	}

	bi = &rgd->bits[i];
	if (!bi->bi_bh)
		return GFS2_BLKST_FREE;

	byte = (bi->bi_bh->b_data + bi->bi_offset) + (offset/GFS2_NBBY);
	bit = (offset % GFS2_NBBY) * GFS2_BIT_SIZE;

	return (*byte >> bit) & GFS2_BIT_MASK;
}