Developers.Hash.TigerTree.Math

Tree Math

Here are the variables.

defined hashsize: the size of each hash in the tree, 24 bytes minblocksize: the file gets cut into blocks of this size, the last one may be smaller, 1024 bytes

input filesize: the total size in bytes of the file maxheight: don't make a tree taller than this number

output blocks: the number of blocks the file got cut into blocksize: the maximum size of each block height: the number of different levels the tree has hashes on hashes: the number of hashes in the tree treesize: the size in bytes of the tree

minblocksize, filesize, maxheight -> blocks, blocksize, height, hashes

<source lang="c"> // Takes the minimum block size, the file size, and the maximum tree height we want // Chooses a block size that will generate a short enough tree // Writes blocks, blocksize, height, and the number of hashes in the tree void TreeMath3(int minblocksize, int filesize, int maxheight, int& blocks, int& blocksize, int& height, int& hashes) {

// Start out with the minimum block size blocksize = minblocksize;

// Loop to try out bigger and bigger block sizes until we get a tree short enough while (true) {

// Find out how many blocks of that size the file would get cut into TreeMath2(filesize, blocksize, blocks); // Sets blocks

// See how tall the tree would be with that block size TreeMath(blocks, height, hashes);

// If this tree isn't too high, we're done if (height <= maxheight) break;

// Double the block size and try again to get a shorter tree blocksize *= 2; } } </source>

blocks -> height, hashes

<source lang="c"> // Takes the number of blocks in a file // Computes how many nodes the TigerTree above it would have, and how high it will be void TreeMath(int blocks, int& height, int& hashes) {

// Start by counting the root height = hashes = 1;

// Loop once for each row in the tree, bottom to top while (blocks > 1) {

// Count this row height++; // The tree is one row higher because of this row hashes += blocks; // Add the number of nodes in this row to the total

// Calculate how many hashes there are in the row above this one if (blocks % 2) blocks = [[blocks - 1) / 2) + 1; // The odd hash is passed up else blocks = blocks / 2; // Pairs of hashes are combined } } </source>

hashes, hashsize -> treesize

<source lang="c"> treesize = hashes * hashsize; </source>

filesize, blocksize -> blocks

<source lang="c"> // Takes the size of the file in bytes and the size of the blocks to cut it into // Computes how many blocks there will be void TreeMath2(int filesize, int blocksize, int& blocks) {

// Divide to determine how many full blocks the file holds blocks = filesize / blocksize;

// If the end of the file has a remainder portion, it gets its own block at the end if (filesize % blocksize) blocks++; } </source>