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