19 files changed, 435 insertions, 72 deletions

diff --git a/pyecsca/codegen/bn/bn.c b/pyecsca/codegen/bn/bn.c
index 148403c..d7a44b6 100644
--- a/pyecsca/codegen/bn/bn.c
+++ b/pyecsca/codegen/bn/bn.c
@@ -27,6 +27,8 @@ void math_init(void) {
 	#endif //TODO: COMBA
 }
 
+const int bn_digit_bits __attribute__((used)) = MP_DIGIT_BIT;
+
 bn_err bn_init(bn_t *bn) {
 	return mp_init(bn);
 }
@@ -47,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);
@@ -394,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;
@@ -418,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:
@@ -463,6 +472,90 @@ wnaf_t *bn_bnaf(const bn_t *bn) {
 	return bn_wnaf(bn, 2);
 }
 
+void bn_naf_pad_left(wnaf_t *naf, int8_t value, size_t amount) {
+    if (amount == 0) {
+        return;
+    }
+    int8_t *new_data = calloc(naf->length + amount, sizeof(int8_t));
+    for (size_t i = 0; i < naf->length; i++) {
+        new_data[i + amount] = naf->data[i];
+    }
+    for (size_t i = 0; i < amount; i++) {
+        new_data[i] = value;
+    }
+    free(naf->data);
+    naf->data = new_data;
+    naf->length += amount;
+}
+
+void bn_naf_pad_right(wnaf_t *naf, int8_t value, size_t amount) {
+    if (amount == 0) {
+        return;
+    }
+    naf->data = realloc(naf->data, (naf->length + amount) * sizeof(int8_t));
+    for (size_t i = naf->length; i < naf->length + amount; i++) {
+        naf->data[i] = value;
+    }
+    naf->length += amount;
+}
+
+void bn_naf_strip_left(wnaf_t *naf, int8_t value) {
+    size_t i = 0;
+    while (i < naf->length && naf->data[i] == value) {
+        i++;
+    }
+    if (i == 0) {
+        return;
+    }
+    if (i == naf->length) {
+        free(naf->data);
+        naf->data = NULL;
+        naf->length = 0;
+        return;
+    }
+    int8_t *new_data = calloc(naf->length - i, sizeof(int8_t));
+    for (size_t j = 0; j < naf->length - i; j++) {
+        new_data[j] = naf->data[j + i];
+    }
+    free(naf->data);
+    naf->data = new_data;
+    naf->length -= i;
+}
+
+void bn_naf_strip_right(wnaf_t *naf, int8_t value) {
+    size_t i = naf->length;
+    while (i > 0 && naf->data[i - 1] == value) {
+        i--;
+    }
+    if (i == naf->length) {
+        return;
+    }
+    if (i == 0) {
+        free(naf->data);
+        naf->data = NULL;
+        naf->length = 0;
+        return;
+    }
+    naf->data = realloc(naf->data, i * sizeof(int8_t));
+    naf->length = i;
+}
+
+void bn_naf_reverse(wnaf_t *naf) {
+    for (size_t i = 0; i < naf->length / 2; i++) {
+        int8_t temp = naf->data[i];
+        naf->data[i] = naf->data[naf->length - i - 1];
+        naf->data[naf->length - i - 1] = temp;
+    }
+}
+
+void bn_naf_clear(wnaf_t *naf) {
+    if (naf == NULL) {
+        return;
+    }
+    free(naf->data);
+    free(naf);
+}
+
 wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w) {
     if (w > 8 || w < 2) {
 		return NULL;
@@ -540,8 +633,8 @@ wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w) {
 	wsliding_t *result = NULL;
 
     int blen = bn_bit_length(bn);
-    uint8_t arr[blen + 2];
-    memset(arr, 0, (blen + 2) * sizeof(uint8_t));
+    uint8_t arr[blen + w];
+    memset(arr, 0, (blen + w) * sizeof(uint8_t));
 
     bn_t k;
 	if (mp_init(&k) != BN_OKAY) {
@@ -555,7 +648,7 @@ wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w) {
 	}
 
     int 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)) {
             arr[i++] = 0;
             bn_rsh(&k, 1, &k);
@@ -594,6 +687,14 @@ exit_k:
 	return result;
 }
 
+void bn_wsliding_clear(wsliding_t *wsliding) {
+    if (wsliding == NULL) {
+        return;
+    }
+    free(wsliding->data);
+    free(wsliding);
+}
+
 small_base_t *bn_convert_base_small(const bn_t *bn, int m) {
     small_base_t *result = NULL;
 
@@ -604,7 +705,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;
     }
 
