I would like a help in a program I just write. Does someone knows how to develop "bit stuffing" in an arm processor?

If you are doing it in C, then you do it the same way as you do it for any other processor. I have created embedded applications for several embedded processors using arm-linux toolchains that CPU vendors supply for their devices. There are always some hardware considerations that are different, but C is C (and, in particular, gcc is gcc).

Here's my black-sheep uncle's recipe for making chicken soup:

1. First you steal a chicken.
.
.
.


Here's my recipe for developing a software application:

1. First you write a program specification for whatever unit you are coding.
.
.
.

Suppose you are creating a function to do something called "bit stuffing".

Then a program specification will include:

A. Description of input parameters. Types of variables, range of values, etc.

B. Description of output parameters.

C. Description of the processing that is to be carried out in the function in order to create the outputs from the inputs.

D. Description of any constraints. Should it be optimized for memory usage? Should it be optomized for speed? Are there any absolute timing requirements. Etc.

E. Description of a procedure for testing the function. It is usually desired to test as much as possible before plugging it into a larger program and just hoping that all of the little details have been implemented correctly.

Sometimes (usually) you have to be given something about the application that will be calling the function in order to understand the functional requirements. The way that the function interacts with the rest of the system is something that has to be considered up front, not after the code has been complete.

I feel that your best chance of getting help from a general programming assistance forum like this one is to show us at least some part of your program specification.

Regards,

Dave

I manage to write something... check that:
you think can I prove that code a little? I mean to cut some lines, just to make it faster.

Before answering your question I have a couple of questions for you. I will list them in reverse order of importance:

4. How fast is it now?

3. How fast does it have to be?

2. Have you tested it to see it performs its function correctly?

1. How is it supposed to work? For example if your message consists of the bytes 0x12, 0x3e, 0x56 how many bits are going to be put out? I assume that the function that calls this function is going to pass the output data along to some other function that will actually create the output stream. How can this function cause the correct output stream be generated?

See: if it doesn't work, then why waste time "optimizing" it?

If it is good enough to meet requirements, then why waste time "optimizing" it?

If you don't know what the requirements are, then how the heck can you know how fast it can be, regardless of how fast it has to be? See footnote.


Now, whether the code you posted can be changed to make it faster:

The answer to your question is, "it depends."

It depends on how your particular compiler optimizes things for your particular target architecture and how the code is actually executed in the operating system environment on the target machine. Sometimes I am completely blown away by the way that modern compilers optimize away people's carefully hand-crafted code into something that looks very different (and, in fact may or may not be more "optimal").

Every project is different, but I'll try to give a typical development flow for me.

I am assuming that I (or, maybe, some mid-level engineering manager) have been given an overall product Marketing Requirements Document or some such thing, and that issues have been addressed in a response (an Engineering Specification Document) that details the system architecture and includes various implementation specifics (including cost and schedule projections) that let the Marketing department decide whether this is going to be a product. That is, can it meet cost requirements as well as functional requirements within a time frame consistent with whatever it takes to make money on the beast? Refer, again, to the footnote.

I am assuming that I have been given the task to write some function that will be part of the overall software.

So, here might be a "typical" design flow for a particular functional unit:


Regards,

Dave

Footnote: Everybody knows the First Rule of Engineering:
If it ain't broke, don't fix it.

The thing that separates real Engineering from some kind of Science Project concerns whether you can make money doing it. Not every one just coming out of school knows this one, and lots of experienced Engineers don't know it. My mom (probably yours, too) would cringe at what I am going to say, but I feel it's important, and many projects have failed to meet schedule requirements because either the rule was not made known to the implementors (or, maybe, it wasn't enforced):

Don't be any better than you have to be.

If the thing is supposed to work at 922k bits per second, and if the design meets this requirement, and if a project team member spends even one man-hour trying to make it faster, that's money (and time) down the drain.

That's only my opinion, of course, and we would never tell anyone about it (think about all of the extra antacids that would be needed by the Public Relations department if it ever got out). However, I think it's important to reinforce my assertion that you should have a clear view of requirements before you start coding, let alone optimizing.)

D

I made an analysis of my program:

First I want a program which will take bytes (that's why I use mask technique), my device will read them and then it should separate if we have bit stuff or not.

I use a counter to count the bits and then I increase that counter. Maybe my English are not so good

It's not the english that I am having a problem with; it's the program and the lack of a specification.

If you aren't going to have bit stuffing, then the output of this function is the same as the input (so what's the point?). If you are going to have bit stuffing, then the output depends on the data pattern of bits of the input data bytes, and there can be more bits in the output than were in the input bytes.

For example: the bytes that I used as an example have 24 bits. With correct bit stuffing, the result is 25 bits. I am thinking that the result will be in 4 bytes, and since you are going most significant bit first, the 25'th output bit will be in the most significant bit of the fourth byte.

