/* ============================================================
 * Copyright (c) 2014 Actifio Inc. All Rights Reserved
 * =============================================================
 */

#include <stdlib.h>
#include <assert.h>
#include <sys/stat.h>
#include <errno.h>
#include <stdbool.h>
#include <fcntl.h>

#include "bitmap.h"

extern int verbosity;

#define COMPRESSION_LEVEL 6

ram_bitmap_t *bitmap_create(uint64_t volsize, unsigned int grainsize)
{
        uint64_t size = sizeof(fc_bitmap_hdr_t) + sizeof(fc_bitmap_mq_hdr_t);
        /* Roundup to grainsize and to the next byte */
        uint64_t bmsize = (((volsize + grainsize - 1) / grainsize) + 8 - 1) / 8;

        if (volsize % LBAS_SIZE || grainsize % LBAS_SIZE) {
                printf("Invalid alignment: volsize/grainsize %"PRIi64"/%u "
                       "should be multible of LBAS %u\n", volsize, grainsize, LBAS_SIZE);
                return NULL;
        }
        if (volsize % grainsize) {
                printf("Invalid alignment: volsize %"PRIi64" should be multible of grainsize %u\n",
                       volsize, grainsize);
                return NULL;
        }
        size += bmsize;

        ram_bitmap_t * bitmap = (ram_bitmap_t *) malloc(size);

        assert(bitmap);
        memset(bitmap,0,size);

        bitmap->mqhdr.grain_size_lbas = grainsize/LBAS_SIZE;
        bitmap->mqhdr.vdisk_size_lbas = volsize/LBAS_SIZE;      
        bitmap->mqhdr.bitmap_size_bytes = bmsize;

        bitmap->mqhdr.bitmap_mq_magic[0] = ((FC_BITMAP_MQ_MAGIC >> 24) & 0xFF);
        bitmap->mqhdr.bitmap_mq_magic[1] = ((FC_BITMAP_MQ_MAGIC >> 16) & 0xFF);
        bitmap->mqhdr.bitmap_mq_magic[2] = ((FC_BITMAP_MQ_MAGIC >>  8) & 0xFF);
        bitmap->mqhdr.bitmap_mq_magic[3] = (FC_BITMAP_MQ_MAGIC & 0xFF);

        // Let's make sure we did this right.
        assert( bitmap->mqhdr.bitmap_size_bytes == bmsize);

        return bitmap;
}

ram_bitmap_t *bitmap_dup(ram_bitmap_t *bitmap)
{
	ram_bitmap_t *new_bitmap =
		bitmap_create(bitmap->mqhdr.vdisk_size_lbas*LBAS_SIZE,
			      bitmap->mqhdr.grain_size_lbas*LBAS_SIZE);
	if (new_bitmap)
		bcopy(&(bitmap->bits[0]), &(new_bitmap->bits[0]),
		      bitmap->mqhdr.bitmap_size_bytes);

	return (new_bitmap);
}

void bitmap_destroy(ram_bitmap_t *bitmap)
{
        free(bitmap);
}

ram_bitmap_pair_t *bitmap_pair_create(uint64_t volsize, unsigned int grainsize)
{
        ram_bitmap_pair_t *pair = malloc(sizeof(ram_bitmap_pair_t));
        if (pair == NULL)
		return NULL;

	pair->diff_bitmap = bitmap_create(volsize, grainsize);
	if (pair->diff_bitmap == NULL) {
		free(pair);
		return NULL;
	}

	pair->free_bitmap = bitmap_create(volsize, grainsize);
	if (pair->free_bitmap == NULL) {
		free(pair->diff_bitmap);
		free(pair);
		return NULL;
	}

	return pair;
}

void bitmap_pair_destroy(ram_bitmap_pair_t *pair)
{
	if (pair) {
		if (pair->free_bitmap)
			bitmap_destroy(pair->free_bitmap);
		if (pair->diff_bitmap)
			bitmap_destroy(pair->diff_bitmap);
		free(pair);
	}
}