@@ -630,6 +733,14 @@ exit_k:
     return result;
 }
 
+void bn_small_base_clear(small_base_t *sb) {
+    if (sb == NULL) {
+        return;
+    }
+    free(sb->data);
+    free(sb);
+}
+
 large_base_t *bn_convert_base_large(const bn_t *bn, const bn_t *m) {
     large_base_t *result = NULL;
 
@@ -640,7 +751,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;
     }
 
@@ -666,4 +779,72 @@ exit_len:
     bn_clear(&k);
 exit_k:
     return result;
+}
+
+void bn_large_base_clear(large_base_t *lb) {
+    if (lb == NULL) {
+        return;
+    }
+    for (int i = 0; i < lb->length; i++) {
+        bn_clear(&lb->data[i]);
+    }
+    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, int32_t 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 7c25c22..03526b0 100644
--- a/pyecsca/codegen/bn/bn.h
+++ b/pyecsca/codegen/bn/bn.h
@@ -76,8 +76,16 @@ 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;
+
 bn_err  bn_init(bn_t *bn);
 #define bn_init_multi mp_init_multi
 bn_err  bn_copy(const bn_t *from, bn_t *to);
@@ -86,6 +94,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);
@@ -135,11 +144,24 @@ 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_pad_left(wnaf_t *naf, int8_t value, size_t amount);
+void    bn_naf_pad_right(wnaf_t *naf, int8_t value, size_t amount);
+void    bn_naf_strip_left(wnaf_t *naf, int8_t value);
+void    bn_naf_strip_right(wnaf_t *naf, int8_t value);
+void    bn_naf_reverse(wnaf_t *naf);
+void    bn_naf_clear(wnaf_t *naf);
 
 wsliding_t *bn_wsliding_ltr(const bn_t *bn, int w);
 wsliding_t *bn_wsliding_rtl(const bn_t *bn, int w);
+void        bn_wsliding_clear(wsliding_t *wsliding);
 
 small_base_t *bn_convert_base_small(const bn_t *bn, int m);
