text / strings in C

[Simon]

Code: [Select]

void copy_array_to_array(uint8_t destination[], uint8_t destination_start, uint8_t source[], uint8_t source_start, uint8_t source_end ){

uint8_t destination_index = destination_start;
uint8_t source_index      = source_start;

while(source_index <= source_end){

destination[destination_index] = source[source_index];
destination_index++;
source_index++;
}

}

I know I have probably reinvented the wheel but I need the learning and mental exercise in making code up, works a treat.

[Jeroen3]

Code: [Select]

void copy_array_to_array(uint8_t destination[], uint8_t destination_start, uint8_t source[], uint8_t source_start, uint8_t source_end ){

uint8_t destination_index = destination_start;
uint8_t source_index      = source_start;

while(source_index <= source_end){

destination[destination_index] = source[source_index];
destination_index++;
source_index++;
}

}

I know I have probably reinvented the wheel but I need the learning and mental exercise in making code up, works a treat.

That is a very convoluted way of writing

Code: [Select]

memcpy(&destination[destination_start], &source[source_start], source_end-source_start);
But ok..

It looks like you just want to replace some part of a string with another string?
Attempting to display something.
Write up a printf format string that fits your display. Probably a character display I'm guessing.

Code: [Select]

printf("Text: % 5s.", "A"); // prints A right aligned of a 5 char block
printf("Text: %-5s.\n", "B"); // prints B left aligned of a 5 char block
Printf is magic.
Maybe not all the features are available in your toolchain, read the docs. These probably are.
This is the most luxury you're going to get, and you do not have to worry about memory access violation or forgotten null characters and getting gibberish on the screen.

[brucehoult]

Yea the K&R book on C says that pointers are faster. From what i can tell I need to use pointers anyway to bring the data into my function. I would have to put the strings into an array as nothing else will hold that sort of data.

K&R was written over 40 years ago. Compilers have improved slightly in that time.

Also ignore any advice about declaring variables as "register" as modern compilers simply ignore that and decide for themselves what will be in registers -- usually "everything" for typical (not huge) functions on a machine with 16 or 32 registers.

[brucehoult]

Code: [Select]

void copy_array_to_array(uint8_t destination[], uint8_t destination_start, uint8_t source[], uint8_t source_start, uint8_t source_end ){

uint8_t destination_index = destination_start;
uint8_t source_index      = source_start;

while(source_index <= source_end){

destination[destination_index] = source[source_index];
destination_index++;
source_index++;
}

}

I know I have probably reinvented the wheel but I need the learning and mental exercise in making code up, works a treat.

That's absolutely fine. I write loops and functions like this all the time, especially of the types of source and destination are different, in which case memcpy() won't help anyway. With at least -O1 optimization and small values of source_end-source_start this will be just as fast as memcpy anyway.

A few absolutely unimportant notes:

- unless you are actually on an 8 bit CPU such as AVR or PIC it would be better (more flexible and possibly a little more efficient) to have destination_start, source_start, source_end and *especially* source_index and destination_index as plain int. Then it will be ok for source[] and destination[] have more than 256 bytes, and work with offsets greater than 256 in them.

- source_index and destination_index are unnecessary but harmless. Arguably they serve to make the code slightly more readable, so it's fine, but as a matter of how C works it's absolutely fine to just use (and increment) source_start and destination_start. This won't propagate back the variables the caller uses. (It would in FORTRAN or ALGOL but those are ancient)

- I'd probably name source_end instead as source_last. Or change the comparison to < instead of <=. The name "source_end" makes me think it's as usual in C one-past-the-end. This would avoid a lot of doing "size-1" in the caller and fit most C programmer's expectations.

- with 5 function arguments you're getting close to the limit of what can be passed in registers on x86_64 (6) and past the limit on ARM32 (4). It's fine to exceed the limit but it just means more code in both the caller and the called function to copy the value to the stack and back.

[Simon]

Also ignore any advice about declaring variables as "register" as modern compilers simply ignore that and decide for themselves what will be in registers -- usually "everything" for typical (not huge) functions on a machine with 16 or 32 registers.

How to you mean? I have to set any pointer to a register as volatile or nothing happens and the code does not work.