void bitmap_addbit(ram_bitmap_t *diffbitmap, uint64_t rangeaddr, uint64_t rangesize)
{
        /*
         * Get the (first) grain that contains rangeaddr, get the (last) grain that contains
         * rangeadd+rangesize, then walk through the range of grains including the last 
         * changed grain and set the bits
         */
        uint64_t start_block = rangeaddr/(diffbitmap->mqhdr.grain_size_lbas * LBAS_SIZE);
        uint64_t end_block = (rangeaddr + rangesize - 1)/(diffbitmap->mqhdr.grain_size_lbas * LBAS_SIZE);
        uint64_t b;

        for (b = start_block; b <= end_block; b++) {
                uint64_t byte_idx = b / 8;
                int bit_idx = b % 8;
                diffbitmap->bits[byte_idx] |= (uint8_t)(1 << bit_idx);
        }
}

void bitmap_fwrite(const void *ptr, size_t size, size_t nmemb,
    FILE *stream)
{
        if (fwrite(ptr, size, nmemb, stream) != nmemb)
        {
                fprintf(stderr,"Error: cannot write to bitmap file\n");
                exit(-1);
        }
}


bool is_buffer_zeroed(unsigned char *buffer, uint64_t size)
{
    return !(bool)(*buffer || memcmp(buffer, buffer + 1, (size_t)size - 1));
}

/* This routine will keep calling pwrite until all the bytes in a block gets written. 
 * Subsequent pwrite calls will attempt to write only the remaining bytes. 
 * At any point of time if pwrite returns a value <= 0, error will be thrown.
 */
int pwrite_data(const int fd, const void *buf, size_t size, off_t write_offset)
{
        off_t read_offset = 0;
        int rem = size;
        while (rem) {
                int nbytes = pwrite(fd, buf + read_offset, rem, write_offset);
                if (nbytes <= 0)
                        return -1;
                rem -= nbytes;
                read_offset += nbytes;
                write_offset += nbytes;
        }
        return 0;
}
/* 
 * Write bitmap portion (without headers) of ram_bitmap_t in sparse manner
 */
int bitmap_write_sparse(const int fd, uint64_t bitmap_size_bytes, unsigned char *buf)
{
        ftruncate(fd, (FC_BITMAP_BITMAP_OFFSET + bitmap_size_bytes));
        int64_t i, remainder, chunks;
        off_t read_offset = 0;
        off_t write_offset = FC_BITMAP_BITMAP_OFFSET;
        chunks = bitmap_size_bytes / LBAS_SIZE;
        remainder = bitmap_size_bytes % LBAS_SIZE;

        for (i = 0; i < chunks; i++) {
                if (!(is_buffer_zeroed(&buf[read_offset], LBAS_SIZE))) {
                        if (pwrite_data(fd, buf + read_offset, LBAS_SIZE, write_offset) < 0)
                                return -1;
                }
                read_offset += LBAS_SIZE;
                write_offset += LBAS_SIZE;
        }

        if (remainder) {
                if (pwrite_data(fd, buf + read_offset, remainder, write_offset) < 0)
                        return -1;
        }
        return 0;
}

void bitmap_write(ram_bitmap_t *diff_bitmap, const char * bitmap)
{
        struct stat sb;
        int fd = open(bitmap, O_CREAT|O_WRONLY, 0666);
        if(fd < 0) {
                fprintf(stderr,"Error: cannot create bitmap file %s: %s\n", bitmap, strerror(errno));
                exit(-1);
        }

        if(fstat(fd, &sb)) {
                fprintf(stderr,"Error: cannot retrieve file info %s: %s\n", bitmap, strerror(errno));
                close(fd);
                exit(-1);
        }
        /* write out the bm header only if this is a new file
         * for existing bitmap, bmhdr is already up to date, we just need to update mqhdr and
         * the actual bitmap
         */
        if(!sb.st_size && (pwrite_data(fd, &diff_bitmap->bmhdr, sizeof(diff_bitmap->bmhdr), 0) < 0))
                goto write_fail;

        /* mqhdr needs to be updated even if it is an already existing file. Bitmap size (initially 0)
         * and other fields of mqhdr will be modified here
         */
        if (pwrite_data(fd, &diff_bitmap->mqhdr, sizeof(diff_bitmap->mqhdr), FC_BITMAP_MQ_HDR_OFFSET) < 0)
                goto write_fail;

        if (bitmap_write_sparse(fd, diff_bitmap->mqhdr.bitmap_size_bytes, diff_bitmap->bits) < 0)
                goto write_fail;

        if (close(fd)) {
                fprintf(stderr, "Error: unable to close fd %s: %s\n", bitmap, strerror(errno));
                exit(-1);
        }
        return;

write_fail:
        fprintf(stderr, "Error: unable to write bitmap %s : %s\n", bitmap, strerror(errno));
        close(fd);
        exit(-1);
}

