1 //
2 // This file is part of Dire Wolf, an amateur radio packet TNC.
3 //
4 // Copyright (C) 2019 John Langner, WB2OSZ
5 //
6 // This program is free software: you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation, either version 2 of the License, or
9 // (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program. If not, see <http://www.gnu.org/licenses/>.
18 //
19 // -----------------------------------------------------------------------
20 //
21 //
22 // Some of this is based on:
23 //
24 // FX.25 Encoder
25 // Author: Jim McGuire KB3MPL
26 // Date: 23 October 2007
27 //
28 // This program is a single-file implementation of the FX.25 encapsulation
29 // structure for use with AX.25 data packets. Details of the FX.25
30 // specification are available at:
31 // http://www.stensat.org/Docs/Docs.htm
32 //
33 // This program implements a single RS(255,239) FEC structure. Future
34 // releases will incorporate more capabilities as accommodated in the FX.25
35 // spec.
36 //
37 // The Reed Solomon encoding routines are based on work performed by
38 // Phil Karn. Phil was kind enough to release his code under the GPL, as
39 // noted below. Consequently, this FX.25 implementation is also released
40 // under the terms of the GPL.
41 //
42 // Phil Karn's original copyright notice:
43 /* Test the Reed-Solomon codecs
44 * for various block sizes and with random data and random error patterns
45 *
46 * Copyright 2002 Phil Karn, KA9Q
47 * May be used under the terms of the GNU General Public License (GPL)
48 *
49 */
50
51 #include "direwolf.h"
52
53 #include <stdio.h>
54 #include <stdlib.h>
55 #include <string.h>
56 #include <ctype.h>
57 #include <stdint.h> // uint64_t
58 #include <inttypes.h> // PRIx64
59 #include <assert.h>
60
61 #include "fx25.h"
62 #include "textcolor.h"
63
64
65 #define NTAB 3
66
67 static struct {
68 int symsize; // Symbol size, bits (1-8). Always 8 for this application.
69 int genpoly; // Field generator polynomial coefficients.
70 int fcs; // First root of RS code generator polynomial, index form.
71 int prim; // Primitive element to generate polynomial roots.
72 int nroots; // RS code generator polynomial degree (number of roots).
73 // Same as number of check bytes added.
74 struct rs *rs; // Pointer to RS codec control block. Filled in at init time.
75 } Tab[NTAB] = {
76 {8, 0x11d, 1, 1, 16, NULL }, // RS(255,239)
77 {8, 0x11d, 1, 1, 32, NULL }, // RS(255,223)
78 {8, 0x11d, 1, 1, 64, NULL }, // RS(255,191)
79 };
80
81 /*
82 * Reference: http://www.stensat.org/docs/FX-25_01_06.pdf
83 * FX.25
84 * Forward Error Correction Extension to
85 * AX.25 Link Protocol For Amateur Packet Radio
86 * Version: 0.01 DRAFT
87 * Date: 01 September 2006
88 */
89
90 struct correlation_tag_s {
91 uint64_t value; // 64 bit value, send LSB first.
92 int n_block_radio; // Size of transmitted block, all in bytes.
93 int k_data_radio; // Size of transmitted data part.
94 int n_block_rs; // Size of RS algorithm block.
95 int k_data_rs; // Size of RS algorithm data part.
96 int itab; // Index into Tab array.
97 };
98
99 static const struct correlation_tag_s tags[16] = {
100 /* Tag_00 */ { 0x566ED2717946107ELL, 0, 0, 0, 0, -1 }, // Reserved
101
102 /* Tag_01 */ { 0xB74DB7DF8A532F3ELL, 255, 239, 255, 239, 0 }, // RS(255, 239) 16-byte check value, 239 information bytes
103 /* Tag_02 */ { 0x26FF60A600CC8FDELL, 144, 128, 255, 239, 0 }, // RS(144,128) - shortened RS(255, 239), 128 info bytes
104 /* Tag_03 */ { 0xC7DC0508F3D9B09ELL, 80, 64, 255, 239, 0 }, // RS(80,64) - shortened RS(255, 239), 64 info bytes
105 /* Tag_04 */ { 0x8F056EB4369660EELL, 48, 32, 255, 239, 0 }, // RS(48,32) - shortened RS(255, 239), 32 info bytes
106
107 /* Tag_05 */ { 0x6E260B1AC5835FAELL, 255, 223, 255, 223, 1 }, // RS(255, 223) 32-byte check value, 223 information bytes
108 /* Tag_06 */ { 0xFF94DC634F1CFF4ELL, 160, 128, 255, 223, 1 }, // RS(160,128) - shortened RS(255, 223), 128 info bytes
109 /* Tag_07 */ { 0x1EB7B9CDBC09C00ELL, 96, 64, 255, 223, 1 }, // RS(96,64) - shortened RS(255, 223), 64 info bytes
110 /* Tag_08 */ { 0xDBF869BD2DBB1776LL, 64, 32, 255, 223, 1 }, // RS(64,32) - shortened RS(255, 223), 32 info bytes
111
112 /* Tag_09 */ { 0x3ADB0C13DEAE2836LL, 255, 191, 255, 191, 2 }, // RS(255, 191) 64-byte check value, 191 information bytes
113 /* Tag_0A */ { 0xAB69DB6A543188D6LL, 192, 128, 255, 191, 2 }, // RS(192, 128) - shortened RS(255, 191), 128 info bytes
114 /* Tag_0B */ { 0x4A4ABEC4A724B796LL, 128, 64, 255, 191, 2 }, // RS(128, 64) - shortened RS(255, 191), 64 info bytes
115
116 /* Tag_0C */ { 0x0293D578626B67E6LL, 0, 0, 0, 0, -1 }, // Undefined
117 /* Tag_0D */ { 0xE3B0B0D6917E58A6LL, 0, 0, 0, 0, -1 }, // Undefined
118 /* Tag_0E */ { 0x720267AF1BE1F846LL, 0, 0, 0, 0, -1 }, // Undefined
119 /* Tag_0F */ { 0x93210201E8F4C706LL, 0, 0, 0, 0, -1 } // Undefined
120 };
121
122
123
124 #define CLOSE_ENOUGH 8 // How many bits can be wrong in tag yet consider it a match?
125 // Needs to be large enough to match with significant errors
126 // but not so large to get frequent false matches.
127 // Probably don't want >= 16 because the hamming distance between
128 // any two pairs is 32.
129 // What is a good number? 8?? 12?? 15??
130 // 12 got many false matches with random noise.
131 // Even 8 might be too high. We see 2 or 4 bit errors here
132 // at the point where decoding the block is very improbable.
133 // After 2 months of continuous operation as a digipeater/iGate,
134 // no false triggers were observed. So 8 doesn't seem to be too
135 // high for 1200 bps. No study has been done for 9600 bps.
136
137 // Given a 64 bit correlation tag value, find acceptable match in table.
138 // Return index into table or -1 for no match.
139
140 // Both gcc and clang have a built in function to count the number of '1' bits
141 // in an integer. This can result in a single machine instruction. You might need
142 // to supply your own popcount function if using a different compiler.
143
fx25_tag_find_match(uint64_t t)144 int fx25_tag_find_match (uint64_t t)
145 {
146 for (int c = CTAG_MIN; c <= CTAG_MAX; c++) {
147 if (__builtin_popcountll(t ^ tags[c].value) <= CLOSE_ENOUGH) {
148 //printf ("%016" PRIx64 " received\n", t);
149 //printf ("%016" PRIx64 " tag %d\n", tags[c].value, c);
150 //printf ("%016" PRIx64 " xor, popcount = %d\n", t ^ tags[c].value, __builtin_popcountll(t ^ tags[c].value));
151 return (c);
152 }
153 }
154 return (-1);
155 }
156
157
158
free_rs_char(struct rs * rs)159 void free_rs_char(struct rs *rs){
160 free(rs->alpha_to);
161 free(rs->index_of);
162 free(rs->genpoly);
163 free(rs);
164 }
165
166
167 /*-------------------------------------------------------------
168 *
169 * Name: fx25_init
170 *
171 * Purpose: This must be called once before any of the other fx25 functions.
172 *
173 * Inputs: debug_level - Controls level of informational / debug messages.
174 *
175 * 0 Only errors.
176 * 1 (default) Transmitting ctag. Currently no other way to know this.
177 * 2 Receive correlation tag detected. FEC decode complete.
178 * 3 Dump data going in and out.
179 *
180 * Use command line -dx to increase level or -qx for quiet.
181 *
182 * Description: Initialize 3 Reed-Solomon codecs, for 16, 32, and 64 check bytes.
183 *
184 *--------------------------------------------------------------*/
185
186 static int g_debug_level;
187
fx25_init(int debug_level)188 void fx25_init ( int debug_level )
189 {
190 g_debug_level = debug_level;
191
192 for (int i = 0 ; i < NTAB ; i++) {
193 Tab[i].rs = INIT_RS(Tab[i].symsize, Tab[i].genpoly, Tab[i].fcs, Tab[i].prim, Tab[i].nroots);
194 if (Tab[i].rs == NULL) {
195 text_color_set(DW_COLOR_ERROR);
196 dw_printf("FX.25 internal error: init_rs_char failed!\n");
197 exit(EXIT_FAILURE);
198 }
199 }
200
201 // Verify integrity of tables and assumptions.
202 // This also does a quick check for the popcount function.
203
204 for (int j = 0; j < 16 ; j++) {
205 for (int k = 0; k < 16; k++) {
206 if (j == k) {
207 assert (__builtin_popcountll(tags[j].value ^ tags[k].value) == 0);
208 }
209 else {
210 assert (__builtin_popcountll(tags[j].value ^ tags[k].value) == 32);
211 }
212 }
213 }
214
215 for (int j = CTAG_MIN; j <= CTAG_MAX; j++) {
216 assert (tags[j].n_block_radio - tags[j].k_data_radio == Tab[tags[j].itab].nroots);
217 assert (tags[j].n_block_rs - tags[j].k_data_rs == Tab[tags[j].itab].nroots);
218 assert (tags[j].n_block_rs == FX25_BLOCK_SIZE);
219 }
220
221 assert (fx25_pick_mode (100+1, 239) == 1);
222 assert (fx25_pick_mode (100+1, 240) == -1);
223
224 assert (fx25_pick_mode (100+5, 223) == 5);
225 assert (fx25_pick_mode (100+5, 224) == -1);
226
227 assert (fx25_pick_mode (100+9, 191) == 9);
228 assert (fx25_pick_mode (100+9, 192) == -1);
229
230 assert (fx25_pick_mode (16, 32) == 4);
231 assert (fx25_pick_mode (16, 64) == 3);
232 assert (fx25_pick_mode (16, 128) == 2);
233 assert (fx25_pick_mode (16, 239) == 1);
234 assert (fx25_pick_mode (16, 240) == -1);
235
236 assert (fx25_pick_mode (32, 32) == 8);
237 assert (fx25_pick_mode (32, 64) == 7);
238 assert (fx25_pick_mode (32, 128) == 6);
239 assert (fx25_pick_mode (32, 223) == 5);
240 assert (fx25_pick_mode (32, 234) == -1);
241
242 assert (fx25_pick_mode (64, 64) == 11);
243 assert (fx25_pick_mode (64, 128) == 10);
244 assert (fx25_pick_mode (64, 191) == 9);
245 assert (fx25_pick_mode (64, 192) == -1);
246
247 assert (fx25_pick_mode (1, 32) == 4);
248 assert (fx25_pick_mode (1, 33) == 3);
249 assert (fx25_pick_mode (1, 64) == 3);
250 assert (fx25_pick_mode (1, 65) == 6);
251 assert (fx25_pick_mode (1, 128) == 6);
252 assert (fx25_pick_mode (1, 191) == 9);
253 assert (fx25_pick_mode (1, 223) == 5);
254 assert (fx25_pick_mode (1, 239) == 1);
255 assert (fx25_pick_mode (1, 240) == -1);
256
257 } // fx25_init
258
259
260 // Get properties of specified CTAG number.
261
fx25_get_rs(int ctag_num)262 struct rs *fx25_get_rs (int ctag_num)
263 {
264 assert (ctag_num >= CTAG_MIN && ctag_num <= CTAG_MAX);
265 assert (tags[ctag_num].itab >= 0 && tags[ctag_num].itab < NTAB);
266 assert (Tab[tags[ctag_num].itab].rs != NULL);
267 return (Tab[tags[ctag_num].itab].rs);
268 }
269
fx25_get_ctag_value(int ctag_num)270 uint64_t fx25_get_ctag_value (int ctag_num)
271 {
272 assert (ctag_num >= CTAG_MIN && ctag_num <= CTAG_MAX);
273 return (tags[ctag_num].value);
274 }
275
fx25_get_k_data_radio(int ctag_num)276 int fx25_get_k_data_radio (int ctag_num)
277 {
278 assert (ctag_num >= CTAG_MIN && ctag_num <= CTAG_MAX);
279 return (tags[ctag_num].k_data_radio);
280 }
281
fx25_get_k_data_rs(int ctag_num)282 int fx25_get_k_data_rs (int ctag_num)
283 {
284 assert (ctag_num >= CTAG_MIN && ctag_num <= CTAG_MAX);
285 return (tags[ctag_num].k_data_rs);
286 }
287
fx25_get_nroots(int ctag_num)288 int fx25_get_nroots (int ctag_num)
289 {
290 assert (ctag_num >= CTAG_MIN && ctag_num <= CTAG_MAX);
291 return (Tab[tags[ctag_num].itab].nroots);
292 }
293
fx25_get_debug(void)294 int fx25_get_debug (void)
295 {
296 return (g_debug_level);
297 }
298
299 /*-------------------------------------------------------------
300 *
301 * Name: fx25_pick_mode
302 *
303 * Purpose: Pick suitable transmission format based on user preference
304 * and size of data part required.
305 *
306 * Inputs: fx_mode - 0 = none.
307 * 1 = pick a tag automatically.
308 * 16, 32, 64 = use this many check bytes.
309 * 100 + n = use tag n.
310 *
311 * 0 and 1 would be the most common.
312 * Others are mostly for testing.
313 *
314 * dlen - Required size for transmitted "data" part, in bytes.
315 * This includes the AX.25 frame with bit stuffing and a flag
316 * pattern on each end.
317 *
318 * Returns: Correlation tag number in range of CTAG_MIN thru CTAG_MAX.
319 * -1 is returned for failure.
320 * The caller should fall back to using plain old AX.25.
321 *
322 *--------------------------------------------------------------*/
323
fx25_pick_mode(int fx_mode,int dlen)324 int fx25_pick_mode (int fx_mode, int dlen)
325 {
326 if (fx_mode <= 0) return (-1);
327
328 // Specify a specific tag by adding 100 to the number.
329 // Fails if data won't fit.
330
331 if (fx_mode - 100 >= CTAG_MIN && fx_mode - 100 <= CTAG_MAX) {
332 if (dlen <= fx25_get_k_data_radio(fx_mode - 100)) {
333 return (fx_mode - 100);
334 }
335 else {
336 return (-1); // Assuming caller prints failure message.
337 }
338 }
339
340 // Specify number of check bytes.
341 // Pick the shortest one that can handle the required data length.
342
343 else if (fx_mode == 16 || fx_mode == 32 || fx_mode == 64) {
344 for (int k = CTAG_MAX; k >= CTAG_MIN; k--) {
345 if (fx_mode == fx25_get_nroots(k) && dlen <= fx25_get_k_data_radio(k)) {
346 return (k);
347 }
348 }
349 return (-1);
350 }
351
352 // For any other number, [[ or if the preference was not possible, ?? ]]
353 // try to come up with something reasonable. For shorter frames,
354 // use smaller overhead. For longer frames, where an error is
355 // more probable, use more check bytes. When the data gets even
356 // larger, check bytes must be reduced to fit in block size.
357 // When all else fails, fall back to normal AX.25.
358 // Some of this is from observing UZ7HO Soundmodem behavior.
359 //
360 // Tag Data Check Max Num
361 // Number Bytes Bytes Repaired
362 // ------ ----- ----- -----
363 // 0x04 32 16 8
364 // 0x03 64 16 8
365 // 0x06 128 32 16
366 // 0x09 191 64 32
367 // 0x05 223 32 16
368 // 0x01 239 16 8
369 // none larger
370 //
371 // The PRUG FX.25 TNC has additional modes that will handle larger frames
372 // by using multiple RS blocks. This is a future possibility but needs
373 // to be coordinated with other FX.25 developers so we maintain compatibility.
374
375 static const int prefer[6] = { 0x04, 0x03, 0x06, 0x09, 0x05, 0x01 };
376 for (int k = 0; k < 6; k++) {
377 int m = prefer[k];
378 if (dlen <= fx25_get_k_data_radio(m)) {
379 return (m);
380 }
381 }
382 return (-1);
383
384 // TODO: revisit error messages, produced by caller, when this returns -1.
385
386 }
387
388
389 /* Initialize a Reed-Solomon codec
390 * symsize = symbol size, bits (1-8) - always 8 for this application.
391 * gfpoly = Field generator polynomial coefficients
392 * fcr = first root of RS code generator polynomial, index form
393 * prim = primitive element to generate polynomial roots
394 * nroots = RS code generator polynomial degree (number of roots)
395 */
396
INIT_RS(unsigned int symsize,unsigned int gfpoly,unsigned fcr,unsigned prim,unsigned int nroots)397 struct rs *INIT_RS(unsigned int symsize,unsigned int gfpoly,unsigned fcr,unsigned prim,
398 unsigned int nroots){
399 struct rs *rs;
400 int i, j, sr,root,iprim;
401
402 if(symsize > 8*sizeof(DTYPE))
403 return NULL; /* Need version with ints rather than chars */
404
405 if(fcr >= (1<<symsize))
406 return NULL;
407 if(prim == 0 || prim >= (1<<symsize))
408 return NULL;
409 if(nroots >= (1<<symsize))
410 return NULL; /* Can't have more roots than symbol values! */
411
412 rs = (struct rs *)calloc(1,sizeof(struct rs));
413 rs->mm = symsize;
414 rs->nn = (1<<symsize)-1;
415
416 rs->alpha_to = (DTYPE *)malloc(sizeof(DTYPE)*(rs->nn+1));
417 if(rs->alpha_to == NULL){
418 free(rs);
419 return NULL;
420 }
421 rs->index_of = (DTYPE *)malloc(sizeof(DTYPE)*(rs->nn+1));
422 if(rs->index_of == NULL){
423 free(rs->alpha_to);
424 free(rs);
425 return NULL;
426 }
427
428 /* Generate Galois field lookup tables */
429 rs->index_of[0] = A0; /* log(zero) = -inf */
430 rs->alpha_to[A0] = 0; /* alpha**-inf = 0 */
431 sr = 1;
432 for(i=0;i<rs->nn;i++){
433 rs->index_of[sr] = i;
434 rs->alpha_to[i] = sr;
435 sr <<= 1;
436 if(sr & (1<<symsize))
437 sr ^= gfpoly;
438 sr &= rs->nn;
439 }
440 if(sr != 1){
441 /* field generator polynomial is not primitive! */
442 free(rs->alpha_to);
443 free(rs->index_of);
444 free(rs);
445 return NULL;
446 }
447
448 /* Form RS code generator polynomial from its roots */
449 rs->genpoly = (DTYPE *)malloc(sizeof(DTYPE)*(nroots+1));
450 if(rs->genpoly == NULL){
451 free(rs->alpha_to);
452 free(rs->index_of);
453 free(rs);
454 return NULL;
455 }
456 rs->fcr = fcr;
457 rs->prim = prim;
458 rs->nroots = nroots;
459
460 /* Find prim-th root of 1, used in decoding */
461 for(iprim=1;(iprim % prim) != 0;iprim += rs->nn)
462 ;
463 rs->iprim = iprim / prim;
464
465 rs->genpoly[0] = 1;
466 for (i = 0,root=fcr*prim; i < nroots; i++,root += prim) {
467 rs->genpoly[i+1] = 1;
468
469 /* Multiply rs->genpoly[] by @**(root + x) */
470 for (j = i; j > 0; j--){
471 if (rs->genpoly[j] != 0)
472 rs->genpoly[j] = rs->genpoly[j-1] ^ rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[j]] + root)];
473 else
474 rs->genpoly[j] = rs->genpoly[j-1];
475 }
476 /* rs->genpoly[0] can never be zero */
477 rs->genpoly[0] = rs->alpha_to[modnn(rs,rs->index_of[rs->genpoly[0]] + root)];
478 }
479 /* convert rs->genpoly[] to index form for quicker encoding */
480 for (i = 0; i <= nroots; i++) {
481 rs->genpoly[i] = rs->index_of[rs->genpoly[i]];
482 }
483
484 // diagnostic prints
485 /*
486 printf("Alpha To:\n\r");
487 for (i=0; i < sizeof(DTYPE)*(rs->nn+1); i++)
488 printf("0x%2x,", rs->alpha_to[i]);
489 printf("\n\r");
490
491 printf("Index Of:\n\r");
492 for (i=0; i < sizeof(DTYPE)*(rs->nn+1); i++)
493 printf("0x%2x,", rs->index_of[i]);
494 printf("\n\r");
495
496 printf("GenPoly:\n\r");
497 for (i = 0; i <= nroots; i++)
498 printf("0x%2x,", rs->genpoly[i]);
499 printf("\n\r");
500 */
501 return rs;
502 }
503
504
505 // TEMPORARY!!!
506 // FIXME: We already have multiple copies of this.
507 // Consolidate them into one somewhere.
508
fx_hex_dump(unsigned char * p,int len)509 void fx_hex_dump (unsigned char *p, int len)
510 {
511 int n, i, offset;
512
513 offset = 0;
514 while (len > 0) {
515 n = len < 16 ? len : 16;
516 dw_printf (" %03x: ", offset);
517 for (i=0; i<n; i++) {
518 dw_printf (" %02x", p[i]);
519 }
520 for (i=n; i<16; i++) {
521 dw_printf (" ");
522 }
523 dw_printf (" ");
524 for (i=0; i<n; i++) {
525 dw_printf ("%c", isprint(p[i]) ? p[i] : '.');
526 }
527 dw_printf ("\n");
528 p += 16;
529 offset += 16;
530 len -= 16;
531 }
532 }
533
534