wolf SSL / CyaSSL-2.9.4

Dependents:  

Embed: (wiki syntax)

« Back to documentation index

Show/hide line numbers ecc.c Source File

ecc.c

00001 /* ecc.c
00002  *
00003  * Copyright (C) 2006-2013 wolfSSL Inc.
00004  *
00005  * This file is part of CyaSSL.
00006  *
00007  * CyaSSL is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 2 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * CyaSSL is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
00020  */
00021 
00022 
00023 #ifdef HAVE_CONFIG_H
00024     #include <config.h>
00025 #endif
00026 
00027 /* in case user set HAVE_ECC there */
00028 #include <cyassl/ctaocrypt/settings.h>
00029 
00030 #ifdef HAVE_ECC
00031 
00032 #include <cyassl/ctaocrypt/ecc.h>
00033 #include <cyassl/ctaocrypt/asn.h>
00034 #include <cyassl/ctaocrypt/error-crypt.h>
00035 
00036 #ifdef HAVE_ECC_ENCRYPT
00037     #include <cyassl/ctaocrypt/hmac.h>
00038     #include <cyassl/ctaocrypt/aes.h>
00039 #endif
00040 
00041 
00042 /* map
00043 
00044    ptmul -> mulmod
00045 
00046 */
00047 
00048 #define ECC112
00049 #define ECC128
00050 #define ECC160
00051 #define ECC192
00052 #define ECC224
00053 #define ECC256
00054 #define ECC384
00055 #define ECC521
00056 
00057 
00058 
00059 /* This holds the key settings.  ***MUST*** be organized by size from
00060    smallest to largest. */
00061 
00062 const ecc_set_type ecc_sets[] = {
00063 #ifdef ECC112
00064 {
00065         14,
00066         "SECP112R1",
00067         "DB7C2ABF62E35E668076BEAD208B",
00068         "659EF8BA043916EEDE8911702B22",
00069         "DB7C2ABF62E35E7628DFAC6561C5",
00070         "09487239995A5EE76B55F9C2F098",
00071         "A89CE5AF8724C0A23E0E0FF77500"
00072 },
00073 #endif
00074 #ifdef ECC128
00075 {
00076         16,
00077         "SECP128R1",
00078         "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF",
00079         "E87579C11079F43DD824993C2CEE5ED3",
00080         "FFFFFFFE0000000075A30D1B9038A115",
00081         "161FF7528B899B2D0C28607CA52C5B86",
00082         "CF5AC8395BAFEB13C02DA292DDED7A83",
00083 },
00084 #endif
00085 #ifdef ECC160
00086 {
00087         20,
00088         "SECP160R1",
00089         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF",
00090         "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45",
00091         "0100000000000000000001F4C8F927AED3CA752257",
00092         "4A96B5688EF573284664698968C38BB913CBFC82",
00093         "23A628553168947D59DCC912042351377AC5FB32",
00094 },
00095 #endif
00096 #ifdef ECC192
00097 {
00098         24,
00099         "ECC-192",
00100         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF",
00101         "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1",
00102         "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831",
00103         "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012",
00104         "7192B95FFC8DA78631011ED6B24CDD573F977A11E794811",
00105 },
00106 #endif
00107 #ifdef ECC224
00108 {
00109         28,
00110         "ECC-224",
00111         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001",
00112         "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4",
00113         "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D",
00114         "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21",
00115         "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34",
00116 },
00117 #endif
00118 #ifdef ECC256
00119 {
00120         32,
00121         "ECC-256",
00122         "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF",
00123         "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B",
00124         "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551",
00125         "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296",
00126         "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5",
00127 },
00128 #endif
00129 #ifdef ECC384
00130 {
00131         48,
00132         "ECC-384",
00133         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF",
00134         "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF",
00135         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973",
00136         "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7",
00137         "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F",
00138 },
00139 #endif
00140 #ifdef ECC521
00141 {
00142         66,
00143         "ECC-521",
00144         "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",
00145         "51953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00",
00146         "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409",
00147         "C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66",
00148         "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650",
00149 },
00150 #endif
00151 {
00152    0,
00153    NULL, NULL, NULL, NULL, NULL, NULL
00154 }
00155 };
00156 
00157 
00158 ecc_point* ecc_new_point(void);
00159 void ecc_del_point(ecc_point* p);
00160 int  ecc_map(ecc_point*, mp_int*, mp_digit*);
00161 int  ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
00162                               mp_int* modulus, mp_digit* mp);
00163 int  ecc_projective_dbl_point(ecc_point* P, ecc_point* R, mp_int* modulus,
00164                               mp_digit* mp);
00165 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
00166                       int map);
00167 #ifdef ECC_SHAMIR
00168 static int ecc_mul2add(ecc_point* A, mp_int* kA, ecc_point* B, mp_int* kB,
00169                        ecc_point* C, mp_int* modulus);
00170 #endif
00171 
00172 
00173 /* helper for either lib */
00174 static int get_digit_count(mp_int* a)
00175 {
00176     if (a == NULL)
00177         return 0;
00178 
00179     return a->used;
00180 }
00181 
00182 /* helper for either lib */
00183 static unsigned long get_digit(mp_int* a, int n)
00184 {
00185     if (a == NULL)
00186         return 0;
00187 
00188     return (n >= a->used || n < 0) ? 0 : a->dp[n];
00189 }
00190 
00191 
00192 #if defined(USE_FAST_MATH)
00193 
00194 /* fast math accelerated version, but not for fp ecc yet */
00195 
00196 /**
00197    Add two ECC points
00198    P        The point to add
00199    Q        The point to add
00200    R        [out] The destination of the double
00201    modulus  The modulus of the field the ECC curve is in
00202    mp       The "b" value from montgomery_setup()
00203    return   MP_OKAY on success
00204 */
00205 int ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R,
00206                              mp_int* modulus, mp_digit* mp)
00207 {
00208    fp_int t1, t2, x, y, z;
00209    int    err;
00210 
00211    if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
00212        return ECC_BAD_ARG_E;
00213 
00214    if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
00215       return err;
00216    }
00217 
00218    /* should we dbl instead? */
00219    fp_sub(modulus, &Q->y, &t1);
00220    if ( (fp_cmp(&P->x, &Q->x) == FP_EQ) && 
00221         (get_digit_count(&Q->z) && fp_cmp(&P->z, &Q->z) == FP_EQ) &&
00222         (fp_cmp(&P->y, &Q->y) == FP_EQ || fp_cmp(&P->y, &t1) == FP_EQ)) {
00223         return ecc_projective_dbl_point(P, R, modulus, mp);
00224    }
00225 
00226    fp_copy(&P->x, &x);
00227    fp_copy(&P->y, &y);
00228    fp_copy(&P->z, &z);
00229 
00230    /* if Z is one then these are no-operations */
00231    if (get_digit_count(&Q->z)) {
00232       /* T1 = Z' * Z' */
00233       fp_sqr(&Q->z, &t1);
00234       fp_montgomery_reduce(&t1, modulus, *mp);
00235       /* X = X * T1 */
00236       fp_mul(&t1, &x, &x);
00237       fp_montgomery_reduce(&x, modulus, *mp);
00238       /* T1 = Z' * T1 */
00239       fp_mul(&Q->z, &t1, &t1);
00240       fp_montgomery_reduce(&t1, modulus, *mp);
00241       /* Y = Y * T1 */
00242       fp_mul(&t1, &y, &y);
00243       fp_montgomery_reduce(&y, modulus, *mp);
00244    }
00245 
00246    /* T1 = Z*Z */
00247    fp_sqr(&z, &t1);
00248    fp_montgomery_reduce(&t1, modulus, *mp);
00249    /* T2 = X' * T1 */
00250    fp_mul(&Q->x, &t1, &t2);
00251    fp_montgomery_reduce(&t2, modulus, *mp);
00252    /* T1 = Z * T1 */
00253    fp_mul(&z, &t1, &t1);
00254    fp_montgomery_reduce(&t1, modulus, *mp);
00255    /* T1 = Y' * T1 */
00256    fp_mul(&Q->y, &t1, &t1);
00257    fp_montgomery_reduce(&t1, modulus, *mp);
00258 
00259    /* Y = Y - T1 */
00260    fp_sub(&y, &t1, &y);
00261    if (fp_cmp_d(&y, 0) == FP_LT) {
00262       fp_add(&y, modulus, &y);
00263    }
00264    /* T1 = 2T1 */
00265    fp_add(&t1, &t1, &t1);
00266    if (fp_cmp(&t1, modulus) != FP_LT) {
00267       fp_sub(&t1, modulus, &t1);
00268    }
00269    /* T1 = Y + T1 */
00270    fp_add(&t1, &y, &t1);
00271    if (fp_cmp(&t1, modulus) != FP_LT) {
00272       fp_sub(&t1, modulus, &t1);
00273    }
00274    /* X = X - T2 */
00275    fp_sub(&x, &t2, &x);
00276    if (fp_cmp_d(&x, 0) == FP_LT) {
00277       fp_add(&x, modulus, &x);
00278    }
00279    /* T2 = 2T2 */
00280    fp_add(&t2, &t2, &t2);
00281    if (fp_cmp(&t2, modulus) != FP_LT) {
00282       fp_sub(&t2, modulus, &t2);
00283    }
00284    /* T2 = X + T2 */
00285    fp_add(&t2, &x, &t2);
00286    if (fp_cmp(&t2, modulus) != FP_LT) {
00287       fp_sub(&t2, modulus, &t2);
00288    }
00289 
00290    /* if Z' != 1 */
00291    if (get_digit_count(&Q->z)) {
00292       /* Z = Z * Z' */
00293       fp_mul(&z, &Q->z, &z);
00294       fp_montgomery_reduce(&z, modulus, *mp);
00295    }
00296 
00297    /* Z = Z * X */
00298    fp_mul(&z, &x, &z);
00299    fp_montgomery_reduce(&z, modulus, *mp);
00300 
00301    /* T1 = T1 * X  */
00302    fp_mul(&t1, &x, &t1);
00303    fp_montgomery_reduce(&t1, modulus, *mp);
00304    /* X = X * X */
00305    fp_sqr(&x, &x);
00306    fp_montgomery_reduce(&x, modulus, *mp);
00307    /* T2 = T2 * x */
00308    fp_mul(&t2, &x, &t2);
00309    fp_montgomery_reduce(&t2, modulus, *mp);
00310    /* T1 = T1 * X  */
00311    fp_mul(&t1, &x, &t1);
00312    fp_montgomery_reduce(&t1, modulus, *mp);
00313  
00314    /* X = Y*Y */
00315    fp_sqr(&y, &x);
00316    fp_montgomery_reduce(&x, modulus, *mp);
00317    /* X = X - T2 */
00318    fp_sub(&x, &t2, &x);
00319    if (fp_cmp_d(&x, 0) == FP_LT) {
00320       fp_add(&x, modulus, &x);
00321    }
00322 
00323    /* T2 = T2 - X */
00324    fp_sub(&t2, &x, &t2);
00325    if (fp_cmp_d(&t2, 0) == FP_LT) {
00326       fp_add(&t2, modulus, &t2);
00327    } 
00328    /* T2 = T2 - X */
00329    fp_sub(&t2, &x, &t2);
00330    if (fp_cmp_d(&t2, 0) == FP_LT) {
00331       fp_add(&t2, modulus, &t2);
00332    }
00333    /* T2 = T2 * Y */
00334    fp_mul(&t2, &y, &t2);
00335    fp_montgomery_reduce(&t2, modulus, *mp);
00336    /* Y = T2 - T1 */
00337    fp_sub(&t2, &t1, &y);
00338    if (fp_cmp_d(&y, 0) == FP_LT) {
00339       fp_add(&y, modulus, &y);
00340    }
00341    /* Y = Y/2 */
00342    if (fp_isodd(&y)) {
00343       fp_add(&y, modulus, &y);
00344    }
00345    fp_div_2(&y, &y);
00346 
00347    fp_copy(&x, &R->x);
00348    fp_copy(&y, &R->y);
00349    fp_copy(&z, &R->z);
00350    
00351    return MP_OKAY;
00352 }
00353 
00354 
00355 /**
00356    Double an ECC point
00357    P   The point to double
00358    R   [out] The destination of the double
00359    modulus  The modulus of the field the ECC curve is in
00360    mp       The "b" value from montgomery_setup()
00361    return   MP_OKAY on success
00362 */
00363 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
00364                              mp_digit* mp)
00365 {
00366    fp_int   t1, t2;
00367    int      err;
00368 
00369    if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
00370        return ECC_BAD_ARG_E;
00371 
00372    if (P != R) {
00373       fp_copy(&P->x, &R->x);
00374       fp_copy(&P->y, &R->y);
00375       fp_copy(&P->z, &R->z);
00376    }
00377 
00378    if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
00379       return err;
00380    }
00381 
00382    /* t1 = Z * Z */
00383    fp_sqr(&R->z, &t1);
00384    fp_montgomery_reduce(&t1, modulus, *mp);
00385    /* Z = Y * Z */
00386    fp_mul(&R->z, &R->y, &R->z);
00387    fp_montgomery_reduce(&R->z, modulus, *mp);
00388    /* Z = 2Z */
00389    fp_add(&R->z, &R->z, &R->z);
00390    if (fp_cmp(&R->z, modulus) != FP_LT) {
00391       fp_sub(&R->z, modulus, &R->z);
00392    }
00393    
00394    /* &t2 = X - T1 */
00395    fp_sub(&R->x, &t1, &t2);
00396    if (fp_cmp_d(&t2, 0) == FP_LT) {
00397       fp_add(&t2, modulus, &t2);
00398    }
00399    /* T1 = X + T1 */
00400    fp_add(&t1, &R->x, &t1);
00401    if (fp_cmp(&t1, modulus) != FP_LT) {
00402       fp_sub(&t1, modulus, &t1);
00403    }
00404    /* T2 = T1 * T2 */
00405    fp_mul(&t1, &t2, &t2);
00406    fp_montgomery_reduce(&t2, modulus, *mp);
00407    /* T1 = 2T2 */
00408    fp_add(&t2, &t2, &t1);
00409    if (fp_cmp(&t1, modulus) != FP_LT) {
00410       fp_sub(&t1, modulus, &t1);
00411    }
00412    /* T1 = T1 + T2 */
00413    fp_add(&t1, &t2, &t1);
00414    if (fp_cmp(&t1, modulus) != FP_LT) {
00415       fp_sub(&t1, modulus, &t1);
00416    }
00417 
00418    /* Y = 2Y */
00419    fp_add(&R->y, &R->y, &R->y);
00420    if (fp_cmp(&R->y, modulus) != FP_LT) {
00421       fp_sub(&R->y, modulus, &R->y);
00422    }
00423    /* Y = Y * Y */
00424    fp_sqr(&R->y, &R->y);
00425    fp_montgomery_reduce(&R->y, modulus, *mp);
00426    /* T2 = Y * Y */
00427    fp_sqr(&R->y, &t2);
00428    fp_montgomery_reduce(&t2, modulus, *mp);
00429    /* T2 = T2/2 */
00430    if (fp_isodd(&t2)) {
00431       fp_add(&t2, modulus, &t2);
00432    }
00433    fp_div_2(&t2, &t2);
00434    /* Y = Y * X */
00435    fp_mul(&R->y, &R->x, &R->y);
00436    fp_montgomery_reduce(&R->y, modulus, *mp);
00437 
00438    /* X  = T1 * T1 */
00439    fp_sqr(&t1, &R->x);
00440    fp_montgomery_reduce(&R->x, modulus, *mp);
00441    /* X = X - Y */
00442    fp_sub(&R->x, &R->y, &R->x);
00443    if (fp_cmp_d(&R->x, 0) == FP_LT) {
00444       fp_add(&R->x, modulus, &R->x);
00445    }
00446    /* X = X - Y */
00447    fp_sub(&R->x, &R->y, &R->x);
00448    if (fp_cmp_d(&R->x, 0) == FP_LT) {
00449       fp_add(&R->x, modulus, &R->x);
00450    }
00451 
00452    /* Y = Y - X */     
00453    fp_sub(&R->y, &R->x, &R->y);
00454    if (fp_cmp_d(&R->y, 0) == FP_LT) {
00455       fp_add(&R->y, modulus, &R->y);
00456    }
00457    /* Y = Y * T1 */
00458    fp_mul(&R->y, &t1, &R->y);
00459    fp_montgomery_reduce(&R->y, modulus, *mp);
00460    /* Y = Y - T2 */
00461    fp_sub(&R->y, &t2, &R->y);
00462    if (fp_cmp_d(&R->y, 0) == FP_LT) {
00463       fp_add(&R->y, modulus, &R->y);
00464    }
00465  
00466    return MP_OKAY;
00467 }
00468 
00469 #else /* USE_FAST_MATH */
00470 
00471 /**
00472    Add two ECC points
00473    P        The point to add
00474    Q        The point to add
00475    R        [out] The destination of the double
00476    modulus  The modulus of the field the ECC curve is in
00477    mp       The "b" value from montgomery_setup()
00478    return   MP_OKAY on success
00479 */
00480 int ecc_projective_add_point(ecc_point* P, ecc_point* Q, ecc_point* R,
00481                              mp_int* modulus, mp_digit* mp)
00482 {
00483    mp_int t1;
00484    mp_int t2;
00485    mp_int x;
00486    mp_int y;
00487    mp_int z;
00488    int    err;
00489 
00490    if (P == NULL || Q == NULL || R == NULL || modulus == NULL || mp == NULL)
00491        return ECC_BAD_ARG_E;
00492 
00493    if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != MP_OKAY) {
00494       return err;
00495    }
00496    
00497    /* should we dbl instead? */
00498    err = mp_sub(modulus, &Q->y, &t1);
00499 
00500    if (err == MP_OKAY) {
00501        if ( (mp_cmp(&P->x, &Q->x) == MP_EQ) && 
00502             (get_digit_count(&Q->z) && mp_cmp(&P->z, &Q->z) == MP_EQ) &&
00503             (mp_cmp(&P->y, &Q->y) == MP_EQ || mp_cmp(&P->y, &t1) == MP_EQ)) {
00504                 mp_clear(&t1);
00505                 mp_clear(&t2);
00506                 mp_clear(&x);
00507                 mp_clear(&y);
00508                 mp_clear(&z);
00509 
00510                 return ecc_projective_dbl_point(P, R, modulus, mp);
00511        }
00512    }
00513 
00514    if (err == MP_OKAY)
00515        err = mp_copy(&P->x, &x);
00516    if (err == MP_OKAY)
00517        err = mp_copy(&P->y, &y);
00518    if (err == MP_OKAY)
00519        err = mp_copy(&P->z, &z);
00520 
00521    /* if Z is one then these are no-operations */
00522    if (err == MP_OKAY) {
00523        if (get_digit_count(&Q->z)) {
00524            /* T1 = Z' * Z' */
00525            err = mp_sqr(&Q->z, &t1);
00526            if (err == MP_OKAY)
00527                err = mp_montgomery_reduce(&t1, modulus, *mp);
00528 
00529            /* X = X * T1 */
00530            if (err == MP_OKAY)
00531                err = mp_mul(&t1, &x, &x);
00532            if (err == MP_OKAY)
00533                err = mp_montgomery_reduce(&x, modulus, *mp);
00534 
00535            /* T1 = Z' * T1 */
00536            if (err == MP_OKAY)
00537                err = mp_mul(&Q->z, &t1, &t1);
00538            if (err == MP_OKAY)
00539                err = mp_montgomery_reduce(&t1, modulus, *mp);
00540 
00541            /* Y = Y * T1 */
00542            if (err == MP_OKAY)
00543                err = mp_mul(&t1, &y, &y);
00544            if (err == MP_OKAY)
00545                err = mp_montgomery_reduce(&y, modulus, *mp);
00546        }
00547    }
00548 
00549    /* T1 = Z*Z */
00550    if (err == MP_OKAY)
00551        err = mp_sqr(&z, &t1);
00552    if (err == MP_OKAY)
00553        err = mp_montgomery_reduce(&t1, modulus, *mp);
00554 
00555    /* T2 = X' * T1 */
00556    if (err == MP_OKAY)
00557        err = mp_mul(&Q->x, &t1, &t2);
00558    if (err == MP_OKAY)
00559        err = mp_montgomery_reduce(&t2, modulus, *mp);
00560 
00561    /* T1 = Z * T1 */
00562    if (err == MP_OKAY)
00563        err = mp_mul(&z, &t1, &t1);
00564    if (err == MP_OKAY)
00565        err = mp_montgomery_reduce(&t1, modulus, *mp);
00566 
00567    /* T1 = Y' * T1 */
00568    if (err == MP_OKAY)
00569        err = mp_mul(&Q->y, &t1, &t1);
00570    if (err == MP_OKAY)
00571        err = mp_montgomery_reduce(&t1, modulus, *mp);
00572 
00573    /* Y = Y - T1 */
00574    if (err == MP_OKAY)
00575        err = mp_sub(&y, &t1, &y);
00576    if (err == MP_OKAY) {
00577        if (mp_cmp_d(&y, 0) == MP_LT)
00578            err = mp_add(&y, modulus, &y);
00579    }
00580    /* T1 = 2T1 */
00581    if (err == MP_OKAY)
00582        err = mp_add(&t1, &t1, &t1);
00583    if (err == MP_OKAY) {
00584        if (mp_cmp(&t1, modulus) != MP_LT)
00585            err = mp_sub(&t1, modulus, &t1);
00586    }
00587    /* T1 = Y + T1 */
00588    if (err == MP_OKAY)
00589        err = mp_add(&t1, &y, &t1);
00590    if (err == MP_OKAY) {
00591        if (mp_cmp(&t1, modulus) != MP_LT)
00592            err = mp_sub(&t1, modulus, &t1);
00593    }
00594    /* X = X - T2 */
00595    if (err == MP_OKAY)
00596        err = mp_sub(&x, &t2, &x);
00597    if (err == MP_OKAY) {
00598        if (mp_cmp_d(&x, 0) == MP_LT)
00599            err = mp_add(&x, modulus, &x);
00600    }
00601    /* T2 = 2T2 */
00602    if (err == MP_OKAY)
00603        err = mp_add(&t2, &t2, &t2);
00604    if (err == MP_OKAY) {
00605        if (mp_cmp(&t2, modulus) != MP_LT)
00606            err = mp_sub(&t2, modulus, &t2);
00607    }
00608    /* T2 = X + T2 */
00609    if (err == MP_OKAY)
00610        err = mp_add(&t2, &x, &t2);
00611    if (err == MP_OKAY) {
00612        if (mp_cmp(&t2, modulus) != MP_LT)
00613            err = mp_sub(&t2, modulus, &t2);
00614    }
00615 
00616    if (err == MP_OKAY) {
00617        if (get_digit_count(&Q->z)) {
00618            /* Z = Z * Z' */
00619            err = mp_mul(&z, &Q->z, &z);
00620            if (err == MP_OKAY)
00621                err = mp_montgomery_reduce(&z, modulus, *mp);
00622        }
00623    }
00624 
00625    /* Z = Z * X */
00626    if (err == MP_OKAY)
00627        err = mp_mul(&z, &x, &z);
00628    if (err == MP_OKAY)
00629        err = mp_montgomery_reduce(&z, modulus, *mp);
00630 
00631    /* T1 = T1 * X  */
00632    if (err == MP_OKAY)
00633        err = mp_mul(&t1, &x, &t1);
00634    if (err == MP_OKAY)
00635        err = mp_montgomery_reduce(&t1, modulus, *mp);
00636 
00637    /* X = X * X */
00638    if (err == MP_OKAY)
00639        err = mp_sqr(&x, &x);
00640    if (err == MP_OKAY)
00641        err = mp_montgomery_reduce(&x, modulus, *mp);
00642    
00643    /* T2 = T2 * x */
00644    if (err == MP_OKAY)
00645        err = mp_mul(&t2, &x, &t2);
00646    if (err == MP_OKAY)
00647        err = mp_montgomery_reduce(&t2, modulus, *mp);
00648 
00649    /* T1 = T1 * X  */
00650    if (err == MP_OKAY)
00651        err = mp_mul(&t1, &x, &t1);
00652    if (err == MP_OKAY)
00653        err = mp_montgomery_reduce(&t1, modulus, *mp);
00654  
00655    /* X = Y*Y */
00656    if (err == MP_OKAY)
00657        err = mp_sqr(&y, &x);
00658    if (err == MP_OKAY)
00659        err = mp_montgomery_reduce(&x, modulus, *mp);
00660 
00661    /* X = X - T2 */
00662    if (err == MP_OKAY)
00663        err = mp_sub(&x, &t2, &x);
00664    if (err == MP_OKAY) {
00665        if (mp_cmp_d(&x, 0) == MP_LT)
00666            err = mp_add(&x, modulus, &x);
00667    }
00668    /* T2 = T2 - X */
00669    if (err == MP_OKAY)
00670        err = mp_sub(&t2, &x, &t2);
00671    if (err == MP_OKAY) {
00672        if (mp_cmp_d(&t2, 0) == MP_LT)
00673            err = mp_add(&t2, modulus, &t2);
00674    } 
00675    /* T2 = T2 - X */
00676    if (err == MP_OKAY)
00677        err = mp_sub(&t2, &x, &t2);
00678    if (err == MP_OKAY) {
00679        if (mp_cmp_d(&t2, 0) == MP_LT)
00680            err = mp_add(&t2, modulus, &t2);
00681    }
00682    /* T2 = T2 * Y */
00683    if (err == MP_OKAY)
00684        err = mp_mul(&t2, &y, &t2);
00685    if (err == MP_OKAY)
00686        err = mp_montgomery_reduce(&t2, modulus, *mp);
00687 
00688    /* Y = T2 - T1 */
00689    if (err == MP_OKAY)
00690        err = mp_sub(&t2, &t1, &y);
00691    if (err == MP_OKAY) {
00692        if (mp_cmp_d(&y, 0) == MP_LT)
00693            err = mp_add(&y, modulus, &y);
00694    }
00695    /* Y = Y/2 */
00696    if (err == MP_OKAY) {
00697        if (mp_isodd(&y))
00698            err = mp_add(&y, modulus, &y);
00699    }
00700    if (err == MP_OKAY)
00701        err = mp_div_2(&y, &y);
00702 
00703    if (err == MP_OKAY)
00704        err = mp_copy(&x, &R->x);
00705    if (err == MP_OKAY)
00706        err = mp_copy(&y, &R->y);
00707    if (err == MP_OKAY)
00708        err = mp_copy(&z, &R->z);
00709 
00710    /* clean up */
00711    mp_clear(&t1);
00712    mp_clear(&t2);
00713    mp_clear(&x);
00714    mp_clear(&y);
00715    mp_clear(&z);
00716 
00717    return err;
00718 }
00719 
00720 
00721 /**
00722    Double an ECC point
00723    P   The point to double
00724    R   [out] The destination of the double
00725    modulus  The modulus of the field the ECC curve is in
00726    mp       The "b" value from montgomery_setup()
00727    return   MP_OKAY on success
00728 */
00729 int ecc_projective_dbl_point(ecc_point *P, ecc_point *R, mp_int* modulus,
00730                              mp_digit* mp)
00731 {
00732    mp_int t1;
00733    mp_int t2;
00734    int    err;
00735 
00736    if (P == NULL || R == NULL || modulus == NULL || mp == NULL)
00737        return ECC_BAD_ARG_E;
00738 
00739    if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
00740       return err;
00741    }
00742 
00743    if (P != R) {
00744       err = mp_copy(&P->x, &R->x);
00745       if (err == MP_OKAY)
00746           err = mp_copy(&P->y, &R->y);
00747       if (err == MP_OKAY)
00748           err = mp_copy(&P->z, &R->z);
00749    }
00750 
00751    /* t1 = Z * Z */
00752    if (err == MP_OKAY)
00753        err = mp_sqr(&R->z, &t1);
00754    if (err == MP_OKAY)
00755        err = mp_montgomery_reduce(&t1, modulus, *mp);
00756 
00757    /* Z = Y * Z */
00758    if (err == MP_OKAY)
00759        err = mp_mul(&R->z, &R->y, &R->z);
00760    if (err == MP_OKAY)
00761        err = mp_montgomery_reduce(&R->z, modulus, *mp);
00762 
00763    /* Z = 2Z */
00764    if (err == MP_OKAY)
00765        err = mp_add(&R->z, &R->z, &R->z);
00766    if (err == MP_OKAY) {
00767        if (mp_cmp(&R->z, modulus) != MP_LT)
00768            err = mp_sub(&R->z, modulus, &R->z);
00769    }
00770 
00771    /* T2 = X - T1 */
00772    if (err == MP_OKAY)
00773        err = mp_sub(&R->x, &t1, &t2);
00774    if (err == MP_OKAY) {
00775        if (mp_cmp_d(&t2, 0) == MP_LT)
00776            err = mp_add(&t2, modulus, &t2);
00777    }
00778    /* T1 = X + T1 */
00779    if (err == MP_OKAY)
00780        err = mp_add(&t1, &R->x, &t1);
00781    if (err == MP_OKAY) {
00782        if (mp_cmp(&t1, modulus) != MP_LT)
00783            err = mp_sub(&t1, modulus, &t1);
00784    }
00785    /* T2 = T1 * T2 */
00786    if (err == MP_OKAY)
00787        err = mp_mul(&t1, &t2, &t2);
00788    if (err == MP_OKAY)
00789        err = mp_montgomery_reduce(&t2, modulus, *mp);
00790 
00791    /* T1 = 2T2 */
00792    if (err == MP_OKAY)
00793        err = mp_add(&t2, &t2, &t1);
00794    if (err == MP_OKAY) {
00795        if (mp_cmp(&t1, modulus) != MP_LT)
00796            err = mp_sub(&t1, modulus, &t1);
00797    }
00798    /* T1 = T1 + T2 */
00799    if (err == MP_OKAY)
00800        err = mp_add(&t1, &t2, &t1);
00801    if (err == MP_OKAY) {
00802        if (mp_cmp(&t1, modulus) != MP_LT)
00803            err = mp_sub(&t1, modulus, &t1);
00804    }
00805    /* Y = 2Y */
00806    if (err == MP_OKAY)
00807        err = mp_add(&R->y, &R->y, &R->y);
00808    if (err == MP_OKAY) {
00809        if (mp_cmp(&R->y, modulus) != MP_LT)
00810            err = mp_sub(&R->y, modulus, &R->y);
00811    }
00812    /* Y = Y * Y */
00813    if (err == MP_OKAY)
00814        err = mp_sqr(&R->y, &R->y);
00815    if (err == MP_OKAY)
00816        err = mp_montgomery_reduce(&R->y, modulus, *mp);
00817    
00818    /* T2 = Y * Y */
00819    if (err == MP_OKAY)
00820        err = mp_sqr(&R->y, &t2);
00821    if (err == MP_OKAY)
00822        err = mp_montgomery_reduce(&t2, modulus, *mp);
00823 
00824    /* T2 = T2/2 */
00825    if (err == MP_OKAY) {
00826        if (mp_isodd(&t2))
00827            err = mp_add(&t2, modulus, &t2);
00828    }
00829    if (err == MP_OKAY)
00830        err = mp_div_2(&t2, &t2);
00831    
00832    /* Y = Y * X */
00833    if (err == MP_OKAY)
00834        err = mp_mul(&R->y, &R->x, &R->y);
00835    if (err == MP_OKAY)
00836        err = mp_montgomery_reduce(&R->y, modulus, *mp);
00837 
00838    /* X  = T1 * T1 */
00839    if (err == MP_OKAY)
00840        err = mp_sqr(&t1, &R->x);
00841    if (err == MP_OKAY)
00842        err = mp_montgomery_reduce(&R->x, modulus, *mp);
00843 
00844    /* X = X - Y */
00845    if (err == MP_OKAY)
00846        err = mp_sub(&R->x, &R->y, &R->x);
00847    if (err == MP_OKAY) {
00848        if (mp_cmp_d(&R->x, 0) == MP_LT)
00849            err = mp_add(&R->x, modulus, &R->x);
00850    }
00851    /* X = X - Y */
00852    if (err == MP_OKAY)
00853        err = mp_sub(&R->x, &R->y, &R->x);
00854    if (err == MP_OKAY) {
00855        if (mp_cmp_d(&R->x, 0) == MP_LT)
00856            err = mp_add(&R->x, modulus, &R->x);
00857    }
00858    /* Y = Y - X */     
00859    if (err == MP_OKAY)
00860        err = mp_sub(&R->y, &R->x, &R->y);
00861    if (err == MP_OKAY) {
00862        if (mp_cmp_d(&R->y, 0) == MP_LT)
00863            err = mp_add(&R->y, modulus, &R->y);
00864    }
00865    /* Y = Y * T1 */
00866    if (err == MP_OKAY)
00867        err = mp_mul(&R->y, &t1, &R->y);
00868    if (err == MP_OKAY)
00869        err = mp_montgomery_reduce(&R->y, modulus, *mp);
00870 
00871    /* Y = Y - T2 */
00872    if (err == MP_OKAY)
00873        err = mp_sub(&R->y, &t2, &R->y);
00874    if (err == MP_OKAY) {
00875        if (mp_cmp_d(&R->y, 0) == MP_LT)
00876            err = mp_add(&R->y, modulus, &R->y);
00877    }
00878 
00879    /* clean up */ 
00880    mp_clear(&t1);
00881    mp_clear(&t2);
00882 
00883    return err;
00884 }
00885 
00886 #endif /* USE_FAST_MATH */
00887 
00888 /**
00889   Map a projective jacbobian point back to affine space
00890   P        [in/out] The point to map
00891   modulus  The modulus of the field the ECC curve is in
00892   mp       The "b" value from montgomery_setup()
00893   return   MP_OKAY on success
00894 */
00895 int ecc_map(ecc_point* P, mp_int* modulus, mp_digit* mp)
00896 {
00897    mp_int t1;
00898    mp_int t2;
00899    int    err;
00900 
00901    if (P == NULL || mp == NULL || modulus == NULL)
00902        return ECC_BAD_ARG_E;
00903 
00904    if ((err = mp_init_multi(&t1, &t2, NULL, NULL, NULL, NULL)) != MP_OKAY) {
00905       return MEMORY_E;
00906    }
00907 
00908    /* first map z back to normal */
00909    err = mp_montgomery_reduce(&P->z, modulus, *mp);
00910 
00911    /* get 1/z */
00912    if (err == MP_OKAY)
00913        err = mp_invmod(&P->z, modulus, &t1);
00914  
00915    /* get 1/z^2 and 1/z^3 */
00916    if (err == MP_OKAY)
00917        err = mp_sqr(&t1, &t2);
00918    if (err == MP_OKAY)
00919        err = mp_mod(&t2, modulus, &t2);
00920    if (err == MP_OKAY)
00921        err = mp_mul(&t1, &t2, &t1);
00922    if (err == MP_OKAY)
00923        err = mp_mod(&t1, modulus, &t1);
00924 
00925    /* multiply against x/y */
00926    if (err == MP_OKAY)
00927        err = mp_mul(&P->x, &t2, &P->x);
00928    if (err == MP_OKAY)
00929        err = mp_montgomery_reduce(&P->x, modulus, *mp);
00930    if (err == MP_OKAY)
00931        err = mp_mul(&P->y, &t1, &P->y);
00932    if (err == MP_OKAY)
00933        err = mp_montgomery_reduce(&P->y, modulus, *mp);
00934    
00935    if (err == MP_OKAY)
00936        mp_set(&P->z, 1);
00937 
00938    /* clean up */
00939    mp_clear(&t1);
00940    mp_clear(&t2);
00941 
00942    return err;
00943 }
00944 
00945 
00946 #ifndef ECC_TIMING_RESISTANT
00947 
00948 /* size of sliding window, don't change this! */
00949 #define WINSIZE 4
00950 
00951 /**
00952    Perform a point multiplication 
00953    k    The scalar to multiply by
00954    G    The base point
00955    R    [out] Destination for kG
00956    modulus  The modulus of the field the ECC curve is in
00957    map      Boolean whether to map back to affine or not
00958                 (1==map, 0 == leave in projective)
00959    return MP_OKAY on success
00960 */
00961 #ifdef FP_ECC
00962 static int normal_ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R,
00963                              mp_int* modulus, int map)
00964 #else
00965 static int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
00966                       int map)
00967 #endif
00968 {
00969    ecc_point *tG, *M[8];
00970    int           i, j, err;
00971    mp_int        mu;
00972    mp_digit      mp;
00973    unsigned long buf;
00974    int           first = 1, bitbuf = 0, bitcpy = 0, bitcnt = 0, mode = 0,
00975                  digidx = 0;
00976 
00977    if (k == NULL || G == NULL || R == NULL || modulus == NULL)
00978        return ECC_BAD_ARG_E;
00979 
00980    /* init montgomery reduction */
00981    if ((err = mp_montgomery_setup(modulus, &mp)) != MP_OKAY) {
00982       return err;
00983    }
00984    if ((err = mp_init(&mu)) != MP_OKAY) {
00985       return err;
00986    }
00987    if ((err = mp_montgomery_calc_normalization(&mu, modulus)) != MP_OKAY) {
00988       mp_clear(&mu);
00989       return err;
00990    }
00991   
00992   /* alloc ram for window temps */
00993   for (i = 0; i < 8; i++) {
00994       M[i] = ecc_new_point();
00995       if (M[i] == NULL) {
00996          for (j = 0; j < i; j++) {
00997              ecc_del_point(M[j]);
00998          }
00999          mp_clear(&mu);
01000          return MEMORY_E;
01001       }
01002   }
01003 
01004    /* make a copy of G incase R==G */
01005    tG = ecc_new_point();
01006    if (tG == NULL)
01007        err = MEMORY_E;
01008 
01009    /* tG = G  and convert to montgomery */
01010    if (err == MP_OKAY) {
01011        if (mp_cmp_d(&mu, 1) == MP_EQ) {
01012            err = mp_copy(&G->x, &tG->x);
01013            if (err == MP_OKAY)
01014                err = mp_copy(&G->y, &tG->y);
01015            if (err == MP_OKAY)
01016                err = mp_copy(&G->z, &tG->z);
01017        } else {
01018            err = mp_mulmod(&G->x, &mu, modulus, &tG->x);
01019            if (err == MP_OKAY)
01020                err = mp_mulmod(&G->y, &mu, modulus, &tG->y);
01021            if (err == MP_OKAY)
01022                err = mp_mulmod(&G->z, &mu, modulus, &tG->z);
01023        }
01024    }
01025    mp_clear(&mu);
01026    
01027    /* calc the M tab, which holds kG for k==8..15 */
01028    /* M[0] == 8G */
01029    if (err == MP_OKAY)
01030        err = ecc_projective_dbl_point(tG, M[0], modulus, &mp);
01031    if (err == MP_OKAY)
01032        err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
01033    if (err == MP_OKAY)
01034        err = ecc_projective_dbl_point(M[0], M[0], modulus, &mp);
01035 
01036    /* now find (8+k)G for k=1..7 */
01037    if (err == MP_OKAY)
01038        for (j = 9; j < 16; j++) {
01039            err = ecc_projective_add_point(M[j-9], tG, M[j-8], modulus, &mp);
01040            if (err != MP_OKAY) break;
01041        }
01042 
01043    /* setup sliding window */
01044    if (err == MP_OKAY) {
01045        mode   = 0;
01046        bitcnt = 1;
01047        buf    = 0;
01048        digidx = get_digit_count(k) - 1;
01049        bitcpy = bitbuf = 0;
01050        first  = 1;
01051 
01052        /* perform ops */
01053        for (;;) {
01054            /* grab next digit as required */
01055            if (--bitcnt == 0) {
01056                if (digidx == -1) {
01057                    break;
01058                }
01059                buf    = get_digit(k, digidx);
01060                bitcnt = (int) DIGIT_BIT; 
01061                --digidx;
01062            }
01063 
01064            /* grab the next msb from the ltiplicand */
01065            i = (int)(buf >> (DIGIT_BIT - 1)) & 1;
01066            buf <<= 1;
01067 
01068            /* skip leading zero bits */
01069            if (mode == 0 && i == 0)
01070                continue;
01071 
01072            /* if the bit is zero and mode == 1 then we double */
01073            if (mode == 1 && i == 0) {
01074                err = ecc_projective_dbl_point(R, R, modulus, &mp);
01075                if (err != MP_OKAY) break;
01076                continue;
01077            }
01078 
01079            /* else we add it to the window */
01080            bitbuf |= (i << (WINSIZE - ++bitcpy));
01081            mode = 2;
01082 
01083            if (bitcpy == WINSIZE) {
01084                /* if this is the first window we do a simple copy */
01085                if (first == 1) {
01086                    /* R = kG [k = first window] */
01087                    err = mp_copy(&M[bitbuf-8]->x, &R->x);
01088                    if (err != MP_OKAY) break;
01089 
01090                    err = mp_copy(&M[bitbuf-8]->y, &R->y);
01091                    if (err != MP_OKAY) break;
01092 
01093                    err = mp_copy(&M[bitbuf-8]->z, &R->z);
01094                    first = 0;
01095                } else {
01096                    /* normal window */
01097                    /* ok window is filled so double as required and add  */
01098                    /* double first */
01099                    for (j = 0; j < WINSIZE; j++) {
01100                        err = ecc_projective_dbl_point(R, R, modulus, &mp);
01101                        if (err != MP_OKAY) break;
01102                    }
01103                    if (err != MP_OKAY) break;  /* out of first for(;;) */
01104 
01105                    /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranted */
01106                    err = ecc_projective_add_point(R,M[bitbuf-8],R,modulus,&mp);
01107                }
01108                if (err != MP_OKAY) break;
01109                /* empty window and reset */
01110                bitcpy = bitbuf = 0;
01111                mode = 1;
01112            }
01113        }
01114    }
01115 
01116    /* if bits remain then double/add */
01117    if (err == MP_OKAY) {
01118        if (mode == 2 && bitcpy > 0) {
01119            /* double then add */
01120            for (j = 0; j < bitcpy; j++) {
01121                /* only double if we have had at least one add first */
01122                if (first == 0) {
01123                    err = ecc_projective_dbl_point(R, R, modulus, &mp);
01124                    if (err != MP_OKAY) break;
01125                }
01126 
01127                bitbuf <<= 1;
01128                if ((bitbuf & (1 << WINSIZE)) != 0) {
01129                    if (first == 1) {
01130                        /* first add, so copy */
01131                        err = mp_copy(&tG->x, &R->x);
01132                        if (err != MP_OKAY) break;
01133 
01134                        err = mp_copy(&tG->y, &R->y);
01135                        if (err != MP_OKAY) break;
01136 
01137                        err = mp_copy(&tG->z, &R->z);
01138                        if (err != MP_OKAY) break;
01139                        first = 0;
01140                    } else {
01141                        /* then add */
01142                        err = ecc_projective_add_point(R, tG, R, modulus, &mp);
01143                        if (err != MP_OKAY) break;
01144                    }
01145                }
01146            }
01147        }
01148    }
01149 
01150    /* map R back from projective space */
01151    if (err == MP_OKAY && map)
01152        err = ecc_map(R, modulus, &mp);
01153 
01154    mp_clear(&mu);
01155    ecc_del_point(tG);
01156    for (i = 0; i < 8; i++) {
01157        ecc_del_point(M[i]);
01158    }
01159    return err;
01160 }
01161 
01162 #undef WINSIZE
01163 #endif /* ECC_TIMING_RESISTANT */
01164 
01165 
01166 /**
01167    Allocate a new ECC point
01168    return A newly allocated point or NULL on error 
01169 */
01170 ecc_point* ecc_new_point(void)
01171 {
01172    ecc_point* p;
01173    p = (ecc_point*)XMALLOC(sizeof(ecc_point), 0, DYNAMIC_TYPE_BIGINT);
01174    if (p == NULL) {
01175       return NULL;
01176    }
01177    XMEMSET(p, 0, sizeof(ecc_point));
01178    if (mp_init_multi(&p->x, &p->y, &p->z, NULL, NULL, NULL) != MP_OKAY) {
01179       XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
01180       return NULL;
01181    }
01182    return p;
01183 }
01184 
01185 /** Free an ECC point from memory
01186   p   The point to free
01187 */
01188 void ecc_del_point(ecc_point* p)
01189 {
01190    /* prevents free'ing null arguments */
01191    if (p != NULL) {
01192       mp_clear(&p->x);
01193       mp_clear(&p->y);
01194       mp_clear(&p->z);
01195       XFREE(p, 0, DYNAMIC_TYPE_BIGINT);
01196    }
01197 }
01198 
01199 
01200 /** Returns whether an ECC idx is valid or not
01201   n      The idx number to check
01202   return 1 if valid, 0 if not
01203 */  
01204 static int ecc_is_valid_idx(int n)
01205 {
01206    int x;
01207 
01208    for (x = 0; ecc_sets[x].size != 0; x++)
01209        ;
01210    /* -1 is a valid index --- indicating that the domain params
01211       were supplied by the user */
01212    if ((n >= -1) && (n < x)) {
01213       return 1;
01214    }
01215    return 0;
01216 }
01217 
01218 
01219 /**
01220   Create an ECC shared secret between two keys
01221   private_key      The private ECC key
01222   public_key       The public key
01223   out              [out] Destination of the shared secret
01224                    Conforms to EC-DH from ANSI X9.63
01225   outlen           [in/out] The max size and resulting size of the shared secret
01226   return           MP_OKAY if successful
01227 */
01228 int ecc_shared_secret(ecc_key* private_key, ecc_key* public_key, byte* out,
01229                       word32* outlen)
01230 {
01231    word32         x = 0;
01232    ecc_point*     result;
01233    mp_int         prime;
01234    int            err;
01235 
01236    if (private_key == NULL || public_key == NULL || out == NULL ||
01237                                                     outlen == NULL)
01238        return BAD_FUNC_ARG;
01239 
01240    /* type valid? */
01241    if (private_key->type != ECC_PRIVATEKEY) {
01242       return ECC_BAD_ARG_E;
01243    }
01244 
01245    if (ecc_is_valid_idx(private_key->idx) == 0 ||
01246        ecc_is_valid_idx(public_key->idx)  == 0)
01247       return ECC_BAD_ARG_E;
01248 
01249    if (XSTRNCMP(private_key->dp->name, public_key->dp->name, ECC_MAXNAME) != 0)
01250       return ECC_BAD_ARG_E;
01251 
01252    /* make new point */
01253    result = ecc_new_point();
01254    if (result == NULL) {
01255       return MEMORY_E;
01256    }
01257 
01258    if ((err = mp_init(&prime)) != MP_OKAY) {
01259       ecc_del_point(result);
01260       return err;
01261    }
01262 
01263    err = mp_read_radix(&prime, (char *)private_key->dp->prime, 16);
01264 
01265    if (err == MP_OKAY)
01266        err = ecc_mulmod(&private_key->k, &public_key->pubkey, result, &prime,1);
01267 
01268    if (err == MP_OKAY) {
01269        x = mp_unsigned_bin_size(&prime);
01270        if (*outlen < x)
01271           err = BUFFER_E;
01272    }
01273 
01274    if (err == MP_OKAY) {
01275        XMEMSET(out, 0, x);
01276        err = mp_to_unsigned_bin(&result->x,out + (x -
01277                                             mp_unsigned_bin_size(&result->x)));
01278        *outlen = x;
01279    }
01280 
01281    mp_clear(&prime);
01282    ecc_del_point(result);
01283 
01284    return err;
01285 }
01286 
01287 
01288 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp);
01289 
01290 /**
01291   Make a new ECC key 
01292   rng          An active RNG state
01293   keysize      The keysize for the new key (in octets from 20 to 65 bytes)
01294   key          [out] Destination of the newly created key
01295   return       MP_OKAY if successful,
01296                        upon error all allocated memory will be freed
01297 */
01298 int ecc_make_key(RNG* rng, int keysize, ecc_key* key)
01299 {
01300    int x, err;
01301 
01302    /* find key size */
01303    for (x = 0; (keysize > ecc_sets[x].size) && (ecc_sets[x].size != 0); x++)
01304        ;
01305    keysize = ecc_sets[x].size;
01306 
01307    if (keysize > ECC_MAXSIZE || ecc_sets[x].size == 0) {
01308       return BAD_FUNC_ARG;
01309    }
01310    err = ecc_make_key_ex(rng, key, &ecc_sets[x]);
01311    key->idx = x;
01312 
01313    return err;
01314 }
01315 
01316 int ecc_make_key_ex(RNG* rng, ecc_key* key, const ecc_set_type* dp)
01317 {
01318    int            err;
01319    ecc_point*     base;
01320    mp_int         prime;
01321    mp_int         order;
01322    byte           buf[ECC_MAXSIZE];
01323    int            keysize;
01324 
01325    if (key == NULL || rng == NULL || dp == NULL)
01326        return ECC_BAD_ARG_E;
01327 
01328    key->idx = -1;
01329    key->dp  = dp;
01330    keysize  = dp->size;
01331 
01332    /* allocate ram */
01333    base = NULL;
01334 
01335    /* make up random string */
01336    RNG_GenerateBlock(rng, buf, keysize);
01337    buf[0] |= 0x0c;
01338 
01339    /* setup the key variables */
01340    if ((err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z,
01341                             &key->k, &prime, &order)) != MP_OKAY)
01342        return MEMORY_E;
01343 
01344    base = ecc_new_point();
01345    if (base == NULL)
01346       err = MEMORY_E;
01347 
01348    /* read in the specs for this key */
01349    if (err == MP_OKAY) 
01350        err = mp_read_radix(&prime,   (char *)key->dp->prime, 16);
01351    if (err == MP_OKAY) 
01352        err = mp_read_radix(&order,   (char *)key->dp->order, 16);
01353    if (err == MP_OKAY) 
01354        err = mp_read_radix(&base->x, (char *)key->dp->Gx, 16);
01355    if (err == MP_OKAY) 
01356        err = mp_read_radix(&base->y, (char *)key->dp->Gy, 16);
01357    
01358    if (err == MP_OKAY) 
01359        mp_set(&base->z, 1);
01360    if (err == MP_OKAY) 
01361        err = mp_read_unsigned_bin(&key->k, (byte*)buf, keysize);
01362 
01363    /* the key should be smaller than the order of base point */
01364    if (err == MP_OKAY) { 
01365        if (mp_cmp(&key->k, &order) != MP_LT)
01366            err = mp_mod(&key->k, &order, &key->k);
01367    }
01368    /* make the public key */
01369    if (err == MP_OKAY)
01370        err = ecc_mulmod(&key->k, base, &key->pubkey, &prime, 1);
01371    if (err == MP_OKAY)
01372        key->type = ECC_PRIVATEKEY;
01373 
01374    if (err != MP_OKAY) {
01375        /* clean up */
01376        mp_clear(&key->pubkey.x);
01377        mp_clear(&key->pubkey.y);
01378        mp_clear(&key->pubkey.z);
01379        mp_clear(&key->k);
01380    }
01381    ecc_del_point(base);
01382    mp_clear(&prime);
01383    mp_clear(&order);
01384 #ifdef ECC_CLEAN_STACK
01385    XMEMSET(buff, 0, ECC_MAXSIZE);
01386 #endif
01387    return err;
01388 }
01389 
01390 
01391 /* Setup dynamic pointers is using normal math for proper freeing */
01392 void ecc_init(ecc_key* key)
01393 {
01394     (void)key;
01395 #ifndef USE_FAST_MATH
01396     key->pubkey.x.dp = NULL;
01397     key->pubkey.y.dp = NULL;
01398     key->pubkey.z.dp = NULL;
01399 
01400     key->k.dp = NULL;
01401 #endif
01402 }
01403 
01404 
01405 /**
01406   Sign a message digest
01407   in        The message digest to sign
01408   inlen     The length of the digest
01409   out       [out] The destination for the signature
01410   outlen    [in/out] The max size and resulting size of the signature
01411   key       A private ECC key
01412   return    MP_OKAY if successful
01413 */
01414 int ecc_sign_hash(const byte* in, word32 inlen, byte* out, word32 *outlen, 
01415                   RNG* rng, ecc_key* key)
01416 {
01417    mp_int        r;
01418    mp_int        s;
01419    mp_int        e;
01420    mp_int        p;
01421    int           err;
01422 
01423    if (in == NULL || out == NULL || outlen == NULL || key == NULL || rng ==NULL)
01424        return ECC_BAD_ARG_E;
01425 
01426    /* is this a private key? */
01427    if (key->type != ECC_PRIVATEKEY) {
01428       return ECC_BAD_ARG_E;
01429    }
01430    
01431    /* is the IDX valid ?  */
01432    if (ecc_is_valid_idx(key->idx) != 1) {
01433       return ECC_BAD_ARG_E;
01434    }
01435 
01436    /* get the hash and load it as a bignum into 'e' */
01437    /* init the bignums */
01438    if ((err = mp_init_multi(&r, &s, &p, &e, NULL, NULL)) != MP_OKAY) { 
01439       return err;
01440    }
01441    err = mp_read_radix(&p, (char *)key->dp->order, 16);
01442 
01443    if (err == MP_OKAY) {
01444        /* we may need to truncate if hash is longer than key size */
01445        word32 orderBits = mp_count_bits(&p);
01446 
01447        /* truncate down to byte size, may be all that's needed */
01448        if ( (CYASSL_BIT_SIZE * inlen) > orderBits)
01449            inlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE;
01450        err = mp_read_unsigned_bin(&e, (byte*)in, inlen);
01451 
01452        /* may still need bit truncation too */
01453        if (err == MP_OKAY && (CYASSL_BIT_SIZE * inlen) > orderBits)
01454            mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7));
01455    }
01456 
01457    /* make up a key and export the public copy */
01458    if (err == MP_OKAY) {
01459        ecc_key pubkey;
01460        ecc_init(&pubkey);
01461        for (;;) {
01462            err = ecc_make_key_ex(rng, &pubkey, key->dp);
01463            if (err != MP_OKAY) break;
01464 
01465            /* find r = x1 mod n */
01466            err = mp_mod(&pubkey.pubkey.x, &p, &r);
01467            if (err != MP_OKAY) break;
01468 
01469            if (mp_iszero(&r) == MP_YES)
01470                ecc_free(&pubkey);
01471            else { 
01472                /* find s = (e + xr)/k */
01473                err = mp_invmod(&pubkey.k, &p, &pubkey.k);
01474                if (err != MP_OKAY) break;
01475 
01476                err = mp_mulmod(&key->k, &r, &p, &s);   /* s = xr */
01477                if (err != MP_OKAY) break;
01478            
01479                err = mp_add(&e, &s, &s);               /* s = e +  xr */
01480                if (err != MP_OKAY) break;
01481 
01482                err = mp_mod(&s, &p, &s);               /* s = e +  xr */
01483                if (err != MP_OKAY) break;
01484 
01485                err = mp_mulmod(&s, &pubkey.k, &p, &s); /* s = (e + xr)/k */
01486                if (err != MP_OKAY) break;
01487 
01488                ecc_free(&pubkey);
01489                if (mp_iszero(&s) == MP_NO)
01490                    break;
01491             }
01492        }
01493        ecc_free(&pubkey);
01494    }
01495 
01496    /* store as SEQUENCE { r, s -- integer } */
01497    if (err == MP_OKAY)
01498        err = StoreECC_DSA_Sig(out, outlen, &r, &s);
01499 
01500    mp_clear(&r);
01501    mp_clear(&s);
01502    mp_clear(&p);
01503    mp_clear(&e);
01504 
01505    return err;
01506 }
01507 
01508 
01509 /**
01510   Free an ECC key from memory
01511   key   The key you wish to free
01512 */
01513 void ecc_free(ecc_key* key)
01514 {
01515    if (key == NULL)
01516        return;
01517 
01518    mp_clear(&key->pubkey.x);
01519    mp_clear(&key->pubkey.y);
01520    mp_clear(&key->pubkey.z);
01521    mp_clear(&key->k);
01522 }
01523 
01524 
01525 #ifdef USE_FAST_MATH
01526     #define GEN_MEM_ERR FP_MEM
01527 #else
01528     #define GEN_MEM_ERR MP_MEM
01529 #endif
01530 
01531 #ifdef ECC_SHAMIR
01532 
01533 /** Computes kA*A + kB*B = C using Shamir's Trick
01534   A        First point to multiply
01535   kA       What to multiple A by
01536   B        Second point to multiply
01537   kB       What to multiple B by
01538   C        [out] Destination point (can overlap with A or B)
01539   modulus  Modulus for curve 
01540   return MP_OKAY on success
01541 */
01542 #ifdef FP_ECC
01543 static int normal_ecc_mul2add(ecc_point* A, mp_int* kA,
01544                              ecc_point* B, mp_int* kB,
01545                              ecc_point* C, mp_int* modulus)
01546 #else
01547 static int ecc_mul2add(ecc_point* A, mp_int* kA,
01548                     ecc_point* B, mp_int* kB,
01549                     ecc_point* C, mp_int* modulus)
01550 #endif
01551 {
01552   ecc_point*     precomp[16];
01553   unsigned       bitbufA, bitbufB, lenA, lenB, len, x, y, nA, nB, nibble;
01554   unsigned char* tA;
01555   unsigned char* tB;
01556   int            err = MP_OKAY, first;
01557   int            muInit    = 0;
01558   int            tableInit = 0;
01559   mp_digit mp;
01560   mp_int   mu;
01561  
01562   /* argchks */
01563   if (A == NULL || kA == NULL || B == NULL || kB == NULL || C == NULL || 
01564                    modulus == NULL)
01565     return ECC_BAD_ARG_E;
01566 
01567 
01568   /* allocate memory */
01569   tA = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
01570   if (tA == NULL) {
01571      return GEN_MEM_ERR;
01572   }
01573   tB = XMALLOC(ECC_BUFSIZE, NULL, DYNAMIC_TYPE_TMP_BUFFER);
01574   if (tB == NULL) {
01575      XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
01576      return GEN_MEM_ERR;
01577   }
01578   XMEMSET(tA, 0, ECC_BUFSIZE);
01579   XMEMSET(tB, 0, ECC_BUFSIZE);
01580 
01581   /* get sizes */
01582   lenA = mp_unsigned_bin_size(kA);
01583   lenB = mp_unsigned_bin_size(kB);
01584   len  = MAX(lenA, lenB);
01585 
01586   /* sanity check */
01587   if ((lenA > ECC_BUFSIZE) || (lenB > ECC_BUFSIZE)) {
01588      err = BAD_FUNC_ARG;
01589   }
01590 
01591   if (err == MP_OKAY) {
01592     /* extract and justify kA */
01593     err = mp_to_unsigned_bin(kA, (len - lenA) + tA);
01594 
01595     /* extract and justify kB */
01596     if (err == MP_OKAY)
01597         err = mp_to_unsigned_bin(kB, (len - lenB) + tB);
01598 
01599     /* allocate the table */
01600     if (err == MP_OKAY) {
01601         for (x = 0; x < 16; x++) {
01602             precomp[x] = ecc_new_point();
01603             if (precomp[x] == NULL) {
01604                 for (y = 0; y < x; ++y) {
01605                     ecc_del_point(precomp[y]);
01606                 }
01607                 err = GEN_MEM_ERR;
01608                 break;
01609             }
01610         }
01611     }
01612   }
01613 
01614   if (err == MP_OKAY)
01615     tableInit = 1;
01616 
01617   if (err == MP_OKAY)
01618    /* init montgomery reduction */
01619    err = mp_montgomery_setup(modulus, &mp);
01620 
01621   if (err == MP_OKAY)
01622     err = mp_init(&mu);
01623   if (err == MP_OKAY)
01624     muInit = 1;
01625 
01626   if (err == MP_OKAY)
01627     err = mp_montgomery_calc_normalization(&mu, modulus);
01628 
01629   if (err == MP_OKAY)
01630     /* copy ones ... */
01631     err = mp_mulmod(&A->x, &mu, modulus, &precomp[1]->x);
01632 
01633   if (err == MP_OKAY)
01634     err = mp_mulmod(&A->y, &mu, modulus, &precomp[1]->y);
01635   if (err == MP_OKAY)
01636     err = mp_mulmod(&A->z, &mu, modulus, &precomp[1]->z);
01637 
01638   if (err == MP_OKAY)
01639     err = mp_mulmod(&B->x, &mu, modulus, &precomp[1<<2]->x);
01640   if (err == MP_OKAY)
01641     err = mp_mulmod(&B->y, &mu, modulus, &precomp[1<<2]->y);
01642   if (err == MP_OKAY)
01643     err = mp_mulmod(&B->z, &mu, modulus, &precomp[1<<2]->z);
01644 
01645   if (err == MP_OKAY)
01646     /* precomp [i,0](A + B) table */
01647     err = ecc_projective_dbl_point(precomp[1], precomp[2], modulus, &mp);
01648 
01649   if (err == MP_OKAY)
01650     err = ecc_projective_add_point(precomp[1], precomp[2], precomp[3],
01651                                    modulus, &mp);
01652   if (err == MP_OKAY)
01653     /* precomp [0,i](A + B) table */
01654     err = ecc_projective_dbl_point(precomp[1<<2], precomp[2<<2], modulus, &mp);
01655 
01656   if (err == MP_OKAY)
01657     err = ecc_projective_add_point(precomp[1<<2], precomp[2<<2], precomp[3<<2],
01658                                    modulus, &mp);
01659 
01660   if (err == MP_OKAY) {
01661     /* precomp [i,j](A + B) table (i != 0, j != 0) */
01662     for (x = 1; x < 4; x++) {
01663         for (y = 1; y < 4; y++) {
01664             if (err == MP_OKAY)
01665                 err = ecc_projective_add_point(precomp[x], precomp[(y<<2)],
01666                                                precomp[x+(y<<2)], modulus, &mp);
01667         }
01668     } 
01669   }  
01670 
01671   if (err == MP_OKAY) {
01672     nibble  = 3;
01673     first   = 1;
01674     bitbufA = tA[0];
01675     bitbufB = tB[0];
01676 
01677     /* for every byte of the multiplicands */
01678     for (x = -1;; ) {
01679         /* grab a nibble */
01680         if (++nibble == 4) {
01681             ++x; if (x == len) break;
01682             bitbufA = tA[x];
01683             bitbufB = tB[x];
01684             nibble  = 0;
01685         }
01686 
01687         /* extract two bits from both, shift/update */
01688         nA = (bitbufA >> 6) & 0x03;
01689         nB = (bitbufB >> 6) & 0x03;
01690         bitbufA = (bitbufA << 2) & 0xFF;   
01691         bitbufB = (bitbufB << 2) & 0xFF;   
01692 
01693         /* if both zero, if first, continue */
01694         if ((nA == 0) && (nB == 0) && (first == 1)) {
01695             continue;
01696         }
01697 
01698         /* double twice, only if this isn't the first */
01699         if (first == 0) {
01700             /* double twice */
01701             if (err == MP_OKAY)
01702                 err = ecc_projective_dbl_point(C, C, modulus, &mp);
01703             if (err == MP_OKAY)
01704                 err = ecc_projective_dbl_point(C, C, modulus, &mp);
01705             else
01706                 break;
01707         }
01708 
01709         /* if not both zero */
01710         if ((nA != 0) || (nB != 0)) {
01711             if (first == 1) {
01712                 /* if first, copy from table */
01713                 first = 0;
01714                 if (err == MP_OKAY)
01715                     err = mp_copy(&precomp[nA + (nB<<2)]->x, &C->x);
01716 
01717                 if (err == MP_OKAY)
01718                     err = mp_copy(&precomp[nA + (nB<<2)]->y, &C->y);
01719 
01720                 if (err == MP_OKAY)
01721                     err = mp_copy(&precomp[nA + (nB<<2)]->z, &C->z);
01722                 else
01723                     break;
01724             } else {
01725                 /* if not first, add from table */
01726                 if (err == MP_OKAY)
01727                     err = ecc_projective_add_point(C, precomp[nA + (nB<<2)], C,
01728                                                    modulus, &mp);
01729                 else
01730                     break;
01731             }
01732         }
01733     }
01734   }
01735 
01736   if (err == MP_OKAY)
01737     /* reduce to affine */
01738     err = ecc_map(C, modulus, &mp);
01739 
01740   /* clean up */
01741   if (muInit)
01742     mp_clear(&mu);
01743 
01744   if (tableInit) {
01745     for (x = 0; x < 16; x++) {
01746        ecc_del_point(precomp[x]);
01747     }
01748   }
01749 #ifdef ECC_CLEAN_STACK
01750    XMEMSET(tA, 0, ECC_BUF_SIZE);
01751    XMEMSET(tB, 0, ECC_BUF_SIZE);
01752 #endif
01753    XFREE(tA, NULL, DYNAMIC_TYPE_TMP_BUFFER);
01754    XFREE(tB, NULL, DYNAMIC_TYPE_TMP_BUFFER);
01755 
01756    return err;
01757 }
01758 
01759 
01760 #endif /* ECC_SHAMIR */
01761 
01762 
01763 
01764 /* verify 
01765  *
01766  * w  = s^-1 mod n
01767  * u1 = xw 
01768  * u2 = rw
01769  * X = u1*G + u2*Q
01770  * v = X_x1 mod n
01771  * accept if v == r
01772  */
01773 
01774 /**
01775    Verify an ECC signature
01776    sig         The signature to verify
01777    siglen      The length of the signature (octets)
01778    hash        The hash (message digest) that was signed
01779    hashlen     The length of the hash (octets)
01780    stat        Result of signature, 1==valid, 0==invalid
01781    key         The corresponding public ECC key
01782    return      MP_OKAY if successful (even if the signature is not valid)
01783 */
01784 int ecc_verify_hash(const byte* sig, word32 siglen, const byte* hash,
01785                     word32 hashlen, int* stat, ecc_key* key)
01786 {
01787    ecc_point    *mG, *mQ;
01788    mp_int        r;
01789    mp_int        s;
01790    mp_int        v;
01791    mp_int        w;
01792    mp_int        u1;
01793    mp_int        u2;
01794    mp_int        e;
01795    mp_int        p;
01796    mp_int        m;
01797    int           err;
01798 
01799    if (sig == NULL || hash == NULL || stat == NULL || key == NULL)
01800        return ECC_BAD_ARG_E; 
01801 
01802    /* default to invalid signature */
01803    *stat = 0;
01804 
01805    /* is the IDX valid ?  */
01806    if (ecc_is_valid_idx(key->idx) != 1) {
01807       return ECC_BAD_ARG_E;
01808    }
01809 
01810    /* allocate ints */
01811    if ((err = mp_init_multi(&v, &w, &u1, &u2, &p, &e)) != MP_OKAY) {
01812       return MEMORY_E;
01813    }
01814 
01815    if ((err = mp_init(&m)) != MP_OKAY) {
01816       mp_clear(&v);
01817       mp_clear(&w);
01818       mp_clear(&u1);
01819       mp_clear(&u2);
01820       mp_clear(&p);
01821       mp_clear(&e);
01822       return MEMORY_E;
01823    }
01824 
01825    /* allocate points */
01826    mG = ecc_new_point();
01827    mQ = ecc_new_point();
01828    if (mQ  == NULL || mG == NULL)
01829       err = MEMORY_E;
01830 
01831    /* Note, DecodeECC_DSA_Sig() calls mp_init() on r and s.
01832     * If either of those don't allocate correctly, none of
01833     * the rest of this function will execute, and everything
01834     * gets cleaned up at the end. */
01835    XMEMSET(&r, 0, sizeof(r));
01836    XMEMSET(&s, 0, sizeof(s));
01837    if (err == MP_OKAY) 
01838        err = DecodeECC_DSA_Sig(sig, siglen, &r, &s);
01839 
01840    /* get the order */
01841    if (err == MP_OKAY)
01842        err = mp_read_radix(&p, (char *)key->dp->order, 16);
01843 
01844    /* get the modulus */
01845    if (err == MP_OKAY)
01846        err = mp_read_radix(&m, (char *)key->dp->prime, 16);
01847 
01848    /* check for zero */
01849    if (err == MP_OKAY) {
01850        if (mp_iszero(&r) || mp_iszero(&s) || mp_cmp(&r, &p) != MP_LT ||
01851                                              mp_cmp(&s, &p) != MP_LT)
01852            err = MP_ZERO_E; 
01853    }
01854    /* read hash */
01855    if (err == MP_OKAY) {
01856        /* we may need to truncate if hash is longer than key size */
01857        unsigned int orderBits = mp_count_bits(&p);
01858 
01859        /* truncate down to byte size, may be all that's needed */
01860        if ( (CYASSL_BIT_SIZE * hashlen) > orderBits)
01861            hashlen = (orderBits + CYASSL_BIT_SIZE - 1)/CYASSL_BIT_SIZE;
01862        err = mp_read_unsigned_bin(&e, hash, hashlen);
01863 
01864        /* may still need bit truncation too */
01865        if (err == MP_OKAY && (CYASSL_BIT_SIZE * hashlen) > orderBits)
01866            mp_rshb(&e, CYASSL_BIT_SIZE - (orderBits & 0x7));
01867    }
01868 
01869    /*  w  = s^-1 mod n */
01870    if (err == MP_OKAY)
01871        err = mp_invmod(&s, &p, &w);
01872 
01873    /* u1 = ew */
01874    if (err == MP_OKAY)
01875        err = mp_mulmod(&e, &w, &p, &u1);
01876 
01877    /* u2 = rw */
01878    if (err == MP_OKAY)
01879        err = mp_mulmod(&r, &w, &p, &u2);
01880 
01881    /* find mG and mQ */
01882    if (err == MP_OKAY)
01883        err = mp_read_radix(&mG->x, (char *)key->dp->Gx, 16);
01884 
01885    if (err == MP_OKAY)
01886        err = mp_read_radix(&mG->y, (char *)key->dp->Gy, 16);
01887    if (err == MP_OKAY)
01888        mp_set(&mG->z, 1);
01889 
01890    if (err == MP_OKAY)
01891        err = mp_copy(&key->pubkey.x, &mQ->x);
01892    if (err == MP_OKAY)
01893        err = mp_copy(&key->pubkey.y, &mQ->y);
01894    if (err == MP_OKAY)
01895        err = mp_copy(&key->pubkey.z, &mQ->z);
01896 
01897 #ifndef ECC_SHAMIR
01898     {
01899        mp_digit      mp;
01900 
01901        /* compute u1*mG + u2*mQ = mG */
01902        if (err == MP_OKAY)
01903            err = ecc_mulmod(&u1, mG, mG, &m, 0);
01904        if (err == MP_OKAY)
01905            err = ecc_mulmod(&u2, mQ, mQ, &m, 0);
01906   
01907        /* find the montgomery mp */
01908        if (err == MP_OKAY)
01909            err = mp_montgomery_setup(&m, &mp);
01910 
01911        /* add them */
01912        if (err == MP_OKAY)
01913            err = ecc_projective_add_point(mQ, mG, mG, &m, &mp);
01914    
01915        /* reduce */
01916        if (err == MP_OKAY)
01917            err = ecc_map(mG, &m, &mp);
01918     }
01919 #else
01920        /* use Shamir's trick to compute u1*mG + u2*mQ using half the doubles */
01921        if (err == MP_OKAY)
01922            err = ecc_mul2add(mG, &u1, mQ, &u2, mG, &m);
01923 #endif /* ECC_SHAMIR */ 
01924 
01925    /* v = X_x1 mod n */
01926    if (err == MP_OKAY)
01927        err = mp_mod(&mG->x, &p, &v);
01928 
01929    /* does v == r */
01930    if (err == MP_OKAY) {
01931        if (mp_cmp(&v, &r) == MP_EQ)
01932            *stat = 1;
01933    }
01934 
01935    ecc_del_point(mG);
01936    ecc_del_point(mQ);
01937 
01938    mp_clear(&r);
01939    mp_clear(&s);
01940    mp_clear(&v);
01941    mp_clear(&w);
01942    mp_clear(&u1);
01943    mp_clear(&u2);
01944    mp_clear(&p);
01945    mp_clear(&e);
01946    mp_clear(&m);
01947 
01948    return err;
01949 }
01950 
01951 
01952 /* export public ECC key in ANSI X9.63 format */
01953 int ecc_export_x963(ecc_key* key, byte* out, word32* outLen)
01954 {
01955    byte   buf[ECC_BUFSIZE];
01956    word32 numlen;
01957    int    ret = MP_OKAY;
01958 
01959    if (key == NULL || out == NULL || outLen == NULL)
01960        return ECC_BAD_ARG_E;
01961 
01962    if (ecc_is_valid_idx(key->idx) == 0) {
01963       return ECC_BAD_ARG_E;
01964    }
01965    numlen = key->dp->size;
01966 
01967    if (*outLen < (1 + 2*numlen)) {
01968       *outLen = 1 + 2*numlen;
01969       return BUFFER_E;
01970    }
01971 
01972    /* store byte 0x04 */
01973    out[0] = 0x04;
01974 
01975    /* pad and store x */
01976    XMEMSET(buf, 0, sizeof(buf));
01977    ret = mp_to_unsigned_bin(&key->pubkey.x,
01978                       buf + (numlen - mp_unsigned_bin_size(&key->pubkey.x)));
01979    if (ret != MP_OKAY)
01980        return ret;
01981    XMEMCPY(out+1, buf, numlen);
01982 
01983    /* pad and store y */
01984    XMEMSET(buf, 0, sizeof(buf));
01985    ret = mp_to_unsigned_bin(&key->pubkey.y,
01986                       buf + (numlen - mp_unsigned_bin_size(&key->pubkey.y)));
01987    if (ret != MP_OKAY)
01988        return ret;
01989    XMEMCPY(out+1+numlen, buf, numlen);
01990 
01991    *outLen = 1 + 2*numlen;
01992 
01993    return 0;
01994 }
01995 
01996 
01997 /* import public ECC key in ANSI X9.63 format */
01998 int ecc_import_x963(const byte* in, word32 inLen, ecc_key* key)
01999 {
02000    int x, err;
02001    
02002    if (in == NULL || key == NULL)
02003        return ECC_BAD_ARG_E;
02004 
02005    /* must be odd */
02006    if ((inLen & 1) == 0) {
02007       return ECC_BAD_ARG_E;
02008    }
02009 
02010    /* init key */
02011    if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k,
02012                      NULL, NULL) != MP_OKAY) {
02013       return MEMORY_E;
02014    }
02015    err = MP_OKAY;
02016 
02017    /* check for 4, 6 or 7 */
02018    if (in[0] != 4 && in[0] != 6 && in[0] != 7) {
02019       err = ASN_PARSE_E;
02020    }
02021 
02022    /* read data */
02023    if (err == MP_OKAY) 
02024        err = mp_read_unsigned_bin(&key->pubkey.x, (byte*)in+1, (inLen-1)>>1);
02025 
02026    if (err == MP_OKAY) 
02027        err = mp_read_unsigned_bin(&key->pubkey.y, (byte*)in+1+((inLen-1)>>1),
02028                                   (inLen-1)>>1);
02029    
02030    if (err == MP_OKAY) 
02031        mp_set(&key->pubkey.z, 1);
02032 
02033    if (err == MP_OKAY) {
02034      /* determine the idx */
02035       for (x = 0; ecc_sets[x].size != 0; x++) {
02036          if ((unsigned)ecc_sets[x].size >= ((inLen-1)>>1)) {
02037             break;
02038          }
02039       }
02040       if (ecc_sets[x].size == 0) {
02041          err = ASN_PARSE_E;
02042       } else {
02043           /* set the idx */
02044           key->idx  = x;
02045           key->dp = &ecc_sets[x];
02046           key->type = ECC_PUBLICKEY;
02047       }
02048    }
02049 
02050    if (err != MP_OKAY) {
02051        mp_clear(&key->pubkey.x);
02052        mp_clear(&key->pubkey.y);
02053        mp_clear(&key->pubkey.z);
02054        mp_clear(&key->k);
02055    }
02056 
02057    return err;
02058 }
02059 
02060 
02061 /* export ecc private key only raw, outLen is in/out size 
02062    return MP_OKAY on success */
02063 int ecc_export_private_only(ecc_key* key, byte* out, word32* outLen)
02064 {
02065    word32 numlen;
02066 
02067    if (key == NULL || out == NULL || outLen == NULL)
02068        return ECC_BAD_ARG_E;
02069 
02070    if (ecc_is_valid_idx(key->idx) == 0) {
02071       return ECC_BAD_ARG_E;
02072    }
02073    numlen = key->dp->size;
02074 
02075    if (*outLen < numlen) {
02076       *outLen = numlen;
02077       return BUFFER_E;
02078    }
02079    *outLen = numlen; 
02080    XMEMSET(out, 0, *outLen);
02081    return mp_to_unsigned_bin(&key->k, out + (numlen -
02082                                              mp_unsigned_bin_size(&key->k)));
02083 }
02084 
02085 
02086 /* ecc private key import, public key in ANSI X9.63 format, private raw */
02087 int ecc_import_private_key(const byte* priv, word32 privSz, const byte* pub,
02088                            word32 pubSz, ecc_key* key)
02089 {
02090     int ret = ecc_import_x963(pub, pubSz, key);
02091     if (ret != 0)
02092         return ret;
02093 
02094     key->type = ECC_PRIVATEKEY;
02095 
02096     return mp_read_unsigned_bin(&key->k, priv, privSz);
02097 }
02098 
02099 
02100 /* key size in octets */
02101 int ecc_size(ecc_key* key)
02102 {
02103     if (key == NULL) return 0;
02104 
02105     return key->dp->size;
02106 }
02107 
02108 
02109 /* worst case estimate, check actual return from ecc_sign_hash for actual value
02110    of signature size in octets */
02111 int ecc_sig_size(ecc_key* key)
02112 {
02113     int sz = ecc_size(key);
02114     if (sz < 0)
02115         return sz;
02116 
02117     return sz * 2 + SIG_HEADER_SZ + 4;  /* (4) worst case estimate */
02118 }
02119 
02120 
02121 #ifdef FP_ECC
02122 
02123 /* fixed point ECC cache */
02124 /* number of entries in the cache */
02125 #ifndef FP_ENTRIES
02126     #define FP_ENTRIES 16
02127 #endif
02128 
02129 /* number of bits in LUT */
02130 #ifndef FP_LUT
02131     #define FP_LUT     8U
02132 #endif
02133 
02134 #ifdef ECC_SHAMIR
02135     /* Sharmir requires a bigger LUT, TAO */
02136     #if (FP_LUT > 12) || (FP_LUT < 4)
02137         #error FP_LUT must be between 4 and 12 inclusively
02138     #endif
02139 #else
02140     #if (FP_LUT > 12) || (FP_LUT < 2)
02141         #error FP_LUT must be between 2 and 12 inclusively
02142     #endif
02143 #endif
02144 
02145 
02146 /** Our FP cache */
02147 typedef struct {
02148    ecc_point* g;               /* cached COPY of base point */
02149    ecc_point* LUT[1U<<FP_LUT]; /* fixed point lookup */ 
02150    mp_int     mu;              /* copy of the montgomery constant */
02151    int        lru_count;       /* amount of times this entry has been used */
02152    int        lock;            /* flag to indicate cache eviction */
02153                                /* permitted (0) or not (1) */
02154 } fp_cache_t;
02155 
02156 /* if HAVE_THREAD_LS this cache is per thread, no locking needed */
02157 static THREAD_LS_T fp_cache_t fp_cache[FP_ENTRIES];
02158 
02159 #ifndef HAVE_THREAD_LS
02160     static volatile int initMutex = 0;  /* prevent multiple mutex inits */
02161     static CyaSSL_Mutex ecc_fp_lock;
02162 #endif /* HAVE_THREAD_LS */
02163 
02164 /* simple table to help direct the generation of the LUT */
02165 static const struct {
02166    int ham, terma, termb;
02167 } lut_orders[] = {
02168    { 0, 0, 0 }, { 1, 0, 0 }, { 1, 0, 0 }, { 2, 1, 2 }, { 1, 0, 0 }, { 2, 1, 4 }, { 2, 2, 4 }, { 3, 3, 4 }, 
02169    { 1, 0, 0 }, { 2, 1, 8 }, { 2, 2, 8 }, { 3, 3, 8 }, { 2, 4, 8 }, { 3, 5, 8 }, { 3, 6, 8 }, { 4, 7, 8 }, 
02170    { 1, 0, 0 }, { 2, 1, 16 }, { 2, 2, 16 }, { 3, 3, 16 }, { 2, 4, 16 }, { 3, 5, 16 }, { 3, 6, 16 }, { 4, 7, 16 }, 
02171    { 2, 8, 16 }, { 3, 9, 16 }, { 3, 10, 16 }, { 4, 11, 16 }, { 3, 12, 16 }, { 4, 13, 16 }, { 4, 14, 16 }, { 5, 15, 16 }, 
02172    { 1, 0, 0 }, { 2, 1, 32 }, { 2, 2, 32 }, { 3, 3, 32 }, { 2, 4, 32 }, { 3, 5, 32 }, { 3, 6, 32 }, { 4, 7, 32 }, 
02173    { 2, 8, 32 }, { 3, 9, 32 }, { 3, 10, 32 }, { 4, 11, 32 }, { 3, 12, 32 }, { 4, 13, 32 }, { 4, 14, 32 }, { 5, 15, 32 }, 
02174    { 2, 16, 32 }, { 3, 17, 32 }, { 3, 18, 32 }, { 4, 19, 32 }, { 3, 20, 32 }, { 4, 21, 32 }, { 4, 22, 32 }, { 5, 23, 32 }, 
02175    { 3, 24, 32 }, { 4, 25, 32 }, { 4, 26, 32 }, { 5, 27, 32 }, { 4, 28, 32 }, { 5, 29, 32 }, { 5, 30, 32 }, { 6, 31, 32 }, 
02176 #if FP_LUT > 6
02177    { 1, 0, 0 }, { 2, 1, 64 }, { 2, 2, 64 }, { 3, 3, 64 }, { 2, 4, 64 }, { 3, 5, 64 }, { 3, 6, 64 }, { 4, 7, 64 }, 
02178    { 2, 8, 64 }, { 3, 9, 64 }, { 3, 10, 64 }, { 4, 11, 64 }, { 3, 12, 64 }, { 4, 13, 64 }, { 4, 14, 64 }, { 5, 15, 64 }, 
02179    { 2, 16, 64 }, { 3, 17, 64 }, { 3, 18, 64 }, { 4, 19, 64 }, { 3, 20, 64 }, { 4, 21, 64 }, { 4, 22, 64 }, { 5, 23, 64 }, 
02180    { 3, 24, 64 }, { 4, 25, 64 }, { 4, 26, 64 }, { 5, 27, 64 }, { 4, 28, 64 }, { 5, 29, 64 }, { 5, 30, 64 }, { 6, 31, 64 }, 
02181    { 2, 32, 64 }, { 3, 33, 64 }, { 3, 34, 64 }, { 4, 35, 64 }, { 3, 36, 64 }, { 4, 37, 64 }, { 4, 38, 64 }, { 5, 39, 64 }, 
02182    { 3, 40, 64 }, { 4, 41, 64 }, { 4, 42, 64 }, { 5, 43, 64 }, { 4, 44, 64 }, { 5, 45, 64 }, { 5, 46, 64 }, { 6, 47, 64 }, 
02183    { 3, 48, 64 }, { 4, 49, 64 }, { 4, 50, 64 }, { 5, 51, 64 }, { 4, 52, 64 }, { 5, 53, 64 }, { 5, 54, 64 }, { 6, 55, 64 }, 
02184    { 4, 56, 64 }, { 5, 57, 64 }, { 5, 58, 64 }, { 6, 59, 64 }, { 5, 60, 64 }, { 6, 61, 64 }, { 6, 62, 64 }, { 7, 63, 64 }, 
02185 #if FP_LUT > 7
02186    { 1, 0, 0 }, { 2, 1, 128 }, { 2, 2, 128 }, { 3, 3, 128 }, { 2, 4, 128 }, { 3, 5, 128 }, { 3, 6, 128 }, { 4, 7, 128 }, 
02187    { 2, 8, 128 }, { 3, 9, 128 }, { 3, 10, 128 }, { 4, 11, 128 }, { 3, 12, 128 }, { 4, 13, 128 }, { 4, 14, 128 }, { 5, 15, 128 }, 
02188    { 2, 16, 128 }, { 3, 17, 128 }, { 3, 18, 128 }, { 4, 19, 128 }, { 3, 20, 128 }, { 4, 21, 128 }, { 4, 22, 128 }, { 5, 23, 128 }, 
02189    { 3, 24, 128 }, { 4, 25, 128 }, { 4, 26, 128 }, { 5, 27, 128 }, { 4, 28, 128 }, { 5, 29, 128 }, { 5, 30, 128 }, { 6, 31, 128 }, 
02190    { 2, 32, 128 }, { 3, 33, 128 }, { 3, 34, 128 }, { 4, 35, 128 }, { 3, 36, 128 }, { 4, 37, 128 }, { 4, 38, 128 }, { 5, 39, 128 }, 
02191    { 3, 40, 128 }, { 4, 41, 128 }, { 4, 42, 128 }, { 5, 43, 128 }, { 4, 44, 128 }, { 5, 45, 128 }, { 5, 46, 128 }, { 6, 47, 128 }, 
02192    { 3, 48, 128 }, { 4, 49, 128 }, { 4, 50, 128 }, { 5, 51, 128 }, { 4, 52, 128 }, { 5, 53, 128 }, { 5, 54, 128 }, { 6, 55, 128 }, 
02193    { 4, 56, 128 }, { 5, 57, 128 }, { 5, 58, 128 }, { 6, 59, 128 }, { 5, 60, 128 }, { 6, 61, 128 }, { 6, 62, 128 }, { 7, 63, 128 }, 
02194    { 2, 64, 128 }, { 3, 65, 128 }, { 3, 66, 128 }, { 4, 67, 128 }, { 3, 68, 128 }, { 4, 69, 128 }, { 4, 70, 128 }, { 5, 71, 128 }, 
02195    { 3, 72, 128 }, { 4, 73, 128 }, { 4, 74, 128 }, { 5, 75, 128 }, { 4, 76, 128 }, { 5, 77, 128 }, { 5, 78, 128 }, { 6, 79, 128 }, 
02196    { 3, 80, 128 }, { 4, 81, 128 }, { 4, 82, 128 }, { 5, 83, 128 }, { 4, 84, 128 }, { 5, 85, 128 }, { 5, 86, 128 }, { 6, 87, 128 }, 
02197    { 4, 88, 128 }, { 5, 89, 128 }, { 5, 90, 128 }, { 6, 91, 128 }, { 5, 92, 128 }, { 6, 93, 128 }, { 6, 94, 128 }, { 7, 95, 128 }, 
02198    { 3, 96, 128 }, { 4, 97, 128 }, { 4, 98, 128 }, { 5, 99, 128 }, { 4, 100, 128 }, { 5, 101, 128 }, { 5, 102, 128 }, { 6, 103, 128 }, 
02199    { 4, 104, 128 }, { 5, 105, 128 }, { 5, 106, 128 }, { 6, 107, 128 }, { 5, 108, 128 }, { 6, 109, 128 }, { 6, 110, 128 }, { 7, 111, 128 }, 
02200    { 4, 112, 128 }, { 5, 113, 128 }, { 5, 114, 128 }, { 6, 115, 128 }, { 5, 116, 128 }, { 6, 117, 128 }, { 6, 118, 128 }, { 7, 119, 128 }, 
02201    { 5, 120, 128 }, { 6, 121, 128 }, { 6, 122, 128 }, { 7, 123, 128 }, { 6, 124, 128 }, { 7, 125, 128 }, { 7, 126, 128 }, { 8, 127, 128 }, 
02202 #if FP_LUT > 8
02203    { 1, 0, 0 }, { 2, 1, 256 }, { 2, 2, 256 }, { 3, 3, 256 }, { 2, 4, 256 }, { 3, 5, 256 }, { 3, 6, 256 }, { 4, 7, 256 }, 
02204    { 2, 8, 256 }, { 3, 9, 256 }, { 3, 10, 256 }, { 4, 11, 256 }, { 3, 12, 256 }, { 4, 13, 256 }, { 4, 14, 256 }, { 5, 15, 256 }, 
02205    { 2, 16, 256 }, { 3, 17, 256 }, { 3, 18, 256 }, { 4, 19, 256 }, { 3, 20, 256 }, { 4, 21, 256 }, { 4, 22, 256 }, { 5, 23, 256 }, 
02206    { 3, 24, 256 }, { 4, 25, 256 }, { 4, 26, 256 }, { 5, 27, 256 }, { 4, 28, 256 }, { 5, 29, 256 }, { 5, 30, 256 }, { 6, 31, 256 }, 
02207    { 2, 32, 256 }, { 3, 33, 256 }, { 3, 34, 256 }, { 4, 35, 256 }, { 3, 36, 256 }, { 4, 37, 256 }, { 4, 38, 256 }, { 5, 39, 256 }, 
02208    { 3, 40, 256 }, { 4, 41, 256 }, { 4, 42, 256 }, { 5, 43, 256 }, { 4, 44, 256 }, { 5, 45, 256 }, { 5, 46, 256 }, { 6, 47, 256 }, 
02209    { 3, 48, 256 }, { 4, 49, 256 }, { 4, 50, 256 }, { 5, 51, 256 }, { 4, 52, 256 }, { 5, 53, 256 }, { 5, 54, 256 }, { 6, 55, 256 }, 
02210    { 4, 56, 256 }, { 5, 57, 256 }, { 5, 58, 256 }, { 6, 59, 256 }, { 5, 60, 256 }, { 6, 61, 256 }, { 6, 62, 256 }, { 7, 63, 256 }, 
02211    { 2, 64, 256 }, { 3, 65, 256 }, { 3, 66, 256 }, { 4, 67, 256 }, { 3, 68, 256 }, { 4, 69, 256 }, { 4, 70, 256 }, { 5, 71, 256 }, 
02212    { 3, 72, 256 }, { 4, 73, 256 }, { 4, 74, 256 }, { 5, 75, 256 }, { 4, 76, 256 }, { 5, 77, 256 }, { 5, 78, 256 }, { 6, 79, 256 }, 
02213    { 3, 80, 256 }, { 4, 81, 256 }, { 4, 82, 256 }, { 5, 83, 256 }, { 4, 84, 256 }, { 5, 85, 256 }, { 5, 86, 256 }, { 6, 87, 256 }, 
02214    { 4, 88, 256 }, { 5, 89, 256 }, { 5, 90, 256 }, { 6, 91, 256 }, { 5, 92, 256 }, { 6, 93, 256 }, { 6, 94, 256 }, { 7, 95, 256 }, 
02215    { 3, 96, 256 }, { 4, 97, 256 }, { 4, 98, 256 }, { 5, 99, 256 }, { 4, 100, 256 }, { 5, 101, 256 }, { 5, 102, 256 }, { 6, 103, 256 }, 
02216    { 4, 104, 256 }, { 5, 105, 256 }, { 5, 106, 256 }, { 6, 107, 256 }, { 5, 108, 256 }, { 6, 109, 256 }, { 6, 110, 256 }, { 7, 111, 256 }, 
02217    { 4, 112, 256 }, { 5, 113, 256 }, { 5, 114, 256 }, { 6, 115, 256 }, { 5, 116, 256 }, { 6, 117, 256 }, { 6, 118, 256 }, { 7, 119, 256 }, 
02218    { 5, 120, 256 }, { 6, 121, 256 }, { 6, 122, 256 }, { 7, 123, 256 }, { 6, 124, 256 }, { 7, 125, 256 }, { 7, 126, 256 }, { 8, 127, 256 }, 
02219    { 2, 128, 256 }, { 3, 129, 256 }, { 3, 130, 256 }, { 4, 131, 256 }, { 3, 132, 256 }, { 4, 133, 256 }, { 4, 134, 256 }, { 5, 135, 256 }, 
02220    { 3, 136, 256 }, { 4, 137, 256 }, { 4, 138, 256 }, { 5, 139, 256 }, { 4, 140, 256 }, { 5, 141, 256 }, { 5, 142, 256 }, { 6, 143, 256 }, 
02221    { 3, 144, 256 }, { 4, 145, 256 }, { 4, 146, 256 }, { 5, 147, 256 }, { 4, 148, 256 }, { 5, 149, 256 }, { 5, 150, 256 }, { 6, 151, 256 }, 
02222    { 4, 152, 256 }, { 5, 153, 256 }, { 5, 154, 256 }, { 6, 155, 256 }, { 5, 156, 256 }, { 6, 157, 256 }, { 6, 158, 256 }, { 7, 159, 256 }, 
02223    { 3, 160, 256 }, { 4, 161, 256 }, { 4, 162, 256 }, { 5, 163, 256 }, { 4, 164, 256 }, { 5, 165, 256 }, { 5, 166, 256 }, { 6, 167, 256 }, 
02224    { 4, 168, 256 }, { 5, 169, 256 }, { 5, 170, 256 }, { 6, 171, 256 }, { 5, 172, 256 }, { 6, 173, 256 }, { 6, 174, 256 }, { 7, 175, 256 }, 
02225    { 4, 176, 256 }, { 5, 177, 256 }, { 5, 178, 256 }, { 6, 179, 256 }, { 5, 180, 256 }, { 6, 181, 256 }, { 6, 182, 256 }, { 7, 183, 256 }, 
02226    { 5, 184, 256 }, { 6, 185, 256 }, { 6, 186, 256 }, { 7, 187, 256 }, { 6, 188, 256 }, { 7, 189, 256 }, { 7, 190, 256 }, { 8, 191, 256 }, 
02227    { 3, 192, 256 }, { 4, 193, 256 }, { 4, 194, 256 }, { 5, 195, 256 }, { 4, 196, 256 }, { 5, 197, 256 }, { 5, 198, 256 }, { 6, 199, 256 }, 
02228    { 4, 200, 256 }, { 5, 201, 256 }, { 5, 202, 256 }, { 6, 203, 256 }, { 5, 204, 256 }, { 6, 205, 256 }, { 6, 206, 256 }, { 7, 207, 256 }, 
02229    { 4, 208, 256 }, { 5, 209, 256 }, { 5, 210, 256 }, { 6, 211, 256 }, { 5, 212, 256 }, { 6, 213, 256 }, { 6, 214, 256 }, { 7, 215, 256 }, 
02230    { 5, 216, 256 }, { 6, 217, 256 }, { 6, 218, 256 }, { 7, 219, 256 }, { 6, 220, 256 }, { 7, 221, 256 }, { 7, 222, 256 }, { 8, 223, 256 }, 
02231    { 4, 224, 256 }, { 5, 225, 256 }, { 5, 226, 256 }, { 6, 227, 256 }, { 5, 228, 256 }, { 6, 229, 256 }, { 6, 230, 256 }, { 7, 231, 256 }, 
02232    { 5, 232, 256 }, { 6, 233, 256 }, { 6, 234, 256 }, { 7, 235, 256 }, { 6, 236, 256 }, { 7, 237, 256 }, { 7, 238, 256 }, { 8, 239, 256 }, 
02233    { 5, 240, 256 }, { 6, 241, 256 }, { 6, 242, 256 }, { 7, 243, 256 }, { 6, 244, 256 }, { 7, 245, 256 }, { 7, 246, 256 }, { 8, 247, 256 }, 
02234    { 6, 248, 256 }, { 7, 249, 256 }, { 7, 250, 256 }, { 8, 251, 256 }, { 7, 252, 256 }, { 8, 253, 256 }, { 8, 254, 256 }, { 9, 255, 256 }, 
02235 #if FP_LUT > 9
02236    { 1, 0, 0 }, { 2, 1, 512 }, { 2, 2, 512 }, { 3, 3, 512 }, { 2, 4, 512 }, { 3, 5, 512 }, { 3, 6, 512 }, { 4, 7, 512 }, 
02237    { 2, 8, 512 }, { 3, 9, 512 }, { 3, 10, 512 }, { 4, 11, 512 }, { 3, 12, 512 }, { 4, 13, 512 }, { 4, 14, 512 }, { 5, 15, 512 }, 
02238    { 2, 16, 512 }, { 3, 17, 512 }, { 3, 18, 512 }, { 4, 19, 512 }, { 3, 20, 512 }, { 4, 21, 512 }, { 4, 22, 512 }, { 5, 23, 512 }, 
02239    { 3, 24, 512 }, { 4, 25, 512 }, { 4, 26, 512 }, { 5, 27, 512 }, { 4, 28, 512 }, { 5, 29, 512 }, { 5, 30, 512 }, { 6, 31, 512 }, 
02240    { 2, 32, 512 }, { 3, 33, 512 }, { 3, 34, 512 }, { 4, 35, 512 }, { 3, 36, 512 }, { 4, 37, 512 }, { 4, 38, 512 }, { 5, 39, 512 }, 
02241    { 3, 40, 512 }, { 4, 41, 512 }, { 4, 42, 512 }, { 5, 43, 512 }, { 4, 44, 512 }, { 5, 45, 512 }, { 5, 46, 512 }, { 6, 47, 512 }, 
02242    { 3, 48, 512 }, { 4, 49, 512 }, { 4, 50, 512 }, { 5, 51, 512 }, { 4, 52, 512 }, { 5, 53, 512 }, { 5, 54, 512 }, { 6, 55, 512 }, 
02243    { 4, 56, 512 }, { 5, 57, 512 }, { 5, 58, 512 }, { 6, 59, 512 }, { 5, 60, 512 }, { 6, 61, 512 }, { 6, 62, 512 }, { 7, 63, 512 }, 
02244    { 2, 64, 512 }, { 3, 65, 512 }, { 3, 66, 512 }, { 4, 67, 512 }, { 3, 68, 512 }, { 4, 69, 512 }, { 4, 70, 512 }, { 5, 71, 512 }, 
02245    { 3, 72, 512 }, { 4, 73, 512 }, { 4, 74, 512 }, { 5, 75, 512 }, { 4, 76, 512 }, { 5, 77, 512 }, { 5, 78, 512 }, { 6, 79, 512 }, 
02246    { 3, 80, 512 }, { 4, 81, 512 }, { 4, 82, 512 }, { 5, 83, 512 }, { 4, 84, 512 }, { 5, 85, 512 }, { 5, 86, 512 }, { 6, 87, 512 }, 
02247    { 4, 88, 512 }, { 5, 89, 512 }, { 5, 90, 512 }, { 6, 91, 512 }, { 5, 92, 512 }, { 6, 93, 512 }, { 6, 94, 512 }, { 7, 95, 512 }, 
02248    { 3, 96, 512 }, { 4, 97, 512 }, { 4, 98, 512 }, { 5, 99, 512 }, { 4, 100, 512 }, { 5, 101, 512 }, { 5, 102, 512 }, { 6, 103, 512 }, 
02249    { 4, 104, 512 }, { 5, 105, 512 }, { 5, 106, 512 }, { 6, 107, 512 }, { 5, 108, 512 }, { 6, 109, 512 }, { 6, 110, 512 }, { 7, 111, 512 }, 
02250    { 4, 112, 512 }, { 5, 113, 512 }, { 5, 114, 512 }, { 6, 115, 512 }, { 5, 116, 512 }, { 6, 117, 512 }, { 6, 118, 512 }, { 7, 119, 512 }, 
02251    { 5, 120, 512 }, { 6, 121, 512 }, { 6, 122, 512 }, { 7, 123, 512 }, { 6, 124, 512 }, { 7, 125, 512 }, { 7, 126, 512 }, { 8, 127, 512 }, 
02252    { 2, 128, 512 }, { 3, 129, 512 }, { 3, 130, 512 }, { 4, 131, 512 }, { 3, 132, 512 }, { 4, 133, 512 }, { 4, 134, 512 }, { 5, 135, 512 }, 
02253    { 3, 136, 512 }, { 4, 137, 512 }, { 4, 138, 512 }, { 5, 139, 512 }, { 4, 140, 512 }, { 5, 141, 512 }, { 5, 142, 512 }, { 6, 143, 512 }, 
02254    { 3, 144, 512 }, { 4, 145, 512 }, { 4, 146, 512 }, { 5, 147, 512 }, { 4, 148, 512 }, { 5, 149, 512 }, { 5, 150, 512 }, { 6, 151, 512 }, 
02255    { 4, 152, 512 }, { 5, 153, 512 }, { 5, 154, 512 }, { 6, 155, 512 }, { 5, 156, 512 }, { 6, 157, 512 }, { 6, 158, 512 }, { 7, 159, 512 }, 
02256    { 3, 160, 512 }, { 4, 161, 512 }, { 4, 162, 512 }, { 5, 163, 512 }, { 4, 164, 512 }, { 5, 165, 512 }, { 5, 166, 512 }, { 6, 167, 512 }, 
02257    { 4, 168, 512 }, { 5, 169, 512 }, { 5, 170, 512 }, { 6, 171, 512 }, { 5, 172, 512 }, { 6, 173, 512 }, { 6, 174, 512 }, { 7, 175, 512 }, 
02258    { 4, 176, 512 }, { 5, 177, 512 }, { 5, 178, 512 }, { 6, 179, 512 }, { 5, 180, 512 }, { 6, 181, 512 }, { 6, 182, 512 }, { 7, 183, 512 }, 
02259    { 5, 184, 512 }, { 6, 185, 512 }, { 6, 186, 512 }, { 7, 187, 512 }, { 6, 188, 512 }, { 7, 189, 512 }, { 7, 190, 512 }, { 8, 191, 512 }, 
02260    { 3, 192, 512 }, { 4, 193, 512 }, { 4, 194, 512 }, { 5, 195, 512 }, { 4, 196, 512 }, { 5, 197, 512 }, { 5, 198, 512 }, { 6, 199, 512 }, 
02261    { 4, 200, 512 }, { 5, 201, 512 }, { 5, 202, 512 }, { 6, 203, 512 }, { 5, 204, 512 }, { 6, 205, 512 }, { 6, 206, 512 }, { 7, 207, 512 }, 
02262    { 4, 208, 512 }, { 5, 209, 512 }, { 5, 210, 512 }, { 6, 211, 512 }, { 5, 212, 512 }, { 6, 213, 512 }, { 6, 214, 512 }, { 7, 215, 512 }, 
02263    { 5, 216, 512 }, { 6, 217, 512 }, { 6, 218, 512 }, { 7, 219, 512 }, { 6, 220, 512 }, { 7, 221, 512 }, { 7, 222, 512 }, { 8, 223, 512 }, 
02264    { 4, 224, 512 }, { 5, 225, 512 }, { 5, 226, 512 }, { 6, 227, 512 }, { 5, 228, 512 }, { 6, 229, 512 }, { 6, 230, 512 }, { 7, 231, 512 }, 
02265    { 5, 232, 512 }, { 6, 233, 512 }, { 6, 234, 512 }, { 7, 235, 512 }, { 6, 236, 512 }, { 7, 237, 512 }, { 7, 238, 512 }, { 8, 239, 512 }, 
02266    { 5, 240, 512 }, { 6, 241, 512 }, { 6, 242, 512 }, { 7, 243, 512 }, { 6, 244, 512 }, { 7, 245, 512 }, { 7, 246, 512 }, { 8, 247, 512 }, 
02267    { 6, 248, 512 }, { 7, 249, 512 }, { 7, 250, 512 }, { 8, 251, 512 }, { 7, 252, 512 }, { 8, 253, 512 }, { 8, 254, 512 }, { 9, 255, 512 }, 
02268    { 2, 256, 512 }, { 3, 257, 512 }, { 3, 258, 512 }, { 4, 259, 512 }, { 3, 260, 512 }, { 4, 261, 512 }, { 4, 262, 512 }, { 5, 263, 512 }, 
02269    { 3, 264, 512 }, { 4, 265, 512 }, { 4, 266, 512 }, { 5, 267, 512 }, { 4, 268, 512 }, { 5, 269, 512 }, { 5, 270, 512 }, { 6, 271, 512 }, 
02270    { 3, 272, 512 }, { 4, 273, 512 }, { 4, 274, 512 }, { 5, 275, 512 }, { 4, 276, 512 }, { 5, 277, 512 }, { 5, 278, 512 }, { 6, 279, 512 }, 
02271    { 4, 280, 512 }, { 5, 281, 512 }, { 5, 282, 512 }, { 6, 283, 512 }, { 5, 284, 512 }, { 6, 285, 512 }, { 6, 286, 512 }, { 7, 287, 512 }, 
02272    { 3, 288, 512 }, { 4, 289, 512 }, { 4, 290, 512 }, { 5, 291, 512 }, { 4, 292, 512 }, { 5, 293, 512 }, { 5, 294, 512 }, { 6, 295, 512 }, 
02273    { 4, 296, 512 }, { 5, 297, 512 }, { 5, 298, 512 }, { 6, 299, 512 }, { 5, 300, 512 }, { 6, 301, 512 }, { 6, 302, 512 }, { 7, 303, 512 }, 
02274    { 4, 304, 512 }, { 5, 305, 512 }, { 5, 306, 512 }, { 6, 307, 512 }, { 5, 308, 512 }, { 6, 309, 512 }, { 6, 310, 512 }, { 7, 311, 512 }, 
02275    { 5, 312, 512 }, { 6, 313, 512 }, { 6, 314, 512 }, { 7, 315, 512 }, { 6, 316, 512 }, { 7, 317, 512 }, { 7, 318, 512 }, { 8, 319, 512 }, 
02276    { 3, 320, 512 }, { 4, 321, 512 }, { 4, 322, 512 }, { 5, 323, 512 }, { 4, 324, 512 }, { 5, 325, 512 }, { 5, 326, 512 }, { 6, 327, 512 }, 
02277    { 4, 328, 512 }, { 5, 329, 512 }, { 5, 330, 512 }, { 6, 331, 512 }, { 5, 332, 512 }, { 6, 333, 512 }, { 6, 334, 512 }, { 7, 335, 512 }, 
02278    { 4, 336, 512 }, { 5, 337, 512 }, { 5, 338, 512 }, { 6, 339, 512 }, { 5, 340, 512 }, { 6, 341, 512 }, { 6, 342, 512 }, { 7, 343, 512 }, 
02279    { 5, 344, 512 }, { 6, 345, 512 }, { 6, 346, 512 }, { 7, 347, 512 }, { 6, 348, 512 }, { 7, 349, 512 }, { 7, 350, 512 }, { 8, 351, 512 }, 
02280    { 4, 352, 512 }, { 5, 353, 512 }, { 5, 354, 512 }, { 6, 355, 512 }, { 5, 356, 512 }, { 6, 357, 512 }, { 6, 358, 512 }, { 7, 359, 512 }, 
02281    { 5, 360, 512 }, { 6, 361, 512 }, { 6, 362, 512 }, { 7, 363, 512 }, { 6, 364, 512 }, { 7, 365, 512 }, { 7, 366, 512 }, { 8, 367, 512 }, 
02282    { 5, 368, 512 }, { 6, 369, 512 }, { 6, 370, 512 }, { 7, 371, 512 }, { 6, 372, 512 }, { 7, 373, 512 }, { 7, 374, 512 }, { 8, 375, 512 }, 
02283    { 6, 376, 512 }, { 7, 377, 512 }, { 7, 378, 512 }, { 8, 379, 512 }, { 7, 380, 512 }, { 8, 381, 512 }, { 8, 382, 512 }, { 9, 383, 512 }, 
02284    { 3, 384, 512 }, { 4, 385, 512 }, { 4, 386, 512 }, { 5, 387, 512 }, { 4, 388, 512 }, { 5, 389, 512 }, { 5, 390, 512 }, { 6, 391, 512 }, 
02285    { 4, 392, 512 }, { 5, 393, 512 }, { 5, 394, 512 }, { 6, 395, 512 }, { 5, 396, 512 }, { 6, 397, 512 }, { 6, 398, 512 }, { 7, 399, 512 }, 
02286    { 4, 400, 512 }, { 5, 401, 512 }, { 5, 402, 512 }, { 6, 403, 512 }, { 5, 404, 512 }, { 6, 405, 512 }, { 6, 406, 512 }, { 7, 407, 512 }, 
02287    { 5, 408, 512 }, { 6, 409, 512 }, { 6, 410, 512 }, { 7, 411, 512 }, { 6, 412, 512 }, { 7, 413, 512 }, { 7, 414, 512 }, { 8, 415, 512 }, 
02288    { 4, 416, 512 }, { 5, 417, 512 }, { 5, 418, 512 }, { 6, 419, 512 }, { 5, 420, 512 }, { 6, 421, 512 }, { 6, 422, 512 }, { 7, 423, 512 }, 
02289    { 5, 424, 512 }, { 6, 425, 512 }, { 6, 426, 512 }, { 7, 427, 512 }, { 6, 428, 512 }, { 7, 429, 512 }, { 7, 430, 512 }, { 8, 431, 512 }, 
02290    { 5, 432, 512 }, { 6, 433, 512 }, { 6, 434, 512 }, { 7, 435, 512 }, { 6, 436, 512 }, { 7, 437, 512 }, { 7, 438, 512 }, { 8, 439, 512 }, 
02291    { 6, 440, 512 }, { 7, 441, 512 }, { 7, 442, 512 }, { 8, 443, 512 }, { 7, 444, 512 }, { 8, 445, 512 }, { 8, 446, 512 }, { 9, 447, 512 }, 
02292    { 4, 448, 512 }, { 5, 449, 512 }, { 5, 450, 512 }, { 6, 451, 512 }, { 5, 452, 512 }, { 6, 453, 512 }, { 6, 454, 512 }, { 7, 455, 512 }, 
02293    { 5, 456, 512 }, { 6, 457, 512 }, { 6, 458, 512 }, { 7, 459, 512 }, { 6, 460, 512 }, { 7, 461, 512 }, { 7, 462, 512 }, { 8, 463, 512 }, 
02294    { 5, 464, 512 }, { 6, 465, 512 }, { 6, 466, 512 }, { 7, 467, 512 }, { 6, 468, 512 }, { 7, 469, 512 }, { 7, 470, 512 }, { 8, 471, 512 }, 
02295    { 6, 472, 512 }, { 7, 473, 512 }, { 7, 474, 512 }, { 8, 475, 512 }, { 7, 476, 512 }, { 8, 477, 512 }, { 8, 478, 512 }, { 9, 479, 512 }, 
02296    { 5, 480, 512 }, { 6, 481, 512 }, { 6, 482, 512 }, { 7, 483, 512 }, { 6, 484, 512 }, { 7, 485, 512 }, { 7, 486, 512 }, { 8, 487, 512 }, 
02297    { 6, 488, 512 }, { 7, 489, 512 }, { 7, 490, 512 }, { 8, 491, 512 }, { 7, 492, 512 }, { 8, 493, 512 }, { 8, 494, 512 }, { 9, 495, 512 }, 
02298    { 6, 496, 512 }, { 7, 497, 512 }, { 7, 498, 512 }, { 8, 499, 512 }, { 7, 500, 512 }, { 8, 501, 512 }, { 8, 502, 512 }, { 9, 503, 512 }, 
02299    { 7, 504, 512 }, { 8, 505, 512 }, { 8, 506, 512 }, { 9, 507, 512 }, { 8, 508, 512 }, { 9, 509, 512 }, { 9, 510, 512 }, { 10, 511, 512 }, 
02300 #if FP_LUT > 10
02301    { 1, 0, 0 }, { 2, 1, 1024 }, { 2, 2, 1024 }, { 3, 3, 1024 }, { 2, 4, 1024 }, { 3, 5, 1024 }, { 3, 6, 1024 }, { 4, 7, 1024 }, 
02302    { 2, 8, 1024 }, { 3, 9, 1024 }, { 3, 10, 1024 }, { 4, 11, 1024 }, { 3, 12, 1024 }, { 4, 13, 1024 }, { 4, 14, 1024 }, { 5, 15, 1024 }, 
02303    { 2, 16, 1024 }, { 3, 17, 1024 }, { 3, 18, 1024 }, { 4, 19, 1024 }, { 3, 20, 1024 }, { 4, 21, 1024 }, { 4, 22, 1024 }, { 5, 23, 1024 }, 
02304    { 3, 24, 1024 }, { 4, 25, 1024 }, { 4, 26, 1024 }, { 5, 27, 1024 }, { 4, 28, 1024 }, { 5, 29, 1024 }, { 5, 30, 1024 }, { 6, 31, 1024 }, 
02305    { 2, 32, 1024 }, { 3, 33, 1024 }, { 3, 34, 1024 }, { 4, 35, 1024 }, { 3, 36, 1024 }, { 4, 37, 1024 }, { 4, 38, 1024 }, { 5, 39, 1024 }, 
02306    { 3, 40, 1024 }, { 4, 41, 1024 }, { 4, 42, 1024 }, { 5, 43, 1024 }, { 4, 44, 1024 }, { 5, 45, 1024 }, { 5, 46, 1024 }, { 6, 47, 1024 }, 
02307    { 3, 48, 1024 }, { 4, 49, 1024 }, { 4, 50, 1024 }, { 5, 51, 1024 }, { 4, 52, 1024 }, { 5, 53, 1024 }, { 5, 54, 1024 }, { 6, 55, 1024 }, 
02308    { 4, 56, 1024 }, { 5, 57, 1024 }, { 5, 58, 1024 }, { 6, 59, 1024 }, { 5, 60, 1024 }, { 6, 61, 1024 }, { 6, 62, 1024 }, { 7, 63, 1024 }, 
02309    { 2, 64, 1024 }, { 3, 65, 1024 }, { 3, 66, 1024 }, { 4, 67, 1024 }, { 3, 68, 1024 }, { 4, 69, 1024 }, { 4, 70, 1024 }, { 5, 71, 1024 }, 
02310    { 3, 72, 1024 }, { 4, 73, 1024 }, { 4, 74, 1024 }, { 5, 75, 1024 }, { 4, 76, 1024 }, { 5, 77, 1024 }, { 5, 78, 1024 }, { 6, 79, 1024 }, 
02311    { 3, 80, 1024 }, { 4, 81, 1024 }, { 4, 82, 1024 }, { 5, 83, 1024 }, { 4, 84, 1024 }, { 5, 85, 1024 }, { 5, 86, 1024 }, { 6, 87, 1024 }, 
02312    { 4, 88, 1024 }, { 5, 89, 1024 }, { 5, 90, 1024 }, { 6, 91, 1024 }, { 5, 92, 1024 }, { 6, 93, 1024 }, { 6, 94, 1024 }, { 7, 95, 1024 }, 
02313    { 3, 96, 1024 }, { 4, 97, 1024 }, { 4, 98, 1024 }, { 5, 99, 1024 }, { 4, 100, 1024 }, { 5, 101, 1024 }, { 5, 102, 1024 }, { 6, 103, 1024 }, 
02314    { 4, 104, 1024 }, { 5, 105, 1024 }, { 5, 106, 1024 }, { 6, 107, 1024 }, { 5, 108, 1024 }, { 6, 109, 1024 }, { 6, 110, 1024 }, { 7, 111, 1024 }, 
02315    { 4, 112, 1024 }, { 5, 113, 1024 }, { 5, 114, 1024 }, { 6, 115, 1024 }, { 5, 116, 1024 }, { 6, 117, 1024 }, { 6, 118, 1024 }, { 7, 119, 1024 }, 
02316    { 5, 120, 1024 }, { 6, 121, 1024 }, { 6, 122, 1024 }, { 7, 123, 1024 }, { 6, 124, 1024 }, { 7, 125, 1024 }, { 7, 126, 1024 }, { 8, 127, 1024 }, 
02317    { 2, 128, 1024 }, { 3, 129, 1024 }, { 3, 130, 1024 }, { 4, 131, 1024 }, { 3, 132, 1024 }, { 4, 133, 1024 }, { 4, 134, 1024 }, { 5, 135, 1024 }, 
02318    { 3, 136, 1024 }, { 4, 137, 1024 }, { 4, 138, 1024 }, { 5, 139, 1024 }, { 4, 140, 1024 }, { 5, 141, 1024 }, { 5, 142, 1024 }, { 6, 143, 1024 }, 
02319    { 3, 144, 1024 }, { 4, 145, 1024 }, { 4, 146, 1024 }, { 5, 147, 1024 }, { 4, 148, 1024 }, { 5, 149, 1024 }, { 5, 150, 1024 }, { 6, 151, 1024 }, 
02320    { 4, 152, 1024 }, { 5, 153, 1024 }, { 5, 154, 1024 }, { 6, 155, 1024 }, { 5, 156, 1024 }, { 6, 157, 1024 }, { 6, 158, 1024 }, { 7, 159, 1024 }, 
02321    { 3, 160, 1024 }, { 4, 161, 1024 }, { 4, 162, 1024 }, { 5, 163, 1024 }, { 4, 164, 1024 }, { 5, 165, 1024 }, { 5, 166, 1024 }, { 6, 167, 1024 }, 
02322    { 4, 168, 1024 }, { 5, 169, 1024 }, { 5, 170, 1024 }, { 6, 171, 1024 }, { 5, 172, 1024 }, { 6, 173, 1024 }, { 6, 174, 1024 }, { 7, 175, 1024 }, 
02323    { 4, 176, 1024 }, { 5, 177, 1024 }, { 5, 178, 1024 }, { 6, 179, 1024 }, { 5, 180, 1024 }, { 6, 181, 1024 }, { 6, 182, 1024 }, { 7, 183, 1024 }, 
02324    { 5, 184, 1024 }, { 6, 185, 1024 }, { 6, 186, 1024 }, { 7, 187, 1024 }, { 6, 188, 1024 }, { 7, 189, 1024 }, { 7, 190, 1024 }, { 8, 191, 1024 }, 
02325    { 3, 192, 1024 }, { 4, 193, 1024 }, { 4, 194, 1024 }, { 5, 195, 1024 }, { 4, 196, 1024 }, { 5, 197, 1024 }, { 5, 198, 1024 }, { 6, 199, 1024 }, 
02326    { 4, 200, 1024 }, { 5, 201, 1024 }, { 5, 202, 1024 }, { 6, 203, 1024 }, { 5, 204, 1024 }, { 6, 205, 1024 }, { 6, 206, 1024 }, { 7, 207, 1024 }, 
02327    { 4, 208, 1024 }, { 5, 209, 1024 }, { 5, 210, 1024 }, { 6, 211, 1024 }, { 5, 212, 1024 }, { 6, 213, 1024 }, { 6, 214, 1024 }, { 7, 215, 1024 }, 
02328    { 5, 216, 1024 }, { 6, 217, 1024 }, { 6, 218, 1024 }, { 7, 219, 1024 }, { 6, 220, 1024 }, { 7, 221, 1024 }, { 7, 222, 1024 }, { 8, 223, 1024 }, 
02329    { 4, 224, 1024 }, { 5, 225, 1024 }, { 5, 226, 1024 }, { 6, 227, 1024 }, { 5, 228, 1024 }, { 6, 229, 1024 }, { 6, 230, 1024 }, { 7, 231, 1024 }, 
02330    { 5, 232, 1024 }, { 6, 233, 1024 }, { 6, 234, 1024 }, { 7, 235, 1024 }, { 6, 236, 1024 }, { 7, 237, 1024 }, { 7, 238, 1024 }, { 8, 239, 1024 }, 
02331    { 5, 240, 1024 }, { 6, 241, 1024 }, { 6, 242, 1024 }, { 7, 243, 1024 }, { 6, 244, 1024 }, { 7, 245, 1024 }, { 7, 246, 1024 }, { 8, 247, 1024 }, 
02332    { 6, 248, 1024 }, { 7, 249, 1024 }, { 7, 250, 1024 }, { 8, 251, 1024 }, { 7, 252, 1024 }, { 8, 253, 1024 }, { 8, 254, 1024 }, { 9, 255, 1024 }, 
02333    { 2, 256, 1024 }, { 3, 257, 1024 }, { 3, 258, 1024 }, { 4, 259, 1024 }, { 3, 260, 1024 }, { 4, 261, 1024 }, { 4, 262, 1024 }, { 5, 263, 1024 }, 
02334    { 3, 264, 1024 }, { 4, 265, 1024 }, { 4, 266, 1024 }, { 5, 267, 1024 }, { 4, 268, 1024 }, { 5, 269, 1024 }, { 5, 270, 1024 }, { 6, 271, 1024 }, 
02335    { 3, 272, 1024 }, { 4, 273, 1024 }, { 4, 274, 1024 }, { 5, 275, 1024 }, { 4, 276, 1024 }, { 5, 277, 1024 }, { 5, 278, 1024 }, { 6, 279, 1024 }, 
02336    { 4, 280, 1024 }, { 5, 281, 1024 }, { 5, 282, 1024 }, { 6, 283, 1024 }, { 5, 284, 1024 }, { 6, 285, 1024 }, { 6, 286, 1024 }, { 7, 287, 1024 }, 
02337    { 3, 288, 1024 }, { 4, 289, 1024 }, { 4, 290, 1024 }, { 5, 291, 1024 }, { 4, 292, 1024 }, { 5, 293, 1024 }, { 5, 294, 1024 }, { 6, 295, 1024 }, 
02338    { 4, 296, 1024 }, { 5, 297, 1024 }, { 5, 298, 1024 }, { 6, 299, 1024 }, { 5, 300, 1024 }, { 6, 301, 1024 }, { 6, 302, 1024 }, { 7, 303, 1024 }, 
02339    { 4, 304, 1024 }, { 5, 305, 1024 }, { 5, 306, 1024 }, { 6, 307, 1024 }, { 5, 308, 1024 }, { 6, 309, 1024 }, { 6, 310, 1024 }, { 7, 311, 1024 }, 
02340    { 5, 312, 1024 }, { 6, 313, 1024 }, { 6, 314, 1024 }, { 7, 315, 1024 }, { 6, 316, 1024 }, { 7, 317, 1024 }, { 7, 318, 1024 }, { 8, 319, 1024 }, 
02341    { 3, 320, 1024 }, { 4, 321, 1024 }, { 4, 322, 1024 }, { 5, 323, 1024 }, { 4, 324, 1024 }, { 5, 325, 1024 }, { 5, 326, 1024 }, { 6, 327, 1024 }, 
02342    { 4, 328, 1024 }, { 5, 329, 1024 }, { 5, 330, 1024 }, { 6, 331, 1024 }, { 5, 332, 1024 }, { 6, 333, 1024 }, { 6, 334, 1024 }, { 7, 335, 1024 }, 
02343    { 4, 336, 1024 }, { 5, 337, 1024 }, { 5, 338, 1024 }, { 6, 339, 1024 }, { 5, 340, 1024 }, { 6, 341, 1024 }, { 6, 342, 1024 }, { 7, 343, 1024 }, 
02344    { 5, 344, 1024 }, { 6, 345, 1024 }, { 6, 346, 1024 }, { 7, 347, 1024 }, { 6, 348, 1024 }, { 7, 349, 1024 }, { 7, 350, 1024 }, { 8, 351, 1024 }, 
02345    { 4, 352, 1024 }, { 5, 353, 1024 }, { 5, 354, 1024 }, { 6, 355, 1024 }, { 5, 356, 1024 }, { 6, 357, 1024 }, { 6, 358, 1024 }, { 7, 359, 1024 }, 
02346    { 5, 360, 1024 }, { 6, 361, 1024 }, { 6, 362, 1024 }, { 7, 363, 1024 }, { 6, 364, 1024 }, { 7, 365, 1024 }, { 7, 366, 1024 }, { 8, 367, 1024 }, 
02347    { 5, 368, 1024 }, { 6, 369, 1024 }, { 6, 370, 1024 }, { 7, 371, 1024 }, { 6, 372, 1024 }, { 7, 373, 1024 }, { 7, 374, 1024 }, { 8, 375, 1024 }, 
02348    { 6, 376, 1024 }, { 7, 377, 1024 }, { 7, 378, 1024 }, { 8, 379, 1024 }, { 7, 380, 1024 }, { 8, 381, 1024 }, { 8, 382, 1024 }, { 9, 383, 1024 }, 
02349    { 3, 384, 1024 }, { 4, 385, 1024 }, { 4, 386, 1024 }, { 5, 387, 1024 }, { 4, 388, 1024 }, { 5, 389, 1024 }, { 5, 390, 1024 }, { 6, 391, 1024 }, 
02350    { 4, 392, 1024 }, { 5, 393, 1024 }, { 5, 394, 1024 }, { 6, 395, 1024 }, { 5, 396, 1024 }, { 6, 397, 1024 }, { 6, 398, 1024 }, { 7, 399, 1024 }, 
02351    { 4, 400, 1024 }, { 5, 401, 1024 }, { 5, 402, 1024 }, { 6, 403, 1024 }, { 5, 404, 1024 }, { 6, 405, 1024 }, { 6, 406, 1024 }, { 7, 407, 1024 }, 
02352    { 5, 408, 1024 }, { 6, 409, 1024 }, { 6, 410, 1024 }, { 7, 411, 1024 }, { 6, 412, 1024 }, { 7, 413, 1024 }, { 7, 414, 1024 }, { 8, 415, 1024 }, 
02353    { 4, 416, 1024 }, { 5, 417, 1024 }, { 5, 418, 1024 }, { 6, 419, 1024 }, { 5, 420, 1024 }, { 6, 421, 1024 }, { 6, 422, 1024 }, { 7, 423, 1024 }, 
02354    { 5, 424, 1024 }, { 6, 425, 1024 }, { 6, 426, 1024 }, { 7, 427, 1024 }, { 6, 428, 1024 }, { 7, 429, 1024 }, { 7, 430, 1024 }, { 8, 431, 1024 }, 
02355    { 5, 432, 1024 }, { 6, 433, 1024 }, { 6, 434, 1024 }, { 7, 435, 1024 }, { 6, 436, 1024 }, { 7, 437, 1024 }, { 7, 438, 1024 }, { 8, 439, 1024 }, 
02356    { 6, 440, 1024 }, { 7, 441, 1024 }, { 7, 442, 1024 }, { 8, 443, 1024 }, { 7, 444, 1024 }, { 8, 445, 1024 }, { 8, 446, 1024 }, { 9, 447, 1024 }, 
02357    { 4, 448, 1024 }, { 5, 449, 1024 }, { 5, 450, 1024 }, { 6, 451, 1024 }, { 5, 452, 1024 }, { 6, 453, 1024 }, { 6, 454, 1024 }, { 7, 455, 1024 }, 
02358    { 5, 456, 1024 }, { 6, 457, 1024 }, { 6, 458, 1024 }, { 7, 459, 1024 }, { 6, 460, 1024 }, { 7, 461, 1024 }, { 7, 462, 1024 }, { 8, 463, 1024 }, 
02359    { 5, 464, 1024 }, { 6, 465, 1024 }, { 6, 466, 1024 }, { 7, 467, 1024 }, { 6, 468, 1024 }, { 7, 469, 1024 }, { 7, 470, 1024 }, { 8, 471, 1024 }, 
02360    { 6, 472, 1024 }, { 7, 473, 1024 }, { 7, 474, 1024 }, { 8, 475, 1024 }, { 7, 476, 1024 }, { 8, 477, 1024 }, { 8, 478, 1024 }, { 9, 479, 1024 }, 
02361    { 5, 480, 1024 }, { 6, 481, 1024 }, { 6, 482, 1024 }, { 7, 483, 1024 }, { 6, 484, 1024 }, { 7, 485, 1024 }, { 7, 486, 1024 }, { 8, 487, 1024 }, 
02362    { 6, 488, 1024 }, { 7, 489, 1024 }, { 7, 490, 1024 }, { 8, 491, 1024 }, { 7, 492, 1024 }, { 8, 493, 1024 }, { 8, 494, 1024 }, { 9, 495, 1024 }, 
02363    { 6, 496, 1024 }, { 7, 497, 1024 }, { 7, 498, 1024 }, { 8, 499, 1024 }, { 7, 500, 1024 }, { 8, 501, 1024 }, { 8, 502, 1024 }, { 9, 503, 1024 }, 
02364    { 7, 504, 1024 }, { 8, 505, 1024 }, { 8, 506, 1024 }, { 9, 507, 1024 }, { 8, 508, 1024 }, { 9, 509, 1024 }, { 9, 510, 1024 }, { 10, 511, 1024 }, 
02365    { 2, 512, 1024 }, { 3, 513, 1024 }, { 3, 514, 1024 }, { 4, 515, 1024 }, { 3, 516, 1024 }, { 4, 517, 1024 }, { 4, 518, 1024 }, { 5, 519, 1024 }, 
02366    { 3, 520, 1024 }, { 4, 521, 1024 }, { 4, 522, 1024 }, { 5, 523, 1024 }, { 4, 524, 1024 }, { 5, 525, 1024 }, { 5, 526, 1024 }, { 6, 527, 1024 }, 
02367    { 3, 528, 1024 }, { 4, 529, 1024 }, { 4, 530, 1024 }, { 5, 531, 1024 }, { 4, 532, 1024 }, { 5, 533, 1024 }, { 5, 534, 1024 }, { 6, 535, 1024 }, 
02368    { 4, 536, 1024 }, { 5, 537, 1024 }, { 5, 538, 1024 }, { 6, 539, 1024 }, { 5, 540, 1024 }, { 6, 541, 1024 }, { 6, 542, 1024 }, { 7, 543, 1024 }, 
02369    { 3, 544, 1024 }, { 4, 545, 1024 }, { 4, 546, 1024 }, { 5, 547, 1024 }, { 4, 548, 1024 }, { 5, 549, 1024 }, { 5, 550, 1024 }, { 6, 551, 1024 }, 
02370    { 4, 552, 1024 }, { 5, 553, 1024 }, { 5, 554, 1024 }, { 6, 555, 1024 }, { 5, 556, 1024 }, { 6, 557, 1024 }, { 6, 558, 1024 }, { 7, 559, 1024 }, 
02371    { 4, 560, 1024 }, { 5, 561, 1024 }, { 5, 562, 1024 }, { 6, 563, 1024 }, { 5, 564, 1024 }, { 6, 565, 1024 }, { 6, 566, 1024 }, { 7, 567, 1024 }, 
02372    { 5, 568, 1024 }, { 6, 569, 1024 }, { 6, 570, 1024 }, { 7, 571, 1024 }, { 6, 572, 1024 }, { 7, 573, 1024 }, { 7, 574, 1024 }, { 8, 575, 1024 }, 
02373    { 3, 576, 1024 }, { 4, 577, 1024 }, { 4, 578, 1024 }, { 5, 579, 1024 }, { 4, 580, 1024 }, { 5, 581, 1024 }, { 5, 582, 1024 }, { 6, 583, 1024 }, 
02374    { 4, 584, 1024 }, { 5, 585, 1024 }, { 5, 586, 1024 }, { 6, 587, 1024 }, { 5, 588, 1024 }, { 6, 589, 1024 }, { 6, 590, 1024 }, { 7, 591, 1024 }, 
02375    { 4, 592, 1024 }, { 5, 593, 1024 }, { 5, 594, 1024 }, { 6, 595, 1024 }, { 5, 596, 1024 }, { 6, 597, 1024 }, { 6, 598, 1024 }, { 7, 599, 1024 }, 
02376    { 5, 600, 1024 }, { 6, 601, 1024 }, { 6, 602, 1024 }, { 7, 603, 1024 }, { 6, 604, 1024 }, { 7, 605, 1024 }, { 7, 606, 1024 }, { 8, 607, 1024 }, 
02377    { 4, 608, 1024 }, { 5, 609, 1024 }, { 5, 610, 1024 }, { 6, 611, 1024 }, { 5, 612, 1024 }, { 6, 613, 1024 }, { 6, 614, 1024 }, { 7, 615, 1024 }, 
02378    { 5, 616, 1024 }, { 6, 617, 1024 }, { 6, 618, 1024 }, { 7, 619, 1024 }, { 6, 620, 1024 }, { 7, 621, 1024 }, { 7, 622, 1024 }, { 8, 623, 1024 }, 
02379    { 5, 624, 1024 }, { 6, 625, 1024 }, { 6, 626, 1024 }, { 7, 627, 1024 }, { 6, 628, 1024 }, { 7, 629, 1024 }, { 7, 630, 1024 }, { 8, 631, 1024 }, 
02380    { 6, 632, 1024 }, { 7, 633, 1024 }, { 7, 634, 1024 }, { 8, 635, 1024 }, { 7, 636, 1024 }, { 8, 637, 1024 }, { 8, 638, 1024 }, { 9, 639, 1024 }, 
02381    { 3, 640, 1024 }, { 4, 641, 1024 }, { 4, 642, 1024 }, { 5, 643, 1024 }, { 4, 644, 1024 }, { 5, 645, 1024 }, { 5, 646, 1024 }, { 6, 647, 1024 }, 
02382    { 4, 648, 1024 }, { 5, 649, 1024 }, { 5, 650, 1024 }, { 6, 651, 1024 }, { 5, 652, 1024 }, { 6, 653, 1024 }, { 6, 654, 1024 }, { 7, 655, 1024 }, 
02383    { 4, 656, 1024 }, { 5, 657, 1024 }, { 5, 658, 1024 }, { 6, 659, 1024 }, { 5, 660, 1024 }, { 6, 661, 1024 }, { 6, 662, 1024 }, { 7, 663, 1024 }, 
02384    { 5, 664, 1024 }, { 6, 665, 1024 }, { 6, 666, 1024 }, { 7, 667, 1024 }, { 6, 668, 1024 }, { 7, 669, 1024 }, { 7, 670, 1024 }, { 8, 671, 1024 }, 
02385    { 4, 672, 1024 }, { 5, 673, 1024 }, { 5, 674, 1024 }, { 6, 675, 1024 }, { 5, 676, 1024 }, { 6, 677, 1024 }, { 6, 678, 1024 }, { 7, 679, 1024 }, 
02386    { 5, 680, 1024 }, { 6, 681, 1024 }, { 6, 682, 1024 }, { 7, 683, 1024 }, { 6, 684, 1024 }, { 7, 685, 1024 }, { 7, 686, 1024 }, { 8, 687, 1024 }, 
02387    { 5, 688, 1024 }, { 6, 689, 1024 }, { 6, 690, 1024 }, { 7, 691, 1024 }, { 6, 692, 1024 }, { 7, 693, 1024 }, { 7, 694, 1024 }, { 8, 695, 1024 }, 
02388    { 6, 696, 1024 }, { 7, 697, 1024 }, { 7, 698, 1024 }, { 8, 699, 1024 }, { 7, 700, 1024 }, { 8, 701, 1024 }, { 8, 702, 1024 }, { 9, 703, 1024 }, 
02389    { 4, 704, 1024 }, { 5, 705, 1024 }, { 5, 706, 1024 }, { 6, 707, 1024 }, { 5, 708, 1024 }, { 6, 709, 1024 }, { 6, 710, 1024 }, { 7, 711, 1024 }, 
02390    { 5, 712, 1024 }, { 6, 713, 1024 }, { 6, 714, 1024 }, { 7, 715, 1024 }, { 6, 716, 1024 }, { 7, 717, 1024 }, { 7, 718, 1024 }, { 8, 719, 1024 }, 
02391    { 5, 720, 1024 }, { 6, 721, 1024 }, { 6, 722, 1024 }, { 7, 723, 1024 }, { 6, 724, 1024 }, { 7, 725, 1024 }, { 7, 726, 1024 }, { 8, 727, 1024 }, 
02392    { 6, 728, 1024 }, { 7, 729, 1024 }, { 7, 730, 1024 }, { 8, 731, 1024 }, { 7, 732, 1024 }, { 8, 733, 1024 }, { 8, 734, 1024 }, { 9, 735, 1024 }, 
02393    { 5, 736, 1024 }, { 6, 737, 1024 }, { 6, 738, 1024 }, { 7, 739, 1024 }, { 6, 740, 1024 }, { 7, 741, 1024 }, { 7, 742, 1024 }, { 8, 743, 1024 }, 
02394    { 6, 744, 1024 }, { 7, 745, 1024 }, { 7, 746, 1024 }, { 8, 747, 1024 }, { 7, 748, 1024 }, { 8, 749, 1024 }, { 8, 750, 1024 }, { 9, 751, 1024 }, 
02395    { 6, 752, 1024 }, { 7, 753, 1024 }, { 7, 754, 1024 }, { 8, 755, 1024 }, { 7, 756, 1024 }, { 8, 757, 1024 }, { 8, 758, 1024 }, { 9, 759, 1024 }, 
02396    { 7, 760, 1024 }, { 8, 761, 1024 }, { 8, 762, 1024 }, { 9, 763, 1024 }, { 8, 764, 1024 }, { 9, 765, 1024 }, { 9, 766, 1024 }, { 10, 767, 1024 }, 
02397    { 3, 768, 1024 }, { 4, 769, 1024 }, { 4, 770, 1024 }, { 5, 771, 1024 }, { 4, 772, 1024 }, { 5, 773, 1024 }, { 5, 774, 1024 }, { 6, 775, 1024 }, 
02398    { 4, 776, 1024 }, { 5, 777, 1024 }, { 5, 778, 1024 }, { 6, 779, 1024 }, { 5, 780, 1024 }, { 6, 781, 1024 }, { 6, 782, 1024 }, { 7, 783, 1024 }, 
02399    { 4, 784, 1024 }, { 5, 785, 1024 }, { 5, 786, 1024 }, { 6, 787, 1024 }, { 5, 788, 1024 }, { 6, 789, 1024 }, { 6, 790, 1024 }, { 7, 791, 1024 }, 
02400    { 5, 792, 1024 }, { 6, 793, 1024 }, { 6, 794, 1024 }, { 7, 795, 1024 }, { 6, 796, 1024 }, { 7, 797, 1024 }, { 7, 798, 1024 }, { 8, 799, 1024 }, 
02401    { 4, 800, 1024 }, { 5, 801, 1024 }, { 5, 802, 1024 }, { 6, 803, 1024 }, { 5, 804, 1024 }, { 6, 805, 1024 }, { 6, 806, 1024 }, { 7, 807, 1024 }, 
02402    { 5, 808, 1024 }, { 6, 809, 1024 }, { 6, 810, 1024 }, { 7, 811, 1024 }, { 6, 812, 1024 }, { 7, 813, 1024 }, { 7, 814, 1024 }, { 8, 815, 1024 }, 
02403    { 5, 816, 1024 }, { 6, 817, 1024 }, { 6, 818, 1024 }, { 7, 819, 1024 }, { 6, 820, 1024 }, { 7, 821, 1024 }, { 7, 822, 1024 }, { 8, 823, 1024 }, 
02404    { 6, 824, 1024 }, { 7, 825, 1024 }, { 7, 826, 1024 }, { 8, 827, 1024 }, { 7, 828, 1024 }, { 8, 829, 1024 }, { 8, 830, 1024 }, { 9, 831, 1024 }, 
02405    { 4, 832, 1024 }, { 5, 833, 1024 }, { 5, 834, 1024 }, { 6, 835, 1024 }, { 5, 836, 1024 }, { 6, 837, 1024 }, { 6, 838, 1024 }, { 7, 839, 1024 }, 
02406    { 5, 840, 1024 }, { 6, 841, 1024 }, { 6, 842, 1024 }, { 7, 843, 1024 }, { 6, 844, 1024 }, { 7, 845, 1024 }, { 7, 846, 1024 }, { 8, 847, 1024 }, 
02407    { 5, 848, 1024 }, { 6, 849, 1024 }, { 6, 850, 1024 }, { 7, 851, 1024 }, { 6, 852, 1024 }, { 7, 853, 1024 }, { 7, 854, 1024 }, { 8, 855, 1024 }, 
02408    { 6, 856, 1024 }, { 7, 857, 1024 }, { 7, 858, 1024 }, { 8, 859, 1024 }, { 7, 860, 1024 }, { 8, 861, 1024 }, { 8, 862, 1024 }, { 9, 863, 1024 }, 
02409    { 5, 864, 1024 }, { 6, 865, 1024 }, { 6, 866, 1024 }, { 7, 867, 1024 }, { 6, 868, 1024 }, { 7, 869, 1024 }, { 7, 870, 1024 }, { 8, 871, 1024 }, 
02410    { 6, 872, 1024 }, { 7, 873, 1024 }, { 7, 874, 1024 }, { 8, 875, 1024 }, { 7, 876, 1024 }, { 8, 877, 1024 }, { 8, 878, 1024 }, { 9, 879, 1024 }, 
02411    { 6, 880, 1024 }, { 7, 881, 1024 }, { 7, 882, 1024 }, { 8, 883, 1024 }, { 7, 884, 1024 }, { 8, 885, 1024 }, { 8, 886, 1024 }, { 9, 887, 1024 }, 
02412    { 7, 888, 1024 }, { 8, 889, 1024 }, { 8, 890, 1024 }, { 9, 891, 1024 }, { 8, 892, 1024 }, { 9, 893, 1024 }, { 9, 894, 1024 }, { 10, 895, 1024 }, 
02413    { 4, 896, 1024 }, { 5, 897, 1024 }, { 5, 898, 1024 }, { 6, 899, 1024 }, { 5, 900, 1024 }, { 6, 901, 1024 }, { 6, 902, 1024 }, { 7, 903, 1024 }, 
02414    { 5, 904, 1024 }, { 6, 905, 1024 }, { 6, 906, 1024 }, { 7, 907, 1024 }, { 6, 908, 1024 }, { 7, 909, 1024 }, { 7, 910, 1024 }, { 8, 911, 1024 }, 
02415    { 5, 912, 1024 }, { 6, 913, 1024 }, { 6, 914, 1024 }, { 7, 915, 1024 }, { 6, 916, 1024 }, { 7, 917, 1024 }, { 7, 918, 1024 }, { 8, 919, 1024 }, 
02416    { 6, 920, 1024 }, { 7, 921, 1024 }, { 7, 922, 1024 }, { 8, 923, 1024 }, { 7, 924, 1024 }, { 8, 925, 1024 }, { 8, 926, 1024 }, { 9, 927, 1024 }, 
02417    { 5, 928, 1024 }, { 6, 929, 1024 }, { 6, 930, 1024 }, { 7, 931, 1024 }, { 6, 932, 1024 }, { 7, 933, 1024 }, { 7, 934, 1024 }, { 8, 935, 1024 }, 
02418    { 6, 936, 1024 }, { 7, 937, 1024 }, { 7, 938, 1024 }, { 8, 939, 1024 }, { 7, 940, 1024 }, { 8, 941, 1024 }, { 8, 942, 1024 }, { 9, 943, 1024 }, 
02419    { 6, 944, 1024 }, { 7, 945, 1024 }, { 7, 946, 1024 }, { 8, 947, 1024 }, { 7, 948, 1024 }, { 8, 949, 1024 }, { 8, 950, 1024 }, { 9, 951, 1024 }, 
02420    { 7, 952, 1024 }, { 8, 953, 1024 }, { 8, 954, 1024 }, { 9, 955, 1024 }, { 8, 956, 1024 }, { 9, 957, 1024 }, { 9, 958, 1024 }, { 10, 959, 1024 }, 
02421    { 5, 960, 1024 }, { 6, 961, 1024 }, { 6, 962, 1024 }, { 7, 963, 1024 }, { 6, 964, 1024 }, { 7, 965, 1024 }, { 7, 966, 1024 }, { 8, 967, 1024 }, 
02422    { 6, 968, 1024 }, { 7, 969, 1024 }, { 7, 970, 1024 }, { 8, 971, 1024 }, { 7, 972, 1024 }, { 8, 973, 1024 }, { 8, 974, 1024 }, { 9, 975, 1024 }, 
02423    { 6, 976, 1024 }, { 7, 977, 1024 }, { 7, 978, 1024 }, { 8, 979, 1024 }, { 7, 980, 1024 }, { 8, 981, 1024 }, { 8, 982, 1024 }, { 9, 983, 1024 }, 
02424    { 7, 984, 1024 }, { 8, 985, 1024 }, { 8, 986, 1024 }, { 9, 987, 1024 }, { 8, 988, 1024 }, { 9, 989, 1024 }, { 9, 990, 1024 }, { 10, 991, 1024 }, 
02425    { 6, 992, 1024 }, { 7, 993, 1024 }, { 7, 994, 1024 }, { 8, 995, 1024 }, { 7, 996, 1024 }, { 8, 997, 1024 }, { 8, 998, 1024 }, { 9, 999, 1024 }, 
02426    { 7, 1000, 1024 }, { 8, 1001, 1024 }, { 8, 1002, 1024 }, { 9, 1003, 1024 }, { 8, 1004, 1024 }, { 9, 1005, 1024 }, { 9, 1006, 1024 }, { 10, 1007, 1024 }, 
02427    { 7, 1008, 1024 }, { 8, 1009, 1024 }, { 8, 1010, 1024 }, { 9, 1011, 1024 }, { 8, 1012, 1024 }, { 9, 1013, 1024 }, { 9, 1014, 1024 }, { 10, 1015, 1024 }, 
02428    { 8, 1016, 1024 }, { 9, 1017, 1024 }, { 9, 1018, 1024 }, { 10, 1019, 1024 }, { 9, 1020, 1024 }, { 10, 1021, 1024 }, { 10, 1022, 1024 }, { 11, 1023, 1024 }, 
02429 #if FP_LUT > 11
02430    { 1, 0, 0 }, { 2, 1, 2048 }, { 2, 2, 2048 }, { 3, 3, 2048 }, { 2, 4, 2048 }, { 3, 5, 2048 }, { 3, 6, 2048 }, { 4, 7, 2048 }, 
02431    { 2, 8, 2048 }, { 3, 9, 2048 }, { 3, 10, 2048 }, { 4, 11, 2048 }, { 3, 12, 2048 }, { 4, 13, 2048 }, { 4, 14, 2048 }, { 5, 15, 2048 }, 
02432    { 2, 16, 2048 }, { 3, 17, 2048 }, { 3, 18, 2048 }, { 4, 19, 2048 }, { 3, 20, 2048 }, { 4, 21, 2048 }, { 4, 22, 2048 }, { 5, 23, 2048 }, 
02433    { 3, 24, 2048 }, { 4, 25, 2048 }, { 4, 26, 2048 }, { 5, 27, 2048 }, { 4, 28, 2048 }, { 5, 29, 2048 }, { 5, 30, 2048 }, { 6, 31, 2048 }, 
02434    { 2, 32, 2048 }, { 3, 33, 2048 }, { 3, 34, 2048 }, { 4, 35, 2048 }, { 3, 36, 2048 }, { 4, 37, 2048 }, { 4, 38, 2048 }, { 5, 39, 2048 }, 
02435    { 3, 40, 2048 }, { 4, 41, 2048 }, { 4, 42, 2048 }, { 5, 43, 2048 }, { 4, 44, 2048 }, { 5, 45, 2048 }, { 5, 46, 2048 }, { 6, 47, 2048 }, 
02436    { 3, 48, 2048 }, { 4, 49, 2048 }, { 4, 50, 2048 }, { 5, 51, 2048 }, { 4, 52, 2048 }, { 5, 53, 2048 }, { 5, 54, 2048 }, { 6, 55, 2048 }, 
02437    { 4, 56, 2048 }, { 5, 57, 2048 }, { 5, 58, 2048 }, { 6, 59, 2048 }, { 5, 60, 2048 }, { 6, 61, 2048 }, { 6, 62, 2048 }, { 7, 63, 2048 }, 
02438    { 2, 64, 2048 }, { 3, 65, 2048 }, { 3, 66, 2048 }, { 4, 67, 2048 }, { 3, 68, 2048 }, { 4, 69, 2048 }, { 4, 70, 2048 }, { 5, 71, 2048 }, 
02439    { 3, 72, 2048 }, { 4, 73, 2048 }, { 4, 74, 2048 }, { 5, 75, 2048 }, { 4, 76, 2048 }, { 5, 77, 2048 }, { 5, 78, 2048 }, { 6, 79, 2048 }, 
02440    { 3, 80, 2048 }, { 4, 81, 2048 }, { 4, 82, 2048 }, { 5, 83, 2048 }, { 4, 84, 2048 }, { 5, 85, 2048 }, { 5, 86, 2048 }, { 6, 87, 2048 }, 
02441    { 4, 88, 2048 }, { 5, 89, 2048 }, { 5, 90, 2048 }, { 6, 91, 2048 }, { 5, 92, 2048 }, { 6, 93, 2048 }, { 6, 94, 2048 }, { 7, 95, 2048 }, 
02442    { 3, 96, 2048 }, { 4, 97, 2048 }, { 4, 98, 2048 }, { 5, 99, 2048 }, { 4, 100, 2048 }, { 5, 101, 2048 }, { 5, 102, 2048 }, { 6, 103, 2048 }, 
02443    { 4, 104, 2048 }, { 5, 105, 2048 }, { 5, 106, 2048 }, { 6, 107, 2048 }, { 5, 108, 2048 }, { 6, 109, 2048 }, { 6, 110, 2048 }, { 7, 111, 2048 }, 
02444    { 4, 112, 2048 }, { 5, 113, 2048 }, { 5, 114, 2048 }, { 6, 115, 2048 }, { 5, 116, 2048 }, { 6, 117, 2048 }, { 6, 118, 2048 }, { 7, 119, 2048 }, 
02445    { 5, 120, 2048 }, { 6, 121, 2048 }, { 6, 122, 2048 }, { 7, 123, 2048 }, { 6, 124, 2048 }, { 7, 125, 2048 }, { 7, 126, 2048 }, { 8, 127, 2048 }, 
02446    { 2, 128, 2048 }, { 3, 129, 2048 }, { 3, 130, 2048 }, { 4, 131, 2048 }, { 3, 132, 2048 }, { 4, 133, 2048 }, { 4, 134, 2048 }, { 5, 135, 2048 }, 
02447    { 3, 136, 2048 }, { 4, 137, 2048 }, { 4, 138, 2048 }, { 5, 139, 2048 }, { 4, 140, 2048 }, { 5, 141, 2048 }, { 5, 142, 2048 }, { 6, 143, 2048 }, 
02448    { 3, 144, 2048 }, { 4, 145, 2048 }, { 4, 146, 2048 }, { 5, 147, 2048 }, { 4, 148, 2048 }, { 5, 149, 2048 }, { 5, 150, 2048 }, { 6, 151, 2048 }, 
02449    { 4, 152, 2048 }, { 5, 153, 2048 }, { 5, 154, 2048 }, { 6, 155, 2048 }, { 5, 156, 2048 }, { 6, 157, 2048 }, { 6, 158, 2048 }, { 7, 159, 2048 }, 
02450    { 3, 160, 2048 }, { 4, 161, 2048 }, { 4, 162, 2048 }, { 5, 163, 2048 }, { 4, 164, 2048 }, { 5, 165, 2048 }, { 5, 166, 2048 }, { 6, 167, 2048 }, 
02451    { 4, 168, 2048 }, { 5, 169, 2048 }, { 5, 170, 2048 }, { 6, 171, 2048 }, { 5, 172, 2048 }, { 6, 173, 2048 }, { 6, 174, 2048 }, { 7, 175, 2048 }, 
02452    { 4, 176, 2048 }, { 5, 177, 2048 }, { 5, 178, 2048 }, { 6, 179, 2048 }, { 5, 180, 2048 }, { 6, 181, 2048 }, { 6, 182, 2048 }, { 7, 183, 2048 }, 
02453    { 5, 184, 2048 }, { 6, 185, 2048 }, { 6, 186, 2048 }, { 7, 187, 2048 }, { 6, 188, 2048 }, { 7, 189, 2048 }, { 7, 190, 2048 }, { 8, 191, 2048 }, 
02454    { 3, 192, 2048 }, { 4, 193, 2048 }, { 4, 194, 2048 }, { 5, 195, 2048 }, { 4, 196, 2048 }, { 5, 197, 2048 }, { 5, 198, 2048 }, { 6, 199, 2048 }, 
02455    { 4, 200, 2048 }, { 5, 201, 2048 }, { 5, 202, 2048 }, { 6, 203, 2048 }, { 5, 204, 2048 }, { 6, 205, 2048 }, { 6, 206, 2048 }, { 7, 207, 2048 }, 
02456    { 4, 208, 2048 }, { 5, 209, 2048 }, { 5, 210, 2048 }, { 6, 211, 2048 }, { 5, 212, 2048 }, { 6, 213, 2048 }, { 6, 214, 2048 }, { 7, 215, 2048 }, 
02457    { 5, 216, 2048 }, { 6, 217, 2048 }, { 6, 218, 2048 }, { 7, 219, 2048 }, { 6, 220, 2048 }, { 7, 221, 2048 }, { 7, 222, 2048 }, { 8, 223, 2048 }, 
02458    { 4, 224, 2048 }, { 5, 225, 2048 }, { 5, 226, 2048 }, { 6, 227, 2048 }, { 5, 228, 2048 }, { 6, 229, 2048 }, { 6, 230, 2048 }, { 7, 231, 2048 }, 
02459    { 5, 232, 2048 }, { 6, 233, 2048 }, { 6, 234, 2048 }, { 7, 235, 2048 }, { 6, 236, 2048 }, { 7, 237, 2048 }, { 7, 238, 2048 }, { 8, 239, 2048 }, 
02460    { 5, 240, 2048 }, { 6, 241, 2048 }, { 6, 242, 2048 }, { 7, 243, 2048 }, { 6, 244, 2048 }, { 7, 245, 2048 }, { 7, 246, 2048 }, { 8, 247, 2048 }, 
02461    { 6, 248, 2048 }, { 7, 249, 2048 }, { 7, 250, 2048 }, { 8, 251, 2048 }, { 7, 252, 2048 }, { 8, 253, 2048 }, { 8, 254, 2048 }, { 9, 255, 2048 }, 
02462    { 2, 256, 2048 }, { 3, 257, 2048 }, { 3, 258, 2048 }, { 4, 259, 2048 }, { 3, 260, 2048 }, { 4, 261, 2048 }, { 4, 262, 2048 }, { 5, 263, 2048 }, 
02463    { 3, 264, 2048 }, { 4, 265, 2048 }, { 4, 266, 2048 }, { 5, 267, 2048 }, { 4, 268, 2048 }, { 5, 269, 2048 }, { 5, 270, 2048 }, { 6, 271, 2048 }, 
02464    { 3, 272, 2048 }, { 4, 273, 2048 }, { 4, 274, 2048 }, { 5, 275, 2048 }, { 4, 276, 2048 }, { 5, 277, 2048 }, { 5, 278, 2048 }, { 6, 279, 2048 }, 
02465    { 4, 280, 2048 }, { 5, 281, 2048 }, { 5, 282, 2048 }, { 6, 283, 2048 }, { 5, 284, 2048 }, { 6, 285, 2048 }, { 6, 286, 2048 }, { 7, 287, 2048 }, 
02466    { 3, 288, 2048 }, { 4, 289, 2048 }, { 4, 290, 2048 }, { 5, 291, 2048 }, { 4, 292, 2048 }, { 5, 293, 2048 }, { 5, 294, 2048 }, { 6, 295, 2048 }, 
02467    { 4, 296, 2048 }, { 5, 297, 2048 }, { 5, 298, 2048 }, { 6, 299, 2048 }, { 5, 300, 2048 }, { 6, 301, 2048 }, { 6, 302, 2048 }, { 7, 303, 2048 }, 
02468    { 4, 304, 2048 }, { 5, 305, 2048 }, { 5, 306, 2048 }, { 6, 307, 2048 }, { 5, 308, 2048 }, { 6, 309, 2048 }, { 6, 310, 2048 }, { 7, 311, 2048 }, 
02469    { 5, 312, 2048 }, { 6, 313, 2048 }, { 6, 314, 2048 }, { 7, 315, 2048 }, { 6, 316, 2048 }, { 7, 317, 2048 }, { 7, 318, 2048 }, { 8, 319, 2048 }, 
02470    { 3, 320, 2048 }, { 4, 321, 2048 }, { 4, 322, 2048 }, { 5, 323, 2048 }, { 4, 324, 2048 }, { 5, 325, 2048 }, { 5, 326, 2048 }, { 6, 327, 2048 }, 
02471    { 4, 328, 2048 }, { 5, 329, 2048 }, { 5, 330, 2048 }, { 6, 331, 2048 }, { 5, 332, 2048 }, { 6, 333, 2048 }, { 6, 334, 2048 }, { 7, 335, 2048 }, 
02472    { 4, 336, 2048 }, { 5, 337, 2048 }, { 5, 338, 2048 }, { 6, 339, 2048 }, { 5, 340, 2048 }, { 6, 341, 2048 }, { 6, 342, 2048 }, { 7, 343, 2048 }, 
02473    { 5, 344, 2048 }, { 6, 345, 2048 }, { 6, 346, 2048 }, { 7, 347, 2048 }, { 6, 348, 2048 }, { 7, 349, 2048 }, { 7, 350, 2048 }, { 8, 351, 2048 }, 
02474    { 4, 352, 2048 }, { 5, 353, 2048 }, { 5, 354, 2048 }, { 6, 355, 2048 }, { 5, 356, 2048 }, { 6, 357, 2048 }, { 6, 358, 2048 }, { 7, 359, 2048 }, 
02475    { 5, 360, 2048 }, { 6, 361, 2048 }, { 6, 362, 2048 }, { 7, 363, 2048 }, { 6, 364, 2048 }, { 7, 365, 2048 }, { 7, 366, 2048 }, { 8, 367, 2048 }, 
02476    { 5, 368, 2048 }, { 6, 369, 2048 }, { 6, 370, 2048 }, { 7, 371, 2048 }, { 6, 372, 2048 }, { 7, 373, 2048 }, { 7, 374, 2048 }, { 8, 375, 2048 }, 
02477    { 6, 376, 2048 }, { 7, 377, 2048 }, { 7, 378, 2048 }, { 8, 379, 2048 }, { 7, 380, 2048 }, { 8, 381, 2048 }, { 8, 382, 2048 }, { 9, 383, 2048 }, 
02478    { 3, 384, 2048 }, { 4, 385, 2048 }, { 4, 386, 2048 }, { 5, 387, 2048 }, { 4, 388, 2048 }, { 5, 389, 2048 }, { 5, 390, 2048 }, { 6, 391, 2048 }, 
02479    { 4, 392, 2048 }, { 5, 393, 2048 }, { 5, 394, 2048 }, { 6, 395, 2048 }, { 5, 396, 2048 }, { 6, 397, 2048 }, { 6, 398, 2048 }, { 7, 399, 2048 }, 
02480    { 4, 400, 2048 }, { 5, 401, 2048 }, { 5, 402, 2048 }, { 6, 403, 2048 }, { 5, 404, 2048 }, { 6, 405, 2048 }, { 6, 406, 2048 }, { 7, 407, 2048 }, 
02481    { 5, 408, 2048 }, { 6, 409, 2048 }, { 6, 410, 2048 }, { 7, 411, 2048 }, { 6, 412, 2048 }, { 7, 413, 2048 }, { 7, 414, 2048 }, { 8, 415, 2048 }, 
02482    { 4, 416, 2048 }, { 5, 417, 2048 }, { 5, 418, 2048 }, { 6, 419, 2048 }, { 5, 420, 2048 }, { 6, 421, 2048 }, { 6, 422, 2048 }, { 7, 423, 2048 }, 
02483    { 5, 424, 2048 }, { 6, 425, 2048 }, { 6, 426, 2048 }, { 7, 427, 2048 }, { 6, 428, 2048 }, { 7, 429, 2048 }, { 7, 430, 2048 }, { 8, 431, 2048 }, 
02484    { 5, 432, 2048 }, { 6, 433, 2048 }, { 6, 434, 2048 }, { 7, 435, 2048 }, { 6, 436, 2048 }, { 7, 437, 2048 }, { 7, 438, 2048 }, { 8, 439, 2048 }, 
02485    { 6, 440, 2048 }, { 7, 441, 2048 }, { 7, 442, 2048 }, { 8, 443, 2048 }, { 7, 444, 2048 }, { 8, 445, 2048 }, { 8, 446, 2048 }, { 9, 447, 2048 }, 
02486    { 4, 448, 2048 }, { 5, 449, 2048 }, { 5, 450, 2048 }, { 6, 451, 2048 }, { 5, 452, 2048 }, { 6, 453, 2048 }, { 6, 454, 2048 }, { 7, 455, 2048 }, 
02487    { 5, 456, 2048 }, { 6, 457, 2048 }, { 6, 458, 2048 }, { 7, 459, 2048 }, { 6, 460, 2048 }, { 7, 461, 2048 }, { 7, 462, 2048 }, { 8, 463, 2048 }, 
02488    { 5, 464, 2048 }, { 6, 465, 2048 }, { 6, 466, 2048 }, { 7, 467, 2048 }, { 6, 468, 2048 }, { 7, 469, 2048 }, { 7, 470, 2048 }, { 8, 471, 2048 }, 
02489    { 6, 472, 2048 }, { 7, 473, 2048 }, { 7, 474, 2048 }, { 8, 475, 2048 }, { 7, 476, 2048 }, { 8, 477, 2048 }, { 8, 478, 2048 }, { 9, 479, 2048 }, 
02490    { 5, 480, 2048 }, { 6, 481, 2048 }, { 6, 482, 2048 }, { 7, 483, 2048 }, { 6, 484, 2048 }, { 7, 485, 2048 }, { 7, 486, 2048 }, { 8, 487, 2048 }, 
02491    { 6, 488, 2048 }, { 7, 489, 2048 }, { 7, 490, 2048 }, { 8, 491, 2048 }, { 7, 492, 2048 }, { 8, 493, 2048 }, { 8, 494, 2048 }, { 9, 495, 2048 }, 
02492    { 6, 496, 2048 }, { 7, 497, 2048 }, { 7, 498, 2048 }, { 8, 499, 2048 }, { 7, 500, 2048 }, { 8, 501, 2048 }, { 8, 502, 2048 }, { 9, 503, 2048 }, 
02493    { 7, 504, 2048 }, { 8, 505, 2048 }, { 8, 506, 2048 }, { 9, 507, 2048 }, { 8, 508, 2048 }, { 9, 509, 2048 }, { 9, 510, 2048 }, { 10, 511, 2048 }, 
02494    { 2, 512, 2048 }, { 3, 513, 2048 }, { 3, 514, 2048 }, { 4, 515, 2048 }, { 3, 516, 2048 }, { 4, 517, 2048 }, { 4, 518, 2048 }, { 5, 519, 2048 }, 
02495    { 3, 520, 2048 }, { 4, 521, 2048 }, { 4, 522, 2048 }, { 5, 523, 2048 }, { 4, 524, 2048 }, { 5, 525, 2048 }, { 5, 526, 2048 }, { 6, 527, 2048 }, 
02496    { 3, 528, 2048 }, { 4, 529, 2048 }, { 4, 530, 2048 }, { 5, 531, 2048 }, { 4, 532, 2048 }, { 5, 533, 2048 }, { 5, 534, 2048 }, { 6, 535, 2048 }, 
02497    { 4, 536, 2048 }, { 5, 537, 2048 }, { 5, 538, 2048 }, { 6, 539, 2048 }, { 5, 540, 2048 }, { 6, 541, 2048 }, { 6, 542, 2048 }, { 7, 543, 2048 }, 
02498    { 3, 544, 2048 }, { 4, 545, 2048 }, { 4, 546, 2048 }, { 5, 547, 2048 }, { 4, 548, 2048 }, { 5, 549, 2048 }, { 5, 550, 2048 }, { 6, 551, 2048 }, 
02499    { 4, 552, 2048 }, { 5, 553, 2048 }, { 5, 554, 2048 }, { 6, 555, 2048 }, { 5, 556, 2048 }, { 6, 557, 2048 }, { 6, 558, 2048 }, { 7, 559, 2048 }, 
02500    { 4, 560, 2048 }, { 5, 561, 2048 }, { 5, 562, 2048 }, { 6, 563, 2048 }, { 5, 564, 2048 }, { 6, 565, 2048 }, { 6, 566, 2048 }, { 7, 567, 2048 }, 
02501    { 5, 568, 2048 }, { 6, 569, 2048 }, { 6, 570, 2048 }, { 7, 571, 2048 }, { 6, 572, 2048 }, { 7, 573, 2048 }, { 7, 574, 2048 }, { 8, 575, 2048 }, 
02502    { 3, 576, 2048 }, { 4, 577, 2048 }, { 4, 578, 2048 }, { 5, 579, 2048 }, { 4, 580, 2048 }, { 5, 581, 2048 }, { 5, 582, 2048 }, { 6, 583, 2048 }, 
02503    { 4, 584, 2048 }, { 5, 585, 2048 }, { 5, 586, 2048 }, { 6, 587, 2048 }, { 5, 588, 2048 }, { 6, 589, 2048 }, { 6, 590, 2048 }, { 7, 591, 2048 }, 
02504    { 4, 592, 2048 }, { 5, 593, 2048 }, { 5, 594, 2048 }, { 6, 595, 2048 }, { 5, 596, 2048 }, { 6, 597, 2048 }, { 6, 598, 2048 }, { 7, 599, 2048 }, 
02505    { 5, 600, 2048 }, { 6, 601, 2048 }, { 6, 602, 2048 }, { 7, 603, 2048 }, { 6, 604, 2048 }, { 7, 605, 2048 }, { 7, 606, 2048 }, { 8, 607, 2048 }, 
02506    { 4, 608, 2048 }, { 5, 609, 2048 }, { 5, 610, 2048 }, { 6, 611, 2048 }, { 5, 612, 2048 }, { 6, 613, 2048 }, { 6, 614, 2048 }, { 7, 615, 2048 }, 
02507    { 5, 616, 2048 }, { 6, 617, 2048 }, { 6, 618, 2048 }, { 7, 619, 2048 }, { 6, 620, 2048 }, { 7, 621, 2048 }, { 7, 622, 2048 }, { 8, 623, 2048 }, 
02508    { 5, 624, 2048 }, { 6, 625, 2048 }, { 6, 626, 2048 }, { 7, 627, 2048 }, { 6, 628, 2048 }, { 7, 629, 2048 }, { 7, 630, 2048 }, { 8, 631, 2048 }, 
02509    { 6, 632, 2048 }, { 7, 633, 2048 }, { 7, 634, 2048 }, { 8, 635, 2048 }, { 7, 636, 2048 }, { 8, 637, 2048 }, { 8, 638, 2048 }, { 9, 639, 2048 }, 
02510    { 3, 640, 2048 }, { 4, 641, 2048 }, { 4, 642, 2048 }, { 5, 643, 2048 }, { 4, 644, 2048 }, { 5, 645, 2048 }, { 5, 646, 2048 }, { 6, 647, 2048 }, 
02511    { 4, 648, 2048 }, { 5, 649, 2048 }, { 5, 650, 2048 }, { 6, 651, 2048 }, { 5, 652, 2048 }, { 6, 653, 2048 }, { 6, 654, 2048 }, { 7, 655, 2048 }, 
02512    { 4, 656, 2048 }, { 5, 657, 2048 }, { 5, 658, 2048 }, { 6, 659, 2048 }, { 5, 660, 2048 }, { 6, 661, 2048 }, { 6, 662, 2048 }, { 7, 663, 2048 }, 
02513    { 5, 664, 2048 }, { 6, 665, 2048 }, { 6, 666, 2048 }, { 7, 667, 2048 }, { 6, 668, 2048 }, { 7, 669, 2048 }, { 7, 670, 2048 }, { 8, 671, 2048 }, 
02514    { 4, 672, 2048 }, { 5, 673, 2048 }, { 5, 674, 2048 }, { 6, 675, 2048 }, { 5, 676, 2048 }, { 6, 677, 2048 }, { 6, 678, 2048 }, { 7, 679, 2048 }, 
02515    { 5, 680, 2048 }, { 6, 681, 2048 }, { 6, 682, 2048 }, { 7, 683, 2048 }, { 6, 684, 2048 }, { 7, 685, 2048 }, { 7, 686, 2048 }, { 8, 687, 2048 }, 
02516    { 5, 688, 2048 }, { 6, 689, 2048 }, { 6, 690, 2048 }, { 7, 691, 2048 }, { 6, 692, 2048 }, { 7, 693, 2048 }, { 7, 694, 2048 }, { 8, 695, 2048 }, 
02517    { 6, 696, 2048 }, { 7, 697, 2048 }, { 7, 698, 2048 }, { 8, 699, 2048 }, { 7, 700, 2048 }, { 8, 701, 2048 }, { 8, 702, 2048 }, { 9, 703, 2048 }, 
02518    { 4, 704, 2048 }, { 5, 705, 2048 }, { 5, 706, 2048 }, { 6, 707, 2048 }, { 5, 708, 2048 }, { 6, 709, 2048 }, { 6, 710, 2048 }, { 7, 711, 2048 }, 
02519    { 5, 712, 2048 }, { 6, 713, 2048 }, { 6, 714, 2048 }, { 7, 715, 2048 }, { 6, 716, 2048 }, { 7, 717, 2048 }, { 7, 718, 2048 }, { 8, 719, 2048 }, 
02520    { 5, 720, 2048 }, { 6, 721, 2048 }, { 6, 722, 2048 }, { 7, 723, 2048 }, { 6, 724, 2048 }, { 7, 725, 2048 }, { 7, 726, 2048 }, { 8, 727, 2048 }, 
02521    { 6, 728, 2048 }, { 7, 729, 2048 }, { 7, 730, 2048 }, { 8, 731, 2048 }, { 7, 732, 2048 }, { 8, 733, 2048 }, { 8, 734, 2048 }, { 9, 735, 2048 }, 
02522    { 5, 736, 2048 }, { 6, 737, 2048 }, { 6, 738, 2048 }, { 7, 739, 2048 }, { 6, 740, 2048 }, { 7, 741, 2048 }, { 7, 742, 2048 }, { 8, 743, 2048 }, 
02523    { 6, 744, 2048 }, { 7, 745, 2048 }, { 7, 746, 2048 }, { 8, 747, 2048 }, { 7, 748, 2048 }, { 8, 749, 2048 }, { 8, 750, 2048 }, { 9, 751, 2048 }, 
02524    { 6, 752, 2048 }, { 7, 753, 2048 }, { 7, 754, 2048 }, { 8, 755, 2048 }, { 7, 756, 2048 }, { 8, 757, 2048 }, { 8, 758, 2048 }, { 9, 759, 2048 }, 
02525    { 7, 760, 2048 }, { 8, 761, 2048 }, { 8, 762, 2048 }, { 9, 763, 2048 }, { 8, 764, 2048 }, { 9, 765, 2048 }, { 9, 766, 2048 }, { 10, 767, 2048 }, 
02526    { 3, 768, 2048 }, { 4, 769, 2048 }, { 4, 770, 2048 }, { 5, 771, 2048 }, { 4, 772, 2048 }, { 5, 773, 2048 }, { 5, 774, 2048 }, { 6, 775, 2048 }, 
02527    { 4, 776, 2048 }, { 5, 777, 2048 }, { 5, 778, 2048 }, { 6, 779, 2048 }, { 5, 780, 2048 }, { 6, 781, 2048 }, { 6, 782, 2048 }, { 7, 783, 2048 }, 
02528    { 4, 784, 2048 }, { 5, 785, 2048 }, { 5, 786, 2048 }, { 6, 787, 2048 }, { 5, 788, 2048 }, { 6, 789, 2048 }, { 6, 790, 2048 }, { 7, 791, 2048 }, 
02529    { 5, 792, 2048 }, { 6, 793, 2048 }, { 6, 794, 2048 }, { 7, 795, 2048 }, { 6, 796, 2048 }, { 7, 797, 2048 }, { 7, 798, 2048 }, { 8, 799, 2048 }, 
02530    { 4, 800, 2048 }, { 5, 801, 2048 }, { 5, 802, 2048 }, { 6, 803, 2048 }, { 5, 804, 2048 }, { 6, 805, 2048 }, { 6, 806, 2048 }, { 7, 807, 2048 }, 
02531    { 5, 808, 2048 }, { 6, 809, 2048 }, { 6, 810, 2048 }, { 7, 811, 2048 }, { 6, 812, 2048 }, { 7, 813, 2048 }, { 7, 814, 2048 }, { 8, 815, 2048 }, 
02532    { 5, 816, 2048 }, { 6, 817, 2048 }, { 6, 818, 2048 }, { 7, 819, 2048 }, { 6, 820, 2048 }, { 7, 821, 2048 }, { 7, 822, 2048 }, { 8, 823, 2048 }, 
02533    { 6, 824, 2048 }, { 7, 825, 2048 }, { 7, 826, 2048 }, { 8, 827, 2048 }, { 7, 828, 2048 }, { 8, 829, 2048 }, { 8, 830, 2048 }, { 9, 831, 2048 }, 
02534    { 4, 832, 2048 }, { 5, 833, 2048 }, { 5, 834, 2048 }, { 6, 835, 2048 }, { 5, 836, 2048 }, { 6, 837, 2048 }, { 6, 838, 2048 }, { 7, 839, 2048 }, 
02535    { 5, 840, 2048 }, { 6, 841, 2048 }, { 6, 842, 2048 }, { 7, 843, 2048 }, { 6, 844, 2048 }, { 7, 845, 2048 }, { 7, 846, 2048 }, { 8, 847, 2048 }, 
02536    { 5, 848, 2048 }, { 6, 849, 2048 }, { 6, 850, 2048 }, { 7, 851, 2048 }, { 6, 852, 2048 }, { 7, 853, 2048 }, { 7, 854, 2048 }, { 8, 855, 2048 }, 
02537    { 6, 856, 2048 }, { 7, 857, 2048 }, { 7, 858, 2048 }, { 8, 859, 2048 }, { 7, 860, 2048 }, { 8, 861, 2048 }, { 8, 862, 2048 }, { 9, 863, 2048 }, 
02538    { 5, 864, 2048 }, { 6, 865, 2048 }, { 6, 866, 2048 }, { 7, 867, 2048 }, { 6, 868, 2048 }, { 7, 869, 2048 }, { 7, 870, 2048 }, { 8, 871, 2048 }, 
02539    { 6, 872, 2048 }, { 7, 873, 2048 }, { 7, 874, 2048 }, { 8, 875, 2048 }, { 7, 876, 2048 }, { 8, 877, 2048 }, { 8, 878, 2048 }, { 9, 879, 2048 }, 
02540    { 6, 880, 2048 }, { 7, 881, 2048 }, { 7, 882, 2048 }, { 8, 883, 2048 }, { 7, 884, 2048 }, { 8, 885, 2048 }, { 8, 886, 2048 }, { 9, 887, 2048 }, 
02541    { 7, 888, 2048 }, { 8, 889, 2048 }, { 8, 890, 2048 }, { 9, 891, 2048 }, { 8, 892, 2048 }, { 9, 893, 2048 }, { 9, 894, 2048 }, { 10, 895, 2048 }, 
02542    { 4, 896, 2048 }, { 5, 897, 2048 }, { 5, 898, 2048 }, { 6, 899, 2048 }, { 5, 900, 2048 }, { 6, 901, 2048 }, { 6, 902, 2048 }, { 7, 903, 2048 }, 
02543    { 5, 904, 2048 }, { 6, 905, 2048 }, { 6, 906, 2048 }, { 7, 907, 2048 }, { 6, 908, 2048 }, { 7, 909, 2048 }, { 7, 910, 2048 }, { 8, 911, 2048 }, 
02544    { 5, 912, 2048 }, { 6, 913, 2048 }, { 6, 914, 2048 }, { 7, 915, 2048 }, { 6, 916, 2048 }, { 7, 917, 2048 }, { 7, 918, 2048 }, { 8, 919, 2048 }, 
02545    { 6, 920, 2048 }, { 7, 921, 2048 }, { 7, 922, 2048 }, { 8, 923, 2048 }, { 7, 924, 2048 }, { 8, 925, 2048 }, { 8, 926, 2048 }, { 9, 927, 2048 }, 
02546    { 5, 928, 2048 }, { 6, 929, 2048 }, { 6, 930, 2048 }, { 7, 931, 2048 }, { 6, 932, 2048 }, { 7, 933, 2048 }, { 7, 934, 2048 }, { 8, 935, 2048 }, 
02547    { 6, 936, 2048 }, { 7, 937, 2048 }, { 7, 938, 2048 }, { 8, 939, 2048 }, { 7, 940, 2048 }, { 8, 941, 2048 }, { 8, 942, 2048 }, { 9, 943, 2048 }, 
02548    { 6, 944, 2048 }, { 7, 945, 2048 }, { 7, 946, 2048 }, { 8, 947, 2048 }, { 7, 948, 2048 }, { 8, 949, 2048 }, { 8, 950, 2048 }, { 9, 951, 2048 }, 
02549    { 7, 952, 2048 }, { 8, 953, 2048 }, { 8, 954, 2048 }, { 9, 955, 2048 }, { 8, 956, 2048 }, { 9, 957, 2048 }, { 9, 958, 2048 }, { 10, 959, 2048 }, 
02550    { 5, 960, 2048 }, { 6, 961, 2048 }, { 6, 962, 2048 }, { 7, 963, 2048 }, { 6, 964, 2048 }, { 7, 965, 2048 }, { 7, 966, 2048 }, { 8, 967, 2048 }, 
02551    { 6, 968, 2048 }, { 7, 969, 2048 }, { 7, 970, 2048 }, { 8, 971, 2048 }, { 7, 972, 2048 }, { 8, 973, 2048 }, { 8, 974, 2048 }, { 9, 975, 2048 }, 
02552    { 6, 976, 2048 }, { 7, 977, 2048 }, { 7, 978, 2048 }, { 8, 979, 2048 }, { 7, 980, 2048 }, { 8, 981, 2048 }, { 8, 982, 2048 }, { 9, 983, 2048 }, 
02553    { 7, 984, 2048 }, { 8, 985, 2048 }, { 8, 986, 2048 }, { 9, 987, 2048 }, { 8, 988, 2048 }, { 9, 989, 2048 }, { 9, 990, 2048 }, { 10, 991, 2048 }, 
02554    { 6, 992, 2048 }, { 7, 993, 2048 }, { 7, 994, 2048 }, { 8, 995, 2048 }, { 7, 996, 2048 }, { 8, 997, 2048 }, { 8, 998, 2048 }, { 9, 999, 2048 }, 
02555    { 7, 1000, 2048 }, { 8, 1001, 2048 }, { 8, 1002, 2048 }, { 9, 1003, 2048 }, { 8, 1004, 2048 }, { 9, 1005, 2048 }, { 9, 1006, 2048 }, { 10, 1007, 2048 }, 
02556    { 7, 1008, 2048 }, { 8, 1009, 2048 }, { 8, 1010, 2048 }, { 9, 1011, 2048 }, { 8, 1012, 2048 }, { 9, 1013, 2048 }, { 9, 1014, 2048 }, { 10, 1015, 2048 }, 
02557    { 8, 1016, 2048 }, { 9, 1017, 2048 }, { 9, 1018, 2048 }, { 10, 1019, 2048 }, { 9, 1020, 2048 }, { 10, 1021, 2048 }, { 10, 1022, 2048 }, { 11, 1023, 2048 }, 
02558    { 2, 1024, 2048 }, { 3, 1025, 2048 }, { 3, 1026, 2048 }, { 4, 1027, 2048 }, { 3, 1028, 2048 }, { 4, 1029, 2048 }, { 4, 1030, 2048 }, { 5, 1031, 2048 }, 
02559    { 3, 1032, 2048 }, { 4, 1033, 2048 }, { 4, 1034, 2048 }, { 5, 1035, 2048 }, { 4, 1036, 2048 }, { 5, 1037, 2048 }, { 5, 1038, 2048 }, { 6, 1039, 2048 }, 
02560    { 3, 1040, 2048 }, { 4, 1041, 2048 }, { 4, 1042, 2048 }, { 5, 1043, 2048 }, { 4, 1044, 2048 }, { 5, 1045, 2048 }, { 5, 1046, 2048 }, { 6, 1047, 2048 }, 
02561    { 4, 1048, 2048 }, { 5, 1049, 2048 }, { 5, 1050, 2048 }, { 6, 1051, 2048 }, { 5, 1052, 2048 }, { 6, 1053, 2048 }, { 6, 1054, 2048 }, { 7, 1055, 2048 }, 
02562    { 3, 1056, 2048 }, { 4, 1057, 2048 }, { 4, 1058, 2048 }, { 5, 1059, 2048 }, { 4, 1060, 2048 }, { 5, 1061, 2048 }, { 5, 1062, 2048 }, { 6, 1063, 2048 }, 
02563    { 4, 1064, 2048 }, { 5, 1065, 2048 }, { 5, 1066, 2048 }, { 6, 1067, 2048 }, { 5, 1068, 2048 }, { 6, 1069, 2048 }, { 6, 1070, 2048 }, { 7, 1071, 2048 }, 
02564    { 4, 1072, 2048 }, { 5, 1073, 2048 }, { 5, 1074, 2048 }, { 6, 1075, 2048 }, { 5, 1076, 2048 }, { 6, 1077, 2048 }, { 6, 1078, 2048 }, { 7, 1079, 2048 }, 
02565    { 5, 1080, 2048 }, { 6, 1081, 2048 }, { 6, 1082, 2048 }, { 7, 1083, 2048 }, { 6, 1084, 2048 }, { 7, 1085, 2048 }, { 7, 1086, 2048 }, { 8, 1087, 2048 }, 
02566    { 3, 1088, 2048 }, { 4, 1089, 2048 }, { 4, 1090, 2048 }, { 5, 1091, 2048 }, { 4, 1092, 2048 }, { 5, 1093, 2048 }, { 5, 1094, 2048 }, { 6, 1095, 2048 }, 
02567    { 4, 1096, 2048 }, { 5, 1097, 2048 }, { 5, 1098, 2048 }, { 6, 1099, 2048 }, { 5, 1100, 2048 }, { 6, 1101, 2048 }, { 6, 1102, 2048 }, { 7, 1103, 2048 }, 
02568    { 4, 1104, 2048 }, { 5, 1105, 2048 }, { 5, 1106, 2048 }, { 6, 1107, 2048 }, { 5, 1108, 2048 }, { 6, 1109, 2048 }, { 6, 1110, 2048 }, { 7, 1111, 2048 }, 
02569    { 5, 1112, 2048 }, { 6, 1113, 2048 }, { 6, 1114, 2048 }, { 7, 1115, 2048 }, { 6, 1116, 2048 }, { 7, 1117, 2048 }, { 7, 1118, 2048 }, { 8, 1119, 2048 }, 
02570    { 4, 1120, 2048 }, { 5, 1121, 2048 }, { 5, 1122, 2048 }, { 6, 1123, 2048 }, { 5, 1124, 2048 }, { 6, 1125, 2048 }, { 6, 1126, 2048 }, { 7, 1127, 2048 }, 
02571    { 5, 1128, 2048 }, { 6, 1129, 2048 }, { 6, 1130, 2048 }, { 7, 1131, 2048 }, { 6, 1132, 2048 }, { 7, 1133, 2048 }, { 7, 1134, 2048 }, { 8, 1135, 2048 }, 
02572    { 5, 1136, 2048 }, { 6, 1137, 2048 }, { 6, 1138, 2048 }, { 7, 1139, 2048 }, { 6, 1140, 2048 }, { 7, 1141, 2048 }, { 7, 1142, 2048 }, { 8, 1143, 2048 }, 
02573    { 6, 1144, 2048 }, { 7, 1145, 2048 }, { 7, 1146, 2048 }, { 8, 1147, 2048 }, { 7, 1148, 2048 }, { 8, 1149, 2048 }, { 8, 1150, 2048 }, { 9, 1151, 2048 }, 
02574    { 3, 1152, 2048 }, { 4, 1153, 2048 }, { 4, 1154, 2048 }, { 5, 1155, 2048 }, { 4, 1156, 2048 }, { 5, 1157, 2048 }, { 5, 1158, 2048 }, { 6, 1159, 2048 }, 
02575    { 4, 1160, 2048 }, { 5, 1161, 2048 }, { 5, 1162, 2048 }, { 6, 1163, 2048 }, { 5, 1164, 2048 }, { 6, 1165, 2048 }, { 6, 1166, 2048 }, { 7, 1167, 2048 }, 
02576    { 4, 1168, 2048 }, { 5, 1169, 2048 }, { 5, 1170, 2048 }, { 6, 1171, 2048 }, { 5, 1172, 2048 }, { 6, 1173, 2048 }, { 6, 1174, 2048 }, { 7, 1175, 2048 }, 
02577    { 5, 1176, 2048 }, { 6, 1177, 2048 }, { 6, 1178, 2048 }, { 7, 1179, 2048 }, { 6, 1180, 2048 }, { 7, 1181, 2048 }, { 7, 1182, 2048 }, { 8, 1183, 2048 }, 
02578    { 4, 1184, 2048 }, { 5, 1185, 2048 }, { 5, 1186, 2048 }, { 6, 1187, 2048 }, { 5, 1188, 2048 }, { 6, 1189, 2048 }, { 6, 1190, 2048 }, { 7, 1191, 2048 }, 
02579    { 5, 1192, 2048 }, { 6, 1193, 2048 }, { 6, 1194, 2048 }, { 7, 1195, 2048 }, { 6, 1196, 2048 }, { 7, 1197, 2048 }, { 7, 1198, 2048 }, { 8, 1199, 2048 }, 
02580    { 5, 1200, 2048 }, { 6, 1201, 2048 }, { 6, 1202, 2048 }, { 7, 1203, 2048 }, { 6, 1204, 2048 }, { 7, 1205, 2048 }, { 7, 1206, 2048 }, { 8, 1207, 2048 }, 
02581    { 6, 1208, 2048 }, { 7, 1209, 2048 }, { 7, 1210, 2048 }, { 8, 1211, 2048 }, { 7, 1212, 2048 }, { 8, 1213, 2048 }, { 8, 1214, 2048 }, { 9, 1215, 2048 }, 
02582    { 4, 1216, 2048 }, { 5, 1217, 2048 }, { 5, 1218, 2048 }, { 6, 1219, 2048 }, { 5, 1220, 2048 }, { 6, 1221, 2048 }, { 6, 1222, 2048 }, { 7, 1223, 2048 }, 
02583    { 5, 1224, 2048 }, { 6, 1225, 2048 }, { 6, 1226, 2048 }, { 7, 1227, 2048 }, { 6, 1228, 2048 }, { 7, 1229, 2048 }, { 7, 1230, 2048 }, { 8, 1231, 2048 }, 
02584    { 5, 1232, 2048 }, { 6, 1233, 2048 }, { 6, 1234, 2048 }, { 7, 1235, 2048 }, { 6, 1236, 2048 }, { 7, 1237, 2048 }, { 7, 1238, 2048 }, { 8, 1239, 2048 }, 
02585    { 6, 1240, 2048 }, { 7, 1241, 2048 }, { 7, 1242, 2048 }, { 8, 1243, 2048 }, { 7, 1244, 2048 }, { 8, 1245, 2048 }, { 8, 1246, 2048 }, { 9, 1247, 2048 }, 
02586    { 5, 1248, 2048 }, { 6, 1249, 2048 }, { 6, 1250, 2048 }, { 7, 1251, 2048 }, { 6, 1252, 2048 }, { 7, 1253, 2048 }, { 7, 1254, 2048 }, { 8, 1255, 2048 }, 
02587    { 6, 1256, 2048 }, { 7, 1257, 2048 }, { 7, 1258, 2048 }, { 8, 1259, 2048 }, { 7, 1260, 2048 }, { 8, 1261, 2048 }, { 8, 1262, 2048 }, { 9, 1263, 2048 }, 
02588    { 6, 1264, 2048 }, { 7, 1265, 2048 }, { 7, 1266, 2048 }, { 8, 1267, 2048 }, { 7, 1268, 2048 }, { 8, 1269, 2048 }, { 8, 1270, 2048 }, { 9, 1271, 2048 }, 
02589    { 7, 1272, 2048 }, { 8, 1273, 2048 }, { 8, 1274, 2048 }, { 9, 1275, 2048 }, { 8, 1276, 2048 }, { 9, 1277, 2048 }, { 9, 1278, 2048 }, { 10, 1279, 2048 }, 
02590    { 3, 1280, 2048 }, { 4, 1281, 2048 }, { 4, 1282, 2048 }, { 5, 1283, 2048 }, { 4, 1284, 2048 }, { 5, 1285, 2048 }, { 5, 1286, 2048 }, { 6, 1287, 2048 }, 
02591    { 4, 1288, 2048 }, { 5, 1289, 2048 }, { 5, 1290, 2048 }, { 6, 1291, 2048 }, { 5, 1292, 2048 }, { 6, 1293, 2048 }, { 6, 1294, 2048 }, { 7, 1295, 2048 }, 
02592    { 4, 1296, 2048 }, { 5, 1297, 2048 }, { 5, 1298, 2048 }, { 6, 1299, 2048 }, { 5, 1300, 2048 }, { 6, 1301, 2048 }, { 6, 1302, 2048 }, { 7, 1303, 2048 }, 
02593    { 5, 1304, 2048 }, { 6, 1305, 2048 }, { 6, 1306, 2048 }, { 7, 1307, 2048 }, { 6, 1308, 2048 }, { 7, 1309, 2048 }, { 7, 1310, 2048 }, { 8, 1311, 2048 }, 
02594    { 4, 1312, 2048 }, { 5, 1313, 2048 }, { 5, 1314, 2048 }, { 6, 1315, 2048 }, { 5, 1316, 2048 }, { 6, 1317, 2048 }, { 6, 1318, 2048 }, { 7, 1319, 2048 }, 
02595    { 5, 1320, 2048 }, { 6, 1321, 2048 }, { 6, 1322, 2048 }, { 7, 1323, 2048 }, { 6, 1324, 2048 }, { 7, 1325, 2048 }, { 7, 1326, 2048 }, { 8, 1327, 2048 }, 
02596    { 5, 1328, 2048 }, { 6, 1329, 2048 }, { 6, 1330, 2048 }, { 7, 1331, 2048 }, { 6, 1332, 2048 }, { 7, 1333, 2048 }, { 7, 1334, 2048 }, { 8, 1335, 2048 }, 
02597    { 6, 1336, 2048 }, { 7, 1337, 2048 }, { 7, 1338, 2048 }, { 8, 1339, 2048 }, { 7, 1340, 2048 }, { 8, 1341, 2048 }, { 8, 1342, 2048 }, { 9, 1343, 2048 }, 
02598    { 4, 1344, 2048 }, { 5, 1345, 2048 }, { 5, 1346, 2048 }, { 6, 1347, 2048 }, { 5, 1348, 2048 }, { 6, 1349, 2048 }, { 6, 1350, 2048 }, { 7, 1351, 2048 }, 
02599    { 5, 1352, 2048 }, { 6, 1353, 2048 }, { 6, 1354, 2048 }, { 7, 1355, 2048 }, { 6, 1356, 2048 }, { 7, 1357, 2048 }, { 7, 1358, 2048 }, { 8, 1359, 2048 }, 
02600    { 5, 1360, 2048 }, { 6, 1361, 2048 }, { 6, 1362, 2048 }, { 7, 1363, 2048 }, { 6, 1364, 2048 }, { 7, 1365, 2048 }, { 7, 1366, 2048 }, { 8, 1367, 2048 }, 
02601    { 6, 1368, 2048 }, { 7, 1369, 2048 }, { 7, 1370, 2048 }, { 8, 1371, 2048 }, { 7, 1372, 2048 }, { 8, 1373, 2048 }, { 8, 1374, 2048 }, { 9, 1375, 2048 }, 
02602    { 5, 1376, 2048 }, { 6, 1377, 2048 }, { 6, 1378, 2048 }, { 7, 1379, 2048 }, { 6, 1380, 2048 }, { 7, 1381, 2048 }, { 7, 1382, 2048 }, { 8, 1383, 2048 }, 
02603    { 6, 1384, 2048 }, { 7, 1385, 2048 }, { 7, 1386, 2048 }, { 8, 1387, 2048 }, { 7, 1388, 2048 }, { 8, 1389, 2048 }, { 8, 1390, 2048 }, { 9, 1391, 2048 }, 
02604    { 6, 1392, 2048 }, { 7, 1393, 2048 }, { 7, 1394, 2048 }, { 8, 1395, 2048 }, { 7, 1396, 2048 }, { 8, 1397, 2048 }, { 8, 1398, 2048 }, { 9, 1399, 2048 }, 
02605    { 7, 1400, 2048 }, { 8, 1401, 2048 }, { 8, 1402, 2048 }, { 9, 1403, 2048 }, { 8, 1404, 2048 }, { 9, 1405, 2048 }, { 9, 1406, 2048 }, { 10, 1407, 2048 }, 
02606    { 4, 1408, 2048 }, { 5, 1409, 2048 }, { 5, 1410, 2048 }, { 6, 1411, 2048 }, { 5, 1412, 2048 }, { 6, 1413, 2048 }, { 6, 1414, 2048 }, { 7, 1415, 2048 }, 
02607    { 5, 1416, 2048 }, { 6, 1417, 2048 }, { 6, 1418, 2048 }, { 7, 1419, 2048 }, { 6, 1420, 2048 }, { 7, 1421, 2048 }, { 7, 1422, 2048 }, { 8, 1423, 2048 }, 
02608    { 5, 1424, 2048 }, { 6, 1425, 2048 }, { 6, 1426, 2048 }, { 7, 1427, 2048 }, { 6, 1428, 2048 }, { 7, 1429, 2048 }, { 7, 1430, 2048 }, { 8, 1431, 2048 }, 
02609    { 6, 1432, 2048 }, { 7, 1433, 2048 }, { 7, 1434, 2048 }, { 8, 1435, 2048 }, { 7, 1436, 2048 }, { 8, 1437, 2048 }, { 8, 1438, 2048 }, { 9, 1439, 2048 }, 
02610    { 5, 1440, 2048 }, { 6, 1441, 2048 }, { 6, 1442, 2048 }, { 7, 1443, 2048 }, { 6, 1444, 2048 }, { 7, 1445, 2048 }, { 7, 1446, 2048 }, { 8, 1447, 2048 }, 
02611    { 6, 1448, 2048 }, { 7, 1449, 2048 }, { 7, 1450, 2048 }, { 8, 1451, 2048 }, { 7, 1452, 2048 }, { 8, 1453, 2048 }, { 8, 1454, 2048 }, { 9, 1455, 2048 }, 
02612    { 6, 1456, 2048 }, { 7, 1457, 2048 }, { 7, 1458, 2048 }, { 8, 1459, 2048 }, { 7, 1460, 2048 }, { 8, 1461, 2048 }, { 8, 1462, 2048 }, { 9, 1463, 2048 }, 
02613    { 7, 1464, 2048 }, { 8, 1465, 2048 }, { 8, 1466, 2048 }, { 9, 1467, 2048 }, { 8, 1468, 2048 }, { 9, 1469, 2048 }, { 9, 1470, 2048 }, { 10, 1471, 2048 }, 
02614    { 5, 1472, 2048 }, { 6, 1473, 2048 }, { 6, 1474, 2048 }, { 7, 1475, 2048 }, { 6, 1476, 2048 }, { 7, 1477, 2048 }, { 7, 1478, 2048 }, { 8, 1479, 2048 }, 
02615    { 6, 1480, 2048 }, { 7, 1481, 2048 }, { 7, 1482, 2048 }, { 8, 1483, 2048 }, { 7, 1484, 2048 }, { 8, 1485, 2048 }, { 8, 1486, 2048 }, { 9, 1487, 2048 }, 
02616    { 6, 1488, 2048 }, { 7, 1489, 2048 }, { 7, 1490, 2048 }, { 8, 1491, 2048 }, { 7, 1492, 2048 }, { 8, 1493, 2048 }, { 8, 1494, 2048 }, { 9, 1495, 2048 }, 
02617    { 7, 1496, 2048 }, { 8, 1497, 2048 }, { 8, 1498, 2048 }, { 9, 1499, 2048 }, { 8, 1500, 2048 }, { 9, 1501, 2048 }, { 9, 1502, 2048 }, { 10, 1503, 2048 }, 
02618    { 6, 1504, 2048 }, { 7, 1505, 2048 }, { 7, 1506, 2048 }, { 8, 1507, 2048 }, { 7, 1508, 2048 }, { 8, 1509, 2048 }, { 8, 1510, 2048 }, { 9, 1511, 2048 }, 
02619    { 7, 1512, 2048 }, { 8, 1513, 2048 }, { 8, 1514, 2048 }, { 9, 1515, 2048 }, { 8, 1516, 2048 }, { 9, 1517, 2048 }, { 9, 1518, 2048 }, { 10, 1519, 2048 }, 
02620    { 7, 1520, 2048 }, { 8, 1521, 2048 }, { 8, 1522, 2048 }, { 9, 1523, 2048 }, { 8, 1524, 2048 }, { 9, 1525, 2048 }, { 9, 1526, 2048 }, { 10, 1527, 2048 }, 
02621    { 8, 1528, 2048 }, { 9, 1529, 2048 }, { 9, 1530, 2048 }, { 10, 1531, 2048 }, { 9, 1532, 2048 }, { 10, 1533, 2048 }, { 10, 1534, 2048 }, { 11, 1535, 2048 }, 
02622    { 3, 1536, 2048 }, { 4, 1537, 2048 }, { 4, 1538, 2048 }, { 5, 1539, 2048 }, { 4, 1540, 2048 }, { 5, 1541, 2048 }, { 5, 1542, 2048 }, { 6, 1543, 2048 }, 
02623    { 4, 1544, 2048 }, { 5, 1545, 2048 }, { 5, 1546, 2048 }, { 6, 1547, 2048 }, { 5, 1548, 2048 }, { 6, 1549, 2048 }, { 6, 1550, 2048 }, { 7, 1551, 2048 }, 
02624    { 4, 1552, 2048 }, { 5, 1553, 2048 }, { 5, 1554, 2048 }, { 6, 1555, 2048 }, { 5, 1556, 2048 }, { 6, 1557, 2048 }, { 6, 1558, 2048 }, { 7, 1559, 2048 }, 
02625    { 5, 1560, 2048 }, { 6, 1561, 2048 }, { 6, 1562, 2048 }, { 7, 1563, 2048 }, { 6, 1564, 2048 }, { 7, 1565, 2048 }, { 7, 1566, 2048 }, { 8, 1567, 2048 }, 
02626    { 4, 1568, 2048 }, { 5, 1569, 2048 }, { 5, 1570, 2048 }, { 6, 1571, 2048 }, { 5, 1572, 2048 }, { 6, 1573, 2048 }, { 6, 1574, 2048 }, { 7, 1575, 2048 }, 
02627    { 5, 1576, 2048 }, { 6, 1577, 2048 }, { 6, 1578, 2048 }, { 7, 1579, 2048 }, { 6, 1580, 2048 }, { 7, 1581, 2048 }, { 7, 1582, 2048 }, { 8, 1583, 2048 }, 
02628    { 5, 1584, 2048 }, { 6, 1585, 2048 }, { 6, 1586, 2048 }, { 7, 1587, 2048 }, { 6, 1588, 2048 }, { 7, 1589, 2048 }, { 7, 1590, 2048 }, { 8, 1591, 2048 }, 
02629    { 6, 1592, 2048 }, { 7, 1593, 2048 }, { 7, 1594, 2048 }, { 8, 1595, 2048 }, { 7, 1596, 2048 }, { 8, 1597, 2048 }, { 8, 1598, 2048 }, { 9, 1599, 2048 }, 
02630    { 4, 1600, 2048 }, { 5, 1601, 2048 }, { 5, 1602, 2048 }, { 6, 1603, 2048 }, { 5, 1604, 2048 }, { 6, 1605, 2048 }, { 6, 1606, 2048 }, { 7, 1607, 2048 }, 
02631    { 5, 1608, 2048 }, { 6, 1609, 2048 }, { 6, 1610, 2048 }, { 7, 1611, 2048 }, { 6, 1612, 2048 }, { 7, 1613, 2048 }, { 7, 1614, 2048 }, { 8, 1615, 2048 }, 
02632    { 5, 1616, 2048 }, { 6, 1617, 2048 }, { 6, 1618, 2048 }, { 7, 1619, 2048 }, { 6, 1620, 2048 }, { 7, 1621, 2048 }, { 7, 1622, 2048 }, { 8, 1623, 2048 }, 
02633    { 6, 1624, 2048 }, { 7, 1625, 2048 }, { 7, 1626, 2048 }, { 8, 1627, 2048 }, { 7, 1628, 2048 }, { 8, 1629, 2048 }, { 8, 1630, 2048 }, { 9, 1631, 2048 }, 
02634    { 5, 1632, 2048 }, { 6, 1633, 2048 }, { 6, 1634, 2048 }, { 7, 1635, 2048 }, { 6, 1636, 2048 }, { 7, 1637, 2048 }, { 7, 1638, 2048 }, { 8, 1639, 2048 }, 
02635    { 6, 1640, 2048 }, { 7, 1641, 2048 }, { 7, 1642, 2048 }, { 8, 1643, 2048 }, { 7, 1644, 2048 }, { 8, 1645, 2048 }, { 8, 1646, 2048 }, { 9, 1647, 2048 }, 
02636    { 6, 1648, 2048 }, { 7, 1649, 2048 }, { 7, 1650, 2048 }, { 8, 1651, 2048 }, { 7, 1652, 2048 }, { 8, 1653, 2048 }, { 8, 1654, 2048 }, { 9, 1655, 2048 }, 
02637    { 7, 1656, 2048 }, { 8, 1657, 2048 }, { 8, 1658, 2048 }, { 9, 1659, 2048 }, { 8, 1660, 2048 }, { 9, 1661, 2048 }, { 9, 1662, 2048 }, { 10, 1663, 2048 }, 
02638    { 4, 1664, 2048 }, { 5, 1665, 2048 }, { 5, 1666, 2048 }, { 6, 1667, 2048 }, { 5, 1668, 2048 }, { 6, 1669, 2048 }, { 6, 1670, 2048 }, { 7, 1671, 2048 }, 
02639    { 5, 1672, 2048 }, { 6, 1673, 2048 }, { 6, 1674, 2048 }, { 7, 1675, 2048 }, { 6, 1676, 2048 }, { 7, 1677, 2048 }, { 7, 1678, 2048 }, { 8, 1679, 2048 }, 
02640    { 5, 1680, 2048 }, { 6, 1681, 2048 }, { 6, 1682, 2048 }, { 7, 1683, 2048 }, { 6, 1684, 2048 }, { 7, 1685, 2048 }, { 7, 1686, 2048 }, { 8, 1687, 2048 }, 
02641    { 6, 1688, 2048 }, { 7, 1689, 2048 }, { 7, 1690, 2048 }, { 8, 1691, 2048 }, { 7, 1692, 2048 }, { 8, 1693, 2048 }, { 8, 1694, 2048 }, { 9, 1695, 2048 }, 
02642    { 5, 1696, 2048 }, { 6, 1697, 2048 }, { 6, 1698, 2048 }, { 7, 1699, 2048 }, { 6, 1700, 2048 }, { 7, 1701, 2048 }, { 7, 1702, 2048 }, { 8, 1703, 2048 }, 
02643    { 6, 1704, 2048 }, { 7, 1705, 2048 }, { 7, 1706, 2048 }, { 8, 1707, 2048 }, { 7, 1708, 2048 }, { 8, 1709, 2048 }, { 8, 1710, 2048 }, { 9, 1711, 2048 }, 
02644    { 6, 1712, 2048 }, { 7, 1713, 2048 }, { 7, 1714, 2048 }, { 8, 1715, 2048 }, { 7, 1716, 2048 }, { 8, 1717, 2048 }, { 8, 1718, 2048 }, { 9, 1719, 2048 }, 
02645    { 7, 1720, 2048 }, { 8, 1721, 2048 }, { 8, 1722, 2048 }, { 9, 1723, 2048 }, { 8, 1724, 2048 }, { 9, 1725, 2048 }, { 9, 1726, 2048 }, { 10, 1727, 2048 }, 
02646    { 5, 1728, 2048 }, { 6, 1729, 2048 }, { 6, 1730, 2048 }, { 7, 1731, 2048 }, { 6, 1732, 2048 }, { 7, 1733, 2048 }, { 7, 1734, 2048 }, { 8, 1735, 2048 }, 
02647    { 6, 1736, 2048 }, { 7, 1737, 2048 }, { 7, 1738, 2048 }, { 8, 1739, 2048 }, { 7, 1740, 2048 }, { 8, 1741, 2048 }, { 8, 1742, 2048 }, { 9, 1743, 2048 }, 
02648    { 6, 1744, 2048 }, { 7, 1745, 2048 }, { 7, 1746, 2048 }, { 8, 1747, 2048 }, { 7, 1748, 2048 }, { 8, 1749, 2048 }, { 8, 1750, 2048 }, { 9, 1751, 2048 }, 
02649    { 7, 1752, 2048 }, { 8, 1753, 2048 }, { 8, 1754, 2048 }, { 9, 1755, 2048 }, { 8, 1756, 2048 }, { 9, 1757, 2048 }, { 9, 1758, 2048 }, { 10, 1759, 2048 }, 
02650    { 6, 1760, 2048 }, { 7, 1761, 2048 }, { 7, 1762, 2048 }, { 8, 1763, 2048 }, { 7, 1764, 2048 }, { 8, 1765, 2048 }, { 8, 1766, 2048 }, { 9, 1767, 2048 }, 
02651    { 7, 1768, 2048 }, { 8, 1769, 2048 }, { 8, 1770, 2048 }, { 9, 1771, 2048 }, { 8, 1772, 2048 }, { 9, 1773, 2048 }, { 9, 1774, 2048 }, { 10, 1775, 2048 }, 
02652    { 7, 1776, 2048 }, { 8, 1777, 2048 }, { 8, 1778, 2048 }, { 9, 1779, 2048 }, { 8, 1780, 2048 }, { 9, 1781, 2048 }, { 9, 1782, 2048 }, { 10, 1783, 2048 }, 
02653    { 8, 1784, 2048 }, { 9, 1785, 2048 }, { 9, 1786, 2048 }, { 10, 1787, 2048 }, { 9, 1788, 2048 }, { 10, 1789, 2048 }, { 10, 1790, 2048 }, { 11, 1791, 2048 }, 
02654    { 4, 1792, 2048 }, { 5, 1793, 2048 }, { 5, 1794, 2048 }, { 6, 1795, 2048 }, { 5, 1796, 2048 }, { 6, 1797, 2048 }, { 6, 1798, 2048 }, { 7, 1799, 2048 }, 
02655    { 5, 1800, 2048 }, { 6, 1801, 2048 }, { 6, 1802, 2048 }, { 7, 1803, 2048 }, { 6, 1804, 2048 }, { 7, 1805, 2048 }, { 7, 1806, 2048 }, { 8, 1807, 2048 }, 
02656    { 5, 1808, 2048 }, { 6, 1809, 2048 }, { 6, 1810, 2048 }, { 7, 1811, 2048 }, { 6, 1812, 2048 }, { 7, 1813, 2048 }, { 7, 1814, 2048 }, { 8, 1815, 2048 }, 
02657    { 6, 1816, 2048 }, { 7, 1817, 2048 }, { 7, 1818, 2048 }, { 8, 1819, 2048 }, { 7, 1820, 2048 }, { 8, 1821, 2048 }, { 8, 1822, 2048 }, { 9, 1823, 2048 }, 
02658    { 5, 1824, 2048 }, { 6, 1825, 2048 }, { 6, 1826, 2048 }, { 7, 1827, 2048 }, { 6, 1828, 2048 }, { 7, 1829, 2048 }, { 7, 1830, 2048 }, { 8, 1831, 2048 }, 
02659    { 6, 1832, 2048 }, { 7, 1833, 2048 }, { 7, 1834, 2048 }, { 8, 1835, 2048 }, { 7, 1836, 2048 }, { 8, 1837, 2048 }, { 8, 1838, 2048 }, { 9, 1839, 2048 }, 
02660    { 6, 1840, 2048 }, { 7, 1841, 2048 }, { 7, 1842, 2048 }, { 8, 1843, 2048 }, { 7, 1844, 2048 }, { 8, 1845, 2048 }, { 8, 1846, 2048 }, { 9, 1847, 2048 }, 
02661    { 7, 1848, 2048 }, { 8, 1849, 2048 }, { 8, 1850, 2048 }, { 9, 1851, 2048 }, { 8, 1852, 2048 }, { 9, 1853, 2048 }, { 9, 1854, 2048 }, { 10, 1855, 2048 }, 
02662    { 5, 1856, 2048 }, { 6, 1857, 2048 }, { 6, 1858, 2048 }, { 7, 1859, 2048 }, { 6, 1860, 2048 }, { 7, 1861, 2048 }, { 7, 1862, 2048 }, { 8, 1863, 2048 }, 
02663    { 6, 1864, 2048 }, { 7, 1865, 2048 }, { 7, 1866, 2048 }, { 8, 1867, 2048 }, { 7, 1868, 2048 }, { 8, 1869, 2048 }, { 8, 1870, 2048 }, { 9, 1871, 2048 }, 
02664    { 6, 1872, 2048 }, { 7, 1873, 2048 }, { 7, 1874, 2048 }, { 8, 1875, 2048 }, { 7, 1876, 2048 }, { 8, 1877, 2048 }, { 8, 1878, 2048 }, { 9, 1879, 2048 }, 
02665    { 7, 1880, 2048 }, { 8, 1881, 2048 }, { 8, 1882, 2048 }, { 9, 1883, 2048 }, { 8, 1884, 2048 }, { 9, 1885, 2048 }, { 9, 1886, 2048 }, { 10, 1887, 2048 }, 
02666    { 6, 1888, 2048 }, { 7, 1889, 2048 }, { 7, 1890, 2048 }, { 8, 1891, 2048 }, { 7, 1892, 2048 }, { 8, 1893, 2048 }, { 8, 1894, 2048 }, { 9, 1895, 2048 }, 
02667    { 7, 1896, 2048 }, { 8, 1897, 2048 }, { 8, 1898, 2048 }, { 9, 1899, 2048 }, { 8, 1900, 2048 }, { 9, 1901, 2048 }, { 9, 1902, 2048 }, { 10, 1903, 2048 }, 
02668    { 7, 1904, 2048 }, { 8, 1905, 2048 }, { 8, 1906, 2048 }, { 9, 1907, 2048 }, { 8, 1908, 2048 }, { 9, 1909, 2048 }, { 9, 1910, 2048 }, { 10, 1911, 2048 }, 
02669    { 8, 1912, 2048 }, { 9, 1913, 2048 }, { 9, 1914, 2048 }, { 10, 1915, 2048 }, { 9, 1916, 2048 }, { 10, 1917, 2048 }, { 10, 1918, 2048 }, { 11, 1919, 2048 }, 
02670    { 5, 1920, 2048 }, { 6, 1921, 2048 }, { 6, 1922, 2048 }, { 7, 1923, 2048 }, { 6, 1924, 2048 }, { 7, 1925, 2048 }, { 7, 1926, 2048 }, { 8, 1927, 2048 }, 
02671    { 6, 1928, 2048 }, { 7, 1929, 2048 }, { 7, 1930, 2048 }, { 8, 1931, 2048 }, { 7, 1932, 2048 }, { 8, 1933, 2048 }, { 8, 1934, 2048 }, { 9, 1935, 2048 }, 
02672    { 6, 1936, 2048 }, { 7, 1937, 2048 }, { 7, 1938, 2048 }, { 8, 1939, 2048 }, { 7, 1940, 2048 }, { 8, 1941, 2048 }, { 8, 1942, 2048 }, { 9, 1943, 2048 }, 
02673    { 7, 1944, 2048 }, { 8, 1945, 2048 }, { 8, 1946, 2048 }, { 9, 1947, 2048 }, { 8, 1948, 2048 }, { 9, 1949, 2048 }, { 9, 1950, 2048 }, { 10, 1951, 2048 }, 
02674    { 6, 1952, 2048 }, { 7, 1953, 2048 }, { 7, 1954, 2048 }, { 8, 1955, 2048 }, { 7, 1956, 2048 }, { 8, 1957, 2048 }, { 8, 1958, 2048 }, { 9, 1959, 2048 }, 
02675    { 7, 1960, 2048 }, { 8, 1961, 2048 }, { 8, 1962, 2048 }, { 9, 1963, 2048 }, { 8, 1964, 2048 }, { 9, 1965, 2048 }, { 9, 1966, 2048 }, { 10, 1967, 2048 }, 
02676    { 7, 1968, 2048 }, { 8, 1969, 2048 }, { 8, 1970, 2048 }, { 9, 1971, 2048 }, { 8, 1972, 2048 }, { 9, 1973, 2048 }, { 9, 1974, 2048 }, { 10, 1975, 2048 }, 
02677    { 8, 1976, 2048 }, { 9, 1977, 2048 }, { 9, 1978, 2048 }, { 10, 1979, 2048 }, { 9, 1980, 2048 }, { 10, 1981, 2048 }, { 10, 1982, 2048 }, { 11, 1983, 2048 }, 
02678    { 6, 1984, 2048 }, { 7, 1985, 2048 }, { 7, 1986, 2048 }, { 8, 1987, 2048 }, { 7, 1988, 2048 }, { 8, 1989, 2048 }, { 8, 1990, 2048 }, { 9, 1991, 2048 }, 
02679    { 7, 1992, 2048 }, { 8, 1993, 2048 }, { 8, 1994, 2048 }, { 9, 1995, 2048 }, { 8, 1996, 2048 }, { 9, 1997, 2048 }, { 9, 1998, 2048 }, { 10, 1999, 2048 }, 
02680    { 7, 2000, 2048 }, { 8, 2001, 2048 }, { 8, 2002, 2048 }, { 9, 2003, 2048 }, { 8, 2004, 2048 }, { 9, 2005, 2048 }, { 9, 2006, 2048 }, { 10, 2007, 2048 }, 
02681    { 8, 2008, 2048 }, { 9, 2009, 2048 }, { 9, 2010, 2048 }, { 10, 2011, 2048 }, { 9, 2012, 2048 }, { 10, 2013, 2048 }, { 10, 2014, 2048 }, { 11, 2015, 2048 }, 
02682    { 7, 2016, 2048 }, { 8, 2017, 2048 }, { 8, 2018, 2048 }, { 9, 2019, 2048 }, { 8, 2020, 2048 }, { 9, 2021, 2048 }, { 9, 2022, 2048 }, { 10, 2023, 2048 }, 
02683    { 8, 2024, 2048 }, { 9, 2025, 2048 }, { 9, 2026, 2048 }, { 10, 2027, 2048 }, { 9, 2028, 2048 }, { 10, 2029, 2048 }, { 10, 2030, 2048 }, { 11, 2031, 2048 }, 
02684    { 8, 2032, 2048 }, { 9, 2033, 2048 }, { 9, 2034, 2048 }, { 10, 2035, 2048 }, { 9, 2036, 2048 }, { 10, 2037, 2048 }, { 10, 2038, 2048 }, { 11, 2039, 2048 }, 
02685    { 9, 2040, 2048 }, { 10, 2041, 2048 }, { 10, 2042, 2048 }, { 11, 2043, 2048 }, { 10, 2044, 2048 }, { 11, 2045, 2048 }, { 11, 2046, 2048 }, { 12, 2047, 2048 }, 
02686 #endif
02687 #endif
02688 #endif
02689 #endif
02690 #endif
02691 #endif
02692 };
02693 
02694 /* find a hole and free as required, return -1 if no hole found */
02695 static int find_hole(void)
02696 {
02697    unsigned x;
02698    int      y, z;
02699    for (z = -1, y = INT_MAX, x = 0; x < FP_ENTRIES; x++) {
02700        if (fp_cache[x].lru_count < y && fp_cache[x].lock == 0) {
02701           z = x;
02702           y = fp_cache[x].lru_count;
02703        }
02704    }
02705 
02706    /* decrease all */
02707    for (x = 0; x < FP_ENTRIES; x++) {
02708       if (fp_cache[x].lru_count > 3) {
02709          --(fp_cache[x].lru_count);
02710       }
02711    }
02712 
02713    /* free entry z */
02714    if (z >= 0 && fp_cache[z].g) {
02715       mp_clear(&fp_cache[z].mu);
02716       ecc_del_point(fp_cache[z].g);
02717       fp_cache[z].g  = NULL;
02718       for (x = 0; x < (1U<<FP_LUT); x++) {
02719          ecc_del_point(fp_cache[z].LUT[x]);
02720          fp_cache[z].LUT[x] = NULL;
02721       }
02722       fp_cache[z].lru_count = 0;
02723    }
02724    return z;
02725 }
02726 
02727 /* determine if a base is already in the cache and if so, where */
02728 static int find_base(ecc_point* g)
02729 {
02730    int x;
02731    for (x = 0; x < FP_ENTRIES; x++) {
02732       if (fp_cache[x].g != NULL && 
02733           mp_cmp(&fp_cache[x].g->x, &g->x) == MP_EQ && 
02734           mp_cmp(&fp_cache[x].g->y, &g->y) == MP_EQ && 
02735           mp_cmp(&fp_cache[x].g->z, &g->z) == MP_EQ) {
02736          break;
02737       }
02738    }
02739    if (x == FP_ENTRIES) {
02740       x = -1;
02741    }
02742    return x;
02743 }
02744 
02745 /* add a new base to the cache */
02746 static int add_entry(int idx, ecc_point *g)
02747 {
02748    unsigned x, y;
02749 
02750    /* allocate base and LUT */
02751    fp_cache[idx].g = ecc_new_point();
02752    if (fp_cache[idx].g == NULL) {
02753       return GEN_MEM_ERR;
02754    }
02755 
02756    /* copy x and y */
02757    if ((mp_copy(&g->x, &fp_cache[idx].g->x) != MP_OKAY) ||
02758        (mp_copy(&g->y, &fp_cache[idx].g->y) != MP_OKAY) ||
02759        (mp_copy(&g->z, &fp_cache[idx].g->z) != MP_OKAY)) {
02760       ecc_del_point(fp_cache[idx].g);
02761       fp_cache[idx].g = NULL;
02762       return GEN_MEM_ERR;
02763    }              
02764 
02765    for (x = 0; x < (1U<<FP_LUT); x++) {
02766       fp_cache[idx].LUT[x] = ecc_new_point();
02767       if (fp_cache[idx].LUT[x] == NULL) {
02768          for (y = 0; y < x; y++) {
02769             ecc_del_point(fp_cache[idx].LUT[y]);
02770             fp_cache[idx].LUT[y] = NULL;
02771          }
02772          ecc_del_point(fp_cache[idx].g);
02773          fp_cache[idx].g         = NULL;
02774          fp_cache[idx].lru_count = 0;
02775          return GEN_MEM_ERR;
02776       }
02777    }
02778    
02779    fp_cache[idx].lru_count = 0;
02780 
02781    return MP_OKAY;
02782 }
02783 
02784 /* build the LUT by spacing the bits of the input by #modulus/FP_LUT bits apart 
02785  * 
02786  * The algorithm builds patterns in increasing bit order by first making all 
02787  * single bit input patterns, then all two bit input patterns and so on
02788  */
02789 static int build_lut(int idx, mp_int* modulus, mp_digit* mp, mp_int* mu)
02790 { 
02791    unsigned x, y, err, bitlen, lut_gap;
02792    mp_int tmp;
02793 
02794    if (mp_init(&tmp) != MP_OKAY)
02795        return GEN_MEM_ERR;
02796 
02797    /* sanity check to make sure lut_order table is of correct size,
02798       should compile out to a NOP if true */
02799    if ((sizeof(lut_orders) / sizeof(lut_orders[0])) < (1U<<FP_LUT)) {
02800        err = BAD_FUNC_ARG;
02801    }
02802    else {   
02803     /* get bitlen and round up to next multiple of FP_LUT */
02804     bitlen  = mp_unsigned_bin_size(modulus) << 3;
02805     x       = bitlen % FP_LUT;
02806     if (x) {
02807       bitlen += FP_LUT - x;
02808     }  
02809     lut_gap = bitlen / FP_LUT;
02810 
02811     /* init the mu */
02812     err = mp_init_copy(&fp_cache[idx].mu, mu);
02813    }
02814    
02815    /* copy base */
02816    if (err == MP_OKAY) {
02817      if ((mp_mulmod(&fp_cache[idx].g->x, mu, modulus,
02818                   &fp_cache[idx].LUT[1]->x) != MP_OKAY) || 
02819          (mp_mulmod(&fp_cache[idx].g->y, mu, modulus,
02820                   &fp_cache[idx].LUT[1]->y) != MP_OKAY) || 
02821          (mp_mulmod(&fp_cache[idx].g->z, mu, modulus,
02822                   &fp_cache[idx].LUT[1]->z) != MP_OKAY)) {
02823        err = MP_MULMOD_E; 
02824      }
02825    }
02826        
02827    /* make all single bit entries */
02828    for (x = 1; x < FP_LUT; x++) {
02829       if (err != MP_OKAY)
02830           break;
02831       if ((mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->x,
02832                    &fp_cache[idx].LUT[1<<x]->x) != MP_OKAY) || 
02833           (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->y,
02834                    &fp_cache[idx].LUT[1<<x]->y) != MP_OKAY) || 
02835           (mp_copy(&fp_cache[idx].LUT[1<<(x-1)]->z,
02836                    &fp_cache[idx].LUT[1<<x]->z) != MP_OKAY)){
02837           err = MP_INIT_E;
02838           break;
02839       } else {
02840           
02841          /* now double it bitlen/FP_LUT times */
02842          for (y = 0; y < lut_gap; y++) {
02843              if ((err = ecc_projective_dbl_point(fp_cache[idx].LUT[1<<x],
02844                             fp_cache[idx].LUT[1<<x], modulus, mp)) != MP_OKAY) {
02845                  break;
02846              }
02847          }
02848      }
02849   }
02850       
02851    /* now make all entries in increase order of hamming weight */
02852    for (x = 2; x <= FP_LUT; x++) {
02853        if (err != MP_OKAY)
02854            break;
02855        for (y = 0; y < (1UL<<FP_LUT); y++) {
02856            if (err != MP_OKAY)
02857              break;
02858            if (lut_orders[y].ham != (int)x) continue;
02859                      
02860            /* perform the add */
02861            if ((err = ecc_projective_add_point(
02862                            fp_cache[idx].LUT[lut_orders[y].terma],
02863                            fp_cache[idx].LUT[lut_orders[y].termb],
02864                            fp_cache[idx].LUT[y], modulus, mp)) != MP_OKAY) {
02865               break;
02866            }
02867        }
02868    }
02869       
02870    /* now map all entries back to affine space to make point addition faster */
02871    for (x = 1; x < (1UL<<FP_LUT); x++) {
02872        if (err != MP_OKAY)
02873            break;
02874 
02875        /* convert z to normal from montgomery */
02876        err = mp_montgomery_reduce(&fp_cache[idx].LUT[x]->z, modulus, *mp);
02877  
02878        /* invert it */
02879        if (err == MP_OKAY)
02880          err = mp_invmod(&fp_cache[idx].LUT[x]->z, modulus,
02881                          &fp_cache[idx].LUT[x]->z);
02882 
02883        if (err == MP_OKAY)
02884          /* now square it */
02885          err = mp_sqrmod(&fp_cache[idx].LUT[x]->z, modulus, &tmp);
02886        
02887        if (err == MP_OKAY)
02888          /* fix x */
02889          err = mp_mulmod(&fp_cache[idx].LUT[x]->x, &tmp, modulus,
02890                          &fp_cache[idx].LUT[x]->x);
02891 
02892        if (err == MP_OKAY)
02893          /* get 1/z^3 */
02894          err = mp_mulmod(&tmp, &fp_cache[idx].LUT[x]->z, modulus, &tmp);
02895 
02896        if (err == MP_OKAY)
02897          /* fix y */
02898          err = mp_mulmod(&fp_cache[idx].LUT[x]->y, &tmp, modulus,
02899                          &fp_cache[idx].LUT[x]->y);
02900 
02901        if (err == MP_OKAY)
02902          /* free z */
02903          mp_clear(&fp_cache[idx].LUT[x]->z);
02904    }
02905    mp_clear(&tmp);
02906 
02907    if (err == MP_OKAY)
02908      return MP_OKAY;
02909 
02910    /* err cleanup */
02911    for (y = 0; y < (1U<<FP_LUT); y++) {
02912       ecc_del_point(fp_cache[idx].LUT[y]);
02913       fp_cache[idx].LUT[y] = NULL;
02914    }
02915    ecc_del_point(fp_cache[idx].g);
02916    fp_cache[idx].g         = NULL;
02917    fp_cache[idx].lru_count = 0;
02918    mp_clear(&fp_cache[idx].mu);
02919    mp_clear(&tmp);
02920 
02921    return err;
02922 }
02923 
02924 /* perform a fixed point ECC mulmod */
02925 static int accel_fp_mul(int idx, mp_int* k, ecc_point *R, mp_int* modulus,
02926                         mp_digit* mp, int map)
02927 {
02928    unsigned char kb[128];
02929    int      x;
02930    unsigned y, z, err, bitlen, bitpos, lut_gap, first;
02931    mp_int   tk;
02932 
02933    if (mp_init(&tk) != MP_OKAY)
02934        return MP_INIT_E;
02935 
02936    /* if it's smaller than modulus we fine */
02937    if (mp_unsigned_bin_size(k) > mp_unsigned_bin_size(modulus)) {
02938       mp_int order;
02939       if (mp_init(&order) != MP_OKAY) {
02940         mp_clear(&tk);
02941         return MP_INIT_E;
02942       }
02943 
02944       /* find order */
02945       y = mp_unsigned_bin_size(modulus);
02946       for (x = 0; ecc_sets[x].size; x++) {
02947          if (y <= (unsigned)ecc_sets[x].size) break;
02948       }
02949    
02950       /* back off if we are on the 521 bit curve */
02951       if (y == 66) --x;
02952       
02953       if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
02954          mp_clear(&order);
02955          mp_clear(&tk);
02956          return err;
02957       }
02958 
02959       /* k must be less than modulus */
02960       if (mp_cmp(k, &order) != MP_LT) {
02961          if ((err = mp_mod(k, &order, &tk)) != MP_OKAY) {
02962             mp_clear(&tk);
02963             mp_clear(&order);
02964             return err;
02965          }
02966       } else {
02967          mp_copy(k, &tk);
02968       }
02969       mp_clear(&order);
02970    } else {
02971       mp_copy(k, &tk);
02972    }       
02973    
02974    /* get bitlen and round up to next multiple of FP_LUT */
02975    bitlen  = mp_unsigned_bin_size(modulus) << 3;
02976    x       = bitlen % FP_LUT;
02977    if (x) {
02978       bitlen += FP_LUT - x;
02979    }  
02980    lut_gap = bitlen / FP_LUT;
02981         
02982    /* get the k value */
02983    if (mp_unsigned_bin_size(&tk) > (int)(sizeof(kb) - 2)) {
02984       mp_clear(&tk);
02985       return BUFFER_E;
02986    }
02987    
02988    /* store k */
02989    XMEMSET(kb, 0, sizeof(kb));
02990    if ((err = mp_to_unsigned_bin(&tk, kb)) != MP_OKAY) {
02991       mp_clear(&tk);
02992       return err;
02993    }
02994    
02995    /* let's reverse kb so it's little endian */
02996    x = 0;
02997    y = mp_unsigned_bin_size(&tk) - 1;
02998    mp_clear(&tk);
02999 
03000    while ((unsigned)x < y) {
03001       z = kb[x]; kb[x] = kb[y]; kb[y] = z;
03002       ++x; --y;
03003    }      
03004    
03005    /* at this point we can start, yipee */
03006    first = 1;
03007    for (x = lut_gap-1; x >= 0; x--) {
03008        /* extract FP_LUT bits from kb spread out by lut_gap bits and offset
03009           by x bits from the start */
03010        bitpos = x;
03011        for (y = z = 0; y < FP_LUT; y++) {
03012           z |= ((kb[bitpos>>3] >> (bitpos&7)) & 1) << y;
03013           bitpos += lut_gap;  /* it's y*lut_gap + x, but here we can avoid
03014                                  the mult in each loop */
03015        }
03016               
03017        /* double if not first */
03018        if (!first) {
03019           if ((err = ecc_projective_dbl_point(R, R, modulus, mp)) != MP_OKAY) {
03020              return err;
03021           }
03022        }
03023        
03024        /* add if not first, otherwise copy */          
03025        if (!first && z) {
03026           if ((err = ecc_projective_add_point(R, fp_cache[idx].LUT[z], R,
03027                                               modulus, mp)) != MP_OKAY) {
03028              return err;
03029           }
03030        } else if (z) {
03031           if ((mp_copy(&fp_cache[idx].LUT[z]->x, &R->x) != MP_OKAY) || 
03032               (mp_copy(&fp_cache[idx].LUT[z]->y, &R->y) != MP_OKAY) || 
03033               (mp_copy(&fp_cache[idx].mu,        &R->z) != MP_OKAY)) {
03034               return GEN_MEM_ERR;
03035           }
03036               first = 0;              
03037        }
03038    }     
03039    z = 0;
03040    XMEMSET(kb, 0, sizeof(kb));
03041    /* map R back from projective space */
03042    if (map) {
03043       err = ecc_map(R, modulus, mp);
03044    } else {
03045       err = MP_OKAY;
03046    }
03047 
03048    return err;
03049 }
03050 
03051 #ifdef ECC_SHAMIR
03052 /* perform a fixed point ECC mulmod */
03053 static int accel_fp_mul2add(int idx1, int idx2, 
03054                             mp_int* kA, mp_int* kB,
03055                             ecc_point *R, mp_int* modulus, mp_digit* mp)
03056 {
03057    unsigned char kb[2][128];
03058    int      x;
03059    unsigned y, z, err, bitlen, bitpos, lut_gap, first, zA, zB;
03060    mp_int tka;
03061    mp_int tkb;
03062    mp_int order;
03063 
03064    if (mp_init_multi(&tka, &tkb, 0, 0, 0, 0) != MP_OKAY)
03065        return MP_INIT_E;
03066 
03067    /* if it's smaller than modulus we fine */
03068    if (mp_unsigned_bin_size(kA) > mp_unsigned_bin_size(modulus)) {
03069       /* find order */
03070       y = mp_unsigned_bin_size(modulus);
03071       for (x = 0; ecc_sets[x].size; x++) {
03072          if (y <= (unsigned)ecc_sets[x].size) break;
03073       }
03074    
03075       /* back off if we are on the 521 bit curve */
03076       if (y == 66) --x;
03077       
03078       if ((err = mp_init(&order)) != MP_OKAY) {
03079          mp_clear(&tkb);
03080          mp_clear(&tka);
03081          return err;
03082       }      
03083       if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
03084          mp_clear(&tkb);
03085          mp_clear(&tka);
03086          mp_clear(&order);
03087          return err;
03088       }
03089 
03090       /* kA must be less than modulus */
03091       if (mp_cmp(kA, &order) != MP_LT) {
03092          if ((err = mp_mod(kA, &order, &tka)) != MP_OKAY) {
03093             mp_clear(&tkb);
03094             mp_clear(&tka);
03095             mp_clear(&order);
03096             return err;
03097          }
03098       } else {
03099          mp_copy(kA, &tka);
03100       }
03101       mp_clear(&order);
03102    } else {
03103       mp_copy(kA, &tka);
03104    }       
03105 
03106    /* if it's smaller than modulus we fine */
03107    if (mp_unsigned_bin_size(kB) > mp_unsigned_bin_size(modulus)) {
03108       /* find order */
03109       y = mp_unsigned_bin_size(modulus);
03110       for (x = 0; ecc_sets[x].size; x++) {
03111          if (y <= (unsigned)ecc_sets[x].size) break;
03112       }
03113    
03114       /* back off if we are on the 521 bit curve */
03115       if (y == 66) --x;
03116       
03117       if ((err = mp_init(&order)) != MP_OKAY) {
03118          mp_clear(&tkb);
03119          mp_clear(&tka);
03120          return err;
03121       }      
03122       if ((err = mp_read_radix(&order, ecc_sets[x].order, 16)) != MP_OKAY) {
03123          mp_clear(&tkb);
03124          mp_clear(&tka);
03125          mp_clear(&order);
03126          return err;
03127       }
03128 
03129       /* kB must be less than modulus */
03130       if (mp_cmp(kB, &order) != MP_LT) {
03131          if ((err = mp_mod(kB, &order, &tkb)) != MP_OKAY) {
03132             mp_clear(&tkb);
03133             mp_clear(&tka);
03134             mp_clear(&order);
03135             return err;
03136          }
03137       } else {
03138          mp_copy(kB, &tkb);
03139       }
03140       mp_clear(&order);
03141    } else {
03142       mp_copy(kB, &tkb);
03143    }     
03144 
03145    /* get bitlen and round up to next multiple of FP_LUT */
03146    bitlen  = mp_unsigned_bin_size(modulus) << 3;
03147    x       = bitlen % FP_LUT;
03148    if (x) {
03149       bitlen += FP_LUT - x;
03150    }  
03151    lut_gap = bitlen / FP_LUT;
03152         
03153    /* get the k value */
03154    if ((mp_unsigned_bin_size(&tka) > (int)(sizeof(kb[0]) - 2)) ||
03155        (mp_unsigned_bin_size(&tkb) > (int)(sizeof(kb[0]) - 2))  ) {
03156       mp_clear(&tka);
03157       mp_clear(&tkb);
03158       return BUFFER_E;
03159    }
03160    
03161    /* store k */
03162    XMEMSET(kb, 0, sizeof(kb));
03163    if ((err = mp_to_unsigned_bin(&tka, kb[0])) != MP_OKAY) {
03164       mp_clear(&tka);
03165       mp_clear(&tkb);
03166       return err;
03167    }
03168    
03169    /* let's reverse kb so it's little endian */
03170    x = 0;
03171    y = mp_unsigned_bin_size(&tka) - 1;
03172    mp_clear(&tka);
03173    while ((unsigned)x < y) {
03174       z = kb[0][x]; kb[0][x] = kb[0][y]; kb[0][y] = z;
03175       ++x; --y;
03176    }      
03177    
03178    /* store b */
03179    if ((err = mp_to_unsigned_bin(&tkb, kb[1])) != MP_OKAY) {
03180       mp_clear(&tkb);
03181       return err;
03182    }
03183 
03184    x = 0;
03185    y = mp_unsigned_bin_size(&tkb) - 1;
03186    mp_clear(&tkb);
03187    while ((unsigned)x < y) {
03188       z = kb[1][x]; kb[1][x] = kb[1][y]; kb[1][y] = z;
03189       ++x; --y;
03190    }      
03191 
03192    /* at this point we can start, yipee */
03193    first = 1;
03194    for (x = lut_gap-1; x >= 0; x--) {
03195        /* extract FP_LUT bits from kb spread out by lut_gap bits and
03196           offset by x bits from the start */
03197        bitpos = x;
03198        for (y = zA = zB = 0; y < FP_LUT; y++) {
03199           zA |= ((kb[0][bitpos>>3] >> (bitpos&7)) & 1) << y;
03200           zB |= ((kb[1][bitpos>>3] >> (bitpos&7)) & 1) << y;
03201           bitpos += lut_gap;    /* it's y*lut_gap + x, but here we can avoid
03202                                    the mult in each loop */
03203        }
03204               
03205        /* double if not first */
03206        if (!first) {
03207           if ((err = ecc_projective_dbl_point(R, R, modulus, mp)) != MP_OKAY) {
03208              return err;
03209           }
03210        }
03211        
03212        /* add if not first, otherwise copy */          
03213        if (!first) {
03214           if (zA) {
03215              if ((err = ecc_projective_add_point(R, fp_cache[idx1].LUT[zA],
03216                                                  R, modulus, mp)) != MP_OKAY) {
03217                 return err;
03218              }
03219           }
03220           if (zB) {
03221              if ((err = ecc_projective_add_point(R, fp_cache[idx2].LUT[zB],
03222                                                  R, modulus, mp)) != MP_OKAY) {
03223                 return err;
03224              }
03225           }
03226        } else {
03227           if (zA) {
03228               if ((mp_copy(&fp_cache[idx1].LUT[zA]->x, &R->x) != MP_OKAY) || 
03229                  (mp_copy(&fp_cache[idx1].LUT[zA]->y, &R->y) != MP_OKAY) || 
03230                  (mp_copy(&fp_cache[idx1].mu,        &R->z) != MP_OKAY)) {
03231                   return GEN_MEM_ERR;
03232               }
03233                  first = 0;              
03234           }
03235           if (zB && first == 0) {
03236              if (zB) {
03237                 if ((err = ecc_projective_add_point(R, fp_cache[idx2].LUT[zB],
03238                                                    R, modulus, mp)) != MP_OKAY){
03239                    return err;
03240                 }
03241              }
03242           } else if (zB && first == 1) {
03243               if ((mp_copy(&fp_cache[idx2].LUT[zB]->x, &R->x) != MP_OKAY) || 
03244                  (mp_copy(&fp_cache[idx2].LUT[zB]->y, &R->y) != MP_OKAY) || 
03245                  (mp_copy(&fp_cache[idx2].mu,        &R->z) != MP_OKAY)) {
03246                   return GEN_MEM_ERR;
03247               }
03248                  first = 0;              
03249           }
03250        }
03251    }     
03252    XMEMSET(kb, 0, sizeof(kb));
03253 
03254    return ecc_map(R, modulus, mp);
03255 }
03256 
03257 /** ECC Fixed Point mulmod global
03258   Computes kA*A + kB*B = C using Shamir's Trick
03259   A        First point to multiply
03260   kA       What to multiple A by
03261   B        Second point to multiply
03262   kB       What to multiple B by
03263   C        [out] Destination point (can overlap with A or B)
03264   modulus  Modulus for curve 
03265   return MP_OKAY on success
03266 */ 
03267 int ecc_mul2add(ecc_point* A, mp_int* kA,
03268                 ecc_point* B, mp_int* kB,
03269                 ecc_point* C, mp_int* modulus)
03270 {
03271    int  idx1 = -1, idx2 = -1, err = MP_OKAY, mpInit = 0;
03272    mp_digit mp;
03273    mp_int   mu;
03274   
03275    err = mp_init(&mu);
03276    if (err != MP_OKAY)
03277        return err;
03278 
03279 #ifndef HAVE_THREAD_LS
03280    if (initMutex == 0) {
03281         InitMutex(&ecc_fp_lock);
03282         initMutex = 1;
03283    }
03284    if (LockMutex(&ecc_fp_lock) != 0)
03285       return BAD_MUTEX_E;
03286 #endif /* HAVE_THREAD_LS */
03287 
03288       /* find point */
03289       idx1 = find_base(A);
03290 
03291       /* no entry? */
03292       if (idx1 == -1) {
03293          /* find hole and add it */
03294          if ((idx1 = find_hole()) >= 0) {
03295             err = add_entry(idx1, A);
03296          }
03297       }
03298       if (err == MP_OKAY && idx1 != -1) {
03299          /* increment LRU */
03300          ++(fp_cache[idx1].lru_count);
03301       }
03302 
03303       if (err == MP_OKAY)
03304         /* find point */
03305         idx2 = find_base(B);
03306 
03307       if (err == MP_OKAY) {
03308         /* no entry? */
03309         if (idx2 == -1) {
03310            /* find hole and add it */
03311            if ((idx2 = find_hole()) >= 0)
03312               err = add_entry(idx2, B);
03313          }
03314       }
03315 
03316       if (err == MP_OKAY && idx2 != -1) {
03317          /* increment LRU */
03318          ++(fp_cache[idx2].lru_count);
03319       }
03320 
03321       if (err == MP_OKAY) {
03322         /* if it's 2 build the LUT, if it's higher just use the LUT */
03323         if (idx1 >= 0 && fp_cache[idx1].lru_count == 2) {
03324            /* compute mp */
03325            err = mp_montgomery_setup(modulus, &mp);
03326 
03327            if (err == MP_OKAY) {
03328              mpInit = 1;
03329              err = mp_montgomery_calc_normalization(&mu, modulus);
03330            }
03331                  
03332            if (err == MP_OKAY)
03333              /* build the LUT */
03334                err = build_lut(idx1, modulus, &mp, &mu);
03335         }
03336       }
03337 
03338       if (err == MP_OKAY) {
03339         /* if it's 2 build the LUT, if it's higher just use the LUT */
03340         if (idx2 >= 0 && fp_cache[idx2].lru_count == 2) {
03341            if (mpInit == 0) {
03342                 /* compute mp */
03343                 err = mp_montgomery_setup(modulus, &mp);
03344                 if (err == MP_OKAY) {
03345                     mpInit = 1;
03346                     err = mp_montgomery_calc_normalization(&mu, modulus);
03347                 }
03348             }
03349                  
03350             if (err == MP_OKAY) 
03351             /* build the LUT */
03352               err = build_lut(idx2, modulus, &mp, &mu);
03353         }
03354       }
03355 
03356 
03357       if (err == MP_OKAY) {
03358         if (idx1 >=0 && idx2 >= 0 && fp_cache[idx1].lru_count >= 2 &&
03359                                      fp_cache[idx2].lru_count >= 2) {
03360            if (mpInit == 0) {
03361               /* compute mp */
03362               err = mp_montgomery_setup(modulus, &mp);
03363            }
03364            if (err == MP_OKAY)
03365              err = accel_fp_mul2add(idx1, idx2, kA, kB, C, modulus, &mp);
03366         } else {
03367            err = normal_ecc_mul2add(A, kA, B, kB, C, modulus);
03368         }
03369     }
03370 
03371 #ifndef HAVE_THREAD_LS
03372     UnLockMutex(&ecc_fp_lock);
03373 #endif /* HAVE_THREAD_LS */
03374     mp_clear(&mu);
03375 
03376     return err;
03377 }
03378 #endif
03379 
03380 /** ECC Fixed Point mulmod global
03381     k        The multiplicand
03382     G        Base point to multiply
03383     R        [out] Destination of product
03384     modulus  The modulus for the curve
03385     map      [boolean] If non-zero maps the point back to affine co-ordinates,
03386              otherwise it's left in jacobian-montgomery form
03387     return MP_OKAY if successful
03388 */   
03389 int ecc_mulmod(mp_int* k, ecc_point *G, ecc_point *R, mp_int* modulus,
03390                int map)
03391 {
03392    int   idx, err = MP_OKAY;
03393    mp_digit mp;
03394    mp_int   mu;
03395    int      mpSetup = 0;
03396 
03397    if (mp_init(&mu) != MP_OKAY)
03398        return MP_INIT_E;
03399    
03400 #ifndef HAVE_THREAD_LS
03401    if (initMutex == 0) {
03402         InitMutex(&ecc_fp_lock);
03403         initMutex = 1;
03404    }
03405    
03406    if (LockMutex(&ecc_fp_lock) != 0)
03407       return BAD_MUTEX_E;
03408 #endif /* HAVE_THREAD_LS */
03409 
03410       /* find point */
03411       idx = find_base(G);
03412 
03413       /* no entry? */
03414       if (idx == -1) {
03415          /* find hole and add it */
03416          idx = find_hole();
03417 
03418          if (idx >= 0)
03419             err = add_entry(idx, G);
03420       }
03421       if (err == MP_OKAY && idx != -1) {
03422          /* increment LRU */
03423          ++(fp_cache[idx].lru_count);
03424       }
03425 
03426 
03427       if (err == MP_OKAY) { 
03428         /* if it's 2 build the LUT, if it's higher just use the LUT */
03429         if (idx >= 0 && fp_cache[idx].lru_count == 2) {
03430            /* compute mp */
03431            err = mp_montgomery_setup(modulus, &mp);
03432 
03433            if (err == MP_OKAY) {
03434              /* compute mu */
03435              mpSetup = 1;
03436              err = mp_montgomery_calc_normalization(&mu, modulus);
03437            }
03438                  
03439            if (err == MP_OKAY) 
03440              /* build the LUT */
03441              err = build_lut(idx, modulus, &mp, &mu);
03442         }
03443       }
03444 
03445       if (err == MP_OKAY) { 
03446         if (idx >= 0 && fp_cache[idx].lru_count >= 2) {
03447            if (mpSetup == 0) {
03448               /* compute mp */
03449               err = mp_montgomery_setup(modulus, &mp);
03450            }
03451            if (err == MP_OKAY)
03452              err = accel_fp_mul(idx, k, R, modulus, &mp, map);
03453         } else {
03454            err = normal_ecc_mulmod(k, G, R, modulus, map);
03455         }
03456      }
03457 
03458 #ifndef HAVE_THREAD_LS
03459     UnLockMutex(&ecc_fp_lock);
03460 #endif /* HAVE_THREAD_LS */
03461     mp_clear(&mu);
03462 
03463     return err;
03464 }
03465 
03466 /* helper function for freeing the cache ...
03467    must be called with the cache mutex locked */
03468 static void ecc_fp_free_cache(void)
03469 {
03470    unsigned x, y;
03471    for (x = 0; x < FP_ENTRIES; x++) {
03472       if (fp_cache[x].g != NULL) {
03473          for (y = 0; y < (1U<<FP_LUT); y++) {
03474             ecc_del_point(fp_cache[x].LUT[y]);
03475             fp_cache[x].LUT[y] = NULL;
03476          }
03477          ecc_del_point(fp_cache[x].g);
03478          fp_cache[x].g         = NULL;
03479          mp_clear(&fp_cache[x].mu);
03480          fp_cache[x].lru_count = 0;
03481          fp_cache[x].lock = 0;
03482       }         
03483    }
03484 }         
03485 
03486 /** Free the Fixed Point cache */
03487 void ecc_fp_free(void)
03488 {
03489 #ifndef HAVE_THREAD_LS
03490    if (initMutex == 0) {
03491         InitMutex(&ecc_fp_lock);
03492         initMutex = 1;
03493    }
03494    
03495    if (LockMutex(&ecc_fp_lock) == 0) {
03496 #endif /* HAVE_THREAD_LS */
03497 
03498        ecc_fp_free_cache();
03499 
03500 #ifndef HAVE_THREAD_LS
03501        UnLockMutex(&ecc_fp_lock);
03502        FreeMutex(&ecc_fp_lock);
03503        initMutex = 0;
03504    }
03505 #endif /* HAVE_THREAD_LS */
03506 }
03507 
03508 
03509 #endif /* FP_ECC */
03510 
03511 #ifdef HAVE_ECC_ENCRYPT
03512 
03513 
03514 enum ecCliState {
03515     ecCLI_INIT      = 1,    
03516     ecCLI_SALT_GET  = 2,    
03517     ecCLI_SALT_SET  = 3,    
03518     ecCLI_SENT_REQ  = 4,    
03519     ecCLI_RECV_RESP = 5,    
03520     ecCLI_BAD_STATE = 99    
03521 };
03522 
03523 enum ecSrvState {
03524     ecSRV_INIT      = 1,    
03525     ecSRV_SALT_GET  = 2,    
03526     ecSRV_SALT_SET  = 3,    
03527     ecSRV_RECV_REQ  = 4,    
03528     ecSRV_SENT_RESP = 5,    
03529     ecSRV_BAD_STATE = 99    
03530 };
03531 
03532 
03533 struct ecEncCtx {
03534     byte*     kdfSalt;     /* optional salt for kdf */
03535     byte*     kdfInfo;     /* optional info for kdf */
03536     byte*     macSalt;     /* optional salt for mac */
03537     word32    kdfSaltSz;   /* size of kdfSalt */
03538     word32    kdfInfoSz;   /* size of kdfInfo */
03539     word32    macSaltSz;   /* size of macSalt */
03540     byte      clientSalt[EXCHANGE_SALT_SZ];  /* for msg exchange */
03541     byte      serverSalt[EXCHANGE_SALT_SZ];  /* for msg exchange */
03542     byte      encAlgo;     /* which encryption type */
03543     byte      kdfAlgo;     /* which key derivation function type */
03544     byte      macAlgo;     /* which mac function type */
03545     byte      protocol;    /* are we REQ_RESP client or server ? */
03546     byte      cliSt;       /* protocol state, for sanity checks */
03547     byte      srvSt;       /* protocol state, for sanity checks */
03548 };
03549 
03550 
03551 const byte* ecc_ctx_get_own_salt(ecEncCtx* ctx)
03552 {
03553     if (ctx == NULL || ctx->protocol == 0)
03554         return NULL;
03555 
03556     if (ctx->protocol == REQ_RESP_CLIENT) {
03557         if (ctx->cliSt == ecCLI_INIT) {
03558             ctx->cliSt =  ecCLI_SALT_GET;
03559             return ctx->clientSalt;
03560         }
03561         else {
03562             ctx->cliSt = ecCLI_BAD_STATE;
03563             return NULL;
03564         }
03565     }
03566     else if (ctx->protocol == REQ_RESP_SERVER) {
03567         if (ctx->srvSt == ecSRV_INIT) {
03568             ctx->srvSt =  ecSRV_SALT_GET;
03569             return ctx->serverSalt;
03570         }
03571         else {
03572             ctx->srvSt = ecSRV_BAD_STATE;
03573             return NULL;
03574         }
03575     }
03576 
03577     return NULL;
03578 }
03579 
03580 
03581 static const char* exchange_info = "Secure Message Exchange";
03582 
03583 int ecc_ctx_set_peer_salt(ecEncCtx* ctx, const byte* salt)
03584 {
03585     byte tmp[EXCHANGE_SALT_SZ/2];
03586     int  halfSz = EXCHANGE_SALT_SZ/2;
03587 
03588     if (ctx == NULL || ctx->protocol == 0 || salt == NULL)
03589         return BAD_FUNC_ARG;
03590 
03591     if (ctx->protocol == REQ_RESP_CLIENT) {
03592         XMEMCPY(ctx->serverSalt, salt, EXCHANGE_SALT_SZ);
03593         if (ctx->cliSt == ecCLI_SALT_GET)
03594             ctx->cliSt =  ecCLI_SALT_SET;
03595         else {
03596             ctx->cliSt =  ecCLI_BAD_STATE;
03597             return BAD_ENC_STATE_E;
03598         }
03599     }
03600     else {
03601         XMEMCPY(ctx->clientSalt, salt, EXCHANGE_SALT_SZ);
03602         if (ctx->srvSt == ecSRV_SALT_GET)
03603             ctx->srvSt =  ecSRV_SALT_SET;
03604         else {
03605             ctx->srvSt =  ecSRV_BAD_STATE;
03606             return BAD_ENC_STATE_E;
03607         }
03608     }
03609 
03610     /* mix half and half */
03611     /* tmp stores 2nd half of client before overwrite */
03612     XMEMCPY(tmp, ctx->clientSalt + halfSz, halfSz);
03613     XMEMCPY(ctx->clientSalt + halfSz, ctx->serverSalt, halfSz);
03614     XMEMCPY(ctx->serverSalt, tmp, halfSz);
03615 
03616     ctx->kdfSalt   = ctx->clientSalt;
03617     ctx->kdfSaltSz = EXCHANGE_SALT_SZ;
03618 
03619     ctx->macSalt   = ctx->serverSalt;
03620     ctx->macSaltSz = EXCHANGE_SALT_SZ;
03621 
03622     ctx->kdfInfo   = (byte*)exchange_info;
03623     ctx->kdfInfoSz = EXCHANGE_INFO_SZ;
03624 
03625     return 0;
03626 }
03627 
03628 
03629 static int ecc_ctx_set_salt(ecEncCtx* ctx, int flags, RNG* rng)
03630 {
03631     byte* saltBuffer = NULL;
03632 
03633     if (ctx == NULL || rng == NULL || flags == 0) 
03634         return BAD_FUNC_ARG;
03635 
03636     saltBuffer = (flags == REQ_RESP_CLIENT) ? ctx->clientSalt : ctx->serverSalt;
03637     RNG_GenerateBlock(rng, saltBuffer, EXCHANGE_SALT_SZ);
03638 
03639     return 0;
03640 }
03641 
03642 
03643 static void ecc_ctx_init(ecEncCtx* ctx, int flags)
03644 {
03645     if (ctx) {
03646         XMEMSET(ctx, 0, sizeof(ecEncCtx));
03647 
03648         ctx->encAlgo  = ecAES_128_CBC;
03649         ctx->kdfAlgo  = ecHKDF_SHA256;
03650         ctx->macAlgo  = ecHMAC_SHA256;
03651         ctx->protocol = (byte)flags;
03652 
03653         if (flags == REQ_RESP_CLIENT)
03654             ctx->cliSt = ecCLI_INIT;
03655         if (flags == REQ_RESP_SERVER)
03656             ctx->srvSt = ecSRV_INIT;
03657     }
03658 }
03659 
03660 
03661 /* allow ecc context reset so user doesn't have to init/free for resue */
03662 int ecc_ctx_reset(ecEncCtx* ctx, RNG* rng)
03663 {
03664     if (ctx == NULL || rng == NULL)
03665         return BAD_FUNC_ARG;
03666 
03667     ecc_ctx_init(ctx, ctx->protocol);
03668     return ecc_ctx_set_salt(ctx, ctx->protocol, rng);
03669 }
03670 
03671 
03672 /* alloc/init and set defaults, return new Context  */
03673 ecEncCtx* ecc_ctx_new(int flags, RNG* rng)
03674 {
03675     int       ret = 0;
03676     ecEncCtx* ctx = (ecEncCtx*)XMALLOC(sizeof(ecEncCtx), 0, DYNAMIC_TYPE_ECC);
03677 
03678     if (ctx)
03679         ctx->protocol = (byte)flags;
03680 
03681     ret = ecc_ctx_reset(ctx, rng);
03682     if (ret != 0) {
03683         ecc_ctx_free(ctx);
03684         ctx = NULL;
03685     }
03686 
03687     return ctx;
03688 }
03689 
03690 
03691 /* free any resources, clear any keys */
03692 void ecc_ctx_free(ecEncCtx* ctx)
03693 {
03694     if (ctx) {
03695         XMEMSET(ctx, 0, sizeof(ecEncCtx));
03696         XFREE(ctx, 0, DYNAMIC_TYPE_ECC);
03697     }
03698 }
03699 
03700 
03701 static int ecc_get_key_sizes(ecEncCtx* ctx, int* encKeySz, int* ivSz,
03702                              int* keysLen, word32* digestSz, word32* blockSz)
03703 {
03704     if (ctx) {
03705         switch (ctx->encAlgo) {
03706             case ecAES_128_CBC:
03707                 *encKeySz = KEY_SIZE_128;
03708                 *ivSz     = IV_SIZE_64;
03709                 *blockSz  = AES_BLOCK_SIZE;
03710                 break;
03711             default:
03712                 return BAD_FUNC_ARG;
03713         }
03714 
03715         switch (ctx->macAlgo) {
03716             case ecHMAC_SHA256:
03717                 *digestSz = SHA256_DIGEST_SIZE;
03718                 break;
03719             default:
03720                 return BAD_FUNC_ARG;
03721         }
03722     } else
03723         return BAD_FUNC_ARG;
03724 
03725     *keysLen  = *encKeySz + *ivSz + *digestSz;
03726 
03727     return 0;
03728 }
03729 
03730 
03731 /* ecc encrypt with shared secret run through kdf
03732    ctx holds non default algos and inputs
03733    msgSz should be the right size for encAlgo, i.e., already padded 
03734    return 0 on success */
03735 int ecc_encrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg,
03736                 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx)
03737 {
03738     int          ret;
03739     word32       blockSz;
03740     word32       digestSz;
03741     ecEncCtx     localCtx;
03742     byte         sharedSecret[ECC_MAXSIZE];  /* 521 max size */
03743     byte         keys[ECC_BUFSIZE];         /* max size */
03744     word32       sharedSz = sizeof(sharedSecret);
03745     int          keysLen;
03746     int          encKeySz;
03747     int          ivSz;
03748     int          offset = 0;         /* keys offset if doing msg exchange */
03749     byte*        encKey;
03750     byte*        encIv;
03751     byte*        macKey;
03752 
03753     if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL ||
03754                            outSz  == NULL)
03755         return BAD_FUNC_ARG;
03756 
03757     if (ctx == NULL) {  /* use defaults */
03758         ecc_ctx_init(&localCtx, 0);
03759         ctx = &localCtx;  
03760     }
03761         
03762     ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz,
03763                             &blockSz);
03764     if (ret != 0)
03765         return ret;
03766 
03767     if (ctx->protocol == REQ_RESP_SERVER) {
03768         offset = keysLen;
03769         keysLen *= 2;
03770 
03771         if (ctx->srvSt != ecSRV_RECV_REQ)
03772             return BAD_ENC_STATE_E;
03773 
03774         ctx->srvSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */
03775     }
03776     else if (ctx->protocol == REQ_RESP_CLIENT) {
03777         if (ctx->cliSt != ecCLI_SALT_SET)
03778             return BAD_ENC_STATE_E;
03779 
03780         ctx->cliSt = ecCLI_SENT_REQ; /* only do this once */
03781     }
03782         
03783     if (keysLen > (int)sizeof(keys))
03784         return BUFFER_E;
03785         
03786     if ( (msgSz%blockSz) != 0)
03787         return BAD_PADDING_E;
03788 
03789     if (*outSz < (msgSz + digestSz))
03790         return BUFFER_E;
03791 
03792     ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz); 
03793     if (ret != 0)
03794         return ret;
03795 
03796     switch (ctx->kdfAlgo) {
03797         case ecHKDF_SHA256 :
03798                 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt,
03799                            ctx->kdfSaltSz, ctx->kdfInfo,
03800                            ctx->kdfInfoSz, keys, keysLen);
03801                 if (ret != 0)
03802                     return ret;
03803             break;
03804 
03805         default:
03806             return BAD_FUNC_ARG;
03807     }
03808 
03809     encKey = keys + offset;
03810     encIv  = encKey + encKeySz;
03811     macKey = encKey + encKeySz + ivSz;
03812 
03813     switch (ctx->encAlgo) {
03814         case ecAES_128_CBC:
03815             {
03816                 Aes aes;
03817                 ret = AesSetKey(&aes, encKey,KEY_SIZE_128,encIv,AES_ENCRYPTION);
03818                 if (ret != 0)
03819                     return ret;
03820                 ret = AesCbcEncrypt(&aes, out, msg, msgSz);
03821                 if (ret != 0)
03822                     return ret;
03823             }
03824             break;
03825 
03826         default:
03827             return BAD_FUNC_ARG;
03828     }
03829 
03830     switch (ctx->macAlgo) {
03831         case ecHMAC_SHA256:
03832             {
03833                 Hmac hmac;
03834                 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE);
03835                 if (ret != 0)
03836                     return ret;
03837                 HmacUpdate(&hmac, out, msgSz);
03838                 HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz);
03839                 HmacFinal(&hmac, out+msgSz);
03840             }
03841             break;
03842 
03843         default:
03844             return BAD_FUNC_ARG;
03845     }
03846 
03847     *outSz = msgSz + digestSz;
03848 
03849     return 0;
03850 }
03851 
03852 
03853 /* ecc decrypt with shared secret run through kdf
03854    ctx holds non default algos and inputs
03855    return 0 on success */
03856 int ecc_decrypt(ecc_key* privKey, ecc_key* pubKey, const byte* msg,
03857                 word32 msgSz, byte* out, word32* outSz, ecEncCtx* ctx)
03858 {
03859     int          ret;
03860     word32       blockSz;
03861     word32       digestSz;
03862     ecEncCtx     localCtx;
03863     byte         sharedSecret[ECC_MAXSIZE];  /* 521 max size */
03864     byte         keys[ECC_BUFSIZE];         /* max size */
03865     word32       sharedSz = sizeof(sharedSecret);
03866     int          keysLen;
03867     int          encKeySz;
03868     int          ivSz;
03869     int          offset = 0;       /* in case using msg exchange */
03870     byte*        encKey;
03871     byte*        encIv;
03872     byte*        macKey;
03873 
03874     if (privKey == NULL || pubKey == NULL || msg == NULL || out == NULL ||
03875                            outSz  == NULL)
03876         return BAD_FUNC_ARG;
03877 
03878     if (ctx == NULL) {  /* use defaults */
03879         ecc_ctx_init(&localCtx, 0);
03880         ctx = &localCtx;  
03881     }
03882         
03883     ret = ecc_get_key_sizes(ctx, &encKeySz, &ivSz, &keysLen, &digestSz,
03884                             &blockSz);
03885     if (ret != 0)
03886         return ret;
03887         
03888     if (ctx->protocol == REQ_RESP_CLIENT) {
03889         offset = keysLen;
03890         keysLen *= 2;
03891 
03892         if (ctx->cliSt != ecCLI_SENT_REQ)
03893             return BAD_ENC_STATE_E;
03894 
03895         ctx->cliSt = ecSRV_BAD_STATE; /* we're done no more ops allowed */
03896     }
03897     else if (ctx->protocol == REQ_RESP_SERVER) {
03898         if (ctx->srvSt != ecSRV_SALT_SET)
03899             return BAD_ENC_STATE_E;
03900 
03901         ctx->srvSt = ecSRV_RECV_REQ; /* only do this once */
03902     }
03903         
03904     if (keysLen > (int)sizeof(keys))
03905         return BUFFER_E;
03906         
03907     if ( ((msgSz-digestSz) % blockSz) != 0)
03908         return BAD_PADDING_E;
03909 
03910     if (*outSz < (msgSz - digestSz))
03911         return BUFFER_E;
03912 
03913     ret = ecc_shared_secret(privKey, pubKey, sharedSecret, &sharedSz); 
03914     if (ret != 0)
03915         return ret;
03916 
03917     switch (ctx->kdfAlgo) {
03918         case ecHKDF_SHA256 :
03919                 ret = HKDF(SHA256, sharedSecret, sharedSz, ctx->kdfSalt,
03920                            ctx->kdfSaltSz, ctx->kdfInfo,
03921                            ctx->kdfInfoSz, keys, keysLen);
03922                 if (ret != 0)
03923                     return ret;
03924             break;
03925 
03926         default:
03927             return BAD_FUNC_ARG;
03928     }
03929 
03930     encKey = keys + offset;
03931     encIv  = encKey + encKeySz;
03932     macKey = encKey + encKeySz + ivSz;
03933 
03934     switch (ctx->macAlgo) {
03935         case ecHMAC_SHA256:
03936             {
03937                 byte verify[SHA256_DIGEST_SIZE];
03938                 Hmac hmac;
03939                 ret = HmacSetKey(&hmac, SHA256, macKey, SHA256_DIGEST_SIZE);
03940                 if (ret != 0)
03941                     return ret;
03942                 HmacUpdate(&hmac, msg, msgSz-digestSz);
03943                 HmacUpdate(&hmac, ctx->macSalt, ctx->macSaltSz);
03944                 HmacFinal(&hmac, verify);
03945 
03946                 if (memcmp(verify, msg + msgSz - digestSz, digestSz) != 0) {
03947                     return -1;
03948                 }
03949             }
03950             break;
03951 
03952         default:
03953             return BAD_FUNC_ARG;
03954     }
03955 
03956     switch (ctx->encAlgo) {
03957         case ecAES_128_CBC:
03958             {
03959                 Aes aes;
03960                 ret = AesSetKey(&aes, encKey,KEY_SIZE_128,encIv,AES_DECRYPTION);
03961                 if (ret != 0)
03962                     return ret;
03963                 ret = AesCbcDecrypt(&aes, out, msg, msgSz-digestSz);
03964                 if (ret != 0)
03965                     return ret;
03966             }
03967             break;
03968 
03969         default:
03970             return BAD_FUNC_ARG;
03971     }
03972 
03973     *outSz = msgSz - digestSz;
03974 
03975     return 0;
03976 }
03977 
03978 
03979 #endif /* HAVE_ECC_ENCRYPT */
03980 
03981 #endif /* HAVE_ECC */