git.samba.org - gd/nettle/blob - umac-poly128.c

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