/* Helper: Do a successful Extended ORPort authentication handshake. */
static void
do_ext_or_handshake(or_connection_t *conn)
{
  char b[256];

  tt_int_op(0, OP_EQ, connection_ext_or_start_auth(conn));
  CONTAINS("\x01\x00", 2);
  WRITE("\x01", 1);
  WRITE("But when I look ahead up the whi", 32);
  MOCK(crypto_rand, crypto_rand_return_tse_str);
  tt_int_op(0, OP_EQ, connection_ext_or_process_inbuf(conn));
  UNMOCK(crypto_rand);
  tt_int_op(TO_CONN(conn)->state, OP_EQ,
            EXT_OR_CONN_STATE_AUTH_WAIT_CLIENT_HASH);
  CONTAINS("\xec\x80\xed\x6e\x54\x6d\x3b\x36\xfd\xfc\x22\xfe\x13\x15\x41\x6b"
           "\x02\x9f\x1a\xde\x76\x10\xd9\x10\x87\x8b\x62\xee\xb7\x40\x38\x21"
           "te road There is always another ", 64);
  /* Send the right response this time. */
  WRITE("\xab\x39\x17\x32\xdd\x2e\xd9\x68\xcd\x40\xc0\x87\xd1\xb1\xf2\x5b"
        "\x33\xb3\xcd\x77\xff\x79\xbd\x80\xc2\x07\x4b\xbf\x43\x81\x19\xa2",
        32);
  tt_int_op(0, OP_EQ, connection_ext_or_process_inbuf(conn));
  CONTAINS("\x01", 1);
  tt_assert(! TO_CONN(conn)->marked_for_close);
  tt_int_op(TO_CONN(conn)->state, OP_EQ, EXT_OR_CONN_STATE_OPEN);

 done: ;
}

static int range_cmp_for_search(const void *l, const void *r) {
    range_t *left = (range_t *)l, *right = (range_t *)r;
    if (INTERSECT(left, right) ||
        CONTAINS(left, right) ||
        CONTAINS(right, left)) {
        return 0;
    }
    return left->start - right->start;
}

bool DecoSimple::canPlaceDecoration(MMVManip *vm, v3s16 p)
{
	// Don't bother if there aren't any decorations to place
	if (c_decos.size() == 0)
		return false;

	u32 vi = vm->m_area.index(p);

	// Check if the decoration can be placed on this node
	if (!CONTAINS(c_place_on, vm->m_data[vi].getContent()))
		return false;

	// Don't continue if there are no spawnby constraints
	if (nspawnby == -1)
		return true;

	int nneighs = 0;
	v3s16 dirs[16] = {
		v3s16( 0, 0,  1),
		v3s16( 0, 0, -1),
		v3s16( 1, 0,  0),
		v3s16(-1, 0,  0),
		v3s16( 1, 0,  1),
		v3s16(-1, 0,  1),
		v3s16(-1, 0, -1),
		v3s16( 1, 0, -1),

		v3s16( 0, 1,  1),
		v3s16( 0, 1, -1),
		v3s16( 1, 1,  0),
		v3s16(-1, 1,  0),
		v3s16( 1, 1,  1),
		v3s16(-1, 1,  1),
		v3s16(-1, 1, -1),
		v3s16( 1, 1, -1)
	};

	// Check a Moore neighborhood if there are enough spawnby nodes
	for (size_t i = 0; i != ARRLEN(dirs); i++) {
		u32 index = vm->m_area.index(p + dirs[i]);
		if (!vm->m_area.contains(index))
			continue;

		if (CONTAINS(c_spawnby, vm->m_data[index].getContent()))
			nneighs++;
	}

	if (nneighs < nspawnby)
		return false;

	return true;
}

void printFaceTupleFaces(bitset tuple){
    int i, j;
    for(i=0; i<nf; i++){
        if(CONTAINS(tuple, i)){
            fprintf(stderr, "%d) ", i+1);
            for(j=0; j<nv; j++){
                if(CONTAINS(faceSets[i], j)){
                    fprintf(stderr, "%d ", j+1);
                }
            }
            fprintf(stderr, "\n");
        }
    }
}

void Dashboard::addWidget(DashboardWidget *widget)
{
    if (CONTAINS(widgets, widget))
        return;
    
    widgets.push_back(widget);
}