extern size_t gzip_compress(void *src, void *dst, size_t s_len, size_t d_len, int level);
extern int gzip_decompress(void *s_start, void *d_start, size_t s_len, size_t d_len, int n);

/*
 * Because of runs of 1s, holemap files don't sparsify well.
 * This function will compress the bitmap portion of ram_bitmap_t before
 * persisting it to the disk
 */
void holemap_write(ram_bitmap_t *free_bitmap, const char * holemap)
{
        int exists = 0;
        struct stat sb;
        size_t nread;
        FILE *bm;
        unsigned char * compressed_bitmap;

        u_int64_t size = free_bitmap->mqhdr.bitmap_size_bytes;
        compressed_bitmap = (unsigned char *) malloc(size);
        assert(compressed_bitmap);
        memset(compressed_bitmap,0,size);

        /* In some cases compression output is worse than input, and thus it won't fit. This will cause the
         * library to return failure. gzip_compress() indicates this failure by returning original input size.
         * However in failure case, gzip_compress() simply copies data from src to dest buffer if s_len, d_len
         * parameters have the same value. Therefore to avoid unnecessary copying, dst_len = src-len - 1 is
         * being passed.
         * If return value of gzip_compress() equals original size, it'll be identified as error scenario and
         * original uncompressed bitmap will be written to the disk.
         */
        u_int64_t dest_size = gzip_compress(free_bitmap->bits, compressed_bitmap, size, size-1, COMPRESSION_LEVEL);

        if(stat(holemap, &sb)==0)
                exists = 1;
  
        if (exists) {
                bm = fopen(holemap, "r+b");
		if(!bm) {
			fprintf(stderr,"Error: cannot open holemap file %s: %s\n", holemap, strerror(errno));
                        free(compressed_bitmap);
			exit(-1);
		}
                fseek(bm, 0, size);
                nread = fread(&free_bitmap->bmhdr, sizeof(free_bitmap->bmhdr), 1, bm);
	} else {
		bm = fopen(holemap, "w+b");
		if(!bm) {
			fprintf(stderr,"Error: cannot create holemap file %s: %s\n", holemap, strerror(errno));
                        free(compressed_bitmap);
			exit(-1);
		}
        }

        if (dest_size != size) {
                /* compressed length < source length 
                 * i.e. compression was successful 
                 */
                free_bitmap->bmhdr.compressed_size = dest_size;
                free_bitmap->bmhdr.is_compressed = 1;
                fseek(bm, 0, SEEK_SET);
                bitmap_fwrite(&free_bitmap->bmhdr, sizeof(free_bitmap->bmhdr), 1, bm);
                bitmap_fwrite(&free_bitmap->mqhdr, sizeof(free_bitmap->mqhdr), 1, bm);
                fseek(bm, FC_BITMAP_BITMAP_OFFSET, SEEK_SET);
                /* write compressed bitmap */
                bitmap_fwrite(compressed_bitmap, dest_size, 1, bm);
        } else {
                /* compressed length = source length: this can happen only 
                 * in case of failure
                 */
                fseek(bm, 0, SEEK_SET);
                bitmap_fwrite(&free_bitmap->bmhdr, sizeof(free_bitmap->bmhdr), 1, bm);
                bitmap_fwrite(&free_bitmap->mqhdr, sizeof(free_bitmap->mqhdr), 1, bm);
                fseek(bm, FC_BITMAP_BITMAP_OFFSET, SEEK_SET);
                /* write uncompressed bitmap */
                bitmap_fwrite(free_bitmap->bits, size, 1, bm);
        }

        free(compressed_bitmap);
        if (fclose(bm)) {
                fprintf(stderr, "Error: unable to close file %s : %s\n", holemap, strerror(errno));
                exit(-1);
        }
}

