Базовое преобразование чисел произвольного размера (PHP)

Question

У меня есть длинная "двоичная строка", например, выходная информация PHP-пакета.

Как я могу преобразовать это значение в base62 (0-9a-zA-Z)? Встроенные математические функции переполняются такими длинными входами, и BCmath не имеет функции base_convert или чего-то такого особенного. Мне также нужна соответствующая функция «pack base62».

Answer 1

Я думаю, что за этим вопросом стоит недоразумение. Базовое преобразование и кодирование / декодирование отличаются . Вывод base64_encode(...) равен , а не большому числу base64. Это ряд дискретных значений base64, соответствующих функции сжатия. Вот почему BC Math не работает, потому что BC Math имеет дело с одиночными большими числами, а не со строками, которые в действительности являются группами небольших чисел, представляющих двоичные данные.

Вот пример, иллюстрирующий разницу:

base64_encode(1234) = "MTIzNA=="
base64_convert(1234) = "TS" //if the base64_convert function existed

кодирование base64 разбивает входные данные на группы по 3 байта (3 * 8 = 24 бита), а затем преобразует каждый подсегмент из 6 бит (2 ^ 6 = 64, следовательно, "base64") на соответствующий символ base64 (значения: «ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789 + /», где A = 0, / = 63).

В нашем примере base64_encode() обрабатывает "1234" как строку из 4 символов, а не целое число (поскольку base64_encode() не работает с целыми числами). Поэтому он выводит «MTIzNA ==», потому что (в US-ASCII / UTF-8 / ISO-8859-1) «1234» - это 00110001 00110010 00110011 00110100 в двоичном виде. Это разбивается на 001100 (12 в десятичном формате, символ «M») 010011 (19 в десятичном формате, символ «T») 001000 («I») 110011 («z») 001101 («N») 00. С последней группы не завершено, оно дополняется нулями, и значение равно 000000 («A»). Поскольку все выполняется группами из 3 входных символов, есть две группы: «123» и «4». Последняя группа дополняется символом =, чтобы сделать его длиной 3 символа, поэтому весь вывод становится «MTIzNA ==».

преобразование в base64 , с другой стороны, принимает одно целочисленное значение и преобразует его в одно значение base64. В нашем примере 1234 (десятичное число) - это «TS» (base64), если мы используем ту же строку значений base64, что и выше. Работа в обратном направлении и слева направо: T = 19 (столбец 1), S = 18 (столбец 0), поэтому (19 * 64 ^ 1) + (18 * 64 ^ 0) = 19 * 64 + 18 = 1234 (десятичный). То же число может быть представлено как "4D2" в шестнадцатеричном (base16): (4 * 16 ^ 2) + (D * 16 ^ 1) + (2 * 16 ^ 0) = (4 * 256 ) + (13 * 16) + (2 * 1) = 1234 (десятичное число).

В отличие от кодировки , которая принимает строку символов и изменяет ее, базовое преобразование не изменяет фактическое число, а только изменяет его представление. Шестнадцатеричное (base16) «FF» - это то же число , что и десятичное (base10) «255», то есть такое же число, что и «11111111» в двоичном формате (base2). Думайте об этом как об обмене валюты, если обменный курс никогда не менялся: 1 доллар США имеет ту же стоимость, что и 0,79 фунта стерлингов (курс на сегодня, но притворяется, что он никогда не меняется).

В вычислениях целые числа обычно обрабатываются как двоичные значения (потому что легко построить 1-битные арифметические единицы, а затем сложить их вместе, чтобы получить 32-битные и т. Д. Арифметические единицы). Чтобы сделать что-то столь же простое, как «255 + 255» (десятичное), компьютер должен сначала преобразовать числа в двоичные («11111111» + «11111111»), а затем выполнить операцию в Арифметическом логическом блоке (ALU).