void OreScatter::generate(ManualMapVoxelManipulator *vm, int seed,
						  u32 blockseed, v3s16 nmin, v3s16 nmax) {
	PseudoRandom pr(blockseed);
	MapNode n_ore(c_ore, 0, ore_param2);

	int volume = (nmax.X - nmin.X + 1) *
				 (nmax.Y - nmin.Y + 1) *
				 (nmax.Z - nmin.Z + 1);
	int csize     = clust_size;
	int orechance = (csize * csize * csize) / clust_num_ores;
	int nclusters = volume / clust_scarcity;

	for (int i = 0; i != nclusters; i++) {
		int x0 = pr.range(nmin.X, nmax.X - csize + 1);
		int y0 = pr.range(nmin.Y, nmax.Y - csize + 1);
		int z0 = pr.range(nmin.Z, nmax.Z - csize + 1);

		if (np && (NoisePerlin3D(np, x0, y0, z0, seed) < nthresh))
			continue;

		for (int z1 = 0; z1 != csize; z1++)
		for (int y1 = 0; y1 != csize; y1++)
		for (int x1 = 0; x1 != csize; x1++) {
			if (pr.range(1, orechance) != 1)
				continue;

			u32 i = vm->m_area.index(x0 + x1, y0 + y1, z0 + z1);
			if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
				continue;

			vm->m_data[i] = n_ore;
		}
	}
}

void VirtualNetwork::removeDevice(NetworkDevice *device)
{
    if (CONTAINS(devices, device)) {
        this->devices.erase(FIND(devices, device));
        device->disconnectFromNetwork();
    }
}

size_t DecoSchematic::generate(MMVManip *vm, PseudoRandom *pr, v3s16 p)
{
	// Schematic could have been unloaded but not the decoration
	// In this case generate() does nothing (but doesn't *fail*)
	if (schematic == NULL)
		return 0;

	u32 vi = vm->m_area.index(p);
	content_t c = vm->m_data[vi].getContent();
	if (!CONTAINS(c_place_on, c))
		return 0;

	if (flags & DECO_PLACE_CENTER_X)
		p.X -= (schematic->size.X - 1) / 2;
	if (flags & DECO_PLACE_CENTER_Y)
		p.Y -= (schematic->size.Y - 1) / 2;
	if (flags & DECO_PLACE_CENTER_Z)
		p.Z -= (schematic->size.Z - 1) / 2;

	Rotation rot = (rotation == ROTATE_RAND) ?
		(Rotation)pr->range(ROTATE_0, ROTATE_270) : rotation;

	bool force_placement = (flags & DECO_FORCE_PLACEMENT);

	schematic->blitToVManip(p, vm, rot, force_placement);

	return 1;
}

boolean findEOPD(bitset tuple){
    int i, j;
    //first we check the stored OPD's
    for(i = 0; i < eopdCount; i++){
        bitset intersectionOpd = INTERSECTION(tuple, opdFaces[i]);
        bitset intersectionExtensions = INTERSECTION(tuple, extensionFaces[i]);
        if((IS_NOT_EMPTY(intersectionOpd) && IS_NOT_EMPTY(intersectionExtensions)) ||
                (HAS_MORE_THAN_ONE_ELEMENT(intersectionOpd))){
            numberOfTuplesCoveredByStoredOpd++;
            return TRUE;
        }
    }
    
    //then we try to find a new eOPD
    for(i = 0; i < nf; i++){
        if(CONTAINS(tuple, i)){
            //try to find a eOPD with face i as extension
            bitset remainingFaces = MINUS(tuple, i);
            //we use each edge once as a possible shared edge 
            EDGE *sharedEdge = facestart[i];
            for(j = 0; j < 3; j++){
                //construct initial eopd
                int neighbouringFace = sharedEdge->inverse->rightface;
                bitset currentEopdVertices = faceSets[neighbouringFace];
                bitset currentEopdFaces = UNION(SINGLETON(i), SINGLETON(neighbouringFace));
                if(findEOPD_impl(currentEopdVertices, currentEopdFaces, i, remainingFaces, sharedEdge->inverse)){
                    return TRUE;
                }
                sharedEdge = sharedEdge->next->inverse;
            }
        }
    }
    return FALSE;
}

void printVector(FILE *f, bitset vector){
    int i;
    
    for(i = 0; i < n; i++){
        fprintf(f, CONTAINS(vector, i) ? "1" : "0");
    }
    fprintf(f, "\n");
}

void VirtualNetwork::addDevice(NetworkDevice *device)
{
    if (CONTAINS(devices, device))
        return;
    
    devices.push_back(device);
    device->connectToNetwork(this);
}