/*
 * Read bitmap/holemap file from disk.
 * holemap files will be decompressed before populating ram_bitmap_t
 */
ram_bitmap_t *bitmap_read(const char *bitmap)
{
	size_t nread, compressed_size;
        int ret;
        unsigned char * compressed_bitmap = NULL;
	fc_bitmap_mq_hdr_t mqhdr;
	ram_bitmap_t *ram_bitmap = NULL;
        FILE *bm = fopen(bitmap, "r");
        
        if (!bm)
	        goto fail;

	/* get the size of the bitmap */
	fseek(bm, FC_BITMAP_MQ_HDR_OFFSET, SEEK_SET);
        nread = fread(&mqhdr, sizeof(mqhdr), 1, bm);
	if (nread != 1)
		goto fail;

	/* create the bitmap */
	if ((ram_bitmap = bitmap_create(mqhdr.vdisk_size_lbas*LBAS_SIZE,
					mqhdr.grain_size_lbas*LBAS_SIZE)) == NULL)
		goto fail;
	
        /*
	 * now that the properly sized bitmap is created, read it in
	 * first, read the headers
	 * then, read the bits
	 */
	fseek(bm, 0, SEEK_SET);
	nread = fread (&ram_bitmap->bmhdr, sizeof(ram_bitmap->bmhdr), 1, bm);
	if (nread != 1)
		goto fail;
	
        /*
	 * this is initialized by bitmap_create(), but still rewrite,
	 * just to make sure the header is exactly the same as on disk
	 */
	ram_bitmap->mqhdr = mqhdr;
	/* read in the bitmap bits */
        fseek(bm, FC_BITMAP_BITMAP_OFFSET, SEEK_SET);

        /* check if bitmap needs to be decompressed before storing*/
        if (ram_bitmap->bmhdr.is_compressed) {
                compressed_size = ram_bitmap->bmhdr.compressed_size;
                compressed_bitmap = (unsigned char *) malloc(compressed_size);
                nread = fread(compressed_bitmap, compressed_size, 1, bm);
                if (nread != 1)
                        goto fail;
                ret = gzip_decompress(compressed_bitmap, ram_bitmap->bits, compressed_size, 
                                ram_bitmap->mqhdr.bitmap_size_bytes, COMPRESSION_LEVEL);
                if (ret < 0) {
                        fprintf(stderr,"Error: holemap file decompression failed\n");
                        goto fail;
                }
                free(compressed_bitmap);
        } else {
                nread = fread(ram_bitmap->bits, ram_bitmap->mqhdr.bitmap_size_bytes, 1, bm);
                if (nread != 1)
                        goto fail;
        }
        fclose(bm);

	return ram_bitmap;
fail:
	perror("Failed to read bitmap");
	if (bm)
		fclose(bm);
	if (ram_bitmap)
		free(ram_bitmap);
        if (compressed_bitmap)
                free(compressed_bitmap);
	return (NULL);
}


/*
 * Produce a result bitmap which is a logical OR of the
 * left- and righ-hand-side bitmap arguments
 * the lhs and rhs arguments can be of different sizes,
 * but the result has to be of the largest size
 */
