home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / glibc-1.09 / glibc-1 / glibc-1.09.1 / sysdeps / generic / memcmp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-24  |  8.5 KB  |  365 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. #include <sys/types.h>
  43.  
  44. /* Type to use for aligned memory operations.
  45.    This should normally be the biggest type supported by a single load
  46.    and store.  Must be an unsigned type.  */
  47. #define    op_t    unsigned long int
  48. #define OPSIZ    (sizeof(op_t))
  49.  
  50. /* Threshold value for when to enter the unrolled loops.  */
  51. #define    OP_T_THRES    16
  52.  
  53. /* Type to use for unaligned operations.  */
  54. typedef unsigned char byte;
  55.  
  56. #ifndef WORDS_BIGENDIAN
  57. #define MERGE(w0, sh_1, w1, sh_2) (((w0) >> (sh_1)) | ((w1) << (sh_2)))
  58. #else
  59. #define MERGE(w0, sh_1, w1, sh_2) (((w0) << (sh_1)) | ((w1) >> (sh_2)))
  60. #endif
  61.  
  62. #endif    /* In the GNU C library.  */
  63.  
  64. #ifdef WORDS_BIGENDIAN
  65. #define CMP_LT_OR_GT(a, b) ((a) > (b) ? 1 : -1)
  66. #else
  67. #define CMP_LT_OR_GT(a, b) memcmp_bytes ((a), (b))
  68. #endif
  69.  
  70. /* BE VERY CAREFUL IF YOU CHANGE THIS CODE!  */
  71.  
  72. /* The strategy of this memcmp is:
  73.  
  74.    1. Compare bytes until one of the block pointers is aligned.
  75.  
  76.    2. Compare using memcmp_common_alignment or
  77.       memcmp_not_common_alignment, regarding the alignment of the other
  78.       block after the initial byte operations.  The maximum number of
  79.       full words (of type op_t) are compared in this way.
  80.  
  81.    3. Compare the few remaining bytes.  */
  82.  
  83. #ifndef WORDS_BIGENDIAN
  84. /* memcmp_bytes -- Compare A and B bytewise in the byte order of the machine.
  85.    A and B are known to be different.
  86.    This is needed only on little-endian machines.  */
  87. #ifdef  __GNUC__
  88. __inline
  89. #endif
  90. static int
  91. memcmp_bytes (a, b)
  92.      op_t a, b;
  93. {
  94.   long int srcp1 = (long int) &a;
  95.   long int srcp2 = (long int) &b;
  96.   op_t a0, b0;
  97.  
  98.   do
  99.     {
  100.       a0 = ((byte *) srcp1)[0];
  101.       b0 = ((byte *) srcp2)[0];
  102.       srcp1 += 1;
  103.       srcp2 += 1;
  104.     }
  105.   while (a0 == b0);
  106.   return a0 - b0;
  107. }
  108. #endif
  109.  
  110. /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
  111.    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
  112.    memory operations on `op_t's.  */
  113. #ifdef    __GNUC__
  114. __inline
  115. #endif
  116. static int
  117. memcmp_common_alignment (srcp1, srcp2, len)
  118.      long int srcp1;
  119.      long int srcp2;
  120.      size_t len;
  121. {
  122.   op_t a0, a1;
  123.   op_t b0, b1;
  124.  
  125.   switch (len % 4)
  126.     {
  127.     case 2:
  128.       a0 = ((op_t *) srcp1)[0];
  129.       b0 = ((op_t *) srcp2)[0];
  130.       srcp1 -= 2 * OPSIZ;
  131.       srcp2 -= 2 * OPSIZ;
  132.       len += 2;
  133.       goto do1;
  134.     case 3:
  135.       a1 = ((op_t *) srcp1)[0];
  136.       b1 = ((op_t *) srcp2)[0];
  137.       srcp1 -= OPSIZ;
  138.       srcp2 -= OPSIZ;
  139.       len += 1;
  140.       goto do2;
  141.     case 0:
  142.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  143.     return 0;
  144.       a0 = ((op_t *) srcp1)[0];
  145.       b0 = ((op_t *) srcp2)[0];
  146.       goto do3;
  147.     case 1:
  148.       a1 = ((op_t *) srcp1)[0];
  149.       b1 = ((op_t *) srcp2)[0];
  150.       srcp1 += OPSIZ;
  151.       srcp2 += OPSIZ;
  152.       len -= 1;
  153.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  154.     goto do0;
  155.       /* Fall through.  */
  156.     }
  157.  
  158.   do
  159.     {
  160.       a0 = ((op_t *) srcp1)[0];
  161.       b0 = ((op_t *) srcp2)[0];
  162.       if (a1 != b1)
  163.     return CMP_LT_OR_GT (a1, b1);
  164.  
  165.     do3:
  166.       a1 = ((op_t *) srcp1)[1];
  167.       b1 = ((op_t *) srcp2)[1];
  168.       if (a0 != b0)
  169.     return CMP_LT_OR_GT (a0, b0);
  170.  
  171.     do2:
  172.       a0 = ((op_t *) srcp1)[2];
  173.       b0 = ((op_t *) srcp2)[2];
  174.       if (a1 != b1)
  175.     return CMP_LT_OR_GT (a1, b1);
  176.  
  177.     do1:
  178.       a1 = ((op_t *) srcp1)[3];
  179.       b1 = ((op_t *) srcp2)[3];
  180.       if (a0 != b0)
  181.     return CMP_LT_OR_GT (a0, b0);
  182.  
  183.       srcp1 += 4 * OPSIZ;
  184.       srcp2 += 4 * OPSIZ;
  185.       len -= 4;
  186.     }
  187.   while (len != 0);
  188.  
  189.   /* This is the right position for do0.  Please don't move
  190.      it into the loop.  */
  191.  do0:
  192.   if (a1 != b1)
  193.     return CMP_LT_OR_GT (a1, b1);
  194.   return 0;
  195. }
  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. #ifdef    __GNUC__
  201. __inline
  202. #endif
  203. static int
  204. memcmp_not_common_alignment (srcp1, srcp2, len)
  205.      long int srcp1;
  206.      long int srcp2;
  207.      size_t len;
  208. {
  209.   op_t a0, a1, a2, a3;
  210.   op_t b0, b1, b2, b3;
  211.   op_t x;
  212.   int shl, shr;
  213.  
  214.   /* Calculate how to shift a word read at the memory operation
  215.      aligned srcp1 to make it aligned for comparison.  */
  216.  
  217.   shl = 8 * (srcp1 % OPSIZ);
  218.   shr = 8 * OPSIZ - shl;
  219.  
  220.   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
  221.      it points in the middle of.  */
  222.   srcp1 &= -OPSIZ;
  223.  
  224.   switch (len % 4)
  225.     {
  226.     case 2:
  227.       a1 = ((op_t *) srcp1)[0];
  228.       a2 = ((op_t *) srcp1)[1];
  229.       b2 = ((op_t *) srcp2)[0];
  230.       srcp1 -= 1 * OPSIZ;
  231.       srcp2 -= 2 * OPSIZ;
  232.       len += 2;
  233.       goto do1;
  234.     case 3:
  235.       a0 = ((op_t *) srcp1)[0];
  236.       a1 = ((op_t *) srcp1)[1];
  237.       b1 = ((op_t *) srcp2)[0];
  238.       srcp2 -= 1 * OPSIZ;
  239.       len += 1;
  240.       goto do2;
  241.     case 0:
  242.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  243.     return 0;
  244.       a3 = ((op_t *) srcp1)[0];
  245.       a0 = ((op_t *) srcp1)[1];
  246.       b0 = ((op_t *) srcp2)[0];
  247.       srcp1 += 1 * OPSIZ;
  248.       goto do3;
  249.     case 1:
  250.       a2 = ((op_t *) srcp1)[0];
  251.       a3 = ((op_t *) srcp1)[1];
  252.       b3 = ((op_t *) srcp2)[0];
  253.       srcp1 += 2 * OPSIZ;
  254.       srcp2 += 1 * OPSIZ;
  255.       len -= 1;
  256.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  257.     goto do0;
  258.       /* Fall through.  */
  259.     }
  260.  
  261.   do
  262.     {
  263.       a0 = ((op_t *) srcp1)[0];
  264.       b0 = ((op_t *) srcp2)[0];
  265.       x = MERGE(a2, shl, a3, shr);
  266.       if (x != b3)
  267.     return CMP_LT_OR_GT (x, b3);
  268.  
  269.     do3:
  270.       a1 = ((op_t *) srcp1)[1];
  271.       b1 = ((op_t *) srcp2)[1];
  272.       x = MERGE(a3, shl, a0, shr);
  273.       if (x != b0)
  274.     return CMP_LT_OR_GT (x, b0);
  275.  
  276.     do2:
  277.       a2 = ((op_t *) srcp1)[2];
  278.       b2 = ((op_t *) srcp2)[2];
  279.       x = MERGE(a0, shl, a1, shr);
  280.       if (x != b1)
  281.     return CMP_LT_OR_GT (x, b1);
  282.  
  283.     do1:
  284.       a3 = ((op_t *) srcp1)[3];
  285.       b3 = ((op_t *) srcp2)[3];
  286.       x = MERGE(a1, shl, a2, shr);
  287.       if (x != b2)
  288.     return CMP_LT_OR_GT (x, b2);
  289.  
  290.       srcp1 += 4 * OPSIZ;
  291.       srcp2 += 4 * OPSIZ;
  292.       len -= 4;
  293.     }
  294.   while (len != 0);
  295.  
  296.   /* This is the right position for do0.  Please don't move
  297.      it into the loop.  */
  298.  do0:
  299.   x = MERGE(a2, shl, a3, shr);
  300.   if (x != b3)
  301.     return CMP_LT_OR_GT (x, b3);
  302.   return 0;
  303. }
  304.  
  305. int
  306. memcmp (s1, s2, len)
  307.      const __ptr_t s1;
  308.      const __ptr_t s2;
  309.      size_t len;
  310. {
  311.   op_t a0;
  312.   op_t b0;
  313.   long int srcp1 = (long int) s1;
  314.   long int srcp2 = (long int) s2;
  315.   op_t res;
  316.  
  317.   if (len >= OP_T_THRES)
  318.     {
  319.       /* There are at least some bytes to compare.  No need to test
  320.      for LEN == 0 in this alignment loop.  */
  321.       while (srcp2 % OPSIZ != 0)
  322.     {
  323.       a0 = ((byte *) srcp1)[0];
  324.       b0 = ((byte *) srcp2)[0];
  325.       srcp1 += 1;
  326.       srcp2 += 1;
  327.       res = a0 - b0;
  328.       if (res != 0)
  329.         return res;
  330.       len -= 1;
  331.     }
  332.  
  333.       /* SRCP2 is now aligned for memory operations on `op_t'.
  334.      SRCP1 alignment determines if we can do a simple,
  335.      aligned compare or need to shuffle bits.  */
  336.  
  337.       if (srcp1 % OPSIZ == 0)
  338.     res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
  339.       else
  340.     res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
  341.       if (res != 0)
  342.     return res;
  343.  
  344.       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
  345.       srcp1 += len & -OPSIZ;
  346.       srcp2 += len & -OPSIZ;
  347.       len %= OPSIZ;
  348.     }
  349.  
  350.   /* There are just a few bytes to compare.  Use byte memory operations.  */
  351.   while (len != 0)
  352.     {
  353.       a0 = ((byte *) srcp1)[0];
  354.       b0 = ((byte *) srcp2)[0];
  355.       srcp1 += 1;
  356.       srcp2 += 1;
  357.       res = a0 - b0;
  358.       if (res != 0)
  359.     return res;
  360.       len -= 1;
  361.     }
  362.  
  363.   return 0;
  364. }
  365.