Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #3478 > unrolled thread

memmem()

Back to article view | Back to comp.lang.c

Contents

  memmem() barcaroller <barcaroller@music.net> - 2011-05-07 22:53 -0400
    Re: memmem() "Bill Cunningham" <nospam@nspam.invalid> - 2011-05-08 02:33 -0400
    Re: memmem() puppi <fabricio.puppi@gmail.com> - 2011-05-08 00:11 -0700
      Re: memmem() "Bill Cunningham" <nospam@nspam.invalid> - 2011-05-08 04:36 -0400
      Re: memmem() James Kuyper <jameskuyper@verizon.net> - 2011-05-08 09:33 -0400
        Re: memmem() barcaroller <barcaroller@music.net> - 2011-05-08 10:48 -0400
      Re: memmem() barcaroller <barcaroller@gmail.com> - 2011-05-08 10:46 -0400
        Re: memmem() Angel <angel+news@spamcop.net> - 2011-05-08 15:56 +0000
          Re: memmem() barcaroller <barcaroller@music.net> - 2011-05-08 12:03 -0400
            Re: memmem() puppi <fabricio.puppi@gmail.com> - 2011-05-09 04:58 -0700
              Re: memmem() Keith Thompson <kst-u@mib.org> - 2011-05-09 08:45 -0700
        Re: memmem() puppi <fabricio.puppi@gmail.com> - 2011-05-09 04:47 -0700
    Re: memmem() blp@cs.stanford.edu (Ben Pfaff) - 2011-05-09 09:45 -0700
      Re: memmem() Nobody <nobody@nowhere.com> - 2011-05-10 07:19 +0100
        Re: memmem() Dr Nick <3-nospam@temporary-address.org.uk> - 2011-05-10 07:35 +0100
          Re: memmem() pete <pfiland@mindspring.com> - 2011-05-10 04:27 -0400
        Re: memmem() Ben Pfaff <blp@cs.stanford.edu> - 2011-05-10 07:16 -0700
          Re: memmem() Nobody <nobody@nowhere.com> - 2011-05-10 21:07 +0100

#3478 — memmem()

Does anyone know of a POSIX-equivalent for GNU's memmem(), which 
searches for a sequence of bytes within a larger block of memory?

[toc] | [next] | [standalone]

#3496

barcaroller wrote:
> Does anyone know of a POSIX-equivalent for GNU's memmem(), which
> searches for a sequence of bytes within a larger block of memory?

    I think you might want comp.unix.programmer

Bill

[toc] | [prev] | [next] | [standalone]

#3500

On May 7, 11:53 pm, barcaroller <barcarol...@music.net> wrote:
> Does anyone know of a POSIX-equivalent for GNU's memmem(), which
> searches for a sequence of bytes within a larger block of memory?

There is strstr(). It's defined by C89 and C99. The essential
difference between strstr() and memmem() is that strstr() assumes that
the "haystack" and the "needle" are null-byte ended, while in memmem()
the lengths are specified. Hence it's not quite an equivalence (but
unless you are reading raw binary data, it's close to that).

[toc] | [prev] | [next] | [standalone]

#3509

puppi wrote:
> On May 7, 11:53 pm, barcaroller <barcarol...@music.net> wrote:

> There is strstr(). It's defined by C89 and C99. The essential
> difference between strstr() and memmem() is that strstr() assumes that
> the "haystack" and the "needle" are null-byte ended, while in memmem()
> the lengths are specified. Hence it's not quite an equivalence (but
> unless you are reading raw binary data, it's close to that).

    Strstr() interesting choice I'll look at that. But he's asking about 
POSIX and I wouldn't know how to answer myself.

Bill

[toc] | [prev] | [next] | [standalone]

#3523

On 05/08/2011 03:11 AM, puppi wrote:
> On May 7, 11:53�pm, barcaroller <barcarol...@music.net> wrote:
>> Does anyone know of a POSIX-equivalent for GNU's memmem(), which
>> searches for a sequence of bytes within a larger block of memory?
> 
> There is strstr(). It's defined by C89 and C99. The essential
> difference between strstr() and memmem() is that strstr() assumes that
> the "haystack" and the "needle" are null-byte ended, while in memmem()
> the lengths are specified. Hence it's not quite an equivalence (but
> unless you are reading raw binary data, it's close to that).

I strongly suspect that the OP is not working with null-terminated data.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#3526

On 2011-05-08 09:33:28 -0400, James Kuyper said:

> I strongly suspect that the OP is not working with null-terminated data.

You are right.

[toc] | [prev] | [next] | [standalone]

#3525

On 2011-05-08 03:11:17 -0400, puppi said:

