chiark / gitweb /
magic.h: Present message labels as an encoding of major and minor numbers.
authorMark Wooding <mdw@distorted.org.uk>
Sun, 30 Apr 2017 23:03:08 +0000 (00:03 +0100)
committerMark Wooding <mdw@distorted.org.uk>
Wed, 25 Sep 2019 12:46:44 +0000 (13:46 +0100)
The encoding is strange for historical reasons, but represents all pairs
of 16-bit major and minor codes.

I've exhaustively verified that the encoding is invertable, and that it
reproduces the old manually assigned labels; this program is
`msgcode-test.c', which I've added to the standard test run, though it's
rather slow to run.

Signed-off-by: Mark Wooding <mdw@distorted.org.uk>
Makefile.in
magic.h
msgcode-test.c [new file with mode: 0644]
secnet-wireshark.lua

index 7de2918..6bc02ef 100644 (file)
@@ -144,7 +144,8 @@ secnet: $(wildcard .git/packed-refs)
 endif
 
 check: eax-aes-test.confirm eax-serpent-test.confirm \
-       eax-serpentbe-test.confirm check-ipaddrset
+       eax-serpentbe-test.confirm check-ipaddrset \
+       msgcode-test.confirm
 
 version.c: Makefile
        echo "#include \"secnet.h\"" >$@.new
@@ -164,6 +165,13 @@ eax-%-test.confirm: eax-%-test eax-%-test.vectors
        ./$< <$(srcdir)/eax-$*-test.vectors >$@.new
        mv -f $@.new $@
 
+msgcode-test: msgcode-test.o
+       $(CC) $(LDFLAGS) $(ALL_CFLAGS) -o $@ $^
+
+msgcode-test.confirm: msgcode-test
+       ./msgcode-test
+       touch $@
+
 check-ipaddrset: ipaddrset-test.py ipaddrset.py ipaddrset-test.expected
        $(srcdir)/ipaddrset-test.py >ipaddrset-test.new
        diff -u $(srcdir)/ipaddrset-test.expected ipaddrset-test.new
@@ -198,6 +206,7 @@ install-force:
 clean:
        $(RM) -f *.o *.yy.[ch] *.tab.[ch] $(TARGETS) core version.c
        $(RM) -f *.d *.pyc *~ eax-*-test.confirm eax-*-test
+       $(RM) -f msgcode-test.confirm msgcode-test
 
 realclean:     clean
        $(RM) -f *~ Makefile config.h  *.d \
diff --git a/magic.h b/magic.h
index 38982de..fa171fd 100644 (file)
--- a/magic.h
+++ b/magic.h
 #ifndef magic_h
 #define magic_h
 
-#define LABEL_NAK     0x00000000
-#define LABEL_MSG0    0x00020200
-#define LABEL_MSG1    0x01010101
-#define LABEL_MSG2    0x02020202
-#define LABEL_MSG3    0x03030303
-#define LABEL_MSG3BIS 0x13030313
-#define LABEL_MSG4    0x04040404
-#define LABEL_MSG5    0x05050505
-#define LABEL_MSG6    0x06060606
-#define LABEL_MSG7    0x07070707
-#define LABEL_MSG8    0x08080808
-#define LABEL_MSG9    0x09090909
-#define LABEL_PROD    0x0a0a0a0a
+/* Encode a pair of 16 bit major and minor codes as a single 32-bit label.
+ * The encoding is strange for historical reasons.  Suppose that the nibbles
+ * of the major number are (from high to low) a, b, c, d, and the minor
+ * number has nibbles w, x, y, z.  (Here, a, b, c, d are variables, not hex
+ * digits.)  We scramble them to form a message label as follows.
+ *
+ *     0 d 0 d 0 d 0 d
+ *     0 0 0 a b c 0 0
+ *     z 0 0 0 0 0 z 0
+ *     w x y 0 0 0 0 0
+ *     ---------------
+ *     f g h i j k l m
+ *
+ * and calculate the nibbles f, g, ..., m of the message label (higher
+ * significance on the left) by XORing the columns.  It can be shown that
+ * this is invertible using linear algebra in GF(16), but but it's easier to
+ * notice that d = m, z = l, c = k XOR d, b = j, a = i XOR d, y = h,
+ * x = g XOR d, and w = f XOR z.
+ *
+ * Encoding in the forward direction, from a major/minor pair to a label, is
+ * (almost?) always done on constants, so its performance is fairly
+ * unimportant.  There is a compatibility constraint on the patterns produced
+ * with a = b = c = w = x = y = 0.  Subject to that, I wanted to find an
+ * invertible GF(16)-linear transformation which would let me recover the
+ * major and minor numbers with relatively little calculation.
+ */
+
+#define MSGCODE(major, minor)                                          \
+       ((((uint32_t)(major)&0x0000000fu) <<  0) ^                      \
+        (((uint32_t)(major)&0x0000000fu) <<  8) ^                      \
+        (((uint32_t)(major)&0x0000000fu) << 16) ^                      \
+        (((uint32_t)(major)&0x0000000fu) << 24) ^                      \
+        (((uint32_t)(major)&0x0000fff0u) <<  4) ^                      \
+        (((uint32_t)(minor)&0x0000000fu) <<  4) ^                      \
+        (((uint32_t)(minor)&0x0000000fu) << 28) ^                      \
+        (((uint32_t)(minor)&0x0000fff0u) << 16))
+
+/* Extract major and minor codes from a 32-bit message label. */
+#define MSGMAJOR(label)                                                        \
+       ((((uint32_t)(label)&0x0000000fu) <<  0) ^                      \
+        (((uint32_t)(label)&0x0000000fu) <<  4) ^                      \
+        (((uint32_t)(label)&0x0000000fu) << 12) ^                      \
+        (((uint32_t)(label)&0x000fff00u) >>  4))
+#define MSGMINOR(label)                                                        \
+       ((((uint32_t)(label)&0x000000ffu) <<  8) ^                      \
+        (((uint32_t)(label)&0x000000f0u) >>  4) ^                      \
+        (((uint32_t)(label)&0xfff00000u) >> 16))
+
+#define LABEL_NAK      MSGCODE(     0, 0)
+#define LABEL_MSG0     MSGCODE(0x2020, 0) /* ! */
+#define LABEL_MSG1     MSGCODE(     1, 0)
+#define LABEL_MSG2     MSGCODE(     2, 0)
+#define LABEL_MSG3     MSGCODE(     3, 0)
+#define LABEL_MSG3BIS  MSGCODE(     3, 1)
+#define LABEL_MSG4     MSGCODE(     4, 0)
+#define LABEL_MSG5     MSGCODE(     5, 0)
+#define LABEL_MSG6     MSGCODE(     6, 0)
+#define LABEL_MSG7     MSGCODE(     7, 0)
+#define LABEL_MSG8     MSGCODE(     8, 0)
+#define LABEL_MSG9     MSGCODE(     9, 0)
+#define LABEL_PROD     MSGCODE(    10, 0)
 
 /*
  * The capability mask is a set of bits, one for each optional feature
diff --git a/msgcode-test.c b/msgcode-test.c
new file mode 100644 (file)
index 0000000..401bf6f
--- /dev/null
@@ -0,0 +1,93 @@
+/*
+ * msgcode-test.c: check that the new message encoding is correct
+ */
+/*
+ * This file is Free Software.  It was originally written for secnet.
+ *
+ * Copyright 2017 Mark Wooding
+ *
+ * You may redistribute secnet as a whole and/or modify it under the
+ * terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 3, or (at your option) any
+ * later version.
+ *
+ * You may redistribute this file and/or modify it under the terms of
+ * the GNU General Public License as published by the Free Software
+ * Foundation; either version 2, or (at your option) any later
+ * version.
+ *
+ * This software 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 software; if not, see
+ * https://www.gnu.org/licenses/gpl.html.
+ */
+
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "magic.h"
+
+#define OLD_LABEL_NAK     0x00000000
+#define OLD_LABEL_MSG0    0x00020200
+#define OLD_LABEL_MSG1    0x01010101
+#define OLD_LABEL_MSG2    0x02020202
+#define OLD_LABEL_MSG3    0x03030303
+#define OLD_LABEL_MSG3BIS 0x13030313
+#define OLD_LABEL_MSG4    0x04040404
+#define OLD_LABEL_MSG5    0x05050505
+#define OLD_LABEL_MSG6    0x06060606
+#define OLD_LABEL_MSG7    0x07070707
+#define OLD_LABEL_MSG8    0x08080808
+#define OLD_LABEL_MSG9    0x09090909
+#define OLD_LABEL_PROD    0x0a0a0a0a
+
+static void check_labels(const char *what, uint32_t new, uint32_t old)
+{
+    if (old != new) {
+       printf("mismatch for %s: %08"PRIx32" (new) /= %08"PRIx32" (old)\n",
+              what, new, old);
+       exit(2);
+    }
+}
+
+int main(void)
+{
+    unsigned i, j;
+    uint32_t m, r, s;
+
+#define CHECK(label) check_labels(#label, LABEL_##label, OLD_LABEL_##label)
+    CHECK(NAK);
+    CHECK(MSG0);
+    CHECK(MSG1);
+    CHECK(MSG2);
+    CHECK(MSG3);
+    CHECK(MSG3BIS);
+    CHECK(MSG4);
+    CHECK(MSG5);
+    CHECK(MSG6);
+    CHECK(MSG7);
+    CHECK(MSG8);
+    CHECK(MSG9);
+    CHECK(PROD);
+#undef CHECK
+    for (i = 0; i < 65536; i++) {
+       for (j = 0; j < 65536; j++) {
+           m = MSGCODE(i, j);
+           r = MSGMAJOR(m); s = MSGMINOR(m);
+           if (r != i || s != j) {
+               printf("roundtrip fail: %04x %04x -> %08"PRIx32" "
+                      "-> %08"PRIx32" %08"PRIx32"\n",
+                      i, j, m, r, s);
+               exit(2);
+           }
+       }
+    }
+
+    return (0);
+}
index c9b25d2..62739bc 100644 (file)
@@ -262,20 +262,53 @@ end
 local PF = { } -- The table of protocol fields, filled in later.
 local F = { } -- A table of field values, also filled in later.
 
+local function msgcode(major, minor)
+  -- Construct a Secnet message number according to the complicated rules.
+
+  local majlo = bit.band(major, 0x000f)
+  local majhi = bit.band(major, 0xfff0)
+  local minlo = bit.band(minor, 0x000f)
+  local minhi = bit.band(minor, 0xfff0)
+  return bit.bxor(bit.lshift(majlo,  0),
+                 bit.lshift(majlo,  8),
+                 bit.lshift(majlo, 16),
+                 bit.lshift(majlo, 24),
+                 bit.lshift(majhi,  4),
+                 bit.lshift(minlo,  4),
+                 bit.lshift(minlo, 28),
+                 bit.lshift(minhi, 16))
+end
+
+local function msgmajor(label)
+  -- Return the major message number from a LABEL.
+
+  local lo = bit.band(label, 0x000f)
+  local hi = bit.band(bit.rshift(label, 4), 0xfff0)
+  return bit.bxor(lo, bit.lshift(lo, 4), bit.lshift(lo, 12), hi)
+end
+
+local function msgminor(label)
+  -- Return the minor message number from a LABEL.
+
+  return bit.bxor(bit.lshift(bit.band(label, 0x00ff), 8),
+                 bit.band(bit.rshift(label, 4), 0x000f),
+                 bit.band(bit.rshift(label, 16), 0xfff0))
+end
+
 -- Main message-number table.
-local M = { NAK                = 0x00000000
-           MSG0        = 0x00020200
-           MSG1        = 0x01010101
-           MSG2        = 0x02020202
-           MSG3        = 0x03030303
-           MSG3BIS     = 0x13030313
-           MSG4        = 0x04040404
-           MSG5        = 0x05050505
-           MSG6        = 0x06060606
-           MSG7        = 0x07070707
-           MSG8        = 0x08080808
-           MSG9        = 0x09090909
-           PROD        = 0x0a0a0a0a }
+local M = { NAK                = msgcode(     0, 0),
+           MSG0        = msgcode(0x2020, 0), -- !
+           MSG1        = msgcode(     1, 0),
+           MSG2        = msgcode(     2, 0),
+           MSG3        = msgcode(     3, 0),
+           MSG3BIS     = msgcode(     3, 1),
+           MSG4        = msgcode(     4, 0),
+           MSG5        = msgcode(     5, 0),
+           MSG6        = msgcode(     6, 0),
+           MSG7        = msgcode(     7, 0),
+           MSG8        = msgcode(     8, 0),
+           MSG9        = msgcode(     9, 0),
+           PROD        = msgcode(    10, 0)}
 
 -- The `dissect_*' functions follow a common protocol.  They parse a thing
 -- from a packet buffer BUF, of size SZ, starting from POS, and store