Viterbi

Implementation

Modern C

/*
 * Anders Sikvall 2026 Version 1.0
 * <anders@sikvall.se>
 * 
 * Implementation i C av en standard Viterbi-algoritm som används bl.a. av 
 * Qualcomm och NASA och är välpublicerad.
 *
 * PUBLIC DOMAIN FOR EDUCATIONAL PURPOSES
 *
 * Kompilera med gcc -o viterbi viterbi.c
 *
 * ANVÄNDNING
 *         viterbi -e <indatastream >utdatastream   Kodar <indatastream till >utdatastream
 *         viterbi -d <indatastream >utdatastream   Avkodar <indatastream till >utdatastream
 *         viterbi -t                               Utför en intern test på 64 randomiserade oktetter
 *         viterbi -h                               Visar en kort hjälptext
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <time.h>

#define K 7
#define NUM_STATES (1 << (K - 1))

// Standard NASA/Qualcomm-polynom (Rate 1/2, K=7)
const uint8_t POLY_G0 = 0x4F; // 1001111 i binärt
const uint8_t POLY_G1 = 0x6D; // 1101101 i binärt

// Hårdvaruoptimerad paritetsberäkning
static inline uint8_t parity(uint8_t x) {
    return __builtin_parity(x) & 1;
}

// ============================================================================
// KODARE (-e)
// ============================================================================
void encode(FILE *in, FILE *out) {
    uint8_t encoder_state = 0;
    uint8_t out_byte = 0;
    int bit_count = 0;
    int ch;

    while ((ch = fgetc(in)) != EOF) {
        // Processa varje bit från MSB till LSB
        for (int i = 7; i >= 0; i--) {
            uint8_t bit = (ch >> i) & 1;
            uint8_t current_word = (encoder_state << 1) | bit;

            // Beräkna de två paritetsbitarna
            uint8_t out0 = parity(current_word & POLY_G0);
            uint8_t out1 = parity(current_word & POLY_G1);

            // Packa bit 0
            out_byte = (out_byte << 1) | out0;
            bit_count++;
            if (bit_count == 8) {
                fputc(out_byte, out);
                out_byte = 0;
                bit_count = 0;
            }

            // Packa bit 1
            out_byte = (out_byte << 1) | out1;
            bit_count++;
            if (bit_count == 8) {
                fputc(out_byte, out);
                out_byte = 0;
                bit_count = 0;
            }

            // Uppdatera skiftregistret (behåll K-1 bitar)
            encoder_state = current_word & (NUM_STATES - 1);
        }
    }
    
    // Töm resterande bitar i sista byten vid behov
    if (bit_count > 0) {
        out_byte <<= (8 - bit_count);
        fputc(out_byte, out);
    }
}

// ============================================================================
// AVKODARE (-d)
// ============================================================================
void decode(FILE *in, FILE *out) {
    size_t history_capacity = 1024;
    size_t step = 0;

    uint8_t (*history)[NUM_STATES] = malloc(history_capacity * sizeof(*history));
    if (!history) {
        return;
    }

    uint32_t path_metrics[NUM_STATES];
    uint32_t old_metrics[NUM_STATES];
    
    // Initiera felkostnader (tillstånd 0 är garanterad start)
    for (int i = 1; i < NUM_STATES; i++) {
        path_metrics[i] = 1e6;
    }
    path_metrics[0] = 0;

    int ch;

    // 1. Framåtpass (Forward Pass / Add-Compare-Select)
    while ((ch = fgetc(in)) != EOF) {
        for (int bit_pair = 3; bit_pair >= 0; bit_pair--) {
            uint8_t b0 = (ch >> (bit_pair * 2 + 1)) & 1;
            uint8_t b1 = (ch >> (bit_pair * 2)) & 1;

            // Expandera historikbufferten dynamiskt om det behövs
            if (step >= history_capacity) {
                history_capacity *= 2;
                uint8_t (*new_history)[NUM_STATES] = realloc(history, history_capacity * sizeof(*history));
                if (!new_history) {
                    free(history);
                    return;
                }
                history = new_history;
            }

            memcpy(old_metrics, path_metrics, sizeof(path_metrics));

            // Gå igenom alla möjliga måltillstånd
            for (int state = 0; state < NUM_STATES; state++) {
                int prev0 = state >> 1;
                int prev1 = prev0 | (NUM_STATES >> 1);
                uint8_t input_bit = state & 1;

                // Väg 0
                uint8_t word0 = (prev0 << 1) | input_bit;
                uint8_t exp0_0 = parity(word0 & POLY_G0);
                uint8_t exp0_1 = parity(word0 & POLY_G1);
                uint32_t cost0 = (exp0_0 != b0) + (exp0_1 != b1);

                // Väg 1
                uint8_t word1 = (prev1 << 1) | input_bit;
                uint8_t exp1_0 = parity(word1 & POLY_G0);
                uint8_t exp1_1 = parity(word1 & POLY_G1);
                uint32_t cost1 = (exp1_0 != b0) + (exp1_1 != b1);

                uint32_t m0 = old_metrics[prev0] + cost0;
                uint32_t m1 = old_metrics[prev1] + cost1;

                // Välj den bästa överlevande vägen
                if (m0 <= m1) {
                    path_metrics[state] = m0;
                    history[step][state] = 0;
                } else {
                    path_metrics[state] = m1;
                    history[step][state] = 1;
                }
            }
            step++;
        }
    }

    if (step == 0) {
        free(history);
        return;
    }

    // 2. Hitta bästa sluttillstånd (lägsta metric)
    int curr_state = 0;
    uint32_t min_m = path_metrics[0];
    for (int i = 1; i < NUM_STATES; i++) {
        if (path_metrics[i] < min_m) {
            min_m = path_metrics[i];
            curr_state = i;
        }
    }

    // 3. Bakåtspårning (Traceback)
    uint8_t *decoded_bits = malloc(step);
    if (!decoded_bits) {
        free(history);
        return;
    }

    for (int s = (int)step - 1; s >= 0; s--) {
        decoded_bits[s] = curr_state & 1;
        int decision = history[s][curr_state];
        int prev0 = curr_state >> 1;
        
        if (decision == 0) {
            curr_state = prev0;
        } else {
            curr_state = prev0 | (NUM_STATES >> 1);
        }
    }

    // 4. Återpacka till bytes och skriv ut till strömmen
    uint8_t current_byte = 0;
    for (size_t i = 0; i < step; i++) {
        current_byte = (current_byte << 1) | decoded_bits[i];
        if ((i + 1) % 8 == 0) {
            fputc(current_byte, out);
            current_byte = 0;
        }
    }

    free(decoded_bits);
    free(history);
}

// ============================================================================
// INTERNT TEST (-t)
// ============================================================================
void run_test(void) {
    printf("[*] Startar internt test (64 bytes randomiserat data)...\n");
    
    uint8_t original_data[64];
    srand((unsigned int)time(NULL));
    for (int i = 0; i < 64; i++) {
        original_data[i] = rand() % 256;
    }

    FILE *orig_stream = tmpfile();
    FILE *encoded_stream = tmpfile();
    FILE *decoded_stream = tmpfile();

    if (!orig_stream || !encoded_stream || !decoded_stream) {
        fprintf(stderr, "Kunde inte skapa temporära filer.\n");
        return;
    }

    fwrite(original_data, 1, 64, orig_stream);
    rewind(orig_stream);

    encode(orig_stream, encoded_stream);
    rewind(encoded_stream);

    decode(encoded_stream, decoded_stream);
    rewind(decoded_stream);

    uint8_t final_data[64];
    size_t read_bytes = fread(final_data, 1, 64, decoded_stream);

    bool success = true;
    if (read_bytes != 64) {
        printf("[FAIL] Avkodade fel antal bytes: %zu (förväntade 64)\n", read_bytes);
        success = false;
    } else {
        for (int i = 0; i < 64; i++) {
            if (original_data[i] != final_data[i]) {
                printf("[FAIL] Diff vid byte %d: Org=0x%02X, Avkodad=0x%02X\n", i, original_data[i], final_data[i]);
                success = false;
                break;
            }
        }
    }

    fclose(orig_stream);
    fclose(encoded_stream);
    fclose(decoded_stream);

    if (success) {
        printf("[SUCCESS] Testet lyckades! Allt data matchar perfekt.\n");
    }
}

// ============================================================================
// HJÄLPTEXT OCH MAIN
// ============================================================================
void print_help(const char *prog_name) {
    printf("Användning: %s [option]\n", prog_name);
    printf("Optioner:\n");
    printf("  -e <infil >utfil   Kodar infil till utfil (Rate 1/2, K=7)\n");
    printf("  -d <infil >utfil   Avkodar infil till utfil med Viterbi\n");
    printf("  -h                 Visar denna hjälptext\n");
    printf("  -t                 Kör internt test med 64 bytes slumpdata\n");
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        print_help(argv[0]);
        return EXIT_FAILURE;
    }

    if (strcmp(argv[1], "-e") == 0) {
        encode(stdin, stdout);
    } else if (strcmp(argv[1], "-d") == 0) {
        decode(stdin, stdout);
    } else if (strcmp(argv[1], "-h") == 0) {
        print_help(argv[0]);
    } else if (strcmp(argv[1], "-t") == 0) {
        run_test();
    } else {
        fprintf(stderr, "Fel: Okänd parameter '%s'\n", argv[1]);
        print_help(argv[0]);
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}