Hamming Error Correction

hamming.c

// Reference: https://www.geeksforgeeks.org/hamming-code-in-computer-network/

#include <inttypes.h>
#include <stdio.h>
#include <assert.h>


#define PRINT_BITS(x)                                                          \
	for (int i = sizeof(x) << 3; i; i--)                                   \
		putchar('0' + (((x) >> (i - 1)) & 1));                         \
	putchar('\n');


int8_t hamming_encode(int32_t *hamming, int32_t raw, int8_t n_bits) {
	int8_t raw_i = 0;
	int8_t hamming_i = 0;
	int8_t out_i = 0;
	int8_t out_n;
	int8_t hamming_n;

	*hamming = 0;

	// Put raw data in
	while (raw_i < n_bits) {
		if (out_i + 1 == 1 << hamming_i) {
			hamming_i++;
		} else {
			*hamming |= (raw & (1 << raw_i)) << (out_i - raw_i);
			raw_i++;
		}
		out_i++;
	}
	out_n = out_i;
	hamming_n = hamming_i;

	// Engrave hamming bits
	for (hamming_i = 0; hamming_i < hamming_n; hamming_i++) {
		int8_t hamming_parity = 0;
		for (int8_t i = 0; i < out_n; i++) {
			if ((i + 1) & (1 << hamming_i) &&
			    (i + 1) != 1 << hamming_i) {
				hamming_parity += (*hamming & (1 << i)) >> i;
			}
		}
		*hamming |= (hamming_parity % 2) << ((1 << hamming_i) - 1);
	}
	return out_n;
}

int8_t hamming_decode(int32_t *raw, int32_t hamming, int8_t n_bits) {
	int8_t hamming_i = 0;
	int8_t raw_i = 0;
	int8_t swap_bit_index = 0;

	// Find problematic bit index
	for (hamming_i = 0; (1 << hamming_i) < n_bits; hamming_i++) {
		int8_t hamming_parity = 0;
		for (int8_t i = 0; i < n_bits; i++) {
			if ((i + 1) & (1 << hamming_i)) {
				hamming_parity += (hamming & (1 << i)) >> i;
			}
		}
		swap_bit_index |= (hamming_parity % 2) << hamming_i;
	}

	// Fix the problematic bit
	if (swap_bit_index) {
		hamming ^= (1 << (swap_bit_index - 1));
	}

	// Write data
	*raw = 0;
	hamming_i = 0;
	for (int8_t out_i = 0; out_i < n_bits; out_i++) {
		if (out_i + 1 == 1 << hamming_i) {
			hamming_i++;
		} else {
			*raw |= (hamming & (1 << out_i)) >> (out_i - raw_i);
			raw_i++;
		}
	}

	return raw_i;
}

int main() {
	int32_t hamming;
	int32_t raw = 0b1011001;
	int8_t n_bits = 7;
	int8_t length_hamming;
	int8_t length_raw;
	int32_t raw_decoded;

	// Basic encode
	length_hamming = hamming_encode(&hamming, raw, n_bits);
	assert(0b10101001110 == hamming);
	assert(11 == length_hamming);

	// Basic decode
	length_raw = hamming_decode(&raw_decoded, hamming, length_hamming);
	assert(0b1011001 == raw_decoded);
	assert(n_bits == length_raw);

	// Flip random bit
	hamming ^= 1 << 5;
	length_raw = hamming_decode(&raw_decoded, hamming, length_hamming);
	assert(0b1011001 == raw_decoded);
	assert(n_bits == length_raw);
	hamming ^= 1 << 5;

	// Flip random bit
	hamming ^= 1 << 2;
	length_raw = hamming_decode(&raw_decoded, hamming, length_hamming);
	assert(0b1011001 == raw_decoded);
	assert(n_bits == length_raw);
	hamming ^= 1 << 2;

	// Short simple
	n_bits = 4;
	raw = 5;
	length_hamming = hamming_encode(&hamming, raw, n_bits);
	length_raw = hamming_decode(&raw_decoded, hamming, length_hamming);
	assert(raw == raw_decoded);

	// Short error
	n_bits = 4;
	raw = 5;
	length_hamming = hamming_encode(&hamming, raw, n_bits);
	hamming ^= 1 << 2;
	length_raw = hamming_decode(&raw_decoded, hamming, length_hamming);
	assert(raw == raw_decoded);

	return 0;
}