Game of Life 32b - Revision history

HellMood: /* Switching to Textmode : 38 bytes */

2020-05-04T10:27:00Z

‎Switching to Textmode : 38 bytes

HellMood at 21:54, 30 April 2020

2020-04-30T21:54:38Z

HellMood: clearer explanation, thanks gargaj

2020-04-30T18:52:25Z

clearer explanation, thanks gargaj

HellMood: /* Modbyte tuning, jumping into modbytes, code path alignment : 32b */

2020-04-30T18:32:32Z

‎Modbyte tuning, jumping into modbytes, code path alignment : 32b

HellMood: /* Original version : 65 bytes */

2020-04-30T18:05:02Z

‎Original version : 65 bytes

HellMood: /* Modbyte tuning, jumping into modbytes, code path alignment : 32b */

2020-04-30T17:57:28Z

‎Modbyte tuning, jumping into modbytes, code path alignment : 32b

HellMood at 17:14, 30 April 2020

2020-04-30T17:14:40Z

HellMood at 17:11, 30 April 2020

2020-04-30T17:11:28Z

HellMood: /* Synchronizing SI/DI, Improved cleanup : 34 bytes */

2020-04-30T16:56:41Z

‎Synchronizing SI/DI, Improved cleanup : 34 bytes

HellMood at 16:47, 30 April 2020

2020-04-30T16:47:42Z

@@ Line 134: / Line 134: @@
 [[File:Golt38.png|thumb|game of life, text mode, 32b - 38b]]
 == Switching to Textmode : 38 bytes==
-Setting up screen mode and pixel access is requiring quite a bit of space, so in this version, it is removed. That is directly punished with an additional byte, because <code>DI</code> is no longer involved in the process, thus, an optimization had to be removed. The assumption is that the computer this runs on, is already in text mode (40x25 chars, colors). This also helps with the calculation, since now it takes place directly on the screen (only one segment has to be set up) and no content has to be generated initially, since there is always at least something on the screen that works as seed value. A small downside is the alignment of cells, because in textmode, one cell occupies TWO bytes (one for color information). Luckily, the color information is by default set to "gray on black". An additional <code>dec bx</code>, replacing <code>lodsb</code> with <code>lodsw</code> and changing <code>mov bl,3</code> to <code>mov bl,6</code> helps fixing the alignment issue. Additionally, the screen address changed (<code>push 0xb800</code> <code>pop ds</code>) Another lucky coincident is, that instead of blue pixels, we now have a "smiley char" with orthogonal borders, which is a decent representation of a living cell. Inbetween marking and correction it shortly changes to an exclamation mark (!), which is barely visible.
+Setting up screen mode and pixel access is requiring quite a bit of space, so in this version, it is removed. That is directly punished with an additional byte, because <code>DI</code> is no longer involved in the process, thus, an optimization had to be removed. The assumption is that the computer this runs on, is already in text mode (80x25 chars, colors). This also helps with the calculation, since now it takes place directly on the screen (only one segment has to be set up) and no content has to be generated initially, since there is always at least something on the screen that works as seed value. A small downside is the alignment of cells, because in textmode, one cell occupies TWO bytes (one for color information). Luckily, the color information is by default set to "gray on black". An additional <code>dec bx</code>, replacing <code>lodsb</code> with <code>lodsw</code> and changing <code>mov bl,3</code> to <code>mov bl,6</code> helps fixing the alignment issue. Additionally, the screen address changed (<code>push 0xb800</code> <code>pop ds</code>) Another lucky coincident is, that instead of blue pixels, we now have a "smiley char" with orthogonal borders, which is a decent representation of a living cell. Inbetween marking and correction it shortly changes to an exclamation mark (!), which is barely visible.
 <syntaxhighlight lang="nasm">

