C/C++ Programming II

Chapter 1: Bitwise Operations

In embedded C, you rarely work with whole integers. You work with individual bits. A hardware register is a 32-bit value where each bit controls something different: bit 5 turns on an LED, bit 3 enables a timer, bit 12 selects the clock source. You need surgical tools to flip one bit without disturbing the others.

C gives you six bitwise operators that work on each bit independently:

Here's a real embedded example. On an STM32, GPIO Port A's Output Data Register (GPIOA->ODR) is at address 0x40020014. Bit 5 controls the onboard LED. To turn it on:

c
// Turn on LED (bit 5 of GPIOA->ODR)
GPIOA->ODR |= (1 << 5);    // Set bit 5: xxxx_xxxx |= 0010_0000

// Turn off LED
GPIOA->ODR &= ~(1 << 5);   // Clear bit 5: xxxx_xxxx &= 1101_1111

// Toggle LED
GPIOA->ODR ^= (1 << 5);    // Flip bit 5 only

// Check if bit 5 is set
if (GPIOA->IDR & (1 << 5)) {
    // Button is pressed
}

Bit fields let you pack multiple flags into a single byte. Instead of wasting 4 bytes (an int) for a boolean flag, you use 1 bit:

c
struct SensorFlags {
    uint8_t ready    : 1;  // 1 bit: sensor data ready
    uint8_t overflow : 1;  // 1 bit: buffer overflow
    uint8_t channel  : 3;  // 3 bits: channel 0-7
    uint8_t gain     : 2;  // 2 bits: gain 0-3
    uint8_t reserved : 1;  // 1 bit: padding to 8 bits total
};  // sizeof = 1 byte! Not 4 ints = 16 bytes.

Chapter 2: Pointers Deep Dive

You already know a pointer holds a memory address. But pointer arithmetic is where C reveals its true power — and its danger. When you write p + 1, C doesn't add 1 byte. It adds sizeof(*p) bytes. This is how arrays work under the hood: arr[i] is exactly *(arr + i).

Let's trace through memory. Suppose we have an array of 4-byte integers starting at address 0x2000:

c
int arr[4] = {10, 20, 30, 40};
int *p = arr;           // p = 0x2000

// Pointer arithmetic:
*p        // value at 0x2000 = 10
*(p + 1)  // value at 0x2004 = 20  (NOT 0x2001!)
*(p + 2)  // value at 0x2008 = 30
*(p + 3)  // value at 0x200C = 40

// These are identical:
arr[2]       // = 30
*(arr + 2)  // = 30
*(p + 2)    // = 30

Double pointers (char **) hold the address of a pointer. Why? Two common reasons: (1) you need a function to modify a pointer (pass pointer-to-pointer), and (2) arrays of strings (argv in main).

c
// Function that allocates memory and returns it via double pointer
void create_buffer(int **out, int size) {
    *out = (int *)malloc(size * sizeof(int));
}

int *buf = NULL;
create_buffer(&buf, 100);  // buf now points to allocated memory
// Without **, the function would modify a LOCAL copy of buf

Function pointers store the address of a function. This enables callbacks — you pass behavior as an argument:

c
// Declare a function pointer type
typedef void (*callback_t)(int event_code);

// A function matching that signature
void on_button_press(int code) {
    printf("Button %d pressed\n", code);
}

// Register the callback
callback_t handler = on_button_press;
handler(5);  // calls on_button_press(5)

Chapter 3: Dynamic Memory

Static arrays have a problem: you must decide their size at compile time. But what if you don't know how many sensor readings you'll collect? You need memory allocated at runtime. In C, that means asking the heap for space using malloc.

The heap is a region of memory managed by a runtime allocator. Unlike the stack (which is automatic), heap memory persists until you explicitly free it. Forget to free? That's a memory leak. Free it twice? That's undefined behavior (usually a crash).

c
// Allocate array of 100 ints (400 bytes on 32-bit system)
int *data = (int *)malloc(100 * sizeof(int));
if (data == NULL) {
    // malloc failed! Out of memory. Handle gracefully.
    return -1;
}

// Use it
data[0] = 42;
data[99] = 7;

// Need more space? Resize to 200 ints
int *bigger = (int *)realloc(data, 200 * sizeof(int));
if (bigger == NULL) {
    // realloc failed, but data is still valid!
    free(data);
    return -1;
}
data = bigger;  // ptr may have moved

// Done. Free it.
free(data);
data = NULL;  // ALWAYS null after free to prevent dangling pointer

