From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-13.0 required=3.0 tests=BAYES_00, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY,URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id E5D81C433E9 for ; Thu, 3 Sep 2020 14:36:07 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by mail.kernel.org (Postfix) with ESMTP id AFF54206EB for ; Thu, 3 Sep 2020 14:36:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729358AbgICOfq (ORCPT ); Thu, 3 Sep 2020 10:35:46 -0400 Received: from out4436.biz.mail.alibaba.com ([47.88.44.36]:5731 "EHLO out4436.biz.mail.alibaba.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1729305AbgICOfe (ORCPT ); Thu, 3 Sep 2020 10:35:34 -0400 X-Alimail-AntiSpam: AC=PASS;BC=-1|-1;BR=01201311R241e4;CH=green;DM=||false|;DS=||;FP=0|-1|-1|-1|0|-1|-1|-1;HT=e01e01355;MF=tianjia.zhang@linux.alibaba.com;NM=1;PH=DS;RN=31;SR=0;TI=SMTPD_---0U7ok5HV_1599138764; Received: from localhost(mailfrom:tianjia.zhang@linux.alibaba.com fp:SMTPD_---0U7ok5HV_1599138764) by smtp.aliyun-inc.com(127.0.0.1); Thu, 03 Sep 2020 21:12:44 +0800 From: Tianjia Zhang To: Herbert Xu , "David S. Miller" , David Howells , Maxime Coquelin , Alexandre Torgue , James Morris , "Serge E. Hallyn" , Stephan Mueller , Marcelo Henrique Cerri , "Steven Rostedt (VMware)" , Masahiro Yamada , Brendan Higgins , Andrew Morton , Johannes Weiner , Waiman Long , Mimi Zohar , Lakshmi Ramasubramanian , Colin Ian King , Tushar Sugandhi , Vitaly Chikunov , "Gilad Ben-Yossef" , Pascal van Leeuwen , linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org, keyrings@vger.kernel.org, linux-stm32@st-md-mailman.stormreply.com, linux-arm-kernel@lists.infradead.org, linux-security-module@vger.kernel.org Cc: Xufeng Zhang , Jia Zhang , Tianjia Zhang Subject: [PATCH v6 3/8] lib/mpi: Introduce ec implementation to MPI library Date: Thu, 3 Sep 2020 21:12:37 +0800 Message-Id: <20200903131242.128665-4-tianjia.zhang@linux.alibaba.com> X-Mailer: git-send-email 2.19.1.3.ge56e4f7 In-Reply-To: <20200903131242.128665-1-tianjia.zhang@linux.alibaba.com> References: <20200903131242.128665-1-tianjia.zhang@linux.alibaba.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Sender: linux-crypto-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-crypto@vger.kernel.org The implementation of EC is introduced from libgcrypt as the basic algorithm of elliptic curve, which can be more perfectly integrated with MPI implementation. Some other algorithms will be developed based on mpi ecc, such as SM2. Signed-off-by: Tianjia Zhang Tested-by: Xufeng Zhang --- include/linux/mpi.h | 105 +++ lib/mpi/Makefile | 1 + lib/mpi/ec.c | 1509 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1615 insertions(+) create mode 100644 lib/mpi/ec.c diff --git a/include/linux/mpi.h b/include/linux/mpi.h index 3c9e41603cf6..3e5358f4de2f 100644 --- a/include/linux/mpi.h +++ b/include/linux/mpi.h @@ -157,6 +157,111 @@ void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor); /*-- mpi-inv.c --*/ int mpi_invm(MPI x, MPI a, MPI n); +/*-- ec.c --*/ + +/* Object to represent a point in projective coordinates */ +struct gcry_mpi_point { + MPI x; + MPI y; + MPI z; +}; + +typedef struct gcry_mpi_point *MPI_POINT; + +/* Models describing an elliptic curve */ +enum gcry_mpi_ec_models { + /* The Short Weierstrass equation is + * y^2 = x^3 + ax + b + */ + MPI_EC_WEIERSTRASS = 0, + /* The Montgomery equation is + * by^2 = x^3 + ax^2 + x + */ + MPI_EC_MONTGOMERY, + /* The Twisted Edwards equation is + * ax^2 + y^2 = 1 + bx^2y^2 + * Note that we use 'b' instead of the commonly used 'd'. + */ + MPI_EC_EDWARDS +}; + +/* Dialects used with elliptic curves */ +enum ecc_dialects { + ECC_DIALECT_STANDARD = 0, + ECC_DIALECT_ED25519, + ECC_DIALECT_SAFECURVE +}; + +/* This context is used with all our EC functions. */ +struct mpi_ec_ctx { + enum gcry_mpi_ec_models model; /* The model describing this curve. */ + enum ecc_dialects dialect; /* The ECC dialect used with the curve. */ + int flags; /* Public key flags (not always used). */ + unsigned int nbits; /* Number of bits. */ + + /* Domain parameters. Note that they may not all be set and if set + * the MPIs may be flaged as constant. + */ + MPI p; /* Prime specifying the field GF(p). */ + MPI a; /* First coefficient of the Weierstrass equation. */ + MPI b; /* Second coefficient of the Weierstrass equation. */ + MPI_POINT G; /* Base point (generator). */ + MPI n; /* Order of G. */ + unsigned int h; /* Cofactor. */ + + /* The actual key. May not be set. */ + MPI_POINT Q; /* Public key. */ + MPI d; /* Private key. */ + + const char *name; /* Name of the curve. */ + + /* This structure is private to mpi/ec.c! */ + struct { + struct { + unsigned int a_is_pminus3:1; + unsigned int two_inv_p:1; + } valid; /* Flags to help setting the helper vars below. */ + + int a_is_pminus3; /* True if A = P - 3. */ + + MPI two_inv_p; + + mpi_barrett_t p_barrett; + + /* Scratch variables. */ + MPI scratch[11]; + + /* Helper for fast reduction. */ + /* int nist_nbits; /\* If this is a NIST curve, the # of bits. *\/ */ + /* MPI s[10]; */ + /* MPI c; */ + } t; + + /* Curve specific computation routines for the field. */ + void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec); + void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); + void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); +}; + +void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model, + enum ecc_dialects dialect, + int flags, MPI p, MPI a, MPI b); +void mpi_ec_deinit(struct mpi_ec_ctx *ctx); +MPI_POINT mpi_point_new(unsigned int nbits); +void mpi_point_release(MPI_POINT p); +void mpi_point_init(MPI_POINT p); +void mpi_point_free_parts(MPI_POINT p); +int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx); +void mpi_ec_add_points(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx); +void mpi_ec_mul_point(MPI_POINT result, + MPI scalar, MPI_POINT point, + struct mpi_ec_ctx *ctx); +int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx); + /* inline functions */ /** diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile index 477debd7ed50..6e6ef9a34fe1 100644 --- a/lib/mpi/Makefile +++ b/lib/mpi/Makefile @@ -13,6 +13,7 @@ mpi-y = \ generic_mpih-rshift.o \ generic_mpih-sub1.o \ generic_mpih-add1.o \ + ec.o \ mpicoder.o \ mpi-add.o \ mpi-bit.o \ diff --git a/lib/mpi/ec.c b/lib/mpi/ec.c new file mode 100644 index 000000000000..c21470122dfc --- /dev/null +++ b/lib/mpi/ec.c @@ -0,0 +1,1509 @@ +/* ec.c - Elliptic Curve functions + * Copyright (C) 2007 Free Software Foundation, Inc. + * Copyright (C) 2013 g10 Code GmbH + * + * This file is part of Libgcrypt. + * + * Libgcrypt is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * Libgcrypt is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this program; if not, see . + */ + +#include "mpi-internal.h" +#include "longlong.h" + +#define point_init(a) mpi_point_init((a)) +#define point_free(a) mpi_point_free_parts((a)) + +#define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__) +#define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__) + +#define DIM(v) (sizeof(v)/sizeof((v)[0])) + + +/* Create a new point option. NBITS gives the size in bits of one + * coordinate; it is only used to pre-allocate some resources and + * might also be passed as 0 to use a default value. + */ +MPI_POINT mpi_point_new(unsigned int nbits) +{ + MPI_POINT p; + + (void)nbits; /* Currently not used. */ + + p = kmalloc(sizeof(*p), GFP_KERNEL); + if (p) + mpi_point_init(p); + return p; +} +EXPORT_SYMBOL_GPL(mpi_point_new); + +/* Release the point object P. P may be NULL. */ +void mpi_point_release(MPI_POINT p) +{ + if (p) { + mpi_point_free_parts(p); + kfree(p); + } +} +EXPORT_SYMBOL_GPL(mpi_point_release); + +/* Initialize the fields of a point object. gcry_mpi_point_free_parts + * may be used to release the fields. + */ +void mpi_point_init(MPI_POINT p) +{ + p->x = mpi_new(0); + p->y = mpi_new(0); + p->z = mpi_new(0); +} +EXPORT_SYMBOL_GPL(mpi_point_init); + +/* Release the parts of a point object. */ +void mpi_point_free_parts(MPI_POINT p) +{ + mpi_free(p->x); p->x = NULL; + mpi_free(p->y); p->y = NULL; + mpi_free(p->z); p->z = NULL; +} +EXPORT_SYMBOL_GPL(mpi_point_free_parts); + +/* Set the value from S into D. */ +static void point_set(MPI_POINT d, MPI_POINT s) +{ + mpi_set(d->x, s->x); + mpi_set(d->y, s->y); + mpi_set(d->z, s->z); +} + +static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx) +{ + size_t nlimbs = ctx->p->nlimbs; + + mpi_resize(p->x, nlimbs); + p->x->nlimbs = nlimbs; + mpi_resize(p->z, nlimbs); + p->z->nlimbs = nlimbs; + + if (ctx->model != MPI_EC_MONTGOMERY) { + mpi_resize(p->y, nlimbs); + p->y->nlimbs = nlimbs; + } +} + +static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap, + struct mpi_ec_ctx *ctx) +{ + mpi_swap_cond(d->x, s->x, swap); + if (ctx->model != MPI_EC_MONTGOMERY) + mpi_swap_cond(d->y, s->y, swap); + mpi_swap_cond(d->z, s->z, swap); +} + + +/* W = W mod P. */ +static void ec_mod(MPI w, struct mpi_ec_ctx *ec) +{ + if (ec->t.p_barrett) + mpi_mod_barrett(w, w, ec->t.p_barrett); + else + mpi_mod(w, w, ec->p); +} + +static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_add(w, u, v); + ec_mod(w, ctx); +} + +static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec) +{ + mpi_sub(w, u, v); + while (w->sign) + mpi_add(w, w, ec->p); + /*ec_mod(w, ec);*/ +} + +static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_mul(w, u, v); + ec_mod(w, ctx); +} + +/* W = 2 * U mod P. */ +static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx) +{ + mpi_lshift(w, u, 1); + ec_mod(w, ctx); +} + +static void ec_powm(MPI w, const MPI b, const MPI e, + struct mpi_ec_ctx *ctx) +{ + mpi_powm(w, b, e, ctx->p); + /* mpi_abs(w); */ +} + +/* Shortcut for + * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx); + * for easier optimization. + */ +static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + /* Using mpi_mul is slightly faster (at least on amd64). */ + /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */ + ec_mulm(w, b, b, ctx); +} + +/* Shortcut for + * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx); + * for easier optimization. + */ +static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p); +} + +static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx) +{ + if (!mpi_invm(x, a, ctx->p)) + log_error("ec_invm: inverse does not exist:\n"); +} + +static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up, + mpi_size_t usize, unsigned long set) +{ + mpi_size_t i; + mpi_limb_t mask = ((mpi_limb_t)0) - set; + mpi_limb_t x; + + for (i = 0; i < usize; i++) { + x = mask & (wp[i] ^ up[i]); + wp[i] = wp[i] ^ x; + } +} + +/* Routines for 2^255 - 19. */ + +#define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) + +static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519]; + mpi_limb_t borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("addm_25519: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + mpihelp_add_n(wp, up, vp, wsize); + borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); +} + +static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519]; + mpi_limb_t borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("subm_25519: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + borrow = mpihelp_sub_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); +} + +static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519*2]; + mpi_limb_t m[LIMB_SIZE_25519+1]; + mpi_limb_t cy; + int msb; + + (void)ctx; + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("mulm_25519: different sizes\n"); + + up = u->d; + vp = v->d; + wp = w->d; + + mpihelp_mul_n(n, up, vp, wsize); + memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB); + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); + + memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); + mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB)); + + memcpy(n, m, wsize * BYTES_PER_MPI_LIMB); + cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4); + m[LIMB_SIZE_25519] = cy; + cy = mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] += cy; + cy = mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] += cy; + cy = mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] += cy; + + cy = mpihelp_add_n(wp, wp, m, wsize); + m[LIMB_SIZE_25519] += cy; + + memset(m, 0, wsize * BYTES_PER_MPI_LIMB); + msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); + m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19; + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); + mpihelp_add_n(wp, wp, m, wsize); + + m[0] = 0; + cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL)); + mpihelp_add_n(wp, wp, m, wsize); +} + +static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx) +{ + ec_addm_25519(w, u, u, ctx); +} + +static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + ec_mulm_25519(w, b, b, ctx); +} + +/* Routines for 2^448 - 2^224 - 1. */ + +#define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) +#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2) + +static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t cy; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("addm_448: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + cy = mpihelp_add_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); + mpihelp_sub_n(wp, wp, n, wsize); +} + +static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("subm_448: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + borrow = mpihelp_sub_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); +} + +static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448*2]; + mpi_limb_t a2[LIMB_SIZE_HALF_448]; + mpi_limb_t a3[LIMB_SIZE_HALF_448]; + mpi_limb_t b0[LIMB_SIZE_HALF_448]; + mpi_limb_t b1[LIMB_SIZE_HALF_448]; + mpi_limb_t cy; + int i; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + mpi_limb_t b1_rest, a3_rest; +#endif + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("mulm_448: different sizes\n"); + + up = u->d; + vp = v->d; + wp = w->d; + + mpihelp_mul_n(n, up, vp, wsize); + + for (i = 0; i < (wsize + 1) / 2; i++) { + b0[i] = n[i]; + b1[i] = n[i+wsize/2]; + a2[i] = n[i+wsize]; + a3[i] = n[i+wsize+wsize/2]; + } + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; + a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; + + b1_rest = 0; + a3_rest = 0; + + for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { + mpi_limb_t b1v, a3v; + b1v = b1[i]; + a3v = a3[i]; + b1[i] = (b1_rest << 32) | (b1v >> 32); + a3[i] = (a3_rest << 32) | (a3v >> 32); + b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); + a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); + } +#endif + + cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); + for (i = 0; i < (wsize + 1) / 2; i++) + wp[i] = b0[i]; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1); +#endif + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b0[LIMB_SIZE_HALF_448-1] >> 32; +#endif + + cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); + cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b1_rest = 0; + for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { + mpi_limb_t b1v = b1[i]; + b1[i] = (b1_rest << 32) | (b1v >> 32); + b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); + } + wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); +#endif + for (i = 0; i < wsize / 2; i++) + wp[i+(wsize + 1) / 2] = b1[i]; + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b1[LIMB_SIZE_HALF_448-1]; +#endif + + memset(n, 0, wsize * BYTES_PER_MPI_LIMB); + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + n[LIMB_SIZE_HALF_448-1] = cy << 32; +#else + n[LIMB_SIZE_HALF_448] = cy; +#endif + n[0] = cy; + mpihelp_add_n(wp, wp, n, wsize); + + memset(n, 0, wsize * BYTES_PER_MPI_LIMB); + cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); +} + +static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx) +{ + ec_addm_448(w, u, u, ctx); +} + +static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + ec_mulm_448(w, b, b, ctx); +} + +struct field_table { + const char *p; + + /* computation routines for the field. */ + void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); + void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); +}; + +static const struct field_table field_table[] = { + { + "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", + ec_addm_25519, + ec_subm_25519, + ec_mulm_25519, + ec_mul2_25519, + ec_pow2_25519 + }, + { + "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" + "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + ec_addm_448, + ec_subm_448, + ec_mulm_448, + ec_mul2_448, + ec_pow2_448 + }, + { NULL, NULL, NULL, NULL, NULL, NULL }, +}; + +/* Force recomputation of all helper variables. */ +static void mpi_ec_get_reset(struct mpi_ec_ctx *ec) +{ + ec->t.valid.a_is_pminus3 = 0; + ec->t.valid.two_inv_p = 0; +} + +/* Accessor for helper variable. */ +static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec) +{ + MPI tmp; + + if (!ec->t.valid.a_is_pminus3) { + ec->t.valid.a_is_pminus3 = 1; + tmp = mpi_alloc_like(ec->p); + mpi_sub_ui(tmp, ec->p, 3); + ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp); + mpi_free(tmp); + } + + return ec->t.a_is_pminus3; +} + +/* Accessor for helper variable. */ +static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec) +{ + if (!ec->t.valid.two_inv_p) { + ec->t.valid.two_inv_p = 1; + if (!ec->t.two_inv_p) + ec->t.two_inv_p = mpi_alloc(0); + ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec); + } + return ec->t.two_inv_p; +} + +static const char *const curve25519_bad_points[] = { + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", + "0x0000000000000000000000000000000000000000000000000000000000000000", + "0x0000000000000000000000000000000000000000000000000000000000000001", + "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0", + "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee", + NULL +}; + +static const char *const curve448_bad_points[] = { + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000001", + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe", + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "00000000000000000000000000000000000000000000000000000000", + NULL +}; + +static const char *const *bad_points_table[] = { + curve25519_bad_points, + curve448_bad_points, +}; + +static void mpi_ec_coefficient_normalize(MPI a, MPI p) +{ + if (a->sign) { + mpi_resize(a, p->nlimbs); + mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs); + a->nlimbs = p->nlimbs; + a->sign = 0; + } +} + +/* This function initialized a context for elliptic curve based on the + * field GF(p). P is the prime specifying this field, A is the first + * coefficient. CTX is expected to be zeroized. + */ +void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model, + enum ecc_dialects dialect, + int flags, MPI p, MPI a, MPI b) +{ + int i; + static int use_barrett = -1 /* TODO: 1 or -1 */; + + mpi_ec_coefficient_normalize(a, p); + mpi_ec_coefficient_normalize(b, p); + + /* Fixme: Do we want to check some constraints? e.g. a < p */ + + ctx->model = model; + ctx->dialect = dialect; + ctx->flags = flags; + if (dialect == ECC_DIALECT_ED25519) + ctx->nbits = 256; + else + ctx->nbits = mpi_get_nbits(p); + ctx->p = mpi_copy(p); + ctx->a = mpi_copy(a); + ctx->b = mpi_copy(b); + + ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; + + mpi_ec_get_reset(ctx); + + if (model == MPI_EC_MONTGOMERY) { + for (i = 0; i < DIM(bad_points_table); i++) { + MPI p_candidate = mpi_scanval(bad_points_table[i][0]); + int match_p = !mpi_cmp(ctx->p, p_candidate); + int j; + + mpi_free(p_candidate); + if (!match_p) + continue; + + for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) + ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]); + } + } else { + /* Allocate scratch variables. */ + for (i = 0; i < DIM(ctx->t.scratch); i++) + ctx->t.scratch[i] = mpi_alloc_like(ctx->p); + } + + ctx->addm = ec_addm; + ctx->subm = ec_subm; + ctx->mulm = ec_mulm; + ctx->mul2 = ec_mul2; + ctx->pow2 = ec_pow2; + + for (i = 0; field_table[i].p; i++) { + MPI f_p; + + f_p = mpi_scanval(field_table[i].p); + if (!f_p) + break; + + if (!mpi_cmp(p, f_p)) { + ctx->addm = field_table[i].addm; + ctx->subm = field_table[i].subm; + ctx->mulm = field_table[i].mulm; + ctx->mul2 = field_table[i].mul2; + ctx->pow2 = field_table[i].pow2; + mpi_free(f_p); + + mpi_resize(ctx->a, ctx->p->nlimbs); + ctx->a->nlimbs = ctx->p->nlimbs; + + mpi_resize(ctx->b, ctx->p->nlimbs); + ctx->b->nlimbs = ctx->p->nlimbs; + + for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) + ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; + + break; + } + + mpi_free(f_p); + } +} +EXPORT_SYMBOL_GPL(mpi_ec_init); + +void mpi_ec_deinit(struct mpi_ec_ctx *ctx) +{ + int i; + + mpi_barrett_free(ctx->t.p_barrett); + + /* Domain parameter. */ + mpi_free(ctx->p); + mpi_free(ctx->a); + mpi_free(ctx->b); + mpi_point_release(ctx->G); + mpi_free(ctx->n); + + /* The key. */ + mpi_point_release(ctx->Q); + mpi_free(ctx->d); + + /* Private data of ec.c. */ + mpi_free(ctx->t.two_inv_p); + + for (i = 0; i < DIM(ctx->t.scratch); i++) + mpi_free(ctx->t.scratch[i]); +} +EXPORT_SYMBOL_GPL(mpi_ec_deinit); + +/* Compute the affine coordinates from the projective coordinates in + * POINT. Set them into X and Y. If one coordinate is not required, + * X or Y may be passed as NULL. CTX is the usual context. Returns: 0 + * on success or !0 if POINT is at infinity. + */ +int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + if (!mpi_cmp_ui(point->z, 0)) + return -1; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */ + { + MPI z1, z2, z3; + + z1 = mpi_new(0); + z2 = mpi_new(0); + ec_invm(z1, point->z, ctx); /* z1 = z^(-1) mod p */ + ec_mulm(z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ + + if (x) + ec_mulm(x, point->x, z2, ctx); + + if (y) { + z3 = mpi_new(0); + ec_mulm(z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ + ec_mulm(y, point->y, z3, ctx); + mpi_free(z3); + } + + mpi_free(z2); + mpi_free(z1); + } + return 0; + + case MPI_EC_MONTGOMERY: + { + if (x) + mpi_set(x, point->x); + + if (y) { + log_fatal("%s: Getting Y-coordinate on %s is not supported\n", + "mpi_ec_get_affine", "Montgomery"); + return -1; + } + } + return 0; + + case MPI_EC_EDWARDS: + { + MPI z; + + z = mpi_new(0); + ec_invm(z, point->z, ctx); + + mpi_resize(z, ctx->p->nlimbs); + z->nlimbs = ctx->p->nlimbs; + + if (x) { + mpi_resize(x, ctx->p->nlimbs); + x->nlimbs = ctx->p->nlimbs; + ctx->mulm(x, point->x, z, ctx); + } + if (y) { + mpi_resize(y, ctx->p->nlimbs); + y->nlimbs = ctx->p->nlimbs; + ctx->mulm(y, point->y, z, ctx); + } + + mpi_free(z); + } + return 0; + + default: + return -1; + } +} +EXPORT_SYMBOL_GPL(mpi_ec_get_affine); + +/* RESULT = 2 * POINT (Weierstrass version). */ +static void dup_point_weierstrass(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define t1 (ctx->t.scratch[0]) +#define t2 (ctx->t.scratch[1]) +#define t3 (ctx->t.scratch[2]) +#define l1 (ctx->t.scratch[3]) +#define l2 (ctx->t.scratch[4]) +#define l3 (ctx->t.scratch[5]) + + if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) { + /* P_y == 0 || P_z == 0 => [1:1:0] */ + mpi_set_ui(x3, 1); + mpi_set_ui(y3, 1); + mpi_set_ui(z3, 0); + } else { + if (ec_get_a_is_pminus3(ctx)) { + /* Use the faster case. */ + /* L1 = 3(X - Z^2)(X + Z^2) */ + /* T1: used for Z^2. */ + /* T2: used for the right term. */ + ec_pow2(t1, point->z, ctx); + ec_subm(l1, point->x, t1, ctx); + ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); + ec_addm(t2, point->x, t1, ctx); + ec_mulm(l1, l1, t2, ctx); + } else { + /* Standard case. */ + /* L1 = 3X^2 + aZ^4 */ + /* T1: used for aZ^4. */ + ec_pow2(l1, point->x, ctx); + ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); + ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx); + ec_mulm(t1, t1, ctx->a, ctx); + ec_addm(l1, l1, t1, ctx); + } + /* Z3 = 2YZ */ + ec_mulm(z3, point->y, point->z, ctx); + ec_mul2(z3, z3, ctx); + + /* L2 = 4XY^2 */ + /* T2: used for Y2; required later. */ + ec_pow2(t2, point->y, ctx); + ec_mulm(l2, t2, point->x, ctx); + ec_mulm(l2, l2, mpi_const(MPI_C_FOUR), ctx); + + /* X3 = L1^2 - 2L2 */ + /* T1: used for L2^2. */ + ec_pow2(x3, l1, ctx); + ec_mul2(t1, l2, ctx); + ec_subm(x3, x3, t1, ctx); + + /* L3 = 8Y^4 */ + /* T2: taken from above. */ + ec_pow2(t2, t2, ctx); + ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx); + + /* Y3 = L1(L2 - X3) - L3 */ + ec_subm(y3, l2, x3, ctx); + ec_mulm(y3, y3, l1, ctx); + ec_subm(y3, y3, l3, ctx); + } + +#undef x3 +#undef y3 +#undef z3 +#undef t1 +#undef t2 +#undef t3 +#undef l1 +#undef l2 +#undef l3 +} + +/* RESULT = 2 * POINT (Montgomery version). */ +static void dup_point_montgomery(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + (void)result; + (void)point; + (void)ctx; + log_fatal("%s: %s not yet supported\n", + "mpi_ec_dup_point", "Montgomery"); +} + +/* RESULT = 2 * POINT (Twisted Edwards version). */ +static void dup_point_edwards(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ +#define X1 (point->x) +#define Y1 (point->y) +#define Z1 (point->z) +#define X3 (result->x) +#define Y3 (result->y) +#define Z3 (result->z) +#define B (ctx->t.scratch[0]) +#define C (ctx->t.scratch[1]) +#define D (ctx->t.scratch[2]) +#define E (ctx->t.scratch[3]) +#define F (ctx->t.scratch[4]) +#define H (ctx->t.scratch[5]) +#define J (ctx->t.scratch[6]) + + /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */ + + /* B = (X_1 + Y_1)^2 */ + ctx->addm(B, X1, Y1, ctx); + ctx->pow2(B, B, ctx); + + /* C = X_1^2 */ + /* D = Y_1^2 */ + ctx->pow2(C, X1, ctx); + ctx->pow2(D, Y1, ctx); + + /* E = aC */ + if (ctx->dialect == ECC_DIALECT_ED25519) + ctx->subm(E, ctx->p, C, ctx); + else + ctx->mulm(E, ctx->a, C, ctx); + + /* F = E + D */ + ctx->addm(F, E, D, ctx); + + /* H = Z_1^2 */ + ctx->pow2(H, Z1, ctx); + + /* J = F - 2H */ + ctx->mul2(J, H, ctx); + ctx->subm(J, F, J, ctx); + + /* X_3 = (B - C - D) · J */ + ctx->subm(X3, B, C, ctx); + ctx->subm(X3, X3, D, ctx); + ctx->mulm(X3, X3, J, ctx); + + /* Y_3 = F · (E - D) */ + ctx->subm(Y3, E, D, ctx); + ctx->mulm(Y3, Y3, F, ctx); + + /* Z_3 = F · J */ + ctx->mulm(Z3, F, J, ctx); + +#undef X1 +#undef Y1 +#undef Z1 +#undef X3 +#undef Y3 +#undef Z3 +#undef B +#undef C +#undef D +#undef E +#undef F +#undef H +#undef J +} + +/* RESULT = 2 * POINT */ +static void +mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + dup_point_weierstrass(result, point, ctx); + break; + case MPI_EC_MONTGOMERY: + dup_point_montgomery(result, point, ctx); + break; + case MPI_EC_EDWARDS: + dup_point_edwards(result, point, ctx); + break; + } +} + +/* RESULT = P1 + P2 (Weierstrass version).*/ +static void add_points_weierstrass(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ +#define x1 (p1->x) +#define y1 (p1->y) +#define z1 (p1->z) +#define x2 (p2->x) +#define y2 (p2->y) +#define z2 (p2->z) +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define l1 (ctx->t.scratch[0]) +#define l2 (ctx->t.scratch[1]) +#define l3 (ctx->t.scratch[2]) +#define l4 (ctx->t.scratch[3]) +#define l5 (ctx->t.scratch[4]) +#define l6 (ctx->t.scratch[5]) +#define l7 (ctx->t.scratch[6]) +#define l8 (ctx->t.scratch[7]) +#define l9 (ctx->t.scratch[8]) +#define t1 (ctx->t.scratch[9]) +#define t2 (ctx->t.scratch[10]) + + if ((!mpi_cmp(x1, x2)) && (!mpi_cmp(y1, y2)) && (!mpi_cmp(z1, z2))) { + /* Same point; need to call the duplicate function. */ + mpi_ec_dup_point(result, p1, ctx); + } else if (!mpi_cmp_ui(z1, 0)) { + /* P1 is at infinity. */ + mpi_set(x3, p2->x); + mpi_set(y3, p2->y); + mpi_set(z3, p2->z); + } else if (!mpi_cmp_ui(z2, 0)) { + /* P2 is at infinity. */ + mpi_set(x3, p1->x); + mpi_set(y3, p1->y); + mpi_set(z3, p1->z); + } else { + int z1_is_one = !mpi_cmp_ui(z1, 1); + int z2_is_one = !mpi_cmp_ui(z2, 1); + + /* l1 = x1 z2^2 */ + /* l2 = x2 z1^2 */ + if (z2_is_one) + mpi_set(l1, x1); + else { + ec_pow2(l1, z2, ctx); + ec_mulm(l1, l1, x1, ctx); + } + if (z1_is_one) + mpi_set(l2, x2); + else { + ec_pow2(l2, z1, ctx); + ec_mulm(l2, l2, x2, ctx); + } + /* l3 = l1 - l2 */ + ec_subm(l3, l1, l2, ctx); + /* l4 = y1 z2^3 */ + ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l4, l4, y1, ctx); + /* l5 = y2 z1^3 */ + ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l5, l5, y2, ctx); + /* l6 = l4 - l5 */ + ec_subm(l6, l4, l5, ctx); + + if (!mpi_cmp_ui(l3, 0)) { + if (!mpi_cmp_ui(l6, 0)) { + /* P1 and P2 are the same - use duplicate function. */ + mpi_ec_dup_point(result, p1, ctx); + } else { + /* P1 is the inverse of P2. */ + mpi_set_ui(x3, 1); + mpi_set_ui(y3, 1); + mpi_set_ui(z3, 0); + } + } else { + /* l7 = l1 + l2 */ + ec_addm(l7, l1, l2, ctx); + /* l8 = l4 + l5 */ + ec_addm(l8, l4, l5, ctx); + /* z3 = z1 z2 l3 */ + ec_mulm(z3, z1, z2, ctx); + ec_mulm(z3, z3, l3, ctx); + /* x3 = l6^2 - l7 l3^2 */ + ec_pow2(t1, l6, ctx); + ec_pow2(t2, l3, ctx); + ec_mulm(t2, t2, l7, ctx); + ec_subm(x3, t1, t2, ctx); + /* l9 = l7 l3^2 - 2 x3 */ + ec_mul2(t1, x3, ctx); + ec_subm(l9, t2, t1, ctx); + /* y3 = (l9 l6 - l8 l3^3)/2 */ + ec_mulm(l9, l9, l6, ctx); + ec_powm(t1, l3, mpi_const(MPI_C_THREE), ctx); /* fixme: Use saved value*/ + ec_mulm(t1, t1, l8, ctx); + ec_subm(y3, l9, t1, ctx); + ec_mulm(y3, y3, ec_get_two_inv_p(ctx), ctx); + } + } + +#undef x1 +#undef y1 +#undef z1 +#undef x2 +#undef y2 +#undef z2 +#undef x3 +#undef y3 +#undef z3 +#undef l1 +#undef l2 +#undef l3 +#undef l4 +#undef l5 +#undef l6 +#undef l7 +#undef l8 +#undef l9 +#undef t1 +#undef t2 +} + +/* RESULT = P1 + P2 (Montgomery version).*/ +static void add_points_montgomery(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ + (void)result; + (void)p1; + (void)p2; + (void)ctx; + log_fatal("%s: %s not yet supported\n", + "mpi_ec_add_points", "Montgomery"); +} + +/* RESULT = P1 + P2 (Twisted Edwards version).*/ +static void add_points_edwards(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ +#define X1 (p1->x) +#define Y1 (p1->y) +#define Z1 (p1->z) +#define X2 (p2->x) +#define Y2 (p2->y) +#define Z2 (p2->z) +#define X3 (result->x) +#define Y3 (result->y) +#define Z3 (result->z) +#define A (ctx->t.scratch[0]) +#define B (ctx->t.scratch[1]) +#define C (ctx->t.scratch[2]) +#define D (ctx->t.scratch[3]) +#define E (ctx->t.scratch[4]) +#define F (ctx->t.scratch[5]) +#define G (ctx->t.scratch[6]) +#define tmp (ctx->t.scratch[7]) + + point_resize(result, ctx); + + /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */ + + /* A = Z1 · Z2 */ + ctx->mulm(A, Z1, Z2, ctx); + + /* B = A^2 */ + ctx->pow2(B, A, ctx); + + /* C = X1 · X2 */ + ctx->mulm(C, X1, X2, ctx); + + /* D = Y1 · Y2 */ + ctx->mulm(D, Y1, Y2, ctx); + + /* E = d · C · D */ + ctx->mulm(E, ctx->b, C, ctx); + ctx->mulm(E, E, D, ctx); + + /* F = B - E */ + ctx->subm(F, B, E, ctx); + + /* G = B + E */ + ctx->addm(G, B, E, ctx); + + /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ + ctx->addm(tmp, X1, Y1, ctx); + ctx->addm(X3, X2, Y2, ctx); + ctx->mulm(X3, X3, tmp, ctx); + ctx->subm(X3, X3, C, ctx); + ctx->subm(X3, X3, D, ctx); + ctx->mulm(X3, X3, F, ctx); + ctx->mulm(X3, X3, A, ctx); + + /* Y_3 = A · G · (D - aC) */ + if (ctx->dialect == ECC_DIALECT_ED25519) { + ctx->addm(Y3, D, C, ctx); + } else { + ctx->mulm(Y3, ctx->a, C, ctx); + ctx->subm(Y3, D, Y3, ctx); + } + ctx->mulm(Y3, Y3, G, ctx); + ctx->mulm(Y3, Y3, A, ctx); + + /* Z_3 = F · G */ + ctx->mulm(Z3, F, G, ctx); + + +#undef X1 +#undef Y1 +#undef Z1 +#undef X2 +#undef Y2 +#undef Z2 +#undef X3 +#undef Y3 +#undef Z3 +#undef A +#undef B +#undef C +#undef D +#undef E +#undef F +#undef G +#undef tmp +} + +/* Compute a step of Montgomery Ladder (only use X and Z in the point). + * Inputs: P1, P2, and x-coordinate of DIF = P1 - P1. + * Outputs: PRD = 2 * P1 and SUM = P1 + P2. + */ +static void montgomery_ladder(MPI_POINT prd, MPI_POINT sum, + MPI_POINT p1, MPI_POINT p2, MPI dif_x, + struct mpi_ec_ctx *ctx) +{ + ctx->addm(sum->x, p2->x, p2->z, ctx); + ctx->subm(p2->z, p2->x, p2->z, ctx); + ctx->addm(prd->x, p1->x, p1->z, ctx); + ctx->subm(p1->z, p1->x, p1->z, ctx); + ctx->mulm(p2->x, p1->z, sum->x, ctx); + ctx->mulm(p2->z, prd->x, p2->z, ctx); + ctx->pow2(p1->x, prd->x, ctx); + ctx->pow2(p1->z, p1->z, ctx); + ctx->addm(sum->x, p2->x, p2->z, ctx); + ctx->subm(p2->z, p2->x, p2->z, ctx); + ctx->mulm(prd->x, p1->x, p1->z, ctx); + ctx->subm(p1->z, p1->x, p1->z, ctx); + ctx->pow2(sum->x, sum->x, ctx); + ctx->pow2(sum->z, p2->z, ctx); + ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ + ctx->mulm(sum->z, sum->z, dif_x, ctx); + ctx->addm(prd->z, p1->x, prd->z, ctx); + ctx->mulm(prd->z, prd->z, p1->z, ctx); +} + +/* RESULT = P1 + P2 */ +void mpi_ec_add_points(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + add_points_weierstrass(result, p1, p2, ctx); + break; + case MPI_EC_MONTGOMERY: + add_points_montgomery(result, p1, p2, ctx); + break; + case MPI_EC_EDWARDS: + add_points_edwards(result, p1, p2, ctx); + break; + } +} +EXPORT_SYMBOL_GPL(mpi_ec_add_points); + +/* Scalar point multiplication - the main function for ECC. If takes + * an integer SCALAR and a POINT as well as the usual context CTX. + * RESULT will be set to the resulting point. + */ +void mpi_ec_mul_point(MPI_POINT result, + MPI scalar, MPI_POINT point, + struct mpi_ec_ctx *ctx) +{ + MPI x1, y1, z1, k, h, yy; + unsigned int i, loops; + struct gcry_mpi_point p1, p2, p1inv; + + if (ctx->model == MPI_EC_EDWARDS) { + /* Simple left to right binary method. Algorithm 3.27 from + * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott}, + * title = {Guide to Elliptic Curve Cryptography}, + * year = {2003}, isbn = {038795273X}, + * url = {http://www.cacr.math.uwaterloo.ca/ecc/}, + * publisher = {Springer-Verlag New York, Inc.}} + */ + unsigned int nbits; + int j; + + if (mpi_cmp(scalar, ctx->p) >= 0) + nbits = mpi_get_nbits(scalar); + else + nbits = mpi_get_nbits(ctx->p); + + mpi_set_ui(result->x, 0); + mpi_set_ui(result->y, 1); + mpi_set_ui(result->z, 1); + point_resize(point, ctx); + + point_resize(result, ctx); + point_resize(point, ctx); + + for (j = nbits-1; j >= 0; j--) { + mpi_ec_dup_point(result, result, ctx); + if (mpi_test_bit(scalar, j)) + mpi_ec_add_points(result, result, point, ctx); + } + return; + } else if (ctx->model == MPI_EC_MONTGOMERY) { + unsigned int nbits; + int j; + struct gcry_mpi_point p1_, p2_; + MPI_POINT q1, q2, prd, sum; + unsigned long sw; + mpi_size_t rsize; + int scalar_copied = 0; + + /* Compute scalar point multiplication with Montgomery Ladder. + * Note that we don't use Y-coordinate in the points at all. + * RESULT->Y will be filled by zero. + */ + + nbits = mpi_get_nbits(scalar); + point_init(&p1); + point_init(&p2); + point_init(&p1_); + point_init(&p2_); + mpi_set_ui(p1.x, 1); + mpi_free(p2.x); + p2.x = mpi_copy(point->x); + mpi_set_ui(p2.z, 1); + + point_resize(&p1, ctx); + point_resize(&p2, ctx); + point_resize(&p1_, ctx); + point_resize(&p2_, ctx); + + mpi_resize(point->x, ctx->p->nlimbs); + point->x->nlimbs = ctx->p->nlimbs; + + q1 = &p1; + q2 = &p2; + prd = &p1_; + sum = &p2_; + + for (j = nbits-1; j >= 0; j--) { + MPI_POINT t; + + sw = mpi_test_bit(scalar, j); + point_swap_cond(q1, q2, sw, ctx); + montgomery_ladder(prd, sum, q1, q2, point->x, ctx); + point_swap_cond(prd, sum, sw, ctx); + t = q1; q1 = prd; prd = t; + t = q2; q2 = sum; sum = t; + } + + mpi_clear(result->y); + sw = (nbits & 1); + point_swap_cond(&p1, &p1_, sw, ctx); + + rsize = p1.z->nlimbs; + MPN_NORMALIZE(p1.z->d, rsize); + if (rsize == 0) { + mpi_set_ui(result->x, 1); + mpi_set_ui(result->z, 0); + } else { + z1 = mpi_new(0); + ec_invm(z1, p1.z, ctx); + ec_mulm(result->x, p1.x, z1, ctx); + mpi_set_ui(result->z, 1); + mpi_free(z1); + } + + point_free(&p1); + point_free(&p2); + point_free(&p1_); + point_free(&p2_); + if (scalar_copied) + mpi_free(scalar); + return; + } + + x1 = mpi_alloc_like(ctx->p); + y1 = mpi_alloc_like(ctx->p); + h = mpi_alloc_like(ctx->p); + k = mpi_copy(scalar); + yy = mpi_copy(point->y); + + if (mpi_has_sign(k)) { + k->sign = 0; + ec_invm(yy, yy, ctx); + } + + if (!mpi_cmp_ui(point->z, 1)) { + mpi_set(x1, point->x); + mpi_set(y1, yy); + } else { + MPI z2, z3; + + z2 = mpi_alloc_like(ctx->p); + z3 = mpi_alloc_like(ctx->p); + ec_mulm(z2, point->z, point->z, ctx); + ec_mulm(z3, point->z, z2, ctx); + ec_invm(z2, z2, ctx); + ec_mulm(x1, point->x, z2, ctx); + ec_invm(z3, z3, ctx); + ec_mulm(y1, yy, z3, ctx); + mpi_free(z2); + mpi_free(z3); + } + z1 = mpi_copy(mpi_const(MPI_C_ONE)); + + mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h = 3k */ + loops = mpi_get_nbits(h); + if (loops < 2) { + /* If SCALAR is zero, the above mpi_mul sets H to zero and thus + * LOOPs will be zero. To avoid an underflow of I in the main + * loop we set LOOP to 2 and the result to (0,0,0). + */ + loops = 2; + mpi_clear(result->x); + mpi_clear(result->y); + mpi_clear(result->z); + } else { + mpi_set(result->x, point->x); + mpi_set(result->y, yy); + mpi_set(result->z, point->z); + } + mpi_free(yy); yy = NULL; + + p1.x = x1; x1 = NULL; + p1.y = y1; y1 = NULL; + p1.z = z1; z1 = NULL; + point_init(&p2); + point_init(&p1inv); + + /* Invert point: y = p - y mod p */ + point_set(&p1inv, &p1); + ec_subm(p1inv.y, ctx->p, p1inv.y, ctx); + + for (i = loops-2; i > 0; i--) { + mpi_ec_dup_point(result, result, ctx); + if (mpi_test_bit(h, i) == 1 && mpi_test_bit(k, i) == 0) { + point_set(&p2, result); + mpi_ec_add_points(result, &p2, &p1, ctx); + } + if (mpi_test_bit(h, i) == 0 && mpi_test_bit(k, i) == 1) { + point_set(&p2, result); + mpi_ec_add_points(result, &p2, &p1inv, ctx); + } + } + + point_free(&p1); + point_free(&p2); + point_free(&p1inv); + mpi_free(h); + mpi_free(k); +} +EXPORT_SYMBOL_GPL(mpi_ec_mul_point); + +/* Return true if POINT is on the curve described by CTX. */ +int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + int res = 0; + MPI x, y, w; + + x = mpi_new(0); + y = mpi_new(0); + w = mpi_new(0); + + /* Check that the point is in range. This needs to be done here and + * not after conversion to affine coordinates. + */ + if (mpi_cmpabs(point->x, ctx->p) >= 0) + goto leave; + if (mpi_cmpabs(point->y, ctx->p) >= 0) + goto leave; + if (mpi_cmpabs(point->z, ctx->p) >= 0) + goto leave; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + { + MPI xxx; + + if (mpi_ec_get_affine(x, y, point, ctx)) + goto leave; + + xxx = mpi_new(0); + + /* y^2 == x^3 + a·x + b */ + ec_pow2(y, y, ctx); + + ec_pow3(xxx, x, ctx); + ec_mulm(w, ctx->a, x, ctx); + ec_addm(w, w, ctx->b, ctx); + ec_addm(w, w, xxx, ctx); + + if (!mpi_cmp(y, w)) + res = 1; + + mpi_free(xxx); + } + break; + + case MPI_EC_MONTGOMERY: + { +#define xx y + /* With Montgomery curve, only X-coordinate is valid. */ + if (mpi_ec_get_affine(x, NULL, point, ctx)) + goto leave; + + /* The equation is: b * y^2 == x^3 + a · x^2 + x */ + /* We check if right hand is quadratic residue or not by + * Euler's criterion. + */ + /* CTX->A has (a-2)/4 and CTX->B has b^-1 */ + ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx); + ec_addm(w, w, mpi_const(MPI_C_TWO), ctx); + ec_mulm(w, w, x, ctx); + ec_pow2(xx, x, ctx); + ec_addm(w, w, xx, ctx); + ec_addm(w, w, mpi_const(MPI_C_ONE), ctx); + ec_mulm(w, w, x, ctx); + ec_mulm(w, w, ctx->b, ctx); +#undef xx + /* Compute Euler's criterion: w^(p-1)/2 */ +#define p_minus1 y + ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx); + mpi_rshift(p_minus1, p_minus1, 1); + ec_powm(w, w, p_minus1, ctx); + + res = !mpi_cmp_ui(w, 1); +#undef p_minus1 + } + break; + + case MPI_EC_EDWARDS: + { + if (mpi_ec_get_affine(x, y, point, ctx)) + goto leave; + + mpi_resize(w, ctx->p->nlimbs); + w->nlimbs = ctx->p->nlimbs; + + /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */ + ctx->pow2(x, x, ctx); + ctx->pow2(y, y, ctx); + if (ctx->dialect == ECC_DIALECT_ED25519) + ctx->subm(w, ctx->p, x, ctx); + else + ctx->mulm(w, ctx->a, x, ctx); + ctx->addm(w, w, y, ctx); + ctx->mulm(x, x, y, ctx); + ctx->mulm(x, x, ctx->b, ctx); + ctx->subm(w, w, x, ctx); + if (!mpi_cmp_ui(w, 1)) + res = 1; + } + break; + } + +leave: + mpi_free(w); + mpi_free(x); + mpi_free(y); + + return res; +} +EXPORT_SYMBOL_GPL(mpi_ec_curve_point); -- 2.19.1.3.ge56e4f7 From mboxrd@z Thu Jan 1 00:00:00 1970 From: Tianjia Zhang Date: Thu, 03 Sep 2020 13:12:37 +0000 Subject: [PATCH v6 3/8] lib/mpi: Introduce ec implementation to MPI library Message-Id: <20200903131242.128665-4-tianjia.zhang@linux.alibaba.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8bit List-Id: References: <20200903131242.128665-1-tianjia.zhang@linux.alibaba.com> In-Reply-To: <20200903131242.128665-1-tianjia.zhang@linux.alibaba.com> To: Herbert Xu , "David S. Miller" , David Howells , Maxime Coquelin , Alexandre Torgue , James Morris , "Serge E. Hallyn" , Stephan Mueller , Marcelo Henrique Cerri , "Steven Rostedt (VMware)" , Masahiro Yamada , Brendan Higgins , Andrew Morton , Johannes Weiner , Waiman Long , Mimi Zohar , Lakshmi Ramasubramanian , Colin Ian King , Tushar Sugandhi , Vitaly Chikunov , Gilad Ben-Yossef , Pascal van Leeuwen , linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org, keyrings@vger.kernel.org, linux-stm32@st-md-mailman.stormreply.com, linux-arm-kernel@lists.infradead.org, linux-security-module@vger.kernel.org Cc: Xufeng Zhang , Tianjia Zhang , Jia Zhang The implementation of EC is introduced from libgcrypt as the basic algorithm of elliptic curve, which can be more perfectly integrated with MPI implementation. Some other algorithms will be developed based on mpi ecc, such as SM2. Signed-off-by: Tianjia Zhang Tested-by: Xufeng Zhang --- include/linux/mpi.h | 105 +++ lib/mpi/Makefile | 1 + lib/mpi/ec.c | 1509 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1615 insertions(+) create mode 100644 lib/mpi/ec.c diff --git a/include/linux/mpi.h b/include/linux/mpi.h index 3c9e41603cf6..3e5358f4de2f 100644 --- a/include/linux/mpi.h +++ b/include/linux/mpi.h @@ -157,6 +157,111 @@ void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor); /*-- mpi-inv.c --*/ int mpi_invm(MPI x, MPI a, MPI n); +/*-- ec.c --*/ + +/* Object to represent a point in projective coordinates */ +struct gcry_mpi_point { + MPI x; + MPI y; + MPI z; +}; + +typedef struct gcry_mpi_point *MPI_POINT; + +/* Models describing an elliptic curve */ +enum gcry_mpi_ec_models { + /* The Short Weierstrass equation is + * y^2 = x^3 + ax + b + */ + MPI_EC_WEIERSTRASS = 0, + /* The Montgomery equation is + * by^2 = x^3 + ax^2 + x + */ + MPI_EC_MONTGOMERY, + /* The Twisted Edwards equation is + * ax^2 + y^2 = 1 + bx^2y^2 + * Note that we use 'b' instead of the commonly used 'd'. + */ + MPI_EC_EDWARDS +}; + +/* Dialects used with elliptic curves */ +enum ecc_dialects { + ECC_DIALECT_STANDARD = 0, + ECC_DIALECT_ED25519, + ECC_DIALECT_SAFECURVE +}; + +/* This context is used with all our EC functions. */ +struct mpi_ec_ctx { + enum gcry_mpi_ec_models model; /* The model describing this curve. */ + enum ecc_dialects dialect; /* The ECC dialect used with the curve. */ + int flags; /* Public key flags (not always used). */ + unsigned int nbits; /* Number of bits. */ + + /* Domain parameters. Note that they may not all be set and if set + * the MPIs may be flaged as constant. + */ + MPI p; /* Prime specifying the field GF(p). */ + MPI a; /* First coefficient of the Weierstrass equation. */ + MPI b; /* Second coefficient of the Weierstrass equation. */ + MPI_POINT G; /* Base point (generator). */ + MPI n; /* Order of G. */ + unsigned int h; /* Cofactor. */ + + /* The actual key. May not be set. */ + MPI_POINT Q; /* Public key. */ + MPI d; /* Private key. */ + + const char *name; /* Name of the curve. */ + + /* This structure is private to mpi/ec.c! */ + struct { + struct { + unsigned int a_is_pminus3:1; + unsigned int two_inv_p:1; + } valid; /* Flags to help setting the helper vars below. */ + + int a_is_pminus3; /* True if A = P - 3. */ + + MPI two_inv_p; + + mpi_barrett_t p_barrett; + + /* Scratch variables. */ + MPI scratch[11]; + + /* Helper for fast reduction. */ + /* int nist_nbits; /\* If this is a NIST curve, the # of bits. *\/ */ + /* MPI s[10]; */ + /* MPI c; */ + } t; + + /* Curve specific computation routines for the field. */ + void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec); + void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); + void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); +}; + +void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model, + enum ecc_dialects dialect, + int flags, MPI p, MPI a, MPI b); +void mpi_ec_deinit(struct mpi_ec_ctx *ctx); +MPI_POINT mpi_point_new(unsigned int nbits); +void mpi_point_release(MPI_POINT p); +void mpi_point_init(MPI_POINT p); +void mpi_point_free_parts(MPI_POINT p); +int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx); +void mpi_ec_add_points(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx); +void mpi_ec_mul_point(MPI_POINT result, + MPI scalar, MPI_POINT point, + struct mpi_ec_ctx *ctx); +int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx); + /* inline functions */ /** diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile index 477debd7ed50..6e6ef9a34fe1 100644 --- a/lib/mpi/Makefile +++ b/lib/mpi/Makefile @@ -13,6 +13,7 @@ mpi-y = \ generic_mpih-rshift.o \ generic_mpih-sub1.o \ generic_mpih-add1.o \ + ec.o \ mpicoder.o \ mpi-add.o \ mpi-bit.o \ diff --git a/lib/mpi/ec.c b/lib/mpi/ec.c new file mode 100644 index 000000000000..c21470122dfc --- /dev/null +++ b/lib/mpi/ec.c @@ -0,0 +1,1509 @@ +/* ec.c - Elliptic Curve functions + * Copyright (C) 2007 Free Software Foundation, Inc. + * Copyright (C) 2013 g10 Code GmbH + * + * This file is part of Libgcrypt. + * + * Libgcrypt is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as + * published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * Libgcrypt is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this program; if not, see . + */ + +#include "mpi-internal.h" +#include "longlong.h" + +#define point_init(a) mpi_point_init((a)) +#define point_free(a) mpi_point_free_parts((a)) + +#define log_error(fmt, ...) pr_err(fmt, ##__VA_ARGS__) +#define log_fatal(fmt, ...) pr_err(fmt, ##__VA_ARGS__) + +#define DIM(v) (sizeof(v)/sizeof((v)[0])) + + +/* Create a new point option. NBITS gives the size in bits of one + * coordinate; it is only used to pre-allocate some resources and + * might also be passed as 0 to use a default value. + */ +MPI_POINT mpi_point_new(unsigned int nbits) +{ + MPI_POINT p; + + (void)nbits; /* Currently not used. */ + + p = kmalloc(sizeof(*p), GFP_KERNEL); + if (p) + mpi_point_init(p); + return p; +} +EXPORT_SYMBOL_GPL(mpi_point_new); + +/* Release the point object P. P may be NULL. */ +void mpi_point_release(MPI_POINT p) +{ + if (p) { + mpi_point_free_parts(p); + kfree(p); + } +} +EXPORT_SYMBOL_GPL(mpi_point_release); + +/* Initialize the fields of a point object. gcry_mpi_point_free_parts + * may be used to release the fields. + */ +void mpi_point_init(MPI_POINT p) +{ + p->x = mpi_new(0); + p->y = mpi_new(0); + p->z = mpi_new(0); +} +EXPORT_SYMBOL_GPL(mpi_point_init); + +/* Release the parts of a point object. */ +void mpi_point_free_parts(MPI_POINT p) +{ + mpi_free(p->x); p->x = NULL; + mpi_free(p->y); p->y = NULL; + mpi_free(p->z); p->z = NULL; +} +EXPORT_SYMBOL_GPL(mpi_point_free_parts); + +/* Set the value from S into D. */ +static void point_set(MPI_POINT d, MPI_POINT s) +{ + mpi_set(d->x, s->x); + mpi_set(d->y, s->y); + mpi_set(d->z, s->z); +} + +static void point_resize(MPI_POINT p, struct mpi_ec_ctx *ctx) +{ + size_t nlimbs = ctx->p->nlimbs; + + mpi_resize(p->x, nlimbs); + p->x->nlimbs = nlimbs; + mpi_resize(p->z, nlimbs); + p->z->nlimbs = nlimbs; + + if (ctx->model != MPI_EC_MONTGOMERY) { + mpi_resize(p->y, nlimbs); + p->y->nlimbs = nlimbs; + } +} + +static void point_swap_cond(MPI_POINT d, MPI_POINT s, unsigned long swap, + struct mpi_ec_ctx *ctx) +{ + mpi_swap_cond(d->x, s->x, swap); + if (ctx->model != MPI_EC_MONTGOMERY) + mpi_swap_cond(d->y, s->y, swap); + mpi_swap_cond(d->z, s->z, swap); +} + + +/* W = W mod P. */ +static void ec_mod(MPI w, struct mpi_ec_ctx *ec) +{ + if (ec->t.p_barrett) + mpi_mod_barrett(w, w, ec->t.p_barrett); + else + mpi_mod(w, w, ec->p); +} + +static void ec_addm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_add(w, u, v); + ec_mod(w, ctx); +} + +static void ec_subm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ec) +{ + mpi_sub(w, u, v); + while (w->sign) + mpi_add(w, w, ec->p); + /*ec_mod(w, ec);*/ +} + +static void ec_mulm(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_mul(w, u, v); + ec_mod(w, ctx); +} + +/* W = 2 * U mod P. */ +static void ec_mul2(MPI w, MPI u, struct mpi_ec_ctx *ctx) +{ + mpi_lshift(w, u, 1); + ec_mod(w, ctx); +} + +static void ec_powm(MPI w, const MPI b, const MPI e, + struct mpi_ec_ctx *ctx) +{ + mpi_powm(w, b, e, ctx->p); + /* mpi_abs(w); */ +} + +/* Shortcut for + * ec_powm(B, B, mpi_const(MPI_C_TWO), ctx); + * for easier optimization. + */ +static void ec_pow2(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + /* Using mpi_mul is slightly faster (at least on amd64). */ + /* mpi_powm(w, b, mpi_const(MPI_C_TWO), ctx->p); */ + ec_mulm(w, b, b, ctx); +} + +/* Shortcut for + * ec_powm(B, B, mpi_const(MPI_C_THREE), ctx); + * for easier optimization. + */ +static void ec_pow3(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + mpi_powm(w, b, mpi_const(MPI_C_THREE), ctx->p); +} + +static void ec_invm(MPI x, MPI a, struct mpi_ec_ctx *ctx) +{ + if (!mpi_invm(x, a, ctx->p)) + log_error("ec_invm: inverse does not exist:\n"); +} + +static void mpih_set_cond(mpi_ptr_t wp, mpi_ptr_t up, + mpi_size_t usize, unsigned long set) +{ + mpi_size_t i; + mpi_limb_t mask = ((mpi_limb_t)0) - set; + mpi_limb_t x; + + for (i = 0; i < usize; i++) { + x = mask & (wp[i] ^ up[i]); + wp[i] = wp[i] ^ x; + } +} + +/* Routines for 2^255 - 19. */ + +#define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) + +static void ec_addm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519]; + mpi_limb_t borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("addm_25519: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + mpihelp_add_n(wp, up, vp, wsize); + borrow = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); +} + +static void ec_subm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519]; + mpi_limb_t borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("subm_25519: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + borrow = mpihelp_sub_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); +} + +static void ec_mulm_25519(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_25519; + mpi_limb_t n[LIMB_SIZE_25519*2]; + mpi_limb_t m[LIMB_SIZE_25519+1]; + mpi_limb_t cy; + int msb; + + (void)ctx; + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("mulm_25519: different sizes\n"); + + up = u->d; + vp = v->d; + wp = w->d; + + mpihelp_mul_n(n, up, vp, wsize); + memcpy(wp, n, wsize * BYTES_PER_MPI_LIMB); + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); + + memcpy(m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); + mpihelp_rshift(m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB)); + + memcpy(n, m, wsize * BYTES_PER_MPI_LIMB); + cy = mpihelp_lshift(m, m, LIMB_SIZE_25519, 4); + m[LIMB_SIZE_25519] = cy; + cy = mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] += cy; + cy = mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] += cy; + cy = mpihelp_add_n(m, m, n, wsize); + m[LIMB_SIZE_25519] += cy; + + cy = mpihelp_add_n(wp, wp, m, wsize); + m[LIMB_SIZE_25519] += cy; + + memset(m, 0, wsize * BYTES_PER_MPI_LIMB); + msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); + m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19; + wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); + mpihelp_add_n(wp, wp, m, wsize); + + m[0] = 0; + cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(m, ctx->p->d, wsize, (cy != 0UL)); + mpihelp_add_n(wp, wp, m, wsize); +} + +static void ec_mul2_25519(MPI w, MPI u, struct mpi_ec_ctx *ctx) +{ + ec_addm_25519(w, u, u, ctx); +} + +static void ec_pow2_25519(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + ec_mulm_25519(w, b, b, ctx); +} + +/* Routines for 2^448 - 2^224 - 1. */ + +#define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) +#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2) + +static void ec_addm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t cy; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("addm_448: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + cy = mpihelp_add_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); + mpihelp_sub_n(wp, wp, n, wsize); +} + +static void ec_subm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("subm_448: different sizes\n"); + + memset(n, 0, sizeof(n)); + up = u->d; + vp = v->d; + wp = w->d; + + borrow = mpihelp_sub_n(wp, up, vp, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (borrow != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); +} + +static void ec_mulm_448(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448*2]; + mpi_limb_t a2[LIMB_SIZE_HALF_448]; + mpi_limb_t a3[LIMB_SIZE_HALF_448]; + mpi_limb_t b0[LIMB_SIZE_HALF_448]; + mpi_limb_t b1[LIMB_SIZE_HALF_448]; + mpi_limb_t cy; + int i; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + mpi_limb_t b1_rest, a3_rest; +#endif + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug("mulm_448: different sizes\n"); + + up = u->d; + vp = v->d; + wp = w->d; + + mpihelp_mul_n(n, up, vp, wsize); + + for (i = 0; i < (wsize + 1) / 2; i++) { + b0[i] = n[i]; + b1[i] = n[i+wsize/2]; + a2[i] = n[i+wsize]; + a3[i] = n[i+wsize+wsize/2]; + } + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b0[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; + a2[LIMB_SIZE_HALF_448-1] &= ((mpi_limb_t)1UL << 32)-1; + + b1_rest = 0; + a3_rest = 0; + + for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { + mpi_limb_t b1v, a3v; + b1v = b1[i]; + a3v = a3[i]; + b1[i] = (b1_rest << 32) | (b1v >> 32); + a3[i] = (a3_rest << 32) | (a3v >> 32); + b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); + a3_rest = a3v & (((mpi_limb_t)1UL << 32)-1); + } +#endif + + cy = mpihelp_add_n(b0, b0, a2, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b0, b0, a3, LIMB_SIZE_HALF_448); + for (i = 0; i < (wsize + 1) / 2; i++) + wp[i] = b0[i]; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + wp[LIMB_SIZE_HALF_448-1] &= (((mpi_limb_t)1UL << 32)-1); +#endif + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b0[LIMB_SIZE_HALF_448-1] >> 32; +#endif + + cy = mpihelp_add_1(b1, b1, LIMB_SIZE_HALF_448, cy); + cy += mpihelp_add_n(b1, b1, a2, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); + cy += mpihelp_add_n(b1, b1, a3, LIMB_SIZE_HALF_448); +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b1_rest = 0; + for (i = (wsize + 1) / 2 - 1; i >= 0; i--) { + mpi_limb_t b1v = b1[i]; + b1[i] = (b1_rest << 32) | (b1v >> 32); + b1_rest = b1v & (((mpi_limb_t)1UL << 32)-1); + } + wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); +#endif + for (i = 0; i < wsize / 2; i++) + wp[i+(wsize + 1) / 2] = b1[i]; + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b1[LIMB_SIZE_HALF_448-1]; +#endif + + memset(n, 0, wsize * BYTES_PER_MPI_LIMB); + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + n[LIMB_SIZE_HALF_448-1] = cy << 32; +#else + n[LIMB_SIZE_HALF_448] = cy; +#endif + n[0] = cy; + mpihelp_add_n(wp, wp, n, wsize); + + memset(n, 0, wsize * BYTES_PER_MPI_LIMB); + cy = mpihelp_sub_n(wp, wp, ctx->p->d, wsize); + mpih_set_cond(n, ctx->p->d, wsize, (cy != 0UL)); + mpihelp_add_n(wp, wp, n, wsize); +} + +static void ec_mul2_448(MPI w, MPI u, struct mpi_ec_ctx *ctx) +{ + ec_addm_448(w, u, u, ctx); +} + +static void ec_pow2_448(MPI w, const MPI b, struct mpi_ec_ctx *ctx) +{ + ec_mulm_448(w, b, b, ctx); +} + +struct field_table { + const char *p; + + /* computation routines for the field. */ + void (*addm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*subm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*mulm)(MPI w, MPI u, MPI v, struct mpi_ec_ctx *ctx); + void (*mul2)(MPI w, MPI u, struct mpi_ec_ctx *ctx); + void (*pow2)(MPI w, const MPI b, struct mpi_ec_ctx *ctx); +}; + +static const struct field_table field_table[] = { + { + "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", + ec_addm_25519, + ec_subm_25519, + ec_mulm_25519, + ec_mul2_25519, + ec_pow2_25519 + }, + { + "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" + "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + ec_addm_448, + ec_subm_448, + ec_mulm_448, + ec_mul2_448, + ec_pow2_448 + }, + { NULL, NULL, NULL, NULL, NULL, NULL }, +}; + +/* Force recomputation of all helper variables. */ +static void mpi_ec_get_reset(struct mpi_ec_ctx *ec) +{ + ec->t.valid.a_is_pminus3 = 0; + ec->t.valid.two_inv_p = 0; +} + +/* Accessor for helper variable. */ +static int ec_get_a_is_pminus3(struct mpi_ec_ctx *ec) +{ + MPI tmp; + + if (!ec->t.valid.a_is_pminus3) { + ec->t.valid.a_is_pminus3 = 1; + tmp = mpi_alloc_like(ec->p); + mpi_sub_ui(tmp, ec->p, 3); + ec->t.a_is_pminus3 = !mpi_cmp(ec->a, tmp); + mpi_free(tmp); + } + + return ec->t.a_is_pminus3; +} + +/* Accessor for helper variable. */ +static MPI ec_get_two_inv_p(struct mpi_ec_ctx *ec) +{ + if (!ec->t.valid.two_inv_p) { + ec->t.valid.two_inv_p = 1; + if (!ec->t.two_inv_p) + ec->t.two_inv_p = mpi_alloc(0); + ec_invm(ec->t.two_inv_p, mpi_const(MPI_C_TWO), ec); + } + return ec->t.two_inv_p; +} + +static const char *const curve25519_bad_points[] = { + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", + "0x0000000000000000000000000000000000000000000000000000000000000000", + "0x0000000000000000000000000000000000000000000000000000000000000001", + "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0", + "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec", + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee", + NULL +}; + +static const char *const curve448_bad_points[] = { + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000001", + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe", + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "00000000000000000000000000000000000000000000000000000000", + NULL +}; + +static const char *const *bad_points_table[] = { + curve25519_bad_points, + curve448_bad_points, +}; + +static void mpi_ec_coefficient_normalize(MPI a, MPI p) +{ + if (a->sign) { + mpi_resize(a, p->nlimbs); + mpihelp_sub_n(a->d, p->d, a->d, p->nlimbs); + a->nlimbs = p->nlimbs; + a->sign = 0; + } +} + +/* This function initialized a context for elliptic curve based on the + * field GF(p). P is the prime specifying this field, A is the first + * coefficient. CTX is expected to be zeroized. + */ +void mpi_ec_init(struct mpi_ec_ctx *ctx, enum gcry_mpi_ec_models model, + enum ecc_dialects dialect, + int flags, MPI p, MPI a, MPI b) +{ + int i; + static int use_barrett = -1 /* TODO: 1 or -1 */; + + mpi_ec_coefficient_normalize(a, p); + mpi_ec_coefficient_normalize(b, p); + + /* Fixme: Do we want to check some constraints? e.g. a < p */ + + ctx->model = model; + ctx->dialect = dialect; + ctx->flags = flags; + if (dialect = ECC_DIALECT_ED25519) + ctx->nbits = 256; + else + ctx->nbits = mpi_get_nbits(p); + ctx->p = mpi_copy(p); + ctx->a = mpi_copy(a); + ctx->b = mpi_copy(b); + + ctx->t.p_barrett = use_barrett > 0 ? mpi_barrett_init(ctx->p, 0) : NULL; + + mpi_ec_get_reset(ctx); + + if (model = MPI_EC_MONTGOMERY) { + for (i = 0; i < DIM(bad_points_table); i++) { + MPI p_candidate = mpi_scanval(bad_points_table[i][0]); + int match_p = !mpi_cmp(ctx->p, p_candidate); + int j; + + mpi_free(p_candidate); + if (!match_p) + continue; + + for (j = 0; i < DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) + ctx->t.scratch[j] = mpi_scanval(bad_points_table[i][j]); + } + } else { + /* Allocate scratch variables. */ + for (i = 0; i < DIM(ctx->t.scratch); i++) + ctx->t.scratch[i] = mpi_alloc_like(ctx->p); + } + + ctx->addm = ec_addm; + ctx->subm = ec_subm; + ctx->mulm = ec_mulm; + ctx->mul2 = ec_mul2; + ctx->pow2 = ec_pow2; + + for (i = 0; field_table[i].p; i++) { + MPI f_p; + + f_p = mpi_scanval(field_table[i].p); + if (!f_p) + break; + + if (!mpi_cmp(p, f_p)) { + ctx->addm = field_table[i].addm; + ctx->subm = field_table[i].subm; + ctx->mulm = field_table[i].mulm; + ctx->mul2 = field_table[i].mul2; + ctx->pow2 = field_table[i].pow2; + mpi_free(f_p); + + mpi_resize(ctx->a, ctx->p->nlimbs); + ctx->a->nlimbs = ctx->p->nlimbs; + + mpi_resize(ctx->b, ctx->p->nlimbs); + ctx->b->nlimbs = ctx->p->nlimbs; + + for (i = 0; i < DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) + ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; + + break; + } + + mpi_free(f_p); + } +} +EXPORT_SYMBOL_GPL(mpi_ec_init); + +void mpi_ec_deinit(struct mpi_ec_ctx *ctx) +{ + int i; + + mpi_barrett_free(ctx->t.p_barrett); + + /* Domain parameter. */ + mpi_free(ctx->p); + mpi_free(ctx->a); + mpi_free(ctx->b); + mpi_point_release(ctx->G); + mpi_free(ctx->n); + + /* The key. */ + mpi_point_release(ctx->Q); + mpi_free(ctx->d); + + /* Private data of ec.c. */ + mpi_free(ctx->t.two_inv_p); + + for (i = 0; i < DIM(ctx->t.scratch); i++) + mpi_free(ctx->t.scratch[i]); +} +EXPORT_SYMBOL_GPL(mpi_ec_deinit); + +/* Compute the affine coordinates from the projective coordinates in + * POINT. Set them into X and Y. If one coordinate is not required, + * X or Y may be passed as NULL. CTX is the usual context. Returns: 0 + * on success or !0 if POINT is at infinity. + */ +int mpi_ec_get_affine(MPI x, MPI y, MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + if (!mpi_cmp_ui(point->z, 0)) + return -1; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */ + { + MPI z1, z2, z3; + + z1 = mpi_new(0); + z2 = mpi_new(0); + ec_invm(z1, point->z, ctx); /* z1 = z^(-1) mod p */ + ec_mulm(z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ + + if (x) + ec_mulm(x, point->x, z2, ctx); + + if (y) { + z3 = mpi_new(0); + ec_mulm(z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ + ec_mulm(y, point->y, z3, ctx); + mpi_free(z3); + } + + mpi_free(z2); + mpi_free(z1); + } + return 0; + + case MPI_EC_MONTGOMERY: + { + if (x) + mpi_set(x, point->x); + + if (y) { + log_fatal("%s: Getting Y-coordinate on %s is not supported\n", + "mpi_ec_get_affine", "Montgomery"); + return -1; + } + } + return 0; + + case MPI_EC_EDWARDS: + { + MPI z; + + z = mpi_new(0); + ec_invm(z, point->z, ctx); + + mpi_resize(z, ctx->p->nlimbs); + z->nlimbs = ctx->p->nlimbs; + + if (x) { + mpi_resize(x, ctx->p->nlimbs); + x->nlimbs = ctx->p->nlimbs; + ctx->mulm(x, point->x, z, ctx); + } + if (y) { + mpi_resize(y, ctx->p->nlimbs); + y->nlimbs = ctx->p->nlimbs; + ctx->mulm(y, point->y, z, ctx); + } + + mpi_free(z); + } + return 0; + + default: + return -1; + } +} +EXPORT_SYMBOL_GPL(mpi_ec_get_affine); + +/* RESULT = 2 * POINT (Weierstrass version). */ +static void dup_point_weierstrass(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define t1 (ctx->t.scratch[0]) +#define t2 (ctx->t.scratch[1]) +#define t3 (ctx->t.scratch[2]) +#define l1 (ctx->t.scratch[3]) +#define l2 (ctx->t.scratch[4]) +#define l3 (ctx->t.scratch[5]) + + if (!mpi_cmp_ui(point->y, 0) || !mpi_cmp_ui(point->z, 0)) { + /* P_y = 0 || P_z = 0 => [1:1:0] */ + mpi_set_ui(x3, 1); + mpi_set_ui(y3, 1); + mpi_set_ui(z3, 0); + } else { + if (ec_get_a_is_pminus3(ctx)) { + /* Use the faster case. */ + /* L1 = 3(X - Z^2)(X + Z^2) */ + /* T1: used for Z^2. */ + /* T2: used for the right term. */ + ec_pow2(t1, point->z, ctx); + ec_subm(l1, point->x, t1, ctx); + ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); + ec_addm(t2, point->x, t1, ctx); + ec_mulm(l1, l1, t2, ctx); + } else { + /* Standard case. */ + /* L1 = 3X^2 + aZ^4 */ + /* T1: used for aZ^4. */ + ec_pow2(l1, point->x, ctx); + ec_mulm(l1, l1, mpi_const(MPI_C_THREE), ctx); + ec_powm(t1, point->z, mpi_const(MPI_C_FOUR), ctx); + ec_mulm(t1, t1, ctx->a, ctx); + ec_addm(l1, l1, t1, ctx); + } + /* Z3 = 2YZ */ + ec_mulm(z3, point->y, point->z, ctx); + ec_mul2(z3, z3, ctx); + + /* L2 = 4XY^2 */ + /* T2: used for Y2; required later. */ + ec_pow2(t2, point->y, ctx); + ec_mulm(l2, t2, point->x, ctx); + ec_mulm(l2, l2, mpi_const(MPI_C_FOUR), ctx); + + /* X3 = L1^2 - 2L2 */ + /* T1: used for L2^2. */ + ec_pow2(x3, l1, ctx); + ec_mul2(t1, l2, ctx); + ec_subm(x3, x3, t1, ctx); + + /* L3 = 8Y^4 */ + /* T2: taken from above. */ + ec_pow2(t2, t2, ctx); + ec_mulm(l3, t2, mpi_const(MPI_C_EIGHT), ctx); + + /* Y3 = L1(L2 - X3) - L3 */ + ec_subm(y3, l2, x3, ctx); + ec_mulm(y3, y3, l1, ctx); + ec_subm(y3, y3, l3, ctx); + } + +#undef x3 +#undef y3 +#undef z3 +#undef t1 +#undef t2 +#undef t3 +#undef l1 +#undef l2 +#undef l3 +} + +/* RESULT = 2 * POINT (Montgomery version). */ +static void dup_point_montgomery(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + (void)result; + (void)point; + (void)ctx; + log_fatal("%s: %s not yet supported\n", + "mpi_ec_dup_point", "Montgomery"); +} + +/* RESULT = 2 * POINT (Twisted Edwards version). */ +static void dup_point_edwards(MPI_POINT result, + MPI_POINT point, struct mpi_ec_ctx *ctx) +{ +#define X1 (point->x) +#define Y1 (point->y) +#define Z1 (point->z) +#define X3 (result->x) +#define Y3 (result->y) +#define Z3 (result->z) +#define B (ctx->t.scratch[0]) +#define C (ctx->t.scratch[1]) +#define D (ctx->t.scratch[2]) +#define E (ctx->t.scratch[3]) +#define F (ctx->t.scratch[4]) +#define H (ctx->t.scratch[5]) +#define J (ctx->t.scratch[6]) + + /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */ + + /* B = (X_1 + Y_1)^2 */ + ctx->addm(B, X1, Y1, ctx); + ctx->pow2(B, B, ctx); + + /* C = X_1^2 */ + /* D = Y_1^2 */ + ctx->pow2(C, X1, ctx); + ctx->pow2(D, Y1, ctx); + + /* E = aC */ + if (ctx->dialect = ECC_DIALECT_ED25519) + ctx->subm(E, ctx->p, C, ctx); + else + ctx->mulm(E, ctx->a, C, ctx); + + /* F = E + D */ + ctx->addm(F, E, D, ctx); + + /* H = Z_1^2 */ + ctx->pow2(H, Z1, ctx); + + /* J = F - 2H */ + ctx->mul2(J, H, ctx); + ctx->subm(J, F, J, ctx); + + /* X_3 = (B - C - D) · J */ + ctx->subm(X3, B, C, ctx); + ctx->subm(X3, X3, D, ctx); + ctx->mulm(X3, X3, J, ctx); + + /* Y_3 = F · (E - D) */ + ctx->subm(Y3, E, D, ctx); + ctx->mulm(Y3, Y3, F, ctx); + + /* Z_3 = F · J */ + ctx->mulm(Z3, F, J, ctx); + +#undef X1 +#undef Y1 +#undef Z1 +#undef X3 +#undef Y3 +#undef Z3 +#undef B +#undef C +#undef D +#undef E +#undef F +#undef H +#undef J +} + +/* RESULT = 2 * POINT */ +static void +mpi_ec_dup_point(MPI_POINT result, MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + dup_point_weierstrass(result, point, ctx); + break; + case MPI_EC_MONTGOMERY: + dup_point_montgomery(result, point, ctx); + break; + case MPI_EC_EDWARDS: + dup_point_edwards(result, point, ctx); + break; + } +} + +/* RESULT = P1 + P2 (Weierstrass version).*/ +static void add_points_weierstrass(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ +#define x1 (p1->x) +#define y1 (p1->y) +#define z1 (p1->z) +#define x2 (p2->x) +#define y2 (p2->y) +#define z2 (p2->z) +#define x3 (result->x) +#define y3 (result->y) +#define z3 (result->z) +#define l1 (ctx->t.scratch[0]) +#define l2 (ctx->t.scratch[1]) +#define l3 (ctx->t.scratch[2]) +#define l4 (ctx->t.scratch[3]) +#define l5 (ctx->t.scratch[4]) +#define l6 (ctx->t.scratch[5]) +#define l7 (ctx->t.scratch[6]) +#define l8 (ctx->t.scratch[7]) +#define l9 (ctx->t.scratch[8]) +#define t1 (ctx->t.scratch[9]) +#define t2 (ctx->t.scratch[10]) + + if ((!mpi_cmp(x1, x2)) && (!mpi_cmp(y1, y2)) && (!mpi_cmp(z1, z2))) { + /* Same point; need to call the duplicate function. */ + mpi_ec_dup_point(result, p1, ctx); + } else if (!mpi_cmp_ui(z1, 0)) { + /* P1 is at infinity. */ + mpi_set(x3, p2->x); + mpi_set(y3, p2->y); + mpi_set(z3, p2->z); + } else if (!mpi_cmp_ui(z2, 0)) { + /* P2 is at infinity. */ + mpi_set(x3, p1->x); + mpi_set(y3, p1->y); + mpi_set(z3, p1->z); + } else { + int z1_is_one = !mpi_cmp_ui(z1, 1); + int z2_is_one = !mpi_cmp_ui(z2, 1); + + /* l1 = x1 z2^2 */ + /* l2 = x2 z1^2 */ + if (z2_is_one) + mpi_set(l1, x1); + else { + ec_pow2(l1, z2, ctx); + ec_mulm(l1, l1, x1, ctx); + } + if (z1_is_one) + mpi_set(l2, x2); + else { + ec_pow2(l2, z1, ctx); + ec_mulm(l2, l2, x2, ctx); + } + /* l3 = l1 - l2 */ + ec_subm(l3, l1, l2, ctx); + /* l4 = y1 z2^3 */ + ec_powm(l4, z2, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l4, l4, y1, ctx); + /* l5 = y2 z1^3 */ + ec_powm(l5, z1, mpi_const(MPI_C_THREE), ctx); + ec_mulm(l5, l5, y2, ctx); + /* l6 = l4 - l5 */ + ec_subm(l6, l4, l5, ctx); + + if (!mpi_cmp_ui(l3, 0)) { + if (!mpi_cmp_ui(l6, 0)) { + /* P1 and P2 are the same - use duplicate function. */ + mpi_ec_dup_point(result, p1, ctx); + } else { + /* P1 is the inverse of P2. */ + mpi_set_ui(x3, 1); + mpi_set_ui(y3, 1); + mpi_set_ui(z3, 0); + } + } else { + /* l7 = l1 + l2 */ + ec_addm(l7, l1, l2, ctx); + /* l8 = l4 + l5 */ + ec_addm(l8, l4, l5, ctx); + /* z3 = z1 z2 l3 */ + ec_mulm(z3, z1, z2, ctx); + ec_mulm(z3, z3, l3, ctx); + /* x3 = l6^2 - l7 l3^2 */ + ec_pow2(t1, l6, ctx); + ec_pow2(t2, l3, ctx); + ec_mulm(t2, t2, l7, ctx); + ec_subm(x3, t1, t2, ctx); + /* l9 = l7 l3^2 - 2 x3 */ + ec_mul2(t1, x3, ctx); + ec_subm(l9, t2, t1, ctx); + /* y3 = (l9 l6 - l8 l3^3)/2 */ + ec_mulm(l9, l9, l6, ctx); + ec_powm(t1, l3, mpi_const(MPI_C_THREE), ctx); /* fixme: Use saved value*/ + ec_mulm(t1, t1, l8, ctx); + ec_subm(y3, l9, t1, ctx); + ec_mulm(y3, y3, ec_get_two_inv_p(ctx), ctx); + } + } + +#undef x1 +#undef y1 +#undef z1 +#undef x2 +#undef y2 +#undef z2 +#undef x3 +#undef y3 +#undef z3 +#undef l1 +#undef l2 +#undef l3 +#undef l4 +#undef l5 +#undef l6 +#undef l7 +#undef l8 +#undef l9 +#undef t1 +#undef t2 +} + +/* RESULT = P1 + P2 (Montgomery version).*/ +static void add_points_montgomery(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ + (void)result; + (void)p1; + (void)p2; + (void)ctx; + log_fatal("%s: %s not yet supported\n", + "mpi_ec_add_points", "Montgomery"); +} + +/* RESULT = P1 + P2 (Twisted Edwards version).*/ +static void add_points_edwards(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ +#define X1 (p1->x) +#define Y1 (p1->y) +#define Z1 (p1->z) +#define X2 (p2->x) +#define Y2 (p2->y) +#define Z2 (p2->z) +#define X3 (result->x) +#define Y3 (result->y) +#define Z3 (result->z) +#define A (ctx->t.scratch[0]) +#define B (ctx->t.scratch[1]) +#define C (ctx->t.scratch[2]) +#define D (ctx->t.scratch[3]) +#define E (ctx->t.scratch[4]) +#define F (ctx->t.scratch[5]) +#define G (ctx->t.scratch[6]) +#define tmp (ctx->t.scratch[7]) + + point_resize(result, ctx); + + /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */ + + /* A = Z1 · Z2 */ + ctx->mulm(A, Z1, Z2, ctx); + + /* B = A^2 */ + ctx->pow2(B, A, ctx); + + /* C = X1 · X2 */ + ctx->mulm(C, X1, X2, ctx); + + /* D = Y1 · Y2 */ + ctx->mulm(D, Y1, Y2, ctx); + + /* E = d · C · D */ + ctx->mulm(E, ctx->b, C, ctx); + ctx->mulm(E, E, D, ctx); + + /* F = B - E */ + ctx->subm(F, B, E, ctx); + + /* G = B + E */ + ctx->addm(G, B, E, ctx); + + /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ + ctx->addm(tmp, X1, Y1, ctx); + ctx->addm(X3, X2, Y2, ctx); + ctx->mulm(X3, X3, tmp, ctx); + ctx->subm(X3, X3, C, ctx); + ctx->subm(X3, X3, D, ctx); + ctx->mulm(X3, X3, F, ctx); + ctx->mulm(X3, X3, A, ctx); + + /* Y_3 = A · G · (D - aC) */ + if (ctx->dialect = ECC_DIALECT_ED25519) { + ctx->addm(Y3, D, C, ctx); + } else { + ctx->mulm(Y3, ctx->a, C, ctx); + ctx->subm(Y3, D, Y3, ctx); + } + ctx->mulm(Y3, Y3, G, ctx); + ctx->mulm(Y3, Y3, A, ctx); + + /* Z_3 = F · G */ + ctx->mulm(Z3, F, G, ctx); + + +#undef X1 +#undef Y1 +#undef Z1 +#undef X2 +#undef Y2 +#undef Z2 +#undef X3 +#undef Y3 +#undef Z3 +#undef A +#undef B +#undef C +#undef D +#undef E +#undef F +#undef G +#undef tmp +} + +/* Compute a step of Montgomery Ladder (only use X and Z in the point). + * Inputs: P1, P2, and x-coordinate of DIF = P1 - P1. + * Outputs: PRD = 2 * P1 and SUM = P1 + P2. + */ +static void montgomery_ladder(MPI_POINT prd, MPI_POINT sum, + MPI_POINT p1, MPI_POINT p2, MPI dif_x, + struct mpi_ec_ctx *ctx) +{ + ctx->addm(sum->x, p2->x, p2->z, ctx); + ctx->subm(p2->z, p2->x, p2->z, ctx); + ctx->addm(prd->x, p1->x, p1->z, ctx); + ctx->subm(p1->z, p1->x, p1->z, ctx); + ctx->mulm(p2->x, p1->z, sum->x, ctx); + ctx->mulm(p2->z, prd->x, p2->z, ctx); + ctx->pow2(p1->x, prd->x, ctx); + ctx->pow2(p1->z, p1->z, ctx); + ctx->addm(sum->x, p2->x, p2->z, ctx); + ctx->subm(p2->z, p2->x, p2->z, ctx); + ctx->mulm(prd->x, p1->x, p1->z, ctx); + ctx->subm(p1->z, p1->x, p1->z, ctx); + ctx->pow2(sum->x, sum->x, ctx); + ctx->pow2(sum->z, p2->z, ctx); + ctx->mulm(prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ + ctx->mulm(sum->z, sum->z, dif_x, ctx); + ctx->addm(prd->z, p1->x, prd->z, ctx); + ctx->mulm(prd->z, prd->z, p1->z, ctx); +} + +/* RESULT = P1 + P2 */ +void mpi_ec_add_points(MPI_POINT result, + MPI_POINT p1, MPI_POINT p2, + struct mpi_ec_ctx *ctx) +{ + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + add_points_weierstrass(result, p1, p2, ctx); + break; + case MPI_EC_MONTGOMERY: + add_points_montgomery(result, p1, p2, ctx); + break; + case MPI_EC_EDWARDS: + add_points_edwards(result, p1, p2, ctx); + break; + } +} +EXPORT_SYMBOL_GPL(mpi_ec_add_points); + +/* Scalar point multiplication - the main function for ECC. If takes + * an integer SCALAR and a POINT as well as the usual context CTX. + * RESULT will be set to the resulting point. + */ +void mpi_ec_mul_point(MPI_POINT result, + MPI scalar, MPI_POINT point, + struct mpi_ec_ctx *ctx) +{ + MPI x1, y1, z1, k, h, yy; + unsigned int i, loops; + struct gcry_mpi_point p1, p2, p1inv; + + if (ctx->model = MPI_EC_EDWARDS) { + /* Simple left to right binary method. Algorithm 3.27 from + * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott}, + * title = {Guide to Elliptic Curve Cryptography}, + * year = {2003}, isbn = {038795273X}, + * url = {http://www.cacr.math.uwaterloo.ca/ecc/}, + * publisher = {Springer-Verlag New York, Inc.}} + */ + unsigned int nbits; + int j; + + if (mpi_cmp(scalar, ctx->p) >= 0) + nbits = mpi_get_nbits(scalar); + else + nbits = mpi_get_nbits(ctx->p); + + mpi_set_ui(result->x, 0); + mpi_set_ui(result->y, 1); + mpi_set_ui(result->z, 1); + point_resize(point, ctx); + + point_resize(result, ctx); + point_resize(point, ctx); + + for (j = nbits-1; j >= 0; j--) { + mpi_ec_dup_point(result, result, ctx); + if (mpi_test_bit(scalar, j)) + mpi_ec_add_points(result, result, point, ctx); + } + return; + } else if (ctx->model = MPI_EC_MONTGOMERY) { + unsigned int nbits; + int j; + struct gcry_mpi_point p1_, p2_; + MPI_POINT q1, q2, prd, sum; + unsigned long sw; + mpi_size_t rsize; + int scalar_copied = 0; + + /* Compute scalar point multiplication with Montgomery Ladder. + * Note that we don't use Y-coordinate in the points at all. + * RESULT->Y will be filled by zero. + */ + + nbits = mpi_get_nbits(scalar); + point_init(&p1); + point_init(&p2); + point_init(&p1_); + point_init(&p2_); + mpi_set_ui(p1.x, 1); + mpi_free(p2.x); + p2.x = mpi_copy(point->x); + mpi_set_ui(p2.z, 1); + + point_resize(&p1, ctx); + point_resize(&p2, ctx); + point_resize(&p1_, ctx); + point_resize(&p2_, ctx); + + mpi_resize(point->x, ctx->p->nlimbs); + point->x->nlimbs = ctx->p->nlimbs; + + q1 = &p1; + q2 = &p2; + prd = &p1_; + sum = &p2_; + + for (j = nbits-1; j >= 0; j--) { + MPI_POINT t; + + sw = mpi_test_bit(scalar, j); + point_swap_cond(q1, q2, sw, ctx); + montgomery_ladder(prd, sum, q1, q2, point->x, ctx); + point_swap_cond(prd, sum, sw, ctx); + t = q1; q1 = prd; prd = t; + t = q2; q2 = sum; sum = t; + } + + mpi_clear(result->y); + sw = (nbits & 1); + point_swap_cond(&p1, &p1_, sw, ctx); + + rsize = p1.z->nlimbs; + MPN_NORMALIZE(p1.z->d, rsize); + if (rsize = 0) { + mpi_set_ui(result->x, 1); + mpi_set_ui(result->z, 0); + } else { + z1 = mpi_new(0); + ec_invm(z1, p1.z, ctx); + ec_mulm(result->x, p1.x, z1, ctx); + mpi_set_ui(result->z, 1); + mpi_free(z1); + } + + point_free(&p1); + point_free(&p2); + point_free(&p1_); + point_free(&p2_); + if (scalar_copied) + mpi_free(scalar); + return; + } + + x1 = mpi_alloc_like(ctx->p); + y1 = mpi_alloc_like(ctx->p); + h = mpi_alloc_like(ctx->p); + k = mpi_copy(scalar); + yy = mpi_copy(point->y); + + if (mpi_has_sign(k)) { + k->sign = 0; + ec_invm(yy, yy, ctx); + } + + if (!mpi_cmp_ui(point->z, 1)) { + mpi_set(x1, point->x); + mpi_set(y1, yy); + } else { + MPI z2, z3; + + z2 = mpi_alloc_like(ctx->p); + z3 = mpi_alloc_like(ctx->p); + ec_mulm(z2, point->z, point->z, ctx); + ec_mulm(z3, point->z, z2, ctx); + ec_invm(z2, z2, ctx); + ec_mulm(x1, point->x, z2, ctx); + ec_invm(z3, z3, ctx); + ec_mulm(y1, yy, z3, ctx); + mpi_free(z2); + mpi_free(z3); + } + z1 = mpi_copy(mpi_const(MPI_C_ONE)); + + mpi_mul(h, k, mpi_const(MPI_C_THREE)); /* h = 3k */ + loops = mpi_get_nbits(h); + if (loops < 2) { + /* If SCALAR is zero, the above mpi_mul sets H to zero and thus + * LOOPs will be zero. To avoid an underflow of I in the main + * loop we set LOOP to 2 and the result to (0,0,0). + */ + loops = 2; + mpi_clear(result->x); + mpi_clear(result->y); + mpi_clear(result->z); + } else { + mpi_set(result->x, point->x); + mpi_set(result->y, yy); + mpi_set(result->z, point->z); + } + mpi_free(yy); yy = NULL; + + p1.x = x1; x1 = NULL; + p1.y = y1; y1 = NULL; + p1.z = z1; z1 = NULL; + point_init(&p2); + point_init(&p1inv); + + /* Invert point: y = p - y mod p */ + point_set(&p1inv, &p1); + ec_subm(p1inv.y, ctx->p, p1inv.y, ctx); + + for (i = loops-2; i > 0; i--) { + mpi_ec_dup_point(result, result, ctx); + if (mpi_test_bit(h, i) = 1 && mpi_test_bit(k, i) = 0) { + point_set(&p2, result); + mpi_ec_add_points(result, &p2, &p1, ctx); + } + if (mpi_test_bit(h, i) = 0 && mpi_test_bit(k, i) = 1) { + point_set(&p2, result); + mpi_ec_add_points(result, &p2, &p1inv, ctx); + } + } + + point_free(&p1); + point_free(&p2); + point_free(&p1inv); + mpi_free(h); + mpi_free(k); +} +EXPORT_SYMBOL_GPL(mpi_ec_mul_point); + +/* Return true if POINT is on the curve described by CTX. */ +int mpi_ec_curve_point(MPI_POINT point, struct mpi_ec_ctx *ctx) +{ + int res = 0; + MPI x, y, w; + + x = mpi_new(0); + y = mpi_new(0); + w = mpi_new(0); + + /* Check that the point is in range. This needs to be done here and + * not after conversion to affine coordinates. + */ + if (mpi_cmpabs(point->x, ctx->p) >= 0) + goto leave; + if (mpi_cmpabs(point->y, ctx->p) >= 0) + goto leave; + if (mpi_cmpabs(point->z, ctx->p) >= 0) + goto leave; + + switch (ctx->model) { + case MPI_EC_WEIERSTRASS: + { + MPI xxx; + + if (mpi_ec_get_affine(x, y, point, ctx)) + goto leave; + + xxx = mpi_new(0); + + /* y^2 = x^3 + a·x + b */ + ec_pow2(y, y, ctx); + + ec_pow3(xxx, x, ctx); + ec_mulm(w, ctx->a, x, ctx); + ec_addm(w, w, ctx->b, ctx); + ec_addm(w, w, xxx, ctx); + + if (!mpi_cmp(y, w)) + res = 1; + + mpi_free(xxx); + } + break; + + case MPI_EC_MONTGOMERY: + { +#define xx y + /* With Montgomery curve, only X-coordinate is valid. */ + if (mpi_ec_get_affine(x, NULL, point, ctx)) + goto leave; + + /* The equation is: b * y^2 = x^3 + a · x^2 + x */ + /* We check if right hand is quadratic residue or not by + * Euler's criterion. + */ + /* CTX->A has (a-2)/4 and CTX->B has b^-1 */ + ec_mulm(w, ctx->a, mpi_const(MPI_C_FOUR), ctx); + ec_addm(w, w, mpi_const(MPI_C_TWO), ctx); + ec_mulm(w, w, x, ctx); + ec_pow2(xx, x, ctx); + ec_addm(w, w, xx, ctx); + ec_addm(w, w, mpi_const(MPI_C_ONE), ctx); + ec_mulm(w, w, x, ctx); + ec_mulm(w, w, ctx->b, ctx); +#undef xx + /* Compute Euler's criterion: w^(p-1)/2 */ +#define p_minus1 y + ec_subm(p_minus1, ctx->p, mpi_const(MPI_C_ONE), ctx); + mpi_rshift(p_minus1, p_minus1, 1); + ec_powm(w, w, p_minus1, ctx); + + res = !mpi_cmp_ui(w, 1); +#undef p_minus1 + } + break; + + case MPI_EC_EDWARDS: + { + if (mpi_ec_get_affine(x, y, point, ctx)) + goto leave; + + mpi_resize(w, ctx->p->nlimbs); + w->nlimbs = ctx->p->nlimbs; + + /* a · x^2 + y^2 - 1 - b · x^2 · y^2 = 0 */ + ctx->pow2(x, x, ctx); + ctx->pow2(y, y, ctx); + if (ctx->dialect = ECC_DIALECT_ED25519) + ctx->subm(w, ctx->p, x, ctx); + else + ctx->mulm(w, ctx->a, x, ctx); + ctx->addm(w, w, y, ctx); + ctx->mulm(x, x, y, ctx); + ctx->mulm(x, x, ctx->b, ctx); + ctx->subm(w, w, x, ctx); + if (!mpi_cmp_ui(w, 1)) + res = 1; + } + break; + } + +leave: + mpi_free(w); + mpi_free(x); + mpi_free(y); + + return res; +} +EXPORT_SYMBOL_GPL(mpi_ec_curve_point); -- 2.19.1.3.ge56e4f7 From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-13.0 required=3.0 tests=BAYES_00,DKIMWL_WL_HIGH, DKIM_SIGNED,DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH, MAILING_LIST_MULTI,SIGNED_OFF_BY,SPF_HELO_NONE,SPF_PASS,UNPARSEABLE_RELAY, URIBL_BLOCKED,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 88882C433E9 for ; Thu, 3 Sep 2020 13:14:44 +0000 (UTC) Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 2152F20758 for ; Thu, 3 Sep 2020 13:14:44 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=lists.infradead.org header.i=@lists.infradead.org header.b="LhfHTd8d" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org 2152F20758 Authentication-Results: mail.kernel.org; dmarc=fail (p=none dis=none) header.from=linux.alibaba.com Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=merlin.20170209; h=Sender:Content-Transfer-Encoding: Content-Type:Cc:List-Subscribe:List-Help:List-Post:List-Archive: List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To:Message-Id:Date: Subject:To:From:Reply-To:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Owner; bh=iv9s0qUwHSXC0UN/EeBOL1ccMUxDbep8gcQ8pXq2BaQ=; b=LhfHTd8d1lw1D/rqEetHt+eE4 ZcCN19R++0JcsEP2k0wkybYQjAEKoABerDLhjz4VkUsXe9ksf4NJI25I8bLe9JN1jtIYMv+iMZ2P0 0Bb64EgqZEA6mG33ArsQnvoH17Qh6Z0nlxnl3W2ciD3RbCsupNRd4/+7Ml88IjT8/JNa8b/jCC2B5 NHKYbrSZZfY3Fy0kRFdeEPU2ngzzH59K9tcFRREFMrHb6R7pRP7f/6exyU/dSgD/xkQWAMXj1wRKE 4BmTbytH2GfJ83FPVHrczk+ls7EI2aQMxGRrDZYCpj6dRvldcQCNtU6M/Lca2sMpT9aNLf0xGfaeE /lC05i6nQ==; Received: from localhost ([::1] helo=merlin.infradead.org) by merlin.infradead.org with esmtp (Exim 4.92.3 #3 (Red Hat Linux)) id 1kDp3G-0003Cy-2G; Thu, 03 Sep 2020 13:13:18 +0000 Received: from out30-133.freemail.mail.aliyun.com ([115.124.30.133]) by merlin.infradead.org with esmtps (Exim 4.92.3 #3 (Red Hat Linux)) id 1kDp2z-000384-Dp for linux-arm-kernel@lists.infradead.org; Thu, 03 Sep 2020 13:13:08 +0000 X-Alimail-AntiSpam: AC=PASS; BC=-1|-1; BR=01201311R241e4; CH=green; DM=||false|; DS=||; FP=0|-1|-1|-1|0|-1|-1|-1; HT=e01e01355; MF=tianjia.zhang@linux.alibaba.com; NM=1; PH=DS; RN=31; SR=0; TI=SMTPD_---0U7ok5HV_1599138764; Received: from localhost(mailfrom:tianjia.zhang@linux.alibaba.com fp:SMTPD_---0U7ok5HV_1599138764) by smtp.aliyun-inc.com(127.0.0.1); Thu, 03 Sep 2020 21:12:44 +0800 From: Tianjia Zhang To: Herbert Xu , "David S. Miller" , David Howells , Maxime Coquelin , Alexandre Torgue , James Morris , "Serge E. Hallyn" , Stephan Mueller , Marcelo Henrique Cerri , "Steven Rostedt (VMware)" , Masahiro Yamada , Brendan Higgins , Andrew Morton , Johannes Weiner , Waiman Long , Mimi Zohar , Lakshmi Ramasubramanian , Colin Ian King , Tushar Sugandhi , Vitaly Chikunov , "Gilad Ben-Yossef" , Pascal van Leeuwen , linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org, keyrings@vger.kernel.org, linux-stm32@st-md-mailman.stormreply.com, linux-arm-kernel@lists.infradead.org, linux-security-module@vger.kernel.org Subject: [PATCH v6 3/8] lib/mpi: Introduce ec implementation to MPI library Date: Thu, 3 Sep 2020 21:12:37 +0800 Message-Id: <20200903131242.128665-4-tianjia.zhang@linux.alibaba.com> X-Mailer: git-send-email 2.19.1.3.ge56e4f7 In-Reply-To: <20200903131242.128665-1-tianjia.zhang@linux.alibaba.com> References: <20200903131242.128665-1-tianjia.zhang@linux.alibaba.com> MIME-Version: 1.0 X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20200903_091302_586233_0C9FFA07 X-CRM114-Status: GOOD ( 29.20 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Xufeng Zhang , Tianjia Zhang , Jia Zhang Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: base64 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org VGhlIGltcGxlbWVudGF0aW9uIG9mIEVDIGlzIGludHJvZHVjZWQgZnJvbSBsaWJnY3J5cHQgYXMg dGhlCmJhc2ljIGFsZ29yaXRobSBvZiBlbGxpcHRpYyBjdXJ2ZSwgd2hpY2ggY2FuIGJlIG1vcmUg cGVyZmVjdGx5CmludGVncmF0ZWQgd2l0aCBNUEkgaW1wbGVtZW50YXRpb24uClNvbWUgb3RoZXIg YWxnb3JpdGhtcyB3aWxsIGJlIGRldmVsb3BlZCBiYXNlZCBvbiBtcGkgZWNjLCBzdWNoIGFzIFNN Mi4KClNpZ25lZC1vZmYtYnk6IFRpYW5qaWEgWmhhbmcgPHRpYW5qaWEuemhhbmdAbGludXguYWxp YmFiYS5jb20+ClRlc3RlZC1ieTogWHVmZW5nIFpoYW5nIDx5dW5iby54dWZlbmdAbGludXguYWxp YmFiYS5jb20+Ci0tLQogaW5jbHVkZS9saW51eC9tcGkuaCB8ICAxMDUgKysrCiBsaWIvbXBpL01h a2VmaWxlICAgIHwgICAgMSArCiBsaWIvbXBpL2VjLmMgICAgICAgIHwgMTUwOSArKysrKysrKysr KysrKysrKysrKysrKysrKysrKysrKysrKysrKysrKysrCiAzIGZpbGVzIGNoYW5nZWQsIDE2MTUg aW5zZXJ0aW9ucygrKQogY3JlYXRlIG1vZGUgMTAwNjQ0IGxpYi9tcGkvZWMuYwoKZGlmZiAtLWdp dCBhL2luY2x1ZGUvbGludXgvbXBpLmggYi9pbmNsdWRlL2xpbnV4L21waS5oCmluZGV4IDNjOWU0 MTYwM2NmNi4uM2U1MzU4ZjRkZTJmIDEwMDY0NAotLS0gYS9pbmNsdWRlL2xpbnV4L21waS5oCisr KyBiL2luY2x1ZGUvbGludXgvbXBpLmgKQEAgLTE1Nyw2ICsxNTcsMTExIEBAIHZvaWQgbXBpX2Zk aXZfcShNUEkgcXVvdCwgTVBJIGRpdmlkZW5kLCBNUEkgZGl2aXNvcik7CiAvKi0tIG1waS1pbnYu YyAtLSovCiBpbnQgbXBpX2ludm0oTVBJIHgsIE1QSSBhLCBNUEkgbik7CiAKKy8qLS0gZWMuYyAt LSovCisKKy8qIE9iamVjdCB0byByZXByZXNlbnQgYSBwb2ludCBpbiBwcm9qZWN0aXZlIGNvb3Jk aW5hdGVzICovCitzdHJ1Y3QgZ2NyeV9tcGlfcG9pbnQgeworCU1QSSB4OworCU1QSSB5OworCU1Q SSB6OworfTsKKwordHlwZWRlZiBzdHJ1Y3QgZ2NyeV9tcGlfcG9pbnQgKk1QSV9QT0lOVDsKKwor LyogTW9kZWxzIGRlc2NyaWJpbmcgYW4gZWxsaXB0aWMgY3VydmUgKi8KK2VudW0gZ2NyeV9tcGlf ZWNfbW9kZWxzIHsKKwkvKiBUaGUgU2hvcnQgV2VpZXJzdHJhc3MgZXF1YXRpb24gaXMKKwkgKiAg ICAgIHleMiA9IHheMyArIGF4ICsgYgorCSAqLworCU1QSV9FQ19XRUlFUlNUUkFTUyA9IDAsCisJ LyogVGhlIE1vbnRnb21lcnkgZXF1YXRpb24gaXMKKwkgKiAgICAgIGJ5XjIgPSB4XjMgKyBheF4y ICsgeAorCSAqLworCU1QSV9FQ19NT05UR09NRVJZLAorCS8qIFRoZSBUd2lzdGVkIEVkd2FyZHMg ZXF1YXRpb24gaXMKKwkgKiAgICAgIGF4XjIgKyB5XjIgPSAxICsgYnheMnleMgorCSAqIE5vdGUg dGhhdCB3ZSB1c2UgJ2InIGluc3RlYWQgb2YgdGhlIGNvbW1vbmx5IHVzZWQgJ2QnLgorCSAqLwor CU1QSV9FQ19FRFdBUkRTCit9OworCisvKiBEaWFsZWN0cyB1c2VkIHdpdGggZWxsaXB0aWMgY3Vy dmVzICovCitlbnVtIGVjY19kaWFsZWN0cyB7CisJRUNDX0RJQUxFQ1RfU1RBTkRBUkQgPSAwLAor CUVDQ19ESUFMRUNUX0VEMjU1MTksCisJRUNDX0RJQUxFQ1RfU0FGRUNVUlZFCit9OworCisvKiBU aGlzIGNvbnRleHQgaXMgdXNlZCB3aXRoIGFsbCBvdXIgRUMgZnVuY3Rpb25zLiAqLworc3RydWN0 IG1waV9lY19jdHggeworCWVudW0gZ2NyeV9tcGlfZWNfbW9kZWxzIG1vZGVsOyAvKiBUaGUgbW9k ZWwgZGVzY3JpYmluZyB0aGlzIGN1cnZlLiAqLworCWVudW0gZWNjX2RpYWxlY3RzIGRpYWxlY3Q7 ICAgICAvKiBUaGUgRUNDIGRpYWxlY3QgdXNlZCB3aXRoIHRoZSBjdXJ2ZS4gKi8KKwlpbnQgZmxh Z3M7ICAgICAgICAgICAgICAgICAgICAgLyogUHVibGljIGtleSBmbGFncyAobm90IGFsd2F5cyB1 c2VkKS4gKi8KKwl1bnNpZ25lZCBpbnQgbmJpdHM7ICAgICAgICAgICAgLyogTnVtYmVyIG9mIGJp dHMuICAqLworCisJLyogRG9tYWluIHBhcmFtZXRlcnMuICBOb3RlIHRoYXQgdGhleSBtYXkgbm90 IGFsbCBiZSBzZXQgYW5kIGlmIHNldAorCSAqIHRoZSBNUElzIG1heSBiZSBmbGFnZWQgYXMgY29u c3RhbnQuCisJICovCisJTVBJIHA7ICAgICAgICAgLyogUHJpbWUgc3BlY2lmeWluZyB0aGUgZmll bGQgR0YocCkuICAqLworCU1QSSBhOyAgICAgICAgIC8qIEZpcnN0IGNvZWZmaWNpZW50IG9mIHRo ZSBXZWllcnN0cmFzcyBlcXVhdGlvbi4gICovCisJTVBJIGI7ICAgICAgICAgLyogU2Vjb25kIGNv ZWZmaWNpZW50IG9mIHRoZSBXZWllcnN0cmFzcyBlcXVhdGlvbi4gICovCisJTVBJX1BPSU5UIEc7 ICAgLyogQmFzZSBwb2ludCAoZ2VuZXJhdG9yKS4gICovCisJTVBJIG47ICAgICAgICAgLyogT3Jk ZXIgb2YgRy4gICovCisJdW5zaWduZWQgaW50IGg7ICAgICAgIC8qIENvZmFjdG9yLiAgKi8KKwor CS8qIFRoZSBhY3R1YWwga2V5LiAgTWF5IG5vdCBiZSBzZXQuICAqLworCU1QSV9QT0lOVCBROyAg IC8qIFB1YmxpYyBrZXkuICAgKi8KKwlNUEkgZDsgICAgICAgICAvKiBQcml2YXRlIGtleS4gICov CisKKwljb25zdCBjaGFyICpuYW1lOyAgICAgIC8qIE5hbWUgb2YgdGhlIGN1cnZlLiAgKi8KKwor CS8qIFRoaXMgc3RydWN0dXJlIGlzIHByaXZhdGUgdG8gbXBpL2VjLmMhICovCisJc3RydWN0IHsK KwkJc3RydWN0IHsKKwkJCXVuc2lnbmVkIGludCBhX2lzX3BtaW51czM6MTsKKwkJCXVuc2lnbmVk IGludCB0d29faW52X3A6MTsKKwkJfSB2YWxpZDsgLyogRmxhZ3MgdG8gaGVscCBzZXR0aW5nIHRo ZSBoZWxwZXIgdmFycyBiZWxvdy4gICovCisKKwkJaW50IGFfaXNfcG1pbnVzMzsgIC8qIFRydWUg aWYgQSA9IFAgLSAzLiAqLworCisJCU1QSSB0d29faW52X3A7CisKKwkJbXBpX2JhcnJldHRfdCBw X2JhcnJldHQ7CisKKwkJLyogU2NyYXRjaCB2YXJpYWJsZXMuICAqLworCQlNUEkgc2NyYXRjaFsx MV07CisKKwkJLyogSGVscGVyIGZvciBmYXN0IHJlZHVjdGlvbi4gICovCisJCS8qICAgaW50IG5p c3RfbmJpdHM7IC9cKiBJZiB0aGlzIGlzIGEgTklTVCBjdXJ2ZSwgdGhlICMgb2YgYml0cy4gKlwv ICovCisJCS8qICAgTVBJIHNbMTBdOyAqLworCQkvKiAgIE1QSSBjOyAqLworCX0gdDsKKworCS8q IEN1cnZlIHNwZWNpZmljIGNvbXB1dGF0aW9uIHJvdXRpbmVzIGZvciB0aGUgZmllbGQuICAqLwor CXZvaWQgKCphZGRtKShNUEkgdywgTVBJIHUsIE1QSSB2LCBzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4 KTsKKwl2b2lkICgqc3VibSkoTVBJIHcsIE1QSSB1LCBNUEkgdiwgc3RydWN0IG1waV9lY19jdHgg KmVjKTsKKwl2b2lkICgqbXVsbSkoTVBJIHcsIE1QSSB1LCBNUEkgdiwgc3RydWN0IG1waV9lY19j dHggKmN0eCk7CisJdm9pZCAoKnBvdzIpKE1QSSB3LCBjb25zdCBNUEkgYiwgc3RydWN0IG1waV9l Y19jdHggKmN0eCk7CisJdm9pZCAoKm11bDIpKE1QSSB3LCBNUEkgdSwgc3RydWN0IG1waV9lY19j dHggKmN0eCk7Cit9OworCit2b2lkIG1waV9lY19pbml0KHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgs IGVudW0gZ2NyeV9tcGlfZWNfbW9kZWxzIG1vZGVsLAorCQkJZW51bSBlY2NfZGlhbGVjdHMgZGlh bGVjdCwKKwkJCWludCBmbGFncywgTVBJIHAsIE1QSSBhLCBNUEkgYik7Cit2b2lkIG1waV9lY19k ZWluaXQoc3RydWN0IG1waV9lY19jdHggKmN0eCk7CitNUElfUE9JTlQgbXBpX3BvaW50X25ldyh1 bnNpZ25lZCBpbnQgbmJpdHMpOwordm9pZCBtcGlfcG9pbnRfcmVsZWFzZShNUElfUE9JTlQgcCk7 Cit2b2lkIG1waV9wb2ludF9pbml0KE1QSV9QT0lOVCBwKTsKK3ZvaWQgbXBpX3BvaW50X2ZyZWVf cGFydHMoTVBJX1BPSU5UIHApOworaW50IG1waV9lY19nZXRfYWZmaW5lKE1QSSB4LCBNUEkgeSwg TVBJX1BPSU5UIHBvaW50LCBzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4KTsKK3ZvaWQgbXBpX2VjX2Fk ZF9wb2ludHMoTVBJX1BPSU5UIHJlc3VsdCwKKwkJCU1QSV9QT0lOVCBwMSwgTVBJX1BPSU5UIHAy LAorCQkJc3RydWN0IG1waV9lY19jdHggKmN0eCk7Cit2b2lkIG1waV9lY19tdWxfcG9pbnQoTVBJ X1BPSU5UIHJlc3VsdCwKKwkJCU1QSSBzY2FsYXIsIE1QSV9QT0lOVCBwb2ludCwKKwkJCXN0cnVj dCBtcGlfZWNfY3R4ICpjdHgpOworaW50IG1waV9lY19jdXJ2ZV9wb2ludChNUElfUE9JTlQgcG9p bnQsIHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpOworCiAvKiBpbmxpbmUgZnVuY3Rpb25zICovCiAK IC8qKgpkaWZmIC0tZ2l0IGEvbGliL21waS9NYWtlZmlsZSBiL2xpYi9tcGkvTWFrZWZpbGUKaW5k ZXggNDc3ZGViZDdlZDUwLi42ZTZlZjlhMzRmZTEgMTAwNjQ0Ci0tLSBhL2xpYi9tcGkvTWFrZWZp bGUKKysrIGIvbGliL21waS9NYWtlZmlsZQpAQCAtMTMsNiArMTMsNyBAQCBtcGkteSA9IFwKIAln ZW5lcmljX21waWgtcnNoaWZ0Lm8JCVwKIAlnZW5lcmljX21waWgtc3ViMS5vCQlcCiAJZ2VuZXJp Y19tcGloLWFkZDEubwkJXAorCWVjLm8JCQkJXAogCW1waWNvZGVyLm8JCQlcCiAJbXBpLWFkZC5v CQkJXAogCW1waS1iaXQubwkJCVwKZGlmZiAtLWdpdCBhL2xpYi9tcGkvZWMuYyBiL2xpYi9tcGkv ZWMuYwpuZXcgZmlsZSBtb2RlIDEwMDY0NAppbmRleCAwMDAwMDAwMDAwMDAuLmMyMTQ3MDEyMmRm YwotLS0gL2Rldi9udWxsCisrKyBiL2xpYi9tcGkvZWMuYwpAQCAtMCwwICsxLDE1MDkgQEAKKy8q IGVjLmMgLSAgRWxsaXB0aWMgQ3VydmUgZnVuY3Rpb25zCisgKiBDb3B5cmlnaHQgKEMpIDIwMDcg RnJlZSBTb2Z0d2FyZSBGb3VuZGF0aW9uLCBJbmMuCisgKiBDb3B5cmlnaHQgKEMpIDIwMTMgZzEw IENvZGUgR21iSAorICoKKyAqIFRoaXMgZmlsZSBpcyBwYXJ0IG9mIExpYmdjcnlwdC4KKyAqCisg KiBMaWJnY3J5cHQgaXMgZnJlZSBzb2Z0d2FyZTsgeW91IGNhbiByZWRpc3RyaWJ1dGUgaXQgYW5k L29yIG1vZGlmeQorICogaXQgdW5kZXIgdGhlIHRlcm1zIG9mIHRoZSBHTlUgTGVzc2VyIEdlbmVy YWwgUHVibGljIExpY2Vuc2UgYXMKKyAqIHB1Ymxpc2hlZCBieSB0aGUgRnJlZSBTb2Z0d2FyZSBG b3VuZGF0aW9uOyBlaXRoZXIgdmVyc2lvbiAyLjEgb2YKKyAqIHRoZSBMaWNlbnNlLCBvciAoYXQg eW91ciBvcHRpb24pIGFueSBsYXRlciB2ZXJzaW9uLgorICoKKyAqIExpYmdjcnlwdCBpcyBkaXN0 cmlidXRlZCBpbiB0aGUgaG9wZSB0aGF0IGl0IHdpbGwgYmUgdXNlZnVsLAorICogYnV0IFdJVEhP VVQgQU5ZIFdBUlJBTlRZOyB3aXRob3V0IGV2ZW4gdGhlIGltcGxpZWQgd2FycmFudHkgb2YKKyAq IE1FUkNIQU5UQUJJTElUWSBvciBGSVRORVNTIEZPUiBBIFBBUlRJQ1VMQVIgUFVSUE9TRS4gIFNl ZSB0aGUKKyAqIEdOVSBMZXNzZXIgR2VuZXJhbCBQdWJsaWMgTGljZW5zZSBmb3IgbW9yZSBkZXRh aWxzLgorICoKKyAqIFlvdSBzaG91bGQgaGF2ZSByZWNlaXZlZCBhIGNvcHkgb2YgdGhlIEdOVSBM ZXNzZXIgR2VuZXJhbCBQdWJsaWMKKyAqIExpY2Vuc2UgYWxvbmcgd2l0aCB0aGlzIHByb2dyYW07 IGlmIG5vdCwgc2VlIDxodHRwOi8vd3d3LmdudS5vcmcvbGljZW5zZXMvPi4KKyAqLworCisjaW5j bHVkZSAibXBpLWludGVybmFsLmgiCisjaW5jbHVkZSAibG9uZ2xvbmcuaCIKKworI2RlZmluZSBw b2ludF9pbml0KGEpICBtcGlfcG9pbnRfaW5pdCgoYSkpCisjZGVmaW5lIHBvaW50X2ZyZWUoYSkg IG1waV9wb2ludF9mcmVlX3BhcnRzKChhKSkKKworI2RlZmluZSBsb2dfZXJyb3IoZm10LCAuLi4p IHByX2VycihmbXQsICMjX19WQV9BUkdTX18pCisjZGVmaW5lIGxvZ19mYXRhbChmbXQsIC4uLikg cHJfZXJyKGZtdCwgIyNfX1ZBX0FSR1NfXykKKworI2RlZmluZSBESU0odikgKHNpemVvZih2KS9z aXplb2YoKHYpWzBdKSkKKworCisvKiBDcmVhdGUgYSBuZXcgcG9pbnQgb3B0aW9uLiAgTkJJVFMg Z2l2ZXMgdGhlIHNpemUgaW4gYml0cyBvZiBvbmUKKyAqIGNvb3JkaW5hdGU7IGl0IGlzIG9ubHkg dXNlZCB0byBwcmUtYWxsb2NhdGUgc29tZSByZXNvdXJjZXMgYW5kCisgKiBtaWdodCBhbHNvIGJl IHBhc3NlZCBhcyAwIHRvIHVzZSBhIGRlZmF1bHQgdmFsdWUuCisgKi8KK01QSV9QT0lOVCBtcGlf cG9pbnRfbmV3KHVuc2lnbmVkIGludCBuYml0cykKK3sKKwlNUElfUE9JTlQgcDsKKworCSh2b2lk KW5iaXRzOyAgLyogQ3VycmVudGx5IG5vdCB1c2VkLiAgKi8KKworCXAgPSBrbWFsbG9jKHNpemVv ZigqcCksIEdGUF9LRVJORUwpOworCWlmIChwKQorCQltcGlfcG9pbnRfaW5pdChwKTsKKwlyZXR1 cm4gcDsKK30KK0VYUE9SVF9TWU1CT0xfR1BMKG1waV9wb2ludF9uZXcpOworCisvKiBSZWxlYXNl IHRoZSBwb2ludCBvYmplY3QgUC4gIFAgbWF5IGJlIE5VTEwuICovCit2b2lkIG1waV9wb2ludF9y ZWxlYXNlKE1QSV9QT0lOVCBwKQoreworCWlmIChwKSB7CisJCW1waV9wb2ludF9mcmVlX3BhcnRz KHApOworCQlrZnJlZShwKTsKKwl9Cit9CitFWFBPUlRfU1lNQk9MX0dQTChtcGlfcG9pbnRfcmVs ZWFzZSk7CisKKy8qIEluaXRpYWxpemUgdGhlIGZpZWxkcyBvZiBhIHBvaW50IG9iamVjdC4gIGdj cnlfbXBpX3BvaW50X2ZyZWVfcGFydHMKKyAqIG1heSBiZSB1c2VkIHRvIHJlbGVhc2UgdGhlIGZp ZWxkcy4KKyAqLwordm9pZCBtcGlfcG9pbnRfaW5pdChNUElfUE9JTlQgcCkKK3sKKwlwLT54ID0g bXBpX25ldygwKTsKKwlwLT55ID0gbXBpX25ldygwKTsKKwlwLT56ID0gbXBpX25ldygwKTsKK30K K0VYUE9SVF9TWU1CT0xfR1BMKG1waV9wb2ludF9pbml0KTsKKworLyogUmVsZWFzZSB0aGUgcGFy dHMgb2YgYSBwb2ludCBvYmplY3QuICovCit2b2lkIG1waV9wb2ludF9mcmVlX3BhcnRzKE1QSV9Q T0lOVCBwKQoreworCW1waV9mcmVlKHAtPngpOyBwLT54ID0gTlVMTDsKKwltcGlfZnJlZShwLT55 KTsgcC0+eSA9IE5VTEw7CisJbXBpX2ZyZWUocC0+eik7IHAtPnogPSBOVUxMOworfQorRVhQT1JU X1NZTUJPTF9HUEwobXBpX3BvaW50X2ZyZWVfcGFydHMpOworCisvKiBTZXQgdGhlIHZhbHVlIGZy b20gUyBpbnRvIEQuICAqLworc3RhdGljIHZvaWQgcG9pbnRfc2V0KE1QSV9QT0lOVCBkLCBNUElf UE9JTlQgcykKK3sKKwltcGlfc2V0KGQtPngsIHMtPngpOworCW1waV9zZXQoZC0+eSwgcy0+eSk7 CisJbXBpX3NldChkLT56LCBzLT56KTsKK30KKworc3RhdGljIHZvaWQgcG9pbnRfcmVzaXplKE1Q SV9QT0lOVCBwLCBzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4KQoreworCXNpemVfdCBubGltYnMgPSBj dHgtPnAtPm5saW1iczsKKworCW1waV9yZXNpemUocC0+eCwgbmxpbWJzKTsKKwlwLT54LT5ubGlt YnMgPSBubGltYnM7CisJbXBpX3Jlc2l6ZShwLT56LCBubGltYnMpOworCXAtPnotPm5saW1icyA9 IG5saW1iczsKKworCWlmIChjdHgtPm1vZGVsICE9IE1QSV9FQ19NT05UR09NRVJZKSB7CisJCW1w aV9yZXNpemUocC0+eSwgbmxpbWJzKTsKKwkJcC0+eS0+bmxpbWJzID0gbmxpbWJzOworCX0KK30K Kworc3RhdGljIHZvaWQgcG9pbnRfc3dhcF9jb25kKE1QSV9QT0lOVCBkLCBNUElfUE9JTlQgcywg dW5zaWduZWQgbG9uZyBzd2FwLAorCQlzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4KQoreworCW1waV9z d2FwX2NvbmQoZC0+eCwgcy0+eCwgc3dhcCk7CisJaWYgKGN0eC0+bW9kZWwgIT0gTVBJX0VDX01P TlRHT01FUlkpCisJCW1waV9zd2FwX2NvbmQoZC0+eSwgcy0+eSwgc3dhcCk7CisJbXBpX3N3YXBf Y29uZChkLT56LCBzLT56LCBzd2FwKTsKK30KKworCisvKiBXID0gVyBtb2QgUC4gICovCitzdGF0 aWMgdm9pZCBlY19tb2QoTVBJIHcsIHN0cnVjdCBtcGlfZWNfY3R4ICplYykKK3sKKwlpZiAoZWMt PnQucF9iYXJyZXR0KQorCQltcGlfbW9kX2JhcnJldHQodywgdywgZWMtPnQucF9iYXJyZXR0KTsK KwllbHNlCisJCW1waV9tb2QodywgdywgZWMtPnApOworfQorCitzdGF0aWMgdm9pZCBlY19hZGRt KE1QSSB3LCBNUEkgdSwgTVBJIHYsIHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJbXBpX2Fk ZCh3LCB1LCB2KTsKKwllY19tb2QodywgY3R4KTsKK30KKworc3RhdGljIHZvaWQgZWNfc3VibShN UEkgdywgTVBJIHUsIE1QSSB2LCBzdHJ1Y3QgbXBpX2VjX2N0eCAqZWMpCit7CisJbXBpX3N1Yih3 LCB1LCB2KTsKKwl3aGlsZSAody0+c2lnbikKKwkJbXBpX2FkZCh3LCB3LCBlYy0+cCk7CisJLypl Y19tb2QodywgZWMpOyovCit9CisKK3N0YXRpYyB2b2lkIGVjX211bG0oTVBJIHcsIE1QSSB1LCBN UEkgdiwgc3RydWN0IG1waV9lY19jdHggKmN0eCkKK3sKKwltcGlfbXVsKHcsIHUsIHYpOworCWVj X21vZCh3LCBjdHgpOworfQorCisvKiBXID0gMiAqIFUgbW9kIFAuICAqLworc3RhdGljIHZvaWQg ZWNfbXVsMihNUEkgdywgTVBJIHUsIHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJbXBpX2xz aGlmdCh3LCB1LCAxKTsKKwllY19tb2QodywgY3R4KTsKK30KKworc3RhdGljIHZvaWQgZWNfcG93 bShNUEkgdywgY29uc3QgTVBJIGIsIGNvbnN0IE1QSSBlLAorCQlzdHJ1Y3QgbXBpX2VjX2N0eCAq Y3R4KQoreworCW1waV9wb3dtKHcsIGIsIGUsIGN0eC0+cCk7CisJLyogbXBpX2Ficyh3KTsgKi8K K30KKworLyogU2hvcnRjdXQgZm9yCisgKiBlY19wb3dtKEIsIEIsIG1waV9jb25zdChNUElfQ19U V08pLCBjdHgpOworICogZm9yIGVhc2llciBvcHRpbWl6YXRpb24uCisgKi8KK3N0YXRpYyB2b2lk IGVjX3BvdzIoTVBJIHcsIGNvbnN0IE1QSSBiLCBzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4KQorewor CS8qIFVzaW5nIG1waV9tdWwgaXMgc2xpZ2h0bHkgZmFzdGVyIChhdCBsZWFzdCBvbiBhbWQ2NCku ICAqLworCS8qIG1waV9wb3dtKHcsIGIsIG1waV9jb25zdChNUElfQ19UV08pLCBjdHgtPnApOyAq LworCWVjX211bG0odywgYiwgYiwgY3R4KTsKK30KKworLyogU2hvcnRjdXQgZm9yCisgKiBlY19w b3dtKEIsIEIsIG1waV9jb25zdChNUElfQ19USFJFRSksIGN0eCk7CisgKiBmb3IgZWFzaWVyIG9w dGltaXphdGlvbi4KKyAqLworc3RhdGljIHZvaWQgZWNfcG93MyhNUEkgdywgY29uc3QgTVBJIGIs IHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJbXBpX3Bvd20odywgYiwgbXBpX2NvbnN0KE1Q SV9DX1RIUkVFKSwgY3R4LT5wKTsKK30KKworc3RhdGljIHZvaWQgZWNfaW52bShNUEkgeCwgTVBJ IGEsIHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJaWYgKCFtcGlfaW52bSh4LCBhLCBjdHgt PnApKQorCQlsb2dfZXJyb3IoImVjX2ludm06IGludmVyc2UgZG9lcyBub3QgZXhpc3Q6XG4iKTsK K30KKworc3RhdGljIHZvaWQgbXBpaF9zZXRfY29uZChtcGlfcHRyX3Qgd3AsIG1waV9wdHJfdCB1 cCwKKwkJbXBpX3NpemVfdCB1c2l6ZSwgdW5zaWduZWQgbG9uZyBzZXQpCit7CisJbXBpX3NpemVf dCBpOworCW1waV9saW1iX3QgbWFzayA9ICgobXBpX2xpbWJfdCkwKSAtIHNldDsKKwltcGlfbGlt Yl90IHg7CisKKwlmb3IgKGkgPSAwOyBpIDwgdXNpemU7IGkrKykgeworCQl4ID0gbWFzayAmICh3 cFtpXSBeIHVwW2ldKTsKKwkJd3BbaV0gPSB3cFtpXSBeIHg7CisJfQorfQorCisvKiBSb3V0aW5l cyBmb3IgMl4yNTUgLSAxOS4gICovCisKKyNkZWZpbmUgTElNQl9TSVpFXzI1NTE5ICgoMjU2K0JJ VFNfUEVSX01QSV9MSU1CLTEpL0JJVFNfUEVSX01QSV9MSU1CKQorCitzdGF0aWMgdm9pZCBlY19h ZGRtXzI1NTE5KE1QSSB3LCBNUEkgdSwgTVBJIHYsIHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7 CisJbXBpX3B0cl90IHdwLCB1cCwgdnA7CisJbXBpX3NpemVfdCB3c2l6ZSA9IExJTUJfU0laRV8y NTUxOTsKKwltcGlfbGltYl90IG5bTElNQl9TSVpFXzI1NTE5XTsKKwltcGlfbGltYl90IGJvcnJv dzsKKworCWlmICh3LT5ubGltYnMgIT0gd3NpemUgfHwgdS0+bmxpbWJzICE9IHdzaXplIHx8IHYt Pm5saW1icyAhPSB3c2l6ZSkKKwkJbG9nX2J1ZygiYWRkbV8yNTUxOTogZGlmZmVyZW50IHNpemVz XG4iKTsKKworCW1lbXNldChuLCAwLCBzaXplb2YobikpOworCXVwID0gdS0+ZDsKKwl2cCA9IHYt PmQ7CisJd3AgPSB3LT5kOworCisJbXBpaGVscF9hZGRfbih3cCwgdXAsIHZwLCB3c2l6ZSk7CisJ Ym9ycm93ID0gbXBpaGVscF9zdWJfbih3cCwgd3AsIGN0eC0+cC0+ZCwgd3NpemUpOworCW1waWhf c2V0X2NvbmQobiwgY3R4LT5wLT5kLCB3c2l6ZSwgKGJvcnJvdyAhPSAwVUwpKTsKKwltcGloZWxw X2FkZF9uKHdwLCB3cCwgbiwgd3NpemUpOworCXdwW0xJTUJfU0laRV8yNTUxOS0xXSAmPSB+KCht cGlfbGltYl90KTEgPDwgKDI1NSAlIEJJVFNfUEVSX01QSV9MSU1CKSk7Cit9CisKK3N0YXRpYyB2 b2lkIGVjX3N1Ym1fMjU1MTkoTVBJIHcsIE1QSSB1LCBNUEkgdiwgc3RydWN0IG1waV9lY19jdHgg KmN0eCkKK3sKKwltcGlfcHRyX3Qgd3AsIHVwLCB2cDsKKwltcGlfc2l6ZV90IHdzaXplID0gTElN Ql9TSVpFXzI1NTE5OworCW1waV9saW1iX3QgbltMSU1CX1NJWkVfMjU1MTldOworCW1waV9saW1i X3QgYm9ycm93OworCisJaWYgKHctPm5saW1icyAhPSB3c2l6ZSB8fCB1LT5ubGltYnMgIT0gd3Np emUgfHwgdi0+bmxpbWJzICE9IHdzaXplKQorCQlsb2dfYnVnKCJzdWJtXzI1NTE5OiBkaWZmZXJl bnQgc2l6ZXNcbiIpOworCisJbWVtc2V0KG4sIDAsIHNpemVvZihuKSk7CisJdXAgPSB1LT5kOwor CXZwID0gdi0+ZDsKKwl3cCA9IHctPmQ7CisKKwlib3Jyb3cgPSBtcGloZWxwX3N1Yl9uKHdwLCB1 cCwgdnAsIHdzaXplKTsKKwltcGloX3NldF9jb25kKG4sIGN0eC0+cC0+ZCwgd3NpemUsIChib3Jy b3cgIT0gMFVMKSk7CisJbXBpaGVscF9hZGRfbih3cCwgd3AsIG4sIHdzaXplKTsKKwl3cFtMSU1C X1NJWkVfMjU1MTktMV0gJj0gfigobXBpX2xpbWJfdCkxIDw8ICgyNTUgJSBCSVRTX1BFUl9NUElf TElNQikpOworfQorCitzdGF0aWMgdm9pZCBlY19tdWxtXzI1NTE5KE1QSSB3LCBNUEkgdSwgTVBJ IHYsIHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJbXBpX3B0cl90IHdwLCB1cCwgdnA7CisJ bXBpX3NpemVfdCB3c2l6ZSA9IExJTUJfU0laRV8yNTUxOTsKKwltcGlfbGltYl90IG5bTElNQl9T SVpFXzI1NTE5KjJdOworCW1waV9saW1iX3QgbVtMSU1CX1NJWkVfMjU1MTkrMV07CisJbXBpX2xp bWJfdCBjeTsKKwlpbnQgbXNiOworCisJKHZvaWQpY3R4OworCWlmICh3LT5ubGltYnMgIT0gd3Np emUgfHwgdS0+bmxpbWJzICE9IHdzaXplIHx8IHYtPm5saW1icyAhPSB3c2l6ZSkKKwkJbG9nX2J1 ZygibXVsbV8yNTUxOTogZGlmZmVyZW50IHNpemVzXG4iKTsKKworCXVwID0gdS0+ZDsKKwl2cCA9 IHYtPmQ7CisJd3AgPSB3LT5kOworCisJbXBpaGVscF9tdWxfbihuLCB1cCwgdnAsIHdzaXplKTsK KwltZW1jcHkod3AsIG4sIHdzaXplICogQllURVNfUEVSX01QSV9MSU1CKTsKKwl3cFtMSU1CX1NJ WkVfMjU1MTktMV0gJj0gfigobXBpX2xpbWJfdCkxIDw8ICgyNTUgJSBCSVRTX1BFUl9NUElfTElN QikpOworCisJbWVtY3B5KG0sIG4rTElNQl9TSVpFXzI1NTE5LTEsICh3c2l6ZSsxKSAqIEJZVEVT X1BFUl9NUElfTElNQik7CisJbXBpaGVscF9yc2hpZnQobSwgbSwgTElNQl9TSVpFXzI1NTE5KzEs ICgyNTUgJSBCSVRTX1BFUl9NUElfTElNQikpOworCisJbWVtY3B5KG4sIG0sIHdzaXplICogQllU RVNfUEVSX01QSV9MSU1CKTsKKwljeSA9IG1waWhlbHBfbHNoaWZ0KG0sIG0sIExJTUJfU0laRV8y NTUxOSwgNCk7CisJbVtMSU1CX1NJWkVfMjU1MTldID0gY3k7CisJY3kgPSBtcGloZWxwX2FkZF9u KG0sIG0sIG4sIHdzaXplKTsKKwltW0xJTUJfU0laRV8yNTUxOV0gKz0gY3k7CisJY3kgPSBtcGlo ZWxwX2FkZF9uKG0sIG0sIG4sIHdzaXplKTsKKwltW0xJTUJfU0laRV8yNTUxOV0gKz0gY3k7CisJ Y3kgPSBtcGloZWxwX2FkZF9uKG0sIG0sIG4sIHdzaXplKTsKKwltW0xJTUJfU0laRV8yNTUxOV0g Kz0gY3k7CisKKwljeSA9IG1waWhlbHBfYWRkX24od3AsIHdwLCBtLCB3c2l6ZSk7CisJbVtMSU1C X1NJWkVfMjU1MTldICs9IGN5OworCisJbWVtc2V0KG0sIDAsIHdzaXplICogQllURVNfUEVSX01Q SV9MSU1CKTsKKwltc2IgPSAod3BbTElNQl9TSVpFXzI1NTE5LTFdID4+ICgyNTUgJSBCSVRTX1BF Ul9NUElfTElNQikpOworCW1bMF0gPSAobVtMSU1CX1NJWkVfMjU1MTldICogMiArIG1zYikgKiAx OTsKKwl3cFtMSU1CX1NJWkVfMjU1MTktMV0gJj0gfigobXBpX2xpbWJfdCkxIDw8ICgyNTUgJSBC SVRTX1BFUl9NUElfTElNQikpOworCW1waWhlbHBfYWRkX24od3AsIHdwLCBtLCB3c2l6ZSk7CisK KwltWzBdID0gMDsKKwljeSA9IG1waWhlbHBfc3ViX24od3AsIHdwLCBjdHgtPnAtPmQsIHdzaXpl KTsKKwltcGloX3NldF9jb25kKG0sIGN0eC0+cC0+ZCwgd3NpemUsIChjeSAhPSAwVUwpKTsKKwlt cGloZWxwX2FkZF9uKHdwLCB3cCwgbSwgd3NpemUpOworfQorCitzdGF0aWMgdm9pZCBlY19tdWwy XzI1NTE5KE1QSSB3LCBNUEkgdSwgc3RydWN0IG1waV9lY19jdHggKmN0eCkKK3sKKwllY19hZGRt XzI1NTE5KHcsIHUsIHUsIGN0eCk7Cit9CisKK3N0YXRpYyB2b2lkIGVjX3BvdzJfMjU1MTkoTVBJ IHcsIGNvbnN0IE1QSSBiLCBzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4KQoreworCWVjX211bG1fMjU1 MTkodywgYiwgYiwgY3R4KTsKK30KKworLyogUm91dGluZXMgZm9yIDJeNDQ4IC0gMl4yMjQgLSAx LiAgKi8KKworI2RlZmluZSBMSU1CX1NJWkVfNDQ4ICgoNDQ4K0JJVFNfUEVSX01QSV9MSU1CLTEp L0JJVFNfUEVSX01QSV9MSU1CKQorI2RlZmluZSBMSU1CX1NJWkVfSEFMRl80NDggKChMSU1CX1NJ WkVfNDQ4KzEpLzIpCisKK3N0YXRpYyB2b2lkIGVjX2FkZG1fNDQ4KE1QSSB3LCBNUEkgdSwgTVBJ IHYsIHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJbXBpX3B0cl90IHdwLCB1cCwgdnA7CisJ bXBpX3NpemVfdCB3c2l6ZSA9IExJTUJfU0laRV80NDg7CisJbXBpX2xpbWJfdCBuW0xJTUJfU0la RV80NDhdOworCW1waV9saW1iX3QgY3k7CisKKwlpZiAody0+bmxpbWJzICE9IHdzaXplIHx8IHUt Pm5saW1icyAhPSB3c2l6ZSB8fCB2LT5ubGltYnMgIT0gd3NpemUpCisJCWxvZ19idWcoImFkZG1f NDQ4OiBkaWZmZXJlbnQgc2l6ZXNcbiIpOworCisJbWVtc2V0KG4sIDAsIHNpemVvZihuKSk7CisJ dXAgPSB1LT5kOworCXZwID0gdi0+ZDsKKwl3cCA9IHctPmQ7CisKKwljeSA9IG1waWhlbHBfYWRk X24od3AsIHVwLCB2cCwgd3NpemUpOworCW1waWhfc2V0X2NvbmQobiwgY3R4LT5wLT5kLCB3c2l6 ZSwgKGN5ICE9IDBVTCkpOworCW1waWhlbHBfc3ViX24od3AsIHdwLCBuLCB3c2l6ZSk7Cit9CisK K3N0YXRpYyB2b2lkIGVjX3N1Ym1fNDQ4KE1QSSB3LCBNUEkgdSwgTVBJIHYsIHN0cnVjdCBtcGlf ZWNfY3R4ICpjdHgpCit7CisJbXBpX3B0cl90IHdwLCB1cCwgdnA7CisJbXBpX3NpemVfdCB3c2l6 ZSA9IExJTUJfU0laRV80NDg7CisJbXBpX2xpbWJfdCBuW0xJTUJfU0laRV80NDhdOworCW1waV9s aW1iX3QgYm9ycm93OworCisJaWYgKHctPm5saW1icyAhPSB3c2l6ZSB8fCB1LT5ubGltYnMgIT0g d3NpemUgfHwgdi0+bmxpbWJzICE9IHdzaXplKQorCQlsb2dfYnVnKCJzdWJtXzQ0ODogZGlmZmVy ZW50IHNpemVzXG4iKTsKKworCW1lbXNldChuLCAwLCBzaXplb2YobikpOworCXVwID0gdS0+ZDsK Kwl2cCA9IHYtPmQ7CisJd3AgPSB3LT5kOworCisJYm9ycm93ID0gbXBpaGVscF9zdWJfbih3cCwg dXAsIHZwLCB3c2l6ZSk7CisJbXBpaF9zZXRfY29uZChuLCBjdHgtPnAtPmQsIHdzaXplLCAoYm9y cm93ICE9IDBVTCkpOworCW1waWhlbHBfYWRkX24od3AsIHdwLCBuLCB3c2l6ZSk7Cit9CisKK3N0 YXRpYyB2b2lkIGVjX211bG1fNDQ4KE1QSSB3LCBNUEkgdSwgTVBJIHYsIHN0cnVjdCBtcGlfZWNf Y3R4ICpjdHgpCit7CisJbXBpX3B0cl90IHdwLCB1cCwgdnA7CisJbXBpX3NpemVfdCB3c2l6ZSA9 IExJTUJfU0laRV80NDg7CisJbXBpX2xpbWJfdCBuW0xJTUJfU0laRV80NDgqMl07CisJbXBpX2xp bWJfdCBhMltMSU1CX1NJWkVfSEFMRl80NDhdOworCW1waV9saW1iX3QgYTNbTElNQl9TSVpFX0hB TEZfNDQ4XTsKKwltcGlfbGltYl90IGIwW0xJTUJfU0laRV9IQUxGXzQ0OF07CisJbXBpX2xpbWJf dCBiMVtMSU1CX1NJWkVfSEFMRl80NDhdOworCW1waV9saW1iX3QgY3k7CisJaW50IGk7CisjaWYg KExJTUJfU0laRV9IQUxGXzQ0OCA+IExJTUJfU0laRV80NDgvMikKKwltcGlfbGltYl90IGIxX3Jl c3QsIGEzX3Jlc3Q7CisjZW5kaWYKKworCWlmICh3LT5ubGltYnMgIT0gd3NpemUgfHwgdS0+bmxp bWJzICE9IHdzaXplIHx8IHYtPm5saW1icyAhPSB3c2l6ZSkKKwkJbG9nX2J1ZygibXVsbV80NDg6 IGRpZmZlcmVudCBzaXplc1xuIik7CisKKwl1cCA9IHUtPmQ7CisJdnAgPSB2LT5kOworCXdwID0g dy0+ZDsKKworCW1waWhlbHBfbXVsX24obiwgdXAsIHZwLCB3c2l6ZSk7CisKKwlmb3IgKGkgPSAw OyBpIDwgKHdzaXplICsgMSkgLyAyOyBpKyspIHsKKwkJYjBbaV0gPSBuW2ldOworCQliMVtpXSA9 IG5baSt3c2l6ZS8yXTsKKwkJYTJbaV0gPSBuW2krd3NpemVdOworCQlhM1tpXSA9IG5baSt3c2l6 ZSt3c2l6ZS8yXTsKKwl9CisKKyNpZiAoTElNQl9TSVpFX0hBTEZfNDQ4ID4gTElNQl9TSVpFXzQ0 OC8yKQorCWIwW0xJTUJfU0laRV9IQUxGXzQ0OC0xXSAmPSAoKG1waV9saW1iX3QpMVVMIDw8IDMy KS0xOworCWEyW0xJTUJfU0laRV9IQUxGXzQ0OC0xXSAmPSAoKG1waV9saW1iX3QpMVVMIDw8IDMy KS0xOworCisJYjFfcmVzdCA9IDA7CisJYTNfcmVzdCA9IDA7CisKKwlmb3IgKGkgPSAod3NpemUg KyAxKSAvIDIgLSAxOyBpID49IDA7IGktLSkgeworCQltcGlfbGltYl90IGIxdiwgYTN2OworCQli MXYgPSBiMVtpXTsKKwkJYTN2ID0gYTNbaV07CisJCWIxW2ldID0gKGIxX3Jlc3QgPDwgMzIpIHwg KGIxdiA+PiAzMik7CisJCWEzW2ldID0gKGEzX3Jlc3QgPDwgMzIpIHwgKGEzdiA+PiAzMik7CisJ CWIxX3Jlc3QgPSBiMXYgJiAoKChtcGlfbGltYl90KTFVTCA8PCAzMiktMSk7CisJCWEzX3Jlc3Qg PSBhM3YgJiAoKChtcGlfbGltYl90KTFVTCA8PCAzMiktMSk7CisJfQorI2VuZGlmCisKKwljeSA9 IG1waWhlbHBfYWRkX24oYjAsIGIwLCBhMiwgTElNQl9TSVpFX0hBTEZfNDQ4KTsKKwljeSArPSBt cGloZWxwX2FkZF9uKGIwLCBiMCwgYTMsIExJTUJfU0laRV9IQUxGXzQ0OCk7CisJZm9yIChpID0g MDsgaSA8ICh3c2l6ZSArIDEpIC8gMjsgaSsrKQorCQl3cFtpXSA9IGIwW2ldOworI2lmIChMSU1C X1NJWkVfSEFMRl80NDggPiBMSU1CX1NJWkVfNDQ4LzIpCisJd3BbTElNQl9TSVpFX0hBTEZfNDQ4 LTFdICY9ICgoKG1waV9saW1iX3QpMVVMIDw8IDMyKS0xKTsKKyNlbmRpZgorCisjaWYgKExJTUJf U0laRV9IQUxGXzQ0OCA+IExJTUJfU0laRV80NDgvMikKKwljeSA9IGIwW0xJTUJfU0laRV9IQUxG XzQ0OC0xXSA+PiAzMjsKKyNlbmRpZgorCisJY3kgPSBtcGloZWxwX2FkZF8xKGIxLCBiMSwgTElN Ql9TSVpFX0hBTEZfNDQ4LCBjeSk7CisJY3kgKz0gbXBpaGVscF9hZGRfbihiMSwgYjEsIGEyLCBM SU1CX1NJWkVfSEFMRl80NDgpOworCWN5ICs9IG1waWhlbHBfYWRkX24oYjEsIGIxLCBhMywgTElN Ql9TSVpFX0hBTEZfNDQ4KTsKKwljeSArPSBtcGloZWxwX2FkZF9uKGIxLCBiMSwgYTMsIExJTUJf U0laRV9IQUxGXzQ0OCk7CisjaWYgKExJTUJfU0laRV9IQUxGXzQ0OCA+IExJTUJfU0laRV80NDgv MikKKwliMV9yZXN0ID0gMDsKKwlmb3IgKGkgPSAod3NpemUgKyAxKSAvIDIgLSAxOyBpID49IDA7 IGktLSkgeworCQltcGlfbGltYl90IGIxdiA9IGIxW2ldOworCQliMVtpXSA9IChiMV9yZXN0IDw8 IDMyKSB8IChiMXYgPj4gMzIpOworCQliMV9yZXN0ID0gYjF2ICYgKCgobXBpX2xpbWJfdCkxVUwg PDwgMzIpLTEpOworCX0KKwl3cFtMSU1CX1NJWkVfSEFMRl80NDgtMV0gfD0gKGIxX3Jlc3QgPDwg MzIpOworI2VuZGlmCisJZm9yIChpID0gMDsgaSA8IHdzaXplIC8gMjsgaSsrKQorCQl3cFtpKyh3 c2l6ZSArIDEpIC8gMl0gPSBiMVtpXTsKKworI2lmIChMSU1CX1NJWkVfSEFMRl80NDggPiBMSU1C X1NJWkVfNDQ4LzIpCisJY3kgPSBiMVtMSU1CX1NJWkVfSEFMRl80NDgtMV07CisjZW5kaWYKKwor CW1lbXNldChuLCAwLCB3c2l6ZSAqIEJZVEVTX1BFUl9NUElfTElNQik7CisKKyNpZiAoTElNQl9T SVpFX0hBTEZfNDQ4ID4gTElNQl9TSVpFXzQ0OC8yKQorCW5bTElNQl9TSVpFX0hBTEZfNDQ4LTFd ID0gY3kgPDwgMzI7CisjZWxzZQorCW5bTElNQl9TSVpFX0hBTEZfNDQ4XSA9IGN5OworI2VuZGlm CisJblswXSA9IGN5OworCW1waWhlbHBfYWRkX24od3AsIHdwLCBuLCB3c2l6ZSk7CisKKwltZW1z ZXQobiwgMCwgd3NpemUgKiBCWVRFU19QRVJfTVBJX0xJTUIpOworCWN5ID0gbXBpaGVscF9zdWJf bih3cCwgd3AsIGN0eC0+cC0+ZCwgd3NpemUpOworCW1waWhfc2V0X2NvbmQobiwgY3R4LT5wLT5k LCB3c2l6ZSwgKGN5ICE9IDBVTCkpOworCW1waWhlbHBfYWRkX24od3AsIHdwLCBuLCB3c2l6ZSk7 Cit9CisKK3N0YXRpYyB2b2lkIGVjX211bDJfNDQ4KE1QSSB3LCBNUEkgdSwgc3RydWN0IG1waV9l Y19jdHggKmN0eCkKK3sKKwllY19hZGRtXzQ0OCh3LCB1LCB1LCBjdHgpOworfQorCitzdGF0aWMg dm9pZCBlY19wb3cyXzQ0OChNUEkgdywgY29uc3QgTVBJIGIsIHN0cnVjdCBtcGlfZWNfY3R4ICpj dHgpCit7CisJZWNfbXVsbV80NDgodywgYiwgYiwgY3R4KTsKK30KKworc3RydWN0IGZpZWxkX3Rh YmxlIHsKKwljb25zdCBjaGFyICpwOworCisJLyogY29tcHV0YXRpb24gcm91dGluZXMgZm9yIHRo ZSBmaWVsZC4gICovCisJdm9pZCAoKmFkZG0pKE1QSSB3LCBNUEkgdSwgTVBJIHYsIHN0cnVjdCBt cGlfZWNfY3R4ICpjdHgpOworCXZvaWQgKCpzdWJtKShNUEkgdywgTVBJIHUsIE1QSSB2LCBzdHJ1 Y3QgbXBpX2VjX2N0eCAqY3R4KTsKKwl2b2lkICgqbXVsbSkoTVBJIHcsIE1QSSB1LCBNUEkgdiwg c3RydWN0IG1waV9lY19jdHggKmN0eCk7CisJdm9pZCAoKm11bDIpKE1QSSB3LCBNUEkgdSwgc3Ry dWN0IG1waV9lY19jdHggKmN0eCk7CisJdm9pZCAoKnBvdzIpKE1QSSB3LCBjb25zdCBNUEkgYiwg c3RydWN0IG1waV9lY19jdHggKmN0eCk7Cit9OworCitzdGF0aWMgY29uc3Qgc3RydWN0IGZpZWxk X3RhYmxlIGZpZWxkX3RhYmxlW10gPSB7CisJeworCQkiMHg3RkZGRkZGRkZGRkZGRkZGRkZGRkZG RkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkVEIiwKKwkJZWNfYWRkbV8y NTUxOSwKKwkJZWNfc3VibV8yNTUxOSwKKwkJZWNfbXVsbV8yNTUxOSwKKwkJZWNfbXVsMl8yNTUx OSwKKwkJZWNfcG93Ml8yNTUxOQorCX0sCisJeworCQkiMHhGRkZGRkZGRkZGRkZGRkZGRkZGRkZG RkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRSIKKwkJIkZGRkZGRkZGRkZGRkZGRkZG RkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGRkZGIiwKKwkJZWNfYWRkbV80NDgs CisJCWVjX3N1Ym1fNDQ4LAorCQllY19tdWxtXzQ0OCwKKwkJZWNfbXVsMl80NDgsCisJCWVjX3Bv dzJfNDQ4CisJfSwKKwl7IE5VTEwsIE5VTEwsIE5VTEwsIE5VTEwsIE5VTEwsIE5VTEwgfSwKK307 CisKKy8qIEZvcmNlIHJlY29tcHV0YXRpb24gb2YgYWxsIGhlbHBlciB2YXJpYWJsZXMuICAqLwor c3RhdGljIHZvaWQgbXBpX2VjX2dldF9yZXNldChzdHJ1Y3QgbXBpX2VjX2N0eCAqZWMpCit7CisJ ZWMtPnQudmFsaWQuYV9pc19wbWludXMzID0gMDsKKwllYy0+dC52YWxpZC50d29faW52X3AgPSAw OworfQorCisvKiBBY2Nlc3NvciBmb3IgaGVscGVyIHZhcmlhYmxlLiAgKi8KK3N0YXRpYyBpbnQg ZWNfZ2V0X2FfaXNfcG1pbnVzMyhzdHJ1Y3QgbXBpX2VjX2N0eCAqZWMpCit7CisJTVBJIHRtcDsK KworCWlmICghZWMtPnQudmFsaWQuYV9pc19wbWludXMzKSB7CisJCWVjLT50LnZhbGlkLmFfaXNf cG1pbnVzMyA9IDE7CisJCXRtcCA9IG1waV9hbGxvY19saWtlKGVjLT5wKTsKKwkJbXBpX3N1Yl91 aSh0bXAsIGVjLT5wLCAzKTsKKwkJZWMtPnQuYV9pc19wbWludXMzID0gIW1waV9jbXAoZWMtPmEs IHRtcCk7CisJCW1waV9mcmVlKHRtcCk7CisJfQorCisJcmV0dXJuIGVjLT50LmFfaXNfcG1pbnVz MzsKK30KKworLyogQWNjZXNzb3IgZm9yIGhlbHBlciB2YXJpYWJsZS4gICovCitzdGF0aWMgTVBJ IGVjX2dldF90d29faW52X3Aoc3RydWN0IG1waV9lY19jdHggKmVjKQoreworCWlmICghZWMtPnQu dmFsaWQudHdvX2ludl9wKSB7CisJCWVjLT50LnZhbGlkLnR3b19pbnZfcCA9IDE7CisJCWlmICgh ZWMtPnQudHdvX2ludl9wKQorCQkJZWMtPnQudHdvX2ludl9wID0gbXBpX2FsbG9jKDApOworCQll Y19pbnZtKGVjLT50LnR3b19pbnZfcCwgbXBpX2NvbnN0KE1QSV9DX1RXTyksIGVjKTsKKwl9CisJ cmV0dXJuIGVjLT50LnR3b19pbnZfcDsKK30KKworc3RhdGljIGNvbnN0IGNoYXIgKmNvbnN0IGN1 cnZlMjU1MTlfYmFkX3BvaW50c1tdID0geworCSIweDdmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZm ZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZWQiLAorCSIweDAwMDAwMDAwMDAw MDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAiLAor CSIweDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAw MDAwMDAwMDAwMDEiLAorCSIweDAwYjg0OTVmMTYwNTYyODZmZGIxMzI5Y2ViOGQwOWRhNmFjNDlm ZjFmYWUzNTYxNmFlYjg0MTNiN2M3YWViZTAiLAorCSIweDU3MTE5ZmQwZGQ0ZTIyZDg4NjhlMWM1 OGM0NWM0NDA0NWJlZjgzOWM1NWIxZDBiMTI0OGM1MGEzYmM5NTljNWYiLAorCSIweDdmZmZmZmZm ZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZWMi LAorCSIweDdmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZm ZmZmZmZmZmZmZmZmZWUiLAorCU5VTEwKK307CisKK3N0YXRpYyBjb25zdCBjaGFyICpjb25zdCBj dXJ2ZTQ0OF9iYWRfcG9pbnRzW10gPSB7CisJIjB4ZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZm ZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmUiCisJImZmZmZmZmZmZmZmZmZmZmZmZmZmZmZm ZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmIiwKKwkiMHgwMDAwMDAwMDAwMDAwMDAw MDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMCIKKwkiMDAwMDAwMDAwMDAw MDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAiLAorCSIweDAwMDAw MDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwIgorCSIw MDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMSIs CisJIjB4ZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZm ZmZmZmUiCisJImZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZm ZmZmZmZmZmZlIiwKKwkiMHhmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZmZm ZmZmZmZmZmZmZmZmZmZmZiIKKwkiMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAwMDAw MDAwMDAwMDAwMDAwMDAwMDAwMDAiLAorCU5VTEwKK307CisKK3N0YXRpYyBjb25zdCBjaGFyICpj b25zdCAqYmFkX3BvaW50c190YWJsZVtdID0geworCWN1cnZlMjU1MTlfYmFkX3BvaW50cywKKwlj dXJ2ZTQ0OF9iYWRfcG9pbnRzLAorfTsKKworc3RhdGljIHZvaWQgbXBpX2VjX2NvZWZmaWNpZW50 X25vcm1hbGl6ZShNUEkgYSwgTVBJIHApCit7CisJaWYgKGEtPnNpZ24pIHsKKwkJbXBpX3Jlc2l6 ZShhLCBwLT5ubGltYnMpOworCQltcGloZWxwX3N1Yl9uKGEtPmQsIHAtPmQsIGEtPmQsIHAtPm5s aW1icyk7CisJCWEtPm5saW1icyA9IHAtPm5saW1iczsKKwkJYS0+c2lnbiA9IDA7CisJfQorfQor CisvKiBUaGlzIGZ1bmN0aW9uIGluaXRpYWxpemVkIGEgY29udGV4dCBmb3IgZWxsaXB0aWMgY3Vy dmUgYmFzZWQgb24gdGhlCisgKiBmaWVsZCBHRihwKS4gIFAgaXMgdGhlIHByaW1lIHNwZWNpZnlp bmcgdGhpcyBmaWVsZCwgQSBpcyB0aGUgZmlyc3QKKyAqIGNvZWZmaWNpZW50LiAgQ1RYIGlzIGV4 cGVjdGVkIHRvIGJlIHplcm9pemVkLgorICovCit2b2lkIG1waV9lY19pbml0KHN0cnVjdCBtcGlf ZWNfY3R4ICpjdHgsIGVudW0gZ2NyeV9tcGlfZWNfbW9kZWxzIG1vZGVsLAorCQkJZW51bSBlY2Nf ZGlhbGVjdHMgZGlhbGVjdCwKKwkJCWludCBmbGFncywgTVBJIHAsIE1QSSBhLCBNUEkgYikKK3sK KwlpbnQgaTsKKwlzdGF0aWMgaW50IHVzZV9iYXJyZXR0ID0gLTEgLyogVE9ETzogMSBvciAtMSAq LzsKKworCW1waV9lY19jb2VmZmljaWVudF9ub3JtYWxpemUoYSwgcCk7CisJbXBpX2VjX2NvZWZm aWNpZW50X25vcm1hbGl6ZShiLCBwKTsKKworCS8qIEZpeG1lOiBEbyB3ZSB3YW50IHRvIGNoZWNr IHNvbWUgY29uc3RyYWludHM/IGUuZy4gIGEgPCBwICAqLworCisJY3R4LT5tb2RlbCA9IG1vZGVs OworCWN0eC0+ZGlhbGVjdCA9IGRpYWxlY3Q7CisJY3R4LT5mbGFncyA9IGZsYWdzOworCWlmIChk aWFsZWN0ID09IEVDQ19ESUFMRUNUX0VEMjU1MTkpCisJCWN0eC0+bmJpdHMgPSAyNTY7CisJZWxz ZQorCQljdHgtPm5iaXRzID0gbXBpX2dldF9uYml0cyhwKTsKKwljdHgtPnAgPSBtcGlfY29weShw KTsKKwljdHgtPmEgPSBtcGlfY29weShhKTsKKwljdHgtPmIgPSBtcGlfY29weShiKTsKKworCWN0 eC0+dC5wX2JhcnJldHQgPSB1c2VfYmFycmV0dCA+IDAgPyBtcGlfYmFycmV0dF9pbml0KGN0eC0+ cCwgMCkgOiBOVUxMOworCisJbXBpX2VjX2dldF9yZXNldChjdHgpOworCisJaWYgKG1vZGVsID09 IE1QSV9FQ19NT05UR09NRVJZKSB7CisJCWZvciAoaSA9IDA7IGkgPCBESU0oYmFkX3BvaW50c190 YWJsZSk7IGkrKykgeworCQkJTVBJIHBfY2FuZGlkYXRlID0gbXBpX3NjYW52YWwoYmFkX3BvaW50 c190YWJsZVtpXVswXSk7CisJCQlpbnQgbWF0Y2hfcCA9ICFtcGlfY21wKGN0eC0+cCwgcF9jYW5k aWRhdGUpOworCQkJaW50IGo7CisKKwkJCW1waV9mcmVlKHBfY2FuZGlkYXRlKTsKKwkJCWlmICgh bWF0Y2hfcCkKKwkJCQljb250aW51ZTsKKworCQkJZm9yIChqID0gMDsgaSA8IERJTShjdHgtPnQu c2NyYXRjaCkgJiYgYmFkX3BvaW50c190YWJsZVtpXVtqXTsgaisrKQorCQkJCWN0eC0+dC5zY3Jh dGNoW2pdID0gbXBpX3NjYW52YWwoYmFkX3BvaW50c190YWJsZVtpXVtqXSk7CisJCX0KKwl9IGVs c2UgeworCQkvKiBBbGxvY2F0ZSBzY3JhdGNoIHZhcmlhYmxlcy4gICovCisJCWZvciAoaSA9IDA7 IGkgPCBESU0oY3R4LT50LnNjcmF0Y2gpOyBpKyspCisJCQljdHgtPnQuc2NyYXRjaFtpXSA9IG1w aV9hbGxvY19saWtlKGN0eC0+cCk7CisJfQorCisJY3R4LT5hZGRtID0gZWNfYWRkbTsKKwljdHgt PnN1Ym0gPSBlY19zdWJtOworCWN0eC0+bXVsbSA9IGVjX211bG07CisJY3R4LT5tdWwyID0gZWNf bXVsMjsKKwljdHgtPnBvdzIgPSBlY19wb3cyOworCisJZm9yIChpID0gMDsgZmllbGRfdGFibGVb aV0ucDsgaSsrKSB7CisJCU1QSSBmX3A7CisKKwkJZl9wID0gbXBpX3NjYW52YWwoZmllbGRfdGFi bGVbaV0ucCk7CisJCWlmICghZl9wKQorCQkJYnJlYWs7CisKKwkJaWYgKCFtcGlfY21wKHAsIGZf cCkpIHsKKwkJCWN0eC0+YWRkbSA9IGZpZWxkX3RhYmxlW2ldLmFkZG07CisJCQljdHgtPnN1Ym0g PSBmaWVsZF90YWJsZVtpXS5zdWJtOworCQkJY3R4LT5tdWxtID0gZmllbGRfdGFibGVbaV0ubXVs bTsKKwkJCWN0eC0+bXVsMiA9IGZpZWxkX3RhYmxlW2ldLm11bDI7CisJCQljdHgtPnBvdzIgPSBm aWVsZF90YWJsZVtpXS5wb3cyOworCQkJbXBpX2ZyZWUoZl9wKTsKKworCQkJbXBpX3Jlc2l6ZShj dHgtPmEsIGN0eC0+cC0+bmxpbWJzKTsKKwkJCWN0eC0+YS0+bmxpbWJzID0gY3R4LT5wLT5ubGlt YnM7CisKKwkJCW1waV9yZXNpemUoY3R4LT5iLCBjdHgtPnAtPm5saW1icyk7CisJCQljdHgtPmIt Pm5saW1icyA9IGN0eC0+cC0+bmxpbWJzOworCisJCQlmb3IgKGkgPSAwOyBpIDwgRElNKGN0eC0+ dC5zY3JhdGNoKSAmJiBjdHgtPnQuc2NyYXRjaFtpXTsgaSsrKQorCQkJCWN0eC0+dC5zY3JhdGNo W2ldLT5ubGltYnMgPSBjdHgtPnAtPm5saW1iczsKKworCQkJYnJlYWs7CisJCX0KKworCQltcGlf ZnJlZShmX3ApOworCX0KK30KK0VYUE9SVF9TWU1CT0xfR1BMKG1waV9lY19pbml0KTsKKwordm9p ZCBtcGlfZWNfZGVpbml0KHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJaW50IGk7CisKKwlt cGlfYmFycmV0dF9mcmVlKGN0eC0+dC5wX2JhcnJldHQpOworCisJLyogRG9tYWluIHBhcmFtZXRl ci4gICovCisJbXBpX2ZyZWUoY3R4LT5wKTsKKwltcGlfZnJlZShjdHgtPmEpOworCW1waV9mcmVl KGN0eC0+Yik7CisJbXBpX3BvaW50X3JlbGVhc2UoY3R4LT5HKTsKKwltcGlfZnJlZShjdHgtPm4p OworCisJLyogVGhlIGtleS4gICovCisJbXBpX3BvaW50X3JlbGVhc2UoY3R4LT5RKTsKKwltcGlf ZnJlZShjdHgtPmQpOworCisJLyogUHJpdmF0ZSBkYXRhIG9mIGVjLmMuICAqLworCW1waV9mcmVl KGN0eC0+dC50d29faW52X3ApOworCisJZm9yIChpID0gMDsgaSA8IERJTShjdHgtPnQuc2NyYXRj aCk7IGkrKykKKwkJbXBpX2ZyZWUoY3R4LT50LnNjcmF0Y2hbaV0pOworfQorRVhQT1JUX1NZTUJP TF9HUEwobXBpX2VjX2RlaW5pdCk7CisKKy8qIENvbXB1dGUgdGhlIGFmZmluZSBjb29yZGluYXRl cyBmcm9tIHRoZSBwcm9qZWN0aXZlIGNvb3JkaW5hdGVzIGluCisgKiBQT0lOVC4gIFNldCB0aGVt IGludG8gWCBhbmQgWS4gIElmIG9uZSBjb29yZGluYXRlIGlzIG5vdCByZXF1aXJlZCwKKyAqIFgg b3IgWSBtYXkgYmUgcGFzc2VkIGFzIE5VTEwuICBDVFggaXMgdGhlIHVzdWFsIGNvbnRleHQuIFJl dHVybnM6IDAKKyAqIG9uIHN1Y2Nlc3Mgb3IgITAgaWYgUE9JTlQgaXMgYXQgaW5maW5pdHkuCisg Ki8KK2ludCBtcGlfZWNfZ2V0X2FmZmluZShNUEkgeCwgTVBJIHksIE1QSV9QT0lOVCBwb2ludCwg c3RydWN0IG1waV9lY19jdHggKmN0eCkKK3sKKwlpZiAoIW1waV9jbXBfdWkocG9pbnQtPnosIDAp KQorCQlyZXR1cm4gLTE7CisKKwlzd2l0Y2ggKGN0eC0+bW9kZWwpIHsKKwljYXNlIE1QSV9FQ19X RUlFUlNUUkFTUzogLyogVXNpbmcgSmFjb2JpYW4gY29vcmRpbmF0ZXMuICAqLworCQl7CisJCQlN UEkgejEsIHoyLCB6MzsKKworCQkJejEgPSBtcGlfbmV3KDApOworCQkJejIgPSBtcGlfbmV3KDAp OworCQkJZWNfaW52bSh6MSwgcG9pbnQtPnosIGN0eCk7ICAvKiB6MSA9IHpeKC0xKSBtb2QgcCAg Ki8KKwkJCWVjX211bG0oejIsIHoxLCB6MSwgY3R4KTsgICAgLyogejIgPSB6XigtMikgbW9kIHAg ICovCisKKwkJCWlmICh4KQorCQkJCWVjX211bG0oeCwgcG9pbnQtPngsIHoyLCBjdHgpOworCisJ CQlpZiAoeSkgeworCQkJCXozID0gbXBpX25ldygwKTsKKwkJCQllY19tdWxtKHozLCB6MiwgejEs IGN0eCk7ICAgICAgLyogejMgPSB6XigtMykgbW9kIHAgKi8KKwkJCQllY19tdWxtKHksIHBvaW50 LT55LCB6MywgY3R4KTsKKwkJCQltcGlfZnJlZSh6Myk7CisJCQl9CisKKwkJCW1waV9mcmVlKHoy KTsKKwkJCW1waV9mcmVlKHoxKTsKKwkJfQorCQlyZXR1cm4gMDsKKworCWNhc2UgTVBJX0VDX01P TlRHT01FUlk6CisJCXsKKwkJCWlmICh4KQorCQkJCW1waV9zZXQoeCwgcG9pbnQtPngpOworCisJ CQlpZiAoeSkgeworCQkJCWxvZ19mYXRhbCgiJXM6IEdldHRpbmcgWS1jb29yZGluYXRlIG9uICVz IGlzIG5vdCBzdXBwb3J0ZWRcbiIsCisJCQkJCQkibXBpX2VjX2dldF9hZmZpbmUiLCAiTW9udGdv bWVyeSIpOworCQkJCXJldHVybiAtMTsKKwkJCX0KKwkJfQorCQlyZXR1cm4gMDsKKworCWNhc2Ug TVBJX0VDX0VEV0FSRFM6CisJCXsKKwkJCU1QSSB6OworCisJCQl6ID0gbXBpX25ldygwKTsKKwkJ CWVjX2ludm0oeiwgcG9pbnQtPnosIGN0eCk7CisKKwkJCW1waV9yZXNpemUoeiwgY3R4LT5wLT5u bGltYnMpOworCQkJei0+bmxpbWJzID0gY3R4LT5wLT5ubGltYnM7CisKKwkJCWlmICh4KSB7CisJ CQkJbXBpX3Jlc2l6ZSh4LCBjdHgtPnAtPm5saW1icyk7CisJCQkJeC0+bmxpbWJzID0gY3R4LT5w LT5ubGltYnM7CisJCQkJY3R4LT5tdWxtKHgsIHBvaW50LT54LCB6LCBjdHgpOworCQkJfQorCQkJ aWYgKHkpIHsKKwkJCQltcGlfcmVzaXplKHksIGN0eC0+cC0+bmxpbWJzKTsKKwkJCQl5LT5ubGlt YnMgPSBjdHgtPnAtPm5saW1iczsKKwkJCQljdHgtPm11bG0oeSwgcG9pbnQtPnksIHosIGN0eCk7 CisJCQl9CisKKwkJCW1waV9mcmVlKHopOworCQl9CisJCXJldHVybiAwOworCisJZGVmYXVsdDoK KwkJcmV0dXJuIC0xOworCX0KK30KK0VYUE9SVF9TWU1CT0xfR1BMKG1waV9lY19nZXRfYWZmaW5l KTsKKworLyogIFJFU1VMVCA9IDIgKiBQT0lOVCAgKFdlaWVyc3RyYXNzIHZlcnNpb24pLiAqLwor c3RhdGljIHZvaWQgZHVwX3BvaW50X3dlaWVyc3RyYXNzKE1QSV9QT0lOVCByZXN1bHQsCisJCU1Q SV9QT0lOVCBwb2ludCwgc3RydWN0IG1waV9lY19jdHggKmN0eCkKK3sKKyNkZWZpbmUgeDMgKHJl c3VsdC0+eCkKKyNkZWZpbmUgeTMgKHJlc3VsdC0+eSkKKyNkZWZpbmUgejMgKHJlc3VsdC0+eikK KyNkZWZpbmUgdDEgKGN0eC0+dC5zY3JhdGNoWzBdKQorI2RlZmluZSB0MiAoY3R4LT50LnNjcmF0 Y2hbMV0pCisjZGVmaW5lIHQzIChjdHgtPnQuc2NyYXRjaFsyXSkKKyNkZWZpbmUgbDEgKGN0eC0+ dC5zY3JhdGNoWzNdKQorI2RlZmluZSBsMiAoY3R4LT50LnNjcmF0Y2hbNF0pCisjZGVmaW5lIGwz IChjdHgtPnQuc2NyYXRjaFs1XSkKKworCWlmICghbXBpX2NtcF91aShwb2ludC0+eSwgMCkgfHwg IW1waV9jbXBfdWkocG9pbnQtPnosIDApKSB7CisJCS8qIFBfeSA9PSAwIHx8IFBfeiA9PSAwID0+ IFsxOjE6MF0gKi8KKwkJbXBpX3NldF91aSh4MywgMSk7CisJCW1waV9zZXRfdWkoeTMsIDEpOwor CQltcGlfc2V0X3VpKHozLCAwKTsKKwl9IGVsc2UgeworCQlpZiAoZWNfZ2V0X2FfaXNfcG1pbnVz MyhjdHgpKSB7CisJCQkvKiBVc2UgdGhlIGZhc3RlciBjYXNlLiAgKi8KKwkJCS8qIEwxID0gMyhY IC0gWl4yKShYICsgWl4yKSAqLworCQkJLyogICAgICAgICAgICAgICAgICAgICAgICAgIFQxOiB1 c2VkIGZvciBaXjIuICovCisJCQkvKiAgICAgICAgICAgICAgICAgICAgICAgICAgVDI6IHVzZWQg Zm9yIHRoZSByaWdodCB0ZXJtLiAqLworCQkJZWNfcG93Mih0MSwgcG9pbnQtPnosIGN0eCk7CisJ CQllY19zdWJtKGwxLCBwb2ludC0+eCwgdDEsIGN0eCk7CisJCQllY19tdWxtKGwxLCBsMSwgbXBp X2NvbnN0KE1QSV9DX1RIUkVFKSwgY3R4KTsKKwkJCWVjX2FkZG0odDIsIHBvaW50LT54LCB0MSwg Y3R4KTsKKwkJCWVjX211bG0obDEsIGwxLCB0MiwgY3R4KTsKKwkJfSBlbHNlIHsKKwkJCS8qIFN0 YW5kYXJkIGNhc2UuICovCisJCQkvKiBMMSA9IDNYXjIgKyBhWl40ICovCisJCQkvKiAgICAgICAg ICAgICAgICAgICAgICAgICAgVDE6IHVzZWQgZm9yIGFaXjQuICovCisJCQllY19wb3cyKGwxLCBw b2ludC0+eCwgY3R4KTsKKwkJCWVjX211bG0obDEsIGwxLCBtcGlfY29uc3QoTVBJX0NfVEhSRUUp LCBjdHgpOworCQkJZWNfcG93bSh0MSwgcG9pbnQtPnosIG1waV9jb25zdChNUElfQ19GT1VSKSwg Y3R4KTsKKwkJCWVjX211bG0odDEsIHQxLCBjdHgtPmEsIGN0eCk7CisJCQllY19hZGRtKGwxLCBs MSwgdDEsIGN0eCk7CisJCX0KKwkJLyogWjMgPSAyWVogKi8KKwkJZWNfbXVsbSh6MywgcG9pbnQt PnksIHBvaW50LT56LCBjdHgpOworCQllY19tdWwyKHozLCB6MywgY3R4KTsKKworCQkvKiBMMiA9 IDRYWV4yICovCisJCS8qICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgVDI6IHVzZWQgZm9y IFkyOyByZXF1aXJlZCBsYXRlci4gKi8KKwkJZWNfcG93Mih0MiwgcG9pbnQtPnksIGN0eCk7CisJ CWVjX211bG0obDIsIHQyLCBwb2ludC0+eCwgY3R4KTsKKwkJZWNfbXVsbShsMiwgbDIsIG1waV9j b25zdChNUElfQ19GT1VSKSwgY3R4KTsKKworCQkvKiBYMyA9IEwxXjIgLSAyTDIgKi8KKwkJLyog ICAgICAgICAgICAgICAgICAgICAgICAgICAgICBUMTogdXNlZCBmb3IgTDJeMi4gKi8KKwkJZWNf cG93Mih4MywgbDEsIGN0eCk7CisJCWVjX211bDIodDEsIGwyLCBjdHgpOworCQllY19zdWJtKHgz LCB4MywgdDEsIGN0eCk7CisKKwkJLyogTDMgPSA4WV40ICovCisJCS8qICAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgVDI6IHRha2VuIGZyb20gYWJvdmUuICovCisJCWVjX3BvdzIodDIsIHQy LCBjdHgpOworCQllY19tdWxtKGwzLCB0MiwgbXBpX2NvbnN0KE1QSV9DX0VJR0hUKSwgY3R4KTsK KworCQkvKiBZMyA9IEwxKEwyIC0gWDMpIC0gTDMgKi8KKwkJZWNfc3VibSh5MywgbDIsIHgzLCBj dHgpOworCQllY19tdWxtKHkzLCB5MywgbDEsIGN0eCk7CisJCWVjX3N1Ym0oeTMsIHkzLCBsMywg Y3R4KTsKKwl9CisKKyN1bmRlZiB4MworI3VuZGVmIHkzCisjdW5kZWYgejMKKyN1bmRlZiB0MQor I3VuZGVmIHQyCisjdW5kZWYgdDMKKyN1bmRlZiBsMQorI3VuZGVmIGwyCisjdW5kZWYgbDMKK30K KworLyogIFJFU1VMVCA9IDIgKiBQT0lOVCAgKE1vbnRnb21lcnkgdmVyc2lvbikuICovCitzdGF0 aWMgdm9pZCBkdXBfcG9pbnRfbW9udGdvbWVyeShNUElfUE9JTlQgcmVzdWx0LAorCQkJCU1QSV9Q T0lOVCBwb2ludCwgc3RydWN0IG1waV9lY19jdHggKmN0eCkKK3sKKwkodm9pZClyZXN1bHQ7CisJ KHZvaWQpcG9pbnQ7CisJKHZvaWQpY3R4OworCWxvZ19mYXRhbCgiJXM6ICVzIG5vdCB5ZXQgc3Vw cG9ydGVkXG4iLAorCQkJIm1waV9lY19kdXBfcG9pbnQiLCAiTW9udGdvbWVyeSIpOworfQorCisv KiAgUkVTVUxUID0gMiAqIFBPSU5UICAoVHdpc3RlZCBFZHdhcmRzIHZlcnNpb24pLiAqLworc3Rh dGljIHZvaWQgZHVwX3BvaW50X2Vkd2FyZHMoTVBJX1BPSU5UIHJlc3VsdCwKKwkJTVBJX1BPSU5U IHBvaW50LCBzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4KQoreworI2RlZmluZSBYMSAocG9pbnQtPngp CisjZGVmaW5lIFkxIChwb2ludC0+eSkKKyNkZWZpbmUgWjEgKHBvaW50LT56KQorI2RlZmluZSBY MyAocmVzdWx0LT54KQorI2RlZmluZSBZMyAocmVzdWx0LT55KQorI2RlZmluZSBaMyAocmVzdWx0 LT56KQorI2RlZmluZSBCIChjdHgtPnQuc2NyYXRjaFswXSkKKyNkZWZpbmUgQyAoY3R4LT50LnNj cmF0Y2hbMV0pCisjZGVmaW5lIEQgKGN0eC0+dC5zY3JhdGNoWzJdKQorI2RlZmluZSBFIChjdHgt PnQuc2NyYXRjaFszXSkKKyNkZWZpbmUgRiAoY3R4LT50LnNjcmF0Y2hbNF0pCisjZGVmaW5lIEgg KGN0eC0+dC5zY3JhdGNoWzVdKQorI2RlZmluZSBKIChjdHgtPnQuc2NyYXRjaFs2XSkKKworCS8q IENvbXB1dGU6IChYXzMgOiBZXzMgOiBaXzMpID0gMiggWF8xIDogWV8xIDogWl8xICkgKi8KKwor CS8qIEIgPSAoWF8xICsgWV8xKV4yICAqLworCWN0eC0+YWRkbShCLCBYMSwgWTEsIGN0eCk7CisJ Y3R4LT5wb3cyKEIsIEIsIGN0eCk7CisKKwkvKiBDID0gWF8xXjIgKi8KKwkvKiBEID0gWV8xXjIg Ki8KKwljdHgtPnBvdzIoQywgWDEsIGN0eCk7CisJY3R4LT5wb3cyKEQsIFkxLCBjdHgpOworCisJ LyogRSA9IGFDICovCisJaWYgKGN0eC0+ZGlhbGVjdCA9PSBFQ0NfRElBTEVDVF9FRDI1NTE5KQor CQljdHgtPnN1Ym0oRSwgY3R4LT5wLCBDLCBjdHgpOworCWVsc2UKKwkJY3R4LT5tdWxtKEUsIGN0 eC0+YSwgQywgY3R4KTsKKworCS8qIEYgPSBFICsgRCAqLworCWN0eC0+YWRkbShGLCBFLCBELCBj dHgpOworCisJLyogSCA9IFpfMV4yICovCisJY3R4LT5wb3cyKEgsIFoxLCBjdHgpOworCisJLyog SiA9IEYgLSAySCAqLworCWN0eC0+bXVsMihKLCBILCBjdHgpOworCWN0eC0+c3VibShKLCBGLCBK LCBjdHgpOworCisJLyogWF8zID0gKEIgLSBDIC0gRCkgwrcgSiAqLworCWN0eC0+c3VibShYMywg QiwgQywgY3R4KTsKKwljdHgtPnN1Ym0oWDMsIFgzLCBELCBjdHgpOworCWN0eC0+bXVsbShYMywg WDMsIEosIGN0eCk7CisKKwkvKiBZXzMgPSBGIMK3IChFIC0gRCkgKi8KKwljdHgtPnN1Ym0oWTMs IEUsIEQsIGN0eCk7CisJY3R4LT5tdWxtKFkzLCBZMywgRiwgY3R4KTsKKworCS8qIFpfMyA9IEYg wrcgSiAqLworCWN0eC0+bXVsbShaMywgRiwgSiwgY3R4KTsKKworI3VuZGVmIFgxCisjdW5kZWYg WTEKKyN1bmRlZiBaMQorI3VuZGVmIFgzCisjdW5kZWYgWTMKKyN1bmRlZiBaMworI3VuZGVmIEIK KyN1bmRlZiBDCisjdW5kZWYgRAorI3VuZGVmIEUKKyN1bmRlZiBGCisjdW5kZWYgSAorI3VuZGVm IEoKK30KKworLyogIFJFU1VMVCA9IDIgKiBQT0lOVCAgKi8KK3N0YXRpYyB2b2lkCittcGlfZWNf ZHVwX3BvaW50KE1QSV9QT0lOVCByZXN1bHQsIE1QSV9QT0lOVCBwb2ludCwgc3RydWN0IG1waV9l Y19jdHggKmN0eCkKK3sKKwlzd2l0Y2ggKGN0eC0+bW9kZWwpIHsKKwljYXNlIE1QSV9FQ19XRUlF UlNUUkFTUzoKKwkJZHVwX3BvaW50X3dlaWVyc3RyYXNzKHJlc3VsdCwgcG9pbnQsIGN0eCk7CisJ CWJyZWFrOworCWNhc2UgTVBJX0VDX01PTlRHT01FUlk6CisJCWR1cF9wb2ludF9tb250Z29tZXJ5 KHJlc3VsdCwgcG9pbnQsIGN0eCk7CisJCWJyZWFrOworCWNhc2UgTVBJX0VDX0VEV0FSRFM6CisJ CWR1cF9wb2ludF9lZHdhcmRzKHJlc3VsdCwgcG9pbnQsIGN0eCk7CisJCWJyZWFrOworCX0KK30K KworLyogUkVTVUxUID0gUDEgKyBQMiAgKFdlaWVyc3RyYXNzIHZlcnNpb24pLiovCitzdGF0aWMg dm9pZCBhZGRfcG9pbnRzX3dlaWVyc3RyYXNzKE1QSV9QT0lOVCByZXN1bHQsCisJCU1QSV9QT0lO VCBwMSwgTVBJX1BPSU5UIHAyLAorCQlzdHJ1Y3QgbXBpX2VjX2N0eCAqY3R4KQoreworI2RlZmlu ZSB4MSAocDEtPngpCisjZGVmaW5lIHkxIChwMS0+eSkKKyNkZWZpbmUgejEgKHAxLT56KQorI2Rl ZmluZSB4MiAocDItPngpCisjZGVmaW5lIHkyIChwMi0+eSkKKyNkZWZpbmUgejIgKHAyLT56KQor I2RlZmluZSB4MyAocmVzdWx0LT54KQorI2RlZmluZSB5MyAocmVzdWx0LT55KQorI2RlZmluZSB6 MyAocmVzdWx0LT56KQorI2RlZmluZSBsMSAoY3R4LT50LnNjcmF0Y2hbMF0pCisjZGVmaW5lIGwy IChjdHgtPnQuc2NyYXRjaFsxXSkKKyNkZWZpbmUgbDMgKGN0eC0+dC5zY3JhdGNoWzJdKQorI2Rl ZmluZSBsNCAoY3R4LT50LnNjcmF0Y2hbM10pCisjZGVmaW5lIGw1IChjdHgtPnQuc2NyYXRjaFs0 XSkKKyNkZWZpbmUgbDYgKGN0eC0+dC5zY3JhdGNoWzVdKQorI2RlZmluZSBsNyAoY3R4LT50LnNj cmF0Y2hbNl0pCisjZGVmaW5lIGw4IChjdHgtPnQuc2NyYXRjaFs3XSkKKyNkZWZpbmUgbDkgKGN0 eC0+dC5zY3JhdGNoWzhdKQorI2RlZmluZSB0MSAoY3R4LT50LnNjcmF0Y2hbOV0pCisjZGVmaW5l IHQyIChjdHgtPnQuc2NyYXRjaFsxMF0pCisKKwlpZiAoKCFtcGlfY21wKHgxLCB4MikpICYmICgh bXBpX2NtcCh5MSwgeTIpKSAmJiAoIW1waV9jbXAoejEsIHoyKSkpIHsKKwkJLyogU2FtZSBwb2lu dDsgbmVlZCB0byBjYWxsIHRoZSBkdXBsaWNhdGUgZnVuY3Rpb24uICAqLworCQltcGlfZWNfZHVw X3BvaW50KHJlc3VsdCwgcDEsIGN0eCk7CisJfSBlbHNlIGlmICghbXBpX2NtcF91aSh6MSwgMCkp IHsKKwkJLyogUDEgaXMgYXQgaW5maW5pdHkuICAqLworCQltcGlfc2V0KHgzLCBwMi0+eCk7CisJ CW1waV9zZXQoeTMsIHAyLT55KTsKKwkJbXBpX3NldCh6MywgcDItPnopOworCX0gZWxzZSBpZiAo IW1waV9jbXBfdWkoejIsIDApKSB7CisJCS8qIFAyIGlzIGF0IGluZmluaXR5LiAgKi8KKwkJbXBp X3NldCh4MywgcDEtPngpOworCQltcGlfc2V0KHkzLCBwMS0+eSk7CisJCW1waV9zZXQoejMsIHAx LT56KTsKKwl9IGVsc2UgeworCQlpbnQgejFfaXNfb25lID0gIW1waV9jbXBfdWkoejEsIDEpOwor CQlpbnQgejJfaXNfb25lID0gIW1waV9jbXBfdWkoejIsIDEpOworCisJCS8qIGwxID0geDEgejJe MiAgKi8KKwkJLyogbDIgPSB4MiB6MV4yICAqLworCQlpZiAoejJfaXNfb25lKQorCQkJbXBpX3Nl dChsMSwgeDEpOworCQllbHNlIHsKKwkJCWVjX3BvdzIobDEsIHoyLCBjdHgpOworCQkJZWNfbXVs bShsMSwgbDEsIHgxLCBjdHgpOworCQl9CisJCWlmICh6MV9pc19vbmUpCisJCQltcGlfc2V0KGwy LCB4Mik7CisJCWVsc2UgeworCQkJZWNfcG93MihsMiwgejEsIGN0eCk7CisJCQllY19tdWxtKGwy LCBsMiwgeDIsIGN0eCk7CisJCX0KKwkJLyogbDMgPSBsMSAtIGwyICovCisJCWVjX3N1Ym0obDMs IGwxLCBsMiwgY3R4KTsKKwkJLyogbDQgPSB5MSB6Ml4zICAqLworCQllY19wb3dtKGw0LCB6Miwg bXBpX2NvbnN0KE1QSV9DX1RIUkVFKSwgY3R4KTsKKwkJZWNfbXVsbShsNCwgbDQsIHkxLCBjdHgp OworCQkvKiBsNSA9IHkyIHoxXjMgICovCisJCWVjX3Bvd20obDUsIHoxLCBtcGlfY29uc3QoTVBJ X0NfVEhSRUUpLCBjdHgpOworCQllY19tdWxtKGw1LCBsNSwgeTIsIGN0eCk7CisJCS8qIGw2ID0g bDQgLSBsNSAgKi8KKwkJZWNfc3VibShsNiwgbDQsIGw1LCBjdHgpOworCisJCWlmICghbXBpX2Nt cF91aShsMywgMCkpIHsKKwkJCWlmICghbXBpX2NtcF91aShsNiwgMCkpIHsKKwkJCQkvKiBQMSBh bmQgUDIgYXJlIHRoZSBzYW1lIC0gdXNlIGR1cGxpY2F0ZSBmdW5jdGlvbi4gKi8KKwkJCQltcGlf ZWNfZHVwX3BvaW50KHJlc3VsdCwgcDEsIGN0eCk7CisJCQl9IGVsc2UgeworCQkJCS8qIFAxIGlz IHRoZSBpbnZlcnNlIG9mIFAyLiAgKi8KKwkJCQltcGlfc2V0X3VpKHgzLCAxKTsKKwkJCQltcGlf c2V0X3VpKHkzLCAxKTsKKwkJCQltcGlfc2V0X3VpKHozLCAwKTsKKwkJCX0KKwkJfSBlbHNlIHsK KwkJCS8qIGw3ID0gbDEgKyBsMiAgKi8KKwkJCWVjX2FkZG0obDcsIGwxLCBsMiwgY3R4KTsKKwkJ CS8qIGw4ID0gbDQgKyBsNSAgKi8KKwkJCWVjX2FkZG0obDgsIGw0LCBsNSwgY3R4KTsKKwkJCS8q IHozID0gejEgejIgbDMgICovCisJCQllY19tdWxtKHozLCB6MSwgejIsIGN0eCk7CisJCQllY19t dWxtKHozLCB6MywgbDMsIGN0eCk7CisJCQkvKiB4MyA9IGw2XjIgLSBsNyBsM14yICAqLworCQkJ ZWNfcG93Mih0MSwgbDYsIGN0eCk7CisJCQllY19wb3cyKHQyLCBsMywgY3R4KTsKKwkJCWVjX211 bG0odDIsIHQyLCBsNywgY3R4KTsKKwkJCWVjX3N1Ym0oeDMsIHQxLCB0MiwgY3R4KTsKKwkJCS8q IGw5ID0gbDcgbDNeMiAtIDIgeDMgICovCisJCQllY19tdWwyKHQxLCB4MywgY3R4KTsKKwkJCWVj X3N1Ym0obDksIHQyLCB0MSwgY3R4KTsKKwkJCS8qIHkzID0gKGw5IGw2IC0gbDggbDNeMykvMiAg Ki8KKwkJCWVjX211bG0obDksIGw5LCBsNiwgY3R4KTsKKwkJCWVjX3Bvd20odDEsIGwzLCBtcGlf Y29uc3QoTVBJX0NfVEhSRUUpLCBjdHgpOyAvKiBmaXhtZTogVXNlIHNhdmVkIHZhbHVlKi8KKwkJ CWVjX211bG0odDEsIHQxLCBsOCwgY3R4KTsKKwkJCWVjX3N1Ym0oeTMsIGw5LCB0MSwgY3R4KTsK KwkJCWVjX211bG0oeTMsIHkzLCBlY19nZXRfdHdvX2ludl9wKGN0eCksIGN0eCk7CisJCX0KKwl9 CisKKyN1bmRlZiB4MQorI3VuZGVmIHkxCisjdW5kZWYgejEKKyN1bmRlZiB4MgorI3VuZGVmIHky CisjdW5kZWYgejIKKyN1bmRlZiB4MworI3VuZGVmIHkzCisjdW5kZWYgejMKKyN1bmRlZiBsMQor I3VuZGVmIGwyCisjdW5kZWYgbDMKKyN1bmRlZiBsNAorI3VuZGVmIGw1CisjdW5kZWYgbDYKKyN1 bmRlZiBsNworI3VuZGVmIGw4CisjdW5kZWYgbDkKKyN1bmRlZiB0MQorI3VuZGVmIHQyCit9CisK Ky8qIFJFU1VMVCA9IFAxICsgUDIgIChNb250Z29tZXJ5IHZlcnNpb24pLiovCitzdGF0aWMgdm9p ZCBhZGRfcG9pbnRzX21vbnRnb21lcnkoTVBJX1BPSU5UIHJlc3VsdCwKKwkJTVBJX1BPSU5UIHAx LCBNUElfUE9JTlQgcDIsCisJCXN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJKHZvaWQpcmVz dWx0OworCSh2b2lkKXAxOworCSh2b2lkKXAyOworCSh2b2lkKWN0eDsKKwlsb2dfZmF0YWwoIiVz OiAlcyBub3QgeWV0IHN1cHBvcnRlZFxuIiwKKwkJCSJtcGlfZWNfYWRkX3BvaW50cyIsICJNb250 Z29tZXJ5Iik7Cit9CisKKy8qIFJFU1VMVCA9IFAxICsgUDIgIChUd2lzdGVkIEVkd2FyZHMgdmVy c2lvbikuKi8KK3N0YXRpYyB2b2lkIGFkZF9wb2ludHNfZWR3YXJkcyhNUElfUE9JTlQgcmVzdWx0 LAorCQlNUElfUE9JTlQgcDEsIE1QSV9QT0lOVCBwMiwKKwkJc3RydWN0IG1waV9lY19jdHggKmN0 eCkKK3sKKyNkZWZpbmUgWDEgKHAxLT54KQorI2RlZmluZSBZMSAocDEtPnkpCisjZGVmaW5lIFox IChwMS0+eikKKyNkZWZpbmUgWDIgKHAyLT54KQorI2RlZmluZSBZMiAocDItPnkpCisjZGVmaW5l IFoyIChwMi0+eikKKyNkZWZpbmUgWDMgKHJlc3VsdC0+eCkKKyNkZWZpbmUgWTMgKHJlc3VsdC0+ eSkKKyNkZWZpbmUgWjMgKHJlc3VsdC0+eikKKyNkZWZpbmUgQSAoY3R4LT50LnNjcmF0Y2hbMF0p CisjZGVmaW5lIEIgKGN0eC0+dC5zY3JhdGNoWzFdKQorI2RlZmluZSBDIChjdHgtPnQuc2NyYXRj aFsyXSkKKyNkZWZpbmUgRCAoY3R4LT50LnNjcmF0Y2hbM10pCisjZGVmaW5lIEUgKGN0eC0+dC5z Y3JhdGNoWzRdKQorI2RlZmluZSBGIChjdHgtPnQuc2NyYXRjaFs1XSkKKyNkZWZpbmUgRyAoY3R4 LT50LnNjcmF0Y2hbNl0pCisjZGVmaW5lIHRtcCAoY3R4LT50LnNjcmF0Y2hbN10pCisKKwlwb2lu dF9yZXNpemUocmVzdWx0LCBjdHgpOworCisJLyogQ29tcHV0ZTogKFhfMyA6IFlfMyA6IFpfMykg PSAoWF8xIDogWV8xIDogWl8xKSArIChYXzIgOiBZXzIgOiBaXzMpICovCisKKwkvKiBBID0gWjEg wrcgWjIgKi8KKwljdHgtPm11bG0oQSwgWjEsIFoyLCBjdHgpOworCisJLyogQiA9IEFeMiAqLwor CWN0eC0+cG93MihCLCBBLCBjdHgpOworCisJLyogQyA9IFgxIMK3IFgyICovCisJY3R4LT5tdWxt KEMsIFgxLCBYMiwgY3R4KTsKKworCS8qIEQgPSBZMSDCtyBZMiAqLworCWN0eC0+bXVsbShELCBZ MSwgWTIsIGN0eCk7CisKKwkvKiBFID0gZCDCtyBDIMK3IEQgKi8KKwljdHgtPm11bG0oRSwgY3R4 LT5iLCBDLCBjdHgpOworCWN0eC0+bXVsbShFLCBFLCBELCBjdHgpOworCisJLyogRiA9IEIgLSBF ICovCisJY3R4LT5zdWJtKEYsIEIsIEUsIGN0eCk7CisKKwkvKiBHID0gQiArIEUgKi8KKwljdHgt PmFkZG0oRywgQiwgRSwgY3R4KTsKKworCS8qIFhfMyA9IEEgwrcgRiDCtyAoKFhfMSArIFlfMSkg wrcgKFhfMiArIFlfMikgLSBDIC0gRCkgKi8KKwljdHgtPmFkZG0odG1wLCBYMSwgWTEsIGN0eCk7 CisJY3R4LT5hZGRtKFgzLCBYMiwgWTIsIGN0eCk7CisJY3R4LT5tdWxtKFgzLCBYMywgdG1wLCBj dHgpOworCWN0eC0+c3VibShYMywgWDMsIEMsIGN0eCk7CisJY3R4LT5zdWJtKFgzLCBYMywgRCwg Y3R4KTsKKwljdHgtPm11bG0oWDMsIFgzLCBGLCBjdHgpOworCWN0eC0+bXVsbShYMywgWDMsIEEs IGN0eCk7CisKKwkvKiBZXzMgPSBBIMK3IEcgwrcgKEQgLSBhQykgKi8KKwlpZiAoY3R4LT5kaWFs ZWN0ID09IEVDQ19ESUFMRUNUX0VEMjU1MTkpIHsKKwkJY3R4LT5hZGRtKFkzLCBELCBDLCBjdHgp OworCX0gZWxzZSB7CisJCWN0eC0+bXVsbShZMywgY3R4LT5hLCBDLCBjdHgpOworCQljdHgtPnN1 Ym0oWTMsIEQsIFkzLCBjdHgpOworCX0KKwljdHgtPm11bG0oWTMsIFkzLCBHLCBjdHgpOworCWN0 eC0+bXVsbShZMywgWTMsIEEsIGN0eCk7CisKKwkvKiBaXzMgPSBGIMK3IEcgKi8KKwljdHgtPm11 bG0oWjMsIEYsIEcsIGN0eCk7CisKKworI3VuZGVmIFgxCisjdW5kZWYgWTEKKyN1bmRlZiBaMQor I3VuZGVmIFgyCisjdW5kZWYgWTIKKyN1bmRlZiBaMgorI3VuZGVmIFgzCisjdW5kZWYgWTMKKyN1 bmRlZiBaMworI3VuZGVmIEEKKyN1bmRlZiBCCisjdW5kZWYgQworI3VuZGVmIEQKKyN1bmRlZiBF CisjdW5kZWYgRgorI3VuZGVmIEcKKyN1bmRlZiB0bXAKK30KKworLyogQ29tcHV0ZSBhIHN0ZXAg b2YgTW9udGdvbWVyeSBMYWRkZXIgKG9ubHkgdXNlIFggYW5kIFogaW4gdGhlIHBvaW50KS4KKyAq IElucHV0czogIFAxLCBQMiwgYW5kIHgtY29vcmRpbmF0ZSBvZiBESUYgPSBQMSAtIFAxLgorICog T3V0cHV0czogUFJEID0gMiAqIFAxIGFuZCAgU1VNID0gUDEgKyBQMi4KKyAqLworc3RhdGljIHZv aWQgbW9udGdvbWVyeV9sYWRkZXIoTVBJX1BPSU5UIHByZCwgTVBJX1BPSU5UIHN1bSwKKwkJTVBJ X1BPSU5UIHAxLCBNUElfUE9JTlQgcDIsIE1QSSBkaWZfeCwKKwkJc3RydWN0IG1waV9lY19jdHgg KmN0eCkKK3sKKwljdHgtPmFkZG0oc3VtLT54LCBwMi0+eCwgcDItPnosIGN0eCk7CisJY3R4LT5z dWJtKHAyLT56LCBwMi0+eCwgcDItPnosIGN0eCk7CisJY3R4LT5hZGRtKHByZC0+eCwgcDEtPngs IHAxLT56LCBjdHgpOworCWN0eC0+c3VibShwMS0+eiwgcDEtPngsIHAxLT56LCBjdHgpOworCWN0 eC0+bXVsbShwMi0+eCwgcDEtPnosIHN1bS0+eCwgY3R4KTsKKwljdHgtPm11bG0ocDItPnosIHBy ZC0+eCwgcDItPnosIGN0eCk7CisJY3R4LT5wb3cyKHAxLT54LCBwcmQtPngsIGN0eCk7CisJY3R4 LT5wb3cyKHAxLT56LCBwMS0+eiwgY3R4KTsKKwljdHgtPmFkZG0oc3VtLT54LCBwMi0+eCwgcDIt PnosIGN0eCk7CisJY3R4LT5zdWJtKHAyLT56LCBwMi0+eCwgcDItPnosIGN0eCk7CisJY3R4LT5t dWxtKHByZC0+eCwgcDEtPngsIHAxLT56LCBjdHgpOworCWN0eC0+c3VibShwMS0+eiwgcDEtPngs IHAxLT56LCBjdHgpOworCWN0eC0+cG93MihzdW0tPngsIHN1bS0+eCwgY3R4KTsKKwljdHgtPnBv dzIoc3VtLT56LCBwMi0+eiwgY3R4KTsKKwljdHgtPm11bG0ocHJkLT56LCBwMS0+eiwgY3R4LT5h LCBjdHgpOyAvKiBDVFgtPkE6IChhLTIpLzQgKi8KKwljdHgtPm11bG0oc3VtLT56LCBzdW0tPnos IGRpZl94LCBjdHgpOworCWN0eC0+YWRkbShwcmQtPnosIHAxLT54LCBwcmQtPnosIGN0eCk7CisJ Y3R4LT5tdWxtKHByZC0+eiwgcHJkLT56LCBwMS0+eiwgY3R4KTsKK30KKworLyogUkVTVUxUID0g UDEgKyBQMiAqLwordm9pZCBtcGlfZWNfYWRkX3BvaW50cyhNUElfUE9JTlQgcmVzdWx0LAorCQlN UElfUE9JTlQgcDEsIE1QSV9QT0lOVCBwMiwKKwkJc3RydWN0IG1waV9lY19jdHggKmN0eCkKK3sK Kwlzd2l0Y2ggKGN0eC0+bW9kZWwpIHsKKwljYXNlIE1QSV9FQ19XRUlFUlNUUkFTUzoKKwkJYWRk X3BvaW50c193ZWllcnN0cmFzcyhyZXN1bHQsIHAxLCBwMiwgY3R4KTsKKwkJYnJlYWs7CisJY2Fz ZSBNUElfRUNfTU9OVEdPTUVSWToKKwkJYWRkX3BvaW50c19tb250Z29tZXJ5KHJlc3VsdCwgcDEs IHAyLCBjdHgpOworCQlicmVhazsKKwljYXNlIE1QSV9FQ19FRFdBUkRTOgorCQlhZGRfcG9pbnRz X2Vkd2FyZHMocmVzdWx0LCBwMSwgcDIsIGN0eCk7CisJCWJyZWFrOworCX0KK30KK0VYUE9SVF9T WU1CT0xfR1BMKG1waV9lY19hZGRfcG9pbnRzKTsKKworLyogU2NhbGFyIHBvaW50IG11bHRpcGxp Y2F0aW9uIC0gdGhlIG1haW4gZnVuY3Rpb24gZm9yIEVDQy4gIElmIHRha2VzCisgKiBhbiBpbnRl Z2VyIFNDQUxBUiBhbmQgYSBQT0lOVCBhcyB3ZWxsIGFzIHRoZSB1c3VhbCBjb250ZXh0IENUWC4K KyAqIFJFU1VMVCB3aWxsIGJlIHNldCB0byB0aGUgcmVzdWx0aW5nIHBvaW50LgorICovCit2b2lk IG1waV9lY19tdWxfcG9pbnQoTVBJX1BPSU5UIHJlc3VsdCwKKwkJCU1QSSBzY2FsYXIsIE1QSV9Q T0lOVCBwb2ludCwKKwkJCXN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJTVBJIHgxLCB5MSwg ejEsIGssIGgsIHl5OworCXVuc2lnbmVkIGludCBpLCBsb29wczsKKwlzdHJ1Y3QgZ2NyeV9tcGlf cG9pbnQgcDEsIHAyLCBwMWludjsKKworCWlmIChjdHgtPm1vZGVsID09IE1QSV9FQ19FRFdBUkRT KSB7CisJCS8qIFNpbXBsZSBsZWZ0IHRvIHJpZ2h0IGJpbmFyeSBtZXRob2QuICBBbGdvcml0aG0g My4yNyBmcm9tCisJCSAqIHthdXRob3I9e0hhbmtlcnNvbiwgRGFycmVsIGFuZCBNZW5lemVzLCBB bGZyZWQgSi4gYW5kIFZhbnN0b25lLCBTY290dH0sCisJCSAqICB0aXRsZSA9IHtHdWlkZSB0byBF bGxpcHRpYyBDdXJ2ZSBDcnlwdG9ncmFwaHl9LAorCQkgKiAgeWVhciA9IHsyMDAzfSwgaXNibiA9 IHswMzg3OTUyNzNYfSwKKwkJICogIHVybCA9IHtodHRwOi8vd3d3LmNhY3IubWF0aC51d2F0ZXJs b28uY2EvZWNjL30sCisJCSAqICBwdWJsaXNoZXIgPSB7U3ByaW5nZXItVmVybGFnIE5ldyBZb3Jr LCBJbmMufX0KKwkJICovCisJCXVuc2lnbmVkIGludCBuYml0czsKKwkJaW50IGo7CisKKwkJaWYg KG1waV9jbXAoc2NhbGFyLCBjdHgtPnApID49IDApCisJCQluYml0cyA9IG1waV9nZXRfbmJpdHMo c2NhbGFyKTsKKwkJZWxzZQorCQkJbmJpdHMgPSBtcGlfZ2V0X25iaXRzKGN0eC0+cCk7CisKKwkJ bXBpX3NldF91aShyZXN1bHQtPngsIDApOworCQltcGlfc2V0X3VpKHJlc3VsdC0+eSwgMSk7CisJ CW1waV9zZXRfdWkocmVzdWx0LT56LCAxKTsKKwkJcG9pbnRfcmVzaXplKHBvaW50LCBjdHgpOwor CisJCXBvaW50X3Jlc2l6ZShyZXN1bHQsIGN0eCk7CisJCXBvaW50X3Jlc2l6ZShwb2ludCwgY3R4 KTsKKworCQlmb3IgKGogPSBuYml0cy0xOyBqID49IDA7IGotLSkgeworCQkJbXBpX2VjX2R1cF9w b2ludChyZXN1bHQsIHJlc3VsdCwgY3R4KTsKKwkJCWlmIChtcGlfdGVzdF9iaXQoc2NhbGFyLCBq KSkKKwkJCQltcGlfZWNfYWRkX3BvaW50cyhyZXN1bHQsIHJlc3VsdCwgcG9pbnQsIGN0eCk7CisJ CX0KKwkJcmV0dXJuOworCX0gZWxzZSBpZiAoY3R4LT5tb2RlbCA9PSBNUElfRUNfTU9OVEdPTUVS WSkgeworCQl1bnNpZ25lZCBpbnQgbmJpdHM7CisJCWludCBqOworCQlzdHJ1Y3QgZ2NyeV9tcGlf cG9pbnQgcDFfLCBwMl87CisJCU1QSV9QT0lOVCBxMSwgcTIsIHByZCwgc3VtOworCQl1bnNpZ25l ZCBsb25nIHN3OworCQltcGlfc2l6ZV90IHJzaXplOworCQlpbnQgc2NhbGFyX2NvcGllZCA9IDA7 CisKKwkJLyogQ29tcHV0ZSBzY2FsYXIgcG9pbnQgbXVsdGlwbGljYXRpb24gd2l0aCBNb250Z29t ZXJ5IExhZGRlci4KKwkJICogTm90ZSB0aGF0IHdlIGRvbid0IHVzZSBZLWNvb3JkaW5hdGUgaW4g dGhlIHBvaW50cyBhdCBhbGwuCisJCSAqIFJFU1VMVC0+WSB3aWxsIGJlIGZpbGxlZCBieSB6ZXJv LgorCQkgKi8KKworCQluYml0cyA9IG1waV9nZXRfbmJpdHMoc2NhbGFyKTsKKwkJcG9pbnRfaW5p dCgmcDEpOworCQlwb2ludF9pbml0KCZwMik7CisJCXBvaW50X2luaXQoJnAxXyk7CisJCXBvaW50 X2luaXQoJnAyXyk7CisJCW1waV9zZXRfdWkocDEueCwgMSk7CisJCW1waV9mcmVlKHAyLngpOwor CQlwMi54ID0gbXBpX2NvcHkocG9pbnQtPngpOworCQltcGlfc2V0X3VpKHAyLnosIDEpOworCisJ CXBvaW50X3Jlc2l6ZSgmcDEsIGN0eCk7CisJCXBvaW50X3Jlc2l6ZSgmcDIsIGN0eCk7CisJCXBv aW50X3Jlc2l6ZSgmcDFfLCBjdHgpOworCQlwb2ludF9yZXNpemUoJnAyXywgY3R4KTsKKworCQlt cGlfcmVzaXplKHBvaW50LT54LCBjdHgtPnAtPm5saW1icyk7CisJCXBvaW50LT54LT5ubGltYnMg PSBjdHgtPnAtPm5saW1iczsKKworCQlxMSA9ICZwMTsKKwkJcTIgPSAmcDI7CisJCXByZCA9ICZw MV87CisJCXN1bSA9ICZwMl87CisKKwkJZm9yIChqID0gbmJpdHMtMTsgaiA+PSAwOyBqLS0pIHsK KwkJCU1QSV9QT0lOVCB0OworCisJCQlzdyA9IG1waV90ZXN0X2JpdChzY2FsYXIsIGopOworCQkJ cG9pbnRfc3dhcF9jb25kKHExLCBxMiwgc3csIGN0eCk7CisJCQltb250Z29tZXJ5X2xhZGRlcihw cmQsIHN1bSwgcTEsIHEyLCBwb2ludC0+eCwgY3R4KTsKKwkJCXBvaW50X3N3YXBfY29uZChwcmQs IHN1bSwgc3csIGN0eCk7CisJCQl0ID0gcTE7ICBxMSA9IHByZDsgIHByZCA9IHQ7CisJCQl0ID0g cTI7ICBxMiA9IHN1bTsgIHN1bSA9IHQ7CisJCX0KKworCQltcGlfY2xlYXIocmVzdWx0LT55KTsK KwkJc3cgPSAobmJpdHMgJiAxKTsKKwkJcG9pbnRfc3dhcF9jb25kKCZwMSwgJnAxXywgc3csIGN0 eCk7CisKKwkJcnNpemUgPSBwMS56LT5ubGltYnM7CisJCU1QTl9OT1JNQUxJWkUocDEuei0+ZCwg cnNpemUpOworCQlpZiAocnNpemUgPT0gMCkgeworCQkJbXBpX3NldF91aShyZXN1bHQtPngsIDEp OworCQkJbXBpX3NldF91aShyZXN1bHQtPnosIDApOworCQl9IGVsc2UgeworCQkJejEgPSBtcGlf bmV3KDApOworCQkJZWNfaW52bSh6MSwgcDEueiwgY3R4KTsKKwkJCWVjX211bG0ocmVzdWx0LT54 LCBwMS54LCB6MSwgY3R4KTsKKwkJCW1waV9zZXRfdWkocmVzdWx0LT56LCAxKTsKKwkJCW1waV9m cmVlKHoxKTsKKwkJfQorCisJCXBvaW50X2ZyZWUoJnAxKTsKKwkJcG9pbnRfZnJlZSgmcDIpOwor CQlwb2ludF9mcmVlKCZwMV8pOworCQlwb2ludF9mcmVlKCZwMl8pOworCQlpZiAoc2NhbGFyX2Nv cGllZCkKKwkJCW1waV9mcmVlKHNjYWxhcik7CisJCXJldHVybjsKKwl9CisKKwl4MSA9IG1waV9h bGxvY19saWtlKGN0eC0+cCk7CisJeTEgPSBtcGlfYWxsb2NfbGlrZShjdHgtPnApOworCWggID0g bXBpX2FsbG9jX2xpa2UoY3R4LT5wKTsKKwlrICA9IG1waV9jb3B5KHNjYWxhcik7CisJeXkgPSBt cGlfY29weShwb2ludC0+eSk7CisKKwlpZiAobXBpX2hhc19zaWduKGspKSB7CisJCWstPnNpZ24g PSAwOworCQllY19pbnZtKHl5LCB5eSwgY3R4KTsKKwl9CisKKwlpZiAoIW1waV9jbXBfdWkocG9p bnQtPnosIDEpKSB7CisJCW1waV9zZXQoeDEsIHBvaW50LT54KTsKKwkJbXBpX3NldCh5MSwgeXkp OworCX0gZWxzZSB7CisJCU1QSSB6MiwgejM7CisKKwkJejIgPSBtcGlfYWxsb2NfbGlrZShjdHgt PnApOworCQl6MyA9IG1waV9hbGxvY19saWtlKGN0eC0+cCk7CisJCWVjX211bG0oejIsIHBvaW50 LT56LCBwb2ludC0+eiwgY3R4KTsKKwkJZWNfbXVsbSh6MywgcG9pbnQtPnosIHoyLCBjdHgpOwor CQllY19pbnZtKHoyLCB6MiwgY3R4KTsKKwkJZWNfbXVsbSh4MSwgcG9pbnQtPngsIHoyLCBjdHgp OworCQllY19pbnZtKHozLCB6MywgY3R4KTsKKwkJZWNfbXVsbSh5MSwgeXksIHozLCBjdHgpOwor CQltcGlfZnJlZSh6Mik7CisJCW1waV9mcmVlKHozKTsKKwl9CisJejEgPSBtcGlfY29weShtcGlf Y29uc3QoTVBJX0NfT05FKSk7CisKKwltcGlfbXVsKGgsIGssIG1waV9jb25zdChNUElfQ19USFJF RSkpOyAvKiBoID0gM2sgKi8KKwlsb29wcyA9IG1waV9nZXRfbmJpdHMoaCk7CisJaWYgKGxvb3Bz IDwgMikgeworCQkvKiBJZiBTQ0FMQVIgaXMgemVybywgdGhlIGFib3ZlIG1waV9tdWwgc2V0cyBI IHRvIHplcm8gYW5kIHRodXMKKwkJICogTE9PUHMgd2lsbCBiZSB6ZXJvLiAgVG8gYXZvaWQgYW4g dW5kZXJmbG93IG9mIEkgaW4gdGhlIG1haW4KKwkJICogbG9vcCB3ZSBzZXQgTE9PUCB0byAyIGFu ZCB0aGUgcmVzdWx0IHRvICgwLDAsMCkuCisJCSAqLworCQlsb29wcyA9IDI7CisJCW1waV9jbGVh cihyZXN1bHQtPngpOworCQltcGlfY2xlYXIocmVzdWx0LT55KTsKKwkJbXBpX2NsZWFyKHJlc3Vs dC0+eik7CisJfSBlbHNlIHsKKwkJbXBpX3NldChyZXN1bHQtPngsIHBvaW50LT54KTsKKwkJbXBp X3NldChyZXN1bHQtPnksIHl5KTsKKwkJbXBpX3NldChyZXN1bHQtPnosIHBvaW50LT56KTsKKwl9 CisJbXBpX2ZyZWUoeXkpOyB5eSA9IE5VTEw7CisKKwlwMS54ID0geDE7IHgxID0gTlVMTDsKKwlw MS55ID0geTE7IHkxID0gTlVMTDsKKwlwMS56ID0gejE7IHoxID0gTlVMTDsKKwlwb2ludF9pbml0 KCZwMik7CisJcG9pbnRfaW5pdCgmcDFpbnYpOworCisJLyogSW52ZXJ0IHBvaW50OiB5ID0gcCAt IHkgbW9kIHAgICovCisJcG9pbnRfc2V0KCZwMWludiwgJnAxKTsKKwllY19zdWJtKHAxaW52Lnks IGN0eC0+cCwgcDFpbnYueSwgY3R4KTsKKworCWZvciAoaSA9IGxvb3BzLTI7IGkgPiAwOyBpLS0p IHsKKwkJbXBpX2VjX2R1cF9wb2ludChyZXN1bHQsIHJlc3VsdCwgY3R4KTsKKwkJaWYgKG1waV90 ZXN0X2JpdChoLCBpKSA9PSAxICYmIG1waV90ZXN0X2JpdChrLCBpKSA9PSAwKSB7CisJCQlwb2lu dF9zZXQoJnAyLCByZXN1bHQpOworCQkJbXBpX2VjX2FkZF9wb2ludHMocmVzdWx0LCAmcDIsICZw MSwgY3R4KTsKKwkJfQorCQlpZiAobXBpX3Rlc3RfYml0KGgsIGkpID09IDAgJiYgbXBpX3Rlc3Rf Yml0KGssIGkpID09IDEpIHsKKwkJCXBvaW50X3NldCgmcDIsIHJlc3VsdCk7CisJCQltcGlfZWNf YWRkX3BvaW50cyhyZXN1bHQsICZwMiwgJnAxaW52LCBjdHgpOworCQl9CisJfQorCisJcG9pbnRf ZnJlZSgmcDEpOworCXBvaW50X2ZyZWUoJnAyKTsKKwlwb2ludF9mcmVlKCZwMWludik7CisJbXBp X2ZyZWUoaCk7CisJbXBpX2ZyZWUoayk7Cit9CitFWFBPUlRfU1lNQk9MX0dQTChtcGlfZWNfbXVs X3BvaW50KTsKKworLyogUmV0dXJuIHRydWUgaWYgUE9JTlQgaXMgb24gdGhlIGN1cnZlIGRlc2Ny aWJlZCBieSBDVFguICAqLworaW50IG1waV9lY19jdXJ2ZV9wb2ludChNUElfUE9JTlQgcG9pbnQs IHN0cnVjdCBtcGlfZWNfY3R4ICpjdHgpCit7CisJaW50IHJlcyA9IDA7CisJTVBJIHgsIHksIHc7 CisKKwl4ID0gbXBpX25ldygwKTsKKwl5ID0gbXBpX25ldygwKTsKKwl3ID0gbXBpX25ldygwKTsK KworCS8qIENoZWNrIHRoYXQgdGhlIHBvaW50IGlzIGluIHJhbmdlLiAgVGhpcyBuZWVkcyB0byBi ZSBkb25lIGhlcmUgYW5kCisJICogbm90IGFmdGVyIGNvbnZlcnNpb24gdG8gYWZmaW5lIGNvb3Jk aW5hdGVzLgorCSAqLworCWlmIChtcGlfY21wYWJzKHBvaW50LT54LCBjdHgtPnApID49IDApCisJ CWdvdG8gbGVhdmU7CisJaWYgKG1waV9jbXBhYnMocG9pbnQtPnksIGN0eC0+cCkgPj0gMCkKKwkJ Z290byBsZWF2ZTsKKwlpZiAobXBpX2NtcGFicyhwb2ludC0+eiwgY3R4LT5wKSA+PSAwKQorCQln b3RvIGxlYXZlOworCisJc3dpdGNoIChjdHgtPm1vZGVsKSB7CisJY2FzZSBNUElfRUNfV0VJRVJT VFJBU1M6CisJCXsKKwkJCU1QSSB4eHg7CisKKwkJCWlmIChtcGlfZWNfZ2V0X2FmZmluZSh4LCB5 LCBwb2ludCwgY3R4KSkKKwkJCQlnb3RvIGxlYXZlOworCisJCQl4eHggPSBtcGlfbmV3KDApOwor CisJCQkvKiB5XjIgPT0geF4zICsgYcK3eCArIGIgKi8KKwkJCWVjX3BvdzIoeSwgeSwgY3R4KTsK KworCQkJZWNfcG93Myh4eHgsIHgsIGN0eCk7CisJCQllY19tdWxtKHcsIGN0eC0+YSwgeCwgY3R4 KTsKKwkJCWVjX2FkZG0odywgdywgY3R4LT5iLCBjdHgpOworCQkJZWNfYWRkbSh3LCB3LCB4eHgs IGN0eCk7CisKKwkJCWlmICghbXBpX2NtcCh5LCB3KSkKKwkJCQlyZXMgPSAxOworCisJCQltcGlf ZnJlZSh4eHgpOworCQl9CisJCWJyZWFrOworCisJY2FzZSBNUElfRUNfTU9OVEdPTUVSWToKKwkJ eworI2RlZmluZSB4eCB5CisJCQkvKiBXaXRoIE1vbnRnb21lcnkgY3VydmUsIG9ubHkgWC1jb29y ZGluYXRlIGlzIHZhbGlkLiAqLworCQkJaWYgKG1waV9lY19nZXRfYWZmaW5lKHgsIE5VTEwsIHBv aW50LCBjdHgpKQorCQkJCWdvdG8gbGVhdmU7CisKKwkJCS8qIFRoZSBlcXVhdGlvbiBpczogYiAq IHleMiA9PSB4XjMgKyBhIMK3IHheMiArIHggKi8KKwkJCS8qIFdlIGNoZWNrIGlmIHJpZ2h0IGhh bmQgaXMgcXVhZHJhdGljIHJlc2lkdWUgb3Igbm90IGJ5CisJCQkgKiBFdWxlcidzIGNyaXRlcmlv bi4KKwkJCSAqLworCQkJLyogQ1RYLT5BIGhhcyAoYS0yKS80IGFuZCBDVFgtPkIgaGFzIGJeLTEg Ki8KKwkJCWVjX211bG0odywgY3R4LT5hLCBtcGlfY29uc3QoTVBJX0NfRk9VUiksIGN0eCk7CisJ CQllY19hZGRtKHcsIHcsIG1waV9jb25zdChNUElfQ19UV08pLCBjdHgpOworCQkJZWNfbXVsbSh3 LCB3LCB4LCBjdHgpOworCQkJZWNfcG93Mih4eCwgeCwgY3R4KTsKKwkJCWVjX2FkZG0odywgdywg eHgsIGN0eCk7CisJCQllY19hZGRtKHcsIHcsIG1waV9jb25zdChNUElfQ19PTkUpLCBjdHgpOwor CQkJZWNfbXVsbSh3LCB3LCB4LCBjdHgpOworCQkJZWNfbXVsbSh3LCB3LCBjdHgtPmIsIGN0eCk7 CisjdW5kZWYgeHgKKwkJCS8qIENvbXB1dGUgRXVsZXIncyBjcml0ZXJpb246IHdeKHAtMSkvMiAq LworI2RlZmluZSBwX21pbnVzMSB5CisJCQllY19zdWJtKHBfbWludXMxLCBjdHgtPnAsIG1waV9j b25zdChNUElfQ19PTkUpLCBjdHgpOworCQkJbXBpX3JzaGlmdChwX21pbnVzMSwgcF9taW51czEs IDEpOworCQkJZWNfcG93bSh3LCB3LCBwX21pbnVzMSwgY3R4KTsKKworCQkJcmVzID0gIW1waV9j bXBfdWkodywgMSk7CisjdW5kZWYgcF9taW51czEKKwkJfQorCQlicmVhazsKKworCWNhc2UgTVBJ X0VDX0VEV0FSRFM6CisJCXsKKwkJCWlmIChtcGlfZWNfZ2V0X2FmZmluZSh4LCB5LCBwb2ludCwg Y3R4KSkKKwkJCQlnb3RvIGxlYXZlOworCisJCQltcGlfcmVzaXplKHcsIGN0eC0+cC0+bmxpbWJz KTsKKwkJCXctPm5saW1icyA9IGN0eC0+cC0+bmxpbWJzOworCisJCQkvKiBhIMK3IHheMiArIHle MiAtIDEgLSBiIMK3IHheMiDCtyB5XjIgPT0gMCAqLworCQkJY3R4LT5wb3cyKHgsIHgsIGN0eCk7 CisJCQljdHgtPnBvdzIoeSwgeSwgY3R4KTsKKwkJCWlmIChjdHgtPmRpYWxlY3QgPT0gRUNDX0RJ QUxFQ1RfRUQyNTUxOSkKKwkJCQljdHgtPnN1Ym0odywgY3R4LT5wLCB4LCBjdHgpOworCQkJZWxz ZQorCQkJCWN0eC0+bXVsbSh3LCBjdHgtPmEsIHgsIGN0eCk7CisJCQljdHgtPmFkZG0odywgdywg eSwgY3R4KTsKKwkJCWN0eC0+bXVsbSh4LCB4LCB5LCBjdHgpOworCQkJY3R4LT5tdWxtKHgsIHgs IGN0eC0+YiwgY3R4KTsKKwkJCWN0eC0+c3VibSh3LCB3LCB4LCBjdHgpOworCQkJaWYgKCFtcGlf Y21wX3VpKHcsIDEpKQorCQkJCXJlcyA9IDE7CisJCX0KKwkJYnJlYWs7CisJfQorCitsZWF2ZToK KwltcGlfZnJlZSh3KTsKKwltcGlfZnJlZSh4KTsKKwltcGlfZnJlZSh5KTsKKworCXJldHVybiBy ZXM7Cit9CitFWFBPUlRfU1lNQk9MX0dQTChtcGlfZWNfY3VydmVfcG9pbnQpOwotLSAKMi4xOS4x LjMuZ2U1NmU0ZjcKCgpfX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19fX19f X19fXwpsaW51eC1hcm0ta2VybmVsIG1haWxpbmcgbGlzdApsaW51eC1hcm0ta2VybmVsQGxpc3Rz LmluZnJhZGVhZC5vcmcKaHR0cDovL2xpc3RzLmluZnJhZGVhZC5vcmcvbWFpbG1hbi9saXN0aW5m by9saW51eC1hcm0ta2VybmVsCg==