monotone

monotone Mtn Source Tree

Root/botan/mp_fkmul.cpp

1/*************************************************
2* Fixed Karatsuba Multiplication Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/mp_core.h>
7#include <botan/mem_ops.h>
8#include <botan/parsing.h>
9#include <botan/exceptn.h>
10
11namespace Botan {
12
13/*************************************************
14* Karatsuba Multiplication Operation *
15*************************************************/
16#define KARATSUBA_CORE(N, INNER_MUL, z, x, y) \
17 { \
18 const u32bit N2 = N / 2; \
19 \
20 const word* x0 = x; \
21 const word* x1 = x + N2; \
22 const word* y0 = y; \
23 const word* y1 = y + N2; \
24 word* z0 = z; \
25 word* z1 = z + N; \
26 \
27 const s32bit cmp0 = bigint_cmp(x0, N2, x1, N2); \
28 const s32bit cmp1 = bigint_cmp(y1, N2, y0, N2); \
29 \
30 bool positive = (cmp0 == cmp1) || (cmp0 == 0) || (cmp1 == 0); \
31 \
32 word ws[N+N+1] = { 0 }; \
33 word* middle = ws + N; \
34 \
35 if(cmp0 && cmp1) \
36 { \
37 if(cmp0 > 0) \
38 bigint_sub3(middle, x0, N2, x1, N2); \
39 else \
40 bigint_sub3(middle, x1, N2, x0, N2); \
41 \
42 if(cmp1 > 0) \
43 bigint_sub3(z, y1, N2, y0, N2); \
44 else \
45 bigint_sub3(z, y0, N2, y1, N2); \
46 \
47 INNER_MUL(ws, middle, z); \
48 } \
49 \
50 INNER_MUL(z0, x0, y0); \
51 INNER_MUL(z1, x1, y1); \
52 \
53 bigint_add3(middle, z0, N, z1, N); \
54 \
55 if(positive) \
56 bigint_add2(middle, N+1, ws, N); \
57 else \
58 { \
59 const s32bit scmp = bigint_cmp(middle, N+1, ws, N); \
60 \
61 if(scmp < 0) \
62 throw Internal_Error("bigint_karat" + to_string(N) + \
63 ": scmp < 0"); \
64 \
65 if(scmp > 0) \
66 bigint_sub2(middle, N+1, ws, N); \
67 else \
68 clear_mem(middle, N+1); \
69 } \
70 bigint_add2(z + N2, 2*N-N2, middle, N+1); \
71 \
72 clear_mem(ws, 2*N+1); \
73 }
74
75/*************************************************
76* Karatsuba 16x16 Multiplication *
77*************************************************/
78void bigint_karat16(word z[32], const word x[16], const word y[16])
79 {
80 KARATSUBA_CORE(16, bigint_comba8, z, x, y);
81 }
82
83/*************************************************
84* Karatsuba 32x32 Multiplication *
85*************************************************/
86void bigint_karat32(word z[64], const word x[32], const word y[32])
87 {
88 KARATSUBA_CORE(32, bigint_karat16, z, x, y);
89 }
90
91/*************************************************
92* Karatsuba 64x64 Multiplication *
93*************************************************/
94void bigint_karat64(word z[128], const word x[64], const word y[64])
95 {
96 KARATSUBA_CORE(64, bigint_karat32, z, x, y);
97 }
98
99/*************************************************
100* Karatsuba 128x128 Multiplication *
101*************************************************/
102void bigint_karat128(word z[256], const word x[128], const word y[128])
103 {
104 KARATSUBA_CORE(128, bigint_karat64, z, x, y);
105 }
106
107/*************************************************
108* Karatsuba 12x12 Multiplication *
109*************************************************/
110void bigint_karat12(word z[24], const word x[12], const word y[12])
111 {
112 KARATSUBA_CORE(12, bigint_comba6, z, x, y);
113 }
114
115/*************************************************
116* Karatsuba 24x24 Multiplication *
117*************************************************/
118void bigint_karat24(word z[48], const word x[24], const word y[24])
119 {
120 KARATSUBA_CORE(24, bigint_karat12, z, x, y);
121 }
122
123/*************************************************
124* Karatsuba 48x48 Multiplication *
125*************************************************/
126void bigint_karat48(word z[96], const word x[48], const word y[48])
127 {
128 KARATSUBA_CORE(48, bigint_karat24, z, x, y);
129 }
130
131/*************************************************
132* Karatsuba 96x96 Multiplication *
133*************************************************/
134void bigint_karat96(word z[192], const word x[96], const word y[96])
135 {
136 KARATSUBA_CORE(96, bigint_karat48, z, x, y);
137 }
138
139}

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status