+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/pyecsca/codegen/builder.py b/pyecsca/codegen/builder.py
index 63e7801..b7b5e22 100644
--- a/pyecsca/codegen/builder.py
+++ b/pyecsca/codegen/builder.py
@@ -81,7 +81,7 @@ def get_multiplier(ctx: click.Context, param, value: Optional[str]) -> Optional[
     if value is None:
         return None
     res = re.match(
-        "(?P<name>[a-zA-Z\-]+)\((?P<args>([a-zA-Z_]+ *= *[a-zA-Z0-9.]+, ?)*?([a-zA-Z_]+ *= *[a-zA-Z0-9.]+)*)\)",
+        r"(?P<name>[a-zA-Z\-]+)\((?P<args>([a-zA-Z_]+ *= *[a-zA-Z0-9.]+, ?)*?([a-zA-Z_]+ *= *[a-zA-Z0-9.]+)*)\)",
         value)
     if not res:
         raise click.BadParameter("Couldn't parse multiplier spec: {}.".format(value))
diff --git a/pyecsca/codegen/render.py b/pyecsca/codegen/render.py
index 692deab..b1c1477 100644
--- a/pyecsca/codegen/render.py
+++ b/pyecsca/codegen/render.py
@@ -30,7 +30,7 @@ from pyecsca.ec.mult import (
     BGMWMultiplier,
     CombMultiplier,
     AccumulationOrder,
-    ProcessingDirection
+    ProcessingDirection, WindowBoothMultiplier
 )
 from pyecsca.ec.op import OpType, CodeOp
 
@@ -227,6 +227,7 @@ def render_scalarmult_impl(scalarmult: ScalarMultiplier) -> str:
                                              DifferentialLadderMultiplier=DifferentialLadderMultiplier,
                                              BinaryNAFMultiplier=BinaryNAFMultiplier,
                                              WindowNAFMultiplier=WindowNAFMultiplier,
+                                             WindowBoothMultiplier=WindowBoothMultiplier,
                                              SlidingWindowMultiplier=SlidingWindowMultiplier,
                                              FixedWindowLTRMultiplier=FixedWindowLTRMultiplier,
                                              FullPrecompMultiplier=FullPrecompMultiplier,
diff --git a/pyecsca/codegen/templates/formula_add.c b/pyecsca/codegen/templates/formula_add.c
index 6026601..48bab07 100644
--- a/pyecsca/codegen/templates/formula_add.c
+++ b/pyecsca/codegen/templates/formula_add.c
@@ -16,16 +16,17 @@ __attribute__((noinline)) void point_add(const point_t *one, const point_t *othe
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(other, out_one);
-			return;
+			goto end;
 		}
 		if (point_equals(other, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("add") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_dbl.c b/pyecsca/codegen/templates/formula_dbl.c
index 451b0ee..e1cfa15 100644
--- a/pyecsca/codegen/templates/formula_dbl.c
+++ b/pyecsca/codegen/templates/formula_dbl.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_dbl(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("dbl") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_neg.c b/pyecsca/codegen/templates/formula_neg.c
index 93fbe20..fa96c63 100644
--- a/pyecsca/codegen/templates/formula_neg.c
+++ b/pyecsca/codegen/templates/formula_neg.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_neg(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("neg") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_scl.c b/pyecsca/codegen/templates/formula_scl.c
index 48ac52e..f1471a2 100644
--- a/pyecsca/codegen/templates/formula_scl.c
+++ b/pyecsca/codegen/templates/formula_scl.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_scl(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("scl") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/formula_tpl.c b/pyecsca/codegen/templates/formula_tpl.c
index d280bad..0b4cd64 100644
--- a/pyecsca/codegen/templates/formula_tpl.c
+++ b/pyecsca/codegen/templates/formula_tpl.c
@@ -16,12 +16,13 @@ __attribute__((noinline)) void point_tpl(const point_t *one, const curve_t *curv
 	{%- if short_circuit %}
 		if (point_equals(one, curve->neutral)) {
 			point_set(one, out_one);
-			return;
+			goto end;
 		}
 	{%- endif %}
 	{{ ops.render_initializations(initializations) }}
 	{{ ops.render_ops(operations) }}
 	{{ ops.render_returns(returns) }}
 	//NOP_128();
+end:
 	{{ end_action("tpl") }}
 }
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult.c b/pyecsca/codegen/templates/mult.c
index 0144e36..4070952 100644
--- a/pyecsca/codegen/templates/mult.c
+++ b/pyecsca/codegen/templates/mult.c
@@ -31,6 +31,10 @@
 
     {% include "mult_wnaf.c" %}
 
+{%- elif isinstance(scalarmult, WindowBoothMultiplier) -%}
+
+    {% include "mult_booth.c" %}
+
 {%- elif isinstance(scalarmult, SlidingWindowMultiplier) -%}
 
     {% include "mult_sliding_w.c" %}
diff --git a/pyecsca/codegen/templates/mult_bgmw.c b/pyecsca/codegen/templates/mult_bgmw.c
index 5298fb1..e2e8c72 100644
--- a/pyecsca/codegen/templates/mult_bgmw.c
+++ b/pyecsca/codegen/templates/mult_bgmw.c
@@ -48,8 +48,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
         {%- endif %}
         point_accumulate(a, b, curve, a);
 	}
-	free(bs->data);
-	free(bs);
+	bn_small_base_clear(bs);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(a, curve, a);
diff --git a/pyecsca/codegen/templates/mult_bnaf.c b/pyecsca/codegen/templates/mult_bnaf.c
index 68d1569..9c760af 100644
--- a/pyecsca/codegen/templates/mult_bnaf.c
+++ b/pyecsca/codegen/templates/mult_bnaf.c
@@ -1,51 +1,109 @@
 #include "mult.h"
 #include "point.h"
 
-point_t *scalar_mult_ltr(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf) {
-    point_t *q = point_copy(curve->neutral);
-	for (long i = naf->length - 1; i >= 0; i--) {
+point_t *scalar_mult_ltr(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf, size_t bits) {
+    point_t *q;
+    long i;
+    {% if scalarmult.complete %}
+	    bn_naf_pad_left(naf, 0, (bits + 1) - naf->length);
+	    q = point_copy(curve->neutral);
+	    i = 0;
+	{% else %}
+	    bn_naf_strip_left(naf, 0);
+	    int8_t val = naf->data[0];
+	    if (val == 1) {
+            q = point_copy(point);
+	    } else if (val == -1) {
+            q = point_copy(neg);
+        }
+        i = 1;
+	{% endif %}
+
+    {% if scalarmult.always %}
+        point_t *q_copy = point_new();
+    {% endif %}
+	for (; i < naf->length; i++) {
 		point_dbl(q, curve, q);
+
+		{% if scalarmult.always %}
+            point_set(q, q_copy);
+        {% endif %}
+
 		if (naf->data[i] == 1) {
 			point_accumulate(q, point, curve, q);
+			{% if scalarmult.always %}
+                point_accumulate(q_copy, neg, curve, q_copy);
+            {% endif %}
 		} else if (naf->data[i] == -1) {
 			point_accumulate(q, neg, curve, q);
+			{% if scalarmult.always %}
+                point_accumulate(q_copy, point, curve, q_copy);
+            {% endif %}
 		}
 	}
+	{% if scalarmult.always %}
+        point_free(q_copy);
+    {% endif %}
     return q;
 }
 
-point_t* scalar_mult_rtl(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf) {
-    point_t *r = point_copy(point);
-    point_t *q = point_copy(curve->neutral);
-    point_t *r_neg = point_new();
+point_t* scalar_mult_rtl(point_t *point, point_t *neg, curve_t *curve, wnaf_t *naf, size_t bits) {
+    {% if scalarmult.always %}
+        point_t *r_copy = point_new();
+    {% endif %}
+
+    {% if scalarmult.complete %}
+	    bn_naf_pad_left(naf, 0, (bits + 1) - naf->length);
+	{% endif %}
+
+	bn_naf_reverse(naf);
+
+    point_t *q = point_copy(point);
+    point_t *r = point_copy(curve->neutral);
+    point_t *q_neg = point_new();
     for (long i = 0; i < naf->length; i++) {
+        {% if scalarmult.always %}
+            point_set(r, r_copy);
+        {% endif %}
+
         if (naf->data[i] == 1) {
-            point_accumulate(q, r, curve, q);
+            point_accumulate(r, q, curve, r);
+            {% if scalarmult.always %}
+                point_neg(q, curve, q_neg);
+                point_accumulate(r_copy, q_neg, curve, r_copy);
+            {% endif %}
         } else if (naf->data[i] == -1) {
-            point_neg(r, curve, r_neg);
-            point_accumulate(q, r_neg, curve, q);
+            point_neg(q, curve, q_neg);
+            point_accumulate(r, q_neg, curve, r);
+            {% if scalarmult.always %}
+                point_accumulate(r_copy, q, curve, r_copy);
+            {% endif %}
         }
-        point_dbl(r, curve, r);
+        point_dbl(q, curve, q);
     }
-    point_free(r_neg);
-    point_free(r);
+    point_free(q_neg);
+    point_free(q);
 
-    return q;
+    {% if scalarmult.always %}
+        point_free(r_copy);
+    {% endif %}
+    return r;
 }
 
 static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
 	point_t *neg = point_new();
 	point_neg(point, curve, neg);
+
 	wnaf_t *naf = bn_bnaf(scalar);
+	size_t bits = bn_bit_length(&curve->n);
 
     {% if scalarmult.direction == ProcessingDirection.LTR %}
-        point_t *q = scalar_mult_ltr(point, neg, curve, naf);
+        point_t *q = scalar_mult_ltr(point, neg, curve, naf, bits);
     {% elif scalarmult.direction == ProcessingDirection.RTL %}
-        point_t *q = scalar_mult_rtl(point, neg, curve, naf);
+        point_t *q = scalar_mult_rtl(point, neg, curve, naf, bits);
     {% endif %}
 
-    free(naf->data);
-	free(naf);
+    bn_naf_clear(naf);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(q, curve, q);
diff --git a/pyecsca/codegen/templates/mult_booth.c b/pyecsca/codegen/templates/mult_booth.c
new file mode 100644
index 0000000..4c1ba40
--- /dev/null
+++ b/pyecsca/codegen/templates/mult_booth.c
@@ -0,0 +1,78 @@
+#include "mult.h"
+#include "point.h"
+
+
+
+static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
+    point_t *points[{{ 2 ** (scalarmult.width - 1) }}];
+    {% if scalarmult.precompute_negation %}
+        point_t *points_neg[{{ 2 ** (scalarmult.width - 1) }}];
+    {% endif %}
+
+    point_t *current = point_copy(point);
+    point_t *dbl = point_new();
+    point_dbl(current, curve, dbl);
+    points[0] = point_copy(current);
+    {% if scalarmult.precompute_negation %}
+        points_neg[0] = point_new();
+        point_neg(points[0], curve, points_neg[0]);
+    {% endif %}
+    {% if scalarmult.width > 1 %}
+        points[1] = point_copy(dbl);
+        {% if scalarmult.precompute_negation %}
+            points_neg[1] = point_new();
+            point_neg(points[1], curve, points_neg[1]);
+        {% endif %}
+    {% endif %}
+
+    point_set(dbl, current);
+    {% if scalarmult.width > 2 %}
+        for (long i = 2; i < {{ 2 ** (scalarmult.width - 1) }}; i++) {
+            point_add(current, point, curve, current);
+            points[i] = point_copy(current);
+            {% if scalarmult.precompute_negation %}
+                points_neg[i] = point_new();
+                point_neg(points[i], curve, points_neg[i]);
+            {% endif %}
+        }
+    {% endif %}
+    point_free(current);
+    point_free(dbl);
+
+    size_t bits = bn_bit_length(&curve->n);
+
+    booth_t *bs = bn_booth(scalar, {{ scalarmult.width }}, bits);
+
+    point_t *q = point_copy(curve->neutral);
+    point_t *neg = point_new();
+    for (long i = 0; i < bs->length; i++) {
+        for (long j = 0; j < {{ scalarmult.width }}; j++) {
+            point_dbl(q, curve, q);
+        }
+        int32_t val = bs->data[i];
+        if (val > 0) {
+            point_accumulate(q, points[val - 1], curve, q);
+        } else if (val < 0) {
+            {% if scalarmult.precompute_negation %}
+                point_accumulate(q, points_neg[-val - 1], curve, q);
+            {% else %}
+                point_neg(points[-val - 1], curve, neg);
+                point_accumulate(q, neg, curve, q);
+            {% endif %}
+        }
+    }
+    bn_booth_clear(bs);
+    point_free(neg);
+
+    {%- if "scl" in scalarmult.formulas %}
+        point_scl(q, curve, q);
+    {%- endif %}
+    point_set(q, out);
+    for (long i = 0; i < {{ 2 ** (scalarmult.width - 1) }}; i++) {
+        point_free(points[i]);
+        {% if scalarmult.precompute_negation %}
+            point_free(points_neg[i]);
+        {% endif %}
+    }
+    point_free(q);
+}
\ No newline at end of file
diff --git a/pyecsca/codegen/templates/mult_comb.c b/pyecsca/codegen/templates/mult_comb.c
index 9df9796..1fbb5a3 100644
--- a/pyecsca/codegen/templates/mult_comb.c
+++ b/pyecsca/codegen/templates/mult_comb.c
@@ -39,6 +39,10 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 	bn_from_int(1, &base);
     bn_lsh(&base, d, &base);
 
+    {% if scalarmult.always %}
+        point_t *dummy = point_new();
+    {% endif %}
+
 	large_base_t *bs = bn_convert_base_large(scalar, &base);
 	for (int i = d - 1; i >= 0; i--) {
         point_dbl(q, curve, q);
@@ -50,14 +54,18 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
         }
         if (word) {
             point_accumulate(q, points[word], curve, q);
+        } else {
+            {% if scalarmult.always %}
+                int j = i % {{ 2**scalarmult.width }};
+                if (j == 0) {
+                    point_accumulate(q, point, curve, dummy);
+                } else {
+                    point_accumulate(q, points[j], curve, dummy);
+                }
+            {% endif %}
         }
 	}
-	for (int i = 0; i < bs->length; i++) {
-	    bn_clear(&bs->data[i]);
-	}
-	free(bs->data);
-	bn_clear(&bs->m);
-	free(bs);
+	bn_large_base_clear(bs);
 	bn_clear(&base);
 
 
diff --git a/pyecsca/codegen/templates/mult_fixed_w.c b/pyecsca/codegen/templates/mult_fixed_w.c
index b0a4bb0..6a079b3 100644
--- a/pyecsca/codegen/templates/mult_fixed_w.c
+++ b/pyecsca/codegen/templates/mult_fixed_w.c
@@ -20,18 +20,22 @@ void scalar_mult_by_m_base(point_t *point, curve_t *curve) {
 
 static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *out) {
 	point_t *q = point_copy(curve->neutral);
-    point_t *points[{{ scalarmult.m }}];
+    point_t *points[{{ scalarmult.m - 1 }}];
 
     point_t *current = point_copy(point);
     point_t *dbl = point_new();
     point_dbl(current, curve, dbl);
     points[0] = point_copy(current);
-    points[1] = point_copy(dbl);
+    {% if scalarmult.m > 2 %}
+        points[1] = point_copy(dbl);
+    {% endif %}
     point_set(dbl, current);
-    for (long i = 2; i < {{ scalarmult.m }}; i++) {
-        point_add(current, point, curve, current);
-        points[i] = point_copy(current);
-    }
+    {% if scalarmult.m > 3 %}
+        for (long i = 2; i < {{ scalarmult.m - 1 }}; i++) {
+            point_add(current, point, curve, current);
+            points[i] = point_copy(current);
+        }
+    {% endif %}
     point_free(current);
     point_free(dbl);
 
@@ -49,14 +53,13 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 			point_accumulate(q, points[val-1], curve, q);
         }
 	}
-	free(bs->data);
-	free(bs);
+	bn_small_base_clear(bs);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(q, curve, q);
     {%- endif %}
     point_set(q, out);
-    for (long i = 0; i < {{ scalarmult.m }}; i++) {
+    for (long i = 0; i < {{ scalarmult.m - 1 }}; i++) {
         point_free(points[i]);
     }
 	point_free(q);
diff --git a/pyecsca/codegen/templates/mult_rtl.c b/pyecsca/codegen/templates/mult_rtl.c
index 71949b4..119ee7e 100644
--- a/pyecsca/codegen/templates/mult_rtl.c
+++ b/pyecsca/codegen/templates/mult_rtl.c
@@ -5,6 +5,12 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
 	point_t *q = point_copy(point);
 	point_t *r = point_copy(curve->neutral);
 
+    {% if scalarmult.complete %}
+	    size_t bits = bn_bit_length(&curve->n);
+	{% else %}
+        size_t bits = bn_bit_length(scalar);
+    {% endif %}
+
 	{%- if scalarmult.always %}
 		point_t *dummy = point_new();
 	{%- endif %}
@@ -12,7 +18,7 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
 	bn_init(&copy);
 	bn_copy(scalar, &copy);
 
-    while (!bn_is_0(&copy)) {
+    for (int i = 0; i < bits; i++) {
         if (bn_get_bit(&copy, 0) == 1) {
             point_accumulate(r, q, curve, r);
         } else {
diff --git a/pyecsca/codegen/templates/mult_simple_ldr.c b/pyecsca/codegen/templates/mult_simple_ldr.c
index ceb257a..33bfcd9 100644
--- a/pyecsca/codegen/templates/mult_simple_ldr.c
+++ b/pyecsca/codegen/templates/mult_simple_ldr.c
@@ -11,7 +11,7 @@ void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, point_t *ou
 	{%- endif %}
 
 	for (int i = nbits; i >= 0; i--) {
-		if (bn_get_bit(scalar, i) == 1) {
+		if (bn_get_bit(scalar, i) == 0) {
 			point_add(p0, p1, curve, p1);
 			point_dbl(p0, curve, p0);
 		} else {
diff --git a/pyecsca/codegen/templates/mult_sliding_w.c b/pyecsca/codegen/templates/mult_sliding_w.c
index 1e80a84..347c313 100644
--- a/pyecsca/codegen/templates/mult_sliding_w.c
+++ b/pyecsca/codegen/templates/mult_sliding_w.c
@@ -34,8 +34,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
     {%- endif %}
     point_set(q, out);
 
-    free(ws->data);
-	free(ws);
+    bn_wsliding_clear(ws);
     for (long i = 0; i < {{ 2 ** (scalarmult.width - 1) }}; i++) {
         point_free(points[i]);
     }
diff --git a/pyecsca/codegen/templates/mult_wnaf.c b/pyecsca/codegen/templates/mult_wnaf.c
index 3c5f2b2..569e78b 100644
--- a/pyecsca/codegen/templates/mult_wnaf.c
+++ b/pyecsca/codegen/templates/mult_wnaf.c
@@ -26,7 +26,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 
 	wnaf_t *naf = bn_wnaf(scalar, {{ scalarmult.width }});
 
-	for (long i = naf->length - 1; i >= 0; i--) {
+	for (long i = 0; i < naf->length; i++) {
 		point_dbl(q, curve, q);
 		int8_t val = naf->data[i];
 		if (val > 0) {
@@ -40,8 +40,7 @@ static void scalar_mult_inner(bn_t *scalar, point_t *point, curve_t *curve, poin
 		    {%- endif %}
 		}
 	}
-	free(naf->data);
-	free(naf);
+	bn_naf_clear(naf);
 
     {%- if "scl" in scalarmult.formulas %}
     	point_scl(q, curve, q);