summaryrefslogtreecommitdiffstats
path: root/epan/golay.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-10 20:34:10 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-10 20:34:10 +0000
commite4ba6dbc3f1e76890b22773807ea37fe8fa2b1bc (patch)
tree68cb5ef9081156392f1dd62a00c6ccc1451b93df /epan/golay.c
parentInitial commit. (diff)
downloadwireshark-e4ba6dbc3f1e76890b22773807ea37fe8fa2b1bc.tar.xz
wireshark-e4ba6dbc3f1e76890b22773807ea37fe8fa2b1bc.zip
Adding upstream version 4.2.2.upstream/4.2.2
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'epan/golay.c')
-rw-r--r--epan/golay.c257
1 files changed, 257 insertions, 0 deletions
diff --git a/epan/golay.c b/epan/golay.c
new file mode 100644
index 00000000..0751a12f
--- /dev/null
+++ b/epan/golay.c
@@ -0,0 +1,257 @@
+/*
+ * Provides routines for encoding and decoding the extended Golay
+ * (24,12,8) code.
+ *
+ * This implementation will detect up to 4 errors in a codeword (without
+ * being able to correct them); it will correct up to 3 errors.
+ *
+ * Wireshark - Network traffic analyzer
+ * By Gerald Combs <gerald@wireshark.org>
+ * Copyright 1998 Gerald Combs
+ *
+ * SPDX-License-Identifier: GPL-2.0-or-later
+ */
+
+#include <glib.h>
+#include "golay.h"
+
+
+/* Encoding matrix, H
+
+ These entries are formed from the matrix specified in H.223/B.3.2.1.3;
+ it's first transposed so we have:
+
+ [P1 ] [111110010010] [MC1 ]
+ [P2 ] [011111001001] [MC2 ]
+ [P3 ] [110001110110] [MC3 ]
+ [P4 ] [011000111011] [MC4 ]
+ [P5 ] [110010001111] [MPL1]
+ [P6 ] = [100111010101] [MPL2]
+ [P7 ] [101101111000] [MPL3]
+ [P8 ] [010110111100] [MPL4]
+ [P9 ] [001011011110] [MPL5]
+ [P10] [000101101111] [MPL6]
+ [P11] [111100100101] [MPL7]
+ [P12] [101011100011] [MPL8]
+
+ So according to the equation, P1 = MC1+MC2+MC3+MC4+MPL1+MPL4+MPL7
+
+ Looking down the first column, we see that if MC1 is set, we toggle bits
+ 1,3,5,6,7,11,12 of the parity: in binary, 110001110101 = 0xE3A
+
+ Similarly, to calculate the inverse, we read across the top of the table and
+ see that P1 is affected by bits MC1,MC2,MC3,MC4,MPL1,MPL4,MPL7: in binary,
+ 111110010010 = 0x49F.
+
+ I've seen cunning implementations of this which only use one table. That
+ technique doesn't seem to work with these numbers though.
+*/
+
+static const guint golay_encode_matrix[12] = {
+ 0xC75,
+ 0x49F,
+ 0xD4B,
+ 0x6E3,
+ 0x9B3,
+ 0xB66,
+ 0xECC,
+ 0x1ED,
+ 0x3DA,
+ 0x7B4,
+ 0xB1D,
+ 0xE3A,
+};
+
+static const guint golay_decode_matrix[12] = {
+ 0x49F,
+ 0x93E,
+ 0x6E3,
+ 0xDC6,
+ 0xF13,
+ 0xAB9,
+ 0x1ED,
+ 0x3DA,
+ 0x7B4,
+ 0xF68,
+ 0xA4F,
+ 0xC75,
+};
+
+
+
+/* Function to compute the Hamming weight of a 12-bit integer */
+static guint weight12(guint vector)
+{
+ guint w=0;
+ guint i;
+ for( i=0; i<12; i++ )
+ if( vector & 1<<i )
+ w++;
+ return w;
+}
+
+/* returns the golay coding of the given 12-bit word */
+static guint golay_coding(guint w)
+{
+ guint out=0;
+ guint i;
+
+ for( i = 0; i<12; i++ ) {
+ if( w & 1<<i )
+ out ^= golay_encode_matrix[i];
+ }
+ return out;
+}
+
+/* encodes a 12-bit word to a 24-bit codeword */
+guint32 golay_encode(guint w)
+{
+ return ((guint32)w) | ((guint32)golay_coding(w))<<12;
+}
+
+
+
+/* returns the golay coding of the given 12-bit word */
+static guint golay_decoding(guint w)
+{
+ guint out=0;
+ guint i;
+
+ for( i = 0; i<12; i++ ) {
+ if( w & 1<<(i) )
+ out ^= golay_decode_matrix[i];
+ }
+ return out;
+}
+
+
+/* return a mask showing the bits which are in error in a received
+ * 24-bit codeword, or -1 if 4 errors were detected.
+ */
+gint32 golay_errors(guint32 codeword)
+{
+ guint received_data, received_parity;
+ guint syndrome;
+ guint w,i;
+ guint inv_syndrome = 0;
+
+ received_parity = (guint)(codeword>>12);
+ received_data = (guint)codeword & 0xfff;
+
+ /* We use the C notation ^ for XOR to represent addition modulo 2.
+ *
+ * Model the received codeword (r) as the transmitted codeword (u)
+ * plus an error vector (e).
+ *
+ * r = e ^ u
+ *
+ * Then we calculate a syndrome (s):
+ *
+ * s = r * H, where H = [ P ], where I12 is the identity matrix
+ * [ I12 ]
+ *
+ * (In other words, we calculate the parity check for the received
+ * data bits, and add them to the received parity bits)
+ */
+
+ syndrome = received_parity ^ (golay_coding(received_data));
+ w = weight12(syndrome);
+
+ /*
+ * The properties of the golay code are such that the Hamming distance (ie,
+ * the minimum distance between codewords) is 8; that means that one bit of
+ * error in the data bits will cause 7 errors in the parity bits.
+ *
+ * In particular, if we find 3 or fewer errors in the parity bits, either:
+ * - there are no errors in the data bits, or
+ * - there are at least 5 errors in the data bits
+ * we hope for the former (we don't profess to deal with the
+ * latter).
+ */
+ if( w <= 3 ) {
+ return ((gint32) syndrome)<<12;
+ }
+
+ /* the next thing to try is one error in the data bits.
+ * we try each bit in turn and see if an error in that bit would have given
+ * us anything like the parity bits we got. At this point, we tolerate two
+ * errors in the parity bits, but three or more errors would give a total
+ * error weight of 4 or more, which means it's actually uncorrectable or
+ * closer to another codeword. */
+
+ for( i = 0; i<12; i++ ) {
+ guint error = 1<<i;
+ guint coding_error = golay_encode_matrix[i];
+ if( weight12(syndrome^coding_error) <= 2 ) {
+ return (gint32)((((guint32)(syndrome^coding_error))<<12) | (guint32)error) ;
+ }
+ }
+
+ /* okay then, let's see whether the parity bits are error free, and all the
+ * errors are in the data bits. model this as follows:
+ *
+ * [r | pr] = [u | pu] + [e | 0]
+ *
+ * pr = pu
+ * pu = H * u => u = H' * pu = H' * pr , where H' is inverse of H
+ *
+ * we already have s = H*r + pr, so pr = s - H*r = s ^ H*r
+ * e = u ^ r
+ * = (H' * ( s ^ H*r )) ^ r
+ * = H'*s ^ r ^ r
+ * = H'*s
+ *
+ * Once again, we accept up to three error bits...
+ */
+
+ inv_syndrome = golay_decoding(syndrome);
+ w = weight12(inv_syndrome);
+ if( w <=3 ) {
+ return (gint32)inv_syndrome;
+ }
+
+ /* Final shot: try with 2 errors in the data bits, and 1 in the parity
+ * bits; as before we try each of the bits in the parity in turn */
+ for( i = 0; i<12; i++ ) {
+ guint error = 1<<i;
+ guint coding_error = golay_decode_matrix[i];
+ if( weight12(inv_syndrome^coding_error) <= 2 ) {
+ guint32 error_word = ((guint32)(inv_syndrome^coding_error)) | ((guint32)error)<<12;
+ return (gint32)error_word;
+ }
+ }
+
+ /* uncorrectable error */
+ return -1;
+}
+
+
+
+/* decode a received codeword. Up to 3 errors are corrected for; 4
+ errors are detected as uncorrectable (return -1); 5 or more errors
+ cause an incorrect correction.
+*/
+gint golay_decode(guint32 w)
+{
+ guint data = (guint)w & 0xfff;
+ gint32 errors = golay_errors(w);
+ guint data_errors;
+
+ if( errors == -1 )
+ return -1;
+ data_errors = (guint)errors & 0xfff;
+ return (gint)(data ^ data_errors);
+}
+
+/*
+ * Editor modelines
+ *
+ * Local Variables:
+ * c-basic-offset: 4
+ * tab-width: 8
+ * indent-tabs-mode: nil
+ * End:
+ *
+ * ex: set shiftwidth=4 tabstop=8 expandtab:
+ * :indentSize=4:tabSize=8:noTabs=true:
+ */