Home | History | Annotate | Line # | Download | only in generic
popham.c revision 1.1.1.2 
      1 /* mpn_popcount, mpn_hamdist -- mpn bit population count/hamming distance.
      2 
      3 Copyright 1994, 1996, 2000, 2001, 2002, 2005, 2011, 2012 Free Software
      4 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 Lesser General Public License as published by
     10 the Free Software Foundation; either version 3 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 Lesser General Public
     16 License for more details.
     17 
     18 You should have received a copy of the GNU Lesser General Public License
     19 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
     20 
     21 #include "gmp.h"
     22 #include "gmp-impl.h"
     23 
     24 #if OPERATION_popcount
     25 #define FNAME mpn_popcount
     26 #define POPHAM(u,v) u
     27 #endif
     28 
     29 #if OPERATION_hamdist
     30 #define FNAME mpn_hamdist
     31 #define POPHAM(u,v) u ^ v
     32 #endif
     33 
     34 mp_bitcnt_t
     35 FNAME (mp_srcptr up,
     36 #if OPERATION_hamdist
     37        mp_srcptr vp,
     38 #endif
     39        mp_size_t n) __GMP_NOTHROW
     40 {
     41   mp_bitcnt_t result = 0;
     42   mp_limb_t p0, p1, p2, p3, x, p01, p23;
     43   mp_size_t i;
     44 
     45   ASSERT (n >= 1);		/* Actually, this code handles any n, but some
     46 				   assembly implementations do not.  */
     47 
     48   for (i = n >> 2; i != 0; i--)
     49     {
     50       p0 = POPHAM (up[0], vp[0]);
     51       p0 -= (p0 >> 1) & MP_LIMB_T_MAX/3;				/* 2 0-2 */
     52       p0 = ((p0 >> 2) & MP_LIMB_T_MAX/5) + (p0 & MP_LIMB_T_MAX/5);	/* 4 0-4 */
     53 
     54       p1 = POPHAM (up[1], vp[1]);
     55       p1 -= (p1 >> 1) & MP_LIMB_T_MAX/3;				/* 2 0-2 */
     56       p1 = ((p1 >> 2) & MP_LIMB_T_MAX/5) + (p1 & MP_LIMB_T_MAX/5);	/* 4 0-4 */
     57 
     58       p01 = p0 + p1;							/* 8 0-8 */
     59       p01 = ((p01 >> 4) & MP_LIMB_T_MAX/17) + (p01 & MP_LIMB_T_MAX/17);	/* 8 0-16 */
     60 
     61       p2 = POPHAM (up[2], vp[2]);
     62       p2 -= (p2 >> 1) & MP_LIMB_T_MAX/3;				/* 2 0-2 */
     63       p2 = ((p2 >> 2) & MP_LIMB_T_MAX/5) + (p2 & MP_LIMB_T_MAX/5);	/* 4 0-4 */
     64 
     65       p3 = POPHAM (up[3], vp[3]);
     66       p3 -= (p3 >> 1) & MP_LIMB_T_MAX/3;				/* 2 0-2 */
     67       p3 = ((p3 >> 2) & MP_LIMB_T_MAX/5) + (p3 & MP_LIMB_T_MAX/5);	/* 4 0-4 */
     68 
     69       p23 = p2 + p3;							/* 8 0-8 */
     70       p23 = ((p23 >> 4) & MP_LIMB_T_MAX/17) + (p23 & MP_LIMB_T_MAX/17);	/* 8 0-16 */
     71 
     72       x = p01 + p23;							/* 8 0-32 */
     73       x = (x >> 8) + x;							/* 8 0-64 */
     74       x = (x >> 16) + x;						/* 8 0-128 */
     75 #if GMP_LIMB_BITS > 32
     76       x = ((x >> 32) & 0xff) + (x & 0xff);				/* 8 0-256 */
     77       result += x;
     78 #else
     79       result += x & 0xff;
     80 #endif
     81       up += 4;
     82 #if OPERATION_hamdist
     83       vp += 4;
     84 #endif
     85     }
     86 
     87   n &= 3;
     88   if (n != 0)
     89     {
     90       x = 0;
     91       do
     92 	{
     93 	  p0 = POPHAM (up[0], vp[0]);
     94 	  p0 -= (p0 >> 1) & MP_LIMB_T_MAX/3;				/* 2 0-2 */
     95 	  p0 = ((p0 >> 2) & MP_LIMB_T_MAX/5) + (p0 & MP_LIMB_T_MAX/5);	/* 4 0-4 */
     96 	  p0 = ((p0 >> 4) + p0) & MP_LIMB_T_MAX/17;			/* 8 0-8 */
     97 
     98 	  x += p0;
     99 	  up += 1;
    100 #if OPERATION_hamdist
    101 	  vp += 1;
    102 #endif
    103 	}
    104       while (--n);
    105 
    106       x = (x >> 8) + x;
    107       x = (x >> 16) + x;
    108 #if GMP_LIMB_BITS > 32
    109       x = (x >> 32) + x;
    110 #endif
    111       result += x & 0xff;
    112     }
    113 
    114   return result;
    115 }
    116