モールス符号のデコード関数

Gan 8月 21, 2024No Comments

モールス符号のデコーダを書いてみました。初見でこれの原理がぱっとわかったらちょっとすごいです。

/* Advance to the next state for an input, '.', '-'. or 0 (terminal).
 * The initial state is zero. Returns the next state, or the result:
 *   < 0 when more input is needed (i.e. next state)
 *   = 0 for invalid input
 *   > 0 the ASCII result
 */
int morse_decode(int state, int c) {
    static const unsigned char table[] = {
        0xac, 0xca, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
        0x00, 0x00, 0x80, 0x86, 0x92, 0x80, 0x94, 0x82, 0x80, 0x80,
        0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x46, 0x50, 0x0e, 0x00,
        0x00, 0x00, 0x26, 0x52, 0x34, 0x24, 0x00, 0x00, 0x56, 0x44,
        0x0c, 0x0a, 0x48, 0x4c, 0x00, 0x04, 0x28, 0x54, 0x00, 0x00,
        0x30, 0x40, 0x2a, 0x38, 0x18, 0x1a, 0x00, 0x00, 0x00, 0x00,
        0x3a, 0x00, 0x32, 0x4e, 0x3e, 0x3c, 0x2e, 0x16, 0x00, 0x08,
        0x42, 0x36, 0x00, 0x00, 0x00, 0x00, 0x10, 0x00,
    };
    int index = (-state) & 0x7f;
    switch (c) {
    case 0: case ' ': return (table[index] & 0x80) == 0 ? index / 2 + '/' : 0;
    case '.': return -table[index];
    case '-': return -table[index + 1];
    default: return 0;
    }
}

Chris Wellons さんの実装に触発されました。魔法のようなプログラムで最初見たときたまげました。上の関数は Chris さんのオリジナルの関数と入れ替えて使えます。考え方は似ていますが別のアプローチで実装されています。

https://nullprogram.com/blog/2020/12/31

この関数を動かすためのサンプルのメイン関数はこちら

int main(int argc, char *argv[]) {
    char *code = ".... . .-.. .-.. ---";
    char decoded[32];
    int iout = 0;
    int state = 0;
    for (int i = 0; i < strlen(code) + 1; ++i) {
        int c = code[i];
        state = morse_decode(state, c);
        if (state == 0) {
            fprintf(stderr, "syntax error\n");
            return -1;
        }
        if (state > 0) {
            decoded[iout++] = state;
            state = 0;
        }
    }
    decoded[iout] = '\0';
    printf("result: %s\n", decoded);
    return 0;
}