laddr_to_paddr.c

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

struct paddr_val {
	uint64_t paddr;
	uint64_t val;
};

int paddr_val_cmp(const void *a, const void *b)
{
	const struct paddr_val *q = a, *w = b;
	return q->paddr - w->paddr;
}

struct paddr_val *memory_find(struct paddr_val *mem, size_t memlen, uint64_t paddr)
{
	return bsearch(&(struct paddr_val){ .paddr = paddr }, mem, memlen, sizeof(*mem),
		       &paddr_val_cmp);
}

uint64_t tbl_rec_paddr(uint64_t tbl_rec)
{
	return tbl_rec & (0x7fffffffff << 12);
}

uint64_t laddr_to_paddr(struct paddr_val *memory, size_t memlen, uint64_t laddr,
			uint64_t paddr_start)
{
	uint64_t l[5] = {
		(((laddr >> 39) & 0x1ff) * 8),
		(((laddr >> 30) & 0x1ff) * 8),
		(((laddr >> 21) & 0x1ff) * 8),
		(((laddr >> 12) & 0x1ff) * 8),
		laddr & 0xfff,
	};

	uint64_t paddr = paddr_start + l[0];
	for (int i = 1; i <= 4; i++) {
		struct paddr_val *res = memory_find(memory, memlen, paddr);
		uint64_t val = res == NULL ? 0 : res->val;
		if (!(val & 1))
			return -1;
		paddr = tbl_rec_paddr(val);
		paddr += l[i];
	}

	return paddr;
}

int main(int argc, char **argv)
{
	int m = 0, q = 0, r = 0;
	scanf("%d %d %d\n", &m, &q, &r);

	struct paddr_val *memory = malloc(sizeof(*memory) * m);
	for (int i = 0; i < m; i++)
		scanf("%lu %lu", &memory[i].paddr, &memory[i].val);
	qsort(memory, m, sizeof(*memory), &paddr_val_cmp);

	uint64_t laddr = 0;
	for (int i = 0; i < q; i++) {
		scanf("%lu", &laddr);
		int64_t paddr = laddr_to_paddr(memory, m, laddr, r);
		if (paddr < 0) {
			printf("fault\n");
			continue;
		}
		printf("%ld\n", paddr);
	}

	free(memory);
	return 0;
}