punycode encoding/decoding 알고리즘(bootstring)

1. puny 코드

2. 작성동기

3.관련 사전 정보

4. puny 코드 알고리즘 번역 및 주석

5. 단순화한 조금 더 직관적인 설명

6. punycode

7. 감상

 

1. puny 코드

퓨니코드(Punycode)는 유니코드 문자열을 호스트 이름에서 허용된 문자만으로 인코딩하는 방법으로, RFC 3492에 기술되어 있다. 퓨니코드는 유니코드가 지원하는 모든 언어로 국제화 도메인을 쓸 수 있게 한 IDNA의 일부로, 변환은 전적으로 웹 브라우저와 같은 클라이언트에서 이루어진다.
이 과정은 ASCII 문자 집합으로 표시할 수 없는 도메인 이름의 부분마다 따로 일어나고, 변환된 퓨니코드 문자열에는 예약된 접두어 xn--이 덧붙는다. 
출처-https://ko.wikipedia.org/wiki/%ED%93%A8%EB%8B%88%EC%BD%94%EB%93%9C

즉, url에서 쓸 수 있는 unicode -> ascii 인코딩 방식이고 url 에서 쓸 때는 앞에 xn--이 붙는다.
이 방식으로 dns의 시스템의 변경없이 한글 및 기타 유니코드를 dns 에서 사용할 수 있다.

2. 작성동기
우연히 한글 도메인을 보고 과연 어떻게 저장될까 라는 의문을 가지고 url을 확인해 보았습니다.
그때 xn-- 의 접두사와 인코딩된 코드를 보고 의문이 생겼고 찾아보니 puny 코드인 것을 확인했습니다.
그러나 인코딩 방식에 대한 설명은 잘 안 나와 있어 글로 써보려 합니다.
아쉽게도 한글 wiki에는 encoding/decoding 방식이 안 나와 있어서 작성합니다.

3. 관련 사전 정보
qwe.com/abc 의 aqe.com 을 도메인이라 부른다.
lable("." 으로 구분된 각 문자열) 은 최대 63 charaters를 가지고 (rfc-1034)
도메인 전체는 최대 253 charaters(rfc-2181) 가진다.
도메인에는 a-z, 0-9 , "-" 을 사용할 수 있다. (LDH ruole, letters, digits, hyphen)
처음과 끝에는 "-" 이 올 수 없다.
대문자와 소문자는 같은 의미를 가진다.
com 은 top-level domain(TLD), qwe는 second label domain 으로 불린다.

puny 코드는 unicode 도메인을 인코딩하는 방식입니다.
도메인 -> xn--encoded-code
bootstring 은 puny code에서 encoded-code 를 만드는 방식입니다.
도메인 -> encoded-code

4. puny 코드 알고리즘 번역 및 주석

우선 내용이 조금 복잡합니다.또한 rfc 부분은 번역투가 심해서 이해하기 힘들 거라고 생각됩니다.
최대한 읽기 편하게 의역과 주석을 달았지만 저도 중간중간 이해 안 되는 부분이 있어서 번역만 해둔 부분이 있습니다.

rfc 번역은 가볍게 읽고 목차 5번에 조금 더 단순화한 내용이 있으니 편하게 읽으시면 됩니다.
다만 3번 Generalized variable-length integers 만 punycode 알고리즘에서 자주 쓰이니 주의 깊게 읽고 넘어가시면 됩니다.
코드로 보는 것이 더 편하신 분은 다음 글에 구현 코드와 주석이 있으니 참고해주세요.

*bootstring representation
bootstring 표현은 임의의 코드 포인트(Unicode)들을 기본 코드 포인트([0-9a-z]) 로 표현하는 방법이다. bootstring에서 사용되는 4가지의 기법을 설명한다.
1. basic code point segregation
이 방법은 기본 코드로 이루어진 문자열을 효율적으로 처리한다.
2. Insertion unsort coding
비기본 코드를 나타난 순서가 아니라 코드 크기순으로 delta 로 변환한다.
3. generalized variable-length integers
delta 를 변환하는 방식이다.
값을 표현하는 방식으로 기본 코드를 사용한다.
4. bias adaptation
generalized variable-length integers 에서 사용하는 parameters 를 정하는 방법이다.
연속된 delta의 크기가 비슷할 때 효율이 올라간다.

