bn_asm.c 27 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039
  1. /*
  2. * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include <assert.h>
  10. #include <openssl/crypto.h>
  11. #include "internal/cryptlib.h"
  12. #include "bn_lcl.h"
  13. #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
  14. BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
  15. BN_ULONG w)
  16. {
  17. BN_ULONG c1 = 0;
  18. assert(num >= 0);
  19. if (num <= 0)
  20. return c1;
  21. # ifndef OPENSSL_SMALL_FOOTPRINT
  22. while (num & ~3) {
  23. mul_add(rp[0], ap[0], w, c1);
  24. mul_add(rp[1], ap[1], w, c1);
  25. mul_add(rp[2], ap[2], w, c1);
  26. mul_add(rp[3], ap[3], w, c1);
  27. ap += 4;
  28. rp += 4;
  29. num -= 4;
  30. }
  31. # endif
  32. while (num) {
  33. mul_add(rp[0], ap[0], w, c1);
  34. ap++;
  35. rp++;
  36. num--;
  37. }
  38. return c1;
  39. }
  40. BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
  41. {
  42. BN_ULONG c1 = 0;
  43. assert(num >= 0);
  44. if (num <= 0)
  45. return c1;
  46. # ifndef OPENSSL_SMALL_FOOTPRINT
  47. while (num & ~3) {
  48. mul(rp[0], ap[0], w, c1);
  49. mul(rp[1], ap[1], w, c1);
  50. mul(rp[2], ap[2], w, c1);
  51. mul(rp[3], ap[3], w, c1);
  52. ap += 4;
  53. rp += 4;
  54. num -= 4;
  55. }
  56. # endif
  57. while (num) {
  58. mul(rp[0], ap[0], w, c1);
  59. ap++;
  60. rp++;
  61. num--;
  62. }
  63. return c1;
  64. }
  65. void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
  66. {
  67. assert(n >= 0);
  68. if (n <= 0)
  69. return;
  70. # ifndef OPENSSL_SMALL_FOOTPRINT
  71. while (n & ~3) {
  72. sqr(r[0], r[1], a[0]);
  73. sqr(r[2], r[3], a[1]);
  74. sqr(r[4], r[5], a[2]);
  75. sqr(r[6], r[7], a[3]);
  76. a += 4;
  77. r += 8;
  78. n -= 4;
  79. }
  80. # endif
  81. while (n) {
  82. sqr(r[0], r[1], a[0]);
  83. a++;
  84. r += 2;
  85. n--;
  86. }
  87. }
  88. #else /* !(defined(BN_LLONG) ||
  89. * defined(BN_UMULT_HIGH)) */
  90. BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num,
  91. BN_ULONG w)
  92. {
  93. BN_ULONG c = 0;
  94. BN_ULONG bl, bh;
  95. assert(num >= 0);
  96. if (num <= 0)
  97. return (BN_ULONG)0;
  98. bl = LBITS(w);
  99. bh = HBITS(w);
  100. # ifndef OPENSSL_SMALL_FOOTPRINT
  101. while (num & ~3) {
  102. mul_add(rp[0], ap[0], bl, bh, c);
  103. mul_add(rp[1], ap[1], bl, bh, c);
  104. mul_add(rp[2], ap[2], bl, bh, c);
  105. mul_add(rp[3], ap[3], bl, bh, c);
  106. ap += 4;
  107. rp += 4;
  108. num -= 4;
  109. }
  110. # endif
  111. while (num) {
  112. mul_add(rp[0], ap[0], bl, bh, c);
  113. ap++;
  114. rp++;
  115. num--;
  116. }
  117. return c;
  118. }
  119. BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
  120. {
  121. BN_ULONG carry = 0;
  122. BN_ULONG bl, bh;
  123. assert(num >= 0);
  124. if (num <= 0)
  125. return (BN_ULONG)0;
  126. bl = LBITS(w);
  127. bh = HBITS(w);
  128. # ifndef OPENSSL_SMALL_FOOTPRINT
  129. while (num & ~3) {
  130. mul(rp[0], ap[0], bl, bh, carry);
  131. mul(rp[1], ap[1], bl, bh, carry);
  132. mul(rp[2], ap[2], bl, bh, carry);
  133. mul(rp[3], ap[3], bl, bh, carry);
  134. ap += 4;
  135. rp += 4;
  136. num -= 4;
  137. }
  138. # endif
  139. while (num) {
  140. mul(rp[0], ap[0], bl, bh, carry);
  141. ap++;
  142. rp++;
  143. num--;
  144. }
  145. return carry;
  146. }
  147. void bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
  148. {
  149. assert(n >= 0);
  150. if (n <= 0)
  151. return;
  152. # ifndef OPENSSL_SMALL_FOOTPRINT
  153. while (n & ~3) {
  154. sqr64(r[0], r[1], a[0]);
  155. sqr64(r[2], r[3], a[1]);
  156. sqr64(r[4], r[5], a[2]);
  157. sqr64(r[6], r[7], a[3]);
  158. a += 4;
  159. r += 8;
  160. n -= 4;
  161. }
  162. # endif
  163. while (n) {
  164. sqr64(r[0], r[1], a[0]);
  165. a++;
  166. r += 2;
  167. n--;
  168. }
  169. }
  170. #endif /* !(defined(BN_LLONG) ||
  171. * defined(BN_UMULT_HIGH)) */
  172. #if defined(BN_LLONG) && defined(BN_DIV2W)
  173. BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
  174. {
  175. return ((BN_ULONG)(((((BN_ULLONG) h) << BN_BITS2) | l) / (BN_ULLONG) d));
  176. }
  177. #else
  178. /* Divide h,l by d and return the result. */
  179. /* I need to test this some more :-( */
  180. BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
  181. {
  182. BN_ULONG dh, dl, q, ret = 0, th, tl, t;
  183. int i, count = 2;
  184. if (d == 0)
  185. return BN_MASK2;
  186. i = BN_num_bits_word(d);
  187. assert((i == BN_BITS2) || (h <= (BN_ULONG)1 << i));
  188. i = BN_BITS2 - i;
  189. if (h >= d)
  190. h -= d;
  191. if (i) {
  192. d <<= i;
  193. h = (h << i) | (l >> (BN_BITS2 - i));
  194. l <<= i;
  195. }
  196. dh = (d & BN_MASK2h) >> BN_BITS4;
  197. dl = (d & BN_MASK2l);
  198. for (;;) {
  199. if ((h >> BN_BITS4) == dh)
  200. q = BN_MASK2l;
  201. else
  202. q = h / dh;
  203. th = q * dh;
  204. tl = dl * q;
  205. for (;;) {
  206. t = h - th;
  207. if ((t & BN_MASK2h) ||
  208. ((tl) <= ((t << BN_BITS4) | ((l & BN_MASK2h) >> BN_BITS4))))
  209. break;
  210. q--;
  211. th -= dh;
  212. tl -= dl;
  213. }
  214. t = (tl >> BN_BITS4);
  215. tl = (tl << BN_BITS4) & BN_MASK2h;
  216. th += t;
  217. if (l < tl)
  218. th++;
  219. l -= tl;
  220. if (h < th) {
  221. h += d;
  222. q--;
  223. }
  224. h -= th;
  225. if (--count == 0)
  226. break;
  227. ret = q << BN_BITS4;
  228. h = ((h << BN_BITS4) | (l >> BN_BITS4)) & BN_MASK2;
  229. l = (l & BN_MASK2l) << BN_BITS4;
  230. }
  231. ret |= q;
  232. return ret;
  233. }
  234. #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
  235. #ifdef BN_LLONG
  236. BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
  237. int n)
  238. {
  239. BN_ULLONG ll = 0;
  240. assert(n >= 0);
  241. if (n <= 0)
  242. return (BN_ULONG)0;
  243. # ifndef OPENSSL_SMALL_FOOTPRINT
  244. while (n & ~3) {
  245. ll += (BN_ULLONG) a[0] + b[0];
  246. r[0] = (BN_ULONG)ll & BN_MASK2;
  247. ll >>= BN_BITS2;
  248. ll += (BN_ULLONG) a[1] + b[1];
  249. r[1] = (BN_ULONG)ll & BN_MASK2;
  250. ll >>= BN_BITS2;
  251. ll += (BN_ULLONG) a[2] + b[2];
  252. r[2] = (BN_ULONG)ll & BN_MASK2;
  253. ll >>= BN_BITS2;
  254. ll += (BN_ULLONG) a[3] + b[3];
  255. r[3] = (BN_ULONG)ll & BN_MASK2;
  256. ll >>= BN_BITS2;
  257. a += 4;
  258. b += 4;
  259. r += 4;
  260. n -= 4;
  261. }
  262. # endif
  263. while (n) {
  264. ll += (BN_ULLONG) a[0] + b[0];
  265. r[0] = (BN_ULONG)ll & BN_MASK2;
  266. ll >>= BN_BITS2;
  267. a++;
  268. b++;
  269. r++;
  270. n--;
  271. }
  272. return (BN_ULONG)ll;
  273. }
  274. #else /* !BN_LLONG */
  275. BN_ULONG bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
  276. int n)
  277. {
  278. BN_ULONG c, l, t;
  279. assert(n >= 0);
  280. if (n <= 0)
  281. return (BN_ULONG)0;
  282. c = 0;
  283. # ifndef OPENSSL_SMALL_FOOTPRINT
  284. while (n & ~3) {
  285. t = a[0];
  286. t = (t + c) & BN_MASK2;
  287. c = (t < c);
  288. l = (t + b[0]) & BN_MASK2;
  289. c += (l < t);
  290. r[0] = l;
  291. t = a[1];
  292. t = (t + c) & BN_MASK2;
  293. c = (t < c);
  294. l = (t + b[1]) & BN_MASK2;
  295. c += (l < t);
  296. r[1] = l;
  297. t = a[2];
  298. t = (t + c) & BN_MASK2;
  299. c = (t < c);
  300. l = (t + b[2]) & BN_MASK2;
  301. c += (l < t);
  302. r[2] = l;
  303. t = a[3];
  304. t = (t + c) & BN_MASK2;
  305. c = (t < c);
  306. l = (t + b[3]) & BN_MASK2;
  307. c += (l < t);
  308. r[3] = l;
  309. a += 4;
  310. b += 4;
  311. r += 4;
  312. n -= 4;
  313. }
  314. # endif
  315. while (n) {
  316. t = a[0];
  317. t = (t + c) & BN_MASK2;
  318. c = (t < c);
  319. l = (t + b[0]) & BN_MASK2;
  320. c += (l < t);
  321. r[0] = l;
  322. a++;
  323. b++;
  324. r++;
  325. n--;
  326. }
  327. return (BN_ULONG)c;
  328. }
  329. #endif /* !BN_LLONG */
  330. BN_ULONG bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b,
  331. int n)
  332. {
  333. BN_ULONG t1, t2;
  334. int c = 0;
  335. assert(n >= 0);
  336. if (n <= 0)
  337. return (BN_ULONG)0;
  338. #ifndef OPENSSL_SMALL_FOOTPRINT
  339. while (n & ~3) {
  340. t1 = a[0];
  341. t2 = b[0];
  342. r[0] = (t1 - t2 - c) & BN_MASK2;
  343. if (t1 != t2)
  344. c = (t1 < t2);
  345. t1 = a[1];
  346. t2 = b[1];
  347. r[1] = (t1 - t2 - c) & BN_MASK2;
  348. if (t1 != t2)
  349. c = (t1 < t2);
  350. t1 = a[2];
  351. t2 = b[2];
  352. r[2] = (t1 - t2 - c) & BN_MASK2;
  353. if (t1 != t2)
  354. c = (t1 < t2);
  355. t1 = a[3];
  356. t2 = b[3];
  357. r[3] = (t1 - t2 - c) & BN_MASK2;
  358. if (t1 != t2)
  359. c = (t1 < t2);
  360. a += 4;
  361. b += 4;
  362. r += 4;
  363. n -= 4;
  364. }
  365. #endif
  366. while (n) {
  367. t1 = a[0];
  368. t2 = b[0];
  369. r[0] = (t1 - t2 - c) & BN_MASK2;
  370. if (t1 != t2)
  371. c = (t1 < t2);
  372. a++;
  373. b++;
  374. r++;
  375. n--;
  376. }
  377. return c;
  378. }
  379. #if defined(BN_MUL_COMBA) && !defined(OPENSSL_SMALL_FOOTPRINT)
  380. # undef bn_mul_comba8
  381. # undef bn_mul_comba4
  382. # undef bn_sqr_comba8
  383. # undef bn_sqr_comba4
  384. /* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
  385. /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
  386. /* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
  387. /*
  388. * sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number
  389. * c=(c2,c1,c0)
  390. */
  391. # ifdef BN_LLONG
  392. /*
  393. * Keep in mind that additions to multiplication result can not
  394. * overflow, because its high half cannot be all-ones.
  395. */
  396. # define mul_add_c(a,b,c0,c1,c2) do { \
  397. BN_ULONG hi; \
  398. BN_ULLONG t = (BN_ULLONG)(a)*(b); \
  399. t += c0; /* no carry */ \
  400. c0 = (BN_ULONG)Lw(t); \
  401. hi = (BN_ULONG)Hw(t); \
  402. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  403. } while(0)
  404. # define mul_add_c2(a,b,c0,c1,c2) do { \
  405. BN_ULONG hi; \
  406. BN_ULLONG t = (BN_ULLONG)(a)*(b); \
  407. BN_ULLONG tt = t+c0; /* no carry */ \
  408. c0 = (BN_ULONG)Lw(tt); \
  409. hi = (BN_ULONG)Hw(tt); \
  410. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  411. t += c0; /* no carry */ \
  412. c0 = (BN_ULONG)Lw(t); \
  413. hi = (BN_ULONG)Hw(t); \
  414. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  415. } while(0)
  416. # define sqr_add_c(a,i,c0,c1,c2) do { \
  417. BN_ULONG hi; \
  418. BN_ULLONG t = (BN_ULLONG)a[i]*a[i]; \
  419. t += c0; /* no carry */ \
  420. c0 = (BN_ULONG)Lw(t); \
  421. hi = (BN_ULONG)Hw(t); \
  422. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  423. } while(0)
  424. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  425. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  426. # elif defined(BN_UMULT_LOHI)
  427. /*
  428. * Keep in mind that additions to hi can not overflow, because
  429. * the high word of a multiplication result cannot be all-ones.
  430. */
  431. # define mul_add_c(a,b,c0,c1,c2) do { \
  432. BN_ULONG ta = (a), tb = (b); \
  433. BN_ULONG lo, hi; \
  434. BN_UMULT_LOHI(lo,hi,ta,tb); \
  435. c0 += lo; hi += (c0<lo)?1:0; \
  436. c1 += hi; c2 += (c1<hi)?1:0; \
  437. } while(0)
  438. # define mul_add_c2(a,b,c0,c1,c2) do { \
  439. BN_ULONG ta = (a), tb = (b); \
  440. BN_ULONG lo, hi, tt; \
  441. BN_UMULT_LOHI(lo,hi,ta,tb); \
  442. c0 += lo; tt = hi+((c0<lo)?1:0); \
  443. c1 += tt; c2 += (c1<tt)?1:0; \
  444. c0 += lo; hi += (c0<lo)?1:0; \
  445. c1 += hi; c2 += (c1<hi)?1:0; \
  446. } while(0)
  447. # define sqr_add_c(a,i,c0,c1,c2) do { \
  448. BN_ULONG ta = (a)[i]; \
  449. BN_ULONG lo, hi; \
  450. BN_UMULT_LOHI(lo,hi,ta,ta); \
  451. c0 += lo; hi += (c0<lo)?1:0; \
  452. c1 += hi; c2 += (c1<hi)?1:0; \
  453. } while(0)
  454. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  455. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  456. # elif defined(BN_UMULT_HIGH)
  457. /*
  458. * Keep in mind that additions to hi can not overflow, because
  459. * the high word of a multiplication result cannot be all-ones.
  460. */
  461. # define mul_add_c(a,b,c0,c1,c2) do { \
  462. BN_ULONG ta = (a), tb = (b); \
  463. BN_ULONG lo = ta * tb; \
  464. BN_ULONG hi = BN_UMULT_HIGH(ta,tb); \
  465. c0 += lo; hi += (c0<lo)?1:0; \
  466. c1 += hi; c2 += (c1<hi)?1:0; \
  467. } while(0)
  468. # define mul_add_c2(a,b,c0,c1,c2) do { \
  469. BN_ULONG ta = (a), tb = (b), tt; \
  470. BN_ULONG lo = ta * tb; \
  471. BN_ULONG hi = BN_UMULT_HIGH(ta,tb); \
  472. c0 += lo; tt = hi + ((c0<lo)?1:0); \
  473. c1 += tt; c2 += (c1<tt)?1:0; \
  474. c0 += lo; hi += (c0<lo)?1:0; \
  475. c1 += hi; c2 += (c1<hi)?1:0; \
  476. } while(0)
  477. # define sqr_add_c(a,i,c0,c1,c2) do { \
  478. BN_ULONG ta = (a)[i]; \
  479. BN_ULONG lo = ta * ta; \
  480. BN_ULONG hi = BN_UMULT_HIGH(ta,ta); \
  481. c0 += lo; hi += (c0<lo)?1:0; \
  482. c1 += hi; c2 += (c1<hi)?1:0; \
  483. } while(0)
  484. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  485. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  486. # else /* !BN_LLONG */
  487. /*
  488. * Keep in mind that additions to hi can not overflow, because
  489. * the high word of a multiplication result cannot be all-ones.
  490. */
  491. # define mul_add_c(a,b,c0,c1,c2) do { \
  492. BN_ULONG lo = LBITS(a), hi = HBITS(a); \
  493. BN_ULONG bl = LBITS(b), bh = HBITS(b); \
  494. mul64(lo,hi,bl,bh); \
  495. c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
  496. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  497. } while(0)
  498. # define mul_add_c2(a,b,c0,c1,c2) do { \
  499. BN_ULONG tt; \
  500. BN_ULONG lo = LBITS(a), hi = HBITS(a); \
  501. BN_ULONG bl = LBITS(b), bh = HBITS(b); \
  502. mul64(lo,hi,bl,bh); \
  503. tt = hi; \
  504. c0 = (c0+lo)&BN_MASK2; if (c0<lo) tt++; \
  505. c1 = (c1+tt)&BN_MASK2; if (c1<tt) c2++; \
  506. c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
  507. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  508. } while(0)
  509. # define sqr_add_c(a,i,c0,c1,c2) do { \
  510. BN_ULONG lo, hi; \
  511. sqr64(lo,hi,(a)[i]); \
  512. c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
  513. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  514. } while(0)
  515. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  516. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  517. # endif /* !BN_LLONG */
  518. void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  519. {
  520. BN_ULONG c1, c2, c3;
  521. c1 = 0;
  522. c2 = 0;
  523. c3 = 0;
  524. mul_add_c(a[0], b[0], c1, c2, c3);
  525. r[0] = c1;
  526. c1 = 0;
  527. mul_add_c(a[0], b[1], c2, c3, c1);
  528. mul_add_c(a[1], b[0], c2, c3, c1);
  529. r[1] = c2;
  530. c2 = 0;
  531. mul_add_c(a[2], b[0], c3, c1, c2);
  532. mul_add_c(a[1], b[1], c3, c1, c2);
  533. mul_add_c(a[0], b[2], c3, c1, c2);
  534. r[2] = c3;
  535. c3 = 0;
  536. mul_add_c(a[0], b[3], c1, c2, c3);
  537. mul_add_c(a[1], b[2], c1, c2, c3);
  538. mul_add_c(a[2], b[1], c1, c2, c3);
  539. mul_add_c(a[3], b[0], c1, c2, c3);
  540. r[3] = c1;
  541. c1 = 0;
  542. mul_add_c(a[4], b[0], c2, c3, c1);
  543. mul_add_c(a[3], b[1], c2, c3, c1);
  544. mul_add_c(a[2], b[2], c2, c3, c1);
  545. mul_add_c(a[1], b[3], c2, c3, c1);
  546. mul_add_c(a[0], b[4], c2, c3, c1);
  547. r[4] = c2;
  548. c2 = 0;
  549. mul_add_c(a[0], b[5], c3, c1, c2);
  550. mul_add_c(a[1], b[4], c3, c1, c2);
  551. mul_add_c(a[2], b[3], c3, c1, c2);
  552. mul_add_c(a[3], b[2], c3, c1, c2);
  553. mul_add_c(a[4], b[1], c3, c1, c2);
  554. mul_add_c(a[5], b[0], c3, c1, c2);
  555. r[5] = c3;
  556. c3 = 0;
  557. mul_add_c(a[6], b[0], c1, c2, c3);
  558. mul_add_c(a[5], b[1], c1, c2, c3);
  559. mul_add_c(a[4], b[2], c1, c2, c3);
  560. mul_add_c(a[3], b[3], c1, c2, c3);
  561. mul_add_c(a[2], b[4], c1, c2, c3);
  562. mul_add_c(a[1], b[5], c1, c2, c3);
  563. mul_add_c(a[0], b[6], c1, c2, c3);
  564. r[6] = c1;
  565. c1 = 0;
  566. mul_add_c(a[0], b[7], c2, c3, c1);
  567. mul_add_c(a[1], b[6], c2, c3, c1);
  568. mul_add_c(a[2], b[5], c2, c3, c1);
  569. mul_add_c(a[3], b[4], c2, c3, c1);
  570. mul_add_c(a[4], b[3], c2, c3, c1);
  571. mul_add_c(a[5], b[2], c2, c3, c1);
  572. mul_add_c(a[6], b[1], c2, c3, c1);
  573. mul_add_c(a[7], b[0], c2, c3, c1);
  574. r[7] = c2;
  575. c2 = 0;
  576. mul_add_c(a[7], b[1], c3, c1, c2);
  577. mul_add_c(a[6], b[2], c3, c1, c2);
  578. mul_add_c(a[5], b[3], c3, c1, c2);
  579. mul_add_c(a[4], b[4], c3, c1, c2);
  580. mul_add_c(a[3], b[5], c3, c1, c2);
  581. mul_add_c(a[2], b[6], c3, c1, c2);
  582. mul_add_c(a[1], b[7], c3, c1, c2);
  583. r[8] = c3;
  584. c3 = 0;
  585. mul_add_c(a[2], b[7], c1, c2, c3);
  586. mul_add_c(a[3], b[6], c1, c2, c3);
  587. mul_add_c(a[4], b[5], c1, c2, c3);
  588. mul_add_c(a[5], b[4], c1, c2, c3);
  589. mul_add_c(a[6], b[3], c1, c2, c3);
  590. mul_add_c(a[7], b[2], c1, c2, c3);
  591. r[9] = c1;
  592. c1 = 0;
  593. mul_add_c(a[7], b[3], c2, c3, c1);
  594. mul_add_c(a[6], b[4], c2, c3, c1);
  595. mul_add_c(a[5], b[5], c2, c3, c1);
  596. mul_add_c(a[4], b[6], c2, c3, c1);
  597. mul_add_c(a[3], b[7], c2, c3, c1);
  598. r[10] = c2;
  599. c2 = 0;
  600. mul_add_c(a[4], b[7], c3, c1, c2);
  601. mul_add_c(a[5], b[6], c3, c1, c2);
  602. mul_add_c(a[6], b[5], c3, c1, c2);
  603. mul_add_c(a[7], b[4], c3, c1, c2);
  604. r[11] = c3;
  605. c3 = 0;
  606. mul_add_c(a[7], b[5], c1, c2, c3);
  607. mul_add_c(a[6], b[6], c1, c2, c3);
  608. mul_add_c(a[5], b[7], c1, c2, c3);
  609. r[12] = c1;
  610. c1 = 0;
  611. mul_add_c(a[6], b[7], c2, c3, c1);
  612. mul_add_c(a[7], b[6], c2, c3, c1);
  613. r[13] = c2;
  614. c2 = 0;
  615. mul_add_c(a[7], b[7], c3, c1, c2);
  616. r[14] = c3;
  617. r[15] = c1;
  618. }
  619. void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  620. {
  621. BN_ULONG c1, c2, c3;
  622. c1 = 0;
  623. c2 = 0;
  624. c3 = 0;
  625. mul_add_c(a[0], b[0], c1, c2, c3);
  626. r[0] = c1;
  627. c1 = 0;
  628. mul_add_c(a[0], b[1], c2, c3, c1);
  629. mul_add_c(a[1], b[0], c2, c3, c1);
  630. r[1] = c2;
  631. c2 = 0;
  632. mul_add_c(a[2], b[0], c3, c1, c2);
  633. mul_add_c(a[1], b[1], c3, c1, c2);
  634. mul_add_c(a[0], b[2], c3, c1, c2);
  635. r[2] = c3;
  636. c3 = 0;
  637. mul_add_c(a[0], b[3], c1, c2, c3);
  638. mul_add_c(a[1], b[2], c1, c2, c3);
  639. mul_add_c(a[2], b[1], c1, c2, c3);
  640. mul_add_c(a[3], b[0], c1, c2, c3);
  641. r[3] = c1;
  642. c1 = 0;
  643. mul_add_c(a[3], b[1], c2, c3, c1);
  644. mul_add_c(a[2], b[2], c2, c3, c1);
  645. mul_add_c(a[1], b[3], c2, c3, c1);
  646. r[4] = c2;
  647. c2 = 0;
  648. mul_add_c(a[2], b[3], c3, c1, c2);
  649. mul_add_c(a[3], b[2], c3, c1, c2);
  650. r[5] = c3;
  651. c3 = 0;
  652. mul_add_c(a[3], b[3], c1, c2, c3);
  653. r[6] = c1;
  654. r[7] = c2;
  655. }
  656. void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
  657. {
  658. BN_ULONG c1, c2, c3;
  659. c1 = 0;
  660. c2 = 0;
  661. c3 = 0;
  662. sqr_add_c(a, 0, c1, c2, c3);
  663. r[0] = c1;
  664. c1 = 0;
  665. sqr_add_c2(a, 1, 0, c2, c3, c1);
  666. r[1] = c2;
  667. c2 = 0;
  668. sqr_add_c(a, 1, c3, c1, c2);
  669. sqr_add_c2(a, 2, 0, c3, c1, c2);
  670. r[2] = c3;
  671. c3 = 0;
  672. sqr_add_c2(a, 3, 0, c1, c2, c3);
  673. sqr_add_c2(a, 2, 1, c1, c2, c3);
  674. r[3] = c1;
  675. c1 = 0;
  676. sqr_add_c(a, 2, c2, c3, c1);
  677. sqr_add_c2(a, 3, 1, c2, c3, c1);
  678. sqr_add_c2(a, 4, 0, c2, c3, c1);
  679. r[4] = c2;
  680. c2 = 0;
  681. sqr_add_c2(a, 5, 0, c3, c1, c2);
  682. sqr_add_c2(a, 4, 1, c3, c1, c2);
  683. sqr_add_c2(a, 3, 2, c3, c1, c2);
  684. r[5] = c3;
  685. c3 = 0;
  686. sqr_add_c(a, 3, c1, c2, c3);
  687. sqr_add_c2(a, 4, 2, c1, c2, c3);
  688. sqr_add_c2(a, 5, 1, c1, c2, c3);
  689. sqr_add_c2(a, 6, 0, c1, c2, c3);
  690. r[6] = c1;
  691. c1 = 0;
  692. sqr_add_c2(a, 7, 0, c2, c3, c1);
  693. sqr_add_c2(a, 6, 1, c2, c3, c1);
  694. sqr_add_c2(a, 5, 2, c2, c3, c1);
  695. sqr_add_c2(a, 4, 3, c2, c3, c1);
  696. r[7] = c2;
  697. c2 = 0;
  698. sqr_add_c(a, 4, c3, c1, c2);
  699. sqr_add_c2(a, 5, 3, c3, c1, c2);
  700. sqr_add_c2(a, 6, 2, c3, c1, c2);
  701. sqr_add_c2(a, 7, 1, c3, c1, c2);
  702. r[8] = c3;
  703. c3 = 0;
  704. sqr_add_c2(a, 7, 2, c1, c2, c3);
  705. sqr_add_c2(a, 6, 3, c1, c2, c3);
  706. sqr_add_c2(a, 5, 4, c1, c2, c3);
  707. r[9] = c1;
  708. c1 = 0;
  709. sqr_add_c(a, 5, c2, c3, c1);
  710. sqr_add_c2(a, 6, 4, c2, c3, c1);
  711. sqr_add_c2(a, 7, 3, c2, c3, c1);
  712. r[10] = c2;
  713. c2 = 0;
  714. sqr_add_c2(a, 7, 4, c3, c1, c2);
  715. sqr_add_c2(a, 6, 5, c3, c1, c2);
  716. r[11] = c3;
  717. c3 = 0;
  718. sqr_add_c(a, 6, c1, c2, c3);
  719. sqr_add_c2(a, 7, 5, c1, c2, c3);
  720. r[12] = c1;
  721. c1 = 0;
  722. sqr_add_c2(a, 7, 6, c2, c3, c1);
  723. r[13] = c2;
  724. c2 = 0;
  725. sqr_add_c(a, 7, c3, c1, c2);
  726. r[14] = c3;
  727. r[15] = c1;
  728. }
  729. void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
  730. {
  731. BN_ULONG c1, c2, c3;
  732. c1 = 0;
  733. c2 = 0;
  734. c3 = 0;
  735. sqr_add_c(a, 0, c1, c2, c3);
  736. r[0] = c1;
  737. c1 = 0;
  738. sqr_add_c2(a, 1, 0, c2, c3, c1);
  739. r[1] = c2;
  740. c2 = 0;
  741. sqr_add_c(a, 1, c3, c1, c2);
  742. sqr_add_c2(a, 2, 0, c3, c1, c2);
  743. r[2] = c3;
  744. c3 = 0;
  745. sqr_add_c2(a, 3, 0, c1, c2, c3);
  746. sqr_add_c2(a, 2, 1, c1, c2, c3);
  747. r[3] = c1;
  748. c1 = 0;
  749. sqr_add_c(a, 2, c2, c3, c1);
  750. sqr_add_c2(a, 3, 1, c2, c3, c1);
  751. r[4] = c2;
  752. c2 = 0;
  753. sqr_add_c2(a, 3, 2, c3, c1, c2);
  754. r[5] = c3;
  755. c3 = 0;
  756. sqr_add_c(a, 3, c1, c2, c3);
  757. r[6] = c1;
  758. r[7] = c2;
  759. }
  760. # ifdef OPENSSL_NO_ASM
  761. # ifdef OPENSSL_BN_ASM_MONT
  762. # include <alloca.h>
  763. /*
  764. * This is essentially reference implementation, which may or may not
  765. * result in performance improvement. E.g. on IA-32 this routine was
  766. * observed to give 40% faster rsa1024 private key operations and 10%
  767. * faster rsa4096 ones, while on AMD64 it improves rsa1024 sign only
  768. * by 10% and *worsens* rsa4096 sign by 15%. Once again, it's a
  769. * reference implementation, one to be used as starting point for
  770. * platform-specific assembler. Mentioned numbers apply to compiler
  771. * generated code compiled with and without -DOPENSSL_BN_ASM_MONT and
  772. * can vary not only from platform to platform, but even for compiler
  773. * versions. Assembler vs. assembler improvement coefficients can
  774. * [and are known to] differ and are to be documented elsewhere.
  775. */
  776. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  777. const BN_ULONG *np, const BN_ULONG *n0p, int num)
  778. {
  779. BN_ULONG c0, c1, ml, *tp, n0;
  780. # ifdef mul64
  781. BN_ULONG mh;
  782. # endif
  783. volatile BN_ULONG *vp;
  784. int i = 0, j;
  785. # if 0 /* template for platform-specific
  786. * implementation */
  787. if (ap == bp)
  788. return bn_sqr_mont(rp, ap, np, n0p, num);
  789. # endif
  790. vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
  791. n0 = *n0p;
  792. c0 = 0;
  793. ml = bp[0];
  794. # ifdef mul64
  795. mh = HBITS(ml);
  796. ml = LBITS(ml);
  797. for (j = 0; j < num; ++j)
  798. mul(tp[j], ap[j], ml, mh, c0);
  799. # else
  800. for (j = 0; j < num; ++j)
  801. mul(tp[j], ap[j], ml, c0);
  802. # endif
  803. tp[num] = c0;
  804. tp[num + 1] = 0;
  805. goto enter;
  806. for (i = 0; i < num; i++) {
  807. c0 = 0;
  808. ml = bp[i];
  809. # ifdef mul64
  810. mh = HBITS(ml);
  811. ml = LBITS(ml);
  812. for (j = 0; j < num; ++j)
  813. mul_add(tp[j], ap[j], ml, mh, c0);
  814. # else
  815. for (j = 0; j < num; ++j)
  816. mul_add(tp[j], ap[j], ml, c0);
  817. # endif
  818. c1 = (tp[num] + c0) & BN_MASK2;
  819. tp[num] = c1;
  820. tp[num + 1] = (c1 < c0 ? 1 : 0);
  821. enter:
  822. c1 = tp[0];
  823. ml = (c1 * n0) & BN_MASK2;
  824. c0 = 0;
  825. # ifdef mul64
  826. mh = HBITS(ml);
  827. ml = LBITS(ml);
  828. mul_add(c1, np[0], ml, mh, c0);
  829. # else
  830. mul_add(c1, ml, np[0], c0);
  831. # endif
  832. for (j = 1; j < num; j++) {
  833. c1 = tp[j];
  834. # ifdef mul64
  835. mul_add(c1, np[j], ml, mh, c0);
  836. # else
  837. mul_add(c1, ml, np[j], c0);
  838. # endif
  839. tp[j - 1] = c1 & BN_MASK2;
  840. }
  841. c1 = (tp[num] + c0) & BN_MASK2;
  842. tp[num - 1] = c1;
  843. tp[num] = tp[num + 1] + (c1 < c0 ? 1 : 0);
  844. }
  845. if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
  846. c0 = bn_sub_words(rp, tp, np, num);
  847. if (tp[num] != 0 || c0 == 0) {
  848. for (i = 0; i < num + 2; i++)
  849. vp[i] = 0;
  850. return 1;
  851. }
  852. }
  853. for (i = 0; i < num; i++)
  854. rp[i] = tp[i], vp[i] = 0;
  855. vp[num] = 0;
  856. vp[num + 1] = 0;
  857. return 1;
  858. }
  859. # else
  860. /*
  861. * Return value of 0 indicates that multiplication/convolution was not
  862. * performed to signal the caller to fall down to alternative/original
  863. * code-path.
  864. */
  865. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  866. const BN_ULONG *np, const BN_ULONG *n0, int num)
  867. {
  868. return 0;
  869. }
  870. # endif /* OPENSSL_BN_ASM_MONT */
  871. # endif
  872. #else /* !BN_MUL_COMBA */
  873. /* hmm... is it faster just to do a multiply? */
  874. # undef bn_sqr_comba4
  875. # undef bn_sqr_comba8
  876. void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
  877. {
  878. BN_ULONG t[8];
  879. bn_sqr_normal(r, a, 4, t);
  880. }
  881. void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
  882. {
  883. BN_ULONG t[16];
  884. bn_sqr_normal(r, a, 8, t);
  885. }
  886. void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  887. {
  888. r[4] = bn_mul_words(&(r[0]), a, 4, b[0]);
  889. r[5] = bn_mul_add_words(&(r[1]), a, 4, b[1]);
  890. r[6] = bn_mul_add_words(&(r[2]), a, 4, b[2]);
  891. r[7] = bn_mul_add_words(&(r[3]), a, 4, b[3]);
  892. }
  893. void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  894. {
  895. r[8] = bn_mul_words(&(r[0]), a, 8, b[0]);
  896. r[9] = bn_mul_add_words(&(r[1]), a, 8, b[1]);
  897. r[10] = bn_mul_add_words(&(r[2]), a, 8, b[2]);
  898. r[11] = bn_mul_add_words(&(r[3]), a, 8, b[3]);
  899. r[12] = bn_mul_add_words(&(r[4]), a, 8, b[4]);
  900. r[13] = bn_mul_add_words(&(r[5]), a, 8, b[5]);
  901. r[14] = bn_mul_add_words(&(r[6]), a, 8, b[6]);
  902. r[15] = bn_mul_add_words(&(r[7]), a, 8, b[7]);
  903. }
  904. # ifdef OPENSSL_NO_ASM
  905. # ifdef OPENSSL_BN_ASM_MONT
  906. # include <alloca.h>
  907. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  908. const BN_ULONG *np, const BN_ULONG *n0p, int num)
  909. {
  910. BN_ULONG c0, c1, *tp, n0 = *n0p;
  911. volatile BN_ULONG *vp;
  912. int i = 0, j;
  913. vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
  914. for (i = 0; i <= num; i++)
  915. tp[i] = 0;
  916. for (i = 0; i < num; i++) {
  917. c0 = bn_mul_add_words(tp, ap, num, bp[i]);
  918. c1 = (tp[num] + c0) & BN_MASK2;
  919. tp[num] = c1;
  920. tp[num + 1] = (c1 < c0 ? 1 : 0);
  921. c0 = bn_mul_add_words(tp, np, num, tp[0] * n0);
  922. c1 = (tp[num] + c0) & BN_MASK2;
  923. tp[num] = c1;
  924. tp[num + 1] += (c1 < c0 ? 1 : 0);
  925. for (j = 0; j <= num; j++)
  926. tp[j] = tp[j + 1];
  927. }
  928. if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
  929. c0 = bn_sub_words(rp, tp, np, num);
  930. if (tp[num] != 0 || c0 == 0) {
  931. for (i = 0; i < num + 2; i++)
  932. vp[i] = 0;
  933. return 1;
  934. }
  935. }
  936. for (i = 0; i < num; i++)
  937. rp[i] = tp[i], vp[i] = 0;
  938. vp[num] = 0;
  939. vp[num + 1] = 0;
  940. return 1;
  941. }
  942. # else
  943. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  944. const BN_ULONG *np, const BN_ULONG *n0, int num)
  945. {
  946. return 0;
  947. }
  948. # endif /* OPENSSL_BN_ASM_MONT */
  949. # endif
  950. #endif /* !BN_MUL_COMBA */