Implemented umac.

1 files changed, 140 insertions, 0 deletions

diff --git a/umac-poly128.c b/umac-poly128.c
new file mode 100644
index 00000000..0c0f0a73
--- /dev/null
+++ b/umac-poly128.c
@@ -0,0 +1,140 @@
+/* umac-poly128.c
+ */
+
+/* nettle, low-level cryptographics library
+ *
+ * Copyright (C) 2013 Niels Möller
+ *
+ * The nettle library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The nettle library 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 Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the nettle library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ * MA 02111-1301, USA.
+ */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "umac.h"
+
+#define HI(x) (x >> 32)
+#define LO(x) (x & 0xffffffffUL)
+
+static void
+poly128_mul (const uint32_t *k, uint64_t *y)
+{
+  uint64_t y0,y1,y2,y3,p0,p1,p2,p3,m0,m1,m2;
+  y0 = LO (y[1]);
+  y1 = HI (y[1]);
+  y2 = LO (y[0]);
+  y3 = HI (y[0]);
+
+  p0 = y0 * k[3];
+  m0 = y0 * k[2] + y1 * k[3];
+  p1 = y0 * k[1] + y1 * k[2] + y2 * k[3];
+  m1 = y0 * k[0] + y1 * k[1] + y2 * k[2] + y3 * k[3];
+  p2 = y1 * k[0] + y2 * k[1] + y3 * k[2];
+  m2 = y2 * k[0] + y3 * k[1];
+  p3 = y3 * k[0];
+
+  /* Collaps to 4 64-bit words,
+     +---+---+---+---+
+     | p3| p2| p1| p0|
+     +-+-+-+-+-+-+-+-+
+    +  | m2| m1| m0|
+    -+-+-+-+-+-+-+-+-+
+  */
+  /* But it's convenient to reduce (p3,p2,p1,p0) and (m2,m1,m0) mod p first.*/
+  m1 += UMAC_P128_OFFSET * HI(p3);
+  p1 += UMAC_P128_OFFSET * (LO(p3) + HI(m2));
+  m0 += UMAC_P128_OFFSET * (HI(p2) + LO(m2));
+  p0 += UMAC_P128_OFFSET * (LO(p2) + HI(m1));
+
+  /* Left to add
+     +---+---+
+     | p1| p0|
+     +-+-+-+-+
+     m1| m0|
+     +-+---+
+  */
+  /* First add high parts, with no possibilities for carries */
+  p1 += m0 >> 32;
+
+  m0 <<= 32;
+  m1 <<= 32;
+
+  /* Remains:
+     +---+---+
+     | p1| p0|
+     +-+-+---+
+    +| m1| m0|
+    -+---+---+
+  */
+  p0 += m0;
+  p1 += (p0 < m0);
+  p1 += m1;
+  if (p1 < m1)
+    {
+      p0 += UMAC_P128_OFFSET;
+      p1 += (p0 < UMAC_P128_OFFSET);
+    }
+
+  y[0] = p1;
+  y[1] = p0;
+}
+
+void
+_umac_poly128 (const uint32_t *k, uint64_t *y, uint64_t mh, uint64_t ml)
+{
+  uint64_t yh, yl, cy;
+
+  if ( (mh >> 32) == 0xffffffff)
+    {
+      poly128_mul (k, y);
+      if (y[1] > 0)
+	y[1]--;
+      else if (y[0] > 0)
+	{
+	  y[0]--;
+	  y[1] = UMAC_P128_HI;
+	}
+      else
+	{
+	  y[0] = UMAC_P128_HI;
+	  y[1] = UMAC_P128_LO-1;
+	}
+
+      mh -= (ml < UMAC_P128_OFFSET);
+      ml -= UMAC_P128_OFFSET;
+    }
+  assert (mh < UMAC_P128_HI || ml < UMAC_P128_LO);
+
+  poly128_mul (k, y);
+  yl = y[1] + ml;
+  cy = (yl < ml);
+  yh = y[0] + cy;
+  cy = (yh < cy);
+  yh += mh;
+  cy += (yh < mh);
+  assert (cy <= 1);
+  if (cy)
+    {
+      yl += UMAC_P128_OFFSET;
+      yh += yl < UMAC_P128_OFFSET;
+    }
+
+  y[0] = yh;
+  y[1] = yl;
+}