git.sur5r.net Git - freertos/blob - FreeRTOS-Plus/Source/CyaSSL/ctaocrypt/src/ecc.c

   1 /* ecc.c
   2  *
   3  * Copyright (C) 2006-2014 wolfSSL Inc.
   4  *
   5  * This file is part of CyaSSL.
   6  *
   7  * CyaSSL is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * CyaSSL is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with this program; if not, write to the Free Software
  19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
  20  */
  21
  22
  23 #ifdef HAVE_CONFIG_H
  24     #include <config.h>
  25 #endif
  26
  27 /* in case user set HAVE_ECC there */
  28 #include <cyassl/ctaocrypt/settings.h>
  29
  30 #ifdef HAVE_ECC
  31
  32 #include <cyassl/ctaocrypt/ecc.h>
  33 #include <cyassl/ctaocrypt/asn.h>
  34 #include <cyassl/ctaocrypt/error-crypt.h>
  35
  36 #ifdef HAVE_ECC_ENCRYPT
  37     #include <cyassl/ctaocrypt/hmac.h>
  38     #include <cyassl/ctaocrypt/aes.h>
  39 #endif
  40
  41
  42 /* map
  43
  44    ptmul -> mulmod
  45
  46 */
  47
  48 #define ECC112
  49 #define ECC128
  50 #define ECC160
  51 #define ECC192
  52 #define ECC224
  53 #define ECC256
  54 #define ECC384
  55 #define ECC521
  56
  57
  58
  59 /* This holds the key settings.  ***MUST*** be organized by size from
  60    smallest to largest. */
  61
  62 const ecc_set_type ecc_sets[] = {
  63 #ifdef ECC112
  64 {
  65         14,
  66         "SECP112R1",
  67         "DB7C2ABF62E35E668076BEAD208B",
  68         "659EF8BA043916EEDE8911702B22",
  69         "DB7C2ABF62E35E7628DFAC6561C5",
  70         "09487239995A5EE76B55F9C2F098",
  71         "A89CE5AF8724C0A23E0E0FF77500"
  72 },
  73 #endif
  74 #ifdef ECC128
  75 {
  76         16,
  77         "SECP128R1",
  78         "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF",
  79         "E87579C11079F43DD824993C2CEE5ED3",
  80         "FFFFFFFE0000000075A30D1B9038A115",
  81         "161FF7528B899B2D0C28607CA52C5B86",
  82         "CF5AC8395BAFEB13C02DA292DDED7A83",
  83 },
  84 #endif
  85 #ifdef ECC160
  86 {
  87         20,
  88         "SECP160R1",
  89         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF",
  90         "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45",
  91         "0100000000000000000001F4C8F927AED3CA752257",
  92         "4A96B5688EF573284664698968C38BB913CBFC82",
  93         "23A628553168947D59DCC912042351377AC5FB32",
  94 },
  95 #endif
  96 #ifdef ECC192
  97 {
  98         24,
  99         "ECC-192",
 100         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF",
 101         "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1",
 102         "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831",
 103         "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012",
 104         "7192B95FFC8DA78631011ED6B24CDD573F977A11E794811",
 105 },
 106 #endif
 107 #ifdef ECC224
 108 {
 109         28,
 110         "ECC-224",
 111         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001",
 112         "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4",
 113         "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D",
 114         "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21",
 115         "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34",
 116 },
 117 #endif
 118 #ifdef ECC256
 119 {
 120         32,
 121         "ECC-256",
 122         "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
 123         "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
 124         "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
 125         "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
 126         "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
 127 },
 128 #endif
 129 #ifdef ECC384
 130 {
 131         48,
 132         "ECC-384",
 133         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF",
 134         "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF",
 135         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
 136         "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7",
 137         "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F",
 138 },
 139 #endif
 140 #ifdef ECC521
 141 {
 142         66,
 143         "ECC-521",
 144         "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
 145         "51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
 146         "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
 147         "C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
 148         "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650",
 149 },
 150 #endif
 151 {
 152    0,
 153    NULL, NULL, NULL, NULL, NULL, NULL
 154 }
 155 };
 156
 157
 158 ecc_point* ecc_new_point(void);
 159 void ecc_del_point(ecc_point* p);
 160 int  ecc_map(ecc_point*, mp_int*, mp_digit*);
 161 int  ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
 162                               mp_int* modulus, mp_digit* mp);
 163 int  ecc_projective_dbl_point(ecc_point* P, ecc_point* R, mp_int* modulus,
 164                               mp_digit* mp);
 165 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
 166                       int map);
 167 #ifdef ECC_SHAMIR
 168 static int ecc_mul2add(ecc_point* A, mp_int* kA, ecc_point* B, mp_int* kB,
 169                        ecc_point* C, mp_int* modulus);
 170 #endif
 171
 172
 173 /* helper for either lib */
 174 static int get_digit_count(mp_int* a)
 175 {
 176     if (a == NULL)
 177         return 0;
 178
 179     return a->used;
 180 }
 181
 182 /* helper for either lib */
 183 static unsigned long get_digit(mp_int* a, int n)
 184 {
 185     if (a == NULL)
 186         return 0;
 187
 188     return (n >= a->used || n < 0) ? 0 : a->dp[n];
 189 }
 190
 191
 192 #if defined(USE_FAST_MATH)
 193
 194 /* fast math accelerated version, but not for fp ecc yet */
 195
 196 /**
 197    Add two ECC points
 198    P        The point to add
 199    Q        The point to add
 200    R        [out] The destination of the double
 201    modulus  The modulus of the field the ECC curve is in
 202    mp       The "b" value from montgomery_setup()
 203    return   MP_OKAY on success
 204 */
 205 int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R,
 206                              mp_int* modulus, mp_digit* mp)
 207 {
 208    fp_int t1, t2, x, y, z;
 209    int    err;
 210
 211    if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
 212        return ECC_BAD_ARG_E;
 213
 214    if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
 215       return err;
 216    }
 217
 218    /* should we dbl instead? */
 219    fp_sub(modulus, &Q->y, &t1);
 220    if ( (fp_cmp(&P->x, &Q->x) == FP_EQ) &&
 221         (get_digit_count(&Q->z) && fp_cmp(&P->z, &Q->z) == FP_EQ) &&
 222         (fp_cmp(&P->y, &Q->y) == FP_EQ || fp_cmp(&P->y, &t1) == FP_EQ)) {
 223         return ecc_projective_dbl_point(P, R, modulus, mp);
 224    }
 225
 226    fp_copy(&P->x, &x);
 227    fp_copy(&P->y, &y);
 228    fp_copy(&P->z, &z);
 229
 230    /* if Z is one then these are no-operations */
 231    if (get_digit_count(&Q->z)) {
 232       /* T1 = Z' * Z' */
 233       fp_sqr(&Q->z, &t1);
 234       fp_montgomery_reduce(&t1, modulus, *mp);
 235       /* X = X * T1 */
 236       fp_mul(&t1, &x, &x);
 237       fp_montgomery_reduce(&x, modulus, *mp);
 238       /* T1 = Z' * T1 */
 239       fp_mul(&Q->z, &t1, &t1);
 240       fp_montgomery_reduce(&t1, modulus, *mp);
 241       /* Y = Y * T1 */
 242       fp_mul(&t1, &y, &y);
 243       fp_montgomery_reduce(&y, modulus, *mp);
 244    }
 245
 246    /* T1 = Z*Z */
 247    fp_sqr(&z, &t1);
 248    fp_montgomery_reduce(&t1, modulus, *mp);
 249    /* T2 = X' * T1 */
 250    fp_mul(&Q->x, &t1, &t2);
 251    fp_montgomery_reduce(&t2, modulus, *mp);
 252    /* T1 = Z * T1 */
 253    fp_mul(&z, &t1, &t1);
 254    fp_montgomery_reduce(&t1, modulus, *mp);
 255    /* T1 = Y' * T1 */
 256    fp_mul(&Q->y, &t1, &t1);
 257    fp_montgomery_reduce(&t1, modulus, *mp);
 258
 259    /* Y = Y - T1 */
 260    fp_sub(&y, &t1, &y);
 261    if (fp_cmp_d(&y, 0) == FP_LT) {
 262       fp_add(&y, modulus, &y);
 263    }
 264    /* T1 = 2T1 */
 265    fp_add(&t1, &t1, &t1);
 266    if (fp_cmp(&t1, modulus) != FP_LT) {
 267       fp_sub(&t1, modulus, &t1);
 268    }
 269    /* T1 = Y + T1 */
 270    fp_add(&t1, &y, &t1);
 271    if (fp_cmp(&t1, modulus) != FP_LT) {
 272       fp_sub(&t1, modulus, &t1);
 273    }
 274    /* X = X - T2 */
 275    fp_sub(&x, &t2, &x);
 276    if (fp_cmp_d(&x, 0) == FP_LT) {
 277       fp_add(&x, modulus, &x);
 278    }
 279    /* T2 = 2T2 */
 280    fp_add(&t2, &t2, &t2);
 281    if (fp_cmp(&t2, modulus) != FP_LT) {
 282       fp_sub(&t2, modulus, &t2);
 283    }
 284    /* T2 = X + T2 */
 285    fp_add(&t2, &x, &t2);
 286    if (fp_cmp(&t2, modulus) != FP_LT) {
 287       fp_sub(&t2, modulus, &t2);
 288    }
 289
 290    /* if Z' != 1 */
 291    if (get_digit_count(&Q->z)) {
 292       /* Z = Z * Z' */
 293       fp_mul(&z, &Q->z, &z);
 294       fp_montgomery_reduce(&z, modulus, *mp);
 295    }
 296
 297    /* Z = Z * X */
 298    fp_mul(&z, &x, &z);
 299    fp_montgomery_reduce(&z, modulus, *mp);
 300
 301    /* T1 = T1 * X  */
 302    fp_mul(&t1, &x, &t1);
 303    fp_montgomery_reduce(&t1, modulus, *mp);
 304    /* X = X * X */
 305    fp_sqr(&x, &x);
 306    fp_montgomery_reduce(&x, modulus, *mp);
 307    /* T2 = T2 * x */
 308    fp_mul(&t2, &x, &t2);
 309    fp_montgomery_reduce(&t2, modulus, *mp);
 310    /* T1 = T1 * X  */
 311    fp_mul(&t1, &x, &t1);
 312    fp_montgomery_reduce(&t1, modulus, *mp);
 313
 314    /* X = Y*Y */
 315    fp_sqr(&y, &x);
 316    fp_montgomery_reduce(&x, modulus, *mp);
 317    /* X = X - T2 */
 318    fp_sub(&x, &t2, &x);
 319    if (fp_cmp_d(&x, 0) == FP_LT) {
 320       fp_add(&x, modulus, &x);
 321    }
 322
 323    /* T2 = T2 - X */
 324    fp_sub(&t2, &x, &t2);
 325    if (fp_cmp_d(&t2, 0) == FP_LT) {
 326       fp_add(&t2, modulus, &t2);
 327    }
 328    /* T2 = T2 - X */
 329    fp_sub(&t2, &x, &t2);
 330    if (fp_cmp_d(&t2, 0) == FP_LT) {
 331       fp_add(&t2, modulus, &t2);
 332    }
 333    /* T2 = T2 * Y */
 334    fp_mul(&t2, &y, &t2);
 335    fp_montgomery_reduce(&t2, modulus, *mp);
 336    /* Y = T2 - T1 */
 337    fp_sub(&t2, &t1, &y);
 338    if (fp_cmp_d(&y, 0) == FP_LT) {
 339       fp_add(&y, modulus, &y);
 340    }
 341    /* Y = Y/2 */
 342    if (fp_isodd(&y)) {
 343       fp_add(&y, modulus, &y);
 344    }
 345    fp_div_2(&y, &y);
 346
 347    fp_copy(&x, &R->x);
 348    fp_copy(&y, &R->y);
 349    fp_copy(&z, &R->z);
 350
 351    return MP_OKAY;
 352 }
 353
 354
 355 /**
 356    Double an ECC point
 357    P   The point to double
 358    R   [out] The destination of the double
 359    modulus  The modulus of the field the ECC curve is in
 360    mp       The "b" value from montgomery_setup()
 361    return   MP_OKAY on success
 362 */
 363 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
 364                              mp_digit* mp)
 365 {
 366    fp_int   t1, t2;
 367    int      err;
 368
 369    if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
 370        return ECC_BAD_ARG_E;
 371
 372    if (P != R) {
 373       fp_copy(&P->x, &R->x);
 374       fp_copy(&P->y, &R->y);
 375       fp_copy(&P->z, &R->z);
 376    }
 377
 378    if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
 379       return err;
 380    }
 381
 382    /* t1 = Z * Z */
 383    fp_sqr(&R->z, &t1);
 384    fp_montgomery_reduce(&t1, modulus, *mp);
 385    /* Z = Y * Z */
 386    fp_mul(&R->z, &R->y, &R->z);
 387    fp_montgomery_reduce(&R->z, modulus, *mp);
 388    /* Z = 2Z */
 389    fp_add(&R->z, &R->z, &R->z);
 390    if (fp_cmp(&R->z, modulus) != FP_LT) {
 391       fp_sub(&R->z, modulus, &R->z);
 392    }
 393
 394    /* &t2 = X - T1 */
 395    fp_sub(&R->x, &t1, &t2);
 396    if (fp_cmp_d(&t2, 0) == FP_LT) {
 397       fp_add(&t2, modulus, &t2);
 398    }
 399    /* T1 = X + T1 */
 400    fp_add(&t1, &R->x, &t1);
 401    if (fp_cmp(&t1, modulus) != FP_LT) {
 402       fp_sub(&t1, modulus, &t1);
 403    }
 404    /* T2 = T1 * T2 */
 405    fp_mul(&t1, &t2, &t2);
 406    fp_montgomery_reduce(&t2, modulus, *mp);
 407    /* T1 = 2T2 */
 408    fp_add(&t2, &t2, &t1);
 409    if (fp_cmp(&t1, modulus) != FP_LT) {
 410       fp_sub(&t1, modulus, &t1);
 411    }
 412    /* T1 = T1 + T2 */
 413    fp_add(&t1, &t2, &t1);
 414    if (fp_cmp(&t1, modulus) != FP_LT) {
 415       fp_sub(&t1, modulus, &t1);
 416    }
 417
 418    /* Y = 2Y */
 419    fp_add(&R->y, &R->y, &R->y);
 420    if (fp_cmp(&R->y, modulus) != FP_LT) {
 421       fp_sub(&R->y, modulus, &R->y);
 422    }
 423    /* Y = Y * Y */
 424    fp_sqr(&R->y, &R->y);
 425    fp_montgomery_reduce(&R->y, modulus, *mp);
 426    /* T2 = Y * Y */
 427    fp_sqr(&R->y, &t2);
 428    fp_montgomery_reduce(&t2, modulus, *mp);
 429    /* T2 = T2/2 */
 430    if (fp_isodd(&t2)) {
 431       fp_add(&t2, modulus, &t2);
 432    }
 433    fp_div_2(&t2, &t2);
 434    /* Y = Y * X */
 435    fp_mul(&R->y, &R->x, &R->y);
 436    fp_montgomery_reduce(&R->y, modulus, *mp);
 437
 438    /* X  = T1 * T1 */
 439    fp_sqr(&t1, &R->x);
 440    fp_montgomery_reduce(&R->x, modulus, *mp);
 441    /* X = X - Y */
 442    fp_sub(&R->x, &R->y, &R->x);
 443    if (fp_cmp_d(&R->x, 0) == FP_LT) {
 444       fp_add(&R->x, modulus, &R->x);
 445    }
 446    /* X = X - Y */
 447    fp_sub(&R->x, &R->y, &R->x);
 448    if (fp_cmp_d(&R->x, 0) == FP_LT) {
 449       fp_add(&R->x, modulus, &R->x);
 450    }
 451
 452    /* Y = Y - X */
 453    fp_sub(&R->y, &R->x, &R->y);
 454    if (fp_cmp_d(&R->y, 0) == FP_LT) {
 455       fp_add(&R->y, modulus, &R->y);
 456    }
 457    /* Y = Y * T1 */
 458    fp_mul(&R->y, &t1, &R->y);
 459    fp_montgomery_reduce(&R->y, modulus, *mp);
 460    /* Y = Y - T2 */
 461    fp_sub(&R->y, &t2, &R->y);
 462    if (fp_cmp_d(&R->y, 0) == FP_LT) {
 463       fp_add(&R->y, modulus, &R->y);
 464    }
 465
 466    return MP_OKAY;
 467 }
 468
 469 #else /* USE_FAST_MATH */
 470
 471 /**
 472    Add two ECC points
 473    P        The point to add
 474    Q        The point to add
 475    R        [out] The destination of the double
 476    modulus  The modulus of the field the ECC curve is in
 477    mp       The "b" value from montgomery_setup()
 478    return   MP_OKAY on success
 479 */
 480 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
 481                              mp_int* modulus, mp_digit* mp)
 482 {
 483    mp_int t1;
 484    mp_int t2;
 485    mp_int x;
 486    mp_int y;
 487    mp_int z;
 488    int    err;
 489
 490    if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
 491        return ECC_BAD_ARG_E;
 492
 493    if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
 494       return err;
 495    }
 496
 497    /* should we dbl instead? */
 498    err = mp_sub(modulus, &Q->y, &t1);
 499
 500    if (err == MP_OKAY) {
 501        if ( (mp_cmp(&P->x, &Q->x) == MP_EQ) &&
 502             (get_digit_count(&Q->z) && mp_cmp(&P->z, &Q->z) == MP_EQ) &&
 503             (mp_cmp(&P->y, &Q->y) == MP_EQ || mp_cmp(&P->y, &t1) == MP_EQ)) {
 504                 mp_clear(&t1);
 505                 mp_clear(&t2);
 506                 mp_clear(&x);
 507                 mp_clear(&y);
 508                 mp_clear(&z);
 509
 510                 return ecc_projective_dbl_point(P, R, modulus, mp);
 511        }
 512    }
 513
 514    if (err == MP_OKAY)
 515        err = mp_copy(&P->x, &x);
 516    if (err == MP_OKAY)
 517        err = mp_copy(&P->y, &y);
 518    if (err == MP_OKAY)
 519        err = mp_copy(&P->z, &z);
 520
 521    /* if Z is one then these are no-operations */
 522    if (err == MP_OKAY) {
 523        if (get_digit_count(&Q->z)) {
 524            /* T1 = Z' * Z' */
 525            err = mp_sqr(&Q->z, &t1);
 526            if (err == MP_OKAY)
 527                err = mp_montgomery_reduce(&t1, modulus, *mp);
 528
 529            /* X = X * T1 */
 530            if (err == MP_OKAY)
 531                err = mp_mul(&t1, &x, &x);
 532            if (err == MP_OKAY)
 533                err = mp_montgomery_reduce(&x, modulus, *mp);
 534
 535            /* T1 = Z' * T1 */
 536            if (err == MP_OKAY)
 537                err = mp_mul(&Q->z, &t1, &t1);
 538            if (err == MP_OKAY)
 539                err = mp_montgomery_reduce(&t1, modulus, *mp);
 540
 541            /* Y = Y * T1 */
 542            if (err == MP_OKAY)
 543                err = mp_mul(&t1, &y, &y);
 544            if (err == MP_OKAY)
 545                err = mp_montgomery_reduce(&y, modulus, *mp);
 546        }
 547    }
 548
 549    /* T1 = Z*Z */
 550    if (err == MP_OKAY)
 551        err = mp_sqr(&z, &t1);
 552    if (err == MP_OKAY)
 553        err = mp_montgomery_reduce(&t1, modulus, *mp);
 554
 555    /* T2 = X' * T1 */
 556    if (err == MP_OKAY)
 557        err = mp_mul(&Q->x, &t1, &t2);
 558    if (err == MP_OKAY)
 559        err = mp_montgomery_reduce(&t2, modulus, *mp);
 560
 561    /* T1 = Z * T1 */
 562    if (err == MP_OKAY)
 563        err = mp_mul(&z, &t1, &t1);
 564    if (err == MP_OKAY)
 565        err = mp_montgomery_reduce(&t1, modulus, *mp);
 566
 567    /* T1 = Y' * T1 */
 568    if (err == MP_OKAY)
 569        err = mp_mul(&Q->y, &t1, &t1);
 570    if (err == MP_OKAY)
 571        err = mp_montgomery_reduce(&t1, modulus, *mp);
 572
 573    /* Y = Y - T1 */
 574    if (err == MP_OKAY)
 575        err = mp_sub(&y, &t1, &y);
 576    if (err == MP_OKAY) {
 577        if (mp_cmp_d(&y, 0) == MP_LT)
 578            err = mp_add(&y, modulus, &y);
 579    }
 580    /* T1 = 2T1 */
 581    if (err == MP_OKAY)
 582        err = mp_add(&t1, &t1, &t1);
 583    if (err == MP_OKAY) {
 584        if (mp_cmp(&t1, modulus) != MP_LT)
 585            err = mp_sub(&t1, modulus, &t1);
 586    }
 587    /* T1 = Y + T1 */
 588    if (err == MP_OKAY)
 589        err = mp_add(&t1, &y, &t1);
 590    if (err == MP_OKAY) {
 591        if (mp_cmp(&t1, modulus) != MP_LT)
 592            err = mp_sub(&t1, modulus, &t1);
 593    }
 594    /* X = X - T2 */
 595    if (err == MP_OKAY)
 596        err = mp_sub(&x, &t2, &x);
 597    if (err == MP_OKAY) {
 598        if (mp_cmp_d(&x, 0) == MP_LT)
 599            err = mp_add(&x, modulus, &x);
 600    }
 601    /* T2 = 2T2 */
 602    if (err == MP_OKAY)
 603        err = mp_add(&t2, &t2, &t2);
 604    if (err == MP_OKAY) {
 605        if (mp_cmp(&t2, modulus) != MP_LT)
 606            err = mp_sub(&t2, modulus, &t2);
 607    }
 608    /* T2 = X + T2 */
 609    if (err == MP_OKAY)
 610        err = mp_add(&t2, &x, &t2);
 611    if (err == MP_OKAY) {
 612        if (mp_cmp(&t2, modulus) != MP_LT)
 613            err = mp_sub(&t2, modulus, &t2);
 614    }
 615
 616    if (err == MP_OKAY) {
 617        if (get_digit_count(&Q->z)) {
 618            /* Z = Z * Z' */
 619            err = mp_mul(&z, &Q->z, &z);
 620            if (err == MP_OKAY)
 621                err = mp_montgomery_reduce(&z, modulus, *mp);
 622        }
 623    }
 624
 625    /* Z = Z * X */
 626    if (err == MP_OKAY)
 627        err = mp_mul(&z, &x, &z);
 628    if (err == MP_OKAY)
 629        err = mp_montgomery_reduce(&z, modulus, *mp);
 630
 631    /* T1 = T1 * X  */
 632    if (err == MP_OKAY)
 633        err = mp_mul(&t1, &x, &t1);
 634    if (err == MP_OKAY)
 635        err = mp_montgomery_reduce(&t1, modulus, *mp);
 636
 637    /* X = X * X */
 638    if (err == MP_OKAY)
 639        err = mp_sqr(&x, &x);
 640    if (err == MP_OKAY)
 641        err = mp_montgomery_reduce(&x, modulus, *mp);
 642
 643    /* T2 = T2 * x */
 644    if (err == MP_OKAY)
 645        err = mp_mul(&t2, &x, &t2);
 646    if (err == MP_OKAY)
 647        err = mp_montgomery_reduce(&t2, modulus, *mp);
 648
 649    /* T1 = T1 * X  */
 650    if (err == MP_OKAY)
 651        err = mp_mul(&t1, &x, &t1);
 652    if (err == MP_OKAY)
 653        err = mp_montgomery_reduce(&t1, modulus, *mp);
 654
 655    /* X = Y*Y */
 656    if (err == MP_OKAY)
 657        err = mp_sqr(&y, &x);
 658    if (err == MP_OKAY)
 659        err = mp_montgomery_reduce(&x, modulus, *mp);
 660
 661    /* X = X - T2 */
 662    if (err == MP_OKAY)
 663        err = mp_sub(&x, &t2, &x);
 664    if (err == MP_OKAY) {
 665        if (mp_cmp_d(&x, 0) == MP_LT)
 666            err = mp_add(&x, modulus, &x);
 667    }
 668    /* T2 = T2 - X */
 669    if (err == MP_OKAY)
 670        err = mp_sub(&t2, &x, &t2);
 671    if (err == MP_OKAY) {
 672        if (mp_cmp_d(&t2, 0) == MP_LT)
 673            err = mp_add(&t2, modulus, &t2);
 674    }
 675    /* T2 = T2 - X */
 676    if (err == MP_OKAY)
 677        err = mp_sub(&t2, &x, &t2);
 678    if (err == MP_OKAY) {
 679        if (mp_cmp_d(&t2, 0) == MP_LT)
 680            err = mp_add(&t2, modulus, &t2);
 681    }
 682    /* T2 = T2 * Y */
 683    if (err == MP_OKAY)
 684        err = mp_mul(&t2, &y, &t2);
 685    if (err == MP_OKAY)
 686        err = mp_montgomery_reduce(&t2, modulus, *mp);
 687
 688    /* Y = T2 - T1 */
 689    if (err == MP_OKAY)
 690        err = mp_sub(&t2, &t1, &y);
 691    if (err == MP_OKAY) {
 692        if (mp_cmp_d(&y, 0) == MP_LT)
 693            err = mp_add(&y, modulus, &y);
 694    }
 695    /* Y = Y/2 */
 696    if (err == MP_OKAY) {
 697        if (mp_isodd(&y))
 698            err = mp_add(&y, modulus, &y);
 699    }
 700    if (err == MP_OKAY)
 701        err = mp_div_2(&y, &y);
 702
 703    if (err == MP_OKAY)
 704        err = mp_copy(&x, &R->x);
 705    if (err == MP_OKAY)
 706        err = mp_copy(&y, &R->y);
 707    if (err == MP_OKAY)
 708        err = mp_copy(&z, &R->z);
 709
 710    /* clean up */
 711    mp_clear(&t1);
 712    mp_clear(&t2);
 713    mp_clear(&x);
 714    mp_clear(&y);
 715    mp_clear(&z);
 716
 717    return err;
 718 }
 719
 720
 721 /**
 722    Double an ECC point
 723    P   The point to double
 724    R   [out] The destination of the double
 725    modulus  The modulus of the field the ECC curve is in
 726    mp       The "b" value from montgomery_setup()
 727    return   MP_OKAY on success
 728 */
 729 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
 730                              mp_digit* mp)
 731 {
 732    mp_int t1;
 733    mp_int t2;
 734    int    err;
 735
 736    if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
 737        return ECC_BAD_ARG_E;
 738
 739    if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
 740       return err;
 741    }
 742
 743    if (P != R) {
 744       err = mp_copy(&P->x, &R->x);
 745       if (err == MP_OKAY)
 746           err = mp_copy(&P->y, &R->y);
 747       if (err == MP_OKAY)
 748           err = mp_copy(&P->z, &R->z);
 749    }
 750
 751    /* t1 = Z * Z */
 752    if (err == MP_OKAY)
 753        err = mp_sqr(&R->z, &t1);
 754    if (err == MP_OKAY)
 755        err = mp_montgomery_reduce(&t1, modulus, *mp);
 756
 757    /* Z = Y * Z */
 758    if (err == MP_OKAY)
 759        err = mp_mul(&R->z, &R->y, &R->z);
 760    if (err == MP_OKAY)
 761        err = mp_montgomery_reduce(&R->z, modulus, *mp);
 762
 763    /* Z = 2Z */
 764    if (err == MP_OKAY)
 765        err = mp_add(&R->z, &R->z, &R->z);
 766    if (err == MP_OKAY) {
 767        if (mp_cmp(&R->z, modulus) != MP_LT)
 768            err = mp_sub(&R->z, modulus, &R->z);
 769    }
 770
 771    /* T2 = X - T1 */
 772    if (err == MP_OKAY)
 773        err = mp_sub(&R->x, &t1, &t2);
 774    if (err == MP_OKAY) {
 775        if (mp_cmp_d(&t2, 0) == MP_LT)
 776            err = mp_add(&t2, modulus, &t2);
 777    }
 778    /* T1 = X + T1 */
 779    if (err == MP_OKAY)
 780        err = mp_add(&t1, &R->x, &t1);
 781    if (err == MP_OKAY) {
 782        if (mp_cmp(&t1, modulus) != MP_LT)
 783            err = mp_sub(&t1, modulus, &t1);
 784    }
 785    /* T2 = T1 * T2 */
 786    if (err == MP_OKAY)
 787        err = mp_mul(&t1, &t2, &t2);
 788    if (err == MP_OKAY)
 789        err = mp_montgomery_reduce(&t2, modulus, *mp);
 790
 791    /* T1 = 2T2 */
 792    if (err == MP_OKAY)
 793        err = mp_add(&t2, &t2, &t1);
 794    if (err == MP_OKAY) {
 795        if (mp_cmp(&t1, modulus) != MP_LT)
 796            err = mp_sub(&t1, modulus, &t1);
 797    }
 798    /* T1 = T1 + T2 */
 799    if (err == MP_OKAY)
 800        err = mp_add(&t1, &t2, &t1);
 801    if (err == MP_OKAY) {
 802        if (mp_cmp(&t1, modulus) != MP_LT)
 803            err = mp_sub(&t1, modulus, &t1);
 804    }
 805    /* Y = 2Y */
 806    if (err == MP_OKAY)
 807        err = mp_add(&R->y, &R->y, &R->y);
 808    if (err == MP_OKAY) {
 809        if (mp_cmp(&R->y, modulus) != MP_LT)
 810            err = mp_sub(&R->y, modulus, &R->y);
 811    }
 812    /* Y = Y * Y */
 813    if (err == MP_OKAY)
 814        err = mp_sqr(&R->y, &R->y);
 815    if (err == MP_OKAY)
 816        err = mp_montgomery_reduce(&R->y, modulus, *mp);
 817
 818    /* T2 = Y * Y */
 819    if (err == MP_OKAY)
 820        err = mp_sqr(&R->y, &t2);
 821    if (err == MP_OKAY)
 822        err = mp_montgomery_reduce(&t2, modulus, *mp);
 823
 824    /* T2 = T2/2 */
 825    if (err == MP_OKAY) {
 826        if (mp_isodd(&t2))
 827            err = mp_add(&t2, modulus, &t2);
 828    }
 829    if (err == MP_OKAY)
 830        err = mp_div_2(&t2, &t2);
 831
 832    /* Y = Y * X */
 833    if (err == MP_OKAY)
 834        err = mp_mul(&R->y, &R->x, &R->y);
 835    if (err == MP_OKAY)
 836        err = mp_montgomery_reduce(&R->y, modulus, *mp);
 837
 838    /* X  = T1 * T1 */
 839    if (err == MP_OKAY)
 840        err = mp_sqr(&t1, &R->x);
 841    if (err == MP_OKAY)
 842        err = mp_montgomery_reduce(&R->x, modulus, *mp);
 843
 844    /* X = X - Y */
 845    if (err == MP_OKAY)
 846        err = mp_sub(&R->x, &R->y, &R->x);
 847    if (err == MP_OKAY) {
 848        if (mp_cmp_d(&R->x, 0) == MP_LT)
 849            err = mp_add(&R->x, modulus, &R->x);
 850    }
 851    /* X = X - Y */
 852    if (err == MP_OKAY)
 853        err = mp_sub(&R->x, &R->y, &R->x);
 854    if (err == MP_OKAY) {
 855        if (mp_cmp_d(&R->x, 0) == MP_LT)
 856            err = mp_add(&R->x, modulus, &R->x);
 857    }
 858    /* Y = Y - X */
 859    if (err == MP_OKAY)
 860        err = mp_sub(&R->y, &R->x, &R->y);
 861    if (err == MP_OKAY) {
 862        if (mp_cmp_d(&R->y, 0) == MP_LT)
 863            err = mp_add(&R->y, modulus, &R->y);
 864    }
 865    /* Y = Y * T1 */
 866    if (err == MP_OKAY)
 867        err = mp_mul(&R->y, &t1, &R->y);
 868    if (err == MP_OKAY)
 869        err = mp_montgomery_reduce(&R->y, modulus, *mp);
 870
 871    /* Y = Y - T2 */
 872    if (err == MP_OKAY)
 873        err = mp_sub(&R->y, &t2, &R->y);
 874    if (err == MP_OKAY) {
 875        if (mp_cmp_d(&R->y, 0) == MP_LT)
 876            err = mp_add(&R->y, modulus, &R->y);
 877    }
 878
 879    /* clean up */
 880    mp_clear(&t1);
 881    mp_clear(&t2);
 882
 883    return err;
 884 }
 885
 886 #endif /* USE_FAST_MATH */
 887
 888 /**
 889   Map a projective jacbobian point back to affine space
 890   P        [in/out] The point to map
 891   modulus  The modulus of the field the ECC curve is in
 892   mp       The "b" value from montgomery_setup()
 893   return   MP_OKAY on success
 894 */
 895 int ecc_map(ecc_point* P, mp_int* modulus, mp_digit* mp)
 896 {
 897    mp_int t1;
 898    mp_int t2;
 899    int    err;
 900
 901    if (P == NULL || mp == NULL || modulus == NULL)
 902        return ECC_BAD_ARG_E;
 903
 904    if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
 905       return MEMORY_E;
 906    }
 907
 908    /* first map z back to normal */
 909    err = mp_montgomery_reduce(&P->z, modulus, *mp);
 910
 911    /* get 1/z */
 912    if (err == MP_OKAY)
 913        err = mp_invmod(&P->z, modulus, &t1);
 914
 915    /* get 1/z^2 and 1/z^3 */
 916    if (err == MP_OKAY)
 917        err = mp_sqr(&t1, &t2);
 918    if (err == MP_OKAY)
 919        err = mp_mod(&t2, modulus, &t2);
 920    if (err == MP_OKAY)
 921        err = mp_mul(&t1, &t2, &t1);
 922    if (err == MP_OKAY)
 923        err = mp_mod(&t1, modulus, &t1);
 924
 925    /* multiply against x/y */
 926    if (err == MP_OKAY)
 927        err = mp_mul(&P->x, &t2, &P->x);
 928    if (err == MP_OKAY)
 929        err = mp_montgomery_reduce(&P->x, modulus, *mp);
 930    if (err == MP_OKAY)
 931        err = mp_mul(&P->y, &t1, &P->y);
 932    if (err == MP_OKAY)
 933        err = mp_montgomery_reduce(&P->y, modulus, *mp);
 934
 935    if (err == MP_OKAY)
 936        mp_set(&P->z, 1);
 937
 938    /* clean up */
 939    mp_clear(&t1);
 940    mp_clear(&t2);
 941
 942    return err;
 943 }
 944
 945
 946 #ifndef ECC_TIMING_RESISTANT
 947
 948 /* size of sliding window, don't change this! */
 949 #define WINSIZE 4
 950
 951 /**
 952    Perform a point multiplication
 953    k    The scalar to multiply by
 954    G    The base point
 955    R    [out] Destination for kG
 956    modulus  The modulus of the field the ECC curve is in
 957    map      Boolean whether to map back to affine or not
 958                 (1==map, 0 == leave in projective)
 959    return MP_OKAY on success
 960 */
 961 #ifdef FP_ECC
 962 static int normal_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R,
 963                              mp_int* modulus, int map)
 964 #else
 965 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
 966                       int map)
 967 #endif
 968 {
 969    ecc_point *tG, *M[8];
 970    int           i, j, err;
 971    mp_int        mu;
 972    mp_digit      mp;
 973    unsigned long buf;
 974    int           first = 1, bitbuf = 0, bitcpy = 0, bitcnt = 0, mode = 0,
 975                  digidx = 0;
 976
 977    if (k == NULL || G == NULL || R == NULL || modulus == NULL)
 978        return ECC_BAD_ARG_E;
 979
 980    /* init montgomery reduction */
 981    if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
 982       return err;
 983    }
 984    if ((err = mp_init(&mu)) != MP_OKAY) {
 985       return err;
 986    }
 987    if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
 988       mp_clear(&mu);
 989       return err;
 990    }
 991
 992   /* alloc ram for window temps */
 993   for (i = 0; i < 8; i++) {
 994       M[i] = ecc_new_point();
 995       if (M[i] == NULL) {
 996          for (j = 0; j < i; j++) {
 997              ecc_del_point(M[j]);
 998          }
 999          mp_clear(&mu);
1000          return MEMORY_E;
1001       }
1002   }
1003
1004    /* make a copy of G incase R==G */
1005    tG = ecc_new_point();
1006    if (tG == NULL)
1007        err = MEMORY_E;
1008
1009    /* tG = G  and convert to montgomery */
1010    if (err == MP_OKAY) {
1011        if (mp_cmp_d(&mu, 1) == MP_EQ) {
1012            err = mp_copy(&G->x, &tG->x);
1013            if (err == MP_OKAY)
1014                err = mp_copy(&G->y, &tG->y);
1015            if (err == MP_OKAY)
1016                err = mp_copy(&G->z, &tG->z);
1017        } else {
1018            err = mp_mulmod(&G->x, &mu, modulus, &tG->x);
1019            if (err == MP_OKAY)
1020                err = mp_mulmod(&G->y, &mu, modulus, &tG->y);
1021            if (err == MP_OKAY)
1022                err = mp_mulmod(&G->z, &mu, modulus, &tG->z);
1023        }
1024    }
1025    mp_clear(&mu);
1026
1027    /* calc the M tab, which holds kG for k==8..15 */
1028    /* M[0] == 8G */
1029    if (err == MP_OKAY)
1030        err = ecc_projective_dbl_point(tG, M[0], modulus, &mp);
1031    if (err == MP_OKAY)
1032        err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
1033    if (err == MP_OKAY)
1034        err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
1035
1036    /* now find (8+k)G for k=1..7 */
1037    if (err == MP_OKAY)
1038        for (j = 9; j < 16; j++) {
1039            err = ecc_projective_add_point(M[j-9], tG, M[j-8], modulus, &mp);
1040            if (err != MP_OKAY) break;
1041        }
1042
1043    /* setup sliding window */
1044    if (err == MP_OKAY) {
1045        mode   = 0;
1046        bitcnt = 1;
1047        buf    = 0;
1048        digidx = get_digit_count(k) - 1;
1049        bitcpy = bitbuf = 0;
1050        first  = 1;
1051
1052        /* perform ops */
1053        for (;;) {
1054            /* grab next digit as required */
1055            if (--bitcnt == 0) {
1056                if (digidx == -1) {
1057                    break;
1058                }
1059                buf    = get_digit(k, digidx);
1060                bitcnt = (int) DIGIT_BIT;
1061                --digidx;
1062            }
1063
1064            /* grab the next msb from the ltiplicand */
1065            i = (int)(buf >> (DIGIT_BIT - 1)) & 1;
1066            buf <<= 1;
1067
1068            /* skip leading zero bits */
1069            if (mode == 0 && i == 0)
1070                continue;
1071
1072            /* if the bit is zero and mode == 1 then we double */
1073            if (mode == 1 && i == 0) {
1074                err = ecc_projective_dbl_point(R, R, modulus, &mp);
1075                if (err != MP_OKAY) break;
1076                continue;
1077            }
1078
1079            /* else we add it to the window */
1080            bitbuf |= (i << (WINSIZE - ++bitcpy));
1081            mode = 2;
1082
1083            if (bitcpy == WINSIZE) {
1084                /* if this is the first window we do a simple copy */
1085                if (first == 1) {
1086                    /* R = kG [k = first window] */
1087                    err = mp_copy(&M[bitbuf-8]->x, &R->x);
1088                    if (err != MP_OKAY) break;
1089
1090                    err = mp_copy(&M[bitbuf-8]->y, &R->y);
1091                    if (err != MP_OKAY) break;
1092
1093                    err = mp_copy(&M[bitbuf-8]->z, &R->z);
1094                    first = 0;
1095                } else {
1096                    /* normal window */
1097                    /* ok window is filled so double as required and add  */
1098                    /* double first */
1099                    for (j = 0; j < WINSIZE; j++) {
1100                        err = ecc_projective_dbl_point(R, R, modulus, &mp);
1101                        if (err != MP_OKAY) break;
1102                    }
1103                    if (err != MP_OKAY) break;  /* out of first for(;;) */
1104
1105                    /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranted */
1106                    err = ecc_projective_add_point(R,M[bitbuf-8],R,modulus,&mp);
1107                }
1108                if (err != MP_OKAY) break;
1109                /* empty window and reset */
1110                bitcpy = bitbuf = 0;
1111                mode = 1;
1112            }
1113        }
1114    }
1115
1116    /* if bits remain then double/add */
1117    if (err == MP_OKAY) {
1118        if (mode == 2 && bitcpy > 0) {
1119            /* double then add */
1120            for (j = 0; j < bitcpy; j++) {
1121                /* only double if we have had at least one add first */
1122                if (first == 0) {
1123                    err = ecc_projective_dbl_point(R, R, modulus, &mp);
1124                    if (err != MP_OKAY) break;
1125                }
1126
1127                bitbuf <<= 1;
1128                if ((bitbuf & (1 << WINSIZE)) != 0) {
1129                    if (first == 1) {
1130                        /* first add, so copy */
1131                        err = mp_copy(&tG->x, &R->x);
1132                        if (err != MP_OKAY) break;
1133
1134                        err = mp_copy(&tG->y, &R->y);
1135                        if (err != MP_OKAY) break;
1136
1137                        err = mp_copy(&tG->z, &R->z);
1138                        if (err != MP_OKAY) break;
1139                        first = 0;
1140                    } else {
1141                        /* then add */
1142                        err = ecc_projective_add_point(R, tG, R, modulus, &mp);
1143                        if (err != MP_OKAY) break;
1144                    }
1145                }
1146            }
1147        }
1148    }
1149
1150    /* map R back from projective space */
1151    if (err == MP_OKAY && map)
1152        err = ecc_map(R, modulus, &mp);
1153
1154    mp_clear(&mu);
1155    ecc_del_point(tG);
1156    for (i = 0; i < 8; i++) {
1157        ecc_del_point(M[i]);
1158    }
1159    return err;
1160 }
1161
1162 #undef WINSIZE
1163 #endif /* ECC_TIMING_RESISTANT */
1164
1165
1166 /**
1167    Allocate a new ECC point
1168    return A newly allocated point or NULL on error
1169 */
1170 ecc_point* ecc_new_point(void)
1171 {
1172    ecc_point* p;
1173    p = (ecc_point*)XMALLOC(sizeof(ecc_point), 0, DYNAMIC_TYPE_BIGINT);
1174    if (p == NULL) {
1175       return NULL;
1176    }
1177    XMEMSET(p, 0, sizeof(ecc_point));
1178    if (mp_init_multi(&p->x, &p->y, &p->z, NULL, NULL, NULL) != MP_OKAY) {
1179       XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
1180       return NULL;
1181    }
1182    return p;
1183 }
1184
1185 /** Free an ECC point from memory
1186   p   The point to free
1187 */
1188 void ecc_del_point(ecc_point* p)
1189 {
1190    /* prevents free'ing null arguments */
1191    if (p != NULL) {
1192       mp_clear(&p->x);
1193       mp_clear(&p->y);
1194       mp_clear(&p->z);
1195       XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
1196    }
1197 }
1198
1199
1200 /** Returns whether an ECC idx is valid or not
1201   n      The idx number to check
1202   return 1 if valid, 0 if not
1203 */
1204 static int ecc_is_valid_idx(int n)
1205 {
1206    int x;
1207
1208    for (x = 0; ecc_sets[x].size != 0; x++)
1209        ;
1210    /* -1 is a valid index --- indicating that the domain params
1211       were supplied by the user */
1212    if ((n >= -1) && (n < x)) {
1213       return 1;
1214    }
1215    return 0;
1216 }
1217
1218
1219 /**
1220   Create an ECC shared secret between two keys
1221   private_key      The private ECC key
1222   public_key       The public key
1223   out              [out] Destination of the shared secret
1224                    Conforms to EC-DH from ANSI X9.63
1225   outlen           [in/out] The max size and resulting size of the shared secret
1226   return           MP_OKAY if successful
1227 */
1228 int ecc_shared_secret(ecc_key* private_key, ecc_key* public_key, byte* out,
1229                       word32* outlen)
1230 {
1231    word32         x = 0;
1232    ecc_point*     result;
1233    mp_int         prime;
1234    int            err;
1235
1236    if (private_key == NULL || public_key == NULL || out == NULL ||
1237                                                     outlen == NULL)
1238        return BAD_FUNC_ARG;
1239
1240    /* type valid? */
1241    if (private_key->type != ECC_PRIVATEKEY) {
1242       return ECC_BAD_ARG_E;
1243    }
1244
1245    if (ecc_is_valid_idx(private_key->idx) == 0 ||
1246        ecc_is_valid_idx(public_key->idx)  == 0)
1247       return ECC_BAD_ARG_E;
1248
1249    if (XSTRNCMP(private_key->dp->name, public_key->dp->name, ECC_MAXNAME) != 0)
1250       return ECC_BAD_ARG_E;
1251
1252    /* make new point */
1253    result = ecc_new_point();
1254    if (result == NULL) {
1255       return MEMORY_E;
1256    }
1257
1258    if ((err = mp_init(&prime)) != MP_OKAY) {
1259       ecc_del_point(result);
1260       return err;
1261    }
1262
1263    err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16);
1264
1265    if (err == MP_OKAY)
1266        err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime,1);
1267
1268    if (err == MP_OKAY) {
1269        x = mp_unsigned_bin_size(&prime);
1270        if (*outlen < x)
1271           err = BUFFER_E;
1272    }
1273
1274    if (err == MP_OKAY) {
1275        XMEMSET(out, 0, x);
1276        err = mp_to_unsigned_bin(&result->x,out + (x -
1277                                             mp_unsigned_bin_size(&result->x)));
1278        *outlen = x;
1279    }
1280
1281    mp_clear(&prime);
1282    ecc_del_point(result);
1283
1284    return err;
1285 }
1286
1287
1288 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp);
1289
1290 /**
1291   Make a new ECC key
1292   rng          An active RNG state
1293   keysize      The keysize for the new key (in octets from 20 to 65 bytes)
1294   key          [out] Destination of the newly created key
1295   return       MP_OKAY if successful,
1296                        upon error all allocated memory will be freed
1297 */
1298 int ecc_make_key(RNG* rng, int keysize, ecc_key* key)
1299 {
1300    int x, err;
1301
1302    if (key == NULL || rng == NULL)
1303        return ECC_BAD_ARG_E;
1304
1305    /* find key size */
1306    for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++)
1307        ;
1308    keysize = ecc_sets[x].size;
1309
1310    if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) {
1311       return BAD_FUNC_ARG;
1312    }
1313    err = ecc_make_key_ex(rng, key, &ecc_sets[x]);
1314    key->idx = x;
1315
1316    return err;
1317 }
1318
1319 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp)
1320 {
1321    int            err;
1322    ecc_point*     base;
1323    mp_int         prime;
1324    mp_int         order;
1325 #ifdef CYASSL_SMALL_STACK
1326    byte*          buf;
1327 #else
1328    byte           buf[ECC_MAXSIZE];
1329 #endif
1330    int            keysize;
1331
1332    if (key == NULL || rng == NULL || dp == NULL)
1333        return ECC_BAD_ARG_E;
1334
1335 #ifdef CYASSL_SMALL_STACK
1336    buf = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1337    if (buf == NULL)
1338        return MEMORY_E;
1339 #endif
1340
1341    key->idx = -1;
1342    key->dp  = dp;
1343    keysize  = dp->size;
1344
1345    /* allocate ram */
1346    base = NULL;
1347
1348    /* make up random string */
1349    err = RNG_GenerateBlock(rng, buf, keysize);
1350    if (err == 0)
1351        buf[0] |= 0x0c;
1352
1353    /* setup the key variables */
1354    if (err == 0) {
1355        err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z,
1356                             &key->k, &prime, &order);
1357        if (err != MP_OKAY)
1358            err = MEMORY_E;
1359    }
1360
1361    if (err == MP_OKAY) {
1362        base = ecc_new_point();
1363        if (base == NULL)
1364            err = MEMORY_E;
1365    }
1366
1367    /* read in the specs for this key */
1368    if (err == MP_OKAY)
1369        err = mp_read_radix(&prime,   (char *)key->dp->prime, 16);
1370    if (err == MP_OKAY)
1371        err = mp_read_radix(&order,   (char *)key->dp->order, 16);
1372    if (err == MP_OKAY)
1373        err = mp_read_radix(&base->x, (char *)key->dp->Gx, 16);
1374    if (err == MP_OKAY)
1375        err = mp_read_radix(&base->y, (char *)key->dp->Gy, 16);
1376
1377    if (err == MP_OKAY)
1378        mp_set(&base->z, 1);
1379    if (err == MP_OKAY)
1380        err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize);
1381
1382    /* the key should be smaller than the order of base point */
1383    if (err == MP_OKAY) {
1384        if (mp_cmp(&key->k, &order) != MP_LT)
1385            err = mp_mod(&key->k, &order, &key->k);
1386    }
1387    /* make the public key */
1388    if (err == MP_OKAY)
1389        err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1);
1390    if (err == MP_OKAY)
1391        key->type = ECC_PRIVATEKEY;
1392
1393    if (err != MP_OKAY) {
1394        /* clean up */
1395        mp_clear(&key->pubkey.x);
1396        mp_clear(&key->pubkey.y);
1397        mp_clear(&key->pubkey.z);
1398        mp_clear(&key->k);
1399    }
1400    ecc_del_point(base);
1401    mp_clear(&prime);
1402    mp_clear(&order);
1403
1404 #ifdef ECC_CLEAN_STACK
1405    XMEMSET(buf, 0, ECC_MAXSIZE);
1406 #endif
1407
1408 #ifdef CYASSL_SMALL_STACK
1409    XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1410 #endif
1411
1412    return err;
1413 }
1414
1415
1416 /* Setup dynamic pointers is using normal math for proper freeing */
1417 void ecc_init(ecc_key* key)
1418 {
1419     (void)key;
1420 #ifndef USE_FAST_MATH
1421     key->pubkey.x.dp = NULL;
1422     key->pubkey.y.dp = NULL;
1423     key->pubkey.z.dp = NULL;
1424
1425     key->k.dp = NULL;
1426 #endif
1427 }
1428
1429
1430 /**
1431   Sign a message digest
1432   in        The message digest to sign
1433   inlen     The length of the digest
1434   out       [out] The destination for the signature
1435   outlen    [in/out] The max size and resulting size of the signature
1436   key       A private ECC key
1437   return    MP_OKAY if successful
1438 */
1439 int ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen,
1440                   RNG* rng, ecc_key* key)
1441 {
1442    mp_int        r;
1443    mp_int        s;
1444    mp_int        e;
1445    mp_int        p;
1446    int           err;
1447
1448    if (in == NULL || out == NULL || outlen == NULL || key == NULL || rng ==NULL)
1449        return ECC_BAD_ARG_E;
1450
1451    /* is this a private key? */
1452    if (key->type != ECC_PRIVATEKEY) {
1453       return ECC_BAD_ARG_E;
1454    }
1455
1456    /* is the IDX valid ?  */
1457    if (ecc_is_valid_idx(key->idx) != 1) {
1458       return ECC_BAD_ARG_E;
1459    }
1460
1461    /* get the hash and load it as a bignum into 'e' */
1462    /* init the bignums */
1463    if ((err = mp_init_multi(&r, &s, &p, &e, NULL, NULL)) != MP_OKAY) {
1464       return err;
1465    }
1466    err = mp_read_radix(&p, (char *)key->dp->order, 16);
1467
1468    if (err == MP_OKAY) {
1469        /* we may need to truncate if hash is longer than key size */
1470        word32 orderBits = mp_count_bits(&p);
1471
1472        /* truncate down to byte size, may be all that's needed */
1473        if ( (CYASSL_BIT_SIZE * inlen) > orderBits)
1474            inlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE;
1475        err = mp_read_unsigned_bin(&e, (byte*)in, inlen);
1476
1477        /* may still need bit truncation too */
1478        if (err == MP_OKAY && (CYASSL_BIT_SIZE * inlen) > orderBits)
1479            mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7));
1480    }
1481
1482    /* make up a key and export the public copy */
1483    if (err == MP_OKAY) {
1484        ecc_key pubkey;
1485        ecc_init(&pubkey);
1486        for (;;) {
1487            err = ecc_make_key_ex(rng, &pubkey, key->dp);
1488            if (err != MP_OKAY) break;
1489
1490            /* find r = x1 mod n */
1491            err = mp_mod(&pubkey.pubkey.x, &p, &r);
1492            if (err != MP_OKAY) break;
1493
1494            if (mp_iszero(&r) == MP_YES)
1495                ecc_free(&pubkey);
1496            else {
1497                /* find s = (e + xr)/k */
1498                err = mp_invmod(&pubkey.k, &p, &pubkey.k);
1499                if (err != MP_OKAY) break;
1500
1501                err = mp_mulmod(&key->k, &r, &p, &s);   /* s = xr */
1502                if (err != MP_OKAY) break;
1503
1504                err = mp_add(&e, &s, &s);               /* s = e +  xr */
1505                if (err != MP_OKAY) break;
1506
1507                err = mp_mod(&s, &p, &s);               /* s = e +  xr */
1508                if (err != MP_OKAY) break;
1509
1510                err = mp_mulmod(&s, &pubkey.k, &p, &s); /* s = (e + xr)/k */
1511                if (err != MP_OKAY) break;
1512
1513                ecc_free(&pubkey);
1514                if (mp_iszero(&s) == MP_NO)
1515                    break;
1516             }
1517        }
1518        ecc_free(&pubkey);
1519    }
1520
1521    /* store as SEQUENCE { r, s -- integer } */
1522    if (err == MP_OKAY)
1523        err = StoreECC_DSA_Sig(out, outlen, &r, &s);
1524
1525    mp_clear(&r);
1526    mp_clear(&s);
1527    mp_clear(&p);
1528    mp_clear(&e);
1529
1530    return err;
1531 }
1532
1533
1534 /**
1535   Free an ECC key from memory
1536   key   The key you wish to free
1537 */
1538 void ecc_free(ecc_key* key)
1539 {
1540    if (key == NULL)
1541        return;
1542
1543    mp_clear(&key->pubkey.x);
1544    mp_clear(&key->pubkey.y);
1545    mp_clear(&key->pubkey.z);
1546    mp_clear(&key->k);
1547 }
1548
1549
1550 #ifdef USE_FAST_MATH
1551     #define GEN_MEM_ERR FP_MEM
1552 #else
1553     #define GEN_MEM_ERR MP_MEM
1554 #endif
1555
1556 #ifdef ECC_SHAMIR
1557
1558 /** Computes kA*A + kB*B = C using Shamir's Trick
1559   A        First point to multiply
1560   kA       What to multiple A by
1561   B        Second point to multiply
1562   kB       What to multiple B by
1563   C        [out] Destination point (can overlap with A or B)
1564   modulus  Modulus for curve
1565   return MP_OKAY on success
1566 */
1567 #ifdef FP_ECC
1568 static int normal_ecc_mul2add(ecc_point* A, mp_int* kA,
1569                              ecc_point* B, mp_int* kB,
1570                              ecc_point* C, mp_int* modulus)
1571 #else
1572 static int ecc_mul2add(ecc_point* A, mp_int* kA,
1573                     ecc_point* B, mp_int* kB,
1574                     ecc_point* C, mp_int* modulus)
1575 #endif
1576 {
1577   ecc_point*     precomp[16];
1578   unsigned       bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
1579   unsigned char* tA;
1580   unsigned char* tB;
1581   int            err = MP_OKAY, first;
1582   int            muInit    = 0;
1583   int            tableInit = 0;
1584   mp_digit mp;
1585   mp_int   mu;
1586
1587   /* argchks */
1588   if (A == NULL || kA == NULL || B == NULL || kB == NULL || C == NULL ||
1589                    modulus == NULL)
1590     return ECC_BAD_ARG_E;
1591
1592
1593   /* allocate memory */
1594   tA = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1595   if (tA == NULL) {
1596      return GEN_MEM_ERR;
1597   }
1598   tB = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1599   if (tB == NULL) {
1600      XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1601      return GEN_MEM_ERR;
1602   }
1603   XMEMSET(tA, 0, ECC_BUFSIZE);
1604   XMEMSET(tB, 0, ECC_BUFSIZE);
1605
1606   /* get sizes */
1607   lenA = mp_unsigned_bin_size(kA);
1608   lenB = mp_unsigned_bin_size(kB);
1609   len  = MAX(lenA, lenB);
1610
1611   /* sanity check */
1612   if ((lenA > ECC_BUFSIZE) || (lenB > ECC_BUFSIZE)) {
1613      err = BAD_FUNC_ARG;
1614   }
1615
1616   if (err == MP_OKAY) {
1617     /* extract and justify kA */
1618     err = mp_to_unsigned_bin(kA, (len - lenA) + tA);
1619
1620     /* extract and justify kB */
1621     if (err == MP_OKAY)
1622         err = mp_to_unsigned_bin(kB, (len - lenB) + tB);
1623
1624     /* allocate the table */
1625     if (err == MP_OKAY) {
1626         for (x = 0; x < 16; x++) {
1627             precomp[x] = ecc_new_point();
1628             if (precomp[x] == NULL) {
1629                 for (y = 0; y < x; ++y) {
1630                     ecc_del_point(precomp[y]);
1631                 }
1632                 err = GEN_MEM_ERR;
1633                 break;
1634             }
1635         }
1636     }
1637   }
1638
1639   if (err == MP_OKAY)
1640     tableInit = 1;
1641
1642   if (err == MP_OKAY)
1643    /* init montgomery reduction */
1644    err = mp_montgomery_setup(modulus, &mp);
1645
1646   if (err == MP_OKAY)
1647     err = mp_init(&mu);
1648   if (err == MP_OKAY)
1649     muInit = 1;
1650
1651   if (err == MP_OKAY)
1652     err = mp_montgomery_calc_normalization(&mu, modulus);
1653
1654   if (err == MP_OKAY)
1655     /* copy ones ... */
1656     err = mp_mulmod(&A->x, &mu, modulus, &precomp[1]->x);
1657
1658   if (err == MP_OKAY)
1659     err = mp_mulmod(&A->y, &mu, modulus, &precomp[1]->y);
1660   if (err == MP_OKAY)
1661     err = mp_mulmod(&A->z, &mu, modulus, &precomp[1]->z);
1662
1663   if (err == MP_OKAY)
1664     err = mp_mulmod(&B->x, &mu, modulus, &precomp[1<<2]->x);
1665   if (err == MP_OKAY)
1666     err = mp_mulmod(&B->y, &mu, modulus, &precomp[1<<2]->y);
1667   if (err == MP_OKAY)
1668     err = mp_mulmod(&B->z, &mu, modulus, &precomp[1<<2]->z);
1669
1670   if (err == MP_OKAY)
1671     /* precomp [i,0](A + B) table */
1672     err = ecc_projective_dbl_point(precomp[1], precomp[2], modulus, &mp);
1673
1674   if (err == MP_OKAY)
1675     err = ecc_projective_add_point(precomp[1], precomp[2], precomp[3],
1676                                    modulus, &mp);
1677   if (err == MP_OKAY)
1678     /* precomp [0,i](A + B) table */
1679     err = ecc_projective_dbl_point(precomp[1<<2], precomp[2<<2], modulus, &mp);
1680
1681   if (err == MP_OKAY)
1682     err = ecc_projective_add_point(precomp[1<<2], precomp[2<<2], precomp[3<<2],
1683                                    modulus, &mp);
1684
1685   if (err == MP_OKAY) {
1686     /* precomp [i,j](A + B) table (i != 0, j != 0) */
1687     for (x = 1; x < 4; x++) {
1688         for (y = 1; y < 4; y++) {
1689             if (err == MP_OKAY)
1690                 err = ecc_projective_add_point(precomp[x], precomp[(y<<2)],
1691                                                precomp[x+(y<<2)], modulus, &mp);
1692         }
1693     }
1694   }
1695
1696   if (err == MP_OKAY) {
1697     nibble  = 3;
1698     first   = 1;
1699     bitbufA = tA[0];
1700     bitbufB = tB[0];
1701
1702     /* for every byte of the multiplicands */
1703     for (x = -1;; ) {
1704         /* grab a nibble */
1705         if (++nibble == 4) {
1706             ++x; if (x == len) break;
1707             bitbufA = tA[x];
1708             bitbufB = tB[x];
1709             nibble  = 0;
1710         }
1711
1712         /* extract two bits from both, shift/update */
1713         nA = (bitbufA >> 6) & 0x03;
1714         nB = (bitbufB >> 6) & 0x03;
1715         bitbufA = (bitbufA << 2) & 0xFF;
1716         bitbufB = (bitbufB << 2) & 0xFF;
1717
1718         /* if both zero, if first, continue */
1719         if ((nA == 0) && (nB == 0) && (first == 1)) {
1720             continue;
1721         }
1722
1723         /* double twice, only if this isn't the first */
1724         if (first == 0) {
1725             /* double twice */
1726             if (err == MP_OKAY)
1727                 err = ecc_projective_dbl_point(C, C, modulus, &mp);
1728             if (err == MP_OKAY)
1729                 err = ecc_projective_dbl_point(C, C, modulus, &mp);
1730             else
1731                 break;
1732         }
1733
1734         /* if not both zero */
1735         if ((nA != 0) || (nB != 0)) {
1736             if (first == 1) {
1737                 /* if first, copy from table */
1738                 first = 0;
1739                 if (err == MP_OKAY)
1740                     err = mp_copy(&precomp[nA + (nB<<2)]->x, &C->x);
1741
1742                 if (err == MP_OKAY)
1743                     err = mp_copy(&precomp[nA + (nB<<2)]->y, &C->y);
1744
1745                 if (err == MP_OKAY)
1746                     err = mp_copy(&precomp[nA + (nB<<2)]->z, &C->z);
1747                 else
1748                     break;
1749             } else {
1750                 /* if not first, add from table */
1751                 if (err == MP_OKAY)
1752                     err = ecc_projective_add_point(C, precomp[nA + (nB<<2)], C,
1753                                                    modulus, &mp);
1754                 else
1755                     break;
1756             }
1757         }
1758     }
1759   }
1760
1761   if (err == MP_OKAY)
1762     /* reduce to affine */
1763     err = ecc_map(C, modulus, &mp);
1764
1765   /* clean up */
1766   if (muInit)
1767     mp_clear(&mu);
1768
1769   if (tableInit) {
1770     for (x = 0; x < 16; x++) {
1771        ecc_del_point(precomp[x]);
1772     }
1773   }
1774 #ifdef ECC_CLEAN_STACK
1775    XMEMSET(tA, 0, ECC_BUFSIZE);
1776    XMEMSET(tB, 0, ECC_BUFSIZE);
1777 #endif
1778    XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1779    XFREE(tB, NULL, DYNAMIC_TYPE_TMP_BUFFER);
1780
1781    return err;
1782 }
1783
1784
1785 #endif /* ECC_SHAMIR */
1786
1787
1788
1789 /* verify
1790  *
1791  * w  = s^-1 mod n
1792  * u1 = xw
1793  * u2 = rw
1794  * X = u1*G + u2*Q
1795  * v = X_x1 mod n
1796  * accept if v == r
1797  */
1798
1799 /**
1800    Verify an ECC signature
1801    sig         The signature to verify
1802    siglen      The length of the signature (octets)
1803    hash        The hash (message digest) that was signed
1804    hashlen     The length of the hash (octets)
1805    stat        Result of signature, 1==valid, 0==invalid
1806    key         The corresponding public ECC key
1807    return      MP_OKAY if successful (even if the signature is not valid)
1808 */
1809 int ecc_verify_hash(const byte* sig, word32 siglen, const byte* hash,
1810                     word32 hashlen, int* stat, ecc_key* key)
1811 {
1812    ecc_point    *mG, *mQ;
1813    mp_int        r;
1814    mp_int        s;
1815    mp_int        v;
1816    mp_int        w;
1817    mp_int        u1;
1818    mp_int        u2;
1819    mp_int        e;
1820    mp_int        p;
1821    mp_int        m;
1822    int           err;
1823
1824    if (sig == NULL || hash == NULL || stat == NULL || key == NULL)
1825        return ECC_BAD_ARG_E;
1826
1827    /* default to invalid signature */
1828    *stat = 0;
1829
1830    /* is the IDX valid ?  */
1831    if (ecc_is_valid_idx(key->idx) != 1) {
1832       return ECC_BAD_ARG_E;
1833    }
1834
1835    /* allocate ints */
1836    if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) {
1837       return MEMORY_E;
1838    }
1839
1840    if ((err = mp_init(&m)) != MP_OKAY) {
1841       mp_clear(&v);
1842       mp_clear(&w);
1843       mp_clear(&u1);
1844       mp_clear(&u2);
1845       mp_clear(&p);
1846       mp_clear(&e);
1847       return MEMORY_E;
1848    }
1849
1850    /* allocate points */
1851    mG = ecc_new_point();
1852    mQ = ecc_new_point();
1853    if (mQ  == NULL || mG == NULL)
1854       err = MEMORY_E;
1855
1856    /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s.
1857     * If either of those don't allocate correctly, none of
1858     * the rest of this function will execute, and everything
1859     * gets cleaned up at the end. */
1860    XMEMSET(&r, 0, sizeof(r));
1861    XMEMSET(&s, 0, sizeof(s));
1862    if (err == MP_OKAY)
1863        err = DecodeECC_DSA_Sig(sig, siglen, &r, &s);
1864
1865    /* get the order */
1866    if (err == MP_OKAY)
1867        err = mp_read_radix(&p, (char *)key->dp->order, 16);
1868
1869    /* get the modulus */
1870    if (err == MP_OKAY)
1871        err = mp_read_radix(&m, (char *)key->dp->prime, 16);
1872
1873    /* check for zero */
1874    if (err == MP_OKAY) {
1875        if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT ||
1876                                              mp_cmp(&s, &p) != MP_LT)
1877            err = MP_ZERO_E;
1878    }
1879    /* read hash */
1880    if (err == MP_OKAY) {
1881        /* we may need to truncate if hash is longer than key size */
1882        unsigned int orderBits = mp_count_bits(&p);
1883
1884        /* truncate down to byte size, may be all that's needed */
1885        if ( (CYASSL_BIT_SIZE * hashlen) > orderBits)
1886            hashlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE;
1887        err = mp_read_unsigned_bin(&e, hash, hashlen);
1888
1889        /* may still need bit truncation too */
1890        if (err == MP_OKAY && (CYASSL_BIT_SIZE * hashlen) > orderBits)
1891            mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7));
1892    }
1893
1894    /*  w  = s^-1 mod n */
1895    if (err == MP_OKAY)
1896        err = mp_invmod(&s, &p, &w);
1897
1898    /* u1 = ew */
1899    if (err == MP_OKAY)
1900        err = mp_mulmod(&e, &w, &p, &u1);
1901
1902    /* u2 = rw */
1903    if (err == MP_OKAY)
1904        err = mp_mulmod(&r, &w, &p, &u2);
1905
1906    /* find mG and mQ */
1907    if (err == MP_OKAY)
1908        err = mp_read_radix(&mG->x, (char *)key->dp->Gx, 16);
1909
1910    if (err == MP_OKAY)
1911        err = mp_read_radix(&mG->y, (char *)key->dp->Gy, 16);
1912    if (err == MP_OKAY)
1913        mp_set(&mG->z, 1);
1914
1915    if (err == MP_OKAY)
1916        err = mp_copy(&key->pubkey.x, &mQ->x);
1917    if (err == MP_OKAY)
1918        err = mp_copy(&key->pubkey.y, &mQ->y);
1919    if (err == MP_OKAY)
1920        err = mp_copy(&key->pubkey.z, &mQ->z);
1921
1922 #ifndef ECC_SHAMIR
1923     {
1924        mp_digit      mp;
1925
1926        /* compute u1*mG + u2*mQ = mG */
1927        if (err == MP_OKAY)
1928            err = ecc_mulmod(&u1, mG, mG, &m, 0);
1929        if (err == MP_OKAY)
1930            err = ecc_mulmod(&u2, mQ, mQ, &m, 0);
1931
1932        /* find the montgomery mp */
1933        if (err == MP_OKAY)
1934            err = mp_montgomery_setup(&m, &mp);
1935
1936        /* add them */
1937        if (err == MP_OKAY)
1938            err = ecc_projective_add_point(mQ, mG, mG, &m, &mp);
1939
1940        /* reduce */
1941        if (err == MP_OKAY)
1942            err = ecc_map(mG, &m, &mp);
1943     }
1944 #else
1945        /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */
1946        if (err == MP_OKAY)
1947            err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m);
1948 #endif /* ECC_SHAMIR */
1949
1950    /* v = X_x1 mod n */
1951    if (err == MP_OKAY)
1952        err = mp_mod(&mG->x, &p, &v);
1953
1954    /* does v == r */
1955    if (err == MP_OKAY) {
1956        if (mp_cmp(&v, &r) == MP_EQ)
1957            *stat = 1;
1958    }
1959
1960    ecc_del_point(mG);
1961    ecc_del_point(mQ);
1962
1963    mp_clear(&r);
1964    mp_clear(&s);
1965    mp_clear(&v);
1966    mp_clear(&w);
1967    mp_clear(&u1);
1968    mp_clear(&u2);
1969    mp_clear(&p);
1970    mp_clear(&e);
1971    mp_clear(&m);
1972
1973    return err;
1974 }
1975
1976
1977 /* export public ECC key in ANSI X9.63 format */
1978 int ecc_export_x963(ecc_key* key, byte* out, word32* outLen)
1979 {
1980 #ifdef CYASSL_SMALL_STACK
1981    byte*  buf;
1982 #else
1983    byte   buf[ECC_BUFSIZE];
1984 #endif
1985    word32 numlen;
1986    int    ret = MP_OKAY;
1987
1988    if (key == NULL || out == NULL || outLen == NULL)
1989        return ECC_BAD_ARG_E;
1990
1991    if (ecc_is_valid_idx(key->idx) == 0) {
1992       return ECC_BAD_ARG_E;
1993    }
1994    numlen = key->dp->size;
1995
1996    if (*outLen < (1 + 2*numlen)) {
1997       *outLen = 1 + 2*numlen;
1998       return BUFFER_E;
1999    }
2000
2001    /* store byte 0x04 */
2002    out[0] = 0x04;
2003
2004 #ifdef CYASSL_SMALL_STACK
2005    buf = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2006    if (buf == NULL)
2007       return MEMORY_E;
2008 #endif
2009
2010    do {
2011       /* pad and store x */
2012       XMEMSET(buf, 0, ECC_BUFSIZE);
2013       ret = mp_to_unsigned_bin(&key->pubkey.x,
2014                          buf + (numlen - mp_unsigned_bin_size(&key->pubkey.x)));
2015       if (ret != MP_OKAY)
2016          break;
2017       XMEMCPY(out+1, buf, numlen);
2018
2019       /* pad and store y */
2020       XMEMSET(buf, 0, ECC_BUFSIZE);
2021       ret = mp_to_unsigned_bin(&key->pubkey.y,
2022                          buf + (numlen - mp_unsigned_bin_size(&key->pubkey.y)));
2023       if (ret != MP_OKAY)
2024          break;
2025       XMEMCPY(out+1+numlen, buf, numlen);
2026
2027       *outLen = 1 + 2*numlen;
2028    } while (0);
2029
2030 #ifdef CYASSL_SMALL_STACK
2031    XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);
2032 #endif
2033
2034    return ret;
2035 }
2036
2037
2038 /* import public ECC key in ANSI X9.63 format */
2039 int ecc_import_x963(const byte* in, word32 inLen, ecc_key* key)
2040 {
2041    int x, err;
2042
2043    if (in == NULL || key == NULL)
2044        return ECC_BAD_ARG_E;
2045
2046    /* must be odd */
2047    if ((inLen & 1) == 0) {
2048       return ECC_BAD_ARG_E;
2049    }
2050
2051    /* init key */
2052    if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k,
2053                      NULL, NULL) != MP_OKAY) {
2054       return MEMORY_E;
2055    }
2056    err = MP_OKAY;
2057
2058    /* check for 4, 6 or 7 */
2059    if (in[0] != 4 && in[0] != 6 && in[0] != 7) {
2060       err = ASN_PARSE_E;
2061    }
2062
2063    /* read data */
2064    if (err == MP_OKAY)
2065        err = mp_read_unsigned_bin(&key->pubkey.x, (byte*)in+1, (inLen-1)>>1);
2066
2067    if (err == MP_OKAY)
2068        err = mp_read_unsigned_bin(&key->pubkey.y, (byte*)in+1+((inLen-1)>>1),
2069                                   (inLen-1)>>1);
2070
2071    if (err == MP_OKAY)
2072        mp_set(&key->pubkey.z, 1);
2073
2074    if (err == MP_OKAY) {
2075      /* determine the idx */
2076       for (x = 0; ecc_sets[x].size != 0; x++) {
2077          if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) {
2078             break;
2079          }
2080       }
2081       if (ecc_sets[x].size == 0) {
2082          err = ASN_PARSE_E;
2083       } else {
2084           /* set the idx */
2085           key->idx  = x;
2086           key->dp = &ecc_sets[x];
2087           key->type = ECC_PUBLICKEY;
2088       }
2089    }
2090
2091    if (err != MP_OKAY) {
2092        mp_clear(&key->pubkey.x);
2093        mp_clear(&key->pubkey.y);
2094        mp_clear(&key->pubkey.z);
2095        mp_clear(&key->k);
2096    }
2097
2098    return err;
2099 }
2100
2101
2102 /* export ecc private key only raw, outLen is in/out size
2103    return MP_OKAY on success */
2104 int ecc_export_private_only(ecc_key* key, byte* out, word32* outLen)
2105 {
2106    word32 numlen;
2107
2108    if (key == NULL || out == NULL || outLen == NULL)
2109        return ECC_BAD_ARG_E;
2110
2111    if (ecc_is_valid_idx(key->idx) == 0) {
2112       return ECC_BAD_ARG_E;
2113    }
2114    numlen = key->dp->size;
2115
2116    if (*outLen < numlen) {
2117       *outLen = numlen;
2118       return BUFFER_E;
2119    }
2120    *outLen = numlen;
2121    XMEMSET(out, 0, *outLen);
2122    return mp_to_unsigned_bin(&key->k, out + (numlen -
2123                                              mp_unsigned_bin_size(&key->k)));
2124 }
2125
2126
2127 /* ecc private key import, public key in ANSI X9.63 format, private raw */
2128 int ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub,
2129                            word32 pubSz, ecc_key* key)
2130 {
2131     int ret = ecc_import_x963(pub, pubSz, key);
2132     if (ret != 0)
2133         return ret;
2134
2135     key->type = ECC_PRIVATEKEY;
2136
2137     return mp_read_unsigned_bin(&key->k, priv, privSz);
2138 }
2139
2140
2141 /* key size in octets */
2142 int ecc_size(ecc_key* key)
2143 {
2144     if (key == NULL) return 0;
2145
2146     return key->dp->size;
2147 }
2148
2149
2150 /* worst case estimate, check actual return from ecc_sign_hash for actual value
2151    of signature size in octets */
2152 int ecc_sig_size(ecc_key* key)
2153 {
2154     int sz = ecc_size(key);
2155     if (sz < 0)
2156         return sz;
2157
2158     return sz * 2 + SIG_HEADER_SZ + 4;  /* (4) worst case estimate */
2159 }
2160
2161
2162 #ifdef FP_ECC
2163
2164 /* fixed point ECC cache */
2165 /* number of entries in the cache */
2166 #ifndef FP_ENTRIES
2167     #define FP_ENTRIES 16
2168 #endif
2169
2170 /* number of bits in LUT */
2171 #ifndef FP_LUT
2172     #define FP_LUT     8U
2173 #endif
2174
2175 #ifdef ECC_SHAMIR
2176     /* Sharmir requires a bigger LUT, TAO */
2177     #if (FP_LUT > 12) || (FP_LUT < 4)
2178         #error FP_LUT must be between 4 and 12 inclusively
2179     #endif
2180 #else
2181     #if (FP_LUT > 12) || (FP_LUT < 2)
2182         #error FP_LUT must be between 2 and 12 inclusively
2183     #endif
2184 #endif
2185
2186
2187 /** Our FP cache */
2188 typedef struct {
2189    ecc_point* g;               /* cached COPY of base point */
2190    ecc_point* LUT[1U<<FP_LUT]; /* fixed point lookup */
2191    mp_int     mu;              /* copy of the montgomery constant */
2192    int        lru_count;       /* amount of times this entry has been used */
2193    int        lock;            /* flag to indicate cache eviction */
2194                                /* permitted (0) or not (1) */
2195 } fp_cache_t;
2196
2197 /* if HAVE_THREAD_LS this cache is per thread, no locking needed */
2198 static THREAD_LS_T fp_cache_t fp_cache[FP_ENTRIES];
2199
2200 #ifndef HAVE_THREAD_LS
2201     static volatile int initMutex = 0;  /* prevent multiple mutex inits */
2202     static CyaSSL_Mutex ecc_fp_lock;
2203 #endif /* HAVE_THREAD_LS */
2204
2205 /* simple table to help direct the generation of the LUT */
2206 static const struct {
2207    int ham, terma, termb;
2208 } lut_orders[] = {
2209    { 0, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 }, { 2, 1, 2 }, { 1, 0, 0 }, { 2, 1, 4 }, { 2, 2, 4 }, { 3, 3, 4 },
2210    { 1, 0, 0 }, { 2, 1, 8 }, { 2, 2, 8 }, { 3, 3, 8 }, { 2, 4, 8 }, { 3, 5, 8 }, { 3, 6, 8 }, { 4, 7, 8 },
2211    { 1, 0, 0 }, { 2, 1, 16 }, { 2, 2, 16 }, { 3, 3, 16 }, { 2, 4, 16 }, { 3, 5, 16 }, { 3, 6, 16 }, { 4, 7, 16 },
2212    { 2, 8, 16 }, { 3, 9, 16 }, { 3, 10, 16 }, { 4, 11, 16 }, { 3, 12, 16 }, { 4, 13, 16 }, { 4, 14, 16 }, { 5, 15, 16 },
2213    { 1, 0, 0 }, { 2, 1, 32 }, { 2, 2, 32 }, { 3, 3, 32 }, { 2, 4, 32 }, { 3, 5, 32 }, { 3, 6, 32 }, { 4, 7, 32 },
2214    { 2, 8, 32 }, { 3, 9, 32 }, { 3, 10, 32 }, { 4, 11, 32 }, { 3, 12, 32 }, { 4, 13, 32 }, { 4, 14, 32 }, { 5, 15, 32 },
2215    { 2, 16, 32 }, { 3, 17, 32 }, { 3, 18, 32 }, { 4, 19, 32 }, { 3, 20, 32 }, { 4, 21, 32 }, { 4, 22, 32 }, { 5, 23, 32 },
2216    { 3, 24, 32 }, { 4, 25, 32 }, { 4, 26, 32 }, { 5, 27, 32 }, { 4, 28, 32 }, { 5, 29, 32 }, { 5, 30, 32 }, { 6, 31, 32 },
2217 #if FP_LUT > 6
2218    { 1, 0, 0 }, { 2, 1, 64 }, { 2, 2, 64 }, { 3, 3, 64 }, { 2, 4, 64 }, { 3, 5, 64 }, { 3, 6, 64 }, { 4, 7, 64 },
2219    { 2, 8, 64 }, { 3, 9, 64 }, { 3, 10, 64 }, { 4, 11, 64 }, { 3, 12, 64 }, { 4, 13, 64 }, { 4, 14, 64 }, { 5, 15, 64 },
2220    { 2, 16, 64 }, { 3, 17, 64 }, { 3, 18, 64 }, { 4, 19, 64 }, { 3, 20, 64 }, { 4, 21, 64 }, { 4, 22, 64 }, { 5, 23, 64 },
2221    { 3, 24, 64 }, { 4, 25, 64 }, { 4, 26, 64 }, { 5, 27, 64 }, { 4, 28, 64 }, { 5, 29, 64 }, { 5, 30, 64 }, { 6, 31, 64 },
2222    { 2, 32, 64 }, { 3, 33, 64 }, { 3, 34, 64 }, { 4, 35, 64 }, { 3, 36, 64 }, { 4, 37, 64 }, { 4, 38, 64 }, { 5, 39, 64 },
2223    { 3, 40, 64 }, { 4, 41, 64 }, { 4, 42, 64 }, { 5, 43, 64 }, { 4, 44, 64 }, { 5, 45, 64 }, { 5, 46, 64 }, { 6, 47, 64 },
2224    { 3, 48, 64 }, { 4, 49, 64 }, { 4, 50, 64 }, { 5, 51, 64 }, { 4, 52, 64 }, { 5, 53, 64 }, { 5, 54, 64 }, { 6, 55, 64 },
2225    { 4, 56, 64 }, { 5, 57, 64 }, { 5, 58, 64 }, { 6, 59, 64 }, { 5, 60, 64 }, { 6, 61, 64 }, { 6, 62, 64 }, { 7, 63, 64 },
2226 #if FP_LUT > 7
2227    { 1, 0, 0 }, { 2, 1, 128 }, { 2, 2, 128 }, { 3, 3, 128 }, { 2, 4, 128 }, { 3, 5, 128 }, { 3, 6, 128 }, { 4, 7, 128 },
2228    { 2, 8, 128 }, { 3, 9, 128 }, { 3, 10, 128 }, { 4, 11, 128 }, { 3, 12, 128 }, { 4, 13, 128 }, { 4, 14, 128 }, { 5, 15, 128 },
2229    { 2, 16, 128 }, { 3, 17, 128 }, { 3, 18, 128 }, { 4, 19, 128 }, { 3, 20, 128 }, { 4, 21, 128 }, { 4, 22, 128 }, { 5, 23, 128 },
2230    { 3, 24, 128 }, { 4, 25, 128 }, { 4, 26, 128 }, { 5, 27, 128 }, { 4, 28, 128 }, { 5, 29, 128 }, { 5, 30, 128 }, { 6, 31, 128 },
2231    { 2, 32, 128 }, { 3, 33, 128 }, { 3, 34, 128 }, { 4, 35, 128 }, { 3, 36, 128 }, { 4, 37, 128 }, { 4, 38, 128 }, { 5, 39, 128 },
2232    { 3, 40, 128 }, { 4, 41, 128 }, { 4, 42, 128 }, { 5, 43, 128 }, { 4, 44, 128 }, { 5, 45, 128 }, { 5, 46, 128 }, { 6, 47, 128 },
2233    { 3, 48, 128 }, { 4, 49, 128 }, { 4, 50, 128 }, { 5, 51, 128 }, { 4, 52, 128 }, { 5, 53, 128 }, { 5, 54, 128 }, { 6, 55, 128 },
2234    { 4, 56, 128 }, { 5, 57, 128 }, { 5, 58, 128 }, { 6, 59, 128 }, { 5, 60, 128 }, { 6, 61, 128 }, { 6, 62, 128 }, { 7, 63, 128 },
2235    { 2, 64, 128 }, { 3, 65, 128 }, { 3, 66, 128 }, { 4, 67, 128 }, { 3, 68, 128 }, { 4, 69, 128 }, { 4, 70, 128 }, { 5, 71, 128 },
2236    { 3, 72, 128 }, { 4, 73, 128 }, { 4, 74, 128 }, { 5, 75, 128 }, { 4, 76, 128 }, { 5, 77, 128 }, { 5, 78, 128 }, { 6, 79, 128 },
2237    { 3, 80, 128 }, { 4, 81, 128 }, { 4, 82, 128 }, { 5, 83, 128 }, { 4, 84, 128 }, { 5, 85, 128 }, { 5, 86, 128 }, { 6, 87, 128 },
2238    { 4, 88, 128 }, { 5, 89, 128 }, { 5, 90, 128 }, { 6, 91, 128 }, { 5, 92, 128 }, { 6, 93, 128 }, { 6, 94, 128 }, { 7, 95, 128 },
2239    { 3, 96, 128 }, { 4, 97, 128 }, { 4, 98, 128 }, { 5, 99, 128 }, { 4, 100, 128 }, { 5, 101, 128 }, { 5, 102, 128 }, { 6, 103, 128 },
2240    { 4, 104, 128 }, { 5, 105, 128 }, { 5, 106, 128 }, { 6, 107, 128 }, { 5, 108, 128 }, { 6, 109, 128 }, { 6, 110, 128 }, { 7, 111, 128 },
2241    { 4, 112, 128 }, { 5, 113, 128 }, { 5, 114, 128 }, { 6, 115, 128 }, { 5, 116, 128 }, { 6, 117, 128 }, { 6, 118, 128 }, { 7, 119, 128 },
2242    { 5, 120, 128 }, { 6, 121, 128 }, { 6, 122, 128 }, { 7, 123, 128 }, { 6, 124, 128 }, { 7, 125, 128 }, { 7, 126, 128 }, { 8, 127, 128 },
2243 #if FP_LUT > 8
2244    { 1, 0, 0 }, { 2, 1, 256 }, { 2, 2, 256 }, { 3, 3, 256 }, { 2, 4, 256 }, { 3, 5, 256 }, { 3, 6, 256 }, { 4, 7, 256 },
2245    { 2, 8, 256 }, { 3, 9, 256 }, { 3, 10, 256 }, { 4, 11, 256 }, { 3, 12, 256 }, { 4, 13, 256 }, { 4, 14, 256 }, { 5, 15, 256 },
2246    { 2, 16, 256 }, { 3, 17, 256 }, { 3, 18, 256 }, { 4, 19, 256 }, { 3, 20, 256 }, { 4, 21, 256 }, { 4, 22, 256 }, { 5, 23, 256 },
2247    { 3, 24, 256 }, { 4, 25, 256 }, { 4, 26, 256 }, { 5, 27, 256 }, { 4, 28, 256 }, { 5, 29, 256 }, { 5, 30, 256 }, { 6, 31, 256 },
2248    { 2, 32, 256 }, { 3, 33, 256 }, { 3, 34, 256 }, { 4, 35, 256 }, { 3, 36, 256 }, { 4, 37, 256 }, { 4, 38, 256 }, { 5, 39, 256 },
2249    { 3, 40, 256 }, { 4, 41, 256 }, { 4, 42, 256 }, { 5, 43, 256 }, { 4, 44, 256 }, { 5, 45, 256 }, { 5, 46, 256 }, { 6, 47, 256 },
2250    { 3, 48, 256 }, { 4, 49, 256 }, { 4, 50, 256 }, { 5, 51, 256 }, { 4, 52, 256 }, { 5, 53, 256 }, { 5, 54, 256 }, { 6, 55, 256 },
2251    { 4, 56, 256 }, { 5, 57, 256 }, { 5, 58, 256 }, { 6, 59, 256 }, { 5, 60, 256 }, { 6, 61, 256 }, { 6, 62, 256 }, { 7, 63, 256 },
2252    { 2, 64, 256 }, { 3, 65, 256 }, { 3, 66, 256 }, { 4, 67, 256 }, { 3, 68, 256 }, { 4, 69, 256 }, { 4, 70, 256 }, { 5, 71, 256 },
2253    { 3, 72, 256 }, { 4, 73, 256 }, { 4, 74, 256 }, { 5, 75, 256 }, { 4, 76, 256 }, { 5, 77, 256 }, { 5, 78, 256 }, { 6, 79, 256 },
2254    { 3, 80, 256 }, { 4, 81, 256 }, { 4, 82, 256 }, { 5, 83, 256 }, { 4, 84, 256 }, { 5, 85, 256 }, { 5, 86, 256 }, { 6, 87, 256 },
2255    { 4, 88, 256 }, { 5, 89, 256 }, { 5, 90, 256 }, { 6, 91, 256 }, { 5, 92, 256 }, { 6, 93, 256 }, { 6, 94, 256 }, { 7, 95, 256 },
2256    { 3, 96, 256 }, { 4, 97, 256 }, { 4, 98, 256 }, { 5, 99, 256 }, { 4, 100, 256 }, { 5, 101, 256 }, { 5, 102, 256 }, { 6, 103, 256 },
2257    { 4, 104, 256 }, { 5, 105, 256 }, { 5, 106, 256 }, { 6, 107, 256 }, { 5, 108, 256 }, { 6, 109, 256 }, { 6, 110, 256 }, { 7, 111, 256 },
2258    { 4, 112, 256 }, { 5, 113, 256 }, { 5, 114, 256 }, { 6, 115, 256 }, { 5, 116, 256 }, { 6, 117, 256 }, { 6, 118, 256 }, { 7, 119, 256 },
2259    { 5, 120, 256 }, { 6, 121, 256 }, { 6, 122, 256 }, { 7, 123, 256 }, { 6, 124, 256 }, { 7, 125, 256 }, { 7, 126, 256 }, { 8, 127, 256 },
2260    { 2, 128, 256 }, { 3, 129, 256 }, { 3, 130, 256 }, { 4, 131, 256 }, { 3, 132, 256 }, { 4, 133, 256 }, { 4, 134, 256 }, { 5, 135, 256 },
2261    { 3, 136, 256 }, { 4, 137, 256 }, { 4, 138, 256 }, { 5, 139, 256 }, { 4, 140, 256 }, { 5, 141, 256 }, { 5, 142, 256 }, { 6, 143, 256 },
2262    { 3, 144, 256 }, { 4, 145, 256 }, { 4, 146, 256 }, { 5, 147, 256 }, { 4, 148, 256 }, { 5, 149, 256 }, { 5, 150, 256 }, { 6, 151, 256 },
2263    { 4, 152, 256 }, { 5, 153, 256 }, { 5, 154, 256 }, { 6, 155, 256 }, { 5, 156, 256 }, { 6, 157, 256 }, { 6, 158, 256 }, { 7, 159, 256 },
2264    { 3, 160, 256 }, { 4, 161, 256 }, { 4, 162, 256 }, { 5, 163, 256 }, { 4, 164, 256 }, { 5, 165, 256 }, { 5, 166, 256 }, { 6, 167, 256 },
2265    { 4, 168, 256 }, { 5, 169, 256 }, { 5, 170, 256 }, { 6, 171, 256 }, { 5, 172, 256 }, { 6, 173, 256 }, { 6, 174, 256 }, { 7, 175, 256 },
2266    { 4, 176, 256 }, { 5, 177, 256 }, { 5, 178, 256 }, { 6, 179, 256 }, { 5, 180, 256 }, { 6, 181, 256 }, { 6, 182, 256 }, { 7, 183, 256 },
2267    { 5, 184, 256 }, { 6, 185, 256 }, { 6, 186, 256 }, { 7, 187, 256 }, { 6, 188, 256 }, { 7, 189, 256 }, { 7, 190, 256 }, { 8, 191, 256 },
2268    { 3, 192, 256 }, { 4, 193, 256 }, { 4, 194, 256 }, { 5, 195, 256 }, { 4, 196, 256 }, { 5, 197, 256 }, { 5, 198, 256 }, { 6, 199, 256 },
2269    { 4, 200, 256 }, { 5, 201, 256 }, { 5, 202, 256 }, { 6, 203, 256 }, { 5, 204, 256 }, { 6, 205, 256 }, { 6, 206, 256 }, { 7, 207, 256 },
2270    { 4, 208, 256 }, { 5, 209, 256 }, { 5, 210, 256 }, { 6, 211, 256 }, { 5, 212, 256 }, { 6, 213, 256 }, { 6, 214, 256 }, { 7, 215, 256 },
2271    { 5, 216, 256 }, { 6, 217, 256 }, { 6, 218, 256 }, { 7, 219, 256 }, { 6, 220, 256 }, { 7, 221, 256 }, { 7, 222, 256 }, { 8, 223, 256 },
2272    { 4, 224, 256 }, { 5, 225, 256 }, { 5, 226, 256 }, { 6, 227, 256 }, { 5, 228, 256 }, { 6, 229, 256 }, { 6, 230, 256 }, { 7, 231, 256 },
2273    { 5, 232, 256 }, { 6, 233, 256 }, { 6, 234, 256 }, { 7, 235, 256 }, { 6, 236, 256 }, { 7, 237, 256 }, { 7, 238, 256 }, { 8, 239, 256 },
2274    { 5, 240, 256 }, { 6, 241, 256 }, { 6, 242, 256 }, { 7, 243, 256 }, { 6, 244, 256 }, { 7, 245, 256 }, { 7, 246, 256 }, { 8, 247, 256 },
2275    { 6, 248, 256 }, { 7, 249, 256 }, { 7, 250, 256 }, { 8, 251, 256 }, { 7, 252, 256 }, { 8, 253, 256 }, { 8, 254, 256 }, { 9, 255, 256 },
2276 #if FP_LUT > 9
2277    { 1, 0, 0 }, { 2, 1, 512 }, { 2, 2, 512 }, { 3, 3, 512 }, { 2, 4, 512 }, { 3, 5, 512 }, { 3, 6, 512 }, { 4, 7, 512 },
2278    { 2, 8, 512 }, { 3, 9, 512 }, { 3, 10, 512 }, { 4, 11, 512 }, { 3, 12, 512 }, { 4, 13, 512 }, { 4, 14, 512 }, { 5, 15, 512 },
2279    { 2, 16, 512 }, { 3, 17, 512 }, { 3, 18, 512 }, { 4, 19, 512 }, { 3, 20, 512 }, { 4, 21, 512 }, { 4, 22, 512 }, { 5, 23, 512 },
2280    { 3, 24, 512 }, { 4, 25, 512 }, { 4, 26, 512 }, { 5, 27, 512 }, { 4, 28, 512 }, { 5, 29, 512 }, { 5, 30, 512 }, { 6, 31, 512 },
2281    { 2, 32, 512 }, { 3, 33, 512 }, { 3, 34, 512 }, { 4, 35, 512 }, { 3, 36, 512 }, { 4, 37, 512 }, { 4, 38, 512 }, { 5, 39, 512 },
2282    { 3, 40, 512 }, { 4, 41, 512 }, { 4, 42, 512 }, { 5, 43, 512 }, { 4, 44, 512 }, { 5, 45, 512 }, { 5, 46, 512 }, { 6, 47, 512 },
2283    { 3, 48, 512 }, { 4, 49, 512 }, { 4, 50, 512 }, { 5, 51, 512 }, { 4, 52, 512 }, { 5, 53, 512 }, { 5, 54, 512 }, { 6, 55, 512 },
2284    { 4, 56, 512 }, { 5, 57, 512 }, { 5, 58, 512 }, { 6, 59, 512 }, { 5, 60, 512 }, { 6, 61, 512 }, { 6, 62, 512 }, { 7, 63, 512 },
2285    { 2, 64, 512 }, { 3, 65, 512 }, { 3, 66, 512 }, { 4, 67, 512 }, { 3, 68, 512 }, { 4, 69, 512 }, { 4, 70, 512 }, { 5, 71, 512 },
2286    { 3, 72, 512 }, { 4, 73, 512 }, { 4, 74, 512 }, { 5, 75, 512 }, { 4, 76, 512 }, { 5, 77, 512 }, { 5, 78, 512 }, { 6, 79, 512 },
2287    { 3, 80, 512 }, { 4, 81, 512 }, { 4, 82, 512 }, { 5, 83, 512 }, { 4, 84, 512 }, { 5, 85, 512 }, { 5, 86, 512 }, { 6, 87, 512 },
2288    { 4, 88, 512 }, { 5, 89, 512 }, { 5, 90, 512 }, { 6, 91, 512 }, { 5, 92, 512 }, { 6, 93, 512 }, { 6, 94, 512 }, { 7, 95, 512 },
2289    { 3, 96, 512 }, { 4, 97, 512 }, { 4, 98, 512 }, { 5, 99, 512 }, { 4, 100, 512 }, { 5, 101, 512 }, { 5, 102, 512 }, { 6, 103, 512 },
2290    { 4, 104, 512 }, { 5, 105, 512 }, { 5, 106, 512 }, { 6, 107, 512 }, { 5, 108, 512 }, { 6, 109, 512 }, { 6, 110, 512 }, { 7, 111, 512 },
2291    { 4, 112, 512 }, { 5, 113, 512 }, { 5, 114, 512 }, { 6, 115, 512 }, { 5, 116, 512 }, { 6, 117, 512 }, { 6, 118, 512 }, { 7, 119, 512 },
2292    { 5, 120, 512 }, { 6, 121, 512 }, { 6, 122, 512 }, { 7, 123, 512 }, { 6, 124, 512 }, { 7, 125, 512 }, { 7, 126, 512 }, { 8, 127, 512 },
2293    { 2, 128, 512 }, { 3, 129, 512 }, { 3, 130, 512 }, { 4, 131, 512 }, { 3, 132, 512 }, { 4, 133, 512 }, { 4, 134, 512 }, { 5, 135, 512 },
2294    { 3, 136, 512 }, { 4, 137, 512 }, { 4, 138, 512 }, { 5, 139, 512 }, { 4, 140, 512 }, { 5, 141, 512 }, { 5, 142, 512 }, { 6, 143, 512 },
2295    { 3, 144, 512 }, { 4, 145, 512 }, { 4, 146, 512 }, { 5, 147, 512 }, { 4, 148, 512 }, { 5, 149, 512 }, { 5, 150, 512 }, { 6, 151, 512 },
2296    { 4, 152, 512 }, { 5, 153, 512 }, { 5, 154, 512 }, { 6, 155, 512 }, { 5, 156, 512 }, { 6, 157, 512 }, { 6, 158, 512 }, { 7, 159, 512 },
2297    { 3, 160, 512 }, { 4, 161, 512 }, { 4, 162, 512 }, { 5, 163, 512 }, { 4, 164, 512 }, { 5, 165, 512 }, { 5, 166, 512 }, { 6, 167, 512 },
2298    { 4, 168, 512 }, { 5, 169, 512 }, { 5, 170, 512 }, { 6, 171, 512 }, { 5, 172, 512 }, { 6, 173, 512 }, { 6, 174, 512 }, { 7, 175, 512 },
2299    { 4, 176, 512 }, { 5, 177, 512 }, { 5, 178, 512 }, { 6, 179, 512 }, { 5, 180, 512 }, { 6, 181, 512 }, { 6, 182, 512 }, { 7, 183, 512 },
2300    { 5, 184, 512 }, { 6, 185, 512 }, { 6, 186, 512 }, { 7, 187, 512 }, { 6, 188, 512 }, { 7, 189, 512 }, { 7, 190, 512 }, { 8, 191, 512 },
2301    { 3, 192, 512 }, { 4, 193, 512 }, { 4, 194, 512 }, { 5, 195, 512 }, { 4, 196, 512 }, { 5, 197, 512 }, { 5, 198, 512 }, { 6, 199, 512 },
2302    { 4, 200, 512 }, { 5, 201, 512 }, { 5, 202, 512 }, { 6, 203, 512 }, { 5, 204, 512 }, { 6, 205, 512 }, { 6, 206, 512 }, { 7, 207, 512 },
2303    { 4, 208, 512 }, { 5, 209, 512 }, { 5, 210, 512 }, { 6, 211, 512 }, { 5, 212, 512 }, { 6, 213, 512 }, { 6, 214, 512 }, { 7, 215, 512 },
2304    { 5, 216, 512 }, { 6, 217, 512 }, { 6, 218, 512 }, { 7, 219, 512 }, { 6, 220, 512 }, { 7, 221, 512 }, { 7, 222, 512 }, { 8, 223, 512 },
2305    { 4, 224, 512 }, { 5, 225, 512 }, { 5, 226, 512 }, { 6, 227, 512 }, { 5, 228, 512 }, { 6, 229, 512 }, { 6, 230, 512 }, { 7, 231, 512 },
2306    { 5, 232, 512 }, { 6, 233, 512 }, { 6, 234, 512 }, { 7, 235, 512 }, { 6, 236, 512 }, { 7, 237, 512 }, { 7, 238, 512 }, { 8, 239, 512 },
2307    { 5, 240, 512 }, { 6, 241, 512 }, { 6, 242, 512 }, { 7, 243, 512 }, { 6, 244, 512 }, { 7, 245, 512 }, { 7, 246, 512 }, { 8, 247, 512 },
2308    { 6, 248, 512 }, { 7, 249, 512 }, { 7, 250, 512 }, { 8, 251, 512 }, { 7, 252, 512 }, { 8, 253, 512 }, { 8, 254, 512 }, { 9, 255, 512 },
2309    { 2, 256, 512 }, { 3, 257, 512 }, { 3, 258, 512 }, { 4, 259, 512 }, { 3, 260, 512 }, { 4, 261, 512 }, { 4, 262, 512 }, { 5, 263, 512 },
2310    { 3, 264, 512 }, { 4, 265, 512 }, { 4, 266, 512 }, { 5, 267, 512 }, { 4, 268, 512 }, { 5, 269, 512 }, { 5, 270, 512 }, { 6, 271, 512 },
2311    { 3, 272, 512 }, { 4, 273, 512 }, { 4, 274, 512 }, { 5, 275, 512 }, { 4, 276, 512 }, { 5, 277, 512 }, { 5, 278, 512 }, { 6, 279, 512 },
2312    { 4, 280, 512 }, { 5, 281, 512 }, { 5, 282, 512 }, { 6, 283, 512 }, { 5, 284, 512 }, { 6, 285, 512 }, { 6, 286, 512 }, { 7, 287, 512 },
2313    { 3, 288, 512 }, { 4, 289, 512 }, { 4, 290, 512 }, { 5, 291, 512 }, { 4, 292, 512 }, { 5, 293, 512 }, { 5, 294, 512 }, { 6, 295, 512 },
2314    { 4, 296, 512 }, { 5, 297, 512 }, { 5, 298, 512 }, { 6, 299, 512 }, { 5, 300, 512 }, { 6, 301, 512 }, { 6, 302, 512 }, { 7, 303, 512 },
2315    { 4, 304, 512 }, { 5, 305, 512 }, { 5, 306, 512 }, { 6, 307, 512 }, { 5, 308, 512 }, { 6, 309, 512 }, { 6, 310, 512 }, { 7, 311, 512 },
2316    { 5, 312, 512 }, { 6, 313, 512 }, { 6, 314, 512 }, { 7, 315, 512 }, { 6, 316, 512 }, { 7, 317, 512 }, { 7, 318, 512 }, { 8, 319, 512 },
2317    { 3, 320, 512 }, { 4, 321, 512 }, { 4, 322, 512 }, { 5, 323, 512 }, { 4, 324, 512 }, { 5, 325, 512 }, { 5, 326, 512 }, { 6, 327, 512 },
2318    { 4, 328, 512 }, { 5, 329, 512 }, { 5, 330, 512 }, { 6, 331, 512 }, { 5, 332, 512 }, { 6, 333, 512 }, { 6, 334, 512 }, { 7, 335, 512 },
2319    { 4, 336, 512 }, { 5, 337, 512 }, { 5, 338, 512 }, { 6, 339, 512 }, { 5, 340, 512 }, { 6, 341, 512 }, { 6, 342, 512 }, { 7, 343, 512 },
2320    { 5, 344, 512 }, { 6, 345, 512 }, { 6, 346, 512 }, { 7, 347, 512 }, { 6, 348, 512 }, { 7, 349, 512 }, { 7, 350, 512 }, { 8, 351, 512 },
2321    { 4, 352, 512 }, { 5, 353, 512 }, { 5, 354, 512 }, { 6, 355, 512 }, { 5, 356, 512 }, { 6, 357, 512 }, { 6, 358, 512 }, { 7, 359, 512 },
2322    { 5, 360, 512 }, { 6, 361, 512 }, { 6, 362, 512 }, { 7, 363, 512 }, { 6, 364, 512 }, { 7, 365, 512 }, { 7, 366, 512 }, { 8, 367, 512 },
2323    { 5, 368, 512 }, { 6, 369, 512 }, { 6, 370, 512 }, { 7, 371, 512 }, { 6, 372, 512 }, { 7, 373, 512 }, { 7, 374, 512 }, { 8, 375, 512 },
2324    { 6, 376, 512 }, { 7, 377, 512 }, { 7, 378, 512 }, { 8, 379, 512 }, { 7, 380, 512 }, { 8, 381, 512 }, { 8, 382, 512 }, { 9, 383, 512 },
2325    { 3, 384, 512 }, { 4, 385, 512 }, { 4, 386, 512 }, { 5, 387, 512 }, { 4, 388, 512 }, { 5, 389, 512 }, { 5, 390, 512 }, { 6, 391, 512 },
2326    { 4, 392, 512 }, { 5, 393, 512 }, { 5, 394, 512 }, { 6, 395, 512 }, { 5, 396, 512 }, { 6, 397, 512 }, { 6, 398, 512 }, { 7, 399, 512 },
2327    { 4, 400, 512 }, { 5, 401, 512 }, { 5, 402, 512 }, { 6, 403, 512 }, { 5, 404, 512 }, { 6, 405, 512 }, { 6, 406, 512 }, { 7, 407, 512 },
2328    { 5, 408, 512 }, { 6, 409, 512 }, { 6, 410, 512 }, { 7, 411, 512 }, { 6, 412, 512 }, { 7, 413, 512 }, { 7, 414, 512 }, { 8, 415, 512 },
2329    { 4, 416, 512 }, { 5, 417, 512 }, { 5, 418, 512 }, { 6, 419, 512 }, { 5, 420, 512 }, { 6, 421, 512 }, { 6, 422, 512 }, { 7, 423, 512 },
2330    { 5, 424, 512 }, { 6, 425, 512 }, { 6, 426, 512 }, { 7, 427, 512 }, { 6, 428, 512 }, { 7, 429, 512 }, { 7, 430, 512 }, { 8, 431, 512 },
2331    { 5, 432, 512 }, { 6, 433, 512 }, { 6, 434, 512 }, { 7, 435, 512 }, { 6, 436, 512 }, { 7, 437, 512 }, { 7, 438, 512 }, { 8, 439, 512 },
2332    { 6, 440, 512 }, { 7, 441, 512 }, { 7, 442, 512 }, { 8, 443, 512 }, { 7, 444, 512 }, { 8, 445, 512 }, { 8, 446, 512 }, { 9, 447, 512 },
2333    { 4, 448, 512 }, { 5, 449, 512 }, { 5, 450, 512 }, { 6, 451, 512 }, { 5, 452, 512 }, { 6, 453, 512 }, { 6, 454, 512 }, { 7, 455, 512 },
2334    { 5, 456, 512 }, { 6, 457, 512 }, { 6, 458, 512 }, { 7, 459, 512 }, { 6, 460, 512 }, { 7, 461, 512 }, { 7, 462, 512 }, { 8, 463, 512 },
2335    { 5, 464, 512 }, { 6, 465, 512 }, { 6, 466, 512 }, { 7, 467, 512 }, { 6, 468, 512 }, { 7, 469, 512 }, { 7, 470, 512 }, { 8, 471, 512 },
2336    { 6, 472, 512 }, { 7, 473, 512 }, { 7, 474, 512 }, { 8, 475, 512 }, { 7, 476, 512 }, { 8, 477, 512 }, { 8, 478, 512 }, { 9, 479, 512 },
2337    { 5, 480, 512 }, { 6, 481, 512 }, { 6, 482, 512 }, { 7, 483, 512 }, { 6, 484, 512 }, { 7, 485, 512 }, { 7, 486, 512 }, { 8, 487, 512 },
2338    { 6, 488, 512 }, { 7, 489, 512 }, { 7, 490, 512 }, { 8, 491, 512 }, { 7, 492, 512 }, { 8, 493, 512 }, { 8, 494, 512 }, { 9, 495, 512 },
2339    { 6, 496, 512 }, { 7, 497, 512 }, { 7, 498, 512 }, { 8, 499, 512 }, { 7, 500, 512 }, { 8, 501, 512 }, { 8, 502, 512 }, { 9, 503, 512 },
2340    { 7, 504, 512 }, { 8, 505, 512 }, { 8, 506, 512 }, { 9, 507, 512 }, { 8, 508, 512 }, { 9, 509, 512 }, { 9, 510, 512 }, { 10, 511, 512 },
2341 #if FP_LUT > 10
2342    { 1, 0, 0 }, { 2, 1, 1024 }, { 2, 2, 1024 }, { 3, 3, 1024 }, { 2, 4, 1024 }, { 3, 5, 1024 }, { 3, 6, 1024 }, { 4, 7, 1024 },
2343    { 2, 8, 1024 }, { 3, 9, 1024 }, { 3, 10, 1024 }, { 4, 11, 1024 }, { 3, 12, 1024 }, { 4, 13, 1024 }, { 4, 14, 1024 }, { 5, 15, 1024 },
2344    { 2, 16, 1024 }, { 3, 17, 1024 }, { 3, 18, 1024 }, { 4, 19, 1024 }, { 3, 20, 1024 }, { 4, 21, 1024 }, { 4, 22, 1024 }, { 5, 23, 1024 },
2345    { 3, 24, 1024 }, { 4, 25, 1024 }, { 4, 26, 1024 }, { 5, 27, 1024 }, { 4, 28, 1024 }, { 5, 29, 1024 }, { 5, 30, 1024 }, { 6, 31, 1024 },
2346    { 2, 32, 1024 }, { 3, 33, 1024 }, { 3, 34, 1024 }, { 4, 35, 1024 }, { 3, 36, 1024 }, { 4, 37, 1024 }, { 4, 38, 1024 }, { 5, 39, 1024 },
2347    { 3, 40, 1024 }, { 4, 41, 1024 }, { 4, 42, 1024 }, { 5, 43, 1024 }, { 4, 44, 1024 }, { 5, 45, 1024 }, { 5, 46, 1024 }, { 6, 47, 1024 },
2348    { 3, 48, 1024 }, { 4, 49, 1024 }, { 4, 50, 1024 }, { 5, 51, 1024 }, { 4, 52, 1024 }, { 5, 53, 1024 }, { 5, 54, 1024 }, { 6, 55, 1024 },
2349    { 4, 56, 1024 }, { 5, 57, 1024 }, { 5, 58, 1024 }, { 6, 59, 1024 }, { 5, 60, 1024 }, { 6, 61, 1024 }, { 6, 62, 1024 }, { 7, 63, 1024 },
2350    { 2, 64, 1024 }, { 3, 65, 1024 }, { 3, 66, 1024 }, { 4, 67, 1024 }, { 3, 68, 1024 }, { 4, 69, 1024 }, { 4, 70, 1024 }, { 5, 71, 1024 },
2351    { 3, 72, 1024 }, { 4, 73, 1024 }, { 4, 74, 1024 }, { 5, 75, 1024 }, { 4, 76, 1024 }, { 5, 77, 1024 }, { 5, 78, 1024 }, { 6, 79, 1024 },
2352    { 3, 80, 1024 }, { 4, 81, 1024 }, { 4, 82, 1024 }, { 5, 83, 1024 }, { 4, 84, 1024 }, { 5, 85, 1024 }, { 5, 86, 1024 }, { 6, 87, 1024 },
2353    { 4, 88, 1024 }, { 5, 89, 1024 }, { 5, 90, 1024 }, { 6, 91, 1024 }, { 5, 92, 1024 }, { 6, 93, 1024 }, { 6, 94, 1024 }, { 7, 95, 1024 },
2354    { 3, 96, 1024 }, { 4, 97, 1024 }, { 4, 98, 1024 }, { 5, 99, 1024 }, { 4, 100, 1024 }, { 5, 101, 1024 }, { 5, 102, 1024 }, { 6, 103, 1024 },
2355    { 4, 104, 1024 }, { 5, 105, 1024 }, { 5, 106, 1024 }, { 6, 107, 1024 }, { 5, 108, 1024 }, { 6, 109, 1024 }, { 6, 110, 1024 }, { 7, 111, 1024 },
2356    { 4, 112, 1024 }, { 5, 113, 1024 }, { 5, 114, 1024 }, { 6, 115, 1024 }, { 5, 116, 1024 }, { 6, 117, 1024 }, { 6, 118, 1024 }, { 7, 119, 1024 },
2357    { 5, 120, 1024 }, { 6, 121, 1024 }, { 6, 122, 1024 }, { 7, 123, 1024 }, { 6, 124, 1024 }, { 7, 125, 1024 }, { 7, 126, 1024 }, { 8, 127, 1024 },
2358    { 2, 128, 1024 }, { 3, 129, 1024 }, { 3, 130, 1024 }, { 4, 131, 1024 }, { 3, 132, 1024 }, { 4, 133, 1024 }, { 4, 134, 1024 }, { 5, 135, 1024 },
2359    { 3, 136, 1024 }, { 4, 137, 1024 }, { 4, 138, 1024 }, { 5, 139, 1024 }, { 4, 140, 1024 }, { 5, 141, 1024 }, { 5, 142, 1024 }, { 6, 143, 1024 },
2360    { 3, 144, 1024 }, { 4, 145, 1024 }, { 4, 146, 1024 }, { 5, 147, 1024 }, { 4, 148, 1024 }, { 5, 149, 1024 }, { 5, 150, 1024 }, { 6, 151, 1024 },
2361    { 4, 152, 1024 }, { 5, 153, 1024 }, { 5, 154, 1024 }, { 6, 155, 1024 }, { 5, 156, 1024 }, { 6, 157, 1024 }, { 6, 158, 1024 }, { 7, 159, 1024 },
2362    { 3, 160, 1024 }, { 4, 161, 1024 }, { 4, 162, 1024 }, { 5, 163, 1024 }, { 4, 164, 1024 }, { 5, 165, 1024 }, { 5, 166, 1024 }, { 6, 167, 1024 },
2363    { 4, 168, 1024 }, { 5, 169, 1024 }, { 5, 170, 1024 }, { 6, 171, 1024 }, { 5, 172, 1024 }, { 6, 173, 1024 }, { 6, 174, 1024 }, { 7, 175, 1024 },
2364    { 4, 176, 1024 }, { 5, 177, 1024 }, { 5, 178, 1024 }, { 6, 179, 1024 }, { 5, 180, 1024 }, { 6, 181, 1024 }, { 6, 182, 1024 }, { 7, 183, 1024 },
2365    { 5, 184, 1024 }, { 6, 185, 1024 }, { 6, 186, 1024 }, { 7, 187, 1024 }, { 6, 188, 1024 }, { 7, 189, 1024 }, { 7, 190, 1024 }, { 8, 191, 1024 },
2366    { 3, 192, 1024 }, { 4, 193, 1024 }, { 4, 194, 1024 }, { 5, 195, 1024 }, { 4, 196, 1024 }, { 5, 197, 1024 }, { 5, 198, 1024 }, { 6, 199, 1024 },
2367    { 4, 200, 1024 }, { 5, 201, 1024 }, { 5, 202, 1024 }, { 6, 203, 1024 }, { 5, 204, 1024 }, { 6, 205, 1024 }, { 6, 206, 1024 }, { 7, 207, 1024 },
2368    { 4, 208, 1024 }, { 5, 209, 1024 }, { 5, 210, 1024 }, { 6, 211, 1024 }, { 5, 212, 1024 }, { 6, 213, 1024 }, { 6, 214, 1024 }, { 7, 215, 1024 },
2369    { 5, 216, 1024 }, { 6, 217, 1024 }, { 6, 218, 1024 }, { 7, 219, 1024 }, { 6, 220, 1024 }, { 7, 221, 1024 }, { 7, 222, 1024 }, { 8, 223, 1024 },
2370    { 4, 224, 1024 }, { 5, 225, 1024 }, { 5, 226, 1024 }, { 6, 227, 1024 }, { 5, 228, 1024 }, { 6, 229, 1024 }, { 6, 230, 1024 }, { 7, 231, 1024 },
2371    { 5, 232, 1024 }, { 6, 233, 1024 }, { 6, 234, 1024 }, { 7, 235, 1024 }, { 6, 236, 1024 }, { 7, 237, 1024 }, { 7, 238, 1024 }, { 8, 239, 1024 },
2372    { 5, 240, 1024 }, { 6, 241, 1024 }, { 6, 242, 1024 }, { 7, 243, 1024 }, { 6, 244, 1024 }, { 7, 245, 1024 }, { 7, 246, 1024 }, { 8, 247, 1024 },
2373    { 6, 248, 1024 }, { 7, 249, 1024 }, { 7, 250, 1024 }, { 8, 251, 1024 }, { 7, 252, 1024 }, { 8, 253, 1024 }, { 8, 254, 1024 }, { 9, 255, 1024 },
2374    { 2, 256, 1024 }, { 3, 257, 1024 }, { 3, 258, 1024 }, { 4, 259, 1024 }, { 3, 260, 1024 }, { 4, 261, 1024 }, { 4, 262, 1024 }, { 5, 263, 1024 },
2375    { 3, 264, 1024 }, { 4, 265, 1024 }, { 4, 266, 1024 }, { 5, 267, 1024 }, { 4, 268, 1024 }, { 5, 269, 1024 }, { 5, 270, 1024 }, { 6, 271, 1024 },
2376    { 3, 272, 1024 }, { 4, 273, 1024 }, { 4, 274, 1024 }, { 5, 275, 1024 }, { 4, 276, 1024 }, { 5, 277, 1024 }, { 5, 278, 1024 }, { 6, 279, 1024 },
2377    { 4, 280, 1024 }, { 5, 281, 1024 }, { 5, 282, 1024 }, { 6, 283, 1024 }, { 5, 284, 1024 }, { 6, 285, 1024 }, { 6, 286, 1024 }, { 7, 287, 1024 },
2378    { 3, 288, 1024 }, { 4, 289, 1024 }, { 4, 290, 1024 }, { 5, 291, 1024 }, { 4, 292, 1024 }, { 5, 293, 1024 }, { 5, 294, 1024 }, { 6, 295, 1024 },
2379    { 4, 296, 1024 }, { 5, 297, 1024 }, { 5, 298, 1024 }, { 6, 299, 1024 }, { 5, 300, 1024 }, { 6, 301, 1024 }, { 6, 302, 1024 }, { 7, 303, 1024 },
2380    { 4, 304, 1024 }, { 5, 305, 1024 }, { 5, 306, 1024 }, { 6, 307, 1024 }, { 5, 308, 1024 }, { 6, 309, 1024 }, { 6, 310, 1024 }, { 7, 311, 1024 },
2381    { 5, 312, 1024 }, { 6, 313, 1024 }, { 6, 314, 1024 }, { 7, 315, 1024 }, { 6, 316, 1024 }, { 7, 317, 1024 }, { 7, 318, 1024 }, { 8, 319, 1024 },
2382    { 3, 320, 1024 }, { 4, 321, 1024 }, { 4, 322, 1024 }, { 5, 323, 1024 }, { 4, 324, 1024 }, { 5, 325, 1024 }, { 5, 326, 1024 }, { 6, 327, 1024 },
2383    { 4, 328, 1024 }, { 5, 329, 1024 }, { 5, 330, 1024 }, { 6, 331, 1024 }, { 5, 332, 1024 }, { 6, 333, 1024 }, { 6, 334, 1024 }, { 7, 335, 1024 },
2384    { 4, 336, 1024 }, { 5, 337, 1024 }, { 5, 338, 1024 }, { 6, 339, 1024 }, { 5, 340, 1024 }, { 6, 341, 1024 }, { 6, 342, 1024 }, { 7, 343, 1024 },
2385    { 5, 344, 1024 }, { 6, 345, 1024 }, { 6, 346, 1024 }, { 7, 347, 1024 }, { 6, 348, 1024 }, { 7, 349, 1024 }, { 7, 350, 1024 }, { 8, 351, 1024 },
2386    { 4, 352, 1024 }, { 5, 353, 1024 }, { 5, 354, 1024 }, { 6, 355, 1024 }, { 5, 356, 1024 }, { 6, 357, 1024 }, { 6, 358, 1024 }, { 7, 359, 1024 },
2387    { 5, 360, 1024 }, { 6, 361, 1024 }, { 6, 362, 1024 }, { 7, 363, 1024 }, { 6, 364, 1024 }, { 7, 365, 1024 }, { 7, 366, 1024 }, { 8, 367, 1024 },
2388    { 5, 368, 1024 }, { 6, 369, 1024 }, { 6, 370, 1024 }, { 7, 371, 1024 }, { 6, 372, 1024 }, { 7, 373, 1024 }, { 7, 374, 1024 }, { 8, 375, 1024 },
2389    { 6, 376, 1024 }, { 7, 377, 1024 }, { 7, 378, 1024 }, { 8, 379, 1024 }, { 7, 380, 1024 }, { 8, 381, 1024 }, { 8, 382, 1024 }, { 9, 383, 1024 },
2390    { 3, 384, 1024 }, { 4, 385, 1024 }, { 4, 386, 1024 }, { 5, 387, 1024 }, { 4, 388, 1024 }, { 5, 389, 1024 }, { 5, 390, 1024 }, { 6, 391, 1024 },
2391    { 4, 392, 1024 }, { 5, 393, 1024 }, { 5, 394, 1024 }, { 6, 395, 1024 }, { 5, 396, 1024 }, { 6, 397, 1024 }, { 6, 398, 1024 }, { 7, 399, 1024 },
2392    { 4, 400, 1024 }, { 5, 401, 1024 }, { 5, 402, 1024 }, { 6, 403, 1024 }, { 5, 404, 1024 }, { 6, 405, 1024 }, { 6, 406, 1024 }, { 7, 407, 1024 },
2393    { 5, 408, 1024 }, { 6, 409, 1024 }, { 6, 410, 1024 }, { 7, 411, 1024 }, { 6, 412, 1024 }, { 7, 413, 1024 }, { 7, 414, 1024 }, { 8, 415, 1024 },
2394    { 4, 416, 1024 }, { 5, 417, 1024 }, { 5, 418, 1024 }, { 6, 419, 1024 }, { 5, 420, 1024 }, { 6, 421, 1024 }, { 6, 422, 1024 }, { 7, 423, 1024 },
2395    { 5, 424, 1024 }, { 6, 425, 1024 }, { 6, 426, 1024 }, { 7, 427, 1024 }, { 6, 428, 1024 }, { 7, 429, 1024 }, { 7, 430, 1024 }, { 8, 431, 1024 },
2396    { 5, 432, 1024 }, { 6, 433, 1024 }, { 6, 434, 1024 }, { 7, 435, 1024 }, { 6, 436, 1024 }, { 7, 437, 1024 }, { 7, 438, 1024 }, { 8, 439, 1024 },
2397    { 6, 440, 1024 }, { 7, 441, 1024 }, { 7, 442, 1024 }, { 8, 443, 1024 }, { 7, 444, 1024 }, { 8, 445, 1024 }, { 8, 446, 1024 }, { 9, 447, 1024 },
2398    { 4, 448, 1024 }, { 5, 449, 1024 }, { 5, 450, 1024 }, { 6, 451, 1024 }, { 5, 452, 1024 }, { 6, 453, 1024 }, { 6, 454, 1024 }, { 7, 455, 1024 },
2399    { 5, 456, 1024 }, { 6, 457, 1024 }, { 6, 458, 1024 }, { 7, 459, 1024 }, { 6, 460, 1024 }, { 7, 461, 1024 }, { 7, 462, 1024 }, { 8, 463, 1024 },
2400    { 5, 464, 1024 }, { 6, 465, 1024 }, { 6, 466, 1024 }, { 7, 467, 1024 }, { 6, 468, 1024 }, { 7, 469, 1024 }, { 7, 470, 1024 }, { 8, 471, 1024 },
2401    { 6, 472, 1024 }, { 7, 473, 1024 }, { 7, 474, 1024 }, { 8, 475, 1024 }, { 7, 476, 1024 }, { 8, 477, 1024 }, { 8, 478, 1024 }, { 9, 479, 1024 },
2402    { 5, 480, 1024 }, { 6, 481, 1024 }, { 6, 482, 1024 }, { 7, 483, 1024 }, { 6, 484, 1024 }, { 7, 485, 1024 }, { 7, 486, 1024 }, { 8, 487, 1024 },
2403    { 6, 488, 1024 }, { 7, 489, 1024 }, { 7, 490, 1024 }, { 8, 491, 1024 }, { 7, 492, 1024 }, { 8, 493, 1024 }, { 8, 494, 1024 }, { 9, 495, 1024 },
2404    { 6, 496, 1024 }, { 7, 497, 1024 }, { 7, 498, 1024 }, { 8, 499, 1024 }, { 7, 500, 1024 }, { 8, 501, 1024 }, { 8, 502, 1024 }, { 9, 503, 1024 },
2405    { 7, 504, 1024 }, { 8, 505, 1024 }, { 8, 506, 1024 }, { 9, 507, 1024 }, { 8, 508, 1024 }, { 9, 509, 1024 }, { 9, 510, 1024 }, { 10, 511, 1024 },
2406    { 2, 512, 1024 }, { 3, 513, 1024 }, { 3, 514, 1024 }, { 4, 515, 1024 }, { 3, 516, 1024 }, { 4, 517, 1024 }, { 4, 518, 1024 }, { 5, 519, 1024 },
2407    { 3, 520, 1024 }, { 4, 521, 1024 }, { 4, 522, 1024 }, { 5, 523, 1024 }, { 4, 524, 1024 }, { 5, 525, 1024 }, { 5, 526, 1024 }, { 6, 527, 1024 },
2408    { 3, 528, 1024 }, { 4, 529, 1024 }, { 4, 530, 1024 }, { 5, 531, 1024 }, { 4, 532, 1024 }, { 5, 533, 1024 }, { 5, 534, 1024 }, { 6, 535, 1024 },
2409    { 4, 536, 1024 }, { 5, 537, 1024 }, { 5, 538, 1024 }, { 6, 539, 1024 }, { 5, 540, 1024 }, { 6, 541, 1024 }, { 6, 542, 1024 }, { 7, 543, 1024 },
2410    { 3, 544, 1024 }, { 4, 545, 1024 }, { 4, 546, 1024 }, { 5, 547, 1024 }, { 4, 548, 1024 }, { 5, 549, 1024 }, { 5, 550, 1024 }, { 6, 551, 1024 },
2411    { 4, 552, 1024 }, { 5, 553, 1024 }, { 5, 554, 1024 }, { 6, 555, 1024 }, { 5, 556, 1024 }, { 6, 557, 1024 }, { 6, 558, 1024 }, { 7, 559, 1024 },
2412    { 4, 560, 1024 }, { 5, 561, 1024 }, { 5, 562, 1024 }, { 6, 563, 1024 }, { 5, 564, 1024 }, { 6, 565, 1024 }, { 6, 566, 1024 }, { 7, 567, 1024 },
2413    { 5, 568, 1024 }, { 6, 569, 1024 }, { 6, 570, 1024 }, { 7, 571, 1024 }, { 6, 572, 1024 }, { 7, 573, 1024 }, { 7, 574, 1024 }, { 8, 575, 1024 },
2414    { 3, 576, 1024 }, { 4, 577, 1024 }, { 4, 578, 1024 }, { 5, 579, 1024 }, { 4, 580, 1024 }, { 5, 581, 1024 }, { 5, 582, 1024 }, { 6, 583, 1024 },
2415    { 4, 584, 1024 }, { 5, 585, 1024 }, { 5, 586, 1024 }, { 6, 587, 1024 }, { 5, 588, 1024 }, { 6, 589, 1024 }, { 6, 590, 1024 }, { 7, 591, 1024 },
2416    { 4, 592, 1024 }, { 5, 593, 1024 }, { 5, 594, 1024 }, { 6, 595, 1024 }, { 5, 596, 1024 }, { 6, 597, 1024 }, { 6, 598, 1024 }, { 7, 599, 1024 },
2417    { 5, 600, 1024 }, { 6, 601, 1024 }, { 6, 602, 1024 }, { 7, 603, 1024 }, { 6, 604, 1024 }, { 7, 605, 1024 }, { 7, 606, 1024 }, { 8, 607, 1024 },
2418    { 4, 608, 1024 }, { 5, 609, 1024 }, { 5, 610, 1024 }, { 6, 611, 1024 }, { 5, 612, 1024 }, { 6, 613, 1024 }, { 6, 614, 1024 }, { 7, 615, 1024 },
2419    { 5, 616, 1024 }, { 6, 617, 1024 }, { 6, 618, 1024 }, { 7, 619, 1024 }, { 6, 620, 1024 }, { 7, 621, 1024 }, { 7, 622, 1024 }, { 8, 623, 1024 },
2420    { 5, 624, 1024 }, { 6, 625, 1024 }, { 6, 626, 1024 }, { 7, 627, 1024 }, { 6, 628, 1024 }, { 7, 629, 1024 }, { 7, 630, 1024 }, { 8, 631, 1024 },
2421    { 6, 632, 1024 }, { 7, 633, 1024 }, { 7, 634, 1024 }, { 8, 635, 1024 }, { 7, 636, 1024 }, { 8, 637, 1024 }, { 8, 638, 1024 }, { 9, 639, 1024 },
2422    { 3, 640, 1024 }, { 4, 641, 1024 }, { 4, 642, 1024 }, { 5, 643, 1024 }, { 4, 644, 1024 }, { 5, 645, 1024 }, { 5, 646, 1024 }, { 6, 647, 1024 },
2423    { 4, 648, 1024 }, { 5, 649, 1024 }, { 5, 650, 1024 }, { 6, 651, 1024 }, { 5, 652, 1024 }, { 6, 653, 1024 }, { 6, 654, 1024 }, { 7, 655, 1024 },
2424    { 4, 656, 1024 }, { 5, 657, 1024 }, { 5, 658, 1024 }, { 6, 659, 1024 }, { 5, 660, 1024 }, { 6, 661, 1024 }, { 6, 662, 1024 }, { 7, 663, 1024 },
2425    { 5, 664, 1024 }, { 6, 665, 1024 }, { 6, 666, 1024 }, { 7, 667, 1024 }, { 6, 668, 1024 }, { 7, 669, 1024 }, { 7, 670, 1024 }, { 8, 671, 1024 },
2426    { 4, 672, 1024 }, { 5, 673, 1024 }, { 5, 674, 1024 }, { 6, 675, 1024 }, { 5, 676, 1024 }, { 6, 677, 1024 }, { 6, 678, 1024 }, { 7, 679, 1024 },
2427    { 5, 680, 1024 }, { 6, 681, 1024 }, { 6, 682, 1024 }, { 7, 683, 1024 }, { 6, 684, 1024 }, { 7, 685, 1024 }, { 7, 686, 1024 }, { 8, 687, 1024 },
2428    { 5, 688, 1024 }, { 6, 689, 1024 }, { 6, 690, 1024 }, { 7, 691, 1024 }, { 6, 692, 1024 }, { 7, 693, 1024 }, { 7, 694, 1024 }, { 8, 695, 1024 },
2429    { 6, 696, 1024 }, { 7, 697, 1024 }, { 7, 698, 1024 }, { 8, 699, 1024 }, { 7, 700, 1024 }, { 8, 701, 1024 }, { 8, 702, 1024 }, { 9, 703, 1024 },
2430    { 4, 704, 1024 }, { 5, 705, 1024 }, { 5, 706, 1024 }, { 6, 707, 1024 }, { 5, 708, 1024 }, { 6, 709, 1024 }, { 6, 710, 1024 }, { 7, 711, 1024 },
2431    { 5, 712, 1024 }, { 6, 713, 1024 }, { 6, 714, 1024 }, { 7, 715, 1024 }, { 6, 716, 1024 }, { 7, 717, 1024 }, { 7, 718, 1024 }, { 8, 719, 1024 },
2432    { 5, 720, 1024 }, { 6, 721, 1024 }, { 6, 722, 1024 }, { 7, 723, 1024 }, { 6, 724, 1024 }, { 7, 725, 1024 }, { 7, 726, 1024 }, { 8, 727, 1024 },
2433    { 6, 728, 1024 }, { 7, 729, 1024 }, { 7, 730, 1024 }, { 8, 731, 1024 }, { 7, 732, 1024 }, { 8, 733, 1024 }, { 8, 734, 1024 }, { 9, 735, 1024 },
2434    { 5, 736, 1024 }, { 6, 737, 1024 }, { 6, 738, 1024 }, { 7, 739, 1024 }, { 6, 740, 1024 }, { 7, 741, 1024 }, { 7, 742, 1024 }, { 8, 743, 1024 },
2435    { 6, 744, 1024 }, { 7, 745, 1024 }, { 7, 746, 1024 }, { 8, 747, 1024 }, { 7, 748, 1024 }, { 8, 749, 1024 }, { 8, 750, 1024 }, { 9, 751, 1024 },
2436    { 6, 752, 1024 }, { 7, 753, 1024 }, { 7, 754, 1024 }, { 8, 755, 1024 }, { 7, 756, 1024 }, { 8, 757, 1024 }, { 8, 758, 1024 }, { 9, 759, 1024 },
2437    { 7, 760, 1024 }, { 8, 761, 1024 }, { 8, 762, 1024 }, { 9, 763, 1024 }, { 8, 764, 1024 }, { 9, 765, 1024 }, { 9, 766, 1024 }, { 10, 767, 1024 },
2438    { 3, 768, 1024 }, { 4, 769, 1024 }, { 4, 770, 1024 }, { 5, 771, 1024 }, { 4, 772, 1024 }, { 5, 773, 1024 }, { 5, 774, 1024 }, { 6, 775, 1024 },
2439    { 4, 776, 1024 }, { 5, 777, 1024 }, { 5, 778, 1024 }, { 6, 779, 1024 }, { 5, 780, 1024 }, { 6, 781, 1024 }, { 6, 782, 1024 }, { 7, 783, 1024 },
2440    { 4, 784, 1024 }, { 5, 785, 1024 }, { 5, 786, 1024 }, { 6, 787, 1024 }, { 5, 788, 1024 }, { 6, 789, 1024 }, { 6, 790, 1024 }, { 7, 791, 1024 },
2441    { 5, 792, 1024 }, { 6, 793, 1024 }, { 6, 794, 1024 }, { 7, 795, 1024 }, { 6, 796, 1024 }, { 7, 797, 1024 }, { 7, 798, 1024 }, { 8, 799, 1024 },
2442    { 4, 800, 1024 }, { 5, 801, 1024 }, { 5, 802, 1024 }, { 6, 803, 1024 }, { 5, 804, 1024 }, { 6, 805, 1024 }, { 6, 806, 1024 }, { 7, 807, 1024 },
2443    { 5, 808, 1024 }, { 6, 809, 1024 }, { 6, 810, 1024 }, { 7, 811, 1024 }, { 6, 812, 1024 }, { 7, 813, 1024 }, { 7, 814, 1024 }, { 8, 815, 1024 },
2444    { 5, 816, 1024 }, { 6, 817, 1024 }, { 6, 818, 1024 }, { 7, 819, 1024 }, { 6, 820, 1024 }, { 7, 821, 1024 }, { 7, 822, 1024 }, { 8, 823, 1024 },
2445    { 6, 824, 1024 }, { 7, 825, 1024 }, { 7, 826, 1024 }, { 8, 827, 1024 }, { 7, 828, 1024 }, { 8, 829, 1024 }, { 8, 830, 1024 }, { 9, 831, 1024 },
2446    { 4, 832, 1024 }, { 5, 833, 1024 }, { 5, 834, 1024 }, { 6, 835, 1024 }, { 5, 836, 1024 }, { 6, 837, 1024 }, { 6, 838, 1024 }, { 7, 839, 1024 },
2447    { 5, 840, 1024 }, { 6, 841, 1024 }, { 6, 842, 1024 }, { 7, 843, 1024 }, { 6, 844, 1024 }, { 7, 845, 1024 }, { 7, 846, 1024 }, { 8, 847, 1024 },
2448    { 5, 848, 1024 }, { 6, 849, 1024 }, { 6, 850, 1024 }, { 7, 851, 1024 }, { 6, 852, 1024 }, { 7, 853, 1024 }, { 7, 854, 1024 }, { 8, 855, 1024 },
2449    { 6, 856, 1024 }, { 7, 857, 1024 }, { 7, 858, 1024 }, { 8, 859, 1024 }, { 7, 860, 1024 }, { 8, 861, 1024 }, { 8, 862, 1024 }, { 9, 863, 1024 },
2450    { 5, 864, 1024 }, { 6, 865, 1024 }, { 6, 866, 1024 }, { 7, 867, 1024 }, { 6, 868, 1024 }, { 7, 869, 1024 }, { 7, 870, 1024 }, { 8, 871, 1024 },
2451    { 6, 872, 1024 }, { 7, 873, 1024 }, { 7, 874, 1024 }, { 8, 875, 1024 }, { 7, 876, 1024 }, { 8, 877, 1024 }, { 8, 878, 1024 }, { 9, 879, 1024 },
2452    { 6, 880, 1024 }, { 7, 881, 1024 }, { 7, 882, 1024 }, { 8, 883, 1024 }, { 7, 884, 1024 }, { 8, 885, 1024 }, { 8, 886, 1024 }, { 9, 887, 1024 },
2453    { 7, 888, 1024 }, { 8, 889, 1024 }, { 8, 890, 1024 }, { 9, 891, 1024 }, { 8, 892, 1024 }, { 9, 893, 1024 }, { 9, 894, 1024 }, { 10, 895, 1024 },
2454    { 4, 896, 1024 }, { 5, 897, 1024 }, { 5, 898, 1024 }, { 6, 899, 1024 }, { 5, 900, 1024 }, { 6, 901, 1024 }, { 6, 902, 1024 }, { 7, 903, 1024 },
2455    { 5, 904, 1024 }, { 6, 905, 1024 }, { 6, 906, 1024 }, { 7, 907, 1024 }, { 6, 908, 1024 }, { 7, 909, 1024 }, { 7, 910, 1024 }, { 8, 911, 1024 },
2456    { 5, 912, 1024 }, { 6, 913, 1024 }, { 6, 914, 1024 }, { 7, 915, 1024 }, { 6, 916, 1024 }, { 7, 917, 1024 }, { 7, 918, 1024 }, { 8, 919, 1024 },
2457    { 6, 920, 1024 }, { 7, 921, 1024 }, { 7, 922, 1024 }, { 8, 923, 1024 }, { 7, 924, 1024 }, { 8, 925, 1024 }, { 8, 926, 1024 }, { 9, 927, 1024 },
2458    { 5, 928, 1024 }, { 6, 929, 1024 }, { 6, 930, 1024 }, { 7, 931, 1024 }, { 6, 932, 1024 }, { 7, 933, 1024 }, { 7, 934, 1024 }, { 8, 935, 1024 },
2459    { 6, 936, 1024 }, { 7, 937, 1024 }, { 7, 938, 1024 }, { 8, 939, 1024 }, { 7, 940, 1024 }, { 8, 941, 1024 }, { 8, 942, 1024 }, { 9, 943, 1024 },
2460    { 6, 944, 1024 }, { 7, 945, 1024 }, { 7, 946, 1024 }, { 8, 947, 1024 }, { 7, 948, 1024 }, { 8, 949, 1024 }, { 8, 950, 1024 }, { 9, 951, 1024 },
2461    { 7, 952, 1024 }, { 8, 953, 1024 }, { 8, 954, 1024 }, { 9, 955, 1024 }, { 8, 956, 1024 }, { 9, 957, 1024 }, { 9, 958, 1024 }, { 10, 959, 1024 },
2462    { 5, 960, 1024 }, { 6, 961, 1024 }, { 6, 962, 1024 }, { 7, 963, 1024 }, { 6, 964, 1024 }, { 7, 965, 1024 }, { 7, 966, 1024 }, { 8, 967, 1024 },
2463    { 6, 968, 1024 }, { 7, 969, 1024 }, { 7, 970, 1024 }, { 8, 971, 1024 }, { 7, 972, 1024 }, { 8, 973, 1024 }, { 8, 974, 1024 }, { 9, 975, 1024 },
2464    { 6, 976, 1024 }, { 7, 977, 1024 }, { 7, 978, 1024 }, { 8, 979, 1024 }, { 7, 980, 1024 }, { 8, 981, 1024 }, { 8, 982, 1024 }, { 9, 983, 1024 },
2465    { 7, 984, 1024 }, { 8, 985, 1024 }, { 8, 986, 1024 }, { 9, 987, 1024 }, { 8, 988, 1024 }, { 9, 989, 1024 }, { 9, 990, 1024 }, { 10, 991, 1024 },
2466    { 6, 992, 1024 }, { 7, 993, 1024 }, { 7, 994, 1024 }, { 8, 995, 1024 }, { 7, 996, 1024 }, { 8, 997, 1024 }, { 8, 998, 1024 }, { 9, 999, 1024 },
2467    { 7, 1000, 1024 }, { 8, 1001, 1024 }, { 8, 1002, 1024 }, { 9, 1003, 1024 }, { 8, 1004, 1024 }, { 9, 1005, 1024 }, { 9, 1006, 1024 }, { 10, 1007, 1024 },
2468    { 7, 1008, 1024 }, { 8, 1009, 1024 }, { 8, 1010, 1024 }, { 9, 1011, 1024 }, { 8, 1012, 1024 }, { 9, 1013, 1024 }, { 9, 1014, 1024 }, { 10, 1015, 1024 },
2469    { 8, 1016, 1024 }, { 9, 1017, 1024 }, { 9, 1018, 1024 }, { 10, 1019, 1024 }, { 9, 1020, 1024 }, { 10, 1021, 1024 }, { 10, 1022, 1024 }, { 11, 1023, 1024 },
2470 #if FP_LUT > 11
2471    { 1, 0, 0 }, { 2, 1, 2048 }, { 2, 2, 2048 }, { 3, 3, 2048 }, { 2, 4, 2048 }, { 3, 5, 2048 }, { 3, 6, 2048 }, { 4, 7, 2048 },
2472    { 2, 8, 2048 }, { 3, 9, 2048 }, { 3, 10, 2048 }, { 4, 11, 2048 }, { 3, 12, 2048 }, { 4, 13, 2048 }, { 4, 14, 2048 }, { 5, 15, 2048 },
2473    { 2, 16, 2048 }, { 3, 17, 2048 }, { 3, 18, 2048 }, { 4, 19, 2048 }, { 3, 20, 2048 }, { 4, 21, 2048 }, { 4, 22, 2048 }, { 5, 23, 2048 },
2474    { 3, 24, 2048 }, { 4, 25, 2048 }, { 4, 26, 2048 }, { 5, 27, 2048 }, { 4, 28, 2048 }, { 5, 29, 2048 }, { 5, 30, 2048 }, { 6, 31, 2048 },
2475    { 2, 32, 2048 }, { 3, 33, 2048 }, { 3, 34, 2048 }, { 4, 35, 2048 }, { 3, 36, 2048 }, { 4, 37, 2048 }, { 4, 38, 2048 }, { 5, 39, 2048 },
2476    { 3, 40, 2048 }, { 4, 41, 2048 }, { 4, 42, 2048 }, { 5, 43, 2048 }, { 4, 44, 2048 }, { 5, 45, 2048 }, { 5, 46, 2048 }, { 6, 47, 2048 },
2477    { 3, 48, 2048 }, { 4, 49, 2048 }, { 4, 50, 2048 }, { 5, 51, 2048 }, { 4, 52, 2048 }, { 5, 53, 2048 }, { 5, 54, 2048 }, { 6, 55, 2048 },
2478    { 4, 56, 2048 }, { 5, 57, 2048 }, { 5, 58, 2048 }, { 6, 59, 2048 }, { 5, 60, 2048 }, { 6, 61, 2048 }, { 6, 62, 2048 }, { 7, 63, 2048 },
2479    { 2, 64, 2048 }, { 3, 65, 2048 }, { 3, 66, 2048 }, { 4, 67, 2048 }, { 3, 68, 2048 }, { 4, 69, 2048 }, { 4, 70, 2048 }, { 5, 71, 2048 },
2480    { 3, 72, 2048 }, { 4, 73, 2048 }, { 4, 74, 2048 }, { 5, 75, 2048 }, { 4, 76, 2048 }, { 5, 77, 2048 }, { 5, 78, 2048 }, { 6, 79, 2048 },
2481    { 3, 80, 2048 }, { 4, 81, 2048 }, { 4, 82, 2048 }, { 5, 83, 2048 }, { 4, 84, 2048 }, { 5, 85, 2048 }, { 5, 86, 2048 }, { 6, 87, 2048 },
2482    { 4, 88, 2048 }, { 5, 89, 2048 }, { 5, 90, 2048 }, { 6, 91, 2048 }, { 5, 92, 2048 }, { 6, 93, 2048 }, { 6, 94, 2048 }, { 7, 95, 2048 },
2483    { 3, 96, 2048 }, { 4, 97, 2048 }, { 4, 98, 2048 }, { 5, 99, 2048 }, { 4, 100, 2048 }, { 5, 101, 2048 }, { 5, 102, 2048 }, { 6, 103, 2048 },
2484    { 4, 104, 2048 }, { 5, 105, 2048 }, { 5, 106, 2048 }, { 6, 107, 2048 }, { 5, 108, 2048 }, { 6, 109, 2048 }, { 6, 110, 2048 }, { 7, 111, 2048 },
2485    { 4, 112, 2048 }, { 5, 113, 2048 }, { 5, 114, 2048 }, { 6, 115, 2048 }, { 5, 116, 2048 }, { 6, 117, 2048 }, { 6, 118, 2048 }, { 7, 119, 2048 },
2486    { 5, 120, 2048 }, { 6, 121, 2048 }, { 6, 122, 2048 }, { 7, 123, 2048 }, { 6, 124, 2048 }, { 7, 125, 2048 }, { 7, 126, 2048 }, { 8, 127, 2048 },
2487    { 2, 128, 2048 }, { 3, 129, 2048 }, { 3, 130, 2048 }, { 4, 131, 2048 }, { 3, 132, 2048 }, { 4, 133, 2048 }, { 4, 134, 2048 }, { 5, 135, 2048 },
2488    { 3, 136, 2048 }, { 4, 137, 2048 }, { 4, 138, 2048 }, { 5, 139, 2048 }, { 4, 140, 2048 }, { 5, 141, 2048 }, { 5, 142, 2048 }, { 6, 143, 2048 },
2489    { 3, 144, 2048 }, { 4, 145, 2048 }, { 4, 146, 2048 }, { 5, 147, 2048 }, { 4, 148, 2048 }, { 5, 149, 2048 }, { 5, 150, 2048 }, { 6, 151, 2048 },
2490    { 4, 152, 2048 }, { 5, 153, 2048 }, { 5, 154, 2048 }, { 6, 155, 2048 }, { 5, 156, 2048 }, { 6, 157, 2048 }, { 6, 158, 2048 }, { 7, 159, 2048 },
2491    { 3, 160, 2048 }, { 4, 161, 2048 }, { 4, 162, 2048 }, { 5, 163, 2048 }, { 4, 164, 2048 }, { 5, 165, 2048 }, { 5, 166, 2048 }, { 6, 167, 2048 },
2492    { 4, 168, 2048 }, { 5, 169, 2048 }, { 5, 170, 2048 }, { 6, 171, 2048 }, { 5, 172, 2048 }, { 6, 173, 2048 }, { 6, 174, 2048 }, { 7, 175, 2048 },
2493    { 4, 176, 2048 }, { 5, 177, 2048 }, { 5, 178, 2048 }, { 6, 179, 2048 }, { 5, 180, 2048 }, { 6, 181, 2048 }, { 6, 182, 2048 }, { 7, 183, 2048 },
2494    { 5, 184, 2048 }, { 6, 185, 2048 }, { 6, 186, 2048 }, { 7, 187, 2048 }, { 6, 188, 2048 }, { 7, 189, 2048 }, { 7, 190, 2048 }, { 8, 191, 2048 },
2495    { 3, 192, 2048 }, { 4, 193, 2048 }, { 4, 194, 2048 }, { 5, 195, 2048 }, { 4, 196, 2048 }, { 5, 197, 2048 }, { 5, 198, 2048 }, { 6, 199, 2048 },
2496    { 4, 200, 2048 }, { 5, 201, 2048 }, { 5, 202, 2048 }, { 6, 203, 2048 }, { 5, 204, 2048 }, { 6, 205, 2048 }, { 6, 206, 2048 }, { 7, 207, 2048 },
2497    { 4, 208, 2048 }, { 5, 209, 2048 }, { 5, 210, 2048 }, { 6, 211, 2048 }, { 5, 212, 2048 }, { 6, 213, 2048 }, { 6, 214, 2048 }, { 7, 215, 2048 },
2498    { 5, 216, 2048 }, { 6, 217, 2048 }, { 6, 218, 2048 }, { 7, 219, 2048 }, { 6, 220, 2048 }, { 7, 221, 2048 }, { 7, 222, 2048 }, { 8, 223, 2048 },
2499    { 4, 224, 2048 }, { 5, 225, 2048 }, { 5, 226, 2048 }, { 6, 227, 2048 }, { 5, 228, 2048 }, { 6, 229, 2048 }, { 6, 230, 2048 }, { 7, 231, 2048 },
2500    { 5, 232, 2048 }, { 6, 233, 2048 }, { 6, 234, 2048 }, { 7, 235, 2048 }, { 6, 236, 2048 }, { 7, 237, 2048 }, { 7, 238, 2048 }, { 8, 239, 2048 },
2501    { 5, 240, 2048 }, { 6, 241, 2048 }, { 6, 242, 2048 }, { 7, 243, 2048 }, { 6, 244, 2048 }, { 7, 245, 2048 }, { 7, 246, 2048 }, { 8, 247, 2048 },
2502    { 6, 248, 2048 }, { 7, 249, 2048 }, { 7, 250, 2048 }, { 8, 251, 2048 }, { 7, 252, 2048 }, { 8, 253, 2048 }, { 8, 254, 2048 }, { 9, 255, 2048 },
2503    { 2, 256, 2048 }, { 3, 257, 2048 }, { 3, 258, 2048 }, { 4, 259, 2048 }, { 3, 260, 2048 }, { 4, 261, 2048 }, { 4, 262, 2048 }, { 5, 263, 2048 },
2504    { 3, 264, 2048 }, { 4, 265, 2048 }, { 4, 266, 2048 }, { 5, 267, 2048 }, { 4, 268, 2048 }, { 5, 269, 2048 }, { 5, 270, 2048 }, { 6, 271, 2048 },
2505    { 3, 272, 2048 }, { 4, 273, 2048 }, { 4, 274, 2048 }, { 5, 275, 2048 }, { 4, 276, 2048 }, { 5, 277, 2048 }, { 5, 278, 2048 }, { 6, 279, 2048 },
2506    { 4, 280, 2048 }, { 5, 281, 2048 }, { 5, 282, 2048 }, { 6, 283, 2048 }, { 5, 284, 2048 }, { 6, 285, 2048 }, { 6, 286, 2048 }, { 7, 287, 2048 },
2507    { 3, 288, 2048 }, { 4, 289, 2048 }, { 4, 290, 2048 }, { 5, 291, 2048 }, { 4, 292, 2048 }, { 5, 293, 2048 }, { 5, 294, 2048 }, { 6, 295, 2048 },
2508    { 4, 296, 2048 }, { 5, 297, 2048 }, { 5, 298, 2048 }, { 6, 299, 2048 }, { 5, 300, 2048 }, { 6, 301, 2048 }, { 6, 302, 2048 }, { 7, 303, 2048 },
2509    { 4, 304, 2048 }, { 5, 305, 2048 }, { 5, 306, 2048 }, { 6, 307, 2048 }, { 5, 308, 2048 }, { 6, 309, 2048 }, { 6, 310, 2048 }, { 7, 311, 2048 },
2510    { 5, 312, 2048 }, { 6, 313, 2048 }, { 6, 314, 2048 }, { 7, 315, 2048 }, { 6, 316, 2048 }, { 7, 317, 2048 }, { 7, 318, 2048 }, { 8, 319, 2048 },
2511    { 3, 320, 2048 }, { 4, 321, 2048 }, { 4, 322, 2048 }, { 5, 323, 2048 }, { 4, 324, 2048 }, { 5, 325, 2048 }, { 5, 326, 2048 }, { 6, 327, 2048 },
2512    { 4, 328, 2048 }, { 5, 329, 2048 }, { 5, 330, 2048 }, { 6, 331, 2048 }, { 5, 332, 2048 }, { 6, 333, 2048 }, { 6, 334, 2048 }, { 7, 335, 2048 },
2513    { 4, 336, 2048 }, { 5, 337, 2048 }, { 5, 338, 2048 }, { 6, 339, 2048 }, { 5, 340, 2048 }, { 6, 341, 2048 }, { 6, 342, 2048 }, { 7, 343, 2048 },
2514    { 5, 344, 2048 }, { 6, 345, 2048 }, { 6, 346, 2048 }, { 7, 347, 2048 }, { 6, 348, 2048 }, { 7, 349, 2048 }, { 7, 350, 2048 }, { 8, 351, 2048 },
2515    { 4, 352, 2048 }, { 5, 353, 2048 }, { 5, 354, 2048 }, { 6, 355, 2048 }, { 5, 356, 2048 }, { 6, 357, 2048 }, { 6, 358, 2048 }, { 7, 359, 2048 },
2516    { 5, 360, 2048 }, { 6, 361, 2048 }, { 6, 362, 2048 }, { 7, 363, 2048 }, { 6, 364, 2048 }, { 7, 365, 2048 }, { 7, 366, 2048 }, { 8, 367, 2048 },
2517    { 5, 368, 2048 }, { 6, 369, 2048 }, { 6, 370, 2048 }, { 7, 371, 2048 }, { 6, 372, 2048 }, { 7, 373, 2048 }, { 7, 374, 2048 }, { 8, 375, 2048 },
2518    { 6, 376, 2048 }, { 7, 377, 2048 }, { 7, 378, 2048 }, { 8, 379, 2048 }, { 7, 380, 2048 }, { 8, 381, 2048 }, { 8, 382, 2048 }, { 9, 383, 2048 },
2519    { 3, 384, 2048 }, { 4, 385, 2048 }, { 4, 386, 2048 }, { 5, 387, 2048 }, { 4, 388, 2048 }, { 5, 389, 2048 }, { 5, 390, 2048 }, { 6, 391, 2048 },
2520    { 4, 392, 2048 }, { 5, 393, 2048 }, { 5, 394, 2048 }, { 6, 395, 2048 }, { 5, 396, 2048 }, { 6, 397, 2048 }, { 6, 398, 2048 }, { 7, 399, 2048 },
2521    { 4, 400, 2048 }, { 5, 401, 2048 }, { 5, 402, 2048 }, { 6, 403, 2048 }, { 5, 404, 2048 }, { 6, 405, 2048 }, { 6, 406, 2048 }, { 7, 407, 2048 },
2522    { 5, 408, 2048 }, { 6, 409, 2048 }, { 6, 410, 2048 }, { 7, 411, 2048 }, { 6, 412, 2048 }, { 7, 413, 2048 }, { 7, 414, 2048 }, { 8, 415, 2048 },
2523    { 4, 416, 2048 }, { 5, 417, 2048 }, { 5, 418, 2048 }, { 6, 419, 2048 }, { 5, 420, 2048 }, { 6, 421, 2048 }, { 6, 422, 2048 }, { 7, 423, 2048 },
2524    { 5, 424, 2048 }, { 6, 425, 2048 }, { 6, 426, 2048 }, { 7, 427, 2048 }, { 6, 428, 2048 }, { 7, 429, 2048 }, { 7, 430, 2048 }, { 8, 431, 2048 },
2525    { 5, 432, 2048 }, { 6, 433, 2048 }, { 6, 434, 2048 }, { 7, 435, 2048 }, { 6, 436, 2048 }, { 7, 437, 2048 }, { 7, 438, 2048 }, { 8, 439, 2048 },
2526    { 6, 440, 2048 }, { 7, 441, 2048 }, { 7, 442, 2048 }, { 8, 443, 2048 }, { 7, 444, 2048 }, { 8, 445, 2048 }, { 8, 446, 2048 }, { 9, 447, 2048 },
2527    { 4, 448, 2048 }, { 5, 449, 2048 }, { 5, 450, 2048 }, { 6, 451, 2048 }, { 5, 452, 2048 }, { 6, 453, 2048 }, { 6, 454, 2048 }, { 7, 455, 2048 },
2528    { 5, 456, 2048 }, { 6, 457, 2048 }, { 6, 458, 2048 }, { 7, 459, 2048 }, { 6, 460, 2048 }, { 7, 461, 2048 }, { 7, 462, 2048 }, { 8, 463, 2048 },
2529    { 5, 464, 2048 }, { 6, 465, 2048 }, { 6, 466, 2048 }, { 7, 467, 2048 }, { 6, 468, 2048 }, { 7, 469, 2048 }, { 7, 470, 2048 }, { 8, 471, 2048 },
2530    { 6, 472, 2048 }, { 7, 473, 2048 }, { 7, 474, 2048 }, { 8, 475, 2048 }, { 7, 476, 2048 }, { 8, 477, 2048 }, { 8, 478, 2048 }, { 9, 479, 2048 },
2531    { 5, 480, 2048 }, { 6, 481, 2048 }, { 6, 482, 2048 }, { 7, 483, 2048 }, { 6, 484, 2048 }, { 7, 485, 2048 }, { 7, 486, 2048 }, { 8, 487, 2048 },
2532    { 6, 488, 2048 }, { 7, 489, 2048 }, { 7, 490, 2048 }, { 8, 491, 2048 }, { 7, 492, 2048 }, { 8, 493, 2048 }, { 8, 494, 2048 }, { 9, 495, 2048 },
2533    { 6, 496, 2048 }, { 7, 497, 2048 }, { 7, 498, 2048 }, { 8, 499, 2048 }, { 7, 500, 2048 }, { 8, 501, 2048 }, { 8, 502, 2048 }, { 9, 503, 2048 },
2534    { 7, 504, 2048 }, { 8, 505, 2048 }, { 8, 506, 2048 }, { 9, 507, 2048 }, { 8, 508, 2048 }, { 9, 509, 2048 }, { 9, 510, 2048 }, { 10, 511, 2048 },
2535    { 2, 512, 2048 }, { 3, 513, 2048 }, { 3, 514, 2048 }, { 4, 515, 2048 }, { 3, 516, 2048 }, { 4, 517, 2048 }, { 4, 518, 2048 }, { 5, 519, 2048 },
2536    { 3, 520, 2048 }, { 4, 521, 2048 }, { 4, 522, 2048 }, { 5, 523, 2048 }, { 4, 524, 2048 }, { 5, 525, 2048 }, { 5, 526, 2048 }, { 6, 527, 2048 },
2537    { 3, 528, 2048 }, { 4, 529, 2048 }, { 4, 530, 2048 }, { 5, 531, 2048 }, { 4, 532, 2048 }, { 5, 533, 2048 }, { 5, 534, 2048 }, { 6, 535, 2048 },
2538    { 4, 536, 2048 }, { 5, 537, 2048 }, { 5, 538, 2048 }, { 6, 539, 2048 }, { 5, 540, 2048 }, { 6, 541, 2048 }, { 6, 542, 2048 }, { 7, 543, 2048 },
2539    { 3, 544, 2048 }, { 4, 545, 2048 }, { 4, 546, 2048 }, { 5, 547, 2048 }, { 4, 548, 2048 }, { 5, 549, 2048 }, { 5, 550, 2048 }, { 6, 551, 2048 },
2540    { 4, 552, 2048 }, { 5, 553, 2048 }, { 5, 554, 2048 }, { 6, 555, 2048 }, { 5, 556, 2048 }, { 6, 557, 2048 }, { 6, 558, 2048 }, { 7, 559, 2048 },
2541    { 4, 560, 2048 }, { 5, 561, 2048 }, { 5, 562, 2048 }, { 6, 563, 2048 }, { 5, 564, 2048 }, { 6, 565, 2048 }, { 6, 566, 2048 }, { 7, 567, 2048 },
2542    { 5, 568, 2048 }, { 6, 569, 2048 }, { 6, 570, 2048 }, { 7, 571, 2048 }, { 6, 572, 2048 }, { 7, 573, 2048 }, { 7, 574, 2048 }, { 8, 575, 2048 },
2543    { 3, 576, 2048 }, { 4, 577, 2048 }, { 4, 578, 2048 }, { 5, 579, 2048 }, { 4, 580, 2048 }, { 5, 581, 2048 }, { 5, 582, 2048 }, { 6, 583, 2048 },
2544    { 4, 584, 2048 }, { 5, 585, 2048 }, { 5, 586, 2048 }, { 6, 587, 2048 }, { 5, 588, 2048 }, { 6, 589, 2048 }, { 6, 590, 2048 }, { 7, 591, 2048 },
2545    { 4, 592, 2048 }, { 5, 593, 2048 }, { 5, 594, 2048 }, { 6, 595, 2048 }, { 5, 596, 2048 }, { 6, 597, 2048 }, { 6, 598, 2048 }, { 7, 599, 2048 },
2546    { 5, 600, 2048 }, { 6, 601, 2048 }, { 6, 602, 2048 }, { 7, 603, 2048 }, { 6, 604, 2048 }, { 7, 605, 2048 }, { 7, 606, 2048 }, { 8, 607, 2048 },
2547    { 4, 608, 2048 }, { 5, 609, 2048 }, { 5, 610, 2048 }, { 6, 611, 2048 }, { 5, 612, 2048 }, { 6, 613, 2048 }, { 6, 614, 2048 }, { 7, 615, 2048 },
2548    { 5, 616, 2048 }, { 6, 617, 2048 }, { 6, 618, 2048 }, { 7, 619, 2048 }, { 6, 620, 2048 }, { 7, 621, 2048 }, { 7, 622, 2048 }, { 8, 623, 2048 },
2549    { 5, 624, 2048 }, { 6, 625, 2048 }, { 6, 626, 2048 }, { 7, 627, 2048 }, { 6, 628, 2048 }, { 7, 629, 2048 }, { 7, 630, 2048 }, { 8, 631, 2048 },
2550    { 6, 632, 2048 }, { 7, 633, 2048 }, { 7, 634, 2048 }, { 8, 635, 2048 }, { 7, 636, 2048 }, { 8, 637, 2048 }, { 8, 638, 2048 }, { 9, 639, 2048 },
2551    { 3, 640, 2048 }, { 4, 641, 2048 }, { 4, 642, 2048 }, { 5, 643, 2048 }, { 4, 644, 2048 }, { 5, 645, 2048 }, { 5, 646, 2048 }, { 6, 647, 2048 },
2552    { 4, 648, 2048 }, { 5, 649, 2048 }, { 5, 650, 2048 }, { 6, 651, 2048 }, { 5, 652, 2048 }, { 6, 653, 2048 }, { 6, 654, 2048 }, { 7, 655, 2048 },
2553    { 4, 656, 2048 }, { 5, 657, 2048 }, { 5, 658, 2048 }, { 6, 659, 2048 }, { 5, 660, 2048 }, { 6, 661, 2048 }, { 6, 662, 2048 }, { 7, 663, 2048 },
2554    { 5, 664, 2048 }, { 6, 665, 2048 }, { 6, 666, 2048 }, { 7, 667, 2048 }, { 6, 668, 2048 }, { 7, 669, 2048 }, { 7, 670, 2048 }, { 8, 671, 2048 },
2555    { 4, 672, 2048 }, { 5, 673, 2048 }, { 5, 674, 2048 }, { 6, 675, 2048 }, { 5, 676, 2048 }, { 6, 677, 2048 }, { 6, 678, 2048 }, { 7, 679, 2048 },
2556    { 5, 680, 2048 }, { 6, 681, 2048 }, { 6, 682, 2048 }, { 7, 683, 2048 }, { 6, 684, 2048 }, { 7, 685, 2048 }, { 7, 686, 2048 }, { 8, 687, 2048 },
2557    { 5, 688, 2048 }, { 6, 689, 2048 }, { 6, 690, 2048 }, { 7, 691, 2048 }, { 6, 692, 2048 }, { 7, 693, 2048 }, { 7, 694, 2048 }, { 8, 695, 2048 },
2558    { 6, 696, 2048 }, { 7, 697, 2048 }, { 7, 698, 2048 }, { 8, 699, 2048 }, { 7, 700, 2048 }, { 8, 701, 2048 }, { 8, 702, 2048 }, { 9, 703, 2048 },
2559    { 4, 704, 2048 }, { 5, 705, 2048 }, { 5, 706, 2048 }, { 6, 707, 2048 }, { 5, 708, 2048 }, { 6, 709, 2048 }, { 6, 710, 2048 }, { 7, 711, 2048 },
2560    { 5, 712, 2048 }, { 6, 713, 2048 }, { 6, 714, 2048 }, { 7, 715, 2048 }, { 6, 716, 2048 }, { 7, 717, 2048 }, { 7, 718, 2048 }, { 8, 719, 2048 },
2561    { 5, 720, 2048 }, { 6, 721, 2048 }, { 6, 722, 2048 }, { 7, 723, 2048 }, { 6, 724, 2048 }, { 7, 725, 2048 }, { 7, 726, 2048 }, { 8, 727, 2048 },
2562    { 6, 728, 2048 }, { 7, 729, 2048 }, { 7, 730, 2048 }, { 8, 731, 2048 }, { 7, 732, 2048 }, { 8, 733, 2048 }, { 8, 734, 2048 }, { 9, 735, 2048 },
2563    { 5, 736, 2048 }, { 6, 737, 2048 }, { 6, 738, 2048 }, { 7, 739, 2048 }, { 6, 740, 2048 }, { 7, 741, 2048 }, { 7, 742, 2048 }, { 8, 743, 2048 },
2564    { 6, 744, 2048 }, { 7, 745, 2048 }, { 7, 746, 2048 }, { 8, 747, 2048 }, { 7, 748, 2048 }, { 8, 749, 2048 }, { 8, 750, 2048 }, { 9, 751, 2048 },
2565    { 6, 752, 2048 }, { 7, 753, 2048 }, { 7, 754, 2048 }, { 8, 755, 2048 }, { 7, 756, 2048 }, { 8, 757, 2048 }, { 8, 758, 2048 }, { 9, 759, 2048 },
2566    { 7, 760, 2048 }, { 8, 761, 2048 }, { 8, 762, 2048 }, { 9, 763, 2048 }, { 8, 764, 2048 }, { 9, 765, 2048 }, { 9, 766, 2048 }, { 10, 767, 2048 },
2567    { 3, 768, 2048 }, { 4, 769, 2048 }, { 4, 770, 2048 }, { 5, 771, 2048 }, { 4, 772, 2048 }, { 5, 773, 2048 }, { 5, 774, 2048 }, { 6, 775, 2048 },
2568    { 4, 776, 2048 }, { 5, 777, 2048 }, { 5, 778, 2048 }, { 6, 779, 2048 }, { 5, 780, 2048 }, { 6, 781, 2048 }, { 6, 782, 2048 }, { 7, 783, 2048 },
2569    { 4, 784, 2048 }, { 5, 785, 2048 }, { 5, 786, 2048 }, { 6, 787, 2048 }, { 5, 788, 2048 }, { 6, 789, 2048 }, { 6, 790, 2048 }, { 7, 791, 2048 },
2570    { 5, 792, 2048 }, { 6, 793, 2048 }, { 6, 794, 2048 }, { 7, 795, 2048 }, { 6, 796, 2048 }, { 7, 797, 2048 }, { 7, 798, 2048 }, { 8, 799, 2048 },
2571    { 4, 800, 2048 }, { 5, 801, 2048 }, { 5, 802, 2048 }, { 6, 803, 2048 }, { 5, 804, 2048 }, { 6, 805, 2048 }, { 6, 806, 2048 }, { 7, 807, 2048 },
2572    { 5, 808, 2048 }, { 6, 809, 2048 }, { 6, 810, 2048 }, { 7, 811, 2048 }, { 6, 812, 2048 }, { 7, 813, 2048 }, { 7, 814, 2048 }, { 8, 815, 2048 },
2573    { 5, 816, 2048 }, { 6, 817, 2048 }, { 6, 818, 2048 }, { 7, 819, 2048 }, { 6, 820, 2048 }, { 7, 821, 2048 }, { 7, 822, 2048 }, { 8, 823, 2048 },
2574    { 6, 824, 2048 }, { 7, 825, 2048 }, { 7, 826, 2048 }, { 8, 827, 2048 }, { 7, 828, 2048 }, { 8, 829, 2048 }, { 8, 830, 2048 }, { 9, 831, 2048 },
2575    { 4, 832, 2048 }, { 5, 833, 2048 }, { 5, 834, 2048 }, { 6, 835, 2048 }, { 5, 836, 2048 }, { 6, 837, 2048 }, { 6, 838, 2048 }, { 7, 839, 2048 },
2576    { 5, 840, 2048 }, { 6, 841, 2048 }, { 6, 842, 2048 }, { 7, 843, 2048 }, { 6, 844, 2048 }, { 7, 845, 2048 }, { 7, 846, 2048 }, { 8, 847, 2048 },
2577    { 5, 848, 2048 }, { 6, 849, 2048 }, { 6, 850, 2048 }, { 7, 851, 2048 }, { 6, 852, 2048 }, { 7, 853, 2048 }, { 7, 854, 2048 }, { 8, 855, 2048 },
2578    { 6, 856, 2048 }, { 7, 857, 2048 }, { 7, 858, 2048 }, { 8, 859, 2048 }, { 7, 860, 2048 }, { 8, 861, 2048 }, { 8, 862, 2048 }, { 9, 863, 2048 },
2579    { 5, 864, 2048 }, { 6, 865, 2048 }, { 6, 866, 2048 }, { 7, 867, 2048 }, { 6, 868, 2048 }, { 7, 869, 2048 }, { 7, 870, 2048 }, { 8, 871, 2048 },
2580    { 6, 872, 2048 }, { 7, 873, 2048 }, { 7, 874, 2048 }, { 8, 875, 2048 }, { 7, 876, 2048 }, { 8, 877, 2048 }, { 8, 878, 2048 }, { 9, 879, 2048 },
2581    { 6, 880, 2048 }, { 7, 881, 2048 }, { 7, 882, 2048 }, { 8, 883, 2048 }, { 7, 884, 2048 }, { 8, 885, 2048 }, { 8, 886, 2048 }, { 9, 887, 2048 },
2582    { 7, 888, 2048 }, { 8, 889, 2048 }, { 8, 890, 2048 }, { 9, 891, 2048 }, { 8, 892, 2048 }, { 9, 893, 2048 }, { 9, 894, 2048 }, { 10, 895, 2048 },
2583    { 4, 896, 2048 }, { 5, 897, 2048 }, { 5, 898, 2048 }, { 6, 899, 2048 }, { 5, 900, 2048 }, { 6, 901, 2048 }, { 6, 902, 2048 }, { 7, 903, 2048 },
2584    { 5, 904, 2048 }, { 6, 905, 2048 }, { 6, 906, 2048 }, { 7, 907, 2048 }, { 6, 908, 2048 }, { 7, 909, 2048 }, { 7, 910, 2048 }, { 8, 911, 2048 },
2585    { 5, 912, 2048 }, { 6, 913, 2048 }, { 6, 914, 2048 }, { 7, 915, 2048 }, { 6, 916, 2048 }, { 7, 917, 2048 }, { 7, 918, 2048 }, { 8, 919, 2048 },
2586    { 6, 920, 2048 }, { 7, 921, 2048 }, { 7, 922, 2048 }, { 8, 923, 2048 }, { 7, 924, 2048 }, { 8, 925, 2048 }, { 8, 926, 2048 }, { 9, 927, 2048 },
2587    { 5, 928, 2048 }, { 6, 929, 2048 }, { 6, 930, 2048 }, { 7, 931, 2048 }, { 6, 932, 2048 }, { 7, 933, 2048 }, { 7, 934, 2048 }, { 8, 935, 2048 },
2588    { 6, 936, 2048 }, { 7, 937, 2048 }, { 7, 938, 2048 }, { 8, 939, 2048 }, { 7, 940, 2048 }, { 8, 941, 2048 }, { 8, 942, 2048 }, { 9, 943, 2048 },
2589    { 6, 944, 2048 }, { 7, 945, 2048 }, { 7, 946, 2048 }, { 8, 947, 2048 }, { 7, 948, 2048 }, { 8, 949, 2048 }, { 8, 950, 2048 }, { 9, 951, 2048 },
2590    { 7, 952, 2048 }, { 8, 953, 2048 }, { 8, 954, 2048 }, { 9, 955, 2048 }, { 8, 956, 2048 }, { 9, 957, 2048 }, { 9, 958, 2048 }, { 10, 959, 2048 },
2591    { 5, 960, 2048 }, { 6, 961, 2048 }, { 6, 962, 2048 }, { 7, 963, 2048 }, { 6, 964, 2048 }, { 7, 965, 2048 }, { 7, 966, 2048 }, { 8, 967, 2048 },
2592    { 6, 968, 2048 }, { 7, 969, 2048 }, { 7, 970, 2048 }, { 8, 971, 2048 }, { 7, 972, 2048 }, { 8, 973, 2048 }, { 8, 974, 2048 }, { 9, 975, 2048 },
2593    { 6, 976, 2048 }, { 7, 977, 2048 }, { 7, 978, 2048 }, { 8, 979, 2048 }, { 7, 980, 2048 }, { 8, 981, 2048 }, { 8, 982, 2048 }, { 9, 983, 2048 },
2594    { 7, 984, 2048 }, { 8, 985, 2048 }, { 8, 986, 2048 }, { 9, 987, 2048 }, { 8, 988, 2048 }, { 9, 989, 2048 }, { 9, 990, 2048 }, { 10, 991, 2048 },
2595    { 6, 992, 2048 }, { 7, 993, 2048 }, { 7, 994, 2048 }, { 8, 995, 2048 }, { 7, 996, 2048 }, { 8, 997, 2048 }, { 8, 998, 2048 }, { 9, 999, 2048 },
2596    { 7, 1000, 2048 }, { 8, 1001, 2048 }, { 8, 1002, 2048 }, { 9, 1003, 2048 }, { 8, 1004, 2048 }, { 9, 1005, 2048 }, { 9, 1006, 2048 }, { 10, 1007, 2048 },
2597    { 7, 1008, 2048 }, { 8, 1009, 2048 }, { 8, 1010, 2048 }, { 9, 1011, 2048 }, { 8, 1012, 2048 }, { 9, 1013, 2048 }, { 9, 1014, 2048 }, { 10, 1015, 2048 },
2598    { 8, 1016, 2048 }, { 9, 1017, 2048 }, { 9, 1018, 2048 }, { 10, 1019, 2048 }, { 9, 1020, 2048 }, { 10, 1021, 2048 }, { 10, 1022, 2048 }, { 11, 1023, 2048 },
2599    { 2, 1024, 2048 }, { 3, 1025, 2048 }, { 3, 1026, 2048 }, { 4, 1027, 2048 }, { 3, 1028, 2048 }, { 4, 1029, 2048 }, { 4, 1030, 2048 }, { 5, 1031, 2048 },
2600    { 3, 1032, 2048 }, { 4, 1033, 2048 }, { 4, 1034, 2048 }, { 5, 1035, 2048 }, { 4, 1036, 2048 }, { 5, 1037, 2048 }, { 5, 1038, 2048 }, { 6, 1039, 2048 },
2601    { 3, 1040, 2048 }, { 4, 1041, 2048 }, { 4, 1042, 2048 }, { 5, 1043, 2048 }, { 4, 1044, 2048 }, { 5, 1045, 2048 }, { 5, 1046, 2048 }, { 6, 1047, 2048 },
2602    { 4, 1048, 2048 }, { 5, 1049, 2048 }, { 5, 1050, 2048 }, { 6, 1051, 2048 }, { 5, 1052, 2048 }, { 6, 1053, 2048 }, { 6, 1054, 2048 }, { 7, 1055, 2048 },
2603    { 3, 1056, 2048 }, { 4, 1057, 2048 }, { 4, 1058, 2048 }, { 5, 1059, 2048 }, { 4, 1060, 2048 }, { 5, 1061, 2048 }, { 5, 1062, 2048 }, { 6, 1063, 2048 },
2604    { 4, 1064, 2048 }, { 5, 1065, 2048 }, { 5, 1066, 2048 }, { 6, 1067, 2048 }, { 5, 1068, 2048 }, { 6, 1069, 2048 }, { 6, 1070, 2048 }, { 7, 1071, 2048 },
2605    { 4, 1072, 2048 }, { 5, 1073, 2048 }, { 5, 1074, 2048 }, { 6, 1075, 2048 }, { 5, 1076, 2048 }, { 6, 1077, 2048 }, { 6, 1078, 2048 }, { 7, 1079, 2048 },
2606    { 5, 1080, 2048 }, { 6, 1081, 2048 }, { 6, 1082, 2048 }, { 7, 1083, 2048 }, { 6, 1084, 2048 }, { 7, 1085, 2048 }, { 7, 1086, 2048 }, { 8, 1087, 2048 },
2607    { 3, 1088, 2048 }, { 4, 1089, 2048 }, { 4, 1090, 2048 }, { 5, 1091, 2048 }, { 4, 1092, 2048 }, { 5, 1093, 2048 }, { 5, 1094, 2048 }, { 6, 1095, 2048 },
2608    { 4, 1096, 2048 }, { 5, 1097, 2048 }, { 5, 1098, 2048 }, { 6, 1099, 2048 }, { 5, 1100, 2048 }, { 6, 1101, 2048 }, { 6, 1102, 2048 }, { 7, 1103, 2048 },
2609    { 4, 1104, 2048 }, { 5, 1105, 2048 }, { 5, 1106, 2048 }, { 6, 1107, 2048 }, { 5, 1108, 2048 }, { 6, 1109, 2048 }, { 6, 1110, 2048 }, { 7, 1111, 2048 },
2610    { 5, 1112, 2048 }, { 6, 1113, 2048 }, { 6, 1114, 2048 }, { 7, 1115, 2048 }, { 6, 1116, 2048 }, { 7, 1117, 2048 }, { 7, 1118, 2048 }, { 8, 1119, 2048 },
2611    { 4, 1120, 2048 }, { 5, 1121, 2048 }, { 5, 1122, 2048 }, { 6, 1123, 2048 }, { 5, 1124, 2048 }, { 6, 1125, 2048 }, { 6, 1126, 2048 }, { 7, 1127, 2048 },
2612    { 5, 1128, 2048 }, { 6, 1129, 2048 }, { 6, 1130, 2048 }, { 7, 1131, 2048 }, { 6, 1132, 2048 }, { 7, 1133, 2048 }, { 7, 1134, 2048 }, { 8, 1135, 2048 },
2613    { 5, 1136, 2048 }, { 6, 1137, 2048 }, { 6, 1138, 2048 }, { 7, 1139, 2048 }, { 6, 1140, 2048 }, { 7, 1141, 2048 }, { 7, 1142, 2048 }, { 8, 1143, 2048 },
2614    { 6, 1144, 2048 }, { 7, 1145, 2048 }, { 7, 1146, 2048 }, { 8, 1147, 2048 }, { 7, 1148, 2048 }, { 8, 1149, 2048 }, { 8, 1150, 2048 }, { 9, 1151, 2048 },
2615    { 3, 1152, 2048 }, { 4, 1153, 2048 }, { 4, 1154, 2048 }, { 5, 1155, 2048 }, { 4, 1156, 2048 }, { 5, 1157, 2048 }, { 5, 1158, 2048 }, { 6, 1159, 2048 },
2616    { 4, 1160, 2048 }, { 5, 1161, 2048 }, { 5, 1162, 2048 }, { 6, 1163, 2048 }, { 5, 1164, 2048 }, { 6, 1165, 2048 }, { 6, 1166, 2048 }, { 7, 1167, 2048 },
2617    { 4, 1168, 2048 }, { 5, 1169, 2048 }, { 5, 1170, 2048 }, { 6, 1171, 2048 }, { 5, 1172, 2048 }, { 6, 1173, 2048 }, { 6, 1174, 2048 }, { 7, 1175, 2048 },
2618    { 5, 1176, 2048 }, { 6, 1177, 2048 }, { 6, 1178, 2048 }, { 7, 1179, 2048 }, { 6, 1180, 2048 }, { 7, 1181, 2048 }, { 7, 1182, 2048 }, { 8, 1183, 2048 },
2619    { 4, 1184, 2048 }, { 5, 1185, 2048 }, { 5, 1186, 2048 }, { 6, 1187, 2048 }, { 5, 1188, 2048 }, { 6, 1189, 2048 }, { 6, 1190, 2048 }, { 7, 1191, 2048 },
2620    { 5, 1192, 2048 }, { 6, 1193, 2048 }, { 6, 1194, 2048 }, { 7, 1195, 2048 }, { 6, 1196, 2048 }, { 7, 1197, 2048 }, { 7, 1198, 2048 }, { 8, 1199, 2048 },
2621    { 5, 1200, 2048 }, { 6, 1201, 2048 }, { 6, 1202, 2048 }, { 7, 1203, 2048 }, { 6, 1204, 2048 }, { 7, 1205, 2048 }, { 7, 1206, 2048 }, { 8, 1207, 2048 },
2622    { 6, 1208, 2048 }, { 7, 1209, 2048 }, { 7, 1210, 2048 }, { 8, 1211, 2048 }, { 7, 1212, 2048 }, { 8, 1213, 2048 }, { 8, 1214, 2048 }, { 9, 1215, 2048 },
2623    { 4, 1216, 2048 }, { 5, 1217, 2048 }, { 5, 1218, 2048 }, { 6, 1219, 2048 }, { 5, 1220, 2048 }, { 6, 1221, 2048 }, { 6, 1222, 2048 }, { 7, 1223, 2048 },
2624    { 5, 1224, 2048 }, { 6, 1225, 2048 }, { 6, 1226, 2048 }, { 7, 1227, 2048 }, { 6, 1228, 2048 }, { 7, 1229, 2048 }, { 7, 1230, 2048 }, { 8, 1231, 2048 },
2625    { 5, 1232, 2048 }, { 6, 1233, 2048 }, { 6, 1234, 2048 }, { 7, 1235, 2048 }, { 6, 1236, 2048 }, { 7, 1237, 2048 }, { 7, 1238, 2048 }, { 8, 1239, 2048 },
2626    { 6, 1240, 2048 }, { 7, 1241, 2048 }, { 7, 1242, 2048 }, { 8, 1243, 2048 }, { 7, 1244, 2048 }, { 8, 1245, 2048 }, { 8, 1246, 2048 }, { 9, 1247, 2048 },
2627    { 5, 1248, 2048 }, { 6, 1249, 2048 }, { 6, 1250, 2048 }, { 7, 1251, 2048 }, { 6, 1252, 2048 }, { 7, 1253, 2048 }, { 7, 1254, 2048 }, { 8, 1255, 2048 },
2628    { 6, 1256, 2048 }, { 7, 1257, 2048 }, { 7, 1258, 2048 }, { 8, 1259, 2048 }, { 7, 1260, 2048 }, { 8, 1261, 2048 }, { 8, 1262, 2048 }, { 9, 1263, 2048 },
2629    { 6, 1264, 2048 }, { 7, 1265, 2048 }, { 7, 1266, 2048 }, { 8, 1267, 2048 }, { 7, 1268, 2048 }, { 8, 1269, 2048 }, { 8, 1270, 2048 }, { 9, 1271, 2048 },
2630    { 7, 1272, 2048 }, { 8, 1273, 2048 }, { 8, 1274, 2048 }, { 9, 1275, 2048 }, { 8, 1276, 2048 }, { 9, 1277, 2048 }, { 9, 1278, 2048 }, { 10, 1279, 2048 },
2631    { 3, 1280, 2048 }, { 4, 1281, 2048 }, { 4, 1282, 2048 }, { 5, 1283, 2048 }, { 4, 1284, 2048 }, { 5, 1285, 2048 }, { 5, 1286, 2048 }, { 6, 1287, 2048 },
2632    { 4, 1288, 2048 }, { 5, 1289, 2048 }, { 5, 1290, 2048 }, { 6, 1291, 2048 }, { 5, 1292, 2048 }, { 6, 1293, 2048 }, { 6, 1294, 2048 }, { 7, 1295, 2048 },
2633    { 4, 1296, 2048 }, { 5, 1297, 2048 }, { 5, 1298, 2048 }, { 6, 1299, 2048 }, { 5, 1300, 2048 }, { 6, 1301, 2048 }, { 6, 1302, 2048 }, { 7, 1303, 2048 },
2634    { 5, 1304, 2048 }, { 6, 1305, 2048 }, { 6, 1306, 2048 }, { 7, 1307, 2048 }, { 6, 1308, 2048 }, { 7, 1309, 2048 }, { 7, 1310, 2048 }, { 8, 1311, 2048 },
2635    { 4, 1312, 2048 }, { 5, 1313, 2048 }, { 5, 1314, 2048 }, { 6, 1315, 2048 }, { 5, 1316, 2048 }, { 6, 1317, 2048 }, { 6, 1318, 2048 }, { 7, 1319, 2048 },
2636    { 5, 1320, 2048 }, { 6, 1321, 2048 }, { 6, 1322, 2048 }, { 7, 1323, 2048 }, { 6, 1324, 2048 }, { 7, 1325, 2048 }, { 7, 1326, 2048 }, { 8, 1327, 2048 },
2637    { 5, 1328, 2048 }, { 6, 1329, 2048 }, { 6, 1330, 2048 }, { 7, 1331, 2048 }, { 6, 1332, 2048 }, { 7, 1333, 2048 }, { 7, 1334, 2048 }, { 8, 1335, 2048 },
2638    { 6, 1336, 2048 }, { 7, 1337, 2048 }, { 7, 1338, 2048 }, { 8, 1339, 2048 }, { 7, 1340, 2048 }, { 8, 1341, 2048 }, { 8, 1342, 2048 }, { 9, 1343, 2048 },
2639    { 4, 1344, 2048 }, { 5, 1345, 2048 }, { 5, 1346, 2048 }, { 6, 1347, 2048 }, { 5, 1348, 2048 }, { 6, 1349, 2048 }, { 6, 1350, 2048 }, { 7, 1351, 2048 },
2640    { 5, 1352, 2048 }, { 6, 1353, 2048 }, { 6, 1354, 2048 }, { 7, 1355, 2048 }, { 6, 1356, 2048 }, { 7, 1357, 2048 }, { 7, 1358, 2048 }, { 8, 1359, 2048 },
2641    { 5, 1360, 2048 }, { 6, 1361, 2048 }, { 6, 1362, 2048 }, { 7, 1363, 2048 }, { 6, 1364, 2048 }, { 7, 1365, 2048 }, { 7, 1366, 2048 }, { 8, 1367, 2048 },
2642    { 6, 1368, 2048 }, { 7, 1369, 2048 }, { 7, 1370, 2048 }, { 8, 1371, 2048 }, { 7, 1372, 2048 }, { 8, 1373, 2048 }, { 8, 1374, 2048 }, { 9, 1375, 2048 },
2643    { 5, 1376, 2048 }, { 6, 1377, 2048 }, { 6, 1378, 2048 }, { 7, 1379, 2048 }, { 6, 1380, 2048 }, { 7, 1381, 2048 }, { 7, 1382, 2048 }, { 8, 1383, 2048 },
2644    { 6, 1384, 2048 }, { 7, 1385, 2048 }, { 7, 1386, 2048 }, { 8, 1387, 2048 }, { 7, 1388, 2048 }, { 8, 1389, 2048 }, { 8, 1390, 2048 }, { 9, 1391, 2048 },
2645    { 6, 1392, 2048 }, { 7, 1393, 2048 }, { 7, 1394, 2048 }, { 8, 1395, 2048 }, { 7, 1396, 2048 }, { 8, 1397, 2048 }, { 8, 1398, 2048 }, { 9, 1399, 2048 },
2646    { 7, 1400, 2048 }, { 8, 1401, 2048 }, { 8, 1402, 2048 }, { 9, 1403, 2048 }, { 8, 1404, 2048 }, { 9, 1405, 2048 }, { 9, 1406, 2048 }, { 10, 1407, 2048 },
2647    { 4, 1408, 2048 }, { 5, 1409, 2048 }, { 5, 1410, 2048 }, { 6, 1411, 2048 }, { 5, 1412, 2048 }, { 6, 1413, 2048 }, { 6, 1414, 2048 }, { 7, 1415, 2048 },
2648    { 5, 1416, 2048 }, { 6, 1417, 2048 }, { 6, 1418, 2048 }, { 7, 1419, 2048 }, { 6, 1420, 2048 }, { 7, 1421, 2048 }, { 7, 1422, 2048 }, { 8, 1423, 2048 },
2649    { 5, 1424, 2048 }, { 6, 1425, 2048 }, { 6, 1426, 2048 }, { 7, 1427, 2048 }, { 6, 1428, 2048 }, { 7, 1429, 2048 }, { 7, 1430, 2048 }, { 8, 1431, 2048 },
2650    { 6, 1432, 2048 }, { 7, 1433, 2048 }, { 7, 1434, 2048 }, { 8, 1435, 2048 }, { 7, 1436, 2048 }, { 8, 1437, 2048 }, { 8, 1438, 2048 }, { 9, 1439, 2048 },
2651    { 5, 1440, 2048 }, { 6, 1441, 2048 }, { 6, 1442, 2048 }, { 7, 1443, 2048 }, { 6, 1444, 2048 }, { 7, 1445, 2048 }, { 7, 1446, 2048 }, { 8, 1447, 2048 },
2652    { 6, 1448, 2048 }, { 7, 1449, 2048 }, { 7, 1450, 2048 }, { 8, 1451, 2048 }, { 7, 1452, 2048 }, { 8, 1453, 2048 }, { 8, 1454, 2048 }, { 9, 1455, 2048 },
2653    { 6, 1456, 2048 }, { 7, 1457, 2048 }, { 7, 1458, 2048 }, { 8, 1459, 2048 }, { 7, 1460, 2048 }, { 8, 1461, 2048 }, { 8, 1462, 2048 }, { 9, 1463, 2048 },
2654    { 7, 1464, 2048 }, { 8, 1465, 2048 }, { 8, 1466, 2048 }, { 9, 1467, 2048 }, { 8, 1468, 2048 }, { 9, 1469, 2048 }, { 9, 1470, 2048 }, { 10, 1471, 2048 },
2655    { 5, 1472, 2048 }, { 6, 1473, 2048 }, { 6, 1474, 2048 }, { 7, 1475, 2048 }, { 6, 1476, 2048 }, { 7, 1477, 2048 }, { 7, 1478, 2048 }, { 8, 1479, 2048 },
2656    { 6, 1480, 2048 }, { 7, 1481, 2048 }, { 7, 1482, 2048 }, { 8, 1483, 2048 }, { 7, 1484, 2048 }, { 8, 1485, 2048 }, { 8, 1486, 2048 }, { 9, 1487, 2048 },
2657    { 6, 1488, 2048 }, { 7, 1489, 2048 }, { 7, 1490, 2048 }, { 8, 1491, 2048 }, { 7, 1492, 2048 }, { 8, 1493, 2048 }, { 8, 1494, 2048 }, { 9, 1495, 2048 },
2658    { 7, 1496, 2048 }, { 8, 1497, 2048 }, { 8, 1498, 2048 }, { 9, 1499, 2048 }, { 8, 1500, 2048 }, { 9, 1501, 2048 }, { 9, 1502, 2048 }, { 10, 1503, 2048 },
2659    { 6, 1504, 2048 }, { 7, 1505, 2048 }, { 7, 1506, 2048 }, { 8, 1507, 2048 }, { 7, 1508, 2048 }, { 8, 1509, 2048 }, { 8, 1510, 2048 }, { 9, 1511, 2048 },
2660    { 7, 1512, 2048 }, { 8, 1513, 2048 }, { 8, 1514, 2048 }, { 9, 1515, 2048 }, { 8, 1516, 2048 }, { 9, 1517, 2048 }, { 9, 1518, 2048 }, { 10, 1519, 2048 },
2661    { 7, 1520, 2048 }, { 8, 1521, 2048 }, { 8, 1522, 2048 }, { 9, 1523, 2048 }, { 8, 1524, 2048 }, { 9, 1525, 2048 }, { 9, 1526, 2048 }, { 10, 1527, 2048 },
2662    { 8, 1528, 2048 }, { 9, 1529, 2048 }, { 9, 1530, 2048 }, { 10, 1531, 2048 }, { 9, 1532, 2048 }, { 10, 1533, 2048 }, { 10, 1534, 2048 }, { 11, 1535, 2048 },
2663    { 3, 1536, 2048 }, { 4, 1537, 2048 }, { 4, 1538, 2048 }, { 5, 1539, 2048 }, { 4, 1540, 2048 }, { 5, 1541, 2048 }, { 5, 1542, 2048 }, { 6, 1543, 2048 },
2664    { 4, 1544, 2048 }, { 5, 1545, 2048 }, { 5, 1546, 2048 }, { 6, 1547, 2048 }, { 5, 1548, 2048 }, { 6, 1549, 2048 }, { 6, 1550, 2048 }, { 7, 1551, 2048 },
2665    { 4, 1552, 2048 }, { 5, 1553, 2048 }, { 5, 1554, 2048 }, { 6, 1555, 2048 }, { 5, 1556, 2048 }, { 6, 1557, 2048 }, { 6, 1558, 2048 }, { 7, 1559, 2048 },
2666    { 5, 1560, 2048 }, { 6, 1561, 2048 }, { 6, 1562, 2048 }, { 7, 1563, 2048 }, { 6, 1564, 2048 }, { 7, 1565, 2048 }, { 7, 1566, 2048 }, { 8, 1567, 2048 },
2667    { 4, 1568, 2048 }, { 5, 1569, 2048 }, { 5, 1570, 2048 }, { 6, 1571, 2048 }, { 5, 1572, 2048 }, { 6, 1573, 2048 }, { 6, 1574, 2048 }, { 7, 1575, 2048 },
2668    { 5, 1576, 2048 }, { 6, 1577, 2048 }, { 6, 1578, 2048 }, { 7, 1579, 2048 }, { 6, 1580, 2048 }, { 7, 1581, 2048 }, { 7, 1582, 2048 }, { 8, 1583, 2048 },
2669    { 5, 1584, 2048 }, { 6, 1585, 2048 }, { 6, 1586, 2048 }, { 7, 1587, 2048 }, { 6, 1588, 2048 }, { 7, 1589, 2048 }, { 7, 1590, 2048 }, { 8, 1591, 2048 },
2670    { 6, 1592, 2048 }, { 7, 1593, 2048 }, { 7, 1594, 2048 }, { 8, 1595, 2048 }, { 7, 1596, 2048 }, { 8, 1597, 2048 }, { 8, 1598, 2048 }, { 9, 1599, 2048 },
2671    { 4, 1600, 2048 }, { 5, 1601, 2048 }, { 5, 1602, 2048 }, { 6, 1603, 2048 }, { 5, 1604, 2048 }, { 6, 1605, 2048 }, { 6, 1606, 2048 }, { 7, 1607, 2048 },
2672    { 5, 1608, 2048 }, { 6, 1609, 2048 }, { 6, 1610, 2048 }, { 7, 1611, 2048 }, { 6, 1612, 2048 }, { 7, 1613, 2048 }, { 7, 1614, 2048 }, { 8, 1615, 2048 },
2673    { 5, 1616, 2048 }, { 6, 1617, 2048 }, { 6, 1618, 2048 }, { 7, 1619, 2048 }, { 6, 1620, 2048 }, { 7, 1621, 2048 }, { 7, 1622, 2048 }, { 8, 1623, 2048 },
2674    { 6, 1624, 2048 }, { 7, 1625, 2048 }, { 7, 1626, 2048 }, { 8, 1627, 2048 }, { 7, 1628, 2048 }, { 8, 1629, 2048 }, { 8, 1630, 2048 }, { 9, 1631, 2048 },
2675    { 5, 1632, 2048 }, { 6, 1633, 2048 }, { 6, 1634, 2048 }, { 7, 1635, 2048 }, { 6, 1636, 2048 }, { 7, 1637, 2048 }, { 7, 1638, 2048 }, { 8, 1639, 2048 },
2676    { 6, 1640, 2048 }, { 7, 1641, 2048 }, { 7, 1642, 2048 }, { 8, 1643, 2048 }, { 7, 1644, 2048 }, { 8, 1645, 2048 }, { 8, 1646, 2048 }, { 9, 1647, 2048 },
2677    { 6, 1648, 2048 }, { 7, 1649, 2048 }, { 7, 1650, 2048 }, { 8, 1651, 2048 }, { 7, 1652, 2048 }, { 8, 1653, 2048 }, { 8, 1654, 2048 }, { 9, 1655, 2048 },
2678    { 7, 1656, 2048 }, { 8, 1657, 2048 }, { 8, 1658, 2048 }, { 9, 1659, 2048 }, { 8, 1660, 2048 }, { 9, 1661, 2048 }, { 9, 1662, 2048 }, { 10, 1663, 2048 },
2679    { 4, 1664, 2048 }, { 5, 1665, 2048 }, { 5, 1666, 2048 }, { 6, 1667, 2048 }, { 5, 1668, 2048 }, { 6, 1669, 2048 }, { 6, 1670, 2048 }, { 7, 1671, 2048 },
2680    { 5, 1672, 2048 }, { 6, 1673, 2048 }, { 6, 1674, 2048 }, { 7, 1675, 2048 }, { 6, 1676, 2048 }, { 7, 1677, 2048 }, { 7, 1678, 2048 }, { 8, 1679, 2048 },
2681    { 5, 1680, 2048 }, { 6, 1681, 2048 }, { 6, 1682, 2048 }, { 7, 1683, 2048 }, { 6, 1684, 2048 }, { 7, 1685, 2048 }, { 7, 1686, 2048 }, { 8, 1687, 2048 },
2682    { 6, 1688, 2048 }, { 7, 1689, 2048 }, { 7, 1690, 2048 }, { 8, 1691, 2048 }, { 7, 1692, 2048 }, { 8, 1693, 2048 }, { 8, 1694, 2048 }, { 9, 1695, 2048 },
2683    { 5, 1696, 2048 }, { 6, 1697, 2048 }, { 6, 1698, 2048 }, { 7, 1699, 2048 }, { 6, 1700, 2048 }, { 7, 1701, 2048 }, { 7, 1702, 2048 }, { 8, 1703, 2048 },
2684    { 6, 1704, 2048 }, { 7, 1705, 2048 }, { 7, 1706, 2048 }, { 8, 1707, 2048 }, { 7, 1708, 2048 }, { 8, 1709, 2048 }, { 8, 1710, 2048 }, { 9, 1711, 2048 },
2685    { 6, 1712, 2048 }, { 7, 1713, 2048 }, { 7, 1714, 2048 }, { 8, 1715, 2048 }, { 7, 1716, 2048 }, { 8, 1717, 2048 }, { 8, 1718, 2048 }, { 9, 1719, 2048 },
2686    { 7, 1720, 2048 }, { 8, 1721, 2048 }, { 8, 1722, 2048 }, { 9, 1723, 2048 }, { 8, 1724, 2048 }, { 9, 1725, 2048 }, { 9, 1726, 2048 }, { 10, 1727, 2048 },
2687    { 5, 1728, 2048 }, { 6, 1729, 2048 }, { 6, 1730, 2048 }, { 7, 1731, 2048 }, { 6, 1732, 2048 }, { 7, 1733, 2048 }, { 7, 1734, 2048 }, { 8, 1735, 2048 },
2688    { 6, 1736, 2048 }, { 7, 1737, 2048 }, { 7, 1738, 2048 }, { 8, 1739, 2048 }, { 7, 1740, 2048 }, { 8, 1741, 2048 }, { 8, 1742, 2048 }, { 9, 1743, 2048 },
2689    { 6, 1744, 2048 }, { 7, 1745, 2048 }, { 7, 1746, 2048 }, { 8, 1747, 2048 }, { 7, 1748, 2048 }, { 8, 1749, 2048 }, { 8, 1750, 2048 }, { 9, 1751, 2048 },
2690    { 7, 1752, 2048 }, { 8, 1753, 2048 }, { 8, 1754, 2048 }, { 9, 1755, 2048 }, { 8, 1756, 2048 }, { 9, 1757, 2048 }, { 9, 1758, 2048 }, { 10, 1759, 2048 },
2691    { 6, 1760, 2048 }, { 7, 1761, 2048 }, { 7, 1762, 2048 }, { 8, 1763, 2048 }, { 7, 1764, 2048 }, { 8, 1765, 2048 }, { 8, 1766, 2048 }, { 9, 1767, 2048 },
2692    { 7, 1768, 2048 }, { 8, 1769, 2048 }, { 8, 1770, 2048 }, { 9, 1771, 2048 }, { 8, 1772, 2048 }, { 9, 1773, 2048 }, { 9, 1774, 2048 }, { 10, 1775, 2048 },
2693    { 7, 1776, 2048 }, { 8, 1777, 2048 }, { 8, 1778, 2048 }, { 9, 1779, 2048 }, { 8, 1780, 2048 }, { 9, 1781, 2048 }, { 9, 1782, 2048 }, { 10, 1783, 2048 },
2694    { 8, 1784, 2048 }, { 9, 1785, 2048 }, { 9, 1786, 2048 }, { 10, 1787, 2048 }, { 9, 1788, 2048 }, { 10, 1789, 2048 }, { 10, 1790, 2048 }, { 11, 1791, 2048 },
2695    { 4, 1792, 2048 }, { 5, 1793, 2048 }, { 5, 1794, 2048 }, { 6, 1795, 2048 }, { 5, 1796, 2048 }, { 6, 1797, 2048 }, { 6, 1798, 2048 }, { 7, 1799, 2048 },
2696    { 5, 1800, 2048 }, { 6, 1801, 2048 }, { 6, 1802, 2048 }, { 7, 1803, 2048 }, { 6, 1804, 2048 }, { 7, 1805, 2048 }, { 7, 1806, 2048 }, { 8, 1807, 2048 },
2697    { 5, 1808, 2048 }, { 6, 1809, 2048 }, { 6, 1810, 2048 }, { 7, 1811, 2048 }, { 6, 1812, 2048 }, { 7, 1813, 2048 }, { 7, 1814, 2048 }, { 8, 1815, 2048 },
2698    { 6, 1816, 2048 }, { 7, 1817, 2048 }, { 7, 1818, 2048 }, { 8, 1819, 2048 }, { 7, 1820, 2048 }, { 8, 1821, 2048 }, { 8, 1822, 2048 }, { 9, 1823, 2048 },
2699    { 5, 1824, 2048 }, { 6, 1825, 2048 }, { 6, 1826, 2048 }, { 7, 1827, 2048 }, { 6, 1828, 2048 }, { 7, 1829, 2048 }, { 7, 1830, 2048 }, { 8, 1831, 2048 },
2700    { 6, 1832, 2048 }, { 7, 1833, 2048 }, { 7, 1834, 2048 }, { 8, 1835, 2048 }, { 7, 1836, 2048 }, { 8, 1837, 2048 }, { 8, 1838, 2048 }, { 9, 1839, 2048 },
2701    { 6, 1840, 2048 }, { 7, 1841, 2048 }, { 7, 1842, 2048 }, { 8, 1843, 2048 }, { 7, 1844, 2048 }, { 8, 1845, 2048 }, { 8, 1846, 2048 }, { 9, 1847, 2048 },
2702    { 7, 1848, 2048 }, { 8, 1849, 2048 }, { 8, 1850, 2048 }, { 9, 1851, 2048 }, { 8, 1852, 2048 }, { 9, 1853, 2048 }, { 9, 1854, 2048 }, { 10, 1855, 2048 },
2703    { 5, 1856, 2048 }, { 6, 1857, 2048 }, { 6, 1858, 2048 }, { 7, 1859, 2048 }, { 6, 1860, 2048 }, { 7, 1861, 2048 }, { 7, 1862, 2048 }, { 8, 1863, 2048 },
2704    { 6, 1864, 2048 }, { 7, 1865, 2048 }, { 7, 1866, 2048 }, { 8, 1867, 2048 }, { 7, 1868, 2048 }, { 8, 1869, 2048 }, { 8, 1870, 2048 }, { 9, 1871, 2048 },
2705    { 6, 1872, 2048 }, { 7, 1873, 2048 }, { 7, 1874, 2048 }, { 8, 1875, 2048 }, { 7, 1876, 2048 }, { 8, 1877, 2048 }, { 8, 1878, 2048 }, { 9, 1879, 2048 },
2706    { 7, 1880, 2048 }, { 8, 1881, 2048 }, { 8, 1882, 2048 }, { 9, 1883, 2048 }, { 8, 1884, 2048 }, { 9, 1885, 2048 }, { 9, 1886, 2048 }, { 10, 1887, 2048 },
2707    { 6, 1888, 2048 }, { 7, 1889, 2048 }, { 7, 1890, 2048 }, { 8, 1891, 2048 }, { 7, 1892, 2048 }, { 8, 1893, 2048 }, { 8, 1894, 2048 }, { 9, 1895, 2048 },
2708    { 7, 1896, 2048 }, { 8, 1897, 2048 }, { 8, 1898, 2048 }, { 9, 1899, 2048 }, { 8, 1900, 2048 }, { 9, 1901, 2048 }, { 9, 1902, 2048 }, { 10, 1903, 2048 },
2709    { 7, 1904, 2048 }, { 8, 1905, 2048 }, { 8, 1906, 2048 }, { 9, 1907, 2048 }, { 8, 1908, 2048 }, { 9, 1909, 2048 }, { 9, 1910, 2048 }, { 10, 1911, 2048 },
2710    { 8, 1912, 2048 }, { 9, 1913, 2048 }, { 9, 1914, 2048 }, { 10, 1915, 2048 }, { 9, 1916, 2048 }, { 10, 1917, 2048 }, { 10, 1918, 2048 }, { 11, 1919, 2048 },
2711    { 5, 1920, 2048 }, { 6, 1921, 2048 }, { 6, 1922, 2048 }, { 7, 1923, 2048 }, { 6, 1924, 2048 }, { 7, 1925, 2048 }, { 7, 1926, 2048 }, { 8, 1927, 2048 },
2712    { 6, 1928, 2048 }, { 7, 1929, 2048 }, { 7, 1930, 2048 }, { 8, 1931, 2048 }, { 7, 1932, 2048 }, { 8, 1933, 2048 }, { 8, 1934, 2048 }, { 9, 1935, 2048 },
2713    { 6, 1936, 2048 }, { 7, 1937, 2048 }, { 7, 1938, 2048 }, { 8, 1939, 2048 }, { 7, 1940, 2048 }, { 8, 1941, 2048 }, { 8, 1942, 2048 }, { 9, 1943, 2048 },
2714    { 7, 1944, 2048 }, { 8, 1945, 2048 }, { 8, 1946, 2048 }, { 9, 1947, 2048 }, { 8, 1948, 2048 }, { 9, 1949, 2048 }, { 9, 1950, 2048 }, { 10, 1951, 2048 },
2715    { 6, 1952, 2048 }, { 7, 1953, 2048 }, { 7, 1954, 2048 }, { 8, 1955, 2048 }, { 7, 1956, 2048 }, { 8, 1957, 2048 }, { 8, 1958, 2048 }, { 9, 1959, 2048 },
2716    { 7, 1960, 2048 }, { 8, 1961, 2048 }, { 8, 1962, 2048 }, { 9, 1963, 2048 }, { 8, 1964, 2048 }, { 9, 1965, 2048 }, { 9, 1966, 2048 }, { 10, 1967, 2048 },
2717    { 7, 1968, 2048 }, { 8, 1969, 2048 }, { 8, 1970, 2048 }, { 9, 1971, 2048 }, { 8, 1972, 2048 }, { 9, 1973, 2048 }, { 9, 1974, 2048 }, { 10, 1975, 2048 },
2718    { 8, 1976, 2048 }, { 9, 1977, 2048 }, { 9, 1978, 2048 }, { 10, 1979, 2048 }, { 9, 1980, 2048 }, { 10, 1981, 2048 }, { 10, 1982, 2048 }, { 11, 1983, 2048 },
2719    { 6, 1984, 2048 }, { 7, 1985, 2048 }, { 7, 1986, 2048 }, { 8, 1987, 2048 }, { 7, 1988, 2048 }, { 8, 1989, 2048 }, { 8, 1990, 2048 }, { 9, 1991, 2048 },
2720    { 7, 1992, 2048 }, { 8, 1993, 2048 }, { 8, 1994, 2048 }, { 9, 1995, 2048 }, { 8, 1996, 2048 }, { 9, 1997, 2048 }, { 9, 1998, 2048 }, { 10, 1999, 2048 },
2721    { 7, 2000, 2048 }, { 8, 2001, 2048 }, { 8, 2002, 2048 }, { 9, 2003, 2048 }, { 8, 2004, 2048 }, { 9, 2005, 2048 }, { 9, 2006, 2048 }, { 10, 2007, 2048 },
2722    { 8, 2008, 2048 }, { 9, 2009, 2048 }, { 9, 2010, 2048 }, { 10, 2011, 2048 }, { 9, 2012, 2048 }, { 10, 2013, 2048 }, { 10, 2014, 2048 }, { 11, 2015, 2048 },
2723    { 7, 2016, 2048 }, { 8, 2017, 2048 }, { 8, 2018, 2048 }, { 9, 2019, 2048 }, { 8, 2020, 2048 }, { 9, 2021, 2048 }, { 9, 2022, 2048 }, { 10, 2023, 2048 },
2724    { 8, 2024, 2048 }, { 9, 2025, 2048 }, { 9, 2026, 2048 }, { 10, 2027, 2048 }, { 9, 2028, 2048 }, { 10, 2029, 2048 }, { 10, 2030, 2048 }, { 11, 2031, 2048 },
2725    { 8, 2032, 2048 }, { 9, 2033, 2048 }, { 9, 2034, 2048 }, { 10, 2035, 2048 }, { 9, 2036, 2048 }, { 10, 2037, 2048 }, { 10, 2038, 2048 }, { 11, 2039, 2048 },
2726    { 9, 2040, 2048 }, { 10, 2041, 2048 }, { 10, 2042, 2048 }, { 11, 2043, 2048 }, { 10, 2044, 2048 }, { 11, 2045, 2048 }, { 11, 2046, 2048 }, { 12, 2047, 2048 },
2727 #endif
2728 #endif
2729 #endif
2730 #endif
2731 #endif
2732 #endif
2733 };
2734
2735 /* find a hole and free as required, return -1 if no hole found */
2736 static int find_hole(void)
2737 {
2738    unsigned x;
2739    int      y, z;
2740    for (z = -1, y = INT_MAX, x = 0; x < FP_ENTRIES; x++) {
2741        if (fp_cache[x].lru_count < y && fp_cache[x].lock == 0) {
2742           z = x;
2743           y = fp_cache[x].lru_count;
2744        }
2745    }
2746
2747    /* decrease all */
2748    for (x = 0; x < FP_ENTRIES; x++) {
2749       if (fp_cache[x].lru_count > 3) {
2750          --(fp_cache[x].lru_count);
2751       }
2752    }
2753
2754    /* free entry z */
2755    if (z >= 0 && fp_cache[z].g) {
2756       mp_clear(&fp_cache[z].mu);
2757       ecc_del_point(fp_cache[z].g);
2758       fp_cache[z].g  = NULL;
2759       for (x = 0; x < (1U<<FP_LUT); x++) {
2760          ecc_del_point(fp_cache[z].LUT[x]);
2761          fp_cache[z].LUT[x] = NULL;
2762       }
2763       fp_cache[z].lru_count = 0;
2764    }
2765    return z;
2766 }
2767
2768 /* determine if a base is already in the cache and if so, where */
2769 static int find_base(ecc_point* g)
2770 {
2771    int x;
2772    for (x = 0; x < FP_ENTRIES; x++) {
2773       if (fp_cache[x].g != NULL &&
2774           mp_cmp(&fp_cache[x].g->x, &g->x) == MP_EQ &&
2775           mp_cmp(&fp_cache[x].g->y, &g->y) == MP_EQ &&
2776           mp_cmp(&fp_cache[x].g->z, &g->z) == MP_EQ) {
2777          break;
2778       }
2779    }
2780    if (x == FP_ENTRIES) {
2781       x = -1;
2782    }
2783    return x;
2784 }
2785
2786 /* add a new base to the cache */
2787 static int add_entry(int idx, ecc_point *g)
2788 {
2789    unsigned x, y;
2790
2791    /* allocate base and LUT */
2792    fp_cache[idx].g = ecc_new_point();
2793    if (fp_cache[idx].g == NULL) {
2794       return GEN_MEM_ERR;
2795    }
2796
2797    /* copy x and y */
2798    if ((mp_copy(&g->x, &fp_cache[idx].g->x) != MP_OKAY) ||
2799        (mp_copy(&g->y, &fp_cache[idx].g->y) != MP_OKAY) ||
2800        (mp_copy(&g->z, &fp_cache[idx].g->z) != MP_OKAY)) {
2801       ecc_del_point(fp_cache[idx].g);
2802       fp_cache[idx].g = NULL;
2803       return GEN_MEM_ERR;
2804    }
2805
2806    for (x = 0; x < (1U<<FP_LUT); x++) {
2807       fp_cache[idx].LUT[x] = ecc_new_point();
2808       if (fp_cache[idx].LUT[x] == NULL) {
2809          for (y = 0; y < x; y++) {
2810             ecc_del_point(fp_cache[idx].LUT[y]);
2811             fp_cache[idx].LUT[y] = NULL;
2812          }
2813          ecc_del_point(fp_cache[idx].g);
2814          fp_cache[idx].g         = NULL;
2815          fp_cache[idx].lru_count = 0;
2816          return GEN_MEM_ERR;
2817       }
2818    }
2819
2820    fp_cache[idx].lru_count = 0;
2821
2822    return MP_OKAY;
2823 }
2824
2825 /* build the LUT by spacing the bits of the input by #modulus/FP_LUT bits apart
2826  *
2827  * The algorithm builds patterns in increasing bit order by first making all
2828  * single bit input patterns, then all two bit input patterns and so on
2829  */
2830 static int build_lut(int idx, mp_int* modulus, mp_digit* mp, mp_int* mu)
2831 {
2832    unsigned x, y, err, bitlen, lut_gap;
2833    mp_int tmp;
2834
2835    if (mp_init(&tmp) != MP_OKAY)
2836        return GEN_MEM_ERR;
2837
2838    /* sanity check to make sure lut_order table is of correct size,
2839       should compile out to a NOP if true */
2840    if ((sizeof(lut_orders) / sizeof(lut_orders[0])) < (1U<<FP_LUT)) {
2841        err = BAD_FUNC_ARG;
2842    }
2843    else {
2844     /* get bitlen and round up to next multiple of FP_LUT */
2845     bitlen  = mp_unsigned_bin_size(modulus) << 3;
2846     x       = bitlen % FP_LUT;
2847     if (x) {
2848       bitlen += FP_LUT - x;
2849     }
2850     lut_gap = bitlen / FP_LUT;
2851
2852     /* init the mu */
2853     err = mp_init_copy(&fp_cache[idx].mu, mu);
2854    }
2855
2856    /* copy base */
2857    if (err == MP_OKAY) {
2858      if ((mp_mulmod(&fp_cache[idx].g->x, mu, modulus,
2859                   &fp_cache[idx].LUT[1]->x) != MP_OKAY) ||
2860          (mp_mulmod(&fp_cache[idx].g->y, mu, modulus,
2861                   &fp_cache[idx].LUT[1]->y) != MP_OKAY) ||
2862          (mp_mulmod(&fp_cache[idx].g->z, mu, modulus,
2863                   &fp_cache[idx].LUT[1]->z) != MP_OKAY)) {
2864        err = MP_MULMOD_E;
2865      }
2866    }
2867
2868    /* make all single bit entries */
2869    for (x = 1; x < FP_LUT; x++) {
2870       if (err != MP_OKAY)
2871           break;
2872       if ((mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->x,
2873                    &fp_cache[idx].LUT[1<<x]->x) != MP_OKAY) ||
2874           (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->y,
2875                    &fp_cache[idx].LUT[1<<x]->y) != MP_OKAY) ||
2876           (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->z,
2877                    &fp_cache[idx].LUT[1<<x]->z) != MP_OKAY)){
2878           err = MP_INIT_E;
2879           break;
2880       } else {
2881
2882          /* now double it bitlen/FP_LUT times */
2883          for (y = 0; y < lut_gap; y++) {
2884              if ((err = ecc_projective_dbl_point(fp_cache[idx].LUT[1<<x],
2885                             fp_cache[idx].LUT[1<<x], modulus, mp)) != MP_OKAY) {
2886                  break;
2887              }
2888          }
2889      }
2890   }
2891
2892    /* now make all entries in increase order of hamming weight */
2893    for (x = 2; x <= FP_LUT; x++) {
2894        if (err != MP_OKAY)
2895            break;
2896        for (y = 0; y < (1UL<<FP_LUT); y++) {
2897            if (err != MP_OKAY)
2898              break;
2899            if (lut_orders[y].ham != (int)x) continue;
2900
2901            /* perform the add */
2902            if ((err = ecc_projective_add_point(
2903                            fp_cache[idx].LUT[lut_orders[y].terma],
2904                            fp_cache[idx].LUT[lut_orders[y].termb],
2905                            fp_cache[idx].LUT[y], modulus, mp)) != MP_OKAY) {
2906               break;
2907            }
2908        }
2909    }
2910
2911    /* now map all entries back to affine space to make point addition faster */
2912    for (x = 1; x < (1UL<<FP_LUT); x++) {
2913        if (err != MP_OKAY)
2914            break;
2915
2916        /* convert z to normal from montgomery */
2917        err = mp_montgomery_reduce(&fp_cache[idx].LUT[x]->z, modulus, *mp);
2918
2919        /* invert it */
2920        if (err == MP_OKAY)
2921          err = mp_invmod(&fp_cache[idx].LUT[x]->z, modulus,
2922                          &fp_cache[idx].LUT[x]->z);
2923
2924        if (err == MP_OKAY)
2925          /* now square it */
2926          err = mp_sqrmod(&fp_cache[idx].LUT[x]->z, modulus, &tmp);
2927
2928        if (err == MP_OKAY)
2929          /* fix x */
2930          err = mp_mulmod(&fp_cache[idx].LUT[x]->x, &tmp, modulus,
2931                          &fp_cache[idx].LUT[x]->x);
2932
2933        if (err == MP_OKAY)
2934          /* get 1/z^3 */
2935          err = mp_mulmod(&tmp, &fp_cache[idx].LUT[x]->z, modulus, &tmp);
2936
2937        if (err == MP_OKAY)
2938          /* fix y */
2939          err = mp_mulmod(&fp_cache[idx].LUT[x]->y, &tmp, modulus,
2940                          &fp_cache[idx].LUT[x]->y);
2941
2942        if (err == MP_OKAY)
2943          /* free z */
2944          mp_clear(&fp_cache[idx].LUT[x]->z);
2945    }
2946    mp_clear(&tmp);
2947
2948    if (err == MP_OKAY)
2949      return MP_OKAY;
2950
2951    /* err cleanup */
2952    for (y = 0; y < (1U<<FP_LUT); y++) {
2953       ecc_del_point(fp_cache[idx].LUT[y]);
2954       fp_cache[idx].LUT[y] = NULL;
2955    }
2956    ecc_del_point(fp_cache[idx].g);
2957    fp_cache[idx].g         = NULL;
2958    fp_cache[idx].lru_count = 0;
2959    mp_clear(&fp_cache[idx].mu);
2960    mp_clear(&tmp);
2961
2962    return err;
2963 }
2964
2965 /* perform a fixed point ECC mulmod */
2966 static int accel_fp_mul(int idx, mp_int* k, ecc_point *R, mp_int* modulus,
2967                         mp_digit* mp, int map)
2968 {
2969 #define KB_SIZE 128
2970
2971 #ifdef CYASSL_SMALL_STACK
2972    unsigned char* kb;
2973 #else
2974    unsigned char kb[128];
2975 #endif
2976    int      x;
2977    unsigned y, z, err, bitlen, bitpos, lut_gap, first;
2978    mp_int   tk;
2979
2980    if (mp_init(&tk) != MP_OKAY)
2981        return MP_INIT_E;
2982
2983    /* if it's smaller than modulus we fine */
2984    if (mp_unsigned_bin_size(k) > mp_unsigned_bin_size(modulus)) {
2985       mp_int order;
2986       if (mp_init(&order) != MP_OKAY) {
2987         mp_clear(&tk);
2988         return MP_INIT_E;
2989       }
2990
2991       /* find order */
2992       y = mp_unsigned_bin_size(modulus);
2993       for (x = 0; ecc_sets[x].size; x++) {
2994          if (y <= (unsigned)ecc_sets[x].size) break;
2995       }
2996
2997       /* back off if we are on the 521 bit curve */
2998       if (y == 66) --x;
2999
3000       if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
3001          mp_clear(&order);
3002          mp_clear(&tk);
3003          return err;
3004       }
3005
3006       /* k must be less than modulus */
3007       if (mp_cmp(k, &order) != MP_LT) {
3008          if ((err = mp_mod(k, &order, &tk)) != MP_OKAY) {
3009             mp_clear(&tk);
3010             mp_clear(&order);
3011             return err;
3012          }
3013       } else {
3014          mp_copy(k, &tk);
3015       }
3016       mp_clear(&order);
3017    } else {
3018       mp_copy(k, &tk);
3019    }
3020
3021    /* get bitlen and round up to next multiple of FP_LUT */
3022    bitlen  = mp_unsigned_bin_size(modulus) << 3;
3023    x       = bitlen % FP_LUT;
3024    if (x) {
3025       bitlen += FP_LUT - x;
3026    }
3027    lut_gap = bitlen / FP_LUT;
3028
3029    /* get the k value */
3030    if (mp_unsigned_bin_size(&tk) > (int)(KB_SIZE - 2)) {
3031       mp_clear(&tk);
3032       return BUFFER_E;
3033    }
3034
3035    /* store k */
3036 #ifdef CYASSL_SMALL_STACK
3037    kb = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3038    if (kb == NULL)
3039       return MEMORY_E;
3040 #endif
3041
3042    XMEMSET(kb, 0, KB_SIZE);
3043    if ((err = mp_to_unsigned_bin(&tk, kb)) != MP_OKAY) {
3044       mp_clear(&tk);
3045    }
3046    else {
3047       /* let's reverse kb so it's little endian */
3048       x = 0;
3049       y = mp_unsigned_bin_size(&tk) - 1;
3050       mp_clear(&tk);
3051
3052       while ((unsigned)x < y) {
3053          z = kb[x]; kb[x] = kb[y]; kb[y] = z;
3054          ++x; --y;
3055       }
3056
3057       /* at this point we can start, yipee */
3058       first = 1;
3059       for (x = lut_gap-1; x >= 0; x--) {
3060           /* extract FP_LUT bits from kb spread out by lut_gap bits and offset
3061              by x bits from the start */
3062           bitpos = x;
3063           for (y = z = 0; y < FP_LUT; y++) {
3064              z |= ((kb[bitpos>>3] >> (bitpos&7)) & 1) << y;
3065              bitpos += lut_gap;  /* it's y*lut_gap + x, but here we can avoid
3066                                     the mult in each loop */
3067           }
3068
3069           /* double if not first */
3070           if (!first) {
3071              if ((err = ecc_projective_dbl_point(R, R, modulus,
3072                                                               mp)) != MP_OKAY) {
3073                 break;
3074              }
3075           }
3076
3077           /* add if not first, otherwise copy */
3078           if (!first && z) {
3079              if ((err = ecc_projective_add_point(R, fp_cache[idx].LUT[z], R,
3080                                                      modulus, mp)) != MP_OKAY) {
3081                 break;
3082              }
3083           } else if (z) {
3084              if ((mp_copy(&fp_cache[idx].LUT[z]->x, &R->x) != MP_OKAY) ||
3085                  (mp_copy(&fp_cache[idx].LUT[z]->y, &R->y) != MP_OKAY) ||
3086                  (mp_copy(&fp_cache[idx].mu,        &R->z) != MP_OKAY)) {
3087                  err = GEN_MEM_ERR;
3088                  break;
3089              }
3090                  first = 0;
3091           }
3092       }
3093    }
3094
3095    if (err == MP_OKAY) {
3096       z = 0;
3097       XMEMSET(kb, 0, KB_SIZE);
3098       /* map R back from projective space */
3099       if (map) {
3100          err = ecc_map(R, modulus, mp);
3101       } else {
3102          err = MP_OKAY;
3103       }
3104    }
3105
3106 #ifdef CYASSL_SMALL_STACK
3107    XFREE(kb, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3108 #endif
3109
3110 #undef KB_SIZE
3111
3112    return err;
3113 }
3114
3115 #ifdef ECC_SHAMIR
3116 /* perform a fixed point ECC mulmod */
3117 static int accel_fp_mul2add(int idx1, int idx2,
3118                             mp_int* kA, mp_int* kB,
3119                             ecc_point *R, mp_int* modulus, mp_digit* mp)
3120 {
3121 #define KB_SIZE 128
3122
3123 #ifdef CYASSL_SMALL_STACK
3124    unsigned char* kb[2];
3125 #else
3126    unsigned char kb[2][128];
3127 #endif
3128    int      x;
3129    unsigned y, z, err, bitlen, bitpos, lut_gap, first, zA, zB;
3130    mp_int tka;
3131    mp_int tkb;
3132    mp_int order;
3133
3134    if (mp_init_multi(&tka, &tkb, 0, 0, 0, 0) != MP_OKAY)
3135        return MP_INIT_E;
3136
3137    /* if it's smaller than modulus we fine */
3138    if (mp_unsigned_bin_size(kA) > mp_unsigned_bin_size(modulus)) {
3139       /* find order */
3140       y = mp_unsigned_bin_size(modulus);
3141       for (x = 0; ecc_sets[x].size; x++) {
3142          if (y <= (unsigned)ecc_sets[x].size) break;
3143       }
3144
3145       /* back off if we are on the 521 bit curve */
3146       if (y == 66) --x;
3147
3148       if ((err = mp_init(&order)) != MP_OKAY) {
3149          mp_clear(&tkb);
3150          mp_clear(&tka);
3151          return err;
3152       }
3153       if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
3154          mp_clear(&tkb);
3155          mp_clear(&tka);
3156          mp_clear(&order);
3157          return err;
3158       }
3159
3160       /* kA must be less than modulus */
3161       if (mp_cmp(kA, &order) != MP_LT) {
3162          if ((err = mp_mod(kA, &order, &tka)) != MP_OKAY) {
3163             mp_clear(&tkb);
3164             mp_clear(&tka);
3165             mp_clear(&order);
3166             return err;
3167          }
3168       } else {
3169          mp_copy(kA, &tka);
3170       }
3171       mp_clear(&order);
3172    } else {
3173       mp_copy(kA, &tka);
3174    }
3175
3176    /* if it's smaller than modulus we fine */
3177    if (mp_unsigned_bin_size(kB) > mp_unsigned_bin_size(modulus)) {
3178       /* find order */
3179       y = mp_unsigned_bin_size(modulus);
3180       for (x = 0; ecc_sets[x].size; x++) {
3181          if (y <= (unsigned)ecc_sets[x].size) break;
3182       }
3183
3184       /* back off if we are on the 521 bit curve */
3185       if (y == 66) --x;
3186
3187       if ((err = mp_init(&order)) != MP_OKAY) {
3188          mp_clear(&tkb);
3189          mp_clear(&tka);
3190          return err;
3191       }
3192       if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
3193          mp_clear(&tkb);
3194          mp_clear(&tka);
3195          mp_clear(&order);
3196          return err;
3197       }
3198
3199       /* kB must be less than modulus */
3200       if (mp_cmp(kB, &order) != MP_LT) {
3201          if ((err = mp_mod(kB, &order, &tkb)) != MP_OKAY) {
3202             mp_clear(&tkb);
3203             mp_clear(&tka);
3204             mp_clear(&order);
3205             return err;
3206          }
3207       } else {
3208          mp_copy(kB, &tkb);
3209       }
3210       mp_clear(&order);
3211    } else {
3212       mp_copy(kB, &tkb);
3213    }
3214
3215    /* get bitlen and round up to next multiple of FP_LUT */
3216    bitlen  = mp_unsigned_bin_size(modulus) << 3;
3217    x       = bitlen % FP_LUT;
3218    if (x) {
3219       bitlen += FP_LUT - x;
3220    }
3221    lut_gap = bitlen / FP_LUT;
3222
3223    /* get the k value */
3224    if ((mp_unsigned_bin_size(&tka) > (int)(KB_SIZE - 2)) ||
3225        (mp_unsigned_bin_size(&tkb) > (int)(KB_SIZE - 2))  ) {
3226       mp_clear(&tka);
3227       mp_clear(&tkb);
3228       return BUFFER_E;
3229    }
3230
3231    /* store k */
3232 #ifdef CYASSL_SMALL_STACK
3233    kb[0] = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3234    if (kb[0] == NULL)
3235       return MEMORY_E;
3236 #endif
3237
3238    XMEMSET(kb[0], 0, KB_SIZE);
3239    if ((err = mp_to_unsigned_bin(&tka, kb[0])) != MP_OKAY) {
3240       mp_clear(&tka);
3241       mp_clear(&tkb);
3242       XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3243       return err;
3244    }
3245
3246    /* let's reverse kb so it's little endian */
3247    x = 0;
3248    y = mp_unsigned_bin_size(&tka) - 1;
3249    mp_clear(&tka);
3250    while ((unsigned)x < y) {
3251       z = kb[0][x]; kb[0][x] = kb[0][y]; kb[0][y] = z;
3252       ++x; --y;
3253    }
3254
3255    /* store b */
3256 #ifdef CYASSL_SMALL_STACK
3257    kb[1] = (unsigned char*)XMALLOC(KB_SIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3258    if (kb[1] == NULL) {
3259       XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3260       return MEMORY_E;
3261    }
3262 #endif
3263
3264    XMEMSET(kb[1], 0, KB_SIZE);
3265    if ((err = mp_to_unsigned_bin(&tkb, kb[1])) != MP_OKAY) {
3266       mp_clear(&tkb);
3267    }
3268    else {
3269       x = 0;
3270       y = mp_unsigned_bin_size(&tkb) - 1;
3271       mp_clear(&tkb);
3272       while ((unsigned)x < y) {
3273          z = kb[1][x]; kb[1][x] = kb[1][y]; kb[1][y] = z;
3274          ++x; --y;
3275       }
3276
3277       /* at this point we can start, yipee */
3278       first = 1;
3279       for (x = lut_gap-1; x >= 0; x--) {
3280           /* extract FP_LUT bits from kb spread out by lut_gap bits and
3281              offset by x bits from the start */
3282           bitpos = x;
3283           for (y = zA = zB = 0; y < FP_LUT; y++) {
3284              zA |= ((kb[0][bitpos>>3] >> (bitpos&7)) & 1) << y;
3285              zB |= ((kb[1][bitpos>>3] >> (bitpos&7)) & 1) << y;
3286              bitpos += lut_gap;    /* it's y*lut_gap + x, but here we can avoid
3287                                       the mult in each loop */
3288           }
3289
3290           /* double if not first */
3291           if (!first) {
3292              if ((err = ecc_projective_dbl_point(R, R, modulus,
3293                                                               mp)) != MP_OKAY) {
3294                 break;
3295              }
3296           }
3297
3298           /* add if not first, otherwise copy */
3299           if (!first) {
3300              if (zA) {
3301                 if ((err = ecc_projective_add_point(R, fp_cache[idx1].LUT[zA],
3302                                                   R, modulus, mp)) != MP_OKAY) {
3303                    break;
3304                 }
3305              }
3306              if (zB) {
3307                 if ((err = ecc_projective_add_point(R, fp_cache[idx2].LUT[zB],
3308                                                   R, modulus, mp)) != MP_OKAY) {
3309                    break;
3310                 }
3311              }
3312           } else {
3313              if (zA) {
3314                  if ((mp_copy(&fp_cache[idx1].LUT[zA]->x, &R->x) != MP_OKAY) ||
3315                     (mp_copy(&fp_cache[idx1].LUT[zA]->y,  &R->y) != MP_OKAY) ||
3316                     (mp_copy(&fp_cache[idx1].mu,          &R->z) != MP_OKAY)) {
3317                      err = GEN_MEM_ERR;
3318                      break;
3319                  }
3320                     first = 0;
3321              }
3322              if (zB && first == 0) {
3323                 if (zB) {
3324                    if ((err = ecc_projective_add_point(R,
3325                            fp_cache[idx2].LUT[zB], R, modulus, mp)) != MP_OKAY){
3326                       break;
3327                    }
3328                 }
3329              } else if (zB && first == 1) {
3330                  if ((mp_copy(&fp_cache[idx2].LUT[zB]->x, &R->x) != MP_OKAY) ||
3331                     (mp_copy(&fp_cache[idx2].LUT[zB]->y, &R->y) != MP_OKAY) ||
3332                     (mp_copy(&fp_cache[idx2].mu,        &R->z) != MP_OKAY)) {
3333                      err = GEN_MEM_ERR;
3334                      break;
3335                  }
3336                     first = 0;
3337              }
3338           }
3339       }
3340    }
3341
3342    XMEMSET(kb[0], 0, KB_SIZE);
3343    XMEMSET(kb[1], 0, KB_SIZE);
3344
3345 #ifdef CYASSL_SMALL_STACK
3346    XFREE(kb[0], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3347    XFREE(kb[1], NULL, DYNAMIC_TYPE_TMP_BUFFER);
3348 #endif
3349
3350 #undef KB_SIZE
3351
3352    return ecc_map(R, modulus, mp);
3353 }
3354
3355 /** ECC Fixed Point mulmod global
3356   Computes kA*A + kB*B = C using Shamir's Trick
3357   A        First point to multiply
3358   kA       What to multiple A by
3359   B        Second point to multiply
3360   kB       What to multiple B by
3361   C        [out] Destination point (can overlap with A or B)
3362   modulus  Modulus for curve
3363   return MP_OKAY on success
3364 */
3365 int ecc_mul2add(ecc_point* A, mp_int* kA,
3366                 ecc_point* B, mp_int* kB,
3367                 ecc_point* C, mp_int* modulus)
3368 {
3369    int  idx1 = -1, idx2 = -1, err = MP_OKAY, mpInit = 0;
3370    mp_digit mp;
3371    mp_int   mu;
3372
3373    err = mp_init(&mu);
3374    if (err != MP_OKAY)
3375        return err;
3376
3377 #ifndef HAVE_THREAD_LS
3378    if (initMutex == 0) {
3379         InitMutex(&ecc_fp_lock);
3380         initMutex = 1;
3381    }
3382    if (LockMutex(&ecc_fp_lock) != 0)
3383       return BAD_MUTEX_E;
3384 #endif /* HAVE_THREAD_LS */
3385
3386       /* find point */
3387       idx1 = find_base(A);
3388
3389       /* no entry? */
3390       if (idx1 == -1) {
3391          /* find hole and add it */
3392          if ((idx1 = find_hole()) >= 0) {
3393             err = add_entry(idx1, A);
3394          }
3395       }
3396       if (err == MP_OKAY && idx1 != -1) {
3397          /* increment LRU */
3398          ++(fp_cache[idx1].lru_count);
3399       }
3400
3401       if (err == MP_OKAY)
3402         /* find point */
3403         idx2 = find_base(B);
3404
3405       if (err == MP_OKAY) {
3406         /* no entry? */
3407         if (idx2 == -1) {
3408            /* find hole and add it */
3409            if ((idx2 = find_hole()) >= 0)
3410               err = add_entry(idx2, B);
3411          }
3412       }
3413
3414       if (err == MP_OKAY && idx2 != -1) {
3415          /* increment LRU */
3416          ++(fp_cache[idx2].lru_count);
3417       }
3418
3419       if (err == MP_OKAY) {
3420         /* if it's 2 build the LUT, if it's higher just use the LUT */
3421         if (idx1 >= 0 && fp_cache[idx1].lru_count == 2) {
3422            /* compute mp */
3423            err = mp_montgomery_setup(modulus, &mp);
3424
3425            if (err == MP_OKAY) {
3426              mpInit = 1;
3427              err = mp_montgomery_calc_normalization(&mu, modulus);
3428            }
3429
3430            if (err == MP_OKAY)
3431              /* build the LUT */
3432                err = build_lut(idx1, modulus, &mp, &mu);
3433         }
3434       }
3435
3436       if (err == MP_OKAY) {
3437         /* if it's 2 build the LUT, if it's higher just use the LUT */
3438         if (idx2 >= 0 && fp_cache[idx2].lru_count == 2) {
3439            if (mpInit == 0) {
3440                 /* compute mp */
3441                 err = mp_montgomery_setup(modulus, &mp);
3442                 if (err == MP_OKAY) {
3443                     mpInit = 1;
3444                     err = mp_montgomery_calc_normalization(&mu, modulus);
3445                 }
3446             }
3447
3448             if (err == MP_OKAY)
3449             /* build the LUT */
3450               err = build_lut(idx2, modulus, &mp, &mu);
3451         }
3452       }
3453
3454
3455       if (err == MP_OKAY) {
3456         if (idx1 >=0 && idx2 >= 0 && fp_cache[idx1].lru_count >= 2 &&
3457                                      fp_cache[idx2].lru_count >= 2) {
3458            if (mpInit == 0) {
3459               /* compute mp */
3460               err = mp_montgomery_setup(modulus, &mp);
3461            }
3462            if (err == MP_OKAY)
3463              err = accel_fp_mul2add(idx1, idx2, kA, kB, C, modulus, &mp);
3464         } else {
3465            err = normal_ecc_mul2add(A, kA, B, kB, C, modulus);
3466         }
3467     }
3468
3469 #ifndef HAVE_THREAD_LS
3470     UnLockMutex(&ecc_fp_lock);
3471 #endif /* HAVE_THREAD_LS */
3472     mp_clear(&mu);
3473
3474     return err;
3475 }
3476 #endif
3477
3478 /** ECC Fixed Point mulmod global
3479     k        The multiplicand
3480     G        Base point to multiply
3481     R        [out] Destination of product
3482     modulus  The modulus for the curve
3483     map      [boolean] If non-zero maps the point back to affine co-ordinates,
3484              otherwise it's left in jacobian-montgomery form
3485     return MP_OKAY if successful
3486 */
3487 int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
3488                int map)
3489 {
3490    int   idx, err = MP_OKAY;
3491    mp_digit mp;
3492    mp_int   mu;
3493    int      mpSetup = 0;
3494
3495    if (mp_init(&mu) != MP_OKAY)
3496        return MP_INIT_E;
3497
3498 #ifndef HAVE_THREAD_LS
3499    if (initMutex == 0) {
3500         InitMutex(&ecc_fp_lock);
3501         initMutex = 1;
3502    }
3503
3504    if (LockMutex(&ecc_fp_lock) != 0)
3505       return BAD_MUTEX_E;
3506 #endif /* HAVE_THREAD_LS */
3507
3508       /* find point */
3509       idx = find_base(G);
3510
3511       /* no entry? */
3512       if (idx == -1) {
3513          /* find hole and add it */
3514          idx = find_hole();
3515
3516          if (idx >= 0)
3517             err = add_entry(idx, G);
3518       }
3519       if (err == MP_OKAY && idx != -1) {
3520          /* increment LRU */
3521          ++(fp_cache[idx].lru_count);
3522       }
3523
3524
3525       if (err == MP_OKAY) {
3526         /* if it's 2 build the LUT, if it's higher just use the LUT */
3527         if (idx >= 0 && fp_cache[idx].lru_count == 2) {
3528            /* compute mp */
3529            err = mp_montgomery_setup(modulus, &mp);
3530
3531            if (err == MP_OKAY) {
3532              /* compute mu */
3533              mpSetup = 1;
3534              err = mp_montgomery_calc_normalization(&mu, modulus);
3535            }
3536
3537            if (err == MP_OKAY)
3538              /* build the LUT */
3539              err = build_lut(idx, modulus, &mp, &mu);
3540         }
3541       }
3542
3543       if (err == MP_OKAY) {
3544         if (idx >= 0 && fp_cache[idx].lru_count >= 2) {
3545            if (mpSetup == 0) {
3546               /* compute mp */
3547               err = mp_montgomery_setup(modulus, &mp);
3548            }
3549            if (err == MP_OKAY)
3550              err = accel_fp_mul(idx, k, R, modulus, &mp, map);
3551         } else {
3552            err = normal_ecc_mulmod(k, G, R, modulus, map);
3553         }
3554      }
3555
3556 #ifndef HAVE_THREAD_LS
3557     UnLockMutex(&ecc_fp_lock);
3558 #endif /* HAVE_THREAD_LS */
3559     mp_clear(&mu);
3560
3561     return err;
3562 }
3563
3564 /* helper function for freeing the cache ...
3565    must be called with the cache mutex locked */
3566 static void ecc_fp_free_cache(void)
3567 {
3568    unsigned x, y;
3569    for (x = 0; x < FP_ENTRIES; x++) {
3570       if (fp_cache[x].g != NULL) {
3571          for (y = 0; y < (1U<<FP_LUT); y++) {
3572             ecc_del_point(fp_cache[x].LUT[y]);
3573             fp_cache[x].LUT[y] = NULL;
3574          }
3575          ecc_del_point(fp_cache[x].g);
3576          fp_cache[x].g         = NULL;
3577          mp_clear(&fp_cache[x].mu);
3578          fp_cache[x].lru_count = 0;
3579          fp_cache[x].lock = 0;
3580       }
3581    }
3582 }
3583
3584 /** Free the Fixed Point cache */
3585 void ecc_fp_free(void)
3586 {
3587 #ifndef HAVE_THREAD_LS
3588    if (initMutex == 0) {
3589         InitMutex(&ecc_fp_lock);
3590         initMutex = 1;
3591    }
3592
3593    if (LockMutex(&ecc_fp_lock) == 0) {
3594 #endif /* HAVE_THREAD_LS */
3595
3596        ecc_fp_free_cache();
3597
3598 #ifndef HAVE_THREAD_LS
3599        UnLockMutex(&ecc_fp_lock);
3600        FreeMutex(&ecc_fp_lock);
3601        initMutex = 0;
3602    }
3603 #endif /* HAVE_THREAD_LS */
3604 }
3605
3606
3607 #endif /* FP_ECC */
3608
3609 #ifdef HAVE_ECC_ENCRYPT
3610
3611
3612 enum ecCliState {
3613     ecCLI_INIT      = 1,
3614     ecCLI_SALT_GET  = 2,
3615     ecCLI_SALT_SET  = 3,
3616     ecCLI_SENT_REQ  = 4,
3617     ecCLI_RECV_RESP = 5,
3618     ecCLI_BAD_STATE = 99
3619 };
3620
3621 enum ecSrvState {
3622     ecSRV_INIT      = 1,
3623     ecSRV_SALT_GET  = 2,
3624     ecSRV_SALT_SET  = 3,
3625     ecSRV_RECV_REQ  = 4,
3626     ecSRV_SENT_RESP = 5,
3627     ecSRV_BAD_STATE = 99
3628 };
3629
3630
3631 struct ecEncCtx {
3632     const byte* kdfSalt;   /* optional salt for kdf */
3633     const byte* kdfInfo;   /* optional info for kdf */
3634     const byte* macSalt;   /* optional salt for mac */
3635     word32    kdfSaltSz;   /* size of kdfSalt */
3636     word32    kdfInfoSz;   /* size of kdfInfo */
3637     word32    macSaltSz;   /* size of macSalt */
3638     byte      clientSalt[EXCHANGE_SALT_SZ];  /* for msg exchange */
3639     byte      serverSalt[EXCHANGE_SALT_SZ];  /* for msg exchange */
3640     byte      encAlgo;     /* which encryption type */
3641     byte      kdfAlgo;     /* which key derivation function type */
3642     byte      macAlgo;     /* which mac function type */
3643     byte      protocol;    /* are we REQ_RESP client or server ? */
3644     byte      cliSt;       /* protocol state, for sanity checks */
3645     byte      srvSt;       /* protocol state, for sanity checks */
3646 };
3647
3648
3649 const byte* ecc_ctx_get_own_salt(ecEncCtx* ctx)
3650 {
3651     if (ctx == NULL || ctx->protocol == 0)
3652         return NULL;
3653
3654     if (ctx->protocol == REQ_RESP_CLIENT) {
3655         if (ctx->cliSt == ecCLI_INIT) {
3656             ctx->cliSt =  ecCLI_SALT_GET;
3657             return ctx->clientSalt;
3658         }
3659         else {
3660             ctx->cliSt = ecCLI_BAD_STATE;
3661             return NULL;
3662         }
3663     }
3664     else if (ctx->protocol == REQ_RESP_SERVER) {
3665         if (ctx->srvSt == ecSRV_INIT) {
3666             ctx->srvSt =  ecSRV_SALT_GET;
3667             return ctx->serverSalt;
3668         }
3669         else {
3670             ctx->srvSt = ecSRV_BAD_STATE;
3671             return NULL;
3672         }
3673     }
3674
3675     return NULL;
3676 }
3677
3678
3679 /* optional set info, can be called before or after set_peer_salt */
3680 int ecc_ctx_set_info(ecEncCtx* ctx, const byte* info, int sz)
3681 {
3682     if (ctx == NULL || info == 0 || sz < 0)
3683         return BAD_FUNC_ARG;
3684
3685     ctx->kdfInfo   = info;
3686     ctx->kdfInfoSz = sz;
3687
3688     return 0;
3689 }
3690
3691
3692 static const char* exchange_info = "Secure Message Exchange";
3693
3694 int ecc_ctx_set_peer_salt(ecEncCtx* ctx, const byte* salt)
3695 {
3696     byte tmp[EXCHANGE_SALT_SZ/2];
3697     int  halfSz = EXCHANGE_SALT_SZ/2;
3698
3699     if (ctx == NULL || ctx->protocol == 0 || salt == NULL)
3700         return BAD_FUNC_ARG;
3701
3702     if (ctx->protocol == REQ_RESP_CLIENT) {
3703         XMEMCPY(ctx->serverSalt, salt, EXCHANGE_SALT_SZ);
3704         if (ctx->cliSt == ecCLI_SALT_GET)
3705             ctx->cliSt =  ecCLI_SALT_SET;
3706         else {
3707             ctx->cliSt =  ecCLI_BAD_STATE;
3708             return BAD_ENC_STATE_E;
3709         }
3710     }
3711     else {
3712         XMEMCPY(ctx->clientSalt, salt, EXCHANGE_SALT_SZ);
3713         if (ctx->srvSt == ecSRV_SALT_GET)
3714             ctx->srvSt =  ecSRV_SALT_SET;
3715         else {
3716             ctx->srvSt =  ecSRV_BAD_STATE;
3717             return BAD_ENC_STATE_E;
3718         }
3719     }
3720
3721     /* mix half and half */
3722     /* tmp stores 2nd half of client before overwrite */
3723     XMEMCPY(tmp, ctx->clientSalt + halfSz, halfSz);
3724     XMEMCPY(ctx->clientSalt + halfSz, ctx->serverSalt, halfSz);
3725     XMEMCPY(ctx->serverSalt, tmp, halfSz);
3726
3727     ctx->kdfSalt   = ctx->clientSalt;
3728     ctx->kdfSaltSz = EXCHANGE_SALT_SZ;
3729
3730     ctx->macSalt   = ctx->serverSalt;
3731     ctx->macSaltSz = EXCHANGE_SALT_SZ;
3732
3733     if (ctx->kdfInfo == NULL) {
3734         /* default info */
3735         ctx->kdfInfo   = (const byte*)exchange_info;
3736         ctx->kdfInfoSz = EXCHANGE_INFO_SZ;
3737     }
3738
3739     return 0;
3740 }
3741
3742
3743 static int ecc_ctx_set_salt(ecEncCtx* ctx, int flags, RNG* rng)
3744 {
3745     byte* saltBuffer = NULL;
3746
3747     if (ctx == NULL || rng == NULL || flags == 0)
3748         return BAD_FUNC_ARG;
3749
3750     saltBuffer = (flags == REQ_RESP_CLIENT) ? ctx->clientSalt : ctx->serverSalt;
3751
3752     return RNG_GenerateBlock(rng, saltBuffer, EXCHANGE_SALT_SZ);
3753 }
3754
3755
3756 static void ecc_ctx_init(ecEncCtx* ctx, int flags)
3757 {
3758     if (ctx) {
3759         XMEMSET(ctx, 0, sizeof(ecEncCtx));
3760
3761         ctx->encAlgo  = ecAES_128_CBC;
3762         ctx->kdfAlgo  = ecHKDF_SHA256;
3763         ctx->macAlgo  = ecHMAC_SHA256;
3764         ctx->protocol = (byte)flags;
3765
3766         if (flags == REQ_RESP_CLIENT)
3767             ctx->cliSt = ecCLI_INIT;
3768         if (flags == REQ_RESP_SERVER)
3769             ctx->srvSt = ecSRV_INIT;
3770     }
3771 }
3772
3773
3774 /* allow ecc context reset so user doesn't have to init/free for resue */
3775 int ecc_ctx_reset(ecEncCtx* ctx, RNG* rng)
3776 {
3777     if (ctx == NULL || rng == NULL)
3778         return BAD_FUNC_ARG;
3779
3780     ecc_ctx_init(ctx, ctx->protocol);
3781     return ecc_ctx_set_salt(ctx, ctx->protocol, rng);
3782 }
3783
3784
3785 /* alloc/init and set defaults, return new Context  */
3786 ecEncCtx* ecc_ctx_new(int flags, RNG* rng)
3787 {
3788     int       ret = 0;
3789     ecEncCtx* ctx = (ecEncCtx*)XMALLOC(sizeof(ecEncCtx), 0, DYNAMIC_TYPE_ECC);
3790
3791     if (ctx)
3792         ctx->protocol = (byte)flags;
3793
3794     ret = ecc_ctx_reset(ctx, rng);
3795     if (ret != 0) {
3796         ecc_ctx_free(ctx);
3797         ctx = NULL;
3798     }
3799
3800     return ctx;
3801 }
3802
3803
3804 /* free any resources, clear any keys */
3805 void ecc_ctx_free(ecEncCtx* ctx)
3806 {
3807     if (ctx) {
3808         XMEMSET(ctx, 0, sizeof(ecEncCtx));
3809         XFREE(ctx, 0, DYNAMIC_TYPE_ECC);
3810     }
3811 }
3812
3813
3814 static int ecc_get_key_sizes(ecEncCtx* ctx, int* encKeySz, int* ivSz,
3815                              int* keysLen, word32* digestSz, word32* blockSz)
3816 {
3817     if (ctx) {
3818         switch (ctx->encAlgo) {
3819             case ecAES_128_CBC:
3820                 *encKeySz = KEY_SIZE_128;
3821                 *ivSz     = IV_SIZE_64;
3822                 *blockSz  = AES_BLOCK_SIZE;
3823                 break;
3824             default:
3825                 return BAD_FUNC_ARG;
3826         }
3827
3828         switch (ctx->macAlgo) {
3829             case ecHMAC_SHA256:
3830                 *digestSz = SHA256_DIGEST_SIZE;
3831                 break;
3832             default:
3833                 return BAD_FUNC_ARG;
3834         }
3835     } else
3836         return BAD_FUNC_ARG;
3837
3838     *keysLen  = *encKeySz + *ivSz + *digestSz;
3839
3840     return 0;
3841 }
3842
3843
3844 /* ecc encrypt with shared secret run through kdf
3845    ctx holds non default algos and inputs
3846    msgSz should be the right size for encAlgo, i.e., already padded
3847    return 0 on success */
3848 int ecc_encrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg,
3849                 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx)
3850 {
3851     int          ret;
3852     word32       blockSz;
3853     word32       digestSz;
3854     ecEncCtx     localCtx;
3855 #ifdef CYASSL_SMALL_STACK
3856     byte*        sharedSecret;
3857     byte*        keys;
3858 #else
3859     byte         sharedSecret[ECC_MAXSIZE];  /* 521 max size */
3860     byte         keys[ECC_BUFSIZE];         /* max size */
3861 #endif
3862     word32       sharedSz = ECC_MAXSIZE;
3863     int          keysLen;
3864     int          encKeySz;
3865     int          ivSz;
3866     int          offset = 0;         /* keys offset if doing msg exchange */
3867     byte*        encKey;
3868     byte*        encIv;
3869     byte*        macKey;
3870
3871     if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL ||
3872                            outSz  == NULL)
3873         return BAD_FUNC_ARG;
3874
3875     if (ctx == NULL) {  /* use defaults */
3876         ecc_ctx_init(&localCtx, 0);
3877         ctx = &localCtx;
3878     }
3879
3880     ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz,
3881                             &blockSz);
3882     if (ret != 0)
3883         return ret;
3884
3885     if (ctx->protocol == REQ_RESP_SERVER) {
3886         offset = keysLen;
3887         keysLen *= 2;
3888
3889         if (ctx->srvSt != ecSRV_RECV_REQ)
3890             return BAD_ENC_STATE_E;
3891
3892         ctx->srvSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */
3893     }
3894     else if (ctx->protocol == REQ_RESP_CLIENT) {
3895         if (ctx->cliSt != ecCLI_SALT_SET)
3896             return BAD_ENC_STATE_E;
3897
3898         ctx->cliSt = ecCLI_SENT_REQ; /* only do this once */
3899     }
3900
3901     if (keysLen > ECC_BUFSIZE) /* keys size */
3902         return BUFFER_E;
3903
3904     if ( (msgSz%blockSz) != 0)
3905         return BAD_PADDING_E;
3906
3907     if (*outSz < (msgSz + digestSz))
3908         return BUFFER_E;
3909
3910 #ifdef CYASSL_SMALL_STACK
3911     sharedSecret = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3912     if (sharedSecret == NULL)
3913         return MEMORY_E;
3914
3915     keys = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3916     if (keys == NULL) {
3917         XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3918         return MEMORY_E;
3919     }
3920 #endif
3921
3922     ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz);
3923
3924     if (ret == 0) {
3925        switch (ctx->kdfAlgo) {
3926            case ecHKDF_SHA256 :
3927                ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt,
3928                           ctx->kdfSaltSz, ctx->kdfInfo, ctx->kdfInfoSz,
3929                           keys, keysLen);
3930                break;
3931
3932            default:
3933                ret = BAD_FUNC_ARG;
3934                break;
3935        }
3936     }
3937
3938     if (ret == 0) {
3939        encKey = keys + offset;
3940        encIv  = encKey + encKeySz;
3941        macKey = encKey + encKeySz + ivSz;
3942
3943        switch (ctx->encAlgo) {
3944            case ecAES_128_CBC:
3945                {
3946                    Aes aes;
3947                    ret = AesSetKey(&aes, encKey, KEY_SIZE_128, encIv,
3948                                                                 AES_ENCRYPTION);
3949                    if (ret != 0)
3950                        break;
3951                    ret = AesCbcEncrypt(&aes, out, msg, msgSz);
3952                }
3953                break;
3954
3955            default:
3956                ret = BAD_FUNC_ARG;
3957                break;
3958        }
3959     }
3960
3961     if (ret == 0) {
3962        switch (ctx->macAlgo) {
3963            case ecHMAC_SHA256:
3964                {
3965                    Hmac hmac;
3966                    ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE);
3967                    if (ret != 0)
3968                        break;
3969                    ret = HmacUpdate(&hmac, out, msgSz);
3970                    if (ret != 0)
3971                        break;
3972                    ret = HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz);
3973                    if (ret != 0)
3974                        break;
3975                    ret = HmacFinal(&hmac, out+msgSz);
3976                }
3977                break;
3978
3979            default:
3980                ret = BAD_FUNC_ARG;
3981                break;
3982        }
3983     }
3984
3985     if (ret == 0)
3986        *outSz = msgSz + digestSz;
3987
3988 #ifdef CYASSL_SMALL_STACK
3989     XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3990     XFREE(keys, NULL, DYNAMIC_TYPE_TMP_BUFFER);
3991 #endif
3992
3993     return ret;
3994 }
3995
3996
3997 /* ecc decrypt with shared secret run through kdf
3998    ctx holds non default algos and inputs
3999    return 0 on success */
4000 int ecc_decrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg,
4001                 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx)
4002 {
4003     int          ret;
4004     word32       blockSz;
4005     word32       digestSz;
4006     ecEncCtx     localCtx;
4007 #ifdef CYASSL_SMALL_STACK
4008     byte*        sharedSecret;
4009     byte*        keys;
4010 #else
4011     byte         sharedSecret[ECC_MAXSIZE];  /* 521 max size */
4012     byte         keys[ECC_BUFSIZE];         /* max size */
4013 #endif
4014     word32       sharedSz = ECC_MAXSIZE;
4015     int          keysLen;
4016     int          encKeySz;
4017     int          ivSz;
4018     int          offset = 0;       /* in case using msg exchange */
4019     byte*        encKey;
4020     byte*        encIv;
4021     byte*        macKey;
4022
4023     if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL ||
4024                            outSz  == NULL)
4025         return BAD_FUNC_ARG;
4026
4027     if (ctx == NULL) {  /* use defaults */
4028         ecc_ctx_init(&localCtx, 0);
4029         ctx = &localCtx;
4030     }
4031
4032     ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz,
4033                             &blockSz);
4034     if (ret != 0)
4035         return ret;
4036
4037     if (ctx->protocol == REQ_RESP_CLIENT) {
4038         offset = keysLen;
4039         keysLen *= 2;
4040
4041         if (ctx->cliSt != ecCLI_SENT_REQ)
4042             return BAD_ENC_STATE_E;
4043
4044         ctx->cliSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */
4045     }
4046     else if (ctx->protocol == REQ_RESP_SERVER) {
4047         if (ctx->srvSt != ecSRV_SALT_SET)
4048             return BAD_ENC_STATE_E;
4049
4050         ctx->srvSt = ecSRV_RECV_REQ; /* only do this once */
4051     }
4052
4053     if (keysLen > ECC_BUFSIZE) /* keys size */
4054         return BUFFER_E;
4055
4056     if ( ((msgSz-digestSz) % blockSz) != 0)
4057         return BAD_PADDING_E;
4058
4059     if (*outSz < (msgSz - digestSz))
4060         return BUFFER_E;
4061
4062 #ifdef CYASSL_SMALL_STACK
4063     sharedSecret = (byte*)XMALLOC(ECC_MAXSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4064     if (sharedSecret == NULL)
4065         return MEMORY_E;
4066
4067     keys = (byte*)XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4068     if (keys == NULL) {
4069         XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4070         return MEMORY_E;
4071     }
4072 #endif
4073
4074     ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz);
4075
4076     if (ret == 0) {
4077        switch (ctx->kdfAlgo) {
4078            case ecHKDF_SHA256 :
4079                ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt,
4080                           ctx->kdfSaltSz, ctx->kdfInfo, ctx->kdfInfoSz,
4081                           keys, keysLen);
4082                break;
4083
4084            default:
4085                ret = BAD_FUNC_ARG;
4086                break;
4087        }
4088     }
4089
4090     if (ret == 0) {
4091        encKey = keys + offset;
4092        encIv  = encKey + encKeySz;
4093        macKey = encKey + encKeySz + ivSz;
4094
4095        switch (ctx->macAlgo) {
4096            case ecHMAC_SHA256:
4097                {
4098                    byte verify[SHA256_DIGEST_SIZE];
4099                    Hmac hmac;
4100                    ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE);
4101                    if (ret != 0)
4102                        break;
4103                    ret = HmacUpdate(&hmac, msg, msgSz-digestSz);
4104                    if (ret != 0)
4105                        break;
4106                    ret = HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz);
4107                    if (ret != 0)
4108                        break;
4109                    ret = HmacFinal(&hmac, verify);
4110                    if (ret != 0)
4111                        break;
4112                    if (memcmp(verify, msg + msgSz - digestSz, digestSz) != 0)
4113                        ret = -1;
4114                }
4115                break;
4116
4117            default:
4118                ret = BAD_FUNC_ARG;
4119                break;
4120        }
4121     }
4122
4123     if (ret == 0) {
4124        switch (ctx->encAlgo) {
4125            case ecAES_128_CBC:
4126                {
4127                    Aes aes;
4128                    ret = AesSetKey(&aes, encKey, KEY_SIZE_128, encIv,
4129                                                                 AES_DECRYPTION);
4130                    if (ret != 0)
4131                        break;
4132                    ret = AesCbcDecrypt(&aes, out, msg, msgSz-digestSz);
4133                }
4134                break;
4135
4136            default:
4137                ret = BAD_FUNC_ARG;
4138                break;
4139        }
4140     }
4141
4142     if (ret == 0)
4143        *outSz = msgSz - digestSz;
4144
4145 #ifdef CYASSL_SMALL_STACK
4146     XFREE(sharedSecret, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4147     XFREE(keys, NULL, DYNAMIC_TYPE_TMP_BUFFER);
4148 #endif
4149
4150     return ret;
4151 }
4152
4153
4154 #endif /* HAVE_ECC_ENCRYPT */
4155
4156 #endif /* HAVE_ECC */