Skip to main content
gamedev.net
🔒 Locked

comparing memory buffers

Started by Simage 4 replies 500+ views
Original Post
Simage
Simage
ok.. I know of memcmp in libc, but I dont THINK it does what I want. what I want is some way of finding the number of bytes that differ between the two blocks for example comparing the strings "hello world" and "Hello World" should return 2, I have created a solution, I''m just not certain that its the optimal solution, its a mess but here it is 
  
int memdiff(void * buf1,void *buf2,int n)
{
	int n_int,n_short,n_char,n_diff,r,i,j,k,index;
	void *cur1,*cur2;
	
	n_diff=0;
	cur1=buf1;
	cur2=buf2;
	
	//divide the number of bytes to compare by the size of int

	n_int=n/sizeof(int);
	//use mod to get the remainder

	r=n%sizeof(int);
	//get the number of shorts remaining

	n_short=r/sizeof(short);
	r=r%sizeof(short);
	//get the number of chars remaining

	n_char=r/sizeof(char);
	r=r%sizeof(char);
	
	//test as many ints as we can

	for(i=0;i<n_int;i++)
	{
	//cast to int, if XORing the two ints is NOT 0 we test the 

	//upper and lower short if those are still different we then 

	//test upper and lower chars of the given short

		if (*(int*)cur1^*(int*)cur2)
		{
			for(j=0;j<(sizeof(int)/sizeof(short));j++)
			{
				if(((short*)cur1)[j]^((short*)cur2)[j])
				{
					for(k=0;k<(sizeof(short)/sizeof(char));k++)
					{
						index=(sizeof(short)/sizeof(char))*j+k;
						if(((char*)cur1)[index]^((char*)cur2)[index])
							n_diff++;
					}
				}
			}
		}
		
		cur1=((int*)cur1)++;
		cur2=((int*)cur2)++;
	}
	//test as many shorts as there are left

	for(i=0;i<n_short;i++)
	{
		if(*(short*)cur1^*(short*)cur2)
		
		for(j=0;j<(sizeof(short)/sizeof(char));j++)
			if(((char*)cur1)[j]^((char*)cur2)[j])
				n_diff++;
		
		cur1=((short*)cur1)++;
		cur2=((short*)cur2)++;
	}

	//test as many chars as there are left

	for(i=0;i<n_char;i++)
	{
		if(*(char*)cur1^*(char*)cur2)
			n_diff++;
			
		cur1=((char*)cur1)++;
		cur2=((char*)cur2)++;
	}
	
	return(n_diff);
}
the good news is that it hasn''t crashed yet. other than that, I''m not sure if XOR or == is more efficient
Zipster
Zipster
There are a few problems with your method. You don't know how big the data type being passed is, so you can't compare using a type as big as int. Take your string comparison example. Each character is only a single byte, yet if you try to compare the string using integers, it will compare every four bytes at once, and you could be missing differences that appear within those four-byte segments because they are included into a single integer check.

Ultimately, it comes down to how large a "disparity" is to you. Is it a single byte? A short? An integer? The size matters, unless you want to keep it at the smallest type, a char. But it's vary data-dependent. If you're trying to compare a list of integers, you want to check at the integer size, if you're checking a list of shorts, you want to check at the short size, etc.

If you don't want to get stuck using byte-size all the time, either you add an extra parameter telling you the size of the data, or you take it a step up and do it the C++ way, templating the function and using comparison operators instead of XOR on the raw data. This allows you to pass classes that have overloaded comparison operators as well.

Something along the lines of:

      
template<typename T>
int CompareMemory(const T* l1, const T* l2, size_t n)
{
   int differences = 0;

   for(int i = 0; i < n; ++i)
   {
      if(l1[i] != l2[i])
         ++differences;
   }

   return differences;
}


[edited by - Zipster on January 14, 2003 2:35:29 AM]
Simage
Simage
k... I''m not sure I see the problem you mention in mine, the first section of code goes thru and sees howmany ints we can create from the buffer how many shorts and how many individual chars and then does the comparison, in this particular instance the disparity I''m interested in is the number of bytes that differ, I dunno, maybe you see something in my code that I''m missing
Zipster
Zipster
Ah, sorry, my mistake. Misread the code

Your method looks alright, hehe. It depends though on what type of data you are going to be using it on. Your algorithm has the potential to cut the number of checks by 75%, but that''s only if the integers as a whole are equal. Once you discover a disparity, however, it can degenerate into 7 total checks for every 4 bytes as opposed to one.

String data can be vary unpredicable, and unless certain letters are going to be in certain patterns at similar locations in both strings, then your algorithm might start to degenerate as it has to check deep-down into the integer. A straight char-char test might be better.
Chozo
Chozo
This is what I'd do:


  
int memdiff(unsigned char* a1, size_t s1, unsigned char* a2, size_t s2)
{
    const int smallest = min(s1, s2);

    int count = 0;
    for(int i=0; i<smallest; ++i)
        if(a1[i] != a2[i])
            ++count;
    return count + (max(s1, s2) - smallest);
}


Then call it like this:


  
int a1[] = { 1, 2, 3, 4, 5 };
std::cout << "Difference is: " << memdiff(reinterpret_cast<unsigned char*>(a1), 5 * sizeof(int), reinterpret_cast<unsigned char*>(argv[1]), strlen(argv[1])) << std::endl;


That way it compares buffers of different lengths and types and only cares about the number of bytes that are different (since IIRC sizeof(unsigned char) is the only standard type size). It is costly to do the casting and total byte calculations in the call, however.

[edited by - Chozo on January 14, 2003 3:49:12 PM]
Simage
Simage
yeah... templates are nice, unfortunately C doesn''t have em :-/, and I''m trying to restrict myself to C on this project. the reason I cast to int and short is to reduce the number of calls in the average case, worst case, it actually gets worse than an char by char comparison, best case I only do 1/4 the comparisons, right now I''m just using it to compare two memory buffers ( actually influence maps) to determine if they''ve changed between iterations. another question, is XOR more expensive than == or !=or not??? I can''t decide, part of me says that its a basic logical operator, should be one cycle, but the same should be true of ==, and != is just a different opcode if I remember my x86 assembler right.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.