In other words (in addition to the fact that your bit stuffing doesn't exactly do the trick), the return value from the function can't simply be a number of bytes; I think it should be a bit count. And, if the total number of bits is not a multiple of 8, then the last byte will have the data in the upper bits. That's the kind of things that you put into the program specification before you write the code.

However, it's your project, and your specification, and I hate to repeat myself, but there's not much value in optimizing unless you have tested it to have some confidence that it is functionally correct.

Regards,

Dave

I understand what you mean... so what should I change to make that function work better? I said that because you told me that there is a problem with 25bits and the last bit... so maybe I have to change something to make it better. I don't mean to make it faster, just to cover all cases.

You already have most of the mechanism in place. Here is a way that I might look at the requirements:

Outer loop:
This is controlled by a byte counter to get the given number of input bytes from the input array. You have this.

Inner loop:
A loop to processes each bit of each input byte. You can use a bit counter to count the number of bits, or you can do something like this for the inner loop. (No need to have a separate variable do the bit counting for processing input bytes)


Within the inner loop, and independently of loop controls and counters, you will have logic that processes each input bit. You will have something like:

A ones counter to detect five 1's in a row. This starts with a value of zero before entering the outer loop. It is incremented after a '1' is written to an output byte and reset to zero after a '0' is written to the outer loop. The bit stuffing comes when the ones counter indicates that five successive '1' bits have been written. You have the right idea with this, but you need to pay attention to details: what does it take to put in the extra zero bit? Make sure it gets the right value into the output byte and doesn't change the state of the input bit processing logic.

You also need:
An output bit counter that is initialized to zero before you enter the outer loop and is incremented each time a bit is written to the output byte (increment after each input bit, and increment after each stuff bit). When the counter indicates that eight bits have been written, then store the output byte in the output array and reset the output bit counter to zero. Note, particularly that the output bit counter has nothing to do with the input bit counter. You pretty much have the right idea here.

Here's something new that you need:
A "totalbits" counter that is initialized before entering the outer loop and is incremented each time the output bit counter is incremented.

Here's something else you need: After all input bytes have been processed, if the output bit counter is not zero that means that some bits have been written to the output byte, but the output byte has not been written to the output array. These bits are in the lower bits of the output byte. You need to shift them to the upper bits and then write that byte to the output array.

The routine will return "totalbits".

Whatever routine is actually going to put the bitstream to a transmitter needs access to the array of bytes and it needs to know "totalbits".

Note that implementation details may modify slightly some of the above description.

For example: is it more efficient to have a separate bit counter for the output and test to see if it is equal to 8 every time a bit is written to the output byte. Or, could you just use totalbits? You could test to see if (totalbits % 8) is equal to zero or you could test to see if (totalbits & 0xfffffff8) is equal to zero.

Some people insist that use of pointer notation is more efficient than use of array notation, but my experience is that "it depends". My advice is not to try to guess which is more optimal, but to do whatever is absolutely clearest to you (so that it will be easier debug). Later, if your performance measurements indicate that optimization is necessary, you can try looking for and experimenting with some alternatives.

But first, get the code absolutely correct (to the best of your ability to test). Then test, test, and test some more. You can't prove a program works by testing, but if you do it right you can find a lot of bugs. Don't just use random bytes in the input stream. Use messages that don't require bit stuffing. Use messages with 4 ones in a row. Use messages with 5 ones in a row. Use messages with 6 ones in a row. Each test case should be short enough for you to test "by hand", so that you can know that the program is handling it correctly. (Don't just put in a bunch of stuff and then take the program output and see if you get the same answer "by hand"; make sure you understand ahead of time what the program should give you.)

Here's an example with three input bytes:


The zero bit that was stuffed into the lower bit of the second byte "shoved" the rest of the input bits to the right.

Remember that the input bit stream is a bit stream, and the ones counter is not reset at the end of each input byte; it is reset whenever five ones in a row have been written to the output byte:


Run through these examples by hand to make sure you know exactly the bit stuffing works. Make up other examples. Do them by hand.

This has two benefits:
1. In doing it by hand, bit-by-bit, you may get a better idea of the program flow that can do it. (Maybe your program flow won't be the same as mine, and that's probably a Good Thing --- as long as it works.)

2. You should always (always) have a test plan and test cases worked out before (yes, before) you start writing or modifying code. I have seen too many cases where even experienced programmers, who should know better, just start twiddling the code so that they can get the "right answer" to a particular test case and end up with something that is not only non functional for general cases, but is just too ugly to contemplate. (And impossible to debug without throwing out all of the "fixes" and starting again.)


Regards,

Dave

I think I got a little confused with the things I should add to the program, can you please give me a little help in those two steps you told me I have to add? I mean by giving me a code example

1. "An output bit counter that is initialized to zero"

2. A "totalbits" counter