src/test/crc_native/test_crc.cpp

   1 #include <cstdint>
   2 #include <unity.h>
   3 #include "ucrc_t.h"
   4 #include <crc.h>
   5 #include "common.h"
   6
   7 #ifdef BIG_TEST
   8 #define NUM_ITERATIONS 1000000
   9 #else
  10 #define NUM_ITERATIONS 1000
  11 #endif
  12
  13 static char *genMsg(uint8_t bytes[], int len) {
  14     static char buf[80];
  15     char hex[4];
  16     sprintf(buf, "bytes ");
  17     for (int i = 0; i < len; i++)
  18     {
  19         sprintf(hex, "%02x ", bytes[i]);
  20         strcat(buf, hex);
  21     }
  22     return buf;
  23 }
  24
  25 void test_crc14_implementation_compatibility(void)
  26 {
  27     uint8_t bytes[7];
  28     for (int i = 0; i < sizeof(bytes); i++)
  29         bytes[i] = random() % 255;
  30     bytes[0] &= 0b11;
  31
  32     uCRC_t ccrc = uCRC_t("CRC14", 14, ELRS_CRC14_POLY, 0, false, false, 0);
  33     uint64_t crc = ccrc.get_raw_crc(bytes, 7, 0);
  34
  35     GENERIC_CRC14 ecrc = GENERIC_CRC14(ELRS_CRC14_POLY);
  36     uint16_t c = ecrc.calc(bytes, 7, 0);
  37
  38     TEST_ASSERT_EQUAL_MESSAGE((int)(crc & 0x3FFF), c, genMsg(bytes, sizeof(bytes)));
  39 }
  40
  41 void test_crc14_flip_random(int flip)
  42 {
  43     int false_positive = 0;
  44     GENERIC_CRC14 ccrc = GENERIC_CRC14(ELRS_CRC14_POLY);
  45
  46     for (int x = 0; x < NUM_ITERATIONS; x++)
  47     {
  48         uint8_t bytes[7];
  49         uint8_t fbytes[7];
  50
  51         for (int i = 0; i < sizeof(bytes); i++)
  52             bytes[i] = random() % 255;
  53         bytes[0] &= 0b11;
  54         memcpy(fbytes, bytes, 7);
  55
  56         uint16_t c = ccrc.calc(bytes, 7, 0);
  57
  58         // Flip 'flip' random bits
  59         do {
  60             memcpy(bytes, fbytes, 7);
  61             for (int i = 0; i < flip; i++)
  62             {
  63                 int bit = random() % 50;
  64                 bytes[bit / 8] ^= 1 << (bit % 8);
  65             }
  66         } while (memcmp(fbytes, bytes, 7) == 0);
  67
  68         uint16_t e = ccrc.calc(bytes, 7, 0);
  69         if (c == e)
  70         {
  71             //fprintf(stderr, "False +ve %s\n", genMsg(bytes, sizeof(bytes)));
  72             false_positive++;
  73         }
  74     }
  75     printf("%d out of %d false positives, %f%%\n", false_positive, NUM_ITERATIONS, false_positive * 100.0 / NUM_ITERATIONS);
  76 }
  77
  78 void test_crc14_flip_sequential(int flip)
  79 {
  80     int false_positive = 0;
  81     GENERIC_CRC14 ccrc = GENERIC_CRC14(ELRS_CRC14_POLY);
  82
  83     for (int x=0 ; x<NUM_ITERATIONS ; x++) {
  84         uint8_t bytes[7];
  85         uint8_t fbytes[7];
  86
  87         for (int i = 0; i < sizeof(bytes); i++)
  88             bytes[i] = random() % 255;
  89         bytes[0] &= 0b11;
  90
  91         memcpy(fbytes, bytes, 7);
  92
  93         uint16_t c = ccrc.calc(bytes, 7, 0);
  94
  95         // Flip 'flip' bits starting at a random position
  96         do {
  97             memcpy(bytes, fbytes, 7);
  98             int pos = random() % (50 - flip);
  99             for(int bit=pos ; bit<pos+flip ; bit++) {
 100                 int f = bit>1 ? bit+6 : bit;
 101                 bytes[f / 8] ^= 1 << (f % 8);
 102             }
 103         } while (memcmp(fbytes, bytes, 7) == 0);
 104
 105         uint16_t e = ccrc.calc(bytes, 7, 0);
 106         if (c == e)
 107         {
 108             //fprintf(stderr, "False +ve %s\n", genMsg(bytes, sizeof(bytes)));
 109             false_positive++;
 110         }
 111     }
 112     printf("%d out of %d false positives, %f%%\n", false_positive, NUM_ITERATIONS, false_positive*100.0/NUM_ITERATIONS);
 113 }
 114
 115 void test_crc14_flip_within(int flip)
 116 {
 117     int false_positive = 0;
 118     GENERIC_CRC14 ccrc = GENERIC_CRC14(ELRS_CRC14_POLY);
 119
 120     for (int x = 0; x < NUM_ITERATIONS; x++)
 121     {
 122         uint8_t bytes[7];
 123         uint8_t fbytes[7];
 124
 125         for (int i = 0; i < sizeof(bytes); i++)
 126             bytes[i] = random() % 255;
 127         bytes[0] &= 0b11;
 128
 129         memcpy(fbytes, bytes, 7);
 130
 131         uint16_t c = ccrc.calc(bytes, 7, 0);
 132
 133         // Flip 'flip' bits starting at a random position
 134         int start = random() % (50 - 13);
 135         do {
 136             memcpy(bytes, fbytes, 7);
 137             for (int i = 0; i < flip; i++)
 138             {
 139                 int bit = random() % 13 + start;
 140                 if (bit>1) bit += 6;
 141                 bytes[bit / 8] ^= 1 << (bit % 8);
 142             }
 143         } while (memcmp(fbytes, bytes, 7)==0);
 144
 145         uint16_t e = ccrc.calc(bytes, 7, 0);
 146         if (c == e)
 147         {
 148             //fprintf(stderr, "False +ve %s\n", genMsg(bytes, sizeof(bytes)));
 149             false_positive++;
 150         }
 151     }
 152     printf("%d out of %d false positives, %f%%\n", false_positive, NUM_ITERATIONS, false_positive * 100.0 / NUM_ITERATIONS);
 153 }
 154
 155 void test_crc14_flip5(void)
 156 {
 157     GENERIC_CRC14 ccrc = GENERIC_CRC14(ELRS_CRC14_POLY);
 158
 159     for (int x = 0; x < NUM_ITERATIONS; x++)
 160     {
 161         uint8_t bytes[7];
 162         uint8_t fbytes[7];
 163
 164         for (int i = 0; i < sizeof(bytes); i++)
 165             bytes[i] = random() % 255;
 166         bytes[0] &= 0b11;
 167
 168         memcpy(fbytes, bytes, 7);
 169
 170         uint16_t c = ccrc.calc(bytes, 7, 0);
 171
 172         // Flip 4 random bits
 173         do {
 174             memcpy(bytes, fbytes, 7);
 175             for (int i = 0; i < 4; i++)
 176             {
 177                 int pos = random() % 50;
 178                 if (pos > 1)
 179                     pos += 6;
 180                 bytes[pos / 8] ^= 1 << (pos % 8);
 181             }
 182         }
 183         while (memcmp(fbytes, bytes, 7) == 0);
 184
 185     // Flip all the bits one after the other
 186     for (int i = 0; i < 50; i++)
 187     {
 188         // flip bit i and test
 189         int pos = i;
 190         if (pos > 1)
 191             pos += 6;
 192         bytes[pos / 8] ^= 1 << (pos % 8);
 193
 194         uint16_t e = ccrc.calc(bytes, 7, 0);
 195         if (c == e && memcmp(fbytes, bytes, 7) != 0)
 196         {
 197             fprintf(stderr, "False +ve %s\n", genMsg(bytes, sizeof(bytes)));
 198         }
 199
 200         // flip bit i back again
 201         bytes[pos / 8] ^= 1 << (pos % 8);
 202         }
 203     }
 204 }
 205
 206 void test_crc8(void)
 207 {
 208     // Size of a CRSF packet
 209     uint8_t bytes[11];
 210     for (int i = 0; i < sizeof(bytes); i++)
 211         bytes[i] = random() % 255;
 212
 213     uCRC_t ccrc = uCRC_t("CRC8", 8, ELRS_CRC_POLY, 0, false, false, 0);
 214     uint64_t crc = ccrc.get_raw_crc(bytes, 7, 0);
 215
 216     GENERIC_CRC8 ecrc = GENERIC_CRC8(ELRS_CRC_POLY);
 217     uint16_t c = ecrc.calc(bytes, 7);
 218
 219     TEST_ASSERT_EQUAL_MESSAGE((int)(crc & 0xFF), c, genMsg(bytes, sizeof(bytes)));
 220 }
 221
 222 int main(int argc, char **argv)
 223 {
 224     srandom(micros());
 225 #ifndef BIG_TEST
 226     UNITY_BEGIN();
 227     RUN_TEST(test_crc14_implementation_compatibility);
 228     RUN_TEST(test_crc14_flip5);
 229     RUN_TEST(test_crc8);
 230     UNITY_END();
 231 #endif
 232 #ifdef BIG_TEST
 233     printf("Random flipped bits within 14-bit range\n");
 234     for (int i = 1; i < 31; i++)
 235     {
 236         printf("%2d : ", i);
 237         test_crc14_flip_within(i);
 238     }
 239     printf("============================================================\n");
 240     printf("Flipped bits in a single sequence at random start position\n");
 241     for (int i = 1; i < 31; i++)
 242     {
 243         printf("%2d : ", i);
 244         test_crc14_flip_sequential(i);
 245     }
 246     printf("============================================================\n");
 247     printf("Randomly flipped bits\n");
 248     for (int i = 1; i < 31; i++)
 249     {
 250         printf("%2d : ", i);
 251         test_crc14_flip_random(i);
 252     }
 253     printf("============================================================\n");
 254 #endif
 255
 256     return 0;
 257 }