The maze output program at 13 ... no. 10 bytes!
In the past, having found an interesting solution when writing a demo, I quietly used it or boasted to a narrow circle of friends in the demoscene. But now my opportunities to achieve something at the demostsena have come to an end, and minimalist programming tournaments are not held, so I decided to write a blog about my achievement: a maze generator with just 13 bytes of x86 machine code.
To understand the essence of the achievement, you need to know about the team 10 PRINT. This is a line of Commodore 64 BASIC code that, when launched, creates an infinite maze. Of course, its conclusion is not a real labyrinth, there is no entrance and exit there, and it is full of enclosed spaces and dead ends. But it looks like a labyrinth. It is amazing how a simple command produces an infinitely complex pattern.
Also under the name “10 PRINT” a book of 324 pages was published. She talks about code, art, perception, culture, chance, mazes and everything else. It is recommended for reading to anyone who is interested in programming - for everyone there will be interesting topics that are also very well lit and decorated.
Let's go back to the code. In the book “10 PRINT” I read that the code from BASIC can be represented in a more compact form in the machine code C64. There was also a problem for readers. The record was set up by 4-Mat and Wisdom comrades, who pushed the solution into 15 bytes. I wondered how this can be done on x86. So I wrote the first version of this program:
')
This code behaves “decently”, does not make assumptions about the state of the processor and quits (the original version 10 PRINT worked indefinitely). A random number is more or less well generated from the iron timer, which counts from 65535 to 0 every second. When compiling a86, the 42-byte .COM file comes out
The size is very different from C64 in two places: a random number generator and symbol selection. The C64 has an advantage in symbols, since both slashes are next to PETSCII. If you have a random bit, you can simply add it to the first slash, and get either it or the second slash. When using ASCII, this does not work, you have to use a condition.
Then, for optimization, I decided to remove the selection condition. When you shift the code of one of the slashes, both slashes start to differ in just one bit.
Therefore, it is possible to replace the pickch piece:
It was cool, but as a result, the size increased to 48 bytes. I had to drop the idea.
Another optimization is to remove the writec output procedure, and just push the bytes into the video memory. This removed two bytes from the output procedure, but added 4 bytes to the tuning (and 5, if it remained within the 8086 standard), so it also had to be discarded.
I took a closer look at the largest segment of the program - the random number generator. It is obvious that the quality of the generator does not concern us much - the main thing is that there should be no obvious repetitions. Therefore, I replaced the “getrnd” block with a single LODSB instruction. It takes out a byte from memory and goes to the next one, so you can read the sequence from memory. And the place from which I started reading is where DS: SI shows when the program starts. For a COM file in DOS, it indicates the beginning of the program itself. Therefore, my "random" stream was determined by the compiled code itself, and all kinds of garbage from other programs. As a result, the code is greatly reduced to 25 bytes.
Here I already got excited - an opportunity to approach the size of the C64 version appeared. I got rid of all kinds of gestures such as changing video mode, clean output (now the program works forever) and register initialization. At the end it looked like this:
15 bytes is a success!
Everything seemed to me that I could improve the pickch block. The block starts with assigning a random variable to the carry flag, but the 8086 has a parity flag, which is automatically set in some cases. Unfortunately, LODSB flags are not cocked. A mathematical operation would have raised the parity flag, but such an operation would have taken more space. If you could find a single-byte instruction that does the same thing as LODSB and cocks the parity flag depending on the input data ...
There is such an instruction! SCAS - loads a byte, compares it with AL, and cocks the flag according to the results of the comparison. It is intended for use in a loop, but no one bothers to use it without a loop. And as a result:
And here you are 13 bytes. It even works on old IBM PCs, since it does not use instructions from 80186+. Approximate output:
Reader Peter Ferier has managed to improve my achievement by one byte.
Bravissimo. However, the reader herm1t noted that if we use int 29h to output a character, then the code is reduced to
Cleverly. But wait a minute, that's not all!
Peter struck back and cracked another byte (this code will not work on non-Intel processors such as the NEC V20 or V30).
To understand the essence of the achievement, you need to know about the team 10 PRINT. This is a line of Commodore 64 BASIC code that, when launched, creates an infinite maze. Of course, its conclusion is not a real labyrinth, there is no entrance and exit there, and it is full of enclosed spaces and dead ends. But it looks like a labyrinth. It is amazing how a simple command produces an infinitely complex pattern.
Also under the name “10 PRINT” a book of 324 pages was published. She talks about code, art, perception, culture, chance, mazes and everything else. It is recommended for reading to anyone who is interested in programming - for everyone there will be interesting topics that are also very well lit and decorated.
42 bytes
Let's go back to the code. In the book “10 PRINT” I read that the code from BASIC can be represented in a more compact form in the machine code C64. There was also a problem for readers. The record was set up by 4-Mat and Wisdom comrades, who pushed the solution into 15 bytes. I wondered how this can be done on x86. So I wrote the first version of this program:
')
; , "10 PRINT" ; "" ; . ; ; ; . init: mov ax,0001h int 10h ; 40x25 xor bh,bh ; , vidpage=0 mov cx,(40*23) ; getrnd: xor ax,ax ; al=0 pushf cli ; , out 43h,al ; in al,40h ; lobyte mov ah,al in al,40h ; hibyte popf ; xchg ah,al ; 8253 raw 16-bit word pickch: shr ax,1 ;BIOS count-by-2, lo shr ax,1 ; carry = "" mov al,'\' jc writec ; , mov al,'/' ; writec: mov ah,0eh ; int 10h loop getrnd int 20h ; DOS This code behaves “decently”, does not make assumptions about the state of the processor and quits (the original version 10 PRINT worked indefinitely). A random number is more or less well generated from the iron timer, which counts from 65535 to 0 every second. When compiling a86, the 42-byte .COM file comes out
The size is very different from C64 in two places: a random number generator and symbol selection. The C64 has an advantage in symbols, since both slashes are next to PETSCII. If you have a random bit, you can simply add it to the first slash, and get either it or the second slash. When using ASCII, this does not work, you have to use a condition.
Then, for optimization, I decided to remove the selection condition. When you shift the code of one of the slashes, both slashes start to differ in just one bit.
"/"=2f "\"=5c 2f=00101111 5c=01011100 Therefore, it is possible to replace the pickch piece:
pickch: shr ax,1 ;BIOS count-by-2, lo push cx ; mov cl,al ; cl and cl,1 ;cl 0 1 mov al,'\' ; '\' shr al,cl or al,cl ; cl=1, '\' '/', – It was cool, but as a result, the size increased to 48 bytes. I had to drop the idea.
Another optimization is to remove the writec output procedure, and just push the bytes into the video memory. This removed two bytes from the output procedure, but added 4 bytes to the tuning (and 5, if it remained within the 8086 standard), so it also had to be discarded.
25 bytes
I took a closer look at the largest segment of the program - the random number generator. It is obvious that the quality of the generator does not concern us much - the main thing is that there should be no obvious repetitions. Therefore, I replaced the “getrnd” block with a single LODSB instruction. It takes out a byte from memory and goes to the next one, so you can read the sequence from memory. And the place from which I started reading is where DS: SI shows when the program starts. For a COM file in DOS, it indicates the beginning of the program itself. Therefore, my "random" stream was determined by the compiled code itself, and all kinds of garbage from other programs. As a result, the code is greatly reduced to 25 bytes.
15 bytes
Here I already got excited - an opportunity to approach the size of the C64 version appeared. I got rid of all kinds of gestures such as changing video mode, clean output (now the program works forever) and register initialization. At the end it looked like this:
init: mov ah,0eh ;10h getrnd: lodsb ; , DS:SI pickch: shr al,1 ;carry = "" mov al,'\' jc writec ; , mov al,'/' ; writec: int 10h ; jmp getrnd ; 15 bytes is a success!
13 bytes
Everything seemed to me that I could improve the pickch block. The block starts with assigning a random variable to the carry flag, but the 8086 has a parity flag, which is automatically set in some cases. Unfortunately, LODSB flags are not cocked. A mathematical operation would have raised the parity flag, but such an operation would have taken more space. If you could find a single-byte instruction that does the same thing as LODSB and cocks the parity flag depending on the input data ...
There is such an instruction! SCAS - loads a byte, compares it with AL, and cocks the flag according to the results of the comparison. It is intended for use in a loop, but no one bothers to use it without a loop. And as a result:
init: mov ah,0eh ;10h getrnd: scasb ; ES:DI AL ; pickch: mov al,'\' ; jc writec ; , mov al,'/' ; writec: int 10h ; jmp getrnd ; And here you are 13 bytes. It even works on old IBM PCs, since it does not use instructions from 80186+. Approximate output:
12 bytes
Reader Peter Ferier has managed to improve my achievement by one byte.
init: mov ax,0e5ch ; AH cmd " " AL '\' scasb ; ES:DI AL ;this sets flags similar to a subtraction pickch: jp writec ; , AL mov al,'/' ; writec: int 10h ; AL jmp init ; Bravissimo. However, the reader herm1t noted that if we use int 29h to output a character, then the code is reduced to
11 bytes
init: mov al, '\' scasb jp writec mov al, '/' writec: int 29h jmp init Cleverly. But wait a minute, that's not all!
10 bytes
init: scasb salc and al,'\'-'/' add al,'/' int 29h jmp init Peter struck back and cracked another byte (this code will not work on non-Intel processors such as the NEC V20 or V30).
Source: https://habr.com/ru/post/251631/
All Articles