Fragmentation is the silent killer of embedded systems. After many malloc/free cycles, the heap becomes a patchwork of used and unused blocks. You might have 1 KB free total, but split into 10 non-contiguous 100-byte fragments. A request for 200 bytes fails even though "enough" memory exists.

Chapter 4: Recursion

A recursive function calls itself. That sounds circular, but it works because each call handles a smaller version of the problem, and there's a base case that stops the chain. Without a base case, you recurse forever and overflow the stack.

Every recursive call creates a new stack frame — a block of memory on the stack holding that call's local variables, parameters, and return address. When the function returns, its frame is popped. This is why deep recursion is dangerous in embedded: each frame costs memory.

Let's trace factorial(4) step by step:

c
int factorial(int n) {
    if (n <= 1) return 1;       // Base case
    return n * factorial(n - 1);  // Recursive case
}

// Trace of factorial(4):
// factorial(4): return 4 * factorial(3)  [frame 4 pushed]
//   factorial(3): return 3 * factorial(2)  [frame 3 pushed]
//     factorial(2): return 2 * factorial(1)  [frame 2 pushed]
//       factorial(1): return 1  (BASE CASE)   [frame 1 pushed]
//     factorial(2): return 2 * 1 = 2          [frame 1 popped]
//   factorial(3): return 3 * 2 = 6            [frame 2 popped]
// factorial(4): return 4 * 6 = 24             [frame 3 popped]

Binary search is another natural fit for recursion. Each call halves the search space:

c
int binary_search(int *arr, int lo, int hi, int target) {
    if (lo > hi) return -1;          // Base: not found
    int mid = lo + (hi - lo) / 2;    // Avoid overflow vs (lo+hi)/2
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)
        return binary_search(arr, mid + 1, hi, target);
    return binary_search(arr, lo, mid - 1, target);
}

Chapter 5: Data Structures

Arrays are fast for random access (arr[i] is O(1)) but terrible for insertion in the middle (you must shift everything). Different problems demand different structures. The big three in C: linked lists, binary search trees, and hash tables.

Linked Lists

A linked list is a chain of nodes, each containing data and a pointer to the next. Insertion anywhere is O(1) (just rewire pointers), but finding the i-th element is O(n) (walk the chain).

c
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// Insert at head: O(1)
void push(Node **head, int val) {
    Node *n = (Node *)malloc(sizeof(Node));
    n->data = val;
    n->next = *head;   // new node points to old head
    *head = n;          // head now points to new node
}