[Simon]

That's absolutely fine. I write loops and functions like this all the time, especially of the types of source and destination are different, in which case memcpy() won't help anyway. With at least -O1 optimization and small values of source_end-source_start this will be just as fast as memcpy anyway.

A few absolutely unimportant notes:

- unless you are actually on an 8 bit CPU such as AVR or PIC it would be better (more flexible and possibly a little more efficient) to have destination_start, source_start, source_end and *especially* source_index and destination_index as plain int. Then it will be ok for source[] and destination[] have more than 256 bytes, and work with offsets greater than 256 in them.

- source_index and destination_index are unnecessary but harmless. Arguably they serve to make the code slightly more readable, so it's fine, but as a matter of how C works it's absolutely fine to just use (and increment) source_start and destination_start. This won't propagate back the variables the caller uses. (It would in FORTRAN or ALGOL but those are ancient)

- I'd probably name source_end instead as source_last. Or change the comparison to < instead of <=. The name "source_end" makes me think it's as usual in C one-past-the-end. This would avoid a lot of doing "size-1" in the caller and fit most C programmer's expectations.

- with 5 function arguments you're getting close to the limit of what can be passed in registers on x86_64 (6) and past the limit on ARM32 (4). It's fine to exceed the limit but it just means more code in both the caller and the called function to copy the value to the stack and back.

It's for ARM at the moment. For my intended use I can't see me needing more than 256 elements.

Not sure what I can do to reduce the amount of elements, the only way to get it to 4 is to have it just copy all of the source array, this is probably how i would use it most of the time.

[IanB]

Code: [Select]

void copy_array_to_array(uint8_t destination[], uint8_t destination_start, uint8_t source[], uint8_t source_start, uint8_t source_end ){

uint8_t destination_index = destination_start;
uint8_t source_index      = source_start;

while(source_index <= source_end){

destination[destination_index] = source[source_index];
destination_index++;
source_index++;
}

}

I know I have probably reinvented the wheel but I need the learning and mental exercise in making code up, works a treat.

It is by the way not necessary to create new variables for destination_index and source_index, since you already have destination_start and source_start variables available and ready to use. You can just increment them from their starting values in the loop.

[IanB]

Not sure what I can do to reduce the amount of elements, the only way to get it to 4 is to have it just copy all of the source array, this is probably how i would use it most of the time.

You don't really need a function for this since the code is so compact:

Code: [Select]

