Base32의 모든 것

[YoungSeokHong]

제가 Discussion으로 시행착오를 너무 많이하면서 Base32를 만들어서 읽다가 헷갈리시는 분들이 계실까봐 Base32에 대한 내용을 정리해봤습니다.

1. Base32

1.1. Base16과의 차이

여러 멘티님들께서 Euphony 코드를 다뤄보시다가 자연스럽게 아셨듯이 우리가 주로 사용하는 자료형(?)에는 HexVector가 있습니다. HexVector에는 정보들이 모두 16진수로 저장되고 Base16도 16진수로 이루어져 있으므로 Base16에서 HexVector를 불러올 때는 진수변환이 필요 없습니다. 코드도 보시면 Base16.cpp가 가장 간단하게 이루어져있죠.
하지만, 우리는 어떤 이유에서 Base32, Base64를 사용해서 16진수를 32진수, 64진수로 바꿔줄 것입니다. 따라서 Base32의 주요 기능은 16진수를 32진수로 바꿔주는 계산기라고 보시면 됩니다. 그러면 왜 굳이 16진수를 32진수로 바꿔줄까요? 그 이유에 대해서는 바로 아래서 다루겠습니다.😀

1.2. 16진수와 32진수 (압축)

멘토님께서 회의 중에 말씀하셨듯이 Base16이냐 Base32냐의 차이는 단지 이진수로 표현된 수를 4개씩 끊어 읽냐 5개씩 끊어 읽냐의 차이입니다.

예를 들어 01100100111010110011이 있을 때,
16진수는 0110 0100 1110 1011 0011즉 '64eb3',
32진수는 01100 10011 10101 10011 즉 'cjlj'가 됩니다.

이 때, 16진수는 5글자이지만 32진수는 4글자가 됩니다. 여기서 우리는 5n개의 글자가 4n개의 글자로 변하는 20%의 압축효과를 볼 수 있습니다. 우리가 16진수를 32진수로 변환해서 사용하는 이유가 여기에 있습니다. 이렇게 되면 통신을 할 때 더 짧은 정보를 보내도 되니까 자연스럽게 통신의 속도가 빨라지는 효과를 볼 수 있겠죠.😀

1.3. 진수 변환 방법

앞서 말한 예시처럼 20비트의 정보가 들어와서 4와 5로 딱 나누어 떨어지면 정말 좋겠지만, 아쉽게도 정보의 길이는 다양합니다.ㅠㅠ
정보의 길이가 [20의 배수]비트가 아니면 앞에서 본 그림과 같이 이쁘게 나누어 떨어지지 않죠.

두자리수 16진수 '0x5A'가 들어왔다고 생각해봅시다. 이 경우 0101 1010는 길이가 8인데 5로 이쁘게 나누어 떨어지지 않습니다. 나머지 3비트가 남게됩니다. 여기서 우리는 결정해야됩니다. 비트를 앞에서부터 읽어서 나머지 3비트를 뒤에다 둘 것인지, 비트를 뒤에서부터 읽어서 나머지 3비트를 앞에다 둘 것인지.

앞에서부터 읽을 경우

'0x5A' 즉 0101 1010을 읽을 때 01011010이 01011 010즉 'B2 (32)' 로 저장됩니다. 이는 전송 중에 'B2 (32)'로 이동할 것이고 도착해서는 'B2 (32)' 즉 01011 00010으로 읽힐것입니다. 이 수가 다시 비트로 읽힐 때는 0101100010으로 읽히는 정보 왜곡이 일어납니다.
이는 16진수로 앞에서 읽으면 0101 1000 10즉 '0x582'가 되고 뒤에서 읽으면 01 0110 0010즉 '0x162'로 처음 수 0x5A와는 전혀 다른 수가 되어버립니다. 절대 처음의 수로 돌아갈 수 없죠.

뒤에서부터 읽을 경우

뒤에서부터 읽을 경우, 앞에서와 같이 '0x5A' 즉 0101 1010을 읽을 때 01011010이 010 11010즉 '2Q (32)'로 저장됩니다. 이는 '2Q (32)'로 도착하고 00010 11010으로 읽힙니다. 이 수가 다시 비트로 읽힐 때는 0001011010으로 읽히기는 하지만, 16진수로 뒤에서부터 읽을 경우 (단순 32->16진수 변환) 00 0101 1010이 되는데, 앞의 00이 날아가 원래 수인 '0x5A'로 읽을 수 있습니다.😀