// Free entire list
void free_list(Node *head) {
    while (head) {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

Binary Search Trees

A BST stores values such that for every node: all left descendants are smaller, all right descendants are larger. Search, insert, and delete are all O(log n) on average — but O(n) worst case if the tree becomes a straight line (unbalanced).

c
typedef struct TreeNode {
    int key;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* insert(TreeNode *root, int key) {
    if (!root) {
        TreeNode *n = (TreeNode*)malloc(sizeof(TreeNode));
        n->key = key; n->left = n->right = NULL;
        return n;
    }
    if (key < root->key) root->left = insert(root->left, key);
    else root->right = insert(root->right, key);
    return root;
}

Hash Tables

A hash table maps keys to values in O(1) average time. You hash the key to get an array index. Collisions (two keys mapping to the same index) are handled by chaining (linked list at each slot) or open addressing (probe for next empty slot).

Chapter 6: Sorting & Searching

Sorting is the most studied problem in computer science. Why? Because searching a sorted array is O(log n) instead of O(n). That's the difference between finding a record in 20 comparisons vs 1,000,000. The key divide: O(n²) algorithms (bubble, insertion) vs O(n log n) algorithms (quicksort, mergesort).

Quicksort (The King)

Quicksort picks a pivot, partitions the array so everything smaller is left and everything larger is right, then recurses on each half. Average case: O(n log n). Worst case (already sorted): O(n²). In practice, fastest for random data.

c
void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int *arr, int lo, int hi) {
    int pivot = arr[hi];  // last element as pivot
    int i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[hi]);
    return i + 1;
}

void quicksort(int *arr, int lo, int hi) {
    if (lo < hi) {
        int p = partition(arr, lo, hi);
        quicksort(arr, lo, p - 1);
        quicksort(arr, p + 1, hi);
    }
}

Let's trace quicksort on [38, 27, 43, 3, 9, 82]:

Final sorted: [3, 9, 27, 38, 43, 82].

Chapter 7: State Machines

A Finite State Machine (FSM) is the most important design pattern in embedded C. Your microcontroller is always in exactly one state. When an event occurs, it transitions to a new state and may produce an action. That's it. No complex logic trees. No tangled if-else chains. Just: current state + event → action + next state.

Why FSMs dominate embedded? Because they're provably correct. You can draw every possible state and transition on paper. If you can't reach a dangerous state from the diagram, it can't happen in code. Compare that to 500 lines of nested if-statements where one forgotten condition means the motor never stops.

c
typedef enum { IDLE, COIN_IN, SELECTING, DISPENSING, CHANGE } State;
typedef enum { EVT_COIN, EVT_SELECT, EVT_DONE, EVT_TIMEOUT } Event;

State current = IDLE;

void fsm_step(Event evt) {
    switch (current) {
    case IDLE:
        if (evt == EVT_COIN) {
            display("Coin accepted");
            current = COIN_IN;
        }
        break;
    case COIN_IN:
        if (evt == EVT_SELECT) {
            start_motor();
            current = DISPENSING;
        } else if (evt == EVT_TIMEOUT) {
            return_coin();
            current = IDLE;
        }
        break;
    case DISPENSING:
        if (evt == EVT_DONE) {
            give_change();
            current = CHANGE;
        }
        break;
    case CHANGE:
        current = IDLE;  // auto-transition back
        break;
    }
}

The transition table is the formal specification:

Chapter 8: Storage Maps & Data Representation

When you define a struct in C, the compiler doesn't always pack the fields tightly. It inserts padding bytes to ensure each field starts at an aligned address. Why? Because most CPUs can only read a 4-byte int from an address that's a multiple of 4. Unaligned access is either slow (ARM) or illegal (older ARM, some MIPS).

Let's trace a real struct:

c
struct Example {
    char  a;    // 1 byte, offset 0
                 // 3 bytes PADDING (next field needs 4-byte alignment)
    int   b;    // 4 bytes, offset 4
    short c;    // 2 bytes, offset 8
                 // 2 bytes PADDING (struct size must be multiple of largest align)
};
// sizeof(struct Example) = 12, NOT 7!

// Memory layout (byte by byte):
// [a][P][P][P][b][b][b][b][c][c][P][P]
//  0  1  2  3  4  5  6  7  8  9  10 11

You can reduce wasted space by reordering fields from largest to smallest:

c
struct Packed {
    int   b;    // 4 bytes, offset 0
    short c;    // 2 bytes, offset 4
    char  a;    // 1 byte,  offset 6
                 // 1 byte PADDING (struct align to 4)
};
// sizeof(struct Packed) = 8 — saved 4 bytes!

Endianness matters for data sent between machines. Little-endian (x86, ARM default): least significant byte at lowest address. Big-endian (network byte order): most significant byte first. The value 0x12345678:

Chapter 9: File I/O & Portability

In C, files are accessed through file pointers (FILE *). You open a file, read or write, then close it. The key insight: C treats files as a stream of bytes. You maintain a file position indicator that advances as you read/write. You can jump to any position with fseek.

c
// Write 100 records to a binary file
typedef struct { uint32_t id; float value; } Record;

FILE *f = fopen("data.bin", "wb");  // "wb" = write binary
if (!f) { perror("fopen"); return 1; }

Record rec = { .id = 42, .value = 3.14f };
fwrite(&rec, sizeof(Record), 1, f);  // write 1 record
fclose(f);

// Read record N directly (random access)
f = fopen("data.bin", "rb");
int record_num = 5;
fseek(f, record_num * sizeof(Record), SEEK_SET);
fread(&rec, sizeof(Record), 1, f);
// rec now contains record #5
fclose(f);

Portability Landmines

C's primitive types have implementation-defined sizes. int could be 2 bytes on a 16-bit micro or 4 bytes on a PC. If you write raw int values to a file on one machine and read them on another, you'll get garbage. The solution: fixed-width types from <stdint.h>:

c
// Portable serialization: write uint32 in little-endian
void write_le32(FILE *f, uint32_t val) {
    uint8_t buf[4];
    buf[0] = val & 0xFF;
    buf[1] = (val >> 8) & 0xFF;
    buf[2] = (val >> 16) & 0xFF;
    buf[3] = (val >> 24) & 0xFF;
    fwrite(buf, 4, 1, f);
}

// Portable deserialization: read uint32 from little-endian
uint32_t read_le32(FILE *f) {
    uint8_t buf[4];
    fread(buf, 4, 1, f);
    return buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24);
}

