암호화한 결과를 ASCII 문자로 나타내야 할 일이 있었다. 그런데 Base64는 일부 특수문자까지 사용하여 이를 제외하고 숫자와 알파벳으로만 구성하고 싶었다.
쓸 수 있는 문자 수는 숫자 10개, 알파벳 대문자 26개, 알파벳 소문자 26개로 총 62개. 다만 단지 자동화 처리 용도가 아닌, 사람이 볼 수 있어야 하여 비슷해 보이는 문자들은 제거하려 했다.
이를 위해 처음에는 Base58을 그대로 사용하려 했다. 그렇다면 long 길이인 8B(64bit)를 표시하는 데에 몇 개의 문자가 필요한지 계산해 보았다.
\[\log_{58} 2^{64} = {\log 2^{64} \over \log 58} = {\log 2 \times 64 \over \log 58} \simeq 10.925\]
즉 11개의 문자가 필요하다.
그런데 57종류의 문자만 사용하더라도 11개의 문자가 필요함을 알 수 있다. (\({\log 2 \times 64 \over \log 57} \simeq 10.972\))
따라서 Base58에서 역시 혼동될 수 있는 '1'까지 빼서 57종류의 문자만 사용하기로 했고, 이를 Base57로 이름 지었다.
계산해보면 패딩과 줄 바꿈을 고려하지 않을 때 Base64는 3바이트를 4바이트로 인코딩하므로 33%의 용량 증가가 있고, Base57은 8바이트를 11바이트로 인코딩하므로 37.5%의 용량 증가가 있다.
마땅한 방법이 없어 직접 구현하기로 했다. 참고한 소스는 JDK의 Long#toString(long, int) 이다. JDK 9 이상에서는 COMPACT_STRINGS 가지고 분기가 들어가는데 크게 다르지는 않다. 물론 변환한 값은 Compact String에 적합하지만, StringLatin1의 instance를 직접 생성할 수 없어 String 생성자에서 주어진 byte array에 음수가 있는지 검사하는 과정을 거칠 수밖에 없다.
openjdk/jdk@319a3b9/jdk/src/share/classes/java/lang/Long.java#L115-L139
public static String toString(long i, int radix) {
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
radix = 10;
if (radix == 10)
return toString(i);
char[] buf = new char[65];
int charPos = 64;
boolean negative = (i < 0);
if (!negative) {
i = -i;
}
while (i <= -radix) {
buf[charPos--] = Integer.digits[(int)(-(i % radix))];
i = i / radix;
}
buf[charPos] = Integer.digits[(int)(-i)];
if (negative) {
buf[--charPos] = '-';
}
return new String(buf, charPos, (65 - charPos));
}가장 큰 문제는 Java에 unsigned long이 없다는 점이다. 이를 해결한 방법을 따라가 본다.
코드는 의도적으로 main set과 test set을 섞어 썼다. 테스트는 JUnit 5, AssertJ 3 환경에서 실행한다.
private static final char[] DigitsBase57 = "23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz".toCharArray();
private static final int Base57Radix = 57;
private static final BigInteger UNSIGNED_LONG_MAX = BigInteger.ONE.shiftLeft(64);
private static final BigInteger Base57RadixB = BigInteger.valueOf(Base57Radix);
private static final BigInteger NegatedBase57RadixB = Base57RadixB.negate();
public static String toBase57UsingBigInteger(long i) {
BigInteger bi = BigInteger.valueOf(i);
if (bi.signum() < 0) {
bi = bi.add(UNSIGNED_LONG_MAX);
}
return toBase57(bi);
}
/**
* {@link Long#toString(long, int)}의 동작을 BigInteger로 그대로 모방
*/
public static String toBase57(BigInteger i) {
byte[] buf = new byte[65];
int charPos = 64;
boolean negative = (i.signum() < 0);
if (!negative) {
i = i.negate();
}
while (i.compareTo(NegatedBase57RadixB) <= 0) {
buf[charPos--] = (byte) DigitsBase57[-i.remainder(Base57RadixB).intValueExact()];
i = i.divide(Base57RadixB);
}
buf[charPos] = (byte) DigitsBase57[-i.intValueExact()];
if (negative) {
buf[--charPos] = '-';
}
return new String(buf, charPos, (65 - charPos));
}public static String toBase57UsingPositiveBigInteger(long i) {
BigInteger bi = BigInteger.valueOf(i);
if (bi.signum() < 0) {
bi = bi.add(UNSIGNED_LONG_MAX);
}
return toBase57FromPositive(bi);
}
/**
* {@link #toBase57}이 입력으로 unsigned long 범위만 받으므로 {@link BigInteger#negate} 호출 제거,
* 배열 길이 한정으로 약간의 최적화
*/
public static String toBase57FromPositive(BigInteger i) {
byte[] buf = new byte[11];
int charPos = 10;
while (i.compareTo(Base57RadixB) >= 0) {
buf[charPos--] = (byte) DigitsBase57[i.remainder(Base57RadixB).intValueExact()];
i = i.divide(Base57RadixB);
}
buf[charPos] = (byte) DigitsBase57[i.intValueExact()];
return new String(buf, charPos, (11 - charPos));
}private static final byte[] UNSIGNED_LONG_MAX_IN_BASE57 = {50, 54, 18, 47, 27, 40, 18, 12, 20, 11, 55};
/**
* long 특성상 음수가 있을 수 있으므로, 변환한 후 음수라면
* 2^64를 Base57로 변환한 각 자리 ordinal인 {@link #UNSIGNED_LONG_MAX_IN_BASE57}에서 빼준다.
* <p>
* 2^64 = 18,446,744,073,709,551,616
* <p>
* 57^11 = 20,635,899,893,042,801,193
*
* @see Long#toString(long, int)
*/
public static String toBase57(long i) {
byte[] buf = new byte[11];
int charPos = 10;
boolean negative = (i < 0);
if (!negative) {
i = -i;
}
while (i <= -Base57Radix) {
buf[charPos--] = (byte) (-(i % Base57Radix));
i = i / Base57Radix;
}
buf[charPos] = (byte) (-i);
if (negative) {
for (int j = 10; j >= 0; j--) {
buf[j] = (byte) (UNSIGNED_LONG_MAX_IN_BASE57[j] - buf[j]);
if (buf[j] < 0) {
buf[j] += Base57Radix;
buf[j - 1]++;
}
}
charPos = 0;
}
for (int j = charPos; j < 11; j++) {
buf[j] = (byte) DigitsBase57[buf[j]];
}
return new String(buf, charPos, (11 - charPos));
}JEP 378: Text Blocks를 사용하였기에 JDK 15+에서만 실행할 수 있다.
/**
* @param description 단순 케이스 설명으로, assertion에 사용되지 않음
* @param i unsigned long, 입력 가능 범위 0 ~ 2^64-1
* @param empty Spock data table의 double pipe symbol 형태 사용을 위해 있는 placeholder 역할
* @param expectedLong 해당 8바이트를 long으로 변환한 값 = 계산에 실제로 사용되는 값
* @param expectedBase57 해당 8바이트를 Base57로 변환한 값; 피드백 ID로 사용할 때에는 길이 11, 문자 '2'로 leftPad 필요
*/
@ParameterizedTest
@CsvSource(delimiter = '|', textBlock = """
ZERO | 0 || 0 | 2
ONE | 1 || 1 | 3
RADIX | 57 || 57 | 32
RADIX SQUARE | 3249 || 3249 | 322
RADIX CUBIC - 1 | 185192 || 185192 | zzz
MILLION | 1000000 || 1000000 | 7Qns
BILLION | 1000000000 || 1000000000 | 3fjn2f
TRILLION | 1000000000000 || 1000000000000 | XAyr9Q9
QUADRILLION | 1000000000000000 || 1000000000000000 | AyYYjPd8p
QUINTILLION | 1000000000000000000 || 1000000000000000000 | 4mTKn4xF9S3
LONG_MAX | 9223372036854775807 || 9223372036854775807 | TVBRkNB8C7y
LONG_MAX + 1 | 9223372036854775808 || -9223372036854775808 | TVBRkNB8C7z
LONG_MAX + 2 | 9223372036854775809 || -9223372036854775807 | TVBRkNB8C82
UNSIGNED_LONG_MAX - 1 | 18446744073709551614 || -2 | txLqViLENDw
UNSIGNED_LONG_MAX | 18446744073709551615 || -1 | txLqViLENDx
""")
void testBase57(String description, BigInteger i, String empty, long expectedLong, String expectedBase57) {
long longValue = i.longValue();
if (i.signum() > 0 && expectedLong < 0) {
Assertions.assertThatThrownBy(i::longValueExact).isInstanceOf(ArithmeticException.class);
}
Assertions.assertThat(longValue).isEqualTo(expectedLong);
Assertions.assertThat(toBase57(longValue))
.isEqualTo(expectedBase57)
.isEqualTo(toBase57UsingBigInteger(longValue))
.isEqualTo(toBase57UsingPositiveBigInteger(longValue));
}
/**
* {@link #UNSIGNED_LONG_MAX_IN_BASE57}이 2^64 값을 잘 가지고 있는지 확인한다.
*/
@Test
void testUnsignedLongMaxInBase57Constant() {
BigInteger i = UNSIGNED_LONG_MAX;
byte[] buf = new byte[65];
int charPos = 64;
boolean negative = (i.signum() < 0);
if (!negative) {
i = i.negate();
}
while (i.compareTo(NegatedBase57RadixB) <= 0) {
buf[charPos--] = (byte) -i.remainder(Base57RadixB).intValueExact();
i = i.divide(Base57RadixB);
}
buf[charPos] = (byte) -i.intValueExact();
for (int j = charPos; j < 65; j++) {
Assertions.assertThat(buf[j]).isEqualTo(UNSIGNED_LONG_MAX_IN_BASE57[j - charPos]);
}
}List.of()를 사용하였기에 JDK 9+에서만 실행할 수 있다.
/**
* <table>
* <tr><th> Iteration </th><th> BigInteger </th><th> PositiveBigInteger </th><th> LongAndSubtract </th></tr>
* <tr><td> 1,000,000 </td><td> 1045ms </td><td> 853ms </td><td> 95ms </td></tr>
* <tr><td> 5,000,000 </td><td> 4527ms </td><td> 4256ms </td><td> 321ms </td></tr>
* <tr><td> 10,000,000 </td><td> 9044ms </td><td> 8464ms </td><td> 592ms </td></tr>
* <tr><td> 30,000,000 </td><td> 26690ms </td><td> 25274ms </td><td> 1815ms </td></tr>
* </table>
*/
@Test
void benchmarkBase57() {
List<Pair<String, LongFunction<String>>> targets = List.of(
Pair.of("BigInteger", Base57::toBase57UsingBigInteger),
Pair.of("PositiveBigInteger", Base57::toBase57UsingPositiveBigInteger),
Pair.of("LongAndSubtract", Base57::toBase57)
);
System.out.println("<table>");
System.out.print("<tr><th> Iteration </th>");
targets.forEach(target -> System.out.printf("<th> %s </th>", target.getFirst()));
System.out.println("</tr>");
ThreadLocalRandom random = ThreadLocalRandom.current();
for (int count : List.of(1_000_000, 5_000_000, 10_000_000, 30_000_000)) {
System.out.printf("<tr><td> %,10d </td>", count);
for (Pair<String, LongFunction<String>> target : targets) {
long start = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
target.getSecond().apply(random.nextLong());
}
long end = System.currentTimeMillis();
System.out.printf("<td> %" + (target.getFirst().length() - 2) + "dms </td>", end - start);
}
System.out.println("</tr>");
}
System.out.println("</table>");
}java.util.Base64.Encoder처럼 풀세트로 다 만들어보고 싶다.