← Older revision		Revision as of 21:54, 30 April 2020
Line 1:		Line 1:
−	~~This writeup is still in the works! Come back later to get information on all the mean tricks ;) Meanwhile you~~ can [https://www.pouet.net/prod.php?which=85485 download and comment] the intro.	+	You can [https://www.pouet.net/prod.php?which=85485 download and comment] the intro.

	==Original version : 65 bytes==		==Original version : 65 bytes==

@@ Line 231: / Line 231: @@
 ==Modbyte tuning, jumping into modbytes, code path alignment : 32 bytes==
 [[File:Modbyte to 100h.png|frame|right|lds_modbyte_instructions]]
-Sometimes, an instruction has several degrees of "freedom". That means, that the effect of that instruction can also be achieved by an alternative version of that instruction. In this case, the <code>lds</code> instruction, which puts two bytes of the code into the segment DS, also loads two bytes into a register we (almost) don't care about. The only requirement is that <code>lds</code> points to the start of the code, which can either be done by [SI] or [BX+SI]. The right image shows which modbyte numbers would be satisfying (highlighted green). Now, this selection can be applied to the instruction table below (highlighted red). It becomes clear that the used instruction<code>and al,0x20</code> would, interpreted as modbyte, be <code>SP,[SI]</code> and thus it would be possible to jump into this modbyte to execute.
+Sometimes, an instruction has several degrees of "freedom". That means, that the effect of that instruction can also be achieved by an alternative version of that instruction. In this case, the <code>lds</code> instruction, which puts two bytes of the code into the segment DS, also loads two bytes into a register we (almost) don't care about. The only requirement is that <code>lds</code> points to the start of the code, which can either be done by [SI] or [BX+SI]. The right image shows which modbyte numbers would be satisfying (highlighted green). Now, this selection can be applied to the instruction table below (highlighted red). It becomes clear that the used instruction<code>and al,0x20</code> would, interpreted as modbyte, be <code>SP,[SI]</code> and thus it would be possible to jump into this modbyte to execute. <br/><br/>
 <br/>To make this work, the "host" instruction has to be only executed once (it would not work in a loop). Also, the parameter of the injected instruction has to be put "behind" the "host" instruction (a single <code>db 32</code> in the code). Finally, it has to be made sure that this second code path aligns with the rest of the code, and does no damage to the intended effect (for example, critical registers could be modified, or worse, illegal instructions could be created that way). In this case the new codepath consists of <code>and [bp+di+0807h],dh</code> and <code>add al,0a7h</code>, after which it aligns normally. These instructions are executed only once and do not modify critical registers.<br/>
 Sometimes, a bit of code shuffling has to be performed to make such a trick work. Here, the <code>lodsb</code> and <code>dec si</code> have been replaced with <code>mov al,[si]</code>. The critical function of being also a good segment value has been overtaken by <code>mov bl</code> (see table above).<br/>

@@ Line 229: / Line 229: @@
           jmp short LifeLoop
 </syntaxhighlight>
-==Modbyte tuning, jumping into modbytes, code path alignment : 32b==
+==Modbyte tuning, jumping into modbytes, code path alignment : 32 bytes==
 [[File:Modbyte to 100h.png|frame|right|lds_modbyte_instructions]]
 Sometimes, an instruction has several degrees of "freedom". That means, that the effect of that instruction can also be achieved by an alternative version of that instruction. In this case, the <code>lds</code> instruction, which puts two bytes of the code into the segment DS, also loads two bytes into a register we (almost) don't care about. The only requirement is that <code>lds</code> points to the start of the code, which can either be done by [SI] or [BX+SI]. The right image shows which modbyte numbers would be satisfying (highlighted green). Now, this selection can be applied to the instruction table below (highlighted red). It becomes clear that the used instruction<code>and al,0x20</code> would, interpreted as modbyte, be <code>SP,[SI]</code> and thus it would be possible to jump into this modbyte to execute.

@@ Line 5: / Line 5: @@
 <br />
-It will help to understand what the core algorithm does, before optimizing it. I will not go into the details of random number generation and key handling since these parts are removed in the final version anyway. Setting up screen mode and putting pixels to the screen is described in the basic sectionn of this Wiki. The core routine computes the [https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Rules "normal" game of life rules, but with a twist. Instead of regarding only eight neighbour cells inside a 3x3 neighbourhood , ALL nine cells are taken into consideration, and the rules are reinterpreted as:
+It will help to understand what the core algorithm does, before optimizing it. I will not go into the details of random number generation and key handling since these parts are removed in the final version anyway. Setting up screen mode and putting pixels to the screen is described in the basic sectionn of this Wiki. The core routine computes the [https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life#Rules "normal" game of life rules], but with a twist. Instead of regarding only eight neighbour cells inside a 3x3 neighbourhood , ALL nine cells are taken into consideration, and the rules are reinterpreted as:
 <br />
 * If the number of cells is 3, the center cell will be alive.

@@ Line 202: / Line 202: @@
           add  cl,[si+bx+160-4]
           dec  bx               ; Loop back
           dec  bx               ; Loop back
           jnz  AccLoop
           jmp short LifeLoop
 </syntaxhighlight>

@@ Line 183: / Line 183: @@
 == Synchronizing SI/DI, Improved cleanup : 34 bytes ==
 A lot of tiny changes were the result of just one idea: How to optimize the clean up step? After all it is not really neccessary to correct a marked cell as soon as possible, instead, it can be waited for a certain amount of time/steps. But any nontrivial version of <code>shr byte [si-160-6],5</code> still uses four bytes, unless it is brought into one of the "pure" forms that only take up THREE bytes: <code>shr byte[(bp/bx)+si/di],x</code>. Since SI and BX were already in use, and the usage of BP would implicate that the register SS is used instead of DS, the only remaining register possible is DI.<br/>
+Now there are very short instructions available to advance the registers SI and DI, some of them at the same time, and one of them is <code>cmpsw</code>. Not only does it not "hurt" the intended computation (the "compare" part of the instruction can be ignored), it also advances both SI and DI by TWO, so that the alignment of the screen in text mode is perfectly matched.<br/>
 <syntaxhighlight lang="nasm">
 		 lds bx,[si]

@@ Line 173: / Line 173: @@
 		 xchg cx,ax
 AccLoop: add  cl,[si+bx-160-4]    ; Add in this column
           add  cl,[si+bx-4]
           add  cl,[si+bx+160-4]