From b292c14790fc225029cba3f80ce8ad6c5652bc4e Mon Sep 17 00:00:00 2001 From: Keith Packard Date: Sat, 23 Jun 2012 16:05:42 -0700 Subject: altos: improve FEC apis to reduce data copying Integrate interleaving and whitening into encode and decode steps. Add CRC checking function for receive. Make ao_fec_test program round-trip the data and verify correctness. Signed-off-by: Keith Packard --- src/test/Makefile | 6 +- src/test/ao_fec_test.c | 198 ++++++++++++++++++++++++++++++++++++++++++++++ src/test/ao_fec_tx_test.c | 192 -------------------------------------------- 3 files changed, 201 insertions(+), 195 deletions(-) create mode 100644 src/test/ao_fec_test.c delete mode 100644 src/test/ao_fec_tx_test.c (limited to 'src/test') diff --git a/src/test/Makefile b/src/test/Makefile index 7bcf24e1..cdcecd51 100644 --- a/src/test/Makefile +++ b/src/test/Makefile @@ -1,6 +1,6 @@ vpath % ..:../core:../drivers:../util -PROGS=ao_flight_test ao_flight_test_baro ao_flight_test_accel ao_flight_test_noisy_accel ao_gps_test ao_gps_test_skytraq ao_convert_test ao_convert_pa_test ao_fec_tx_test +PROGS=ao_flight_test ao_flight_test_baro ao_flight_test_accel ao_flight_test_noisy_accel ao_gps_test ao_gps_test_skytraq ao_convert_test ao_convert_pa_test ao_fec_test KALMAN=make-kalman @@ -40,5 +40,5 @@ ao_convert_pa_test: ao_convert_pa_test.c ao_convert_pa.c altitude-pa.h ao_kalman.h: $(KALMAN) (cd .. && make ao_kalman.h) -ao_fec_tx_test: ao_fec_tx_test.c ao_fec_tx.c ao_viterbi.c - cc $(CFLAGS) -o $@ ao_fec_tx_test.c ../core/ao_fec_tx.c ../core/ao_viterbi.c -lm +ao_fec_test: ao_fec_test.c ao_fec_tx.c ao_viterbi.c + cc $(CFLAGS) -o $@ ao_fec_test.c ../core/ao_fec_tx.c ../core/ao_viterbi.c -lm diff --git a/src/test/ao_fec_test.c b/src/test/ao_fec_test.c new file mode 100644 index 00000000..c7509728 --- /dev/null +++ b/src/test/ao_fec_test.c @@ -0,0 +1,198 @@ +/* + * Copyright © 2012 Keith Packard + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. + */ + +#include +#include +#include +#include +#include +#include + +#ifndef RANDOM_MAX +#define RANDOM_MAX 0x7fffffff +#endif + +static double +rand_real(void) { + return (double) random() / (double) RANDOM_MAX; +} + +static double +gaussian_random(double mean, double dev) +{ + static int save_x_valid = 0; + static double save_x; + double x; + + if (save_x_valid) + { + x = save_x; + save_x_valid = 0; + } + else + { + double w; + double normal_x1, normal_x2; + + do { + normal_x1 = 2 * rand_real () - 1; + normal_x2 = 2 * rand_real () - 1; + w = normal_x1*normal_x1 + normal_x2*normal_x2; + } while (w >= 1 || w < 1E-30); + + w = sqrt(log(w)*(-2./w)); + + /* + * normal_x1 and normal_x2 are independent normally + * distributed variates + */ + + x = normal_x1 * w; + /* save normal_x2 for next call */ + save_x = normal_x2 * w; + save_x_valid = 1; + } + return x * dev + mean; +} + +#define PREPARE_LEN(input_len) ((input_len) + AO_FEC_PREPARE_EXTRA) +#define ENCODE_LEN(input_len) (PREPARE_LEN(input_len) * 2) +#define DECODE_LEN(input_len) ((input_len) + AO_FEC_PREPARE_EXTRA) +#define EXPAND_LEN(input_len) (ENCODE_LEN(input_len) * 8) + +static int +ao_expand(uint8_t *bits, int bits_len, uint8_t *bytes) +{ + int i, bit; + uint8_t b; + + for (i = 0; i < bits_len; i++) { + b = bits[i]; + for (bit = 7; bit >= 0; bit--) + *bytes++ = ((b >> bit) & 1) * 0xff; + } + + return bits_len * 8; +} + +static int +ao_fuzz (uint8_t *in, int in_len, uint8_t *out, double dev) +{ + int i; + int errors = 0; + + for (i = 0; i < in_len; i++) { + double error = gaussian_random(0, dev); + uint8_t byte = in[i]; + + if (error > 0) { + if (error > 0xff) + error = 0xff; + if (error >= 0x80) + errors++; + if (byte < 0x80) + byte += error; + else + byte -= error; + } + out[i] = byte; + } + return errors; +} + +static uint8_t +ao_random_data(uint8_t *out, uint8_t out_len) +{ + uint8_t len = random() % (out_len + 1); + uint8_t i; + + for (i = 0; i < len; i++) + out[i] = random(); + return len; +} + + +int +main(int argc, char **argv) +{ + int trial; + + uint8_t original[120]; + uint8_t original_len; + + uint8_t encode[ENCODE_LEN(sizeof(original))]; + int encode_len; + + uint8_t transmit[EXPAND_LEN(sizeof(original))]; + int transmit_len; + + uint8_t receive[EXPAND_LEN(sizeof(original))]; + int receive_len, receive_errors; + + uint8_t decode[DECODE_LEN(sizeof(original))]; + int decode_len; + + int errors = 0; + int error; + + srandom(0); + for (trial = 0; trial < 10000; trial++) { + + /* Compute some random data */ + original_len = ao_random_data(original, sizeof(original)); + + /* Encode it */ + encode_len = ao_fec_encode(original, original_len, encode); + + /* Expand from 1-bit-per-symbol to 1-byte-per-symbol */ + transmit_len = ao_expand(encode, encode_len, transmit); + + /* Add gaussian noise to the signal */ + receive_errors = ao_fuzz(transmit, transmit_len, receive, 0x30); + receive_len = transmit_len; + + /* Decode it */ + decode_len = ao_fec_decode(receive, receive_len, decode); + + /* Check to see if we received the right data */ + error = 0; + + if (decode_len < original_len + 2) { + printf ("len mis-match\n"); + error++; + } + + if (!ao_fec_check_crc(decode, original_len)) { + printf ("crc mis-match\n"); + error++; + } + + if (memcmp(original, decode, original_len) != 0) { + printf ("data mis-match\n"); + error++; + } + if (error) { + printf ("Errors: %d\n", receive_errors); + ao_fec_dump_bytes(original, original_len, "Input"); + ao_fec_dump_bytes(decode, original_len, "Decode"); + errors += error; + } + } + return errors; +} + + diff --git a/src/test/ao_fec_tx_test.c b/src/test/ao_fec_tx_test.c deleted file mode 100644 index 1b1fd56d..00000000 --- a/src/test/ao_fec_tx_test.c +++ /dev/null @@ -1,192 +0,0 @@ -/* - * Copyright © 2012 Keith Packard - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; version 2 of the License. - * - * This program is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. - */ - -#include -#include -#include -#include -#include - -#ifndef RANDOM_MAX -#define RANDOM_MAX 0x7fffffff -#endif - -static double -rand_real(void) { - return (double) random() / (double) RANDOM_MAX; -} - -static double -gaussian_random(double mean, double dev) -{ - static int save_x_valid = 0; - static double save_x; - double x; - - if (save_x_valid) - { - x = save_x; - save_x_valid = 0; - } - else - { - double w; - double normal_x1, normal_x2; - - do { - normal_x1 = 2 * rand_real () - 1; - normal_x2 = 2 * rand_real () - 1; - w = normal_x1*normal_x1 + normal_x2*normal_x2; - } while (w >= 1 || w < 1E-30); - - w = sqrt(log(w)*(-2./w)); - - /* - * normal_x1 and normal_x2 are independent normally - * distributed variates - */ - - x = normal_x1 * w; - /* save normal_x2 for next call */ - save_x = normal_x2 * w; - save_x_valid = 1; - } - return x * dev + mean; -} - -#define PREPARE_LEN(input_len) ((input_len) + AO_FEC_PREPARE_EXTRA) -#define ENCODE_LEN(input_len) (PREPARE_LEN(input_len) * 2) -#define INTERLEAVE_LEN(input_len) ENCODE_LEN(input_len) - -static int -ao_encode(uint8_t *input, int input_len, uint8_t *output) -{ - uint8_t prepare[PREPARE_LEN(input_len)]; - uint8_t encode[ENCODE_LEN(input_len)]; - uint8_t prepare_len; - uint8_t encode_len; - uint8_t interleave_len; - - ao_fec_dump_bytes(input, input_len, "Input"); - - prepare_len = ao_fec_prepare(input, input_len, prepare); - - ao_fec_dump_bytes(prepare, prepare_len, "Prepare"); - - encode_len = ao_fec_encode(prepare, prepare_len, encode); - - ao_fec_dump_bytes(encode, encode_len, "Encode"); - - interleave_len = ao_fec_interleave(encode, encode_len, output); - - ao_fec_dump_bytes(output, interleave_len, "Interleave"); - - return interleave_len; -} - -#define RADIO_LEN(input_len) (INTERLEAVE_LEN(input_len) * 8) - -static int -ao_radio(uint8_t *bits, int bits_len, uint8_t *bytes) -{ - uint8_t b, *bytes_orig = bytes; - uint8_t interleave[bits_len]; - int i, bit; - - ao_fec_interleave(bits, bits_len, interleave); - - ao_fec_dump_bytes(interleave, bits_len, "De-interleave"); - - for (i = 0; i < bits_len; i++) { - b = interleave[i]; - for (bit = 7; bit >= 0; bit--) - *bytes++ = ((b >> bit) & 1) * 0xff; - } - - ao_fec_dump_bytes(bytes_orig, bits_len * 8, "Bytes"); - - return bits_len * 8; -} - -static int -ao_fuzz (uint8_t *in, int in_len, uint8_t *out, double dev) -{ - int i; - int errors = 0; - - for (i = 0; i < in_len; i++) { - double error = gaussian_random(0, dev); - uint8_t byte = in[i]; - - if (error > 0) { - if (error > 0xff) - error = 0xff; - if (error >= 0x80) - errors++; - if (byte < 0x80) - byte += error; - else - byte -= error; - } - out[i] = byte; - } - - printf ("Introduced %d errors\n", errors); - ao_fec_dump_bytes(out, in_len, "Fuzz"); - return in_len; -} - -static int -ao_decode(uint8_t *bytes, int bytes_len, uint8_t *bits) -{ - int bits_len; - - bits_len = ao_fec_decode(bytes, bytes_len, bits); - - ao_fec_dump_bytes(bits, bits_len, "Decode"); - return bits_len; -} - -int -main(int argc, char **argv) -{ - uint8_t original[4] = { 3, 1, 2, 3 }; - uint8_t encode[INTERLEAVE_LEN(sizeof(original))]; - int encode_len; - - uint8_t transmit[RADIO_LEN(sizeof(original))]; - int transmit_len; - - uint8_t receive[RADIO_LEN(sizeof(original))]; - int receive_len; - - uint8_t decode[INTERLEAVE_LEN(sizeof(original))]; - int decode_len; - - encode_len = ao_encode(original, sizeof(original), encode); - - transmit_len = ao_radio(encode, encode_len, transmit); - - /* apply gaussian noise to test viterbi code against errors */ - receive_len = ao_fuzz(transmit, transmit_len, receive, 0x70); - - decode_len = ao_decode(receive, receive_len, decode); - - return decode_len >= sizeof(original); -} - - -- cgit v1.2.3