diff --git a/openbsc/.gitignore b/openbsc/.gitignore
index 3743f69..79222f7 100644
--- a/openbsc/.gitignore
+++ b/openbsc/.gitignore
@@ -50,6 +50,7 @@
 
 #tests
 tests/bsc-nat/bsc_nat_test
+tests/bsc-nat-trie/bsc_nat_trie_test
 tests/channel/channel_test
 tests/db/db_test
 tests/debug/debug_test
diff --git a/openbsc/configure.ac b/openbsc/configure.ac
index 0227d26..ce2a328 100644
--- a/openbsc/configure.ac
+++ b/openbsc/configure.ac
@@ -157,6 +157,7 @@
     tests/db/Makefile
     tests/channel/Makefile
     tests/bsc-nat/Makefile
+    tests/bsc-nat-trie/Makefile
     tests/mgcp/Makefile
     tests/gprs/Makefile
     tests/si/Makefile
diff --git a/openbsc/include/openbsc/Makefile.am b/openbsc/include/openbsc/Makefile.am
index 93b30bb..6ba6d1b 100644
--- a/openbsc/include/openbsc/Makefile.am
+++ b/openbsc/include/openbsc/Makefile.am
@@ -13,7 +13,7 @@
 		osmo_bsc_rf.h osmo_bsc.h network_listen.h bsc_nat_sccp.h \
 		osmo_msc_data.h osmo_bsc_grace.h sms_queue.h abis_om2000.h \
 		bss.h gsm_data_shared.h control_cmd.h ipaccess.h mncc_int.h \
-		arfcn_range_encode.h
+		arfcn_range_encode.h nat_rewrite_trie.h
 
 openbsc_HEADERS = gsm_04_08.h meas_rep.h bsc_api.h
 openbscdir = $(includedir)/openbsc
diff --git a/openbsc/include/openbsc/bsc_nat.h b/openbsc/include/openbsc/bsc_nat.h
index 1950318..6ebe045 100644
--- a/openbsc/include/openbsc/bsc_nat.h
+++ b/openbsc/include/openbsc/bsc_nat.h
@@ -45,6 +45,7 @@
 struct bsc_nat_parsed;
 struct bsc_nat;
 struct bsc_nat_ussd_con;
+struct nat_rewrite_rule;
 
 enum {
 	NAT_CON_TYPE_NONE,
@@ -298,6 +299,8 @@
 	/* number rewriting */
 	char *num_rewr_name;
 	struct llist_head num_rewr;
+	char *num_rewr_post_name;
+	struct llist_head num_rewr_post;
 
 	char *smsc_rewr_name;
 	struct llist_head smsc_rewr;
@@ -308,6 +311,10 @@
 	char *sms_num_rewr_name;
 	struct llist_head sms_num_rewr;
 
+	/* more rewriting */
+	char *num_rewr_trie_name;
+	struct nat_rewrite *num_rewr_trie;
+
 	/* USSD messages  we want to match */
 	char *ussd_lst_name;
 	char *ussd_query;
@@ -452,6 +459,7 @@
 	regex_t num_reg;
 
 	char *replace;
+	uint8_t is_prefix_lookup;
 };
 
 void bsc_nat_num_rewr_entry_adapt(void *ctx, struct llist_head *head, const struct osmo_config_list *);
diff --git a/openbsc/include/openbsc/nat_rewrite_trie.h b/openbsc/include/openbsc/nat_rewrite_trie.h
new file mode 100644
index 0000000..0571099
--- /dev/null
+++ b/openbsc/include/openbsc/nat_rewrite_trie.h
@@ -0,0 +1,47 @@
+/*
+ * (C) 2013 by On-Waves
+ * (C) 2013 by Holger Hans Peter Freyther <zecke@selfish.org>
+ * All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+#ifndef NAT_REWRITE_FILE_H
+#define NAT_REWRITE_FILE_H
+
+#include <osmocom/core/linuxrbtree.h>
+
+struct vty;
+
+struct nat_rewrite_rule {
+	/* For digits 0-9 and + */
+	struct nat_rewrite_rule *rules[11];
+
+	char empty;
+	char prefix[14];
+	char rewrite[6];
+};
+
+struct nat_rewrite {
+	struct nat_rewrite_rule rule;
+	size_t prefixes;
+};
+
+
+struct nat_rewrite *nat_rewrite_parse(void *ctx, const char *filename);
+struct nat_rewrite_rule *nat_rewrite_lookup(struct nat_rewrite *, const char *prefix);
+void nat_rewrite_dump(struct nat_rewrite *rewr);
+void nat_rewrite_dump_vty(struct vty *vty, struct nat_rewrite *rewr);
+
+#endif
diff --git a/openbsc/src/osmo-bsc_nat/Makefile.am b/openbsc/src/osmo-bsc_nat/Makefile.am
index e2ba551..aae6d69 100644
--- a/openbsc/src/osmo-bsc_nat/Makefile.am
+++ b/openbsc/src/osmo-bsc_nat/Makefile.am
@@ -7,7 +7,7 @@
 
 osmo_bsc_nat_SOURCES = bsc_filter.c bsc_mgcp_utils.c bsc_nat.c bsc_nat_utils.c \
 		  bsc_nat_vty.c bsc_sccp.c bsc_ussd.c bsc_nat_ctrl.c \
-		  bsc_nat_rewrite.c bsc_nat_filter.c
+		  bsc_nat_rewrite.c bsc_nat_filter.c bsc_nat_rewrite_trie.c
 osmo_bsc_nat_LDADD = $(top_builddir)/src/libcommon/libcommon.a \
 		$(top_builddir)/src/libmgcp/libmgcp.a \
 		$(top_builddir)/src/libbsc/libbsc.a \
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat.c b/openbsc/src/osmo-bsc_nat/bsc_nat.c
index 1237339..897c657 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat.c
@@ -1480,6 +1480,7 @@
 	.is_config_node	= bsc_vty_is_config_node,
 };
 
