umac-poly128.c

   1 /* umac-poly128.c
   2  */
   3
   4 /* nettle, low-level cryptographics library
   5  *
   6  * Copyright (C) 2013 Niels Möller
   7  *
   8  * The nettle library is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU Lesser General Public License as published by
  10  * the Free Software Foundation; either version 2.1 of the License, or (at your
  11  * option) any later version.
  12  *
  13  * The nettle library is distributed in the hope that it will be useful, but
  14  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  15  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  16  * License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  20  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  21  * MA 02111-1301, USA.
  22  */
  23
  24 #if HAVE_CONFIG_H
  25 # include "config.h"
  26 #endif
  27
  28 #include <assert.h>
  29
  30 #include "umac.h"
  31
  32 #define HI(x) (x >> 32)
  33 #define LO(x) (x & 0xffffffffUL)
  34
  35 static void
  36 poly128_mul (const uint32_t *k, uint64_t *y)
  37 {
  38   uint64_t y0,y1,y2,y3,p0,p1,p2,p3,m0,m1,m2;
  39   y0 = LO (y[1]);
  40   y1 = HI (y[1]);
  41   y2 = LO (y[0]);
  42   y3 = HI (y[0]);
  43
  44   p0 = y0 * k[3];
  45   m0 = y0 * k[2] + y1 * k[3];
  46   p1 = y0 * k[1] + y1 * k[2] + y2 * k[3];
  47   m1 = y0 * k[0] + y1 * k[1] + y2 * k[2] + y3 * k[3];
  48   p2 = y1 * k[0] + y2 * k[1] + y3 * k[2];
  49   m2 = y2 * k[0] + y3 * k[1];
  50   p3 = y3 * k[0];
  51
  52   /* Collaps to 4 64-bit words,
  53      +---+---+---+---+
  54      | p3| p2| p1| p0|
  55      +-+-+-+-+-+-+-+-+
  56     +  | m2| m1| m0|
  57     -+-+-+-+-+-+-+-+-+
  58   */
  59   /* But it's convenient to reduce (p3,p2,p1,p0) and (m2,m1,m0) mod p first.*/
  60   m1 += UMAC_P128_OFFSET * HI(p3);
  61   p1 += UMAC_P128_OFFSET * (LO(p3) + HI(m2));
  62   m0 += UMAC_P128_OFFSET * (HI(p2) + LO(m2));
  63   p0 += UMAC_P128_OFFSET * (LO(p2) + HI(m1));
  64
  65   /* Left to add
  66      +---+---+
  67      | p1| p0|
  68      +-+-+-+-+
  69      m1| m0|
  70      +-+---+
  71   */
  72   /* First add high parts, with no possibilities for carries */
  73   p1 += m0 >> 32;
  74
  75   m0 <<= 32;
  76   m1 <<= 32;
  77
  78   /* Remains:
  79      +---+---+
  80      | p1| p0|
  81      +-+-+---+
  82     +| m1| m0|
  83     -+---+---+
  84   */
  85   p0 += m0;
  86   p1 += (p0 < m0);
  87   p1 += m1;
  88   if (p1 < m1)
  89     {
  90       p0 += UMAC_P128_OFFSET;
  91       p1 += (p0 < UMAC_P128_OFFSET);
  92     }
  93
  94   y[0] = p1;
  95   y[1] = p0;
  96 }
  97
  98 void
  99 _umac_poly128 (const uint32_t *k, uint64_t *y, uint64_t mh, uint64_t ml)
 100 {
 101   uint64_t yh, yl, cy;
 102
 103   if ( (mh >> 32) == 0xffffffff)
 104     {
 105       poly128_mul (k, y);
 106       if (y[1] > 0)
 107         y[1]--;
 108       else if (y[0] > 0)
 109         {
 110           y[0]--;
 111           y[1] = UMAC_P128_HI;
 112         }
 113       else
 114         {
 115           y[0] = UMAC_P128_HI;
 116           y[1] = UMAC_P128_LO-1;
 117         }
 118
 119       mh -= (ml < UMAC_P128_OFFSET);
 120       ml -= UMAC_P128_OFFSET;
 121     }
 122   assert (mh < UMAC_P128_HI || ml < UMAC_P128_LO);
 123
 124   poly128_mul (k, y);
 125   yl = y[1] + ml;
 126   cy = (yl < ml);
 127   yh = y[0] + cy;
 128   cy = (yh < cy);
 129   yh += mh;
 130   cy += (yh < mh);
 131   assert (cy <= 1);
 132   if (cy)
 133     {
 134       yl += UMAC_P128_OFFSET;
 135       yh += yl < UMAC_P128_OFFSET;
 136     }
 137
 138   y[0] = yh;
 139   y[1] = yl;
 140 }