#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

uint8_t hamming47(uint8_t four_bits) {
    return (__builtin_parity(four_bits & 0b1101) << 7) |
           (__builtin_parity(four_bits & 0b1011) << 6) |
           ((four_bits & 0b1000) << 5) |
           (__builtin_parity(four_bits & 0b0111) << 4) |
           ((four_bits & 0b0100) << 3) | ((four_bits & 0b0010) << 2) |
           ((four_bits & 0b0001) << 1);
}

void encode(void *data, void *encoded, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        uint8_t byte = ((uint8_t *)data)[i];
        ((uint8_t *)encoded)[2 * i] = hamming47(byte & 0b1111);
        ((uint8_t *)encoded)[2 * i + 1] = hamming47(byte >> 4);
    }
}

uint8_t hamming_decode(uint8_t enc) {
    if (!(__builtin_parity(enc & 0b01100110) |
          __builtin_parity(enc & 0b01100110) |
          __builtin_parity(enc & 0b00011110))) {
        return ((enc & 0b00001110) >> 1) | ((enc & 0b00100000) >> 2);
    } else {
        int err0 = __builtin_parity(enc & 0b10101010);
        int err1 = __builtin_parity(enc & 0b01100110);
        int err3 = __builtin_parity(enc & 0b00011110);
        int ind = err0 + (err1 << 1) + (err3 << 2) - 1;
        uint8_t fixed_enc = enc ^ (ind << 1);
        return ((fixed_enc & 0b00001110) >> 1) |
               ((fixed_enc & 0b00100000) >> 2);
    }
}

void decode(void *encoded, void *data, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        ((uint8_t *)data)[2 * i] = hamming_decode(((uint8_t *)encoded)[2 * i]) |
                  (hamming_decode(((uint8_t *)encoded)[2 * i + 1]) << 4);
    }
}

void generate_random_data(void *buffer, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        ((uint8_t *)buffer)[i] = rand();
    }
}

void bitflip(void *buffer, size_t n) {
    if (rand() % n) {
        ((uint8_t *)buffer)[rand() % n] ^= (1 << (rand() % 8));
    }
}

void test() {
    const size_t n = 1000;
    void *data = malloc(n);
    generate_random_data(data, n);

    void *encoded_buffer = malloc(2 * n);
    encode(data, encoded_buffer, n);
    bitflip(encoded_buffer, n);

    void *decoded_buffer = malloc(n);
    decode(encoded_buffer, decoded_buffer, n);
    assert(memcmp(data, decoded_buffer, n) == 0);
    free(encoded_buffer);
    free(data);
    free(decoded_buffer);
}

int main() {
    size_t counter = 0;
    for (int _ = 0; _ < 1000; ++_) {
        test();
        printf("%zu tests passed...\n", ++counter);
    }
}