monotone

monotone Mtn Source Tree

Root/botan/mp_mul.cpp

1/*************************************************
2* MP Multiplication Source File *
3* (C) 1999-2005 The Botan Project *
4*************************************************/
5
6#include <botan/mp_core.h>
7
8namespace Botan {
9
10namespace {
11
12/*************************************************
13* Length Checking *
14*************************************************/
15bool use_op(u32bit x_sw, u32bit y_sw,
16 u32bit x_size, u32bit y_size, u32bit z_size,
17 u32bit limit, u32bit min = 0)
18 {
19 return (x_sw <= limit && y_sw <= limit &&
20 x_size >= limit && y_size >= limit && z_size >= 2*limit &&
21 (x_sw + y_sw) >= min);
22 }
23
24/*************************************************
25* Attempt a Karatsuba multiply *
26*************************************************/
27bool do_karat(word z[], u32bit z_size,
28 const word x[], u32bit x_size, u32bit x_sw,
29 const word y[], u32bit y_size, u32bit y_sw)
30 {
31 const u32bit KARAT_12_BOUND = 20;
32 const u32bit KARAT_16_BOUND = 24;
33 const u32bit KARAT_24_BOUND = 38;
34 const u32bit KARAT_32_BOUND = 46;
35 const u32bit KARAT_48_BOUND = 66;
36 const u32bit KARAT_64_BOUND = 80;
37 const u32bit KARAT_96_BOUND = 114;
38 const u32bit KARAT_128_BOUND = 136;
39
40 if(use_op(x_sw, y_sw, x_size, y_size, z_size, 12, KARAT_12_BOUND))
41 bigint_karat12(z, x, y);
42 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 16, KARAT_16_BOUND))
43 bigint_karat16(z, x, y);
44 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 24, KARAT_24_BOUND))
45 bigint_karat24(z, x, y);
46 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 32, KARAT_32_BOUND))
47 bigint_karat32(z, x, y);
48 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 48, KARAT_48_BOUND))
49 bigint_karat48(z, x, y);
50 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 64, KARAT_64_BOUND))
51 bigint_karat64(z, x, y);
52 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 96, KARAT_96_BOUND))
53 bigint_karat96(z, x, y);
54 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 128, KARAT_128_BOUND))
55 bigint_karat128(z, x, y);
56 else
57 return false;
58
59 return true;
60 }
61
62
63}
64
65/*************************************************
66* MP Multiplication Algorithm Dispatcher *
67*************************************************/
68void bigint_mul3(word z[], u32bit z_size,
69 const word x[], u32bit x_size, u32bit x_sw,
70 const word y[], u32bit y_size, u32bit y_sw)
71 {
72 if(x_sw == 1) bigint_linmul3(z, y, y_sw, x[0]);
73 else if(y_sw == 1) bigint_linmul3(z, x, x_sw, y[0]);
74
75 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 4))
76 bigint_comba4(z, x, y);
77 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 6))
78 bigint_comba6(z, x, y);
79 else if(use_op(x_sw, y_sw, x_size, y_size, z_size, 8))
80 bigint_comba8(z, x, y);
81 else if(!do_karat(z, z_size, x, x_size, x_sw, y, y_size, y_sw))
82 bigint_smul(z, x, x_sw, y, y_sw);
83 }
84
85}

Archive Download this file

Branches

Tags

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