* hash algorithm identifier;
* a sibling hash value;
* concatenation direction indicator;
* level restriction (limiting the number of preceding steps) of this computation step.
*
*
* Hash chain entries are presented as GTHashEntry objects.
*
* @package tsp
*/
class GTHashChain {
private $entries = array();
/**
* Constructs a new GTHashChain instance.
*
* @throws GTException
* @param array $bytes hash chain bytes
* @param bool $checkLevel whether to check that level bytes are in increasing order
*/
private function __construct(array $bytes, $checkLevel) {
if (empty($bytes)) {
throw new GTException("parameter bytes is required");
}
if (!is_array($bytes)) {
throw new GTException("parameter bytes must be an array of bytes");
}
$previousLevel = -1;
for ($i = 0; $i < count($bytes);) {
$algorithm = GTHashAlgorithm::getByGtid($bytes[$i++]);
if ($i >= count($bytes)) {
throw new GTException("Invalid chain: not enough bytes");
}
$direction = $bytes[$i++];
if ($i >= count($bytes)) {
throw new GTException("Invalid chain: not enough bytes");
}
if ($direction != 0 && $direction != 1) {
throw new GTException("invalid hash step direction: {$direction}");
}
$siblingAlgorithm = GTHashAlgorithm::getByGtid($bytes[$i++]);
$siblingHash = new GTDataHash($siblingAlgorithm, array_slice($bytes, $i, $siblingAlgorithm->getLength()));
$i += $siblingAlgorithm->getLength();
if ($i >= count($bytes)) {
throw new GTException("Invalid chain: not enough bytes");
}
$level = $bytes[$i++] & 0xFF;
if ($checkLevel && $previousLevel >= $level) {
throw new GTException("invalid hash step level: {$level}");
}
$previousLevel = $level;
array_push($this->entries, new GTHashEntry($algorithm, $direction, $siblingHash, $level));
}
}
/**
* Computes the result of passing the given bytes through this hash chain.
*
* @throws GTException
* @param array $bytes bytes to compute chain output for
* @return array chain output, the final hash value
*/
public function computeOutput(array $bytes) {
if (empty($bytes)) {
throw new GTException("parameter bytes is required");
}
if (!is_array($bytes)) {
throw new GTException("parameter bytes must be an array of bytes");
}
$output = $bytes;
foreach ($this->entries as $entry) {
$output = $entry->computeOutput($output);
}
return $output;
}
/**
* Checks that past entries match in this history chain and the other provided history chain.
*
* Past history chain entries are those which have a 0 direction.
*
* @param GTHashChain $hashChain history chain to compare this chain entries with
* @return bool true if all past entries match, false otherwise
*/
public function checkPastEntries(GTHashChain $hashChain) {
$iter1 = new ArrayIterator($this->entries);
$iter2 = new ArrayIterator($hashChain->entries);
while ($iter1->valid()) {
$entry = null;
do {
$entry = $iter1->current();
$iter1->next();
} while ($iter1->valid() && $entry->getDirection() == 1);
if ($entry->getDirection() == 0 && !$iter2->valid()) {
return false;
}
$other = null;
do {
$other = $iter2->current();
$iter2->next();
} while ($iter2->valid() && $other->getDirection() == 1);
if ($entry->getDirection() == 1 && $other->getDirection() == 1) {
return true;
} else if ($entry != $other) {
return false;
}
}
return true;
}
/**
* Computes location ID of this chain.
*
* This computation is only sensible for location chains.
*
* @return GTBigInteger location ID computed on this location chain
*/
public function computeLocationId() {
// Skip: machine bits + slot bits
$topSkip = 3 + 3;
$nationalSkip = 3 + 2;
$stateSkip = 2 + 2;
// Level: depth + machine bits + slot bits - 2
$topLevel = 60 + $topSkip - 2;
$nationalLevel = 39 + $nationalSkip - 2;
$stateLevel = 19 + $stateSkip - 2;
$locationId = new GTBigInteger(0);
$i = count($this->entries) - 1;
$i--; // skip hasher bit
// calculate national id
$idNational = 0;
while (true) {
$entry = $this->entries[$i--];
if ($entry->getLevel() > $topLevel) {
$idNational = 2 * $idNational + (1 - $entry->getDirection());
} else {
break;
}
}
$locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idNational));
// Skip machine and slot bits of top-level aggregator
$i -= $topSkip;
// Calculate state ID
$idState = 0;
while (true) {
$entry = $this->entries[$i--];
if ($entry->getLevel() > $nationalLevel) {
$idState = 2 * $idState + (1 - $entry->getDirection());
} else {
break;
}
}
$locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idState));
// Skip machine and slot bits of national-level aggregator
$i -= $nationalSkip;
// Calculate local ID
$idLocal = 0;
while (true) {
$entry = $this->entries[$i--];
if ($entry->getLevel() > $stateLevel) {
$idLocal = 2 * $idLocal + (1 - $entry->getDirection());
} else {
break;
}
}
$locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idLocal));
// Skip machine and slot bits of state-level aggregator
$i -= $stateSkip;
// Calculate client ID
$idClient = 0;
while ($i > 0) {
$entry = $this->entries[$i--];
$idClient = 2 * $idClient + (1 - $entry->getDirection());
}
$locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idClient));
return $locationId;
}
/**
* Computes history ID of this hash chain.
*
* History ID is the number of seconds from 1970-01-01 00:00:00 UTC to
* the time corresponding to the starting position of this hash chain
* in the GuardTime calendar tree.
*
* This computation is only sensible for history chains.
*
* @param string $publicationId history ID corresponding to the root of the
* calendar tree from which the history chain was extracted.
*
* @return GTBigInteger history ID computed on this history chain
*/
public function computeHistoryId($publicationId) {
$N = $publicationId->add(new GTBigInteger(1));
$m = 0; // number of 1 bits in N
$bits = $N->toBits();
for ($i = 0; $i < strlen($bits); $i++) {
if ($bits{$i} == '1') {
$m++;
}
}
$hashChainLength = count($this->entries);
$hashChainDirs = new GTBigInteger(0);
$i = $hashChainLength;
while ($i > 0) {
$i--;
$hashChainDirs = $hashChainDirs->shiftLeft(1);
$entry = $this->entries[$i];
if ($entry->getDirection() == 1) {
$hashChainDirs = $hashChainDirs->bitOr(new GTBigInteger(1));
}
}
// number of leading zeroes in $hashChainDirs
$bits = $hashChainDirs->toBits();
// pad to 64 bit
while (strlen($bits) % 64 != 0) {
$bits = '0' . $bits;
}
$z = 0;
for ($i = 0; $i < strlen($bits); $i++) {
if ($bits{$i} == '0') {
$z++;
} else {
break;
}
}
// Get leading zeros within `hashChainLen` number of last bits
$z = $z - (64 - $hashChainLength);
$count = 0;
if ($z + 1 > $m) {
$hashChainLength -= $m - 1;
$count = 1;
} else {
$hashChainLength -= $z + 1;
$count = $m - $z;
}
$mask = new GTBigInteger(0x1);
$zero = new GTBigInteger(0x0);
$i = 0;
while ($i < $count && $N->comp($zero) > 0) {
if ($N->bitAnd($mask)->comp($mask) == 0) {
$N = $N->bitXOr($mask);
$i++;
}
$mask = $mask->shiftLeft(1);
}
$hashChainDirs = $hashChainDirs->bitNot();
$mask = new GTBigInteger(0x1);
$n = new GTBigInteger(0);
$i = 0;
while ($i < $hashChainLength) {
if ($hashChainDirs->bitAnd($mask)->comp($mask) == 0) {
$n = $n->add($mask);
}
$mask = $mask->shiftLeft(1);
$i++;
}
$result = new GTBigInteger($n);
$result = $result->add($N);
return $result;
}
/**
* Builds a new location hash chain out of the specified hash chain bytes.
*
* Hash chain bytes is a binary representation of a hash chain extracted
* from the timestamp.
*
* @static
* @param array $bytes byte array containing the hash chain bytes
* @return GTHashChain hash chain object
*/
public static function getLocationInstance(array $bytes) {
return new GTHashChain($bytes, true);
}
/**
* Builds a new history hash chain out of the specified hash chain bytes.
*
* Hash chain bytes is a binary representation of a hash chain extracted
* from the timestamp.
*
* @static
* @param array $bytes byte array containing the hash chain bytes
* @return GTHashChain hash chain object
*/
public static function getHistoryInstance(array $bytes) {
return new GTHashChain($bytes, false);
}
}
?>