1 /*
2 * Copyright (c) 2024 A Labs GmbH
3 * Copyright (c) 2024 tado GmbH
4 *
5 * SPDX-License-Identifier: Apache-2.0
6 */
7
8 /*
9 * Implementation of the fragment encoding algorithm described in the LoRaWAN TS004-1.0.0.
10 * https://lora-alliance.org/wp-content/uploads/2020/11/fragmented_data_block_transport_v1.0.0.pdf
11 *
12 * Note: This algorithm is not compatible with TS004-2.0.0, which has some subtle differences
13 * in the parity matrix generation.
14 *
15 * Variable naming according to LoRaWAN specification:
16 *
17 * M: Number of uncoded fragments (original data)
18 * N: Number of coded fragments (including the original data at the beginning)
19 * CR: Coding ratio M/N
20 */
21
22 #include "frag_encoder.h"
23
24 #include <zephyr/sys/util.h>
25 #include <zephyr/logging/log.h>
26
27 LOG_MODULE_REGISTER(lorawan_frag_enc, CONFIG_LORAWAN_SERVICES_LOG_LEVEL);
28
29 /**
30 * Generate a 23bit Pseudorandom Binary Sequence (PRBS)
31 *
32 * @param seed Seed input value
33 *
34 * @returns Pseudorandom output value
35 */
prbs23(int32_t seed)36 static int32_t prbs23(int32_t seed)
37 {
38 int32_t b0 = seed & 1;
39 int32_t b1 = (seed & 32) / 32;
40
41 return (seed / 2) + ((b0 ^ b1) << 22);
42 }
43
44 /**
45 * Generate vector for coded fragment n of the MxN parity matrix
46 *
47 * @param m Total number of uncoded fragments (M)
48 * @param n Coded fragment number (starting at 1 and not 0)
49 * @param vec Output vector (buffer size must be greater than m)
50 */
lorawan_fec_parity_matrix_vector(int m,int n,uint8_t * vec)51 void lorawan_fec_parity_matrix_vector(int m, int n, uint8_t *vec)
52 {
53 int mm, x, r;
54
55 memset(vec, 0, m);
56
57 /*
58 * Powers of 2 must be treated differently to make sure matrix content is close
59 * to random. Powers of 2 tend to generate patterns.
60 */
61 if (is_power_of_two(m)) {
62 mm = m + 1;
63 } else {
64 mm = m;
65 }
66
67 x = 1 + (1001 * n);
68
69 for (int nb_coeff = 0; nb_coeff < (m / 2); nb_coeff++) {
70 r = (1 << 16);
71 while (r >= m) {
72 x = prbs23(x);
73 r = x % mm;
74 }
75 vec[r] = 1;
76 }
77 }
78
lorawan_frag_encoder(const uint8_t * uncoded,size_t uncoded_len,uint8_t * coded,size_t coded_size,size_t frag_size,unsigned int redundant_frags)79 int lorawan_frag_encoder(const uint8_t *uncoded, size_t uncoded_len, uint8_t *coded,
80 size_t coded_size, size_t frag_size, unsigned int redundant_frags)
81 {
82 int uncoded_frags = DIV_ROUND_UP(uncoded_len, frag_size);
83 int coded_frags = uncoded_frags + redundant_frags;
84 uint8_t parity_vec[frag_size];
85
86 memset(parity_vec, 0, sizeof(parity_vec));
87
88 if (coded_size < coded_frags * frag_size) {
89 LOG_ERR("output buffer not large enough");
90 return -EINVAL;
91 }
92
93 /* copy uncoded frags to the beginning of coded fragments and pad with zeros */
94 memcpy(coded, uncoded, uncoded_len);
95 memset(coded + uncoded_len, 0, uncoded_frags * frag_size - uncoded_len);
96
97 /* generate remaining coded (redundant) frags */
98 for (int i = 1; i <= redundant_frags; i++) {
99 lorawan_fec_parity_matrix_vector(uncoded_frags, i, parity_vec);
100
101 uint8_t *out = coded + (uncoded_frags + i - 1) * frag_size;
102
103 for (int j = 0; j < uncoded_frags; j++) {
104 if (parity_vec[j] == 1) {
105 for (int m = 0; m < frag_size; m++) {
106 out[m] ^= coded[j * frag_size + m];
107 }
108 }
109 }
110 }
111
112 return 0;
113 }
114
