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
|
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
// public class TreeHashExample {
public class TreeHash {
static final int ONE_MB = 1024 * 1024;
/**
* Compute the Hex representation of the SHA-256 tree hash for the specified
* File
*
* @param args
* args[0]: a file to compute a SHA-256 tree hash for
*/
public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Missing required filename argument");
System.exit(-1);
}
File inputFile = new File(args[0]);
try {
byte[] treeHash = computeSHA256TreeHash(inputFile);
System.out.printf("%s", toHex(treeHash));
} catch (IOException ioe) {
System.err.format("Exception when reading from file %s: %s", inputFile,
ioe.getMessage());
System.exit(-1);
} catch (NoSuchAlgorithmException nsae) {
System.err.format("Cannot locate MessageDigest algorithm for SHA-256: %s",
nsae.getMessage());
System.exit(-1);
}
}
/**
* Computes the SHA-256 tree hash for the given file
*
* @param inputFile
* a File to compute the SHA-256 tree hash for
* @return a byte[] containing the SHA-256 tree hash
* @throws IOException
* Thrown if there's an issue reading the input file
* @throws NoSuchAlgorithmException
*/
public static byte[] computeSHA256TreeHash(File inputFile) throws IOException,
NoSuchAlgorithmException {
byte[][] chunkSHA256Hashes = getChunkSHA256Hashes(inputFile);
return computeSHA256TreeHash(chunkSHA256Hashes);
}
/**
* Computes a SHA256 checksum for each 1 MB chunk of the input file. This
* includes the checksum for the last chunk even if it is smaller than 1 MB.
*
* @param file
* A file to compute checksums on
* @return a byte[][] containing the checksums of each 1 MB chunk
* @throws IOException
* Thrown if there's an IOException when reading the file
* @throws NoSuchAlgorithmException
* Thrown if SHA-256 MessageDigest can't be found
*/
public static byte[][] getChunkSHA256Hashes(File file) throws IOException,
NoSuchAlgorithmException {
MessageDigest md = MessageDigest.getInstance("SHA-256");
long numChunks = file.length() / ONE_MB;
if (file.length() % ONE_MB > 0) {
numChunks++;
}
if (numChunks == 0) {
return new byte[][] { md.digest() };
}
byte[][] chunkSHA256Hashes = new byte[(int) numChunks][];
FileInputStream fileStream = null;
try {
fileStream = new FileInputStream(file);
byte[] buff = new byte[ONE_MB];
int bytesRead;
int idx = 0;
while ((bytesRead = fileStream.read(buff, 0, ONE_MB)) > 0) {
md.reset();
md.update(buff, 0, bytesRead);
chunkSHA256Hashes[idx++] = md.digest();
}
return chunkSHA256Hashes;
} finally {
if (fileStream != null) {
try {
fileStream.close();
} catch (IOException ioe) {
System.err.printf("Exception while closing %s.\n %s", file.getName(),
ioe.getMessage());
}
}
}
}
/**
* Computes the SHA-256 tree hash for the passed array of 1 MB chunk
* checksums.
*
* This method uses a pair of arrays to iteratively compute the tree hash
* level by level. Each iteration takes two adjacent elements from the
* previous level source array, computes the SHA-256 hash on their
* concatenated value and places the result in the next level's destination
* array. At the end of an iteration, the destination array becomes the
* source array for the next level.
*
* @param chunkSHA256Hashes
* An array of SHA-256 checksums
* @return A byte[] containing the SHA-256 tree hash for the input chunks
* @throws NoSuchAlgorithmException
* Thrown if SHA-256 MessageDigest can't be found
*/
public static byte[] computeSHA256TreeHash(byte[][] chunkSHA256Hashes)
throws NoSuchAlgorithmException {
MessageDigest md = MessageDigest.getInstance("SHA-256");
byte[][] prevLvlHashes = chunkSHA256Hashes;
while (prevLvlHashes.length > 1) {
int len = prevLvlHashes.length / 2;
if (prevLvlHashes.length % 2 != 0) {
len++;
}
byte[][] currLvlHashes = new byte[len][];
int j = 0;
for (int i = 0; i < prevLvlHashes.length; i = i + 2, j++) {
// If there are at least two elements remaining
if (prevLvlHashes.length - i > 1) {
// Calculate a digest of the concatenated nodes
md.reset();
md.update(prevLvlHashes[i]);
md.update(prevLvlHashes[i + 1]);
currLvlHashes[j] = md.digest();
} else { // Take care of remaining odd chunk
currLvlHashes[j] = prevLvlHashes[i];
}
}
prevLvlHashes = currLvlHashes;
}
return prevLvlHashes[0];
}
/**
* Returns the hexadecimal representation of the input byte array
*
* @param data
* a byte[] to convert to Hex characters
* @return A String containing Hex characters
*/
public static String toHex(byte[] data) {
StringBuilder sb = new StringBuilder(data.length * 2);
for (int i = 0; i < data.length; i++) {
String hex = Integer.toHexString(data[i] & 0xFF);
if (hex.length() == 1) {
// Append leading zero.
sb.append("0");
}
sb.append(hex);
}
return sb.toString().toLowerCase();
}
}
|