Add booth recoding functions with tests.

3 files changed, 132 insertions, 1 deletions

diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c
index 6dea91c..8805b69 100644
--- a/pyecsca/codegen/bn/bn.c
+++ b/pyecsca/codegen/bn/bn.c
@@ -791,4 +791,60 @@ void bn_large_base_clear(large_base_t *lb) {
     free(lb->data);
     bn_clear(&lb->m);
     free(lb);
+}
+
+int32_t bn_booth_word(int32_t digit, int32_t w) {
+    int32_t s = ~((digit >> w) - 1);  //s = ~((digit >> w) - 1)
+    int32_t d = (1 << (w + 1)) - digit - 1;  //d = (1 << (w + 1)) - digit - 1
+    d = (d & s) | (digit & ~s); // d = (d & s) | (digit & ~s)
+    d = (d >> 1) + (d & 1); //d = (d >> 1) + (d & 1)
+
+    if (s) { //return -d if s else d
+        return -d;
+    } else {
+        return d;
+    }
+}
+
+booth_t *bn_booth(const bn_t *bn, int w, size_t bits) {
+    if (w >= 30) {
+        return NULL;
+    }
+    int32_t mask = (1 << (w + 1)) - 1;
+    bn_t d, m;
+    bn_init(&d);
+    bn_init(&m);
+    bn_from_int(mask, &m);
+
+    size_t len = (bits / w) + 1;
+    booth_t *result = malloc(sizeof(booth_t));
+    result->length = len;
+    result->w = w;
+    result->data = calloc(len, sizeof(int32_t));
+
+    long l = 0;
+    for (long i = bits + (w - (bits % w) - 1); i > 0; i -= w) {
+        int32_t digit;
+        bn_copy(bn, &d);
+        if (i >= w) {
+            bn_rsh(&d, i - w, &d);
+        } else {
+            bn_lsh(&d, w - i, &d);
+        }
+        bn_and(&d, &m, &d);
+        digit = bn_to_int(&d);
+        int32_t val = bn_booth_word(digit, w);
+        result->data[l++] = val;
+    }
+    bn_clear(&d);
+    bn_clear(&m);
+    return result;
+}
+
+void bn_booth_clear(booth_t *booth) {
+    if (booth == NULL) {
+        return;
+    }
+    free(booth->data);
+    free(booth);
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h
index d6a6add..03526b0 100644
--- a/pyecsca/codegen/bn/bn.h
+++ b/pyecsca/codegen/bn/bn.h
@@ -76,6 +76,12 @@ typedef struct {
     bn_t m;
 } large_base_t;
 
+typedef struct {
+	int32_t *data;
+	size_t length;
+	int w;
+} booth_t;
+
 void math_init(void);
 
 extern const int bn_digit_bits;
@@ -154,4 +160,8 @@ void          bn_small_base_clear(small_base_t *sb);
 large_base_t *bn_convert_base_large(const bn_t *bn, const bn_t *m);
 void          bn_large_base_clear(large_base_t *lb);
 
+int32_t  bn_booth_word(int32_t digit, int32_t w);
+booth_t *bn_booth(const bn_t *bn, int32_t w, size_t bits);
+void     bn_booth_clear(booth_t *booth);
+
 #endif //BN_H_
\ No newline at end of file
diff --git a/test/test_bn.c b/test/test_bn.c
index 2d3461c..b04c936 100644
--- a/test/test_bn.c
+++ b/test/test_bn.c
@@ -336,6 +336,71 @@ int test_bn_wnaf_manipulation() {
     return 0;
 }
 
+int test_booth() {
+    printf("test_booth: ");
+    for (int i = 0; i < (1 << 6); i++) {
+        int32_t bw = bn_booth_word(i, 5);
+        if (i <= 31) {
+            if (bw != (i + 1) / 2) {
+                printf("FAILED (bad booth for %d: %d instead of %d)\n", i, bw, (i + 1) / 2);
+                return 1;
+            }
+        } else {
+            if (bw != -((64 - i) / 2)) {
+                printf("FAILED (bad booth for %d: %d instead of %d)\n", i, bw, -((64 - i) / 2));
+                return 1;
+            }
+        }
+    }
+    int failed = 0;
+    struct {
+        const char *value;
+        int w;
+        size_t bits;
+        int expected_len;
+        int32_t expected[256]; // max expected length
+    } cases[] = {
+        // booth begin
+        {"12345678123456781234567812345678123456781234567812345678", 1, 224, 225, {0, 0, 0, 1, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, -1, 0, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, -1, 0, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, -1, 0, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, -1, 0, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, -1, 0, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, -1, 0, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 1, -1, 0, 1, -1, 0, 0, 1, 0, -1, 1, -1, 0, 0, 1, -1, 1, -1, 1, 0, -1, 0, 1, 0, 0, 0, -1, 0, 0, 0}},
+        {"12345678123456781234567812345678123456781234567812345678", 2, 224, 113, {0, 0, 1, 1, -2, 1, -1, 1, 0, 1, 1, 2, -2, 2, 0, -2, 0, 0, 1, 1, -2, 1, -1, 1, 0, 1, 1, 2, -2, 2, 0, -2, 0, 0, 1, 1, -2, 1, -1, 1, 0, 1, 1, 2, -2, 2, 0, -2, 0, 0, 1, 1, -2, 1, -1, 1, 0, 1, 1, 2, -2, 2, 0, -2, 0, 0, 1, 1, -2, 1, -1, 1, 0, 1, 1, 2, -2, 2, 0, -2, 0, 0, 1, 1, -2, 1, -1, 1, 0, 1, 1, 2, -2, 2, 0, -2, 0, 0, 1, 1, -2, 1, -1, 1, 0, 1, 1, 2, -2, 2, 0, -2, 0}},
+        {"12345678123456781234567812345678123456781234567812345678", 5, 224, 45, {1, 4, 13, 3, -10, 15, 0, 9, 3, 9, -10, -12, -8, 2, 9, -6, 5, 13, -2, 1, -14, 7, -15, 11, 8, -16, 5, -14, -12, 11, -6, -4, 1, 4, 13, 3, -10, 15, 0, 9, 3, 9, -10, -12, -8}},
+        {"12345678123456781234567812345678123456781234567812345678", 16, 224, 15, {0, 4660, 22136, 4660, 22136, 4660, 22136, 4660, 22136, 4660, 22136, 4660, 22136, 4660, 22136}},
+        {"12345678123456781234567812345678123456781234567812345678", 24, 224, 10, {18, 3430008, 1193046, 7868980, 5666834, 3430008, 1193046, 7868980, 5666834, 3430008}},
+        {"12345678123456781234567812345678123456781234567812345678", 30, 224, 0, {}}
+        // booth 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_hex(cases[t].value, &bn);
+        booth_t *booth = bn_booth(&bn, cases[t].w, cases[t].bits);
+        if (booth == NULL && cases[t].expected_len != 0) {
+            printf("Case %d: NULL\n", t);
+            failed++;
+            bn_clear(&bn);
+            continue;
+        }
+        if (cases[t].expected_len != 0) {
+            if (booth->length != cases[t].expected_len) {
+                printf("Case %d: Bad length (%li instead of %i)\n", t, booth->length, cases[t].expected_len);
+                failed++;
+            }
+            for (int i = 0; i < cases[t].expected_len; i++) {
+                if (booth->data[i] != cases[t].expected[i]) {
+                    printf("FAILED (bad booth data at %d: %d instead of %d)\n", i, booth->data[i], cases[t].expected[i]);
+                    failed++;
+                    break;
+                }
+            }
+        }
+        bn_clear(&bn);
+        bn_booth_clear(booth);
+    }
+    printf("OK\n");
+    return 0;
+}
+
 int main(void) {
-    return test_wsliding_ltr() + test_wsliding_rtl() + test_convert_base_small() + test_convert_base_large() + test_bn_wnaf() + test_bn_wnaf_manipulation();
+    return test_wsliding_ltr() + test_wsliding_rtl() + test_convert_base_small() + test_convert_base_large() + test_bn_wnaf() + test_bn_wnaf_manipulation() + test_booth();
 }