1 /* mpz_hamdist -- calculate hamming distance. 2 3 Copyright 1994, 1996, 2001, 2002, 2009-2011 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 either: 9 10 * the GNU Lesser General Public License as published by the Free 11 Software Foundation; either version 3 of the License, or (at your 12 option) any later version. 13 14 or 15 16 * the GNU General Public License as published by the Free Software 17 Foundation; either version 2 of the License, or (at your option) any 18 later version. 19 20 or both in parallel, as here. 21 22 The GNU MP Library is distributed in the hope that it will be useful, but 23 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 24 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 25 for more details. 26 27 You should have received copies of the GNU General Public License and the 28 GNU Lesser General Public License along with the GNU MP Library. If not, 29 see https://www.gnu.org/licenses/. */ 30 31 #include "gmp.h" 32 #include "gmp-impl.h" 33 34 35 mp_bitcnt_t 36 mpz_hamdist (mpz_srcptr u, mpz_srcptr v) __GMP_NOTHROW 37 { 38 mp_srcptr up, vp; 39 mp_size_t usize, vsize; 40 mp_bitcnt_t count; 41 42 usize = SIZ(u); 43 vsize = SIZ(v); 44 45 up = PTR(u); 46 vp = PTR(v); 47 48 if (usize >= 0) 49 { 50 if (vsize < 0) 51 return ~ (mp_bitcnt_t) 0; 52 53 /* positive/positive */ 54 55 if (usize < vsize) 56 MPN_SRCPTR_SWAP (up,usize, vp,vsize); 57 58 count = 0; 59 if (vsize != 0) 60 count = mpn_hamdist (up, vp, vsize); 61 62 usize -= vsize; 63 if (usize != 0) 64 count += mpn_popcount (up + vsize, usize); 65 66 return count; 67 } 68 else 69 { 70 mp_limb_t ulimb, vlimb; 71 mp_size_t old_vsize, step; 72 73 if (vsize >= 0) 74 return ~ (mp_bitcnt_t) 0; 75 76 /* negative/negative */ 77 78 usize = -usize; 79 vsize = -vsize; 80 81 /* skip common low zeros */ 82 for (;;) 83 { 84 ASSERT (usize > 0); 85 ASSERT (vsize > 0); 86 87 usize--; 88 vsize--; 89 90 ulimb = *up++; 91 vlimb = *vp++; 92 93 if (ulimb != 0) 94 break; 95 96 if (vlimb != 0) 97 { 98 MPN_SRCPTR_SWAP (up,usize, vp,vsize); 99 ulimb = vlimb; 100 vlimb = 0; 101 break; 102 } 103 } 104 105 /* twos complement first non-zero limbs (ulimb is non-zero, but vlimb 106 might be zero) */ 107 ulimb = -ulimb; 108 vlimb = -vlimb; 109 popc_limb (count, (ulimb ^ vlimb) & GMP_NUMB_MASK); 110 111 if (vlimb == 0) 112 { 113 mp_bitcnt_t twoscount; 114 115 /* first non-zero of v */ 116 old_vsize = vsize; 117 do 118 { 119 ASSERT (vsize > 0); 120 vsize--; 121 vlimb = *vp++; 122 } 123 while (vlimb == 0); 124 125 /* part of u corresponding to skipped v zeros */ 126 step = old_vsize - vsize - 1; 127 count += step * GMP_NUMB_BITS; 128 step = MIN (step, usize); 129 if (step != 0) 130 { 131 count -= mpn_popcount (up, step); 132 usize -= step; 133 up += step; 134 } 135 136 /* First non-zero vlimb as twos complement, xor with ones 137 complement ulimb. Note -v^(~0^u) == (v-1)^u. */ 138 vlimb--; 139 if (usize != 0) 140 { 141 usize--; 142 vlimb ^= *up++; 143 } 144 popc_limb (twoscount, vlimb); 145 count += twoscount; 146 } 147 148 /* Overlapping part of u and v, if any. Ones complement both, so just 149 plain hamdist. */ 150 step = MIN (usize, vsize); 151 if (step != 0) 152 { 153 count += mpn_hamdist (up, vp, step); 154 usize -= step; 155 vsize -= step; 156 up += step; 157 vp += step; 158 } 159 160 /* Remaining high part of u or v, if any, ones complement but xor 161 against all ones in the other, so plain popcount. */ 162 if (usize != 0) 163 { 164 remaining: 165 count += mpn_popcount (up, usize); 166 } 167 else if (vsize != 0) 168 { 169 up = vp; 170 usize = vsize; 171 goto remaining; 172 } 173 return count; 174 } 175 } 176