+
 int main(int argc, char **argv)
 {
 	int rc;
@@ -1526,6 +1527,8 @@
 	/* seed the PRNG */
 	srand(time(NULL));
 
+
+
 	/*
 	 * Setup the MGCP code..
 	 */
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c
index 06071c4..54fc573 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite.c
@@ -27,6 +27,7 @@
 #include <openbsc/gsm_data.h>
 #include <openbsc/debug.h>
 #include <openbsc/ipaccess.h>
+#include <openbsc/nat_rewrite_trie.h>
 
 #include <osmocom/core/linuxlist.h>
 #include <osmocom/core/talloc.h>
@@ -37,9 +38,30 @@
 
 #include <osmocom/sccp/sccp.h>
 
+static char *trie_lookup(struct nat_rewrite *trie, const char *number,
+			regoff_t off, void *ctx)
+{
+	struct nat_rewrite_rule *rule;
+
+	if (!trie) {
+		LOGP(DCC, LOGL_ERROR,
+			"Asked to do a table lookup but no table.\n");
+		return NULL;
+	}
+
+	rule = nat_rewrite_lookup(trie, number);
+	if (!rule) {
+		LOGP(DCC, LOGL_DEBUG,
+			"Couldn't find a prefix rule for %s\n", number);
+		return NULL;
+	}
+
+	return talloc_asprintf(ctx, "%s%s", rule->rewrite, &number[off]);
+}
+
 static char *match_and_rewrite_number(void *ctx, const char *number,
-				      const char *imsi,
-				      struct llist_head *list)
+				const char *imsi, struct llist_head *list,
+				struct nat_rewrite *trie)
 {
 	struct bsc_nat_num_rewr_entry *entry;
 	char *new_number = NULL;
@@ -53,11 +75,17 @@
 			continue;
 
 		/* this regexp matches... */
-		if (regexec(&entry->num_reg, number, 2, matches, 0) == 0 &&
-		    matches[1].rm_eo != -1)
-			new_number = talloc_asprintf(ctx, "%s%s",
+		if (regexec(&entry->num_reg, number, 2, matches, 0) == 0
+			&& matches[1].rm_eo != -1) {
+			if (entry->is_prefix_lookup)
+				new_number = trie_lookup(trie, number,
+						matches[1].rm_so, ctx);
+			else
+				new_number = talloc_asprintf(ctx, "%s%s",
 					entry->replace,
 					&number[matches[1].rm_so]);
+		}
+
 		if (new_number)
 			break;
 	}
@@ -65,18 +93,24 @@
 	return new_number;
 }
 
-static char *rewrite_isdn_number(struct bsc_nat *nat, void *ctx, const char *imsi,
-				       struct gsm_mncc_number *called)
+static char *rewrite_isdn_number(struct bsc_nat *nat, struct llist_head *rewr_list,
+				void *ctx, const char *imsi,
+				struct gsm_mncc_number *called)
 {
 	char int_number[sizeof(called->number) + 2];
 	char *number = called->number;
 
-	if (llist_empty(&nat->num_rewr))
+	if (llist_empty(&nat->num_rewr)) {
+		LOGP(DCC, LOGL_DEBUG, "Rewrite rules empty.\n");
 		return NULL;
+	}
 
 	/* only ISDN plan */
-	if (called->plan != 1)
+	if (called->plan != 1) {
+		LOGP(DCC, LOGL_DEBUG, "Called plan is not 1 it was %d\n",
+			called->plan);
 		return NULL;
+	}
 
 	/* international, prepend */
 	if (called->type == 1) {
@@ -86,9 +120,24 @@
 	}
 
 	return match_and_rewrite_number(ctx, number,
-					imsi, &nat->num_rewr);
+					imsi, rewr_list, nat->num_rewr_trie);
 }
 
+static void update_called_number(struct gsm_mncc_number *called,
+				const char *chosen_number)
+{
+	if (strncmp(chosen_number, "00", 2) == 0) {
+		called->type = 1;
+		strncpy(called->number, chosen_number + 2, sizeof(called->number));
+	} else {
+		/* rewrite international to unknown */
+		if (called->type == 1)
+			called->type = 0;
+		strncpy(called->number, chosen_number, sizeof(called->number));
+	}
+
+	called->number[sizeof(called->number) - 1] = '\0';
+}
 
 /**
  * Rewrite non global numbers... according to rules based on the IMSI
@@ -101,7 +150,7 @@
 	unsigned int payload_len;
 	struct gsm_mncc_number called;
 	struct msgb *out;
-	char *new_number = NULL;
+	char *new_number_pre = NULL, *new_number_post = NULL, *chosen_number;
 	uint8_t *outptr;
 	const uint8_t *msgptr;
 	int sec_len;
@@ -119,16 +168,39 @@
 			    TLVP_VAL(&tp, GSM48_IE_CALLED_BCD) - 1);
 
 	/* check if it looks international and stop */
-	new_number = rewrite_isdn_number(nat, msg, imsi, &called);
+	LOGP(DCC, LOGL_DEBUG,
+		"Pre-Rewrite for IMSI(%s) Plan(%d) Type(%d) Number(%s)\n",
+		imsi, called.plan, called.type, called.number);
+	new_number_pre = rewrite_isdn_number(nat, &nat->num_rewr, msg, imsi, &called);
 
