Multiple definitions in COFF

A couple of days ago, I was curious about how the linker deals with multiple definitions of a function. So I read Microsoft's online PE documentation about the COFF format and how COFF was dealing with multiple defintions. In this post, I'm going to investigate some simple object files with dumpbin from Microsoft. I'm using Visual studio 2019, C++ 14, 32 bit. The compiler flags will be stated further down in this post. So grab another cup of coffee and let's get started! 

As mentioned above, the online PE documentation is of great help when understanding the structure of the object file. It states that a section is a basic unit of code or data within a PE or COFF file. Below, we will learn that COMDAT is a special type of section, and we will further dig into this. 

First, I will have a brief discussion with an introductory example of the symbol table. Then I will present a couple of setups, where each setup is slightly different. My focus will be on the .text sections, since the code resides inside those. Below is the code for this introductory example.

int main()
{
   return 0;
}

The code resides inside main.cpp and is compiled into main.obj, using these flags.

/JMC /permissive- /ifcOutput "Debug\" /GS /analyze- /W3 /Zc:wchar_t /ZI /Gm- /Od /sdl /Fd"Debug\vc142.pdb" /Zc:inline /fp:precise /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /errorReport:prompt /WX- /Zc:forScope /RTC1 /Gd /Oy- /MDd /FC /Fa"Debug\" /EHsc /nologo /Fo"Debug\" /Fp"Debug\project.pch" /diagnostics:column

I will dump the symbol table by using dumpbin, like this:

dumpbin /symbols main.obj

Dumping the symbols gives output below (truncated).

COFF SYMBOL TABLE
000 010575C9 ABS    notype       Static       | @comp.id
001 80010391 ABS    notype       Static       | @feat.00
002 00000002 ABS    notype       Static       | @vol.md
003 00000000 SECT1  notype       Static       | .drectve
    Section length   85, #relocs    0, #linenums    0, checksum        0
    Relocation CRC 00000000
006 00000000 SECT2  notype       Static       | .debug$S
    Section length  1E0, #relocs    2, #linenums    0, checksum        0
    Relocation CRC BE724FAD
009 00000000 SECT3  notype       Static       | .msvcjmc
    Section length    1, #relocs    0, #linenums    0, checksum 77073096
    Relocation CRC 00000000
00C 00000000 SECT3  notype       Static       | __D3C22540_main@cpp
00D 00000000 SECT4  notype       Static       | .text$mn
    Section length    5, #relocs    0, #linenums    0, checksum 672BE856, selection    2 (pick any)
    Relocation CRC 4A6A8444
010 00000000 SECT5  notype       Static       | .debug$S
    Section length   98, #relocs    3, #linenums    0, checksum        0, selection    5 (pick associative Section 0x4)
    Relocation CRC B9D5806A
013 00000000 SECT6  notype       Static       | .text$mn
    Section length   37, #relocs    3, #linenums    0, checksum A2398015, selection    1 (pick no duplicates)
    Relocation CRC 2E7CF6B9
016 00000000 SECT7  notype       Static       | .debug$S
    Section length  104, #relocs    9, #linenums    0, checksum        0, selection    5 (pick associative Section 0x6)
    Relocation CRC 351E60C8
019 00000000 SECT6  notype ()    External     | _main

In the truncated table above, we can see 26 entries from the symbol table, where the 26th entry is telling us that the symbol _main is external and belongs to section #6. 

From the online PE documentation, we can understand that the sections are defined inside the symbol table as well. For such entry, SECT6 (entry 0x13 above), there follows another entry (entry 0x014 above), providing information about the section. This entry is in Auxiliary Format 5 and since section #6 is a COMDAT section (see below for explanation), there is a selection type defined, in this case 1 (pick no duplicates). The selection type tells linker how to deal with multiple definitions of COMDATA sections. In this particular case, the linker only accepts one definition, if there are more, the linker issues a multiple definition error.

Further, I will dump the headers for each section, like this:

dumpbin /headers main.obj

