오늘 Wolfenstein 3D 게임이 Linear Feedback Shift Register를 이용해 페이드 효과를 구현한 방법에 대한 흥미로운 글을 읽었다. 화면의 모든 픽셀이 의사 난수 방식으로 빨간색으로 칠해지다가 결국 화면 전체가 빨간색(혹은 게임에서 발생하는 이벤트에 따라 다른 색)으로 바뀌는 방식이다. 구현을 설명한 블로그 글은 여기에서 볼 수 있으며 읽어볼 만하다: http://fabiensanglard.net/fizzlefade/index.php

원래 코드가 왜 LFSR을 썼는지, 그리고 왜 내가 단순한 setPixel(rand(),rand()) 대신 다른 접근법을 제안하는지 궁금할 수도 있다. 블로그 글에서도 언급했듯 의사 난수 생성기로 이렇게 구현하면 느릴 뿐만 아니라 시각적으로도 매우 거슬린다. 이미 빨간색으로 칠해진 픽셀이 많아질수록 아직 빨갛지 않은 새로운 픽셀을 맞출 확률이 떨어지기 때문에 마지막 남은 픽셀들이 빨갛게 변하는 데 끝없이 오래 걸리기 때문이다(예전에 Spectrum, C64 시절이나 나중에 QBASIC이나 GWBasic으로 직접 해본 독자라면 분명 공감할 것이다). 블로그 글 마지막 부분에서 저자는 이렇게 썼다:

“이 효과는 픽셀을 하나씩 찍는 방식으로 동작하기 때문에, 개발자들이 하드웨어 가속 GPU로 게임을 포팅하려 할 때 재현하기가 어려웠다. Wolf4SDL을 제외하고는 어떤 포팅 버전도 fizzlefade를 재현하지 못했는데, Wolf4SDL은 320x200보다 높은 해상도에 도달할 수 있는 LFSR 탭 구성을 찾아냈기 때문이다.”

로켓 과학은 아니지만, 다른 해상도에 적합한 LFSR을 찾는 일은 어려웠을 수도 있다. 하지만 다른 해상도에 적합한 LFSR을 찾는 일의 실제 복잡도와는 별개로, 포팅을 맡은 개발자들은 Feistel Network라 불리는 다른 기법을 이용해 정확히 같은 결과를 아주 간단하게 얻을 수 있었을 것이다.

Feistel 네트워크란 무엇인가?

암호학에서 흔히 쓰이는 구성 요소다. 비트 수열을 다른 비트 수열로 변환하는데, Feistel 네트워크 내부에 어떤 종류의 비선형 변환을 넣더라도 변환이 항상 가역적이 되도록 만든다. 쉽게 말해 Feistel 네트워크는 예를 들어 32비트 숫자 A를 어떤 함수 F()에 따라 다른 32비트 숫자 B로 변환할 수 있으며, 나중에 B에서 다시 A로 돌아올 수 있다. 함수가 가역적이라는 것은 Feistel 네트워크가 모든 입력값에 대해 서로 다른 출력값을 생성한다는 것을 의미한다.

다음은 의사 코드로 작성한 간단한 Feistel 네트워크다:

Split the input into L and R halves (Example: L = INPUT & 0xFF, R = INPUT >> 8)
REPEAT for N rounds:
    next_L = R
    R = L XOR F(R)
    L = next_L
END
RETURN the value composing L and R again into a single sequence of bits: R<<8 | L

즉, (예를 들어) 16비트 정수를 L과 R이라는 두 개의 8비트 정수로 나누고, N번의 라운드를 수행해 변환한 뒤, 다시 하나의 16비트 정수로 합쳐 출력으로 내보내는 것이다.

그렇다면 이게 FizzleFade를 구현하는 문제에 어떻게 도움이 될까? 2D 화면을 픽셀들의 선형 배열로 상상해 보자. 원작 게임처럼 해상도가 320x200이라면 픽셀은 0번부터 63999번까지 있다. 따라서 0부터 63999까지의 모든 정수에 대해 차례로 세어가며 Feistel 네트워크가 반환하는 위치에 픽셀을 찍으면 무작위처럼 보이는 픽셀 위치를 생성할 수 있다. 문제는 Feistel 네트워크가 비트 단위로 동작한다는 점이라, 0부터 63999까지 정확히 맞출 수는 없고 2의 거듭제곱 중 충분히 큰 수를 골라야 한다는 것이다. 이 경우 가장 가까운 수는 16이다. 16비트를 쓰면 65536개의 정수-대-정수 변환을 얻을 수 있는데, 실제 픽셀을 찍는 데 사용되지 않는 몇 번의 사이클이 생기지만 큰 낭비는 아니다.

그래서 Javascript로 구현한 우리의 Feistel 네트워크는 이렇게 생겼다:

/* Transforms the 16 bit input into another seemingly psenduo random number
 * in the same range. Every input 16 bit input will generate a different
 * 16 bit output. This is called a Feistel network. */
function feistelNet(input) {
    var l = input & 0xff;
    var r = input >> 8;
    for (var i = 0; i < 8; i++) {
        var nl = r;
        var F = (((r * 11) + (r >> 5) + 7 * 127) ^ r) & 0xff;
        r = l ^ F;
        l = nl;
    }
    return ((r<<8)|l)&0xffff;
}

내가 사용하는 비선형 변환 “F”는 그저 무작위로 고른 몇 가지 곱셈과 시프트 연산의 조합이다. 더 좋은 F 함수를 쓴다면 8라운드까지 필요하지 않을 수도 있지만, 효과가 무작위처럼 보이길 원해서 8라운드를 사용했다(우연히도 무작위로 픽셀을 그리는 것은 자명한 분포 결함을 시각적으로 잡아내는 꽤 괜찮은 방법이기도 하다).

이를 Javascript 캔버스를 이용해 구현하려면 2D 컨텍스트를 얻고 픽셀을 찍는 몇 가지 함수가 더 필요하다.

최종 코드는 이 Gist에 있다: https://gist.github.com/antirez/6d58860b221a6ae5622ced8ccdddbe47

결과는 여기에서 볼 수 있다: http://antirez.com/misc/fizzlefade.html

이 글에서 탐구하려는 원래 문제는 다른 해상도에서 효과를 구현하는 방법을 찾는 것이었으므로, 320x200 경우를 자명하게 확장한 것에 불과하지만 예를 하나 들어보자. 똑같은 효과를 1024*768로 구현하고 싶다고 상상해 보자. 픽셀은 총 786432개이므로 2^20인 1048576개의 정수가 꽤 잘 맞는다. L과 R 변수를 각각 10비트씩 사용하도록 Feistel 네트워크를 수정해 20비트 입출력을 갖도록 해야 하며, 그 외에는 거의 동일하다. 단, (프레임 수를 검사하는) 종료 조건도 함께 변경해야 한다는 점을 잊지 말자.

사실 Feistel 네트워크의 일대일 의사 난수 매핑 특성은 다른 맥락에서도 매우 유용하다. 예를 들어 나는 레딕스 트리 구현 테스트에서 이를 활용했다(https://github.com/antirez/rax 궁금하다면 참고). 프로그래머의 머릿속 도구 상자에 넣어두면 좋은 도구다.