1 /*
  2  * Copyright (c) 2019, 2021, Oracle and/or its affiliates. All rights reserved.
  3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4  *
  5  * This code is free software; you can redistribute it and/or modify it
  6  * under the terms of the GNU General Public License version 2 only, as
  7  * published by the Free Software Foundation.
  8  *
  9  * This code is distributed in the hope that it will be useful, but WITHOUT
 10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 12  * version 2 for more details (a copy is included in the LICENSE file that
 13  * accompanied this code).
 14  *
 15  * You should have received a copy of the GNU General Public License version
 16  * 2 along with this work; if not, write to the Free Software Foundation,
 17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 18  *
 19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 20  * or visit www.oracle.com if you need additional information or have any
 21  * questions.
 22  */
 23 
 24 package org.openjdk.bench.jdk.incubator.vector.crypto;
 25 
 26 import org.openjdk.jmh.annotations.*;
 27 import jdk.incubator.vector.*;
 28 
 29 import java.nio.ByteOrder;
 30 import java.util.Arrays;
 31 
 32 @State(Scope.Thread)
 33 @BenchmarkMode(Mode.Throughput)
 34 @Fork(value = 1, jvmArgsPrepend = {"--add-modules=jdk.incubator.vector"})
 35 @Warmup(iterations = 3, time = 3)
 36 @Measurement(iterations = 8, time = 2)
 37 public class Poly1305Bench {
 38 
 39     @Param({"16384", "65536"})
 40     private int dataSize;
 41 
 42     private Poly1305Vector poly1305_S128 = makePoly1305(VectorShape.S_128_BIT);
 43     private Poly1305Vector poly1305_S256 = makePoly1305(VectorShape.S_256_BIT);
 44     private Poly1305Vector poly1305_S512 = makePoly1305(VectorShape.S_512_BIT);
 45 
 46     private byte[] in;
 47     private byte[] out = new byte[16];
 48     private byte[] key = new byte[32];
 49 
 50     private static Poly1305Vector makePoly1305(VectorShape shape) {
 51         Poly1305Vector poly = new Poly1305Vector(shape);
 52         runKAT(poly);
 53         return poly;
 54     }
 55 
 56     @Setup
 57     public void setup() {
 58         in = new byte[dataSize];
 59     }
 60 
 61     @Benchmark
 62     public void auth128() {
 63         poly1305_S128.computeTag(key, in, out);
 64     }
 65 
 66     @Benchmark
 67     public void auth256() {
 68         poly1305_S256.computeTag(key, in, out);
 69     }
 70 
 71     @Benchmark
 72     public void auth512() {
 73         poly1305_S512.computeTag(key, in, out);
 74     }
 75 
 76     private static class Poly1305Vector {
 77 
 78         private static final int BITS_PER_LIMB = 26;
 79         private static final int LIMB_MASK = (1 << BITS_PER_LIMB) - 1;
 80         private static final int KEY_LENGTH = 32;
 81         private static final int RS_LENGTH = KEY_LENGTH / 2;
 82 
 83         private final VectorSpecies<Long> longSpecies;
 84         private final VectorSpecies<Integer> intSpecies;
 85         private final int vectorWidth;
 86         private final int parBlockCount;
 87 
 88         private final VectorShuffle<Long> inShuffle0;
 89         private final VectorShuffle<Long> inShuffle1;
 90         private final VectorMask<Long> inMask;
 91 
 92         public Poly1305Vector(VectorShape shape) {
 93 
 94             this.longSpecies = VectorSpecies.of(long.class, shape);
 95             int intSize = shape.vectorBitSize() / 2;
 96             VectorShape intShape = VectorShape.forBitSize(intSize);
 97             this.intSpecies = VectorSpecies.of(int.class, intShape);
 98             this.vectorWidth = longSpecies.length();
 99             this.parBlockCount = vectorWidth * 16;
100 
101             this.inShuffle0 = makeInShuffle0();
102             this.inShuffle1 = makeInShuffle1();
103             this.inMask = makeInMask();
104         }
105 
106         private VectorShuffle<Long> makeInShuffle0() {
107             int[] indexArr = new int[vectorWidth];
108             for (int i = 0; i < indexArr.length; i++) {
109                 indexArr[i] = (2 * i) % vectorWidth;
110             }
111             return VectorShuffle.fromArray(longSpecies, indexArr, 0);
112         }
113         private VectorShuffle<Long> makeInShuffle1() {
114             int[] indexArr = new int[vectorWidth];
115             for (int i = 0; i < indexArr.length; i++) {
116                 indexArr[i] = ((2 * i) % vectorWidth) + 1;
117             }
118             return VectorShuffle.fromArray(longSpecies, indexArr, 0);
119         }
120         private VectorMask<Long> makeInMask() {
121             boolean[] maskArr = new boolean[vectorWidth];
122             for (int i = vectorWidth / 2; i < vectorWidth; i++) {
123                 maskArr[i] = true;
124             }
125             return VectorMask.fromArray(longSpecies, maskArr, 0);
126         }
127 
128         private static int[] fromByteArray(byte[] buf) {
129             int[] result = new int[5];
130 
131             result[0]
132                     = (buf[0] & 0xFF)
133                     + ((buf[1] & 0xFF) << 8)
134                     + ((buf[2] & 0xFF) << 16)
135                     + ((buf[3] & 0x03) << 24);
136             result[1]
137                     = ((buf[3] & 0xFF) >> 2)
138                     + ((buf[4] & 0xFF) << 6)
139                     + ((buf[5] & 0xFF) << 14)
140                     + ((buf[6] & 0x0F) << 22);
141             result[2]
142                     = ((buf[6] & 0xFF) >> 4)
143                     + ((buf[7] & 0xFF) << 4)
144                     + ((buf[8] & 0xFF) << 12)
145                     + ((buf[9] & 0x3F) << 20);
146             result[3]
147                     = ((buf[9] & 0xFF) >> 6)
148                     + ((buf[10] & 0xFF) << 2)
149                     + ((buf[11] & 0xFF) << 10)
150                     + ((buf[12] & 0xFF) << 18);
151             result[4]
152                     = (buf[13] & 0xFF)
153                     + ((buf[14] & 0xFF) << 8)
154                     + ((buf[15] & 0xFF) << 16);
155 
156             return result;
157         }
158 
159         private static void toByteArray(long v0, long v1, long v2, long v3,
160             long v4, byte[] dst) {
161 
162             dst[0] = (byte) v0;
163             v0 >>= 8;
164             dst[1] = (byte) v0;
165             v0 >>= 8;
166             dst[2] = (byte) v0;
167             v0 >>= 8;
168             dst[3] = (byte) v0;
169 
170             dst[3] += (v1 & 0x3F) << 2;
171             v1 >>= 6;
172             dst[4] = (byte) v1;
173             v1 >>= 8;
174             dst[5] = (byte) v1;
175             v1 >>= 8;
176             dst[6] = (byte) v1;
177 
178             dst[6] += (v2 & 0xF) << 4;
179             v2 >>= 4;
180             dst[7] = (byte) v2;
181             v2 >>= 8;
182             dst[8] = (byte) v2;
183             v2 >>= 8;
184             dst[9] = (byte) v2;
185 
186             dst[9] += (v3 & 0x3) << 6;
187             v3 >>= 2;
188             dst[10] = (byte) v3;
189             v3 >>= 8;
190             dst[11] = (byte) v3;
191             v3 >>= 8;
192             dst[12] = (byte) v3;
193 
194             dst[13] = (byte) v4;
195             v4 >>= 8;
196             dst[14] = (byte) v4;
197             v4 >>= 8;
198             dst[15] = (byte) v4;
199         }
200 
201         protected static long carryValue(long x) {
202             return x >> BITS_PER_LIMB;
203         }
204 
205         public static void carryReduce(int[] r, long c0, long c1, long c2,
206             long c3, long c4) {
207 
208             long c;
209 
210             c = carryValue(c3); c3 &= LIMB_MASK; c4 += c;
211             c = carryValue(c4); c4 &= LIMB_MASK; c0 += c * 5;
212             c = carryValue(c0); c0 &= LIMB_MASK; c1 += c;
213             c = carryValue(c1); c1 &= LIMB_MASK; c2 += c;
214             c = carryValue(c2); c2 &= LIMB_MASK; c3 += c;
215             c = carryValue(c3); c3 &= LIMB_MASK; c4 += c;
216 
217             r[0] = (int) c0;
218             r[1] = (int) c1;
219             r[2] = (int) c2;
220             r[3] = (int) c3;
221             r[4] = (int) c4;
222         }
223 
224         private int[] multiply(int[] a, int[] b) {
225             int[] result = new int[5];
226 
227             long a0 = a[0];
228             long a1 = a[1];
229             long a2 = a[2];
230             long a3 = a[3];
231             long a4 = a[4];
232 
233             long c0 = (a0 * b[0]) + 5 * (a1 * b[4]) + 5 * (a2 * b[3]) +
234                 5 * (a3 * b[2]) + 5 * (a4 * b[1]);
235             long c1 = (a0 * b[1]) + (a1 * b[0]) + 5 * (a2 * b[4]) +
236                 5 * (a3 * b[3]) + 5 * (a4 * b[2]);
237             long c2 = (a0 * b[2]) + (a1 * b[1]) + (a2 * b[0]) +
238                 5 * (a3 * b[4]) + 5 * (a4 * b[3]);
239             long c3 = (a0 * b[3]) + (a1 * b[2]) + (a2 * b[1]) + (a3 * b[0]) +
240                 5 * (a4 * b[4]);
241             long c4 = (a0 * b[4]) + (a1 * b[3]) + (a2 * b[2]) + (a3 * b[1]) +
242                 (a4 * b[0]);
243 
244             carryReduce(result, c0, c1, c2, c3, c4);
245 
246             return result;
247         }
248 
249         private LongVector rPowerVec(int[][] r, long[] temp, int maxIndex,
250             int secondIndex) {
251 
252             for (int i = 0; i < temp.length; i++) {
253                 temp[i] = r[maxIndex - i][secondIndex];
254             }
255             return LongVector.fromArray(longSpecies, temp, 0);
256         }
257 
258         public void computeTag(byte[] key, byte[] msg, byte[] out) {
259 
260             byte[] keyBytes = key.clone();
261 
262             // setup key values
263             // Clamp the bytes in the "r" half of the key.
264             keyBytes[3] &= 15;
265             keyBytes[7] &= 15;
266             keyBytes[11] &= 15;
267             keyBytes[15] &= 15;
268             keyBytes[4] &= 252;
269             keyBytes[8] &= 252;
270             keyBytes[12] &= 252;
271 
272             // Create IntegerModuloP elements from the r and s values
273             int[][] r = new int[vectorWidth][];
274             r[0] = fromByteArray(keyBytes);
275             for (int i = 1; i < vectorWidth; i++) {
276                 r[i] = multiply(r[i - 1], r[0]);
277             }
278 
279             int rUpIndex = vectorWidth - 1;
280             IntVector rUp0_int = IntVector.broadcast(intSpecies, r[rUpIndex][0]);
281             IntVector rUp1_int = IntVector.broadcast(intSpecies, r[rUpIndex][1]);
282             IntVector rUp2_int = IntVector.broadcast(intSpecies, r[rUpIndex][2]);
283             IntVector rUp3_int = IntVector.broadcast(intSpecies, r[rUpIndex][3]);
284             IntVector rUp4_int = IntVector.broadcast(intSpecies, r[rUpIndex][4]);
285 
286             IntVector r5Up1_int = rUp1_int.mul(5);
287             IntVector r5Up2_int = rUp2_int.mul(5);
288             IntVector r5Up3_int = rUp3_int.mul(5);
289             IntVector r5Up4_int = rUp4_int.mul(5);
290 
291             LongVector longMsg0 = LongVector.fromByteArray(longSpecies, msg, 0, ByteOrder.LITTLE_ENDIAN);
292             LongVector longMsg1 =
293                 LongVector.fromByteArray(longSpecies, msg, vectorWidth * 8, ByteOrder.LITTLE_ENDIAN);
294 
295             LongVector inAlign0 =
296             longMsg0.rearrange(inShuffle0).blend(longMsg1.rearrange(inShuffle0), inMask);
297             LongVector inAlign1 =
298             longMsg0.rearrange(inShuffle1).blend(longMsg1.rearrange(inShuffle1), inMask);
299 
300             IntVector a0 = (IntVector)
301                 inAlign0.and(LIMB_MASK).castShape(intSpecies, 0);
302             IntVector a1 = (IntVector)
303                 inAlign0.lanewise(VectorOperators.LSHR,26).and(LIMB_MASK).castShape(intSpecies, 0);
304             IntVector a2 = (IntVector)
305                 inAlign0.lanewise(VectorOperators.LSHR,52).and(0xFFF).castShape(intSpecies, 0);
306             a2 = a2.or(inAlign1.and(0x3FFF).lanewise(VectorOperators.LSHL,12).castShape(intSpecies, 0));
307             IntVector a3 = (IntVector)
308                 inAlign1.lanewise(VectorOperators.LSHR,14).and(LIMB_MASK).castShape(intSpecies, 0);
309             IntVector a4 = (IntVector)
310                 inAlign1.lanewise(VectorOperators.LSHR,40).and(0xFFFFFF).castShape(intSpecies, 0);
311             a4 = a4.or(1 << 24);
312 
313             int numParBlocks = msg.length / parBlockCount - 1;
314             for (int i = 0; i < numParBlocks; i++) {
315 
316                 // multiply and reduce
317                 LongVector c0 = (LongVector)
318                     a0.castShape(longSpecies, 0).mul(rUp0_int.castShape(longSpecies, 0))
319                     .add(a1.castShape(longSpecies, 0).mul(r5Up4_int.castShape(longSpecies, 0)))
320                     .add(a2.castShape(longSpecies, 0).mul(r5Up3_int.castShape(longSpecies, 0)))
321                     .add(a3.castShape(longSpecies, 0).mul(r5Up2_int.castShape(longSpecies, 0)))
322                     .add(a4.castShape(longSpecies, 0).mul(r5Up1_int.castShape(longSpecies, 0)));
323 
324                 LongVector c1 = (LongVector)
325                     a0.castShape(longSpecies, 0).mul(rUp1_int.castShape(longSpecies, 0))
326                     .add(a1.castShape(longSpecies, 0).mul(rUp0_int.castShape(longSpecies, 0)))
327                     .add(a2.castShape(longSpecies, 0).mul(r5Up4_int.castShape(longSpecies, 0)))
328                     .add(a3.castShape(longSpecies, 0).mul(r5Up3_int.castShape(longSpecies, 0)))
329                     .add(a4.castShape(longSpecies, 0).mul(r5Up2_int.castShape(longSpecies, 0)));
330 
331                 LongVector c2 = (LongVector)
332                     a0.castShape(longSpecies, 0).mul(rUp2_int.castShape(longSpecies, 0))
333                     .add(a1.castShape(longSpecies, 0).mul(rUp1_int.castShape(longSpecies, 0)))
334                     .add(a2.castShape(longSpecies, 0).mul(rUp0_int.castShape(longSpecies, 0)))
335                     .add(a3.castShape(longSpecies, 0).mul(r5Up4_int.castShape(longSpecies, 0)))
336                     .add(a4.castShape(longSpecies, 0).mul(r5Up3_int.castShape(longSpecies, 0)));
337 
338                 LongVector c3 = (LongVector)
339                     a0.castShape(longSpecies, 0).mul(rUp3_int.castShape(longSpecies, 0))
340                     .add(a1.castShape(longSpecies, 0).mul(rUp2_int.castShape(longSpecies, 0)))
341                     .add(a2.castShape(longSpecies, 0).mul(rUp1_int.castShape(longSpecies, 0)))
342                     .add(a3.castShape(longSpecies, 0).mul(rUp0_int.castShape(longSpecies, 0)))
343                     .add(a4.castShape(longSpecies, 0).mul(r5Up4_int.castShape(longSpecies, 0)));
344 
345                 LongVector c4 = (LongVector)
346                     a0.castShape(longSpecies, 0).mul(rUp4_int.castShape(longSpecies, 0))
347                     .add(a1.castShape(longSpecies, 0).mul(rUp3_int.castShape(longSpecies, 0)))
348                     .add(a2.castShape(longSpecies, 0).mul(rUp2_int.castShape(longSpecies, 0)))
349                     .add(a3.castShape(longSpecies, 0).mul(rUp1_int.castShape(longSpecies, 0)))
350                     .add(a4.castShape(longSpecies, 0).mul(rUp0_int.castShape(longSpecies, 0)));
351 
352                 // carry/reduce
353                 // Note: this carry/reduce sequence might not be correct
354                 c4 = c4.add(c3.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
355                 c3 = c3.and(LIMB_MASK);
356                 c0 = c0.add(c4.lanewise(VectorOperators.LSHR, BITS_PER_LIMB).mul(5));
357                 c4 = c4.and(LIMB_MASK);
358                 c1 = c1.add(c0.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
359                 c0 = c0.and(LIMB_MASK);
360                 c2 = c2.add(c1.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
361                 c1 = c1.and(LIMB_MASK);
362                 c3 = c3.add(c2.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
363                 c2 = c2.and(LIMB_MASK);
364                 c4 = c4.add(c3.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
365                 c3 = c3.and(LIMB_MASK);
366 
367                 a0 = (IntVector) c0.castShape(intSpecies, 0);
368                 a1 = (IntVector) c1.castShape(intSpecies, 0);
369                 a2 = (IntVector) c2.castShape(intSpecies, 0);
370                 a3 = (IntVector) c3.castShape(intSpecies, 0);
371                 a4 = (IntVector) c4.castShape(intSpecies, 0);
372 
373                 // fromByteArray and add next part of message
374                 int start = parBlockCount * (i + 1);
375 
376                 longMsg0 = LongVector.fromByteArray(longSpecies, msg, start, ByteOrder.LITTLE_ENDIAN);
377                 longMsg1 = LongVector.fromByteArray(longSpecies, msg,
378                     start + vectorWidth * 8, ByteOrder.LITTLE_ENDIAN);
379 
380                 inAlign0 =
381                         longMsg0.rearrange(inShuffle0).blend(longMsg1.rearrange(inShuffle0), inMask);
382                 inAlign1 =
383                         longMsg0.rearrange(inShuffle1).blend(longMsg1.rearrange(inShuffle1), inMask);
384 
385                 IntVector in0 = (IntVector)
386                     inAlign0.and(LIMB_MASK).castShape(intSpecies, 0);
387                 IntVector in1 = (IntVector)
388                     inAlign0.lanewise(VectorOperators.LSHR, 26).and(LIMB_MASK).castShape(intSpecies, 0);
389                 IntVector in2 = (IntVector)
390                     inAlign0.lanewise(VectorOperators.LSHR, 52).and(0xFFF).castShape(intSpecies, 0);
391                 in2 = in2.or(inAlign1.and(0x3FFF).lanewise(VectorOperators.LSHL, 12).castShape(intSpecies, 0));
392                 IntVector in3 = (IntVector)
393                     inAlign1.lanewise(VectorOperators.LSHR, 14).and(LIMB_MASK).castShape(intSpecies, 0);
394                 IntVector in4 = (IntVector)
395                     inAlign1.lanewise(VectorOperators.LSHR, 40).and(0xFFFFFF).castShape(intSpecies, 0);
396                 in4 = in4.or(1 << 24);
397 
398                 a0 = a0.add(in0);
399                 a1 = a1.add(in1);
400                 a2 = a2.add(in2);
401                 a3 = a3.add(in3);
402                 a4 = a4.add(in4);
403             }
404 
405             // multiply by powers of r
406             long[] rTemp = new long[vectorWidth];
407             LongVector rFin0 = rPowerVec(r, rTemp, rUpIndex, 0);
408             LongVector rFin1 = rPowerVec(r, rTemp, rUpIndex, 1);
409             LongVector rFin2 = rPowerVec(r, rTemp, rUpIndex, 2);
410             LongVector rFin3 = rPowerVec(r, rTemp, rUpIndex, 3);
411             LongVector rFin4 = rPowerVec(r, rTemp, rUpIndex, 4);
412 
413             LongVector r5Fin_1 = rFin1.mul(5);
414             LongVector r5Fin_2 = rFin2.mul(5);
415             LongVector r5Fin_3 = rFin3.mul(5);
416             LongVector r5Fin_4 = rFin4.mul(5);
417 
418             LongVector c0 = (LongVector) a0.castShape(longSpecies, 0).mul(rFin0)
419                 .add(a1.castShape(longSpecies, 0).mul(r5Fin_4))
420                 .add(a2.castShape(longSpecies, 0).mul(r5Fin_3))
421                 .add(a3.castShape(longSpecies, 0).mul(r5Fin_2))
422                 .add(a4.castShape(longSpecies, 0).mul(r5Fin_1));
423             LongVector c1 = (LongVector) a0.castShape(longSpecies, 0).mul(rFin1)
424                 .add(a1.castShape(longSpecies, 0).mul(rFin0))
425                 .add(a2.castShape(longSpecies, 0).mul(r5Fin_4))
426                 .add(a3.castShape(longSpecies, 0).mul(r5Fin_3))
427                 .add(a4.castShape(longSpecies, 0).mul(r5Fin_2));
428             LongVector c2 = (LongVector) a0.castShape(longSpecies, 0).mul(rFin2)
429                 .add(a1.castShape(longSpecies, 0).mul(rFin1))
430                 .add(a2.castShape(longSpecies, 0).mul(rFin0))
431                 .add(a3.castShape(longSpecies, 0).mul(r5Fin_4))
432                 .add(a4.castShape(longSpecies, 0).mul(r5Fin_3));
433             LongVector c3 = (LongVector) a0.castShape(longSpecies, 0).mul(rFin3)
434                 .add(a1.castShape(longSpecies, 0).mul(rFin2))
435                 .add(a2.castShape(longSpecies, 0).mul(rFin1))
436                 .add(a3.castShape(longSpecies, 0).mul(rFin0))
437                 .add(a4.castShape(longSpecies, 0).mul(r5Fin_4));
438             LongVector c4 = (LongVector) a0.castShape(longSpecies, 0).mul(rFin4)
439                 .add(a1.castShape(longSpecies, 0).mul(rFin3))
440                 .add(a2.castShape(longSpecies, 0).mul(rFin2))
441                 .add(a3.castShape(longSpecies, 0).mul(rFin1))
442                 .add(a4.castShape(longSpecies, 0).mul(rFin0));
443 
444             c4 = c4.add(c3.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
445             c3 = c3.and(LIMB_MASK);
446             c0 = c0.add(c4.lanewise(VectorOperators.LSHR, BITS_PER_LIMB).mul(5));
447             c4 = c4.and(LIMB_MASK);
448             c1 = c1.add(c0.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
449             c0 = c0.and(LIMB_MASK);
450             c2 = c2.add(c1.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
451             c1 = c1.and(LIMB_MASK);
452             c3 = c3.add(c2.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
453             c2 = c2.and(LIMB_MASK);
454             c4 = c4.add(c3.lanewise(VectorOperators.LSHR, BITS_PER_LIMB));
455             c3 = c3.and(LIMB_MASK);
456 
457             a0 = (IntVector) c0.castShape(intSpecies, 0);
458             a1 = (IntVector) c1.castShape(intSpecies, 0);
459             a2 = (IntVector) c2.castShape(intSpecies, 0);
460             a3 = (IntVector) c3.castShape(intSpecies, 0);
461             a4 = (IntVector) c4.castShape(intSpecies, 0);
462 
463             // collect lanes and calculate tag
464             long a0Fin = a0.reduceLanes(VectorOperators.ADD);
465             long a1Fin = a1.reduceLanes(VectorOperators.ADD);
466             long a2Fin = a2.reduceLanes(VectorOperators.ADD);
467             long a3Fin = a3.reduceLanes(VectorOperators.ADD);
468             long a4Fin = a4.reduceLanes(VectorOperators.ADD);
469 
470             // carry/reduce the result
471             a4Fin = a4Fin + (a3Fin >>> BITS_PER_LIMB);
472             a3Fin = a3Fin & LIMB_MASK;
473             a0Fin = a0Fin + ((a4Fin >>> BITS_PER_LIMB) * 5);
474             a4Fin = a4Fin & LIMB_MASK;
475             a1Fin = a1Fin + (a0Fin >>> BITS_PER_LIMB);
476             a0Fin = a0Fin & LIMB_MASK;
477             a2Fin = a2Fin + (a1Fin >>> BITS_PER_LIMB);
478             a1Fin = a1Fin & LIMB_MASK;
479             a3Fin = a3Fin + (a2Fin >>> BITS_PER_LIMB);
480             a2Fin = a2Fin & LIMB_MASK;
481             a4Fin = a4Fin + (a3Fin >>> BITS_PER_LIMB);
482             a3Fin = a3Fin & LIMB_MASK;
483 
484             byte[] s_arr =
485                 Arrays.copyOfRange(keyBytes, RS_LENGTH, 2 * RS_LENGTH);
486             int[] s = fromByteArray(s_arr);
487 
488             // Add in the s-half of the key to the accumulator
489             a0Fin += s[0];
490             a1Fin += s[1];
491             a2Fin += s[2];
492             a3Fin += s[3];
493             a4Fin += s[4];
494 
495             // final carry mod 2^130
496             a1Fin = a1Fin + (a0Fin >> BITS_PER_LIMB);
497             a0Fin = a0Fin & LIMB_MASK;
498             a2Fin = a2Fin + (a1Fin >> BITS_PER_LIMB);
499             a1Fin = a1Fin & LIMB_MASK;
500             a3Fin = a3Fin + (a2Fin >> BITS_PER_LIMB);
501             a2Fin = a2Fin & LIMB_MASK;
502             a4Fin = a4Fin + (a3Fin >> BITS_PER_LIMB);
503             a3Fin = a3Fin & LIMB_MASK;
504             a4Fin = a4Fin & LIMB_MASK;
505 
506             // put result in buffer
507             toByteArray(a0Fin, a1Fin, a2Fin, a3Fin, a4Fin, out);
508         }
509     }
510 
511 
512     private static byte[] hexStringToByteArray(String str) {
513         byte[] result = new byte[str.length() / 2];
514         for (int i = 0; i < result.length; i++) {
515             result[i] = (byte) Character.digit(str.charAt(2 * i), 16);
516             result[i] <<= 4;
517             result[i] += Character.digit(str.charAt(2 * i + 1), 16);
518         }
519         return result;
520     }
521 
522     public static String byteArrayToHexString(byte[] arr) {
523         StringBuilder result = new StringBuilder();
524         for (int i = 0; i < arr.length; ++i) {
525             byte curVal = arr[i];
526             result.append(Character.forDigit(curVal >> 4 & 0xF, 16));
527             result.append(Character.forDigit(curVal & 0xF, 16));
528         }
529         return result.toString();
530     }
531 
532     private static void kat(Poly1305Vector poly1305, String key, String msg,
533         String expectedTag) {
534 
535         kat(poly1305, hexStringToByteArray(key), hexStringToByteArray(msg),
536             hexStringToByteArray(expectedTag));
537     }
538 
539     private static void kat(Poly1305Vector poly1305, byte[] key, byte[] msg,
540         byte[] expectedTag) {
541 
542         byte[] tag = new byte[expectedTag.length];
543         poly1305.computeTag(key, msg, tag);
544         if (!Arrays.equals(tag, expectedTag)) {
545             throw new RuntimeException(
546                     "bad tag: " + byteArrayToHexString(tag) +
547                     " expected: " + byteArrayToHexString(expectedTag));
548         }
549     }
550 
551     /*
552      * Poly1305 Known Answer Tests to ensure that the implementation is correct.
553      */
554     private static void runKAT(Poly1305Vector poly1305) {
555         kat(poly1305,
556             "d212b886dd4682a41f1759e6c5aef84760e5a63d4423ca7d1fb5c7ecfc5dac27",
557             "5d2ad39e2a7b0bc5f375488643acf391188d01ad936971457427bc053c4262a1" +
558             "598532850def8573213c5f79fa736703c57c03ec49b55617210998c8af408698" +
559             "866632a7ecf7e9a688605cbca919e17e2badd090a7a6d83ad90be0617fa44642" +
560             "cc9a1ca38514a026cbea51c287ec0b56719fc61183c88e9450ba85aa8ab7d390",
561             "7ccdfa8e82df540276e8172f705adce2");
562 
563         kat(poly1305,
564             "2b0b684c86910104aee1d261ac4d5a0f5443b4b7746cf7f8ba03921d273f6a9b",
565             "027b359f44a5d60f81073ceb74749207742529dcefa4a26a1817db2c8d50ba2b" +
566             "d9e170cd1930946872d95e4eae41389f362087871a749897e0fbe42494e6f0b3" +
567             "8db01e2059510b6fda4f422ce7d226433ba00940e1761baaff80d9b8f3a61d11" +
568             "a109e6082d231cf85aa718199e6eaaaf07bad562469ef1b8e639c727967bf6da" +
569             "bcd16fcb0fc102095325e2fac92e599e81c26900df1deb7b0a0b5c321a658024" +
570             "26506740509ece646fecf33a517b66e57577372156aae85765c6b473521d1019" +
571             "4f5fbe0e932cfee716e1d41c9154fb8e15b82ab7e807fb54f3d7d3e4c589cc9a" +
572             "492d17ea4fd27894fa9d22a9db6d5df674cd1e97e7e8758a360291f22dfe1cc3",
573             "84ca3a778faf0ab9f840fe5fb38ace27");
574 
575         kat(poly1305,
576             "870c6fa7da2eadb845ac8b0eeaed4cf856eca67bf96b64a29a2e6a881821fa8a",
577             "ff1a3b67a4f575be5f05c4054e4c7365838c2cbe786ba78900c8b43f197c3c4d" +
578             "120432a287e434669af579bcd56f3320e54d2f97a306f917f2f41b1c97cc69db" +
579             "4ac2051adccd687fa89f92504d1ab5c3006681d846c8051aabccca0024ef5ec4" +
580             "c43b8701ffc9d14fef8d55e229ed210a2b9bde996f5d7b545d15e1fc32764604" +
581             "b2a0384dd173aa800b7526c8ff397c05130bb6a1f2194968adaef6979b023cd8" +
582             "d9195d2739351c7e4ac6c43508634f813641f669e78cbcf732ccb1321a2cd2c4" +
583             "14c7df5b9ea3408f2e12fbf3a3cbdb98699dd5402725ec25f9fff9bcd0f93cb3" +
584             "cf0dac016fec41a5ef3ae8b8d258a09f530ad14ad2e52186041592eac0ea22ff" +
585             "8c3751009b516c60f7764cccbb816394ef035bd8cb2a38d5c6b9229e528e56cd" +
586             "62600b5219b64212642384e628f01d790eeef4963a7d1a63a9faff79d4acfa09" +
587             "78b58b0b623ae89389661aa408b16814d3baaca20978dce6888c3365f4ffd2fa" +
588             "8f031a44f2e870a06da21d7becf450d335e1386268bc189435e7955a477bc368",
589             "ff4e0ee6feb1c6a57e638a79fafc7c60");
590 
591         kat(poly1305,
592             "c27987ae88a833ae2ea90371b2e257c15773da3bc34516b6b075446e1f844a81",
593             "64e5a2e2940b173c7103ae931ced302a8f8c778f4e5c0b3677c51552655005d8" +
594             "504b724107e7262448c94db83fc9c6a2a26fc973360dce15c0553b73bb733d3e" +
595             "f61fcba8977e76c32523b80c3b45b1226b23ee17522f9b677880c69b356917ae" +
596             "3c792a0c5b0c77b90dfa51483626323b7a73fffb1b128c595d553bf62a8f5bb9" +
597             "fa48b4a850a932481bf607e8da84730c9052bba9316ec7eb84007a4eb5cbed5c" +
598             "7c67ef32d4c5cb6cfbccd738d239857c240de6d3d4e5af14d480feb63541e5d8" +
599             "036e088b2e32431e6fe0c4d3505aebe2e14bd02b6b15325f89aef048cd1236db" +
600             "4461a59304b7c61ece2c52ef8ac4cf2326e6aaff013494b1b191be4ae4381f57" +
601             "e72b947ee23d0a528087db9338bc28c68484929fc3436995b2083b06a765ceb7" +
602             "09e9dd41ba896d99832d6851189766e844137d9a83d2890bc2be7afc82f9ebb8" +
603             "bafe08ef5f7ff0cce9a1d08e6b797a17df04731f384a34b16e72e9f2ab070114" +
604             "8008945509fe378658dc51eb752248f48364be327cd1b6bd148c518a976ae95d" +
605             "d391f3b0d447251988c7e77400c9d44395b8f9f10cbc442a6804d0ad83e8c3e3" +
606             "9fa09c2140fac143c90f09a7d907c57e29b528d54c8bd927f39aee2cec671213" +
607             "c50fe657b29682d57a419e3e52dafb348cbe44b6c17e4be18f5c5e411734fcfc" +
608             "99b9ca26f29a21cc93374ef1bfa86ca2bb3be76b94b4ef69ec790c968a51e4d0",
609             "d4c09727f68fa3beb57ce9e74205b652");
610 
611         kat(poly1305,
612             "2593adf2efc0e49c7fde0d45de4f7a21ceb76df45c0e5a917ef1f6b7fbf4fb7e",
613             "23665b9a6d4f04c9d58347d32d64d4cbf8d4ca993a8bb73758e6eb2db9f97096" +
614             "d0f00aca8cb16460d2bc15c0136fa92482602f47b3ec78244c4dc619d9b28afa" +
615             "19b063c196bcff848eff179102cce29dfcc58bf90a2f6311e6d021e2573ccbb4" +
616             "4e06947167c9865127c0b7362196523f97c8157058f7aebff475f77e23393dc1" +
617             "a3031bbaf31270db3eadc00cca6ae073aa53160d095afdce0a202de8a23d9a38" +
618             "b0bed20cbe64e1ec77fc13ba0cfc9be52edb70475bf1aeaaff25e11f2e0ae47f" +
619             "f23cbd4a6219d276fcc6c8f12a739f11434c86d4e24397f96ef6e36d9195fa8a" +
620             "48eb55990d69feacfb754b5019a3ebafa98d5544077b46c136cc11de8ee7f8a6" +
621             "76a6696600088696233f4e8f060ba8a64890fb638469639bfb727ed758c36250" +
622             "a553b7ce1115509f2bb19c13cea87003a8eff45ce9e1cff0a21ba5ae19226d50" +
623             "e108db212a588e5f4c502468859b9b607922c3311b5d912bd9400e696d7debbb" +
624             "9ac5454cc7d0f95fc242c491f095a02f0d3bd7ead0f0b7358c9b1d85e4e9ab75" +
625             "24bb43867c94a21a4e0db6470a210c9dd937e4801396bd687127fa7c83014c85" +
626             "372553c56dfd6cd9b75fa10483aea825f8e3fa53c6bf17467e37c2e7439ed0ea" +
627             "6fb24d13d428965c44f1ac943c7bc77fa84711c91b41f5ee6d9a7d9091648a96" +
628             "cc7c261d7fc5d964446d1e3dcc41d32ecaa8d7791b8462563fcf7f96cd1d11d4" +
629             "34923e0150321356866f5bdafebc96f2661bfd3c1f104e96b6492cafcbe25fc6" +
630             "ec0c92a3bbec7328e1905d5951fae04625a2452f596027a5d9c64eed55165c8a" +
631             "23bc3f944b4fa9c7ad83ebc1777c7153d5de13d04c0a12e774b17906a62f5134" +
632             "685c2de31da08bd04840299fd62d56ffe95248365034e7ba95961cebf0542b24",
633             "b9f68b0996caf5135136b10b37fe5f81");
634 
635         kat(poly1305,
636             "e9c8c78bc0ad5751f094fd4657fe5ef2a3c232f6930eef3431cde76659f04210",
637             "914e57a2745fd475d7b8f982483fe11a05d7b55853239112d5ae99616c718b3c" +
638             "4a0c2d05e3ca1df509614c0fe051b414d404149ec422e0998e192e51518518c4" +
639             "b8acd9e3e3ff9f3b4ef931d3052755785d38e75821ceefa7da0bfe3f1fb2dc6d" +
640             "738e2a2332e53ce77d44547621bb7aa724dd8805c7c795088db865d6b13d9b3e" +
641             "8acec846efb072d105ab6e599f8292a7601087e0ba13af9f503dcfd426e26e4d" +
642             "fb22bf5a1ff1a82d67d9bd8871e6adc17aa39d221f2865f81da9ed566192c269" +
643             "3c85f0442924e603b9ae54b88dd0f21e92eedc40c08dd484c552e297894eeee8" +
644             "b5acc91d5ae16f56257bb0836b48e1a8fa72e83a8b10b7026a7f466c8b08eac5" +
645             "4359b70e639117cf688e263b891f004db94d77941380f3ab0559538c9398c859" +
646             "b76d2bbcd6b635e753160583e7adc263097a80520d003514e134a21597c1ec57" +
647             "55da3a70acc6951b4d4d81e98b9eb962d9e3bc37d5e8ebd61e2a3f61cc452a65" +
648             "56571e12c190d4e3d0f8cc61ffcb60324b4a6987e7375a832ff807682e0b4595" +
649             "66ef1f765638f3d2e837ed43ce2c1c7837f271c866908d865c3d9174fd4f8056" +
650             "265abfb88fbc207db7a12c0a0ad035e5a728725e98cb682d41fd0bcf3aef2fd7" +
651             "ab261727f310fc7cf3b34286c9e9ee235995315167191f3b4d77e5642fb57dbd" +
652             "fdb5ccadefc5d03866918ab1a3eff54b405d8946e2b0c2fa444d1b2be4c3d41d" +
653             "990515e7534190d66d10e38c36c5d3df0315db85ba10c924bef97d1faa07a5f8" +
654             "f04998a7d38689237a1912bea3f821357d8383d7c5cfa66ba5965b5a94bb702c" +
655             "e6583e59879021139355c5b90e0f9cd13b34f3357ffde404bbf34c97f9fd55b5" +
656             "53e42d8a6b370eded02c8a5221e15db701da56918412520e12fd1ef9f4748647" +
657             "858488d5e0abd5b9e01457768907e1d24581f9591771304192711292e4025fce" +
658             "bd92adb2297e9496852f80bd78578bbdb292ca209f7584ff76e9eb66ec8a111e" +
659             "add30dc7ef364c4f1339312f226fe0cfa7a5b1602417e469cf2c8e3874c51232" +
660             "00f2d90dbe7f3c3ff5c6c6484052a80eb6229a6ed6176ad600da185da624bea6",
661             "c1de44dd8ea245ca43e5587460feb514");
662     }
663 }