bn_asm.c 27 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032
  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_local.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. /* mul_add_c(a,b,c0,c1,c2) -- c+=a*b for three word number c=(c2,c1,c0) */
  381. /* mul_add_c2(a,b,c0,c1,c2) -- c+=2*a*b for three word number c=(c2,c1,c0) */
  382. /* sqr_add_c(a,i,c0,c1,c2) -- c+=a[i]^2 for three word number c=(c2,c1,c0) */
  383. /*
  384. * sqr_add_c2(a,i,c0,c1,c2) -- c+=2*a[i]*a[j] for three word number
  385. * c=(c2,c1,c0)
  386. */
  387. # ifdef BN_LLONG
  388. /*
  389. * Keep in mind that additions to multiplication result can not
  390. * overflow, because its high half cannot be all-ones.
  391. */
  392. # define mul_add_c(a,b,c0,c1,c2) do { \
  393. BN_ULONG hi; \
  394. BN_ULLONG t = (BN_ULLONG)(a)*(b); \
  395. t += c0; /* no carry */ \
  396. c0 = (BN_ULONG)Lw(t); \
  397. hi = (BN_ULONG)Hw(t); \
  398. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  399. } while(0)
  400. # define mul_add_c2(a,b,c0,c1,c2) do { \
  401. BN_ULONG hi; \
  402. BN_ULLONG t = (BN_ULLONG)(a)*(b); \
  403. BN_ULLONG tt = t+c0; /* no carry */ \
  404. c0 = (BN_ULONG)Lw(tt); \
  405. hi = (BN_ULONG)Hw(tt); \
  406. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  407. t += c0; /* no carry */ \
  408. c0 = (BN_ULONG)Lw(t); \
  409. hi = (BN_ULONG)Hw(t); \
  410. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  411. } while(0)
  412. # define sqr_add_c(a,i,c0,c1,c2) do { \
  413. BN_ULONG hi; \
  414. BN_ULLONG t = (BN_ULLONG)a[i]*a[i]; \
  415. t += c0; /* no carry */ \
  416. c0 = (BN_ULONG)Lw(t); \
  417. hi = (BN_ULONG)Hw(t); \
  418. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  419. } while(0)
  420. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  421. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  422. # elif defined(BN_UMULT_LOHI)
  423. /*
  424. * Keep in mind that additions to hi can not overflow, because
  425. * the high word of a multiplication result cannot be all-ones.
  426. */
  427. # define mul_add_c(a,b,c0,c1,c2) do { \
  428. BN_ULONG ta = (a), tb = (b); \
  429. BN_ULONG lo, hi; \
  430. BN_UMULT_LOHI(lo,hi,ta,tb); \
  431. c0 += lo; hi += (c0<lo)?1:0; \
  432. c1 += hi; c2 += (c1<hi)?1:0; \
  433. } while(0)
  434. # define mul_add_c2(a,b,c0,c1,c2) do { \
  435. BN_ULONG ta = (a), tb = (b); \
  436. BN_ULONG lo, hi, tt; \
  437. BN_UMULT_LOHI(lo,hi,ta,tb); \
  438. c0 += lo; tt = hi+((c0<lo)?1:0); \
  439. c1 += tt; c2 += (c1<tt)?1:0; \
  440. c0 += lo; hi += (c0<lo)?1:0; \
  441. c1 += hi; c2 += (c1<hi)?1:0; \
  442. } while(0)
  443. # define sqr_add_c(a,i,c0,c1,c2) do { \
  444. BN_ULONG ta = (a)[i]; \
  445. BN_ULONG lo, hi; \
  446. BN_UMULT_LOHI(lo,hi,ta,ta); \
  447. c0 += lo; hi += (c0<lo)?1:0; \
  448. c1 += hi; c2 += (c1<hi)?1:0; \
  449. } while(0)
  450. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  451. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  452. # elif defined(BN_UMULT_HIGH)
  453. /*
  454. * Keep in mind that additions to hi can not overflow, because
  455. * the high word of a multiplication result cannot be all-ones.
  456. */
  457. # define mul_add_c(a,b,c0,c1,c2) do { \
  458. BN_ULONG ta = (a), tb = (b); \
  459. BN_ULONG lo = ta * tb; \
  460. BN_ULONG hi = BN_UMULT_HIGH(ta,tb); \
  461. c0 += lo; hi += (c0<lo)?1:0; \
  462. c1 += hi; c2 += (c1<hi)?1:0; \
  463. } while(0)
  464. # define mul_add_c2(a,b,c0,c1,c2) do { \
  465. BN_ULONG ta = (a), tb = (b), tt; \
  466. BN_ULONG lo = ta * tb; \
  467. BN_ULONG hi = BN_UMULT_HIGH(ta,tb); \
  468. c0 += lo; tt = hi + ((c0<lo)?1:0); \
  469. c1 += tt; c2 += (c1<tt)?1:0; \
  470. c0 += lo; hi += (c0<lo)?1:0; \
  471. c1 += hi; c2 += (c1<hi)?1:0; \
  472. } while(0)
  473. # define sqr_add_c(a,i,c0,c1,c2) do { \
  474. BN_ULONG ta = (a)[i]; \
  475. BN_ULONG lo = ta * ta; \
  476. BN_ULONG hi = BN_UMULT_HIGH(ta,ta); \
  477. c0 += lo; hi += (c0<lo)?1:0; \
  478. c1 += hi; c2 += (c1<hi)?1:0; \
  479. } while(0)
  480. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  481. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  482. # else /* !BN_LLONG */
  483. /*
  484. * Keep in mind that additions to hi can not overflow, because
  485. * the high word of a multiplication result cannot be all-ones.
  486. */
  487. # define mul_add_c(a,b,c0,c1,c2) do { \
  488. BN_ULONG lo = LBITS(a), hi = HBITS(a); \
  489. BN_ULONG bl = LBITS(b), bh = HBITS(b); \
  490. mul64(lo,hi,bl,bh); \
  491. c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
  492. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  493. } while(0)
  494. # define mul_add_c2(a,b,c0,c1,c2) do { \
  495. BN_ULONG tt; \
  496. BN_ULONG lo = LBITS(a), hi = HBITS(a); \
  497. BN_ULONG bl = LBITS(b), bh = HBITS(b); \
  498. mul64(lo,hi,bl,bh); \
  499. tt = hi; \
  500. c0 = (c0+lo)&BN_MASK2; if (c0<lo) tt++; \
  501. c1 = (c1+tt)&BN_MASK2; if (c1<tt) c2++; \
  502. c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
  503. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  504. } while(0)
  505. # define sqr_add_c(a,i,c0,c1,c2) do { \
  506. BN_ULONG lo, hi; \
  507. sqr64(lo,hi,(a)[i]); \
  508. c0 = (c0+lo)&BN_MASK2; if (c0<lo) hi++; \
  509. c1 = (c1+hi)&BN_MASK2; if (c1<hi) c2++; \
  510. } while(0)
  511. # define sqr_add_c2(a,i,j,c0,c1,c2) \
  512. mul_add_c2((a)[i],(a)[j],c0,c1,c2)
  513. # endif /* !BN_LLONG */
  514. void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  515. {
  516. BN_ULONG c1, c2, c3;
  517. c1 = 0;
  518. c2 = 0;
  519. c3 = 0;
  520. mul_add_c(a[0], b[0], c1, c2, c3);
  521. r[0] = c1;
  522. c1 = 0;
  523. mul_add_c(a[0], b[1], c2, c3, c1);
  524. mul_add_c(a[1], b[0], c2, c3, c1);
  525. r[1] = c2;
  526. c2 = 0;
  527. mul_add_c(a[2], b[0], c3, c1, c2);
  528. mul_add_c(a[1], b[1], c3, c1, c2);
  529. mul_add_c(a[0], b[2], c3, c1, c2);
  530. r[2] = c3;
  531. c3 = 0;
  532. mul_add_c(a[0], b[3], c1, c2, c3);
  533. mul_add_c(a[1], b[2], c1, c2, c3);
  534. mul_add_c(a[2], b[1], c1, c2, c3);
  535. mul_add_c(a[3], b[0], c1, c2, c3);
  536. r[3] = c1;
  537. c1 = 0;
  538. mul_add_c(a[4], b[0], c2, c3, c1);
  539. mul_add_c(a[3], b[1], c2, c3, c1);
  540. mul_add_c(a[2], b[2], c2, c3, c1);
  541. mul_add_c(a[1], b[3], c2, c3, c1);
  542. mul_add_c(a[0], b[4], c2, c3, c1);
  543. r[4] = c2;
  544. c2 = 0;
  545. mul_add_c(a[0], b[5], c3, c1, c2);
  546. mul_add_c(a[1], b[4], c3, c1, c2);
  547. mul_add_c(a[2], b[3], c3, c1, c2);
  548. mul_add_c(a[3], b[2], c3, c1, c2);
  549. mul_add_c(a[4], b[1], c3, c1, c2);
  550. mul_add_c(a[5], b[0], c3, c1, c2);
  551. r[5] = c3;
  552. c3 = 0;
  553. mul_add_c(a[6], b[0], c1, c2, c3);
  554. mul_add_c(a[5], b[1], c1, c2, c3);
  555. mul_add_c(a[4], b[2], c1, c2, c3);
  556. mul_add_c(a[3], b[3], c1, c2, c3);
  557. mul_add_c(a[2], b[4], c1, c2, c3);
  558. mul_add_c(a[1], b[5], c1, c2, c3);
  559. mul_add_c(a[0], b[6], c1, c2, c3);
  560. r[6] = c1;
  561. c1 = 0;
  562. mul_add_c(a[0], b[7], c2, c3, c1);
  563. mul_add_c(a[1], b[6], c2, c3, c1);
  564. mul_add_c(a[2], b[5], c2, c3, c1);
  565. mul_add_c(a[3], b[4], c2, c3, c1);
  566. mul_add_c(a[4], b[3], c2, c3, c1);
  567. mul_add_c(a[5], b[2], c2, c3, c1);
  568. mul_add_c(a[6], b[1], c2, c3, c1);
  569. mul_add_c(a[7], b[0], c2, c3, c1);
  570. r[7] = c2;
  571. c2 = 0;
  572. mul_add_c(a[7], b[1], c3, c1, c2);
  573. mul_add_c(a[6], b[2], c3, c1, c2);
  574. mul_add_c(a[5], b[3], c3, c1, c2);
  575. mul_add_c(a[4], b[4], c3, c1, c2);
  576. mul_add_c(a[3], b[5], c3, c1, c2);
  577. mul_add_c(a[2], b[6], c3, c1, c2);
  578. mul_add_c(a[1], b[7], c3, c1, c2);
  579. r[8] = c3;
  580. c3 = 0;
  581. mul_add_c(a[2], b[7], c1, c2, c3);
  582. mul_add_c(a[3], b[6], c1, c2, c3);
  583. mul_add_c(a[4], b[5], c1, c2, c3);
  584. mul_add_c(a[5], b[4], c1, c2, c3);
  585. mul_add_c(a[6], b[3], c1, c2, c3);
  586. mul_add_c(a[7], b[2], c1, c2, c3);
  587. r[9] = c1;
  588. c1 = 0;
  589. mul_add_c(a[7], b[3], c2, c3, c1);
  590. mul_add_c(a[6], b[4], c2, c3, c1);
  591. mul_add_c(a[5], b[5], c2, c3, c1);
  592. mul_add_c(a[4], b[6], c2, c3, c1);
  593. mul_add_c(a[3], b[7], c2, c3, c1);
  594. r[10] = c2;
  595. c2 = 0;
  596. mul_add_c(a[4], b[7], c3, c1, c2);
  597. mul_add_c(a[5], b[6], c3, c1, c2);
  598. mul_add_c(a[6], b[5], c3, c1, c2);
  599. mul_add_c(a[7], b[4], c3, c1, c2);
  600. r[11] = c3;
  601. c3 = 0;
  602. mul_add_c(a[7], b[5], c1, c2, c3);
  603. mul_add_c(a[6], b[6], c1, c2, c3);
  604. mul_add_c(a[5], b[7], c1, c2, c3);
  605. r[12] = c1;
  606. c1 = 0;
  607. mul_add_c(a[6], b[7], c2, c3, c1);
  608. mul_add_c(a[7], b[6], c2, c3, c1);
  609. r[13] = c2;
  610. c2 = 0;
  611. mul_add_c(a[7], b[7], c3, c1, c2);
  612. r[14] = c3;
  613. r[15] = c1;
  614. }
  615. void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  616. {
  617. BN_ULONG c1, c2, c3;
  618. c1 = 0;
  619. c2 = 0;
  620. c3 = 0;
  621. mul_add_c(a[0], b[0], c1, c2, c3);
  622. r[0] = c1;
  623. c1 = 0;
  624. mul_add_c(a[0], b[1], c2, c3, c1);
  625. mul_add_c(a[1], b[0], c2, c3, c1);
  626. r[1] = c2;
  627. c2 = 0;
  628. mul_add_c(a[2], b[0], c3, c1, c2);
  629. mul_add_c(a[1], b[1], c3, c1, c2);
  630. mul_add_c(a[0], b[2], c3, c1, c2);
  631. r[2] = c3;
  632. c3 = 0;
  633. mul_add_c(a[0], b[3], c1, c2, c3);
  634. mul_add_c(a[1], b[2], c1, c2, c3);
  635. mul_add_c(a[2], b[1], c1, c2, c3);
  636. mul_add_c(a[3], b[0], c1, c2, c3);
  637. r[3] = c1;
  638. c1 = 0;
  639. mul_add_c(a[3], b[1], c2, c3, c1);
  640. mul_add_c(a[2], b[2], c2, c3, c1);
  641. mul_add_c(a[1], b[3], c2, c3, c1);
  642. r[4] = c2;
  643. c2 = 0;
  644. mul_add_c(a[2], b[3], c3, c1, c2);
  645. mul_add_c(a[3], b[2], c3, c1, c2);
  646. r[5] = c3;
  647. c3 = 0;
  648. mul_add_c(a[3], b[3], c1, c2, c3);
  649. r[6] = c1;
  650. r[7] = c2;
  651. }
  652. void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
  653. {
  654. BN_ULONG c1, c2, c3;
  655. c1 = 0;
  656. c2 = 0;
  657. c3 = 0;
  658. sqr_add_c(a, 0, c1, c2, c3);
  659. r[0] = c1;
  660. c1 = 0;
  661. sqr_add_c2(a, 1, 0, c2, c3, c1);
  662. r[1] = c2;
  663. c2 = 0;
  664. sqr_add_c(a, 1, c3, c1, c2);
  665. sqr_add_c2(a, 2, 0, c3, c1, c2);
  666. r[2] = c3;
  667. c3 = 0;
  668. sqr_add_c2(a, 3, 0, c1, c2, c3);
  669. sqr_add_c2(a, 2, 1, c1, c2, c3);
  670. r[3] = c1;
  671. c1 = 0;
  672. sqr_add_c(a, 2, c2, c3, c1);
  673. sqr_add_c2(a, 3, 1, c2, c3, c1);
  674. sqr_add_c2(a, 4, 0, c2, c3, c1);
  675. r[4] = c2;
  676. c2 = 0;
  677. sqr_add_c2(a, 5, 0, c3, c1, c2);
  678. sqr_add_c2(a, 4, 1, c3, c1, c2);
  679. sqr_add_c2(a, 3, 2, c3, c1, c2);
  680. r[5] = c3;
  681. c3 = 0;
  682. sqr_add_c(a, 3, c1, c2, c3);
  683. sqr_add_c2(a, 4, 2, c1, c2, c3);
  684. sqr_add_c2(a, 5, 1, c1, c2, c3);
  685. sqr_add_c2(a, 6, 0, c1, c2, c3);
  686. r[6] = c1;
  687. c1 = 0;
  688. sqr_add_c2(a, 7, 0, c2, c3, c1);
  689. sqr_add_c2(a, 6, 1, c2, c3, c1);
  690. sqr_add_c2(a, 5, 2, c2, c3, c1);
  691. sqr_add_c2(a, 4, 3, c2, c3, c1);
  692. r[7] = c2;
  693. c2 = 0;
  694. sqr_add_c(a, 4, c3, c1, c2);
  695. sqr_add_c2(a, 5, 3, c3, c1, c2);
  696. sqr_add_c2(a, 6, 2, c3, c1, c2);
  697. sqr_add_c2(a, 7, 1, c3, c1, c2);
  698. r[8] = c3;
  699. c3 = 0;
  700. sqr_add_c2(a, 7, 2, c1, c2, c3);
  701. sqr_add_c2(a, 6, 3, c1, c2, c3);
  702. sqr_add_c2(a, 5, 4, c1, c2, c3);
  703. r[9] = c1;
  704. c1 = 0;
  705. sqr_add_c(a, 5, c2, c3, c1);
  706. sqr_add_c2(a, 6, 4, c2, c3, c1);
  707. sqr_add_c2(a, 7, 3, c2, c3, c1);
  708. r[10] = c2;
  709. c2 = 0;
  710. sqr_add_c2(a, 7, 4, c3, c1, c2);
  711. sqr_add_c2(a, 6, 5, c3, c1, c2);
  712. r[11] = c3;
  713. c3 = 0;
  714. sqr_add_c(a, 6, c1, c2, c3);
  715. sqr_add_c2(a, 7, 5, c1, c2, c3);
  716. r[12] = c1;
  717. c1 = 0;
  718. sqr_add_c2(a, 7, 6, c2, c3, c1);
  719. r[13] = c2;
  720. c2 = 0;
  721. sqr_add_c(a, 7, c3, c1, c2);
  722. r[14] = c3;
  723. r[15] = c1;
  724. }
  725. void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
  726. {
  727. BN_ULONG c1, c2, c3;
  728. c1 = 0;
  729. c2 = 0;
  730. c3 = 0;
  731. sqr_add_c(a, 0, c1, c2, c3);
  732. r[0] = c1;
  733. c1 = 0;
  734. sqr_add_c2(a, 1, 0, c2, c3, c1);
  735. r[1] = c2;
  736. c2 = 0;
  737. sqr_add_c(a, 1, c3, c1, c2);
  738. sqr_add_c2(a, 2, 0, c3, c1, c2);
  739. r[2] = c3;
  740. c3 = 0;
  741. sqr_add_c2(a, 3, 0, c1, c2, c3);
  742. sqr_add_c2(a, 2, 1, c1, c2, c3);
  743. r[3] = c1;
  744. c1 = 0;
  745. sqr_add_c(a, 2, c2, c3, c1);
  746. sqr_add_c2(a, 3, 1, c2, c3, c1);
  747. r[4] = c2;
  748. c2 = 0;
  749. sqr_add_c2(a, 3, 2, c3, c1, c2);
  750. r[5] = c3;
  751. c3 = 0;
  752. sqr_add_c(a, 3, c1, c2, c3);
  753. r[6] = c1;
  754. r[7] = c2;
  755. }
  756. # ifdef OPENSSL_NO_ASM
  757. # ifdef OPENSSL_BN_ASM_MONT
  758. # include <alloca.h>
  759. /*
  760. * This is essentially reference implementation, which may or may not
  761. * result in performance improvement. E.g. on IA-32 this routine was
  762. * observed to give 40% faster rsa1024 private key operations and 10%
  763. * faster rsa4096 ones, while on AMD64 it improves rsa1024 sign only
  764. * by 10% and *worsens* rsa4096 sign by 15%. Once again, it's a
  765. * reference implementation, one to be used as starting point for
  766. * platform-specific assembler. Mentioned numbers apply to compiler
  767. * generated code compiled with and without -DOPENSSL_BN_ASM_MONT and
  768. * can vary not only from platform to platform, but even for compiler
  769. * versions. Assembler vs. assembler improvement coefficients can
  770. * [and are known to] differ and are to be documented elsewhere.
  771. */
  772. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  773. const BN_ULONG *np, const BN_ULONG *n0p, int num)
  774. {
  775. BN_ULONG c0, c1, ml, *tp, n0;
  776. # ifdef mul64
  777. BN_ULONG mh;
  778. # endif
  779. volatile BN_ULONG *vp;
  780. int i = 0, j;
  781. # if 0 /* template for platform-specific
  782. * implementation */
  783. if (ap == bp)
  784. return bn_sqr_mont(rp, ap, np, n0p, num);
  785. # endif
  786. vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
  787. n0 = *n0p;
  788. c0 = 0;
  789. ml = bp[0];
  790. # ifdef mul64
  791. mh = HBITS(ml);
  792. ml = LBITS(ml);
  793. for (j = 0; j < num; ++j)
  794. mul(tp[j], ap[j], ml, mh, c0);
  795. # else
  796. for (j = 0; j < num; ++j)
  797. mul(tp[j], ap[j], ml, c0);
  798. # endif
  799. tp[num] = c0;
  800. tp[num + 1] = 0;
  801. goto enter;
  802. for (i = 0; i < num; i++) {
  803. c0 = 0;
  804. ml = bp[i];
  805. # ifdef mul64
  806. mh = HBITS(ml);
  807. ml = LBITS(ml);
  808. for (j = 0; j < num; ++j)
  809. mul_add(tp[j], ap[j], ml, mh, c0);
  810. # else
  811. for (j = 0; j < num; ++j)
  812. mul_add(tp[j], ap[j], ml, c0);
  813. # endif
  814. c1 = (tp[num] + c0) & BN_MASK2;
  815. tp[num] = c1;
  816. tp[num + 1] = (c1 < c0 ? 1 : 0);
  817. enter:
  818. c1 = tp[0];
  819. ml = (c1 * n0) & BN_MASK2;
  820. c0 = 0;
  821. # ifdef mul64
  822. mh = HBITS(ml);
  823. ml = LBITS(ml);
  824. mul_add(c1, np[0], ml, mh, c0);
  825. # else
  826. mul_add(c1, ml, np[0], c0);
  827. # endif
  828. for (j = 1; j < num; j++) {
  829. c1 = tp[j];
  830. # ifdef mul64
  831. mul_add(c1, np[j], ml, mh, c0);
  832. # else
  833. mul_add(c1, ml, np[j], c0);
  834. # endif
  835. tp[j - 1] = c1 & BN_MASK2;
  836. }
  837. c1 = (tp[num] + c0) & BN_MASK2;
  838. tp[num - 1] = c1;
  839. tp[num] = tp[num + 1] + (c1 < c0 ? 1 : 0);
  840. }
  841. if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
  842. c0 = bn_sub_words(rp, tp, np, num);
  843. if (tp[num] != 0 || c0 == 0) {
  844. for (i = 0; i < num + 2; i++)
  845. vp[i] = 0;
  846. return 1;
  847. }
  848. }
  849. for (i = 0; i < num; i++)
  850. rp[i] = tp[i], vp[i] = 0;
  851. vp[num] = 0;
  852. vp[num + 1] = 0;
  853. return 1;
  854. }
  855. # else
  856. /*
  857. * Return value of 0 indicates that multiplication/convolution was not
  858. * performed to signal the caller to fall down to alternative/original
  859. * code-path.
  860. */
  861. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  862. const BN_ULONG *np, const BN_ULONG *n0, int num)
  863. {
  864. return 0;
  865. }
  866. # endif /* OPENSSL_BN_ASM_MONT */
  867. # endif
  868. #else /* !BN_MUL_COMBA */
  869. /* hmm... is it faster just to do a multiply? */
  870. void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
  871. {
  872. BN_ULONG t[8];
  873. bn_sqr_normal(r, a, 4, t);
  874. }
  875. void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
  876. {
  877. BN_ULONG t[16];
  878. bn_sqr_normal(r, a, 8, t);
  879. }
  880. void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  881. {
  882. r[4] = bn_mul_words(&(r[0]), a, 4, b[0]);
  883. r[5] = bn_mul_add_words(&(r[1]), a, 4, b[1]);
  884. r[6] = bn_mul_add_words(&(r[2]), a, 4, b[2]);
  885. r[7] = bn_mul_add_words(&(r[3]), a, 4, b[3]);
  886. }
  887. void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
  888. {
  889. r[8] = bn_mul_words(&(r[0]), a, 8, b[0]);
  890. r[9] = bn_mul_add_words(&(r[1]), a, 8, b[1]);
  891. r[10] = bn_mul_add_words(&(r[2]), a, 8, b[2]);
  892. r[11] = bn_mul_add_words(&(r[3]), a, 8, b[3]);
  893. r[12] = bn_mul_add_words(&(r[4]), a, 8, b[4]);
  894. r[13] = bn_mul_add_words(&(r[5]), a, 8, b[5]);
  895. r[14] = bn_mul_add_words(&(r[6]), a, 8, b[6]);
  896. r[15] = bn_mul_add_words(&(r[7]), a, 8, b[7]);
  897. }
  898. # ifdef OPENSSL_NO_ASM
  899. # ifdef OPENSSL_BN_ASM_MONT
  900. # include <alloca.h>
  901. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  902. const BN_ULONG *np, const BN_ULONG *n0p, int num)
  903. {
  904. BN_ULONG c0, c1, *tp, n0 = *n0p;
  905. volatile BN_ULONG *vp;
  906. int i = 0, j;
  907. vp = tp = alloca((num + 2) * sizeof(BN_ULONG));
  908. for (i = 0; i <= num; i++)
  909. tp[i] = 0;
  910. for (i = 0; i < num; i++) {
  911. c0 = bn_mul_add_words(tp, ap, num, bp[i]);
  912. c1 = (tp[num] + c0) & BN_MASK2;
  913. tp[num] = c1;
  914. tp[num + 1] = (c1 < c0 ? 1 : 0);
  915. c0 = bn_mul_add_words(tp, np, num, tp[0] * n0);
  916. c1 = (tp[num] + c0) & BN_MASK2;
  917. tp[num] = c1;
  918. tp[num + 1] += (c1 < c0 ? 1 : 0);
  919. for (j = 0; j <= num; j++)
  920. tp[j] = tp[j + 1];
  921. }
  922. if (tp[num] != 0 || tp[num - 1] >= np[num - 1]) {
  923. c0 = bn_sub_words(rp, tp, np, num);
  924. if (tp[num] != 0 || c0 == 0) {
  925. for (i = 0; i < num + 2; i++)
  926. vp[i] = 0;
  927. return 1;
  928. }
  929. }
  930. for (i = 0; i < num; i++)
  931. rp[i] = tp[i], vp[i] = 0;
  932. vp[num] = 0;
  933. vp[num + 1] = 0;
  934. return 1;
  935. }
  936. # else
  937. int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp,
  938. const BN_ULONG *np, const BN_ULONG *n0, int num)
  939. {
  940. return 0;
  941. }
  942. # endif /* OPENSSL_BN_ASM_MONT */
  943. # endif
  944. #endif /* !BN_MUL_COMBA */