/*
 *  sbit.c
 *  Sierpinsky
 *
 *  Created by Victor Grishchenko on 2/19/09.
 *  Copyright 2009 Delft Technical University. All rights reserved.
 *
 */
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "sbit.h"

sbit			sbit_new (int height) {
	assert(height>=6);
	sbit ret;
	ret.height = height;
	size_t bytesize = 1<<(height-2);
	ret.bits = (sbitint*) malloc( bytesize );
	memset(ret.bits,0,bytesize);
	return ret;
}


void sbit_init () {
	mlat_init();
	for(uint8_t h=0; h<64; h++) {
		uint8_t blocklog = h%6;
		uint8_t blocksize = 1<<blocklog;
		//FEYE_BLOCK_SIZE[h] = blocksize;
		SBIT_BLOCK_MASK01[h] = 0;
		SBIT_BLOCK_MASK10[h] = 0;
		for(uint8_t i=0; i<SBIT_CHUNK_BITS; i++) {
			if (i%(blocksize*2)<blocksize)
				SBIT_BLOCK_MASK01[h] |= ((uint64_t)1)<<i;
			else
				SBIT_BLOCK_MASK10[h] |= ((uint64_t)1)<<i;
		}
	}
	// SBIT_BLOCK_MASKS[height%SBIT_HEIGHT][7bitmlat]
	for(int mlat7=0; mlat7<=125; mlat7++) { // plain linear layout for the 1st layer
		mlat ized = mlat7 | ~127;
		int height=mlat_height(ized)-25, length=1<<height;
		int offset = mlat_layer_offset(ized);
		SBIT_BLOCK_MASKS[0][mlat7] = ((sbitint)BITROWS[length])<<(offset*length);
	}
	SBIT_BLOCK_MASKS[0][126] = 0xFFFFFFFFFFFFFFFFLU;
	SBIT_BLOCK_MASKS[0][127] = 0;
	for(int layer=1; layer<6; layer++) {
		mlat root = mlat_new(6,0);
		for (int h=0; h<6; h++) {
			sbit2int pair;
			mlat from = mlat_leftn(root,6-h), to = mlat_rightn(root,6-h);
			pair.right=0;
			for(mlat m=from; m<from+(32>>h); m++) {
				pair.left = SBIT_BLOCK_MASKS[layer-1][mlat_rel64(mlat_left(root),m)];
				SBIT_BLOCK_MASKS[layer][mlat_rel64(root,m)] = sbit_join(pair, layer-1);
			}
			pair.left=0;
			for(mlat m=from+(32>>h); m<=to; m++) {
				pair.right = SBIT_BLOCK_MASKS[layer-1][mlat_rel64(mlat_right(root),m)], pair.left=0;
				SBIT_BLOCK_MASKS[layer][mlat_rel64(root,m)] = sbit_join(pair, layer-1);
			}
		}
		SBIT_BLOCK_MASKS[layer][126] = 0xFFFFFFFFFFFFFFFFLU;
		SBIT_BLOCK_MASKS[layer][127] = 0;
	}
}



static inline sbitint	sbit_mask_for (mlat bit, mlat chunktop) {
	int layout = mlat_height(chunktop)%6;
	uint8_t relpos = mlat_rel64(chunktop,bit);
	return SBIT_BLOCK_MASKS[layout][relpos];
}


inline int sbit_chunk_for (sbit bitmap, mlat top) {
	uint8_t height = mlat_height(top);
	assert(height<=bitmap.height);
	mlat fullmlat = mlat_new(height+31-bitmap.height,mlat_layer_offset(top));
	mlat cutmlat = fullmlat & BITROWS[bitmap.height+1-6];
	return cutmlat;
}


void			sbit_set (sbit bitmap, mlat bit) {
	uint8_t height = mlat_height(bit);
	mlat left, right;
	if (height<6) {
		mlat top = mlat_parentn(bit,6-height);
		left = right = top;
		int chunk = sbit_chunk_for(bitmap, top);
		sbitint m = sbit_mask_for(bit,top);
		bitmap.bits[chunk] |= m;
	} else {
		left = mlat_leftn(bit,height-6);
		right = mlat_rightn(bit,height-6);
		for(int c=sbit_chunk_for(bitmap,left); c<=sbit_chunk_for(bitmap,right); c++)
			bitmap.bits[c] = SBIT_1CHUNK;
	}
	for (uint8_t h=6+1; h<=bitmap.height; h++) {
		for(mlat t=mlat_parentn(left,h-6); t<=mlat_parentn(right,h-6); t++) {
			int c = sbit_chunk_for(bitmap, t);
			sbit2int pair;
			pair.left = bitmap.bits[sbit_chunk_for(bitmap, mlat_left(t))];
			pair.right = bitmap.bits[sbit_chunk_for(bitmap, mlat_right(t))];
			bitmap.bits[c] = sbit_join(pair, h-1);
		}
	}
}


sbitint			sbit_get_chunk (sbit bitmap, mlat top) {
	uint8_t height = mlat_height(top);
	assert(height>=SBIT_HEIGHT);
	if (height<=bitmap.height)
		return bitmap.bits[sbit_chunk_for(bitmap, top)];
	if (height<=bitmap.height+6 && !mlat_layer_offset(top)) {
		sbit2int p;	// now, the tricky cap
		p.left = bitmap.bits[sbit_chunk_for(bitmap, mlat_new(bitmap.height,0))];
		p.right = 0;
		for (int h=bitmap.height; h<height; h++) 
			p.left = sbit_join(p, h);
		return p.left;
	}
	return 0;
}

int 			sbit_get (sbit bitmap, mlat bit) {
	mlat top = mlat_parentn(bit,SBIT_HEIGHT);
	sbitint chunk = sbit_get_chunk(bitmap, top);
	return ( chunk & sbit_mask_for(bit, top) ) != 0;
}


void		sbit_free (sbit s) {
	free(s.bits);
}