C-style array members

A while ago, I was dealing with a class with a c-style array member. Questions arose about how copy- and move- constructions works for such class. In this post, I will have a look how c-style array members are handled in such scenarios like copy- and move constructions. I will have a small discussion around initializations and take a look in the memory, using Visual studio 2019, C++14, 32 bit. 

Okay, let's start by define a struct and have some discussion about it.

struct SimpleStruct
{
   int myInts[4]
}

This is a simple struct. It's also meeting the criterias for being a POD as well as an aggregate. In the C++98 era, the typical initialization of such struct would be:

SimpleStruct s = {{1, 2, 3, 4}};

In C++11, the list initialization was introduced. We can use the list initialization syntax, in this case the copy list initialization version, which will perform aggregate initialization, since SimpleStruct is an aggregate.

SimpleStruct s = {{1, 2, 3, 4}};

The other form of list initialization, the direct list initialization, will also perform aggregate initialization. This syntax was not available in the C++98 era.

SimpleStruct s{{1, 2, 3, 4}};

Aggregate initialization typically performs a memberwise initialization. Let's look in memory, when the statement above has executed. Remember that 0xcc is the opcode for debug break.

0x00B5F9B0  00 00 00 00 5e ef 18 7b 74 60 26 7b cc cc cc cc  ....^ï.{t`&{ÌÌÌÌ
0x00B5F9C0  01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00  ................
0x00B5F9D0  cc cc cc cc f4 f9 b5 00 03 32 43 00 01 00 00 00  ÌÌÌÌôùµ..2C.....

Before continuing with the copy/move construction, let's see what std::is_trivial, std::is_standard_layout and std:: is_pod returns when taking SimpleStruct as a template argument.

int main()
{
    std::cout << std::boolalpha;
    std::cout << "SimpleStruct is trivial: " << std::is_trivial<SimpleStruct>::value << std::endl;
    std::cout << "SimpleStruct is standard layout: " << std::is_standard_layout<SimpleStruct>::value << std::endl;
    std::cout << "SimpleStruct is pod: " << std::is_pod<SimpleStruct>::value << std::endl;
}

SimpleStruct is trivial: true
SimpleStruct is standard layout: true
SimpleStruct is pod: true

Now. let's see what is happening when we want to copy an instance of SimpleStruct. Remember, since SimpleStruct does not define any special member functions, all of them are implicitly defined, including the copy- and move- constructor.

SimpleStruct s{{1, 2, 3, 4}};
SimpleStruct other{s};

Again, we are using direct list initialization, this time resulting in a call to the copy constructor. The copy constructor is implicitly defined and performs a memberwise copying. 

Let's look into the memory.

0x00F3FBA0  bc fb f3 00 cc cc cc cc 01 00 00 00 02 00 00 00  .ûó.ÌÌÌÌ........
0x00F3FBB0  03 00 00 00 04 00 00 00 cc cc cc cc cc cc cc cc  ........ÌÌÌÌÌÌÌÌ
0x00F3FBC0  01 00 00 00 02 00 00 00 03 00 00 00 04 00 00 00  ................
0x00F3FBD0  cc cc cc cc f4 fb f3 00 03 32 8d 00 01 00 00 00  ÌÌÌÌôûó..2......

Above, at 0x00F3FBC0, we have s, and at 0x00F3FBA8, we have other.

Finally, let's investigate the move construction.

SimpleStruct s{{1, 2, 3, 4}};
SimpleStruct other{std::move(s)};

It was this statement that orginally confused me. I had a poor understanding about memberwise moving for a class, which contains a c-style array and imagine a copy of a pointer, since c-style arrays, in general, decays into pointers. The move constructor is implicitly defined and performs a memberwise move. What does it mean for a c-style array? Well, applying std::move on a single int would imply a copy and applying std::move on a c-style array would imply a copy of the whole array.

Let's look into the memory.

0x010FF6C0  cc cc cc cc 01 00 00 00 02 00 00 00 03 00 00 00  ÌÌÌÌ............
0x010FF6D0  04 00 00 00 cc cc cc cc cc cc cc cc 01 00 00 00  ....ÌÌÌÌÌÌÌÌ....
0x010FF6E0  02 00 00 00 03 00 00 00 04 00 00 00 cc cc cc cc  ............ÌÌÌÌ

Above, at 0x010FF6DC, we have s, and at 0x010FF6C4, we have other.

According to this StackOverflow post, which is discussing the 'c-style array in a struct/class scenario', we have this statement from the C++ standard:

if the subobject is an array, each element is assigned, in the manner appropriate to the element type;

This is what we have seen above in the memory dumps.

You are welcome to leave comments, complaints or questions!

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 calculation 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 calculates 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 describe 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!