Algorithms for Embedded C Development#
Introduction to Algorithms for Embedded C Development#
Algorithms are fundamental to embedded C development, driving the logic and efficiency of software running on constrained hardware. Embedded systems often have strict requirements for performance, memory, and real-time responsiveness, making algorithm optimization a critical skill for developers.
Why Algorithms Are Essential in Embedded C Development:#
Efficiency:
Embedded devices have limited computational power. Efficient algorithms ensure that operations are performed with minimal resource usage. Real-Time Performance:
Many embedded applications require timely responses (e.g., automotive systems, medical devices). Algorithms must provide predictable execution times to meet real-time deadlines.
Memory Optimization:
With limited RAM and storage, embedded algorithms need to minimize memory footprints and avoid unnecessary overhead.
Reliability:
Embedded systems often operate in critical environments where failure is not an option. Algorithms must be robust and error-tolerant.
Hardware Constraints:
Algorithms in embedded C often need to work closely with hardware, considering low-level details like registers, interrupts, and communication protocols.
Key Characteristics of Algorithms for Embedded Systems:#
Deterministic Execution:
Real-time systems demand algorithms with predictable timing behavior.
Low Complexity:
Simple algorithms are preferred to reduce processing time and power consumption.
Resource Awareness:
Memory, power, and processing constraints directly influence algorithm design.
Portability:
Algorithms should be modular and adaptable to different microcontrollers and hardware platforms.
Common Algorithm Types in Embedded C Development:#
Sorting and Searching Algorithms:
Bubble Sort, Quick Sort: Efficient data organization.
Binary Search: Fast data lookup for static or sorted datasets.
Control Algorithms:
PID Controllers: Widely used in automation and robotics.
State Machines: Manage state transitions in event-driven systems.
Signal Processing Algorithms:
FFT (Fast Fourier Transform): Analyzing frequency components in digital signals.
Digital Filters: Noise reduction and signal smoothing.
Scheduling Algorithms:
Round Robin: Simple multitasking in real-time systems.
Priority-Based Scheduling: Handling critical tasks with higher urgency.
Data Compression and Encryption:
Huffman Coding: Data compression in constrained environments.
AES, RSA: Secure data transmission and storage.
Communication Protocol Algorithms:
CRC (Cyclic Redundancy Check): Ensures data integrity.
UART, SPI, I2C Protocols: Algorithms for serial communication with peripherals.
Considerations for Algorithm Selection:#
Hardware Limitations: Consider CPU speed, memory, and power constraints.
Application Requirements: Real-time constraints, safety-critical functions, and system reliability.
Optimization Trade-offs: Balance between speed, memory usage, and code complexity.
Sorting Algorithms#
Why?: Organizing data for quick access and efficient processing.
Common Algorithms:
Bubble Sort: Simple but slow; used when resources are extremely limited.
Quick Sort: Fast for larger datasets; used in systems with sufficient memory.
Insertion Sort: Efficient for small or nearly sorted datasets.
Example: Bubble Sort
#include <stdio.h>
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int data[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(data) / sizeof(data[0]);
bubbleSort(data, n);
for (int i = 0; i < n; i++) printf("%d ", data[i]);
return 0;
}
Searching Algorithms#
Why?: Locate specific data in a collection.
Common Algorithms:
Linear Search: Simple, used for unsorted or small datasets.
Binary Search: Efficient for sorted datasets.
Example: Binary Search
#include <stdio.h>
int binarySearch(int arr[], int size, int key) {
int low = 0, high = size - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main() {
int data[] = {1, 2, 3, 4, 5};
int n = sizeof(data) / sizeof(data[0]);
int key = 3;
int result = binarySearch(data, n, key);
printf("Element found at index: %d\n", result);
return 0;
}
Cyclic Redundancy Check (CRC)#
Why?: Error detection in data communication.
Usage: UART, SPI, and CAN bus communication.
Example: Compute CRC-8, CRC-16, or CRC-32 for integrity checks.
#include <stdio.h>
#include <stdint.h>
#define CRC8_POLYNOMIAL 0x07 // Polynomial: x^8 + x^2 + x + 1
#define CRC8_INITIAL 0x00 // Initial CRC value
// Function to calculate CRC-8
uint8_t calculateCRC8(uint8_t* data, size_t length) {
uint8_t crc = CRC8_INITIAL;
for (size_t i = 0; i < length; i++) {
crc ^= data[i]; // XOR byte into the current CRC
for (uint8_t bit = 0; bit < 8; bit++) {
if (crc & 0x80) {
crc = (crc << 1) ^ CRC8_POLYNOMIAL; // Apply polynomial
} else {
crc <<= 1; // Shift left
}
}
}
return crc; // Return the computed CRC
}
int main() {
// Example data to compute CRC
uint8_t data[] = {0x31, 0x32, 0x33, 0x34}; // ASCII for "1234"
size_t length = sizeof(data) / sizeof(data[0]);
// Calculate CRC-8
uint8_t crc = calculateCRC8(data, length);
// Print result
printf("Data: ");
for (size_t i = 0; i < length; i++) {
printf("0x%02X ", data[i]);
}
printf("\nCRC-8: 0x%02X\n", crc);
return 0;
}
Debouncing Algorithms#
Why?: Stabilize input from noisy mechanical switches.
Usage: Button press handling in microcontrollers.
Example: Debouncing a Button
#include <stdbool.h>
#include <stdio.h>
#define DEBOUNCE_DELAY_MS 50
bool isButtonPressed();
bool debounceButton() {
static int lastState = 0;
static unsigned long lastDebounceTime = 0;
int currentState = isButtonPressed();
if (currentState != lastState) {
lastDebounceTime = getMillis(); // Replace with timer function
}
if ((getMillis() - lastDebounceTime) > DEBOUNCE_DELAY_MS) {
return currentState;
}
return lastState;
}
PID Control Algorithm#
Why?: Maintain control of processes like motor speed, temperature, or position.
Usage: Robotics, HVAC systems, and automation.
Example: Basic PID Controller
double computePID(double setpoint, double measuredValue) {
static double previousError = 0;
static double integral = 0;
double kp = 1.0, ki = 0.1, kd = 0.01;
double error = setpoint - measuredValue;
integral += error;
double derivative = error - previousError;
previousError = error;
return kp * error + ki * integral + kd * derivative;
}
Finite State Machines (FSM)#
Why?: Manage state transitions in embedded systems.
Usage: Device modes, communication protocols, and control systems.
Simple Elevator Controller
States:
IDLE: The elevator is stationary and waiting for a command.
MOVING_UP: The elevator is moving up.
MOVING_DOWN: The elevator is moving down.
DOORS_OPEN: The elevator doors are open.
Transitions:
IDLE → MOVING_UP: When the “up” command is received.
IDLE → MOVING_DOWN: When the “down” command is received.
MOVING_UP/DOWN → IDLE: When the destination floor is reached.
IDLE → DOORS_OPEN: When the doors need to open at the destination.
#include <stdio.h>
// Define states
typedef enum {
STATE_IDLE,
STATE_MOVING_UP,
STATE_MOVING_DOWN,
STATE_DOORS_OPEN
} ElevatorState;
// Function prototypes for state actions
void idleStateAction();
void movingUpStateAction();
void movingDownStateAction();
void doorsOpenStateAction();
// FSM function
void elevatorFSM(ElevatorState* currentState, int command);
int main() {
ElevatorState currentState = STATE_IDLE; // Initial state
// Simulate elevator commands
int commands[] = {1, 2, 3, 0, 4}; // 1=Up, 2=Down, 3=Open Doors, 0=Stop
size_t numCommands = sizeof(commands) / sizeof(commands[0]);
for (size_t i = 0; i < numCommands; i++) {
printf("\nProcessing Command: %d\n", commands[i]);
elevatorFSM(¤tState, commands[i]);
}
return 0;
}
// FSM function
void elevatorFSM(ElevatorState* currentState, int command) {
switch (*currentState) {
case STATE_IDLE:
idleStateAction();
if (command == 1) {
*currentState = STATE_MOVING_UP;
} else if (command == 2) {
*currentState = STATE_MOVING_DOWN;
} else if (command == 3) {
*currentState = STATE_DOORS_OPEN;
}
break;
case STATE_MOVING_UP:
movingUpStateAction();
if (command == 0) {
*currentState = STATE_IDLE;
}
break;
case STATE_MOVING_DOWN:
movingDownStateAction();
if (command == 0) {
*currentState = STATE_IDLE;
}
break;
case STATE_DOORS_OPEN:
doorsOpenStateAction();
if (command == 0) {
*currentState = STATE_IDLE;
}
break;
default:
printf("Unknown state!\n");
break;
}
}
// State actions
void idleStateAction() {
printf("Elevator is idle, waiting for a command.\n");
}
void movingUpStateAction() {
printf("Elevator is moving up.\n");
}
void movingDownStateAction() {
printf("Elevator is moving down.\n");
}
void doorsOpenStateAction() {
printf("Elevator doors are open.\n");
}
Signal Filtering Algorithms#
Why?: Reduce noise in sensor data.
Common Techniques:
Moving Average Filter: Average a sliding window of samples.
Low-Pass Filter: Suppress high-frequency noise.
Example: Moving Average Filter
#include <stdio.h>
#define WINDOW_SIZE 5
double movingAverage(double newSample) {
static double buffer[WINDOW_SIZE] = {0};
static int index = 0;
static double sum = 0;
sum -= buffer[index];
buffer[index] = newSample;
sum += newSample;
index = (index + 1) % WINDOW_SIZE;
return sum / WINDOW_SIZE;
}
Example: Low Pass Filter
#include <stdio.h>
#include <math.h>
#define SAMPLING_FREQ 100.0 // Hz
#define CUTOFF_FREQ 10.0 // Hz
// Calculate alpha based on the sampling and cutoff frequencies
double calculateAlpha(double samplingFreq, double cutoffFreq) {
return (2 * M_PI * cutoffFreq) / (samplingFreq + 2 * M_PI * cutoffFreq);
}
// Apply a low-pass filter
void lowPassFilter(double* input, double* output, int length, double alpha) {
output[0] = input[0]; // Initialize first output value
for (int i = 1; i < length; i++) {
output[i] = alpha * input[i] + (1 - alpha) * output[i - 1];
}
}
int main() {
// Example input signal: Simulated noisy data
double inputSignal[10] = {1.0, 1.2, 0.9, 1.3, 0.8, 1.1, 1.0, 1.5, 0.7, 1.0};
double filteredSignal[10] = {0.0};
// Calculate alpha for the low-pass filter
double alpha = calculateAlpha(SAMPLING_FREQ, CUTOFF_FREQ);
printf("Alpha: %f\n", alpha);
// Apply the low-pass filter
lowPassFilter(inputSignal, filteredSignal, 10, alpha);
// Print the results
printf("Filtered Signal:\n");
for (int i = 0; i < 10; i++) {
printf("Sample %d: %f\n", i, filteredSignal[i]);
}
return 0;
}
Median Filter Example
How the Median Filter Works:
A sliding window of a fixed size (e.g., 3, 5, or 7 samples) is applied over the input signal.
The samples within the window are sorted.
The median (middle value) of the sorted samples is taken as the output.
#include <stdio.h>
#define WINDOW_SIZE 3 // Size of the sliding window (must be odd)
// Function to sort an array (helper for finding the median)
void sortArray(int* arr, int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = i + 1; j < size; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
// Apply the median filter
void medianFilter(int* input, int* output, int length) {
int window[WINDOW_SIZE]; // Temporary window for sorting
for (int i = 0; i < length; i++) {
// Populate the sliding window
for (int j = 0; j < WINDOW_SIZE; j++) {
int index = i - WINDOW_SIZE / 2 + j;
// Handle edge cases by extending the edge values
if (index < 0) {
window[j] = input[0];
} else if (index >= length) {
window[j] = input[length - 1];
} else {
window[j] = input[index];
}
}
// Sort the window and find the median
sortArray(window, WINDOW_SIZE);
output[i] = window[WINDOW_SIZE / 2];
}
}
int main() {
// Example input signal (noisy data)
int inputSignal[] = {10, 20, 80, 30, 90, 40, 70, 50};
int length = sizeof(inputSignal) / sizeof(inputSignal[0]);
// Output signal
int filteredSignal[length];
// Apply the median filter
medianFilter(inputSignal, filteredSignal, length);
// Print the results
printf("Input Signal: ");
for (int i = 0; i < length; i++) {
printf("%d ", inputSignal[i]);
}
printf("\nFiltered Signal: ");
for (int i = 0; i < length; i++) {
printf("%d ", filteredSignal[i]);
}
return 0;
}
Scheduling Algorithms#
Why?: Efficiently manage task execution in real-time systems.
Common Techniques:
Round-Robin: Tasks executed in a cyclic order.
Priority-Based: Higher-priority tasks preempt lower-priority ones.
Round-Robin Scheduling Example
Concept:
In a Round-Robin scheduler, tasks are executed sequentially in a cyclic manner.
Each task gets an equal amount of CPU time, ensuring fairness.
#include <stdio.h>
#include <stdbool.h>
// Define task functions
void task1() { printf("Task 1 executed\n"); }
void task2() { printf("Task 2 executed\n"); }
void task3() { printf("Task 3 executed\n"); }
// Task function pointer array
void (*tasks[])(void) = {task1, task2, task3};
#define NUM_TASKS (sizeof(tasks) / sizeof(tasks[0]))
int main() {
int currentTask = 0;
// Simulate a scheduler loop
for (int tick = 0; tick < 10; tick++) { // Simulate 10 ticks
printf("Tick %d: ", tick);
tasks[currentTask](); // Execute the current task
currentTask = (currentTask + 1) % NUM_TASKS; // Move to the next task
}
return 0;
}
Round-Robin:
Tasks are executed in a cyclic order.
Simple and fair for equal-priority tasks.
Does not handle tasks with varying urgency.
Priority-Based Scheduling Example
Concept:
Tasks are assigned priorities, and higher-priority tasks are executed before lower-priority tasks.
Priority can be static or dynamic.
#include <stdio.h>
// Task function prototypes
void highPriorityTask() { printf("High-priority task executed\n"); }
void mediumPriorityTask() { printf("Medium-priority task executed\n"); }
void lowPriorityTask() { printf("Low-priority task executed\n"); }
// Define tasks with priorities
typedef struct {
void (*taskFunc)(void); // Task function pointer
int priority; // Priority (lower number = higher priority)
} Task;
#define NUM_TASKS 3
Task taskList[NUM_TASKS] = {
{lowPriorityTask, 3},
{highPriorityTask, 1},
{mediumPriorityTask, 2}
};
// Scheduler function
void priorityScheduler(Task* tasks, int numTasks) {
// Sort tasks by priority (bubble sort for simplicity)
for (int i = 0; i < numTasks - 1; i++) {
for (int j = 0; j < numTasks - i - 1; j++) {
if (tasks[j].priority > tasks[j + 1].priority) {
Task temp = tasks[j];
tasks[j] = tasks[j + 1];
tasks[j + 1] = temp;
}
}
}
// Execute tasks in priority order
for (int i = 0; i < numTasks; i++) {
tasks[i].taskFunc();
}
}
int main() {
printf("Executing tasks based on priority:\n");
priorityScheduler(taskList, NUM_TASKS);
return 0;
}
Priority-Based:
Tasks are sorted and executed based on their priority.
Ensures that high-priority tasks are executed first.
More suitable for real-time systems.
Memory Management Algorithms#
Why?: Optimize memory usage.
Usage: Memory pooling, fragmentation management in embedded systems without dynamic memory.
Example: Fixed-size memory allocator.
Memory Pooling
Divides memory into fixed-size blocks (pools).
Pros: Fast allocation and deallocation, no fragmentation.
Cons: Wastes memory if block sizes don’t fit the use case.
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#define POOL_SIZE 1024 // Total pool size in bytes
#define BLOCK_SIZE 32 // Size of each block in bytes
#define NUM_BLOCKS (POOL_SIZE / BLOCK_SIZE) // Number of blocks
// Memory pool structure
typedef struct {
uint8_t memory[POOL_SIZE];
bool freeBlocks[NUM_BLOCKS];
} MemoryPool;
// Initialize the memory pool
void initMemoryPool(MemoryPool* pool) {
memset(pool->memory, 0, POOL_SIZE);
memset(pool->freeBlocks, true, NUM_BLOCKS * sizeof(bool));
}
// Allocate a block from the pool
void* allocateBlock(MemoryPool* pool) {
for (int i = 0; i < NUM_BLOCKS; i++) {
if (pool->freeBlocks[i]) {
pool->freeBlocks[i] = false;
return &pool->memory[i * BLOCK_SIZE];
}
}
return NULL; // No free blocks
}
// Free a block in the pool
void freeBlock(MemoryPool* pool, void* block) {
uintptr_t offset = (uintptr_t)block - (uintptr_t)pool->memory;
if (offset % BLOCK_SIZE == 0 && offset / BLOCK_SIZE < NUM_BLOCKS) {
pool->freeBlocks[offset / BLOCK_SIZE] = true;
}
}
// Test the memory pool
int main() {
MemoryPool pool;
initMemoryPool(&pool);
// Allocate three blocks
void* block1 = allocateBlock(&pool);
void* block2 = allocateBlock(&pool);
void* block3 = allocateBlock(&pool);
printf("Block 1 address: %p\n", block1);
printf("Block 2 address: %p\n", block2);
printf("Block 3 address: %p\n", block3);
// Free the second block
freeBlock(&pool, block2);
printf("Block 2 freed.\n");
// Allocate another block
void* block4 = allocateBlock(&pool);
printf("Block 4 address: %p\n", block4);
return 0;
}
Memory Pool:
A fixed-size array represents the memory pool (memory).
An array of booleans (freeBlocks) tracks the allocation status of each block.
Allocation:
The first free block is located and returned to the caller.
The corresponding freeBlocks entry is marked as false.
Deallocation:
The block is marked as free by setting the corresponding freeBlocks entry to true.
Advantages:
Deterministic allocation and deallocation.
No fragmentation.
Compression Algorithms#
Why?: Reduce data size for storage or transmission.
Usage: Logging systems, telemetry, or wireless communication.
Common Algorithms:
Run-Length Encoding (RLE).
Huffman Encoding.
Example: Run-Length Encoding (RLE)
How It Works:
RLE replaces consecutive repeated characters (or data) with a single character followed by its count.
Example:
Input: AAAABBBCCDAA
Compressed: A4B3C2D1A2
#include <stdio.h>
#include <string.h>
// Function to perform Run-Length Encoding
void runLengthEncode(const char* input, char* output) {
int len = strlen(input);
int index = 0;
for (int i = 0; i < len; i++) {
char currentChar = input[i];
int count = 1;
// Count consecutive occurrences of the character
while (i + 1 < len && input[i] == input[i + 1]) {
count++;
i++;
}
// Store the character and its count in the output
output[index++] = currentChar;
output[index++] = count + '0'; // Convert count to character
}
output[index] = '\0'; // Null-terminate the output string
}
int main() {
const char* input = "AAAABBBCCDAA";
char output[50]; // Ensure the output buffer is large enough
printf("Input: %s\n", input);
// Perform Run-Length Encoding
runLengthEncode(input, output);
printf("Compressed: %s\n", output);
return 0;
}
Explanation:
Input:
The string input contains the data to be compressed.
Count Consecutive Characters:
Use a loop to traverse the input string.
Count consecutive occurrences of each character.
Store Character and Count:
Append the character and its count to the output string.
Convert the count to a character using + ‘0’.
Output:
The compressed string is null-terminated and ready for storage or transmission.
Cryptography Algorithms#
Why?: Ensure secure communication.
Usage: Encrypt sensitive data or communication protocols.
Common Algorithms:
AES (Advanced Encryption Standard).
RSA for key exchange.
Example: AES-128 Encryption in Embedded C
AES Basics:
AES is a symmetric encryption algorithm, meaning the same key is used for encryption and decryption.
AES-128 uses a 128-bit key.
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
// Example AES S-Box for substitution step
const uint8_t sbox[256] = {
0x63, 0x7c, 0x77, 0x7b, /* ... omitted for brevity ... */ 0xbb, 0x16
};
// Function to perform a simple substitution (partial AES example)
void aesSubBytes(uint8_t* state) {
for (int i = 0; i < 16; i++) {
state[i] = sbox[state[i]];
}
}
// Dummy AES encryption function for demonstration
void aesEncrypt(uint8_t* plaintext, uint8_t* key, uint8_t* ciphertext) {
uint8_t state[16];
memcpy(state, plaintext, 16); // Copy plaintext to state
// AddRoundKey (simplified as XOR with the key)
for (int i = 0; i < 16; i++) {
state[i] ^= key[i];
}
// SubBytes step
aesSubBytes(state);
// Copy state to ciphertext
memcpy(ciphertext, state, 16);
}
int main() {
// Example 16-byte plaintext and key
uint8_t plaintext[16] = {
0x32, 0x43, 0xf6, 0xa8, 0x88, 0x5a, 0x30, 0x8d,
0x31, 0x31, 0x98, 0xa2, 0xe0, 0x37, 0x07, 0x34
};
uint8_t key[16] = {
0x2b, 0x7e, 0x15, 0x16, 0x28, 0xae, 0xd2, 0xa6,
0xab, 0xf7, 0x45, 0x25, 0x87, 0x8a, 0xf5, 0x32
};
uint8_t ciphertext[16];
printf("Plaintext: ");
for (int i = 0; i < 16; i++) printf("%02x ", plaintext[i]);
printf("\n");
// Encrypt the plaintext
aesEncrypt(plaintext, key, ciphertext);
printf("Ciphertext: ");
for (int i = 0; i < 16; i++) printf("%02x ", ciphertext[i]);
printf("\n");
return 0;
}
Explanation:
AES Basics:
The algorithm operates on a 4x4 matrix (128 bits).
Includes steps like AddRoundKey, SubBytes, ShiftRows, and MixColumns.
This example implements a simplified version with SubBytes and AddRoundKey.
SubBytes:
Each byte in the state matrix is substituted using a predefined S-Box.
AddRoundKey:
Each byte of the state matrix is XOR-ed with a key byte.
Input/Output:
Input: 16-byte plaintext and 16-byte key.
Output: 16-byte ciphertext.
Lightweight Cryptography Alternatives:
For resource-constrained systems, consider:
Speck/Simon:
Designed by the NSA for lightweight applications.
ChaCha20:
Stream cipher with efficient implementation.
TinyAES:
A small and portable AES implementation for embedded systems.
Advanced
SHA-256 Implementation
Using a Lightweight Library
SHA-256 implementations can be complex due to mathematical operations. Below is an example using the mbedTLS library (commonly used in embedded systems).
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "mbedtls/sha256.h"
int main() {
// Input data
const char *input = "Hello, Embedded World!";
uint8_t hash[32]; // 256-bit hash
// Compute SHA-256 hash
mbedtls_sha256_context ctx;
mbedtls_sha256_init(&ctx);
mbedtls_sha256_starts_ret(&ctx, 0); // 0 for SHA-256
mbedtls_sha256_update_ret(&ctx, (const unsigned char *)input, strlen(input));
mbedtls_sha256_finish_ret(&ctx, hash);
mbedtls_sha256_free(&ctx);
// Print the hash
printf("Input: %s\n", input);
printf("SHA-256 Hash: ");
for (int i = 0; i < 32; i++) {
printf("%02x", hash[i]);
}
printf("\n");
return 0;
}
Using Lightweight RSA Library
This example encrypts and decrypts a small message using mbedTLS.
#include <stdio.h>
#include "mbedtls/rsa.h"
#include "mbedtls/ctr_drbg.h"
#include "mbedtls/entropy.h"
int main() {
const char *message = "Hello, RSA!";
uint8_t encrypted[256];
uint8_t decrypted[256];
size_t olen;
// Initialize RSA context
mbedtls_rsa_context rsa;
mbedtls_rsa_init(&rsa, MBEDTLS_RSA_PKCS_V15, 0);
// Generate RSA keys
mbedtls_ctr_drbg_context ctr_drbg;
mbedtls_entropy_context entropy;
mbedtls_entropy_init(&entropy);
mbedtls_ctr_drbg_init(&ctr_drbg);
mbedtls_ctr_drbg_seed(&ctr_drbg, mbedtls_entropy_func, &entropy, NULL, 0);
mbedtls_rsa_gen_key(&rsa, mbedtls_ctr_drbg_random, &ctr_drbg, 2048, 65537);
// Encrypt message
mbedtls_rsa_pkcs1_encrypt(&rsa, mbedtls_ctr_drbg_random, &ctr_drbg, MBEDTLS_RSA_PUBLIC,
strlen(message), (const unsigned char *)message, encrypted);
printf("Encrypted Message: ");
for (size_t i = 0; i < rsa.len; i++) {
printf("%02x", encrypted[i]);
}
printf("\n");
// Decrypt message
mbedtls_rsa_pkcs1_decrypt(&rsa, mbedtls_ctr_drbg_random, &ctr_drbg, MBEDTLS_RSA_PRIVATE,
&olen, encrypted, decrypted, sizeof(decrypted));
printf("Decrypted Message: %s\n", decrypted);
// Free resources
mbedtls_rsa_free(&rsa);
mbedtls_ctr_drbg_free(&ctr_drbg);
mbedtls_entropy_free(&entropy);
return 0;
}
Explanation:
SHA-256:
Uses mbedTLS’s mbedtls_sha256_xxx functions to process the input.
Produces a 256-bit hash.
RSA:
Generates a 2048-bit RSA key pair using mbedtls_rsa_gen_key.
Encrypts the message with the public key using mbedtls_rsa_pkcs1_encrypt.
Decrypts the message with the private key using mbedtls_rsa_pkcs1_decrypt.
Applications in Embedded Systems:
SHA-256:
Verify firmware integrity.
Generate digital signatures for authentication.
RSA:
Secure key exchange in IoT devices.
Protect sensitive communication.
Repo location: Mbed-TLS/mbedtls
Data Encoding/Decoding Algorithms#
Why?: Efficient data transfer.
Usage: Base64 encoding for binary data transmission, Manchester encoding for signals.
Base64 Encoding/Decoding
Use Case:
Encode binary data into ASCII characters.
Common in email, JSON, and data transmission.
#include <stdio.h>
#include <string.h>
// Base64 character set
const char base64_table[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
// Function to encode data to Base64
void base64_encode(const unsigned char* input, int length, char* output) {
int i, j;
for (i = 0, j = 0; i < length;) {
uint32_t octet_a = i < length ? input[i++] : 0;
uint32_t octet_b = i < length ? input[i++] : 0;
uint32_t octet_c = i < length ? input[i++] : 0;
uint32_t triple = (octet_a << 16) | (octet_b << 8) | octet_c;
output[j++] = base64_table[(triple >> 18) & 0x3F];
output[j++] = base64_table[(triple >> 12) & 0x3F];
output[j++] = (i > length + 1) ? '=' : base64_table[(triple >> 6) & 0x3F];
output[j++] = (i > length) ? '=' : base64_table[triple & 0x3F];
}
output[j] = '\0'; // Null-terminate the output
}
int main() {
const char* input = "Hello, World!";
char output[25]; // Make sure this is large enough for the encoded data
base64_encode((const unsigned char*)input, strlen(input), output);
printf("Input: %s\n", input);
printf("Base64 Encoded: %s\n", output);
return 0;
}
Hex Encoding/Decoding
Use Case:
Represent binary data as hexadecimal strings.
Common for debugging, checksum verification, and low-level communication.
Hex Encoding Example:
#include <stdio.h>
// Function to encode data to Hex
void hex_encode(const unsigned char* input, int length, char* output) {
const char hex_table[] = "0123456789ABCDEF";
for (int i = 0; i < length; i++) {
output[i * 2] = hex_table[(input[i] >> 4) & 0xF];
output[i * 2 + 1] = hex_table[input[i] & 0xF];
}
output[length * 2] = '\0'; // Null-terminate the output
}
int main() {
const char* input = "Hello, World!";
char output[50]; // Ensure enough space for the encoded data
hex_encode((const unsigned char*)input, strlen(input), output);
printf("Input: %s\n", input);
printf("Hex Encoded: %s\n", output);
return 0;
}
Manchester Encoding
Use Case:
Encode data for reliable transmission, commonly used in networking and RFID communication.
Manchester Encoding Example:
#include <stdio.h>
// Function to encode a byte using Manchester encoding
void manchester_encode(unsigned char byte, char* output) {
for (int i = 0; i < 8; i++) {
if (byte & (1 << (7 - i))) {
// Logic 1: High-to-Low
output[i * 2] = '1';
output[i * 2 + 1] = '0';
} else {
// Logic 0: Low-to-High
output[i * 2] = '0';
output[i * 2 + 1] = '1';
}
}
output[16] = '\0'; // Null-terminate the output
}
int main() {
unsigned char input = 0xA3; // Example byte (10100011 in binary)
char output[17]; // 16 bits + null terminator
manchester_encode(input, output);
printf("Input Byte: 0x%X\n", input);
printf("Manchester Encoded: %s\n", output);
return 0;
}
Applications of Encoding/Decoding:
Base64:
Encoding binary data for HTTP, JSON, or XML.
Hex Encoding:
Debugging and low-level communication protocols.
Manchester Encoding:
Reliable data transmission over noisy channels.
Advanced
Using a Lightweight JSON Library
For embedded systems, lightweight JSON libraries like cJSON or MicroJSON are ideal because they minimize memory usage.
Below is an example using the cJSON library.
JSON Serialization#
Scenario: Serialize data for a device’s configuration into a JSON string.
#include <stdio.h>
#include <stdlib.h>
#include "cJSON.h"
int main() {
// Create a JSON object
cJSON *root = cJSON_CreateObject();
// Add key-value pairs
cJSON_AddStringToObject(root, "device_name", "SensorNode123");
cJSON_AddNumberToObject(root, "battery_level", 78);
cJSON_AddBoolToObject(root, "is_active", 1);
// Serialize to JSON string
char *json_string = cJSON_Print(root);
printf("Serialized JSON:\n%s\n", json_string);
// Free memory
cJSON_Delete(root);
free(json_string);
return 0;
}
JSON Parsing
Scenario: Parse incoming JSON data representing device status.
#include <stdio.h>
#include <stdlib.h>
#include "cJSON.h"
int main() {
// Example JSON string
const char *json_string = "{\"device_name\":\"SensorNode123\",\"battery_level\":78,\"is_active\":true}";
// Parse JSON string
cJSON *root = cJSON_Parse(json_string);
if (!root) {
printf("Error parsing JSON!\n");
return -1;
}
// Extract data
const cJSON *device_name = cJSON_GetObjectItemCaseSensitive(root, "device_name");
const cJSON *battery_level = cJSON_GetObjectItemCaseSensitive(root, "battery_level");
const cJSON *is_active = cJSON_GetObjectItemCaseSensitive(root, "is_active");
// Print extracted data
if (cJSON_IsString(device_name)) {
printf("Device Name: %s\n", device_name->valuestring);
}
if (cJSON_IsNumber(battery_level)) {
printf("Battery Level: %d%%\n", battery_level->valueint);
}
if (cJSON_IsBool(is_active)) {
printf("Device Active: %s\n", cJSON_IsTrue(is_active) ? "Yes" : "No");
}
// Free memory
cJSON_Delete(root);
return 0;
}
Explanation:
Serialization:
Create a JSON object using cJSON_CreateObject.
Add fields with cJSON_AddStringToObject, cJSON_AddNumberToObject, or cJSON_AddBoolToObject.
Convert the JSON object to a string with cJSON_Print.
Parsing:
Parse a JSON string into a JSON object with cJSON_Parse.
Access fields with cJSON_GetObjectItemCaseSensitive.
Validate and extract data using functions like cJSON_IsString and
cJSON_IsNumber.
Applications in Embedded Systems:
Configuration Files:
Load and save device configurations in JSON format.
Communication:
Send sensor data or receive commands in JSON format over HTTP, MQTT, or WebSocket.
Debugging:
Log system states in a structured JSON format.
Integration in Embedded Systems:
Download the cJSON library: cJSON GitHub Repository.
Include the library in your embedded project.
Ensure enough memory for JSON strings, especially for devices with constrained resources.
**
**