1 | /* Copyright (C) 1991-2024 Free Software Foundation, Inc. |
2 | This file is part of the GNU C Library. |
3 | |
4 | The GNU C Library is free software; you can redistribute it and/or |
5 | modify it under the terms of the GNU Lesser General Public |
6 | License as published by the Free Software Foundation; either |
7 | version 2.1 of the License, or (at your option) any later version. |
8 | |
9 | The GNU C Library is distributed in the hope that it will be useful, |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
12 | Lesser General Public License for more details. |
13 | |
14 | You should have received a copy of the GNU Lesser General Public |
15 | License along with the GNU C Library; if not, see |
16 | <https://www.gnu.org/licenses/>. */ |
17 | |
18 | #include <stdint.h> |
19 | #include <string-fzb.h> |
20 | #include <string-fzc.h> |
21 | #include <string-fzi.h> |
22 | #include <string.h> |
23 | #include <memcopy.h> |
24 | |
25 | #ifdef STRCMP |
26 | # define strcmp STRCMP |
27 | #endif |
28 | |
29 | static inline int |
30 | final_cmp (const op_t w1, const op_t w2) |
31 | { |
32 | unsigned int idx = index_first_zero_ne (x1: w1, x2: w2); |
33 | return extractbyte (x: w1, idx) - extractbyte (x: w2, idx); |
34 | } |
35 | |
36 | /* Aligned loop: if a difference is found, exit to compare the bytes. Else |
37 | if a zero is found we have equal strings. */ |
38 | static inline int |
39 | strcmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1) |
40 | { |
41 | op_t w2 = *x2++; |
42 | |
43 | while (w1 == w2) |
44 | { |
45 | if (has_zero (x: w1)) |
46 | return 0; |
47 | w1 = *x1++; |
48 | w2 = *x2++; |
49 | } |
50 | |
51 | return final_cmp (w1, w2); |
52 | } |
53 | |
54 | /* Unaligned loop: align the first partial of P2, with 0xff for the rest of |
55 | the bytes so that we can also apply the has_zero test to see if we have |
56 | already reached EOS. If we have, then we can simply fall through to the |
57 | final comparison. */ |
58 | static inline int |
59 | strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs) |
60 | { |
61 | op_t w2a = *x2++; |
62 | uintptr_t sh_1 = ofs * CHAR_BIT; |
63 | uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; |
64 | |
65 | op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); |
66 | if (!has_zero (x: w2)) |
67 | { |
68 | op_t w2b; |
69 | |
70 | /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, |
71 | does not contain end-of-string. Therefore it is safe (and necessary) |
72 | to read another word from each while we do not have a difference. */ |
73 | while (1) |
74 | { |
75 | w2b = *x2++; |
76 | w2 = MERGE (w2a, sh_1, w2b, sh_2); |
77 | if (w1 != w2) |
78 | return final_cmp (w1, w2); |
79 | if (has_zero (x: w2b)) |
80 | break; |
81 | w1 = *x1++; |
82 | w2a = w2b; |
83 | } |
84 | |
85 | /* Zero found in the second partial of P2. If we had EOS in the aligned |
86 | word, we have equality. */ |
87 | if (has_zero (x: w1)) |
88 | return 0; |
89 | |
90 | /* Load the final word of P1 and align the final partial of P2. */ |
91 | w1 = *x1++; |
92 | w2 = MERGE (w2b, sh_1, 0, sh_2); |
93 | } |
94 | |
95 | return final_cmp (w1, w2); |
96 | } |
97 | |
98 | /* Compare S1 and S2, returning less than, equal to or |
99 | greater than zero if S1 is lexicographically less than, |
100 | equal to or greater than S2. */ |
101 | int |
102 | strcmp (const char *p1, const char *p2) |
103 | { |
104 | /* Handle the unaligned bytes of p1 first. */ |
105 | uintptr_t n = -(uintptr_t)p1 % sizeof(op_t); |
106 | for (int i = 0; i < n; ++i) |
107 | { |
108 | unsigned char c1 = *p1++; |
109 | unsigned char c2 = *p2++; |
110 | int diff = c1 - c2; |
111 | if (c1 == '\0' || diff != 0) |
112 | return diff; |
113 | } |
114 | |
115 | /* P1 is now aligned to op_t. P2 may or may not be. */ |
116 | const op_t *x1 = (const op_t *) p1; |
117 | op_t w1 = *x1++; |
118 | uintptr_t ofs = (uintptr_t) p2 % sizeof(op_t); |
119 | return ofs == 0 |
120 | ? strcmp_aligned_loop (x1, x2: (const op_t *)p2, w1) |
121 | : strcmp_unaligned_loop (x1, x2: (const op_t *)(p2 - ofs), w1, ofs); |
122 | } |
123 | #ifndef STRCMP |
124 | libc_hidden_builtin_def (strcmp) |
125 | #endif |
126 | |