`AICH` redundant calculation and optimization

[Fd929c2CE5fA]

First of all, thank you for your implementation of AICH, which helped me to understand the algorithm.

I'm not a C/C++ language expert, but because the algorithm lacks good specifications, I have to refer to some code implementations.

I accidentally discovered something interesting while debugging, that is, the RHash implementation appears to calculate the Block-Hash-Tree twice (as LEFT_BRANCH and RIGHT_BRANCH) in all parts except the first and last part.

I did not fully understand all the code logic, but I guess it might be as a streaming calculation, it is designed as is to pick the correct HASH value from it when calculate the FULL_TREE in the end.

Reading the code seems to be true:

RHash/librhash/aich.c

Lines 297 to 307 in e5b0cb6

	/* small optimization: skip a left-branch-hash for the last chunk */
	if (!(type & AICH_PROCESS_FINAL_BLOCK) || ctx->chunks_count == 0) {
	/* calculate a tree hash to be used in left branch */
	rhash_aich_hash_tree(ctx, pair[1], AICH_HASH_LEFT_BRANCH);
	}
	/* small optimization: skip right-branch-hash for the very first chunk */
	if (ctx->chunks_count > 0) {
	/* calculate a tree hash to be used in right branch */
	rhash_aich_hash_tree(ctx, pair[0], AICH_HASH_RIGHT_BRANCH);
	}

The design here is probably save memory usage, that is, whenever the full 53 blocks are obtained, the Part-Hash is calculated immediately, I'm not sure whether the memory footprint of the 53 blocks of Hash is then released.

In any case, based on my own implementation, I find this seems like a trade-off that is not worth it.

Let's assume we want to hash a 100GB file, based on the fact that the result of SHA1 takes up 20 bytes and the size of each block is 184320 bytes, we can get that caching the full block hashes set requires about 11MB of memory. (100 * 1000 / 184320 * 20 ≈ 10.85MB)

This seems trivial for most modern devices. But performing twice Block-Hash-Tree calculations on almost all parts, where the result of one will not end up being used, seems like an unnecessary and considerable waste.

So I think delaying Block-Hash-Tree calculation until all blocks are hashed and only performing necessary calculations based on tree branches is a feasible optimization method. It would be beneficial for most devices and significantly reduce the carbon footprint.

Of course, perhaps on devices with, say, only 32MB of RAM, this might be an issue. Maybe make available memory determinations?

Finally, thank you again for developing the tool, in addition to helping me understand the algorithm, I found it useful in other ways. ❤️🙏

[Fd929c2CE5fA]

RHash/librhash/aich.c

Lines 53 to 63 in e5b0cb6

	/*
	* AICH algorithm could be implemented a bit faster if it knows
	* a hashed message size beforehand. It would allow
	* to build balanced tree while hashing the message.
	*
	* This AICH implementation works with unknown
	* message size like other well-known hash algorithms.
	* So, it just stores sha1 hashes and builds balanced tree
	* only on the last step, when the full message processed
	* and its size got to be known.
	*/

In addition, for file input instead of STDIN, the file size should be obtained in advance, so it is also feasible to build a complete balance tree in advance and perform streaming calculations.

But perhaps distinguishing between different scenarios only adds unnecessary complexity.