Dumping the headers gives the output below (only section header #6 pasted).

SECTION HEADER #6
.text$mn name
       0 physical address
       0 virtual address
      37 size of raw data
     501 file pointer to raw data (00000501 to 00000537)
     538 file pointer to relocation table
       0 file pointer to line numbers
       3 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= _main
         16 byte align
         Execute Read

In the truncated output above, we can see section flags 60501020. The online PE documentation (Section Flags) can be used to understand the 60501020. It's also briefly described in the output above; the section contains executable code, the section contains COMDAT data, the section can be executed as code, the section can be read.

Now let's look into the different setups. Each setup contains a main.cpp with a main function and a variation of additional source files. The figure summarize the source files and resulting object files with its symbols. The compiler options are according to the introductory example above. In each setup, after the figure, I will present the important parts of the object files (using the commands described above) and have a brief discussion. Let's look at the first one.

Setup 1

Figure 1

void helperfunc1()
{}

00D 00000000 SECT4  notype       Static       | .text$mn
    Section length   35, #relocs    3, #linenums    0, checksum  DB372CC, selection    1 (pick no duplicates)
    Relocation CRC E4C10A68

019 00000000 SECT4  notype ()    External     | ?helperfunc1@@YAXXZ (void __cdecl helperfunc1(void))

SECTION HEADER #4
.text$mn name
       0 physical address
       0 virtual address
      35 size of raw data
     45A file pointer to raw data (0000045A to 0000048E)
     48F file pointer to relocation table
       0 file pointer to line numbers
       3 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl helperfunc1(void)" (?helperfunc1@@YAXXZ)
         16 byte align
         Execute Read

From above, we see entry 0x00D and entry 0x019 in the symbol table, which defines SECT4 and the external symbol ?helperfunc1@@YAXXZ, which is the name mangled name of the function helperfunc1. 

Setup 2

Figure 2

static void helperfunc1()
{}

COFF SYMBOL TABLE
000 010575C9 ABS    notype       Static       | @comp.id
001 80010391 ABS    notype       Static       | @feat.00
002 00000002 ABS    notype       Static       | @vol.md
003 00000000 SECT1  notype       Static       | .drectve
    Section length   41, #relocs    0, #linenums    0, checksum        0
    Relocation CRC 00000000
006 00000000 SECT2  notype       Static       | .debug$S
    Section length  148, #relocs    2, #linenums    0, checksum        0
    Relocation CRC 3A286AB6
009 00000000 SECT3  notype       Static       | .msvcjmc
    Section length    1, #relocs    0, #linenums    0, checksum 77073096
    Relocation CRC 00000000
00C 00000000 SECT3  notype       Static       | __5291C45E_helperfuncs@cpp
00D 00000000 SECT4  notype       Static       | .debug$T
    Section length   5C, #relocs    0, #linenums    0, checksum        0
    Relocation CRC 00000000
010 00000000 SECT5  notype       Static       | .chks64
    Section length   28, #relocs    0, #linenums    0, checksum        0
    Relocation CRC 00000000

Running the dumpbin command with the symbol option gives no helperfunc1 symbol. The symbol is not present in the object file, since it is not used in the translation unit and is declared as static.

Setup 3

Figure 3

static void helperfunc1()
{}

void libfunc1()
{
   helperfunc1();
}

00D 00000000 SECT4  notype       Static       | .text$mn
    Section length   35, #relocs    3, #linenums    0, checksum  DB372CC, selection    1 (pick no duplicates)
    Relocation CRC E4C10A68

013 00000000 SECT6  notype       Static       | .text$mn
    Section length   3A, #relocs    4, #linenums    0, checksum 81ED1D3A, selection    1 (pick no duplicates)
    Relocation CRC B844FE03

01F 00000000 SECT4  notype ()    Static       | ?helperfunc1@@YAXXZ (void __cdecl helperfunc1(void))

020 00000000 SECT6  notype ()    External     | ?libfunc1@@YAXXZ (void __cdecl libfunc1(void))

SECTION HEADER #4
.text$mn name
       0 physical address
       0 virtual address
      35 size of raw data
     4AA file pointer to raw data (000004AA to 000004DE)
     4DF file pointer to relocation table
       0 file pointer to line numbers
       3 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl helperfunc1(void)" (?helperfunc1@@YAXXZ)
         16 byte align
         Execute Read

SECTION HEADER #6
.text$mn name
       0 physical address
       0 virtual address
      3A size of raw data
     65B file pointer to raw data (0000065B to 00000694)
     695 file pointer to relocation table
       0 file pointer to line numbers
       4 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl libfunc1(void)" (?libfunc1@@YAXXZ)
         16 byte align
         Execute Read

Now libfunc is calling helperfunc1. From above, we see entry 0x00D and entry 0x013 in the symbol table, which defines SECT4 and SECT6 respectively. We can also see the the symbol ?helperfunc1@@YAXXZ again, this time it's defined as a static symbol, since we defined helperfunc1 as static in the code. Further, we also see the external symbol ?libfunc1@@YAXXZ. Both symbols states for the linker that there is only one defintion allowed.

Setup 4

Figure 4

inline void helperfunc1()
{}

COFF SYMBOL TABLE
000 010575C9 ABS    notype       Static       | @comp.id
001 80010391 ABS    notype       Static       | @feat.00
002 00000002 ABS    notype       Static       | @vol.md
003 00000000 SECT1  notype       Static       | .drectve
    Section length   41, #relocs    0, #linenums    0, checksum        0
    Relocation CRC 00000000
006 00000000 SECT2  notype       Static       | .debug$S
    Section length  148, #relocs    2, #linenums    0, checksum        0
    Relocation CRC 3A286AB6
009 00000000 SECT3  notype       Static       | .msvcjmc
    Section length    1, #relocs    0, #linenums    0, checksum 77073096
    Relocation CRC 00000000
00C 00000000 SECT3  notype       Static       | __5291C45E_helperfuncs@cpp
00D 00000000 SECT4  notype       Static       | .debug$T
    Section length   5C, #relocs    0, #linenums    0, checksum        0
    Relocation CRC 00000000
010 00000000 SECT5  notype       Static       | .chks64
    Section length   28, #relocs    0, #linenums    0, checksum        0
    Relocation CRC 00000000

Running the dumpbin command with the symbol option gives no helperfunc1 symbol. The symbol is not present in the object file, since it is not used in the translation unit and declared inline. As a matter of fact, this symbols table looks identical with the symbol table from Setup 2.

Setup 5

Figure 5

inline void helperfunc1()
{}

void libfunc1()
{
   helperfunc1();
}

00D 00000000 SECT4  notype       Static       | .text$mn
    Section length   35, #relocs    3, #linenums    0, checksum  DB372CC, selection    2 (pick any)
    Relocation CRC E4C10A68

013 00000000 SECT6  notype       Static       | .text$mn
    Section length   3A, #relocs    4, #linenums    0, checksum 81ED1D3A, selection    1 (pick no duplicates)
    Relocation CRC B844FE03

01F 00000000 SECT4  notype ()    External     | ?helperfunc1@@YAXXZ (void __cdecl helperfunc1(void))

020 00000000 SECT6  notype ()    External     | ?libfunc1@@YAXXZ (void __cdecl libfunc1(void))

SECTION HEADER #4
.text$mn name
       0 physical address
       0 virtual address
      35 size of raw data
     4AA file pointer to raw data (000004AA to 000004DE)
     4DF file pointer to relocation table
       0 file pointer to line numbers
       3 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl helperfunc1(void)" (?helperfunc1@@YAXXZ)
         16 byte align
         Execute Read

SECTION HEADER #6
.text$mn name
       0 physical address
       0 virtual address
      3A size of raw data
     65B file pointer to raw data (0000065B to 00000694)
     695 file pointer to relocation table
       0 file pointer to line numbers
       4 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl libfunc1(void)" (?libfunc1@@YAXXZ)
         16 byte align
         Execute Read 

Now libfunc1 is calling helperfunc1. From above, we see entry 0x00D and entry 0x013 in the symbol table, which defines SECT4 and SECT6 respectively. We can also see the the external symbol ?helperfunc1@@YAXXZ and libfunc1@@YAXXZ. Unlike Setup 3, helperfunc1 is external and its selection type is 1, meaning any symbol can be linked.

Setup 6

Figure 6

inline void helperfunc1()
{}

#include "helperfuncs.hpp"

void libfunc1()
{
   helperfunc1();
}

00E 00000000 SECT4  notype       Static       | .text$mn
    Section length   35, #relocs    3, #linenums    0, checksum  DB372CC, selection    2 (pick any)
    Relocation CRC 16A75AA6

014 00000000 SECT6  notype       Static       | .text$mn
    Section length   3A, #relocs    4, #linenums    0, checksum 81ED1D3A, selection    1 (pick no duplicates)
    Relocation CRC B844FE03

020 00000000 SECT4  notype ()    External     | ?helperfunc1@@YAXXZ (void __cdecl helperfunc1(void))

021 00000000 SECT6  notype ()    External     | ?libfunc1@@YAXXZ (void __cdecl libfunc1(void))

SECTION HEADER #4
.text$mn name
       0 physical address
       0 virtual address
      35 size of raw data
     53B file pointer to raw data (0000053B to 0000056F)
     570 file pointer to relocation table
       0 file pointer to line numbers
       3 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl helperfunc1(void)" (?helperfunc1@@YAXXZ)
         16 byte align
         Execute Read

SECTION HEADER #6
.text$mn name
       0 physical address
       0 virtual address
      3A size of raw data
     6EC file pointer to raw data (000006EC to 00000725)
     726 file pointer to relocation table
       0 file pointer to line numbers
       4 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl libfunc1(void)" (?libfunc1@@YAXXZ)
         16 byte align
         Execute Read

This setup does not differ from Setup 5. The only difference is the created helperfuncs.hpp, which is included in the created libfuncs1.cpp. This is a more typical setup, where the inline function is defined inside the header file. Note that the symbol entries and sections are identical with Setup 5.

Setup 7

Figure 7

inline void helperfunc1()
{}

#include "helperfuncs.hpp"

void libfunc1()
{
   helperfunc1();
}

#include "helperfuncs.hpp"

void libfunc2()
{
   helperfunc1();
}

00E 00000000 SECT4  notype       Static       | .text$mn
    Section length   35, #relocs    3, #linenums    0, checksum  DB372CC, selection    2 (pick any)
    Relocation CRC 16A75AA6

014 00000000 SECT6  notype       Static       | .text$mn
    Section length   3A, #relocs    4, #linenums    0, checksum 81ED1D3A, selection    1 (pick no duplicates)
    Relocation CRC 4796C86E

020 00000000 SECT4  notype ()    External     | ?helperfunc1@@YAXXZ (void __cdecl helperfunc1(void))

021 00000000 SECT6  notype ()    External     | ?libfunc2@@YAXXZ (void __cdecl libfunc2(void))

SECTION HEADER #4
.text$mn name
       0 physical address
       0 virtual address
      35 size of raw data
     533 file pointer to raw data (00000533 to 00000567)
     568 file pointer to relocation table
       0 file pointer to line numbers
       3 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl helperfunc1(void)" (?helperfunc1@@YAXXZ)
         16 byte align
         Execute Read

SECTION HEADER #6
.text$mn name
       0 physical address
       0 virtual address
      3A size of raw data
     6E4 file pointer to raw data (000006E4 to 0000071D)
     71E file pointer to relocation table
       0 file pointer to line numbers
       4 number of relocations
       0 number of line numbers
60501020 flags
         Code
         COMDAT; sym= "void __cdecl libfunc2(void)" (?libfunc2@@YAXXZ)
         16 byte align
         Execute Read

This is even a more typical setup. The inline function is defined inside the header file. The header file is included in two cpp files. 

Above is only the symbol table for the additional file libfuncs2.obj stated. We can compare the symbols from libfuncs1.obj (from Setup 6) with the symbols from libfuncs2.obj in this Setup. Both object files contains the external symbol?helperfunc1@@YAXXZ, with selection type 2. Thanks to this selection type, the linker will not complain about multiple defintions during link time.

You are welcome to leave comments, complaints or questions!

Encoding CRC-32

CRC, cyclic redundant check, is a method for error detection. In this post, I'm focusing on different implementations of the CRC calulation and more specific the CRC-32 calculation and its variations. Finally, I will investigate a zip file and its CRC calculation. I'm using Visual Studio 2019 Community, HxD editor and WinRar.

Before going into the implementation, I will provide a short overview of the CRC. I have no intention to explain the theory in detail, I leave that to other resources on the web. I'm focusing on CRC-32 since it's used in the zip file.

CRC is a type of cyclic block codes. Cyclic block codes are a type of linear block codes. The CRC itself is a number, typically 8- 16- or 32- bits in size. It is calculated from the message data and a polynom. Typically the CRC bits together with the message data forms a code word, which is modulated and sent over a channel.

Regarding the calculation, it can be described from a mathematical point of view using long division. It can also be described from a LFSR (Linear-feedback shift register) point of view and that is what is described here.

The LFSR can be described as a fixed number of cascaded flip-flops. Each clock tick will shift around the content (0 or 1) of the flip-flops according to the polynom. The polynom specify how many flip-flops, how many XOR gates and where they are in the circuit. We will have a look at the CRC-32 circuit in a moment.

A commonly used CRC-32 polynom, used in Ethernet, PKZIP and other applications, is defined as: 

G(x) = x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

The polynom can be written in two forms, forward and reversed. In addition, the MSB can be omitted, since it is always 1.

Forward form:    x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

Reversed form: 1 + x + x² + x⁴ + x⁵ + x⁷ +  x⁸ + x¹⁰ + x¹¹ + x¹² + x¹⁶ + x²² +  x²³ + x²⁶

For implementation purpose, we can translate the polynom into a binary/hexadecimal number.

Forward form:    00000100110000010001110110110111 (0x04C11DB7)

Reversed form:   11101101101110001000001100100000 (0xEDB88320)

The CRC-32 circuit can be represented as:

CRC-32 circuit

In the circuit above, there are 32 flip-flops and 14 XOR gates. For each clock tick, each flip-flop shift out its content. This means the XOR gate in the top right corner will produce a new LSB value based on the MSB and the incoming message bit.

Let's start the discussion about the CRC-32 implementation by showing an example that simulates the CRC-32 circuit.

uint32_t CalcCrc32_LeftShift(const std::vector<uint8_t>& bytes)
{
  uint32_t crcRegister = 0xFFFFFFFF;

  for (auto byte : bytes) {
    for (int j = 0; j < 8; j++) {
      uint32_t result = ((byte << 24) ^ crcRegister) & 0x80000000;
      crcRegister <<= 1;
      if (result) crcRegister ^= 0x04C11DB7;
      byte <<= 1;
    }
  }

  return ~crcRegister;
}

What's going on here?
Here is the short story. The function takes a vector of bytes (message data) and produce a CRC by doing a MSB shift (left shift) for each bit in the message data and applying the normal CRC-32 polynom when needed.

Here is the long story. The variable uint32_t crcRegister is used to represent the 32 bit LFSR. The crcRegister simulates the cascaded flip-flops, where the MSB of the crcRegister corresponds to flip-flop 31 in the CRC-32 circuit. For each byte, we loop 8 times, which simulates 8 clock ticks, i.e. 8 shifts. We have to shift 8 times since one byte is 8 bits. For each clock tick, the content of crcRegister will be updated. From the CRC-32 circuit, we can observe that we only need to apply the CRC-32 polynom if the output from the XOR gate in the top right corner is 1. I will explain in moment why. By "apply" the forward CRC-32 polynom, I mean perform each XOR operation in the CRC-32 circuit. The output from the XOR gate in the top right corner, is actually represented by the MSB in the variable uint32_t result. So let's say that the MSB in result is 1, then we know for sure that one of the operands in each XOR operations will have the value 1. The other operand in each XOR operation is the value shifted out from the flip-flop, which can be either 0 or 1. So the result of performing each XOR operation may either be 0 or 1. On the other hand if the MSB in result is 0, then we know for sure that one of the operands in each XOR operation will have the value 0. The other operand in each XOR operations is the value shifted out from the flip-flop, which can either be 0 or 1. So the result of performing each XOR operation can always be considered as the value shifted out from the flip-flop, meaning no XOR operation is neeed.

Below is a program, which is calcules the CRC-32 code (CRC-32 BZIP2) from a message data.

int main() {
  std::vector<uint8_t> messageData = {0xDE, 0xAD, 0xBE, 0xEF};
  auto crc32_BZIP2 = CalcCrc32_LeftShift(messageData);
  std::cout << std::hex << crc32_BZIP2 << std::endl;
  return 0;
}

CRC-32 BZIP2 = 0x7e25e5e7 for message data = 0xDEADBEEF

There are details in the function CalcCrc32_LeftShift that I've not discussed yet. These details are related to the name CRC-32 BZIP2, which I will desribe in a moment. Except from the polynom, there are additional parameters that can be variated to obtain slightly differerent CRC-32 codes. I will discuss them below.

The initialization value of the crcRegister is commonly set to 0x00000000 or 0xFFFFFFFF. From an LFSR point of view, the flip-flops are set to 0 or 1.

We may choose to perform a bitwise inversion of the final result. Note that this can be achieved by applying an XOR operation with 0xFFFFFFFF of the final result as well.

There are two more possible parameters. For each byte, we may (or not) reflect the input, i.e the bits in the message data. Further, we may (or not) reflect the output, i.e. the bits in final result after all iterations.

Take a look at the previous program again, which calls the function CalcCrc32_LeftShift. First we have the polynom, which is set to 0x04C11DB7. There is no reflection of the input. The initialization value is set to 0xFFFFFFFF. The MSB in the crcRegister is shifted out and processed together with the MSB in the message bytes. The output is inverted. There is no reflection of the output. All these parameters together gives the specific CRC-32 code called CRC-32 BZIP2 code. 

For further variations of the parameters and its specific CRC-32 code, I recommend the Online CRC calculator.

Let's have a look at another program where the input and output are reflected. The name of this specific CRC-32 code, is simply CRC-32. The bits in each byte must be reflected as well as the final result. In other words, the MSB in the crcRegister is shifted out and processed together with the LSB in the message bytes. Below is an implementation of reflecting data.

template <class T>
T Reflect(T in)
{
  T x = in;
  T out = 0;
  auto n = sizeof(T) * 8;
  for (auto i = 0; i < n; i++) {
    out = out << 1 | (x & 1);
    x >>= 1;
  }

  return out;
}

std::vector<uint8_t> Reflect(const std::vector<uint8_t>& data)
{
  std::vector<uint8_t> result(data.size());
  std::transform(data.begin(), data.end(), result.begin(), 
                 [](auto byte) { return Reflect(byte); });

  return result;
}

int main() {
  std::vector<uint8_t> messageData = {0xDE, 0xAD, 0xBE, 0xEF};
  auto crc32 = Reflect(CalcCrc32_LeftShift(Reflect(messageData)));
  std::cout <<  std::hex << crc32 << std::endl;
  return 0;
}

CRC-32 = 0x7c9ca35a for message data = 0xDEADBEEF

There is a more efficient way to calculate the CRC-32 above by using a right shift implementation instead. In this implemenation the reversed polynom come in handy.

uint32_t CalcCrc32_RightShift(const std::vector<uint8_t>& bytes)
{
  uint32_t crcRegister = 0xFFFFFFFF;

  for (auto byte : bytes) {
    for (int j = 0; j < 8; j++) {
      uint32_t result = (byte ^ crcRegister) & 1;
      crcRegister >>= 1;
      if (result) crcRegister ^= 0xEDB88320;
      byte >>= 1;
    }
  }

  return ~crcRegister;
}

int main() {
  std::vector<uint8_t> messageData = {0xDE, 0xAD, 0xBE, 0xEF};
  auto crc32 = CalcCrc32_RightShift(messageData);
  std::cout <<  std::hex << crc32 << std::endl;
  return 0;
}

CRC-32 = 0x7c9ca35a for message data = 0xDEADBEEF

We can understand the simularity between the reversed input/output left shift version and right shift version. In both cases, we process the MSB in the crcRegister together with LSB in the message bytes.

From above, we can conclude:
CRC-32 BZIP2 = CalcCrc32_LeftShift(messageData) = Reverse(CalcCrc32_RightShift(Reverse(messageData)) 

CRC-32 = CalcCrc32_RightShift(messageData) = Reverse(CalcCrc32_LeftShift(Reverse(messageData))

Before ending this post, I will have a quick look at a compressed file and its CRC code.

I'm using HxD to create a simple file, containing 0xDEADBEEF.

HxD - Uncompressed file

I compress it, using WinRar,  and look into the compressed file using HxD.

HxD - Compressed file

According to Wikipedia - Zip,  we can see that the CRC code is at offset 14 in the file header. This code is what we've recently calculated, i.e. the CRC-32 code.

You are welcome to leave comments, complaints or questions!

Representation of big- and little- endians in memory

In previous posts, I've briefly discussed endianess. In this post I will look further into this topic and provide some C++ code. I'm using Windows 10 64 bit with Microsoft Visual Community C++2019.

When I'm building programs in my IDE, I'm building in x86 debug mode. Yes, x86 means little endianess. Little endianess means LSB byte of the data is stored at lower address.

Let's look into an C++ example, how to display the addresses and values.

uint32_t data = 0xDEADBEEF;

This is the value we are going investigate how it's represented in memory. The LSB byte is EF and since we are dealing with x86, it will be stored at lower address.

First we need a function to output the content of each memory address.

void DisplayMemory(uint32_t data)
{
  auto address = reinterpret_cast<uint8_t*>(&data);
  auto n = sizeof(data);

  for (std::size_t i = 0; i < n; i++) {
    std::cout << "[" 
              << static_cast<void*>(address + i) 
              << "]: " 
              << std::setw(2) 
              << std::setfill('0')
              << std::hex
              << static_cast<uint32_t>(*(address + i))
              << std::endl;
  }
}

Let's discuss the snippet above in more detail.

auto address = reinterpret_cast<uint8_t*>(&data);

Above, we cast the address of data from uint32_t pointer to uint8_t pointer and store it in an address pointer. We have to do this cast, so we can step the address pointer byte by byte. Since those types are unrelated, we have to use the reinterpret_cast operator (and not static_cast) for this purpose. We could use (uint8_t*) for conversion as well. Let's continue with the display part of the code.

std::cout << "[" 
          << static_cast<void*>(address + i) 
          << "]: " 
          << std::setw(2) 
          << std::setfill('0')
          << std::hex
          << static_cast<uint32_t>(*(address + i))
          << std::endl;

Above, we cast address + i, i.e. the uint8_t pointer to void pointer. Why? If we pass uint8_t pointer to the operator<<, it will handle the pointer as a string (char*). Since we want to display the address as a hexadecimal address, we must use the static_cast operator and cast to void pointer for this purpose. It is sufficient with the static_cast operator, since all types of pointers can be converted to void pointers (reinterpret_cast not needed).

There is one more static_cast above. It is needed to display the content of the address pointer. Like the previously cast, we need static_cast since we don't want to display a character, but a number. As a matter of fact, integer promotion could have solved this as well.

+(*(address + i))

The for-loop call std::cout for each address pointer and display the associated byte value.

Note that we could have used printf as well in this example.

printf("[%x]: %.2x\n", address + i, *(address + i));

Let's find out how the output from this code below, look like.

DisplayMemory(data);

 

0xDEADBEEF - Little endianess

Above, we see the little endianess representation of 0xDEADBEEF. LSB byte ef is stored at lower address.

Now, let's continue with big endianess. Big endianess means MSB byte of the data is stored at lower address. In our example, the MSB byte is DE, it will be stored at lower address, which we will se below.

First we need a function to convert from little endianess to big endianess.

uint32_t SwapEndians(uint32_t data)
{
   return (data >> 24) | 
           ((data & 0x00FF0000) >> 8) |
           ((data & 0x0000FF00) << 8) | 
           (data << 24);
}

The implementation above uses shift and binary manipulations. Another implementation would be to copy the bytes in wanted order.

uint32_t SwapEndians(uint32_t data)
{
  uint32_t result;
  uint8_t *resultPtr = reinterpret_cast(&result);
  uint8_t *dataPtr = reinterpret_cast(&data);
  resultPtr[0] = dataPtr[3];
  resultPtr[1] = dataPtr[2];
  resultPtr[2] = dataPtr[1];
  resultPtr[3] = dataPtr[0];
  
  return result;
}

Now, let's use this function to display the big endian representation of 0xDEADBEEF.

uint32_t data = 0xDEADBEEF;
auto b = SwapEndians(data);
DisplayMemory(b);

0xDEADBEEF - Big endianess

Above, we see the big endianess representation of 0xDEADBEEF. MSB byte be is stored at lower address.

You are welcome to leave comments, complaints or questions!

Representation of data types in memory - Part 3

You have probably written statements like this thousand of times, but do you know what's going on under the hood?

float foo = 1.21;

This is the continuation of my series about representation of data types in memory. In my previous post, I've discussed the numerical integral types. Now it's time to dig into the wonderful world of floating types. There is a lot to discuss about floating types, so in this post I will focus on the Normalized form and its representation in memory.

Every C++ programmer has dealt with the data types float and double and we will soon see how they are represented in memory. But before doing that, we need to understand some basic concepts and formats, so let's discuss some theory before proceeding to the practical part.

My intention is not to give a complete description about the theory of floating points, I will give a very brief summary here (and I mean it!), the details can easily be found on the net.

Below is a very good description (from this site), which describes how a floating point is expressed when stored in memory.

A floating-point number is typically expressed in the scientific notation, with a fraction (F), and an exponent (E) of a certain radix (r), in the form of F×rE. Decimal numbers use radix of 10 (F×10E); while binary numbers use radix of 2 (F×2E).

Example:
Let's say we have 16.2510. By using the scientific notation, it can be written as 16.2510 * 100 or 1.62510 * 101 and so forth. In binary, it can be written as 10000.012 * 2⁰, 1000.0012 * 2¹, 100.00012 * 2², 10.000012 * 2³ or 1.0000012 * 2⁴ and so forth. The representation used in a floating point is 1.0000012 * 2⁴, which is called the Normalized form.

The IEEE standard 754 describes the single precision format and double precision format. It is important to have a brief understanding of these formats, because the floating types in C++ is based on them.

According to MSDN, following is stated (Visual Studio 2010 specific) for the data type float;

The float type is stored as a four-byte, single-precision, floating-point number. It represents a single-precision 32-bit IEEE 754 value.

According to MSDN, following is stated (Visual Studio 2010 specific) for the data type double;

The double type is stored as an eight-byte, double-precision, floating-point number. It represents a double-precision 64-bit IEEE 754 value.

Voila! There we have the basic definition of the data types float and double.

The single precision format consists of 32 bits (4 bytes), where the Most Significant Bit (MSB) represent the sign (S) bit, the following 8 bits represent the exponent (E), and the 23 Least Significant Bit(s) (LSB) represent the fraction (F). Note that a bias is applied to the exponent (E) in order to represent both positive and negative exponents. The bias is 127 in single precision format, meaning exponent (E) = 0 is represented as 127, E=1 is represented as 128 and so on.

The double precision format consists of 64 bits (8 bytes), where the MSB represent the sign (S) bit, the following 11 bits represent the exponent (E), and the 52 LSB(s) represent the fraction (F). Note that a bias is applied to the exponent (E) in order to represent both positive and negative exponents. The bias is 1023 in double precision format, meaning exponent (E) = 0 is represented as 1023, E=1 is represented as 1024 and so on.

Before proceeding to the practical part, just a few words about Normalized form.

As we have seen above, Normalized form means we have an implicit leading 1 to the left of the radix point, which is used in the fraction (F), for instance 1.0000012. This leading 1 is not represented in the 32/64 bit format, but we know the leading 1 is there, if Normalized form is used.

Let's look into a simple application. This is very similar to my previous simple application, except from the fact the data type is float.

int main()
{
   float a = 1.0;
   float b = 2.0;
   float c = 3.0;
   float d = 4.0;

   return 0;
}

When starting WinDbg and execute all the initializations statements, we see the result below.

WinDbg - Memory view after initializations

As discussed in previous posts, in the Memory view, we can see the blue rectangle which indicates the inserted block of 0xCC which is typically done in Debug mode. The blue arrow shows the offset of the Memory view, which is where the insertion of 0xCC starts. Each float is also "guarded" by four bytes 0xCC. In the Disassembly view, we can notice that special floating point instructions are used. I will not discuss them in detail here, if you want more information, they are described in Intel x86 reference manual, more specific in the section "Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M"

Binary representation of 1.0

To understand how a float is stored in the memory, I will work through a couple of examples. Let's start with the first statement in the simple application;

float a = 1.0;

In binary we have 1.010 = 1.02, which is equal to 1.02 * 20 in Normalized form. Now let's see how this number 1.02 * 20 is stored in memory bit by bit.
Positive number -> Sign (S) bit = 02
Exponent: 0, i.e. the exponent (E) is represented as 12710 = 011111112
Fraction (F): 02 = 000000000000000000000002
Binary representation: 00111111 10000000 00000000 000000002
Hexadecimal representation: 3F80000016

This number is stored in the memory by this instruction;

fstp    dword ptr[ebp-8h]

The fstp instruction (Store Floating Point Value) copies the value from the FPU register stack to the memory in either single- or double precision format (single in this case due to float type). Note that the fld1 (Load Floating Point Value) instruction pushed this value (1.0) onto the FPU register stack in the first place. 0x3F800000 will be stored at memory address ebp-0x8. Taking little-endian into account, each byte will be saved according to below;

ebp-0x8: 0x00
ebp-0x7: 0x00
ebp-0x6: 0x80
ebp-0x5: 0x3F

Binary representation of 2.0

float b = 2.0;

Since 1.0 already was converted above, I will give a briefer explanation below.
Binary form: 10.02
Normalized form: 1.02 * 21
Positive number -> Sign (S) bit = 02
Exponent: 1, i.e. the exponent (E) is represented as 12810 = 100000002
Fraction (F): 02 = 000000000000000000000002
Binary representation: 01000000 00000000 00000000 000000002
Hexadecimal representation: 4000000016

This number is stored in the memory by this instruction;

fstp    dword ptr[ebp-14h]

Taking little-endian into account, each byte will be saved according to below;

ebp-0x14: 0x00
ebp-0x13: 0x00
ebp-0x12: 0x00
ebp-0x11: 0x40

Binary representation of 3.0

float a = 3.0;

Binary form: 11.02

Normalized form: 1.12 * 21
Positive number -> Sign (S) bit = 02
Exponent: 1, i.e., the exponent (E) is represented as 12810 = 100000002
Fraction (F): 12 = 100000000000000000000002
Binary representation: 01000000 01000000 00000000 000000002
Hexadecimal representation: 4040000016

This number is stored in the memory by this instruction;

fstp    dword ptr [ebp-20h]

Taking little-endian into account, each byte will be saved according to below;

ebp-0x14: 0x00
ebp-0x13: 0x00
ebp-0x12: 0x40
ebp-0x11: 0x40

Binary representation of 4.0

float a = 4.0;

Binary form: 100.02

Normalized form: 1.02 * 22
Positive number -> Sign (S) bit = 02
Exponent: 2, i.e. the exponent (E) is represented as 12910 = 100000012
Fraction (F): 02 = 000000000000000000000002
Binary representation: 01000000 10000000 00000000 000000002
Hexadecimal representation: 4080000016

This number is stored in the memory by this instruction;

fstp    dword ptr[ebp-2Ch]

Taking little-endian into account, each byte will be saved according to below;

ebp-0x14: 0x00
ebp-0x13: 0x00
ebp-0x12: 0x80
ebp-0x11: 0x40

The four examples above was only dealing with numbers in Normalized form. Later, I will have a look at the Denormalized form.

You are welcome to leave comments, complaints or questions!

Representation of data types in memory - Part 2

This is the continuation of the series "Representation of data types in memory". In this part, I will investigate how signed numerical integers are stored in memory. I'm using Windows Vista 32 bit with Microsoft Visual C++ 2010 Express (in Debug Mode) and WinDbg. Note that I'm not considering C++11.

Well, in my previous post, we saw how the unsigned numerical integers were saved in little-endian format in a block of 0xCC. This is of course true for signed numerical integers as well, but signed integers need to take the sign into account as well.

I will start this post in a similar way like my previous one, by using the same simple program, but with signed numerical integers.

int main()
{
   int a = -1;
   int b = -2;
   int c = -3;
   int d = -4;

   return 0;
}

When starting WinDbg and execute all the initializations statements, we see the result below.


WinDbg - Memory view after initializations

As discussed before, in the Memory view, we can see the blue rectangle which indicates the inserted block of 0xCC, which typically is done in Debug mode. The blue arrow shows the offset of the Memory view, which is where the insertion of 0xCC starts. Each integer is also "guarded" by four bytes 0xCC. Now we will focus on how the signed numerical integers are saved in memory. This is done by using the two's-complement representation. What is two's-complement? You can read all about it on the net, but here is a short explanation cited from wikipedia.

"Two's complement is a mathematical operation on binary numbers, as well as a binary signed number representation based on this operation. Its wide use in computing makes it the most important example of a radix complement."

There are a lot of in-depth information on the net how two's-complement conversion is done, here is my short version;

Invert all bits of the (positive) number and add one (+1).

Let's use an actual value from our simple program as an example, for instance;

int a = -1;

Positive number: 110

It's an int, i.e. four bytes in size -> 110 = 0000000116.

Then invert all bits; 0000000116 -> FFFFFFFE16
and then add one (+1); FFFFFFFE16 -> FFFFFFFF16

In other words, the number FFFFFFFF16, represent -1 in two's complement representation.

We can see this number in the Disassembly view, more specific, we can see this instruction;

mov     dword ptr [ebp-8],0FFFFFFFFh

It means that -1 is represented as 0xFFFFFFFF and will be stored at memory address ebp-0x8. Taking little-endian into account, each byte will be saved according to below;

ebp-0x8: 0xFF
ebp-0x7: 0xFF
ebp-0x6: 0xFF
ebp-0x5: 0xFF

Now let's continue with a similar program as in the first part in this series, this time with signed numerical integers.

int main()
{
   char a = -1;
   short int b = -2;
   int c = -3;
   long int d = -4;

   return 0;
}

When starting WinDbg and execute all the initializations statements, we see the result below.

WinDbg - Memory view after initializations

Like the first simple program, the blue arrow and blue rectangle, shows the inserted 0xCC done by the rep stos instruction.
Let's investigate how each type is stored. We know they are stored in two's-complement little-endian format.

Below, I've used following shorthand to denote the two's complement conversion for each type;

Positive number (using correct size) -> Invert all bits -> Added 1

char a = -1;

0116 -> FE16 -> FF16

ebp-0x5: 0xFF

short int b = -2;

000216 -> FFFD16 -> FFFE16

ebp-0x14: 0xFE
ebp-0x13: 0xFF

int c = -3;

0000000316 -> FFFFFFFC16 -> FFFFFFFD16

ebp-0x20: 0xFD
ebp-0x1F: 0xFF
ebp-0x1E: 0xFF
ebp-0x1D: 0xFF

long int d = -4;

0000000416 -> FFFFFFFB16 -> FFFFFFFC16

ebp-0x2C: 0xFC
ebp-0x2B: 0xFF
ebp-0x2A: 0xFF
ebp-0x29: 0xFF

You are welcome to leave comments, complaints or questions!