[BACK]Return to and.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / gmp-2.0.2 / mpz

Annotation of OpenXM/src/kan96xx/gmp-2.0.2/mpz/and.c, Revision 1.1.1.1

1.1       maekawa     1: /* mpz_and -- Logical and.
                      2:
                      3: Copyright (C) 1991, 1993, 1994, 1996 Free Software Foundation, Inc.
                      4:
                      5: This file is part of the GNU MP Library.
                      6:
                      7: The GNU MP Library is free software; you can redistribute it and/or modify
                      8: it under the terms of the GNU Library General Public License as published by
                      9: the Free Software Foundation; either version 2 of the License, or (at your
                     10: option) any later version.
                     11:
                     12: The GNU MP Library is distributed in the hope that it will be useful, but
                     13: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
                     14: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
                     15: License for more details.
                     16:
                     17: You should have received a copy of the GNU Library General Public License
                     18: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     19: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     20: MA 02111-1307, USA. */
                     21:
                     22: #include "gmp.h"
                     23: #include "gmp-impl.h"
                     24:
                     25: void
                     26: #if __STDC__
                     27: mpz_and (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2)
                     28: #else
                     29: mpz_and (res, op1, op2)
                     30:      mpz_ptr res;
                     31:      mpz_srcptr op1;
                     32:      mpz_srcptr op2;
                     33: #endif
                     34: {
                     35:   mp_srcptr op1_ptr, op2_ptr;
                     36:   mp_size_t op1_size, op2_size;
                     37:   mp_ptr res_ptr;
                     38:   mp_size_t res_size;
                     39:   mp_size_t i;
                     40:   TMP_DECL (marker);
                     41:
                     42:   TMP_MARK (marker);
                     43:   op1_size = op1->_mp_size;
                     44:   op2_size = op2->_mp_size;
                     45:
                     46:   op1_ptr = op1->_mp_d;
                     47:   op2_ptr = op2->_mp_d;
                     48:   res_ptr = res->_mp_d;
                     49:
                     50:   if (op1_size >= 0)
                     51:     {
                     52:       if (op2_size >= 0)
                     53:        {
                     54:          res_size = MIN (op1_size, op2_size);
                     55:          /* First loop finds the size of the result.  */
                     56:          for (i = res_size - 1; i >= 0; i--)
                     57:            if ((op1_ptr[i] & op2_ptr[i]) != 0)
                     58:              break;
                     59:          res_size = i + 1;
                     60:
                     61:          /* Handle allocation, now then we know exactly how much space is
                     62:             needed for the result.  */
                     63:          if (res->_mp_alloc < res_size)
                     64:            {
                     65:              _mpz_realloc (res, res_size);
                     66:              op1_ptr = op1->_mp_d;
                     67:              op2_ptr = op2->_mp_d;
                     68:              res_ptr = res->_mp_d;
                     69:            }
                     70:
                     71:          /* Second loop computes the real result.  */
                     72:          for (i = res_size - 1; i >= 0; i--)
                     73:            res_ptr[i] = op1_ptr[i] & op2_ptr[i];
                     74:
                     75:          res->_mp_size = res_size;
                     76:          return;
                     77:        }
                     78:       else /* op2_size < 0 */
                     79:        {
                     80:          /* Fall through to the code at the end of the function.  */
                     81:        }
                     82:     }
                     83:   else
                     84:     {
                     85:       if (op2_size < 0)
                     86:        {
                     87:          mp_ptr opx;
                     88:          mp_limb_t cy;
                     89:          mp_size_t res_alloc;
                     90:
                     91:          /* Both operands are negative, so will be the result.
                     92:             -((-OP1) & (-OP2)) = -(~(OP1 - 1) & ~(OP2 - 1)) =
                     93:             = ~(~(OP1 - 1) & ~(OP2 - 1)) + 1 =
                     94:             = ((OP1 - 1) | (OP2 - 1)) + 1      */
                     95:
                     96:          /* It might seem as we could end up with an (invalid) result with
                     97:             a leading zero-limb here when one of the operands is of the
                     98:             type 1,,0,,..,,.0.  But some analysis shows that we surely
                     99:             would get carry into the zero-limb in this situation...  */
                    100:
                    101:          op1_size = -op1_size;
                    102:          op2_size = -op2_size;
                    103:
                    104:          res_alloc = 1 + MAX (op1_size, op2_size);
                    105:
                    106:          opx = (mp_ptr) TMP_ALLOC (op1_size * BYTES_PER_MP_LIMB);
                    107:          mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1);
                    108:          op1_ptr = opx;
                    109:
                    110:          opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
                    111:          mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
                    112:          op2_ptr = opx;
                    113:
                    114:          if (res->_mp_alloc < res_alloc)
                    115:            {
                    116:              _mpz_realloc (res, res_alloc);
                    117:              res_ptr = res->_mp_d;
                    118:              /* Don't re-read OP1_PTR and OP2_PTR.  They point to
                    119:                 temporary space--never to the space RES->_mp_D used
                    120:                 to point to before reallocation.  */
                    121:            }
                    122:
                    123:          if (op1_size >= op2_size)
                    124:            {
                    125:              MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
                    126:                        op1_size - op2_size);
                    127:              for (i = op2_size - 1; i >= 0; i--)
                    128:                res_ptr[i] = op1_ptr[i] | op2_ptr[i];
                    129:              res_size = op1_size;
                    130:            }
                    131:          else
                    132:            {
                    133:              MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size,
                    134:                        op2_size - op1_size);
                    135:              for (i = op1_size - 1; i >= 0; i--)
                    136:                res_ptr[i] = op1_ptr[i] | op2_ptr[i];
                    137:              res_size = op2_size;
                    138:            }
                    139:
                    140:          cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1);
                    141:          if (cy)
                    142:            {
                    143:              res_ptr[res_size] = cy;
                    144:              res_size++;
                    145:            }
                    146:
                    147:          res->_mp_size = -res_size;
                    148:          TMP_FREE (marker);
                    149:          return;
                    150:        }
                    151:       else
                    152:        {
                    153:          /* We should compute -OP1 & OP2.  Swap OP1 and OP2 and fall
                    154:             through to the code that handles OP1 & -OP2.  */
                    155:          {mpz_srcptr t = op1; op1 = op2; op2 = t;}
                    156:          {mp_srcptr t = op1_ptr; op1_ptr = op2_ptr; op2_ptr = t;}
                    157:          {mp_size_t t = op1_size; op1_size = op2_size; op2_size = t;}
                    158:        }
                    159:
                    160:     }
                    161:
                    162:   {
                    163: #if ANDNEW
                    164:     mp_size_t op2_lim;
                    165:     mp_size_t count;
                    166:
                    167:     /* OP2 must be negated as with infinite precision.
                    168:
                    169:        Scan from the low end for a non-zero limb.  The first non-zero
                    170:        limb is simply negated (two's complement).  Any subsequent
                    171:        limbs are one's complemented.  Of course, we don't need to
                    172:        handle more limbs than there are limbs in the other, positive
                    173:        operand as the result for those limbs is going to become zero
                    174:        anyway.  */
                    175:
                    176:     /* Scan for the least significant. non-zero OP2 limb, and zero the
                    177:        result meanwhile for those limb positions.  (We will surely
                    178:        find a non-zero limb, so we can write the loop with one
                    179:        termination condition only.)  */
                    180:     for (i = 0; op2_ptr[i] == 0; i++)
                    181:       res_ptr[i] = 0;
                    182:     op2_lim = i;
                    183:
                    184:     op2_size = -op2_size;
                    185:
                    186:     if (op1_size <= op2_size)
                    187:       {
                    188:        /* The ones-extended OP2 is >= than the zero-extended OP1.
                    189:           RES_SIZE <= OP1_SIZE.  Find the exact size.  */
                    190:        for (i = op1_size - 1; i > op2_lim; i--)
                    191:          if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
                    192:            break;
                    193:        res_size = i + 1;
                    194:        for (i = res_size - 1; i > op2_lim; i--)
                    195:          res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
                    196:        res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
                    197:        /* Yes, this *can* happen!  */
                    198:        MPN_NORMALIZE (res_ptr, res_size);
                    199:       }
                    200:     else
                    201:       {
                    202:        /* The ones-extended OP2 is < than the zero-extended OP1.
                    203:           RES_SIZE == OP1_SIZE, since OP1 is normalized.  */
                    204:        res_size = op1_size;
                    205:        MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size);
                    206:        for (i = op2_size - 1; i > op2_lim; i--)
                    207:          res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
                    208:        res_ptr[op2_lim] = op1_ptr[op2_lim] & -op2_ptr[op2_lim];
                    209:       }
                    210:
                    211:     res->_mp_size = res_size;
                    212: #else
                    213:
                    214:     /* OP1 is positive and zero-extended,
                    215:        OP2 is negative and ones-extended.
                    216:        The result will be positive.
                    217:        OP1 & -OP2 = OP1 & ~(OP2 - 1).  */
                    218:
                    219:     mp_ptr opx;
                    220:
                    221:     op2_size = -op2_size;
                    222:     opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB);
                    223:     mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1);
                    224:     op2_ptr = opx;
                    225:
                    226:     if (op1_size > op2_size)
                    227:       {
                    228:        /* The result has the same size as OP1, since OP1 is normalized
                    229:           and longer than the ones-extended OP2.  */
                    230:        res_size = op1_size;
                    231:
                    232:        /* Handle allocation, now then we know exactly how much space is
                    233:           needed for the result.  */
                    234:        if (res->_mp_alloc < res_size)
                    235:          {
                    236:            _mpz_realloc (res, res_size);
                    237:            res_ptr = res->_mp_d;
                    238:            op1_ptr = op1->_mp_d;
                    239:            /* Don't re-read OP2_PTR.  It points to temporary space--never
                    240:               to the space RES->_mp_D used to point to before reallocation.  */
                    241:          }
                    242:
                    243:        MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size,
                    244:                  res_size - op2_size);
                    245:        for (i = op2_size - 1; i >= 0; i--)
                    246:          res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
                    247:
                    248:        res->_mp_size = res_size;
                    249:       }
                    250:     else
                    251:       {
                    252:        /* Find out the exact result size.  Ignore the high limbs of OP2,
                    253:           OP1 is zero-extended and would make the result zero.  */
                    254:        for (i = op1_size - 1; i >= 0; i--)
                    255:          if ((op1_ptr[i] & ~op2_ptr[i]) != 0)
                    256:            break;
                    257:        res_size = i + 1;
                    258:
                    259:        /* Handle allocation, now then we know exactly how much space is
                    260:           needed for the result.  */
                    261:        if (res->_mp_alloc < res_size)
                    262:          {
                    263:            _mpz_realloc (res, res_size);
                    264:            res_ptr = res->_mp_d;
                    265:            op1_ptr = op1->_mp_d;
                    266:            /* Don't re-read OP2_PTR.  It points to temporary space--never
                    267:               to the space RES->_mp_D used to point to before reallocation.  */
                    268:          }
                    269:
                    270:        for (i = res_size - 1; i >= 0; i--)
                    271:          res_ptr[i] = op1_ptr[i] & ~op2_ptr[i];
                    272:
                    273:        res->_mp_size = res_size;
                    274:       }
                    275: #endif
                    276:   }
                    277:   TMP_FREE (marker);
                    278: }

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