DEV Community: Oskar Mendel

Creating good puzzle games

Oskar Mendel — Sat, 14 Jan 2023 13:08:47 +0000

During the last three weeks I have not spent too much time on just programming and instead addressed a topic of game development that I’ve just like many other more programmer-oriented game developers tend to postpone because it is quite difficult and needs serious deep mental work in order to turn out well.

Like I mentioned within my previous devlog I have already discovered once that my initial design of the game had flaws and instead of throwing the project away I am determined to interate on it to try make it better. In order to do this I have to put my designer hat on and really think about what makes a puzzle game good.

In this writeup I want to outline some of the things I’ve learned while studying during these weeks. Some of the points will seem very fundamental but I include them anyway in order to emphasize how important they are, and while some of the points are simple they are still not followed in many games.

Core mechanic

Traditionally a puzzle game revolves around a core mechanic, the mechanic is often simple enough to be explained with a single sentence and while simple it should be fully explored it can then be enhanced by several other mechanics if needed.

In the puzzle platformer, Braid the player has the power to rewind time as its core mechanic. Upon progressing the game introduces a new mechanic where some items are “magical” and not affected by the player’s power. Here a new mechanic is used in a way that hinders the player from utilizing their main ability but also opens the game up for a whole new set of states which itself gives more possibilities for interesting puzzles.

In the game Portal, the player is in charge of a gun that can open up portals that the player can walk through. In this game, the developers decided to bring in more mechanics that complement their core mechanics, for example, items in the world can travel through the portals as well as allow the player to experiment with using the portal in new ways with the different items in the world.

I believe the most elegant mechanics are the ones that give you all their power right from the start but are not directly visible and instead slowly present themselves to you as you progress. A good example of what I mean here is how the game Stephen's Sausage Roll does it, in other Sokoban-style games you often see several new mechanics introduced while you progress. Traditionally they start by pushing the box around the level but shortly after you are met with pressure plates, monsters, and many other different creations.

While this is not bad it is something I want to avoid as it gives the player a discovery feeling while stumbling on new unknown elements instead of the revelation that the player feels when reaching a deeper understanding of how the game works. I do not think this is beyond reach within a game that contains many different mechanics but I do believe it is harder to get right and for Brainroll I want to attempt to limit the number of mechanics and focus on the game’s core.

Linear and non-linear

Something I have thought a lot about when investigating other games is the two different forms of puzzle games. Linear puzzles are what you can call Brainroll today, you spawn into a level and once you complete that level you will move into the next. Non-linear, on the other hand, is a game that presents the user with multiple ways of solving the puzzles, the start and end goal may still be static but the tools available to the user gives for enough freedom to solve the puzzle in many ways.

I want to expand on this idea further a bit and also include the games that don’t have a linear set of levels for the user to complete. For example, in open-world style puzzle games the user is free to wander around and solve puzzles in whatever order they want. This is an important observation because this type of design allows the designer to build the game in a way where exploration is also a key part of reaching the revelation I mentioned earlier.

A good example is Jonathan Blow’s game The Witness where once you complete the “tutorial” the first puzzle you stumble upon is designed to be too hard for you to initially solve and the idea is for the player to try it, fail, and then move on and find another area which contains a much simpler subset of the same puzzle that teaches the player how to solve the previous one.

I don’t want to say that non-linear puzzle design is always better than linear but I do believe that if you do have a linear puzzle game such as Brainroll or another Sokoban-style game you can add a lot more depth into the game if you somehow connect the different levels. What I mean with this is for example if you utilize an overworld when the user navigates from level to level, this is a good opportunity for the overworld to also be a puzzle in interesting ways.

No Tutorials

Tutorials are a point of discussion, some games couldn’t be made without them, and many AAA games today wouldn’t survive without having tutorials upon tutorials for all their different systems and subsystems. It is not uncommon for these games to include skill trees, crafting, and perhaps different advanced attack combos. Having the players learn all of this would most likely take up so much of the core game that just learning how everything works would be the entire game, instead, it is just easier to strap short text prompts or messages on the screen with text that explains what you’re doing. One thing we all can agree on however is that text in games are almost always boring and just takes away the fun of playing the game. This is exactly what we want to strive for, letting the players just play the game. A quote often used is “A game with good game design explains itself” and this is also something I want to strive for in my games. The strategy that I apply when removing the need for tutorials is to incrementally introduce new things into the game, for example in Brainroll the first levels are just about movement, there are no real other mechanics to interact with and that allows the levels to be simple enough so that the players can just experiment their way to the goal. Allowing user freedom here is a great benefit to your game because the game will be more interesting if there is room for experimentation.

Level design language

Another advice I got and applied to my game design is that I try to think really hard about what I am asking the player to do in the level. For you who played the latest version of Brainroll there is a mechanic where a sleepy brain would stick to you on collision and you have to move them around in order to aid you reaching the goal. I created a set of levels and analyed them by writing down all the actions the user has to perform in order to complete them and by doing this I learned that the mechanic surounding the sleepy brain had another set of mechanics tied to it, by moving them around you had the oupportunity to arrange them in different patterns, by carefull positioning you can reach new places, they can be used as padding as if you were moving a wall around with you and finally you can sling them around corners.

While all of these mechanics are overlapping they are still distinct enough to have a language to use when describing the designed levels. This allows me to go into the level design with concrete ideas of what I want the level to be about. Instead of experimentation (which also can be very lucrative) I can go into the design mode by specifying for example that I want the player to arrange the sleepy brains to form the letter L for them to trigger a pressure plate that opens the next door. This can of course be achieved without having terms to describe the different actions your player performs but I still believe there is a benefit in making it more formal.

Don’t design backwards

Designing levels I’ve come to believe that it is bad to design backward, what I mean with this is if you choose to design your levels by placing down a start position and an end goal and solely move the level forward by finding ways to block the path between the player and the goal in different ways. I am sure this can yield success sometimes but to further dive into the mechanics you’ve created and learn what they are about you have to try to start from the other end as well, before even creating the level start with an idea, this idea can be very simple like “I want to design a level that looks like a skull” or even better “I want the player to use a sleepy brain as padding to slide between two walls”. All of the best levels I’ve created have come from this way of making them. Why I believe the backward route is bad is also because when I’ve done it that way, later when playing the levels something has always felt a bit off. I later concluded that the reason behind this weird feeling has been the result of artificial complexity being introduced into the level. What I mean by this is that the puzzle I’ve created wasn’t a puzzle with an idea, it was just something preventing you from reaching the goal. This is the same problem that Brainroll had before when the game was oriented around mazes, which just wasn’t interesting or fun. So try to design forwards, start with a good or interesting idea and explore how your game’s mechanics fare against this idea. In some cases, it won't work and then you’re at a crossroads where you have to decide as a game developer if you want to change the game to make it work or just accept that this idea won’t work in the game you’re making and move on.

I hope this was an interesting read, if you enjoyed it please consider checking out my other socials!

💻GITHUB 🐦TWITTER 🙏PATREON 🗨DISCORD 📹YOUTUBE

UI Subsystem Iteration

Oskar Mendel — Sat, 03 Dec 2022 21:16:53 +0000

The title already spoiled the subject as we’re going to dive into the UI system that has been implemented into my engine. In this post I will outline some of the improvements made to the current ui system that I've implemented for Maraton.

Graphical User Interface

A User Interface or UI for short is our medium of interaction with the machine. One of the most important goals that designers of interfaces have is to not have their users think too much about the interface itself. What this means is not that we want mindless and lazy users but instead, we want our interface to be as intuitive as possible to not force users to have to reason about what things do or how to do things.

The first step to address this is to build your user interface with components that users will already make the correct assumption on how to use. These components can be:

Buttons
Checkboxes
Radio buttons
Text fields
Sliders

Why this matters at all are because we’re building our UI system from scratch so we have the opportunity to define the behavior of all of our components ourselves, if we’re not trying to explicitly try to redefine how the components should work it wouldn’t make much sense to make the behavior different to how they work anywhere else. The reason for this is because as mentioned above that our users would most likely make the incorrect assumption of what happens when they for example click a button which will result in the user losing time and most likely getting frustrated.

For a button, the set of rules of operation may be pretty simple but for a text field, it can become more complex as it would involve tons of new keybinds, and perhaps you would need to implement a cursor allowing the user to see where they are when they’re writing which itself has a different set of behavior. All of the standard components actually have analog counterparts that we’re taught since childhood, for example the keys on your keyboard which acts just like the buttons inside an elevator. Or the knobs on your stove or microwave to control the heat acts like a slider.

This brings us to our first constraint on our user interface system: “Do not defy the standard behavior of user interface components but be flexible enough to allow it.”

Example of a control panel showcasing an analog interface with buttons, togglers and sliders (Source: Control Desk).

UI Modes

Designing a UI system has many exciting aspects to it, there are generally two styles of implementations for UI systems and they have two camps of developer communities split between them.

Retained mode

The first style is known as “Retained mode UI” and I would like to say that this is the most common style as it is adopted by many popular UI frameworks. The word “Retained” comes from the idea that this type of system retains the state of the UI across frames, the main idea is that the library or system retains the data of the scene and objects used to build it. Using this style you build an API that hides details from the user about the internally used objects, rendering primitives, and interaction with the different widgets are often done in an indirect fashion where you tell the library what you want to update and rely on it taking care of it. Retained mode is often but not limited to being built using the object-oriented style of programming.

