OSPF: Redesign LSA checksumming

New LSA checksumming code separates generic Fletcher-16 and OSPF-specific
code and avoids back and forth endianity conversions, making it much more
readable and also several times faster.

1 files changed, 196 insertions, 0 deletions

diff --git a/lib/fletcher16.h b/lib/fletcher16.h
new file mode 100644
index 00000000..0b245a71
--- /dev/null
+++ b/lib/fletcher16.h
@@ -0,0 +1,196 @@
+/*
+ *	BIRD Library -- Fletcher-16 checksum
+ *
+ *	(c) 2015 Ondrej Zajicek <santiago@crfreenet.org>
+ *	(c) 2015 CZ.NIC z.s.p.o.
+ *
+ *	Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+/**
+ * DOC: Fletcher-16 checksum
+ *
+ * Fletcher-16 checksum is a position-dependent checksum algorithm used for
+ * error-detection e.g. in OSPF LSAs.
+ *
+ * To generate Fletcher-16 checksum, zero the checksum field in data, initialize
+ * the context by fletcher16_init(), process the data by fletcher16_update(),
+ * compute the checksum value by fletcher16_final() and store it to the checksum
+ * field in data by put_u16() (or other means involving htons() conversion).
+ *
+ * To verify Fletcher-16 checksum, initialize the context by fletcher16_init(),
+ * process the data by fletcher16_update(), compute a passing checksum by
+ * fletcher16_compute() and check if it is zero.
+ */
+
+#ifndef _BIRD_FLETCHER16_H_
+#define _BIRD_FLETCHER16_H_
+
+#include "nest/bird.h"
+
+
+struct fletcher16_context
+{
+  int c0, c1;
+};
+
+
+/**
+ * fletcher16_init - initialize Fletcher-16 context
+ * @ctx: the context
+ */
+static inline void
+fletcher16_init(struct fletcher16_context *ctx)
+{
+  ctx->c0 = ctx->c1 = 0;
+}
+
+/**
+ * fletcher16_update - process data to Fletcher-16 context
+ * @ctx: the context
+ * @buf: data buffer
+ * @len: data length
+ *
+ * fletcher16_update() reads data from the buffer @buf and updates passing sums
+ * in the context @ctx. It may be used multiple times for multiple blocks of
+ * checksummed data.
+ */
+static inline void
+fletcher16_update(struct fletcher16_context *ctx, const u8* buf, int len)
+{
+  /*
+   * The Fletcher-16 sum is essentially a sequence of
+   * ctx->c1 += ctx->c0 += *buf++, modulo 255.
+   *
+   * In the inner loop, we eliminate modulo operation and we do some loop
+   * unrolling. MODX is the maximal number of steps that can be done without
+   * modulo before overflow, see RFC 1008 for details. We use a bit smaller
+   * value to cover for initial steps due to loop unrolling.
+   */
+
+#define MODX 4096
+
+  int blen, i;
+
+  blen = len % 4;
+  len -= blen;
+
+  for (i = 0; i < blen; i++)
+    ctx->c1 += ctx->c0 += *buf++;
+
+  do {
+    blen = MIN(len, MODX);
+    len -= blen;
+
+    for (i = 0; i < blen; i += 4)
+    {
+      ctx->c1 += ctx->c0 += *buf++;
+      ctx->c1 += ctx->c0 += *buf++;
+      ctx->c1 += ctx->c0 += *buf++;
+      ctx->c1 += ctx->c0 += *buf++;
+    }
+
+    ctx->c0 %= 255;
+    ctx->c1 %= 255;
+
+  } while (len);
+}
+
+
+/**
+ * fletcher16_update_n32 - process data to Fletcher-16 context, with endianity adjustment
+ * @ctx: the context
+ * @buf: data buffer
+ * @len: data length
+ *
+ * fletcher16_update_n32() works like fletcher16_update(), except it applies
+ * 32-bit host/network endianity swap to the data before they are processed.
+ * I.e., it assumes that the data is a sequence of u32 that must be converted by
+ * ntohl() or htonl() before processing. The @buf need not to be aligned, but
+ * its length (@len) must be multiple of 4. Note that on big endian systems the
+ * host endianity is the same as the network endianity, therefore there is no
+ * endianity swap.
+ */
+static inline void
+fletcher16_update_n32(struct fletcher16_context *ctx, const u8* buf, int len)
+{
+  /* See fletcher16_update() for details */
+
+  int blen, i;
+
+  do {
+    blen = MIN(len, MODX);
+    len -= blen;
+
+    for (i = 0; i < blen; i += 4)
+    {
+#ifdef CPU_BIG_ENDIAN
+      ctx->c1 += ctx->c0 += *buf++;
+      ctx->c1 += ctx->c0 += *buf++;
+      ctx->c1 += ctx->c0 += *buf++;
+      ctx->c1 += ctx->c0 += *buf++;
+#else
+      ctx->c1 += ctx->c0 += buf[3];
+      ctx->c1 += ctx->c0 += buf[2];
+      ctx->c1 += ctx->c0 += buf[1];
+      ctx->c1 += ctx->c0 += buf[0];
+      buf += 4;
+#endif
+    }
+
+    ctx->c0 %= 255;
+    ctx->c1 %= 255;
+
+  } while (len);
+}
+
+/**
+ * fletcher16_final - compute final Fletcher-16 checksum value
+ * @ctx: the context
+ * @len: total data length
+ * @pos: offset in data where the checksum will be stored
+ *
+ * fletcher16_final() computes the final checksum value and returns it.
+ * The caller is responsible for storing it in the appropriate position.
+ * The checksum value depends on @len and @pos, but only their difference
+ * (i.e. the offset from the end) is significant.
+ *
+ * The checksum value is represented as u16, although it is defined as two
+ * consecutive bytes. We treat them as one u16 in big endian / network order.
+ * I.e., the returned value is in the form that would be returned by get_u16()
+ * from the checksum field in the data buffer, therefore the caller should use
+ * put_u16() or an explicit host-to-network conversion when storing it to the
+ * checksum field in the data buffer.
+ *
+ * Note that the returned checksum value is always nonzero.
+ */
+static inline u16
+fletcher16_final(struct fletcher16_context *ctx, int len, int pos)
+{
+  int x = ((len - pos - 1) * ctx->c0 - ctx->c1) % 255;
+  if (x <= 0)
+    x += 255;
+
+  int y = 510 - ctx->c0 - x;
+  if (y > 255)
+    y -= 255;
+
+  return (x << 8) | y;
+}
+
+
+/**
+ * fletcher16_compute - compute Fletcher-16 sum for verification
+ * @ctx: the context
+ *
+ * fletcher16_compute() returns a passing Fletcher-16 sum for processed data.
+ * If the data contains the proper Fletcher-16 checksum value, the returned
+ * value is zero.
+ */
+static inline u16
+fletcher16_compute(struct fletcher16_context *ctx)
+{
+  return (ctx->c0 << 8) | ctx->c1;
+}
+
+#endif