이 때문에 16진수에서 32진수로 변환할 때 뒤에서부터 읽는 방법을 선택했습니다. 코드 설명은 접어두겠습니다.

코드 설명

Base32.cpp의 내부 함수들입니다. 아직까지 추가적인 문제를 해결하지 못한 코드이므로 현재 올라와있는 코드와 차이가 있습니다.

원시 getBaseString함수

std::string Base32::getBaseString() {
    int sum = 0;

    int count = 0;
    for(u_int8_t hex : hexVector) {
        sum = (sum << 4) | hex;
    }

    return bitsToBase32(sum);
}

hexVector로부터 4비트씩 정보를 받아와 이어 붙이는 함수입니다.
4비트의 정보를 받아오면 기존의 sum을 << 4비트연산자로 4칸 밀어서 공간을 만들고 들어온 수(hex)는 |비트연산자를 통해서 앞서 계산한 수에 더해주도록 했습니다.

예를들어 '0x6'에 해당하는 0110이 이미 sum에 있고 그후 '0x1'에 해당하는 0001을 받은 경우, 먼저 << 4연산을 통해 sum을 01100000 즉 '0x60'으로 만들어줍니다. 그후 |연산을 통해 앞에 있는 수에 더해줍니다. 밀려난 4칸은 0이기 때문에 당연히 |연산을 해주면 앞에 수에 더해준 효과가 나겠죠. 결국 앞서 계산한 01100000과 현재 들어온 00000001의 or연산으로 두 값이 더해진 01100001을 만드는 것입니다.

bitsToBase32 함수

std::string Base32::bitsToBase32(int value){
    std::string result;
    int count = 0;
    int base32;

    for (int i = 0; i < 32; i += 5) {
        if ((value >> i) > 0) count = i / 5;
    }

    for (int i = count * 5; i >= 0; i -= 5) {
        base32 = ((value >> i) & 31);
        result.push_back(convertInt2Char(base32));
    }

    return result;
}

16진수를 32진수로 바꿔주는 사실상 핵심 함수입니다.

첫번째 for문에서 받아온 수의 길이가 5로 나눴을 경우 [몫 + 1]이 얼마인지 계산 합니다. 방법은 간단합니다. 5비트씩 밀어봐서 0인지 양수인지 확인합니다. 값이 0이 나오면 더이상 밀릴 칸이 없으므로 이전의 밀린숫자까지가 유효했다는 뜻이 됩니다.

두번째 for문에서는 방금전에 구한 값으로 뒤에서부터 5비트씩 오면서 값을 확인합니다. 확인한 값은 convertInt2Char를 통해 32진수의 수로 바뀌고 앞서 준비한 string에 차곡차곡 쌓이게 됩니다.

1.4. int의 한계와 극복방안

이제 모든 길이의 정보를 처리할 수 있게 되었지만, 아직 하나의 문제가 더 남아있습니다.
이 내용을 구현하려면 int에 들어온 정보들을 담아야하는데 int는 아시다시피 32비트의 정보밖에 담지 못합니다.ㅠㅠ 이때문에 만약 {0x61, 0x62, 0x63, 0x64, 0x65} 총 40비트의 수(혹은 그 이상)가 들어오게 되면 들어온 수를 int에 다 담아주지 못합니다. 따라서 적당한 선에서 끊어서 계산한 값을 string으로 바꿔서 저장해주고 다시 계산을 하는 작업이 필요합니다.

32진수는 5비트씩 16진수는 4비트씩 끊어서 읽으므로 4와 5의 최소공배수인 20을 사용하면 됩니다. 즉 20비트씩 끊어서 읽으면 이 문제는 해결될 수 있습니다. 이때, 아까 앞서 1.3에서 설명한 것과 같은 논리로 수는 뒤에서부터 20비트씩 끊어야합니다.