bool NodeDefManager::nodeboxConnects(MapNode from, MapNode to,
	u8 connect_face) const
{
	const ContentFeatures &f1 = get(from);

	if ((f1.drawtype != NDT_NODEBOX) || (f1.node_box.type != NODEBOX_CONNECTED))
		return false;

	// lookup target in connected set
	if (!CONTAINS(f1.connects_to_ids, to.param0))
		return false;

	const ContentFeatures &f2 = get(to);

	if ((f2.drawtype == NDT_NODEBOX) && (f2.node_box.type == NODEBOX_CONNECTED))
		// ignores actually looking if back connection exists
		return CONTAINS(f2.connects_to_ids, from.param0);

	// does to node declare usable faces?
	if (f2.connect_sides > 0) {
		if ((f2.param_type_2 == CPT2_FACEDIR ||
				f2.param_type_2 == CPT2_COLORED_FACEDIR)
				&& (connect_face >= 4)) {
			static const u8 rot[33 * 4] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 4, 32, 16, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, // 4 - back
				8, 4, 32, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, // 8 - right
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 8, 4, 32, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, // 16 - front
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 32, 16, 8, 4 // 32 - left
				};
			return (f2.connect_sides
				& rot[(connect_face * 4) + (to.param2 & 0x1F)]);
		}
		return (f2.connect_sides & connect_face);
	}
	// the target is just a regular node, so connect no matter back connection
	return true;
}

bool ModChannel::registerConsumer(session_t peer_id)
{

	// ignore if peer_id already joined
	if (CONTAINS(m_client_consumers, peer_id))
		return false;

	m_client_consumers.push_back(peer_id);
	return true;
}

void printVertexTuple(bitset tuple){
    int i;
    fprintf(stderr, "Vertex tuple: ");
    for(i=0; i<nv; i++){
        if(CONTAINS(tuple, i)){
            fprintf(stderr, "%d ", i+1);
        }
    }
    fprintf(stderr, "\n");
}

void printFaceTuple(bitset tuple){
    int i;
    fprintf(stderr, "Face tuple: ");
    for(i=0; i<nf; i++){
        if(CONTAINS(tuple, i)){
            fprintf(stderr, "%d ", i+1);
        }
    }
    fprintf(stderr, "\n");
}

void OreStratum::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax, u8 *biomemap)
{
	PcgRandom pr(blockseed + 4234);
	MapNode n_ore(c_ore, 0, ore_param2);

	if (flags & OREFLAG_USE_NOISE) {
		if (!(noise && noise_stratum_thickness)) {
			int sx = nmax.X - nmin.X + 1;
			int sz = nmax.Z - nmin.Z + 1;
			noise = new Noise(&np, 0, sx, sz);
			noise_stratum_thickness = new Noise(&np_stratum_thickness, 0, sx, sz);
		}
		noise->perlinMap2D(nmin.X, nmin.Z);
		noise_stratum_thickness->perlinMap2D(nmin.X, nmin.Z);
	}

	size_t index = 0;

	for (int z = nmin.Z; z <= nmax.Z; z++)
	for (int x = nmin.X; x <= nmax.X; x++, index++) {
		if (biomemap && !biomes.empty()) {
			std::unordered_set<u8>::const_iterator it = biomes.find(biomemap[index]);
			if (it == biomes.end())
				continue;
		}

		int y0;
		int y1;

		if (flags & OREFLAG_USE_NOISE) {
			float nmid = noise->result[index];
			float nhalfthick = noise_stratum_thickness->result[index] / 2.0f;
			y0 = MYMAX(nmin.Y, nmid - nhalfthick);
			y1 = MYMIN(nmax.Y, nmid + nhalfthick);
		} else {
			y0 = nmin.Y;
			y1 = nmax.Y;
		}

		for (int y = y0; y <= y1; y++) {
			if (pr.range(1, clust_scarcity) != 1)
				continue;

			u32 i = vm->m_area.index(x, y, z);
			if (!vm->m_area.contains(i))
				continue;
			if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
				continue;

			vm->m_data[i] = n_ore;
		}
	}
}

void OreBlob::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax)
{
	PseudoRandom pr(blockseed + 2404);
	MapNode n_ore(c_ore, 0, ore_param2);

	int volume = (nmax.X - nmin.X + 1) *
				 (nmax.Y - nmin.Y + 1) *
				 (nmax.Z - nmin.Z + 1);
	int csize  = clust_size;
	int nblobs = volume / clust_scarcity;

	if (!noise)
		noise = new Noise(&np, mapseed, csize, csize, csize);

	for (int i = 0; i != nblobs; i++) {
		int x0 = pr.range(nmin.X, nmax.X - csize + 1);
		int y0 = pr.range(nmin.Y, nmax.Y - csize + 1);
		int z0 = pr.range(nmin.Z, nmax.Z - csize + 1);

		bool noise_generated = false;
		noise->seed = blockseed + i;

		size_t index = 0;
		for (int z1 = 0; z1 != csize; z1++)
		for (int y1 = 0; y1 != csize; y1++)
		for (int x1 = 0; x1 != csize; x1++, index++) {
			u32 i = vm->m_area.index(x0 + x1, y0 + y1, z0 + z1);
			if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
				continue;

			// Lazily generate noise only if there's a chance of ore being placed
			// This simple optimization makes calls 6x faster on average
			if (!noise_generated) {
				noise_generated = true;
				noise->perlinMap3D(x0, y0, z0);
			}

			float noiseval = noise->result[index];

			float xdist = x1 - csize / 2;
			float ydist = y1 - csize / 2;
			float zdist = z1 - csize / 2;

			noiseval -= (sqrt(xdist * xdist + ydist * ydist + zdist * zdist) / csize);

			if (noiseval < nthresh)
				continue;

			vm->m_data[i] = n_ore;
		}
	}
}

