4
\$\begingroup\$

I am trying to construct a binary message packet. It needs to escape binary value 0 by appending extra 0 in front of it:

//Before escape
data[] = { 1, 2, 3, 4, 5, 0, 6, 7, 8, 9 }

//After escape - value 0 is appended after 0
data[] = { 1, 2, 3, 4, 5, 0, 0, 6, 7, 8, 9 }

My source code:

uint8_t escape_data[32];
uint8_t escape_index = 0;
uint8_t data[] = { 1, 2, 3, 4, 5, 0, 6, 7, 8, 9 };

for (int i = 0; i < sizeof(data); i++)
{
    escape_data[escape_index++] = data[i];
    if (data[i] == 0) {
        escape_data[escape_index++] = 0;
    }
}

Is there any elegant way to solve this problem?

P.S the code above is designed to be simple to read, I ignore those array sizing for simplicity and hard coding them, I want to know a good algorithm or a good way to write to solve this problem with the least variable and memory footprint

  1. Searching for 0
  2. Appending byte in between array
\$\endgroup\$
4
\$\begingroup\$

Hard coding 32 as the size of the destination array regardless of the size if the source array is not so good, as it might not be big enough. Better approaches would be:

  • Make the destination twice as big as the input: that way it will always be big enough to contain the escape zeros. The drawback is that most often it will be too big.
  • Count the number of zeros first, and the allocate the exact size that you need. The drawback is that the counting step is an extra \$O(N)\$ operation. On the other hand, if the counting step find no zeros, then you can skip the copying step. If most input will not contain zeros, then this approach should work pretty well.
\$\endgroup\$
  • \$\begingroup\$ your approach of counting 0 is good, but I still need to iterate over the loop and checking them, i guess this is the only way? but when I found 0 is there anyway of inserting an extra 0 in between, the above is OK, but I think there is a better approach? like using (memmove) as mention by @syb0rg? \$\endgroup\$ – Tim Jun 5 '15 at 7:07
  • \$\begingroup\$ The problem with memmove is that it's not really moving, it's actually copying, so it will still iterate over the elements "moved". And if there are multiple zeros in the input, then some elements will be iterated over multiple times. Take for example an array of 10 elements, with 0 at the 3rd and 6th index. When you see the first 0 at index 3, you copy the rest of the array to make space for the extra zero, and then you will find another 0 at index 7, and move the rest of the elements. These latter will be moved for the 2nd time. \$\endgroup\$ – Stop ongoing harm to Monica Jun 5 '15 at 8:08
  • \$\begingroup\$ yup! u are right, so what is the best way to do it? u mention count for 0 1st, if none skip, that is almost the same one implemented by me? \$\endgroup\$ – Tim Jun 5 '15 at 8:34
  • 2
    \$\begingroup\$ There is a trade-off whichever way you choose. If you don't mind wasting memory, then your original method without counting can do the job in a single pass. If you don't want to waste memory, then you need a first pass to count. I don't think there's a "best" method, it always depends on your other requirements \$\endgroup\$ – Stop ongoing harm to Monica Jun 5 '15 at 8:43
3
\$\begingroup\$

A few notes:

  • 32 is a magic number in your declaration of escape_data. Define it and give it a name so that the number has more meaning behind it. Also, comments wouldn't hurt.

  • You aren't actually iterating over your data set properly. sizeof(data) isn't always guaranteed to equal the number of items in your array. It works this time since sizeof(uint8_t) is one, but it would be better to protect yourself from future confusion by either leaving a comment or changing it to something like sizeof(data)/sizeof(data[0]).

  • I would say you want to consider looking at memmove() (or the better memmove_s()) for the actual insertion of the 0 into your array. It's most likely going to be a bit faster than your current method of doing things (since there's less moving parts), and requires a bit less code making your program more readable.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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