librols/findbytes.c

   1 /*
   2  * This file has been modified for the cdrkit suite.
   3  *
   4  * The behaviour and appearence of the program code below can differ to a major
   5  * extent from the version distributed by the original author(s).
   6  *
   7  * For details, see Changelog file distributed with the cdrkit package. If you
   8  * received this file from another source then ask the distributing person for
   9  * a log of modifications.
  10  *
  11  */
  12
  13 /* @(#)findbytes.c      1.2 03/06/15 Copyright 2000-2003 J. Schilling */
  14 /*
  15  *      Find a byte with specific value in memory.
  16  *
  17  *      Copyright (c) 2000-2003 J. Schilling
  18  *
  19  *      Based on a strlen() idea from Torbjorn Granlund (tege@sics.se) and
  20  *      Dan Sahlin (dan@sics.se) and the memchr() suggestion
  21  *      from Dick Karpinski (dick@cca.ucsf.edu).
  22  */
  23 /*
  24  * This program is free software; you can redistribute it and/or modify
  25  * it under the terms of the GNU General Public License version 2
  26  * as published by the Free Software Foundation.
  27  *
  28  * This program is distributed in the hope that it will be useful,
  29  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  30  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  31  * GNU General Public License for more details.
  32  *
  33  * You should have received a copy of the GNU General Public License along with
  34  * this program; see the file COPYING.  If not, write to the Free Software
  35  * Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  36  */
  37
  38 #include <mconfig.h>
  39 #include <stdxlib.h>
  40 #include <utypes.h>
  41 #include <align.h>
  42 #include <standard.h>
  43 #include <strdefs.h>
  44 #include <schily.h>
  45
  46 #ifdef  PROTOTYPES
  47 EXPORT char *
  48 findbytes(const void *vp, int cnt, char val)
  49 #else
  50 EXPORT char *
  51 findbytes(vp, cnt, val)
  52                 const   void    *vp;
  53         register        int     cnt;
  54                         char    val;
  55 #endif
  56 {
  57         register        Uchar   uval = (Uchar)val;
  58         register const  Uchar   *cp  = (Uchar *)vp;
  59         register const  Ulong   *lp;
  60         register        Ulong   lval;
  61         register        Ulong   lmask;
  62         register        Ulong   magic_mask;
  63
  64         /*
  65          * Test byte-wise until cp is properly aligned for a long pointer.
  66          */
  67         while (--cnt >= 0 && !laligned(cp)) {
  68                 if (*cp++ == uval)
  69                         return ((char *)--cp);
  70         }
  71         cnt++;
  72
  73         /*
  74          * The magic mask is a long word where all carry bits a clear.
  75          * This are bits 8, 16, 24 ...
  76          * In addition, the top bit is not set (e.g bit 31 or 63). The magic
  77          * mask will look this way:
  78          *
  79          * bits:  01111110 11111110 ... 11111110 11111111
  80          * bytes: AAAAAAAA BBBBBBBB ... CCCCCCCC DDDDDDDD
  81          *
  82          * If we add anything to this magic number, no carry bit will change if
  83          * it is the first carry bit left to a 0 byte. Adding anything != 0
  84          * to the magic number will just turn the carry bit left to the byte
  85          * but does not propagate any further.
  86          */
  87 #if SIZE_LONG == 4
  88         magic_mask = 0x7EFEFEFFL;
  89 #else
  90 #if SIZE_LONG == 8
  91         magic_mask = 0x7EFEFEFEFEFEFEFFL;
  92 #else
  93         /*
  94          * #error will not work for all compilers (e.g. sunos4)
  95          * The following line will abort compilation on all compilers
  96          * if none of the above is defines. And that's  what we want.
  97          */
  98         error   SIZE_LONG has unknown value
  99 #endif
 100 #endif
 101
 102         lmask = val & 0xFF;
 103         lmask |= lmask << 8;
 104         lmask |= lmask << 16;
 105 #if SIZE_LONG > 4
 106         lmask |= lmask << 32;
 107 #endif
 108 #if SIZE_LONG > 8
 109         error   SIZE_LONG has unknown value
 110 #endif
 111         for (lp = (const Ulong *)cp; cnt >= sizeof (long); cnt -= sizeof (long)) {
 112                 /*
 113                  * We are not looking for 0 bytes so we need to xor with the
 114                  * long mask of repeated bytes. If any of the bytes matches our
 115                  * wanted char, we will create a 0 byte in the current long.
 116                  * But how will we find if at least one byte in a long is zero?
 117                  *
 118                  * If we add 'magic_mask' and any of the holes in the magic
 119                  * mask do not change, we most likely found a 0 byte in the
 120                  * long word. It is only a most likely match because if bits
 121                  * 24..30 (ot bits 56..62) are 0 but bit 31 (or bit 63) is set
 122                  * we will believe that we found a match but there is none.
 123                  * This will happen if there is 0x80nnnnnn / 0x80nnnnnnnnnnnnnn
 124                  */
 125                 lval = (*lp++ ^ lmask);            /* create 0 byte on match */
 126                 lval = (lval + magic_mask) ^ ~lval; /* set bits unchanged by +*/
 127                 if ((lval & ~magic_mask) != 0) {   /* a magic hole was set   */
 128                         /*
 129                          * If any of the hole bits did not change by addition,
 130                          * we most likely had a match.
 131                          * If this was a correct match, find the matching byte.
 132                          */
 133                         cp = (const Uchar *)(lp - 1);
 134
 135                         if (cp[0] == uval)
 136                                 return ((char *)cp);
 137                         if (cp[1] == uval)
 138                                 return ((char *)&cp[1]);
 139                         if (cp[2] == uval)
 140                                 return ((char *)&cp[2]);
 141                         if (cp[3] == uval)
 142                                 return ((char *)&cp[3]);
 143 #if SIZE_LONG > 4
 144                         if (cp[4] == uval)
 145                                 return ((char *)&cp[4]);
 146                         if (cp[5] == uval)
 147                                 return ((char *)&cp[5]);
 148                         if (cp[6] == uval)
 149                                 return ((char *)&cp[6]);
 150                         if (cp[7] == uval)
 151                                 return ((char *)&cp[7]);
 152 #endif
 153 #if SIZE_LONG > 8
 154                         error   SIZE_LONG has unknown value
 155 #endif
 156                 }
 157         }
 158
 159         for (cp = (const Uchar *)lp; --cnt >= 0; ) {
 160                 if (*cp++ == uval)
 161                         return ((char *)--cp);
 162         }
 163         return ((char *)NULL);
 164 }