1 | /* Copyright (C) 1991-2022 Free Software Foundation, Inc. |
---|---|

2 | This file is part of the GNU C Library. |

3 | Contributed by Torbjorn Granlund (tege@sics.se). |

4 | |

5 | The GNU C Library is free software; you can redistribute it and/or |

6 | modify it under the terms of the GNU Lesser General Public |

7 | License as published by the Free Software Foundation; either |

8 | version 2.1 of the License, or (at your option) any later version. |

9 | |

10 | The GNU C Library is distributed in the hope that it will be useful, |

11 | but WITHOUT ANY WARRANTY; without even the implied warranty of |

12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |

13 | Lesser General Public License for more details. |

14 | |

15 | You should have received a copy of the GNU Lesser General Public |

16 | License along with the GNU C Library; if not, see |

17 | <https://www.gnu.org/licenses/>. */ |

18 | |

19 | #ifdef HAVE_CONFIG_H |

20 | # include "config.h" |

21 | #endif |

22 | |

23 | #if defined HAVE_STRING_H || defined _LIBC |

24 | # include <string.h> |

25 | #endif |

26 | |

27 | #undef memcmp |

28 | |

29 | #ifndef MEMCMP |

30 | # define MEMCMP memcmp |

31 | #endif |

32 | |

33 | #ifdef _LIBC |

34 | |

35 | # include <memcopy.h> |

36 | # include <endian.h> |

37 | |

38 | # if __BYTE_ORDER == __BIG_ENDIAN |

39 | # define WORDS_BIGENDIAN |

40 | # endif |

41 | |

42 | #else /* Not in the GNU C library. */ |

43 | |

44 | # include <sys/types.h> |

45 | |

46 | /* Type to use for aligned memory operations. |

47 | This should normally be the biggest type supported by a single load |

48 | and store. Must be an unsigned type. */ |

49 | # define op_t unsigned long int |

50 | # define OPSIZ (sizeof (op_t)) |

51 | |

52 | /* Threshold value for when to enter the unrolled loops. */ |

53 | # define OP_T_THRES 16 |

54 | |

55 | /* Type to use for unaligned operations. */ |

56 | typedef unsigned char byte; |

57 | |

58 | # ifndef WORDS_BIGENDIAN |

59 | # define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2))) |

60 | # else |

61 | # define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2))) |

62 | # endif |

63 | |

64 | #endif /* In the GNU C library. */ |

65 | |

66 | #ifdef WORDS_BIGENDIAN |

67 | # define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1) |

68 | #else |

69 | # define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b)) |

70 | #endif |

71 | |

72 | /* BE VERY CAREFUL IF YOU CHANGE THIS CODE! */ |

73 | |

74 | /* The strategy of this memcmp is: |

75 | |

76 | 1. Compare bytes until one of the block pointers is aligned. |

77 | |

78 | 2. Compare using memcmp_common_alignment or |

79 | memcmp_not_common_alignment, regarding the alignment of the other |

80 | block after the initial byte operations. The maximum number of |

81 | full words (of type op_t) are compared in this way. |

82 | |

83 | 3. Compare the few remaining bytes. */ |

84 | |

85 | #ifndef WORDS_BIGENDIAN |

86 | /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine. |

87 | A and B are known to be different. |

88 | This is needed only on little-endian machines. */ |

89 | |

90 | static int memcmp_bytes (op_t, op_t) __THROW; |

91 | |

92 | static int |

93 | memcmp_bytes (op_t a, op_t b) |

94 | { |

95 | long int srcp1 = (long int) &a; |

96 | long int srcp2 = (long int) &b; |

97 | op_t a0, b0; |

98 | |

99 | do |

100 | { |

101 | a0 = ((byte *) srcp1)[0]; |

102 | b0 = ((byte *) srcp2)[0]; |

103 | srcp1 += 1; |

104 | srcp2 += 1; |

105 | } |

106 | while (a0 == b0); |

107 | return a0 - b0; |

108 | } |

109 | #endif |

110 | |

111 | static int memcmp_common_alignment (long, long, size_t) __THROW; |

112 | |

113 | /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t' |

114 | objects (not LEN bytes!). Both SRCP1 and SRCP2 should be aligned for |