예를 들면 16진수 616263이 들어왔을 때, 6 16263으로 나눠서 앞의 6을 먼저 32진수로 계산해 String으로 변환해서 저장해주고 이후에 뒤의 16263을 32진수로 계산해 String으로 변환해서 저장해주는 것입니다.
이는 계산을 직접 해보면 쉽게 이해할 수 있습니다. '0x6'의 32진수는 '6 (32)'이고 '0x16263'의 32진수는 '2oj3 (32)'인데 '0x616263'은 이 둘을 이어붙인 '62oj3 (32)'가 됩니다.
진수변환기를 사용해서 두 세번정도 계산하시면 금방 이해하실겁니다.😀진수 변환기

코드 설명

getBaseString 함수

std::string Base32::getBaseString() {
    std::stringstream ss;
    int sum = 0;
    int rest = hexVector.getSize() % 5;

    int count = 0;
    for(u_int8_t hex : hexVector) {
        count++;
        sum = (sum << 4) | hex;
        if(count % 5 == rest) {
            ss << bitsToBase32(sum);
            sum = 0;
        }
    }

    return ss.str();
}

아까와 달라진 부분에 대해서만 설명하겠습니다. 먼저 String들을 받아서 이어붙이기 위해 String Stream인 ss를 사용했습니다.
벡터의 사이즈를 가져와 5로 나눈 뒤 나머지(뒤에서부터 끊었을 때 앞에 남는 비트의 수)를 구합니다.
for문을 돌면서 비트가 20인 경우 즉 5개의 16진수가 들어온 경우마다 bitsToBase32를 통해 32진수 String으로 바꿔준 뒤 ss에 이어붙입니다.

여기서 조건을 if(!(count % 5))(5번 마다 함수 실행)이 아닌 if(count % 5 == rest)으로 한 이유는 우리가 20비트씩 뒤에서 끊기로 했기 때문입니다. 이렇게 하면 앞에 나머지 비트를 먼저 계산하고 이후에 5비트씩 계산할 수 있습니다.

끝

---

아까 회의 끝나고 바로 만들어서 올릴려 했는데 놀다가 너무 늦게 올리네요 ㅠㅠ
언제나 그랬듯 또 너무 길게 쓴것 같습니다😥 세줄 요약하자면

1. 압축을 하기 위해 16진수를 32진수로 변환하고자한다.
2. 근데 앞에서부터 끊어서 읽어야하나 뒤에서부터 끊어서 읽어야하나.
3. 구현하려다보니 int가 32비트밖에 못 받아주기 때문에 20비트씩 끊는 방법을 선택했다.

로 볼 수 있겠습니다.😄

[jopopcorn]

우와 너무나도 친절하고 자세한 설명이네요 길게 적어주셔서 더 이해가 잘됐습니다!!
Base32 만들기 디스커션에서의 내용이 백프로 이해되지 않았는데, 이거 읽고 다시 보니 명쾌하게 이해됐습니다! 🙌🙌
유닛테스트 많이 올리고 Base64도 다같이 고민을 많이 해봐야겠네요! 구현하시느라 고생 많으셨어요! 👍👍👍

[YoungSeokHong]

감사합니다!
사실 Base64는 수만 조금 바꿔서 같은 포메이션으로 Base32를 만들 때 이미 같이 만들었습니다 ㅋㅋㅋㅋㅠㅠ
제가 조금 찾아보니까 Base64보다 더 압축할 수 있는 Base85가 있던데 혹시 관심 있으신 분은 디스커션 올려주시면 같이 열심히 개발해봤으면 좋겠습니다🚀

[psh2849]

정리해주셔서 너무 감사합니다! 어제 코드만 보고 이해하려고 하니 스스로 조금 부족한 감이 없지 않아있었는데
이렇게 정리해주셔서 쉽게 이해할 수 있었던 것 같습니다! 감사합니다!
그리고 구현하시느라 너무 고생 많으셨어요 👍 👍 👍

[YoungSeokHong]

코드도 읽어보셨군요! ㅋㅋㅋ
안그래도 코드가 너무 저 편한대로만 짜서 다른 분들이 이해하기 힘드시면 어쩌지하고 걱정했는데, 이 글을 읽고 쉽게 이해할 수 있으셨다니 정리하길 잘했다는 생각이 드네요 ㅋㅋㅋㅋ
감사합니다!

[kmsaidev]

깔끔한 정리 너무 감사합니다!
예시와 그림을 통해서 설명해주시니까 너무 이해가 잘 되네요.
정말 수고 많으셨어요!:relaxed:

