Implement multipliers.

2 files changed, 76 insertions, 0 deletions

diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c
index dd22ca1..635eaae 100644
--- a/pyecsca/codegen/bn/bn.c
+++ b/pyecsca/codegen/bn/bn.c
@@ -1,4 +1,6 @@
 #include "bn.h"
+#include <string.h>
+#include <stdlib.h>
 
 bn_err bn_init(bn_t *bn) {
 	return mp_init(bn);
@@ -28,6 +30,7 @@ int bn_from_int(uint64_t value, bn_t *out) {
 void bn_to_binpad(const bn_t *one, uint8_t *data, size_t size) {
 	size_t ubin_size = mp_ubin_size(one);
 	size_t offset = size - ubin_size;
+	memset(data, 0, offset);
 	mp_to_ubin(one, data + offset, ubin_size, NULL);
 }
 
@@ -109,6 +112,18 @@ bool bn_eq(const bn_t *one, const bn_t *other) {
 	return mp_cmp_mag(one, other) == MP_EQ;
 }
 
+bool bn_is_0(const bn_t *one) {
+	return mp_cmp_d(one, 0) == MP_EQ;
+}
+
+bool bn_is_1(const bn_t *one) {
+	return mp_cmp_d(one, 1) == MP_EQ;
+}
+
+bn_sign bn_get_sign(const bn_t *one) {
+	return one->sign;
+}
+
 int bn_get_bit(const bn_t *bn, int which) {
 	int which_digit = which / MP_DIGIT_BIT;
 	int which_bit = which % MP_DIGIT_BIT;
@@ -120,4 +135,53 @@ int bn_get_bit(const bn_t *bn, int which) {
 
 int bn_bit_length(const bn_t *bn) {
 	return mp_count_bits(bn);
+}
+
+wnaf_t *bn_wnaf(const bn_t *bn, int w) {
+	if (w > 8 || w < 2) {
+		return NULL;
+	}
+	wnaf_t *result = malloc(sizeof(wnaf_t));
+	result->w = w;
+	result->length = bn_bit_length(bn) + 1;
+	result->data = calloc(result->length, sizeof(int8_t));
+
+	bn_t half_width;
+	bn_init(&half_width);
+	bn_from_int(1, &half_width);
+	bn_lsh(&half_width, w - 1, &half_width);
+	bn_t full_width;
+	bn_init(&full_width);
+	bn_from_int(1, &full_width);
+	bn_lsh(&full_width, w, &full_width);
+
+	bn_t k; bn_init(&k);
+	bn_copy(bn, &k);
+
+	bn_t val_mod; bn_init(&val_mod);
+
+	size_t i = 0;
+	while (!bn_is_0(&k) && !(bn_get_sign(&k) == MP_NEG)) {
+		if (bn_get_bit(&k, 0) == 1) {
+			bn_mod(&k, &full_width, &val_mod);
+			if (mp_cmp(&val_mod, &half_width) == MP_GT) {
+				mp_sub(&val_mod, &full_width, &val_mod);
+			}
+			int8_t val = (int8_t) mp_get_i32(&val_mod);
+			result->data[i++] = val;
+			mp_sub(&k, &val_mod, &k);
+		} else {
+			result->data[i++] = 0;
+		}
+		bn_rsh(&k, 1, &k);
+	}
+	bn_clear(&val_mod);
+	bn_clear(&half_width);
+	bn_clear(&full_width);
+	bn_clear(&k);
+	return result;
+}
+
+wnaf_t *bn_bnaf(const bn_t *bn) {
+	return bn_wnaf(bn, 2);
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/bn/bn.h b/pyecsca/codegen/bn/bn.h
index 68ede2f..a5b1ba9 100644
--- a/pyecsca/codegen/bn/bn.h
+++ b/pyecsca/codegen/bn/bn.h
@@ -5,12 +5,19 @@
 
 #define bn_t mp_int
 #define bn_err mp_err
+#define bn_sign mp_sign
 
 typedef struct {
 	char name;
 	bn_t value;
 } named_bn_t;
 
+typedef struct {
+	int8_t *data;
+	size_t length;
+	int w;
+} wnaf_t;
+
 bn_err bn_init(bn_t *bn);
 void bn_copy(const bn_t *from, bn_t *to);
 void bn_clear(bn_t *bn);
@@ -45,8 +52,13 @@ void bn_lsh(const bn_t *one, int amount, bn_t *out);
 void bn_rsh(const bn_t *one, int amount, bn_t *out);
 
 bool bn_eq(const bn_t *one, const bn_t *other);
+bool bn_is_0(const bn_t *one);
+bool bn_is_1(const bn_t *one);
+bn_sign bn_get_sign(const bn_t *one);
 
 int bn_get_bit(const bn_t *bn, int which);
 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);
 
 #endif //BN_H_
\ No newline at end of file