filling memory with a pattern
-
Sorry for the cross post, but I'm beginning to feel like maybe I put this in the wrong forum to begin with. Over here I'm sure I'd have gotten responses by now. http://www.codeproject.com/script/comments/forums.asp?forumid=326859&df=100&mpp=50&select=2265207#xx2265207xx[^]
-
Sorry for the cross post, but I'm beginning to feel like maybe I put this in the wrong forum to begin with. Over here I'm sure I'd have gotten responses by now. http://www.codeproject.com/script/comments/forums.asp?forumid=326859&df=100&mpp=50&select=2265207#xx2265207xx[^]
What are you wanting such that
memset()does not work?
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
-
What are you wanting such that
memset()does not work?
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
http://www.cplusplus.com/reference/clibrary/cstring/memset.html[^] I'm looking to fill memory with a pattern, not with a single byte. Like I said, I have a <= 2*log(n) solution, but it still seems that this should be a standard thing in text books or something. I just can't seem find it. David
-
http://www.cplusplus.com/reference/clibrary/cstring/memset.html[^] I'm looking to fill memory with a pattern, not with a single byte. Like I said, I have a <= 2*log(n) solution, but it still seems that this should be a standard thing in text books or something. I just can't seem find it. David
DQNOK wrote:
I'm looking to fill memory with a pattern...
I guess it all depends on what the pattern is. Anything beyond a single byte becomes application-specific, so I would think a nonexistent function would be normal.
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
-
DQNOK wrote:
I'm looking to fill memory with a pattern...
I guess it all depends on what the pattern is. Anything beyond a single byte becomes application-specific, so I would think a nonexistent function would be normal.
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
OK. Thanks for your thoughts and replies. My algorithm is not application specific (that I can see). I'll go ahead and post it here in case anyone else can benefit from it. It looks long, but it's mostly comments. The test case at the end works fine for me when I compile and run it with Digital Mars C++.
//author: David Qualls //date: Sept 2007 #include <string.h> void memoryfill( void* target, char* pattern, size_t ptrnlen, size_t numRepeats ) { char* trgt = (char*)target; //for ease in pointer manipulation. if( 0 == numRepeats ) { ; // do nothing! } else if( 1 == ptrnlen ) { memset(target, *pattern, numRepeats); } else { // The naive approach here would be: // while( numRepeats-- > 0 ) // { memcpy(target, pattern, ptrnlen); // (char*)target += ptrnlen; // } // But this is O(numRepeats). Very ineffecient for large numRepeats. // Use a binary algorithm instead. This one uses between log(numRepeats) // and 2*log(numRepeats) calls to memcpy(); a maximum of 64 calls to // memcpy()for 32-bit size_t's : versus up to 4-billion calls to memcpy(). // First, fill target up to the highest "bit" of repeatCount. log(n) loops. memcpy(trgt, pattern, ptrnlen); //begin by putting one copy into target. int snglbit=1; //number of copies in target. Always a power of 2. int thisCnt = numRepeats >> 1; //one bit of repeatCount has already been taken care of. while( thisCnt > 0 ) //until all bits have been shifted off. { memcpy(trgt+ptrnlen*snglbit, trgt, ptrnlen*snglbit); //now double the amount in target. snglbit <<= 1; //doubles the value of snglbit. thisCnt >>= 1; //halves the value of thisCnt. } // snglbit now matches the most significant bit of repeatCount. char* endptr = trgt + ptrnlen*snglbit; //where the next memcpy target is. while( (snglbit >>= 1) > 0 ) //for each lower bit within numRepeats, { if( snglbit & numRepeats ) //if this bit is ON within numRepeats, { memcpy(endptr, trgt, ptrnlen*snglbit); endptr += ptrnlen*snglbit; } } } return; } #include <stdio.h> int main() { char buf[1024]; memset(buf, 0, 1024); //insure null terminator(s) memoryfill( buf, "Hello World_", 12, 19 ); printf("\n%s", buf); } -
OK. Thanks for your thoughts and replies. My algorithm is not application specific (that I can see). I'll go ahead and post it here in case anyone else can benefit from it. It looks long, but it's mostly comments. The test case at the end works fine for me when I compile and run it with Digital Mars C++.
//author: David Qualls //date: Sept 2007 #include <string.h> void memoryfill( void* target, char* pattern, size_t ptrnlen, size_t numRepeats ) { char* trgt = (char*)target; //for ease in pointer manipulation. if( 0 == numRepeats ) { ; // do nothing! } else if( 1 == ptrnlen ) { memset(target, *pattern, numRepeats); } else { // The naive approach here would be: // while( numRepeats-- > 0 ) // { memcpy(target, pattern, ptrnlen); // (char*)target += ptrnlen; // } // But this is O(numRepeats). Very ineffecient for large numRepeats. // Use a binary algorithm instead. This one uses between log(numRepeats) // and 2*log(numRepeats) calls to memcpy(); a maximum of 64 calls to // memcpy()for 32-bit size_t's : versus up to 4-billion calls to memcpy(). // First, fill target up to the highest "bit" of repeatCount. log(n) loops. memcpy(trgt, pattern, ptrnlen); //begin by putting one copy into target. int snglbit=1; //number of copies in target. Always a power of 2. int thisCnt = numRepeats >> 1; //one bit of repeatCount has already been taken care of. while( thisCnt > 0 ) //until all bits have been shifted off. { memcpy(trgt+ptrnlen*snglbit, trgt, ptrnlen*snglbit); //now double the amount in target. snglbit <<= 1; //doubles the value of snglbit. thisCnt >>= 1; //halves the value of thisCnt. } // snglbit now matches the most significant bit of repeatCount. char* endptr = trgt + ptrnlen*snglbit; //where the next memcpy target is. while( (snglbit >>= 1) > 0 ) //for each lower bit within numRepeats, { if( snglbit & numRepeats ) //if this bit is ON within numRepeats, { memcpy(endptr, trgt, ptrnlen*snglbit); endptr += ptrnlen*snglbit; } } } return; } #include <stdio.h> int main() { char buf[1024]; memset(buf, 0, 1024); //insure null terminator(s) memoryfill( buf, "Hello World_", 12, 19 ); printf("\n%s", buf); }This reminds me of how I create large test files. For example, if I wanted a file with 100,000 characters, I would open Notepad, type 10 characters, copy those and paste nine times (yielding 100 characters). Then I would copy those 100 characters and copy those nine times (yielding 1000 characters). I would repeat this two more times to get the final result, all from an initial 10 typed characters.
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
-
This reminds me of how I create large test files. For example, if I wanted a file with 100,000 characters, I would open Notepad, type 10 characters, copy those and paste nine times (yielding 100 characters). Then I would copy those 100 characters and copy those nine times (yielding 1000 characters). I would repeat this two more times to get the final result, all from an initial 10 typed characters.
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
-
Sorry for the cross post, but I'm beginning to feel like maybe I put this in the wrong forum to begin with. Over here I'm sure I'd have gotten responses by now. http://www.codeproject.com/script/comments/forums.asp?forumid=326859&df=100&mpp=50&select=2265207#xx2265207xx[^]
Well, probably not the answer you were looking for but if you really want to do this in the most efficient way possible you are going to need to use assembly language and take advantage of the chip specific instructions. I have done this before for some built-in-self-tests for embedded hardware where the timing requirements were that all of the tests had to complete in under 1 clock cycle.
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
-
Well, probably not the answer you were looking for but if you really want to do this in the most efficient way possible you are going to need to use assembly language and take advantage of the chip specific instructions. I have done this before for some built-in-self-tests for embedded hardware where the timing requirements were that all of the tests had to complete in under 1 clock cycle.
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
Thanks for the response. I'm sure you are correct if efficiency is the driving force. I figured the best approach would be one that does a lot of what memcpy() already does: deals with all possible alignment issues, and once those are out of the way, uses the fastest native size (2, 4, or 8 bytes, depending on the processor) to do the guts of the transfer. Clearly, this is assembly language/processor specific kinds of stuff. Nevertheless, I had thought perhaps someone already had some good cross platform algorithm that would at least do the alignment stuff, then assume
intwas best for the rest of the transfer. My approach is pretty good, except that it forces repeated dealing with alignment issues on every single call to memcpy(). Fortunately, it calls memcpy() a max of 63 times. I haven't spent many hours pondering this, but it MIGHT be that there is just no way around repeatedly dealing with alignment issues. If this is the case, then perhaps my algorithm is already optimum. I really don't know. Thanks again for the response. David -
Thanks for the response. I'm sure you are correct if efficiency is the driving force. I figured the best approach would be one that does a lot of what memcpy() already does: deals with all possible alignment issues, and once those are out of the way, uses the fastest native size (2, 4, or 8 bytes, depending on the processor) to do the guts of the transfer. Clearly, this is assembly language/processor specific kinds of stuff. Nevertheless, I had thought perhaps someone already had some good cross platform algorithm that would at least do the alignment stuff, then assume
intwas best for the rest of the transfer. My approach is pretty good, except that it forces repeated dealing with alignment issues on every single call to memcpy(). Fortunately, it calls memcpy() a max of 63 times. I haven't spent many hours pondering this, but it MIGHT be that there is just no way around repeatedly dealing with alignment issues. If this is the case, then perhaps my algorithm is already optimum. I really don't know. Thanks again for the response. DavidYou might want to look for an open implementation of memcpy and then create your own version that does the same thing but excludes the alignment stuff, which you could then do once as a separate call. I don't know if the Rotor source code includes an implementation of memcpy for use on non-Windows systems, but it might be a place to start. (I know it does have other low-level C functions that have been reproduced, just not sure if memcpy is one of them.)
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
-
You might want to look for an open implementation of memcpy and then create your own version that does the same thing but excludes the alignment stuff, which you could then do once as a separate call. I don't know if the Rotor source code includes an implementation of memcpy for use on non-Windows systems, but it might be a place to start. (I know it does have other low-level C functions that have been reproduced, just not sure if memcpy is one of them.)
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
Interesting! Clever idea. I probably won't do it just because I already have a workable solution, and don't want to spend the kind of time it would require. I was really just fishing, assuming someone out there already had an optimum portable algorithm. For my application, the maximum numRepeats will only be on the order of a few hundred, so the looping won't be severe; for sure won't justify the amount of time I'd spend writing an optimum algorithm. See http://www.codeproject.com/tips/optimizationenemy.asp?df=100&forumid=683&mpp=50&select=2267125&msg=2267125[^] Thanks again. David
-
Interesting! Clever idea. I probably won't do it just because I already have a workable solution, and don't want to spend the kind of time it would require. I was really just fishing, assuming someone out there already had an optimum portable algorithm. For my application, the maximum numRepeats will only be on the order of a few hundred, so the looping won't be severe; for sure won't justify the amount of time I'd spend writing an optimum algorithm. See http://www.codeproject.com/tips/optimizationenemy.asp?df=100&forumid=683&mpp=50&select=2267125&msg=2267125[^] Thanks again. David
DQNOK wrote:
Interesting! Clever idea.
Thanks! I did a quick search and found the following implementation: http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/common/util/memcpy.c[^] However, I don't blame you for wanting to stick with the solution you already have...particularly if you are sure the maximum looping will be relatively small.
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
-
DQNOK wrote:
Interesting! Clever idea.
Thanks! I did a quick search and found the following implementation: http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/common/util/memcpy.c[^] However, I don't blame you for wanting to stick with the solution you already have...particularly if you are sure the maximum looping will be relatively small.
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]
I took a quick look at the source. It doesn't do any alignment; just the straight-forward
*(target++) = *(src++);kind of thing. I suppose they're relying on the compiler to recognize the pattern, and substitute the appropriate idiom for memory copy on the selected platform. I guess if the compiler is smart enough, that's a good; well, a *portable* way to do it... -
I took a quick look at the source. It doesn't do any alignment; just the straight-forward
*(target++) = *(src++);kind of thing. I suppose they're relying on the compiler to recognize the pattern, and substitute the appropriate idiom for memory copy on the selected platform. I guess if the compiler is smart enough, that's a good; well, a *portable* way to do it...Ahh...I didn't really look at the source other than to verify that it was actually a memcpy implementation. Oh well...
Scott.
—In just two days, tomorrow will be yesterday. [Forum Guidelines] [Articles] [Blog]