1928. Base64 Decoder

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5PR4DKAG0DFAUq&categoryId=AV5PR4DKAG0DFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=2&pageSize=30&pageIndex=1 

SW Expert Academy

 

 

 

문제 이해

 -> 우선 24비트 버퍼에 위쪽(MSB)부터 한 byte씩 3 byte의 문자를 집어넣는다.

 -> 버퍼의 위쪽부터 6비트씩 잘라 그 값을 읽고, 각각의 값을 아래 표의 문자로 Encoding 한다.

 -> 입력으로 Base64 Encoding 된 String 이 주어졌을 때, 해당 String 을 Decoding 하여, 원문을 출력하는 프로그램

 

문제 주의

 -> 문자열의 길이는 항상 4의 배수

 -> 문자열의 길이는 100,000 이하

 

// http://minsone.github.io/programming/algorithm-base64-encoding-decoding

// https://zetawiki.com/wiki/SWEA_1928_Base64_Decoder

// 위 링크를 코드 리뷰 형식으로 문제 풀이

문제 풀이

 -> 인코딩은 8비트 x3글자를 6비트 x4글자로 변환

 -> 디코딩은 6비트 x4글자를 8비트 x3글자로 변환

 -> Init() 함수에서는 위 그림처럼 0부터 127까지 배열을 각 칸에 맞게 숫자를 삽입

 -> decode() 함수에서는 비트와 위치를 바탕으로 m[] 배열에서 비트연산을 취한다.

 -> 4개의 글자를 m[] 배열의 값에서 인코딩된 문자열 기준으로 위치에서 비트연산을 하고,

 -> 3개의 글자를 숫자로 비트연산을 한다.

 

 -> 이는 TGlmZSBpdHNlbGYgaXMgYSBxdW90YXRpb24u 문자열에서 TGlm 이 들어왔을 때 문자를 읽고

 -> T는 ASCII 코드로 84이므로 m[src[pos++]] -> m[src[0]] -> m[T] -> m[84] -> 19 가 나온다.

 -> 여기서 19를 비트연산을 통하여 18만큼 이동시켰을 때 bits의 변수 값은 4980736 이 나온다.

 -> 다음 단계로 넘어가서,

 -> G는 ASCII 코드로 71이므로 위 방식과 동일하게 연산하여 m[71] -> 6 이 나온다.

 -> 여기서 6을 비트연산을 통하여 12만큼 이동시켰을 때 24576이 나오는데 bits 변수값에 더하여 5005312 가 나온다.

 -> 다음 단계로 넘어가서,

 -> l는 ASCII 코드로 108이므로 m[108] -> 37 이 나온다.                // l은 소문자 엘 (l)

 -> 여기서 37을 비트연산을 통하여 6만큼 이동시켰을 때 2368이 나오는데 bits 변수값에 더하여 5007680 가 나온다.

 -> 다음 단계로 넘어가서,

 -> m는 ASCII 코드로 109이므로 m[109] -> 38 이 나온다.

 -> 여기서 38을 비트연산 없이 그대로 bits 변수에 더하여 5007718 가 나온다.

 

 -> 디코딩 단계를 시작하여,

 -> bits >> 16 & 0xFF 구문을 해석하면 5007718 >> 16 & 0xFF -> 5007718 >> 0001 0000 & 1111 1111 ->

     507718 >> 0001 0000 -> 5007718 >> 16 -> 76 -> (char)L 가 나오게 된다.

 -> 다음 단계로 넘어가서,

 -> bits >> 8 & 0xFF 구문을 해석하면 5007718 >> 8 & 0xFF -> 5007718 >> 0000 1000 & 1111 1111 ->

     5007718 >> 0000 1000 -> 5007718 >> 6 -> 105 -> (char)i 가 나오게 된다.

 -> 다음 단계로 넘어가서,

 -> bits & 0xFF 구문을 해석하면 5007718 & 0xFF -> 5007718 & 1111 1111 -> 102 -> (char)f 가 나오게 된다.

 -> 위와 같은 방식을 반복하게되면 디코딩한 문장이 출력하게 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// https://zetawiki.com/wiki/SWEA_1928_Base64_Decoder

#include <string>

#include <iostream>
using namespace std;

int m[128];

void init()
{
    for (int i = 0; i < 26; i++)
        m['A' + i] = i;
    for (int i = 0; i < 26; i++)
        m['a' + i] = 26 + i;
    for (int i = 0; i < 11; i++)
        m['0' + i] = 52 + i;

    m['+'] = 62;
    m['/'] = 63;
}

void decode(char* src, char* dst)
{
    int bits, pos = 0, pos2 = 0;

    while (src[pos])
    {
        bits = m[src[pos++]] << 18;
        bits += m[src[pos++]] << 12;
        bits += m[src[pos++]] << 6;
        bits += m[src[pos++]];

        dst[pos2++] = bits >> 16 & 0xFF;
        dst[pos2++] = bits >> 8 & 0xFF;
        dst[pos2++] = bits & 0xFF;
    }
    dst[pos2] = 0;
}

int main()
{
    init();

    int T;
    cin >> T;

    char encoded[100000];
    char decoded[100000];

    for (int tc = 1; tc <= T; tc++)
    {
        cin >> encoded;
        decode(encoded, decoded);
        printf("#%d %s \n", tc, decoded);
    }

    return 0;
}