Blog for coding and math stuff

Raw Source Code

Complete high level overview of the memory mechanisms in the Unreal Engine MallocBinned2 allocator.

An illustrated overview of the Unreal Engine MallocBinned2 allocator

Pointers to the MallocBinned2 source code to be used in tandem with the illustrated overview

Friendly MB2 source code reference


<ProseBlock>

If you just want the full source code [click here](https://gist.github.com/romualdo97/7423f4c5812ee72745a3b3bc3740d158).

## Unicode basics

Unicode associates each possible character (letter, number, punctuation, emoji, etc…) with a
unique number known as a codepoint.

> Characters are the abstract representations of the smallest components of written
> language that have semantic value.
>
> [Unicode 16.0.0 / 2.2.3 Characters, No Glyphs](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-2/#G8085)

The set of all codepoints is known as [codespace](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-2/#G25564) and Unicode states that there are `1114112`
or `0x10FFFF` codepoints.

[Notationally](https://www.unicode.org/versions/Unicode16.0.0/core-spec/appendix-a/#G7083), a codepoint is denoted by `U+n`, where `n` is four to six hexadecimal digits, omitting leading zeros,
unless the code point would have fewer than four hexadecimal digits—for example, `U+0001`, `U+0012`, `U+0123`,
`U+1234`, `U+12345`, `U+102345`.

The codespace is divided in `17` sections or ranges, known as planes, each plane has `65536` characters.
The first plane (Plane 0) is known as the `BMP` or [Basic Multilingual Plane](https://en.wikipedia.org/wiki/Plane_(Unicode)),
this plane contains English letters, and matches ASCII from `0` to `127`.

The last four hexadecimal digits in each codepoint indicate a character’s position inside a plane.
The remaining digits indicate the plane. For example, `U+23456` is found at location `0x3456` in Plane 2.
for more details see [Unicode 16.0.0 / 2.9 Details of Allocation](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-2/#G16482).

In this post we’re interested in encoding Unicode codepoints, which for our purposes it will mean how
to represent a codepoint in binary for actual usage in computer systems.
Let's start with a couple of observations.

## Bits required

We can represent any codepoint in the codespace using `21` bits

```math
2^{21} = 2097152
```

This would leave us with `965040` unused numbers.

```math
2097152 - 1114112 = 965040
```

We also can encode the entire codespace using any number of bits greater than `21`,
but we end up with a lot more unused numbers (which sometimes is preferable,
see UTF-32 encoding below).

Alternatively, we can use `16` bits + `20` bits
to precisely represent the Unicode codespace
(See UTF-16 encoding below).

```math
2^{16} + 2^{20} = 65536 + 1048576 = 1114112 
```

## Fixed vs variable width encoding

When representing a codepoint in memory we need to define how many bits will be used per character,
fixed-width means that all codepoints will be encoded using the same number of bits,
variable-width means that different characters can be encoded with different numbers of bits.

A specific encoding system like `UTF8`, `UTF16` or `UTF32` defines the number of bits to be used
for a given codepoint through a code unit, which is the minimal storable information in the system.
We say for example:

The code point `U+1F92F`: 🤯

- Requires 4 code units to be encoded in UTF-8 (where code unit is 8 bits)
- Requires 2 code units to be encoded in UTF-16 (where code unit is 16 bits)
- Requires 1 code unit to be encoded in UTF-32 (where code unit is 32 bits)

The code point `U+0041`: A

- Requires 1 code unit to be encoded in UTF-8 (where code unit is 8 bits)
- Requires 1 code unit to be encoded in UTF-16 (where code unit is 16 bits)
- Requires 1 code unit to be encoded in UTF-32 (where code unit is 32 bits)

## UTF 32
It is a fixed-width encoding, each codepoint is directly mapped to a 32 bit code unit

```cpp
uint32_t LetterA = 0x0041;
```

Can be useful when working on unicode text whose characters need to be indexed easily or require other per-codepoint processing:

```cpp
uint32_t RandomUserEmoji = UserInputEmojis[4];
```

See [Unicode 16.0.0 / 3.9.1 UTF-32](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-3/#G28875)

## UTF 16
It is a variable-width encoding, a codepoint is represented using one code unit (16 bits)
if the character to be encoded is in the `BMP plane` or two code units otherwise.

Codepoints outside of the `BMP` are encoded using a `surrogate pair`,
which is a pair of two code units whose value is in the range `[0xD800, DFFF]`,
this value is associated uniquely with a Unicode scalar value in the range `[U+10000,U+10FFFF]`.

<img src="/simple-unicode-aware-class-in-cpp/Roadmap_to_Unicode_BMP_multilingual.png"/>

> Figure from [Wikipedia Unicode Plane article]("https://en.wikipedia.org/wiki/Plane_(Unicode)")

The 6 highest bits of a code unit in a surrogate pair, denote which element of the pair the code unit is,
observe the following bit pattern for an illustration:

```cpp
// Possible numeric ranges of first element of the surrogate pair
// First 6 digits are 0b1101’10
From 0xD800 to 0xD8FF = From 0b1101’1000’0000’0000 to 0b1101’1000’1111’1111
From 0xD900 to 0xD9FF = From 0b1101’1001’0000’0000 to 0b1101’1001’1111’1111
From 0xDA00 to 0xDAFF = From 0b1101’1010’0000’0000 to 0b1101’1010’1111’1111
From 0xDB00 to 0xDBFF = From 0b1101’1011’0000’0000 to 0b1101’1011’1111’1111

// Possible numeric ranges of second element in the surrogate pair
// First 6 digits are 0b1101’11
From 0xDC00 to 0xDCFF = From 0b1101’1100’0000’0000 to 0b1101’1100’1111’1111
From 0xDD00 to 0xDDFF = From 0b1101’1101’0000’0000 to 0b1101’1101’1111’1111
From 0xDE00 to 0xDEFF = From 0b1101’1110’0000’0000 to 0b1101’1110’1111’1111
From 0xDF00 to 0xDFFF = From 0b1101’1111’0000’0000 to 0b1101’1111’1111’1111
```

From the above bit pattern we can also note that there are 10 free bits (per pair element)
that can be used to encode stuff, summing a total of 20 free bits
(Which can represent `1048576` distinct values).

See [Unicode 16.0.0 / 3.9.2 UTF-16](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-3/#G31699)

## UTF 8

It is a variable-width encoding, the high bits of each code unit indicate the part of the
code unit sequence to which each byte belongs, for example.

### 0b0xxx’xxxx
Code units that represent an ASCII character, which is a number in the range [0, 127]

### 0b10xx’xxxx
For code units that are part of a code unit sequence but are not the leading (first) byte of the sequence

### 0b110x’xxxx
For code units that are the first byte in a code unit sequence of 2 bytes

### 0b1110’xxxx
For code units that are the first byte in a code unit sequence of 3 bytes

### 0b1111’0xxx
For code units that are the first byte in a code unit sequence of 4 bytes

See [Unicode 16.0.0 / 3.9.3 UTF-8](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-3/#G31703)

## Code

The following code aligns to the [UTF-8 everywhere manifesto](https://utf8everywhere.org/), that suggests using UTF-8 internally
in your program and doing conversions when communicating with other APIs that receive other
types of encodings.

Let's start detecting the size of an UTF-8 code unit sequence, note that there are better ways to implement this
but here we're aiming for a simple and easy to understand approach.

```cpp
enum class EUtf8SequenceSize : uint8_t
{
    One, Two, Three, Four, Invalid
};

[[nodiscard]] EUtf8SequenceSize SizeOfUtf8Sequence(const unsigned char& Utf8Char)
{
    // https://unicode.org/mail-arch/unicode-ml/y2003-m02/att-0467/01-The_Algorithm_to_Valide_an_UTF-8_String
    if (Utf8Char <= 0x7f) // 0b0111'1111
    {
        // ASCII
        return EUtf8SequenceSize::One;
    }
    else if (Utf8Char <= 0xbf) // 0b1011'1111
    {
        // Not a leading UTF8 byte, possibly something went wrong reading previous sequences
        return EUtf8SequenceSize::Invalid; 
    }
    else if (Utf8Char <= 0xdf) // 0b1101'1111
    {
        // Leading byte in a two byte sequence
        return EUtf8SequenceSize::Two;
    }
    else if (Utf8Char <= 0xef) // 0b1110'1111
    {
        // Leading byte in a three byte sequence
        return EUtf8SequenceSize::Three;
    }
    else if (Utf8Char <= 0xf7) // 0b1111'0111
    {
        // Leading byte in a four byte sequence
        return EUtf8SequenceSize::Four;
    }

    // Unicode 3.1 ruled out the five and six octets UTF-8 sequence as illegal although
    // previous standard / specification such as Unicode 3.0 and RFC 2279 allow the
    // five and six octets UTF-8 sequence. Therefore, we need to make sure those value are not in the UTF-8
    return EUtf8SequenceSize::Invalid;
}
```

Now a function to convert an UTF8 sequence into a unicode code point (encoded in UTF32).

```cpp
[[nodiscard]] char32_t NextCodepointFromUtf8Sequence(const unsigned char*& Utf8Sequence)
{
    if (*Utf8Sequence == 0)
    {
        return 0;
    }

    EUtf8SequenceSize NumOfBytes = SizeOfUtf8Sequence(*Utf8Sequence);
    if (NumOfBytes == EUtf8SequenceSize::Invalid)
    {
        return 0; // End processing
    }

    unsigned char FirstByte = *Utf8Sequence;
    if (NumOfBytes == EUtf8SequenceSize::One)
    {
        ++Utf8Sequence; // Point to the start of the next UTF8 sequence
        return FirstByte;
    }

    unsigned char SecondByte = *(++Utf8Sequence);
    if (SecondByte == 0)
    {
        return 0;
    }

    if (NumOfBytes == EUtf8SequenceSize::Two)
    {
        ++Utf8Sequence; // Point to the start of the next UTF8 sequence
        return
            ((FirstByte      & 0b0001'1111) << 6)       |
             (SecondByte     & 0b0011'1111);
    }

    unsigned char ThirdByte = *(++Utf8Sequence);
    if (ThirdByte == 0)
    {
        return 0;
    }

    if (NumOfBytes == EUtf8SequenceSize::Three)
    {
        ++Utf8Sequence; // Point to the start of the next UTF8 sequence
        return
            ((FirstByte      & 0b0000'1111) << 12)      |
            ((SecondByte     & 0b0011'1111) << 6)       |
             (ThirdByte      & 0b0011'1111);
    }

    unsigned char FourthByte = *(++Utf8Sequence);
    if (FourthByte == 0)
    {
        return 0;
    }

    ++Utf8Sequence; // Point to the start of the next UTF8 sequence
    return
        ((FirstByte         & 0b0000'0111) << 18)   |
        ((SecondByte        & 0b0011'1111) << 12)   |
        ((ThirdByte         & 0b0011'1111) << 6)    |
         (FourthByte        & 0b0011'1111);
}
```

The above functions can be easily used to create utility methods for our `Utf8String` class,
below is a function that calculates how many code points does the UTF8 string has.

```cpp

int32_t Utf8String::CodePointsLen() const
{
    if (Len() == 0)
    {
        return 0;
    }

    int32_t TotalCodePoints = 0;
    const unsigned char* Utf8Str = GetRawData();
    while (NextCodepointFromUtf8Sequence(Utf8Str))
    {
        ++TotalCodePoints;
    }
    return TotalCodePoints;
}
```

A function that converts from UTF8 to UTF32
```cpp

std::u32string Utf8String::ToUtf32() const
{
    std::u32string Utf32Output;
    if (Len() == 0)
    {
        return Utf32Output;
    }

    const unsigned char* Utf8Str = GetRawData();
    while (*Utf8Str != 0)
    {
        char32_t UnicodeCodePoint = NextCodepointFromUtf8Sequence(Utf8Str);
        Utf32Output.push_back(UnicodeCodePoint);
    }

    return Utf32Output;
}
```

A function that converts from UTF8 to UTF16
```cpp
std::u16string Utf8String::ToUtf16() const
{
    std::u16string Utf16Output;
    if (Len() == 0)
    {
        return Utf16Output;
    }

    const unsigned char* Utf8Str = GetRawData();
    while (*Utf8Str != 0)
    {
        char32_t UnicodeCodePoint = NextCodepointFromUtf8Sequence(Utf8Str);
        if (UnicodeCodePoint < 0x1'0000) // 0b0001'0000'0000'0000'0000
        {
            Utf16Output.push_back(UnicodeCodePoint);
        }
        else
        {
            UnicodeCodePoint -= 0x1'0000;
            char16_t HighSurrogate = 0xd800 + ((UnicodeCodePoint >> 10) & 0x3FF); // 0x3FF == 0b0011'1111'1111
            char16_t LowSurrogate = 0xdc00 + (UnicodeCodePoint & 0x3FF);
            Utf16Output.push_back(HighSurrogate);
            Utf16Output.push_back(LowSurrogate);
        }
    }

    return Utf16Output;
}
```

See [full source code here](https://gist.github.com/romualdo97/7423f4c5812ee72745a3b3bc3740d158).

## Understanding the `wchar` mess

Size of `wchar_t` can be different depending on the platform, on Windows it’s 2 bytes (16 bits) and on
most Unix systems it’s 4 bytes (32 bits), why?

In the beginning 7 bits were used to encode ASCII characters (numbers from 0 to 127),
then multiple working groups tried to define rules for the usage of one extra bit (8 bits in total)
to represent characters outside of the ASCII range.

ISO produced `ISO-8859-1`, `ISO-8859-2`, and 13 more standards, Microsoft created [Windows-1252](https://en.wikipedia.org/wiki/Windows-1252)
a.k.a [CP-1252](https://learn.microsoft.com/en-us/windows/win32/intl/code-page-identifiers)
(and a bunch of other code pages) and referred to them as "ANSI code pages", which is technically
incorrect because they never became ANSI standards, in words of Cathy Wissink:

> The term "ANSI" as used to signify Windows code pages is a historical reference,
> but is nowadays a misnomer that continues to persist in the Windows community.
> The source of this comes from the fact that the Windows code page 1252 was originally based on an ANSI
> draft, which became ISO Standard 8859-1.
>
> However, in adding code points to the range
> reserved for control codes in the ISO standard, the Windows code page 1252 and
> subsequent Windows code pages originally based on the ISO 8859-x series deviated
> from ISO. To this day, it is not uncommon to have the development community, both
> within and outside of Microsoft, confuse the 8859-1 code page with Windows 1252, as
> well as see “ANSI” or “A” used to signify Windows code page support."
>
> [Unicode WinXP, Cathy Wissink](https://web.archive.org/web/20150204175931/http://download.microsoft.com/download/5/6/8/56803da0-e4a0-4796-a62c-ca920b73bb17/21-Unicode_WinXP.pdf)

Then people noted that if they wanted to encode all possible characters in a unified way,
more than `8 bits` were required, how many?
`16 bits` according to ISO (first draft of `ISO/IEC-10646`) and people from Xerox and Apple (`Unicode 1.0`).

In 1990 two initiatives existed for a unified character set,
`ISO/IEC-10646` and `Unicode`, ISO defined an encoding form known as UCS-2
which was a fixed width encoding of `16 bits`, in 1991 ISO and Unicode agreed to
synchronize their codepoint assignments and UCS-2 became the standard way to encode Unicode codepoints.

Then the cool guys at Microsoft decided to support Unicode, in the process they invented the data
type `wchar` with a size of `2 bytes`, the “w” stands for [wide](https://en.wikipedia.org/wiki/Wide_character) to outline the
fact that this is a character wider than `1 byte`.

Time passed and the smart guys at ISO and Unicode noted again that they needed more than 16 bits
to encode all characters of the world, the solution was the introduction of the surrogate
pairs of `UTF-16` stated in `Unicode 2.0` in 1996, Also `UTF-32` (`UCS-4`) emerged and Unix systems
decided to make their `wchar` to be a size of `4 bytes` instead of 2 for easier unicode support.

## Links
- [Unicode 16.0.0 / 2.2.3 Characters, No Glyphs](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-2/#G8085)
- [Unicode 16.0.0 / 2.2.4 Code Points and Characters](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-2/#G25564)
- [Unicode 16.0.0 / 2.9 Details of Allocation](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-2/#G16482)
- [Unicode 16.0.0 / 3.9.1 UTF-32](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-3/#G28875)
- [Unicode 16.0.0 / 3.9.2 UTF-16](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-3/#G31699)
- [Unicode 16.0.0 / 3.9.3 UTF-8](https://www.unicode.org/versions/Unicode16.0.0/core-spec/chapter-3/#G31703)
- [Unicode 16.0.0 / A.1.1 Code Points](https://www.unicode.org/versions/Unicode16.0.0/core-spec/appendix-a/#G7083)
- [UTF-8 everywhere manifesto](https://utf8everywhere.org/)
- [Unicode WinXP, Cathy Wissink](https://web.archive.org/web/20150204175931/http://download.microsoft.com/download/5/6/8/56803da0-e4a0-4796-a62c-ca920b73bb17/21-Unicode_WinXP.pdf)
- [Wide Character from Wikipedia](https://en.wikipedia.org/wiki/Wide_character)
- [Differences between ANSI, ISO-8859-1 and MacRoman character sets](https://www.alanwood.net/demos/charsetdiffs.html)
- [Basic Multilingual Plane by Wikipedia](https://en.wikipedia.org/wiki/Plane_(Unicode))

## Credits
Written by [Romualdo Villalobos](https://www.linkedin.com/in/romualdo-villalobos/)

</ProseBlock>


A quick tour on different Unicode encode forms with an easy to extend C++ class example

Simple Unicode-aware class in C++


<ProseBlock>

## Introduction

[CRC](https://en.wikipedia.org/wiki/Cyclic_redundancy_check) is a function that receives a sequence of bits of
arbitrary size and returns a sequence of bits of fixed size:

```cpp
uint8_t Result = CRC(ArbitraryLengthData);
```

The function name depends on how many bits it returns:

```cpp
uint8 ResultA = CRC8(Data); // Returns 8 bits
uint16 ResultB = CRC16(Data); // Returns 16 bits
uint32 ResultC = CRC32(Data); // Returns 32 bits
```

Given the same input the function always returns the same output:

```cpp
uint8_t ResultA = CRC8(DataA);
uint8_t ResultB = CRC8(DataA);
assert(ResultA == ResultB);
```

However two different inputs could return the same output, but dependending on the CRC polynomial
in use the chances can be low (As a general note if the polynomial has a name it means that a
couple of PHDs crafted the polynomial
and demonstrated the low chances of repetition under certain criteria).

```cpp
uint8_t ResultA = CRC8(DataA);
uint8_t ResultB = CRC8(DataB);
if (DataA != DataB &&
    ResultA == ResultB)
{
    printf("Collision");
}
```

If you transmit a message of arbitrary size along with the
respective computed CRC it's possible for a receiver to recalculate
the CRC and compare if it is equal to the received CRC
(Used like this by USB, RFID, SD, Bluetooth, Ethernet,
SCTP, PNG, SATA, cksum, Layers on OSI model and much more).

```cpp
// At transmitter
Transmit(Message, CRC32(Message));

// At receiver
DataFrame Received = GetData();
if (Received.GetCRC() == CRC32(Received.GetMessage()))
{
    printf("Received CRC matches recomputed CRC");
}
```

You can also use the CRC function as a hash function,
which is useful if you're building a hash map or something
else that requires a hash (For example, Unreal Engine uses
CRC to hash various data structures inside TMaps).

```cpp
// Unreal Engine function that creates a
// hash value from an IntVector2 data
template<typename T>
uint32 GetTypeHash(const TIntVector2<T>& Vector)
{
	return FCrc::MemCrc32(&Vector, sizeof(Vector));
}
```

## Calculation

[CRC](https://en.wikipedia.org/wiki/Cyclic_redundancy_check) computation consists on calculating:


```math
remainder \left( \frac{d(x)}{g(x)} \right)=r(x)
```

Where:
```math
d(x)
```
Is a polynomial whose coefficients encode an arbitrary chunk of data, and:
```math
g(x)
```
Is a polynomial known as the divisor, generator or CRC polynomial. The degree of
the generator polynomial states the name of the CRC in use and also the max degree of:
```math
r(x)
```
For example, the following CRC polynomial is known as CRC16-CCITT:
```math
x^{16}+x^{12}+x^{5}+1
```

The coefficients of these polynomials can be only 1 or 0,
or more rigurously, these coefficients are elements of the underlying set of a [mathematical field](https://en.wikipedia.org/wiki/Field_(mathematics))
known as [GF(2)](https://en.wikipedia.org/wiki/GF(2)), coders can interpret this as fancy terminology to refer to boolean `true`, `false`, `XOR` and `AND`.

## Description of GF(2)

Underlaying set of the field is defined as:
```math
S=\{0, 1\}
```

Binary operations of the field are:
```math
\{+, *\}
```

The field is defined as:
```math
GF(2)=(S,+, *)
```

Intuitively it means that addition, subtraction, multiplication, and division
are defined and behave as the corresponding operations on rational and real numbers.

All the valid operations in GF(2) are:

| `A` | `B` | `A + B` | `A - B` |
| - | - | - | - |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |


Note above that subtraction and addition looks the same and is equivalent to the boolean XOR operation.

| `A` | `B` | `A * B` | `A / B` |
| - | - | - | - |
| 0 | 0 | 0 | Undefined |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | Undefined |
| 1 | 1 | 1 | 1 |

We conventionally state division by zero to be undefined, apart from that,
multiplication and division looks very similar and are equivalent to the boolean AND operation.

## Polynomials over GF(2)

Some example of operations between polynomials whose coefficients are elements of GF(2).

```math
x^2+x^2=(1+1)x^2=0x^2=0
```
```math
x^7-x^7=(1-1)x^7=0x^7=0
```

```math
x^2(x^3+x^2+1)=x^{3+2}+x^{2+2}+x^{0+2}=x^5+x^4+x^2
```
The following [github repo](https://github.com/romualdo97/CyclicRedundancyCheckPlayground/blob/main/Basic/Polynomial.cpp)
contains a toy C++ class to perform operations between polynomials over GF(2)
using a syntax similar to the one of math texts (Sacrificing performance as is intended only for small experimentation)
and it will be used in the following sections.

```cpp
Polynomial A = (1 * x{6} + 1 * x{ 0 }) * x{ 1 };
Polynomial B = x{ 7 } + x{ 1 };
Polynomial SumResult = SumA + SumB;
assert(SumResult == Polynomial::Zero);
```

## Polynomials to binary

With the tools previously described we can encode a polynomial using binary strings:
```math
x^3+x^1+1 \leftrightarrow (1011)
```
```math
x^2+1 \leftrightarrow (0101)
```
And perform polynomial operations using bitwise XOR and AND:
```math
(x^3+x^1+1)+(x^2+1) = x^3+x^1+x^2 \leftrightarrow 1011 \oplus 0101 = 1110
```

## CRC computation 1 bit at a time

This is based on the standard [long division](https://en.wikipedia.org/wiki/Long_division) algorithm taught in school,
where multiples of the divisor `g(x)` are subtracted from the dividend `d(x)`
until the remainder is of smaller degree than `g(x)`.

The following slide illustrates the computation of:

```math
remainder \left( \frac{x^3+x^2+1}{x^3+x+1} \right)
\leftrightarrow
remainder \left( \frac{1101}{1011} \right)
```

<Slider
  dots
  infinite
  speed={500}
  slidesToShow={1}
  slidesToScroll={1}
>
    <img src="/programmer-notes-on-crc-computation/simple/SimpleIteration0.svg" alt="SimpleIteration0" />
    <img src="/programmer-notes-on-crc-computation/simple/SimpleIteration1.svg" alt="SimpleIteration1" />
    <img src="/programmer-notes-on-crc-computation/simple/SimpleIteration2.svg" alt="SimpleIteration2" />
    <img src="/programmer-notes-on-crc-computation/simple/SimpleIteration3.svg" alt="SimpleIteration3" />
</Slider>

Let `n` be the degree of the `CRC` polynomial, in this case n=3, the algorithm above
consists on
- Load the first `(n + 1)` terms of the polynomial `d(x)`
- Subtract the `CRC` polynomial
- (1) Store the result
- (2) Left shift the result
- Subtract the `CRC` polynomial, repeat...
- Stop after 4 iterations because d(x) encodes a 4 bits long message

C++ example implementation below (see full source [code here](https://github.com/romualdo97/CyclicRedundancyCheckPlayground/blob/main/Basic/main.cpp)):

```cpp
Polynomial Message = x{3} + x{2} + x{0};
Polynomial Crc3 = x{3} + x{1} + x{0};

// Load n+1 bits of the message
// (we depend here on Message
// and CRC having the same degree,
// otherwise this is incorrect,
// read next examples for a demostration on how to handle
// message and CRC not having the same degree)
Polynomial Remainder = Message;
assert(Remainder.GetDegree() == Crc3.GetDegree());

for (size_t Counter = 0;
    Counter < Message.TotalTerms();
    ++Counter)
{
    if (Remainder.GetDegree() == Crc3.GetDegree())
    {
        Remainder = Remainder - Crc3;
    }

    // Left shift the remainder one bit
    Remainder = Remainder * x{ 1 };
}

return Remainder;
```

The above code won't work if the message has greater degree than the CRC polynomial,
next we will handle the loading of abitrary sized messages:

```cpp
// This example is based on
// https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Computation
Polynomial Crc3 = x{3} + x{1} + x{0};

// A message polynomial of degree 13, encoding 14 bits
PolynomialBitString Message{ 0b11'0100'1110'1100, 14 };

// Load first n bits of the message a.k.a 110
Polynomial Remainder =
    Polynomial::FromBitString(
        Message.Substring(Crc3.GetDegree())
    );

for (size_t Index = 0;
    Index < Message.TotalTerms();
    ++Index)
{
    Remainder =
        // Align remainder and CRC, e.g. make 110, to be 1100
        // so it has the same degree of CRC
        Remainder * x{ 1 }

        // Load the next bit of the message
        + Message[Crc3.GetDegree() + Index] * x{ 0 };

    // Subtract and update the remainder
    // if both polynomials share the same degree
    if (Remainder.GetDegree() == Crc3.GetDegree())
    {
        Remainder = Remainder - Crc3;
    }
}

return Remainder;
```

Note that we can ignore the term of degree n as it always
gets zeroed when subtracting the CRC from the Remainder.

The following example is the most used in hardware, it doesn't
requires preloading the first n bits of the message and only uses n registers to store
the result (instead of n + 1), to achive this, it leverages on the associative property of addition,
i.e. it performs the same additions per digit noted above, but in a distinct order,
continue reading for an illustrated explanation.

```cpp
// This example is based on
// https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Computation
Polynomial Crc3 = x{3} + x{1} + x{0};

// A message polynomial of degree 13, encoding 14 bits
PolynomialBitString Message{ 0b11'0100'1110'1100, 14 };

// No more need to load first n bits of the message
Polynomial Remainder = Polynomial::Zero();

for (size_t Index = 0;
    Index < Message.TotalTerms();
    ++Index)
{
    Remainder =
        // No more need of left shifting one bit
        Remainder

        // Load the next bit of the message
        + Message[Index] * x{ Crc3.GetDegree() - 1 };

    // Is the term n-1 at remainder 1? will the remainder
    // be aligned to the crc after one left shift?
    // 0110 (This will be aligned to CRC after one left shift)
    // 1011
    if (Remainder.GetDegree() == (Crc3.GetDegree() - 1))
    {
        // Each register of remainder will accumulate
        // the operations consider the first iteration:
        // r= x*1x^(n-1) = 1x^n
        // crc=            1x^n + x + 1
        // updated r=             x + 1
        // the terms x and 1 will eventually be subtracted
        // from a new loaded bit
        Remainder = Remainder * x{ 1 } - Crc3;
    }
    else
    {
        // Shift left everything if loaded n-1 term was zero
        Remainder = Remainder * x{ 1 };
    }
}

return Remainder;
```

Below is an illustrated step by step debugging of the above algorithm, each bit
has an identifier tracking when was it read for first time so you can track
the order of operations.


<Slider
  dots
  infinite
  speed={500}
  slidesToShow={1}
  slidesToScroll={1}
>
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration0.a.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration0.b.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration0.c.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration1.a.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration1.b.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration1.c.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration2.a.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration2.b.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration2.c.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration3.a.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration3.b.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIteration3.c.svg" />
    <img src="/programmer-notes-on-crc-computation/hardware/AdvancedCrcIterationResult.svg" />
</Slider>

For more credibility compare the above graphic with all the operations "expected" to happen on each digit
in the first algorithm studied.

```cpp
Iteration 0
                result bits
1   1   0   1   0   0   0   =   d(x)
1   0   1   1               =   g(x)
1+1 1+0 0+1 1+1                 operations at iteration 0

Iteration 1
                result bits
0   1   1   0   0   0   0   =   d(x)
    1   0   1   1           =   g(x)
1+1 1+0 0+1 1+1                 operations at iteration 0
    1+1 1+0 0+1 0+1             operations at iteration 1

Iteration 2
                result bits
0   0   1   1   1   0   0   =   d(x)
        1   0   1   1       =   g(x)
1+1 1+0 0+1 1+1                 operations at iteration 0
    1+1 1+0 0+1 0+1             operations at iteration 1
        1+1 1+0 1+1 0+1         operations at iteration 2

Iteration 3
                result bits
0   0   0   1   0   1   0   =   d(x)
            1   0   1   1   =   g(x)
1+1 1+0 0+1 1+1                 operations at iteration 0
    1+1 1+0 0+1 0+1             operations at iteration 1
        1+1 1+0 1+1 0+1         operations at iteration 2
            1+1 0+0 1+1 0+1     operations at iteration 3

Which expands to:
digit 6 = 1+1
digit 5 = (1+0)+1
digit 4 = ((0+1)+0)+1
digit 3 = ((((1+1)+1)+0)+1)
digit 2 = (((0+1)+1)+0)
digit 1 = ((0+1)+1)
digit 0 = (0+1)

Where digit 2, 1 and 0 conform the result.
```

Next example uses bitwise operators directly to removes
usage of the class Polynomial.

```cpp
// Binary message
// 00010000 00010001 00010010 00010011
// 00010100 00010101 00010110 00010111
constexpr uint8_t Message[] {
        0x10, 0x11, 0x12, 0x13,
        0x14, 0x15, 0x16, 0x17
    };

// Most significant bit first (big-endian),
// note that the x power n bit is ignored,
// aka the coefficient of the msb bit
// (x16)+x12+x5+1 = (1) 0001 0000 0010 0001 = 0x1021
constexpr uint32_t Crc = 0x1021;
constexpr uint32_t CrcN = 16;

// Result of the CRC function
uint32_t Remainder = 0;

for (uint8_t MessageByte : Message)
{
    // Load the next byte and
    // Align the byte with the generator
    // polynomial e.g. make 0x12 to be 0x1200 so
    // it represents a polynomial of degree n-1
    uint32_t MessageByteShifted = MessageByte << 8;

    // Calculate the remainder
    Remainder = Remainder ^ MessageByteShifted;

    // Process the next 8 bits
    for (uint32_t BitIndex = 0; BitIndex < 8; ++BitIndex)
    {
        // Check the coefficient of polynomial n-1,
        // i.e. 1000 0000 0000 0000
        if (Remainder & 0x8000)
        {
            Remainder = (Remainder << 1) ^ Crc;
        }
        else
        {
            Remainder = Remainder << 1;
        }
    }

    // We need to mask 16bits on the remainder because we are ignoring the n coefficient of the crc polynomial
    // so we are not guaranteeing the n coefficient at remainder and crc to cancel each other
    Remainder = Remainder & 0xffff;
}

return Remainder;
```

If we encode the polynomial coefficients using a LSB endianess the code simplifies to:

```cpp
// Binary message
// 00010000 00010001 00010010 00010011
// 00010100 00010101 00010110 00010111
constexpr uint8_t Message[] {
        0x10, 0x11, 0x12, 0x13,
        0x14, 0x15, 0x16, 0x17
    };

// Least significant bit first (little-endian)
// 1+x5+x12+(x16) = 1000 0100 0000 1000 (1) = 0x8408
constexpr uint32_t Crc = 0x8408;
constexpr uint32_t CrcN = 16;

// Result of the CRC function
uint32_t Remainder = 0;

for (uint8_t MessageByte : Message)
{
    // Calculate the remainder
    Remainder = Remainder ^ MessageByte

    // Process the next 8 bits
    for (uint32_t BitIndex = 0; BitIndex < 8; ++BitIndex)
    {
        // Check the coefficient of polynomial n-1, i.e. 0000 0001
        if (Remainder & 0x1)
        {
            Remainder = (Remainder >> 1) ^ Crc;
        }
        else
        {
            Remainder = Remainder >> 1;
        }
    }
}
```

## CRC computation using Dilip V. Sarwate algorithm

Sarwate's algorithm consists of a table
containing 256 rows where each element represents the remainder
of a polynomial division:

```math
remainder \left( \frac{T_p(x)}{g(x)} \right)=r(x)
```

Such that:

```math
0 \leq p \leq255
```

And:

```math
T_p(x)=i_7x^7 + i_6x^6 + ... + i_2x^2 + i_1x^1 + i_0x^0
```
Where:
```math
DecimalToBinary(p) = (i_7,i_6,i_5,i_4,i_3,i_2,i_1,i_0)
```

This way, if we wanted to calculate the remainder of:

```math
remainder \left( \frac{x^6+x^4+x^3+x+1}{g(x)} \right)=r(x)
```

We would only need to look-up an entry from a table T.

```math
x^6+x^4+x^3+x+1 \leftrightarrow 0b01011011 \leftrightarrow 91
```
```math
remainder \left( \frac{T_{91}(x)}{g(x)} \right)=F[91]
```

Next example shows how to compute a CRC16 from a 4 bytes long message.

```cpp
Iteration                                                                           Result bytes
            A3          A2              A1                      A0                  A{-1}           A{-2}
0:          T=A3        C1=F1[T]        C0=F0[T]
1:                      T=C1+A2         C1=C0+F1[T]             C0=F0[T]
1:                                      T=C1+A1                 C1=C0+F1[T]         C0=F0[T]
1:                                                              T=C1+A0             C1=C0+F1[T]     C0=F0[T]
```

In the above example consider that only one byte is loaded from the message at a time, e.g.
at iteration 0 only A3 is loaded, at iteration 1 only A2 and so on.

For a detailed explanation on how to generate the table `F[T]` please refer to appendix at [Sarwate's paper](https://dl.acm.org/doi/pdf/10.1145/63030.63037).

## Further lecture

Sarwate's work was [extendend](https://static.aminer.org/pdf/PDF/000/432/446/a_systematic_approach_to_building_high_performance_software_based_crc.pdf) by Kounavis and Berry to perform 4 bytes and 8 bytes per iteration,
this is the most performant software implementation so far and is widely used in a lot of mainstream systems like
the [Linux kernel](https://www.kernel.org/doc/Documentation/crc32.txt) and [Unreal Engine (Requires access to the github repo)](https://github.com/EpicGames/UnrealEngine/blob/release/Engine/Source/Runtime/Core/Private/Misc/Crc.cpp).

Check the slide by 8 implementation used by Unreal with a lot of extra comments [here](https://github.com/romualdo97/CyclicRedundancyCheckPlayground/blob/main/SlideByEight/Crc.cpp)

## Links

- [How do CRCs work? By Ben Eater](https://www.youtube.com/watch?v=izG7qT0EpBw&t=1864s)
- [Computation of cyclic redundancy checks via table look-up By Dilip V. Sarwate](https://dl.acm.org/doi/pdf/10.1145/63030.63037)
- [A systematic approach to building high performance, software based, CRC generators By Michael E. Kounavis and Frank L. Berry](https://static.aminer.org/pdf/PDF/000/432/446/a_systematic_approach_to_building_high_performance_software_based_crc.pdf)
- [Online CRC calculator by Bastian Molkenthin](https://www.sunshine2k.de/coding/javascript/crc/crc_js.html)
- [Understanding CRC by Bastian Molkenthin](https://www.sunshine2k.de/articles/coding/crc/understanding_crc.html)
- [CRC Playground in C++ by Romualdo Villalobos](https://github.com/romualdo97/CyclicRedundancyCheckPlayground/)
- [CRC documentation at Kernel.org](https://www.kernel.org/doc/Documentation/crc32.txt)
- [CRC Unreal Source Code At Github](https://github.com/EpicGames/UnrealEngine/blob/release/Engine/Source/Runtime/Core/Private/Misc/Crc.cpp)
- [Cyclic redundancy check at Wikipedia](https://en.wikipedia.org/wiki/Cyclic_redundancy_check)
- [Computation of cyclic redundancy checks at Wikipedia](https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks)
- [Algebra group at Wikipedia](https://en.wikipedia.org/wiki/Group_(mathematics))
- [Algebra field at Wikipedia](https://en.wikipedia.org/wiki/Field_(mathematics))
- [Field GF(2) at Wikipedia](https://en.wikipedia.org/wiki/GF(2))
- [Long division at Wikipedia](https://en.wikipedia.org/wiki/Long_division)

## Credits
Written by [Romualdo Villalobos](https://www.linkedin.com/in/romualdo-villalobos/)

</ProseBlock>


Notes on different techniques used to calculate and implement a cyclic redundancy check generator

Programmer notes on CRC computation


<ProseBlock>

## Descriptor:

Describes a resource to the GPU such as a buffer, image or sampler, is an opaque data structure representing a shader resource. Descriptors are organized into descriptor sets, which are bound during command recording for use in subsequent drawing commands.
<br></br>

</ProseBlock>

<img src="/vulkan-descriptor-set-cheat-sheet/image1_descriptor.svg" alt="Image1: Example of a descriptor that describes or represents a buffer object." />

<ProseBlock>

_Image 1: Example of a descriptor that "describes" or "represents" a buffer object._


### References:
- [Direct3D 12 Descriptor Overview](https://learn.microsoft.com/en-us/windows/win32/direct3d12/descriptors-overview)
- [Vulkan Resource Descriptors](https://docs.vulkan.org/spec/latest/chapters/descriptorsets.html)
- [Structure VkDescriptorBufferInfo](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorBufferInfo.html)
- [Function vkBindBufferMemory](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/vkBindBufferMemory.html)

---

## Pipelines and Descriptors:

Different stages of a pipeline access arbitrary resources like Buffers, Images or Samplers through descriptors.

<br></br>

</ProseBlock>

<img src="/vulkan-descriptor-set-cheat-sheet/image2_pipelines_and_descriptors.svg" alt="Image2: Graphic Pipeline (1) reads buffer A at Vertex and Fragment stage and reads buffer B at Vertex stage; Compute Pipeline (2) reads buffer B at Compute stage; Compute Pipeline (3) reads image C, sampler D and uniform buffer E at Compute stage." />

<ProseBlock>

_Image 2: Graphic Pipeline (1) reads buffer A at Vertex and Fragment stage and reads buffer B at Vertex stage; Compute Pipeline (2) reads buffer B at Compute stage; Compute Pipeline (3) reads image C, sampler D and uniform buffer E at Compute stage._

### References:
- [The Vulkan Pipeline Vulkan](https://docs.vulkan.org/tutorial/latest/11_Compute_Shader.html#_the_vulkan_pipeline)
- [Enum VkDescriptorType](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorType.html)

---

## Descriptor Sets:

A pipeline cannot access a descriptor individually, we need to group them in sets.
<br></br>

</ProseBlock>

<img src="/vulkan-descriptor-set-cheat-sheet/image3_descriptor_sets.svg" alt="Image3: Some shader stages at Graphic Pipeline (1) read from set A while also read and write from set B; shader at Compute Pipeline (2) reads and writes from set B; shader at Compute Pipeline (3) reads and writes from set B." />

<ProseBlock>

_Image 3: Some shader stages at Graphic Pipeline (1) read from set A while also read and write from set B; shader at Compute Pipeline (2) reads and writes from set B; shader at Compute Pipeline (3) reads and writes from set B._

You define how many and what type of descriptors a set will have (layout of the set) using a [VkDescriptorSetLayout](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorSetLayout.html) object.

<br></br>
</ProseBlock>

<img src="/vulkan-descriptor-set-cheat-sheet/image4_descriptor_sets_2.svg" alt="Image4: Two descriptor sets describing different resources." />

<ProseBlock>

_Image 4: Two descriptor sets describing different resources._

A descriptor set is structured as a sequence of slots known as bindings, each binding represents a single type of descriptor, for instance buffer, image, sampler, etc… A binding also defines how many descriptors of the given type will be available at a given slot and on what pipeline stages the described resources will be accessible, see [Structure VkDescriptorSetLayoutCreateInfo](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorSetLayoutCreateInfo.html).

### References:
- [Structure VkDescriptorSetLayoutCreateInfo](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorSetLayoutCreateInfo.html)
- [Handle VkDescriptorSetLayout](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorSetLayout.html)
- [Storage buffers](https://vkguide.dev/docs/chapter-4/storage_buffers/)

---

## Allocating a Descriptor Set:

You allocate descriptor sets from a pool of descriptors.

<br></br>
</ProseBlock>

<img src="/vulkan-descriptor-set-cheat-sheet/image5_allocating_a_descriptor_set.svg" alt="Image5: A descriptor pool with 12 descriptors, 3 of type image, 7 of type buffer and 2 of type sampler." />

<ProseBlock>

_Image 5: A descriptor pool with 12 descriptors, 3 of type image, 7 of type buffer and 2 of type sampler._

When creating a descriptor pool you indicate how many descriptors the pool will have and the max amount of descriptor sets that can take descriptors from the pool.

### References:
- [Handle VkDescriptorPool](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorPool.html)
- [Structure VkDescriptorPoolCreateInfo](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorPoolCreateInfo.html)

---

## Pipeline Layout:

The pipeline layout defines what descriptors are accessible from a given pipeline.

<br></br>
</ProseBlock>

<img src="/vulkan-descriptor-set-cheat-sheet/image6_pipeline_layout.svg" alt="Image6: A pipeline layout defining what descriptor sets are accessible from the pipeline." />

<ProseBlock>

_Image 6: A pipeline layout defining what descriptor sets are accessible from the pipeline._

The pipeline layout represents a sequence of descriptor sets with each having a specific descriptor set layout.

### References:
- [Handle VkPipelineLayout](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkPipelineLayout.html)
- [Structure VkPipelineLayoutCreateInfo](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkPipelineLayoutCreateInfo.html)
- [Structure VkGraphicsPipelineCreateInfo](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkGraphicsPipelineCreateInfo.html)

---

## Making Descriptors point to Resources:

Descriptors can be thought as some kind of pointers to resources. To update a descriptor so it points and represents an actual resource you use the [function vkUpdateDescriptorSets](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/vkUpdateDescriptorSets.html).

<br></br>
</ProseBlock>

<img src="/vulkan-descriptor-set-cheat-sheet/image7_making_descriptors_point_to_resources.svg" alt="Image7: A set with a single descriptor that is being updated to identify an actual buffer resource." />

<ProseBlock>

_Image 7: A set with a single descriptor that is being updated to identify an actual buffer resource._

### References:
- [Function vkUpdateDescriptorSets](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/vkUpdateDescriptorSets.html)

---
## Using pipelines and descriptor sets:

Once you have a pipeline and a descriptor set you can bind them together for actual usage in the pipeline with the [function vkCmdBindDescriptorSets](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/vkUpdateDescriptorSets.html).

### References:
- [Function vkCmdBindDescriptorSets](https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/vkUpdateDescriptorSets.html)

---

## Code Example | Creating descriptors:

### Creating a descriptor set layout:

```cpp
// Binding 0 will describes 1 uniform buffer
const VkDescriptorSetLayoutBinding BindingDescription
{
  .binding = 0,
  .descriptorType = VK_DESCRIPTOR_TYPE_UNIFORM_BUFFER,
  .descriptorCount = 1,
  .stageFlags = VK_SHADER_STAGE_VERTEX_BIT,
  .pImmutableSamplers = nullptr
};

// The layout of a DescriptorSet that contains a single Descriptor  
const VkDescriptorSetLayoutCreateInfo DescriptorSetLayoutCreateInfo
{
  .sType = VK_STRUCTURE_TYPE_DESCRIPTOR_SET_LAYOUT_CREATE_INFO,
  .pNext = nullptr,
  .flags = 0,
  .bindingCount = 1,
  .pBindings = &BindingDescription
};

// Handle to a descriptor set layout object
VkDescriptorSetLayout DescriptorSetLayout;

// Create the descriptor set layout
if (vkCreateDescriptorSetLayout(
  DeviceHandle, // VkDevice                                    
  &DescriptorSetLayoutCreateInfo, // VkDescriptorSetLayoutCreateInfo
  nullptr, // VkAllocationCallbacks
  &DescriptorSetLayout) != VK_SUCCESS)
{
  assert(false);
}
```

### Creating a descriptor pool:
```cpp
// The amount of `Descriptors` representing `Uniform Buffers` in the descriptor pool
const VkDescriptorPoolSize DescriptorPoolSize
{
  .type = VK_DESCRIPTOR_TYPE_UNIFORM_BUFFER,
  .descriptorCount = 1
};

// Create info for the descriptor pool
const VkDescriptorPoolCreateInfo DescriptorPoolCreateInfo
{
  .sType = VK_STRUCTURE_TYPE_DESCRIPTOR_POOL_CREATE_INFO,
  .pNext = nullptr,
  .flags = 0,
  .maxSets = 1, // Max DescriptorSets allocatable from this pool
  .poolSizeCount = 1,
  .pPoolSizes = &DescriptorPoolSize
};

// Handle to the descriptor pool object
VkDescriptorPool DescriptorPool;

// Create the descriptor pool
if (vkCreateDescriptorPool(
  DeviceHandle, // VkDevice
  &DescriptorPoolCreateInfo, // VkDescriptorPoolCreateInfo
  nullptr, // VkAllocationCallbacks
  &DescriptorPool) != VK_SUCCESS)
{
  assert(false);
}
```

### Allocating a descriptor set

```cpp
// Create info for the DescriptorSet
const VkDescriptorSetAllocateInfo DescriptorSetAllocateInfo
{
    .sType = VK_STRUCTURE_TYPE_DESCRIPTOR_SET_ALLOCATE_INFO,
    .pNext = nullptr,
    .descriptorPool = DescriptorPool,
    .descriptorSetCount = 1,
    .pSetLayouts = &DescriptorSetLayout
};

// Handle to the DescriptorSet object
VkDescriptorSet DescriptorSet;

if (vkAllocateDescriptorSets(
  DeviceHandle, // VkDevice
  &DescriptorSetAllocateInfo, // VkDescriptorSetAllocateInfo
  &DescriptorSet) != VK_SUCCESS)
{
    assert(false);
}
```

### Making descriptors point to resources:

```cpp
// https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkDescriptorBufferInfo.html
VkDescriptorBufferInfo DescriptorBufferInfo
{
  .buffer = MyUniformBufferHandle, // VkBuffer
  .offset = 0, // offset
  .range = VK_WHOLE_SIZE // from offset to end of buffer
};

// https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/VkWriteDescriptorSet.html
const VkWriteDescriptorSet WriteDescriptorSet
{
  .sType = VK_STRUCTURE_TYPE_WRITE_DESCRIPTOR_SET,
  .pNext = nullptr,
  .dstSet = DescriptorSet,
  .dstBinding = 0,
  .dstArrayElement = 0,
  .descriptorCount = 1,
  .descriptorType = VK_DESCRIPTOR_TYPE_UNIFORM_BUFFER,
  .pImageInfo = nullptr,
  .pBufferInfo = &DescriptorBufferInfo,
  .pTexelBufferView = nullptr
};

// https://registry.khronos.org/vulkan/specs/1.3-extensions/man/html/vkUpdateDescriptorSets.html
vkUpdateDescriptorSets(
  DeviceHandle, // VkDevice
  1, // descriptorWriteCount
  &WriteDescriptorSet, // VkWriteDescriptorSet
  0, // descriptorCopyCount
  nullptr); // VkCopyDescriptorSet
```

---

## Code Example | Making descriptors accesible in a pipeline:

### Creating a pipeline layout:

```cpp
// A pipeline layout representing
// a pipeline that has access
// to a single descriptor set
const VkPipelineLayoutCreateInfo PipelineLayoutCreateInfo
{
  .sType = VK_STRUCTURE_TYPE_PIPELINE_LAYOUT_CREATE_INFO,
  .pNext = nullptr,
  .flags = 0,

  .setLayoutCount = 1,
  .pSetLayouts = &DescriptorSetLayout,

  .pushConstantRangeCount = 0,
  .pPushConstantRanges = nullptr
};

// Handle to the new pipeline layout object
VkPipelineLayout PipelineLayout;

if (vkCreatePipelineLayout(
  DeviceHandle, // VkDevice
  &PipelineLayoutCreateInfo, // VkPipelineLayoutCreateInfo
  nullptr, // VkAllocationCallbacks
  &PipelineLayout) != VK_SUCCESS)
{
  assert(false);
}
```

### Creating a pipeline:

```cpp
// Create info for the pipeline
const VkGraphicsPipelineCreateInfo PipelineCreateInfo
{
  .sType = VK_STRUCTURE_TYPE_GRAPHICS_PIPELINE_CREATE_INFO,

  // more code...

  .layout = PipelineLayout

  // more code...
}

// Handle to the graphics pipeline object
VkPipeline GraphicsPipeline;

if (vkCreateGraphicsPipelines(
  /* more code... */
  &PipelineCreateInfo,
  /* more code... */
  GraphicsPipeline) != VK_SUCCESS)
{
  assert(false);
}
```

## Code Example | Using descriptors:

### Shader code

```cpp
// This shader requires a pipeline that has a uniform buffer at set 0 -> binding 0
layout(set = 0, binding = 0) uniform MyUniformBufferData
{
    mat4 Foo;
    mat4 Var;
    mat4 Zas;
    mat4 Boo;
} uMyUniformBufferData;
```

### Binding descriptors with an actual pipeline

```cpp
// Bind DescriptorSet to any GRAPHIC pipeline
vkCmdBindDescriptorSets(
  CommandBufferHandle,

  VK_PIPELINE_BIND_POINT_GRAPHICS, // Type of the pipeline that will use the descriptors
  PipelineLayout, // The pipeline layout

  /* more code... */

  1, // How many descriptor sets to bind?
  &DescriptorSet,

  /* more code... */);

// In this example subsequent commands
// that interact with a pipeline of GRAPHICS type 
// will have access to the bound descriptors

```
---

## Further lectures

- [Vulkan Docs | Descriptor Indexing](https://docs.vulkan.org/samples/latest/samples/extensions/descriptor_indexing/README.html)
- [DethRaid | How do you “descriptor set”?](https://gist.github.com/NotAPenguin0/284461ecc81267fa41a7fbc472cd3afe)
- [ChunkStories.xyz | A note on Descriptor Indexing](https://chunkstories.xyz/blog/a-note-on-descriptor-indexing/)
- [Vulkan Docs | Descriptor and Buffer management](https://docs.vulkan.org/samples/latest/samples/performance/descriptor_management/README.html)
- [Gasim Gasimzada | Managing bindless descriptors in Vulkan](https://dev.to/gasim/implementing-bindless-design-in-vulkan-34no)
- [Wicked Engine | Bindless Descriptors](https://wickedengine.net/2021/04/bindless-descriptors/)
- [The Khronos Group | Bringing Fortnite to Mobile with Vulkan and OpenGL ES - GDC 2019]()
- [Adrian Courreges | GTA V Graphics Study](https://www.adriancourreges.com/blog/2015/11/02/gta-v-graphics-study/)
- [Adrian Courreges | Doom 2016 Graphics Study](https://www.adriancourreges.com/blog/2016/09/09/doom-2016-graphics-study/)

## Credits
Written by [Romualdo Villalobos](https://www.linkedin.com/in/romualdo-villalobos/)

</ProseBlock>


An illustrated glossary and mental model of Vulkan's descriptor sets, their setup and relation with other entities like pipelines, layouts, buffers, etc...

Vulkan Descriptor Sets cheat sheet


<ProseBlock>

[Previously](https://rawsourcecode.io/posts/unreal-delegates-under-the-hood) we dived into Unreal `TDelegate` class by writing a simple and incomplete [minimalist clone](https://gist.github.com/romualdo97/9482b924bab9644cbe914f92b607e670) of Unreal Unicast Delegate.

Today we aim to expand previous knowledge of `TDelegate`s with some additional graphics and insightful info for anyone interested in diving deeper into the inner workings of Delegates.

For a comprehensive and introductory explanation of different kinds of delegates present in Unreal, please check this [nice article from BenUI](https://benui.ca/unreal/delegates-intro/).

---

## What is class TDelegate?

Roughly speaking It’s the _templated class_ that holds a pointer to something that you can invoke _i.e. a callable type like a lambda expression, an object method, a free function, etc.._

A `TDelegate` uses a helper object that implements the interface `IDelegateInstance` to store this data.

<img src="/unreal-delegates-under-the-hood-part-2/TDelegateBasicStructure.svg" alt="Figure1: TDelegate Basic Structure" />

_Figure1: `TDelegate` Basic Structure_

---

## TDelegate default policy

In [Generic Programming](https://en.wikipedia.org/wiki/Generic_programming#:~:text=Generic%20programming%20is%20a%20style,specific%20types%20provided%20as%20parameters.) a policy allows you to configure the behavior of a specific generic type at compile time. Please check the following references for more information.

> A policy is a class or class template that defines an interface as a service to other classes.
>> [Computer Science Presentation at Karlsruhe Institute of Technology](https://wiki.scc.kit.edu/gridkaschool/upload/8/87/5MorePatterns.pdf)

> A policy is a generic function or class whose behavior can be configured [... at compile time]
>> [Rainer Grimm at modernescpp.org](https://www.modernescpp.org/)

We find that `TDelegate` can be configured using a _default policy_ named [`FDefaultDelegateUserPolicy`](https://docs.unrealengine.com/4.26/en-US/API/Runtime/Core/Delegates/FDefaultDelegateUserPolicy/) which defines the following type aliases. (We simple users don't care about this, right?).

### FDelegateInstanceExtras
```cpp
using FDelegateInstanceExtras = IDelegateInstance;
```

A [type alias](https://en.cppreference.com/w/cpp/language/type_alias) to a class that publicly inherits the interface `IDelegateInstance`, classes that implement this interface are responsible for holding any relevant data necessary to invoke a delegate _e.g. pointer to objects, function pointers, function names etc._


### FDelegateExtras
```cpp
using FDelegateExtras = TDelegateBase<FThreadSafetyMode>;
```

A [type alias](https://en.cppreference.com/w/cpp/language/type_alias) to a class that publicly inherits the class `TDelegateBase` and holds an instance of a class that derives `IDelegateInstance`. 

### FMulticastDelegateExtras

Similar to `FDelegateExtra` but for _Multicast Delegates_, let’s ignore for now.

### FThreadSafetyMode

Used to synchronize the access to _delegate internal_ data in a _multithreaded environment_, let’s ignore for now.

This _policy_ is used mainly to configure the _inheritance relationship_ of classes shown previously at _Figure 1_
<img src="/unreal-delegates-under-the-hood-part-2/TDelegateInheritanceDiagram.svg" alt="Figure1: TDelegate Inheritance diagram overview" />

_Figure2: `TDelegate` Inheritance diagram overview_

For the default user policy this translates to `TDelegate` -> *extends* -> `TDelegateBase` -> *owns/composes* -> `IBaseDelegateInstance` -> *extends* -> `IDelegateInstance`.

### IDelegateInstance vs IBaseDelegateInstance

`IDelegateInstance` defines the interface to fetch useful info like the _UObject a delegate instance is bound to, a pointer to the associated method pointer or a bool indicating safety of executing the delegate instance_, on the other hand `IBaseDelegateInstance` describes the _interface to execute a delegate instance_
<img src="/unreal-delegates-under-the-hood-part-2/IDelegateInstanceInterface.svg" alt="IDelegateInstanceInterface" />

<img src="/unreal-delegates-under-the-hood-part-2/IBaseDelegateInstanceInterface.svg" alt="IBaseDelegateInstanceInterface" />

### Jargon challenge

Typically member functions in `UserPolicy::FDelegateExtras` (e.g. `TDelegateBase`) and its _derived classes_ will forward calls to the inner `UserPolicy::FDelegateInstanceExtras` class (e.g. `IDelegateInstance`) by downcasting the result of a call to `TDelegateBase::GetDelegateInstanceProtected()`.

For example check how `TDelegate` (which extends from `TDelegateBase`) downcasts its owned `IDelegateInstance` to `IBaseDelegateInstance` in order to execute the delegate.

```cpp
/**
* Execute the delegate.
*
* If the function pointer is not valid,
* an error will occur.
* Check IsBound() before
* calling this method or
* use ExecuteIfBound() instead.
*
* @see ExecuteIfBound
*/
FORCEINLINE RetValType
Execute(ParamTypes... Params) const
{
  FReadAccessScope ReadScope = GetReadAccessScope();

  // The following method down-casts from 
  // IDelegateInstance to IBaseDelegateInstance

  const DelegateInstanceInterfaceType*
  LocalDelegateInstance = GetDelegateInstanceProtected();

  // Where DelegateInstanceInterfaceType is:
  // using DelegateInstanceInterfaceType = typedef IBaseDelegateInstance/*...*/;

  // If this assert goes off, Execute() was called before a function was bound to the delegate.
  // Consider using ExecuteIfBound() instead.
  checkSlow(LocalDelegateInstance != nullptr);

  // Use the interface to invoke the associated callable
  return LocalDelegateInstance->Execute(Forward<ParamTypes>(Params)...);
}

```

## Concrete IBaseDelegateInstance implementations:

<h3 id="TBaseStaticDelegateInstance">class TBaseStaticDelegateInstance</h3>

Holds a pointer to _free function_ or _static member function_

<img src="/unreal-delegates-under-the-hood-part-2/TBaseStaticDelegateInstance.svg" alt="TBaseStaticDelegateInstance" />

<h3 id="TBaseRawMethodDelegateInstance">class TBaseRawMethodDelegateInstance</h3>

Holds a pointer to a _raw C++ object_ (instance of class that doesn’t have the `UOBJECT` declaration) and a pointer to a _member function in the object_.

<img src="/unreal-delegates-under-the-hood-part-2/TBaseRawMethodDelegateInstance.svg" alt="TBaseRawMethodDelegateInstance" />

<h3 id="TBaseFunctorDelegateInstance">class TBaseFunctorDelegateInstance</h3>

Holds a _functor object_.

<img src="/unreal-delegates-under-the-hood-part-2/TBaseFunctorDelegateInstance.svg" alt="TBaseFunctorDelegateInstance" />

<h3 id="TWeakBaseFunctorDelegateInstance">class TWeakBaseFunctorDelegateInstance</h3>

Holds a _functor object_ and a [weak object pointer](https://dev.epicgames.com/community/learning/tutorials/kx/unreal-engine-all-about-soft-and-weak-pointers) that will be used to define the _safety of invoking_ the associated functor object.

<img src="/unreal-delegates-under-the-hood-part-2/TWeakBaseFunctorDelegateInstance.svg" alt="TWeakBaseFunctorDelegateInstance" />

<h3 id="TBaseSPMethodDelegateInstance">class TBaseSPMethodDelegateInstance</h3>

Holds a [weak pointer](https://forums.unrealengine.com/t/difference-between-tweakptr-and-tweakobjectptr/331467) to a _raw C++ object_ or _class derived from [`TSharedFromThis`](https://docs.unrealengine.com/4.26/en-US/API/Runtime/Core/Templates/TSharedFromThis/)_ and a pointer to a _member function in the object_.

<img src="/unreal-delegates-under-the-hood-part-2/TBaseSPMethodDelegateInstance.svg" alt="TBaseSPMethodDelegateInstance" />

<h3 id="TBaseUFunctionDelegateInstance">class TBaseUFunctionDelegateInstance</h3>

Holds a [weak object pointer](https://dev.epicgames.com/community/learning/tutorials/kx/unreal-engine-all-about-soft-and-weak-pointers) and an `FName` of a _function declared with `UFUNCTION`_, also stores a _cache to the associated `UFunction`_.

<img src="/unreal-delegates-under-the-hood-part-2/TBaseUFunctionDelegateInstance.svg" alt="TBaseUFunctionDelegateInstance" />

<h3 id="TBaseUObjectMethodDelegateInstance">class TBaseUObjectMethodDelegateInstance</h3>

Holds a [weak object pointer](https://dev.epicgames.com/community/learning/tutorials/kx/unreal-engine-all-about-soft-and-weak-pointers) and a _pointer to a member function in the `UObject`_.

<img src="/unreal-delegates-under-the-hood-part-2/TBaseUObjectMethodDelegateInstance.svg" alt="TBaseUObjectMethodDelegateInstance" />

## How to create distinct delegate instances?

`TDelegate` exposes the _public interface_ of the _Unicast Delegate API_ and exposes two kind of functions to instance concrete `IBaseDelegateInstance` objects (described above), the first one are static functions with prefix `Create`, these are used to _instance/construct_ a `TDelegate` object and bind the callable _(e.g. function pointer, functor, etc..)_ into the inner `IDelegateInstance`.

The second family uses a prefix `Bind` on the function name, aren’t static and are used to change the callable bound to a `TDelegate` object or to bind a callable into `TDelegate` later in user code _(very useful when you write a function that receives a default callback delegate)_.

So in summary:

| `Create` prefix | `Bind` prefix |
| ------ | ------------------------------------------------------------------------- |
| Static function member. | Non static function member. | Non static function member |
| Instances a `TDelegate` and binds a callable into it. | Binds a callable into an existing `TDelegate` object. |
| Can be used to instance all concrete `IBaseDelegateInstance` classes. | Can be used to instance all concrete `IBaseDelegateInstance` classes. |

All the `Create`/`Bind` functions are:

| `Create` prefix | `Bind` prefix | Concrete `IBaseDelegateInstance` |
| ------ | ------ | ------ |
| `CreateStatic` | `BindStatic` | [`TBaseStaticDelegateInstance`](#TBaseStaticDelegateInstance) |
| `CreateLambda` | `BindLambda` | [`TBaseFunctorDelegateInstance`](#TBaseFunctorDelegateInstance) |
| `CreateWeakLambda` | `BindWeakLambda` | [`TWeakBaseFunctorDelegateInstance`](#TWeakBaseFunctorDelegateInstance) |
| `CreateRaw` | `BindRaw` | [`TBaseRawMethodDelegateInstance`](#TBaseRawMethodDelegateInstance) |
| `CreateSP` | `BindSP` | [`TBaseSPMethodDelegateInstance`](#TBaseSPMethodDelegateInstance) |
| `CreateUFunction` | `BindUFunction` | [`TBaseUFunctionDelegateInstance`](#TBaseUFunctionDelegateInstance) |
| `CreateUObject` | `BindUObject` | [`TBaseUObjectMethodDelegateInstance`](#TBaseUObjectMethodDelegateInstance) |

---

## Final comments:
With this we finish our reduced study on _implementation details_ of `TDelegate` public API, next we’ll start taking a look into the _payload system_, _thread safety_ and _memory management_ of these objects and will eventually expand into the _Multicast Delegates_ which in essence are only a plain array of `TDelegate` objects.

## Links

- [Difference between TWeakPtr and TWeakObjectPtr?](https://forums.unrealengine.com/t/difference-between-tweakptr-and-tweakobjectptr/331467)
- [Unreal delegates](https://docs.unrealengine.com/4.27/en-US/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Delegates/)
- [Policy and traits](https://stackoverflow.com/questions/14718055/what-is-the-difference-between-a-trait-and-a-policy)

## Credits
Written by [Romualdo Villalobos](https://www.linkedin.com/in/romualdo-villalobos/)

</ProseBlock>


More insight into the general structure and architecture of Unreal Delegate System internals.

Unreal delegates under the hood - Part II


<ProseBlock>

[Delegate](https://docs.unrealengine.com/4.27/en-US/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Delegates/) systems are central part
in software development, they allow decoupling between distinct components on nicely architected programs and show up naturally when
talking about events, event emitters, the observer pattern and more.

Today we aim to understand how Unreal implements its [delegate](https://docs.unrealengine.com/4.27/en-US/API/Runtime/Core/Delegates/TDelegate/) system
under the hood by building our own delegate clone class which will hold/bind references to member
functions of *raw C++ objects* and *free functions* on a uniform and type-safe way easy to extend.

> Unreal can also hold references to member functions of `UObject` objects, `Lambda/Functors` and `Shared Pointers`.

We intentionally exclude Unreal sophisticated memory handling and other details like the [bound payload](https://docs.unrealengine.com/4.27/en-US/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Delegates/#payloaddata)
in order to focus our attention to class hierarchies, template specializations and general structure.

---

## Part 1: IBaseDelegateInstance

Abstract class representing a "pointer holder", distinct type of pointers (free, member functions) will extend from this class.

Note that `IBaseDelegateInstance` is a [forward declared templated class](https://stackoverflow.com/questions/13848451/how-to-forward-declare-a-c-template-class).

```cpp
template <typename FuncType>
struct IBaseDelegateInstance;
```

Then we find the following definition which is also:
- A class template with additional `RetType`, and variadic `ArgTypes` parameters
- `IBaseDelegateInstance` specialized for [function types](https://stackoverflow.com/questions/23219227/function-type-vs-function-pointer-type).

```cpp
template <typename RetType,
  typename... ArgTypes>
struct IBaseDelegateInstance
  <RetType(ArgTypes...)>
{
 /**
  * Execute the delegate.
  If the function pointer
  is not valid, an error
  will occur.
  */
  virtual RetType
  Execute(ArgTypes...) const = 0;
};
```

## Part 2: TMemFunPtrType

Forward declared template class that will be used to generate the signature of a "pointer to member function" type.

```cpp
template <bool Const,
  typename Class,
  typename FuncType>
struct TMemFunPtrType;
```

Similarly as before we find the following definition which is:
- A class template with additional `Class`, `RetType` and variadic `ArgTypes` parameters
- `TMemFunPtrType` specialized for `when Const is false` and `when FuncType is RetType(ArgTypes...)`.

```cpp
template <typename Class,
  typename RetType,
  typename... ArgTypes>
struct TMemFunPtrType<false,
  Class,
  RetType(ArgTypes...)>
{
  typedef RetType(Class::* Type)(ArgTypes...);
};
```

And for pointers to constant member functions we have the following:

- `TMemFunPtrType` specialized for `when Const is true` and `when FuncType is RetType(ArgTypes...)`.

```cpp
template <typename Class,
  typename RetType,
  typename... ArgTypes>
struct TMemFunPtrType<true,
  Class,
  RetType(ArgTypes...)>
{
  typedef RetType(Class::* Type)(ArgTypes...) const;
};
```

## Part 2: TBaseRawMethodDelegateInstance

Implements a delegate binding for C++ member functions, this class is intended to hold a pointer to an `object`
and a pointer to a function in the `object`. First we find the following forward declared template class

```cpp
template <bool bConst,
  class UserClass,
  typename FuncType>
class TBaseRawMethodDelegateInstance;
```

And the following definition which finally holds pointer to things:

- A class template with additional parameters:
  - `bConst`: Is `TBaseRawMethodDelegateInstance` holding a constant member function?
  - `UserClass`: The type of the object that has the member function.
  - `WrappedRetValType`: The type of the return value of the member function.
  - Variadic `ParamTypes`: The type of the parameters of the member function (if any).

```cpp
template <
  bool bConst,
  class UserClass,
  typename WrappedRetValType,
  typename... ParamTypes>
```

- `TBaseRawMethodDelegateInstance` specialized for:
  - `when Const is true or false`
  - `when UserClass is` whatever it comes from template argument `UserClass`
  - `when FuncType is WrappedRetValType(ArgTypes...)`.

```cpp
class TBaseRawMethodDelegateInstance<
  bConst,
  UserClass,
  WrappedRetValType(ParamTypes...)>
```

- A class that extends (and implements) the abstract class `IBaseDelegateInstance` with `FuncType` evaluated to the function type
`WrappedRetValType(ParamTypes...)`
```cpp
  : public IBaseDelegateInstance<
  WrappedRetValType(ParamTypes...)>
{
```

- Typedef of pointer to member function

```cpp
public:
  using FMethodPtr = typename TMemFunPtrType<
    bConst,
    UserClass,
    WrappedRetValType(ParamTypes...)>::Type;
```

- Constructor receiving:
  - Pointer to an `UserClass` object.
  - Pointer to a member function in the object.

```cpp
  TBaseRawMethodDelegateInstance(
    UserClass* InUserObject,
    FMethodPtr InMethodPtr)
  : UserObject(InUserObject), MethodPtr(InMethodPtr)
  {
    // ORIGINAL UNREAL NOTE:
    // Non-expirable delegates must always
    // have a non-null object pointer on
    // creation (otherwise they could never execute.)
    // check(InUserObject != nullptr &&
    //       MethodPtr != nullptr);
  }
```

- Implements the `Execute` method from the abstract class `IBaseDelegateInstance<WrappedRetValType(ParamTypes...)>`
here is where we finally invoke the function pointer.

```cpp
  WrappedRetValType Execute(
    ParamTypes... Params) const override
  {
    // NOTE: This is an oversimplified version
    // check unreal source code for more fun.
    return (UserObject->*MethodPtr)(Params...);
    //return std::invoke(MethodPtr, ParamTypes...);
  }
```

- Class defines the following fields to hold the pointer to `UserClass` object and its `member function`.

```cpp
private:
  UserClass* UserObject;
  FMethodPtr MethodPtr;
};
```

## Exercise 1: Free function pointers

Based on previous notes implement your own `IBaseDelegateInstance` class which will be used to hold pointers to free functions (Solution at end of this article).

## Part 3: TMyDelegate

The macro `DECLARE_DELEGATE(DelegateName)` declares a `TDelegate` type, so you can create your own objects of this type.
Also note that in this document I renamed this to `TMyDelegate` in order to hint that the code shown below is an extremely
over simplified version inspired from the original Unreal code and is only intended for study to
interested readers on more in-depth diving into Unreal internals.

First we find the following templated class that will be used if you tell the compiler
to instantiate something that is not a function e.g.: `TMyDelegate<int>`, read the next section to understand
why this works.

```cpp
/**
 * Unicast delegate template class.
 *
 * Use the various DECLARE_DELEGATE
 * macros to create the actual delegate
 * type, templated to the function
 * signature the delegate is compatible with.
 * Then, you can create an instance
 * of that class when you want to
 * bind a function to the delegate.
 */
template<typename DelegateSignature>
class TMyDelegate
{
	static_assert(sizeof(DelegateSignature) == 0, "Expected a function signature for the delegate template parameter");
};
```
Now you find `TMyDelagate` specialized for `when DelegateSignature is` the function type `InRetValType(ParamTypes...)`,
otherwise it will fallback to the non-specialized version defined previously.

```cpp
template<typename InRetValType, typename... ParamTypes>
class TMyDelegate<InRetValType(ParamTypes...)>
{

}
```

Unreal defines the following type aliases.

```cpp
/* ...class TMyDelegate declaration... */
{
  using FuncType = InRetValType(ParamTypes...);
  using IBaseDelegateInstanceType = IBaseDelegateInstance<FuncType>;
  using RetValType = InRetValType;
}
```

And the static Create functions which you usually use to create a delegate object and bind it to a function:

```cpp
  /**
  * Static: Creates a raw C++ pointer
  * member function delegate.
  *
  * Raw pointer doesn't use any sort of reference,
  * so may be unsafe to call if the object was
  * deleted out from underneath your delegate.
  * Be caref  ul when calling Execute()!
  */
  template <typename UserClass>
  inline static TMyDelegate<RetValType(ParamTypes...)>
  CreateRaw(  
    UserClass* InUserObject,
    typename TMemFunPtrType<false,
      UserClass,
      RetValType(ParamTypes...)
    >::Type InFunc)
  {
    TMyDelegate<RetValType(ParamTypes...)> Result;

    // Instance the Delegate instance
    Result.LocalDelegateInstance.reset(
    new TBaseRawMethodDelegateInstance<false,
      UserClass,
      FuncType>(InUserObject, InFunc));

    return Result;
  }
```
We also create our own version of the Execute method:

```cpp
  inline RetValType Execute(ParamTypes... Params)
  {
    return LocalDelegateInstance->Execute(Params...);
  }
```

And as a final simplification we create a field to hold our bound `IBaseDelegateInstanceType` object.

```cpp
private:
  std::shared_ptr<IBaseDelegateInstanceType>
    LocalDelegateInstance;
```

## Solution to exercise 1:

Below I put my own `IBaseDelegateInstanceType` code for free function delegate instances,
which you won't find on real Unreal code because I completely came up with this as exercise,
instead you should look for `TBaseStaticDelegateInstance`.

```cpp
/**
 * Implements a delegate binding for C++ free functions.
 */
template <typename FuncType>
class TBaseFreeFunctionDelegateInstance;

template <typename WrappedRetValType,
  typename... ParamTypes>
class TBaseFreeFunctionDelegateInstance<
  WrappedRetValType(ParamTypes...)>
  : public IBaseDelegateInstance<
    WrappedRetValType(ParamTypes...)>
{
public:
  using FFreeFunctionPtr = WrappedRetValType(*)(ParamTypes...);

  TBaseFreeFunctionDelegateInstance(FFreeFunctionPtr InFuncPtr)
  : FuncPtr(InFuncPtr)
  {

  }

  WrappedRetValType Execute(ParamTypes... Params) const override
  {
    return (*FuncPtr)(Params...);
  }

private:
  FFreeFunctionPtr FuncPtr;
};
```

## Part 4: Using "my delegate" class

We start defining the following class with a dummy member function.

```cpp
/* Dummy class with a method that
will be bound to a delegate*/
class MyClass
{
public:
    void HandleSomething(int Num, float Num2, const std::string& Name)
    {
        std::cout << "Handling something on member function listener with " << Num << " and " << Num2 << " by " << Name << std::endl;
    }
};
```

And also the following free function just for testing.

```cpp
/* Dummy free function that will be bound to a delegate*/
void HandleSomethingFromFreeFunction(int Num, float Num2, const std::string& Name)
{
    std::cout << "Handling something on free function listener with " << Num << " and " << Num2 << " by " << Name << std::endl;
}
```

Finally we instantiate our delegate objects and bound them to some functions.

```cpp

int main()
{
    MyClass obj;

    using MyDelegateSignature = TMyDelegate<void(int, float, const std::string&)>;

    // An invocation list whose targets are member function and free functions
    MyDelegateSignature MultiCastInvocationList[2]{
        MyDelegateSignature::CreateRaw(&obj, &MyClass::HandleSomething),
        MyDelegateSignature::CreateFreeFunction(&HandleSomethingFromFreeFunction)
    };

    // Invoke all the delegates (somehow similar to unreal multi-cast delegates)
    for (MyDelegateSignature& Delegate : MultiCastInvocationList)
    {
        Delegate.Execute(5, 10.0f, "Romualdo Villalobos");
    }
}
```

## Final comments:
Delegates on Unreal is a very robust system with a lot more of complexity than
shown in this article. Here we only explored the surface of some of the classes involved on unicast delegates
and on the final section we also noted how could we possibly create our own multicast delegates.

As a final comment please note this document consists of study notes on the delegate system internals and as such is very distanct from the full picture.
More fun is granted for you on the real source code.

## Links

- [Full code gist](https://gist.github.com/romualdo97/9482b924bab9644cbe914f92b607e670)
- [Unreal delegates](https://docs.unrealengine.com/4.27/en-US/ProgrammingAndScripting/ProgrammingWithCPP/UnrealArchitecture/Delegates/)
- [function type vs. function pointer type](https://stackoverflow.com/questions/23219227/function-type-vs-function-pointer-type)
- [TDelegate](https://docs.unrealengine.com/4.27/en-US/API/Runtime/Core/Delegates/TDelegate/)
- [TDelegate<InRetValType(ParamTypes...), UserPolicy>](https://docs.unrealengine.com/4.27/en-US/API/Runtime/Core/Delegates/TDelegate_InRetValType_ParamType-/)
- [std::shared_ptr](https://en.cppreference.com/w/cpp/memory/shared_ptr)

## Credits
Written by [Romualdo Villalobos](https://www.linkedin.com/in/romualdo-villalobos/)

</ProseBlock>

Understand how the unreal delegates works under the hood by implementing your own minimalist TDelegate class clone which can hold references to free and member functions uniformly.