| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /* | ||
| 2 | * Common code for ECC calculations. | ||
| 3 | * Copyright © 2005-2026, albinoloverats ~ Software Development | ||
| 4 | * email: webmaster@albinoloverats.net | ||
| 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 3 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 | * ecc Version 1.2 by Paul Flaherty (paulf@stanford.edu) | ||
| 23 | * Copyright (C) 1993 Free Software Foundation, Inc. | ||
| 24 | * | ||
| 25 | * Basic Software Tool for Encoding and Decoding Files. | ||
| 26 | * | ||
| 27 | * This is a simple stream encoder. It takes a buffer of data 249 bytes | ||
| 28 | * (encode) - or 255 bytes (decode) - and copies the corresponding | ||
| 29 | * encoded/decoded block to the output buffer. An encoded block contains | ||
| 30 | * 249 data bytes and 6 redundancy bytes. | ||
| 31 | */ | ||
| 32 | |||
| 33 | #include <stdio.h> | ||
| 34 | #include <stdlib.h> | ||
| 35 | #include <string.h> | ||
| 36 | #include <inttypes.h> | ||
| 37 | |||
| 38 | #include "ecc.h" | ||
| 39 | |||
| 40 | |||
| 41 | /* Multiply two field elements */ | ||
| 42 | #define GF_MUL(A, B) ((A) == 0 || (B) == 0 ? 0 : e2v[(v2e[A] + v2e[B]) % ECC_CAPACITY]) | ||
| 43 | /* Add two field elements. Subtraction and addition are equivalent */ | ||
| 44 | #define GF_ADD(A, B) ((A) ^ (B)) | ||
| 45 | /* Invert a field element, for division */ | ||
| 46 | #define GF_INV(A) (e2v[ECC_CAPACITY - v2e[A]]) | ||
| 47 | /* Exponentiation. Convert to exponential notation, mod ECC_CAPACITY */ | ||
| 48 | #define GF_EXP(A, B) ((A) == 0 ? 0 : e2v[(v2e[A] * (B)) % ECC_CAPACITY]) | ||
| 49 | |||
| 50 | #define REVERSE(A, L) \ | ||
| 51 | for (int i = 0, j = (L) - 1; i < (L) / 2; i++, j--) \ | ||
| 52 | { \ | ||
| 53 | A[i] ^= A[j]; \ | ||
| 54 | A[j] ^= A[i]; \ | ||
| 55 | A[i] ^= A[j]; \ | ||
| 56 | } | ||
| 57 | |||
| 58 | |||
| 59 | static const uint8_t g[ECC_OFFSET] = { 0x75, 0x31, 0x3A, 0x9E, 0x04, 0x7E }; | ||
| 60 | |||
| 61 | static const uint8_t e2v[ECC_CAPACITY + 1] = | ||
| 62 | { | ||
| 63 | 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1D, 0x3A, 0x74, 0xE8, 0xCD, 0x87, 0x13, 0x26, | ||
| 64 | 0x4C, 0x98, 0x2D, 0x5A, 0xB4, 0x75, 0xEA, 0xC9, 0x8F, 0x03, 0x06, 0x0C, 0x18, 0x30, 0x60, 0xC0, | ||
| 65 | 0x9D, 0x27, 0x4E, 0x9C, 0x25, 0x4A, 0x94, 0x35, 0x6A, 0xD4, 0xB5, 0x77, 0xEE, 0xC1, 0x9F, 0x23, | ||
| 66 | 0x46, 0x8C, 0x05, 0x0A, 0x14, 0x28, 0x50, 0xA0, 0x5D, 0xBA, 0x69, 0xD2, 0xB9, 0x6F, 0xDE, 0xA1, | ||
| 67 | 0x5F, 0xBE, 0x61, 0xC2, 0x99, 0x2F, 0x5E, 0xBC, 0x65, 0xCA, 0x89, 0x0F, 0x1E, 0x3C, 0x78, 0xF0, | ||
| 68 | 0xFD, 0xE7, 0xD3, 0xBB, 0x6B, 0xD6, 0xB1, 0x7F, 0xFE, 0xE1, 0xDF, 0xA3, 0x5B, 0xB6, 0x71, 0xE2, | ||
| 69 | 0xD9, 0xAF, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0D, 0x1A, 0x34, 0x68, 0xD0, 0xBD, 0x67, 0xCE, | ||
| 70 | 0x81, 0x1F, 0x3E, 0x7C, 0xF8, 0xED, 0xC7, 0x93, 0x3B, 0x76, 0xEC, 0xC5, 0x97, 0x33, 0x66, 0xCC, | ||
| 71 | 0x85, 0x17, 0x2E, 0x5C, 0xB8, 0x6D, 0xDA, 0xA9, 0x4F, 0x9E, 0x21, 0x42, 0x84, 0x15, 0x2A, 0x54, | ||
| 72 | 0xA8, 0x4D, 0x9A, 0x29, 0x52, 0xA4, 0x55, 0xAA, 0x49, 0x92, 0x39, 0x72, 0xE4, 0xD5, 0xB7, 0x73, | ||
| 73 | 0xE6, 0xD1, 0xBF, 0x63, 0xC6, 0x91, 0x3F, 0x7E, 0xFC, 0xE5, 0xD7, 0xB3, 0x7B, 0xF6, 0xF1, 0xFF, | ||
| 74 | 0xE3, 0xDB, 0xAB, 0x4B, 0x96, 0x31, 0x62, 0xC4, 0x95, 0x37, 0x6E, 0xDC, 0xA5, 0x57, 0xAE, 0x41, | ||
| 75 | 0x82, 0x19, 0x32, 0x64, 0xC8, 0x8D, 0x07, 0x0E, 0x1C, 0x38, 0x70, 0xE0, 0xDD, 0xA7, 0x53, 0xA6, | ||
| 76 | 0x51, 0xA2, 0x59, 0xB2, 0x79, 0xF2, 0xF9, 0xEF, 0xC3, 0x9B, 0x2B, 0x56, 0xAC, 0x45, 0x8A, 0x09, | ||
| 77 | 0x12, 0x24, 0x48, 0x90, 0x3D, 0x7A, 0xF4, 0xF5, 0xF7, 0xF3, 0xFB, 0xEB, 0xCB, 0x8B, 0x0B, 0x16, | ||
| 78 | 0x2C, 0x58, 0xB0, 0x7D, 0xFA, 0xE9, 0xCF, 0x83, 0x1B, 0x36, 0x6C, 0xD8, 0xAD, 0x47, 0x8E, 0x01 | ||
| 79 | }; | ||
| 80 | |||
| 81 | static const uint8_t v2e[ECC_CAPACITY + 1] = | ||
| 82 | { | ||
| 83 | 0xFF, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1A, 0xC6, 0x03, 0xDF, 0x33, 0xEE, 0x1B, 0x68, 0xC7, 0x4B, | ||
| 84 | 0x04, 0x64, 0xE0, 0x0E, 0x34, 0x8D, 0xEF, 0x81, 0x1C, 0xC1, 0x69, 0xF8, 0xC8, 0x08, 0x4C, 0x71, | ||
| 85 | 0x05, 0x8A, 0x65, 0x2F, 0xE1, 0x24, 0x0F, 0x21, 0x35, 0x93, 0x8E, 0xDA, 0xF0, 0x12, 0x82, 0x45, | ||
| 86 | 0x1D, 0xB5, 0xC2, 0x7D, 0x6A, 0x27, 0xF9, 0xB9, 0xC9, 0x9A, 0x09, 0x78, 0x4D, 0xE4, 0x72, 0xA6, | ||
| 87 | 0x06, 0xBF, 0x8B, 0x62, 0x66, 0xDD, 0x30, 0xFD, 0xE2, 0x98, 0x25, 0xB3, 0x10, 0x91, 0x22, 0x88, | ||
| 88 | 0x36, 0xD0, 0x94, 0xCE, 0x8F, 0x96, 0xDB, 0xBD, 0xF1, 0xD2, 0x13, 0x5C, 0x83, 0x38, 0x46, 0x40, | ||
| 89 | 0x1E, 0x42, 0xB6, 0xA3, 0xC3, 0x48, 0x7E, 0x6E, 0x6B, 0x3A, 0x28, 0x54, 0xFA, 0x85, 0xBA, 0x3D, | ||
| 90 | 0xCA, 0x5E, 0x9B, 0x9F, 0x0A, 0x15, 0x79, 0x2B, 0x4E, 0xD4, 0xE5, 0xAC, 0x73, 0xF3, 0xA7, 0x57, | ||
| 91 | 0x07, 0x70, 0xC0, 0xF7, 0x8C, 0x80, 0x63, 0x0D, 0x67, 0x4A, 0xDE, 0xED, 0x31, 0xC5, 0xFE, 0x18, | ||
| 92 | 0xE3, 0xA5, 0x99, 0x77, 0x26, 0xB8, 0xB4, 0x7C, 0x11, 0x44, 0x92, 0xD9, 0x23, 0x20, 0x89, 0x2E, | ||
| 93 | 0x37, 0x3F, 0xD1, 0x5B, 0x95, 0xBC, 0xCF, 0xCD, 0x90, 0x87, 0x97, 0xB2, 0xDC, 0xFC, 0xBE, 0x61, | ||
| 94 | 0xF2, 0x56, 0xD3, 0xAB, 0x14, 0x2A, 0x5D, 0x9E, 0x84, 0x3C, 0x39, 0x53, 0x47, 0x6D, 0x41, 0xA2, | ||
| 95 | 0x1F, 0x2D, 0x43, 0xD8, 0xB7, 0x7B, 0xA4, 0x76, 0xC4, 0x17, 0x49, 0xEC, 0x7F, 0x0C, 0x6F, 0xF6, | ||
| 96 | 0x6C, 0xA1, 0x3B, 0x52, 0x29, 0x9D, 0x55, 0xAA, 0xFB, 0x60, 0x86, 0xB1, 0xBB, 0xCC, 0x3E, 0x5A, | ||
| 97 | 0xCB, 0x59, 0x5F, 0xB0, 0x9C, 0xA9, 0xA0, 0x51, 0x0B, 0xF5, 0x16, 0xEB, 0x7A, 0x75, 0x2C, 0xD7, | ||
| 98 | 0x4F, 0xAE, 0xD5, 0xE9, 0xE6, 0xE7, 0xAD, 0xE8, 0x74, 0xD6, 0xF4, 0xEA, 0xA8, 0x50, 0x58, 0xAF | ||
| 99 | }; | ||
| 100 | |||
| 101 | |||
| 102 | /* | ||
| 103 | * Polynomial Evaluator, used to determine the Syndrome Vector. This is | ||
| 104 | * relatively straightforward, and there are faster algorithms. | ||
| 105 | */ | ||
| 106 | 30 | static uint8_t evalpoly(uint8_t p[ECC_CAPACITY], uint8_t x) | |
| 107 | { | ||
| 108 | 30 | uint8_t y = 0; | |
| 109 |
2/2✓ Branch 0 taken 7650 times.
✓ Branch 1 taken 30 times.
|
7680 | for (int i = 0; i < ECC_CAPACITY; i++) |
| 110 |
5/8✓ Branch 0 taken 7620 times.
✓ Branch 1 taken 30 times.
✓ Branch 2 taken 7620 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 7620 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 7620 times.
✗ Branch 7 not taken.
|
7650 | y = GF_ADD(y, GF_MUL(p[i], GF_EXP(x, i))); |
| 111 | 30 | return y; | |
| 112 | } | ||
| 113 | |||
| 114 | /* | ||
| 115 | * Determine the Syndrome Vector. Note that in s[0] we return the OR of | ||
| 116 | * all of the syndromes; this allows for an easy check for the no - error | ||
| 117 | * condition. | ||
| 118 | */ | ||
| 119 | 5 | static void syndrome(uint8_t c[ECC_CAPACITY], uint8_t s[7]) | |
| 120 | { | ||
| 121 | 5 | s[0] = 0; | |
| 122 |
2/2✓ Branch 0 taken 30 times.
✓ Branch 1 taken 5 times.
|
35 | for (int i = 1; i < ECC_OFFSET + 1; i++) |
| 123 | { | ||
| 124 | 30 | s[i] = evalpoly(c, e2v[i]); | |
| 125 | 30 | s[0] |= s[i]; | |
| 126 | } | ||
| 127 | 5 | } | |
| 128 | |||
| 129 | /* | ||
| 130 | * Determine the number of errors in a block. Since we have to find the | ||
| 131 | * determinant of the S[] matrix in order to determine singularity, we | ||
| 132 | * also return the determinant to be used by the Cramer's Rule correction | ||
| 133 | * algorithm. | ||
| 134 | */ | ||
| 135 | 4 | static void errnum(uint8_t s[ECC_OFFSET + 1], uint8_t *det, int *errs) | |
| 136 | { | ||
| 137 |
6/12✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 4 times.
✗ Branch 11 not taken.
|
4 | *det = GF_MUL(s[2], GF_MUL(s[4], s[6])); |
| 138 |
6/12✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 4 times.
✗ Branch 11 not taken.
|
4 | *det = GF_ADD(*det, GF_MUL(s[2], GF_MUL(s[5], s[5]))); |
| 139 |
6/12✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 4 times.
✗ Branch 11 not taken.
|
4 | *det = GF_ADD(*det, GF_MUL(s[6], GF_MUL(s[3], s[3]))); |
| 140 |
6/12✓ Branch 0 taken 4 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 4 times.
✗ Branch 11 not taken.
|
4 | *det = GF_ADD(*det, GF_MUL(s[4], GF_MUL(s[4], s[4]))); |
| 141 | 4 | *errs = 3; | |
| 142 | |||
| 143 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
|
4 | if (*det != 0) |
| 144 | 2 | return; | |
| 145 | |||
| 146 |
3/6✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
|
2 | *det = GF_ADD(GF_MUL(s[2], s[4]), GF_EXP(s[3], 2)); |
| 147 | 2 | *errs = 2; | |
| 148 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
|
2 | if (*det != 0) |
| 149 | 1 | return; | |
| 150 | |||
| 151 | 1 | *det = s[1]; | |
| 152 | 1 | *errs = 1; | |
| 153 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | if (*det != 0) |
| 154 | 1 | return; | |
| 155 | |||
| 156 | ✗ | *errs = 4; | |
| 157 | } | ||
| 158 | |||
| 159 | /* | ||
| 160 | * Polynomial Solver. Simple exhaustive search, as solving polynomials is | ||
| 161 | * generally NP - Complete anyway. | ||
| 162 | */ | ||
| 163 | 3 | static void polysolve(uint8_t polynom[4], uint8_t roots[3], int *numsol) | |
| 164 | { | ||
| 165 | 3 | *numsol = 0; | |
| 166 | |||
| 167 |
2/2✓ Branch 0 taken 765 times.
✓ Branch 1 taken 3 times.
|
768 | for (int i = 0; i < ECC_CAPACITY; i++) |
| 168 | { | ||
| 169 | 765 | uint8_t y = 0; | |
| 170 |
2/2✓ Branch 0 taken 3060 times.
✓ Branch 1 taken 765 times.
|
3825 | for (int j = 0; j < 4; j++) |
| 171 |
5/8✓ Branch 0 taken 2805 times.
✓ Branch 1 taken 255 times.
✓ Branch 2 taken 2805 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2805 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2805 times.
✗ Branch 7 not taken.
|
3060 | y = GF_ADD(y, GF_MUL(polynom[j], GF_EXP(e2v[i], j))); |
| 172 |
2/2✓ Branch 0 taken 5 times.
✓ Branch 1 taken 760 times.
|
765 | if (y == 0) |
| 173 | 5 | roots[(*numsol)++] = e2v[i]; | |
| 174 | } | ||
| 175 | 3 | } | |
| 176 | |||
| 177 | |||
| 178 | /* | ||
| 179 | * Full implementation of the three error correcting Peterson decoder. For | ||
| 180 | * t<6, it is faster than Massey - Berlekamp. It is also somewhat more | ||
| 181 | * intuitive. | ||
| 182 | */ | ||
| 183 | 5 | extern void ecc_decode(uint8_t code[ECC_CAPACITY], uint8_t mesg[ECC_CAPACITY], int *errcode) | |
| 184 | { | ||
| 185 |
2/2✓ Branch 0 taken 635 times.
✓ Branch 1 taken 5 times.
|
640 | REVERSE(code, ECC_CAPACITY); |
| 186 | |||
| 187 | uint8_t syn[ECC_OFFSET + 1], deter, z[4], e0, e1, e2, n0, n1, n2, w0, w1, w2, x0, x[3]; | ||
| 188 | int sols; | ||
| 189 | |||
| 190 | 5 | *errcode = 0; | |
| 191 | |||
| 192 | /* | ||
| 193 | * First, get the message out of the code, so that even if we can't correct | ||
| 194 | * it, we return an estimate. | ||
| 195 | */ | ||
| 196 |
2/2✓ Branch 0 taken 1245 times.
✓ Branch 1 taken 5 times.
|
1250 | for (int i = 0; i < ECC_PAYLOAD; i++) |
| 197 | 1245 | mesg[i] = code[(ECC_CAPACITY - 1) - i]; | |
| 198 | |||
| 199 | 5 | syndrome(code, syn); | |
| 200 | |||
| 201 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
|
5 | if (syn[0] == 0) |
| 202 | 5 | return; | |
| 203 | |||
| 204 | /* | ||
| 205 | * We now know we have at least one error. If there are no errors detected, | ||
| 206 | * we assume that something funny is going on, and so return with errcode 4, | ||
| 207 | * else pass the number of errors back via errcode. | ||
| 208 | */ | ||
| 209 | 4 | errnum(syn, &deter, errcode); | |
| 210 | |||
| 211 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 4 times.
|
4 | if (*errcode == 4) |
| 212 | ✗ | return; | |
| 213 | |||
| 214 | /* Having obtained the syndrome, the number of errors, and the determinant, | ||
| 215 | * we now proceed to correct the block. If we do not find exactly the | ||
| 216 | * number of solutions equal to the number of errors, we have exceeded our | ||
| 217 | * error capacity, and return with the block uncorrected, and errcode 4. | ||
| 218 | */ | ||
| 219 | |||
| 220 |
3/4✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
4 | switch (*errcode) |
| 221 | { | ||
| 222 | 1 | case 1: | |
| 223 |
2/4✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | x0 = GF_MUL(syn[2], GF_INV(syn[1])); |
| 224 |
4/8✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
|
1 | w0 = GF_MUL(GF_EXP(syn[1], 2), GF_INV(syn[2])); |
| 225 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | if (v2e[x0] > 5) |
| 226 | 1 | mesg[(ECC_CAPACITY - 1) - v2e[x0]] = GF_ADD(mesg[(ECC_CAPACITY - 1) - v2e[x0]], w0); | |
| 227 | 1 | return; | |
| 228 | |||
| 229 | 1 | case 2: | |
| 230 |
8/16✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 1 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
|
1 | z[0] = GF_MUL(GF_ADD(GF_MUL(syn[1], syn[3]), GF_EXP(syn[2], 2)), GF_INV(deter)); |
| 231 |
10/20✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 1 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 1 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 1 times.
✗ Branch 19 not taken.
|
1 | z[1] = GF_MUL(GF_ADD(GF_MUL(syn[2], syn[3]), GF_MUL(syn[1], syn[4])), GF_INV(deter)); |
| 232 | 1 | z[2] = 1; | |
| 233 | 1 | z[3] = 0; | |
| 234 | 1 | polysolve(z, x, &sols); | |
| 235 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | if (sols != 2) |
| 236 | { | ||
| 237 | ✗ | *errcode = 4; | |
| 238 | ✗ | return; | |
| 239 | } | ||
| 240 |
2/4✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | w0 = GF_MUL(z[0], syn[1]); |
| 241 |
4/8✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
|
1 | w1 = GF_ADD(GF_MUL(z[0], syn[2]), GF_MUL(z[1], syn[1])); |
| 242 | 1 | n0 = (ECC_CAPACITY - 1) - v2e[GF_INV(x[0])]; | |
| 243 | 1 | n1 = (ECC_CAPACITY - 1) - v2e[GF_INV(x[1])]; | |
| 244 |
6/12✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
|
1 | e0 = GF_MUL(GF_ADD(w0, GF_MUL(w1, x[0])), GF_INV(z[1])); |
| 245 |
6/12✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
|
1 | e1 = GF_MUL(GF_ADD(w0, GF_MUL(w1, x[1])), GF_INV(z[1])); |
| 246 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1 times.
|
1 | if (n0 < ECC_PAYLOAD) |
| 247 | ✗ | mesg[n0] = GF_ADD(mesg[n0], e0); | |
| 248 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | if (n1 < ECC_PAYLOAD) |
| 249 | 1 | mesg[n1] = GF_ADD(mesg[n1], e1); | |
| 250 | 1 | return; | |
| 251 | |||
| 252 | 2 | case 3: | |
| 253 | 2 | z[3] = 1; | |
| 254 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[2] = GF_MUL(syn[1], GF_MUL(syn[4], syn[6])); |
| 255 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[2] = GF_ADD(z[2], GF_MUL(syn[1], GF_MUL(syn[5], syn[5]))); |
| 256 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[2] = GF_ADD(z[2], GF_MUL(syn[5], GF_MUL(syn[3], syn[3]))); |
| 257 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[2] = GF_ADD(z[2], GF_MUL(syn[3], GF_MUL(syn[4], syn[4]))); |
| 258 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[2] = GF_ADD(z[2], GF_MUL(syn[2], GF_MUL(syn[5], syn[4]))); |
| 259 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[2] = GF_ADD(z[2], GF_MUL(syn[2], GF_MUL(syn[3], syn[6]))); |
| 260 |
2/4✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | z[2] = GF_MUL(z[2], GF_INV(deter)); |
| 261 | |||
| 262 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[1] = GF_MUL(syn[1], GF_MUL(syn[3], syn[6])); |
| 263 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[1] = GF_ADD(z[1], GF_MUL(syn[1], GF_MUL(syn[5], syn[4]))); |
| 264 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[1] = GF_ADD(z[1], GF_MUL(syn[4], GF_MUL(syn[3], syn[3]))); |
| 265 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[1] = GF_ADD(z[1], GF_MUL(syn[2], GF_MUL(syn[4], syn[4]))); |
| 266 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[1] = GF_ADD(z[1], GF_MUL(syn[2], GF_MUL(syn[3], syn[5]))); |
| 267 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[1] = GF_ADD(z[1], GF_MUL(syn[2], GF_MUL(syn[2], syn[6]))); |
| 268 |
2/4✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | z[1] = GF_MUL(z[1], GF_INV(deter)); |
| 269 | |||
| 270 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[0] = GF_MUL(syn[2], GF_MUL(syn[3], syn[4])); |
| 271 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[0] = GF_ADD(z[0], GF_MUL(syn[3], GF_MUL(syn[2], syn[4]))); |
| 272 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[0] = GF_ADD(z[0], GF_MUL(syn[3], GF_MUL(syn[5], syn[1]))); |
| 273 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[0] = GF_ADD(z[0], GF_MUL(syn[4], GF_MUL(syn[4], syn[1]))); |
| 274 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[0] = GF_ADD(z[0], GF_MUL(syn[3], GF_MUL(syn[3], syn[3]))); |
| 275 |
6/12✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
|
2 | z[0] = GF_ADD(z[0], GF_MUL(syn[2], GF_MUL(syn[2], syn[5]))); |
| 276 |
2/4✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
|
2 | z[0] = GF_MUL(z[0], GF_INV(deter)); |
| 277 | |||
| 278 | 2 | polysolve (z, x, &sols); | |
| 279 |
2/2✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
|
2 | if (sols != 3) |
| 280 | { | ||
| 281 | 1 | *errcode = 4; | |
| 282 | 1 | return; | |
| 283 | } | ||
| 284 | |||
| 285 |
2/4✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
|
1 | w0 = GF_MUL(z[0], syn[1]); |
| 286 |
4/8✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
|
1 | w1 = GF_ADD(GF_MUL(z[0], syn[2]), GF_MUL(z[1], syn[1])); |
| 287 |
6/12✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
|
1 | w2 = GF_ADD(GF_MUL(z[0], syn[3]), GF_ADD(GF_MUL(z[1], syn[2]), GF_MUL(z[2], syn[1]))); |
| 288 | |||
| 289 | 1 | n0 = (ECC_CAPACITY - 1) - v2e[GF_INV(x[0])]; | |
| 290 | 1 | n1 = (ECC_CAPACITY - 1) - v2e[GF_INV(x[1])]; | |
| 291 | 1 | n2 = (ECC_CAPACITY - 1) - v2e[GF_INV(x[2])]; | |
| 292 | |||
| 293 |
6/12✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
|
1 | e0 = GF_ADD(w0, GF_ADD(GF_MUL(w1, x[0]), GF_MUL(w2, GF_EXP(x[0], 2)))); |
| 294 |
4/8✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
|
1 | e0 = GF_MUL(e0, GF_INV(GF_ADD(z[1], GF_EXP(x[0], 2)))); |
| 295 |
6/12✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
|
1 | e1 = GF_ADD(w0, GF_ADD(GF_MUL(w1, x[1]), GF_MUL(w2, GF_EXP(x[1], 2)))); |
| 296 |
4/8✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
|
1 | e1 = GF_MUL(e1, GF_INV(GF_ADD(z[1], GF_EXP(x[1], 2)))); |
| 297 |
6/12✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
|
1 | e2 = GF_ADD(w0, GF_ADD(GF_MUL(w1, x[2]), GF_MUL(w2, GF_EXP(x[2], 2)))); |
| 298 |
4/8✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
|
1 | e2 = GF_MUL(e2, GF_INV(GF_ADD(z[1], GF_EXP(x[2], 2)))); |
| 299 | |||
| 300 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | if (n0 < ECC_PAYLOAD) |
| 301 | 1 | mesg[n0] = GF_ADD(mesg[n0], e0); | |
| 302 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | if (n1 < ECC_PAYLOAD) |
| 303 | 1 | mesg[n1] = GF_ADD(mesg[n1], e1); | |
| 304 |
1/2✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
|
1 | if (n2 < ECC_PAYLOAD) |
| 305 | 1 | mesg[n2] = GF_ADD(mesg[n2], e2); | |
| 306 | 1 | return; | |
| 307 | } | ||
| 308 | } | ||
| 309 | |||
| 310 | /* | ||
| 311 | * Reed - Solomon Encoder. The Encoder uses a shift register algorithm, | ||
| 312 | * as detailed in _Applied Modern Algebra_ by Dornhoff and Hohn (p.446). | ||
| 313 | * Note that the message is reversed in the code array; this was done to | ||
| 314 | * allow for (emergency) recovery of the message directly from the | ||
| 315 | * data stream. | ||
| 316 | */ | ||
| 317 | 3 | extern void ecc_encode(uint8_t m[ECC_PAYLOAD], uint8_t c[ECC_CAPACITY]) | |
| 318 | { | ||
| 319 | 3 | uint8_t r[ECC_OFFSET] = { 0x0 }; | |
| 320 | |||
| 321 |
2/2✓ Branch 0 taken 747 times.
✓ Branch 1 taken 3 times.
|
750 | for (int i = 0; i < ECC_PAYLOAD; i++) |
| 322 | { | ||
| 323 | 747 | c[(ECC_CAPACITY - 1) - i] = m[i]; | |
| 324 | 747 | uint8_t rtmp = GF_ADD(m[i], r[5]); | |
| 325 |
2/2✓ Branch 0 taken 3735 times.
✓ Branch 1 taken 747 times.
|
4482 | for (int j = ECC_OFFSET - 1; j > 0; j--) |
| 326 |
3/4✓ Branch 0 taken 3705 times.
✓ Branch 1 taken 30 times.
✓ Branch 2 taken 3705 times.
✗ Branch 3 not taken.
|
3735 | r[j] = GF_ADD(GF_MUL(rtmp, g[j]), r[j - 1]); |
| 327 |
3/4✓ Branch 0 taken 741 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 741 times.
✗ Branch 3 not taken.
|
747 | r[0] = GF_MUL(rtmp, g[0]); |
| 328 | } | ||
| 329 |
2/2✓ Branch 0 taken 18 times.
✓ Branch 1 taken 3 times.
|
21 | for (int i = 0; i < ECC_OFFSET; i++) |
| 330 | 18 | c[i] = r[i]; | |
| 331 | |||
| 332 |
2/2✓ Branch 0 taken 381 times.
✓ Branch 1 taken 3 times.
|
384 | REVERSE(c, ECC_CAPACITY); |
| 333 | 3 | } | |
| 334 |