source: trunk/Packages/Common/BigInt.php

Last change on this file was 63, checked in by chronos, 3 years ago
  • Modified: Used explicit types where possible for better error reporting.
  • Modified: Updated Common packaged to newer version.
  • Modified: Simplified pages title.
  • Added: Simple keyword based spam filter for meet items.
File size: 7.1 KB
Line 
1<?php
2
3define('INT64', 64);
4define('INT128', 128);
5define('INT256', 256);
6define('INT512', 512);
7
8// BigInt represented as string of characters
9// First byte is MSB and last byte is LSB
10
11function BigIntNew($BitWidth): string
12{
13 return str_repeat(chr(0), $BitWidth >> 3);
14}
15
16function BigIntNewAs($A): string
17{
18 return str_repeat(chr(0), strlen($A));
19}
20
21function BigIntCheck(string $A, string $B): void
22{
23 if (strlen($A) != strlen($B))
24 throw new Exception('BigInt parameters bit width doesn\'t match.');
25}
26
27function BigIntAdd(string $A, string $B): string
28{
29 BigIntCheck($A, $B);
30 $Result = BigIntNewAs($A);
31 $Carry = 0;
32 for ($I = strlen($Result) - 1; $I >= 0; $I--)
33 {
34 $Sum = ord($A[$I]) + ord($B[$I]) + $Carry;
35 $Result[$I] = chr($Sum);
36 if ($Sum > 255) $Carry = 1;
37 else $Carry = 0;
38 }
39 return $Result;
40}
41
42function BigIntSub(string $A, string $B): string
43{
44 BigIntCheck($A, $B);
45 $Result = BigIntNewAs($A);
46 $Carry = 0;
47 for ($I = strlen($Result) - 1; $I >= 0; $I--)
48 {
49 $Sum = ord($A[$I]) - ord($B[$I]) - $Carry;
50 $Result[$I] = chr($Sum);
51 if ($Sum < 0) $Carry = 1;
52 else $Carry = 0;
53 }
54 return $Result;
55}
56
57function BigIntInc(string $A): string
58{
59 $Result = BigIntNewAs($A);
60 $Carry = 1;
61 for ($I = strlen($Result) - 1; $I >= 0; $I--)
62 {
63 $Sum = ord($A[$I]) + $Carry;
64 $Result[$I] = chr($Sum);
65 if ($Sum > 255) $Carry = 1;
66 else $Carry = 0;
67 }
68 return $Result;
69}
70
71function BigIntDec(string $A): string
72{
73 $Result = BigIntNewAs($A);
74 $Carry = 1;
75 for ($I = strlen($Result) - 1; $I >= 0; $I--)
76 {
77 $Sum = ord($A[$I]) - $Carry;
78 $Result[$I] = chr($Sum);
79 if ($Sum < 0) $Carry = 1;
80 else $Carry = 0;
81 }
82 return $Result;
83}
84
85function BigIntNeg(string $A): string
86{
87 return BigIntInc(BigIntNot($A));
88}
89
90function BigIntIsNeg(string $A): string
91{
92 return ord($A[0]) & 0x80;
93}
94
95function BigIntEqual(string $A, string $B): bool
96{
97 return $A == $B; // Simple string comparison
98}
99
100function BigIntNotEqual(string $A, string $B): bool
101{
102 return $A != $B; // Simple string comparison
103}
104
105function BigIntGreater(string $A, string $B): bool
106{
107 return BigIntIsNeg(BigIntSub($B, $A));
108}
109
110function BigIntGreaterOrEqual(string $A, string $B): bool
111{
112 return BigIntIsNeg(BigIntSub($B, $A)) or BigIntEqual($A, $B);
113}
114
115function BigIntLesser(string $A, string $B): bool
116{
117 return BigIntIsNeg(BigIntSub($A, $B));
118}
119
120function BigIntLesserOrEqual(string $A, string $B): bool
121{
122 return BigIntIsNeg(BigIntSub($A, $B)) or BigIntEqual($A, $B);
123}
124
125function BigIntMul(string $A, string $B): string
126{
127 BigIntCheck($A, $B);
128 $Result = BigIntNewAs($A);
129 while (BigIntGreater($B, BigIntNewAs($A)))
130 {
131 $Result = BigIntAdd($Result, $A);
132 $B = BigIntDec($B);
133 }
134 return $Result;
135}
136
137function BigIntDiv(string $A, string $B): string
138{
139 BigIntCheck($A, $B);
140 $Result = BigIntNewAs($A);
141 while (BigIntGreaterOrEqual($A, $B))
142 {
143 $A = BigIntSub($A, $B);
144 $Result = BigIntInc($Result);
145 }
146 return $Result;
147}
148
149function BigIntMod(string $A, string $B): string
150{
151 BigIntCheck($A, $B);
152 $Result = BigIntNewAs($A);
153 while (BigIntGreaterOrEqual($A, $B))
154 {
155 $A = BigIntSub($A, $B);
156 $Result = BigIntInc($Result);
157 }
158 return $A;
159}
160
161function BigIntAnd(string $A, string $B): string
162{
163 BigIntCheck($A, $B);
164 $Result = BigIntNewAs($A);
165 for ($I = 0; $I < strlen($Result); $I++)
166 {
167 $Result[$I] = chr(ord($A[$I]) & ord($B[$I]));
168 }
169 return $Result;
170}
171
172function BigIntOr(string $A, string $B): string
173{
174 BigIntCheck($A, $B);
175 $Result = BigIntNewAs($A);
176 for ($I = 0; $I < strlen($Result); $I++)
177 {
178 $Result[$I] = chr(ord($A[$I]) | ord($B[$I]));
179 }
180 return $Result;
181}
182
183function BigIntXor(string $A, string $B): string
184{
185 BigIntCheck($A, $B);
186 $Result = BigIntNewAs($A);
187 for ($I = 0; $I < strlen($Result); $I++)
188 {
189 $Result[$I] = chr(ord($A[$I]) ^ ord($B[$I]));
190 }
191 return $Result;
192}
193
194function BigIntNot(string $A): string
195{
196 $Result = BigIntNewAs($A);
197 for ($I = 0; $I < strlen($Result); $I++)
198 {
199 $Result[$I] = chr(~ord($A[$I]));
200 }
201 return $Result;
202}
203
204function BigIntShl1(string $A): string
205{
206 $Result = BigIntNewAs($A);
207 for ($I = 0; $I < strlen($Result) - 1; $I++)
208 {
209 $Result[$I] = chr((ord($A[$I]) << 1) | (ord($A[$I + 1]) >> 7));
210 }
211 $Result[strlen($Result) - 1] = chr(ord($A[strlen($Result) - 1]) << 1);
212 return $Result;
213}
214
215function BigIntShl(string $A, string $B): string
216{
217 BigIntCheck($A, $B);
218 $Result = $A;
219 for ($I = 0; $I < Int128ToInt($B); $I++)
220 {
221 $Result = BigIntShl1($Result);
222 }
223 return $Result;
224}
225
226function BigIntShr1(string $A): string
227{
228 $Result = BigIntNewAs($A);
229 for ($I = strlen($Result) - 1; $I > 0; $I--)
230 {
231 $Result[$I] = chr((ord($A[$I]) >> 1) | ((ord($A[$I - 1]) & 1) << 7));
232 }
233 $Result[0] = chr(ord($A[0]) >> 1);
234 return $Result;
235}
236
237function BigIntShr(string $A, string $B): string
238{
239 BigIntCheck($A, $B);
240 $Result = $A;
241 for ($I = 0; $I < Int128ToInt($B); $I++)
242 {
243 $Result = BigIntShr1($Result);
244 }
245 return $Result;
246}
247
248function BigIntToHex(string $A): string
249{
250 $Result = '';
251 for ($I = 0; $I < strlen($A); $I++)
252 {
253 $Result .= str_pad(dechex(ord($A[$I])), 2, '0', STR_PAD_LEFT);
254 }
255 return $Result;
256}
257
258function HexToBigInt(string $A, int $BitWidth): string
259{
260 $Result = BigIntNew($BitWidth);
261 $I = strlen($A) - 1;
262 $Index = 15;
263 while (($I >= 0) && ($Index >= 0))
264 {
265 $Result[$Index] = chr(ord($Result[$Index]) | hexdec($A[$I]));
266 $I--;
267 if ($I >= 0)
268 {
269 $Result[$Index] = chr(ord($Result[$Index]) | (hexdec($A[$I]) << 4));
270 $I--;
271 }
272 $Index--;
273 }
274 return $Result;
275}
276
277function BigIntToBin(string $A): string
278{
279 $Result = '';
280 for ($I = 0; $I < strlen($A); $I++)
281 {
282 $Result .= str_pad(decbin(ord($A[$I])), 8, '0', STR_PAD_LEFT);
283 }
284 return $Result;
285}
286
287function BinToBigInt(string $A, int $BitWidth): string
288{
289 $Result = BigIntNew($BitWidth);
290 $I = strlen($A) - 1;
291 $Index = strlen($Result) - 1;
292 while (($I >= 0) && ($Index >= 0))
293 {
294 for ($J = 0; $J < 7; $J++)
295 {
296 if ($I >= 0)
297 {
298 $Result[$Index] = chr(ord($Result[$Index]) | (bindec($A[$I]) << $J));
299 $I--;
300 }
301 }
302 $Index--;
303 }
304 return $Result;
305}
306
307function BigIntToInt(string $A): int
308{
309 // 32-bit int support
310 return ord($A[15]) | (ord($A[14]) << 8) | (ord($A[13]) << 16) | (ord($A[12]) << 24);
311}
312
313function IntToBigInt(int $A, int $BitWidth): string
314{
315 $Result = BigIntNew($BitWidth);
316 // 32-bit int support
317 $Result[15] = chr($A & 0xff);
318 $Result[14] = chr(($A >> 8) & 0xff);
319 $Result[13] = chr(($A >> 16) & 0xff);
320 $Result[12] = chr(($A >> 24) & 0xff);
321 return $Result;
322}
323
324function BigIntToDec(string $A): string
325{
326 $BitWidth = strlen($A) << 3;
327 $Result = '';
328 $Zero = BigIntNewAs($A);
329 while (BigIntGreater($A, $Zero))
330 {
331 $Result = strval(BigIntToInt(BigIntMod($A, IntToBigInt(10, $BitWidth)))).$Result;
332 $A = BigIntDiv($A, IntToBigInt(10, $BitWidth));
333 }
334 return $Result;
335}
336
337function DecToBigInt(string $A, int $BitWidth): string
338{
339 $Result = BigIntNew($BitWidth);
340 $I = 0;
341 while ($I < strlen($A))
342 {
343 $Result = BigIntMul($Result, IntToBigInt(10, $BitWidth));
344 $Result = BigIntAdd($Result, IntToBigInt(intval($A[$I]), $BitWidth));
345 $I++;
346 }
347 return $Result;
348}
Note: See TracBrowser for help on using the repository browser.