mpn/generic/popham.c

   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.h"
  33 #include "gmp-impl.h"
  34
  35 #if OPERATION_popcount
  36 #define FNAME mpn_popcount
  37 #define POPHAM(u,v) u
  38 #endif
  39
  40 #if OPERATION_hamdist
  41 #define FNAME mpn_hamdist
  42 #define POPHAM(u,v) u ^ v
  43 #endif
  44
  45 mp_bitcnt_t
  46 FNAME (mp_srcptr up,
  47 #if OPERATION_hamdist
  48        mp_srcptr vp,
  49 #endif
  50        mp_size_t n) __GMP_NOTHROW
  51 {
  52   mp_bitcnt_t result = 0;
  53   mp_limb_t p0, p1, p2, p3, x, p01, p23;
  54   mp_size_t i;
  55
  56   ASSERT (n >= 1);              /* Actually, this code handles any n, but some
  57                                    assembly implementations do not.  */
  58
  59   for (i = n >> 2; i != 0; i--)
  60     {
  61       p0 = POPHAM (up[0], vp[0]);
  62       p0 -= (p0 >> 1) & MP_LIMB_T_MAX/3;                                /* 2 0-2 */
  63       p0 = ((p0 >> 2) & MP_LIMB_T_MAX/5) + (p0 & MP_LIMB_T_MAX/5);      /* 4 0-4 */
  64
  65       p1 = POPHAM (up[1], vp[1]);
  66       p1 -= (p1 >> 1) & MP_LIMB_T_MAX/3;                                /* 2 0-2 */
  67       p1 = ((p1 >> 2) & MP_LIMB_T_MAX/5) + (p1 & MP_LIMB_T_MAX/5);      /* 4 0-4 */
  68
  69       p01 = p0 + p1;                                                    /* 8 0-8 */
  70       p01 = ((p01 >> 4) & MP_LIMB_T_MAX/17) + (p01 & MP_LIMB_T_MAX/17); /* 8 0-16 */
  71
  72       p2 = POPHAM (up[2], vp[2]);
  73       p2 -= (p2 >> 1) & MP_LIMB_T_MAX/3;                                /* 2 0-2 */
  74       p2 = ((p2 >> 2) & MP_LIMB_T_MAX/5) + (p2 & MP_LIMB_T_MAX/5);      /* 4 0-4 */
  75
  76       p3 = POPHAM (up[3], vp[3]);
  77       p3 -= (p3 >> 1) & MP_LIMB_T_MAX/3;                                /* 2 0-2 */
  78       p3 = ((p3 >> 2) & MP_LIMB_T_MAX/5) + (p3 & MP_LIMB_T_MAX/5);      /* 4 0-4 */
  79
  80       p23 = p2 + p3;                                                    /* 8 0-8 */
  81       p23 = ((p23 >> 4) & MP_LIMB_T_MAX/17) + (p23 & MP_LIMB_T_MAX/17); /* 8 0-16 */
  82
  83       x = p01 + p23;                                                    /* 8 0-32 */
  84       x = (x >> 8) + x;                                                 /* 8 0-64 */
  85       x = (x >> 16) + x;                                                /* 8 0-128 */
  86 #if GMP_LIMB_BITS > 32
  87       x = ((x >> 32) & 0xff) + (x & 0xff);                              /* 8 0-256 */
  88       result += x;
  89 #else
  90       result += x & 0xff;
  91 #endif
  92       up += 4;
  93 #if OPERATION_hamdist
  94       vp += 4;
  95 #endif
  96     }
  97
  98   n &= 3;
  99   if (n != 0)
 100     {
 101       x = 0;
 102       do
 103         {
 104           p0 = POPHAM (up[0], vp[0]);
 105           p0 -= (p0 >> 1) & MP_LIMB_T_MAX/3;                            /* 2 0-2 */
 106           p0 = ((p0 >> 2) & MP_LIMB_T_MAX/5) + (p0 & MP_LIMB_T_MAX/5);  /* 4 0-4 */
 107           p0 = ((p0 >> 4) + p0) & MP_LIMB_T_MAX/17;                     /* 8 0-8 */
 108
 109           x += p0;
 110           up += 1;
 111 #if OPERATION_hamdist
 112           vp += 1;
 113 #endif
 114         }
 115       while (--n);
 116
 117       x = (x >> 8) + x;
 118       x = (x >> 16) + x;
 119 #if GMP_LIMB_BITS > 32
 120       x = (x >> 32) + x;
 121 #endif
 122       result += x & 0xff;
 123     }
 124
 125   return result;
 126 }