Debian Codegraph @

share/libc/string.c

raw
1 /**************************************************************************/
2 /* */
3 /* This file is part of Frama-C. */
4 /* */
5 /* Copyright (C) 2007-2022 */
6 /* CEA (Commissariat à l'énergie atomique et aux énergies */
7 /* alternatives) */
8 /* */
9 /* you can redistribute it and/or modify it under the terms of the GNU */
10 /* Lesser General Public License as published by the Free Software */
11 /* Foundation, version 2.1. */
12 /* */
13 /* It is distributed in the hope that it will be useful, */
14 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
15 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
16 /* GNU Lesser General Public License for more details. */
17 /* */
18 /* See the GNU Lesser General Public License version 2.1 */
19 /* for more details (enclosed in the file licenses/LGPLv2.1). */
20 /* */
21 /**************************************************************************/
22
23 #include "__fc_builtin.h"
24 #include "string.h"
25 #include "stdint.h" // for uintptr_t
26 #include "stdlib.h" // for malloc()
27 #include "errno.h"
28 __PUSH_FC_STDLIB
29
30 void* memcpy(void* restrict dest, const void* restrict src, size_t n)
31 {
32 /*@
33 loop invariant no_eva: 0 <= i <= n;
34 loop invariant no_eva: \forall ℤ k; 0 <= k < i ==> ((char*)dest)[k] == ((char*)src)[k];
35 loop assigns i, ((char*)dest)[0 .. n-1];
36 loop variant n - i;
37 */
38 for (size_t i = 0; i < n; i++) {
39 ((char*)dest)[i] = ((char*)src)[i];
40 }
41 return dest;
42 }
43
44 // Non-POSIX; GNU extension
45 void* mempcpy(void* restrict dest, const void* restrict src, size_t n)
46 {
47 size_t i;
48 /*@
49 loop invariant no_eva: 0 <= i <= n;
50 loop invariant no_eva: \forall ℤ k; 0 <= k < i ==> ((char*)dest)[k] == ((char*)src)[k];
51 loop assigns i, ((char*)dest)[0 .. n-1];
52 loop variant n - i;
53 */
54 for (i = 0; i < n; i++) {
55 ((char*)dest)[i] = ((char*)src)[i];
56 }
57 return (char*)dest + i;
58 }
59
60 // memoverlap: auxiliary function that returns
61 // 0 if p[0..n-1] and q[0..n-1] do not overlap;
62 // -1/+1 otherwise, according to whether p is before or after q in the memory
63 /*@
64 assigns \result \from indirect:p, indirect:q, indirect:n;
65 behavior separated:
66 assumes separation:no_overlap: \separated(p + (0 .. n-1), q + (0 .. n-1));
67 ensures result_no_overlap: \result == 0;
68 behavior not_separated_lt:
69 assumes separation:overlap: !\separated(p + (0 .. n-1), q + (0 .. n-1));
70 assumes p_before_q: p <= q < p + n;
71 ensures result_p_before_q: \result == -1;
72 behavior not_separated_gt:
73 assumes separation:overlap: !\separated(p + (0 .. n-1), q + (0 .. n-1));
74 assumes p_after_q: q < p <= q + n;
75 ensures result_p_after_q: \result == 1;
76 complete behaviors;
77 disjoint behaviors;
78 */
79 static int memoverlap(char const *p, char const *q, size_t n) {
80 uintptr_t
81 p1 = (uintptr_t)p, p2 = (uintptr_t)(p+n),
82 q1 = (uintptr_t)q, q2 = (uintptr_t)(q+n);
83 if (p1 <= q1 && p2 > q1) return -1;
84 else if (q1 <= p1 && q2 > p1) return 1;
85 else return 0;
86 }
87
88 void* memmove(void* dest, const void* src, size_t n)
89 {
90 if (n == 0) return dest;
91 char *s = (char*)src;
92 char *d = (char*)dest;
93 if (memoverlap(dest, src, n) <= 0) { /* default: copy up */
94 /*@
95 loop invariant no_eva: 0 <= i <= n;
96 loop invariant no_eva: \forall ℤ k; 0 <= k < i ==> ((char*)dest)[k] == \at(((char*)src)[k],LoopEntry);
97 loop invariant no_eva: \forall ℤ k; i <= k < n ==> ((char*)src)[k] == \at(((char*)src)[k],LoopEntry);
98 loop assigns i, ((char*)dest)[0 .. n-1];
99 loop variant n - i;
100 */
101 for (size_t i = 0; i < n; i++)
102 d[i] = s[i];
103 } else { // beginning of dest overlaps with src: copy down
104 // to avoid unsigned overflow in the loop below, the '0' case is
105 // done outside the loop (note: n == 0 has already been tested)
106 /*@
107 loop invariant no_eva: 0 <= i < n;
108 loop invariant no_eva: \forall ℤ k; i < k < n ==> ((char*)dest)[k] == \at(((char*)src)[k],LoopEntry);
109 loop invariant no_eva: \forall ℤ k; 0 <= k <= i ==> ((char*)src)[k] == \at(((char*)src)[k],LoopEntry);
110 loop assigns i, ((char*)dest)[0 .. n-1];
111 loop variant i;
112 */
113 for (size_t i = n-1; i > 0; i--)
114 d[i] = s[i];
115 d[0] = s[0];
116 }
117 return dest;
118 }
119
120 size_t strlen(const char *s)
121 {
122 size_t i;
123 for (i = 0; s[i] != 0; i++);
124 return i;
125 }
126
127 size_t strnlen(const char *s, size_t maxlen)
128 {
129 size_t i;
130 for (i = 0; i < maxlen && s[i] != 0; i++);
131 return i;
132 }
133
134 void* memset (void* s, int c, size_t n)
135 {
136 unsigned char *p = (unsigned char*)s;
137 for (size_t i = 0; i < n; i++) {
138 p[i] = c;
139 }
140 return s;
141 }
142
143 int strcmp(const char *s1, const char *s2)
144 {
145 size_t i;
146 for (i = 0; s1[i] == s2[i]; i++) {
147 if (s1[i] == 0) return 0;
148 }
149 return (((unsigned char *)s1)[i] - ((unsigned char *)s2)[i]);
150 }
151
152 int strncmp(const char *s1, const char *s2, size_t n)
153 {
154 for (size_t i = 0; i < n; i++) {
155 if (s1[i] != s2[i])
156 return ((unsigned char *)s1)[i] - ((unsigned char *)s2)[i];
157 /* stop comparison when strings end */
158 if (s1[i] == 0) return 0;
159 }
160 return 0;
161 }
162
163 int memcmp(const void *s1, const void *s2, size_t n)
164 {
165 const unsigned char *p1, *p2;
166 p1 = (const unsigned char *)s1;
167 p2 = (const unsigned char *)s2;
168 for (size_t i = 0; i < n; i++)
169 if (p1[i] != p2[i]) return p1[i] - p2[i];
170 return 0;
171 }
172
173 // NOTE: strcasecmp is in POSIX's strings.h but not in C99
174 // auxiliary function for strcasecmp
175 static int char_equal_ignore_case(char c1, char c2)
176 {
177 if (c1 >= 'A' && c1 <= 'Z') c1 -= ('A' - 'a');
178 if (c2 >= 'A' && c2 <= 'Z') c2 -= ('A' - 'a');
179 if (c1 == c2) return 0;
180 else return (int) ((unsigned char)c2 - (unsigned char)c1);
181 }
182
183 int strcasecmp(const char *s1, const char *s2)
184 {
185 size_t i;
186 for (i = 0; s1[i] != 0 && s2[i] != 0; i++) {
187 int res = char_equal_ignore_case(s1[i], s2[i]);
188 if (res != 0) return res;
189 }
190 if (s1[i] == 0 && s2[i] == 0) return 0;
191 else if (s1[i] == 0) return -1;
192 else return 1;
193 }
194
195 char* strcat(char *dest, const char *src)
196 {
197 size_t i;
198 size_t n = strlen(dest);
199 for (i = 0; src[i] != 0; i++) {
200 dest[n+i] = src[i];
201 }
202 dest[n+i] = 0;
203 return dest;
204 }
205
206 /* From the strncat man page */
207 char* strncat(char *dest, const char *src, size_t n)
208 {
209 size_t dest_len = strlen(dest);
210 size_t i;
211 for (i = 0; i < n; i++) {
212 if (src[i] == 0) break;
213 dest[dest_len + i] = src[i];
214 }
215 dest[dest_len + i] = 0;
216
217 return dest;
218 }
219
220 char* strcpy(char *dest, const char *src)
221 {
222 size_t i;
223 for (i = 0; src[i] != 0; i++)
224 dest[i] = src[i];
225 dest[i] = 0;
226 return dest;
227 }
228
229 // POSIX.1-2008
230 char* stpcpy(char *dest, const char *src)
231 {
232 size_t i;
233 for (i = 0; src[i] != 0; i++)
234 dest[i] = src[i];
235 dest[i] = 0;
236 return dest + i;
237 }
238
239 char *strncpy(char *dest, const char *src, size_t n)
240 {
241 size_t i;
242 for (i = 0; i < n; i++) {
243 dest[i] = src[i];
244 if (src[i] == 0) break;
245 }
246 for (; i < n; i++)
247 dest[i] = 0;
248 return dest;
249 }
250
251 char *strchr(const char *s, int c)
252 {
253 const char ch = c;
254 size_t i;
255 for (i = 0; s[i] != ch; i++)
256 if (s[i] == 0) return NULL;
257 return (char*)&s[i];
258 }
259
260 char *strrchr(const char *s, int c)
261 {
262 const char ch = c;
263 for (size_t i = strlen(s)+1; i > 0; i--)
264 if (s[i-1] == ch) return (char *)&s[i-1];
265 return NULL;
266 }
267
268 void *memchr(const void *s, int c, size_t n)
269 {
270 const unsigned char ch = c;
271 const unsigned char *ss = (const unsigned char *)s;
272 for (size_t i = 0; i < n; i++)
273 if (ss[i] == ch) return (void *)&ss[i];
274 return NULL;
275 }
276
277 void *memrchr(const void *s, int c, size_t n)
278 {
279 const unsigned char ch = c;
280 const unsigned char *ss = (const unsigned char *)s;
281 for (size_t i = n; i > 0; i--)
282 if (ss[i-1] == ch) return (void *)&ss[i-1];
283 return NULL;
284 }
285
286 char *strstr(const char *haystack, const char *needle)
287 {
288 // special case: empty string starts everywhere
289 if (needle[0] == 0) return (char*)haystack;
290 for (size_t i = 0; haystack[i] != 0; i++) {
291 size_t j;
292 for (j = 0; haystack[i+j] != 0; j++) {
293 if (haystack[i+j] != needle[j]) break;
294 }
295 if (needle[j] == 0) return (char*)&haystack[i];
296 }
297 return NULL;
298 }
299
300 char __fc_strerror[64];
301
302 char *strerror(int errnum)
303 {
304 #ifdef __FRAMAC__
305 static int __fc_strerror_init;
306 if (!__fc_strerror_init) {
307 Frama_C_make_unknown(__fc_strerror, 63);
308 __fc_strerror[63] = 0;
309 __fc_strerror_init = 1;
310 }
311 #endif
312 return __fc_strerror;
313 }
314
315 /* Warning: read considerations about malloc() in Frama-C */
316 char *strdup(const char *s)
317 {
318 size_t l = strlen(s) + 1;
319 char *p = malloc(l);
320 if (!p) {
321 errno = ENOMEM;
322 return 0;
323 }
324 memcpy(p, s, l);
325 return p;
326 }
327
328 /* Warning: read considerations about malloc() in Frama-C */
329 char *strndup(const char *s, size_t n)
330 {
331 /* find length up to n bytes */
332 size_t l;
333 for (l = 0; l < n; l++) {
334 if (s[l] == 0) break;
335 }
336 char *p = malloc(l+1); /* include terminating '\0' */
337 if (!p) {
338 errno = ENOMEM;
339 return 0;
340 }
341 memcpy(p, s, l);
342 p[l] = 0;
343 return p;
344 }
345
346 char __fc_strsignal[64];
347
348 char *strsignal(int signum)
349 {
350 #ifdef __FRAMAC__
351 static int __fc_strsignal_init;
352 if (!__fc_strsignal_init) {
353 Frama_C_make_unknown(__fc_strsignal, 63);
354 __fc_strsignal[63] = 0;
355 __fc_strsignal_init = 1;
356 }
357 #endif
358 return __fc_strsignal;
359 }
360
361 __POP_FC_STDLIB