115 | memory operations on `op_t's. */ |

116 | static int |

117 | memcmp_common_alignment (long int srcp1, long int srcp2, size_t len) |

118 | { |

119 | op_t a0, a1; |

120 | op_t b0, b1; |

121 | |

122 | switch (len % 4) |

123 | { |

124 | default: /* Avoid warning about uninitialized local variables. */ |

125 | case 2: |

126 | a0 = ((op_t *) srcp1)[0]; |

127 | b0 = ((op_t *) srcp2)[0]; |

128 | srcp1 -= 2 * OPSIZ; |

129 | srcp2 -= 2 * OPSIZ; |

130 | len += 2; |

131 | goto do1; |

132 | case 3: |

133 | a1 = ((op_t *) srcp1)[0]; |

134 | b1 = ((op_t *) srcp2)[0]; |

135 | srcp1 -= OPSIZ; |

136 | srcp2 -= OPSIZ; |

137 | len += 1; |

138 | goto do2; |

139 | case 0: |

140 | if (OP_T_THRES <= 3 * OPSIZ && len == 0) |

141 | return 0; |

142 | a0 = ((op_t *) srcp1)[0]; |

143 | b0 = ((op_t *) srcp2)[0]; |

144 | goto do3; |

145 | case 1: |

146 | a1 = ((op_t *) srcp1)[0]; |

147 | b1 = ((op_t *) srcp2)[0]; |

148 | srcp1 += OPSIZ; |

149 | srcp2 += OPSIZ; |

150 | len -= 1; |

151 | if (OP_T_THRES <= 3 * OPSIZ && len == 0) |

152 | goto do0; |

153 | /* Fall through. */ |

154 | } |

155 | |

156 | do |

157 | { |

158 | a0 = ((op_t *) srcp1)[0]; |

159 | b0 = ((op_t *) srcp2)[0]; |

160 | if (a1 != b1) |

161 | return CMP_LT_OR_GT (a1, b1); |

162 | |

163 | do3: |

164 | a1 = ((op_t *) srcp1)[1]; |

165 | b1 = ((op_t *) srcp2)[1]; |

166 | if (a0 != b0) |

167 | return CMP_LT_OR_GT (a0, b0); |

168 | |

169 | do2: |

170 | a0 = ((op_t *) srcp1)[2]; |

171 | b0 = ((op_t *) srcp2)[2]; |

172 | if (a1 != b1) |

173 | return CMP_LT_OR_GT (a1, b1); |

174 | |

175 | do1: |

176 | a1 = ((op_t *) srcp1)[3]; |

177 | b1 = ((op_t *) srcp2)[3]; |

178 | if (a0 != b0) |

179 | return CMP_LT_OR_GT (a0, b0); |

180 | |

181 | srcp1 += 4 * OPSIZ; |

182 | srcp2 += 4 * OPSIZ; |

183 | len -= 4; |

184 | } |

185 | while (len != 0); |

186 | |

187 | /* This is the right position for do0. Please don't move |

188 | it into the loop. */ |

189 | do0: |

190 | if (a1 != b1) |

191 | return CMP_LT_OR_GT (a1, b1); |

192 | return 0; |

193 | } |

194 | |

195 | static int memcmp_not_common_alignment (long, long, size_t) __THROW; |

196 | |

197 | /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN |

198 | `op_t' objects (not LEN bytes!). SRCP2 should be aligned for memory |

