#
source:
trunk/third/gmp/mpz/xor.c
@
18191

Revision 18191, 5.3 KB checked in by ghudson, 22 years ago (diff) |
---|

Line | |
---|---|

1 | /* mpz_xor -- Logical xor. |

2 | |

3 | Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001 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 2.1 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; see the file COPYING.LIB. If not, write to |

20 | the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |

21 | MA 02111-1307, USA. */ |

22 | |

23 | #include "gmp.h" |

24 | #include "gmp-impl.h" |

25 | |

26 | void |

27 | mpz_xor (mpz_ptr res, mpz_srcptr op1, mpz_srcptr op2) |

28 | { |

29 | mp_srcptr op1_ptr, op2_ptr; |

30 | mp_size_t op1_size, op2_size; |

31 | mp_ptr res_ptr; |

32 | mp_size_t res_size, res_alloc; |

33 | mp_size_t i; |

34 | TMP_DECL (marker); |

35 | |

36 | TMP_MARK (marker); |

37 | op1_size = op1->_mp_size; |

38 | op2_size = op2->_mp_size; |

39 | |

40 | op1_ptr = op1->_mp_d; |

41 | op2_ptr = op2->_mp_d; |

42 | res_ptr = res->_mp_d; |

43 | |

44 | if (op1_size >= 0) |

45 | { |

46 | if (op2_size >= 0) |

47 | { |

48 | if (op1_size >= op2_size) |

49 | { |

50 | if (res->_mp_alloc < op1_size) |

51 | { |

52 | _mpz_realloc (res, op1_size); |

53 | op1_ptr = op1->_mp_d; |

54 | op2_ptr = op2->_mp_d; |

55 | res_ptr = res->_mp_d; |

56 | } |

57 | |

58 | if (res_ptr != op1_ptr) |

59 | MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, |

60 | op1_size - op2_size); |

61 | for (i = op2_size - 1; i >= 0; i--) |

62 | res_ptr[i] = op1_ptr[i] ^ op2_ptr[i]; |

63 | res_size = op1_size; |

64 | } |

65 | else |

66 | { |

67 | if (res->_mp_alloc < op2_size) |

68 | { |

69 | _mpz_realloc (res, op2_size); |

70 | op1_ptr = op1->_mp_d; |

71 | op2_ptr = op2->_mp_d; |

72 | res_ptr = res->_mp_d; |

73 | } |

74 | |

75 | if (res_ptr != op2_ptr) |

76 | MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, |

77 | op2_size - op1_size); |

78 | for (i = op1_size - 1; i >= 0; i--) |

79 | res_ptr[i] = op1_ptr[i] ^ op2_ptr[i]; |

80 | res_size = op2_size; |

81 | } |

82 | |

83 | MPN_NORMALIZE (res_ptr, res_size); |

84 | res->_mp_size = res_size; |

85 | return; |

86 | } |

87 | else /* op2_size < 0 */ |

88 | { |

89 | /* Fall through to the code at the end of the function. */ |

90 | } |

91 | } |

92 | else |

93 | { |

94 | if (op2_size < 0) |

95 | { |

96 | mp_ptr opx; |

97 | |

98 | /* Both operands are negative, the result will be positive. |

99 | (-OP1) ^ (-OP2) = |

100 | = ~(OP1 - 1) ^ ~(OP2 - 1) = |

101 | = (OP1 - 1) ^ (OP2 - 1) */ |

102 | |

103 | op1_size = -op1_size; |

104 | op2_size = -op2_size; |

105 | |

106 | /* Possible optimization: Decrease mpn_sub precision, |

107 | as we won't use the entire res of both. */ |

108 | opx = (mp_ptr) TMP_ALLOC (op1_size * BYTES_PER_MP_LIMB); |

109 | mpn_sub_1 (opx, op1_ptr, op1_size, (mp_limb_t) 1); |

110 | op1_ptr = opx; |

111 | |

112 | opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB); |

113 | mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1); |

114 | op2_ptr = opx; |

115 | |

116 | res_alloc = MAX (op1_size, op2_size); |