[YoungSeokHong]

감사합니다!!
팀 미션하시느라 바쁘실텐데 Base32에도 관심 가져주셔서 감사합니다!
이해가 잘 되셨다니 다행이네요 ㅋㅋㅋ

[designe]

이런 친절한 정리 너무 좋네요! 👍
이걸 이해하시면 자연스럽게 BASE64도 이해가 가능한데
일상에서 쓰이는 표준 BASE64 코덱도 읽어보시고 이런 느낌으로다가 정리해주실 수 있는 분 있을까요?! ㅎㅎㅎ 👍

[designe]

참고로 표준 BASE64의 경우에는 앞에서부터 6비트씩 잘라서 처리하게 됩니다.
그럼 @YoungSeokHong 님이 말씀하신대로 모든 글자들이 아름답게 바이너리 길이가
4 * 6의 배수로 끝나지 않기 때문에 남는 공간이 생겨서 정보의 왜곡 현상이 발생할 수 있어요.

그때 padding 을 통해 해결하는데요.
base64 문자열을 보다보면 마지막에 = 1개 또는 == 2개가 붙는 것을 볼 수 있는데
=은 참고로 base64에서는 0으로 해석됩니다. 0으로 채운다는 의미에요.
=의 개수를 통해 0이 몇개가 붙었는지 디코더 측에서 예상가능하게 만들어줍니다.

=의 역할이 바로 패딩인데 한번 base64 codec 변환기 같은거 써보시면서
기존에 어떻게 해결했었는지 살펴보는 것도 좋은 공부가 될 것 같습니다 :)

[YoungSeokHong]

안그래도 Hex to Base64 계산기가 있길래 Base64 Test Case만들 때 사용해봤더니 자꾸 다른 숫자가 나오고 '='으로 padding이 되더라고요 ㅋㅋㅋㅋ 이게 인코딩 방식의 차이 때문이었군요!
'='으로 0의 갯수를 미리 알려줘서 문자를 꽉채워서 보내는 방법도 굉장히 좋네요! 이걸 빨리 생각해냈으면 좋았을 텐데 ㅋㅋㅋ 감사합니다! 새로운 사실 배워갑니다!

[designe]

padding도 좋고
마지막 문자는 반대로 저장하는 방식을 취하면 따로 추가적인 패딩 문자가 없어도 앞에서부터도 인식해도 문제는 없을 것 같아요.
영석님이 만드신 패치를 추가적인 문자가 없이도 잘된다는 점을 강조해서 뛰어나다! 라고 해도 좋을 것 같습니다 ㅎㅎ :)

[dlwlstks96]

@YoungSeokHong
이해하기 쉽게 설명해주셔서 감사합니다!! 코드 리뷰해보려고 이전 디스커션 읽어보던 중
막히는 부분들이 많았는데 해결되었습니다!!
정말 너무 고생하셨습니다 멋지십니다:)

[YoungSeokHong]

감사합니다! 도움이 됐다니 기분이 좋네요!
아직 제가 만든 Base32도 보시면 5비트씩 끊어읽을 때 5를 한 번에 변수 선언해서 계속 사용하지 않고 일일히 쓸 때 마다 5를 입력하는 등 소소한 문제들이 몇가지 있습니다. 제가 발견하지 못한 문제들이 있을 수도 있고요!
진산님께서 같이 코드 뜯어 보시면서 이런 유지보수성과 같은 비기능을 향상시키는데 도움을 주시면 감사하겠습니다!

[dlwlstks96]

네 알겠습니다!! 💪💪

[YoungSeokHong]

32진수는 5비트씩 16진수는 4비트씩 끊어서 읽으므로 4와 5의 최대공약수인 20을 사용하면 됩니다

오늘 다른거 하다가 갑자기 생각나서 봤더니 최소공배수가 아니라 최대공약수로 돼있네요 ㅋㅋㅋㅋㅋㅋㅋㅋ😂
먼저 읽으신 분들 오해있으실까봐 올립니다! 최대공약수가 아니라 최소공배수입니다!
중학교 수학부터 다시 배워야겠네요ㅠㅠ

[judemin]

한눈에 보기 쉽게 정리해주신 자료 정말 감사합니다!!