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 / i386 / memchr.c.new < prev    next >
Encoding:
Text File  |  1994-12-12  |  9.5 KB  |  318 lines

  1. /* memchr (str, ch, n) -- Return pointer to first occurrence of CH in STR less
  2.    than N.
  3.    For Intel 80x86, x>=3.
  4.    Copyright (C) 1994 Free Software Foundation, Inc.
  5.    Contributed by Ulrich Drepper <drepper@ira.uka.de>
  6.  
  7.    This version is developed using the same algorithm as the fast C
  8.    version which carries the following introduction:
  9.  
  10.    Based on strlen implemention by Torbjorn Granlund (tege@sics.se),
  11.    with help from Dan Sahlin (dan@sics.se) and
  12.    commentary by Jim Blandy (jimb@ai.mit.edu);
  13.    adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
  14.    and implemented by Roland McGrath (roland@ai.mit.edu).
  15.  
  16. The GNU C Library is free software; you can redistribute it and/or
  17. modify it under the terms of the GNU Library General Public License as
  18. published by the Free Software Foundation; either version 2 of the
  19. License, or (at your option) any later version.
  20.  
  21. The GNU C Library is distributed in the hope that it will be useful,
  22. but WITHOUT ANY WARRANTY; without even the implied warranty of
  23. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  24. Library General Public License for more details.
  25.  
  26. You should have received a copy of the GNU Library General Public
  27. License along with the GNU C Library; see the file COPYING.LIB.  If
  28. not, write to the Free Software Foundation, Inc., 675 Mass Ave,
  29. Cambridge, MA 02139, USA.  */
  30.  
  31. #include <ansidecl.h>
  32.  
  33. #include <string.h>
  34.  
  35. #ifdef    __GNUC__
  36.  
  37. #include "asm-ops.h"
  38.  
  39. PTR
  40. memchr(CONST PTR str, int c, size_t len)
  41. {
  42. PTR __res;
  43. __asm__(
  44. #if defined(__PIC__) || defined(__pic__)    
  45.         /*
  46.      * As with gcc-2.6.2 it has problems with the %ebx handling.  It
  47.      * should know that %ebx is a special register and must be saved
  48.      * but it don't.  So we have to do it by hand...
  49.      */
  50.     "pushl %%ebx\n\t"
  51. #endif
  52.     "testl %3,%3\n\t"
  53.     "je " LF(7) "\n\t"    /* if len==0, not found => return NULL */
  54.  
  55.     "movb %%dl,%%dh\n\t"    /* now %dx is c|c */
  56.     "movw %%dx,%%di\n\t"
  57.     "shll $16,%%edx\n\t"    /*     %edx is c|c|0|0 */
  58.     "movw %%di,%%dx\n\t"    /*     %edx is c|c|c|c */
  59.  
  60.     /* A better performance can be achieved if the word (32 bit) memory
  61.      * access is aligned on a four-byte-boundary.  So process first
  62.      * bytes one by one until boundary is reached.  Don't use a loop
  63.      * for better performance.  */
  64.  
  65.         "testb $3,%0\n\t"       /* correct aligned ? */
  66.         "je " LF(1) "\n\t"      /* yes => begin loop */
  67.         "cmpb %%dl,(%0)\n\t"    /* compare byte */
  68.         "je " LF(9) "\n\t"      /* target found => return */
  69.         "incl %0\n\t"           /* increment source ptr */
  70.         "decl %3\n\t"           /* decrement len counter */
  71.         "je " LF(7) "\n\t"      /* len==0 => return NULL */
  72.  
  73.     "testb $3,%0\n\t"    /* dito */
  74.     "je " LF(1) "\n\t"
  75.     "cmpb %%dl,(%0)\n\t"
  76.     "je " LF(9) "\n\t"
  77.     "incl %0\n\t"
  78.     "decl %3\n\t"
  79.     "je " LF(7) "\n\t"
  80.  
  81.     "testb $3,%0\n\t"    /* dito */
  82.     "je " LF(1) "\n\t"
  83.     "cmpb %%dl,(%0)\n\t"
  84.     "je " LF(9) "\n\t"
  85.     "incl %0\n\t"
  86.     "decl %3\n"
  87.         /* no test for %3==0 here, because this is done in the loop head */
  88.  
  89.       /* We tentatively exit the loop if adding MAGIC_BITS to
  90.      LONGWORD fails to change any of the hole bits of LONGWORD.
  91.  
  92.      1) Is this safe?  Will it catch all the zero bytes?
  93.      Suppose there is a byte with all zeros.  Any carry bits
  94.      propagating from its left will fall into the hole at its
  95.      least significant bit and stop.  Since there will be no
  96.      carry from its most significant bit, the LSB of the
  97.      byte to the left will be unchanged, and the zero will be
  98.      detected.
  99.  
  100.      2) Is this worthwhile?  Will it ignore everything except
  101.      zero bytes?  Suppose every byte of LONGWORD has a bit set
  102.      somewhere.  There will be a carry into bit 8.  If bit 8
  103.      is set, this will carry into bit 16.  If bit 8 is clear,
  104.      one of bits 9-15 must be set, so there will be a carry
  105.      into bit 16.  Similarly, there will be a carry into bit
  106.      24.  If one of bits 24-31 is set, there will be a carry
  107.      into bit 32 (=carry flag), so all of the hole bits will
  108.      be changed.
  109.  
  110.      3) But wait!  Aren't we looking for C, not zero?
  111.      Good point.  So what we do is XOR LONGWORD with a longword,
  112.      each of whose bytes is C.  This turns each byte that is C
  113.      into a zero.  */
  114.  
  115.         /* each round the main loop processes 16 bytes.  Because the correction
  116.          * of the counters happens as the first loop we have to correct
  117.      * them here.  */
  118.  
  119.     /* If you cannot guess what this is for look through the resulting
  120.      * code.  The dumb version has an .align at the beginning of the
  121.      * following asm statement.  This is quite long.  If we could
  122.      * make the jump to the label '1' behind the NOPs we could save
  123.      * the time in 75% of the cases.  Exactly this is done here.
  124.      * If anything in the prepending code changes the number of NOPs
  125.      * may have to change, too.  */
  126.  
  127. #if (!defined(__i486__) && !defined(__i586__)) || \
  128.     defined(I_DONT_KNOW_WHAT_THIS_MEANS)
  129.     
  130. LL(1)    "\tsubl $16,%0\n\t"
  131.     "addl $16,%3\n\t"
  132.  
  133.     ALIGN
  134. #else
  135.     "\tnop; nop; nop\n"
  136. LL(1)    "\tsubl $16,%0\n\t"
  137.     "addl $16,%3\n"
  138. #endif
  139.  
  140.         /* Decrement both counters for a full round, i.e. 16 bytes.  */
  141. LL(2)    "\taddl $16,%0\n\t"
  142.     "subl $16,%3\n\t"
  143.  
  144.         /* If less than 16 bytes remain to test do them outside the loop.  */
  145.         "cmpl $16,%3\n\t"
  146.     "jb " LF(8) "\n\t"
  147.  
  148.     /* Get word (= 4 bytes) in question) */
  149.     "movl (%0),%%edi\n\t"
  150.  
  151.     /* XOR with word c|c|c|c => bytes of str == c, are now 0 */
  152.     "xorl %%edx,%%edi\n\t"
  153.  
  154.     /* We need the inverted of this value for the last step => %ebx.
  155.        inverting follows below.  */
  156.     "movl %%edi,%%ebx\n\t"
  157.  
  158.     /* Add the magic value to the word.  We get carry bits reported
  159.        for each byte which != 0  */
  160.     "addl $0xfefefeff,%%edi\n\t"
  161.  
  162.     /* According to the algorithm we had to reverse the effect of the
  163.      * XOR first and then test the overflow bits.  But because the
  164.      * following XOR would destroy the carry flag and it would (in a
  165.      * representation with more than 32 bits) not alter then last
  166.      * overflow, we can now test this condition.  If now carry is signaled
  167.      * no overflow must have occured in the last byte => it was 0.  */
  168.     "jnc " LF(6) "\n\t"
  169.  
  170.     /* Reverse the effect of the first XOR because we look for c and not
  171.        for zero.  */
  172.     "xorl %%ebx,%%edi\n\t"    /* ((word^charmask)+magic)&~(word^charmask) */
  173.  
  174.          /* invert  */
  175.     "notl %%edi\n\t"
  176.  
  177.     /* Now test for the other three overflow bits.  */
  178.     "andl $0x01010100,%%edi\n\t" /* and examine overflow bits */
  179.  
  180.     /* If at least one bit is set an matching byte was detected.  */
  181.     "jne " LF(6) "\n\t"
  182.  
  183.     /* this process is here four times unfolded for better performance.
  184.      * we don't increment the source pointer each time.  Instead we
  185.      * use offsets and increment by 16 in each run of the loop.  But
  186.      * before probing for the matching by we need some extra code
  187.      * (following LL(13) below).  Even the len can be compared with
  188.      * constants instead of decrementing each time.  */
  189.  
  190.     "movl 4(%0),%%edi\n\t"
  191.     "xorl %%edx,%%edi\n\t"
  192.     "movl %%edi,%%ebx\n\t"
  193.     "addl $0xfefefeff,%%edi\n\t"
  194.     "jnc " LF(5) "\n\t"
  195.     "xorl %%ebx,%%edi\n\t"
  196.     "notl %%edi\n\t"
  197.     "andl $0x01010100,%%edi\n\t"
  198.     "jne " LF(5) "\n\t"
  199.  
  200.     "movl 8(%0),%%edi\n\t"
  201.     "xorl %%edx,%%edi\n\t"
  202.     "movl %%edi,%%ebx\n\t"
  203.     "addl $0xfefefeff,%%edi\n\t"
  204.     "jnc " LF(4) "\n\t"
  205.     "xorl %%ebx,%%edi\n\t"
  206.     "notl %%edi\n\t"
  207.     "andl $0x01010100,%%edi\n\t"
  208.     "jne " LF(4) "\n\t"
  209.  
  210.     "movl 12(%0),%%edi\n\t"
  211.     "xorl %%edx,%%edi\n\t"
  212.     "movl %%edi,%%ebx\n\t"
  213.     "addl $0xfefefeff,%%edi\n\t"
  214.     "jnc " LF(3) "\n\t"
  215.     "xorl %%ebx,%%edi\n\t"
  216.     "notl %%edi\n\t"
  217.     "andl $0x01010100,%%edi\n\t"
  218.     "je " LB(2) "\n"
  219.  
  220.     /* add missing source pointer increments */
  221. LL(3)    "\taddl $4,%0\n"
  222. LL(4)    "\taddl $4,%0\n"
  223. LL(5)    "\taddl $4,%0\n"
  224.  
  225.     /* Test for the matching byte.  %ebx contains a NULL char in that
  226.      * bytes which contain the searched character.  */
  227.     
  228. LL(6)    "\ttestb $0xff,%%bl\n\t"
  229.     "jz " LF(9) "\n\t"
  230.     "incl %0\n\t"
  231.     "testb $0xff,%%bh\n\t"
  232.     "jz " LF(9) "\n\t"
  233.     "incl %0\n\t"
  234.     "testl $0xff0000,%%ebx\n\t"
  235.     "jz " LF(9) "\n\t"
  236.     "incl %0\n\t"
  237.     
  238.     /* No further test needed because we know one of them matches.  */
  239.     "jmp " LF(9) "\n"
  240.  
  241. LL(7)    "\txorl %0,%0\n\t"
  242.     "jmp " LF(9) "\n"
  243.  
  244. LL(83)    "\taddl $4,%0\n"        /* correct counter */
  245. LL(82)    "\taddl $4,%0\n"
  246. LL(81)    "\taddl $4,%0\n"
  247.     
  248. LL(8)    "\tcmpl $4,%3\n\t"        /* rest < 4 bytes ? */
  249.     "jb " LF(89) "\n\t"        /* yes, than test byte by byte */
  250.  
  251.     "movl (%0),%%edi\n\t"
  252.     "xorl %%edx,%%edi\n\t"
  253.     "movl %%edi,%%ebx\n\t"
  254.     "addl $0xfefefeff,%%edi\n\t"
  255.     "jnc " LB(6) "\n\t"
  256.     "xorl %%ebx,%%edi\n\t"
  257.     "notl %%edi\n\t"
  258.     "andl $0x01010100,%%edi\n\t"
  259.     "jne " LB(6) "\n\t"
  260.     "addl $4,%0\n\t"
  261.  
  262.         "cmpl $8,%3\n\t"        /* rest < 8 bytes ? */
  263.         "jb " LF(89) "\n\t"        /* yes, than test byte by byte */
  264.  
  265.     "movl (%0),%%edi\n\t"
  266.     "xorl %%edx,%%edi\n\t"
  267.     "movl %%edi,%%ebx\n\t"
  268.     "addl $0xfefefeff,%%edi\n\t"
  269.     "jnc " LB(6) "\n\t"
  270.     "xorl %%ebx,%%edi\n\t"
  271.     "notl %%edi\n\t"
  272.     "andl $0x01010100,%%edi\n\t"
  273.     "jne " LB(6) "\n\t"
  274.     "addl $4,%0\n\t"
  275.  
  276.         "cmpl $12,%3\n\t"        /* rest < 12 bytes ? */
  277.         "jb " LF(89) "\n\t"        /* yes, than test byte by byte */
  278.  
  279.     "movl (%0),%%edi\n\t"
  280.     "xorl %%edx,%%edi\n\t"
  281.     "movl %%edi,%%ebx\n\t"
  282.     "addl $0xfefefeff,%%edi\n\t"
  283.     "jnc " LB(6) "\n\t"
  284.     "xorl %%ebx,%%edi\n\t"
  285.     "notl %%edi\n\t"
  286.     "andl $0x01010100,%%edi\n\t"
  287.     "jne " LB(6) "\n\t"
  288.     "addl $4,%0\n"
  289.             
  290.     /* Check the remaining bytes (less the four) one by one.  */
  291. LL(89)    "\tandl $3,%3\n\t"
  292.         "jz " LB(7) "\n\t"
  293.     "cmpb %%dl,(%0)\n\t"
  294.     "je " LF(9) "\n\t"
  295.     "incl %0\n\t"
  296.     "decl %3\n\t"
  297.     "je " LB(7) "\n\t"
  298.     "cmpb %%dl,(%0)\n\t"
  299.     "je " LF(9) "\n\t"
  300.     "incl %0\n\t"
  301.     "decl %3\n\t"
  302.     "je " LB(7) "\n\t"
  303.     "cmpb %%dl,(%0)\n\t"
  304.     "jne " LB(7) "\n"
  305. LL(9)
  306. #if defined(__PIC__) || defined(__pic__)
  307.     "\tpopl %%ebx"
  308.     :"=a" (__res):"d" (c),"0" (str),"c" (len):"di");
  309. #else
  310.     :"=a" (__res):"d" (c),"0" (str),"c" (len):"bx","di"); 
  311. #endif
  312. return __res;
  313. }
  314.  
  315. #else
  316. #include <sysdeps/generic/memchr.c>
  317. #endif
  318.