From 9918eb505321183e20357221a4dcf2aa9c1e057c Mon Sep 17 00:00:00 2001 From: jaseg Date: Mon, 4 May 2020 21:31:31 +0200 Subject: fw: add working reed-solomon encoder/decoder --- controller/fw/Makefile | 65 ++++---- controller/fw/reed_solomon | 1 + controller/fw/src/gpio_helpers.c | 46 ++++++ controller/fw/src/gpio_helpers.h | 14 ++ controller/fw/src/ldpc_decoder.c | 267 --------------------------------- controller/fw/src/ldpc_decoder_test.py | 72 --------- controller/fw/src/ldpc_wrapper.cpp | 84 ----------- controller/fw/src/main.c | 34 ++++- controller/fw/src/mspdebug_wrapper.c | 5 +- controller/fw/src/protocol.c | 2 + controller/fw/src/rscode-config.h | 9 ++ controller/fw/src/rslib.c | 29 ++++ controller/fw/src/rslib.h | 9 ++ controller/fw/tools/reed_solomon.py | 81 ++++++++++ 14 files changed, 253 insertions(+), 465 deletions(-) create mode 160000 controller/fw/reed_solomon create mode 100644 controller/fw/src/gpio_helpers.c create mode 100644 controller/fw/src/gpio_helpers.h delete mode 100644 controller/fw/src/ldpc_decoder.c delete mode 100644 controller/fw/src/ldpc_decoder_test.py delete mode 100644 controller/fw/src/ldpc_wrapper.cpp create mode 100644 controller/fw/src/rscode-config.h create mode 100644 controller/fw/src/rslib.c create mode 100644 controller/fw/src/rslib.h create mode 100644 controller/fw/tools/reed_solomon.py (limited to 'controller/fw') diff --git a/controller/fw/Makefile b/controller/fw/Makefile index ab9d66c..b6fa43f 100644 --- a/controller/fw/Makefile +++ b/controller/fw/Makefile @@ -9,6 +9,7 @@ MSPDEBUG_DIR ?= mspdebug LIBSODIUM_DIR ?= libsodium TINYAES_DIR ?= tinyaes MUSL_DIR ?= musl +RSLIB_DIR ?= reed_solomon ######################################################################################################################## # Algorithm parameters @@ -56,34 +57,38 @@ C_SOURCES += tinyprintf/tinyprintf.c C_SOURCES += $(MSPDEBUG_DIR)/drivers/jtaglib.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/TransformFunctions/arm_rfft_fast_init_f32.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/TransformFunctions/arm_rfft_fast_f32.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/TransformFunctions/arm_cfft_init_f32.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/TransformFunctions/arm_cfft_f32.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/TransformFunctions/arm_cfft_radix8_f32.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/CommonTables/arm_const_structs.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/CommonTables/arm_common_tables.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/TransformFunctions/arm_bitreversal.c -CMSIS_SOURCES += $(CMSIS_DIR)/CMSIS/DSP/Source/TransformFunctions/arm_bitreversal2.c - -MUSL_SOURCES += $(MUSL_DIR)/src/math/tanhf.c $(MUSL_DIR)/src/math/atanhf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/expm1f.c $(MUSL_DIR)/src/math/log1pf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/expf.c $(MUSL_DIR)/src/math/exp2f_data.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/powf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/sqrtf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/fabsf.c -MUSL_SOURCES += $(MUSL_DIR)/src/stdlib/abs.c -MUSL_SOURCES += $(MUSL_DIR)/src/string/memset.c -MUSL_SOURCES += $(MUSL_DIR)/src/string/memcpy.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/__math_oflowf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/__math_uflowf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/__math_xflowf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/__math_invalidf.c -MUSL_SOURCES += $(MUSL_DIR)/src/math/powf_data.c - -C_SOURCES += $(CMSIS_SOURCES) $(MUSL_SOURCES) - -CXX_SOURCES += src/ldpc_wrapper.cpp +CMSIS_SOURCES += TransformFunctions/arm_rfft_fast_init_f32.c +CMSIS_SOURCES += TransformFunctions/arm_rfft_fast_f32.c +CMSIS_SOURCES += TransformFunctions/arm_cfft_init_f32.c +CMSIS_SOURCES += TransformFunctions/arm_cfft_f32.c +CMSIS_SOURCES += TransformFunctions/arm_cfft_radix8_f32.c +CMSIS_SOURCES += CommonTables/arm_const_structs.c +CMSIS_SOURCES += CommonTables/arm_common_tables.c +CMSIS_SOURCES += TransformFunctions/arm_bitreversal.c +CMSIS_SOURCES += TransformFunctions/arm_bitreversal2.c +CMSIS_SOURCES := $(addprefix $(CMSIS_DIR)/CMSIS/DSP/Source/,$(CMSIS_SOURCES)) + +MUSL_SOURCES += math/tanhf.c math/atanhf.c +MUSL_SOURCES += math/expm1f.c math/log1pf.c +MUSL_SOURCES += math/expf.c math/exp2f_data.c +MUSL_SOURCES += math/powf.c +MUSL_SOURCES += math/sqrtf.c +MUSL_SOURCES += math/fabsf.c +MUSL_SOURCES += stdlib/abs.c +MUSL_SOURCES += string/memset.c +MUSL_SOURCES += string/memcpy.c +MUSL_SOURCES += math/__math_oflowf.c +MUSL_SOURCES += math/__math_uflowf.c +MUSL_SOURCES += math/__math_xflowf.c +MUSL_SOURCES += math/__math_invalidf.c +MUSL_SOURCES += math/powf_data.c +MUSL_SOURCES := $(addprefix $(MUSL_DIR)/src/,$(MUSL_SOURCES)) + +RSLIB_SOURCES += $(addprefix $(RSLIB_DIR)/src/,rs.c ecc.c berlekamp.c galois.c) + +C_SOURCES += $(CMSIS_SOURCES) $(MUSL_SOURCES) $(RSLIB_SOURCES) + +CXX_SOURCES += BUILDDIR ?= build BINARY := safetyreset.elf @@ -299,8 +304,8 @@ $(BUILDDIR)/tinyaes/aes.o: # mkdir -p $(BUILDDIR)/musl # cd $(BUILDDIR)/musl && CFLAGS="$(SIM_CFLAGS) $(COMMON_CFLAGS)" CC=$(CC) LD=$(LD) AR=$(AR) $(MUSL_DIR_ABS)/configure && $(MAKE) TARGET=arm-linux-musleabihf GCC_CONFIG="-mcpu=cortex-m4 -mfloat-abi=soft" -j $(shell nproc) -build/ldpc_decoder_test.so: src/ldpc_decoder.c - gcc -fPIC -shared -Wall -Wextra -Wpedantic -std=gnu11 -O0 -g -o $@ $^ +build/rslib.so: $(RSLIB_SOURCES) src/rslib.c + gcc -fPIC -shared -Wall -Wextra -Wpedantic -std=gnu11 -O0 -g -o $@ -Isrc -I$(RSLIB_DIR)/src $^ clean: rm -rf $(BUILDDIR)/src diff --git a/controller/fw/reed_solomon b/controller/fw/reed_solomon new file mode 160000 index 0000000..63ff148 --- /dev/null +++ b/controller/fw/reed_solomon @@ -0,0 +1 @@ +Subproject commit 63ff1482d42547422896418d5990a66a80e88d34 diff --git a/controller/fw/src/gpio_helpers.c b/controller/fw/src/gpio_helpers.c new file mode 100644 index 0000000..07b9a33 --- /dev/null +++ b/controller/fw/src/gpio_helpers.c @@ -0,0 +1,46 @@ + +#include "gpio_helpers.h" + +void gpio_pin_mode(GPIO_TypeDef *gpio, int pin, int mode) { + gpio->MODER &= ~(3 << (2*pin)); + gpio->MODER |= mode << (2*pin); +} + +void gpio_pin_setup(GPIO_TypeDef *gpio, int pin, int mode, int speed, int pullups, int afsel) { + int gpio_idx = ((uint32_t)gpio>>10) & 0xf; + RCC->AHB1ENR |= 1<MODER &= ~(3 << (2*pin)); + gpio->MODER |= mode << (2*pin); + gpio->OSPEEDR &= ~(3 << (2*pin)); + gpio->OSPEEDR |= speed << (2*pin); + gpio->PUPDR &= ~(3 << (2*pin)); + gpio->PUPDR |= pullups << (2*pin); + gpio->AFR[pin>>3] &= ~(0xf << (4*(pin&7))); + gpio->AFR[pin>>3] |= afsel << (4*(pin&7)); + gpio->BSRR = 1<MODER &= ~(3 << (2*pin)); + else + gpio->MODER |= 1 << (2*pin); +} + +void gpio_pin_input(GPIO_TypeDef *gpio, int pin, int pullups) { + gpio_pin_setup(gpio, pin, 0, 0, pullups, 0); +} + +void gpio_pin_af(GPIO_TypeDef *gpio, int pin, int speed, int pullups, int afsel) { + gpio_pin_setup(gpio, pin, 2, speed, pullups, afsel); +} + +void gpio_pin_analog(GPIO_TypeDef *gpio, int pin) { + gpio_pin_setup(gpio, pin, 3, 0, 0, 0); +} + diff --git a/controller/fw/src/gpio_helpers.h b/controller/fw/src/gpio_helpers.h new file mode 100644 index 0000000..abe2e85 --- /dev/null +++ b/controller/fw/src/gpio_helpers.h @@ -0,0 +1,14 @@ +#ifndef __GPIO_HELPERS_H__ +#define __GPIO_HELPERS_H__ + +#include + +void gpio_pin_mode(GPIO_TypeDef *gpio, int pin, int mode); +void gpio_pin_setup(GPIO_TypeDef *gpio, int pin, int mode, int speed, int pullups, int afsel); +void gpio_pin_output(GPIO_TypeDef *gpio, int pin, int speed); +void gpio_pin_input(GPIO_TypeDef *gpio, int pin, int pullups); +void gpio_pin_af(GPIO_TypeDef *gpio, int pin, int speed, int pullups, int afsel); +void gpio_pin_analog(GPIO_TypeDef *gpio, int pin); +void gpio_pin_tristate(GPIO_TypeDef *gpio, int pin, int tristate); + +#endif /* __GPIO_HELPERS_H__ */ diff --git a/controller/fw/src/ldpc_decoder.c b/controller/fw/src/ldpc_decoder.c deleted file mode 100644 index fe59d77..0000000 --- a/controller/fw/src/ldpc_decoder.c +++ /dev/null @@ -1,267 +0,0 @@ - -#include -#include -#include -#include -#include - - -void gausselimination(size_t n, size_t k, int8_t *A, int8_t *b); - -void inner_logbp( - size_t m, size_t n, - size_t bits_count, size_t nodes_count, const uint32_t bits_values[], const uint32_t nodes_values[], - int8_t Lc[], - float Lq[], float Lr[], - unsigned int n_iter, - float L_posteriori_out[]); - -//decode(384, 6, 8, ...) -int decode(size_t n, size_t nodes_count, size_t bits_count, uint32_t bits[], int8_t y[], int8_t out[], unsigned int maxiter) { - const size_t m = n * nodes_count / bits_count; - float Lq[m*n]; - float Lr[m*n]; - float L_posteriori[n]; - - /* Calculate column bit positions from row bit positions */ - int32_t bits_transposed[nodes_count * n]; - for (size_t i=0; i 1000 && i/w > head_tail && i/w < m*n/w-head_tail) { - if (!ellipsis) { - ellipsis = true; - printf("\n ..."); - } - continue; - } - if (i) - printf(", "); - if (i%w == 0) - printf("\n "); - float outf = arrs[j][i]; - char *s = outf < 0 ? "\033[91m" : (outf > 0 ? "\033[92m" : "\033[94m"); - printf("%s% 012.6g\033[38;5;240m", s, outf); - } - printf("\n]\n"); - } - */ - - for (size_t i=0; i 0 ? "\033[92m" : "\033[94m"); - //printf("nij=%04u Lc=%s%3d\033[38;5;240m ", bits_values[q], s, lcv); - x *= tanhf(0.5f * Lc[bits_values[q]]); - } - } - - } else { - for (size_t q=bits_counter; q=0; i--) { - out[i] = x[i]; - - uint8_t sum = 0; - for (size_t j=i+1; j -#include -#include -#include - -#include "ldpc/generic.hh" -#include "ldpc/layered_decoder.hh" - -static const int DEFAULT_TRIALS = 25; - -struct DVB_S2_TABLE_C9 -{ - static const int M = 360; - static const int N = 16200; - static const int K = 13320; - static const int LINKS_MIN_CN = 15; - static const int LINKS_MAX_CN = 19; - static const int LINKS_TOTAL = 49319; - static const int DEG_MAX = 13; - static const int DEG[]; - static const int LEN[]; - static const int POS[]; -}; - -const int DVB_S2_TABLE_C9::DEG[] = { - 13, 3, 0 -}; - -const int DVB_S2_TABLE_C9::LEN[] = { - 1, 36, 0 -}; - -const int DVB_S2_TABLE_C9::POS[] = { - 3, 2409, 499, 1481, 908, 559, 716, 1270, 333, 2508, 2264, 1702, 2805, - 4, 2447, 1926, - 5, 414, 1224, - 6, 2114, 842, - 7, 212, 573, - 0, 2383, 2112, - 1, 2286, 2348, - 2, 545, 819, - 3, 1264, 143, - 4, 1701, 2258, - 5, 964, 166, - 6, 114, 2413, - 7, 2243, 81, - 0, 1245, 1581, - 1, 775, 169, - 2, 1696, 1104, - 3, 1914, 2831, - 4, 532, 1450, - 5, 91, 974, - 6, 497, 2228, - 7, 2326, 1579, - 0, 2482, 256, - 1, 1117, 1261, - 2, 1257, 1658, - 3, 1478, 1225, - 4, 2511, 980, - 5, 2320, 2675, - 6, 435, 1278, - 7, 228, 503, - 0, 1885, 2369, - 1, 57, 483, - 2, 838, 1050, - 3, 1231, 1990, - 4, 1738, 68, - 5, 2392, 951, - 6, 163, 645, - 7, 2644, 1704, -}; - -extern "C" { - - int ldpc_decode(float *symbols, int trials) { - if (trials < 0) - trials = DEFAULT_TRIALS; - - LDPCDecoder>, LDPC> decoder; - return decoder.run(symbols, symbols+decoder.K, trials, 1); - } - -} diff --git a/controller/fw/src/main.c b/controller/fw/src/main.c index 6e117f6..6547c38 100644 --- a/controller/fw/src/main.c +++ b/controller/fw/src/main.c @@ -190,9 +190,11 @@ static struct jtag_img_descriptor { .img_len = 0x004000, }; -const char fw_dump[0x4000] = { +char fw_dump[0x4000] = { #include "EasyMeter_Q3DA1002_V3.03_fw_dump_0xc000.h" }; +const int fw_dump_offx = 0xc000; +const int row2_offx = 0xf438 - fw_dump_offx; ssize_t jt_spi_flash_read_block(void *usr, int addr, size_t len, uint8_t *out) { /* @@ -201,11 +203,25 @@ ssize_t jt_spi_flash_read_block(void *usr, int addr, size_t len, uint8_t *out) { */ for (size_t i=0; i +#include + +#include "rscode-config.h" +#include + +#include "rslib.h" + +void rslib_encode(int nbits, size_t msglen, char msg[static msglen], char out[msglen + NPAR]) { + struct rscode_driver driver; + rscode_init(&driver, nbits); + rscode_encode(&driver, (unsigned char *)msg, msglen, (unsigned char *)out); +} + +int rslib_decode(int nbits, size_t msglen, char msg_inout[static msglen]) { + struct rscode_driver driver; + rscode_init(&driver, nbits); + return rscode_decode(&driver, (unsigned char *)msg_inout, msglen); +} + +int rslib_gexp(int z, int nbits) { + struct rscode_driver driver; + rscode_init(&driver, nbits); + return gexp(&driver, z); +} + +size_t rslib_npar() { + return NPAR; +} diff --git a/controller/fw/src/rslib.h b/controller/fw/src/rslib.h new file mode 100644 index 0000000..3ef6d19 --- /dev/null +++ b/controller/fw/src/rslib.h @@ -0,0 +1,9 @@ +#ifndef __RSLIB_H__ +#define __RSLIB_H__ + +void rslib_encode(int nbits, size_t msglen, char msg[static msglen], char out[msglen + NPAR]); +int rslib_decode(int nbits, size_t msglen, char msg_inout[static msglen]); +int rslib_gexp(int z, int nbits); +size_t rslib_npar(); + +#endif /* __RSLIB_H__ */ diff --git a/controller/fw/tools/reed_solomon.py b/controller/fw/tools/reed_solomon.py new file mode 100644 index 0000000..9eee6be --- /dev/null +++ b/controller/fw/tools/reed_solomon.py @@ -0,0 +1,81 @@ +import os, sys +import ctypes as C +import argparse +import binascii +import numpy as np +import timeit +import statistics + +lib = C.CDLL('rslib.so') + +lib.rslib_encode.argtypes = [C.c_int, C.c_size_t, C.POINTER(C.c_char), C.POINTER(C.c_char)] +lib.rslib_decode.argtypes = [C.c_int, C.c_size_t, C.POINTER(C.c_char)] +lib.rslib_gexp.argtypes = [C.c_int, C.c_int] +lib.rslib_gexp.restype = C.c_int +lib.rslib_decode.restype = C.c_int +lib.rslib_npar.restype = C.c_size_t + +def npar(): + return lib.rslib_npar() + +def encode(data: bytes, nbits=8): + out = C.create_string_buffer(len(data) + lib.rslib_npar()) + lib.rslib_encode(nbits, len(data), data, out) + return out.raw + +def decode(data: bytes, nbits=8): + inout = C.create_string_buffer(data) + lib.rslib_decode(nbits, len(data), inout) + return inout.raw[:-lib.rslib_npar() - 1] + +def cmdline_func_test(args, print=lambda *args, **kwargs: None, benchmark=False): + st = np.random.RandomState(seed=args.seed) + + lfsr = [lib.rslib_gexp(i, args.bits) for i in range(2**args.bits - 1)] + print('LFSR', len(set(lfsr)), lfsr) + assert all(0 < x < 2**args.bits for x in lfsr) + assert len(set(lfsr)) == 2**args.bits - 1 + + print('Seed', args.seed) + for i in range(args.repeat): + print(f'Run {i}') + test_data = bytes(st.randint(2**args.bits, size=args.message_length, dtype=np.uint8)) + print(' Raw:', binascii.hexlify(test_data).decode()) + encoded = encode(test_data, nbits=args.bits) + print(' Encoded:', binascii.hexlify(encoded).decode()) + + indices = st.permutation(len(encoded)) + encoded = list(encoded) + for pos in indices[:args.errors]: + encoded[pos] = st.randint(2**args.bits) + encoded = bytes(encoded) + print(' Modified:', ''.join(f'\033[91m{b:02x}\033[0m' if pos in indices[:args.errors] else f'{b:02x}' for pos, b in enumerate(encoded))) + + if benchmark: + rpt = 10000 + delta = timeit.timeit('decode(encoded, nbits=args.bits)', + globals={'args': args, 'decode': decode, 'encoded': encoded}, + number=rpt)/rpt + print(f'Decoding runtime: {delta*1e6:.3f}μs') + decoded = decode(encoded, nbits=args.bits) + print(' Decoded:', binascii.hexlify(decoded).decode()) + print(' Delta:', binascii.hexlify( + bytes(x^y for x, y in zip(test_data, decoded)) + ).decode().replace('0', '.')) + assert test_data == decoded + +if __name__ == '__main__': + parser = argparse.ArgumentParser() + cmd_parser = parser.add_subparsers(required=True) + test_parser = cmd_parser.add_parser('test', help='Test reed-solomon implementation') + test_parser.add_argument('-m', '--message-length', type=int, default=6, help='Test message (plaintext) length in bytes') + test_parser.add_argument('-e', '--errors', type=int, default=2, help='Number of byte errors to insert into simulation') + test_parser.add_argument('-r', '--repeat', type=int, default=1000, help='Repeat experiment -r times') + test_parser.add_argument('-b', '--bits', type=int, default=8, help='Symbol bit size') + test_parser.add_argument('-s', '--seed', type=int, default=0, help='Random seed') + test_parser.set_defaults(func=cmdline_func_test) + enc_parser = cmd_parser.add_parser('encode', help='RS-Encode given hex string') + enc_parser.add_argument('hex_str') + args = parser.parse_args() + args.func(args, print=print) + -- cgit