199 | operations on `op_t', but SRCP1 *should be unaligned*. */ |

200 | static int |

201 | memcmp_not_common_alignment (long int srcp1, long int srcp2, size_t len) |

202 | { |

203 | op_t a0, a1, a2, a3; |

204 | op_t b0, b1, b2, b3; |

205 | op_t x; |

206 | int shl, shr; |

207 | |

208 | /* Calculate how to shift a word read at the memory operation |

209 | aligned srcp1 to make it aligned for comparison. */ |

210 | |

211 | shl = 8 * (srcp1 % OPSIZ); |

212 | shr = 8 * OPSIZ - shl; |

213 | |

214 | /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t' |

215 | it points in the middle of. */ |

216 | srcp1 &= -OPSIZ; |

217 | |

218 | switch (len % 4) |

219 | { |

220 | default: /* Avoid warning about uninitialized local variables. */ |

221 | case 2: |

222 | a1 = ((op_t *) srcp1)[0]; |

223 | a2 = ((op_t *) srcp1)[1]; |

224 | b2 = ((op_t *) srcp2)[0]; |

225 | srcp1 -= 1 * OPSIZ; |

226 | srcp2 -= 2 * OPSIZ; |

227 | len += 2; |

228 | goto do1; |

229 | case 3: |

230 | a0 = ((op_t *) srcp1)[0]; |

231 | a1 = ((op_t *) srcp1)[1]; |

232 | b1 = ((op_t *) srcp2)[0]; |

233 | srcp2 -= 1 * OPSIZ; |

234 | len += 1; |

235 | goto do2; |

236 | case 0: |

237 | if (OP_T_THRES <= 3 * OPSIZ && len == 0) |

238 | return 0; |

239 | a3 = ((op_t *) srcp1)[0]; |

240 | a0 = ((op_t *) srcp1)[1]; |

241 | b0 = ((op_t *) srcp2)[0]; |

242 | srcp1 += 1 * OPSIZ; |

243 | goto do3; |

244 | case 1: |

245 | a2 = ((op_t *) srcp1)[0]; |

246 | a3 = ((op_t *) srcp1)[1]; |

247 | b3 = ((op_t *) srcp2)[0]; |

248 | srcp1 += 2 * OPSIZ; |

249 | srcp2 += 1 * OPSIZ; |

250 | len -= 1; |

251 | if (OP_T_THRES <= 3 * OPSIZ && len == 0) |

252 | goto do0; |

253 | /* Fall through. */ |

254 | } |

255 | |

256 | do |

257 | { |

258 | a0 = ((op_t *) srcp1)[0]; |

259 | b0 = ((op_t *) srcp2)[0]; |

260 | x = MERGE(a2, shl, a3, shr); |

261 | if (x != b3) |

262 | return CMP_LT_OR_GT (x, b3); |

263 | |

264 | do3: |

265 | a1 = ((op_t *) srcp1)[1]; |

266 | b1 = ((op_t *) srcp2)[1]; |

267 | x = MERGE(a3, shl, a0, shr); |

268 | if (x != b0) |

269 | return CMP_LT_OR_GT (x, b0); |

270 | |

271 | do2: |

272 | a2 = ((op_t *) srcp1)[2]; |

273 | b2 = ((op_t *) srcp2)[2]; |

274 | x = MERGE(a0, shl, a1, shr); |

275 | if (x != b1) |

276 | return CMP_LT_OR_GT (x, b1); |

277 | |

278 | do1: |

279 | a3 = ((op_t *) srcp1)[3]; |

280 | b3 = ((op_t *) srcp2)[3]; |

281 | x = MERGE(a1, shl, a2, shr); |

282 | if (x != b2) |

283 | return CMP_LT_OR_GT (x, b2); |

284 | |

285 | srcp1 += 4 * OPSIZ; |

286 | srcp2 += 4 * OPSIZ; |

287 | len -= 4; |

288 | } |

289 | while (len != 0); |

290 | |

291 | /* This is the right position for do0. Please don't move |

292 | it into the loop. */ |

293 | do0: |

294 | x = MERGE(a2, shl, a3, shr); |

295 | if (x != b3) |

296 | return CMP_LT_OR_GT (x, b3); |

297 | return 0; |

298 | } |

299 | |

300 | int |

301 | MEMCMP (const void *s1, const void *s2, size_t len) |

302 | { |

303 | op_t a0; |

304 | op_t b0; |

305 | long int srcp1 = (long int) s1; |

306 | long int srcp2 = (long int) s2; |

307 | op_t res; |

308 | |

309 | if (len >= OP_T_THRES) |

310 | { |

311 | /* There are at least some bytes to compare. No need to test |

312 | for LEN == 0 in this alignment loop. */ |

313 | while (srcp2 % OPSIZ != 0) |

314 | { |

315 | a0 = ((byte *) srcp1)[0]; |

316 | b0 = ((byte *) srcp2)[0]; |

317 | srcp1 += 1; |

318 | srcp2 += 1; |

319 | res = a0 - b0; |

320 | if (res != 0) |

321 | return res; |

322 | len -= 1; |

323 | } |

324 | |

325 | /* SRCP2 is now aligned for memory operations on `op_t'. |

326 | SRCP1 alignment determines if we can do a simple, |

327 | aligned compare or need to shuffle bits. */ |

328 | |

329 | if (srcp1 % OPSIZ == 0) |

330 | res = memcmp_common_alignment (srcp1, srcp2, len: len / OPSIZ); |

331 | else |

332 | res = memcmp_not_common_alignment (srcp1, srcp2, len: len / OPSIZ); |

333 | if (res != 0) |

334 | return res; |

335 | |

336 | /* Number of bytes remaining in the interval [0..OPSIZ-1]. */ |

337 | srcp1 += len & -OPSIZ; |

338 | srcp2 += len & -OPSIZ; |

339 | len %= OPSIZ; |

340 | } |

341 | |

342 | /* There are just a few bytes to compare. Use byte memory operations. */ |

343 | while (len != 0) |

344 | { |

345 | a0 = ((byte *) srcp1)[0]; |

346 | b0 = ((byte *) srcp2)[0]; |

347 | srcp1 += 1; |

348 | srcp2 += 1; |

349 | res = a0 - b0; |

350 | if (res != 0) |

351 | return res; |

352 | len -= 1; |

353 | } |

354 | |

355 | return 0; |

356 | } |

357 | libc_hidden_builtin_def(memcmp) |

358 | #ifdef weak_alias |

359 | # undef bcmp |

360 | weak_alias (memcmp, bcmp) |

361 | #endif |

362 | |

363 | #undef __memcmpeq |

364 | strong_alias (memcmp, __memcmpeq) |

365 | libc_hidden_def(__memcmpeq) |

366 |