> There is strstr(). It's defined by C89 and C99. The essential
> difference between strstr() and memmem() is that strstr() assumes that
> the "haystack" and the "needle" are null-byte ended, while in memmem()
> the lengths are specified. Hence it's not quite an equivalence (but
> unless you are reading raw binary data, it's close to that).

Thank your for your response.  I am in fact dealing with raw binary 
data.  I am a bit suprised that strstr() is in C99, but no similar 
function for binary data.  I could roll my own, but I like GNU's 
optimizations in memmem (making use of word boundaries etc).

[toc] | [prev] | [next] | [standalone]

#3531

On 2011-05-08, barcaroller <barcaroller@gmail.com> wrote:
> On 2011-05-08 03:11:17 -0400, puppi said:
>
>> There is strstr(). It's defined by C89 and C99. The essential
>> difference between strstr() and memmem() is that strstr() assumes that
>> the "haystack" and the "needle" are null-byte ended, while in memmem()
>> the lengths are specified. Hence it's not quite an equivalence (but
>> unless you are reading raw binary data, it's close to that).
>
> Thank your for your response.  I am in fact dealing with raw binary 
> data.  I am a bit suprised that strstr() is in C99, but no similar 
> function for binary data.  I could roll my own, but I like GNU's 
> optimizations in memmem (making use of word boundaries etc).

You might want to be careful with that, memmem() is broken in several
versions of libc.


-- 
The perfected state of a spam server is a smoking crater.
- The Crater Corollary to Rule #4

[toc] | [prev] | [next] | [standalone]

#3533

On 2011-05-08 11:56:23 -0400, Angel said:

> You might want to be careful with that, memmem() is broken in several
> versions of libc.

I know that it was broken at some point in the past (in fact, it says 
so in the manpage) but my understanding is that it has now been fixed.  
If you know otherwise, please let me know (or point me to a source).

[toc] | [prev] | [next] | [standalone]

#3603

On May 8, 1:03 pm, barcaroller <barcarol...@music.net> wrote:
> On 2011-05-08 11:56:23 -0400, Angel said:
>
> > You might want to be careful with that, memmem() is broken in several
> > versions of libc.
>
> I know that it was broken at some point in the past (in fact, it says
> so in the manpage) but my understanding is that it has now been fixed.  
> If you know otherwise, please let me know (or point me to a source).

You could also bitwise AND with 0x01 each byte of the sequences to be
compared, filtering out the low bits (and preferably packing them 8 by
8 in a single byte), then bitwise OR the original sequences with 0x01,
put a sentinel 0x00 at the end and use 2 strstr()s (or 1 strstr() and
1 plain equality test for each possible match). Of course it wouldn't
be as efficient, but at least it's as alternative.

[toc] | [prev] | [next] | [standalone]

#3615

puppi <fabricio.puppi@gmail.com> writes:
> On May 8, 1:03 pm, barcaroller <barcarol...@music.net> wrote:
>> On 2011-05-08 11:56:23 -0400, Angel said:
>>
>> > You might want to be careful with that, memmem() is broken in several
>> > versions of libc.
>>
>> I know that it was broken at some point in the past (in fact, it says
>> so in the manpage) but my understanding is that it has now been fixed.  
>> If you know otherwise, please let me know (or point me to a source).
>
> You could also bitwise AND with 0x01 each byte of the sequences to be
> compared, filtering out the low bits (and preferably packing them 8 by
> 8 in a single byte), then bitwise OR the original sequences with 0x01,
> put a sentinel 0x00 at the end and use 2 strstr()s (or 1 strstr() and
> 1 plain equality test for each possible match). Of course it wouldn't
> be as efficient, but at least it's as alternative.

Or you could use memcmp() in a loop.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#3602

On May 8, 11:46 am, barcaroller <barcarol...@gmail.com> wrote:
> On 2011-05-08 03:11:17 -0400, puppi said:
>
> > There is strstr(). It's defined by C89 and C99. The essential
> > difference between strstr() and memmem() is that strstr() assumes that
> > the "haystack" and the "needle" are null-byte ended, while in memmem()
> > the lengths are specified. Hence it's not quite an equivalence (but
> > unless you are reading raw binary data, it's close to that).
>
> Thank your for your response.  I am in fact dealing with raw binary
> data.  I am a bit suprised that strstr() is in C99, but no similar
> function for binary data.  I could roll my own, but I like GNU's
> optimizations in memmem (making use of word boundaries etc).

If your project is open-source, you can always simply use glibc's
implementation in a "copy-paste" fashion. Just be sure to account for
the legal technicalities in doing that.

[toc] | [prev] | [next] | [standalone]

#3620

barcaroller <barcaroller@music.net> writes:

> Does anyone know of a POSIX-equivalent for GNU's memmem(), which
> searches for a sequence of bytes within a larger block of memory?