-	if (!new_number) {
-		LOGP(DNAT, LOGL_DEBUG, "No IMSI match found, returning message.\n");
+	if (!new_number_pre) {
+		LOGP(DCC, LOGL_DEBUG, "No IMSI(%s) match found, returning message.\n",
+			imsi);
 		return NULL;
 	}
 
-	if (strlen(new_number) > sizeof(called.number)) {
-		LOGP(DNAT, LOGL_ERROR, "Number is too long for structure.\n");
-		talloc_free(new_number);
+	if (strlen(new_number_pre) > sizeof(called.number)) {
+		LOGP(DCC, LOGL_ERROR, "Number %s is too long for structure.\n",
+				new_number_pre);
+		talloc_free(new_number_pre);
+		return NULL;
+	}
+	update_called_number(&called, new_number_pre);
+
+	/* another run through the re-write engine with other rules */
+	LOGP(DCC, LOGL_DEBUG,
+		"Post-Rewrite for IMSI(%s) Plan(%d) Type(%d) Number(%s)\n",
+		imsi, called.plan, called.type, called.number);
+	new_number_post = rewrite_isdn_number(nat, &nat->num_rewr_post, msg,
+					imsi, &called);
+	chosen_number = new_number_post ? new_number_post : new_number_pre;
+
+
+	if (strlen(chosen_number) > sizeof(called.number)) {
+		LOGP(DCC, LOGL_ERROR, "Number %s is too long for structure.\n",
+			chosen_number);
+		talloc_free(new_number_pre);
+		talloc_free(new_number_post);
 		return NULL;
 	}
 
@@ -140,8 +212,9 @@
 
 	out = msgb_alloc_headroom(4096, 128, "changed-setup");
 	if (!out) {
-		LOGP(DNAT, LOGL_ERROR, "Failed to allocate.\n");
-		talloc_free(new_number);
+		LOGP(DCC, LOGL_ERROR, "Failed to allocate.\n");
+		talloc_free(new_number_pre);
+		talloc_free(new_number_post);
 		return NULL;
 	}
 
@@ -155,15 +228,10 @@
 	memcpy(outptr, &hdr48->data[0], sec_len);
 
 	/* create the new number */
-	if (strncmp(new_number, "00", 2) == 0) {
-		called.type = 1;
-		strncpy(called.number, new_number + 2, sizeof(called.number));
-	} else {
-		/* rewrite international to unknown */
-		if (called.type == 1)
-			called.type = 0;
-		strncpy(called.number, new_number, sizeof(called.number));
-	}
+	update_called_number(&called, chosen_number);
+	LOGP(DCC, LOGL_DEBUG,
+		"Chosen number for IMSI(%s) is Plan(%d) Type(%d) Number(%s)\n",
+		imsi, called.plan, called.type, called.number);
 	gsm48_encode_called(out, &called);
 
 	/* copy thre rest */
@@ -173,7 +241,8 @@
 	outptr = msgb_put(out, sec_len);
 	memcpy(outptr, msgptr, sec_len);
 
-	talloc_free(new_number);
+	talloc_free(new_number_pre);
+	talloc_free(new_number_post);
 	return out;
 }
 
@@ -261,7 +330,7 @@
 			     const char *imsi, const char *dest_nr)
 {
 	return match_and_rewrite_number(ctx, dest_nr, imsi,
-					&nat->sms_num_rewr);
+					&nat->sms_num_rewr, NULL);
 }
 
 /**
@@ -600,6 +669,9 @@
 			continue;
 		}
 
+		if (strcmp("prefix_lookup", entry->replace) == 0)
+			entry->is_prefix_lookup = 1;
+
 		/* we will now build a regexp string */
 		if (cfg_entry->mcc[0] == '^') {
 			regexp = talloc_strdup(entry, cfg_entry->mcc);
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
new file mode 100644
index 0000000..faceb59
--- /dev/null
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
@@ -0,0 +1,259 @@
+/* Handling for loading a re-write file/database */
+/*
+ * (C) 2013 by On-Waves
+ * (C) 2013 by Holger Hans Peter Freyther <zecke@selfish.org>
+ * All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <openbsc/nat_rewrite_trie.h>
+#include <openbsc/debug.h>
+#include <openbsc/vty.h>
+
+#include <osmocom/core/talloc.h>
+#include <osmocom/core/utils.h>
+
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+
+#define CHECK_IS_DIGIT_OR_FAIL(prefix, pos)						\
+	if (!isdigit(prefix[pos]) && prefix[pos] != '+') {				\
+			LOGP(DNAT, LOGL_ERROR,						\
+				"Prefix(%s) contains non ascii text at(%d=%c)\n",	\
+				prefix, pos, prefix[pos]);				\
+			goto fail;							\
+	}
+#define TO_INT(c) \
+	((c) == '+' ? 10 : ((c - '0') % 10))
+
+static void insert_rewrite_node(struct nat_rewrite_rule *rule, struct nat_rewrite *root)
+{
+	struct nat_rewrite_rule *new = &root->rule;
+
+	const size_t len = strlen(rule->prefix);
+	int i;
+
+	if (len == 0) {
+		LOGP(DNAT, LOGL_ERROR, "An empty prefix does not make sense.\n");
+		goto fail;
+	}
+
+	for (i = 0; i < len - 1; ++i) {
+		int pos;
+
+		/* check if the input is valid */
+		CHECK_IS_DIGIT_OR_FAIL(rule->prefix, i);
+
+		/* check if the next node is already valid */
+		pos = TO_INT(rule->prefix[i]);
+		if (!new->rules[pos]) {
+			new->rules[pos] = talloc_zero(root, struct nat_rewrite_rule);
+			if (!new->rules[pos]) {
+				LOGP(DNAT, LOGL_ERROR,
+					"Failed to allocate memory.\n");
+				goto fail;
+			}
+
+			new->rules[pos]->empty = 1;
+		}
+
+		/* we continue here */
+		new = new->rules[pos];
+	}
+
+	/* new now points to the place where we want to add it */
+	int pos;
+
+	/* check if the input is valid */
+	CHECK_IS_DIGIT_OR_FAIL(rule->prefix, (len - 1));
+
+	/* check if the next node is already valid */
+	pos = TO_INT(rule->prefix[len - 1]);
+	if (!new->rules[pos])
+		new->rules[pos] = rule;
+	else if (new->rules[pos]->empty) {
+		/* copy over entries */
+		new->rules[pos]->empty = 0;
+		memcpy(new->rules[pos]->prefix, rule->prefix, sizeof(rule->prefix));
+		memcpy(new->rules[pos]->rewrite, rule->rewrite, sizeof(rule->rewrite));
+		talloc_free(rule);
+	} else {
+		LOGP(DNAT, LOGL_ERROR,
+			"Prefix(%s) is already installed\n", rule->prefix);
+		goto fail;
+	}
+
+	root->prefixes += 1;
+	return;
+
+fail:
+	talloc_free(rule);
+	return;
+}
+
+static void handle_line(struct nat_rewrite *rewrite, char *line)
+{
+	char *split;
+	struct nat_rewrite_rule *rule;
+	size_t size_prefix, size_end, len;
+
+
+	/* Find the ',' in the line */
+	len = strlen(line);
+	split = strstr(line, ",");
+	if (!split) {
+		LOGP(DNAT, LOGL_ERROR, "Line doesn't contain ','\n");
+		return;
+	}
+
+	/* Check if there is space for the rewrite rule */
+	size_prefix = split - line;
+	if (len - size_prefix <= 2) {
+		LOGP(DNAT, LOGL_ERROR, "No rewrite available.\n");
+		return;
+	}
+
+	/* Continue after the ',' to the end */
+	split = &line[size_prefix + 1];
+	size_end = strlen(split) - 1;
+
+	/* Check if both strings can fit into the static array */
+	if (size_prefix > sizeof(rule->prefix) - 1) {
+		LOGP(DNAT, LOGL_ERROR,
+			"Prefix is too long with %zu\n", size_prefix);
+		return;
+	}
+
+	if (size_end > sizeof(rule->rewrite) - 1) {
+		LOGP(DNAT, LOGL_ERROR,
+			"Rewrite is too long with %zu on %s\n",
+			size_end, &line[size_prefix + 1]);
+		return;
+	}
+
+	/* Now create the entry and insert it into the trie */
+	rule = talloc_zero(rewrite, struct nat_rewrite_rule);
+	if (!rule) {
+		LOGP(DNAT, LOGL_ERROR, "Can not allocate memory\n");
+		return;
+	}
+
+	memcpy(rule->prefix, line, size_prefix);
+	assert(size_prefix < sizeof(rule->prefix));
+	rule->prefix[size_prefix] = '\0';
+
+	memcpy(rule->rewrite, split, size_end);
+	assert(size_end < sizeof(rule->rewrite));
+	rule->rewrite[size_end] = '\0';
+
+	/* now insert and balance the tree */
+	insert_rewrite_node(rule, rewrite);
+}
+
+struct nat_rewrite *nat_rewrite_parse(void *ctx, const char *filename)
+{
+	FILE *file;
+	char *line = NULL;
+	size_t n = 2342;
+	struct nat_rewrite *res;
+
+	file = fopen(filename, "r");
+	if (!file)
+		return NULL;
+
+	res = talloc_zero(ctx, struct nat_rewrite);
+	if (!res) {
+		fclose(file);
+		return NULL;
+	}
+
+	/* mark the root as empty */
+	res->rule.empty = 1;
+
+	while (getline(&line, &n, file) != -1) {
+		handle_line(res, line);
+	}
+
+	free(line);
+	fclose(file);
+	return res;
+}
+
+/**
+ * Simple find that tries to do a longest match...
+ */
+struct nat_rewrite_rule *nat_rewrite_lookup(struct nat_rewrite *rewrite,
+					const char *prefix)
+{
+	struct nat_rewrite_rule *rule = &rewrite->rule;
+	struct nat_rewrite_rule *last = NULL;
+	const int len = OSMO_MIN(strlen(prefix), (sizeof(rule->prefix) - 1));
+	int i;
+
+	for (i = 0; rule && i < len; ++i) {
+		int pos;
+
+		CHECK_IS_DIGIT_OR_FAIL(prefix, i);
+		pos = TO_INT(prefix[i]);
+
+		rule = rule->rules[pos];
+		if (rule && !rule->empty)
+			last = rule;
+	}
+
+	return last;
+
+fail:
+	return NULL;
+}
+
+static void nat_rewrite_dump_rec(struct nat_rewrite_rule *rule)
+{
+	int i;
+	if (!rule->empty)
+		printf("%s,%s\n", rule->prefix, rule->rewrite);
+
+	for (i = 0; i < ARRAY_SIZE(rule->rules); ++i) {
+		if (!rule->rules[i])
+			continue;
+		nat_rewrite_dump_rec(rule->rules[i]);
+	}
+}
+
+void nat_rewrite_dump(struct nat_rewrite *rewrite)
+{
+	nat_rewrite_dump_rec(&rewrite->rule);
+}
+
+static void nat_rewrite_dump_rec_vty(struct vty *vty, struct nat_rewrite_rule *rule)
+{
+	int i;
+	if (!rule->empty)
+		vty_out(vty, "%s,%s%s", rule->prefix, rule->rewrite, VTY_NEWLINE);
+
+	for (i = 0; i < ARRAY_SIZE(rule->rules); ++i) {
+		if (!rule->rules[i])
+			continue;
+		nat_rewrite_dump_rec_vty(vty, rule->rules[i]);
+	}
+}
+
+void nat_rewrite_dump_vty(struct vty *vty, struct nat_rewrite *rewrite)
+{
+	nat_rewrite_dump_rec_vty(vty, &rewrite->rule);
+}
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c b/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
index 45c224c..bc8c4c1 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_utils.c
@@ -96,6 +96,7 @@
 	INIT_LLIST_HEAD(&nat->access_lists);
 	INIT_LLIST_HEAD(&nat->dests);
 	INIT_LLIST_HEAD(&nat->num_rewr);
