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