4.2 H3

This section gives an example of computing the H3 hashes of a sequence of 11 bytes of data with a windowSize of 4.

First, H3 is required to determine the appropriate shift_amount for a 4-byte windowSize. Applying the algorithm in section 3.1.5.1.1 yields a shift_amount of eight.

hash_value is initialized to 0x00, and the H3 algorithm starts at the first data byte. Recall that for the purposes of H3, all data bytes before the beginning of the file are treated as having 0 value. Therefore, in the example that follows, this is rotate_bits_left(0 XOR H3 Table[0] XOR H3 Table[0x48],8). Looking into the H3 table yields H3 Table[0] = 0x5e3f7c48 and H3 Table[0x48] = 0x3d519a77. Computing the XOR yields 0x636ee63f, and rotating left 8 bits yields 0x6ee63f63, which is the first H3 value, v0.

To compute v1, repeat the procedure using v0 as the initial hash_value; that is, rotate_bits_left(0x6ee63f63 XOR H3 Table[0] XOR H3 Table[0x65],8). H3 Table[0] = 0x5e3f7c48 and H3 Table[0x65] = 0x824fdbe8, so the result of the XOR is 0xb29698c3. Rotating yields v1 = 0x9698c3b2.

Because of the way shift_amount is computed, (windowSize * shift_amount) MODULUS 32 = 0. Therefore, when a byte is at the trailing edge of the window, the XOR with its corresponding table value is in the same position as when the table value was XOR'd in when it was at the leading edge. Furthermore, for all a, a XOR a = 0, so the second XOR cancels out the effect of the first one. Therefore, the H3 value for a window does not depend on any bytes outside the window, and H3 is a hash function.

The following diagram illustrates the computation of H3 hashes.

Figure 7: H3 hash computation