+	INIT_LLIST_HEAD(&nat->num_rewr_post);
 	INIT_LLIST_HEAD(&nat->smsc_rewr);
 	INIT_LLIST_HEAD(&nat->tpdest_match);
 	INIT_LLIST_HEAD(&nat->sms_clear_tp_srr);
diff --git a/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c b/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c
index 46dc38e..0cac794 100644
--- a/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c
+++ b/openbsc/src/osmo-bsc_nat/bsc_nat_vty.c
@@ -1,6 +1,6 @@
 /* OpenBSC NAT interface to quagga VTY */
-/* (C) 2010-2012 by Holger Hans Peter Freyther
- * (C) 2010-2012 by On-Waves
+/* (C) 2010-2013 by Holger Hans Peter Freyther
+ * (C) 2010-2013 by On-Waves
  * All Rights Reserved
  *
  * This program is free software; you can redistribute it and/or modify
@@ -26,6 +26,7 @@
 #include <openbsc/gsm_04_08.h>
 #include <openbsc/mgcp.h>
 #include <openbsc/vty.h>
+#include <openbsc/nat_rewrite_trie.h>
 
 #include <osmocom/core/talloc.h>
 #include <osmocom/core/rate_ctr.h>
@@ -126,6 +127,10 @@
 
 	if (_nat->num_rewr_name)
 		vty_out(vty, " number-rewrite %s%s", _nat->num_rewr_name, VTY_NEWLINE);
+	if (_nat->num_rewr_post_name)
+		vty_out(vty, " number-rewrite-post %s%s",
+			_nat->num_rewr_post_name, VTY_NEWLINE);
+
 	if (_nat->smsc_rewr_name)
 		vty_out(vty, " rewrite-smsc addr %s%s",
 			_nat->smsc_rewr_name, VTY_NEWLINE);
@@ -138,6 +143,9 @@
 	if (_nat->sms_num_rewr_name)
 		vty_out(vty, " sms-number-rewrite %s%s",
 			_nat->sms_num_rewr_name, VTY_NEWLINE);
+	if (_nat->num_rewr_trie_name)
+		vty_out(vty, " prefix-tree %s%s",
+			_nat->num_rewr_trie_name, VTY_NEWLINE);
 
 	llist_for_each_entry(lst, &_nat->access_lists, list)
 		write_acc_lst(vty, lst);
@@ -554,6 +562,39 @@
 			     &_nat->num_rewr, argv[0]);
 }
 
+DEFUN(cfg_nat_no_number_rewrite,
+      cfg_nat_no_number_rewrite_cmd,
+      "no number-rewrite",
+      NO_STR "Set the file with rewriting rules.\n")
+{
+	talloc_free(_nat->num_rewr_name);
+	_nat->num_rewr_name = NULL;
+
+	bsc_nat_num_rewr_entry_adapt(NULL, &_nat->num_rewr, NULL);
+	return CMD_SUCCESS;
+}
+
+DEFUN(cfg_nat_number_rewrite_post,
+      cfg_nat_number_rewrite_post_cmd,
+      "number-rewrite-post FILENAME",
+      "Set the file with post-routing rewriting rules.\n" "Filename")
+{
+	return replace_rules(_nat, &_nat->num_rewr_post_name,
+			     &_nat->num_rewr_post, argv[0]);
+}
+
+DEFUN(cfg_nat_no_number_rewrite_post,
+      cfg_nat_no_number_rewrite_post_cmd,
+      "no number-rewrite-post",
+      NO_STR "Set the file with post-routing rewriting rules.\n")
+{
+	talloc_free(_nat->num_rewr_post_name);
+	_nat->num_rewr_post_name = NULL;
+
+	bsc_nat_num_rewr_entry_adapt(NULL, &_nat->num_rewr_post, NULL);
+	return CMD_SUCCESS;
+}
+
 DEFUN(cfg_nat_smsc_addr,
       cfg_nat_smsc_addr_cmd,
       "rewrite-smsc addr FILENAME",
@@ -621,6 +662,59 @@
 	return CMD_SUCCESS;
 }
 
+DEFUN(cfg_nat_prefix_trie,
+      cfg_nat_prefix_trie_cmd,
+      "prefix-tree FILENAME",
+      "Prefix tree for number rewriting\n" "File to load\n")
+{
+	/* give up the old data */
+	talloc_free(_nat->num_rewr_trie);
+	_nat->num_rewr_trie = NULL;
+
+	/* replace the file name */
+	bsc_replace_string(_nat, &_nat->num_rewr_trie_name, argv[0]);
+	if (!_nat->num_rewr_trie_name) {
+		vty_out(vty, "%% prefix-tree no filename is present.%s", VTY_NEWLINE);
+		return CMD_WARNING;
+	}
+
+	_nat->num_rewr_trie = nat_rewrite_parse(_nat, _nat->num_rewr_trie_name);
+	if (!_nat->num_rewr_trie) {
+		vty_out(vty, "%% prefix-tree parsing has failed.%s", VTY_NEWLINE);
+		return CMD_WARNING;
+	}
+
+	vty_out(vty, "%% prefix-tree loaded %zu rules.%s",
+		_nat->num_rewr_trie->prefixes, VTY_NEWLINE);
+	return CMD_SUCCESS;
+}
+
+DEFUN(cfg_nat_no_prefix_trie, cfg_nat_no_prefix_trie_cmd,
+      "no prefix-tree",
+      NO_STR "Prefix tree for number rewriting\n")
+{
+	talloc_free(_nat->num_rewr_trie);
+	_nat->num_rewr_trie = NULL;
+	talloc_free(_nat->num_rewr_trie_name);
+	_nat->num_rewr_trie_name = NULL;
+
+	return CMD_SUCCESS;
+}
+
+DEFUN(show_prefix_tree, show_prefix_tree_cmd,
+      "show prefix-tree",
+      SHOW_STR "Prefix tree for number rewriting\n")
+{
+	if (!_nat->num_rewr_trie) {
+		vty_out(vty, "%% there is now prefix tree loaded.%s",
+			VTY_NEWLINE);
+		return CMD_WARNING;
+	}
+
+	nat_rewrite_dump_vty(vty, _nat->num_rewr_trie);
+	return CMD_SUCCESS;
+}
+
 DEFUN(cfg_nat_ussd_lst_name,
       cfg_nat_ussd_lst_name_cmd,
       "ussd-list-name NAME",
@@ -1077,6 +1171,7 @@
 	install_element_ve(&show_bsc_mgcp_cmd);
 	install_element_ve(&show_acc_lst_cmd);
 	install_element_ve(&show_bar_lst_cmd);
+	install_element_ve(&show_prefix_tree_cmd);
 
 	install_element(ENABLE_NODE, &set_last_endp_cmd);
 	install_element(ENABLE_NODE, &block_new_conn_cmd);
@@ -1112,12 +1207,17 @@
 
 	/* number rewriting */
 	install_element(NAT_NODE, &cfg_nat_number_rewrite_cmd);
+	install_element(NAT_NODE, &cfg_nat_no_number_rewrite_cmd);
+	install_element(NAT_NODE, &cfg_nat_number_rewrite_post_cmd);
+	install_element(NAT_NODE, &cfg_nat_no_number_rewrite_post_cmd);
 	install_element(NAT_NODE, &cfg_nat_smsc_addr_cmd);
 	install_element(NAT_NODE, &cfg_nat_smsc_tpdest_cmd);
 	install_element(NAT_NODE, &cfg_nat_sms_clear_tpsrr_cmd);
 	install_element(NAT_NODE, &cfg_nat_no_sms_clear_tpsrr_cmd);
 	install_element(NAT_NODE, &cfg_nat_sms_number_rewrite_cmd);
 	install_element(NAT_NODE, &cfg_nat_no_sms_number_rewrite_cmd);
+	install_element(NAT_NODE, &cfg_nat_prefix_trie_cmd);
+	install_element(NAT_NODE, &cfg_nat_no_prefix_trie_cmd);
 
 	install_element(NAT_NODE, &cfg_nat_pgroup_cmd);
 	install_element(NAT_NODE, &cfg_nat_no_pgroup_cmd);
diff --git a/openbsc/tests/Makefile.am b/openbsc/tests/Makefile.am
index c9afeed..0597c14 100644
--- a/openbsc/tests/Makefile.am
+++ b/openbsc/tests/Makefile.am
@@ -1,7 +1,7 @@
 SUBDIRS = gsm0408 db channel mgcp gprs si abis
 
 if BUILD_NAT
-SUBDIRS += bsc-nat
+SUBDIRS += bsc-nat bsc-nat-trie
 endif
 
 if BUILD_SMPP
diff --git a/openbsc/tests/bsc-nat-trie/Makefile.am b/openbsc/tests/bsc-nat-trie/Makefile.am
new file mode 100644
index 0000000..355ed64
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/Makefile.am
@@ -0,0 +1,18 @@
+AM_CPPFLAGS = $(all_includes) -I$(top_srcdir)/include
+AM_CFLAGS=-Wall -ggdb3 $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGSM_CFLAGS) $(LIBOSMOSCCP_CFLAGS) $(LIBOSMOABIS_CFLAGS) $(COVERAGE_CFLAGS)
+AM_LDFLAGS = $(COVERAGE_LDFLAGS)
+
+EXTRA_DIST = bsc_nat_trie_test.ok prefixes.csv
+
+noinst_PROGRAMS = bsc_nat_trie_test
+
+bsc_nat_trie_test_SOURCES = bsc_nat_trie_test.c \
+			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c
+bsc_nat_trie_test_LDADD = $(top_builddir)/src/libbsc/libbsc.a \
+			$(top_srcdir)/src/libctrl/libctrl.a \
+			$(top_srcdir)/src/libmgcp/libmgcp.a \
+			$(top_srcdir)/src/libtrau/libtrau.a \
+			$(top_srcdir)/src/libcommon/libcommon.a \
+			$(LIBOSMOCORE_LIBS) $(LIBOSMOGSM_LIBS) -lrt \
+			$(LIBOSMOSCCP_LIBS) $(LIBOSMOVTY_LIBS) \
+			$(LIBOSMOABIS_LIBS)
diff --git a/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c
new file mode 100644
index 0000000..4b4df2f
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.c
@@ -0,0 +1,87 @@
+/*
+ * (C) 2013 by On-Waves
+ * (C) 2013 by Holger Hans Peter Freyther <zecke@selfish.org>
+ * All Rights Reserved
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published by
+ * the Free Software Foundation; either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <openbsc/nat_rewrite_trie.h>
+#include <openbsc/debug.h>
+
+#include <osmocom/core/application.h>
+#include <osmocom/core/backtrace.h>
+#include <osmocom/core/talloc.h>
+#include <osmocom/core/utils.h>
+
+#include <string.h>
+
+int main(int argc, char **argv)
+{
+	struct nat_rewrite *trie;
+
+	osmo_init_logging(&log_info);
+
+	printf("Testing the trie\n");
+
+	trie = nat_rewrite_parse(NULL, "prefixes.csv");
+	OSMO_ASSERT(trie);
+
+	/* verify that it has been parsed */
+	OSMO_ASSERT(trie->prefixes == 17);
+	printf("Dumping the internal trie\n");
+	nat_rewrite_dump(trie);
+
+	/* now do the matching... */
+	OSMO_ASSERT(!nat_rewrite_lookup(trie, ""));
+	OSMO_ASSERT(!nat_rewrite_lookup(trie, "2"));
+
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1")->rewrite, "1") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12")->rewrite, "2") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123")->rewrite, "3") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234")->rewrite, "4") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345")->rewrite, "5") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123456")->rewrite, "6") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234567")->rewrite, "7") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678")->rewrite, "8") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "123456789")->rewrite, "9") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1234567890")->rewrite, "10") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "13")->rewrite, "11") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "14")->rewrite, "12") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "15")->rewrite, "13") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "16")->rewrite, "14") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "823455")->rewrite, "15") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "82")->rewrite, "16") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "+49123445")->rewrite, "17") == 0);
+
+	/* match a prefix */
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "121")->rewrite, "2") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "1292323")->rewrite, "2") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678901")->rewrite, "10") == 0);
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "160")->rewrite, "14") == 0);
+
+	OSMO_ASSERT(strcmp(nat_rewrite_lookup(trie, "12345678901123452123123")->rewrite, "10") == 0);
+
+	/* invalid input */
+	OSMO_ASSERT(!nat_rewrite_lookup(trie, "12abc"));
+
+	talloc_free(trie);
+
+	trie = nat_rewrite_parse(NULL, "does_not_exist.csv");
+	OSMO_ASSERT(!trie);
+
+	printf("Done with the tests.\n");
+	return 0;
+}
diff --git a/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok
new file mode 100644
index 0000000..4d4cc99
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/bsc_nat_trie_test.ok
@@ -0,0 +1,20 @@
+Testing the trie
+Dumping the internal trie
+1,1
+12,2
+123,3
+1234,4
+12345,5
+123456,6
+1234567,7
+12345678,8
+123456789,9
+1234567890,10
+13,11
+14,12
+15,13
+16,14
+82,16
+823455,15
++49123,17
+Done with the tests.
diff --git a/openbsc/tests/bsc-nat-trie/prefixes.csv b/openbsc/tests/bsc-nat-trie/prefixes.csv
new file mode 100644
index 0000000..35485b1
--- /dev/null
+++ b/openbsc/tests/bsc-nat-trie/prefixes.csv
@@ -0,0 +1,25 @@
+1,1
+12,2
+123,3
+1234,4
+12345,5
+123456,6
+1234567,7
+12345678,8
+123456789,9
+1234567890,10
+13,11
+14,12
+15,13
+16,14
+823455,15
+82,16
++49123,17
+1ABC,18
+12345678901234567890,19
+,20
+14A,21
+124,324324324234
+1234567890,10
+no line
+99,
diff --git a/openbsc/tests/bsc-nat/Makefile.am b/openbsc/tests/bsc-nat/Makefile.am
index 0847678..1078d9b 100644
--- a/openbsc/tests/bsc-nat/Makefile.am
+++ b/openbsc/tests/bsc-nat/Makefile.am
@@ -2,7 +2,7 @@
 AM_CFLAGS=-Wall -ggdb3 $(LIBOSMOCORE_CFLAGS) $(LIBOSMOGSM_CFLAGS) $(LIBOSMOSCCP_CFLAGS) $(LIBOSMOABIS_CFLAGS) $(COVERAGE_CFLAGS)
 AM_LDFLAGS = $(COVERAGE_LDFLAGS)
 