/* copy 8 elements from position 0 in array text to position 10 in array buf:
   int i, j, n;
   for (i = 10, j = 0, n = 8; n > 0; ++i, ++j, --n) {
       buf[i] = text[j];
   }


[Simon]

It's something that will be reused often. Potentially to save RAM I can create a number of constant strings that are different display options that get copied to the display RAM buffer with the numbers of variables inserted into the array in the appropriate places.

[Nominal Animal]

If you are using a GCC-derived compiler, using the __builtin_memcpy() should yield optimal code for each processor; these is provided by gcc, not by any library per se. If you want your exact interface, then

Code: [Select]

static inline void copy_array_to_array(uint8_t destination[], int destination_start, uint8_t source[], int source_start, int source_end)
{
    __builtin_memcpy(destination + destination_start, source + source_start, (source_end - source_start + 1) * sizeof destination[0]);
}
The useful points to realize here are

• GCC provides a number of built-ins that are normally provided by the C library; these are optimized for the target architecture.  The ones relevant for microcontrollers include strlen(), strchr(), strrchr(), strcmp(), memset(), memcpy(), and memchr().
• When stuff is an array or a pointer, and index is an integer, (stuff + index) == &(stuff[index]).
• sizeof stuff[0] evaluates to the size of the elements in stuff, without dereferencing it; the compiler computes the size at compile time.
  I recommend omitting the parentheses when possible, to remind us humans that sizeof is an operator, not a function.
  (For a type, I recommend sizeof (type), with an extra space in between.)

Whether these are relevant for Simon, I'm not sure.  Typically, the amount of time spent in copying stuff around in memory is neglible on microcontrollers.

[Simon]

Well as I said it's good code practicing for me. There is learning the mechanics of C and there is actually devising ways of using it to solve problems which is what this was more of an exercise in. In the time it takes me to look this stuff up I can write it myself and know that i am familiar with how it works.

[Yansi]

That's absolutely fine. I write loops and functions like this all the time, especially of the types of source and destination are different, in which case memcpy() won't help anyway. With at least -O1 optimization and small values of source_end-source_start this will be just as fast as memcpy anyway.

A few absolutely unimportant notes:

- unless you are actually on an 8 bit CPU such as AVR or PIC it would be better (more flexible and possibly a little more efficient) to have destination_start, source_start, source_end and *especially* source_index and destination_index as plain int. Then it will be ok for source[] and destination[] have more than 256 bytes, and work with offsets greater than 256 in them.

- source_index and destination_index are unnecessary but harmless. Arguably they serve to make the code slightly more readable, so it's fine, but as a matter of how C works it's absolutely fine to just use (and increment) source_start and destination_start. This won't propagate back the variables the caller uses. (It would in FORTRAN or ALGOL but those are ancient)

- I'd probably name source_end instead as source_last. Or change the comparison to < instead of <=. The name "source_end" makes me think it's as usual in C one-past-the-end. This would avoid a lot of doing "size-1" in the caller and fit most C programmer's expectations.

- with 5 function arguments you're getting close to the limit of what can be passed in registers on x86_64 (6) and past the limit on ARM32 (4). It's fine to exceed the limit but it just means more code in both the caller and the called function to copy the value to the stack and back.

It's for ARM at the moment. For my intended use I can't see me needing more than 256 elements.

Not sure what I can do to reduce the amount of elements, the only way to get it to 4 is to have it just copy all of the source array, this is probably how i would use it most of the time.

If it's for ARM (32bit architecture), it is not a generally good idea to limit yourself to 8bit index/size variables. It makes for an evil size limitation (when you will need larger sizes afterwards) and 32bit index variable will be as fast, in some cases even faster!

[Simon]

not really. ARM addresses memory in bytes. I have saved 3 bytes of RAM on the 4 you suggest. Next I could use 16 bits but really i can't see myself at the moment with an array of more than 256 elements. I can of course make this an 8 bit version and write the 16 bit version when required.

[Simon]

My current use here is for a display of up to 80 characters.

[Yansi]

If you are using a GCC-derived compiler, using the __builtin_memcpy() should yield optimal code for each processor; these is provided by gcc, not by any library per se. If you want your exact interface, then

Code: [Select]

static inline void copy_array_to_array(uint8_t destination[], int destination_start, uint8_t source[], int source_start, int source_end)
{
    __builtin_memcpy(destination + destination_start, source + source_start, (source_end - source_start + 1) * sizeof destination[0]);
}
The useful points to realize here are

• GCC provides a number of built-ins that are normally provided by the C library; these are optimized for the target architecture.  The ones relevant for microcontrollers include strlen(), strchr(), strrchr(), strcmp(), memset(), memcpy(), and memchr().
• When stuff is an array or a pointer, and index is an integer, (stuff + index) == &(stuff[index]).
• sizeof stuff[0] evaluates to the size of the elements in stuff, without dereferencing it; the compiler computes the size at compile time.
  I recommend omitting the parentheses when possible, to remind us humans that sizeof is an operator, not a function.
  (For a type, I recommend sizeof (type), with an extra space in between.)

Whether these are relevant for Simon, I'm not sure.  Typically, the amount of time spent in copying stuff around in memory is neglible on microcontrollers.

Not really true. Maybe true for most "arduino type of work".  As Simon uses ARM, memory access speed in fact IS a concern.  ARM is an awful load-store architecture, with pretty inefficient memory access speeds.

For generic occasional data move, this is not of a concern. But whenever a repeated task of copying (especially larger) data is used, the programmer should well be aware of what resources will be consumed. It is especially important, when working with external memory chips and especially DRAM, that is well suited for burst access.

Repeated tasks such as: Continuously refreshing complex drawings on LCDs, any data processing, etc.

I would not like to go tangent here with an argument, just making a point, that memory access is not  free on ARM. Can take more cycles than you would think. It is now up to Simon to learn or ask if interested.

Regarding our current discussed topic of copying memory: The correct buzzwords to look for is loop unrolling and the generic idea behind improving memory access speeds is to read or write in bursts of the largest possible size.

[Yansi]

not really. ARM addresses memory in bytes. I have saved 3 bytes of RAM on the 4 you suggest. Next I could use 16 bits but really i can't see myself at the moment with an array of more than 256 elements. I can of course make this an 8 bit version and write the 16 bit version when required.

Thats just an imagination of a not well informed person. Just  make a function that has a parameter of a size BYTE (8 bits) and see how it compiles: You should not be surprised to find the parameter is actually passed using a 32bit register anyway.

Restricting a variable to 8bits on ARM may lead to unnecessary instructions executed, such as SIGN EXTENSION, or other truncation of resulting data to fit back to the memory location.

Memory access speed to BYTE (8bit), HALFWORD (16bit) and WORD (32bit) on ARM is exactly the same.*

And rarely you need to optimize for RAM size.  Most of times you need to optimize for execution time instead.

In fact, I have never came into a situation on ARM, where I did have to start optimizing memory used.

//EDIT: * if talking about aligned memory access. unaligned ones are slow or not possible at all, leading to a hardfault.

[Simon]

So your saying that if i can spare the working RAM I should always use 32 bit variables to save the time spent dealing with converting what will be a 32 bit memory transaction anyway into 8 bit. I thought ARM M0+ which is what this is going on ran a 16 bit instruction set (thumb) in order to improve memory bandwidth. would 16 bit be a fair compromise that the CPU is more used to nativey handling.

Why have byte addressable RAM if the chip works best at 32 bit access chunks?

[Yansi]

Not always. That is not what I meant. I am just trying to make a point and make you aware what the difference may be, when using just 8bit variables and 32bits.

Having a byte addressable RAM does not rule out with anything. That is an actual benefit.

I am trying to make a point, that the memory has a 32bit wide data bus and that reading it by 32bits at a time is obviously faster, than reading 4 bytes successively.

Also, all processing is done using 32bit wide registers.   So you do not necessarily gain speed with processing data 8 bits at a time, but you can loose time instead, by processing them in this manner.

[Nominal Animal]

Note that very often function parameters and local variables are not stored in RAM, and only exist in registers.  This is especially true for 32-bit ARMs. If you use a smaller explicit-size type like unsigned char, int8_t, or int16_t, the compiler may have to add unnecessary AND instructions to ensure the passed register contains a value representable by that type.

Technically, C does nowadays provide types like int_fastN_t and uint_fastN_t for N = 8, 16, 32, and 64, where the type is at least that size, possibly larger, whatever is most efficient for the target processor, exactly for this purpose (local variables and static inline function parameters).   For example, on x86-64 on Linux, gcc uses 8-bit uint_fast8_t and int_fast8_t, but 64-bit for the larger types.


The one oddball trick I have sometimes used is to fill in the string buffer backwards, from right to left.

For example:

Code: [Select]

char *prepend_uint(char *p, unsigned int u)
{
    do {
        *(--p) = '0' + (u % 10);
        u /= 10;
    } while (u);
    return p;
}

char *prepend_block(char *p, const void *s, const int n)
{
    memcpy(p - n, s, n);
    return p - n;
}

char *prepend_reverse(char *p, const char *s)
{
    while (*s) {
        *(--p) = *(s++);
    }
    return p;
}
Let's say you want to construct string No accidents for num days, and you have a buffer with room for say 32 characters, char buffer[32];.  You would use the above functions using e.g.

Code: [Select]

    char *p = buffer + sizeof buffer;
    *(--p) = '\0';  /* End-of-string marker */
    p = prepend_reverse(p, "syad ");
    p = prepend_uint(num);
    p = prepend_reverse(p, " rof stnedicca oN");
