1<?php
2/*
3 * Copyright 2008-2010 GuardTime AS
4 *
5 * This file is part of the GuardTime PHP SDK.
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 *     http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20/**
21 * @package tsp
22 */
23
24/**
25 * Hash chain object used to link timestamps to publication.
26 *
27 * Hash chain is a sequence of entries (links), each containing
28 * <ul>
29 * <li> hash algorithm identifier;
30 * <li> a sibling hash value;
31 * <li> concatenation direction indicator;
32 * <li> level restriction (limiting the number of preceding steps) of this computation step.
33 * </ul>
34 *
35 * Hash chain entries are presented as GTHashEntry objects.
36 *
37 * @package tsp
38 */
39class GTHashChain {
40
41    private $entries = array();
42
43    /**
44     * Constructs a new GTHashChain instance.
45     *
46     * @throws GTException
47     * @param  array $bytes hash chain bytes
48     * @param  bool $checkLevel whether to check that level bytes are in increasing order
49     */
50    private function __construct(array $bytes, $checkLevel) {
51
52        if (empty($bytes)) {
53            throw new GTException("parameter bytes is required");
54        }
55
56        if (!is_array($bytes)) {
57            throw new GTException("parameter bytes must be an array of bytes");
58        }
59
60        $previousLevel = -1;
61
62        for ($i = 0; $i < count($bytes);) {
63
64            $algorithm = GTHashAlgorithm::getByGtid($bytes[$i++]);
65
66            if ($i >= count($bytes)) {
67                throw new GTException("Invalid chain: not enough bytes");
68            }
69
70            $direction = $bytes[$i++];
71
72            if ($i >= count($bytes)) {
73                throw new GTException("Invalid chain: not enough bytes");
74            }
75
76            if ($direction != 0 && $direction != 1) {
77                throw new GTException("invalid hash step direction: {$direction}");
78            }
79
80            $siblingAlgorithm = GTHashAlgorithm::getByGtid($bytes[$i++]);
81            $siblingHash = new GTDataHash($siblingAlgorithm, array_slice($bytes, $i, $siblingAlgorithm->getLength()));
82
83            $i += $siblingAlgorithm->getLength();
84
85            if ($i >= count($bytes)) {
86                throw new GTException("Invalid chain: not enough bytes");
87            }
88            $level = $bytes[$i++] & 0xFF;
89
90            if ($checkLevel && $previousLevel >= $level) {
91                throw new GTException("invalid hash step level: {$level}");
92            }
93            $previousLevel = $level;
94
95            array_push($this->entries, new GTHashEntry($algorithm, $direction, $siblingHash, $level));
96        }
97
98    }
99
100    /**
101     * Computes the result of passing the given bytes through this hash chain.
102     *
103     * @throws GTException
104     * @param  array $bytes bytes to compute chain output for
105     * @return array chain output, the final hash value
106     */
107    public function computeOutput(array $bytes) {
108
109        if (empty($bytes)) {
110            throw new GTException("parameter bytes is required");
111        }
112
113        if (!is_array($bytes)) {
114            throw new GTException("parameter bytes must be an array of bytes");
115        }
116
117        $output = $bytes;
118
119        foreach ($this->entries as $entry) {
120            $output = $entry->computeOutput($output);
121        }
122
123        return $output;
124
125    }
126
127    /**
128     * Checks that past entries match in this history chain and the other provided history chain.
129     *
130     * Past history chain entries are those which have a 0 direction.
131     *
132     * @param  GTHashChain $hashChain history chain to compare this chain entries with
133     * @return bool true if all past entries match, false otherwise
134     */
135    public function checkPastEntries(GTHashChain $hashChain) {
136
137        $iter1 = new ArrayIterator($this->entries);
138        $iter2 = new ArrayIterator($hashChain->entries);
139
140        while ($iter1->valid()) {
141
142            $entry = null;
143
144            do {
145                $entry = $iter1->current();
146                $iter1->next();
147            } while ($iter1->valid() && $entry->getDirection() == 1);
148
149            if ($entry->getDirection() == 0 && !$iter2->valid()) {
150                return false;
151            }
152
153            $other = null;
154
155            do {
156                $other = $iter2->current();
157                $iter2->next();
158            } while ($iter2->valid() && $other->getDirection() == 1);
159
160            if ($entry->getDirection() == 1 && $other->getDirection() == 1) {
161                return true;
162            } else if ($entry != $other) {
163                return false;
164            }
165        }
166
167        return true;
168
169    }
170
171    /**
172     * Computes location ID of this chain.
173     *
174     * This computation is only sensible for location chains.
175     *
176     * @return GTBigInteger location ID computed on this location chain
177     */
178    public function computeLocationId() {
179
180        // Skip: machine bits + slot bits
181        $topSkip = 3 + 3;
182        $nationalSkip = 3 + 2;
183        $stateSkip = 2 + 2;
184
185        // Level: depth + machine bits + slot bits - 2
186        $topLevel = 60 + $topSkip - 2;
187        $nationalLevel = 39 + $nationalSkip - 2;
188        $stateLevel = 19 + $stateSkip - 2;
189
190        $locationId = new GTBigInteger(0);
191
192        $i = count($this->entries) - 1;
193        $i--; // skip hasher bit
194
195        // calculate national id
196        $idNational = 0;
197
198        while (true) {
199            $entry = $this->entries[$i--];
200
201            if ($entry->getLevel() > $topLevel) {
202                $idNational = 2 * $idNational + (1 - $entry->getDirection());
203
204            } else {
205                break;
206
207            }
208        }
209
210        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idNational));
211
212        // Skip machine and slot bits of top-level aggregator
213        $i -= $topSkip;
214
215        // Calculate state ID
216        $idState = 0;
217
218        while (true) {
219            $entry = $this->entries[$i--];
220
221            if ($entry->getLevel() > $nationalLevel) {
222                $idState = 2 * $idState + (1 - $entry->getDirection());
223
224            } else {
225                break;
226            }
227        }
228
229        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idState));
230
231        // Skip machine and slot bits of national-level aggregator
232        $i -= $nationalSkip;
233
234        // Calculate local ID
235        $idLocal = 0;
236
237        while (true) {
238            $entry = $this->entries[$i--];
239
240            if ($entry->getLevel() > $stateLevel) {
241                $idLocal = 2 * $idLocal + (1 - $entry->getDirection());
242
243            } else {
244                break;
245            }
246
247        }
248
249        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idLocal));
250
251        // Skip machine and slot bits of state-level aggregator
252        $i -= $stateSkip;
253
254        // Calculate client ID
255        $idClient = 0;
256
257        while ($i > 0) {
258            $entry = $this->entries[$i--];
259            $idClient = 2 * $idClient + (1 - $entry->getDirection());
260        }
261
262        $locationId = $locationId->shiftLeft(16)->bitOr(new GTBigInteger($idClient));
263
264        return $locationId;
265    }
266
267    /**
268     * Computes history ID of this hash chain.
269     *
270     * History ID is the number of seconds from 1970-01-01 00:00:00 UTC to
271     * the time corresponding  to the starting position of this hash chain
272     * in the GuardTime calendar tree.
273     *
274     * This computation is only sensible for history chains.
275     *
276     * @param  string $publicationId history ID corresponding to the root of the
277     * calendar tree from which the history chain was extracted.
278     *
279     * @return GTBigInteger history ID computed on this history chain
280     */
281    public function computeHistoryId($publicationId) {
282
283        $N = $publicationId->add(new GTBigInteger(1));
284        $m = 0; // number of 1 bits in N
285
286        $bits = $N->toBits();
287
288        for ($i = 0; $i < strlen($bits); $i++) {
289            if ($bits{$i} == '1') {
290                $m++;
291            }
292        }
293
294        $hashChainLength = count($this->entries);
295        $hashChainDirs = new GTBigInteger(0);
296
297        $i = $hashChainLength;
298
299        while ($i > 0) {
300            $i--;
301            $hashChainDirs = $hashChainDirs->shiftLeft(1);
302
303            $entry = $this->entries[$i];
304
305            if ($entry->getDirection() == 1) {
306                $hashChainDirs = $hashChainDirs->bitOr(new GTBigInteger(1));
307            }
308        }
309
310        // number of leading zeroes in $hashChainDirs
311        $bits = $hashChainDirs->toBits();
312
313        // pad to 64 bit
314        while (strlen($bits) % 64 != 0) {
315            $bits = '0' . $bits;
316        }
317
318        $z = 0;
319
320        for ($i = 0; $i < strlen($bits); $i++) {
321            if ($bits{$i} == '0') {
322                $z++;
323            } else {
324                break;
325            }
326        }
327
328        // Get leading zeros within `hashChainLen` number of last bits
329        $z = $z - (64 - $hashChainLength);
330
331        $count = 0;
332
333        if ($z + 1 > $m) {
334            $hashChainLength -= $m - 1;
335            $count = 1;
336        } else {
337            $hashChainLength -= $z + 1;
338            $count = $m - $z;
339        }
340
341        $mask = new GTBigInteger(0x1);
342        $zero = new GTBigInteger(0x0);
343
344        $i = 0;
345
346        while ($i < $count && $N->comp($zero) > 0) {
347
348            if ($N->bitAnd($mask)->comp($mask) == 0) {
349                $N = $N->bitXOr($mask);
350                $i++;
351            }
352
353            $mask = $mask->shiftLeft(1);
354        }
355
356        $hashChainDirs = $hashChainDirs->bitNot();
357
358        $mask = new GTBigInteger(0x1);
359        $n = new GTBigInteger(0);
360
361        $i = 0;
362
363        while ($i < $hashChainLength) {
364
365            if ($hashChainDirs->bitAnd($mask)->comp($mask) == 0) {
366                $n = $n->add($mask);
367            }
368
369            $mask = $mask->shiftLeft(1);
370            $i++;
371        }
372
373        $result = new GTBigInteger($n);
374        $result = $result->add($N);
375
376        return $result;
377
378    }
379
380    /**
381     * Builds a new location hash chain out of the specified hash chain bytes.
382     *
383     * Hash chain bytes is a binary representation of a hash chain extracted
384     * from the timestamp.
385     *
386     * @static
387     * @param  array $bytes byte array containing the hash chain bytes
388     * @return GTHashChain hash chain object
389     */
390    public static function getLocationInstance(array $bytes) {
391        return new GTHashChain($bytes, true);
392    }
393
394    /**
395     * Builds a new history hash chain out of the specified hash chain bytes.
396     *
397     * Hash chain bytes is a binary representation of a hash chain extracted
398     * from the timestamp.
399     *
400     * @static
401     * @param  array $bytes byte array containing the hash chain bytes
402     * @return GTHashChain hash chain object
403     */
404    public static function getHistoryInstance(array $bytes) {
405        return new GTHashChain($bytes, false);
406    }
407}
408
409?>
410