C++ Lab 2. ITMO Endian

This repository contains my second laboratory work for the Programming Fundamentals course in C++.

The lab was completed during my first semester of the Software Engineering program at ITMO University. The project represents my early practical experience with C++ and basic programming concepts.

Below is the original laboratory assignment statement translated into English.

Check out my other C++ labs:

• First semester. Programming fundamentals in C++:
  • Lab 1. Log Analyzer
  • Lab 3. Sandpile Model
  • Lab 4. ArgParser
• Second semester. Programming in C++:
  • Lab 6. WayHome
  • Lab 7. Unrolled List
  • Lab 8. STL. Adapters
  • Lab 9. Scheduler
  • Lab 10. ITMOScript

---

🇬🇧 English | 🇷🇺 Русский

Task

You have already become familiar with various integer types (int32_t, int8_t, uint16_t) and learned that they can be stored in sign-magnitude, one's complement, and two's complement representations, as well as that their byte order can be different, for example, big endian and little endian.

In this work, you will have to design and implement your own unsigned integer type uint239_t, whose storage format is ITMO Endian.

Value range of this type: $[0; 2^{239} - 1]$.

Type size: 35 bytes.

For the type described above, the following set of functions and operators must be implemented:

1. Conversion from the uint32_t type.
2. Conversion from a string. For M3110-14, it is guaranteed that the number in the string is $< 2^{64}$.
3. Addition.
4. Subtraction.
5. Multiplication. Only for M3100-09.
6. Division. Only for M3100-09.
7. Outputting the number to a stream.
8. Getting the shift.
9. Equality check.
10. Inequality check.

ITMO Endian Format

In ITMO-endian, each byte contains 7 significant bits, which are the lower bits, and one service bit, which is the highest bit.

uint239_t occupies exactly 35 bytes. Since 239 is not divisible by 7, the bytes of uint239_t contain 6 padding bits, which are always equal to zero.

Thus, a uint239_t written in binary form contains:

• 239 significant bits.
• 35 service bits responsible for the shift.
• 6 padding bits, which are always equal to zero.

It is important to note that the padding bits participate in the shift.

For example, the number 2047 in ITMO Endian format will have the following representation. The service bits are highlighted in red, and the padding bits are highlighted in blue:

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{000000} \underbrace{0\dots0}_{260} \ \textcolor{red}{0} 0001111 \ \textcolor{red}{0} 1111111 \rangle, \qquad \text{Shift} = 0} $$

The service bits are responsible for the circular shift of the significant bits according to the following rule: the sequence of service bits represents an integer written in direct code and indicates by how many bits the significant bits have been circularly shifted to the left.

For example, the following bit sequences also encode 2047:

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{00000} \underbrace{0\dots0}_{260} \ \textcolor{red}{0} 0011111 \ \textcolor{red}{1} 111111\textcolor{blue}{0} \rangle, \qquad \text{Shift} = 1} $$

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{0000} \underbrace{0\dots0}_{260} \ \textcolor{red}{1} 0111111 \ \textcolor{red}{0} 11111\textcolor{blue}{00} \rangle, \qquad \text{Shift} = 2} $$

$$ \large{2047 = \langle \textcolor{red}{0} \textcolor{blue}{000} \underbrace{0\dots0}_{260} \ \textcolor{red}{1} 1111111 \ \textcolor{red}{1} 1111\textcolor{blue}{000} \rangle, \qquad \text{Shift} = 3} $$

Arithmetic Operations on ITMO Endian

Arithmetic operations on ITMO Endian work according to the following rules:

• Numbers encoded in ITMO Endian are added, subtracted, multiplied, and divided according to the rules of standard arithmetic.
• During operations, the shift of the resulting number is calculated from the shifts of the operands: it is the sum of the operand shifts for addition and multiplication, and the difference of the operand shifts for subtraction and division.
• Overflow of significant bits is Undefined Behavior.

Operation	Operation for the shift	Example
Addition	Addition	239 (shift 3) + 30 (shift 5) = 269 (shift 8).
Subtraction	Subtraction	239 (shift 3) - 30 (shift 5) = 209 (shift $2^{35} - 2$, because overflow occurs.
Multiplication	Addition	123 (shift 6) * 10 (shift 4) = 1230 (shift 10).
Division	Subtraction	42 (shift 7) / 5 (shift 2) = 8 (shift 5).

Implementation Instructions

You are given a project template consisting of three directories:

• bin
• lib
• tests

Changing the project structure or adding new files is forbidden.

Required:

1. Implement the uint239_t type by describing it in the header file lib/number.h. Note that such a structure already exists there; you need to complete its description.
2. Implement the functions and operators listed above by writing their implementation in lib/number.cpp.

Tests

The project contains a basic set of tests that allows you to make sure that the function implementation does not contain obvious errors.

To run the tests from the command line, you can execute the following command:

cmake --build . --target number_tests && ctest -V

or use the tools provided by your IDE.

Until all tests pass, the laboratory work must not be shown. Groups for which multiplication and division are not required may comment out the unnecessary tests; see the comment in the code.

The tests may be extended if desired, but this is not required.

The tests also complement the assignment by demonstrating the expected behavior of operators and functions.

If This Was Not Enough

The bin directory contains a console application that you may also use at your discretion, for example, to test your code.

To run it, execute the following command:

cmake --build . --target labwork2 && bin/labwork2

or use your IDE.

Note

The implementation of arithmetic operations is described in the code as the overloading of the corresponding operators. At the moment, we have not yet discussed operators and operator overloading in lectures, so for now the notation

uint239_t operator+(const uint239_t& lhs, const uint239_t& rhs)

should be interpreted as a function that takes two arguments, adds them, and returns a result of the same type.

Restrictions

• The use of standard containers is forbidden (std::vector, std::list, etc.).
• The use of std::bitset is forbidden.

Examples

Number Examples

1 with shift 1:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000010

1 with shift 3:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000010001000

Operation Examples

Let A be the first number from the example above, and B be the second one. Then:

A + B = 

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000100000

B - A = 

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000

Additional Information

• Most likely, you will need bitwise operations for the implementation.
• If you want to extend the tests, although this is not part of the assignment, the GoogleTest documentation can be found here.

Deadlines

1. 15.10.24 23:59 - 0.8
2. 22.10.24 23:59 - 0.65
3. 29.10.24 23:59 - 0.5