← Back to branch summary

~ubuntu-branches/ubuntu/vivid/samba/vivid

« back to all changes in this revision

Viewing changes to source4/heimdal/lib/hcrypto/libtommath/bn_mp_toom_sqr.c

  • Committer: Package Import Robot
  • Author(s): Chuck Short
  • Date: 2011-12-21 13:18:04 UTC
  • mfrom: (0.39.21 sid)
  • Revision ID: package-import@ubuntu.com-20111221131804-xtlr39wx6njehxxr
Tags: 2:3.6.1-3ubuntu1
* Merge from Debian testing.  Remaining changes:
  + debian/patches/VERSION.patch:
    - set SAMBA_VERSION_SUFFIX to Ubuntu.
  + debian/patches/error-trans.fix-276472:
    - Add the translation of Unix Error code -ENOTSUP to NT Error Code
    - NT_STATUS_NOT_SUPPORTED to prevent the Permission denied error.
  + debian/smb.conf:
    - add "(Samba, Ubuntu)" to server string.
    - comment out the default [homes] share, and add a comment about
      "valid users = %S" to show users how to restrict access to
      \\server\username to only username.
    - Set 'usershare allow guests', so that usershare admins are 
      allowed to create public shares in addition to authenticated
      ones.
    - add map to guest = Bad user, maps bad username to guest access.
  + debian/samba-common.config:
    - Do not change priority to high if dhclient3 is installed.
    - Use priority medium instead of high for the workgroup question.
  + debian/control:
    - Don't build against or suggest ctdb.
    - Add dependency on samba-common-bin to samba.
  + Add ufw integration:
    - Created debian/samba.ufw.profile
    - debian/rules, debian/samba.dirs, debian/samba.files: install
      profile
    - debian/control: have samba suggest ufw
  + Add apport hook:
    - Created debian/source_samba.py.
    - debian/rules, debian/samba.dirs, debian/samba-common-bin.files: install
  + Switch to upstart:
    - Add debian/samba.{nmbd,smbd}.upstart.
  + debian/samba.logrotate, debian/samba-common.dhcp, debian/samba.if-up:
    - Make them upstart compatible
  + debian/samba.postinst: 
    - Avoid scary pdbedit warnings on first import.
  + debian/samba-common.postinst: Add more informative error message for
    the case where smb.conf was manually deleted
  + debian/patches/fix-debuglevel-name-conflict.patch: don't use 'debug_level'
    as a global variable name in an NSS module 
  + Dropped:
    - debian/patches/error-trans.fix-276472
    - debian/patches/fix-debuglevel-name-conflict.patch

Show diffs side-by-side

added added

removed removed

Lines of Context:
source4/heimdal/lib/hcrypto/libtommath/bn_mp_toom_sqr.c
 
1
#include <tommath.h>
 
2
#ifdef BN_MP_TOOM_SQR_C
 
3
/* LibTomMath, multiple-precision integer library -- Tom St Denis
 
4
 *
 
5
 * LibTomMath is a library that provides multiple-precision
 
6
 * integer arithmetic as well as number theoretic functionality.
 
7
 *
 
8
 * The library was designed directly after the MPI library by
 
9
 * Michael Fromberger but has been written from scratch with
 
10
 * additional optimizations in place.
 
11
 *
 
12
 * The library is free for all purposes without any express
 
13
 * guarantee it works.
 
14
 *
 
15
 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org
 
16
 */
 
17
 
 
18
/* squaring using Toom-Cook 3-way algorithm */
 
19
int
 
20
mp_toom_sqr(mp_int *a, mp_int *b)
 
21
{
 
22
    mp_int w0, w1, w2, w3, w4, tmp1, a0, a1, a2;
 
23
    int res, B;
 
24
 
 
25
    /* init temps */
 
26
    if ((res = mp_init_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL)) != MP_OKAY) {
 
27
       return res;
 
28
    }
 
29
 
 
30
    /* B */
 
31
    B = a->used / 3;
 
32
 
 
33
    /* a = a2 * B**2 + a1 * B + a0 */
 
34
    if ((res = mp_mod_2d(a, DIGIT_BIT * B, &a0)) != MP_OKAY) {
 
35
       goto ERR;
 
36
    }
 