# 설명을 위한 단어 정리
basic code point = a-z 와 0-9 와 "-" 이다. 다만 일반적인 도메인 규칙을 지키면 U+0080 아래의 코드들은 사용되지 않거나 소문자로 변경해서 구현 코드에서는 {v|v<0x80} 으로 표현된다.
기본 코드로 번역, 표현 할 것이다.

delta = 비기본 코드를 위치와 코드 값을 곱한값, delimiter(-) 뒤에 generalized variable-length integers 표현으로 나타난다.
delta 그대로 사용한다.

value = 진수와 관련없는 숫자 그 자체이다. 110(2)=6(10)=6(8) 등 어떤 식으로 표현하듯 6이라는 정수값은 동일하다. value는 이러한 정수값 자체를 의미한다.

1. basic code point segregation
모든 기본 코드는 문자열 앞부터 나온 순서에 따라 채워진다.
기본 코드가 하나 이상이라면 delimiter(-)가 뒤에 온다.
"abc" -> "abc-"
"a가b" -> "ab-"
"가" -> ""
"--" -> "---"

2. Insertion unsort coding

기본 코드가 아닌 코드 들은 delta 로 변환돼서 표현된다.
delta의 의미는 디코더와 관련해서 얘기할 때 가장 이해하기 쉽다.

디코더는 문자열을 점진적으로 만든다.
delimiter(-)전 코드들을 결과에 복사한다.
그리고 디코더는 delimiter(-) 뒤에 있는 비기본 코드를 나타내는 각각의 delta 를 문자열에 삽입한다.
마침내 디코딩된 문자열을 얻을 수 있다.

이 과정의 요점은 index i와 counter n 을 가진 상태 기계이다 index i 는 현재 만들고 있는 문자열의 위치를 나타내고 0부터 현재 문자열 길이의 값을 가진다.
예로 현재 상태가 <n, i> 라면 다음 상태는 <n, i+1> 이고 i+1 이 현재 문자열보다 길다면 <n+1, 0> 이다.
다시 말해서 매 단계마다 i 를 증가시키고 필요시 0으로 초기화하고 counter n 을 증가 시킨다.

상태 기계는 항상 일방적으로 진행되므로 디코더가 중간에 값을 반환하는 일은 없다.
각 단계에서 삽입은 일어나거나 일어나지 않고 최대 한번의 삽입이 행해진다.
삽입은 값 n을 값 i 의 위치에 삽입한다.
delta 는 이 과정의 실행-길이 인코딩이다.
delta 는 삽입 상태 앞에 있는 비삽입 상태의 실행 길이 이다.
그러므로 각 delta 마다 디코더는 delta의 상태를 바꾸고, 삽입하고, 상태를 바꾼다.

인코더의 주요 일은 디코더가 문자열 만들 때 사용할 delta들을 만드는 것이다. 

###

일단 직역을 하기는 했지만 이해가 안 돼서 직역을 그대로 옮겨 두었습니다.
이해한 바로 풀어서 써보겠습니다.
delta 라는 음이 아닌 정수 값들을 이용해서 디코딩을 할 것 입니다.
값들을 문자열로 디코딩하면 비정렬 삽입 코딩의 의미대로 문자 값(code point)과 위치 정보를 기반으로 정렬되지 않은 방법으로 삽입합니다.

여기서 비정렬이란 선택하는 문자 값을 문자열의 순서가 아닌 문자 값이 가장 작은 문자 부터 선택합니다.

예) "다가나" 가 있으면 "가"를 선택하여 삽입합니다.

