1656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* crypto/bn/bn_mul.c */ 2656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * All rights reserved. 4656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 5656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This package is an SSL implementation written 6656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * by Eric Young (eay@cryptsoft.com). 7656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The implementation was written so as to conform with Netscapes SSL. 8656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 9656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This library is free for commercial and non-commercial use as long as 10656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the following conditions are aheared to. The following conditions 11656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * apply to all code found in this distribution, be it the RC4, RSA, 12656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * included with this distribution is covered by the same copyright terms 14656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 16656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Copyright remains Eric Young's, and as such any Copyright notices in 17656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the code are not to be removed. 18656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * If this package is used in a product, Eric Young should be given attribution 19656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * as the author of the parts of the library used. 20656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * This can be in the form of a textual message at program startup or 21656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * in documentation (online or textual) provided with the package. 22656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 23656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Redistribution and use in source and binary forms, with or without 24656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * modification, are permitted provided that the following conditions 25656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * are met: 26656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 1. Redistributions of source code must retain the copyright 27656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer. 28656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 29656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * notice, this list of conditions and the following disclaimer in the 30656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * documentation and/or other materials provided with the distribution. 31656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 3. All advertising materials mentioning features or use of this software 32656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * must display the following acknowledgement: 33656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes cryptographic software written by 34656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * Eric Young (eay@cryptsoft.com)" 35656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The word 'cryptographic' can be left out if the rouines from the library 36656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * being used are not cryptographic related :-). 37656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 4. If you include any Windows specific code (or a derivative thereof) from 38656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * the apps directory (application code) you must include an acknowledgement: 39656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 41656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * SUCH DAMAGE. 52656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * 53656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * The licence and distribution terms for any publically available version or 54656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * derivative of this code cannot be changed. i.e. this code cannot simply be 55656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * copied and put under another distribution licence 56656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * [including the GNU Public Licence.] 57656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 58656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 59656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifndef BN_DEBUG 60656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# undef NDEBUG /* avoid conflicting definitions */ 61656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# define NDEBUG 62656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 63656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 64656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include <stdio.h> 65656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include <assert.h> 66656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "cryptlib.h" 67656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#include "bn_lcl.h" 68656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 69656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#if defined(OPENSSL_NO_ASM) || !defined(OPENSSL_BN_ASM_PART_WORDS) 70656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* Here follows specialised variants of bn_add_words() and 71656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(). They have the property performing operations on 72656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project arrays of different sizes. The sizes of those arrays is expressed through 73656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project cl, which is the common length ( basicall, min(len(a),len(b)) ), and dl, 74656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project which is the delta between the two lengths, calculated as len(a)-len(b). 75656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project All lengths are the number of BN_ULONGs... For the operations that require 76656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a result array as parameter, it must have the length cl+abs(dl). 77656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project These functions should probably end up in bn_asm.c as soon as there are 78656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project assembler counterparts for the systems that use assembler files. */ 79656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 80656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source ProjectBN_ULONG bn_sub_part_words(BN_ULONG *r, 81656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BN_ULONG *a, const BN_ULONG *b, 82656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int cl, int dl) 83656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 84656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG c, t; 85656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 86656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project assert(cl >= 0); 87656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c = bn_sub_words(r, a, b, cl); 88656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 89656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl == 0) 90656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return c; 91656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 92656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += cl; 93656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a += cl; 94656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b += cl; 95656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 96656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl < 0) 97656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 98656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 99656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_sub_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); 100656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 101656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (;;) 102656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 103656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = b[0]; 104656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[0] = (0-t-c)&BN_MASK2; 105656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=1; 106656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 107656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 108656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = b[1]; 109656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = (0-t-c)&BN_MASK2; 110656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=1; 111656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 112656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 113656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = b[2]; 114656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = (0-t-c)&BN_MASK2; 115656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=1; 116656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 117656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 118656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = b[3]; 119656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = (0-t-c)&BN_MASK2; 120656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=1; 121656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 122656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 123656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b += 4; 124656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 125656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 126656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 127656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 128656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 129656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int save_dl = dl; 130656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 131656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c = %d)\n", cl, dl, c); 132656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 133656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while(c) 134656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 135656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = a[0]; 136656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[0] = (t-c)&BN_MASK2; 137656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=0; 138656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 139656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 140656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = a[1]; 141656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = (t-c)&BN_MASK2; 142656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=0; 143656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 144656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 145656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = a[2]; 146656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = (t-c)&BN_MASK2; 147656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=0; 148656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 149656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 150656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = a[3]; 151656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = (t-c)&BN_MASK2; 152656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (t != 0) c=0; 153656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 154656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 155656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project save_dl = dl; 156656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a += 4; 157656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 158656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 159656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl > 0) 160656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 161656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 162656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); 163656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 164656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (save_dl > dl) 165656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 166656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project switch (save_dl - dl) 167656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 168656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 1: 169656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = a[1]; 170656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 171656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 2: 172656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = a[2]; 173656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 174656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 3: 175656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = a[3]; 176656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 177656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 178656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a += 4; 179656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 180656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 181656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 182656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl > 0) 183656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 184656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 185656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_sub_part_words %d + %d (dl > 0, copy)\n", cl, dl); 186656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 187656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for(;;) 188656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 189656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[0] = a[0]; 190656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 191656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = a[1]; 192656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 193656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = a[2]; 194656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 195656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = a[3]; 196656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 197656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 198656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a += 4; 199656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 200656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 201656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 202656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 203656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return c; 204656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 205656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 206656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 207656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source ProjectBN_ULONG bn_add_part_words(BN_ULONG *r, 208656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project const BN_ULONG *a, const BN_ULONG *b, 209656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int cl, int dl) 210656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 211656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG c, l, t; 212656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 213656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project assert(cl >= 0); 214656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c = bn_add_words(r, a, b, cl); 215656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 216656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl == 0) 217656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return c; 218656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 219656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += cl; 220656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a += cl; 221656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b += cl; 222656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 223656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl < 0) 224656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 225656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int save_dl = dl; 226656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 227656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c = %d)\n", cl, dl, c); 228656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 229656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (c) 230656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 231656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project l=(c+b[0])&BN_MASK2; 232656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(l < c); 233656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[0]=l; 234656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 235656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 236656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project l=(c+b[1])&BN_MASK2; 237656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(l < c); 238656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1]=l; 239656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 240656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 241656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project l=(c+b[2])&BN_MASK2; 242656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(l < c); 243656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2]=l; 244656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 245656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 246656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project l=(c+b[3])&BN_MASK2; 247656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(l < c); 248656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3]=l; 249656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 250656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 251656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project save_dl = dl; 252656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b+=4; 253656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r+=4; 254656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 255656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl < 0) 256656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 257656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 258656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, c == 0)\n", cl, dl); 259656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 260656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (save_dl < dl) 261656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 262656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project switch (dl - save_dl) 263656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 264656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 1: 265656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = b[1]; 266656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 267656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 2: 268656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = b[2]; 269656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 270656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 3: 271656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = b[3]; 272656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 273656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 274656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b += 4; 275656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 276656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 277656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 278656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl < 0) 279656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 280656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 281656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_add_part_words %d + %d (dl < 0, copy)\n", cl, dl); 282656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 283656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for(;;) 284656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 285656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[0] = b[0]; 286656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 287656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = b[1]; 288656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 289656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = b[2]; 290656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 291656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = b[3]; 292656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (++dl >= 0) break; 293656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 294656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b += 4; 295656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 296656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 297656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 298656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 299656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 300656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 301656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int save_dl = dl; 302656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 303656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_add_part_words %d + %d (dl > 0)\n", cl, dl); 304656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 305656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project while (c) 306656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 307656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t=(a[0]+c)&BN_MASK2; 308656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(t < c); 309656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[0]=t; 310656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 311656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 312656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t=(a[1]+c)&BN_MASK2; 313656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(t < c); 314656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1]=t; 315656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 316656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 317656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t=(a[2]+c)&BN_MASK2; 318656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(t < c); 319656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2]=t; 320656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 321656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 322656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t=(a[3]+c)&BN_MASK2; 323656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c=(t < c); 324656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3]=t; 325656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 326656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 327656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project save_dl = dl; 328656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a+=4; 329656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r+=4; 330656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 331656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 332656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, c == 0)\n", cl, dl); 333656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 334656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl > 0) 335656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 336656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (save_dl > dl) 337656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 338656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project switch (save_dl - dl) 339656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 340656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 1: 341656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = a[1]; 342656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 343656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 2: 344656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = a[2]; 345656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 346656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 3: 347656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = a[3]; 348656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 349656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 350656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a += 4; 351656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 352656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 353656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 354656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (dl > 0) 355656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 356656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 357656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr, " bn_add_part_words %d + %d (dl > 0, copy)\n", cl, dl); 358656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 359656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for(;;) 360656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 361656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[0] = a[0]; 362656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 363656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[1] = a[1]; 364656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 365656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[2] = a[2]; 366656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 367656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[3] = a[3]; 368656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--dl <= 0) break; 369656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 370656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project a += 4; 371656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r += 4; 372656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 373656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 374656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 375656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return c; 376656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 377656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 378656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_RECURSION 379656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* Karatsuba recursive multiplication algorithm 380656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * (cf. Knuth, The Art of Computer Programming, Vol. 2) */ 381656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 382656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* r is 2*n2 words in size, 383656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * a and b are both n2 words in size. 384656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * n2 must be a power of 2. 385656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * We multiply and return the result. 386656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * t must be 2*n2 words in size 387656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * We calculate 388656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * a[0]*b[0] 389656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0]) 390656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * a[1]*b[1] 391656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 392656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* dnX may not be positive, but n2/2+dnX has to be */ 393656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 394656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int dna, int dnb, BN_ULONG *t) 395656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 396656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int n=n2/2,c1,c2; 397656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int tna=n+dna, tnb=n+dnb; 398656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project unsigned int neg,zero; 399656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG ln,lo,*p; 400656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 401656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# ifdef BN_COUNT 402656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr," bn_mul_recursive %d%+d * %d%+d\n",n2,dna,n2,dnb); 403656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 404656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# ifdef BN_MUL_COMBA 405656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# if 0 406656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n2 == 4) 407656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 408656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba4(r,a,b); 409656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return; 410656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 411656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 412656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Only call bn_mul_comba 8 if n2 == 8 and the 413656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * two arrays are complete [steve] 414656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 415656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n2 == 8 && dna == 0 && dnb == 0) 416656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 417656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(r,a,b); 418656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return; 419656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 420656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif /* BN_MUL_COMBA */ 421656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Else do normal multiply */ 422656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) 423656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 424656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_normal(r,a,n2+dna,b,n2+dnb); 425656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((dna + dnb) < 0) 426656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&r[2*n2 + dna + dnb], 0, 427656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project sizeof(BN_ULONG) * -(dna + dnb)); 428656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return; 429656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 430656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* r=(a[0]-a[1])*(b[1]-b[0]) */ 431656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); 432656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); 433656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project zero=neg=0; 434656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project switch (c1*3+c2) 435656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 436656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -4: 437656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 438656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 439656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 440656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -3: 441656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project zero=1; 442656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 443656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -2: 444656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 445656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ 446656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=1; 447656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 448656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -1: 449656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 0: 450656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 1: 451656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project zero=1; 452656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 453656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 2: 454656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ 455656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 456656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=1; 457656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 458656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 3: 459656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project zero=1; 460656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 461656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 4: 462656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, a, &(a[n]),tna,n-tna); 463656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); 464656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 465656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 466656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 467656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# ifdef BN_MUL_COMBA 468656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n == 4 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba4 could take 469656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project extra args to do this well */ 470656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 471656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!zero) 472656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba4(&(t[n2]),t,&(t[n])); 473656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 474656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(t[n2]),0,8*sizeof(BN_ULONG)); 475656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 476656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba4(r,a,b); 477656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba4(&(r[n2]),&(a[n]),&(b[n])); 478656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 479656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else if (n == 8 && dna == 0 && dnb == 0) /* XXX: bn_mul_comba8 could 480656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project take extra args to do this 481656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project well */ 482656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 483656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!zero) 484656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(&(t[n2]),t,&(t[n])); 485656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 486656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(t[n2]),0,16*sizeof(BN_ULONG)); 487656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 488656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(r,a,b); 489656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(&(r[n2]),&(a[n]),&(b[n])); 490656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 491656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 492656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif /* BN_MUL_COMBA */ 493656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 494656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project p= &(t[n2*2]); 495656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (!zero) 496656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); 497656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 498656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(t[n2]),0,n2*sizeof(BN_ULONG)); 499656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(r,a,b,n,0,0,p); 500656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]),n,dna,dnb,p); 501656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 502656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 503656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 504656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[10] holds (a[0]*b[0]) 505656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[32] holds (b[1]*b[1]) 506656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 507656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 508656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); 509656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 510656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (neg) /* if t[32] is negative */ 511656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 512656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); 513656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 514656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 515656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 516656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Might have a carry */ 517656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2)); 518656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 519656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 520656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 521656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[10] holds (a[0]*b[0]) 522656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[32] holds (b[1]*b[1]) 523656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * c1 holds the carry bits 524656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 525656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); 526656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (c1) 527656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 528656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project p= &(r[n+n2]); 529656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lo= *p; 530656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ln=(lo+c1)&BN_MASK2; 531656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project *p=ln; 532656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 533656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* The overflow will stop before we over write 534656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * words we should not overwrite */ 535656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (ln < (BN_ULONG)c1) 536656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 537656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project do { 538656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project p++; 539656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lo= *p; 540656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ln=(lo+1)&BN_MASK2; 541656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project *p=ln; 542656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } while (ln == 0); 543656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 544656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 545656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 546656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 547656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* n+tn is the word length 548656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * t needs to be n*4 is size, as does r */ 549656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* tnX may not be negative but less than n */ 550656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n, 551656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int tna, int tnb, BN_ULONG *t) 552656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 553656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i,j,n2=n*2; 55443c12e3d4f9bbbbd4a8ba7b149686437514bc6b6Brian Carlstrom int c1,c2,neg; 555656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG ln,lo,*p; 556656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 557656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# ifdef BN_COUNT 558656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr," bn_mul_part_recursive (%d%+d) * (%d%+d)\n", 559656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project n, tna, n, tnb); 560656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 561656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n < 8) 562656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 563656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_normal(r,a,n+tna,b,n+tnb); 564656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return; 565656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 566656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 567656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* r=(a[0]-a[1])*(b[1]-b[0]) */ 568656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=bn_cmp_part_words(a,&(a[n]),tna,n-tna); 569656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c2=bn_cmp_part_words(&(b[n]),b,tnb,tnb-n); 57043c12e3d4f9bbbbd4a8ba7b149686437514bc6b6Brian Carlstrom neg=0; 571656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project switch (c1*3+c2) 572656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 573656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -4: 574656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 575656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 576656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 577656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -3: 578656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* break; */ 579656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -2: 580656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, &(a[n]),a, tna,tna-n); /* - */ 581656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); /* + */ 582656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=1; 583656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 584656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -1: 585656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 0: 586656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 1: 587656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* break; */ 588656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 2: 589656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, a, &(a[n]),tna,n-tna); /* + */ 590656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),b, &(b[n]),tnb,n-tnb); /* - */ 591656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=1; 592656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 593656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 3: 594656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* break; */ 595656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 4: 596656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(t, a, &(a[n]),tna,n-tna); 597656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_part_words(&(t[n]),&(b[n]),b, tnb,tnb-n); 598656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 599656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 600656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* The zero case isn't yet implemented here. The speedup 601656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project would probably be negligible. */ 602656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# if 0 603656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n == 4) 604656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 605656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba4(&(t[n2]),t,&(t[n])); 606656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba4(r,a,b); 607656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_normal(&(r[n2]),&(a[n]),tn,&(b[n]),tn); 608656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(r[n2+tn*2]),0,sizeof(BN_ULONG)*(n2-tn*2)); 609656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 610656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 611656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 612656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n == 8) 613656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 614656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(&(t[n2]),t,&(t[n])); 615656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(r,a,b); 616656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); 617656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(r[n2+tna+tnb]),0,sizeof(BN_ULONG)*(n2-tna-tnb)); 618656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 619656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 620656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 621656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project p= &(t[n2*2]); 622656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(&(t[n2]),t,&(t[n]),n,0,0,p); 623656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(r,a,b,n,0,0,p); 624656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i=n/2; 625656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* If there is only a bottom half to the number, 626656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * just do it */ 627656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (tna > tnb) 628656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j = tna - i; 629656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 630656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j = tnb - i; 631656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (j == 0) 632656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 633656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(&(r[n2]),&(a[n]),&(b[n]), 634656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i,tna-i,tnb-i,p); 635656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(r[n2+i*2]),0,sizeof(BN_ULONG)*(n2-i*2)); 636656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 637656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else if (j > 0) /* eg, n == 16, i == 8 and tn == 11 */ 638656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 639656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_part_recursive(&(r[n2]),&(a[n]),&(b[n]), 640656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i,tna-i,tnb-i,p); 641656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(r[n2+tna+tnb]),0, 642656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project sizeof(BN_ULONG)*(n2-tna-tnb)); 643656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 644656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else /* (j < 0) eg, n == 16, i == 8 and tn == 5 */ 645656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 646656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project memset(&(r[n2]),0,sizeof(BN_ULONG)*n2); 647656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL 648656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project && tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) 649656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 650656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_normal(&(r[n2]),&(a[n]),tna,&(b[n]),tnb); 651656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 652656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 653656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 654656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (;;) 655656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 656656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i/=2; 657656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* these simplified conditions work 658656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * exclusively because difference 659656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * between tna and tnb is 1 or 0 */ 660656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i < tna || i < tnb) 661656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 662656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_part_recursive(&(r[n2]), 663656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project &(a[n]),&(b[n]), 664656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i,tna-i,tnb-i,p); 665656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 666656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 667656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else if (i == tna || i == tnb) 668656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 669656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(&(r[n2]), 670656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project &(a[n]),&(b[n]), 671656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i,tna-i,tnb-i,p); 672656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 673656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 674656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 675656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 676656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 677656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 678656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 679656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign 680656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[10] holds (a[0]*b[0]) 681656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[32] holds (b[1]*b[1]) 682656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 683656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 684656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=(int)(bn_add_words(t,r,&(r[n2]),n2)); 685656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 686656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (neg) /* if t[32] is negative */ 687656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 688656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1-=(int)(bn_sub_words(&(t[n2]),t,&(t[n2]),n2)); 689656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 690656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 691656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 692656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Might have a carry */ 693656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),t,n2)); 694656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 695656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 696656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1]) 697656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[10] holds (a[0]*b[0]) 698656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[32] holds (b[1]*b[1]) 699656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * c1 holds the carry bits 700656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 701656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1+=(int)(bn_add_words(&(r[n]),&(r[n]),&(t[n2]),n2)); 702656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (c1) 703656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 704656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project p= &(r[n+n2]); 705656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lo= *p; 706656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ln=(lo+c1)&BN_MASK2; 707656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project *p=ln; 708656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 709656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* The overflow will stop before we over write 710656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * words we should not overwrite */ 711656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (ln < (BN_ULONG)c1) 712656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 713656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project do { 714656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project p++; 715656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lo= *p; 716656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ln=(lo+1)&BN_MASK2; 717656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project *p=ln; 718656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } while (ln == 0); 719656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 720656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 721656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 722656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 723656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* a and b must be the same size, which is n2. 724656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r needs to be n2 words and t needs to be n2*2 725656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 726656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 727656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG *t) 728656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 729656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int n=n2/2; 730656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 731656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# ifdef BN_COUNT 732656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr," bn_mul_low_recursive %d * %d\n",n2,n2); 733656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 734656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 735656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(r,a,b,n,0,0,&(t[0])); 736656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) 737656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 738656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_low_recursive(&(t[0]),&(a[0]),&(b[n]),n,&(t[n2])); 739656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); 740656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_low_recursive(&(t[0]),&(a[n]),&(b[0]),n,&(t[n2])); 741656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); 742656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 743656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 744656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 745656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_low_normal(&(t[0]),&(a[0]),&(b[n]),n); 746656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_low_normal(&(t[n]),&(a[n]),&(b[0]),n); 747656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_add_words(&(r[n]),&(r[n]),&(t[0]),n); 748656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_add_words(&(r[n]),&(r[n]),&(t[n]),n); 749656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 750656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 751656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 752656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project/* a and b must be the same size, which is n2. 753656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r needs to be n2 words and t needs to be n2*2 754656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * l is the low words of the output. 755656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * t needs to be n2*3 756656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 757656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, 758656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG *t) 759656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 760656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i,n; 761656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int c1,c2; 762656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int neg,oneg,zero; 763656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG ll,lc,*lp,*mp; 764656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 765656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# ifdef BN_COUNT 766656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr," bn_mul_high %d * %d\n",n2,n2); 767656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 768656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project n=n2/2; 769656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 770656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Calculate (al-ah)*(bh-bl) */ 771656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=zero=0; 772656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=bn_cmp_words(&(a[0]),&(a[n]),n); 773656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c2=bn_cmp_words(&(b[n]),&(b[0]),n); 774656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project switch (c1*3+c2) 775656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 776656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -4: 777656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); 778656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); 779656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 780656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -3: 781656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project zero=1; 782656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 783656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -2: 784656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[0]),&(a[n]),&(a[0]),n); 785656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); 786656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=1; 787656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 788656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case -1: 789656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 0: 790656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 1: 791656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project zero=1; 792656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 793656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 2: 794656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); 795656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[n]),&(b[0]),&(b[n]),n); 796656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=1; 797656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 798656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 3: 799656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project zero=1; 800656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 801656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project case 4: 802656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[0]),&(a[0]),&(a[n]),n); 803656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(r[n]),&(b[n]),&(b[0]),n); 804656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project break; 805656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 806656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 807656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project oneg=neg; 808656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */ 809656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* r[10] = (a[1]*b[1]) */ 810656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# ifdef BN_MUL_COMBA 811656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (n == 8) 812656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 813656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(&(t[0]),&(r[0]),&(r[n])); 814656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(r,&(a[n]),&(b[n])); 815656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 816656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 817656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 818656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 819656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(&(t[0]),&(r[0]),&(r[n]),n,0,0,&(t[n2])); 820656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(r,&(a[n]),&(b[n]),n,0,0,&(t[n2])); 821656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 822656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 823656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* s0 == low(al*bl) 824656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl) 825656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * We know s0 and s1 so the only unknown is high(al*bl) 826656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl)) 827656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * high(al*bl) == s1 - (r[0]+l[0]+t[0]) 828656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 829656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (l != NULL) 830656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 831656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lp= &(t[n2+n]); 832656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=(int)(bn_add_words(lp,&(r[0]),&(l[0]),n)); 833656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 834656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 835656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 836656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=0; 837656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lp= &(r[0]); 838656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 839656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 840656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (neg) 841656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=(int)(bn_sub_words(&(t[n2]),lp,&(t[0]),n)); 842656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 843656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 844656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_add_words(&(t[n2]),lp,&(t[0]),n); 845656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project neg=0; 846656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 847656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 848656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (l != NULL) 849656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 850656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_sub_words(&(t[n2+n]),&(l[n]),&(t[n2]),n); 851656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 852656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 853656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 854656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lp= &(t[n2+n]); 855656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project mp= &(t[n2]); 856656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (i=0; i<n; i++) 857656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lp[i]=((~mp[i])+1)&BN_MASK2; 858656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 859656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 860656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* s[0] = low(al*bl) 861656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * t[3] = high(al*bl) 862656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign 863656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * r[10] = (a[1]*b[1]) 864656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 865656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* R[10] = al*bl 866656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0]) 867656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * R[32] = ah*bh 868656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 869656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* R[1]=t[3]+l[0]+r[0](+-)t[0] (have carry/borrow) 870656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * R[2]=r[0]+t[3]+r[1](+-)t[1] (have carry/borrow) 871656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project * R[3]=r[1]+(carry/borrow) 872656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project */ 873656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (l != NULL) 874656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 875656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lp= &(t[n2]); 876656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1= (int)(bn_add_words(lp,&(t[n2+n]),&(l[0]),n)); 877656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 878656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 879656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 880656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lp= &(t[n2+n]); 881656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1=0; 882656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 883656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1+=(int)(bn_add_words(&(t[n2]),lp, &(r[0]),n)); 884656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (oneg) 885656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1-=(int)(bn_sub_words(&(t[n2]),&(t[n2]),&(t[0]),n)); 886656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 887656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c1+=(int)(bn_add_words(&(t[n2]),&(t[n2]),&(t[0]),n)); 888656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 889656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c2 =(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n2+n]),n)); 890656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(r[n]),n)); 891656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (oneg) 892656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c2-=(int)(bn_sub_words(&(r[0]),&(r[0]),&(t[n]),n)); 893656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 894656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project c2+=(int)(bn_add_words(&(r[0]),&(r[0]),&(t[n]),n)); 895656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 896656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (c1 != 0) /* Add starting at r[0], could be +ve or -ve */ 897656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 898656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i=0; 899656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (c1 > 0) 900656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 901656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc=c1; 902656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project do { 903656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ll=(r[i]+lc)&BN_MASK2; 904656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[i++]=ll; 905656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc=(lc > ll); 906656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } while (lc); 907656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 908656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 909656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 910656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc= -c1; 911656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project do { 912656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ll=r[i]; 913656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[i++]=(ll-lc)&BN_MASK2; 914656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc=(lc > ll); 915656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } while (lc); 916656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 917656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 918656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (c2 != 0) /* Add starting at r[1] */ 919656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 920656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i=n; 921656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (c2 > 0) 922656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 923656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc=c2; 924656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project do { 925656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ll=(r[i]+lc)&BN_MASK2; 926656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[i++]=ll; 927656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc=(lc > ll); 928656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } while (lc); 929656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 930656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 931656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 932656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc= -c2; 933656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project do { 934656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ll=r[i]; 935656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r[i++]=(ll-lc)&BN_MASK2; 936656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project lc=(lc > ll); 937656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } while (lc); 938656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 939656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 940656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 941656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif /* BN_RECURSION */ 942656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 943656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectint BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) 944656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 945656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int ret=0; 946656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int top,al,bl; 947656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *rr; 948656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 949656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int i; 950656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 951656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_RECURSION 952656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *t=NULL; 953656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int j=0,k; 954656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 955656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 956656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 957656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr,"BN_mul %d * %d\n",a->top,b->top); 958656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 959656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 960656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(a); 961656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(b); 962656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(r); 963656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 964656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project al=a->top; 965656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bl=b->top; 966656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 967656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((al == 0) || (bl == 0)) 968656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 969656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_zero(r); 970656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(1); 971656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 972656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project top=al+bl; 973656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 974656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_start(ctx); 975656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((r == a) || (r == b)) 976656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 977656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((rr = BN_CTX_get(ctx)) == NULL) goto err; 978656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 979656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 980656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr = r; 981656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr->neg=a->neg^b->neg; 982656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 983656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 984656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i = al-bl; 985656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 986656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_MUL_COMBA 987656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i == 0) 988656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 989656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# if 0 990656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (al == 4) 991656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 992656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(rr,8) == NULL) goto err; 993656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr->top=8; 994656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba4(rr->d,a->d,b->d); 995656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto end; 996656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 997656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project# endif 998656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (al == 8) 999656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1000656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(rr,16) == NULL) goto err; 1001656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr->top=16; 1002656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_comba8(rr->d,a->d,b->d); 1003656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto end; 1004656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1005656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1006656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif /* BN_MUL_COMBA */ 1007656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_RECURSION 1008656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) 1009656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1010656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i >= -1 && i <= 1) 1011656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1012656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* Find out the power of two lower or equal 1013656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project to the longest of the two numbers */ 1014656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i >= 0) 1015656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1016656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j = BN_num_bits_word((BN_ULONG)al); 1017656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1018656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i == -1) 1019656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1020656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j = BN_num_bits_word((BN_ULONG)bl); 1021656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1022656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j = 1<<(j-1); 1023656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project assert(j <= al || j <= bl); 1024656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project k = j+j; 1025656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = BN_CTX_get(ctx); 102698d58bb80c64b02a33662f0ea80351d4a1535267Brian Carlstrom if (t == NULL) 102798d58bb80c64b02a33662f0ea80351d4a1535267Brian Carlstrom goto err; 1028656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (al > j || bl > j) 1029656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 103098d58bb80c64b02a33662f0ea80351d4a1535267Brian Carlstrom if (bn_wexpand(t,k*4) == NULL) goto err; 103198d58bb80c64b02a33662f0ea80351d4a1535267Brian Carlstrom if (bn_wexpand(rr,k*4) == NULL) goto err; 1032656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_part_recursive(rr->d,a->d,b->d, 1033656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j,al-j,bl-j,t->d); 1034656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1035656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else /* al <= j || bl <= j */ 1036656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 103798d58bb80c64b02a33662f0ea80351d4a1535267Brian Carlstrom if (bn_wexpand(t,k*2) == NULL) goto err; 103898d58bb80c64b02a33662f0ea80351d4a1535267Brian Carlstrom if (bn_wexpand(rr,k*2) == NULL) goto err; 1039656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(rr->d,a->d,b->d, 1040656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j,al-j,bl-j,t->d); 1041656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1042656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr->top=top; 1043656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto end; 1044656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1045656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#if 0 1046656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i == 1 && !BN_get_flags(b,BN_FLG_STATIC_DATA)) 1047656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1048656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *tmp_bn = (BIGNUM *)b; 1049656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(tmp_bn,al) == NULL) goto err; 1050656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project tmp_bn->d[bl]=0; 1051656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bl++; 1052656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i--; 1053656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1054656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else if (i == -1 && !BN_get_flags(a,BN_FLG_STATIC_DATA)) 1055656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1056656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BIGNUM *tmp_bn = (BIGNUM *)a; 1057656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(tmp_bn,bl) == NULL) goto err; 1058656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project tmp_bn->d[al]=0; 1059656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project al++; 1060656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project i++; 1061656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1062656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (i == 0) 1063656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1064656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* symmetric and > 4 */ 1065656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project /* 16 or larger */ 1066656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j=BN_num_bits_word((BN_ULONG)al); 1067656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project j=1<<(j-1); 1068656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project k=j+j; 1069656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project t = BN_CTX_get(ctx); 1070656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (al == j) /* exact multiple */ 1071656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1072656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(t,k*2) == NULL) goto err; 1073656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(rr,k*2) == NULL) goto err; 1074656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_recursive(rr->d,a->d,b->d,al,t->d); 1075656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1076656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 1077656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1078656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(t,k*4) == NULL) goto err; 1079656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(rr,k*4) == NULL) goto err; 1080656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_part_recursive(rr->d,a->d,b->d,al-j,j,t->d); 1081656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1082656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr->top=top; 1083656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project goto end; 1084656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1085656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 1086656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1087656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif /* BN_RECURSION */ 1088656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (bn_wexpand(rr,top) == NULL) goto err; 1089656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr->top=top; 1090656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_normal(rr->d,a->d,al,b->d,bl); 1091656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1092656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#if defined(BN_MUL_COMBA) || defined(BN_RECURSION) 1093656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectend: 1094656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 1095656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_correct_top(rr); 1096656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (r != rr) BN_copy(r,rr); 1097656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ret=1; 1098656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projecterr: 1099656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_check_top(r); 1100656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_CTX_end(ctx); 1101656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return(ret); 1102656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1103656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1104656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb) 1105656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1106656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG *rr; 1107656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1108656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 1109656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr," bn_mul_normal %d * %d\n",na,nb); 1110656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 1111656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1112656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (na < nb) 1113656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1114656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project int itmp; 1115656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project BN_ULONG *ltmp; 1116656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1117656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project itmp=na; na=nb; nb=itmp; 1118656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project ltmp=a; a=b; b=ltmp; 1119656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1120656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1121656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr= &(r[na]); 1122656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (nb <= 0) 1123656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1124656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project (void)bn_mul_words(r,a,na,0); 1125656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project return; 1126656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1127656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project else 1128656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr[0]=bn_mul_words(r,a,na,b[0]); 1129656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1130656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (;;) 1131656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1132656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--nb <= 0) return; 1133656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr[1]=bn_mul_add_words(&(r[1]),a,na,b[1]); 1134656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--nb <= 0) return; 1135656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr[2]=bn_mul_add_words(&(r[2]),a,na,b[2]); 1136656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--nb <= 0) return; 1137656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr[3]=bn_mul_add_words(&(r[3]),a,na,b[3]); 1138656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--nb <= 0) return; 1139656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr[4]=bn_mul_add_words(&(r[4]),a,na,b[4]); 1140656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project rr+=4; 1141656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r+=4; 1142656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b+=4; 1143656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1144656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1145656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1146656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Projectvoid bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n) 1147656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1148656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#ifdef BN_COUNT 1149656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project fprintf(stderr," bn_mul_low_normal %d * %d\n",n,n); 1150656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project#endif 1151656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_words(r,a,n,b[0]); 1152656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project 1153656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project for (;;) 1154656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project { 1155656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--n <= 0) return; 1156656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_add_words(&(r[1]),a,n,b[1]); 1157656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--n <= 0) return; 1158656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_add_words(&(r[2]),a,n,b[2]); 1159656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--n <= 0) return; 1160656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_add_words(&(r[3]),a,n,b[3]); 1161656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project if (--n <= 0) return; 1162656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project bn_mul_add_words(&(r[4]),a,n,b[4]); 1163656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project r+=4; 1164656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project b+=4; 1165656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1166656d9c7f52f88b3a3daccafa7655dec086c4756eThe Android Open Source Project } 1167