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]

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