It's not hard to write such a function.  Have you considered
doing that?
-- 
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}

[toc] | [prev] | [next] | [standalone]

#3664

On Mon, 09 May 2011 09:45:26 -0700, Ben Pfaff wrote:

>> Does anyone know of a POSIX-equivalent for GNU's memmem(), which
>> searches for a sequence of bytes within a larger block of memory?
> 
> It's not hard to write such a function.  Have you considered
> doing that?

It's not hard to write something which works, but it's easy to end up with
something which is far less efficient than it needs to be.

Hint to OP: look up the Boyer–Moore algorithm.

[toc] | [prev] | [next] | [standalone]

#3665

Nobody <nobody@nowhere.com> writes:

> On Mon, 09 May 2011 09:45:26 -0700, Ben Pfaff wrote:
>
>>> Does anyone know of a POSIX-equivalent for GNU's memmem(), which
>>> searches for a sequence of bytes within a larger block of memory?
>> 
>> It's not hard to write such a function.  Have you considered
>> doing that?
>
> It's not hard to write something which works, but it's easy to end up with
> something which is far less efficient than it needs to be.

Do you need it now, or do you want to make sure your code is portable.
If you want it now then I think you do either have to write your own or
use GNU's if the license is compatible.

If you're "just" worried about the future, what I do is (putting the
relevant code for all such functions together in one header/source file
pair) do something like this:

use something external to C to check if the function is available
(autoconf in my case).
if it is, I conditionally #define another name, comfortably in user
namespace, for it
#define search_memory memmem
if not, #error

then a future porter "just" needs to put the prototype in the header
file where the #error is, and write the code in the C file and there he
is.

I've got "caseless_strcmp" in my code, built on strcasecmp (and, on
porting to Windows, stricmp)

Thusly:

#ifdef HAVE_STRCASECMP
  #define caseless_strcmp(x,y) strcasecmp(x,y)
#else
  #ifdef HAVE_STRICMP
    #define caseless_strcmp(x,y) stricmp(x,y)
  #else
    #error Need to implement caseless string comparison here
  #endif
#endif

So I push the problem off for the time being, avoid writing code I don't
need to, but don't leave anyone porting it in the future to a non GNU
system foundering with no idea of what has gone wrong.
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

[toc] | [prev] | [next] | [standalone]

#3672

Dr Nick wrote:
 
> I've got "caseless_strcmp" in my code, built on strcasecmp (and, on
> porting to Windows, stricmp)
> 
> Thusly:
> 
> #ifdef HAVE_STRCASECMP
>   #define caseless_strcmp(x,y) strcasecmp(x,y)
> #else
>   #ifdef HAVE_STRICMP
>     #define caseless_strcmp(x,y) stricmp(x,y)
>   #else
>     #error Need to implement caseless string comparison here
>   #endif
> #endif
> 
> So I push the problem off for the time being,
> avoid writing code I don't
> need to, but don't leave anyone porting it in the future to a non GNU
> system foundering with no idea of what has gone wrong.


This is what I have so far:

#include <ctype.h>

int str_ccmp(const char *s1, const char *s2)
{
    for (;;) {
        if (*s1 != *s2) {
            const int c1 = tolower(*(const unsigned char *)s1);
            const int c2 = tolower(*(const unsigned char *)s2);

            if (c2 != c1) {
                return c2 > c1 ? -1 : 1;
            }
        } else {
            if (*s1 == '\0') {
                return 0;
            }
        }
        ++s1;
        ++s2;
    }
}

I'm still not sure whether it's better to use
    tolower(*(const unsigned char *)s1)
or
    tolower((unsigned char)*s1)

-- 
pete

[toc] | [prev] | [next] | [standalone]

#3681

Nobody <nobody@nowhere.com> writes:

> On Mon, 09 May 2011 09:45:26 -0700, Ben Pfaff wrote:
>
>>> Does anyone know of a POSIX-equivalent for GNU's memmem(), which
>>> searches for a sequence of bytes within a larger block of memory?
>> 
>> It's not hard to write such a function.  Have you considered
>> doing that?
>
> It's not hard to write something which works, but it's easy to end up with
> something which is far less efficient than it needs to be.

It depends on what you are searching for.  If it's fairly short,
then simple and obvious algorithms are just fine.
-- 
Ben Pfaff 
http://benpfaff.org

[toc] | [prev] | [next] | [standalone]

#3692

On Tue, 10 May 2011 07:16:42 -0700, Ben Pfaff wrote:

>> It's not hard to write something which works, but it's easy to end up with
>> something which is far less efficient than it needs to be.
> 
> It depends on what you are searching for.  If it's fairly short,
> then simple and obvious algorithms are just fine.

True enough. In fact, that's probably what memmem() uses.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web