-EXTRA_DIST = bsc_nat_test.ok bsc_data.c barr.cfg barr_dup.cfg
+EXTRA_DIST = bsc_nat_test.ok bsc_data.c barr.cfg barr_dup.cfg prefixes.csv
 
 noinst_PROGRAMS = bsc_nat_test
 
@@ -12,6 +12,7 @@
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_utils.c \
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_filter.c \
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_rewrite.c \
+			$(top_srcdir)/src/osmo-bsc_nat/bsc_nat_rewrite_trie.c \
 			$(top_srcdir)/src/osmo-bsc_nat/bsc_mgcp_utils.c
 bsc_nat_test_LDADD = $(top_builddir)/src/libbsc/libbsc.a \
 			$(top_srcdir)/src/libctrl/libctrl.a \
diff --git a/openbsc/tests/bsc-nat/bsc_nat_test.c b/openbsc/tests/bsc-nat/bsc_nat_test.c
index 4a244db..5158f46 100644
--- a/openbsc/tests/bsc-nat/bsc_nat_test.c
+++ b/openbsc/tests/bsc-nat/bsc_nat_test.c
@@ -26,6 +26,7 @@
 #include <openbsc/gsm_data.h>
 #include <openbsc/bsc_nat.h>
 #include <openbsc/bsc_nat_sccp.h>
