in preparation for de-pluginising h223, move golay code support into libwireshark

svn path=/trunk/; revision=22603

3 files changed, 310 insertions, 2 deletions

diff --git a/epan/Makefile.common b/epan/Makefile.common
index 3196517109..c730361425 100644
--- a/epan/Makefile.common
+++ b/epan/Makefile.common
@@ -43,7 +43,7 @@ LIBWIRESHARK_SRC = 		\
 	crc32.c			\
 	crc6.c			\
 	crcdrm.c		\
-	dissector_filters.c		\
+	dissector_filters.c	\
 	emem.c			\
 	epan.c			\
 	ex-opt.c		\
@@ -55,6 +55,7 @@ LIBWIRESHARK_SRC = 		\
 	frequency-utils.c	\
 	funnel.c    		\
 	gcp.c			\
+        golay.c			\
 	guid-utils.c    	\
 	h225-persistentdata.c	\
 	in_cksum.c		\
@@ -154,7 +155,7 @@ LIBWIRESHARK_INCLUDES = 	\
 	crc32.h			\
 	crcdrm.h		\
 	diam_dict.h		\
-	dissector_filters.h		\
+	dissector_filters.h	\
 	dtd.h			\
 	dtd_parse.h 		\
 	emem.h			\
@@ -172,6 +173,7 @@ LIBWIRESHARK_INCLUDES = 	\
 	funnel.h		\
 	garrayfix.h		\
 	gcp.h			\
+	golay.h			\
 	gnuc_format_check.h	\
 	greproto.h		\
 	guid-utils.h		\
diff --git a/epan/golay.c b/epan/golay.c
new file mode 100644
index 0000000000..3de2062269
--- /dev/null
+++ b/epan/golay.c
@@ -0,0 +1,257 @@
+/* $Id$
+ *
+ * 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
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+
+#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);
+}
diff --git a/epan/golay.h b/epan/golay.h
new file mode 100644
index 0000000000..1a6e7994a8
--- /dev/null
+++ b/epan/golay.h
@@ -0,0 +1,49 @@
+/* $Id$
+ *
+ * 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.
+ *
+ * We use guint32s to hold the 24-bit codewords, with the data part in
+ * the bottom 12 bits and the parity in bits 12-23.
+ *
+ *
+ * Wireshark - Network traffic analyzer
+ * By Gerald Combs <gerald@wireshark.org>
+ * Copyright 1998 Gerald Combs
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ */
+#ifndef __GOLAY_H__
+#define __GOLAY_H__
+
+/* encodes a 12-bit word to a 24-bit codeword
+ */
+guint32 golay_encode(guint w);
+
+/* 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);
+
+/* 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);
+
+#endif