자세하게는 delta 에는 문자의 값, unicode 값과 삽입 되어야 할 위치의 정보가 들어있습니다.
방식은 아래와 비슷합니다.
delta = (이전 value - 현재 value) * (현재 문자열 길이+1) + (이전 index - 현재 index) 입니다.
이러한 delta 를 delta%(현재 문자열 길이+1) 와 delta/(현재 문자열 길이+1)를 통하여 value와 index를 알아내어 문자를 하나씩 위치에 맞게 삽입하여 문자열을 만들어갑니다.

여기서 상태기계는 index 부분을 말하는 것 같기는 한데 왜 저런 식으로 썼는지는 이해가 잘 되지는 않습니다.
굳이 따지자면 (이전 index - 현재 index) 이 부분이 index 가 index 범위를 넘어서면 (현재 index) + (범위 - 이전 index) 으로 회전해서 정해집니다.
구현 코드를 보면 상태 기계와 비슷하게 돌기는 하지만 이해에는 썩 도움이 되지는 않는 것 같습니다.

###

3. Generalized variable-length integers

일반적인 수 표현에서는 value 를 0~base-1 로 된 digit 들로 표현된다.
digit_i 를 i 번째 least significant digit으로 표현하면 수는 sum( digit_j * w(j) ) 이다.( w(j) = base^j )
이것은 두개의 단점이 있다.
첫째, 734 을 0734, 00734 등 여러 방법으로 표현할 수 있다. 인코딩에서는 유일한 표현 하나로 나타내기를 원한다.
둘째, [456,987...] 등 숫자 나열을 "456987" 로 표현되어 있으면 자체적으로 구분해서 표현할 수 없다.
"," 등의 추가적인 표현 또는 정해진 길이 등으로 구분이 필요하다.
generalized variable-length representation 이러한 문제를 해결한다.

# value 는 특정 진수로 표현 되는 값이 아닌 그저 정수 값이다.

3.1. 변환된 결과 digit은 0~base-1 이다.

3.2. 734251 가 있으면 digit_i < t(i) 를 만족하는 위치가 구분되는 위치이다. (t=threashold, i 는 0부터 시작하고 구분 시마다 0으로 초기화 된다.)
t(i) = { 1,2,6,6..} 로 잡으면 734,251로 구분할 수 있다.

3.3. generalized variable-length representation로 표현된 value의 값 계산이 일반적인 진법과 비슷하지만 조금 달라진다.
w(j) = w(j-1) * (base - t(j-1) ) for j>0, w(0) = 1 # w = weight
value = sum( digit_j * w(j) )
      = d[0]*w(0) + d[1]*w(0)*(base-t(0)) + d[2]*w(0)*(base-t(0))(base-t(1)) ...
예) base=10 일때 257 value는 , value = 7 * 1 + 5 * 1 * (10-1) + 2 * 1 * 9 * (10 - 2) = 196
# d = [digit_0, digit_1, digit_2... ], 예) 257(10진법) 의 d = [7, 5, 2]

3.4. decoding( Generalized variable-length integers  -> value) 는 보편적인 진수 변환과 비슷하다.
w(i)*d[i] 를 반복해서 더해주면 된다.
대신 digit_i 가 t(i) 보다 작을 때까지만 더하면 된다.

value, i = "", 0
while True:
  value += d[i] * w(i)
  i += 1 
  if d[i] < t(i): break

3.5. encoding( value -> Generalized variable-length integers ) 은 조금 복잡하다.
일반적인 10진법에서는 d[0] = v%10, v/d[0] = v/10 를 반복해서 구한다.
value = d[0]*w(0) + d[1]*w(0)*(base-t(0)) + d[2]*w(0)*(base-t(0))(base-t(1)) ... 의 형태로 나타내질 것이다.
여기서 d[0] 를 구하려면 첫 항을 제외한 공통인 (base-t(0)) 나머지 연산을 한다.
즉, value mod (base-t(0)) 또는 value % (base-t(0)) 를 해주면 d[0]*w(0) 만 남고 w(0) = 1 이니 d[0] = value mod (base-t(0)) 이다.
다만 여기서 조건이 하나 있다.
d[0] 가 (base - t(0) ) 보다 작아야 한다.

