Use 64 bit counters to keep track of bytes sent/received from the virtual network...
[tinc] / lib / memcmp.c
1 /* Copyright (C) 1991, 1993, 1995, 1997, 1998 Free Software Foundation, Inc.
2    Contributed by Torbjorn Granlund (tege@sics.se).
3
4    NOTE: The canonical source of this file is maintained with the GNU C Library.
5    Bugs can be reported to bug-glibc@prep.ai.mit.edu.
6
7    This program is free software; you can redistribute it and/or modify it
8    under the terms of the GNU General Public License as published by the
9    Free Software Foundation; either version 2, or (at your option) any
10    later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License along
18    with this program; if not, write to the Free Software Foundation, Inc.,
19    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
20 */
21
22 #ifdef HAVE_CONFIG_H
23 # include "config.h"
24 #endif
25
26 #undef  __ptr_t
27 #if defined __cplusplus || (defined __STDC__ && __STDC__)
28 # define __ptr_t        void *
29 #else /* Not C++ or ANSI C.  */
30 # undef const
31 # define const
32 # define __ptr_t        char *
33 #endif /* C++ or ANSI C.  */
34
35 #ifndef __P
36 # if defined __GNUC__ || (defined __STDC__ && __STDC__)
37 #  define __P(args) args
38 # else
39 #  define __P(args) ()
40 # endif  /* GCC.  */
41 #endif  /* Not __P.  */
42
43 #if defined HAVE_STRING_H || defined _LIBC
44 # include <string.h>
45 #endif
46
47 #undef memcmp
48
49 #ifdef _LIBC
50
51 # include <memcopy.h>
52
53 #else   /* Not in the GNU C library.  */
54
55 # include <sys/types.h>
56
57 /* Type to use for aligned memory operations.
58    This should normally be the biggest type supported by a single load
59    and store.  Must be an unsigned type.  */
60 # define op_t   unsigned long int
61 # define OPSIZ  (sizeof(op_t))
62
63 /* Threshold value for when to enter the unrolled loops.  */
64 # define OP_T_THRES     16
65
66 /* Type to use for unaligned operations.  */
67 typedef unsigned char byte;
68
69 # ifndef WORDS_BIGENDIAN
70 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
71 # else
72 #  define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
73 # endif
74
75 #endif  /* In the GNU C library.  */
76
77 #ifdef WORDS_BIGENDIAN
78 # define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
79 #else
80 # define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
81 #endif
82
83 /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
84
85 /* The strategy of this memcmp is:
86
87    1. Compare bytes until one of the block pointers is aligned.
88
89    2. Compare using memcmp_common_alignment or
90       memcmp_not_common_alignment, regarding the alignment of the other
91       block after the initial byte operations.  The maximum number of
92       full words (of type op_t) are compared in this way.
93
94    3. Compare the few remaining bytes.  */
95
96 #ifndef WORDS_BIGENDIAN
97 /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
98    A and B are known to be different.
99    This is needed only on little-endian machines.  */
100
101 static int memcmp_bytes __P((op_t, op_t));
102
103 # ifdef  __GNUC__
104 __inline
105 # endif
106 static int
107 memcmp_bytes (a, b)
108      op_t a, b;
109 {
110   intptr_t srcp1 = (intptr_t) &a;
111   intptr_t srcp2 = (intptr_t) &b;
112   op_t a0, b0;
113
114   do
115     {
116       a0 = ((byte *) srcp1)[0];
117       b0 = ((byte *) srcp2)[0];
118       srcp1 += 1;
119       srcp2 += 1;
120     }
121   while (a0 == b0);
122   return a0 - b0;
123 }
124 #endif
125
126 static int memcmp_common_alignment __P((intptr_t, intptr_t, size_t));
127
128 /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
129    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
130    memory operations on `op_t's.  */
131 #ifdef  __GNUC__
132 __inline
133 #endif
134 static int
135 memcmp_common_alignment (srcp1, srcp2, len)
136      intptr_t srcp1;
137      intptr_t srcp2;
138      size_t len;
139 {
140   op_t a0, a1;
141   op_t b0, b1;
142
143   switch (len % 4)
144     {
145     default: /* Avoid warning about uninitialized local variables.  */
146     case 2:
147       a0 = ((op_t *) srcp1)[0];
148       b0 = ((op_t *) srcp2)[0];
149       srcp1 -= 2 * OPSIZ;
150       srcp2 -= 2 * OPSIZ;
151       len += 2;
152       goto do1;
153     case 3:
154       a1 = ((op_t *) srcp1)[0];
155       b1 = ((op_t *) srcp2)[0];
156       srcp1 -= OPSIZ;
157       srcp2 -= OPSIZ;
158       len += 1;
159       goto do2;
160     case 0:
161       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
162         return 0;
163       a0 = ((op_t *) srcp1)[0];
164       b0 = ((op_t *) srcp2)[0];
165       goto do3;
166     case 1:
167       a1 = ((op_t *) srcp1)[0];
168       b1 = ((op_t *) srcp2)[0];
169       srcp1 += OPSIZ;
170       srcp2 += OPSIZ;
171       len -= 1;
172       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
173         goto do0;
174       /* Fall through.  */
175     }
176
177   do
178     {
179       a0 = ((op_t *) srcp1)[0];
180       b0 = ((op_t *) srcp2)[0];
181       if (a1 != b1)
182         return CMP_LT_OR_GT (a1, b1);
183
184     do3:
185       a1 = ((op_t *) srcp1)[1];
186       b1 = ((op_t *) srcp2)[1];
187       if (a0 != b0)
188         return CMP_LT_OR_GT (a0, b0);
189
190     do2:
191       a0 = ((op_t *) srcp1)[2];
192       b0 = ((op_t *) srcp2)[2];
193       if (a1 != b1)
194         return CMP_LT_OR_GT (a1, b1);
195
196     do1:
197       a1 = ((op_t *) srcp1)[3];
198       b1 = ((op_t *) srcp2)[3];
199       if (a0 != b0)
200         return CMP_LT_OR_GT (a0, b0);
201
202       srcp1 += 4 * OPSIZ;
203       srcp2 += 4 * OPSIZ;
204       len -= 4;
205     }
206   while (len != 0);
207
208   /* This is the right position for do0.  Please don't move
209      it into the loop.  */
210  do0:
211   if (a1 != b1)
212     return CMP_LT_OR_GT (a1, b1);
213   return 0;
214 }
215
216 static int memcmp_not_common_alignment __P((intptr_t, intptr_t, size_t));
217
218 /* memcmp_not_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN
219    `op_t' objects (not LEN bytes!).  SRCP2 should be aligned for memory
220    operations on `op_t', but SRCP1 *should be unaligned*.  */
221 #ifdef  __GNUC__
222 __inline
223 #endif
224 static int
225 memcmp_not_common_alignment (srcp1, srcp2, len)
226      intptr_t srcp1;
227      intptr_t srcp2;
228      size_t len;
229 {
230   op_t a0, a1, a2, a3;
231   op_t b0, b1, b2, b3;
232   op_t x;
233   int shl, shr;
234
235   /* Calculate how to shift a word read at the memory operation
236      aligned srcp1 to make it aligned for comparison.  */
237
238   shl = 8 * (srcp1 % OPSIZ);
239   shr = 8 * OPSIZ - shl;
240
241   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
242      it points in the middle of.  */
243   srcp1 &= -OPSIZ;
244
245   switch (len % 4)
246     {
247     default: /* Avoid warning about uninitialized local variables.  */
248     case 2:
249       a1 = ((op_t *) srcp1)[0];
250       a2 = ((op_t *) srcp1)[1];
251       b2 = ((op_t *) srcp2)[0];
252       srcp1 -= 1 * OPSIZ;
253       srcp2 -= 2 * OPSIZ;
254       len += 2;
255       goto do1;
256     case 3:
257       a0 = ((op_t *) srcp1)[0];
258       a1 = ((op_t *) srcp1)[1];
259       b1 = ((op_t *) srcp2)[0];
260       srcp2 -= 1 * OPSIZ;
261       len += 1;
262       goto do2;
263     case 0:
264       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
265         return 0;
266       a3 = ((op_t *) srcp1)[0];
267       a0 = ((op_t *) srcp1)[1];
268       b0 = ((op_t *) srcp2)[0];
269       srcp1 += 1 * OPSIZ;
270       goto do3;
271     case 1:
272       a2 = ((op_t *) srcp1)[0];
273       a3 = ((op_t *) srcp1)[1];
274       b3 = ((op_t *) srcp2)[0];
275       srcp1 += 2 * OPSIZ;
276       srcp2 += 1 * OPSIZ;
277       len -= 1;
278       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
279         goto do0;
280       /* Fall through.  */
281     }
282
283   do
284     {
285       a0 = ((op_t *) srcp1)[0];
286       b0 = ((op_t *) srcp2)[0];
287       x = MERGE(a2, shl, a3, shr);
288       if (x != b3)
289         return CMP_LT_OR_GT (x, b3);
290
291     do3:
292       a1 = ((op_t *) srcp1)[1];
293       b1 = ((op_t *) srcp2)[1];
294       x = MERGE(a3, shl, a0, shr);
295       if (x != b0)
296         return CMP_LT_OR_GT (x, b0);
297
298     do2:
299       a2 = ((op_t *) srcp1)[2];
300       b2 = ((op_t *) srcp2)[2];
301       x = MERGE(a0, shl, a1, shr);
302       if (x != b1)
303         return CMP_LT_OR_GT (x, b1);
304
305     do1:
306       a3 = ((op_t *) srcp1)[3];
307       b3 = ((op_t *) srcp2)[3];
308       x = MERGE(a1, shl, a2, shr);
309       if (x != b2)
310         return CMP_LT_OR_GT (x, b2);
311
312       srcp1 += 4 * OPSIZ;
313       srcp2 += 4 * OPSIZ;
314       len -= 4;
315     }
316   while (len != 0);
317
318   /* This is the right position for do0.  Please don't move
319      it into the loop.  */
320  do0:
321   x = MERGE(a2, shl, a3, shr);
322   if (x != b3)
323     return CMP_LT_OR_GT (x, b3);
324   return 0;
325 }
326
327 int
328 rpl_memcmp (s1, s2, len)
329      const __ptr_t s1;
330      const __ptr_t s2;
331      size_t len;
332 {
333   op_t a0;
334   op_t b0;
335   intptr_t srcp1 = (intptr_t) s1;
336   intptr_t srcp2 = (intptr_t) s2;
337   op_t res;
338
339   if (len >= OP_T_THRES)
340     {
341       /* There are at least some bytes to compare.  No need to test
342          for LEN == 0 in this alignment loop.  */
343       while (srcp2 % OPSIZ != 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       /* SRCP2 is now aligned for memory operations on `op_t'.
356          SRCP1 alignment determines if we can do a simple,
357          aligned compare or need to shuffle bits.  */
358
359       if (srcp1 % OPSIZ == 0)
360         res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
361       else
362         res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
363       if (res != 0)
364         return res;
365
366       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
367       srcp1 += len & -OPSIZ;
368       srcp2 += len & -OPSIZ;
369       len %= OPSIZ;
370     }
371
372   /* There are just a few bytes to compare.  Use byte memory operations.  */
373   while (len != 0)
374     {
375       a0 = ((byte *) srcp1)[0];
376       b0 = ((byte *) srcp2)[0];
377       srcp1 += 1;
378       srcp2 += 1;
379       res = a0 - b0;
380       if (res != 0)
381         return res;
382       len -= 1;
383     }
384
385   return 0;
386 }
387
388 #ifdef weak_alias
389 # undef bcmp
390 weak_alias (memcmp, bcmp)
391 #endif