x86 Quine: These 12 Bytes Print Themselves
source link: https://susam.net/blog/x86-quine.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
x86 Quine: These 12 Bytes Print Themselves
x86 Quine: These 12 Bytes Print Themselves
The following 12-byte program composed of pure x86 machine code writes itself to standard output when executed in a DOS environment:
fc b1 0c ac 92 b4 02 cd 21 e2 f8 c3We can write these bytes to a file with the .COM extension and execute it in DOS. It runs successfully in MS-DOS 6.22, Windows 98, as well as in DOSBox and writes a copy of itself to standard output.
On a Unix or Linux system, the following commands demonstrate this program with the help of DOSBox:
echo fc b1 0c ac 92 b4 02 cd 21 e2 f8 c3 | xxd -r -p > quine.com
dosbox -c 'MOUNT C .' -c 'C:\QUINE > C:\OUT.COM' -c 'EXIT'
diff quine.com OUT.COM
The diff command should produce no output confirming
that the output of the program is identical to the program itself.
On an actual MS-DOS 6.22 system or a Windows 98 system, we can
demonstrate this program in the following manner:
C:\>DEBUG -E 100 fc b1 0c ac 92 b4 02 cd 21 e2 f8 c3 -N QUINE.COM -R CX CX 0000 :C -W Writing 0000C bytes -Q C:\>QUINE > OUT.COM C:\>FC QUINE.COM OUT.COM Comparing files QUINE.COM and OUT.COM FC: no differences encountered
In the DEBUG session shown above, we use the debugger
command E to enter the machine code at offset 0x100 of
the code segment. Then we use the N command to name the
file we want to write this machine code to. The command R
CX is used to specify that we want to write 0xC (decimal 12)
bytes to this file. The W command writes the 12 bytes
entered at offset 0x100. The Q command quits the
debugger. Then we run the new QUINE.COM program while
redirecting its output to OUT.COM. Finally, we use
the FC command to compare the two files and confirm
that they are exactly the same.
Disassembly
In the previous section, we entered the entire program in hexadecimal format. In this section we disassemble the program to see what it does. The output below is generated using the Netwide Disassembler (NDISASM), a tool that comes with Netwide Assembler (NASM):
$ ndisasm -o 0x100 quine.com 00000100 FC cld 00000101 B10C mov cl,0xc 00000103 AC lodsb 00000104 92 xchg ax,dx 00000105 B402 mov ah,0x2 00000107 CD21 int 0x21 00000109 E2F8 loop 0x103 0000010B C3 ret
When DOS executes a program in .COM file, it loads the machine code
in the file at offset 0x100 of the code segment chosen by DOS. That
is why we ask the disassembler to assume a load address of 0x100
with the -o 0x100 command line arguments. The first
instruction clears the direction flag. The purpose of this
instruction is explained later. The next instruction sets the
register CL to 0xc (decimal 12). The register CH is already set to 0
by default when a .COM program starts. Thus setting the register CL
to 0 effectively sets the entire register CX to 0xc. The register CX
is used as a loop counter for the loop 0x103
instruction that comes later. Everytime this loop instruction
executes, it decrements CX and makes a near jump to offset 0x103 if
CX is not 0. This results in 12 iterations of the loop.
In each iteration of the loop, the instructions from offset 0x103 to
offset 0x109 are executed. The lodsb instruction loads
a byte from address DS:SI into AL. When DOS starts executing this
program, DS and SI are set to CS and 0x100 by default, so at the
beginning DS:SI points to the first byte of the program.
The xchg instruction exchanges the values in AX and DX.
Thus the byte we just loaded into AL ends up in DL. Then we set AH
to 2 and generate the software interrupt 0x21 (decimal 33) to write
the byte in DL to standard output. This is how each iteration reads
a byte of this program and writes it to standard output. program is
The lodsb instruction increments or decrements SI
depending on the state of the direction flag (DF). When DF is
cleared, it increments SI. If DF is set, it decrements SI. We use
the cld instruction at the beginning to clear DF, so
that in each iteration of the loop, SI moves forward to point to the
next byte of the program. This is how the 12 iterations of the loop
writes 12 bytes of the program to standard output. In many DOS
environments, the DF flag is already in cleared state when a .COM
program starts, so the CLD instruction could be omitted in such
environments. However, there are some environments where DF may not
be in cleared state when our program starts, so it is a best
practice to clear DF before relying on it.
Finally, when the loop terminates, we execute the RET
instruction to terminate the program.
Quine Conundrums
While reading the description of the self-printing program presented earlier, one might feel suspicious if it really is a proper quine. While there is no standardized definition of the term quine, it is generally accepted that a quine is a computer program that takes no input and produces an exact copy of its own source code as its output. Since a quine cannot take any input, tricks involving reading its own source code or evaluating itself are ruled out.
For example, this shell script is a valid quine:
s='s=\47%s\47;printf "$s" "$s"\n';printf "$s" "$s"However, the following shell script is not considered a proper quine:
cat $0The shell script above reads its own source code which is considered cheating. Improper quines like this are often called cheating quines.
Is our 12-byte x86 program a proper quine or not? It turns out that we have a conundrum. First, there is no notion of source code in this program. There would have been one if we had written out the source code of this program in assembly language and in that case we would first need to choose an assembler and a proper quine would need to produce an exact copy of the assembly language source code (not the machine code bytes) for the chosen assembler. But we are not doing that here. We want the machine code to produce an exact copy of itself. There is no source code involved. We only have machine code. So we could argue that the whole notion of machine code quine is nonsense. No machine code quine can exist because there is no source code to produce as output.
However, we could also argue that the machine code is the source code for the CPU that the CPU fetches, decodes, and converts to a sequence of state changes in the CPU. If we define a machine code quine to be a machine code program that writes its own bytes, then we could say that we have a machine code quine here.
Let us now entertain the thought that our 12-byte program is indeed a machine code quine. Now we have a new conundrum. Is it a proper quine? This program reads its own bytes from memory and writes them. Does that make it a cheating quine? What would a proper quine written in pure machine code even look like? If we look at the shell script quine above, we see that it contains parts of the executable part of the script code embedded in a string as data. Then we format the string cleverly to produce a new string that looks exactly like the entire shell script. It is a common pattern followed in many quines. The quine does not read its own code but it reads some data defined by the code and formats that data to look like its own code. However, in a pure machine code like this the lines between data and code are blurred. Even if we try to keep the bytes we want to read at a separate place in the memory and treat it like data, they would look exactly like machine instructions, so one might wonder if there is any point in trying to make a machine quine that does not read its own bytes. Nevertheless the next section shows how to accomplish this.
Proper Quines
If the thought of a machine code quine program reading its own bytes from the memory makes you uncomfortable, here is an adapation of the previous program that keeps the machine instructions to be executed separate from the data bytes to be read by the program.
fc b3 02 b1 14 be 14 01 ac 92 b4 02 cd 21 e2 f8 4b 75 f0 c3
fc b3 02 b1 14 be 14 01 ac 92 b4 02 cd 21 e2 f8 4b 75 f0 c3
Here is how we can demonstrate this 40-byte program:
echo fc b3 02 b1 14 be 14 01 ac 92 b4 02 cd 21 e2 f8 4b 75 f0 c3 | xxd -r -p > quine.com
echo fc b3 02 b1 14 be 14 01 ac 92 b4 02 cd 21 e2 f8 4b 75 f0 c3 | xxd -r -p >> quine.com
dosbox -c 'MOUNT C .' -c 'C:\QUINE > C:\OUT.COM' -c 'EXIT'
diff quine.com OUT.COM
Here is the disassembly:
$ ndisasm -o 0x100 quine.com 00000100 FC cld 00000101 B302 mov bl,0x2 00000103 B114 mov cl,0x14 00000105 BE1401 mov si,0x114 00000108 AC lodsb 00000109 92 xchg ax,dx 0000010A B402 mov ah,0x2 0000010C CD21 int 0x21 0000010E E2F8 loop 0x108 00000110 4B dec bx 00000111 75F0 jnz 0x103 00000113 C3 ret 00000114 FC cld 00000115 B302 mov bl,0x2 00000117 B114 mov cl,0x14 00000119 BE1401 mov si,0x114 0000011C AC lodsb 0000011D 92 xchg ax,dx 0000011E B402 mov ah,0x2 00000120 CD21 int 0x21 00000122 E2F8 loop 0x11c 00000124 4B dec bx 00000125 75F0 jnz 0x117 00000127 C3 ret
The first 20 bytes is the executable part of the program. The next 20 bytes is the data read by the program. The executable bytes are identical to the data bytes. The executable part of the program has an outer loop that iterates twice. In each iteration, it reads the data bytes and writes them to standard output. Therefore, in two iterations of the outer loop, it writes the data bytes twice. In this manner, the output is identical to the program itself.
Here is another simpler 32-byte quine based on this approach:
b8 23 09 fe c0 a2 20 01 ba 10 01 cd 21 cd 21 c3
b8 23 09 fe c0 a2 20 01 ba 10 01 cd 21 cd 21 c3
Here are the commands to demostrate this quine:
echo b8 23 09 fe c0 a2 20 01 ba 10 01 cd 21 cd 21 c3 | xxd -r -p > quine.com
echo b8 23 09 fe c0 a2 20 01 ba 10 01 cd 21 cd 21 c3 | xxd -r -p >> quine.com
dosbox -c 'MOUNT C .' -c 'C:\QUINE > C:\OUT.COM' -c 'EXIT'
diff quine.com OUT.COM
Here is the disassembly:
$ ndisasm -o 0x100 quine.com 00000100 B82309 mov ax,0x923 00000103 FEC0 inc al 00000105 A22001 mov [0x120],al 00000108 BA1001 mov dx,0x110 0000010B CD21 int 0x21 0000010D CD21 int 0x21 0000010F C3 ret 00000110 B82309 mov ax,0x923 00000113 FEC0 inc al 00000115 A22001 mov [0x120],al 00000118 BA1001 mov dx,0x110 0000011B CD21 int 0x21 0000011D CD21 int 0x21 0000011F C3 ret
This example too has two parts. The first half has the executable
bytes and the second half has the data bytes. Both parts are
identical. This example sets AH to 9 in the first instruction and
then later uses int 0x21 to invoke the DOS service that
prints a dollar-terminated string beginning at address specifed in
DS:SI. When a .COM program starts, DS already points to the current
code segment, so we don't have to set it explicitly. The dollar
symbol has an ASCII code of 0x24 (decimal 36). We need to be careful
about not having this value anywhere within the the data bytes or
this DOS function would prematurely stop printing our data bytes as
soon as it encounters this value. That is why we set AL to 0x23 in
the first instruction, then increment it to 0x24 in the second
instruction, and then copy this value to the end of the data bytes
in the third instruction. Finally, we execute int 0x21
twice to write the data bytes twice to standard output, so that the
output matches the program itself.
While both these programs take care not to read the same memory region that is being executed by the CPU, the data bytes they read look exactly like the executable bytes. This is what I meant when I mentioned earlier that the lines between code and data are blurred in an exercise like this. This is why I don't really see a point in keeping the executable bytes separate from the data bytes while writing machine code quines.
A Note On DOS Services
The self-printing programs presented above use int 0x21
which offers DOS services that support various input/output
functions. We select the function to write a character to standard
output by setting AH to 2 before invoking this software interrupt.
The ret instruction in the end too relies on DOS
services. When a .COM program starts, the register SP contains
0xfffe. The stack memory locations at offset 0xfffe and 0xffff
contain 0x00 and 0x00, respectively. Further, the memory address at
offset 0x0000 contains the instruction int 0x20 which
is a DOS service that terminates the program. As a result, executing
the ret instruction pops 0x0000 off the stack at 0xfffe
and loads it into IP. This results in the instruction int
0x20 at offset 0x0000 getting executed. This instruction
terminates the program and returns to DOS.
Relying on DOS services gives us a comfortable environment to work
with. In particular, DOS implements the notion of standard
output which lets us redirect standard output to a file. This
lets us conveniently compare the original program file and the
output file with the FC command and confirm that they
are identical.
But one might wonder if we could avoid relying on DOS services completely and still write a program that prints its own bytes to screen. We definitely can. We could write directly to video memory at address 0xb800:0x0000 and show the bytes of the program on screen. The next section shows how to do this.
Writing to Video Memory Directly
Here is an example of an 18-byte self-printing program that writes directly to the video memory at address 0xb800:0x0000.
fc b4 b8 8e c0 31 ff b1 12 b4 0a ac ab e2 fc f4 eb fdHere are the commands to create and run this program:
echo fc b4 b8 8e c0 31 ff b1 12 b4 0a ac ab e2 fc f4 eb fd | xxd -r -p > quine.com
dosbox quine.com
With the default code page active, i.e., with code page 437 active, the program should display an output that looks approximately like the following and halt:
ⁿ┤╕Ä└1 ▒↕┤◙¼½Γⁿ⌠δ²
Now of course this type of output looks gibberish but there is a
quick and dirty way to confirm that this output indeed represents
the bytes of our program. We can use the TYPE command
of DOS to print the program and check if the symbols that appear in
its output seem consistent with the output above. Here is an
example:
C:\>TYPE QUINE.COM
ⁿ┤╕Ä└1 ▒↕┤
¼½Γⁿ⌠δ²
C:\>
This output looks very similar to the previous one except that the byte value 0x0a is rendered as a line break in this output whereas in the previous output this byte value is represented as a circle in a box. This method would not have worked if there were any control characters such as backspace or carriage return that result in characters being erased in the displayed output.
A proper way to verify that the output of the program represents the bytes of the program would be to find each symbol in the output in a chart for code page 437 and confirm that each byte value that occurs in the chart for each symbol matches each byte value in the program. Here is one such chart that approximates the symbols in code page 437 with Unicode symbols: cp437.html.
Here is the disassembly of the above program:
$ ndisasm -o 0x100 quine.com 00000100 FC cld 00000101 B4B8 mov ah,0xb8 00000103 8EC0 mov es,ax 00000105 31FF xor di,di 00000107 B112 mov cl,0x12 00000109 B40A mov ah,0xa 0000010B AC lodsb 0000010C AB stosw 0000010D E2FC loop 0x10b 0000010F F4 hlt 00000110 EBFD jmp short 0x10f
This program sets ES to 0xb800 and DI to 0. Thus ES:DI points to the
video memory at 0xb800:0x0000. DS:SI points to the first instruction
of this program by default. Further AH is set to 0xa. This is used
to specify the colour attribute of the text to be displayed on
screen. Each iteration of the loop in this program loads a byte of
the program and writes it along with the colour attribute to video
memory. The lodsb instruction loads a byte of the
program from the memory address specified by DS:SI into AL and
increments SI by 1. AH is already set to 0xa. The value 0xa (binary
00001010) here specifies black as the background colour and bright
green as the foreground colour. The stosw instruction
stores a word from AX to the memory address specified by ES:DI and
increments DI by 2. In this manner, the byte in AL and its colour
attribute in AH gets copied to the video memory.
Once again, if you are not happy about the program reading its own executable bytes, we can keep the bytes we read separate from the bytes the CPU executes. Here is a 54-byte program that does this:
fc b3 02 b4 b8 8e c0 31 ff be 1b 01 b9 1b 00 b4
0a ac ab e2 fc 4b 75 f1 f4 eb fd fc b3 02 b4 b8
8e c0 31 ff be 1b 01 b9 1b 00 b4 0a ac ab e2 fc
4b 75 f1 f4 eb fd
Here is how we can create and run this program:
echo fc b3 02 b4 b8 8e c0 31 ff be 1b 01 b9 1b 00 b4 | xxd -r -p > quine.com
echo 0a ac ab e2 fc 4b 75 f1 f4 eb fd fc b3 02 b4 b8 | xxd -r -p >> quine.com
echo 8e c0 31 ff be 1b 01 b9 1b 00 b4 0a ac ab e2 fc | xxd -r -p >> quine.com
echo 4b 75 f1 f4 eb fd | xxd -r -p >> quine.com
dosbox quine.com
With code page 437 active, the output should look approximately like this:
ⁿ│☻┤╕Ä└1 ╛←☺╣← ┤◙¼½ΓⁿKu±⌠δ²ⁿ│☻┤╕Ä└1 ╛←☺╣← ┤◙¼½ΓⁿKu±⌠δ²
We can clearly see in this output that the first 27 bytes of output are identical to the next 27 bytes of the output. Like the proper quines discussed earlier, this one too has two halves that are identical to each other. The executable code in the first half reads the data bytes from the second half and prints the data bytes twice so that the output bytes is an exact copy of all 54 bytes in the program. Here is the disassembly:
$ ndisasm -o 0x100 quine.com 00000100 FC cld 00000101 B302 mov bl,0x2 00000103 B4B8 mov ah,0xb8 00000105 8EC0 mov es,ax 00000107 31FF xor di,di 00000109 BE1B01 mov si,0x11b 0000010C B91B00 mov cx,0x1b 0000010F B40A mov ah,0xa 00000111 AC lodsb 00000112 AB stosw 00000113 E2FC loop 0x111 00000115 4B dec bx 00000116 75F1 jnz 0x109 00000118 F4 hlt 00000119 EBFD jmp short 0x118 0000011B FC cld 0000011C B302 mov bl,0x2 0000011E B4B8 mov ah,0xb8 00000120 8EC0 mov es,ax 00000122 31FF xor di,di 00000124 BE1B01 mov si,0x11b 00000127 B91B00 mov cx,0x1b 0000012A B40A mov ah,0xa 0000012C AC lodsb 0000012D AB stosw 0000012E E2FC loop 0x12c 00000130 4B dec bx 00000131 75F1 jnz 0x124 00000133 F4 hlt 00000134 EBFD jmp short 0x133
This disassembly is rather long but we can clearly see that the bytes from offset 0x100 to offset 0x11a are identical to the bytes from offset 0x11b to 0x135. These are the bytes we see in the output of the program too.
© 2001–2022 Susam Pal
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK