1/* mpih-w-sdiv -- implement udiv_qrnnd on machines with only signed 2 * division. 3 * Copyright (C) 1992, 1994, 1996, 1998, 2002 Free Software Foundation, Inc. 4 * Contributed by Peter L. Montgomery. 5 * 6 * This file is part of Libgcrypt. 7 * 8 * Libgcrypt is free software; you can redistribute it and/or modify 9 * it under the terms of the GNU Lesser General Public License as 10 * published by the Free Software Foundation; either version 2.1 of 11 * the License, or (at your option) any later version. 12 * 13 * Libgcrypt is distributed in the hope that it will be useful, 14 * but WITHOUT ANY WARRANTY; without even the implied warranty of 15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 * GNU Lesser General Public License for more details. 17 * 18 * You should have received a copy of the GNU Lesser General Public 19 * License along with this program; if not, write to the Free Software 20 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 21 */ 22 23#include <config.h> 24#include <stdio.h> 25#include <stdlib.h> 26#include "mpi-internal.h" 27#include "longlong.h" 28 29 30#if 0 /* not yet ported to MPI */ 31 32mpi_limb_t 33mpihelp_udiv_w_sdiv( mpi_limp_t *rp, 34 mpi_limp_t *a1, 35 mpi_limp_t *a0, 36 mpi_limp_t *d ) 37{ 38 mp_limb_t q, r; 39 mp_limb_t c0, c1, b1; 40 41 if ((mpi_limb_signed_t) d >= 0) 42 { 43 if (a1 < d - a1 - (a0 >> (BITS_PER_MP_LIMB - 1))) 44 { 45 /* dividend, divisor, and quotient are nonnegative */ 46 sdiv_qrnnd (q, r, a1, a0, d); 47 } 48 else 49 { 50 /* Compute c1*2^32 + c0 = a1*2^32 + a0 - 2^31*d */ 51 sub_ddmmss (c1, c0, a1, a0, d >> 1, d << (BITS_PER_MP_LIMB - 1)); 52 /* Divide (c1*2^32 + c0) by d */ 53 sdiv_qrnnd (q, r, c1, c0, d); 54 /* Add 2^31 to quotient */ 55 q += (mp_limb_t) 1 << (BITS_PER_MP_LIMB - 1); 56 } 57 } 58 else 59 { 60 b1 = d >> 1; /* d/2, between 2^30 and 2^31 - 1 */ 61 c1 = a1 >> 1; /* A/2 */ 62 c0 = (a1 << (BITS_PER_MP_LIMB - 1)) + (a0 >> 1); 63 64 if (a1 < b1) /* A < 2^32*b1, so A/2 < 2^31*b1 */ 65 { 66 sdiv_qrnnd (q, r, c1, c0, b1); /* (A/2) / (d/2) */ 67 68 r = 2*r + (a0 & 1); /* Remainder from A/(2*b1) */ 69 if ((d & 1) != 0) 70 { 71 if (r >= q) 72 r = r - q; 73 else if (q - r <= d) 74 { 75 r = r - q + d; 76 q--; 77 } 78 else 79 { 80 r = r - q + 2*d; 81 q -= 2; 82 } 83 } 84 } 85 else if (c1 < b1) /* So 2^31 <= (A/2)/b1 < 2^32 */ 86 { 87 c1 = (b1 - 1) - c1; 88 c0 = ~c0; /* logical NOT */ 89 90 sdiv_qrnnd (q, r, c1, c0, b1); /* (A/2) / (d/2) */ 91 92 q = ~q; /* (A/2)/b1 */ 93 r = (b1 - 1) - r; 94 95 r = 2*r + (a0 & 1); /* A/(2*b1) */ 96 97 if ((d & 1) != 0) 98 { 99 if (r >= q) 100 r = r - q; 101 else if (q - r <= d) 102 { 103 r = r - q + d; 104 q--; 105 } 106 else 107 { 108 r = r - q + 2*d; 109 q -= 2; 110 } 111 } 112 } 113 else /* Implies c1 = b1 */ 114 { /* Hence a1 = d - 1 = 2*b1 - 1 */ 115 if (a0 >= -d) 116 { 117 q = -1; 118 r = a0 + d; 119 } 120 else 121 { 122 q = -2; 123 r = a0 + 2*d; 124 } 125 } 126 } 127 128 *rp = r; 129 return q; 130} 131 132#endif 133 134