More tests for bn functions.

6 files changed, 281 insertions, 79 deletions

diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml
index f2e480d..5ba5a27 100644
--- a/.github/workflows/test.yml
+++ b/.github/workflows/test.yml
@@ -50,7 +50,7 @@ jobs:
           make test
       - name: Test (C)
         run: |
-          cd test && make test_bn && ./test_bn && cd ..
+          cd test && make test && cd ..
       - name: Code coverage
         uses: codecov/codecov-action@v3
         if: ${{ matrix.python-version == 3.9 }}
diff --git a/Makefile b/Makefile
index faeaacb..3d19252 100644
--- a/Makefile
+++ b/Makefile
@@ -1,5 +1,3 @@
-TESTS = test_builder test_client test_render test_impl test_simulator
-
 test:
 	pytest -m "not slow" --cov=pyecsca.codegen
 
diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c
index 7f91cfd..02371e2 100644
--- a/pyecsca/codegen/bn/bn.c
+++ b/pyecsca/codegen/bn/bn.c
@@ -49,6 +49,10 @@ bn_err bn_from_hex(const char *data, bn_t *out) {
 	return mp_read_radix(out, data, 16);
 }
 
+bn_err bn_from_dec(const char *data, bn_t *out) {
+    return mp_read_radix(out, data, 10);
+}
+
 bn_err bn_from_int(unsigned int value, bn_t *out) {
 	if (sizeof(unsigned int) == 8) {
 		mp_set_u64(out, value);
@@ -396,6 +400,9 @@ wnaf_t *bn_wnaf(const bn_t *bn, int w) {
 	}
 	wnaf_t *result = NULL;
 
+	size_t bits = bn_bit_length(bn) + 1;
+    int8_t arr[bits];
+
 	bn_t half_width;
 	if (mp_init(&half_width) != BN_OKAY) {
 		return NULL;
@@ -420,38 +427,38 @@ wnaf_t *bn_wnaf(const bn_t *bn, int w) {
 		goto exit_val_mod;
 	}
 
-	result = malloc(sizeof(wnaf_t));
-	result->w = w;
-	result->length = bn_bit_length(bn) + 1;
-	result->data = calloc(result->length, sizeof(int8_t));
-
 	size_t i = 0;
-	while (!bn_is_0(&k) && !(bn_get_sign(&k) == BN_NEG)) {
+	while (mp_cmp_d(&k, 0) == MP_GT) {
 		if (bn_get_bit(&k, 0) == 1) {
 			bn_mod(&k, &full_width, &val_mod);
 			if (mp_cmp(&val_mod, &half_width) == MP_GT) {
 				if (mp_sub(&val_mod, &full_width, &val_mod) != BN_OKAY) {
-					free(result->data);
-					free(result);
-					result = NULL;
-					break;
+					goto exit_result;
 				}
 			}
 			int8_t val = (int8_t) mp_get_i32(&val_mod);
-			result->data[i++] = val;
+			arr[i++] = val;
 			if (mp_sub(&k, &val_mod, &k) != BN_OKAY) {
-				free(result->data);
-				free(result);
-				result = NULL;
-				break;
+				goto exit_result;
 			}
 		} else {
-			result->data[i++] = 0;
+			arr[i++] = 0;
 		}
 		bn_rsh(&k, 1, &k);
 	}
-	bn_clear(&val_mod);
 
+	result = malloc(sizeof(wnaf_t));
+	result->w = w;
+	result->length = i;
+	result->data = calloc(result->length, sizeof(int8_t));
+
+    // Revert
+    for (size_t j = 0; j < i; j++) {
+        result->data[j] = arr[i - j - 1];
+    }
+
+exit_result:
+    bn_clear(&val_mod);
 exit_val_mod:
 	bn_clear(&k);
 exit_k:
@@ -465,6 +472,20 @@ wnaf_t *bn_bnaf(const bn_t *bn) {
 	return bn_wnaf(bn, 2);
 }
 
+void bn_naf_extend(wnaf_t *naf, size_t new_length) {
+    if (new_length <= naf->length) {
+        return;
+    }
+    int8_t *new_data = calloc(new_length, sizeof(int8_t));
+    size_t diff = new_length - naf->length;
+    for (size_t i = 0; i < naf->length; i++) {
+        new_data[i + diff] = naf->data[i];
+    }
+    free(naf->data);
+    naf->data = new_data;
+    naf->length = new_length;
+}
+
 wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w) {
     if (w > 8 || w < 2) {
 		return NULL;
@@ -606,7 +627,9 @@ small_base_t *bn_convert_base_small(const bn_t *bn, int m) {
 	bn_copy(bn, &k);
 
     int len = 0;
-    if (mp_log_n(&k, m, &len) != BN_OKAY) {
+    if (mp_cmp_d(&k, 0) == MP_EQ) {
+        len = 0;
+    } else if (mp_log_n(&k, m, &len) != BN_OKAY) {
         goto exit_len;
     }
 
@@ -642,7 +665,9 @@ large_base_t *bn_convert_base_large(const bn_t *bn, const bn_t *m) {
 	bn_copy(bn, &k);
 
     int len = 0;
-    if (mp_log(&k, m, &len) != BN_OKAY) {
+    if (mp_cmp_d(&k, 0) == MP_EQ) {
+        len = 0;
+    } else if (mp_log(&k, m, &len) != BN_OKAY) {
         goto exit_len;
     }
 
diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h
index 58bd6df..4e69474 100644
--- a/pyecsca/codegen/bn/bn.h
+++ b/pyecsca/codegen/bn/bn.h
@@ -88,6 +88,7 @@ void    bn_clear(bn_t *bn);
 
 bn_err bn_from_bin(const uint8_t *data, size_t size, bn_t *out);
 bn_err bn_from_hex(const char *data, bn_t *out);
+bn_err bn_from_dec(const char *data, bn_t *out);
 bn_err bn_from_int(unsigned int value, bn_t *out);
 
 bn_err bn_to_binpad(const bn_t *one, uint8_t *data, size_t size);
@@ -137,6 +138,7 @@ int     bn_bit_length(const bn_t *bn);
 
 wnaf_t *bn_wnaf(const bn_t *bn, int w);
 wnaf_t *bn_bnaf(const bn_t *bn);
+void bn_naf_extend(wnaf_t *naf, size_t new_length);
 
 wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w);
 wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w);
diff --git a/test/Makefile b/test/Makefile
index eb6724a..d0068a2 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -1,3 +1,13 @@
 
-test_bn: test_bn.c ../pyecsca/codegen/bn/bn.c
+test_bn_san: test_bn.c ../pyecsca/codegen/bn/bn.c
 	gcc -g -o $@ $^ -fsanitize=address -fsanitize=undefined -I ../pyecsca/codegen/ -I ../pyecsca/codegen/tommath/ -L ../pyecsca/codegen/tommath/ -l:libtommath-HOST.a
+
+test_bn_val: test_bn.c ../pyecsca/codegen/bn/bn.c
+	gcc -g -o $@ $^ -I ../pyecsca/codegen/ -I ../pyecsca/codegen/tommath/ -L ../pyecsca/codegen/tommath/ -l:libtommath-HOST.a
+
+
+test: test_bn_san test_bn_val
+	./test_bn_san
+	valgrind -q ./test_bn_val
+
+.PHONY: test
\ No newline at end of file
diff --git a/test/test_bn.c b/test/test_bn.c
index 1f6d14d..66ce377 100644
--- a/test/test_bn.c
+++ b/test/test_bn.c
@@ -4,55 +4,80 @@
 
 int test_wsliding_ltr() {
     printf("test_wsliding_ltr: ");
-    bn_t bn;
-    bn_init(&bn);
-    bn_from_int(181, &bn);
-    wsliding_t *ws = bn_wsliding_ltr(&bn, 3);
-    if (ws == NULL) {
-        printf("NULL\n");
-        return 1;
-    }
-    if (ws->length != 6) {
-        printf("Bad length (%li instead of 6)\n", ws->length);
-        return 1;
-    }
-    uint8_t expected[6] = {5, 0, 0, 5, 0, 1};
-    for (int i = 0; i < 6; i++) {
-        if (ws->data[i] != expected[i]) {
-            printf("Bad data (%i instead of %i)\n", ws->data[i], expected[i]);
-            return 1;
+    int failed = 0;
+    struct {
+        const char *value;
+        int w;
+        int expected_len;
+        uint8_t expected[100]; // max expected length
+    } cases[] = {
+        // sliding_window_ltr begin
+        {"181", 3, 6, {5, 0, 0, 5, 0, 1}},
+        {"1", 3, 1, {1}},
+        {"1234", 2, 11, {1, 0, 0, 0, 3, 0, 1, 0, 0, 1, 0}},
+        {"170", 4, 6, {5, 0, 0, 0, 5, 0}},
+        {"554", 5, 6, {17, 0, 0, 0, 5, 0}},
+        {"123456789123456789123456789", 5, 83, {25, 1, 0, 0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 23, 0, 0, 0, 0, 25, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 29, 0, 0, 0, 0, 17, 0, 0, 0, 0, 19, 0, 0, 0, 0, 29, 0, 0, 0, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 0, 21}}
+        // sliding_window_ltr end
+    };
+    int num_cases = sizeof(cases) / sizeof(cases[0]);
+    for (int t = 0; t < num_cases; t++) {
+        bn_t bn;
+        bn_init(&bn);
+        bn_from_dec(cases[t].value, &bn);
+        wsliding_t *ws = bn_wsliding_ltr(&bn, cases[t].w);
+        if (ws == NULL) {
+            printf("Case %d: NULL\n", t);
+            failed++;
+            bn_clear(&bn);
+            continue;
+        }
+        if (ws->length != cases[t].expected_len) {
+            printf("Case %d: Bad length (%li instead of %i)\n", t, ws->length, cases[t].expected_len);
+            failed++;
+        }
+        for (int i = 0; i < cases[t].expected_len; i++) {
+            if (ws->data[i] != cases[t].expected[i]) {
+                printf("Case %d: Bad data at %d (%i instead of %i)\n", t, i, ws->data[i], cases[t].expected[i]);
+                failed++;
+                break;
+            }
         }
+        bn_clear(&bn);
+        free(ws->data);
+        free(ws);
     }
-    printf("OK\n");
-    bn_clear(&bn);
-    free(ws->data);
-    free(ws);
-    return 0;
+    if (failed == 0) {
+        printf("OK\n");
+    } else {
+        printf("FAILED (%d cases)\n", failed);
+    }
+    return failed;
 }
 
 int test_wsliding_rtl() {
     printf("test_wsliding_rtl: ");
     int failed = 0;
     struct {
-        int value;
+        const char *value;
         int w;
         int expected_len;
-        uint8_t expected[16]; // max expected length
+        uint8_t expected[100]; // max expected length
     } cases[] = {
-        // Original test
-        {181, 3, 8, {1, 0, 0, 3, 0, 0, 0, 5}},
-        // Edge case: 1
-        {1, 3, 1, {1}},
-        // w = 2, value = 1234
-        {1234, 2, 11, {1, 0, 0, 0, 3, 0, 1, 0, 0, 1, 0}},
-        // w = 4, value = 0b10101010
-        {0b10101010, 4, 6, {5, 0, 0, 0, 5, 0}},
+        // sliding_window_rtl begin
+        {"181", 3, 8, {1, 0, 0, 3, 0, 0, 0, 5}},
+        {"1", 3, 1, {1}},
+        {"1234", 2, 11, {1, 0, 0, 0, 3, 0, 1, 0, 0, 1, 0}},
+        {"170", 4, 6, {5, 0, 0, 0, 5, 0}},
+        {"554", 5, 10, {1, 0, 0, 0, 0, 0, 0, 0, 21, 0}},
+        {"123456789123456789123456789",5, 87, {1, 0, 0, 0, 0, 19, 0, 0, 0, 0, 1, 0, 0, 0, 0, 29, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 17, 0, 0, 0, 0, 27, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0, 0, 0, 0, 21}}
+        // sliding_window_rtl end
     };
     int num_cases = sizeof(cases) / sizeof(cases[0]);
     for (int t = 0; t < num_cases; t++) {
         bn_t bn;
         bn_init(&bn);
-        bn_from_int(cases[t].value, &bn);
+        bn_from_dec(cases[t].value, &bn);
         wsliding_t *ws = bn_wsliding_rtl(&bn, cases[t].w);
         if (ws == NULL) {
             printf("Case %d: NULL\n", t);
@@ -83,34 +108,176 @@ int test_wsliding_rtl() {
     return failed;
 }
 
-int test_convert_base() {
-    printf("test_convert_base: ");
-    bn_t bn;
-    bn_init(&bn);
-    bn_from_int(11, &bn);
-    small_base_t *bs = bn_convert_base_small(&bn, 2);
-    if (bs == NULL) {
-        printf("NULL\n");
-        return 1;
+int test_convert_base_small() {
+    printf("test_convert_base_small: ");
+    int failed = 0;
+    struct {
+        const char *value;
+        int base;
+        int expected_len;
+        uint8_t expected[100]; // max expected length
+    } cases[] = {
+        // convert_base_small begin
+        {"11", 2, 4, {1, 1, 0, 1}},
+        {"255", 2, 8, {1, 1, 1, 1, 1, 1, 1, 1}},
+        {"1234", 10, 4, {4, 3, 2, 1}},
+        {"0", 2, 1, {0}},
+        {"1", 2, 1, {1}},
+        {"123456789123456789123456789", 16, 22, {5, 1, 15, 5, 4, 0, 12, 7, 15, 9, 1, 11, 3, 14, 2, 15, 13, 15, 14, 1, 6, 6}}
+        // convert_base_small end
+    };
+    int num_cases = sizeof(cases) / sizeof(cases[0]);
+    for (int t = 0; t < num_cases; t++) {
+        bn_t bn;
+        bn_init(&bn);
+        bn_from_dec(cases[t].value, &bn);
+        small_base_t *bs = bn_convert_base_small(&bn, cases[t].base);
+        if (bs == NULL) {
+            printf("Case %d: NULL\n", t);
+            failed++;
+            bn_clear(&bn);
+            continue;
+        }
+        if (bs->length != cases[t].expected_len) {
+            printf("Case %d: Bad length (%li instead of %i)\n", t, bs->length, cases[t].expected_len);
+            failed++;
+        }
+        for (int i = 0; i < cases[t].expected_len; i++) {
+            if (bs->data[i] != cases[t].expected[i]) {
+                printf("Case %d: Bad data at %d (%i instead of %i)\n", t, i, bs->data[i], cases[t].expected[i]);
+                failed++;
+                break;
+            }
+        }
+        bn_clear(&bn);
+        free(bs->data);
+        free(bs);
     }
-    if (bs->length != 4) {
-        printf("Bad length (%li instead of 4)\n", bs->length);
-        return 1;
+    if (failed == 0) {
+        printf("OK\n");
+    } else {
+        printf("FAILED (%d cases)\n", failed);
     }
-    uint8_t expected[4] = {1, 1, 0, 1};
-    for (int i = 0; i < 4; i++) {
-        if (bs->data[i] != expected[i]) {
-            printf("Bad data (%i insead of %i)\n", bs->data[i], expected[i]);
-            return 1;
+    return failed;
+}
+
+int test_convert_base_large() {
+    printf("test_convert_base_large: ");
+    int failed = 0;
+    struct {
+        const char *value;
+        const char *base;
+        int expected_len;
+        const char *expected[100]; // max expected length
+    } cases[] = {
+        // convert_base_large begin
+        {"123456789123456", "2", 47, {"0", "0", "0", "0", "0", "0", "0", "1", "1", "0", "0", "0", "1", "0", "0", "1", "1", "1", "1", "1", "0", "0", "0", "0", "0", "1", "1", "0", "0", "0", "0", "1", "0", "0", "0", "1", "0", "0", "1", "0", "0", "0", "0", "0", "1", "1", "1"}},
+        {"123456789123456789123456789", "123456", 6, {"104661", "75537", "83120", "74172", "37630", "4"}},
+        {"352099265818416392997042486274568094251", "18446744073709551616", 3, {"12367597952119210539", "640595372834356666", "1"}}
+        // convert_base_large end
+    };
+    int num_cases = sizeof(cases) / sizeof(cases[0]);
+    for (int t = 0; t < num_cases; t++) {
+        bn_t bn, base;
+        bn_init(&bn);
+        bn_init(&base);
+        bn_from_dec(cases[t].value, &bn);
+        bn_from_dec(cases[t].base, &base);
+        large_base_t *bs = bn_convert_base_large(&bn, &base);
+        if (bs == NULL) {
+            printf("Case %d: NULL\n", t);
+            failed++;
+            bn_clear(&bn);
+            bn_clear(&base);
+            continue;
+        }
+        if (bs->length != cases[t].expected_len) {
+            printf("Case %d: Bad length (%li instead of %i)\n", t, bs->length, cases[t].expected_len);
+            failed++;
+        }
+        for (int i = 0; i < cases[t].expected_len; i++) {
+            bn_t exp;
+            bn_init(&exp);
+            bn_from_dec(cases[t].expected[i], &exp);
+            if (!bn_eq(&bs->data[i], &exp)) {
+                printf("Case %d: Bad data at %d\n", t, i);
+                failed++;
+                bn_clear(&exp);
+                break;
+            }
+            bn_clear(&exp);
+        }
+        for (int i = 0; i < bs->length; i++) {
+            bn_clear(&bs->data[i]);
+        }
+        bn_clear(&bs->m);
+        bn_clear(&bn);
+        bn_clear(&base);
+        free(bs->data);
+        free(bs);
+    }
+    if (failed == 0) {
+        printf("OK\n");
+    } else {
+        printf("FAILED (%d cases)\n", failed);
+    }
+    return failed;
+}
+
+int test_bn_wnaf() {
+    printf("test_bn_wnaf: ");
+    int failed = 0;
+    struct {
+        const char *value;
+        int w;
+        int expected_len;
+        int8_t expected[100]; // max expected length
+    } cases[] = {
+        // wnaf begin
+        {"19", 2, 5, {1, 0, 1, 0, -1}},
+        {"45", 3, 5, {3, 0, 0, 0, -3}},
+        {"0", 3, 0, {}},
+        {"1", 2, 1, {1}},
+        {"21", 4, 5, {1, 0, 0, 0, 5}},
+        {"123456789", 3, 28, {1, 0, 0, -1, 0, 0, 3, 0, 0, -1, 0, 0, 0, 0, 0, -3, 0, 0, 0, -3, 0, 0, 0, 0, 3, 0, 0, -3}},
+        {"123456789123456789123456789", 5, 84, {13, 0, 0, 0, 0, 0, -15, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -13, 0, 0, 0, 0, 0, -7, 0, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, 13, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, -7, 0, 0, 0, 0, -11}}
+        // wnaf end
+    };
+    int num_cases = sizeof(cases) / sizeof(cases[0]);
+    for (int t = 0; t < num_cases; t++) {
+        bn_t bn;
+        bn_init(&bn);
+        bn_from_dec(cases[t].value, &bn);
+        wnaf_t *naf = bn_wnaf(&bn, cases[t].w);
+        if (naf == NULL) {
+            printf("Case %d: NULL\n", t);
+            failed++;
+            bn_clear(&bn);
+            continue;
+        }
+        if (naf->length != cases[t].expected_len) {
+            printf("Case %d: Bad length (%li instead of %i)\n", t, naf->length, cases[t].expected_len);
+            failed++;
+        }
+        for (int i = 0; i < cases[t].expected_len; i++) {
+            if (naf->data[i] != cases[t].expected[i]) {
+                printf("Case %d: Bad data at %d (%i instead of %i)\n", t, i, naf->data[i], cases[t].expected[i]);
+                failed++;
+                break;
+            }
         }
+        bn_clear(&bn);
+        free(naf->data);
+        free(naf);
     }
-    printf("OK\n");
-    bn_clear(&bn);
-    free(bs->data);
-    free(bs);
-    return 0;
+    if (failed == 0) {
+        printf("OK\n");
+    } else {
+        printf("FAILED (%d cases)\n", failed);
+    }
+    return failed;
 }
 
 int main(void) {
-    return test_wsliding_ltr() + test_wsliding_rtl() + test_convert_base();
+    return test_wsliding_ltr() + test_wsliding_rtl() + test_convert_base_small() + test_convert_base_large() + test_bn_wnaf();
 }