git.gag.com Git - fw/altos/blob - src/test/ao_fec_test.c

   1 /*
   2  * Copyright © 2012 Keith Packard <keithp@keithp.com>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; version 2 of the License.
   7  *
   8  * This program is distributed in the hope that it will be useful, but
   9  * WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public License along
  14  * with this program; if not, write to the Free Software Foundation, Inc.,
  15  * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
  16  */
  17
  18 #include <ao_fec.h>
  19 #include <stdlib.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <math.h>
  23 #include <string.h>
  24
  25 #ifndef RANDOM_MAX
  26 #define RANDOM_MAX 0x7fffffff
  27 #endif
  28
  29 static double
  30 rand_real(void) {
  31         return (double) random() / (double) RANDOM_MAX;
  32 }
  33
  34 static double
  35 gaussian_random(double mean, double dev)
  36 {
  37         static int      save_x_valid = 0;
  38         static double   save_x;
  39         double          x;
  40
  41         if (save_x_valid)
  42         {
  43                 x = save_x;
  44                 save_x_valid = 0;
  45         }
  46         else
  47         {
  48                 double    w;
  49                 double    normal_x1, normal_x2;
  50
  51                 do {
  52                         normal_x1 = 2 * rand_real () - 1;
  53                         normal_x2 = 2 * rand_real () - 1;
  54                         w = normal_x1*normal_x1 + normal_x2*normal_x2;
  55                 } while (w >= 1 || w < 1E-30);
  56
  57                 w = sqrt(log(w)*(-2./w));
  58
  59                 /*
  60                  * normal_x1 and normal_x2 are independent normally
  61                  * distributed variates
  62                  */
  63
  64                 x = normal_x1 * w;
  65                 /* save normal_x2 for next call */
  66                 save_x = normal_x2 * w;
  67                 save_x_valid = 1;
  68         }
  69         return x * dev + mean;
  70 }
  71
  72 #define PREPARE_LEN(input_len)          ((input_len) + AO_FEC_PREPARE_EXTRA)
  73 #define ENCODE_LEN(input_len)           (PREPARE_LEN(input_len) * 2)
  74 #define DECODE_LEN(input_len)           ((input_len) + AO_FEC_PREPARE_EXTRA)
  75 #define EXPAND_LEN(input_len)           (ENCODE_LEN(input_len) * 8)
  76
  77 static int
  78 ao_expand(uint8_t *bits, int bits_len, uint8_t *bytes)
  79 {
  80         int     i, bit;
  81         uint8_t b;
  82
  83         for (i = 0; i < bits_len; i++) {
  84                 b = bits[i];
  85                 for (bit = 7; bit >= 0; bit--)
  86                         *bytes++ = ((b >> bit) & 1) * 0xff;
  87         }
  88
  89         return bits_len * 8;
  90 }
  91
  92 static int
  93 ao_fuzz (uint8_t *in, int in_len, uint8_t *out, double dev)
  94 {
  95         int     i;
  96         int     errors = 0;
  97
  98         for (i = 0; i < in_len; i++) {
  99                 double  error = gaussian_random(0, dev);
 100                 uint8_t byte = in[i];
 101
 102                 if (error > 0) {
 103                         if (error > 0xff)
 104                                 error = 0xff;
 105                         if (error >= 0x80)
 106                                 errors++;
 107                         if (byte < 0x80)
 108                                 byte += error;
 109                         else
 110                                 byte -= error;
 111                 }
 112                 out[i] = byte;
 113         }
 114         return errors;
 115 }
 116
 117 static uint8_t
 118 ao_random_data(uint8_t  *out, uint8_t out_len)
 119 {
 120         uint8_t len = random() % (out_len + 1);
 121         uint8_t i;
 122
 123         for (i = 0; i < len; i++)
 124                 out[i] = random();
 125         return len;
 126 }
 127
 128
 129 int
 130 main(int argc, char **argv)
 131 {
 132         int             trial;
 133
 134         uint8_t         original[120];
 135         uint8_t         original_len;
 136
 137         uint8_t         encode[ENCODE_LEN(sizeof(original))];
 138         int             encode_len;
 139
 140         uint8_t         transmit[EXPAND_LEN(sizeof(original))];
 141         int             transmit_len;
 142
 143         uint8_t         receive[EXPAND_LEN(sizeof(original))];
 144         int             receive_len, receive_errors;
 145
 146         uint8_t         decode[DECODE_LEN(sizeof(original))];
 147         int             decode_len;
 148
 149         int             errors = 0;
 150         int             error;
 151
 152         srandom(0);
 153         for (trial = 0; trial < 10000; trial++) {
 154
 155                 /* Compute some random data */
 156                 original_len = ao_random_data(original, sizeof(original));
 157
 158                 /* Encode it */
 159                 encode_len = ao_fec_encode(original, original_len, encode);
 160
 161                 /* Expand from 1-bit-per-symbol to 1-byte-per-symbol */
 162                 transmit_len = ao_expand(encode, encode_len, transmit);
 163
 164                 /* Add gaussian noise to the signal */
 165                 receive_errors = ao_fuzz(transmit, transmit_len, receive, 0x30);
 166                 receive_len = transmit_len;
 167
 168                 /* Decode it */
 169                 decode_len = ao_fec_decode(receive, receive_len, decode);
 170
 171                 /* Check to see if we received the right data */
 172                 error = 0;
 173
 174                 if (decode_len < original_len + 2) {
 175                         printf ("len mis-match\n");
 176                         error++;
 177                 }
 178
 179                 if (!ao_fec_check_crc(decode, original_len)) {
 180                         printf ("crc mis-match\n");
 181                         error++;
 182                 }
 183
 184                 if (memcmp(original, decode, original_len) != 0) {
 185                         printf ("data mis-match\n");
 186                         error++;
 187                 }
 188                 if (error) {
 189                         printf ("Errors: %d\n", receive_errors);
 190                         ao_fec_dump_bytes(original, original_len, "Input");
 191                         ao_fec_dump_bytes(decode, original_len, "Decode");
 192                         errors += error;
 193                 }
 194         }
 195         return errors;
 196 }
 197
 198