title: Tree Hash: How to verify if a range is tree-hash-aligned?
body: <p>"Tree Hash" is a concept similar to Merkle Tree/Tiger Hash Tree used by Amazon Glacier to verify the data integrity of a subsets of a given datastream.</p>
  
  <p>In order to receive tree hashes from Amazon Glacier when retrieving data, the specified byte range has to be "tree hash aligned".</p>
  
  <p><a href="http://docs.aws.amazon.com/amazonglacier/latest/dev/checksum-calculations-range.html" rel="nofollow">The concept of "tree hash aligned" is described here.</a></p>
  
  <p>Quoting from the developer documentation:</p>
  
  <blockquote>
    <p>A range [A, B] is tree-hash aligned with respect to an archive if and only if when a new tree hash is built over [A, B], the root of the tree hash of that range is equivalent to a node in the tree hash of the whole archive. [...]</p>
    
    <p>Consider [P, Q) as the range query for an archive of N megabytes (MB) and P and Q are multiples of one MB. Note that the actual inclusive range is [P MB, Q MB – 1 byte], but for simplicity, we show it as [P, Q). With these considerations, then</p>
    
    <ul>
    <li>If P is an odd number, there is only one possible tree-hash aligned range—that is [P, P + 1 MB).</li>
    <li>If P is an even number and k is the maximum number, where P can be written as 2k * X, then there are at most k tree-hash aligned ranges that start with P. X is an integer greater than 0. The tree-hash aligned ranges fall in the following categories:
    
    <ul>
    <li>For each i, where (0 &lt;= i &lt;= k) and where P + 2i &lt; N, then [P, Q + 2i) is a tree-hash aligned range.</li>
    <li>P = 0 is the special case where A = 2[lgN]*0</li>
    </ul></li>
    </ul>
  </blockquote>
  
  <p>Now the question: How do I verify programmatically if a given range [startByte, endByte] is tree-hash-aligned? Programming language does not matter.</p>
  
  <p>Test cases:</p>
  
  <pre><code>[0,0) =&gt; true
  [0,1) =&gt; true
  [0,2) =&gt; false
  [0,3) =&gt; true
  [1,2) =&gt; false
  [4,5) =&gt; true
  </code></pre>