mul

2 files changed, 22 insertions, 1 deletions

diff --git a/src/fz_div.c b/src/fz_div.c
index d2cc999..24390d4 100644
--- a/src/fz_div.c
+++ b/src/fz_div.c
@@ -12,10 +12,11 @@ void fz_idiv(word_t *a,word_t *b,word_t *q_out,word_t *r_out,size_t len){
   size_t  qr_len  = len*2;
   word_t *q       = qr;
   word_t *r       = qr+len;
+  size_t  bitness = fz_bitness(len);
 
   fz_copy(a,q,len);
   fz_clear(r,len);
-  for(size_t x = 0;x < len;x++){
+  for(size_t x = 0;x < bitness;x++){
     wbool_t c;
     fz_shl(qr,qr,qr_len,1);
     c = fz_sub(r,b,r,len);
diff --git a/src/fz_mul.c b/src/fz_mul.c
index a821035..d0d6434 100644
--- a/src/fz_mul.c
+++ b/src/fz_mul.c
@@ -1,5 +1,25 @@
 #include <okeffa/fz_arith.h>
+#include <okeffa/fz_basic.h>
+#include <okeffa/fz_shift.h>
+#include <okeffa/fz_bitop.h>
+#include <okeffa/fz_pred.h>
+#include <okeffa/fz.h>
+#include <okeffa/w_op.h>
 
 void fz_mul_egypt(word_t *a,word_t *b,word_t *o_lo,word_t *o_hi,size_t len){
+  assert(len <= FZ_MAXLEN);
+  word_t  xy[FZ_MAXLEN*2];
+  word_t  xs[FZ_MAXLEN*2];
+  word_t  ys[FZ_MAXLEN];
+  size_t  len2  = len*2;
+  size_t  bitness = fz_bitness(len);
+
+  for(size_t x = 0;x < bitness;x++){
+    fz_add_gated(xy,xs,xy,len2,fz_odd(ys));
+    fz_shl(xs,xs,len2,1);
+    fz_shr(ys,ys,len,1);
+  }
+  fz_copy(xy,    o_lo,len);
+  fz_copy(xy+len,o_hi,len);
 }