int bitmap_add(ram_bitmap_t *result, ram_bitmap_t *lhs, ram_bitmap_t *rhs)
{
        fc_bitmap_mq_hdr_t *hdr_res = &(result->mqhdr),
		*hdr_lhs = &(lhs->mqhdr), *hdr_rhs = &(rhs->mqhdr);
        unsigned char *bits_res = &(result->bits[0]), *bits_lhs = &(lhs->bits[0]),
		*bits_rhs = &(rhs->bits[0]), *bits_remainder = NULL;
        uint64_t i, min_size, max_size;

        /* compare grains and sizes */
        if (hdr_lhs->grain_size_lbas != hdr_rhs->grain_size_lbas ||
	    hdr_lhs->grain_size_lbas != hdr_res->grain_size_lbas) {
                fprintf(stderr, "different bitmap grain size detected,"
			" cannot add bitmaps\n");
                return (-1);
        }

        if (hdr_lhs->bitmap_size_bytes > hdr_rhs->bitmap_size_bytes) {
		min_size = hdr_rhs->bitmap_size_bytes;
		max_size = hdr_lhs->bitmap_size_bytes;
		bits_remainder = bits_lhs;
	} else {
		min_size = hdr_lhs->bitmap_size_bytes;
		max_size = hdr_rhs->bitmap_size_bytes;
		bits_remainder = bits_rhs;
	}

        if (max_size != hdr_res->bitmap_size_bytes) {
                fprintf(stderr, "resulting bitmap is of wrong byte size,"
			" cannot add bitmaps\n");
                return (-1);
        }

	/* OR the common parts of the bitmaps */
        for (i = 0; i < min_size; i++)
                bits_res[i] = bits_lhs[i] | bits_rhs[i];

	/* fill in the rest using the larger bitmap */
	for ( ; i < max_size; i++)
		bits_res[i] = bits_remainder[i];

        return (0);
}

/*
 * Produce a result bitmap which is a logical AND of the
 * left-hand-side bitmap and the inverse of the right-hand-size bitmap
 * We will require that the rhs bitmap is not larger than the lhs bitmap,
 * and the lhs bitmap is not larger than the lhs bitmap
 */
int bitmap_subtract(ram_bitmap_t *result, ram_bitmap_t *lhs, ram_bitmap_t *rhs)
{
        fc_bitmap_mq_hdr_t *hdr_res = &(result->mqhdr),
		*hdr_lhs = &(lhs->mqhdr), *hdr_rhs = &(rhs->mqhdr);
        unsigned char *bits_res = &(result->bits[0]), *bits_lhs = &(lhs->bits[0]),
		*bits_rhs = &(rhs->bits[0]);
        uint64_t i;

        /* compare grains and byte sizes */
        if (hdr_lhs->grain_size_lbas != hdr_rhs->grain_size_lbas ||
	    hdr_lhs->grain_size_lbas != hdr_res->grain_size_lbas) {
                fprintf(stderr, "different bitmap grain sizes detected,"
			" cannot subtract bitmaps\n");
                return (-1);
        }

        if (hdr_lhs->bitmap_size_bytes < hdr_rhs->bitmap_size_bytes ||
	    hdr_res->bitmap_size_bytes < hdr_lhs->bitmap_size_bytes) {
                fprintf(stderr, "bitmap sizes are incompatible,"
			" cannot subtract bitmaps\n");
                return (-1);
	}
		
	/* subtract up to the rhs size */
        for (i = 0; i < hdr_rhs->bitmap_size_bytes; i++)
                bits_res[i] = bits_lhs[i] & (~bits_rhs[i]);

	/* copy up to the lhs size */
        for ( ; i < hdr_lhs->bitmap_size_bytes; i++)
                bits_res[i] = bits_lhs[i];

        return (0);
}


/* assumes the string of length at least 9 is managed by the caller */
char *bitmap_show_bits(char *string, const char bits)
{
	/* print out bits 0-7 left to right */
	char *ptr;
	int i;
	for (i = 0, ptr = string; i < 8; i++, ptr++) {
		sprintf(ptr, "%d", (bits & (1 << i)) >> i);
	}
	string[8] = '\0';
	return string;
}