Почти все другие виды использования основ исключительно для удобства людей (презентационные) - компьютеры отображают свое внутреннее значение 11111111 (двоичное) как 255 (десятичное), потому что люди обучены работать с десятичными числами. Функция base64_convert() не существует как часть стандартного репертуара PHP, потому что она часто никому не полезна: не многие люди читают числа base64 изначально. Напротив, двоичные 1 и 0 иногда полезны для программистов (мы можем использовать их как переключатели вкл / выкл!), А шестнадцатеричное удобно для людей, редактирующих двоичные данные, потому что весь 8-битный байт может быть однозначно представлен от 00 до FF, не тратя слишком много места.

Вы можете спросить: «Если базовое преобразование только для представления, почему BC Math существует?» Это справедливый вопрос, а также почему я сказал «почти» исключительно для наглядности: типичные компьютеры ограничены 32-битными или 64-битными числами, которые обычно достаточно велики. Иногда вам нужно оперировать действительно действительно большими числами (например, модулями RSA), которые не вписываются в эти регистры. BC Math решает эту проблему, выступая в качестве уровня абстракции: он преобразует огромные числа в длинные строки текста. Когда пришло время выполнить какую-либо операцию, BC Math кропотливо разбивает длинные строки текста на небольшие куски, с которыми может справиться компьютер. Это намного, намного медленнее, чем собственные операции, но может обрабатывать числа произвольного размера.

Answer 2

Если вы действительно, действительно не должны иметь base62, почему бы не пойти на:

base64_encode()
base64_decode()

Единственными другими добавленными символами являются "+" и "=", и это очень хорошо известный способ упаковки и распаковки двоичных строк с доступными функциями во многих других языках.

Answer 3

Вот функция base_conv(), которая может конвертировать между совершенно произвольными базами, выраженными в виде массивов строк; Каждый элемент массива представляет собой одну «цифру» в этой базе, что также позволяет использовать многосимвольные значения (это ваша ответственность, чтобы избежать двусмысленности).

function base_conv($val, &$baseTo, &$baseFrom)
    {
    return base_arr_to_str(base_conv_arr(base_str_to_arr((string) $val, $baseFrom), count($baseTo), count($baseFrom)), $baseTo);
    }

function base_conv_arr($val, $baseToDigits, $baseFromDigits)
    {
    $valCount = count($val);
    $result = array();
    do
        {
        $divide = 0;
        $newlen = 0;
        for ($i = 0; $i < $valCount; ++$i)
            {
            $divide = $divide * $baseFromDigits + $val[$i];
            if ($divide >= $baseToDigits)
                {
                $val[$newlen ++] = (int) ($divide / $baseToDigits);
                $divide = $divide % $baseToDigits;
                }
            else if ($newlen > 0)
                {
                $val[$newlen ++] = 0;
                }
            }
        $valCount = $newlen;
        array_unshift($result, $divide);
        }
        while ($newlen != 0);
    return $result;
    }

function base_arr_to_str($arr, &$base)
    {
    $str = '';
    foreach ($arr as $digit)
        {
        $str .= $base[$digit];
        }
    return $str;
    }

function base_str_to_arr($str, &$base)
    {
    $arr = array();
    while ($str === '0' || !empty($str))
        {
        foreach ($base as $index => $digit)
            {
            if (mb_substr($str, 0, $digitLen = mb_strlen($digit)) === $digit)
                {
                $arr[] = $index;
                $str = mb_substr($str, $digitLen);
                continue 2;
                }
            }
        throw new Exception();
        }
    return $arr;
    }

Примеры:

$baseDec = str_split('0123456789');
$baseHex = str_split('0123456789abcdef');

echo base_conv(255, $baseHex, $baseDec); // ff
echo base_conv('ff', $baseDec, $baseHex); // 255

// multi-character base:
$baseHelloworld = array('hello ', 'world ');
echo base_conv(37, $baseHelloworld, $baseDec); // world hello hello world hello world 
echo base_conv('world hello hello world hello world ', $baseDec, $baseHelloworld); // 37

// ambiguous base:
// don't do this! base_str_to_arr() won't know how to decode e.g. '11111'
// (well it does, but the result might not be what you'd expect;
// It matches digits sequentially so '11111' would be array(0, 0, 1)
// here (matched as '11', '11', '1' since they come first in the array))
$baseAmbiguous = array('11', '1', '111');