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 util
22 */
23
24/**
25 * BigInteger implementation based on PHP BCMath.
26 *
27 * @link http://www.php.net/manual/en/book.bc.php
28 *
29 * @package util
30 */
31class GTBigInteger {
32
33    /**
34     * Constructs a new instance of GTBigInteger.
35     *
36     * Both negative and positive integers of any size are supported.
37     *
38     * Example:
39     *
40     * <code>
41     * $int1 = new GTBigInteger(4);
42     * $int2 = new GTBigInteger("-12312321351878937123123098123");
43     * $int3 = new GTBigInteger(array(1, 226, 64));
44     * </code>
45     *
46     * @throws GTException
47     * @param  string|int|array $value value as string or integer or byte array
48     */
49    public function __construct($value) {
50
51        if ($value === null || $value === '') {
52            throw new GTException("parameter value is required");
53        }
54
55        if (is_array($value)) {
56
57            $bytes = $value;
58
59            $value = '0';
60            $sign = '';
61
62            $length = count($bytes);
63
64            if ($length <= 0) {
65                throw new GTException("Invalid length: {$length}");
66            }
67
68            if ($bytes[0] >> 7 == 1) {
69
70                $sign = '-';
71
72                for ($i = 0; $i < $length; $i++) {
73                    $bytes[$i] = ~$bytes[$i] & 0xFF;
74                }
75            }
76
77            for ($i = 0; $i < $length; $i++) {
78                $value = bcadd($value, bcmul($bytes[$i], bcpow(256, $length - $i - 1, 0), 0), 0);
79            }
80
81            if ($sign == '-') {
82                $value = bcadd($value, 1);
83            }
84
85            $value = $sign . $value;
86
87        } else if ($value instanceof GTBigInteger) {
88            $value = $value->getValue();
89        }
90
91        $value = (string) $value;
92
93        $chars = array(
94            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-'
95        );
96
97        foreach (GTUtil::toArray($value) as $c) {
98            if (!in_array($c, $chars, true)) {
99                throw new GTException("parameter value contains invalid character: {$c}");
100            }
101        }
102
103        $this->value = $value;
104    }
105
106    /**
107     * Gets the integer value as string.
108     *
109     * @return string integer value as string
110     */
111    public function getValue() {
112        return $this->value;
113    }
114
115    /**
116     * Compares this GTBigInteger to another GTBigInteger.
117     *
118     * @param  GTBigInteger $integer the other GTBigInteger
119     * @return int 0 if both integers are equal, 1 if current integer is larger than the other, -1 otherwise
120     */
121    public function comp(GTBigInteger $integer) {
122        return bccomp($this->value, $integer->value, 0);
123    }
124
125    /**
126     * Adds this GTBigInteger and another GTBigInteger.
127     *
128     * @param  GTBigInteger $integer the other GTBigInteger
129     * @return GTBigInteger the sum of the two integers
130     */
131    public function add(GTBigInteger $integer) {
132        return new GTBigInteger(bcadd($this->value, $integer->value, 0));
133    }
134
135    /**
136     * Subtracts another GTBigInteger from this integer.
137     *
138     * @param  GTBigInteger $integer the GTBigInteger to subtract from this one
139     * @return GTBigInteger the result of the subtraction
140     */
141    public function sub(GTBigInteger $integer) {
142        return new GTBigInteger(bcsub($this->value, $integer->value, 0));
143    }
144
145    /**
146     * Multiplies another GTBigInteger with this GTBigInteger.
147     *
148     * @param  GTBigInteger $integer the GTBigInteger to multiply with
149     * @return GTBigInteger the result of the multiplication
150     */
151    public function mul(GTBigInteger $integer) {
152        return new GTBigInteger(bcmul($this->value, $integer->value, 0));
153    }
154
155    /**
156     * Divides this GTBigInteger with another GTBigInteger.
157     *
158     * @param  GTBigInteger $integer the GTBigInteger to divide by
159     * @return GTBigInteger the result of the division
160     */
161    public function div(GTBigInteger $integer) {
162        return new GTBigInteger(bcdiv($this->value, $integer->value, 0));
163    }
164
165    /**
166     * Gets the modulus of this GTBigInteger using another GTBigInteger as modulus.
167     *
168     * @param  int $integer modulus
169     * @return GTBigInteger the modulus
170     */
171    public function mod($modulus) {
172        return new GTBigInteger(bcmod($this->value, $modulus));
173    }
174
175    /**
176     * Raises this GTBigInteger to the power of another GTBigInteger.
177     *
178     * @param  GTBigInteger $integer power
179     * @return GTBigInteger result of raising this GTBigInteger to the power of another GTBigInteger
180     */
181    public function pow(GTBigInteger $integer) {
182        return new GTBigInteger(bcpow($this->value, $integer->value, 0));
183    }
184
185    /**
186     * Returns a GTBigInteger whose value is (this << $step).
187     *
188     * @param  int $step shift distance
189     * @return GTBigInteger this << $step
190     */
191    public function shiftLeft($step) {
192        return new GTBigInteger(bcmul($this->value, bcpow(2, $step)));
193    }
194
195    /**
196     * Returns a GTBigInteger whose value is (this >> $step).
197     *
198     * @param  int $step shift distance
199     * @return GTBigInteger this >> $step
200     */
201    public function shiftRight($step) {
202        return new GTBigInteger(bcdiv($this->value, bcpow(2, $step)));
203    }
204
205    /**
206     * Returns a GTBitInteger whose value is ($this | $integer).
207     *
208     * @param  GTBigInteger $integer value to be OR'ed with this GTBigInteger
209     * @return GTBigInteger $this | $integer
210     */
211    public function bitOr(GTBigInteger $integer) {
212
213        $bytes1 = $this->toBytes();
214        $bytes2 = $integer->toBytes();
215
216        $length = max(count($bytes1), count($bytes2));
217
218        GTUtil::lpad($bytes1, $length, 0x0);
219        GTUtil::lpad($bytes2, $length, 0x0);
220
221        $result = array();
222
223        for ($i = 0; $i < $length; $i++) {
224            $result[$i] = $bytes1[$i] | $bytes2[$i];
225        }
226
227        return new GTBigInteger($result);
228    }
229
230    /**
231     * Returns a GTBigInteger whose value is ($this ^ $integer).
232     *
233     * @param  GTBigInteger $integer value to be XOR'ed with this GTBigInteger
234     * @return GTBigInteger $this | $integer
235     */
236    public function bitXor(GTBigInteger $integer) {
237
238        $bytes1 = $this->toBytes();
239        $bytes2 = $integer->toBytes();
240
241        $length = max(count($bytes1), count($bytes2));
242
243        GTUtil::lpad($bytes1, $length, 0x0);
244        GTUtil::lpad($bytes2, $length, 0x0);
245
246        $result = array();
247
248        for ($i = 0; $i < $length; $i++) {
249            $result[$i] = $bytes1[$i] ^ $bytes2[$i];
250        }
251
252        return new GTBigInteger($result);
253    }
254
255    /**
256     * Returns a GTBigInteger whose value is ($this & $integer).
257     *
258     * @param  GTBigInteger $integer value to be AND'ed with this GTBigInteger
259     * @return GTBigInteger $this & $integer
260     */
261    public function bitAnd(GTBigInteger $integer) {
262
263        $bytes1 = $this->toBytes();
264        $bytes2 = $integer->toBytes();
265
266        $length = max(count($bytes1), count($bytes2));
267
268        GTUtil::lpad($bytes1, $length, 0x0);
269        GTUtil::lpad($bytes2, $length, 0x0);
270
271        $result = array();
272
273        for ($i = 0; $i < $length; $i++) {
274            $result[$i] = $bytes1[$i] & $bytes2[$i];
275        }
276
277        return new GTBigInteger($result);
278    }
279
280    /**
281     * Returns a GTBigInteger whose value is (~$this).
282     *
283     *
284     * @return GTBigInteger ~$this
285     */
286    public function bitNot() {
287
288        $result = array();
289
290        foreach ($this->toBytes() as $byte) {
291            array_push($result, ~$byte & 0xFF);
292        }
293
294        return new GTBigInteger($result);
295    }
296
297    /**
298     * Returns an array of bytes that contains this integers two's complement representation.
299     *
300     * Example:
301     *
302     * <code>
303     * $int = new GTBigInteger(123456);
304     *
305     * print_r($int->toBytes());
306     *
307     * // Array
308     * // (
309     * //   [0] => 1
310     * //   [1] => 226
311     * //   [2] => 64
312     * // )
313     * </code>
314     *
315     * @return array byte array that contains two's complement representation of this integer
316     */
317    public function toBytes() {
318
319        $result = '';
320
321        $buff = $this->value;
322        $sign = '';
323
324        if ($buff{0} == '-') {
325            $sign = '-';
326            $buff = substr($buff, 1);
327        }
328
329        while (bccomp($buff, 255, 0) == 1) {
330
331            $rest = bcmod($buff, 256);
332            $buff = bcdiv($buff, 256, 0);
333
334            $result = chr($rest) . $result;
335        }
336
337        $result = chr($buff) . $result;
338
339        $bytes = GTUtil::toByteArray($result);
340
341        if ($sign == '-') {
342
343            for ($i = 0; $i < count($bytes); $i++) {
344                $bytes[$i] = ~$bytes[$i] & 0xFF;
345            }
346
347            array_unshift($bytes, 0x0);
348
349            $int = new GTBigInteger($bytes);
350            $int = $int->add(new GTBigInteger(1));
351
352            $bytes = $int->toBytes();
353
354            // strip leading 0 bytes
355            while (count($bytes) > 0 && $bytes[0] == 0x0) {
356                array_shift($bytes);
357            }
358
359            return $bytes;
360
361        } else {
362
363            // add leading 0x0 so the integer isn't considered negative
364            if (count($bytes) > 0 && $bytes[0] >> 7 == 1) {
365                array_unshift($bytes, 0x0);
366            }
367
368            return $bytes;
369
370        }
371
372    }
373
374    /**
375     * Returns a bit string that contains the bits of this integer.
376     *
377     * Example:
378     *
379     * <code>
380     * $int = new GTBigInteger(4);
381     * echo $int->toBits();
382     *
383     * // 00000100
384     * </code>
385     *
386     * @return string bit string containing the bits of this integer
387     */
388    public function toBits() {
389
390        $result = '';
391
392        foreach ($this->toBytes() as $byte) {
393
394            $byte = decbin($byte);
395
396            while (strlen($byte) % 8 != 0) {
397                $byte = '0' . $byte;
398            }
399
400            $result .= $byte;
401        }
402
403        return $result;
404
405    }
406
407}
408
409?>
410