/* growing operand and return stacks share the runtime's buddy allocator.
   allocation here cannot call vm code or collect: an overflowing return stack
   has no room for an allocator call. the runtime registers its allocator and
   stack globals once the heap is ready. addresses are vm word indices. */
#ifndef TINYVM_STACK_H
#define TINYVM_STACK_H

static Cell stack_control;
enum {
	SC_FRAME_FLOOR, SC_FRAME_TOP, SC_FRAME_GUARD,
	SC_DATA_LOW, SC_DATA_TOP, SC_DATA_NODE,
	SC_RETURN_LOW, SC_RETURN_TOP, SC_RETURN_NODE,
	SC_FREE, SC_STOP, SC_BUMP, SC_MAX, SC_HOLD_LOW, SC_HOLD_HIGH, SC_CUT, SC_GC_ACTIVE, SC_COUNT
};

/* the including core supplies stack_memory_grow and refreshes m if it moves. */
static Cell stack_get(int slot) { Cell p = m[stack_control + slot]; return inmem(p) ? m[p] : 0; }
static void stack_set(int slot, Cell value) { Cell p = m[stack_control + slot]; if (inmem(p)) m[p] = value; }
static int stack_register(Cell control)
{
	int i;
	if (control <= 0 || !inmem(control + SC_COUNT - 1)) return 0;
	for (i = 0; i < SC_COUNT; i++) if (!inmem(m[control + i])) return 0;
	if (!inmem(m[control + SC_FREE] + 31)) return 0;
	stack_control = control;
	return 1;
}
static void stack_push(Cell b, int k)
{
	Cell list = m[stack_control + SC_FREE], head;
	if (k < 3 || k >= 31 || b < 0 || !inmem(b + 6) || list < 0 || !inmem(list + k)) return;
	head = m[list + k];
	if (head && (head < 0 || !inmem(head + 6))) return;
	m[b] = (Cell)1 << k; m[b + 1] = (Cell)k << 16; m[b + 2] = 0;
	m[b + 3] = 0; m[b + 4] = 0; m[b + 5] = head; m[b + 6] = 0;
	if (head) m[head + 6] = b;
	m[list + k] = b;
}
static int stack_heap_grow(int k)
{
	Cell old = stack_get(SC_STOP), h = old - HEAP_LO, block = (Cell)1 << k;
	Cell need = ((h + block - 1) / block + 1) * block, size = h * 2, off, part;
	int c;
	if (h <= 0 || (h & 7) || !HEAP_GROW || !stack_get(SC_MAX) || stack_get(SC_CUT) || stack_get(SC_HOLD_HIGH)) return 0;
	if (size < need) size = need;
	if (HEAP_LO + size > 0x7fffffff || !stack_memory_grow((UCell)(HEAP_LO + size))) {
		size = need;
		if (HEAP_LO + size > 0x7fffffff || !stack_memory_grow((UCell)(HEAP_LO + size))) return 0;
	}
	stack_set(SC_STOP, HEAP_LO + size); stack_set(SC_BUMP, HEAP_LO + size);
	stack_set(SC_MAX, HEAP_LO + size);
	off = h;
	while (off < size) {
		part = 8; c = 3;
		while (part * 2 <= size - off && !(off % (part * 2))) { part *= 2; c++; }
		stack_push(HEAP_LO + off, c); off += part;
	}
	return 1;
}
static Cell stack_allocate(Cell words)
{
	Cell list, b, next, other, p, i;
	int k = 3, j, grown = 0;
	if (!stack_control || words < 0 || words > 0x3ffffffa) return 0;
	while (((Cell)1 << k) < words + 5) k++;
	for (;;) {
		list = m[stack_control + SC_FREE]; j = k;
		if (list < 0 || !inmem(list + 31)) return 0;
		while (j < 31 && !m[list + j]) j++;
		if (j == 31) {
			if (grown || !stack_heap_grow(k)) return 0;
			grown = 1; continue;
		}
		b = m[list + j];
		if (b < 0 || !inmem(b + ((Cell)1 << j) - 1) || m[b] != ((Cell)1 << j) || (m[b + 1] & 65535)) return 0;
		next = m[b + 5]; m[list + j] = next;
		if (next) { if (!inmem(next + 6)) return 0; m[next + 6] = 0; }
		while (j > k) { j--; other = b + ((Cell)1 << j); stack_push(other, j); }
		if (stack_get(SC_HOLD_HIGH) && b < stack_get(SC_HOLD_HIGH) && b + ((Cell)1 << k) > stack_get(SC_HOLD_LOW)) {
			m[b] = (Cell)1 << k; m[b + 1] = ((Cell)k << 16) | 2;
			m[b + 2] = 0; m[b + 5] = 0; m[b + 6] = 0; continue;
		}
		p = b + 5;
		m[b] = (Cell)1 << k; m[b + 1] = ((Cell)k << 16) | 1 | 512 | 1024 | (stack_get(SC_GC_ACTIVE) ? 2 : 0);
		m[b + 2] = p ^ 0x2B7E1516; m[b + 3] = 0; m[b + 4] = -words - 1;
		for (i = p; i < b + ((Cell)1 << k); i++) m[i] = 0;
		return p;
	}
}
static Cell stack_expand(int is_return, Cell minimum, Cell *sp, Cell *rp)
{
	int low_slot = is_return ? SC_RETURN_LOW : SC_DATA_LOW, top_slot = low_slot + 1, node_slot = low_slot + 2;
	Cell low, top, capacity, used, node, oldnode, i, source;
	if (!stack_control) return -1;
	low = stack_get(low_slot); top = stack_get(top_slot); capacity = top - low;
	used = is_return ? *rp - low : top - *sp;
	if (capacity <= 0 || used < 0 || used > capacity + (is_return ? 8 : 0) || minimum < 0 || minimum > 0x3ffffff0) return -1;
	if (minimum <= capacity) return capacity;
	if (minimum < capacity * 2) minimum = capacity * 2;
	node = stack_allocate(minimum + 16);
	if (!node) return -1;
	source = is_return ? low : *sp;
	for (i = 0; i < used; i++) m[node + (is_return ? i : minimum - used + i)] = m[source + i];
	oldnode = stack_get(node_slot);
	stack_set(low_slot, node); stack_set(top_slot, node + minimum); stack_set(node_slot, node);
	if (is_return) *rp = node + used; else *sp = node + minimum - used;
	if (oldnode >= 5 && inmem(oldnode - 4)) stack_push(oldnode - 5, (int)((m[oldnode - 4] >> 16) & 31));
	return minimum;
}
static Cell stack_data_limit(void) { return stack_control ? stack_get(SC_DATA_LOW) + 1100 : DSLIM; }
static Cell stack_return_limit(void) { return stack_control ? stack_get(SC_RETURN_TOP) : RSLIM; }
#endif