monotone

monotone Mtn Source Tree

Root/botan/mp_sqr.cpp

1/*************************************************
2* Karatsuba Squaring Source File *
3* (C) 1999-2007 The Botan Project *
4*************************************************/
5
6#include <botan/mp_core.h>
7#include <botan/mem_ops.h>
8
9namespace Botan {
10
11namespace {
12
13/*************************************************
14* Simple O(N^2) Squaring *
15*************************************************/
16void bigint_simple_sqr(word z[], const word x[], u32bit x_size)
17 {
18 clear_mem(z, 2*x_size);
19
20 for(u32bit j = 0; j != x_size; ++j)
21 z[j+x_size] = bigint_mul_add_words(z + j, x, x_size, x[j]);
22 }
23
24/*************************************************
25* Karatsuba Squaring Operation *
26*************************************************/
27void karatsuba_sqr(word z[], const word x[], u32bit N, word workspace[])
28 {
29 const u32bit KARATSUBA_SQR_LOWER_SIZE = BOTAN_KARAT_SQR_THRESHOLD;
30
31 if(N == 6)
32 bigint_comba_sqr6(z, x);
33 else if(N == 8)
34 bigint_comba_sqr8(z, x);
35 else if(N < KARATSUBA_SQR_LOWER_SIZE || N % 2)
36 bigint_simple_sqr(z, x, N);
37 else
38 {
39 const u32bit N2 = N / 2;
40
41 const word* x0 = x;
42 const word* x1 = x + N2;
43 word* z0 = z;
44 word* z1 = z + N;
45
46 const s32bit cmp = bigint_cmp(x0, N2, x1, N2);
47
48 clear_mem(workspace, 2*N);
49
50 if(cmp)
51 {
52 if(cmp > 0)
53 bigint_sub3(z0, x0, N2, x1, N2);
54 else
55 bigint_sub3(z0, x1, N2, x0, N2);
56
57 karatsuba_sqr(workspace, z0, N2, workspace+N);
58 }
59
60 karatsuba_sqr(z0, x0, N2, workspace+N);
61 karatsuba_sqr(z1, x1, N2, workspace+N);
62
63 word carry = bigint_add3_nc(workspace+N, z0, N, z1, N);
64 carry += bigint_add2_nc(z + N2, N, workspace + N, N);
65 bigint_add2_nc(z + N + N2, N2, &carry, 1);
66
67 if(cmp == 0)
68 bigint_add2(z + N2, 2*N-N2, workspace, N);
69 else
70 bigint_sub2(z + N2, 2*N-N2, workspace, N);
71 }
72 }
73
74/*************************************************
75* Pick a good size for the Karatsuba squaring *
76*************************************************/
77u32bit karatsuba_size(u32bit z_size, u32bit x_size, u32bit x_sw)
78 {
79 if(x_sw == x_size)
80 {
81 if(x_sw % 2)
82 return 0;
83 return x_sw;
84 }
85
86 for(u32bit j = x_sw; j <= x_size; ++j)
87 {
88 if(j % 2)
89 continue;
90
91 if(2*j > z_size)
92 return 0;
93
94 if(j % 4 == 2 && (j+2) <= x_size && 2*(j+2) <= z_size)
95 return j+2;
96 return j;
97 }
98
99 return 0;
100 }
101
102/*************************************************
103* Handle small operand squarings *
104*************************************************/
105void handle_small_sqr(word z[], u32bit z_size,
106 const word x[], u32bit x_size, u32bit x_sw)
107 {
108 if(x_sw == 1)
109 bigint_linmul3(z, x, x_sw, x[0]);
110 else if(x_sw <= 4 && x_size >= 4 && z_size >= 8)
111 bigint_comba_sqr4(z, x);
112 else if(x_sw <= 6 && x_size >= 6 && z_size >= 12)
113 bigint_comba_sqr6(z, x);
114 else if(x_sw <= 8 && x_size >= 8 && z_size >= 16)
115 bigint_comba_sqr8(z, x);
116 else
117 bigint_simple_sqr(z, x, x_sw);
118 }
119
120}
121
122/*************************************************
123* Squaring Algorithm Dispatcher *
124*************************************************/
125void bigint_sqr(word z[], u32bit z_size, word workspace[],
126 const word x[], u32bit x_size, u32bit x_sw)
127 {
128 if(x_size <= 8 || x_sw <= 8)
129 {
130 handle_small_sqr(z, z_size, x, x_size, x_sw);
131 return;
132 }
133
134 const u32bit N = karatsuba_size(z_size, x_size, x_sw);
135
136 if(N)
137 {
138 clear_mem(workspace, 2*N);
139 karatsuba_sqr(z, x, N, workspace);
140 }
141 else
142 bigint_simple_sqr(z, x, x_sw);
143 }
144
145}

Archive Download this file

Branches

Tags

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