Base62 coding

Question

I wonder where I can get some PHP implementation, similar to MIME Base64 PHP but only with A-Z, a-z and 0-9 characters.

The Base64 from PHP is quite versatile, but I need an algorithm that doesn’t contemplate the characters +, /, - and =. I know that I can replace the characters mentioned for the purpose of a URL, which is not even the case, but actually intended a direct coding algorithm.

The encoding of numbers for base62, is linear, but intended to encode a binary PHP string. Important to perform the encounter and the Decode.

Can someone tell me some practical implementation?

Answer 1

Follows the implementation.

• Implemented in two different languages: PHP and Java.
• Allows you to specify the alphabet in the constructor.
• The alphabet size is obtained from the alphabet itself.
• Should work for any alphabet size >= 2 and < 256.
• The functioning of encode consists in interpreting the String input as a base-256 number to be converted to BigInteger. Then the BigInteger is converted to a String base-62 (or any other, according to the given alphabet).
• The functioning of decode is just the reverse of encode. Receives the String as if it were a number in base-62 (or any other), converts to BigInteger and then converts the BigInteger for a String base-256.

PHP:

Here’s the code:

<?php

include('Math/BigInteger.php');

class BaseN {

    private $base;
    private $radix;
    private $bi256, $one, $zero;

    function __construct($base) {
        $this->base = $base;
        $this->radix = new Math_BigInteger(strlen($base));
        $this->bi256 = new Math_BigInteger(256);
        $this->zero = new Math_BigInteger(0);
        $this->one = new Math_BigInteger(1);
    }

    public function encode($text) {
        $big = $this->one;
        for ($j = 0; $j < strlen($text); $j++) {
            $big = $big->multiply($this->bi256)->add(new Math_BigInteger(ord($text[$j])));
        }
        $result = "";
        while (!$this->zero->equals($big)) {
            $parts = $big->divide($this->radix);
            $small = intval($parts[1]->toString());
            $big = $parts[0];
            $result = $this->base[$small] . $result;
        }
        return $result;
    }

    public function decode($text) {
        $big = $this->zero;
        for ($j = 0; $j < strlen($text); $j++) {
            $i = strpos($this->base, $text[$j]);
            $big = $big->multiply($this->radix)->add(new Math_BigInteger($i));
        }
        $result = "";
        while (!$this->zero->equals($big)) {
            $parts = $big->divide($this->bi256);
            $small = $parts[1]->toBytes();
            $big = $parts[0];
            $result = $small . $result;
        }
        return substr($result, 1);
     }
}

?>

Mode of use:

// Passa o alfabeto como parâmetro. Tem 62 caracteres aqui, então são 62 símbolos.
$k = new BaseN("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
$x = "The quick brown fox jumps over a lazy dog";
echo $x . "\n";
$c = $k->encode($x);
echo $c . "\n"; // Escreve "1u9WLfG65OMtVkQWPtWDcC6o8IjI5td5l9DzpilIK4Nyx81tKLRrStPj"
$d = $k->decode($c);
echo $d . "\n"; // Escreve "The quick brown fox jumps over a lazy dog"

See here in ideone (don’t be alarmed by the size of the code, I had to put the class BigInteger entire there).

In Java

And if anyone is interested, I also implemented it in Java. Here’s the code:

import java.util.List;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;

/**
 * @author Victor
 */
public class BaseN {
    private static final BigInteger BI_256 = BigInteger.valueOf(256);

    private final String base;
    private final BigInteger radix;

    public BaseN(String base) {
        this.base = base;
        this.radix = BigInteger.valueOf(base.length());
    }

    public String encode(String text) {
        byte[] bytes = text.getBytes();
        BigInteger big = BigInteger.ONE;
        for (byte b : bytes) {
            big = big.multiply(BI_256).add(BigInteger.valueOf(b));
        }
        StringBuilder sb = new StringBuilder(bytes.length * 4 / 3 + 2);
        while (!BigInteger.ZERO.equals(big)) {
            BigInteger[] parts = big.divideAndRemainder(radix);
            int small = parts[1].intValue();
            big = parts[0];
            sb.append(base.charAt(small));
        }

        return sb.reverse().toString();
    }

    public String decode(String text) {
        BigInteger big = BigInteger.ZERO;
        for (char c : text.toCharArray()) {
            int i = base.indexOf(c);
            if (i == -1) throw new IllegalArgumentException();
            big = big.multiply(radix).add(BigInteger.valueOf(i));
        }

        List<Byte> byteList = new ArrayList<>(text.length());
        while (!BigInteger.ZERO.equals(big)) {
            BigInteger[] parts = big.divideAndRemainder(BI_256);
            int small = parts[1].intValue();
            big = parts[0];
            byteList.add((byte) small);
        }
        Collections.reverse(byteList);

        byte[] r = new byte[byteList.size() - 1];
        int i = 0;
        for (Byte b : byteList) {
            if (i > 0) r[i - 1] = b;
            i++;
        }
        return new String(r);
    }
}

Mode of use:

public class Main {
    public static void main(String[] args) {
        // Passa o alfabeto como parâmetro. Tem 62 caracteres aqui, então são 62 símbolos.
        BaseN bn = new BaseN("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz");
        String x = "The quick brown fox jumps over a lazy dog";
        System.out.println(x);
        String a = bn.encode(x);
        System.out.println(a); // Escreve "1u9WLfG65OMtVkQWPtWDcC6o8IjI5td5l9DzpilIK4Nyx81tKLRrStPj"
        String b = bn.decode(a);
        System.out.println(b); // Escreve "The quick brown fox jumps over a lazy dog"
    }
}

See here in ideone.

Answer 2

You cannot have something represented in Base64 with just this character range (A-Z, a-z and 0-9) as this range has only 62 characters and Base64 requires 64 distinct representations.

So if you don’t want the characters + and / in its representation in Base64, you will need to replace them with something else outside this range. You will have to choose a replacement for the = also because it can appear in a representation in Base64 in order to complete the size of the last block.

What has been used in practice, when the need for example to include a Base64 representation in a URL, is to replace the set {+ / =} for {- _ ,}, respectively.

In a quick search, it seemed to me that PHP doesn’t natively have a function for this, so you’ll have to implement your own.

Even if your intention is not to use in URL, this idea should suit you:

function base64url_encode($plainText) {

    $base64 = base64_encode($plainText);
    $base64url = strtr($base64, '+/=', '-_,');
    return $base64url;   
}

function base64url_decode($plainText) {

    $base64url = strtr($plainText, '-_,', '+/=');
    $base64 = base64_decode($base64url);
    return $base64;   
}

Update: It just occurred to me too that you can convert your bytes to Hexadecimal, which is represented only by 0-9 and A-F. The resulting string is much larger than in the Base64 representation, but it may suit you. I don’t know PHP function that does this but the logic of converting bytes to hexadecimal is quite simple.