+#include <openbsc/nat_rewrite_trie.h>
 
 #include <osmocom/core/application.h>
 #include <osmocom/core/backtrace.h>
@@ -451,6 +452,8 @@
 		printf("Should have found it.\n");
 		abort();
 	}
+
+	talloc_free(nat);
 }
 
 static void test_mgcp_allocations(void)
@@ -819,6 +822,7 @@
 	}
 
 	msgb_free(msg);
+	talloc_free(nat);
 }
 
 static void test_dt_filter()
@@ -1039,6 +1043,117 @@
 	verify_msg(out, cc_setup_national_again,
 			ARRAY_SIZE(cc_setup_national_again));
 	msgb_free(out);
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr, NULL);
+	talloc_free(nat);
+}
+
+static void test_setup_rewrite_prefix(void)
+{
+	struct msgb *msg = msgb_alloc(4096, "test_dt_filter");
+	struct msgb *out;
+	struct bsc_nat_parsed *parsed;
+	const char *imsi = "27408000001234";
+
+	struct bsc_nat *nat = bsc_nat_alloc();
+
+	/* a fake list */
+	struct osmo_config_list entries;
+	struct osmo_config_entry entry;
+
+	INIT_LLIST_HEAD(&entries.entry);
+	entry.mcc = "274";
+	entry.mnc = "08";
+	entry.option = "^0([1-9])";
+	entry.text = "prefix_lookup";
+	llist_add_tail(&entry.list, &entries.entry);
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr, &entries);
+
+        nat->num_rewr_trie = nat_rewrite_parse(nat, "prefixes.csv");
+
+	msgb_reset(msg);
+	copy_to_msg(msg, cc_setup_national, ARRAY_SIZE(cc_setup_national));
+	parsed = bsc_nat_parse(msg);
+	if (!parsed) {
+		printf("FAIL: Could not parse ID resp\n");
+		abort();
+	}
+
+	out = bsc_nat_rewrite_msg(nat, msg, parsed, imsi);
+	if (!out) {
+		printf("FAIL: A new message should be created.\n");
+		abort();
+	}
+
+	if (msg == out) {
+		printf("FAIL: The message should have changed\n");
+		abort();
+	}
+
+	verify_msg(out, cc_setup_national_patched, ARRAY_SIZE(cc_setup_national_patched));
+	msgb_free(out);
+
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr, NULL);
+	talloc_free(nat);
+}
+
+static void test_setup_rewrite_post(void)
+{
+	struct msgb *msg = msgb_alloc(4096, "test_dt_filter");
+	struct msgb *out;
+	struct bsc_nat_parsed *parsed;
+	const char *imsi = "27408000001234";
+
+	struct bsc_nat *nat = bsc_nat_alloc();
+
+	/* a fake list */
+	struct osmo_config_list entries;
+	struct osmo_config_entry entry;
+	struct osmo_config_list entries_post;
+	struct osmo_config_entry entry_post;
+
+	INIT_LLIST_HEAD(&entries.entry);
+	entry.mcc = "274";
+	entry.mnc = "08";
+	entry.option = "^0([1-9])";
+	entry.text = "0049";
+	llist_add_tail(&entry.list, &entries.entry);
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr, &entries);
+
+	/* attempt to undo the previous one */
+	INIT_LLIST_HEAD(&entries_post.entry);
+	entry_post.mcc = "274";
+	entry_post.mnc = "08";
+	entry_post.option = "^\\+49([1-9])";
+	entry_post.text = "prefix_lookup";
+	llist_add_tail(&entry_post.list, &entries_post.entry);
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr_post, &entries_post);
+
+        nat->num_rewr_trie = nat_rewrite_parse(nat, "prefixes.csv");
+
+	msgb_reset(msg);
+	copy_to_msg(msg, cc_setup_national, ARRAY_SIZE(cc_setup_national));
+	parsed = bsc_nat_parse(msg);
+	if (!parsed) {
+		printf("FAIL: Could not parse ID resp\n");
+		abort();
+	}
+
+	out = bsc_nat_rewrite_msg(nat, msg, parsed, imsi);
+	if (!out) {
+		printf("FAIL: A new message should be created.\n");
+		abort();
+	}
+
+	if (msg == out) {
+		printf("FAIL: The message should have changed\n");
+		abort();
+	}
+
+	verify_msg(out, cc_setup_national, ARRAY_SIZE(cc_setup_national));
+	msgb_free(out);
+
+	bsc_nat_num_rewr_entry_adapt(nat, &nat->num_rewr, NULL);
+	talloc_free(nat);
 }
 
 static void test_sms_smsc_rewrite()