이 문제를 해결하기 위해서 약간의 트릭을 쓴다.
마지막 digit을 제외하고는 0 <= t(0) <= d[0] < base 는 보장 되었으므로  d[0] - t(0) < base - t(0) 가 성립한다.
또한
t(0) + t(0) <= t(0) + d[0] < base + d[0]
t(0) + t(0) < base + d[0]
-base + t(0) < d[0] - t(0)가 성립한다.
-( base - t(0) ) < d[0] - t[0] < base - t(0) 가 성립하므로 {value-t(0)}를 하고 나머지 연산을 하면 d[0] 값이 사라지지 않는다.
최종적으로 뺀 t(0) 를 다시 더해주면 수식이 완성된다.
d[0] = (value - t(0)) mod (base - t(0)) + t(0)
     = { (d[0] + d[1]*(base-t(0)) + d[2]*(base-t(0))(base-t(1)) ...) - t(0) }  mod (base - t(0)) + t(0)
     = { ( d[0] - t(0) )  + d[1]*(base-t(0)) + d[2]*(base-t(0))(base-t(1)) ... }  mod (base - t(0)) + t(0)
     = ( d[0] - t(0) ) mod (base - t(0)) + t(0)
     = d[0] - t(0) + t(0)
     = d[0]

비슷하게 이미 사용한 d[0]와 base-t(0) 를 수식에서 제외하려면 # d[0] - t(0) < base - t(0) 앞에서 증명
value_i = ( value - t(0) ) / ( base - t(0) )
        = { (d[0] + d[1]*(base-t(0)) + d[2]*(base-t(0))(base-t(1)) ...) - t(0) } / (base - t(0))
        = (d[0] - t(0) + d[1]*(base-t(0)) + d[2]*(base-t(0))(base-t(1)) ...) / (base - t(0))
        = d[1] + d[2](base-t(1)) + d[2](base-t(1))(base-t(2))...
이 과정을 반복해 value 에서 Generalized variable-length integers의 digit 들을 얻어 낼 수 있다.

음수가 아닌 정수에 대하여 generalized variable-length representation 은 유일한 값을 얻을 수 있다.
generalized variable-length representation 은 big-eidian, little-endian 에서 둘다 동작하지만 bootstring 에서는 little-endian 을 사용한다.

앞의 t(i) 를 임의의 값으로 넣었지만 실제로는 상수 base, tmin, tmax  와 변수 bias 로 정의 된다.
t(j) = max(min(   (base*(j+1) - bias)   ,tmax),tmin) # tmin <= t(j) <= tmax
즉, 이 t(j) 값들은 [tmin,tmax] 범위 내에서 bias 에 의해 정해지는 값이다.

4. Bias adaptation

bias 는 delta의 영향을 받는다.
delta 가 인코딩 되거나 디코딩 된 후 bias 는 다음 delta 를 위해 변경된다.

1. delta = isFirst ? delta/2 : delta/damp
delta가 너무 커지지 않게한다.
그러나 보통 두번째 delta 가 처음보다 작기 때문에 이를 보상하기 위해 처음 delta 일 경우 상수 damp 로 나눈다.
2. delta = delta + ( delta / numpoints )
다음 delta 는 더 긴 문자열에 삽입 된다는 것을 보상하기 위해 delta를 증가시킨다.
numpoint 는 지금까지 인코딩/디코딩 된 code point 수이다. (현재 계산하고 있는 delta 와 기본 코드 포함해서)
3. 다음 델타를 나타내는 데 필요한 최소 자릿수를 예측하기 위해  delta 가 ((base-tmin)*tmax)/2 보다 작을 때까지 반복한다.
count_step3 = 0
while delta > ((base-tmin)*tmax)/2:
      delta = delta / (base - tmin)
      count_step3 = count_step3 + 1
4. bias = (base*count_step3)+( ((base-tmin+1)*delta)/(delta+skew) )

