# Computer Archiecture 2022: Term Project - Reduce memory usage for DOOM
## Prepare
### Prepare GNU Toolchain for RISC-V.
1. See [The xPack GNU RISC-V Embedded GCC](https://xpack.github.io/riscv-none-elf-gcc/)
```shell
$ cd /tmp
$ wget https://github.com/xpack-dev-tools/riscv-none-elf-gcc-xpack/releases/download/v12.2.0-1/xpack-riscv-none-elf-gcc-12.2.0-1-linux-x64.tar.gz
$ tar zxvf xpack-riscv-none-elf-gcc-12.2.0-1-linux-x64.tar.gz
$ cp -af xpack-riscv-none-elf-gcc-12.2.0-1 $HOME/riscv-none-elf-gcc
```
2. Configure `$PATH`
```shell
$ cd $HOME/riscv-none-elf-gcc
$ echo "export PATH=`pwd`/bin:$PATH" > setenv
```
Once step (1) and (2) are complete, you can simply update `$PATH` environment variable via:
```shell
$ cd $HOME
$ source riscv-none-elf-gcc/setenv
```
### Prepare rv32emu
```shell
$ cd $HOME
$ git clone https://github.com/sysprog21/rv32emu
$ cd rv32emu
$ make
```
### Prepare doom & compile it
```shell
$ cd $HOME
$ git clone https://github.com/sysprog21/doom_riscv
$ cd doom_riscv-rv32emu/src/riscv
// edit makefile's line 1 CROSS ?= from riscv-none-embed- to riscv-none-elf-
$ make
```
if succeess it will show like below
```
lto-wrapper: warning: using serial compilation of 4 LTRANS jobs
lto-wrapper: note: see the '-flto' option documentation for more information
riscv-none-elf-size doom-riscv.elf
text data bss dec hex filename
546200 86324 1420317 2052841 1f52e9 doom-riscv.elf
```
### run doom on rv32emu
fiest we make doom for dowmload ensntial file like DOOM1.WAD
```shell
$ cd ./rv32emu
$ make doom
```
run doom
```shell
$ cp $HOME/doom_riscv-rv32emu/src/riscv/doom-riscv.elf $HOME/rv32emu/build
$ cd build
$ ./rv32emu ./doom-riscv.elf
```
## study DOOM with and for reduce memory use
reference 1: [embeddedDOOM](https://github.com/cnlohr/embeddedDOOM)
reference 2: [Studying Doom's source code - where to start?](https://www.doomworld.com/forum/topic/106971-studying-dooms-source-code-where-to-start/?fbclid=IwAR3v0egqZ6SmlU1bNyBQoLCIiZXn-Ajp3gS_X3G2uu0GxLni8OERSkS-VEw)
reference 3: [GAME ENGINE BLACK BOOK DOOM](https://fabiensanglard.net/b/gebbdoom.pdf)
### DOOM ARCHITECTURE
browse the Black Book chapter 5 to understand the structure of Doom. It helps me to understand the purpose of each source code.
blow show Prefixes's meaning on each source code
```
V_ is for Video, M_ is for Menu, Z_ is for Zone Memory Allocator,
R_ is for Renderer, P_ is for gamePlay, I_ is for plementation dependent,
D_ is for main Doom, S_ is for Sound, HU_ is for HUD, and ST_ is for STatus bar.
```
below pictue show DOOM source code architecture (source: [GAME ENGINE BLACK BOOK page 192](https://fabiensang#endiflard.net/b/gebbdoom.pdf))
### embeddedDOOM
First I read README.md and see what has it done, finally i focuse on implement "CombinedScreens" and "cut blood transitions" ,beacuse both are relation and intuition
below is embeddedDOOM say what is "CombinedScreens"
```
Framebuffer lives in this space. It's CombinedScreens -- Note: This is not the normal behavior, normally DOOM Keeps 4 copies of each screen, but we just lie and alias all 4 copies. It does mean you can't get the blood transitions between levels and the end screens get a tad sloppy.
```
### blood transitions
What is "blood transition", base on GAME ENGINE BLACK BOOK DOOM, we can know "blood transition" be called "Wipe" in BLACK BOOK DOOM, Also known as the "screen melt",it is used to transition between sections of the game.
We need two buffer to implement "blood transitions", buffer's size is same as screen size, it means we need two times of screen buffer space.
Below is GAME ENGINE BLACK BOOK DOOM explain what is blood transitions on DOOM
```
"Wipe" takes whatever is in framebuffer #2 and progressively transforms it into what is stored in framebuffer #3, writing the output into framebuffer #0.
The first step is to reorganize the two sources of data from row major to column major. This is done so the read operations on vertical strips play nicely with the 486 cachelines.
After that, a random sequence of 160 numbers is generated in an array y where each value is within 16 units of its two neighbors. These are used to form the top "wave".
The animation is made so columns of pixels from the source are falling down, letting the destination show behind, as if the source image had been wiped off the screen.
During the animation, columns two pixels wide and 200 pixels tall are copied repeatedly from src and dest to framebuffer #0. All columns fall at the same speed but they are offset by values in y, hence producing the wipe illusion.
```
Below is show what "blood transition" look like
### observe how to cut blood transitions
the blood transitions is in f_wipe.c, almost all the function in here will be abandon, only leave wipe_StartScreen(), wipe_EndScreen(), wipe_ScreenWipe().
wipe_StartScreen() is for save current Scenes in buffer#2.
wipe_EndScreen() is for caculate next Scenes and save to buffer#3.
wipe_ScreenWipe() is function to do blood transitions.
During blood transitions impelment, it will call malloc twice, and free then when blood transitions function end.
total malloc size is 130560 byte, if we cut blood transitions maybe we can save 130560 bytes on heap.
blow show function call will call malloc in f_wipe.c
```
wipe_initMelt(){
...
y = (int *) Z_Malloc(width*sizeof(int), PU_STATIC, 0); // 320 * 8 = 2560byte
...
}
wipe_shittyColMajorXform(){
...
dest = (short*) Z_Malloc(width*height*2, PU_STATIC, 0); // 320 * 200 * 2 = 128000
...
}
```
Because We don't need wipe effect so we only need take buffer#3(next Scenes) to buffer#0(screen output)
the change show below:
```diff
-int
-wipe_ScreenWipe
-( int wipeno,
- int x,
- int y,
- int width,
- int height,
- int ticks )
-{
- int rc;
- static int (*wipes[])(int, int, int) =
- {
- wipe_initColorXForm, wipe_doColorXForm, wipe_exitColorXForm,
- wipe_initMelt, wipe_doMelt, wipe_exitMelt
- };
- void V_MarkRect(int, int, int, int);
- // initial stuff
- if (!go)
- {
- go = 1;
- // wipe_scr = (byte *) Z_Malloc(width*height, PU_STATIC, 0); // DEBUG
- wipe_scr = screens[0];
- (*wipes[wipeno*3])(width, height, ticks);
- }
- // do a piece of wipe-in
- V_MarkRect(0, 0, width, height);
- rc = (*wipes[wipeno*3+1])(width, height, ticks);
- // V_DrawBlock(x, y, 0, width, height, wipe_scr); // DEBUG
- // final stuff
- if (rc)
- {
- go = 0;
- (*wipes[wipeno*3+2])(width, height, ticks);
- }
- return !go;
-}
+int
+wipe_ScreenWipe
+( int wipeno,
+ int x,
+ int y,
+ int width,
+ int height,
+ int ticks )
+{
+ just copy screen[3] to screen[0]
+ memcpy( screens[0], wipe_scr_end, width*height );
+ return 1;
+}
```
### observe how to Combiescreen
If we cut blood transitions, it mean we do not need screen buffer#2、screen buffer#3 so we can save 128000(320 * 200 * 2) byte
buffer#1 is for savedata and some backscreen paattern, we can draw directly in screen and save and load function has some probelm now, so we can ignore it too, this way can save 64000(320 *200) byte.
we just make 4 scrren buffer pointer to same address
```diff
+ base = I_AllocLow(SCREENWIDTH*SCREENHEIGHT);
+ for (i=0 ; i<4 ; i++)
+ screens[i] = base;
- base = I_AllocLow (SCREENWIDTH*SCREENHEIGHT*4);
- for (i=0 ; i<4 ; i++)
- screens[i] = base + i*SCREENWIDTH*SCREENHEIGHT;
```
## Evaluation
For evaluation my improve i replace dynamic memory allocation by static memory allocation
like this
```diff=
i_system.c
+ CombinedScreens[SCREENWIDTH*SCREENHEIGHT*4]
byte* I_AllocLow(int length)
{
+ byte* mem;
+ mem = CombinedScreens;
+ memset (mem,0,length);
+ return mem;
- //return calloc(1, length);
}
+ #define DOOM_HEAP_SIZE 6*1024*1024
+ nsigned char DOOMHeap[DOOM_HEAP_SIZE];
byte* I_ZoneBase(int *size)
{
/* Give 6M to DOOM */
- *size = 6 * 1024 * 1024;
- return (byte *) malloc (*size);
+ *size = DOOM_HEAP_SIZE;
+ return (byte *) DOOMHeap;
}
```
original code, only replace dynamic memory allocation by static memory allocation
```shell
$ riscv-none-elf-size doom-riscv.elf
text data bss dec hex filename
546200 86324 8633373 9265897 8d62e9 doom-riscv.elf
```
cut blood transition(I Don't change heapsize)
```shell
riscv-none-elf-size doom-riscv.elf
text data bss dec hex filename
545368 86324 8633361 9265053 8d5f9d doom-riscv.elf
```
combine screen + cut blood transition
```shell
riscv-none-elf-size doom-riscv.elf
text data bss dec hex filename
545348 86324 7942161 8573833 82d389 doom-riscv.elf
```
combine screen + cut blood transition(Cut heap size)
```shell
riscv-none-elf-size doom-riscv.elf
text data bss dec hex filename
545352 86324 7811601 8443277 80d589 doom-riscv.elf
```
## TO DO
1. find complete way to make sure all the change is work perfect, I just play it a little to make sure it can play.
2. maybe wipe_StartScreen() is nolonger need?
3. Cacluate How many space will be actually allocate, in this way we can reduce DOOMHeap size(6M -> ?).
4. if use "combine screen" it may cause some problem when saveing data because saveing game function will use screen buffer, maybe we need extra space for saveing.
```
void G_DoSaveGame (void) {
...
save_p = savebuffer = screens[1]+0x4000;
...
}
```
Sign in with Wallet
Connect another wallet