@@ -1322,6 +1437,8 @@
 	test_cr_filter();
 	test_dt_filter();
 	test_setup_rewrite();
+	test_setup_rewrite_prefix();
+	test_setup_rewrite_post();
 	test_sms_smsc_rewrite();
 	test_sms_number_rewrite();
 	test_mgcp_allocations();
diff --git a/openbsc/tests/bsc-nat/prefixes.csv b/openbsc/tests/bsc-nat/prefixes.csv
new file mode 100644
index 0000000..0c7660f
--- /dev/null
+++ b/openbsc/tests/bsc-nat/prefixes.csv
@@ -0,0 +1,2 @@
+0172,0049
++49,0
diff --git a/openbsc/tests/testsuite.at b/openbsc/tests/testsuite.at
index ea3fa1c..e54d4b5 100644
--- a/openbsc/tests/testsuite.at
+++ b/openbsc/tests/testsuite.at
@@ -34,6 +34,7 @@
 AT_SETUP([bsc-nat])
 AT_KEYWORDS([bsc-nat])
 AT_CHECK([test "$enable_nat_test" != no || exit 77])
+cp $abs_srcdir/bsc-nat/prefixes.csv .
 cp $abs_srcdir/bsc-nat/barr.cfg .
 cp $abs_srcdir/bsc-nat/barr_dup.cfg .
 cat $abs_srcdir/bsc-nat/bsc_nat_test.ok > expout