or, equivalently,

Code: [Select]

    char *p = buffer + sizeof buffer;
    *(--p) = '\0';
    p = prepend_block(p, " days", 4);
    p = prepend_uint(num);
    p = prepend_block("No accidents for ", 13);
and in both cases, you would have the desired string starting at p .

To see exactly why this would be useful, one would need to look at the machine code: this compiles to very tight little code.  Right-aligning fixed-width fields, and alternate versions for architectures where ROM/Flash memory access is special, is easy to implement.

When filling buffers in the normal order, you can convert numbers to strings in reverse (swapped right-to-left), append any left padding, reverse the string, and finally append any right padding.

[Simon]

I am trying to make a point, that the memory has a 32bit wide data bus and that reading it by 32bits at a time is obviously faster, than reading 4 bytes successively.

But how does that help me? I can't put more than one 8 bit variable into a single 32 one as I would have to then "decode" the variables which would in turn waste time. Yes if I was doing a bit flag variable I would make one 32 bit one rather than 4 8 bit ones.

[Simon]

Ultimately my buffer is being pumped out on an 8 bit serial port, are there any better variable types that I should use? what does GCC for ARM support?

[brucehoult]

Not sure what I can do to reduce the amount of elements, the only way to get it to 4 is to have it just copy all of the source array, this is probably how i would use it most of the time.

