1<?php
2declare(strict_types=1);
3namespace ParagonIE\ConstantTime;
4
5/**
6 *  Copyright (c) 2016 - 2018 Paragon Initiative Enterprises.
7 *  Copyright (c) 2014 Steve "Sc00bz" Thomas (steve at tobtu dot com)
8 *
9 *  Permission is hereby granted, free of charge, to any person obtaining a copy
10 *  of this software and associated documentation files (the "Software"), to deal
11 *  in the Software without restriction, including without limitation the rights
12 *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 *  copies of the Software, and to permit persons to whom the Software is
14 *  furnished to do so, subject to the following conditions:
15 *
16 *  The above copyright notice and this permission notice shall be included in all
17 *  copies or substantial portions of the Software.
18 *
19 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 *  SOFTWARE.
26 */
27
28/**
29 * Class Base32
30 * [A-Z][2-7]
31 *
32 * @package ParagonIE\ConstantTime
33 */
34abstract class Base32 implements EncoderInterface
35{
36    /**
37     * Decode a Base32-encoded string into raw binary
38     *
39     * @param string $encodedString
40     * @param bool $strictPadding
41     * @return string
42     */
43    public static function decode(string $encodedString, bool $strictPadding = false): string
44    {
45        return static::doDecode($encodedString, false, $strictPadding);
46    }
47
48    /**
49     * Decode an uppercase Base32-encoded string into raw binary
50     *
51     * @param string $src
52     * @param bool $strictPadding
53     * @return string
54     */
55    public static function decodeUpper(string $src, bool $strictPadding = false): string
56    {
57        return static::doDecode($src, true, $strictPadding);
58    }
59
60    /**
61     * Encode into Base32 (RFC 4648)
62     *
63     * @param string $binString
64     * @return string
65     * @throws \TypeError
66     */
67    public static function encode(string $binString): string
68    {
69        return static::doEncode($binString, false, true);
70    }
71    /**
72     * Encode into Base32 (RFC 4648)
73     *
74     * @param string $src
75     * @return string
76     * @throws \TypeError
77     */
78    public static function encodeUnpadded(string $src): string
79    {
80        return static::doEncode($src, false, false);
81    }
82
83    /**
84     * Encode into uppercase Base32 (RFC 4648)
85     *
86     * @param string $src
87     * @return string
88     * @throws \TypeError
89     */
90    public static function encodeUpper(string $src): string
91    {
92        return static::doEncode($src, true, true);
93    }
94
95    /**
96     * Encode into uppercase Base32 (RFC 4648)
97     *
98     * @param string $src
99     * @return string
100     * @throws \TypeError
101     */
102    public static function encodeUpperUnpadded(string $src): string
103    {
104        return static::doEncode($src, true, false);
105    }
106
107    /**
108     * Uses bitwise operators instead of table-lookups to turn 5-bit integers
109     * into 8-bit integers.
110     *
111     * @param int $src
112     * @return int
113     */
114    protected static function decode5Bits(int $src): int
115    {
116        $ret = -1;
117
118        // if ($src > 96 && $src < 123) $ret += $src - 97 + 1; // -64
119        $ret += (((0x60 - $src) & ($src - 0x7b)) >> 8) & ($src - 96);
120
121        // if ($src > 0x31 && $src < 0x38) $ret += $src - 24 + 1; // -23
122        $ret += (((0x31 - $src) & ($src - 0x38)) >> 8) & ($src - 23);
123
124        return $ret;
125    }
126
127    /**
128     * Uses bitwise operators instead of table-lookups to turn 5-bit integers
129     * into 8-bit integers.
130     *
131     * Uppercase variant.
132     *
133     * @param int $src
134     * @return int
135     */
136    protected static function decode5BitsUpper(int $src): int
137    {
138        $ret = -1;
139
140        // if ($src > 64 && $src < 91) $ret += $src - 65 + 1; // -64
141        $ret += (((0x40 - $src) & ($src - 0x5b)) >> 8) & ($src - 64);
142
143        // if ($src > 0x31 && $src < 0x38) $ret += $src - 24 + 1; // -23
144        $ret += (((0x31 - $src) & ($src - 0x38)) >> 8) & ($src - 23);
145
146        return $ret;
147    }
148
149    /**
150     * Uses bitwise operators instead of table-lookups to turn 8-bit integers
151     * into 5-bit integers.
152     *
153     * @param int $src
154     * @return string
155     */
156    protected static function encode5Bits(int $src): string
157    {
158        $diff = 0x61;
159
160        // if ($src > 25) $ret -= 72;
161        $diff -= ((25 - $src) >> 8) & 73;
162
163        return \pack('C', $src + $diff);
164    }
165
166    /**
167     * Uses bitwise operators instead of table-lookups to turn 8-bit integers
168     * into 5-bit integers.
169     *
170     * Uppercase variant.
171     *
172     * @param int $src
173     * @return string
174     */
175    protected static function encode5BitsUpper(int $src): string
176    {
177        $diff = 0x41;
178
179        // if ($src > 25) $ret -= 40;
180        $diff -= ((25 - $src) >> 8) & 41;
181
182        return \pack('C', $src + $diff);
183    }
184
185
186    /**
187     * Base32 decoding
188     *
189     * @param string $src
190     * @param bool $upper
191     * @param bool $strictPadding
192     * @return string
193     * @throws \TypeError
194     * @psalm-suppress RedundantCondition
195     */
196    protected static function doDecode(string $src, bool $upper = false, bool $strictPadding = false): string
197    {
198        // We do this to reduce code duplication:
199        $method = $upper
200            ? 'decode5BitsUpper'
201            : 'decode5Bits';
202
203        // Remove padding
204        $srcLen = Binary::safeStrlen($src);
205        if ($srcLen === 0) {
206            return '';
207        }
208        if ($strictPadding) {
209            if (($srcLen & 7) === 0) {
210                for ($j = 0; $j < 7; ++$j) {
211                    if ($src[$srcLen - 1] === '=') {
212                        $srcLen--;
213                    } else {
214                        break;
215                    }
216                }
217            }
218            if (($srcLen & 7) === 1) {
219                throw new \RangeException(
220                    'Incorrect padding'
221                );
222            }
223        } else {
224            $src = \rtrim($src, '=');
225            $srcLen = Binary::safeStrlen($src);
226        }
227
228        $err = 0;
229        $dest = '';
230        // Main loop (no padding):
231        for ($i = 0; $i + 8 <= $srcLen; $i += 8) {
232            /** @var array<int, int> $chunk */
233            $chunk = \unpack('C*', Binary::safeSubstr($src, $i, 8));
234            /** @var int $c0 */
235            $c0 = static::$method($chunk[1]);
236            /** @var int $c1 */
237            $c1 = static::$method($chunk[2]);
238            /** @var int $c2 */
239            $c2 = static::$method($chunk[3]);
240            /** @var int $c3 */
241            $c3 = static::$method($chunk[4]);
242            /** @var int $c4 */
243            $c4 = static::$method($chunk[5]);
244            /** @var int $c5 */
245            $c5 = static::$method($chunk[6]);
246            /** @var int $c6 */
247            $c6 = static::$method($chunk[7]);
248            /** @var int $c7 */
249            $c7 = static::$method($chunk[8]);
250
251            $dest .= \pack(
252                'CCCCC',
253                (($c0 << 3) | ($c1 >> 2)             ) & 0xff,
254                (($c1 << 6) | ($c2 << 1) | ($c3 >> 4)) & 0xff,
255                (($c3 << 4) | ($c4 >> 1)             ) & 0xff,
256                (($c4 << 7) | ($c5 << 2) | ($c6 >> 3)) & 0xff,
257                (($c6 << 5) | ($c7     )             ) & 0xff
258            );
259            $err |= ($c0 | $c1 | $c2 | $c3 | $c4 | $c5 | $c6 | $c7) >> 8;
260        }
261        // The last chunk, which may have padding:
262        if ($i < $srcLen) {
263            /** @var array<int, int> $chunk */
264            $chunk = \unpack('C*', Binary::safeSubstr($src, $i, $srcLen - $i));
265            /** @var int $c0 */
266            $c0 = static::$method($chunk[1]);
267
268            if ($i + 6 < $srcLen) {
269                /** @var int $c1 */
270                $c1 = static::$method($chunk[2]);
271                /** @var int $c2 */
272                $c2 = static::$method($chunk[3]);
273                /** @var int $c3 */
274                $c3 = static::$method($chunk[4]);
275                /** @var int $c4 */
276                $c4 = static::$method($chunk[5]);
277                /** @var int $c5 */
278                $c5 = static::$method($chunk[6]);
279                /** @var int $c6 */
280                $c6 = static::$method($chunk[7]);
281
282                $dest .= \pack(
283                    'CCCC',
284                    (($c0 << 3) | ($c1 >> 2)             ) & 0xff,
285                    (($c1 << 6) | ($c2 << 1) | ($c3 >> 4)) & 0xff,
286                    (($c3 << 4) | ($c4 >> 1)             ) & 0xff,
287                    (($c4 << 7) | ($c5 << 2) | ($c6 >> 3)) & 0xff
288                );
289                $err |= ($c0 | $c1 | $c2 | $c3 | $c4 | $c5 | $c6) >> 8;
290            } elseif ($i + 5 < $srcLen) {
291                /** @var int $c1 */
292                $c1 = static::$method($chunk[2]);
293                /** @var int $c2 */
294                $c2 = static::$method($chunk[3]);
295                /** @var int $c3 */
296                $c3 = static::$method($chunk[4]);
297                /** @var int $c4 */
298                $c4 = static::$method($chunk[5]);
299                /** @var int $c5 */
300                $c5 = static::$method($chunk[6]);
301
302                $dest .= \pack(
303                    'CCCC',
304                    (($c0 << 3) | ($c1 >> 2)             ) & 0xff,
305                    (($c1 << 6) | ($c2 << 1) | ($c3 >> 4)) & 0xff,
306                    (($c3 << 4) | ($c4 >> 1)             ) & 0xff,
307                    (($c4 << 7) | ($c5 << 2)             ) & 0xff
308                );
309                $err |= ($c0 | $c1 | $c2 | $c3 | $c4 | $c5) >> 8;
310            } elseif ($i + 4 < $srcLen) {
311                /** @var int $c1 */
312                $c1 = static::$method($chunk[2]);
313                /** @var int $c2 */
314                $c2 = static::$method($chunk[3]);
315                /** @var int $c3 */
316                $c3 = static::$method($chunk[4]);
317                /** @var int $c4 */
318                $c4 = static::$method($chunk[5]);
319
320                $dest .= \pack(
321                    'CCC',
322                    (($c0 << 3) | ($c1 >> 2)             ) & 0xff,
323                    (($c1 << 6) | ($c2 << 1) | ($c3 >> 4)) & 0xff,
324                    (($c3 << 4) | ($c4 >> 1)             ) & 0xff
325                );
326                $err |= ($c0 | $c1 | $c2 | $c3 | $c4) >> 8;
327            } elseif ($i + 3 < $srcLen) {
328                /** @var int $c1 */
329                $c1 = static::$method($chunk[2]);
330                /** @var int $c2 */
331                $c2 = static::$method($chunk[3]);
332                /** @var int $c3 */
333                $c3 = static::$method($chunk[4]);
334
335                $dest .= \pack(
336                    'CC',
337                    (($c0 << 3) | ($c1 >> 2)             ) & 0xff,
338                    (($c1 << 6) | ($c2 << 1) | ($c3 >> 4)) & 0xff
339                );
340                $err |= ($c0 | $c1 | $c2 | $c3) >> 8;
341            } elseif ($i + 2 < $srcLen) {
342                /** @var int $c1 */
343                $c1 = static::$method($chunk[2]);
344                /** @var int $c2 */
345                $c2 = static::$method($chunk[3]);
346
347                $dest .= \pack(
348                    'CC',
349                    (($c0 << 3) | ($c1 >> 2)             ) & 0xff,
350                    (($c1 << 6) | ($c2 << 1)             ) & 0xff
351                );
352                $err |= ($c0 | $c1 | $c2) >> 8;
353            } elseif ($i + 1 < $srcLen) {
354                /** @var int $c1 */
355                $c1 = static::$method($chunk[2]);
356
357                $dest .= \pack(
358                    'C',
359                    (($c0 << 3) | ($c1 >> 2)             ) & 0xff
360                );
361                $err |= ($c0 | $c1) >> 8;
362            } else {
363                $dest .= \pack(
364                    'C',
365                    (($c0 << 3)                          ) & 0xff
366                );
367                $err |= ($c0) >> 8;
368            }
369        }
370        $check = ($err === 0);
371        if (!$check) {
372            throw new \RangeException(
373                'Base32::doDecode() only expects characters in the correct base32 alphabet'
374            );
375        }
376        return $dest;
377    }
378
379    /**
380     * Base32 Encoding
381     *
382     * @param string $src
383     * @param bool $upper
384     * @param bool $pad
385     * @return string
386     * @throws \TypeError
387     */
388    protected static function doEncode(string $src, bool $upper = false, $pad = true): string
389    {
390        // We do this to reduce code duplication:
391        $method = $upper
392            ? 'encode5BitsUpper'
393            : 'encode5Bits';
394
395        $dest = '';
396        $srcLen = Binary::safeStrlen($src);
397
398        // Main loop (no padding):
399        for ($i = 0; $i + 5 <= $srcLen; $i += 5) {
400            /** @var array<int, int> $chunk */
401            $chunk = \unpack('C*', Binary::safeSubstr($src, $i, 5));
402            $b0 = $chunk[1];
403            $b1 = $chunk[2];
404            $b2 = $chunk[3];
405            $b3 = $chunk[4];
406            $b4 = $chunk[5];
407            $dest .=
408                static::$method(              ($b0 >> 3)  & 31) .
409                static::$method((($b0 << 2) | ($b1 >> 6)) & 31) .
410                static::$method((($b1 >> 1)             ) & 31) .
411                static::$method((($b1 << 4) | ($b2 >> 4)) & 31) .
412                static::$method((($b2 << 1) | ($b3 >> 7)) & 31) .
413                static::$method((($b3 >> 2)             ) & 31) .
414                static::$method((($b3 << 3) | ($b4 >> 5)) & 31) .
415                static::$method(  $b4                     & 31);
416        }
417        // The last chunk, which may have padding:
418        if ($i < $srcLen) {
419            /** @var array<int, int> $chunk */
420            $chunk = \unpack('C*', Binary::safeSubstr($src, $i, $srcLen - $i));
421            $b0 = $chunk[1];
422            if ($i + 3 < $srcLen) {
423                $b1 = $chunk[2];
424                $b2 = $chunk[3];
425                $b3 = $chunk[4];
426                $dest .=
427                    static::$method(              ($b0 >> 3)  & 31) .
428                    static::$method((($b0 << 2) | ($b1 >> 6)) & 31) .
429                    static::$method((($b1 >> 1)             ) & 31) .
430                    static::$method((($b1 << 4) | ($b2 >> 4)) & 31) .
431                    static::$method((($b2 << 1) | ($b3 >> 7)) & 31) .
432                    static::$method((($b3 >> 2)             ) & 31) .
433                    static::$method((($b3 << 3)             ) & 31);
434                if ($pad) {
435                    $dest .= '=';
436                }
437            } elseif ($i + 2 < $srcLen) {
438                $b1 = $chunk[2];
439                $b2 = $chunk[3];
440                $dest .=
441                    static::$method(              ($b0 >> 3)  & 31) .
442                    static::$method((($b0 << 2) | ($b1 >> 6)) & 31) .
443                    static::$method((($b1 >> 1)             ) & 31) .
444                    static::$method((($b1 << 4) | ($b2 >> 4)) & 31) .
445                    static::$method((($b2 << 1)             ) & 31);
446                if ($pad) {
447                    $dest .= '===';
448                }
449            } elseif ($i + 1 < $srcLen) {
450                $b1 = $chunk[2];
451                $dest .=
452                    static::$method(              ($b0 >> 3)  & 31) .
453                    static::$method((($b0 << 2) | ($b1 >> 6)) & 31) .
454                    static::$method((($b1 >> 1)             ) & 31) .
455                    static::$method((($b1 << 4)             ) & 31);
456                if ($pad) {
457                    $dest .= '====';
458                }
459            } else {
460                $dest .=
461                    static::$method(              ($b0 >> 3)  & 31) .
462                    static::$method( ($b0 << 2)               & 31);
463                if ($pad) {
464                    $dest .= '======';
465                }
466            }
467        }
468        return $dest;
469    }
470}
471