@@ -48,6 +49,14 @@
 AT_CHECK([$abs_top_builddir/tests/smpp/smpp_test], [], [expout], [experr])
 AT_CLEANUP
 
+AT_SETUP([bsc-nat-trie])
+AT_KEYWORDS([bsc-nat-trie])
+AT_CHECK([test "$enable_nat_test" != no || exit 77])
+cp $abs_srcdir/bsc-nat-trie/prefixes.csv .
+cat $abs_srcdir/bsc-nat-trie/bsc_nat_trie_test.ok > expout
+AT_CHECK([$abs_top_builddir/tests/bsc-nat-trie/bsc_nat_trie_test], [], [expout], [ignore])
+AT_CLEANUP
+
 AT_SETUP([si])
 AT_KEYWORDS([si])
 cat $abs_srcdir/si/si_test.ok > expout
diff --git a/openbsc/tests/vty_test_runner.py b/openbsc/tests/vty_test_runner.py
index 778cde0..730b8ba 100644
--- a/openbsc/tests/vty_test_runner.py
+++ b/openbsc/tests/vty_test_runner.py
@@ -96,8 +96,41 @@
     def vty_app(self):
         return (4244, "src/osmo-bsc_nat/osmo-bsc_nat",  "OsmoBSCNAT", "nat")
 
-    def testMoo(self):
-        pass
+    def testRewriteNoRewrite(self):
+        self.vty.enable()
+        res = self.vty.command("configure terminal")
+        res = self.vty.command("nat")
+        res = self.vty.command("number-rewrite rewrite.cfg")
+        res = self.vty.command("no number-rewrite")
+
+    def testRewritePostNoRewrite(self):
+        self.vty.enable()
+        self.vty.command("configure terminal")
+        self.vty.command("nat")
+        self.vty.verify("number-rewrite-post rewrite.cfg", [''])
+        self.vty.verify("no number-rewrite-post", [''])
+
+
+    def testPrefixTreeLoading(self):
+        cfg = os.path.join(confpath, "tests/bsc-nat-trie/prefixes.csv")
+
+        self.vty.enable()
+        self.vty.command("configure terminal")
+        self.vty.command("nat")
+        res = self.vty.command("prefix-tree %s" % cfg)
+        self.assertEqual(res, "% prefix-tree loaded 17 rules.")
+        self.vty.command("end")
+
+        res = self.vty.command("show prefix-tree")
+        self.assertEqual(res, '1,1\r\n12,2\r\n123,3\r\n1234,4\r\n12345,5\r\n123456,6\r\n1234567,7\r\n12345678,8\r\n123456789,9\r\n1234567890,10\r\n13,11\r\n14,12\r\n15,13\r\n16,14\r\n82,16\r\n823455,15\r\n+49123,17')
+
+        self.vty.command("configure terminal")
+        self.vty.command("nat")
+        self.vty.command("no prefix-tree")
+        self.vty.command("end")
+
+        res = self.vty.command("show prefix-tree")
+        self.assertEqual(res, "% there is now prefix tree loaded.")
 
 
 def add_nat_test(suite, workdir):