Abstract diagram of retained mode ui. (Source: https://learn.microsoft.com/en-us/windows/win32/learnwin32/retained-mode-versus-immediate-mode)

Why this idea that is retained often is coupled with the object-oriented approach is that this model tends to be designed in a way where the users have to extend existing elements to build new constructs within the boundaries of the library. Hence this type of library is often designed in a way where the users are required to extend and inherit pre-defined behavior to create new elements that are not supported by default by the library. There are however no such limitations to this style, where extensibility in a procedural approach can be achieved with for example function pointers. If you are interested in diving further into this I recommend a tutorial that a developer that goes by nakst has put together that is available here. He also has a good library to learn from available on Github here.

Immediate mode

The second style that has grown in popularity in more recent years is the “Immediate mode UI” style. This approach has lately been frequently adopted by game developers because of its simplicity and how easy it is to learn and get started with especially in an environment where rapid iterations are of interest. In an Immediate mode system, the code that defines for example a button is also the same code that handles the rendering and code that checks if it was interacted with or not. This results in an extremely simple API for developers to consume were creating a button in your interface may becomes as simple as an if statement, for example:

if (Button("Click Me"))
{
    DoSomething();
}

If you do not want the button to be rendered in this case you simply do not call the Button function. This means that a lot of code that you write will be code that decides if the UI should be drawn or not but the simplicity of it all remains the same.

Abstract diagram of immediate mode ui. (Source: https://learn.microsoft.com/en-us/windows/win32/learnwin32/retained-mode-versus-immediate-mode)

In this style of library, all the data required is within the client code and not inside a library. This means that more weight is put on the user of the library which also allows for more freedom. Because of the “immediate nature” of the API and the fact that the user holds the data, the types of libraries that implement this tend to not store any internal state about what to draw and not which results in the immediate type interfaces often being redrawn every single frame. While some may argue that this is a drawback because it will result in a slow application I wouldn’t bother that much because the UI would have to be very complex before refilling your vertex buffers are going to be the bottleneck in your application and you will most likely find that optimizing other areas of your application will give more results than rendering your interface. One real drawback that between this and a retained mode style approach is that the library itself cannot make assumptions about what is and is not visible on the screen which can be a limitation for some projects.

Due to the simplicity of the immediate type of approach the libraries that you use also tend to introduce less bloat into your application, this is even part of the slogan for the most popular immediate mode libraries “Dear ImGui”. At the end of the day though you can build very powerful systems with both approaches and I for one would be interested in sinking my teeth into retained-mode in the future.

I have since chosen to stick with the immediate mode style because of the beforementioned reasons and with this we also get two more constraints for our UI system: “Designed for developer’s ease of use” & “Do not get in the way of development”.

The previous UI system

The old UI system for my game engine Maraton was an immediate mode-style implementation that had a few interesting concepts attached to it. This UI system was designed to work and not to be the most flexible system out there, but while working it was also designed to be flexible enough to be able to construct real applications. One of the most limiting factors of this system was that every widget was hard-wired to be a part of the system itself.

The code defining widgets in this system was built upon the idea of discriminated unions (also known as “tagged unions”), it was all built on code that looks like the following:

enum ui_widget_type
{
    UI_WidgetType_Button,
    UI_WidgetType_Slider,
    ...
};

struct ui_widget
{
    ui_widget_type Type;

    struct
    {
        ...
    } button;

    struct
    {
        ...
    } slider;
};

While I love this structure of code it has serious issues when trying to build a flexible system because we are already declaring a button and a slider to be two separate things while in practice they are very similar and utilize many of the same properties. This design gave me many troubles with the engine in the past because every time I wanted to support something new like a button using a texture instead of text and then a toggler with the same thing then perhaps a scrollable list, it all ended up with me having to do quite a bit of work inside the internals for the engine and the library code gave me very little power when it comes to extending it or making small tweaks. This already breaks the first and third constraints that we set up for our UI system.

Another lacking part of the system was that it did not have any internal support for autolayouting, this means that the entire system was based on you keeping track of where everything is. There was a concept of rows and columns but how big they are and where they are located on the screen was part of the API and something the user had to keep track of, an example UI from my game Brainroll looked something like this:

UIPushTextColor(UI, Vector4Init(1.0f, 1.0f, 1.0f, FadeInOutTransparency));
vector2 Size = Vector2Init(400, 80);
vector2 Position = Vector2Init(ScreenWidth / 8.0f, ScreenHeight / 2.0f - (Size.Y * 5) / 2.0f);
UIPushColumn(UI, Position, Size);
{
    UITitle(UI, "Brainroll");

    if (UIButton(UI, "Play"))
    {
        PlayUIClickSound();
        State->LevelSelectMenuOpen = true;
    }
    if (UIButton(UI, "Editor"))
    {
        PlayUIClickSound();
    }
    if (UIButton(UI, "Settings"))
    {
        PlayUIClickSound();
        State->SettingsMenuOpen = true;
    }
    if (UIButton(UI, "Quit"))
    {
        PlayUIClickSound();
        Quit = 1;
    }
}
UIPopColumn(UI);
UIPopTextColor(UI);

You can see on like 2 and 3 that I am calculating where this UI should be placed on the screen and what size it should be. For this specific case, it is not that fatal but it is still something that I do not like having to do while performing fast iterations on for example a game in this case. Thankfully in this example the buttons have their size calculated depending on the text size so they will be laid out next to eachother vertically in a column.

Last but not least the previous system had no notion at all of the keyboard navigation, it was designed like keyboard navigation wasn’t a thing and this caused me a big pain because I know how frustrating it is for a player of a 2D puzzle game that only plays with the keyboard to always have to grab the mouse because for some reason it doesn’t react to keyboard input in the menus. While performing Brainroll playtests this has been a feature that almost everyone has asked about.

Before moving on I still want to touch on some of the good parts of the system. In the above code example, you can see the pattern of Push and Pop being used to almost push a text color and also for the Column. This is a concept that I use in many places of Maraton, I was introduced to this concept by the name of “Push buffer”. The idea here is that we have a set of internal stacks for different things such as colors, fonts, and positions that will modify all widgets until we pop them off the stack. Since it is a stack and if we push several things onto it, the system will then always peek at the stack and use the last thing pushed onto it when creating its elements. This is an idea that works very well and was transferred over to the new UI implementation.

Another very positive thing with the old system was that it had what I call a “backdoor” for things that I knew I never would implement as a standard widget, this was a way for you to through function pointers define your widgets, and this allowed you to create two callback functions one for what happens during an update and one to specify what happens during rendering of the widget. This was powerful enough for the cases where I needed to implement something new and wanted it to somewhat interface with the rest of the UI system.

Harder, Better, Faster, Stronger

I was sitting in a dark room hacking away in the night, in the middle of a short sprint developing a new renderer for Maraton in preparation for supporting multiple renderer backends. While taking a small break from reading discord messages I see something that catches my eye. Ryan Fleury who is a very talented developer that has inspired me multiple times and helped solve many issues and give plenty of good ideas applied to Maraton, released a new article on his substack explaining his new UI system and while reading it I got more and more captivated by it. Within this article Ryan explains the UI system solving all of my issues and I decided to scope-creep my current sprint and implement this in the engine before continuing work on my game Brainroll. I will not go into too much detail about the internals of this system and instead refer all the traffic to Ryan's site but I will however explain the parts of the system that solve my previously mentioned constraints.

Flexible components & developer freedom

Instead of tagged unions, Ryan disconnects every widget from the idea of having a type and instead into adopting a set of properties. For example, a button can have the following properties:

Background
Text
Clickable
Hover Animation
Click Animation

Instead of building this as a button widget, we build an abstract widget type that can have all of these properties toggled on or off. I never thought about this myself but when laid out in front of me this is a very flexible and strong approach to managing the building blocks of the interface as once one property is added it can be used by any component. Representing this in code is very simple, instead of using the enum type inside your widget you use an integer type and define your enum as a set of bitflags allowing you to toggle any flag on or off. For example:

typedef u32 ui_widgetflags;
enum
{
    UI_WidgetFlag_Background     = (1<<0),
    UI_WidgetFlag_Text           = (1<<1),
    UI_WidgetFlag_Clickable      = (1<<2),
    UI_WidgetFlag_HoverAnimation = (1<<3),
    UI_WidgetFlag_ClickAnimation = (1<<4),
};

struct ui_widget
{
  ui_widgetflags Flags;
};

The different flags don’t have to apply to every process step of the widget’s lifetime but instead, it can only be managed where it matters, for the button example above the flags UI_WidgetFlag_Background & UI_WidgetFlag_Text will only be toched by the rendering code while the UI_WidgetFlag_HoverAnimation may be touched both by the code performing the animation and the rendering code. So every process step that the widget goes through can look at what flags the widget has activated and decide whether to perform part of the processing or not depending on its flags.

This type of system also streamlines the code that manages the user input because every widget can just be treated the same, it doesn’t matter if it's a button or a slider we still record if it was clicked or not as well as where it was clicked. This becomes very dynamic because the core UI system will technically support almost any widget you want and you can accompany the core itself with a library of basic widgets.

Looking back at our first constraint, this is no longer an issue because with this system nothing is preventing you as a developer from defining any component with any behavior. You can also fairly easy with this system combine several widgets almost like legos to build new widgets in your system. As mentioned earlier for a more in-depth look at how this is done I will refer to Ryan’s articles.

Ease of use

I mentioned earlier that I felt like I was missing a system that aids me with layouting because it would save me tons of time when going through iterations on a codebase. The system Ryan came up with also takes care of this for you. Remember earlier when I mentioned that most immediate mode systems re-build the entire UI every frame? What this system does is that while building a hierarchy of widgets it also caches their state as long as they are in use. The reason behind this is that when for example you are pushing a button into the current scene since the system is immediate you are only working with a partial scene and some assumptions that we make at this stage may change because we do not have access to the complete hierarchy at this point.

If we, however, separate the building of the hierarchy and rendering step we are free to inject an autolayouting step in between which allows us to work with the entire hierarchy and allows us to make advanced layouting decisions as a result.

The way this is achieved in this system is that the underlying data structure is constructed as an n-ary tree. Each widget has a parent, siblings, and children that can form a sort of hierarchy structure internally. If you google n-ary trees most examples do not keep references to siblings, an example I drew on paper may look like this:

In code this can be written like:

struct ui_widget
{
    // tree links
    ui_widget *First;  // First Child
    ui_widget *Last;   // Last Child
    ui_widget *Next;   // Next Sibling
    ui_widget *Prev;   // Previous Sibling
    ui_widget *Parent; // Parent

    ...
};

So our widgets are cached in-between frames like it would in a “retained-mode” design we still utilize the features of an immediate mode API. Since at the time we perform layouting we have access to the entire hierarchy we can perform quite advanced layouting and can be just as sophisticated as any algorithm applied to a retained-mode hierarchy.

The layouting itself is boiled down into something that we refer to as “Semantic sizes”. This is a way for us to assign each widget a way how it should be managed by the autolayouting system. In my implementation I have the following semantic sizes:

Pixels - A “hard” set size specified in pixels
TextContent - Size is set to be the text of the widget in the used font’s size.
PercentOfParent - The widget is a specified percent of the parent’s size.
ChildrenSum - The widget’s size is a sum of the size of its children.
BiggestChild - The size is set to be the same size as the biggest child widget.

Each semantic size has one of the types above as well as a value and a strictness. The value is not always used but for example, for pixels, it would be the pixel amount and the percent for the PercentOfParent. The strictness is the interesting part, it is a way for us to predetermine how much of the widget’s size in percent it is willing to give up in case it doesn’t fit within the layout.

Each widget adopts two semantic sizes, one for each axis. This is extremely powerful because it allows us to make advanced decisions where the layouts can differ on X and Y, for example, we can have a container that is hard set to 250 pixels in height but it will always be 50% in width.

The autolayouting algorithm itself traverses our tree of widgets once per axis in 5 different steps:

Calculate standalone sizes. Theese are the widgets with semantic sizes that are not dependant on any other widgets in the hierarchy(Pixels & TextContent). This can be done in either post or pre-order traversal of the tree.
Calculate the “upwards-dependent” sizes. This are the widgets with semantic sizes that depends on their parent (PercentOfParent). This should be done in pre-order traversal.
Calculate the “downwards-dependent” sizes. This is the widgets whos semantic size depends on their children (ChildrenSum & BiggestChild).
Solve size violations. At this step we traverse the entire hierarchy and verify that no widgets extends past their parent’s boundaries. Exceptions are made for parents that do allow overflow (usefull for cases where you want to implement scrolling). In case of a violation it will cut off part of the child’s size depending on the strictness defined within it’s semantic size. This should be done as a pre-order traversal step.
Compute the final screen coordinates and the relative positions between every widget. This step produces the rectangle that will be used for rendering and user input. This should be done in pre-order traversal.

This covers most cases while also being very simple to extend. As a user of this API, it will save me a lot of time as I do not have to worry about the placement of individual elements as the auto layout together with the specified semantic sizes can be utilized to take care of the thinking for me.

Another very important thing is that this type of implementation makes keyboard input quite trivial. I solved this by building a quadtree of directional links during the layouting step, this allows me to based on each widget’s position within the tree build another tree with the default behavior of which widget you would be taken to on directional key navigation. The way this is done is by looking at the spatial distance between the widgets on the screen in all 4 directions and selecting the closest widget (that allows user interaction) and then building up a tree of links to widgets in the real hierarchy. This also allows the user to set their shortcuts to different parts of the UI.

This solves the remaining constraints we had on this UI system. And the resulting system is a system that:

Allows the developer to utilize a more granular type of building blocks that allow them to define a wide variety of UI components by thinking of properties instead of hard specified components.
The system is designed with ease of use in mind. The API is small and consistent and everything follows the same push / pop pattern. As the system is still utilizing stacks internally it is trivial for new users to get a grasp of the basics and modify and style parts of the UI with limited knowledge.
Compared to the old system this approach doesn’t get in my way as much as I can worry about the content and postpone the exact layout as the algorithm will take care of it for me. I do not have to worry about new widget properties as everything I have now is for sure enough to complete my next game and as a bonus the navigation is solved and requries zero developer maintenance to be supported.

Result

In the end I have a more robust and production ready UI system inside Maraton than before. I wouldn’t claim that this is the silver bullet that solves all my UI problems for the rest of my career but it for sure is an iteration in the right direction. Here is a sample screenshot of one of the UI examples that is shipped with the engine.

Here is a visual representation of the autolayouting algorithm at work:

While this took far too long for me to get in place I am very happy that I went on this journey because I got to learn an enourmous amount of new things. This is the work I wanted to get done before allowing others to take part of the Maraton project and it is now finished and now it is time for me to finish my game Brainroll.

If you are interested in supporting my projects, me becoming an indie game developer or just want access to my games as well as the Maraton game engine it is available to my patreons here.

You can also follow my work on theese other places:

💻GITHUB 🐦TWITTER 🙏PATREON 🗨DISCORD 📹YOUTUBE

Maraton Release v1.4.0

Oskar Mendel — Thu, 24 Nov 2022 09:33:10 +0000

It is finally time for me to step out of the shadows and make my work public for the programming enthusiasts out there. Today I have finally merged one of the biggest PRs I’ve ever made to my engine and it is now in what I consider a useable state. This post will mostly just announce the engine and I will not go into too much depth of it's internal and instead save that for a future post.

What is going on?

For the ones who have not followed me since before, welcome! This is a post that I produced in addition to my first devlog.

I am an aspiring indie game developer, for my indie games, I am developing my general-purpose game engine from scratch without any libraries. While working on my games and the engine I released it to a close set of friends and all of them gave me very positive feedback (in addition to a big bag full of bugs to fix) and mentioned that they felt very productive in it because of how easy it is to get started and make fast iterations on your project.

I always knew I sometimes wanted to release the engine but I didn’t know in what way or capacity but decided before I release it there are a couple of things I wanted to polish. This was mainly the UI system and the built-in renderer.

So what I’ve done is rewrite the renderer as well as the UI system for the engine to allow users to be more modular and not be as restrictive. The new renderer doesn’t force users to rely on it and users can use the OpenGL wrapper that comes with the project to write their things. Same with the UI system that I have prepared a more in-depth and lengthy post about.

Why not unity?

My main answer to this question is that I want to learn, I want to open the black box and not rely on any “magic” instead I want to understand every single part of how a game engine works and with this engine, I want to encourage everyone else to also not be afraid and learn it just like me.

The engine is built in a low-level language C++ but utilizes a more C-like coding style for simplicity. This makes the codebase very lightweight and built in a way where you are not limited to modifying the engine for specialized games. This can be very powerful, while this is also possible in a game engine like unreal it has a much steeper curve while in Maraton you can modify the engine very quickly once you’ve grasped the basics.

I'm sure you can talk to other developers using their custom engine and they will say the same regarding productivity. They know every single part of the engine like the back of their hands and it does show when you’re going to produce and ship something. Maraton is a great oupportunity for developers that want to use their own engine to have a good base or starting point. There is nothing wrong with using Maraton for learning or as a stepping stone to start making your own specialized engine.

Quick overview

Above is a simplified diagram of the different submodules available in this initial release. I didn’t make it very fine-grained to keep it simple. In most cases, the APIs that you will consume is for the UI, Renderer, Debug, and Audio. The way these modules are documented is in their respective header files where forward declarations have been placed. I hope that for now, the function signatures will be enough to get a grasp of what the functions do but knowing that sometimes it is not enough I have also prepared a set of examples. I am also in the process of preparing some tutorials for working in the engine as well.

The examples itself is a list of example projects that links to source files that show in code how to produce what is shown in the screenshots. This is something I am going to build over time, my hope is also for other users to engage with the community and share their examples.

If you are uncertain of what you can produce with this engine I have examples published on youtube for two games built in the engine.

While this may seem simple I am also producing a full game called Brainroll using this engine that will be complete so the possibilities are not limiting instead very open for tinkerers to build what they want.

Moving forward I will have a different format of the release posts that is more focused on the changelogs. Full set of changes for the earlier versions also ship with each release of the engine.

Closing notes

My goal with this release and moving forwards is to build a community of like-minded people interested in developing games. I have created this engine as a base for people wanting to get into development and also created a discord server where I encourage people to post their questions and help each other learn and become better at what we do.

Moving forward I will also post new devlogs not only for the engine but also for my indie game. On my website, I will also produce more posts explaining the engine and valuable information on how to build interesting things.

If you are interested in supporting my projects, me becoming an indie game developer or just want access to my games as well as the Maraton game engine it is available to my patreons here.

You can also follow my work on theese other places:

💻GITHUB 🐦TWITTER 🙏PATREON 🗨DISCORD 📹YOUTUBE

Mathematics And Physics Part 2

Oskar Mendel — Mon, 07 Nov 2022 16:59:10 +0000

After learning more about numbers it is time to investigate the most elementary part of mathematics, arithmetic. Arithmetic consists of the study of the more fundamental properties of numbers as well as how they work under the operations of addition, subtraction, multiplication, and division but it's not limited to those. Since I and hopefully everyone reading this already know all the basic mathematical operations on integers we are going to divide our integers into fractions to view them in a new light that can show us a new way of working with numbers.

While I restrain myself from calling any of these operations basic they are on the easier side of math to get the hang of. As a developer, I would say you really would need to have a good grasp of what we will go through in this post as it acts as a very powerful toolkit for us developers when developing software which we will quickly notice as we get our hands dirty.

Fractions

While we did go through fractions in the previous post it is often something that not I get stuck on or have forgotten the details of over the years. Starting things off we will examine them in greater detail.

A fraction is interesting, it is like an instruction telling you to divide $a$ and $b$ like so: $ab\frac{a}{b}$ .

Multiplication of fractions

To multiply two fractions, all you have to do is to multiply the numerators followed by multiplying the denominators: $35∗37=3∗35∗7=935\frac{3}{5}*\frac{3}{7}=\frac{3*3}{5*7} = \frac{9}{35}$

When multiplying with an integer remember that any integer is a fraction with the denominator of 1 meaning that for example $\frac{5}{1}$ this means that when you’re multiplying a fraction with an integer you can simply just multiply the integer with the numerator and leave the denominator alone.

A common way of visualizing this is to draw rectangles for each of the two fractions, one as rows and one as columns.

How this works is that you first draw your two fractions, one as rows and one as columns, I have highlighted $23\frac{2}{3}$ columns in one and $34\frac{3}{4}$ rows in the other. Then what happens is that I’ve drawn a third rectangle where I highlighted the overlapping boxes in black, those are our numerator while our denominator will be the total number of boxes.

Division of fractions

If we take the example of dividing $57\frac{5}{7}$ with $28\frac{2}{8}$ you first want to flip $28\frac{2}{8}$ so that it becomes $82\frac{8}{2}$ then simply perform multiplication on them like so: $57÷28=57∗82=4014\frac{5}{7} \div \frac{2}{8} = \frac{5}{7} * \frac{8}{2} = \frac{40}{14}$

You can use the same on-paper method displayed above by flipping the values of the second fraction first.

This may seem weird at first but there is a logical explanation for it. If you first think of dividing an integer by 2. You are taking half of the number, which is the same as multiplying the integer with $12\frac{1}{2}$ .

If you then attack if from the other side and think of dividing a number by $12\frac{1}{2}$ , what you are doing is finding out how many halves that go into that number. Since the number of 1s in a number is the same as the number itself it means dividing a number by $12\frac{1}{2}$ (finding out how many times 0.5 fits in the number) means you’re multiplying it by 2.

Addition and subtraction of fractions

Both addition and subtraction are not as simple as division and multiplication. As long as you have the same denominator you are free to both subtract and add to the fractions as you please, you just leave the denominator alone and perform normal addition or subtraction on the numerator.

However, if you are dealing with fractions of different denominators you will stumble into problems because the units you are trying to add or subtract are different.

The interesting part is that every fraction can be represented in an infinite number of ways so if you multiply the numerator and denominator by any number you are still left with the same fraction. This works because every number divided by itself is 1.

For example both $22\frac{2}{2}$ and $55\frac{5}{5}$ is equal to 1. With this knowledge, let’s say that you want to calculate $14+58\frac{1}{4} + \frac{5}{8}$ here it’s much easier if you recognize that $14=28\frac{1}{4} = \frac{2}{8}$ simply by multiplying both the numerator and denominator by 2. Now suddenly all you’re left with is a simple addition to turn it into $28+58=78\frac{2}{8} + \frac{5}{8} = \frac{7}{8}$ . This technique works even though the two fractions are not as easily converted between each other, for example, $13+37\frac{1}{3} + \frac{3}{7}$ . Here you can utilize something known as cross-multiplication where you are multiplying the numerator and denominator of each fraction by the denominator of the opposite fraction. For example:

$13+37=1∗73∗7+3∗37∗3=721+921=1621\frac{1}{3} + \frac{3}{7} = \frac{1*7}{3*7} + \frac{3* 3}{7*3} = \frac{7}{21} + \frac{9}{21} = \frac{16}{21}$

Why this works should make sense by now, we are making the two fractions have a common denominator. A problem when doing this however is that you often end up with a larger fraction than you want. A way of solving this is by looking deeper into factors.

Factors

To solve the problem of our fractions becoming too big we need to reduce the numbers into their smallest forms and this can be done by looking at the factors of the numbers. A factor is simply an integer that can exactly be divided into another target integer. For example, 1, 2, 4, and 8 are all factors of the number 8.

If we move back a bit and consider the fraction of $612\frac{6}{12}$ you may see that both numbers may be divided by 2 to arrive at $36\frac{3}{6}$ and here we can divide it by 3 to get $12\frac{1}{2}$ . Or we can skip the extra steps and recognize that $612\frac{6}{12}$ can be divided by 6 directly. Skipping the extra steps can be done by finding the greatest common divisor also known as GCD that will allow you to find the value to divide the numerator and denominator with in order to reduce the fraction to its smallest form*.*

Greatest common divisor

Finding the GCD can be done in multiple ways, while there are simple ways to find it it was earlier common to find them using the prime factors of two numbers. This is not the optimal approach but it allows us to also touch on the subject of prime numbers hence we will first describe this approach. A prime number is simply a number whose only factors are 1 and itself. This means that the number can only be evenly divided by either 1 or itself, examples are 2, 3, 5, 7, … and so on. Prime numbers are a very deeply studied subject, they are a key subject in for example cryptography.

There are several algorithms to generate a list of prime numbers, a very common one is called “Eratosthenes ‘Sieve” which allows you to generate a list of prime numbers less than some number $N$. To perform this you perform these steps:

Start with a list of all the numbers in the range of 2 to $N$.
Take the first number of the list and delete all the numbers in the list that are divisible by this number.
Remove the same number from the list and add it to the list of primes.
Repeat this process until the first number of the list is greater than $N\sqrt{N}$ .
All the remaining numbers are primes.

Step four of this process works because if any of the products are greater than $N\sqrt{N}$ then the final product will become greater than $N$ . An implementation in C may look something like this:

void 
sieve(int *Numbers, int N)
{
    int MaxN = floor(sqrt(N));
    for (int I = 0; I < MaxN; ++I)
    {
        if (Numbers[I] != -1)
        {
            for (int J = 2 * Numbers[I] - 2; J < N; J += Numbers[I])
            {
                Numbers[J] = -1;
            }
        }
    }
}

If we were to return to the subject of prime factors. A prime factor of a number is as you now might figure out, a prime number that is a factor of $N$ . A very interesting property is that every number can be represented as a product of prime numbers, for example, $12 = 2 * 2 * 3$ . This is also known as “The Fundamental Theorem of Arithmetic”.

If we are to use these prime factors as a way of getting the GCD of a number we can do so by finding the primes that produce the number we are interested in and using those to divide the numerator and denominator of your fraction. However, this might be very tedious as you would have to identify common primes for both to produce the GCD. For example lets take the number $1624\frac{16}{24}$ first we would have to identify that $16 = 2 * 2 * 2 * 2$ and $24 = 2 * 2 * 2 * 3$ we have $2 * 2 * 2$ in common hence our GCD in this case is $8$ and we can reduce the fraction to $16/824/8=23\frac{16/8}{24/8} = \frac{2}{3}$ .

There is a better way that also is much faster and does not involve primes. This method is known as “Euclid’s Algorithm”. Euclid’s algorithm is very interesting as it relies on the observation that if you have three numbers $A$ , $B$ and $C$ such that $A = B + C$ and if some number $n$ is a factor of both $A$ and $B$ , it must be a factor of $C$ as well.

This allows us to construct a different function for getting the $GC D (n, m)$ by performing this simple number of steps:

Divide $n$ by $m$ and get the remainder $r$ .
You now know that $n = a * m + r$ for some number $a$ .
If $r = 0$ then $m$ is a factor of $n$ so the result is $m$ . Otherwise, repeat the process using the numbers $m$ and $r$ .

This can very trivially be implemented in C like so:

int gcd(int n, int m) {
    int r = n % m;

    if (r == 0) {
        return m;
    }

    return gcd(m, r);
}

The Modulo operator

In this example, we are using the modulo operator which allows us to get the remainder of a division. Modulo is a very important tool in your toolbox and we will soon investigate some very useful cases where it can make our lives easier. But first let's briefly talk about how it works.

In very simple terms it is just the remainder of a division, in practice what these means are if we are dividing numbers that are not evenly divided, part of the divided number is discarded as we are working with integers. For me this was most obviously explained by presenting it like this:

5 % 1 = 0 // 5 / 1 = 5. Remainder is 0.
5 % 2 = 1 // 5 / 2 = 2. Remainder is 1.
5 % 3 = 2 // 5 / 3 = 2. Remainder is 2.
5 % 4 = 1 // 5 / 4 = 1. Remainder is 1.
5 % 5 = 0 // 5 / 5 = 1. Remainder is 0.

I hope you can spot the pattern here. Something that I found very interesting when I first understood this was that the result from the modulo operation on the same number almost works in a circular fashion where we can see the number looping around in a way.

Check if number is even or odd

One of the most basic usages for the modulo operator in a programmer's daily life is to perform checks on whether a number is even or odd. This can trivially be done for any number $N$ by $\bmod 2$ . What happens here is that it will always return either 1 or 0. Even numbers because they are always divisible by 2 will return 0 while odd numbers will always have the remainder of 1. If we were to create a simple C function of this it would look like this:

int 
IsEven(int n)
{
    return (n % 2 == 0);
}

Cycling through data

Sometimes you only have a fixed number of options or things you want to loop through, this is also a perfect use case for modulo. Let's say we want to organize which plant is going to be watered on which weekday.

char *Weekdays[] = { "Monday", "Tuesday", "Wednesday", "Thursday", "Friday" };
int NumberOfDays = 5;
int NumberOfPlats = 10;

for (int I = 0; I  < NumberOfPlants; ++I)
{
  int DayIndex = I % NumberOfDays;
  char *Weekday = Weekdays[DayIndex];

  printf("Plant #%d should be watered on %s", I, Weekday);
}

Proportions

Something else about fractions that we should consider is looking at the numerator and denominator as a ratio. A proportion by itself is almost the same thing as a fraction but used in very different circumstances. We usually write rations using a colon such as a ratio 4:3 which is equivalent to $43\frac{4}{3}$ . Two things are in the ratio of 4:3 if one of the two is $43\frac{4}{3}$ times bigger than the other.

In the real world, we can easily see this on paper for example the standard A4 size remains the same proportion if you scale it to double of its size. This is something that we have already covered in this post because scaling up like that is the same as multiplying the numerator and denominator by the same number as the fraction itself remains unchanged.

In game development which I am currently invested in this can be useful when scaling things, for example, if you were to find the new height of an object after its width have been changed:

int
NewHeight(int OriginalWidth, int OriginalHeight, int NewWidth)
{
  return (NewWidth * OriginalHeight / OriginalWidth);
}

This type of math allows you to simply map between different sizes of rectangles. And does not only have to be the size proportions but also the coordinates of objects for example. In games this is common when scaling for different resolutions, in fact all monitor resolutions have their own aspect ratios which works in the same way where for example 1920x1440, 1600x1200 and 1440x1080 are all 4:3 aspect ratios.

When talking about rations there are interesting things such as the golden ratio and the Fibonacci sequence that can be interesting to dive into but I will not talk about them in this post.

Something I recently stumbled upon without specifically studying math was when I was working on my UI system for my game engine and was building the slider and scrolling logic. A slider in a user interface is a graphical representation of a range of numbers. On your PC you have a volume slider for controlling the volume or a slider for controlling the brightness of your monitor.

These standard sliders often represent a value between 0 and 100 but are not restricted to. For you to create your slider you first need to know the bounds (the number at the start and the end of the line). When building the user interface system I also have to know the positions of these. You can find the proportion of the slider by finding the size of the total range divided by the total length of the slider itself: $\frac{maxVal - minVal}{endPoint - startPoint}$

To then get the value represented by a specific point on the slider you can find how far the value has been moved along the slider by multiplying it with the proportion we got from the previous calculation: $Va l u e = (p o in t - s t a r tP o in t) * p ro p or t i o n + minVa l$

In my game engine the real calculation looks something like:

(\frac{(point - startPos)}{ SliderWidth}) + minVal

This is very similar to the previous calculation except I do not need the specific proportion to retrieve my value as I normalize it hence I get away with just the range between the min and max value.

For me, this post has been pretty valuable because I got to touch fractions in a completely different way than what I was taught in school. I can see how some problems may be clearer to see if you look at them as fractions instead of whole numbers. Since I wanted to make a series on math from start to finish I do understand that these first posts may seem a bit unorganized and abstract but this will change once we move into algebra in the next post.

If you are interested and want to hear more from me, subscribe to my email list.

You can also follow my work on theese other places:
💻GITHUB 🐦TWITTER 🙏PATREON 🗨 DISCORD 📹 YOUTUBE

How to hack a .NET Core game

Oskar Mendel — Tue, 16 Aug 2022 16:08:01 +0000

During my vacation, I spent some time with an MMORPG that I had not played before. I was enjoying playing the game but when I had to get back to work I realized that I won't have time to play this game If I also want to make progress on my stuff like my game engine and my game.

The idea in my head was “What if I could write a program to make the gameplay itself?”. I played around a bit with this idea and like with many pictures like this it piqued my interest just enough for me to investigate what that kind of program would look like as well as if I have the skills to pull it off, so I rolled up my sleeves and got to work.

Disclaimer: In this post I will not explain how to hack any specific application or game, I will just mention some of the approaches that people who make cheats and bots use so that we can learn about them. No game was harmed in the process of making this.

Disclaimer: I do not promise that this is 100% bulletproof and works for everything. I am sure there are countermeasures to this that would require you to be even more clever. I have however not investigated how to protect yourself from this and will save that for another article. So if you care about this then consider the title a clickbait.

With that said let’s get into what I came up with!

Background

Some background information before starting this. Before doing this small project I had no previous experience with hacking or reverse engineering anything so what I did was just blindly test different stuff that I learned along the way.

The target game I had in mind was built using .NET Core using FNA and was an open-source game. The reason I mention this is because many of the things I tried just simply won't work because of the technology the game was built with which we will get more into.

Another thing before we start that perhaps is good to know is that there are two common approaches to design your hack that I am aware of, it can either be external or internal where external hints at a standalone application using the platform APIs to manipulate another process on the machine where internal injects itself into the process and attacks it from within.

This article will go through the steps I went through to investigate and eventually land on a solution. I will not go overly in-depth into any of the techniques, if something specific needs to be clarified however just tell me and I will try to answer to the best of my knowledge.

Attempt 1: Memory hacking

So the first thing I tried which I also knew about before because it is not only used for reverse engineering was to manipulate the game’s memory. If you have ever been curious about cheats and perhaps googled around a bit I’m sure many of you know a program called “Cheat Engine”.

Many people are under the impression that this is a tool for people who want to make cheats but don’t know how or just want to create small scripts. This is not true, Cheat Engine is a very valuable tool used for memory scanning and debugging. It is capable of scanning the memory of running processes on your computer as well as debugging the disassembled source code of the executable of your choice.

The most simple way to manipulate a game using this piece of software is to open your target process within Cheat Engine followed by searching for a known value within the application. A common example is if you currently have 100 health within your game you would scan for the value 100 within Cheat Engine, this would bring up thousands upon thousands of results of every address in memory that contains the value 100. To narrow it down Cheat Engine allows you to create a new scan for each variable that changed, so for example if you take some damage within the game and now have 70 health you would perform a new scan for all values that were 100 but are now 70.

This is a process you do over and over again until you have a manageable amount of addresses left. What you then can do is to select the addresses and manipulate them, for example manually changing the value to 200, if you found the correct health variable within your game your health would now be 200 because you set that address in memory to that value.

Let us say that you managed to find the correct address and change it to 200. Well, now you’ve manipulated and “hacked” the game. But what happens if you restart the game? There is no guarantee that they will get the same address in memory upon restart. This is where another technique called pointer scanning comes into play.

Cheat Engine comes with a feature that allows you to save all pointers into what is called a pointer map, this is a file with a snapshot of the game’s memory at that specific given time.

You can then scan that pointer map for a specific pointer and compare it between different runs of the game. What this essentially allows you to do is to find static offsets within the memory where things will always be located at.

I will not go into the details on how to perform this but in the end, you will find a pointer that looks something like this within the user interface of Cheat Engine:

So this is a chain of pointers that ends up with a value of 1000 within the loaded application. The interesting part that the pointer scan can do for us is that it scanned through a chain of addresses that ends up giving us our desired value. With this available, we have a static offset inside our target program that will persist between runs and we can write a program to change this value for us so that we can change our health value whenever we want.

How to access memory addresses through code

So how we make use of this information we found in Cheat Engine is quite simple. All we have to do is to get the base address for the application we are targetting, in the example image above this is the address for the “cheatengine-x86_64-SSE4-AVX2.exe” string that is used because I opened the Cheat Engine process for this example.

So to find this address we can use the Windows API which has a handy function ready for us called CreateToolhelp32Snapshot which gives us a snapshot of a target process which includes its heaps, modules, and threads.

We can use this function to get the process id (PID) for our target process as well as all the modules within a given process. With this information, we can simply iterate over all the modules and once we find a module we care about take that module’s address and use that as a base address.

The PID can then be used with the function OpenProcess which gives us an open handle to the specified process. This allows us to use the functions ReadProcessMemory as well as WriteProcessMemory. The two functions mentioned last allow us to Read and Write to a process's internal memory which allows us to manipulate the memory of the process.

#include <Windows.h>
#include <TlHelp32.h>

DWORD GetProcessId(const wchar_t ProcessName)
{
    DWORD ProcessId = 0;
    HANDLE SnapshotHandle = CreateToolhelp32Snapshot(TH32CS_SNAPMODULE | TH32CS_SNAPMODULE32, ProcessId);
    if (Snapshothandle != INVALID_HANDLE_VALUE)
    {
        PROCESSENTRY32 ProcessEntry = { 0 };
        ProcessEntry .dwSize = sizeof(ProcessEntry);
        if (Process32First(Snapshothandle, &ProcessEntry))
        {
            do
            {
                if (!_wcsicmp(ModuleEntry.szModule, ProcessEntry))
                {
                    ProcessId = ProcessEntry.th32ProcessID;
                    break;
                }
            } while (Process32Next(Snapshothandle, &ProcessEntry));
        }
    }
    CloseHandle(Snapshothandle);
    return ProcessId ;
}

uintptr_t GetModuleBaseAddress(DWORD ProcessId, const wchar_t ModuleName)
{
    uintptr_t ModuleBaseAddress = 0;
    HANDLE SnapshotHandle = CreateToolhelp32Snapshot(TH32CS_SNAPMODULE | TH32CS_SNAPMODULE32, ProcessId);
    if (Snapshothandle != INVALID_HANDLE_VALUE)
    {
        MODULEENTRY32 ModuleEntry = { 0 };
        ModuleEntry.dwSize = sizeof(ModuleEntry);
        if (Module32First(Snapshothandle, &ModuleEntry))
        {
            do
            {
                if (!_wcsicmp(ModuleEntry.szModule, ModuleName))
                {
                    ModuleBaseAddress = (uintptr_t)ModuleEntry.modBaseAddr;
                    break;
                }
            } while (Module32Next(Snapshothandle, &ModuleEntry));
        }
    }
    CloseHandle(Snapshothandle);
    return ModuleBaseAddress;
}

int main()
{
    DWORD ProcessId = GetProcessId(L"MyGame.exe");
    uintptr_t ModuleBaseAddress = GetModuleBaseAddress(ProcessId, L"MyGame.exe");

    HANDLE ProcessHandle = 0;
    ProcesHandle = OpenProcess(PROCESS_ALL_ACCESS, NULL, ProcessId);

    uintptr_t PointerBaseAddress = ModuleBaseAddress + 0x00E036B0;

    uintptr_t TargetAddress = 0;
    int Offsets[] = { 0x148, 0xA8, 0x88, 0x48, 0x8, 0x58, 0x0 };
    int NumberOfOffsets = 7;

    for(int Index = 0; Index < NumberOfOffsets; ++Index)
    {
        ReadProcessMemory(ProcessHandle, (BYTE *)TargetAddress, &TargetAddress, sizeof(TargetAddress), 0);
        TargetAddress += Offsets[Index];
    }

    // TargetAddress now contains the address!

    int NewHealthValue = 5000;
    WriteProcessMemory(ProcessHandle, (BYTE *)TargetAddress, &NewHealthValue, sizeof(NewHealthValue), 0);

    return 0;
}

Why attempt #1 doesn’t work for .NET Core

Unfortunately, even though it takes a lot of work to even get this far this method of reverse engineering does not work for a .NET Core process.

The reason is that the .NET compiler produces code that can run on the CLR (Common Language Runtime) which handles the stuff for you like garbage collection, runtime type checking, and reference checking.

Unlike languages like C/C++ which produces machine code that is not managed hence nothing is done for you in a sense.

So in practice, this means that even if we do this type of scanning we won’t get static offsets within the executable because the code that is executed is not part of it in a sense and is prone to change when the CLR performs just in time compilation for example.

So if you were to try this, most of the addresses you would find wouldn’t even be inside your executable but inside the coreclr.dll which will have different pointer offsets each time.

So, back to the drawing board.

Attempt 2: Signature Scanning

The next thing I investigated was if I were to do signature scanning on the application’s code to find a sequence of bytes that I have previously identified to mean something I know.

In the end, this will give the same result as attempt 1 but we use a different method to arrive at the final address. Instead of scanning for data itself, we are scanning for the code. At this point, I didn’t think too much that this will result in the same problems as attempt 1.

So Cheat Engine also contains a memory view that allows you to see the code part of the process, it can look something like this:

This view also allows you to set breakpoints and step around the application while it's running. I used this to find the method for GetPlayer in the application I used. This requires you to understand some assembly as well as experiment a lot.

Once you find something interesting you can use the sequence of bytes in the second column of the image in as that code’s signature. There are many tools developed for Cheat Engine to help you with this. The tool I used allowed me to right-click an address and export a signature for it. That kind of signature looks something like this: 48 8d 64 24 ? 48 8b 45 ? 48 8d 4d.

Something weird you may notice is that there are question marks within the generated sequence, these are wildcards that exist because while the address may be moved around in memory the actual code will stay the same hence we use wildcards to aid us with finding these offsets even though the address space is updated between runs.

Some implementations use Masks to help with parsing the string which means to accompany the pattern above with a string like xxxx?xxx?xxx .

So an example of how this would look within code would be very similar to the first implementation.

Important when doing this is that you only scan parts of memory that matter. What this means is that we can use the function VirtualQuery which will retrieve memory information of that memory region only yielding valid memory regions which will save us time.

Here it depends a bit if you are writing internal or external code, the example above was an external application that will modify the memory of the target application externally but below we are utilizing an internal application that is injected into the target as a DLL. The reason for this is that when utilizing DLL injection we are becoming a part of the target process meaning that we have access to its memory from within itself.

char* _Scan(char* Pattern, char* Mask, char* Begin, intptr_t Size)
{
    intptr_t PatternLength = strlen(Mask);

    for (int I = 0; I < Size; I++)
    {
        bool Found = true;
        for (int J = 0; J < PatternLength; J++)
        {
            if (Mask[J] != '?' && Pattern[J] != *(char*)((intptr_t)Begin + I + J))
            {
                Found = false;
                break;
            }
        }
        if (Found)
        {
            return (Begin + I);
        }
    }
    return 0;
}

char *Scan(char *Pattern, char *Mask, char *Begin, intptr_t Size)
{
    char *Match { 0 };
    MEMORY_BASIC_INFORMATION MBI = { 0 };

    for (char *Current = Begin; Current < Begin + Size; Current += MBI.RegionSize)
    {
        if (!VirtualQuery(Current, &MBI, sizeof(MBI)) || MBI.State != MEM_COMMIT || MBI.Protect == PAGE_NOACCESS) continue;
        Match = _Scan(Pattern, Mark, Current, MBI.RegionSize);

        if (Match != 0)
        {
            break;
        }
    }

    return Match;
}

Why attempt #2 doesn’t work for .NET Core

In addition to what’s mentioned about why attempt 1 didn’t work is that .NET running its applications on the CLR is that it doesn’t produce machine code. Instead, it produces a special type of bytecode known to the CLR called Intermediate Langue (IL). This is later run within the CLR which takes this IL code and translates it into native instructions that the CPU can understand, this process is known as Just In Time (JIT) Compilation.

This is just as it sounds, a compiler that takes the code and compiles it to machine code as it is executed the first time. There is, of course, more to this if you were to dig down deeper into the CLR but for our purposes, this means that our signatures may not look the same each run as they are compiled on the fly. This can produce insanely long signatures (it did in my case) which takes a long time to look for.

For example the main one I wanted to work on looked like this:

ff 15 ? ? ? ? 48 8b 80 ? ? ? ? 48 83 c4 ? c3 cc cc cc cc cc cc cc cc cc cc 56 48 83 ec ? 48 8b f1 ff 15 ? ? ? ? 48 8d 88 ? ? ? ? 48 8b d6 ff 15 ? ? ? ? 90 48 83 c4 ? 5e c3 cc cc cc cc cc cc cc cc cc cc cc 48 83 ec ? ff 15 ? ? ? ? 48 8b 80 ? ? ? ? 48 83 c4 ? c3 cc cc cc cc cc cc cc cc cc cc 48 83 ec

And unfortunately it wasn’t consistent between runs.

Attempt 3: CLR Hosting

At this point, I had spent a lot of hours investigating the subject and getting real frustrated as nothing I was throwing at the game worked. I started reading up about a concept called function hooking which is used to change the game’s instructions to make it call your function before or after executing the normal code or simply ignore the original altogether and just execute your code.

At this point I understood that I can’t manipulate the game’s memory through static memory offsets, I had to change my strategy a bit. I stumbled upon a concept called CLR Hosting.

What this technique means is that you boot up a CLR instance to get into a managed application space and execute your code there. If you were to do this from inside a DLL injected into an application this means that your code will now run alongside the already managed application and you will have access to everything like you would in a normal C# application.

My hypothesis here was that if I can execute managed code from here I would be able to use reflection in C# to modify the code in the target application. The question is how do you do this?

The irony in it all was that all along Microsoft already had a code sample available for how you would do this available among their interop tests.

The code is very simple and all it does is find the handle to the coreclr.dll which is the module that is running our code then get its CLR Host and execute the target function inside the target dll using the method ExecuteInDefaultAppDomain because we are a DLL injected into the target process the same and main AppDomain as the rest of the code that we’ve been wanting to manipulate.

HMODULE CoreCLRModule;
CoreCLRModule = GetModuleHandleA("coreclr.dll");
if (!CoreCLRModule)
{
    printf("ERROR - CoreCLR.dll could not be found");
    return -1;
}

ICLRRuntimeHost2* RuntimeHost;
FnGetCLRRuntimeHost PFNGetCLRRuntimeHost =
    (FnGetCLRRuntimeHost)::GetProcAddress(CoreCLRModule, "GetCLRRuntimeHost");

if (!PFNGetCLRRuntimeHost)
{
    printf("ERROR - GetCLRRuntimeHost not found");
    return -1;
}

HRESULT hr = PFNGetCLRRuntimeHost(IID_ICLRRuntimeHost2, (IUnknown**)&RuntimeHost);
if (FAILED(hr))
{
    printf("ERROR - Failed to get ICLRRuntimeHost2 instance");
    return -1;
}

hr = RuntimeHost->Start();
if (FAILED(hr))
{
    printf("ERROR - Failed to start the runtime");
    return -1;
}

DWORD ExitCode = -1;
hr = RuntimeHost->ExecuteInDefaultAppDomain(L"MyHack.dll", L"Namespace.Class", L"Method", L"Arguments", &ExitCode);
if (FAILED(hr))
{
    printf("Assembly execution failed!");
    return -1;
}

To combine this with reflection, there are handy tools that play heavily upon the fact that .NET is compiled into IL code and can rebuild the C# code written in a very accurate way which you can inspect to find out more information. An example of such a program is ILSpy which I show an example screenshot of below alongside Visual Studio.

Final notes and future reading

Once again I do not promote or condone cheating or hacking. I simply did this as an experiment and to learn more about it.

If you are interested in learning more about this type of stuff and perhaps want to get into it yourself I can recommend a book called “Game Hacking: Developing Autonomous Bots for Online Games” by Nick Cano. It goes more in-depth about the techniques that I mention here as well as covers more things you can do.

In addition to that, there are very good information and communities available for free on the internet if you just google.

I think this was a very fun experience and I like something that Nick Cano mention early in his book that goes something along the lines that within every game there is another game available in addition to the one in the title, the cat and mouse game of wits between game developers and hackers. I think this is a fun way to look at it, almost like there is more to a game than the features you are supposed to interact with, more content that you can explore and even make yourself. This gives me the happy thought that nothing is stopping you from using this kind of technique to patch parts of a game that you are unhappy with or you want to improve.

Mathematics And Physics Part 1

Oskar Mendel — Sat, 23 Jul 2022 12:54:48 +0000

Whether you like it or not eventually you will have to apply some mathematics in your programs. Maybe you’re writing a game and have to simulate the player moving around in the world. You may have to convert between different currencies in a financial application, sample large datasets, or simply get HTML elements to appear where you want them on your website.

While you have probably studied both maths and physics in school it is easy to forget and while learning to program it is not always obvious how a computer deals with numbers.

I have personally never been good at math or physics, most likely because I never liked it growing up. I think this was because I didn’t understand the point of it. I had nothing to apply what I learned, so I was never interested. However, as I learned more about computer science and programming I started to find areas where math could be applied, and just like programming, I found that there is a system behind mathematics and it can be not only useful but fun if you invest some time into it.

This series is going to act as a journal for when I dive into getting better at mathematics and physics as a programmer. I am going to start from the basics and also apply what I learn through programming all the way.

With that said let’s start.

Numbers

What are numbers in the eyes of a computer and what can they do for us?

Let us start with the thought that there are different types of numbers. These types are divided into several subsets where a set is a collection of elements where each element within the set must be unique.

The first set that most people are taught is the set of natural numbers which is represented by the symbol

\displaystyle \mathbb {N}

. The numbers in this set are the positive numbers starting from one (1, 2, 3, 4, 5 …). Some mathematicians include 0 in this set.

Adding the set of negative numbers gives us the set of integers that we as programmers know as an int in most programming languages. The symbol for this set is denoted as

Z\displaystyle \mathbb {Z}

Negative numbers are interesting, I learned to think about negative numbers in terms of transactions or trades. So for example, if you have 5 apples and you want to give 2 of them to Johnny it is the same as Johnny giving you -2 apples. This idea of two approaches can be extended to work for multiplication as well. If Johnny gives you -2 apples -2 times it is the opposite of him doing it 2 times so it is the opposite of -4 giving you 4.

It might take some time to let that sink in. If you don’t get it right away then you shouldn’t get discouraged because it took centuries for people to accept this.

Beyond the set of integers, there is also the set of rational numbers using the symbol $${\displaystyle \mathbb {Q} }$$ which includes the previous sets we talked about as well as the set of fractions.

Moving on we also have irrational numbers which are numbers that cannot be expressed by the quotient of two integers, a good example is the square root of 2. Rational and irrational numbers form the set of real numbers using the symbol

R\displaystyle \mathbb {R}

. These are the sets that we will focus on for now.

The symbols for the different sets are something you can forget because we most likely won't use them beyond this point. However, if you are planning some math on paper or discussing it with a mathematician it can be useful to speak the same language.

Representing numbers

When we’re talking about the number 4 for example there are different ways of representing this number. You can represent it with a geometric figure as a rectangle but you can also just draw 4 dots on paper or simply just use the symbol “4”. Different representations have their advantages and disadvantages, sometimes a problem is easier solved if you can see it visually.

Different representations of the number 4.

There is no universal symbol for each number, instead, we use a limited set of symbols that we can combine to represent any given number. This is done by using a base system, the numbers in our daily life are written in base 10 but nothing is stopping us from using any other base.

To any number N in any base B you can apply an algorithm like the following:

function NumberToBase(N, B) 
{
    ConvertedNumber = [];
    Index = 0;

    while (N != 0)
    {
        ConvertedNumber[index] = N % B;
    N = N / B;
    ++Index;
    }

   // Use the ConvertedNumber array to build a number or string
}

An actual example of a C implementation may look like:

char *NumberTable[] = 
{
    "0", // 0
    "1", // 1
    "2", // 2
    "3", // 3
    "4", // 4
    "5", // 5
    "6", // 6
    "7", // 7
    "8", // 8
    "9", // 9
    "A", // 10
    "B", // 11
    "C", // 12
    "D", // 13
    "E", // 14
    "F", // 15
};

char *
NumberToBase(int Number, int Base)
{
    char *Result = calloc(1, 1024);
    int At = 0;

    while (Number != 0)
    {
        int ConvertedNumber = Number % Base;
        Number = Number / Base;
        PrependString(Result, NumberTable[ConvertedNumber]);
    }

    return Result;
}

How these algorithm works are quite simple, if you were to enter the numbers 462 for the Number argument and 10 for the Base, the remainder when dividing Number and Base would be 2. Then by dividing the Number by 10 we get the number 62 which is used to repeat the process giving us the number 462 when done.

The same operation can be done in reverse:

int 
BaseStringToValue2(char *Digits, int Base)
{
    int StringLength = strlen(Digits); 

    if (StringLength == 0)
    {
        return 0;
    }

    int Result = 0;
    int Power = 0;
    while (StringLength != 0)
    {
        char C = Digits[StringLength - 1];
        int Number = ToNumber(C);

        Result += pow(Base, Power) * Number;

        StringLength--;
        Power++;
    }

    return Result;
}

If you feed the string “3572” and base 10 this algorithm will go through the number starting from 2 and yield

2 * 1 + 7 * 10 + 5 * 100 + 3 * 1000

There is not too much special about using 10 as a base for your numbers other than the fact that we have 10 fingers to count with. Different bases have their advantages and can be seen used in different areas, for example, computers use base 2 because of how it maps well into the transistors within the hardware. Base 12 is used when talking about feet and inches, the clock often uses base 60 and when talking about degrees we are using a base of 360.

How computers represent numbers

As we mentioned earlier, computers represent numbers in binary. This is ideal as down to the hardware the computer is built on the concept of “switches” that can be either turned on or off, this is represented as 1 or 0 respectively. Each switch represents one bit of information, the word bit here is short for “Binary digit”. With 8 bits you can represent any number from 0 to 255 while with 32 bits you can represent any number up to 4294967295 and with 64 bits you can represent numbers up to 18446744073709551615. The numbers 32 and 64-bit are something you may recognize, CPUs some years ago used to support 32-bit and you would have a 32-bit version of Windows installed while nowadays you most likely have a 64-bit CPU which means its natively working with 64-bit integers instead of 32-bit ones.

This does not mean that every single bit is used, usually, one bit is set aside to represent if the number is positive or negative. This means that a 32-bit computer would only deal with numbers from -2147483647 to 2147483647 instead of only a positive range up to 4294967295.

Binary addition works simply by adding every digit in the same column and if both are 1s you use a carry digits that cary over, example of this is when you perform addition like

1 + 1 = 10

Subtraction works almost the same but you borrow from the next column if the column contains a 0 instead of a carry like with addition, for example:

10 - 1 = 1

and

101 - 10 = 11

Arithmetic operations on binary numbers are quite trivial and are usually implemented using logical operators AND, OR, and NOT. The tables below show the different combinations of bits for the different operations.

AND

The AND operator yields 1 only if both operands are 1

A	B	Result
1	0	0
0	1	0
1	1	1
0	0	0

OR

The OR operator yields one if one or the other operand is 1.

A	B	Result
0	1	1
1	0	1
1	1	1
0	0	0

NOT

The NOT operation yields 1 if the bit is set to 0 vice versa.

Bit	Result
0	1
1	0

Floating point

At some point reading this you may have asked yourself how floating point numbers fit into all of this that we’ve talked about. If computers only know binary numbers 0 and 1 how can we represent a value that is less than 1 but not 0? To do this we do just like we do in real life, we use a marker known as the decimal point (also known as the radix point).

In base 10 the numbers after the decimal point represents tenths, hundreds. thousands and so on. In binary they represent halves, quarters and so on. Knowing this the number

1381\frac{3}{8}

is represented in binary as

(1+\frac{1}{4}+\frac{1}{8})

. While this seems sane there is a fatal problem with this and that is not all fractions can be represented this way. For example in decimal its hard to represent

13\frac{1}{3}

because it would consist of an infinite series of

310+3100+31000+...\frac{3}{10} + \frac{3}{100} + \frac{3}{1000} + ...

hence we oten just write

0.333...

In binary the situation is even worse because you cannot represent any fraction whose denominator is divisible by any number other than 2. An example of this is

15\frac{1}{5}

which in decimal equals to exactly

0.2

but in binary it ends up as an indefinitely repeating number:

0.001100110011...

Because theese types of number doesn’t have a clear definition when to stop computers have troubles with them.

There are ways around this that have been tried in the past. One way is to forget the radix point and simply represent the numbers as fractions, some programming languages have experimented with this. While every number can be represented exactly there are some problems when adding incompatible fractions resulting in increasing the complexity of the fraction with each step in a computation, easily reaching the maximum size for integers, and even if you don’t reach the maximum size the computations will be slow because of the size of the fractions.

Another problem is when you’re working with irrational numbers which cannot be expressed exactly as a fraction, instead you are forced to approximate the number. Computers use the base system to represent non-integers and round them to the nearest digit.

There may be problems with this as well but other problems can occur if for example fixed-point representations are used instead. What this means is that only a fixed amount of digits are used after the radix point.

Since you only have a limited number of bits for each number, each bit added to the right of the radix point means one bit less to use at the left. As a result, you are limiting how large and how small numbers can be. Instead what most programming languages do is allow the radix point to be moved.

Scientific notation

Similar to this moving radix point is scientific notation, a representation which uses the first significant (non-zero) digit followed with as many digits you need after that, then you specify the position of the radix. For example the number

305.57

could be represented as

30557; 3

. Using scientific notation this is commonly represented as

3.0557 e^2

. If you follow the convention you start with the radix after the first digit and then go on from there,

e^2

in this case is the exponent of the number.

IEEE Standard

IEEE which stands for the Institute of Electrical and Electronic Engineers, is an organization that has created many standards which are commonly used by computer manafacturers and software developers. Theese standards are important for creating a common ground between different hardware, programming languages and systems.

An IEEE standard was established for using floating point numbers that specified that if you are working with 32 bits you should use 1 bit for the sign (positive or negative) and 8 bits for the position of the radix point (from -127 to +127) which gives a total of 255. The value of the actual number can go as high as just below

2^{128}

the remaining bits (23) represent the mantissa, which is the actual digits of the number. This simply works because the first significant digit of a binary number is always 1, there is no need to include this digit in the computer’s representation of the number, it is simply always implicitly there.

A great visualization for this can be seen as:

Source: https://en.wikipedia.org/wiki/IEEE_754

You can think of the exponent indicating the size of the number while the mantissa or fraction in the above image determines the precision of the number.

A fun little trick you can do in C++ to actually see this in action is with this code snippet:

#include <stdio.h> 

struct FloatBits 
{
    unsigned int fraction:23; /**< Value is binary 1.fraction ("mantissa") */
    unsigned int exp:8;       /**< Value is 2^(exp-127) */
    unsigned int sign:1;      /**< 0 for positive, 1 for negative */
};

/* A union is a struct where all the fields *overlap* each other */
union FloatUnion 
{
    float f;
    FloatBits b;
};

int main()
{
    FloatUnion s;
    s.f=8.0;
    printf("%f = sign %d exp %d fract %d\n", s.f, s.b.sign, s.b.exp, s.b.fraction);
    return 0;
}

How this snippet works is that we simply define a struct for the bits just as how we specified in the image and description above, this can be done using C++ bit fields. The order of the fields is backward to what you might have imagined, this is because the machine we are working on is little-endian.

We then define a union for the float primitive as well as our FloatBits struct, this allows us to create a primitive float and see the same representation in our data type.

The calculation of the number looks like: $$value = (-1) * sign * 2 (exponent-127) * 1.fraction$$

For example the value $$8.0$$ specified in the example above would be stored with the sign 0, exponent 130 $$(3+127)$$ and the mantissa would just be zeroes because the leading 1 is implicit.

Once again problems arise because no matter how precise we make these floating point numbers they will rarely be exact. This means that errors in calculations can happen, while this is not as common anymore it can still easily happen. These are mostly because of rounding errors where a number cannot be represented exactly and is rounded to the nearest number. Performing heavy math and scientific calculations will be a major problem. Sometimes it can help to move things around in your equations but the problem is still there. Nowadays however compilers tend to take care of this for us so rounding errors are less common.

Another problem is that floating point calculations use more expensive instructions than integers hence can result in worse performance than just using integers. However modern processors are becoming better and better at doing this as well but it is something to keep in mind.

If you really want to dive into floating point and its ups an downs I can heavily recommend this article: What Every Computer Scientist Should Know About Floating-Point Arithmetic

Computer Memory Part 4

Oskar Mendel — Mon, 04 Jul 2022 05:25:54 +0000

In this article, we will finally get our hands dirty by writing some code. We’ve now learned about how the CPU works and how it deals with memory so now it is time to discuss what programmers can do with this knowledge.

Programming in a way that utilizes the CPU cache efficiently is a whole subject on its own. I will for sure not be able to cover everything in this subject but hopefully, at least get you started.

Data-oriented design

This is a subject that is quite popular within the game development space where you focus on the data layout of your application. Some may think that the compiler is smart enough to do this for them but this is not the case as compilers lack the bigger picture it needs to optimize the data access and data flow of the application.

Optimize for size

One part of the data-oriented design is to optimize your data structures for size. Why this can be important because if your data structure is small then more of them can fit within a single cache line.

An example of how this may look in practice is pretty simple. The compiler has explicit alignment for primitive types and their structures.

This means for example that an int can never be on address 0x15 (unless you specifically tell it to have a different allignment) because it is aligned to 4 bytes so the only aligned memory addresses would be: 0, 4, 8, 0xC, 0x10, 0x14, 0x18 …

Putting that same int on any misaligned address would be undefined behavior and the code would potentially not work at all. With that in mind look at the following code snippet:

struct example
{
  char  A;
  uint32_t B;
};

Since a char is 1 byte the 32-bit integer here would be misaligned if the compiler did not introduce padding between the two fields. To see what the compiler does behind the scenes there is a flag for MSVC that allows you to print out the layout of your data structure called /d1reportSingleClassLayout which if we use we get the following output:

class example   size(8):
    +---
 0  | A
    | <alignment member> (size=3)
 4  | B
    +---
Compiler returned: 0

This padding can lead to the structure being larger than it needs to be based on in which order you place your fields in that struct. Let's take another example:

struct example
{
    uint32_t A;
    uint64_t B;
    uint32_t C;
};

/*
class example   size(24):
    +---
 0  | A
    | <alignment member> (size=4)
 8  | B
16  | C
    | <alignment member> (size=4)
    +---
Compiler returned: 0
*/

This would result in a structure of 24 bytes due to the padding being introduced between A and B as well as after C. However if we re-order our fields like this:

struct example
{
    uint64_t B;
    uint32_t A;
    uint32_t C;
};

/*
class example size(16):
    +---
 0  | B
 8  | A
12  | C
    +---
Compiler returned: 0
*/

And completely get rid of the padding and get a smaller resulting data structure which in turn we can fit more of in the cache.

Spatial locality

Another common concept in data-oriented design is to start thinking about how your data is accessed. By now you should understand that processing data sequentially in memory is more efficient that having to jump around to different memory locations. A simple way to show this is when organizing data in terms of structures of arrays (SOA) versus arrays of structures (AOS). Data structure adopting this mindset looks like this:

#define SIZE 16384

typedef struct entityaos_
{
    uint64_t Power;
    uint64_t Health;
    uint64_t Speed;
} entityAOS;

typedef struct entitysoa_
{
    uint64_t Power[SIZE];
    uint64_t Health[SIZE];
    uint64_t Speed[SIZE];
} entitySOA;

What happens here is that instead of allocating an array of entities we have a data structure that has all the different fields an entity can have in its arrays. The implications these two methods have on memory access are very different and can be easily spotted when visualized.

Now instead of processing each entity separately, we would instead process their fields. This allows us to deal with the specific field as a contiguous block of memory which helps us with fitting more of that property into the cache. I wrote a small piece of code to showcase this, here is two dummy functions for the two structs presented above which go over each entity and sum their power level.

#define SIZE 16384

typedef struct entity1_
{
    uint64_t Power;
    uint64_t Health;
    uint64_t Speed;
} entityAOS;

typedef struct entity2_
{
    uint64_t Power[SIZE];
    uint64_t Health[SIZE];
    uint64_t Speed[SIZE];
} entitySOA;

void InitEntityAOS(entityAOS *E)
{
    E->Power = rand();
    E->Health = rand();
    E->Speed = rand();
}

void InitEntitySOA(entitySOA *E)
{
    for (int i = 0; i < SIZE; ++i)
    {
        E->Power[i] = rand();
        E->Health[i] = rand();
        E->Speed[i] = rand();
    }
}

uint64_t SumEntitiesAOS(entityAOS *Entities, int Number)
{
    uint64_t Sum = 0;

    for (int i = 0; i < Number; ++i)
    {
        Sum += Entities[i].Power;
    }

    return (Sum);
}

uint64_t SumEntitiesSOA(entitySOA *Entities, int Number)
{
    uint64_t Sum = 0;

    for (int i = 0; i < Number; ++i)
    {
        Sum += Entities->Power[i];
    }

    return (Sum);
}

The result of benchmarking this can be seen in the following graph where the lower bar means faster. Here processing the SOA-based entities is about 3,5 times faster than processing them as AOS. A small disclaimer here is that entity is just an example and probably not something I would write like this in the real world as it would get tedious.

Intrinsics

Moving on we will be using something called intrinsics. What this is is a specific compiler function not part of any library but the compiler itself. These intrinsic functions can be thought of almost like an inline function that the compiler exposes to you when programming. We will specifically use intrinsics that are directly mapped to the x86 single instruction multiple data (SIMD) instruction set. SIMD is a way of operating on multiple data at once. For example in the previous section when we are adding all the power values for the entities instead of looping over each one we can loop over four at a time and add all of them together increasing the performance even further. However this type of optimization I would expect the compiler to try and do for us in this specific example due to its simplicity.

Figure from H. Jeong, S. Kim, W. Lee, and S.-H. Myung, “Performance of sse and avx instruction sets,” arXiv preprint arXiv:1211.0820, 2012.

There are two main SIMD instruction sets available called SSE (Streaming SIMD Extensions) and AVX (Advanced Vector Extensions) which offer 128-bit XMM registers and 256-bit YMM registers respectively.

Initially, SSE offered a set of 70 instructions that number was later increased with the releases of SSE2, SSE3, SSSE3, and SSE4. The XMM registers are displayed in the figure above and as you can see this instruction set allows for operating on four values at once since each register is 128-bit (16 bytes).

The AVX instruction set uses the YMM registers which can fit double the size of an XMM register which means that eight values can be stored in one register which is 256-bit (32 bytes) in size. In addition to its size, the AVX instruction set also provides the option for three input arguments which allows functions with the format of c = a + b instead of the normally used format a = a + b which SSE is restricted to.

Important to note when using SIMD instructions is to keep track of what throughput the instructions used have and how that affects your application. An example is the AVX instruction “VDIVPD” whose latency is twice as high as the alternative SSE instruction “DIVPD”. Using the wrong instructions can have a negative impact and become a performance bottleneck.

A great resource for available intrinsics is available on Intel’s intrinsic guide. I will probably make a separate series on SIMD so I won’t touch more on this subject here but if you are confused by the _mm instructions in the following sections do know that they are intrinsic functions and their documentation is available in the intel’s guide.

Bypassing the cache

Sometimes we are working with data that will not be immediately used or with large data structures and because each store operation will read a full cache line first and then modify that cached data if we have a large enough structure that means that the earlier parts of it will be evicted from the cache as we process the later parts of the structure and this makes caching the writes ineffective.

To solve this we have something called non-temporal write operations. If you remember that temporal here refers to re-use within a relatively small time duration and since the operation is non-temporal there is no reason to cache it. These operations do not read a cache line and then modify it, instead, they write new content into memory directly.

Following are a couple of code snippets taken from Ulrich Drepper's paper which perfectly display how to do this. In the first one we can see the available intrinsics to perform the non-temporal writes:

#include <emmintrin.h>
void _mm_stream_si32(int *p, int a);
void _mm_stream_si128(int *p, __m128i a);
void _mm_stream_pd(double *p, __m128d a);
#include <xmmintrin.h>
void _mm_stream_pi(__m64 *p, __m64 a);
void _mm_stream_ps(float *p, __m128 a);
#include <ammintrin.h>
void _mm_stream_sd(double *p, __m128d a);
void _mm_stream_ss(float *p, __m128 a);

The next snippet shows how to use these intrinsics in order to initialize a matrix which can be useful when doing math or game development:

#include <emmintrin.h>
void setbytes(char *p, int c)
{
    __m128i i = _mm_set_epi8(c, c, c, c,
                             c, c, c, c,
                             c, c, c, c,
                             c, c, c, c);
    _mm_stream_si128((__m128i *)&p[0], i);
    _mm_stream_si128((__m128i *)&p[16], i);
    _mm_stream_si128((__m128i *)&p[32], i);
    _mm_stream_si128((__m128i *)&p[48], i);
}

This is also how the memset function within the C standard runtime deals with writing large blocks of memory. There is a single instruction available _mm_stream_load_si128for loading with the same non-temporal memory hint which means that you do have the option of loading memory without risking cache eviction.

Final notes

Using what we’ve learned so far in the series we should have all the tools available to understand how we can optimize our application's cache usage. While the series has not presented every single optimization technique I think it has successfully laid the foundation for thinking about memory.

Moving on from here involves a lot of reading and experimentation, every application is different and hence needs different types of optimizations. Unfortunately for these types of things, there is no universal solution but to think about your data and how it is moving around in your application.

Resources

Computer Memory Part 3

Oskar Mendel — Mon, 27 Jun 2022 14:38:55 +0000

Last article we learned about CPU caches and its different levels, we also learned about cache lines, how they are stored and retrieved and last but not least we also touched upon multiprocessing describing the MESI protocol briefly.

In this article we will dive into virtual memory as well as non-uniform memory access. I suspect this to be the last article before we start to actually discuss code.

Virtual Memory

The virtual memory subsystem is part of the processor and can provide a virtual address space to each process, this kind of makes each process think it's alone within the system. The main storage from the process perspective becomes one contiguous address space or collection of contiguous segments of memory.

The part of the CPU that implements the virtual address space is the Memory Management Unit (MMU). The operating system has to manage the virtual address spaces and assign them with real memory, the CPU has the capabilities here to automatically translate virtual addresses into physical addresses. A very beneficial part of this is that the main memory can be extended further than the real main memory’s capacity by utilizing disk storage.

The way the CPU looks up a physical address is by walking a set of hierarchically organized directories.

Taken from Drepper, Ulrich. “What Every Programmer Should Know About Memory.” (2007).

The above figure displays how a 64-bit address maps into the different directories. First, the top bits of the address are removed and used as a lookup inside the root directory which is the L4 Directory in this image.

When inside the L4 directory we will determine if it's a valid address if it's not we will stop because of a page fault while if it's valid we will use those bits to lookup which L3 directory we are going to look at. The process is then repeated by using the Level 3 Index in the L3 directory. Once the process has been repeated the L1 directory will find out where the memory is in physical memory, the remaining bits of the virtual address are then used as an offset within the resulting page.

With all the caching we’ve gone through earlier that is great we don’t have to read memory that often but if we would have to perform four reads instead of one because of looking up physical memory addresses that would be very inefficient.

TLB cache

To solve that we have another cache called Translation Look-Aside Buffer (TLB). These TLBs are multi-level caches for the virtual address translations. On my machine which has a Haswell-based Intel CPU, there are two levels of TLBs, an L1 and L2. The L1 has 64 4KB page entries, 32 2MB, and 4 1GB page entries. What is stored inside one of these cache entries is the page for this specific translation, this means that for each entry there are 4096 physical bytes available which mean that there is a total buffer of 256KB that can be cached and looked up instantly.

The 32 2MB pages and the single 1GB page are something often referred to as “Huge pages” and are somewhat tedious to set up as they need for example administrator privileges on Windows and have the risk of failing if you have more of it than available memory. But it can be quite worthwhile as you do get a big buffer of memory which lets you prevent TLB misses.

With all this said the TLB is not something thought of much as it does get flushed upon context switches.

In practice

This gives quite some power to the developer to do some very interesting things. When allocating memory through the virtual memory system the memory is not actually allocated physically but instead just reserved so that no other code can use that memory space until we start operating on the allocated pages.

Most commonly in ArrayList implementations, the array size is first set to a default value like 4, then once the capacity is met the underlying array is simply reallocated into the double size.

Using virtual memory we don’t have to go through this hassle but instead, we can allocate a very big array from the start, let’s say for example 1 million objects.

This can be done using VirtualAlloc on Windows or mmap on Linux.

NUMA

Non-uniform memory access is just something we will briefly mention but not talk about too much.

NUMA comes into play when you are dealing with multi-chip solutions where you have more than one physical CPU. This is very common for servers or high-end machines.

The communication between these CPUs is expensive and they have their own set of RAM plugged directly into them. The RAM plugged in to all of those CPUs does become the RAM of the computer so it is possible for one CPU to access the RAM plugged into the other but this is of course slower. So non-uniform in this case means that memory can’t be accessed in a uniform way access memory in the system as it depends on where it is plugged in on the chip and where your application is running.

NUMA can improve the performance over single shared memory on a factor based on the number of processors available.

References

Computer Memory Part 2

Oskar Mendel — Thu, 16 Jun 2022 17:56:09 +0000

Last article we talked about the physical aspects of memory, how it communicates with different components, and how RAM chips work. This time we will combine that with how the memory within the CPU works.

CPU cache

CPU speeds have increased over the years while the speed of RAM chips hasn’t increased in the same pase. As we went over in the last article this is not because there is no faster RAM but because it wouldn’t be economically viable. Therefore it is more common to choose a lot of relatively fast RAM over a small amount of very fast RAM because it is much faster than accessing data on disk so having more space to put stuff in RAM helps us speed up our applications.

This fortunately is not an all-or-nothing deal, we can combine the two and use a bit of both. One way would be to decide on one part of the address space and dedicate it for SRAM and the rest DRAM and rely on the operating system to optimally distribute it. While possible it is not an ideal way of setting it up because mapping physical resources of SRAM to the virtual memory space of the individual processes is hard and also would require every process to administer the allocations of this memory location which would cause a lot of overhead. Every process would want access to this fast memory which would require us to deal with heavy synchronization.

So instead of this approach, it is under the control of the CPU. In this implementation, the SRAM is used to make temporary copies (cache) of data within the main memory which is likely to soon be used. The way this is possible is due to both program code and data having temporal and spatial locality.

Temporal locality refers to data being reused within a relatively small time duration, for example, a call to a function whose address is far away in memory space but a call to this function is made often.

Spatial locality refers to the use of data elements within relatively close storage locations, for example looping over an array in a for a loop.

The CPU caches are not that big on most machines. For example, my machine has 16GB of ram but only 4MB of cache. This is not a problem if the data being worked on is smaller than the cache size but we often want to work on data sets as well as run several processes using memory differently from each other. Because of this, the CPU needs an efficient and well-defined strategy to decide when to cache what.

Cache levels

The CPU cores themselves are not directly connected to the main memory instead they are connected to the cache which acts like a middleman where all the load and store operations first have to go through the cache before it reaches the CPU.

The connection between the cache and CPU is a special fast connection and the connection between cache and main memory is connected via the Front-side bus briefly mentioned in the previous article.

With time when the speed difference between main memory and cache increased, instead of increasing the size of the cache, new caches were added that are bigger and slower. This is to save cost.

That is why we today talk about multiple cache levels where the CPU cache is divided into multiple levels all increasing in size and decreasing in speed. Most common are CPUs with three levels of cache known as the L1, L2, and L3 caches where L1 is the smallest but also the fastest to access while L3 is the slowest but largest.

The L1 and L2 cache are a part of the individual CPU cores while the L3 cache is shared between all cores. Let us talk about how this makes sense. Remember when we briefly mentioned that every load and store operation has to go through the cache first?

Because of this fact, every time memory is needed by the processor the memory is first looked for within the cache. First, the L1 cache is searched then the L2, then L3, and only then the memory is fetched from the main memory. Every time memory is loaded it is also loaded into the cache and once new memory is loaded the old memory is not thrown away but instead pushed into the bigger caches so first it is pushed out of the L1 cache into the L2 cache and then it is pushed into L3 and then in finally to main memory.

This may seem very inefficient but if you compare the speeds of access for different parts of memory you will notice that it's still more efficient to go through this process than always loading directly from the main memory.

Destination	Cycles	Size
Register	≤ 1	8B
L1	~4	32KB
L2	~12	256KB
L3	~36	2 - 45MB (Shared)
Main memory	~230	-

The above numbers are from my old machine running an intel Haswell chip 3.4 GHz i7-4770.

Cache lines

First of all the processor break the memory up into parts it can reason about and this is known as “cache lines”. The reason for this is if you remember from the previous article that RAM tries to be as efficient as possible by transporting as many words in a row as possible without the need for a new CAS or RAS signal.

A cache line is not a word but instead a line of several words, a cache line is normally 64 bytes of memory and if the memory bus is 64-bit wide this means 8 transfers per cache line.

The memory address for each cache line is computed by masking the value according to the cache line size. For a 64-byte cache line, this means that the low 6 bytes are zeroed and used for the offset into the cache line.

Some number of bits is then taken from the address to choose a set and we are left with 64 - S - 6 bits to form a tag. The chosen set maps the cache line into its own “section” of the cache.

Within the same set, there are several paths and the number of paths corresponds to the number of cache entries of the same set that can occupy that part of the cache. These are different depending on which level of the cache we are in.

So once again the bottom 6 bits tell us where we are within a cache line, the next S bits will tell us which path within the cache we will be looking at. Lastly, there is the Tag which allows us to identify the data that we’re interested in.

Taken from Drepper, Ulrich. “What Every Programmer Should Know About Memory.” (2007).

Why it works this way can be described using this simplified block diagram of a 4-way cache.

At the top, we have an address that is split into a tag, set, and offset. First of all the set is going to be fed into the multiplexers where each of the columns below represents one set. From each row of sets, there is a line which is the path we previously mentioned.

Once a column is selected the data and their tags are fed into a bunch of comparators where the tag from the cache and then the top bits of the address itself are compared where the comparator will compare them and output a one bit if they match and zero if they don’t. If a one bit is emitted it will open up the path for the data which has then been selected.

Multiprocessing

You may have asked yourself how this all works when our machines perform an insane amount of different things at the same time. As we went over before the L1 and L2 caches are unique per core which means that they are shared by hyperthreading but how is it possible for two CPUs to read and write to the same memory if each core has its own set of L1 and L2 caches while keeping a coherent view of the memory?

For this, there is a protocol developed to solve this problem called MESI whose name consists of the four states each cache line can have (Modified, Exclusive, Shared, and Invalid).

Modified: The cache line has been modified locally, this means it's the only copy within any cache.
Exclusive: The cache line is not modified and known to not be loaded in any other cache.
Shared: the cache line is not modified and might exist in another cache.
Invalid: The cache line is invalid or not used.

Taken from Drepper, Ulrich. “What Every Programmer Should Know About Memory.” (2007).

Above is a diagram of all the possible state transitions within this protocol. We will go over the most important parts.

Initially, all the cache lines are empty therefore their state is Invalid. If data is loaded into the cache for writing the state will be changed to Modified. If data is loaded for reading the state will depend on whether another processor has the cache line loaded as well, if that is the case the state will be Shared otherwise it will be set to Exclusive.

If a cache line is marked as modified and later read or written to on the same processor the state does not have to change however if a second processor wants to read from the same cache line the first processor has to send the content of its cache to the second processor followed by changing its state to Shared.

When sending the data it is also processed by the memory controller which stores the memory.

If the second processor instead wants to write to the cache line the first processor sends the content over and then marks its cache line locally as Invalid. This is also known as RFO (Request for ownership).

If a cache line is marked as Shared and the local processor wants to read from it no state change is required but if a write operation from another processor is requested then the same type of RFO message is announced and the first processor marks the cache line as invalid.

The Exclusive state is very similar to the Shared state except that a local write operation does not have to be announced on the bus. In this case, the local cache is the only one holding this specific cache line which can be a huge performance advantage.

Thoughts

While this article didn’t go into the more specific parts of the performance benefits of the CPU cache I still found it very informative and useful to understand how to think about the memory within the cache. Combining what we learned here together with what we talked about in the previous article it does make sense to me why we talk about cache lines instead of just cached memory as well as understanding the hierarchical structure of the different cache levels and how they relate.

References

Computer Memory Part 1

Oskar Mendel — Tue, 14 Jun 2022 04:47:42 +0000

At work, we have something that we call "competence day" once per month where all developers spend an entire day learning new things and keeping up to date with technology. Recently I've been spending those days just reading since when working a day job then coming home coding at Nullsson things I rarely have time left to read.

Inspired by a talk that Jonathan Blow had called "Preventing the collapse of civilization" I started to investigate academic papers since that's an area that I have usually avoided in the past. Within this talk Jonathan mentions how technology degrades naturally and this has since stuck with me. I notice just with smaller features at work that while working on a feature you become sort of an expert at that specific thing since you're investigating and falling down all the different pits there is implementing that thing. If someone else would pick up your work mid through they'd have to go through the same process and potentially making the same mistakes you did.

I stumbled upon a paper by a man named Ulrich Drepper called "What Every Programmer Should Know About Memory" and this paper was sort of a big eye opener for me. It inspired me to make a presentation at work teaching others about what I've learned and that is also what this initial article is about, my notes learning about this stuff.

For me there are several areas of memory I want to explore and I plan on making this series about the things I learn researching this and learning more about it. I plan on doing a few of these depending on how interesting and valuable I feel it is.

Computers

Historically computers were first designed as a single component where all components had a similar performance. Later this was split up into different components and optimized which resulted in some parts being faster than others. This also resulted in some components becoming bottlenecks, the main ones was and still is the mass storage and memory systems. Since we are going through memory with these articles we will completely ignore the mass storage part just like Ulrich's paper.

By Original: Gribeco at French WikipediaDerivative work: Moxfyre at English Wikipedia - This file was derived from: Diagramme carte mère.png, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3789066

Personal computers and smaller servers adopted a structure where the chip was split into two main parts: The northbridge and the southbridge. This today has changed a bit but I feel like its still relevant when we think about how things works.

The CPU was connected to the northbridge through what's called the front side bus also known as FSB. Inside the northbridge there is a memory controller whose implementation decides which types of RAM chips that are supported by the computer.

To reach other system devices the northbridge communicates with the southbridge which in turn communicates with different devices through its own set of busses like PCI, PCI Express, SATA and USB.

Historically this design came with a problem which was when a device wants to access the RAM. In older PCs' communication on either bridge had to pass through the CPU which resulted in performance problems. A workaround was developed called DMA (Direct memory access). DMA allowed the northbridge to help store and receive data in RAM directly. This is what basically all high performance devices use today and the battle is for bandwidth since the northbridge and CPU compete for RAM access.

Other components on the chip such as the network controller cannot really afford all the traffic passing the CPU either hence it makes heavy use of DMA by writing and reading memory there directly. At times where there is heavy DMA traffic it might stall the CPU just because its waiting for data from the memory. Worth to note that today the northbridge has been moved into the CPU itself on modern chips and instead we just refer to it as CPU and a chipset where the chipset acts like a southbridge.

Different types of RAM

RAM stands for "Random Access Memory" and what this means is that memory doesn't have to be accessed in a sequence and instead can be accessed directly. There are several different types of RAM and the differences can be dramatic, we will however keep it on topic and only talk about the main ones being SRAM (Static RAM) and DRAM (Dynamic RAM).

Hardware intermission

Before getting into the specifics I feel like its important to understand the two main electrical components that we will talk about moving forward. First of all we got the Transistor which is the main component in almost any electrical devices today.

A transistor is like a binary switch which allows current to either flow through it or not, they can be placed in different patterns to form logical gates.

Then we have the Capacitor which is a component used to store a small electrical charge and release it at a later time. I picture this almost like a very small battery.

These components today are made at semiconductor using technology that allows to make these components in the size of nanometers. This is so small that you can't see it without a microscope.

Static RAM

Taken from Drepper, Ulrich. “What Every Programmer Should Know About Memory.” (2007).

This is a 6 transistor static RAM cell. The core of it is made up of M1 - M4 which forms two "Cross Coupled Inverters". They can have two stable states either 0 or 1 respectively and they are stable for as long as there is power available on the Vdd (Voltage Drain Drain). These are used as a sort of "Flip Flop" mechanism to flip the electrical current back and forth to avoid having to refresh the state which we will get into shortly. In order to access its state the WL (Word Access Line) is raised which allows the state of the cell to immediately be available on the two BL lines.

Dynamic RAM

Taken from Drepper, Ulrich. “What Every Programmer Should Know About Memory.” (2007).

Here is a dynamic RAM cell which you can probably see looks simpler than the static one. This is because it only uses one transistor and one capacitor. The state of the cell is kept within the capacitor in form of an electric charge and the transistor is used to guard the access to it.

In order to read the state of the cell the Access Line (AL) is raised which causes current to flow on the Data Line (DL) or not depending on the capacitor. To write state to the cell the DL is set and then AL is raised for a long enough time to either charge or drain the capacitor. An important thing to keep in mind here is that since the cell makes use of a capacitor the charge inside it is drained every time its state is read. This means you cannot repeat the procedure without charging it somehow. Every read of a cell is followed by a write where the output of the read is routed back to the cell to automatically charge it again.

It only takes a short amount of time to charge the cell but also for the charge to dissipate and this problem is referred to as "Leakage". A RAM cell like this can store one bit for us (0 or 1) and today it is common with several gigabytes of RAM storage on these chips hence we are talking billions of these cells and because of leakage all of their state has to be refreshed. For most chips this needs to happen every 64ms. During a refresh it is not possible to access the memory, the reason behind this is that a refresh is basically a read operation where the read value is immediately discarded. For some workloads this overhead may stall up to 50% of the memory access.

The main advantage that the dynamic RAM cells have over static RAM is the chip real estate. DRAM cells takes up much less space but is also much cheaper to produce. This means its simpler to pack several of them close together on the same die. SRAM cells are mainly used for our CPU caches.

DRAM Access

A program that we developers make uses virtual addresses for its memory locations, the CPU takes these virtual addresses and translates them to physical ones and finally the memory controller selects the RAM chip for that corresponding address. To select an individual memory cell on that RAM chip parts of the physical address are passed in the form of a number of address lines. Accessing memory individually from the memory controller is impractical since 4GB of RAM would require 2^32 address lines. Instead addresses is passed as an encoded binary number using a smaller set of address lines. This type of address needs to be demultiplexed first which means that one signal is routed into many signals (One to Many). The cells on the chip is organized in rows and columns in order to decrease the size of the demultiplexer.

Taken from Drepper, Ulrich. “What Every Programmer Should Know About Memory.” (2007).

First the Row Address Selection (RAS) is passed its signals which are demultiplexed in order to find the correct row for the address, when found the entire row of cells are made available to the Column Address Selection (CAS) which uses a multiplexer (Many to One) to route the correct cell to the data pin. Worth to note is that this happens several times in parallel.

DRAM Access technical details

Synchronous DRAM (SDRAM) works relative to a clock provided by the memory controller which frequency determines the speed of the bus between the chips and memory controller. 800MHz, 1066MHz, 1333MHz and 1600MHz are all frequencies of used maybe 10 years ago. These frequencies used to advertise RAM chips are not the frequencies actually used on the bus but instead the values on the chips are double or quad pumped which means that the data is transported two respectively four times per cycle. A quad pumped 200MHz bus is therefore advertised as an effective 800MHz bus. However today it is not unusual for chips to be in the range of 3200 - 3800MHz.

Taken from Drepper, Ulrich. “What Every Programmer Should Know About Memory.” (2007).

A read cycle begins with the memory controller making the row address available by lowering the RAS signal. All signals are read on the rising edge of the CLK signal. Setting the row address causes the RAM chip to launch the addressed row. The CAS signal can be sent after a delay called RAS to CAS delay (tRCD) which is specified in clock cycles. The column address is then transmitted by making it available on the address bus and lowering the CAS line, this allows both the row and column address be sent on the same address bus. After this the addressing is complete and the data can be transmitted. The RAM chip needs some time to prepare for this and this is referred to as CAS latency (CL).

It is quite a process to read data as you can see. That is why it is important to try help the computer collect as much related data as possible in one go in order to not have to go through this process as much, this is one of the ideas behind "Data oriented design". The memory controller helps with the process by not only transferring one data word but instead DRAM modules allows the memory controller to specify how much data to be transmitted to save time, this is often a choice between 2, 4 or 8 words. This allows for filling entire cache lines without a new read cycle.

DDR is a technology that is used today which stands for Double Data Rate, this allows for data to be read on the rising edge of the CLK signal as well allowing data to be read at double the speed without an increase in frequency.

Thoughts

Just this first part learning about RAM and how the tech works was so fruitful. Like I said for me reading this for the first time was an eye opener when it comes to how powerful machines we have in front of us today. I did previously to learning about this understand that memory access was something that you had to think about for performance but after learning about this suddenly there is a reason behind the question WHY things are the way they are. This has been my notes collected from learning about RAM and in the future I plan on doing a write-up on different areas of memory. Almost all the content of this article can also be learned about within the paper mentioned at the beginning of the article but for me it helps writing about it and reasoning a bit behind it for it to really stick and perhaps someone may find this useful.

DEV Community: Oskar Mendel

Creating good puzzle games

Core mechanic

Linear and non-linear

No Tutorials

Level design language

Don’t design backwards

UI Subsystem Iteration

Graphical User Interface

UI Modes

Retained mode

Immediate mode

The previous UI system

Harder, Better, Faster, Stronger

Flexible components & developer freedom

Ease of use

Result

Maraton Release v1.4.0

What is going on?

Why not unity?

Quick overview

Closing notes

Mathematics And Physics Part 2

Fractions

Multiplication of fractions

Division of fractions

Addition and subtraction of fractions

Factors

Greatest common divisor

The Modulo operator

Check if number is even or odd

Cycling through data

Proportions

How to hack a .NET Core game

Background

Attempt 1: Memory hacking

How to access memory addresses through code

Why attempt #1 doesn’t work for .NET Core

Attempt 2: Signature Scanning

Why attempt #2 doesn’t work for .NET Core

Attempt 3: CLR Hosting

Final notes and future reading

Mathematics And Physics Part 1

Numbers

Representing numbers

How computers represent numbers

AND

OR

NOT

Floating point

Scientific notation

IEEE Standard

Computer Memory Part 4

Data-oriented design

Optimize for size

Spatial locality

Further reading

Intrinsics

Bypassing the cache

Final notes

Resources

Computer Memory Part 3

Virtual Memory

TLB cache

In practice

NUMA

References

Computer Memory Part 2

CPU cache

Cache levels

Cache lines

Multiprocessing

Thoughts

References

Computer Memory Part 1

Computers

Different types of RAM

Hardware intermission

Static RAM

Dynamic RAM