117 | if (res->_mp_alloc < res_alloc) |

118 | { |

119 | _mpz_realloc (res, res_alloc); |

120 | res_ptr = res->_mp_d; |

121 | /* Don't re-read OP1_PTR and OP2_PTR. They point to |

122 | temporary space--never to the space RES->_mp_d used |

123 | to point to before reallocation. */ |

124 | } |

125 | |

126 | if (op1_size > op2_size) |

127 | { |

128 | MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, |

129 | op1_size - op2_size); |

130 | for (i = op2_size - 1; i >= 0; i--) |

131 | res_ptr[i] = op1_ptr[i] ^ op2_ptr[i]; |

132 | res_size = op1_size; |

133 | } |

134 | else |

135 | { |

136 | MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, |

137 | op2_size - op1_size); |

138 | for (i = op1_size - 1; i >= 0; i--) |

139 | res_ptr[i] = op1_ptr[i] ^ op2_ptr[i]; |

140 | res_size = op2_size; |

141 | } |

142 | |

143 | MPN_NORMALIZE (res_ptr, res_size); |

144 | res->_mp_size = res_size; |

145 | TMP_FREE (marker); |

146 | return; |

147 | } |

148 | else |

149 | { |

150 | /* We should compute -OP1 ^ OP2. Swap OP1 and OP2 and fall |

151 | through to the code that handles OP1 ^ -OP2. */ |

152 | MPZ_SRCPTR_SWAP (op1, op2); |

153 | MPN_SRCPTR_SWAP (op1_ptr,op1_size, op2_ptr,op2_size); |

154 | } |

155 | } |

156 | |

157 | { |

158 | mp_ptr opx; |

159 | mp_limb_t cy; |

160 | |

161 | /* Operand 2 negative, so will be the result. |

162 | -(OP1 ^ (-OP2)) = -(OP1 ^ ~(OP2 - 1)) = |

163 | = ~(OP1 ^ ~(OP2 - 1)) + 1 = |

164 | = (OP1 ^ (OP2 - 1)) + 1 */ |

165 | |

166 | op2_size = -op2_size; |

167 | |

168 | opx = (mp_ptr) TMP_ALLOC (op2_size * BYTES_PER_MP_LIMB); |

169 | mpn_sub_1 (opx, op2_ptr, op2_size, (mp_limb_t) 1); |

170 | op2_ptr = opx; |

171 | |

172 | res_alloc = MAX (op1_size, op2_size) + 1; |

173 | if (res->_mp_alloc < res_alloc) |

174 | { |

175 | _mpz_realloc (res, res_alloc); |

176 | op1_ptr = op1->_mp_d; |

177 | res_ptr = res->_mp_d; |

178 | /* Don't re-read OP2_PTR. It points to temporary space--never |

179 | to the space RES->_mp_d used to point to before reallocation. */ |

180 | } |

181 | |

182 | if (op1_size > op2_size) |

183 | { |

184 | MPN_COPY (res_ptr + op2_size, op1_ptr + op2_size, op1_size - op2_size); |

185 | for (i = op2_size - 1; i >= 0; i--) |

186 | res_ptr[i] = op1_ptr[i] ^ op2_ptr[i]; |

187 | res_size = op1_size; |

188 | } |

189 | else |

190 | { |

191 | MPN_COPY (res_ptr + op1_size, op2_ptr + op1_size, op2_size - op1_size); |

192 | for (i = op1_size - 1; i >= 0; i--) |

193 | res_ptr[i] = op1_ptr[i] ^ op2_ptr[i]; |

194 | res_size = op2_size; |

195 | } |

196 | |

197 | cy = mpn_add_1 (res_ptr, res_ptr, res_size, (mp_limb_t) 1); |

198 | if (cy) |

199 | { |

200 | res_ptr[res_size] = cy; |

201 | res_size++; |

202 | } |

203 | |

204 | MPN_NORMALIZE (res_ptr, res_size); |

205 | res->_mp_size = -res_size; |

206 | TMP_FREE (marker); |

207 | } |

208 | } |

**Note:**See TracBrowser for help on using the repository browser.