void bitmap_show(ram_bitmap_t *bitmap, uint64_t offset)
{
    uint64_t i, j, ngrains;

    if ((bitmap->mqhdr.bitmap_mq_magic[0] != ((FC_BITMAP_MQ_MAGIC >> 24) & 0xFF)) ||
	(bitmap->mqhdr.bitmap_mq_magic[1] != ((FC_BITMAP_MQ_MAGIC >> 16) & 0xFF)) ||
	(bitmap->mqhdr.bitmap_mq_magic[2] != ((FC_BITMAP_MQ_MAGIC >>  8) & 0xFF)) ||
	(bitmap->mqhdr.bitmap_mq_magic[3] != (FC_BITMAP_MQ_MAGIC & 0xFF))) {
	fprintf(stderr, "Invalid magic number in the bitmap mq header\n");
	exit(-1);
    }

    fprintf(stdout, "Bitmap header:\n");
    fprintf(stdout, "\tbitmap size: 0x%"PRIx64" grains\n", bitmap->mqhdr.bitmap_size_bytes*8);
    fprintf(stdout, "\tvdisk size: 0x%"PRIx64"\n", bitmap->mqhdr.vdisk_size_lbas*LBAS_SIZE);
    fprintf(stdout, "\tgrain size: 0x%"PRIx32"\n", bitmap->mqhdr.grain_size_lbas*LBAS_SIZE);

    if (offset != ~0ULL) {
	/* just find the grain and tell if it is set */
	uint64_t grain = offset / (bitmap->mqhdr.grain_size_lbas*LBAS_SIZE);
	fprintf(stdout,
		"bitmap offset 0x%"PRIx64" belongs to grain 0x%"PRIx64" that is %s\n",
		offset, grain, (bitmap->bits[grain/8] & (1 << (grain%8))) ? "set" : "cleared");
	return;
    }

    ngrains = bitmap->mqhdr.bitmap_size_bytes * 8;

    fprintf(stdout, "Bitmap bitset:");
    for (i = 0; i < bitmap->mqhdr.bitmap_size_bytes; i++) {
	char bit_string[9];
	if ((i % 8) == 0)
	    fprintf(stdout, "\n\t");
	fprintf(stdout, "%s ", bitmap_show_bits(bit_string, bitmap->bits[i]));
    }
    fprintf(stdout, "\n");

    fprintf(stdout, "Bitmap range list:\n");
    for (i = 0; i < ngrains; i = j) {
	uint64_t start, end;
	int iset = (bitmap->bits[i/8] & (1 << (i%8))) >> (i%8);
	/* find next cleared/set range */
	for (j = i; (j < ngrains); j++) {
	    int jset = (bitmap->bits[j/8] & (1 << (j%8))) >> (j%8);
	    if (jset != iset)
		break;
	}
	start = bitmap->mqhdr.grain_size_lbas*LBAS_SIZE*i;
	end = bitmap->mqhdr.grain_size_lbas*LBAS_SIZE*j;
	fprintf(stdout, "\tbitmap range: [0x%"PRIx64",0x%"PRIx64") is %s (0x%"PRIx64" grain%s)\n",
		start, end, (iset) ? "set" : "cleared", j - i, ((j - i) > 1) ? "s" : "");
    }

    return;
}


/*
 * return 0 if bitmap1 is a subset of bitmap2 (or equal to it),
 * and return -1 otherwise
 */
