Java Base57 구현

2022-10-08

들어가며

암호화한 결과를 ASCII 문자로 나타내야 할 일이 있었다. 그런데 Base64는 일부 특수문자까지 사용하여 이를 제외하고 숫자와 알파벳으로만 구성하고 싶었다.

쓸 수 있는 문자 수는 숫자 10개, 알파벳 대문자 26개, 알파벳 소문자 26개로 총 62개. 다만 단지 자동화 처리 용도가 아닌, 사람이 볼 수 있어야 하여 비슷해 보이는 문자들은 제거하려 했다.

이를 위해 처음에는 Base58을 그대로 사용하려 했다. 그렇다면 long 길이인 8B(64bit)를 표시하는 데에 몇 개의 문자가 필요한지 계산해 보았다.

즉 11개의 문자가 필요하다.

그런데 57종류의 문자만 사용하더라도 11개의 문자가 필요함을 알 수 있다. ()

따라서 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에 음수가 있는지 검사하는 과정을 거칠 수밖에 없다.

Long#toString(long, int)

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 환경에서 실행한다.

v1: BigInteger

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));
}

v2: PositiveBigInteger

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));
}

v3: LongAndSubtract

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처럼 풀세트로 다 만들어보고 싶다.

돌아가기