# 어떤 방식을 이 식과 상수값들이 나오는 지 이해할 수가 없다..

5. bootstring parameters

initial value N 은 기본 코드([a-zA-Z0-9]) 보다 커야되고 아래의 조건을 만족해야한다.

1. 0x80 <= initial value N
2. 0 <= tmin <= tmax <= base-1
3. skew >= 1
4. damp >= 2
5. initial_bias mod base <= base - tmin

최종적으로 punycode에서 사용하는 상수값들을 아래와 같다.
base         = 36
tmin         = 1
tmax         = 26
skew         = 38
damp         = 700
initial_bias = 72
initial_n    = 128 = 0x80

punycode는 음이 아닌 정수만 만족하면 되지만 특히 저 상수값들은 Unicode(0~10FFF) 에서 잘 동작한다.

기본 코드는 [0-9A-Za-z] 로 정의하고 delimiter 를 U+00dD(-) 로 정의한다.
인코딩된 결과물이 '-'로 끝나거나 '-' 시작할 수 있는데 IDNA 에서는 prefix(xn--) 가 있으므로 제거한다. [RFC952]
decoder 는 소문자와 대문자 모두를 읽을 수 있어야 하고 encoder는 소문자를 출력해야한다.

def adapt(delta, num_points, first_time):
    delta //= 2 if first_time else 4
    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))

5. 단순화한 조금 더 직관적인 설명

5.1 인코딩
"a다b가다c" 라는 문자열을 예시로 가능한 직관적으로 설명을 해보겠습니다.
output 에 기본 문자들인 "abc" 를 먼저 추가합니다.
"a다b가다c" 라는 문자열을 "abc" 제외하고 code point 로 보면 [45796, 44032, 45796] = ["다", "가", "다"] 가 됩니다.
이 간단한 인코딩은 그저 나온 먼저나온 코드 부터 처리합니다.
그리고 delta 에는 값 N과 index에 대한 정보가 있어야 합니다.
변수 out 을 현재 output 에 있는 길이라고 둡니다.
delta = N * out + index 로 정의하면 N과 index 정보가 들어갑니다.
index 는 output 에 삽입할 위치이므로 항상 out 보다 작습니다.
그러므로 index < out 는 보장됩니다.

처음에는 output = "abc" 이고 디코딩 중에 delta 를 이용해서 "다가다"를 추가해야 되니 "abc" 의 1번 위치에 "다" 를 삽입할 것입니다.

delta_1 = 45796 * 3 + 1 = 137389 입니다.
output = "a다bc"
비슷한 방식으로 "가" 를 "a다bc" 에 삽입하기 위해 3번위치에 이후 "다"를 "a다b가c" 4번위치에 추가하기 위한 delta를 계산합니다.
delta_2 = 44032 * 4 + 3 = 176131
output = "a다b가c"
delta_3 = 45796 * 5 + 4 = 228984
output = "a다b가다c"
delta = [137389, 176131, 228984]

bias = 72 로 고정하고 t=[1,1,26,26], w=[1,35,35,10] 로 생각해봅시다.
delta 를 generalized variable-length integers 로 각각 변환하면 ["of6i", "l17l", "o60q" ]= [[14, 5, 32, 8], [11, 27, 33, 11], [14, 32, 26, 16]] 이 됩니다.
이를 [a-z0-9] 로 매핑하면 output = "abc-of6il17lo60q"
encoding 이 완료됩니다.

5.2 디코딩

디코딩 과정을 설명하겠습니다.
위의 단순화한 인코딩 되었다고 가정해보면 "a다b가다c" 문자열은 인코딩해서 "abc-of6il17lo60q" 입니다.
output 에 "-"앞의 문자들인 "abc" 를 먼저 추가합니다.
generalized variable-length integers 표현을 위해 bias = 72 로 고정하고 t=[1,1,26,26], w=[1,35,35,10] 로 생각해봅시다.
뒤의 delta는 t에 의해서 나눠지고 변환됩니다.
"of6il17lo60q" = [14, 5, 32, 8, 11, 27, 33, 11, 14, 32, 26, 16] = [[14, 5, 32, 8], [11, 27, 33, 11], [14, 32, 26, 16]] = [137389, 176131, 228984]
변수 out 을 현재 output 에 있는 길이라고 둡니다.
그리고 아래의 식과 같은 방식으로 n, i 값을 얻을 수 있습니다.
n = delta // out
i = delta % out

