Repository navigation
Expand file tree
/
Copy pathKerl.java
More file actions
354 lines (288 loc) · 10.5 KB
/
Copy pathKerl.java
File metadata and controls
354 lines (288 loc) · 10.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
package jota.pow;
import jota.utils.Pair;
import org.bouncycastle.jcajce.provider.digest.Keccak;
import java.util.LinkedHashSet;
import java.util.Set;
public class Kerl extends JCurl {
private static final int HASH_LENGTH = 243;
private static final int BIT_HASH_LENGTH = 384;
private static final int BYTE_HASH_LENGTH = BIT_HASH_LENGTH / 8;
private static final int RADIX = 3;
private static final int MAX_TRIT_VALUE = (RADIX - 1) / 2, MIN_TRIT_VALUE = -MAX_TRIT_VALUE;
private final Keccak.Digest384 keccak;
private byte[] byte_state;
private int[] trit_state;
private static final int[] HALF_3 = new int[]{
0xa5ce8964, 0x9f007669, 0x1484504f, 0x3ade00d9, 0x0c24486e, 0x50979d57, 0x79a4c702, 0x48bbae36, 0xa9f6808b, 0xaa06a805, 0xa87fabdf, 0x5e69ebef};
private static int BYTE_LENGTH = 48;
private static int INT_LENGTH = BYTE_LENGTH / 4;
Kerl() {
super();
this.keccak = new Keccak.Digest384();
this.byte_state = new byte[BYTE_HASH_LENGTH];
this.trit_state = new int[HASH_LENGTH];
}
private static final long toUnsignedLong(int i) {
return i & 0xFFFFFFFFL;
}
private static int toUnsignedInt(byte x) {
return x & 0xff;
}
private static int sum(int[] toSum) {
int sum = 0;
for (int i = 0; i < toSum.length; i++) {
sum += toSum[i];
}
return sum;
}
public static byte[] convertTritsToBytes(final int[] trits) {
if (trits.length != Kerl.HASH_LENGTH) {
throw new RuntimeException("Input trits length must be " + Kerl.HASH_LENGTH + "in length");
}
int[] base = new int[INT_LENGTH];
Set<Integer> setUniqueNumbers = new LinkedHashSet<Integer>();
for (int x : trits) {
setUniqueNumbers.add(x);
}
if (setUniqueNumbers.size() == 1 && setUniqueNumbers.contains(-1)) {
base = HALF_3.clone();
bigint_not(base);
bigint_add(base, 1);
} else {
int size = INT_LENGTH;
for (int i = Kerl.HASH_LENGTH - 1; i-- > 0; ) {
{ // Multiply by radix
int sz = size;
int carry = 0;
for (int j = 0; j < sz; j++) {
// full_mul
long v = Kerl.toUnsignedLong(base[j]) * (Kerl.toUnsignedLong(RADIX)) + Kerl.toUnsignedLong(carry);
carry = (int) ((v >> Integer.SIZE) & 0xFFFFFFFF);
base[j] = (int) (v & 0xFFFFFFFF);
}
if (carry > 0) {
base[sz] = carry;
size += 1;
}
}
final int in = trits[i] + 1;
{ // Add
int sz = bigint_add(base, in);
if (sz > size) {
size = sz;
}
}
}
if (sum(base) != 0) {
if (bigint_cmp(HALF_3, base) <= 0) {
// base is >= HALF_3.
// just do base - HALF_3
base = bigint_sub(base, HALF_3);
} else {
// we don't have a wrapping sub.
// so we need to be clever.
base = bigint_sub(HALF_3, base);
bigint_not(base);
bigint_add(base, 1);
}
}
}
byte[] out = new byte[BYTE_LENGTH];
for (int i = 0; i < INT_LENGTH; i++) {
out[i * 4 + 0] = (byte) ((base[INT_LENGTH - 1 - i] & 0xFF000000) >> 24);
out[i * 4 + 1] = (byte) ((base[INT_LENGTH - 1 - i] & 0x00FF0000) >> 16);
out[i * 4 + 2] = (byte) ((base[INT_LENGTH - 1 - i] & 0x0000FF00) >> 8);
out[i * 4 + 3] = (byte) ((base[INT_LENGTH - 1 - i] & 0x000000FF) >> 0);
}
return out;
}
public static int[] convertBytesToTrits(byte[] bytes) {
int[] base = new int[INT_LENGTH];
int[] out = new int[243];
out[Kerl.HASH_LENGTH - 1] = 0;
if (bytes.length != BYTE_LENGTH) {
throw new RuntimeException("Input base must be " + BYTE_LENGTH + " in length");
}
for (int i = 0; i < INT_LENGTH; i++) {
base[INT_LENGTH - 1 - i] = Kerl.toUnsignedInt(bytes[i * 4]) << 24;
base[INT_LENGTH - 1 - i] |= Kerl.toUnsignedInt(bytes[i * 4 + 1]) << 16;
base[INT_LENGTH - 1 - i] |= Kerl.toUnsignedInt(bytes[i * 4 + 2]) << 8;
base[INT_LENGTH - 1 - i] |= Kerl.toUnsignedInt(bytes[i * 4 + 3]);
}
if (bigint_cmp(base, HALF_3) == 0) {
int val = 0;
if (base[0] > 0) {
val = -1;
} else if (base[0] < 0) {
val = 1;
}
for (int i = 0; i < Kerl.HASH_LENGTH - 1; i++) {
out[i] = val;
}
} else {
boolean flipTrits = false;
// See if we have a positive or negative two's complement number.
if (Kerl.toUnsignedLong(base[INT_LENGTH - 1]) >> 31 != 0) {
// negative value.
bigint_not(base);
if (bigint_cmp(base, HALF_3) > 0) {
base = bigint_sub(base, HALF_3);
flipTrits = true;
} else {
bigint_add(base, 1);
base = bigint_sub(HALF_3, base);
}
} else {
// positive. we need to shift right by HALF_3
base = bigint_add(HALF_3, base);
}
int size = INT_LENGTH;
int remainder = 0;
for (int i = 0; i < Kerl.HASH_LENGTH - 1; i++) {
{ //div_rem
remainder = 0;
for (int j = size - 1; j >= 0; j--) {
long lhs = (Kerl.toUnsignedLong(remainder) << 32) | Kerl.toUnsignedLong(base[j]);
long rhs = Kerl.toUnsignedLong(RADIX);
int q = (int) (lhs / rhs);
int r = (int) (lhs % rhs);
base[j] = q;
remainder = r;
}
}
out[i] = remainder - 1;
}
if (flipTrits) {
for (int i = 0; i < out.length; i++) {
out[i] = -out[i];
}
}
}
return out;
}
private static void bigint_not(int[] base) {
for (int i = 0; i < base.length; i++) {
base[i] = ~base[i];
}
}
private static int bigint_add(int[] base, final int rh) {
Pair<Integer, Boolean> res = full_add(base[0], rh, false);
base[0] = res.low;
int j = 1;
while (res.hi) {
res = full_add(base[j], 0, true);
base[j] = res.low;
j += 1;
}
return j;
}
private static int[] bigint_add(final int[] lh, final int[] rh) {
int[] out = new int[INT_LENGTH];
boolean carry = false;
Pair<Integer, Boolean> ret;
for (int i = 0; i < INT_LENGTH; i++) {
ret = full_add(lh[i], rh[i], carry);
out[i] = ret.low;
carry = ret.hi;
}
if (carry) {
throw new RuntimeException("Exceeded max value.");
}
return out;
}
private static int bigint_cmp(final int[] lh, final int[] rh) {
for (int i = INT_LENGTH - 1; i >= 0; i--) {
int ret = Long.compare(Kerl.toUnsignedLong(lh[i]), Kerl.toUnsignedLong(rh[i]));
if (ret != 0) {
return ret;
}
}
return 0;
}
private static int[] bigint_sub(final int[] lh, final int[] rh) {
int[] out = new int[INT_LENGTH];
boolean noborrow = true;
Pair<Integer, Boolean> ret;
for (int i = 0; i < INT_LENGTH; i++) {
ret = full_add(lh[i], ~rh[i], noborrow);
out[i] = ret.low;
noborrow = ret.hi;
}
if (!noborrow) {
throw new RuntimeException("noborrow");
}
return out;
}
private static Pair<Integer, Boolean> full_add(final int ia, final int ib, final boolean carry) {
long a = Kerl.toUnsignedLong(ia);
long b = Kerl.toUnsignedLong(ib);
long v = a + b;
long l = v >> 32;
long r = v & 0xFFFFFFFF;
boolean carry1 = l != 0;
if (carry) {
v = r + 1;
}
l = (v >> 32) & 0xFFFFFFFF;
r = v & 0xFFFFFFFF;
boolean carry2 = l != 0;
return new Pair<>((int) r, carry1 || carry2);
}
@Override
public Kerl reset() {
this.keccak.reset();
return this;
}
@Override
public Kerl absorb(final int[] trits, int offset, int length) {
if (length % 243 != 0) throw new RuntimeException("Illegal length: " + length);
do {
//copy trits[offset:offset+length]
System.arraycopy(trits, offset, trit_state, 0, HASH_LENGTH);
//convert to bits
trit_state[HASH_LENGTH - 1] = 0;
byte[] bytes = convertTritsToBytes(trit_state);
//run keccak
keccak.update(bytes);
offset += HASH_LENGTH;
} while ((length -= HASH_LENGTH) > 0);
return this;
}
@Override
public int[] squeeze(final int[] trits, int offset, int length) {
if (length % 243 != 0) throw new RuntimeException("Illegal length: " + length);
do {
byte_state = this.keccak.digest();
//convert to trits
trit_state = convertBytesToTrits(byte_state);
//copy with offset
trit_state[HASH_LENGTH - 1] = 0;
System.arraycopy(trit_state, 0, trits, offset, HASH_LENGTH);
//calculate hash again
for (int i = byte_state.length; i-- > 0; ) {
byte_state[i] = (byte) (byte_state[i] ^ 0xFF);
}
keccak.update(byte_state);
offset += HASH_LENGTH;
} while ((length -= HASH_LENGTH) > 0);
return trits;
}
/**
* Squeezes the specified trits.
*
* @param trits The trits.
* @return The squeezes trits.
*/
public int[] squeeze(final int[] trits) {
return squeeze(trits, 0, trits.length);
}
/**
* Clones this instance.
*
* @return A new instance.
*/
@Override
public Kerl clone() {
return new Kerl();
}
}