Homework 1

Author

Rohit Gurusamy Anandakumar

PART 1: Benchmark

Cyclic Redundancy Check (CRC) in BRIL

About CRC:

A Cyclic Redundancy Check (CRC) is an error-detecting code used in digital networks and storage devices to detect accidental changes to raw data. In embedded systems, CRCs are crucial for ensuring data integrity during communication, verifying data stored in memory, and validating firmware updates. They are popular due to their simplicity, efficiency in binary hardware, and effectiveness in detecting common transmission errors.

  • It ensure data integrity in communication protocols like UART, SPI, and I2C by detecting errors caused by noise or interference.
  • How CRC Works:
    • Polynomial Division: The data block is treated as a large binary number and divided by a fixed polynomial. The remainder of this division is the CRC value.
    • Appending CRC: The CRC value is appended to the data before transmission or storage.
    • Verification: Upon retrieval, the same polynomial division is performed. If the remainder matches the CRC value, the data is considered intact; otherwise, it indicates corruption
  • Learn more at: https://en.wikipedia.org/wiki/Cyclic_redundancy_check

CRC as Microbenchmark:

  • CRC calculations prominently involve memory allocation, extensively using ptr<int>.
  • CRC algorithms typically involve a mix of arithmetic (e.g., addition, subtraction, Multiplication) and bitwise operations (e.g., XOR, shifts).
  • This makes CRC an excellent microbenchmark for evaluating how well your Bril implementation handles these critical operations, which are essential for many real-world applications.

Helpful Tools:

  • Bril code for CRC is fully hand typed code of 300+ lines using VS Code, the most useful tool ever was Bril syntax highlighting Extension in VS Code.
  • Turnt tool was used to test and save the output file.
  • turnt.toml file:
    [envs.test]
    command = "bril2json < {filename} | brili -p {args}"
    output.out = "-"
    output.prof = "2"

Method:

%%{init: {"flowchart": {"htmlLabels": false}} }%%

%%| echo: false 
graph LR;
A[Initialize Inputs]--> B0[Get CRC Remainder] --> B1["Check CRC"] --> B2[Print Outputs];

Initialize Inputs:
Get CRC Remainder:
  • To divide Word and Divisor we need to do xor in each bit.
  • First copy first few bits from Word to Word_split having same length as Divisor.
  • Call @xorfunction and overwrite the result to first few bits of Word.
  • Call @shiftleft function to left shift the Word and decrement word_size.
  • Repeat this process until Word_size < Div_size.
  • At the end return Word as a crc_rem to @main.
  • Convert crc_rem from ptr<int> to int by calling toNum function.
Check CRC:
  • If: crc_rem == 0 then there is no error in bit and crc_check is true.
  • Else: there is a error and crc_check is false.

Test Cases:

Example 1
Get Remainder:
  • Input:
    word: int = const 1101101;
    word_size: int = const 7;
    divisor: int = const 10101;
    divisor_size: int = const 5;
    check_value: int = const 0;
  • Output:
    false
    1011
  • Total Dynamic Instructions:
    total_dyn_inst: 1784
Check CRC:
  • Input:
    word: int = const 1101101;
    word_size: int = const 7;
    divisor: int = const 10101;
    divisor_size: int = const 5;
    check_value: int = const 1011;
  • Output:
    true
    0
  • Total Dynamic Instructions:
    total_dyn_inst: 1784
Example 2
Get Remainder:
  • Input:
    word: int = const 11010011101100;
    word_size: int = const 14;
    divisor: int = const 1011;
    divisor_size: int = const 4;
    check_value: int = const 0;
  • Output:
    false
    100
  • Total Dynamic Instructions:
    total_dyn_inst: 3061
Check CRC:
  • Input:
    word: int = const 11010011101100;
    word_size: int = const 14;
    divisor: int = const 1011;
    divisor_size: int = const 4;
    check_value: int = const 100;
  • Output:
    true
    0
  • Total Dynamic Instructions:
    total_dyn_inst: 3061

PART 2: Analysis:

Finding Number of Functions and its Calls

Initialize

  • This analysis is done in python.
  • Using bril2json converting .bril file to JSON.
  • Loading into python file using prog = json.load(sys.stdin).
  • JSON heap structure will be loaded as dictionary in python.

Process

  • Counting all functions in bril.
  • Counting function calls of a function.

Test

  • Turnt.toml file:
    [envs.countFunc]
    default = false
    command = "bril2json < {filename} | python3 hw.py > {base}.txt"
  • Output is stored in .txt file.
Example 1: CRC
Input:
Output:
```
Number of Functions:  11
------------------------
Function Call Counts:
main     : 0
rem      : 1
n_zeros  : 2
toPtr    : 2
wordSplit: 1
xor      : 1
shiftLeft: 1
print_ptr: 0
crc_rem  : 1
crc_check: 1
toNum    : 1


##### Example 2: Fibonacci
###### Input: 
- file: <https://github.com/normrubin/bril/blob/main/benchmarks/core/fibonacci.bril>

###### Output:
    ```
    Number of Functions:  2
    ------------------------
    Function Call Counts:
    main     : 0
    Fibonacci: 3
Back to top