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