void greedyExtendOpdAndStore(bitset currentOpdVertices, bitset currentOpdFaces){
    int i;
    int top;
    EDGE *boundaryStack[MAXE];

    top = 0;
    
    //fill the stack with the current boundary
    for(i = 0; i < ne; i++){
        if(CONTAINS_ALL(currentOpdVertices, edges[i].vertices) &&
                !CONTAINS(currentOpdFaces, edges[i].rightface)){
            PUSH(boundaryStack, edges + i);
        }
    }
    
    while(STACKISNOTEMPTY){
        EDGE *currentEdge = POP(boundaryStack);
        if(INTERSECTION(currentOpdVertices, neighbourhood[currentEdge->next->end])
                == currentEdge->vertices){
            //modify OPD by adding face to the right of current edge
            ADD_ALL(currentOpdVertices, faceSets[currentEdge->rightface]);
            ADD(currentOpdFaces, currentEdge->rightface);
            
            //push new boundary edges on stack
            PUSH(boundaryStack, currentEdge->next);
            PUSH(boundaryStack, currentEdge->inverse->prev->inverse);
        }
    }
    
    //store the OPD together with all possible extensions
    opdFaces[eopdCount] = currentOpdFaces;
    extensionFaces[eopdCount] = EMPTY_SET;
    for(i = 0; i < nf; i++){
        if(!CONTAINS(currentOpdFaces, i) &&
                HAS_MORE_THAN_ONE_ELEMENT(INTERSECTION(faceSets[i], currentOpdVertices))){
            ADD(extensionFaces[eopdCount], i);
        }
    }
    eopdCount++;
}

void OreVein::generate(MMVManip *vm, int mapseed, u32 blockseed,
	v3s16 nmin, v3s16 nmax, u8 *biomemap)
{
	PcgRandom pr(blockseed + 520);
	MapNode n_ore(c_ore, 0, ore_param2);

	u32 sizex = (nmax.X - nmin.X + 1);

	if (!noise) {
		int sx = nmax.X - nmin.X + 1;
		int sy = nmax.Y - nmin.Y + 1;
		int sz = nmax.Z - nmin.Z + 1;
		noise  = new Noise(&np, mapseed, sx, sy, sz);
		noise2 = new Noise(&np, mapseed + 436, sx, sy, sz);
	}
	bool noise_generated = false;

	size_t index = 0;
	for (int z = nmin.Z; z <= nmax.Z; z++)
	for (int y = nmin.Y; y <= nmax.Y; y++)
	for (int x = nmin.X; x <= nmax.X; x++, index++) {
		u32 i = vm->m_area.index(x, y, z);
		if (!vm->m_area.contains(i))
			continue;
		if (!CONTAINS(c_wherein, vm->m_data[i].getContent()))
			continue;

		if (biomemap && !biomes.empty()) {
			u32 bmapidx = sizex * (z - nmin.Z) + (x - nmin.X);
			std::set<u8>::iterator it = biomes.find(biomemap[bmapidx]);
			if (it == biomes.end())
				continue;
		}

		// Same lazy generation optimization as in OreBlob
		if (!noise_generated) {
			noise_generated = true;
			noise->perlinMap3D(nmin.X, nmin.Y, nmin.Z);
			noise2->perlinMap3D(nmin.X, nmin.Y, nmin.Z);
		}

		// randval ranges from -1..1
		float randval   = (float)pr.next() / (pr.RANDOM_RANGE / 2) - 1.f;
		float noiseval  = contour(noise->result[index]);
		float noiseval2 = contour(noise2->result[index]);
		if (noiseval * noiseval2 + randval * random_factor < nthresh)
			continue;

		vm->m_data[i] = n_ore;
	}
}

static int check_overlap(struct hlist_head *ptype,
				unsigned long paddr,
				unsigned long len)
{
	struct msm_pmem_region *region;
	struct msm_pmem_region t = { .paddr = paddr, .len = len };
	struct hlist_node *node;

	hlist_for_each_entry(region, node, ptype, list) {
		if (CONTAINS(region, &t, paddr) ||
			CONTAINS(&t, region, paddr) ||
			OVERLAPS(region, &t, paddr)) {
			CDBG(" region (PHYS %p len %ld)"
				" clashes with registered region"
				" (paddr %p len %ld)\n",
				(void *)t.paddr, t.len,
				(void *)region->paddr, region->len);
			return -EINVAL;
		}
	}

	return 0;
}