22

I need to write a repeating pattern to memory (e.g. 0x11223344), so that the whole memory looks like (in hex):

1122334411223344112233441122334411223344112233441122334411223344...

I can't figure out how to do it with memset() because it takes only a single byte, not 4 bytes.

Any ideas?

0

8 Answers 8

9

On OS X, one uses memset_pattern4( ) for this; I would expect other platforms to have similar APIs.

I don't know of a simple portable solution, other than just filling in the buffer with a loop (which is pretty darn simple).

1
  • 2
    I forgot I could use loop. Thanks for reminding. Trying it with loop now.
    – bodacydo
    Jul 27, 2010 at 15:18
6

If your pattern fits in a wchar_t, you can use wmemset() as you would have used memset().

6

Recursively copy the memory, using the area which you already filled as a template per iteration O(log(N)):

int fillLen = ...;
int blockSize = 4; // Size of your pattern

memmove(dest, srcPattern, blockSize);
char * start = dest;
char * current = dest + blockSize;
char * end = start + fillLen;
while(current + blockSize < end) {
    memmove(current, start, blockSize);
    current += blockSize;
    blockSize *= 2;
}
// fill the rest
memmove(current, start, (int)end-current);

What I mean with O(log(N)) is that the runtime will be much faster than if you fill the memory manually since memmove() usually uses special, hand-optimized assembler loops that are blazing fast.

1
  • 10
    It's O(log(n)) calls to memmove; the actual complexity is still O(n). Jul 27, 2010 at 15:39
5

An efficient way would be to cast the pointer to a pointer of the needed size in bytes (e.g. uint32_t for 4 bytes) and fill with integers. It's a little ugly though.

char buf[256] = { 0, };
uint32_t * p = (uint32_t *) buf, i;

for (i = 0; i < sizeof(buf) / sizeof(* p); i++) {
    p[i] = 0x11223344;
}

Not tested!

8
  • 7
    The one thing to be aware of is that buf might not satisfy the alignment requirements for a uint32_t on your platform. If buf is the result of a malloc, you don't need to worry about this, but if it's (say) passed in as an argument by code you don't control, you'll need to check the alignment before you write to it in this fashion, or else this will result in invalid accesses on some platforms. Jul 27, 2010 at 16:41
  • 1
    Another thing to watch for may be endianness, if this is run on a little endian computer and the filling and reading are done using types with different sizes (ie. filling with int but reading with char) Jul 27, 2010 at 19:32
  • 2
    This is not very efficient; using memmove() as in my example is much, much faster because it uses special assembler ops and hand-optimized code. Jul 28, 2010 at 9:50
  • 2
    @Aaron Digulla: that claim depends on a lot of things: for small buffers, for example, you're going to get slaughtered by function call overhead making repeated small calls to memmove( ). For "typical" buffers, your solution will probably be faster on most platforms with a well-optimized library, but for truly huge buffers, your solution will asymptotically take twice as many page faults and be very nearly 2x slower on most platforms. Jul 28, 2010 at 15:59
  • 3
    As far as I can tell the code contains UB in general case (not this snippet alone - other then before mentioned alignment) - the buf can be accessed as something else then char or uint32_t violating strict pointer aliasing rule - so if OP wanted to fill array of floats (s)he would run into UB. Oct 28, 2014 at 17:56
2

Well, the normal method of doing that is to manually setup the first four bytes, and then memcpy(ptr+4, ptr, len -4)

This copies the first four bytes into the second four bytes, then copies the second four bytes into the third, and so on.

Note, that this "usually" works, but is not guarenteed to, depending on your CPU architecture, and your C run-time library.

10
  • 7
    The behavior of memcpy is undefined if the source and destination buffers overlap. This will probably work on some platforms, but it will certainly not work on many others. Jul 27, 2010 at 15:18
  • 1
    This will overwrite the first four bytes with whatever is in the second four bytes. Further, memcpy should not be used with overlapping ranges.
    – bstpierre
    Jul 27, 2010 at 15:20
  • Are you commenting on my original or editted message. memcpy is (dest, src, len), which I have correct now. (I had it backward initially, but I though I had it fixed before your comment) Jul 27, 2010 at 15:39
  • I was commenting on the original -- see that you fixed the order now. (I'd remove the downvote but you'd need to edit to unlock it)
    – bstpierre
    Jul 27, 2010 at 16:40
  • 2
    IF you are just doing this for 4 bytes, you'd be better off speed wise with a straight *iPtr++ = dwordValue than a call to memcpy. memcpy is only faster once you get above N bytes. N being more than 4. Can't remember the value, but did some tests on it a few years back. Jul 28, 2010 at 10:36
2

Standard C library has no such function. But memset is usually implemented as an unrolled loop to minimize branching and condition checking:

static INLINE void memset4(uint32_t *RESTRICT p, uint32_t val, int len) {
  uint32_t *end = p + (len&~0x1f); //round down to nearest multiple of 32
  while (p != end) { //copy 32 times
    p[ 0] = val;
    p[ 1] = val;
    p[ 2] = val;
    p[ 3] = val;
    p[ 4] = val;
    p[ 5] = val;
    p[ 6] = val;
    p[ 7] = val;
    p[ 8] = val;
    p[ 9] = val;
    p[10] = val;
    p[11] = val;
    p[12] = val;
    p[13] = val;
    p[14] = val;
    p[15] = val;
    p[16] = val;
    p[17] = val;
    p[18] = val;
    p[19] = val;
    p[20] = val;
    p[21] = val;
    p[22] = val;
    p[23] = val;
    p[24] = val;
    p[25] = val;
    p[26] = val;
    p[27] = val;
    p[28] = val;
    p[29] = val;
    p[30] = val;
    p[31] = val;
    p += 32;
  }
  end += len&0x1f; //remained
  while (p != end) *p++ = val; //copy remaining bytes
}

Good compiler will likely use some CPU specific instructions to optimize it further (like i.e. use SSE 128-bit store), but even without optimizations, it should be as fast as a library memset, because such simple loops are memory access bound.

2

You could set up the sequence somewhere then copy it using memcpy() to where you need it.

1
  • memset can store only single-byte patterns, not a 4-byte int like that
    – phuclv
    Jul 31, 2021 at 2:00
0

I was thinking about this today when I had to duplicate a complex scalar across a memory aligned array in order to use Volk to perform SIMD multiplication. I see the solutions above but I don't know enough about compilers to say what will and won't be optimized. I plan to benchmark a few of these suggestions, but the solution that occurred to me is:

inline void duplicate_32fc(lv_32fc_t *out, lv_32fc_t in, int size) {

    int n = 1;
    int last_n;

    if (n < 1)
        return;

    //Copy the first one
    out[0] = in;

    //Double the size of the copy for each copy
    while (n*2 <= size) {
        memcpy(&out[n], out, n * sizeof(lv_32fc_t));
        last_n = n;
        n = n * 2;
    }

    //Copy the tail
    if (last_n < size) {
        memcpy(&out[last_n], out, (size - last_n) * sizeof(lv_32fc_t));
    }
}

Each iteration copies all of the previous copies to the new space so I think it is O(log(n)), no?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.