Azembler

텍스트에서 문자열을 검색하는 After the Search Ultimate 프로그램이 실패하자, Igor K.는 생각에 잠겼다. "도대체 왜 내 프로그램은 이렇게 느리게 작동하지?" 그는 코드를 다시 확인하며 말했다. "내 코드에는 오류가 없지만, 그래도 Search Ultimate을 개선할 방법은 알고 있어!" 그러고는 책장에서 커다란 책을 꺼냈다. 책에는 "Azembler. Principally New Approach"라고 쓰여 있었다.

책을 주의 깊게 훑어본 Igor K.는 알고 보니 수를 수십 배 더 빠르게 곱할 수 있다는 것을 깨달았다. "Search Ultimate은 지금까지보다 훨씬 빨라질 거야!" 그는 기뻐서 외치고 작업에 착수했다.

이제 Igor의 아이디어가 무엇이었는지 명확히 설명하자. 컴파일러가 생성한 코드는 완벽과는 거리가 멀었다. 표준 곱셈은 책에서 언급한 기법보다 느리게 작동한다.

The Azembler 언어는 26개의 레지스터(eax, ebx, ..., ezx)와 두 가지 명령을 사용한다.

• — 주소 x에 있는 값을 반환한다. 예를 들어, [eax]는 레지스터 eax의 값과 같은 주소에 있던 값을 반환한다.
• lea x, y — 첫 번째 피연산자로 지정된 레지스터 x에 두 번째 피연산자의 주소를 대입한다. 따라서 예를 들어 "lea ebx, [eax]" 명령은 ebx 레지스터에 eax 레지스터의 내용을 기록한다. 먼저 [eax] 연산이 수행되며, 그 결과는 eax에 기록된 주소에 있는 어떤 값이다. 하지만 그 값은 필요하지 않다. 다음 연산인 lea가 [eax]의 주소, 즉 eax 레지스터의 값을 가져와 ebx에 기록하기 때문이다.

처음 생각했을 때 두 번째 연산은 무의미해 보이지만, 알고 보니 다음과 같이 연산을 작성할 수 있다.

lea ecx, [eax + ebx],

lea ecx, [k*eax]

또는 심지어

lea ecx, [ebx + k*eax],

여기서 k = 1, 2, 4 또는 8이다.

그 결과 레지스터 ecx는 각각 eax + ebx, keax, ebx + keax이 된다. 그러나 이러한 연산은 일반적인 수의 곱셈보다 여러 배, 즉 수십 배 더 빠르게 수행된다. 이런 연산을 여러 번 사용하면 어떤 수에 다른 수를 매우 빠르게 곱할 수 있다. 물론 eax, ebx, ecx 대신 어떤 레지스터든 사용할 수 있다.

예를 들어, eax 레지스터에 41을 곱해야 하는 어떤 수가 들어 있다고 하자. 다음 2줄이면 된다.

lea ebx, $[eax + 4*eax]$ // 이제 ebx = 5*eax

lea eax, $[eax + 8*ebx]$ // 이제 eax = eax + 8ebx = 41eax

Igor K.는 다음 질문에 관심을 가지게 되었다. 주어진 수 n을 곱하는 데 필요한 lea 연산의 최소 횟수는 얼마이며, 어떻게 해야 하는가? 그를 돕는 것이 여러분의 과제다.

초기 시점에 eax에는 Igor K.가 n을 곱하려던 수가 들어 있고, ebx부터 ezx까지의 레지스터에는 수 0이 들어 있다고 간주한다. 최종 시점에 결과는 어떤 레지스터에 있어도 된다.

입력 데이터에는 Igor K.가 곱하려는 유일한 정수 n (1 ≤ n ≤ 255)이 주어진다.

첫 번째 줄에 이를 수행하는 데 필요한 lea 연산의 최소 횟수를 나타내는 수 p를 출력한다. 그다음 해당 연산을 수행하는 p개의 명령으로 이루어진 프로그램을 출력한다. 1부터 255까지의 모든 n에 대해 이러한 프로그램이 존재함이 보장된다.

명령은 정확히 다음 형식을 사용한다(여기서 k는 1, 2, 4 또는 8이고, x, y, z는 서로 같아도 되는 임의의 레지스터다).

lea x, [y]

lea x, [y + z]

lea x, [k*y]

lea x, [y + k*z]

명령 끝에 불필요한 공백이 있으면 허용되지 않는다는 점에 유의한다.