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

Question

У меня есть длинная "бинарная строка", как вывод функции пакета PHPs.

Как я могу преобразовать это значение в 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 входных символов, есть 2 группы: "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');