[BACK]Return to get_str.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / gmp-2.0.2-ssh-2 / mpn / generic

Annotation of OpenXM/src/kan96xx/gmp-2.0.2-ssh-2/mpn/generic/get_str.c, Revision 1.1.1.1

1.1       takayama    1: /* mpn_get_str -- Convert a MSIZE long limb vector pointed to by MPTR
                      2:    to a printable string in STR in base BASE.
                      3:
                      4: Copyright (C) 1991, 1992, 1993, 1994, 1996 Free Software Foundation, Inc.
                      5:
                      6: This file is part of the GNU MP Library.
                      7:
                      8: The GNU MP Library is free software; you can redistribute it and/or modify
                      9: it under the terms of the GNU Library General Public License as published by
                     10: the Free Software Foundation; either version 2 of the License, or (at your
                     11: option) any later version.
                     12:
                     13: The GNU MP Library is distributed in the hope that it will be useful, but
                     14: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
                     15: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
                     16: License for more details.
                     17:
                     18: You should have received a copy of the GNU Library General Public License
                     19: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     20: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     21: MA 02111-1307, USA. */
                     22:
                     23: #include "gmp.h"
                     24: #include "gmp-impl.h"
                     25: #include "longlong.h"
                     26:
                     27: /* Convert the limb vector pointed to by MPTR and MSIZE long to a
                     28:    char array, using base BASE for the result array.  Store the
                     29:    result in the character array STR.  STR must point to an array with
                     30:    space for the largest possible number represented by a MSIZE long
                     31:    limb vector + 1 extra character.
                     32:
                     33:    The result is NOT in Ascii, to convert it to printable format, add
                     34:    '0' or 'A' depending on the base and range.
                     35:
                     36:    Return the number of digits in the result string.
                     37:    This may include some leading zeros.
                     38:
                     39:    The limb vector pointed to by MPTR is clobbered.  */
                     40:
                     41: size_t
                     42: mpn_get_str (str, base, mptr, msize)
                     43:      unsigned char *str;
                     44:      int base;
                     45:      mp_ptr mptr;
                     46:      mp_size_t msize;
                     47: {
                     48:   mp_limb_t big_base;
                     49: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
                     50:   int normalization_steps;
                     51: #endif
                     52: #if UDIV_TIME > 2 * UMUL_TIME
                     53:   mp_limb_t big_base_inverted;
                     54: #endif
                     55:   unsigned int dig_per_u;
                     56:   mp_size_t out_len;
                     57:   register unsigned char *s;
                     58:
                     59:   big_base = __mp_bases[base].big_base;
                     60:
                     61:   s = str;
                     62:
                     63:   /* Special case zero, as the code below doesn't handle it.  */
                     64:   if (msize == 0)
                     65:     {
                     66:       s[0] = 0;
                     67:       return 1;
                     68:     }
                     69:
                     70:   if ((base & (base - 1)) == 0)
                     71:     {
                     72:       /* The base is a power of 2.  Make conversion from most
                     73:         significant side.  */
                     74:       mp_limb_t n1, n0;
                     75:       register int bits_per_digit = big_base;
                     76:       register int x;
                     77:       register int bit_pos;
                     78:       register int i;
                     79:
                     80:       n1 = mptr[msize - 1];
                     81:       count_leading_zeros (x, n1);
                     82:
                     83:        /* BIT_POS should be R when input ends in least sign. nibble,
                     84:           R + bits_per_digit * n when input ends in n:th least significant
                     85:           nibble. */
                     86:
                     87:       {
                     88:        int bits;
                     89:
                     90:        bits = BITS_PER_MP_LIMB * msize - x;
                     91:        x = bits % bits_per_digit;
                     92:        if (x != 0)
                     93:          bits += bits_per_digit - x;
                     94:        bit_pos = bits - (msize - 1) * BITS_PER_MP_LIMB;
                     95:       }
                     96:
                     97:       /* Fast loop for bit output.  */
                     98:       i = msize - 1;
                     99:       for (;;)
                    100:        {
                    101:          bit_pos -= bits_per_digit;
                    102:          while (bit_pos >= 0)
                    103:            {
                    104:              *s++ = (n1 >> bit_pos) & ((1 << bits_per_digit) - 1);
                    105:              bit_pos -= bits_per_digit;
                    106:            }
                    107:          i--;
                    108:          if (i < 0)
                    109:            break;
                    110:          n0 = (n1 << -bit_pos) & ((1 << bits_per_digit) - 1);
                    111:          n1 = mptr[i];
                    112:          bit_pos += BITS_PER_MP_LIMB;
                    113:          *s++ = n0 | (n1 >> bit_pos);
                    114:        }
                    115:
                    116:       *s = 0;
                    117:
                    118:       return s - str;
                    119:     }
                    120:   else
                    121:     {
                    122:       /* General case.  The base is not a power of 2.  Make conversion
                    123:         from least significant end.  */
                    124:
                    125:       /* If udiv_qrnnd only handles divisors with the most significant bit
                    126:         set, prepare BIG_BASE for being a divisor by shifting it to the
                    127:         left exactly enough to set the most significant bit.  */
                    128: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
                    129:       count_leading_zeros (normalization_steps, big_base);
                    130:       big_base <<= normalization_steps;
                    131: #if UDIV_TIME > 2 * UMUL_TIME
                    132:       /* Get the fixed-point approximation to 1/(BIG_BASE << NORMALIZATION_STEPS).  */
                    133:       big_base_inverted = __mp_bases[base].big_base_inverted;
                    134: #endif
                    135: #endif
                    136:
                    137:       dig_per_u = __mp_bases[base].chars_per_limb;
                    138:       out_len = ((size_t) msize * BITS_PER_MP_LIMB
                    139:                 * __mp_bases[base].chars_per_bit_exactly) + 1;
                    140:       s += out_len;
                    141:
                    142:       while (msize != 0)
                    143:        {
                    144:          int i;
                    145:          mp_limb_t n0, n1;
                    146:
                    147: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
                    148:          /* If we shifted BIG_BASE above, shift the dividend too, to get
                    149:             the right quotient.  We need to do this every loop,
                    150:             since the intermediate quotients are OK, but the quotient from
                    151:             one turn in the loop is going to be the dividend in the
                    152:             next turn, and the dividend needs to be up-shifted.  */
                    153:          if (normalization_steps != 0)
                    154:            {
                    155:              n0 = mpn_lshift (mptr, mptr, msize, normalization_steps);
                    156:
                    157:              /* If the shifting gave a carry out limb, store it and
                    158:                 increase the length.  */
                    159:              if (n0 != 0)
                    160:                {
                    161:                  mptr[msize] = n0;
                    162:                  msize++;
                    163:                }
                    164:            }
                    165: #endif
                    166:
                    167:          /* Divide the number at TP with BIG_BASE to get a quotient and a
                    168:             remainder.  The remainder is our new digit in base BIG_BASE.  */
                    169:          i = msize - 1;
                    170:          n1 = mptr[i];
                    171:
                    172:          if (n1 >= big_base)
                    173:            n1 = 0;
                    174:          else
                    175:            {
                    176:              msize--;
                    177:              i--;
                    178:            }
                    179:
                    180:          for (; i >= 0; i--)
                    181:            {
                    182:              n0 = mptr[i];
                    183: #if UDIV_TIME > 2 * UMUL_TIME
                    184:              udiv_qrnnd_preinv (mptr[i], n1, n1, n0, big_base, big_base_inverted);
                    185: #else
                    186:              udiv_qrnnd (mptr[i], n1, n1, n0, big_base);
                    187: #endif
                    188:            }
                    189:
                    190: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
                    191:          /* If we shifted above (at previous UDIV_NEEDS_NORMALIZATION tests)
                    192:             the remainder will be up-shifted here.  Compensate.  */
                    193:          n1 >>= normalization_steps;
                    194: #endif
                    195:
                    196:          /* Convert N1 from BIG_BASE to a string of digits in BASE
                    197:             using single precision operations.  */
                    198:          for (i = dig_per_u - 1; i >= 0; i--)
                    199:            {
                    200:              *--s = n1 % base;
                    201:              n1 /= base;
                    202:              if (n1 == 0 && msize == 0)
                    203:                break;
                    204:            }
                    205:        }
                    206:
                    207:       while (s != str)
                    208:        *--s = 0;
                    209:       return out_len;
                    210:     }
                    211: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>