Base58.java

/*
 * Copyright (C) 2019 sw4j.org
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.sw4j.tool.barcode.random.coder;

import java.util.Arrays;

/**
 * <p>
 * This utility class implements a base58 encoding with the alphabet from bitcoin.
 * </p>
 * <p>
 * This class is thread safe.
 * </p>
 * @author Uwe Plonus &lt;u.plonus@gmail.com&gt;
 */
public final class Base58 {

    /**
     * <p>
     * The number of ASCII characters, used for the reverse lookup array.
     * </p>
     */
    private static final int NUMBER_ASCII_CHARS = 128;

    /**
     * <p>
     * The base of a byte (256).
     * </p>
     */
    private static final int BYTE_BASE = 256;

    /**
     * <p>
     * The base of a character in the base58 string.
     * </p>
     */
    private static final int BASE = 58;

    /**
     * <p>
     * The bit mask to mask a single byte out of a larger integer number.
     * </p>
     */
    private static final int BYTE_MASK = 0xff;

    /**
     * <p>
     * The alphabet to use for the base58 encoding.
     * </p>
     */
    private static final char[] ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz".toCharArray();

    /**
     * <p>
     * The reverse lookup for the {@link #ALPHABET}.
     * </p>
     */
    private static final int[] INDEX = new int[NUMBER_ASCII_CHARS];

    /**
     * <p>
     * Static initializer to setup the reverse lookup table.
     * </p>
     */
    static {
        for (int i = 0; i < INDEX.length; i++) {
            INDEX[i] = -1;
        }
        for (int i = 0; i < ALPHABET.length; i++) {
            INDEX[ALPHABET[i]] = i;
        }
    }

    /**
     * <p>
     * Hidden default constructor for this utility class.
     * </p>
     */
    private Base58() {
    }

    /**
     * <p>
     * Convert the data into a Base58 string.
     * </p>
     * @param data the data to encode.
     * @return the encoded data.
     */
    public static String encode(final byte[] data) {
        StringBuilder result = new StringBuilder();
        byte[] copy = Arrays.copyOf(data, data.length);
        int leadingZeros = leadingZeros(data);
        boolean done = (copy.length == 0 || copy.length == leadingZeros);
        while (!done) {
            byte remainder = divide(copy, BYTE_BASE, BASE);
            result.insert(0, ALPHABET[remainder]);
            done = true;
            for (int i = 0; i < copy.length; i++) {
                done = done & (copy[i] == 0);
            }
        }
        for (int i = 0; i < leadingZeros; i++) {
            result.insert(0, ALPHABET[0]);
        }
        return result.toString();
    }

    /**
     * <p>
     * Helper method to count the number of leading zero values in a byte array.
     * </p>
     * @param data the byte array to inspect.
     * @return the number of leading zero bytes in the array.
     */
    private static int leadingZeros(final byte[] data) {
        int leadingZeros = 0;
        boolean foundNonZero = false;
        for (int i = 0; !foundNonZero && i < data.length; i++) {
            if (data[i] == 0) {
                leadingZeros++;
            } else {
                foundNonZero = true;
            }
        }
        return leadingZeros;
    }

    /**
     * <p>
     * Convert the Base58 string into a byte array.
     * </p>
     * @param data the base58 string to convert back into a byte array.
     * @return the decoded data.
     */
    public static byte[] decode(final String data) {
        byte[] input = new byte[data.length()];
        byte[] output = new byte[data.length()];
        for (int i = 0; i < data.length(); i++) {
            char c = data.charAt(i);
            int digit = c < NUMBER_ASCII_CHARS ? INDEX[c] : -1;
            if (digit < 0) {
                throw new IllegalArgumentException(String.format("The digit '%c' is not recognized.", c));
            }
            input[i] = (byte)digit;
        }
        int leadingZeros = leadingZeros(input);
        int outputIndex = output.length;
        int zeros = leadingZeros(input);
        while (zeros < input.length) {
            byte remainder = divide(input, BASE, BYTE_BASE);
            output[--outputIndex] = remainder;
            zeros = leadingZeros(input);
        }
        return Arrays.copyOfRange(output, outputIndex - leadingZeros, output.length);
    }

    /**
     * <p>
     * A helper method to divide the dividend (in the byte array) by a divisor. The elements of the byte array are
     * treated as figures to the given base.
     * </p>
     * @param dividend the dividend of the division. Contains the quotient of the division after the method is finished.
     * @param base the base (max 256) of the digits in the number (each element is a digit).
     * @param divisor the divisor (max 256) of the division.
     * @return the remainder of the division.
     */
    public static byte divide(final byte[] dividend, final int base, final int divisor) {
        if (divisor == 0) {
            throw new IllegalArgumentException("The divisor may not be 0.");
        }
        int remainder = 0;
        for (int i = 0; i < dividend.length; i++) {
            int digit = (int)(dividend[i] & BYTE_MASK);
            if (digit > base) {
                throw new IllegalArgumentException(
                        String.format("The digit at place %d (%d) is larger than the base %d.", i, digit, base));
            }
            int temp = remainder * base + digit;
            dividend[i] = (byte)(temp / divisor);
            remainder = temp % divisor;
        }
        return (byte)remainder;
    }

}