8
\$\begingroup\$

Introduction

The Radio Data System (RDS) is a digital signal modulated onto a 57 kHz subcarrier of broadcast FM radio (above the 19 kHz pilot tone and 38 kHz stereo difference channel). The details of the modulation scheme are unimportant here; we assume that the output of demodulation is a series of 0 or 1 bits corresponding to the transmitted data stream.

(Aside: it could be useful to receive fuzzy inputs rather than immediately thresholding to straight binary, but let's assume that's out of scope here.)

The bit stream is structured as a sequence of independent groups of four blocks; each block comprises 16 data bits and 10 error-correction bits. Blocks within a group are transmitted in sequence: A, B, C (or C'), D; one of the bits of B indicates whether C or C' follows.

The error correction bits of each block are computed using the generator polynomial

g(x) = x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x³ + 1

A checkword is then XORed with the block; different checkwords allow the five block types to be distinguished.

The blocks are not completely opaque to us; there are some features of the content that we can use to improve our performance:

  • Block A contains the station's programme identifier, and is normally the same in every group.
  • Block B contains the programme type, which changes only infrequently. It also contains the group type, which indicates whether it's followed by C or C'.
  • Block C' is a copy of block A, but with a different checkword.
  • Blocks C and D contain no useful information at this level of decoding.

Objective

Given a demodulated RDS stream from a received broadcast, extract the groups and correct (as far as possible) the errors found therein.

Some desirable features (in priority order, so later goals must not be achieved at the expense of earlier ones):

  1. Extract and correct as much data as possible in challenging reception conditions.
  2. Minimise latency between reception and reporting.
  3. Minimise computational overhead in good conditions.
  4. Readable and maintainable code.

One significant non-goal is portability - I'm compiling this with GCC, and lean heavily on its __int128 type and __builtin_popcount() function. Portable alternatives to these may be helpful, especially to other reviewers, so I'll upvote answers which contribute to that, but that's not what I'm really looking for in a review.

Structure

Since C' doesn't make for good C++ identifiers, I've used the letter K in the code to refer to any C' block. Where we examine the A blocks from consecutive groups, I use E to identify the second; this is not to be confused with RDBS E blocks, which are no longer used.

Although I built the low-level facilities using unit tests, I've omitted the tests here, so as not to create too big a review.

We rely on a table of corrections of the most likely errors (which tend to occur in bursts rather than independently). Rather than generating this as an initialisation step, we build it at compile time by compiling and running a program (corrections) which generates C++ input.

Test program and inputs

I've provided a test program which reads files as if received by channel-hopping, and reports summary information of how many blocks could and couldn't be corrected. It reads input files that encode the received bits in big-endian order into 8-bit bytes; some suitable input files are available from the RDS Surveyor site (no affiliation to me).

Concerns

I'm comfortable with writing constants intrinsic to the RDS protocol as "magic numbers" in the code (e.g. bit shifts and masks), but there's a few more subjective numbers, such as threshold error counts that are more objective and could need tweaking. I can't think of good but short names for them.

Am I on the right track requiring subclassing and overriding users to subclass Synchronizer and override its virtual methods? It was the only manageable technique before I realised I needed to bundle the received blocks and their correction counts into the group structure, but perhaps we just need to give the synchronizer a callable object instead? I do anticipate using e.g. Qt signals at a higher level of decoding, but wanted to keep the low-level code as plain C++ without external libraries, to make it usable in any program.

There's a two-state machine in Synchronizer, where incoming bits go to different functions depending on whether we're synchronized or still looking to identify group boundaries. Is this reasonable, or would it be clearer to have a big if/else directly in push()?


rdstypes.hh

#ifndef RDSTYPES_HH
#define RDSTYPES_HH

#include <cstdint>

namespace rds
{
    struct block {
        std::uint16_t value;
        std::uint8_t err_count = 0xff;
        bool is_valid = false;

        operator std::uint16_t() const { return value; }
    };

    struct group {
        block a, b, c, d;
    };
}

#endif  /* RDSTYPES_HH */

crc.hh

#ifndef CRC_HH
#define CRC_HH

#include <cstdint>

namespace rds
{
    // Figure B.1, page 61
    static constexpr std::uint32_t encode(std::uint16_t x)
    {
        return ((x >> 15) & 1) * 0b10000000000000000001110111
            ^  ((x >> 14) & 1) * 0b01000000000000001011100111
            ^  ((x >> 13) & 1) * 0b00100000000000001110101111
            ^  ((x >> 12) & 1) * 0b00010000000000001100001011
            ^  ((x >> 11) & 1) * 0b00001000000000001101011001
            ^  ((x >> 10) & 1) * 0b00000100000000001101110000
            ^  ((x >>  9) & 1) * 0b00000010000000000110111000
            ^  ((x >>  8) & 1) * 0b00000001000000000011011100
            ^  ((x >>  7) & 1) * 0b00000000100000000001101110
            ^  ((x >>  6) & 1) * 0b00000000010000000000110111
            ^  ((x >>  5) & 1) * 0b00000000001000001011000111
            ^  ((x >>  4) & 1) * 0b00000000000100001110111111
            ^  ((x >>  3) & 1) * 0b00000000000010001100000011
            ^  ((x >>  2) & 1) * 0b00000000000001001101011101
            ^  ((x >>  1) & 1) * 0b00000000000000101101110010
            ^  ((x >>  0) & 1) * 0b00000000000000010110111001;
    }

    // Figure B.3, page 63
    constexpr std::uint16_t syndrome(std::uint32_t y)
    {
        return ((y >> 25) & 1) * 0b1000000000
            ^  ((y >> 24) & 1) * 0b0100000000
            ^  ((y >> 23) & 1) * 0b0010000000
            ^  ((y >> 22) & 1) * 0b0001000000
            ^  ((y >> 21) & 1) * 0b0000100000
            ^  ((y >> 20) & 1) * 0b0000010000
            ^  ((y >> 19) & 1) * 0b0000001000
            ^  ((y >> 18) & 1) * 0b0000000100
            ^  ((y >> 17) & 1) * 0b0000000010
            ^  ((y >> 16) & 1) * 0b0000000001
            ^  ((y >> 15) & 1) * 0b1011011100
            ^  ((y >> 14) & 1) * 0b0101101110
            ^  ((y >> 13) & 1) * 0b0010110111
            ^  ((y >> 12) & 1) * 0b1010000111
            ^  ((y >> 11) & 1) * 0b1110011111
            ^  ((y >> 10) & 1) * 0b1100010011
            ^  ((y >>  9) & 1) * 0b1101010101
            ^  ((y >>  8) & 1) * 0b1101110110
            ^  ((y >>  7) & 1) * 0b0110111011
            ^  ((y >>  6) & 1) * 0b1000000001
            ^  ((y >>  5) & 1) * 0b1111011100
            ^  ((y >>  4) & 1) * 0b0111101110
            ^  ((y >>  3) & 1) * 0b0011110111
            ^  ((y >>  2) & 1) * 0b1010100111
            ^  ((y >>  1) & 1) * 0b1110001111
            ^  ((y >>  0) & 1) * 0b1100011011;
    }
}

#endif  /* CRC_HH */

corrections.cc

// This program is run as part of the build, to generate the table of
// corrections as C++ source, to be compiled into the program.

#include "crc.hh"

#include <array>
#include <cstdint>
#include <iomanip>
#include <iostream>

struct Correction
{
    std::uint16_t correction = 0;
    unsigned char distance = ~0;
    bool correctable = false;
    void update(unsigned int c, unsigned int d)
    {
        if (d > distance)
            return;         // already have a better correction
        else if (d < distance)
            distance = d, correction = c, correctable = true;
        else if (c != correction)
            correctable = false; // detect only
    }
};


int main()
{
    std::array<Correction, 1024> t;
    // Recieved exactly
    t[0] = {0, 0, true};
    // 1-9 bit burst errors
    for (unsigned int dist = 1;  dist < 10;  ++dist) {
        const std::uint32_t first = (1u << (dist-1)) | 1;
        const std::uint32_t last = 1u << dist;
        for (std::uint32_t i = first;  i < last;  i+=2) {
            for (std::uint32_t j = i;  !(j & 1u<<26);  j <<=1)
                t[rds::syndrome(j)].update(j>>10, dist);
        }
    }
    // two independent 1-2 bit errors
    for (unsigned int dist = 9;  dist < 24;  ++dist) {
        for (std::uint32_t j: { ((1<<dist)+1), ((3<<dist)+1), ((1<<dist)+3), ((3<<dist)+3) }) {
            for (unsigned shift = 0;  dist+shift < 26;  ++shift) {
                t[rds::syndrome(j<<shift)].update(j<<shift>>10, 1 + __builtin_popcount(j));
            }
        }
    }

    std::cout << "// Generated by corrections.cc - edits may be overwritten without notice\n";
    for (auto const& item: t) {
        std::cout << "{"
                  << item.correction << ','
                  << 0u + item.distance << ','
                  << item.correctable << "},";
    }
}

synchronizer.hh

#ifndef SYNCHRONIZER_HH
#define SYNCHRONIZER_HH

#include "rdstypes.hh"

#include <cstdint>

namespace rds {

class Synchronizer
{
    // No valid programme identifier has country code 0, so we can use
    // zero to indicate initial condition.
    std::uint32_t prog_id = 0;

    // Initial state needs to not look like 0BCD0
    static constexpr unsigned __int128 initial_state = 0xffff;

    // 128 bits can store a whole 104-bit group, plus 24 bits of
    // adjacent context.
    unsigned __int128 state = initial_state;

    static auto constexpr max_loss_blocks = 10;
    unsigned int bits_until_a = 0;
    unsigned int blocks_since_lock = 0;
    std::uint32_t last_good_b = 0;

public:
    static constexpr std::uint32_t CHECKWORD_A = 0x0fc;
    static constexpr std::uint32_t CHECKWORD_B = 0x198;
    static constexpr std::uint32_t CHECKWORD_C = 0x168;
    static constexpr std::uint32_t CHECKWORD_K = 0x350;
    static constexpr std::uint32_t CHECKWORD_D = 0x1b4;

    virtual ~Synchronizer() = default;

    std::uint16_t pid() const {
        return prog_id >> 10;
    }

    virtual void reset() {
        state = initial_state;
        prog_id = 0;
        perBitAction = &Synchronizer::search_for_lock;
        // other members will be set before we enter the locked state
    }

    void push(bool bit)
    {
        state <<= 1;
        state += bit;
        (this->*perBitAction)();
    }


protected:
    // @return error weight
    static rds::block correct(std::uint16_t checkword, std::uint32_t input);

    void (Synchronizer::*perBitAction)() = &Synchronizer::search_for_lock;

    void search_for_lock();
    void confirm_lock();

    void lock_found(std::uint16_t pid, unsigned int bits_to_go);
    void lock_lost();

    virtual void process_group(const rds::group& group);
};

}

#endif /* SYNCHRONIZER_HH */

synchronizer.cc

#include "synchronizer.hh"

#include "crc.hh"

#include <algorithm>
#include <array>
#include <cstdint>

using rds::Synchronizer;

namespace {

    struct Correction
    {
        std::uint16_t correction;
        unsigned char distance;
        bool correctable;
    };

    const std::array<Correction, 1024> corrections{{
#include "corrections.table"
        }};

    template<unsigned char size, typename... T>
    static constexpr int hamming_distance(T... v)
    {
        auto constexpr mask = (std::common_type_t<T...>(1) << size) - 1;
        return __builtin_popcount((mask & (... ^ v)));
    }
}

// @return error weight
rds::block Synchronizer::correct(std::uint16_t checkword, std::uint32_t input)
{
    input ^= checkword;
    auto s = syndrome(input);

    rds::block b = {static_cast<std::uint16_t>(input >> 10), 0, true};
    if (!s) {
        // perfect
        return b;
    }

    auto const& entry = corrections[s];

    b.value ^= entry.correction;
    b.err_count = entry.distance;
    b.is_valid = entry.correctable;
    return b;
}

void Synchronizer::search_for_lock()
{
    constexpr int MAX_ERR = 8;

    // Check self-similarity first, with 0.5% false-positive rate, before examining CRCs
    if (hamming_distance<26>(CHECKWORD_A, CHECKWORD_K, state, state >> 52) <= 6) {
        rds::block a,b,k,d;
        int err;

        if ((err = (k = correct(CHECKWORD_K, state)).err_count) <= MAX_ERR
            && (err += (a = correct(CHECKWORD_A, state >> 52)).err_count) <= MAX_ERR
            && a.value == k.value
            && (err += (b = correct(CHECKWORD_B, state >> 26)).err_count) <= MAX_ERR)
            {
                // we matched A.K
                lock_found(a.value, 52);
                return;
            }
        if ((err = (a = correct(CHECKWORD_A, state)).err_count) <= MAX_ERR
            && (err += (k = correct(CHECKWORD_K, state >> 52)).err_count) <= MAX_ERR
            && a.value == k.value
            && (err += (d = correct(CHECKWORD_D, state >> 26)).err_count) <= MAX_ERR)
            {
                // we matched K.A
                lock_found(a.value, 0);
                return;
            }
    }
    // Have we got a match with A...A?  Again, we require >99.5% certainty before checking CRCs.
    // Note that we only have 24 bits remaining of the previous A, so fill in from the new one.
    if (hamming_distance<24>(state, state >> 104) <= 5) {
        rds::block a,b,c,d,e;
        int err;
        if ((err = (a = correct(CHECKWORD_A, state)).err_count) <= MAX_ERR
            && (err += (e = correct(CHECKWORD_A, ((state >> 104) & 0xffffff) | (state & 0x3000000))).err_count) <= MAX_ERR
            && e.value == a.value
            && (err += (d = correct(CHECKWORD_D, state >> 26)).err_count) <= MAX_ERR
            && (err += (c = correct(CHECKWORD_C, state >> 52)).err_count) <= MAX_ERR
            && (err += (b = correct(CHECKWORD_B, state >> 78)).err_count) <= MAX_ERR)
            {
                // we matched A...A
                lock_found(a.value, 0);
                return;
            }
    }
}


void Synchronizer::confirm_lock()
{
    if (--bits_until_a)
        return;
    bits_until_a = 104;

    rds::block a = correct(CHECKWORD_A, state);
    rds::block b = correct(CHECKWORD_B, state >> 78);
    rds::block c = correct(CHECKWORD_C, state >> 52);
    rds::block k = correct(CHECKWORD_K, state >> 52);
    rds::block d = correct(CHECKWORD_D, state >> 26);

    unsigned ck = std::min(k.err_count, c.err_count);

    if ((a.err_count >= 4 || a.value != prog_id>>10) && b.err_count * ck * d.err_count >= 16) {
        if (hamming_distance<25>(std::uint32_t(state), prog_id>>1) <= 5) {
            // bit slip - need one more bit
            bits_until_a = 1;
        } else if (hamming_distance<26>(std::uint32_t(state)>>1, prog_id) <= 5) {
            // bit slip - miss one bit
            bits_until_a = 103;
        } else {
            lock_lost();
        }
        return;
    }

    if (a.err_count == 0 && a.value != prog_id>>10) {
        // prog_id has changed
        prog_id = CHECKWORD_A ^ encode(a);
    }

    // reset counter
    blocks_since_lock = 0;

    if (b.err_count > 8) {
        // attempt to recover block 2 using saved PTY and inferred A/B
        //                                 AAAABTPPPPPiiiii..........
        static constexpr auto pty_mask = 0b00000011111000000000000000;
        static constexpr auto ab_mask  = 0b00001000000000000000000000;
        std::uint32_t block2 =
            ((~pty_mask & ~ab_mask) & (state >> 78))
            | (pty_mask & last_good_b)
            | (ab_mask & (c.err_count == k.err_count ? last_good_b : -1 * (c.err_count >= k.err_count)));
        auto b2 = correct(CHECKWORD_B, block2);
        if (b2.err_count >= b.err_count) {
            // couldn't decode the B block, so the rest is useless
            return;
        }
    } else {
        last_good_b = state >> 78;
    }

    process_group({a, b, c, d});
}


void Synchronizer::lock_found(std::uint16_t pid, unsigned int bits_to_go) {
    perBitAction = &Synchronizer::confirm_lock;
    prog_id = CHECKWORD_A ^ encode(pid);
    blocks_since_lock = 0;
    bits_until_a = 1 + bits_to_go;
    confirm_lock();
}

void Synchronizer::lock_lost() {
    if (++blocks_since_lock >= max_loss_blocks)
        perBitAction = &Synchronizer::search_for_lock;
}

void Synchronizer::process_group(const rds::group&)
{
    // to be overridden
}

decode-file.cc

#include "synchronizer.hh"

#include <fstream>
#include <iostream>

struct TestSynchronizer : rds::Synchronizer
{
    // keep track of some statistics
    unsigned long bits = 0;
    unsigned long good_blocks = 0;
    unsigned long corrected_blocks = 0;
    unsigned long bad_blocks = 0;

    void push(bool bit) {
        ++bits;
        rds::Synchronizer::push(bit);
    }

    void process_group(const rds::group& group) override
    {
        for (auto const& block: {group.a, group.b, group.c, group.d}) {
            auto& count
                = !block.is_valid ? bad_blocks
                : block.err_count ? corrected_blocks
                : good_blocks;
            ++count;
        }
    }

    void read_file(const std::string& filename)
    {
        reset();
        bits = good_blocks = corrected_blocks = bad_blocks = 0;

        std::ifstream in(filename, std::ifstream::binary);
        int c;
        while ((c = in.get()) != EOF) {
            for (int m = 0x80;  m;  m >>= 1)
                push(c & m);
        }

        // Summary statistics
        std::clog << filename << ": "
                  << good_blocks << " good, "
                  << corrected_blocks << " corrected, "
                  << bad_blocks << " uncorrectable blocks; "
                  << bits - 26 * (good_blocks + corrected_blocks + bad_blocks)
                  << " undecoded bits"
                  << std::endl;
    }
};

int main(int, char **argv)
{
    TestSynchronizer s;
    while (*++argv) {
        s.read_file(*argv);
    }
}

Makefile

CPPFLAGS += -finput-charset=UTF-8

CXX=g++-8
CXXFLAGS += -std=c++2a
CXXFLAGS += -Wall -Wextra -Werror
CXXFLAGS += -march=native -O3 -g
#CXXFLAGS += -march=native -O0 -g

LINK.o := $(LINK.cc)

# House-keeping build targets.

all: decode-file

clean:
    $(RM) *.o *.dep
    $(RM) corrections.table

tidy: 
    $(RM) *~

distclean: clean tidy
    $(RM) decode-file corrections

%.dep: %.cc
    @echo [dep] $<
    @$(CXX) -MM $(CPPFLAGS) $<  | sed -e 's,\($*\)\.o[ :]*,\1.o $@ : ,g' > $@

# Actions
run-%: %
    ./$< $(RUN_ARGS)

valgrind-%: %
    valgrind -q --leak-check=full ./$< $(RUN_ARGS)

sources := $(wildcard *.cc)

ifeq ($(filter $(MAKECMDGOALS),clean tidy distclean),)
include $(sources:.cc=.dep)
endif

corrections.table: corrections
    ./$< >$@

synchronizer.o synchronizer.dep: corrections.table

decode-file: decode-file.o
decode-file: synchronizer.o

run-decode-file valgrind-decode-file: RUN_ARGS += *.rds

.PHONY: run-% valgrind-% clean tidy distclean all
.DELETE_ON_ERROR:

Single-source version

This may be useful if you want to experiment with the code (in the case of any discrepancies, the multi-file version is authoritative). Compile using g++ -std=c++17 -Wall -Wextra -Werror.

#include <algorithm>
#include <array>
#include <cstdint>
#include <fstream>
#include <iostream>

namespace rds
{
    struct block {
        std::uint16_t value;
        std::uint8_t err_count = 0xff;
        bool is_valid = false;

        operator std::uint16_t() const { return value; }
    };

    struct group {
        block a, b, c, d;
    };

    // Figure B.1, page 61
    static constexpr std::uint32_t encode(std::uint16_t x)
    {
        return ((x >> 15) & 1) * 0b10000000000000000001110111
            ^  ((x >> 14) & 1) * 0b01000000000000001011100111
            ^  ((x >> 13) & 1) * 0b00100000000000001110101111
            ^  ((x >> 12) & 1) * 0b00010000000000001100001011
            ^  ((x >> 11) & 1) * 0b00001000000000001101011001
            ^  ((x >> 10) & 1) * 0b00000100000000001101110000
            ^  ((x >>  9) & 1) * 0b00000010000000000110111000
            ^  ((x >>  8) & 1) * 0b00000001000000000011011100
            ^  ((x >>  7) & 1) * 0b00000000100000000001101110
            ^  ((x >>  6) & 1) * 0b00000000010000000000110111
            ^  ((x >>  5) & 1) * 0b00000000001000001011000111
            ^  ((x >>  4) & 1) * 0b00000000000100001110111111
            ^  ((x >>  3) & 1) * 0b00000000000010001100000011
            ^  ((x >>  2) & 1) * 0b00000000000001001101011101
            ^  ((x >>  1) & 1) * 0b00000000000000101101110010
            ^  ((x >>  0) & 1) * 0b00000000000000010110111001;
    }

    // Figure B.3, page 63
    constexpr std::uint16_t syndrome(std::uint32_t y)
    {
        return ((y >> 25) & 1) * 0b1000000000
            ^  ((y >> 24) & 1) * 0b0100000000
            ^  ((y >> 23) & 1) * 0b0010000000
            ^  ((y >> 22) & 1) * 0b0001000000
            ^  ((y >> 21) & 1) * 0b0000100000
            ^  ((y >> 20) & 1) * 0b0000010000
            ^  ((y >> 19) & 1) * 0b0000001000
            ^  ((y >> 18) & 1) * 0b0000000100
            ^  ((y >> 17) & 1) * 0b0000000010
            ^  ((y >> 16) & 1) * 0b0000000001
            ^  ((y >> 15) & 1) * 0b1011011100
            ^  ((y >> 14) & 1) * 0b0101101110
            ^  ((y >> 13) & 1) * 0b0010110111
            ^  ((y >> 12) & 1) * 0b1010000111
            ^  ((y >> 11) & 1) * 0b1110011111
            ^  ((y >> 10) & 1) * 0b1100010011
            ^  ((y >>  9) & 1) * 0b1101010101
            ^  ((y >>  8) & 1) * 0b1101110110
            ^  ((y >>  7) & 1) * 0b0110111011
            ^  ((y >>  6) & 1) * 0b1000000001
            ^  ((y >>  5) & 1) * 0b1111011100
            ^  ((y >>  4) & 1) * 0b0111101110
            ^  ((y >>  3) & 1) * 0b0011110111
            ^  ((y >>  2) & 1) * 0b1010100111
            ^  ((y >>  1) & 1) * 0b1110001111
            ^  ((y >>  0) & 1) * 0b1100011011;
    }


    class Synchronizer
    {
        // No valid programme identifier has country code 0, so we can use
        // zero to indicate initial condition.
        std::uint32_t prog_id = 0;

        // Initial state needs to not look like 0BCD0
        static constexpr unsigned __int128 initial_state = 0xffff;

        // 128 bits can store a whole 104-bit group, plus 24 bits of
        // adjacent context.
        unsigned __int128 state = initial_state;

        static auto constexpr max_loss_blocks = 10;
        unsigned int bits_until_a = 0;
        unsigned int blocks_since_lock = 0;
        std::uint32_t last_good_b = 0;

    public:
        static constexpr std::uint32_t CHECKWORD_A = 0x0fc;
        static constexpr std::uint32_t CHECKWORD_B = 0x198;
        static constexpr std::uint32_t CHECKWORD_C = 0x168;
        static constexpr std::uint32_t CHECKWORD_K = 0x350;
        static constexpr std::uint32_t CHECKWORD_D = 0x1b4;

        virtual ~Synchronizer() = default;

        std::uint16_t pid() const {
            return prog_id >> 10;
        }

        virtual void reset() {
            state = initial_state;
            prog_id = 0;
            perBitAction = &Synchronizer::search_for_lock;
            // other members will be set before we enter the locked state
        }

        void push(bool bit)
        {
            state <<= 1;
            state += bit;
            (this->*perBitAction)();
        }


    protected:
        // @return error weight
        static rds::block correct(std::uint16_t checkword, std::uint32_t input);

        void (Synchronizer::*perBitAction)() = &Synchronizer::search_for_lock;

        void search_for_lock();
        void confirm_lock();

        void lock_found(std::uint16_t pid, unsigned int bits_to_go);
        void lock_lost();

        virtual void process_group(const rds::group& group);
    };

}

namespace {

    struct Correction
    {
        std::uint16_t correction;
        unsigned char distance;
        bool correctable;

        Correction()
            : correction(0), distance(0xf), correctable(false)
        {}

        void update(unsigned int c, unsigned int d)
        {
            if (d > distance)
                return;         // already have a better correction
            else if (d < distance)
                distance = d, correction = c, correctable = 1;
            else if (c != correction)
                correctable = 0; // detect only
        }
    };

    static auto const corrections =
        []{
            std::array<Correction, 1024> t;
            // Recieved exactly
            t[0].distance = 0;
            // 1-9 bit burst errors
            for (unsigned int dist = 1;  dist < 10;  ++dist) {
                const std::uint32_t first = (1u << (dist-1)) | 1;
                const std::uint32_t last = 1u << dist;
                for (std::uint32_t i = first;  i < last;  i+=2) {
                    for (std::uint32_t j = i;  !(j & 1u<<26);  j <<=1)
                        t[rds::syndrome(j)].update(j>>10, dist);
                }
            }
            // two independent 1-2 bit errors
            for (unsigned int dist = 9;  dist < 24;  ++dist) {
                for (std::uint32_t j: { ((1<<dist)+1), ((3<<dist)+1), ((1<<dist)+3), ((3<<dist)+3) }) {
                    for (unsigned shift = 0;  dist+shift < 26;  ++shift) {
                        t[rds::syndrome(j<<shift)].update(j<<shift>>10, 1 + __builtin_popcount(j));
                    }
                }
            }
            return t;
        }();

    template<unsigned char size, typename... T>
    static constexpr int hamming_distance(T... v)
    {
        auto constexpr mask = (std::common_type_t<T...>(1) << size) - 1;
        return __builtin_popcount((mask & (... ^ v)));
    }
}

// @return error weight
rds::block rds::Synchronizer::correct(std::uint16_t checkword, std::uint32_t input)
{
    input ^= checkword;
    auto s = syndrome(input);

    rds::block b = {static_cast<std::uint16_t>(input >> 10), 0, true};
    if (!s) {
        // perfect
        return b;
    }

    auto const& entry = corrections[s];

    b.value ^= entry.correction;
    b.err_count = entry.distance;
    b.is_valid = entry.correctable;
    return b;
}

void rds::Synchronizer::search_for_lock()
{
    constexpr int MAX_ERR = 8;

    // Check self-similarity first, with 0.5% false-positive rate, before examining CRCs
    if (hamming_distance<26>(CHECKWORD_A, CHECKWORD_K, state, state >> 52) <= 6) {
        rds::block a,b,k,d;
        int err;

        if ((err = (k = correct(CHECKWORD_K, state)).err_count) <= MAX_ERR
            && (err += (a = correct(CHECKWORD_A, state >> 52)).err_count) <= MAX_ERR
            && a.value == k.value
            && (err += (b = correct(CHECKWORD_B, state >> 26)).err_count) <= MAX_ERR)
            {
                // we matched A.K
                lock_found(a.value, 52);
                return;
            }
        if ((err = (a = correct(CHECKWORD_A, state)).err_count) <= MAX_ERR
            && (err += (k = correct(CHECKWORD_K, state >> 52)).err_count) <= MAX_ERR
            && a.value == k.value
            && (err += (d = correct(CHECKWORD_D, state >> 26)).err_count) <= MAX_ERR)
            {
                // we matched K.A
                lock_found(a.value, 0);
                return;
            }
    }
    // Have we got a match with A...A?  Again, we require >99.5% certainty before checking CRCs.
    // Note that we only have 24 bits remaining of the previous A, so fill in from the new one.
    if (hamming_distance<24>(state, state >> 104) <= 5) {
        rds::block a,b,c,d,e;
        int err;
        if ((err = (a = correct(CHECKWORD_A, state)).err_count) <= MAX_ERR
            && (err += (e = correct(CHECKWORD_A, ((state >> 104) & 0xffffff) | (state & 0x3000000))).err_count) <= MAX_ERR
            && e.value == a.value
            && (err += (d = correct(CHECKWORD_D, state >> 26)).err_count) <= MAX_ERR
            && (err += (c = correct(CHECKWORD_C, state >> 52)).err_count) <= MAX_ERR
            && (err += (b = correct(CHECKWORD_B, state >> 78)).err_count) <= MAX_ERR)
            {
                // we matched A...A
                lock_found(a.value, 0);
                return;
            }
    }
}


void rds::Synchronizer::confirm_lock()
{
    if (--bits_until_a)
        return;
    bits_until_a = 104;

    rds::block a = correct(CHECKWORD_A, state);
    rds::block b = correct(CHECKWORD_B, state >> 78);
    rds::block c = correct(CHECKWORD_C, state >> 52);
    rds::block k = correct(CHECKWORD_K, state >> 52);
    rds::block d = correct(CHECKWORD_D, state >> 26);

    unsigned ck = std::min(k.err_count, c.err_count);

    if ((a.err_count >= 4 || a.value != prog_id>>10) && b.err_count * ck * d.err_count >= 16) {
        if (hamming_distance<25>(std::uint32_t(state), prog_id>>1) <= 5) {
            // bit slip - need one more bit
            bits_until_a = 1;
        } else if (hamming_distance<26>(std::uint32_t(state)>>1, prog_id) <= 5) {
            // bit slip - miss one bit
            bits_until_a = 103;
        } else {
            lock_lost();
        }
        return;
    }

    if (a.err_count == 0 && a.value != prog_id>>10) {
        // prog_id has changed
        prog_id = CHECKWORD_A ^ encode(a);
    }

    // reset counter
    blocks_since_lock = 0;

    if (b.err_count > 8) {
        // attempt to recover block 2 using saved PTY and inferred A/B
        //                                 AAAABTPPPPPiiiii..........
        static constexpr auto pty_mask = 0b00000011111000000000000000;
        static constexpr auto ab_mask  = 0b00001000000000000000000000;
        std::uint32_t block2 =
            ((~pty_mask & ~ab_mask) & (state >> 78))
            | (pty_mask & last_good_b)
            | (ab_mask & (c.err_count == k.err_count ? last_good_b : -1 * (c.err_count >= k.err_count)));
        auto b2 = correct(CHECKWORD_B, block2);
        if (b2.err_count >= b.err_count) {
            // couldn't decode the B block, so the rest is useless
            return;
        }
    } else {
        last_good_b = state >> 78;
    }

    process_group({a, b, c, d});
}


void rds::Synchronizer::lock_found(std::uint16_t pid, unsigned int bits_to_go) {
    perBitAction = &Synchronizer::confirm_lock;
    prog_id = CHECKWORD_A ^ encode(pid);
    blocks_since_lock = 0;
    bits_until_a = 1 + bits_to_go;
    confirm_lock();
}

void rds::Synchronizer::lock_lost() {
    if (++blocks_since_lock >= max_loss_blocks)
        perBitAction = &Synchronizer::search_for_lock;
}

void rds::Synchronizer::process_group(const rds::group&)
{
    // to be overridden
}



struct TestSynchronizer : rds::Synchronizer
{
    // keep track of some statistics
    unsigned long bits = 0;
    unsigned long good_blocks = 0;
    unsigned long corrected_blocks = 0;
    unsigned long bad_blocks = 0;

    void push(bool bit) {
        ++bits;
        rds::Synchronizer::push(bit);
    }

    void process_group(const rds::group& group) override
    {
        for (auto const& block: {group.a, group.b, group.c, group.d}) {
            auto& count
                = !block.is_valid ? bad_blocks
                : block.err_count ? corrected_blocks
                : good_blocks;
            ++count;
        }
    }

    void read_file(const std::string& filename)
    {
        reset();
        bits = good_blocks = corrected_blocks = bad_blocks = 0;

        std::ifstream in(filename, std::ifstream::binary);
        int c;
        while ((c = in.get()) != EOF) {
            for (int m = 0x80;  m;  m >>= 1)
                push(c & m);
        }

        // Summary statistics
        std::clog << filename << ": "
                  << good_blocks << " good, "
                  << corrected_blocks << " corrected, "
                  << bad_blocks << " uncorrectable blocks; "
                  << bits - 26 * (good_blocks + corrected_blocks + bad_blocks)
                  << " undecoded bits"
                  << std::endl;
    }
};

int main(int, char **argv)
{
    TestSynchronizer s;
    while (*++argv) {
        s.read_file(*argv);
    }
}
\$\endgroup\$
2
\$\begingroup\$

The generation of the table was moved to compile time due to very slow startup of the program. But evidently that problem is no longer present:

$ time ./corrections >/dev/null
real    0m0.001s
user    0m0.001s
sys     0m0.000s

So the table generator can be inlined into synchronizer.cc just as in the single-file version in the question (using an immediately-invoked lambda to give us a constant).

\$\endgroup\$
2
\$\begingroup\$

No overloaded population counts

One point is that you should either (i) statically enforce your integer type to have 32 bits, or (ii) call the correct population count function depending on the integer width.

That is, the argument for __builtin_popcount is an unsigned int, but __builtin_popcountl takes an unsigned long and __builtin_popcountll takes an unsigned long long. So in particular, there is no overload for __builtin_popcount, but the functions for different widths are actually different.

Portability

As noted, the __builtin_popcount functions are specific to GCC. For portability, you can write the Hamming distance computation with the help of std::bitset as follows:

template<unsigned char size, typename... T>
static constexpr int hamming_distance(T... v)
{
    return std::bitset<size>((... ^ v)).count();
}

In fact, it seems that (on Compiler Explorer) that the above creates object code identical to yours, so there should be absolutely no difference in performance.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.