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