37
 
 
38
    if ((res = mp_copy(a, &a1)) != MP_OKAY) {
 
39
       goto ERR;
 
40
    }
 
41
    mp_rshd(&a1, B);
 
42
    mp_mod_2d(&a1, DIGIT_BIT * B, &a1);
 
43
 
 
44
    if ((res = mp_copy(a, &a2)) != MP_OKAY) {
 
45
       goto ERR;
 
46
    }
 
47
    mp_rshd(&a2, B*2);
 
48
 
 
49
    /* w0 = a0*a0 */
 
50
    if ((res = mp_sqr(&a0, &w0)) != MP_OKAY) {
 
51
       goto ERR;
 
52
    }
 
53
 
 
54
    /* w4 = a2 * a2 */
 
55
    if ((res = mp_sqr(&a2, &w4)) != MP_OKAY) {
 
56
       goto ERR;
 
57
    }
 
58
 
 
59
    /* w1 = (a2 + 2(a1 + 2a0))**2 */
 
60
    if ((res = mp_mul_2(&a0, &tmp1)) != MP_OKAY) {
 
61
       goto ERR;
 
62
    }
 
63
    if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) {
 
64
       goto ERR;
 
65
    }
 
66
    if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) {
 
67
       goto ERR;
 
68
    }
 
69
    if ((res = mp_add(&tmp1, &a2, &tmp1)) != MP_OKAY) {
 
70
       goto ERR;
 
71
    }
 
72
 
 
73
    if ((res = mp_sqr(&tmp1, &w1)) != MP_OKAY) {
 
74
       goto ERR;
 
75
    }
 
76
 
 
77
    /* w3 = (a0 + 2(a1 + 2a2))**2 */
 
78
    if ((res = mp_mul_2(&a2, &tmp1)) != MP_OKAY) {
 
79
       goto ERR;
 
80
    }
 
81
    if ((res = mp_add(&tmp1, &a1, &tmp1)) != MP_OKAY) {
 
82
       goto ERR;
 
83
    }
 
84
    if ((res = mp_mul_2(&tmp1, &tmp1)) != MP_OKAY) {
 
85
       goto ERR;
 
86
    }
 
87
    if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) {
 
88
       goto ERR;
 
89
    }
 
90
 
 
91
    if ((res = mp_sqr(&tmp1, &w3)) != MP_OKAY) {
 
92
       goto ERR;
 
93
    }
 
94
 
 
95
 
 
96
    /* w2 = (a2 + a1 + a0)**2 */
 
97
    if ((res = mp_add(&a2, &a1, &tmp1)) != MP_OKAY) {
 
98
       goto ERR;
 
99
    }
 
100
    if ((res = mp_add(&tmp1, &a0, &tmp1)) != MP_OKAY) {
 
101
       goto ERR;
 
102
    }
 
103
    if ((res = mp_sqr(&tmp1, &w2)) != MP_OKAY) {
 
104
       goto ERR;
 
105
    }
 
106
 
 
107
    /* now solve the matrix
 
108
 
 
109
       0  0  0  0  1
 
110
       1  2  4  8  16
 
111
       1  1  1  1  1
 
112
       16 8  4  2  1
 
113
       1  0  0  0  0
 
114
 
 
115
       using 12 subtractions, 4 shifts, 2 small divisions and 1 small multiplication.
 
116
     */
 
117
 
 
118
     /* r1 - r4 */
 
119
     if ((res = mp_sub(&w1, &w4, &w1)) != MP_OKAY) {
 
120
        goto ERR;
 
121
     }
 
122
     /* r3 - r0 */
 
123
     if ((res = mp_sub(&w3, &w0, &w3)) != MP_OKAY) {
 
124
        goto ERR;
 
125
     }
 
126
     /* r1/2 */
 
127
     if ((res = mp_div_2(&w1, &w1)) != MP_OKAY) {
 
128
        goto ERR;
 
129
     }
 
130
     /* r3/2 */
 
131
     if ((res = mp_div_2(&w3, &w3)) != MP_OKAY) {
 
132
        goto ERR;
 
133
     }
 
