home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / glibc-1.06 / sysdeps / generic / memcmp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-03  |  7.6 KB  |  332 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.  */
  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. /* memcmp_common_alignment -- Compare blocks at SRCP1 and SRCP2 with LEN `op_t'
  77.    objects (not LEN bytes!).  Both SRCP1 and SRCP2 should be aligned for
  78.    memory operations on `op_t's.  */
  79. #ifdef    __GNUC__
  80. __inline
  81. #endif
  82. static int
  83. memcmp_common_alignment (srcp1, srcp2, len)
  84.      long int srcp1;
  85.      long int srcp2;
  86.      size_t len;
  87. {
  88.   op_t a0, a1;
  89.   op_t b0, b1;
  90.   op_t res;
  91.  
  92.   switch (len % 4)
  93.     {
  94.     case 2:
  95.       a0 = ((op_t *) srcp1)[0];
  96.       b0 = ((op_t *) srcp2)[0];
  97.       srcp1 -= 2 * OPSIZ;
  98.       srcp2 -= 2 * OPSIZ;
  99.       len += 2;
  100.       goto do1;
  101.     case 3:
  102.       a1 = ((op_t *) srcp1)[0];
  103.       b1 = ((op_t *) srcp2)[0];
  104.       srcp1 -= OPSIZ;
  105.       srcp2 -= OPSIZ;
  106.       len += 1;
  107.       goto do2;
  108.     case 0:
  109.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  110.     return 0;
  111.       a0 = ((op_t *) srcp1)[0];
  112.       b0 = ((op_t *) srcp2)[0];
  113.       goto do3;
  114.     case 1:
  115.       a1 = ((op_t *) srcp1)[0];
  116.       b1 = ((op_t *) srcp2)[0];
  117.       srcp1 += OPSIZ;
  118.       srcp2 += OPSIZ;
  119.       len -= 1;
  120.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  121.     goto do0;
  122.       /* Fall through.  */
  123.     }
  124.  
  125.   do
  126.     {
  127.       a0 = ((op_t *) srcp1)[0];
  128.       b0 = ((op_t *) srcp2)[0];
  129.       res = a1 - b1;
  130.       if (res != 0)
  131.     return res;
  132.     do3:
  133.       a1 = ((op_t *) srcp1)[1];
  134.       b1 = ((op_t *) srcp2)[1];
  135.       res = a0 - b0;
  136.       if (res != 0)
  137.     return res;
  138.     do2:
  139.       a0 = ((op_t *) srcp1)[2];
  140.       b0 = ((op_t *) srcp2)[2];
  141.       res = a1 - b1;
  142.       if (res != 0)
  143.     return res;
  144.     do1:
  145.       a1 = ((op_t *) srcp1)[3];
  146.       b1 = ((op_t *) srcp2)[3];
  147.       res = a0 - b0;
  148.       if (res != 0)
  149.     return res;
  150.  
  151.       srcp1 += 4 * OPSIZ;
  152.       srcp2 += 4 * OPSIZ;
  153.       len -= 4;
  154.     }
  155.   while (len != 0);
  156.  
  157.   /* This is the right position for do0.  Please don't move
  158.      it into the loop.  */
  159.  do0:
  160.   return a1 - b1;
  161. }
  162.  
  163.  
  164. /* SRCP2 should be aligned for memory operations on `op_t',
  165.    but SRCP1 *should be unaligned*.  */
  166.  
  167. #ifdef    __GNUC__
  168. __inline
  169. #endif
  170. static int
  171. memcmp_not_common_alignment (srcp1, srcp2, len)
  172.      long int srcp1;
  173.      long int srcp2;
  174.      size_t len;
  175. {
  176.   op_t a0, a1, a2, a3;
  177.   op_t b0, b1, b2, b3;
  178.   op_t res;
  179.   op_t x;
  180.   int shl, shr;
  181.  
  182.   /* Calculate how to shift a word read at the memory operation
  183.      aligned srcp1 to make it aligned for comparison.  */
  184.  
  185.   shl = 8 * (srcp1 % OPSIZ);
  186.   shr = 8 * OPSIZ - shl;
  187.  
  188.   /* Make SRCP1 aligned by rounding it down to the beginning of the `op_t'
  189.      it points in the middle of.  */
  190.   srcp1 &= -OPSIZ;
  191.  
  192.   switch (len % 4)
  193.     {
  194.     case 2:
  195.       a1 = ((op_t *) srcp1)[0];
  196.       a2 = ((op_t *) srcp1)[1];
  197.       b2 = ((op_t *) srcp2)[0];
  198.       srcp1 -= 1 * OPSIZ;
  199.       srcp2 -= 2 * OPSIZ;
  200.       len += 2;
  201.       goto do1;
  202.     case 3:
  203.       a0 = ((op_t *) srcp1)[0];
  204.       a1 = ((op_t *) srcp1)[1];
  205.       b1 = ((op_t *) srcp2)[0];
  206.       srcp2 -= 1 * OPSIZ;
  207.       len += 1;
  208.       goto do2;
  209.     case 0:
  210.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  211.     return 0;
  212.       a3 = ((op_t *) srcp1)[0];
  213.       a0 = ((op_t *) srcp1)[1];
  214.       b0 = ((op_t *) srcp2)[0];
  215.       srcp1 += 1 * OPSIZ;
  216.       goto do3;
  217.     case 1:
  218.       a2 = ((op_t *) srcp1)[0];
  219.       a3 = ((op_t *) srcp1)[1];
  220.       b3 = ((op_t *) srcp2)[0];
  221.       srcp1 += 2 * OPSIZ;
  222.       srcp2 += 1 * OPSIZ;
  223.       len -= 1;
  224.       if (OP_T_THRES <= 3 * OPSIZ && len == 0)
  225.     goto do0;
  226.       /* Fall through.  */
  227.     }
  228.  
  229.   do
  230.     {
  231.       a0 = ((op_t *) srcp1)[0];
  232.       b0 = ((op_t *) srcp2)[0];
  233.       x = MERGE(a2, shl, a3, shr);
  234.       res = x - b3;
  235.       if (res != 0)
  236.     return res;
  237.     do3:
  238.       a1 = ((op_t *) srcp1)[1];
  239.       b1 = ((op_t *) srcp2)[1];
  240.       x = MERGE(a3, shl, a0, shr);
  241.       res = x - b0;
  242.       if (res != 0)
  243.     return res;
  244.     do2:
  245.       a2 = ((op_t *) srcp1)[2];
  246.       b2 = ((op_t *) srcp2)[2];
  247.       x = MERGE(a0, shl, a1, shr);
  248.       res = x - b1;
  249.       if (res != 0)
  250.     return res;
  251.     do1:
  252.       a3 = ((op_t *) srcp1)[3];
  253.       b3 = ((op_t *) srcp2)[3];
  254.       x = MERGE(a1, shl, a2, shr);
  255.       res = x - b2;
  256.       if (res != 0)
  257.     return res;
  258.  
  259.       srcp1 += 4 * OPSIZ;
  260.       srcp2 += 4 * OPSIZ;
  261.       len -= 4;
  262.     }
  263.   while (len != 0);
  264.  
  265.   /* This is the right position for do0.  Please don't move
  266.      it into the loop.  */
  267.  do0:
  268.   x = MERGE(a2, shl, a3, shr);
  269.   return x - b3;
  270. }
  271.  
  272. int
  273. memcmp (s1, s2, len)
  274.      const __ptr_t s1;
  275.      const __ptr_t s2;
  276.      size_t len;
  277. {
  278.   op_t a0;
  279.   op_t b0;
  280.   long int srcp1 = (long int) s1;
  281.   long int srcp2 = (long int) s2;
  282.   op_t res;
  283.  
  284.   if (len >= OP_T_THRES)
  285.     {
  286.       /* There are at least some bytes to compare.  No need to test
  287.      for LEN == 0 in this alignment loop.  */
  288.       while (srcp2 % OPSIZ != 0)
  289.     {
  290.       a0 = ((byte *) srcp1)[0];
  291.       b0 = ((byte *) srcp2)[0];
  292.       srcp1 += 1;
  293.       srcp2 += 1;
  294.       res = a0 - b0;
  295.       if (res != 0)
  296.         return res;
  297.       len -= 1;
  298.     }
  299.  
  300.       /* SRCP2 is now aligned for memory operations on `op_t'.
  301.      SRCP1 alignment determines if we can do a simple,
  302.      aligned compare or need to shuffle bits.  */
  303.  
  304.       if (srcp1 % OPSIZ == 0)
  305.     res = memcmp_common_alignment (srcp1, srcp2, len / OPSIZ);
  306.       else
  307.     res = memcmp_not_common_alignment (srcp1, srcp2, len / OPSIZ);
  308.       if (res != 0)
  309.     return res;
  310.  
  311.       /* Number of bytes remaining in the interval [0..OPSIZ-1].  */
  312.       srcp1 += len & -OPSIZ;
  313.       srcp2 += len & -OPSIZ;
  314.       len %= OPSIZ;
  315.     }
  316.  
  317.   /* There are just a few bytes to compare.  Use byte memory operations.  */
  318.   while (len != 0)
  319.     {
  320.       a0 = ((byte *) srcp1)[0];
  321.       b0 = ((byte *) srcp2)[0];
  322.       srcp1 += 1;
  323.       srcp2 += 1;
  324.       res = a0 - b0;
  325.       if (res != 0)
  326.     return res;
  327.       len -= 1;
  328.     }
  329.  
  330.   return 0;
  331. }
  332.