Chapter 10: Variable Arguments & Non-Local Gotos

How does printf accept any number of arguments? Through C's variable argument (varargs) mechanism. The function declares a minimum set of fixed parameters, then uses va_list to iterate over the rest. This is how you write your own printf-like logging function in embedded code.

c
#include <stdarg.h>

// Custom debug logger: logs to UART in embedded, stdout in testing
void debug_log(const char *fmt, ...) {
    va_list args;
    va_start(args, fmt);    // Initialize: 'fmt' is the last fixed param

    // Extract arguments one by one based on format string
    // (simplified: real impl would parse fmt)
    vprintf(fmt, args);     // printf that takes a va_list

    va_end(args);           // MUST call when done. Cleans up.
}

// Usage:
debug_log("Sensor %d: value = %f\n", 3, 27.5);
debug_log("Error at addr 0x%08X\n", 0xDEADBEEF);

setjmp / longjmp: C's Exception Handling

C has no try/catch. But embedded code often has deeply nested function calls that can fail. Unwinding the stack manually (checking return codes at every level) is tedious. setjmp/longjmp provides non-local jumps — you mark a return point, and can jump back to it from any depth.

c
#include <setjmp.h>

jmp_buf error_recovery;

void deep_function() {
    // ... 5 levels deep in call stack ...
    if (hardware_fault()) {
        longjmp(error_recovery, 1);  // Jump back to setjmp site!
        // Code below here NEVER executes
    }
}

void main_loop() {
    if (setjmp(error_recovery) != 0) {
        // We got here via longjmp. Handle the error.
        reset_hardware();
        printf("Recovered from fault\n");
        return;
    }
    // Normal execution path:
    init_sensors();
    calibrate();       // calls deep_function somewhere inside
    run_control_loop();
}

Warning: longjmp unwinds the stack without calling any cleanup code in intermediate functions. Any malloc'd memory in those functions is leaked. Any open file handles are leaked. Any hardware left in a half-configured state stays that way. This is why embedded teams use it ONLY at the top-level error boundary.

Chapter 11: Mastery & Connections

You now have the complete low-level C toolkit: bit manipulation for hardware registers, pointer arithmetic for efficient traversal, dynamic memory (and why embedded avoids it), recursion, data structures, sorting, state machines for control flow, and storage maps for understanding what the compiler actually does with your structs.

Complexity Cheat Sheet

State Machine Design Template

c
// 1. Define states and events as enums
typedef enum { ST_INIT, ST_RUNNING, ST_ERROR, ST_COUNT } State;
typedef enum { EV_START, EV_FAULT, EV_RESET, EV_COUNT } Event;

// 2. Define action type
typedef void (*Action)(void);

// 3. Transition table (table-driven FSM)
typedef struct { State next; Action action; } Transition;

Transition table[ST_COUNT][EV_COUNT] = {
    /*           EV_START          EV_FAULT          EV_RESET */
    /* INIT  */ {{ST_RUNNING, go}, {ST_ERROR, log},  {ST_INIT, nop}},
    /* RUN   */ {{ST_RUNNING,nop}, {ST_ERROR, stop}, {ST_INIT, reset}},
    /* ERROR */ {{ST_ERROR, nop},  {ST_ERROR, nop},  {ST_INIT, reset}},
};

// 4. Step function: O(1), no switch-case needed
void fsm_dispatch(Event e) {
    Transition t = table[state][e];
    if (t.action) t.action();
    state = t.next;
}

Bitwise Operations Quick Reference

Design Challenge: Pool Allocator

Implement a memory pool allocator for fixed-size blocks. This eliminates fragmentation entirely: all blocks are the same size, so any free block fits any allocation request.

c
// Pool allocator: zero fragmentation, O(1) alloc and free
#define POOL_SIZE    32
#define BLOCK_SIZE   64   // bytes per block

static uint8_t pool_memory[POOL_SIZE * BLOCK_SIZE];
static uint8_t pool_used[POOL_SIZE];  // 0 = free, 1 = used

void* pool_alloc(void) {
    for (int i = 0; i < POOL_SIZE; i++) {
        if (!pool_used[i]) {
            pool_used[i] = 1;
            return &pool_memory[i * BLOCK_SIZE];
        }
    }
    return NULL;  // pool exhausted
}

void pool_free(void *ptr) {
    int idx = ((uint8_t*)ptr - pool_memory) / BLOCK_SIZE;
    pool_used[idx] = 0;
}

"C is quirky, flawed, and an enormous success." — Dennis Ritchie