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