castbox
/
upm_guru_kcp
25
0
Fork 0
Code Issues Pull Requests Packages Projects Releases Wiki Activity
upm_guru_kcp/Runtime/csharp-kcp/reedsolomon_csharp/Galois.cs

337 lines
11 KiB
C#
Raw Permalink Blame History

using System;
using System.Collections.Generic;
namespace fec
{
public sealed class Galois
{
/**
* The number of elements in the field.
*/
public const int FIELD_SIZE = 256;
/**
* The polynomial used to generate the logarithm table.
*
* There are a number of polynomials that work to generate
* a Galois field of 256 elements. The choice is arbitrary,
* and we just use the first one.
*
* The possibilities are: 29, 43, 45, 77, 95, 99, 101, 105,
* 113, 135, 141, 169, 195, 207, 231, and 245.
*/
public const int GENERATING_POLYNOMIAL = 29;
public static readonly short[] LOG_TABLE = new short[]
{
-1, 0, 1, 25, 2, 50, 26, 198,
3, 223, 51, 238, 27, 104, 199, 75,
4, 100, 224, 14, 52, 141, 239, 129,
28, 193, 105, 248, 200, 8, 76, 113,
5, 138, 101, 47, 225, 36, 15, 33,
53, 147, 142, 218, 240, 18, 130, 69,
29, 181, 194, 125, 106, 39, 249, 185,
201, 154, 9, 120, 77, 228, 114, 166,
6, 191, 139, 98, 102, 221, 48, 253,
226, 152, 37, 179, 16, 145, 34, 136,
54, 208, 148, 206, 143, 150, 219, 189,
241, 210, 19, 92, 131, 56, 70, 64,
30, 66, 182, 163, 195, 72, 126, 110,
107, 58, 40, 84, 250, 133, 186, 61,
202, 94, 155, 159, 10, 21, 121, 43,
78, 212, 229, 172, 115, 243, 167, 87,
7, 112, 192, 247, 140, 128, 99, 13,
103, 74, 222, 237, 49, 197, 254, 24,
227, 165, 153, 119, 38, 184, 180, 124,
17, 68, 146, 217, 35, 32, 137, 46,
55, 63, 209, 91, 149, 188, 207, 205,
144, 135, 151, 178, 220, 252, 190, 97,
242, 86, 211, 171, 20, 42, 93, 158,
132, 60, 57, 83, 71, 109, 65, 162,
31, 45, 67, 216, 183, 123, 164, 118,
196, 23, 73, 236, 127, 12, 111, 246,
108, 161, 59, 82, 41, 157, 85, 170,
251, 96, 134, 177, 187, 204, 62, 90,
203, 89, 95, 176, 156, 169, 160, 81,
11, 245, 22, 235, 122, 117, 44, 215,
79, 174, 213, 233, 230, 231, 173, 232,
116, 214, 244, 234, 168, 80, 88, 175
};
public static readonly sbyte[] EXP_TABLE = new sbyte[]
{
1, 2, 4, 8, 16, 32, 64, -128,
29, 58, 116, -24, -51, -121, 19, 38,
76, -104, 45, 90, -76, 117, -22, -55,
-113, 3, 6, 12, 24, 48, 96, -64,
-99, 39, 78, -100, 37, 74, -108, 53,
106, -44, -75, 119, -18, -63, -97, 35,
70, -116, 5, 10, 20, 40, 80, -96,
93, -70, 105, -46, -71, 111, -34, -95,
95, -66, 97, -62, -103, 47, 94, -68,
101, -54, -119, 15, 30, 60, 120, -16,
-3, -25, -45, -69, 107, -42, -79, 127,
-2, -31, -33, -93, 91, -74, 113, -30,
-39, -81, 67, -122, 17, 34, 68, -120,
13, 26, 52, 104, -48, -67, 103, -50,
-127, 31, 62, 124, -8, -19, -57, -109,
59, 118, -20, -59, -105, 51, 102, -52,
-123, 23, 46, 92, -72, 109, -38, -87,
79, -98, 33, 66, -124, 21, 42, 84,
-88, 77, -102, 41, 82, -92, 85, -86,
73, -110, 57, 114, -28, -43, -73, 115,
-26, -47, -65, 99, -58, -111, 63, 126,
-4, -27, -41, -77, 123, -10, -15, -1,
-29, -37, -85, 75, -106, 49, 98, -60,
-107, 55, 110, -36, -91, 87, -82, 65,
-126, 25, 50, 100, -56, -115, 7, 14,
28, 56, 112, -32, -35, -89, 83, -90,
81, -94, 89, -78, 121, -14, -7, -17,
-61, -101, 43, 86, -84, 69, -118, 9,
18, 36, 72, -112, 61, 122, -12, -11,
-9, -13, -5, -21, -53, -117, 11, 22,
44, 88, -80, 125, -6, -23, -49, -125,
27, 54, 108, -40, -83, 71, -114,
// Repeat the table a second time, so multiply()
// does not have to check bounds.
1, 2, 4, 8, 16, 32, 64, -128,
29, 58, 116, -24, -51, -121, 19, 38,
76, -104, 45, 90, -76, 117, -22, -55,
-113, 3, 6, 12, 24, 48, 96, -64,
-99, 39, 78, -100, 37, 74, -108, 53,
106, -44, -75, 119, -18, -63, -97, 35,
70, -116, 5, 10, 20, 40, 80, -96,
93, -70, 105, -46, -71, 111, -34, -95,
95, -66, 97, -62, -103, 47, 94, -68,
101, -54, -119, 15, 30, 60, 120, -16,
-3, -25, -45, -69, 107, -42, -79, 127,
-2, -31, -33, -93, 91, -74, 113, -30,
-39, -81, 67, -122, 17, 34, 68, -120,
13, 26, 52, 104, -48, -67, 103, -50,
-127, 31, 62, 124, -8, -19, -57, -109,
59, 118, -20, -59, -105, 51, 102, -52,
-123, 23, 46, 92, -72, 109, -38, -87,
79, -98, 33, 66, -124, 21, 42, 84,
-88, 77, -102, 41, 82, -92, 85, -86,
73, -110, 57, 114, -28, -43, -73, 115,
-26, -47, -65, 99, -58, -111, 63, 126,
-4, -27, -41, -77, 123, -10, -15, -1,
-29, -37, -85, 75, -106, 49, 98, -60,
-107, 55, 110, -36, -91, 87, -82, 65,
-126, 25, 50, 100, -56, -115, 7, 14,
28, 56, 112, -32, -35, -89, 83, -90,
81, -94, 89, -78, 121, -14, -7, -17,
-61, -101, 43, 86, -84, 69, -118, 9,
18, 36, 72, -112, 61, 122, -12, -11,
-9, -13, -5, -21, -53, -117, 11, 22,
44, 88, -80, 125, -6, -23, -49, -125,
27, 54, 108, -40, -83, 71, -114
};
public static readonly byte[] EXP_TABLE_BYTE = generateExpTable();
/**
* A multiplication table for the Galois field.
*
* Using this table is an alternative to using the multiply() method,
* which uses log/exp table lookups.
*/
public static readonly byte[][] MULTIPLICATION_TABLE= generateMultiplicationTable();
/**
* Adds two elements of the field. If you're in an inner loop,
* you should inline this function: it's just XOR.
*/
public static sbyte add(sbyte a, sbyte b)
{
return (sbyte) (a ^ b);
}
/**
* Inverse of addition. If you're in an inner loop,
* you should inline this function: it's just XOR.
*/
public static byte subtract(sbyte a, sbyte b)
{
return (byte) (a ^ b);
}
/**
* Multiplies two elements of the field.
*/
public static byte multiply(byte a, byte b)
{
if (a == 0 || b == 0)
{
return 0;
}
int logA = LOG_TABLE[a];
int logB = LOG_TABLE[b];
int logResult = logA + logB;
return EXP_TABLE_BYTE[logResult];
}
/**
* Inverse of multiplication.
*/
public static byte divide(byte a, byte b)
{
if (a == 0)
{
return 0;
}
if (b == 0)
{
throw new Exception("Argument 'divisor' is 0");
}
int logA = LOG_TABLE[a];
int logB = LOG_TABLE[b];
int logResult = logA - logB;
if (logResult < 0)
{
logResult += 255;
}
return EXP_TABLE_BYTE[logResult];
}
/**
* Computes a**n.
*
* The result will be the same as multiplying a times itself n times.
*
* @param a A member of the field.
* @param n A plain-old integer.
* @return The result of multiplying a by itself n times.
*/
public static byte exp(byte a, int n)
{
if (n == 0)
{
return 1;
}
if (a == 0)
{
return 0;
}
int logA = LOG_TABLE[a];
int logResult = logA * n;
while (255 <= logResult)
{
logResult -= 255;
}
return EXP_TABLE_BYTE[logResult];
}
/**
* Generates a logarithm table given a starting polynomial.
*/
public static short[] generateLogTable(int polynomial)
{
short[] result = new short[FIELD_SIZE];
for (int i = 0; i < FIELD_SIZE; i++)
{
result[i] = -1; // -1 means "not set"
}
int b = 1;
for (int log = 0; log < FIELD_SIZE - 1; log++)
{
if (result[b] != -1)
{
throw new Exception("BUG: duplicate logarithm (bad polynomial?)");
}
result[b] = (short) log;
b = (b << 1);
if (FIELD_SIZE <= b)
{
b = ((b - FIELD_SIZE) ^ polynomial);
}
}
return result;
}
/**
* Generates the inverse log table.
*/
public static byte[] generateExpTable(short[] logTable)
{
byte[] result = new byte [FIELD_SIZE * 2 - 2];
for (int i = 1; i < FIELD_SIZE; i++)
{
int log = logTable[i];
result[log] = (byte) i;
result[log + FIELD_SIZE - 1] = (byte) i;
}
return result;
}
public static byte[] generateExpTable()
{
byte[] result = new byte[EXP_TABLE.Length];
for (var i = 0; i < EXP_TABLE.Length; i++)
{
result[i] = (byte) EXP_TABLE[i];
}
return result;
}
public static byte[][] generateMultiplicationTable()
{
byte[][] result = new byte [256][];
for (int a = 0; a < FIELD_SIZE; a++)
{
result[a] = new byte[256];
for (int b = 0; b < FIELD_SIZE; b++)
{
result[a][b] = multiply((byte) a, (byte) b);
}
}
return result;
}
/**
* Returns a list of all polynomials that can be used to generate
* the field.
*
* This is never used in the code; it's just here for completeness.
*/
public static int[] allPossiblePolynomials()
{
List<int> result = new List<int>();
for (int i = 0; i < FIELD_SIZE; i++)
{
try
{
generateLogTable(i);
result.Add(i);
}
catch (Exception e)
{
// this one didn't work
}
}
return result.ToArray();
}
}
}
Reference in New Issue View Git Blame Copy Permalink