134
     /* r2 - r0 - r4 */
 
135
     if ((res = mp_sub(&w2, &w0, &w2)) != MP_OKAY) {
 
136
        goto ERR;
 
137
     }
 
138
     if ((res = mp_sub(&w2, &w4, &w2)) != MP_OKAY) {
 
139
        goto ERR;
 
140
     }
 
141
     /* r1 - r2 */
 
142
     if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) {
 
143
        goto ERR;
 
144
     }
 
145
     /* r3 - r2 */
 
146
     if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) {
 
147
        goto ERR;
 
148
     }
 
149
     /* r1 - 8r0 */
 
150
     if ((res = mp_mul_2d(&w0, 3, &tmp1)) != MP_OKAY) {
 
151
        goto ERR;
 
152
     }
 
153
     if ((res = mp_sub(&w1, &tmp1, &w1)) != MP_OKAY) {
 
154
        goto ERR;
 
155
     }
 
156
     /* r3 - 8r4 */
 
157
     if ((res = mp_mul_2d(&w4, 3, &tmp1)) != MP_OKAY) {
 
158
        goto ERR;
 
159
     }
 
160
     if ((res = mp_sub(&w3, &tmp1, &w3)) != MP_OKAY) {
 
161
        goto ERR;
 
162
     }
 
163
     /* 3r2 - r1 - r3 */
 
164
     if ((res = mp_mul_d(&w2, 3, &w2)) != MP_OKAY) {
 
165
        goto ERR;
 
166
     }
 
167
     if ((res = mp_sub(&w2, &w1, &w2)) != MP_OKAY) {
 
168
        goto ERR;
 
169
     }
 
170
     if ((res = mp_sub(&w2, &w3, &w2)) != MP_OKAY) {
 
171
        goto ERR;
 
172
     }
 
173
     /* r1 - r2 */
 
174
     if ((res = mp_sub(&w1, &w2, &w1)) != MP_OKAY) {
 
175
        goto ERR;
 
176
     }
 
177
     /* r3 - r2 */
 
178
     if ((res = mp_sub(&w3, &w2, &w3)) != MP_OKAY) {
 
179
        goto ERR;
 
180
     }
 
181
     /* r1/3 */
 
182
     if ((res = mp_div_3(&w1, &w1, NULL)) != MP_OKAY) {
 
183
        goto ERR;
 
184
     }
 
185
     /* r3/3 */
 
186
     if ((res = mp_div_3(&w3, &w3, NULL)) != MP_OKAY) {
 
187
        goto ERR;
 
188
     }
 
189
 
 
190
     /* at this point shift W[n] by B*n */
 
191
     if ((res = mp_lshd(&w1, 1*B)) != MP_OKAY) {
 
192
        goto ERR;
 
193
     }
 
194
     if ((res = mp_lshd(&w2, 2*B)) != MP_OKAY) {
 
195
        goto ERR;
 
196
     }
 
197
     if ((res = mp_lshd(&w3, 3*B)) != MP_OKAY) {
 
198
        goto ERR;
 
199
     }
 
200
     if ((res = mp_lshd(&w4, 4*B)) != MP_OKAY) {
 
201
        goto ERR;
 
202
     }
 
203
 
 
204
     if ((res = mp_add(&w0, &w1, b)) != MP_OKAY) {
 
205
        goto ERR;
 
206
     }
 
207
     if ((res = mp_add(&w2, &w3, &tmp1)) != MP_OKAY) {
 
208
        goto ERR;
 
209
     }
 
210
     if ((res = mp_add(&w4, &tmp1, &tmp1)) != MP_OKAY) {
 
211
        goto ERR;
 
212
     }
 
213
     if ((res = mp_add(&tmp1, b, b)) != MP_OKAY) {
 
214
        goto ERR;
 
215
     }
 
216
 
 
217
ERR:
 
218
     mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL);
 
219
     return res;
 
220
}
 
221
 
 
222
#endif
 
223
 
 
224
/* $Source: /cvs/libtom/libtommath/bn_mp_toom_sqr.c,v $ */
 
225
/* $Revision: 1.4 $ */
 
226
/* $Date: 2006/12/28 01:25:13 $ */