현재 output = "abc" 이고 out = 3 이므로 delta 를 차례대로 처리하면 됩니다.
n = 137389 // 3 = 45796 = "다"
i = 137389 % 3 = 1
output의 i위치에 n 을 추가하면 output = "a다bc" 가 됩니다.
반복적으로
n2 = 176131 // 4 = 44032
i2 = 176131 % 4 = 3
output = "a다b가c"
n3 = 228984 // 5 = 45796
i3 = 228984 % 5 = 4
output = "a다b가다c"
decoding 이 완료됩니다.

5.3 단순화된 인코딩의 문제점

1. out+1 문제

out이 0이 될 때, 예로 "가나" 일 때(기본 코드가 없을 때) out 은 0 이 되어서 N * 0 + index 로 N 값이 사라집니다.
그러므로 out 에 (+1)을 하여 계산합니다.
delta = N * (out+1) + index 로 인코딩하고
N = delta // out, i = delta % out 로 디코딩합니다.

2. 숫자가 커짐에 따라 인코딩 길이가 길어집니다.
"a다b가다c" 를 실제로 bootstring으로 변환하면 "abc-xm7ls9yca" 로 13글자입니다.
위의 단순화한 인코딩은 "abc-of6il17lo60q"로 16글자입니다.
원인은 delta 들의 숫자의 크기 차이입니다.
generalized variable-length integers는 value의 값이 커질 수록 표현이 길어집니다.
이를 위해서 bootstring은 가장 작은 N부터 선택하여 이후 차이만을 이용하여 정보를 나타냅니다.
문자열이 정렬 되어있지 않으므로 삽입 순서가 뒤죽박죽 되겠지만 삽입 위치 i 가 포함됨으로 문제는 없습니다.

5.4 문제점을 해결한 인코딩
delta = ( N - prevN ) * (out+1) + index 으로 표현해서 인코딩해봅시다.
똑같이 "a다b가다c" 를 예시로 들겠습니다.

output = "abc"로 기본 코드를 분리합니다.
["다", "가", "다"] = [45796, 44032, 45796] 이고 44032 가 가장 작고 2번 위치에 삽입한다는 정보를 나타내봅시다.
이전 N = prevN 이 없지만 기본 코드 0x80=128 보다는 클 것이 명확하니 처음 prevN = 128 로 두고 시작합니다.
delta_1 = (44032 - 128) * (3+1) + 2 = 175618
비슷한 방식으로 "다"를 1번 위치, 4번 위치에 삽입한다는 정보를 delta 로 나타냅니다.
delta_2 = (45796 - 44032) * (4+1) + 1 = 8821
delta_3 = (45796 - 45796) * (5+1) + 4 = 4
delta = [175618, 8821, 4] = ['xm7l', 'bhh', 'ea']
output = "abc-xm7lbhhea"
13글자로 bootstring 과 비슷하게 짧아졌습니다.
실제 bootstring와는 다른 문제점과  bias adaptation 으로 인해서 결과가 달라졌지만 의도 정도는 전달될 것 같습니다.

6.5 문제점을 해결한 디코딩
N = delta // (out+1) + prevN , i = delta % (out+1) 로 디코딩해봅시다
output = "abc" 와 delta= [175618, 8821, 4]를 예시로 설명하겠습니다.

output = "abc" , out = 3
N = 175618 // (3+1) + 128 = 44032 = "가"
i = 175618 % (3+1) = 2
output = "ab가c", out = 4
N = 8821 // (4+1) + 44032 = 45796 = "다"
i = 8821 % (4+1) = 1
output = "a다b가c", out = 1
N = 4 // (5+1) + 45796 = 45796 = "다"
i = 4 % (5+1) = 4
output = "a다b가다c", out = 4