int bitmap_compare(ram_bitmap_t *bm1, ram_bitmap_t *bm2)
{
        fc_bitmap_mq_hdr_t *hdr1 = &(bm1->mqhdr), *hdr2 = &(bm2->mqhdr);
        unsigned char *bitmap1 = &(bm1->bits[0]), *bitmap2 = &(bm2->bits[0]);
        uint64_t i, missing_bits = 0, extra_bits = 0;

        /* compare headers */
        if (hdr1->grain_size_lbas != hdr2->grain_size_lbas) {
                fprintf(stderr, "different bitmap grain size (%d vs %d), "
                    "cannot compare bitmaps\n",
                    hdr1->grain_size_lbas, hdr2->grain_size_lbas);
                return (-1);
        }
        if (hdr1->bitmap_size_bytes > hdr2->bitmap_size_bytes) {
                uint64_t diff_first_byte =
                    hdr2->bitmap_size_bytes*8*hdr2->grain_size_lbas*LBAS_SIZE,
                    diff_last_byte =
                    hdr1->bitmap_size_bytes*8*hdr1->grain_size_lbas*LBAS_SIZE;
                fprintf(stderr, "unexpected differences found in byte range "
                    "[0x%"PRIx64",0x%"PRIx64") (all data different) \n",
                    diff_first_byte, diff_last_byte);
                return (-1);
        }

        for (i = 0; i < hdr1->bitmap_size_bytes; i++) {
		char bm_byte[2][9];
                uint8_t mask = (uint8_t)(bitmap1[i] & ~bitmap2[i]);
		uint64_t diff_first_byte =
			i*8*hdr1->grain_size_lbas*LBAS_SIZE,
			diff_last_byte =
			diff_first_byte + 8*hdr1->grain_size_lbas*LBAS_SIZE;
		uint32_t grain_bytes = hdr1->grain_size_lbas*LBAS_SIZE;

                /*
                 * are there some bits in bitmap1[i] that are not
                 * present in bitmap2[i] ?
                 */
		mask = (uint8_t)(bitmap1[i] & ~bitmap2[i]);
                if (mask) {
                        if (verbosity) {
                                fprintf(stderr, "missing bits found in byte range "
                                    "[0x%"PRIx64",0x%"PRIx64"), grain size 0x%x bytes, "
                                    "range diffs (gain units) %s vs %s\n",
                                    diff_first_byte, diff_last_byte, grain_bytes,
				    bitmap_show_bits(bm_byte[0], bitmap1[i]),
				    bitmap_show_bits(bm_byte[1], bitmap2[i]));
                        }
                        missing_bits = 1;
                }
                /*
                 * are there some bits in bitmap2[i] that are not
                 * present in bitmap1[i] (extra bits)?
                 */
                mask = (uint8_t)(bitmap2[i] & ~bitmap1[i]);
                if (mask) {
                        if (verbosity) {
                                fprintf(stderr, "extra bits found in byte range "
                                    "[0x%"PRIx64",0x%"PRIx64"), grain size 0x%x bytes, "
                                    "range diffs (grain units) %s vs %s\n",
                                    diff_first_byte, diff_last_byte, grain_bytes,
				    bitmap_show_bits(bm_byte[0], bitmap1[i]),
				    bitmap_show_bits(bm_byte[1], bitmap2[i]));
                        }
                        extra_bits = 1;
                }
        }

        if (missing_bits) {
                fprintf(stderr, "bitmap is missing some bits\n");
                return (-1);
        }

        if (extra_bits)
                fprintf(stderr, "bitmap has some extra bits\n");

        /* bitmap1 is a subset of (or equal to) bitmap2 */
        return (0);
}

uint64_t bitmap_get_bitcount(ram_bitmap_t *bm)
{
        const uint64_t bitmap_size_bytes = bm->mqhdr.bitmap_size_bytes;
        const unsigned char *bitmap = &(bm->bits[0]);
        uint64_t i, j, bitcount;

        /* walk the bitmap and count the bits */
        for (bitcount = 0, i = 0; i < bitmap_size_bytes; i++) {
		if (bitmap[i] == 0)
			continue;
                for (j = 0; j < 8; j++) {
                        if (bitmap[i] & (1 << j))
                                bitcount++;
                }
        }

        return (bitcount);
}

int bitmap_get_bit(ram_bitmap_t *bm, uint64_t byte_offset)
{
        const unsigned char *bitmap = &(bm->bits[0]);
        uint64_t grainsize = bm->mqhdr.grain_size_lbas * LBAS_SIZE;
        uint64_t abs_bit = byte_offset / grainsize;
        uint64_t byte = abs_bit / 8, bit = abs_bit % 8;
    
        if (byte >= bm->mqhdr.bitmap_size_bytes)
                return -1;

        return ((bitmap[byte] & (1 << bit)) >> bit);
}