Common embedded bugs and fixes in Embedded C - Time & Space Complexity

Time Complexity: Common embedded bugs and fixes

O(n)

Understanding Time Complexity

When we look at common bugs in embedded C code, we want to understand how the time it takes to run the code changes as inputs or conditions change.

We ask: How do these bugs affect the speed or efficiency of the program?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void delay(int count) {
    while(count-- > 0) {
        // empty loop for delay
    }
}

void process_data(int *data, int size) {
    for(int i = 0; i < size; i++) {  // bug fixed: changed <= to < to avoid off-by-one error
        data[i] = data[i] * 2;
    }
}
    

This code has a delay loop and a function that processes an array. The original off-by-one bug has been fixed to prevent unexpected behavior.

Identify Repeating Operations

Look at the loops that repeat operations.

• Primary operation: The for-loop in process_data that multiplies each array element.
• How many times: It runs size times, correctly processing each element once.

How Execution Grows With Input

The loop runs exactly as many times as the size of the input array, ensuring no extra work or errors.

Input Size (n)	Approx. Operations
10	10
100	100
1000	1000

Pattern observation: The loop runs exactly the intended number of times, preventing out-of-bounds access.

Final Time Complexity

Time Complexity: O(n)

This means the time to run grows directly with the size of the input array, with no extra cost or errors.

Common Mistake

[X] Wrong: "The loop runs exactly the number of elements in the array without error."

[OK] Correct: Because the loop condition originally used <= instead of <, it ran one extra time, causing out-of-bounds access and possible crashes.

Interview Connect

Understanding how small bugs affect time and behavior shows your attention to detail and helps you write safer, more efficient embedded code.

Self-Check

"What if we changed the loop condition from <= size to < size? How would the time complexity and safety change?"

Practice

1. What is a common cause of unpredictable behavior in embedded C programs related to variables?

easy

A. Using uninitialized variables before setting a value

B. Using too many comments in the code

C. Writing functions with too many parameters

D. Using global variables only

Solution

1. Step 1: Understand variable initialization

   Uninitialized variables contain garbage values, causing unpredictable behavior.

2. Step 2: Recognize the impact in embedded systems

   Embedded systems rely on precise values; uninitialized variables can cause errors or crashes.

3. Final Answer:

   Using uninitialized variables before setting a value -> Option A

4. Quick Check:

   Uninitialized variables = unpredictable values [OK]

Hint: Always initialize variables before use to avoid surprises [OK]

Common Mistakes:

• Assuming variables start at zero automatically
• Ignoring compiler warnings about uninitialized variables
• Thinking only pointers need initialization

2. Which of the following is the correct way to clear an interrupt flag in embedded C?

easy

A. interrupt_flag++;

B. interrupt_flag = 1;

C. interrupt_flag = 0;

D. interrupt_flag = -1;

Solution

1. Step 1: Identify interrupt flag clearing method

   Interrupt flags are cleared by setting them to 0 to indicate the interrupt is handled.

2. Step 2: Understand why other options fail

   Setting to 1 or incrementing does not clear the flag; negative values are invalid.

3. Final Answer:

   interrupt_flag = 0; -> Option C

4. Quick Check:

   Clear interrupt flag = 0 [OK]

Hint: Clear interrupt flags by setting them to zero [OK]

Common Mistakes:

• Setting flag to 1 instead of 0
• Incrementing flag instead of clearing
• Ignoring the need to clear flags causing repeated interrupts

3. What will be the output of this embedded C code snippet?

volatile int flag = 0;
void ISR() {
  flag = 1;
}
int main() {
  while(flag == 0) {
    // wait
  }
  return 0;
}

medium

A. Program waits until ISR sets flag to 1, then exits

B. Program exits immediately

C. Compilation error due to volatile keyword

D. Program runs indefinitely without stopping

Solution

1. Step 1: Understand volatile keyword usage

   Volatile tells compiler the variable can change anytime, so it won't optimize the loop away.

2. Step 2: Analyze program flow

   Main waits in loop until ISR sets flag to 1, then loop ends and program exits.

3. Final Answer:

   Program waits until ISR sets flag to 1, then exits -> Option A

4. Quick Check:

   Volatile flag updated by ISR = loop ends [OK]

Hint: Use volatile for variables changed by interrupts [OK]

Common Mistakes:

• Ignoring volatile causing infinite loop
• Assuming ISR runs automatically without setup
• Thinking volatile causes compile errors

4. Identify the bug in this embedded C code and the best fix:

int counter;
void setup() {
  // No initialization of counter
}
void loop() {
  counter++;
  if(counter > 10) {
    counter = 0;
  }
}

medium

A. Change counter to volatile

B. Initialize counter to 0 in setup()

C. Remove the if condition

D. Declare counter as static

Solution

1. Step 1: Identify uninitialized variable usage

   Counter is used without initialization, causing unpredictable start value.

2. Step 2: Fix by initializing counter

   Set counter = 0 in setup() to ensure predictable counting behavior.

3. Final Answer:

   Initialize counter to 0 in setup() -> Option B

4. Quick Check:

   Initialize variables before use = correct count [OK]

Hint: Always initialize counters before incrementing [OK]

Common Mistakes:

• Assuming global variables start at zero
• Using volatile without need
• Ignoring initialization causing wrong counts

5. You have a sensor reading stored in a variable that updates via interrupt. Which combination of fixes ensures safe and correct reading in main code?

volatile int sensor_value;
int safe_value;

void ISR() {
  sensor_value = read_sensor();
}

int main() {
  // What should be done here?
}

hard

A. Make sensor_value non-volatile and copy it

B. Directly use sensor_value without copying

C. Use a delay loop before reading sensor_value

D. Disable interrupts, copy sensor_value to safe_value, enable interrupts

Solution

1. Step 1: Understand volatile and interrupt safety

   Volatile ensures compiler reads fresh value, but reading multi-byte data can be interrupted causing corruption.

2. Step 2: Use interrupt disable-copy-enable pattern

   Disable interrupts, copy sensor_value to safe_value, then enable interrupts to get consistent snapshot.

3. Final Answer:

   Disable interrupts, copy sensor_value to safe_value, enable interrupts -> Option D

4. Quick Check:

   Disable interrupts to safely copy volatile data [OK]

Hint: Disable interrupts when copying multi-byte volatile data [OK]

Common Mistakes:

• Reading volatile multi-byte data without protection
• Making volatile variable non-volatile
• Using delay instead of disabling interrupts