5.6 추가적인 개선안
삽입 위치 i를 보면 같은 코드 값일 경우 항상 증가합니다.
그러면 i 또한 차이만을 기록하면 값을 더 줄일 수 있습니다.
# 사실 한글 기준으로는 줄어드는 것이 맞는지는 의문입니다.
# 코드값이 정렬되어 있을 수록 또는 같은 코드를 쓸 수록 값은 줄어들지만 과연 우리는 가나다 순으로 쓰는 일이 많을까..? 또는 같은 글자를 많이 쓸까..?
# 한글 완성형 코드나 한자 등 말고 abc 처럼 철자가 끊어져있다면 효율이 올라갈 것 같기는 합니다.

똑같이 "a다b가다c" 를 예시로 들겠습니다.
이 문자열은 문제점을 해결한 단순화한 디코딩 과정중에
"abc"
"ab가c" - index 2
"a다b가c" - index 1
"a다b가다c" - index 4
순으로 변경되고 index [2, 1, 4] 가 delta들에 기록됩니다.
하지만 이때 저장된 index값이 [2, 3, 2] 이라고 생각해봅시다.
원래의 index값을 구하려면 2를 현재 문자열 "abc" 길이는 3 이지만 out+1 문제에 의하여 1을 더한 4로 나머지를 구합니다.
(0+2)%(3+1) = 2
다음 index는 2+(3+1)=6 를 현재 문자열 "ab가c" 길이 4+1로 나누면 1을 구할 수 있습니다.
3+1 인 이유는 out+1 문제에 의한 보정값입니다.
(2+3+1)%(4+1) = 1
비슷하게
(1+2+1)%(5+1) = 4
로 원래의 index 를 구할 수 있습니다.

인코딩은 저 값을 적절하게 구해주면 됩니다.
구현으로는 rfc의 상태 기계 처럼 문자열을 돌면서 가장 작은 N 값을 하나 선택해 처리하고 i 값을 늘렸다가 문자열 끝에 다다르면 처음부터 i 값을 계속 늘리는 식으로 구현할 수도 있습니다.
또는 다음 처리할 위치 N_i, 현재 i 의 값, 현재 문자열 길이 등을 이용해서 i = N_i < i ? i - N_i : out-i + N_i 식을 이용하여 구할 수 있습니다.
만약 이런식으로 구해진 index 가 out을 넘어도 문제는 없습니다.
실제 index는 out+1의 나머지를 구하여 계산하기 때문에 정확한 위치가 구해집니다.

6. punycode
punycode 는 다른 것 없이 기본 코드만 존재하면 그대로 출력합니다.
기본 코드가 아닐 시 xn-- 을 앞에 붙여 bootstring 인코딩합니다.

7. 감상
bias adaptation도 몰라서 설명도 못 했고 글이 너무 길어져서 생략하는 등 모자란 부분이 많습니다.
자료가 없기도 하고 글이 길어지면서 지치고 해서 생략된 부분이 많아 아쉽기는 합니다.
추후 기회가 되면 추가해보겠습니다.

base64 안 쓰고 base36 쓰는 이유는 dns에서 대/소문자 구분 안 하고 써서 그런 듯 합니다.
unicode 로 되어있는 표현을 36진법으로 encoding 결과값은 필연적으로 늘어납니다.
unicode 에서 최대한 앞의 숫자를 할당 받았으면 더 긴 한글을 도메인에 쓸 수 있지 않았을까 싶습니다.

+아직도 bias adaption 은 왜 저런 숫자와 수식이 나왔는지 이해가 안 되네요.
제가 못 찾거나 이해를 못 하는 것이겠지만 공식문서에도 그저 가장 적절하다고 쓰여있고 논문을 찾아도 나오는 것은 없었습니다..

https://en.wikipedia.org/wiki/Punycode
https://www.rfc-editor.org/rfc/rfc3492.txt