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(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(string 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     unittest
143     {
144         import crypto.base58;
145 
146         string str = Base58.encode(cast(byte[]) "abcdef1234");
147         writeln(str);
148         byte[] buf = Base58.decode(str);
149         writeln(cast(string) buf);
150     }
151 }