1 module crypto.base58;
2
3 import std.bigint;
4 import std.conv;
5
6 public class Base58
7 {
8 public static char[] ALPHABET = cast(char[]) "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
9 private static int[] INDEXES = new int[128];
10
11 static this()
12 {
13 for (int i = 0; i < INDEXES.length; i++)
14 {
15 INDEXES[i] = -1;
16 }
17
18 for (int i = 0; i < ALPHABET.length; i++)
19 {
20 INDEXES[ALPHABET[i]] = i;
21 }
22 }
23
24 /// Encodes the given bytes as a base58 string (no checksum is appended).
25 public static string encode(in byte[] inp)
26 {
27 if (inp.length == 0)
28 {
29 return "";
30 }
31 // Count leading zeros.
32 int zeros = 0;
33 while (zeros < inp.length && inp[zeros] == 0)
34 {
35 ++zeros;
36 }
37 // Convert base-256 digits to base-58 digits (plus conversion to ASCII characters)
38 auto input = new byte[inp.length];
39 input[0 .. inp.length] = inp[0 .. $]; // since we modify it in-place
40 auto encoded = new char[input.length * 2]; // upper bound
41 auto outputStart = encoded.length;
42
43 for (int inputStart = zeros; inputStart < input.length;)
44 {
45 encoded[--outputStart] = ALPHABET[divmod(input, inputStart, 256, 58)];
46
47 if (input[inputStart] == 0)
48 {
49 ++inputStart; // optimization - skip leading zeros
50 }
51 }
52 // Preserve exactly as many leading encoded zeros in output as there were leading zeros in input.
53 while (outputStart < encoded.length && encoded[outputStart] == ALPHABET[0])
54 {
55 ++outputStart;
56 }
57
58 while (--zeros >= 0)
59 {
60 encoded[--outputStart] = ALPHABET[0];
61 }
62 // Return encoded string (including encoded leading zeros).
63 return encoded[outputStart .. encoded.length].to!string();
64 }
65
66 /// Decodes the given base58 string into the original data bytes.
67 public static byte[] decode(in char[] input)
68 {
69 if (input.length == 0)
70 {
71 return new byte[0];
72 }
73 // Convert the base58-encoded ASCII chars to a base58 byte sequence (base58 digits).
74 byte[] input58 = new byte[input.length];
75
76 for (int i = 0; i < input.length; ++i)
77 {
78 char c = input[i];
79 int digit = c < 128 ? INDEXES[c] : -1;
80
81 if (digit < 0)
82 {
83 throw new Exception("Illegal character " ~ c ~ " at position " ~ to!string(i));
84 }
85
86 input58[i] = cast(byte) digit;
87 }
88 // Count leading zeros.
89 int zeros = 0;
90 while (zeros < input58.length && input58[zeros] == 0)
91 {
92 ++zeros;
93 }
94 // Convert base-58 digits to base-256 digits.
95 byte[] decoded = new byte[input.length];
96 int outputStart = cast(int) decoded.length;
97
98 for (int inputStart = zeros; inputStart < input58.length;)
99 {
100 decoded[--outputStart] = divmod(input58, inputStart, 58, 256);
101
102 if (input58[inputStart] == 0)
103 {
104 ++inputStart; // optimization - skip leading zeros
105 }
106 }
107 // Ignore extra leading zeroes that were added during the calculation.
108 while (outputStart < decoded.length && decoded[outputStart] == 0)
109 {
110 ++outputStart;
111 }
112 // Return decoded data (including original number of leading zeros).
113 return decoded[outputStart - zeros .. decoded.length];
114 }
115
116 private static BigInt decodeToBigInteger(string input)
117 {
118 return BigInt(cast(string) decode(input));
119 }
120
121 /++
122 Divides a number, represented as an array of bytes each containing a single digit
123 in the specified base, by the given divisor. The given number is modified in-place
124 to contain the quotient, and the return value is the remainder.
125 +/
126 private static byte divmod(byte[] number, int firstDigit, int base, int divisor)
127 {
128 // this is just long division which accounts for the base of the input digits
129 int remainder = 0;
130
131 for (int i = firstDigit; i < number.length; i++)
132 {
133 int digit = cast(int) number[i] & 0xFF;
134 int temp = remainder * base + digit;
135 number[i] = cast(byte)(temp / divisor);
136 remainder = temp % divisor;
137 }
138
139 return cast(byte) remainder;
140 }
141 }
142
143 unittest
144 {
145 string data = "abcdef1234";
146 string en = Base58.encode(cast(byte[]) data);
147 byte[] de = Base58.decode(en);
148 assert(data == cast(string) de);
149 }