1 /*
2 * Copyright (C) 2019 sw4j.org
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17 package org.sw4j.tool.barcode.random.coder;
18
19 import java.util.Arrays;
20
21 /**
22 * <p>
23 * This utility class implements a base58 encoding with the alphabet from bitcoin.
24 * </p>
25 * <p>
26 * This class is thread safe.
27 * </p>
28 * @author Uwe Plonus <u.plonus@gmail.com>
29 */
30 public final class Base58 {
31
32 /**
33 * <p>
34 * The number of ASCII characters, used for the reverse lookup array.
35 * </p>
36 */
37 private static final int NUMBER_ASCII_CHARS = 128;
38
39 /**
40 * <p>
41 * The base of a byte (256).
42 * </p>
43 */
44 private static final int BYTE_BASE = 256;
45
46 /**
47 * <p>
48 * The base of a character in the base58 string.
49 * </p>
50 */
51 private static final int BASE = 58;
52
53 /**
54 * <p>
55 * The bit mask to mask a single byte out of a larger integer number.
56 * </p>
57 */
58 private static final int BYTE_MASK = 0xff;
59
60 /**
61 * <p>
62 * The alphabet to use for the base58 encoding.
63 * </p>
64 */
65 private static final char[] ALPHABET = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz".toCharArray();
66
67 /**
68 * <p>
69 * The reverse lookup for the {@link #ALPHABET}.
70 * </p>
71 */
72 private static final int[] INDEX = new int[NUMBER_ASCII_CHARS];
73
74 /**
75 * <p>
76 * Static initializer to setup the reverse lookup table.
77 * </p>
78 */
79 static {
80 for (int i = 0; i < INDEX.length; i++) {
81 INDEX[i] = -1;
82 }
83 for (int i = 0; i < ALPHABET.length; i++) {
84 INDEX[ALPHABET[i]] = i;
85 }
86 }
87
88 /**
89 * <p>
90 * Hidden default constructor for this utility class.
91 * </p>
92 */
93 private Base58() {
94 }
95
96 /**
97 * <p>
98 * Convert the data into a Base58 string.
99 * </p>
100 * @param data the data to encode.
101 * @return the encoded data.
102 */
103 public static String encode(final byte[] data) {
104 StringBuilder result = new StringBuilder();
105 byte[] copy = Arrays.copyOf(data, data.length);
106 int leadingZeros = leadingZeros(data);
107 boolean done = (copy.length == 0 || copy.length == leadingZeros);
108 while (!done) {
109 byte remainder = divide(copy, BYTE_BASE, BASE);
110 result.insert(0, ALPHABET[remainder]);
111 done = true;
112 for (int i = 0; i < copy.length; i++) {
113 done = done & (copy[i] == 0);
114 }
115 }
116 for (int i = 0; i < leadingZeros; i++) {
117 result.insert(0, ALPHABET[0]);
118 }
119 return result.toString();
120 }
121
122 /**
123 * <p>
124 * Helper method to count the number of leading zero values in a byte array.
125 * </p>
126 * @param data the byte array to inspect.
127 * @return the number of leading zero bytes in the array.
128 */
129 private static int leadingZeros(final byte[] data) {
130 int leadingZeros = 0;
131 boolean foundNonZero = false;
132 for (int i = 0; !foundNonZero && i < data.length; i++) {
133 if (data[i] == 0) {
134 leadingZeros++;
135 } else {
136 foundNonZero = true;
137 }
138 }
139 return leadingZeros;
140 }
141
142 /**
143 * <p>
144 * Convert the Base58 string into a byte array.
145 * </p>
146 * @param data the base58 string to convert back into a byte array.
147 * @return the decoded data.
148 */
149 public static byte[] decode(final String data) {
150 byte[] input = new byte[data.length()];
151 byte[] output = new byte[data.length()];
152 for (int i = 0; i < data.length(); i++) {
153 char c = data.charAt(i);
154 int digit = c < NUMBER_ASCII_CHARS ? INDEX[c] : -1;
155 if (digit < 0) {
156 throw new IllegalArgumentException(String.format("The digit '%c' is not recognized.", c));
157 }
158 input[i] = (byte)digit;
159 }
160 int leadingZeros = leadingZeros(input);
161 int outputIndex = output.length;
162 int zeros = leadingZeros(input);
163 while (zeros < input.length) {
164 byte remainder = divide(input, BASE, BYTE_BASE);
165 output[--outputIndex] = remainder;
166 zeros = leadingZeros(input);
167 }
168 return Arrays.copyOfRange(output, outputIndex - leadingZeros, output.length);
169 }
170
171 /**
172 * <p>
173 * A helper method to divide the dividend (in the byte array) by a divisor. The elements of the byte array are
174 * treated as figures to the given base.
175 * </p>
176 * @param dividend the dividend of the division. Contains the quotient of the division after the method is finished.
177 * @param base the base (max 256) of the digits in the number (each element is a digit).
178 * @param divisor the divisor (max 256) of the division.
179 * @return the remainder of the division.
180 */
181 public static byte divide(final byte[] dividend, final int base, final int divisor) {
182 if (divisor == 0) {
183 throw new IllegalArgumentException("The divisor may not be 0.");
184 }
185 int remainder = 0;
186 for (int i = 0; i < dividend.length; i++) {
187 int digit = (int)(dividend[i] & BYTE_MASK);
188 if (digit > base) {
189 throw new IllegalArgumentException(
190 String.format("The digit at place %d (%d) is larger than the base %d.", i, digit, base));
191 }
192 int temp = remainder * base + digit;
193 dividend[i] = (byte)(temp / divisor);
194 remainder = temp % divisor;
195 }
196 return (byte)remainder;
197 }
198
199 }