1 /* mpz_hamdist -- calculate hamming distance. 2 3 Copyright 1994, 1996, 2001, 2002, 2009, 2010, 2011 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 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 25 mp_bitcnt_t 26 mpz_hamdist (mpz_srcptr u, mpz_srcptr v) __GMP_NOTHROW 27 { 28 mp_srcptr up, vp; 29 mp_size_t usize, vsize; 30 mp_bitcnt_t count; 31 32 usize = SIZ(u); 33 vsize = SIZ(v); 34 35 up = PTR(u); 36 vp = PTR(v); 37 38 if (usize >= 0) 39 { 40 if (vsize < 0) 41 return ~ (mp_bitcnt_t) 0; 42 43 /* positive/positive */ 44 45 if (usize < vsize) 46 MPN_SRCPTR_SWAP (up,usize, vp,vsize); 47 48 count = 0; 49 if (vsize != 0) 50 count = mpn_hamdist (up, vp, vsize); 51 52 usize -= vsize; 53 if (usize != 0) 54 count += mpn_popcount (up + vsize, usize); 55 56 return count; 57 } 58 else 59 { 60 mp_limb_t ulimb, vlimb; 61 mp_size_t old_vsize, step; 62 63 if (vsize >= 0) 64 return ~ (mp_bitcnt_t) 0; 65 66 /* negative/negative */ 67 68 usize = -usize; 69 vsize = -vsize; 70 71 /* skip common low zeros */ 72 for (;;) 73 { 74 ASSERT (usize > 0); 75 ASSERT (vsize > 0); 76 77 usize--; 78 vsize--; 79 80 ulimb = *up++; 81 vlimb = *vp++; 82 83 if (ulimb != 0) 84 break; 85 86 if (vlimb != 0) 87 { 88 MPN_SRCPTR_SWAP (up,usize, vp,vsize); 89 ulimb = vlimb; 90 vlimb = 0; 91 break; 92 } 93 } 94 95 /* twos complement first non-zero limbs (ulimb is non-zero, but vlimb 96 might be zero) */ 97 ulimb = -ulimb; 98 vlimb = -vlimb; 99 popc_limb (count, (ulimb ^ vlimb) & GMP_NUMB_MASK); 100 101 if (vlimb == 0) 102 { 103 mp_bitcnt_t twoscount; 104 105 /* first non-zero of v */ 106 old_vsize = vsize; 107 do 108 { 109 ASSERT (vsize > 0); 110 vsize--; 111 vlimb = *vp++; 112 } 113 while (vlimb == 0); 114 115 /* part of u corresponding to skipped v zeros */ 116 step = old_vsize - vsize - 1; 117 count += step * GMP_NUMB_BITS; 118 step = MIN (step, usize); 119 if (step != 0) 120 { 121 count -= mpn_popcount (up, step); 122 usize -= step; 123 up += step; 124 } 125 126 /* First non-zero vlimb as twos complement, xor with ones 127 complement ulimb. Note -v^(~0^u) == (v-1)^u. */ 128 vlimb--; 129 if (usize != 0) 130 { 131 usize--; 132 vlimb ^= *up++; 133 } 134 popc_limb (twoscount, vlimb); 135 count += twoscount; 136 } 137 138 /* Overlapping part of u and v, if any. Ones complement both, so just 139 plain hamdist. */ 140 step = MIN (usize, vsize); 141 if (step != 0) 142 { 143 count += mpn_hamdist (up, vp, step); 144 usize -= step; 145 vsize -= step; 146 up += step; 147 vp += step; 148 } 149 150 /* Remaining high part of u or v, if any, ones complement but xor 151 against all ones in the other, so plain popcount. */ 152 if (usize != 0) 153 { 154 remaining: 155 count += mpn_popcount (up, usize); 156 } 157 else if (vsize != 0) 158 { 159 up = vp; 160 usize = vsize; 161 goto remaining; 162 } 163 return count; 164 } 165 } 166