You don't really need a function for this since the code is so compact:

Code: [Select]

/* copy 8 elements from position 0 in array text to position 10 in array buf:
   int i, j, n;
   for (i = 10, j = 0, n = 8; n > 0; ++i, ++j, --n) {
       buf[i] = text[j];
   }


That generates more code than memcpy(buf+10, text, and you'd never notice the speed difference. You'd only win if your program didn't already link in memcpy.

[brucehoult]

- with 5 function arguments you're getting close to the limit of what can be passed in registers on x86_64 (6) and past the limit on ARM32 (4). It's fine to exceed the limit but it just means more code in both the caller and the called function to copy the value to the stack and back.

Not sure what I can do to reduce the amount of elements, the only way to get it to 4 is to have it just copy all of the source array, this is probably how i would use it most of the time.

You can reduce it by not passing both destination and destination_start to the function but just the sum of them -- or to put it another way, the address of the first byte to write to. And the same for source.

[brucehoult]

not really. ARM addresses memory in bytes. I have saved 3 bytes of RAM on the 4 you suggest. Next I could use 16 bits but really i can't see myself at the moment with an array of more than 256 elements. I can of course make this an 8 bit version and write the 16 bit version when required.

No, that's not correct. Those function arguments (the first 4 of them anyway, on ARM) and local variables (up to 12 or so total that are live at the same time) are in CPU registers, not RAM. The registers are always 32 bits even if you put an 8 bit value into them.

[Nominal Animal]

Here is a practical example why local variables and function parameters should generally be ints and not chars or shorts or explicit-length types:

Code: [Select]

int  my_slen1(const char *p) { return __builtin_strlen(p); }
char my_slen2(const char *p) { return __builtin_strlen(p); }
When compiling the above using GCC for Cortex-M4 using Thumb instructions, the two compile essentially to

Code: [Select]

    .text
    .thumb

my_slen1:
    b   strlen

my_slen2:
    push {r3, lr}
    bl   strlen
    uxtb  r0, r0
    pop  {r3, pc}
Instead of saving memory, my_slen2() generates extra code, because the return value must be limited to 8 bits!

Similar effects happen when calling functions that take parameters that are limited to smaller range of values than the native registers support.

So, what to do?

It is a portability issue.  On 8-bit Arduinos, int is a 16-bit type, and technically requires two registers.  On 64-bit architectures, int may be just 32-bits.

Although the int_fastN_t and uint_fastN_t types would be the technically best option (with N being the smallest reasonable value for that particular variable; 8, 16, 32, or 64), not many programmers use them.  If others work on your code, they may be surprised and get it wrong, which incurs a maintenance burden.

Current POSIXy systems I use are either ILP32 or LP64, so long is the "native register type".  However, for in-memory sizes and counts, I use size_t .

Some projects define their own types, using preprocessor #if directives to choose the best mapping.  For example, you might have iregN and uregN, analogously to int_fastN_t and uint_fastN_t.  Because of the nonstandard type name, other programmers might actually read the documentation or comments on how the types are intended to be used.  However, don't fall into the WORD/DWORD/QWORD trap; better assume the types are binary (two's complement if signed) with a fixed number of bits, and have that number (or lower limit) in the type.

Most current C code seems to use size_t (for in-memory sizes and counts) and int for everything else.