punycode encoding/decoding 알고리즘(bootstring) - 2

1. python 구현 코드
2. 코드 디버깅 추적 및 주석

1. python 구현 코드

예외 처리 코드는 이해를 위해 제외했습니다.
실제 사용하실 때는 python 기본 인코딩을 이용하시면 됩니다.
"a다b가다c".encode('idna').decode()

INITIAL_N = 0x80
INITIAL_BIAS = 72
BASE = 36
TMIN = 1
TMAX = 26
SKEW = 38
DAMP = 700
MAX_INT = 0x7FFFFFFF

def adapt(delta, num_points, first_time):
    delta //= 2 if not first_time else DAMP
    delta += delta // num_points
    k = 0
    while delta > ((BASE - TMIN) * TMAX) // 2:
        delta //= BASE - TMIN
        k += BASE
    return k + (((BASE - TMIN + 1) * delta) // (delta + SKEW))

def encode(inputs):
    # 초기 기본값들
    i, n, delta, bias = 0, 0x80, 0, 72
    base, TMIN, TMAX = 36, 1, 26
    outputs = []
    # digits = [a-z0-9]
    digits = [ chr(i) for i in range(ord("a"),ord("z")+1) ] + [ chr(i) for i in range(ord("0"),ord("9")+1) ] 
    input_codes = [ ord(i) for i in inputs] # "q다w나" -> [113, 45796, 119, 45208 ]
    input_length = len(inputs)

    isBasic = lambda _n : _n < 0x80
    basic_codes = [ chr(i) for i in input_codes if isBasic(i) ] # 나온 순서대로 기본 코드들
    outputs += basic_codes

    handle_count = basic_count = len(basic_codes)
    # handle_count 는 처리한 코드 수
    # basic_count 는 기본 코드 수

    if basic_count > 0 : # 기본 코드가 하나라도 있으면
        delimiter = "-"
        outputs += [delimiter] # delimiter 추가
        
    while handle_count < input_length : # input 에 있는 모든 코드를 처리할 때까지
        nextN = min(cp for cp in input_codes if cp >= n) # 현재까지 처리 안 한 코드 중 가장 작은 값, initalN = 0x80 은 기본 코드 최댓값 +1
        delta += ( nextN - n ) * ( handle_count + 1 ) # ( 현 처리 할 값 - 이전 n 값 ) * ( 현재 처리하고 있는 것, 기본 코드 포함 길이 )
        n = nextN # n은 현재 처리할 코드 값
        for code_point in input_codes:            
            if code_point < n:
                delta += 1 # n의 위치 
                # delta = 이전 delta + ( m - n ) * ( handle_count + 1 ) + code index - 이전 code index
            elif code_point == n: # 입력값에 같은 코드가 여러개 있을 수 있다.
                currDelta = delta
                k = base
                while True:
                    t = min(max(k - bias, TMIN),TMAX)
                    if currDelta < t:
                        break 
                    digit = (currDelta - t) % (base - t) + t 
                    outputs += [digits[digit]]
                    currDelta = (currDelta - t) // (base - t)
                    k += base
                digit = currDelta
                outputs += [ digits[digit] ]
                bias = adapt (delta, handle_count + 1, handle_count == basic_count );
                delta = 0
                handle_count += 1
        delta += 1
        n += 1
    return "".join(i for i in outputs)


def decode(input):
    # n - delta 의 n 값
    # i - delta 의 위치 값
    # out - out 의 길이    
    n, i, output_length, bias, base = 0x80, 0, 0, 72, 36
    input_length = len(input)
    output = []
    # digits = {'a':0,'b':1,...,'9':35} digit에 대응되는 value 모음
    digits = { chr(_i) : _idx for _idx, _i in enumerate(range(ord("a"),ord("z")+1)) } | { chr(_i) : _idx + 26 for _idx, _i in enumerate(range(ord("0"),ord("9")+1)) }

    output += input[0:input.rfind("-")] # 마지막 delimeter 이전의 코드 복사
    output_length = len(output)
    in_index = output_length+1 if output_length else 0 # 기본코드가 존재하면 delimeter 제외하고 다음 index
    while in_index < input_length:
        oldi = i
        weight = 1
        k = base
        # generalized variable-length representation 표현에 의해서 t 보다 작은 digit 까지 weight 곲해서 누적, Little endian
        while True:
            digit = digits[input[in_index]]
            in_index += 1
            i += digit * weight
            t = min(max(k - bias, TMIN),TMAX)            
            if digit < t: break          
            weight *= (base - t)
            k += base        
        bias = adapt(i - oldi, output_length + 1, oldi == 0)        
        # i = n * (out+1) + index
        n += i // (output_length+1)        
        
        i %= output_length+1
        print(n,i)
        output.insert(i,chr(n))

        i += 1
        output_length += 1

    return "".join(i for i in output)

2. 코드 디버깅 추적 및 주석

2.1 "a다b가다c"를 예시로 인코딩 코드 추적

input_codes=[97, 45796, 98, 44032, 45796, 99] # code point 변환
output = ["a", "b", "c", "-"]   # 0x80=128 미만 code 분리(handle_count=3, basic_count = 3)

## "가" 변환
initialN = 128보다 큰 code 중 가장 작은 값 m=44,032 선정 (delta = 0, n = 128, m = 44032)
delta += (m-n)*(handle_count+1) = (44032-128)*(3+1) = 175,616
n = m  # (m-n) 계산 했으니 임시 변수 m -> n 으로 (n = m = 44,032)
delta += 2 = 175618 # input_codes중 이전 n위치(처음 나온 n이기에 0) 이후의 n보다 작은 code 수, 디코딩 과정 중 삽입할 위치 ( delta = 175,618, q=delta=175,618 k = base=36, bias=72 ,t = 1 )

# Generalized variable-length integers 표현으로 변환, q < t 일 때까지 반복
# t = [1,1,26,26], w=[1,35,35,10]
t = min(max(k - bias, TMIN),TMAX)
digit = (q - t) % (base - t) + t = (175618-1)%(36-1) + 1 = 23
q = (q - t) // (base - t) = (175618-1)//(36-1) = 5017
k += base  # ( t = 1, q = 5017, k = 72 )
# 결과 = [23,12,33,11],  23*1 + 12*1*35 + 33*1*35*35 + 11*35*35*10 = 175618
output = ["a", "b", "c", "-", 23,12,33,11]
delta = 0
delta += 1 # n의 마지막 code 이후로 나오는 n 보다 작은 code 수, 44032 이후 [99] 하나

delta++, n++ # 단순화된 인코딩의 문제점 1번 out+1 보정을 위해 delta값 증가(=index 증가), 다음으로 자기보다 큰값 정할 n을 위해 증가

## "다" 변환
다음 현재 n=44,033 보다 크고 나머지 중 가장 작은 m=45,796 선정 (n = 44,033, m = 45,796, delta = 2)

delta += (m-n)*(handle_count+1) = (45796-44033)*(4+1) = 2 + 8815 = 8817
n = m  # (m-n) 계산 했으니 임시 변수 m -> n 으로 (n = m = 45,796)

## index 1 번 45796 변환
delta += 1 = 8818 # input_codes중 이전 n위치(처음 나온 n이기에 0) 이후의 n보다 작은 code 수
# delta 에 "ab가c" 의 "c", 회전 한번, "ab" 를 더해서 delta += 3 것과 같고 삽입할 위치
# 즉 delta = 8815 + 3 = 1763 * 5 + 3 = N * out + index
# ( delta = 8818, q=delta=8818, bias=32 ,t = 1 )
# Generalized variable-length integers 표현으로 변환, t=[4,26,26], w=[1,32,10,10]
# 결과 = [18,35,24],  18*1 + 35*1*32 + 24*1*32*10 = 8818
output = ["a", "b", "c", "-", 23,12,33,11, 18,35,24]
delta = 0

## index 5 번 45796 변환
delta += 2 = 2 = 0 * 6 + 2 # input_codes중 이전 n위치(index 1) 이후의 n보다 작은 code 수, [98, 44032] 둘 ( delta = 2, q=delta=2, bias=64 ,t = 1 )
# Generalized variable-length integers 표현으로 변환, t=[1,8], w= [1,35,28]
# 결과 = [2,0],  2*1 + 0*1*35 = 2
output = ["a", "b", "c", "-", 23,12,33,11, 18,35,24, 2,0]

#모든 code를 다 변환했으니 종료 후 output 을 [a-z0-9] 로 변환
output = "abc-xm7ls9yca" = ["a", "b", "c", "-", 23,12,33,11, 18,35,24, 2,0]

정리하면 delta 는 아래와 같고 이 값을 Generalized variable-length integers 로 변환한다.
delta = [ 0+2+(44032-128)*(3+1), 2+1+(45796-44033)*(4+1), 0+2+0 ] = [175618, 8818, 2]
# 이전 나머지 code + 현재 앞의 code + (m-n)*(handle_count+1)
즉, 역으로 계산하면 들어갈 위치와 m-n 으로 n 값을 얻을 수 있다.


2.2 "a다b가다c" -> "abc-xm7ls9yca" 를 예시로 디코딩 추적

output = ["a", "b", "c"] # 가장 뒤에 나오는 "-" 앞의 기본 코드들 복사
input = [ 23,12,33,11, 18,35,24, 2,0]  # code 로 변환
out = len(output)  # 진행중인 출력 길이, 이후 길이 변경 시마다 계산
i = 0 # 처음 시작은 0 index 부터

# Generalized variable-length integers 표현 변환
# (i=0, n=0x80=128, out=3, w=1, k=base=36, bias=72)
# bias 와 TMIN, TMAX, base 가 같으므로 encoding 과정의 t 와 w가 같다.
# t = [1,1,26,26], w=[1,35,35,10]
# [23,12,33,11, 18,35,24, 2,0] 에서 11부터 t 보다 작으므로 [23,12,33,11] 까지를 변환
i += 23*1 + 12*1*35 + 33*1*35*35 + 11*35*35*10 = 175618
# n, i 추출
n += i // (out+1) = 128 + 175618 // (3+1) = 44032 # 이전 n 값, 초기값 0x80=128
i = i % (out+1) = 0 + 175618 % (3+1) = 2 # (n=44032='가', i=2) # 이전 i 값, 초기값 0
output = ["a", "b", "가", "c"]
i++ # out+1 에 의한 보정값

# Generalized variable-length integers 표현 변환
# (i=3, n=44032, out=4, w=1, k=base=36, bias=32)
# t = [4,26,26], w=[1,32,10]
# [18,35,24, 2,0] 에서 24부터 t 보다 작으므로 [18,35,24] 까지를 변환
i += 18*1 + 35*1*32 + 24*1*32*10 = 3 + 8818 = 8821 
# n, i 추출
n += i // (out+1) = 44032 + 8821 // (4+1) = 45796
i = i % (out+1) = 8821 % (4+1) = ( 2 + 3 + 1 + (45796-44032)*5 ) % 5 = 1 # (n=45796='다', i=1)
#(이전 i 값 + i 차이값 + 보정값 + (N-prevN)*(out+1)) % *(out+1) = 1
output = ["a", "다", "b", "가", "c"]
i++

# (i=2, n=45796, out=5, w=1, k=base=36, bias=64)
# t = [1,8], w=[1,35]
# [2,0] 에서 11부터 t 보다 작으므로 [2,0] 까지를 변환
i += 2*1 + 0*1*35 = 2 + 2 = 4
# n, i 추출
n += i // (out+1) = 45796 + 4 // (5+1) = 45796
i = i % (out+1) = 4 % (5+1) = 4 # (n=45796='다', i=4)
output = ["a", "다", "b", "가", "다", "c"]